Vehicular Networks

Models and Algorithms

André-Luc Beylot, Houda Labiod, André-Luc Beylot, Houda Labiod

• Publisher: Wiley-ISTE
• Year: 2013
• Print ISBN: 9781848214897
• eBook ISBN: 9781118648735
• Edition: 1
• Topic: Technology & Engineering
• Subtopic: Automotive Transportation & Engineering
• Index: Technology & Engineering

Over the last few years vehicular networks have been receiving a lot of attention from academia, industry, standardization bodies, and the various transportation agencies and departments of many governments around the world. It is envisaged in the next decade that the Intelligent Transportation System (ITS) will become an essential part of our daily life. This book describes models and/or algorithms designed to investigate evolutionary solutions to overcome important issues such as congestion control, routing, clustering, interconnection with long-term evolution (LTE) and LTE advanced cellular networks, traffic signal control and analysis of performances through simulation tools and the generation of vehicular mobility traces for network simulations.
It provides an up-to-date progress report on the most significant contributions carried out by the specialized research community in the various fields concerned, in terms of models and algorithms. The proposals and new directions explored by the authors are highly original, and a rather descriptive method has been chosen, which aims at drawing up complete states of the art as well as providing an overall presentation of the personal contributions brought by the authors and clearly illustrating the advantages and limitations as well as issues for future work.

Contents

1. Introduction
2. Congestion Control for Safety Vehicular Ad-Hoc Networks
3. Inter-Vehicle Communication for the Next Generation of Intelligent Transport System: Trends in Geographic Ad Hoc Routing Techniques
4. CONVOY: A New Cluster-Based Routing Protocol for Vehicular Networks
5. Complementarity between Vehicular Networks and LTE Networks
6. Gateway Selection Algorithms in a Hybrid VANET-LTE Advanced Network
7. Synthetic Mobility Traces for Vehicular Networking
8. Traffic Signal Control Systems and Car-to-Car Communications

About the Authors

André-Luc Beylot is Professor in the Telecommunication and Network Department of the ENSEEIHT of IRIT-T, University of Toulouse in France.
Houda Labiod is Associate Professor at Telecom ParisTech in the INFRES (Computer Science and Network) Department, France.

Chapter 1

Congestion Control for Safety Vehicular Ad Hoc Networks

1.1. Introduction

In the highly dynamic vehicular environment, congestion control is essential, especially with regard to safety messages. Although a dedicated spectrum has been allocated for vehicular communications, the European 30 MHz Intelligent Transportation System (ITS) band (with a possible extension to 50 MHz) or the US 75 MHz Direct Short Range Communication (DSRC) band still represent a scarce resource and need efficient mechanisms in order to be optimally used under high vehicular density. In both Europe and the US, the allocated spectrum has been divided into 10 MHz channels. From these channels, one is known as the control channel (CCH) and it is used solely by road safety applications. The rest of the channels, called service channels (SCH), can be used by both safety and non-safety applications.

The number of proposed vehicular safety applications that could use direct vehicle to vehicle (V2V) communication is impressive [PAP 09]. However, at a close inspection, it can be noted that all these applications practically use the same information, coming from onboard sensors of neighboring vehicles: speed, acceleration, steering angle and location.

Considering this, the standardization bodies decided to add a supplementary layer between the applications and the transport protocol. The role of this layer, called message sublayer in the IEEE Wireless Access in Vehicular Environments (WAVE) architecture and facilities layer in the ETSI ITS terminology, is to keep an accurate image of the surrounding environment inside every vehicle and to provide applications with the desired information.

The facilities layer only needs two types of messages in order to achieve these objectives, called (in the ETSI ITS architecture) cooperative awareness message (CAM) and decentralized environmental notification message (DENM). CAMs are regular beacons, transmitted by every vehicle with a predetermined frequency, and containing details about the vehicle that might be relevant to its neighbors from a safety point of view. In addition, if a vehicle detects a potential hazard (e.g. a sudden brake) and considers that this information needs to be quickly disseminated to the other traffic participants, it transmits a DENM.

However, regardless of the scenario and message type, these safety messages are always transmitted in broadcast mode at the medium access control (MAC) layer. Even in the case when the transmitted information targets a certain geographical area (e.g. an electronic brake alarm is only of interest to vehicles traveling in the same direction as the transmitter and situated behind it), the message is still broadcast and the filtering happens at the facilities layer, as described by the ETSI framework [EUR 10].

The broadcast nature of the CCH in vehicular ad hoc networks (VANET) is an essential property that distinguishes it from other IEEE 802.11-based networks. As a matter of fact, the numerous studies on the distributed coordination function (DCF) implementing MAC mechanisms in IEEE 802.11 usually focus on unicast traffic, and broadcast messages are only considered for control purposes. Oliveira et al. [OLI 09] quantify the influence of broadcast traffic on the performance of IEEE 802.11 networks, and they find out that the effect of broadcast messages becomes significant when the proportion of broadcast traffic is higher than 50%. In this scenario, the behavior of the network largely deviates from what is predicted by classic DCF models. However, the authors consider this situation quite unreal and they do not investigate the issue further.

Another important characteristic of safety messages comes from the limited lifetime of CAMs. As these beacons are produced periodically by the facilities layer, there is a certain probability that they can expire before the MAC layer has the opportunity to transmit them. When a CAM is waiting for the IEEE 802.11 back-off timer to expire, and the next beacon also arrives in the transmission queue, the first message has to be dropped, as its transmission would only disseminate outdated information to its neighbors. This property, rarely taken into consideration in VANET studies, has a significant effect on the optimal value of different MAC layer parameters.

The IEEE 802.11p amendment [THE 10] is the preferred MAC technology in both the IEEE WAVE and the ETSI ITS architectures. IEEE 802.11p radios can communicate at a distance of 1 km. In a simple scenario, with a two-lane road in both directions and an average inter-vehicular distance of 50 m (a medium density highway), the number of one-hop neighbors reaches 160 vehicles. This is clearly a more challenging environment than the classic Wireless Local Area Network (WLAN), with a central access point and no more than 10–20 nodes. The MAC layer protocol, therefore, needs solutions for this congested environment to achieve scalability.

Congestion control mechanisms received a lot of attention from the VANET research community and the most relevant studies in this area are summarized later. The standardization bodies also recognized the importance of a decentralized congestion control framework for V2V safety communications, and ETSI published a series of technical specifications in this area in July 2011 [EUR 11]. In the US, the Society of Automotive Engineers (SAE) is also developing a standard with similar objectives, SAE J2945.1, currently in a draft phase. SAE J2945.1 is expected to be integrated into the WAVE architecture as a complement for the different IEEE standards.

In this chapter, five different approaches for MAC layer congestion control are discussed. In section 1.2, beaconing frequency adaptation is presented that reduces the number of transmitted safety messages in a dense network, speculating the relationship between high density and reduced speed in vehicular traffic. In section 1.3, increased data rates can be achieved by using more complex modulations and result in a lower occupancy of the CCH. Other proposals form the object of section 1.4, which are based on the fact that transmission power control has an important impact on the number of hidden nodes, and can increase the spatial reuse and hence the channel capacity, in a congested network. In section 1.5, the fourth element, the minimum contention window (CWmin), is analyzed, a parameter with a major importance for collision probability in an IEEE 802.11 network. Finally, the role of the physical carrier sense in congestion control is highlighted in section 1.6.

1.2. Beaconing frequency

The most obvious solution for controlling the channel load in a congested environment is to reduce the number of transmitted messages. This can be achieved in a straightforward manner in vehicular networks by adapting the frequency of the safety beaconing. However, such an adaptive mechanism should be designed carefully because sending less messages can easily have the effect of damaging the performance of safety applications instead of improving it.

In this context, Fukui et al. [FUK 02] proposed transmitting a CAM every time the vehicle travels a certain distance instead of using a regular time interval. According to a fundamental relationship from traffic theory, the mean speed decreases when the vehicular density increases, thus the consequence of this approach would be that nodes would reduce the beaconing frequency in a dense network where they would travel at low speeds. However, a basic example for which this solution fails is that of a vehicle waiting to make a left turn in normal traffic. Because the vehicle would need to stop, the adaptive mechanism would practically turn off the beaconing transmission, making an application like the left turn assistant practically unusable. Therefore, as stationary vehicles or low speeds are not always the consequences of high vehicular densities, such an approach cannot be efficiently used in a real scenario.

As a part of the California PATH program, Rezaei et al. [REZ 07] take a more complex approach, where vehicles run an estimator to calculate the position of each one-hop neighbor based on the already received messages. The same estimator is used by the node to predict its own position, as it would be calculated by its neighbors. When the difference between the prediction and the actual location becomes larger than a predefined threshold, the node transmits a safety beacon. The problem with this solution is that it is efficient in the predictable free-flow traffic, but not in a congested scenario where the acceleration is highly variable. Moreover, this self-estimator approach does not take into account that the error at some of the neighbors might be considerably different because some of the transmitted beacons could be lost. To solve this problem, Huang et al. [HUA 10] further develop this idea using the packet error ratio (PER) measured by a node to predict the losses encountered by its neighbors. Still, measuring a PER in a vehicular network without being able to detect collisions or use feedback from the receivers is not a straightforward task.

Seo et al. [SEO 10] make an analogy between the safety beaconing and the coupon collector problem. The mechanism they design relies upon nodes piggybacking acknowledgments (ACKs) for the received beacons in their own safety message. Every received ACK would further delay the transmission of the next CAM, reducing the beaconing frequency. However, the introduced overhead would be significant, especially in a dense network (a 4 byte ACK for 50 one-hop neighbors would result in 200 extra bytes for every safety message). It is also unclear if this approach would be compatible with a security framework based on changing pseudonyms, like the approach currently proposed by the ETSI ITS architecture [PAP 08], because the ACK would need to include the identifier of the sender and most probably a sequence number for the acknowledged message.

Adaptive Traffic Beacon (ATB) is a solution/mechanism/ approach proposed by Sommer et al. [SOM 11], where the beaconing frequency is calculated based on two metrics: the channel quality and the message utility. The idea is to transmit only the most important messages in a congested network, reducing the offered load. Nevertheless, the channel quality is very sensitive to the number of collisions, which implies that the nodes are somehow supposed to detect such events, clearly a difficult task in a broadcast environment [STA 12]. Moreover, while different utility factors could help differentiate between CAMs and DENs, safety beacons would be difficult to prioritise, as they belong to the same message class. Finally, ATB increases the beaconing period to a mean of 3.6 s, clearly a value that does not comply with the delay requirements of most safety applications, which vary between 100 ms and 500 ms [PAP 09].

For more details on adaptive beaconing solutions, the reader is referred to the very comprehensive review paper by Schmidt et al. [SCH 10]. To conclude, while reducing the beaconing frequency is a powerful tool in congestion control, the consequences of this adjustment on every safety application should be taken into account. However, road safety applications will most likely not be standardized, and addressing the constraints imposed by proprietary solutions is a difficult task.

1.3. Data rate

The standards from the IEEE 802.11 family provide multi-rate capability at the physical layer, but without specifying a particular approach for data rate adaptation. In wireless communications, a more complex modulation results in a higher data rate, but it also requires a higher signal-to-noise ratio (SNR) at the receiver in order to be correctly decoded. In the continuous fight for increased bandwidth, the search for an efficient data rate control solution in the very lucrative WLAN industry stimulated the research in this area, and two main classes of mechanisms have been designed.

The solutions in the first class are based on their choice for a certain modulation and coding rate on the success or failure of previously sent messages. For example, the Robust Rate Adaptation Algorithm (RRAA), proposed by Wong et al. [WON 06], calculates the frame loss ratio in a short time window and compares this value with two predefined thresholds. Too many losses determine a reduction in data rate, while a high percentage of successful transmissions results in the choice of a more complex modulation. The second type of mechanisms are based on feedback from the receiver regarding signal quality. A representative example in this class is receiver-based auto rate (RBAR), described by Holland et al. [HOL 01]. RBAR relies upon the idea of receivers measuring the channel quality by analyzing the Request To Send (RTS) message and calculating the highest achievable data rate based on the channel conditions. This information reaches the transmitter through the Clear To Send (CTS) message and the best modulation is set for the data frame.

The applicability of mechanisms from the two classes discussed above in a unicast vehicular network is studied experimentally by Camp and Knightly [CAM 08]. They show that, because of the highly variable vehicular channel, decisions based on historical data are not accurate in this environment, while the SNR-based mechanisms need to be trained in the target geographical region in order to cope with the short coherence time (around 300 μs when other vehicles are also present on the road).

In broadcast safety communications, solutions using feedback from the receivers are clearly unsuitable, therefore the data rate adaptation mechanisms proposed for vehicular safety messages follow the classic path of algorithms based on historical data. Mertens et al. [MER 08] use RRAA in their simulation study, showing a significant improvement in performance when compared with regular IEEE 802.11p. Nevertheless, they do not address the problem of computing the frame loss ratio in a VANET. A more innovative approach is proposed by Ruffini and Reumerman [RUF 05], building on the correctly received CAMs to create a map of the average path loss at different receivers and use this map to estimate th...

Table of contents

• Cover
• Contents
• Title Page
• Copyright
• Introduction
• Chapter 1: Congestion Control for Safety Vehicular Ad Hoc Networks
• Chapter 2: Inter-Vehicle Communication for the Next Generation of Intelligent Transport Systems: Trends in Geographic Ad Hoc Routing Techniques
• Chapter 3: CONVOY: A New Cluster-Based Routing Protocol for Vehicular Networks
• Chapter 4: Complementarity between Vehicular Networks and LTE Networks
• Chapter 5: Gateway Selection Algorithms in Vehicular Networks
• Chapter 6: Synthetic Mobility Traces for Vehicular Networking
• Chapter 7: Traffic Signal Control Systems and Car-to-Car Communications
• List of Authors
• Index