Robust surface coverage using deterministic grid based deployment in wireless sensor networks

Abstract

The rapid progress in the field of wireless communication ans MEMS technology has made wireless sensor networks (WSN) possible. These networks may have low cost sensors deployed which are capable of sensing any activity in the vicinity, storing the information etcetera to carry out a certain task. An important problem receiving increasing consideration is the sensor coverage problem, that is, how well the sensors observe the physical space? Coverage can be considered as a measure of quality of service (QoS) of a sensor network [17]. Using equilateral triangle grid based deployment of the sensors, it is necessary to place the sensor nodes such that they are not too close so that the overlapping of the covered area is minimum. But, at the same time, not too far away that it leads to some uncovered areas known as the coverage holes. Thus, the sensing capabilities of the sensor nodes must be fully utilized in order to maximize coverage of the FoI. To find the coverage of the given uneven surface, the concepts in computational geometry, especially the Voronoi diagrams have been extensively used. When the sensor nodes are deployed using an aircraft, the accuracy of the sensor deployment is affected due to various factors like terrain properties, timing errors in deployment mechanism and more. Hence, it is necessary to take into consideration these placement errors while calculating the coverage of the surface. Existing work on the coverage of the given surface provides mathematical formulation for 2-D surfaces [5]. But, in real world applications, the surfaces are not 2-D in nature. But have many perturbations. This work intends towards deriving mathematical formulas based on Voronoi Diagram concept for such perturbed surfaces which calculates the value, the sensing radius should be set to, so that the entire region is covered. It also derives formulas when horizontal and vertical errors are introduced individually and when introduced together. This work also proposes an algorithm for calculating the coverage of the region under consideration when random errors are introduced in the deployment of the sensor nodes. It also provides information about total area covered for different values of the sensing radius of the sensor nodes. This information is required by different applications having different coverage needs.