Energy Optimized Ad hoc on-Demand Multipath Routing Protocol for Mobile Ad hoc Networks

Published Online October 2014 in MECS

A Mobile Ad hoc Network (MANET) is an interconnection of autonomous mobile nodes by wireless links forming dynamic topology and providing multi-hop communications without using much physical network infrastructure such as routers, servers, access points or cables or centralized administration. Each mobile node is acting as a router as well as a node. The properties of these networks make them to be more desirable in war zones, disaster recovery, aircraft and marine communications, industrial, home and other scenarios. The issues that are involved in MANET [1,2,3] are: (i) unpredictable link properties that expose packet collision and signal propagation, (ii) node mobility creates dynamic topology, (iii) limited battery life of mobile devices, (iv) hidden and exposed terminal problems occur when signals of two nodes are colliding with each other. (v) route maintenance is very difficult because of changing behavior of the communication medium, and (vi) insecurity.

Multipath routing protocols are needed to send communication from source to destination by having backup routes. During end-to-end communication, if a primary route fails, the backup routes are used for efficient delivery of messages at their destination. These protocols [4] are generally classified into (i) proactive, (ii) reactive and (iii) hybrid based on route discovery and maintenance mechanisms. Proactive routing protocols determine the routes to all destinations at start up and maintain using periodic update process. Reactive routing protocols determine routes when they are required by the source using route discovery process. Hybrid routing protocols combine the features of proactive and reactive together as a single protocol. In [5], the proactive routing protocols are more expensive than the reactive routing protocols in terms of energy consumption because of the former incurred large routing overhead.

Broadcast is a very important communication primitive in wireless ad hoc networks. Wireless ad hoc networks, due to their ad hoc nature and mobile environment, make frequent use of broadcast primitives to adapt to network changes. Broadcast is also widely used in sensor networks to disseminate information about environmental changes to other nodes in the network. Therefore, it is essential to develop efficient broadcast protocols that are optimizing energy consumption by incorporating information about nodes’ remaining battery levels into routing which helps to avoid route with low energy.

In this paper, we investigate and illustrate a multipath routing protocol with minimal nodal residual energy between any source to destination pair in order to reduce energy consumption, routing overhead and average end to end delay. We propose a novel route update rule for AOMDV routing protocol by modifying the route update rule of MMRE-AOMDV routing protocol in order to generate more energy efficient routes than MMRE-AOMDV and to elect the efficient route among multiple routes between any source and destination pair based on minimal residual nodal energy to forward data packets.

The rest of the paper is organized as follows: Section II gives a brief description about the related work. Section III presents the proposed routing protocol. The simulation environment and experimental results are discussed in Section IV. Finally, conclusions and future work are given in Section V.

• II.    Related Works

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

AOMDV [6] is the extension of a well-studied AODV [7] so as to eliminate the occurrence of frequent link failures and route breaks in a highly dynamic ad hoc networks. It adds some extra fields in routing tables and control packets, and follows the two rules during a route discovery phase in order to compute loop-free and link-disjoint multiple routes between a source and destination. The rules are (i) the route update rule establishes and maintains multiple loop-free paths at each node, and (ii) the distributed protocol finds link-disjoint paths. Link failures may occur because of node mobility, node failures, congestion in traffic, packet collisions, and so on.

There is no common link among the multiple routes between a source and destination pair in the link-disjoint routes. To achieve loop-freedom, every node maintains a variable called the advertised hop count . The advertised hop count is added in each RREQ (route request) or RREP (route reply) and in addition to the routing table has the usual fields that are used for AODV. The advertised hop count field of a node is set to the length of the longest available path to the destination expressed in terms of the number of hops if it initiates a RREQ or RREP with a particular destination sequence number and it remains unchanged till the associated destination sequence number is changed.

The loop-freedom rule says that if a node receives a RREQ (RREP) for a particular destination with a destination sequence number: (i) it should update its routing information with the information obtained from the received RREQ (RREP) if the destination sequence number is higher than the one stored in its routing table; (ii) it can re-send the received RREQ (RREP) when the advertised hop count in the RREQ (RREP) is greater than the corresponding value in its routing table and if the destination sequence number is equal to the one stored in its routing table; and (iii) it can update its routing table with the information available in the received RREQ (RREP) when the advertised hop count in the RREQ (RREP) is less than the corresponding value in its routing table if the destination sequence number is equal to the one stored in its routing table.

For link-disjointness, each node maintains a route list in its routing table for a particular destination and its route list contains the next hop, last hop, and hop count information for the destination. The next hop represents a downstream neighbour through which the destination can be reached. The last hop refers to the node immediately preceding the destination. The hop count is used to measure the distance from the node to the destination through the associated next and last hops. The link-disjointness among all the paths can be achieved if a node can ensure that those paths to a destination from itself differ in their next and last hops. Using this observation, AOMDV ensures link-disjointness among multiple routes for the same source and destination pair and also adds a last hop field in each RREQ and RREP.

In AOMDV, all copies of an RREQ are examined for the potential alternate reverse paths during route discovery. On receiving an RREQ, an intermediate node creates a reverse path if the RREQ satisfies the rules for loop-freedom and link-disjointness. Moreover, it checks if it has one or more valid next hop entries for the destination. The intermediate node generates an RREP and sends it back to the source along the reverse path if such an entry is found. Otherwise, it rebroadcasts the RREQ. The destination follows the same rules for creating reverse paths if it receives RREQ copies. Unlike the intermediate nodes, it generates an RREP for every copy of RREQ that arrives via a loop-free path, for increasing the possibility of finding more disjoint routes.

• B.    Power Efficient Routing

Power saving during route discovery and power control during data transmission are the two major classification of power saving techniques for wireless ad hoc networks. The total energy consumption is reduced in power saving technique in idle listening mode [8,9,10] by putting the mobile nodes into periodical sleep where as in power control technique [11,12], the total energy consumption is also reduced by adjusting the transmission ranges during data transmission. Broadcast is a very important communication primitive used in wireless ad hoc networks. Several power efficient on-demand routing protocols have been developed. Liu et al. [13] proposed a novel Collision-Constrained Energy Algorithm (ECCA) by defining correlation factor to weigh collision probability while using node-disjoint multipath to transmit data simultaneously. It also calculates an upper limit for correlation factor according to service requirement, and find a minimum energy node-disjoint multipath routing to satisfy the upper limit.

Liang et al. [14] designed an energy and mobility aware geographical multipath routing for wireless sensor networks. This algorithm considers the remaining battery capacity, mobility, and distance to the destination node of candidate sensors in the local communication range for next hop relay node selection, and a fuzzy logic system applied for decision making. Simulation results showed that this scheme could extend the network lifetime. In [15], Bergamo et al. proposed a DPC(Distributed Power Control) Energy Efficient routing protocol for ad hoc networks, which acts in combination with the routing layer by means of a mechanism estimating the amount of power which is needed for reliable communications over any link. This power is then used both to transmit a packet over the link, and the link weight is calculated using minimum-weight path search algorithm. In this way, transmit power can be tuned in order to build the desired connectivity diagram and its information is used to privilege lower energy paths while looking a route for packet transmission. Existing routing protocols, such as proactive and reactive protocols, can be modified in order to incorporate this power control feature which tries to minimize the interference in the network and the energy consumption of multihop operation.

Yumei Liu et al. [16] have proposed Maximal Minimal nodal Residual Energy (MMRE) approach into the existing AOMDV, called MMRE-AOMDV routing protocol by finding minimal nodal residual energy of each route in the route discovery phase and sorting multiple routes by descending nodal residual energy and use the route with maximal nodal residual energy to forward data packets. Simulation results showed that this scheme could extend the network lifetime and packet delivery ratio and diminish the number of nodes dying than AOMDV. Our work deals with conserving power by employing power control mechanism for data transmission.

• III.    Proposed Routing Protocol: OMMRE-AOMDV

Our multiplath routing protocol is extended by slightly modifying MMRE-AOMDV route update rules in order to generate more energy efficient routes than MMRE-AOMDV routing protocol which reduces energy consumption, routing overhead, normalized routing overhead and average end-to-end delay. It also improves packet delivery ratio and throughput.

The following are the general procedures of OMMRE-AOMDV routing protocol:

• 1.    Finding minimal nodal residual energy of each route between any source and destination pair in the route discovery process, that is, min_re_energy .

• 2.    Sorting the multiple routes by descending nodal residual energy and elect the route with maximal nodal residual energy to forward data packets.

• A. Finding minimal nodal residual energy

Several changes required in the route discovery phase of AOMDV to find the minimal nodal residual energy of each route between any source and destination pair. Each RREQ and RREP now carries an additional field called min_re_energy in order to have the route’s minimal residual energy. Structure of Routing Table Entries of AOMDV, MMRE-AOMDV and OMMRE-AOMDV routing protocols are illustrated in Fig. 1.

Destination sequence number advertised hop count route list {(nexthop 1 ,hopcount 1 ), (nexthop₂,hopcount₂),…} expiration time out AOMDV [6]

destination sequence number advertised hop count route list {(nexthop1,hopcount1,min_re_energy1), (nexthop2,hopcount2,min_re_energy2),…} expiration time out OMMRE-AOMDV (MMRE-AOMDV [16])

In the source node the value of min_re_energy should be assigned as a maximum value such as node’s initial energy. In the intermediate nodes, the route update rule of OMMRE-AOMDV is shown in Fig.4 invoked whenever a node receives the route advertisement. In other words, when an intermediate node receives RREQ if the sequence number of just received packet is greater than this node, it updates its residual energy with the min_re_energy of RREQ of this node if it is less than min_re_energy of RREQ of this node in order to keep the value of min_re_energy lowest among all the nodes in this route. The set up of reverse routes at the destination node of OMMRE-AOMDV routing protocol is just like in AOMDV routing protocol.

• 1.       if ( seqnum i^d < seqnum ^dj ) then

• 2.               seqnum i^d := seqnum ^dj ;

• 3.                if ( i ≠ d ) then

• 4.                              advertised _ hopcount_i ^d : = ∞;

• 5.                else

• 6.                              advertised _ hopcount ^d _i := 0;

• 7.               end if

• 8.               route _ list i^d = NULL ;

• 9.                insert ( j ,    advertised _ hopcount ^dj   +1,

• 10.     else if ( seqnum i^d = seqnum ^dj ) and (( advertised _ hopcount i^d ,i) >

• 11.              insert ( j ,    advertised _ hopcount ^dj   +1,

• 12.    end if

min_re_energy ^dj ) into route _listⁱ d ;

( advertised _ hopcount j^d ,j)) then

min_re_energy ^dj ) into route _listⁱ d ;

Fig. 2. Route Update Rules of AOMDV Routing Protocol [6]

The AOMDV route update rules are illustrated in Fig. 2, when a node i receives a RREQ or RREP, it updates its advertised hop count for a destination d if its sequence number is less than the sequence number of RREQ or RREP of node j.

• 1.       if ( seqnum i^d < seqnum ^dj ) then

• 2.            seqnum i^d := seqnum ^dj ;

• 3.             if ( i ≠ d ) then

• 4.               if ( re_energy i < min_re_energy ^dj ) then

• 5.                     min_re_energy ^dj := re_energy i ;

• 6.                     advertised _ hopcount i^d :=∞;

• 7.                     route _ list i^d = NULL ;

• 8.                      insert ( j ,   advertised _ hopcount ^dj +1,

• 9.                 else

• 10.                    advertised _ hopcount ^di := 0;

• 11.               end if

• 12.     else if ( seqnum i^d = seqnum ^dj ) and (( advertised _ hopcount i^d ,i) >

• 13.         if ( re_energy_i < min_re_energy ^dj ) then

• 14.               min_re_energy ^dj := re_energy_i ;

• 15.               insert ( j ,    advertised _ hopcount ^dj   +1,

• 16.    end if

min_re_energy ^dj ) into route _listⁱ d ;

( advertised _ hopcount j^d ,j)) then

min_re_energy ^dj ) into route _listⁱ d ;

Fig. 3. Route Update Rules of MMRE-AOMDV Routing Protocol [16]

The MMRE-AOMDV route update rules are illustrated in Fig. 3, when a node i receives a RREQ or RREP, it updates its advertised hop count for a destination d if its sequence number is less than the sequence number of

RREQ or RREP of node j as well as it updates its minimal residual energy with the minimal residual energy of RREQ or RREP of node j if minimal residual energy of RREQ or RREP of node i is less than minimal residual energy of RREQ or RREP of node j. Since the MMRE-AOMDV route update rules create fresh route list when an energy efficient route between any source to destination pair encountered, we propose an Optimized MMRE-AOMDV (OMMRE-AOMDV) route update rules by slightly modifying MMRE-AOMDV route update rules in order to generate more energy efficient routes than MMRE-AOMDV routing protocol illustrated in Fig.4.

• 1.       if ( seqnum i^d < seqnum ^dj ) then

• 2.            seqnum i^d := seqnum ^dj ;

• 3.             if ( i±d) then

• 4.              if ( re_energy i < min_re_energy ^dj ) then

• 5.                    min_re_energy ^dj := re_energy i ;

• 6.                     advertised _ hopcount,^d :=ro;

• 7.                else

• 8.                    advertised _ hopcount ^di := 0;

• 9.              end if

• 10.             route _ list i^d = NULL ;

• 11.             insert ( j ,    advertised _ hopcount ^dj   +1,

• 12.     else if ( seqnum i^d = seqnum ^dj ) and (( advertised _ hopcount i^d ,i) >

• 13.         if ( re_energy i < min_re_energy ^dj ) then

• 14.              min_re_energy ^dj := re_energy_i ;

• 15.              insert ( j ,    advertised _ hopcount ^dj   +1,

• 16.    end if

min_re_energy ^dj ) into route _listⁱ d ;

( advertised _ hopcount j^d ,j)) then

min_re_energy ^dj ) into route _listⁱ d ;

Fig. 4. Route Update Rules of OMMRE-AOMDV Routing Protocol

• B.    Sorting multiple routes by descending nodal residual energy and the route selection process

Each node maintains route list as shown in Fig.1. After finding the minimal nodal energy phase, the multiple routes between any source and destination pair are sorted by descending nodal residual energy. We add another field into the route list called min_re_energy . The value of min_re_energy is updated according to the rules as shown in Fig.4.

Whenever a node i receives a route advertisement to a destination d from a neighbour j, it invokes OMMRE-AOMDV route update rules in order to setup forward routes as shown in Fig. 4. The variables seqnum i^d , advertised _ hopcount i^d , route _listⁱ d , and min_re_energy ^dj are sequence number, advertised_hopcount, route_list and minimal nodal residual energy for destination d at node i or node j respectively. The route with maximal nodal residual energy for any source to destination is adopted for forwarding data packets.

• IV.    Simulation Environment and Experimental Results

• A.    Simulation model

We evaluate the performance of OMMRE-AOMDV ,

MMRE-AOMDV and AOMDV routing protocols using NS 2.34 [17,18,19,20]. Fig. 5 and Table 1 illustrate the simulation model and the simulation parameters respectively. The result of simulation generated as trace files and the awk & perl scripts prepared for analyzing the trace files into graphs for various performance metrics.

Fig. 5 Overview of the simulation model

Table 1. Simulation Parameters

Parameter	Value
Simulator	NS-2.34
MAC Type	802.11
Simulation Time	100 seconds
Channel Type	Wireless Channel
Routing Protocols	AOMDV, MMRE-AOMDV & OMMRE-AOMDV
Antenna Model	Omni
Simulation Area	2200 m x 600 m
Traffic Type	CBR(udp)
Data Payload	512 bytes/packet
Network Loads	4 packets/sec
Number of Connections	40
Radio Propagation Model	TwoRayGround
Idle Power	0.005
Transmission Power	12.7
Receiving Power	12.7
Sleep Power	0.0001
Transition Power	0.002
Transition Time	0.005
Initial Energy	100 Joules
Interface Queue Length	50
Interface Queue Type	DropTail/PriQueue
Number of nodes	100
Pause Time	0
Speed	5,10,15,20,25
Mobility Model	Random Waypoint (RWM)
Simulation Time	100 Sec.
Parameter	Value

• B.    Experimental results and Discussion

We evaluate the following six different performance metrics:

• (i)    Average End-to-End delay - the average time of the data packet to be successfully transmitted across a MANET from source to destination. It includes all possible delays such as buffering during the route discovery latency, queuing at the interface queue, retransmission delay at the MAC, the propagation and the

transfer time.

• (ii)    Routing overhead – the total number of control packets or routing packets generated by routing protocol during simulation.

• (iii)    Normalized Routing overhead – the number of routing packets transmitted per data packet towards destination during simulation.

• (iv)    Total Energy consumed – the summation of the energy consumed by all nodes in the simulation environment. i.e., energy consumed by a node = initial energy of that node – residual energy of that node .

• (v)    Throughput – the number of bytes received successfully.

• (vi)    Packet Delivery Ratio – the ratio of data packets delivered to the destination to those generated by the sources.

Fig. 6 represent the Average End-to-End Delay (in ms) of AOMDV, MMRE-AOMDV and OMMRE-AOMDV routing protocols. Our OMMRE-AOMDV routing protocol reduces end to end delay whenever speed of the node increases. It is found that the routing overhead is also reduced by our protocol compared with AOMDV and MMRE-AOMDV routing protocols as shown in Fig. 7. It is found that the normalized routing overhead is also reduced by our protocol compared with AOMDV and MMRE-AOMDV routing protocols as shown in Fig. 8. It is also found that the total energy consumption of our protocol is very less (more efficient) when we compare it with AOMDV and MMRE-AOMDV routing protocols as shown in Fig. 9. OMMRE-AOMDV protocol gives better throughput and packet delivery ratio than AOMDV and MMRE-AOMDV protocols as shown in Fig. 10 and Fig. 11 respectively.

• V.    Conclusions and Future Work

We proposed an OMMRE-AOMDV routing protocol by extending MMRE-AOMDV routing protocol [16] in order to generate more energy efficient routes which reduces the energy consumption, average end to end delay, routing overhead and normalized routing overhead. It also improves the throughput and packet delivery ratio under random way point mobility model. Simulation results show that the OMMRE-AOMDV routing protocol performed better than AOMDV and MMRE-AOMDV routing protocol.

In future we will put a greater effort to improve its overall performance considering new metrics associated with network nodes such as networks lifetime and reduction in average number of nodes dying in different mobility models by studying and enhancing recent power efficient strategies. We will also make changes in OMMRE-AOMDV to co-operate with MAC layer’s multi-interface and multi-channel assignment schemes for wireless sensor or vehicular networks.