Journal
SENSORS
Volume 21, Issue 1, Pages -Publisher
MDPI
DOI: 10.3390/s21010184
Keywords
approximation algorithm; integer programming; mobile sensors; target coverage; wireless sensor network
Funding
- National Key R&D Program of China [2017YFB0203201]
- Key-Area Research and Development Plan of Guangdong Province [2020B010164003]
Ask authors/readers for more resources
This study formulates and analyzes a generic coverage optimization problem in mobile sensor networks, proving its NP-hardness and devising four heuristic or approximate algorithms to solve it. Experimental results validate the effectiveness of these algorithms in various parameter settings.
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 Delta(-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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available