Network-Wide Task Offloading With LEO Satellites: A Computation and Transmission Fusion Approach

Jiaqi Cao, Shengli Zhang, Qingxia Chen, Houtian Wang, Mingzhe Wang, Naijin LiuarXiv 2022 · DOI · arXiv

TL;DR

This paper tackles the challenge of efficiently offloading computing tasks from satellites to ground stations or other satellites. They propose a novel "metagraph-based computation and transmission fusion" approach that unifies the representation of both data transmission and computation, allowing for network-wide optimization and significantly reducing overall task delay compared to existing methods.

What Problem Does This Paper Address?

In space missions, especially those involving remote sensing, the demand for computational power is rapidly increasing due to advancements in image processing and machine learning. Traditional methods of offloading these tasks to ground servers face a significant bottleneck: the slow and unreliable satellite-to-ground links (SGLs). While offloading tasks to Low Earth Orbit (LEO) satellites directly (visible offloading) offers a solution, it suffers from uneven network loads, leading to overloaded visible satellites and underutilized resources elsewhere. This paper addresses the need for a network-wide offloading strategy that can leverage all available computing resources, both on visible and invisible LEO satellites, as well as ground servers, to minimize task completion delay.

Methods

The core of the proposed solution lies in a novel way of representing and optimizing task offloading.

  • Virtual Edges for Computation: To unify the representation of transmission and computation, the authors introduce "virtual edges." They create a duplicate of the network and connect each node in the original network to its corresponding node in the duplicate with a virtual edge. These virtual edges represent the computation process, while actual edges represent data transmission. This allows both processes to be treated uniformly within a graph framework.
  • Metagraph for Multi-Tier Networks: To handle the complexity of multi-tier networks (e.g., RS satellites, LEO satellites, and ground stations), they employ a "metagraph." A metagraph is essentially a graph of graphs, where each individual network tier is represented as a graph, and connections between these tiers (inter-tier visibility) are represented by edges in the metagraph. This allows for a holistic view and optimization across all network tiers.
  • Shortest Path Optimization: By assigning appropriate weights (representing transmission and computation delays) to the edges in the metagraph, the network-wide task offloading problem is transformed into a shortest path problem. The algorithm then finds the optimal path that minimizes the overall delay for task completion.

Datasets

The paper utilizes data from the "Internet Census 2012" to estimate the network connection index of geographical zones, which informs the task arrival rates. The simulation parameters are based on state-of-the-art LEO satellite technologies and typical remote sensing scenarios. No new benchmark datasets were introduced.

Key Insights and Ideas

  • Network-Wide Offloading is Crucial: The paper strongly advocates for extending offloading targets beyond visible satellites to the entire network to overcome the limitations of uneven load distribution and resource underutilization.
  • Unified Representation is Key: Representing both computation and transmission as edges in a graph (using virtual edges for computation) is a powerful abstraction that enables joint optimization.
  • Metagraphs for Heterogeneous Networks: The metagraph approach effectively integrates different network tiers, allowing for seamless offloading decisions across diverse network components.
  • Invisible Satellites are Valuable Resources: The proposed scheme's ability to leverage computing resources on invisible satellites is a significant advantage, especially in scenarios with high demand.

Key Results

The proposed fusion offloading scheme demonstrates significant improvements over existing methods:

  • Reduced Overall Delay: The weighted average delay is reduced by up to 87.51% compared to the ground offloading scheme and 18.70% compared to the visible offloading scheme, especially under high network loads (L=300).
  • Lower Growth Rate: The fusion offloading scheme exhibits the lowest growth rate in delay as network load increases, indicating better scalability.
  • Robustness to Network Properties: The scheme's performance remains superior even with lower computing capabilities of LEO satellites and lower SGL data rates.
  • Impact of Task Properties: The superiority of the proposed scheme becomes more pronounced with higher computational requirements of tasks.

Limitations and Future Work

  • Dynamic Network Modeling: The current model uses virtual nodes to represent the dynamic LEO satellite network. Future work aims to construct a fusion network that models the dynamics of the LEO satellite network directly, rather than relying on virtual nodes.
  • Energy and Storage: The paper assumes sufficient energy and storage resources on LEO satellites, which are left for future work to investigate.
  • Algorithm-Level Comparison: The current study focuses on scheme-level comparison, and future work may involve detailed comparisons of individual algorithms within these schemes.

Summary updated

BibTeX
@misc{cao2022network,
  author = {Jiaqi Cao and Shengli Zhang and Qingxia Chen and Houtian Wang and Mingzhe Wang and Naijin Liu},
  title = {{Network-Wide Task Offloading With LEO Satellites: A Computation and Transmission Fusion Approach}},
  year = {2022},
  eprint = {2211.09672},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2211.09672},
}
Figure