Target Coverage Deployment Based On Probabilistic Sensing Model In WSN

In recent years,wireless sensor network is one of the most important research areas which aroused tremendous interests from both industrial and academic communities.Wireless sensor networks are widely applied in practical applications,such as environmental monitoring,forest-fire prevention,air quality monitoring and so on.Coverage problem is fundamental in WSN.According to the coverage subject,three categories of coverage are identified:target coverage,area coverage,and barrier coverage.The connected coverage problem is a special case of target coverage.The connected coverage problem aims at activating sensor nodes to monitor a finite set of targets,and the connectivity of these active nodes with the sink must be retained at the same time(via some relaying nodes).Conventional researches on this topic focus on 0/1 disk coverage model which is only a coarse approximation to the practical sensing model.In the 0/1 disk model,a target within the sensing radius of a node is always assumed detected with a probability of 1 while outside this circle it is assumed not detected.In practical,however,the sensing capabilities of sensors are affected by environmental factors in real deployment,especially for acoustic sensors.In this case,the 0/1 disk model is no longer practical.The probabilistic sensing model,which can characterize the quality of sensor coverage more accurately,has been proposed with the assumption that sensing probability is a decreasing function of the sensing distance 1301.The detection probability in 0/1 disk coverage model,instead of being a real number between 0 and 1,is assigned 1 or 0 according to whether a target lies in the sensor detection scope or not.Due to the uncertainty of detection,each target requires different number of probabilistic sensors when the probabilistic deployment model is used,while only one(for one coverage)or k(for k coverage)sensors are needed for every target when the 0/1 disk model is used.Traditional algorithms based on 0/1 disk model are no longer practical in probabilistic 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 WSN based on probabilistic sensing model.We analyze the joint detection probability of target with multiple sensors.Based on the theoretical analysis of 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 MVMFA with provable approximation ratios.Considering high energy consumption of omnidirectional sensors,we further study the target coverage problem based on directional probabilistic sensors.In this paper,we assume the energy cost of each sensor includes connectivity and coverage.Based on the assumption,we formulate the minimum energy-connected coverage problem,aiming at minimizing the energy of sensors satisfying the needs of both coverage and connectivity.By reducing the set cover problem to our problem,we prove that it is NP-hard.We map it into a flow graph and present an approximation algorithm called Minimum Weight Maximum Flow Algorithm(MWMFA)with provable time complex and approximation ratios.To evaluate our design,we analyze the performance of MVMFA and MWMFA theoretically and also perform extensive simulations to demonstrate the effectiveness of our algorithm.