1 Introduction

Currently, vehicular ad hoc network (VANET) has become an important research topic. The IEEE 802.11p [1], which provides enhancements to the physical (PHY) and medium access control (MAC) layers of the 802.11 protocol, has been published for VANET.

In most vehicular safety applications intended to propagate the safety-related information to all surrounding vehicles within a certain geographic area, multi-hop broadcasting is applied in VANET. Broadcasting in VANET requires high reliability and efficiency for delivering emergency messages. However, this requirement is not easily met, because packet acknowledgment, retransmission, and RTS/CTS handshaking are not usually used in broadcasting and the communications between moving vehicles face with serious interference and path fading. As well-known, The conventional broadcasting schemes such as blind flooding introduce the broadcast storm problem (BSP) [2] in VANET, where simultaneous broadcasting among neighboring nodes may lead to packet loss and collision. Therefore, it is important to design a reliable and efficient vehicle-to-vehicle broadcasting protocol to support safety applications. Broadcasting is one of the most active interests in the VANET research community [3].

There are three challenges of broadcasting in VANET. The first challenge is the BSP. To solve the BSP for Mobile Ad hoc Network (MANET), some broadcasting schemes, such as MPR [4], select some relay nodes to forward packets based on the premise that the transmission range of the relay nodes covers all two-hop neighbors of the sender. The Minimum Connected Dominating Set (MCDS) [5] is considered as one of the viable ways to address the BSP. Taking the advantage of linear topology, VANET just finds only one relay in the direction of transmission under the ideal channel condition instead of finding the MCDS. Most of the researches focus on the way that selects only one relay to transmit a packet by utilizing the contention of the receivers, which partially alleviates the BSP. However, multiple receivers contending the channel in a short period bring the Local Broadcast Storm Problem (LBSP), which will be discussed in Sect. 3. The second challenge is broadcasting time-sensitive messages. In a dense network, the speed of broadcast transmission can be considerably improved when the BSP is tackled. In a sparse network, the receiver contention based protocols [4, 6–9] introduce the Slow Reaction Problem (SRP) (discussed in Sect. 3) that brings a long delay. The third challenge is reliability. Because an emergency message is short compared to an RTS/CTS packet generally, most of the broadcasting schemes abandon the RTS/CTS and ACK mechanism and subsequently have low reliability.

In this paper, we propose an efficient multi-hop Sender-designated Opportunistic Broadcast Protocol (SOBP) for highway VANET. The scheme adopts the opportunistic broadcast mechanism which has multiple candidate forwarders (CF). It designates multiple CFs separated with a certain distance and assigns priorities to them before broadcasting a packet to avoid the possible collision in receivers. It can reduce the redundant transmission and keep the broadcasting overhead at a low level. It also avoids the LBSP and the SRP in dense and sparse network, respectively. Additionally, we analyze the average number of transmissions in a successful broadcast and propose the retransmission strategy to enhance the reliability. Simulations show that SOBP can achieve better performances than other broadcasting schemes.

The remainder of this paper is organized as follows. Section 2 introduces the related works in the field of broadcasting in VANET. Section 3 states the problems (i.e., the SRP and LBSP) that should be solved in this paper. Our proposed scheme is presented in Sect. 4. Next, Sect. 5 describes the simulation method in detail. Then we evaluate the performance in Sect. 6. Finally, the last section concludes this paper.

2 Related work

In the past few years, researchers have realized the importance of exploiting an efficient and reliable broadcast protocol for VANET. Many broadcasting schemes have been proposed to cope with the BSP.

In the counter-based [2] method, nodes cache each non-duplicate message and set a timer for it. The counter increases when the node overhears duplicate messages forwarded by its neighbors. If the counter exceeds a threshold when the timer expires, then the node gives up retransmission. The main drawback of the counter based method is that it cannot eliminate the redundancy of forwarding completely.

The Distance Defer Transmission protocol (DDT) is presented in [6] for message transmission, in which the defer time is set to inversely proportional to the distance from the source. In a distance-based scheme, as the density increases, the number of forwarders increases, resulting in more collisions. To alleviate this problem, p-IVG [10] keeps the forwarders almost constant by using a probability function that is inversely proportional to the density. Although p-IVG partially alleviates the LBSP, it still does not consider the SRP.

The probability based [2] methods simply let each node rebroadcast a packet with a fixed probability. A Weighted persistence (Weighted-p) probability based method is proposed in [7], where a receiver that is farther from the sender rebroadcasts the packet with a higher probability. But, this scheme exhibits a shortcoming of redundant broadcasting since the forwarding probability of the nodes close to the transmission border is too large, which arises from the phenomenon that the forwarding probability increases with the distance linearly.

Another broadcast technique (i.e., Slotted-1 persistence broadcasting), in which each node rebroadcasts the received message by using a preassigned time slot, is also proposed in [7]. In this scheme, the nodes locate in the farther region from the sender have a shorter waiting time. How to choose a precise number of slots is a difficult task in Slotted-1 persistence broadcasting because of the variety of traffic load.

Some protocols focus on MAC layer to design the broadcast protocol. They adopt revised RTS/CTS handshaking and ACK mechanism to enhance the performance.

In [8], a black burst broadcast scheme, called Urban Multihop Broadcast Protocol (UMB) is proposed, which needs Request to Broadcast/Clear to Broadcast (RTB/CTB) handshake before sending a data packet. First, the current relaying node broadcasts an RTB packet. Then, each receiver in the dissemination direction sends a channel jamming signal (black-burst) with the duration proportional to the distance from the sender. The furthest receiver wins the chance to reply a CTB packet by sending the longest black-burst and becomes the next relay node. Nevertheless, the UMB has two drawbacks: one is that the channel resource is greatly consumed by the jamming signal, and the other is that the relay node waits for the longest time before rebroadcast.

Similar to UMP, the position based multi-hop broadcast protocol (PMBP) proposed in [9] broadcasts a Broadcast RTS (BRTS) packet at each hop before sending a data packet. The transmission range of a sender is divided into several slots. All nodes which receive the BRTS set a defer timer according to the slot in which they locate. Therefore, the farthest node from the source defers the least time, and has the highest priority to reply a Broadcast CTS (BCTS) packet. To avoid collisions caused by the simultaneous reply of BCTSes, PMBP sets the size of a slot to the average length of vehicles so that each slot has only one vehicle. However, it cannot guarantee this goal in multiple-lane scenarios and more slots increase the latency, especially in sparse networks.

The revised RTS/CTS mechanism decreases the influence of the hidden node problem and accesses the channel to transmit packets point-to-point. However, it is not worth to use these mechanisms to avoid collision because an emergency message is short compared to a revised RTS/CTS packet. According to [11], the maximum bandwidth utilization of 802.11a with RTS/CTS handshake, at 54 Mb/s with payload size of 100 bytes, is less than 7 %. Moreover, point-to-point transmission does not make use of the broadcast nature that all the neighboring nodes may receive the packet successfully to enhance the efficiency of transmission even though without MAC layer collision.

The forwarders are decided by the contention of the receivers in the above protocols, while the others [4, 12–14] designate forwarders on the sender side. These schemes always need broadcasting “hello” packets periodically to collect the topology information about the network. MPR [4] restricts the number of forwarders to a small set of neighboring nodes instead of all neighbors and proposes one heuristic for the selection of multipoint relays. It is hard of MPR to keep the relay set small enough to reduce the number of redundant transmissions by efficiently selecting the neighbors which cover the two-hop radio range as the complete set of neighbors does. Finding the minimum relay set means finding the MCDS [5]. It is well known that finding the MCDS of a unit disk graph is NP-hard. To guarantee full delivery, MPR needs two-hop neighbor information.

Some sender-designated protocols [12–14] were designed for VANET specifically. In VRR [12], a sender chooses at most 4 MPR nodes (i.e., one in each direction) depending on their distances, motion vectors and speeds. Subsequently receiving node determines its priority to rebroadcast depending on whether it is an MPR node. If the node is a member of the set of MPRs, it sets up the shortest backoff time; otherwise, it then calculates its backoff time depending on the distance, motion vector and speed so that it can further reduce the collision probability. VRR mainly rely on the transmission of the non-MPR nodes in a dense network. However, the collision probability is very high as the non-MPR nodes have a small backoff range between 11 and 15. It means that the priority of the non-MPR node which rebroadcasts the packet successfully may be very low, i.e., the non-MPR node locates near the previous forwarder and waits for a long time to rebroadcast the packet. As a continuous work, the authors of VRR proposed an extension, namely SRMB, minimizing data collisions on forwarding broadcasts by using a dynamic slot wait time [13]. They also presented the Pseudo acknowledgments (PACK) mechanism to improve the reliability of broadcasting protocols. VMP [14] designates multiple CFs that have the same moving direction as the sender with different forwarding delay. There is no retransmission when the specified forwarders fail to transmit the emergency message, and the non-forwarder nodes will start to rebroadcast the message by exploiting the Slotted-1 scheme. The weakness of VMP is that the CFs may be close to one another and all of them would be interfered by hidden nodes. The absence of packet retransmission also decreases the probability of message’s reception [15].

The aforementioned schemes have an advantage in that they can partially mitigate the BSP and MAC layer collisions. However, one problem associated with these schemes is that they perform poorly in dense and sparse network because of the SRP and the LBSP.

3 Problem statement

In most of the distance-based broadcast protocols [6–9], the receivers decide whether to forward or not depending on the defer timer or the forward probability. The performance will be degraded by two problems as follows:

  1. 1.

    Slow Reaction Problem (SRP): In sparse network, two cases will cause the SRP. One is that all CFs are close to the sender. Another case is that all CFs are far from the sender, but they fail to receive the packet. The actual forwarder will wait for a long time to rebroadcast the packet or rebroadcast the packet with a low probability in both case. As shown in Fig. 1(a), C1–C3 are the CFs. If C1 does not exist in the network or it fails to receive the packet, C2 will wait for a long time to confirm whether it should rebroadcast, or it will rebroadcast with a low probability. The key point of this problem is that the defer timer or the forward probability of C2 is fixed regardless of the node density.

    Fig. 1
    figure 1

    Slow reaction problem and local broadcast storm problem of VANET broadcast protocol

    Full size image
  2. 2.

    Local Broadcast Storm Problem (LBSP): As shown in Fig. 1, we divide the area that behinds the sender with one-hop range into several blocks that have the same size by dashed lines. Nodes of the same block have a similar even equal backoff timer or forward probability. We define the block which contains much more nodes than other blocks as High Density Block (HDB) (e.g., the block 2 of Fig. 1(b) and block 1 of Fig. 1(c)). A network which has some HDBs is defined as a local dense network (LDN). The nodes are close to one another in HDB. They will contend to rebroadcast the packets acutely and cause LBSP: multiple packets have already been inserted to the queues for transmissions by the receivers when they overhear a copy transmitted by the winner. For Slotted-1 protocol, the defer time of lower priority node is shorter than the time which the higher priority node takes to suppress the redundant transmission. There are too many nodes which have the same defer timer to avoid collision in the same slot. Similarly, many nodes have a similar forward probability in Weighted-p protocol. LBSP makes the nodes of the same block cannot be distinguished effectively.

Due to the rapid changing topology, VANET becomes a LDN easily even though in one-hop range. A possible way of mitigating the LBSP is considering the node density of a network to design a broadcasting scheme. It means that the size of a block should be set depending on the node density. In Fig. 1(d), for example, the one-hop range is divided into 9 blocks which have at most two nodes. However, some empty blocks (i.e., block 4 and block 7) will bring a long delay. In Fig. 1(b), if a protocol divides the area into only 3 blocks, there are too many nodes in block 2; if it divides the area into more blocks, the original block 1 and block 3 will be divided into too many blocks that have little nodes and introduce the SRP. Additionally, the estimation of the density of a network for each node may be different from one another. As a result, the LBSP cannot be solved effectively by considering the density limited in one-hop range.

4 Protocol design

4.1 Protocol overview

The key challenge of MPR is to select a subset of neighbors that can cover all two-hop neighboring nodes. Because vehicles are assumed to be distributed along a one-dimensional freeway that its width can be ignored compared to transmission range, it is enough to choose one relay in the transmission direction in VANET. Some broadcasting schemes [4, 8, 9] try to greedily select the furthest neighbor as next hop. However, the expectant forwarder may be out of the transmission range of the sender because the position of neighbors based on an imprecise estimation. In [16], a smart next-hop selection algorithm has been proposed to alleviate this problem. Another problem is that the further the distance, the greater the likelihood of packet loss under the unreliable wireless channel. The transmission between a sender and an expectant forwarder may be executed several times for successful packet reception.

The broadcast nature of wireless channel makes all the neighboring nodes may receive the packet successfully or not. Exploiting the random packet receptions of the neighboring nodes can enhance the performance of the transmission. This fact brings the concept of opportunistic routing [17]. As shown in Fig. 2, the packet reception probabilities which decrease with distance are labeled on the curves. Traditional routing will forward data through some sub-sequence of the chain, for example SRC-B-D-DST. If a packet transmission from the source reaches farther than B, for example reaches to C, traditional routing cannot make use of that benefit. If a transmission just only reaches to A, the packet must be retransmitted by the source in traditional routing. Opportunistic routing, in contrast, can often take advantage of the broadcast nature of wireless media to achieve better progress at each hop. In the former case, C will forward the packet, allowing it to make some progress. In the latter case, A will forward the packet instead of the source’s retransmission.

Fig. 2
figure 2

An example of opportunistic routing

Full size image

Opportunistic routing can easily be adapted for broadcasting even though there is no specific destination for the packet. Considering the reliable transmission, we focus on the latter case mentioned above in VANET.

Based the idea of opportunistic routing, we propose a Sender-designated Opportunistic Broadcast Protocol called SOBP. SOBP is a multiple CFs broadcast scheme unrelated to node density. Similar to MPR, VRR and VMP, a sender of SOBP designates multiple CFs as a forwarding set (FS) and inserts it into the packet header. CFs in the FS follow a specific priority to rebroadcast the packet, that is, a CF will rebroadcast the packet only if it receives the packet correctly and all the nodes with higher priorities fail to do so. The sender will repeat the transmission when no CF has successfully rebroadcasted the packet. The actual forwarder will become a new sender and suppress all the other potential CFs. The new sender also chooses multiple CFs and repeats this process until the transmission reaches some limit (e.g., achieved distance, hop count or lifetime limited). To choose proper CFs, all vehicles are assumed equipped with Global Positioning System (GPS) receivers so that they can obtain the position information themselves. SOBP avoids the SRP and the LBSP effectively by choosing specific nodes as a FS.

4.2 Packet format

SOBP inserts a variable length header in each packet, as shown in Fig. 3. The SOBP header sits between the IP and UDP headers. Therefore, SOBP works at network layer and has more flexibility and compatibility. The header starts with a few required fields that appear in every SOBP packet. The fields Long and Lat denote the position of the current forwarder. We use the last four digits of the geodetic position represent the longitude (Long) and latitude (Lat) fields respectively [18]. For example, in the case of 120∘10.1234E and 30∘16.5678N they are represented as 1234 and 5678. The next field is Nc, the number of CFs. Following Nc, the fields Dir and Dis specify the broadcasting direction and the distance respectively. The last required field is the Ex, which is left for extension. The list of candidates has variable length and identifies all potential CFs ordered according to their priorities. Except for the Dir and Dis, all fields are set locally by each forwarder. In contrast, the Dir and Dis are initialized by the source and copied to the packets created by the forwarders.

Fig. 3
figure 3

Packet header

Full size image

4.3 Forwarding set selection

Most opportunistic routing protocols, such as ExOR [17] and LCOR [19], require global topology and link quality information to compute the routing metric and select the FS toward the destination strictly. Therefore, they are more suitable for static wireless mesh or sensor networks while SOBP, as an opportunistic broadcast protocol, is suitable for VANET because it needs only one-hop topology.

We assume that the packet reception is affected mainly by fading, noise and collision of hidden node. Therefore, the packet reception probability falls off with distance, and SOBP just use distance and direction as the metric to select FS. Each node periodically sends out beacon messages that include the position information to its neighbors so that SOBP can obtain one-hop topology information. According the position of the previous forwarder and the broadcast direction, current sender chooses the CFs by using a candidate selection algorithm. If the CFs are close to one another (e.g., VMP protocol), they would be collided by a hidden node easily. As shown in Fig. 4, if C1, C2 and C3 (i.e., the FS 1) are chosen as CFs while R is the one-hop transmission range, all of them will be collided by a hidden node with a high probability. To remedy this problem, SOBP selects the CFs separated with a certain distance. For example, the FS 2 is more effective than the FS 1 in Fig. 4.

Fig. 4
figure 4

The efficiency of forwarding set selection

Full size image

For a further description of our proposed approach, a pseudo code of the CF selection is presented in Algorithm 1. For simplicity, we assume that the nodes broadcast a message from a smaller position to a bigger position (i.e., from west to east in the simulations). We define the main variables used in the following:

  • R: expected average transmission range

  • i: the parameter of the interval between CFs

  • Position_N: the position of the processing neighbor

  • Position_S: the position of current sender

  • SR: the searching range of the CFs selection

  • Num_C: the required number of CFs

Algorithm 1
figure 5

candidate selection algorithm

Full size image

As illustrated in Algorithm 1, the protocol sorts the neighbors in a descending order first (line 1) then sets the searching range to the one-hop transmission range (line 2). The interval between CFs is computed through the parameter i and the average transmission range R (line 3). If a neighbor is found in the searching range, it will be chosen as a CF (line 7). The next CF must far from the current CF at least one “interval” (line 12). The process will continue until the number of CFs reaches the required number, or all eligible neighbors have been processed.

4.4 Priority scheduling

All CFs have different priorities with different forwarding delay in SOBP. A sender assigns the priorities to the CFs depending on their distances from the sender. It specifies that the value of first priority as 0, second as 1, third as 2, and so forth. Further CF gets higher priority (i.e., faster) to forward the packet. The CF, which receives the packet correctly, sets its timer based on its priority read from the header of the packet. Lower priority CF will cancel their impending transmissions when they hear a higher priority transmission to prevent redundant packet transmissions and collisions.

Given the priority of the CF, i, the defer timer Tdelay(i) can be easily calculated as

$$ \mathit{Tdelay}(i)=i\times\tau $$
(1)

where τ is the estimated one-hop delay, which includes the medium access delay and propagation delay. The sender also joins the forwarding process with the longest defer time which is calculated as that the real number of CFs multiplies the one-hop delay. As a result, the sender can retransmit the packet if all CFs fail to rebroadcast the packet.

The priority scheduling of SOBP avoids the SRP. As shown in Fig. 1(a), we assume that the first priority is assigned to C1 while the second priority is assigned to C2. If C1 fails to rebroadcast, C2 can rebroadcast after a one-hop delay no matter how far they are separated. The priority scheduling also solves the LBSP. Take advantage of the scheduling, the defer time of CFs never close to one another. It means that they will not transmit in a short period and sequentially solves the LBSP.

4.5 The size of forwarding set

Opportunistic routing increases a connection’s throughput while using no more network capacity than traditional routing and reduces the total number of transmissions in multi-hop wireless networks. However, the end-to-end delay introduced by the CFs should be considered in VANET. In opportunistic broadcast, though a lower priority CF has a higher packet reception ratio, it waits for a longer time to rebroadcast the packet. We assume there are k CFs for current forwarder. The ith CF, which has the packet reception ratio p, must wait for i−1 hops delay to rebroadcast the packet with probability p. Under the unreliable wireless channel, if k is too large, the CF which receives the packet successfully may has a very low priority which means that it must wait for a long time to rebroadcast. On the contrary, if k is temperate, even though all CFs fail to rebroadcast the packet, the kth CF (i.e., the sender) can retransmit the packet quickly with probability 1 to reduce the delay effectively. If k equals 2, SOBP retrogrades to the traditional routing. The opportunistic broadcast will become a receiver contention-based broadcasting scheme if the value of k is unlimited. It solves the LBSP because all timers of CFs are separated with one-hop delay. However, this method introduces a long forward delay with a high probability. Therefore, we need to strike a balance between the total number of transmissions and delay. In addition, more CFs make a bigger packet header and reduce the efficiency of the transmission. A proper value of the candidate number will be discussed in Sect. 6.1.

4.6 Retransmission

Because of high mobility, unreliable channel and the problem of hidden node, the broadcasting of VANET is unreliable [15]. The broadcasting reception ratio is still undependable even though using the opportunistic broadcast mechanism. We adopt the retransmission strategy in SOBP to increase the success ratio of the broadcasting. When the defer timer expires, a sender retransmits the packet. The retransmission limit will be discussed in Sect. 6.2.

As shown in Fig. 5, we define the ordered set of the CFs as

$$ F_{s,d}=\{s=0,1,2,\ldots,n-1,n=d\} $$
(2)

where s is a source node, d is a destination.

Fig. 5
figure 6

N candidate relays of the sender

Full size image

We define the probability that taking c transmissions to deliver a packet from i to j as p(i,j,d(i,j),c) where d(i,j) is the distance between i and j. Given the probability of successfully delivering a packet from i to j, p(i,j,d(i,j),1), the probability P that the source node needs to retransmit, i.e., all the CFs fail to receive the packet, can be expressed as

$$ P=\prod_{m=1}^n \bigl[1-p\bigl(0,m,d(0,m),1\bigr)\bigr] $$
(3)

Considering the distance between a sender and a receiver, Bai et al. [20] analyzed the probability PDR(r) that a receiver vehicle j successfully receives a packet from a sender vehicle i whereas the distance between them is r(r≤R). Assuming that the vehicles follow an exponential distribution with exponent λ, PDR(r) can be computed as

$$ \mathit{PDR}(r)=(1-p)e^{-2\lambda pR}e^{-2\lambda p\tau r} $$
(4)

where R is the intended average transmission range, p is the probability that each vehicle intends to transmit a packet at a given time slot and τ is the number of time slots to transmit a data packet. Replace r with d(i,j), we have the expression of p(i,j,d(i,j),1) when d(i,j)≤R. We ignore d(i,j) of p(i,j,d(i,j),1) to depict clearly in the following discussion.

We assume that a node retransmits a packet until successful delivery in our analysis model. The highest priority node that indeed receives the packet rebroadcasts the packet as an actual forwarder. Let Q(j,i−j) denotes the probability that the CF who becomes a forwarder in the jth transmission of the source node taking i−j transmissions to deliver a packet to the destination. The probability that the source node 0 taking i transmissions to deliver a packet to the destination node n can be expressed as

$$ p(0,n,i)=\left \{ \begin{array}{l@{\quad}l} p(0,n,1),&i=1\\ \sum_{j=1}^{i-1}P^{j-1} Q(j,i-j)\\ \quad{}+P^{i-1}p(0,n,1),&i\geq2\\ \end{array} \right . $$
(5)

When i≥2, the first term accounts for the probability that the packets of the foremost j−1 transmissions are dropped by all the CFs and the node who wins the chance to rebroadcast in the jth transmission needs i−j transmissions to deliver a packet to the destination; the second term represents the probability that the foremost i−1 transmissions fail to transmit (i.e., no node can receive any packets) and the destination receives the packet in the ith transmission.

To compute Q(j,i−j), we define with P l the probability that the highest priority CF that indeed receives the packet is l. Therefore, accounting for the statistical independence among the packet reception failure events, we have that:

$$ P_l=p(0,n-l,1)\prod_{k=0}^{l-1} \bigl[1-p(0,n-k,1)\bigr],\quad1\leq l \leq n-1 $$
(6)

Based on Eq. (6), we have

$$ Q(j,i-j)=\sum_{l=1}^{n-1} \bigl[P_lp(n-l,n,i-j)\bigr] $$
(7)

Substituting Eq. (7) into Eq. (5), p(0,n,i) can be expressed in Eq. (11) as a recursive form.

Then, we can calculate the expected number of transmissions in the case of opportunistic retransmission as

$$ E[TX]=\sum_{i=1}^{\infty}ip(0,n,i) $$
(8)

5 Simulation setup

We evaluate the effect of Flooding, Weighted-p, Slotted-1, VMP and VRR compared to our proposed scheme by using the ns-3 network simulator [21]. The authors of [7] suggested that the number of slots in Slotted-1 should be set adaptively depending on node density. However, the authors did not propose the method, so we use 10, 20, and ideal slots to evaluate the performance. The rule of “ideal slots” is that the length of the spatial slot adapts to the local vehicle density, which results in two nodes per slot on average. As a result, given the transmission range, R, the number of lanes, N l , the density of the vehicles, p, the number of ideal slots N i can be expressed as

$$ N_i=\rho RN_l/2 $$
(9)

While periodic beaconing is a necessary mechanism for many safety applications in VANET, each vehicle periodically sends out beacon messages (hello messages) to its neighbors at a default frequency of 1 Hz in all the protocol we simulate. In SOBP, we set the interval parameter i to 0.05. Table 1 lists the other relevant parameters of the protocols.

Table 1 Related parameters of protocols
Full size table

5.1 Highway scenarios and mobility model

Arbabi et al. [22] have implemented the highway mobility model which using the Intelligent Driver Model (IDM) and the MOBIL lane change model [23] in ns-3. The IDM, as a car-following model, is one of the microscopic models that adapt a following car’s mobility according to a set of rules to maintain a safe distance and avoid collision with the lead vehicles. Considering this model, we create two types of vehicles: sedan (desire velocity is 35 m/s) and truck (desire velocity is 25 m/s).Footnote 1 The roadway is a bidirectional 4 km highway with two lanes in each direction, and some vehicles are deployed on the road first according different densities. The inter-vehicle distances on the highway follow a nearly exponential distribution [20].

Some vehicles located in the western half of the highway are randomly chosen as the source nodes and send the messages from West to East. The simulation time is 15 s, and the first 5 seconds is warm up period. Each source node has two groups of broadcasting which begin with a jitter of 20 % at the 5th second and the 8th second, respectively. Each group sends one packet with the size 100 bytes every 100 ms until ten packets have been sent.

5.2 Radio propagation model

The work in [24] shows that the radio channel propagation modeling highly influences the performance of VANET communication protocols. Several studies, e.g., [15, 25], have shown that the realistic non-deterministic Nakagami-m fading model is a suitable channel model for simulation of highway scenarios. To simulate the realistic wireless environment, we use Two Ray Ground model and Nakagami-m model as the path loss model and the fast fading model, respectively.

The probability density function of Nakagami-m fading can be expressed as

$$ f(x)=\frac{2m^m}{\varGamma(m)\varOmega^m}x^{2m-1}e^{-\frac{m}{\varOmega }x^2}\quad x\geq0,\varOmega\geq0,m\geq\frac{1}{2} $$
(10)

where m is the shape parameter, and Ω controls the spread of the distribution. According to [15], we average m to 3 for short distance (≤50 m) between the sender and the receiver, decrease it to 1.5 for middle range distances, and make it 1 for distances higher than 150 m. We select 500 m as an intended transmission range in ideal conditions. Figure 6 shows the statistical average of 1000 simulation runs.

$$ p(0,n,i)=\!\!\left \{\! \begin{array}{l@{\quad}l} p(0,n,1),&i=1\\ \sum_{j=1}^{i-1}P^{j-1}\\ \quad\!\!\!\times\sum_{l=1}^{n-1}[P_lp(n-l,n,i-j)]\\ \quad\!\!\!+P^{i-1}p(0,n,1),&i\geq2\\ \end{array} \right . $$
(11)
Fig. 6
figure 7

The probability of reception of a packet with respect to the distance for Two-Ray ground and Nakagami-m model+Two-Ray ground

Full size image

5.3 IEEE 802.11p PHY/MAC

Table 2 lists the relevant parameters about 802.11p PHY/MAC used in simulations.

Table 2 Simulation parameters
Full size table

6 Performance analysis

We present the following metrics for comparing the performance of the protocols:

  • REachability (RE): the number of nodes receiving the broadcast message divided by the total number of nodes that are reachable, directly or indirectly, from the source node.

  • Saved ReBroadcast (SRB): (r−t)/r, where r is the number of the nodes receiving the broadcast message, and t is the number of the packets transmitted by the source node and the actual forwarders.

  • Average Packet Delivery Ratio (APDR): \(\frac{1}{N}\sum r/n\), where r is the number of the neighbors receiving the broadcast message in a single transmission, n is the number of all neighbors for an actual forwarder and N is the number of all transmissions. Two nodes are considered neighbors if and only if they can communicate each other directly.

  • Packet Dissemination Speed (PDS): The average distance which the message can reach in one millisecond. We use dissemination speed instead of traditional end-to-end delay just because of the different end-to-end distances in our simulation.

To check the performance of these protocols with different node densities and network traffics, we use three types of network traffic to run the simulation under varied densities. In low network traffic, 5 % of the vehicles generate the messages for broadcasting and 10 % in medium network traffic and 20 % in heavy network traffic.

6.1 Impact of candidate forwarder number

One factor that affects the performance is the size of a FS (i.e., the number of CFs). Figure 7 shows the RE with different densities and network traffics for different sizes of a FS. Three types of densities, low (5 vehicles/km/lane), medium (10 vehicles/km/lane) and heavy (20 vehicles/km/lane), are used to validate the impact. When SOBP uses only one CF to broadcast the messages, it works like unicast and gets very low performance. If the number of CFs is over three, it obtains a significant improvement of RE. However, the RE gains by increasing the number of CFs would become marginal. Moreover, the size of a packet is also expected to grow with the size of a FS. Obviously, larger packet needs more time to be transmitted and gets more chance to be collided. Therefore, there is a critical value for the CF number. Figure 7(c) provides an example. The RE of the case using 7 CFs is 98.61 % with density 20. While using 10 CFs, the RE decreases to 97.61 %.

Fig. 7
figure 8

Impact of candidate forwarder number on Reachability at different network traffics: (a) low load; (b) medium load; (c) heavy load

Full size image

As shown in Fig. 8, the packet dissemination speed declines with the CF number gradually. There is a tradeoff relation between the PDS and the RE for the CF number. According to the simulations, 5 is a proper value to balance these performances. We choose 5 as the CF number in the following simulations.

Fig. 8
figure 9

Impact of candidate forwarder number on Packet Dissemination Speed at different network traffics: (a) low load; (b) medium load; (c) heavy load

Full size image

6.2 Impact of retransmission limit on reachability

We compare the RE of SOBP with different retransmission limit for such a scenario in Sect. 6.1. For ease of the following discussion, we assume MaxRetries to be the retransmission limit (i.e., the maximum number of retransmission). Figure 9 shows the RE results. Similar to the impact of CF number discussed in Sect. 6.1, the RE gains by increasing the MaxRetries would become marginal. In SOBP, the CFs that receive the broadcasting messages wait until the defer timer expires and then rebroadcasts. The previous forwarder may overhear this rebroadcasting and consider it as a pseudo acknowledgement (PACK) [13]. To investigate the impact of retransmission, we collected the unacknowledged rates and the percentages of retransmissions by using a simulation with MaxRetries=3. The unacknowledged rate contains three parts: (1) the CFs fail to receive the packet; (2) the previous forwarder does not overhear the rebroadcasting; (3) the CFs discard the redundant packet silently without acknowledging the previous forwarder. So missing the PACK does not mean failed transmission. The results in Table 3 show that the unacknowledged rates are fairly high across all scenarios (>60 %) because of the unreliable wireless channel. Table 4 provides insights into the effect of retransmission. We observe that the retransmission rates are lower than the unacknowledged rates. The reason is that the MaxRetries is reached after several retransmissions.

Fig. 9
figure 10

Impact of retransmission limit on Reachability at different network traffics: (a) low load; (b) medium load; (c) heavy load

Full size image
Table 3 Unacknowledged rates
Full size table
Table 4 Percentages of retransmissions
Full size table

The retransmission principle of SOBP will cause a few redundant transmissions. For example, node A specifies node B as a CF, but it does not overhear the PACK from Node B and sends a redundant rebroadcasting. Moreover, node B would not reacknowledge the redundant transmission and node A would repeat the rebroadcasting until it reaches the limit. A few redundant transmissions are useful for increasing reliability. However, excess retransmission introduces too many collisions. Therefore, the maximal number of retransmission cannot be indefinitely large. Our implementation limits it to 3.

6.3 REachability (RE)

Figure 10 shows the RE with different densities and network traffics. The RE of all protocols ups to 95 % except Flooding and Weighted-p under the moderate density (i.e., 5–15 vehicles/km/lane). The RE of SOBP, Slotted-1-10, Slotted-1-20, VMP and VRR almost achieve to 100 % while Slotted-1-ideal has the worst performance when the density is less than 5. The reason is that although only two nodes in each slot on average, the transmission range is divided into only one or two slots. The broadcast process would be disrupted by the collision of the nodes located in the same slot with a high probability. Broadcasting needs more slots to guarantee the reliability. We can conclude from this that Slotted-1-x protocols is sensitive to the density of the nodes and Sender-designated protocols such as SOBP, VMP and VRR can solve the SRP effectively. In dense network (i.e., density is larger than 15), all protocols have a good performance except Flooding when the network traffic is low (see Fig. 10(a)). Only SOBP, VRR, Slotted-1-20 and Slotted-1-ideal keep the level of good performance in the moderate network traffic (see Fig. 10(b)). With the same density, the performance of all protocols is declining when they suffer from heavy network traffic that can be seen from Fig. 10(c). The reason for receiver contention-based protocols (i.e., Weighted-p and Slotted-1-x) is that many nodes have the chance to rebroadcast the massages in dense network leads to a high probability of collision. The performance of SOBP declines slowly and its lowest RE still up to 91.6 %. In contrast, the RE of VMP falls sharply because other receivers would go into the contention phase when the designated CFs fail to rebroadcast the packet. This phenomenon easily occurs in high node density and heavy network traffic. The absence of retransmission also contributes to the deterioration of the performance. Although the non-MPR nodes would go into the contention phase like VMP, the rebroadcasting of VRR is carefully scheduled using different priorities so that it can still get a high RE.

Fig. 10
figure 11

Reachability at different network traffics: (a) low load; (b) medium load; (c) heavy load

Full size image

6.4 Saved ReBroadcast (SRB)

Obviously, the SRB of Flooding always equals 0 as shown in Fig. 11. Flooding assumes that all neighbors within the transmission range of a sender rebroadcast the received messages to guarantee reliable delivery to all reachable nodes. As the prominent LBSP, Weighted-p introduces many redundant transmissions which lead to low SRB for any cases. Low SRB may cause low APDR that can be seen from Fig. 12. In the case of Slotted-1-x, the SRB is generally higher than that of the Weighted-p case. This is due to the nodes which have a chance to forward packets are limited at foremost slots. However, the SRBs of slotted-1-ideal are lower than other Slotted-1-x protocols in low density. It demonstrates that the slot number of slotted-1-ideal is not real ideal. The optimal slot number relies on the node density seriously.

Fig. 11
figure 12

Save Rebroadcast at different network traffics: (a) low load; (b) medium load; (c) heavy load

Full size image
Fig. 12
figure 13

Average Packet Delivery Ratio at different network traffics: (a) low load; (b) medium load; (c) heavy load

Full size image

Generally, the number of forwarders would increase with node density. As a result, broadcasting overhead becomes heavier and sequentially, PDS and APDR would deteriorate quickly. In SOBP, the number of CFs is constant and only one CF can become an actual forwarder to rebroadcast a packet. Thus, SOBP prevents the increase of the number of forwarders and its SRB also goes up as node density rises for all network traffics. It can be seen from Fig. 11(a), (b) and (c) that the shape and the position of SOBP curves are nearly the same. For example, the SRB of three type’s network traffic are 70.7 %, 70.22 % and 69.17 % for density 3, and 94.53 %, 94.16 % and 93.25 % for density 30. Because of the constant number of forwarders, the number of packets which are injected into the network by SOBP remains constant regardless of the node density. This advantage of SOBP becomes more prominent as the node density and network traffic increase. SOBP completely solves the LBSP.

Inversely, the SRB of Slotted-1-x protocols drop gradually in the case of high density and heavy network traffic (see Fig. 11(c) for density 20–30) except Slotted-1-ideal whose SRB remains steady at 79 %. Although VRR can get a high RE, it wastes many transmissions in the collision of the non-MPR nodes with higher priority. As a result, its SRB is lower than SOBP in any cases. Due to the mechanism, the sender designates the forwarders, plays an important part in the packet forwarding when the density is low, the performance of VMP is similar to SOBP. However, the packet reception ratios of CFs gradually decline as the density of the network increases, VMP turns to Slotted-1 protocol and the performance declines quickly like Slotted-1-x protocol.

6.5 Average Packet Delivery Ratio (APDR)

The APDR is mainly affected by two factors: radio propagation model discussed in Sect. 5 and the collision of packets. Obviously, a high rebroadcast ratio (i.e., low SRB as shown in Fig. 11) causes high contention at the link layer and leads to high overhead of the network and sequentially cause low APDR. Low APDR poses serious problems to other applications, because any urgent messages transmitted pass to this area get lost with a high probability because of link layer contention. From Fig. 12, it can be seen that the APDR of SOBP is higher than other protocols in any case. The communication overhead injected by SOBP is about the same in any case. It can sustain the same performance level. Consequently, low SRB leads to low APDR in Flooding and Weighted-p.

Because more slots can reduce more redundant transmission (i.e., higher SRB) in Slotted-1-x, the APDR of Slotted-1-20 is better than that of Slotted-1-10 for all cases. According to the rule of “ideal” and our simulation parameters, the number of slots equals the value of density. It can be seen from Fig. 12 clearly that the performance of Slotted-1-ideal is better than that of Slotted-1-10 when the density is larger than 10. It is also better than Slotted-1-20 when the density is larger than 20. Like SRB, the APDR of VMP is similar to SOBP when the density is low and drops quickly as Slotted-1-x when the density is high. Since Flooding, Weighted-p and VRR inject abundant packets into the network, they get low APDRs that respond to the result of Fig. 11.

The above results show that the link load gradually increases as the number of forwarders increases dues to high node density and heavy network traffic for contention-based protocols. Taking the advantage of the fixed CF number, SOBP reduces the redundant packets effectively even though in high node density and heavy network load.

6.6 Packet Dissemination Speed (PDS)

Finally, we study the PDS that can be observed from Fig. 13. Flooding transmits the packet quickly in low density. This is mainly attributed to the high probability of that the packets are rebroadcasted successfully by the furthest potential forwarder. However, the PDS of Flooding fall as the highest speed due to the more redundant forward. When the density is low, Weighted-p and Slotted-1-20 have the worst performance mainly because of the prominent SRP. The forwarders may be close to the sender and they will rebroadcast the packet with a low probability in Weighted-p. As a result, the average one-hop transmit distance is short and the PDS is slow. Similarly, they will wait for a long time to rebroadcast the packet in Slotted-1-20 and lead to a long average one-hop delay. Slotted-1-10 and Slotted-1-ideal perform better as the number of slots reduces. Because a CF waits for the same delay (i.e., estimated one-hop delay) irrespective of its distance from the sender, SOBP also keeps the good performance in sparse network.

Fig. 13
figure 14

Packet Dissemination Speed at different network traffics: (a) low load; (b) medium load; (c) heavy load

Full size image

It can also be observed that there is a clear performance deterioration for these protocols when the density and network traffic increase except SOBP. VMP has the similar action with Slotted-1-x in high density and heavy network traffic. Therefore, its performance level is the same as Slotted-1-x’s. We can see from Fig. 13(b) and (c) that assigning more slots in Slotted-1-x has little effect on the LBSP. When the density equals 30 and network traffic equals 20 %, Slotted-1-ideal has the best performance except VRR and SOBP. The results are: SOBP, 223.28 m/ms, VRR 24.74 m/ms, Slotted-1-ideal, 8.22 m/ms, Slotted-1-20, 5.85 m/ms, VMP, 2.84 m/ms, Slotted-1-10, 2.58 m/ms, Weighted-p, 1.95 m/ms and Flooding, 0.6 m/ms. For VRR, the collision probability is very high at non-MPR nodes, resulting in low PDS. Giving up the contention of the low priority non-MPR nodes and using the repeat broadcasting of the previous forwarder is more efficient because the unique previous forwarder can wait for a short time to repeat the collision free transmission. For SOBP, it diminishes the number of redundant packets and reduces the load of the link effectively by assigning a fixed number of CFs. For this reason, the dissemination speed is still larger than 200 m/ms with SOBP. SOBP avoids the LBSP simply.

7 Conclusions and future work

In this paper, we investigate the Slow Reaction Problem (SRP) and the Local Broadcast Storm Problem (LBSP) in sparse and dense VANET, respectively. We also analyze the average number of transmissions under the opportunistic broadcast protocol. Then we present an efficient multi-hop Sender-designated Opportunistic Broadcast Protocol (SOBP) for highway VANET. Unlike other studies, SOBP injects the same load into the network regardless of the node density.

We compare the performance of SOBP with existing broadcasting schemes by using ns-3. Results show that SOBP can solve the SRP and the LBSP effectively and outperform existing solutions in terms of reachability, saved rebroadcast, average packet delivery ratio, and packet dissemination speed. The main advantages of SOBP are summarized as follows: (1) It utilizes the concept of opportunistic routing to enhance the efficiency of a single transmission and does not require any specific assumptions about the network topology and link statistics that are hard to estimate. (2) It takes the advantage of the linear topology of VANET to select candidate forwarders. Because the number of these candidates is fixed and their priorities are predetermined, candidates are collision free and only one candidate to rebroadcast the packet finally. SOBP changes broadcast into “unicast” whose destination is extended to multiple candidates and solves the BSP and the LBSP. (3) It adopts the retransmission strategy to enhance the reliability of broadcasting while using fewer packets to rebroadcast. (4) It sets the parameters irrespective of the node density and maintains a consistent performance level in all node densities. Because of the fixed number of candidates, SOBP can fix the SRP and the LBSP in sparse and dense network, respectively.

In the future work, the selection of candidates can be further improved by considering more characteristics of VANET and the network traffic. Moreover, future work involves developing a new SOBP protocol that supports more common scenarios such as curve highways, rural scenarios and city’s environments [18].