Sensing coverage is a fundamental problem in wireless sensor networks (WSNs), which has attracted considerable attention. Conventional research on this topic focuses on the 0/1 coverage model, which is only a coarse approximation to the practical sensing model. In this paper, we study the target coverage problem, where the objective is to find the least number of sensor nodes in randomly-deployed WSNs based on the probabilistic sensing model. We analyze the joint detection probability of target with multiple sensors. Based on the theoretical analysis of the detection probability, we formulate the minimum ϵ-detection coverage problem. We prove that the minimum ϵ-detection coverage problem is NP-hard and present an approximation algorithm called the Probabilistic Sensor Coverage Algorithm (PSCA) with provable approximation ratios. To evaluate our design, we analyze the performance of PSCA theoretically and also perform extensive simulations to demonstrate the effectiveness of our proposed algorithm.

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.

Coverage is a fundamental issue in the research field of wireless sensor networks (WSNs). Connected target coverage discusses the sensor placement to guarantee the needs of both coverage and connectivity. Existing works largely leverage on the Boolean disk model, which is only a coarse approximation to the practical sensing model. In this paper, we focus on the connected target coverage issue based on the probabilistic sensing model, which can characterize the quality of coverage more accurately. In the probabilistic sensing model, sensors are only be able to detect a target with certain probability. We study the collaborative detection probability of target under multiple sensors. Armed with the analysis of collaborative detection probability, we further formulate the minimum ϵ-connected target coverage problem, aiming to minimize the number of sensors satisfying the requirements of both coverage and connectivity. We map it into a flow graph and present an approximation algorithm called the minimum vertices maximum flow algorithm (MVMFA) with provable time complex and approximation ratios. To evaluate our design, we analyze the performance of MVMFA theoretically and also conduct extensive simulation studies to demonstrate the effectiveness of our proposed algorithm.