9 F-ETX: A Metric Designed for Vehicular Networks – Networking Simulation for Intelligent Transportation Systems

9
F-ETX: A Metric Designed for Vehicular Networks

9.1. Introduction

Due to their inherent characteristics, including self-organization, scalability, mobility and the fast changing transmission channel quality, vehicular ad hoc networks (VANET) address specific challenges. Vehicles move on the road network according to traffic patterns and they do not rely on a limited battery capacity. Vehicle-to-Vehicle (V2V) communications rely on the cooperation with each other to build opportunistic wireless networks. Since vehicles move with a wide range of speeds according to traffic patterns, the network topology is characterized by a potentially high dynamic. The road environment (e.g. urban, suburban and motorway) also plays a key role in the disturbance of the transmission channel.

Distributed applications require the cooperation of nodes, but they are bounded by connectivity and reliability issues. Those are partially solved by routing protocols, which ensure an end-to-end communication with a multi-hop relaying technique. To this end, protocols compute and share local information on the direct neighborhood to determine the best end-to-end path. A relevant challenge for routing protocols is the selection of the best kind of estimator to obtain reliable information on local links. Indeed, routing performance in terms of end-to-end delay and packet delivery ratio depends on the reliability of the selected path. The traditional hop count metric relates the cost of a path to the number of hops required to reach a destination. However, De Couto et al. [DEC 03b] have demonstrated the inefficiency of such a technique in wireless networks.

Link Quality Estimators (LQE) have been developed in order to fix the intrinsic limitations related to the hop count metric. They take into account either the signal quality or the lossy and the dynamic of a link to assess its quality. As discussed, in [BAC 12], LQEs have to meet four requirements, including: (i) the energy consumption, (ii) the accuracy, (iii) the reactivity and (iv) the stability of the estimation. However, for an LQE to be suitable for vehicular networks, additional requirements must be considered. The first one deals with the support of the node mobility since a vehicle may change its speed according to the speed limits and the traffic patterns. Regarding the signal disturbance, environment impacts the transmission channel quality. Finally, Zamalloa and Krishnamachari [ZAM 07] showed that the quality of a link can be split into three regions, connected, transitional and disconnected. In the connected region, a link has a high probability of having a high packet reception rate. In the disconnected region, a link has a high probability of having a low packet reception rate. The transitional region is an intermediate region characterized by an unstable link quality. The main challenge for an LQEs is accurately assessing the link quality regardless of the current region.

In order to build a thorough sample and assess the link quality, current estimators maintain an estimation window that stores received packets. Carpa et al. [CER 05a] invested the related challenges in order to assess the Packet Reception Ratio (PRR). They determine that a window can have a small size if the PRR is high or low, but a larger size is needed in other cases. However, current estimators keep a fixed estimation window size regardless of the PRR and cannot provide a reliable assessment if the link quality is situated in the transitional region. As a result, current LQEs have limited effectiveness in vehicular networks. To address the problem of the link assessment in vehicular networks, the Fast Expected Transmission Count (F-ETX) estimator has been developed [BIN 15b]. Unlike current estimators, it uses a dynamic window size fitting according to the packet loss occurrences. From experiments, we have observed that such an estimation provides only a snapshot of the quality. This remains insufficient since the quality trend is not taken into account to compare links among each other. Figure 9.1 shows the quality of a couple of links. If a link selection mechanism relies on a short-term estimation, it will continuously switch the best one among available links during the 80th and the 90th second. In contrast, a long-term estimation can highlight a tendency of the link quality while one grows (Link #2) and another decreases (link #1). We argue that a multi-estimator approach as suggested in [BAC 10b] [REN 11] is a better approach. As a result, F-ETX has been extended with three additional estimators assessing distinct features of a link in order to assess the link quality and determine the link state [BIN 15a]. We have also developed a framework in order to integrate the F-ETX within routing protocols. This chapter provides a detailed investigation of the metric. We provide a theoretical analysis of the window estimation and show its relationship with the quality assessment. Then, we describe the design of the F-ETX including window management algorithms and multi-estimators, and outline the framework to integrate the metric into a routing protocol. Finally, we prove its usefulness through realistic simulations.

Figure 9.1. The link selection problem

The remainder of this chapter is organized as follows. In section 9.2, the literature related to the LQEs is described. In section 9.3, we perform an analysis of the estimation by regarding its impact on the reactivity and the accuracy of the estimator. In section 9.4, we detail the F-ETX metric, including the couple of algorithms managing the window size and each estimator, and we outline the framework to integrate the metric into a routing protocol. In section 9.5, we describe simulation settings and depict results in section 9.6.

9.2. Link quality estimators

Link monitoring and measurement are a fundamental building block to assess the quality of wireless links. This information is used by several algorithms, e.g. for routing decision and group formation to build a substantial knowledge of the neighborhood. The literature related to this topic has been well investigated and several estimators have been developed. In this section, we summarize the literature and highlight the main challenges. LQEs can be classified into two categories: (i) hardware-based and (ii) software-based.

9.2.1. Hardware-based LQE

Hardware-based estimators profit from measures made at the physical layer by the hardware to assess the link quality. The quality is assessed as soon as a packet is received, without specific cost since the measurement is performed by the hardware. Such estimators assess the link quality by performing measurements on received packets. An estimation from a hardware-based estimator that correlates with the PRR is considered as a suitable metric. Two types of estimators can be distinguished, classical metrics exploiting the signal properties and a novel generation of estimators which retrieve information from the decoding process of the Direct-Sequence Spread Spectrum (DSSS) and the Orthogonal Frequency-Division Multiplexing (OFDM) techniques.

9.2.1.1. Signal property-based

The first one is the Received Signal Strength Indicator (RSSI) based on the measurement of the power reception of the incoming frame. Practical experiences have shown that RSSI can provide an accurate estimation when a link has good quality [SRI 06]. Srinivasan et al. [SRI 06] showed that above a RSSI value (−87dBm), the PRR is consistently high (99%). In [SRI 10], the same authors observed that the standard deviation of PRR is weak over a short time span. A variation of the RSSI can change a good link to a bad link if it operates near to the noise floor. A simple reading of the RSSI value is not sufficient to determine the related PRR, since they are not sufficiently correlated. The second one is the Signal-to-Noise Ratio (SNR). For a given modulation scheme, the bit error rate can be computed with the SNR, which can be extrapolated to the packet error rate and so the PRR [ZAM 07]. Unlike the RSSI, which is the sum of the power of the signal and the noise, the SNR indicator determines how strong the signal is compared to the ambient noise. As a result, SNR is a better candidate than the RSSI indicator. However, experiments have shown that correlation with the PRR is not deductible at all, and Lal et al. [LAI 03] depreciate its use when the link has an intermediate link quality. The Link Quality Indicator (LQI) was introduced in the IEEE 802.15.4 [IEE 16] for low rate wireless networks. Experimental works led by Lui et Cerpa [LIU 14] show that the assessment provided by the LQI has the best matching compared to the RSSI and the SNR. However, in the transitional region a simple reading of the LQI is insufficient to determine the PRR since its variance is too important. Boano et al. [BOA 09] suggest using the variance to distinguish good and bad links.

9.2.1.2. Decoding event-based

Heinzer et al. [HEI 12] developed a metric dealing with DSSS decoding process to measure the Chip Error Per Symbol (CEPS). However, the correlation between the assessment given by this metric and the PRR can be approximated by a linear fitting. To overcome this drawback, a novel metric called BLITZ was designed, also dealing with the DSSS decoding process [SPU 13]. Unlike CEPS, which performs on the payload, BLITZ relies on a measurement on the frame preamble used to synchronize the sender and the receiver. Experimental results show the better performance of BLITZ compared to the other metrics, but the experimentation environment was limited to a simple transmitter and a receiver in the same collision domain. Gabteni et al. [GAB 14] developed a link state indicator that analyzes decoding errors of the OFDM reception process. Called Link State Forwarding Indicator (LSFI), it is able to predict future link disruptions.

9.2.2. Software-based

Software-based estimators retrieve information from uppers layers, e.g. MAC and Net, to determine whether an expected packet will be received or not. These estimators are usually classified in three categories: (i) PRR-based, (ii) RNP-based and (iii) Score-based.

9.2.2.1. PRR-based

This type of estimator is based on successive PRR measurements to determine the link quality. Classical approaches maintain a window to monitor and sample traffic over the link. Cerpa et al. [CER 05a] advise the maintenance of a narrow window if a link has a low or high PRR. On the other hand, the links with a medium PRR must be monitored with a larger window to enhance the estimation accuracy. Woo and Culler [WOO 03] designed the WMEWMA technique to smooth the PRR estimation. This technique is based on the EWMA filter that applies an exponential weight to give more importance to the newest or the oldest data. These estimators share the same drawbacks by assessing the link quality through the traffic of the downlink. Indeed, they cannot take into account losses of the uplink; this is why RNP-based estimators were suggested.

9.2.2.2. RNP-based

RNP-based estimators monitor both the downlink and uplink to assess the link quality. Cerpa et al. suggested the RNP (Required Number of Packet transmissions) estimator counting the average number of retransmissions required to deliver a packet [CER 05b]. The protocol requires the use of an ARQ (Automatic Repeat reQuest) technique for counting the number of failed and succeed transmissions. The Expected Transmission Count (ETX) metric was designed by De Couto et al. [DEC 03a] and takes into account the delivery ratio (computed from the average number of transmitted packets successfully received) and the reverse delivery ratio (computed from the average number of successfully received ACKs) to assess the link quality. Unlike RNP, which uses data traffic (passive method), ETX has to monitor the link with an active monitoring technique.

9.2.2.3. Score-based

Score-based estimators combine multi-estimators in order to assess the link quality and determine the link state. Baccour et al. [BAC 10] designed a hybrid metric called F-LQE, based on a multi-estimator approach, each assessing the packet delivery ratio, the link asymmetry level, the link stability and the channel quality. These estimators are aggregated into a single metric following a fuzzy logic method. In addition, they implemented F-LQE into the Collection Tree Protocol (CTP) routing protocol and proved its effectiveness in wireless sensor networks [BAC 15]. The Holistic Packet Statistic (HoPS) metric suggested by Renner et al. [REN 11] incorporates four estimators, namely short term, long term, absolute deviation and trend estimation. However, an intrinsic problem of the use of this filter limits the agility of estimators. It also has the disadvantage of requiring a large amount of traffic to train the estimators and consequently increases the detection time of link state changes.

9.2.3. Discussion

Classical hardware-based estimators measure the signal quality to determine the reception state of the upcoming packet. Experiments have proven the inability of such metrics to provide a fine grain of link quality, since the correlation with the PRR is not deductible. Computed from successfully received packets, these estimators may overestimate the link quality by not considering lost packets. A novel type of estimator extracts and analyzes information retrieved from the decoding process. Even if they are more accurate than classical approaches, they require information retrieved from specific radio chips.

On the other hand, software-based estimators assess the link quality according to the application point of view, i.e. the successful packet reception ratio or packet transmitted. Unlike hardware-based estimators software-based estimators, especially RNP-based, are able to assess both parts of a link (uplink and downlink) to ensure a more reliable assessment. Experimental works have confirmed this observation. As a result, such estimators have been well used by routing protocols. Beside, score-based metrics provide a multi-faced assessment to obtain a reliable link quality. This state-of-the-art is summarized in Table 9.1.

9.3. Analysis of legacy estimation techniques

In this section, we address the issue concerning estimation windows of RNP-based estimators by focusing our attention on the fulfillment process and computation techniques. This lays the foundation for us to understand and analyze performances of current assessment techniques. We regard only active traffic monitoring where nodes monitor the links of their neighbors by broadcasting probe packets.

Since RNP-based estimators assess both sides of a link, the quality assessment relies on two information sources. Indeed, ETX-like estimators compute two ratios: (i) df counting the number of packets successfully received by a neighbor and (ii) dr counting the number of received packets from a neighbor. Figure 9.2 shows the link monitoring scheme of ETX-like estimators. Several techniques have been retained to count received packets. Two kinds must be considered and are the main purpose of the next section.

Table 9.1. LQE review

Type1CategoriesNameTechniqueLocationLink2
HSignal propertiesRSSISignal StrengthReceiver
HSignal propertiesSNRSignal to Noise ratioReceiver
HSignal propertiesLQIError between the ideal constellation and the received signalReceiver
HDecoding eventCEPS, BLITZDSSS decoding processReceiver
HDecoding eventLSFIOFDM decoding processReceiver
SPRR-basedPRRAverageReceiver
SRNP-basedRNPAverageSender
SRNP-basedETXAverageReceiver
SScore-basedF-LQEFuzzy logicReceiver
SScore-basedHoPSHeuristicReceiver

Figure 9.2. Link monitoring scheme

9.3.1. Type of window

In order to monitor the link and to perform measures, estimators use a window mechanism. This forms a representative sample of the transmitted and received traffic. According to [DEC 03a] and [QUA 11], samples can be built from temporal or sequential information.

9.3.1.1. Temporal

Temporal information was introduced by De Couto et al. [DEC 03a]. The df ratio is computed from the number of probe packets received by a neighbor. To this end, nodes must periodically exchange the number of packets received from the neighbor. The computation of the df ratio is detailed in the following equation:

[9.1]

Count(tw, t) is a function counting probe packets received during a period w and w/t is the number of probe packets which should be received. The freshness of the df ratio relies on the fixed period w determining the sample size. The main drawback of this approach is the exchange of the df ratio. If a probe packet is lost, a receiver cannot determine whether its probe packet has been successfully transmitted. As a result, it assumes the transmitted packet as lost, even if it has been successfully received. Since the df ratio is exchanged periodically through probe packets sent, nodes cannot exchange their current values. Indeed, nodes send the df ratio corresponding to the last exchange and not the current one.

9.3.1.2. Sequential

Rather, sequential information provides an affordable solution to determine ratios. To this end, a sequence number is used as an ID and is assigned exclusively to probe packets. A novel and fresh approach has been developed in [QUA 11], which is actually implemented in the Better Approach To Mobile Ad-hoc Networking (BATMAN) routing protocol. The proposed approach avoids the exchange of the df ratio by changing the retransmission policy, where only the emitter node is responsible for the computation of ratios. This is computed from the assumption that df × dr represents the ratio that a transmission is successfully received and acknowledged. According to Figure 9.3, each probe packet is retransmitted by the receiver in order for the originator of the probe packet to compute the delivery ratio.

Figure 9.3. Novel assessment of the df ratio

With this approach, nodes are able to assess the current link quality, since information about the two ratios is acquired within the current period. On the other hand, the number of transmission increases, because each probe packet must be forwarded. Avoiding an infinity retransmission is ensured with the retransmission policy. Probe packets have to contain three specific fields: the node’s address that creates the probe packet (AddrOrign), the address of the last forwarder (AddrPrev) and the sequence number (SN). The retransmission policy is described in algorithm 1.

9.3.2. Window analysis

In this section, we address the problem of the window size since it impacts both the convergence time and the accuracy of the estimator. We focus our attention on sequential windows, fulfilled periodically with probe packets. The filling of the window depends on its size and the sending period. However, reducing the sending period has a negative impact on the network performance, since it reduces the bandwidth allocated to data. To this end, the only way to change the convergence time of a window is to adapt its size.

The size impacts the time to fulfill the window, so it determines the time to declare a link with a maximum quality or detect a disruption. In this section, we investigate the computational techniques that rely on a window mechanism. We focus our attention on the assessment technique used by ETX and show the benefits and the limits of such a method. The quality assessed by ETX takes into account both the df and dr ratios and is computed as . Figure 9.4 shows the impact of the mean filter on the convergence time to declare a link with a maximal quality. A larger size implies a longer time to declare a link with a maximal quality, since it increases the time to fulfill the window. Concerning the stacked density function, we observe that an estimator with a larger window size is able to assess the link quality with more values. However, the distribution function is more situated on the left, this means that more values to describe low qualities (< 50) are obtained.

Figure 9.4. ETX: link emergence study

The window size also determines the number of observations required to assess a link as being at its maximum quality. It also impacts the estimation accuracy, since it determines the observation number of the sample. We consider each attempt transmission as a Bernoulli trial. Thus, the reception state of a packet can be described as a binary value, meaning its successful reception or its loss. Therefore, the sample can be described as a binary word whose length is the sample size. Determining the estimation accuracy can be done with combinatorial analysis. Since ETX uses the mean filter to compute the two ratios, the ranking is not considered and the sample can be seen as a combination with allowed repetitions. Let n describe the binary reception state and k the sample size, the total number of combinations is described by:

[9.2]

With a larger window size, ETX is able to assess the link quality with more values than a small window size. However, as shown in Figure 9.4, this increases the convergence time of the estimator. We have also observed, on the density function plot, the inequality distribution of estimated values, with most situated on the left (lowest values). As a result, ETX is not able to be both reactive and accurate, because it uses a fixed window size.

9.4. The F-ETX metric

Several efforts have been made to develop trustworthy link quality estimators. Most of them have been developed and tested in Wireless Sensor Networks (WSN)s. In section 9.3, we have observed that for an estimator a static window size implies a trade-off between accuracy and reactivity. Their effectiveness is limited in mobile environments, since they do not deal with the short span of link lifetimes. Besides, mobile nodes can evolve in different environments with specific mobility patterns, which leads to unpredictably disturb the radio channel.

A novel metric called F-ETX has been proposed to deal with the problem of the link quality assessment in mobile networks. The metric is composed of four estimators, each assessing a specific feature of the link and allows a multi-faced assessment. The metric is able to assess the link quality and determine the link state in order to prevent future events, such as a link disruption. F-ETX avoids the problems related to the use of static window size for traffic monitoring by using a dynamic management of the size. We regard the packet loss as a relevant event to reduce or extend window size. To this end, the metric owns two algorithms to manage the window size, each one assigned to a specific job: size reduction and size growth.

9.4.1. Window management algorithms

A relevant challenge for LQEs is to provide a quick and an accurate assessment in an unknown and dynamic environment. As depicted in the last section, current solutions imply a trade-off. F-ETX tackles all suggested estimators from all of the state-of-the-art by bringing a dynamic management of the window size. Its main insight is to automatically adapt the accuracy and the reactivity of the estimator. Information concerning the packet losses has been retained as the most relevant to achieve a window size fitting. To this end, F-ETX implements two tight algorithms. The first one is dedicated to the reduction of the window size, in order to improve the estimator reactivity. The second one is able to extend the window size, in order to increase the assessment accuracy.

9.4.1.1. Window size reducing algorithm

With the reduction of the window size, the algorithm is able to increase the reactivity of the estimator but also decrease the assessment accuracy. One of the most important features is to detect a link disruption as soon as possible. Let a packet p P be a finite whole of observed packets such as P = {p0, p1, p2, , pn−1}, with n being the number of observation. Each observed packet p is labeled according to its reception state, such as a label L ∈ [0, 1], where L ← 0 indicates a loss and L ← 1 a reception. The number of packet considered as received, a, and lost, ā, are computed as follows:

[9.3]
[9.4]

Thus, the window size n is reduced according to the number of packet considered lost:

[9.5]

The key idea is to increase the reduction process, in accordance with the packet loss. If packet losses are sporadic, n is slightly reduced, otherwise, n is significantly reduced. Implementing this algorithm requires some extra considerations. To support traffic monitoring through a window mechanism, packets must contain a sequence number in order to be identified. Since F-ETX is based on an active monitoring, the sending period is used to determine whether a packet can be declared as received or lost. Figure 9.5 shows a study case, where the last expected packet is lost (Sequence Number N#8).

Figure 9.5. Illustration of the window size reduction algorithm

9.4.1.2. Window size growing algorithm

The following algorithm is able to extend the window size in order to enhance the assessment accuracy. It is triggered after a packet loss and as soon as a novel packet is received. The algorithm proceeds in two steps. The first one is the recovery phase, in which the algorithm extends the window size for each new received packet. The goal is to recover the initial window size before the packet loss. The second one is the link stability sensing, in which the algorithm gropes for the extension of the window. The algorithm tries to extend the window according to the link stability in order to provide a more accurate assessment. The switch between the recovery phase and the link stability sensing phase is triggered by the threshold Th. Its value is set to the window size before the first packet loss. Until the window size is lower than Th, the widow size is incremented by one for each new received packet. Indeed, the algorithm tries to recover the last window size before the disruption. Then, in the recovery phase, the window (W) is increased or shifted (left) according to a dedicated counter C, as described in algorithm 2.

The reduction algorithm attempts to detect the disruptions at the earliest by reducing the size of the tight couple of the windows. When the link gets back, the second algorithm tries to recover the initial window size before the last disruption. Upon reaching their initial size, the algorithm gropes for the increase of the window size. During this stage, the size is progressively increased until reaching the maximum window size.

9.4.2. Multi-assessment approach

The link quality assessment aims to find the highest throughput link. Renner et al. [REN 11] have pointed out the problem of such a method for comparing links (see Figure 9.1). Rather, Renner et al. and Baccour et al. suggested a metric to be capable of assessing multi-features of a link. These approaches have been developed for WSNs and do not have the required ability to be deployed in mobile networks. Even if previous algorithms enhance the reactivity and the accuracy of the link quality assessment, this is not sufficient. That is why F-ETX implements four estimators, two dedicated to the link quality assessment and another dedicated to determining the link state.

9.4.2.1. Link quality

The expected probability that a message is successfully received and acquitted is df × dr. If we consider a packet transmission as a Bernoulli trial (success or fail), the link quality (χLQ) estimation is determined as follows:

[9.6]

9.4.2.2. Link quality trend

This indicator tracks the course of the link quality by computing the variation between the current and the previous estimation To provide a long-term estimation, this result is averaged with an EWMA filter:

[9.7]

the coefficient β influences the sensitivity of the estimator. Choosing a small β value is advisable to achieve a long-term estimation. Note that two successive nulls χLQ indicate a disruption and reset the link quality trend estimator.

9.4.2.3. Link stability estimation

We observed that a fine analysis of the window content provides link stability information. Let a binary state [0, 1] representing the reception state of an excepted packet in a window. We denote Wmax as the maximum window size, Wn the current window size and Wi the ith element in the window. The windows maintained to compute the df and dr probabilities are respectively denoted as Wdf and Wdr. The link stability indicator is computed with an EWMA filter, taking into account the absolute Ξ and the relative stability ξ:

[9.8]

The absolute estimation (Ξ) computed from the maximum window size (fixed value) represents the absolute level of stability of the link. The relative estimation (ξ) computed from the current window size (dynamic value) represents the relative stability. This third estimation gives the level of the link stability according to the current window size. This information is useful, since, for the same absolute value, the relative link estimation gives an additional assessment taking into account losses which occurred recently. Both absolute and relative information are suitable for assessing the link stability. They must be taken into account in the same way. Hence, we advise a γ value fixed at 0.5.

9.4.2.4. Unidirectional link level

This last estimator deals with the detection of bidirectional links becoming unidirectional. Current approaches like F-LQE with the ASL estimator track the difference between the uplink and downlink reception rates. Such a method becomes inefficient if the link has a short life time or experiences a high level of packet losses. In this case, windows are not sufficient trained to give a trustworthy estimation. Our method overcomes this limitation by measuring the variation of the up and downlink reception ratios. This makes it independent of the window size and does not require any training period. Let W be a window and its size at time t. The variation of the reception ratio provided by the window W at time t is denoted as . The indicator is given by:

[9.9]

To give a tendency, we advise a λ value fixed at a high value. A link may become unidirectional (e.g. nodes with different transmit power level) if the assessment becomes negative.

9.4.3. Routing integration framework

In this section, we describe the framework designed to integrate all estimators into a routing protocol. Each estimator assesses a specific property of a link in order to provide information on its quality and its state. It is a key concept for addressing issues of routing protocols. Current metrics using multi-estimators such as F-LQE [BAC 10] and HoPS [REN 11] compute a scored quality link estimation in order to provide a single value. Even if Baccour et al. [BAC 15] have implemented F-LQE in the CTP routing protocol, there are no silver bullets to compute an ultimate single estimation including all assessment provided by estimators.

To solve this issue, we propose a framework integrating each estimation into the routing process. Indeed, each estimator is related to the routing table in order to indicate the link quality and inform us about the link state event occurrence. Based on an active monitoring, each estimation is computed after the reception of a probe packet. Then, they assign their assessment to the associated entry into the routing table. The proposed framework is illustrated in Figure 9.6, including the routing protocol and our metric.

Figure 9.6. Routing framework

Since we consider the routing table as the intermediary part between the metric and the outing protocol, each piece of information is stored in the associated entry in the routing table. Then, the routing algorithm selects the best link according to its quality and its state. Thus, we need to define how the quality is assessed and which state is stored in the routing table. In addition, we detail how a routing algorithm may interpret information stored in the routing table.

9.4.3.1. Local link evaluation

As pointed out, F-ETX includes four estimators, namely a short-term link quality, long-term link quality, stability estimator and unidirectional link indicator.

As shown in Figure 9.1, it becomes a major concern when two links are close in quality but have opposite trends. We propose a novel link quality assessment merging both the short and the long term:

[9.10]

Taking into account both the short and the long-term estimation makes it possible to penalize the short-term estimation according to its current trend. If a couple of links have a close link quality, the metric is able to select the best one according to its quality trend.

The stability indicator determines if a link is fitted to support data transmission. This information is used to declare a routing entry as enabled or disabled. Indeed, a null estimation brands a routing entry as disable even if the quality is not null. Thus, our estimator also indicates two possible states of the link stability:

  1. χStab = 0: disable routing entry;
  2. χStab > 0: enable routing entry.

The unidirectional link indicator detects transient loses which turn a bidirectional link into an unidirectional link. Besides, persistent unidirectional links can be detected with a direct observation of the dr ratio indicating the number of packets retransmitted by a neighbor. Thus, our indicator is able to detect the unidirectional property of the link:

  1. Up: persistent unidirectional link;
  2. Ut: transient unidirectional link.

9.4.3.2. Routing in praxis

When a packet is received, the routing algorithm is responsible for routing the packet to the destination by selecting the best link. This selection process is performed by selecting the corresponding entry in the routing table. That is why the protocol ranks, for each destination node, the best potential neighbor according to the link quality (χLQ+χTrend). Then, the protocol inspects the stability indicator to determine whether a route is declared available or disable. In the disable case, the algorithm selects the next route and restarts the same approach. At the end, the protocol checks if the link is unidirectional. In the case of a transient state, the route is selected, else the routing algorithm looks for another route.

9.5. Simulation settings

We investigate the performance of the F-ETX metric into two rounds. In the first one, we lead to a performance evaluation between the F-ETX and two current multi-estimators, F-LQE and HoPS. In the second one, we observe the impact of the F-ETX on the routing performance, if it is used as the principal metric. In order to lead our investigation, we define two scenarios, including a realistic mobility pattern and a real signal propagation environment, and simulated with ns-3 [RIL 10].

9.5.1. First scenario

The first scenario is used in the performance evaluation of the F-ETX, F-LQE and HoPS. In this scenario, 40 vehicles move in an urban area of 500m × 500m with a Manhattan mobility model 4 × 4. We set the mean speed of vehicles at 30km/h in order to simulate a high speed traffic. From [BEN 12], we fix the channel propagation parameters, with a Three Log Distance Loss Model as a shadowing model and Rayleigh’s model as a fast-fading model, to reproduce a realistic urban channel propagation environment. Table 9.2 details propagation environment carefully.

Table 9.2. Signal propagation parameter

PHY parameters
Tx/Rx power (dbm) 0
Gain of antenna (dB) 0
Power Detection Threshold (dbm) –96
MAC parameters
Standard 802.11g
Mode OFDM 6 Mpbs
Rate adaptation ARF
Propagation Loss Parameters
ThreeLogDistance
Exponent 0 2.5
Exponent 1 5
Exponent 2 10
Distance 0 1
Distance 1 75
Distance 2 114
Nakagami-m
Rayleight m = 1

9.5.2. Second scenario

The second scenario is used in order to observe the impact of the F-ETX on the routing performance. In this scenario, 50 vehicles move in an urban area of 1 km2 with a Manhattan mobility model 4 × 4. We set the mean speed of vehicles at 50 km/h, and limit the minimal speed at 30 km/h. Like in the first scenario, channel propagation parameters are detailed in Table 9.2, which details propagation environment carefully.

9.6. Simulation results

We now describe the results obtained by our experiments. As mentioned previously, we test our approach in a realistic urban environment. We explore the performance of each estimator of the F-ETX metric and its impact on the routing performance.

9.6.1. Performance of the multi-estimators

We investigate the performance and the robustness of all estimators of F-ETX. To this end, we compare the performance of our estimators and current metrics namely F-LQE [BAC 10] and HoPS [REN 11]. We set the parameters of each estimator according to [BAC 10] for F-LQE and [REN 11] for HoPS. We fix the parameters of F-LQE as follows. We set the coefficient of the WMEWMA filter used to compute the packet delivery ratio at 0.6. The assessment of the link quality and the link stability requires a history of PRR that we set at 30. A minimal history is maintained at 5 PRR until it reaches 30. For HoPS, we set the parameters as follows. Coefficients are respectively set to 0.9 and 0.997 and their short- and long-term estimations are initialized at 50% for new links. Finally, for F-ETX, we determine the parameters of EWMA filters by setting companion estimators called λ, β and γ to 0.9, 0.1 and 0.5 respectively.

Our main goal is to assess both the agility of estimators by observing their ability to track fluctuation and their accuracy and their robustness. We achieve both temporal and statistical evaluations. Through the temporal experiments, we observe the behavior of estimators in order to have an overview of their ability to assess the link property. We made also a statistical evaluation of estimators to measure their forecasting properties.

9.6.1.1. Temporal assessment

We observe a fast speed crossing wherein nodes are able to communicate within a few seconds (4s). Figure 9.7 shows the result of the first scenario.

Regarding the distribution of the dr and df , nodes are able to communicate within a few seconds (from 6s to 10s, while stochastic losses can be observed that result from a significant fading (Rayleigh) effect). The PRR computed over a history of packets declares the link disrupted at 15s, but the effective disruption occurs at 11s.

Concerning the F-LQE, Figure 9.7(b) shows the smoothed PRR (SPRR) evaluating the link quality and the link stability estimation (SF). Figure 9.7(c) shows the unidirectionality level of a link estimator (ASL). The SPRR follows the corresponding PRR (Figure 9.7) trace with a smoothing trend, but the estimator is clearly not reactive enough and detects the disruption too late. This results from the EWMA filter that provides more stability than reactivity to the estimator. The SF estimator detects that the link quality is changing at 11s, because the link is disrupted. However, the variation indicated by the estimator does not reflect a disruption case but only a slight variation of the link quality. The disruption can be clearly detected at the end with a more important value of the indicator. Regarding the ASL indicator, the variation of dr and df distribution introduces light fluctuations, indicating a low probability of having an asymmetric link.

Regarding estimators from HoPS (Figure 9.7(d) and (e)), we observed the slow convergence time of the short-term estimation; while a link is disrupted, the estimator declares the link quality as not disrupted. But the long-term estimator indicates a correct decreasing trend. Consequently, the EWMA filter is well used for the long-term estimation but is not suitable for a short-term estimation which also smooths the estimation. In the same way, the link quality trend and the variation indicators are affected by the long reactivity of the short- and long-term estimations and react too slowly when a disruption occurs.

The estimators of F-ETX are shown in Figure 9.7(f) and (g). In contrast with other LQEs, F-ETX is more reactive than the others and declares the link disrupted earlier (at 13s). The trend estimation indicates a degradation of the link quality via consecutive negative values. This is confirmed by the link stability estimator indicating a low level of stability and a decrease. We also observe that the stability estimator declares the link disrupted earlier than the link quality estimator (12s). Concerning the unidirectional indicator, it gives a positive value (at 10s) indicating that the link can be unidirectional.

Figure 9.7. Fast speed crossing

Figure 9.8. Statistical evaluation

9.6.1.2. Statistical analysis

While previous evaluations provide detail about the strength and weakness of LQEs, we extend our assessment with a statistical analysis of all the links available in the scenario.

We have observed that the link quality estimator of F-ETX is more reactive than F-LQE and HoPs. In this statistical study, we are focused on how this estimator can anticipate disruptions compared to the PRR solution based on a history of 5 packets. Figure 9.8 (a) shows that F-ETX is clearly the best solution for anticipating disruptions before the PRR solution. Since it is based on the dynamic window size, the metric is more reactive and tracks, link states change very well. In addition, F-ETX assesses both link directions, unlike a PRR solution that only evaluates the downlink.

The rest of the statistical analysis is made with the Mean Absolute Error (MAE) that measures the magnitude of the predicted estimation and the current outcome. A low score indicates a good prediction while a bigger value indicates a greater error between the prediction and the current value. The link quality trend is additional information that determines the current course of the link quality. Figure 9.8(b) shows the link quality trend of HoPs and F-ETX. We observe the better ability of our estimator to give the tendency of the link quality compared to HoPS, even if both of them are based on the link quality estimator and computed with an EWMA filter. Their ability to track the link quality course depends on the ability of the short-term link quality estimator. HoPS-ST suffers from lag with the use of the EWMA filter impacting the HoPS-LT. On the other hand, the link quality estimator from F-ETX is reactive but unstable. That is why, with the use of EWMA, the estimation is stabilized given a better long-term estimation than the HoPS-LT overestimating the tendency.

Figure 9.8(c) shows the unidirectional link estimator of F-LQE and F-ETX. During the simulation, any effective unidirectional links are present. The ASL estimation often makes a single reading of the reception ratio of the up and downlink different when high propagation disturbances are present. Our indicator adopts another strategy based on the variation between the up and downlink. As a result our estimation is more robust to disturbances and gives more accurate information about the potential of a bidirectional link becoming unidirectional.

Tracking link stability is an essential feature for detecting and differentiating transient and persistent links. We have compared in Figure 9.8(d) the variation of the value given by these estimators to the current variation observed from the delivery and forward ratios. F-ETX estimator gives the lowest MAE compared to the others. Because the HoPS indicator only tracks the variation between the HoPs ST and LT estimations, it is not really related to the link stability. For F-LQE, the estimation is based on a PRR history generating consecutive error predictions.

9.6.2. Performance of routing protocols

We investigate the impact of the F-ETX metric, when it is used as the metric. We have developed a simulation model retracing the behavior of the B.A.T.M.A.N. (Better Approach To Mobile Ad-hoc Networking) protocol. We have implemented the F-ETX metric into the routing protocol and define our metric as the main. We compare the performances of our modified protocol to a couple of protocols, such as OLSR (Optimized Link State Routing Protocol) and AODV (Ad hoc On Demand Distance Vector). We have retained these protocols, because they get routing information with a different approach, proactive for OLSR and reactive for AODV. In order to rank protocols, we regard two indicators. The first one is the Packet Delivery Ratio (PDR), which indicates the number of packets successfully delivered to a destination. The second one is the end-to-end delay bringing information on the time taken by a packet to be transmitted from a source to a destination.

9.6.2.1. Influence of the node number

We observe the impact of the node number present in the network on the routing performances. For this purpose, nodes transmit with a constant bit rate, UDP datagrams. We analyze six traffic patterns during the simulation period, which represent a total of 2688 bytes exchanged. Figure 9.9 shows the average PDR and the average end-to-end delay.

Figure 9.9. Influence of the node number

Our modified protocol is clearly the best one, since it presents the best performance compared to OLSR and AODV. Regarding the PDR, the node number has a great influence on the two protocols, but with contrasting effects. When the node number increases, the OLSR protocol gets better performances whereas the AODV protocol obtains less efficients performances. Regarding our protocol, the node number has some impact on its performance.

Concerning the end-to-end delay, expected proactive protocols, including OLSR and our protocol, get the minimum end-to-end delay compared to the reactive protocol, AODV. Since the two proactive protocols discover the network topology periodically, nodes are able to find the best as soon as data is required to be transmitted. However, reactive protocols like AODV trigger the route discovery as soon as data have to be transmitted. That is why the end-to-end increases, since this discovery phase introduces a delay.

9.6.2.2. Influence of the applicative throughput

We investigate the impact of the applicative throughput on the routing performance. We study scenarios with 20 and 50 nodes and fix the applicative throughput with different sending periods, 600, 300 and 150 ms in order to differently stress the routing path. Figure 9.10 shows the resulting PDR and end-to-end delay.

Concerning the PDR, the modified version of BATMAN gets the best ratio with a PDR ≥ 0.8. Even if the throughput of the application impacts all protocols, the modified BATMAN maintains the best performance. Concerning the end-to-end delay, as expected, proactive protocols have lower delay than the reactive protocol AODV. The end-to-end delay obtained by proactive protocols is close (< 2.7ms). Finally, the modified BATMAN protocol appears as the best one, since it has the best PDR ratio and a low end-to-end delay close to the OLSR delay.

Figure 9.10. Influence of the applicative throughput

9.7. Conclusion

The F-ETX has been proposed to overcome the intrinsic limitations of LQEs design for WSNs. To deal with the dynamic of vehicular networks, the metric relies on a dynamic window size. F-ETX is formed of four estimators, two dedicated to the link quality assessment and another two to the link state determination. The first couple assesses both the short and long-term link quality, and the other two determine if the link is stable and unidirectional. We have developed a framework in order to integrate each estimator into the routing process. To this end, a link is assessed both on its quality and its state.

We have investigated the performance of the F-ETX metric and its impact into a routing protocol, through a realistic simulation environment. Compared to other current multi-estimator solutions, our metric is more reactive and accurate and provides the best predictions. We have implemented the metric into a proactive routing protocol (BATMAN) and compare its performance to another proactive protocol (OLSR) and a reactive protocol (OLSR). Regardless of the node number and the application throughput, our modified BATMAN obtains the best results in terms of the packet delivery ratio and has a similar delay to the OLSR protocol.

9.8. Bibliography

[BAC 10] BACCOUR N., KOUBÂA A., YOUSSEF H. et al., “F-LQE: a fuzzy link quality estimator for wireless sensor networks”, Proceedings of the 7th European Conference on Wireless Sensor Networks (EWSN’10), pp. 240–255, 2010.

[BAC 12] BACCOUR N., KOUBÂA A., MOTTOLA L. et al., “Radio link quality estimation in wireless sensor networks: a survey”, ACM Transactions on Sensor Networks, vol. 8, no. 4, pp. 34:1–34:33, 2012.

[BAC 15] BACCOUR N., KOUBÂA A., YOUSSEF H. et al., “Reliable link quality estimation in low-power wireless networks and its impact on tree-routing”, Ad Hoc Networks, vol. 27, no. C, pp. 1–25, 2015.

[BEN 12] BENIN J., NOWATKOWSKI M., OWEN H., “Vehicular Network simulation propagation loss model parameter standardization in ns-3 and beyond”, Southeastcon, 2012 Proceedings of IEEE, pp. 1–5, March 2012.

[BIN 15a] BINDEL S., CHAUMETTE S., HILT B., “A novel predictive link quality metric for mobile ad-hoc networks in urban contexts”, Ad Hoc Networks: 7th International Conference, AdHocHets 2015, San Remo, pp. 134–145, September 2015.

[BIN 15b] BINDEL S., CHAUMETTE S., HILT B., “F-ETX: an enhancement of ETX metric for wireless mobile networks”, Communication Technologies for Vehicles: 8th International Workshop, Nets4Cars/Nets4Trains/Nets4Aircraft 2015, Sousse, pp. 35–46, May 2015.

[BOA 09] BOANO C.A., VOIGT T., DUNKELS A. et al., “Poster abstract: exploiting the LQI variance for rapid channel quality assessment”, International Conference on Information Processing in Sensor Networks, IPSN 2009, pp. 369–370, April 2009.

[CER 05a] CERPA A., WONG J.L., KUANG L. et al., “Statistical model of lossy links in wireless sensor networks”, IPSN 2005. Fourth International Symposium on Information Processing in Sensor Networks, pp. 81–88, April 2005.

[CER 05b] CERPA A., WONG J.L., POTKONJAK M. et al., “Temporal properties of low power wireless links: modeling and implications on multi-hop routing”, Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc ’05, New York, pp. 414–425, 2005.

[DEC 03a] DE COUTO D.S.J., AGUAYO D., BICKET J. et al., “A high-throughput path metric for multi-hop wireless routing”, Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, MobiCom ’03, New York, pp. 134–146, 2003.

[DEC 03b] DE COUTO D.S.J., AGUAYO D., CHAMBERS B.A. et al., “Performance of multihop wireless networks: shortest path is not enough”, ACM SIGCOMM Computer Communication Review, vol. 33, no. 1, pp. 83–88, January 2003.

[GAB 14] GABTENI H., HILT B., DROUHIN F. et al., “A novel predictive link state indicator for ad-hoc networks”, 2014 IEEE Global Communications Conference, pp. 149–154, December 2014.

[HEI 12] HEINZER P., LENDERS V., LEGENDRE F., “Fast and accurate packet delivery estimation based on DSSS chip errors”, INFOCOM, 2012 Proceedings IEEE, pp. 2916–2920, March 2012.

[IEE 16] IEEE, “IEEE Standard for Low-Rate Wireless Personal Area Networks (WPANs)”, IEEE Std 802.15.4-2015 (Revision of IEEE Std 802.15.4-2011), pp. 1–709, April 2016.

[LAI 03] LAI D., MANJESHWAR A., HERRMANN F. et al., “Measurement and characterization of link quality metrics in energy constrained wireless sensor networks”, Global Telecommunications Conference, 2003. GLOBECOM ’03. IEEE, vol. 1, pp. 446–452, December 2003.

[LIU 14] LIU T., CERPA A.E., “Data-driven link quality prediction using link features”, ACM Transactions on Sensor Networks, vol. 10, no. 2, pp. 37:1–37:35, January 2014.

[QUA 11] QUARTULLI A., C.L., “Client announcement and Fast roaming in a Layer-2 mesh network”, Technical Report #DISI-11-472, University of Trento, 2011.

[REN 11] RENNER C., ERNST S., WEYER C. et al., “Prediction accuracy of link-quality estimators”, Wireless Sensor Networks: 8th European Conference, EWSN 2011, Bonn, pp. 1–16, February 2011.

[RIL 10] RILEY G., HENDERSON T., “The ns-3 Network Simulator”, in WEHRLE K., GÜNES M., GROSS J. (eds.), Modeling and Tools for Network Simulation, Springer, Berlin, 2010.

[SPU 13] SPUHLER M., LENDERS V., GIUSTINIANO D., “BLITZ: wireless link quality estimation in the dark”, Proceedings of the 10th European Conference on Wireless Sensor Networks (EWSN’13), pp. 99–114, 2013.

[SRI 06] SRINIVASAN K., DUTTA P., TAVAKOLI A. et al., “Understanding the causes of packet delivery success and failure in dense wireless sensor networks”, Proceedings of the 4th International Conference on Embedded Networked Sensor Systems (SenSys ’06), New York, pp. 419–420, 2006.

[SRI 10] SRINIVASAN K., DUTTA P., TAVAKOLI A. et al., “An empirical study of low-power wireless”, ACM Transactions on Sensor Networks, vol. 6, no. 2, pp. 16:1–16:49, March 2010.

[WOO 03] WOO A., CULLER D., Evaluation of efficient link reliability estimators for low-power wireless networks, Report no. UCB/CSD-03-1270, EECS Department, University of California, Berkeley, 2003.

[ZAM 07] ZAMALLOA M.Z.N., KRISHNAMACHARI B., “An analysis of unreliability and asymmetry in low-power wireless links”, ACM Transactions on Sensor Networks, vol. 3, no. 2, 2007.

Chapter written by Sébastien BINDEL, Benoit HILT and Serge CHAUMETTE.