Cell Breathing Techniques for Load Balancing in Wireless LANs

Maximizing the network throughput while providing fairness is one of the key challenges in wireless LANs (WLANs). This goal is typically achieved when the load of the access points (APs) is balanced. However, recent studies on operational WLANs have shown that AP load is often substantially uneven. 

To alleviate such imbalance of load, several load balancing schemes have been proposed. These schemes, essentially, require proprietary client software or specially-designed WLAN cards at the user computers for controlling the user-AP association. In this paper we present a new technique that achieves load balancing by reducing the cell size of congested APs, which is conceptually similar to the so-called "cell breathing" methods in cellular networks. 

The proposed scheme does not require any modification at the user side neither the standard, but it only requires the ability of dynamically changing the transmission power of the AP beacon messages. Unlike existing cell-breathing methods, which utilize local optimization heuristics, we develop algorithms that guarantee to find the optimal beacon power settings, which minimize the load of the most congested APs, in polynomial time. 

We then consider the problem of network-wide min-max load balancing. We prove that this problem is NP-hard and cannot be easily approximated. In spite of this, we identify a variant of the problem, termed m min-max priority load balancing, and present polynomial- time algorithms to find optimal solutions. Extensive simulations show that the performance of our cell-breathing methods is comparable with or superior to the existing association-based methods.