College of Physics and Information Engineering, Fuzhou University, Fuzhou 350116, China.
College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China.
Sensors (Basel). 2019 Jan 11;19(2):273. doi: 10.3390/s19020273.
Given a set of sensors distributed on the plane and a set of Point of Interests (POIs) on a line segment, a primary task of the mobile wireless sensor network is to schedule covering the POIs by the sensors, such that each POI is monitored by at least one sensor. For balancing the energy consumption, we study the min-max line barrier target coverage (LBTC) problem which aims to minimize the maximum movement of the sensors from their original positions to their final positions at which the coverage is composed. We first proved that when the radius of the sensors are non-uniform integers, even 1-dimensional LBTC (1D-LBTC), a special case of LBTC in which the sensors are distributed on the line segment instead of the plane, is NP -hard. The hardness result is interesting, since the continuous version of LBTC to cover a given line segment instead of the POIs is known polynomial solvable. Then we present an exact algorithm for LBTC with uniform radius and sensors distributed on the plane, via solving the decision version of LBTC. We argue that our algorithm runs in time O ( n 2 log n ) and produces an optimal solution to LBTC. The time complexity compares favorably to the state-of-art runtime O ( n 3 log n ) of the continuous version which aims to cover a line barrier instead of the targets. Last but not the least, we carry out numerical experiments to evaluate the practical performance of the algorithms, which demonstrates a practical runtime gain comparing with an optimal algorithm based on integer linear programming.
给定一组分布在平面上的传感器和一组在线段上的兴趣点 (Point of Interests，POI)，移动无线传感器网络的主要任务是安排传感器覆盖 POI，使得每个 POI 至少由一个传感器进行监控。为了平衡能量消耗，我们研究了最小最大线障碍目标覆盖 (Min-Max Line Barrier Target Coverage，LBTC) 问题，该问题旨在最小化传感器从原始位置到覆盖位置的最大移动距离。我们首先证明了当传感器的半径是非均匀整数时，即使是 LBTC 的一维特殊情况 (1D-LBTC)，即传感器分布在线段上而不是平面上，也是 NP 难问题。这个困难的结果很有趣，因为已知连续版本的 LBTC 可以多项式时间求解来覆盖给定的线段而不是 POI。然后，我们通过求解 LBTC 的决策版本，提出了一种用于具有均匀半径且传感器分布在平面上的 LBTC 的精确算法。我们认为我们的算法的运行时间为 O(n^2logn)，并产生 LBTC 的最优解。与旨在覆盖线障碍而不是目标的连续版本的最新运行时 O(n^3logn)相比，时间复杂度具有优势。最后但同样重要的是，我们进行了数值实验来评估算法的实际性能，与基于整数线性规划的最优算法相比，它展示了实际运行时间的优势。
