Maximum target coverage problem in mobile wireless sensor networks

Dieyan Liang, Hong Shen, Lin Chen

Research output: Contribution to journalArticlepeer-review

24 Citations (Scopus)

Abstract

We formulate and analyze a generic coverage optimization problem arising in wireless sensor networks with sensors of limited mobility. Given a set of targets to be covered and a set of mobile sensors, we seek a sensor dispatch algorithm maximizing the covered targets under the constraint that the maximal moving distance for each sensor is upper-bounded by a given threshold. We prove that the problem is NP-hard. Given its hardness, we devise four algorithms to solve it heuristically or approximately. Among the approximate algorithms, we first develop randomized (1 − 1/e)−optimal algorithm. We then employ a derandomization technique to devise a deterministic (1 − 1/e)−approximation algorithm. We also design a deterministic approximation algorithm with nearly △−1 approximation ratio by using a colouring technique, where △ denotes the maximal number of subsets covering the same target. Experiments are also conducted to validate the effectiveness of the algorithms in a variety of parameter settings.

Original languageEnglish
Article number184
Pages (from-to)1-13
Number of pages13
JournalSensors
Volume21
Issue number1
DOIs
Publication statusPublished - 1 Jan 2021
Externally publishedYes

Keywords

  • Approximation algorithm
  • Integer programming
  • Mobile sensors
  • Target coverage
  • Wireless sensor network

Fingerprint

Dive into the research topics of 'Maximum target coverage problem in mobile wireless sensor networks'. Together they form a unique fingerprint.

Cite this