A velocity and neighbor density-based broadcast scheme in mobile ad hoc networks

Abstract

Broadcasting is a fundamental and essential data dissemination mechanism in Mobile Ad hoc NETworks (MANETs). This paper presents an efficient probability-based broadcast scheme. In the scheme, to accelerate the packets propagation, the nodes with higher velocity are selected with higher probability to rebroadcast the received packet. Moreover, to reduce transmission redundancy and collisions without decreasing packet delivery ratio, the rebroadcast probability at each node is dynamically and adaptively adjusted according to neighbor density. The velocity and neighbor density-based rebroadcast mechanism keeps the scheme insensitive to the ever-changing network environment, even to the high mobility environment. The theoretical analysis and the simulations show that the proposed scheme outperforms the existing broadcast schemes in packet delivery ratio and normalized broadcast overhead, especially in average end-to-end delay.

Keywords

Rebroadcast probability normalized broadcast overhead average end-to-end delay packet delivery ratio

1. Introduction

There has been a growing research activity on Mobile Ad hoc NETworks (MANETs) over the past years due to their potential and useful civilian and military applications. MANETs as multi-hop wireless networks require no fixed infrastructure, and the deployed mobile nodes act as both the end-points and the routers to forward packets. Due to these self-organizing nodes being free to move randomly, the network’s topology may change rapidly and unpredictably, which brings a fundamental challenge in designing dynamic routing protocol. The routing protocol should efficiently establish routes to deliver data packets between mobile nodes with minimum communication overhead while ensuring high throughput and low end-to-end delay.

Broadcasting as a communication primitive in MANETs is employed widely, such as finding a route to a particular host [21] and propagating an important message [10,15,19]. Because radio signals are likely to overlap with each other in a 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 [27]. Thus, a number of research groups have proposed more efficient broadcast protocols to minimize the number of transmissions while ensuring a higher packet delivery ratio.

Except for blind flooding [7,9], broadcast protocols can be classified into two categories: deterministic broadcast scheme and probabilistic broadcast scheme.

The first category includes tree-based scheme [2,3] and connected dominating set (CDS) and neighbor elimination-based scheme [6,11,12,16,17,23,25,26,31]. Tree-based schemes construct a routing tree on which broadcast packets are forwarded. Fu-Wen Chen proposed a tree-based broadcast scheme [3] in different way, in which the game theory is used to solve the minimum transmission broadcast (MTB) problem. The authors model the MTB problems as a noncooperative game, named broadcast tree construction game. And the broadcast tree construction game can be regarded as a generalization of the global connection game in the sense that both edge cost and node cost are encouraged to be shared. So, the broadcast tree construction game always converges to the famous stable state, Nash Equilibrium. The game-based broadcast tree construction (GB-BTC) algorithm is developed to construct a forwarding tree without directed cycles. However, the broadcast tree construction game can hardly converge to the stable state as claimed due to high mobility of nodes, it is still not a good broadcast solution in high dynamic environment.

CDS and neighbor elimination-based schemes maintain states on the neighborhood of each node, via “Hello” packets. With the information of its neighbors, each node decides its role (forward node or non-forward node) in a specific broadcasting. For example, Majid Khabbazian proposed broadcast algorithm [12] that every broadcasting node selects at most one of its neighbors to forward the packet. A node has to broadcast the packet if it is selected to forward. Other nodes that are not selected have to choose whether or not to broadcast upon a self-pruning condition called coverage condition. To evaluate the coverage condition, every node u maintains a list ${List}_{u}^{cov} (m)$ for every unique message m. Upon receiving a message m for the first time, ${List}_{u}^{cov} (m)$ is initialized and filled with the IDs of all neighbors of u. By collecting neighbor information within 2-hops, ${List}_{u}^{cov} (m)$ is updated before the rebroadcast delay ends, that the neighbors covered by m are removed from ${List}_{u}^{cov} (m)$ . If ${List}_{u}^{cov} (m)$ is not empty, u will rebroadcast m, and select one node which is still in the list to be the next forwarder. Deterministic schemes use network topological information to build a global forwarding structure to reduce broadcast redundancy. But they do not tolerate frequent network topological changes well, since maintaining the forwarding structure in dynamic environment incurs excessive control overhead. In high mobility environment, even deterministic schemes could not provide more reachability than probabilistic schemes.

The second category includes probability-based [5,20,22,27,29], counter-based [8,28,33], distance-based [14,18,24] and location-based schemes [1,30,34]. Probabilistic schemes need not any information from whole network but, rather, start of building a network with each broadcast domain. 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. Although, they have inability to guarantee full network coverage and avoid some redundant transmission.

In this paper, a probabilistic broadcast scheme in high dynamic environment is proposed, where (1) the higher-velocity mobile nodes are employed to rebroadcast the packet with higher probability to accelerate the message propagation, (2) the rebroadcast probability at each node is adjusted adaptively and dynamically according to its neighbor density. In sparse regions, a big rebroadcast probability is adopted to guarantee high packet delivery ratio. While in dense regions, a small rebroadcast probability is used to reduce the redundancy, contention and collisions without deceasing packet delivery ratio.

The rest of the paper is organized as follows. In Section 2, we give a brief review of probabilistic broadcast schemes in MANETs. In Section 3, the Velocity and Neighbor Density-based Broadcast (VNDB) scheme is presented. Section 4 presents the mathematical analysis of VNDB scheme. Section 5 shows the simulation results to validate the performance of the proposed scheme and Section 6 concludes the paper.

2. Related work

Probabilistic schemes only need to maintain rough local topology knowledge so they are broadly used in broadcasting. Probability-based schemes [5,27] use some basic understanding of the network topology to assign a fixed probability to a node to rebroadcast. The fixed gossip probability makes the schemes perform not so well in changing and asymmetrical network environment. In RGB scheme [29], dynamic rebroadcast probability is calculated upon the number of neighbors of the forwarding node.

In counter-based scheme [33], the number of neighbors is used to determine whether the node is located within dense, medium distribution or sparse regions and assigned $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 to $C_{min}$ , $C_{mid}$ and $C_{max}$ , and then one of four different rebroadcast probabilities is assigned to the node. In [8], only two thresholds, unlike in [33], are used to evaluate the node distribution. In [28], the decision to forward the broadcast packet is determined by the function $C (n)$ where n is the number of neighbors of the forwarding node.

In distance-based scheme [14], messages are rebroadcasted according to the decision made between the relative distance of mobile node and the previous sender. When a broadcast message is heard for the first time, $d_{min}$ is initialized to be the distance of the broadcasting node and the count is set to 1. If $d_{min} < D$ (where D is a distance threshold pre-defined), the node stops rebroadcasting. Otherwise, the node waits for a random number of slots, during which every time a copy of the broadcast message is received, $d_{min}$ and D are changed accordingly. If $d_{min} < D$ , the node stops rebroadcasting. Else, if timeout, the node rebroadcasts the message.

In location-based scheme [30,34], a rebroadcast delay is adopted to exploit the neighbor coverage information to obtain an accurate additional coverage ratio. In [30], three node-stamping broadcast algorithms, named basic stamping, advanced stamping, and hybrid stamping, are proposed. Each node in Advanced stamping algorithm collects its 1-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 if 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 2-hop neighbor information for pruning. With hybrid stamping, each node further checks if 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 firstly. For each neighbor n not contained in the stamp, node r then tries to check if there is a neighbor p in $N (n)$ is in the stamp. If node p has higher priority than node r, node r can assume node n will be covered by broadcasting from node p or node with 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 NCPR [34], the periodical hello packets are exchanged among the neighbors to collect the neighbor information. The rebroadcast delay defined in NCPR is inversely proportional with the common neighbor ratio of the upstream node and the downstream node. The node’s uncovered neighbors set is updated according to the neighbor list, every time it receives a duplicate RREQ packet from its neighbor before the rebroadcast delay expires. The connectivity factor is defined to provide the node density adaptation. By combining the additional coverage ratio and connectivity factor, a reasonable rebroadcast probability is calculated.

In above schemes, the rebroadcast probabilities depend on the count-thresholds, or the distance information, or the coverage knowledge. The accuracy of them is fatal for these schemes. But, the rapid movement of nodes definitely leads to inaccuracy of these information, which makes the rebroadcast not so reasonable. And note that, a random delay is adopted to obtain the key information in all three kinds of schemes above. No doubt, it increases the average end-to-end delay. How to improve the rebroadcast efficiency and reduce the delay in high mobility environment is exactly the problem we plan to solve in this paper.

3. Velocity and Neighbor Density-based Broadcast (VNDB) scheme

In VNDB scheme, to reduce transmission redundancy and collisions without decreasing packet delivery ratio, the rebroadcast probability at each node is dynamically and adaptively adjusted according to upstream and downstream node density. Moreover, the nodes with higher velocity are selected with higher probability to rebroadcast the received packet. It accelerates the packets propagation and decreases the average end-to-end delay. This section introduces how VNDB scheme works adaptively in inhomogeneous environment.

3.1. Collection of neighbor knowledge

The proposed scheme use Hello packets to collect a node’s one hop neighbor knowledge. To reduce the overhead of Hello packets, piggybacking is used. Moreover, piggybacking of the Hello packet by broadcast packet makes the neighbor knowledge fresh. Only when the time elapsed from the last broadcasting packet is greater than a Hello Interval, the node needs to send a Hello packet.

In VNDB, Hello packet includes:

NID: node’s ID

BID: ID of broadcast packet received

v: node’s velocity

flag_leaf: If the node is a leaf, flag_leaf is set to 1. Otherwise, this field is excluded from Hello packet.

Definitions:

leaf: the node has only one neighbor.

secondary leaf: if a node has only two neighbors and one of them is a leaf, then this node is a secondary leaf.

3.2. Rebroadcast probability based on node velocity

Several studies [4] indicated that the mobility increases the capacity of MANETS. But, for most of existing broadcast protocols the high mobility is a stumbling block to the good performance. In this paper, a small part of high-velocity nodes are employed to propagate the packet with a bigger probability for low delay.

The velocity of node $n_{i}$ is denoted by $v_{i}$ . It has $k_{i}$ neighbors, whose velocities are denoted by $v_{j}$ ( $j = 1, \dots, k_{i}$ ). The maximum velocity of them is denoted by $v_{max}$ . The arithmetic mean of these neighbors’ velocities is $\bar{v}$ and the standard deviation of velocities σ are calculated as follows: $\begin{array}{rclr} \bar{v} = \frac{1}{k_{i} + 1} (\sum_{j = 1}^{k_{i}} v_{j} + v_{i}), & (1) \\ σ = \frac{1}{k_{i} + 1} (\sum_{j = 1}^{k_{i}} \sqrt{{(v_{j} - \bar{v})}^{2}} + \sqrt{{(v_{i} - \bar{v})}^{2}}) . & (2) \end{array}$

If $v_{i}$ is bigger than $(\bar{v} + σ)$ , it is selected to calculate node $n_{i}$ ’s rebroadcast probability $p_{v} (n_{i})$ based on velocity. $p_{v} (n_{i}) = \frac{v_{i} - (\bar{v} + σ)}{v_{max} - (\bar{v} + σ)} .$ (3)

3.3. Rebroadcast probability based on node density

In order to keep a high packet delivery ratio and reduce the collisions, the big and low rebroadcast probability should be adopted respectively by the nodes in sparse and dense area. Xue and Kumar [32] concluded that if each node connects to more than $5.1774 {log}^{N}$ of its nearest 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. Then, we use $5.1774 {log}^{N}$ as a connectivity metric to evaluate the local density. Node $n_{i}$ ’s rebroadcast probability $p_{d} (n_{i})$ based on its own neighbor density can be calculated as follows: $p_{d} (n_{i}) = α \frac{C_{m}}{k_{i}},$ (4) where $C_{m} = 5.1774 {log}^{N}$ , $k_{i}$ is the number of neighbors of node $n_{i}$ , and α is a constant coefficient. If $p_{d} (n_{i})$ is bigger than 1, we set it to 1.

We stipulate that the nodes one hop away from the source rebroadcast the packet with probability 1 to refrain this packet from dying before spreading into the network.

3.4. Algorithm description

In our algorithm, the rebroadcast probability of node $n_{i}$ is determined by both $n_{i}$ ’s velocity and the local node densities.

In VNDB scheme, the nodes, whose velocities are higher than $(\bar{v} + σ)$ , take part in calculating their $p_{d} (n_{i})$ . That is to say, these nodes have more chance to rebroadcast the packet compared to the low-velocity nodes.

The local node densities of upstream node $n_{h}$ and downstream node $n_{i}$ both affect the rebroadcast probability of $n_{i}$ .

If node $n_{h}$ has fairly more neighbors, node $n_{i}$ ’s coverage area may overlaps with it neighbor’s as shown in Fig. 1(a). Otherwise, it maybe not, as shown in Fig. 1(b). A smaller rebroadcast probability adopted by node $n_{i}$ in Fig. 1(a), compared to that in Fig. 1(b), is advantageous to reduce the collisions and the redundant packet.

Fig. 1.

Node density affects rebroadcast probability. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JHS-150522.)

Be different form Fig. 1(a), if $n_{i}$ is with fewer neighbors as shown in and Fig. 1(c), rebroadcast probability adopted by $n_{i}$ should be changed as well. If node $n_{i}$ has fewer neighbors, there could be less overlap between them, as shown in Fig. 1(c). A bigger rebroadcast probability adopted by node $n_{i}$ in Fig. 1(c), compared to that in Fig. 1(a), can keep a high packet delivery ratio. We can conclude that $n_{i}$ ’s rebroadcast probability, defined by $p_{d 2} (n_{i})$ , relies on both node densities around $n_{h}$ and $n_{i}$ . So we have the formula (5) and formula (6): $\begin{array}{rclr} p_{d 2} (n_{i}) = ω \cdot p_{d} (n_{i}) + (1 - ω) \cdot p_{d} (n_{h}) \\ = ω α \frac{C_{m}}{k_{i}} + (1 - ω) α \frac{C_{m}}{k_{h}} \\ = \frac{(1 - ω) k_{i} + ω k_{h}}{k_{i} k_{h}} α C_{m} (0 < ω < 1), & (5) \\ p_{d 2} (n_{i}) \cdot \frac{k_{i} k_{h}}{(1 - ω) k_{i} + ω k_{h}} = α C_{m}, & (6) \end{array}$ where ω is an influence coefficient. $k_{i} k_{h} / ((1 - ω) k_{i} + ω k_{h})$ reflects the local density information of $n_{i}$ , called density coefficient – $d (n_{i})$ . For each node, $p_{d 2} (n_{i}) \cdot d (n_{i})$ is a constant called rebroadcast intensity. $p_{d 2} (n_{i}) \cdot d (n_{i}) = α C_{m} .$ (7)

Note that, in Fig. 1(c), $n_{i}$ is also a secondary leaf node, whose leaf node is $n_{j}$ . So, node $n_{i}$ must rebroadcast the packet with probability 1 for node $n_{j}$ . But $n_{j}$ gives up the rebroadcast as the last node on the forwarding path.

Except for leaf nodes and secondary leaf nodes, other nodes will select the maximum of $p_{v} (n_{i})$ and $p_{d} (n_{i})$ as rebroadcast probability. The formal description of the Velocity and Neighbor Density-based Broadcast algorithm is shown in Fig. 2.

Fig. 2.

Velocity and Neighbor Density-based Broadcast (VNDB) algorithm.

4. Theoretical analysis

This section provides a mathematical analysis on the packet delivery ratio and the overhead of VNDB scheme.

4.1. Packet delivery ratio and delay analysis

Since VNDB scheme has a strong similarity with epidemic spreading of disease, we analyze it using a simple epidemic model called the SI model in [13]. The SI model we used is somewhat different from the original paper. Their analytical parameters are different from each other. In this paper, we study how the rebroadcast intensity $p_{d 2} (n_{i}) \cdot d (n_{i})$ affects the packet delivery ratio.

Some parameters mentioned in the SI model are defined in the following:

N: Number of nodes in the network.

$S (t)$ : Number of nodes not received the broadcast message m until time t.

$I (t)$ : Number of nodes received m until time t.

$d (n_{i})$ : Density coefficient.

$p_{d 2} (n_{i}) \cdot d (n_{i})$ , namely $α C_{m}$ : Rebroadcast intensity.

$r = p_{d 2} (n_{i}) \cdot d (n_{i}) / N$ : Broadcast message transmission rate.

$β = r \cdot I (t)$ : Probability per unit time for a node to receive m.

$i (t) = I (t) / N$ : Packet delivery ratio of m.

The balance equations are presented as follows: $\{\begin{matrix} \frac{d S (t)}{d (t)} = - β \cdot S (t), \\ \frac{d I (t)}{d (t)} = β \cdot S (t) . \end{matrix}$ (8)

Since $β = r \cdot I (t)$ and $S (t) = N - I (t)$ , thus $\begin{array}{rclr} \frac{d I (t)}{d (t)} & = & r \cdot I (t) \cdot [N - I (t)] \\ = & r \cdot N \cdot I (t) - r \cdot I^{2} (t) . & (9) \end{array}$

This first order ordinary differential equation has the following general solution: $I (t) = \frac{N}{1 + C \cdot N \cdot e^{- r \cdot N \cdot t}},$ (10) where C is a constant that only depends on the initial conditions. Here C is computed as follows. At the beginning ( $t = 0$ ), we assume that only one source node carries the broadcast message m, so $I (t)$ should satisfy $I (0) = 1$ . $I (0) = 1 = \frac{N}{1 + C \cdot N \cdot e^{- r \cdot N \cdot 0}} ⟹ C = \frac{N - 1}{N} .$ (11)

To study the relationship between $i (t)$ and parameters $p_{d 2} (n_{i})$ and $d (n_{i})$ , r is replaced by $p_{d 2} (n_{i}) \cdot d (n_{i}) / N$ and $α C_{m}$ , then we get: $\begin{array}{rclr} i (t) & = & I (t) / N = \frac{1}{1 + (N - 1) \cdot e^{- p_{d 2} (n_{i}) \cdot d (n_{i}) \cdot t}} \\ = & \frac{1}{1 + (N - 1) \cdot e^{- α \cdot C_{m} \cdot t}} . & (12) \end{array}$

In a specified network, N is or almost is constant, then the packet delivery ratio $i (t)$ depends on $p_{d 2} (n_{i}) \cdot d (n_{i})$ and t. It is obvious that the time t taken to get similar $i (t)$ decreases with the increase of $p_{d 2} (n_{i}) \cdot d (n_{i})$ named rebroadcast intensity. As shown in Fig. 3, $N = 100$ , α is set to 0.3, 0.4, 0.5, 0.6 separately, corresponding values of $p_{d 2} (n_{i}) \cdot d (n_{i})$ are $0.3 C_{m}$ , $0.4 C_{m}$ , $0.5 C_{m}$ , $0.6 C_{m}$ , and $i (t) = 99$ %, the values of time t are 2.96, 2.22, 1.78, 1.48. Obviously, we achieve a high packet delivery ratio and low delay in theory.

Fig. 3.

$i (t)$ vs. t with $N = 100$ .

4.2. Overhead analysis

The control overhead of Hello packets are reduced by piggybacking in our scheme. The transmission overhead includes redundant rebroadcasts based on node density and velocity.

There is a controllable tradeoff, by adjusting the value of α, between the packet delivery ratio, the delay and the transmission overhead incurred by rebroadcast based on node density. The selected bigger rebroadcast probability $p_{d 2} (n_{i})$ brings not only a higher packet delivery ratio and a lower delay as shown in Fig. 3, but also more rebroadcasts, namely, more overhead.

We assume that the node velocity obeys uniform distribution between $v_{min}$ and $v_{max}$ , the percentage $P_{u}$ of nodes who take part in computing $p_{v} (n_{i})$ is 0.21 calculated by formula (14). Similarly, if the node velocity obeys Gaussian distribution, the percentage is 0.159. Finally, only few of these nodes really need to rebroadcast, so it incurs less overhead. $\begin{matrix} \begin{matrix} σ_{u} = \sqrt{\frac{{(v_{max} - v_{min})}^{2}}{12}}, \\ {\bar{v}}_{u} = \frac{v_{max} + v_{min}}{2}, \end{matrix} & (13) \\ P_{u} = 1 - F ({\bar{v}}_{u} + σ_{u}) = 1 - (\frac{{\bar{v}}_{u} + σ_{u} - v_{min}}{v_{max} - v_{min}}) = 0.21 . & (14) \end{matrix}$

5. Simulation and analysis

In this section, we evaluate the performance of VNDB scheme compared with Local Broadcast Algorithm (LBA) [12], DCB [33] and NCPR [34] 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 in a square of size 1000 × 1000 m². The detailed simulation parameters are listed in Table 1, and the values of α and ω in VNDB are set to 0.5.

We have used the following performance metrics for comparison purposes.

Normalized broadcast overhead: the 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 which receive the broadcast packet.

The simulations are divided to three parts, and in each part we evaluate the impact of one of the following parameters on the performance of broadcast schemes.

Mobility velocity. We change the max mobility velocity of nodes from 0 m/s to 25 m/s to evaluate the impact of different node mobility. In this part, we set the number of nodes to 200, and set the number of CBR connections to 50.

Number of nodes. We change the number of nodes from 50 to 300 in a fixed square to evaluate the impact of different network density. In this part, we set the max mobility velocity of nodes to 20 m/s, and set the number of CBR connections to 20.

Number of CBR connections. We change the number of randomly chosen CBR connections from 10 to 60 with a fixed packet rate to evaluate the impact of different traffic load. In this part, we set the max mobility velocity of nodes to 20 m/s, and set the number of nodes to 200.

Table 1
Simulation parameters

Simulation parameters Value

Mobility model Random waypoint model

Topology size 1000 $\times$ 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

Rebroadcast delay (NCPR, DCB, LBA) 0.01 s

Simulation parameters	Value
Mobility model	Random waypoint model
Topology size	1000 $\times$ 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
Rebroadcast delay (NCPR, DCB, LBA)	0.01 s

5.1. Effects of node mobility

Figure 4 shows that the normalized broadcast overhead of all schemes increases proportional to the node mobility. It is due to the fact that when the node mobility grows, the topological changes also increase and more control packets are generated to maintain the topology. Furthermore, the frequent change of topology incurs many collisions followed by retransmissions. LBA gives up rebroadcasting only when receiving the integrated neighbor coverage knowledge, which is almost impossible in high mobility environment. Then, many redundant packets are sent out, leading to severe overhead. In DCB, the node mobility brings inaccuracy for both the value of the thresholds and the number of duplicate packets received, and incurs redundant rebroadcasts and collisions. Different from LBA and DCB, VNDB and NCPR are affected by node mobility slightly since their rebroadcast probabilities do not rely on the precise neighbor knowledge.

Fig. 4.

Mobility velocity vs. normalized broadcast overhead.

Fig. 5.

Mobility velocity vs. average end-to-end delay.

Fig. 6.

Mobility velocity vs. packet delivery ratio.

Figure 5 shows the effects of node mobility on the average end-to-end delay. As mentioned in last paragraph, the topological changes incur the collisions and the retransmissions, leading to more delay. No doubt LBA deserves the worst average end-to-end delay followed by DCB. The node mobility has less impact on average end-to-end delay of NCPR than that of LBA and DCB. VNDB performs the best performance of delay, because it doesn’t introduce the rebroadcast delay to collect the duplicate packets as the other three schemes do. Moreover, VNDB avoids many contentions and collisions. As can be noticed, the node mobility does accelerate the propagation of packet in VNDB, since the nodes with higher velocities are employed to rebroadcast.

Figure 6 shows that the node mobility affects the packet delivery ratio achieved by all scheme in negative way. The packet delivery ratio of NCPR is affected gently, because its rebroadcast doesn’t rely on the accurate neighbor knowledge. Unlike VNDB and NCPR, LBA is liable to make wrong deterministic rebroadcast decisions upon 100 percent accurate coverage knowledge. For DCB, the changing of the topology reduces the accuracy of the threshold significantly, leading to the severe declining of its packet delivery ratio. Compared with the other three schemes, except for at low velocity, VNDB scheme obtains a better packet delivery ratio in most scenarios, especially at high velocity. The adaptive, smooth change of rebroadcast probability at each node makes VNDB difference in packet delivery ratio.

5.2. Effects of network density

The effects of the network density on the performance are illustrated in this section.

As shown in Fig. 7, at the very start, the normalized broadcast overhead of all schemes decreases as the number of nodes grows, since the network connectivity is enhanced by the joined nodes and once rebroadcast can cover more nodes. But, the continued increasing of the nodes incurs many collisions, which results in the increasing of the normalized broadcast overhead afterwards. The curves of NCPR and VNDB are almost flat due to the adaptive changing of their rebroadcast probability with the network density. Different from the other schemes, the normalized broadcast overhead of DCB decreases in dense node scenario. That is because the value of threshold $C_{max}$ taken by DCB is not big enough in dense scenario, then the packets are rebroadcasted with a smaller probability. Moreover, the average end-to-end delay is also decreased as shown in Fig. 8. But, it brings a serious negative effect at the same time, leading directly to the lower packet delivery ratio as shown in Fig. 9.

Fig. 7.

Number of nodes vs. normalized broadcast overhead.

Figures 8 and 9 show the effects of network density on the average end-to-end delay and the packet delivery ratio. As mentioned in last paragraph, the overhead decreases with the rise of node number in sparse network environment. It makes the rebroadcast more efficient, namely, less delay and higher delivery ratio. But, in dense network, the increasing of the nodes results in many collisions and retransmissions, incurs long end-to-end delay and aggravates the delivery ratio. The network density affects NCPR and VNDB slightly on the delay and the delivery ratio as on the overhead. Rebroadcast without rebroadcast delay makes VNDB perform more excellently in delay than other schemes.

Fig. 8.

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

Fig. 9.

Number of nodes vs. packet delivery ratio.

Fig. 10.

Number of CBR connections vs. normalized broadcast.

5.3. Effects of traffic load

The effects of the traffic load on the performance are illustrated in this section.

As shown in Fig. 10, the normalized broadcast overhead of all schemes increases as the traffic load grows, because more traffic load leads to more contentions and collisions. Apparently, there is a more noticeable increase of the overhead in LBA than that in other scheme. In this part, we set the max mobility velocity of nodes to 20 m/s and the higher mobility velocity is disadvantageous especially to LBA as mentioned in the Section 5.1. In NCPR scheme, the rebroadcast delay of a node is inverse ratio to the number of the common neighbors between the upstream node and this node. Generally, a node with many neighbors has a smaller rebroadcast delay and it rebroadcasts the packet more possibly. Then these nodes forward more packets in less time than the other nodes, which incurs the contention and the collision more likely. The situation becomes worse as the traffic load increases. As shown in Fig. 10, the overhead of NCPR increases remarkably when the CBR connections are set to 50 and 60. The rebroadcast mechanism of VNDB keeps the traffic load distribution relatively uniform in the network, which has less effect on the normalized broadcast overhead. Correspondingly, the increasing of the average end-to-end delay and the decreasing of the packet delivery ratio of all schemes follow with the rise of the contentions and the collisions, as shown in Fig. 11 and Fig. 12. VNDB scheme still is the best one in keeping low average end-to-end delay in the different load cases among all four schemes.

Fig. 11.

Number of CBR connections vs. average end-to-end delay overhead.

Fig. 12.

Number of CBR connections vs. packet delivery ratio.

6. Conclusions and future work

In this paper, a velocity and neighbor density-based probabilistic broadcast scheme in MANETs is proposed, where the rebroadcast probability at each node is dynamically and adaptively adjusted according to its mobility velocity and local node density. This mechanism guarantees a low broadcast overhead, delay, and a high packet delivery ratio in the high mobility environment, although Fig. 4 and Fig. 6 show that VNDB scheme is not the best one in the low mobility environment among all schemes. Furthermore, the probabilistic characteristic enables VNDB to obtain a desired tradeoff between the overhead and the delivery ratio by tuning the rebroadcast intensity $p \cdot x$ . Moreover, the rebroadcast mechanism based on the mobility velocity can be easily extended to other probabilistic broadcast schemes which need to collect the neighbor knowledge, such as NCPR and DCB. Our future work will focus on the extension of rebroadcast mechanism based on the mobility velocity and resolving the influence coefficient ω.

Footnotes

Acknowledgements

This study is supported by National Natural Science Fund, China (Grant Nos. 61300198 and 61070092), Guangdong Province Natural Science Foundation (No. S2013040016582). Guangdong University Scientific Innovation Project (Nos. 2013KJCX0177 and 2014KTSCX188).

References

[1]

Bako,

Kargl,

Schoch et al., Advanced adaptive gossiping using 2-hop neighborhood information, in: Proceedings of IEEE Global Telecommunications Conference, New Orleans, LA, USA, 2008, pp. 1–6.

[2]

Banerjee,

Misra,

Yeo et al., Energy-efficient broadcast and multicast trees for reliable wireless communication, in: Proceedings of IEEE Wireless Communications and Networking (WCNC), New Orleans, LA, USA, 2003, pp. 660–667.

[3]

Chen and

Kao, Game-based broadcast over reliable and unreliable wireless links in wireless multihop networks, IEEE Trans. on Mobile Computing 12(8) (2013), 1613–1624.

[4]

Grossglauser and

Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Trans. on Networking 10(4) (2002), 477–486.

[5]

Z.J.

Haas,

J.Y.

Halpern and

Li, Gossip-based ad hoc routing, IEEE/ACM Trans. on Networking 14(3) (2006), 479–491.

[6]

Z.J.

Haas and

M.V.

Nikolov, Towards optimal broadcast in wireless networks, in: Proceedings of the 14th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems, ACM, New York, NY, 2011, pp. 213–222.

[7]

Ho,

Obraczka,

Tsudik et al., Flooding for reliable multicast in multi-hop ad hoc networks, in: Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, ACM, New York, 1999, pp. 64–71.

[8]

Humoud,

Mackenzie and

Abdulai, Neighbourhood-aware counter-based broadcast scheme for wireless ad hoc networks, in: Proceedings of IEEE GLOBECOM Workshops, New Orleans, LA, USA, 2008, pp. 1–6.

[9]

Jetcheva,

Hu,

Maltz et al., A simple protocol for multicast and broadcast in mobile ad hoc networks, Internet-Draft, IETF MANET Working Group, 2001.

10.

[10]

Ke,

Yi and

Ren, Improved broadcast encryption schemes with enhanced security, Journal of Ambient Intelligence and Humanized Computing 6(1) (2015), 121–129.

11.

[11]

Khabbazian and

V.K.

Bhargava, Efficient broadcasting in mobile ad hoc networks, IEEE Trans. on Mobile Computing 8(2) (2009), 231–245.

12.

[12]

Khabbazian,

Blake and

Bhargava, Local broadcast algorithms in wireless ad hoc networks: reducing the number of transmissions, IEEE Trans. on Mobile Computing 11(3) (2012), 402–413.

13.

[13]

Khelil,

Becker,

Tian et al., An epidemic model for information diffusion in MANETs, in: Proceedings of the 5th ACM International Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems, ACM, New York, NY, 2002, pp. 54–60.

14.

[14]

Liarokapis,

Shahrabi and

Komninos, Diba: an adaptive broadcasting scheme in mobile ad hoc networks, in: Proceedings of Communication Networks and Services Research Conference, Moncton, NB, Canada, 2009, pp. 224–231.

15.

[15]

Lin and

Jan, A tree-based scheme for security of many-to-many communications, Journal of High Speed Networks 16(1) (2007), 69–79.

16.

[16]

Liu,

Wan,

Jia et al., Efficient flooding scheme based on 1-hop information in mobile ad hoc networks, in: Proceedings of IEEE INFOCOM, Catalunya, Spain, 2006, pp. 1–12.

17.

[17]

Lou and

Wu, Toward broadcast reliability in mobile ad hoc networks with double coverage, IEEE Trans. on Mobile Computing 6(2) (2007), 148–163.

18.

[18]

M.N.

Mariyasagayam,

Osafune and

Lenardi, Enhanced multi-hop vehicular broadcast (MHVB) for active safety applications, in: Proceedings of Seventh International Conference on ITS Telecommunications, Sophia Antipolis, France, 2007, pp. 1–6.

19.

[19]

Palmieri, Scalable service discovery in ubiquitous and pervasive computing architectures: a percolation-driven approach, Future Generation Computer Systems 29(3) (2013), 693–703.

20.

[20]

Palmieri and

Castiglione, Condensation-based routing in mobile ad-hoc networks, Mobile Information Systems 8(3) (2012), 199–211.

21.

[21]

Perkins ,

Belding-Royer and

Das, Ad hoc on-demand distance vector (AODV) routing, RFC 3561, IETF, 2003.

22.

[22]

D.G.

Reina,

J.M.

Leon-Coca,

S.L.

Toral et al., Multi-objective performance optimization of a probabilistic similarity/dissimilarity-based broadcasting scheme for mobile ad hoc networks in disaster response scenarios, Soft Computing 18(9) (2014), 1745–1756.

23.

[23]

F.J.

Ros,

P.M.

Ruiz and

Stojmenovic, Acknowledgment-based broadcast protocol for reliable and efficient data dissemination in vehicular ad hoc networks, IEEE Trans. on Mobile Computing 11(1) (2012), 33–46.

24.

[24]

Slavik and

Mahgoub, Spatial distribution and channel quality adaptive protocol for multihop wireless broadcast routing in VANET, IEEE Trans. on Mobile Computing 12(4) (2013), 722–734.

25.

[25]

Stojmenovic,

Seddigh and

Zunic, Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks, IEEE Trans. on Parallel and Distributed Systems 13(1) (2002), 14–25.

26.

[26]

Tao,

Lu and

Yang, An adaptive energy-aware multi-path routing protocol with load balance for wireless sensor networks, Wireless Personal Communications 63(4) (2012), 823–846.

27.

[27]

Tseng,

Ni,

Chen and

Sheu, The broadcast storm problem in a mobile ad hoc network, Wireless Networks 8(2–3) (2002), 153–167.

28.

[28]

Tseng,

Ni and

Shih, Adaptive approaches to relieving broadcast storms in a wireless multihop mobile ad hoc network, IEEE Trans. on Computers 52(5) (2003), 545–557.

29.

[29]

Wang,

Lu,

Jia et al., Reliable gossip-based broadcast protocol in mobile ad hoc networks, in: Proceedings of Mobile Ad-Hoc and Sensor Networks, Wuhan, China, 2005, pp. 207–218.

30.

[30]

Wu and

Li, Intelligent broadcast in wireless ad hoc networks using live packet information, in: Proceedings of 9th International Conference on Information, Communications and Signal Processing, Tainan, Taiwan, China, 2013, pp. 1–5.

31.

[31]

Wu and

Dai, Broadcasting in ad hoc networks based on self-pruning, in: Proceedings of INFOCOM, San Francisco, CA, USA, 2003, pp. 2240–2250.

32.

[32]

Xue and

Kumar, The number of neighbors needed for connectivity of wireless networks, Wireless Networks 10(2) (2004), 169–181.

33.

[33]

M.B.

Yassein,

S.F.

Nimer and

A.Y.

Al-Dubai, A new dynamic counter-based broadcasting scheme for mobile ad hoc networks, Simulation Modelling Practice and Theory 19(1) (2011), 553–563.

34.

[34]

X.M.

Zhang,

E.B.

Wang,

J.J.

Xia et al., A neighbor coverage-based probabilistic rebroadcast for reducing routing overhead in mobile ad hoc networks, IEEE Trans. on Mobile Computing 12(3) (2013), 424–433.