Improving Vehicle Traffic using An Alerting and Rerouting System

Improving Vehicle Traffic using An Alerting and Rerouting System

Eng. Khaled Mohmad Zein Aldien Alhasbani Department of Automation & Computer Engineering

Damascus University

Dr. Eng. Wasim Mousa Alsamara Department of Automation & Computer Engineering

Damascus University

AbstractVehicular Ad-hoc Network (VANET) is an emerging new technology to enable communications among vehicles and nearby roadside infrastructures to provide intelligent transportation applications. In order to provide stable connections between vehicles, a reliable routing protocol is needed. Currently, there are several routing protocols designed for MANETs could be applied to VANETs. However, due to the unique characteristics of VANETs, the results are not encouraging. In this paper, we propose a new routing protocol named AODV-TWR, which incorporates the vehicles movement information into the route discovery process based on Ad hoc On-Demand Distance Vector (AODV). A Total Weight of the Route is introduced to choose the best route together with an expiration time estimation to minimize the link breakages. With these modifications, the proposed protocol is able to achieve better routing performances.

Keywords-VANET; routing protocol; AODV

1. INTRODUCTION

   A Vehicular Ad-hoc Network (VANET) is a form of wireless ad hoc network to provide communications among vehicles and nearby roadside equipment. The major purpose of VANET is to provide (1) ubiquitous connectivity while on the road to mobile users, and (2) efficient vehicle-to- vehicle communications that enable the Intelligent Transportation Systems (ITS). A variety of applications for safety, traffic efficiency, driver assistance and infotainment will be enabled with the emerging vehicular networks.

   Unlike other communication networks, VANET has its unique characteristics. The mobility of vehicles is constrained by predefined roads and buildings. Vehicle speed range could be from 0 to speed limit. Such speed limit, for example in the high way, could be 90km/h. Thus, VANET differs in size, speed of the vehicles, relevance of their geographic position and sporadic connectivity between them with unreliable channel conditions. These characteristics pose many challenging research issues, including routing, data dissemination, data sharing, and security issues. Existing routing protocols, traditionally designed for mobile ad hoc networks (MANETs), do not utilize the unique characteristics of VANETs and are not suitable for vehicle-to-vehicle communications over VANETs.

   In this paper, we propose a new routing protocol by utilizing the vehicles movement information (e.g., position, speed, acceleration and direction) based on Ad hoc On- Demand Distance Vector (AODV) [1] and our previous work [2, 3]. We extend our previous work by introducing weight factors to calculate a Total Weight of the Route (TWR) to determine the

   best routing path compared to [2]. Besides, an estimation of the expiration time of the chosen route is included to minimize the link breakage, and changing the direction weight factor according to different direction ranges is also presented for the TWR calculation compared to [3]. The remainder of this paper is organized as follows. Section II presents some works in literature related to this area. In Section III, the specifics of the proposed routing protocol are given. Simulation and performance results are presented in Section IV, and the paper is concluded in Section V.

2. RELATED WORK

   In this section, we survey some important routing protocols, which are attempted to apply into VANET networks.

   Routing protocols for the execution of routing in MANET networks can be classified as either proactive, reactive, or hybrid. Proactive routing protocols are table- driven routing protocols and their route updates are periodically performed regardless of network load, bandwidth constraints, and network size. Routing information is stored in a variety of tables and is based on received control traffic. Generation of control messages and route calculation are driven by the routing tables. Thus, proactive protocols have two main characteristics: immediate retrieval of routes overcomes the issue of the initial route establishment delay in case of reactive protocols; and periodic updates of routing tables result in substantial signaling overhead. Some of the protocols that have achieved prominence in the proactive category include Optimized Link State Routing (OLSR) [4], Hazy Sighted Link State Routing (HSLS) [5], Topology Broadcast based on Reverse Path Forwarding (TBRPF) [6], and Destination-Sequenced Distance Vector (DSDV) [7].

   On the contrary, in reactive routing protocols, also known as on-demand routing protocols, routing paths are searched only when a source needs to find a destination which is not listed in its routing table. Compared to proactive protocols, the smaller overhead is incurred on control messages for reactive

   protocols. The reason is that in a wireless mobile environment where mobile nodes move in and out of radio communication range, the frequent updates in proactive protocols will incur a larger overhead of routing control messages. Several protocols fall in this category. Notable examples are Ad hoc On-Demand Distance Vector (AODV) and Dynamic Source Routing (DSR) [8].

   Hybrid routing protocols have both proactive and reactive characteristics, which are designed to improve the scalability of proactive protocols while maintaining lower routing control messages. An example of this category protocols is Zone Routing Protocol (ZRP) [9]. ZRP divides the network into different zones where each zone may have different size. Routing within zones, intra-zone routing, is performed by a proactive protocol. On the other hand, to increase system scalability, routing between zones, inter- zone routing, is done by a reactive protocol. However, the disadvantage is that it introduces too much latency when finding new routes, and their implementation has not gained that much popularity.

   Proactive protocols are easier to implement and exhibit relative stability than reactive protocols. However, a storm of control messages is required to maintain an accurate view of the network topology when they are applied to a highly mobile VANET environment. This intuitively results in heavy traffic contention, collisions of packets due to mass flooding broadcasts between neighboring nodes, and, consequently, a significant waste of the scarce wireless bandwidth.

   Reactive protocols are hence preferred for dynamically changing VANET environments [10] as they offer a smaller routing overhead and less memory intensive since they do not keep track of the states of all the nodes in the network. The performances of reactive routing protocols in various traffic conditions in VANETs have been simulated and studied by various groups of people [11-15]. Those simulation results show that most reactive routing protocols (e.g., AODV and DSR) suffer from poor route convergence and low communication throughput. For example, in [14], AODV is evaluated with six sedan vehicles. Its results show that AODV is unable to quickly find, maintain, and update long routes in the VANET environment. In addition, in their real-world experiment, it is almost impossible for a TCP connection to finish its three-way handshake to establish a connection due to route failures and excessive packets loss under AODV. Thus, this paper presents our modification to the existing AODV reactive routing protocol with the aim to improve its reliability and performances.

   discovery process. These characteristicsinclude position, speed, acceleration, direction of the vehicle and the link quality between the communicating vehicles. We will name it AODV- TWR. AODV is chosen above all of the other reactive MANET routing protocols due to its ability to quickly react to network changes. On top of that, it has an efficient route discovery method that allows intermediate nodes, which have a valid route to the destination node, to reply to requests messages. In particular, the changes are made to the AODV- UU [16] version of the MANET routing protocol.

   1. Total Weight of the Route

      One way to determine whether an intermediate vehicle should be chosen to route data packets is by examining whether it is within the radio range long enough so as to send all the needed data packets. Therefore, the aforementioned VANET characteristics are required to be considered before the source node to decide the best route to its intended destination. We define the Total Weight of the Route (TWR) between the source and destination nodes so as to include these characteristics with mathematical representation. Next, we will show how these VANET characteristics affect TWR.

      1. Vehicle Speed and Acceleration

         The larger the speed and acceleration differences between two vehicles should account for a larger TWR between the two vehicles. The rationale is to anticipate the breakage of the link because of the speed difference of the vehicles. Vehicles that are moving in a relatively same velocity and acceleration will stay in radio communication range much longer. Hence, such conditions are more desirable and should be assigned a lower TWR.

      2. Vehicle Movement Direction

         Logically, vehicles moving in a similar direction will stay in radio communication range much longer. Therefore, a direction vector is also crucial in calculating the TWR to the target. In fact, direction parameter is a very important factor in determining the route choice, and we will elaborate it later.

      3. Link Quality Between Vehicles

         Another parameter needs to be considered in the TWR is the link quality between nodes in the route to the destination. In VANETs, neighboring vehicles, buildings and obstructions may affect the link quality between vehicles. Therefore, the link quality factor should be included in the TWR calculation

         In conclusion, the TWR from the source node to the destination node could be expressed in the following mathematical equation:

         =

         =

         = { × | | + × | | +

3. AODV-TWR

   The main idea of the proposed routing protocol is to incorporate the VANET features into AODV for the route

   where,

   × |

   | +

   × ( )} (1)

   N: Number of nodes in the route. S: Speed of the vehicle.

   fs: Speed weight factor.

   A: Acceleration of the vehicle. fa: Acceleration weight factor.

   D: Direction vector of the vehicle. fd: Direction weight factor.

   fq: Link quality weight factor.

   LQ: Link quality between the two adjacent vehicles.

   From (1), we can see that the TWR of a path is determined by the differences of speed, acceleration, direction and link quality of every intermediate vehicle in the route towards the destination. The best route, which with the least TWR, consists of vehicles choosing next-hop nodes that have almost the same speed and acceleration, identical direction and sound link quality.

   1. Direction Constraint

      As mentioned before, direction of the vehicle plays an important role in choosing the best route. To explain this, we will consider the following example. Four vehicles, namely Vehicles A, B, C and D, are moving around at a crossing. Vehicle D is turning right onto a new road, while the other three vehicles will remain straight on the same road. Vehicle A tends to establish a connection with Vehicle C with two possible choices: one via Vehicle B (route A-B-

      C) and the other one via Vehicle D (route A-D-C). As Vehicle D is turning right and Vehicle A is staying straight, the latter route is more likely to break after a certain time. Clearly, the selection of the former route is a more stable choice.

      Although in (1) we already present a bigger contribution

      Figure 1. Direction Ranges

   2. Expiration Time

      For now, after the route discovery process, we are able to choose the best route from the source to the destination nodes. However, along the connection path, a link breakage still occurs if an intermediate routing vehicle leaves the radio communication range. To avoid link ruptures and to establish reliable routes, we could estimate the expiration time T of the chosen route and initiate a new route discovery process before the link breaks. The new route discovery happens at a time t before the estimated expiration time. From [17], if we consider two vehicles i and j with a transmission or line-of-sight range of R, speeds vi and vj, coordinates (xi, yi) and (xj, yj), and velocity angles i and j, respectively (Figure 2), then the predicted expiration time is

      of different directions to the TWR calculation, we can further prevent this by changing the direction weight factor according to different direction ranges. Refer to Figure 1 for the direction ranges.

      There are four direction ranges based on the target vehicle that is choosing its next-hop. The vehicle is moving in direction S . Thus, the nodes moving in the direction

      where,

      = (+)+(2+2)2()2

      a2+2

      a= vi cosi vj cosj b = xi xj c = vi sini vj sinj

      d = yi yj

      (2)

      1

      ranges of S2 and S4 will not be chosen as the next-hop. This is done by assigning a much bigger value to the direction weight factor so that these paths will be eliminated directly. As for the vehicles moving in direction range S3, which means they are roughly on the opposite direction to the target vehicle, we will introduce a penalty scheme. The reason we will not remove these nodes from the choices is that this scenario may be beneficial to a longer establishment of the route. Imagine that two vehicles of opposite directions arriving at an intersection with a stop sign. Then these two vehicles are able to establish a communication as long as the stop sign is on. The penalty scheme ensures that the target vehicle will not treat this one as the same as the vehicles that move in the same direction of the target vehicle. In this case, the direction weight factor will be doubled so as to increase the TWR. As for those vehicles move in direction range S1, the original direction weight factor is applied.

   3. Route Packets

      1. Route Request (RREQ)

         The route request algorithm of the AODV-TWR is similar to AODV. Initially, when the RREQ message is created, the requesting node attaches its movement details (position, speed, acceleration and direction) into the RREQ message. The TWR and expiration time are initialized to zero and a large number respectively. It then floods its neighbors with this RREQ message. When a node receives an RREQ message, it extracts the senders movement details from the received RREQ packet and uses this information with its own movement details for TWR and expiration time calculation. If the expiration time is smaller, then the expiration time is updated. It also searches the stored memory for the link quality between the two nodes for TWR calculation. Thereafter, it attaches the new TWR and expiration time to the RREQ message, along with its own movement details into the request message. If the said node does not have a route to the destination, it floods its own neighbors with this new RREQ message and this

         process continues until a node finds a route to the destination or no such destination can be found.

      2. Route Reply (RREP)

         A RREP routing message is generated when a node responds to an RREQ message when the intermediate node has a route to the destination or the RREQ received is for the destiation itself. Concerning the former case, in creating the RREP message, the modified algorithm attaches the TWR and expiration time in the RREQ message into the RREP message. Then the node searches the routing table to look for the TWR and expiration time to the destination and updates this information into the RREP message created. Finally, it sends the RREP message to the source and the destination. Therefore, the source and the destination nodes will eventually obtain the TWR and the expiration time of the routes. In the latter case that a node receives an RREQ message meant for itself, it will find that the TWR is the final route weight from source to destination. Hence, it creates an RREP with the TWR and expiration time and sends it back to the source.

      3. Extract Movement Details

   In order to calculate the TWR and expiration time in the AODV-TWR protocol, the node has to be able to retrieve movement details from the simulator. In a real-life implementation of the AODV-TWR protocol, these data can be obtained from the vehicle via the Controller Area Network BUS (CAN-BUS), vehicles operating systems or even the GPS for direction values. However, with the constraint of this research, these data are collected from OMNET 5.5.1.

4. SIMULATION AND RESULTS

   1. Mobility Model

      Before continue to the simulation results, we shed some lights on the mobility model first. One key component of the mobility models is to keep real-world constraints of a VANET as realistic as possible, which include street conditions, urban conditions, traffic speed, vehicle density, obstacles such as buildings, traffic junction reality, logical vehicular flows, and so on.

      Saha and Johnson [18] first attempted to propose a realistic street mobility model where they used the road information from the Topologically Integrated Geographic Encoding and Referencing (TIGER) [19] US road map by US Census Bureau. In this paper, we follow the work of [3, 20] to generate the mobility model using Traffic and Network Simulation Environment (TraNS). TraNS [21] is a tool that integrates traffic and network simulators to generate realistic simulations of VANETs and it offers fair junction logic and provides actual vehicular flow. TraNS is able to accept the road layout maps from Simulation of Urban MObility (SUMO) [22], which uses the TIGER map database as the input. With these maps, TraNS then creates the mobility model and generates the trace files that can be fed into Network Simulator (OMNET++5.5.1) [23] for simulation.

      Figure 2. Parameters used in calculating the expiration time

   2. Simulation Results and Analysis

      We evaluate the performance of the proposal routing protocol against that of the original AODV routing protocol. Five pairs of vehicles are chosen to establish TCP connections. The TCP packet size varies form 512 bytes to 1280 bytes with a step of 256 bytes. Refer to Table I for the simulation parameters and values.

      Figure 3 and Figure 4 show the routing advertisements and loads of both protocols. Routing advertisement is defined as the total number of routing messages (AODV- related messages) sent and received during the simulation. From Figure 3, we can see that AODV-TWR has a lower number of routing advertisements in every scenario in comparison with AODV. From the number of routing advertisements, the routing loads of these two routing protocols could be addressed. Figure 4 shows us that the routing load of AODV-TWR is lower than that of AODV, which means a better performance.

      The number of bytes received and dropped is presented in Figure 5 and Figure 6 respectively. In Figure 5, it gives the total data bytes received in all of the 10 communicating vehicles. It can be seen that the total bytes received by AODV- TWR protocol is much higher than that of AODV, which suggests a more reliable connection. Figure 6 presents the percent of bytes dropped out of the total bytes transmitted. Clearly, AODV-TWR has a smaller bytes drop probability compared to AODV. This again proves that AODV-TWR is able to establish a more stable link.

      Finally, we will examine the number of packets received and dropped during the communication. The results are displayed in Figure 7 and Figure 8. Similar to the bytes case, AODV-TWR shows that it is able to send more TCP packets compared to AODV, with a lower packets drop rate.

      From the simulation results above, it is apparent that AODV-TWR protocol manages to achieve a better routing performance than the AODV protocol. However, we should realize that a TCP connection may not be the best transport layer protocol for the simulation of ad hoc network protocols due to the high bit error characteristics of an ad hoc network like VANET. Hence, further simulations using better mobility model and transport layer protocols could be done to manage these limitations of the current simulation.

      No. of Bytes Received

      8000000 7838570

      7500000 7264988

      7551608

      No. of Bytes Received

      8000000 7838570

      7500000 7264988

      7551608

      TABLE I. SIMULATION PARAMETERS AND VALUES

      Values Parameters

      Values Parameters

      600s

      AODV, AODV- TWR

      250m

      2 Mb(per second)

      300

      100km(per hour)

      Simulation Time

      7000000

      7000000

      6732735

      6732735

      7039719

      7039719

      No. of Bytes Received

      No. of Bytes Received

      Routing Protocol

      6500000

      6500000

      6600725

      6600725

      5918812

      5918812

      6000000

      6000000

      Transmission range

      5500000

      5500000

      5691163

      5691163

      5000000

      5000000

      512

      512

      768

      768

      1024

      1024

      1280

      1280

      Packet Size(Bytes)

      AODV-TWR AODV

      Packet Size(Bytes)

      AODV-TWR AODV

      Bandwidth Number of Nodes Max. Node speed

      Figure 5. Number of Bytes Received on TCP

      No. of Routing advertisments

      No. of Routing advertisments

      Percentage of Bytes Dropped

      1100

      1100

      980

      980

      0.7

      0.62

      1000

      1000

      905

      905

      925

      925

      No. of Routing advertisments

      No. of Routing advertisments

      Percentage of Byte Dropped (%)

      Percentage of Byte Dropped (%)

      0.6

      900

      900

      806

      806

      962

      962

      905

      800

      840

      905

      800

      840

      0.5

      0.57

      0.57

      0.44

      700

      700

      744

      744

      0.4

      600

      500

      400

      600

      500

      400

      0.3

      0.2

      0.35

      0.3

      0.41

      0.5

      512

      512

      768

      768

      1024

      1024

      1280

      1280

      512 768 1024 1280

      Packet size (Byte)

      Packet size (Byte)

      AODV-TWR

      AODV

      AODV-TWR

      AODV

      14

      11.7

      12 13.5

      12.5

      14

      11.7

      12 13.5

      12.5

      10

      10

      Routing Load (%)

      Routing Load (%)

      Figure 3. Number of Routing Advertisements

      Routing Load

      Routing Load

      18

      16.1

      18

      16.1

      16

      14.4

      16

      14.4

      4

      4

      512

      768

      1024

      1280

      512

      768

      1024

      1280

      Packet size (Bytes)

      Packet size (Bytes)

      AODV-TWR

      AODV

      AODV-TWR

      AODV

      8.2

      8.2

      10.2

      10.2

      8

      6

      8

      6

      7.1

      7.1

      Figure 4. Routing Load

      Packet Size(Bytes)

      AODV-TWR AODV

      No. of TCP packet sent

      12000

      10715

      11000

      10000

      10079

      9000 8370

      8000

      No. of TCP packet sent

      12000

      10715

      11000

      10000

      10079

      9000 8370

      8000

      8160

      8160

      7001

      7001

      No. of TCP packet sent

      No. of TCP packet sent

      Figure 6. Percentage of Bytes Dropped on TCP

      7000

      5931

      6000 6762

      5000 5712

      4000

      512 768 1024 1280

      Packet size(Byte)

      AODV AODV-TWR

      7000

      5931

      6000 6762

      5000 5712

      4000

      512 768 1024 1280

      Packet size(Byte)

      AODV AODV-TWR

      Figure 7. Number of Packets sent on TCP

      Percentage of Packet Drropped

      Percentage of Packet Drooped (%)

      Percentage of Packet Drooped (%)

      1

      0.91

      Communications Review (MC2R), vol. 7, no. 1, pp. 4749,

      January 2003.

      1. Namboodiri, M. Agorwal, and L. Gao, A study on the feasibility of mobile gateways for vehicular ad-hoc networks, The First International Workshop on Vehicular Ad Hoc Networks, pp. 66-

         0.9

         0.8

         0.86

         0.85

         75, 2004.

      2. G. Liu, B.-S. Lee, B.-C. Seet, C.H. Foh, K.J. Wong, and K.-K. Lee, A routing strategy for metropolis vehicular communications, International Conference on Information Networking (ICOIN), pp. 134 143, 2004.

         0.7

         0.6

         0.5

         0.52

         0.63

         0.58

         0.73

      3. S.Y. Wang, C.C. Lin, Y.W. Hwang, K.C. Tao, and C.L. Chou, A practical routing protocol for vehicle-formed mobile ad hoc networks on the roads, The 8th IEEE International Conference on Intelligent Transportation Systems, 2005, pp. 161165.

      4. R. A. Santos, A. Edwards, R. Edwards, and L. Seed, Performance evaluation of routing protocols in vehicular adhoc networks, International Journal of Ad Hoc and Ubiquitous Computing, vol.

         0.4 0.45

         512 768 1024 1280

         Packet size(Byte)

         AODV-TWR AODV

         Figure 8. Percentage of Packets Dropped on TCP

5. CONCLUSIONS

This paper proposes the new routing protocol AODV- TWR by incorporating the vehicles movement information into the route discovery process based on AODV for VANET application. With the introduction of the TWR and expiration time estimation, the proposed protocol is able to achieve better routing performances. Simulation results show the protocols effectiveness in reducing routing load and sustaining more stable connections compared to AODV.

REFERENCES

1. Perkins and E. Belding-Royer, and S. Das, Ad hoc On-Demand Distance-Vector (AODV) Routing, Network Working Group, RFC 3561, July 2003.

2. H.Q. Guo, F. Tao, M.D. Ma, and Y.D. Wu, A Reliable Route Selecting Algorithm for Vehicle Communication, The Seventh International Conference on Information, Communications and Signal Processing (ICICS 2009), Macau, China, December 2009.

3. H.Q. Guo, M. Firdaus B. A. Thani, W.C. Wong and Y.D. Wu. An Optimized Routing Protocol for Vehicular Ad Hoc Networks. TENCON 2010, Fukuoka, Japan, November 2010.

4. T. Clausen, and P. Jacquet, Optimized Link State Routing Protocol (OLSR), Network Working Group, RFC 3626, October 2003.

5. Santivanez, R. Ramanathan, and I. Stavrakakis, Making link-state routing scale for ad hoc networks, ACM MobiHoc 2001, Long Beach, USA, October 2001.

6. R. Ogier, F. Templin, and M. Lewis, Topology Dissemination Based on Reverse-Path Forwarding (TBRPF), Network Working Group, RFC 3684, February 2004.

7. Perkins, Highly Dynamic Destination-Sequenced Distance- Vector Routing (DSDV) for Mobile Computers, ACM SIGCOMM 1994, London, UK, August 1994, pp.234-244.

8. D.B. Johnson, D.A. Maltz, and Y.C. Hu, The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR), IETF MANET Working Group, Internet Draft, July 2004.

9. T. Thongpook, and T. Thumthawatworn, Adaptive Zone Routing Technique for Wireless Ad hoc Networks, ITC-CCSC 2002, Phuket, Thailand, July 2002.

10. Schumacher, S. Painilainen, and T. Luh, Research Study of MANET Routing Protocols, Research Seminar on Hot Topics in Internet Protocols, Helsinki, Finland, Spring 2004.

11. H. Fubler, M. Mauve, H. Hartenstein, M. Kasemann, and D.Vollmer, Location-based routing for vehicular ad-hoc networks, ACM SIGMOBILE Mobile Computing and

1, no. 1/2, pp. 8091, 2005.

1. C. Perkins, E. Belding-Royer and S. Das, http://aodvuu.sourceforge.net/, AODV-UU, RFC3561.

2. W. Su, S.J. Lee, and M. Gerla, Mobility predictionand routing in ad hoc wireless networks, Int. J. of Network Mgmt, 2001.

3. A.K. Saha, and D.B. Johnson, Modeling mobility for vehicular ad-hoc networks, in ACM International Workshop on Vehicular Ad Hoc Networks, pp. 9192, 2004.

4. U.S. Census Bureau, TIGER, TIGER/Line and TIGER-Related Products, http://www.census.gov/geo/www/tiger/.

5. M. Pi´orkowski, M. Raya, A. L. Lugo, P. Papadimitratos, M. Grossglauser, and J-P. Hubaux, TraNS: Realistic Joint Traffic and Network Simulator for VANETs, in ACM SIGMOBILE Mobile Computing and Communications Review, Vol. 12, No. 1, January 2008.

6. TraNS Realistic simulator for VANET. Retrieved January 16, 2010, from http://trans.epfl.ch/.

7. D. Krajzewicz, G. Hertkorn, C. Rossel, and P. Wagner, SUMO: An open-source traffic simulation, In 4th Middle East Symposium on Simulation and Modeling (MESM2002), pp. 183- 187, Sharjah, United Arab Emirates, September 2002.

8. The NS-2, http://nsnam.isi.edu/nsnam/index.php/Main_Page.