RECENT studies ,  on operational IEEE 802.11wireless LANs (WLANs) have shown that traffic loadis often unevenly distributed among the access points(APs). In WLANs, by default, a user scans all availablechannels and associates itself with an AP that has thestrongest received signal strength indicator (RSSI), whilebeing oblivious to the load of APs. As users are, typically,not evenly distributed, some APs tend to suffer from heavyload, while their adjacent APs may carry only light load.Such load imbalance among APs is undesirable as ithampers the network from fully utilizing its capacity andproviding fair services to users. In this paper, we present anovel load balancing scheme that reduces the load ofcongested APs by forcing the users near the boundaries ofcongested cells to move to neighboring less congested cells.We achieve this via cell size dimensioning by controllingthe transmission power of the AP beacon messages. In thispaper, a WLAN cell is defined as a region in which the APbeacon signal has the strongest RSSI. Our approach isconceptually similar to cell breathing in cellular networks ,. We present an optimal algorithm that finds deterministicmin-max load balancing solutions. Informally, aWLAN is called min-max load balanced, if it is impossibleto reduce the load of any AP without increasing the load ofother APs with equal or higher load. Our approach ispractical since it does not require either user assistance orstandard modification.1.1 Related WorkCurrently, the IEEE 802.11 standard does not provide anymechanism to resolve load imbalance. To overcome thisdeficiency, various load balancing schemes have beenproposed. These methods commonly take the approach ofdirectly controlling the user-AP association by deployingproprietary client software or hardware. For instance,vendors can incorporate certain load balancing features intheir device drivers, AP firmwares, and WLAN cards. Inthese proprietary solutions, APs broadcast their load levelsto users via modified beacon messages and each userchooses the least-loaded AP.Several studies , , , , , , , , , have proposed a variety of association metrics insteadof using the RSSI as the sole criterion. These metricstypically take into account such factors as the number ofusers currently associated with an AP, the mean RSSI ofusers currently associated with an AP, and the bandwidththat a new user can get if it is associated with an AP, e.g.,, . Balachandran et al.  proposed to associate a userwith an AP that can provide a minimal bandwidth requiredby the user. In , Velayos et al. introduced a distributedload balancing architecture where the AP load is defined asthe aggregated downlink and uplink traffic through the AP.In , , Kumar and coworkers proposed an associationselection algorithms which are based on the concept ofproportional fairness to balance between throughput andfairness. In , Kauffmann et al. provided a mathematicalfoundation for distributed frequency allocation and userassociation for efficient resource sharing. Recently, in ,Shakkottai et al. considered a noncooperative multihomingapproach and showed that under appropriate pricing, thesystem throughput is maximized. In , a strong relationbetween fairness and load balancing is shown. Most ofthese work determine only the association of newly arrivedusers. Tsai et al.  is an exception, in which Tsai and Lien proposed to reassociate users when the total load exceeds acertain threshold or the bandwidth allocated to users dropsbelow a certain threshold. While the existing load balancingschemes achieved considerable improvement in terms ofthroughput and fairness, they require certain support fromthe client side. In contrast, the proposed scheme does notrequire any proprietary client support.Cell breathing has been studied mostly in the context ofCDMA cellular networks. The coverage and capacity of aCDMA cell are inversely related with each other . Theincrease of the number of active users in a cell causes theincrease of the total interference sensed at the base station.Therefore, in congested cells, users need to transmit withhigher power to maintain a certain signal-to-interferenceratio at the receiving base station. As the users in acongested cell increase their transmission power, they alsoincrease their interference to the neighboring cells since allcells use the same frequency in CDMA networks. As aresult, the overall network capacity may decrease. Furthermore,since the maximal transmission power of the users isbounded, the users who are far from the base station mayexperience poor services. To overcome these problems, thecell breathing approach was proposed by Togo et al.  andJalali . In essence, they reduce the size of congested cells.Some studies have explored the benefit of combining thecell breathing methods with other interference mitigationmethods. For instance, in , Yang and Ephremidespresented a solution, which is based on the combinationof cell breathing and bandwidth space partitioning. Duet al.  proposed a distributed load balancing techniquethat utilizes a bobble oscillation algorithm. In , Sanget al. proposed a method that coordinates the packet levelscheduling with cell breathing techniques. These schemesare different from our scheme mainly in two aspects. First,they utilize probabilistic local optimization heuristics.Therefore, they do not provide any guarantee on thequality of the solutions, while our approach finds theoptimal solution. Second, these schemes cannot be easilyapplied to IEEE 802.11 WLANs, e.g., they require thechange of scheduling mechanism or bandwidth partition.Recently in , Bahl et al. proposed cell breathingalgorithms for WLANs that attempt to maximize the overallsystem throughput. In this paper, the authors formulate thecell breathing problem as a mixed Integer-Linear program,assuming the continuous power level assignment. In thispaper, we present a cell breathing method which findsdeterministic global optimal solutions for providing fairnessunder the assumption that only discrete set of powerlevels are feasible. The scheme in  and our scheme canbe viewed as complementary.1.2 Our ContributionsWLAN fairness needs to be considered in two aspects, intra-AP fairness and inter-AP fairness. Intra-AP fairness requireseach AP to provide fairness to its associated users based ona given objective or metric. The scope of this task is locallyconfined to each AP cell and it can be obtained relativelyeasily, e.g., by controlling the traffic. Inter-AP fairnessaddresses a task of determining user association forensuring fairness across all APs, assuming that each APprovides intra-AP fairness. Inter-AP fairness is obtainedwhen the load of APs is balanced. Since the load of APsfrequently changes as a result of varying channel conditionsand the burstiness of user traffic, short-term load balancingcauses instability of the system as users will be constantlyshifted between APs. To prevent system instability, it isdesirable to consider only the long-term channel conditionand user traffic. In this paper, we target at the long-term inter-AP fairness assuming that intra-AP fairness is provided.Our scheme provides inter-AP fairness by adjusting thecell sizes. The WLAN cell size is changed by controlling thetransmission power of the AP beacons. Note that we do notchange the transmission power of the data traffic messages.The proposed algorithms are not tied to a particular loaddefinition, but support a broad range of load definitions. Wetreat the load of an AP as the aggregation of the loadcontributions of its associated users. The load contributionmay be as simple as the number of users associated with anAP or can be more sophisticated to consider factors liketransmission bit rates and traffic demands. Consequently,various load balancing and max-min fairness objectives canbe achieved, such as bandwidth fairness, time fairness, andweighted fairness.1 Our scheme does neither require anyspecial assistance from users nor any change in the 802.11standard. It only requires the ability of dynamicallychanging the transmission power of the AP beacons. Today,commercial AP products already support multiple transmissionpower levels, so we believe that this requirementcan be relatively easily achieved.Depending on the extent of available information, weconsider two knowledge models. The first model assumescomplete knowledge, in which user-AP association and APload are known a priori for all possible beacon powersettings. Since such information may not be readilyavailable, we also consider the limited knowledge model, inwhich only information on the user-AP association and APload for the current beacon power setting is available.Below, we describe an overview of our algorithms.At first, we address the problem of minimizing the loadof the congested APs. Let us call the AP with the maximalload as congested AP and its load as congestion load. Wedesigned two polynomial time algorithms that find optimalsolutions, one for the complete knowledge model and theother for the limited knowledge model. These results areintriguing, because similar load balancing problems, e.g.,, are known to be strong NP-hard. It is particularlyinteresting that a polynomial time optimal algorithm existsfor the limited knowledge model.Second, we address the problem of min-max loadbalancing. This is a strong NP-hard problem. In , it isproved that there exists no algorithm that guarantees anycoordinatewise approximation ratio, and the approximationratio of any prefix-sum approximation algorithm is at least_ðlognÞ, where n is the number of APs. In this paper, wesolve a variant of this min-max problem, termed min-maxpriority load balancing, whose optimal solution can becalculated in polynomial time for both knowledge models.Here, the AP load is defined as an ordered pair of the aggregated load contributions of its associated users and aunique AP priority.Our algorithms can be efficiently embedded intoadaptive online strategy. Through extensive simulations,we show that the performance of the proposed methods iscomparable with or superior to the existing associationcontrol methods, irrespective of network load patterns. Inparticular, we could achieve such performance even with asmall number of power levels.
2 NETWORK MODEL
We consider a WLAN with a set of APs, denoted by A. jAjdenotes the number of APs. All APs are directly attached toa wired infrastructure. Each AP can support severaltransmission power levels. Without loss of generality, eachAP can use one of K þ 1 transmission power levels, denotedby fPkjk 2 ½0::K_g, where the minimal and maximal levelsare denoted by Pmin ¼ P0 and Pmax ¼ PK, respectively. Apower level Pk is identified by its power index k and itstransmission power is _ times stronger than its predecessorPk_1, where _ is defined as _ ¼ ffiPffiffiffimffiffiffiaffiffixffiffi=ffiffiPffiffiffiffimffiffiffiiffinffiffiKp , i.e., _ > 1.Because Pk ¼ _ _ Pk_1, it follows that Pk ¼ Pmin _ _k forevery k 2 ½0::K_. This assumption is consistent with thetransmission power level configurations supported bycommercial AP products. We refer to the transmissionpower level of an AP a 2 A as the power index of AP a and itis denoted by pa. The network coverage area is defined as theunion of the transmission ranges of all APs in A. Initially, weassume that the AP deployment ensures a high degree ofoverlaps between the range of adjacent APs, so that everyuser is covered by at least one AP even when all APs aretransmitting at the minimal power level Pmin.We later relaxthis strong coverage assumption.U denotes the set of all users in the network coveragearea and jUj denotes their number. For optimal algorithms,we assume that users have a quasi-static mobility pattern.In other words, users can move freely, but they tend to stayin the same locations for a long period. This assumption isbacked up by recent analysis of mobile user behavior ,. User mobility is handled by the online strategydescribed in Section 7. At any given time, each user isassociated with a single AP. When a user enters a WLAN, itscans all channels (i.e., listening for the beacon messages)for identifying all APs in its reach. Then, based on theRSSI’s of the beacon messages, the user associates itself withan AP that has the strongest RSSI. The RSSI depends on thetransmission power of the beacon messages and the signalattenuation between AP and user.Generally, the channel quality is time-varying. For theuser-AP association decision, a user performs multiplesamplings of the channel quality, and only the signalattenuation that results from long-term channel conditionchanges are utilized. Based on the RSSI, we can divide thenetwork coverage area into jAj disjoint cells. The transmissionbit rate for a user-AP pair is determined by the Signalto-Noise Ratio (SNR). Users associated with the same APmay transmit at different bit rates, and each user maycontribute a different amount of load to its serving AP. Weassume that appropriate channel allocation was made, sothat adjacent cells do not interfere with each other.Our algorithms do not require any particular loaddefinition. We only assume that the load of an AP a,denoted by ya, is the sum of the load contributions of itsassociated users. We use la;u to denote the load contribution(also termed the weight) of a user u on an AP a. We assumethat this contribution is constant,2 so that the load of eachAP a 2 A is ya ¼ Pu2Uala;u, where Ua denotes the set ofusers associated with a. The APs that experience themaximal load are called the congested APs and their load,termed congestion load, is denoted by Y . Other APs withlower load are called noncongested APs.Our load model can accommodate various additive loaddefinitions such as the number of users associated with anAP. It can also deal with the multiplicative user loadcontributions, i.e., ya ¼ _u2Ua la;u, by applying log to bothsides. By using different metrics for evaluating the loadcontribution of a user on its AP, la;u, different load balancingobjectives can be achieved. For instance, by allocating aweight of one to all users, time fairness can be achieved. Insuch case, each AP serves each one of its associated usersfor the same time duration but does not necessarily providethe same bandwidth. Weights can be set based on the userstransmission bit rates to achieve bandwidth fairness.Weights for different objectives can be combined, so thattradeoffs between different fairness objectives can be made.Table 1 summarizes the key notations used in this paper.
3 CELL BREATHING APPROACH
In this section, we present the basic concept that underliesour approach and also address the algorithmic challenge.
download full report