2

Routing for Vehicular Ad Hoc Networks

This chapter explains the basic concepts used in the routing process for vehicular Ad hoc networks. It presents various transmission modes that are used to distinguish different kinds of routing such as unicast, multicast and broadcast transmission modes. Moreover, four categories of VANET routing are highlighted on the basis of the route discovery principle of each category. Furthermore, this chapter illustrates the Quality-of-Service (QoS) metrics that are often used to evaluate the effectiveness of VANET routing. To show the VANET community efforts that paved the way for the industry to manufacture devices of vehicular transmission, we exhibit VANET routing standards ratified until nowadays. Finally, routing challenges and issues are highlighted at the end of the chapter.

2.1. Basic concepts

In this section, basic concepts used in Vehicular Ad hoc Network (VANET) routing are reviewed. We begin with the beaconing, single-hop and multi-hop beaconing concepts used to transmit data packets. Later on, we explain the principles of different VANET routing protocol categories that are distinguished according to network infrastructure and equipment used to find paths between nodes. Specifically, we describe the main principles of three VANET routing categories namely, topology-based routing, geography-based routing and cluster-based routing.

2.1.1. Single-hop versus multi-hop beaconing in VANETs

Beaconing is defined as the process of broadcasting messages containing status information of VANET nodes in a local area known as node neighborhood in a periodic manner, using communication devices installed on VANET nodes (i.e. vehicles or roadside units (RSUs)). They are used to improve vehicular traffic safety or to alleviate traffic congestion. A beacon message consists of a vehicle’s identifier, its geographical position and possibly its velocity that should be received up to a certain distance with a specific freshness. Beacon distance and freshness are determined by VANET applications to be useful [MIT 09]. To reach beacon distance, two approaches are defined: single-hop or multi-hop beaconing.

2.1.1.1. Single-hop beaconing

It is a beaconing message dissemination aiming to reach the required dissemination distance in one hop using a high-transmit power, as shown in Figure 2.1. Therefore, a direct node-to-node communication and a reduced delay is the major advantage of such approach due to non-use of intermediate nodes. Hence, multiple hops transmission mode (relaying) is not preferred in traffic safety VANET applications due to the affected delay, especially when VANET nodes performed with low-transmission power. Moreover, single-hop transmission could lead to a less congested network, since reduced beacons are generated and transmitted. However, the quality of received beacons can be limited because of the long distance traveled by these messages.

Figure 2.1. Single-hop beaconing. For a color version of this figure, see www.iste.co.uk/bitam/bio-inspired.zip

2.1.1.2. Multi-hop beaconing

The multi-hop beaconing approach uses a small transmit power to cover the dissemination distance by means of transmitting beacons through multiple relayed nodes, as presented in Figure 2.2. This approach ensures a message transmission with high quality; nevertheless, the network can be very congested, since many more beacons are transmitted than in the single-hop case. To deal with this problem, multi-hop forwarding can be more efficient if it applies an intelligent and an optimized relaying strategy. For example, multiple beacon messages can be multiplexed and sent into one single transmission. Also, one VANET node can reduce network congestion by sending the overhead of multiple message headers into the next beacon transmission.

Figure 2.2. Multi-hop beaconing. For a color version of this figure, see www.iste.co.uk/bitam/bio-inspired.zip

2.1.2. Routing classification of VANETs

According to the network structure used to find routes, proposed VANET routing protocols can be broadly classified into three categories: topology-based, geography-based and cluster-based routing. The principle of each category is explained in the following sections.

2.1.2.1. Topology-based routing

Initially, topology-based routing was conceived for mobile Ad hoc networks (MANETs), and was applied to VANETs due to the large common properties between these two kinds of networks namely, mobility of nodes, topology selforganization, lacking of central control, etc. [ZEA 12]. The main principle of topology-based routing considers topological links between nodes along the sourcedestination path in order to determine routes. In other words, route discovery is based on the information about existing links between nodes, as shown in Figure 2.3. To achieve this, a mechanism of assigning a unique address to each of the participating nodes is defined using a set of control packets sent through existing links [MAU 01]. Three types of topology-based routing protocols can be found in the literature such as proactive, reactive and hybrid routing.

Figure 2.3. Topology-based routing. For a color version of this figure, see www.iste.co.uk/bitam/bio-inspired.zip

2.1.2.1.1. Proactive routing

Proactive routing in Ad hoc networks is defined as a method that aims to find paths in advance for all source and destination pairs. Each node maintains routing information to every other node in routing tables that are periodically updated. Hence, all paths are saved by each node toward all destinations even they are not needed. This periodic discovery copes with the frequent changes of network topology information, where at any time, path is ready to be used without any delay affected by the discovery process [BIT 10, MBA 07]. However, in such dynamic networks characterized by their rapid topology changes, proactive routing may generate much control packets. Also, this type of routing can consume a significant amount of network bandwidth and can update in many times routing tables that are rarely used in its current structure [ABO 04]. In this category, dynamic destinationsequenced distance-vector routing (DSDV) [PER 94] and optimized link state routing (OLSR) [CLA 03] protocols can be cited.

2.1.2.1.2. Reactive routing

Contrary to proactive routing, reactive routing discovers routes only when the source node established a new data transmission routine; it is an on-demand process [BIT 10]. Route discovery usually starts by flooding a route request packet through the network. When a node with a route to the destination (or the destination itself) is reached, a route reply is sent back to the source node using link reversal if the route request has traveled through bidirectional links or by piggybacking the route in a route reply packet via flooding [ABO 04]. We can distinguish two classes of reactive routing protocols: next-hop routing and source routing.

In next-hop routing (also called hop-by-hop routing), each data packet can reach its destination using two addresses kept in its header: the destination address and the next-hop address. Consequently, each next-hop node conducts the packet to the following hop and so on until reaching the destination. It is worth noting that each intermediate node keeps in its routing table the next hop to the requested destination. This mechanism is more appropriate to the dynamics of VANETs, since each node can update its routing table when they receive fresher topology information, and then they forward the data packets over fresher and better routes. However, a periodic beaconing process is mandatory to ensure up-to-date neighbor connectivity that increases the routing overhead [ABO 04]. Ad hoc on-demand distance vector routing (AODV) [PER 03] is one of the well-known protocols proposed in this class.

In source routing, each data packet can reach the destination node using all node addresses of the complete route (from source to destination) kept in its header. Therefore, a periodic beaconing process of neighbor connectivity can be avoided by the intermediate nodes, since transmission is not based on node routing information. Then, the generated control packets are reduced (routing overhead). Nevertheless, due to the network dynamics, the used complete route does not guarantee a correct transmission, especially for the long routes. As an example of source routing protocol, dynamic source routing (DSR) has been proposed in [JOH 01b].

We note that reactive routing (next hop or source routing) generally suffers from a latency affected by the discovery process, since routes are not ready to be used to forward data packets when the source node wants to establish a new communication.

2.1.2.1.3. Hybrid routing

This category combines both proactive and reactive principles to benefit from their advantages and prevent their disadvantages. The main principle is that each node uses a proactive routing in its local region limited by some hops (usually three hops), whereas a reactive routing is applied between regions known as zones. With this principle, control packets are reduced, since the network is organized into a set of local regions (sort of backbones) where nodes of each region share a limited number of discovery packets in a proactive manner. On the other hand, packets forwarding between regions are ensured through a reactive routing. Therefore, this kind of protocol is very adequate to very large and scalable networks. In [HAS 99], a hybrid routing protocol called zone routing protocol (ZRP) was...