2026-07-22T07:15:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23582 2025-10-27T10:21:43Z ddc:004 open_access

A Multi-UAV Router and Scheduler for Executing Spatially Scattered Real-Time Tasks Mukherjee, Sreyashi Yadav, Sachin Kumar, Yedla Anil Sarkar, Arnab UAV Scheduling Task Allocation Optimization Execution Time Cyber-Physical Systems (CPSs) operating in remote or field scenarios often face limited local processing capacity, necessitating complex real-time monitoring and control via remote processing through mobile edge networks, satellite systems, or UAVs. With recent advancements, UAVs are increasingly being favored for such applications, particularly in isolated areas beyond edge or satellite network coverage. This paper presents a unified UAV scheduling and routing framework for executing geographically distributed real-time CPS tasks under both periodic and aperiodic arrival models. We address the challenge of minimizing the number of UAVs required while ensuring strict adherence to task deadlines across diverse temporal and spatial settings. At first, we propose an efficient heuristic strategy called UAV Scheduling and Routing Algorithm for Real-time Tasks - Periodic Arrivals (USRART-P), which decomposes applications into task instances and sequentially creates per-UAV routes and schedules within a hyperperiod, maximizing the number of task instances each UAV can cover while meeting deadlines. Adapting to this framework, we develop two additional variants to handle aperiodic CPS tasks: USRART-SA for Synchronous Aperiodic Arrivals (common arrival time, distinct deadlines) and USRART-AA for Asynchronous Aperiodic Arrivals (distinct but known arrival times and deadlines). For the case of periodic tasks, we frame the problem as a constraint optimization formulation which aims to minimize the number of UAVs that are required to generate static hyperperiodic travel routes with task execution schedules for all UAVs, and discuss how the formulation can be adapted for aperiodic tasks. Solution to this formulation using standard off-the-shelf solvers achieves optimality but incurs high computational overheads. Through extensive simulations, we show that USRART exhibits high performance across diverse operational scenarios, varying task distributions, execution demands, and spatial layouts. The results emphasize USRART’s flexibility and effectiveness in real-world UAV-based CPS scenarios, especially in environments with limited resources and infrastructure. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sreyashi Mukherjee and Sachin Yadav and Yedla Anil Kumar and Arnab Sarkar 2025 Is Part Of LIPIcs, Volume 335, 37th Euromicro Conference on Real-Time Systems (ECRTS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ECRTS.2025.4 urn:nbn:de:0030-drops-235822 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2025.4 eng https://creativecommons.org/licenses/by/4.0/legalcode