Research On K-coverage Hole Detection Algorithm In Wireless Sensor Networks

The coverage problem is one fundamental problem in wireless sensor networks(WSNs).Coverage reflects how well the target field is monitored by a WSN,and it can be considered as the measure of quality of service(QoS)guaranteed by the network.In many WSN applications,the target field is required to be fully covered by sensors.In applications like positioning or for fault tolerance purpose,it is necessary to ensure that the target field is k-covered(k?1).While in practice,coverage holes may be easily formed due to random deployment,energy depletion or sensor destruction.It is thus of paramount importance to study k-coverage hole detection algorithms from both theoretical and practical perspectives.In the thesis,the k-coverage hole detection algorithm is investigated for wireless sensor networks without location information.Based on distance information and connectivity information between nodes,two different kcoverage hole detection algorithms are proposed,and the performance of the algorithms are analyzed by simulations.The main contributions of the thesis are as follows.(1)A range-based k-coverage hole detection scheme is proposed.First,an algorithm is presented to detect boundary cycles of 1-coverage holes.The algorithm consists of two components,named boundary edge detection and boundary cycle detection.Then the 1-coverage hole detection algorithm is extended to k-coverage hole scenarios.A coverage degree reduction scheme is proposed to find an independent covering set of nodes in the covered region of target field and reduce the coverage degree by one through sleeping those nodes.Repeat the 1-coverage hole detection algorithm and the higher order of coverage holes can be found.By iterating the above steps for k-1 times,boundary edges and boundary cycles of all k-coverage holes can be discovered.Finally,the proposed algorithm is compared with a location-based coverage hole detection algorithm,simulation results indicate that the proposed algorithm can accurately detect over 99% coverage holes.(2)The wireless sensor network is modeled by Rips complex in the homology theory,and an efficient simplicial complex reduction algorithm is proposed.The reduction algorithm aims at simplifying the network topology by recurrently deleting redundant vertices and edges in the network,while keeping the homology of the network invariant.The reduction process iterates until no new elements can be deleted,and the simplicial complex is simplified to be nearly planar and easy for computation.(3)The homology theory is applied to the k-coverage problem of WSNs.A k-coverage hole detection algorithm based on connectivity information is proposed for discovering all nontriangular holes.Firstly,the WSN is modeled by Rips complex and a 1-coverage holes discovering scheme is presented by recurrently deleting vertices without changing the homology of the network.Then,an independent covering sub-complex is discovered by the simplicial complex reduction algorithm,and coverage degree of the network is reduced by one through sleeping nodes in the complex.By iterating the 1-coverage hole detection and the coverage degree reduction steps for k-1 times,all k-coverage holes can be discovered.Performance of the proposed algorithm is compared with a location-based scheme,and simulation results show that the algorithm can accurately detect 95% of non-triangular kcoverage holes.