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 SocietyAssociation 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 metropo￾litan 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 adapta￾tion 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 adapta￾tion [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 perfor￾mance 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 Drive￾thru 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 algo￾rithms 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 fre￾quently while the users are driving along the roads, this paper is concerned about the long-term perfor￾mance in terms of efficiency and fairness, and proposes novel algorithms to achieve these long￾term objectives. 2. We propose a theoretical framework for association control over vehicular networks. For the efficiency metric, the problem is transformed into an optimiza￾tion 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 approxima￾tion algorithm to break the large contention group into smaller subgroups, achieving a trade-off be￾tween accuracy and computation complexity. The rest of the paper is organized as follows: We briefly present related work in Section 2. We define the perfor￾mance 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