Routing and data diffusion in VANETs — Routing protocols

Editor's Note: Wireless sensor networks lie at the heart of emerging applications in nearly every industry segment. In building these networks, designers contend with issues that encompass real-time communications, efficient high-bandwidth data exchange, multiple network topologies, selection of optimal routing strategies, and more. The book, Building Wireless Sensor Networks, offers detailed treatments on critical requirements and promising solutions in each of these areas and more. 

This excerpt focuses on design challenges and methods associated with creating a vehicular ad hoc network (VANET). To share data as vehicles pass on roads or rest in parking areas, a VANET must contend with issues as varied as the physics of signal propagation, the fluid nature of data routing, and the security vulnerabilities associated with participation in an ad hoc network. Because of the changing nature of a VANET, designers need a broad understanding of these issues. 

In this excerpt from the book, the authors offer an in-depth discussion that defines the nature of VANET challenges and discusses alternatives for their solution. Continuing the description of VANETs in part 1, part 2 and part 3, this installment of this series provides an in-depth discussion of routing protocols for VANETs. 

Elsevier is offering this and other engineering books at a 30% discount. To use this discount, click here and use code ENGIN318 during checkout.

Adapted from Building Wireless Sensor Networks , by Smain Femmam, Editor.

Chapter 3. Routing and data diffusion in vehicular ad hoc networks (Cont.)
By Frédéric Drouhin and Sébastien Bindel

3.3.2. Routing protocols

Routing protocols dedicated to MANET have been widely investigated in the past. Considered as a subset of MANET, some routing protocols from MANET can also be used in VANET. However, the high velocity of vehicles and their specific motion have been taken into account in the design of specific routing protocols for VANET. A first survey made by [LI 07] introduced a classification based on the following criteria: ad hoc , position-based, cluster-based, broadcast and geocast-based. Even if an author has the merit of giving a classification and introducing concepts, they have become out of date due to recent research advances. [LEE 10] and [SHA 14] investigate in depth routing solutions. The most recent classification is given by [SHA 14] and is based on the VANET architecture, V2V and V2I. Routing protocols dedicated to the V2V architecture can be classified into six categories: (i) topology-based, (ii) position-based, (iii) cluster-based, (iv) geocast-based, (v) multicast-based and (vi) broadcast-based. Figure 3.9 depicts the different delivery scheme used by unicast, broadcast, multicast and geocast protocols. Concerning routing protocols for V2I, two groups are considered: (i) for static infrastructure and (ii) for mobile infrastructure.

click for larger image

Figure 3.9. Type of delivery scheme

3.3.2.1. V2V routing protocols

Routing protocols designed for a V2V architecture exploit the distributed feature of such a network. The most beneficial aspects are the loss of tolerance and its scalability; moreover, it is often hard to maintain stability, which therefore requires several approaches that have been investigated and detailed in the following paragraphs.

3.3.2.1.1. Topology based

Topology-based protocols have been inherited from MANET and rely on topology information to construct a routing path. These protocols are classified into three categories: proactive, reactive and hybrid. Proactive protocols , also called table-driven, maintain a periodic routing path discovery. This strategy has the benefit of providing nodes with a fresh vision of the topology, but it requires a significant bandwidth, not available for data. The most popular protocol is certainly the optimized link state routing (OLSR) protocol, but there are others such as: destination-sequenced distance vector (DSDV), fisheye state routing (FSR), global state routing protocol (GSRP), wireless routing protocol (WRP) and topology dissemination based on reverse-path forwarding routing (TBRPF). Reactive protocols , also called on-demand routing protocols, start the routing discovery process when data need to be transmitted to a desired destination. These protocols have the benefit of having a reduced bandwidth consumption, unlike proactive protocols; however, since the routing process is triggered only by data needed to be transmitted, the delay related to the routing path discovery is then added. The most popular protocol is ad hoc on-demand distance vector (AODV) but there are others: temporally ordered routing algorithm (TORA), prediction-based AODV (PRAODV) and dynamic source routing (DSR). The last category includes protocols that combine both a proactive and a reactive routing scheme. Most protocols define a zone wherein a proactive scheme is used and a reactive scheme to route data inter-zone. The main idea of this approach is to profit from the benefits of proactive and reactive schemes and avoid drawbacks. The best known protocols are zone routing protocol (ZRP) and hybrid ad hoc routing protocol (HARP).

3.3.2.1.2. Position based

Position-based protocols rely on the geographic node’s location acquired with a specific device such as a Global Positioning System (GPS). This information is used for making routing decisions. Such protocols can be classified into three categories: non-delay tolerant, delay tolerant and hybrid. Non-delay tolerant protocols aim to transmit data to a destination as soon as possible. A typical routing strategy is to forward data to the node closest to the destination. This category includes Greedy Perimeter Stateless Routing (GPSR), Geographic Source Routing (GSR), etc. Delay tolerant tolerant protocols adopt another approach by keeping data packets when a direct end-to-end path is not available. The biggest drawback of such a solution is the possible important end-to-end delay. These protocols are efficient when the node density is low. The best known protocols are scalable knowledge-based vehicular routing (SKVR), vehicle-assisted data delivery (VADD) and geographical opportunistic (GeOpps). The last category, Hybrid position-based protocols , combines both a delay and a non-delay routing scheme. The aim is to profit from the network connectivity to choose the best routing algorithm. When a path exists, the non-tolerant algorithm is used, but when the path is broken and no route exists, the tolerant delay algorithm is triggered. This category includes the GeoDTN+NAV protocol.

3.3.2.1.3. Cluster based

Cluster-based protocols form a cluster in order to reduce the number of broadcasting dates by reducing the diffusion domain. A cluster is formed by a cluster head that is responsible for its management. Communications inside a cluster are performed directly between vehicles. For intercommunications, vehicles have to forward data to the cluster head. The creation of a cluster can be static or dynamic; however, the management of dynamic clusters is more difficult. The most common cluster-based routing protocols are cluster-based routing (CBR), location routing algorithm with cluster-based flooding (LORA-CBF), clustering for open IVC network (COIN) and traffic infrastructure-based cluster routing protocol with handoff (TIBCRPH).

3.3.2.1.4. Geocast based

Close to the position-based protocols, geocast-based protocols use a multicast routing to deliver a message to all vehicles situated in a geographical area. The aim of such protocols is to deliver a packet from a source node to all nodes in the same geographical area. Geocast routing can be considered as a multicast service where the network is split according to the desired geographical region. This category includes the following protocols: Inter-Vehicle Geocast (IVG), Cached Geocast Routing (CGR) and Mobicast.

3.3.2.1.5. Multicast based

Unlike geocast-based protocols where packets are delivered to all nodes situated in a region, multicast-based routing protocols maintain a structure such as a tree or a mesh structure to define destination nodes. Tree-based routing protocols attempt to maintain a multicast routing tree to transfer from a source to a group of destination nodes. The main drawback of such an approach is that the tree needs to be rebuilt when the topology is volatile, as a result of which routing service is continuously disrupted. Multicast-based routing protocols rely on a tree structure, which include the multicast ad hoc on demand (MAODV) protocol, adaptative demand-driven multicast routing protocol (ADMR) and multicast with ant-colony optimization for VANETS based on MAODV (MAV-AODV) protocol. Mesh-based multicast routing protocols maintain a connected component of the network containing receivers of a group. Two protocols can be considered as mesh-based multicast routing protocols: On-demand multicast routing protocol (ODMRP) and destination-driven on-demand multicast routing protocol (D-ODMRP).

3.3.2.1.6. Broadcast based

The last category includes broadcast-based protocols that flood routing messages over the network. This strategy enhances the probability reception of a message to a destination, but with a high bandwidth cost. Suitable for scattered networks, they become less efficient when the density increases. Broadcast-based protocols include BROADCOMM, urban multi-hop broadcast (UMB) and distributed vehicular broadcast (DV-CAST).

3.3.2.2. V2I routing protocols

The high mobility of vehicles does not allow V2V protocols to be efficient in all situations. In this context the use of V2V routing protocols only is not sufficient. That is why some routing protocols exploit both the vehicles and the infrastructure. Regarding the infrastructures, they can be considered as static or dynamic.

3.3.2.2.1. Static infrastructure

Assuming fixed RSU linked to a backbone, some routing protocols need a uniform distribution of RSU; meanwhile, others suppose a placement only at intersection. For example, the static node-assisted adaptive (SADV) routing protocol can only consider RSU placed at intersections, but the roadside-aided routing (RAR) require RSU to be placed at each extremity of a geographical area.

3.3.2.2.2. Dynamic infrastructure

RSU tends to minimize the end-to-end delay, the main problem is over the covered area. To solve this issue, some research suggests replacing fixed RSU with mobile vehicles to obtain a mobile infrastructure such as for the mobile infrastructure-based VANET routing (MIBR), the mobile gateway routing protocol (MGRP) and the prediction-based routing (PBR) protocols.

The next installment of this series discusses VANET security issues and protocols.

Reprinted with permission from Elsevier/ISTE Press, Copyright © 2017


Frédéric Drouhin is an Assistant Professor in the Laboratoire Modélisation Intelligence Processus Systèmes (MIPS) at the Université de Haute Alsace.

Sébastien Bindel is an Associate Professor in the Département Réseaux et Télécommunications at Université de Haute-Alsace.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.