Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks

摘要

In this paper, we consider the wireless sensor network in which the power of each sensor is adjustable. Given a set of sensors and a set of targets, we study a problem of minimizing the total power such that the coverage of targets meets partial multi-cover requirement, that is, there are at least a given number of targets each covered by a given number of sensors (this number is called the covering requirement for the target). This is called the minimum power partial multi-cover problem (MinPowerPMC) in a wireless sensor network. Under the assumption that the covering requirements for all targets are upper bounded by a constant, we design the first PTAS for the MinPowerPMC problem, that is, for any epsilon 0, a polynomial-time (1 + epsilon)-approximation.