A fast localized algorithm for scheduling sensors

Given n sensors and m targets, a monitoring schedule is a partition of the sensor set such that each subset of the partition can monitor all the targets. Monitoring schedules are used for maximizing the time all the targets are monitored when there is no possibility of replacing the batteries of the sensors. Each subset of the partition is used for one unit of time, and thus the goal is to maximize the number of subsets in the partition. We make the assumption that any two sensors for which there is a target both can monitor can communicate in one hop.The Monitoring Schedule problem is closely related to the domatic number in graphs and from previous work one can obtain a logarithmic approximation with one round of communication. We consider the special case when the targets are on a curve (such as a road) and each sensor can monitor an interval of the curve. For this case an optimum schedule can be computed in centralized manner. However, in the worst case a localized algorithm requires a linear number of communication rounds to compute a solution which is better than a 2-approximation. We present a (2+ε)-approximate randomized localized algorithm with polylogarithmic number of communication rounds.