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.

Publications

M. Hefeeda, H. Ahmadi, A Probabilistic Coverage Protocol for Wireless Sensor Networks, In Proc. of IEEE International Conference on Network Protocols (ICNP'07), Beijing, China, October 2007. (Acceptance: 15%)

M. Hefeeda, H. Ahmadi, Network Connectivity under Probabilistic Communication Models in Wireless Sensor Networks, In Proc. of IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS'07), Pisa, Italy, October 2007. (Acceptance: 25%)

M. Hefeeda, M. Bagheri, Wireless Sensor Networks for Early Detection of Forest Fires, In Proc. of International Workshop on Mobile Ad hoc and Sensor Systems for Global and Homeland Security (MASS-GHS'07), in conjunction with IEEE MASS'07, Pisa, Italy, October 2007.

M. Hefeeda and M. Bagheri, Randomized k-Coverage Algorithms For Dense Sensor Networks, In Proc. of INFOCOM 2007 Minisymposium, Anchorage, AK, May 2007. (Acceptance: 25%)

Software

Implementation of the Probabilistic Coverage Protocol (PCP) in NS-2. [readme] [code]

Implementation of the Probabilistic Coverage Protocol (PCP) in C++. [readme] [code]

Implementation of the Centralized Randomized K-Coverage Protocols (RKC) in C++. [readme] [code]

Implementation of the Decentralized Randomized K-Coverage Protocols (DRKC) in C++. [readme] [code]

People

Mohamed Hefeeda

Mohamed Hefeeda

Hossein Ahmadi (M.Sc., Graduated Summer 2007)

Majid Bagheri (M.Sc., Graduated Summer 2007)

Miscellaneous

Equations and Fortran Program for the Canadian Forest Fire Weather Index System.