Maximum Target Coverage Problem in Mobile Wireless Sensor Networks

Sensors

Hong Shen¹  Lin Chen¹  Dieyan Liang¹ 

[1] School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510006, China;

关键词: approximation algorithm;    Integer programming;    Mobile sensors;    Target coverage;    Wireless sensor network;   

DOI  :  10.3390/s21010184

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown