Cooperative Sweep Coverage Problem With Mobile Sensors

Sweep coverage plays an important role in many applications such as data gathering, sensing coverage and devices control. In this paper, we deal with the cooperative sweep coverage problem with multiple mobile sensors to periodically cover all positions of interest (Pols) in the surveillance region. Different from traditional sweep coverage scenarios, the cooperative sweep coverage (CSC) problem allows the deployment of multiple sensors on the same trajectory to further reduce the sweep period or detection delay. We also consider the multi-sink sweep coverage (MSSC) problem where each mobile sensor must periodically transmit its collected data to a base station due to the limited storage capacity and power supply. Correspondingly, we propose two constant-factor approximations, namely CoCycle and SinkCycle, to minimize the maximum sweep period for these two problems. The approximation ratios of CoCycle and SinkCycle are proved to be 4 and 6 respectively. As far as we know, SinkCycle is the first approximation for the sweep coverage problem with multiple sinks. We also provide two optimal algorithms for the CSC problem in one dimensional case and a useful insight regarding the MSSC problem with only one available sink. Finally, we conduct various numerical experiments to validate the effectiveness and efficiency of our designs.

Automated summary

This paper investigates the cooperative sweep coverage problem with multiple mobile sensors and the multi-sink sweep coverage problem. Two constant-factor approximations, CoCycle and SinkCycle, are proposed to minimize the maximum sweep period for these two problems, with approximation ratios of 4 and 6, respectively. Additionally, optimal algorithms for the CSC problem and useful insights regarding the MSSC problem are provided. Numerical experiments are conducted to validate the effectiveness and efficiency of the designs.