A scalable neighbor-based routing protocol for mobile ad hoc networks

Abstract

Broadcasting is an essential and effective mechanism used to disseminate data on several types of networks such as mobile ad hoc network. Such method is adopted by a considerable number of routing protocols, in particular, in the route discovery stage since the broadcasting is easy to implement and certainly provides an ideal connectivity among nodes. However, the broadcasting increases the routing overhead, packet delay, which negativity affects the throughput due to the excessive use of the redundant Route REQuest message. In addition, the network is susceptible to so-called broadcast storm problem. Therefore, developing a new routing protocol, which is able to relieve the unnecessary Route REQuest messages while boosting the performance of the network, is required. In this article, a novel routing protocol for mobile ad hoc network, called scalable neighbor-based mobile routing, is proposed. The broadcasting in this protocol is governed by the inverse relation between the number of neighbors and the probability of the rebroadcasted Route REQuest messages. Extensive simulation experiments are carried out to evaluate the performance of the proposed protocol and to compare the state-of-the-art protocols, namely, neighbor coverage-based probabilistic rebroadcast, with the latest version of ad hoc on-demand distance vector protocol. Simulation results show that scalable neighbor-based mobile routing outperforms both protocols, the neighbor coverage-based probabilistic rebroadcast and the ad hoc on-demand distance vector, in terms of routing overhead, medium access control collision, end-to-end delay, packet delivery ratio, and energy consumption.

Keywords

Mobile ad hoc networks probabilistic rebroadcast ad hoc on-demand distance vector routing overhead flooding

Introduction

Mobile ad hoc network (MANET) is a set of temporary connected mobile nodes such as smart mobile phones, laptops, or military devices, and this network may work stand-alone or connected to the Internet. Recently, such types of networks have become prominent due to the vast increase in mobile devices and fast growth of the wireless communication. In addition, MANET could be easily established without the use of any existing network infrastructure. Furthermore, its applications vary from small and static to large-scale and dynamic networks.

Nonetheless, nodes in MANET have limited power resources and may be equipped with different transmission technologies.¹ Moreover, these nodes are connected using a wireless technology, so, they share the same transmission media. As a result, sending and receiving data become much complicated process. Nodes are obligated to wait for a period of time before transmitting their data to avoid the packet collision. However, in some cases, such collision may occur due to the excessive use of Route REQuest (RREQ) messages. Thus, MANET should have a robust and efficient routing protocol to overcome the preceding issues.

The majority of the existing routing protocols are classified into three main types: proactive, reactive, and hybrid routing protocols. Furthermore, the most commonly used protocols are ad hoc on-demand distance vector (AODV) protocol,² dynamic source routing (DSR),³ location-aided routing (LAR),⁴ and zone routing protocol (ZRP).⁵ Basically, mobile nodes in MANET have limited power resource and frequent movements. Thus, it is more convenient to use reactive routing protocols owing to the path only constructed when there are data to be sent. AODV, DSR, and neighbor coverage-based probabilistic rebroadcast (NCPR) are among many reactive protocols which have been proposed for such network.

Broadcasting is the most trivial mechanism used by a considerable number of routing protocols to transfer data between nodes. In fact, the routing process in many reactive routing protocols such as AODV and NCPR protocols could be summarized into three main stages, the route discovery, route reply, and route maintenance. However, this article only deals with the first stage, the route discovery.

With regard to the route discovery, the source node in some routing protocols, such as AODV and NCPR, starts to look up a route to the destination in the routing table. Nevertheless, in the case of no route available, the source node ought to disseminate RREQ to all nodes, such method is known as flooding. This method guarantees a great reachability at the cost of degrading the system performance, in which the delay and routing overhead dramatically increase. In addition, when the transmission media is overwhelmed by these RREQ messages, a collision of the data packets takes place. The aforementioned issues are known as the broadcast storm problem (BSP).^6,7

More importantly, the majority of broadcasting techniques in MANET are classified into four main schemes: (1) simple flooding, (2) probability-based, (3) area-based, and (4) neighbor knowledge schemes.⁸ Although the flooding scheme provides good reachability in the case of the sparse network, in the dense topology, it is considered a resource wasting mechanism. In addition, the area-based and probability-based schemes are undesirable in the dense static network.⁸ In contrast, Kim et al.⁹ indicated that neighbor knowledge scheme is the best among the others. Furthermore, the information about the neighbors could be easily gathered at the node itself, from the neighbors table without the use of any professional devices such as global positioning system (GPS). Moreover, the scalability of the network could be improved by mitigating the routing overhead.¹⁰

Thus, we obtain the initial motivation to use neighbor knowledge scheme along with the probability scheme, so that we benefit from combining their advantages.

Recently, NCPR¹¹ protocol has been proposed to solve the problem of the flooding in the RREQ. However, the NCPR protocol still suffers from routing overhead in the dense network. Thus, in this article, a new protocol is proposed to overcome the inherited routing overhead in NCPR due to the extra RREQ. As a result, the new protocol enhances scalability when the network is witnessing a high-density number of nodes.

This article contributes to the research field as follows:

Introduces a new routing protocol (scalable neighbor-based mobile routing (SNBR)) to reduce the routing overhead based on a novel formula aim to govern the broadcast of RREQ.

Combines and evaluates the two broadcasting schemes, which are the neighbor knowledge and probability-based so as to enhance the overall network performance.

The proposed protocol overcomes the NCPR protocol by 58.80% in terms of normalized routing overhead, 2.7% packet delivery ratio, 5.68% end-to-end delay, and 3.12% medium access control (MAC) collision on average, while saving 9.7% of the node energy. Furthermore, as compared to AODV, 53.52% in terms of normalized routing overhead, 5.98% packet delivery ratio, 23.16% end-to-end delay, and 54.29% MAC collision on average, while saving 7.64% of the node energy for the first scenario.

In section “Related work,” we review the previous work and provide background on broadcasting schemes. Section “SNBR components” describes the new proposed protocol SNBR in detail. Section “The SNBR implementation” presents the simulation scenario and the performance metric used to valid the proposed protocol. Section “Results and discussion” shows the result and discussions based on the experiment scenarios. Finally, the conclusion and future work for the proposed work are presented in section “Conclusion.”

Related work

Fundamentally, routing in decentralized network with mobile and self-reconfiguration nodes forming an unpredictable topology is considered a highly complicated task. Therefore, more control packets must be blindly disseminated to all nodes, even if they already received it. In particular, in the route discovery phase, where the RREQ messages are broadcasted to all nodes, as to find a path to a certain destination. Certainly, numerous proposed works were developed to reduce such control packets with intend to improve the network performance. Most of the previously proposed works have been categorized into simple flooding, probability based, neighbor based, and area based in Williams and Camp.⁸ In addition, Tseng et al.⁷ added two more schemes, the counter and cluster based. Normally, to find a path between the source and destination node, only one RREQ message is needed, instead of sending (N) redundant messages. Such number depends on the number of neighbors for that node. We have summarized the previous work in Figure 1 to get deep understanding of previously suggested solutions used to mitigate the redundant RREQ packets.

Figure 1.

Redundant packets solutions.

Furthermore, Bakhouya¹² has classified the broadcasting in routing protocols into statistical-based or geometric-based and network topology based. The later one presents any approach which uses a threshold value to estimate the network density such as the number of extra routing messages. However, the geometric-based method is based on neighbor information.

Location-based scheme is presented in Ko and Vaidya.^13,14 The idea behind this technique is very simple and effective. Once the source node knows some information about the destination, it will broadcast RREQ to the expected zone of the destination based on the GPS. As a result, only nodes in the expected zone will receive the rebroadcast RREQ. However, such GPS can shorten battery life and not all the nodes have such location information tool.

The new dynamic probabilistic route discovery (DPR)¹⁵ is a routing protocol designed to reduce the redundant packets RREQ. In this work, they have used the coverage area and the neighbor information as factors to calculate the forwarding probability, and as in equation (1), they have considered that the node is located in the middle of the simulation area. However, since nodes are mobile node and free to move to any location, with this in mind, they should consider such case. Meaning that the coverage ratio $α$ must be divided by four for these nodes which are located at the boundary of the simulation area (A)

α = \frac{π \times R^{2}}{A}

(1)

where R is the signal transmission range.

Another proposed work suggested, based on the probability-based scheme, that nodes are divided into four groups, such protocol called leveled probabilistic routing protocol.¹⁶ Each group has different probability values, which depends on the number of neighbors the node has. Thus, each node should be assigned to one of the four groups. Nevertheless, this approach only applied to the static network rather than dynamic one. It is recommended to use the protocol without using the hello message to reduce its routing overhead.

Furthermore, the predetermined fixed probability has been used to curtail the unwanted extra RREQ,⁷ in this work they came up with optimum value for such probability. However, this value should be dynamic set due to the frequent changes in the nodes location and decentralized control for this type of network.

Mohammed et al.¹⁷ have introduced a counter-based protocol to reduce the routing overhead. The forwarding probability is based on the number of received duplicated RREQ message for a period of time. In case that these counted messages exceed the threshold value, such broadcast will be dropped, else it will be forwarded. Even though this approach reduces the routing overhead, it negatively affects the end-to-end delay.

On the other hand, counter-based scheme has been proposed to mitigate the flooding issues by many researchers, such as in Yassein et al.¹⁸ and Bakhouya et al.¹⁹ In this scheme, each node sets a counter for a random time and starts to count the duplicated packets, once the counter exceeds the threshold value, this RREQ will be dropped. Otherwise, the packets will be forwarded. Nevertheless, such scheme adds extra delay, due to the random waiting time used.

Likewise, Zhang et al.¹¹ came up with NCPR protocol in which the neighbor information is used to make the forwarding probability decision. The technique used in this protocol relieves the redundant or extra RREQ by forwarding such packets to uncovered nodes only. In this case, the nodes which are covered by the previous broadcast will not receive another duplicated RREQ packets. Second, NCPR replaced the random waiting time for subsequent broadcast by rebroadcast delay based on the number of covered neighbors which reduced the overall delay of this protocol. On the other hand, using the excessive number of hello message will consume the nodes energy and introduce another overhead, which in turn negatively affects the overall system performance. As a result, there is a room for further enhancement to develop another approach instead of using the hello message or to use the information from neighbors table. Thus, this article contributes by introducing a new protocol to overcome the preceding issues.

SNBR components

In this section, we present the proposed protocol which relies on the information gathered locally from the node itself. SNBR is based on the relation between the node number of neighbors and the probability of the rebroadcasted RREQ packet. It is necessary to illustrate the main components of SNBR before explaining the full details of the proposed protocol. Such components are route discovery, route reply, and route maintenance.

In the first stage, which is the route discovery, when the source node has data to send to a destination node in the same network, it initiates a route discovery procedure, in which the source node has to find a route from the routing table. However, in the case of no existing route, the source node has to disseminate the RREQ to all neighbors using flooding mechanism until one among the nodes replies, either the destination node itself or any node which has a valid route to the destination node.

Furthermore, once the RREQ received by any node, which has a valid route to the destination node or the destination node itself, they will reply by Route REPly (RREP) messages. Additionally, at any node, in the case of route break down, this node sends Route ERRor (RERR) message to its neighbors to report that broken link.

The proposed protocol only deals with flooding issue at the route discovery by mitigating the redundant RREQ packets. As a result, the system performance will improve. All the recently suggested protocols have their drawbacks as mentioned in the literature, more specifically, the NCPR has extra routing overhead which affects the network scalability. Therefore, there is a room for further enhancement. Thus, the SNBR is proposed to improve the network performance as the number of nodes scale. The next subsection elaborates the parameter setting used in our proposed protocol.

Parameter setting

Basically, the aggregated routing overhead is considered as the main issue for many routing protocols such as the AODV and NCPR. Such overhead consists of the routing discovery overhead and the routing maintenance overhead as in the following equation (2)

R o_{aggregated} = R o_{Discovery} + R o_{R - maintenance}

(2)

In this article, routing overhead generated during the route discovery phase (RREQ) is considered, as shown in equation (3)

R o_{discovery} = R o_{RREQ} + R o_{RREP}

(3)

where $R o_{RREP}$ is the route reply overhead, which is not considered here.

In addition, the total $T_{Ro - RREQ}$ is the sum of all RREQ overhead in the whole network for all nodes, which are looking for path to send their data during the specific time (t) as in equation (4)

T_{Ro - RREQ} = \sum_{i = 1}^{n} R o_{RREQ} (P_{i})

(4)

where n is the total number of RREQ for $(P_{i})$ packets.

The SNBR uses the drop factor $(DF (P_{i}))$ , for every received RREQ packet $(P_{i})$ as a factor. Based on such factor, the packet either dropped or forwarded (the calculation of DF factor will be discussed later in upcoming paragraph). In addition, the relation between the $DF (P_{i})$ and the forwarding probability $FP (P_{i})$ is inverse relation

DF (P_{i}) \propto \frac{1}{FP (P_{i})}

To clarify, when the DF value increases, the FP value decreases, and the maximum value for both parameters is equal to one and minimum value is equal to zero. Furthermore, to calculate the forwarding probability for any packet, equation (5) must be used

FP (P_{i}) = 1 - DF (P_{i})

(5)

At any node j, let $α_{j}$ is the total number of neighbors, such value is gathered from the node’s neighbor table without any extra overhead, and T is the neighbor threshold value, which is a system parameter that can be changed on the fly. Let $β$ be the total number of deployed mobile nodes for a given network. While $α_{j}^{\max}$ is the maximum possible number of neighbors at node j, its value is described in equation (6)

α_{j}^{\max} = β - 1

(6)

where $β \geq 1$ and $α_{j} \in {0, \dots, α_{j}^{\max}}$ .

As known, in a network with high mobility nodes, it is difficult to make a decision either to drop the RREQ packets or not. In SNBR, after $α_{j}$ is gathered, another important value has to be calculated, called $λ_{j}$ as shown in equation (7)

λ_{j} = {(\frac{α_{j}}{T})}^{2}

(7)

Basically, $λ_{j}$ is the ratio of the number of neighbors a node has over the neighbor threshold value. In the case that the $α_{j}$ is greater than T value, its value will be set to T. Clearly, $λ_{j}$ reflects necessity of forwarding such packet. For instance, if a node is located in a dense network, its number of neighbors is high; as a consequence, the necessity of such packet is low. In contrast, if the number of neighbors is low compared to the threshold value, this packet must be forwarded, due to the sparse topology it is located in.

In order to get better and fair performance among all the performance metric, we removed the square of the right part of equation (7) as in equation (8) and tested the result of both equations

λ_{j}^{'} = (\frac{α_{j}}{T})

(8)

As it can be seen from Figure 2, $λ_{j}$ provides better results compared to $λ_{j}^{'}$ . The $λ_{j}$ curve increases gradually, while the $λ_{j}^{'}$ curve increases sharply. Therefore, $λ_{j}$ improves the system throughput by the fair dropping policy compared to $λ_{j}^{'}$ , which has aggressive dropping policy. Thus, equation (7) is used in our proposed work.

Figure 2.

The $λ_{j}^{'}$ versus $λ_{j}$ as the number of neighbors increases.

In addition, the values of $λ_{j}^{\max}$ and $λ_{j}^{\min}$ are based on the T value, which are calculated as in equations (9) and (10), respectively

λ_{j}^{\max} = lim_{α_{j} \to T} λ_{j} = 1

(9)

where $λ_{j} = T$

λ_{j}^{\min} = lim_{α_{j} \to 0} λ_{j} = 0

(10)

where $λ_{j} < T$ .

Based on equations (9) and (10), the maximum value for $λ_{j}$ is equal to one when the network is dense, while the minimum value is zero when the network is sparse.

Finally, the last step is to calculate and make the dropping decision based on the DF, the drop factor is calculated as in equation (11)

DF (λ_{j}) = 1 - \sqrt{1 - λ_{j}}

(11)

In equation (11), the square root is used, which reflects the relation between the network density and dropping decision. Consequently, by calculating the $DF (λ_{j})$ for packet $(P_{i})$ , the value is compared to random real value between [0,1]. The random real value between [0,1] is used to achieve fair decision when determining to drop or forward the RREQ packets. Furthermore, to be fair in comparison, our proposed protocol used the same random value used in the NCPR.¹¹

Moreover, in some cases where all the nodes are located in a dense network, such random value gives chance to RREQ to be forwarded, even though the DF value is close to one.

Basically, there are two expected cases for comparing the DF and random value which are as follows:

Case 1. If the drop factor is greater than the random value, the packet will be dropped, which means this node is located in a dense network.

Case 2. The drop factor is less than or equal to the random value, which means the node is located in a sparse network, so RREQ packet has to be sent to avoid network partition.

Parameter relationship

This subsection presents the relation between the system parameters. Figure 3 shows the relation between the drop factor DF and forwarding probability FP of the RREQ in SNBR. Obviously, as the number of neighbors of any node increases, the drop factor value increases as well. In contrast, the probability of this RREQ message to be rebroadcasted becomes low. In addition, once the number of neighbors reaches the threshold value (14), the probability value becomes zero. The threshold value has been chosen after running many extensive experiments.

Figure 3.

The drop factor versus forwarding probability in SNBR.

Furthermore, Figure 4 clearly depicts the relation between $λ_{j}$ and the density of nodes, which is a proportional relation. However, as the density of neighbors increases, the value of DF becomes close to zero, which depends on the value of $λ_{j}$ as it approaches one. Similarly, the probability FP of any RREQ to be forward becomes so low, as the value of $λ_{j}$ approaches one.

Figure 4.

Relation between the $λ_{j}$ , DF, FP, and nodes density.

The threshold value T in the SNBR with different values from 1 to 20 has been tested to show the relation between the normalized routing overhead and T as shown in Figure 5 with number of 150 nodes, which is the average number of nodes used in our experiment.

Figure 5.

The impact of threshold on normalized routing overhead.

Figure 6 depicts the relation between the threshold and the packets delivery ratio, such relation is a proportional relation.

Figure 6.

The impact of threshold T on packet delivery ratio.

Ultimately, the key point of the proposed protocol is the drop factor $(λ_{j})$ which reflects the relation between the number of neighbors and the rebroadcasting probability. As the number of neighbors increases, the forwarding probability decreases and the drop factor increases. When DF value approaches one, this reveals that this node is located in a dense area; as a consequence, such broadcast should be prohibited. However, some neighbors of that node might already rebroadcasted the same packets. Undoubtedly, there is a trade-off between the dropping and forwarding of the RREQ packets, in order to reduce the routing overhead while providing the highest packets delivery ratio, low delay, and MAC collision with minimum possible power.

The algorithm details

Algorithm 1 presents the pseudo-code of SNBR mechanism which is developed to work on dense and sparse networks to enhance the overall performance and resource utilization. Although, nodes are located in a network with high traffic or low traffic. Figure 7 shows the flow control diagram of SNBR, and the following subsections explain the proposed algorithm in detail.

Algorithm 1: Pseudo-code of SNBR Protocol To Mitigate Redundant RREQ Packets.
1 Initialization:
2 β ← Total No. of mobile nodes.
3 α_j ← No. of neighbors at node (j).
4 $α_{j}^{max}$ ← Maximum No. of neighbors.
5 T ← Neighbor threshold value.
6 EventOn RREQ Receiption (P_i) do
7 ifα_j > Tthen
8 α_j = T.
9 end
10 Calculate λ_j as in equation (7).
11 Calculate DF(λ_j) as in equation (11).
12 ifDF(λ_j) < Random[0,1]then
13 Forward(P_i).
14 else
15 Drop(P_i).
16 end
17 end

Figure 7.

The control flow diagram of SNBR.

The rebroadcasting decision at any receiving node could be described in the few steps as follows:

$S_{1}$ . On hearing a broadcast message $P_{i}$ , calculate total number of neighbors of the current node $α_{j}$ .

$S_{2}$ . If the number of neighbors $α_{j}$ is greater than the neighbor threshold T, then go to $S_{3}$ , else go to $S_{4}$ .

$S_{3}$ . Let $α_{j} = T$ .

$S_{4}$ . Calculate $λ_{j}$ as in equation (7) and the drop factor $DF (λ_{j})$ as in equation (11).

$S_{5}$ . If $DF (λ_{j})$ < randomly generated value [0,1], then go to $S_{6}$ , else go to $S_{7}$ .

$S_{6}$ . Forward $P_{i}$ go to $S_{8}$ .

$S_{7}$ . Discard $P_{i}$ .

$S_{8}$ . Exist.

The SNBR implementation

The SNBR protocol has been implemented using NS-2 simulation tools with the latest version (2.35).²⁰ The source code of AODV protocol has been modified to implement the SNBR protocol, the modification has been made to the RREQ receiving function. Neither the hello message is used here nor any modification has been made to RREQ header. These added another advantage to the new proposed protocol SNBR. In addition, the implementation of SNBR has not added any complicated processes, except the calculation of the drop factor as in equation (11) which is not a complicated equation.

The SNBR evaluation

In order to evaluate the performance of the new proposed protocol (SNBR), the SNBR was compared to two of the widely deployed and the latest routing protocols in MANETs, namely, NCPR protocol¹¹ and the well-known protocol AODV (the latest version).

The simulation parameters used in the experiment, such as the transmission range of each node, is 250 m, the mobility and the node position has been generated with the random waypoint model using the provided tools accompanied with the NS-2 package using setdest command version 2 as follows:

./setdest -v 2 -n 150 -s 1 -m 1 -M 5 -t 300 -p 0 -x 1000 -y 1000

The setdest command used here follows the uniform distribution and 27 scenarios have been chosen out of 1300 trials from those generated mobility models. Additionally, the speed of the nodes vary from minimum speed, its value is set to 1 up to maximum speed value equals to 5. The pause time is equal to zero with topology sizes 1000 m × 1000 m and the packet size used is 512 bytes, the bandwidth 2 Mbps. Moreover, the nodes are connected using constant bit rate (CBR) varying from 10, 12, to 20. Table 1 summarizes the simulation parameters used in our experiments.

Table 1.

Performance parameters.

No.	Simulation parameters	Value(s)
1	Simulator	NS-2 version (2.35)
2	Number of nodes	50, 100, 150, 200, 250, 300
3	Size of the topology	1000 m × 1000 m
4	Node transmission range	250 m
5	Connection type	CBR
6	Size of the packet	512 bytes
7	Nodes min speed	1 m/s
8	Nodes max speed	5 m/s
9	Pause time	0 s
10	The number of CBR connection	10, 12, 14, 16, 18, 20
11	Packet rate	4 packets/s
12	Route bandwidth	2 Mbps
13	Interface queue length	50

CBR: constant bit rate.

The performance metrics

To evaluate the SNBR protocol, five performance metrics have been used, starting with normalized routing overhead, packet delivery ratio, average of end-to-end delay, the MAC collision rate and ending with average of energy consumption. To analyze the effect of the scalability and the traffic load, the experiment has been divided into two scenarios:

Scenario 1. In order to analyze the effect of the scalability on the performance of the system, we started the experiment using 50 nodes and then increased them by 50 nodes until they reach 300 nodes.

Scenario 2. To test the effect of the traffic load on the system performance, we started the experiment using 10 CBR traffic and then we increased them by two CBR traffic until they reach 20.

The following are the definitions of performance metrics used for both scenarios:

Normalize routing overhead. It is calculated based on the total control packet size over total data packet size.

Packet delivery ratio. The average of successfully delivered data packets divided by the average of sent data packets (CBR traffic).

Average of end-to-end delay. The time taken by CBR packets from the source node to destination node.

MAC collision rate. The average of the packets dropped at MAC layer due to the collision. (Packets are RREQ, RREP, RERR, and CBR per second.)

Average of energy consumption (J). The average of total energy consumed by all the nodes during the simulation time.

All the aforementioned metrics have been applied on both scenarios. To limit the effect of mobility on the network performance, we calculate the average of 27 trials. Moreover, the comparison (average) is calculated using equation (12) between the SNBR and AODV, and SNBR and NCPR

A V G = (\frac{\sum_{i = 1}^{n} (\frac{x_{i} - y_{i}}{y_{i}})}{n}) \times 100 %

(12)

where $x_{i}$ is the performance metrics of the first protocol, $y_{i}$ is performance parameters of second protocol, and n is the number of trials.

Results and discussion

The result of three routing protocols AODV, NCPR, and the proposed protocol SNBR is discussed in the following subsections for both scenarios when the density and the traffic increase.

Performance analysis with varied number of nodes

Fundamentally, when the number of nodes increases, it decreases the performance of the whole network; however, the reachability of the nodes improves due to network density.

In the first scenario as shown in Figure 8, SNBR has outperformed both protocols NCPR and AODV, in terms of normalized routing overhead due to its forwarding approach. As the density of nodes increases, the SNBR presents low sensitivity to this issue, whereas AODV and NCPR are highly affected by such increase. SNBR protocol achieves lower normalized routing overhead than AODV by 53.53% on average. In addition, as against NCPR protocol, the SNBR clearly reduces the same metrics by 58.80% on average. As the network becomes more dense, the more RREQ packets will be dropped.

Figure 8.

Normalized routing overhead versus number of nodes.

From Figure 9, it is clear that the proposed protocol improves the network delivery ratio, as the number of nodes increases. Thanks to the drop factor mechanism used in SNBR, which shows good enhancement even though the density of the network is high. In contrast, AODV shows the lowest performance, especially in the dense network. Even though the NCPR protocol enhances the delivery ratio compared to AODV, it fails to work in the low-density environment. Certainly, by comparing such valuable result of SNBR to AODV protocol and NCPR the improvement percentage are 19.51% and 7.2% respectively, in the dense network (300 nodes). As more RREQ packets dropped, more data packets will get chance to reach their destination.

Figure 9.

Packet delivery ratio versus number of nodes.

The average of end-to-end delay with increasing number of nodes is shown in Figure 10. Obviously, the AODV protocol suffers from high delay in the high-density network. In addition, the NCPR protocol shows a slight increase in the low-density network due to its dropping scheme. In contrast, using the drop factor scheme, SNBR shows good improvement when compared to others. On average, the percentage of such improvement compared to AODV is 5.68% and to NCPR is 23.16%. Moreover, compared to AODV in the dense network when the number of nodes reaches 300, the SNBR achieves 69.75%, as result of applying the aggressive dropping policy.

Figure 10.

Average end-to-end delay versus number of nodes.

In Figure 11, MAC collision rate is plotted against the increasing number of nodes. Our proposed SNBR outperforms both AODV and SNBR by 3.12% and 54.29%, respectively. This was as a result of its ability to mitigate the generation of excessive redundant RREQ due to dropping policy used. NCPR mechanism exhibits similar features to SNBR toward resisting RREQ generation, thus following a similar trend to SNBR. AODV on the other hand increases rapidly as the number of nodes increases; this is as a result of the flooding mechanism employed which performs poorly in mitigating the excessive generation of RREQ.

Figure 11.

MAC collision versus number of nodes.

A scarce resource, such as the battery lifetime, is critical for many routing protocol developers in MANET. As in Figure 12, the proposed protocol achieves good enhancement, despite the increase in the number of nodes. Compared to NCPR and AODV, SNBR achieves 9.7% and 7.64% on average, respectively. Significantly, this metric proves that the mechanism used in the SNBR is valid to be used in many routing protocols. Furthermore, as the number of packets reduced, the more energy will be saved.

Figure 12.

Average energy consumption versus number of nodes.

To summarize, once the number of node increases, the number of neighbors increases as well, the SNBR becomes more rigorous to drop the RREQ packets. However, some of the other neighbors might rebroadcast the same packet.

Performance with varied traffic load

In the second scenario, the network performance has been tested under a varied number of CBR connections with fixed number of nodes to analyze the impact of the traffic load in the whole network. The experiment started with 10 connections and was gradually increased in step of two until it reaches 20 (maximum connection). In Figure 13, the proposed protocol has achieved significant improvement even when the number of connections is high (congested network). Such improvement with NCPR protocol is 59.54% on average. In addition, when SNBR is compared to AODV protocol in high congested scenario (20 nodes), SNBR has overcome the AODV by 59.54% and 50.02% with NCPR on average. All the previously mentioned improvement due to the dropping policy used in SNBR based on the number of neighbors for each node surely reflects the actual status of the current node.

Figure 13.

Normalized routing overhead versus number of CBR connections.

Fundamentally, by reducing the routing overhead, the other performance metrics will improve. In terms of packet delivery ratio, SNBR outperforms both NCPR and AODV, even though the number of connections increases, as it is shown in Figure 14. In addition, as the number of connection increases, the gap in the performance increases gradually, especially when the number of connections increases to 20 connections. The improvement percentage is 9.26% with AODV and 1.28% with NCPR on average. Furthermore, clearly as the number of connections increases, the SNBR performs better compared to others.

Figure 14.

Packets delivery ratio versus number of CBR connections.

In Figure 15, the SNBR manages to maintain the delay as low as possible undeterred by an excessive number of nodes in the network. However, as against the AODV, the SNBR reduces the end-to-end delay by 41.85% on average. Furthermore, in the event of high traffic, SNBR is slightly better compared to NCPR. In fact, the proposed protocol achieves the enhancement by reducing the number of RREQ packets which cause a delay of the packets and not to mention the dropping and retransmitting of those packets.

Figure 15.

End-to-end delay versus number of CBR connections.

In the same manner, the proposed work in this article relies on eliminating the broadcast to only nodes which are located in space or low congested area as a method to reduce the enormous data or control packets dropped by collision at the MAC layer since all the nodes compete to send at the same time. Moreover, these nodes share the same media to transfer all the data and control packets. Although the SNBR shows a slight increase in the low traffic network, due to its drop policy, the number of neighbors is too low. However, when the traffic boost is achieved (20 connections), an average enhancement of 51.9% is shown in SNBR over AODV and a 36% in SNBR over NCPR as shown in Figure 16.

Figure 16.

MAC collision versus number of CBR connections.

It is equally important to reduce wasted energy that nodes consume. In order for these nodes to find the path, they must broadcast the RREQ and flood the network with these packets which will reduce the battery lifetime. As mentioned previously, the method of reducing the extra packets will reduce the energy consumption at the same time maintain good performance in the case of spare or low traffic network. As a result, the SNBR compared to NCPR gains 10.98% and 5.75% as against the AODV, as shown in Figure 17, since NCPR depends on periodic broadcast hello message.

Figure 17.

Average energy consumption versus number of connections.

To conclude, the achieved results for all the performance metrics are based on the necessity of the RREQ. Dropping decision is based on the node density; if the node is located in a dense area, this packet must be dropped since one of the neighbors may already rebroadcast it. As a result, the more packets dropped the less interference, thus more data to be sent, less collision, and low energy consumption.

Conclusion

SNBR protocol reduces the routing overhead, end-to-end delay, and the MAC collision rate, while improves the packet delivery ratio using the drop policy based on a number of neighbors for each node. Not only the four mention metrics but also wasted energy by redundant packets has been enhanced as compared to both NCPR and AODV protocol. SNBR mitigated the problem of extra RREQ in the first stage route discovery, based on the inverse relation between the number of neighbors and the probability of the rebroadcasted RREQ messages. However, for future work, we plan to test the SNBR with different mobility models different from random waypoint model. Furthermore, we plan to compare the proposed protocol to other protocols such as DSR or destination-sequenced distance vector (DSDV) routing used in MANETs while using different performance metrics.

Footnotes

Academic Editor: Pietro Manzoni

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 was partially supported by Universiti Putra Malaysia and the Ministry of Higher Education (The National Authority for Scientific Research), the State of Libya.

References

Safa

Karam

Moussa

. PHAODV: power aware heterogeneous routing protocol for MANETs. J Netw Comput Appl 2014; 46: 60–71.

Perkins

Belding-Royer

Das

. Ad hoc on-demand distance vector (AODV) routing (RFC 3561). Internet RFCs, 2003, pp.1–38, https://www.ietf.org/rfc/rfc3561.txt

Johnson

Maltz

. The dynamic source routing protocol (DSR) for mobile ad hoc networks for IPV4 (RFC 4728), 2007, https://www.ietf.org/rfc/rfc4728.txt

Y-B

Vaidya

. Location-aided routing (LAR) in mobile ad hoc networks. Wirel Netw 2000; 6(4): 307–321.

Haas

Pearlman

Samar

. The zone routing protocol (ZRP) for ad hoc networks, 2002, https://tools.ietf.org/id/draft-ietf-manet-zone-zrp-04.txt

S-Y

Tseng

Y-C

Chen

Y-S

. The broadcast storm problem in a mobile ad hoc network. In: Proceedings of the 5th annual ACM/IEEE international conference on mobile computing and networking (MobiCom ’99), Seattle, WA, 15–19 August 1999, pp.151–162. New York: ACM.

Tseng

Y-C

S-Y

Chen

Y-S

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

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, Bangalore, India, 29 July–1 August 2002, pp.194–205. New York: ACM.

Kim

J-S

Zhang

Agrawal

. Probabilistic broadcasting based on coverage area and neighbor confirmation in mobile ad hoc networks. In: IEEE global telecommunications conference workshops (GlobeCom 2004 workshops), Dallas, TX, 29 November–3 December 2004, pp.96–101. New York: IEEE.

10.

Al Amri

. Enhancing the scalability of heterogeneous MANET routing protocols, 2012, http://ro.uow.edu.au/theses/3864/

11.

Zhang

Wang

Xia

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

12.

Bakhouya

. Broadcasting approaches for mobile ad hoc networks. In: 2013 international conference on high performance computing and simulation (HPCS), Helsinki, 1–5 July 2013, pp.705–707. New York: IEEE.

13.

Y-B

Vaidya

. GeoTORA: a protocol for geocasting in mobile ad hoc networks. In: Proceedings 2000 international conference on network protocols, Osaka, Japan, 13–16 November 2000, pp.240–250. New York: IEEE.

14.

Y-B

Vaidya

. Geocasting in mobile ad hoc networks: location-based multicast algorithms. In: Proceedings WMCSA’99 second IEEE workshop on mobile computing systems and applications, New Orleans, LA, 25–26 February 1999, pp.101–110. New York: IEEE.

15.

Abdulai

J-D

Ould-Khaoua

Mackenzie

. Neighbour coverage: a dynamic probabilistic route discovery for mobile ad hoc networks. In: International symposium on performance evaluation of computer and telecommunication systems (SPECTS 2008), Edinburgh, 16–18 June 2008, pp.165–172. New York: IEEE.

16.

Zhang

Agrawal

. Analysis of leveled probabilistic routing in mobile ad hoc networks. In: IEEE international conference on communications, Paris, 20–24 June 2004, vol. 7, pp.3896–3900. New York: IEEE.

17.

Mohammed

Ould-Khaoua

Mackenzie

. An efficient counter-based broadcast scheme for mobile ad hoc networks. In: Proceedings of the 4th European performance engineering conference on formal methods and stochastic models for performance evaluation, Berlin, 27–28 September 2007, pp.275–283. New York: ACM.

18.

Yassein

Nimer

Al-Dubai

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

19.

Bakhouya

Gaber

Lorenz

. An adaptive approach for information dissemination in vehicular ad hoc networks. J Netw Comput Appl 2011; 34(6): 1971–1978.

20.

McCanne

Floyd

. NS Network Simulator - Version 2, 1998, http://www.isi.edu/nsnam/ns (accessed June 2016).