General maximal lifetime sensor-target surveillance problem and its solution

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

9 Scopus Citations
View graph of relations

Author(s)

  • Hai Liu
  • Xiaowen Chu
  • Yiu-Wing Leung
  • Xiaohua Jia
  • Peng-Jun Wan

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number5703082
Pages (from-to)1757-1765
Journal / PublicationIEEE Transactions on Parallel and Distributed Systems
Volume22
Issue number10
Publication statusPublished - 2011

Abstract

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. © 2011 IEEE.

Research Area(s)

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

Citation Format(s)

General maximal lifetime sensor-target surveillance problem and its solution. / Liu, Hai; Chu, Xiaowen; Leung, Yiu-Wing; Jia, Xiaohua; Wan, Peng-Jun.

In: IEEE Transactions on Parallel and Distributed Systems, Vol. 22, No. 10, 5703082, 2011, p. 1757-1765.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal