The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Sentry Selection

Balister, PN (University of Memphis)
Monday 17 May 2010, 16:00-17:00

Seminar Room 1, Newton Institute


Suppose 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.


[pdf ]


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧