A Cluster-Based Channel Assignment Technique in IEEE 802.11 Networks

Abstract

Channel assignment has become a critical configuration task in Wi-Fi networks due to the increasing number and density of devices which use the same frequency band in the radioelectric spectrum. There have been a number of research efforts that propose how to assign channels to the access points of Wi-Fi networks. However, most of them ignore the effect of clients (also called stations or STAs) in channel assignment, instead focusing only on access points (APs). In this paper, we claim that considering STAs in the channel assignment procedure yields better solutions in comparison with those obtained when STAs are ignored. To evaluate this hypothesis we have proposed a heuristic technique that includes the effect of interferences produced by STAs. Results show that taking STAs into account clearly improves the performance of the solutions both in terms of the achieved utility and in terms of the variability of results. We believe that these results will be useful to the design of future channel assignment techniques which consider the effect of STAs.

1. Introduction

Wireless networks are arguably the key pieces of technology that have let customers make ubiquitous use of communication networks. In fact, the way that our society uses communication networks could not be understood without wireless techologies. In addition to cellular networks, the most popular and widespread wireless technology is the one based on the family of IEEE 802.11 standards, commercially known as Wi-Fi. Such networks are everywhere, and it is usual to find a high number of Wi-Fi networks coexisting in the same area. However, as Wi-Fi networks share the limited unlicensed wireless spectrum (along with other wireless technologies such as Bluetooth), we must optimize their design and configuration. One of the most significant configuration parameters in Wi-Fi networks is the frequency channel where each access point (AP) operates, chosen from the available set of channels. This choice is important, because if we choose a channel with high interference from other APs, stations (STAs) or even from other wireless techologies, quality of service perceived by customers will be poor. On the other hand, if we make an intelligent channel distribution for the different APs, customers will get the best performance from their Wi-Fi networks.

As channel assignment is a prominent problem, the research community has studied it thoroughly. The main survey that has compiled the main efforts in this topic is [1]. However, since this compilation there have been a number of contributions, such as [2,3,4,5,6,7,8]. Channel assignment techniques can be classified as centralized or distributed. Although the techniques in both categories have the same purpose, in some scenarios only techniques from one category can be used. For example, if the setting under study is a corporate Wi-Fi network, we can resort to centralized techniques that can use optimization procedures to assign channels to APs, so that optimal results are achieved. However, if our setting is a residential area where APs are managed by customers, and therefore, are independent, we cannot use a centralized approach, and we must resort to distributed techniques usually based on heuristics. In fact, although there have been some efforts related to optimization approaches [9,10,11,12,13,14,15,16], most of the studies for channel assignment in Wi-Fi propose heuristic techniques.

Some of the most interesting approaches based on heuristic techniques for channel assignment in IEEE 802.11 networks are briefly reviewed next. In [17], the authors propose an iterative procedure to assign channels to APs, ordering them depending on saturation degree (DSATUR), i.e., depending on the number of APs that can interfere and that have been already assigned respective channels. In [18] the problem of channel assignment is formalized as the minimization of interferences, and then, due to the high complexity of the formalized problem, the authors propose MICA (minimum interference for channel allocation) as an approximated, heuristic algorithm. In [2], the authors propose Uminmax-sum as an evolution and improvement of the works [19,20]. Basically, to choose a channel for a certain AP, they try to avoid harming the utilization of other APs, especially the bottleneck APs. In [21], the authors propose cluster-based channel assignment (CCA), a technique based on measuring the interference from APs by partitioning the network into sets that interfere. The main contribution of [22] was to show the implementation of the algorithm described in [23], which is a weighted extension of the well-known DSATUR algorithm, considering overlapping channels. Moreover, although that paper does not consider STAs in the resulting graph that models the Wi-Fi network setting, it partially considers its effect by connecting APs that, although they cannot receive interference from each other, have an STA in their shared transmission range. On the other hand, [24,25] considered STAs directly as part of the model. In [24], the authors propose a channel assignment technique together with a load balancing proposal, and in [25] three different algorithms are proposed to assign channels to APs considering only the three orthogonal (non-overlapping) channels.

Two other very interesting channel assignment techniques are [7,26]. In [7], the authors propose a channel assignment technique based on choosing the channel with the least interference by using the Wi-Fi control frames. In [26] a channel assignment is proposed which attempts to avoid the same channel in neighboring APs while trying to use the least number of possible channels.

Finally, in [27], the authors propose a technique, which we have called AIIM according to its authors’ initials, to improve the performance of the AP that has the lowest performance without compromising the global performance and iterating this procedure. This is the approach we have taken as a basis for this paper, showing that enhancing AIIM with a cluster-based approach (we have called it CB-AIMM) can significantly improve the resulting channel assignments.

Table 1. Summary of channel assignment techniques in Wi-Fi.

Reference	Centralized	Distributed	Heuristic	Optimization	STAs
[2]	X		X
[3]		X	X		X
[4]		X	X
[5]		X	X		X
[6]		X	X
[7]		X	X		X
[8]		X	X		X
[9]	X			X
[10]		X		X
[11]	X			X	X
[12]	X			X	X
[13]	X			X	X
[14]	X	X		X	X
[15]	X			X	X
[16]	X			X	X
[17]		X	X
[18]	X		X
[19]		X	X
[20]	X		X
[21]	X		X
[22]	X		X		X
[23]	X	X	X		X
[24]	X		X		X
[25]	X		X		X
[26]	X		X
[27]	X		X
CB-AIIM	X		X		X

shows a summary of all the abovementioned channel assignment techniques, showing where they fall in the aforementioned categories (i.e., centralized vs. distributed and heuristic vs. optimal). Moreover, we also show whether the techniques make use of the STAs or not.

The main contribution of this paper is to show that the effect of STAs in a channel assignment technique is not negligible. To show this behavior, we propose a heuristic channel assignment technique called CB-AIIM (cluster-based AIIM) that extends the proposal in [27] by including STAs, and show in the results that the performance greatly increases.

The structure of the paper is as follows. Section 2 defines the Wi-Fi architecture used in the rest of the paper and defines the multilayer graph model we propose, including the propagation and interference models and the definition of the utility concept to evaluate the performance of the results. Section 3 describes the channel assignment technique proposed in this work, called CB-AIIM. Finally, Section 4 describes the evaluation scenarios and shows the results by comparing CB-AIIM with other proposals from the literature. Finally, Section 5 summarizes our contribution and sheds light on some future work.

2. Network Model

2.1. Wi-Fi Architecture

The most common technology with which to deploy wireless local area networks (WLAN) is, without any doubt, based on the family protocols IEEE 802.11, commercially known as Wi-Fi. In this work, we focus our attention in the most widely deployed Wi-Fi operating mode, called infrastructure mode. Under this mode, there two different types of wireless devices: stations (STAs), which are the final devices that make use of the network, and access points (APs), which connect STAs to the rest of the network (wired and/or wireless). For that reason, each STA will be wirelessly associated with a single AP to be able to communicate with the rest of the network. The generic term STA can represent a wide range of wireless devices—smartphones, tablets, laptops, TVs, etc. It is important to highlight that in infrastructure mode, direct communications occurs only between STAs and APs. Direct communication between STAs is not permitted, as those communcations must go through at least one AP. This is the general environment which frames our research, and our focus will be to assign a channel to each AP in the network, as the STAs will use the same channel that is chosen for their associated AP.

In this work, without loss of generality, we focus our attention on the 2.4 GHz frequency band, as it is the most congested one and it is very widely used not only in Wi-Fi 4, but also in the recent Wi-Fi 6, so its future use is guaranteed. It is important to note that, as the frequency bands where Wi-Fi can operate are unlicensed, the interferences in some channels can be unacceptable, which makes proper channel assignment even more necessary. The 2.4 GHz frequency band has from 11 to 14 frequency channels that APs can choose. The choice between 11, 13 or 14 will depend on the region of the world we are in. For example, in Europe there are 13 channels available but in the USA there are only 11. In this work we use the most restrictive choice of having only 11 available channels at hand. Although the set of channels that can be chosen is 11, the main peculiarity of IEEE 802.11 networks is that those channels are partially overlapped. However, as the use of the three non-overlapping channels is commonly accepted and widely deployed, in this paper we focus on those channels only. In an 11-channel setting, only channels 1, 6 and 11 are used, so that only APs operating in the same channel will interfere.

2.2. Connectivity and Interferences Models Using Graphs

Our models are based in the so-called multilayer graphs [28], which have recently emerged as a versatile tool with which to capture a high number of features of real situations into a single (multilayered) graph. Our multilayer graph is composed by two layers, being both geometric. Moreover, in both layers we have two different types of vertices, which are the two types of wireless devices that appear in Wi-Fi networks when operating in infrastructure mode: STAs and APs. Next, we provide a brief description of both layers. For a more in-depth description, please see [29,30].

The first one, called the connectivity layer, represents the connectivity between STAs and APs, so it represents the attachment between each STA and its associated AP. We have considered that each STA is associated with its closest AP (if it is in its coverage area that is defined by the sensitivity of the receiving antennas), as it is usually the AP with the maximum receiving power. In this case, edges are undirected because they represent the attachment between STAs and APs, which is bidirectional. The second layer, called the interference layer, includes all the possible interferences that a wireless device produces regarding other wireless devices. In other words, there is an edge between two vertices A and B provided that A produces interferences affecting B. In this case we consider a geometric weighted directed layer (or weighted digraph). It is a weighted graph because the weight of each edge represents the power of the interference signal. Moreover, it is directed as we consider that interferences received from APs are more harmful than the ones received by STAs, as APs are frequently more active and interferences will have lager impacts over time. For example, for a STA and an AP that interfere, we have two edges between them (with opposite directions), with different weights to represent that the interference produced from the AP to the STA is more harmful than the interference from the STA to the AP. Finally, it is important to note that two STAs attached to the same AP will not interfere with each other, as their communications with the AP are coordinated.

Figure 1 shows an example of the connectivity layer of a Wi-Fi network with 49 APs and 245 STAs. From this figure, it is easy to explain a concept that will be used later on in this work—that is, the concept of a cluster. As can be seen in the figure, the whole network is composed by a set of APs, each one with a set of STAs attached to it. With this, we define a cluster as one of those sets of an AP and its attached STAs. On the other hand, Figure 2 shows, for the same example scenario, the resulting interference layer.

As stated above, the weights of the edges in the interference layer will be determined by the power levels of the interference signals. More specifically, the weight between vertices $V_i$ and $V_j$ will be determined by:

$$I_{V_i\to V_j}=P_t+G_t+G_r-L-P_{loss}+\psi +I,$$

(1)

where, with all values expressed on the logarithmic scale, $P_t$ represents the transmission power; $G_t$ and $G_r$ are the transmission and reception antenna gains, respectively; L includes the propagation losses because of obstacles, such as walls, doors, windows, etc.; and $P_{loss}$ represents the signal loss due to the distance, and has been computed according to [31], considering that antennas are placed 1.5 m above the floor. Additionally, $\psi$ represents the abovementioned asymmetry effect which makes interferences from APs more harmful that the ones received from STAs, as the interferences from APs will take place over far more time than the ones from STAs. On the linear scale, we have considered $\psi =0.5$ for APs and $\mathsf{\Psi }=0.2$ for STAs. Finally, I is the indicator function and represents the collision between two signals operating in the same frequency channel, so on a linear scale, it will take the value 1 if a trasmitter and receptor operate in the same channel and the value 0 otherwise; i.e.,

$$I=\left\{\begin{array}{cc}1,\hfill & \mathrm{if}{c}_i=c_j\hfill \\ 0,\hfill & \mathrm{otherwise}\hfill \end{array}\right.$$

$c_i$ ($c_j$) being the channel of vertex i (j).

2.3. Signal to Interference Ratio and Utility of the Solutions

To evaluate the performance of a specific channel assignment we use a two-step procedure. First, we compute the signal to interference ratio ($SI{R}_i$) for device i, and later on we compute, from the $SI{R}_i$, the utility for a certain wireless device i, denoted by $U_i$, which represents its normalized performance. In the following, we explain how we perform the the computation of both parameters, $SI{R}_i$ and $U_i$.

To compute the $SIR$ for a certain wireless device i we make use of the power levels of the interferences defined in the edge weights of the interference layer and also the power of the desired signal, using the same loss model as in Equation (1). Denoting by $S_{V_j\to V_i}$ the power of the desired signal from vertex j to vertex i, we can compute $SI{R}_i$ by:

$$SI{R}_i=\frac{S_{V_j\to V_i}}{{\sum }_k{I}_{V_k\to V_i}}$$

(2)

.

It is important to highlight that a STA will have only a $SIR$ value but APs will have an $SIR$ value for each of its attached $STAs$. For that reason, we have chosen the worst case as the $SIR$ value for a certain AP; i.e., we have chosen the minimum $SIR$ from all of its STAs to be the final $SIR$ for that AP.

Although $SIR$ is a well-known parameter that could represent the performance for a certain node, the user experience of such performance is upper and lower-bounded [32]. If $SIR$ is above a certain maximum value, the user experience is limited by the performance of the technology, as the throughput is limited by the technology under use. On the other hand, if the $SIR$ is below a minimum threshold, the devices cannot keep their connection and the user experience is unacceptable. For that reason, we have mapped the $SIR$ for a device i into a new performance parameter called utility, denoted by $U_i$, and that is a linear mapping of the $SI{R}_i$ from a minimum value of 0 when $SI{R}_i$ is below $SI{R}_{min}$ up to a maximum value of 1 when $SI{R}_i$ is above $SI{R}_{max}$. Using this new parameter, the performance of every wireless device is in the range of $[0,1]$, so it can be considered as normalized throughput, as higher values of SIR will let higher values of throughput and vice versa.

From the utility obtained by each device in the network, we can define the utility of the whole system for a certain channel assignment as the sum of utilities of all of its devices:

$$U=\sum _{\forall i}{U}_i$$

(3)

.

3. Cluster-Based Channel Assignment

3.1. AIIM Technique

In this work, we propose a heuristic channel assignment technique based in the proposal made in [27] (from now on, we will call this technique AIIM). In the following, we first describe the original proposal in [27] and then we describe our proposal.

AIIM is a network-controlled channel assignment technique based on a central coordinator, so it can be considered a heuristic technique useful for coordinated settings, as the one we are using in Section 4.1.

The final objective of AIIM is to maximize the utility of the AP with the least utility. Note that we are using the definition of utility described in this manuscript. AIIM starts by selecting a random AP and assigning the channel with the best utility (breaking ties randomly), and this process is repeated for all the APs. After this first assignment, we obtain what is called the temporary channel assignment. After this, we compute the utility of this temporary channel assignment, called S. The next step of the procedure is to select APs with utility lower than 1 and try to assign them the respective channels with the highest values for utility that do not degrade S, i.e., without degrading the sum of utilities gotten so far. This process is repeated for all the APs R times.

3.2. Cluster-Based AIIM

As has been mentioned already, in this paper we propose a channel assignment technique that is based on AIIM. Most of the channel assignment proposals for Wi-Fi networks in the literature ignore the STAs in the process. However, we claim that STAs must be taken into account because they represent the final customers receiving service, and their number has been increasing over the years. The proposal of this paper is a generalization of AIIM where we consider that, in addition to the interferences between APs, two clusters also interfere with each other if some of their STAs do. Another perspective of this generalization is to consider the wider concept of a cluster for considering interferences instead of just APs. In Figure 3 we show, by means of an example, a comparison of the interferences considered in AIIM and in CB-AIIM. In Figure 3a we can see five clusters with different colors for identifying each, where each cluster has an AP (large circles) and several STAs (small squares). For that setting, we show with dashed red lines the interferences that are considered in AIIM. However, in Figure 3b we show the same setting and how it would work in CB-AIIM. As can be seen, the difference is that the interferences are taken into account between STAs belonging to different clusters, as dotted red lines show.

4. Experimental Evaluation

In this section we evaluate the performance of the proposed channel assignment technique called CB-AIIM. To evaluate the proposed channel assignment technique, we have made use of the model used in Section 2 using Python as the programming language. The specific parameters used for the model are $P_t=30$ mW, $G_t=G_r=0$ dB, $L=40$ dB, $SI{R}_{min}=10$ dB and $SI{R}_{max}=40$ dB. The specific layouts with which the channel assignment technique have been tested (described in Section 4.1) have been modeled using graphs that are stored as GML (Graph Modeling Language) files and that has been built using the networkx library in Python.

4.1. Experimental Setting

We have chosen a realistic layout to compare our proposal with other well-known channel assignment techniques. This layout is the first floor of the Polytechnic School of the University of Alcala (Spain). This building is square-shaped, with sides approximately 130 m long. We have used the real positions whereat the 26 APs are located in the building, which are shown in the heat map displayed in Figure 4. In this figure, signal coverage ranges from light blue (low coverage) to red (high coverage). The reason for having such a low coverage in the center of the setting is because it is a central courtyard. Regarding the positions of STAs, they are not included in Figure 4, because their positions will depend on the occupancy of the building. In a university campus, students will be mainly attending classes, but there are also a number of students in the buildings involved in different activities (studying, preparing assignments, labs, etc.). For that reason, in all of our settings we have considered that there are 100 randomly located STAs in the plant. Moreover, we have considered a varying number of classrooms under use. In the first floor plant of the building there are 48 classrooms, so in our different settings we have considered 12, 24, 36 and 48 classrooms simultaneously under use, to represent different occupancy settings, being: low, medium, high and total occupancy, respectively. For each of this occupancy settings we have considered two scenarios. For example, in the low occupancy setting, where 12 from a total of 48 classrooms are in use ($25\%$), these 12 classrooms are chosen randomly, so we have tested two different choices. In each classroom that is under use, we have considered that there are 25 students randomly located in that classroom using a normal distribution around the center and a standard deviation of $6.5$ m. To summarize, and for example, the two scenarios of low occupancy (25% of the classrooms under use) have 100 STAs randomly located and $12·25=300$ STAs, giving a total of 400 STAs. With a similar reasoning, for the medium, high and total occupancy settings, we will have 700, 1000 and 1300 STAs, respectively. In Figure 5 we show the resulting graph for one the scenarios for each classroom occupancy. Note that in those figures we have overlapped both connectivity and interference layers into a single picture. Again, we have used large green circles to represent APs, small black squares to represent STAs and red lines to represent interferences. To distinguish interferences from STA-AP associations in the same picture, we have used black-dashed lines to represent the association between APs and STAs.

4.2. Performance Evaluation

In this section we present the main results related to the performance evaluation of the proposed technique, CB-AIIM. We have compared our proposal with four other techniques. First, we have considered the simplest channel assignment technique, which consists of choosing a random channel for each AP. We have called this technique random, and although we expect it to have a low performance, it is interesting to include in the evaluation as a baseline. In addition to random, we have also considered other proposals that have been proposed in the literature in the last years and that have been already cited in Section 1. These techniques have been named according to the names of their authors, so KCKC is the technique proposed in [7] and HZNA the one proposed in [26]. Finally, we have also included AIIM [27] to show how the effect of STAs included in our proposal (CB-AIIM) is able to improve the results.

Figure 6, Figure 7, Figure 8 and Figure 9 show the results of the performance comparison of the abovementioned techniques. In these figures we show the global utility (see Section 2.3) of the channel assignment obtained by the different techniques. To obtain the results, all the experiments have been run 20 times. For each technique and in each of the eight settings, we show the average utility obtained, along with the 95% confidence intervals (in black) and the utility of the best and the worst execution (maximum and minimum utility, shown as blue and red crosses, respectively). As we can notice by inspecting Figure 6, Figure 7, Figure 8 and Figure 9, there are not significant differences in the conclusions that can be obtained depending on the classroom occupancy. As expected, the utility when there are more wireless devices in the network is higher (when the classroom occupancy increases), but the relative performances of the different techniques do not depend on the density of the Wi-Fi network.

If we analyze the differences in the performance among the studied techniques, we notice that “random” offers the worst performance, as expected. Next, the worst performance was obtained by KCKC, which offers better performance than "random" in mean but sometimes gets very poor solutions (see the minimum values for KCKC). However, it is interesting to note that in a few cases KCKC was able also to obtain very good results (see the maximum values for KCKC). From that and especially due to the fact that KCKC usually has the largest confidence intervals, we can conclude that KCKC is the technique with the highest variability from all the studied ones. The performance of AIIM was slightly better than that of KCKC, as it was similar in most scenarios but it was better in both the medium classroom occupancy settings. Moreover, AIIM had lower variability than KCKC. HZNA usually offered greater utility higher than KCKC and AIIM, but not always, as its performance was, in some cases, similar to those of the others. However, from KCKC, HZNA and AIIM, HZNA is the technique with the lowest variability, as its confidence intervals are clearly the smallest.

Once the differences in performance of the proposals random, KCKC, HZNA and AIIM were analyzed, it was time to compare our proposal with all of them. Our proposal, CB-AIIM, was able to obtain the best performance in all the studied cases, and it is also interesting to highlight that the varialbility of the results is similar to that obtained by HZNA. Comparing AIIM with CB-AIIM, we can conclude that considering the interferences produced by STAs lets us obtain much better results, not only in terms of average utility, but also in terms of variability of results, so the effect of STAs in channel assignment, although it has been barely studied in the literature, lets us achieve much better channel assignment distributions.

5. Conclusions

Channel assignment in Wi-Fi networks is a complex problem with increasing interest for our society, as there is unceasing growth in the number of customers that make use of Wi-Fi networks, and the available radio resources are very limited. In this paper we propose a heuristic channel assignment technique that is suitable for Wi-Fi networks with a central coordinator. As software-defined networks (SDN) represent a powerful and flexible method for network management, Wi-Fi networks can benefit from this current technology to implement channel assignment techniques. Using SDN, the deployment of centralized channel assignment techniques is easy to implement, as once the specific channel assignment is known, the SDN controller can apply it through its Openflow southbound API [33].

We modeled the problem as a geometric multilayer graph with two layers: a connectivity layer and an interference layer. The main hypothesis of the paper is that the effect of STAs must be considered in the process of channel assignment. To test that hypothesis, we have proposed a technique called CB-AIIM that is an evolution of AIIM [27], which considers the effect of STAs. In fact, CB-AIIM can be a generalization of AIIM that uses the concept of a cluster (that is composed by an AP and its associated STAs) instead of basing the channel assignment on just the APs. Results show that CB-AIIM clearly improves the performance of AIIM, not only in terms of utility, but also in terms of the variability of the solutions. For that reason, we claim that considering the effect of STAs (the interferences they produce) plays a paramount role in the design of channel assignment techniques. Moreover, we have compared CB-AIIM with other recent proposals appearing in the literature, and we have shown that CB-AIIM outperforms all of them.

Although the proposal has yielded very satisfactory results, there are still plenty of research opportunities in this area. Our most immediate efforts involve shifting from just considering STAs in a centralized channel assignment to actually involving them in reaching the solutions in a semi-decentralized or decentralized manner. In other words, we plan to develop channel assignment techniques that actively involve STAs in the channel assignment process.