• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Guo, Longkun (Guo, Longkun.) [1] | Zou, Wenjie (Zou, Wenjie.) [2] | Wu, Chenchen (Wu, Chenchen.) [3] | Xu, Dachuan (Xu, Dachuan.) [4] | Du, Dingzhu (Du, Dingzhu.) [5]

Indexed by:

EI

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 $\mathcal{NP}$ -complete via reducing from the Partition problem that is known $\mathcal{NP}$ - 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 $O(n^{2})$ when sinks emit sensors of uniform sensing radius, and in time $O(\vert R\vert ^{2}n^{2})$ for sensors of non-uniform radii, where $n$ and $\vert R\vert$ 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 $O(k^{2}(\frac{L}{\epsilon})^{2})$ time and computes a coverage with total movement provably bounded by $opt+\epsilon$ for any fixed sufficiently small $\epsilon > 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. © 2021 IEEE.

Keyword:

Approximation algorithms Energy efficiency Graph theory Optimization Polynomial approximation

Community:

  • [ 1 ] [Guo, Longkun]School of Computer Science and Technology, Qilu University of Technology, Jinan, China
  • [ 2 ] [Zou, Wenjie]College of Mathematics and Computer Science, Fuzhou University, Fuzhou, China
  • [ 3 ] [Wu, Chenchen]College of Science, Tianjin University of Technology, Tianjin, China
  • [ 4 ] [Xu, Dachuan]Beijing University of Technology, Dept. of Operations Res. and Info. Eng., Beijing, China
  • [ 5 ] [Du, Dingzhu]University of Texas at Dallas, Department of Computer Science, TX, United States

Reprint 's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

Year: 2021

Volume: 2021-July

Page: 696-706

Language: English

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count: 9

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 1

Affiliated Colleges:

Online/Total:138/10050711
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1