Cost-effective barrier coverage formation in heterogeneous wireless sensor networks

Barrier coverage is a critical issue in wireless sensor networks (WSNs) for security applications, which however cannot be guaranteed to be formed after initial random deployment of sensors. Existing work on barrier coverage mainly focus on homogeneous WSNs, while little effort has been made on exploiting barrier coverage formation in heterogeneous WSNs where different types of sensors are deployed with different sensing models and costs. In this paper, we study how to efficiently form barrier coverage by leveraging multiple types of mobile sensors to fill in gaps between pre-deployed stationary sensors in heterogeneous WSNs. The stationary sensors are grouped into clusters and a cluster-based directional barrier graph is proposed to model the barrier coverage formation problem. We prove that the minimum cost of mobile sensors required to form a barrier with stationary sensors is the length of the shortest path on the graph. Moreover, we propose a greedy movement algorithm for heterogeneous WSNs to efficiently schedule different types of mobile sensors to different gaps while minimizing the total moving cost. In particular, we formulate the movement problem for homogeneous WSNs as a minimum cost bipartite assignment problem, and solve it in polynomial time using the Hungarian algorithm. Extensively experimental results on homogeneous and heterogeneous WSNs demonstrate the effectiveness of the proposed algorithms.