Minimum energy paths for reliable communication in multi-hop wireless networks

ABSTRACT

Current algorithms for minimum-energy routing in wireless networks typically select minimum-cost multi-hop paths. In scenarios where the transmission power is fixed, each link has the same cost and the minimum-hop path is selected. In situations where the transmission power can be varied with the distance of the link, the link cost is higher for longer hops; the energy-aware routing algorithms select a path with a large number of small-distance hops. In this paper, we argue that such a formulation based solely on the energy spent in a single transmission is misleading --- the proper metric should include the total energy (including that expended for any retransmissions necessary) spent in reliably delivering the packet to its final destination.We first study how link error rates affect this retransmission-aware metric, and how it leads to an efficient choice between a path with a large number of short-distance hops and another with a smaller number of large-distance hops. Such studies motivate the definition of a link cost that is a function of both the energy required for a single transmission attempt across the link and the link error rate. This cost function captures the cumulative energy expended in reliable data transfer, for both reliable and unreliable link layers. Finally, through detailed simulations, we show that our schemes can lead to upto 30-70% energy savings over best known current schemes, under realistic environments.

REFERENCES

• 1: J.-H. Chang and L. Tassiulas. Energy conserving routing in wireless ad-hoc networks. In Proceedings of Infocom, Mar. 2000.
• 2: S. Corson, S. Papademetriou, P. Papadopoulos, V. Park, and A. Qayyum. An Internet MANET encapsulation protocol (IMEP) specification, draft-ietf-manet-imep-spec02. txt. IETF, Aug. 1999.
• 3: Sally Floyd, Connections with multiple congested gateways in packet-switched networks part 1: one-way traffic, ACM SIGCOMM Computer Communication Review, v.21 n.5, p.30-47, Oct. 1991 [doi>10.1145/122431.122434]
• 4: John H. Gass, Jr. , Michael B. Pursley , Harlan B. Russell , Jeffrey S. Wysocarski, An adaptive-transmission protocol for frequency-hop wireless communication networks, Wireless Networks, v.7 n.5, p.487-495, September 2001 [doi>10.1023/A:1016722610259]
• 5: J. Gomez and A. Campbell. Power-aware routing optimization for wireless ad hoc networks. In High Speed Networks Workshop (HSN), June 2001.
• 6: J. Gomez-Castellanos, A. Campbell, M. Naghshineh, and C. Bisdikian. PARO: A power-aware routing optimization scheme for mobile ad hoc networks, draft-gomez-paro-manet-00.txt, work in progress. IETF, Mar. 2001.
• 7: D. Johnson and D. Maltz. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, pages 153--181, 1996.
• 8: T. V. Lakshman , B. Suter , U. Madhow, Window-Based Error Recovery and Flow Control with a Slow Acknowledgement Channel: A Study of TCP/IP Performance, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1199, April 09-11, 1997
• 9: G. Malkin. RIP version 2, RFC 2453. IETF, Nov. 1998.
• 10: Matthew Mathis , Jeffrey Semke , Jamshid Mahdavi, The macroscopic behavior of the TCP congestion avoidance algorithm, ACM SIGCOMM Computer Communication Review, v.27 n.3, p.67-82, July 1997 [doi>10.1145/263932.264023]
• 11: J. Moy. OSPF version 2, RFC 2328. IETF, Apr. 1998.
• 12: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 13: K. Scott and N. Bamboos. Routing and channel assignment for low power transmission in PCS. In Proceedings of ICUPC, Oct. 1996.
• 14: Suresh Singh , C. S. Raghavendra, PAMAS—power aware multi-access protocol with signalling for ad hoc networks, ACM SIGCOMM Computer Communication Review, v.28 n.3, p.5-26, July 1998 [doi>10.1145/293927.293928]
• 15: Suresh Singh , Mike Woo , C. S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.181-190, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288286]
• 16: C. Toh, H. Cobb, and D. Scott. Performance evaluation of battery-life-aware routing schemes for wireless ad hoc networks. In Proceedings of ICC, June 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
ad-hoc networks, energy efficiency, routing