基于PM算法的星间协作计算卸载和任务迁移

基于PM算法的星间协作计算卸载和任务迁移

宁辛，徐飞，刘双煜，申奥祥

（西安工业大学计算机科学与工程学院，陕西 西安 710021）

【摘  要】天地一体化网络中，LEO高机动性无法维持完整且稳定的数据传输通信链路，用户服务质量较差。因此，提出一种基于DRL的星间协作计算方法，通过终端用户和LEO卫星之间的计算卸载和LEO之间的任务迁移，最小化系统加权总能耗、总时延。此外，针对多智能体深度确定性策略梯度算法高维动作空间、复杂状态空间以及训练时的不稳定性，利用优先经验回放机制对其进行改进，提出协作优先经验回放迁移算法，加速收敛性能。仿真结果验证了协作算法的有效性，并且与多智能体双延迟深度确定性策略梯度算法、随机算法和本地计算算法相比，所采用的算法能有效降低系统总成本。 

【关键词】天地一体化网络；低地球轨道卫星；深度强化学习；星间协作

doi:10.3969/j.issn.1006-1010.20240528-0002

中图分类号：TN927          文献标志码：A

文章编号：1006-1010(2024)09-0132-09

引用格式：宁辛,徐飞,刘双煜,等. 基于PM算法的星间协作计算卸载和任务迁移[J]. 移动通信, 2024,48(9): 132-140.

NING Xin, XU Fei, LIU Shuangyu, et al. Inter-satellite Collaborative Computing Offloading and Task Migration Based on PM Algorithm[J]. Mobile Communications, 2024,48(9): 132-140.

0   引言

现有的广域物联网主要建立在第五代（5G, 5th Generation）移动网络的基础上，不能无缝覆盖全球，导致许多用户，特别是农村和岛屿等偏远地区的用户无法接入网络。然而全球覆盖在各种应用中具有很高的价值，例如全球货物跟踪、战场情报感知、天气监测和灾害预警，以及为环境研究定期监测偏远地区的气候。此外，地面基础设施很容易在大规模自然灾害中遭到破坏。同时，人工智能、车联网等应用的快速发展对数据转发、任务处理等网络性能提出了更高要求，这给当前互联网带来了诸多挑战。因此，人们考虑采用不同的通信系统来解决这些问题。

低地球轨道卫星（LEO, Low Earth Orbit）^[1-3]抗毁性强、覆盖范围广和链路功耗低，有望提供无处不在的宽带服务。因此，以LEO星座网络为特征的天地一体化网络架构（如图1所示）^[4]已成为当前网络的有力解决方案和6G（6th Generation）网络的发展趋势。此外，移动边缘计算（MEC, Mobile Edge Computing）技术^[5-6]通过在网络边缘部署一组服务器，为用户设备提供敏捷计算服务，降低时延和能耗。

因此，本文首先提出融合MEC技术的星间协作计算场景系统架构。由于终端用户自身设备的局限性，计算任务将分为终端用户和LEO卫星两层计算节点进行处理。然后，针对卫星高速移动性，引入任务迁移模型，避免卫星覆盖范围变化导致任务失败。最后，将优化问题转换为深度强化学习（DRL, Deep Reinforce Learning）^[7-8]中的马尔可夫决策（MDP, Markov Decision Process）模型，针对多智能体深度确定性策略梯度（MADDPG, Multi-Agent Deep Deterministic Policy Gradient）算法的学习效率低、样本关联性高等问题，引入优先经验回放机制（PER, Prioritized Experience Replay），降低系统的加权总时延和总能耗。

综上所述，本文主要贡献有：

（1）构建星间协作计算场景系统模型，建立优化问题。针对天地一体化通信网络，提出了星间协作计算场景系统模型，其中配备MEC服务器的LEO卫星通过计算卸载和任务迁移为终端用户提供计算服务。然后建立通信模型、卸载模型和迁移模型，采用加权总时延和总能耗建立优化问题。

（2）将原始优化问题转换为MDP模型，利用多智能体DRL算法解决目标优化问题。由于LEO卫星的高速移动和异构性，空间环境不断变化，导致低时延、低能耗的迁移问题复杂性增加。这个问题被认为是非确定性多项式（NP, Nondeterministic Polynomial）困难的。一些传统方法在动态环境下难以自适应求解目标优化问题。因此，本文将优化问题转换为MDP模型，并且对多智能体DRL中的MADDPG算法进行改进，提出协作算法有效解决优化问题。

（3）构建星间协作计算场景下的异构仿真实验。使用Python模拟器模拟星间协作计算场景，并且考虑任务异构性和LEO卫星计算资源异构性，进行大量数值实验验证本文的理论研究。不同算法下的实验结果表明，本文算法优于其他三种基本算法，能够在复杂环境下以最低成本做出最优决策。

1   相关工作

LEO卫星轨道周期较短，有效载荷通常较小。因此，计算卸载和任务迁移技术是降低系统总成本，提高性能的有效途径。

文献[9]融合遗传算法和深度确定性策略梯度算法，降低计算负载；文献[10]联合优化迁移决策、迁移比例和传输功率，提出多任务端、边迁移算法，但两篇论文均并未考虑任务的可拆解性。Li等人^[11]对通信、计算资源和任务队列进行建模，提出一种低负荷基站群的分布式任务卸载策略；Zhu等人^[12]研究无人机辅助MEC中的任务调度问题；Yang等人^[13]将可重用任务的合作卸载过程转化为联盟博弈，提出合作卸载和多任务合作卸载算法；Zhang等人^[14]提出多跳卫星对等卸载问题；Zhou等人^[15]考虑LEO卫星移动性和异构资源约束，最小化时延和能耗，Gong等人^[16]提出动态任务迁移算法，降低系统总能耗。Zhang等人^[17]采用星间合作方式为地面用户提供服务，提出基于贪心策略的任务分配算法。Hu等人^[18]最小化动态卫星网络加权延迟和能耗，但上述论文均忽视了传统MEC算法复杂性和网络资源受限的问题。文献[19]联合优化资源分配和卸载决策，最小化系统长期平均总功率，但忽略了多卫星网络之间的协作性能。文献[20]通过路边单元和停泊车辆集群的合作卸载，提高系统资源利用率，但是没有获取周围车辆的实时信息。文献[21]提出任务迁移与缓存替换机制，但只考虑了针对用户设备的协作迁移。Wu等人^[22]在卫星资源同构的条件下，研究卫星边缘计算服务迁移的任务卸载问题。

不同于上述研究，本文充分利用异构LEO卫星网络的高机动性，联合时延和能耗提高星间协作计算场景系统性能，并且提出协作优先经验回放迁移（PM, Prioritized-experience-replay Migration）算法解决动态环境中的优化问题，减轻终端用户和接入卫星的计算负载，进一步挖掘天地一体化异构网络的发展潜力。

2   系统模型和问题描述

2.1  通信模型

2.2  任务卸载模型

2.3  任务迁移模型

2.4  成本函数

3   基于PM算法的星间协作计算卸载和任务迁移

3.1  马尔可夫决策模型

3.2  PM算法

4   参数设置与结果分析

4.1  仿真环境与参数设置

实验操作部分使用Python 3.9中在Intel酷睿i7-12700H(2.30 GHz)计算机上实现，RAM（Random Access Memory）为16 GB。LEO卫星信息参考高度位于1 400 km的Walker Delta星座^[30]，其轨道平面的轨道倾角是48°。考虑一个由4颗LEO卫星和50个用户组成的协作计算网络。用户随机分布在半径为6 371 km的圆形区域上，且每个用户的传输功率和任务大小均不相同。相关的系统仿真参数如表2所示：

设置神经网络是由256、128和64个神经元组成的三个隐藏层，激活函数为整流线性单元（ReLU, Rectified Linear Unit），采用Adam（Adaptive momentum）优化器进行优化，缓冲区大小为30 000，学习率为0.01，折扣因子为0.99。

4.2  仿真分析

本节中，首先基于上述数据评估PM算法的收敛性。然后通过设置不同的加权总时延、总能耗比重和网络架构分析训练过程中的奖励值变化，对PM算法进行全面探索，验证算法可靠性。最后，为验证PM算法性能，将其与多智能体双延迟深度确定性策略梯度（MATD3, Multi-Agent Twin-Delayed Deep Deterministic Policy Gradient）算法、All-Offloading和Random-Migration算法三种基线算法进行比较，具体描述如下：   

1）MATD3算法：MATD3（Multi-Actor Twin Delayed DDPG）是一种多智能体深度强化学习算法，是DDPG（Deep Deterministic Policy Gradient）的扩展，旨在处理具有多个智能体的协同决策问题，通过引入多个演员网络和多个评论家网络来提高学习的稳定性和效果。

2）Random-Migration算法（RM）：随机生成迁移比例将任务迁移到相邻卫星处理。

3）Local-Offloading算法^[15]（LO）：任务全部由终端用户处理。

（1）算法收敛性分析

图6显示使用默认参数下PM算法收敛性。随着训练的进行，曲线呈现上升趋势，然后逐渐趋于平稳，这表明算法已经收敛到一个相对稳定的状态。图7显示五种算法的加权总能耗和总时延的收敛性能。可以观察到，非DRL算法RM和LO算法始终处于某一区间波动，性能较差。这是因为系统环境较复杂，这两种算法不具备自主学习能力，无法找到最优解。PM、MADDPG、MATD3算法性能随着训练次数的增加趋于稳定状态，但是PM算法优势更明显。这是因为MATD3算法引入多个Actor和Critic网络来处理多智能体环境，增加了算法的计算复杂度，而且超参数较为敏感，需要进行大量的调试来找到最优的超参数设置，训练过程较为复杂。PM算法通过引入优先经验回放机制保留历史经验，提高了样本利用率，有效改善了MADDPG算法的训练效率和性能。

（2）基于不同权值大小的奖励曲线图

加权值的引入使算法变成了多目标优化问题，需要在性能和能耗之间找到一个平衡点。图8通过设置不同的时延、能耗加权值对算法收敛性进行比较分析。由图可以得到，时延加权值过小的情况下，算法收敛性能较低。当μ1=0.3时，算法震荡幅度较大，无法收敛到稳定状态。随着μ1值逐渐增大，算法的收敛性能也随着增加，可以收敛到0附近。

（3）基于不同神经网络的奖励曲线图

神经网络决定了模型对复杂任务和高维状态空间的适应能力，较深的网络可能更容易学习任务的复杂特征，但也容易受到梯度消失或爆炸等问题的影响，因此，图9分析不同网络架构对算法收敛性的影响，这对选择适当的网络深度和宽度非常有必要。设置神经网络有两个隐藏层时，奖励值在230回合左右急剧下降，这是因为当使用两个隐藏层时，虽然网络具备一定的非线性表达能力，但对于复杂的环境，可能不足以捕捉状态-动作值或策略函数的微妙变化。当神经网络有三个隐藏层时，收敛性能较好，但是128*128*128的网络结构在算法收敛到900回合左右奖励值波动幅度较大。通过分析不同DNN下奖励值曲线，可以得出结论，当神经网络设置三个隐藏层且为256*128*64时，算法的收敛性能是最优的。

（4）不同算法性能分析

此外，用户数量、LEO卫星计算能力对计算卸载和任务迁移的性能有显著影响。因此，本文主要评估这几项因素的影响，评估指标为系统加权总时延、能耗和系统总时延。

如图10所示，随着用户数量的增加，四种策略的累计奖励也随着增加。可以发现LO算法的累计奖励呈线性增加，不占据任何优势。RM算法的累计奖励增加较缓慢，但是相对于DRL算法还是不占据任何优势。当用户数量在区间75到175时，PM算法优于MATD3算法，可以探索出最优卸载、迁移策略。当用户数量为小于75或者大于175时，PM算法和MATD3算法差距较小，都可以获得很好的最优解。  

图11显示累计时延与用户数量之间的关系。可以观察到，随着用户数量的增加，每种算法的累计总时延都在增加，但是PM算法始终处于优势。这是因为随着用户数量的增加，任务量增加，计算时延成本较高，但是本文在奖励函数中引入惩罚因子，对时延较大的动作给予较大惩罚。因此，相较于其他三种算法而言，PM始终能以最低时延找到最优方案。

如图12所示，随着智能体计算能力的增加，LO算法的累计奖励始终处于稳定状态，而其他三种算法的累计奖励均缓慢增加，但是PM算法的性能远远高于其它三种算法。图13显示累计时延与计算能力之间的关系。可以发现LO算法的性能始终处于稳定状态，这是因为在LO算法中，任务全部由终端用户处理，改变智能体的计算能力不会对其造成任何影响。虽然RM算法的波动幅度较大，性能甚至在下降，这是因为卸载、迁移策略的随机性较大，算法在每次训练中都无法探索出最优策略。相较于PM算法性能的缓慢增加，虽然MATD3算法性能的增加幅度较大，但是总时延一直低于PM算法。

综上所述，PM算法在计算卸载和任务迁移方面性能优于MATD3、LO、RM算法。     

5   结束语

本文针对现有无线通信网络面临的挑战，提出LEO星座网络为特征的天地一体化通信网络架构，从通信模型、计算卸载模型、任务迁移模型构建星间协作计算场景架构。考虑到动态网络复杂的环境和任务需求，目标是优化系统加权总能耗、总时延，并且将优化问题建模为MDP模型，提出一种改进的MADDPG算法，通过PER机制减少因样本选择不稳定而导致的学习过程波动，提高算法决策的准确性和可靠性。此外，通过不同仿真参数、不同算法下的性能分析，可以看出PM算法不仅能够提高系统性能，还能低时延、低能耗解决复杂的多智能体协作问题。

对于未来的工作，本文将研究多维度星上资源对星间协作卸载决策和迁移决策的影响，进一步探索在系统模型中包含更多因素，如任务间依赖关系、联合调度计算资源和带宽资源。