XIE ET AL.:ASSOCIATION CONTROL FOR VEHICULAR WIFI ACCESS:PURSUING EFFICIENCY AND FAIRNESS 1327 Theorem 3.Maximizing the long-term objective function Algorithm 1 DWOA:Dynamic Weight based Online Algorithm (9 1:t=0 2:while t<T do 3: is consistent with maximizing the long-term objective function For each user j,calculate W(t)for snapshot at t. 世 4: For snapshot at t,set the object function as to j(t)dt. 0 e+bi(t)dt maximize Wj(t)(t),calculate and apply the solution for association. Here,b(t)dt denotes the accumulated bandwidth in time 5:t=t+△t. span 0,t,wj denotes the original fixed weight as priority for 6:end while each user j,and e>is a small constant number. 4.3 Online Algorithm for Max-Min Fairness The proof of Theorem 3 can be found in the supplemen- Since max-min fairness is also a frequently used metric for tary material,which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/ fairness,for completeness,in this section we consider the 10.1109/TPDS.2011.17.Recall that the original long-term approach to achieve long-term max-min fairness.The goal is to maximize intuition of max-min fairness for the Drive-thru Internet scenario is to maximize the throughput allocated to those bj(t)dt (10) users that receive the minimum throughput.As it has been proved by Bejerano et al.[4]that the problem of finding a max-min fair integral association is NP-hard,thus we The only difference between the above two objective functions (9)and (10)is e,which may have an impact on consider an online algorithm to approximately achieve the max-min fairness. the corresponding optimal solution.However,as long as we Assume at each snapshot t,each user j has his set e small enough (-0)in (9),the long-term goal in (9) becomes very near to jewj(b(t)dt). accumulated bandwidth obj(t)dt and current service In order to maximize duration Ti(t).We define a user j to be saturated when ∑CEAPiJ=1ori∈A,∑ieUP=1.In other words,,a user j is saturated only when j has used all his time fraction fo= bj(t)dt, 0 je+bj(t)dt to connect to APs or no remaining time fraction of his candidate APs can be further allocated to j.Algorithm 2 we use the following heuristic snapshot objective illustrates the online algorithm to achieve long-term max- f6)=∑ bj(t). min fairness.We update the association solution for every e+bj(t)dt At time interval.For each snapshot t,we sort the users according to nondecreasing order of along with the constraint depicted in (4)-(8)to approx- imate the long-term optimization solution.The intuition is that maximizing fo(t)at each t contributes to the 当s马h maximization of fo.We thus propose an algorithm based 四5·T(t) on the dynamic weight which is the current allocated throughput normalized by W(t)= 世方 the weight,and we denote the reordered users as e+bj(t)dt 1,2,...,j,....,n.Then we try to allocate fractional resource Since it is possible thatb(t)dt=0,we let e>0 to prevent Pij(t)(iE A)to each user j in a progressive filling approach. Wi(t)from equal to +00.This online algorithm called We start from user 1 and try to allocate resource to user 1 as Dynamic Weight based Online Algorithm (DWOA)is much as possible until illustrated in Algorithm 1.Here,Line 3 takes care of the fairness metric by setting Wi(t)inversely proportional to the -6)t+∑eAr,nA accumulated bandwidth.Line 4 considers the efficiency w·T(t) -=2 metric by attempting to maximize the sum of the weighted or user 1 is saturated with available resources.We further bandwidths.We update the association solution for every allocate resource to user 1 (if user 1 is not yet saturated, At time interval.Conventionally the less At we use,the better solution we can obtain,but the drawback is that it otherwise we stop allocation for user 1)and user 2 as much may cause too many handoffs.In the supplementary file, as possible until any of the users is saturated or which can be found on the Computer Society Digital =y.We continue this progressive filling procedure Library at http://doi.ieeecomputersocietyorg/10.1109until all available resources have been allocated or all of the TPDS.2011.17,we further provide the performance analysis users are saturated.For each round we use parameterto of DWOA and introduce the offline optimization for denote the indices for the involved users 1,2,...,J in proportional fairness. progressive filling.Theorem 3. Maximizing the long-term objective function X j2U wj ln þ Z T 0 bjðtÞdt ; ð9Þ is consistent with maximizing the long-term objective function Z T 0 X j2U wj þ R t 0 bjðtÞdt bjðtÞdt: Here, R 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. The proof of Theorem 3 can be found in the supplemen￾tary material, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/ 10.1109/TPDS.2011.17. Recall that the original long-term goal is to maximize X j2U wj ln Z T 0 bjðtÞdt : ð10Þ The only difference between the above two objective functions (9) and (10) is , which may have an impact on the corresponding optimal solution. However, as long as we set small enough ( ! 0) in (9), the long-term goal in (9) becomes very near to P j2U wj lnð R T 0 bjðtÞdtÞ. In order to maximize fO ¼ Z T 0 X j2U wj þ R t 0 bjðtÞdt bjðtÞdt; we use the following heuristic snapshot objective f0 OðtÞ ¼ X j2U wj þ R t 0 bjðtÞdt bjðtÞ; along with the constraint depicted in (4)-(8) to approx￾imate the long-term optimization solution. The intuition is that maximizing f0 OðtÞ at each t contributes to the maximization of fO. We thus propose an algorithm based on the dynamic weight WjðtÞ ¼ wj þ R t 0 bjðtÞdt: Since it is possible that R t 0 bjðtÞdt ¼ 0, we let > 0 to prevent WjðtÞ from equal to þ1. This online algorithm called Dynamic Weight based Online Algorithm (DWOA) is illustrated in Algorithm 1. Here, Line 3 takes care of the fairness metric by setting WjðtÞ inversely proportional to the accumulated bandwidth. Line 4 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. In the supplementary file, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/10.1109/ TPDS.2011.17, we further provide the performance analysis of DWOA and introduce the offline optimization for proportional fairness. 4.3 Online Algorithm for Max-Min Fairness Since max-min fairness is also a frequently used metric for fairness, for completeness, in this section we consider the approach to achieve long-term max-min fairness. The intuition of max-min fairness for the Drive-thru Internet scenario is to maximize the throughput allocated to those users that receive the minimum throughput. As it has been proved by Bejerano et al. [4] that the problem of finding a max-min fair integral association is NP-hard, thus we consider an online algorithm to approximately achieve the max-min fairness. Assume at each snapshot t, each user j has his accumulated bandwidth R t 0 bjðtÞdt and current service duration TjðtÞ. We define a user j to be saturated when P i2A pi;j ¼ 1 or 8i 2 Aj; P j0 2U pi;j0 ¼ 1. In other words, a user j is saturated only when j has used all his time fraction to connect to APs or no remaining time fraction of his candidate APs can be further allocated to j. Algorithm 2 illustrates the online algorithm to achieve long-term max￾min fairness. We update the association solution for every t time interval. For each snapshot t, we sort the users according to nondecreasing order of yj ¼ R t 0 bjðtÞdt wj  TjðtÞ ; which is the current allocated throughput normalized by the weight, and we denote the reordered users as 1; 2; ... ; j; ... :; n. Then we try to allocate fractional resource pi;jðtÞði 2 AÞ to each user j in a progressive filling approach. We start from user 1 and try to allocate resource to user 1 as much as possible until y0 1 ¼ R t 0 b1ðtÞdt þ P i2A ri;jðtÞ  pi;jðtÞ  t w1  T1ðtÞ ¼ y2 or user 1 is saturated with available resources. We further allocate resource to user 1 (if user 1 is not yet saturated, otherwise we stop allocation for user 1) and user 2 as much as possible until any of the users is saturated or y0 1 ¼ y0 2 ¼ y3. We continue this progressive filling procedure until all available resources have been allocated or all of the users are saturated. For each round we use parameter J to denote the indices for the involved users 1; 2; ... ; J in progressive filling. XIE ET AL.: ASSOCIATION CONTROL FOR VEHICULAR WIFI ACCESS: PURSUING EFFICIENCY AND FAIRNESS 1327