TY - JOUR

T1 - General maximal lifetime sensor-target surveillance problem and its solution

AU - Liu, Hai

AU - Chu, Xiaowen

AU - Leung, Yiu Wing

AU - Jia, Xiaohua

AU - Wan, Peng Jun

N1 - Funding Information:
This work is supported in part by grant from Research Grants of Hong Kong [Project No. HKBU211009], and NSF China Grants No. 60633020 and No. 60970117. Peng-Jun Wan is supported in part by the US National Science Foundation (NSF) under grants CNS-0831831 and CNS-0916666.

PY - 2011/10

Y1 - 2011/10

N2 - 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.

AB - 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.

KW - matching

KW - maximal lifetime

KW - routing

KW - scheduling

KW - Wireless sensor networks

UR - http://www.scopus.com/inward/record.url?scp=80052324615&partnerID=8YFLogxK

U2 - 10.1109/TPDS.2011.42

DO - 10.1109/TPDS.2011.42

M3 - Journal article

AN - SCOPUS:80052324615

SN - 1045-9219

VL - 22

SP - 1757

EP - 1765

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

IS - 10

M1 - 5703082

ER -