低轨卫星协作边缘计算任务迁移和资源分配算法

宋政育，郝媛媛，孙昕

1 引言

近年来，为了满足移动通信和物联网的大计算量、低时延应用的需求，并降低移动终端的能耗，欧洲通信标准化委员会提出了多接入边缘计算（Multi-Access Edge Computing，MEC）技术［1］. 在缺乏地面通信基础设施的偏远地区，可在低轨（Low Earth Orbit，LEO）卫星中部署MEC 服务器，为偏远地区的用户提供高质量的边缘计算服务［2］. 为了充分发挥MEC 技术在降低移动终端能耗和计算时延等方面的优势，必须采用高效的任务迁移以及通信和计算资源分配算法［3，4］. 现有的任务迁移及资源分配算法一般基于凸优化理论设计，还有部分文献采用启发式算法. 文献［5］设计了基于时分多址接入和正交频分多址接入的两种多用户MEC 模型，在计算任务时延的约束下，基于凸优化理论提出了使用户能耗加权和最小的任务迁移和资源分配算法.文献［6］则采用凸优化方法设计了一种统计性的通信和计算资源分配算法，使移动设备和MEC 服务器的长期平均功率最小化. 文献［7］研究了异构MEC网络的能耗和时延的折中优化问题. 当用户数量或计算任务较多时，MEC 服务器容易发生过载现象. 为了解决该问题，可在系统中部署多个MEC 服务器，各MEC 服务器可进行边缘计算协作. 文献［8］基于遗传算法和粒子群优化方法，研究了密集部署的小蜂窝网络MEC 服务器的选择和通信资源分配问题，其中每个小蜂窝基站均可部署MEC 服务器并进行协作边缘计算. 文献［9］将小蜂窝基站的部分任务数据迁移至部署于宏蜂窝基站且计算能力更强的MEC 服务器，实现MEC 服务器间的协作边缘计算. 上述文献仅研究了地面通信网络的边缘计算问题，所提出的任务迁移和资源分配算法不适用于卫星通信网络.

目前，针对卫星通信网络边缘计算的研究比较有限. 文献［10］首次提出了星地一体化网络的MEC 技术，由于LEO 卫星与地面之间的信号传播时延最低可达到1~4 ms，MEC 技术可用于星地一体化网络. 文献［11］提出了一种星地一体化的边缘计算网络架构，并分析了该网络架构面临的技术挑战. 文献［12］研究了一种空天地一体化的边缘计算系统，并提出了基于机器学习的最优任务迁移策略. 上述卫星边缘计算的算法均未考虑卫星间的协作问题.

本文通过LEO 卫星通信网络的星间链路［13］（Inter-Satellite Link，ISL）进行任务数据的二次迁移，实现相邻卫星间的边缘计算协作. 以地面移动用户的加权总能耗最小化为目标，在保证任务时延需求的条件下，提出一种基于ISL 的LEO 卫星协作边缘计算任务迁移和资源分配算法. 仿真结果表明，该算法的收敛速度快；与本地计算和任务数据全部上传算法相比，本文所提出的算法的用户总能耗更低；与非协作边缘计算相比，基于ISL 的LEO 卫星协作边缘计算可有效降低用户能耗，且随着ISL 的信道容量和MEC 服务器计算能力的增加，用户的总能耗不断降低.

2 系统模型与优化问题

2.1 系统模型

设某LEO 卫星协作边缘计算系统有M个地面移动用户、N个LEO 卫星以及K个正交子载波. 在某LEO 卫星的覆盖范围内，采用部分任务迁移机制，通过正交频分多址接入同时将M个用户的部分或全部任务数据迁移至卫星MEC 服务器进行边缘计算，移动用户在本地对未被迁移至卫星的任务数据进行计算.假定移动用户的CPU 采用动态电压和频率调整技术［8］，则任意用户m进行任务数据的本地计算所需的功率为：

其中：κ为一个与CPU 架构有关的常数；fm为用户m的进行本地计算时的CPU时钟频率.

设用户m计算任务的总数据量为ηm，用户m向LEO 卫星迁移的数据量为Sm，二者的单位均为比特，则用户m进行本地计算所需的时间为：其中，β为计算每比特任务数据所需的CPU周期数.

用户m进行本地计算所需的能量可表示为：

设ρmk为子载波分配指示变量，当子载波k分配给用户m时，ρmk=1，否则ρmk=0，则：

当任务数据迁移时，用户m在子载波k上的数据速率可表示为：

其中，pmk与hmk分别为用户m在子载波k上的发射功率和信道增益；B0为子载波带宽；σ2为加性高斯白噪声的功率.

用户m进行任务迁移的总数据速率为：

用户m进行任务迁移所需的总功率为：

用户m进行任务迁移所需的能量为：

其中：Ttx为各用户任务数据迁移时的传输时间.

假定N个LEO 卫星中任意两个相邻的卫星间可通过ISL 进行边缘计算协作. 设地面移动用户接入卫星n，当卫星n的计算能力不足时，可将部分任务数据迁移至相邻卫星j的MEC 服务器进行协作计算. 设卫星n通过ISL迁移至相邻卫星j的数据量为D，卫星n和卫星j的MEC 服务器计算时的CPU 时钟频率分别为fnEC和fjEC，则二者进行边缘计算的时间分别为：

设ISL 的信道容量为C，则卫星通过ISL 迁移任务数据所产生的时延为：

任务数据计算结果的数据量很小，用户下载结果的时间可忽略. 由于星地之间距离较远，不可忽略信号自由空间传播时延. 假定LEO 卫星n的高度为Hn，光速为c，则地面用户与卫星n之间的信号自由空间传播时延可近似表示为：

LEO卫星进行协作边缘计算的总时延为：

2.2 优化问题

本文对LEO 卫星协作边缘计算系统的任务迁移策略以及通信和计算资源分配进行优化，其中通信资源包括各用户的发射功率、用户与卫星间的子载波以及任务迁移的时间；计算资源指用户进行本地计算时的CPU 时钟频率. 以所有用户的加权总能耗最小化为目标，以任务的可容忍时延等为约束条件建立优化问题，则该优化问题可表示为：

其中，f=(fm），ρ=(ρmk)，p=(pmk)，s=(smk).fmmax和Pmmax分别为用户m的CPU最大时钟频率和最大发射功率.T为计算任务可容忍的最大时延.wm为权重参数，用于表示用户的优先级. 约束条件C3和C4表示用户进行本地计算和边缘计算的时延均不能超过任务可容忍的最大时延.C7和C8表示系统中每个子载波最多可分配给一个用户.

3 任务迁移和资源分配算法

3.1 ISL迁移的最优数据量

为了设计LEO 卫星协作边缘计算任务迁移和资源分配算法，需要确定相邻卫星间通过ISL 迁移的最优数据量，可得优化问题的相关定理.

定理1 优化问题式(14)的目标函数为关于Ttx的单调递减函数.

证明由式（5）可得：

将优化问题式（14）的目标函数转换为：

对目标函数E求关于Ttx的导数，可得：

为证明E为关于Ttx的单调递减函数，需证明定义f(rmk) =则可 得. 对函数f(rmk)求关于rmk的导数，有因为rmk≥0，所以当rmk=0时，函数f(rmk)可达最大值，即f(0) =0；当rmk>0时，则f(rmk) ＜0. 若系统中至少一个子载波的数据速率rmk>0，则有因此，优化问题式（14）的目标函数为关于Ttx的单调递减函数. 对于rmk=0,∀m,k的特殊情况，所有的任务数据均由用户在本地进行计算，此时不需要进行任务迁移和资源分配算法的设计. 证毕.

由定理1可知，为了降低能耗，用户将以可允许的最大时长迁移任务数据. 因为Ttx+Tsat≤T，所以当Tsat取得最小值时，用户传输时长Ttx可达到最大，此时用户的能耗最低.根据式（13），对于卫星n时，max为常数，当取得最小值，即Tsat取得最小值.

由式（18）可得，卫星间通过ISL迁移的最优数据量为：

将D*代入式（13），可得Tsat的最小值，即：

3.2 任务迁移和资源分配算法设计

由优化问题式（14）的约束条件C1和C3，可得：

优化问题的目标函数为关于fm的单调递增函数，由式（21）可得fm的最优解，即：

为了保证优化问题的可行性，由式（21）可得：

则由式（23）可得：

将式（20）和式（22）代入式（14）中，优化问题式（14）转换为：

优化问题式（25）的目标函数为非凸的，不易对其直接求解，故将其分解为任务迁移子问题和无线资源分配子问题，通过迭代求解子问题，得到优化问题式（25）的解.

若假定子载波分配变量ρ已知，将式（15）代入优化问题式（25），则可得到任务迁移子问题为：

定理2任务迁移子问题式（26）为凸优化问题.

证明任务迁移子问题式（26）的目标函数的第一项为关于矢量s的凸函数，第二项符合函数的结构. 由于函数为关于x和t的联合凸函数，故优化问题式（26）的目标函数为关于s和Ttx的联合凸函数.定义函数，则约束条件C10 可等价于因为g(s,Ttx)与函数的结构一致，所以g(s,Ttx)为关于s和Ttx的联合凸函数，即约束条件C10 为凸的. 优化问题式（26）的其它约束条件均为线性的. 因此，任务迁移子问题式（26）的目标函数和可行集均为凸的，为凸优化问题. 证毕.

任务迁移子问题式（26）为凸优化问题，则可通过标准凸优化算法（例如内点法等），得到其最优解. 对于无线资源分配子问题式（27），由于存在整数优化变量，难以直接获得其最优解，因此采用拉格朗日对偶分解方法求解.

松弛无线资源分配子问题式（27）的约束条件C2和C11，则其拉格朗日函数为：

其中，θ=(θm)和λ=(λm)分别为约束条件C2 和C11 的拉格朗日因子. 对偶函数为Q(θ,λ) =

由式（28）可知，对于确定的拉格朗日因子θ和λ，可将对偶函数Q(θ,λ)进一步分解为K个独立的子问题，且每个子问题对应一个子载波. 对应于子载波k的子问题可表示为：

定义函数Gmk和Hmk，即：

则子载波分配的最优解为：

由式（33）可得，用户m在子载波k上的最优功率分配为：

基于任务迁移子问题式（26）和无线资源分配子问题式（27）的求解过程，LEO 卫星协作边缘计算任务迁移和资源分配算法归纳为算法1.

定理3描述了算法1的收敛性.

定理3 算法1 每次迭代均可降低目标函数E(ρ,p,s,Ttx)的值，并在有限次迭代内收敛.

当固定子载波分配变量ρ(l)时，算法1求子问题（26）的最优解()，并更新功率分配为p(2l+1)，所以式（35）中的不等式(a)成立. 同样地，当固定各用户迁移的数据量时，算法1 可得到子问题式（27）的解(∀m和传输时间)，所以式（35）中的不等式(b)成立. 不等式（35）表明，算法1的每次迭代均可降低目标函数E(ρ,p,s,Ttx)的值. 由于目标函数值是有下界的，故算法1将在有限次迭代内收敛. 证毕.

算法1迭代求解子问题式（26）和（27）直至收敛. 由于子问题式（26）为凸优化问题，得到其最优解的复杂度为多项式复杂度. 子问题式（27）采用拉格朗日对偶方法求解，其复杂度也为多项式复杂度. 根据定理3，算法1将在有限次迭代内收敛，因此算法1具有多项式复杂度.

4 仿真结果与分析

本节对LEO 卫星协作边缘计算任务迁移和资源分配算法（算法1）的性能进行仿真与分析. 设置LEO 卫星的飞行高度为1500 km，无线信道衰落包括自由空间路径损耗和莱斯衰落，卫星天线增益为43.3 dBi. 系统总带宽为20 MHz，子载波数量K=128，用户数量M=16，卫星MEC 服务器的CPU 时钟频率为8 GHz，且κ=10-26，β=120 cycle/bit.

图1 示出了本文提出的LEO 卫星协作边缘计算任务迁移和资源分配算法的收敛性. 在每次迭代之后，用户总能耗均降低，并在数次迭代后收敛. 对于不同的任务可容忍时延T，算法的收敛速度略有差别，但均可在约8次迭代内收敛. 因此，本文所提出的任务迁移和资源分配算法的收敛速度较快.

图1 LEO卫星协作边缘计算任务迁移和资源分配算法的收敛性

图2 示出了地面用户总能耗与计算任务数据量ηm之间的关系，随着计算任务数据量的增加，本文所提出的任务迁移和资源分配算法（算法1）、本地计算以及任务数据全部上传算法的用户总能耗都在增加. 由于算法1采用了部分任务迁移机制，可根据无线信道质量和计算任务数据量等因素优化迁移至卫星的数据量，所以其能耗始终低于其它两种算法. 当计算任务的数据量为3 Mbit 时，算法1 的能耗比本地计算的能耗降低约81%. 对于任务数据全部上传算法，当计算任务的数据量较少时，其能耗低于本地计算的能耗. 当计算任务的数据量较大时，因为全部数据均必须在有限的带宽和时间内上传至LEO 卫星MEC 服务器，所以任务数据全部上传算法的能耗将随着任务数据量的增加而快速增长.当计算任务的数据量超过1.5 Mbit 时，任务数据全部上传算法的能耗将远大于本地计算和算法1的能耗.

图2 用户总能耗与计算任务数据量之间的关系

图3示出了地面用户总能耗与计算任务可容忍时延T之间的关系. 当计算任务的可容忍时延较小时，用户需要在较短时间内完成任务数据的迁移和计算，因此三种算法的总能耗均较高. 随着任务可容忍时延的增加，用户可在较长的时间内以较低的发射功率进行任务数据的迁移，且本地计算的时间也较长，因此总能耗逐渐降低. 此外，算法1的能耗始终低于本地计算和任务数据全部上传算法的能耗. 当计算任务可容忍时延为0.2 s时，算法1的能耗比本地计算的能耗降低约74%.

图4 示出了用户总能耗与ISL 信道容量之间的关系. 可以看出，ISL 的信道容量越大，用户总能耗越低.对于相同的ISL信道容量，卫星MEC服务器的CPU时钟频率fECn越高，用户总能耗越低. 这是由于当ISL的信道容量较大时，卫星间任务数据迁移产生的传输时延较小，并且卫星MEC服务器的CPU时钟频率越高，卫星执行边缘计算所需的时间越短，因此用户向卫星迁移任务数据的时间Ttx较长. 由定理1可知，用户总能耗是关于Ttx的单调递减函数，故用户总能耗将随着ISL信道容量和卫星MEC 服务器的CPU 时钟频率的增加而降低. 当ISL的信道容量为0时，表示LEO卫星间无法进行边缘计算协作，此时用户的总能耗最高. 与非协作卫星边缘计算相比，当ISL 的信道容量为100 Mbit/s 时，基于ISL 的LEO卫星协作边缘计算的能耗可至少降低约22%.

图3 用户总能耗与计算任务可容忍的时延之间的关系

图4 用户总能耗与ISL信道容量之间的关系

5 结论

研究了LEO 卫星协作边缘计算的任务迁移和资源分配算法，以地面用户加权总能耗最小化为目标，以计算任务可容忍时延等为约束条件，通过LEO 卫星ISL进行任务数据的二次迁移，实现卫星间边缘计算的协作.由于所建立的优化问题的非凸性，将其分解为两个子问题分别求解，并提出了LEO 卫星协作边缘计算的任务迁移和资源分配算法. 仿真结果表明，该算法可在8次迭代内收敛. 与本地计算和任务数据全部上传算法相比，本文所提出的算法可至少降低约74%的用户总能耗；与非协作卫星边缘计算相比，基于ISL 的LEO 卫星协作边缘计算可至少降低约22%的用户总能耗，且ISL的信道容量越大，用户总能耗越低.