2 7 Ju n 20 17 1 Point Sweep Coverage on Path
An important application of wireless sensor networks is the deployment of mobile sensors to periodically monitor (cover) a set of points of interest (PoIs) The problem of Point Sweep Coverage is to deploy fewest sensors to periodically cover the set of PoIs. For PoIs in a Eulerian graph, this problem is known NP Hard even if all sensors are with uniform velocity. In this paper, we study the problem when PoIs are on a line and prove that the decision version of the problem is NP Complete if the sensors are with different velocities. We first formulate the problem of Max PoI sweep coverage on path (MPSCP) to find the maximum number of PoIs covered by a given set of sensors, and then show it is NP Hard. We also extend it to the weighted case, Max Weight sweep coverage on path (MWSCP) problem to maximum the sum of the weight of PoIs covered. For sensors with uniform velocity, we give a polynomial time optimal solution to MWSCP. For sensors with constant kinds of velocities, we present a 1 2 approximation algorithm. For the general case of arbitrary velocities, we propose two algorithms. One is a 1 2a approximation algorithm family scheme, where integer a 2 is the tradeoff factor to balance the time complexity and approximation ratio. The other is a 1 2 (1 1/e) approximation algorithm by randomized analysis.