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

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.


Last updated on 26 Mar 2007 by Teija Kujala - Page created on 23 Mar 2007 by Teija Kujala