On the Goodness of Using Orthogonal Channels in WLAN IEEE 802.11 in Realistic Scenarios

Abstract

Due to the high density of Wi-Fi networks, especially in the unlicensed 2.4 GHz frequency band, channel assignment has become a critical duty for achieving a satisfactory user experience. Probably, the main peculiarity of Wi-Fi networks is the partial overlap of the radio channels that can be used by access points. For that reason, a number of works avoid cochannel interferences by using only channels which are far enough from each other to have no interferences, the so-called orthogonal channels. However, there is a range of choices between using the whole spectrum and using only orthogonal channels. In this work we evaluate the influence of the choice of channel set in realistic settings, using both optimization and heuristic approaches. Results show that the optimizer is not able to achieve better results when using the whole spectrum instead of restricting to only the orthogonal channels. In fact, the optimizer uses mainly the orthogonal channels when they are available, while the heuristics considered lose performance when more channels are available. We believe this insight will be useful to design new heuristics for Wi-Fi channel assignment.

This work is licensed under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

1. Introduction and State of the Art

Wireless technologies have reached an impressive popularity in the last years. Probably, the most widespread wireless technology is the one based in the standard family IEEE 802.11, commercially known as Wi-Fi. However, the radio spectrum is very limited, and this scarcity is especially important in unlicensed frequency bands, like the ones where Wi-Fi operates in. Moreover, in unlicensed frequency bands, in addition to the Wi-Fi devices we also find other devices that can cause harmful interferences to Wi-Fi, like microwave ovens, Bluetooth devices, or baby monitors. Due to this high saturation and scarcity of the radio spectrum, it is of paramount importance for Wi-Fi devices to choose the adequate channel to operate in, from the set of available channels.

One of the prominent peculiarities of Wi-Fi networks is that the available frequency channels are partially overlapped. For example, in the most popular 2.4 GHz frequency band, from the 13 available channels (depending on the world region this number can be different) only a subset of them do not overlap (orthogonal channels). As the problem of channel assignment in WLAN environments is a current and increasingly important problem, it has been extensively studied by the scientific community. Doubtlessly, the main work that compiles the most prominent efforts in this area is the survey [1]. In this work, WLAN channel assignment techniques are classified into two categories: (i) centrally managed and (ii) uncoordinated. In addition to the papers cited in [1] related to channel assignment, since its publication to the present, some of the most prominent works published in this category are [2–8].

Although the classification provided in [1] is the most logical when studying the problem of Wi-Fi channel assignment, there is an additional dimension which is especially relevant for this work: whether they consider only the orthogonal channels or the whole spectrum of channels. Note that the orthogonal channels are channels 1, 6, and 11 when we have 11 available channels at hand (e.g., in the US) and channels 1, 7, and 13 when we have 13 channels available (e.g., in the EU). The main efforts that consider only the three orthogonal channels are [2, 3, 5, 9–12]. On the other hand, there are many approaches that consider the whole spectrum, like, for example, [13–17]. At this point, one could wonder why there are so many papers that consider only three orthogonal channels. Probably, the first idea could be that solving the problem with three nonoverlapping channels is easier to solve that its counterpart that considers 13 overlapped channels. In addition, using three orthogonal channels is easier to evaluate, especially with simulators, as many of them do not consider overlaps between channels.

On the other hand, some of the works [18–20] studying the effect of using partially overlapped channels draw contradictory conclusions. For example, in [18, 19] authors conclude that using partially overlapped channels in Wi-Fi enables a performance improvement. However, other approaches like [20] consider that the gain of using partially overlapped channels is not guaranteed. We believe the respective biases of those studies are due to the fact that the comparison is done using only a heuristic approach, so the results strongly depend on the heuristic considered.

One of the reasons to use heuristics for these studies is the high complexity of optimal channel assignments in Wi-Fi networks, which is already stated in [1, 21]. Some papers [5, 21] formulate channel assignment as an optimization problem, but due to its NP-hardness, they propose a heuristic algorithm to solve it. From the works cited in the survey [1], only two of them [9, 16] make use of optimization techniques (in particular, they both use Integer Linear Programming).

In this paper we thoroughly study the effect of varying the distance between Wi-Fi channels allowed in assignments, ranging from 1 (using the whole spectrum) to 6 (using only orthogonal channels in a 13 channel spectrum), and we perform this study not only analyzing the usual heuristics, but also optimal assignments obtained via nonlinear optimizers. The main contributions of this paper can be summarized as follows:

(i)

We model the problem of Wi-Fi channel assignment as a multilayer weighted geometric digraph (Section 2.2).

(ii)

We model the goodness of Wi-Fi channel assignments with a nonlinear utility model, which takes into account the saturation effect occurring when signal to interference ratio (SIR) is either very high or very low (Section 2.4).

(iii)

We consider channel assignments obtained by a centralized nonlinear optimizer based on simulated annealing, apart from the usual channel assignment heuristics (Section 3).

(iv)

We propose a set of realistic Wi-Fi scenarios for performance evaluation, constructed from real Wi-Fi maps from University buildings (Section 4.1).

(v)

We study the effect of increasing the number of available channels, either with or without taking into account cochannel interference (Section 4). We also compare the overall gain obtained for the most widespread channel spectrum settings: 11 and 13 channels. We analyze not only the aggregate utility of the solutions, but also the distribution of channels in the assignments.

This is, to the best of our knowledge, the first time that the effect of channel distance and number of channels on the goodness of channel assignments is studied, using optimization techniques and in a realistic setting. Since the publication of [1], the only works (apart from our own [22–24]) that use optimization techniques to solve the channel assignment problem in WLANs are [11, 12]. However, neither of these papers studies the effect of using overlapping channels instead of using nonoverlapping channels. As the papers that have study the possibility of using overlapping channels have contradictory conclusions, we think that this paper fills a gap in the literature, as it tackles the channel assignment as an optimization problem. Moreover, another novelty of the paper consists of considering intermediate cases in the set of available channels that can be assigned to access points, i.e., intermediate situations between using only the three nonoverlapping channels and using all the channels of the spectrum, as we can have more than three channels at hand while avoiding the severe interferences that appear between adjacent channels.

The paper can be structured as follows. In Section 2 we describe the Wi-Fi architecture under consideration, later describing accurately the model we propose for such an architecture. Section 3 is devoted to the description of the optimization and heuristic algorithms used for assigning channels in Wi-Fi settings. The scenarios under study and the results of the paper are shown in Section 4. Finally, Section 5 summarizes the paper and the most important conclusions, proposing some future research lines.

2. Network Model

2.1. Wi-Fi Architecture

IEEE 802.11 technology, commercially known as Wi-Fi, is, without any doubt, the most widespread WLAN technology currently deployed. We focus on Wi-Fi networks operating in infrastructure mode, so there are two types of wireless network elements: access points (APs) and wireless devices (WDs). The goal is to assign a channel to each AP, which will be the channel used for the communication between that AP and its associated WDs. Note that the term WD includes a wide range of devices, such as laptops, smartphones, ebooks, TVs, or any other device able to connect to a Wi-Fi network. In infrastructure mode, direct communication occurs only between WDs and APs, as communications between WDs are not permitted without passing through an AP.

Although the frequency band of 5 GHz is also used in Wi-Fi, we focus on the most used and congested frequency band where Wi-Fi can operate, the unlicensed 2.4 GHz frequency band. This band is composed by 11 to 14 frequency channels where devices can operate. The choice between 11, 13, or 14 channels depends on the world region, with 11 channels used in USA and 13 channels used in Europe. For that reason, we focus on the scenario where we have 13 channels at hand, although in the results we compare the differences of having 11 instead of 13 available channels.

The main peculiarity of the Wi-Fi technology is that those channels partially overlap, which makes the problem of frequency assignment more complex, as each channel may interfere its neighboring channels. A first decision when assigning channels to APs in a Wi-Fi network will be to decide the number of channels to take into consideration. Many of the algorithms and implementations for Wi-Fi channel assignment focus on the use of orthogonal channels only (i.e., channels that do not interfere with each other). This choice has the advantage that there are less harmful interferences.

2.2. Graph Modeling

In this work, we model the Wi-Fi network by means of a multilayer graph [25]. Multilayer graphs have recently emerged as a powerful tool to model and capture multiple related aspects of complex systems. In our model, we consider two layers: connectivity layer and signal layer. Both layers are geometric graphs with two different kinds of vertices: APs and WDs.

The connectivity layer is a geometric undirected graph, where the edges represent the logical links between APs and WDs; i.e., the connectivity layer links each WD to the AP to which it is attached to. As it is expected that a WD attaches to the AP that offers the most powerful signal and we assume that power losses depend on the distance, we have attached each WD to its closest AP.

On the other hand, the signal layer is a geometric weighted directed graph (or weighted digraph), whose edges represent all the signals that are received in each vertex. Note that each edge will have a weight that represents the power signal received. We use a directed graph to account for the higher impact of an interference signal coming from an AP rather than coming from a WD; i.e., we consider that the interference produced from an AP is more harmful than the one produced by a WD. For that reason, we have two edges between each WD and AP vertices which interfere, with different weights for the edge representing the interference from the AP to the WD and the edge representing the interference from the WD to the AP.

In the signal layer two vertices are connected by an edge provided that the distance between them is lower than the coverage area ($CA$), which is defined as the distance at which the power signal has decreased enough to be equal than the sensitivity of the receiver. Section 2.3 defines the propagation and interference models, and describes how to compute $CA$.

Note that in the signal layer we have two types of edges: interferences and the desired signal. Interferences are those undesired received signals that can come from other APs or from WDs that are attached to other APs. Note that two WDs attached to the same AP do not interfere, as these communications are coordinated by that AP. On the other hand, the desired signal is the information signal we want to receive.

A graphical example of the layers of a Wi-Fi scenario with 14 APs and 49 WDs is shown in Figure 1. Figure 1(a) represents the connectivity layer, while Figure 1(b) shows the signal layer, according to the definitions previously provided. For practical purposes, note that in the graphical representation of the undirected graph of the signal layer we join the two edges between vertices (one for each direction) into a single one.

[figures omitted; refer to PDF]

2.3. Propagation and Interference Models

The geometric properties of the multilayer graph allow us consider realistic propagation effects of the radio signals. Our purpose is to assign weights to the edges of the signal layer in such a way that, as mentioned above, each weight represents the power of the signal represented by each edge. First of all, we have to define the propagation model used to represent the power losses that a radio signal suffers from transmission to reception. We have made use of the model proposed in [26], which defines that power loss (in dB) as$$\begin{array}{}\text{(1)}& P_{loss}=\mathrm{40}\hspace{0.17em}{\log }_{\mathrm{10}}d+\mathrm{20}\hspace{0.17em}{\log }_{\mathrm{10}}f-\mathrm{20}\hspace{0.17em}{\log }_{\mathrm{10}}\left(h_t{h}_r\right).\end{array}$$

Equation (1) is defined for situations where transmitting and receiving antennas are close to the ground (between $\mathrm{1}\hspace{0.17em}$m and $\mathrm{2.5}\hspace{0.17em}$m), being $h_t$ and $h_r$ their height above the floor expressed in meters. Note that $d$ represents the distance between the transmitter and the receiver (in meters) and $f$ is the frequency (in GHz) of the signal. As the frequency for the different channels where Wi-Fi operates in is very similar, we have assumed $f$ to be constant and equal to $\mathrm{2.4}\hspace{0.17em}$GHz, obtaining$$\begin{array}{}\text{(2)}& P_{loss}=\mathrm{7.6}+\mathrm{40}\hspace{0.17em}{\log }_{\mathrm{10}}d-\mathrm{20}\hspace{0.17em}{\log }_{\mathrm{10}}\left(h_t{h}_r\right).\end{array}$$

As we want to assign the weights to each edge of the signal layer, we are going to identify two different cases: (i) the signal is the one we want to receive, i.e., it contains the desired information, and (ii) the signal is undesired, i.e., it is an interference.

As the Wi-Fi network is operating in infrastructure mode, the desired signal is produced always between a WD and the AP to which the WD is attached to and vice versa. The weight of the edges that represent the desired signal between vertices $i$ and $j$ ($V_i$ and $V_j$) can be computed as$$\begin{array}{}\text{(3)}& S_{V_i\to V_j}=P_t+G_t+G_r-L-P_{loss},\end{array}$$where $P_t$ stands for the transmitting power, expressed in dBm, $G_t$ and $G_r$ stand for the transmission and reception antennas gains, respectively, $L$ stands for losses due to obstacles, like walls, windows, and so on, and is expressed in dB, and ${\mathrm{P}}_{loss}$ is computed with (2).

To compute the weight of the edges representing interferences in the signal layer (between $V_i$ and $V_j$) we use$$\begin{array}{}\text{(4)}& I_{V_i\to V_j}=P_t+G_t+G_r-L-P_{loss}+\Psi +\eta \left(\left|c_i-c_j\right|\right),\end{array}$$where every value is expressed in logarithmic scale. It is important to define parameters $\Psi$ and, specially, $\eta (|c_i-c_j|)$. First, we can define $\Psi$ as the activity index that represents the aforementioned more harmful effect of the interferences produced by APs ($\Psi =\mathrm{0.5}$) rather than produced by WDs ($\Psi =\mathrm{0.2}$). Second, the $\eta$ function represents the cochannel interference, so it is a paramount parameter for the purpose of this work. We have considered the effect of partially overlapped channels, represented by this function $\eta$, empirically measured in [27], although the results are not very different from those obtained in other works [18, 28, 29]. More specifically, $\eta (|c_i-c_j|)$ represents the cochannel interference between vertices $i$ and $j$ when they are assigned channels $c_i$ and $c_j$, respectively. Table 1 shows the cochannel interference defined in [27] and used in this work. As we can see, the overlap between channels decreases as they are farther apart in the spectrum.

Table 1

Spectral overlap between Wi-Fi channels [27].

$|c_i-c_j|$	0	1	2	3	4	5	6	...
Spectral overlap	1	0.8	0.5	0.2	0.1	0.001	0	0

Finally, once the interferences have been defined, we can define how we have computed the coverage area ($CA$) defined in Section 2.2. As we stated, $CA$ represents the distance at which the power signal transmitted by a device is equal to the sensitivity of the receivers ($\sigma$). From the definitions above this $CA$ can be easily computed as$$\begin{array}{}\text{(5)}& CA=\mathrm{1}{\mathrm{0}}^{\left(P_t+G_t+G_r-L-\sigma -\mathrm{7.6}+\mathrm{20}\hspace{0.17em}{\log }_{\mathrm{10}}\left(h_t{h}_r\right)\right)/\mathrm{40}}.\end{array}$$

2.4. Utility of the Solutions

To measure the goodness of a particular channel assignment we use the signal to interference ratio ($SIR$). As the edges of the signal layer include the power of the different signals that appear in the network, $SIR$ can be directly computed from that layer.

The computation of the $SIR$ is slightly different depending on whether the $SIR$ is being computed for a WD or an AP, so we distinguish both cases. For the $i$-th WD (vertex $V_i$ in the graph), that is attached to $j$-th AP (vertex $V_j$ in the graph), $SIR$ can be computed as the quotient between the weight of the edge of the desired signal and the sum of the weights of the edges representing interferences (denoted by subindex $k$); i.e.$$\begin{array}{}\text{(6)}& SI{R}_i=\frac{S_{V_j\to V_i}}{{\sum }_k{I}_{V_k\to V_i}}.\end{array}$$

We have distinguished the $SIR$ value for WDs and for APs as, for APs, we have so many desired signals ($S_{V_j\to V_i}$) as WDs it has attached that AP. In that case, we have chosen the worst case; i.e., for the desired signal we have chosen the one that is received with less power, resulting in the $SIR$ that is minimum for every WD.

Although the SIR represents a good performance parameter to evaluate channel assignments, it can be improved to represent a more realistic situation. As we know, user experience depends on the $SIR$, but this experience has upper and lower bounds, as shown in [30]. If $SIR$ value for a certain device is below a certain value ($SI{R}_{min}$), the signal quality is very poor and devices cannot keep connected and, thus, throughput (and hence perceived utility) equals to zero. On the other hand, when $SIR$ is above a certain value $SI{R}_{max}$ the throughput is limited by the technology, so it has no impact to increase the $SIR$ beyond that value. For those reasons we introduce, as a performance parameter, the utility for device $i$, named $U_i$. Parameter $U_i$ ranges from 0 to 1, representing 0 the situation where the $SIR$ is below $SI{R}_{min}$ and 1 when $SIR$ is above $SI{R}_{max}$. For the values between $SI{R}_{min}$ and $SI{R}_{max}$ we have used a linear function, as shown in Figure 2.

[figure omitted; refer to PDF]

Finally, the utility for a certain channel assignment can be computed as the sum of the utilities for all the vertices in the graph:$$\begin{array}{}\text{(7)}& U={\displaystyle \sum }_{\forall i}{U}_i.\end{array}$$

3. Channel Assignment Approaches Used in the Comparison

In our study, according to the classification in the aforementioned survey [1], we have chosen for benchmarking both a centralized and a distributed approach. We have also made experiments with random assignments, to use them as a baseline. In the following we briefly describe the three channel assignment techniques used in the study.

3.1. Baseline: Random Channel Assignment

As a reference, we have used random channel assignments; that is, we have measured the utility values obtained when choosing a random channel for each AP, using a uniform distribution. This gives us a baseline to compare with other approaches, and to have a better view of whether they achieve a reasonably good solution or not. As we will discuss in Section 4, this also gives us an indication of how the search problem becomes harder as the number of available channels change.

3.2. Least Congested Channel Search (LCCS)

Distributed heuristics are the de facto standard for Wi-Fi-channel assignment. In particular, Least Congested Channel Search (LCCS) [31] works by letting each access point to choose its desired channel autonomously. In order to do so, access points periodically count the number of active wireless devices at each channel, choosing the least used channel for operation. Since LCCS is asynchronous by definition and its convergence is not guaranteed, it is difficult to define a final assignment to use for comparison. To overcome this difficulty, we have implemented a LCCS hill-climber, which means that we conduct a number of iterations, allowing the LCCS algorithm to run asynchronously once for each of the APs (with the ordering of the APs randomly changing) at each iteration. If, at the end of the iteration, the overall utility has increased, we keep the changes. Otherwise, we revert the channel assignments before iterating again. We have set the number of iterations to 3000 in our setting.

3.3. Optimization Using Simulated Annealing (SA)

Simulated annealing is a centralized nonlinear optimization technique [32], which we have used successfully in the past in frequency assignment problems [22]. The idea of simulated annealing is to search through the solution space at each iteration of the algorithm by evaluating some neighboring solutions to the current state, and deciding whether to move to one of these neighboring solutions with a finite probability, which depends on the utility variation of the movement (the greater the utility loss, the less likely to move) and a parameter called annealing temperature, with higher probability of moving when the temperature is high. The temperature is progressively decreasing as the algorithm progresses, guaranteeing its convergence. In this study we used an implementation of SA similar to the one used in [22], with only one neighboring solution evaluated at each iteration (generated by randomly changing the channel assigned to a randomly chosen AP), and by using $P_a=e^{-\Delta u/T}$ as the probability of movement, where $\Delta u$ is the utility loss for the movement and the temperature $T$ starts at 1 and decreases linearly down to zero as the algorithm iterates. We have used the same number of iterations for SA as the one set for LCCS.

4. Numerical Study

4.1. Scenarios under Study and Parameters Used

We have made use of realistic settings to evaluate the effect of the use of orthogonal channels in Wi-Fi technology. In particular, we have considered the real layout of the Wi-Fi campus network from the Science Building of the University of Burgos (Spain), which we show as a heat map representation in Figure 3. With this layout, we have considered a wide range of situations increasing the density of WDs. More specifically, we have considered scenarios with 50, 100, 150, 200, 250 and 300 WDs. This choice originates very different situations regarding interferences, as it can be seen in Figure 4, where we show the graph models for some of these scenarios, including the simplest (with 50 WDs) and the most complex (with 300 WDs). In this figure, we have merged the two layers of the graph model, showing APs as green circles and WDs as smaller black squares. Moreover, the edges of the signal layer are depicted with solid red lines and the edges of the connectivity layer with black dashed lines.

[figure omitted; refer to PDF]

[figures omitted; refer to PDF]

As mentioned before, our goal will be to assign the frequency channels to the different devices in the network in order to maximize the experience perceived by network users, i.e., in order to maximize the utility function $U$ defined in Section 2.4. Typically, channel assignment can be recognized as a graph coloring problem [33], so an example of the result of applying any of the channel assignment algorithms can be shown in Figure 5, where we have represented each of the 13 Wi-Fi channels by a color.

[figure omitted; refer to PDF]

As there are many parameters that define the models proposed in Section 2, we summarize the parameters used in Table 2, as defined in [22].

Table 2

Summary of parameters.

Parameter	Value
$P_t$	$\mathrm{30}$ mW
$G_t$	$\mathrm{0}$ dB
$G_r$	$\mathrm{0}$ dB
$L$	$\mathrm{40}$ dB
$\sigma$	$-\mathrm{90}$ dBm
$h_t$	$\mathrm{1.5}$ m
$h_r$	$\mathrm{1.5}$ m
$\Psi$ (APs)	0.5
$\Psi$ (WDs)	0.2
$SI{R}_{min}$	10 dB
$SI{R}_{max}$	40 dB

4.2. Effect of the Number of Channels

In this section we evaluate the impact of considering the use of only orthogonal channels, in comparison with the use of a wider number of channels up to a maximum of 13 channels. In all cases we have considered evenly spaced possibilities. For that reason, the number of channels used in each case, together with the specific channels considered for each setting, is as shown in Table 3. Note that we have considered all the possibilities that produce evenly spaced channels.

Table 3

Number of channels and channels in use.

Number of channels	Separation	Channels in use
3	6	1, 7, 13
4	4	1, 5, 9, 13
5	3	1, 4, 7, 10, 13
7	2	1, 3, 5, 7, 9, 11, 13
13	1	1-13

4.2.1. Without Cochannel Interference

First of all, we evaluate the effect of the number of channels assuming there are no cochannel interferences, i.e., assuming that all the available 13 channels are orthogonal. Although this situation is not realistic, this experiment is performed to analyze the effect that cochannel interference has on performance, because all the subsequent experiments consider such an interference. In addition, this first experiment lets us validate the model and analyze the effect of the number of channels if cochannel interferences could be avoided.

In this setting, the cochannel interference is 1 for $c_i=c_j$ and 0 otherwise. Results are shown in Figure 6. This figure shows the mean and 95% confidence intervals (showed with the shaded area) obtained as a result of 100 random assignments, and for the different number of WDs under study. Comparing the different curves, we conclude that, as the number of WDs increases, the utility also increases. This is an expected result, as there are more devices to account for the utility when the number of WDs increases. Another identified pattern, also expected, is that the obtained utility increases as we can make use of more channels. This makes sense, since the availability of new channels reduces the amount of “monochromatic edges”, that is, adjacent vertices in the signal layer using the same channel, so interference reduces drastically. In the limit, if we had as many available channels as APs, interference would be zero and utility would be maximized.

[figure omitted; refer to PDF]

4.2.2. With Cochannel Interference

In spite of the results shown in the previous section, it is of paramount importance to consider the cochannel interference, as it is probably the most peculiar feature of Wi-Fi networks. As stated above, for the cochannel interference we have used the data obtained in [27].

Now we evaluate the effect that considering orthogonal channels has in performance, in comparison with using an increasing number of evenly spaced channels. This experiment has been driven for different scenarios and using different algorithms to assign channels. The behavior is shown in Figure 7, where we also show the confidence intervals at 95%. To make confidence intervals narrow enough for the the results to be statistically significant, we have run the LCCS and random channel assignment approaches 1000 times, while the SA optimizer has been run for 50 times (the standard deviation for the SA results is much lower). It is very remarkable the local minimum that appears at every curve when we have 4 channels at hand. This effect is due to the fact that the experiments that consider 4 channels are the only ones that cannot use channel 7, and, as we will see later, channel 7 is one of the most widely used in optimal assignments. In particular, having 4 channels available permits us to use channels 5 and 9, which are not orthogonal either to each other or to channels 1 and 13, respectively. However, results show that it is better to use those new channels (and hence enduring the associated interferences) than to avoid them (therefore having only the two channels 1 and 13, which are orthogonal, but being forced to have a number of high-interference monochromatic edges).

[figures omitted; refer to PDF]

However, the main conclusion from Figure 7 is that, when we increase the number of available channels and consider cochannel interference, the utility achieved does not increase. This result is counterintuitive, and it probably justifies the wide number of research studies that only consider three orthogonal channels in Wi-Fi. In fact, following Figure 7 we could recommend not to use more than 3 channels, as the complexity of the problem increases with no gain in performance, probably because the network layout can be efficiently covered with three colors or, for the scenarios under study, because the AP placement has been done considering that only the orthogonal channels were to be used. In particular, we notice that the optimizer SA is not able to obtain higher gains in utility when it can use a higher number of channels. In addition, it must be noted that the problem complexity of using 13 channels is much higher than considering 3, as the state space of possible solutions increases from $3^N$ to ${13}^N$, where $N$ is the number of APs in the network.

If we compare the performance of the different techniques under evaluation (Figure 7), we notice that random is the worst technique, followed by LCCS. As it could be expected, SA offers the best results. In fact, as SA is an optimizer, we could consider that the results obtained by SA can be considered as upper bounds in performance. As SA requires the complete information about the network, we do not present SA as a realistic technique to be easily used in real networks (it could only be used when we use a central controller). For that reason, comparing the performance of Random and LCCS with SA we can estimate the room for improvement that widely used techniques have. Moreover, it is very important to note that, analyzing the utility achieved by Random and LCCS as the number of available channels increase, this utility decreases. This conclusion is very important, as it can be deduced that when using random or LCCS assignments, it is worth to use 3 nonoverlapping channels, because not choosing the channel correctly can generate more undesired interferences.

In addition to the previous comparison, we now inspect the channels used by the different techniques and for the different deployments. First, and for the sake of space, it is important to note that we focus on the scenario with 200 WDs as a reference, but identical conclusions can be drawn from the rest of scenarios. On one hand, Figure 8 shows the proportion of colors actually used in the channel assignments obtained by the optimizer for the different number of available colors. When we use 3 channels, we note that they are used evenly, as they do not interfere with each other at all. However, when 4 channels are available, we note that channels 5 and 9 are less used than 1 and 13, so the conclusions given before about the utility achieved when having 4 channels are confirmed. Finally, it is worth to note that when we have 5 and 7 channels available, the optimizer only uses the three orthogonal channels (1, 7, and 13), being the use of other channels negligible. A similar conclusion can be given when we have 13 available channels, although the use of other channels different than 1, 7 and 13 is a bit higher.

[figure omitted; refer to PDF]

On the other hand, Figure 9 is the equivalent but for LCCS. In this case, we can notice that LCCS makes use of more channels than the three orthogonal ones, but the most widely used are channels 1 and 13.

[figure omitted; refer to PDF]

4.3. Comparison between the Use of 11 and 13 Channels

As it has been previously shown, increasing the number of channels does not increase the performance, when we consider cochannel interference. For that reason, now we conduct a study comparing the performance that can be achieved when using 11 or 13 channels. Although the choice of having 11 or 13 channels at hand depends on the world region and cannot be chosen individually, following the results of the previous section, it is worth to evaluate the differences that both possibilities have. The main results are summarized in Figure 10, where we show the quotient between the utility achieved when letting the use of 13 channels and 11 channels. Results show that, for all the assignment algorithms under study, the performance of having 13 channels at hand is about 15%-25% better than having only 11 channels. This effect is due to the fact that, although the best choice is to use a reduced number of channels, those channels are more spaced when using 13 channels.

[figure omitted; refer to PDF]

5. Conclusions

Channel assignment is probably the most important configuration issue when deploying Wi-Fi networks. As there is an increasing number of Wi-Fi networks, together with other devices like microwaves, baby monitors, and so on sharing the same spectrum, we must accurately choose in which frequency channel must operate each access point. This frequency planning problem becomes more complex as one of the most peculiarities of Wi-Fi networks is that frequency channels partially overlap between them, raising the problem of cochannel interference. Many works devoted to channel assignment in Wi-Fi networks avoid the use of overlapped channels by using a reduced number of noncolliding channels, called orthogonal channels. In this paper we evaluate the goodness of using only the orthogonal channels instead of a higher number of overlapping channels up to the maximum number of channels available. Moreover, we evaluate our proposal in realistic settings. Although we also consider some usual heuristic channel assignments algorithms, we also use an optimization algorithm based on the simulated annealing technique. Due to its complexity, the Wi-Fi channel assignment problem has been very scarcely addressed as an optimization procedure, being most of the proposals heuristic approaches.

The first study performed in the paper is related to the impact of the number of channels available when we do not consider the cochannel interference. Although this situation is unrealistic, it is included in order to compare its results to the situations where we consider cochannel interference. Results show that, increasing the number of nonoverlapping channels, we improve performance as we have more opportunities to choose a channel that avoids interferences with the channels used in other access points.

Secondly and introducing cochannel interference, we have also studied the effect of the number of channels available. In this comparison we have first determined that the best performance is obtained by the optimizer based on simulated annealing, followed by the heuristic LCCS and, finally, the random assignment, which is useful mainly as a baseline. Furthermore, we conclude that the optimizer is not able to achieve better channel assignments when it is permitted to use more channels than just the orthogonal ones. In fact, it is shown that the algorithm mainly uses the three orthogonal channels even when it is allowed to use the whole spectrum. It is particularly significant the fact that LCCS (the de facto standard for Wi-Fi channel assignment) degrades as more channels are available to choose, probably due to the fact that local interference evaluation avoids channel choices which would be necessary for the globally optimal solutions (we could talk of “sacrificing local utility for the global welfare”). This leads us to think that better heuristics could be designed taking into account the aggregation of utilities further than at the access point level (e.g., considering clusters of APs). The design of such heuristics and the study of the conditions in which they succeed will be the scope of our most immediate future work. Finally, we would like to introduce dynamicity in our model, to see how the different approaches react to changes during and after convergence and the utility loss associated with the cost of (re)convergence.

Conflicts of Interest

The authors declare that they have no conflicts of interest.

Acknowledgments

This work has been supported by the Spanish Ministry of Economy, Industry and Competitiveness Grants TIN2016-80622-P (AEI/FEDER, UE). David Orden has been partially supported by MINECO Project MTM2014-54207, Spanish Ministry of Science Project MTM2017-83750-P (AEI/FEDER, UE), and European Union H2020-MSCA-RISE Project 734922-CONNECT. Authors would like to thank the University of Burgos for granting them access to the wireless infrastructure layout and heat map used in the paper.

References

[1] S. Chieochan, E. Hossain, J. Diamond, "Channel assignment schemes for infrastructure-based 802.11 WLANs: a survey," IEEE Communications Surveys & Tutorials, vol. 12 no. 1, pp. 124-136, DOI: 10.1109/surv.2010.020110.00047, 2010.

[2] M. Drieberg, F.-C. Zheng, R. Ahmad, "MICPA: A client-assisted channel assignment scheme for throughput enhancement in WLANs," IEEE Transactions on Vehicular Technology, vol. 60 no. 9, pp. 4497-4508, DOI: 10.1109/TVT.2011.2171199, 2011.

[3] X. Yue, C.-F. Wong, S.-H. G. Chan, "CACAO: Distributed client-assisted channel assignment optimization for uncoordinated WLANs," IEEE Transactions on Parallel and Distributed Systems, vol. 22 no. 9, pp. 1433-1440, DOI: 10.1109/TPDS.2011.59, 2011.

[4] D. J. Leith, P. Clifford, V. Badarla, D. Malone, "WLAN channel selection without communication," Computer Networks, vol. 56 no. 4, pp. 1424-1441, DOI: 10.1016/j.comnet.2011.12.015, 2012.

[5] D. Gong, M. Zhao, Y. Yang, "Channel assignment in multi-rate 802.11n WLANs," pp. 392-397, DOI: 10.1109/WCNC.2013.6554596, .

[6] A. Bhartia, D. Chakrabarty, K. Chintalapudi, L. Qiu, B. Radunovic, R. Ramjee, "IQ-hopping: Distributed oblivious channel selection for Wireless Networks," Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 81-90, .

[7] Y. M. Kwon, K. Choi, M. Kim, M. Y. Chung, "Distributed channel selection scheme based on the number of interfering stations in WLAN," Ad Hoc Networks, vol. 39, pp. 45-55, DOI: 10.1016/j.adhoc.2015.12.005, 2015.

[8] H. Kasasbeh, F. Wang, L. Cao, R. Viswanathan, "Generous throughput oriented channel assignment for infra-structured WiFi networks," Proceedings of the 2017 IEEE Wireless Communications and Networking Conference, WCNC 2017, .

[9] Y. Lee, K. Kim, Y. Choi, "Optimization of AP placement and channel assignment in wireless LANs," Proceedings of the 27th Annual IEEE Conference on Local Computer Networks, LCN 2002, pp. 831-836, .

[10] J. K. Chen, G. De Veciana, T. S. Rappaport, "Improved measurement-based frequency allocation algorithms for wireless networks," Proceedings of the 50th Annual IEEE Global Telecommunications Conference, GLOBECOM 2007, pp. 4790-4795, .

[11] M. Elwekeil, M. Alghoniemy, M. El-Khamy, H. Furukawa, O. Muta, "Optimal channel assignment for IEEE 802.11 Multi-cell WLANs," Proceedings of the 20th European Signal Processing Conference, EUSIPCO 2012, pp. 694-698, .

[12] M. Seyedebrahimi, F. Bouhafs, A. Raschella, M. MacKay, Q. Shi, "SDN-based channel assignment algorithm for interference management in dense Wi-Fi networks," Proceedings of the 2016 European Conference on Networks and Communications, EUCNC 2016, pp. 128-132, .

[13] P. Mahonen, J. Riihijarvi, M. Petrova, "Automatic channel allocation for small wireless local area networks using graph colouring algorithm approach," Proceedings of the 2004 IEEE 15th International Symposium on Personal, Indoor and Mobile Radio Communications, pp. 536-539, DOI: 10.1109/PIMRC.2004.1370928, .

[14] A. Mishra, S. Banerjee, W. Arbaugh, "Weighted coloring based channel assignment for WLANs," ACM SIGMOBILE Mobile Computing and Communications Review, vol. 9 no. 3, pp. 19-31, DOI: 10.1145/1094549.1094554, 2005.

[15] A. Mishra, V. Brik, S. Banerjee, A. Srinivasan, W. Arbaugh, "A client-driven approach for channel management in wireless LANs," Proceedings of the INFOCOM 2006: 25th IEEE International Conference on Computer Communications, .

[16] M. Haidar, R. Akl, H. Al-Rizzo, Y. Chan, "Channel assignment and load distribution in a power-managed WLAN," Proceedings of the 18th Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, PIMRC'07, .

[17] R. Akl, A. Arepally, "Dynamic Channel Assignment in IEEE 802.11 Networks," Proceedings of the 1st IEEE International Conference on Portable Information Devices, (PIDs '07), .

[18] J. Wang, W. Shi, K. Cui, F. Jin, Y. Li, "Partially overlapped channel assignment for multi-channel multi-radio wireless mesh networks," EURASIP Journal on Wireless Communications and Networking, vol. 2015 no. 1, 2015.

[19] M. Abusubaih, "Using Partially Overlapping Channels in Home 802.11g WLANs," Wireless Personal Communications, vol. 88 no. 2, pp. 295-303, DOI: 10.1007/s11277-015-3114-7, 2016.

[20] M. Doering, L. Budzisz, D. Willkomm, A. Wolisz, "About the practicality of using partially overlapping channels in IEEE 802.11 b/g networks," Proceedings of the 2013 IEEE International Conference on Communications, ICC 2013, pp. 5110-5114, .

[21] Y. Cui, W. Li, X. Cheng, "Partially overlapping channel assignment based on “node orthogonality” for 802.11 wireless networks," Proceedings of the IEEE INFOCOM 2011, pp. 361-365, DOI: 10.1109/INFCOM.2011.5935182, .

[22] E. De La Hoz, J. M. Gimenez-Guzman, I. Marsa-Maestre, D. Orden, "Automated negotiation for resource assignment in wireless surveillance sensor networks," Sensors, vol. 15 no. 11, pp. 29547-29568, DOI: 10.3390/s151129547, 2015.

[23] E. De La, I. Hoz, J. M. Gimenez-Guzman, D. Orden, M. Klein, "Multi-agent nonlinear negotiation for Wi-Fi channel assignment," Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, pp. 1035-1043, .

[24] D. Orden, J. Gimenez-Guzman, I. Marsa-Maestre, E. de la Hoz, "Spectrum Graph Coloring and Applications to Wi-Fi Channel Assignment," Symmetry, vol. 10 no. 3,DOI: 10.3390/sym10030065, 2018.

[25] M. Kivelä, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno, M. A. Porter, "Multilayer networks," Journal of Complex Networks, vol. 2 no. 3, pp. 203-271, DOI: 10.1093/comnet/cnu016, 2014.

[26] D. B. Green, M. S. Obaidat, "An accurate line of sight propagation performance model for Ad-Hoc 802.11 wireless LAN (WLAN) devices," IEEE International Conference on Communications, vol. 5, pp. 3424-3428, 2002.

[27] K. R. Chowdhury, I. F. Akyildiz, "Cognitive Wireless Mesh Networks with dynamic spectrum access," IEEE Journal on Selected Areas in Communications, vol. 26 no. 1, pp. 168-181, DOI: 10.1109/JSAC.2008.080115, 2008.

[28] A. Mishra, V. Shrivastava, S. Banerjee, W. Arbaugh, "Partially overlapped channels not considered harmful," ACM SIGMETRICS Performance Evaluation Review, vol. 34 no. 1, pp. 63-74, DOI: 10.1145/1140103.1140286, 2006.

[29] V. Shrivastava, S. Rayanchu, J. Yoon, S. Banerjee, "802.11n under the microscope," Proceedings of the Internet Measurement Conference 2008, IMC'08, pp. 105-110, .

[30] A. Bazzi, "On uncoordinated multi user multi RAT combining," .

[31] M. Achanta, "Method and apparatus for least congested channel scan for wireless access points," uS Patent App. 10/959, 2006.

[32] T. Ito, M. Klein, H. Hattori, "A multi-issue negotiation protocol among agents with nonlinear utility functions," Multiagent and Grid Systems, vol. 4 no. 1, pp. 67-83, DOI: 10.3233/MGS-2008-4105, 2008.

[33] J. L. Gross, J. Yellen, P. Zhang, Handbook of Graph Theory, 2013.