Minimum-cost sensor placement for required lifetime in wireless sensor-target surveillance networks

Hai Liu, Xiaowen Chu, Yiu Wing Leung, Rui Du

Research output: Contribution to journalJournal articlepeer-review

31 Citations (Scopus)


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.

Original languageEnglish
Article number6297972
Pages (from-to)1783-1796
Number of pages14
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number9
Publication statusPublished - Sept 2013

Scopus Subject Areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

User-Defined Keywords

  • Network optimization
  • Sensor placement
  • Sensor-target surveillance
  • Wireless sensor networks


Dive into the research topics of 'Minimum-cost sensor placement for required lifetime in wireless sensor-target surveillance networks'. Together they form a unique fingerprint.

Cite this