Transcription
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. , NO. , 20131AP Association for Proportional Fairness inMulti-rate WLANsWei Li, Student Member, IEEE, Shengling Wang, Member, IEEE, Yong Cui, Member, IEEE,Xiuzhen Cheng, Senior Member, IEEE, Ran Xin, Mznah A. Al-Rodhaan, Abdullah Al-DhelaanAbstract—In this study, we investigate the problem of achievingproportional fairness via AP association in multi-rate WLANs.This problem is formulated as a non-linear programming with anobjective function of maximizing the total user bandwidth utilitiesin the whole network. Such a formulation jointly considers fairness and AP selection. We first propose a centralized algorithmNLAO-PF to derive the user-AP association via relaxation. Sincethe relaxation may cause a large integrality gap, a compensationfunction is introduced to ensure that our algorithm can achieveat least half of the optimal in the worst-case. This algorithm isassumed to be adopted periodically for resource management.To handle the case of dynamic user membership, we propose adistributed heuristic BPF based on a novel performance revenuefunction, which provides an AP selection criterion for newcomers.When an existing user leaves the network, the transmission timesof other users associated with the same AP can be redistributedeasily based on NLAO-PF. Extensive simulation study has beenperformed to validate our design and to compare the performanceof our algorithms with those of the state-of-the-art.Index Terms—AP association; bandwidth allocation; multi-rateWLANs; proportional fairness.I. I NTRODUCTIONBY default, each user in an IEEE 802.11 WLAN associateswith the AP that has the largest received signal strengthindicator (RSSI). As typically users are not uniformly distributed among all APs, RSSI based approach may overloadsome APs while leave others to carry very light load or even tobe idle. This load unbalancing could result in unfair bandwidthallocation. Although the network is supposed to serve fairly athigh performance, fairness and efficiency are often in conflictwith each other. With the development of multi-rate WLANs,this problem has become even more challenging, as users withdifferent bit rates intend to share the same WLAN.It is well-known that the popular 802.11 MAC protocolprovides equal long-term transmission opportunities to allWei Li and Xiuzhen Cheng are with Department of Computer Science,The George Washington University, Washington DC, USA. Email: {weili,cheng}@gwu.edu.Shengling Wang is with the Institute of Computing Technology, ChineseAcademy of Sciences, Beijing, China. Email: wangshengling@ict.ac.cn.Yong Cui is with Department of Computer Science, Tsinghua University,Beijing, P. R. China. Email: cuiyong@tsinghua.edu.cn.Ran Xin is with Department of Computer Science, Illinois Institute ofTechnology, Chicago, USA. Email: rxin@iit.edu.Mznah A. Al-Rodhaan and Abdullah Al-Dhelaan are with College ofComputer and Information Sciences, King Saud University, Riyadh, SaudiArabia. Email: {rodhaan, dhelaan}@ksu.edu.sa.This work has been supported by the National Science Foundation of theUS (CNS-0831852), the NPST program by King Saud University (ProjectNo. 10-INF1184-02), and the National Natural Science Foundation of China(Grant No. 61272475 and 61003225).users associated with the same AP. Therefore users with thesame frame size and same transmission rate can achieve equalthroughput (i.e. throughput-based fairness). However, in multirate WLANs, throughput-based fairness requires that userswith lower bit rates occupy the channel for longer times thanthose with higher bit rates, drastically reducing the networkthroughput [1], [2]. To overcome this problem, time-basedfairness is proposed such that each user can obtain an equalshare of channel occupancy time. Recent research [1], [3] hasshown that time-based fairness outperforms throughput-basedfairness in multi-rate WLANs.There exist other fairness criteria that are widely adoptedin network resource assignment. Max-min fairness distributesresources as equally as possible among users [4]–[7]; proportional fairness, on the other hand, allocates bandwidth tousers in proportion to their bit rates to maximize the sumof the bandwidth utilities of all users [8]–[10]. Proportionalfairness has been utilized to effectively exploit the tradeoffbetween fairness and network performance [8], [11]. It isargued [12] that within a single saturated AP, throughput-basedfairness and max-min fairness are equivalent; moreover, if allusers have the same priority level, time-based fairness andproportional fairness are also equivalent.Fairness and AP association should be jointly consideredfor resource management in multi-rate WLANs but existingresearch mainly focuses on the joint study of max-min fairnessand AP association. In this paper, we investigate the problemof achieving proportional fairness via AP association forperformance enhancement. To achieve this goal, we formulatethe problem to a non-linear programming (NLP) with anobjective function of maximizing the total user bandwidthutilities in the whole network, and propose a centralizedalgorithm termed Non-Linear Approximation Optimization forProportional Fairness (NLAO-PF) to solve it. Since the objective function of our NLP is nonlinear and the AP associationis a 0-1 integer programming problem, NLP is NP-hard [13].Therefore NLAO-PF is decomposed into four steps to simplifythe issue and improve the degree of approximation. By introducing a compensation function to the objective function ofNLP, the total utility of the bandwidth allocation via NLAOPF is proved to be at least half of the optimal in the worstcase. In real world applications, NLAO-PF can be adoptedperiodically to achieve proportional fairness. To handle thecase of dynamic user membership, we propose a distributedheuristic termed Best Performance First (BPF) based on anovel performance revenue function, which provides an APselection criterion for the newly-arriving users. When an
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. , NO. , 2013existing user leaves the network, the transmission times ofother users associated with the same AP can be redistributedeasily based on NLAO-PF. Our comparison-based simulationstudy indicates that both NLAO-PF and BPF perform wellwhen the users are distributed randomly and uniformly in thewhole network. Moreover, the superiority of our algorithms iseven higher compared to the most relevant ones when usersare distributed in a hot spot area.The rest of the paper is organized as follows. The mostrelated work is discussed in Section II. The fairness criterionand our network model are introduced in Section III. The twoalgorithms are detailed in Sections IV and V. After presentingthe evaluation results in Section VI, we conclude this paperin Section VII.II. R ELATED W ORKAchieving fairness within a single AP via optimizing themedia access procedure has been extensively studied. Thefairness of CSMA/CA is analyzed by Jian and Chen in [14].This work also proposes a rate control protocol called “Proportional Increase Synchronized Multiplicative Decrease” toachieve fair bandwidth allocation. The short-term and longterm fairness of the 802.11 DCF procedure are investigatedin [15] by employing the conditional probabilities of thenumber of inter-transmissions. A technique to estimate the fairrate from passive traffic measurements of a video applicationis also proposed in [15]. In [1], [16]–[18], different mediaaccess methodologies are investigated to optimize the MACparameters for fairness. In [19], a CSMA/CA MAC protocolwithout adopting the exponential back-off procedure is proposed to optimize the throughput when achieving time-basedfairness by adaptively determining the contention window sizebased on the transmission opportunities.AP association is another fundamental problem in wireless networks to enhance the performance. Ekici and Yongacoglu [20] propose a distributed AP selection scheme, inwhich a user associates with an AP that provides the bestperformance in terms of congestion relief by considering thebit rate as well as the number of users accommodated by theAP. Abusubaih and Wolisz [21] present a centralized optimalassociation policy for multi-rate IEEE 802.11 WLANs. Theirpolicy is based on the cell status information and can facilitateinformation exchange between APs. Yen et al. [22] modelAP selection under the framework of game theory, wherethe sole goal of each wireless station is to maximize itsachievable throughput, by considering both the number ofwireless stations that associate with the same AP and the set oflink rates these wireless stations possess. Keranidis et al. [23]make the AP selection for each user in a distributed way tomaximize per-user total throughput, which is defined to be thesum of the throughputs on the uplink and the downlink.None of the works mentioned above jointly considers fairness and AP association. Achieving throughput-based maxmin fairness via AP association has been studied in [6], [24]–[26]. Gong et al. [24] formulate the AP selection problem inwireless mesh networks as a nonlinear optimization programming, and apply a weighting parameter to obtain a tradeoff2between the total throughput and the max-min fairness. In [25],a two-stage smart association control protocol is proposed. Inthe bandwidth allocation stage, APs collaboratively determinethe number of devices they are going to associate for maxmin fairness; while in the AP association stage, devices areassigned to APs for throughput maximization. Bejerano etal. [6] and Xu et al. [26] demonstrate the strong correlationbetween throughput-based max-min fairness and min-max loadbalancing, and achieve the max-min fair bandwidth allocationvia AP association.Throughput based max-min fairness suffers from a lownetwork throughput in multi-rate WLANs [8], [11]. Proportional fairness, on the other hand, can effectively investigatethe tradeoff between fairness and network throughput [8],[11]. Li et al. [11] formulate a non-linear programming toachieve optimal proportional fairness in a network of APs, andpropose two approximate AP selection schemes, cvapPF andnlapPF, for periodic off-line optimization. Both cvapPF andnlapPF rely on relaxation and rounding to obtain an integraluser-AP association. Bu et al. [13] study the proportionalfairness problem in 3G wireless data networks. This studyis particularly suitable for 3G data networks and thereforeis not applicable to multi-rate WLANs. Koukoutsidis andSiris [27] propose a branch-and-bound algorithm to investigatethe network throughput under the max-min fairness and proportional fairness. But the time complexity of this algorithmis inversely proportional to the allowable relative error fromthe optimal solution, resulting in an unbounded performancein the worst case. Xie et al. [28] formulate the problem ofAP association control over vehicular networks as a convexprogramming in the offline setting, and design a dynamicweight-based online algorithm to achieve proportional fairness.Li et al. [29] jointly consider AP association and powercontrol, establish the relationship between the network utilityand the AP utility according to proportional fairness, and thendevise a centralized heuristic approach to optimize the networkutility by increasing the average and decreasing the varianceof the AP utility.In this paper, we propose two algorithms that jointlyconsider AP association and fair bandwidth allocation. Ourcentralized problem formulation is motivated by the non-linearprogramming in [11] but we adopt a completely differentapproach to relax the variables in our approximation algorithmdesign. By introducing a compensation function to the objective function to narrow down the gap caused by relaxation,we achieve an approximate solution that is at least half of theoptimal in the worst-case. Our second algorithm is distributed,which selects an AP for a newly-arriving user based on anovel performance revenue function to achieve proportionalfairness. Note that our centralized and distributed algorithmscan be combined to significantly improve the performance ofdynamic networks where users come and leave by their ownfree will.III. P ROPORTIONAL FAIRNESS AND N ETWORK M ODELIn this section, we first briefly introduce the formal definition of proportional fairness; then we detail our network modeland problem formulation.
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. , NO. , 2013A. Proportional FairnessTo fairly assign bandwidths to users while guaranteeingthe network performance in multi-rate WLANs, we adoptproportional fairness, a fairness criterion that was proposed byF. P. Kelly [8]. According to [8], proportional fairness can beformally defined as follows. Let bi be the effective bandwidthof user i and F (bi ) be the corresponding utility function.A vector of bandwidth assignment {b1 , b2 , . . . , bM }, with Mbeing the number of users in the network, is proportionallyfair if it is feasible and if for any other feasible vector{b 1 , b 2 , · · · , b M }, the aggregate of proportional changes iseither zero or negative, i.e.,MXb biibii 1F 0 (bi )δbi 0.i 1From the definition of proportional fairness, we haveMXδbii 1bi 0,which can be rewritten asMXB. Network ModelOur network topology models an IEEE 802.11 based multirate WLAN that consists of multiple APs operating at thesame channel. Each AP has the same limited coverage areaand serves users in its area. Overlapping coverage areas ofadjacent APs may exist. The union of the coverage areas of allAPs forms the network coverage area. We assume that eachAP transmits messages with the same power as defined byIEEE 802.11. We further assume that each user is covered byat least one AP, and each AP has at least one associated user.The notations and definitions to be utilized are summarized inTABLE I.TABLE IN OTATIONS 0.Consider a small feasible perturbation bi bi δbi , whichincreases the utility function F (bi ) providing thatMX3(log(bi ))0 δbi he set of all access points (APs)The set of APs associated with user iN A , the number of APsThe set of all usersM U , the number of usersThe SINR of the link from AP j to user iThe channel gain from AP j to user iThe transmit power of AP jThe receiver noise powerThe weight (priority) of user i, wi 0The effective bandwidth allocated to user iThe bit rate between user i and AP jThe association coefficient between user i and AP jThe 0-1 user-AP association matrix {xij }The effective transmission time between user i and AP jThe transmission time allocation matrix {tij }i 1Thus it follows that the above proportionally fair bandwidthallocation can be represented by a local maximum of thelogarithmic utility function. Since the logarithmic function isdifferentiable and strictly concave, it has only one maximumand therefore the local maximum is also the global maximum [8]. Accordingly, the objective of a proportionally fairbandwidth allocation can be expressed bymaxMXAs we have known, a user in an overlapping coverage areais typically serviced by one AP and interfered with all otherAPs. The effective bit rate of a user in an 802.11 networkis determined by the experienced SINR of the user. Moreprecisely, let γij denote the SINR of user i when associatedwith AP j. We have,g pP ij jγij ,(1)gik pk N0k Ai k6 jlog(bi ).i 1To quantitatively evaluate the fairness degree of our bandwidth allocation, we adopt Jain’s Fairness Index [30], whichstates that if a system allocates resources (bandwidths in ourcase) to M users, with the ith user receiving an allocation bi ,the fairness index of the system is defined to bePM( i 1 bi )2J , where bi 0.PMM i 1 b2iThis index measures the “equality” of users’ resource allocation {b1 , b2 , . . . , bM }. If all users obtain the same amountof the bandwidth, i.e., all bi ’s are equal, the fairness indexis 1 and the system is 100% fair. As the disparity increases,fairness decreases. An allocation scheme which favors only afew users has a fairness index close to 0.where gij is the channel gain from AP j to user i, pj isthe transmit power of AP j, N0 is the additive Gaussianwhite noise, and Ai is the set of APs whose transmissionsinterfere with user i. Note that here we choose to focuson downlink because the data transmissions from the APsrepresent the dominate traffic for many real-world applicationssuch as social networks [31], [32]. The relationship betweenthe effective bit rates and the SINR ranges in an 802.11network is shown in TABLE II [33], [34].TABLE IIT HE R ELATIONSHIP B ETWEEN SINR S AND E FFECTIVE B IT R ATES INIEEE 802.11 S TANDARDγij (dB) 6-7.8rij (Mbps)67.8-999-10.8 10.8-17 17-18.8 18.8-24 24-24.6 24.6121824364854It is assumed that the network is saturated such that all APsare busy all the time to send data to users. A unit of time, in
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. , NO. , 20134which the network is stable, with no new user joins and nocurrent user leaves, is to be considered. This means that underour consideration the total transmission time of an AP is equalto 1. Each AP assigns fractional transmission times to usersin accordance with proportional fairness. A user is allowed tochoose one and only one AP within a unit time.We formulate the problem of AP association based onproportional fairness as a non-linear programming. Our goal isto construct an assignment of users to APs in a proportionalmanner; i.e., the assignment allocates each user a sufficientamount of bandwidth without unduly restricting the amountof bandwidth available to others. In our system model, theresources at all APs are considered as a whole when allocatingbandwidth fairly to users. With this network-wide fairnessobjective, load balancing is automatically taken into account.NPSince the effective bandwidth of user i is bi xij tij rij ,j 1we obtain the following optimization formulation:maxMXi 1s.t.NXNXwi log(xij tij rij )(2a)j 1xij 1, 1 i M,(2b)xij tij 1, 1 j N,(2c)j 1MXi 1xij {0, 1}, 1 i M, 1 j N,tij [0, 1], 1 i M, 1 j N.(2d)(2e)Eq. (2) is referred as a Non-linear Programming problem(NLP). Note that our objective function (2a) considers theweights of the users, which reflects their priorities in a realnetwork. The constraint (2b) indicates that each user canassociate with one and only one AP; the constraint (2c)requires that the total transmission time of each AP j isequal to 1; the constraint (2d) assures that xij is a binaryvariable that is equal to 1 if and only if user i associatesto AP j; and the constraint (2e) specifies the range of thevariable tij . We can prove that NLP is NP-hard by slightlyadapting the reduction procedure proposed in [13]. Note thatthis problem formulation is motivated by [11] but our approachto solving the problem via relaxation, as elaborated in SectionIV, is fundamentally different and completely novel. Alsonote that the joint problem of AP association and bandwidthallocation expressed by (2) is formulated based on time-basedproportional fairness, given the bit rates between users andAPs.IV. T HE NLAO-PF A LGORITHMAlgorithm 1 NLAO-PF1: Obtain {t0ij } by solving r-NLP.2: Get the fractional solution {x0ij } by solving c-NLP.3: Get the integral solution {xij } by a rounding process.4: Redistribute transmission time to obtain {tij } and calculate {bi }.Since NLP is NP-hard, we propose an approximationalgorithm termed NLAO-PF, which stands for Non-LinearApproximation Optimization for Proportional Fairness, to simplify the issue and improve the degree of approximation. Thesteps of NLAO-PF are outlined in Alg. 1.The basic idea of NLAO-PF is to relax the binary variablexij such that each user is allowed to associate with multipleAPs within a unit time, i.e., xij can be fractional. Actuallywe further relax xij to the extent that any user is allowedto freely associate with all APs by setting xij 1 at thefirst step. Under such a relaxed condition, we compute theoptimal transmission time t0ij by solving a relaxed optimizationproblem (Section IV-A). Taking t0ij as a known parameter, weobtain x0ij , the fractional user-AP association coefficient, bysolving a complemented optimization problem (Section IV-B).A rounding technique is then applied to x0ij to obtain an approximate integral solution of xij (Section IV-C). Based on thenewly obtained xij , the transmission time t0ij is redistributedfor the original NLP problem (Section IV-D).The relaxation involved in NLAO-PF may result in a largeintegrality gap [35]. To overcome this problem, we modify theobjective function of NLP by adding a compensation functiong(X,T) in NLAO-PF, which is defined as follows:Definition 1: The compensation of user i on AP j is definedby wi xij tij log(rij ) if rij 1; and 0 otherwise. Thus thecompensation of user i to all APs can be expressed byNPwixij tij log(rij ). Therefore, the compensation functionj 1g(X, T ) can be defined correspondingly as follows:g(X, T ) MXi 1wiNXxij tij log(rij ).(3)j 1This compensation function is introduced to improve thelower bound of our algorithm to effectively narrow down theintegrality gap caused by relaxation. The steps of NLAO-PFare detailed in the following subsections.A. Relaxed Optimization ProgramThe first step of NLAO-PF is to solve the following relaxedoptimization problem, denoted by r-NLP, to obtain an optimal{t0ij }.maxMXNMNXXXwi log(t0ij rij ) wit0ij log(rij ) (4a)i 1s.t.NXj 1i 1j 1t0ij 1, 1 i M,(4b)t0ij 1, 1 j N,(4c)j 1MXi 1t0ij [0, 1], 1 i M, 1 j N.(4d)t0ij ,Compared with (2), r-NLP replaces tij bysets xij 1,and includes the compensation function in its objective function. The constraint (4b) indicates that the total transmissiontime of user i with all APs cannot surpass 1; the constraint(4c) requires that the total transmission time of each AP is
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. , NO. , 20135equal to 1, which means that all APs are saturated in the unittime; and the constraint (4d) defines the range of the variablet0ij . Obviously, the optimal solution for {t0ij } from (4) can becomputed in polynomial time [11].B. Fractional AssociationAfter solving r-NLP, we obtain the transmission time {t0ij }.Now we take {t0ij } as a known input, and get the fractionaluser-AP association {x0ij }. Because of the requirements forsolving convex programs, we change the linear equality constraint of NLP to a linear inequality constraint in the followingcomplemented Non-linear Programming (c-NLP) formulation,which does not change the solution value.maxMXNMNXXXwi log(x0ij t0ij rij ) wix0ij t0ij log(rij )i 1j 1i 1j 1(5a)s.t.NXx0ij 0, 1 i M,(5b)j 1MXwe fix the time allocation {t0ij } and replace the fractionalassociation {x0ij } by a 0-1 variable {xij } that encodes thedesired association of users to APs. The rounding processcontains two main steps: bipartite graph construction andmaximum-profit matching, which are detailed as follows.First, we construct a bipartite graph G(x) (U, V, E),where the set U represents the users in the network, andthe set V {vjk : j 1, 2, . . . , N, k 1, 2, . . . , Qj },MPwith Qj d x0ij e. This implies that each AP may havei 1multiple nodes in V . The edges in G(x) are constructedaccording to the following method. If Qj 1, there is onlyone node vj1 corresponding to AP j. For each x0ij 0, addedge e(ui , vj1 ) and set x0 (ui , vj1 ) x0ij , where x0 (e) is thefractional association weight of the corresponding user and AP.ikPOtherwise, find the minimum index ik such thatx0ij k.i 1For i ik 1 1, . . . , ik 1 and x0ij 0, add edgee(ui , vjk )and set x0 (ui , vjk ) x0ij . For i ik , add edge e(ui , vjk )ikikP 1Px0 (ui , vjk ). Ifx0ij k,and set x0 (ui , vjk ) 1 i ik 1 1x0ij t0ij 1, 1 j N,(5c)x0ij 0, 1 i M, 1 j N.(5d)add edge e(ui , vj(k 1) ) and set x0 (ui , vj(k 1) ) i 1ikPi 1i 1The objective function of c-NLP is designed to approximatethe optimal solution to NLP. The constraint (5b) indicates thata user should connect with at least one AP; the constraint(5c) forces the total transmission time of each AP be equalto 1; and the constraint (5d) defines the range of x0ij for thecase of fractional association. Note that here we take {t0ij }obtained from (4) as the input to c-NLP and obtain the optimalassociation {x0ij } for c-NLP given {t0ij }.We can prove that the gap introduced by our relaxation proMNPPcedure is bounded. Let f (X, T ) wi log(xij tij rij ),i 1j 1and h(X, T ) f (X, T ) g(X, T ). Then the objectivefunctions of r-NLP and c-NLP become h(X 1, T ) andh(X, T ), respectively. Correspondingly, h(X 1, T 0 ) andh(X 0 , T 0 ) are the solutions obtained from r-NLP and c-NLP,respectively.Theorem 1: Let (X , T ) and (X 0 , T 0 ) be the optimal solutions to NLP and to c-NLP, respectively. Then f (X , T ) h(X 0 , T 0 ) 2f (X , T ).MPx0ij t0ij 1 (constraint (5c)) and rij 1,Proof: Withi 1f (X 0 , T 0 ) g(X 0 , T 0 ) 0. Thus, h(X 0 , T 0 ) 2f (X 0 , T 0 ) 2f (X , T ). Since (X 1, T ) is a feasible solution of theproblem r-NLP and (X 1, T 0 ) is the optimal solution ofr-NLP, we have f (X , T ) f (X 1, T ) f (X 1, T ) g(X 1, T ) h(X 1, T ) h(X 1, T 0 ) h(X 0 , T 0 ), where the last inequality holds from the fact thath(X 1, T 0 ) is feasible to c-NLP.C. RoundingIn this step, we use the rounding algorithm proposed in[36] to obtain an integral association matrix X. That is,x0ij k.Obviously, x0 (e) has the following property:(ikX 1, k 1, 2, . . . , Qj 1,0x (ui , vjk ) 1, k Qj .i i 1k 1This implies that the sum of the fractional association weightson each node vjk does not exceed one. The profit of each edgee(ui , vjk ) in E is defined to be wi log(t0ij rij ).Second, we find a maximum-profit matching M (x) thatmatches each user node with an AP node in G(x). For eachedge e(ui , vjk ) in M (x), schedule user i to AP j and setxij 1. Set other xij ’s to be 0. Since the fractional association {x0ij } specifies a fractional matching, such a maximalmatching does exist and it determines the integral association{xij }. More details can be found in [36].Note that {t0ij } and {x0ij } are computed from r-NLP and cNLP, respectively. The rounding scheme constructs an integralassignment {xij }. We denote this solution by f (X a , T 0 ),which is also feasible to NLP. Then we have,Theorem 2: f (X a , T 0 ) 21 f (X , T ).Proof: Note that {xij } is obtained by employing therounding scheme proposed by Shmoys and Tardos in [36],which proves the following property: f (X a , T 0 ) f (X 0 , T 0 ).Thus, f (X a , T 0 ) f (X 0 , T 0 ) 21 [f (X 0 , T 0 ) g(X 0 , T 0 )] 1100 2 h(X , T ) 2 f (X , T ), where the last inequality holdsfrom Theorem 1.We use an example to demonstrate the rounding process.Suppose that there exist three users and two APs and that wehave obtained the following fractional AP association after thesecond step of Alg. 1: x011 1, x022 1, x031 12 12 . Thecorresponding bipartite graph is illustrated in Fig. 1, wherex0ij 1 for solid edges, x0ij 21 for dashed edges, and thenumbers beside the edges are their profits. More specifically,Q1 Q2 2; that is, each AP has two nodes in thebipartite graph. Then, the maximum-profit matching yields
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. , NO. , 20136x11 x22 x31 1 with a total profit of 2.7, which islarger than the fractional association profit 2.5.The solution obtained from our algorithm NLAO-PF canbe denoted as f (X a , T a ). Based on Theorems 2 and 3, wehave f (X a , T a ) f (X a , T 0 ) 21 f (X , T ). That is, theapproximate solution obtained from NLAO-PF is no less thanhalf of the optimal solution of NLP.V. T HE BPF A LGORITHMFig. 1.An Example of Rounding ProcessD. Transmission Time RedistributionSince the user-AP association changes after rounding, weneed to redistribute the transmission times. This is the last stepof NLAO-PF, in which we assign transmission times to usersaccording to proportional fairness.Theorem 3: Let {xij } be the integral user-AP associationcoefficients obtained from the rounding procedure outlined inSection IV-C. Given {xij }, the unique optimal transmissiontime assigned to user i by AP j according to proportionalfairness iswi xij.(6)tij MPwk xkjk 1Proof: (a) First, we consider the case of a single AP.Assume that the number of users covered by the AP is m.Since the objective function of (2) is the sum of logarithms,maximizing the total utility of the user bandwidth (2) isequivalent to maximizing (7):MY(tij rij )wi i 1MYi 1(ti1 ri1 )wi MY(ti1 )wii 1MY(ri1 )wi .Note that without collecting the network-wide informationa user is only aware of the changes of its currently associatedAP, including the join of a new user and the leave of a currentuser. This implies that it is impossible for a user to switch toan AP whose associated users leave the network. On the otherhand, a user’s utility can be increased if other users associatedwith the same AP leave the network, thus this user has noincentive to leave its currently associated AP. As shown in(6), within one unit of transmission time, the portion assignedto each user is proportional to its weight divided by the totalweights of all users associated with the same AP. Therefore,re-allocating the optimal transmission time when current usersleave from the network on each AP is trivial. Thus in thissection, we focus on the case when a user intends to join thenetwork, i.e., how to select the best AP for a new user.(7)i 1Note that {ri1 } is the set of optimization constants. Therefore maximizing (7) is equivalent to maximizing (8):MYIn this section, we present a distributed algorithm namedBest Performance First (BPF) for AP association to supportproportional fairness in dynamic network scenarios.A. BPF AlgorighmAccording to IEEE 802.11, by default a new user selects(ti1 )wi (t11 t11 · · · t11 )(t21 t21 · · ·
between throughput-based max-min fairness and min-max load balancing, and achieve the max-min fair bandwidth allocation via AP association. Throughput based max-min fairness suffers from a low network throughput in multi-rate WLANs [8], [11]. Propor-tional fairness, on the other hand, can effectively investigate
