Energy Conservation for Ad Hoc On-Demand Distance Vector Multipath Routing Protocol

Published Online May 2014 in MECS

An ad hoc network is characterized by frequent changes in the network topology, the limitation on the bandwidth availability, and the limitation of the electrical power available in the network nodes. The topology of ad hoc networks frequently changes because the nodes in an ad hoc network are able to move collectively or individually in an unpredictable manner. These characteristics make the routing complex in this type of networks.

Many papers have studied routing in ad hoc networks [1-4]. Although the protocols suggested in these papers show certain relevant characteristics, they present some limits, especially when a strong mobility of the nodes or a heavy load of the network is considered, such as loop-free routing, unnecessary control and update traffic, loss of trace of nodes, etc.

The interest in the problem of improving ad hoc routing has given rise to several routing mechanisms. Among these, the multipath routing mechanism is used by several protocols to avoid useless delays during link failures. These failures may be due to the energy depletion of node batteries. A number of researchers have focused on the design of communication protocols that preserve energy so as to assure network service for as long as possible [5-9]. The concept of the multipath routing is to give to the source node the choice, at a given moment, between multiple paths to reach a certain destination. The multiple paths can be used alternatively or in a concurrent way in accordance with some selected criteria.

In this paper we propose a novel on-demand routing protocol for ad hoc networks based on the multipath principle, in order to use the energy of nodes efficiently (extend network life), control the overhead traffic (routing packets), minimize the end-to-end delay of the mobile ad hoc networks (link failures from node mobility and node failures from node power exhaustion will not increase end-to-end delay), and minimize the path energy consumption.

Our protocol is designed primarily for battery-limited nodes, where link failures and path breaks occur frequently. The main idea of our protocol is to discover multiple paths between a source and a destination in a mobile ad hoc network, by exploiting the minimum residual energy of nodes to prevent one or more critical nodes from depleting their energy supplies and dropping out of the network. After the path discovery process, multiple paths may have minimum values of residual energy which are almost the same or similar. A new factor which can be combined with this minimum value is the average residual energy of node batteries along the paths. This combination favours the minimum residual energy because it has a strong impact on breaking of links.

The remainder of the paper is organized as follows. Section 2 provides a review of related works on multipath routing in wireless ad hoc networks. Section 3 gives the design details of our protocol AODVME+. Section 4 provides simulation results for performance evaluation, and Section 5 concludes the paper.

• II.    Related work

• 2.1    Multipath routing

• 2.1.1    Ad hoc On-demand Multipath Distance Vector routing (AOMDV)

In this section, we will first present two typical multiple path routing protocols for ad hoc networks and energy aware routing protocols.

Multipath routing in ad hoc networks is a promising technique which allows the problems of instability, limited bandwidth, conservation of energy, and so on to be solved. The use of multiple paths decreases the effect of the network link failures. This contributes considerably to improving the network performance. Nevertheless multipath routing remains a more difficult technique than simple routing. Its difficulty lies in searching for the (best) multiple paths.

The multipath approach makes it possible to compute multiple paths in a distributed and independent way. It is based on the principle of disjunction of the multiple paths between the same source–destination pair (the disjunction can be partial [10]). The purpose of this disjunction principle is to ensure the independence of paths; that is, if a link of one of the paths fails, this failure will not affect the other paths. The computation of disjoint paths has been the objective of numerous studies [11-13].

Let us note that there are two types of path disjunction: for the links or for the nodes. The first type, link-disjoint paths, does not share common links but a node can participate in several paths; the failure of a shared node (for instance, battery depletion) affects all paths which share this node. The second type of path disjunction, node-disjoint paths, has no node (and no link) in common, and therefore depletion of a node affects only the path containing this node. In our protocol we chose this type of disjunction to ensure the complete independence of the paths. Most of the proposed multipath protocols, like AOMDV [11], AODVM [14] and SMR [15], are based on the single-path version (AODV [16] or DSR [17]). These protocols are reactive routing protocols. In fact, reactive multipath routing protocols improve network performance (load balancing,  delay and  energy efficiency). Several studies [18,19] have shown that AODV performs better than DSR using various performance metrics. The simulation results confirm that AODV protocol provides better end-end delay values and better connectivity with less data loss and good throughput. So we selected this protocol instead of other reactive protocols (such as DSR [17]) as the reference for performance evaluation of our protocol.

AOMDV [11] and AODVM [14] are two multipath protocols based on Ad hoc On-demand Distance Vector (AODV) [16], one of the most popular on-demand wireless routing protocols. We describe these two protocols below.

Ad hoc On-demand Multipath Distance Vector routing (AOMDV) is a multipath routing protocol based on an exchange of a vector of node distances between nodes, producing link-disjoint paths. The multiple paths are calculated in a distributed manner and independently in each node [11]. AOMDV uses the information in RREQ (Route REQuest) messages to detect duplicate RREQs. AOMDV broadcasts the RREQ messages in the same manner and on the same path as AODV [16]: only the first RREQ message received is forwarded further. Instead of discarding duplicate RREQ messages, AOMDV consults the list of nodes which forms the (alternate) path contained in this message; in order to use the list to assure loop-freedom of paths, the node memorizes the paths with disjoined links. For each newly found alternate path, each intermediate node produces a message RREP (Route REPly) and sends it back to the source along the reverse path, if it knows a forward path that has not been used in any previous RREPs for this RREQ. The destination node replies to every RREQ message it receives. AOMDV uses the destination sequence number in the same way as AODV to indicate the freshness of the route, which ensures loop-freedom. Moreover, AOMDV employs the advertised hop count to maintain the multiple paths for the same sequence number. The advertised hop count contains the hop count of the allowed longest path. Once the sequence number changes, the advertised hop count is reset and remains unchanged for this sequence number. A node builds an alternate path for a certain destination node through a neighbour node only if this alternate path has a smaller advertised hop count. It is proved that AOMDV can guarantee loop-free paths because it allows only alternate routes with lower hop counts.

In ad hoc networks, a node failure could be caused by a physical node failure (e.g., physical damage or depletion of the battery) or heavy congestion at the node, which causes packet drop due to buffer overflow. In AOMDV the failure of a node can cause the breaking of multiple paths when this node is shared by them. Thus, Ye et al. [14] have chosen AODV as a candidate protocol and make modifications to it to facilitate the discovery of node-disjoint paths from a source to a destination. AODV is one of the most popular ad hoc routing protocols to facilitate on-demand path discovery and consequently the use of multiple node-disjoint paths. Although there has been prior work on modifying AODV to compute edge-disjoint paths [11], the AODVM protocol is the first modified version of AODV that has the ability to find node-disjoint paths.

• 2.1.2    Ad hoc On-demand Distance Vector routing Multipath (AODVM)

• 2.2    Energy-aware routing protocols

AODVM is a multipath routing protocol whose objective is to find node-disjoint paths [14]. It is an extension of a single-path routing scheme known as AODV [16], and makes it possible to compute multiple loop-free and link-disjoint paths between any source and destination nodes. The propagation of the RREQ (Route REQuest) message follows the same rule as the basic AODV except that the intermediate nodes are not allowed to send route replies back to the source. Each node maintains a table of destinations with the corresponding path costs (hop count). To maintain this table, the source broadcasts RREQ messages. This table is called the

RREQ table in the following. When an RREQ message reaches the destination, an RREP (Route REPly) message is produced and returned to the last node from which the destination received the RREQ message. The RREP message contains a field indicating the identifier of the last node. The RREP message may not follow the same path as the RREQ message. Each intermediate node determines the next node to which the RREP message should be sent. The routing of the RREP message is based on the information recorded in the RREQ table. When an intermediate node receives an RREP message, it looks for a path toward the source (of the RREQ message) in its RREQ table. Then it forwards the RREP message to the next node associated with the destination in the RREQ table. In AODVM, in order to make sure that the same node does not take part in the various paths of a multiple path (and thus to assure the node-disjoint property of multiple paths), when a node detects the transmission by one of its neighbours of an RREP message toward a given destination, the node removes the entry corresponding to this neighbour from its RREQ table. If an intermediate node receives an RREP message and does not find any entry for a given source (of the RREQ message), it produces an RDER (Road Discovery Error) message and forwards it to the node from which it has received the RREP message. The node which receives the RDER message will try to forward the RREP message to a different neighbour.

However, AODVM does not take into account the battery energy level of nodes: a node can be unable to assure data packet forwarding due to the depletion of its energy.

In ad hoc networks, energy efficiency is very important. Energy-aware routing optimization has been treated in recent years. Indeed, numerous routing algorithms have been published to solve this problem.

In [20], a distributed power control has been designed as a way to improve the energy efficiency of routing algorithms in ad hoc networks. Each node in the network estimates the necessary power to reach its own neighbours, and this estimated power is used for tuning the transmission power (thereby reducing interference and energy consumption). The authors of Minimum Drain Rate (MDR) [21] propose a mechanism that attempts to select the best possible stable route for a given source and destination. If a node has higher residual energy, too much traffic load will be injected through it, which results in an uneven sharp reduction of battery power. In this metric, the cost function considers both the Residual energy of the node and the Drain rate of that node. Maximum Lifetime for a given path is determined by the minimum cost value along that path. Finally, MDR selects the optimal path having the highest maximum lifetime value. The protocol, Life-time Prediction-based Routing (LPR) [22], focusing on the minimization of the variances of the nodes’ remaining energies in the network, is proposed. In this protocol, each node tries to predict the future energy expenditure, but its estimation depends on many factors such as node distances, residual power, hop count, and node mobility.

Recently several Energy Aware On-demand Multipath Routing protocols have been proposed. The Multipath Energy-Efficient Routing Protocol (MEER) [23] prolongs the network lifetime by using a rational power control mechanism, where the route discovery phase in which the source is finding energy-efficient routes is similar to that of SMR [15]. The Lifetime-Aware Multipath Optimized Routing (LAMOR) [24] is based on the lifetime of a node, which is related to its residual energy and current traffic conditions. Max-Min Residual Energy (MMRE) [25] is a multipath routing protocol based on AOMDV [11]. This protocol finds the minimal nodal residual energy of nodes of each path, and then it selects the path with maximal residual energy to forward the data packets. It is designed mainly for ad hoc networks that are highly dynamic with limited battery capacity. Simulation results showed that the proposed MMRE routing protocol performed better than AOMDV in terms of packet delivery fraction, throughput and network lifetime. We will use MMRE as the reference for our performance evaluation because it aims to improve the lifetime of ad hoc networks and it has the same characteristics as our protocol, namely its reactivity, its multipaths and the AODV used as its basic protocol. In [26] the authors proposed a Multipath Routing protocol for Network Lifetime Maximization (MRNLM), a protocol that defines a threshold to optimize the forwarding mechanism. It proposes an energy-cost function and uses the function as the criterion for multiple path selection. During the transmission phase, they use a method called “data transmission in multiple paths one by one” to balance the energy consumption on the multiple paths. Multimedia Dynamic Source Routing (MMDSR) [27] is a multipath routing protocol that is able to self-configure dynamically according to network states. The authors used the cross-layer techniques to improve the end-to-end performance of video-streaming services over networks using the IEEE 802.11e. MMDSR uses an analytical model to estimate the path error probability. This model is used by the routing scheme to estimate the lifetime of paths. In this way, they hope that proper proactive decisions can be taken before the paths are broken. All the above studies solve the problem of energy conservation, but power-saving mechanisms based only on the remaining power cannot be used to establish the best route between source and destination nodes. On one hand, if a node is willing to accept all route requests only because it currently has enough residual battery capacity, too much traffic load may be routed through that node. On the other hand, excessive energy conservation neglects power consumption at individual nodes, which speeds up network partition by draining the batteries of the nodes that are critical in the network topology. Indeed, it reduces network performance. Hence, shared and balanced energy consumption is a remedy for these types of problem. Finally the majority of these protocols have been compared only with the original protocols (AODV, AOMDV, DSR,  SMR...), which do not explicitly consider energy consumption, and thus their performance evaluations are not fair.

• III.    Multipath routing protocol aodvme+

• 3.1    Assumptions and problem definition

The aim of this article is to develop a multipath routing protocol in accordance with the AODV [16] and AODVM [14] protocols. Our resulting protocol, AODVME+ (Ad hoc On-demand Distance Vector Multipath Energy Plus), is a reactive protocol for multipath routing which selects the path with the goal of saving the energy of nodes constituting the paths. AODVME+ uses the same types of messages as AODVM.

In this section, we first define some assumptions and then provide the details of the discovery, selection, and maintenance of multiple paths.

A wireless network is represented by an undirected graph, G = (V, E) , where V is the set of nodes and E is the set of bidirectional links. Let w(u), u е V represent the residual energy at node u .

Let c(u, v), (u, v) е E be the energy required to transmit a packet from node u to node v . We assume that c(u, v) = c(v, u) for all (u, v) е E . Let P i (u 0 , u k ) = u ‘0 , u ‘1 , . . ., u ‘k be the i ^th path in G between the two nodes u₀ = uⁱ₀ and u_k = uⁱ k .

Let emin(Pi(u0, uk)), the minimum residual energy of nodes constituting the path Pi(u0, uk) for a source node u0 to destination node uk, be expressed as emin (Pi(u0,uk )) =min w' (u‘j),with 0 ^ j ^ k }      ^)

The total residual energy of the path P i (u 0 , u k ) , denoted e sum (P i (u 0 , u k )) , is given by:

e _sum ( P _i ( u ₀ ,u _k )) = ∑ w ( u ⁱ _j )

^{j = 0}                     (2)

Let eaverage(Pi(u0, uk)), the average residual energy of a path, be given by:

e average

( P_i ( u₀,u_k )) =

e sum ( P_i ( u₀,u_k )) k + 1

Given a source s, a destination d, and a single packet to be routed, we can define two problem formulations:

• i)    Maximum of the minimum residual energy path problem: find a path P(s,d) with maximum emin(P(s,d)).

• ii)    Maximum of the average residual energy path problem:   find a path P(s,d) with maximum

• 3.2    Paths discovery

eaverage(P(s,d)).

In multipath routing, node disjoint paths are usually preferred because they exploit the available network resources efficiently and are hence the most fault-tolerant.

To allow the discovery of several disjoint paths between a source and a destination, instead of discarding the duplicate RREQ messages (as AODVM does), an intermediate node must proceed in the same way as for the first RREQ message retained. When a node receives a duplicate RREQ message, it still establishes a reverse path towards the source by recording the address of the neighbour from which it received the first copy of the RREQ message.

We modify the format of the RREQ message and the RREP message of the AODVM protocol by adding two new fields:  the min_re_energy field and the sum_re_energy field. When the intermediate node receives an RREQ, it compares its residual energy with the value of the min_re_energy message field; if it is lower, the node replaces the value min_re_energy with its own value and increases the field sum_re_energy by the value of its residual energy. This treatment must take into account the sequence number in order to ensure the freshness of paths [14]. The same process is repeated until the RREQ message reaches its final destination. We propose an algorithm for computing the minimum sum and residual energy of nodes on a path:

Algorithm 1. Process discovery path if (seqnumdi

if (re_energyi < min_re_energydj) then min_re_energydj:=re_energyi;

sum_re_energydj:= sum_re_energydj + re_energyi; route_listdi:= NULL;

insert (source_id, seqnumsi ,lasthop_id, j,hopcountj+1,sum_re_energydj, min_re_energydj, Expiration Timer) into route_listdi;

endif elseif (seqnumdi=seqnumdj) then if (re_energyi < min_re_energydj) then min_re_energydj:=re_energyi;

sum_re_energydj:= sum_re_energydj + re_energyi;

insert (source_id, seqnumsi ,lasthop_id, j,hopcountj+1,sum_re_energydj, min_re_energydj, Expiration Timer) into route_listdi;

endif endif.

Before the launch of the discovery mechanism, the fields min_re_energy and sum_re_energy are initialized as the residual energy of the node source and zero, respectively.

• 3.3    Multipath sorting and forwarding data packets

After reception of the first RREQ packet, the destination node waits for a certain period of time (RREQ_Wait_Time) before starting the route selection procedure. This waiting period is necessary to receive the RREQ packets, and before it expires, the destination must have answered by sending an RREP message towards each node from which it received an RREQ message. When a node receives its first RREP message, it creates a path entry towards the node from which it received the RREP message and updates the route_list field. Each node maintains a route_list structure, which is described in Fig. 1. We add the two fields, min_re_energy and sum_re_energy to the original AODVM route_list.

The fields min_re_energy and sum_re_energy are updated according to the rules shown in the proposed algorithm.

Destination ID Destination sequence number Route list

Source ID Source sequence number Last hop ID Next hop ID Hop count Min_re_energy Sum_re_energy Expiration timer

Fig.1. Structure of routing table entries for AODVME+

When the node source receives the first RREP message, it waits for a certain amount of time (RREP_Wait_Time) to receive more RREPs before selecting the best path. The choice of the best path between a source node s and destination node d depends on two values, e_min(P_i(s,d)) and e_average(P_i(s,d)), which are defined by (1) and (3). In this approach, the node source calculates ema(P(s,d)) based on emin(Pi(s,d)) and eaverage(Pi(s,d)) using a weighted sum; formally:

e_ma(P_i(s,d))= αe_min(P_i(s,d))+(1-α)e_average (P_i(s,d))

The coefficient α represents the degree of weighting. Our idea is based on sorting all node disjoints paths between a source node s and destination node d by the descending value of e_ma(P(s,d)). The path with the maximum ema(P(s,d)) is chosen to forward the data packets.

• 3.4    Maintenance

The path maintenance process is the same as that used by AODVM. Once a path is selected, it is used by the source to send data. When an intermediate node detects a link failure while trying to forward a packet to the next hop, it sends an RERR (Route ERRor) message to report the breakage of an intermediate link on a route back to the source. When a source node receives an RERR message, it erases the route from its table and looks for an alternate path towards the destination node if available; otherwise, it initiates a path discovery process to resume the data transmission. The alternate path is selected as described in Section 3.3.

• IV.    Performance evaluation of aodvme+

• 4.1    Performance parameters

• 4.2    Performance evaluation

In this section, we present simulation results to demonstrate the efficiency of our proposed protocol. First we present the metrics used for performance evaluation, then we analyze the values of coefficient α to select the most appropriate value for the rest of the simulations, and we evaluate our protocol by comparing it with two protocols in the literature, namely AODVM [14] and

MMRE [25]. This evaluation is accompanied by an analysis and discussion of results.

We evaluate three key performance metrics. The energy consumption is the average of the energy consumed by participating nodes in packet transfer from the source node to the destination node during all the simulation duration. End-to-end delay is the average transmission delay of data packets that are delivered successfully over all the simulation duration. The routing overhead is measured as the number of control messages transmitted at each node during the simulation. Each message hop is counted as one separate transmission.

In our protocol the choice of the path by a source node to transmit data packets toward a destination node is based on the minimum energy of nodes and the average energy of a path (see equation 4). This is mainly affected by the value of α. In order to find appropriate values of α, we analyze the impact of different values of α on the performance of our protocol AODVME+. We vary the value of α from 0.2 to 0.8 at intervals of 0.2.

We carried out our simulations to determine the effectiveness of our protocol. The principal goal of these simulations is to analyze our protocol by comparing it with other protocols, mainly AODVM and MMRE(4. )The values of simulation parameters are summarized in Table 1.

Table 1. Simulation Parameters.

Traffic Model	Constant bit rate (CBR)
Network Interface Type	Phy/WirelessPhy
MAC Type	IEEE 802.11
Mobility Model	Random Waypoint
Terrain Range	840 m × 840 m
Transmission Range	250 m
Number of Mobile Nodes	30 – 50 – 70- 90
Packet Size	512 bytes
RREQ_Wait_Time	1.0 s
RREP_Wait_Time	1.0 s
Simulation time	300 s

To evaluate AODVME+, we use the network simulator ns-2 [28]. Each simulation has a duration of 300 seconds. During each simulation, constant bit-rates (CBR) connections are generated, and each CBR connection produces 4 packets per second with a packet size of 512 bytes. We select the number of network nodes as 90 in an 840 m*840 m environment. The Random Waypoint model is used to simulate node movement, and each node moves with a speed randomly chosen from 0 to 5m/s, without pausing. The radio model uses characteristics similar to a commercial radio interface, Lucent’s Wave LAN. Wave LAN is a shared-media radio with a nominal bit-rate of 2 Mbit/s and a nominal radio range of 250 meters [29]. Each simulation is carried out under a network with a different number of nodes and the performance metrics are obtained by averaging over 10 simulation runs. We assume that a node consumes 281.8 mW receiving, and 281.8 mW while transmitting. It was shown in [21] that no real node energy optimisation can be achieved in the presence of overhearing or in idle state. For this reason, the energy consumption during idle or overhearing time is not considered in this model. In our simulations, we initialized the energies of the nodes randomly between 10 and 60 Joules (uniform distribution).

(a)   α=0.2

MMRE

AODVM

AODVME+ =0.2 α

(b)   α=0.4

beginning of the simulation, but it improves later. Initially, it is no better than the other protocols, because initially the majority of packets are not yet transmitted, so the total energy of sending and receiving packets is not important. From Fig. 2(a), we can observe, when α=0.2, that the MMRE protocol has lower average energy consumed compared to AODVME+ and AODVM, but the AODVME+ with α=0.4 consumes less energy, and is the best network performance in terms of average energy consumption. The reason is that AODVME+ focuses not only on the energy capacity of a node, which can also get depleted if there is a high level of traffic passing through it, but also on the average energy of the path. This combination guarantees that paths with higher energy are identified and selected for transmission. Thus energy is balanced out across the network and this reduces uneven energy consumption. Finally, we note that when α=0.6 or 0.8, the energy consumption of AODVME + is near to MMRE, because it promotes the max-min energy of the nodes in the path selection, which is the MMRE protocol principle.

AODVME+ =0.4

MMRE

—*— AODVM

AODVME+ =0.6

MMRE

—*— AODVM

AODVME+ =0.8

MMRE

AODVM

Fig 2. Energy consumed vs time.

Fig. 2 shows the energy consumed in different pause times by the AODVME+, MMRE and AODVM protocols. AODVME+ does not perform too well at the

α

α

α

Fig 3. End-to-end delay vs density.

Fig. 3 shows the compared protocols average end-to-end delay with α =0.4. The average end-to-end delay for all tested protocols increases with the increase in network size, but the average end-to-end delay of AODVME+ is lower than that of MMRE and AODVM. When the number of nodes of a network is between 50 and 70, the delay of the AODVME+ protocol is nearly (on average) 11% lower than the delay of the AODVM protocol and even lower than the MMRE protocol. This is mainly because the AODVME+ protocol selects the path depending on nodes’ residual energy combined with the average energy of this path; this greatly affects the end-to-end delay.

Fig 4. Routing overhead vs density.

From Fig. 4 we note that the routing control traffic is more important in the AODVM protocol. Indeed, 590 routing messages (in the case of the 70-node network) have been forwarded in the network during a 300 s time simulation versus 430 for the AODVME+ protocol. The multipath protocols AODVME+ and MMRE generate less control traffic than the AOMDV protocol. The increase in the multipath protocol performance is provided by the use of alternate paths when a link fails. The AODVME+ and MMRE protocols improve the number of control packets compared with AODVM. As can be seen, in all cases, AOMDVE+ has a smaller number of control packets compared with MMRE, which explains how AOMDVE+ can balance the battery utilization using a weighting between the minimum and the average energy of nodes.

• V.    Conclusions

Through this article we have proposed a new routing protocol for wireless ad hoc networks, where link failures and route breaks occur frequently. However, frequent changes topology exhaust the limited power nodes, and this provokes an early network split and thus decreases the network performance. Our approach consists of an extension to the AODVM routing protocol. Alternate paths are pre-computed, and when there is a link failure, one of the alternate paths is used (if at least one is available) to forward the data packets. The choice of the path depends on the weighted sum of all the paths found. The minimum residual energy and the average path energy are the terms used to calculate this weighted sum. By computer simulation, we have evaluated and studied the performances of our routing protocol AODVME+ and compared it with the AODVM and MMRE protocols. Simulation results have shown that our protocol consumes less energy, has a lower average end-to-end delay and minimizes the overhead traffic. We conclude that our protocol AODVME+ improves the network performance. This work shows some interesting possibilities because our AODVME+ solution can also be extended to include criteria for security and energy management during the path discovery process.

Acknowledgments

This work is part of the CAPRAH project 08/U311/4966, supported by the Algerian Ministry of Higher Education and Scientific Research.