TF-DMB: A traffic flow theory-based dynamic multi-hop broadcast protocol

Abstract

In order to ensure traffic safety, the emergency warning message should be transmitted quickly and reliably in vehicular ad hoc networks by multi-hop broadcast. In this article, we propose a traffic flow theory-based dynamic multi-hop broadcast protocol to address the issue of emergency warning message dissemination in vehicular ad hoc networks. The main goal of our protocol is to reduce delay and enhance reliability no matter the traffic density is high or low. First, according to the simulations of the distribution of vehicles under different traffic densities, a method of dynamically dividing the communication range is proposed, which, to a large extent, could find the candidate forwarders by one non-uniform partition. Next, a mechanism of dynamically adjusting the contention window size and boundary is designed, and the minimum waiting time difference is considered. The complete execution process of theory-based dynamic multi-hop broadcast protocol and corresponding retransmission strategies are included for high reliability. Through extensive simulations, we demonstrate the superior performance of our protocol in terms of one-hop delay, one-hop message processing, and delivery ratio compared with other existing schemes.

Keywords

Vehicular ad hoc networks dynamic multi-hop broadcast protocol emergency warning message traffic flow theory dynamic area division dynamic competition mechanism

Introduction

With the development of transportation industry, some serious problems, such as traffic accident and road congestion, are brought into our vision. In order to govern the urban transportation and ensure traffic reliability, Intelligent Transport System¹ (ITS) that combines sensing, control, communication, and other advanced technologies is gradually emerging. In particular, vehicular ad hoc networks (VANETs) is one of the critical technologies to implement ITS, which has attracted a lot of researchers.

In VANETs, safety-related applications are particularly important. The emergency warning message (EWM) resulting from some emergencies (e.g. vehicle crash) should have a higher priority and needs to be disseminated quickly and reliably. However, the communication range of one vehicle is limited. Thus, EWM should be transmitted by means of multi-hop broadcast so that we can timely inform the vehicles in the distance to avoid serial accidents. The multi-hop broadcast protocol for the dissemination of EWM should have two key characteristics: short delay and high reliability.² Short delay means the emergency message should be sent to all vehicles in the interested area as soon as possible; high reliability means high delivery ratio should be guaranteed. The selection of next-hop forwarder and the mechanism of collision avoidance are two main factors that affect the delay and reliability of a protocol.

One kind of effective protocols is based on distance. In these protocols, the communication range of the source is divided into a few areas. We select the next-hop forwarder from the vehicles in the area that is relatively far away from the source (i.e. the remote area). This is based on the knowledge that the further the forwarder, the greater the additional coverage distance it can provide, which is beneficial to reduce end-to-end delay and enhance the effectiveness of the protocols. As the topology of VANETs is dynamic, the vehicle density is also changing. However, most existing broadcast protocols do not take the change of traffic density into consideration.^3–10 Most of these protocols are suitable for operating exclusively under dense or sparse networks. When the traffic density is high, some protocols usually evenly and iteratively divide the communication range. As a result, they waste too much time on repeated and unnecessary partitions, which increases the delay. Some protocols use non-adaptive contention windows (i.e. waiting time intervals), the sizes of which are fixed. It results in high collision probability and thus reduces the reliability. When the traffic density is low, some protocols may suffer long delay because the boundary of the contention window is always fixed. Even if some researchers consider the traffic density when designing protocols,^11–13 they use it for either dividing the area or designing the contention window, which are not detailed and comprehensive enough. In addition, in most cases, the minimum waiting time difference¹⁴ between two adjacent nodes is not taken into account. We must note the fact that when one node completes its waiting, another node may have not received the signal yet but it also completes its own waiting. Therefore, a packet collision occurs. To this end, how to design a dynamic and comprehensive multi-hop broadcast protocol that makes full use of the traffic density both in area partition phase and competitive phase becomes a significant challenge.

Considering that the traffic flow theory¹⁵ is a detailed theory that can reflect the actual traffic conditions and guide the traffic planning and design, in this article, we design a traffic flow theory-based dynamic multi-hop broadcast protocol (TF-DMB) to guarantee good performances at any density. Adopting the traffic flow theory, on one hand, the protocol realizes dynamic partition of communication range according to the change in traffic density. Under different densities, through accurate calculations and simulations, the lengths of remote area are set to be different. In this way, to a large extent, we just need one non-uniform partition to find the next forwarder at any density, which helps to reduce the delay. On the other hand, it can dynamically adjust the size and boundary of the contention window according to current traffic conditions. When the traffic density is high, the size of contention window becomes larger. Thus, the number of optional waiting times increases and the collision probability decreases, which enhances the reliability of the protocol. When the traffic density is low, as there is no need for many waiting times, the upper boundary of the contention window decreases. Thus, the waiting time is shortened, which also helps to reduce delay. Besides, we also take the minimum waiting time difference¹⁴ between two adjacent nodes into account to further reduce the collision probability and enhance reliability. In a word, no matter the traffic density is high or low, the protocol is always well adaptive and has good performances both in delay and reliability. The contributions of this article can be summarized as follows:

We propose a traffic density–based dynamic area partition method. According to the theoretical analysis and calculations based on the traffic flow theory, the lengths of remote area are different under different traffic densities. Therefore, to a large extent, regardless of the traffic density, it can find the area where some candidate forwarders are located by one non-uniform partition, which helps to reduce delay.

We design a traffic density–based dynamic competition mechanism, which can adaptively adjust the contention window size and boundary according to the realistic traffic conditions. It helps to enhance reliability in dense networks and reduce delay in sparse networks. Additionally, the minimum waiting time difference between two adjacent nodes is also considered.

We describe the complete execution process of TF-DMB that makes full use of the dynamic characteristics of the traffic flow. The corresponding retransmission strategies are also introduced in order to ensure high reliability.

Extensive simulations are conducted to demonstrate that our protocol can significantly reduce the one-hop delay, increase the one-hop message process, and the delivery ratio compared with other existing protocols at any density.

The structure of this article is organized as follows. We present the related work in the next section. We describe the system model in the third section. Then, we propose the method of dynamic area partition and the mechanism of dynamic competition in the fourth section. The complete execution process of TF-DMB is also described in the fourth section. Next, we evaluate the performance of our protocol by extensive simulations in the fifth section followed by concluding remarks in the final section.

Related work

Recently, many protocols have been proposed for multi-hop broadcast in VANETs. Most of them are based on distance.¹⁶ These protocols prefer to select the node that is far away from the source.

Urban multi-hop broadcast protocol (UMBP) proposed by Korkmaz et al.³ is a classic protocol based on distance. It evenly divides the communication range of the source into a given number of areas and uses the black-burst (i.e. a channel jamming signal) to find the furthest non-empty area. If there is more than one node in the furthest non-empty area, this area is iteratively divided into sub-areas with smaller widths. After $D_{max}$ iterations, if it still cannot select the furthest node, the nodes in the last sub-area enter to a random selection phase. The vehicles in this area choose random black-burst lengths from $[0, N_{max} - 1]$ slots. The one with the longest duration becomes the final forwarder. In this method, for high vehicle density, the protocol may undergo a long waiting time during the area division phase because it needs to divide many times and the black-burst duration of the farthest node is the longest. Besides, many packet collisions may occur because multiple black-burst signals (BSs) may have the same length.¹¹ In SB,⁴ the coverage area is subdivided into equal areas and nodes in each area randomly pick a back-off value in the contention window assigned to that area. The farther the area from the source, the shorter the back-off values. In high traffic density, it has shorter latency compared with UMBP, but when the traffic density is low, all nodes may be close to the source, so the back-off time is long.¹¹ Additionally, since SB does not spend time to resolve collisions, it sometimes cannot find the relay that provides the largest additional coverage distance.

Sahoo et al.,⁵ developed a binary partition assisted emergency broadcasting protocol (BPAB). The communication range of the source is divided into two equal areas. It also uses the BS to find the far area (the area that is far away from the source). If the far area is non-empty, it starts the next division until N iterations to find the farthest and non-empty area (i.e. the optimal area); otherwise, the near area starts the next iteration. Then, it uses the contention window mechanism to find the final forwarder in the optimal area. It also reduces delay compared with UMBP, but it still needs to iterate many times when the traffic density is high. Suthaputchakun et al.,⁶ and Bi et al.,⁷ respectively proposed trinary partitioned black-burst-based broadcast (3P3B) protocol and urban multi-hop broadcast protocol (UMBP) to improve BPAB. In 3P3B,⁶ by adopting a mini-distributed inter-frame spacing (DIFS) mechanism, the delay is significantly reduced. In UMBP,⁷ the ratio of the far area to the communication range is not 1/2 but an adjustable parameter a. It reduces the number of iterations and delay to a certain extent. BZB⁹ protocol divides the communication range into two areas according to a certain distance threshold. In both areas, the waiting times are selected randomly between two bounds. It is ensured that the closer vehicles get a waiting time longer than the farther ones. Nevertheless, the common drawback of above schemes is also obvious, that is, when the vehicle density is high, the collision performance is still unsatisfactory because the contention window is still non-adaptive.

A black-burst and multi-channel-based multi-hop broadcast protocol (BMMB) is proposed by Wu et al.⁸ Similarly, it finds out the optimal segment by reiterative partitions. Different from others, the vehicles in different segments use different channels to transmit BSs with the same length to find the optimal segment, and the different vehicles in the optimal segment also use different channels to transmit BSs to find the relay node. It shortens the reiteration partitions and avoids packet collision, but multiple reiterations are still possible in high density. In addition, every vehicle needs to equip m antennas, which is costly.

All the protocols mentioned above based on area partition do not consider the actual traffic conditions. Some may be suitable for dense networks and others may be suitable for sparse networks. In some protocols, regardless of the traffic density, they evenly and repeatedly divide the communication range in the same way so that time is wasted on unnecessary area division. In these protocols,^3,5–8 when the traffic density is high, in order to let the number of candidate nodes in the optimal area is not very large to simplify the subsequent competitive process, they need to divide many times to shorten the length of this area, which increases the delay. In some protocols,^5–7,9 the size and boundary of contention window cannot be adjusted according to the density, so the collision probability is big when the traffic density is high, which is not reliable enough and the waiting time may be long even if there are just several vehicles within the communication range. Besides, in some protocols,^4,9 the farthest node cannot be always picked out, which reduces the additional coverage distance in each hop and the effectiveness of the protocols.

There are also many researchers taking the traffic density into account such as Rayeni et al.,¹¹ Akabane et al.,¹² and Berradj and Mammeri.¹³ In the protocol proposed by Rayeni et al.,¹¹ the number of areas is computed depending on the density. In the protocol proposed by Akabane et al.,¹² when the traffic density is above a certain limit, it employs a zone of preference mechanism. Vehicles that are within zone of preference have a smaller waiting time than other vehicles outside it. When the network is sparse, it focus on the scenario that there is no vehicle in the communication range and how to carry the message until the moment that distance between vehicles is sufficiently near, which goes beyond our scope of study. Moreover, the competition mechanisms in both papers are still non-adaptive in different densities. In the protocol proposed by Berradj and Mammeri,¹³ the size of contention window varies with the density, but it does not consider the area partition method and minimum waiting time difference between adjacent nodes.¹⁵ We must note that if two adjacent waiting times are too close, the collision may still occur due to the delay in message propagation.

Of course, some other kinds of protocols have also been developed.^17–19 However, to our best knowledge, besides Jin et al.,²⁰ we are the first using traffic flow theory to design a dynamic multi-hop broadcast protocol for highway scenario. In fact, in the protocol proposed by Jin et al.,²⁰ the traffic flow theory do not be made full use of, and it is more focus on the phenomenon that there are blind nodes in urban intersections, which is not very suitable for highway. In our protocol, both area partition and competition mechanism are dynamic to adapt different traffic densities in highway. No matter the density is high or low, it just needs one non-uniform partition to find the remote area where some candidate forwarders exist, and both the size and boundary of the contention window are adjustable according to the vehicle density. Besides, the concept of minimum waiting time difference is also considered to further reduce collision.

System model

Application scenario

We consider a two-way four-lane highway with a design speed of 120 km/h, as shown in Figure 1.

Figure 1.

Scenario description diagram.

Normally, the vehicles periodically exchange the periodic safety message (PSM). The main contents of PSM include the location, speed, acceleration, and other driving state information about the vehicles; so, the vehicles on the road can always know the running conditions of their neighbors. When there is an emergency such as a traffic accident on the front road, the nearest vehicle A from the scene of the accident will immediately broadcast EWM to the vehicles within its communication range. Then through the relay of the vehicles (B, C, and D) running in the same direction and located behind, the message can be quickly transmitted to the vehicles at a greater distance. The vehicles in the opposite running direction to A will not be affected by the accident, so they discard the received messages and do not forward them.

Specifically, when selecting the forwarding nodes, the source node A divides its communication range into two areas, namely, the near area and the remote area, which is shown in Figure 2. The “remote area” means the area that is relatively far away from the source. We select the next-hop forwarder in this area so that EWM can be transmitted faster and farther at each hop to reduce end-to-end delay. The nodes in this area are called candidate forwarders.

Figure 2.

Communication range partition.

If the number of nodes in the remote area is more than one, then we assign a contention window (i.e. a waiting time interval) to this area. Every candidate forwarder randomly selects a waiting time from the contention window, starts a timer and counts down. The one first completing its countdown then sends a packet to inform the source that it has become the final forwarder.

Traffic flow theory

The traffic flow theory shows the general laws of vehicle behavior. Taking advantage of these laws, we can further guide the traffic planning and design.¹⁵

The basic parameter model of traffic flow is defined as equation (1)

Q = KV

(1)

where Q is the traffic volume, that is, the number of vehicles passing through a certain section on the road during a period of time. K is the average traffic density, that is, the average number of vehicles per unit distance at a certain time. V is the average driving speed within an interval, that is, the distance that a vehicle travels per unit time.

The relationship between V and K can be expressed as equation (2)

V = V_{f} (\frac{1 - K}{K_{j}})

(2)

where $V_{f}$ denotes the average speed when the traffic density approaches to zero and vehicles can run smoothly. $K_{j}$ denotes the jam density, that is, the density when the traffic is so dense that all vehicles are nearly unable to move (V = 0). According to equations (1) and (2), the relationship between Q and K can be expressed as equation (3)

Q = K V_{f} (1 - \frac{K}{K_{j}}) = V_{f} (K - \frac{K^{2}}{K_{j}})

(3)

We can find that equation (3) is a parabolic shape. When $K = K_{j} / 2$ , Q can achieve its maximum value as equation (4)

Q_{m} = \frac{V_{f} K_{j}}{4}

(4)

Similarly, we can get the relationship between Q and V as equation (5)

Q = K_{j} (V - \frac{V^{2}}{V_{f}})

(5)

We denote the distance between two consecutive cars (measured with representative points such as the front bumpers) in the same lane as space headway $h_{s}$ . We also denote and the time interval between two consecutive cars passing through the same section as time headway $h_{t}$ .

The relationship between the average space headway $\bar{h_{s}}$ and the average traffic density K can be expressed as follows

K = \frac{1000}{\bar{h_{s}}}

(6)

The relationship between the average time headway $\bar{h_{t}}$ and traffic volume Q can be expressed as equation (7)

Q = \frac{3600}{\bar{h_{t}}}

(7)

The relationship among space headway $h_{s}$ , time headway $h_{t}$ , and driving speed V is as equation (8)

h_{s} = \frac{V}{3.6} h_{t}

(8)

TF-DMB protocol

We present our TF-DMB protocol in this section. First, we deduce the probability that vehicles exist in the remote area according to the simulations of vehicle distribution under different service levels. Then, we propose a dynamic area partition method based on the calculation results. Next, we develop a dynamic competition mechanism considering the realistic traffic conditions. Finally, the execution process of TF-DMB is described in detail.

Traffic density–based dynamic area partition

The service level classification of expressway

According to the maximum service traffic volume, we can classify the service levels of highway with a design speed of 120 km/h into five grades.²¹ In order to simplify the subsequent analysis, we merge the five service levels into four, which are shown in Table 1. Note that C here denotes the basic traffic capacity, that is, the maximum traffic volume that can be reached per hour (h) per lane (ln) under ideal conditions.

Table 1.

The service level classification of basic highway section with a design speed of 120 km/h.

New service level	Original service level	V/C	The maximum service traffic volume $Q_{m}$ (pcu^a/h/ln)
I	I	$V / C \leq 0.55$	1200
	II
II	III	$0.55 < V / C \leq 0.75$	1650
III	IV	$0.75 < V / C \leq 0.90$	1980
IV	V	$0.90 < V / C$	2200

pcu (passenger car unit) is the standard car equivalent. We convert the traffic volume of other motor vehicles or non-motor vehicles into the equivalent volume of standard cars according to a certain conversion factor. For a standard car, pcu = 1, pcu/h/ln denotes the traffic volume per hour per lane. In this article, we assume that all vehicles are standard cars.

Ideally, when the traffic flow reaches saturation, the average speed $V \leq 48 km / h$ , which means the critical speed (i.e. the speed when traffic volume reaches the maximum value) $V_{m} = 48 km / h$ . As shown in Table 1, we can know that Q_m = 2200 pcu/h/ln. Bring the two variables into equation (1), we can get K_m = 45 pcu/km/ln, where $K_{m}$ denotes the best density (i.e. the density when traffic volume reaches the maximum value). So $K_{j} = 2 K_{m} = 90 pcu / km / \ln$ . Then, according to equation (4), we can get $V_{f} = 97.8 km / h$ . Combining the above calculation results and the maximum traffic volume under different service levels, according to equations (3) and (5), we can easily get the corresponding K and V. Note that here K cannot be larger than $K_{m} = 45 pcu / km / \ln$ and V cannot be less than $V_{m} = 48 km / h$ . The communication range R used in this article is 300 m, so the average number of vehicles in a single lane within the communication range can be calculated according to (K/1000)*R. In addition, in order to get the distribution probability of vehicles, we also need to determine the distribution model under different traffic densities, which can be obtained from Jin et al.²² and Luo et al.²³ The analytical results of relevant parameters are summarized in Table 2.

Table 2.

Analysis result of relevant parameters.

Service level	Traffic density K (pcu/km/ln)	The critical speed V (km/h)	The average number of vehicles within R (pcu/ln)	The distribution model of space headway
I	(0,14]	85.7	(0,4]	Negative exponential distribution
II	(14,22]	75	(4,6]	Shifted negative exponential distribution
III	(22,30]	66	(6,9]	Two-order Erlang distribution
IV	(30,45]	48	(9,13]	Uniform distribution

Dynamic area partition

According to the results in Table 2, we simulate the distribution models of space headway within communication range in single lane under four service levels. The vehicle distribution frequency and relative frequency can be obtained. The probability that vehicles exist in remote areas can also be estimated. In some existing protocols, no matter the traffic density is high or low, the ways of dividing the communication range are always the same. In other words, they always evenly and repeatedly divide the communication range. Therefore, when the density is high, multiple iterations are needed and too much time are wasted. However, taking full account of the laws of vehicle driving and distribution, the length of remote area should be different under different service levels. Through accurate calculations, we can decide the length of remote area under different traffic densities. Thus, to a large extent, we just need to non-uniformly divide once to find the final forwarder. When deciding the length of remote area, there are two main requirements: (1) the probability that vehicles exist in remote area should be large enough so that we can find the next-hop forwarder as soon as possible; and (2) the number of vehicles in the remote area should not be too much so that the competition process can be simplified. Considering above two tips, specific details are as follows. Here, this experiment is repeated 500 times.

Service level I. The traffic density is the lowest under service level I. The number of vehicles within communication range in a single lane is assumed to be 4. In this case, we set the range of remote area from R/2 to R, and the statistical results are shown in Figure 3(a).

Service level II. The traffic density under service level II is larger than that under level I. The number of vehicles within communication range in a single lane is assumed to be 5. In this case, we set the range of remote area from 2R/3 to R. The statistical results are shown in Figure 3(b).

Service level III. The traffic density under service level III is quite large and the number of vehicles within communication range in a single lane is assumed to be 7. So the range of remote area is set from 3R/4 to R. The statistical results are shown in Figure 3(c).

Service level IV. The traffic density under service level IV is the largest and the number of vehicles within communication range in a single lane is assumed to be 10. So the range of remote area is set from 7R/8 to R. The statistical results are shown in Figure 3(d).

Figure 3.

(a) The number of vehicles distributed in [R/2, R] under service level I, (b) the number of vehicles distributed in [2R/3, R] under service level II, (c) the number of vehicles distributed in [3R/4, R] under service level III, and (d) the number of vehicles distributed in [7R/8, R] under service level IV.

As shown in Figure 3, when the number of lanes becomes 1 and the service level is I, the probability that vehicles exist between R/2 and R can be expressed as $1 - P (N = 0)$ , where N denotes the number of vehicles and $P (N = 0)$ denotes the probability that there is no vehicle. So when the number of lanes becomes 2, the probability that vehicles exist between R/2 and R can be expressed as

P (N > 0) = 1 - [P (N = 0)]^{2} = 1 - 0 . 276^{2} = 0.924

(9)

Similarly, the probability that vehicles exist in remote area under different service levels can be calculated in the same way. The results are shown in Table 3.

Table 3.

The probability that vehicles exist in remote area under different service levels.

Service level	The range of remote area	The probability that vehicles exist
I	[R/2, R]	0.924
II	[2R/3, R]	0.981
III	[3R/4, R]	0.984
IV	[7R/8, R]	0.968

As we can see from Table 3, in the ideal case, through one partition, the probability that we can successfully find the area where some candidate forwarders exist is more than 90%, which is relatively high. That is, to a large extent, we do not need to iterate again; so the latency is very small. However, after one partition, there is still less than 10% of the likelihood that there is no vehicle in the remote area. At this time, in order to successfully find the final forwarder and ensure high reliability, we should start the second partition. It is worth noting that the length of the remote area becomes twice the original to ensure the presence of vehicles. For example, when we need to divide three times, the iterative process under service level IV can be described as Figure 4.

Figure 4.

(a) The first partition, (b) the second partition, and (c) the third partition.

Traffic density–based dynamic competition mechanism

Through the method of dynamic area partition, it is possible to quickly locate the area where the candidate forwarders exist. However, the number of vehicles in this area may be more than one, so a more efficient competition mechanism is needed to pick out the final forwarder and avoid packet collision. Packet collision is the main reason for reducing reliability.

For most existing protocols adopting waiting time allocation mechanism, although it is able to find the final forwarder, it is easy to get affected by the collision problem when the traffic density is high and the delay problem when the traffic density is low. Here, if some nodes send the packets at the same time, we say a collision occurs. The reason for these problems is that they do not take the change in traffic density into account. The size and boundary of the contention window are always fixed, which is not adaptive enough. To this end, in this part, we design a contention window that can change its size and boundary with the change in traffic density. When the traffic density is high, it increases the number of waiting times and elongates the interval length to reduce collision probability and enhance reliability; when the traffic density is low, it decreases the upper boundary of contention window and shortens the interval length to reduce delay. Moreover, to further avoid collision, the difference between two adjacent waiting times should have a lower limit, that is, the minimum waiting time difference. Otherwise, when one node completes its countdown, another node may have not received the signal yet, then it also completes its own countdown. Thus, a packet collision occurs.

First of all, the following assumptions should be clear:

The application scenario is shown in Figure 1.

Every vehicle is equipped with a global positioning system (GPS) receiver that updates the vehicle’s location and a wireless access in vehicular environment/dedicated short range communications (WAVE/DSRC) device that enables vehicle ad hoc communication.

The vehicles can periodically exchange PSM according to a certain protocol. So, it is possible for them to estimate the real-time traffic density.

The dynamic contention window is based on the following equations.¹⁵ Equations (10)–(12) can calculate the upper and lower boundaries of waiting time interval. At the same time, the minimum difference between two adjacent waiting times is also taken into account

T_{u} = max {T_{max} \times (1 - α) \times D, T_{min} + L_{cw}}

(10)

T_{l} = T_{u} - β \times N \times Δ_{min} t

(11)

L_{cw} = (T_{max} - T_{min}) \times D \times α

(12)

The following are the explanations of above formulas and related parameters:

$T_{min}, T_{max}$ . They are the minimum and maximum waiting time, respectively. If the application requirements are different, they will get different constant values. Note that $T_{min} \in [0, T_{max}]$ . According to equation (10), $T_{max}$ will affect the value of $T_{u}$ ; so it will also affect the delay. We should set it according to specific latency requirements of different applications.

α: $α = L_{r} / R$ . $L_{r}$ denotes the length of remote area. It is different under different service levels, which has been described in “Dynamic area partition.”R is the communication range.

D: $D = N / N_{max}$ . It indicates the local traffic density, where N is the number of vehicles in remote area, $N_{max}$ denotes the maximum number of vehicles that can be reached in remote area when there is a traffic jam.

$L_{cw}$ . $L_{cw}$ is the length of contention window.

$Δ_{min} t$ . $Δ_{min} t$ is the minimum waiting time difference. The derivation can refer to Yoo and Kim.¹⁴

$T_{l}, T_{u}$ . $T_{l}$ is the lower boundary of waiting time interval and $T_{u}$ is the upper boundary of waiting time interval. In this article, $T_{l}$ and $T_{u}$ vary with the traffic density, which is different from other protocols where the values are fixed. When the traffic density is high, $T_{l}$ decreases but does not equal to zero. At the same time, $T_{u}$ increases. So the waiting time interval is extended, the number of optional waiting time increases, the collision probability reduces and the reliability enhances. In contrast, when the traffic density is low, $T_{l}$ increases and $T_{u}$ decreases. So, the interval is shortened and thus the delay is also reduced. Moreover, the minimum waiting time difference is also taken into account when calculating $T_{l}$ so that we can further reduce the collision probability.

$β$ . $β$ is a control parameter. If we adjust its value, we can control the size of $[T_{l}, T_{u}]$ . The larger the value of $β$ , the longer the interval, and the more the number of optional waiting times. So the probability that different nodes choose the same waiting time is smaller and the collision probability is smaller, too. Next, we will discuss the initial value of $β$ .

According to equation (11), $[T_{l}, T_{u}]$ can be written as equation (13). There are a total of $β N + 1 (β = 1, 2, 3, \dots, k; k \in N^{*})$ waiting time values in the interval; so for the N vehicles in remote area, the probability that different nodes select different waiting times is shown in equation (14)

[T_{l}, T_{u}] = [T_{u} - β N Δ_{min} t, \dots, T_{u} - 2 Δ_{min} t, T_{u} - Δ_{min} t, T_{u}]

(13)

\begin{array}{l} \bar{P_{c}} = (β N + 1) \times (β N) \times \dots \times \frac{(β N + 1 - N + 1)}{{(β N + 1)}^{N}} \\ = \frac{A_{β N + 1}^{N}}{{(β N + 1)}^{N}} \end{array}

(14)

So, the collision probability is

P_{c} = 1 - \bar{P_{c}} = 1 - \frac{A_{β N + 1}^{N}}{{(β N + 1)}^{N}}

(15)

When $β$ is different, the relationship between $P_{c}$ and N is shown in Figure 5. From the figure, we can get the following conclusions. First, in order to ensure a low collision probability, when N is small, $β$ can take a small value; otherwise, it should take a large value. Second, as the value of $β$ increases, the collision probability decreases. However, when $β$ increases to a certain value, its impact on collision probability becomes insignificant. Note that when $β$ increases, in order to ensure $T_{l} > 0$ , $T_{u}$ and $T_{max}$ should also increase, which makes the delay increase. Therefore, there is a trade-off and the value of $β$ is not the bigger the better. From section “Dynamic area partition,” we can find that the most probable number of vehicles in remote area in a single lane is 1 to 3. Thus, when the number of lanes becomes 2, the most probable number of vehicles becomes 2 to 6. Combining with the conclusion of Figure 5, we initially take $β = 7$ in this article, which can guarantee the maximum collision probability does not exceed 0.3.

Figure 5.

Diagram of the relationship between collision probability $P_{c}$ and the number of vehicles N in remote area under different $β$ values.

The execution process of TF-DMB

Next, the specific execution process of TF-DMB is presented by a timeline diagram and a flow chart. Figure 6 shows the process of TF-DMB when it executes successfully without any retransmission. The relevant description is as follows.

Figure 6.

The execution process of TF-DMB protocol.

First, PSMs are exchanged among the vehicles according to a certain single-hop broadcast protocol. By exchanging PSMs, the vehicles can estimate the traffic density in current network and judge the current service level.

SIFS denotes the short inter-frame space. It is equal to the time that a node takes from the transmit state to the receive state and decode correctly, or the time it takes from the receive state to the transmit state.

Before broadcasting EWM, the source node first sends a ready-to-broadcast (RTB) packet to the vehicles within its communication range. The packet can address the hidden node problem and inform the vehicles within its communication range to ready to receive and forward EWM.

After receiving RTB from the source node, other vehicles judge whether their traveling directions are the same as the source node. The vehicles in the opposite direction to the source node will not be affected by the emergency; so, the RTB packet and the subsequent EWM are discarded. However, for the vehicles in the same direction, they regard the EWM is related to themselves; so, they execute dynamic partition according to the current traffic density, which has been described in “Dynamic area partition.” If a vehicle is exactly within the remote area under the current traffic density, it then becomes a candidate forwarding node. Then, the candidate forwarders immediately send a short BS (S) to the source node, where (S) indicates that the signal is successfully transmitted and received. After receiving the BS, the source knows there exist some vehicles in the remote area.

Next, after the dynamic partition, the candidate forwarding nodes enter the competition phase (CW), the competition method is described in “Traffic density–based dynamic competition mechanism.” They select their own waiting times and then count down.

The node that first completes the countdown then sends a clear-to-broadcast (CTB) packet to the source node and becomes the next-hop forwarder finally. Then, the other candidate nodes end their countdowns and quit the competition after detecting the CTB packet.

Once the source node receives the CTB packet, it broadcasts the EWM after a DIFS. Then, the next-hop forwarder continues to forward the EWM to other vehicles.

Note that the broadcast process described in Figure 6 is executed successfully without any retransmission, that is, there exist vehicles in the remote area and no CTB collision occurs. However, sometimes the CTB packets are likely to collide or there may be no vehicle in the remote area; so, the broadcast process is not always so easy. In order to increase the robustness of the protocol and ensure the delivery ratio of EWM, we develop the following two corresponding retransmission strategies.

The retransmission strategy when the dynamic area partition is failed

If there is no vehicle in the remote area, no vehicle will send the BS, that is, the transmission of BS is failed, denoted as BS (F). For this case, while sending the RTB packet, the source node starts a timer at the same time. The time of timer is set to $T_{p}$ . If the source node does not receive the BS within $T_{p}$ , the RTB packet will be retransmitted. For other vehicles, when they receive the RTB packet again, they will start the secondary partition and extend the length of remote area to twice the original. This process is repeated until the BS is transmitted successfully, that is, BS (S).

The retransmission strategy when CTB fails to transmit

Although we have tried our best to reduce the collision probability resulting from the fact that different nodes choose the same waiting time, there is still a little chance of collision, which results in the failure of CTB transmission, that is, CTB (F). In this case, while selecting their own waiting time, the candidate forwarding nodes entering the competition phase also start a timer at the same time. The time of which is set to $T_{c}$ . If the candidate forwarding nodes do not detect the CTB packet from other candidates within $T_{c}$ , they think there occur some collisions. Then, the secondary competition is started. In particular, $β$ increases by 1 so that we can increase the contention window size and decrease the probability of collision. Repeat this process until the CTB packet is sent successfully, which is denoted as CTB (S).

The execution process of TF-DMB protocol with retransmission is shown in Figure 7 and the complete execution process of TF-DMB is shown in Figure 8. Specifically, Figure 8(a) shows the execution process of the source node, and Figure 8(b) shows the execution process of other vehicles.

Figure 7.

The execution process of TF-DMB protocol (with retransmission).

Figure 8.

Flowcharts of TF-DMB protocol execution process: (a) source node and (b) other vehicle nodes.

Performance evaluations

In this section, we evaluate the performance of the proposed protocol and compare it with other four partition-based protocols, namely UMBP, SB, BPAB, and 3P3B, respectively. Because of the two requirements of multi-hop broadcast protocol for EWM disseminated: short delay and high reliability, the evaluation metrics include one-hop delay, one-hop message progress, and delivery ratio. One-hop delay and one-hop message progress are used to verify whether the protocol could transmit EWM to the distant as soon as possible, which is important to the time-critical safety applications. Delivery ratio is used to verify the reliability of the protocol. Some other details and simulation results are presented as follows.

Simulation environments and settings

The simulations are conducted in VanetMobisim and NS2 and the relevant parameters are shown in Table 4.

Table 4.

Simulation parameters.

Parameter	Value
PHY/MAC protocol	IEEE 802.11p
Frequency	5.9 GHz
Data rate	6 Mbps
Wireless propagation model	Two Ray Ground
Simulation area	15 m × 3000 m
Single simulation time	500 s
The length of EWM	512 bytes
The length of RTB	20 bytes
The length of CTB	14 bytes
Slot time	13 µs
Rx/Tx time	2 µs
CCA time	8 µs
DIFS	58 µs
SIFS	32 µs
BS	1 slot
$T_{min}$	0 slot
$T_{max}$	256 slots
$T_{p}$	16 slots
$T_{c}$	260 slots
The number of vehicles per lane	20, 40, 60, 80, 100
Speed	60 km/h, 120 km/h
Visibility	>15 km

EWM: emergency warning message; RTB: ready-to-broadcast; CTB: clear-to-broadcast; CCA: clear channel assessment; DIFS: distributed inter-frame spacing; SIFS: short inter-frame space; BS: burst signal.

Evaluation metrics

To evaluate our proposed protocol, the following metrics are considered.

Average one-hop delay

In TF-DMB, the average one-hop delay is defined as the average interval from the time when the source sends RTB to the time when the next hop receives a complete EWM. This indicator is often used to measure the real-time nature of a protocol. In the following, we deduce the delay of TF-DMB in theory.

As shown in Figure 7, the dynamic partition process and the competition process may lead to communication failure during the execution of TF-DMB. The success of dynamic partition depends on whether there exist vehicles in the remote area. Table 3 shows the probability that there exist vehicles in the remote area under different service levels. It assumes that the four service levels have the same occurrence probability, which is 1/4. So the success and failure probability of dynamic partition can be expressed as equations (16) and (17), respectively

\begin{array}{l} P_{p_s} = P (N \geq 1) \\ = \sum_{i = 1}^{4} P (A_{i}) \times P (N \geq 1 | A_{i}) = 0.964 \end{array}

(16)

P_{p_f} = 1 - P_{p_s} = 0.036

(17)

where $A_{i} (i = 1, 2, 3, 4)$ is a random event that indicates the service level.

The success of competition process depends on the probability of collision $P_{c}$ . So, the success and failure probability of competition process can be expressed as equations (18) and (19)

P_{c_s} = 1 - P_{c}

(18)

P_{c_f} = P_{c}

(19)

According to the process of TF-DMB shown in Figures 7 and 8, the delay of this protocol can be divided into the following cases.

If no retransmission occurs, the delay of the protocol can be expressed as

\begin{array}{l} τ_{s u c c e s s} = t_{S I F S} + t_{R T B} + t_{p a r t i t i o n} + t_{B S} + t_{C W} \\ + t_{S I F S} + t_{C T B} + t_{D I F S} + t_{E W M} \end{array}

(20)

where different t denote corresponding times.

When partition retransmission is M times and there is no contention retransmission, the delay of the protocol can be expressed as

\begin{array}{l} τ_{r e_p a r} = M (t_{S I F S} + T_{p}) + t_{S I F S} + t_{R T B} + t_{p a r t i t i o n} + t_{B S} \\ + t_{C W} + t_{S I F S} + t_{C T B} + t_{D I F S} + t_{E W M} \end{array}

(21)

When contention retransmission is L times and there is no partition retransmission, the delay of the protocol can be expressed as

\begin{array}{l} τ_{r e_c o n} = t_{S I F S} + t_{R T B} + t_{p a r t i t i o n} + t_{B S} + L T_{c} + t_{C W} \\ + t_{S I F S} + t_{C T B} + t_{D I F S} + t_{E W M} \end{array}

(22)

When partition retransmission occurs M times and contention retransmission occurs L times, the delay of the protocol can be expressed as

\begin{array}{l} τ_{r e_p a r_c o n} = M (t_{S I F S} + T_{p}) + t_{S I F S} + t_{R T B} + t_{p a r t i t i o n} \\ + t_{B S} + L T_{c} + t_{C W} + t_{S I F S} + t_{C T B} + t_{D I F S} + t_{E W M} \end{array}

(23)

Thus, the theoretical average one-hop delay of TF-DMB is

\begin{matrix} \bar{τ} = & E (τ) = τ_{success} \times P_{p_s} \times P_{c_s} \\ + τ_{re_par} \times P_{p_f}^{M} \times P_{p_s} \times P_{c_s} \\ + τ_{re_con} \times P_{p_s} \times P_{c_f}^{L} \times P_{c_s} \\ + τ_{re_par_con} \times P_{p_f}^{M} \times P_{p_s} \times P_{p_f}^{L} \times P_{c_s} \end{matrix}

(24)

One-hop message progress

In order to avoid a series of accidents, EWM should be timely sent to the distant vehicles. The one-hop message process is defined as the additional distance covered by the message in one hop, on average (i.e. the distance between the source and the next-hop forwarder).⁴ This metric can measure the coverage of a protocol and reflect its effectiveness to a certain extent. We prefer to select the node falling furthest in distance from the source as forwarder, which is beneficial to reduce end-to-end delay.

As shown in Figure 9, it is the diagram of the one-hop message process. It can be seen that the farther the forwarding node from the last hop, the larger the message process.

Figure 9.

Diagram of the one-hop message progress.

Delivery ratio

The delivery ratio is defined as $N_{EWM_s} / N_{total}$ , where $N_{EWM_s}$ denotes the number of EWM packets received successfully and $N_{total}$ denotes the total number of EWM packets. It is often used to evaluate the reliability of a protocol.

Simulation results and analysis

Figure 10 shows the average one-hop delay of different protocols varying with the number of vehicles. It is observed that compared with the classic protocol UMBP and SB, the average one-hop delay of TF-DMB is significantly reduced. Besides, the delay fluctuation also decreases as the number of vehicles increases. This is because TF-DMB adopts a dynamic mechanism. According to the change in traffic density, it can dynamically divide the communication range of the source, and it can also adjust the contention window size and boundary. Moreover, compared with the two improved protocols BPAB and 3P3B, TF-DMB still has a smaller delay. This is mainly because TF-DMB adopts the traffic flow theory and analyzes the traffic conditions in detail. Thus, it can adaptively adjust the length of remote area according to the number of vehicles. In this way, to a large extent, it can locate the candidate forwarders by only one partition and thus reduce the delay.

Figure 10.

Average one-hop delay comparison between TF-DMB and other protocols.

The simulation of one-hop message progress is shown in Figure 11. As we can observe, on one hand, the one-hop message process for all protocols increases with the number of vehicles. This is because the next-hop forwarders in these protocols are all selected from the vehicles that are far away from the source. When the number of vehicles increases, the probability that vehicles exist in remote area also increases correspondingly. As a result, it is easier to find a vehicle in remote area as the next-hop forwarder. At the same time, the additional distance that can be covered when forwarding also increases. On the other hand, when the number of vehicles is small, the performance of TF-DMB is close to the other protocols. However, with the increase in vehicles, its one-hop message process increases significantly. This is because TF-DMB adopts a dynamic and non-uniform partition method; so, it can adjust the length of remote area according to the current traffic density. Compared with other protocols dividing the area uniformly, in theory, it is easier for TF-DMB to find the area that is the farthest from the source and where vehicles exist. Therefore, it increases the one-hop progress, which is also helps to reduce end-to-end delay.

Figure 11.

Average one-hop message progress comparison between TF-DMB and other protocols.

Figure 12 illustrates the delivery ratio varying with the number of vehicles. As we can observe from the figure, with the increase in vehicles, the delivery ratio of other protocols decreases significantly, while TF-DMB can still guarantee a high delivery ratio and the fluctuation is not obvious. This is because the competition mechanism is optimized in TF-DMB. Both the size and boundary of contention window are dynamically adjustable according to the traffic density. When the traffic density is high, the length of the window increases and the number of optional waiting times also increases. As a result, the collision probability is reduced and a high delivery ratio is ensured, which suggests the proposed protocol has high reliability.

Figure 12.

Delivery ratio comparison between TF-DMB and other protocols.

Conclusion

In this article, we propose a traffic flow theory-based dynamic multi-hop broadcast protocol, called TF-DMB. First, a dynamic area partition method is designed where the length of remote area is different under different traffic densities, which helps to find the non-empty remote area by only one non-uniform partition and reduce the delay. Then, an adaptive contention window mechanism is developed according to the change in traffic flow, which helps to reduce the collision probability in dense networks and reduce delay in sparse networks. Finally, a complete execution process of TF-DMB and corresponding retransmission strategies are also described in detail. Extensive simulations show that our protocol significantly reduces average one-hop delay and increases one-hop message progress and delivery ratio compared with other existing protocols at any traffic density.

Footnotes

Academic Editor: Shi-Jinn Horng

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This article was supported by the State Key Laboratory of Rail Traffic Control and Safety (Contract No. RCS2016 ZT015), Beijing Jiaotong University.

References

Xiong

Sheng

Rong

et al . Intelligent transportation systems for smart cities: a progress review. Sci China Inform Sci 2012; 55(12): 2908–2914.

Khabazian

Aissa

Mehmet-Ali

. Performance modeling of safety messages broadcast in vehicular ad hoc networks. Sci Technol Eng 2014; 14(1): 380–387.

Korkmaz

Ekici

Zgner

et al . Urban multi-hop broadcast protocol for inter-vehicle communication systems. In: Proceedings of the ACM workshop on vehicular ad hoc networks, Philadelphia, PA, 1 October 2004, pp.76–85. New York: ACM.

Fasolo

Zanella

Zorzi

. An effective broadcast scheme for alert message propagation in vehicular ad hoc networks. In: Proceedings of the IEEE international conference on communications, Istanbul, 11–15 June 2006, pp.3960–3965. New York: IEEE.

Sahoo

Sahu

et al . Binary-partition assisted MAC-layer broadcast for emergency message dissemination in VANETs. IEEE T Intell Transp 2011; 12(3): 757–770.

Suthaputchakun

Sun

Dianati

. Trinary partition black-burst based broadcast protocol for emergency message dissemination in VANET. IEEE T Veh Technol 2014; 63(6): 2926–2940.

Shan

Shen

et al . A multi-hop broadcast protocol for emergency message dissemination in urban vehicular ad hoc networks. IEEE T Intell Transp 2016; 17(3): 736–750.

Nie

Fan

et al . An efficient multi-hop broadcast protocol for emergency messages dissemination in VANETs. Chin J Electron 2017; 26(3): 614–622.

Hrizi

Bonnet

Harri

et al . Adapting contention-based forwarding to urban vehicular topologies for traffic safety applications. Ann Telecommun 2013; 68(5–6): 267–285.

10.

Wang

Cui

et al . Regular-hexagon-equilateral-triangle area grouping-based broadcast protocol for safety message in urban vehicular ad hoc networks. Int J Distrib Sens N 2017; 13(1): 1–12.

11.

Rayeni

Hafid

Sahu

. Dynamic spatial partition density-based emergency message dissemination in VANETs. Veh Commun 2015; 2(4): 208–222.

12.

Akabane

Villas

Madeira

ERM

. An adaptive solution for data dissemination under diverse road traffic conditions in urban scenarios. In: Proceedings of the IEEE wireless communications and networking conference, New Orleans, LA, 9–12 March 2015, pp.1654–1659. New York: IEEE.

13.

Berradj

Mammeri

. Adaptive contention window scheme to improve multi-hop broadcast in VANETs. In: Proceedings of the IEEE vehicular technology conference (VTC Spring), Glasgow, 11–14 May 2016, pp.1–6. New York: IEEE.

14.

Yoo

Kim

. ROFF: RObust and fast forwarding in vehicular ad-hoc networks. IEEE T Mobile Comput 2015; 14(7): 1490–1502.

15.

Chen

. Traffic engineering. 1st ed. Beijing: China Communications Press, 2014, pp.1–121.

16.

Hartenstein

Laberteaux

. A tutorial survey on vehicular ad hoc networks. IEEE Commun Mag 2008; 46(6): 164–171.

17.

Guo

Fei

Shen

et al . Partner based broadcasting for multi-hop emergency message dissemination in VANETs. In: Proceedings of the international conference on communications and networking, Shanghai, China, 15–17 August 2015, pp.879–882. New York: IEEE.

18.

Rehman

OMH

Bourdoucen

Ould-Khaoua

. Hybrid relaying for multi-hop broadcast in VANETs. In: Proceedings of the IEEE international conference on ubiquitous wireless broadband, Montreal, QC, Canada, 4–7 October 2015. New York: IEEE.

19.

Jin

Shi

Song

. Cluster based emergency message dissemination scheme for vehicular ad hoc networks. In: Proceedings of the 9th international conference on ubiquitous information management and communication (IMCOM ’15), Bali, Indonesia, 8–10 January 2015, pp.1–8. New York: IEEE.

20.

Jin

Shi

Song

. A traffic flow theory based density adopted emergency message dissemination scheme for vehicular ad hoc networks. In: Proceedings of the international conference on information networking (ICOIN), Siem Reap, Cambodia, 12–14 January 2015, pp.57–62. New York: IEEE.

21.

China Building Standard Highway Commission. Technical standards of highway engineering. Beijing: China Communications Press, 2014, pp.1–36.

22.

Jin

Wang

Shao

. The distribution of space headway under different traffic flow conditions. J Dalian Jiaotong Univ 2014; 35(1): 33–36.

23.

Luo

Huo

. A study on the distribution law of space headway. J Southwest Jiaotong Univ 2001; 36(2): 113–116.