Design Of Coverage Hole Detection And Repairing Scheme In Wireless Sensor Networks

Wireless Sensor Network(WSN)has been widely used in military,agriculture,medical fields,etc.The coverage ratio of a WSN to a monitored area is an significant metric for evaluating the service quality of the WSN.Due to random deployment of nodes and nodes'energy exhaustion or node failure,etc.,coverage holes will appear in the monitored area,which may cause network transmission interruption and affect reliability of collected data.Therefore,after deployment of WSNs,it is necessary to study whether there are coverage holes in the monitoring area and deploy mobile sensor nodes to repair coverage holes.Then these mobile sensor nodes collect data from coverage holes,and forward data to a base station.The main innovations of this dissertation is summarized as follows:1.A dynamic coverage holes detection strategy based on the Elfes coverage model is proposed when nodes exit after deploying a WSN network.First,the sensing field is divide into equal-sized grids.Then we determine whether candidate coverage holes are formed within the maximum sensing area of a faulty node and the threshold sensing area of its neighbors.This can be judged by calculating the set of boundary points enclosing candidate coverage holes.Only when the set of boundary points is not empty,we sample random points from grids in candidate coverage holes and calculate the detection probability of each sampled point under the Elfes model.If there is a point whose detection probability is below the specified threshold probability,then it is determined that a coverage hole occurs.The existing HDRE scheme need to sample and calculate for all grids in the maximum sensing area of a faulty node when detecting coverage holes.Compared with the HDRE scheme,simulation results show that the strategy proposed in this dissertation can significantly reduce the number of sampled points to identify coverage holes.In addition,when a faulty node is redundant,the proposed scheme does not need to perform random sampling,which improves computational efficiency of the coverage hole detection scheme.As the proposed solution need to obtain global geographic location information of each node to calculate coordinates for each boundary point,a method of calculating local coordinates based on distances between nodes is proposed to compute coordinates of boundary points.2.For the problem of assigning multiple mobile nodes to repair coverage holes within monitoring area,the paper proposes a solution based on an approximate solution to the minimum-cost Hamiltonian cycle problem and a Greedy strategy to choose the nearest next node.After dividing the monitoring area into discrete grids,the grids not covered by any node according to the sensing radius of nodes are called coverage-hole grids.In the following,based on the set cover problem,the concept of key coverage-hole grids is proposed.As a result,a mobile node only need to traverse all key coverage-hole grids to collect data within the current location of it in order to completely cover all the coverage-hole grids.Then we consider to assign multiple mobile nodes to traverse the key coverage-hole grids to collect data.As a result,the problem is transformed into the target coverage problem with multiple mobile nodes.Simulation results show that,compared with the existing strategy of assigning multiple mobile nodes to cover coverage-hole grids,the two proposed strategies have the advantage of reducing the sum of moving distance of multiple mobile nodes when repairing coverage holes.3.For the problem of forwarding data to a base station,a data forwarding strategy based on hierarchical node scheduling is proposed.When forwarding data to the next layer,we schedule receiving nodes in the next layer to receive data from source nodes in the current layer.Given the different working cycle quota of each receiving node,we aim to maximize the sum of the working cycle length for receiving nodes.After establishing the mixed integer programming model for the hierarchical node scheduling problem,the mixed integer programming problem is approximately transformed into a linear programming problem after picking a collection of the set of receiving nodes to cover source nodes according to the coverage relationship among receiving nodes and source nodes.Simulation results show that,compared with the existing data forwarding scheme based on the greedy strategy,the proposed scheme can significantly optimize the sum of working cycle length for receiving nodes at each layer.