Span: An energy-efficient coordination algorithm for topology maintenance in Ad Hoc wireless networks

ABSTRACT

This paper presents Span, a power saving technique for multi-hop ad hoc wireless networks that reduces energy consumption without significantly diminishing the capacity or connectivity of the network. Span builds on the observation that when a region of a shared-channel wireless network bag a sufficient density of nodes, only a small number of them need be on at any time to forward traffic for active connections.

Span is a distributed, randomized algorithm where nodes make local decisions on whether to sleep, or to join a forwarding backbone as a coordinator. Each node bases its decision on an estimate of how many of its neighbors will benefit from it being awake, and the amount of energy available to it. We give a randomized algorithm where coordinators rotate with time, demonstrating how localized node decisions lead to a connected, capacity-preserving global topology.

Improvement in system lifetime due to Span increases as the ratio of idle-to-sleep energy consumption increases, and increases as the density of the network increases. For example, our simulations show that with a practical energy model, system lifetime of an 802.11 network in power saving mode with Span is a factor of two better than without. Span integrates nicely with 802.11—when run in conjunction with the 802.11 power saving mode, Span improves communication latency, capacity, and system lifetime.

REFERENCES

• 1: Wireless LAN Medium Access Control and Physical Layer Specifications, Aug. 1999. IEEE 802.11 Standard (IEEE Computer Society LAN MAN Standards Committee).
• 2: Broch, J., Johnson, D., and Maltz, D. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks. In Internet draft, IETF Mobile Ad Hoc Networking Working Group (Dec. 1998).
• 3: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 4: Chang, J., and Tassiulas, L. Energy Conserving Routing in Wireless Ad Hoc Networks. In Proceedings of IEEE INFOCOM (Tel Aviv, Israel, 2000).
• 5: Chesson, G. XTP/protocol engine design. In Proceedings of the IFIP WG6.1/6.4 Workshop (R. uschlikon, May 1989).
• 6: Feeney, L., and Nilsson, M. Investigating the Energy Consumption of a Wireless Network Interface in an Ad Hoc Networking Environment. In Proceedings of IEEE INFOCOM (Anchorage, AK, 2001).
• 7: Fenner, W. Internet Group Management Protocol, Version 2, Nov 1997. RFC-2236.
• 8: Finn, G. G. Routing and Addressing Problems in Large Metropolitan-scale Internetworks. ISI/RR-87-180, ISI, Mar. 1987.
• 9: Sally Floyd , Van Jacobson , Steve McCanne , Ching-Gung Liu , Lixia Zhang, A reliable multicast framework for light-weight sessions and application level framing, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.342-356, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 10: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 11: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 12: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 13: Robin Kravets , P. Krishnan, Power management techniques for mobile communication, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.157-168, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288276]
• 14: Jinyang Li , John Jannotti , Douglas S. J. De Couto , David R. Karger , Robert Morris, A scalable location service for geographic ad hoc routing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.120-130, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345931]
• 15: W. Mangione-Smith , P. Ghang , S. Nazareth , P. Lettieri , W. Boring , R. Jain, A low power architecture for wireless multimedia systems: lessons learned from building a power hog, Proceedings of the 1996 international symposium on Low power electronics and design, p.23-28, August 12-14, 1996, Monterey, California, United States
• 16: CMU Monarch Extensions to ns. http://www.monarch.cs.cmu.edu/.
• 17: ns Notes and Documentation. http://www.isi.edu/vint/nsnam/, 2000.
• 18: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 19: 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]
• 20: Ramanathan, R., and Rosales-Hain, R. Topology Control of Multi-hop Wireless Networks Using Transmit Power Adjustment. In Proceedings of IEEE INFOCOM (Tel Aviv, Israel, March 2000).
• 21: Rodoplu, V., and Meng, T. H. Minimum Energy Mobile Wireless Networks. In Proceedings of the IEEE International Conference on Communications (ICC) (Atlanta, GA, June 1998), vol. 3, pp. 1633-1639.
• 22: Rohl, C., Woesner, H., and Wolisz, A. A Short Look on Power Saving Mechanisms in the Wireless LAN Standard Draft IEEE 802.11. In Proceedings of the the 6th WINLAB Workshop on Third Generation Wireless Systems (New Brunswick, NJ, Mar. 1997).
• 23: Timothy J. Shepard, A channel access scheme for large dense packet radio networks, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.219-230, August 28-30, 1996, Palo Alto, California, United States
• 24: 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]
• 25: Stemm, M., and Katz, R. Reducing Power Consumption of Network Interfaces in Hand-held Devices. In Proceedings of the Third Workshop on Mobile Multimedia Communications (MoMuC-3) (Princeton, NJ, 1996).
• 26: Wattenhofer, R., Li, L., Bahl, P., and Wang, Y.-M. Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks. In Proceedings of IEEE INFOCOM (Anchorage, AK, 2001).
• 27: Xu, Y., Heidemann, J., and Estrin, D. Adaptive Energy-Conserving Routing for Multihop Ad Hoc Networks. Tech. Rep. 527, USC/ISI, Oct. 2000.
• 28: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Cellular architecture (e.g., mobile)
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design, Experimentation, Performance