Minimizing age of information in multi-UAV-assisted IoT networks: a graph theoretical approach

This paper discusses trajectory planning for multiple UAVs in IoT networks to minimize the average Age of Information (AoI). First, using a graph theoretical approach, we present an explicit formula for the average AoI in both Hamiltonian and non-Hamiltonian cycles. These relations tie the upper bound of average AoI with Traveling Salesman Problem (TSP) as well as provide a mechanism to improve AoI in a given flight trajectory by means of creating new cycles around a specific set of IoT devices. Further, we give a lower bound for the average AoI. Secondly, we propose a heuristic algorithm for trajectory planning based on unsupervised clustering. The IoT networks are divided into k subsets and for each of them, a tour is found by a greedy algorithm. Then, the tours are merged together to find the best set of tours for each UAV in terms of average AoI. Moreover, some optimizations are applied on each flight trajectory to improve the average AoI. The evaluation results show that our scheme is efficient compared to both the baseline greedy approach and TSP optimal tour.