Sweep coverage with return time constraint

Sweep coverage is an important problem in wireless sensor networks. With sweep coverage, more Points Of Interests (POIs) can be monitored with fewer mobile sensor nodes thanks to the mobility of the nodes. Most existing studies on sweep coverage focus on the trajectory of the mobile sensor nodes to guarantee the sweep coverage of the POIs. Considering the fact that, in many applications, the collected data is only useful during a fixed period, we studied the problem of sweep coverage with return time constraint. This problem requires that the POIs should be covered and the collected data should be delivered to the base station within a preset time window. In this paper, we prove that the problem of finding the minimum number of mobile sensor nodes required to guarantee sweep coverage with return time constraint is NP-hard. In addition, we present two novel heuristic algorithms, G-MSCR and MinD- Expand, to provide sweep coverage with return time constraint in practice. Our experimental results indicate that, compared to MinD-Expand, G-MSCR requires more sensor nodes and leads to shorter return time. To our knowledge, G-MSCR and MinD- Expand are the only algorithms that attempt to solve the problem of sweep coverage with return time constraint.