As T is a constant,for each snapshot t we only have to it expects to get from AP i.Apparently 0<xi.;(t)<1.We maximize∑jeU号b,(d)for optimization. can view the assignment as a bipartite graph.Then the final Theorem 1 essentially tells us that we can optimize for effi-integral solution is a set of binary variables(t)for all user- ciency metric in each snapshot to achieve overall performance.AP pairs,where(t)is equal to 1 if user j is associated to In the offline setting.we already know Ti in the objective AP i and 0 otherwise.We use the rounding algorithm proposed function.In the online setting,we have to estimate T;based by Shmoy and Tardos [16]to calculate the integral solution on the user's current speed v;(t).Suppose user j gives the i.(t).Readers can refer to [6]for detailed description. driving trajectory to the centralized server through devises like GPS.Knowing the overall distance Sj and the distance sj(t) 人 that user j has traveled at time t,we can continuously estimate Tj for user j at snapshot t using T;(t)=S)+t. Eq2 vs(t) Eq4 U Eqgl To describe the constraints in this problem formulation for each snapshot t,we formulate the association problem into a Eql: linear program(LP)as proposed in [6].We use a fractional variable pi(t)to denote the fraction of time that AP i devotes 43 Ego to user j.For each AP i and user j.if j is associated with Un i,then pi.j(t)is a fraction between 0 and 1;if user j is not 23 67 89 0 112314 associated with i,then the fraction is 0.Since each user j is assigned to only one AP for the integral solution,there is Fig.3.Time line for users to drive through the Equivalence Classes exactly one non-zero pi.j(t)for each i A.We can first relax this constraint and assume that one user can associate with Since we have obtained the optimized strategy for asso- multiple APs for the fractional solution.Then the bandwidth ciation control over each snapshot,we need to consider the bj(t)allocated to each user j can be depicted as bi(t)= handoff strategy for efficiency.Continuously computing the ()(t).Thus we can obtain a fractional solution optimized association solution for each snapshot is definitely from the following linear program formulation: not an appropriate solution,as it incurs too much computing and communication cost.Without loss of generality,we as- marimize∑g1b,(d) (3) sume that the boundaries of a AP's effective range will not T jEU coincide with the others.Fig.3 shows an example of the subject to vehicular scenario,where a set of users U1,U2,....Un are i∈U b()=∑r)·pt) (4) trying to drive through Equivalence Classes over the time iEA span [0,T].Thus we can divide the overall time span [0,T] i∈A ∑p)≤1 into smaller time intervals according to the boundaries of (5) Equivalence Classes over the time span.We denote these jEU time intervals as [to,i],[t,t2],...[,t].We rely on the i∈U ∑P)≤1 (6 following theorem to devise an efficient handoff strategy for iEA efficiency metric. i∈A,j∈U0≤p,(t)≤1 (7) Theorem 2:For optimal association control to maximize j∈Ub(t)≥C (8) the efficiency metric,handoffs to new association solutions for users only happen when at least one user is crossing the The first constraint defines bi(t),the bandwidth allocated to boundaries of Eguivalence Classes.At each boundary the user user j at time point t.The second constraint means that the will meet with one of the following cases:(1)new candidate overall allocated time fraction of each AP i to all users cannot AP is detected;(2)original optimal AP is lost and (3)original be more than 1.The third constraint states that the overall candidate AP is lost.For cases (1)and (2).new association allocated time fraction of each user j that communicates with control is necessary.For case (3),new association control is all APs cannot be more than 1.The fourth constraint shows not needed,so the original optimized solution holds. that the time fraction is between 0 and 1.To ensure that every Proof:According to objective function (t). user is able to maintain connectivity to the internet within the the weight w and service duration T;for each user j are service duration,the fifth constraint guarantees that every user fixed all the time.When all users are within the boundaries of has a minimum bandwidth of C at any time t,where C is Equivalence Classes,the effective bit rates rij(t)are never a constant value for the lower bound.For the pure efficiency changed,which indicates that all parameters for the opti- goal we set C=0 by default. mization problem are not changed,thus the optimal solution For completeness,we describe briefly in the following how holds.For case (1).as a new candidate AP is detected,one to find the integral solution based on the fractional solution. effective bit rate ri(t)will change from 0 to a positive value, After we obtain pi.j(t)for each user-AP pair,we can further so the computation of a new optimal association solution is calculate the fractional assignment i.j(t)= T4p(但 b;(t) necessary.For case(2).since the original optimal AP is lost, which reflects the fraction of user j's total bandwidth that a new optimal association solution is definitely necessary.For 327 Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore.Restrictions apply.As T is a constant, for each snapshot t we only have to maximize j∈U wj Tj bj (t) for optimization. Theorem 1 essentially tells us that we can optimize for effi- ciency metric in each snapshot to achieve overall performance. In the offline setting, we already know Tj in the objective function. In the online setting, we have to estimate Tj based on the user’s current speed vj (t). Suppose user j gives the driving trajectory to the centralized server through devises like GPS. Knowing the overall distance Sj and the distance sj (t) that user j has traveled at time t, we can continuously estimate Tj for user j at snapshot t using Tj (t) = Sj−sj (t) vj (t) + t. To describe the constraints in this problem formulation for each snapshot t, we formulate the association problem into a linear program (LP) as proposed in [6]. We use a fractional variable pi,j (t) to denote the fraction of time that AP i devotes to user j. For each AP i and user j, if j is associated with i, then pi,j (t) is a fraction between 0 and 1; if user j is not associated with i, then the fraction is 0. Since each user j is assigned to only one AP for the integral solution, there is exactly one non-zero pi,j (t) for each i ∈ A. We can first relax this constraint and assume that one user can associate with multiple APs for the fractional solution. Then the bandwidth bj (t) allocated to each user j can be depicted as bj(t) = i∈A ri,j (t)pi,j (t). Thus we can obtain a fractional solution from the following linear program formulation: maximize j∈U wj Tj bj (t) (3) subject to ∀j ∈ U bj (t) =  i∈A ri,j (t) · pi,j (t) (4) ∀i ∈ A  j∈U pi,j (t) ≤ 1 (5) ∀j ∈ U  i∈A pi,j (t) ≤ 1 (6) ∀i ∈ A, j ∈ U 0 ≤ pi,j (t) ≤ 1 (7) ∀j ∈ U bj (t) ≥ C (8) The first constraint defines bj (t), the bandwidth allocated to user j at time point t. The second constraint means that the overall allocated time fraction of each AP i to all users cannot be more than 1. The third constraint states that the overall allocated time fraction of each user j that communicates with all APs cannot be more than 1. The fourth constraint shows that the time fraction is between 0 and 1. To ensure that every user is able to maintain connectivity to the internet within the service duration, the fifth constraint guarantees that every user has a minimum bandwidth of C at any time t, where C is a constant value for the lower bound. For the pure efficiency goal we set C = 0 by default. For completeness, we describe briefly in the following how to find the integral solution based on the fractional solution. After we obtain pi,j (t) for each user-AP pair, we can further calculate the fractional assignment xi,j (t) = ri,j (t)·pi,j (t) bj (t) , which reflects the fraction of user j’s total bandwidth that it expects to get from AP i. Apparently 0 ≤ xi,j (t) ≤ 1. We can view the assignment as a bipartite graph. Then the final integral solution is a set of binary variables xˆi,j (t) for all user￾AP pairs, where xˆi,j (t) is equal to 1 if user j is associated to AP i and 0 otherwise. We use the rounding algorithm proposed by Shmoy and Tardos [16] to calculate the integral solution xˆi,j (t). Readers can refer to [6] for detailed description. 0 T ...... Eq1 Eq2 Eq2 Eq3 Eq4 Eq3 Eq4 U1 U2 Un ...... 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Eq3 Eq4 Eq5 Eq6 Eq1 Fig. 3. Time line for users to drive through the Equivalence Classes Since we have obtained the optimized strategy for asso￾ciation control over each snapshot, we need to consider the handoff strategy for efficiency. Continuously computing the optimized association solution for each snapshot is definitely not an appropriate solution, as it incurs too much computing and communication cost. Without loss of generality, we as￾sume that the boundaries of a AP’s effective range will not coincide with the others. Fig. 3 shows an example of the vehicular scenario, where a set of users U1, U2, ..., Un are trying to drive through Equivalence Classes over the time span [0, T ]. Thus we can divide the overall time span [0, T ] into smaller time intervals according to the boundaries of Equivalence Classes over the time span. We denote these time intervals as [t 0, t 1], [t 1, t 2], ..., [t L−1, t L]. We rely on the following theorem to devise an efficient handoff strategy for efficiency metric. Theorem 2: For optimal association control to maximize the efficiency metric, handoffs to new association solutions for users only happen when at least one user is crossing the boundaries of Equivalence Classes. At each boundary the user will meet with one of the following cases: (1) new candidate AP is detected; (2) original optimal AP is lost and (3) original candidate AP is lost. For cases (1) and (2), new association control is necessary. For case (3), new association control is not needed, so the original optimized solution holds. Proof: According to objective function j∈U wj Tj bj (t), the weight wj and service duration Tj for each user j are fixed all the time. When all users are within the boundaries of Equivalence Classes, the effective bit rates ri,j (t) are never changed, which indicates that all parameters for the opti￾mization problem are not changed, thus the optimal solution holds. For case (1), as a new candidate AP is detected, one effective bit rate ri,j (t) will change from 0 to a positive value, so the computation of a new optimal association solution is necessary. For case (2), since the original optimal AP is lost, a new optimal association solution is definitely necessary. For 327 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore. Restrictions apply.