Recall that the original long-term goal is to maximize of Bj,we can further obtain T bj(t)dt) (16) R= )t-∑西l血 bi(t)dt. o o The only difference between the above two objective functions Theorem 4:The upper bound of R=jeu wjIn Bj- (15)and (16)is e,which may have an impact on the corre- CjeU Wj In Bj for DWOA is sponding optimal solution.However,as long as we set e small enough (0)in (15),the long-term goal in (15)becomes wj.In(maz Tmaz. jEU TminImin 0 very near toe((t)dt). In order to maximize fod D时 where p nminjeu w,Tmin =minjeu(Tj),Tmar= ∑e0" we use the following heuristic snapshot objective fo maxjeU(Tj).rmin is the minimum value of bit rate,and rma ∑jeue+元，odb,(）along with the constraint depicted in 2， is the maximum value of bit rate. (4)-(8)to approximate the long-term optimization solution. Proof:Since DWOA attempts to maximize The intuition is that maximizing fo at each t contributes to Cjev wj In(e+(t)dt),we first define R(e)= the maximization of fo.We thus propose an online algorithm ju四ln(e+6t)d)-∑jeu四n(e+b,()d). DWOA based on dynamic weight W3(t)( We then have Since it is possible that bj(t)dt =0.we let e>0 to prevent Wi(t)from equal to +o0.This online algorithm is Rg=∑四，n+0d illustrated in Algorithm 1.Here Step 1 takes care of the +(t)dt fairness metric by setting Wi(t)inversely proportional to As()dt ≤ Tmar·rmaz and(t)dt≥ the accumulated bandwidth.Step 2 considers the efficiency metric by attempting to maximize the sum of the weighted minje(b(t)dt),we have bandwidths.We update the association solution for every At time interval.Conventionally the less At we use,the better R(e≤∑w·ln( e+Tmax·Tmaz jEU e+minjeu(fbj(t)dt) solution we can obtain,but the drawback is that it may cause too many handoffs. Then according to the definitions of R and R(e),we have Algorithm 1 DWOA:Dynamic Weight based Online Algo- R-Re)=∑西lm 防)d)·(e+b;()) rithm jEU (e+())·(。b)d) 1:t=0 2:while t<T do +1) 3: Step1.For each user j.calculate W(t)(di ≤∑虜（间a J for snapshot at t. Therefore we obtain Step2.For snapshot at t,set the object function as to R≤∑wln( +1)+R(e) maximize iWi(t)bj(t),calculate and apply the jEU injeu(bj(t)dt) solution for association. Step3.t=t+At,go to Step 1. ≤∑w,ln(+mingeu, jEU minjev(b(t)dt) +∑yh( e+Tmaz'Tmar D.Performance Analysis of DWOA jEU e+minjev(bj(t)dt) Due to the mathematical complexity of our objective func- wj.In- e+Tmar·Tmaz (17) tion(Bj),we take the following steps to de- jEU nje((t)dt) fine a metric R to evaluate our online algorithm DWOA. First,realizing the equivalence of its maximization to that Now we need to estimate minje(b(t)dt)in Eq.(17). of∑ev wj(B,we useΠieu(B,m,as the objective We consider the worst case that all users are driving in a very function in the definition of R.Then similar to the approach close neighborhood,and so they are always contending for the used in [6],we define same APs.We assume for the n users w1>w2 >..Wn. According to the algorithm,for the optimal snapshot solution, R=In IIjev(Bj) =∑wlhB防-∑w血B each aP will only allocate bandwidth to the user with the j∈U jEU largest weight Wi(t)within its range.As Wi(t)is changing all the time,we adopt the following procedure:user 1 first Here B;and B;respectively denotes the overall optimal get all the bandwidth from the AP until Wi(t)=W2(t). solution and the online solution.According to the definition then user 1 and 2 will further get bandwidth until Wi(t)= 329 Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore.Restrictions apply.Recall that the original long-term goal is to maximize  j∈U wj ln( T 0 bj (t)dt). (16) The only difference between the above two objective functions (15) and (16) is , which may have an impact on the corre￾sponding optimal solution. However, as long as we set small enough ( → 0) in (15), the long-term goal in (15) becomes very near to j∈U wj ln( T 0 bj(t)dt). In order to maximize fO = T 0 j∈U wj + t 0 bj (t)dt bj (t)dt, we use the following heuristic snapshot objective f O = j∈U wj + t 0 bj (t)dt bj(t) along with the constraint depicted in (4)-(8) to approximate the long-term optimization solution. The intuition is that maximizing f O at each t contributes to the maximization of fO. We thus propose an online algorithm DWOA based on dynamic weight Wj (t) = wj + t 0 bj (t)dt . Since it is possible that t 0 bj(t)dt = 0, we let > 0 to prevent Wj (t) from equal to +∞. This online algorithm is illustrated in Algorithm 1. Here Step 1 takes care of the fairness metric by setting Wj (t) inversely proportional to the accumulated bandwidth. Step 2 considers the efficiency metric by attempting to maximize the sum of the weighted bandwidths. We update the association solution for every Δt time interval. Conventionally the less Δt we use, the better solution we can obtain, but the drawback is that it may cause too many handoffs. Algorithm 1 DWOA: Dynamic Weight based Online Algo￾rithm 1: t = 0 2: while t<T do 3: Step1. For each user j, calculate Wj (t) = wj + t 0 bj (t)dt for snapshot at t. 4: Step2. For snapshot at t, set the object function as to maximize j∈U Wj (t)bj (t), calculate and apply the solution for association. 5: Step3. t = t + Δt, go to Step 1. D. Performance Analysis of DWOA Due to the mathematical complexity of our objective func￾tion j∈U wj ln(Bj ), we take the following steps to de- fine a metric R to evaluate our online algorithm DWOA. First, realizing the equivalence of its maximization to that of j∈U wj ln(Bj ), we use  j∈U (Bj )wj as the objective function in the definition of R. Then similar to the approach used in [6], we define R = ln  j∈U (B∗ j )wj  j∈U (Bj )wj =  j∈U wj ln B∗ j −  j∈U wj ln Bj . Here B∗ j and Bj respectively denotes the overall optimal solution and the online solution. According to the definition of Bj , we can further obtain R =  j∈U wj ln  T 0 b∗ j (t)dt −  j∈U wj ln  T 0 bj (t)dt. Theorem 4: The upper bound of R = j∈U wj ln B∗ j − j∈U wj ln Bj for DWOA is  j∈U wj · ln( rmaxTmax rminTmin · n ρ ), where ρ = n· minj∈U wj j∈U wj , Tmin = minj∈U (Tj), Tmax = maxj∈U (Tj ), rmin is the minimum value of bit rate, and rmax is the maximum value of bit rate. Proof: Since DWOA attempts to maximize j∈U wj ln( + T 0 bj(t)dt), we first define R() = j∈U wj ln( + T 0 b∗ j (t)dt) − j∈U wj ln( + T 0 bj(t)dt). We then have R() =  j∈U wj ln( + T 0 b∗ j (t)dt + T 0 bj (t)dt). As T 0 b∗ j (t)dt ≤ Tmax · rmax and T 0 bj (t)dt ≥ minj∈U ( T 0 bj (t)dt), we have R() ≤  j∈U wj · ln( + Tmax · rmax + minj∈U ( T 0 bj (t)dt) ). Then according to the definitions of R and R(), we have R − R() =  j∈U wj ln(( T 0 b∗ j (t)dt) · ( + T 0 bj(t)dt) ( + T 0 b∗ j (t)dt) · ( T 0 bj(t)dt) ) ≤  j∈U wj ln( T 0 bj (t)dt + 1). Therefore we obtain R ≤  j∈U wj ln( minj∈U ( T 0 bj (t)dt) + 1) + R() ≤  j∈U wj · ln( + minj∈U ( T 0 bj(t)dt) minj∈U ( T 0 bj (t)dt) ) + j∈U wj · ln( + Tmax · rmax + minj∈U ( T 0 bj(t)dt) ) =  j∈U wj · ln + Tmax · rmax minj∈U ( T 0 bj (t)dt) . (17) Now we need to estimate minj∈U ( T 0 bj(t)dt) in Eq. (17). We consider the worst case that all users are driving in a very close neighborhood, and so they are always contending for the same APs. We assume for the n users w1 > w2 > ... > wn. According to the algorithm, for the optimal snapshot solution, each AP will only allocate bandwidth to the user with the largest weight Wj (t) within its range. As Wj (t) is changing all the time, we adopt the following procedure: user 1 first get all the bandwidth from the AP until W1(t) = W2(t), then user 1 and 2 will further get bandwidth until W1(t) = 329 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore. Restrictions apply.