# A Cluster-Based Channel Assignment Technique in IEEE 802.11 Networks
## 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 technologies. 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 technologies, 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.