Decentralised Constraint Satisfaction
Example: Channel Allocation in WLANs
Wireless access points (APs) need to select a radio channel that minimises interference from other unlicensed-band radio transmitters, including other WLANs. In dense WLAN deployments, the collection of WLAN access points must jointly select their radio channels to minimize interference. This should be carried out without explicit co-ordination/message-passing between access points since (i) interfering access points need not be under common administrative control, (ii) it hugely simplifies implementation and rollout, (iii) it avoids introducing standardization issues. The solution must be robust, and not rely on specific assumptions about the radio propagation environment.
Our Approach: Key Features
- Simple. A few lines of user-space code, see box opposite.
- Standards compatible. Runs on any standard hardware and does not require any special message-passing or other infrastructure support.
- Supports incremental rollout. No need for “big bang” deployment.
- Fast. Although lightweight and decentralized, our algorithm finds a good channel assignment as quickly as state of the art centralized solvers for graph colouring and k-sat.
- Robust. Suited to complex radio environments.
- Principled. Algorithm is guaranteed to find a good channel assignment, provided one exists.
Learning Algorithm Pseudo-Code
Each AP maintains a state vector p=[p1, …, pc], pi the probability that AP uses channel i.
1. Probe. Randomly select a channel according to vector p. Sense channel quality – result is either (i) success (good channel) or (ii) failure.
(i) If success on channel i, update pi = 1, pj = 0 for j <> I, i.e. stay on the same channel next time.
(ii) If failure, update pj = (1-b)pj+b/c. b is a design parameter, b=0.1 a universal good value.
3. Repeat. Return to 1
Our summer students developed a nice java applet that uses the CFL algorithm to colour a variety of different types of graph.
- A Self-Managed Distributed Channel Selection Algorithm for WLANs
Proc. RAWNET 2006, Boston, MA
- Convergence of Distributed Learning Algorithms for Optimal Wireless Channel Allocation.
Proc. IEEE Conf. on Decision and Control 2006, San Diego
- Optimal WLAN Channel Selection Without Communication
D.J. Leith, P. Clifford, D.Malone, D.Reid
Hamilton Institute Report, July 2006
- Channel Dependent Interference and Decentralized Colouring.
P. Clifford, D. J. Leith
International Conference on Network Control and Optimization, Avignon, 2007.
- Experimental Implementation of Optimal WLAN Channel Selection Without Communication.
Proc. IEEE Dyspan 2007, pp316-319
- Complexity analysis of a decentralised graph colouring algorithm.
K. Duffy, N. O’Connell, A. Sapozhnikov
Information Processing Letters, 2008
- Stochastic Learning Algorithms for Decentralised Channel Allocation in Wireless Networks
Proc. Yale Workshop on Adaptive and Learning Systems, 2008.
- Field Measurements of 802.11 Collision, Noise and Hidden-Node Loss Rates
D.J. Leith, D. Malone
Proc. 6th International workshop on Wireless Network Measurements, 2010
- Decentralised Constraint Satisfaction
IEEE/ACM Trans on Networking, 21(4), pp1298-1308, August 2013
- WLAN Channel Selection Without Communication
Douglas J. Leith, Peter Clifford, Venkataramana Badarla and David Malone
Computer Networks, 56(4), pp1424–1441, March 2012.
- Learning-Based Constraint Satisfaction With Sensing Restrictions
Alessandro Checco, Douglas J. Leith
IEEE Trans Selected Topics in Signal Processing, 7(5), pp 811-820, Oct 2013.