1326 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,VOL.22,NO.8,AUGUST 2011 To describe the constraints in this problem formulation Time scale 0T1 T3T4 for each snapshot t,we formulate the association problem T5 T6T7 T8T9 T10 TIIT12T'13 T into a linear program(LP)as proposed in [5].We use a Eql Eq2 Eo3 E04 fractional variable pij(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 pij(t)is a fraction between 0 and 1; if user j is not associated with i,then the fraction is 0.Since 43 each user j is assigned to only one AP for the integral Un solution,there is exactly one nonzero pij(t)for each iA. We can first relax this constraint and assume that one user Fig.3.Time line for users to drive through the Equivalence Classes. can associate with multiple APs for the fractional solution. Then the bandwidth bj(t)allocated to each user j can be generality,we assume that the boundaries of an AP's depicted as bj(t)=ieArij(t)pij(t).Thus,we can obtain a effective range will not coincide with the others.Fig.3 fractional solution from the following linear program shows an example of the vehicular scenario,where a set of formulation: users U1,U2,...,Un are driving through various Equivalence Classes over the time span [0,T].As the time intervals for marimize ∑9b,0, (3) each user to drive through the Equivalence Classes may overlap with each other,hence for ease of analysis we can further divide the overall time span (0,T]into smaller time subject to intervals according to the boundaries of Equivalence Classes VjEU b=∑r)·p) (4 over the time span.We denote these time intervals as icA [To:Ti],[T,T2],....[TL_1,Ti],where To=0 and T =T.We i∈A ∑P因≤1， rely on the following theorem to devise an efficient handoff (5 jE strategy for efficiency metric. YjEU ∑P≤1， (6) Theorem 2.For optimal association control to maximize the iE efficiency metric,handoffs to new association solutions for users i∈A,j∈U0≤P(t)≤1， (7) only happen when at least one user is crossing the boundaries of jeUb(t)≥C Equivalence Classes.At each boundary the user will meet (8) with one of the following cases:1)new candidate AP is detected; Constraint(4)defines b;(t),the bandwidth allocated to user 2)original optimal AP is lost;and 3)original candidate AP is j at time point t.Constraint (5)means that the overall lost.For cases 1)and 2),new association control is necessary. allocated time fraction of each AP i to all users cannot be For case 3),new association control is not needed,so the original more than 1.Constraint(6)states that the overall allocated optimized solution holds. time fraction of each user j that communicates with all APs cannot be more than 1.Constraint (7)shows that the time The proof of Theorem 2 can be found in the supplemen- fraction is between 0 and 1.To ensure that every user is tary material,which can be found on the Computer Society able to maintain connectivity to the internet within the Digital Library at http://doi.ieeecomputersociety.org/ service duration,(8)guarantees that every user has 10.1109/TPDS.2011.17.According to Theorem 2,for the a minimum bandwidth of C at any time t,where C is a efficiency metric we only have to compute the optimized constant value for the lower bound.For the pure efficiency association solution each time when one or more users cross goal we set C=0 by default. the boundary of Equivalence Classes.We can further prevent For completeness,we describe briefly in the following how unnecessary computation by checking the special patterns to find the integral solution based on the fractional solution. of adjacent Equivalence Classes. After we obtain pij(t)for each user-AP pair,we can further calculate the fractional assignment(t)=,which 4.2 Online Algorithm for Proportional Fairness b:(t) In the above section,we have demonstrated that for the reflects the fraction of user i's total bandwidth that it expects efficiency metric we can transform the long-term overall to get from AP i.Apparently 0<ij(t)<1.We can view the optimization into the snapshot optimization.However,for assignment as a bipartite graph.Then,the final integral proportional fairness,as each snapshot decision for the solution is a set of binary variablesij(t)for all user-AP pairs, optimal solution may depend on its former and future wherei(t)is equal to 1if user j is associated with APiand0 situations,we cannot simply conduct this transformation. otherwise.We use the rounding algorithm proposed by We know that the exact optimal solution can only be Shmoy and Tardos [17]to calculate the integral solution achieved with information obtained over the whole time (t).Readers can refer to [5]for detailed description. span [0,T]in advance.However,in practice we cannot Since we have obtained the optimized strategy for precisely know the users'future mobility trajectory,thus no association control over each snapshot,we need to consider information about which users will be contending for the handoff strategy for efficiency.Continuously,comput-specified APs in the future can be obtained beforehand.In ing the optimized association solution for each snapshot is this section,according to the online setting described in the definitely not an appropriate solution,as it incurs too much end of Section 3,we design an online algorithm.Our computing and communication cost.Without loss of solution relies on the following theorem.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 [5]. 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 nonzero pi;jðtÞ for each i 2 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Þ ¼ P i2A ri;jðtÞpi;jðtÞ. Thus, we can obtain a fractional solution from the following linear program formulation: maximize X j2U wj Tj bjðtÞ; ð3Þ subject to 8j 2 U bjðtÞ ¼ X i2A ri;jðtÞ  pi;jðtÞ; ð4Þ 8i 2 A X j2U pi;jðtÞ  1; ð5Þ 8j 2 U X i2A pi;jðtÞ  1; ð6Þ 8i 2 A; j 2 U 0  pi;jðtÞ  1; ð7Þ 8j 2 U bjðtÞ  C: ð8Þ Constraint (4) defines bjðtÞ, the bandwidth allocated to user j at time point t. Constraint (5) means that the overall allocated time fraction of each AP i to all users cannot be more than 1. Constraint (6) states that the overall allocated time fraction of each user j that communicates with all APs cannot be more than 1. Constraint (7) 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, (8) 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 with AP i and 0 otherwise. We use the rounding algorithm proposed by Shmoy and Tardos [17] to calculate the integral solution x^i;jðtÞ. Readers can refer to [5] for detailed description. Since we have obtained the optimized strategy for association control over each snapshot, we need to consider the handoff strategy for efficiency. Continuously, comput￾ing 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 assume that the boundaries of an 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 driving through various Equivalence Classes over the time span ½0; T. As the time intervals for each user to drive through the Equivalence Classes may overlap with each other, hence for ease of analysis we can further 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 ½T0 0; T0 1; ½T0 1; T0 2; ... ; ½T0 L1; T0 L, where T0 0 ¼ 0 and T0 L ¼ T. 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. The proof of Theorem 2 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. 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 computation by checking the special patterns of adjacent Equivalence Classes. 4.2 Online Algorithm for Proportional Fairness In the above section, 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. 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 the 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 section, according to the online setting described in the end of Section 3, we design an online algorithm. Our solution relies on the following theorem. 1326 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 22, NO. 8, AUGUST 2011 Fig. 3. Time line for users to drive through the Equivalence Classes.