In-Path Computing-Aware Routing for Low Earth Orbit Satellite Constellations

Abstract

The mismatch between massive spaceborne data generation and constrained satellite-ground links is driving inorbit processing in low Earth orbit (LEO) constellations. Although a single LEO satellite provides limited resources for computation-intensive tasks, task data traverse multiple satellites that collectively offer abundant computing resources, motivating in-path computing-aware routing. This paper proposes DAPS, which jointly partitions a chain-structured task into sequential stages and schedules their execution on in-path satellites to minimize task completion latency. First, DAPS formulates this joint optimization as a binary quadratic programming (BQP) problem, whose direct solution incurs exponential complexity. Then, by exploiting the sequential structure of the task, the BQP is transformed into an equivalent directed acyclic graph (DAG) shortest-path problem, reducing complexity to polynomial time. Finally, to further improve efficiency in mega-constellations, DAPS starts from the initial transmission shortest path and progressively expands nearby candidate computing satellites. Simulation results demonstrate that DAPS consistently outperforms baselines, reducing task completion latency by $\mathbf{1 0. 7 8 \% -44.65\%}$ under various task and constellation settings.