Algorithm

Cartography

Computer science

Sink (geography)

Mathematics

Geography

Combinatorics

Topology (electrical circuits)

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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{NP}$</tex> -complete via reducing from the Partition problem that is known <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{NP}$</tex> - complete. 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(n^{2})$</tex> when sinks emit sensors of uniform sensing radius, and in time <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\vert R\vert ^{2}n^{2})$</tex> for sensors of non-uniform radii, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\vert R\vert$</tex> 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(k^{2}(\frac{L}{\epsilon})^{2})$</tex> time and computes a coverage with total movement provably bounded by <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$opt+\epsilon$</tex> for any fixed sufficiently small <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\epsilon &gt; 0$</tex> , where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$opt, k$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$L$</tex> 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.

MinSum Movement of Barrier and Target Coverage using Sink-based Mobile Sensors on the Plane