面向空天地异构网络的边缘计算部分任务卸载策略

李 斌 刘文帅 费泽松

①(南京信息工程大学计算机与软件学院 南京 210044)

②(北京理工大学信息与电子学院 北京 100081)

1 引言

随着5G网络的不断成熟，物联网的高速发展，物联网设备将部署在地球上的任何地方，用于执行某些具有特定计算需求的任务[1,2]。然而由于一些部署在山脉和海洋等复杂地形的设备，仅仅依靠传统地面无线网络可能无法满足物联网设备的计算要求。此外，地面网络的基础设施易受地震和飓风等自然灾害的破坏，这可能会中断设备通信。为了解决上述问题，空天地异构网络(Space-Air-Ground Integrated Network, SAGIN)的研究成为未来6G网络架构的核心方向之一[3-7]，将人类的网络空间提升到一个新的维度。具体而言，SAGIN可分为3个部分，即天基网络、空基网络和地基网络。在空基网络中，无人机(Unmanned Aerial Vehicle, UAV)作为空中飞行基站为地面终端用户提供低时延的移动边缘计算(Mobile Edge Computing, MEC)服务。在天基网络中的低轨(Low Earth Orbit, LEO)卫星可通过无缝网络覆盖提供无处不在的云计算服务[8]。通过多种网络深度融合，SAGIN可以综合利用各自资源，从而满足差异化应用与用户需求。

目前关于空地协同或天地协同的研究已经取得了很多有价值的研究成果[9-13]。譬如，为了权衡无人机和地面设备的能耗，文献[9]通过引入权重因子，联合优化无人机轨迹、系统资源使得系统能耗最小化。为了解决用户在卸载数据时存在窃听问题，文献[10]通过联合优化用户关联匹配混合资源分配，提出了一种最小化系统能耗的安全卸载策略。为了研究空地协同网络性能，文献[11]提出了一种新的MEC框架，其框架包括多个地面服务器以及1个由无人机携带的空中服务器，通过联合优化通信和计算资源及无人机轨迹使得系统的加权计算效率最大化。随着LEO卫星的最新发展，为探究卫星的任务处理能力，文献[12]提出了利用卫星为远程设备提供计算服务，通过联合优化通信和计算资源使得系统能耗最小化。为了探索天地协同网络性能，文献[13]提出了一个具有3层计算结构的混合云和携带MEC服务器的LEO卫星网络，研究了地面用户、LEO卫星边缘节点和云服务器之间的协作关系，在LEO卫星的覆盖时间和计算能力的约束下最小化地面用户的总能耗。近期，由北京邮电大学深圳研究院与天仪研究院共同发起的“天算星座”实验，通过对卫星智能化，构建空天协同计算网络，为推动我国卫星互联网发展提供技术支撑。

随着各类应用需求的不断提升，为充分利用SAGIN的互补特性，实现无线网络与MEC技术的有机融合，涌现出了一些工作[14-17]。譬如，文献[14]将卫星当作空中中继节点，将用户的任务通过卫星中继传输到地面服务器进行处理。文献[15]将无人机当作移动中继节点，将用户的任务通过无人机中继传输给LEO卫星处理。而上述文献忽视了直接在卫星或无人机上进行任务处理的可行性。为了探索空天地协同计算的可行性，文献[16]提出SAGIN边缘/云计算框架，其中无人机为地面用户提供边缘计算服务，卫星提供云计算服务，在能量和计算的限制下加载计算密集型任务，通过联合优化资源分配和任务调度，寻求最优卸载策略。文献[17]将LEO卫星和高空平台结合起来为地面用户提供边缘计算服务，通过联合优化关联匹配、传输预编码矩阵、计算任务分配和资源分配实现系统总能耗最小化。上述研究工作展现出空天地异构网络的巨大优势，然而它们仅考虑了时延或能耗的单一约束。

不同于上述研究，文献[18]考虑了时延和能耗共同约束，通过联合优化通信和计算资源来提高SAGIN性能。但是该工作将无人机当作空中静止服务器，未考虑无人机固有的移动本质。为了充分利用UAV灵活部署、高机动性以及LEO卫星广域覆盖的特点，进一步挖掘空天地异构网络的互惠潜力，本文提出一种面向SAGIN的移动边缘计算系统，如何合理地进行多边缘节点的协同计算和资源有效分配是亟待解决的关键问题，其主要贡献如下：

(1)本文将多无人机引入空天地异构网络中，并在部分卸载的基础上，联合优化用户匹配关联因子、用户任务分配量、带宽分配、无人机计算资源分配以及多无人机的轨迹，构建一个整数、非线性、多变量耦合的能耗最小化问题。

(2)为了求解该非凸优化问题，本文采用交替迭代优化算法，将原非凸问题分解为3个子问题，并利用变量替换和连续凸逼近算法进行求解，并提出一种基于迭代的能耗最小化资源分配算法。最后给出了算法的收敛性和计算复杂度。

(3)仿真结果表明，本文算法具有良好的收敛特性以及在降低系统能耗方面的有效性。

2 系统模型

如图1所示，空天地网络中有1颗携带服务器的LEO卫星和M架携带微服务器的UAV为K个地面终端用户服务。其中，信关站作为控制中心，负责收集卫星、无人机和用户间的链路信道信息以及地面用户的服务需求等参数，用于进行边缘网络中计算和通信资源分配和无人机轨迹规划。为了便于表达和分析，定义用户、UAV的集合分别为∀k ∈K≜{1,2,...,K}，∀m ∈M≜{1,2,...,M}。由于LEO卫星具有高速运动的特性，因此用户与LEO卫星之间通信时长会受LEO覆盖时间的限制。假设UAV的飞行周期和LEO卫星覆盖时间相同，记为T。UAV飞行在固定高度H，为了使得UAV的位置相对用户近乎保持不变，将T 分割为长度为δt=T/N的足够小的时隙，且仅在不同时隙下UAV的位置发生变化，记时隙集合∀n ∈N={1,2,...,N}。采用笛卡尔坐标系，UAV m在第n个时隙内的位置为qm[n]=[xm[n],ym[n],H]，用户k的位置固定为wk=[xk,yk,0]。UAV m在每个时隙内距离变化与飞行速度有关，假设UAV m在飞行周期结束后返回起点，为了避免UAV之间发生碰撞，其位移约束须满足以下约束

图1 系统模型图

2.1 LEO卫星覆盖时间模型

因此，地面终端用户与低轨卫星之间的最长通信时间可表示为

图2 低轨卫星与地面终端用户的几何关系图

2.2 通信模型

2.3 计算模型

3 优化问题描述

在本文中，通过联合优化用户匹配关联因子、用户任务分配、带宽分配、无人机计算资源分配以及无人机的轨迹，实现无人机的总能耗最小化。具体优化问题建模为

其中，约束C1和约束C2表示无人机的飞行轨迹，约束C3表示无人机之间的安全距离来防止碰撞，约束C4表示用户计算任务分配的约束，约束C5表示本地计算的任务需要在时长T内完成，约束C6和C7表示划分给UAV的任务量需要在时长T内完成，约束C8表示划分给LEO的任务量需要在时长T内完成，约束C9表示用户的总能耗不能超过其可用能量，约束C10和C11表示用户只能关联1个UAV，约束C12表示带宽分配比率，约束C13表示限制UAV自身最大CPU计算频率。由于目标函数的非线性以及约束条件C10是整数变量，使得上述问题是非线性整数规划问题，很难求得其最优解。

4 优化问题求解

由于问题式(8)是变量高度耦合的非线性整数规划问题，难以直接进行求解。为了有效求解该问题，本文采取交替优化的策略，将其分解为3个子问题进行求解，分别为用户无人机的关联匹配、计算任务和带宽分配、无人机计算资源分配和无人机轨迹优化。

4.1 关联匹配

4.2 计算任务和带宽分配

上述问题是线性规划问题，它可以借助优化工具进行求解(例如CVX)。

4.3 无人机计算资源分配和轨迹优化

上述问题是标准凸优化问题，可以借助凸优化求解软件(例如CVX)进行求解。

5 复杂度与收敛性分析

在前一小节中，将原始问题分解为3个子问题，并通过松弛和连续凸逼近等方法将非凸问题转换成凸问题，进而提出一种基于交替迭代的优化算法求解原问题式(8)。交替优化算法的实现过程如表1所示。

表1 交替优化算法(算法1)

5.1 复杂度分析

5.2 收敛性分析

6 仿真结果与分析

图3 K=12时多个UAV的飞行轨迹

平均值为5.394 m/s，从图中可以观察到时隙内的飞行速度变化较为平滑。考虑到飞行能耗随速度的增大而快速升高，优化后的飞行速度波动较小这一现象进一步验证了轨迹优化与能耗最小化的关联性。

图4验证了不同方案下算法的收敛性，其中系统包含12个用户，可以看出，采用交替优化算法求解在7次迭代左右达到收敛。所对比的固定圆形轨迹策略中，各UAV的轨迹均为半径为500 m的圆，对于UAV 1, UAV 2和UAV 3，出发点与圆心连线分别平行和垂直于y轴。与固定圆形轨迹方案相比，所提算法收敛速度略慢，但目标值更优，能耗减小了43.3%，这一点验证了所提算法具有较好的性能。

图4 交替优化算法的收敛曲线

为进一步验证系统的服务效果，图5绘制了各个时隙内5个用户的卸载速率。由图可知，用户卸载速率有较大的波动，并且每个用户都至少获得了一个速率较大的时间段用作任务卸载传输，对应于UAV先靠近用户提供卸载服务，后远离并服务其他用户的过程。该现象验证了优化算法利用UAV自身移动性，使用户得到满足需求的传输速率与传输时间，兼顾到所有用户的服务质量。

图5 K=5时用户在不同时隙内的卸载速率

图6表示不同方案下，用户数量变化对UAV能耗的影响。对于固定带宽方案，每个用户均分带宽；对于随机关联方案，用户随机选择关联的UAV。从图中可见，随用户数增加，UAV能耗增长速度逐渐变大。用户数量较小时，能耗增加幅度较小，这是由于UAV资源充足，能以较小的飞行代价与计算开销服务用户。而当用户数量增大时，由于用户分布具有随机性，UAV飞行中任务卸载时，所关联的用户无法全部以较短的时间完成卸载传输，导致留给UAV计算任务的时间减少，计算频率增大，计算能耗快速升高。

图6 UAV能耗随用户数量变化

7 结束语

本文研究了空天地异构网络赋能的移动边缘计算部分任务卸载及资源分配算法。首先，分析了低轨卫星的覆盖时间，建立了通信模型和计算模型。通过联合优化用户与无人机之间的关联匹配、用户任务分配、带宽分配、无人机计算资源分配和无人机轨迹，实现无人机能耗最小化。其次，为了有效求解这个具有离散二进制变量和耦合约束的非凸问题，将原问题分解为3个子问题，并采用变量替换和连续凸近似方法将原问题转为凸优化问题进行求解。最后，通过仿真验证了所提算法的收敛性与在降低无人机能耗方面的有效性。下一步将在本文的基础上考虑由于低轨卫星高速运动而导致用户离开服务卫星的覆盖范围而中断服务，由此考虑为保障用户通信的连续性，将用户的任务切换至其它卫星，考虑多颗低轨卫星协同下的卸载方案。