基于多智能体强化学习的多无人机边缘计算任务卸载

李 斌

(1.南京信息工程大学 计算机学院，江苏 南京 210044；2.南京信息工程大学 江苏省大气环境与装备技术协同创新中心，江苏 南京 210044)

0 引言

移动边缘计算(Mobile Edge Computing,MEC)技术能有效缓解资源受限设备执行密集型应用的压力,可提高网络的应用体验[1-2]。在临时部署通信服务的偏远地区或聚集活动热点地区等通信条件较差的场景,地面固定式通信设施难以提供较好的服务。利用无人机(UAV)高机动性、易部署和立体式增强覆盖等优势,将UAV与MEC相融合可以提供泛在的接入服务和高质量的计算服务[3-4]。

如今,UAV辅助MEC网络成为了学术界和工业界的研究热点,然而各类参数及用户服务需求时刻发生着变化[5]。深度强化学习(Deep-Reinforcement Learning,DRL)作为人工智能的一种新兴技术,通过与环境不断交互学习、积累经验,从而寻求最优策略[6]。相较于离线求解及迭代算法,采用经过训练的DRL策略能实时地求解系统的能耗与时延等优化问题[7]。为了适应动态变化的网络状态与环境,结合DRL方法能够实时进行决策的优势,研究人员提出了一系列高效的资源管控优化算法。针对两层UAV网络架构,文献[8]结合深度Q网络(Deep Q Network,DQN)与深度确定性策略梯度(Deep Deterministic Policy Gradient,DDPG),设计了一种DRL训练框架,以优化UAV轨迹与虚拟机配置,进而有效地降低系统时延。文献[9]利用智能反射面的通信辅助能力,使用DDPG与双深度Q网络(Double Deep Q Network,DDQN)协同优化网络资源以提高UAV边缘计算的能效。为提升移动用户群组的服务体验,文 献[10]通过聚类算法设计UAV动态部署,并采用DDPG方法优化服务关联,从而降低了系统能耗。文献[11]考虑了多任务调度问题,根据信道状态、任务请求等信息以最小化加权信息年龄,设计了一种基于近端策略优化(Proximal Policy Optimization,PPO)的DRL算法。然而,DDQN、DDPG和PPO等单智能体DRL算法不能很好地应对当网络规模较大时所带来的状态空间及动作空间维数过高的问题。

在实际场景中,多个移动用户(Mobile User,MU)和多个边缘服务器通常部署在不同的位置,易于利用分布式算法进行训练与决策。同时,多智能体强化学习(Multi-Agent Reinforcement Learning,MARL)方法能较好地适应MEC的分布式结构。相比于单智能体DRL,MARL能够减小状态空间与动作空间,并可高效地做出决策。鉴于此,文献[12]面向多UAV边缘计算,利用MARL方法较好地解决了负载均衡问题。文献[13]利用多智能体确定性深度策略梯度(Multi-Agent Deep Deterministic Policy Gradient,MADDPG)方法实时优化多UAV轨迹,最大化计算服务的公平性。文献[14]面向多UAV网络中的隐私问题,利用多智能体联邦学习进行分布式训练,达到了与MARL接近的效果。虽然上述工作应用了MARL的分布式结构,但尚未充分利用不同设备的功能,缺乏多类型设备、异构智能体协作优化MEC服务的研究。同时,上述工作存在服务质量不稳定、算法训练速度慢和UAV轨迹曲折难以实现等问题。

基于此,本文考虑到任务分布式卸载的特点,采用多智能体近端策略优化(Multi-Agent Proximal Policy Optimization,MAPPO)方法,并在MARL算法引入了Beta分布以及注意力机制以提升算法的性能,加快算法的收敛速度,从而有效降低MEC服务的开销。本文的主要工作有如下三方面:

① 研究了多架UAV辅助MEC的系统模型,综合考虑MU的移动性、任务生成的随机性和多UAV之间的安全距离,建立了MU和UAV的加权能耗最小化问题。该问题具有高动态特征,对优化实时性和规模扩展性提出了更高的要求。

② 设计了一种异构MARL方法,通过构建含有3种智能体的系统,基于MAPPO算法训练MU和UAV协同完成卸载决策与资源分配。该分布式决策方法能分解较大的环境状态与动作空间,并将决策能力下沉到各类设备,提高算法的可扩展性。

③ 在Actor网络输出层使用Beta分布以提高动作的探索效率和采样性能,并向Critic网络中引入注意力机制以提高MARL方法的值函数拟合性能。提出了基于MAPPO的能耗最小化任务卸载方法(Energy-efficient-Attention-Beta-MAPPO,E-ABMAPPO),该方法具有较快的收敛性,且系统性能优于基准方法。

1 系统模型及问题描述

本文考虑一种多UAV辅助的MEC系统模型,如图1所示。在该系统中,MU需要将产生的计算任务卸载到UAV边缘服务器进行计算。此系统模型有 1个地面控制中心,M架搭载边缘服务器的UAV为K个MU提供任务卸载服务。为便于表达和分析,定义MU的集合为≜{1,2,…,K},UAV集合为≜{1,2,…,M}。此外,地面控制中心需要借助UAV收集通信链路信道信息、MU的服务需求等系统状态,进而对边缘网络进行即时管控。

(1)

式中:amax为UAV的最大加速度,vmax为UAV最大飞行速度,dmin为UAV之间的最小安全距离。

假设MU初始随机分布,且按照Gauss-Markov模型随机移动[15]。在时隙n内,MUk的速度大小vk[n]和移动的方向角度θk[n]可表示为:

(2)

(3)

(4)

(5)

1.1 计算模型

(6)

① 本地计算:为了充分利用MU有限的计算资源并最小化能耗开销,本地计算将采用动态电压频率缩放技术以给出计算频率。在最大计算频率限制下,本地计算频率可表示为:

(7)

(8)

② 边缘计算:MU可以将自身计算任务卸载至所关联UAV边缘服务器进行处理,具体过程如下:

首先,UAV需要分配通信信道的带宽资源以接收来自MU的任务数据。考虑到大尺度衰落和小尺度衰落,则在时隙n内UAVm和MUk之间的信道增益可表示为:

(9)

(10)

(11)

当MU请求将任务卸载至UAV之后,UAV需分配其计算资源,完成任务的处理。记UAVm可用的计算频率为fm,UAVm在时隙n内为MUk分配的计算资源为fm,k[n]。由此,其满足约束:

(12)

(13)

综上所述,MUk的任务计算时延需满足的约束可以表示为:

(14)

式中:bk,m为带宽分配系数,B为带宽,σ2为噪声功率。

1.2 能耗模型

定义MU和UAV服务器上CPU的有效电容系数为κ,则MUk的计算能耗和传输能耗分别为:

(15)

(16)

由上述分析可知,在时隙n内,MUk的总能耗为:

(17)

根据文献[17],UAVm在时隙n内的飞行能耗可表示为:

(18)

式中:P0为UAVm悬停状态下型阻功率,Pi为UAV悬停状态下的诱导功率,v0为UAV悬停下的平均旋翼诱导速度,d0为机身阻力比,s为总叶片面积与叶片扫过面积之比,ρ0为空气密度,A为UAV叶片扫过的面积。UAVm的计算能耗为:

(19)

2 优化问题描述

(20)

式中:ϖ1、ϖ2、η为能耗权重因子,∏(·)为指示函数,当条件(·)为真时值为1,否则值为0;约束条件C1～C4表示UAV的飞行轨迹,约束条件C5表示卸载关联因子取值,约束条件C6表示每个MU至多选择一个UAV卸载,约束条件C7～C8表示UAV带宽资源与计算资源分配限制,约束条件C9为任务的时延约束,约束条件C10限制了任务划分系数的范围,约束条件C11～C12限制了UAV划分给MU的资源,C13保证了资源分配的有效性,避免不进行任务卸载的用户空占计算资源。

由于MU的随机移动性、卸载关联的离散性以及非凸约束,上述问题不仅仅是一个多变量耦合的非凸组合优化问题,更是一个需要实时决策的优化问题。DRL作为一种自适应的机器学习方法,可以从环境中不断采样学习,并训练得到能部署在设备上的深度策略模型,从而根据当前状态,做出符合长期效益的实时决策,因此适应于所研究的MEC任务卸载场景。

3 基于MAPPO的优化问题求解

3.1 MDP模型

问题(20)需要联合优化多个MU以及多个UAV的决策信息,并且MU以及UAV在服务过程上存在协作关系,在计算和通信资源上存在竞争关系。考虑到该问题具有分布式特征,可将其建模为由多个智能体构成的MDP模型。根据决策变量与目标函数的相关性以及部署位置的差异,将MU作为一种智能体,将UAV分解为2种智能体:UAV资源分配智能体与UAV轨迹优化智能体,因此所提出的MDP模型共有3种智能体参与。

① MU智能体:MU的基本要素包括观测ok(t)、动作ak(t)和奖励rk(t),具体如下:

(21)

动作:MU的决策涉及卸载关联α和任务划分系数ρ,每个MU需要选择关联的UAV,决定其任务划分系数。因此MU智能体k的动作由下式给出:

(22)

奖励:从协作性角度,UAV的能耗负担需要为所有关联的MU所知。从针对性角度,需要考虑每个MU自身能耗开销对总加权能耗的贡献,以及自身不满足时延要求的惩罚。因此,每个MU的奖励应该综合考虑MU本身和所关联UAV的能耗,每个MU的奖励由下式给出:

(23)

式中:mk为MUk所关联的UAV。

MUk不满足时延要求时的惩罚函数为:

(24)

式中:χt为惩罚系数。

② UAV资源分配智能体:每个UAV需要在MU给出卸载关联因子及卸载量后做出决策。因此,其MDP基本要素表述如下

oK+m(t)≜{qm[n],q-m[n],Ωk[n],wk[n],ρk[n],∀k∈}。

(25)

动作:UAV收到MU请求后,需要根据用户任务请求、位置等信息分配带宽和计算资源。因此,UAV资源分配智能体m的动作为:

aK+m(t)≜{bm,k[n],fm,k[n]/fm,∀k∈}。

(26)

奖励:接收MU的计算任务后,UAV从环境中获得奖励。作为服务提供者,每个UAV的奖励需要考虑自身开销和所服务的MU的能耗,在未满足用户时延需求时需要给出一定的惩罚,可以设计得到UAV奖励函数如下:

(27)

③ UAV轨迹优化智能体:UAV已经获取了有价值的状态信息,UAV轨迹优化智能体与UAV资源分配智能体可以共享观测,即oK+M+m(t)=oK+m(t)。其动作与奖励如下:

动作:UAV轨迹优化智能体m需要给出UAVm的移动状态,通过水平加速度变量控制轨迹变化,其动作为:

aK+M+m(t)≜{am[n]}。

(28)

奖励:为获得优化效果更好的轨迹,可通过设计更加具有反馈意义的奖励函数,进而提高动作与目标函数的相关性。当无人机尝试飞出服务范围时,需要给出一定惩罚,因此该种智能体的奖励可设置为:

Po(qm[n+1]),

(29)

式中:dk,m[n′]表示MUk与UAVm在时隙n′的水平距离。上式反映了各个UAV与所服务MU的当前移动平均距离的最大值,以尽可能兼顾到所服务的MU,并促使UAV共同协作,且UAV试图飞出宽度为W的正方形服务区域时给出的惩罚函数为:

(30)

式中:χo为惩罚系数。假设当UAV智能体输出的动作会导致UAV飞出边界或发生碰撞时,该动作无效,UAV将会保持在当前位置。

3.2 基于MAPPO的任务卸载算法

与基于值的DRL方法不同,MAPPO是一种基于策略的方法[18],每个智能体由Actor网络、Critic网络和经验缓存区组成,能通过作为策略的Actor网络直接输出动作得到决策变量,因此MU和UAV可以将预训练的Actor网络部署到本地,并行地进行分布式决策。

(32)

(33)

式中:ξi为Critic网络i的参数。因此,Actor网络和Critic网络分别根据式(31)和式(33)更新。

3.3 E-ABMAPPO训练框架

本文所提出的E-ABMAPPO训练框架如图2所示,MU和UAV根据其智能体的Actor网络所给出的动作执行任务卸载,UAV与地面控制中心同步收集状态、动作等经验组成部分以及系统状态。随后,地面控制中心通过各智能体的观测获得全局环境状态,计算奖励值,将经验存入智能体的缓冲区,并获得预测值。在更新Actor网络和Critic网络后,Actor网络的参数被下载到UAV和MU。

图2 E-ABMAPPO算法训练框架Fig.2 Training framework of E-ABMAPPO algorithm

为了充分挖掘MAPPO的性能,并加速其收敛,本文在训练中引入了Beta分布和注意力机制,具体方式如下:

① 基于Beta分布策略的Actor网络:MEC场景中的决策变量通常是连续且有界的,因此智能体输出的动作应尽可能满足此条件。由于Gaussian分布无界,通过强制截断输出动作的越界值将会导致边界效应,将不可避免地引入策略梯度的估计偏差[19]。为了缓解Gaussian分布策略的边界效应影响,本文在策略网络的输出层使用Beta分布替换Gaussian分布。Beta概率分布密度由下式给出:

(34)

式中:Γ(·)为Gamma函数,α和β为Beta分布的参数。式(34)有界,可以减小截断Gaussian分布带来的策略梯度估计误差,因此适合对有界动作进行采样。

② 具有注意力机制的Critic网络:对于简单全连接层的Critic网络而言,大量的状态输入会导致所需的模型复杂度快速升高,从而导致Critic网络的收敛缓慢或者难以收敛,对Actor网络的动作造成消极影响。本文在Critic网络的多层感知器(Multilayer Perceptron,MLP)之前引入了多头注意力单元,以提高模型训练的收敛性能。对于同种类型智能体的Critic网络,首先接受所有智能体的观测向量,将每种智能体的观测向量分别通过MU和UAV的MLP状态编码器,获得特征值ei。然后将所有智能体的特征值ei作为qi、ki、vi输入其多头注意力单元,以获得各注意力值xi,具体计算如下:

(35)

(36)

基于上述讨论,本文建立了E-ABMAPPO的训练框架,其算法实现过程如算法1所示。

算法1 基于E-ABMAPPO训练框架的联合优化算法输入:最大回合数Epmax,回合长度epl,PPO更新次数PE,折扣因子γ,PPO截断因子,GAE参数λ输出:训练后各智能体的Actor网络与Critic网络1. 初始化各类神经网络模型参数,设置n=1,构建训练环境; 2. FOR Episode,1≤Episode≤Epmax DO3. FOR t,1≤t≤epl DO4. MU智能体从环境中获得观测ok(t),∀k∈;5. 执行动作ak(t),∀k∈;6. UAV资源分配智能体和UAV轨迹优化智能体从环境中获得观测oK+m(t),oK+M+m(t),∀m∈;7. 地面控制中心收集系统状态与经验信息,评估奖励ri(t),∀i∈;8. 将经验 Tri(t)={oi(t),ai(t),ri(t),s(t)},∀i∈放入地面控制中心经验缓存区Bi中;9. IF n=N THEN10. 重置训练环境;

11. END IF12. n←n mod N+1;13. END FOR14. FOR epoch,1≤epoch≤PE DO15. FOR agents i∈DO16. 根据式(31)更新Actor网络参数θi17. 根据式(33)更新Critic网络参数ξi;18. END FOR19. END FOR20. END FOR

4 仿真结果与分析

本节首先对实验平台及实验参数进行简单说明,然后验证了所提算法的收敛性。在此基础上,针对不同的网络资源状况与场景进行了详细的性能实验与评估,并与基线算法进行了对比分析。

4.1 参数设置

本实验的仿真环境使用Python 3.7与PyTorch 1.11.0进行编写。本实验中设置的默认用户数量K为30,无人机数量M为5,总带宽B为15 MHz,任务量大小Dk[n]∈[0.5,1.5]Mb,单位比特平均计算量大小Ck[n]∈[800,1 200] cycles/b,时延约束tk[n]∈[0.7,1.0]s,权重因子设置为η=1,ϖ1=0.001,ϖ2=0.1ϖ1。对于所提算法,各种智能体的策略共享Actor网络参数,使用GAE计算优势函数;考虑到奖励值有界,不使用值归一化方法。其余实验参数与算法参数结合文献[12,20]进行设置,如表1所示。

表1 相关参数设置Tab.1 Parameter setting

为评价E-ABMAPPO方法中各智能体奖励的收敛性,2种基准MARL算法描述如下:

① MAPPO:该方法为不使用Beta分布-注意力机制改进方法的原始MAPPO算法,其奖励函数、动作和状态空间与所提算法相同[21]。

② MADDPG(Multi-Agent Deep Deterministic Policy Gradient):该方法与MAPPO都是目前较为主流和可靠的MARL算法[7]。它由双Actor网络与双Critic网络构成,其中Actor网络的输出即为动作值,之后加以一定探索噪声,Critic用于拟合动作值函数。

4.2 数值分析

本文对比了MU智能体和UAV资源分配智能体如图3和图4所示。从图3可以看出,对于MU智能体,所提E-ABMAPPO方法于4×104步左右收敛,收敛速度最快;MAPPO方法于8×104步左右收敛,而MADDPG方法收敛最慢,过程较为曲折,且所提算法获得的奖励最高,MAPPO次之,MADDPG最低。由此可以推断出,注意力机制能使MU在评价状态时关注更利于自身卸载的UAV,加速了算法的收敛性。此外,MADDPG探索策略的不足导致其收敛较慢或局部最优收敛。从图4可以观察到,所提算法在初期探索阶段前25×103步的奖励上升速度略快,在5×104步出现收敛,最后得到的奖励在-0.30左右。此外,可以看出在UAV资源分配智能体的训练上,所提方法与MAPPO方法训练速度仍然高于MADDPG。由此可见,基于MAPPO的方法探索环境的效率更高,且Beta分布能依据自身特性进一步提升探索—学习这一过程的速度与性能。

图3 MU智能体奖励值收敛性Fig.3 Convergence of MU agent reward

图4 UAV资源分配智能体奖励值收敛性Fig.4 Convergence of UAV resource allocation agent reward

图5展示了UAV的飞行轨迹情况。可以观察到,当UAV起点随机分布在区域内时,UAV能够保持在用户密集区提供服务,通过快速移动以尽可能顾及到更多的用户,当所服务用户在某一区域内时,通过盘旋以保持速率。为此,采用加速度作为决策变量能使轨迹平滑,更能应用于实际场景,UAV轨迹优化智能体学习到了一定的相互协作能力,通过部署到各个区域在空间上分配计算资源,提高MU的服务质量。

图5 UAV飞行轨迹情况Fig.5 Trajectories of UAVs

图6对比了4种算法在不同任务量大小下的性能。任务量大小从1 Mb 增大至2 Mb 时,所提方法的MU平均加权能耗最低,在0.13～0.24 J,随机算法最高,在0.27～0.53 J。相比于MAPPO和MADDPG,所提算法用户平均加权能耗分别降低了 22.5%～31.6%和33.5%～45.8%,相对于随机算法降低了43.7%以上。由此可见,MAPPO搜索到的策略优于MADDPG。这验证了Beta分布与注意力机制的使用能够提升MAPPO算法搜索到的策略质量,从而进一步提升MU的服务质量。

图6 不同任务量下算法性能对比Fig.6 Performance comparison under different tasks

5 结束语

本文提出了一种CTDE的无人机辅助MEC任务卸载方法,以降低移动用户与无人机的总能耗,提高边缘计算网络的可靠性。特别地,利用MARL方法解决了集中式执行的DRI算法不适于应对分布式、具有连续变量和离散变量的混合动作空间的难点,提出了针对不同智能体的特性进行奖励值设计,并将Beta分布与注意力机制引入MAPPO方法以提升探索能力与收敛性能。进行了仿真实验,将E-ABMAPPO与其他基准方法进行了对比,并分析了所提方法的性能。实验结果表明,E-ABMAPPO方法能够有效降低移动用户与无人机的加权能耗,验证了本文方法的有效性。未来工作将考虑多无人机协作与地面基站相结合的多层次边缘计算网络,设计无人机的飞行轨迹和协同计算卸载策略,以取得更好的系统性能。