Cost Efficient Mobile Trajectory Planning in Barrier Sweep Coverage
Rinku Sen, Sunirmal Khatua, Rajib Das · 2024
The problem of detecting intrusion over a curved barrier by deploying sensors is called the barrier coverage problem. In the barrier sweep coverage problem, the objective is to visit every point on the curve at intervals of no more than a given period t called the sweep period. This is a challenging problem, requiring the determination of a tour plan for mobile devices moving at a given speed to ensure sweep coverage within the given sweep period. This paper proposes an algorithm to solve this problem, where we divide the curve C into N small segments of almost equal length. The proposed algorithm has a time complexity of O(N2) and an approximate ratio of 2, which is better than the previous best ratio of Math 1 . Additionally, we presented an Integer Linear Program (ILP) formulation of the problem and conducted experiments to compare the proposed algorithm with the optimal solution obtained from ILP. The results indicate that our algorithm provides solutions very close to the optimal solution obtained from ILP, thereby establishing its effectiveness for solving the barrier sweep coverage problem.