.png){kind=icon}
.png){kind=icon}
Return
Approximation Algorithms for Barrier Sweep Coverage
.png){kind=icon}
PRE
AI
DOI：10.1142/S0129054119500138.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Time-varying coverage, namely sweep coverage is a recent development in the area of wireless sensor networks, where a few mobile sensors sweep or monitor a comparatively large number of locations periodically. In this article, we study barrier sweep coverage with mobile sensors where the barrier is considered as a finite length continuous curve on a plane. The coverage at every point on the curve is time-variant. We propose an optimal solution for sweep coverage of a finite length continuous curve. Usually, energy source of a mobile sensor is a battery with limited power, so energy restricted sweep coverage is a challenging problem for long running applications. We propose an energy-restricted sweep coverage problem where every mobile sensor must visit an energy source frequently to recharge or replace its battery. We propose a 13/3-approximation algorithm for this problem. The proposed algorithm for multiple curves achieves the best possible approximation factor 2 for a special case. We propose a 5-approximation algorithm for the general problem. As an application of the barrier sweep coverage problem for a set of line segments, we formulate a data gathering problem. In this problem a set of mobile sensors is arbitrarily monitoring the line segments one for each. A set of data mules periodically collects the monitoring data from the set of mobile sensors. We prove that finding the minimum number of data mules to collect data periodically from every mobile sensor is NP-hard and propose a 3-approximation algorithm to solve it.
Keywords:
Barrier coverage
sweep coverage
approximation algorithm
Eulerian graph
TSP
mobile sensor
data mule
data gathering
wireless sensor networks
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.1
Papers:
245
Citations:
2.3K