Benjie Chen,
Kyle Jamieson,
Hari Balakrishnan,
Robert Morris

Proc. of the 6th ACM MOBICOM Conf., Rome, Italy, July 2001.

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 both communication latency and capacity without much reduction in system lifetime.

[PostScript (392KB)] [Gzipped PostScript (105KB)] [PDF (245KB)]