case(3)we prove by contradiction that new association control The constraints for bi(t)in(10)-(13)is similar to the formu- is not necessary.We denote the former equivalence class as lations of constraints for bi(t)in (4)-(7).the only difference Eqi and the new equivalence class as Egi.Assume in Eqi is we use the time interval t instead of snapshot t to depict some user will switch to a different AP for a new optimal the parameters in the constraints.The fractional solution of solution.Thus we can use new bandwidth allocation b,(t) Pij(t)for each bj(t)is the exact solution for association for users to improve the objective function(t) control in the lth interval for l=1,..,L,as we allow multiple (t).As only one original candidate AP is lost for handoffs within each interval to achieve the fractional solution. some user in Eqi,each user's candidate AP set for Egj is a Assume within any time interval[t,],there are K phases subset or equivalent set of the one for Egi.So we can apply of association control as AC1,AC2,...,ACK.In each phase this new solution to Egi,so as to further improve the objective ACk,for k =1,...,K,any user can associate with one unique function,but that contradicts with the fact that we already have AP as the integral solution.Hence we can utilize an integer optimal solution for Eqi.Thus the assumption does not hold. linear program (ILP)to figure out the optimized handoff the theorem gets proved. ■ strategies.Due to lack of space,we omit the ILP formulation According to Theorem 2,for the efficiency metric we only and the detail procedure to calculate the handoff strategies. have to compute the optimized association solution each time when one or more users cross the boundary of Eguivalence C.Online Algorithm for Proportional Fairness Classes.We can further prevent unnecessary computations by checking the special patterns of adjacent Equivalence Classes. From the above subsection we know that the exact optimal solution can only be achieved with information obtained over B.Offline Optimization for Proportional Fairness the whole time span (0,T)in advance.However,in practice In the above subsection we have demonstrated that for we cannot precisely know users'future mobility trajectory, the efficiency metric we can transform the long-term overall thus no information about which users will be contending for optimization into the snapshot optimization.However,for specified APs in the future can be obtained beforehand.In this proportional fairness,as each snapshot decision for the optimal subsection,according to the online setting described in Section solution may depend on its former and future situations.we III,we design an online algorithm.Our solution relies on the cannot simply conduct this transformation. following theorem. As illustrated in Fig.3,within each refined time interval Theorem 3:Maximizing the long-term objective function ]for I=1..L.the candidate AP sets and corre-((t)dt)is consistent with maximizing sponding bit rates for all users are fixed.We can devise a fixed pattern of association solution in an optimized approach. the long-term objective function(dt. Following the offline setting described in Section III,and Here.(t)dt denotes the accumulated bandwidth in time using the detailed information over the time span [0,T] span 0,t,w;denotes the original fixed weight as priority for given in advance,we devise an offline algorithm to achieve each user j,and e>0 is a small constant number. optimization for proportional fairness.Here we use bj.t to Proof:Using the fact that T is constant and settingj= denote the average bandwidth allocated in the time interval e+obj(t)dt,we have [ti_1,ti].and we define t=t-t1 for I 1,...,L.So we haveB).Since the objective is to 四b(t) dt wjbi(t) maximize iewj In Bj,we have e元e+6b(t)dt e+bj(t)dt L 7 Wj ∑wlnB,=∑wln(∑bt)-∑w;lhT d(e+ bj(t)dt) e+b(t)dt iEU jEU I=1 iEU re+j。bg(t)dt AsT is constant we can set the objective w1d） function as )Then we obtain the j following convex program formulation: =∑四nx,l+B6d marimize∑w,ln(∑b.l·t) jeU (9) l=0 ∑wn(e+ bi(t)dt)- (14) subject to jEU 5∈U,l∈{L,,Lb.1=∑r0p,(0 (10) iEA As e is constant,maximizing(14)is equivalent to maximizing i∈A,1∈{1，，L} ∑∑p,()≤1 (11) wj In(e+ bj(t)dt). (1 i∈U,le{1,,L} p5,(0≤1 (12) jEU 164 i∈A,1∈U,l∈{1，，L0≤p:,()≤1 (13) The theorem gets proved. 328 Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore.Restrictions apply.case (3) we prove by contradiction that new association control is not necessary. We denote the former equivalence class as Eqi and the new equivalence class as Eqj . Assume in Eqj some user will switch to a different AP for a new optimal solution. Thus we can use new bandwidth allocation b j (t) for users to improve the objective function j∈U wj Tj b j (t) > j∈U wj Tj bj(t). As only one original candidate AP is lost for some user in Eqj , each user’s candidate AP set for Eqj is a subset or equivalent set of the one for Eqi. So we can apply this new solution to Eqi, so as to further improve the objective function, but that contradicts with the fact that we already have optimal solution for Eqi. Thus the assumption does not hold, the theorem gets proved. According to Theorem 2, for the efficiency metric we only have to compute the optimized association solution each time when one or more users cross the boundary of Equivalence Classes. We can further prevent unnecessary computations by checking the special patterns of adjacent Equivalence Classes. B. Offline Optimization for Proportional Fairness In the above subsection we have demonstrated that for the efficiency metric we can transform the long-term overall optimization into the snapshot optimization. However, for proportional fairness, as each snapshot decision for the optimal solution may depend on its former and future situations, we cannot simply conduct this transformation. As illustrated in Fig. 3, within each refined time interval [t l−1, t l] for l = 1, ..., L, the candidate AP sets and corre￾sponding bit rates for all users are fixed. We can devise a fixed pattern of association solution in an optimized approach. Following the offline setting described in Section III, and using the detailed information over the time span [0, T ] given in advance, we devise an offline algorithm to achieve optimization for proportional fairness. Here we use bj,l to denote the average bandwidth allocated in the time interval [t l−1, t l], and we define tl = t l − t l−1 for l = 1, ..., L. So we have Bj = 1 Tj L l=1 (bj,l · tl). Since the objective is to maximize j∈U wj ln Bj , we have  j∈U wj ln Bj =  j∈U wj ln( L l=1 bj,l · tl) −  j∈U wj ln Tj . As − j∈U wj ln Tj is constant, we can set the objective function as j∈U wj ln(L l=0 bj,l · tl). Then we obtain the following convex program formulation: maximize j∈U wj ln(L l=0 bj,l · tl) (9) subject to ∀j ∈ U, l ∈ {1, ..., L} bj,l =  i∈A ri,j (l) · pi,j (l) (10) ∀i ∈ A, l ∈ {1, ..., L}  j∈U pi,j (l) ≤ 1 (11) ∀j ∈ U, l ∈ {1, ..., L}  i∈A pi,j (l) ≤ 1 (12) ∀i ∈ A, j ∈ U, l ∈ {1, ..., L} 0 ≤ pi,j (l) ≤ 1 (13) The constraints for bj(tl) in (10)-(13) is similar to the formu￾lations of constraints for bj(t) in (4)-(7), the only difference is we use the time interval tl instead of snapshot t to depict the parameters in the constraints. The fractional solution of pi,j (tl) for each bj(tl) is the exact solution for association control in the lth interval for l = 1, .., L, as we allow multiple handoffs within each interval to achieve the fractional solution. Assume within any time interval [t l−1, t l], there are K phases of association control as AC1, AC2, ..., ACK. In each phase ACk, for k = 1, ..., K, any user can associate with one unique AP as the integral solution. Hence we can utilize an integer linear program (ILP) to figure out the optimized handoff strategies. Due to lack of space, we omit the ILP formulation and the detail procedure to calculate the handoff strategies. C. Online Algorithm for Proportional Fairness From the above subsection we know that the exact optimal solution can only be achieved with information obtained over the whole time span (0, T ) in advance. However, in practice we cannot precisely know users’ future mobility trajectory, thus no information about which users will be contending for specified APs in the future can be obtained beforehand. In this subsection, according to the online setting described in Section III, we design an online algorithm. Our solution relies on the following theorem. Theorem 3: Maximizing the long-term objective function j∈U wj ln( + T 0 bj (t)dt) is consistent with maximizing the long-term objective function T 0 j∈U wj + t 0 bj (t)dt bj(t)dt. Here, t 0 bj (t)dt denotes the accumulated bandwidth in time span [0, t], wj denotes the original fixed weight as priority for each user j, and > 0 is a small constant number. Proof: Using the fact that T is constant and setting xj = + t 0 bj (t)dt, we have  T 0  j∈U wj bj (t) + t 0 bj (t)dt dt =  j∈U  T 0 wj bj(t) + t 0 bj(t)dt dt =  j∈U  T 0 wj + t 0 bj(t)dt d( +  t 0 bj(t)dt) =  j∈U  + T 0 bj (t)dt wj xj d(xj ) =  j∈U wj ln xj | + T 0 bj (t)dt =  j∈U wj ln( +  T 0 bj (t)dt) −  j∈U wj ln . (14) As is constant, maximizing (14) is equivalent to maximizing  j∈U wj ln( +  T 0 bj (t)dt). (15) The theorem gets proved. 328 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore. Restrictions apply.