Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks

B. Chen, K. Jamieson, H. Balakrishnan, R. Morris

Research output: Contribution to conferencePaperpeer-review

931 Scopus citations

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 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, 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.

Original languageEnglish (US)
Pages85-96
Number of pages12
StatePublished - Jan 1 2001
Externally publishedYes
Event7th Annual International Conference on Mobile Computing and Networking - Rome, Italy
Duration: Jul 16 2001Jul 21 2001

Other

Other7th Annual International Conference on Mobile Computing and Networking
Country/TerritoryItaly
CityRome
Period7/16/017/21/01

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks'. Together they form a unique fingerprint.

Cite this