K-Coverage and its Application to Forest Fire Detection

Mass production of sensor devices with low cost enables the deployment of large-scale sensor networks for real-life applications such as forest fire detection and habitat monitoring. A fundamental issue in such applications is the quality of monitoring provided by the network. This quality is usually measured by how well deployed sensors cover a target area. In its simplest form, coverage means that every point in the target area is monitored by, i.e., within the sensing range of, at least one sensor. This is called 1-coverage. In this paper, we consider the more general k-coverage (k ≥ 1) problem, where each point should be within the sensing range of k or more sensors. Covering each point by multiple sensors is desired for many applications, because it provides redundancy and fault tolerance. Furthermore, k-coverage is necessary for the proper functioning of other applications, such as intrusion detection, data gathering, and object tracking. To illustrate, consider an intrusion detection system in military applications, where k-coverage is essential to identify intruding objects of different sizes. A tank, for instance, is detected by many sensors, while a soldier is detected by only a few. A high degree of coverage makes the classification more precise, because of errors in the measurement and the susceptibility of sensors to failure and power shortage.

In this project, we design new algorithms to achieve k-coverage 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 propose an efficient approximation algorithm which achieves a solution of size within a constant factor from the optimal. We are also interested in applying our k-coverage algorithms in designing a wireless sensor network for early detection of forest fires. Forest fires, also known as wild fires, are uncontrolled fires occurring in wild areas and cause significant damage to natural and human resources. Forest fires eradicate forests, burn the infrastructure, and may result in high human death toll near urban areas. In the province of British Columbia alone, there have been 2,590 forest fires during 2006. These burned 131,086 hectares and costed about $156 million. (Source: BC Ministry of Forests and Range.) Wireless sensor networks could help in reducing some of the damages caused by forest fires.

People

• Mohamed Hefeeda

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

Publications

• M. Hefeeda M. Bagheri, Forest Fire Modeling and Early Detection using Wireless Sensor Networks, Submitted for publications.

• M. Hefeeda and M. Bagheri, K-Coverage Algorithms for Large-Scale Sensor Networks without Location Information, Submitted for publications.

• M. Hefeeda and 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. Slides pptpdf

• M. Hefeeda and M. Bagheri, Randomized k-Coverage Algorithms For Dense Sensor Networks, In Proc. of IEEE INFOCOM 2007 Minisymposium, pp. 2376--2380, Anchorage, AK, May 2007. Slides ppt pdf. (Acceptance: 25%)

Software

• 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

Miscellaneous

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