Energy Efficient Routing Protocols for Mobile Ad Hoc Networks

Energy Efficient Routing Protocols for Mobile Ad Hoc Networks

Abstract

In mobile ad hoc network nodes have limited battery power. If a node is used frequently for transmission or overhearing of data packets, more energy is consumed by that node and after certain amount of time the energy level may not be sufficient for data transmission resulting in connection failure. In this paper, we have considered three routing protocols-Dynamic Source Routing (DSR) & Minimum Maximum Battery cost Routing (MMBCR), Ad hoc OnDemand Distance Vector Routing Protocol (AODV) and studied their performances in terms of network lifetime for the same network scenario. Simulations are carried out using NS2. Finally from the simulation results we have concluded that MMBCR gives more network lifetime by selecting route with maximum battery capacity thereby outperforming DSR.

General Terms:

Energy efficiency, MANETS, Routing Protocols. Keywords:

Battery capacity, DSR, MMBCR, AODV, Network Lifetime.

1. Introduction

   Nodes in an ad hoc wireless network are constrained by limited battery power for their operation. Hence, energy management [1], [2], [3] is an important issue in such networks. The use of multi-hop radio relaying requires a sufficient number of relaying nodes to maintain the network connectivity. Hence, battery power is a precious resource that must be used efficiently in order to avoid early termination of any node. Energy saving issues can be found on each protocol layer in an ad hoc network. At the data link layer power can be saved by reducing control messages which are used to assert neighbor relationships and synchronization purposes. By reducing the amount of control messages sent in MAC protocols, power can be saved but at the expense

   of increased delays [4]. Designing good protocols with few packet collisions reduces power consumption since retransmission of packets requires energy. At the network layer, routing protocols can be designed such that there is an increase in the network lifetime by attempting to distribute the load over multiple different paths. Hence the use of routing metrics that consider the capabilities of the power sources of the network nodes contributes to the efficient utilization of energy and increases the lifetime of the network. The routing protocols that select paths so as to conserve power must be aware of the states at the given node as well as at the other intermediate nodes in the path. In this paper, we have considered the problem of routing in a mobile ad hoc network from energy efficiency point of view. We have simulated ondemand routing protocol (DSR)[6] & power aware routing protocol (MMBCR)[15] [16] and studied their performances in terms of network lifetime for the same network scenario. The rest of the paper is organized as follows: In section 2 we present the related work. Section 3 discusses both the protocols DSR & MMBCR in brief. In section 4 we present the simulation setup, section 5 gives the results and section 6 concludes the paper.

2. RELATED WORK

   I proposed a set of routing metrics in [5], which supports conservation of battery power. In [8], the authors propose a common power protocol (COMPOW) that attempts to satisfy three major objectives- increasing the battery lifetime of the nodes, increasing the traffic carrying capacity of the network and reducing the contention among the nodes. I proved that the COMPOW protocol works well only in a network with a homogeneous distribution of nodes and exists only as a special case of the CLUSTERPOW proposed by them in [9]. CLUSTERPOW is a power control clustering protocol, in which each node runs a distributed algorithm to choose the minimum power p to reach the destination through multiple hops. In [10], the authors have proposed a power optimal scheduling

   and routing protocol which tries to minimize the total average power in the network, subjected to constraints such as peak transmission power of the nodes and achievable data rate per link. In [11] the authors propose a centralized algorithm that calculates the minimum power level for each node that is required to maintain network connectivity based on the global information from all the nodes. [12] discusses the protocols at the TCP layer that take into account the energy reserve while allowing retransmissions.

   In the Fig.1, when the source S wants to send packet to destination D, S has to find the path to D using ERS. The ERS starts searching for the destination by increasing the TTL value and forms the ring structured search as in the Fig.1. For simplicity, initial TTL value has been taken as 1, i.e. the S can send the RREQ to its one hop neighbors and forms the 1st ring. The nodes in the 1st ring does not have any information about destination and so the source again restarts the search with increased broadcast Id and TTL value. The TTL value for the 2nd ring is 3, and some nodes in the 2nd ring have route to the destination. So that nodes will unicasts the Route Reply (RREP) to the source. And when the route to D has not been found out in 2nd search, then the S will rebroadcasts the RREQ using this ring search technique till it finds the route to the destination. The ERS method has the following restrictions. If the destination node is far from the source node, then the source node has to broadcast multiple RREQ messages. Consequently, intermediate nodes have to receive and process this message repeatedly. This leads to more consumption of energy androuting overhead. To overcome this problem, so many methods have been proposed.

3. DESCRIPTION OF ROUTING PROTOCOLS FOR MOBILE AD HOC NETWORKS

   1. Dynamic Source Routing (DSR)

      The key feature of DSR [6] is the use of source routing. That is, the sender knows the complete hop-by hop route to the destination. These routes are stored in a route cache. The data packets carry the source route in the packet header. When a node in the ad hoc network attempts to send a data packet to destination for which it does not already know the route, it uses a route discovery process to dynamically determine such a route. Route discovery works by flooding the network with route request (RREQ) packets. Each node receiving a RREQ rebroadcasts it, unless it is the destination or it has a route to the destination in its route cache. Such a node replies to the RREQ with a route reply (RREP) packet that is routed back to the original source. RREQ and RREP packets are also source routed. The RREQ builds up the path traversed so far. The RREP routes itself backs to the source by traversing this path backwards. The route carried back by the RREP packet is cached at the source for future use. If any link on a source route is broken, the source node is notified using a route error (RERR) packet. The source removes any route using this link from its cache. A new route discovery process must be initiated by the source, if this route is still needed. DSR makes very aggressive use of source routing and route caching.

   2. Minimum Maximum Battery cost Routing (MMBCR)

      The main objective of MMBCR algorithm [15], [16] is to make sure that route selection is done based on the battery capacity of all the individual nodes. MMBCR first finds the node having minimum battery capacity in each of the possible routes and selects the route having maximum value among the selected routes i.e., the route with maximum lifetime is selected. If Ci denotes the battery cost at any instant t, f (Cit) =1/Cit i.e., higher the value of the function fi, the more unwilling the node is to participate in the route selection algorithm. If a route contains N nodes, then the total cost for the route Ri is the sum of the cost functions of all these nodes. The battery cost is defined as Rj = Maxiroutej fi(Cit). Therefore the desired route is given by Ri = Min (Rj, jA) where A is the set containing all possible routes. This algorithm ensures uniform distribution from the batteries. The main advantage of this algorithm is that the metrics used can be directly incorporated in the routing protocol.

   3. AODV routing Protocol:

      In the ERS, the source node will broadcast the RREQ to its

      neighbors to find route. If the neighbor nodes receive it for the first time, it will relay the RREQ. Or else it will just drop the packet. Hence there will be useful information regarding the sender and last hop, dropping the duplicate packets wastes the neighbors information. Therefore we propose a design which helps in utilizing the information before dropping the duplicate RREQ packets to make decision about nodes relay value. This helps in making some nodes silent without forwarding the redundant rebroadcast of the RREQ and thus reduces energy consumption for AODV routing protocol. This improved ERS scheme is named as E2AODV, Energy Efficient AODV. In E2AODV, the state of the node is determined as relaying or being silent by using the Relay Value of each node in the network. Initially the Relay and Forward value of all the nodes is set to be 1, which means that it will relay the RREQ. It is shown in Fig.2. And the Relay and Forward value will be updated based on the TTL value and the P-Addr field in the RREQ packet. The connectivity between nodes in Fig. 2 implies that it can be reachable in one hop that is within the nodes transmission range. The Relay value will be changed based on the

      Figure 2. Initial Relay and Forward Value in E2AODV

4. SIMULATION SETUP

   We have used network simulator (NS-2.34) for our work. NS2 is a discrete event driven simulator [13],[14] developed at the University of Berkeley and the Virtual Inter Network Testbed (VINT). We have used Ubuntu

   11.10 environment. NS2 is suitable for designing new protocols, comparing different protocols and traffic evaluations. It is an object oriented simulation written in C++, with TCL interpreter as a frontend.

5. SIMULATION RESULTS

We have created a network scenario of seven nodes, node 0, 1,2, 3, 4, 5 & 6 with an energy level of 1.5W. Initially node 5 has data to send to node 1, 2 & 3. In the process the energy of node 5 decreases and by the end of transmission i.e., at time 11.04 seconds it reduces to 1.110212W. MMBCR first finds the node having

minimum battery capacity in each of the possible routes and selects the route having the maximum value among the selected routes i.e., the route with maximum lifetime is selected. Node 0 has data to transmit to node

4. There are three routes available to transmit data from 0 to 4. These are 0-5-4, 0-1-6-4 & 0-2-3-4.

MMBCR initiates route discovery process and since it considers the route with maximum lifetime (though 0- 5-4 is the shortest path), MMBCR selects 0-2-3-4 from the route discovery process. As shown in figure1 source node 0 receives the route reply from the destination node 4 via route 0-2-3-4 taking battery lifetime into consideration.

Figure shows the data transmission from node 0 to node 4 via 0-2-3-4 route using MMBCR. At time 59.775073 seconds the energy level of 0, 2 & 3 becomes .146893W, 0W & .13777W respectively and before the link failure takes place source node 0 initiates the route discovery process and transmits the data packets through route 0-1-6-4 thereby increasing the network lifetime as shown in figure

After transmitting certain amount of data, the energy level of node 5 reduces to 0 at time 39.642172 seconds and the link 0-5-4 is no more available. Node 0 initiates the route discovery process and this time it selects route 0-2-3-4 for data transmission. It continues with the data transmission process with the same route until it has data to send and the energy levels of nodes reaches zero or the failure of link 0-2-3-4 occurs. Thus, from the screenshots we observe that DSR does not take into consideration the energy levels of nodes or the lifetime of the network resulting in link failures whereas MMBCR increases the network lifetime by selecting route with maximum battery capacity.

Figure shows the energy level of node 5 at different instances with both DSR & MMBCR protocol for the same network setup.From figure it is clear that energy level of node 5 decreases to 0 at about 39 second for DSR thereby resulting in network failure. As MMBCR selects a route with maximum battery capacity, lifetime of network is more for MMBCR compared to DSR.

1. CONCLUSIONS

   In this paper, we have considered two routing protocols DSR MMBCR and AODV and compared their performances in terms of network using NS2. From the simulations we observed that MMBCR selects the route with nodes containing maximum battery value i.e., the route with maximum lifetime is selected. DSR does not consider the lifetime of the network and chooses the route based on route discovery process. Thus, from the observations we conclude that when network lifetime is considered MMBCR outperforms compare to DSR and AODV. Future work will be on proposing a new energy efficient routing protocol on top of MMBCR thereby increasing the network lifetime and also on MAC Layer in Routing Protocol. Our experimental results justify the necessity of the required features of a minimum energy routing protocol. These features are very generic in nature and can be used as a guideline for designing new minimum energy routing protocols. We have shown that these features can be easily implemented on an existing version of the protocol to derive a minimum energy routing version of the protocol. The minimum energy routing protocol energy consumption is around a factor of three times more than the God energy at low speeds as compared to eight times more in the case of the existing protocol. At higher speeds the ratios are seven and eleven. It is also clear from the results that a minimum energy routing protocol should employ a unified link cache graph data structure to store the routing and power information so that it can converge to the minimum energy route faster with reduced routing overhead.

2. REFERENCES

1. C.F.Chiasserini and R.R.Rao, Energy-Efficient Battery

   Management, Proceedings of IEEE INFOCOM 2000,vol.2, pp-396-403, March 2000.

2. M.Adamou and S.Sarkar, A Framework for Optimal Battery Management for Wireless Nodes, Proceedings of IEEE INFOCOM 2002, pp.1783-1792, June 2002.

3. C.F. Chiasserini and R.R.Rao, Improving Battery Performance by Using Traffic Shaping Techniques, IEEE Journal on Selected Areas of communications, vol.19, no.7, pp.1385-1394, July 2001.

4. S.Jayashree, B.S.Manoj and Shivram Ram Murthy, A Battery Aware MAC Protocol for Ad Hoc Wireless Networks, Technical Report, Department of Computer Science and Engineering, Indian Institute of Technology, Madras, India, October 2003.

5. S.Singh, M.Woo and C.S. Raghavendra, Power Aware Routing in Mobile Ad Hoc Networks, Proceedings of ACM MOBICOM 1998, pp.181-190, October 1998.

6. D.B.Johnson and D.A.Maltz, Dynamic Source Routing in Ad Hoc Wireless Networks, Mobile Computing, Kluwer Academic Publishers, Vol.353, pp.153-181, 1996.

7. C.Siva Ram Murthy and B.S.Manoj, Ad Hoc Wireless Networks Architectures and Protocols, Pearson Education Inc. p.no.642-643.

8. V.Kawadia, S.Narayanaswamy, R.Rozovsky, R.S.Sreenivas and P.R.Kumar, Protocols for Media Control in Wireless Networks, Proceedings of IEEE Conference n Decision and control 2001, Vol 2, pp.1935-1940, December 2001.

9. V.Kawadia and P.R.Kumar, Power Control and Clustering in Ad hoc Networks, Proceedings of IEEE INFOCOM 2003, Vol.1, pp.459-469, April 2003.

10. R.L.Cruz and A.R.Santhanam, Optimal Routing, Link Scheduling and Power control in Multi-Hop Wireless Networks, Proceedings of INFOCOM 2003.

11. M. Sanchez, P.Manzoni and Z.J.Haas, Determination of Critical Transmission Range in Ad Hoc Networks, Proceedings of MMT 1999, October 1999.

12. K.Lahiri, A. Raghunathan, S.Dey and D.Panigrahi,

    Battery-Driven System design: A New frontier in Low-Power Design, Proceedings of ASP- DAC/VLSInDesign 2002, pp.261-267, January 2002.

13. UCB/LBNL/VINT Network Simulator http://www.mash.cs.berkeley.edu/ns/referred on March 2010.

14. The Network Simulatorns-2, available at http://www.isi.edu/nsnam/ns/referred on march 2010.

15. S. Singh, M. Woo, and C. S. Raghavendra, Power-Aware Routing in Mobile Ad Hoc Networks, In Proc. of the International Conference on Mobile Computing and Networking, pages 181190, 1998.

16. C-K. Toh, Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad hoc Networks, IEEE Communications Magazine, Vol. 39, No.6, pp. 138-147, June 2001.

17. Cisco Systems, Cisco Aironet 350 Series Client Adapter Data Sheets 64 Mobile Computing and Communications Review, Volume 6, Number 3

18. Broch, J., Maltz, D., et al. A performance comparison of multi-hop wireless ad hoc network routing protocols, Proc. of MOBICOM, 1998,

    pp. 8597.

19. Brown, T.X, Doshi, S., Zhang, Q., Optimal

    power aware routing in a wireless ad hoc network, IEEE LANMAN 2001 Workshop Proceedings, pp. 102 105.

20. Brown, T.X, Zhang, Q., Gabow, H., Maximum Flow Life Curve for a Wireless Ad Hoc Network,

    MOBIHOC 2001

21. Chang, J., Tassiluas, L., Energy Conserving Routing in Wireless Ad-Hoc Networks, Proceedings of IEEE INFOCOM 2000, pp. 22-31,

    2000.

22. Chen, B., Jamieson, K., Balakrishnan, H., Morris, R., Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad HocWireless Networks, Proceedings of MOBICOM 2001, 2001.

23. Fall, K., Varadhan, K., The ns Manual,(formerly ns Notes and Documentation), The VINT Project: A collaboration between researchers at UC Berkeley, LBL, USC/ISI and Xerox PARC