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.
翻译:通过规划移动传感器的定期扫描路径实现目标的定期覆盖,即通过规划移动传感器的定期扫描范围,实现目标的定期覆盖,传感器很难通过减少移动距离减少能源消耗。因此,收费技术是延长扫描覆盖网络寿命的最佳途径。本文研究可再充电传感器的扫描范围:传感器是可再充电的,在目标点和充电站之间不断进行扫描,不仅满足目标点的定期覆盖要求,而且需要在充电期内返回充电站以避免能源耗竭。本文首次提出可充电扫描覆盖问题的一般定义,并通过分析不同制约下CSC问题来研究CSC问题的复杂性,然后在特殊制约下提出两种CSC问题:(1)传感器需要返回最初的充电站;(2)传感器可以到不同的充电站进行充电,而充电站的数量是2,这两个问题都是NP-硬的。在本文中,这两个问题都是以设定的最大覆盖问题为模型,通过减少实验性实验性实验室的校准和校准能力获得的校准算法。