Patrik Floréen · Petteri Kaski · Jukka Suomela

A distributed approximation scheme for sleep scheduling in sensor networks

SECON 2007 · 4th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, San Diego, CA, USA, June 2007 · doi:10.1109/SAHCN.2007.4292827

authors’ version publisher’s version

Abstract

We investigate the theoretical feasibility of near-optimal, distributed sleep scheduling in energy-constrained sensor networks with pairwise sensor redundancy. In this setting, an optimal sleep schedule is equivalent to an optimal fractional domatic partition of the associated redundancy graph. We present a set of realistic assumptions on the structure of the communication and redundancy relations; for the family of networks meeting these assumptions, we develop an efficient distributed approximation scheme for sleep scheduling. For any ε ≥ 0, we demonstrate that it is possible to schedule the sensing activities of the nodes in a local and distributed manner so that the ratio of the optimum lifetime to the achieved lifetime of the network is at most 1+ε. The computational effort (time, memory and communication) required at each node depends on ε and the parameters of the network family, but given so-called anchor nodes (a set of nodes meeting certain density constraints) and locally unique node identifiers, the effort is independent of the actual network at hand; in particular, the required effort at each node remains constant as the size of the network is scaled up.

Publication

2007 4th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, pages 152–161, IEEE, Piscataway, 2007

ISBN 1-4244-1268-4

Links

© IEEE 2007

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.