Energy Aware Ad Hoc On-Demand Multipath Distance Vector Routing

Published Online June 2015 in MECS

Recent advances in sensor technology, low-power analog and digital electronics, and low-power radio frequency designs have enabled the development of these cheap, small, low-power sensor nodes, integrating sensing, processing, and wireless communication capabilities. Where traditional communication protocol stacks assume an excess of resources and can spare the energy and memory to send many messages, sensor nodes need to save on every bit transmitted to ensure an acceptable network lifetime [20]. Reading sensor data and communication of that data to the base station consumes most of the battery power. WSNs motes are usually battery powered and so have a limited amount of available energy for sensing, processing and communicating. Efforts to make the deployment of motes in the network cheaper, for example, by reducing battery size and extending their lifetime have been worked on intensively during the last decade. Energy consumption becomes worst in the presence of very high traffic loads. This is because radio communication is a very power hungry task and can drain WSN battery very, very quickly. Therefore, communication becomes inefficient in the presence of high traffic loads.

There are numerous routing protocols available which aim to find best network paths. In full multipath routing protocols data is sent along all paths so there is no dilemma in path selection. However, the work in this paper is based on Alternate Path Routing (APR) [23], [7], which does involve the selection of one path on which to send data. Usually path selection is based on a single criterion or metric which is the number of hops to reach the required destination. Generally the shortest path is chosen when selecting a path to send data to the sink mote. The idea of selecting among different criteria has been explored using WSNs, but the focus of this dissertation in the context of a multiple metric path selection algorithm for WSNs using the AOMDV routing protocol along node or link disjoint paths has never been explored.

WSNs have an ad hoc arrangement of motes and therefore there exist many pathways for communication to take place between sensing source motes and the destination mote. It is the job of the routing protocol to find these paths. Typical on-demand routing protocols, for example, Ad hoc On-demand Distance Vector (AODV) [18] and Dynamic Source Routing (DSR) [10] used in WSNs are based on using the shortest paths to route packets between source and destination motes. However, the shortest path may experience quick energy drainage as a result of excessive usage, resulting in more energy efficient paths to be left out when routing packets over the network. The Ad hoc On-demand Multipath Distance Vector (AOMDV) [14] routing protocol is an extension of the AODV routing protocol with the addition of forming multiple paths to be found between a given source and destination node. Two of the major goals of the AOMDV routing protocol were to improve on the AODV routing protocol by answering the following questions: (1) In the AODV routing protocol, how to compute multiple paths between source and destination motes during route discovery? and (2) How to do this with minimal additional overhead to the AODV routing protocol? Like the AODV routing protocol, the AOMDV routing protocol has an on-demand flood based route discovery mechanism, uses a distance vector routing algorithm and employs hop-by-hop routing, where the routing list is sorted based on hop count. There are route discovery and maintenance phases like the AODV routing protocol, but there are multiple paths per route discovery.

The AOMDV protocol ensures loop free paths similar to that of the AODV routing protocol, but an additional feature is the assurance that all paths found are disjoint. The AOMDV routing protocol can either produce link or node disjoint paths, but in this work node disjoint paths are considered. The default number of disjoint paths found is three, but can be adjusted. In the route maintenance phase, the AOMDV routing protocol uses alternate routes on a route failure. New route discovery calls will result in an increase in the number of ‘overall’ route discoveries and so routing overhead for a given time segment. Major uses of the AOMDV routing protocol would be in MANETs (Mobile Ad hoc Networks).

Typically, WSNs motes are battery powered and so have a limited amount of available energy for sensing, processing and communicating. Efforts to make the deployment of motes in the network cheaper, for example, by reducing battery size and extending their lifetime have been worked on intensively during the last decade. Energy consumption becomes worst in the presence of very high traffic loads. This is because radio communication is a very power hungry task and can drain WSN battery very, very quickly. Therefore, communication becomes inefficient in the presence of high traffic loads. A single base station is common in WSNs [25] and this model is used in this research work. Network lifetime can be described by the following methods: (1) “the time to the first node failure due to battery outage,” (2) “the time that an application becomes non-functional or” (3) “the time to the first network partitioning” [8]. Assuming that the number of nodes in the network is fixed, in (1) one mote is out of energy, while in (2) and (3) either no mote is alive (whole network is out of energy) or all the rest except one mote are alive.

We use method (3) in this paper to describe WSN lifetime. The lifetime is complete when there is lost network connectivity in major portions of the WSN. However, we can use method (1) more in the context of describing node survivability for a WSN, but will be more general and redefine it as (1) the time to any node failure due to battery outage. Hence, we take into consideration the lifetime of all motes when determining WSN node survivability in this context. “A non-uniform energy drain is observed in most WSN topologies, with motes nearer to the base station experiencing a greater loss of energy, due to the processing of more messages.” [3]

AOMDV path selection can be either node or link disjoint. To enhance the AOMDV protocol a multicriteria path selection mechanism is proposed and added. This new M-AOMDV routing protocol will try to improve path selection using a trade-off between energy and hop count or packet loss and hop count, thus it hopes to give more longevity, usefulness and intended purpose for motes and applications using the network. The protocol has to be lightweight, scalable and efficient routing additions to the AOMDV routing protocol. This will reduce the costs of expensive battery replacement or preserve essential data packet application requirements. The proposed solution is above the Media Access Control (MAC) layer, at the mote Network Layer [32], so it tries to avoid expensive hardware and firmware modification enabling quick, easy and cheap deployment of sensor motes, using off the shelf components.

One of the aims of this paper was to improve energyawareness in WSNs by improving an on-demand routing protocol targeted for them as they are energy-penurious networks. The motivations of energy needs in WSNs are clearly elucidated in the literature [10][27]. Presently there have been a lot of research on alternative energy methods, such as, solar, wind, wave, geothermal etc... but these methods may be application specific and they have not shown their effectiveness in satisfying mote energy requirements to equal that of battery.

WSN motes are usually placed in remote locations and battery replacement becomes nearly impossible. When motes run out of battery power the network becomes nonfunctional and it is very costly to replace motes. This means battery life will determine how long the area will be monitored. The time the network is not functioning may be immediate due to disruption in application life, but long deployment time may result in the loss of important sensing data, sometimes resulting in disastrous consequences, for example, loss in important seismic [29] or structural (bridges or buildings) monitoring data [30]. By improving battery life the WSNs will be able to monitor its surroundings for longer periods, which eventually reduce the time for costly replacement procedures.

In addition in-network processing and data aggregation which are inherent in WSNs may cause motes to use additional energy apart from the costs of sleeping, sensing and overhearing data transmissions. Also there is an ever increasing need to encompass vector data in sensor transmission, for example, Medium and High Rate Wireless Sensor Networks (MHWSNs) [17]. This poses a special challenge in terms of energy usage.

Next we describe the motivation that facilitated this work in section II. Following this, we discuss the methodology involved in building an implementation for the proposed work in section III. This includes the SAW MCDM technique, an energy metric and the EA-AOMDV protocol. The network simulator, ns2, simulation settings is given in section 4, with the results in section V. Section V first discusses WSN node lifetime, with a discussion following. Finally, we describe the conclusion giving a synopsis of the entire paper in section VI.

• II.    Background and Related Work

Currently AOMDV protocol uses the hop count metric to determine which path to route packets. Shortest path selection based on a single routing metric will not necessarily improve network energy usage. Some important network parameters that will assist the network with achieving some of its intended goals may be excluded. One result may be that the shortest path may experience quick energy drainage, resulting in more energy efficient paths to be left out when routing packets over the network. This will lead to inefficient energy usage, resulting in shorter network lifetimes, a decrease in individual mote longevity, and an uneven distribution of energy within the network. To introduce a more qualitative approach to routing that includes the network’s energy needs, a routing energy metric is needed. Previously, this approach has been used in [26] schemes and has had varying benefits [2]. However, we argue that such schemes have not been proposed for the AOMDV protocol.

The proposed improvement to the AOMDV protocol will require each mote to measure and maintain state information for both the hop count to the destination and the route energy metric, which is basically the mote with the lowest energy value on the path from source mote to destination mote. If we let M be the subset of all the possible node disjoint paths between a source and destination mote then we could add a procedure to the AOMDV algorithm to select a routing path that best optimizes the energy usage of the network rather than just blindly using the shortest path. The strategy proposed in this paper is to find the optimal path from the set M to route packets from source to destination which would lead to overall mote longevity. The basic assumption is that a path is as reliable as its weakest mote and that the weakest motes on multiple paths between source and destination motes should be avoided.

There is no work to date on routing on a combination of hop count and an energy metric in the AOMDV routing protocol. Thus, introducing a mechanism to consider multi metric routing for energy-awareness in the AOMDV routing protocol is considered a novelty. One contribution of this paper is to evaluate the energy performance of the proposed Multi-criteria Ad hoc On-

demand Multipath Distance Vector (EA-AOMDV) routing protocol.

III. SAW

The MCDM [22], [1], [20] is used to determine the best alternative from a set of alternatives given a set of decision criteria. A simple commonly used MCDM method is the Simple Additive Weighting method (SAW) [1] ,[21]. Given a set of alternatives A i (1 < i < n), criteria C j (1 < j < m), weights of criteria W j (1 < j < m) and the measures of performance of alternatives, x ij , the SAW methods uses equations 1 and 2 to build a normalization matrix z ij .

()

=(    ),=1

()

=(    ),=1

,…, ;  ∈ Ω

,…, ;  ∈ Ω

where a j is the max(x ij ) for criterion j and, b j is the min(x ij ) for criterion j, Q b and Q_c are, respectively, the sets of benefit and cost criteria [12]. Associated with each criterion column j in the decision matrix z_i j is weighting w j such that the sum of the sums equals 1. The overall assessment of each alternative is computed by equation 3. The greater the value y i means that the alternative is ranked higher.

= ∑      , =1,…,

A. Route Discovery Phase

In this section we will present an illustrative example of how the EA-AOMDV routing protocol uses SAW method. A WSN topology consisting of four node disjoint paths is shown in Figure 1.

The motes are labeled from A to O and S. The mote labeled A is the source and the node labeled S is the WSN sink. In this example, mote A chooses from four paths when it wants to send data to S. The energy value for each path the mote with the smallest energy value. The hop count for every edge is 1. The hop count is labeled on each link. Assume that data packets are currently being transmitted along path A-B-C-S. The

minimum energy value along all paths will be determined by the sink mote, S. S will now transmit these values back to the source mote, A. A will store the values in its routing table for the various paths. Also the routing decision vector is calculated by using the SAW method. The SAW method makes a multi-criteria path selection for the source mote from the four paths. Take Table 1 as an example. The SAW method would be applied to the

hop count and energy values in the WSN. The eventual   D-E-F-S now has a higher value of 0.87 compared to 0.80

values would lead to the switching of paths from the    for path A-B-C-S.

shortest path A-B-C-S to A-D-E-F-S. This occurs as A-

Table 1. SAW metric values.

Path	Hop count	Energy	SAW Hop Count Value	SAW Energy Value	Combined SAW Hop Count and Energy
A, B, C, S	3.00	25.00	1.00	0.67	0.80
A, D, E, F, S	4.00	34.00	0.67	1.00	0.87
A, G, H, I, J, S	5.00	18.00	0.33	0.41	0.38
A, K, L, M, N, O, S	6.00	7.00	0.00	0.00	0.00
a	3.00	7.00	1.00	1.00
b	6.00	34.00	0.00	0.00
weights	0.40	0.60	0.40	0.60

The M-AOMDV routing uses the same method as the AOMDV protocol to discover and populate the motes routing for multiple routes to a given destination. During the protocol’s route discovery phase, the packet loss percentage is set to zero and stored in each mote’s routing table. Since at this stage there is no packet loss information, the shortest path is used for initial data transmission.

• B.    Energy Metric

Each mote in the WSN has an energy value associated with it given by:

fi(t) = Pnx(t) + Ptx(t) + Prx(t) + Plx(t)           (4)

where Pnx(t) is the mote’s residual energy, Ptx(t) is the transmit power, P (t) is the receive power and P (t) is the idle power of mote k at time t. The mote with the lowest energy on a given path determines the energy for the entire path. Therefore, in each of the n paths available to a source mote for routing to the destination, there exists a mote that has the least energy, say Ei for path i. Given that there are n paths to the destination mote, the max( E ) is used to determine which path has the best energy. We believe that the path selection mechanism should select paths which avoid motes with low energy thus maximizing the lifetime of weaker motes.

• C.    EA-AOMDV

The EA-AOMDV routing protocol consists of multiple components, which are shown in Figure 2 below:

Fig. 2. Components of the EA-AOMDV routing protocol

Energy Metric

EA-AOMDV

In a fully connected graph the number of paths between a given source and destination nodes could be very large. Finding the shortest path is NP-Hard [11] ,[6] and in this work we follow the AOMDV approach by setting the number of discovered paths to 3 [18]. Hence, only 3 paths are stored in the mote routing table for a given destination route.

The energy metric is also stored at the motes routing table along with a SAW value, advertised hop count and last hop as shown in Table 1. The EA-AOMDV has four phases which includes: route discovery (RD), Energy discovery (ED), route selection (RS); and, Route Maintenance (RM). Each phase is described in the following:

• i.    Route Discovery Phase

The EA-AOMDV routing uses the same method as the AOMDV protocol to discover and populate the motes routing table for multiple routes to a given destination. During the protocol’s route discovery phase, the energy value metric is set to zero and stored in each mote’s routing table. At this stage there is no routing energy information and therefore, the shortest path is used for initial data transmission.

• ii.    Energy Discovery Phase

In this phase the source mote sends specially marked packets called data collection packets to the sink mote. A data collection packet is sent on each existing path to the sink mote. The purpose of these packets is to obtain the lowest mote energy value along each path. As the collection packet traverses the path, each mote calculates its energy using Equation 4 and appends this energy value to the collection packet. When the sink mote receives the collection packet for a given path it determines the lowest energy value for that path and sends this value back to the source mote via a special packet called reverse data collection packet. The energy value from the reverse data collection packet is then used to update the source mote’s routing table. When all routes are updated the SAW MCDM method described in Section 3.1 is used to calculate a SAW value for each route by using both the energy value and the hop count values in the mote’s routing table.

• iii.    Route Selection Phase

After the ED phase is completed multiple paths in a given routing table will have a hop count, an energy value and a SAW value for each route for a given destination mote. The shortest path selected at the RD phase is then replaced with the route to the destination with the highest SAW value.

• iv.    Route Maintenance Phase

During normal network operations the routing energy metric is periodically updated, using the ED phase, to ensure that paths selected for routing have the most recent metric values for the calculation of the SAW path value. This phase ensures that routing energy losses experienced along a path are taken into consideration. Hence new SAW values could invoke alternate paths to be used to send packets to a given path with better routing energy values.

The energy model used in ns2 allowed the starting energy value of the mote to be set. All motes received the same initial energy value of 200 Joules. The mote residual energy is obtained from the ns2 energy model and this is the mote energy value at any specific point in time during the simulation. A 1000 byte packet size is used. However, the data frame length used in the experiment is 50 bytes. This means that at the MAC layer a 1000 byte packet will be broken down into twenty, 50 byte data frames which will be sent across the network. This 50 byte data transfer size is still comparable to that of the TinyOS [16] packet used specifically for WSNs. However, there will be a lot of energy use at the MAC layer in order to break the 1000 byte packet into chunks. Thus, by setting the packet size to 1000 bytes the energy usage of the network is tested under the condition of high energy use at the mote. This condition of high energy use is critical to the simulation. The simulation settings selected for this simulation are shown in Table 2.

• IV. Simulation Setting

To evaluate WSNs with the EA-AOMDV routing protocol, the ns-2 simulator [13] is used. The ns-2 simulator is used extensively in evaluating the performance of ad hoc network routing protocols. A static WSN topology (see Figure 3) with a single base station is common in WSNs [31].

The averages and/or variance found when running the simulation several times would give a statistical analysis of a simulation. A total of 1000 runs were done and the average was taken from all the runs. The simulations model radio propagation using the realistic two-ray ground reflection model and account for physical phenomena such as signal strength, propagation delay, capture effect, and interference [15]. The Medium Access Control (MAC) protocol used is the IEEE 802.11 Distributed Coordination Function (DCF) [5]. This protocol has been used as a MAC layer protocol in WSNs for energy efficiency with commendable results. [4]

Fig. 3. Simulation 150 mote WSN topology

• V. Simulation Results

• A. WSN Node Lifetime

The residual energy values of the WSN motes were taken during the simulation. Motes that were completely drained of energy are not considered. The graph on Figure 4 gives the number of motes versus the percent residual energy at 120 seconds. Both routing protocols are tested along node disjoint paths. For residual energy values under 20%, the WSN with the EA-AOMDV routing protocol supports the same amount of motes as the WSN with the AOMDV routing protocol. Both had 8 motes in this energy range from the initial 150 motes. However, in the higher energy ranges, above 75% residual energy, the WSN with the EA-AOMDV routing protocol has 118 motes or 79% compared to 55 motes or 37% for the WSN using the AOMDV routing protocol. This 79% residual energy in the case of EA-AOMDV protocol is quite significant for the expected lifetime of

Table 2. Simulation settings

Method Value Simulator ns2.34 Channel type Channel/WirelessChannel Radio-propagation model Propagation/TwoRayGround Network interface type Phy/WirelessPhy MAC type Mac/802.11 Link layer type LL Antenna Antenna/OmniAntenna Area (mxm) 800 x 800 Number of mobile motes 150 Routing protocol AOMDV Energy model EnergyModel Encoding codec CBR Packet size/data payload 1000 bytes Data frame length 50 bytes Transport protocol UDP the network as there are many motes within this high energy range. The 37% residual energy in the case of AOMDV protocol means that the expected lifetime of the network would be much shorter since most

s EA-AOMDV

Fig. 4. Measure of mote lifetime - 120s into simulation: number of motes versus percent residual energy motes have already died and only few with high energy values remain.

Towards the end of the experiment most of the energy from the network motes is drained (see Figure 5). Both routing protocols had no motes with energy more than 65% residual energy. However, in lower energy ranges we clearly observe the superiority of the WSN that used the EA-AOMDV routing protocol. In the range above 40% residual energy, the EA-AOMDV has 66 motes compared to 6 for the AOMDV routing protocol. In other words, the EA-AOMDV routing protocol still has 44% of motes in the energy range (40%-65%) whilst the AOMDV protocol for this residual energy range have only 4% of motes. In the range below 40% residual energy, the EA-AOMDV and AOMDV routing protocol have roughly the same amount of motes. The AOMDV has 6 more motes in the residual energy range below 40% with AOMDV having 23 versus 17 for EA-AOMDV.

This result shows that the WSN with the AOMDV routing protocol has significantly more energy deprived motes at the end of the simulation compared with the EA-AOMDV protocol. Finally, we see that the WSN with the EA-AOMDV routing protocol has in total 83 or 55% of motes still living, while the WSN with the AOMDV routing protocol has only 29 or 19% of motes still living.

s EA-AOMDV

Fig. 5. Measure of mote lifetime - 180s into simulation: number of motes versus percent residual energy

• B.    Discussion

Overall the WSN with the EA-AOMDV routing protocol communicating along node disjoint paths shows greater longevity. The disadvantage of using only the hop count metric for energy-aware routing is that the continual reliance on the usage of shorter paths forces motes with high energy to be quickly drained. The WSN with the EA-AOMDV routing protocol protects motes on shortest paths by exempting them from excessive communication. This occurs as SAW path selection uses longer paths than the hop count shortest path selection method. Also, the EA-AOMDV routing protocol will experience less route discovery calls as a result of having paths with a better and more balanced network energy distribution. This would result in less use of network energy and a greater expected lifetime. The EA-AOMDV routing protocol preserves shortest paths as low energy motes on these paths will cause a new path to be selected. This can be advantageous as shortest path motes may become mission-critical and their deaths will prevent future usage of these paths.

• VI. Conclusion

An energy-aware AOMDV routing protocol is proposed in this paper. It incorporates the SAW MCDM method and an extra routing energy metric. It is shown that EA-AOMDV improves the expected lifetime of the network. It does this by providing a more energy conservative multi-criteria routing approach.