The Mobile Sensor Deployment Problem and the Target Coverage Problem in Mobile Wireless Sensor Networks are NP-Hard

被引：113

作者：

Ngoc-Tu Nguyen ^{[1
]}

Bing-Hong Liu ^{[2
]}

机构：

[1] Univ Minnesota, Dept Comp Sci & Engn, Minneapolis, MN 55455 USA

[2] Natl Kaohsiung Univ Sci & Technol, Dept Elect Engn, Kaohsiung 80778, Taiwan

来源：

IEEE SYSTEMS JOURNAL | 2019年 / 13卷 / 02期

关键词：

Mobile wireless sensor network (MWSN); network connectivity; NP-hard; polynomial-time reduction; target coverage (TCOV); CONNECTIVITY; MOVEMENT;

D O I：

10.1109/JSYST.2018.2828879

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

080201 [机械制造及其自动化];

摘要：

Recently, the problem of scheduling mobile sensors to cover all targets andmaintain network connectivity such that the totalmovement distance is minimized, termed the mobile sensor deployment (MSD) problem, has received a great deal of attention. However, the complexity of the MSD problem remains unknown because no exact proof has been provided before. In this paper, we show that not only the MSD problem, but also its special case, termed the target coverage problem, are NP-hard.

引用

页码：1312 / 1315

页数：4

共 14 条

[1]

Separability and topology control of quasi unit disk graphs [J].