He Chenlong, Feng Zuren, Ren Zhigang
State Key Laboratory for Manufacturing System Engineering, Systems Engineering Institute, Xi'an Jiaotong University, Xi'an 710049, China.
Autocontrol Research Institute, Xi'an Jiaotong University, Xi'an 710049, China.
Sensors (Basel). 2018 Feb 3;18(2):446. doi: 10.3390/s18020446.
For Wireless Sensor Networks (WSNs), the Voronoi partition of a region is a challenging problem owing to the limited sensing ability of each sensor and the distributed organization of the network. In this paper, an algorithm is proposed for each sensor having a limited sensing range to compute its limited Voronoi cell autonomously, so that the limited Voronoi partition of the entire WSN is generated in a distributed manner. Inspired by Graham's Scan (GS) algorithm used to compute the convex hull of a point set, the limited Voronoi cell of each sensor is obtained by sequentially scanning two consecutive bisectors between the sensor and its neighbors. The proposed algorithm called the Boundary Scan (BS) algorithm has a lower computational complexity than the existing Range-Constrained Voronoi Cell (RCVC) algorithm and reaches the lower bound of the computational complexity of the algorithms used to solve the problem of this kind. Moreover, it also improves the time efficiency of a key step in the Adjust-Sensing-Radius (ASR) algorithm used to compute the exact Voronoi cell. Extensive numerical simulations are performed to demonstrate the correctness and effectiveness of the BS algorithm. The distributed realization of the BS combined with a localization algorithm in WSNs is used to justify the WSN nature of the proposed algorithm.
对于无线传感器网络（WSN）而言，由于每个传感器的感知能力有限以及网络的分布式组织形式，区域的Voronoi划分是一个具有挑战性的问题。本文提出了一种算法，用于让每个具有有限感知范围的传感器自主计算其有限Voronoi单元，从而以分布式方式生成整个WSN的有限Voronoi划分。受用于计算点集凸包的Graham扫描（GS）算法启发，通过依次扫描传感器与其邻居之间的两条连续平分线来获得每个传感器的有限Voronoi单元。所提出的算法称为边界扫描（BS）算法，其计算复杂度低于现有的范围受限Voronoi单元（RCVC）算法，并且达到了解决此类问题的算法计算复杂度的下限。此外，它还提高了用于计算精确Voronoi单元的调整感知半径（ASR）算法中关键步骤的时间效率。进行了大量数值模拟以证明BS算法的正确性和有效性。将BS的分布式实现与WSN中的定位算法相结合，以证明所提出算法的WSN特性。
