Distributed Algorithm for Voronoi Partition of Wireless Sensor Networks with a Limited Sensing Range.

Area of Science:

• Computer Science
• Distributed Systems
• Computational Geometry

Background:

• Voronoi partition in Wireless Sensor Networks (WSNs) is complex due to sensor limitations and network distribution.
• Existing algorithms for limited Voronoi cells in WSNs face challenges in computational complexity and efficiency.

Purpose of the Study:

• To propose a novel distributed algorithm for computing limited Voronoi cells in WSNs.
• To enhance the efficiency and accuracy of regional partitioning in sensor networks.

Main Methods:

• A Boundary Scan (BS) algorithm inspired by Graham's Scan is developed for autonomous Voronoi cell computation.
• The algorithm sequentially scans bisectors between sensors and their neighbors.
• It offers improved computational complexity compared to existing Range-Constrained Voronoi Cell (RCVC) methods.

Main Results:

• The Boundary Scan (BS) algorithm achieves lower computational complexity, nearing the theoretical lower bound.
• It demonstrates improved time efficiency for the Adjust-Sensing-Radius (ASR) algorithm's key steps.
• Numerical simulations confirm the algorithm's correctness and effectiveness in WSNs.

Conclusions:

• The Boundary Scan (BS) algorithm provides an efficient and distributed solution for Voronoi partitioning in WSNs.
• It is suitable for WSN applications, especially when combined with localization algorithms.
• The method advances the state-of-the-art in distributed sensor network computation.