Energy-Efficient Intrusion Detection with a Barrier of Probabilistic Sensors: Global and Local

Intrusion detection is a significant application in wireless sensor networks (WSNs). S. Kumar et al have introduced the concept of barrier coverage, which deploys sensors in a narrow belt region to guarantee that any intrusion across the region is to be detected. However, the practical issues have not been investigated such as scheduling sensors energy-efficiently while guaranteeing the detection probability of any intrusion across the region based on probabilistic sensing model. Besides, the intruders may be humans, animals, fighter planes or other things, which obviously have diverse moving speeds. In this paper, we analyze the detection probability of arbitrary path across the barrier of sensors theoretically and take the maximum speed of possible intruders into consideration since the sensor networks are designed for different intruders in different scenarios. Based on the theoretical analysis of detection probability, we formulate Minimum Weight ε-Barrier Problem about how to schedule sensors energy-efficiently and prove it is NP-hard. We propose both global and local solutions to the problem. The global solution called Minimum Weight Barrier Algorithm is a bounded approximation algorithm, based on which a localized protocol for energy-efficient scheduling is designed. To evaluate our design, we analyze the performance of our approaches theoretically and also perform extensive simulations to demonstrate the effectiveness of our proposed algorithm.