Recently, the problem of scheduling mobile sensors to cover all targets and maintain network connectivity such that the total movement 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.
Bibliographical noteFunding Information:
Manuscript received September 6, 2017; revised April 14, 2018; accepted April 16, 2018. Date of publication May 9, 2018; date of current version May 31, 2019. This work was supported by the Ministry of Science and Technology under Grant MOST 106-2221-E-151-001. (Corresponding author: Bing-Hong Liu.) N.-T. Nguyen is with the Department of Computer Science and Engineering, University of Minnesota, Twin Cities, Minneapolis, MN 55455 USA (e-mail:, email@example.com).
- Mobile wireless sensor network (MWSN)
- network connectivity
- polynomial-time reduction
- target coverage (TCOV)