• 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:

CPCI-S 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 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:

approximation algorithm Barrier coverage NP-complete optimal algorithm sink station target coverage

Community:

  • [ 1 ] [Guo, Longkun]Qilu Univ Technol, Sch Comp Sci & Technol, Jinan, Peoples R China
  • [ 2 ] [Zou, Wenjie]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou, Peoples R China
  • [ 3 ] [Wu, Chenchen]Tianjin Univ Technol, Coll Sci, Tianjin, Peoples R China
  • [ 4 ] [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Info Eng, Beijing, Peoples R China
  • [ 5 ] [Du, Dingzhu]Univ Texas Dallas, Dept Comp Sci, Richardson, TX 75083 USA

Reprint 's Address:

  • [Wu, Chenchen]Tianjin Univ Technol, Coll Sci, Tianjin, Peoples R China

Show more details

Related Keywords:

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

Online/Total:222/10043667
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