XIE ET AL.:ASSOCIATION CONTROL FOR VEHICULAR WIFI ACCESS:PURSUING EFFICIENCY AND FAIRNESS 1325 Effective Bit Rates (kbits/s) online settings of the optimization problem.In the offline AP2 setting,we assume that we know the mobility patterns and AP4 trajectories of vehicular users in advance,in other words, AP3 AP5 we are given the candidate AP set Aj(t)for each user j at each time t0,T]as part of the problem input.In the online setting,each Aj(t)is revealed only at time t,at which time instant we have to instantaneously select an AP from A;(t)to associate for each user j,without any knowledge of Fig.2.Nonuniform AP deployments along user's driving trajectory. the future sets Aj(t')for t'[t,T]. bit rates.We then divide these regions into nonoverlapping 4 OVERALL OPTIMIZATION AND SNAPSHOT Equivalence Classes as Eq,Eg2,...,Egn.Each Eqi denotes a SOLUTION section of the roads,and within each section the candidate AP set and corresponding effective bit rates will keep fixed For the efficiency metric,with a set of vehicular users U on for the specified user. the roads,the objective is to maximizeBj which can be further denoted as 3.2 Performance Metrics We consider two performance metrics in this study: b;(t)dt. (1) efficiency and fairness.Efficiency is measured with the overall throughput received by all users,and fairness is to regulate the association control so that all users have a fair Here wj denotes priority for different users,and it is a fixed distribution of bandwidth as much as possible. value for user j.Similarly,if we choose proportional fairness as the metric,the optimization objective is to For efficiency,we aim to maximize the overall through- put for all vehicular users.The throughput for any user is maximize Bj,which can be further denoted as the average message delivery rate during the user's service period and it is usually measured in bits per second.Hence j(t)dt (2) for any user j,given the service duration [tj,tj+Ti]and the allocated bandwidth bi(t)at time t[tj,tj+Til,we can The above two objectives are optimization metrics over express the throughput B for user jas B()d. the duration of service period for all users.We use the term Consider the overall time interval (0,T],during intervals "long-term"to denote the overall time interval the user gets service.As we aim to continuously construct optimized [0,ti]and [tj+Ti,T],we actually have bj(t)=0,thus we assignments of users to APs within this duration,we use have an equivalent uniform notion as B=b(t)dt. the term "snapshot"to denote the time instant within which Association control without considering fairness may we have to make a decision about aP association for all lead to the starvation of users with poor signal strength.To users.Thus,it is necessary for us to find solutions for each consider fairness,two metrics are used frequently in snapshot to achieve the overall optimal performance. literature:max-min fairness [4]and proportional fairness 4.1 Snapshot Optimization for Efficiency [5].Suppose the throughput allocation for all n users can be denoted as a vector B=(B1,B2,...,B).For max-min We first prove a theorem. fairness,an allocation B is "max-min fair"if and only if an Theorem 1.For the efficiency metric,it is sufficient to maximize increase of any throughput within the domain of feasible (t)for each snapshot t to achieve the long-term optimization goal. allocations must be at the cost of a decrease of some already smaller throughput.For proportional fairness,an The proof of Theorem 1 can be found in the supplemen- allocation B is "proportionally fair"if and only if,for any tary material,which can be found on the Computer Society other feasible allocation.In other words, Digital Library at http://doi.ieeecomputersociety.org/ any change in the allocation must have a negative average 10.1109/TPDS.2011.17.Theorem 1 essentially tells us that change.It has been proved that the unique proportionally we can optimize for efficiency metric in each snapshot to fair allocation can be obtained by maximizing(B)=achieve overall performance.In the offline setting,we In(Bj)over the set of feasible allocations [15]. already know Ti in the objective function.In the online Since all APs are deployed by the same organization,a setting,we have to estimate T;based on the user's current centralized control scheme is possible as proposed in [16]. speed vj(t).Suppose user j gives the driving trajectory to Therefore based on the above models and assumptions, the centralized server through devises like GPS.Knowing assuming we are the service provider of the specified the overall distance S;and the distance s;(t)that user j has region,we aim to build a centralized association control traveled at time t,we can continuously estimate T;for user j system and our goal is to continuously construct optimized at snapshot t using T(t)=t.In case that the vi(t) assignments of APs to users as they are driving along the vehicular user stops at traffic lights,we maintain a window roads,respectively,taking the efficiency and fairness of speeds for recent k snapshots,and use the average speed metrics into consideration.We consider both offline and v;(t)to estimate Ti(t).bit rates. We then divide these regions into nonoverlapping Equivalence Classes as Eq1; Eq2; ... ; Eqn. Each Eqi denotes a section of the roads, and within each section the candidate AP set and corresponding effective bit rates will keep fixed for the specified user. 3.2 Performance Metrics We consider two performance metrics in this study: efficiency and fairness. Efficiency is measured with the overall throughput received by all users, and fairness is to regulate the association control so that all users have a fair distribution of bandwidth as much as possible. For efficiency, we aim to maximize the overall through￾put for all vehicular users. The throughput for any user is the average message delivery rate during the user’s service period and it is usually measured in bits per second. Hence for any user j, given the service duration ½tj; tj þ Tj and the allocated bandwidth bjðtÞ at time t 2 ½tj; tj þ Tj, we can express the throughput Bj for user j as Bj ¼ 1 Tj R tjþTj tj bjðtÞdt. Consider the overall time interval ½0; T, during intervals ½0; tj and ½tj þ Tj; T, we actually have bjðtÞ ¼ 0, thus we have an equivalent uniform notion as Bj ¼ 1 Tj R T 0 bjðtÞdt. Association control without considering fairness may lead to the starvation of users with poor signal strength. To consider fairness, two metrics are used frequently in literature: max-min fairness [4] and proportional fairness [5]. Suppose the throughput allocation for all n users can be denoted as a vector B~ ¼ hB1; B2; ... ; Bni. For max-min fairness, an allocation B~ is “max-min fair” if and only if an increase of any throughput within the domain of feasible allocations must be at the cost of a decrease of some already smaller throughput. For proportional fairness, an allocation B~ is “proportionally fair” if and only if, for any other feasible allocation B~0 , PjB~j j¼1 B0 jBj Bj  0. In other words, any change in the allocation must have a negative average change. It has been proved that the unique proportionally fair allocation can be obtained by maximizing JðB~Þ ¼ P j lnðBjÞ over the set of feasible allocations [15]. Since all APs are deployed by the same organization, a centralized control scheme is possible as proposed in [16]. Therefore based on the above models and assumptions, assuming we are the service provider of the specified region, we aim to build a centralized association control system and our goal is to continuously construct optimized assignments of APs to users as they are driving along the roads, respectively, taking the efficiency and fairness metrics into consideration. We consider both offline and online settings of the optimization problem. In the offline setting, we assume that we know the mobility patterns and trajectories of vehicular users in advance, in other words, we are given the candidate AP set AjðtÞ for each user j at each time t 2 ½0; T as part of the problem input. In the online setting, each AjðtÞ is revealed only at time t, at which time instant we have to instantaneously select an AP from AjðtÞ to associate for each user j, without any knowledge of the future sets Ajðt 0 Þ for t 0 2 ½t; T. 4 OVERALL OPTIMIZATION AND SNAPSHOT SOLUTION For the efficiency metric, with a set of vehicular users U on the roads, the objective is to maximize P j2U wjBj, which can be further denoted as X j2U wj Tj Z T 0 bjðtÞdt: ð1Þ Here wj denotes priority for different users, and it is a fixed value for user j. Similarly, if we choose proportional fairness as the metric, the optimization objective is to maximize P j2U wj ln Bj, which can be further denoted as X j2U wj ln 1 Tj Z T 0 bjðtÞdt : ð2Þ The above two objectives are optimization metrics over the duration of service period for all users. We use the term “long-term” to denote the overall time interval the user gets service. As we aim to continuously construct optimized assignments of users to APs within this duration, we use the term “snapshot” to denote the time instant within which we have to make a decision about AP association for all users. Thus, it is necessary for us to find solutions for each snapshot to achieve the overall optimal performance. 4.1 Snapshot Optimization for Efficiency We first prove a theorem. Theorem 1. P For the efficiency metric, it is sufficient to maximize j2U wj Tj bjðtÞ for each snapshot t to achieve the long-term optimization goal. The proof of Theorem 1 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. Theorem 1 essentially tells us that we can optimize for efficiency 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Þ ¼ SjsjðtÞ vj ðtÞ þ t. In case that the vehicular user stops at traffic lights, we maintain a window of speeds for recent k snapshots, and use the average speed vjðtÞ to estimate TjðtÞ. XIE ET AL.: ASSOCIATION CONTROL FOR VEHICULAR WIFI ACCESS: PURSUING EFFICIENCY AND FAIRNESS 1325 Fig. 2. Nonuniform AP deployments along user’s driving trajectory.