A Distributed Algorithm for Approximate Mobile Sensor Coverage

We consider the problem of covering a domain by mobile sensors and the design of an efficient schedule that re-duces unnecessary sensor overlap and energy consump-tion. The problem is motivated by emerging partici-patory sensing applications as well as other coverage problems involving mobile nodes. The problem of mini-mizing the total energy consumption while maintaining the same level of coverage guarantee is NP-hard. We develop distributed algorithms achieving a constant ap-proximation factor when sensors have unit disk sens-ing ranges, and a (1 + ") approximation factor when the sensors also have constant bounded density. For all these algorithms the communication cost is asymptot-ically bounded by the cost of simply maintaining the direct neighborhood of each sensor. The constant ap-proximation distributed algorithm can be generalized for the k-coverage problem, when each point of interest has to be covered by at least k sensors.