RETRACTED ARTICLE: Enhanced route discovery using connected dominating set and 2-hop repair in wireless ad hoc networks

Abstract

Efficient routing and broadcasting among a set of nodes play a critical role in wireless adhoc networks. for energy efficient routing, a connected dominating set (CDS) based virtual backbone is a promising approach. In the network, one-hop neighbors are selected as multi point relay (MPR) by each node to cover all its two-hop neighbors for the purpose of broadcasting and 2-hop repair. To improve the network lifetime, energy efficient MPR based CDS construction has been proposed by considering the node degree, energy level, node ID and velocity of the node. We also propose a route discovery protocol to relay route request messages, which makes use of the CDS nodes to obtain a stable routing path; 2-hop repair for route maintenance, which reduces the path damage (reduced control packets with lesser consumption of bandwidth) and broadcast storm problem. The simulation results show that the proposed protocol increases the network lifetime up to 30% than other works and effectively repair damaged routes by reducing control packets.

1 Introduction

The Ad hoc wireless networks are characterized by dynamic topology, multi-hop communication and the availability of limited resources. These features make routing a challenging problem. Most existing routing protocols (Joa-Ng and Lu 1999; Johnson et al. 2001; Pei et al. 2000; Perkins and Royer 1999) rely on flooding for route discovery or topology update. However, flooding is unreliable (Sinha et al. 2001), and it results in excessive redundancy, contention and collision, the notorious broadcast problem (Tseng et al. 2002). The idea is to route the control packets along the backbone nodes to decrease the protocol overhead. The virtual backbone is not only good for routing, but also a good infrastructure for multicast/broadcast in ad hoc networks. In addition, the nodes in the network move in random directions with varied speed and time, which affects the virtual backbone (the link is broken due to the movement of nodes). A complete survey of topology control issues in wireless ad hoc and sensor network using connected dominating sets is discussed in detail in Yu et al. (2013).

Constructing efficient transmission routes are of major importance in the resource constrained environment. The existing routing protocol concentrates on the validation of the route and the transmission delay, but fails to take care of the broadcast issue. The reactive routing protocols send route requests by using flooding technique. Therefore, the increase in the number of hops and connections results in the number of broadcast packets which gradually reduces the efficiency of the network. The goal of the proposed work is to concentrate on broadcasting mechanism and routing protocol to generate a stable route in an effective manner. Here, the concept of multi point relaying (MPR) (Liang et al. 2006) is proved to be efficient and incorporated with the proper routing protocol. The selected relay nodes are responsible for broadcasting to neighbor nodes periodically. Therefore, a connected dominating set consists of these entire relay nodes and to obtain such nodes is an NP-hard problem. Many algorithms have been proposed to reduce the CDS size based on the concept of multi point relaying. Nodes are selected based on the node ID or node degree as in MPR based CDS schemes (Wu et al. 2006; Wu 2003; Chen and Shen 2004; Adjih et al. 2005; Badis et al. 2004). Other parameters such as energy, mobility and bandwidth are not yet considered for the selection of CDS nodes. In this proposed work, the CDS based on MPR is constructed by considering together the node degree, energy level, node ID and velocity of the node.

In the ad hoc networks, as the position of the node changes frequently, there is a need for the best path repair mechanism. Few routing protocols like AODV (Perkins and Royer 1999), AOMDV (Marina and Das 2001) and MPRDV (Allard et al. 2003) rebroadcast the ‘Route Request’ in case of route repair. In AODV, all the nodes in the network receive the ‘Route Request’ and transfer it to the remaining nodes in the network by means of flooding. This results in higher bandwidth consumption and increased packet arrival ratio, which degrades the overall performance of the network in large networks.

AOMDV adopts a multipath approach between the source and the destination node. Each and every node in the network has multiple unused paths in the routing table for alternate paths. This leads to the prolonged ‘Route Reply’ packets and increases the network congestion. Few researchers concentrate on energy efficient broadcasting (Rieck and Dhar 2011), k-hop shortest path pruning method for efficient broadcasting (Elhoseny and Singh 2019) and 2-hop neighbors table based broadcasting (Bai et al. 2014) to improve network lifetime with effective transmission. Therefore, in our proposed work, to enhance the routing efficiency, Multipoint Relaying is embedded with 2-hop Repair (MPR-2R) mechanism which achieves efficient transmission. The proposed local repair mechanism helps to reduce the number of broadcast packets; thereby it repairs the damaged path effectively. When ‘Route Request’ or ‘Route Reply’ is sent, the intermediate node records the position of the last two broadcasting node. For example, if a node along the path becomes dead/invalid, the path can be repaired by locating other possible hops of the nodes in the 2-hop adjacent list table. Finally, the new valid 2-hop positions are broadcasted to the nearby nodes. Hence, this local repair mechanism ensures path validity without broadcasting a ‘Route Request’.

The rest of the paper is arranged as: the existing CDS construction techniques are discussed in Sect. 2; Sect. 3 describes the MPR based CDS construction and 2-hop Repair (MPR-2R). Performance evaluation and Conclusion is discussed in Sects. 4 and 5, respectively.

2 Related works

In wireless ad hoc networks, many works have been proposed for multipoint relaying technique which is used for the purpose of flooding (Abdallah 2018). When constructing an MPR, each node $x$ has a Multipoint Relay Set (MRS) which is obtained by selecting a subset of 1-hop neighbors in the network. The set of nodes in the MRS is responsible for forwarding the packet from node $x$ to its 2-hop neighbors. As in Qayyum et al. (2002), obtaining a minimum size MRS is found to be NP-Complete. Therefore, the nodes in the MRS form a local dominating set for a particular node $x$ that in turn dominates its 2-hop neighbor nodes. The authors in Adjih et al. (2005) proposed a source independent MPR which constructs a global CDS based on the MPR technique (MPR_CDS). The algorithm presumes that each node has a unique ID with which the global CDS has been constructed. The simple rules for constructing the MPR_CDS are as follows

• R1: Node $x \in MPR\_CDS \Leftrightarrow y \subseteq \hbox{min}$ (ID) among the 1-hop neighbors.

• R2: Node ${\text{y}} \in MPR\_CDS \Leftrightarrow y \in z^{\prime}s$ MRS where z ID is smallest among $y^{\prime}s$ 1-hop neighbors.

However, the CDS generated by MPR_CDS are not efficient as the selection is based on the node ID. The nodes selected by the first rule (R1) are redundant, which increases the complexity of the network. To overcome this problem, an Enhanced MPR (EMPR) (Wu et al. 2006) was proposed by modifying the rule (R1) to

• R1: Node $y \in MPR\_CDS$ iff $y$ has the smallest ID amongst 1-hop neighbors with atleast two disconnected or independent neighbors.

This leads to high computation complexity in EMPR. Other works on MPR based CDS construction include, the authors in Chen and Shen (2004) examine that the node degree is associated with the CDS size compared to that of the node ID and the rules have been extended as

• R1: Node $y \in MPR\_CDS$ if $y$ has max (node degree) amongst 1-hop neighbors with two independent neighbors.

• R2: Node $y \in MPR\_CDS$ if the node that selects $y$ as MPR should have max (node degree) amongst its 1-hop neighbors.

However, Wu (2002) modified the CDS generated by MPR_CDS in Adjih et al. (2005) by considering the concept of free neighbors in the network. The modified rule is

• R1: Every node $y$ in the network adds it’s free neighbors to its MPR set.

• R2: Node $x$ is said to be a free neighbor of node $y$ iff $x \in N\left( y \right)$ and $y$ should not be the minimum ID neighbor of node $x$.

A greedy algorithm as in Fu et al. (2016) is designed to construct the Minimum Connected Dominating Set (MCDS) in wireless networks. The authors employ the GR_CDS algorithm to construct the MCDS which obtains a relatively optimal CDS size followed by P_CDS algorithm to prune the redundant nodes in the network; rather the performance time is greatly increased. An energy efficient dominating tree algorithm as proposed in Yu et al. (2009) has the marking process and the connection phase. In their algorithm, a Maximal Independent Set (MIS) is obtained by marking process and in addition, connectors are added to form a CDS. In order to enhance the CDS node lifetime and minimize the size of the CDS, power aware connected dominating set (Wu et al. 2002) is proposed by considering the node’s degree and residual energy. Furthermore, node velocity is intended to define stable connected dominating set as in Meghanathan (2010). Here, the author does not consider the node with high mobility and velocity. The author in Ramalakshmi and Radhakrishnan (2012) constructs a stable connected dominating set by considering energy level and velocity. This reduces the CDS size and makes the node stable with varied velocities.

As the nodes change its position frequently, there is a possibility of route outbreak, which results in path repair problem. In order to construct the new route or rebuild the damaged route, more control packets are used for the recovery. The author in Mtibaa and Kamoun (2006) incorporates MPR technique with AOMDV by introducing multiple path formation during path damage. This results in usage of number of control packets. In Mosko et al. (2003), the route request messages are distributed in AODV by applying dominant pruning rules.

In Rab et al. (2017) an improved self-pruning based broadcasting algorithm is used to broadcast packets with extended neighbor knowledge which reduces the forwarding nodes. The author claims that, in denser network, self pruning performs better than dominant pruning which consumes less bandwidth and decreases message overhead. The 2-hop horizon pruning is used to acquit the route request in Spohn and Garcia-Luna-Aceves (2006). The authors used radio range to obtain 2-hop dominating set. By taking into consideration all these factors that affect the CDS construction and route maintenance. The proposed work has the following contributions.

• 1. MPR based CDS construction using ‘Marking Process’ for the purpose of broadcasting.

• 2. Prune all the dominating nodes by considering energy level, node ID, node degree and velocity.

• 3. Obtain final CDS after pruning to relay ‘Route Request’ messages and to reduce ‘Broadcast Storm Problem’.

• 4. 2-Hop route repair for route maintenance and to reduce path damage (reduced control packets) using MPR-2R.

3 MPR based CDS construction and 2-hop repair (MPR-2R)

3.1 Problem definition

An ad hoc network is modeled as a graph $G = \left( {V, E} \right)$, where $V$ indicates the set of nodes and the edge set $E$ represents all the links in the network (Hiyama et al. 2010). A homogenous network is deployed in 2D Euclidean plane, where each node has a uniform transmission range R as stated in Ramalakshmi and Radhakrishnan (2012). A wireless link $\left( {u, v} \right) \in E$ is said to exist, if the two nodes are within the transmission range of each other.

Connected dominating set (CDS) For a given graph $G = \left( {V, E} \right)$, a Dominating Set (DS) is a subset $D \subseteq V$, such that for every vertex $v \in V$, either $v \in D$ or $V$ has a neighbor in $D$. Therefore, the subset $D$ is called connected dominating set if the graph $G^{\prime}$, induced by $D$ is connected (i.e.) $G^{\prime}\left( D \right)$ is connected.

Multipoint relay based CDS (MPR_CDS) For a given graph $G = \left( {V, E} \right)$ and node $v \in V$, let $N_{1 } \left( v \right)$ and $N_{2 } \left( v \right)$ represent the set of 1-hop and 2-hop neighbors of $v$ respectively. MPR_CDS asks for a minimum size subset MPR of $N_{1 } \left( v \right)$ such that $N_{2 } \left( v \right)$ is covered by MPR. It reduces flooding by minimizing the retransmission of broadcast packets in the network.

MPR-2R For a given graph $G = \left( {V, E} \right)$, when a wireless link does not exist $\left( {u,v} \right) \notin E$, it needs a route repair. The nodes in the MPR_CDS uses 2-hop neighbor table information to complete route repair process.

3.2 Notations and assumptions

Each and every node in the network has the same transmission range $R$. When the calculated Euclidean distance among the nodes is less than $R$, these nodes are said to be connected.

The designed algorithm uses the following notations as listed in Table 1.

Table 1 Notations and descriptions

3.3 MPR-2R algorithm description

The proposed algorithm MPR based CDS construction and 2-hop repair (MPR-2R) consists of three phases as, Neighbor Discovery Phase; MPR based CDS Formation Phase and 2-hop Route Repair Phase.

3.3.1 Neighbor discovery phase

Initially, the nodes in the network exchange ‘HELLO’ messages periodically to all its 1-hop neighbors. These nodes just send and receive the message, but do not forward them. The ‘HELLO’ message contains information such as Node ID—${\text{ID}}\left( {\text{x}} \right)$ Energy—${\text{E}}\left( {\text{x}} \right)$, velocity—${\text{V}}\left( {\text{x}} \right)$, node degree—D(x) and a list of neighbors $N^{1} \left( x \right)$. This allows the nodes to be aware of its 2-hop neighbor set as $N^{2} \left( x \right)$ as shown in Fig. 1.

Fig. 1

1-Hop and 2-hop neighbor table

3.3.2 MPR based CDS formation phase

In the CDS formation phase, basically using the simple greedy algorithm, node $x$ locally selects a set $MPR\left( x \right)$ of it’s $N_{G} \left( x \right)$ as its multi point relay as shown in Fig. 2. Followed by the pruning phase, it helps to reduce the size of the connected dominating set. In Wu et al. (2006), a distributed algorithm based marking process is used to construct connected dominating set in Ad Hoc Networks, which in turn is used to select the multipoint relay nodes in our proposed work. In order to reduce the size of the MPR and to obtain a final MPR_CDS, pruning process proposed by Yu et al. (2009) is used by considering additionally the residual energy and velocity of the nodes.

Fig. 2

MPR selection to form connected dominating set

• MPR selection phase

  In the MPR selection phase, initially all the nodes in the network are white in color as shown in Fig. 3. When a node $x$ has two disconnected neighbors, it assigns it’s $N_{G} \left( x \right)$ to $MPR \left( x \right)$ and changes the color of the nodes in $MPR \left( x \right)$ to Black. Finally, all the neighbor nodes of $MPR \left( x \right)$ are marked in Gray color as shown in Fig. 4.

  Fig. 3

  

  Example graph (initial phase)

  Fig. 4

  

  MPR selection

  The nodes obtained from the MPR selection phase form the local CDS nodes and the graph induced by the local CDS be $G^{'}$. Therefore, the nodes in the $MPR \left( x \right)$ are {1, 2, 9, 10, 15, 16, 17, 18, 23, 26, 27}.

• Pruning phase

  In the following, three rules have been proposed as R1, R2 and R3 based on the residual energy and velocity of the node. This helps to increase the overall network lifetime and at the same time, it minimizes the size of the CDS which is obtained from the previous step. In order to maintain a stable network, the residual energy and velocity are considered as primary factors in choosing the CDS node. The graph induced by CDS is considered to be $G^{\prime}$.

R1: Consider the two vertices $x$ and $y$ in $G^{\prime}$. The marker of $y$ is changed to gray color if any one of the following conditions holds:

• i. $N_{G} \left[ y \right] \subseteq N_{G} \left[ x \right]$ in $G$ and $E\left( y \right) < E\left( x \right)$.

• ii. $N_{G} \left[ y \right] \subseteq N_{G} \left[ x \right]$ in $G$ and $V\left( y \right) > V\left( x \right)$ when $E\left( y \right) = E\left( x \right)$.

• iii. rule represents that$N_{G} \left[ y \right] \subseteq N_{G} \left[ x \right]$ in $G$ and $D\left( y \right) < D\left( x \right)$ when $V\left( y \right) = V\left( x \right)$, $E\left( y \right) = E\left( x \right)$.

• iv. $N_{G} \left[ y \right] \subseteq N_{G} \left[ x \right]$ in $G$ and $ID\left( y \right) < ID\left( x \right)$ when $D\left( y \right) = D\left( x \right)$, $V\left( y \right) = V\left( x \right)$, $E\left( y \right) = E\left( x \right)$.

The above rule represents that; node $y$ can be removed from the graph $G^{\prime}$ when the closed neighbor set of $y$ is completely covered by the node $x$ if the residual energy of node $y$ is smaller than the node $x$. When the energy levels of the two nodes $x$ and $y$ are same, the velocity of the node is used to break the tie. Furthermore, when all the parameter values are same, node ID breaks the tie. It is clear that $G^{\prime} - \left\{ { y } \right\}$ is still a connected dominating set of $G$ as shown in Fig. 5, where the condition $N_{G} \left[ y \right] \subseteq N_{G} \left[ x \right]$ holds good in all situations which infer that node $x$ and $y$ are connected in $G^{\prime}$.

Fig. 5

After applying rule R1

R2: Consider the two vertices $x$ and z in $G^{'}$ as marked neighbors of the marked vertex $y$. The marker of $y$ is changed to gray color if any one of the following conditions holds:

• i. $N_{G} \left[ y \right] \subseteq N_{G} \left[ x \right] \cup N_{G} \left[ z \right]$, but $N_{G} \left[ x \right]{ \nsubseteq }N_{G} \left[ y \right] \cup N_{G} \left[ z \right]$ and $N_{G} \left[ z \right] { \nsubseteq }N_{G} \left[ x \right] \cup N_{G} \left[ y \right]$ in $G$

• ii. $N_{G} \left[ y \right] \subseteq N_{G} \left[ x \right] \cup N_{G} \left[ z \right]$ and $N_{G} \left[ x \right] \subseteq N_{G} \left[ y \right] \cup N_{G} \left[ z \right]$, but $N_{G} \left[ z \right] { \nsubseteq }N_{G} \left[ x \right] \cup N_{G} \left[ y \right]$$N_{G} \left[ x \right] \cup N_{G} \left[ y \right]$ in $G$; one of the conditions holds

  a. $E\left( y \right) < E\left( x \right)$ or

  b. $E\left( y \right) = E\left( x \right)$ and $V\left( y \right) > V\left( x \right)$ or

  c. $E\left( y \right) = E\left( x \right)$ and $D\left( y \right) < D\left( x \right)$, $V\left( y \right) = V\left( x \right)$ or

  d. $E\left( y \right) = E\left( x \right)$ and $ID\left( y \right) < ID\left( x \right)$, $D\left( y \right) = D\left( x \right)$, $V\left( y \right) = V\left( x \right)$.

The above rule depicts that, when $y$ is covered by $x$ and $z$; in case (i) node $y$ can be removed from $G^{'}$, if neither $x$ nor $z$ is covered by the other two among $x, y$ and $z$; case (ii) if nodes $y$ and x are covered by the other two among $x, y$ and $z$, but $z$ is not covered by $x$ and $y$, node $y$ can be removed from $G^{\prime}$.

R3: Consider the two vertices $x$ and z in $G^{'}$ as marked neighbors of the marked vertex $y.$ The marker of $y$ is changed to gray color if

• i. $N_{G} \left[ y \right] \subseteq N_{G} \left[ x \right] \cup N_{G} \left[ z \right]$ and $N_{G} \left[ x \right] \subseteq N_{G} \left[ y \right] \cup N_{G} \left[ z \right]$ and $N_{G} \left[ z \right] \subseteq N_{G} \left[ x \right] \cup N_{G} \left[ y \right]$ in $G$; one of the conditions holds

• a. $E\left( y \right) < E\left( x \right)$ and $E\left( y \right) < E\left( z \right)$ or

• b. $E\left( y \right) = E\left( x \right) < E\left( z \right)$ then

  $D\left( y \right) < D\left( x \right)$ when $V\left( y \right) = V\left( x \right)$ or

  $V\left( y \right) > V\left( x \right)$ or

  $ID\left( y \right) < ID\left( x \right)$ when $D\left( y \right) = D\left( x \right)$, $V\left( y \right) = V\left( x \right)$.

• c. $E\left( y \right) = E\left( x \right) = E\left( z \right)$ then

• 1. $V\left( y \right) > V\left( x \right)$ and $V\left( y \right) > V\left( z \right)$ or

• 2. $V\left( y \right) = V\left( x \right) > V\left( z \right)$ and $D\left( y \right) < D\left( x \right)$, $ID\left( y \right) < ID\left( x \right)$

• 3. $V\left( y \right) = V\left( x \right) = V\left( z \right)$ and $D\left( y \right) < D\left( x \right)$ and $ID\left( y \right) = \hbox{min} \left\{ {ID\left( y \right), ID\left( x \right), ID\left( z \right)} \right\}$

The condition $N_{G} \left[ y \right] \subseteq N_{G} \left[ x \right] \cup N_{G} \left[ z \right]$ implies that $x$ and $z$ are connected and hence $G^{\prime} - \left\{ { y } \right\}$ is still a connected dominating set as shown in Fig. 6.

Fig. 6

After applying rule R2 and R3

3.3.3 Route repair phase

The 2-hop route repair phase deals with the path damage problem. When the transmission gets interrupted or when a particular CDS node receives the ACK about the failed transmission, the 2-hop repair mechanism is conducted to repair the route. Before initiating the route repair, the nodes check for the below conditions to be satisfied.

• 1. Ensure that the current route is valid and is not under repair.

• 2. Next 2-hop neighbor must be valid or the next 1-hop neighbor node must be a CDS node connecting ‘N’ nodes.

• 3. Next-hop node is not the destination node.

The overall working of the 2-hop route repair is as depicted in Fig. 7 which is based on the nodes obtained from the previous stage (i.e.) final CDS nodes after pruning process. The Fig. 7a represents the connection between the source and destination and are reached through the CDS nodes.

Fig. 7

Overall working of 2-hop route repair

When a link between node 27 and node 23 breaks or node 23 moves as in Fig. 7b, the CDS node 16 is capable of detecting the disconnection and finally it initiates the 2-hop repair mechanism.

The CDS node 16 searches the 2-hop neighbor table to identify the next 2-hop node 25 and sends an ‘RPRQ’ to node 16 by node 25 as in Fig. 7c. Then, after receiving the ‘RPRQ’, node 16 sends an ‘RPRP’ to the previous CDS node 10 by node 27. A new shorter route is updated via the CDS nodes and finally the CDS node 1 broadcasts an ‘RTCH’ to notify the source node 3 about the route change. Therefore, the 2-hop route repair is established as shown in Fig. 7d.

The nodes in the CDS are capable of eliminating the route repair problem and the broadcast storm problem. The packet is broadcasted by the CDS nodes alone and the packet is received by the non-CDS nodes, which results in the reduction of control packets and the congestion of the network are reduced. When a node joins or leaves the network, the following four scenarios are considered.

• Case 1: The node that leaves the network $G$ is a non-CDS node or dominate node.

• Case 2: The node that leaves the network $G$ is a CDS node or dominator node.

• Case 3: The node that joins the network $G$ is a non-CDS node or dominate node.

• Case 4: The node that joins the network is a CDS node or dominator node.

In all the four cases, an alternative CDS within the new network will be computed when necessary. In case 1, the pruning phase is carried out to identify the redundant black nodes (i.e., former black node is considered as redundant) and are marked as gray nodes which helps to reduce the size of the CDS. In the case 2, a gray node from the CDS neighbor set is selected such that the selected node does not have a black neighbor. Finally, from the neighbor set of the selected gray nodes, a particular gray node is selected and marked as black and hence a new CDS is formed. In both the cases 3 and 4, the new node is initially marked as white (helps to identify as new node by other nodes in the network). The new node then broadcast its $E\left( x \right)$, $V\left( x \right)$, $D\left( x \right)$ and $ID\left( x \right)$ to gather information about the 1-hop neighbors and inturn to obtain its 2-hop neighbors. There is no need for CDS formation when the new node has a black node as its neighbor. Then it marks itself gray and CDS size remains unchanged. When the new node does not have a black neighbor, a new CDS is formed by obtaining a black neighbor from its neighbor set and finally marks that node as black.

4 Performance evaluation

The proposed algorithm MPR-2R is simulated using NS-2.34 and the simulation environment has ‘$n$’ number of nodes to form a network, which are placed randomly in 1000 m² region. In the analysis, the numbers of nodes are assigned from 50 to 300 nodes with a uniform transmission range of 250 m and the initial energy of the node ranges from 1 to 15 J. Each and every node in the network moves randomly with minimum and maximum mobility of 5–100 m/s, respectively to assess the performance of the MPR-2R algorithm. The proposed algorithm is compared with the existing algorithms as in Wu-CDS (Wu et al. 2006), EAS-CDS (Ramalakshmi and Radhakrishnan 2012) and MinV-CDS (Meghanathan 2010). The simulation parameters used are listed in Table 2 and the performance analysis includes Packet Delivery Ratio (PDR), CDS size, CDS lifetime and Control Overhead (CO) based on the route maintenance and repair, the MPR-2R is compared with AODV (Perkins and Royer 1999), AOMDV (Badis et al. 2004), MPRDV (Allard et al. 2003) and MMDV (Mtibaa and Kamoun 2006).

Table 2 Simulation parameter

4.1 Packet delivery ratio (PDR)

The packet delivery ratio is calculated as the total CBR packets received by all the target/destination nodes to the entire count of CBR packets that are transmitted from all source nodes. The Fig. 8 represents that, in case of AODV and AOMDV where the concept of MPR is not integrated with the protocol, the packet delivery ratio decreases with increase in CBR sessions because of the network congestion caused by the repeated RREQ. The proposed protocol MPR-2R proves better when compared with other MPR based protocol such as MPRDV and MMDV, as it has a high packet delivery ratio. Even though the CBR session count increases, it is capable of repairing all the current routes using the 2-hop repair mechanism. For a better analysis, the node mobility is varied from 5 m/s to the maximum mobility of 100 m/s as shown in the Fig. 9.

Fig. 8

Packet delivery ratio vs. CBR sessions

Fig. 9

Packet delivery ratio vs. node mobility

Initially, when the node mobility is 5 m/s (minimum mobility), all the discussed protocols yield similar PDR. Further, when the mobility of the node increases, the evidence of applying the MPR concept is noticeable as it reduces the amount of control packets to repair the damaged route. The 2-hop neighbor table in MPR-2R helps to fix the damaged routes even though the original nodes in the particular route are exhausted of energy or out of the communication range of the node to be repaired.

4.2 Control overhead (CO)

The term control overhead is defined by the total number of control packets, as it represents the excess load in the network. It is represented by the total bandwidth consumed by the control packets. For the best analysis, the bandwidth consumed by the total control packets is considered for transmission rather than considering broadcast time. The Fig. 10 depicts the control overhead for different CBR sessions, where AODV and AOMDV consumes more bandwidth as it spends most of the packets in building main routes and alternative routes. It is clear from the figure that, the protocol integrated with MPR mechanism has a reduced amount of CO. But when the CBR session count increases, there is a large deviation noted between the MPR based protocols and other on-demand routing protocols. As the proposed MPR-2R involves only the CDS nodes in the damaged route repair process, only few control packets are used for the broadcast mechanism and therefore less control overhead is achieved. More RREQ packets are used in MPRV and MMDV to rebuild new routes or repair old routes.

Fig. 10

Control overhead vs. CBR sessions

The Figs. 11 and 12 displays the control overhead at varying node mobility combined with bandwidth 54 Mbps respectively. In this condition, AOMDV needs more RERR packets as it faces the congestion problem and hence the overhead difference is slightly reduced between AOMDV and AODV. Moreover, when the node mobility is increased, there will be frequent route damage/broken routes. The MMDV protocol is capable of reducing the congestion in the network, whereas in MPRDV, the chances of route reconstruction with fixed cost is likely to be more. Therefore, the proposed MPR-2R seems to be a little closer to MPRDV, as it consumes more bandwidth to repair the damage routes but with reduced control overhead.

Fig. 11

Control overhead vs. node mobility

Fig. 12

Control overhead vs. maximum mobility with 54 MBPS

4.3 CDS size

The average number of nodes that act as broadcast relay nodes in the connected dominating set is represented as CDS size. The average CDS size with minimum and maximum velocity is represented in the Figs. 13 and 14, respectively. The average number of CDS generated by MPR-2R is greater than Wu-CDS; as it considers only the degree of the node for node selection process, but lesser than EAS-CDS and MinV-CDS; as it select nodes based on the energy and minimum velocity. In MPR-2R, the nodes are selected based on the MPR mechanism and are pruned by considering the energy level, velocity, node degree and node ID of the nodes.

Fig. 13

CDS size based on minimum velocity (V(x) = 5 m/s)

Fig. 14

CDS size based on maximum velocity (V(x) = 100 m/s)

4.4 Stability of the CDS nodes

The nodes stability is low when the velocity is comparatively high. Hence, the CDS stability may be represented by the first death of the CDS node/dominator node (i.e., the energy level of the CDS node is dropped to zero). The Figs. 15 and 16 depicts the CDS lifetime with minimum and maximum velocity, respectively. In MinV-CDS, the CDS stability are greatly reduced when there is maximum velocity because only the slow moving nodes are considered. In Wu-CDS, considering the node degree alone does not have a greater impact in maintaining node stability. The simulation has been carried for 800 nodes to ensure stability and as the network grows, the number of CDS nodes increases simultaneously. This results in the similar functionality even when the network is scalable. The proposed work outperforms in terms of network lifetime, as the CDS nodes generated by the MPR-2R algorithm have high energy level, node degree and velocity. But when compared with the different velocity ranges, the duration of the node stability is reduced.

Fig. 15

CDS lifetime at minimum velocity (V(x) = 5 m/s)

Fig. 16

CDS lifetime at maximum velocity (V(x) = 100 m/s)

5 Conclusion

The proposed MPR-2R protocol achieves the goal of multipoint relaying based on the MPR broadcast and 2-hop route repair mechanism and route maintenance. The protocol reduces the bandwidth consumption and the number of broadcast packets efficiently. It handles 2-hop route repair mechanism to perform local route repairs effectively caused by the mobility of the node with reduced control packets. In addition, three pruning rules have been proposed to reduce the size of the connected dominating set and to enhance the network lifetime with the velocity, residual energy, node ID and node degree. The simulation results prove that the proposed protocol performs best in terms of packet delivery ratio, control overhead, size of the CDS and CDS node stability increases the overall network lifetime by 30%. Further the future plans include scheduling among the CDS node to improve the stability of the node rather than the MPR mechanism.