Research On Coverage Hole Detection And Recovery Algorithm Based On Geometrical Approaches In Wireless Sensor Network

Sensors has the function of monitoring and collecting environmental physical information, processing the data collected and transferring the collected data to each other, so wireless sensor network which consists of sensors finds a wide utilization in a lot of fields. Whether the area monitored by sensors is completely covered directly determines the integrity and reliability of information collected by these sensors and also has a significant influence on the quality of service provided by the wireless sensor network, thus coverage problem in wireless sensor networks is an important branch of wireless sensor network field and is attracted widespread attention. It is of great significance both in economy and society.This paper studies coverage hole detection and recovery algorithms based on geometric methods. Firstly, the background and significance of the coverage hole detection and recovery algorithm are presented and then this paper mainly elaborates the research status of coverage hole detection and recovery algorithms at home and abroad, states several classical coverage algorithms especially the geometric method related to coverage.Secondly, by studying the seamless characteristic and maximizing coverage ratio feature of the honeycomb structure, a local coverage hole detection and recovery algorithm based on honeycomb structure is proposed. In the two-dimensional sensor networks, this algorithm computes the intersection of node’s target trajectory circle iteratively, determines the best location that the sensor node needs to move to for the sake of repairing coverage holes and then fixes the holes. The target location of the sensor nodes is calculated iteratively and the sensor nodes only needs the related information of neighbor nodes. Compared with some algorithms that search for the optimal solution in the entire solution space, this algorithm need not scan global information repeatedly and update some information constantly. Therefore the complexity of the algorithm is reduced and it’s a local distributed algorithm.The simulation result shows that the algorithm can effectively detect and repair coverage holes and compared with other algorithms, it owns the best average coverage ratio and moving distance.Thirdly, as the sensor nodes are usually scattered in a three-dimension space in the real world, the study will extend to the three-dimensional space. By considering hole boundary detection in three-dimensional wireless sensor networks, a boundary detection algorithm based on empty ball is studied. According to the empty ball feature of Delaunay tetrahedralization, we construct tetrahedral mesh by using the nodes in space, confirm the existence of the holes and the hole boundary in the light of the relationship of the tetrahedral circumradius, the sensing radius of sensor nodes, the distance of two neighbor ball and the radius of intersecting round. The algorithm is also a local distributed algorithm. Each node only needs the information about neighbor nodes which reduce the overhead of multi-hop communication in the networks. When applying to large-scale networks, this algorithm is proper as well. The simulation result indicates that this algorithm can effectively detect coverage holes in the three-dimensional space and as the radius error increase, the boundary detected by this algorithm is still close to the real boundary.Finally, this paper summarizes the main work of this research and analyses the future research directions.