K-Coverage and its Application to Forest Fire Detection

being be updated .... for now see http://nsl.cs.sfu.ca/projects/wsn/

We propose new algorithms to achieve k-coverage (i.e., each point is sensed by at least k sensors) in dense sensor networks. In such networks, covering sensor locations approximates covering the whole area. However, it has been shown before that selecting the minimum set of sensors to activate from an already deployed sensors is NP-hard. We proposed an efficient approximation algorithm which achieves a solution of size within a logarithmic factor from the optimal. Results from our implementation showed that the logarithmic factor is only a worst case upper bound and the solution size is within a constant factor of the optimal in most cases. We also designed and implemented a fully distributed version of our algorithm. Comparison with two other distributed algorithms in the literature showed that our algorithm converges much faster and consumes less energy than the other algorithms.