SECO: Multi-Satellite Edge Computing Enabled Wide-Area and Real-Time Earth Observation Missions

一种多卫星边缘计算赋能的广域实时对地观测任务框架

Rapid advances in low Earth orbit (LEO) satellite technology and satellite edge computing (SEC) have facilitated a key role for LEO satellites in enhanced Earth observation missions (EOM). These missions (e.g., remote object detection) typically require multi-satellite cooperative observations of a large region of interest (RoI) area, as well as the observation image routing and computation processing, enabling accurate and real-time responsiveness. However, optimizing the resources of LEO satellite networks is nontrivial in the presence of its dynamic and heterogeneous properties. To this end, we propose SECO, a SEC-enabled framework that jointly optimizes multi-satellite observation scheduling, routing and computation node selection for enhanced EOM. Specifically, in the observation phase, we leverage the orbital motion and the rotatable onboard cameras of satellites, and propose a distributed game-based scheduling strategy to minimize the overall size of captured images while ensuring full (observation) coverage. In the sequent routing and computation phase, we first adopt image splitting technology to achieve parallel transmission and computation. Then, we propose an efficient iterative algorithm to jointly optimize image splitting, routing and computation node selection for each captured image. On this basis, we propose a theoretically guaranteed systemwide greedy-based strategy to reduce the total time cost (i.e., transmission, computation and queuing delay) over simultaneous processing for multiple images. Extensive experiments based on real-world datasets demonstrate that SECO can achieve up to a 60.7% reduction in overall time cost compared to baselines.

低地球轨道（LEO）卫星技术与卫星边缘计算（SEC）的飞速发展，使得LEO卫星在增强型对地观测任务（EOM）中扮演了关键角色。这类任务（如远程目标检测）通常需要对大范围感兴趣区域（RoI）进行多卫星协同观测，并涉及观测图像的路由与计算处理，以实现精确、实时的响应。然而，鉴于LEO卫星网络固有的动态性与异构性，其资源优化极具挑战性。

为此，我们提出了 SECO，一个由卫星边缘计算赋能的框架，旨在通过协同优化多卫星观测调度、路由以及计算节点选择，来支持增强型对地观测任务。

具体而言:

在观测阶段，我们利用卫星的轨道运动及其搭载的可旋转相机，提出了一种基于分布式博弈的调度策略，在 确保完全观测覆盖的同时，最小化捕获图像的总数据量

在随后的路由与计算阶段，我们首先 采用图像分割技术来实现并行传输与计算 。然后，我们针对每一幅捕获的图像，提出了一种高效的迭代算法，以协同优化其图像分割、路由和计算节点的选择

在此基础上，我们进一步提出了一种具有理论保障的 全系统贪心策略 ，用以降低多图像并发处理场景下的总时间成本（即传输、计算和排队延迟）

基于真实世界数据集进行的大量实验证明，与baseline方法相比，SECO可将总时间成本降低多达60.7%

Introduction

Nowadays, the rapid advancements in low Earth orbit (LEO) satellite technology have significantly enhanced the capacity of LEO satellites in space, which are equipped with high-resolution cameras, communication modules and sophisticated processors [1]. This technological configuration enables LEO satellites to perform timely near-data processing at the edge of LEO satellite networks, thereby giving birth to the concept of satellite edge computing (SEC) [2]. Furthermore, LEO satellites with inter-satellite links (ISLs) [3] can connect with their adjacent satellites, thereby enhancing the utilization of inter-satellite resources to boost service performance. Serving as the centerpiece of SEC, LEO satellites have been extensively utilized in various Earth observation missions (EOM) [4]–[6]. These missions encompass a wide range of critical applications, including carbon emission monitoring [7] and emergency response to diverse natural weather events [8].

The EOM typically involves: i) observation phase, i.e., making observations of a region of interest (RoI), and ii) processing phase, i.e., computationally processing the captured RoI images and routing the results to the designated ground station. In terms of the observation phase, major work utilizes a single satellite to handle the observation of a RoI [6], [9], [10]. Nonetheless, in scenarios like earthquake warnings, observing a large RoI area is crucial for a more accurate and satisfactory response [5], [7], [11]. Therefore, as shown in Fig. 1, the multi-satellite cooperative observation becomes indispensable due to the limited observation range of a single satellite. Regarding the processing phase, EOM is often built upon advanced functionalities such as deep neural network (DNN) inference [12] or multi-stage image compression (MIC) [13], necessitating high efficiency to ensure real-time response for time-sensitive missions [14]. Given these attributes, we term this novel EOM paradigm as wide-area and real-time EOM.

To achieve wide-area and real-time EOM, several challenges must be addressed. First, as depicted in Fig. 2, crossobservation areas by ascending and descending satellites divide the RoI into shards. Notably, for the given boundary shard, the satellite capture properties lead to divergent capture sizes for ascending and descending satellites [5], [15]. For instance, for boundary shard A in Fig. 2, an ascending satellite only needs to capture the shadow area during its motion direction, while a descending satellite needs to capture the entire segment. Moreover, the observation regions for each satellite are time-varying, due to its dynamic property, i.e., orbital motion and the rotatable onboard camera. In this way, efficient sustained cooperation for multiple satellites in the observation phase is nontrivial. Second, the computation of each shard in SEC involves tasks such as DNN inference or MIC that are computationally intensive. To fully leverage the resources within LEO satellite networks, these tasks can be divided into subtasks and assigned to satellite nodes [16]. However, the inherent dependencies within the computation workflow pose a challenge [17]. Additionally, the heterogeneous nature of satellite hardware resources further complicates the embedding of subtasks within the LEO satellite networks. Finally, as shown in Fig. 1, since the satellite is in motion to capture shards, different satellites might capture shards simultaneously, potentially causing congestion (i.e., queuing delays) on computation nodes and transmission links

[18] when they are transmitting and computing. Hence, the complexity of optimizing the processing phase is significantly escalated while considering these queuing delays.

To address the above challenges, we propose SECO, a SECenabled framework for jointly optimizing multi-satellite observation scheduling, routing and computation node selection to facilitate wide-area and real-time EOM. In the observation phase, we strategically employ game theory to enable distributed inter-satellite interactions, thus achieving an efficient multi-satellite observation scheduling for a large RoI area. This approach considers the capture and dynamic properties of satellites, enabling the reduction of the overall captured image size while ensuring full RoI coverage. In the processing phase, to tackle the challenge presented by the dependent property in computation tasks (i.e., DNN inference or MIC) and clarify the mapping of processing for each shard in LEO satellite networks, we model the LEO satellite networks as a layered graph to represent the routing and computation process for embedding computation tasks. We theoretically prove that this model scheme yields an integer optimal solution under linear relaxation, thus enabling efficient optimization of the processing for each shard while considering the queuing delay. Additionally, we augment processing efficiency via shard splitting, which allows for parallel transmission and computation. Supporting this, we design an iterative algorithm for jointly shard splitting, routing and computation node selection for each shard. Finally, due to the satellites capturing shards in motion, when multiple shards are captured simultaneously, a theoretically guaranteed system-wide greedy-based strategy is proposed to optimize the time cost at a system level.

In summary, the main contributions are as follows:

• We propose SECO, a comprehensive framework that optimizes observation scheduling, routing and computation node selection for wide-area and real-time EOM, which has great potential in boosting the real-time responses (i.e., to enable efficient DNN inference or MIC, etc).

• We promote a distributed observation scheduling strategy by resorting to the potential game theory as the algorithm design tool based on the orbital motion and rotatable camera of each satellite. To our knowledge, it is the first strategy considering multi-satellite observations for the large RoI area and fine-grained boundary-side scheduling.

• In SECO, we employ shard splitting to facilitate parallel transmission and computation, thereby reducing time costs. Then an efficient iterative algorithm is proposed to jointly determine the optimal shard splitting, routing and computation node selection for each shard. Further, a system-wide greedy-based strategy is designed to optimize the time cost at the system level, providing performance guarantees through approximation ratio analysis.

• We conduct extensive experiments based on real-world datasets, showing that SECO can achieve up to a 60.7% time cost reduction compared to other baselines.

如今，低地球轨道（LEO）卫星技术的飞速发展显著增强了在轨LEO卫星的能力，这些卫星配备了高分辨率相机、通信模块和先进的处理器 [1]。这种技术配置使LEO卫星能够在卫星网络的边缘执行及时的近数据处理，从而催生了卫星边缘计算（SEC）的概念 [2]。此外，具备星间链路（ISL）[3] 的LEO卫星可以与其相邻卫星连接，从而提高星间资源的利用率以提升服务性能。作为SEC的核心，LEO卫星已被广泛应用于各种对地观测任务（EOM）[4]–[6]。这些任务涵盖了众多关键应用，包括碳排放监测 [7] 和对各类自然气象事件的应急响应 [8]。

对地观测任务通常包括：i) 观测阶段，即对感兴趣区域（RoI）进行观测；以及 ii) 处理阶段，即对捕获的RoI图像进行计算处理，并将结果路由至指定的地面站。在观测阶段，现有主要工作利用单颗卫星来处理对RoI的观测 [6], [9], [10]。然而，在地震预警等场景中，观测大范围的RoI对于实现更精确和理想的响应至关重要 [5], [7], [11]。因此，如图1所示，由于单颗卫星的观测范围有限，多卫星协同观测变得不可或缺。在处理阶段，EOM通常构建在深度神经网络（DNN）推理 [12] 或多级图像压缩（MIC）[13] 等高级功能之上，这要求极高的效率以确保时间敏感型任务的实时响应 [14]。鉴于这些特性，我们将这种新颖的EOM范式称为广域实时对地观测任务。

为实现广域实时对地观测任务，必须解决几项挑战。首先，如图2所示，升轨和降轨卫星的交叉观测区域将RoI分割成多个分片（shards）。值得注意的是，对于给定的边界分片，由于卫星的捕获特性，升轨和降轨卫星的捕获尺寸不同 [5], [15]。例如，对于图2中的边界分片A，一颗升轨卫星在其运动方向上只需捕获阴影区域，而一颗降轨卫星则需要捕获整个区段。此外，由于卫星的动态特性（即轨道运动和可旋转的星载相机），每颗卫星的观测区域是时变的。因此，在观测阶段实现多卫星间高效且持续的协同极具挑战性。其次，在SEC中，每个分片的计算涉及DNN推理或MIC等计算密集型任务。为了充分利用LEO卫星网络内的资源，这些任务可以被划分为子任务并分配给卫星节点 [16]。然而，计算工作流中固有的依赖关系构成了一项挑战 [17]。此外，卫星硬件资源的异构性进一步增加了在LEO卫星网络中嵌入子任务的复杂性。最后，如图1所示，由于卫星在运动中捕获分片，不同卫星可能同时捕获分片，这可能在它们进行传输和计算时导致计算节点和传输链路的拥塞（即排队延迟）[18]。因此，当考虑到这些排队延迟时，优化处理阶段的复杂性会显著增加。

为应对上述挑战，我们提出了 SECO，一个卫星边缘计算赋能的框架，旨在协同优化多卫星观测调度、路由和计算节点选择，以促进广域实时对地观测任务。在观测阶段，我们策略性地采用博弈论来实现分布式的星间交互，从而为大范围RoI实现高效的多卫星观测调度。该方法考虑了卫星的捕获和动态特性，能够在确保RoI完全覆盖的同时，减少捕获图像的总数据量。在处理阶段，为应对计算任务（即DNN推理或MIC）中的依赖性挑战，并明确每个分片在LEO卫星网络中的处理映射关系，我们将LEO卫星网络建模为一个分层图，以表示嵌入计算任务的路由和计算过程。我们从理论上证明了该模型方案在线性松弛下能够产生整数最优解，从而在考虑排队延迟的情况下，能够对每个分片的处理过程进行高效优化。此外，我们通过分片分割来增强处理效率，实现并行传输和计算。为此，我们设计了一种迭代算法，用于协同优化每个分片的分割、路由和计算节点选择。最后，由于卫星在运动中捕获分片，当多个分片被同时捕获时，我们提出了一种具有理论保障的全系统贪心策略，以在系统层面优化时间成本。

综上所述，本文的主要贡献如下：

• 我们提出了 SECO，一个用于广域实时对地观测任务的综合框架，它协同优化了观测调度、路由和计算节点选择，在提升实时响应（如实现高效的DNN推理或MIC等）方面具有巨大潜力

• 我们基于卫星的轨道运动和可旋转相机，借助势博弈理论作为算法设计工具，提出了一种分布式观测调度策略。据我们所知，这是首个针对大范围RoI并考虑了精细化边界调度 (fine-grained boundary-side scheduling) 的多卫星观测策略

• 在 SECO 中，我们采用分片分割技术来促进并行传输和计算，从而降低时间成本。接着，我们提出了一种高效的迭代算法，以协同确定每个分片的最优分割方案、路由和计算节点。此外，我们还设计了一种全系统贪心策略，在系统层面优化时间成本，并通过近似比分析为其提供了性能保障

• 我们基于真实世界数据集进行了大量实验，结果表明，与其他基线方法相比，SECO可实现高达 60.7% 的时间成本降低

仅代表个人观点, 不喜勿喷

读完abs和intro, 这篇文章我就不想看了:

1. idea 毫无新意 (ML on Sat + 图像分割 + 贪心), ASPLOS2020-OEC 完全一致啊
2. 问题很奇怪，像是在强行灌输背景
3. 根据上述1和2, 竟然还没有引用 ASPLOS 2020 OEC ...

好奇这文章靠啥中的... 可能是美工吧🤔

这篇文章后面我只读一下 related work 和 conclusion, 别的真懒得看了😅