
## V. Case Study: Channel Allocation In 802.11 Wlans

Having established general properties of CFL and determined its performance on random instances of k-SAT, we return to a problem of the sort that motivated its introduction. We consider the performance of the CFL algorithm in a realistic wireless network case study. From the online database WIGLE
[35] we obtained the locations of WiFi wireless Access Points
(APs) in an approximately 150m2area at the junction of 5th Avenue and 59th Street in Manhattan1. This space contains 81 APs utilizing the IEEE 802.11 wireless standard. It can be seen from Figure 4, which plots the mean number of APs lying within distance d of an AP, that within a 15m radius an AP has on average 3 neighbours and within a 30m radius it has on average 10 neighbours. Of the 11 channels available in the 802.11 protocol, only 3 are orthogonal. Thus managing interference in this dense deployment is a challenging task.

Imagine a worst-case scenario where after a power-outage all these APs are switched back on. The aim of each AP is to select its radio channel in such a way as to ensure that it is sufficiently different from nearby WLANs. This can be written as a CSP where we have N = 81 APs and N variables xi corresponding to the channel of AP i, i = 1, 2*, ..., N*. As per the 802.11 standard [36] and FCC regulations, each AP can select from one of 11 radio channels in the 2.4GHz band and so the xi, i = 1, 2*, .., N* take values in D = {1, 2*, ..,* 11}.

To avoid excessive interference each AP requires that: (a)
no other AP within a 5m distance operates closer than 3 channels away; (b) no AP within a 10m distance operates closer than 2 channels away and (c) no AP with a 30m distance operates on the same channel. We can realize this as a CSP
with 3 constraint clauses per AP, giving 3N in total, Φm(~x),
m = 1*, ...,* 3N. With e(*i, j*) denoting the Euclidean distance between APs i and j in metres, for m = 1*, ..., N*

$$\Phi_m(\vec{x})=\begin{cases}1&\text{if}\min_{j:e(m,j)<5}|x_m-x_j|\geq3\\ 0&\text{otherwise,}\end{cases}$$ for $m=N+1,...,2N$
$$\Phi_{m}(\vec{x})=\begin{cases}1&\text{if}\min_{j:e(m-N,j)<10}\left|x_{m-N}-x_{j}\right|\geq2\\ 0&\text{otherwise,}\end{cases}$$
and for $ m=2N+1,...,3N$ . 
$$\Phi_{m}(\vec{x})=\begin{cases}1&\text{if}\min_{j:e(m-2N,j)<30}|x_{m-2N}-x_{j}|\geq1\\ 0&\text{otherwise,}\end{cases}$$

The attenuation between adjacent channels is −28dB [36].

Taking the radio path loss with distance as d α, where d is distance in meters and α = 4 the path loss exponent, then these constraints ensure > 60 dB attenuation between APs.

Assuming all APs use the maximum transmit power of 18dBm allowed by the 802.11 standard, this means that the SINR is greater than 20dB within a 10m radius of each AP
which is sufficient to sustain a data rate of 54Mbps when the 1The extracted (x,y,z) coordinate data used is available online at www.

hamilton.ie/net/xyz.txt

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

## Connection Is Line Of Sight And Channel Noise Is Gaussian [36],

[37].

Observe that each variable xiis located at a different AP.

The APs do not belong to a single administrative domain and so security measures such as firewalls prevent communication over the wired network. An AP cannot rely on decoding wireless transmissions to communicate with all of its interferers or even just to identify them. This is because interferers may be too far away to allow their transmissions to be decoded and yet still their aggregate transmission power may be sufficiently powerful to create significant interference.

That is, an AP cannot know the channel selections of other APs, condition (D3) and, moreover, cannot reliably identify or enumerate the clauses in which it participates, condition (D4) . A decentralized algorithm is therefore mandated.

Fig. 5 shows an example satisfying assignment of radio channels obtained by running an instance of the CFL algorithm at all APs. The complexity of the topology generated by the physical location of the APs and the non-uniformity of the clauses it causes is apparent.

Fig. 6 shows the measured distribution of number of itera-