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 sharedchannel wireless network has 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. 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. Additionally, Span also improves communication latency and capacity.

References

1. J. Broch, D. Johnson and D. Maltz, The dynamic source routing protocol for mobile ad hoc networks, Internet draft, IETF Mobile Ad Hoc Networking Working Group (December 1998).
2. J. Broch, D. Maltz, D. Johnson, Y. Hu and J. Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, in: Proceedings of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), Dallas, TX (August 1998).
3. J. Chang and L. Tassiulas, Energy conserving routing in wireless ad hoc networks, in: Proceedings of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Network (MobiCom), Dallas, TX (August 1998).
4. G. Chesson, XTP/protocol engine design, in: Proceedings of the IFIP WG6.1/6.4 Workshop, Rüschlikon (May 1989).
5. CMU Monarch extensions to ns, http://www.monarch.cs.cmu.edu/
6. B. Das and V. Bharghavan, Routing in ad-hoc networks using minimum connected dominating sets, in: Proceedings of the IEEE International Conference on Communications (ICC'97) (June 1997).
7. L. Feeney and M. Nilsson, Investigating the energy consumption of a wireless network interface in an ad hoc networking environment, in: Proceedings of IEEE INFOCOM, Anchorage, AK (2001).
8. W. Fenner, Internet Group Management Protocol, Version 2, RFC-2236 (November 1997).
9. S. Floyd, V. Jacobson, S. McCanne, C.G. Liu and L. Zhang, A reliable multicast framework for lightweight sessions and application level framing, in: Proceedings of the ACM SIGCOMM, Boston, MA (September 1995) pp. 342-356.
10. W.R. Heinzelman, A. Chandrakasan and H. Balakrishnan, Energy-efficient communication protocols for wireless microsensor networks, in: Proceedings of the Hawaaian International Conference on Systems Science (January 2000).
11. IEEE, Wireless LAN Medium Access Control and Physical Layer specifications, IEEE 802.11 Standard, IEEE Computer Society LAN MAN Standards Committee (August 1999).
12. C. Intanagonwiwat, R. Govindan and D. Estrin, Directed diffusion: A scalable and robust communication paradigm for sensor networks, in: Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), Boston, MA (August 2000).
13. B. Karp and H.T. Kung, GPSR: Greedy Perimeter Stateless Routing for wireless networks, in: Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), Boston, MA (August 2000).
14. R. Kravets and P. Krishnan, Application-driven power management for mobile communication, in: Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), Dallas, TX (October 1998).
15. J. Li, J. Jannotti, D.D. Couto, D. Karger and R. Morris, A scalable location service for geographic ad-hoc routing, in: Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom) (August 2000).
16. W. Mangione-Smith, P.S. Ghang, S. Nazareth, P. Lettieri, W. Boring and R. Jain, A low power architecture for wireless multimedia systems: Lessons learned from building a power hog, in: 1996 International Symposium on Low Power Electronics and Design Digest of Technical Papers, Monterey, CA (August 1996).
17. ns notes and documentation (2000) http://www.isi.edu/vint/nsnam/
18. C. Raghavendra and S. Singh, PAMAS: Power Aware Multi-Access Protocol with Signaling for ad hoc networks, ACM Computer Communication Review (July 1998) 5-26.
19. R. Ramanathan and R. Rosales-Hain, Topology control of multi-hop wireless networks using transmit power adjustment, in: Proceedings of IEEE INFOCOM, Tel Aviv, Israel (March 2000).
20. V. Rodoplu and T.H. Meng, Minimum energy mobile wireless networks, in: Proceedings of the IEEE International Conference on Communications (ICC), Vol. 3, Atlanta, GA (June 1998) pp. 1633-1639.
21. C. Rohl, H. Woesner and A. Wolisz, 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 (March 1997).
22. T. Shepard, A channel access scheme for large dense packet radio networks, in: Proceedings of the ACM SIGCOMM, Stanford University, CA (August 1996) pp. 219-230.
23. S. Singh, M. Woo and C.S. Raghavendra, Power-aware routing in mobile ad hoc networks, in: Proceedings of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), Dallas, TX (1998).
24. M. Stemm and R. Katz, 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).
25. R. Wattenhofer, L. Li, P. Bahl and Y.-M. Wang, Distributed topology control for power efficient operation in multihop wireless ad hoc networks, in: Proceedings of IEEE INFOCOM, Anchorage, AK (2001).
26. J. Wu and M. Gao, On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks, in: Proceedings of the 30th Annual International Conference on Parallel Processing, Valencia, Spain (September 2001).
27. J. Wu and H. Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, in: Proceedings of the Third International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Seattle, WA (August 1999).
28. Y. Xu, J. Heidemann and D. Estrin, Adaptive energy-conserving routing for multihop ad hoc networks, Technical report 527, USC/ISI (October 2000).
29. Y. Xu, J. Heidemann and D. Estrin, Geography-informed energy conservation for ad hoc routing, in: Proceedings of the Seventh Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), Rome, Italy (July 2001) pp. 70-84.

Index Terms

• Networks

  • Network properties

    • Network structure

  • Network types

    • Mobile networks

    • Wireless access networks