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

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.