考虑任务依赖的卫星边缘计算资源分配与卸载决策算法*

方 海,赵 扬,高 媛,杨 旭

(西安空间无线电技术研究所，陕西 西安 710100)

1 引言

卫星是6G网络的重要节点[1 - 4]，以星链为代表的卫星星座正在快速地发展[5]。在传统的卫星任务处理模式中，数据传输到地面数据中心进行处理，随着6G网络中卫星业务的不断扩展和丰富，海量数据将导致更长的数据传输时间和更大的带宽压力。

边缘计算的出现为用户利用网络边缘节点的计算能力进行数据处理提供了新的模式[6]。在边缘计算模式下，将分散在每颗卫星上的计算资源整合到同一架构中，实现分散卫星计算能力的融合，为卫星处理海量数据任务和时敏任务提供了统一的在轨边缘计算能力，能够更充分利用在轨计算资源，节省海量数据传输带宽，提高实时数据分析能力，实现卫星资源的高效利用。任务卸载是边缘计算中的关键技术之一，即何时将何任务卸载到哪个边缘处理器，任务卸载决策算法是系统高效运行的关键。

对于卫星边缘计算，文献[7-9]研究了卫星边缘计算应用场景，给出了卫星网络边缘计算的体系架构。在卸载决策算法上文献[10,11]基于深度强化学习,文献[12]基于博弈论进行了卫星边缘计算场景中多个移动设备竞争多颗卫星星载资源的卸载决策，以降低系统时延和能耗。文献[13,14]通过将原始非凸问题转换为凸问题，解决了同时满足低轨卫星覆盖时间和计算能力约束的用户总能耗最小化问题。以上算法均将待卸载任务视为不可分割的实体，用户任务必须作为一个整体在本地或边缘处理器执行。但是将用户任务分解成子任务，可以提高卸载效率[15]。文献[15]中子任务必须顺序地执行,但是在实际中有依赖关系的子任务必须顺序执行，相互独立的子任务可以并行执行。文献[16-18]考虑了子任务之间的依赖关系，但是均没有考虑子任务待处理数据发送时的无线资源分配。虽然子任务的卸载可以减少任务节点的能源消耗，但因为卸载的子任务会导致任务节点和边缘处理器之间的通信延迟，总体任务延迟还与任务待处理数据通信的无线资源分配有关。

随着卫星技术的发展，多处理器系统已实现星载应用。与现有工作不同，本文考虑星载多处理器系统环境，提出了一种联合无线资源分配同时考虑子任务依赖关系的卸载决策调度算法，且基于启发式搜索算法，在保证任务依赖性的同时能够降低任务延迟和能量消耗。

2 系统模型

卫星网络包含高轨卫星和低轨卫星，高轨卫星相对于低轨卫星一般是大卫星，相对有较高的整星功率和计算能力。为了充分利用卫星网络的计算能力，本文重点解决低轨卫星计算任务卸载到高轨卫星的计算卸载问题。

2.1 卫星边缘计算架构

高低轨协同的卫星边缘计算网络体系结构如图1所示。低轨道卫星群位于卫星网络边缘计算层的网络边缘。该层卫星节点较多，搭载的嵌入式计算设备算力有限，但可以为空间或地面用户提供高可靠性、低延迟的边缘处理能力。高轨卫星通信覆盖范围广，可以实现对低轨卫星群的全覆盖，高轨卫星计算和带宽资源充足，适合处理计算量大的复杂任务，同时可以负责卫星边缘计算网络资源的管理。低轨卫星计算任务可以卸载到所接入的高轨卫星，也可以在本地计算。低轨卫星的计算任务可以是低轨卫星本身产生的，也可以是接入该卫星的陆海空天等终端产生的。

Figure 1 System structure of satellite edge computing图1 卫星边缘计算系统结构图

2.2 任务模型

2.3 通信模型

在高低轨协同计算的卫星网络中，低轨卫星子任务可以卸载到高轨卫星中的任一处理器执行或在本地执行。将低轨卫星u到高轨卫星的可用带宽W分成Q个子带，低轨卫星u的任务可以分配使用bu个子带，0≤bu≤Q。仅考虑低轨卫星到高轨卫星链路的带宽分配，高轨卫星内部处理器之间通过内部高速交换网络全互联，设高轨卫星内部处理器之间的传输速率为R。

低轨卫星u到高轨卫星的链路信噪比如式(1)所示：

(1)

其中，U为低轨卫星集合,N0为背景噪声功率谱密度;hu为低轨卫星u到高轨卫星的上行信道增益，包括路损和天线增益;pu为低轨卫星u卸载任务时数据发送的发射功率，0

低轨卫星u到高轨卫星的传输速率如式(2)所示：

Ru=(W/Q)bulb(1+γu)

(2)

对于所有存在子任务卸载到高轨卫星的低轨卫星u，带宽资源分配策略B={bu}，bu∈{1,2,…,Q};所有子任务在低轨卫星本地执行时bu=0。

同样，功率资源分配策略P={pu}，pu>0，所有子任务在低轨卫星本地执行时pu=0。

2.4 计算调度模型

高轨卫星包含M个完全互联的处理器，高轨卫星处理器集合S={s1,s2,…,sM}，每个处理器sj的计算能力为fsj。低轨卫星集合U={u1,u2,…,uN}，低轨卫星处理器集合为S′={s′u|u∈U}，设fu为低轨卫星u的本地计算能力，计算能力单位为cycles/s。

3 任务卸载与资源分配算法

卫星边缘计算卸载问题的目标是为应用中的子任务分配合适的处理器，以最小化系统开销。系统开销根据任务延迟和能耗来评估。本节首先对该问题进行形式化，之后提出一种启发式卸载算法来有效地进行任务卸载决策和无线资源分配。

3.1 问题描述

为了在系统约束下降低任务平均执行延迟和低轨卫星总功耗，首先提出时延和能耗模型，将优化问题形式化，设低轨卫星u完成任务Vu的时延为tu，如式(3)所示:

tu=EFT(u,|Vu|),u∈U

(3)

EFT(u,k)的计算如式(4)所示：

(4)

EST(u,k,m)=max{ap(u,k,m),at(u,k,m)}

(5)

at(u,k,m)=

(6)

(7)

其中,Rm′,m表示2个处理器之间的通信速率，其计算如式(8)所示：

(8)

Tm′,m为路径传播时延，其计算如式(9)所示:

(9)

其中，Lm′,m为低轨卫星和高轨卫星的距离,c为光速。

式(3)是递归定义，递归退出条件如式(10)所示：

EST(u,1,m)=0，∀m∈S∪S′,∀u∈U

(10)

每一个任务的起始子任务最早开始时间都是0。

对于低轨卫星u的能耗Eu，分别由本地计算功率Eu,c和传输发射功率Eu,t决定，如式(11)所示：

Eu=Eu,c+Eu,t

(11)

传输发射功率Eu,t的计算如式(12)所示：

Eu,t=pudu/Ru

(12)

其中,du为所有子任务前序在本地、后序在高轨卫星的任务的数据的和，也即需要从低轨卫星发送到高轨卫星的数据量的总和，如式(13)所示：

(13)

Eu,c和低轨卫星本地执行任务有关，是本地执行任务的总功耗，设低轨卫星u本地执行任务单位时间内的能耗为εuJ/s,则Eu,c的计算如式(14)所示：

(14)

综合时延和能耗，将低轨卫星u的开销定义如式(15)所示：

Cu=αutu+βuEu

(15)

其中，αu和βu分别为时延代价和能耗代价在系统开销中的权重，αu,βu∈[0,1]，αu+βu=1，∀u∈U。通过卸载决策实现无线资源和计算资源的联合优化分配，从而降低低轨卫星系统整体的卸载开销。

将系统开销定义为所有低轨卫星的卸载开销的加权和，如式(16)所示：

(16)

其中，λu为每个低轨卫星的权重。将联合任务卸载和资源分配问题描述为系统开销最小化问题，如式(17)～式(22)所示：

(17)

(18)

(19)

(20)

(21)

0

(22)

其中，Uoffload为存在子任务卸载到高轨卫星的低轨卫星集合，式(18)和式(19)是处理器分配约束，表示每个子任务可以本地执行或者卸载到高轨卫星某个处理器上执行；式(20)是子任务依赖约束，表示子任务的调度必须满足子任务依赖关系；式(21)是无线资源分配约束，即分配的总带宽不能超过系统总带宽；式(22)是功率约束，每个低轨卫星的发射功率不能超过其功率限制。

3.2 任务卸载与资源分配联合优化算法

由于式(17)的联合优化问题是一个混合整数非线性规划问题，求解最优解需要指数级的时间复杂度。随着低轨卫星及其子任务数量的增加，难以在有限的时间内给出最优解。本文针对卫星网络环境，提出了一种基于动态优先级的任务卸载与资源分配联合优化算法，该算法能够适应任务执行环境中的动态资源分配。解决式(17)的问题分为以下几步：

(1)按照子任务依赖关系对子任务进行排序；

(2)根据系统参数给出初始的卸载策略；

(3)在初始卸载策略下进行带宽资源和功率资源分配；

(4)在资源分配策略下重新给出卸载策略；

(5)新的卸载策略不能带来优势时算法退出。

(23)

本试验采用随机排列，不设重复。①九麦2号4.6亩；②中麦895 1.55亩；③小偃22（CK）1.55亩；④秦农578 0.72亩；⑤西农223 1.65亩；⑥陕农33 1.8亩；⑦武农6号1.44亩；⑧凳峰168 1.2亩；合计占地14.5亩。（田间排列设置见附表1）。

为了综合考虑功耗和时延开销，定义子任务的优先级如式(24)所示：

(24)

首先低轨卫星内部根据子任务rank(u,k)的值进行优先级排序，得到当前资源分配下优先级最高的未调度的子任务。在各个低轨卫星之间选择priority(u,k)最大的低轨卫星进行卸载调度，选择时延最小的处理器进行卸载，得到任务卸载决策X和处理器调度策略Z。

在给定任务卸载决策X和处理器调度策略Z的情况下，为降低时延和功耗，设定目标函数如式(25)所示:

(25)

其中,P和B为无线资源分配策略，t′u为低轨卫星u中需要发送数据到高轨卫星的数据传输时延。无线资源分配包括上行功率分配和子带个数分配，以式(25)作为目标函数，满足约束的无线资源分配问题可以表述为式(26)：

s.t. 0

(26)

通过拉格朗日乘子法，可得出关于bu和pu的非线性方程组，每个低轨卫星分配的子带个数满足式(26)约束，用式(27)确定bu的值：

(27)

由于每个低轨卫星传输功率互相独立，bu确定后利用二分法可求出pu的值。

至此，给出了算法运行需要的全部定义和参数，并给出了进行资源分配和调度决策的启发式规则。算法1为任务卸载算法。首先,使用式(23)对所有子任务进行排序;然后，对于每一个低轨卫星上的任务，选择排名最高的未调度子任务，形成候选调度集;接着，使用式(24)在候选调度集中搜索具有最高优先级的子任务；再选择处理该子任务时延最小的处理器作为该子任务的卸载目标处理器。重复该过程，直到所有子任务都被调度。

算法1任务卸载与资源分配联合优化算法

输入:Vu，Eu，S,S′，Pu，W,Q。

输出:卸载决策X、调度策略Z、资源分配策略P、B。

iter=1，C=Inf;

whileTrue

ifiter=1

对∀u∈U，∀k∈Vu,B={bu}，bu=W/(Q×N)，P={pu},pu=Pu;

else

根据X通过解决式(26)重新分配资源得到B和P；

endif

根据式(23)计算rank(u,k)；

对∀u∈U,∀k∈Vu，选择排名最高的未调度子任务，形成候选子任务集；

根据式(24)计算候选子任务的优先级；

选择优先级最高的子任务，选择处理该子任务时延最小的处理器作为该子任务的卸载目标处理器，直至所有子任务均已调度，得到卸载决策Xnew和处理器调度策略Znew;

根据Xnew，Znew和式(16)计算系统开销Cnew;

ifCnew

C=Cnew;X=Xnew;

P=Pnew;B=Bnew;

iter=iter+1;

else

break;

endif

endwhile

returnX、Z、P、B;

4 仿真结果分析

本文对算法的性能进行仿真验证。首先介绍仿真场景和仿真参数的设置,然后在此基础上，将所提出的算法与当前其它算法的性能进行了比较。

4.1 参数设置

基于Walker星座进行了仿真，该星座包括32个轨道面，每个轨道面内有50颗卫星，轨道高度为1 100 km，共有1 600颗低轨卫星，高轨卫星位于地球同步轨道，每颗低轨卫星同时只能接入一颗高轨卫星。每个低轨卫星的任务被划分为10个子任务，子任务依赖关系与文献[16]的一致。具体仿真参数如表1所示。

Table 1 Simulation parameters

4.2 仿真分析

基于4.1节参数设置，通过500次蒙特卡洛仿真对提出的卸载决策算法性能进行评估。仿真在处理器为AMD Ryzen 7 PRO 4750U，内存为32.0 GB，操作系统为Windows 7的计算机上进行，仿真中的任务数据量和任务计算量均是以上述数据为均值随机产生的。

低轨卫星和高轨卫星之间的通信带宽设置如表1所示，高轨卫星处理器之间通过高速有线通道相互连接。任务数据量、任务计算量、高轨卫星处理器的数量和低轨卫星的数量都对任务卸载的性能有显著影响。因此，本文主要评估这几项因素的影响，评估指标为系统时延和能耗。

首先分析高轨卫星处理器数量的影响。将低轨卫星的数量设置为30颗，图2为不同子任务待处理数据量下任务平均完成时间和高轨卫星处理器个数的关系，图3分别为不同子任务待处理数据量下系统功耗和高轨卫星处理器个数的关系。图4为不同任务计算量下任务平均完成时间和高轨卫星处理器个数的关系，图5为不同任务计算量下系统功耗和高轨卫星处理器个数的关系。从图中可见，低轨卫星任务完成的平均时间和总功耗都随着高轨卫星处理器个数的增加而降低；同时在高轨卫星处理器个数不变的情况下，任务数据量和任务计算量的降低都会导致系统时延和能耗的降低。这表明，高轨卫星处理器个数的增加为低轨卫星提供了更多的处理器选择，使子任务可以具有更高的并行度，因此可以降低系统总体开销。

Figure 2 Average latency versus number of processors under different amount of task data图2 不同任务数据量下处理器数量和平均延迟的关系

Figure 3 Energy consumption versus number of processors under different amount of task data图3 不同任务数据量下处理器数量和总能耗的关系

Figure 4 Average latency versus number of processors under different amount of task workload图4 不同任务计算量下处理器数量和平均延迟的关系

Figure 5 Energy consumption versus number of processors under different amount of task workload图5 不同任务计算量下处理器下数量和总能耗的关系

在高轨卫星处理器个数为16，待处理数据量为40 Mbits，子任务平均计算量为8 Gcycles的情况下，图6给出了低轨卫星数量和系统平均延迟的关系，图7给出了低轨卫星数和系统总功耗的关系。图6和图7同时还给出了与文献[16]中提出的DEFO(Distributed Earliest Finish-time Offloading)算法以及和不卸载时系统性能的比较结果。可以发现，随着低轨卫星数目的增加，各个策略的时延和功耗都有增加；与不卸载相比，DEFO算法和本文算法都可以明显降低系统的平均执行时间。同时，在各个低轨卫星数量条件下，与DEFO算法相比，本文算法无论是在降低时延还是系统能耗方面都更具优势，时延平均降低了14.6%，能耗降低了54.1%，说明本文联合考虑无线资源分配的卸载算法可以更有效地提高系统整体效能。

Figure 6 Relationship between number of LEO satellites and average latency图6 低轨卫星数和系统平均延迟的关系

Figure 7 Relationship between number of LEO satellites and energy consumption图7 低轨卫星数和系统总功耗的关系

5 结束语

本文研究了高低轨协同计算的卫星边缘计算网络中的卸载决策问题，对存在子任务依赖的任务延迟和能耗联合优化的卸载问题进行了建模，提出了一种基于动态优先级的子任务卸载算法。该算法在保证任务依赖关系的同时，将能源消耗和时延引入优先级定义中，能根据具体的子任务分配无线和计算资源，使优先级排序在任务卸载决策阶段更加有效。仿真结果表明，与现有工作相比，本文算法可以减少卫星边缘网络中的任务延迟和能耗，有利于实现卫星计算和无线资源的高效利用。