A Throughput-Based Radio Channel Allocation Algorithm for WLANs with Multiple APs

Usually, the radio channel allocation (RCA) problems of wireless LANs (WLANs) are solved by using various heuristic methods. However, it is not clear that the minmax problem is an NP-hard problem or not. In this paper, we consider WLANs with multiple APs that can be deployed in an ad hoc network. First, we propose a distributed heuristic algorithm (DHA) for RCA, which allocates channels in terms of the throughput of the channel used by an access point (AP). The algorithm significantly improves the channel throughput. Then, we analyze the computational complexity of the DHA by using both statistical analysis and simulations, i.e., the computational scale (CS) of the DHA, which is the number of channel reallocation times until the network reaches a convergence state. After that, by extensive simulations, we demonstrate that DHA reaches the convergence state very quickly. The total number of channel reallocations is a log-logistic distribution. Finally, we develop a method to estimate the CS and find that the overall upper limit of the CS is O(I) for a WLAN with I APs.