2025/05/20 by Ching‐Chi Lin, Lin, Ching-Chi, Mario Günzel +3
Computer Science · #Age of Information Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2505.14968
openalex publication_date 2025/05/20 · openalex created_date 2025/10/19 · openalex updated_date 2026/07/28
Age-of-information (AoI) is a critical metric that quantifies the freshness of data in communication systems. In the era of the Internet of Things (IoT), data collected by resource-constrained devices often need to be transmitted to a central server to extract valuable insights in a timely manner. However, maintaining a stable and direct connection between a vast number of IoT devices and servers is often impractical. The Store-Carry-Forward (SCF) communication paradigm, such as Piggyback networks, offers a viable solution to address the data collection and transmission challenges in distributed IoT systems by leveraging the mobility of mobile nodes. In this work, we investigate AoI within the context of patrolling data collection drones, where data packets are generated recurrently at devices and collected by a patrolling drone to be delivered to a server. Our objective is to design a patrolling route that minimizes the Maximum Age-of-Information (MAI) across the system. We demonstrate that determining whether a route with an MAI below a certain threshold can be constructed is NP-Complete. To address this challenge, we propose two approaches with approximation guarantees. Our evaluation results show that the proposed approaches can achieve near-optimal routes in reasonable time across various scenarios