.png){kind=icon}
.png){kind=icon}
Return
Approximating Sweep Coverage Delay
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-030-02849-7_2.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We consider the following fundamental sweep coverage problem that arises in mobile wireless sensor networks: Given a set of k mobile sensors and a set of m points of interests (POIs) in the Euclidean plane, how to schedule the mobile sensors such that the maximum delay between two subsequent visits to a POI by any sensor is minimized. We study two scenarios of this problem: (i) start positions of the sensors are fixed such that they must return to their start positions between subsequent traversals to POIs that fall in their trajectories, and (ii) sensor positions are not fixed and they are not required to return to their start positions between subsequent traversals. Scenario (i) models battery-constrained sensors which need to be recharged frequently, whereas scenario (ii) models sensors that have no constraint on battery and hence frequent recharging is not necessary. We present two constant factor approximation algorithms for each scenario. The problem we consider is NP-hard and, to the best of our knowledge, these are the first algorithms with guaranteed approximation bounds for this problem.
Keywords:
TARGET COVERAGE
SENSOR
ALGORITHMS
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
U
IF:
0
Papers:
6
Citations:
0