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 t<T do 3: is consistent with maximizing the long-term objective function For each user j,calculate W(t)for snapshot at t. 世 4: For snapshot at t,set the object function as to j(t)dt. 0 e+bi(t)dt maximize Wj(t)(t),calculate and apply the solution for association. Here,b(t)dt denotes the accumulated bandwidth in time 5:t=t+△t. span 0,t,wj denotes the original fixed weight as priority for 6:end while each user j,and e>is 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