计算机科学与技术（参考文献）Achieving Efficiency and Fairness for Association Control in Vehicular Networks

Achieving Efficiency and Fairness for Association Control in Vehicular Networks Lei Xiett,Qun Lit,Weizhen Maof,Jie Wus,Daoxu Chent fState Key Laboratory of Novel Software Technology,Nanjing University,China The College of William and Mary,Williamsburg,VA,USA STemple University,Philadelphia,PA,USA Email:ixielei@dislab.nju.edu.cn,fliqun,wm@cs.wm.edu,3jiewu@temple.edu,fcdx@nju.edu.cn Abstract-Deploying city-wide 802.11 access points has made manage AP association in this type of"Vehicular Networks". possible internet access in a vehicle,nevertheless it is challenging Compared with a static network,this type of network is to maintain client performance at vehicular speed especially composed of continuously moving clients that may constantly when multiple mobile users exist.This paper considers the association control problem for vehicular networks in drive- try to associate with the nearby APs.Algorithms that solve thru Internet scenarios.In particular,we aim to improve the for the association control problem in a static network are overall throughput and fairness for all users.We design efficient not suitable because(1)a vehicular network is a much larger algorithms to achieve the objectives through several techniques network composed of thousands of cars and APs compared including approximation.Our simulation results confirm the with a rather small indoor network,and(2)the existing algo- performance of our algorithms. rithms are unable to accommodate the dynamic creation and I.INTRODUCTION removal of the possible communication links in the network graph.Algorithms which are designed for the cellular network Advanced technologies in communication have made ubiq- are also not suitable,because (1)the cell site has a much uitous network connectivity-anywhere,anytime-a reality for mobile users.Wi-Fi technology is one of them,which provides larger coverage,and (2)the cells are devised to have small users easy access to the Internet through nearby WLAN access overlapping areas,and the mobile clients usually do not have multiple candidate cell sites to choose.Hence the handoff only points.WLAN-based access points (AP)can provide cost- occurs when a mobile client moves out of the original cell or effective wireless Internet access with a shared gross data rate that ranges from 10 to 50 Mbits/sec and can be scalable to hun- moves into a new cell.The association control for "Vehicular Networks"is much more complicated and has more urgent dreds of concurrently-active users.Not limited to corporation, real-time demand than the cellular network because a client office,or home use for comparably stationary user,the access can have multiple candidate APs to select most of the time and points,in the Drive-thru Internet[1][2],are recently proposed in a very short interval (20-30s),the client may move out of to be deployed along the roads,thus providing continuous the range of the current AP and switch to a new AP for better network connectivity to mobile users in vehicles.However, for outdoor access of mobile users at high vehicular speeds, performance.We believe that a thorough theoretical study on this problem is highly necessary for the future deployment of due to the dynamically changing network structure of AP-user pairing and contentions among mobile users,it is still a big this type of networks.Some pitfalls can be avoided in real deployment if we have a better understanding about it first. challenge to maintain a good client performance. In order to achieve reasonable efficiency among multiple This paper aims to define a theoretical framework to analyze the performance of a vehicular network in the Drive-thru vehicular users for the above Drive-thru Internet scenario, Internet scenario,in particular to investigate the association several problems should be considered,e.g.,rate adaptation and association control.Association control defines,while control scheme.Considering both the long-term efficiency and fairness metrics,we propose optimized schemes to associate multiple users are driving along the road,how to intelligently mobile users with APs,and approximation algorithms to re- associate these mobile users to specific APs and when to duce computation complexity of calculating optimal solutions. appropriately conduct handoffs of APs for users to improve Although there is some previous work related to this topic the overall system performance.Compared with rate adapta- [12]3].they all focus on the measurement study on vehicular tion,association control considers the entire network from a internet access.To the best of our knowledge,this is the first macro-level perspective,which shows how to optimize system performance from a higher level viewpoint. theoretical work that investigates the optimization problem for association control over vehicular users in Wi-Fi networks. We notice that,albeit some recent work on association And being distinct from the previous research works,since the control for static networks,there is little work on how to association solutions are updated in a frequent approach while This work was done when the first author worked as a visiting scholar at the users are driving along the roads,this paper is concerned the College of William and Mary. about the long-term performance in terms of efficiency and 978-1-4244-4634-6/09/S25.00©20091EEE 324 Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:35:32 UTC from IEEEXplore.Restrictions apply

Achieving Efficiency and Fairness for Association Control in Vehicular Networks Lei Xie†‡, Qun Li‡, Weizhen Mao‡, Jie Wu§, Daoxu Chen† †State Key Laboratory of Novel Software Technology, Nanjing University, China ‡The College of William and Mary, Williamsburg, VA, USA §Temple University, Philadelphia, PA, USA Email: †xielei@dislab.nju.edu.cn, ‡{liqun, wm}@cs.wm.edu, §jiewu@temple.edu, †cdx@nju.edu.cn Abstract—Deploying city-wide 802.11 access points has made possible internet access in a vehicle, nevertheless it is challenging to maintain client performance at vehicular speed especially when multiple mobile users exist. This paper considers the association control problem for vehicular networks in drive￾thru Internet scenarios. In particular, we aim to improve the overall throughput and fairness for all users. We design efficient algorithms to achieve the objectives through several techniques including approximation. Our simulation results confirm the performance of our algorithms. I. INTRODUCTION Advanced technologies in communication have made ubiq￾uitous network connectivity - anywhere, anytime - a reality for mobile users. Wi-Fi technology is one of them, which provides users easy access to the Internet through nearby WLAN access points. WLAN-based access points (AP) can provide cost￾effective wireless Internet access with a shared gross data rate that ranges from 10 to 50 Mbits/sec and can be scalable to hun￾dreds of concurrently-active users. Not limited to corporation, office, or home use for comparably stationary user, the access points, in the Drive-thru Internet[1][2], are recently proposed to be deployed along the roads, thus providing continuous network connectivity to mobile users in vehicles. However, for outdoor access of mobile users at high vehicular speeds, due to the dynamically changing network structure of AP-user pairing and contentions among mobile users, it is still a big challenge to maintain a good client performance. In order to achieve reasonable efficiency among multiple vehicular users for the above Drive-thru Internet scenario, several problems should be considered, e.g., rate adaptation and association control. Association control defines, while multiple users are driving along the road, how to intelligently associate these mobile users to specific APs and when to appropriately conduct handoffs of APs for users to improve the overall system performance. Compared with rate adapta￾tion, association control considers the entire network from a macro-level perspective, which shows how to optimize system performance from a higher level viewpoint. We notice that, albeit some recent work on association control for static networks, there is little work on how to This work was done when the first author worked as a visiting scholar at the College of William and Mary. manage AP association in this type of “Vehicular Networks”. Compared with a static network, this type of network is composed of continuously moving clients that may constantly try to associate with the nearby APs. Algorithms that solve for the association control problem in a static network are not suitable because (1) a vehicular network is a much larger network composed of thousands of cars and APs compared with a rather small indoor network, and (2) the existing algo￾rithms are unable to accommodate the dynamic creation and removal of the possible communication links in the network graph. Algorithms which are designed for the cellular network are also not suitable, because (1) the cell site has a much larger coverage, and (2) the cells are devised to have small overlapping areas, and the mobile clients usually do not have multiple candidate cell sites to choose. Hence the handoff only occurs when a mobile client moves out of the original cell or moves into a new cell. The association control for “Vehicular Networks” is much more complicated and has more urgent real-time demand than the cellular network because a client can have multiple candidate APs to select most of the time and in a very short interval (20-30s), the client may move out of the range of the current AP and switch to a new AP for better performance. We believe that a thorough theoretical study on this problem is highly necessary for the future deployment of this type of networks. Some pitfalls can be avoided in real deployment if we have a better understanding about it first. This paper aims to define a theoretical framework to analyze the performance of a vehicular network in the Drive-thru Internet scenario, in particular to investigate the association control scheme. Considering both the long-term efficiency and fairness metrics, we propose optimized schemes to associate mobile users with APs, and approximation algorithms to re￾duce computation complexity of calculating optimal solutions. Although there is some previous work related to this topic [1][2][3], they all focus on the measurement study on vehicular internet access. To the best of our knowledge, this is the first theoretical work that investigates the optimization problem for association control over vehicular users in Wi-Fi networks. And being distinct from the previous research works, since the association solutions are updated in a frequent approach while the users are driving along the roads, this paper is concerned about the long-term performance in terms of efficiency and 978-1-4244-4634-6/09/$25.00 ©2009 IEEE 324 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore. Restrictions apply

fairness,and proposes novel algorithms to achieve the long- access can be greatly improved [10.Kim et al.present novel term objective.The contributions are summarized as follows: association control algorithms that minimize the frequency 1)We propose a theoretical framework for association of handoffs occurred to mobile devices [11].In the case of control over vehicular networks.For the efficiency metric.the a single user,the optimization of the total throughput with problem is transformed into an optimization problem for each handoff time taken into account is studied in [12]. snapshot over the long-term service duration,and formulated as an integral linear program.For the fairness metric,we first III.PERFORMANCE MODELS AND METRICS formulate the problem as a convex program in the offline A.Models and Assumptions setting,and further propose a dynamic weight based online In the Drive-thru Internet scenario,vehicular users are algorithm to achieve proportional fairness. driving through a region covered with multiple roads,and 2)When the involved number of mobile users and APs APs are deployed along the roads in a nonuniform approach. along the road is rather large,to reduce the computation Each aP has a limited coverage range and it can only serve complexity,we propose an approximation algorithm to break users that reside in its coverage area.Conventionally each the large contention group into smaller sub-groups,achieving user on the roads may have one or more candidate aPs to a tradeoff between accuracy and computation complexity. associate with at any time,and each time the user can only The rest of the paper is organized as follows.We present associate with exactly one AP.Furthermore,contentions for related work in Section II.We define the performance metrics transmission may exist among users if they associate with the and introduce our model and assumptions in Section III.We same AP.If a large number of users associate with the same illustrate our overall optimization and snapshot solutions in AP,their allocated bandwidths will be greatly reduced.We Section IV,respectively for efficiency and fairness.We in-assume that different users have various velocities (including troduce our group-based methodology to simplify association speeds and directions)which may vary over the time.Thus control in Section V.We discuss the practical utilization in while users are driving along the roads,at different time realistic settings in Section VI.We show simulation results in instants and positions,they may be contending with different Section VIl,and we conclude the paper in Section VIII. users for bandwidth from different APs.Each user associates with the first AP after first entering the Wi-Fi deployment II.RELATED WORK area,then goes through a series of hand-offs among different Association control and scheduling solutions for Wireless APs while driving along the roads,and disconnects at the last LANs have been intensely studied,mainly targeting the effi- associated AP before leaving the Wi-Fi deployment area. ciency and fairness metrics.Tassiulas et al.consider max-min We denote the set of APs as A indexed by 1,...,m and fair allocation of bandwidth in wireless ad-hoc networks [41. denote the set of users as U indexed by 1,...,n.We consider and propose a fair scheduling system which assigns dynamic association control over the time interval [0,T].For each user- weights to the flows.Bejerano et al.present an efficient AP pair (j,i),we assume that the effective bit rate ri.j(t)of solution to determine the user-AP association for max-min fair the link between j and i at time t is known.We use b;(t)to bandwidth allocation [5],by leveraging the strong correlation denote the bandwidth allocated to user j at time t.Both bit between fairness and load balancing.To balance aggregate rate and bandwidth can be measured in bits per second (bit/s). throughput while serving users in a fair manner,Li et al. For bandwidth allocation inside each AP,we use time-based consider proportional fairness over wireless LANs [6].They fairness for scheduling.Once an AP is associated to some propose two approximation algorithms for periodical offline users,each user is assigned an equal-sized time slot regardless optimization. its effective bit rate,and is supposed to use all the allocated Internet access with roadside WiFi access points for vehic- bandwidth.Thus if n'users are associated with AP i at time ular users under vehicular speeds has been studied in recent t,then the bandwidth of user j is bj(t)=ri.j(t)/n'. research works [78.Bychkovsky et al.study the case for For the effective bit rate setting in the Drive-thru Internet vehicular clients to connect to open-access residential wireless scenario.we adopt the model proposed in [2].Fig.I depicts 802.11 access points in Boston [1].Giannoulis et al.address three different connectivity phases with respect to effective the problem of maintaining client performance at vehicular bit rate and relative distance.The entry phase and exit phase speeds within city-wide multi-hop 802.11 networks [3].Ott provide very weak connectivity,only the production phase and Kutscher report on measurements for the use of IEEE provides a window of useful connectivity.As the connection 802.11 networks in the drive-thru Internet scenario [2.They is built between a user and an AP,it will maintain a constant measure transmission characteristics in vehicles moving at bit rate in the production phase,which mainly depends on different speeds,and provide analysis on the expected perfor- the AP's signal strength and the user's driving speed.The bit mance.Mahajan et al.deploy a modest-size testbed to analyze rate can basically keep fixed while the user's speed does not the fundamental characteristics of WiFi-based connectivity change too much.Therefore for each specified user we can between base stations and vehicles in urban settings [9]. approximately model the bit rates of APs as square waves.As Hadaller et al.give a central message that wireless conditions Fig.2 shows,we allow nonuniform AP deployments along in the vicinity of a roadside access point are predictable and any user's driving trajectory which include effective ranges, that by exploiting this information,vehicular opportunistic neighbor distances and effective bit rates.We then divide 325 Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore.Restrictions apply

fairness, and proposes novel algorithms to achieve the long￾term objective. The contributions are summarized as follows: 1) We propose a theoretical framework for association control over vehicular networks. For the efficiency metric, the problem is transformed into an optimization problem for each snapshot over the long-term service duration, and formulated as an integral linear program. For the fairness metric, we first formulate the problem as a convex program in the offline setting, and further propose a dynamic weight based online algorithm to achieve proportional fairness. 2) When the involved number of mobile users and APs along the road is rather large, to reduce the computation complexity, we propose an approximation algorithm to break the large contention group into smaller sub-groups, achieving a tradeoff between accuracy and computation complexity. The rest of the paper is organized as follows. We present related work in Section II. We define the performance metrics and introduce our model and assumptions in Section III. We illustrate our overall optimization and snapshot solutions in Section IV, respectively for efficiency and fairness. We in￾troduce our group-based methodology to simplify association control in Section V. We discuss the practical utilization in realistic settings in Section VI. We show simulation results in Section VII, and we conclude the paper in Section VIII. II. RELATED WORK Association control and scheduling solutions for Wireless LANs have been intensely studied, mainly targeting the effi- ciency and fairness metrics. Tassiulas et al. consider max-min fair allocation of bandwidth in wireless ad-hoc networks [4], and propose a fair scheduling system which assigns dynamic weights to the flows. Bejerano et al. present an efficient solution to determine the user-AP association for max-min fair bandwidth allocation [5], by leveraging the strong correlation between fairness and load balancing. To balance aggregate throughput while serving users in a fair manner, Li et al. consider proportional fairness over wireless LANs [6]. They propose two approximation algorithms for periodical offline optimization. Internet access with roadside WiFi access points for vehic￾ular users under vehicular speeds has been studied in recent research works [7][8]. Bychkovsky et al. study the case for vehicular clients to connect to open-access residential wireless 802.11 access points in Boston [1]. Giannoulis et al. address the problem of maintaining client performance at vehicular speeds within city-wide multi-hop 802.11 networks [3]. Ott and Kutscher report on measurements for the use of IEEE 802.11 networks in the drive-thru Internet scenario [2]. They measure transmission characteristics in vehicles moving at different speeds, and provide analysis on the expected perfor￾mance. Mahajan et al. deploy a modest-size testbed to analyze the fundamental characteristics of WiFi-based connectivity between base stations and vehicles in urban settings [9]. Hadaller et al. give a central message that wireless conditions in the vicinity of a roadside access point are predictable and that by exploiting this information, vehicular opportunistic access can be greatly improved [10]. Kim et al. present novel association control algorithms that minimize the frequency of handoffs occurred to mobile devices [11]. In the case of a single user, the optimization of the total throughput with handoff time taken into account is studied in [12]. III. PERFORMANCE MODELS AND METRICS A. Models and Assumptions In the Drive-thru Internet scenario, vehicular users are driving through a region covered with multiple roads, and APs are deployed along the roads in a nonuniform approach. Each AP has a limited coverage range and it can only serve users that reside in its coverage area. Conventionally each user on the roads may have one or more candidate APs to associate with at any time, and each time the user can only associate with exactly one AP. Furthermore, contentions for transmission may exist among users if they associate with the same AP. If a large number of users associate with the same AP, their allocated bandwidths will be greatly reduced. We assume that different users have various velocities (including speeds and directions) which may vary over the time. Thus while users are driving along the roads, at different time instants and positions, they may be contending with different users for bandwidth from different APs. Each user associates with the first AP after first entering the Wi-Fi deployment area, then goes through a series of hand-offs among different APs while driving along the roads, and disconnects at the last associated AP before leaving the Wi-Fi deployment area. We denote the set of APs as A indexed by 1, ..., m and denote the set of users as U indexed by 1, ..., n. We consider association control over the time interval [0, T ]. For each user￾AP pair (j, i), we assume that the effective bit rate ri,j (t) of the link between j and i at time t is known. We use bj(t) to denote the bandwidth allocated to user j at time t. Both bit rate and bandwidth can be measured in bits per second (bit/s). For bandwidth allocation inside each AP, we use time-based fairness for scheduling. Once an AP is associated to some users, each user is assigned an equal-sized time slot regardless its effective bit rate, and is supposed to use all the allocated bandwidth. Thus if n users are associated with AP i at time t, then the bandwidth of user j is bj(t) = ri,j (t)/n . For the effective bit rate setting in the Drive-thru Internet scenario, we adopt the model proposed in [2]. Fig. 1 depicts three different connectivity phases with respect to effective bit rate and relative distance. The entry phase and exit phase provide very weak connectivity, only the production phase provides a window of useful connectivity. As the connection is built between a user and an AP, it will maintain a constant bit rate in the production phase, which mainly depends on the AP’s signal strength and the user’s driving speed. The bit rate can basically keep fixed while the user’s speed does not change too much. Therefore for each specified user we can approximately model the bit rates of APs as square waves. As Fig. 2 shows, we allow nonuniform AP deployments along any user’s driving trajectory which include effective ranges, neighbor distances and effective bit rates. We then divide 325 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore. Restrictions apply.

these regions into non-overlapped Equivalence Classes as in the allocation must have a negative average change.It has Eqi,Eg2,...,Eqn.Each Egi denotes a section of the roads,been proved that the unique proportionally fair allocation can and within each section the candidate AP set and correspond-be obtained by maximizing(B)=In(Bj)over the set ing effective bit rates will keep fixed for the specified user. of feasible allocations [141. Since all APs are deployed by the same organization,a Effective Bit Rates(kbits/s) centralized control scheme is possible as proposed in [15]. Entry Phase Production Phase Exit Phase Therefore based on the above models and assumptions,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 220m 300m 220a1 problem.In the offline setting,we assume that we know the Distance(m) mobility patterns and trajectories of vehicular users in advance, in other words,we are given the candidate AP set Aj(t)for Fig.1.Three connectivity phases each userj at each time t[0,T]as part of the problem input. In the online setting,each A(t)is revealed only at time t,at which time instant,we have to instantaneously select an AP Effective Bit Rates (kbits/s) AP2 from Aj(t)to associate for each user j,without any knowledge APL AP4 of the future sets Aj(t')for t'[t,T]. AP5 AP3 IV.OVERALL OPTIMIZATION AND SNAPSHOT SOLUTION For the efficiency metric,with a set of vehicular users U on the roads,the objective is to maximize Bj,which E95 Eg6 Distance can be further denoted as Fig.2.Nonuniform AP deployments along user's driving trajectory bi(t)d(t). (1) B.Performance Metrics Here wj denotes priority for different users,and it is a fixed We consider two important performance metrics in this value for specified user j.Similarly if we choose proportional study:efficiency and fairness.Efficiency is measured with fairness as the metric,the optimization objective is to maxi- the overall throughput received by all users and fairness is mizeBj.which can be further denoted as to regulate the association control so that all users will have T a fair distribution of bandwidth as much as possible. bi(t)d(t)). (2) ,0 For efficiency,we aim to maximize the overall throughput jEU for all vehicular users.The throughput for any user is the The above two objectives are optimization metrics over average message delivery rate during the user's service period the duration of service period for all users.As we aim to and it is usually measured in bits per second(bit/s).Hence for continuously construct optimized assignments of users to APs any user j.given the service duration [tj,j+Ti]and the allo- within this duration,we use the term"snapshot"to denote the cated bandwidth bi(t)at time t E [tj,t;+Ti],we can express small time interval within which we have to make a decision the throughput B for users,=士y+b,向dd. about AP association for all users.Thus it is necessary for Consider the overall time interval [0,T].during intervals [0,t]us to find solutions for each snapshot to achieve the overall and [tj+Ti,T],we actually have bi(t)=0.thus we have an optimal performance. equivalent uniform notion as B(td(t). Association control without considering fairness may lead A.Snapshot Optimization for Efficiency to the starvation of users with poor signal strength.To consider We first prove a theorem. fairness,two metrics are used frequently in literature:max-min Theorem /For the efficiency metric,it is sufficient to fairness [5]and proportional fairness [6][13].We use propor- maximize(t)for each snapshot t to achieve the tional fairness in this paper because it can achieve a better long-term optimization goal. trade-off between efficiency and extreme fairness.Suppose Proof:For the efficiency metric,we are to maximize the throughput allocation for all n users can be denoted as fo=∑jeu号0b(t)d(e)according to(I).As wj and Tj a vector B=(B1,B2,...,Bn).By definition,an allocation B are constants with time for each user j,we have is "proportionally fair"if and only if,for any other feasible T allocaion戌，∑A马号≤0 In other ords,ay change fo= Jo jeU 326 Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore.Restrictions apply

these regions into non-overlapped Equivalence Classes as Eq1,Eq2, ..., Eqn. Each Eqi denotes a section of the roads, and within each section the candidate AP set and correspond￾ing effective bit rates will keep fixed for the specified user. Entry Phase Production Phase Exit Phase Effective Bit Rates (kbits/s) Distance (m) 220m 300m 220m Fig. 1. Three connectivity phases AP2 AP4 AP5 Eq1 Eq2 Eq3 Eq4 Eq5 Eq6 Eq7 Eq8 Eq9 Effective Bit Rates (kbits/s) Distance AP1 AP3 Fig. 2. Nonuniform AP deployments along user’s driving trajectory B. Performance Metrics We consider two important 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 will have a fair distribution of bandwidth as much as possible. For efficiency, we aim to maximize the overall throughput 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 (bit/s). Hence for any user j, given the service duration [tj , tj +Tj] and the allo￾cated bandwidth bj (t) at time t ∈ [tj , tj +Tj], we can express the throughput Bj for user j as Bj = 1 Tj tj+Tj tj bj (t)d(t). 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 T 0 bj (t)d(t). 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 [5] and proportional fairness [6][13]. We use propor￾tional fairness in this paper because it can achieve a better trade-off between efficiency and extreme fairness. Suppose the throughput allocation for all n users can be denoted as a vector B = B1, B2, ..., Bn. By definition, an allocation B is “proportionally fair” if and only if, for any other feasible allocation B , |B | j=1 B j−Bj 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 ) = j ln(Bj ) over the set of feasible allocations [14]. Since all APs are deployed by the same organization, a centralized control scheme is possible as proposed in [15]. Therefore based on the above models and assumptions, 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 ∈ [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 ) for t ∈ [t, T ]. IV. OVERALL OPTIMIZATION AND SNAPSHOT SOLUTION For the efficiency metric, with a set of vehicular users U on the roads, the objective is to maximize j∈U wjBj , which can be further denoted as  j∈U wj Tj  T 0 bj (t)d(t). (1) Here wj denotes priority for different users, and it is a fixed value for specified user j. Similarly if we choose proportional fairness as the metric, the optimization objective is to maxi￾mize j∈U wj ln Bj , which can be further denoted as  j∈U wj ln( 1 Tj  T 0 bj (t)d(t)). (2) The above two objectives are optimization metrics over the duration of service period for all users. As we aim to continuously construct optimized assignments of users to APs within this duration, we use the term “snapshot” to denote the small time interval 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. A. Snapshot Optimization for Efficiency We first prove a theorem. Theorem 1: For the efficiency metric, it is sufficient to maximize j∈U wj Tj bj (t) for each snapshot t to achieve the long-term optimization goal. Proof: For the efficiency metric, we are to maximize fO = j∈U wj Tj T 0 bj (t)d(t) according to (1). As wj and Tj are constants with time for each user j, we have fO =  j∈U  T 0 wj Tj bj (t)d(t) =  T 0  j∈U wj Tj bj (t)d(t). 326 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 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.

case(3)we prove by contradiction that new association control The constraints for bi(t)in(10)-(13)is similar to the formu- is not necessary.We denote the former equivalence class as lations of constraints for bi(t)in (4)-(7).the only difference Eqi and the new equivalence class as Egi.Assume in Eqi is we use the time interval t instead of snapshot t to depict some user will switch to a different AP for a new optimal the parameters in the constraints.The fractional solution of solution.Thus we can use new bandwidth allocation b,(t) Pij(t)for each bj(t)is the exact solution for association for users to improve the objective function(t) control in the lth interval for l=1,..,L,as we allow multiple (t).As only one original candidate AP is lost for handoffs within each interval to achieve the fractional solution. some user in Eqi,each user's candidate AP set for Egj is a Assume within any time interval[t,],there are K phases subset or equivalent set of the one for Egi.So we can apply of association control as AC1,AC2,...,ACK.In each phase this new solution to Egi,so as to further improve the objective ACk,for k =1,...,K,any user can associate with one unique function,but that contradicts with the fact that we already have AP as the integral solution.Hence we can utilize an integer optimal solution for Eqi.Thus the assumption does not hold. linear program (ILP)to figure out the optimized handoff the theorem gets proved. ■ strategies.Due to lack of space,we omit the ILP formulation According to Theorem 2,for the efficiency metric we only and the detail procedure to calculate the handoff strategies. have to compute the optimized association solution each time when one or more users cross the boundary of Eguivalence C.Online Algorithm for Proportional Fairness Classes.We can further prevent unnecessary computations by checking the special patterns of adjacent Equivalence Classes. From the above subsection we know that the exact optimal solution can only be achieved with information obtained over B.Offline Optimization for Proportional Fairness the whole time span (0,T)in advance.However,in practice In the above subsection we have demonstrated that for we cannot precisely know users'future mobility trajectory, the efficiency metric we can transform the long-term overall thus no information about which users will be contending for optimization into the snapshot optimization.However,for specified APs in the future can be obtained beforehand.In this proportional fairness,as each snapshot decision for the optimal subsection,according to the online setting described in Section solution may depend on its former and future situations.we III,we design an online algorithm.Our solution relies on the cannot simply conduct this transformation. following theorem. As illustrated in Fig.3,within each refined time interval Theorem 3:Maximizing the long-term objective function ]for I=1..L.the candidate AP sets and corre-((t)dt)is consistent with maximizing sponding bit rates for all users are fixed.We can devise a fixed pattern of association solution in an optimized approach. the long-term objective function(dt. Following the offline setting described in Section III,and Here.(t)dt denotes the accumulated bandwidth in time using the detailed information over the time span [0,T] span 0,t,w;denotes the original fixed weight as priority for given in advance,we devise an offline algorithm to achieve each user j,and e>0 is a small constant number. optimization for proportional fairness.Here we use bj.t to Proof:Using the fact that T is constant and settingj= denote the average bandwidth allocated in the time interval e+obj(t)dt,we have [ti_1,ti].and we define t=t-t1 for I 1,...,L.So we haveB).Since the objective is to 四b(t) dt wjbi(t) maximize iewj In Bj,we have e元e+6b(t)dt e+bj(t)dt L 7 Wj ∑wlnB,=∑wln(∑bt)-∑w;lhT d(e+ bj(t)dt) e+b(t)dt iEU jEU I=1 iEU re+j。bg(t)dt AsT is constant we can set the objective w1d） function as )Then we obtain the j following convex program formulation: =∑四nx,l+B6d marimize∑w,ln(∑b.l·t) jeU (9) l=0 ∑wn(e+ bi(t)dt)- (14) subject to jEU 5∈U,l∈{L,,Lb.1=∑r0p,(0 (10) iEA As e is constant,maximizing(14)is equivalent to maximizing i∈A,1∈{1，，L} ∑∑p,()≤1 (11) wj In(e+ bj(t)dt). (1 i∈U,le{1,,L} p5,(0≤1 (12) jEU 164 i∈A,1∈U,l∈{1，，L0≤p:,()≤1 (13) The theorem gets proved. 328 Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore.Restrictions apply

case (3) we prove by contradiction that new association control is not necessary. We denote the former equivalence class as Eqi and the new equivalence class as Eqj . Assume in Eqj some user will switch to a different AP for a new optimal solution. Thus we can use new bandwidth allocation b j (t) for users to improve the objective function j∈U wj Tj b j (t) > j∈U wj Tj bj(t). As only one original candidate AP is lost for some user in Eqj , each user’s candidate AP set for Eqj is a subset or equivalent set of the one for Eqi. So we can apply this new solution to Eqi, so as to further improve the objective function, but that contradicts with the fact that we already have optimal solution for Eqi. Thus the assumption does not hold, the theorem gets proved. 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 computations by checking the special patterns of adjacent Equivalence Classes. B. Offline Optimization for Proportional Fairness In the above subsection 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. As illustrated in Fig. 3, within each refined time interval [t l−1, t l] for l = 1, ..., L, the candidate AP sets and corre￾sponding bit rates for all users are fixed. We can devise a fixed pattern of association solution in an optimized approach. Following the offline setting described in Section III, and using the detailed information over the time span [0, T ] given in advance, we devise an offline algorithm to achieve optimization for proportional fairness. Here we use bj,l to denote the average bandwidth allocated in the time interval [t l−1, t l], and we define tl = t l − t l−1 for l = 1, ..., L. So we have Bj = 1 Tj L l=1 (bj,l · tl). Since the objective is to maximize j∈U wj ln Bj , we have  j∈U wj ln Bj =  j∈U wj ln( L l=1 bj,l · tl) −  j∈U wj ln Tj . As − j∈U wj ln Tj is constant, we can set the objective function as j∈U wj ln(L l=0 bj,l · tl). Then we obtain the following convex program formulation: maximize j∈U wj ln(L l=0 bj,l · tl) (9) subject to ∀j ∈ U, l ∈ {1, ..., L} bj,l =  i∈A ri,j (l) · pi,j (l) (10) ∀i ∈ A, l ∈ {1, ..., L}  j∈U pi,j (l) ≤ 1 (11) ∀j ∈ U, l ∈ {1, ..., L}  i∈A pi,j (l) ≤ 1 (12) ∀i ∈ A, j ∈ U, l ∈ {1, ..., L} 0 ≤ pi,j (l) ≤ 1 (13) The constraints for bj(tl) in (10)-(13) is similar to the formu￾lations of constraints for bj(t) in (4)-(7), the only difference is we use the time interval tl instead of snapshot t to depict the parameters in the constraints. The fractional solution of pi,j (tl) for each bj(tl) is the exact solution for association control in the lth interval for l = 1, .., L, as we allow multiple handoffs within each interval to achieve the fractional solution. Assume within any time interval [t l−1, t l], there are K phases of association control as AC1, AC2, ..., ACK. In each phase ACk, for k = 1, ..., K, any user can associate with one unique AP as the integral solution. Hence we can utilize an integer linear program (ILP) to figure out the optimized handoff strategies. Due to lack of space, we omit the ILP formulation and the detail procedure to calculate the handoff strategies. C. Online Algorithm for Proportional Fairness From the above subsection 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 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 subsection, according to the online setting described in Section III, we design an online algorithm. Our solution relies on the following theorem. Theorem 3: Maximizing the long-term objective function j∈U wj ln( + T 0 bj (t)dt) is consistent with maximizing the long-term objective function T 0 j∈U wj + t 0 bj (t)dt bj(t)dt. Here, 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. Proof: Using the fact that T is constant and setting xj = + t 0 bj (t)dt, we have  T 0  j∈U wj bj (t) + t 0 bj (t)dt dt =  j∈U  T 0 wj bj(t) + t 0 bj(t)dt dt =  j∈U  T 0 wj + t 0 bj(t)dt d( +  t 0 bj(t)dt) =  j∈U  + T 0 bj (t)dt wj xj d(xj ) =  j∈U wj ln xj | + T 0 bj (t)dt =  j∈U wj ln( +  T 0 bj (t)dt) −  j∈U wj ln . (14) As is constant, maximizing (14) is equivalent to maximizing  j∈U wj ln( +  T 0 bj (t)dt). (15) The theorem gets proved. 328 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore. Restrictions apply.