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©20141EEE
Efficient 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 cooperative 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 information 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 networks, 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 problem, 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 communication 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 algorithms 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 module 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], congestion 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
its routing request contains source si and destination di,where On the other hand,distributed routing makes decision siE V,diV.For road (u,v)EE,M(u,v)denotes the locally.There is no central control unit.so the routes are capacity of (u.v).i.e..maximum number of vehicles available computed locally in the nearby sinks.The dynamic traffic for travelling on it. information available is limited to a small range,e.g.,adjacent In regard to the routing result,the routing guidance system roads.For static traffic information,it can be pre-deployed and will reply to vehicle ci with a route Ri in the form of thus be global.Therefore,distributed route guidance scheme (o,1,,vk）,where vo=si,vk=di and v∈V,j= has a much smaller overhead in storage and computing,and 0...k.If we use Rsd to represent the set of all routes from thus more deployable.However,since it lacks global traffic si to di,then Ri should be in the set Rs.d. information,its solution is more likely to be a local optimum The routing target is to make the overall/average travel time one.This architecture can also be applied to Vehicular Ad of all vehicles to be minimum.So the objective of the route hoc NETworks (VANET)since we can choose any point in guidance problem can be represented as follows. the ad-hoc network as the sink minimize T(Ri) (1) B.Analysis Recall that T()is the key parameter in Eg.(1),in order to measure it,we first explore the travel time a vehicle spends subject to around an intersection.Assume that a vehicle is travelling on Ri∈Rs4,d, (2) road (u,v)and will turn to road (v,w),the time duration has two parts:the driving time D(u,v)and the waiting time (u,)∈E,l{ci:c∈C,(u,v)∈Rl≤M(u,v) (3) W(u,v,w),which is represented as follows, where T()is the time duration of route Ri.The second T((u.v.w))=D(u,v)+W(u.v.w) (4) constraint requires that the traffic flow on each road (u,v) should be no greater than its capacity. D(u.v)= Do(u,v) (5) In order to solve this route guidance problem,in this paper S(u.v) we consider two situations based on the infrastructures in vehicular network:centralized route guidance and distributed In Eg.(4).the driving time refers to the time the vehicle route guidance.In the centralized solution,the routing decision spends on the road without being influenced by other vehicles is made in a central control module and requires global or traffic lights.As shown in Eq.(5),it can be calculated using traffic information.In the distributed solution,there is no distance Do(u,v)and speed limit S(u,v)of road (u,v). central controlling and the algorithm only uses local traffic In regard to the waiting time,we measure it from the number information for route guidance. of red lights the vehicle is expected to wait.According to the assumption,the vehicle is on road (u,v)to (v,w),the number IV.SOLUTION of red lights it has to wait depends on both the set of current vehicles before it,F(u,v.w),and the number of vehicles A.System Architecture which can leave the road during one green light,L(u,v,w). Fig.I shows an example of route guidance system architec- We try to find the upper bound of the waiting time in our ture in vehicular networks.In this figure,the components are measurement as shown in Eg.(6). sinks,vehicle-side sensors and a central control unit.Sinks are usually APs in vehicular network,and as discussed in [21. these sinks keep communicating with sensors in the vehicles W(u,v,w)= F(u,v,w) +1 R(u,v,w) (6) such as GPS,cameras,mobile phones,etc.The central control L(u,v,w) unit will exchange data with sinks,but it will only be used in centralized routing.Within this infrastructure,the real-time L(u.v,w)= Gu,v,四）：S(u,v p(u,Uw)】 (7) traffic data and route requests will be shared,and we can utilize these resources to devise efficient route guidance algorithms. In Eq.(6)and Eq.(7),R(u,v,w)and G(u,v,w)represent the the time of one red light and one green light when turning from Central guidance only road (u,v)to (v,w)at intersection v.l is the sum of both Control Unit (average)vehicle length and the gap between two vehicles. p(u,v,w)denotes the density of vehicles during one green light,which is in the range of 0,1. With Eg.(4).T(Rc)can be measured by adding up the travel time of all road-to-road segments in R.. D ● ■ C.Baseline Routing Algorithm Fig.1:An example of route guidance system architecture in To evaluate the route guidance systems,it is essential to vehicular network construct a baseline routing algorithm whose ability is similar to the routing without any guidance.However,for vehicle set In centralized routing,the central control unit collects traffic C from s to d,simply randomly selecting routes from Rs.d information globally.In this way,not only the static traffic uniformly is not reasonable,since by using experiences or information such as the red light duration time.road length. maps,the majority of drivers'routing decisions without any speed limit,etc..but also the dynamic traffic information guidance are more likely to be around the shortest path. like real-time traffic movements can be used in the routing Based on the above understanding,we propose an improved decision for each vehicle.To handle such large amount of data, random routing algorithm,IRR for short.In IRR,we first the central control unit is expected to have abundant storage choose the shortest path from s to d.From the second path,to resources along with powerful computing devices. mimic the imperfection of human beings,we randomly delete
its routing request contains source si and destination di , where si ∈ V, di ∈ V . For road hu, vi ∈ E, M(u, v) denotes the capacity of hu, vi, i.e.,maximum number of vehicles available for travelling on it. In regard to the routing result, the routing guidance system will reply to vehicle ci with a route Ri in the form of hv0, v1, . . . , vki, where v0 = si , vk = di and vj ∈ V, j = 0 . . . k. If we use Rsi,di to represent the set of all routes from si to di , then Ri should be in the set Rsi,di . The routing target is to make the overall/average travel time of all vehicles to be minimum. So the objective of the route guidance problem can be represented as follows, minimize X ci∈C T (Ri) (1) subject to Ri ∈ Rsi,di , (2) ∀hu, vi ∈ E, |{ci : ci ∈ C,hu, vi ∈ Ri}| ≤ M(u, v). (3) where T (·) is the time duration of route Ri . The second constraint requires that the traffic flow on each road hu, vi should be no greater than its capacity. In order to solve this route guidance problem, in this paper we consider two situations based on the infrastructures in vehicular network: centralized route guidance and distributed route guidance. In the centralized solution, the routing decision is made in a central control module and requires global traffic information. In the distributed solution, there is no central controlling and the algorithm only uses local traffic information for route guidance. IV. SOLUTION A. System Architecture Fig.1 shows an example of route guidance system architecture in vehicular networks. In this figure, the components are sinks, vehicle-side sensors and a central control unit. Sinks are usually APs in vehicular network, and as discussed in [2], these sinks keep communicating with sensors in the vehicles such as GPS, cameras, mobile phones, etc. The central control unit will exchange data with sinks, but it will only be used in centralized routing. Within this infrastructure, the real-time traffic data and route requests will be shared, and we can utilize these resources to devise efficient route guidance algorithms. Central Control Unit Sink Sink Sink centralized route guidance only Fig. 1: An example of route guidance system architecture in vehicular network In centralized routing, the central control unit collects traffic information globally. In this way, not only the static traffic information such as the red light duration time, road length, speed limit, etc., but also the dynamic traffic information like real-time traffic movements can be used in the routing decision for each vehicle. To handle such large amount of data, the central control unit is expected to have abundant storage resources along with powerful computing devices. On the other hand, distributed routing makes decision locally. There is no central control unit, so the routes are computed locally in the nearby sinks. The dynamic traffic information available is limited to a small range, e.g., adjacent roads. For static traffic information, it can be pre-deployed and thus be global. Therefore, distributed route guidance scheme has a much smaller overhead in storage and computing, and thus more deployable. However, since it lacks global traffic information, its solution is more likely to be a local optimum one. This architecture can also be applied to Vehicular Ad hoc NETworks (VANET) since we can choose any point in the ad-hoc network as the sink. B. Analysis Recall that T (·) is the key parameter in Eq. (1), in order to measure it, we first explore the travel time a vehicle spends around an intersection. Assume that a vehicle is travelling on road hu, vi and will turn to road hv, wi, the time duration has two parts: the driving time D(u, v) and the waiting time W(u, v, w), which is represented as follows, T (hu, v, wi) = D(u, v) + W(u, v, w) (4) D(u, v) = D0(u, v) S(u, v) (5) In Eq.(4), the driving time refers to the time the vehicle spends on the road without being influenced by other vehicles or traffic lights. As shown in Eq.(5) , it can be calculated using distance D0(u, v) and speed limit S(u, v) of road hu, vi. In regard to the waiting time, we measure it from the number of red lights the vehicle is expected to wait. According to the assumption, the vehicle is on road hu, vi to hv, wi, the number of red lights it has to wait depends on both the set of current vehicles before it, F(u, v, w), and the number of vehicles which can leave the road during one green light, L(u, v, w). We try to find the upper bound of the waiting time in our measurement as shown in Eq.(6). W(u, v, w) = |F(u, v, w)| L(u, v, w) + 1 · R(u, v, w) (6) L(u, v, w) = G(u, v, w) · S(u, v) l · ρ(u, v, w) (7) In Eq.(6) and Eq.(7), R(u, v, w) and G(u, v, w) represent the the time of one red light and one green light when turning from road hu, vi to hv, wi at intersection v. l is the sum of both (average) vehicle length and the gap between two vehicles. ρ(u, v, w) denotes the density of vehicles during one green light, which is in the range of [0, 1]. With Eq.(4), T (Rc) can be measured by adding up the travel time of all road-to-road segments in Rc. C. Baseline Routing Algorithm To evaluate the route guidance systems, it is essential to construct a baseline routing algorithm whose ability is similar to the routing without any guidance. However, for vehicle set C from s to d, simply randomly selecting routes from Rs,d uniformly is not reasonable, since by using experiences or maps, the majority of drivers’ routing decisions without any guidance are more likely to be around the shortest path. Based on the above understanding, we propose an improved random routing algorithm, IRR for short. In IRR, we first choose the shortest path from s to d. From the second path, to mimic the imperfection of human beings, we randomly delete
an edge in the previous path,then find the shortest path again of vehicles available on the road (shown in line 2 in as a new path.This process will continue until the needed Algorithm 1,where D()and l is introduced in Section number of paths is reached.In this way,these routes are very IV-B.Lo(u,v)is the number of lanes in road (u,v)). close to the shortest path but not strictly the top C shortest ● Cost.The cost()for minimum-cost maximum-flow prob- routes.IRR combines the proximity to the shortest path and lem is the travel time T()for route guidance problem. imperfection of human beings,which can be viewed as the As shown in Eg.(4).it will be a function of the traffic random routing decisions made by some local taxi drivers. flow.However,compared to cost(),T()has an extra parameter w.To solve this problem,we can first replace D.Centralized Solution w with a new parameter,the former intersection t before 1)Motivation:When the traffic is not heavy,simply using entering edge (u,v).cost()will only be used when classical guidance techniques such as GPS can handle all calculating the shortest path in MCMF(.).So if using routing requests without any congestion.So the centralized popular shortest path algorithm such as Dijkstra,SPFA route guidance in this paper focuses on the situation when the and etc..t should be already known when in need of traffic is very heavy,where large number of vehicles needs value cost(u.v).In this way,value of T((t,u,v))can be to travel on the main roads and severe traffic jams are likely used as cost(u,v)in MCMF(). to take place.In these cases,the traffic condition takes on a Extracting Paths.From the result of MCMF(),we single-source single-destination pattern.In this way,the two can execute graph traversals from source to destination, targets of our centralized solution are listed as follows. and extract travel paths one by one until there is no 1)Maximize the number of vehicles that can reach the positive flow on any edges.These travel paths then will destination be assigned to the vehicles with routing request as their 2)Minimize the total time duration from source to desti- routing results. nation(refer to the objective in problem formulation) Algorithm 1 MCMF-R Algorithm In this way,we can solve as many routing requests as possible, Input:routing requests (si,di)for each ciEC while sufficiently reducing the overall travel time of vehicular Output:Ri for ci users at the same time. 1:∈E,f(u,v)=0: For vehicle set C to travel from s to d,the routing problem 2 VE E:c(u,v)=D().Lo(u,v): can be represented as Fig.2.If we treat traffic as the flow and the travel time as the cost,centralized route guidance problem 3:partition set C into Cj,j=1,2,...,where ciCj share the same routing request (sj,dj) with single source and single destination can be solved as a 4:for all C;do minimum-cost maximum-flow problem,which is the core idea call MCMF(sj,dj,Cj,cost())to update f(); in the centralized solution. 6:end for 7:For each c;EC,extracting path Ri from f(); c)Multi-Source Multi-Destination Routing:In the real world,the routing requests will often have multiple sources and multiple destinations.Since minimum-cost maximum-flow algorithm is designed for single source and single destination, Fig.2:Centralized routing problem can be reduced to a routing before using it we need to first group the vehicles with problem from source s to destination d the same routing request (same si and di).By doing so, the original vehicle set C is partitioned into small subsets, 2)Minimum-Cost Maximum-Flow based Routing: Cj,j=1,2,....Vehicles in the same subset will have a)Minimum-Cost Maximum-Flow Problem:In the the same source and destination (line 3 in Algorithm 1). minimum-cost maximum-flow problem,there is a directed Then we can use minimum-cost maximum-flow algorithm for graph G(V,E)with source sV and destination(sink)d each subset,as shown in line 4 to 6 in Algorithm 1.When V,edge (u,v)EE has capacity c(u,v)>0,flow f(u,v)>0 processing,larger subsets will have higher priority in the order. and cost cost(u,v)>0.The total flow is uev f(s,v)and Besides grouping same routing requests,if the sizes of the the cost of sending this flow is)co) groups are too small to have good routing performances,we The objective of this problem is to find the cheapest possible can also merge the sources/destinations which are near to each way of sending a certain amount of flow through a flow other geographically into one common source/destination to network.The solution used in this paper [16]can be viewed as form larger subsets. 3)Analysis:The MCMF-R is meant to achieve the two a generalization of the maximum-flow algorithm called Ford- Fulkerson algorithm.The main idea is that while the original targets listed in Section IV-D1,which satisfies the objective in Section III.So if the travel time estimation is accurate enough. Ford-Fulkerson algorithm is seeking an augmenting path,this solution aims to find the one with the minimum cost instead the routing result of MCMF-R will be exactly the same as the b)Minimum-Cost Maximum-Flow based Routing:Based theoretical optimal solution in problem definition.By using on the analysis in Section IV-D1,we propose Minimum- MCMF algorithm,MCMF-R can make routing decisions for a vehicle flow at one time instead of a single vehicle,which Cost Maximum-Flow based Routing,MCMF-R for short,to solve the centralized route guidance problem.The algorithm increases the decision speed by the factor of the flow size is shown in Algorithm 1,where MCMF()means calling the In multi-source multi-destination routing part,the order of processing vehicle subsets is critical for routing efficiency and minimum-cost maximum-flow problem solution [16]. fairness.The earlier the subset is fed into MCMF(),the Flow and Capacity.In our routing problem,we re- shorter path it will get.So the best way to minimize the overall gard the traffic flow as f(u,v),so f(u,v) time duration is to process bigger size subset first.For fairness, 2e,w)∈E,w≠uF(u,v,o)l.Capacity c(u,v）is similar this also ensures that the majority of vehicles have the priority to M(),and is calculated as the maximum number to choose better routes
an edge in the previous path, then find the shortest path again as a new path. This process will continue until the needed number of paths is reached. In this way, these routes are very close to the shortest path but not strictly the top |C| shortest routes. IRR combines the proximity to the shortest path and imperfection of human beings, which can be viewed as the random routing decisions made by some local taxi drivers. D. Centralized Solution 1) Motivation: When the traffic is not heavy, simply using classical guidance techniques such as GPS can handle all routing requests without any congestion. So the centralized route guidance in this paper focuses on the situation when the traffic is very heavy, where large number of vehicles needs to travel on the main roads and severe traffic jams are likely to take place. In these cases, the traffic condition takes on a single-source single-destination pattern. In this way, the two targets of our centralized solution are listed as follows, 1) Maximize the number of vehicles that can reach the destination 2) Minimize the total time duration from source to destination (refer to the objective in problem formulation) In this way, we can solve as many routing requests as possible, while sufficiently reducing the overall travel time of vehicular users at the same time. For vehicle set C to travel from s to d, the routing problem can be represented as Fig.2. If we treat traffic as the flow and the travel time as the cost, centralized route guidance problem with single source and single destination can be solved as a minimum-cost maximum-flow problem, which is the core idea in the centralized solution. s d Fig. 2: Centralized routing problem can be reduced to a routing problem from source s to destination d 2) Minimum-Cost Maximum-Flow based Routing: a) Minimum-Cost Maximum-Flow Problem: In the minimum-cost maximum-flow problem, there is a directed graph GhV, Ei with source s ∈ V and destination (sink) d ∈ V , edge (u, v) ∈ E has capacity c(u, v) > 0, flow f(u, v) ≥ 0 and cost cost(u, v) ≥ 0. The total flow is P u∈V f(s, v) and the cost of sending this flow is P hu,vi∈E f(u, v) · cost(u, v). The objective of this problem is to find the cheapest possible way of sending a certain amount of flow through a flow network. The solution used in this paper [16] can be viewed as a generalization of the maximum-flow algorithm called FordFulkerson algorithm. The main idea is that while the original Ford-Fulkerson algorithm is seeking an augmenting path, this solution aims to find the one with the minimum cost instead. b) Minimum-Cost Maximum-Flow based Routing: Based on the analysis in Section IV-D1, we propose MinimumCost Maximum-Flow based Routing, MCMF-R for short, to solve the centralized route guidance problem. The algorithm is shown in Algorithm 1, where MCMF(·) means calling the minimum-cost maximum-flow problem solution [16]. • Flow and Capacity. In our routing problem, we regard the traffic flow as P f(u, v), so f(u, v) = hv,wi∈E,w6=u |F(u, v, w)|. Capacity c(u, v) is similar to M(·), and is calculated as the maximum number of vehicles available on the road (shown in line 2 in Algorithm 1, where D(·) and l is introduced in Section IV-B, L0(u, v) is the number of lanes in road hu, vi). • Cost. The cost(·) for minimum-cost maximum-flow problem is the travel time T (·) for route guidance problem. As shown in Eq.(4), it will be a function of the traffic flow. However, compared to cost(·), T (·) has an extra parameter w. To solve this problem, we can first replace w with a new parameter, the former intersection t before entering edge hu, vi. cost(·) will only be used when calculating the shortest path in MCMF(·). So if using popular shortest path algorithm such as Dijkstra, SPFA and etc., t should be already known when in need of value cost(u, v). In this way, value of T (ht, u, vi) can be used as cost(u, v) in MCMF(·). • Extracting Paths. From the result of MCMF(·), we can execute graph traversals from source to destination, and extract travel paths one by one until there is no positive flow on any edges. These travel paths then will be assigned to the vehicles with routing request as their routing results. Algorithm 1 MCMF-R Algorithm Input: routing requests hsi , dii for each ci ∈ C Output: Ri for ci 1: ∀ ∈ E, f(u, v) = 0; 2: ∀ ∈ E, c(u, v) = D(u,v) l · L0(u, v); 3: partition set C into Cj , j = 1, 2, . . ., where ci ∈ Cj share the same routing request hsj , dj i 4: for all Cj do 5: call MCMF(sj , dj , Cj , cost(·)) to update f(·); 6: end for 7: For each ci ∈ C, extracting path Ri from f(·); c) Multi-Source Multi-Destination Routing: In the real world, the routing requests will often have multiple sources and multiple destinations. Since minimum-cost maximum-flow algorithm is designed for single source and single destination, before using it we need to first group the vehicles with the same routing request (same si and di). By doing so, the original vehicle set C is partitioned into small subsets, Cj , j = 1, 2, . . .. Vehicles in the same subset will have the same source and destination (line 3 in Algorithm 1). Then we can use minimum-cost maximum-flow algorithm for each subset, as shown in line 4 to 6 in Algorithm 1. When processing, larger subsets will have higher priority in the order. Besides grouping same routing requests, if the sizes of the groups are too small to have good routing performances, we can also merge the sources/destinations which are near to each other geographically into one common source/destination to form larger subsets. 3) Analysis: The MCMF-R is meant to achieve the two targets listed in Section IV-D1, which satisfies the objective in Section III. So if the travel time estimation is accurate enough, the routing result of MCMF-R will be exactly the same as the theoretical optimal solution in problem definition. By using MCMF algorithm, MCMF-R can make routing decisions for a vehicle flow at one time instead of a single vehicle, which increases the decision speed by the factor of the flow size. In multi-source multi-destination routing part, the order of processing vehicle subsets is critical for routing efficiency and fairness. The earlier the subset is fed into MCMF(·), the shorter path it will get. So the best way to minimize the overall time duration is to process bigger size subset first. For fairness, this also ensures that the majority of vehicles have the priority to choose better routes
E.Distributed Solution The traffic splitting algorithm in v discussed above is shown 1)Motivation:Centralized route guidance solution above in Algorithm 2.In the algorithm,all edges adjacent to v should requires large storage space and powerful enough computing be deleted temporarily.After this operation.it is ensured that devices for handling global traffic information and making the shortest path generated in line 2 to 4 will not include routing decisions for all requests.However,these resources are point v.so that the calculation result excludes the cases that sometimes rather limited.Therefore.a distributed solution is the vehicle travels back to v after leaving v. essential to be proposed,which is able to make route decision Algorithm 2 Traffic Splitting (TS)Algorithm with limited traffic information.As discussed in Section IV-A the distributed solution can only obtain the dynamic traffic Input:u,v.Cuv),w1...wp information in adjacent roads collected in one AP. Output:vehicle sets f1...fp In G(V,E),we denote the vehicles travelling on (u,v)to 1:f=0,i=1..p be a vehicle set Cu)For the vehicles in Cu.)when the 2:for i 1...p do sink at v processes their routing requests,v will be their 3: calculate the shortest path from w;to all other inter- common start point.So single source shortest path (SSSP) sections using SSSP algorithm such as Dijkstra; algorithms can be used in the sink at v for routing,serving 4:end for as a feasible distributed routing algorithm.Traditional GPS 5:while ie..fil<C(u.v)l do route guidances are mainly based on this idea.However,if 6 for all ck∈Cudo every vehicle travel in their shortest paths,extremely heavy m∈arg min T(u,v,,,Dk)月 traffic jams could take place,and the resulted solutions for 1∈1..D each vehicle are very likely to largely deviate from the optimal 8: fm=fm+ick}; one (shown in Section V-C). 9: update T((u,v,wm,...,D)); This huge difference between the expected result and the 10 end for actual result is due to the missing information of dynamic 11:end while traffic.With the sinks'dynamic traffic information about We name this algorithm Traffic Splitting Algorithm,TS for adjacent roads,it will be a wise choice to split the traffic short.Its complexity is in O(pn-+pn),where p and n are to different roads around an intersection and thus avoid traffic the number of v's adjacent roads and intersections respectively. jams on one single road TS only requires two message exchanges between vehicles and 2)Traffic Splitting:For the intersection v,we assume that the sink,so the communication overhead is a linear function there are p roads adjacent to it,denoted by (v,w;i= 1...p}.Our target is to find a strategy to split the traffic of the vehicle number,which is quite lightweight. 3)Analysis:For the estimation of T((wi.....D)).TS Cu.v)into vehicle sets fi,i=1...p where Ufi =C(u.v). uses the shortest paths,which includes no dynamic traffic For each vehicle in set fi,the next intersection of their routing information.This will lead to mistakes in choosing roads on result will be w.In other words,after these vehicles pass road line 7 to 8 in Algorithm 2.and as we stated before,the (u,v),they will turn to road (v,wi). difference between the routing of shortest path and reality For a vehicle ck which travels on (u,v)to dk,if it is can be very huge.However,this is actually the limitation classified into set fi,setting wi as the next intersection of from the local information assumption in Section IV-E1.Since the routing solution should be less time-consuming than any the limitation of shortest path estimation will increase with other intersections in the set w;:jef1...p.This the congestion condition,the performance of TS will degrade can be described as follows, when the traffic is heavy. T((u,v,wi;...,dx))=minfT((u,v,wj;...,dx))} (8) When splitting traffic in line 6 to 10,the vehicle ck which is chosen at an earlier time is more possible to be designated where i,j=1...p. into a shorter path.Considering this,the order of choosing ck In Eq.(8),T((u,v.wi.....d)is equal to from C.,introduces some unfairness in our algorithm.To solve it,we can use some metric such as distance to destination T(u,U,)+D(v,w)+T(,,d) (9) urgent level of the request,etc.to rank the vehicles in Cv.For simplification,in the paper all vehicles is considered to have where i=1...p,and D()is the drive time. no difference with each other. In Eq.(9),the time duration from u to d through (u,v) 4)Example of Traffic Splitting Algorithm:For better illus- and (v,w;)consists of the travel time on road (u,v)and the tration of TS algorithm,Fig.3 gives an example of the traffic travel time from road (v.wi)to dk.With the dynamic traffic information of adjacent roads F(u,v,wi),we can calculate splitting process in one intersection.In the figure,intersection v has 4 adjacent roads.There are 4 vehicles travelling on road T((u,v,wi))using Eq.(4).For the travel time from road u,v)and requesting routing to common destination d,and (v,w)to dk,we lack the dynamic information to get a better their next intersection can be w1,w2,or w3.Table I gives estimation.So we calculate it using the sum of drive time. the initial parameters for routing these vehicles.After the D(v,wi)defined in Eq.(5),and the travel time of the shortest calculation of SSSP algorithm for 3 times,we obtain all three path from wi to dk,denoted as T(wi,...,d)). T((w,...,d))values in table I. In the sink at v,for each ckECu and each intersection ,i=1.…p and w:≠u,we have T(u,v,u,,dk) Then we choose the wi with the smallest T((u,v,wi,...,d)) to be the next step of ck,and add ck to fi.After all vehicles in C)have been processed,the traffic splitting of the sink at v finishes.In the next intersection wi.sink at w;will carry out the same traffic splitting process,and guide ck to the next intersection.This routing will relay in each intersection,and ck will finally reach dk. (c) (d) Fig.3:Example of the Traffic Splitting (TS)algorithm process
E. Distributed Solution 1) Motivation: Centralized route guidance solution above requires large storage space and powerful enough computing devices for handling global traffic information and making routing decisions for all requests. However, these resources are sometimes rather limited. Therefore, a distributed solution is essential to be proposed, which is able to make route decision with limited traffic information. As discussed in Section IV-A, the distributed solution can only obtain the dynamic traffic information in adjacent roads collected in one AP. In GhV, Ei, we denote the vehicles travelling on hu, vi to be a vehicle set Chu,vi . For the vehicles in Chu,vi , when the sink at v processes their routing requests, v will be their common start point. So single source shortest path (SSSP) algorithms can be used in the sink at v for routing, serving as a feasible distributed routing algorithm. Traditional GPS route guidances are mainly based on this idea. However, if every vehicle travel in their shortest paths, extremely heavy traffic jams could take place, and the resulted solutions for each vehicle are very likely to largely deviate from the optimal one (shown in Section V-C). This huge difference between the expected result and the actual result is due to the missing information of dynamic traffic. With the sinks’ dynamic traffic information about adjacent roads, it will be a wise choice to split the traffic to different roads around an intersection and thus avoid traffic jams on one single road. 2) Traffic Splitting: For the intersection v, we assume that there are p roads adjacent to it, denoted by {hv, wii|i = 1 . . . p}. Our target is to find a strategy to split the traffic Chu,vi into vehicle sets fi , i = 1 . . . p where ∪fi = Chu,vi . For each vehicle in set fi , the next intersection of their routing result will be wi . In other words, after these vehicles pass road hu, vi, they will turn to road hv, wii. For a vehicle ck which travels on hu, vi to dk, if it is classified into set fi , setting wi as the next intersection of the routing solution should be less time-consuming than any other intersections in the set {wj : j ∈ {1 . . . p} − {i}}. This can be described as follows, T (hu, v, wi , . . . , dki) = min{T (hu, v, wj, . . . , dki)} (8) where i, j = 1 . . . p. In Eq.(8), T (hu, v, wi , . . . , dki) is equal to T (hu, v, wii) + D(v, wi) + T (hwi , . . . , dki) (9) where i = 1 . . . p, and D(·) is the drive time. In Eq.(9), the time duration from u to dk through hu, vi and hv, wii consists of the travel time on road hu, vi and the travel time from road hv, wii to dk. With the dynamic traffic information of adjacent roads F(u, v, wi), we can calculate T (hu, v, wii) using Eq.(4). For the travel time from road hv, wii to dk, we lack the dynamic information to get a better estimation. So we calculate it using the sum of drive time, D(v, wi) defined in Eq.(5), and the travel time of the shortest path from wi to dk, denoted as T (hwi , . . . , dki). In the sink at v, for each ck ∈ Chu,vi and each intersection wi , i = 1 . . . p and wi 6= u, we have T (hu, v, wi , . . . , dki). Then we choose the wi with the smallest T (hu, v, wi , . . . , dki) to be the next step of ck, and add ck to fi . After all vehicles in Chu,vi have been processed, the traffic splitting of the sink at v finishes. In the next intersection wi , sink at wi will carry out the same traffic splitting process, and guide ck to the next intersection. This routing will relay in each intersection, and ck will finally reach dk. The traffic splitting algorithm in v discussed above is shown in Algorithm 2. In the algorithm, all edges adjacent to v should be deleted temporarily. After this operation, it is ensured that the shortest path generated in line 2 to 4 will not include point v, so that the calculation result excludes the cases that the vehicle travels back to v after leaving v. Algorithm 2 Traffic Splitting (TS) Algorithm Input: u, v, Chu,vi , w1 . . . wp Output: vehicle sets f1 . . . fp 1: fi = ∅, i = 1 . . . p; 2: for i = 1. . . p do 3: calculate the shortest path from wi to all other intersections using SSSP algorithm such as Dijkstra; 4: end for 5: while P i∈1...p |fi | < |Chu,vi | do 6: for all ck ∈ Cv do 7: m ∈ arg min i∈1...p T (hu, v, wi , . . . , Dki); 8: fm = fm + {ck}; 9: update T (hu, v, wm, . . . , Dki); 10: end for 11: end while We name this algorithm Traffic Splitting Algorithm, TS for short. Its complexity is in O(pn2 + pn), where p and n are the number of v’s adjacent roads and intersections respectively. TS only requires two message exchanges between vehicles and the sink, so the communication overhead is a linear function of the vehicle number, which is quite lightweight. 3) Analysis: For the estimation of T (hwi , . . . , Dki), TS uses the shortest paths, which includes no dynamic traffic information. This will lead to mistakes in choosing roads on line 7 to 8 in Algorithm 2, and as we stated before, the difference between the routing of shortest path and reality can be very huge. However, this is actually the limitation from the local information assumption in Section IV-E1. Since the limitation of shortest path estimation will increase with the congestion condition, the performance of TS will degrade when the traffic is heavy. When splitting traffic in line 6 to 10, the vehicle ck which is chosen at an earlier time is more possible to be designated into a shorter path. Considering this, the order of choosing ck from Cv introduces some unfairness in our algorithm. To solve it, we can use some metric such as distance to destination, urgent level of the request, etc. to rank the vehicles in Cv. For simplification, in the paper all vehicles is considered to have no difference with each other. 4) Example of Traffic Splitting Algorithm: For better illustration of TS algorithm, Fig.3 gives an example of the traffic splitting process in one intersection. In the figure, intersection v has 4 adjacent roads. There are 4 vehicles travelling on road hu, vi and requesting routing to common destination d, and their next intersection can be w1, w2, or w3. Table I gives the initial parameters for routing these vehicles. After the calculation of SSSP algorithm for 3 times, we obtain all three T (hw, . . . , di) values in table I. v 9 w1 w3 w2 Waiting u (a) v 9 w1 w3 w2 Waiting u (b) v 9 w1 w3 w2 Waiting u (c) v 9 w1 w3 w2 Waiting u (d) Fig. 3: Example of the Traffic Splitting (TS) algorithm process
As shown in Fig.3a,at the beginning 4 vehicles are V.PERFORMANCE EVALUATION placed in the waiting area waiting for routing,and A.Evaluation Method fi f2,f3 are all empty.Using Eq.(9).T((u,v,w1,....d))= T((u,v,w2,...,d)=9,which is the smallest among the 3 In order to test the routing performances of MCMF-R candidate roads.Thus we pick f to add the first vehicle. and TS,we use the realistic traffic generator Simulation of Since L(u,v,w1)=2,the time of waiting red light will Urban MObility (SUMO)[4]to construct the large road increase R(u,v.w1)=2 after adding 2 vehicles.So with network and generate vehicle traffic.In the simulation,we the same analysis as above,we can add another vehicle randomly generate routing requests as input,and then write into set f (Fig.3b).Now fi has traffic volume 2 and C++programs of the route guidance algorithm to make routing T((u,v,w1,...,d))=11,which is no longer the smallest. decisions for them.To test the performance in heavy traffic Now T((u,v,w2,...,d))=10 becomes the smallest,and we condition,we add background traffic in some experiments. can add 1 vehicle to f2(Fig.3c)and after the value increases After that,we use these routing decisions to generate vehicle to 12.Now T(u,v,w1: ...d))=11 is the smallest again,so traffic in SUMO,and record the travel time for each vehicle. in Fig.3d the last vehicle in the waiting area is added to f1. With the travel time,our evaluation is in two dimensions: In this way,we obtain the routing solution:3 vehicles travel Time Efficiency:measured using the average travel time towards w and 1 vehicle travels towards w2. of the vehicles. TABLE I:Parameters Related to the Routing Example in Fig.3 Fairness:measured using the standard deviation of the travel time of the vehicles. intersection w T(u,,四) B.Simulation Parameter 1《0、....d】 6 2 For the road topologies,we construct the road network LD（U.心) L(u,, based on the map of Nanjing city,China.We extract the L.U.D】 central part of Nanjing from openstreetmap [17],and convert it to the map used in SUMO.For convenience,we assume F.Comparison and Hybrid Route Guidance framework that vehicles can turn to any roads adjacent to the road they We summarize the performance of MCMF-R,TS,IRR and travel on.For traffic light setting,since the extracted map traditional GPS routing in Table II.For the time efficiency from openstreetmap does not have traffic light information of the two solutions proposed in this paper,MCMF-R is we manually set the traffic lights at all intersections to be 30 closer to the optimal solution,but imperfect measurement of seconds red light duration and 30 seconds green light duration. travel time makes it underestimate or overestimate the current congestion situation to some extent.TS becomes much worse TABLE III:Setting of the Vehicles in the Simulation than MCMF-R when heavy traffic take place.But since it's Parameter Value ●escnption greedy,it is better than MCMF-R in light traffic condition, accel 10(m/s) acceleration ability of vehicle decel 10(m/s2) deceleration ability of vehicle where the latter overestimates the congestion.In fairness.TS sigma driver imperfection (between 0 and I) is better since MCMF-R considers more global optimization, 3m】 The vehicle's length which needs some vehicles to sacrifice.MCMF-R needs global nimal gap bet en maxSpeed 80(m/s) vehicle's maximum velocity dynamic traffic information and central control,so it has bigger communication overhead compared to other algorithms. The parameters about the vehicles are listed in table III TABLE II:Comparison of MCMF-R,TS,IRR and Traditional For routing request generation,we first randomly generate 200 GPS Routing source and destination pairs,and then assign random vehicle volumes to them.For background traffic,we use repeated Algorithm Overhead Light Tn vehicles in SUMO,which have the repeat period to be 2. MCME-R C.Simulation Result and Analysis GPS Routing casv ow medium very weak 840 Algorithm 3 Hybrid Route Guidance Framework Input:routing requests reg,current traffic condition tc 1:if isRushHour(req,tc)then use MCMF-R 3:else 100 200300 400500 600 use TS Number of Routing Requests 5:end if Fig.5:Average flow size distribution of MCMF-R algorithm Considering that MCMF-R has high time efficiency for In this section.we will evaluate the performance of cen- heavy traffic and TS has low overhead and better fairness tralized routing algorithm MCMF-R and distributed routing for other traffic conditions,we combine them and propose algorithm TS.Besides IRR algorithm,we also use the tradi- a hybrid framework for route guidance according to different tional GPS routing as the comparison algorithm,which keeps traffic pattern,which are shown in Algorithm 3.In normal using shortest path algorithm in routing.Fig.5 shows the traffic period,TS can serve most of the routing requests with high grouping performance of MCMF-R,and the simulation result efficiency and low overhead.When the system detects rush about time efficiency and fairness is shown in Fig.4. hour pattern,the routing algorithm should then be switched to Fig.5 shows the average vehicle flow size managed by MCMF-R.The hybrid framework balances routing overhead MCMF-R for different routing request volumes of one source and time efficiency,providing both better deployment and and destination pair.Between volume 0 to 300,the average routing decisions than IRR and traditional GPS under different flow size is around 15 and between 300 to 550,it increases to traffic intensity situations. 25.This indicates that MCMF-R algorithm can achieve around
As shown in Fig.3a, at the beginning 4 vehicles are placed in the waiting area waiting for routing, and f1, f2, f3 are all empty. Using Eq.(9), T (hu, v, w1, . . . , di) = T (hu, v, w2, . . . , di = 9, which is the smallest among the 3 candidate roads. Thus we pick f1 to add the first vehicle. Since L(u, v, w1) = 2, the time of waiting red light will increase R(u, v, w1) = 2 after adding 2 vehicles. So with the same analysis as above, we can add another vehicle into set f1 (Fig.3b). Now f1 has traffic volume 2 and T (hu, v, w1, . . . , di) = 11, which is no longer the smallest. Now T (hu, v, w2, . . . , di) = 10 becomes the smallest, and we can add 1 vehicle to f2 (Fig.3c) and after the value increases to 12. Now T (hu, v, w1, . . . , di) = 11 is the smallest again, so in Fig.3d the last vehicle in the waiting area is added to f1. In this way, we obtain the routing solution: 3 vehicles travel towards w1 and 1 vehicle travels towards w2. TABLE I: Parameters Related to the Routing Example in Fig.3 intersection w w1 w2 w3 T(hu, v, wi) 2 1 1 T(hw, . . . , di) 6 7 12 D(v, w) 1 2 1 L(u, v, w) 2 1 1 R(u, v, w) 2 2 1 F. Comparison and Hybrid Route Guidance Framework We summarize the performance of MCMF-R, TS, IRR and traditional GPS routing in Table II. For the time efficiency of the two solutions proposed in this paper, MCMF-R is closer to the optimal solution, but imperfect measurement of travel time makes it underestimate or overestimate the current congestion situation to some extent. TS becomes much worse than MCMF-R when heavy traffic take place. But since it’s greedy, it is better than MCMF-R in light traffic condition, where the latter overestimates the congestion. In fairness, TS is better since MCMF-R considers more global optimization, which needs some vehicles to sacrifice. MCMF-R needs global dynamic traffic information and central control, so it has bigger communication overhead compared to other algorithms. TABLE II: Comparison of MCMF-R, TS, IRR and Traditional GPS Routing Algorithm Overhead Fairness Time Efficiency Light Traffic Heavy Traffic MCMF-R hard medium medium strong TS medium high strong medium IRR easy medium medium weak GPS Routing easy low medium very weak Algorithm 3 Hybrid Route Guidance Framework Input: routing requests req, current traffic condition tc 1: if isRushHour(req, tc) then 2: use MCMF-R 3: else 4: use TS 5: end if Considering that MCMF-R has high time efficiency for heavy traffic and TS has low overhead and better fairness for other traffic conditions, we combine them and propose a hybrid framework for route guidance according to different traffic pattern, which are shown in Algorithm 3. In normal period, TS can serve most of the routing requests with high efficiency and low overhead. When the system detects rush hour pattern, the routing algorithm should then be switched to MCMF-R. The hybrid framework balances routing overhead and time efficiency, providing both better deployment and routing decisions than IRR and traditional GPS under different traffic intensity situations. V. PERFORMANCE EVALUATION A. Evaluation Method In order to test the routing performances of MCMF-R and TS, we use the realistic traffic generator Simulation of Urban MObility (SUMO) [4] to construct the large road network and generate vehicle traffic. In the simulation, we randomly generate routing requests as input, and then write C++ programs of the route guidance algorithm to make routing decisions for them. To test the performance in heavy traffic condition, we add background traffic in some experiments. After that, we use these routing decisions to generate vehicle traffic in SUMO, and record the travel time for each vehicle. With the travel time, our evaluation is in two dimensions: • Time Efficiency: measured using the average travel time of the vehicles. • Fairness: measured using the standard deviation of the travel time of the vehicles. B. Simulation Parameter For the road topologies, we construct the road network based on the map of Nanjing city, China. We extract the central part of Nanjing from openstreetmap [17], and convert it to the map used in SUMO. For convenience, we assume that vehicles can turn to any roads adjacent to the road they travel on. For traffic light setting, since the extracted map from openstreetmap does not have traffic light information, we manually set the traffic lights at all intersections to be 30 seconds red light duration and 30 seconds green light duration. TABLE III: Setting of the Vehicles in the Simulation Parameter Value Description accel 10(m/s2 ) acceleration ability of vehicle decel 10(m/s2 ) deceleration ability of vehicle sigma 0 driver imperfection (between 0 and 1) length 3(m) The vehicle’s length minGap 1 minimal gap between vehicles maxSpeed 80(m/s) vehicle’s maximum velocity The parameters about the vehicles are listed in table III. For routing request generation, we first randomly generate 200 source and destination pairs, and then assign random vehicle volumes to them. For background traffic, we use repeated vehicles in SUMO, which have the repeat period to be 2. C. Simulation Result and Analysis 100 200 300 400 500 600 0 20 40 Number of Routing Requests Average Flow Size Fig. 5: Average flow size distribution of MCMF-R algorithm In this section, we will evaluate the performance of centralized routing algorithm MCMF-R and distributed routing algorithm TS. Besides IRR algorithm, we also use the traditional GPS routing as the comparison algorithm, which keeps using shortest path algorithm in routing. Fig.5 shows the traffic grouping performance of MCMF-R, and the simulation result about time efficiency and fairness is shown in Fig.4. Fig.5 shows the average vehicle flow size managed by MCMF-R for different routing request volumes of one source and destination pair. Between volume 0 to 300, the average flow size is around 15 and between 300 to 550, it increases to 25. This indicates that MCMF-R algorithm can achieve around
MEMC-R MEMC-E MEVC-R al GPS Ro 00 0 Number of Rouing Re Number of Routing Reg Routing Request ID n (a)Average travel time without back-(b)Average travel time with back-(c)Standard deviation of travel time (d)Travel time for each request ID ground traffic ground traffic when the number of requests is 8x 104 Fig.4:Time efficiency and fairness comparison among MCMF-R,TS,improved random routing and traditional GPS routing 20x faster routing decision by considering a group of vehicles for the global optimization,causing loss of fairness. at one time VI.CONCLUSION The first two figures in Fig.4 show the time efficiency comparison result for these four algorithms.Fig.4a shows In this paper,we propose two efficient algorithms for route the average travel time for different routing request volumes guidance problem in vehicular network:MCMF-R for central- with no background traffic flows on roads.In Fig.4b,heavy ized routing and TS for distributed routing.Experiment results background traffic is added on some most commonly chosen indicate that,both algorithms have better time efficiency and fairness than traditional methods.Between MCMF-R and TS. roads when no background traffic exists,which simulates the heavy traffic cases discussed in Section IV-D1. TS is more deployable,and more suitable in low traffic volume routing than MCMF-R,and when the traffic is heavy,MCMF- The last two figures in Fig.4 show the fairness comparison R is better in time efficiency but worse in fairness.A hybrid result.Fig.4c shows the standard deviation of the travel time for different routing request volumes,and Fig.4d shows the framework is then proposed to provide better deployment and routing decisions under different traffic intensity situations. sorted travel time for each route request when the routing request volume is 8 x 104 ACKNOWLEDGMENTS In both Fig.4a and Fig.4b,the average travel time of MCMF- This work is supported in part by National Natural Science R and TS are at least 20%better than those of IRR and tradi- Foundation of China under Grant No.61100196,61073028 tional GPS routing,especially when the traffic volume exceed 61321491.91218302:JiangSu Natural Science Foundation 7 x 104.For traditional GPS routing,this improvement can under Grant No.BK2011559 achieve 40%on average.This improvement is even more in REFERENCES Fig.4c and Fig.4d,when the vehicle volume approaches 8x 10 to 10 x 10,the standard deviation and max-min difference [1]D.Schrank,T.Lomax and B.Eisele.(2011,Sep.)Urban mobility report.[Online].Available:http://mobility.tamu.edu/ums/report/ value of both MCMF-R and TS are about 50%of those of [2]J.Ott and D.Kutscher."Drive-thru internet:leee 802.11 b for,automo- IRR.This indicates that the time efficiency and fairness of both bile"Proc.IEEE INFOCOM.vol.1.2004. MCMF-R and TS algorithm are improved largely compared [3]V.Bychkovsky,B.Hull,A.Miu,H.Balakrishnan,and S.Madden A to traditional methods and the random routing of local taxi asurement stu using in situ wi-f networ drivers without any route guidance. Sumo.[Online].Available:http://sourceforge.net/apps/mediawiki/sumo/ IRR is better than traditional GPS routing,especially in [5]F.Li and Y.Wang."Routing in vehicular ad hoc networks:A survey, routing ability.And this advantage is increasing with the traffic [6 veh02-2之，2007 IEEE Vehicular Technology Magazine,vol 2.no.2. L.Xie,Q.Li. and et al volume.This shows that when the traffic is getting heavy,even ursuing efficiency and fairess IEEE Transac local taxi drivers outperform traditional route guidance. Disributed Systems (TPDS).vol.2 no.8.pp.323 3120 el and [7]T.Kitani,T.Shinkawa,and et al.,"Efficient vanet-based traffic informa- For the time efficiency between MCMF-R and TS,they tion sharing using buses on regular routes,"IEEE.Vehicular Technology are quite close,and no one can dominate the other in all ference(VTC). [8 12 and C.3036.2808 "Shortest path algorithms: evaluation using conditions.In Fig.4a.when the traffic volume is fewer than networks, 73 1998 3 x 10,MCMF-R is worse than TS.This is mainly because [9] Lin and S.Chou.Developing adaptive driv ng route guidance systems MCMF-R has more usage of the upper bound of travel time based on fuzzy neural network,"Proc.IET 4th International Conference (Section IV-B)than TS,and overestimates the congestion [10] on Inrelligent Ervironments.pp.1-8.2008. M.Khanafer.M.Guennoun and H.Mouftah,"Wsn architectures condition.When the traffic volume is more than 3 x 10 inteligent tran ta ion sy nation the lack of global information makes the performance of TS Technologies,Mobility and Security (NTMS)pp.1-8. ence on New 2009 degrading largely.When traffic volume is around 5 x 104 [11]M.Khanjary and S.Hashemi,"Route guidance systems:review and classification,"Proc.6th Euro American Conference on Telematics and MCMF-R has a clear advantage over TS,which is about 28% Information Systems,pp.269-275.2012. quicker.After that,TS catches up a little,but MCMF-R is still [12]R.Bauza and J.Gozalvez,"Traffic conge stion detection in la scale narios using vehicle-to ehicle comm stronger than it in time efficiency.In Fig.4b,TS is influenced tions," Computer Applications,2012 more by heavy background traffic than MCMF-R when traffic [13]J.Ding,C.Wang,F.Meng,and T.Wu,"Real-time vehicle route guid- volume is between 3 x 104 to 11 x 104.This indicates that ance using vehicle-to-vehicle communication,"IET:Communications. MCMF-R is more time efficient under heavy traffic conditions. 149R20n20 solutions for freewa travel time In fairness shown in Fig.4c,TS and MCMF-R are compara tion "IEEE Tror Systems. ol.9. ble to each other when the traffic volume is less than 4 x 104 n0.1,Pp.38-47,2008 [15]S.Dornbush and A.Joshi,"Streetsmart traffic:Discovering and dis- Between 4 x 104 and 6 x 104,TS is less fair than MCMF-R seminating automobile congestion using vanet's."Proc IEEE Vehicular since it lacks global information.But when the traffic volume fechnology Conference (VTC),pp.11-15,2007. exceeds 6 x 10,which is also shown in Fig.4d,TS surpasses [16 J.Edmonds and R.Karp. retical improvements in algorithmid efhciency for network MCMF-R and strictly dominates it.It is because in MCMF-R ol ocy o8_264 1972o the ACM (JACM) 972 when the traffic is getting heavy,more vehicles will sacrifice [17]openstreetmap.[Online].Available:http://www.openstreetmap.org/
0 2 4 6 8 10 12 x 104 0 1000 2000 3000 4000 5000 6000 7000 Number of Routing Requests Average Travel Time (s) MFMC−R TS IRR Traditional GPS Routing (a) Average travel time without background traffic 0 2 4 6 8 10 12 x 104 0 1000 2000 3000 4000 5000 6000 7000 Number of Routing Requests Average Travel Time (s) MFMC−R TS IRR Traditional GPS Routing (b) Average travel time with background traffic 0 2 4 6 8 10 12 x 104 0 500 1000 1500 2000 2500 3000 3500 Number of Routing Requests STDEV of Travel Time (s) MFMC−R TS IRR Traditional GPS Routing (c) Standard deviation of travel time 0 2 4 6 8 x 104 0 1000 2000 3000 4000 5000 6000 7000 8000 Routing Request ID Travel Time (s) MFMC−R TS IRR Traditional GPS Routing (d) Travel time for each request ID when the number of requests is 8×104 Fig. 4: Time efficiency and fairness comparison among MCMF-R, TS, improved random routing and traditional GPS routing 20× faster routing decision by considering a group of vehicles at one time. The first two figures in Fig.4 show the time efficiency comparison result for these four algorithms. Fig.4a shows the average travel time for different routing request volumes with no background traffic flows on roads. In Fig.4b, heavy background traffic is added on some most commonly chosen roads when no background traffic exists, which simulates the heavy traffic cases discussed in Section IV-D1. The last two figures in Fig.4 show the fairness comparison result. Fig.4c shows the standard deviation of the travel time for different routing request volumes, and Fig.4d shows the sorted travel time for each route request when the routing request volume is 8 × 104 . In both Fig.4a and Fig.4b, the average travel time of MCMFR and TS are at least 20% better than those of IRR and traditional GPS routing, especially when the traffic volume exceed 7 × 104 . For traditional GPS routing, this improvement can achieve 40% on average. This improvement is even more in Fig.4c and Fig.4d, when the vehicle volume approaches 8×104 to 10 × 104 , the standard deviation and max-min difference value of both MCMF-R and TS are about 50% of those of IRR. This indicates that the time efficiency and fairness of both MCMF-R and TS algorithm are improved largely compared to traditional methods and the random routing of local taxi drivers without any route guidance. IRR is better than traditional GPS routing, especially in routing ability. And this advantage is increasing with the traffic volume. This shows that when the traffic is getting heavy, even local taxi drivers outperform traditional route guidance. For the time efficiency between MCMF-R and TS, they are quite close, and no one can dominate the other in all conditions. In Fig.4a, when the traffic volume is fewer than 3 × 104 , MCMF-R is worse than TS. This is mainly because MCMF-R has more usage of the upper bound of travel time (Section IV-B) than TS, and overestimates the congestion condition. When the traffic volume is more than 3 × 104 , the lack of global information makes the performance of TS degrading largely. When traffic volume is around 5 × 104 , MCMF-R has a clear advantage over TS, which is about 28% quicker. After that, TS catches up a little, but MCMF-R is still stronger than it in time efficiency. In Fig.4b, TS is influenced more by heavy background traffic than MCMF-R when traffic volume is between 3 × 104 to 11 × 104 . This indicates that MCMF-R is more time efficient under heavy traffic conditions. In fairness shown in Fig.4c, TS and MCMF-R are comparable to each other when the traffic volume is less than 4×104 . Between 4 × 104 and 6 × 104 , TS is less fair than MCMF-R since it lacks global information. But when the traffic volume exceeds 6 × 104 , which is also shown in Fig.4d, TS surpasses MCMF-R and strictly dominates it. It is because in MCMF-R, when the traffic is getting heavy, more vehicles will sacrifice for the global optimization, causing loss of fairness. VI. CONCLUSION In this paper, we propose two efficient algorithms for route guidance problem in vehicular network: MCMF-R for centralized routing and TS for distributed routing. Experiment results indicate that, both algorithms have better time efficiency and fairness than traditional methods. Between MCMF-R and TS, TS is more deployable, and more suitable in low traffic volume routing than MCMF-R, and when the traffic is heavy, MCMFR is better in time efficiency but worse in fairness. A hybrid framework is then proposed to provide better deployment and routing decisions under different traffic intensity situations. ACKNOWLEDGMENTS This work is supported in part by National Natural Science Foundation of China under Grant No. 61100196, 61073028, 61321491, 91218302; JiangSu Natural Science Foundation under Grant No. BK2011559. REFERENCES [1] D. Schrank, T. Lomax, and B. Eisele. (2011, Sep.) Urban mobility report. [Online]. Available: http://mobility.tamu.edu/ums/report/ [2] J. Ott and D. Kutscher, “Drive-thru internet: Ieee 802.11 b for, automobile,” Proc. IEEE INFOCOM, vol. 1, 2004. [3] 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, pp. 50–61, 2006. [4] Sumo. [Online]. Available: http://sourceforge.net/apps/mediawiki/sumo/ [5] F. Li and Y. Wang, “Routing in vehicular ad hoc networks: A survey,” IEEE Vehicular Technology Magazine, vol. 2, no. 2, pp. 12–22, 2007. [6] L. Xie, Q. Li, and et al., “Association control for vehicular wifi access: Pursuing efficiency and fairness,” IEEE Transactions on Parallel and Distributed Systems (TPDS), vol. 22, no. 8, pp. 1323–1331, 2011. [7] T. Kitani, T. Shinkawa, and et al., “Efficient vanet-based traffic information sharing using buses on regular routes,” IEEE. Vehicular Technology Conference(VTC), pp. 3031–3036, 2008. [8] F. Zhan and C. Noon, “Shortest path algorithms: an evaluation using real road networks,” Transportation Science, pp. 65–73, 1998. [9] I. Lin and S. Chou, “Developing adaptive driving route guidance systems based on fuzzy neural network,” Proc. IET 4th International Conference on Intelligent Environments, pp. 1–8, 2008. [10] M. Khanafer, M. Guennoun, and H. Mouftah, “Wsn architectures for intelligent transportation systems,” 3rd International Conference on New Technologies, Mobility and Security (NTMS), pp. 1–8, 2009. [11] M. Khanjary and S. Hashemi, “Route guidance systems: review and classification,” Proc. 6th Euro American Conference on Telematics and Information Systems, pp. 269–275, 2012. [12] R. Bauza and J. Gozalvez, “Traffic congestion detection in large-scale scenarios using vehicle-to-vehicle communications,” Journal of Network and Computer Applications, 2012. [13] J. Ding, C. Wang, F. Meng, and T. Wu, “Real-time vehicle route guidance using vehicle-to-vehicle communication,” IET. Communications, vol. 4, no. 7, pp. 870–883, 2010. [14] J. Van Lint, “Online learning solutions for freeway travel time prediction,” IEEE Transactions on Intelligent Transportation Systems, vol. 9, no. 1, pp. 38–47, 2008. [15] S. Dornbush and A. Joshi, “Streetsmart traffic: Discovering and disseminating automobile congestion using vanet’s,” Proc IEEE Vehicular Technology Conference (VTC), pp. 11–15, 2007. [16] J. Edmonds and R. Karp, “Theoretical improvements in algorithmic efficiency for network flow problems,” Journal of the ACM (JACM), vol. 19, no. 2, pp. 248–264, 1972. [17] openstreetmap. [Online]. Available: http://www.openstreetmap.org/