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.