On Energy-Efficient Trap Coverage in Wireless Sensor Networks

In wireless sensor networks (WSNs), trap coverage has recently been proposed to tradeoff between the availability of sensor nodes and sensing performance. It offers an efficient framework to tackle the challenge of limited resources in large scale sensor networks. Currently, existing works only studied the theoretical foundation of how to decide the deployment density of sensors to ensure the desired degree of trap coverage. However, the practical issues such as how to efficiently schedule sensor node to guarantee trap coverage under an arbitrary deployment is still left untouched. In this paper, we formally formulate the Minimum Weight Trap Cover Problem and prove it is an NP-hard problem. To solve the problem, we introduce a bounded approximation algorithm, called Trap Cover Optimization (TCO) to schedule the activation of sensors while satisfying specified trap coverage requirement. The performance of Minimum Weight Trap Coverage we find is proved to be at most O(ρ) times of the optimal solution, where ρ is the density of sensor nodes in the region. To evaluate our design, we perform extensive simulations to demonstrate the effectiveness of our proposed algorithm and show that our algorithm achieves at least 14% better energy efficiency than the state-of-the-art solution.