Sage Journals: Discover world-class research

Abstract

A neighbor knowledge-based broadcast scheme is proposed to reduce the latency for wireless ad hoc networks, yet keeping the overhead at a reasonably low level and fulfilling the reliability. In the scheme, few Hello messages are interchanged to collect one-hop neighbor information. The collected information is used to calculate the neighbor density, the ratio, and the number of one-hop uncovered neighbors, upon which the rebroadcast probability and delay are adjusted adaptively. The way that the rebroadcast probability and delay are defined in neighbor knowledge-based broadcast scheme reduces the transmission overhead and restrains the traffic aggregation effectively. Next, a velocity-based data distribution mechanism is proposed and extended to neighbor knowledge-based broadcast scheme to further reduce the latency, forming neighbor knowledge and velocity-based broadcast scheme. It is stipulated that few higher-velocity nodes are employed with bigger probability to rebroadcast the incoming message. The performance of the schemes is evaluated by the simulation under diverse network configurations. The results show that they outperform the existing broadcast schemes in overhead and especially in average end-to-end delay. Compared with flooding, they reduce the overhead by 88.4% and the average end-to-end delay by 88.9% at most.

Keywords

Wireless ad hoc networks rebroadcast probability rebroadcast delay normalized broadcast overhead average end-to-end delay packet delivery ratio

Introduction

Broadcasting is a communication primitive in wireless ad hoc networks. It is essential to resolve many issues such as route discovery, route maintenance for unicast or multicast and emergency or warning message dissemination in disaster, battlefield, and VANET scenario. In some harsh conditions, an efficient broadcast mechanism is vital and may be the only possible way to disseminate crucial information.¹ Because radio signals are likely to overlap with each other in a same geographical area, a straightforward broadcasting by flooding is usually very costly and will result in serious redundancy, contention, and collisions, to which is referred as the broadcast storm problem.² Thus, during the past decades, broadcasting has attracted much attention of the research groups. Many kinds of broadcast schemes were proposed to minimize the number of transmissions while attempting to ensure a high reliability and a low latency.

Besides blind flooding,^3,4 a basic classification of broadcast schemes divides them into two main categories: probabilistic broadcast scheme and deterministic broadcast scheme.^1,5,6 The probabilistic broadcast scheme includes probability-based schemes,^2,7–11 counter-based schemes,^12–16 distance-based schemes,^17–23 and location-based schemes.^24–27

Probabilistic schemes do not need any information from the whole network and need not maintain a global distributing topology, but, rather, start of building a network with each broadcast domain. In probabilistic schemes, all nodes are allowed to participate in the broadcast process and forward the received broadcast message with some probability. Therefore, the traffic load would not aggregate on a part of nodes. Furthermore, the interest in probabilistic broadcasting schemes is due to their inherent low transmission overhead, low processing complexity, low delay, and high tolerance to frequent and rapid topological changes. Balancing these benefits, though, is the disadvantage of inability to guarantee full network coverage and, still, the presence of some redundant transmissions.

Deterministic broadcast scheme includes tree-based scheme,^28–31 connected dominating set (CDS), and neighbor elimination-based scheme.^32–41 Tree-based schemes construct a routing tree on which broadcast messages are forwarded. In tree-based scheme broadcast redundancy minimization scheduling (BRMS),³¹ a set of forwarding nodes are found first to minimize the number of broadcast transmissions. Then, the scheme constructs a forest of sub-trees based on the relationship between each forwarding node and its corresponding receivers. Finally, a broadcast tree is constructed by connecting all sub-trees with a minimum number of connectors. CDS and neighbor elimination-based schemes maintain state on the neighborhood of each node, via “Hello” packets. Upon the collected neighbor information, each node decides its role (forward node or non-forward node) in a specific broadcasting. For example, in local broadcast algorithms (LBA)³⁸ proposed by Majid Khabbazian, every broadcasting node selects at most one of its neighbors to rebroadcast the received message. A node has to rebroadcast the received message if it is selected to do. Other nodes that are not selected have to decide whether to rebroadcast upon a self-pruning condition called the coverage condition. To evaluate the coverage condition, every node u maintains a list ${List}_{u}^{cov} (m)$ for every unique message m. When node u receives a fresh message m for the first time, ${List}_{u}^{cov} (m)$ is initialized and filled with the IDs of all neighbors of u. ${List}_{u}^{cov} (m)$ is updated before the rebroadcast delay ends, namely, the IDs of neighbors covered by m are being removed from ${List}_{u}^{cov} (m)$ during the rebroadcast delay. Finally, if ${List}_{u}^{cov} (m)$ is not empty, u will rebroadcast m and select one node still in the list to be the next forwarder. Deterministic schemes use topological information to build a global forwarding structure to reduce broadcast redundancy. They can be proven to not degrade reachability compared with flooding and probabilistic schemes, provided communications are perfectly reliable. However, they do not tolerate frequent topological changes well, because maintaining the forwarding structure in dynamic environment brings excessive control overhead. In high mobile environment, deterministic schemes could not provide higher reachability than probabilistic schemes do.

First, we proposed a neighbor knowledge-based broadcast (NKB) scheme for wireless ad hoc networks. In NKB scheme, few Hello messages are interchanged between one-hop neighbors to collect the neighbor information. The rebroadcast probability and the rebroadcast delay on each node are adjusted adaptively according to the obtained neighbor knowledge including the neighbor density, the ratio, and the number of one-hop uncovered neighbors. Second, a velocity-based data distribution mechanism is proposed and extended to NKB scheme to reduce the latency further, forming neighbor knowledge and velocity-based broadcast (NKVB) scheme. In NKVB scheme, few higher-velocity nodes are employed with bigger probability to forward the broadcast message, which makes NKVB different from NKB scheme, and they do accelerate the data transmission.

The rest of the article is organized as follows. Section “Related work” presents a brief review of broadcast schemes. Section “NKB scheme” presents NKB scheme. The velocity-based data distribution mechanism and NKVB scheme are presented in section “NKVB scheme.” Performance evaluation of NKB and NKVB schemes by simulations in the context of wireless ad hoc networks is presented in section “Performance evaluation.” Finally, section “Conclusion” concludes the article.

Related work

Probabilistic broadcast schemes only need to maintain rough local topology knowledge, which makes it more insensitive to node mobility than deterministic broadcast schemes. Probability-based schemes^2,8 use some basic understanding of the network topology to assign a constant forwarding probability to each node to rebroadcast. The fixed probability schemes do not need to collect the beacon information, including density, speed, and energy, and so on, upon which the optimal rebroadcast probability is calculated in the adaptive probability schemes.¹ GOSSIP1(p)⁸ is a pure gossip scheme with the fixed rebroadcast probability. When a node first receives a route request, with probability p, it broadcasts the request to its neighbors and with probability 1 – p, it discards the request. If the node receives the same route request again, it is discarded. The fixed probability schemes cost less control overhead. But the constant rebroadcast probability makes the schemes function not so well in dynamic and asymmetrical network environment. In reliable gossip-based broadcast protocol (RGB)⁷ and velocity and neighbor density-based broadcast scheme (VDNB),¹¹ the dynamic rebroadcast probability is calculated upon the immediate number of neighbors of the node. Compared with the fixed probability schemes, they are more suitable for wireless ad hoc networks.

In dynamic counter-based broadcasting scheme (DCB),¹⁵ the number of neighbors is used to determine whether the node is located within dense, medium distribution or sparse regions and assign C_min, C_mid, and C_max thresholds, respectively. Each node needs to wait for a random assessment delay. Within the delay, the number of copies of the message received by a node is compared with C_min, C_mid, and C_max, and then the corresponding one of four different rebroadcast probabilities is assigned to the node. In Humoud et al.,¹³ only two thresholds, unlike in Yassein et al.,¹⁵ are used to evaluate the node distribution and the rebroadcast probability is rougher. In Tseng et al.,¹² the decision to forward the broadcast message is determined by the function C(n) where n is the number of neighbors of the forwarding node.

In distance-based broadcast scheme,¹⁷ whether a message is rebroadcasted or not is up to the relative distance between the mobile node and the previous sender. When a node receives a broadcast message from a neighbor node for the first time, its d_min is initialized with the distance between them and the count is initialized with 1. If d_min < D (where D is the distance threshold pre-defined), the node stops rebroadcasting. Else, the node waits for a random number of slots, during the waiting period, every time a copy of the broadcast message is received, d_min and D are reassigned correspondingly. If d_min < D, the node stops rebroadcasting. Else, if the waiting time is expired, the node rebroadcasts the received message. In distance and cooperation based broadcast (DCBB),²³ four neighbor nodes at most are determined to forward broadcast packets based on the number of neighbors and the distance between neighbors. The limited number of relay nodes is helpful to reduce the redundancy of the scheme. DCBB is applicable to densely distributed network environment.

In location-based broadcast schemes,^26,27 the rebroadcast probability of a node is in positive correlation with its additional coverage ratio. In order to figure out an accurate additional coverage ratio, the rebroadcast delay is set without exception on each node to collect enough neighbor coverage information. In scalable broadcast algorithm (SBA),²⁶ three node-stamping broadcast algorithms, named basic stamping, advanced stamping, and hybrid stamping, are proposed. Each node in advanced stamping algorithm collects its one-hop neighbor information. IDs of each forwarding node and its neighbors are appended to stamp in advanced stamping scheme. When node r receives a broadcast message m for the first time, it uses the stamp of m to check whether all its neighbors N(r) are already covered. If so, the rebroadcast is stopped; otherwise, node r appends id(r) and id(N(r)) to the stamp and schedules for rebroadcasting. Hybrid stamping utilizes two-hop neighbor information for pruning. With hybrid stamping, each node further checks whether some of its neighbors can also be reached by other nodes in the stamp. When node r receives a new message m, it checks whether its neighbors N(r) are all contained in the stamp of m first. For each neighbor n not contained in the stamp, node r then tries to check whether a neighbor p in N(n) is in the stamp. If node p has a higher priority than node r, node r can assume node n will be covered by broadcasting from node p or node with an even higher priority. If all uncovered neighbors in N(r) will be covered by node with higher priority, the rebroadcast is stopped by node r; otherwise, node r appends id(r) and id(N(r)) to the stamp and schedules for rebroadcasting.

In neighbor coverage-based probabilistic rebroadcast (NCPR),²⁷ the proportion of the common neighbors between node n_i and its upstream node s uniquely determines the rebroadcast delay T_d(n_i) of node n_i, and the rebroadcast delay of node n_i is defined as follows

T_{d} (n_{i}) = M a x D e l a y \times (1 - \frac{| N (s) \cap N (n_{i}) |}{| N (s) |})

(1)

where MaxDelay is a small constant delay; N(s) and N(n_i) are the neighbor sets of node s and n_i, respectively. |.| is the number of elements in a set. In NCPR, another parameter, the connectivity factor, is defined to provide the node density adaptation. The connectivity factor F_c(n_i) and the additional coverage ratio R_a(n_i) of node n_i are defined as follows

F_{c} (n_{i}) = \frac{N_{C}}{| N (n_{i}) |}

(2)

R_{a} (n_{i}) = \frac{| U (n_{i}) |}{| N (n_{i}) |}

(3)

where N_c = 5.1774 log n, and n is the number of nodes in the network. |U(n_i)| is the number of uncovered neighbors of node n_i. By combining the additional coverage ratio and the connectivity factor, the rebroadcast probability of node n_i is calculated as follows

P_{re} (n_{i}) = F_{c} (n_{i}) \cdot R_{a} (n_{i})

(4)

The proposed rebroadcast delay is one of main contributions of NCPR. It determines the rebroadcast order, and then the more accurate additional coverage ratio is obtained.²⁷ We found that, in NCPR, more neighbors a node has, more likely it is to rebroadcast the message in less time. Namely, the way that the rebroadcast delay and the rebroadcast probability are calculated is inclined to incur the traffic aggregation.

In NKB scheme, we focus on defining the rebroadcast delay and the rebroadcast probability more reasonably to balance the traffic load, reduce the collisions and lower the end-to-end delay, which improved the reliability and the scalability of the scheme. For adaptability purpose in mobile environment, for example in disaster and battlefield scenario, few higher-velocity nodes are employed with bigger probability to rebroadcast the message in enhanced NKVB scheme, which lowers the delay further.

NKB scheme

In NKB scheme, the rebroadcast probability is adjusted adaptively at each node according to its neighbor knowledge. The neighbor knowledge includes the ratio of uncovered neighbors, the number of uncovered neighbor, and the neighbor density. The neighbor knowledge is obtained at each node by exchanging Hello message. In order to sufficiently pursue lower average end-to-end delay, exploit more accurate uncovered neighbors set, and avoid channel collisions, a proper rebroadcast delay is set at each node.

For research purpose, the network can be represented by an undirected graph $G = (V, E)$ , where V is a set of vertices (nodes) and E is a set of undirected edges. An undirected edge (n_i, n_j) denotes the connection between two neighboring nodes n_i and n_i. The neighbor set N(n_i) of node n_i is defined as ${n_{i} | (n_{i}, n_{j}) \in E}$ . |N(n_i)| denotes the number of elements in set N(n_i).

Collection of neighbor information

Hello message is used to collect a node’s one-hop neighbor information in NKB scheme. To reduce the overhead of Hello message, piggybacking is used. Moreover, piggybacking of the Hello message by broadcast packet could make the neighbor information fresher. Only when the time elapsed from the last broadcasting packet is greater than a Hello Interval, the node needs to send a separate Hello message.

In NKB, Hello message of node n_i includes the following:

N(n_i): a neighbor list of node n_i;

M(n_i): an ID list of broadcast messages received;

flag_leaf: if node n_i is a leaf node, flag leaf is set to 1. Otherwise, this field is excluded from Hello message.

Definitions

leaf node: A leaf node has only one neighbor; it is a special kind of node who locates at the boundary.

secondary leaf node: It is a kind of node who is the neighbor of a leaf node.

Uncovered neighbors set

When node n_i receives a fresh broadcast message from the upstream node n_s, their common neighbors receive it too because of the broadcast nature of radio communication, as shown in Figure 1. Upon both node n_s’s neighbor list and its own neighbor list collected by the Hello message, node n_i can figure out who are their common neighbors and deduce its uncovered neighbors set. If node n_i has more neighbors uncovered by the broadcast message, it is reasonable for node n_i to rebroadcast the message with a bigger probability. The uncovered neighbors set U(n_i) of node n_i is defined as follows

U (n_{i}) = N (n_{i}) - [N (n_{i}) \cap N (n_{s})] - {n_{s}}

(5)

where N(n_i) and N(n_s) are the neighbor sets of node n_i and n_s, respectively.

Figure 1.

Neighbor set and uncovered neighbors set.

In NKB scheme, each node sets a rebroadcast delay (defined in section “Rebroadcast delay”) when it receives a fresh broadcast message, to exploit its accurate uncovered neighbors set. When node n_i receives a duplicate message during the rebroadcast delay, for example from its neighbor node n_j, node n_i should update its uncovered neighbors setU(n_i) according to formula (6). The uncovered neighbors set U(n_i) is being updated until the rebroadcast delay expires

U (n_{i}) = U (n_{i}) - [U (n_{i}) \cap N (n_{j})] - {n_{j}}

(6)

Rebroadcast probability based on neighbor knowledge

In proposed broadcast scheme, the neighbor knowledge, including the ratio of uncovered neighbors, the number of uncovered neighbors, and the neighbor density, is used to calculate the rebroadcast probability at each node.

Ratio of uncovered neighbors

As soon as the rebroadcast delay expires, node n_i will calculate the ratio of uncovered neighbors R_u(n_i) as follows

R_{u} (n_{i}) = \frac{| U (n_{i}) |}{| N (n_{i}) | - 1}

(7)

where |.| is the number of elements in a set and |N(n_i)| – 1 is the number of node n_i’s neighbors excluding the upstream node n_s.

If node n_i has a big ratio of uncovered neighbors, it is reasonable for n_i to rebroadcast the received message with a big probability to cover more fresh nodes. On the contrary, if node n_i has a small ratio of uncovered neighbors, the smallest possible rebroadcast probability should be adopted by n_i to reduce redundancy and collisions without hurting the packet delivery ratio.

Density factor and absolute number of uncovered neighbor factor

We assume that node n_h and n_i are neighbors of the upstream node n_s and receive the same broadcast message from node n_s. If they have the same ratio of uncovered neighbors but the different numbers of uncovered neighbors, it is reasonable for the node with more uncovered neighbors to rebroadcast the message with a bigger probability. Even when a node has a small ratio of uncovered neighbors, but a big absolute number of uncovered neighbors, it is worth rebroadcasting the message with a big probability.

Besides the number of uncovered neighbors, the neighbor density also affects the rebroadcast probability. When node n_i is in a denser area, a smaller rebroadcast probability adopted avails to reduce the redundancy and the collisions. However, a bigger rebroadcast probability should be adopted to keep a higher packet delivery ratio in a sparser area.

Xue and Kumar⁴² concluded that if each node connects to more than 5.1774 log^N of its neighbors, then the probability of the network being connected is approaching 1 as N increases, where N is the number of nodes in the network. We use 5.1774 log^N, denoted by N_c, as a reference value to evaluate the absolute number of uncovered neighbors and the neighbor density. The density factor d(n_i) and the absolute number of uncovered neighbor factor F_u(n_i) are defined as follows

d (n_{i}) = \frac{| N (n_{i}) |}{N_{C}}

(8)

F_{u} (n_{i}) = \frac{| U (n_{i}) |}{N_{C}}

(9)

Rebroadcast probability based on neighbor knowledge

Combining the ratio of uncovered neighbors, the absolute number of uncovered neighbor factor, and the density factor, we have node n_i’s rebroadcast probability p_k(n_i) based on its neighbor knowledge

p_{k} (n_{i}) = \frac{β \cdot R_{u} (n_{i}) + (1 - β) \cdot F_{u} (n_{i})}{d (n_{i})}

(10)

where β and (1 – β) are the influence coefficients of R_u(n_i) and F_u(n_i), respectively. If p_k(n_i) is greater than 1, we set p_k(n_i) to 1. The value of β is related to node density and node distribution. In even and dense network, a big value of β assigned benefits reducing the collisions and the delay, and upgrading the reliability. A small value of (1 – β) is helpful to improve the packet delivery ratio in sparse area. A number of experiments, which are not emphases mentioned here, were done to prove it. And as a result, the empirical value of β is set to 0.8 in the following simulation in section “Performance evaluation.”

But, if node n_i is an uncovered secondary leaf node, whose leaf node is n_j as shown in Figure 2, it should rebroadcast the message with probability 1 for node n_j. In addition, n_j should give up the rebroadcast as a last node on the forwarding path. Finally, we have the rebroadcast probability p_k(n_i) as follows

\begin{matrix} p_{k} (n_{i}) = \\ {\begin{matrix} 0, & U (n_{i}) = Φ \\ 1, & \exists n_{j}, n_{j} \in U (n_{i}) and N (n_{j}) = {n_{i}} \\ \min (1, \frac{β \cdot R_{u} (n_{i}) + (1 - β) \cdot F_{u} (n_{i})}{d (n_{i})}) & other \end{matrix} \end{matrix}

(11)

Figure 2.

Leaf node and secondary leaf node.

Rebroadcast delay

The definition of the rebroadcast delay is critical for the scheme to achieve optimal performance. The common neighbor ratio of node n_s and node n_i, denoted by R_c(n_si), and the absolute number of uncovered neighbors influence the rebroadcast delay in a different way. R_c(n_si) is defined as follows

R_{c} ({n_{s}}_{i}) = \frac{| N (n_{s}) \cap N (n_{i}) |}{| N (n_{s}) | - 1}

(12)

where |N(n_s)| – 1 is the number of node n_s’s neighbors excluding node n_i.

The rebroadcast delay ratio R_d(n_i) and the rebroadcast delay T_d(n_i) are defined as follows

R_{d} (n_{i}) = {\begin{matrix} 1 - F_{u} (n_{i}) \cdot R_{c} ({n_{s}}_{i}) & N (n_{s}) \cap N (n_{i}) \neq Φ \\ 0 & N (n_{s}) \cap N (n_{i}) = Φ or \exists n_{j}, n_{j} \in U (n_{i}) and N (n_{j}) = {n_{i}} \end{matrix}

(13)

T_{d} (n_{i}) = {\begin{matrix} Δ \cdot R_{d} (n_{i}) & N (n_{s}) \cap N (n_{i}) \neq Φ \\ 0 & N (n_{s}) \cap N (n_{i}) = Φ or \exists n_{j}, n_{j} \in U (n_{i}) and N (n_{j}) = {n_{i}} \end{matrix}

(14)

where Δ is a small constant delay. When there is no common neighbor between node n_i and n_s or n_i is a secondary leaf node, R_d(n_i) and T_d(n_i) are set to 0. If R_d(n_i) is smaller than 0, we set R_d(n_i) to 0.

Next, the details that the rebroadcast delay is defined are explained. Suppose node n_i receives a fresh broadcast message from its upstream node n_s, their common neighbors receive the message too.

If node n_i has more uncovered neighbors, namely a bigger F_u(n_i), it should rebroadcast the received message with a smaller rebroadcast delay to make the message cover more fresh nodes as soon as possible. In this condition, the smaller delay is helpful to accelerate the message propagation and reduce the average end-to-end delay.

If N(n_s) ∩ N(n_i) = Φ, namely there is no common neighbor between node n_s and node n_i, node n_i rebroadcasts the message without delay (T_d(n_i) = 0) will not incur the collision. If $\exists n_{j}, N (n_{j}) = {n_{i}}$ , namely node n_i is a secondary leaf node, node n_i has to rebroadcast the message for the boundary node n_j, and that node n_i rebroadcasts the message without delay (T_d(n_i) = 0) is helpful to accelerate the message propagation.

If bigger the common neighbor ratio of node n_s and n_i is, shorter the rebroadcast delay of node n_i should be. Suppose node n_i and node n_j are neighbors of the upstream node n_s. If the common neighbor ratio of node n_s and node n_i is bigger than the common neighbor ratio of node n_s and node n_j ( $R_{c} (n_{si}) > R_{c} (n_{sj})$ ), node n_i should rebroadcast the message earlier than node n_j. Then, more nodes, namely these common neighbors between n_s and n_i, can update their own uncovered neighbors set upon the received neighbor list from node n_i. Next, their rebroadcast probability will be lowered to reduce redundant messages. If $R_{c} (n_{si}) > R_{c} (n_{sj})$ and $R_{u} (n_{i}) \geq R_{u} (n_{j})$ , the rebroadcast by node n_i within smaller delay will cover more additional fresh nodes in less time than by node n_j. It is helpful to improve the channel utilization and reduce the average end-to-end delay.

The first two points are obviously reasonable. We present the proof for the rationality of the third point in the following.

Proof

\begin{matrix} {\begin{matrix} R_{u} (n_{i}) = x \\ R_{u} (n_{j}) = y \end{matrix} \\ \Rightarrow {\begin{matrix} \frac{| U (n_{i}) |}{| N (n_{i}) | - 1} = x \\ \frac{| U (n_{j}) |}{| N (n_{j}) | - 1} = y \end{matrix} \\ \Rightarrow {\begin{matrix} | N (n_{i}) | = 1 + \frac{| U (n_{i}) |}{x} \\ | N (n_{j}) | = 1 + \frac{| U (n_{j}) |}{y} \end{matrix} \end{matrix}

(15)

Note that

{\begin{matrix} | N (n_{i}) | - | U (n_{i}) | = | N (n_{s}) \cap N (n_{i}) | \\ | N (n_{j}) | - | U (n_{j}) | = | N (n_{s}) \cap N (n_{j}) | \end{matrix}

(16)

If R_c(n_si) > R_c(n_sj), then

\begin{matrix} \frac{| N (n_{s}) \cap N (n_{i}) |}{| N (n_{s}) | - 1} > \frac{| N (n_{s}) \cap N (n_{j}) |}{| N (n_{s}) | - 1} \\ \Rightarrow | N (n_{s}) \cap N (n_{i}) | > | N (n_{s}) \cap N (n_{j}) | \end{matrix}

(17)

Formula (18) can be derived from formulas (16) and (17).

N (n_{i}) | - | U (n_{i}) | > | N (n_{j}) | - | U (n_{j}) |

(18)

Formula (19) can be derived from formulas (15) and (18).

\begin{matrix} 1 + \frac{| U (n_{i}) |}{x} - | U (n_{i}) | > 1 + \frac{| U (n_{j}) |}{y} - | U (n_{j}) | \\ \Rightarrow (\frac{1}{x} - 1) | U (n_{i}) | > (\frac{1}{y} - 1) | U (n_{j}) | \end{matrix}

(19)

\begin{matrix} {\begin{matrix} R_{u} (n_{i}) \geq R_{u} (n_{j}) \\ R_{u} (n_{i}) = x \\ R_{u} (n_{j}) = y \end{matrix} \\ \Rightarrow {\begin{matrix} x < 1, y < 1 \\ x \geq y \end{matrix} \\ \Rightarrow 0 < (\frac{1}{x} - 1) \leq (\frac{1}{y} - 1) \end{matrix}

(20)

Combining formulas (19) and (20), we draw the conclusion as follows

| U (n_{i}) | > | U (n_{j})

(21)

NKB algorithm description

In NKB algorithm, the rebroadcast probability of node n_i is determined by its neighbor knowledge. The formal description of NKB scheme is shown in the following.

The algorithm consists of three phases. In the first phase, U(n_i) is initialized. If U(n_i) = Φ, node n_i refuses to rebroadcast the received message, else, T_d(n_i) is calculated. Next, if U(n_i) ≠ Φ, U(n_i) is being updated before T_d(n_i) expires. Finally, when T_d(n_i) expires and U(n_i) ≠ Φ, p_k(n_i) is calculated and the message is rebroadcasted with probability p_k(n_i).

NKVB scheme

Several studies⁴³ draw the conclusion that the mobility increases the capacity of networks. However, it still is a big challenge for most of existing broadcast schemes to minimize the harm of node mobility. This section proposes a velocity-based data distribution mechanism. It stipulates that few higher-velocity nodes should be selected to rebroadcast the message with a big probability without delay to accelerate the data propagation. The mechanism is extended to NKB scheme to reduce average end-to-end delay further, forming NKVB scheme.

Algorithm 1. Neighbor knowledge-based broadcast algorithm.
Definitions:
m: the received broadcast message.
Timer(n_i, m, T_d(n_i)): timer of node n_i for m message, initialized with the value of T_d(n_i).
random(0, 1): a random function whose range is the interval from 0 to 1.
1: Whilen_i receives a fresh message m from n_sdo
2: $U (n_{i}) = N (n_{i}) - [N (n_{i}) \cap N (n_{s})] - {n_{s}}$
3: if $U (n_{i}) = Φ$ then
4: p_k(n_i) = 0 and return
5: endif
6: if $N (n_{s}) \cap N (n_{i}) = Φ or \exists n_{j}, N (n_{j}) = {n_{i}}$ then
7: T_d(n_i) = 0
8: else
9: $T_{d} (n_{i}) = Δ \times R_{d} (n_{i})$
10: Set a Timer(n_i, m, T_d(n_i))
11: endif
12: endwhile
13: whilen_i receives a duplicate m from n_j before Timer(n_i,m,T_d(n_i)) expires do
14: $U (n_{i}) = U (n_{i}) - [U (n_{i}) \cap N (n_{j})] - {n_{j}}$
15: if $U (n_{i}) = Φ$ then
16: p_k(n_i) = 0 and return
17: endif
18: endwhile
19: While Timer(n_i, m, T_d(n_i)) expires do
20: if $\exists n_{j}, N (n_{j}) = {n_{i}}$ then
21: p_k(n_i) = 1
22: else
23: $p_{k} (n_{i}) = \min (1, (β . R_{u} (n_{i}) + (1 - β) . F_{u} (n_{i})) / d (n_{i}))$
24: endif
25: if random(0, 1) ≤ p_k(n_i) then
26: broadcast(m) and return
27: endif
28: endwhile

Velocity-based data distribution mechanism

Suppose node n_i has k_i neighbors, denoted by ${n_{j} | (n_{i}, n_{j}) \in E, j = 1, 2, \dots, k_{i}}$ , whose velocities are denoted by v_j (j = 1, 2,…, k_i). The minimum and maximum velocity of them are denoted by v_min and v_max, respectively

{\begin{matrix} v_{\max} = \max (v_{1}, v_{2}, \dots, v_{j}) \\ v_{\min} = \min (v_{1}, v_{2}, \dots, v_{j}) \end{matrix} j = 1, 2, \dots, k_{i}

(22)

The arithmetic mean of these neighbors’ velocities $\bar{v}$ and the standard deviation of their velocities $σ$ are calculated respectively as follows

\bar{v} = \frac{1}{k_{i} + 1} (\sum_{j = 1}^{k_{i}} v_{j} + v_{i})

(23)

σ = \frac{1}{k_{i} + 1} (\sum_{j = 1}^{k_{i}} \sqrt{{(v_{j} - \bar{v})}^{2}} + \sqrt{{(v_{i} - \bar{v})}^{2}})

(24)

The velocity-based data distribution mechanism stipulates strictly that node n_i is allowed to rebroadcast the received message with the probability p_v(n_i) only if v_i is bigger than $(\bar{v} + σ)$ . The rebroadcast probability p_v(n_i) is defined by formula (25) as follows

p_{v} (n_{i}) = \frac{v_{i} - (\bar{v} + σ)}{v_{\max} - (\bar{v} + σ)}

(25)

The overhead incurred by these employed high-velocity nodes is very limited. Assume that the node velocity obeys uniform distribution between v_min and v_max, the percentage P_U of the nodes who take part in computing the rebroadcast probability is 0.21 calculated by formula (27)

{\begin{matrix} {\bar{v}}_{U} = \frac{v_{\max} + v_{\min}}{2} \\ σ_{U} = \sqrt{\frac{{(v_{\max} - v_{\min})}^{2}}{12}} \end{matrix}

(26)

\begin{matrix} P_{U} & = 1 - F_{U} ({\bar{v}}_{U} + σ_{U}) \\ = 1 - (\frac{{\bar{v}}_{U} + σ_{U} - v_{\min}}{v_{\max} - v_{\min}}) \\ = 0.21 \end{matrix}

(27)

Similarly, suppose the node velocity obeys normal distribution N(α, σ²), the percentage P_N of the nodes who take part in computing the rebroadcast probability is 0.1587 calculated by formula (29)

{\begin{matrix} {\bar{v}}_{N} = α \\ σ_{N} = σ \end{matrix}

(28)

\begin{matrix} P_{N} & = 1 - F_{N} ({\bar{v}}_{N} + σ_{N}) \\ = 1 - Φ_{α, σ} ({\bar{v}}_{N} + σ_{N}) \\ = 1 - Φ_{α, σ} (α + σ) \\ = 1 - Φ (\frac{(α + σ) - α}{σ}) \\ = 1 - Φ (1) \\ = 0.1587 \end{matrix}

(29)

Note that ultimately, only few of nodes, who take part in computing the rebroadcast probability, are really employed to rebroadcast the message, so the proposed velocity-based data distribution mechanism incurs little overhead. It is also reconfirmed by the simulation result in section “Performance evaluation.”

NKVB algorithm description

In order to collect the neighbor nodes’ velocity, a new field v_i, the velocity of node n_i, needs to be added to Hello message. In NKVB algorithm, the rebroadcast probability of node n_i is determined by both its velocity and its neighbor knowledge. The formal description of the NKVB algorithm is shown in the following.

The algorithm consists of three phases. In the first phase, U(n_i) is initialized. If U(n_i) ≠ Φ and $v_{i} > (\bar{v} + σ)$ , node n_i broadcasts the message with probability p_v(n_i) without delay. If the message is not broadcasted since the random number does not fall in the rebroadcast probability interval from 0 to p_v(n_i), T_d(n_i) is initialized. Next, if U(n_i) ≠ Φ, U(n_i) is being updated before T_d(n_i) expires. Finally, when T_d(n_i) expires and U(n_i) ≠ Φ, p_k(n_i) is calculated and the message is rebroadcasted with probability p_k(n_i).

Performance evaluation

In this section, NKB and NKVB schemes are compared with flooding,⁴ Gossip1(p),⁸ DCB,¹⁵ NCPR,²⁷ and LBA,³⁸ by simulation way using the NS-2(v2.35)⁴⁴ simulator. The IEEE 802.11 MAC with distributed coordination function (DCF) is used as the MAC protocol. The mobility model is based on the random waypoint model (RWM) in a square of size 1000 × 1000 m². In the simulation of our schemes, the empirical value of β is set to 0.8. The rebroadcast probability p of Gossip1(p) is set to 0.65. The detailed simulation parameters are listed in Table 1.

Table 1.

Simulation parameters.

Simulation parameters	Value
Mobility model	RWM
Topology size	1000 × 1000 m²
Numbers of nodes	50, 100, 150, 200, 250, 300
Transmission range	250 m
Bandwidth	2 Mbps
Traffic type	CBR
CBR connection	10, 20, 30, 40, 50, 60
Packet size	512 bytes
Packet rate	4 packets/s
Pause time	0 s
Max mobility velocity (m/s)	0, 5, 10, 15, 20, 25
MAC protocol	802.11 DCF CSMA/CA
Hello interval	0.1 s
Constant delay (Δ)	0.01 s
Fixed probability(Gossip1(p))	0.65

DCF: distributed coordination function.

We have used the following performance metrics for comparison purposes:

Normalized broadcast overhead: normalized broadcast overhead indicates the normalized transmissions of the broadcast operation per node. It defines the ratio of the total transmissions, including the broadcast packets and extra control packets to the broadcast packets per node. It is measured by bytes per broadcast byte per node.

Average end-to-end delay: the average delay of successfully delivered broadcast packets from source to destinations.

Packet delivery ratio: the percentage of nodes received the broadcast message.

The simulation is divided to three parts, and in each part, we evaluate the impact of one of the following factors on the performance of broadcast schemes. In the simulation results, each data point represents the average of 40 trials of experiments. The confidence level is 95%, and the confidence interval is shown as a vertical bar in the figures:

Mobility velocity. The max mobility velocity of nodes is modulated in range of 0–25 m/s to evaluate how the node mobility affects the performance of the schemes. In this part, the number of nodes and the number of CBR connections are set fixedly to 200 and 50, respectively.

Number of nodes. The number of nodes is modulated in range of 50–300 in a fixed square to evaluate how the node density affects the performance of the schemes. In this part, the max mobility velocity of nodes and the number of CBR connections are set fixedly to 15 m/s and 20, respectively.

Number of CBR connections. The number of randomly chosen CBR connections is modulated in range of 10–60 with a fixed packet rate to evaluate how the traffic load affects the performance of the schemes. In this part, the max mobility velocity of nodes and the number of nodes are set fixedly to 15 m/s and 200, respectively.

Algorithm 2. Neighbor knowledge and velocity-based broadcast algorithm.
Definitions:
m: the received broadcast message.
Timer(n_i, m, T_d(n_i)): timer of node n_i for m message, initialized with the value of T_d(n_i).
random(0, 1): a random function whose range is the interval from 0 to 1.
1: Whilen_i receives a fresh message m from n_sdo
2: $U (n_{i}) = N (n_{i}) - [N (n_{i}) \cap N (n_{s})] - {n_{s}}$
3: if $U (n_{i}) = Φ$ then
4: p(n_i) = 0 and return
5: endif
6: ifv_i > $(\bar{v} + σ)$ then
7: $p_{v} (n_{i}) = (v_{i} - (\bar{v} + σ)) / (v_{max} - (\bar{v} + σ))$
8: if random(0, 1) ≤ p_v(n_i) then
9: broadcast(m) and return
10: endif
11: endif
12: if $N (n_{s}) \cap N (n_{i}) = Φ or \exists n_{j}, N (n_{j}) = {n_{i}}$ then
13: T_d(n_i) = 0
14: else
15: $T_{d} (n_{i}) = Δ \times R_{d} (n_{i})$
16: Set a Timer(n_i, m, T_d(n_i))
17: endif
18: endwhile
19: whilen_i receives a duplicate m from n_j before Timer(n_i,m,T_d(n_i)) expires do
20: $U (n_{i}) = U (n_{i}) - [U (n_{i}) \cap N (n_{j})] - {n_{j}}$
21: if $U (n_{i}) = Φ$ then
22: p(n_i) = 0 and return
23: endif
24: endwhile
25: While Timer(n_i, m, T_d(n_i)) expires do
26: if $\exists n_{j}, N (n_{j}) = {n_{i}}$ then
27: p_k(n_i) = 1
28: else
29: $p_{k} (n_{i}) = \min (1, (β . R_{u} (n_{i}) + (1 - β) . F_{u} (n_{i})) / d (n_{i}))$
30: endif
31: if random(0, 1) ≤ p_k(n_i) then
32: broadcast(m) and return
33: endif
34: endwhile

Effects of node mobility

Figure 3 shows that flooding and Gossip1(0.65) are deserved a high normalized broadcast overhead. The result is driven comprehensively by the high node density and their big rebroadcast probabilities. But their overhead curves are almost flat due to the fixed rebroadcast probabilities which are not affected by the node mobility. The normalized broadcast overhead of the other schemes increases proportional to the node mobility, namely, the node mobility has a negative impact on the reduction of overhead. It is because the node mobility directly brings about more control packets to repair the hurt communication link and to maintain the changed network topology. Furthermore, the topological variation may incur some collisions followed by the retransmissions. In some schemes, the node mobility as well gives rise to the imprecise neighbor information collected and the unnecessary rebroadcasts. As shown in Figure 3, when the mobility velocity is bigger than 15 m/s, there is a significant increase in the normalized broadcast overhead, especially for LBA and NCPR schemes.

Figure 3.

Mobility velocity versus normalized broadcast overhead.

In LBA scheme, a node refuses to rebroadcast the received message only if it learned that all of its neighbors have been covered. In fact, it is almost impossible for each node to acquire the intact neighbor coverage knowledge in mobile environment. Then, many superfluous rebroadcasts are executed, leading to some incidental collisions and retransmissions. Therefore, in LBA scheme, the redundant broadcast is the main composition of the normalized broadcast overhead. In mobile environment, DCB scheme tends to define a rough threshold and count a wrong number of reduplicative packets received, which leads inevitably to the redundant rebroadcasts and collisions. Compared with LBA and DCB schemes, the normalized broadcast overhead of NKB, NKVB, and NCPR schemes is affected more mildly by the node mobility since their rebroadcast probabilities do not rely on the precise neighbor knowledge. Compared with Gossip1(0.65) and flooding, NKVB scheme saves 57.5%–84.9% overhead and 65.4%–88.4% overhead, respectively, as shown in Figure 3. Compared with NCPR scheme, NKVB scheme saves 16.2%–26.9% overhead.

Figure 4 shows how the node mobility affects the average end-to-end delay. Both Gossip1(0.65) and flooding keep a stable and higher average end-to-end delay. For the other schemes, as elaborated in Figure 3, the topological change incurs more collisions and retransmissions. Definitely, it leads to higher latency. The incomplete topology knowledge exceedingly amplifies the rebroadcast probability in LBA scheme, and then many redundant messages are rebroadcasted, which leads to a mass of channel competitions and collisions. Definitely, LBA deserves the worst average end-to-end delay among all schemes, especially when the nodes are moving at high velocity.

Figure 4.

Mobility velocity versus average end-to-end delay.

In DCB scheme, the average end-to-end delay increases with the node mobility due to the incremental redundant rebroadcasts and collisions incurred by the inaccurate threshold and count of reduplicative packets. The rest of three schemes only need to maintain relatively rough topology knowledge, so, the node mobility has less influence on their average end-to-end delay than that of LBA and DCB. Both NKB and NKVB schemes outperform NCPR scheme far in average end-to-end delay, as shown in Figure 4, thanks to their reasonable rebroadcast delay and probability. Compared with Gossip1(0.65) and flooding, NKVB scheme reduces 53.4%–58.3% delay and 60.3%–63.6% delay, respectively. Compared with NCPR scheme, NKVB scheme reduces 25.2%–42.3% delay. And, there is an apparent difference that the first half of the curve of NKVB scheme shows a downward trend, which thanks to a part of higher-velocity nodes hired to rebroadcast the messages. These nodes do accelerate the propagation of messages.

As shown in Figure 5, the node mobility almost has no impact on the packet delivery ratio of flooding. Flooding always keeps its reliability at a high level, even when nodes are at high velocity. But the packet delivery ratio of the other schemes is affected in a negative way. The inherent deterministic broadcast mechanism makes LBA scheme obtain the best packet delivery ratio when the node mobility velocity keeps lower than 5 m/s and also makes it failed in high-velocity scenario. For DCB scheme, the changing of the topology reduces the accuracy of the threshold significantly, leading to the serious declining in the packet delivery ratio. The packet delivery ratio of NCPR, NKB, and NKVB schemes is influenced gently by the node mobility, because their rebroadcast does not rely on the accurate neighbor knowledge. Compared with the other three schemes, except for in low velocity scenario, NKB and NKVB scheme obtain a better packet delivery ratio in most scenarios. The simulation result above confirms that probabilistic broadcast schemes are more insensitive to node mobility than deterministic broadcast schemes as mentioned before, since they only need to maintain rough local topology knowledge.

Figure 5.

Mobility velocity versus packet delivery ratio.

Effects of node density

How the node density affects the running of the broadcast schemes is illustrated in this section. As shown in Figure 6, at the very start, the normalized broadcast overhead of all schemes decreases with the increasing number of nodes. It is because the network connectivity is being enhanced by the joined nodes, and then every rebroadcast becomes more efficient to cover more fresh nodes. However, the continued increasing nodes inevitably bring about the collisions followed by retransmissions, which leads to the increasing normalized broadcast overhead afterward. When the number of nodes exceeds 200, the overhead curves of flooding, LBA, and NCPR start a noticeable uptrend. The overhead curves of NKB and NKVB schemes are relatively flat for their self-adjusted rebroadcast probability upon the network density. Compared with Gossip1(0.65) and flooding, NKB and NKVB schemes save 49.2%–67.5% overhead and 59.8%–75.8% overhead, respectively, as shown in Figure 6. Compared with NCPR scheme, NKB and NKVB schemes save 6.6%–41.4% overhead.

Figure 6.

Number of nodes versus normalized broadcast overhead.

Different from the other schemes, the normalized broadcast overhead of DCB scheme almost decreases with the increasing number of nodes all the time. Because the value of threshold C_max taken by DCB is not big enough in dense scenario, so the messages are rebroadcasted with smaller probability, reducing the collisions and the retransmissions. Accordingly, its average end-to-end delay also decreases with the increasing number of nodes as shown in Figure 7. Unfortunately, the inaccurate threshold C_max also leads directly to the lower packet delivery ratio, as shown in Figure 8.

Figure 7.

Number of nodes versus average end-to-end delay.

Figure 8.

Number of nodes versus packet delivery ratio.

Figures 7 and 8 show how the node density acts on the average end-to-end delay and the packet delivery ratio. As mentioned before, the overhead decreases with the increasing nodes in sparse network environment. The increasing nodes make the rebroadcast more efficient, namely, lower delay and higher delivery ratio. In dense network environment, on the contrary, the increasing nodes incur more collisions and more retransmissions, increasing the end-to-end delay and deteriorating the delivery ratio. The increasing node density has a more serious and negative impact on the delay of flooding, compared with the other schemes, as shown in Figure 7. But flooding still keeps a stable and high packet delivery ratio. In NCPR, NKB, and NKVB schemes, the node density is taken into consideration when defining the rebroadcast probability and the rebroadcast delay, so the changing node density has less negative impact on their delay and delivery ratio. In NKB and NKVB schemes, some special nodes such as leaf node deserve a special treat in the process of broadcasting. Their rebroadcast parameters are defined more thoughtfully to deal with the node density than the other schemes do, which makes both schemes more reliable and efficient in complicated network environment. As shown in Figures 6 –8, NKB and NKVB schemes outperform the other schemes especially in average end-to-end delay by 88.9% at most.

Effects of traffic load

How the traffic load affects the running of the broadcast schemes is illustrated in this section. As shown in Figure 9, without exception, the normalized broadcast overhead of all schemes increases with the growing traffic load, since more traffic load leads to more contentions and collisions. The high rebroadcast probability adopted by flooding and Gossip1(0.65) brings about a serious congestion, and the heavy traffic load aggravates the congestion further. LBA scheme rebroadcasts a great many redundant messages, so its overhead experiences a noticeable increase as shown in Figure 9. For DCB scheme, the main of the overhead originates from the retransmission.

Figure 9.

Number of CBR connections versus normalized broadcast overhead.

In NCPR scheme, the rebroadcast delay of a node is inversely proportional to the common neighbors between the upstream node and itself. Generally, it means that the nodes with more neighbors will rebroadcast the message more possibly after a smaller rebroadcast delay. Then, these nodes will forward more packets in less time than the other nodes around. Namely, the way that the rebroadcast delay and the rebroadcast probability are defined is inclined to incur the traffic aggregation. The situation becomes worse as the traffic load increases. As shown in Figure 9, there is a remarkable overhead fluctuation arising when CBR connections of NCPR scheme rise from 50 to 60. At the same time, there is a remarkable increasing of the average end-to-end delay and an obvious decreasing of the packet delivery ratio as shown in Figures 10 and 11, respectively.

Figure 10.

Number of CBR connections versus average end-to-end delay.

Figure 11.

Number of CBR connections versus packet delivery ratio.

Besides the ratio of uncovered neighbors and the neighbor density, the absolute number of uncovered neighbors is taken in consideration to calculate the rebroadcast delay and the rebroadcast probability in NKB and NKVB scheme. It makes the traffic load distribution relatively uniform and more reasonable. The contentions and collisions are restrained effectively. Therefore, the traffic load has less effect on NKB and NKVB scheme than that on the other schemes. Compared with flooding, the propose schemes save 79.2% overhead and reduce 79.1% delay at most, as shown in Figures 9 and 10.

Conclusion

We proposed NKB and NKVB schemes for wireless ad hoc networks. In both schemes, the neighbor density and coverage information are collected by Hello message to calculate the rebroadcast parameters in near real-time at each node. To reduce the overhead of Hello message and upgrade the validity of neighbor knowledge, piggybacking is used. One-hop neighbor information collected keeps the control overhead at a low level. The flexible calculation of the rebroadcast probability and delay guarantees a low average end-to-end delay as well as a high packet delivery ratio in complicated mobile environment. Moreover, the way we defined the rebroadcast delay and the rebroadcast probability is beneficial to balance the traffic load and improve the scalability of the schemes. In order to reduce the latency further, few higher-velocity nodes are employed to rebroadcast the received message in NKVB scheme. It makes NKVB scheme more adaptable to mobile environment. The simulation results show that the proposed schemes outperform the existing broadcast schemes in both reliability and overhead, especially in latency.

Footnotes

Handling Editor: Daniel Gutierrez-Reina

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 work is supported by National Natural Science Foundation (NNSF) of China (61300198 and 61070092), and by Guangdong Natural Science Foundation (2015A030308017) and Guangdong Science and Technology Key Project (2015B010131009).

References

Reina

Toral

Johnson

A survey on probabilistic broadcast schemes for wireless ad hoc networks. Ad Hoc Netw 2015; 25: 263–292.

Tseng

Chen

et al . The broadcast storm problem in a mobile ad hoc network. Wirel Netw 2002; 8(2): 153–167.

Obraczka

Viswanath

Tsudik

et al . Flooding for reliable multicast in multi-hop ad hoc networks. Wirel Netw 2001; 7(6): 64–71.

Jetcheva

Maltz

et al . A simple protocol for multicast and broadcast in mobile ad hoc networks (internet-draft), IETF MANET working group, 2001, https://tools.ietf.org/html/draft-ietf-manet-simple-mbcast-01

Williams

Camp

. Comparison of broadcasting techniques for mobile ad hoc networks. In: Proceedings of the 3rd ACM international symposium on mobile ad hoc networking and computing, Lausanne, 9–11 June 2002, pp.194–205. New York: ACM.

Ruiz

Bouvry

Survey on broadcast algorithms for mobile ad hoc networks. ACM Comput Surv 2015; 48(1): 1–35.

Wang

Jia

et al . Reliable gossip-based broadcast protocol in mobile ad hoc networks. In: Proceedings of the first international conference on mobile ad-hoc and sensor networks, Wuhan, China, 13–15 December 2005, pp.207–218. Berlin: Springer.

Haas

Halpern

et al . Gossip-based ad hoc routing. IEEE ACM T Netw 2006; 14(3): 479–491.

Slavik

Mahgoub

. Stochastic broadcast for VANET. In: 7th IEEE consumer communications and networking conference, Las Vegas, NV, 9–12 January 2010, pp.205–209. New York: IEEE.

10.

Zhou

Cui

Liu

et al . NPPB: a broadcast scheme in dense VANETs. Inf Technol J 2010; 9(2): 247–256.

11.

Dong

Tao

et al . A velocity and neighbor density-based broadcast scheme in mobile ad hoc networks. J High Speed Netw 2015; 21(3): 221–235.

12.

Tseng

Shih

EY.

Adaptive approaches to relieving broadcast storms in a wireless multihop mobile ad hoc network. IEEE T Comput 2003; 52(5): 545–573.

13.

Humoud

Mackenzie

Abdulai

. Neighbourhood-aware counter-based broadcast scheme for wireless ad hoc networks. In: IEEE GLOBECOM workshops, New Orleans, LA, 30 November–4 December 2008, pp.1–6. New York: IEEE.

14.

Mohammed

Ould-Khaoua

Mackenzie

et al . Probabilistic counter-based route discovery for mobile ad hoc networks. In: Proceedings of international conference on wireless communications and mobile computing, Leipzig, 21–24 June 2009, pp.1335–1339. New York: ACM.

15.

Yassein

Nimer

Al-Dubai

AY.

A new dynamic counter-based broadcasting scheme for mobile ad hoc networks. Simul Model Pract Th 2011; 19(1): 553–563.

16.

Liarokapis

Shahrabi

Fuzzy-based probabilistic broadcasting in mobile ad hoc networks. In: IFIP wireless days, Niagara Falls, ON, Canada, 10–12 October 2011, pp.1–6. New York: IEEE.

17.

Liarokapis

Shahrabi

Komninos

DibA: an adaptive broadcasting scheme in mobile ad hoc networks. In: Seventh annual communication networks and services research conference, Moncton, NB, Canada, 11–13 May 2009, pp.224–231. New York: IEEE.

18.

Gang

Shigang

Cai

et al . Research and realization on improved MANET distance broadcast algorithm based on percolation theory. In: International conference on industrial control and electronics engineering, Xi’an, China, 23–25 August 2012, pp.96–99. New York: IEEE.

19.

Kokuti

Simon

. Adaptive multihop broadcast protocols for ad hoc networks. In: 8th international symposium on communication systems, networks & digital signal processing, Poznan, 18–20 July 2012, pp.1–6. New York: IEEE.

20.

Banerjee

Foh

Yeo

et al . Performance improvements for network-wide broadcast with instantaneous network information. J Netw Comput Appl 2012; 35(3): 1162–1174.

21.

Slavik

Mahgoub

Spatial distribution and channel quality adaptive protocol for multihop wireless broadcast routing in VANET. IEEE T Mobile Comput 2013; 12(4): 722–734.

22.

Mostafa

Vegni

Agrawal

DP.

A probabilistic routing by using multi-hop retransmission forecast with packet collision-aware constraints in vehicular networks. Ad Hoc Netw 2014; 14(3): 118–129.

23.

Liu

Zheng

et al . Distance and cooperation based broadcast in wireless ad hoc networks. L N Inst Comp Sci So 2017; 177: 168–178.

24.

Bako

Kargl

Schoch

et al . Advanced adaptive gossiping using 2-hop neighborhood information. In: Global telecommunications conference, New Orleans, LO, 30 November–4 December 2008, pp.1–6. New York: IEEE.

25.

Wang

Shi

A dynamic probabilistic broadcasting scheme based on cross-layer design for manets. Int J Mod Educ Comput Sci 2010; 2(1): 40–47.

26.

Intelligent broadcast in wireless ad hoc networks using live packet information. In: 9th international conference on information, communications and signal processing, Tainan, China, 10–13 December 2013, pp.1–5. New York: IEEE.

27.

Zhang

Wang

Xia

et al . A neighbor coverage-based probabilistic rebroadcast for reducing routing overhead in mobile ad hoc networks. IEEE T Mobile Comput 2013; 12(3): 424–433.

28.

Banerjee

Misra

Yeo

et al . Energy-efficient broadcast and multicast trees for reliable wireless communication. In: IEEE wireless communications and networking conference, New Orleans, LA, 16–20 March 2003, pp.660–667. New York: IEEE.

29.

Ruiz

Dorronsoro

Bouvry

et al . Information dissemination in VANETs based upon a tree topology. Ad Hoc Netw 2012; 10(1): 111–127.

30.

Chen

Kao

Game-based broadcast over reliable and unreliable wireless links in wireless multihop networks. IEEE T Mobile Comput 2013; 12(8): 1613–1624.

31.

Duc

Zalyubovskiy

et al . Towards broadcast redundancy minimization in duty cycled wireless sensor networks. Int J Commun Syst 2017; 30(6): e3108.

32.

Liu

Wan

Jia

et al . Efficient flooding scheme based on 1-hop information in mobile ad hoc networks. In: 25th IEEE international conference on computer communications, Barcelona, 23–29 April 2006, pp.1–12. New York: IEEE.

33.

Woon

Yeung

. Variable power broadcasting based on local information for source-dependent broadcasting protocols. In: IEEE wireless communications and networking conference, Cancun, Mexico, 28–31 March 2011, pp.796–801. New York: IEEE.

34.

Stojmenovic

Khan

Zaguia

Broadcasting with seamless transition from static to highly mobile wireless ad hoc, sensor and vehicular networks. Int J Parall Emer Distrib Syst 2012; 27(3): 225–234.

35.

Schleich

Thi

Bouvry

Solving the minimum M-dominating set problem by a continuous optimization approach based on DC programming and DCA. J Comb Optim 2012; 24(4): 397–412.

36.

Kim

Zhu

et al . Minimum total communication power connected dominating set in wireless networks. In: 7th international conference on wireless algorithms, systems, and applications, Yellow Mountains, China, 8–10 August 2012, pp.132–141. Berlin: Springer.

37.

Ros

Ruiz

Stojmenovi

Acknowledgment-based broadcast protocol for reliable and efficient data dissemination in vehicular ad hoc networks. IEEE T Mobile Comput 2012; 11(1): 33–46.

38.

Khabbazian

Blake

Bhargava

Local broadcast algorithms in wireless ad hoc networks: reducing the number of transmissions. IEEE T Mobile Comput 2012; 11(3): 402–413.

39.

Haas

Nikolov

MV.

Towards optimal broadcast in wireless networks. IEEE T Mobile Comput 2015; 14(7): 213–222.

40.

Kok

Chow

Ishii

Reducing broadcast redundancy in wireless ad-hoc networks with implicit coordination among forwarding nodes. Wireless Pers Commun 2015; 81(1): 253–278.

41.

Nowak

Grochla

Global queue pruning method for efficient broadcast in multihop wireless networks. Commun Comput Inf Sci 2016; 659: 214–224.

42.

Xue

Kumar

PR.

The number of neighbors needed for connectivity of wireless networks

Wirel Netw 2004; 10(2): 169–181.

43.

Grossglauser

Tse

Mobility increases the capacity of ad hoc wireless networks. IEEE ACM T Netw 2002; 10(4): 477–486.

44.

NS2, http://www.isi.edu/nsnam/ns

A neighbor knowledge and velocity-based broadcast scheme for wireless ad hoc networks

Abstract

Keywords

Introduction

Related work

NKB scheme

Collection of neighbor information

Definitions

Uncovered neighbors set

Rebroadcast probability based on neighbor knowledge

Ratio of uncovered neighbors

Density factor and absolute number of uncovered neighbor factor

Rebroadcast probability based on neighbor knowledge

Rebroadcast delay

Proof

NKB algorithm description

NKVB scheme

Velocity-based data distribution mechanism

NKVB algorithm description

Performance evaluation

Effects of node mobility

Effects of node density

Effects of traffic load

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References