Algorithms for sensor coverage and sensor localization problems in wireless sensor networks

Recent advances in sensor technology coupled with embedded systems and wireless networking have made it possible to deploy sensors for numerous applications including monitoring microclimates and wildlife habitats, the structural integrity of bridges and buildings, building security, location of valuable assets, traffic, and so on. Among a variety of the essential algorithmic issues that arise in the context of wireless sensor networks, we investigate (1) sensor deployment algorithms for point/region coverage problems, and (2) sensor localization algorithms for the problem of estimating the location of a source in the plane.;An integer linear programming (ILP) formulation is developed to find the minimum cost deployment of sensors that provides the desired coverage of a target point set. We also propose a greedy heuristic for this problem. Our formulation permits heterogeneous multimodal sensors and is extended easily to account for nonuniform sensor detection resulting from blockage, noise, fading, and so on. A greedy algorithm for solving the proposed general ILP is developed. Additionally, epsilon-approximation algorithms and a polynomial time approximation scheme are proposed for the case of grid coverage. Experiments demonstrate the superiority of our proposed algorithms over earlier algorithms for point coverage of grids by using heterogeneous sensors.;We propose a factor 3 approximation algorithm and a polynomial time approximation scheme for the problem of sensor deployment that provides the desired coverage over the entire region at minimum cost. We further propose an equivalent transformation from region coverage to point coverage, and prove the cost of the optimal point coverage is within a constant factor of that of the optimal region coverage for a network of homogeneous sensors. We also study the performance of deploying sensors in a gridded (equilateral triangle, square, and regular hexagon) layout.;We establish several fundamental properties of localization using distance-differences. These properties enable minimalistic realizations of localization systems. We establish conditions for the unique identification of a source in Euclidean plane, and derive minimum number of sensors needed for unique source identification within the Euclidean plane and a polygonal monitoring region. Compared to four possible intersections of two hyperbolas, we show this task leads to at most 2 intersections, which correspond to potential source estimates.;We propose a computational geometry method for the source localization problem using measurements of DTOA (Difference of Time-Of-Arrival). Compared to existing solutions to this well-studied problem, our method is (a) computationally more efficient and adaptive in that its precision can be controlled as a function of the number of computational operations, making it suitable to low power devices; and (b) robust with respect to measurement and computational errors, and is not susceptible to numerical instabilities typical of existing linear algebraic or quadratic methods.