General maximal lifetime sensor-target surveillance problem and its solution

Hai Liu*, Xiaowen Chu, Yiu Wing Leung, Xiaohua Jia, Peng Jun Wan

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

10 Citations (Scopus)


We address a new and general maximal lifetime problem in sensor-target surveillance. We assume that each sensor can watch at most k targets (k ≥ 1) and each target should be watched by h sensors (h ≥ 1) at any time. The problem is to schedule sensors to watch targets and forward the sensed data to a base station such that the lifetime of the surveillance network is maximized. This general problem includes the existing ones as its special cases (k = 1 and h = 1 in [12] and k = 1 and h ≥ 2 in [13]). It is also important in practice because some sensors can monitor multiple or all targets within their surveillance ranges and multisensor fusion (i.e., watching a target by multiple sensors) gives better surveillance results. The problem involves several subproblems and one of them is a new matching problem called (k, h)-matching. The (k, h)-matching problem is a generalized version of the classic bipartite matching problem (when k = h = 1, (k, h)-matching becomes bipartite matching). We design an efficient (k, h)-matching algorithm to solve the (k, h)-matching problem and then solve the general maximal lifetime problem. As a byproduct of this study, the (k, h)-matching problem and the proposed (k, h)-matching algorithm can potentially be applied to other problems in computer science and operations research.

Original languageEnglish
Article number5703082
Pages (from-to)1757-1765
Number of pages9
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number10
Publication statusPublished - Oct 2011

Scopus Subject Areas

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

User-Defined Keywords

  • matching
  • maximal lifetime
  • routing
  • scheduling
  • Wireless sensor networks


Dive into the research topics of 'General maximal lifetime sensor-target surveillance problem and its solution'. Together they form a unique fingerprint.

Cite this