| Coverage problem in wireless sensor networks has been studied extensively under various models.But in recent years,with the development of Unmanned Aerial Vehicle,the coverage problem has changed from entirely coverage to partial coverage and from continuity to periodicity.Besides,many mobile sensors come into applications and the sweep coverage problem has emerged.Equipped with battery,mobile sensors can travel finite distance until fully recharged,based on which,we study a series of distance constraint sweep coverage in this paper.(1)The minimum distance constraint sweep coverage problem(MinDCSC)is to find the minimum number of mobile sensors and their trajectories such that each static sensor is visited at least once by some mobile sensor every required time period and every mobile sensor visits a base station before running out of its energy(suppose every recharge of energy can support a continues movement of distance D.For one base station case,we give an asymptotically ??/?-2-approximation algorithm on general metric and 2 approximation on tree metric,where a is the performance ratio of Traveling Salesman Problem and D/lmax,in which lmax is the distance between base station and the farthest static sensor;for more than one base stations,we give a k? approximation algorithm,where ? is the performance ratio for one base station.(2)Given the number of mobile sensors,the minimum distance constraint sweep period coverage problem(MinDCSPC)is to find the trajectories and allocations for mobile sensors within distance constraint such that the maximum time period requirement of static sensor is as minimum as possible.When the optimal trajectories are given,we give an optimal allocation way;if the optimal trajectories are not given,we presented an asymptotically k2 ??/?-2-approximation atgor-ithm on general metric and 2k2-approximation on tree metric.(3)For the distance constraint barrier sweep coverage problem,we improve previous the performance ratio 13/3 to 3. |
PDF Full Text Request