Seminar Room 1, Newton Institute
AbstractSuppose we have a collection of sensors in a large region, each of which can detect events within a disk of radius 1. We wish to devise a schedule so that each sensor can sleep for much of the time, while making sure that the whole region is covered by the sensors that are awake. A natural way of doing this is to partition the sensors into k subsets, each subset of sensors covering the whole region. Then in time slot t we activate all the sensors in subset (t mod k). If this is possible we say the sensors are k-partitionable. An obvious necessary condition is that each point in the region is covered by at least k sensors (k-coverage), but this is not in general sufficient. We show that for random deployments of sensors k-coverage usually implies k-partitionability, and identify the most likely obstructions to k-partitionability when this fails. This leads to some natural unsolved problems involving k-partitionability of (deterministic) configurations of disks. Joint work with B. Bollobas, A. Sarkar, and M. Walters.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.