Indexed by:
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:
Reprint 's Address:
Email:
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:
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: