EEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,VOL.22,NO.8,AUGUST 2011 1323 Association Control for Vehicular WiFi Access: Pursuing Efficiency and Fairness Lei Xie,Member,IEEE,Qun Li,Member,IEEE,Weizhen Mao Jie Wu,Fellow,IEEE,and Daoxu Chen,Member,IEEE Abstract-Deploying road-side WiFi 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 WiFi access in the Drive-thru Internet scenario.In particular,we aim to improve the efficiency and fairness for all users.We design efficient algorithms to achieve these objectives through several techniques including approximation.Our simulation results demonstrate that our algorithms can achieve significantly better performance than conventional approaches. Index Terms-Association control,vehicular network,efficiency,fairness. 1 INTRODUCTION [MPROVEMENTS in wireless technology have made it possible there is little work on how to manage AP association in this Lto deploy wireless networks spanning an entire metropo- type of "Vehicular Networks".We believe that a thorough litan area.The availability of anywhere,anytime,wireless theoretical study on this problem is highly necessary for the connectivity will create new categories of users.One such future deployment of vehicular networks.Some pitfalls can category is called "Drive-thru Internet"[1],which provides be avoided in real deployment if we have a better wireless access to users in moving vehicles through road-side understanding first. deployed APs.These vehicular users encounter unique This paper aims to define a theoretical framework to challenges not faced by conventional indoor users,such as analyze the performance of a vehicular network in the Drive- dynamically changing network structure of AP-user pairing thru Internet scenario,in particular to investigate association and contentions among mobile users.Unlike a wireless control schemes.Considering both the long-term efficiency network comprising of static or slow moving users,vehicular and fairness metrics,we propose optimized schemes to users are continuously moving at high speeds,making associate mobile users with APs,and approximation algo- existing AP selection and handoff algorithms unsuitable. rithms to reduce computation complexity of calculating In order to achieve reasonable efficiency among multiple optimal solutions.To the best of our knowledge,this is the vehicular users for the above Drive-thru Internet scenario, first theoretical work that investigates the optimization several problems should be considered,e.g.,rate adapta- problem for association control in vehicular networks.The tion and association control.Association control defines, contributions of this paper are summarized as follows: while multiple users are driving along the road,how to intelligently associate vehicular users to APs and when to 1. Since the association solutions are updated fre- appropriately conduct handoffs for users to improve the quently while the users are driving along the roads, overall system performance.Compared with rate adapta- this paper is concerned about the long-term perfor- tion [2],which adapts the modulation and coding scheme mance in terms of efficiency and fairness,and according to the quality of the radio channel,association proposes novel algorithms to achieve these long- control considers the entire network from a macrolevel term objectives. perspective,which shows how to optimize system perfor- 2. We propose a theoretical framework for association mance from a higher level viewpoint.We notice that,albeit control over vehicular networks.For the efficiency some recent work on association control for static networks, metric,the problem is transformed into an optimiza- tion problem for each snapshot over the long-term service duration.For the fairness metric,we .L.Xie and D.Chen are with the State Key Laboratory of Novel Software respectively,consider the optimization solutions Technology,Department of Computer Science and Technology,Nanjing for proportional fairness and max-min fairness. University,Nanjing 210093,China. E-mail:Ixie@nju.edu.cn,cdx@nju.edu.cn 3. When the involved number of mobile users and APs O.Li and W.Mao are with the Department of Computer Science, along the road is rather large,to reduce the McGlothlin-Street Hall,College of William and Mary,Williamsburg,VA 23187-8795.E-mail:(liqun,wmJ@cs.wm.edu. computation complexity,we propose an approxima- J.Wu is with the Department of Computer and Information Science, tion algorithm to break the large contention group Temple University,1805 N.Broad ST.,Philadelphia,PA 19122. into smaller subgroups,achieving a trade-off be- E-mail:jiewu@temple.edu. tween accuracy and computation complexity. Manuscript received 14 Sept.2009;revised 9 June 2010;accepted 15 July The rest of the paper is organized as follows:We briefly 2010;published online 3 Jan.2011. present related work in Section 2.We define the perfor- Recommended for acceptance by S.Olariu. For information on obtaining reprints of this article,please send e-mail to: mance metrics and introduce our model and assumptions in tpds@computer.org,and reference IEEECS Log Number TPDS-2009-09-0422. Section 3.We illustrate our overall optimization and Digital Object Identifier no.10.1109/TPDS.2011.17. snapshot solutions in Section 4,respectively,for efficiency 1045-9219/11/S26.002011EEE Published by the IEEE Computer Society
Association Control for Vehicular WiFi Access: Pursuing Efficiency and Fairness Lei Xie, Member, IEEE, Qun Li, Member, IEEE, Weizhen Mao, Jie Wu, Fellow, IEEE, and Daoxu Chen, Member, IEEE Abstract—Deploying road-side WiFi 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 WiFi access in the Drive-thru Internet scenario. In particular, we aim to improve the efficiency and fairness for all users. We design efficient algorithms to achieve these objectives through several techniques including approximation. Our simulation results demonstrate that our algorithms can achieve significantly better performance than conventional approaches. Index Terms—Association control, vehicular network, efficiency, fairness. Ç 1 INTRODUCTION I MPROVEMENTS in wireless technology have made it possible to deploy wireless networks spanning an entire metropolitan area. The availability of anywhere, anytime, wireless connectivity will create new categories of users. One such category is called “Drive-thru Internet” [1], which provides wireless access to users in moving vehicles through road-side deployed APs. These vehicular users encounter unique challenges not faced by conventional indoor users, such as dynamically changing network structure of AP-user pairing and contentions among mobile users. Unlike a wireless network comprising of static or slow moving users, vehicular users are continuously moving at high speeds, making existing AP selection and handoff algorithms unsuitable. 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 vehicular users to APs and when to appropriately conduct handoffs for users to improve the overall system performance. Compared with rate adaptation [2], which adapts the modulation and coding scheme according to the quality of the radio channel, association control considers the entire network from a macrolevel 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 manage AP association in this type of “Vehicular Networks”. We believe that a thorough theoretical study on this problem is highly necessary for the future deployment of vehicular networks. Some pitfalls can be avoided in real deployment if we have a better understanding first. This paper aims to define a theoretical framework to analyze the performance of a vehicular network in the Drivethru Internet scenario, in particular to investigate association control schemes. Considering both the long-term efficiency and fairness metrics, we propose optimized schemes to associate mobile users with APs, and approximation algorithms to reduce computation complexity of calculating optimal solutions. To the best of our knowledge, this is the first theoretical work that investigates the optimization problem for association control in vehicular networks. The contributions of this paper are summarized as follows: 1. Since the association solutions are updated frequently while the users are driving along the roads, this paper is concerned about the long-term performance in terms of efficiency and fairness, and proposes novel algorithms to achieve these longterm objectives. 2. 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. For the fairness metric, we, respectively, consider the optimization solutions for proportional fairness and max-min fairness. 3. 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 subgroups, achieving a trade-off between accuracy and computation complexity. The rest of the paper is organized as follows: We briefly present related work in Section 2. We define the performance metrics and introduce our model and assumptions in Section 3. We illustrate our overall optimization and snapshot solutions in Section 4, respectively, for efficiency IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 22, NO. 8, AUGUST 2011 1323 . L. Xie and D. Chen are with the State Key Laboratory of Novel Software Technology, Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China. E-mail: lxie@nju.edu.cn, cdx@nju.edu.cn. . Q. Li and W. Mao are with the Department of Computer Science, McGlothlin-Street Hall, College of William and Mary, Williamsburg, VA 23187-8795. E-mail: {liqun, wm}@cs.wm.edu. . J. Wu is with the Department of Computer and Information Science, Temple University, 1805 N. Broad ST., Philadelphia, PA 19122. E-mail: jiewu@temple.edu. Manuscript received 14 Sept. 2009; revised 9 June 2010; accepted 15 July 2010; published online 3 Jan. 2011. Recommended for acceptance by S. Olariu. For information on obtaining reprints of this article, please send e-mail to: tpds@computer.org, and reference IEEECS Log Number TPDS-2009-09-0422. Digital Object Identifier no. 10.1109/TPDS.2011.17. 1045-9219/11/$26.00 2011 IEEE Published by the IEEE Computer Society
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 effective
and 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 userAP 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 communication 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 underlying 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 timebased 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.
XIE ET AL.:ASSOCIATION CONTROL FOR VEHICULAR WIFI ACCESS:PURSUING EFFICIENCY AND FAIRNESS 1325 Effective Bit Rates (kbits/s) online settings of the optimization problem.In the offline AP2 setting,we assume that we know the mobility patterns and AP4 trajectories of vehicular users in advance,in other words, AP3 AP5 we are given the candidate AP set Aj(t)for each user j at each time t0,T]as part of the problem input.In the online setting,each Aj(t)is revealed only at time t,at which time instant we have to instantaneously select an AP from A;(t)to associate for each user j,without any knowledge of Fig.2.Nonuniform AP deployments along user's driving trajectory. the future sets Aj(t')for t'[t,T]. bit rates.We then divide these regions into nonoverlapping 4 OVERALL OPTIMIZATION AND SNAPSHOT Equivalence Classes as Eq,Eg2,...,Egn.Each Eqi denotes a SOLUTION section of the roads,and within each section the candidate AP set and corresponding effective bit rates will keep fixed For the efficiency metric,with a set of vehicular users U on for the specified user. the roads,the objective is to maximizeBj which can be further denoted as 3.2 Performance Metrics We consider two performance metrics in this study: b;(t)dt. (1) efficiency and fairness.Efficiency is measured with the overall throughput received by all users,and fairness is to regulate the association control so that all users have a fair Here wj denotes priority for different users,and it is a fixed distribution of bandwidth as much as possible. value for user j.Similarly,if we choose proportional fairness as the metric,the optimization objective is to For efficiency,we aim to maximize the overall through- put for all vehicular users.The throughput for any user is maximize Bj,which can be further denoted as the average message delivery rate during the user's service period and it is usually measured in bits per second.Hence j(t)dt (2) for any user j,given the service duration [tj,tj+Ti]and the allocated bandwidth bi(t)at time t[tj,tj+Til,we can The above two objectives are optimization metrics over express the throughput B for user jas B()d. the duration of service period for all users.We use the term Consider the overall time interval (0,T],during intervals "long-term"to denote the overall time interval the user gets service.As we aim to continuously construct optimized [0,ti]and [tj+Ti,T],we actually have bj(t)=0,thus we assignments of users to APs within this duration,we use have an equivalent uniform notion as B=b(t)dt. the term "snapshot"to denote the time instant within which Association control without considering fairness may we have to make a decision about aP association for all lead to the starvation of users with poor signal strength.To users.Thus,it is necessary for us to find solutions for each consider fairness,two metrics are used frequently in snapshot to achieve the overall optimal performance. literature:max-min fairness [4]and proportional fairness 4.1 Snapshot Optimization for Efficiency [5].Suppose the throughput allocation for all n users can be denoted as a vector B=(B1,B2,...,B).For max-min We first prove a theorem. fairness,an allocation B is "max-min fair"if and only if an Theorem 1.For the efficiency metric,it is sufficient to maximize increase of any throughput within the domain of feasible (t)for each snapshot t to achieve the long-term optimization goal. allocations must be at the cost of a decrease of some already smaller throughput.For proportional fairness,an The proof of Theorem 1 can be found in the supplemen- allocation B is "proportionally fair"if and only if,for any tary material,which can be found on the Computer Society other feasible allocation.In other words, Digital Library at http://doi.ieeecomputersociety.org/ any change in the allocation must have a negative average 10.1109/TPDS.2011.17.Theorem 1 essentially tells us that change.It has been proved that the unique proportionally we can optimize for efficiency metric in each snapshot to fair allocation can be obtained by maximizing(B)=achieve overall performance.In the offline setting,we In(Bj)over the set of feasible allocations [15]. already know Ti in the objective function.In the online Since all APs are deployed by the same organization,a setting,we have to estimate T;based on the user's current centralized control scheme is possible as proposed in [16]. speed vj(t).Suppose user j gives the driving trajectory to Therefore based on the above models and assumptions, the centralized server through devises like GPS.Knowing assuming we are the service provider of the specified the overall distance S;and the distance s;(t)that user j has region,we aim to build a centralized association control traveled at time t,we can continuously estimate T;for user j system and our goal is to continuously construct optimized at snapshot t using T(t)=t.In case that the vi(t) assignments of APs to users as they are driving along the vehicular user stops at traffic lights,we maintain a window roads,respectively,taking the efficiency and fairness of speeds for recent k snapshots,and use the average speed metrics into consideration.We consider both offline and v;(t)to estimate Ti(t)
bit rates. We then divide these regions into nonoverlapping Equivalence Classes as Eq1; Eq2; ... ; Eqn. Each Eqi denotes a section of the roads, and within each section the candidate AP set and corresponding effective bit rates will keep fixed for the specified user. 3.2 Performance Metrics We consider two performance metrics in this study: efficiency and fairness. Efficiency is measured with the overall throughput received by all users, and fairness is to regulate the association control so that all users have a fair distribution of bandwidth as much as possible. For efficiency, we aim to maximize the overall 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. Hence for any user j, given the service duration ½tj; tj þ Tj and the allocated bandwidth bjðtÞ at time t 2 ½tj; tj þ Tj, we can express the throughput Bj for user j as Bj ¼ 1 Tj R tjþTj tj bjðtÞdt. Consider the overall time interval ½0; T, during intervals ½0; tj and ½tj þ Tj; T, we actually have bjðtÞ ¼ 0, thus we have an equivalent uniform notion as Bj ¼ 1 Tj R T 0 bjðtÞdt. Association control without considering fairness may lead to the starvation of users with poor signal strength. To consider fairness, two metrics are used frequently in literature: max-min fairness [4] and proportional fairness [5]. Suppose the throughput allocation for all n users can be denoted as a vector B~ ¼ hB1; B2; ... ; Bni. For max-min fairness, an allocation B~ is “max-min fair” if and only if an increase of any throughput within the domain of feasible allocations must be at the cost of a decrease of some already smaller throughput. For proportional fairness, an allocation B~ is “proportionally fair” if and only if, for any other feasible allocation B~0 , PjB~j j¼1 B0 jBj Bj 0. In other words, any change in the allocation must have a negative average change. It has been proved that the unique proportionally fair allocation can be obtained by maximizing JðB~Þ ¼ P j lnðBjÞ over the set of feasible allocations [15]. Since all APs are deployed by the same organization, a centralized control scheme is possible as proposed in [16]. Therefore based on the above models and assumptions, assuming we are the service provider of the specified region, we aim to build a centralized association control system and our goal is to continuously construct optimized assignments of APs to users as they are driving along the roads, respectively, taking the efficiency and fairness metrics into consideration. We consider both offline and online settings of the optimization problem. In the offline setting, we assume that we know the mobility patterns and trajectories of vehicular users in advance, in other words, we are given the candidate AP set AjðtÞ for each user j at each time t 2 ½0; T as part of the problem input. In the online setting, each AjðtÞ is revealed only at time t, at which time instant we have to instantaneously select an AP from AjðtÞ to associate for each user j, without any knowledge of the future sets Ajðt 0 Þ for t 0 2 ½t; T. 4 OVERALL OPTIMIZATION AND SNAPSHOT SOLUTION For the efficiency metric, with a set of vehicular users U on the roads, the objective is to maximize P j2U wjBj, which can be further denoted as X j2U wj Tj Z T 0 bjðtÞdt: ð1Þ Here wj denotes priority for different users, and it is a fixed value for user j. Similarly, if we choose proportional fairness as the metric, the optimization objective is to maximize P j2U wj ln Bj, which can be further denoted as X j2U wj ln 1 Tj Z T 0 bjðtÞdt : ð2Þ The above two objectives are optimization metrics over the duration of service period for all users. We use the term “long-term” to denote the overall time interval the user gets service. As we aim to continuously construct optimized assignments of users to APs within this duration, we use the term “snapshot” to denote the time instant within which we have to make a decision about AP association for all users. Thus, it is necessary for us to find solutions for each snapshot to achieve the overall optimal performance. 4.1 Snapshot Optimization for Efficiency We first prove a theorem. Theorem 1. P For the efficiency metric, it is sufficient to maximize j2U wj Tj bjðtÞ for each snapshot t to achieve the long-term optimization goal. The proof of Theorem 1 can be found in the supplementary material, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/ 10.1109/TPDS.2011.17. Theorem 1 essentially tells us that we can optimize for efficiency metric in each snapshot to achieve overall performance. In the offline setting, we already know Tj in the objective function. In the online setting, we have to estimate Tj based on the user’s current speed vjðtÞ. Suppose user j gives the driving trajectory to the centralized server through devises like GPS. Knowing the overall distance Sj and the distance sjðtÞ that user j has traveled at time t, we can continuously estimate Tj for user j at snapshot t using TjðtÞ ¼ SjsjðtÞ vj ðtÞ þ t. In case that the vehicular user stops at traffic lights, we maintain a window of speeds for recent k snapshots, and use the average speed vjðtÞ to estimate TjðtÞ. XIE ET AL.: ASSOCIATION CONTROL FOR VEHICULAR WIFI ACCESS: PURSUING EFFICIENCY AND FAIRNESS 1325 Fig. 2. Nonuniform AP deployments along user’s driving trajectory.
1326 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,VOL.22,NO.8,AUGUST 2011 To describe the constraints in this problem formulation Time scale 0T1 T3T4 for each snapshot t,we formulate the association problem T5 T6T7 T8T9 T10 TIIT12T'13 T into a linear program(LP)as proposed in [5].We use a Eql Eq2 Eo3 E04 fractional variable pij(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 pij(t)is a fraction between 0 and 1; if user j is not associated with i,then the fraction is 0.Since 43 each user j is assigned to only one AP for the integral Un solution,there is exactly one nonzero pij(t)for each iA. We can first relax this constraint and assume that one user Fig.3.Time line for users to drive through the Equivalence Classes. can associate with multiple APs for the fractional solution. Then the bandwidth bj(t)allocated to each user j can be generality,we assume that the boundaries of an AP's depicted as bj(t)=ieArij(t)pij(t).Thus,we can obtain a effective range will not coincide with the others.Fig.3 fractional solution from the following linear program shows an example of the vehicular scenario,where a set of formulation: users U1,U2,...,Un are driving through various Equivalence Classes over the time span [0,T].As the time intervals for marimize ∑9b,0, (3) each user to drive through the Equivalence Classes may overlap with each other,hence for ease of analysis we can further divide the overall time span (0,T]into smaller time subject to intervals according to the boundaries of Equivalence Classes VjEU b=∑r)·p) (4 over the time span.We denote these time intervals as icA [To:Ti],[T,T2],....[TL_1,Ti],where To=0 and T =T.We i∈A ∑P因≤1， rely on the following theorem to devise an efficient handoff (5 jE strategy for efficiency metric. YjEU ∑P≤1， (6) Theorem 2.For optimal association control to maximize the iE efficiency metric,handoffs to new association solutions for users i∈A,j∈U0≤P(t)≤1， (7) only happen when at least one user is crossing the boundaries of jeUb(t)≥C Equivalence Classes.At each boundary the user will meet (8) with one of the following cases:1)new candidate AP is detected; Constraint(4)defines b;(t),the bandwidth allocated to user 2)original optimal AP is lost;and 3)original candidate AP is j at time point t.Constraint (5)means that the overall lost.For cases 1)and 2),new association control is necessary. allocated time fraction of each AP i to all users cannot be For case 3),new association control is not needed,so the original more than 1.Constraint(6)states that the overall allocated optimized solution holds. time fraction of each user j that communicates with all APs cannot be more than 1.Constraint (7)shows that the time The proof of Theorem 2 can be found in the supplemen- fraction is between 0 and 1.To ensure that every user is tary material,which can be found on the Computer Society able to maintain connectivity to the internet within the Digital Library at http://doi.ieeecomputersociety.org/ service duration,(8)guarantees that every user has 10.1109/TPDS.2011.17.According to Theorem 2,for the a minimum bandwidth of C at any time t,where C is a efficiency metric we only have to compute the optimized constant value for the lower bound.For the pure efficiency association solution each time when one or more users cross goal we set C=0 by default. the boundary of Equivalence Classes.We can further prevent For completeness,we describe briefly in the following how unnecessary computation by checking the special patterns to find the integral solution based on the fractional solution. of adjacent Equivalence Classes. After we obtain pij(t)for each user-AP pair,we can further calculate the fractional assignment(t)=,which 4.2 Online Algorithm for Proportional Fairness b:(t) In the above section,we have demonstrated that for the reflects the fraction of user i's total bandwidth that it expects efficiency metric we can transform the long-term overall to get from AP i.Apparently 0<ij(t)<1.We can view the optimization into the snapshot optimization.However,for assignment as a bipartite graph.Then,the final integral proportional fairness,as each snapshot decision for the solution is a set of binary variablesij(t)for all user-AP pairs, optimal solution may depend on its former and future wherei(t)is equal to 1if user j is associated with APiand0 situations,we cannot simply conduct this transformation. otherwise.We use the rounding algorithm proposed by We know that the exact optimal solution can only be Shmoy and Tardos [17]to calculate the integral solution achieved with information obtained over the whole time (t).Readers can refer to [5]for detailed description. span [0,T]in advance.However,in practice we cannot Since we have obtained the optimized strategy for precisely know the users'future mobility trajectory,thus no association control over each snapshot,we need to consider information about which users will be contending for the handoff strategy for efficiency.Continuously,comput-specified APs in the future can be obtained beforehand.In ing the optimized association solution for each snapshot is this section,according to the online setting described in the definitely not an appropriate solution,as it incurs too much end of Section 3,we design an online algorithm.Our computing and communication cost.Without loss of solution relies on the following theorem
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 [5]. 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 nonzero pi;jðtÞ for each i 2 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Þ ¼ P i2A ri;jðtÞpi;jðtÞ. Thus, we can obtain a fractional solution from the following linear program formulation: maximize X j2U wj Tj bjðtÞ; ð3Þ subject to 8j 2 U bjðtÞ ¼ X i2A ri;jðtÞ pi;jðtÞ; ð4Þ 8i 2 A X j2U pi;jðtÞ 1; ð5Þ 8j 2 U X i2A pi;jðtÞ 1; ð6Þ 8i 2 A; j 2 U 0 pi;jðtÞ 1; ð7Þ 8j 2 U bjðtÞ C: ð8Þ Constraint (4) defines bjðtÞ, the bandwidth allocated to user j at time point t. Constraint (5) means that the overall allocated time fraction of each AP i to all users cannot be more than 1. Constraint (6) states that the overall allocated time fraction of each user j that communicates with all APs cannot be more than 1. Constraint (7) 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, (8) 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 with AP i and 0 otherwise. We use the rounding algorithm proposed by Shmoy and Tardos [17] to calculate the integral solution x^i;jðtÞ. Readers can refer to [5] for detailed description. Since we have obtained the optimized strategy for association 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 assume that the boundaries of an 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 driving through various Equivalence Classes over the time span ½0; T. As the time intervals for each user to drive through the Equivalence Classes may overlap with each other, hence for ease of analysis we can further 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 ½T0 0; T0 1; ½T0 1; T0 2; ... ; ½T0 L1; T0 L, where T0 0 ¼ 0 and T0 L ¼ T. 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. The proof of Theorem 2 can be found in the supplementary material, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/ 10.1109/TPDS.2011.17. 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 computation by checking the special patterns of adjacent Equivalence Classes. 4.2 Online Algorithm for Proportional Fairness In the above section, 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. 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 the 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 section, according to the online setting described in the end of Section 3, we design an online algorithm. Our solution relies on the following theorem. 1326 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 22, NO. 8, AUGUST 2011 Fig. 3. Time line for users to drive through the Equivalence Classes.
XIE ET AL.:ASSOCIATION CONTROL FOR VEHICULAR WIFI ACCESS:PURSUING EFFICIENCY AND FAIRNESS 1327 Theorem 3.Maximizing the long-term objective function Algorithm 1 DWOA:Dynamic Weight based Online Algorithm (9 1:t=0 2:while tis a small constant number. 4.3 Online Algorithm for Max-Min Fairness The proof of Theorem 3 can be found in the supplemen- Since max-min fairness is also a frequently used metric for tary material,which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/ fairness,for completeness,in this section we consider the 10.1109/TPDS.2011.17.Recall that the original long-term approach to achieve long-term max-min fairness.The goal is to maximize intuition of max-min fairness for the Drive-thru Internet scenario is to maximize the throughput allocated to those bj(t)dt (10) users that receive the minimum throughput.As it has been proved by Bejerano et al.[4]that the problem of finding a max-min fair integral association is NP-hard,thus we The only difference between the above two objective functions (9)and (10)is e,which may have an impact on consider an online algorithm to approximately achieve the max-min fairness. the corresponding optimal solution.However,as long as we Assume at each snapshot t,each user j has his set e small enough (-0)in (9),the long-term goal in (9) becomes very near to jewj(b(t)dt). accumulated bandwidth obj(t)dt and current service In order to maximize duration Ti(t).We define a user j to be saturated when ∑CEAPiJ=1ori∈A,∑ieUP=1.In other words,,a user j is saturated only when j has used all his time fraction fo= bj(t)dt, 0 je+bj(t)dt to connect to APs or no remaining time fraction of his candidate APs can be further allocated to j.Algorithm 2 we use the following heuristic snapshot objective illustrates the online algorithm to achieve long-term max- f6)=∑ bj(t). min fairness.We update the association solution for every e+bj(t)dt At time interval.For each snapshot t,we sort the users according to nondecreasing order of along with the constraint depicted in (4)-(8)to approx- imate the long-term optimization solution.The intuition is that maximizing fo(t)at each t contributes to the 当s马h maximization of fo.We thus propose an algorithm based 四5·T(t) on the dynamic weight which is the current allocated throughput normalized by W(t)= 世方 the weight,and we denote the reordered users as e+bj(t)dt 1,2,...,j,....,n.Then we try to allocate fractional resource Since it is possible thatb(t)dt=0,we let e>0 to prevent Pij(t)(iE A)to each user j in a progressive filling approach. Wi(t)from equal to +00.This online algorithm called We start from user 1 and try to allocate resource to user 1 as Dynamic Weight based Online Algorithm (DWOA)is much as possible until illustrated in Algorithm 1.Here,Line 3 takes care of the fairness metric by setting Wi(t)inversely proportional to the -6)t+∑eAr,nA accumulated bandwidth.Line 4 considers the efficiency w·T(t) -=2 metric by attempting to maximize the sum of the weighted or user 1 is saturated with available resources.We further bandwidths.We update the association solution for every allocate resource to user 1 (if user 1 is not yet saturated, At time interval.Conventionally the less At we use,the better solution we can obtain,but the drawback is that it otherwise we stop allocation for user 1)and user 2 as much may cause too many handoffs.In the supplementary file, as possible until any of the users is saturated or which can be found on the Computer Society Digital =y.We continue this progressive filling procedure Library at http://doi.ieeecomputersocietyorg/10.1109until all available resources have been allocated or all of the TPDS.2011.17,we further provide the performance analysis users are saturated.For each round we use parameterto of DWOA and introduce the offline optimization for denote the indices for the involved users 1,2,...,J in proportional fairness. progressive filling
Theorem 3. Maximizing the long-term objective function X j2U wj ln þ Z T 0 bjðtÞdt ; ð9Þ is consistent with maximizing the long-term objective function Z T 0 X j2U wj þ R t 0 bjðtÞdt bjðtÞdt: Here, R 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. The proof of Theorem 3 can be found in the supplementary material, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/ 10.1109/TPDS.2011.17. Recall that the original long-term goal is to maximize X j2U wj ln Z T 0 bjðtÞdt : ð10Þ The only difference between the above two objective functions (9) and (10) is , which may have an impact on the corresponding optimal solution. However, as long as we set small enough ( ! 0) in (9), the long-term goal in (9) becomes very near to P j2U wj lnð R T 0 bjðtÞdtÞ. In order to maximize fO ¼ Z T 0 X j2U wj þ R t 0 bjðtÞdt bjðtÞdt; we use the following heuristic snapshot objective f0 OðtÞ ¼ X j2U wj þ R 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 f0 OðtÞ at each t contributes to the maximization of fO. We thus propose an algorithm based on the dynamic weight WjðtÞ ¼ wj þ R t 0 bjðtÞdt: Since it is possible that R t 0 bjðtÞdt ¼ 0, we let > 0 to prevent WjðtÞ from equal to þ1. This online algorithm called Dynamic Weight based Online Algorithm (DWOA) is illustrated in Algorithm 1. Here, Line 3 takes care of the fairness metric by setting WjðtÞ inversely proportional to the accumulated bandwidth. Line 4 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. In the supplementary file, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/10.1109/ TPDS.2011.17, we further provide the performance analysis of DWOA and introduce the offline optimization for proportional fairness. 4.3 Online Algorithm for Max-Min Fairness Since max-min fairness is also a frequently used metric for fairness, for completeness, in this section we consider the approach to achieve long-term max-min fairness. The intuition of max-min fairness for the Drive-thru Internet scenario is to maximize the throughput allocated to those users that receive the minimum throughput. As it has been proved by Bejerano et al. [4] that the problem of finding a max-min fair integral association is NP-hard, thus we consider an online algorithm to approximately achieve the max-min fairness. Assume at each snapshot t, each user j has his accumulated bandwidth R t 0 bjðtÞdt and current service duration TjðtÞ. We define a user j to be saturated when P i2A pi;j ¼ 1 or 8i 2 Aj; P j0 2U pi;j0 ¼ 1. In other words, a user j is saturated only when j has used all his time fraction to connect to APs or no remaining time fraction of his candidate APs can be further allocated to j. Algorithm 2 illustrates the online algorithm to achieve long-term maxmin fairness. We update the association solution for every t time interval. For each snapshot t, we sort the users according to nondecreasing order of yj ¼ R t 0 bjðtÞdt wj TjðtÞ ; which is the current allocated throughput normalized by the weight, and we denote the reordered users as 1; 2; ... ; j; ... :; n. Then we try to allocate fractional resource pi;jðtÞði 2 AÞ to each user j in a progressive filling approach. We start from user 1 and try to allocate resource to user 1 as much as possible until y0 1 ¼ R t 0 b1ðtÞdt þ P i2A ri;jðtÞ pi;jðtÞ t w1 T1ðtÞ ¼ y2 or user 1 is saturated with available resources. We further allocate resource to user 1 (if user 1 is not yet saturated, otherwise we stop allocation for user 1) and user 2 as much as possible until any of the users is saturated or y0 1 ¼ y0 2 ¼ y3. We continue this progressive filling procedure until all available resources have been allocated or all of the users are saturated. For each round we use parameter J to denote the indices for the involved users 1; 2; ... ; J in progressive filling. XIE ET AL.: ASSOCIATION CONTROL FOR VEHICULAR WIFI ACCESS: PURSUING EFFICIENCY AND FAIRNESS 1327
1328 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,VOL.22,NO.8,AUGUST 2011 Algorithm 2 Using progressive filling method to achieve overall allocated time fraction of each user j that commu- max-min fairness nicates with all APs cannot be more than 1.Constraint(16) 1:t=0 shows that the time fraction is between 0 and 1. 2:while t(p(t)+)≤1， (14) We have implemented a simulator to simulate the Drive- U thru Internet scenario.In order to simulate the realistic 0∈U ∑p)+P()≤1， 15) settings about the road topologies and the vehicles'moving i traces,we use the realistic traffic generator Simulation of i∈A,j∈U'0≤p(t)+p(t)≤1 16 Urban MObility (SUMO)[18]to construct the large road network and generate vehicle traffic.In the simulation,we In the linear programming LP(U),U'denotes the non- build the road topologies based on the road networks in a saturated user set,we,respectively,use p(t)and pij(t)to rectangular region(3,500 m x 3,000 m)in Washington DC., denote the new allocated time fraction and the already which is imported from the TIGER database [19].We build allocated time fraction.The objective is to maximize y, the roads with lanes,and the number of lanes of each road which is the minimum value of yj for each user j inside the ranges from 1 to 6.Hence,the major roads take the majority nonsaturated user set U'.Constraint(12)depicts that y is the of traffic flow as there are more lanes on the major roads than minimum value of yj.Constraint(13)depicts that y;should the other roads.Traffic lights are deployed at the cross of not be allocated more than the value of roads.We generate vehicle traffics over the road networks according to the parameters illustrated in Table 1,where bs(t)dt accel and decel,respectively,denote the acceleration and 四·(T(t)+△t) deceleration ability of vehicles,sigma denotes the driver imperfection (between 0 and 1),length and speed,respec- since we are considering the progressive filling approach tively,denote the vehicle length and average speed,density for users in 1,2,..../for each round.Constraint (14)means denotes the average density of vehicles on the roads.The that the overall allocated time fraction of each AP i to all average speed speed=15 m/s and we observe that the users cannot be more than 1.Constraint(15)states that the 95 percent confidence interval for vehicles'speed is
Algorithm 3 is the optimized allocation algorithm for each progressive filling round. During each round we utilize the linear program LP(U0 ) to iteratively determine the saturated users while trying to maximize the throughput of these saturated users, as shown in the following formulation: maximize y; ð11Þ subject to 8j 2 U0 yj ¼ R t 0 bjðtÞdt þ P i2A ri;jðtÞ p0 i;jðtÞ t wj ðTjðtÞ þ tÞ 8j 2 U0 yj y; ð12Þ 8j 2 U0 yj R t 0 bJ ðtÞdt wj ðTJ ðtÞ þ tÞ ; ð13Þ 8i 2 A X j2U ðpi;jðtÞ þ p0 i;jðtÞÞ 1; ð14Þ 8j 2 U0 X i2A ðpi;jðtÞ þ p0 i;jðtÞÞ 1; ð15Þ 8i 2 A; j 2 U0 0 pi;jðtÞ þ p0 i;jðtÞ 1: ð16Þ In the linear programming LP(U0 ), U0 denotes the nonsaturated user set, we, respectively, use p0 i;jðtÞ and pi;jðtÞ to denote the new allocated time fraction and the already allocated time fraction. The objective is to maximize y, which is the minimum value of yj for each user j inside the nonsaturated user set U0 . Constraint (12) depicts that y is the minimum value of yj. Constraint (13) depicts that yj should not be allocated more than the value of R t 0 bJ ðtÞdt wj ðTJ ðtÞ þ tÞ ; since we are considering the progressive filling approach for users in 1; 2; ... ; J for each round. Constraint (14) means that the overall allocated time fraction of each AP i to all users cannot be more than 1. Constraint (15) states that the overall allocated time fraction of each user j that communicates with all APs cannot be more than 1. Constraint (16) shows that the time fraction is between 0 and 1. In each iteration of Algorithm 3, we attempt to determine the optimal allocations for the users which are still nonsaturated, and check current users if they are already saturated according to the definition. Then we remove the saturated users from the target set U0 . In this way we achieve the “max-min fair” allocation in an approximate approach by using the progressive filling method. In the supplementary material, which can be found on the Computer Society Digital Library at http://doi. ieeecomputersociety.org/10.1109/TPDS.2011.17, we further introduce the group-based methodology to reduce association control complexity, and discuss the practical utilization in realistic settings. 5 PERFORMANCE EVALUATIONS We have implemented a simulator to simulate the Drivethru Internet scenario. In order to simulate the realistic settings about the road topologies and the vehicles’ moving traces, we use the realistic traffic generator Simulation of Urban MObility (SUMO) [18] to construct the large road network and generate vehicle traffic. In the simulation, we build the road topologies based on the road networks in a rectangular region (3,500 m 3,000 m) in Washington DC., which is imported from the TIGER database [19]. We build the roads with lanes, and the number of lanes of each road ranges from 1 to 6. Hence, the major roads take the majority of traffic flow as there are more lanes on the major roads than the other roads. Traffic lights are deployed at the cross of roads. We generate vehicle traffics over the road networks according to the parameters illustrated in Table 1, where accel and decel, respectively, denote the acceleration and deceleration ability of vehicles, sigma denotes the driver imperfection (between 0 and 1), length and speed, respectively, denote the vehicle length and average speed, density denotes the average density of vehicles on the roads. The average speed speed ¼ 15 m=s and we observe that the 95 percent confidence interval for vehicles’ speed is 1328 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 22, NO. 8, AUGUST 2011
XIE ET AL.:ASSOCIATION CONTROL FOR VEHICULAR WIFI ACCESS:PURSUING EFFICIENCY AND FAIRNESS 1329 TABLE 1 TABLE 2 Parameters for Generating Vehicle Traffics Abbreviations parameters default value parameters default value Abbreviation Full Name accel 0.8(m/s2) length 5(m) SSF Strongest Signal First decel 4.5(m/s2) speed 15(m/s) CUB Connect Until Broken sigma 0.5 depart 0(s) OPT-E(offline Offline optimization for efficiency period 30(s) repno 100 OPT-E(online) Online optimization for efficiency density 22 (users/km) OPT-PF(offline) Offline optimization for proportional fairness OPT-PF(online) Online optimization for proportional fairness OPT-MM Online optimization for max-min fairness (5 m/s,20 m/s).We simulate 500 various routes over the road network for the vehicles,for each route we randomly pick the origin position and the destination position and at any location of the roads.In the following part,we hence specify the trip for the route.We use depart to denote conduct the performance evaluation to show how the the time at which the vehicles are emitted into the network, optimal solutions work under the two different situations. and we use period to denote the average time interval after To obtain each simulation result,we take the average value which another vehicular user with the same route shall be of 50 simulation runs.In the supplementary material,which emitted and repno to denote the number of vehicles to emit can be found on the Computer Society Digital Library at which share the same route.We use random seeds to http://doi.ieeecomputersociety.org/10.1109/TPDS.2011.17, generate the time intervals between emitted vehicles with we illustrate more detail simulation results in a compre- the same route.As we set period=30s,thus on average hensive approach. every 30s the vehicles are emitted,and we set the 95 percent 5.1 Efficiency and Fairness confidence interval of the time interval as (20 s,40 s). In this section,we evaluate the performance in terms of Therefore,the application scenario involves about 50,000 efficiency and fairness.In order to illustrate the perfor- vehicular users and lasts about 50 minutes.According to the mance gains of our optimized solutions,we compare with above settings,the average density density 22 users/km, two heuristic strategies.The first strategy is Strongest Signal i.e.,the average number of vehicles per kilometer of road is First,which always associates a user with the Ap yielding 22.We observe that the 95 percent confidence interval for the the strongest received signal strength at all times.The density is(14 users/km,60 users/km). second strategy is Connect Until Broken,which maintains a We conduct the performance evaluation based on the connection with a user and an AP until the user considers settings of large road network and vehicle traffic generated the link to be broken.Upon disconnection,the user will be by SUMO.We randomly place the APs inside the specified associated with a new AP which yields the largest signal region and adopt the experiment results from [1]to strength.When calculating the optimized solution,we solve simulate the effective bit rates of APs.We set their peak the linear program and convex program using MATLAB.In bit rates within the range from 4,000 to 5,000 kbps for the rest of this paper,we use the abbreviations as shown in vehicular users.To sufficiently evaluate the performance of Table 2 to denote the specified solutions.For the ease of various association control strategies,we consider two comparison,we set w;=1 for each user.We set e=1 kbits kinds of situations for AP deployment:the dense AP for OPT-PF(online),and,respectively,set C=200 kbps and deployment and the sparse AP deployment.For the dense C=0 kbps in the dense AP situation and sparse AP AP deployment,we randomly deploy 500 APs and make situation for both OPT-E(offline)and OPT-E(online). sure that at any location of the roads the user is within Fig.4a depicts the total throughput of all users achieved effective range of at least one AP.For the sparse AP by various solutions.As in each run of simulation the deployment,we randomly deploy 150 APs and the user is generated traffic mobility has some variances,in order to not guaranteed within the effective range of at least one AP show the statistical performance results,so we provide the 1200 ■SgF CUB OPT-E(omine) 1000 -CPT-Eonine) OeT-PEIcttlne OPT-E(online) CPT-PF[online CPT-PF(omline 800 -OPT-MM CPT-PFlonline OPT-MM 600 400 200 (b)Sparse AP conditiong 0.5 15 *10 (a) (b) Fig.4.Simulation results for efficiency and fairness.(a)Total throughput(kbps)for all users.(b)Per-user throughput comparison with dense AP deployment
ð5 m=s; 20 m=sÞ. We simulate 500 various routes over the road network for the vehicles, for each route we randomly pick the origin position and the destination position and hence specify the trip for the route. We use depart to denote the time at which the vehicles are emitted into the network, and we use period to denote the average time interval after which another vehicular user with the same route shall be emitted and repno to denote the number of vehicles to emit which share the same route. We use random seeds to generate the time intervals between emitted vehicles with the same route. As we set period ¼ 30 s, thus on average every 30 s the vehicles are emitted, and we set the 95 percent confidence interval of the time interval as ð20 s; 40 sÞ. Therefore, the application scenario involves about 50,000 vehicular users and lasts about 50 minutes. According to the above settings, the average density density ¼ 22 users/km, i.e., the average number of vehicles per kilometer of road is 22. We observe that the 95 percent confidence interval for the density is (14 users/km, 60 users/km). We conduct the performance evaluation based on the settings of large road network and vehicle traffic generated by SUMO. We randomly place the APs inside the specified region and adopt the experiment results from [1] to simulate the effective bit rates of APs. We set their peak bit rates within the range from 4,000 to 5,000 kbps for vehicular users. To sufficiently evaluate the performance of various association control strategies, we consider two kinds of situations for AP deployment: the dense AP deployment and the sparse AP deployment. For the dense AP deployment, we randomly deploy 500 APs and make sure that at any location of the roads the user is within effective range of at least one AP. For the sparse AP deployment, we randomly deploy 150 APs and the user is not guaranteed within the effective range of at least one AP at any location of the roads. In the following part, we conduct the performance evaluation to show how the optimal solutions work under the two different situations. To obtain each simulation result, we take the average value of 50 simulation runs. In the supplementary material, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/10.1109/TPDS.2011.17, we illustrate more detail simulation results in a comprehensive approach. 5.1 Efficiency and Fairness In this section, we evaluate the performance in terms of efficiency and fairness. In order to illustrate the performance gains of our optimized solutions, we compare with two heuristic strategies. The first strategy is Strongest Signal First, which always associates a user with the AP yielding the strongest received signal strength at all times. The second strategy is Connect Until Broken, 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. When calculating the optimized solution, we solve the linear program and convex program using MATLAB. In the rest of this paper, we use the abbreviations as shown in Table 2 to denote the specified solutions. For the ease of comparison, we set wj ¼ 1 for each user. We set ¼ 1 kbits for OPT-PF(online), and, respectively, set C ¼ 200 kbps and C ¼ 0 kbps in the dense AP situation and sparse AP situation for both OPT-E(offline) and OPT-E(online). Fig. 4a depicts the total throughput of all users achieved by various solutions. As in each run of simulation the generated traffic mobility has some variances, in order to show the statistical performance results, so we provide the XIE ET AL.: ASSOCIATION CONTROL FOR VEHICULAR WIFI ACCESS: PURSUING EFFICIENCY AND FAIRNESS 1329 TABLE 1 Parameters for Generating Vehicle Traffics TABLE 2 Abbreviations Fig. 4. Simulation results for efficiency and fairness. (a) Total throughput (kbps) for all users. (b) Per-user throughput comparison with dense AP deployment.
1330 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,VOL.22,NO.8,AUGUST 2011 90 percent confidence interval for the total throughput. Grant No.2009CB320705;the Technology Support Program Note that in both the dense AP situation and sparse AP of Jiangsu Province under Grant No.BE2010179;the US situation,OPT-E(offline)achieves the largest overall National Science Foundation(NSF)under Grant Nos.CNS- throughput,while CUB achieves the smallest throughput. 0721443 and CNS-0831904,CAREER Award CNS-0747108, Due to some nonpredictable issues,OPT-E(online)achieves CNS-0434533,CNS-0531410,and CNS-0626240. a little smaller value for the overall throughput than OPT- E(offline).All solutions in the sparse AP situation achieves a fairly smaller overall throughput compared to the dense AP REFERENCES situation,as fewer aPs are available for association to [1]J.Ott and D.Kutscher,"Drive-thru Internet:IEEE 802.11b for 'Automobile'Users,"Proc.IEEE INFOCOM,2004. provide sufficient throughput for users.We observed that 2☒ J.Camp and E.Knightly,"Modulation Rate Adaptation in Urban in both situations the optimized solutions outperform the and Vehicular Environments:Cross-Layer Implementation and two heuristic solutions.In the dense AP situation OPT- Experimental Evaluation,"Proc.ACM MOBICOM,2008. E(online),respectively,achieves 72.9 and 122.9 percent more L.Tassiulas and S.Sarkar,"Maxmin Fair Scheduling in Wireless Ad Hoc Networks,"IEEE I.Selected Areas in Comm.,vol.23,no.1, throughput than SSF and CUB,while in the sparse AP Pp.163-173,Jan.2005. situation OPT-E(online),respectively,achieves 30.6 and 73.7 [4 Y.Bejerano,S.-J.Han,and L Li,"Fairness and Load Balancing in percent more throughput than SSF and CUB.Since users Wireless LANs Using Association Control,"IEEE/ACM Trans. Networking,vol.15,no.3,pp.560-573,June 2007. have more candidate aPs to associate with in the dense aP L.Li,M.Pal,and Y.R.Yang,"Proportional Fairness in Multi-Rate situation,there exist more opportunities for an optimized Wireless LANs,"Proc.IEEE INFOCOM,2008. solution to achieve more performance gains. [阿 V.Bychkovsky,B.Hull,A.Miu,H.Balakrishnan,and S.Madden "A Measurement Study of Vehicular Internet Access Using In Situ In order to show the performance comparison in terms of Wi-Fi Networks,"Proc.ACM MOBICOM,2006. fairness,Fig.4b illustrates per-user throughput comparison ☑ J.Eriksson,H.Balakrishnan,and S.Madden,"Cabernet:Vehicular in the dense AP situation.The X-axis is the user index and the Content Delivery Using Wi-Fi,"Proc.ACM MOBICOM,2008. Y-axis is users'throughput in kbps.The users are sorted by © A.Giannoulis,M.Fiore,and E.W.Knightly,"Supporting Vehicular Mobility in Urban Multi-Hop Wireless Networks, their throughput in increasing order.The throughput of the Proc.ACM Mobile Systems,Applications,and Services (MOBISYS), user with the same x index actually indicates the average 2008. throughput of the zth lowest throughput user (users [9 R.Mahajan,I.Zahorjan,and B.Zill,"Understanding WiFi-Based allocated the cth lowest bandwidth).In the dense AP Connectivity,"Proc.ACM Internet Measurement Conf.(IMC),2007. [10]D.Hadaller,S.Keshav,T.Brecht,and S.Agarwal,"Vehicular situation,we observe that the optimized solutions OPT- Opportunistic Communication under the Microscope,"Proc.ACM E(online),OPT-PF(offline),OPT-PF(online)and OPT-MM all Mobile Systems,Applications,and Services(MOBISYS),2007. outperform the two heuristic solutions SSF and CUB.For [l1]V.Navda,A.P.Subramanian,K.Dhanasekaran,A.Timm-Giel, and S.R.Das,"Mobisteer:Using Steerable Beam Directional instance,the median indexed user's bandwidth value of Antenna for Vehicular Network Access,"Proc.ACM MOBISYS, OPT-E(online)is,respectively,64 percent higher than SSF and 2007. 181 percent higher than CUB.OPT-PF(offline),OPT-PF(online) [12]M.Kim,Z.Liu,S.Parthasarathy,D.Pendarakis,and H.Yang and OPT-MM have better performance in fairness than OPT- "Association Control in Mobile Wireless Networks,"Proc.IEEE INFOCOM,2008. E(online),since the users with lower indices have higher [13]P.Deshpande,A.Kashyap,C.Sung,and S.Das,"Predictive throughput in OPT-PF(offline),OPT-PF(online)and OPT-MM Methods for Improved Vehicular Wifi Access,"Proc.ACM Mobile compared to OPT-E(online).Among the three solutions,OPT- Systems,Applications,and Services (MOBISYS),2009. MM achieves the best performance in fairness,as the users [14]H.Wu,K.Tan,Y.Zhang,and Q.Zhang,"Proactive Scan:Fast Handoff with Smart Triggers for 802.11 Wireless Lan,"Proc. with lower indices are higher than all the other solutions, INFOCOM,2007. inferring that more fairness is achieved among the users.The [1 T.Nandagopal,T.-E.Kim,X.Gao,and V.Bharghavan,"Achieving performance gains of the above optimized solutions are Mac Layer Fairness in Wireless Packet Networks,"Proc.ACM MOBICOM,pp.87-98,2000. between 200 and 400 kbps in throughput for each user. [16 R.Murty,J.'Padhye,A.Wolman,and B.Zill,"Designing High Performance Enterprise Wi-Fi Networks,"Proc.ACM Networked Systems Design and Implementation (NSDI),2008. 6 CONCLUSION [17]D.B.Shmoys and E.Tardos,"An Approximation Algorithm for the Generalized Assignment Problem,"Math.Programming, In this paper,we conduct a theoretical study on association vol.62,no.3,PP.461-474,1993. control over the Drive-thru Internet scenario.We,respec- 18] "Sumo,"http://sourceforge.net/apps/mediawiki/sumo/,2011. tively,consider efficiency and fairness as the optimization [19] "Tiger,"www.census.gov/geo/www/tiger/,2011. metrics.Due to issues concerning both technology and privacy,the data needed to compute the optimal solutions are currently not easy to gather.Hence,our present research Lei Xie received the BS and PhD degrees from work intends to be a theoretical effort to determine the Nanjing University in 2004 and 2010,respec- tively,all in computer science.He is an upper bounds to what can be achieved in reality. assistant professor in the Department of Computer Science and Technology,Nanjing University,China.His research interests in- ACKNOWLEDGMENTS clude sensor networks,RFID systems,vehicu- lar networks,cognitive radios,and high The authors would like to thank the reviewers for their performance computing.He is a member of careful reading and comments.This work is partially the IEEE and the IEEE Computer Society. supported by the National Natural Science Foundation of China under Grant Nos.61073028 and 61021062;the National Basic Research Program of China (973)under
90 percent confidence interval for the total throughput. Note that in both the dense AP situation and sparse AP situation, OPT-E(offline) achieves the largest overall throughput, while CUB achieves the smallest throughput. Due to some nonpredictable issues, OPT-E(online) achieves a little smaller value for the overall throughput than OPTE(offline). All solutions in the sparse AP situation achieves a fairly smaller overall throughput compared to the dense AP situation, as fewer APs are available for association to provide sufficient throughput for users. We observed that in both situations the optimized solutions outperform the two heuristic solutions. In the dense AP situation OPTE(online), respectively, achieves 72.9 and 122.9 percent more throughput than SSF and CUB, while in the sparse AP situation OPT-E(online), respectively, achieves 30.6 and 73.7 percent more throughput than SSF and CUB. Since users have more candidate APs to associate with in the dense AP situation, there exist more opportunities for an optimized solution to achieve more performance gains. In order to show the performance comparison in terms of fairness, Fig. 4b illustrates per-user throughput comparison in the dense AP situation. 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. The throughput of the user with the same x index actually indicates the average throughput of the xth lowest throughput user (users allocated the xth lowest bandwidth). In the dense AP situation, we observe that the optimized solutions OPTE(online), OPT-PF(offline), OPT-PF(online) and OPT-MM all outperform the two heuristic solutions SSF and CUB. For instance, the median indexed user’s bandwidth value of OPT-E(online) is, respectively, 64 percent higher than SSF and 181 percent higher thanCUB.OPT-PF(offline), OPT-PF(online) and OPT-MM have better performance in fairness than OPTE(online), since the users with lower indices have higher throughput in OPT-PF(offline), OPT-PF(online) and OPT-MM compared to OPT-E(online). Among the three solutions, OPTMM achieves the best performance in fairness, as the users with lower indices are higher than all the other solutions, inferring that more fairness is achieved among the users. The performance gains of the above optimized solutions are between 200 and 400 kbps in throughput for each user. 6 CONCLUSION In this paper, we conduct a theoretical study on association control over the Drive-thru Internet scenario. We, respectively, consider efficiency and fairness as the optimization metrics. Due to issues concerning both technology and privacy, the data needed to compute the optimal solutions are currently not easy to gather. Hence, our present research work intends to be a theoretical effort to determine the upper bounds to what can be achieved in reality. ACKNOWLEDGMENTS The authors would like to thank the reviewers for their careful reading and comments. This work is partially supported by the National Natural Science Foundation of China under Grant Nos. 61073028 and 61021062; the National Basic Research Program of China (973) under Grant No. 2009CB320705; the Technology Support Program of Jiangsu Province under Grant No. BE2010179; the US National Science Foundation (NSF) under Grant Nos. CNS- 0721443 and CNS-0831904, CAREER Award CNS-0747108, CNS-0434533, CNS-0531410, and CNS-0626240. REFERENCES [1] J. Ott and D. Kutscher, “Drive-thru Internet: IEEE 802.11b for ‘Automobile’ Users,” Proc. IEEE INFOCOM, 2004. [2] J. Camp and E. Knightly, “Modulation Rate Adaptation in Urban and Vehicular Environments: Cross-Layer Implementation and Experimental Evaluation,” Proc. ACM MOBICOM, 2008. [3] L. Tassiulas and S. Sarkar, “Maxmin Fair Scheduling in Wireless Ad Hoc Networks,” IEEE J. Selected Areas in Comm., vol. 23, no. 1, pp. 163-173, Jan. 2005. [4] Y. Bejerano, S.-J. Han, and L. Li, “Fairness and Load Balancing in Wireless LANs Using Association Control,” IEEE/ACM Trans. Networking, vol. 15, no. 3, pp. 560-573, June 2007. [5] L. Li, M. Pal, and Y.R. Yang, “Proportional Fairness in Multi-Rate Wireless LANs,” Proc. IEEE INFOCOM, 2008. [6] V. Bychkovsky, B. Hull, A. Miu, H. Balakrishnan, and S. Madden, “A Measurement Study of Vehicular Internet Access Using In Situ Wi-Fi Networks,” Proc. ACM MOBICOM, 2006. [7] J. Eriksson, H. Balakrishnan, and S. Madden, “Cabernet: Vehicular Content Delivery Using Wi-Fi,” Proc. ACM MOBICOM, 2008. [8] A. Giannoulis, M. Fiore, and E.W. Knightly, “Supporting Vehicular Mobility in Urban Multi-Hop Wireless Networks,” Proc. ACM Mobile Systems, Applications, and Services (MOBISYS), 2008. [9] R. Mahajan, J. Zahorjan, and B. Zill, “Understanding WiFi-Based Connectivity,” Proc. ACM Internet Measurement Conf. (IMC), 2007. [10] D. Hadaller, S. Keshav, T. Brecht, and S. Agarwal, “Vehicular Opportunistic Communication under the Microscope,” Proc. ACM Mobile Systems, Applications, and Services (MOBISYS), 2007. [11] V. Navda, A.P. Subramanian, K. Dhanasekaran, A. Timm-Giel, and S.R. Das, “Mobisteer: Using Steerable Beam Directional Antenna for Vehicular Network Access,” Proc. ACM MOBISYS, 2007. [12] M. Kim, Z. Liu, S. Parthasarathy, D. Pendarakis, and H. Yang, “Association Control in Mobile Wireless Networks,” Proc. IEEE INFOCOM, 2008. [13] P. Deshpande, A. Kashyap, C. Sung, and S. Das, “Predictive Methods for Improved Vehicular Wifi Access,” Proc. ACM Mobile Systems, Applications, and Services (MOBISYS), 2009. [14] H. Wu, K. Tan, Y. Zhang, and Q. Zhang, “Proactive Scan: Fast Handoff with Smart Triggers for 802.11 Wireless Lan,” Proc. INFOCOM, 2007. [15] T. Nandagopal, T.-E. Kim, X. Gao, and V. Bharghavan, “Achieving Mac Layer Fairness in Wireless Packet Networks,” Proc. ACM MOBICOM, pp. 87-98, 2000. [16] R. Murty, J. Padhye, A. Wolman, and B. Zill, “Designing High Performance Enterprise Wi-Fi Networks,” Proc. ACM Networked Systems Design and Implementation (NSDI), 2008. [17] D.B. Shmoys and E. Tardos, “An Approximation Algorithm for the Generalized Assignment Problem,” Math. Programming, vol. 62, no. 3, pp. 461-474, 1993. [18] “Sumo,” http://sourceforge.net/apps/mediawiki/sumo/, 2011. [19] “Tiger,” www.census.gov/geo/www/tiger/, 2011. Lei Xie received the BS and PhD degrees from Nanjing University in 2004 and 2010, respectively, all in computer science. He is an assistant professor in the Department of Computer Science and Technology, Nanjing University, China. His research interests include sensor networks, RFID systems, vehicular networks, cognitive radios, and high performance computing. He is a member of the IEEE and the IEEE Computer Society. 1330 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 22, NO. 8, AUGUST 2011
XIE ET AL.:ASSOCIATION CONTROL FOR VEHICULAR WIFI ACCESS:PURSUING EFFICIENCY AND FAIRNESS 1331 Qun Li received the PhD degree in computer Jie Wu is the chair and a professor in the science from Dartmouth College.He is an Department of Computer and Information associate professor in the Department of Com- Sciences,Temple University.Prior to joining puter Science at the College of William and Temple University,he was a program director at Mary.His research interests include wireless National Science Foundation.His research networks,sensor networks,RFID,and pervasive interests include wireless networks and mobile computing systems.He received the NSF computing,routing protocols,fault-tolerant com- Career award in 2008.He is a member of the puting,and interconnection networks.He has IEEE and the IEEE Computer Society. published more than 500 papers in various journals and conference proceedings.He serves in the editorial board of the IEEE Transactions on Computers,IEEE Transactions on Mobile Computing,and Journal of Parallel and Distributed Computing.He is program cochair for IEEE INFOCOM Weizhen Mao received the PhD degree in 2011.He was also general cochair for IEEE MASS 2006,IEEE IPDPS 2008,ACM WiMD 2009.and IEEE/ACM DCOSS 2009.He also served computer science from Princeton University as panel chair for ACM MobiCom 2009.He has served as an IEEE under the supervision of Andrew C.-C.Yao.Her computer society distinguished visitor.Currently,he is the chair of the current research interests include the design and IEEE Technical Committee on Distributed Processing (TCDP)and ACM analysis of online and approximation algorithms distinguished speaker.He is a fellow of the IEEE. for problems arising from application areas,such as multicore job scheduling,wireless and sensor Daoxu Chen received the BS degree in com- networks.She is currently an associate professor puter science from Nanjing University,Nanjing. in the Department of Computer Science at the China,in 1982.He was a visiting researcher with College of William and Mary. Purdue University,West Lafayette,IN,and the City University of Hong Kong,Kowloon,Hong Kong.He is currently a professor with the Department of Computer Science and Technol- ogy,Nanjing University,Nanjing,China.His research interests include distributed computing. parallel processing,and computer networks.He is a member of the Association for Computing Machinery and a Senior Member of the China Computer Federation.He is a member of the IEEE and the IEEE Computer Society. For more information on this or any other computing topic, please visit our Digital Library at www.computer.org/publications/dlib
Qun Li received the PhD degree in computer science from Dartmouth College. He is an associate professor in the Department of Computer Science at the College of William and Mary. His research interests include wireless networks, sensor networks, RFID, and pervasive computing systems. He received the NSF Career award in 2008. He is a member of the IEEE and the IEEE Computer Society. Weizhen Mao received the PhD degree in computer science from Princeton University under the supervision of Andrew C.-C. Yao. Her current research interests include the design and analysis of online and approximation algorithms for problems arising from application areas, such as multicore job scheduling, wireless and sensor networks. She is currently an associate professor in the Department of Computer Science at the College of William and Mary. Jie Wu is the chair and a professor in the Department of Computer and Information Sciences, Temple University. Prior to joining Temple University, he was a program director at National Science Foundation. His research interests include wireless networks and mobile computing, routing protocols, fault-tolerant computing, and interconnection networks. He has published more than 500 papers in various journals and conference proceedings. He serves in the editorial board of the IEEE Transactions on Computers, IEEE Transactions on Mobile Computing, and Journal of Parallel and Distributed Computing. He is program cochair for IEEE INFOCOM 2011. He was also general cochair for IEEE MASS 2006, IEEE IPDPS 2008, ACM WiMD 2009, and IEEE/ACM DCOSS 2009. He also served as panel chair for ACM MobiCom 2009. He has served as an IEEE computer society distinguished visitor. Currently, he is the chair of the IEEE Technical Committee on Distributed Processing (TCDP) and ACM distinguished speaker. He is a fellow of the IEEE. Daoxu Chen received the BS degree in computer science from Nanjing University, Nanjing, China, in 1982. He was a visiting researcher with Purdue University, West Lafayette, IN, and the City University of Hong Kong, Kowloon, Hong Kong. He is currently a professor with the Department of Computer Science and Technology, Nanjing University, Nanjing, China. His research interests include distributed computing, parallel processing, and computer networks. He is a member of the Association for Computing Machinery and a Senior Member of the China Computer Federation. He is a member of the IEEE and the IEEE Computer Society. . For more information on this or any other computing topic, please visit our Digital Library at www.computer.org/publications/dlib. XIE ET AL.: ASSOCIATION CONTROL FOR VEHICULAR WIFI ACCESS: PURSUING EFFICIENCY AND FAIRNESS 1331