Minimum-Cost Sensor Placement for Required Lifetime in Wireless Sensor-Target Surveillance Networks

In sensor-target surveillance networks, sensors are typically powered by batteries with limited energy and hence it is important to manage the energy usage. In the literature, several methods have been proposed to maximize the lifetime of these networks. We observe that some surveillance applications have lifetime requirements. For example, a surveillance network is used to monitor the precious items in an exhibition and its lifetime must be at least equal to the duration of exhibition. For these surveillance applications, it is desirable to minimize the network cost while fulfilling the given lifetime requirement. In this paper, we address a new problem in which the network cost is minimized while the resulting lifetime is at least equal to a given value L. To minimize the network cost, we place the minimum number of sensors such that all the given targets can be monitored for a duration of at least L and all the sensed data can be forwarded to a given base station. We prove that this problem is NP-hard and derive a lower bound on the minimum number of sensors required. We design an efficient approximation algorithm for this problem. Theoretically, we prove that this approximation algorithm has an approximation ratio of max {2l - m + 2, 3}, where m is the number of targets and l is the number of targets in a small disk centered at the base station with a constant radius. Experimentally, we conduct computer simulation to demonstrate that this approximation algorithm gives close-to-optimal solutions.