| Coverage problem in wireless sensor networks is one of the most classic-hard problems in the field of combinatorial optimization and complexity theory.Sweep Coverage problem developed from it has attracted more and more attention recently,and has a very wide application background in practice.Sweep Coverage problem asks for assigning mo-bile sensors to collect information from a set of target points and the information at each static point4)is required to be collected at least once in every time period4).This paper only studies Sweep Coverage problem on path/cycle.For Sweep Coverage on a path,when mobile sensors have uniform velocity,for the goal of minimizing the number of mobile sensors,we propose an exact greedy algorithm;for the goal of minimizing sweep period,minimizing total distance and minimizing energy consuming,we propose dynamic algorithms.When mobile sensors have constant velocities,we propose 2-,2-,2-and 4-approximation algorithms for the above four different problems.When each static point has a handling time,each mobile sensor is required to return to the depot before time span,and all static points have infinite sweep period,for uniform handling time,we present a linear exact algorithm;for non-uniform handling time,NP-hardness is proved and an approximation algorithm with a guaranteed approximation ratio is presented.For Sweep Coverage on a cycle,when each static point has a handling time,each mobile sensor is required to return to the depot before time span,and all static points have infinite sweep period,we show that the problem of non-uniform handling time is-hard and present an approximation algorithm with a guaranteed approximation ratio. |
