Sensing coverage has attracted considerable attention in wireless sensor networks. Existing work focuses mainly on the 0/1 disk model which provides only coarse approximation to real scenarios. In this article, we study the connected target coverage problem which concerns both coverage and connectivity. We use directional probabilistic sensors, and combine probabilistic and directional sensing model features to characterize the quality of coverage more accurately in an energy efficient manner. Based on the analysis of the collaborative detection probability with multiple sensors, we formulate the minimum energy connected target ε-probability coverage problem, aiming at minimizing the total energy cost while satisfying the requirements of both coverage and connectivity. By a reduction from a unit disk cover, we prove that the problem is nondeterministic polynomial (NP)-hard, and present an approximation algorithm with provable time complexity and approximation ratio. To evaluate our design, we analyze the performance of our algorithm theoretically and also conduct extensive evaluations to demonstrate its effectiveness.
- probabilistic sensor
- target coverage
- wireless sensor networks (WSNs)