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

Original language | English |
---|---|

Article number | 5703082 |

Pages (from-to) | 1757-1765 |

Number of pages | 9 |

Journal | IEEE Transactions on Parallel and Distributed Systems |

Volume | 22 |

Issue number | 10 |

DOIs | |

Publication status | Published - 2011 |

## Scopus Subject Areas

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

## User-Defined Keywords

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