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.

• 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.

Each AP maintains a state vector p=[p₁, …, p_c], p_i 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.

2. Learn.
(i) If success on channel i, update p_i = 1, p_j = 0 for j <> I, i.e. stay on the same channel next time.
(ii) If failure, update p_j = (1-b)p_j+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
  D.J.Leith, P.Clifford
  Proc. RAWNET 2006, Boston, MA
• Convergence of Distributed Learning Algorithms for Optimal Wireless Channel Allocation.
  D.J.Leith, P.Clifford
  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.
  D.Malone,P.Clifford,D.Reid,D.J.Leith
  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
  D.J.Leith
  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
  K.R.Duffy, C.Bordenave,D.J.Leith
  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.

Links

Hamilton Institute Networking Group