Chennai Mathematical Institute


Algorithms for sensor cover
Kasturi Varadarajan
University of Iowa.


In the sensor cover problem, we are given a set X of points, and a set S of sensors. Each sensor s in S is associated with a range R_s which is a subset of X, and a duration d_s which is a positive integer. The sensor s is said to be *live* at each x in R_s. A schedule is an assignment of a start time t_s (a positive integer) to each s in S. Sensor s is *active* at times t_s, t_s + 1, ... , t_s + d_s -1. The duration of the schedule is the maximum L >= 1 such that for each point x, at each time t between 1 and L, some sensor that is live at x is active at t. The sensor cover problem is to compute a schedule of maximum duration.

We will describe some algorithms for this problem and for some interesting cases.