23.3.2007 HIIT seminar

HIIT seminars in spring 2007 will be held in hall **B222** of Exactum,
on Fridays starting at 10:15 a.m. Coffee available from 10.

Fri Mar 23
Jukka Suomela
A distributed approximation scheme for sleep scheduling in sensor networks

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 $\epsilon>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+\epsilon$. The total computational effort (time, memory and communication) required at each node depends on $\epsilon$ 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 remains constant as the size of the network is scaled up.

This is joint work work with Patrik Floréen, Petteri Kaski and Topi Musto.