Computing-Aware Routing and Coded Load Allocation for LEO Satellite Cloud Computing

Low earth orbit (LEO) satellite cloud computing is a promising paradigm to support latency-sensitive task, avoiding transmitting massive raw data to terrestrial cloud servers. However, straggler effect caused by heterogeneous satellites and multi-hop communication latency in LEO satellite network become bottlenecks for end-to-end task execution latency. In this paper, we incorporate coded distributed computation (CDC) into LEO satellite cloud computing to facilitate collaboration among multiple relay nodes and accelerate the fusion of computation and communication. In our model, the task is split and distributed processed during the end-to-end routing instead of processed on single satellite, while CDC is introduced to mitigate the straggler effect. We derive the expression of computation and communication latency. An average task execution latency minimization problem is formulated and then decoupled into routing and load allocation problems. A novel computing-aware routing and load allocation (CRLA) algorithm based on block coordinate descent method is proposed, where the computing-aware routing path is obtained by dynamic programming to select the optimal relay nodes, and the coded computation and communication load is balanced based on interior point method. Simulation results indicate that the proposed CRLA decreases average task execution latency compared to existing methods.