W2(t)=W3(t),...,finally we can achieve Wi(t)=W2(t)= propose a group-based approach that partitions the network ..=Wn(t).From then on,all users will share the bandwidth into groups.In each group,we apply the aforementioned LP distribution and keep Wi(t)=W2(t)=...=Wn(t),in this method so that the computation complexity will be reduced. way each user j further gets the bandwidth from the AP with In the rest of this section,as we only focus on the snapshot proporion In order to obtain mine()dt). solution,for the ease of presentation,we omit the "(t)"for we further assume that user n has the minimum service snapshot parameters in the formulas.Next,we give a formal duration T=minje(T),thus among all users jU definition of"group". user n obtains the least bandwidth. Definition 1.We say that a set of users belong to the same We denote the time interval [0,t*]during which user n group if and only if for any two users j'and j from the set. gets no bandwidth and [t,Tn]during which user n shares there is a series of users j1,j2,..j from the set such that the AP's bandwidth distribution.Thus during the interval A;∩Ai1≠p,A1∩Ai2≠p,,Aj.∩A≠o,where A, [0,t*],the total downloaded bits for user 1....,n-1 is is user j's candidate AP set. b(t)dt.As the minimum bit rate is rmin.we According to this definition,different groups are mutually obtain t*≤ 点∑gb,因d进At the time point,as exclusive (each user can only belong to one unique group)and Wi(t")=W2(=Wa(),according to the definition independent (users belonging to different groups will have no of Wi(t),we have shared candidate APs for contention).For any snapshot,the users over the roads can be divided into one or more groups. Wi i=1,2.,n-1, Wn Therefore our association control over all users is reduced to e+。5)成 association control within each group inferred by Theorem 5. Theorem 5:For snapshot solution of the efficiency metric Thus we getfb (t)dt=(-1)e,and further more and online solution of the fairness metric,the optimization achieved within each group is consistent with the overall 18) optimization. Tmin Wn jEU Due to lack of space,we omit the proof of Theorem 5. Now according to Eq.(18)we can estimate the minimum As we have learned from Section IV,both snapshot solution accumulated bandwidth among the users for efficiency and online solution for fairness can be unified in the formulation as to maximize Wjb for each bj(t)dt)>(Tn-t*). WnTmin snapshot.Here for efficiency,we have Wi=wj/Tj:and for ∑jeU proportional fairness,we have W WnTmin m()+( n·n -1)e 之jeU0 A.Breaking into Smaller Sub-Groups In a dense traffic scenario,the distance between adjacent Then according to Eq.(17),if we set p n:minjeU上，we users may be close to share some candidate APs,thus we have cannot divide them into separate groups.Hence we may still have extremely large-sized groups over the roads.In order to R≤∑wm7 e+rmarTmaz (p-1)e+prminTmin/n reduce the computation complexity,we need to break the large groups into smaller sub-groups.Therefore before we conduct Here since e is an adjustable parameter,it is possible to optimization with the linear program based method,we first determine an optimal value for e to minimize the bound.As perform pre-processing.For each user j,we delete those weak p≤l,when e→0，we can achieve the minimum value for links (i,j)with bit rate rij low enough to satisfy ri.j< R's upper bound as∑jeU西lh(am于·）】 ■ BjmaxieA,ri.j.Here,maxieA,ri.j is the maximum bit rate that user j can achieve within its candidate AP set Aj,and V.GROUP-BASED APPROACH The above proposed snapshot solution as well as the online 马={ algorithm solution both require continuously solving a linear If ci< (19) program for each snapshot.The computation complexity may where i*is the specific AP with the maximum bit rate,ci is be huge in our considered scenario,where we have to deal the number of users within AP i*'s effective range,and y >1 with an extremely large Wi-Fi deployment.For example, is a constant parameter.Wheny=1,the intuition is that according to polynomial-time algorithms for linear program from user j's perspective,even choosing i'as its own AP with like the ellipsoid method[17],the computation complexity is no contention is worse than contending for i*with ci users, O(N4.L).where N is the number of parameters and L is the so it is too weak to worth association.We use the constant length of encoding bits for parameters.For our optimization parameter y to control the effect for weak link eliminations. problems,we have N =m.n for all parameters pi.j,(m Actually the larger y is,the greater number of links will be is the number of APs and n is the number of users).Thus, deleted.Thus we are able to break a large group into more sub- if n and m are large enough,N will be a huge number and groups.After deleting these weak links,we check the bipartite the computation complexity will be tremendous.Hereby we graph G(V,E)of AP-user links corresponding to the original 330 Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore.Restrictions apply.W2(t) = W3(t), ..., finally we can achieve W1(t) = W2(t) = ... = Wn(t). From then on, all users will share the bandwidth distribution and keep W1(t) = W2(t) = ... = Wn(t), in this way each user j further gets the bandwidth from the AP with proportion wj j∈U wj . In order to obtain minj∈U ( T 0 bj(t)dt), we further assume that user n has the minimum service duration Tn = minj∈U (Tj ), thus among all users j ∈ U user n obtains the least bandwidth. We denote the time interval [0, t∗] during which user n gets no bandwidth and [t ∗, Tn] during which user n shares the AP’s bandwidth distribution. Thus during the interval [0, t∗], the total downloaded bits for user 1, ..., n − 1 is n−1 j=1 t∗ 0 bj(t)dt. As the minimum bit rate is rmin, we obtain t∗ ≤ 1 rmin n−1 j=1 t∗ 0 bj(t)dt. At the time point t∗, as W1(t∗) = W2(t∗) = ... = Wn(t∗), according to the definition of Wj (t), we have ∀j = 1, 2..., n − 1, wj + t∗ 0 bj (t)dt = wn . Thus we get t∗ 0 bj(t)dt = ( wj wn − 1), and further more t ∗ ≤ rmin ( 1 wn  j∈U wj − n). (18) Now according to Eq. (18) we can estimate the minimum accumulated bandwidth among the users min j∈U (  T 0 bj(t)dt) ≥ (Tn − t ∗) · wnrmin j∈U wj ≥ wnrmin j∈U wj min j∈U (Tj )+( wn · n j∈U wj − 1). Then according to Eq. (17), if we set ρ = n· minj∈U wj j∈U wj , we have R ≤  j∈U wj · ln[ + rmaxTmax (ρ − 1) + ρrminTmin/n]. Here since is an adjustable parameter, it is possible to determine an optimal value for to minimize the bound. As ρ ≤ 1, when → 0, we can achieve the minimum value for R’s upper bound as j∈U wj · ln( rmaxTmax rminTmin · n ρ ). V. GROUP-BASED APPROACH The above proposed snapshot solution as well as the online algorithm solution both require continuously solving a linear program for each snapshot. The computation complexity may be huge in our considered scenario, where we have to deal with an extremely large Wi-Fi deployment. For example, according to polynomial-time algorithms for linear program like the ellipsoid method[17], the computation complexity is O(N4 ·L), where N is the number of parameters and L is the length of encoding bits for parameters. For our optimization problems, we have N = m · n for all parameters pi,j , (m is the number of APs and n is the number of users). Thus, if n and m are large enough, N will be a huge number and the computation complexity will be tremendous. Hereby we propose a group-based approach that partitions the network into groups. In each group, we apply the aforementioned LP method so that the computation complexity will be reduced. In the rest of this section, as we only focus on the snapshot solution, for the ease of presentation, we omit the “(t)” for snapshot parameters in the formulas. Next, we give a formal definition of “group”. Definition 1. We say that a set of users belong to the same group if and only if for any two users j and j from the set, there is a series of users j1, j2, ..., js from the set such that Aj  Aj1 = φ, Aj1  Aj2 = φ, ..., Ajs  Aj = φ, where Aj is user j’s candidate AP set. According to this definition, different groups are mutually exclusive (each user can only belong to one unique group) and independent (users belonging to different groups will have no shared candidate APs for contention). For any snapshot, the users over the roads can be divided into one or more groups. Therefore our association control over all users is reduced to association control within each group inferred by Theorem 5. Theorem 5: For snapshot solution of the efficiency metric and online solution of the fairness metric, the optimization achieved within each group is consistent with the overall optimization. Due to lack of space, we omit the proof of Theorem 5. As we have learned from Section IV, both snapshot solution for efficiency and online solution for fairness can be unified in the formulation as to maximize j∈U Wj · bj for each snapshot. Here for efficiency, we have Wj = wj/Tj; and for proportional fairness, we have Wj = wj + t 0 bj (t)dt . A. Breaking into Smaller Sub-Groups In a dense traffic scenario, the distance between adjacent users may be close to share some candidate APs, thus we cannot divide them into separate groups. Hence we may still have extremely large-sized groups over the roads. In order to reduce the computation complexity, we need to break the large groups into smaller sub-groups. Therefore before we conduct optimization with the linear program based method, we first perform pre-processing. For each user j, we delete those weak links (i , j) with bit rate ri ,j low enough to satisfy ri ,j < βj · maxi∈Aj ri,j . Here, maxi∈Aj ri,j is the maximum bit rate that user j can achieve within its candidate AP set Aj , and βj =  γ/ci∗ If ci∗ ≥ γ 1 If ci∗ < γ (19) where i ∗ is the specific AP with the maximum bit rate, ci∗ is the number of users within AP i ∗’s effective range, and γ ≥ 1 is a constant parameter. When γ = 1, the intuition is that from user j’s perspective, even choosing i as its own AP with no contention is worse than contending for i ∗ with ci∗ users, so it is too weak to worth association. We use the constant parameter γ to control the effect for weak link eliminations. Actually the larger γ is, the greater number of links will be deleted. Thus we are able to break a large group into more sub￾groups. After deleting these weak links, we check the bipartite graph G(V,E) of AP-user links corresponding to the original 330 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore. Restrictions apply.