Distance Constraint Sweep Coverage Problem In Wireless Sensor Networks

Sweep coverage is a very important issue in the field of wireless sensor networks.It refers to collecting information about some detected points through some mobile sensors.The information of each monitoring point needs to be collected once in a period of time.S-ince each mobile sensor has a power limit,we propose a distance limit condition.Under this condition,we studied three models.Distance constraint sweep-coverage with the minimum sum of the number of mobile sensors and the number of base stations(MinDCSC-SB),dis-tance constraint sweep-coverage with base stations,the minimum number of mobile sensors(MinDCSC-BS),and distance constraint min-sweep-period sweep-coverage(MinDCSPSC).For the MinDCSC-SB problem,given connected graph G=(V,E,W),the sweep-period t,the speed v of the mobile sensor,and the distance constraint D,each mobile sensor has to return to the base station for recharging before the length of the moving distance D,the goal is to minimize the sum of the number of mobile sensors and the number of base stations.We give an approximation algorithm with an approximation ratio of 7 on the general graph.For the MinDCSC-BS problem,given some base stations R=(r1,r2,…rk),each mobile sensor has to return to the base station before moving distance D,the gaol is to minimize the total number of mobile sensors.For this problem we give an(O(log 1/?),1+?)bicriteria approximation algorithm,where ??(0,1)is a constant.For the MinDCSPSC problem,given m mobile sensors,each mobile sensor has an upper bound of distance constraint D,find trajectories for these mobile sensors to form a sweep cover such that the maximum sweep period of target points is minimized,each trajectory for mobile sensor has length at most D.We give an approximation algorithm with an approximate ratio of O(m)on the general graph.