Routing and data diffusion in VANETs — Routing mechanisms

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 and part 2, this installment of this series provides an in-depth discussion of key VANET routing mechanisms. 

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. Routing

This section presents routing protocols and their related mechanisms. In VANETs, vehicles have different velocities and are driven in different environments contributing to a decrease in the connectivity of the network. In such a situation, the design of routing protocols need to take into account these features. The first part of this section presents metrics used by routing protocols to assess the local links and thus the routing path. The second part details dedicated routing protocols for both V2V and for V2I infrastructures.

click for larger image

Figure 3.6. Attenuation, shadowing, fast fading effect: power reception over distance with two ray ground, shadowing, Rice (K = 2) and Doppler model

3.3.1. Neighbor selection

Path selection relies on information provided by metric, given a “cost” to reach a neighbor. It can be related to the number of hops, the link quality, the bandwidth, the latency, etc. The computation of the path cost is then related to the cost of each local link composing it and four types of metrics can be distinguished according to [WAN 99]. The first one includes additive metrics, where the cost of the path is the sum of all costs of local links. The second one regroups multiplicative metrics, where the cost of the path is the multiplication of all costs of local links. The third group is the concave metric, where the cost of the path is the minimum cost of local links. The last group includes convex metrics, wherein the cost of the path is the maximum cost of local links. Owing to the high velocity of vehicles in VANET, most of the dedicated routing protocols use a combination of metrics in order to have an accurate assessment of the cost of the link. This section starts with a description of the most used metrics in VANET and details current implemented solutions.

3.3.1.1. Hop count metric

The traditional approach takes into account the number of hops to reach a destination. The ultimate benefit of such a technique is that it is user-friendly. This hop count number is currently coded on 8 bytes and incremented by one at each retransmission. Widely used by routing protocols dedicated to wired networks, such an approach becomes inefficient in wireless networks as pointed out by [DEC 03b]. Authors showed through a wireless sensor test, that the shortest paths often have fewer capacities than others and have opened a discussion on the link quality.

3.3.1.2. Link quality estimators  

Link quality estimators (LQE) have been well designed for wireless sensor networks, and are also used in vehicular networks. [BAC 12] have classified these estimators into two categories. The first category, hardware-based, includes all estimators performing an assessment from information available at the physical layer. The second, software-based, regroups the rest of LQE running at upper layers, either on MAC or the IP layer.

3.3.1.2.1. Hardware LQE

Hardware-based estimators perform an assessment from information available at the physical layer. Assessments are provided by the receiver hardware without any additional computation costs, and are performed only by the receiver at each frame reception. In addition, the computed link quality can be assessed though the current traffic on the wireless channel without the need for any periodical broadcasts. In order to evaluate the reliability of an estimator, a good fitting with the Packet Reception Ratio (PRR) is required.

The first estimator, the received signal strength indicator (RSSI), gives the signal strength of the received packet. The signal-to-noise ratio (SNR) gives the difference between the pure received signal strength and the noise floor. The link quality indicator (LQI) only available in the IEEE 802.15 networks provides a link quality assessment based on the height symbols of the received packet. A second generation of hardware-based LQE has been designed based on detailed information on the decoding process related to the DSSS (direct-sequence spread spectrum) used in IEEE 802.15.4 networks. [HEI 12] have designed an estimator called CEPS, which relies on chip errors on the payload symbols to assess the PRR. As demonstrated by the authors, the correlation between the chip errors and the PRR can be approximated by a linear fit. Later, [SPU 13] suggested the BLITZ estimator, an improvement on the CEPS, by also considering chip errors related to the preamble. This improvement allows analysis of packet synchronization errors in order to obtain faster and more accurate information on the link quality.

As depicted in Figure 3.7(a), the correlation between the RSSI and the PRR is not easily deductible.

click for larger image

Figure 3.7. PRR as a function of RSSI, SNR, LQI in WSN for 160 hours of data though 72 links got by [LIU 14]

However, [SRI 06] have demonstrated that over a RSSI threshold, the PRR is consistently high. This observation can be confirmed on the Figure 3.7(a), where the PRR is above 0.9 when the RSSI is below −85 dBm. Regarding the SNR, it provides a better correlation with the PRR than the RSSI; however, a simple observation is not sufficient to deduct the corresponding PRR. The same observation can be made for the LQI, even if the coefficient correlation is the highest. As a result, regardless of the estimator, a single reading is insufficient to determine the PRR. With CEPS and BLITZ, authors try to solve this deficiency. The two estimators present a better correlation with the PRR, and Blitz can provide an assessment as soon as a preamble is detected, even if the frame reception failed. The major drawback of such solutions is their implementation, since they require information from the decoding process only available in the chipset radio. That is why all experiments have been performed with a software radio.

3.3.1.2.2. Software LQE

Software-based LQE performs an assessment from information available either at the MAC layer or at the network layer. In this context, estimators can only detect the good reception or the loss of a packet. Unlike hardware estimators, their assessments correlate directly with the PRR. Three kinds of estimators can be considered: (i) PRR-based, (ii) RNP-based and (iii) score-based estimators.

3.3.1.2.3. PRR based

PRR-based estimators are the simplest link quality estimators. Their computation is based on the ratio between received packets and expected packets. Considered as a reference for hardware-based, they can only assess the quality of the downlink part. The efficiency of such an estimator is the most challenging, since it relies on the time window size used by the moving average. For wireless sensor networks, a good practice is to fix the window size according to the channel coherence, since the velocity of nodes can be considered as near zero. Let c be the celerity of light (m .s −1), fc the carrier frequency in (Hz ) and v the velocity (m .s −1); the channel coherence Tc is then computed as follows:

Regarding the velocity of vehicles, the PRR cannot be computed from the time channel coherence. There is no silver bullet to compute the PRR regardless of the link lifetime, but some solutions try to solve this issue. [BIN 15] have suggested the use of a dynamic window size and [WOO 03] propose the use of the window mean with exponentially weighted moving average (WMEWMA).

3.3.1.2.4. RNP based

RNP-based estimators assess both sides of a link (downlink and uplink sides). A bidirectional communication is then required, which is why such estimators can detect unidirectional links. [CER 05] have demonstrated the absence of a relationship between the required number of packets (RNP) and the reception rate (RR). From this observation, they have designed an estimator maintained at the sender side and based on the required number of packet transmissions (RNP) before a successful reception. The RNP estimator runs at the link layer and requires the use of an automated repeat request (ARQ) to repeat the transmission of unicast packets until it is received. [DEC 03a] have designed the expected transmission count (ETX) estimator, which is maintained at the receiver side. Based on the computation, several ratios, d f , are related to the PRR and, d r , to the acknowledgment reception ratio (ARR). [FON 07] have designed the four-bit metric to be easily used by routing protocols and provide four bits of information related to each layer. The “white” bit set from the physical layer indicates whether the medium quality is high. The “black” bit provided by the local link layer indicates if an acknowledgment has been received for a transmitted packet. The network layer provides two pieces of information through the “pin” and “compare” bits and are used for the neighbor table replacement policy.

3.3.1.2.5. Score based

This category regroups all estimators providing a score rather than a value related to a specific phenomena such as the packet reception or the number of retransmissions. [BAC 10] have developed the fuzzy link quality estimator (F-LQE) mixing four indicators, the smoothed reception ratio, the link stability factor, the link asymmetry level and the channel average signal-to-noise ratio. F-LQE combines these information by using the fuzzy logic rule, in order to provide a single metric for the routing protocol. In [REN 11], authors designed an estimator called holistic packet statistics (HoPS), which provides information on the static and dynamic behavior of the link through four estimators. One is dedicated to providing a short-term assessment of the packet success rate, and another is dedicated to providing a long-term assessment. From the two, the absolute deviation and the trend are computed in order to assess the stability of the link. The F-ETX metric developed by [BIN 16] assesses both the quality and the state of the link. Concerning the link quality, F-ETX provides a short-term and a long-term assessment in order to compare links with a transient quality. Beside, F-ETX determines the link stability and transient and persistent unidirectionality phases. The main drawback of score-based metrics concerns the integration of information return by the metric in the routing process. There is no silver bullet to combine information to get an only metric value, authors of F-LQE use fuzzy logic; meanwhile, [REN 11] use empirical methods. The approach suggested by [BIN 16] was to integrate each piece of information in the routing process, e.g. if a link is declared unstable, then another link will be looked for.

click for larger image

Figure 3.8. RNP as a function of 1/RR

The next installment of this series examines VANET routing protocols and their differences from mobile ad hoc networks (MANETs).

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.