Research On Coverage Hole Detection Algorithm For WSN Based On Homology Theory

The subject of this thesis is supported by the National Natural Science Foundation of China"Research on homology theory based k-coverage algorithms in wireless sensor networks"(No.61601122).The main objective is to study in-depth some algorithms for coverage hole detection in wireless sensor networks(WSN)in the scenarios without information of node location and information of distances between nodes.In this thesis,Rips complex is used to model WSN.Efficient distributed reduction algorithms for Rips complex are proposed by sleeping redundant sensors while preserving the coverage topology.Then two coverage hole detection algorthms are proposed based on the reduced Rips complex.The main contributions are as follows.(1)The thesis proposes a coverage hole detection algorithm based on the information of the relative direction angles(RDA)according to the characteristics of WSN.First of all,with node location information and distances information between nodes unknown,Rips complex of WSN is constructed by using the connectivity information between nodes based on the homology theory.Then the weight of nodes and the relative direction angles between nodes are used to sleep some nodes and disconnect redundant sensor nodes in order to simplify the Rips complex.Based on the reduced Rips complex,a coverage hole detection algorithm is proposed.The information of the relative direction angles is used to obtain all boundary edges(BE)which can help detect all coverage holes.Finally,simulation results show that the proposed algorithm can reduce the number of active sensor nodes while preservin3g the original topology of WSN.In addition,the algorithm has a computation complexity O(n3)and can accurately detect 99%coverage holes,where n denotes the mumber of nodes,m denotes the number of 1-hop neighbors.(2)The thesis proposes a new coverage hole detection algorithm based on Laplacian matrix by introducing the joint Laplacian operator(JLO)into the Rips complex with the unknown information of the relative direction angles.First,the suitable candidate nodes are chosen to be sleeped after computing the weight of nodes.Then the nodes can be determined whether to be sleeped by computing the dimension of the null space of the Laplacian matrixs(LM)of the new Rips complex constructed with the neighbor nodes of sleeped nodes.According to the simplified Rips complex,boundary edges can be found.Coverage holes in WSN can be detected by connecting boundary edges in order.Finally,simulation results show that the proposed algorithm can reduce the amount of network information relied upon and the algorithm has a computation complexity O(n2m4)and can accurately detect 99%coverage holes,where n denotes the mumber of nodes,m denotes the number of 1-hop neighbors..