Efficient k-coverage algorithms for wireless sensor networks and their applications to early detection of forest fires

Achieving k-coverage in wireless sensor networks has been shown before to be NP-hard. We propose an efficient approximation algorithm which achieves a solution of size within a logarithmic factor of the optimal. A key feature of our algorithm is that it can be implemented in a distributed manner with local information and low message complexity. We design and implement a fully distributed version of our algorithm. Simulation results show that our distributed algorithm converges faster and consumes much less energy than previous algorithms. We use our algorithms in designing a wireless sensor network for early detection of forest fires. Our design is based on the Fire Weather Index (FWI) System developed by the Canadian Forest Service. Our experimental results show the efficiency and accuracy of the proposed system.