Beyond Time-Expanded Graphs: Novel Continuous-Time Graphs for SAGINs

Abstract

Routing and task-scheduling in space–air–ground integrated networks (SAGINs) are usually time-dependent due to heterogeneous mobility, intermittent connectivity, and continuously-varying link rates. Existing studies mainly rely on the time-expanded graph (TEG) framework to accommodate mobile dynamics by discretizing continuous link variations into uniform time slots (segments). Consequently, overly coarse slots lead to information quantization loss, while overly fine slots result in a granularity mismatch with the minimum transmission unit and the scalability problem. To overcome these limitations, we propose a novel continuous-time graph (CTG) framework that directly characterizes link-rate functions in continuous time and thus eliminates the stringent dependence on slot granularity. Building upon this new framework, we develop a new CTG event-driven routing (CTG-EDR) algorithm that can perform multi-source, multi-task scheduling through event-driven verification of link and buffer calendars. Monte Carlo simulations demonstrate that our proposed new CTG-EDR scheme can achieve a significantly lower latency and a higher task-completion ratio than the representative baselines. Our simulation results justify that the proposed new CTG-EDR scheme is very promising for robust and scalable routing and task-scheduling in highly dynamic SAGIN environments.