1324 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,VOL.22,NO.8,AUGUST 2011 and fairness.We show some major simulation results in Effective Bit Rates(kbits/s) Section 5,and we conclude the paper in Section 6. Entry Phase Production Phase Exit Phase 2 RELATED WORK Association control and scheduling solutions for Wireless LANs (WLAN)have been intensely studied,mainly targeting the efficiency and fairness metrics.Tassiulas and Sarkar consider the max-min fair allocation of bandwidth in wireless ad hoc networks [3].Bejerano 220m 3(m 220m et al.present an efficient solution to determine the user- Distance(m) AP association for the max-min fair bandwidth allocation Fig.1.Three connectivity phases. [4].Li et al.consider proportional fairness for WLANs [5]. Internet access with vehicular speeds in the IEEE 802.11 networks have been studied in recent research works. may vary over the time.Thus while users are driving along Bychkovsky et al.study the case for vehicular clients to the roads,at different time instants and positions,they may connect to open-access residential wireless 802.11 access be contending with different users for bandwidth from points in Boston [6],[7].Giannoulis et al.address the different APs.Each user associates with the first AP after first problem of maintaining client performance at vehicular entering the Wi-Fi deployment area,then goes through a speeds within city-wide multihop 802.11 networks [8].Ott series of handoffs among different APs while driving along and Kutscher report on measurements for the use of 802.11 the roads,and disconnects at the last associated aP before networks in the Drive-thru Internet scenario [1.Mahajan leaving the Wi-Fi deployment area.In this paper,we seek a et al.deploy a modest-size test bed and analyze the series of optimized association solutions based on under- fundamental characteristics of WiFi-based connectivity lying technologies [13],[14]to conduct fast handoffs,which between base stations and vehicles in urban settings [9]. can limit the handoff delay within several milliseconds,so Hadaller et al.show that by exploiting wireless conditions, that the handoffs can be performed at a small cost. vehicular opportunistic access can be greatly improved We denote the set of APs as A indexed by i=1,...,m [10].Navda et al.investigate the use of directional and denote the set of users as U indexed by j=1,...,n. antennas and beam steering techniques to improve We consider association control over the time interval performance of 802.11 links in the context of communica- [0,T].For example,0 and T may,respectively,denote 0: tion between a moving vehicle and roadside APs [11].Kim 00 and 24:00 time points of every day.For each AP-user et al.present novel association control algorithms that pair (i,j),we assume that the effective bit rate rij(t)of minimize the frequency of handoffs occurred to mobile the link between i and j at time t is known.The effective devices [12].Deshpande et al.exploit historical information bit rate is measured over a fairly long time period and to develop new handoff and data transfer strategies for also takes into account the overhead of retransmissions improved vehicular WiFi access [13].Wu et al.have due to reception errors.We use bj(t)to denote the developed a fast handoff scheme called Proactive Scan to bandwidth allocated to user j at time t.Both bit rate and reduce the handoff delay [14].In the supplementary bandwidth can be measured in bits per second (bit/s). material,which can be found on the Computer Society For bandwidth allocation inside each AP,we use time- Digital Library at http://doi.ieeecomputersociety.org/ based fairness for scheduling.Once an AP is associated 10.1109/TPDS.2011.17,the related works are introduced with some users,each user is assigned an equal-sized in a more comprehensive approach. time slot regardless its effective bit rate,and is supposed to use all the allocated bandwidth.Thus,if n'users are 3 PERFORMANCE MODELS AND METRICS associated with AP i at time t,then the bandwidth 3.1 Models and Assumptions allocated to user j is bi(t)=rij(t)/n'. For the effective bit rate setting in the Drive-thru Internet In the Drive-thru Internet scenario,vehicular users are driving scenario,we adopt the model proposed in [1].Fig.1 depicts through a region covered with multiple roads,and APs are three different connectivity phases with respect to effective deployed along the roads nonuniformly by the service bit rate and relative distance between the user and AP.The provider.Each AP has a limited coverage range and it can entry phase and exit phase provide very weak connectivity, only serve users in its coverage area.We assume a careful only the production phase provides a window of useful frequency planning where interfering APs are assigned to connectivity.As the connection is built between a user and orthogonal channels so that adjacent APs can fully utilize an aP,it will maintain a constant bit rate in the production their bandwidth without causing interference to each other. phase,which mainly depends on the AP's signal strength Conventionally,each user on the roads may have one or and the user's driving speed.Conventionally the faster the more candidate APs to associate with at any time,and each user's speed is,the lower bit rate the user can achieve.The time the user can only associate with exactly one AP.bit rate can basically keep fixed while the user's speed does Furthermore,contentions for transmission may exist among not change too much.Therefore,for each specified user we users if they associate with the same AP.If a large number of can approximately model the bit rates of APs as square users associate with the same aP,their allocated bandwidths waves.As Fig.2 shows,we allow nonuniform AP will be greatly reduced.We assume that different users have deployments along any user's driving trajectory which various velocities (including speeds and directions)which include effective ranges,neighbor distances,and effectiveand fairness. We show some major simulation results in Section 5, and we conclude the paper in Section 6. 2 RELATED WORK Association control and scheduling solutions for Wireless LANs (WLAN) have been intensely studied, mainly targeting the efficiency and fairness metrics. Tassiulas and Sarkar consider the max-min fair allocation of bandwidth in wireless ad hoc networks [3]. Bejerano et al. present an efficient solution to determine the user￾AP association for the max-min fair bandwidth allocation [4]. Li et al. consider proportional fairness for WLANs [5]. Internet access with vehicular speeds in the IEEE 802.11 networks have been studied in recent research works. Bychkovsky et al. study the case for vehicular clients to connect to open-access residential wireless 802.11 access points in Boston [6], [7]. Giannoulis et al. address the problem of maintaining client performance at vehicular speeds within city-wide multihop 802.11 networks [8]. Ott and Kutscher report on measurements for the use of 802.11 networks in the Drive-thru Internet scenario [1]. Mahajan et al. deploy a modest-size test bed and analyze the fundamental characteristics of WiFi-based connectivity between base stations and vehicles in urban settings [9]. Hadaller et al. show that by exploiting wireless conditions, vehicular opportunistic access can be greatly improved [10]. Navda et al. investigate the use of directional antennas and beam steering techniques to improve performance of 802.11 links in the context of communica￾tion between a moving vehicle and roadside APs [11]. Kim et al. present novel association control algorithms that minimize the frequency of handoffs occurred to mobile devices [12]. Deshpande et al. exploit historical information to develop new handoff and data transfer strategies for improved vehicular WiFi access [13]. Wu et al. have developed a fast handoff scheme called Proactive Scan to reduce the handoff delay [14]. In the supplementary material, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/ 10.1109/TPDS.2011.17, the related works are introduced in a more comprehensive approach. 3 PERFORMANCE MODELS AND METRICS 3.1 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 nonuniformly by the service provider. Each AP has a limited coverage range and it can only serve users in its coverage area. We assume a careful frequency planning where interfering APs are assigned to orthogonal channels so that adjacent APs can fully utilize their bandwidth without causing interference to each other. 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 handoffs among different APs while driving along the roads, and disconnects at the last associated AP before leaving the Wi-Fi deployment area. In this paper, we seek a series of optimized association solutions based on under￾lying technologies [13], [14] to conduct fast handoffs, which can limit the handoff delay within several milliseconds, so that the handoffs can be performed at a small cost. We denote the set of APs as A indexed by i ¼ 1; ... ; m and denote the set of users as U indexed by j ¼ 1; ... ; n. We consider association control over the time interval ½0; T. For example, 0 and T may, respectively, denote 0 : 00 and 24 : 00 time points of every day. For each AP-user pair ði; jÞ, we assume that the effective bit rate ri;jðtÞ of the link between i and j at time t is known. The effective bit rate is measured over a fairly long time period and also takes into account the overhead of retransmissions due to reception errors. 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 with 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 n0 users are associated with AP i at time t, then the bandwidth allocated to user j is bjðtÞ ¼ ri;jðtÞ=n0 . For the effective bit rate setting in the Drive-thru Internet scenario, we adopt the model proposed in [1]. Fig. 1 depicts three different connectivity phases with respect to effective bit rate and relative distance between the user and AP. 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. Conventionally the faster the user’s speed is, the lower bit rate the user can achieve. 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 1324 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 22, NO. 8, AUGUST 2011 Fig. 1. Three connectivity phases.