Efficient point coverage in wireless sensor networks
We study minimum-cost sensor placement on a bounded 3D sensing field, R, which comprises a number of discrete points that may or may not be grid points. Suppose we have xi types of sensors available with different sensing ranges and different costs. We want to find, given an integer sigma >= 1, a selection of sensors and a subset of points to place these sensors such that every point in R is covered by at least sigma sensors and the total cost of the sensors is minimum. This problem is known to be NP-hard. Let k(i) denote the maximum number of points that can be covered by a sensor of the ith type. We present in this paper a polynomial-time approximation algorithm for this problem with a proven approximation ratio gamma = Sigma(l)(i=1) k(i) - sigma + 1. In applications where the distance of any two points has a fixed positive lower bound, each k(i) is a constant, and so we have a polynomial-time approximation algorithms with a constant guarantee. While gamma may be large, we note that it is only a worst-case upper bound. In practice the actual approximation ratio is small, even on randomly generated points that do not have a fixed positive minimum distance between them. We provide a number of numerical results for comparing approximation solutions and optimal solutions, and show that the actual approximation ratios in these examples are all less than 3, even though gamma is substantially larger.
sensor placement approximation algorithms linear programming