10-06-2013, 04:03 PM
Cell Breathing Techniques for Load Balancing in Wireless LANs
Cell Breathing Techniques.pdf (Size: 2.66 MB / Downloads: 20)
Abstract
Maximizing network throughput while providing fairness is one of the key challenges in wireless LANs (WLANs). This goal
is typically achieved when the load of access points (APs) is balanced. Recent studies on operational WLANs, however, have shown
that AP load is often substantially uneven. To alleviate such imbalance of load, several load balancing schemes have been proposed.
These schemes commonly require proprietary software or hardware at the user side for controlling the user-AP association. In this
paper we present a new load balancing technique by controlling the size of WLAN cells (i.e., AP’s coverage range), which is
conceptually similar to cell breathing in cellular networks. The proposed scheme does not require any modification to the users neither
the IEEE 802.11 standard. It only requires the ability of dynamically changing the transmission power of the AP beacon messages. We
develop a set of polynomial time algorithms that find the optimal beacon power settings which minimize the load of the most congested
AP. We also consider the problem of network-wide min-max load balancing. Simulation results show that the performance of the
proposed method is comparable with or superior to the best existing association-based methods.
INTRODUCTION
RECENT studies [2], [3] on operational IEEE 802.11
wireless LANs (WLANs) have shown that traffic load
is often unevenly distributed among the access points
(APs). In WLANs, by default, a user scans all available
channels and associates itself with an AP that has the
strongest received signal strength indicator (RSSI), while
being oblivious to the load of APs. As users are, typically,
not evenly distributed, some APs tend to suffer from heavy
load, while their adjacent APs may carry only light load.
Such load imbalance among APs is undesirable as it
hampers the network from fully utilizing its capacity and
providing fair services to users. In this paper, we present a
novel load balancing scheme that reduces the load of
congested APs by forcing the users near the boundaries of
congested cells to move to neighboring less congested cells.
We achieve this via cell size dimensioning by controlling
the transmission power of the AP beacon messages. In this
paper, a WLAN cell is defined as a region in which the AP
beacon signal has the strongest RSSI. Our approach is
conceptually similar to cell breathing in cellular networks [4],
[5]. We present an optimal algorithm that finds deterministic
min-max load balancing solutions.
Related Work
Currently, the IEEE 802.11 standard does not provide any
mechanism to resolve load imbalance. To overcome this
deficiency, various load balancing schemes have been
proposed. These methods commonly take the approach of
directly controlling the user-AP association by deploying
proprietary client software or hardware. For instance,
vendors can incorporate certain load balancing features in
their device drivers, AP firmwares, and WLAN cards. In
these proprietary solutions, APs broadcast their load levels
to users via modified beacon messages and each user
chooses the least-loaded AP.
Several studies [6], [7], [8], [9], [10], [11], [12], [13], [14],
[15] have proposed a variety of association metrics instead
of using the RSSI as the sole criterion. These metrics
typically take into account such factors as the number of
users currently associated with an AP, the mean RSSI of
users currently associated with an AP, and the bandwidth
that a new user can get if it is associated with an AP, e.g.,
[6], [7]. Balachandran et al. [8] proposed to associate a user
with an AP that can provide a minimal bandwidth required
by the user. In [9], Velayos et al. introduced a distributed
load balancing architecture where the AP load is defined as
the aggregated downlink and uplink traffic through the AP.
In [10], [11], Kumar and coworkers proposed an association
selection algorithms which are based on the concept of
proportional fairness to balance between throughput and
fairness.
Algorithmic Challenges
One may consider a greedy algorithmthat reduces the power
level of the congested APs until any of the congested APs
reaches to the minimal power level. This will shift users
from congested APs to their neighbors, and the set of
congested APs and their load may change during the
execution of the algorithm. As we demonstrate in Example
2, even in a very simple case, the greedy algorithm may
fail to find the optimal solution. Moreover, it can be shown
that in some cases, the final congestion load is even higher
than the initial congestion load. We need more sophisticated
algorithms.
CONCLUSION
We presented a novel scheme for optimal load balancing
in IEEE 802.11 WLANs. We provided rigorous analysis of
the problem and presented two algorithms that find
deterministic optimal solutions. The first algorithm minimizes
the load of the congested AP(s) in the network, and
the second algorithm produces an optimal min-max
(priority) load balanced solution. These optimal solutions
are obtained only with the minimal information which is
readily available without any special assistance from the
users or modification of the standard. We assume only
the control on the transmission power of the AP beacon
messages. The simulations show that even a small
number of power levels, e.g., between 5 and 10, is
enough to achieve near optimal results.