2017/04/14 by Dieyan Liang, Hong Shen, Liang, Dieyan +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #Optimization and Search Problems #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.1704.04332
openalex publication_date 2017/04/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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)/(2α)-approximation algorithm family scheme, where integer α≥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.