A New Routing Protocol with High Energy Efficiency and Reliability for Data Delivery in Mobile Ad Hoc Networks

Abstract

The proliferation of mobile devices has changed the trends by which people access and share contents in the communication world, leading to migration from the wired to wireless networks with high expectations of ubiquitous connectivity. These trends have motivated researchers to have interests in the future advanced mobile communications. In this paper, we concentrate on one of the most promising types of network, that is, mobile ad hoc network (MANET). Due to the highly dynamic network topology and resource shortage of MANET and the limited energy of communicating nodes, the communication route among nodes may fail frequently. To increase the applicability and sustainability of MANET in the future communication environment, we propose here a new routing protocol that constructs a stable, a reliable, and the shortest route having nodes with the minimum level of remaining energy to increase the operational lifetime of MANET. It also introduces a recovery scheme that reduces the network control overhead significantly to increase the reliability of the network. The effectiveness and robustness of our protocol and the corresponding data delivery mechanism make an ideal solution that can go a long way toward effective data dissemination in the future network.

1. Introduction

The mobile ad hoc network (MANET) is an infrastructureless wireless network that employs the adaptive learning of mobile nodes. Due to the dynamic network topology, time-varying wireless channels, and the shortage of power in mobile nodes, the MANET routes are often unstable, causing routes to break frequently. Therefore, providing reliable and timely data delivery with the minimum resource utilization is a challenging problem in MANETs.

AODV [1] is a reactive routing protocol with the resource constraints and dynamic configuration of MANET. It works on demand basis, which means a route is discovered when needed and routes are maintained as long as they are needed. The construction of routes uses network wide redundant control message flooding or retransmission of route request, route reply, or topology sharing (HELLO) messages which may cause considerable energy drain. Huge time and effort are wasted due to more complicated route failures of AODV.

Energy-efficient probabilistic routing (EEPR) [2] algorithm adopts energy-efficient probabilistic metric by using the residual energy of each node and ETX [3] metric value in the context of AODV protocol. It is an extension to AODV that tries to discover a route with the maximum energy to ensure higher lifetime, good link quality, and balanced energy consumption of communicating nodes. In EEPR, when a source node wants to transfer data to a destination node, it broadcasts a route request message to its one-hop neighbor nodes. An intermediate neighbor node that is not the destination node or that has no valid route information to the destination node calculates the forwarding probability using its residual energy and ETX value. If the estimated probability value is high enough, then the intermediate node rebroadcasts the route request message and makes a backward route entry to the previous upstream node. In this scheme, the destination node receives the route request message from the upstream node and replies back to the source node. The source node receives route reply messages and selects a route for data transfer.

In this paper, we propose a new routing protocol named Energy-Aware and Error Resilient (EAER) routing protocol for MANETs. EAER tries to construct a route using the neighbor nodes having the minimum level of packet forwarding capability. This capability is measured by the proposed EAER routing metric. The EAER routing metric is a combination of nodes remaining energy and successful packet transfer capability. The basic assumption is that even if a node's current energy is below a certain level, its probable lifetime in the network is reduced or the node with poor link quality decreases its network lifetime by wasting the residual energy and does not participate in the further communication process. Our protocol will allow a route to be retained locally during the route failure. Hence, the EAER protocol constructs the reliable shortest route that will ensure the balanced consumption of battery power by substantially reducing the amount of control messages of the mobile node in the ad hoc network environment.

The rest of the paper is organized as follows. Section 2 discusses the state-of-the-art protocols for MANETs, and Section 3 presents the proposed EAER routing protocol. Simulation results and analysis are given in Section 4. Finally, we conclude this paper in Section 5.

2. Related Works

AODV-BR [4] is an improvement to the basic AODV without changing the route discovery approach. Every node overhears route reply messages from neighbors and creates its own alternate routes towards the destination of the respective route reply message. When any node on an active route detects a route failure, it broadcasts data packet towards its one-hop intermediate neighbor nodes. Intermediate nodes that have preestablished a backup route transmit data towards the destination. AODV-BR focuses on reliability, but it makes stale routes. It may transmit duplicate packets and may increase end-to-end delay and may dissipate high energy. AODV-ABR [5] follows a similar approach of AODV-BR. For reliability and efficiency, it introduces a three-way handshaking process to construct a recovered route from multiple backup routes after detecting a route failure by the immediate upstream node. IBR-AODV [6] introduces an improvement to the AODV-ABR by introducing the back-off timer concepts for avoiding collisions in the time of local recovery handshaking process. IBR-AODV tries to minimize collisions and control message flooding, but it may suffer from the huge energy dissipation problem for the preemptive backup routing concept.

Link stability based routing [7] uses a stability metric to construct a new route. Link stability is calculated from nodes’ mobility, data delivery efficiency, and residual energy. $R^{\mathrm{2}}$ -routing [7] directs an intermediate node having the minimum level of the metric value to forward a RREQ message. Thus it constructs a route having nodes with the minimum required stability. In [8], the intermediate node receives several route request messages from its neighbor node and forwards only the route message that has the highest robust route index value. Robust route index is measured as a weighted sum of traversed hop length, the speed between corresponding nodes and delays. These protocols are more effective in highly mobile scenarios, but nodes should be aware enough of its current position and also need to retrieve parametric value from different layers, which increases the protocol complexity. Path encounter rate (PER) [9] metric based routing protocol tries to estimate the path encounter rate from the sum of square average encounter rate (node encounter number of new nodes per unit time) values of all nodes along the path and selects a route at the destination node, having the minimum encounter rate values. PER constructs the route using nodes located in low density regions or having less mobility. This routing model tends to pass all the traffic loads to pass through a specific region, which increases the collision probability and creates a vulnerable network. Other contact based and link duration metrics [10–12] show similar shortcomings shown by encounter rate based routing protocol.

Local energy-aware routing [13] indicates that intermediate nodes forward the route request message only when their energy is above a certain threshold value. Otherwise, it drops the message. It overcomes the overhead of periodic exchanges, but, in case of failure, it suffers from more end-to-end delay for reconstructing a route. Other energy-aware routing protocols such as EAODV [14], AODV-PE [15], and energy-efficient reliable routing [16] construct a route having the maximum energy for providing higher operational lifetime of the network. However, the maximum energy route may contain an intermediate node having limited energy. That increases the probability of route failure immediately. These protocols do not provide any robust recovery scheme since it significantly reduces the throughput and data delivery ratio. Energy-efficient probabilistic routing algorithm [2, 17, 18] reduces the RREQ messages propagation using their proposed metric. They do not consider link quality in terms of reliability of the route, which drastically reduces the network lifetime and data transfer efficiency by wasting the residual energy of the nodes having poor link quality. Even though EEPR [2] was proposed to significantly reduce the RREQ message propagation by choosing a metric that combines the node's ETX value with the node's residual energy valueour simulation results show that the combined metric [2, 17, 18] has almost no impact on the nodes’ link quality.

3. The Proposed EAER Routing Protocol

We consider a MANET having a large number of nodes, where each node moves randomly. Nodes use the EAER routing protocol as the network layer protocol. We consider the IEEE 802.11 DCF as the MAC layer protocol. We also consider that each node broadcasts the HELLO massage that indicates its liveliness towards its neighbor node. In case of route failure, a node of the ongoing route that can be used as a possible next node for continued communication to recover the route is called a candidate node. For example, node S in Figure 4 is the source node, node D in Figure 4 is the destination node, and node J in Figure 6 is a candidate node. The following subsections provide an overview and the design details of the proposed EAER routing protocol.

3.1. Overview

An RREQ message is broadcast for constructing a new route. Intermediate nodes that have the minimum level of remaining energy may only rebroadcast the RREQ message. Our proposed protocol reconstructs the route locally from the intermediate node when a route failure occurs.

3.2. Design Preliminaries

The RREQ message structure of AODV [1] is extended to hold the address of the candidate node and a notification flag, and the RREP message structure of AODV [1] is also changed to hold the address of the candidate node as presented in Tables 1 and 2, respectively. The notification flag is set to 1 to notify the one-hop upstream node for reducing the data transmission rate and also buffering the transmitted data towards the failure route. The routing table of AODV [1] is extended in a column to hold the address of the candidate node.

Table 1

RREQ message structure.

Type	R	A	Notify flag	Reserved	Prefix Sz	Hop count
Destination address
Destination sequence number
Originator address
Lifetime
Candidate address

Table 2

RREP message structure.

Type	J	R	G	U	D	Reserved	Hop count
Destination address
Destination sequence number
Originator address
Originator sequence number
Candidate address

The routing table is as follows:

•  

destination address;

 

destination sequence number;

 

sequence number flag;

 

routing flag;

 

network interface;

 

hop count;

 

next hop;

 

candidate address;

 

lifetime.

3.3. Design of EAER Metric

Given a network presented in the form of graph $G=(V,E)$ , a distinct identifier address (i) is assigned to each node i in G. Let $E_{v,\max }$ and $E_v$ denote the initial energy and remaining energy of node v. Node v requires the energy $E_{p,v}$ to transmit a data packet to its neighbor node u given by

$$\begin{array}{cc}& E_{p,v}=E_{rx\left(p,v-\mathrm{1}\right)}+E_{tx\left(p,v\right)},\end{array}$$

(1)

where $E_{rx(p,v-\mathrm{1})}$ and $E_{tx(p,v)}$ denote, respectively, the amount of energy required to receive the packet from the upstream node $v-\mathrm{1}$ and to transmit the packet to the downstream node u. Reliability is an indication of packet forwarding ability of a node in MANET. This value is the ratio of the packet actually received from the neighbor node to the packet actually sent to the neighbor node. Here, we consider the sum of control packets (excluding HELLO packets) and data packets sent to the downstream node and received from the downstream node. Let node v and node u be two communicating nodes. Node v sends $S_{vu}$ number of packets to its one-hop downstream neighbor node u and receives $R_{uv}$ number of packets from its one-hop downstream node u at any time interval t. Then, the reliability $R_{(v,t)}$ between node v and node u is measured by

$$\begin{array}{cc}& R_{\left(v,t\right)}=\frac{R_{uv}}{S_{vu}}.\end{array}$$

(2)

Node v also sends the total of $S_i$ number of packets to its other neighbor nodes i and receives the total of $R_i$ number of packets from other neighbor nodes i at any time interval t. Then, the exponential weighted reliability of node v is measured by

$$\begin{array}{cc}& R_{w\left(v,t\right)}=\left(\mathrm{1}-\alpha \right)R_{\left(v,t\right)}+\alpha \underset{\mathrm{1}\le j\le i,j\ne u}{\max }\frac{R_j}{S_j},\end{array}$$

(3)

where α is a weight factor and meets the condition $\mathrm{0}\le \alpha \le \mathrm{1}$ . Then, the estimated EAER metric $\text{EAE}{\text{R}}_v$ of node v is determined by

$$\begin{array}{ll}{\text{EAER}}_v& ={\text{EAER}}_{v,\min }+\left(\mathrm{1}-\text{EAE}{\text{R}}_{v\text{,min}}\right)\\ & \ast \frac{E_v\ast R_{\left(v,t\right)}}{E_{v,\max }\ast R_{w\left(v,t\right)}}\ast \mathrm{1}\\ & +{\left(\frac{\left(R_{\left(v,t\right)}-R_{w\left(v,t\right)}\right)\ast E_{p,v}}{\left(\mathrm{1}-R_{w\left(v,t\right)}{E}_{p,v}\right)}\right)}^{\mathrm{1}/\beta },\end{array}$$

(4)

where $\text{EAE}{\text{R}}_{v\text{,min}}$ and β are predefined minimum $\text{EAE}{\text{R}}_v$ value and the weighted factor for the variation of the EAER metric value, respectively. Figure 1 shows the EAER value as a function of the reliability value and the residual energy value when $E_{v,\max }=100$ Joules, $\beta =1$ , $E_{p,v}=0.02$ Joules, and ${\text{EAER}}_{v,\min }=0.25$ . We also define EAER scale shown in Figure 2 based on the estimated EAER metric value to show the interest packet forwarding ability to the respective neighbor node.

Figure 1

$\text{EAE}{\text{R}}_v$ values via reliability and residual energy.

Figure 2

EAER scale.

EAER routing metric points out that a node can be selected for data transfer if both of the following conditions are satisfied:

• (1)

The node has enough energy to receive and forward data from other nodes.

(2)

The node is able (in terms of reliability) to transmit data to other neighbor nodes.

Combined EAER routing metric guarantees that a node is able to send or transfer data to neighbor node without any failure. Indeed, the following constraint has to be fulfilled:

$$\begin{array}{l}\text{EAE}{\text{R}}_i\ge {\text{EAER}}_{\left(i,\min \right)}\\ \forall i\in V,\hspace{0.17em}\hspace{0.17em}i\ne \text{dataSource},\hspace{0.17em}\hspace{0.17em}i\ne \text{dataDestination}.\end{array}$$

(5)

3.4. The Proposed EAER's Operations

3.4.1. Route Construction

Similar to AODV, when a source node wants to transmit data to a destination node and the source node does not have any known path information to the destination, it broadcasts an RREQ message by setting to null the address of the candidate node towards its one-hop neighbor node. A node receives the RREQ message (see also Figure 3), checks its duplicity, and takes the action similar to AODV. Then, it searches its routing table entry for a routing path to the destination, where its flag value is equal to the active state mentioned in Table 3. If it has routing information, then it sends back an RREP message or if it finds a path with a flag value other than the active state, then it simply discards the RREQ message. If the node does not discover any routing information, then it estimates its own EAER metric value using (4). If the estimated value is greater than the predefined threshold (the threshold is a user defined design parameter that aims to control the dynamicity of the EAER routing protocol), the node rebroadcasts the RREQ message. When the destination node receives the RREQ message, it replies back with the RREP message without setting the notification flag towards the source node. When an intermediate node receives the RREP message, it updates its routing table and sets the candidate node address extracted from the RREP message. The address of the candidate node is filled up by the address of the next hop node before the RREP message is forwarded to the next intermediate node until it reaches the source node. For example, in Figure 4, a source node S requires a route to any destination D; it broadcasts the route request (RREQ) message in the network. Node A receives the RREQ packet and rebroadcasts the message towards the destination node. Nodes C and B are the neighborhood nodes of node A and receive the RREQ message, and only node B rebroadcasts the RREQ message because of the lower energy level of node C. In a similar fashion, other nodes rebroadcast the RREQ message. When the RREQ message is received by the destination node D, it sends back a route reply (RREP) message towards the source node S. Intermediate nodes receive the RREP message (see also Figure 5) and update their routing table corresponding to the destination node D as shown in Figure 4. Thus, the route S-A-B-E-F-G-J-K-D is established and then node S starts sending data to the destination node D using this route.

Table 3

Routing flag.

State	Value
Inactive	0
Active	1
Repairable	2

Figure 3

Route request messages handling.

Figure 4

Route construction in MANET.

Figure 5

Route reply messages handling.

Figure 6

Local route recovery in MANET.

3.4.2. Route Maintenance

Because of the high mobility of nodes, if any link failure occurs or the upstream node does not receive HELLO message for a fixed time interval, then the upstream nodes assume that the link is broken. For example, as shown in Figure 6, node F detects that the link between node F and node G is broken. When a link failure is detected, the corresponding node initiates two actions.

Store Data and Send a Notification towards the Previous Upstream Node. After detecting the route failure, an intermediate node stores data packets of the eroded route in its local buffer for later transmission until the buffer is filled to a fixed level (we assume that the maximum occupancy level of a buffer is 70% of a node's total buffer size). An RREP message for the same destination is broadcast towards its one-hop neighbor by setting the notification flag to 1 when the buffer crosses the predefined limit. The previous upstream node receives this RREP message, reduces its respective data transmission rate, and starts to store data in its local buffer. In the mean time, the receiving node sets the routing flag of the respected route to the repairable state. Similar actions are taken inside the other upstream nodes until the route is reconstructed or the RREP message reaches to the source node. If the source node receives this kind of RREP message or RERR message, a new route is discovered towards the destination. For example, in Figure 6, node F stores data in its local buffer for the destination node D. The buffer of node F has been occupied at its maximum level, and then it notifies its previous upstream node E.

Recover Route Failure. The node that detects the link failure broadcasts an RREQ message by inserting the same destination address and the candidate node address by limiting the TTL to 2. An intermediate node receives the RREQ message and operates similarly to route construction process. The current source node receives the RREP message and forwards it to another one-hop neighbor node to update the address of the candidate node of the previous upstream node. Intermediate nodes of an active route that have the routing information with a routing flag value set to the repairable state mentioned in Table 3 measure its own buffered data. The routing flag of the routing table is set to the active state when the estimated buffer occupancy level goes below the already predefined buffer level. For example, in Figure 6, node F broadcasts an RREQ message which is destined to node D to the candidate node J to repair the broken route between node F and node G. H and I are neighborhood nodes of F, receive the RREQ message, and check their respective routing table for a route towards the candidate node J. Nodes H and I cannot discover any route towards the destination node D since they rebroadcast the RREQ message due to their higher EAER metric value than the threshold value. In advance node J receives the RREQ message from node O and replies back to the upstream source node F. Thus, the local route F-I-O-J is found towards the destination node D, and node F starts sending data.

4. Performance Evaluations

The performance of our proposed EAER routing protocol has been evaluated and compared with AODV [1], AODV-PE [15], PER [9], and EEPR [2] using NS-2.34 [19].

4.1. Simulation Environment

The network area of 800 m × 800 m has been considered in our simulation, where 100 nodes are randomly deployed to move freely with the random way point movement model in the network environment and out of which 10 source nodes generate data packets at constant bit rate (CBR). EAER can handle also the diverse traffic demands of different applications such as variable bit rate (VBR). As the network traffic becomes heavy, EAER selects a route having good link quality and maintains its data transfer consistency using the data buffering capability of the intermediate nodes. The source-destination pairs are randomly chosen, and they exchange data packets over UDP connections. IEEE 802.11 DCF has been used as the underlying medium access control protocol. Detailed simulation parameters are specified in Table 4.

Table 4

Simulation parameters.

Parameter	Value
Simulation time	500 sec
Pause time	2 sec
Data packet size	512 bytes
Bandwidth	4 Mbps
Packet generation rate	4 packets/sec
Radio propagation model	Two-ray ground
Antenna type	Omniantenna
Initial node energy	8 Joules (J)
Transmitted power	0.03652 W
EAER matric threshold	0.25%

4.2. Simulation Results

In this section, the most focusing, crucial, and common benchmark metrics like packet delivery ratio, end-to-end packet delivery delay, and energy consumption are presented to show the overall performance of the EAER routing protocol. We compare the performances of different routing protocols in terms of varying node mobility speeds while other required parameters are being kept constant. The results obtained are averaged over 20 simulation runs. Therefore, the graphs represent the stable behaviors of the protocols. We measured the performance of AODV, AODV-PE, PER, EEPR, and EAER routing protocols for varying mobility speeds, ranging from 0 m/s to 20 m/s. The simulation results for the aforementioned performance metrics are shown in Figure 7.

Figure 7

Performance comparisons for different node mobility speeds.

(a) Packet Delivery Ratio. This is much affected by increasing mobility speeds in all the protocols, as shown in Figure 7(a). Mobility causes frequent topology changes to reduce the link lifetime and further increases the link failure rates. Packets may be dropped due to the frequent link failure in all protocols. Our proposed EAER protocol outperforms all the other routing protocols and achieves better performance because of choosing the shortest hop route, on-demand local recovery mechanism, and data buffering capability, avoiding the overhead for propagating control packets, which significantly reduces the packet dropping rate over a long period of time.

(b) End-to-End Average Packet Delivery Delay. In EAER, the end-to-end average packet delivery delay is also lower than that of other protocols, as shown in Figure 7(b), since it selects a path with the shortest hop counts and higher lifetime. We observe that the EAER faces a lower packet delivery delay than that of other protocols as shown in Figure 7(b), when the mobility speed of the nodes is higher and is set to 20 m/s.

(c) Average Energy Consumption per Packet. Average energy consumption per packet is shown in Figure 7(c) where the EAER routing protocol avoids selecting nodes with too lower energy level and prevents the nodes from the premature deaths. Therefore, in the EAER even for the higher number of route failures and data packet retransmission scenarios of the high mobility network environment, it consumes less energy than other protocols and maintains the network in a more balanced way.

(d) Normalized Routing Overhead. The normalized routing overhead in all routing protocols increases when the mobility increases. Higher mobility implies higher route failures, which causes more network control packets (i.e., error packet, request packet) flooding. Note that EAER reduces the request message flooding by selecting an intermediate node having minimum boundary of energy level, since all neighborhood nodes can not rebroadcast RREQ message. As shown in Figure 7(d), EAER reduces the normalized routing overhead in a greater extent than the other routing protocols that are evaluated.

(e) Variance of Node Residual Energy. This parameter is considered to evaluate the fairness in the node usage. The higher variance is the unfairness in the node usage and in the energy consumption among nodes. The result for the variance of node residual energy of all the nodes is shown in Figure 7(e). It is interesting to see how AODV, AODV-PE, and PER are the worst in terms of fairness in the node usage. EEPR shows better result than others because of its energy-aware metric and a little consideration of route quality metric. EAER shows outstanding and significant improvement for traffic load balancing because of its judicious choice of EAER routing metric.

(f) Route Construction Probability. It shows the routing success probability due to the success of route construction between source and destination pair. EEPR and EAER dynamically control the number of RREQ packets flooding by using their forwarding probability metric and EAER metric, respectively. So, there is a chance that intermediate neighbor nodes do not forward the RREQ packets in the worst case scenarios which may decrease the route construction probability of EEPR and EAER routing protocol. The route construction probability of AODV, AODV-PE, PER, EEPR, and EAER routing protocol is shown in Figure 7(f). The route construction probability of EAER is little less than other protocols by 2% which may be overpassed by the other dramatic improvements.

5. Conclusion

In this paper, we proposed a reliable and energy-efficient routing protocol for MANETs and also proposed a novel local route recovery scheme for consistent data delivery. EAER finds the most optimum route in terms of the number of hop counts, reliability, and energy efficiency. Simulation results showed that EAER performs better than other representative routing protocols in terms of packet delivery ratio, end-to-end delay, energy consumption, routing overhead, energy change rate, and route construction probability. We also found out that EAER improves the network resource efficiency and other routing performances.