Path Construction and Visit Scheduling for Targets by Using Data Mules

In this paper, the target patrolling problem was considered, in which a set of mobile data collectors, known as data mules (DMs), must efficiently patrol a given set of targets. Because the time interval (or visiting interval) between consecutive visits to each target reflects the degree to which that target is monitored, the goal of this paper was to balance the visiting interval of each target. This paper first presents the basic target points patrolling algorithm, which enables an efficient patrolling route to be constructed for numerous DMs, such that the visiting intervals of all target points are stable. For scenarios containing weighted target points, a weighted target points patrolling (W-TPP) algorithm is presented, which ensures that targets with higher weights have higher data collection frequencies. The energy constraint of each DM was also considered, and this paper presents a W-TPP with recharge (RW-TPP) algorithm, which treats the energy recharge station as a weighted target and arranges for DMs to visit the recharge station before running out of energy. The performance results demonstrated that the proposed algorithms outperformed existing approaches in average visiting frequency, DM movement distance, average quality of monitoring satisfaction rate, and efficiency index.