Design And Implementation Of Localization Algorithm Based On Reconstruction Of Voronoi Diagram In WSN

Localization plays an important role in wireless sensor network (WSN), in which the location of the nodes is the foundation of many applications and routing algorithms. According to the statistics, only fewer than20%localization algorithms are implemented under the practical environment. The remainders also keep in the step of theoretical analysis and simulation. Nevertheless, the characteristics of Voronoi diagram contribute to the reduction of the complexity of the algorithms up to the requirement of localization accuracy. Consequently, localization algorithm based on reconstruction of Voronoi diagram in WSN is valuable in both theoretical issues and practical applications.Focusing on these problems, some research is conducted in this paper. Firstly, the testbed facing localization in WSN is designed and implemented. It supports the experiments of the localization algorithms in WSN, and provides plentiful data for the evaluation of the algorithms. Secondly, focusing on the problems in localization in WSN, the characteristics of Voronoi diagram are paid attention to. Afterwards, the idea of reconstruction of Voronoi diagram is introduced in localization in WSN. According to the different reconstructing methods, two algorithms are proposed. Sorted K-order Voronoi diagram localization (SK.VL) algorithm is based on order-increasing, while cutting Voronoi diagram localization (CVBL) algorithm is based on Voronoi diagram cutting. Thirdly, focusing on the initial awareness, the minimizing of cutting, and the termination conditions, Voronoi diagram growing point selecting (VGS) algorithm is proposed to decrease the complexity. And the optimization of the termination conditions leads to the increment of the efficiency. Finally, the evaluation system facing localization in WSN is enhanced to make the evaluation with more perspectives. The simulation and practical experiments are taken to evaluate the performance of the proposed algorithms. The experimental results show that the conflict between the accuracy and the complexity in localization in WSN is efficiently solved. Compared with the typical SBL algorithm, which is also one of Range-free algorithms, the proposed SKVL, CVBL algorithms achieve lower distance error and fluctuation in the localization region.