计算机科学与技术（参考文献）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.

Recall that the original long-term goal is to maximize of Bj,we can further obtain T bj(t)dt) (16) R= )t-∑西l血 bi(t)dt. o o The only difference between the above two objective functions Theorem 4:The upper bound of R=jeu wjIn Bj- (15)and (16)is e,which may have an impact on the corre- CjeU Wj In Bj for DWOA is sponding optimal solution.However,as long as we set e small enough (0)in (15),the long-term goal in (15)becomes wj.In(maz Tmaz. jEU TminImin 0 very near toe((t)dt). In order to maximize fod D时 where p nminjeu w,Tmin =minjeu(Tj),Tmar= ∑e0" we use the following heuristic snapshot objective fo maxjeU(Tj).rmin is the minimum value of bit rate,and rma ∑jeue+元，odb,(）along with the constraint depicted in 2， is the maximum value of bit rate. (4)-(8)to approximate the long-term optimization solution. Proof:Since DWOA attempts to maximize The intuition is that maximizing fo at each t contributes to Cjev wj In(e+(t)dt),we first define R(e)= the maximization of fo.We thus propose an online algorithm ju四ln(e+6t)d)-∑jeu四n(e+b,()d). DWOA based on dynamic weight W3(t)( We then have Since it is possible that bj(t)dt =0.we let e>0 to prevent Wi(t)from equal to +o0.This online algorithm is Rg=∑四，n+0d illustrated in Algorithm 1.Here Step 1 takes care of the +(t)dt fairness metric by setting Wi(t)inversely proportional to As()dt ≤ Tmar·rmaz and(t)dt≥ the accumulated bandwidth.Step 2 considers the efficiency metric by attempting to maximize the sum of the weighted minje(b(t)dt),we have bandwidths.We update the association solution for every At time interval.Conventionally the less At we use,the better R(e≤∑w·ln( e+Tmax·Tmaz jEU e+minjeu(fbj(t)dt) solution we can obtain,but the drawback is that it may cause too many handoffs. Then according to the definitions of R and R(e),we have Algorithm 1 DWOA:Dynamic Weight based Online Algo- R-Re)=∑西lm 防)d)·(e+b;()) rithm jEU (e+())·(。b)d) 1:t=0 2:while tw2 >..Wn. According to the algorithm,for the optimal snapshot solution, R=In IIjev(Bj) =∑wlhB防-∑w血B each aP will only allocate bandwidth to the user with the j∈U jEU largest weight Wi(t)within its range.As Wi(t)is changing all the time,we adopt the following procedure:user 1 first Here B;and B;respectively denotes the overall optimal get all the bandwidth from the AP until Wi(t)=W2(t). solution and the online solution.According to the definition then user 1 and 2 will further get bandwidth until Wi(t)= 329 Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore.Restrictions apply

Recall that the original long-term goal is to maximize  j∈U wj ln( T 0 bj (t)dt). (16) The only difference between the above two objective functions (15) and (16) is , which may have an impact on the corre￾sponding optimal solution. However, as long as we set small enough ( → 0) in (15), the long-term goal in (15) becomes very near to j∈U wj ln( T 0 bj(t)dt). In order to maximize fO = T 0 j∈U wj + t 0 bj (t)dt bj (t)dt, we use the following heuristic snapshot objective f O = j∈U wj + t 0 bj (t)dt bj(t) along with the constraint depicted in (4)-(8) to approximate the long-term optimization solution. The intuition is that maximizing f O at each t contributes to the maximization of fO. We thus propose an online algorithm DWOA based on dynamic weight Wj (t) = wj + t 0 bj (t)dt . Since it is possible that t 0 bj(t)dt = 0, we let > 0 to prevent Wj (t) from equal to +∞. This online algorithm is illustrated in Algorithm 1. Here Step 1 takes care of the fairness metric by setting Wj (t) inversely proportional to the accumulated bandwidth. Step 2 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. Algorithm 1 DWOA: Dynamic Weight based Online Algo￾rithm 1: t = 0 2: while t w2 > ... > wn. According to the algorithm, for the optimal snapshot solution, each AP will only allocate bandwidth to the user with the largest weight Wj (t) within its range. As Wj (t) is changing all the time, we adopt the following procedure: user 1 first get all the bandwidth from the AP until W1(t) = W2(t), then user 1 and 2 will further get bandwidth until W1(t) = 329 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore. Restrictions apply.

W2(t)=W3(t),...,finally we can achieve Wi(t)=W2(t)= propose a group-based approach that partitions the network ..=Wn(t).From then on,all users will share the bandwidth into groups.In each group,we apply the aforementioned LP distribution and keep Wi(t)=W2(t)=...=Wn(t),in this method so that the computation complexity will be reduced. way each user j further gets the bandwidth from the AP with In the rest of this section,as we only focus on the snapshot proporion In order to obtain mine()dt). solution,for the ease of presentation,we omit the "(t)"for we further assume that user n has the minimum service snapshot parameters in the formulas.Next,we give a formal duration T=minje(T),thus among all users jU definition of"group". user n obtains the least bandwidth. Definition 1.We say that a set of users belong to the same We denote the time interval [0,t*]during which user n group if and only if for any two users j'and j from the set. gets no bandwidth and [t,Tn]during which user n shares there is a series of users j1,j2,..j from the set such that the AP's bandwidth distribution.Thus during the interval A;∩Ai1≠p,A1∩Ai2≠p,,Aj.∩A≠o,where A, [0,t*],the total downloaded bits for user 1....,n-1 is is user j's candidate AP set. b(t)dt.As the minimum bit rate is rmin.we According to this definition,different groups are mutually obtain t*≤ 点∑gb,因d进At the time point,as exclusive (each user can only belong to one unique group)and Wi(t")=W2(=Wa(),according to the definition independent (users belonging to different groups will have no of Wi(t),we have shared candidate APs for contention).For any snapshot,the users over the roads can be divided into one or more groups. Wi i=1,2.,n-1, Wn Therefore our association control over all users is reduced to e+。5)成 association control within each group inferred by Theorem 5. Theorem 5:For snapshot solution of the efficiency metric Thus we getfb (t)dt=(-1)e,and further more and online solution of the fairness metric,the optimization achieved within each group is consistent with the overall 18) optimization. Tmin Wn jEU Due to lack of space,we omit the proof of Theorem 5. Now according to Eq.(18)we can estimate the minimum As we have learned from Section IV,both snapshot solution accumulated bandwidth among the users for efficiency and online solution for fairness can be unified in the formulation as to maximize Wjb for each bj(t)dt)>(Tn-t*). WnTmin snapshot.Here for efficiency,we have Wi=wj/Tj:and for ∑jeU proportional fairness,we have W WnTmin m()+( n·n -1)e 之jeU0 A.Breaking into Smaller Sub-Groups In a dense traffic scenario,the distance between adjacent Then according to Eq.(17),if we set p n:minjeU上，we users may be close to share some candidate APs,thus we have cannot divide them into separate groups.Hence we may still have extremely large-sized groups over the roads.In order to R≤∑wm7 e+rmarTmaz (p-1)e+prminTmin/n reduce the computation complexity,we need to break the large groups into smaller sub-groups.Therefore before we conduct Here since e is an adjustable parameter,it is possible to optimization with the linear program based method,we first determine an optimal value for e to minimize the bound.As perform pre-processing.For each user j,we delete those weak p≤l,when e→0，we can achieve the minimum value for links (i,j)with bit rate rij low enough to satisfy ri.j1 with an extremely large Wi-Fi deployment.For example, is a constant parameter.Wheny=1,the intuition is that according to polynomial-time algorithms for linear program from user j's perspective,even choosing i'as its own AP with like the ellipsoid method[17],the computation complexity is no contention is worse than contending for i*with ci users, O(N4.L).where N is the number of parameters and L is the so it is too weak to worth association.We use the constant length of encoding bits for parameters.For our optimization parameter y to control the effect for weak link eliminations. problems,we have N =m.n for all parameters pi.j,(m Actually the larger y is,the greater number of links will be is the number of APs and n is the number of users).Thus, deleted.Thus we are able to break a large group into more sub- if n and m are large enough,N will be a huge number and groups.After deleting these weak links,we check the bipartite the computation complexity will be tremendous.Hereby we graph G(V,E)of AP-user links corresponding to the original 330 Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore.Restrictions apply

W2(t) = W3(t), ..., finally we can achieve W1(t) = W2(t) = ... = Wn(t). From then on, all users will share the bandwidth distribution and keep W1(t) = W2(t) = ... = Wn(t), in this way each user j further gets the bandwidth from the AP with proportion wj j∈U wj . In order to obtain minj∈U ( T 0 bj(t)dt), we further assume that user n has the minimum service duration Tn = minj∈U (Tj ), thus among all users j ∈ U user n obtains the least bandwidth. We denote the time interval [0, t∗] during which user n gets no bandwidth and [t ∗, Tn] during which user n shares the AP’s bandwidth distribution. Thus during the interval [0, t∗], the total downloaded bits for user 1, ..., n − 1 is n−1 j=1 t∗ 0 bj(t)dt. As the minimum bit rate is rmin, we obtain t∗ ≤ 1 rmin n−1 j=1 t∗ 0 bj(t)dt. At the time point t∗, as W1(t∗) = W2(t∗) = ... = Wn(t∗), according to the definition of Wj (t), we have ∀j = 1, 2..., n − 1, wj + t∗ 0 bj (t)dt = wn . Thus we get t∗ 0 bj(t)dt = ( wj wn − 1), and further more t ∗ ≤ rmin ( 1 wn  j∈U wj − n). (18) Now according to Eq. (18) we can estimate the minimum accumulated bandwidth among the users min j∈U (  T 0 bj(t)dt) ≥ (Tn − t ∗) · wnrmin j∈U wj ≥ wnrmin j∈U wj min j∈U (Tj )+( wn · n j∈U wj − 1). Then according to Eq. (17), if we set ρ = n· minj∈U wj j∈U wj , we have R ≤  j∈U wj · ln[ + rmaxTmax (ρ − 1) + ρrminTmin/n]. Here since is an adjustable parameter, it is possible to determine an optimal value for to minimize the bound. As ρ ≤ 1, when → 0, we can achieve the minimum value for R’s upper bound as j∈U wj · ln( rmaxTmax rminTmin · n ρ ). V. GROUP-BASED APPROACH The above proposed snapshot solution as well as the online algorithm solution both require continuously solving a linear program for each snapshot. The computation complexity may be huge in our considered scenario, where we have to deal with an extremely large Wi-Fi deployment. For example, according to polynomial-time algorithms for linear program like the ellipsoid method[17], the computation complexity is O(N4 ·L), where N is the number of parameters and L is the length of encoding bits for parameters. For our optimization problems, we have N = m · n for all parameters pi,j , (m is the number of APs and n is the number of users). Thus, if n and m are large enough, N will be a huge number and the computation complexity will be tremendous. Hereby we propose a group-based approach that partitions the network into groups. In each group, we apply the aforementioned LP method so that the computation complexity will be reduced. In the rest of this section, as we only focus on the snapshot solution, for the ease of presentation, we omit the “(t)” for snapshot parameters in the formulas. Next, we give a formal definition of “group”. Definition 1. We say that a set of users belong to the same group if and only if for any two users j and j from the set, there is a series of users j1, j2, ..., js from the set such that Aj  Aj1 = φ, Aj1  Aj2 = φ, ..., Ajs  Aj = φ, where Aj is user j’s candidate AP set. According to this definition, different groups are mutually exclusive (each user can only belong to one unique group) and independent (users belonging to different groups will have no shared candidate APs for contention). For any snapshot, the users over the roads can be divided into one or more groups. Therefore our association control over all users is reduced to association control within each group inferred by Theorem 5. Theorem 5: For snapshot solution of the efficiency metric and online solution of the fairness metric, the optimization achieved within each group is consistent with the overall optimization. Due to lack of space, we omit the proof of Theorem 5. As we have learned from Section IV, both snapshot solution for efficiency and online solution for fairness can be unified in the formulation as to maximize j∈U Wj · bj for each snapshot. Here for efficiency, we have Wj = wj/Tj; and for proportional fairness, we have Wj = wj + t 0 bj (t)dt . A. Breaking into Smaller Sub-Groups In a dense traffic scenario, the distance between adjacent users may be close to share some candidate APs, thus we cannot divide them into separate groups. Hence we may still have extremely large-sized groups over the roads. In order to reduce the computation complexity, we need to break the large groups into smaller sub-groups. Therefore before we conduct optimization with the linear program based method, we first perform pre-processing. For each user j, we delete those weak links (i , j) with bit rate ri ,j low enough to satisfy ri ,j < βj · maxi∈Aj ri,j . Here, maxi∈Aj ri,j is the maximum bit rate that user j can achieve within its candidate AP set Aj , and βj =  γ/ci∗ If ci∗ ≥ γ 1 If ci∗ < γ (19) where i ∗ is the specific AP with the maximum bit rate, ci∗ is the number of users within AP i ∗’s effective range, and γ ≥ 1 is a constant parameter. When γ = 1, the intuition is that from user j’s perspective, even choosing i as its own AP with no contention is worse than contending for i ∗ with ci∗ users, so it is too weak to worth association. We use the constant parameter γ to control the effect for weak link eliminations. Actually the larger γ is, the greater number of links will be deleted. Thus we are able to break a large group into more sub￾groups. After deleting these weak links, we check the bipartite graph G(V,E) of AP-user links corresponding to the original 330 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore. Restrictions apply.

large group.Here V denotes the set of users and APs,and According to Lemma 1, E denotes links after weak link eliminations.If the graph is disconnected somewhere due to the effect of weak link ∑WP≤∑∑Wnd=∑W elimination,we will obtain new sub-groups. jEGiES jEG iES B.Approximation Ratio Analysis Then Assume that for any user j in the original optimized solution without edge removal,we have bandwidth b;for the fractional ∑W动≤∑W6+∑Wrp jEG iEG jEGiEA-S solution and b;for the integral solution;and similarly in the approximate solution with edge removal,we have bandwidth Thus by the definition of weak link (i,j)with i Aj-Sj. b,for the fractional solution and b for the integral solution. we have ri.j<月j·Rj,where R=maxicA,ri,j·Then For both the efficiency and fairness metrics,we define the Liec Wy.by approximation ratio as Apparently the ratio is at ∑wb≤∑W6+∑(3RwW,·∑p jEG jEG jEG iEAj-Sy least 1 as∑iecW:6;≥∑jecW:g,since the candidate link set for the original solution is a superset of the one for Since∑ieA,-S,P,i≤1，then approximate solution.In the following we give an upper bound for this approximation ratio. ∑Wb≤∑W4+∑WR For any user j.we denote Aj as its original candidate AP jEG jEG jEG set,and S,as a subset of A;for the remaining candidate AP set after the weak link elimination.Thus A;-Sj is the As we have ∑jecW;·b≤∑jecW·bj because the set of those eliminated candidate APs.We respectively utilize fractional optimal solution can always achieve a better result matrix Pi.j and p to denote the optimized parameters for the than the integral optimal solution,then original solution and the approximate solution.Then according EoWE<EaWb<∑EaWb+ΣEewB to the definition we have ∑jecW-b ∑jecW6 ∑ecWb b=∑ipj=∑rp+∑ Ti.jpi.j iEA iES iEA-S We set 0= to be the approximation ratio for the (20) ∑1EGWb rounding algorithms proposed by Shmoy and Tardos[16],and =∑r,=∑r (21)1≤0≤2.So. iEA iES, We have the property in Lemma 1. ∑jecW· s0+eo西÷R Lemma 1:For optimal parameters pi.j in set Si for the ∑jecW,· ∑jecW· original solution and optimal parameters p;in set Sj for the approximate solution,W After the weak link elimination,the optimal integral solution may come with a worst case,where a bunch of users share only ∑jeg∑es,Wr: Proof:After removing some weak links,those pij with one candidate AP which has the largest bit rate for any of them, iSj corresponding to the weak links are set to 0. with the other candidate APs all eliminated.Then the optimal method for each user j is to select the unique AP with Ri Consequently some constraints for the remaining pi.j with iE Sj get relaxed.We can then add a slack value to adjust which is the largest for j.Thus we have jWj pij to pj so as to further increase the objective function as the lower bound for the optimal result jW.So. sW which at least can remain the same by setting p=pij.Therefore the objective function of the ∑ieGW·6 s0+ ∑ecW·÷·B optimal solution should be equal to or larger than the previous ∑jecW· ∑，ecW品 <0+1 one,ie.∑jec∑ies,Wrpi≤∑jec∑ies,Wri,P The lemma gets proved. ■ Therefore we obtain the approximation ratio as +y, Theorem 6:For the snapshot solution of the weight based where yy is a constant.This indicates we can well control the objective function,the upper bound of the approximation ratio approximation ratio by adjusting y. ■ for group breaking is 0+,where is the approximation ratio for the rounding algorithm in Shmoy and Tardos[16]. C.Computation Complexity Proof:According to Eq.(20)and Eq.(21), Note that the number of variables for the original linear ∑Wb=∑∑Wr+∑∑Wp program is N m.n.After the weak link elimination,we jEG jEGiES j∈GiEA-S can break a large group of APs and users into sub-groups G1,G2,...,Gk.For each group Gi (1 <i<k),we have mi ∑W6=∑∑Wp APs and ni users.Thus,the number of variables for the linear jEGiES program is NmSuppose the expected number 331 Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore.Restrictions apply

large group. Here V denotes the set of users and APs, and E denotes links after weak link eliminations. If the graph is disconnected somewhere due to the effect of weak link elimination, we will obtain new sub-groups. B. Approximation Ratio Analysis Assume that for any user j in the original optimized solution without edge removal, we have bandwidth bj for the fractional solution and ˆbj for the integral solution; and similarly in the approximate solution with edge removal, we have bandwidth b j for the fractional solution and ˆb j for the integral solution. For both the efficiency and fairness metrics, we define the approximation ratio as j∈G Wj ·b ˆ j j∈G Wj · ˆb j . Apparently the ratio is at least 1 as j∈G Wj · ˆbj ≥ j∈G Wj · ˆb j, since the candidate link set for the original solution is a superset of the one for approximate solution. In the following we give an upper bound for this approximation ratio. For any user j, we denote Aj as its original candidate AP set, and Sj as a subset of Aj for the remaining candidate AP set after the weak link elimination. Thus Aj − Sj is the set of those eliminated candidate APs. We respectively utilize matrix pi,j and p i,j to denote the optimized parameters for the original solution and the approximate solution. Then according to the definition we have bj =  i∈Aj ri,j · pi,j =  i∈Sj ri,j · pi,j +  i∈Aj−Sj ri,j · pi,j (20) b j =  i∈Aj ri,j · p i,j =  i∈Sj ri,j · p i,j . (21) We have the property in Lemma 1. Lemma 1: For optimal parameters pi,j in set Sj for the original solution and optimal parameters p i,j in set Sj for the approximate solution, j∈G i∈Sj Wj ri,jpi,j ≤ j∈G i∈Sj Wj ri,jp i,j . Proof: After removing some weak links, those pi ,j with i ∈/ Sj corresponding to the weak links are set to 0. Consequently some constraints for the remaining pi,j with i ∈ Sj get relaxed. We can then add a slack value to adjust pi,j to p i,j so as to further increase the objective function j∈G i∈Sj Wj ri,jpi,j , which at least can remain the same by setting p i,j = pi,j. Therefore the objective function of the optimal solution should be equal to or larger than the previous one, i.e. j∈G i∈Sj Wj ri,jpi,j ≤ j∈G i∈Sj Wj ri,jp i,j . The lemma gets proved. Theorem 6: For the snapshot solution of the weight based objective function, the upper bound of the approximation ratio for group breaking is θ+γ, where θ is the approximation ratio for the rounding algorithm in Shmoy and Tardos[16]. Proof: According to Eq. (20) and Eq. (21),  j∈G Wj bj =  j∈G  i∈Sj Wj ri,j · pi,j +  j∈G  i∈Aj−Sj Wj ri,j · pi,j .  j∈G Wj b j =  j∈G  i∈Sj Wj ri,j · p i,j . According to Lemma 1,  j∈G  i∈Sj Wj ri,jpi,j ≤  j∈G  i∈Sj Wj ri,jp i,j =  j∈G Wj b j. Then  j∈G Wj bj ≤  j∈G Wj b j +  j∈G  i∈Aj−Sj Wj ri,j · pi,j . Thus by the definition of weak link (i, j) with i ∈ Aj − Sj , we have ri,j < βj · Rj , where Rj = maxi∈Aj ri,j . Then  j∈G Wj bj ≤  j∈G Wj b j +  j∈G (βjRjWj ·  i∈Aj−Sj pi,j ). Since i∈Aj−Sj pi,j ≤ 1, then  j∈G Wj bj ≤  j∈G Wj b j +  j∈G WjβjRj . As we have j∈G Wj · b j ≤ j∈G Wj · bj because the fractional optimal solution can always achieve a better result than the integral optimal solution, then j∈G Wj ·b j j∈G Wj · b j ≤ j∈G Wj ·bj j∈G Wj · b j ≤ j∈G Wj ·b j+ j∈G Wj ·βj·Rj j∈G Wj · b j . We set θ = j∈G Wj ·b j j∈G Wj · b j to be the approximation ratio for the rounding algorithms proposed by Shmoy and Tardos[16], and 1 ≤ θ ≤ 2. So, j∈G Wj · b j j∈G Wj · b j ≤ θ + j∈G Wj · γ ci∗ · Rj j∈G Wj · b j . After the weak link elimination, the optimal integral solution may come with a worst case, where a bunch of users share only one candidate AP which has the largest bit rate for any of them, with the other candidate APs all eliminated. Then the optimal method for each user j is to select the unique AP with Rj , which is the largest ri,j for j. Thus we have j∈G Wj · Rj ci∗ as the lower bound for the optimal result j∈G Wj · b j . So, j∈G Wj · b j j∈G Wj · b j ≤ θ + j∈G Wj · γ ci∗ · Rj j∈G Wj · Rj ci∗ ≤ θ + γ Therefore we obtain the approximation ratio as θ + γ, where γ is a constant. This indicates we can well control the approximation ratio by adjusting γ. C. Computation Complexity Note that the number of variables for the original linear program is N = m · n. After the weak link elimination, we can break a large group of APs and users into sub-groups G1, G2, ..., Gk. For each group Gi (1 ≤ i ≤ k), we have mi APs and ni users. Thus, the number of variables for the linear program is N = k i=1 mi · ni. Suppose the expected number 331 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore. Restrictions apply.

of sub-groups is K.The expected computation complexity can least one AP,and that their peak bit rates range from 1000kpbs be calculated as follows. to 3500kbps for vehicular users.In our simulation,we simulate K K a total of 100 users driving over these roads with speed ranged E(N')=E()T mi·ni) E(mi·ni from 40km/h to 100km/h.and utilize a Poisson Process with =1 i=1 parameter A to simulate the series of vehicular users within Assume m;and n;are independent. We have E(mi·n:)= time span [0h,10h].On average,every 10/A second a new E(m)·E(ni),then user will drive into this region.Among these multiple roads, each user randomly selects the trajectory for driving.We solve K m n m·n the linear program and convex program using MATLAB. E(N)= E(m)·E(n)=K K i=1 The ellipsoid method which effectively solves the linear pro- gram,given the number of parameters N,has a computation Strongest Signal First -Integral Optimal Soltion complexity of O(N4).By using group breaking,the compu- ◆Ofline Opfir-Solutio tation complexity is reduced to O(). VI.PRACTICAL CONSIDERATION IN REALISTIC SETTINGS We have already shown how to reduce the computational complexity in computing the optimal association control,but processing the requests on a single server for a large number of (a) (b) vehicles and APs is still a challenging problem.In this section, we discuss how to distribute computational load in practice.In Fig.4.Performance comparison for (a)efficiency,(b)proportional fairness order to alleviate the bottleneck on the central server,we apply the following framework based on the group-based approach to distribute the load.We deploy a primary server and multiple A.Efficiency and Fairness secondary servers,which are connected to the APs via wired In Fig.4(a)and Fig.4(b)we respectively evaluate perfor- back-haul links.When a mobile user first joins the network, mance of our optimal strategies for efficiency and fairness it arbitrarily associates with a nearby AP.The mobile users We compare performance with two heuristic strategies.The continuously upload their current information (i.e.,position, first strategy is Connect Until Broken(CUB),which maintains speed,candidate APs,etc.)to the primary server through a connection with a user and an aP until the user considers the current associated AP.The primary server processes the the link to be broken.Upon disconnection,the user will be bipartite network graph and breaks it into non-intersecting associated with a new AP which yields the largest signal subgraphs.Then the primary sever dispatches these subgraphs strength.The second strategy is Strongest Signal First(SSF), to various secondary servers.Due to the mutually exclusive and which always associates a user with the AP yielding the independent properties,those secondary servers can calculate strongest received signal strength at all times.Fig.4(a)shows the association solutions in parallel.After that the secondary the result for the efficiency metric,where the X axis is the servers send the updated solutions to the users through their time span as users are driving over the roads and the Y current connections,then the users apply the updated solutions. axis is the users'total received data measured in GBits.For Therefore,assuming the number of subgroups is k and the ease of comparison,we set wj=1 and Ti=1h for the computation for the K groups can be fully parallelized, each user,so comparing the total received bits is equal to according to the analysis in Section V-C,the computational comparing the overall throughput.We observe that the integral time can be greatly reduced tos of the original approaches. optimal solution outperforms both the SSF solution and the If the primary server can always limit the size of subgroups CUB solution.The SSF solution achieves about 70%of the to a fixed number,the computational overhead can be kept as total throughput of the integral optimal solution,while the a constant value. CUB solution always performs worst for it only reaches 38% of the total throughput in comparison with the integral optimal VII.PERFORMANCE EVALUATIONS solution.Fig.4(b)shows the result for the proportional fairness We have implemented a simulator to simulate the Drive- metric,where the X axis is the user index and the Y axis thru Internet scenario over a Wi-Fi deployed square region is users'throughput in Kbps.The users are sorted by their (20km x 20km)covered with 10 roads.Among them 5 roads throughput in increasing order.For the ease of comparison, are along the east-west direction and 5 roads are along the we set wj=1 for each user.For the online algorithm we set north-west direction,thus forming 5 x 5 intersections within e=0.01 and every 5 second we recalculate the association the square region.We randomly place a total of 2000 APs solution.We observe that although the two heuristics have over these roads and adopt the experiment results from [2]to similar growth trend as our optimal solutions,and that both simulate effective bit rates of APs.We make sure that at any the offline optimal solution and online solution outperform the location of the roads the user is within effective range of at two heuristic solutions for overall throughput.For instance, 332 Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore.Restrictions apply

of sub-groups is K. The expected computation complexity can be calculated as follows. E(N ) = E(  K i=1 mi · ni) =  K i=1 E(mi · ni) Assume mi and ni are independent. We have E(mi · ni) = E(mi) · E(ni), then E(N ) =  K i=1 E(mi) · E(ni) = K · m K · n K = m · n K = N K The ellipsoid method which effectively solves the linear pro￾gram, given the number of parameters N, has a computation complexity of O(N4). By using group breaking, the compu￾tation complexity is reduced to O( N4 K4 ). VI. PRACTICAL CONSIDERATION IN REALISTIC SETTINGS We have already shown how to reduce the computational complexity in computing the optimal association control, but processing the requests on a single server for a large number of vehicles and APs is still a challenging problem. In this section, we discuss how to distribute computational load in practice. In order to alleviate the bottleneck on the central server, we apply the following framework based on the group-based approach to distribute the load. We deploy a primary server and multiple secondary servers, which are connected to the APs via wired back-haul links. When a mobile user first joins the network, it arbitrarily associates with a nearby AP. The mobile users continuously upload their current information (i.e., position, speed, candidate APs, etc.) to the primary server through the current associated AP. The primary server processes the bipartite network graph and breaks it into non-intersecting subgraphs. Then the primary sever dispatches these subgraphs to various secondary servers. Due to the mutually exclusive and independent properties, those secondary servers can calculate the association solutions in parallel. After that the secondary servers send the updated solutions to the users through their current connections, then the users apply the updated solutions. Therefore, assuming the number of subgroups is K and the computation for the K groups can be fully parallelized, according to the analysis in Section V-C, the computational time can be greatly reduced to 1 K5 of the original approaches. If the primary server can always limit the size of subgroups to a fixed number, the computational overhead can be kept as a constant value. VII. PERFORMANCE EVALUATIONS We have implemented a simulator to simulate the Drive￾thru Internet scenario over a Wi-Fi deployed square region (20km × 20km) covered with 10 roads. Among them 5 roads are along the east-west direction and 5 roads are along the north-west direction, thus forming 5 × 5 intersections within the square region. We randomly place a total of 2000 APs over these roads and adopt the experiment results from [2] to simulate effective bit rates of APs. We make sure that at any location of the roads the user is within effective range of at least one AP, and that their peak bit rates range from 1000kpbs to 3500kbps for vehicular users. In our simulation, we simulate a total of 100 users driving over these roads with speed ranged from 40km/h to 100km/h, and utilize a Poisson Process with parameter λ to simulate the series of vehicular users within time span [0h, 10h]. On average, every 10/λ second a new user will drive into this region. Among these multiple roads, each user randomly selects the trajectory for driving. We solve the linear program and convex program using MATLAB. 0 2 4 6 8 10 0 50 100 150 200 250 Time Span (hour) Total Throughput (GBits) Connect Until Broken Strongest Signal First Integral Optimal Solution 0 20 40 60 80 100 0 100 200 300 400 500 600 User Index Throughput for Each User (kbit/s) Connect Until Broken Strongest Signal First Online Algorithm Solution Offline Optimal Solution (a) (b) Fig. 4. Performance comparison for (a) efficiency, (b) proportional fairness A. Efficiency and Fairness In Fig. 4(a) and Fig. 4(b) we respectively evaluate perfor￾mance of our optimal strategies for efficiency and fairness. We compare performance with two heuristic strategies. The first strategy is Connect Until Broken (CUB), which maintains a connection with a user and an AP until the user considers the link to be broken. Upon disconnection, the user will be associated with a new AP which yields the largest signal strength. The second strategy is Strongest Signal First (SSF), which always associates a user with the AP yielding the strongest received signal strength at all times. Fig. 4(a) shows the result for the efficiency metric, where the X axis is the time span as users are driving over the roads and the Y axis is the users’ total received data measured in GBits. For the ease of comparison, we set wj = 1 and Tj = 1h for each user, so comparing the total received bits is equal to comparing the overall throughput. We observe that the integral optimal solution outperforms both the SSF solution and the CUB solution. The SSF solution achieves about 70% of the total throughput of the integral optimal solution, while the CUB solution always performs worst for it only reaches 38% of the total throughput in comparison with the integral optimal solution. Fig. 4(b) shows the result for the proportional fairness metric, where the X axis is the user index and the Y axis is users’ throughput in Kbps. The users are sorted by their throughput in increasing order. For the ease of comparison, we set wj = 1 for each user. For the online algorithm we set = 0.01 and every 5 second we recalculate the association solution. We observe that although the two heuristics have similar growth trend as our optimal solutions, and that both the offline optimal solution and online solution outperform the two heuristic solutions for overall throughput. For instance, 332 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore. Restrictions apply.

the median user's bandwidth value of the online algorithm We observe that it is much smaller than the worst case ratio solution is 69%higher than the SSF solution and 300%higher +y,which demonstrates for conventional cases we achieve than the CUB solution.The offline optimal solution has better tight bound for the expected approximation ratio. performance than the online solution.since the median user's bandwidth value of the former is 12.9%higher than the latter. VIII.CONCLUSION In this paper,we conduct a theoretical research on associa- tion control over the Drive-thru Internet scenario.We consider lambda-0.2 一ambh both efficiency and fairness metrics,and present corresponding offline and online solutions to achieve overall optimization objectives.We further propose an approximation algorithm for group breaking in order to reduce computation complexity. ACKNOWLEDGMENTS 0.5 1.5 0.5 Value of gamma 15 Value af gamma This project was supported in part by US National Sci- (a)Compute complexity (b)Approximate ratio ence Foundation grants CNS-0721443,CNS-0831904,CA- REER Award CNS-0747108.CNS-0434533.CNS-0531410. +-lambds-1 and CNS-0626240,the China 973 project(2009CB320705, 2006CB303000),the China NSF grant(90718031,60721002 D.E 60573106.60573132,60873026). REFERENCES 0 (1]V.Bychkovsky,B.Hull,A.Miu,H.Balakrishnan,and S.Madden Vae gamma 15 "A measurement study of vehicular intemet access using in situ Wi- Fi networks,"in ACM Proc.of MOBICOM.2006. (c)Compute complexity (d)Approximate ratio [2]J.Ott and D.Kutscher,"Drive-thru internet:IEEE 802.11b for 'auto. mobile'users."in IEEE Proc.of INFOCOM.2004. [3]A.Giannoulis,M.Fiore,and E.W.Knightly."Supporting vehicular Fig.5.Performance evaluation for group breaking approximate algorithm mobility in urban multi-hop wireless networks."in ACM Proc.of MobiSys.2008. [4]L.Tassiulas and S.Sarkar,"Maxmin fair scheduling in wireless ad hoc B.Group Breaking Mechanism networks,"IEEE Journal on Selected Areas in Communications (JSAC). vol.23,no.1,Pp.163-173,2005 In Fig.5 we evaluate the performance for the group breaking [5]Y.Bejerano,S.-J.Han,and L.Li,"Fairess and load balancing in wireless LANs using association control."IEEE/ACM Trans.Netw. approximate algorithm in terms of computation complexity (T0W,vol.15,no.3,Pp.560-573,2007. and approximate ratio.Here we normalize the computation [6]L.Li,M.Pal,and Y.R.Yang,"Proportional fairness in multi-rate complexity as a ratio between the complexity after group wireless LANs,"in IEEE Proc.of INFOCOM,2008. [7 breaking and the original complexity.We respectively con- J.Eriksson,H.Balakrishnan,and S.Madden,"Cabernet:vehicular content delivery using Wi-Fi,"in ACM Proc.of MOBICOM,2008. sider two conventional cases with different A for the Poisson [8]J.Ott and D.Kutscher,"A disconnection-tolerant transport for drive-thru Process.For the sparse case with =0.2,the average internet environments,"in IEEE Proc.of INFOCOM,2005 [9]R.Mahajan,J.Zahorjan,and B.Zill,"Understanding WiFi-based distance between adjacent users is large,thus we can break connectivity from moving vehicles."in Proc.of IMC.2007. the large group of users into many sub-groups.As Fig.5 [10]D.Hadaller,S.Keshav,T.Brecht,and S.Agarwal,"Vehicular op- (a)shows,when y varies from 0 to 0.6,the computation portunistic communication under the microscope,"in ACM Proc.of complexity reduces dramatically from I to 0.1,and when MobiSys,2007. [11]M.Kim,Z.Liu,S.Parthasarathy,D.Pendarakis,and H.Yang,"Associa- further increases from 0.6 to 2,as many of the weak links has tion control in mobile wireless networks."in IEEE Proc.of INFOCOM. already been eliminated,the computation complexity reduces 2008. gently.As Fig.5(b)shows,when y varies from 0 to 1.4,the [12]V.Navda,A.P.Subramanian,K.Dhanasekaran,A.Timm-Giel,and S.R Das,"Mobisteer:using steerable beam directional antenna for vehicular average approximate ratio keeps close to 1 as those weak link network access,"in IEEE Proc.of MobiSys.2007 deleted among the sparse group of users will not impact on [13]L.B.Jiang and S.C.Liew,"Proportional fairness in wireless LANs and the final optimal solution,and when y further increases from ad hoc networks,"in IEEE Proc.of WCNC,2005. [14]T.Nandagopal,T.-E.Kim,X.Gao,and V.Bharghavan,"Achieving mac 1.4 to 2,the approximate ratio grows slightly from 1 to 1.25. layer fairness in wireless packet networks."in ACM Proc.of MobiCom. For the dense case with A=1,the average distance between 2000,pp.87-98. [15]R.Murty,J.Padhye,A.Wolman,and B.Zill,"Designing high perfor- adjacent users is rather small so that eliminating some weak mance enterprise Wi-Fi networks,"in ACM Proc.of NSDI,2008. links will not be enough to break the large group of users [16]D.B.Shmoys and E.Tardos."An approximation algorithm for the into many sub-groups.As Fig.5 (c)shows,the computation generalized assignment problem,"Math.Program.vol.62,no.3.pp. 461-474,1993. complexity first reduces gently when y increases from 0 to 6. [17]W.H.Freeman,"Linear programming."1983. then reduces dramatically when y increases from 6 to 10 due to weak links,and finally the computation complexity reduces slightly.As Fig.5(d)shows,when y varies from 0 to 20,the averaged approximate ratio grows near linearly from I to 1.32. 333 Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore.Restrictions apply

the median user’s bandwidth value of the online algorithm solution is 69% higher than the SSF solution and 300% higher than the CUB solution. The offline optimal solution has better performance than the online solution, since the median user’s bandwidth value of the former is 12.9% higher than the latter. 0 0.5 1 1.5 2 0 0.2 0.4 0.6 0.8 1 Value of gamma Complexity comparison ratio lambda=0.2 0 5 10 15 20 0 0.2 0.4 0.6 0.8 1 Value of gamma Complexity comparison ratio lambda=1 0 0.5 1 1.5 2 0.5 1 1.5 Value of gamma Approximation ratio lambda=0.2 0 5 10 15 20 0.5 1 1.5 2 Value of gamma Approximation ratio lambda=1 (a) Compute complexity (c) Compute complexity (b) Approximate ratio (d) Approximate ratio Fig. 5. Performance evaluation for group breaking approximate algorithm B. Group Breaking Mechanism In Fig. 5 we evaluate the performance for the group breaking approximate algorithm in terms of computation complexity and approximate ratio. Here we normalize the computation complexity as a ratio between the complexity after group breaking and the original complexity. We respectively con￾sider two conventional cases with different λ for the Poisson Process. For the sparse case with λ = 0.2, the average distance between adjacent users is large, thus we can break the large group of users into many sub-groups. As Fig. 5 (a) shows, when γ varies from 0 to 0.6, the computation complexity reduces dramatically from 1 to 0.1, and when γ further increases from 0.6 to 2, as many of the weak links has already been eliminated, the computation complexity reduces gently. As Fig. 5 (b) shows, when γ varies from 0 to 1.4, the average approximate ratio keeps close to 1 as those weak link deleted among the sparse group of users will not impact on the final optimal solution, and when γ further increases from 1.4 to 2, the approximate ratio grows slightly from 1 to 1.25. For the dense case with λ = 1, the average distance between adjacent users is rather small so that eliminating some weak links will not be enough to break the large group of users into many sub-groups. As Fig. 5 (c) shows, the computation complexity first reduces gently when γ increases from 0 to 6, then reduces dramatically when γ increases from 6 to 10 due to weak links, and finally the computation complexity reduces slightly. As Fig. 5 (d) shows, when γ varies from 0 to 20, the averaged approximate ratio grows near linearly from 1 to 1.32. We observe that it is much smaller than the worst case ratio θ + γ, which demonstrates for conventional cases we achieve tight bound for the expected approximation ratio. VIII. CONCLUSION In this paper, we conduct a theoretical research on associa￾tion control over the Drive-thru Internet scenario. We consider both efficiency and fairness metrics, and present corresponding offline and online solutions to achieve overall optimization objectives. We further propose an approximation algorithm for group breaking in order to reduce computation complexity. ACKNOWLEDGMENTS This project was supported in part by US National Sci￾ence Foundation grants CNS-0721443, CNS-0831904, CA￾REER Award CNS-0747108, CNS-0434533, CNS-0531410, and CNS-0626240, the China 973 project (2009CB320705, 2006CB303000), the China NSF grant (90718031, 60721002, 60573106, 60573132, 60873026). REFERENCES [1] V. Bychkovsky, B. Hull, A. Miu, H. Balakrishnan, and S. Madden, “A measurement study of vehicular internet access using in situ Wi￾Fi networks,” in ACM Proc. of MOBICOM, 2006. [2] J. Ott and D. Kutscher, “Drive-thru internet: IEEE 802.11b for ‘auto￾mobile’ users,” in IEEE Proc. of INFOCOM, 2004. [3] A. Giannoulis, M. Fiore, and E. W. Knightly, “Supporting vehicular mobility in urban multi-hop wireless networks,” in ACM Proc. of MobiSys, 2008. [4] L. Tassiulas and S. Sarkar, “Maxmin fair scheduling in wireless ad hoc networks,” IEEE Journal on Selected Areas in Communications (JSAC), vol. 23, no. 1, pp. 163–173, 2005. [5] Y. Bejerano, S.-J. Han, and L. Li, “Fairness and load balancing in wireless LANs using association control,” IEEE/ACM Trans. Netw. (TON), vol. 15, no. 3, pp. 560–573, 2007. [6] L. Li, M. Pal, and Y. R. Yang, “Proportional fairness in multi-rate wireless LANs,” in IEEE Proc. of INFOCOM, 2008. [7] J. Eriksson, H. Balakrishnan, and S. Madden, “Cabernet: vehicular content delivery using Wi-Fi,” in ACM Proc. of MOBICOM, 2008. [8] J. Ott and D. Kutscher, “A disconnection-tolerant transport for drive-thru internet environments,” in IEEE Proc. of INFOCOM, 2005. [9] R. Mahajan, J. Zahorjan, and B. Zill, “Understanding WiFi-based connectivity from moving vehicles,” in Proc. of IMC, 2007. [10] D. Hadaller, S. Keshav, T. Brecht, and S. Agarwal, “Vehicular op￾portunistic communication under the microscope,” in ACM Proc. of MobiSys, 2007. [11] M. Kim, Z. Liu, S. Parthasarathy, D. Pendarakis, and H. Yang, “Associa￾tion control in mobile wireless networks,” in IEEE Proc. of INFOCOM, 2008. [12] V. Navda, A. P. Subramanian, K. Dhanasekaran, A. Timm-Giel, and S. R. Das, “Mobisteer: using steerable beam directional antenna for vehicular network access,” in IEEE Proc. of MobiSys, 2007. [13] L. B. Jiang and S. C. Liew, “Proportional fairness in wireless LANs and ad hoc networks,” in IEEE Proc. of WCNC, 2005. [14] T. Nandagopal, T.-E. Kim, X. Gao, and V. Bharghavan, “Achieving mac layer fairness in wireless packet networks,” in ACM Proc. of MobiCom, 2000, pp. 87–98. [15] R. Murty, J. Padhye, A. Wolman, and B. Zill, “Designing high perfor￾mance enterprise Wi-Fi networks,” in ACM Proc. of NSDI, 2008. [16] D. B. Shmoys and E. Tardos, “An approximation algorithm for the generalized assignment problem,” Math. Program, vol. 62, no. 3, pp. 461–474, 1993. [17] W. H. Freeman, “Linear programming,” 1983. 333 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore. Restrictions apply