Liang Dieyan, Shen Hong
School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510275, China.
Sensors (Basel). 2021 Feb 19;21(4):1457. doi: 10.3390/s21041457.
As an important application of wireless sensor networks (WSNs), deployment of mobile sensors to periodically monitor (sweep cover) a set of points of interest (PoIs) arises in various applications, such as environmental monitoring and data collection. For a set of PoIs in an Eulerian graph, the point sweep coverage problem of deploying the fewest sensors to periodically cover a set of PoIs is known to be Non-deterministic Polynomial Hard (NP-hard), even if all sensors have the same velocity. In this paper, we consider the problem of finding the set of PoIs on a line periodically covered by a given set of mobile sensors that has the maximum sum of weight. The problem is first proven NP-hard when sensors are with different velocities in this paper. Optimal and approximate solutions are also presented for sensors with the same and different velocities, respectively. For sensors and PoIs, the optimal algorithm for the case when sensors are with the same velocity runs in O(MN) time; our polynomial-time approximation algorithm for the case when sensors have a constant number of velocities achieves approximation ratio 12; for the general case of arbitrary velocities, 12α and 12(1-1/e) approximation algorithms are presented, respectively, where integer α≥2 is the tradeoff factor between time complexity and approximation ratio.
作为无线传感器网络（WSN）的一项重要应用，在诸如环境监测和数据收集等各种应用中，都会出现部署移动传感器以定期监测（扫描覆盖）一组兴趣点（PoI）的情况。对于欧拉图中的一组兴趣点，即使所有传感器具有相同的速度，部署最少数量的传感器以定期覆盖一组兴趣点的点扫描覆盖问题也已知是NP难的。在本文中，我们考虑在一条直线上找到由给定的一组移动传感器定期覆盖的兴趣点集合，该集合具有最大权重和的问题。本文首先证明当传感器具有不同速度时该问题是NP难的。还分别针对具有相同速度和不同速度的传感器给出了最优解和近似解。对于M个传感器和N个兴趣点，当传感器具有相同速度时的最优算法运行时间为O(MN)；对于传感器具有恒定数量速度的情况，我们的多项式时间近似算法的近似比为12；对于任意速度的一般情况，分别给出了12α和12(1 - 1/e)的近似算法，其中整数α≥2是时间复杂度和近似比之间的权衡因子。
