Periodic Sweep Coverage Scheme Based on Periodic Vehicle Routing Problem

We provide a sweep coverage algorithm for routing mobile sensors that communicate with a central data sink. This algorithm improves on its predecessors by reducing the number of unnecessary scans when different points of interest (POIs) have different requirements for the time interval within which they must be scanned (sweep period). Most sweep coverage algorithms seek to minimize the number of sensors required to cover a given collection of POIs. When POIs have different sweep period requirements, existing algorithms will produce solutions in which sensors visit some POIs much more frequently than is necessary. We define this as the POI Over-Coverage problem. In order to address this problem we develop a Periodic Sweep Coverage (PSC) scheme based on a well-known solution to the Periodic Vehicle Routing Problem (PVRP). Our algorithm seeks a route for the mobile sensors that minimizes the number of unnecessary visits to each POI. To verify and test the proposed scheme we implemented a C++ simulation and ran scenarios with a variety of POI topologies (number and distribution of the POIs) and the speed at which sensors could travel. The simulation results show that the PSC algorithm outperforms other sweep coverage algorithms such as CSweep and Vehicle Routing Problem Sweep Coverage (VRPSC) on both the average number of sensors in a solution and in the computational time required to find a solution. Our results also demonstrate that the PSC scheme is more suitable for the sweep coverage scenarios in which higher speed mobile sensors are used.