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

author:

Zou, W. (Zou, W..) [1] | Guo, L. (Guo, L..) [2] | Hao, C. (Hao, C..) [3] | Liu, L. (Liu, L..) [4]

Indexed by:

Scopus

Abstract:

Emerging wireless and mobile applications, such as border intrusion detection with station-based drones, brought a new barrier coverage problem of using sink-based mobile sensors to cover a given line barrier with minimum energy consumption. In this paper, we focus on the uniform sink-based line barrier coverage (SLBC) problem, in which we are given a line barrier and k sink stations distributed on the plane which can emit an infinite number of sensors with an identical sensing radius. The problem aims to find their final positions on the barrier for the sensors emitted by the stations, such that the total moving distance of the sensors is minimized and each point of the barrier is within the sensing area of at least one sensor. We first observe the geometric structure of an optimal solution that any optimal solution can be considered as a set of intersecting tangent (disk) segments, where a tangent (disk) segment is a sequence of tangent disks. Then, we devise an algorithm to calculate all possible tangent (disk) segments and another algorithm to calculate the near-optimal positions for each of such segments. After computing all tangent (disk) segments and their near-optimal positions, an algorithm is proposed to transform uniform SLBC into an instance of the shortest path problem. It is shown the whole algorithm deserves a runtime O(k2log⁡[Formula presented]) and consumes at most ε more movement than an optimal solution, where ε is any given positive real number, and r and k are the sensor radius and the number of sink stations, respectively. © 2022

Keyword:

Auxiliary graph Barrier coverage Geometrically tangent segments Mobile sensor Sink station

Community:

  • [ 1 ] [Zou, W.]College of Mathematics and Computer Science, Jiangxi Science and Technology Normal University, Nanchang, 330038, China
  • [ 2 ] [Zou, W.]College of Mathematics and Statistics, Fuzhou University, Fuzhou, 360116, China
  • [ 3 ] [Guo, L.]College of Mathematics and Statistics, Fuzhou University, Fuzhou, 360116, China
  • [ 4 ] [Guo, L.]School of Computer Science, Qilu University of Technology, Jinan, 250316, China
  • [ 5 ] [Hao, C.]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing, 100124, China
  • [ 6 ] [Liu, L.]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing, 100124, China

Reprint 's Address:

  • [Guo, L.]College of Mathematics and Statistics, China

Show more details

Related Keywords:

Source :

Theoretical Computer Science

ISSN: 0304-3975

Year: 2023

Volume: 941

Page: 121-130

0 . 9

JCR@2023

0 . 9 0 0

JCR@2023

ESI HC Threshold:32

JCR Journal Grade:3

CAS Journal Grade:4

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Affiliated Colleges:

Online/Total:96/10471183
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