Distributed coverage optimization in a network of mobile agents subject to measurement error

The effect of localization error in mobile sensor networks is investigated in this paper. Localization is an essential building block in mobile sensor networks, and is achieved through information exchange among the sensors. Sensor deployment algorithms often rely on the Voronoi diagram, which is obtained by using the position information of the neighboring sensors. In the sensor network coverage problem, it is desired to place each sensor in a proper position in its Voronoi cell such that its local coverage increases. On the other hand, it is often assumed that all measurements are sufficiently accurate, while in a practical setup even a small localization error may lead to significant uncertainty in the resultant Voronoi diagram. This paper is concerned with the degrading effect of position measurement error in the sensor network coverage problem. To this end, the effect of localization error on the boundaries of the Voronoi polygons is investigated. Two polygons are obtained for each sensor, and it is shown that the exact Voronoi polygon (corresponding to accurate localization) lies between them. The area between these two polygons is directly related to the size of error. A sensor deployment strategy is presented based on these two polygons, using a quantitative local density function which takes the uncertainty of the Voronoi polygons into account to maximize the local coverage of each sensor.