A Review of Vehicle to Vehicle Communication Protocols for VANETs in the Urban Environment

Abstract

Vehicular Ad-hoc Networks (VANETs) have been gaining significant attention from the research community due to their increasing importance for building an intelligent transportation system. The characteristics of VANETs, such as high mobility, network partitioning, intermittent connectivity and obstacles in city environments, make routing a challenging task. Due to these characteristics of VANETs, the performance of a routing protocol is degraded. The position-based routing is considered to be the most significant approach in VANETs. In this paper, we present a brief review of most significant position based unicast routing protocols designed for vehicle to vehicle communications in the urban environment. We provide them with their working features for exchanging information between vehicular nodes. We describe their pros and cons. This study also provides a comparison of the vehicle to vehicle communication based routing protocols. The comparative study is based on some significant factors such as mobility, traffic density, forwarding techniques and method of junction selection mechanism, and strategy used to handle a local optimum situation. It also provides the simulation based study of existing dynamic junction selection routing protocols and a static junction selection routing protocol. It provides a profound insight into the routing techniques suggested in this area and the most valuable solutions to advance VANETs. More importantly, it can be used as a source of references to other researchers in finding literature that is relevant to routing in VANETs.

Authors’ Biographies: Irshad Ahmed Abbasi is currently working as a researcher at the Department of Computer Science and Information Technology, University of Malaysia Sarawak, Malaysia. He served as a senior lecturer from 2011 to 2016 at King Khalid University, Kingdom of Saudi Arabia. He is also a senior lecturer at the Department of Computer Science, University of Bisha, Kingdom of Saudi Arabia. His research interests include routing in VANETs and MANETs, Mobile Computing, and Cloud Computing. He is an author of many articles including Traffic Flow Oriented Routing Protocol for VANETs published in Springer EURASIP Journal on wireless communication and networking. He is also acting as a reviewer of many well reputed journals.

Adnan Shahid Khan is currently a senior lecturer at Faculty of Computer Science and Information Technology, Universiti Malaysia Sarawak. He has completed his Postdoctoral, Ph.D. and Masters in Networks in 2013, 2012, 2008 respectively from Universiti Technology Malaysia, Johor Bahru, Malaysia and BSc (Hons) Computer Sciences in 2005 from University of Punjab, Lahore Pakistan. His research interest includes Network and Network Security in Wireless communication. He has published more than 70 papers in peer reviewed conferences and journals. He is also acting as a reviewer of many journals.

1. Introduction

The vehicular ad-hoc network (VANET) is also called network on wheels, which is used to provide communication between vehicular nodes. It is an offshoot of mobile ad-hoc networks. In VANETs, vehicular nodes are self-organized and communicate with each other in an infrastructureless environment [1,2,3,4,5,6,7]. Knowing the importance of vehicular ad-hoc network for providing safety-related applications in Intelligent Transportation System (ITS), the IEEE committee has developed the IEEE 802.11p standard for VANETs [1]. The US Federal Communication Commission (FFC) department has assigned 75 MHz of bandwidth at 5.9 GHz for dedicated short-range communication (DSRC), which is used to provide communications between vehicle to vehicle and vehicle to infrastructure [1]. The main aim of VANETs is to build an intelligent transportation system. DSRC can play an important role in building communications between vehicle to vehicle (V2V) and vehicle to infrastructure (V2I). The range of DSRC is about one thousand meters [8].

From the last few years, inter-networking over VANETs has been achieving massive momentum. Realizing its intensifying significance, academia, major car manufacturers, and governmental institutes are making efforts to develop VANETs. Various significant projects are initiated by different countries and famous industrial firms such as Daimler-Chrysler, Toyota, and BMW for inter-vehicular communications. Some of these prominent projects include CarTALK2000 [9], Car-to-Car Communication Consortium (C2CCC) [10], Advanced Driver Assistance Systems (ADASE2), California Partners for Advanced Transit and Highways (California PATH) [11], FleetNet [12], DEMO 2000 by Japan Automobile Research Institute (JSK) [12], Chauffeur in EU [13], and Crash Avoidance Metrics Partnership (CAMP) [14]. These developments are a key step toward the recognition of intelligent transportation services.

VANETs can provide a wide range of services like accident avoidance, a mechanism for regulating traffic flow, provision of internet access to the on-road public, information about the location of parking lots, restaurants, gas stations and infotainment applications such as playing games and listening to music [8,15,16].

The rest of the paper is structured as follows. The vehicular ad-hoc network architecture is explained in Section 2. Section 3 gives details about the position based routing protocols for an urban scenario. This section also contains the comparative study of the existing position based protocols. Simulation and analysis is presented in Section 4. Finally, we present conclusions and future research directions in Section 5.

2. Architectures of VANETs

In VANET, vehicles communicate through wireless links that are mounted on each vehicular node. Each node within VANET acts as both the participant and router of the network, as the nodes communicate through other intermediate nodes that lie within their own transmission range. There is no fixed architecture of VANETs due to their self-organizing nature. The architecture of VANETs can be classified into three types: (a) Pure cellular wireless local area network; (b) Pure ad-hoc networks; (c) Hybrid networks [16,17,18].

Figure 1 shows the cellular wireless local area network. The vehicular nodes access the internet through cellular gateways and wireless local area network access points. It assists vehicular nodes by giving information about traffic congestion and traffic control. It also provides infotainment services such as downloading data, latest news, parking information and advertising. The deployment of such types of architecture is very hard due to the high cost of cellular towers, wireless access points and geographic limitations [16,17,18].

Pure ad hoc network architecture is shown in Figure 2. It provides communication between vehicles and among nearby vehicles. It is also called an inter-vehicles ad-hoc network. This type of architecture collects and disseminates road related information without considering any fixed infrastructure. The vehicles are free to move on the road, high mobility of the vehicles induces quick changes in the network topology. The rapid topology changes create fragments in the network. In the pure ad-hoc mode, the frequent partitions of the network due to the high mobility of vehicular nodes make routing the data more challenging. The advantage of the pure ad-hoc mode is that it overcomes the deployment cost of base stations [16,17,18].

The hybrid architecture, which is shown in Figure 3, is composed of ad-hoc domain and infrastructure domain. It provides communication between vehicles to vehicles (V2V) as well as a vehicle to infrastructure (V2I). This type of architecture is helpful in providing richer contents and improved flexibility in contents sharing [16,17,18].

3. Position-Based Routing in Vehicular Networks

The position-based routing schemes are considered as suitable for tackling routing related issues in VANETs [8,15,16,17]. The position-based routing protocols use the geographical position of source and destination to accomplish communication between them. Every node is aware of its position due to global positioning system (GPS). The position of the neighboring node is found through beacons exchange. The position of the destination node is found using location services. When source node or intermediate node wants to send data to the destination node, if the destination node is in its transmission range than it directly forwards packet to the destination node. If the destination node is not in the transmission range it will forward the packet to a neighbor node that is the nearest to the destination node. In this way, the packet is relayed to destination [8,15,16,17,18]. In position-based routing, every node maintains one-hope neighbor information. Existing position-based routing protocols are developed for highway environment and urban environment. The highway environment consists of straight roads architecture without obstacles. On the other hand, urban environment consists of obstacles in the form of buildings. It is composed of streets and junctions. The points where two or more streets meet each other are called junctions. The data packets are routed towards destination through a set of junctions [19].

The routing of data in an urban environment is challenging because of obstacles. In the existing literature, there are many position-based routing protocols proposed for V2V and V2I communications considering the urban environment [15,16,17,18,19]. Some of these routing protocols are traffic aware. Consideration of traffic flow is very important in position-based routing for enhancing network performance in terms of packet delivery ratio, an end to end delay, and hop count [2]. The position based routing can be categorized based on the working environment as follows.

In Figure 4, we have provided the most significant position-based routing protocols that are designed to provide V2V communication for the city environment. We describe them below.

Greedy Perimeter Stateless Routing (GPSR) [20] finds the location for source node using GPS. The location of the neighbor node is found through beacons exchange. It locates destination using location services (likes Grid Location Service (GLS) and Hierarchical Location Service (HLS)) [21]. It consists of greedy mode and perimeter mode. In greedy mode source node or packet carrier node chooses a node among its neighbor that is closest to the destination and forward packet to it. When the forwarding node finds no neighbor node closest to the destination than itself and the destination is out of its reach. Packet meets local optimum. In such condition, GPSR uses perimeter mode to overcome a local optimum problem. Figure 5 shows the working of the greedy mode of GPSR where source node S selects neighbor node B among all its one-hop neighbors because it is the closest to the destination node D and forwards the packet to it. In the case of a local optimum problem, GPSR uses perimeter mode. Perimeter mode consists of two steps. In the first step, it creates graph planarization using relative neighborhood graph (RNG). In the second step, it uses right-hand rule for finding next neighbor node that relays the packet toward the destination.

Figure 6 shows the working of the perimeter-based forwarding strategy. The vehicular node is unable to locate the closest vehicular node to destination vehicle D than itself. It uses the right-hand rule of perimeter mode and select node B for forwarding packet. Similarly, at node B the packet is forwarded to node C; this will continue until the perimeter mode switches back to greedy mode.

Although this protocol is designed for a high environment, some of the researchers implemented it in the city environment and found it inappropriate. The main drawback of this routing protocol in the city environment is that its graphical planarization fails in city scenarios due to obstacles. Secondly, the perimeter phase uses long routes in relaying packet from source to destination which increases end to end delay. It also creates routing loops, which increases routing overhead. These drawbacks motivated the researchers to design a separate and an appropriate routing strategy that is suitable to overcome routing issues in the city environment [22,23,24,25,26].

Geographic Source Routing (GSR) Protocol [22] is a location-based routing protocol which is designed for the urban environment. In GSR, the source node finds the destination location using reactive location service. It accomplishes shortest routing path between source and destination using Dijkstra shortest path algorithm. The shortest path is composed of a set of junctions that are arranged in sequential order. The packet sent by the source node passes through these junctions and reaches the destination. The packet is forwarded in between junctions using the greedy forwarding approach.

The simulation outcomes, with the use of realistic vehicular traffic in the urban surroundings, illustrated that GSR performed better than topology based routing protocols like Dynamic Source Routing (DSR) and Ad-hoc on Distance Vector (AODV) in terms of end to end delay and packet delivery ratio [8]. GSR selects junction statically without considering traffic density which is its drawback. Consideration of traffic density is very important which provides connectivity for relaying the packet toward destination [15].

Greedy Perimeter Coordinator Routing (GPCR) [23] is proposed for the city environment. It is composed of two phases, the restricted greedy forwarding, and the perimeter mode. The distinguishing feature of GPCR is that the coordinator node is responsible for making routing decision without considering digital map. The node that is located at the junction is called coordinator node. The restricted forwarding mode bound the packet carrier node to forward the packets to a node that is located at the junction, instead of sending them to a node across the junction as shown in Figure 7. When restricted greedy forwarding meets local optimum, it uses perimeter mode to overcome such problem. In perimeter mode, it is assumed that the graphs are naturally planner. So, it does not compute graph planarization which induces partition in the network. The perimeter phase uses the right-hand rule to relay the packet to the destination. The first problem with this protocol is that it is not traffic aware [2]. Secondly, the perimeter phase also causes delay in relaying the packet toward the destination which degrades the throughput of the network [8]. The problem with the restricted greedy forwarding is that it takes more hops as compared to simple greedy forwarding as shown in Figure 8 which degrade the performance of the network [24].

Figure 7 shows that in case of greedy forwarding, node A forwards the packet to node C which is closest to the destination, while in case of restricted greedy forwarding, node A forwards the packet to a node on the junction instead of forwarding to node C.

Figure 8 shows a scenario of the inefficiency of restricted greedy forwarding. In this figure, the number of hops from source to destination node that restricted greedy takes into account is 16 while simple greedy forwarding just takes 12. In case of restricted greedy forwarding of GPCR, the packets are always stopped at the junction and hence, packet traverses greater number of hops as compared to simple greedy forwarding. Therefore, restricted greedy forwarding is inefficient as compared to simple greedy forwarding [24,25].

GpsrJ+ [24] is an enhancement of GPCR. Unlike GPCR, it avoids unnecessary packet stop at intersection which increases hop count. It uses two-hop neighbor information to forecast which street its neighboring intersection vehicle will take. If forecast specifies that its neighboring intersection will forward the packet on to a street with different direction, it forwards the packet to the junction vehicle; else it avoids the intersection and forwards the packet to vehicular node that is closest to the destination. The simulation outcome shows that GPSRJ+ outperforms GPCR in terms of packet delivery ratio and hop count.

Anchor based Street and Traffic Aware Routing (A-STAR) [25] establishes anchor path with high connectivity by using information based on statistically rated maps about city bus routes. When a packet faces local optimum situation then route recovery strategy is used to overcome a local optimum problem by calculating a new anchor path. The simulation results indicate that A-STAR outperforms GSR and GPSR because it has the capability of accomplishing end-to-end connected path even in case of low vehicular traffic density. However, one problem associated with this approach is that routes are along the anchor path that may not be optimal resulting in increased end-to-end delay [2].

Greedy Traffic Aware Routing (GyTAR) [15] is a junction-based geographic routing strategy that is capable of accomplishing robust routes in urban scenarios. It has two modes: (i) a dynamic junction selection mechanism for accomplishing shortest path based on traffic density; (ii) an improved greedy forwarding that forwards the packet in between two junctions. Because of these two mechanisms, packets move towards destination along the urban streets that present higher connectivity. GyTAR performs better than previous routing protocols in terms of packet delivery ratio, routing overhead and end-to-end delay. Problem with this approach is that it does not consider the direction of the vehicle while selecting next junction as a result in some city scenarios, protocol suffers from a local optimum problem which affects the performance of the network [8].

Enhanced Greedy Traffic Aware Routing Protocol (E-GyTAR) [8] is an enhanced version of GyTAR. It has also two phases: (i) dynamic junction selection mechanism based on directional density, (ii) improve greedy forwarding for routing in between junction. It accomplishes shortest routing path on the basis of directional density and thereby routes the packet toward the destination. It uses improved greedy packet forwarding strategy to forward the packet between the junctions. It avoids local optimum by using carry and forward approach. The major problem associated with this routing is that it selects junctions based on directional density and ignores non-directional density flows on a multi-lane road. If directional density is absent then this protocol cannot find the way to relay packets towards the destination. The non-directional density is also useful in relaying packet towards destination [19].

Traffic Flow Oriented Routing Protocol (TFOR) [2] is a recently proposed protocol for the urban environment. Its main feature is to assume traffic flows while routing. It consists of two modules: (a) A junction selection mechanism based on traffic flows and the shortest routing path and (b) forwarding strategy based on two-hop neighbor information. While accomplishing the shortest path, it considers traffic flows. It relays the packet from source to destination through those city streets that contain high traffic flows. Higher traffic flows provide more connectivity which increases the throughput of the network. The simulation outcomes, in realistic vehicular traffic urban surroundings, illustrated that TFOR outperforms E-GyTAR, GSR, and GPSR in terms of packet delivery ratio and end-to-end delay.

Figure 9 shows the junction selection mechanism of TFOR. In this figure, the source vehicle S that is located at the current junction has two candidate neighbor junctions J₂ and J₃ of the current junction. The traffic flow between the current junctions and J₂ is higher as compared to current junction and J₃. Also, J₂ is at the shortest distance to the destination as compared to J₃. So, TFOR protocol chooses J₂ and moves packet through it towards destination D.

Directional Geographic Source Routing (DGSR) [19] is an enhanced version of geographic source routing (GSR) with directional forwarding strategy. In this routing protocol, the source node uses location services to get the position of the destination node. It computes the shortest path from the source to destination using Dijkstra Algorithm. The shortest path is composed of a sequence of junctions. The packets from source node follow the sequence of junctions to reach the destination. If packet meets local optimum, DGSR uses carry and forward approach to overcome a local optimum problem.

Enhance Greedy Traffic Aware Routing-Directional (E-GyTARD) [19] is an enhanced version of E-GyTAR [8] with directional forwarding. It consists of two mechanisms: (i) Junction selection; (ii) Directional greedy forwarding strategy. It uses location services to get the position of the destination node. It selects junctions on the basis of directional traffic density and shortest distance to the destination. It forwards the packets in between junction using directional greedy forwarding. Simulation outcomes in realistic urban scenarios show that E-GyTARD outperformed GSR and DGSR in terms of packet delivery ratio and end-to-end delay.

Table 1. Comparative study of position aware routing protocols for urban environment.

V2V Based Position Aware Protocols	Comparative Characteristics
	Location Service Required	Vehicular Density	Junction Selection	Prediction Based	GPS Required	Digital Map Required	Strategy to Overcome Local Optimum	Environment	Hop Count	Realistic Mobility Flows
GSR [22]	Yes	No	Static	No	Yes	Yes	Fall back on greedy mode	City	Single hop	Yes
GPCR [23]	Yes	No	-	No	Yes	No	Right hand Rule	City	Single hop	Yes
GPSRJ+ [24]	Yes	No	-	Yes	Yes	Yes	Perimeter Mode	City	Two hop	Yes
A-STAR [25]	Yes	No	Static	No	Yes	Yes	Reconstruct anchor path	City	Single hop	Yes
GyTAR [15]	Yes	Yes	Dynamic	Yes	Yes	Yes	Carry and forward	City	Single hop	Yes
E-GTAR [8]	Yes	Yes	Dynamic	Yes	Yes	Yes	Carry and Forward	City	Single hop	Yes
TFOR [2]	Yes	Yes	Dynamic	Yes	Yes	Yes	Carry and Forward	City	Two hop	Yes
DGSR [19]	Yes	no	Static	No	Yes	Yes	Carry and Forward	City	Single hop	Yes
E-GyTARD [19]	Yes	Yes	Dynamic	Yes	Yes	Yes	Carry and Forward	City	Single hop	Yes

GSR: Geographic Source Routing; GPCR: Greedy Perimeter Coordinator Routing; GPSRJ+: Greedy Perimeter Stateless Routing Junction+; A-STAR: Anchor based Street and Traffic Aware Routing; GyTAR: Greedy Traffic Aware Routing; E-GyTAR: Enhanced Greedy Traffic Aware Routing; TFOR: Traffic Flow Oriented Routing; DGSR: Directional Greedy Source Routing; E-GyTARD: Enhanced Greedy Traffic Aware Routing Directional.

shows the comparative characteristic of all the aforementioned routing protocols.

4. Simulation and Analysis

4.1. Simulation Setup

For implementation and performance analysis through simulation, we have chosen two dynamical junction selection routing protocols (i.e., TFOR, and E-GyTARD) and one static junction selection routing protocol (i.e., DGSR). The simulations are carried out in GLOMOSIM (Global Mobile System Simulator) [27]. In our simulation, VanetMobiSim [28,29] is used to generate the vehicular mobility traces in an area of 2400 × 2000 m². The area contains 20 intersections and 32 bidirectional multilane roads in which vehicular nodes mobility is simulated.

The vehicular nodes are randomly distributed over the multilane roads and move in both directions. The movements of the vehicles on the roads are based on the car following model or intelligent driving model [28,29]. The vehicles speed depends on the kinds of the vehicles (like car, bus, truck, etc.) and nature of the roads. The rest of the parameters are summarized in

Table 2. Simulation setup.

Simulation/Scenario		MAC/Routing
Simulation time	100 min	MAC protocol	802.11 DCF
Map size	2400 × 2000 m2	Channel capacity	54 Mbps
Mobility model	VanetMobiSim	Transmission range	266 m
Number of intersections	20	Traffic model	15 CBR connections
Number of double lane roads	32	Packet sending rate	5 packets per second
Number of vehicles	75–250	Vehicle Speed	35–60 km/h
Number of simulation runs	4	Packet size	128 bytes

.

4.2. Results and Discussion

For performance analysis, we used packet delivery ratio, end-to-end delay, and routing overhead as the performance metrics. Packet delivery ratio is the ratio of the data packets delivered successfully to the destination vehicular node to those generated by the source vehicular node [8]. The end-to-end delay is the average time taken for a packet to pass through the network from its source vehicular node to the destination vehicular node [2]. Routing overhead is the ratio of total control packets spawned to the total data packets delivered at the destinations during the entire simulation [2]. The detail of these metrics is provided in [30,31,32,33].

4.2.1. Packet Delivery Ratio

Figure 10 shows the impact of traffic density on packet delivery ratio. With an increase in traffic density, the packet delivery ratio starts to increase. This is because traffic density is the source of connectivity. High traffic density provides more connectivity. The packet delivery ratio depends on connectivity. It is observed from the figure that dynamical junction selecting routing protocols TFOR and E-GyTARD perform better than the static junction selection routing protocol DGSR. The main reason behind this observation is that DGSR selects statically sometime those streets that do not contain enough vehicles to carry packet towards the destination. This causes a reduction in connectivity which reduces packet delivery ratio. The dynamic junction selection routing protocol TFOR outperformed E-GyTARD, this is because TFOR uses both directional and non-directional routing paths efficiently. E-GyTARD selects junction on the basis of directional density and hence misses some important streets that provide the shortest path to the destination. These shortest paths sometime provide enough non-directional traffic density which are useful in relaying packet towards the destination [2].

4.2.2. End-to-End Delay

Figure 11 illustrated that, with an increase in traffic density, the end-to-end delay decreases. This is because an increase in traffic density increases the probability of packets being routed instead of being apprehended in suspension buffer. TFOR and E-GyTARD achieve much lower end-to-end delay than DGSR. This is due to the fact that DGSR first computes the sequence of junctions statically before transmitting a packet, without considering the traffic density, which causes delay.

4.2.3. Routing Overhead

Figure 12 depicts that an increase in traffic density causes an increase in routing overhead for all the three protocols. This is due to the fact that the numbers of control messages depends on traffic density. As the node density increases, the routing overhead also increases. The routing overhead of TFOR and E-GyTARD is lower than DGSR. This is because TFOR and E-GyTARD delivered the larger number of packets to the destination which reduced the routing overhead.

5. Conclusions and Road Map for Future

This paper presented a comprehensive study of various most significant position-based routing protocols which are designed for the vehicle to vehicle communication in city scenarios. At the outset, we provided an overview of the architecture of VANETs. Then we discussed several position-based routing protocols with respect to their methods of working and limitations. We have also provided a qualitative comparative study of aforementioned routing protocols on the basis of some important parameters like mobility, traffic density, forwarding technique and method of junction selection mechanism, location requirement, and strategy used to tackle a local optimum problem. All these parameters affect the performance of the vehicular ad-hoc network. We have also provided a simulation based study of dynamic junction selection and static junction selection based routing protocols.

In VANETs, the design of efficient routing protocol for effective vehicular communications poses a series of technical challenges. However, while the routing mechanism for efficient vehicular communication in VANETs has gained much attention from the wireless network research community, there is still a lack of careful exploration of some of the challenges related to routing. One of them is secure routing in VANETs. Security is vital for message dissemination routing protocols because illegal message tempering will result in overwhelming penalties. Without secure communication, many applications will have an impact on life or death decisions. Due to these features of VANETs, secure routing is more challenging. With security, reliable communication is also a challenge. There are some characteristics of VANETs like high mobility and intermittent connectivity which create sudden link ruptures during routing or forwarding of packets and make the network unstable and unreliable. Addressing sudden link ruptures which cases packet loss is also challenging. Establishing optimal path from source to destination based on traffic density and shortest distance need an efficient mechanism that provides information about traffic density on the road. Without that mechanism, packets may be routed toward the destination through those city streets that contain no traffic density. Traffic density provides connectivity for relaying packets towards the destination. Developing such mechanism is also challenging. As the VANETs have two environments. One is the city environment and other one is the highway. City environment contains junctions and obstacles in the form of high rise buildings while highway environment contains no such obstacles. Developing a routing strategy that is applicable to both environments can be another future research direction.

In general, the process of how to find the most robust route to the desired destination varies depending on the mechanism used in that protocol. In the area of routing, however, real-life urban environment characteristics cannot be properly reflected in the aforementioned routing protocols for VANETs. There is need of optimal path based secure, stable and reliable routing protocol that incorporates real life urban environment characteristics such as intermittent connectivity, high mobility, sparse and dense nature of the network to enhance the performance of VANETs in terms of packet delivery, end-to-end delay, routing overhead and hop count.