Adaptive Mechanisms to Improve Message Dissemination in Vehicular Networks

Contents

1 Motivation, Objectives, and Organization of the Thesis
1.1 Motivation
1.2 Objectives of the Thesis
1.3 Organization of the Thesis

2 Background on Vehicular Networks and Warning Message Dis­semination
2.1 Introduction
2.2 Vehicular Networks
2.2.1 Vehicular ad hoc networks (VANETs)
2.2.2 Characteristics and Applications of VANETs
2.3 Warning dissemination process
2.3.1 Existing Broadcast Message Dissemination Schemes
2.3.2 Classification of the Dissemination Schemes
2.4 Simulation Environment, Methodology, and Metrics
2.5 Summary

3 Real-Time Density Estimation
3.1 Introduction
3.2 Related Work
3.3 Real-Time Vehicular Density Estimation
3.3.1 Phase 1: Features of the Cities Studied
3.3.2 Phase 2: Counting the Number of Beacons Received
3.3.3 Phase 3: Density Estimation Function
3.3.3.1 Time Period Analysis
3.3.4 The Concept of Street
3.4 Validation of Our Proposal
3.5 Comparing Our Proposal with a Beacons-Based Density Estimation
3.6 Summary

4 RTAD: Real-Time Adaptive Dissemination System
4.1 Introduction
4.2 Related Work
4.3 Simulation Environment
4.4 RTAD: Analysis of the Optimal Broadcast Scheme
4.4.1 Broadcast Schemes Used
4.4.2 Metric 1: Percentage of Informed Vehicles
4.4.3 Metric 2: Messages Received per Vehicle
4.4.4 Optimal Broadcast Selection Algorithm
4.5 RTAD: Real-time Adaptive Dissemination System for VANETs
4.6 RTAD Performance Evaluation
4.6.1 RTAD vs. Static Dissemination Schemes
4.6.2 RTAD vs. Adaptive Dissemination Schemes
4.7 Summary

5 Topology-based Broadcast Schemes for Urban Scenarios Target­ing Adverse Density Conditions
5.1 Introduction
5.2 Related Work
5.2.1 Low Density Conditions
5.2.2 High Density Conditions
5.3 Dissemination Schemes Proposed
5.3.1 Junction Store and Forward (JSF)
5.3.2 Neighbor Store and Forward (NSF)
5.3.3 Nearest Junction Located (NJL)
5.4 Simulation Environment
5.5 Simulation Results
5.5.1 Performance Evaluation in Low Vehicle Density Scenarios
5.5.2 Performance Evaluation in High Vehicle Density Scenarios
5.6 Summary

6 Lessons Learned and Comparison of Existing Broadcast Dissem­ination Schemes
6.1 Introduction
6.2 Overall Classification of Warning Dissemination Messages Including our Proposed Schemes
6.3 Parameters Used to Assess the Performance of Existing Broadcast Dissemination Schemes
6.4 Simulation Environment
6.5 Simulation Results
6.6 Summary

7 Conclusions, Publications, and Future Work
7.1 Publications Related to the Thesis
7.1.1 Journals
7.1.2 Indexed Conferences
7.1.3 International Conferences
7.1.4 National Conferences
7.2 Future work

List of Algorithms

1 Optimal Broadcast Selection

2 RTAD Implementation

List of Figures

2.1 Example of a VANET [DoT14]

2.2 Traffic safety applications of VANETs

2.3 Comfort and commercial applications of VANETs

2.4 weighted p-persistence dissemination scheme example [WTP+07]

2.5 TLO dissemination scheme working flowchart [SP08]

2.6 APAL dissemination scheme working algorithm [SPC09]

2.7 eSBR dissemination scheme working algorithms [MFC+10]

2.8 eMDR dissemination scheme working flowchart [FGM+ 12b]

2.9 ATB dissemination scheme working flowchart [STD11]

2.10 SCB dissemination scheme working flowchart [SL12]

2.11 DV-CAST dissemination scheme working flowchart [TWB10]

2.12 UV-CAST dissemination scheme working flowchart [VTB11]

2.13 FDPD dissemination scheme working algorithm [STC+06]

2.14 Venn diagram classifying the broadcast dissemination schemes pre­sented in Section 2.3.1 according to the dissemination policy adopted

2.15 Example of visibility in RAV

3.1 Scenarios used in our simulations. Fragments of the cities of: (a)

Rome (Italy), (b) Rio de Janeiro (Brazil), (c) Valencia (Spain), (d) Sydney (Australia), (e) Amsterdam (Netherlands), (f) Madrid (Spain), (g) San Francisco (USA), and (h) Los Angeles (USA)

3.2 Number of beacons received when varying the vehicular density

3.3 3D representation of our density estimation function

3.4 Number of beacons received per vehicle when varying the time pe­riod and the city roadmap when simulating: (a) 100 vehicles-km-2, and (b) 200 vehicles-km-

3.5 Different criteria when counting the number of streets

3.6 Comparison between simulated and estimated average results

3.7 Absolute error histogram

3.8 Graphical comparison between simulated and estimated results for each function

4.1 Scenarios selected in our simulations. Fragments of the cities of: (a) Rome (Italy), (b) Valencia (Spain), (c) Sydney (Australia), (d) Am­sterdam (Netherlands), (e) Los Angeles (USA), (f) San Francisco (USA), and (g) Madrid (Spain)

4.2 Comparison of different dissemination schemes for VANETs: (a) eSBR, (b) eMDR, and (c) NJL

4.3 Percentage of informed vehicles in San Francisco for: (a) 25, and (b) 100, vehicles/km2, as well as in Valencia for: (c) 25, and (d) 100 vehicles/km

4.4 Percentage of informed vehicles in San Francisco for: (a) 150, and (b) 250 vehicles/km2, as well as in Valencia for: (c) 150, and (d) 250 vehicles/km

4.5 Number of messages received per vehicle when varying the broad­ cast scheme and the vehicular density in: (a) San Francisco and (b) Valencia

4.6 Details of our Real-time adaptive dissemination system

4.7 Simulation results and vehicle density estimation in San Francisco and Valencia

4.8 Broadcast scheme used by each vehicle in Sydney when simulating 150 veh./km2 at: (a) 1 s., and (b) 60 s. after simulation start, respectively. The eMDR is represented with filled dots, and the NJL with empty squares

4.9 Broadcast scheme used by each vehicle in Santiago de Chile when simulating 100 veh./km2, 30 s. after the simulation start. The eMDR scheme is represented with filled dots, and the NJL scheme with empty squares

4.10 Informed vehicles (Pinf ) and Messages received (Mrecv) when vary­ing the vehicle density and the city roadmap: Amsterdam ((a) and (d) ), Los Angeles ((b) and (e)), and Sydney ((c) and (f))

4.11 Informed vehicles (Pinf ) and Messages received (Mrecv) when vary­ing the vehicle density and the city roadmap: Amsterdam ((a) and (b) ), Los Angeles ((b) and (c)), and Sydney ((c) and (d))

5.1 JSF dissemination scheme working flowchart

5.2 NSF dissemination scheme working flowchart

5.3 NJL dissemination scheme working flowchart

5.4 Maps of: (a) Valencia and (b) San Francisco used in the simulations

5.5 Percentage of informed vehicles in Valencia for: (a) 10, (b) 20, and (c) 30 vehicles/km2, as well as in San Francisco for: (d) 10, (e) 20,and (f) 30 vehicles/km

5.6 Number of messages received per vehicle under low vehicle density conditions in: (a) Valencia and (b) San Francisco

5.7 Percentage of informed vehicles in Valencia for: (a) 300, (b) 400, and (c) 500 vehicles/km2, as well as in San Francisco for: (d) 300, (e) 400, and (f) 500 vehicles/km

5.8 Number of messages received per vehicle under high vehicle density conditions in: (a) Valencia, and (b) San Francisco

6.1 Venn diagram classifying the broadcast dissemination schemes stud­ied according to the dissemination policy adopted including our proposed schemes

6.2 Maps of: (a) San Francisco, and (b) Valencia used in our simulations

6.3 Percentage of informed vehicles and warning notification time in San Francisco for: (a) 25 and (b) 100 vehicles/km

6.4 Percentage of informed vehicles and warning notification time in Valencia for: (a) 25 and (b) 100 vehicles/km

6.5 Number of messages received per vehicle in San Francisco for: (a) 25 and (b) 100 vehicles/km

6.6 Number of messages received per vehicle in Valencia for: (a) 25 and (b) 100 vehicles/km

List of Tables

3.1 Map features

3.2 Parameters used for the simulations

3.3 Average percentage difference with respect to the mean value

3.4 Proposed equation coefficients

3.5 Absolute error when varying the time period

3.6 Number of streets obtained depending on the criterion used

3.7 Density estimation error

3.8 Beacons-only functions’ coefficients

3.9 Comparison between our SJ Ratio and the Beacon-based density estimation approaches

4.1 Map features

4.2 Parameter settings in the simulations

4.3 Simulation results for 100 vehicles/km2 in Valencia

4.4 Broadcast Scheme Selected According to our Optimal Broadcast Selection Algorithm

4.5 Performance of the different dissemination schemes when varying the vehicle density and the city roadmap

4.6 Performance of the different adaptive dissemination systems when varying the vehicle density and the city roadmap

5.1 Performance of the JSF variations under low density conditions in Valencia

5.2 Performance of the JSF variations under low density conditions in San Francisco

5.3 Parameter settings in the simulations

5.4 Average time necessary to inform 60% of the vehicles

5.5 Performance of the different dissemination schemes under high den­sity conditions

6.1 Parameters used in the simulations to evaluate the different broad­cast schemes

6.2 Parameter settings in the simulations

Chapter 1

Motivation, Objectives, and Organization of the Thesis

1.1 Motivation

A massive deployment of devices with wireless capabilities has been prominent during the last decade. Nevertheless, during the next few years, this trend is ex­pected to become even more pronounced. Most of the wireless networks available nowadays are infrastructure-based. However, users may not always want to com­municate using an infrastructure due to security, costs, or bandwidth constraints.

In vehicular environments, wireless technologies such as Dedicated Short Range Communication (DSRC) [XSMK04] and IEEE 802.11p Wireless Access for Ve­hicular Environment (WAVE) [IEE10] enable peer-to-peer mobile communication among vehicles (V2V), and communication between vehicles and the infrastructure (V2I). V2V communications allow the transmission of small messages to improve traffic safety. V2I communications, in contrast, allow users to access higher level applications usually related to infotainment. We think that the combination of V2V and V2I communications can propel our communication capabilities even further, allowing us to communicate anytime and anywhere, improving the future Intelligent Transportation Systems (ITS) and increasing our life quality tremen­dously.

Focusing on safety, one of the critical factors clearly stands in the fact of re­ducing the number of accidents and to minimize the possible injuries. When an accident occurs, vehicles will be able to send warning messages to other vehicles, preventing hazardous situations, or alert emergency services. However, high den­sity scenarios are common in vehicular networks (especially in urban environments or in the entrance areas to the cities), and a large amount of information is ex­pected to be transmitted between vehicles themselves and with the infrastructure units as well. Under these premises, the warning dissemination process could often suffer a serious problem due to the contention in the channel. Therefore, we believe that it would be worthy to propose new dissemination protocols for automatically sending warning messages, adapting their behavior according to environmental MOTIVATION, OBJECTIVES AND ORGANIZATION OF THE THESIS characteristics (e.g., the density of vehicles, the type of road in the accident, the attenuation of the wireless signal due to obstacles, etc.).

One of the most determinant factors in the dissemination process is the topol­ogy of the roadmap that affects the average distance between the sender and the receiver, as well as the different obstacles in the scenario. Another critical factor is the vehicle density, since lower densities can provoke message losses due to re­duced communication capabilities, whereas higher densities can provoke a reduced message delivery effectiveness due to serious redundancy, contention, and massive packet collisions caused by simultaneous forwarding, usually known as broadcast storm [TNCS02]. Therefore, we consider that novel dissemination approaches should be proposed and tested under these adverse vehicle density conditions, thereby assessing their real performance under any circumstances.

1.2 Objectives of the Thesis

The main objective of this Thesis is to develop an adaptive broadcast scheme that allows each vehicle to automatically adopt the optimal dissemination scheme, fitting the warning message delivery policy to each specific scenario at any in­stant, and thus achieving the highest number of informed vehicles, while avoiding broadcast storm problems.

In order to implement the adaptive scheme, the second objective is to design an algorithm that selects the optimal broadcast dissemination scheme to be used for each situation. This algorithm should offer the best suitable dissemination technique to be adopted depending on current density and topology of the scenario.

Since the adaptive dissemination scheme requires to know the current vehicle density, the third objective is to allow vehicles to measure the density of their neighborhood. This Thesis should propose a method which allow vehicles to esti­mate the density of vehicles in real time. Unlike previous proposals, the mechanism should use several input parameters such as the number of beacons received per vehicle and the topological characteristics of the environment where the vehicles are located (number of streets, number of junctions, number of lanes, etc.).

As a fourth objective of the Thesis, we want to analyze extreme vehicle density conditions that frequently appear in VANETs. On the one hand, extremely high density conditions, which are very common in urban environments, and where the broadcast storm problem is prone to occur. On the other hand, extremely low density conditions, where the sparse environments make very difficult the spread of the warning messages. After the analysis, we want to propose broadcast dissemination algorithms specially designed to address these adverse conditions.

Finally, we will proceed to classify all the broadcast dissemination schemes studied according to the parameters used in the design of each scheme. In addition, we will make a fair performance evaluation under the same conditions, obtaining a clear picture of the overall improvements achieved.

1.3 Organization of the Thesis

This Thesis is organized as follows: in Chapter 2 we make an introduction to Vehicular Networks (VNs) and Vehicular Ad Hoc Networks (VANETs), showing their main characteristics and applications. Additionally, we present the main features of the warning dissemination process, and some of the most relevant existing broadcast schemes proposed to address this issue. Finally, we classify these schemes depending of the features used in their working mode.

Chapter 3 presents our infrastructureless mechanism to estimate the vehicle density in urban environments. Unlike existing proposals, the mechanism uses as input parameters the number of beacons received per vehicle, and the topological characteristics of the environment where the vehicles are located, allowing each vehicle to estimate the density of its neighborhood.

In Chapter 4 we propose RTAD, a real-time adaptive dissemination system that allows each vehicle to automatically adopt the optimal dissemination scheme to adapt the warning message delivery policy to each specific situation. Its main goal is to maximize the message delivery effectiveness while generating a reduced number of messages and, thus, avoiding or mitigating broadcast storms. As shown in that chapter, RTAD outperforms other static dissemination schemes as well as existing adaptive dissemination systems.

Chapter 5 addresses adverse vehicle density conditions in VANETs; in particu­lar, we propose the Junction Store and Forward (JSF) and the Neighbor Store and Forward (NSF) schemes designed to be used under low density conditions, and the Nearest Junction Located (NJL) scheme specially developed for high density conditions.

In Chapter 6 we present a complete classification of the most relevant broad­cast dissemination schemes, including our proposed approaches. In addition, we analyze the environments used by the different authors to assess their mechanisms, and we provide a comparative analysis of their performance by evaluating them under the same conditions, and focusing on the same metrics, thus providing re­searchers with a general overview of the benefits and drawbacks associated to each scheme.

Finally, in Chapter 7 we present a summary of the main results and contri­butions of this Thesis, along with some concluding remarks. We also include a list of the publications related to the Thesis, and we comment on possible future research works that can derive from the work here presented.

Chapter 2 Background on Vehicular Networks and Warning Message Dissemination

Some years ago, the automotive industry built powerful and safer cars by embed­ding advanced materials and sensors. With the advent of wireless communication technologies, cars are being equipped with wireless communication devices, en­abling them to communicate with other cars. Such communications are not plainly restricted to data transfers (such as emails, etc.), but also create new opportunities for enhancing road safety. Some applications only require communication among vehicles, while other applications require the coordination between vehicles and the road-side infrastructure.

The applications and advantages of using vehicular communication networks for enhancing road safety and driving efficiency are diverse, which explains why research in this area has recently emerged.

2.1 Introduction

In the past, people were focused on how to build efficient highways and roads. Over time, focus shifted to mechanical and automotive engineering, in the pur­suit of building faster cars to surmount greater distances. Later on, electronics technology impacted the construction of cars, embedding them with sensors and advanced electronics, making cars more intelligent, sensitive and safe to drive on. Now, innovations made so far in wireless mobile communications and networking technologies are starting to impact cars, roads, and highways. This impact will drastically change the way we view transportation systems of the next generation and the way we drive in the future. It will create major economic, social, and global impact through a transformation taking place over the next 10-15 years. Hence, technologies in the various fields have now found common grounds in the broad spectrum of the Next Generation Intelligent Transportation Systems (ITS).

ITS are being propelled by the development and adaptation of wireless telecom­munications and computing technologies, thereby allowing our roads and highways to be both safer and more efficient transportation platforms.

The excitement surrounding vehicular networking is not only due to the appli­cations or their potential benefits but also due to the challenges and scale of the solutions. Among technical challenges to be overcome, high mobility of vehicles, wide range of relative speeds between nodes, real-time nature of applications, and a multitude of system and application related requirements can be listed. Further­more, considering ITS applications that require information to be relayed multiple hops between cars, vehicular networks are poised to become the most widely dis­tributed and largest scale ad hoc networks. Such challenges and opportunities serve as the background of the widespread interest in vehicular networking by governmental, industrial, and academic bodies [KAE+11].

In this chapter we examine the impact of vehicular networks in road safety and the warning dissemination process. This chapter is organized as follows: Sec­tion 2.2 presents Vehicular Networks, and also makes an introduction to Vehicular Ad Hoc Networks (VANETs), showing their main characteristics and applications. Warning dissemination process is presented in Section 2.3, and some existing warn­ing dissemination broadcast schemes are shown. Section 2.4 presents the simula­tion environment used in this Thesis. Finally, Section 2.5 concludes this chapter.

2.2 Vehicular Networks

Vehicular networking serves as one of the most important enabling technologies required to implement a myriad of applications related to vehicles, vehicle traffic, drivers, passengers, and pedestrians [KAE+11].

The convergence of wireless telecommunication, computing, and transportation technologies facilitates that our roads and highways can be both our transportation and communication platforms. These changes will completely revolutionize when and how we access services, communicate, commute, entertain, and navigate, in the coming future. Vehicular Networks (VNs) are wireless communication networks that support cooperative driving among communicating vehicles on the road. Ve­hicles act as communication nodes and relays, forming dynamic vehicular networks together with other nearby vehicles and the infrastructure [STFL10]. VNs involve vehicle-to-vehicle (V2V) [MCC+09] and vehicle-to-infrastructure (V2I) [SLCG08] communications, and have received a remarkable attention in recent years.

The specific characteristics of Vehicular Networks (VNs) favor the development of attractive and challenging services and applications, including road safety, traffic flow management, road status monitoring, environmental protection, and mobile infotainment [TML08, CSW10, AAAN13].

2.2.1 Vehicular ad hoc networks (VANETs)

Vehicular Ad hoc Networks (VANETs) are a particular subclass of Vehicular Net­works (VNs) which represent a set of equipped vehicles communicating with each

illustration not visible in this excerpt

Figure 2.1: Example of a VANET [DoT14].

other via the wireless antenna, without requiring the use of infrastructure (see Figure 2.1).

VANETs are characterized by very high speed and limited degrees of freedom in nodes movement due to the road topology. A wide range of applications can be enabled in VANETs, e.g., emergency message dissemination, real-time traffic condition monitoring, collusion avoidance and safety, where communications are exchanged in order to improve the drivers responsiveness and safety in case of road incidents. VANETs not only can enhance traffic safety but also provide comfort applications between vehicles [MLP10].

In VANETs, vehicles are equipped with sensors and Global Positioning Sys­tems (GPS) to collect information about their position, speed, acceleration, and direction to be broadcasted to all vehicles within their range. Upon receiving and processing this information, neighboring vehicles will detect and avoid potential dangers.

The research in VANETs is driven by IEEE 802.11p technology which is in­tended to enhance the IEEE 802.11 to support the Intelligent Transportation Sys­tem applications where reliability and low latency are crucial. These applications are intended to help drivers to travel more safely and reduce the number of fatal­ities due to road accidents.

In IEEE 802.11p, vehicles will not send an acknowledgement (ACK) for received broadcast messages. Therefore, the transmitter could not detect the failure of the packets reception and hence will not retransmit the packet. This is a serious problem in collision warning applications where all vehicles behind the accident have to receive the warning message successfully in short time to avoid chain collisions [KAE+11]. Vehicles can either use large transmission ranges or relay the message in a multi-hop fashion. While increasing the transmission range will increase the probability of interfering from hidden terminal nodes, using multi-hop

illustration not visible in this excerpt

Figure 2.2: Traffic safety applications of VANETs.

communications will increase the time delay the message will encounter until it reaches its intended distance.

2.2.2 Characteristics and Applications of VANETs

VANETs are characterized by: (a) trajectory-based movements with prediction locations and time-varying topology, (b) variable number of vehicles with inde­pendent or correlated speeds, (c) fast time-varying channel conditions (e.g., signal transmissions can be blocked by buildings), (d) lane-constrained mobility patterns (e.g., frequent topology partitioning due to high mobility), and (e) reduced power consumption requirements.

So far, the development of VANETs is backed by strong economical interests since vehicle-to-vehicle (V2V) communication allows using wireless channels for collision avoidance (improving traffic safety), improved route planning, and better control of traffic congestion [BFW03].

The specific characteristics of Vehicular networks favor the development of attractive and challenging services and applications. These applications can be grouped together into two main different categories:

- Safety applications (see Figure 2.2), that look for increasing safety of pas­sengers by exchanging relevant safety information via V2V and V2I commu­nications, in which the information is either presented to the driver, or used to trigger active safety systems. These applications will only be possible if the penetration rate of VANET-enabled cars is high enough. In this Thesis, we will focus in safety applications in order to reduce the number of fatal­ities while significantly improving the response time and the use of rescue resources.

illustration not visible in this excerpt

Figure 2.3: Comfort and commercial applications of VANETs.

- Comfort and Commercial applications (see Figure 2.3) that improve pas­senger comfort and traffic efficiency, optimize the route to a destination, and provide support for commercial transactions. Comfort and commercial applications must not interfere with safety applications [JK08].

2.3 Warning dissemination process

Regarding safety in Vehicular Networks, efficient warning message dissemination schemes are required since the main goal is to reduce the latency of such critical information while ensuring the correct reception of the alert information by nearby vehicles. When a vehicle detects an abnormal situation on the road (e.g., accident, slippery road, etc.), it immediately starts notifying the anomaly to nearby vehicles to rapidly spread the information in a short period of time. Hence, broadcasting warning messages is of utmost importance to alert nearby vehicles.

However, this dissemination is strongly affected by: (i) the signal attenuation due to the distance between sender and receiver (especially in low vehicular density areas), (ii) the effect of obstacles in signal transmission (very usual in urban areas, e.g., due to buildings), and (iii) the instantaneous vehicle density.

Regarding (i) and (ii), the topology of the roadmap is an important factor that affects the average distance between the sender and the receiver, as well as the different obstacles in the scenario. As for (iii), the warning message propagation scheme should be aware of vehicle density. In fact, lower densities can provoke mes­sage losses due to reduced communication capabilities, whereas higher densities can provoke a reduced message delivery effectiveness due to serious redundancy, contention, and massive packet collisions caused by simultaneous forwarding, usu­ally known as broadcast storm [TNCS02].

illustration not visible in this excerpt

Figure 2.4: weighted p-persistence dissemination scheme example [WTP+07].

2.3.1 Existing Broadcast Message Dissemination Schemes

VANETs have particular features, such as distributed processing and organized networking, a great number of nodes (i.e., vehicles) moving at high speeds, a con­strained but highly variable network topology, changing communication conditions and mobility patterns, building-related signal blockage, and frequent network par­titioning due to the high mobility. Hence, several dissemination schemes have been proposed to improve the dissemination process according to the specific charac­teristics of communications in vehicular environments.

In this section, we introduce some of the most relevant broadcast schemes proposed to disseminate warning messages, e.g., in case of accident, or to advertise any critical situation on the road.

- The Counter-based scheme proposed by Tseng et al. [TNCS02] was ini­tially proposed for Mobile Ad Hoc Networks (MANETs). In particular, this scheme aims at mitigating broadcast storms by using a threshold C and a counter c to keep track of the number of times a broadcast message is received. Whenever c C, rebroadcast is inhibited.
- The Distance-based scheme [TNCS02] accounts for the relative distance d between vehicles to decide whether to rebroadcast or not. When the distance d between two vehicles is short, the additional coverage (AC) area of the new rebroadcast is lower, and so rebroadcasting is not recommended. Forwarding is only beneficial when the additional coverage is nearly maximum.
- The weighted p-persistence and the slotted p-persistence techniques presented by Wisitpongphan et al. [WTP+07] are some of the few rebroadcast schemes specifically proposed for VANETs. These probabilistic broadcast suppres­sion techniques can mitigate the severity of the broadcast storms by allow­ing nodes with higher priority to access the channel as quickly as possible. However, their ability to avoid storms is limited since these schemes are specifically designed for highway scenarios.

Figure 2.4 illustrates an example of weighted p-persistence working mode. Upon receiving a packet from node i, node j checks the packet ID and re­broadcasts with probability pj if it receives the packet for the first time; otherwise, it discards the packet. Denoting the relative distance between nodes i and j by pij and the average transmission range by R, the forwarding probability, pij, can be calculated on a per packet basis using the following simple expression: pij = dij/R.

Update the location of the vehicle from which the broadcast message originated

illustration not visible in this excerpt

Figure 2.5: TLO dissemination scheme working flowchart [SP08].

Note that if node j receives duplicate packets from multiple sources within the waiting period of WAIT_TIME (e.g., 2 ms) before retransmission, it selects the smallest pj value as its reforwarding probability; that is, each node should use the relative distance to the nearest broadcaster in order to ensure that nodes who are farther away transmit with higher probability. If node j decides not to rebroadcast, it should buffer the message for an additional WAIT_TIME + σ ms, where σ is the one-hop transmission and propagation delay, which is typically less than WAIT_TIME. In order to prevent message die out and guarantee 100 percent reachability, node j should rebroadcast the message with probability 1 after WAIT_TIME + σ ms, if it does not hear the retransmission from its neighbors. Unlike the p-persistence or gossip-based scheme, weighted p-persistence assigns higher probability to nodes that are located farther away from the broadcaster given that GPS information is available and accessible from the packet header.

- The Last One (TLO) is a scheme proposed by Suriyapaibonwattana et al. [SP08] that attempts to reduce the broadcast storm problem by finding the most distant vehicle from the warning message sender, so that this vehi­cle will be the only one allowed to retransmit the message. This method uses GPS information from the sender vehicle and the possible receivers to calculate the distance between them.

Figure 2.5 shows the flowchart working mode of TLO. In first place, it will check condition ”Am I ’LV’ ” (Last Vehicle) by using GPS data. TLO algorithm will use the longitude and latitude information that is contained in the alert message and compare with position data of its own neighbor table. For example, if Accidented Vehicle (AV) has sent alert message and its position (Latitude = 40.443142, Longitude = -79.953974), the received vehicle will use AV position to find the last one. Authors used Vincenty’s
formula, the most accurate and widely used globally-applicable model for the earth ellipsoid base on WGS-84, to calculate distance between AV and the received vehicle. Each vehicle will calculate its distance and compare to other neighbor’s distance.

Although TLO brings a better performance than simple broadcast, this scheme is only effective in highway scenarios because it does not take into account the effect of obstacles (e.g., buildings) in urban radio signal propa­gation. Moreover, the scheme does not clearly state how a node knows the position of nearby vehicles at any given time.

- The Adaptive Probability Alert Protocol (APAL) is an extension to the TLO scheme that uses adaptive wait-windows and adaptive probability to transmit [SPC09].

APAL protocol is illustrated in Figure 2.6. When vehicle A is involved in an accident, it will send an alert message. This will be received by vehicles B, C, D, E, and F. All these vehicles, after receiving alert message for the first time, will start the APAL algorithm to rebroadcast the alert message. First, vehicles B, C, D, E, and F will execute step 1. They will wait un­til their respective Δτι expires, to decide whether to broadcast or not with probability Pi. Suppose that E decides to rebroadcast the alert message and does it earliest compared to other vehicles. Vehicles B, C, D, and F will receive the duplicated alert message from E, while vehicles G, H, I, and J will receive the alert message for the first time. Then vehicles G, H, I, J, and K will start APAL from step 1, and B, C, D, and F will start step 2, as they received a duplicate alert message. Pj will decrease with Duplicate Number and Δτι increase. APAL decreased next broadcast probability and increased the interval Δτι, because the alert message has already been dis­seminated. The possibility of its loss is low, though not zero. B, C, D, and F will not exit APAL protocol yet. For exiting condition, (CountTime lt; β amp;amp; DuplicateNumber lt; δ) is used for improving the success rate of the alert message and prevent its loss, which may happen because the vehicles following behind are far, or transmission being poor due to bad weather, or some obstacles. Although this scheme shows even better performance than the TLO scheme, it was also only validated in highway scenarios.

- Slavik and Mahgoub [SM10] proposed a stochastic broadcast scheme (SBS) to achieve an anonymous and scalable protocol where relay nodes rebroadcast messages according to a retransmission probability. The performance of the SBS system depends on the vehicle density, and the probabilities must be tuned to adapt to different scenarios. However, the authors only test this scheme in an obstacle-free environment, thus not considering urban scenarios where the presence of buildings could interfere with the radio signal.^[1]

illustration not visible in this excerpt

Figure 2.6: APAL dissemination scheme working [SPC09].

[...]

---

^[1] The enhanced Street Broadcast Reduction (eSBR) scheme, proposed by Mar­tinez et al. [MFC+10], was specially designed to be used in VANETs, taking advantage of the information provided by maps and built-in positioning sys­tems, such as the GPS. Vehicles are only allowed to rebroadcast messages if