Barrier coverage with optimized quality for wireless sensor networks

This paper addresses the construction problem of virtual barrier coverage with optimized detection degree, detection quality, and transmission latency for a wireless sensor network (WSN) consisting of many randomly deployed sensor nodes and few sink nodes. The problem is concerned with how to select sensor nodes to reach three optimization goals: (1) maximizing the degree k of barrier coverage, (2) maximizing the minimum probability p of detecting intruders crossing the monitoring region, and (3) minimizing the expected transmission time t to send data to the sink nodes. An algorithm, called Optimal Barrier Coverage Algorithm (OBCA), is proposed to solve the problem on the basis of graph transformation and two well known maximum flow algorithms. The time complexity of OBCA is also analyzed in this paper.