Approximating Sweep Coverage Delay
Gokarna Sharma and Jong-Hoon Kim
Department of Computer Science, Kent State University, Kent, OH 44242, USA {sharma@cs.,jkim72@}kent.edu
Abstract. 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 POIbyanysensorisminimized.Westudytwoscenariosofthisproblem:(i)start positionsofthesensorsarefixedsuchthattheymustreturntotheirstartpositions betweensubsequenttraversalstoPOIsthatfallintheirtrajectories,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.