Indexed by:
Abstract:
Emerging IoT applications have brought up new coverage problems with sink-based mobile sensors. In this paper, we first focus on the MinSum Sink-based Line Barrier Coverage (SLBC) problem of covering a line barrier with mobile sensors originated at sink stations distributed on the plane. The objective is to minimize the movement sum of the sensors for the sake of energy efficiency. When the sinks emit sensors with non -uniform radii, we prove the MinSum SLBC problem is AT -complete via reducing from the Partition problem that is known ArPcomplete. Then for the MinSum Sink -based on -a -Line Target Coverage (SLTC) problem of covering targets on a line, an exact algorithm is presented based on grouping the targets and transforming to the shortest path problem in the auxiliary graph induced by the vertices corresponding to the groups. The algorithm runs in time 0 (n2) when sinks emit sensors of uniform sensing radius, and in time 0 (I42122) for sensors of non-uniform radii, where n and R are respectively the number of targets and different radii. Eventually for SLBC, we propose a pseudo additive fully polynomial -time approximation scheme by extending the algorithm for SLTC. The algorithm runs in 0 (k2 (E) 2) time and computes a coverage with total movement provably bounded by opt+ for any fixed sufficiently small > 0, where opt, k and L are respectively the movement of an optimum solution, the number of sinks and the length of the barrier. At last, experiments are carried out to demonstrate the practical performance gain of our algorithms.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
2021 IEEE 41ST INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS (ICDCS 2021)
ISSN: 1063-6927
Year: 2021
Page: 696-706
Language: English
Cited Count:
WoS CC Cited Count: 8
SCOPUS Cited Count: 9
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: