一种低轨卫星边缘计算场景下联合资源分配的计算卸载策略

余 翔，陈宇博，刘 晗，褚 轩

(重庆邮电大学通信与信息工程学院，重庆 400065)

尽管5G网络为全球大约20亿用户提供增强的移动宽带服务，以及关键场景中高可靠和低延迟的服务。但当前5G网络受到经济成本与技术水平的限制，导致网络覆盖范围有限。尤其在沙漠、极地、海洋地区以及其他难以建立地面基站的地区缺乏网络覆盖。为了提供无缝覆盖和不间断的网络服务，卫星通信已成为未来 5G/6G通信的有力补充［1］。

随着新兴业务如物联网（IoT）、增强现实（AR）、虚拟现实（VR）和4K/8K视频传输业务的发展，用户终端的计算能力与续航能力导致了用户体验提升的瓶颈。在传统非地面网络（NTN）的透传模式下卫星充当地面网关与用户设备间的中继节点，通过中继请求地面云数据中心服务的模式，占用了大量带宽并导致了用户难以忍受的响应时延与能耗。受到地面多接入边缘计算（Multi⁃Access Edge Computing，MEC）技术的启发［2］，为解决用户对更高服务质量（QoS）需求的挑战，相较于传统中心云模式，将计算能力下沉靠近用户的低轨卫星（Low Earth Orbit，LEO），形成全新的LEO卫星边缘计算场景。LEO卫星节点上部署MEC的服务器可以减少频繁的卫星到地面链路传输，降低用户的响应时延与能耗，从而更好满足用户的任务需求，同时，LEO卫星通信网络的广域覆盖还能解决偏远地区的网络需求问题。

在传统边缘计算的研究中，文献［3］表明了在多核服务器的MEC系统中，设计合理的任务卸载策略可以有效地降低系统时延，而文献［4］则表明了多个边缘节点间的协作，可以扩展网络计算能力，获得更优的时间收益。但由于LEO节点自身载荷能耗敏感，在轨运行呈现高动态和周期性，与传统场景下的研究有很大差异。因此，低轨卫星边缘计算已经引起了学术界和工业界的关注，被认为是未来网络部署的重要研究方向之一。

考虑到能量和负载的影响，LEO卫星上的MEC服务器可以采用轻量级的管理平台，例如Docker［2］，这使卫星具有计算和内容分发的功能。文献［5］讨论了在STN网络中通过MEC技术以提高QoS的可能，给出了所设计的卫星边缘场景模型，并设计了一种协作的计算卸载策略，通过仿真表明计算卸载策略可以显著地降低用户感知时延和系统能耗。文献［6］提出了一种空地海集成的网络架构，并研究了一种基于深度强化学习的联合通信和计算资源分配策略，目的是将用户的总执行延迟降到最低。文献［7］则探讨了一种新型具有双边缘计算功能的卫星地面网络，提出了一种双边缘计算卸载算法，通过 DECO⁃TCM 和 DECO⁃ECM 优化了卸载延迟和系统能耗，并且还进行了数值仿真，证明了该算法使平均延迟和能量消耗分别降低约45%和49%。文献［8］提出一个软件定义的STN来管理和协调网络，将资源分配描述为一个联合优化问题，并采取深度Q学习来解决。文献［9］提出了一种基于排队论和加权方法的服务器选择策略。综合各种因素评分来选择最合适的计算卸载节点，仿真表明，对比固定选择策略和随机选择策略，该策略可以将平均响应延迟分别降低17%和34%。文献［10］针对物联网（IoT）设备的快速增长和计算需求，提出了一种基于博弈论的计算卸载策略以降低用户计算成本，并通过仿真证明了该策略的有效性。

尽管在文献［7］与［10］中，优化了系统的时延与能耗，但忽略了LEO卫星相对有限的计算能力和LEO卫星地面覆盖范围的时变性。由于卫星边缘场景下，有限的计算能力和通信时间是反映卫星边缘节点特性的重要因素，也是优化LEO卫星边缘场景的关键要素。因此，本文综合考虑卫星边缘节点的计算能力和间歇性通信，同时计算卸载过程中的资源分配也是影响时延与能耗的关键因素，影响着用户服务质量，也需要对其进行合理分配优化。

本文针对LEO卫星边缘计算卸载系统，在卫星边缘节点高动态性和计算能力有限的约束条件下，建立了系统模型，以时延和能耗作为系统成本。由于所提出的问题是一个混合整数非线性规划（Mixed Integer Nonlinear Programming，MINP）问题，直接求解困难，为了减少计算复杂性，通过将问题拆分为资源分配和卸载决策两个子问题。第一个子问题是具有预定卸载决策下的资源分配问题，第二个子问题是最优资源分配下的卸载决策求解问题。在此基础上，提出基于博弈论的计算卸载联合资源优化（Game Theory with Computing Offloading and Resource Allocation，GT⁃CORA）策略，进而降低系统总成本并提升用户服务质量。

1 系统模型

本文研究的是单LEO卫星边缘计算系统，如图1所示，该系统是由一个配备了MEC服务器的在轨运行LEO卫星和多个地面用户组成，地面用户任务独立可卸载。部署MEC服务器的在轨LEO卫星称为卫星边缘节点，地面的用户数量为K，用集合D＝｛i：i＝1，2，…，K｝ 表示。 单个设备表示为i。 同时考虑到卫星运行的高动态性，只有在特定的通信窗口才能通过无线信道进行数据通信，实现计算卸载，执行地面设备用户任务，返回计算结果。

图1 卫星边缘计算系统模型

1.1 低轨卫星覆盖模型

不同于地面MEC的网络模型，LEO卫星边缘节点的特点之一就是高动态性，因此地面用户与卫星边缘节点的连接并非全天候保持实时连接，需要卫星边缘节点和地面用户设备保持特殊的几何可视关系，当卫星边缘节点进入通信窗口才能进行通信和数据的传输。根据文献［11］，所需要满足的几何关系如图2所示。其中，Re表示地球半径，h表示卫星轨道运行高度，s表示用户与卫星边缘节点的几何距离。

图2 卫星与地面用户的空间几何关系图

忽略其他因素，只有当α＞0时，卫星进入通信窗口，数据传输可行，其中α为卫星边缘节点与地面的仰角，表达式为

式中，Δϕ＝ϕt－ ϕs，其中，ϕt和φt分别表示用户设备的经度与纬度，ϕs和φs分别表示卫星边缘节点的经度和维度。同时如果移动设备之间相距很远，这些设备间则不构成竞争，因此地面设备位于一个相对于卫星节点静止不动的较小区域，可以假设这些设备与卫星之间的几何关系是相同的。

θ为LEO卫星边缘节点与地面设备间的地心夹角，可以表达为

当α＝0可以求得通信窗口的最大临界值θ0。

1.2 通信模型

对于无线通信模型，假设卫星接入带宽划分为K个子信道，每个信道的带宽为W，用户通过计算卸载可以降低任务的处理时延与能耗，但在传输任务时也带来额外的通信时延与能耗，根据香农定理，将通信模型定义为

式中，Ri为用户i的上行传输速率，Pi为用户i的上行发射功率，hi为信道增益，N为高斯白噪声功率。

1.3 计算模型

1.3.1 本地计算

在本地卸载的决策下，计算任务Wi由本地用户设备执行。是本地用户设备的CPU时钟周期，也代表着本地设备的计算能力，可以计算出本地卸载任务的执行时延为

本地能耗的计算根据文献［12］得

式中，κ表示能量因子，取决于芯片架构［13］，结合时延与能耗可以得到本地卸载的成本函数为

式中，β和1－β分别表示能耗于时延在成本函数的权重值，且0≤β≤1。

1.3.2 卫星边缘计算

在卫星边缘计算的情况下，计算任务卸载到在轨运行的卫星边缘节点执行处理。为卫星边缘节点分配给用户设备i的计算能力（CPU cycles/s）。考虑用户设备与在轨卫星之间的距离所导致的传播时延，卫星卸载策略的时延消耗可以表达为

s可以表达为

式中，θ为用户设备与卫星节点的地心夹角。

卸载到卫星边缘节点的能耗可以表达为

式中，Fs为卫星边缘节点的CPU运行时钟频率。

结合式（7），式（10）和式（11）可以得到选择卫星边缘节点卸载的成本函数为

2 基于博弈论的计算卸载联合资源优化

2.1 问题描述

根据第1节的系统模型，将计算卸载问题转化为一个资源约束条件下的系统成本函数最优化问题，定义为

式中，C1为上行通信资源的约束，保证分配给卸载用户的上行传输功率不超过最大传输功率。C2为计算资源的约束，保证分配给卸载用户的计算资源不超过服务器拥有的最大资源，C3代表二进制变量的卸载策略。

在式（13）中，由于通信资源和计算资源是连续变量，而卸载决策是整数向量，因此该问题是一个混合整数非线性规划（MINLP）问题，是一个NP难的问题。为了简化求解，可重写MINLP问题为

2.2 资源分配

由式（14）拆出的资源分配问题为

给定卸载决策情况下，将式（12），式（7），式（10）和式（11）代入式（15），并拆开整理后可得

式中，V为不与优化变量相关的常数项，且式（16）第一个加号左侧项可表达为通信资源分配子问题，右侧可表达为计算资源分配子问题。求解式（16）的最小值等价为求解两个子问题的最小值。资源分配问题可以由式（17）和式（18）分别表示。

上行功率分配子问题为

计算资源分配子问题为

2.2.1 上行功率分配子问题

对于上行功率分配子问题（17），可以改写为

引理1g（Pi）函数是单峰的。

证明首先g（Pi）在R是二次可微的，接下来检查拟凸的二阶条件，即存在一点x0使得0 也满足

g（Pi） 的一阶导数为

可以看出g′（Pi）的正负完全取决于等号右侧的分子部分，令

算法1上行发射功率分配二分法

2.2.2 计算资源分配子问题

对于计算资源分配子问题可以改写为

以及

式（22）的拉格朗日函数可以表示为

式中，λ表示拉格朗日乘子，拉格朗日函数的导数为

通过使得拉格朗日梯度等于零，解出最优计算资源分配。最优计算资源分配如下

式中，λ∗＞0是连续满足的。因此可以得到KKT条件

将式（27）代入式（28）可得

最终将式（29）代入式（27）得到问题（22）最优解的封闭形式为

2.3 计算卸载

本文将最优资源分配下的最优计算卸载子问题表示为非合作策略博弈G，该博弈可以表示为G＝表示博弈参与者的集合，表示用户参与者i的策略集合，表示系统成本函数，a－i表示除设备i以外的所有设备的卸载选择。在一个竞争博弈环境下，每个用户都在约束条件下独立调整策略来最大化自己的利益，即最小化系统成本

定义1如果对于∀i∈D存在卸载策略组合为非合作博弈G的纳什均衡（Nash Equilibrium，NE），表示为除了用户i外所有用户设备的卸载策略组合，有

式（32）表示均衡状态给定用户的卸载决策a－i情况下，ai不能通过单方面改变它的卸载决策来进一步降低系统的计算开销，但是NE可能存在，或不存在。接下来，本文将引入势博弈的概念来解决这个问题。

定义2在一个有限博弈模型G中，存在一个函数对所有游戏参与者和策略向量满足

则表明该博弈存在势博弈。

定理1如果一个势博弈具有有限的策略集合，那么它存在一个纯策略的纳什均衡。

接下来，证明本文提出的博弈G存在确切的势博弈。

证明首先定义一个势函数P：A→R为

基于式（29）可以得到

基于式（34）可以得到P（1，a－i） 和P（0，a－i） 分别为

由

可以得到

同理可以计算得到

通过式（39）和式（40）证明满足定义2，即本文的博弈存在并可以通过一个确切的势博弈函数表示，并且根据纳什均衡存在定理［15］，其中至少存在一组纯策略纳什均衡。

基于上述分析，本文提出基于博弈论的计算卸载联合资源优化（Game Theory with Computing Offloading and Resource Allocation，GT⁃CORA）策略，详细描述见算法2。

算法 2GT⁃CORA

3 仿真结果和分析

本节通过仿真结果来验证GT⁃CORA的性能，模拟了一个单卫星边缘节点，多地面用户设备的计算卸载系统，结合文献［16－20］中的主要参数设置，表1为性能评估中的主要参数设置，并将GT⁃CORA与以下卸载策略进行对比。

表1 仿真参数

（1） 本地卸载（ALL Local Offloading，ALO）：所有的用户选择本地执行任务。

（2） 全部卸载（All SMEC Offloading，ASO）：所有用户都选择将任务卸载至卫星边缘节点。

（3） 贪婪卸载（Greedy Offloading，GO）：用户贪婪选择开销最小的节点进行卸载。

在仿真实验中，假设有5～40个地面用户设备分布在相较于LEO低轨卫星覆盖范围静止不动的较小区域，区域经纬度分别设置为 106°34′和29°33′，假设地面终端产生任务的过程为泊松过程。卫星节点选择Celestrak公布的铱星星座的两行轨道数据（Two⁃Line Orbital Element，TLE）中的一颗铱星的TLE作为模拟星座轨道，通过STK软件选取2020年1月1日期间模拟LEO在轨运行卫星的卫星坐标。

首先通过对比实验研究不同卸载方案下的边缘地区用户设备数量与平均计算开销的关系。从图3可以看出，相较于ALO、ASO和GO策略，随着用户设备数量的增加，GT⁃CORA的平均计算开销分别降低了47%、31%和20%。而且，随着用户设备的增加，由于设备之间竞争资源的愈加激烈，其他策略无法平衡设备间对资源的竞争，导致成本大幅增加。注意到本文所提出的GT⁃CORA策略和ASO策略之间的差距扩大了。这是因为随着设备数量的增加，GT⁃CORA策略总是为设备提供更好的卸载策略和资源分配，而ASO总是选择卫星卸载，设备增多时，由于排队等待卫星节点处理，会带来巨大的等待时延。因此，当设备数量增加时，GT⁃CORA策略可以有效地降低系统的平均计算开销。

图3 用户在不同卸载方案下的平均计算开销

图4显示了平均计算开销与完成任务所需CPU周期数量之间的关系，可以看到，GT⁃CORA、ASO、ALO、GO的平均计算开销的趋势都随着任务计算所需CPU周期的增加而上升，这表明了计算需求更强的任务会带来更多的平均计算开销。相较于GO、ALO、ASO，GT⁃CORA策略的平均计算开销有明显降低，平均计算开销分别降低了21%、36%和31%。此外还可以观察到GO与ASO随着任务计算所需CPU周期的增加曲线贴合，这是由于随着任务计算能力的增加，本地的计算能力无法处理这些亟待解决的任务，GO策略选取最优节点更加偏向于拥有强大计算能力的卫星边缘节点，策略选择偏向ASO，但这也带来了更多的等待时延和传输时延，增大了计算开销。

图4 任务计算所需CPU周期对应的平均计算开销

在图5中，以不同的卫星边缘节点的计算能力来研究所提出策略的性能，相较于ALO、ASO、GO 3种策略，GT⁃CORA在不同的卫星边缘节点计算能力下都有不错的效果，性能都优于其他3种策略。图5显示了5 GHz前后的不同趋势，下降趋势的原因是随着卫星时钟频率的增加，器件的成本与之成反比，器件在这一时期占主导地位。相反，卫星成本呈小幅上升趋势的原因是与时钟频率成正比，在此期间卫星成本占主导地位。此外，ASO策略选择将任务全部卸载到卫星边缘节点之上，当卫星边缘节点的时钟频率较低时会带来更高的计算开销。而ALO策略选择将任务全部本地执行，计算开销与卫星边缘节点的计算能力无关，平均计算开销保持不变。

图5 卫星边缘节点时钟频率对应的平均计算开销

在任务成功率方面，通过图6可以发现，本文所提出的GT⁃CORA策略任务成功率优于其他策略，随着用户设备数量增多，任务成功率依旧保持在83%左右。而ASO和GO随着用户设备数量的增加，任务成功率下降趋势明显，这是由于用户设备数量增多后选择卸载到卫星边缘节点，但是卫星边缘节点位于通信窗口期内的时间有限，导致了部分任务卸载失败，或任务的时延等待超过了任务最大的容忍的时延阈值，从而任务成功率下降。

图6 不同计算卸载策略的任务成功率

4 结束语

针对低轨卫星边缘计算场景，考虑LEO卫星边缘节点特性，采取博弈论解决地面多用户设备间的计算卸载问题，设计了一种基于博弈论的计算卸载联合资源分配优化策略GT⁃CORA，仿真实验表明，相较于其他算法，本文所提算法具有良好的计算卸载性能和任务成功率，尤其在地面设备增多时性能更优。下一步将研究多LEO卫星边缘节点场景，和地面云节点融合场景下的计算卸载问题，从而实现多层次任务的高效卸载，提升用户服务质量。