2021/05/13 by Dieyan Liang, Hong Shen, Liang, Dieyan +1
Computer Science · Engineering · #Computational Complexity (cs.CC) #Energy Efficient Wireless Sensor Networks #Energy Harvesting in Wireless Networks #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2105.06030
openalex publication_date 2021/05/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Sweep coverage is to realize the periodic coverage of targets by planning the periodic sweeping paths of mobile sensors. It is difficult for sensors to reduce energy consumption by reducing the moving distances. Therefore, charging technology is the best way to extend the lifetime of the sweep coverage network. This paper studies the sweep coverage of rechargeable sensors: the sensors are rechargeable, constantly sweep between the target points and the charging stations not only tp meet the periodic coverage requirement of the target points, but also need to return to the charging stations during the charging period to avoid running out of energy. This paper proposes the general definition of Chargeable Sweep Coverage (CSC) problem for the first time, and studies the complexity of the CSC problem by analyzing CSC problems under different constraints, and then proposes two kinds of CSC problems under special constraints: 1) The sensors need to return to their original charging stations for charging; 2) The sensors can go to different charging stations for charging, and the number of charging stations is 2. Both of these problems are NP-hard. In this paper, these two problems are modeled as the maximum set coverage problem, and the approximation algorithms are obtained by reducing the number of candidate paths to polynomials. The validity and scalability of the proposed algorithms is proved by theoretical proof and experimental simulation.