Weighted Voronoi Sensing Partition Algorithm for Multi-layer Wireless Sensor Network

Wireless sensor networks have been widely implemented in plenty of areas such as environmental observation, agricultural industry, military programs, etc. These sensors are usually deployed in places that are inconvenient or hostile to people, and thus, they cannot be charged and will be abandoned once their energy runs out. In this article, a novel algorithm, WVSP (Weighted Voronoi Sensing Partition Algorithm), is proposed. It is based on hierarchical architecture, which improves the scalability of networks when there are plenty of nodes within the networks. WVSP divides the sensing area into several concentric fan-like rings whose center is the sink node. In each fan-like layer, WVSP computes an optimal number of cluster heads by a correction factor and uses weighted Voronoi polygons to set up clusters. Compared to the LEACH (Low Energy Adaptive Clustering Hierarchy algorithm) and OHILEACH (Optimized Heuristic algorithm of Improved Low Energy Adaptive Clustering Hierarchy), the proposed WVSP algorithm improves the performance of network lifetime and energy efficiency. The simulation demonstrates that in the first scenario, WVSP can save 46.7% and 20.2% more energy than LEACH and OHILEACH, with 75.5% and 35.5% more nodes still alive than LEACH and OHILEACH. In the second scenario, WVSP can save 26.7% and 10.3% more energy than LEACH and OHILEACH, with 65.5% and 40.0% more nodes still alive than LEACH and OHILEACH.