Coverage and Connectivity Improvement Algorithms for the Wireless Sensor Networks
In this paper, the authors study the increase of coverage and connectivity in a sensor network with a view to improving coverage, while preserving the network's coverage. They also examine the impact of on the related problem of coverage-boundary detection. They reduce both problems to the computation of Voronoi diagrams and intersectional point method prove and achieve lower bounds on the solution of these problems and present efficient distributed algorithms for computing and maintaining solutions in cases of sensor failures or insertion of new sensors. They prove the correctness and termination properties of their distributed algorithms, and analytically characterize the time complexity and the traffic generated by their algorithms.