Redundant Coverage in Wireless Sensor Networks
Can Fang, Chor Ping Low · 2007
Coverage is a fundamental problem in sensor networks. In this paper, we addressed the coverage problem from two different view points and refer to them as the worst and best- case coverage problems. Existing work on these two problems assumed that the coverage degree is one (i.e. the target area falls within the sensing range of at least one sensor). In this paper, we address thek-coverage problem, where the coverage degree is a user-defined parameterk. This is a generalization of the earlier work where onlyk=1 is assumed. By combining geometric and algorithmic techniques, we establish an optimal algorithm to solve the two variants of the k-coverage problem in polynomial time.