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].
Chen, Jianer ;
Jiang, Anxiao Andrew ;
Kanj, Iyad A. ;
Xia, Ge ;
Zhang, Fenghui .
WIRELESS NETWORKS, 2011, 17 (01) :53-67
[2]
Garey M. R., 1990, COMPUTERS INTRACTABI
[3]
APPROXIMATION SCHEMES FOR COVERING AND PACKING PROBLEMS IN IMAGE-PROCESSING AND VLSI [J].
HOCHBAUM, DS ;
MAASS, W .
JOURNAL OF THE ACM, 1985, 32 (01) :130-136
[4]
On Using Cooperative Routing for Lifetime Optimization of Multi-Hop Wireless Sensor Networks: Analysis and Guidelines [J].
Jung, Jin Woo ;
Weitnauer, Mary Ann .
IEEE TRANSACTIONS ON COMMUNICATIONS, 2013, 61 (08) :3413-3423
[5]
Karp RM, 1972, COMPLEXITY COMPUTER, P85
[6]
Li J, 2012, IEEE GLOB COMM CONF, P5350, DOI 10.1109/GLOCOM.2012.6503971
[7]
Minimizing Movement for Target Coverage and Network Connectivity in Mobile Sensor Networks [J].
Liao, Zhuofan ;
Wang, Jianxin ;
Zhang, Shigeng ;
Cao, Jiannong ;
Min, Geyong .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2015, 26 (07) :1971-1983
[8]
Novel methods for energy charging and data collection in wireless rechargeable sensor networks [J].
Liu, Bing-Hong ;
Ngoc-Tu Nguyen ;
Van-Trung Pham ;
Lin, Yue-Xian .
INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, 2017, 30 (05)
[9]
Distributed 3D Dynamic Search Coverage for Mobile Wireless Sensor Networks [J].
Nazarzehi, Vali ;
Savkin, Andrey V. ;
Baranzadeh, Ahmad .
IEEE COMMUNICATIONS LETTERS, 2015, 19 (04) :633-636
[10]
Nguyen N.-T., 2018, P IEEE 42 C LOC COMP, P471