Approximation Algorithms for Barrier Sweep Coverage
From MaRDI portal
Abstract: Time-varying coverage, namely sweep coverage is a recent development in the area of wireless sensor networks, where a small number of mobile sensors sweep or monitor 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 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 sensors must visit an energy source frequently to recharge or replace its battery. We propose a -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.
Recommendations
- Approximation algorithm for sweep coverage on graph
- An approximation algorithm for general energy restricted sweep coverage problem
- Minimizing the total cost of barrier coverage in a linear domain
- An approximation algorithm for the total covering problem
- Approximation algorithms for partial covering problems
- Approximation algorithm for MinSum linear barrier coverage with sink-based mobile sensors on the plane
- A 2-approximation algorithm for barrier coverage by weighted non-uniform sensors on a line
- Approximation algorithms for distance constraint sweep coverage with base stations
Cites work
Cited in
(11)- Group sweep coverage with guaranteed approximation ratio
- Approximation algorithm for sweep coverage on graph
- Approximation algorithms for distance constraint sweep coverage with base stations
- An approximation algorithm for general energy restricted sweep coverage problem
- Data sensing with limited mobile sensors in sweep coverage
- Approximation algorithm for distance constraint sweep coverage without predetermined base stations
- Algorithms for max-value path sweep coverage in mobile sensor networks
- Energy efficient sweep coverage with mobile and static sensors
- Comparing barrier algorithms
- Improved PTASs for convex barrier coverage
- Algorithm for partial sweep coverage on a line
This page was built for publication: Approximation Algorithms for Barrier Sweep Coverage
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384125)
