Achieving Efficiency and Fairness for Association Control in Vehicular Networks Lei Xiett,Qun Lit,Weizhen Maof,Jie Wus,Daoxu Chent fState Key Laboratory of Novel Software Technology,Nanjing University,China The College of William and Mary,Williamsburg,VA,USA STemple University,Philadelphia,PA,USA Email:ixielei@dislab.nju.edu.cn,fliqun,wm@cs.wm.edu,3jiewu@temple.edu,fcdx@nju.edu.cn Abstract-Deploying city-wide 802.11 access points has made manage AP association in this type of"Vehicular Networks". possible internet access in a vehicle,nevertheless it is challenging Compared with a static network,this type of network is to maintain client performance at vehicular speed especially composed of continuously moving clients that may constantly when multiple mobile users exist.This paper considers the association control problem for vehicular networks in drive- try to associate with the nearby APs.Algorithms that solve thru Internet scenarios.In particular,we aim to improve the for the association control problem in a static network are overall throughput and fairness for all users.We design efficient not suitable because(1)a vehicular network is a much larger algorithms to achieve the objectives through several techniques network composed of thousands of cars and APs compared including approximation.Our simulation results confirm the with a rather small indoor network,and(2)the existing algo- performance of our algorithms. rithms are unable to accommodate the dynamic creation and I.INTRODUCTION removal of the possible communication links in the network graph.Algorithms which are designed for the cellular network Advanced technologies in communication have made ubiq- are also not suitable,because (1)the cell site has a much uitous network connectivity-anywhere,anytime-a reality for mobile users.Wi-Fi technology is one of them,which provides larger coverage,and (2)the cells are devised to have small users easy access to the Internet through nearby WLAN access overlapping areas,and the mobile clients usually do not have multiple candidate cell sites to choose.Hence the handoff only points.WLAN-based access points (AP)can provide cost- occurs when a mobile client moves out of the original cell or effective wireless Internet access with a shared gross data rate that ranges from 10 to 50 Mbits/sec and can be scalable to hun- moves into a new cell.The association control for "Vehicular Networks"is much more complicated and has more urgent dreds of concurrently-active users.Not limited to corporation, real-time demand than the cellular network because a client office,or home use for comparably stationary user,the access can have multiple candidate APs to select most of the time and points,in the Drive-thru Internet[1][2],are recently proposed in a very short interval (20-30s),the client may move out of to be deployed along the roads,thus providing continuous the range of the current AP and switch to a new AP for better network connectivity to mobile users in vehicles.However, for outdoor access of mobile users at high vehicular speeds, performance.We believe that a thorough theoretical study on this problem is highly necessary for the future deployment of due to the dynamically changing network structure of AP-user pairing and contentions among mobile users,it is still a big this type of networks.Some pitfalls can be avoided in real deployment if we have a better understanding about it first. challenge to maintain a good client performance. In order to achieve reasonable efficiency among multiple This paper aims to define a theoretical framework to analyze the performance of a vehicular network in the Drive-thru vehicular users for the above Drive-thru Internet scenario, Internet scenario,in particular to investigate the association several problems should be considered,e.g.,rate adaptation and association control.Association control defines,while control scheme.Considering both the long-term efficiency and fairness metrics,we propose optimized schemes to associate multiple users are driving along the road,how to intelligently mobile users with APs,and approximation algorithms to re- associate these mobile users to specific APs and when to duce computation complexity of calculating optimal solutions. appropriately conduct handoffs of APs for users to improve Although there is some previous work related to this topic the overall system performance.Compared with rate adapta- [12]3].they all focus on the measurement study on vehicular tion,association control considers the entire network from a internet access.To the best of our knowledge,this is the first macro-level perspective,which shows how to optimize system performance from a higher level viewpoint. theoretical work that investigates the optimization problem for association control over vehicular users in Wi-Fi networks. We notice that,albeit some recent work on association And being distinct from the previous research works,since the control for static networks,there is little work on how to association solutions are updated in a frequent approach while This work was done when the first author worked as a visiting scholar at the users are driving along the roads,this paper is concerned the College of William and Mary. about the long-term performance in terms of efficiency and 978-1-4244-4634-6/09/S25.00©20091EEE 324 Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:35:32 UTC from IEEEXplore.Restrictions apply.Achieving Efficiency and Fairness for Association Control in Vehicular Networks Lei Xie†‡, Qun Li‡, Weizhen Mao‡, Jie Wu§, Daoxu Chen† †State Key Laboratory of Novel Software Technology, Nanjing University, China ‡The College of William and Mary, Williamsburg, VA, USA §Temple University, Philadelphia, PA, USA Email: †xielei@dislab.nju.edu.cn, ‡{liqun, wm}@cs.wm.edu, §jiewu@temple.edu, †cdx@nju.edu.cn Abstract—Deploying city-wide 802.11 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 networks in drive￾thru Internet scenarios. In particular, we aim to improve the overall throughput and fairness for all users. We design efficient algorithms to achieve the objectives through several techniques including approximation. Our simulation results confirm the performance of our algorithms. I. INTRODUCTION Advanced technologies in communication have made ubiq￾uitous network connectivity - anywhere, anytime - a reality for mobile users. Wi-Fi technology is one of them, which provides users easy access to the Internet through nearby WLAN access points. WLAN-based access points (AP) can provide cost￾effective wireless Internet access with a shared gross data rate that ranges from 10 to 50 Mbits/sec and can be scalable to hun￾dreds of concurrently-active users. Not limited to corporation, office, or home use for comparably stationary user, the access points, in the Drive-thru Internet[1][2], are recently proposed to be deployed along the roads, thus providing continuous network connectivity to mobile users in vehicles. However, for outdoor access of mobile users at high vehicular speeds, due to the dynamically changing network structure of AP-user pairing and contentions among mobile users, it is still a big challenge to maintain a good client performance. 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 these mobile users to specific APs and when to appropriately conduct handoffs of APs for users to improve the overall system performance. Compared with rate adapta￾tion, association control considers the entire network from a macro-level 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 This work was done when the first author worked as a visiting scholar at the College of William and Mary. manage AP association in this type of “Vehicular Networks”. Compared with a static network, this type of network is composed of continuously moving clients that may constantly try to associate with the nearby APs. Algorithms that solve for the association control problem in a static network are not suitable because (1) a vehicular network is a much larger network composed of thousands of cars and APs compared with a rather small indoor network, and (2) the existing algo￾rithms are unable to accommodate the dynamic creation and removal of the possible communication links in the network graph. Algorithms which are designed for the cellular network are also not suitable, because (1) the cell site has a much larger coverage, and (2) the cells are devised to have small overlapping areas, and the mobile clients usually do not have multiple candidate cell sites to choose. Hence the handoff only occurs when a mobile client moves out of the original cell or moves into a new cell. The association control for “Vehicular Networks” is much more complicated and has more urgent real-time demand than the cellular network because a client can have multiple candidate APs to select most of the time and in a very short interval (20-30s), the client may move out of the range of the current AP and switch to a new AP for better performance. We believe that a thorough theoretical study on this problem is highly necessary for the future deployment of this type of networks. Some pitfalls can be avoided in real deployment if we have a better understanding about it 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 the association control scheme. Considering both the long-term efficiency and fairness metrics, we propose optimized schemes to associate mobile users with APs, and approximation algorithms to re￾duce computation complexity of calculating optimal solutions. Although there is some previous work related to this topic [1][2][3], they all focus on the measurement study on vehicular internet access. To the best of our knowledge, this is the first theoretical work that investigates the optimization problem for association control over vehicular users in Wi-Fi networks. And being distinct from the previous research works, since the association solutions are updated in a frequent approach while the users are driving along the roads, this paper is concerned about the long-term performance in terms of efficiency and 978-1-4244-4634-6/09/$25.00 ©2009 IEEE 324 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:35:32 UTC from IEEE Xplore. Restrictions apply