Age-Optimal UAV Scheduling for Data Collection With Battery Recharging

We study route scheduling of a UAV for data collection from sensor nodes (SNs) with battery recharging. The freshness of the collected information is captured by the metric of age of information (AoI). The objective is to minimize the average AoI cost of all SNs over a scheduling time horizon. We prove that the problem in its general form is NP-hard. Then, for a special case of the problem, we prove that optimum can be computed in polynomial time. Next, we develop an algorithm based on graph labeling. Finally, we show the effectiveness of our algorithm in comparison to greedy scheduling.