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.

2. Learn.
(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


Java Applet

Our summer students developed a nice java applet that uses the CFL algorithm to colour a variety of different types of graph.


Papers

Links

Hamilton Institute Networking Group