Efficient Route Guidance in Vehicular Wireless Networks Yu Stephanie Sun",Lei Xie,Oi Alfred Chen',Sanglu Lu",Daoxu Chen *State Key Laboratory for Novel Software Technology,Nanjing University,China TUniversity of Michigan,USA Email:*sunyu0401@gmail.com,*Ixie@nju.edu.cn,falfchen@umich.edu,*{sanglu,cdx @nju.edu.cn Abstract-With the rapid proliferation of Wi-Fi technologies vehicles at one time instead of a single one.MCMF-R is in recent years,it has become possible to utilize the vehicular designed for heavy traffic such as situation in rush hours. wireless network to assist the route guidance for drivers in a co- operative approach,aiming to mitigating heavy traffic congestion. With a central control unit,the routing of MCMF-R can In this paper,we investigate into the route guidance problem in make full use of global traffic information. vehicular wireless network,and then propose two efficient routing 2)In order to mitigate the possibility of high communica- algorithms,i.e.,centralized route guidance and distributed route tion and computation overhead,we propose a distributed guidance,according to different situations.A hybrid framework algorithm,Traffic Splitting (TS),for the route guidance is then proposed to provide optimized routing decisions in a uniform way.Simulation results in Simulation of Urban MObility problem,which only uses local traffic information to (SUMO)indicate that,our route guidance schemes achieve much help make routing decisions.TS requires few computing better performance than traditional GPS-based navigation and and communication resources,thus it can be processed randomized routing. in parallel and more suitable for practical usage. Index Terms-Route Guidance;Vehicular Wireless Networks; 3)We propose a hybrid framework combining MCMF-R Energy-Efficiency;Optimization and TS,which are mutually complementary to each other.Using the realistic traffic generator Simulation I.INTRODUCTION of Urban MObility (SUMO)[4],we evaluate our algo- It is well known that traffic congestions can cause serious rithms in a real-world traffic map,and the result shows problems,such as fuel consumption,air pollution and even that our solutions can reduce the average travel time by economic problems.From Urban mobility report 1,the 40%than traditional ones. cost from traffic congestion now is more than $100 billion. nearly S750 for every commuter in the U.S.To mitigate this II.RELATED WORK situation,effective route guidance system should be deployed. Common vehicular wireless network architecture consists helping vehicles choosing faster routes to avoid congestions. of road side units (access point)which communicate with Traditional route guidance schemes leverage GPS module in travelling vehicles and provide information sharing service in vehicles to find the shortest path from the source to destination. local area.Based on this basic design,current research work However.these methods offer limited help for the current mainly focus on the routing protocols [5],access association congestion situations,which is mainly because:first,they are control [6]and information sharing [7]. unaware of the real-time congestion situations;second,when Traditional route guidance systems are based on GPS mod- all vehicles with the same requests are guided to the same ule and shortest path algorithm [8].Realizing their limitation shortest paths,this shortest path will face severe congestions of lacking real-time traffic information,recent research work and become far from the fastest path.To better solve the focus on employing new architectures such as neural network congestion problem,a new route guidance system which [9],Wireless Sensor Network (WSN)[10]to enhance the overcomes these limitations should be designed. information accuracy and routing efficiency.For vehicular Vehicular wireless network provides opportunities to design wireless network.the infrastructureless route guidance system a more effective vehicle routing scheme than before to avoid [11]have been studied in [12][13],which mainly rely on the traffic congestions.In this architecture,road-side access points inter-communication between vehicles to share information. (AP)are widely deployed [2][3],which can provide wireless For infrastructure-based system,latest research work can be access to users in moving vehicles and support data sharing found in problems such as travel time prediction [14],con- among drivers.Therefore,by sharing dynamic traffic informa- gestion avoidance [15],etc.Different from previous work,in tion in this network,it is possible to mitigate the congestion this paper we focus on the problem of utilizing road-side APs problems and further reduce the travel time of drivers. in the current vehicular wireless network architecture to find In this paper we study the route guidance in vehicular net- the fastest routes at the presence of congestion,and propose works,and propose two efficient routing algorithms according two algorithms according to different traffic conditions. to different conditions.The contributions of this paper are summarized as follows, III.PROBLEM FORMULATION 1)Based on the single-source single-destination pattern of In a typical traffic routing scenario,vehicles in need of route the routing requests during peak time,we propose a guidance will send their routing requests including the sources centralized algorithm,Minimum-Cost Maximum-Flow and destinations inside an area to the route guidance system, based Routing (MCMF-R),for the route guidance prob- and wait for the routing result.The area map can be denoted as lem,which can make routing decisions for a group of a directed graph G(V,E),where V and E are respectively the set of the intersections and the set of roads.We denote C as the Corresponding Author:Dr.Lei Xie,Ixie@nju.edu.cn. set of vehicles with routing requests.For each vehicle ciC, 978-1-4799-3083-8/14/$31.00©20141EEEEfficient Route Guidance in Vehicular Wireless Networks Yu Stephanie Sun∗ , Lei Xie∗ , Qi Alfred Chen† , Sanglu Lu∗ , Daoxu Chen∗ ∗State Key Laboratory for Novel Software Technology, Nanjing University, China †University of Michigan, USA Email: ∗ sunyu0401@gmail.com, ∗ lxie@nju.edu.cn, † alfchen@umich.edu, ∗{sanglu,cdx}@nju.edu.cn Abstract—With the rapid proliferation of Wi-Fi technologies in recent years, it has become possible to utilize the vehicular wireless network to assist the route guidance for drivers in a co￾operative approach, aiming to mitigating heavy traffic congestion. In this paper, we investigate into the route guidance problem in vehicular wireless network, and then propose two efficient routing algorithms, i.e., centralized route guidance and distributed route guidance, according to different situations. A hybrid framework is then proposed to provide optimized routing decisions in a uniform way. Simulation results in Simulation of Urban MObility (SUMO) indicate that, our route guidance schemes achieve much better performance than traditional GPS-based navigation and randomized routing. Index Terms—Route Guidance; Vehicular Wireless Networks; Energy-Efficiency; Optimization I. INTRODUCTION It is well known that traffic congestions can cause serious problems, such as fuel consumption, air pollution and even economic problems. From Urban mobility report [1], the cost from traffic congestion now is more than $100 billion, nearly $750 for every commuter in the U.S. To mitigate this situation, effective route guidance system should be deployed, helping vehicles choosing faster routes to avoid congestions. Traditional route guidance schemes leverage GPS module in vehicles to find the shortest path from the source to destination. However, these methods offer limited help for the current congestion situations, which is mainly because: first, they are unaware of the real-time congestion situations; second, when all vehicles with the same requests are guided to the same shortest paths, this shortest path will face severe congestions and become far from the fastest path. To better solve the congestion problem, a new route guidance system which overcomes these limitations should be designed. Vehicular wireless network provides opportunities to design a more effective vehicle routing scheme than before to avoid traffic congestions. In this architecture, road-side access points (AP) are widely deployed [2] [3], which can provide wireless access to users in moving vehicles and support data sharing among drivers. Therefore, by sharing dynamic traffic informa￾tion in this network, it is possible to mitigate the congestion problems and further reduce the travel time of drivers. In this paper we study the route guidance in vehicular net￾works, and propose two efficient routing algorithms according to different conditions. The contributions of this paper are summarized as follows, 1) Based on the single-source single-destination pattern of the routing requests during peak time, we propose a centralized algorithm, Minimum-Cost Maximum-Flow based Routing (MCMF-R), for the route guidance prob￾lem, which can make routing decisions for a group of Corresponding Author: Dr. Lei Xie, lxie@nju.edu.cn. vehicles at one time instead of a single one. MCMF-R is designed for heavy traffic such as situation in rush hours. With a central control unit, the routing of MCMF-R can make full use of global traffic information. 2) In order to mitigate the possibility of high communica￾tion and computation overhead, we propose a distributed algorithm, Traffic Splitting (TS), for the route guidance problem, which only uses local traffic information to help make routing decisions. TS requires few computing and communication resources, thus it can be processed in parallel and more suitable for practical usage. 3) We propose a hybrid framework combining MCMF-R and TS, which are mutually complementary to each other. Using the realistic traffic generator Simulation of Urban MObility (SUMO) [4], we evaluate our algo￾rithms in a real-world traffic map, and the result shows that our solutions can reduce the average travel time by 40% than traditional ones. II. RELATED WORK Common vehicular wireless network architecture consists of road side units (access point) which communicate with travelling vehicles and provide information sharing service in local area. Based on this basic design, current research work mainly focus on the routing protocols [5], access association control [6] and information sharing [7]. Traditional route guidance systems are based on GPS mod￾ule and shortest path algorithm [8]. Realizing their limitation of lacking real-time traffic information, recent research work focus on employing new architectures such as neural network [9], Wireless Sensor Network (WSN) [10] to enhance the information accuracy and routing efficiency. For vehicular wireless network, the infrastructureless route guidance system [11] have been studied in [12] [13], which mainly rely on the inter-communication between vehicles to share information. For infrastructure-based system, latest research work can be found in problems such as travel time prediction [14], con￾gestion avoidance [15], etc. Different from previous work, in this paper we focus on the problem of utilizing road-side APs in the current vehicular wireless network architecture to find the fastest routes at the presence of congestion, and propose two algorithms according to different traffic conditions. III. PROBLEM FORMULATION In a typical traffic routing scenario, vehicles in need of route guidance will send their routing requests including the sources and destinations inside an area to the route guidance system, and wait for the routing result. The area map can be denoted as a directed graph GhV, Ei, where V and E are respectively the set of the intersections and the set of roads. We denote C as the set of vehicles with routing requests. For each vehicle ci ∈ C, 978-1-4799-3083-8/14/$31.00 c 2014 IEEE