基于多维梯度的卫星集群高可靠协同计算方法

马步云/MA Buyun，任智源/REN Zhiyuan，李赞/LI Zan

（西安电子科技大学综合业务网理论及关键技术国家重点实验室，中国 西安 710071）

(State Key Laboratory of Integrated Services Networks,Xidian University,Xi’an 710071,China)

由于具有星地传输距离短、覆盖范围广等优势，基于低轨（LEO）卫星的通信系统[1]受到业界广泛关注。同时，大量数据在传输过程中仍需进一步处理才能被使用（例如，卫星采集的图像需要经过去噪、特征提取等后才可被使用）。然而，受限于卫星的载荷能力和宇宙射线的影响[2]，单颗卫星的计算能力难以大幅提升，很难独自完成计算密集型任务。而将海量数据转发至地面云计算中心，利用云平台强大的计算资源处理数据[3]，虽然可有效降低计算时延，但是会带来过高的通信开销，仍难以有效满足业务需求。因此，研究端到端业务计算方法势在必行。通过协作可使卫星展现出强大的传输与计算数据的能力。

目前，大多数研究者致力于单方面优化路由[4-6]或业务卸载策略[7-10]，将两者统一考虑的很少。而现有的端到端信息处理方案均为集中式业务调度[11-13]，其中，中心管理节点负责管理网络并制订合理的业务调度方案，LEO集群根据预先制订好的方案相互协作。然而，LEO卫星数目众多且计算资源有限，真实的卫星网络很难拥有一个强大的中心管理节点（该节点一旦发生故障，整个网络将瘫痪）。此外，由于卫星工作在复杂的宇宙环境中，极易受到干扰，如采用集中式调度模式处理业务，调度方案中的任何一颗卫星出现故障都将导致任务失败，很难满足业务的可靠性需求。基于此，针对单星计算能力弱、节点故障率高的分布式LEO集群，亟需一种分布式低时延高可靠的端到端业务计算方法，以满足业务需求。

本文面向分布式LEO集群，提出了一种去中心式端到端信息处理技术方法。该方法首先依托时空扩展图（TEG）来屏蔽LEO集群的高动态特性，随后对端到端业务调度进行理论建模并设计分布式业务调度算法。当任务到来时，每颗卫星基于其邻居节点信息，独自运行该算法来选择下一跳节点，并逐步完成数据的传输与计算。该算法提出了一种新的度量梯度指标（业务调度效率）作为选择下一跳节点的依据。该梯度指标综合考虑了节点的计算能力、链路传输速率、故障率、至目标卫星的跳数，可有效降低系统时延，提高系统可靠性。

1 系统模型

分布式LEO集群系统架构如图1所示。其中，为不失一般性，假设地面站定时向LEO集群广播全局拓扑信息，每颗卫星可计算自身到结果接收卫星的跳数。当任务到达时，每颗卫星根据自身相邻节点的信息逐步选择下一节点，并完成端到端业务计算。

▲图1 低轨集群系统架构图

1.1 LEO网络模型

为屏蔽LEO集群的动态性，本节依托LEO卫星运行轨道参数构建TEG模型。

令N={n1,…,np,…,ns}表示 LEO集群，以地心为坐标原点，以赤道平面为X轴、Y轴所在平面，Z轴通过地心并垂直于赤道平面指向北极，建立空间直角坐标系。则在任意时刻t时，np(np∈N)的位置坐标可通运行轨道计算得到。np与no(np,no∈N,p≠o)之间的距离可通过式（1）来计算。

定义t时刻np与no之间的链路状态为，并可表示为式（2）：

其中，r*为星间链路的设计速率，为t时刻np与no的理论传输速率。表示np与no连通且链路传输速率为r*，反之则表示np与no链路中断。可根据香农公式得出式（3）：其中，B为星间链路带宽，σ2为高斯白噪声方差，为t时刻的信号接收功率。在星间链路中，信号传输损耗主要为自由空间传输损耗[14]。因此，可由式（4）来表示：

其中，Gr、Pt、Gt分别表示信号接收增益系数、信号发射功率和信号发射增益系数，λ为载波波长。则式（2）可进一步表示为：

基于式（5），通过遍历可获得LEO集群拓扑。此时，以LEO集群某一时刻状态为起点，将系统运行周期T等分为n个连续时隙，长度定义为Δ=T/n。假设时隙内拓扑稳定不变，则LEO集群N可表示为N=(NT,ET)，其中NT={N1,…,Nn}为节点集合，ET为边集合，如图2所示。

▲图2 低轨集群时空扩展图模型

（1）时隙内边的权重。任意时隙∀q∈T内，边的权重为节点传输单位数据量到节点的时延，如式（6）所示：

则q时隙内LEO集群可表示为式（7）：

（2）时隙间边的权重。数据在传输过程中可能存在由链路中断所导致传输失败的情况，因此，需要定义时隙间边的权重，即数据到达卫星节点时，当前时隙的剩余时间，如式（8）所示：

则相邻时隙q,q+1∈T间LEO集群可表示为式（9）：

此时，LEO集群的TEG模型可表示为式（10）：

1.2 端到端业务计算理论模型

基于TEG，本节提出端到端业务计算理论模型。为不失一般性，本节按照子业务间的依赖关系建立业务有向无环图（DAG）模型。同时，根据文献[15]，任何结构的DAG均可解析为串行DAG，因此，本文仅考虑串行DAG。

定义 DAG 为 Ω =(Ψ,ς)。其中，Ψ ={φ1,…,φl}为节点集合，表示子业务集群，φ1为业务起点，φl为业务终点；ς为边集合，表示子业务间的依赖关系。此外，φi∈ Ψ 由元组{Di,ηi,εi}表征，其中Di为输入数据量，ηi为数据压缩系数，εi为计算复杂度系数。同时，定义为子任务φj的先驱节点集合。此时，业务Ω在LEO集群中的调度可转化为DAG至TEG的映射规则，如图3所示。

▲图3 DAG至TEG的映射示例

（1）节点映射规则

我们首先定义Υ。Ψ→NT表示子业务节点Ψ至卫星节点NT的映射。具体地，如式（11）所示，业务起点映射至业务发起卫星，业务终点映射至结果接收卫星，中间业务节点映射至任意卫星。为不失一般性，假设子业务不可再分，所有子业务均在单颗卫星上计算，考虑到传输过程中链路可能断开，此时数据需在卫星上缓存，经过虚拟链路至下一时隙，ρi为跨时隙数目。

（2）边映射规则

ς→ET表示DAG有向边ς至TEG无向边ET的映射，以反映子业务间的依赖关系。具体地，如式（12）所示，将DAG的有向边 ∀(φi,φj)∈ς映射为图N中 Υ(φi)至 Υ(φj)之间的最短路由。

1.3 分布式端到端业务调度算法

为了实现在分布式LEO集群中数据的“边传输边计算”，本节提出分布式端到端业务调度算法，如算法1所示。该算法主要由3个步骤构成：（1）任务到来时，通过广播发现邻居节点，并获取其必要的状态信息以用于计算任务调度效率（TSE）；（2）计算邻居节点的TSE，并根据TSE选择下一跳节点；（3）判断当前时隙剩余时间是否充足，若充足则将数据发给已确定好的下一跳节点，否则返回步骤2，并基于下时隙信息重新选择下一跳节点。

基于上述端到端业务计算理论模型分析，算法需统一考虑节点的计算能力和链路状态以实现端到端业务计算，而由于缺乏中心节点的统一调度，仅考虑计算能力和链路状态可能会导致数据的反向传输。因此，需要引入目标节点位置信息以实现数据的定向传输，同时为了保证数据传输的可靠性，节点故障率也需要被考虑进算法中。基于以上分析，本节定义TSE梯度指标，综合考虑了节点的计算能力、链路状态、故障率、距目标节点跳数多维梯度信息，如式（13）所示：

其中，HΥ(φi)Υ(φl)为映射节点 Υ(φi)至结果接收卫星Υ(φl)沿最短路径所需跳数，χΥ(φi)为节点 Υ(φi)的故障率，fΥ(φi)为节点 Υ(φi)的计算能力，eΥ(φj)Υ(φi)为子任务φi的前向节点φj的映射节点Υ(φj)沿最短路径至 Υ(φi)的传输速率。由式（13）可知，距目标节点越近，节点计算能力越强，故障率越低、链路传输速率越快，TSE就越小，该节点的调度效率也就越高。

算法1分布式端到端业务调度算法

输入：DAG模型，TEG

步骤1：任务到来时，通过广播发现邻居节点并获取其多维状态信息，包括计算能力、链路状态、故障率、距目标节点跳数；

步骤2：根据式（13）计算各邻居节点的TSE指标，并选取TSE最小的节点为下一跳节点；

步骤3：判断此时将数据传输至下一跳节点的时延是否小于当前剩余时隙，若小于则传输；否则就缓存数据，返回步骤2，并根据TEG预测下时隙的TSE指标，重新选择下一跳节点。

输出：下一跳节点

2 仿真与评估

为验证本文提出的分布式业务调度方案的有效性，本节将该方案同集中式方案进行比较。在比较过程中，所有实验均基于相同假设。在集中式业务调度模式下，中心节点运行集中式业务调度算法以获取传输路径上的关键计算节点。集中式业务调度算法采用经典的DAG调度算法-异态最早结束时间（HEFT）算法[15]。值得注意的是，由于集中式业务调度算法依赖较多的计算资源，卫星节点虽具备一定计算能力，但很难运行集中式业务调度算法。本节同时将基于TSE指标选择下一跳节点的分布式业务调度算法（记为Proposed）同随机式（记为Random）和贪婪式（记为Greedy）两种常用业务调度算法进行比较，并对仿真结果进行分析与讨论。

2.1 仿真场景及参数设置

本文考虑由15颗低轨卫星构成的卫星集群。其中，低轨卫星均取自铱星星座（轨道高度780 km）。本文中，我们利用卫星工具包（STK）获取网络真实连通情况。仿真时间段为2021年4月26日00:00—00:30。本文仿真平台为Python 3.7，采用的业务图为图1中的DAG。参照文献[11]和[16]，仿真参数如表1所示。此外，为不失一般性，本文所有仿真结果均基于3 000次蒙特卡洛实验。

▼表1 基本参数

为了分析与评估性能，我们考虑端到端业务处理时延和任务成功率两个指标。

（1）端到端业务处理时延

基于1.2节的DAG至TEG的调度规则，端到端业务处理时延可建模如下。

进行到子任务φi时的处理时延如式（14）所示：

其中，Tcomp(φi)表示φi的计算时延，Taccu(φi)表示φi前向节点的累积时延。fΥ(φi)为节点 Υ(φi)的计算能力，表示卫星节点Υ(φi)中央处理器（CPU）每秒运行的周期数。

因此，Ω的业务处理时延为最后一个子任务φl的处理时延，如式（15）所示。

（2）任务成功率α

任务成功率α是成功完成的任务数与总试验次数的比值，如式（6）所示。

其中，Nsucc为成功完成的任务数，Ntotal为总实验次数。

2.2 仿真结果与分析

2.2.1 可靠性性能

图4比较了不同业务调度模式在不同环境下的可靠性性能。其中，任务量大小为100 Mbit。值得注意的是，卫星的故障概率包括卫星器件故障概率和卫星受到环境干扰（如发生“0-1翻转”等）导致任务失败的故障概率。因此，为不失一般性，本节设置了4种不同环境：最佳环境、良好环境、恶劣环境、混合环境。在最佳环境中，卫星的故障概率设置为0，即χi=0；在良好环境中，假定卫星的故障概率均匀分布，即χi～U([0,0.5%])；在恶劣环境中，χi～U([1%,3%])；在混合环境中，某些卫星的故障概率为χi～U([0,0.5%])，另外一些卫星的故障概率为χi～U([1%,3%])。由图 4 可知，在最佳环境下，分布式业务调度和集中式业务调度的任务成功率均为100%。这是因为在理想环境中，不会出现卫星故障，任务能100%完成。然而，由于理想情况根本不存在，因此本文研究了3种现实环境下的可靠性性能。由图5可知，集中式业务调度模式的可靠性性能在各种环境下均比较低。恶劣环境中，集中式业务调度模式的任务成功率仅为55.0%。相比之下，分布式业务调度的任务成功率为84.4%。这是因为，分布式业务调度仅须保障当前执行业务节点在执行业务期间不会发生故障，而集中式业务调度模式须保障业务调度方案中所有节点在执行任务之前均不会发生故障。

▲图4 不同环境下不同业务调度模式的可靠性性能比较

2.2.2 时延性能

图5比较了不同计算范式的时延性能，即云计算、本地计算和协同计算。其中，协同计算可进一步分为集中式业务调度和分布式业务调度，并且工作环境为混合环境。由图5可知，当任务量较小时，3种计算范式均表现出良好的时延性能。但随着任务量的增加，云计算的时延也迅速增加。这是因为云计算中心距卫星较远，导致传输时延较高。而本地计算虽可避免较高的通信开销，但由于单星计算能力有限，计算时延也较高。对于协同计算，由于卫星集群具备强大的计算能力，且卫星之间距离较近，因此，随着数据量的增加，其时延仍在可接受范围之内。

▲图5 不同计算范式的时延性能比较

由图5可知，分布式业务调度的时延略高于集中式业务调度。但应注意到，混合环境下，在处理100 Mbit的数据时，分布式业务调度的任务成功率比集中式业务调度提升了21.3%，而时延仅增加了6.21%，即以较小且可接受的时延为代价换取了可靠性性能的大幅度提升。

2.2.3 多种算法可靠性及时延性能分析

本节比较了基于TSE指标的算法（记为Proposed）同随机式（记为Random）和贪婪式（记为Greedy）算法的时延性能和可靠性性能，分别如图6、图7所示。

▲图6 不同算法时延性能比较

▲图7 不同算法可靠性性能比较

图6比较了不同算法的时延性能。其中，工作环境为混合环境。由图6可知，当任务量较小时，3种算法时延差别不明显。而随着任务量的增加，所提算法的时延明显低于其他两种算法。例如，当任务量为500 Mbit时，Proposed、Greedy、Random的时延具体分别为76.14 s、83.08 s、90.94 s，所提算法比其他两种算法的时延分分别低了8.35%、16.27%。这是因为，Random算法随机选取下一跳节点，并未考虑其计算能力，同时Greedy算法选取计算能力最强的节点作为下一跳节点，并未考虑边的传输能力和传输方向，因此时延性能均不如Pro⁃posed算法。

图7比较了不同算法的可靠性性能，其中，任务量为100 Mbit。可以看出，除最佳环境外，在其他环境下所提算法的任务成功率均高于其他两种算法。这是因为Random和Greedy算法在选择下一跳节点时，均未考虑节点的故障概率，因此可靠性性能不如所提算法。

3 结束语

本文面向分布式LEO集群，提出了分布式端到端信息处理技术。首先我们构建TEG将LEO集群动态拓扑稳态化，随后构建端到端信息处理理论模型并提出分布式业务调度算法。该算法通过综合考虑计算资源、通信资源、至目标节点跳数、节点故障率多维信息来选取下一跳节点，并逐步完成数据的传输与计算。仿真结果表明，所提分布式业务调度技术以牺牲较小时延为代价，有效地提升了业务的执行成功率。

致谢

本研究得到西安电子科技大学综合业务网理论及关键技术国家重点实验室程文驰老师的帮助，谨致谢意！