ο€  Proceedings of Engineering and Technology Innovation, vol. 9, 2018, pp. 25 - 31 Message-Efficient Route Planning Based on Comprehensive Real-time Traffic Map in VANETs Chi-Fu Huang*, Yi-Hong Chen Department of Computer Science and Information Engineering, National Chung-Cheng University, Chia-Yi, Taiwan, ROC Received 02 March 2018; received in revised form 05 April 2018; accepted 06 May 2018 Abstract Traffic congestion has become one of the major society issues in many urban areas around the world. It greatly increases the commuting time and fuel consumption. Researchers have proposed many solutions in different aspects to alleviate this issue. In recent years, many works adopt Vehicular Ad Hoc Networks (VANETs) to relieve the problem. Vehicles with communication ability can receive traffic information from infrastructures or other vehicles. Furthermore, drivers can select its driving path by avoiding congestion areas based on the real-time information. However, to speed up the procedures of information collections, many existing works suggest proactive messages to acquire traffic information from other vehicles, which incurs heavy communication overheads. In this work, we propose a real-time traffic collection mechanism, which adopt both proactive and passive schemes. Vehicles passively collect traffic information in most of the time, and proactively broadcast the traffic data only in certain situations in order to speed up urgent information spreading. Thus, vehicles can obtain real-time traffic information in a low-cost way. In addition, we propose a routing planning scheme, which considers travel time, reliability, expected traffic flow as well as other factors, to select reliable and fast routes for vehicles. The simulation results show that, comparing with previous works, the proposed schemes can find better driving paths for vehicles with lower communication cost. Keywords: VANETs, route planning, traffic congestion 1. Introduction Nowadays, traffic congestions have become serious issues in many urban areas. With the increasing number of vehicles, especially in rush hours of big cities, traffic congestion greatly increases the commuting time, fuel consumption, and air pollution. Based on the estimate, the total cost of traffic congestion in the USA is roughly $160 billion annually, according to the urban mobility report [1] by the Texas Transportation Institute (TTI). Therefore, there are many efforts focused on how to alleviate or avoid traffic congestion. In modern cities, sensors, such as cameras and/ or induction loop detectors, are deployed on the roads and the intersections to collect traffic information. By counting the number of vehicles passing through, the vehicular density and traffic condition of a certain road segment can be aware. This information is helpful to distribute traffic flower in a city. However, due to the deployment cost, in most cases only the main roads of a city can install sensors. As a result, only parts of traffic conditions of a city can be aware. It may cause secondary congestions in other neighboring roads. Due to advances in wireless communication technologies, vehicles on the roads can assist each other in message exchange and form an interconnecting network, namely Vehicular Ad Hoc Networks (VANETs) [2]. In a VANET, each vehicle is able to * Corresponding author. E-mail address: cfhuang@cs.ccu.edu.tw Tel.: +886-5-2720411; Fax: +886-5-2720859 Proceedings of Engineering and Technology Innovation, vol. 9, 2018, pp. 25 - 31 Copyright Β© TAETI 26 communicate with nearby vehicles and share information through the network. With assistance of the appropriate applications, drivers can receive warning messages in front of an accident site and thus improve driving safety. Moreover, collection and sharing of real-time traffic information based on VANETs can also be useful to avoid traffic congestions. Many other applications based on VANETs can be found [3]. In recent years, there are many studies aimed to plan driving paths for vehicles to avoid congestion areas. The basic concept is to use the traffic information collected from road segments to calculate their estimated travel times. Then minimum cost algorithm is utilized to derive the fastest rout for each vehicle. Obviously, the immediacy of the traffic information affects the derived results of the planned paths a lot. In VANETs, fast speeds of vehicles result rapid change of the network topology. Outdated traffic information is useless for driving path planning since the road conditions may be greatly different. Therefore, how to obtain real-time traffic information more efficiently is critical for vehicular rout planning. Communications in VANETs can be classified into two categories [4-5]: Vehicle-to-Infrastructure (V2I), and Vehicle-to-Vehicle (V2V), as shown in Fig.1 and Fig. 2. V2I communication relies on fixed infrastructures, such as roadside units (RSUs), to communicate vehicles. RSUs connect to each other through a wired network and form a backbone network. Vehicles can send and receive road conditions through RSUs, and obtain wide range real-time traffic information. However, the drawback of V2I communication is that it needs huge deployment and maintenance cost. On the other hand, in V2V communication, vehicles form a self-organized network without any centralized system and fixed infrastructure. Vehicles communicate with each other directly and achieve long-distance communications through multi-hop relays. Due to the lower deployment cost, V2V communication has become a major trend of researching VANETs. Fig. 1 Vehicle-to-Infrastructure communications. Fig. 2 Vehicle-to-Vehicle (V2V) communications. The existing researches using inter-vehicle communications to exchange traffic information can be divided into two categories: proactive [6] and passive [7]. In the proactive schemes, whenever traffic information regarding to a certain road segment is outdated, a request message is initiated towards the target road segment. The vehicle who owns the fresher newest information of the target road will reply the request. Otherwise, the request will reach the road segment and ask a nearby vehicle to collect the last information. In the passive scheme, vehicles overhear periodical beacon messages from adjacent vehicle to estimate traffic condition of the road segment. Vehicles exchange their own records with other vehicles when passing through intersections. Information is then gradually distributed to the whole network. Although the proactive schemes can achieve faster information distribution than the passive schemes, they suffer from the need of additional request messages, resulting in a larger packet overhead. The amount of messages of the passive schemes is relatively small since information exchanges only take place at intersections. However, the information obtained by passive schemes may lack of timeliness and only cover a limited range. In this paper, in order to collect traffic information efficiently with low cost, a hybrid scheme is proposed. Moreover, we use the collected traffic information to avoid the congestion road and select routes with lower travel time for vehicle. The rest of this paper is organized as follows. In Section 2, we describe the proposed solution. Section 4 3 demonstrates the efficiency of the proposed schemes through simulation studies. Section 6 4 discusses future works and concludes this paper. Proceedings of Engineering and Technology Innovation, vol. 9, 2018, pp. 25 - 31 Copyright Β© TAETI 27 2. The Proposed Solution The schemes proposed in this paper can be divided into two parts: (1) traffic information collection and (2) vehicle route planning. 2.1. Traffic information collection In the traffic information collection, we adopt the V2V passive scheme, namely the Comprehensive Real-time Traffic Map (CRT Map) [7], to collect and establish a wide range of real-time traffic information map on each vehicle. CRT Map is established based on the concept of the Crowd Sensing [8]. Vehicles driving on the roads collect the real-time traffic flow and share with each other. Each vehicle keeps recording the traffic conditions of traveled roads into a designed digital map. Then, the digital map would be exchanged with other vehicles when traveling to intersections. Moreover, in this paper we improve the timeliness and the coverage range of traffic information. When encountering special situations, such as traffic jams or car accidents, vehicles proactively broadcast the road information to speed up the information distribution. Each vehicle in the V2V network equip with a OBU and periodically broadcast beacon messages, including the ID, to adjacent vehicles. Therefore, vehicles can observe how many and which vehicles on the same road and calculate the current traffic flow of this road. In order to get the accurate real-time traffic flow, a vehicle enters a road could ask the opposite lane of the vehicle about the traffic flow of the same direction. When the vehicle obtains new traffic information at the intersection, we can integrate the road information from different vehicles and update the traffic map in the vehicle. Since periodically broadcasting beacon messages is a fundamental operation in the general V2V environment, we use this feature to calculate the traffic flow and send no additional packet, thereby reducing the packet overheads in the process of collecting traffic information. When vehicle travels on the road, it could estimate the current traffic flow and integrate with the existing data by the following formula (1), (2). π‘Šπ‘–π‘— 𝑛 = { 1 1+βˆ†π‘‡π‘–π‘— 𝑛 , βˆ†π‘‡π‘–π‘— 𝑛 ≀ 𝑇𝑇𝐻 1 1+𝑇𝑇𝐻 , βˆ†π‘‡π‘–π‘— 𝑛 > 𝑇𝑇𝐻 (1) 𝑁′𝑖𝑗 = 𝑁𝑖𝑗 𝑛 = 𝑁𝑖𝑗 π‘˜ = (𝑁𝑖𝑗 𝑛 Γ—π‘Šπ‘–π‘— 𝑛 )+(𝑁𝑖𝑗 π‘˜ Γ—π‘Šπ‘–π‘— π‘˜ ) (π‘Šπ‘–π‘— 𝑛+π‘Šπ‘–π‘— π‘˜) (2) In order to spread out the traffic information, vehicles exchange their traffic map by inter-vehicle communication when they meet at the intersection. When vehicle Vi arrives at an intersection, it first observes if there is an exchange process taking place or not. If so, Vi joins this existing process and sends its traffic map to the leading vehicle. Otherwise, Vi initiates a new exchange process and broadcasts the request to collect neighbors’ traffic maps. Then, Vi sets a timer for receiving traffic map. After the neighbor vehicles receive the request, they transmit traffic map to Vi by the random back off mechanism to avoid the collisions. When the timer runs out of time, Vi uses the formula (1) and (2) to integrate traffic maps. Then Later Vi disseminates the integrated traffic map to all neighbor vehicles, as indicated in Fig. 3. If the neighbor vehicles have already been involved in the exchange process, they will update the traffic map after receiving the integrated map. On the other hand, if vehicles arrive at the intersection after the collection runs out of time, they can also receive the new traffic map. These vehicles integrate the new traffic map with the original map by themselves. The basic information exchange method described above allows the vehicle not only to collect traffic data by themselves, but also to exchange the information of other roads with the neighboring vehicles at the intersection. Proceedings of Engineering and Technology Innovation, vol. 9, 2018, pp. 25 - 31 Copyright Β© TAETI 28 Fig. 3 Information exchange process at an intersection In the above method, the exchange of information only performs at the intersections, thus it is less efficient to obtain traffic information in the following condition: (1) When the traffic jam occurs, the average speed on the road is reduced, so that the vehicle will spend more time traveling to the intersection. Thus, the information spreading speed of congestion roads is also reduced. (2) If some records in the map are not updated for a long time, it reduces the effectiveness of the path planning. In particular, in the roads with low vehicular density, the information diffusion rate is relatively slow. However, these roads should be more preferred because lower vehicular density means higher driving speed. Therefore, when the information of a road is outdated, we tend to speed up the access to its information. (3) As encountering a temporary condition, such as car accident and construction, it reduces the average speed of this road. Therefore, to speed up the transmission of traffic information, we let the vehicles on that road proactively send a warning message to inform vehicles on the other roads. 2.2. Vehicle route planning In the vehicle route planning, vehicles use the real-time information in the CRT Map to choose route. The basic factor is the travel time required for each road segment. In addition, we also consider the update time of the road information and regard this factor as the information reliability. Next, we consider the future conditions of roads. The factor of expected traveling paths of vehicles is considered in the calculation of the popularities of road segments. The higher popularity of a road segment means there are more vehicles passing through the segment. Thus, we tend to choose a lower popularity route. The collection and update of road popularities are integrated in the CRT Map operations. The information reliability of a road includes distance reliability and time reliability. The farther the road from the current position of a vehicle will be traveled in the longer future. The traffic condition on the road will continue changing. Hence the information of the road is relatively less valuable to the current path planning. It means that, we would like to reduce the influence of those farther roads in the path selection. On the other side, time reliability is the difference between the update time of the record in the map and the current time. The longer the information is not updated, the less reliability of the information is. The popularity represents the number of vehicles expected to travel on a road. When the popularity of a certain road is high, it means that there may be more vehicles than expected when actually arriving at the road. Thus, we tend to drive on the road with lower popularity. To calculate the popularity, we use a temporary popularity and a permanent popularity for each road segment. Temporary popularity resets to zero when entering to a new road segment. The temporary popularity and the permanent popularity are integrated after arriving at an intersection. Once a vehicle Vi travels on a road, it can obtain the traveling paths of encountered vehicles through the beacon messages. Vi increases the temporary popularity of corresponding road segments in the traveling paths by one. Then, when Vi travels to the intersection, it integrates the temporary popularity collected with the permanent popularity in the traffic map. When exchanging CRT Maps from different vehicles, popularity estimations by different vehicle can also be exchanged and integrated. Proceedings of Engineering and Technology Innovation, vol. 9, 2018, pp. 25 - 31 Copyright Β© TAETI 29 Vehicle will calculate the cost of each road according to the above factors using the following equation (3) and select the route with the lowest cost to the destination. We assume that the following is the set of roads in one of the paths to the destination roadπ‘’π‘˜ : {𝑒1, 𝑒2, … , π‘’π‘˜ |𝑒1 = 𝑒𝑛, 1 ≀ 𝑗 ≀ π‘˜} πΆπ‘œπ‘ π‘‘(𝑒𝑛) = βˆ‘ [(𝛼 Γ— π‘‡π‘Ÿπ‘— + 𝛽 Γ— 𝑃𝑗 ) Γ— π‘Šπ‘‡π‘— Γ— 𝑑𝑗 ] π‘˜ 𝑗=1 (1) π‘‡π‘Ÿπ‘— is the travel time of road 𝑒𝑗 . 𝑃𝑗 is the popularity of road 𝑒𝑗 , π‘Šπ‘‡π‘— is the time reliability of 𝑒𝑗 and π‘Šπ‘‡π‘— = 𝛾 βˆ— ln((π‘‡π‘π‘’π‘Ÿπ‘Ÿπ‘’π‘›π‘‘ βˆ’ 𝑇𝑗 ) + 𝑒). 𝑑𝑗 is the distance reliability of𝑒𝑗 , which use the distance between the current road and road 𝑒𝑗 to divide by the average road length οΏ½Μ…οΏ½. 𝛼, 𝛽, 𝛾 are the weights of travel time, popularity and time reliability, respectively. 3. Simulation Results In this section, we assess the performance between the proposed scheme, DEDR[9], and the shortest path. In DEDR, the road segment is divided into multiple clusters. The cluster head is responsible for collecting the information of vehicles in the same cluster and then transmitting to other clusters. With the proactive information exchange between the clusters, you are able to obtain traffic information. In order to determine whether have to change the path, the authors in [9] also proposed the trust probability to predict the traffic condition of selected path. Fig. 4 Road map of the simulation In our simulation, we use SUMO 0.30.0[10] and TraCI[11] to be our simulator. SUMO is an open source vehicle simulator that can simulate the movement of vehicles. TraCI is library, which can communicate with SUMO and control the behavior of vehicles in real-time. We use python as the implementation language of TraCI. Furthermore, we use OpenStreetMap[12] to capture the map of Kaohsiung as the road map used in our simulation, as shown in Fig. 4. The size of our map is 4.5 km * 4.5 km. The total length of simulation time is 3000 seconds, and the vehicle depart rate is 1 ~ 7 vehicles per second, resulting a total number of 3000 ~ 21000 vehicles. We simulate two scenarios according to different vehicle generation patterns: (1) Uniform mode, and (2) Non-Uniform mode. The uniform mode is to select 10 roads on each of the four boundaries of the map, in which we randomly select the source and destination from these 40 roads. In the non-uniform mode, in order to simulate the situation where vehicles are concentrated on certain roads, we randomly select the source and destination from 20 roads in two pairs of boundaries, where 10 roads are selected with the probability of 70%; the other 10 roads are 30%. We average the results over 100 times in each scenario. 3.1. Travel time of vehicles In the comparison of traveling time, we compare our method with DEDR and the vehicles traveling with shortest path. In Fig. 5, when the vehicle depart rate is low, the three methods have slight differences in travel time. As the vehicle departs rate Proceedings of Engineering and Technology Innovation, vol. 9, 2018, pp. 25 - 31 Copyright Β© TAETI 30 increases, the vehicle density also becomes high. The average travel time of the three methods rise. Moreover, the travel time of shortest path is much higher than other methods. It is because vehicles almost choose the same paths and will not change the path when traveling. Comparing to DEDR, the travel time of our method is much lower at different vehicle depart rates. Approximately 18% travel time is reduced in the case of 7 vehicles produced per second. Fig. 6 compares the travel time in the non-uniform mode. While comparing to the uniform mode, vehicles may be concentrated on some roads in the non-uniform mode, which increasing the chances of road congestion. Therefore, the travel time of both three methods will rise slightly. However, the travel time of our method is still lower than DEDR, especially in the case of high vehicular density. Fig. 5 Travel time vs. Vehicle depart rate in uniform mode Fig. 6 Travel time vs. Vehicle depart rate in non-uniform mode 3.2. Packet overhead In Fig. 7 and Fig. 8, we compare the average packet overhead of different vehicle depart rates in two vehicle generation scenarios. As shown in the figures, DEDR is a proactive method and proactively send traffic information to other vehicles. Therefore, in both scenarios, the packet overhead of our method is less than DEDR. Our method can reduce up to about 70% of the packet overhead in the uniform mode, and 48% in non-uniform mode. In addition, because the probability of traffic congestions in non-uniform mode is higher than uniform mode, the packet overhead of our method in non-uniform mode is higher than uniform mode. Besides, the information of roads with few vehicles driving on is hard to be updated due to the unbalanced vehicle distribution. Our method will send additional packets for congested roads or outdated information roads, thus the packet overhead is higher in non-uniform mode. However, comparing to DEDR, the packet overhead of our method is still lower. Fig. 7 Packet overhead vs. Vehicle depart rate in uniform mode Fig. 8 Packet overhead vs. Vehicle depart rate in non-uniform mode 4. Conclusions In this paper, we utilize the passive traffic collection schemes through the inter-vehicle communication. In order to solve the problem of slow updating and the limited coverage range of coverage, we integrate proactive schemes to speed up information spreading for congestion roads, outdated roads, and temporary condition roads. We combine the proactive and Proceedings of Engineering and Technology Innovation, vol. 9, 2018, pp. 25 - 31 Copyright Β© TAETI 31 passive schemes, which allow vehicles collect extensive and real-time information with low packet overhead. Moreover, we also propose a vehicle rout planning scheme that utilizes the traffic information collected by each vehicle and takes into account the expected route of other vehicles. The simulation results shows that vehicles using the proposed methods can reach their destinations with short travel time and obtain traffic information with low packet overhead. In the future, we will tend to combine the schedule of traffic lights to enable vehicles to select a faster and smoother route. Acknowledgements The study is sponsored by MOST under Grant No. 106-2221-E-194-002. References [1] D. Schrank, B. Eisele, T. Lomax, and J. Bak β€œ2015 urban mobility report,” The Texas A&M Transportation Institute and INRIX, August 2015. [2] S. Al-Sultan, M. M. Al-Doori, A. H. Al-Bayatti, and H. Zedan, β€œA comprehensive survey on vehicular ad hoc network,” Journal of Network and Computer Applications, vol. 37, pp. 380-392, January 2014. [3] C. Englund, L. Chen, A. Vinel, and S. Y. Lin, β€œFuture applications of vanets,” In Vehicular ad hoc Networks Springer International Publishing, pp. 525-544, 2015. [4] M. J. Booysen, S. Zeadally, and G. J. Van Rooyen, β€œSurvey of media access control protocols for vehicular ad hoc networks,” IET Communications, vol. 5, no. 11, pp. 1619-1631, 2011. [5] E. Uhlemann, β€œIntroducing connected vehicles,” IEEE Vehicular Technology Magazine, vol. 10, no. 1, pp. 23-31, March 2015. [6] M. Chaqfeh and A. Lakas, β€œShortest-time route finding application using vehicular communication,” Proc. IEEE Wireless Communications and Networking Conference (WCNC), November 2014. [7] C. F. Huang, Y. F. Chan, and R. H. Hwang, β€œA comprehensive real-time traffic map for geographic routing in vanets,” Applied Sciences, vol. 7, no. 2, January 2017. [8] R. K. Ganti, F. Ye, and H. Lei, β€œMobile crowdsensing: current state and future challenges,” IEEE Communications Magazine, vol. 49, no. 11, November 2011. [9] J. Lin, W. Yu, X. Yang, Q. Yang, X. Fu, and W. Zhao, β€œA real-time en-route route guidance decision scheme for transportation-based cyberphysical systems,” IEEE Transactions on Vehicular Technology, vol. 66, no. 3, March 2017. [10] D. Krajzewicz, J. Erdmann, M. Behrisch, and L. Bieker, β€œRecent development and applications of SUMO - simulation of urban mobility,” International Journal on Advances in Systems and Measurements, vol. 5, no. 3-4, December 2012. [11] A. Wegener, M. Piorkowski, M. Raya, H. HellbrΓΌck, S. Fischer, and J. P. Hubaux, β€œTraCI: a framework for coupling road traffic and network simulators,” Proc. of the 11th Communications and Networking Simulation Symposium, IEEE Press, April 2008. [12] M. Haklay and P. Webber, β€œOpenStreetMap: user-generated street maps,” IEEE Pervasive Computing, vol. 7, no. 4, October 2008. https://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6923023 https://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6923023