基于多智能体联邦强化学习的无人机部署优化方法

1.本发明涉及无人机部署领域，具体涉及一种基于多智能体联邦强化学习的无人机部署优化方法。


背景技术：

2.无人机(unmannedaerial vehicles,uav)可以与移动边缘计算(mobile edge computing,mec)联合组成一个无人机辅助网络，以解决移动设备计算资源短缺的问题。它通过在网络边缘部署边缘服务器的方式将云中心的计算能力下沉到网络边缘，利用边缘服务器较为丰富的计算资源弥补了移动设备(mobile devices,md)计算能力的不足。此外，无人机辅助mec网络还特别适用于高密度公共应急、特别紧急情况和其他按需服务。在动态变化的运行时环境中，无人机的部署方案需要及时调度已获得理想的性能。本节将回顾和分析在无人机辅助mec系统中无人机部署优化问题的相关工作。目前针对无人机自适应部署问题主要包含基于启发式和基于学习的部署优化方法。
3.现有的关于无人机部署优化问题的研究大多采用启发式算法。然而，无人机部署方案的选择面临着组合爆炸的问题，而这些启发式算法无法在短时间内解决这一问题。由于需要大量的迭代来获得一个近似最优解，基于启发式的方法通常不适用于动态环境中实时的mec应用。为了解决这个问题，一些基于深度强化学习(drl)的方法被应用到了无人机调度策略中。这些方法一般采用集中式方式将所有无人机建模为一个单一的代理，这意味着需要一个控制中心来收集全局信息和控制所有代理。这种方法是难以扩展的，因为系统状态和动作空间的大小随着uav或md的数量呈指数级增长，并且在执行阶段需要高度的通信开销。将单代理drl应用于多代理场景的另一种方法是简单地使用drl方法对每个代理进行独立的训练，该方法会由于每个代理的策略随着训练的进行而变化，从而产生一个非稳定的环境。因此，分布式的drl方法更适用于动态环境下的大规模无人机辅助mec通信系统。然而，现有的分布式方法一般较少考虑无人机部署优化和时延约束。此外，智能体之间需要进行大量的通信和交互，可能会增加数据安全和隐私方面的风险。联邦学习可以使智能体能够在本地训练数据，只收集和分配神经网络的参数从而保护智能体的数据安全；
4.考虑到系统中无人机和移动设备的数量规模较大，传统的集中式算法将所有uav建模为一个智能体，这导致了模型不可扩展和额外通信开销的问题，难以有效实现大规模无人机的自适应部署。。


技术实现要素：

5.有鉴于此，本发明的目的在于提供一种基于多智能体联邦强化学习的无人机部署优化方法，实现高效且自适应的无人机部署。
6.为实现上述目的，本发明采用如下技术方案：
7.一种基于多智能体联邦强化学习的无人机部署优化方法，包括以下步骤：
8.步骤s1:将多uav辅助的mec系统的每台uav建模为一个智能体,每台uav根据运行
时环境中收集到的局部信息进行独立决策，并通过设计状态空间、行动空间、转换函数和奖励函数，将uav的动态部署问题建模为马尔可夫问题模型；
9.步骤s2:采用k-mafrl算法训练无人机部署操作的q值预测联邦模型，步骤s3:在执行阶段，每台uav使用步骤s2中得到的无人机部署操作q值预测联邦模型，根据其运行时环境中的局部信息预测不同部署操作的q值，并通过比较q值来选择合适的无人机部署操作，并通过反馈控制和多无人机协同，逐步找到有效的大规模无人机部署方案。
10.进一步的，所述多uav辅助的mec系统由两层结构组成，即由m个md组成的地面层和由n台uav组成的空中层；所述多uav辅助的mec系统中的所有md和uav分别用μ＝{1,2,
…
,m}和ν＝{1,2,
…
,n}表示；使用三维欧几里得坐标系来表示多uav辅助的mec系统内md和uav的位置；
11.md m∈μ的坐标表示为其中和用以表示md m在水平面上的位置；所述多uav辅助的mec系统中所有uav的部署位置用表示，其中为uav n的部署位置，和用于表示uav n在水平面上的部署位置，h表示uav的飞行高度。
12.进一步的，将目标服务区域划分为i
×
j个等面积的单元，每台uav都部署在高度为h的各单元中心上空，并且uav只在各个单元之间移动；
13.md m∈μ的计算任务am用一个正元组《im,dm,om》表示，其中im表示am的输入数据的大小，以比特(bit)为单位；dm表示am的计算复杂度，即计算每一比特输入数据需要的cpu周期数，以cycle/bit为单位；om表示am的计算结果大小，以比特(bit)为单位；
14.md m∈μ与uavn∈ν之间的无线信道用自由空间路径损耗模型进行模拟，表示为
[0015][0016]
其中表示md m与uav n之间的空间距离，φ0表示单位空间距离的无线信道增益；md m与uav n之间无线信道的传输速率为
[0017][0018]
其中β表示无线信道带宽，pm表示第m个md的发射功率，σ2为无线信道中高斯白噪声功率。
[0019]
考虑到所有的uav和md都提供计算服务，md上的计算任务可卸载到uav上执行也可以在本地执行；定义一个二进制变量ξ＝{ξ
m,n
|m∈{1,...,m},n∈{0,1,...,n}}以表示md与uav的接入关系，其中ξ
m,n
∈{0,1}表示md m与uav n之间的接入关系，当md m决定将计算任务卸载到uavn上执行时，ξ
m,n
＝1，否则ξ
m,n
＝0；特别地，当ξ
m,0
＝1时，计算任务在本地执行；设每个md只将计算任务卸载到一台uav上执行，即
[0020][0021]
设每架无人机在所考虑的时隙内接收的计算任务数不能超过最大并行任务数n
max
，即有以下约束
[0022][0023]
进一步的，所述多uav辅助的mec系统的md和uav的接入策略，具体如下：遍历每个md，如果计算任务在本地执行的时间小于卸载到最近uav上的计算时间，则该任务在本地执行；否则，md m尝试将任务卸载到uavn上；若该卸载操作超出uav的服务上限n
max
，则搜索已接入的距离uavn最远的md并使其在本地执行。通过对每个用户执行贪心策略可以得到最终的md-uav接入关系ξ。
[0024]
进一步的，所述多uav辅助的mec系统目标函数的构建具体如下：
[0025]
将md m∈μ在计算任务本地执行过程中的cpu时钟频率定义为f
ml
，则计算任务am输入数据的本地计算时延量化为：
[0026][0027]
计算任务am在uav n上计算的总时延为:
[0028][0029]
其中im/r
m,n
表示任务输入数据从md m传输到uavn的传输时延；i
mdm
/f
m,n
表示计算任务am在uav上的执行时延；f
nu
表示uavn执行任务am时的cpu时钟频率；
[0030]
计算任务am的执行完成时间为:
[0031][0032]
将最小化平均任务响应时间作为优化目标，将目标函数定义为:
[0033][0034][0035][0036][0037][0038][0039]
其中，约束c1和c2表示uav的部署范围约束；约束c3分别表示任务采用完全卸载策略；约束c4表示每个md只将计算任务卸载到一台uav上执行或本地执行；约束c5表示每台uav接收的任务数量不能超过其最大并行处理数。
[0040]
进一步的，所述马尔可夫问题模型定义为一个4元组，用《s、a、r、p》表示，其中s是状态空间，a是动作空间，r是奖励函数，p是状态转移函数。根据第3节所述的问题形式化，各智能体所对应的状态空间s、动作空间a、状态转移函数p和奖励函数r定义如下：
[0041]
状态空间：uavn智能体的状态空间用sn表示；sn被定义成一个3元组义《f
nu
,bn,cn》，
其中包含uavn的计算能力f
nu
，当前uav可视范围内其他无人机的分布情况bn以及地面用户分布情况c
n；
[0042]
动作空间：将uav的动作空间离散化并定义了5个动作，因此uavn的动作空间定义为an＝{0,1,2,3,4}，其中包含将动作方向水平分散到东南西北4个飞行方向的动作和一个垂直悬停动作，悬停动作使uav找到合适位置后保持当前状态；
[0043]
状态转移函数：状态转移函数p(an,sn,s'n)记录给定当前状态sn和应用于sn的当前动作an下一个状态s'n的概率；具体的转移函数表示为
[0044]
p(an,sn,s'n)＝pr(s'n|sn,an)
[0045]
奖励函数：在多无人机部署优化问题中，每个uav都具有相同的目标，即最小化系统平均响应时间，因此将uavn的奖励函数定义为
[0046]rn
＝t-t'
[0047]
其中rn表示uavn在当前状态sn下执行动作an后该智能体所得到的奖励，其中t和t’分别表示部署方案执行动作前后的系统响应时间。
[0048]
进一步的，所述马尔可夫问题模型在训练过程中，每个智能体在运行时从mec环境中获取状态s，再通过最优策略π
*
选择动作a；mdp问题的最优策略π
*
表示为
[0049]
π
*
(s,a)＝argmaxq(s,a；ω)
[0050]
智能体执行动作a之后会从环境中收到相应的奖励值r以及下一个状态s’；接下来基于dqn算法将每一步得到的(s,a,r,s’)存放到经验存放池中；当达到存储阈值后，对神经网络参数进行更新，神经网络的损失函数如下
[0051]
loss＝(r+γmaxq(s',a'；ω')-q(s,a；ω))2[0052]
其中r是奖励值，γ是折扣因子，maxq(s',a'；ω')为targetnet的输出，用于计算在下一个状态s’下选择动作a’所获得的最大q值，q(s,a；ω)是evalnet的输出，用于计算当前状态-动作对的q值。
[0053]
进一步的，所述k-mafrl算法包括两个基本部分：
[0054]
(1)分布式训练，每个uav智能体都使用标准的dqn算法与环境交互来训练其本地模型；在本地训练完成后，从每个智能体中提取网络参数发送到中央聚合单元；
[0055]
(2)联邦聚合，当中央单元接收到各智能体的网络参数时，它将聚合这些网络参数生成一个全局模型，然后将其模型参数传输回所有的智能体以更新其本地网络。
[0056]
进一步的，使用fedavg方法执行模型聚合：
[0057][0058]
其中，ωg和ωn分别表示全局网络参数和第n个uav智能体的本地网络参数。
[0059]
进一步的，所述步骤s3具体为：
[0060]
随机初始化每个uav智能体的evalnet和targetnet的网络权重，并在每个回合初始化无人机的起始位置；
[0061]
在本地模型训练过程中，各智能体与不同场景下的运行时环境交互，观察当前uav周围的局部状态并通过策略π
*
选择飞行动作an；然后计算执行动作an后获得的奖励rn并获取下一状态s'n；
[0062]
接下来,(sn,an,rn,s
n’)被存储到经验池中，其中随机抽取最小批量样本并计算目
标q值。这些样本可能来自不同的运行时环境以保证了学习的充分性。；
[0063]
然后，根据均方损失函数执行梯度下降并更新evalnet神经网络权重ω，并在到达设定的c轮迭代后更新targetnet神经网络权重；
[0064]
接下来，中央聚合单元从所有智能体中接收网络参数并对全局网络进行训练，具体来说，上传的参数通过联邦平均算法来拟合全局q网络；
[0065]
最后，中央聚合单元将全局q网络的参数分发给各个智能体，每个智能体以此更新它们的本地网络。
[0066]
本发明与现有技术相比具有以下有益效果：
[0067]
本发明使用强化学习结合联邦学习方法，面向动态环境下大规模的mec场景研究无人机的部署优化问题，从而实现高效且自适应的无人机部署，以最小化系统平均任务响应时间。
附图说明
[0068]
图1是本发明方法框架；
[0069]
图2是本发明一实施例中多无人机辅助的mec系统；
[0070]
图3是本发明一实施例中k-mafrl与经典算法在变化mds规模下的性能对比；
[0071]
图4是本发明一实施例中无人机数量对于平均任务响应时间的影响；
[0072]
图5是本发明一实施例中mds数量对于平均任务响应时间的影响；
[0073]
图6是本发明一实施例中uav初始置位算法对平均任务响应时间的影响。
具体实施方式
[0074]
下面结合附图及实施例对本发明做进一步说明。
[0075]
请参照图1，本发明提供一种基于多智能体联邦强化学习的无人机部署优化方法，包括以下步骤：
[0076]
步骤s1:将多uav辅助的mec系统的每台uav建模为一个智能体,每台uav根据运行时环境中收集到的局部信息进行独立决策，并通过设计状态空间、行动空间、转换函数和奖励函数，将uav的动态部署问题建模为马尔可夫问题模型；
[0077]
步骤s2:采用k-mafrl算法训练无人机部署操作的q值预测联邦模型，步骤s3:在执行阶段，每台uav使用步骤s2中得到的无人机部署操作q值预测联邦模型，根据其运行时环境中的局部信息预测不同部署操作的q值，并通过比较q值来选择合适的无人机部署操作，并通过反馈控制和多无人机协同，逐步找到有效的大规模无人机部署方案。
[0078]
参考图2，在本实施例中，多uav辅助的mec系统由两层结构组成，即由m个md组成的地面层和由n台uav组成的空中层；系统中的所有mds和uavs分别用μ＝{1,2,
…
,m}和ν＝{1,2,
…
,n}表示。我们使用三维欧几里得坐标系来表示系统内mds和uavs的位置，md m∈μ的坐标可以表示为其中和用以表示md m在水平面上的位置。系统中所有uavs的部署位置用表示，其中为uav n的部署位置，和用于表示uav n在水平面上的部署位置，h表示uav的飞行高度。由于无人机的可选部署方案随着其数量的增加呈指数级增长，为了简化问题模型，我们
将目标服务区域划分为i
×
j个等面积的单元，每台uav都部署在高度为h的各单元中心上空，并且uav只在各个单元之间移动。我们假设uav在计算任务处理过程中悬停在固定高度h》0，其中h》0为uav与工作地形相适应且能避免障碍物的最小高度，uav在飞行过程中无需频繁升降。
[0079]
md m∈μ的计算任务am可以用一个正元组《im,dm,om》表示，其中im表示am的输入数据(例如程序代码和输入参数)的大小，以比特(bit)为单位；dm表示am的计算复杂度，即计算每一比特输入数据需要的cpu周期数，以cycle/bit为单位；om表示am的计算结果大小，以比特(bit)为单位。计算任务的特性由产生它的设备决定，即每个计算任务的输入数据大小、计算复杂度、计算结果大小都不相同。
[0080]
md m∈μ与uavn∈ν之间的无线信道可用自由空间路径损耗模型进行模拟，表示为
[0081][0082]
其中表示md m与uav n之间的空间距离，φ0表示单位空间距离的无线信道增益。md m与uav n之间无线信道的传输速率为
[0083][0084]
其中β表示无线信道带宽，pm表示第m个md的发射功率，σ2为无线信道中高斯白噪声功率。
[0085]
考虑到所有的uavs和mds都可提供计算服务，mds上的计算任务可卸载到uavs上执行也可以在本地执行。定义一个二进制变量ξ＝{ξ
m,n
|m∈{1,...,m},n∈{0,1,...,n}}以表示mds与uavs的接入关系，其中ξ
m,n
∈{0,1}表示md m与uavn之间的接入关系，当md m决定将计算任务卸载到uavn上执行时，ξ
m,n
＝1，否则ξ
m,n
＝0。特别地，当ξ
m,0
＝1时，计算任务在本地执行。我们假设每个md只将计算任务卸载到一台uav上执行，即
[0086][0087]
此外，由于无人机的并行计算能力有限，我们假设每架无人机在所考虑的时隙内接收的计算任务数不能超过最大并行任务数n
max
，即有以下约束
[0088][0089]
在本实施例中，优选的，对于mds和uavs的接入策略假定采用如下方案：当uavs确定部署位置之后，利用基于贪心卸载的策略决定md-uav接入关系，把mds的计算任务卸载到距离当前md最近的uav上以减少卸载时间。具体过程描述为：遍历每个md，如果计算任务在本地执行的时间小于卸载到最近uav上的计算时间，则该任务在本地执行；否则，md m尝试将任务卸载到uav n上。考虑到uav的计算能力有限，只能为一定数量的mds提供卸载服务，若该卸载操作超出uav的服务上限n
max
，则搜索已接入的距离uav n最远的md并使其在本地执行。通过对每个用户执行贪心策略可以得到最终的md-uav接入关系ξ。
[0090]
假设所有mds均采用完全卸载策略，mds的计算任务可卸载到uavs上执行也可以在
本地执行。我们将md m∈μ在计算任务本地执行过程中的cpu时钟频率定义为(以hz为单位)，则计算任务am输入数据的本地计算时延可以量化为
[0091][0092]
当md将计算任务的输入数据卸载到uav上执行时，所产生的时延由三部分组成：1)计算任务输入数据从md传输到uav所产生的通信时延；2)计算任务输入数据在uav上执行所产生的计算时延；3)计算结果从uav回传到md所产生的通信时延。特别的，与输入数据相比，计算结果的大小往往很小，输出计算结果所产生的通信时延很小，所以我们忽略了该过程产生的通信时延。忽略计算结果的回传过程可以大大降低模型的复杂性，这已被许多研究所采用。所以计算任务am在uav n上计算的总时延为
[0093][0094]
其中im/r
m,n
表示任务输入数据从md m传输到uavn的传输时延；i
mdm
/f
m,n
表示计算任务am在uav上的执行时延；f
nu
表示uavn执行任务am时的cpu时钟频率。
[0095]
综上所述，计算任务am的执行完成时间为
[0096][0097]
不同无人机位置和用户位置将会导致不同的任务执行时间，为了在多uav辅助的mec环境中实现更好的计算卸载效果，我们将最小化平均任务响应时间作为优化目标，将目标函数定义为
[0098][0099]
其中，约束c1和c2表示uavs的部署范围约束；约束c3分别表示任务采用完全卸载策略；约束c4表示每个md只将计算任务卸载到一台uav上执行或本地执行；约束c5表示每台uav接收的任务数量不能超过其最大并行处理数。
[0100]
uav n的局部信息包含该无人机的部署位置(表示为)，该无人机的计算能力(表示为f
nu
)，该无人机可视范围内其他uavs的分布情况(表示为bn)和地面移动设备的分布情况(表示为cn)，如表1所示。具体来说，我们将uav n的可视范围区域划分为l
×
l个单元，设其中表示单元(i,j)内分布的其他uav数量；设其中表示单元(i,j)内分布的mds数量。此外，t表示
当前uavs整体部署方案的系统平均任务响应时间，t越小则说明部署方案效果越好，t’表示在uav n执行部署动作an后的系统平均任务响应时间。
[0101]
表1运行时环境中uavn的局部信息及性能指标
[0102][0103]
在本实施例中，采用dqn(deep q-networks)算法来评估无人机不同部署操作的q值，以探索无人机部署方案。基于dqn算法，每台uav被建模为一个智能体并且可以根据运行时环境中的局部信息进行部署决策。通过训练dqn代理，可以找到不同系统状态下q值最高的部署操作，其中dqn算法用于控制q值评估过程。rl的目标是累积报酬的最大化，通常采用马尔可夫决策过程(markov decisionprocess,mdp)对其进行建模。更具体地说，mdp可以定义为一个4元组，用《s、a、r、p》表示，其中s是状态空间，a是动作空间，r是奖励函数，p是状态转移函数。根据第3节所述的问题形式化，各智能体所对应的状态空间s、动作空间a、状态转移函数p和奖励函数r定义如下：
[0104]
状态空间：uavn智能体的状态空间用sn表示。为了综合考虑运行环境和无人机部署方案之间的特点，sn被定义成一个3元组义《f
nu
,bn,cn》，其中包含uavn的计算能力f
nu
，当前uav可视范围内其他无人机的分布情况bn以及地面用户分布情况cn。
[0105]
动作空间：将uavs的动作空间离散化并定义了5个动作，因此uavn的动作空间定义为an＝{0,1,2,3,4}，其中包含将动作方向水平分散到东南西北4个飞行方向的动作和一个垂直悬停动作，悬停动作可以使uav找到合适位置后保持当前状态。
[0106]
状态转移函数：状态转移函数p(an,sn,s'n)记录给定当前状态sn和应用于sn的当前动作an下一个状态s'n的概率。具体的转移函数可以表示为
[0107]
p(an,sn,s'n)＝pr(s'n|sn,an)
ꢀꢀ
公式(3-1)
[0108]
奖励函数：在多无人机部署优化问题中，每个uav都具有相同的目标，即最小化系统平均响应时间，因此将uav n的奖励函数定义为
[0109]rn
＝t-t'
ꢀꢀ
公式(3-2)
[0110]
其中rn表示uavn在当前状态sn下执行动作an后该智能体所得到的奖励，其中t和t’分别表示部署方案执行动作前后的系统响应时间。因此，t
–
t’为负值。为了最大化累计奖励，算法那可以得到最小响应时间。
[0111]
在训练过程中，每个dqn智能体在运行时从mec环境中获取状态s，再通过最优策略π
*
选择动作a。通常，mdp问题的最优策略π
*
可以表示为
[0112]
π
*
(s,a)＝argmaxq(s,a；ω)
ꢀꢀ
公式(3-3)
[0113]
dqn智能体执行动作a之后会从环境中收到相应的奖励值r以及下一个状态s’。接下来dqn算法将每一步得到的(s,a,r,s’)存放到经验存放池中。通常，dqn算法中的经验存放池的容量是预先设定好的，当达到存储阈值后，对神经网络参数进行更新，神经网络的损失函数如下
[0114]
loss＝(r+γmaxq(s',a'；ω')-q(s,a；ω))2ꢀꢀ
公式(3-4)
[0115]
其中r是奖励值，γ是折扣因子，maxq(s',a'；ω')为targetnet的输出，用于计算在下一个状态s’下选择动作a’所获得的最大q值，q(s,a；ω)是evalnet的输出，用于计算当前状态-动作对的q值。
[0116]
在本实施例中，在训练阶段，k-mafrl算法允许智能体分布式地训练其本地模型，然后将这些本地模型发送到一个中央聚合单元以构建一个全局网络。与集中式算法不同，这种通信只需要上传每个智能体的模型参数，这大大降低了通信的负载和延迟。k-mafrl算法中所有智能体的本地模型具有相同的网络结构，并通过联邦平均的方式聚合成全局模型。k-mafrl算法包括两个基本部分：
[0117]
(1)分布式训练。每个uav智能体都使用标准的dqn算法与环境交互来训练其本地模型。在本地训练完成后，从每个智能体中提取网络参数发送到中央聚合单元。
[0118]
(2)联邦聚合。当中央单元接收到各智能体的网络参数时，它将聚合这些网络参数生成一个全局模型，然后将其模型参数传输回所有的智能体以更新其本地网络。我们使用fedavg方法执行模型聚合：
[0119][0120]
其中，ωg和ωn分别表示全局网络参数和第n个uav智能体的本地网络参数。
[0121]
基于上述定义，我们利用k-mafrl算法训练联邦模型用于评估所有无人机部署操作的q值。该算法的关键步骤如算法1所示。首先，随机初始化每个uav智能体的evalnet和targetnet的网络权重(第3-5行)并在每个回合根据算法2初始化无人机的起始位置。在本地模型训练过程中，各智能体与不同场景下的运行时环境交互，观察当前uav周围的局部状态并通过策略π
*
选择飞行动作an(第10行)。然后通过公式9计算执行动作an后获得的奖励rn并获取下一状态s'n(第11行)。接下来,(sn,an,rn,s
n’)被存储到经验池中，其中随机抽取最小批量样本并计算目标q值。这些样本可能来自不同的运行时环境以保证了学习的充分性。(第12-13行)。然后，根据均方损失函数执行梯度下降并更新evalnet神经网络权重ω，并在到达设定的c轮迭代后更新targetnet神经网络权重(第14-16行)。接下来，中央聚合单元从所有智能体中接收网络参数并对全局网络进行训练，具体来说，上传的参数通过联邦平均算法来拟合全局q网络(第18-19行)。最后，中央聚合单元将全局q网络的参数分发给各个智能体，每个智能体以此更新它们的本地网络(第20行)。
[0122][0123]
1.1运行时决策机制
[0124]
in general,mds分布的密集性决定了该区域计算资源的需求量，我们根据当前mds的地面分布情况利用k-means算法对uavs进行初始置位，其主要步骤见算法2。首先将k-means类簇数设置为n并初始化类簇质心(第3行)，然后计算每个md到类簇质心的距离并将其划分到最近类簇中(第5-8行)，接着根据新的类簇更新类簇质心(第9-11行)，迭代上述操作直到最大迭代次数i，并以最终聚类结果初始化uavs的起始位置。
[0125][0126]
在执行阶段，无人机的部署过程包含两个步骤：首先，考虑到无人机初始位置对于结果的影响，我们利用聚类算法生成无人机的初始位置；然后，利用k-mafrl算法训练好的模型，每台无人机可以根据局部信息进行独立决策，并通过反馈控制和多无人机协同逐步找到有效的部署方案。
[0127]
无人机部署操作的决策过程是在运行时进行的。本发明提出了一种运行时决策算法，通过反馈控制机制和多无人机协同逐步找到合理的无人机部署方案，其主要步骤如算法3所示。首先利用算法2根据当前mds的分布情况初始化无人机位置。然后，对于uavn更新其局部信息(第6行)。由于uavn的局部信息在运行时不断发生变化，所以在每一轮决策之前都应该重新获得。通过调用q值预测联邦模型来评估uavn每个部署操作的q值，并得到最大q值对应的动作(第7-8行)。如果得到的动作值为0，则uav n保持悬停不再进行调整(第9-10行)。否则，将继续调整uavn的部署位置(第12行)。
[0128][0129]
通过迭代反馈控制过程，可以在运行时环境中逐步实现大规模无人机部署。反馈控制将持续进行，直到所有无人机都到达最佳部署位置。
[0130]
实施例1：
[0131]
本实施例通过以下研究问题(rqs)评估所出的k-mafrl。
[0132]
●
rq1：与其他常用的基线算法相比，k-mafrl的性能提升了多少？
[0133]
●
rq2：不同规模的无人机数量和移动设备数量对方法会有怎样的影响？
[0134]
·
rq3：当使用k-mafrl求解平均响应时间优化问题时，无人机初始置位算法是否有效？
[0135]
对于rq1，实验结果显示，k-mafrl方法在不同场景下所得到的无人机部署方案的平均任务响应时间相对于常用的基准方法pso-ga、cdrl、greedy和random分别平均减少了2.47％、4.22％、5.76％和8.91％。此外，k-mafrl可以在更短时间内得到uav部署方案，执行时间相比pso-ga、cdrl、greedy和random算法分别平均减少了99.3％、13.4％、67.7％、99.4％。对于rq2，在大规模实验下，k-mafrl的平均响应时间优于其他算法，同时，性能差距随着uav数量和md数量的增加逐渐增大。对于rq3，将k-mafrl与采用随机初始置位的mafrl进行了比较，k-mafrl所得到uavs部署方案的平均任务响应时间相比mafrl平均减少了1.70％，并且k-mafrl的执行时间比mafrl的平均减少了24.3％。
[0136]
在本实施例中，为了模拟应用场景的多样性，我们考虑了四种不同的方形实验区域，其中实验区域大小分别为400*400m2、600*600m2、800*800m2、1000*1000m2，mds在实验区域内随机分布。此外，对于不同大小的实验区域设置了不同的uavs和mds规模，如表所示。该区域分布的mds的cpu周期频率为0.8～1.2ghz，所有无人机的cpu周期频率设置为2.5～
3.5ghz。系统中所有计算任务的输入数据大小在10～20mbit范围内随机分布，计算任务的复杂度设置为80～120cycle/bit。mds的发射功率设置为1w，单位空间距离的无线信道增益设置为-20db，无线信道带宽设置为10mhz，高斯白噪声功率-1
×
10-5
dbm。
[0137]
表2实验规模设置
[0138]
实验区域大小/m2uavs数量nmds数量m400＊400840600＊6001890800＊800321601000＊100050250
[0139]
所提出的k-mafrl基于tensorflow 2.3.0实现。在k-mafrl中，使用由一个输入层、两个隐藏层和一个输出层组成的全连接dnn网络，其中两个隐藏层分别具有256、128个隐藏神经元。经验池大小mc、训练批量样本大小m、折扣因子γ和adam优化器的学习率α分别设置为15000、64、0.9和0.001。此外，我们在四种不同的实验区域中都对联邦模型训练10000个回合，得到的模型可以适用于不同区域大小的场景。
[0140]
为了验证k-mafrl算法的性能优势，我们将算法与无人机辅助mec系统中其他常用的基准方法进行了比较。相关的对比算法描述如下：
[0141]
●
集中式dqn：集中式dqn根据运行时环境中收集到的全局信息为所有无人机进行集中式决策。状态空间包含所有uavs和mds的信息，动作空间设置为所有无人机部署动作的集合。学习率α、折扣因子β、经验池大小容量m以及训练回合数分别设置为0.001、0.9、10000和10000。集中式dqn需要根据不同场景和不同实验规模对模型进行训练。
[0142]
●
pso-ga：通过引入遗传算法的交叉和变异算子改进传统pso算法的粒子更新策略。每个粒子代表系统中所有uavs的一种部署方案，粒子的每个分位编码为各uav的部署位置。两个学习因子c1和c2的起止值和惯性权重w的最大值和最小值分别设置为0.9、0.2、0.9、0.4、0.9和0.4。迭代次数和种群数设置为1000和50。
[0143]
·
贪心算法：基于当前uavs部署位置，每台uav在所有动作中选择一个可以导致最小化平均任务响应时间的动作执行。不断逐台更新无人机的位置，直到所有uav的即时动作都无法得到更好的响应时间。
[0144]
·
随机算法：所有uav在服务区域内随机选择部署位置，取20000次重复实验结果的最优值作为最终结果。
[0145]
图3显示了所提出的k-mafrl算法与其他基准算法在不同场景下的任务平均响应时间的比较。从图中可以看出，在四种实验区域中，k-mafrl的响应时间比pso-ga平均减少了2.47％。特别的，当区域大小为400*400m2时，k-mafrl的响应时间比pso-ga平均高3.09％，而在其他三种大小的实验区域中，k-mafrl的响应时间比pso-ga减少了2.07～6.55％。这是因为pso-ga获得的解的质量可能会受到解空间大小的影响。如果解空间较小，pso-ga可以通过交叉和变异操作得到高质量的方案。例如，当区域大小为400*400m2时，pso-ga能够搜索各种场景下的最优方案。但是，当面对较大的解空间时，pso-ga容易陷入局部最优而无法达到最优方案。如图3所示，k-mafrl在不同实验区域下的任务响应时间相比cdrl平均减少了4.22％。具体来说，当区域大小为400*400m2时，k-mafrl和cdrl达到同等性能,而在其他三种大小的实验区域中，k-mafrl的性能比cdrl好3.14～8.12％。cdrl根据全
局信息对uavs进行集中式部署，当实验规模较小时，cdrl在训练过程中可以覆盖到较为全面的状态信息。然而随着实验规模的增大，大规模的无人机和移动用户意味着更大的系统状态空间和动作空间，这导致训练任务的难度更大，因此难以表现出较好的性能。从图中我们还可以看出，在不同的实验区域下，k-mafrl的性能均优于greedy和random，其响应时间比greedy、random算法分别减少2.65～9.25％和5.11～13.05％。对于greedy算法，由于每次优化只考虑当前最优的部署操作，其计算出来的方案一般都为局部最优解，因此对平均任务响应时间的优化效果有限。而random算法仅是对无人机进行随机部署，完全忽略了mds的位置和计算任务大小对任务响应时间的影响，所以它的性能表现较差。
[0146]
如表3所示，我们评估了五种方法在不同大小的实验区域中获得uav部署方案所需要的执行时间，其中实验结果取四种场景时间开销的平均值。相比之下，k-mafrl算法所用的时间最少，得到uav部署方案所需要的时间比pso-ga、cdrl、greedy和random算法分别平均减少了99.3％、13.4％、67.7％、99.4％。cdrl算法将全局信息作为输入，而随着实验规模的增大，高维度的状态空间增加了算法执行的复杂度。greedy算法需要在执行过程中穷举所有无人机动作所对应的部署方案性能，直到所有无人机的即时动作都无法得到更好的部署方案才算到达局部解，因此需要更长的执行时间。此外，pso-ga和random算法需要大量迭代才能保证所得解的质量，因此执行时间比另外三种算法要长得多。综上所述，所提出的k-mafrl算法可以在更短的时间内得到更优质的大规模无人机部署方案，具有更高的应用价值。
[0147]
表3找到目标部署方案所需时间(s)
[0148]
areasizek-mafrlpso-gacdrlgreedyrandom400*400m21.993274.1351.7652.773289.027600*600m24.116655.0285.0818.327687.278800*800m28.0331212.52910.39018.3231346.5361000*1000m214.3772286.31618.12144.5372523.568
[0149]
接下来，我们进一步评估了所提出的方法在不同实验规模(eg.不同规模的uavs和mds)下的性能表现，使用的对比算法设置与rq1中的算法相同。图4显示了不同无人机数量对于算法平均任务响应时间的影响。从图中可以看出，当mds的数量(即m)不变时，平均响应延迟随着无人机数量的增加而减少。这种现象是因为当待服务的mds数量不变而无人机数量增加时，mds的计算任务可以选择卸载的无人机就更多，同时mds和提供服务的uavs之间的距离也会减小，因此任务的卸载时间也相应减少。我们也可以看出，在600*600m2、800*800m2、1000*1000m2的实验区域中，当uavs数量大于15时，所提出的k-mafrl的平均响应时间都优于其他算法，此外，随着无人机数量的增加性能差距逐渐增大。这是因为在大规模uavs环境中，k-mafrl中每台uav根据局部信息独立地进行部署决策，可以适应于无人机数量的变化，而cdrl的状态空间和动作空间随着无人机数量的增加而呈指数级增长，其他传统方法则因为解空间的增大性能逐渐降低。
[0150]
图5显示不同mds数量与平均任务响应时间的关系。实验结果表明，当系统中无人机的数量(即n)不变时，平均响应延迟会随着md数量的增加而增加。出现上述现象的原因是当md数量增加时，每架无人机需要为更多的md提供计算服务，而uavs计算资源有限导致了mds的任务可能卸载到更远的uav上或者选择在本地执行，因此平均任务响应时间会相应地
增大。从图中可以看出，在600*600m2、800*800m2、1000*1000m2的实验区域中，当mds数量大于70时k-mafrl的平均任务响应时间总是低于其他方法的时间。这是因为在大规模mds环境中，k-mafrl中每台uav只观察环境中的局部信息，再通过模型聚合进行数据共享，状态空间的设定更能适应大规模的mds场景。相比之下，pso-ga、cdrl、greedy和random算法性能逐渐落后于k-mafrl算法，因为cdrl的状态空间随着mds数量增加而增大，这大大降低了方法的收敛效率；更多mds的复杂环境也极大限制了其他传统方法的性能。
[0151]
最后我们将k-mafrl与uavs采用随机初始置位的mafrl进行了比较，以评估初始置位算法在方法中的有效性，其中实验环境与rq1中的场景相同。图6比较了两种方法在不同系统场景下获得的平均任务响应时间。从图中可以看出，k-mafrl所得到的平均任务响应时间相比mafrl平均减少了1.70％，这说明方法基于k-means进行初始置位可以找到更合适的uavs部署方案。此外，我们还比较了两种方法找到uavs部署方案的平均时间开销，如表4所示。实验结果显示，k-mafrl的执行时间比mafrl的平均减少了24.3％，这是因为k-mafrl通过k-means对无人机进行初始置位后，仅需要更少的反馈迭代次数就可以在解空间中搜索到较优的解。由此可见，uavs初始置位算法可以使所提出方法在更短的时间内得到更优质的uavs部署方案。
[0152]
表4找到目标部署方案所需要的时间(s)
[0153]
areasize400*400m2600*600m2800*800m21000*1000m2k-mafrl1.9243.7887.48514.590mafrl2.2295.35210.40119.793
[0154]
以上所述仅为本发明的较佳实施例，凡依本发明申请专利范围所做的均等变化与修饰，皆应属本发明的涵盖范围。

技术特征：
1.一种基于多智能体联邦强化学习的无人机部署优化方法，其特征在于，包括以下步骤：步骤s1:将多uav辅助的mec系统的每台uav建模为一个智能体,每台uav根据运行时环境中收集到的局部信息进行独立决策，并通过设计状态空间、行动空间、转换函数和奖励函数，将uav的动态部署问题建模为马尔可夫问题模型；步骤s2:采用k-mafrl算法训练无人机部署操作的q值预测联邦模型，步骤s3:在执行阶段，每台uav使用步骤s2中得到的无人机部署操作q值预测联邦模型，根据其运行时环境中的局部信息预测不同部署操作的q值，并通过比较q值来选择合适的无人机部署操作，并通过反馈控制和多无人机协同，逐步找到有效的大规模无人机部署方案。2.根据权利要求1所述的基于多智能体联邦强化学习的无人机部署优化方法，其特征在于，所述多uav辅助的mec系统由两层结构组成，即由m个md组成的地面层和由n台uav组成的空中层；所述多uav辅助的mec系统中的所有md和uav分别用μ＝{1,2,
…
,m}和ν＝{1,2,
…
,n}表示；使用三维欧几里得坐标系来表示多uav辅助的mec系统内md和uav的位置；md m∈μ的坐标表示为其中和用以表示md m在水平面上的位置；所述多uav辅助的mec系统中所有uav的部署位置用表示，其中为uav n的部署位置，和用于表示uav n在水平面上的部署位置，h表示uav的飞行高度。3.根据权利要求2所述的基于多智能体联邦强化学习的无人机部署优化方法，其特征在于，将目标服务区域划分为i
×
j个等面积的单元，每台uav都部署在高度为h的各单元中心上空，并且uav只在各个单元之间移动；md m∈μ的计算任务a
m
用一个正元组<i
m
,d
m
,o
m
>表示，其中i
m
表示a
m
的输入数据的大小，以比特(bit)为单位；d
m
表示a
m
的计算复杂度，即计算每一比特输入数据需要的cpu周期数，以cycle/bit为单位；o
m
表示a
m
的计算结果大小，以比特(bit)为单位；md m∈μ与uav n∈ν之间的无线信道用自由空间路径损耗模型进行模拟，表示为其中表示md m与uav n之间的空间距离，φ0表示单位空间距离的无线信道增益；md m与uav n之间无线信道的传输速率为其中β表示无线信道带宽，p
m
表示第m个md的发射功率，σ2为无线信道中高斯白噪声功率；考虑到所有的uav和md都提供计算服务，md上的计算任务可卸载到uav上执行也可以在本地执行；定义一个二进制变量ξ＝{ξ
m,n
|m∈{1,...,m},n∈{0,1,...,n}}以表示md与uav的接入关系，其中ξ
m,n
∈{0,1}表示md m与uav n之间的接入关系，当md m决定将计算任务卸载到uavn上执行时，ξ
m,n
＝1，否则ξ
m,n
＝0；特别地，当ξ
m,0
＝1时，计算任务在本地执行；设每
个md只将计算任务卸载到一台uav上执行，即设每架无人机在所考虑的时隙内接收的计算任务数不能超过最大并行任务数n
max
，即有以下约束4.根据权利要求2所述的基于多智能体联邦强化学习的无人机部署优化方法，其特征在于，所述多uav辅助的mec系统的md和uav的接入策略，具体如下：遍历每个md，如果计算任务在本地执行的时间小于卸载到最近uav上的计算时间，则该任务在本地执行；否则，md m尝试将任务卸载到uav n上；若该卸载操作超出uav的服务上限n
max
，则搜索已接入的距离uav n最远的md并使其在本地执行。通过对每个用户执行贪心策略可以得到最终的md-uav接入关系ξ。5.根据权利要求4所述的基于多智能体联邦强化学习的无人机部署优化方法，其特征在于，所述多uav辅助的mec系统目标函数的构建具体如下：将md m∈μ在计算任务本地执行过程中的cpu时钟频率定义为则计算任务a
m
输入数据的本地计算时延量化为：计算任务a
m
在uav n上计算的总时延为:其中i
m
/r
m,n
表示任务输入数据从md m传输到uavn的传输时延；i
m
d
m
/f
m,n
表示计算任务a
m
在uav上的执行时延；表示uav n执行任务a
m
时的cpu时钟频率；计算任务a
m
的执行完成时间为:将最小化平均任务响应时间作为优化目标，将目标函数定义为:p1:::::
其中，约束c1和c2表示uav的部署范围约束；约束c3分别表示任务采用完全卸载策略；约束c4表示每个md只将计算任务卸载到一台uav上执行或本地执行；约束c5表示每台uav接收的任务数量不能超过其最大并行处理数。6.根据权利要求2所述的基于多智能体联邦强化学习的无人机部署优化方法，其特征在于，所述马尔可夫问题模型定义为一个4元组，用<s、a、r、p>表示，其中s是状态空间，a是动作空间，r是奖励函数，p是状态转移函数。根据第3节所述的问题形式化，各智能体所对应的状态空间s、动作空间a、状态转移函数p和奖励函数r定义如下：状态空间：uav n智能体的状态空间用s
n
表示；s
n
被定义成一个3元组义其中包含uav n的计算能力当前uav可视范围内其他无人机的分布情况b
n
以及地面用户分布情况c
n
；动作空间：将uav的动作空间离散化并定义了5个动作，因此uavn的动作空间定义为a
n
＝{0,1,2,3,4}，其中包含将动作方向水平分散到东南西北4个飞行方向的动作和一个垂直悬停动作，悬停动作使uav找到合适位置后保持当前状态；状态转移函数：状态转移函数p(a
n
,s
n
,s'
n
)记录给定当前状态s
n
和应用于s
n
的当前动作a
n
下一个状态s'
n
的概率；具体的转移函数表示为p(a
n
,s
n
,s'
n
)＝pr(s'
n
|s
n
,a
n
)奖励函数：在多无人机部署优化问题中，每个uav都具有相同的目标，即最小化系统平均响应时间，因此将uavn的奖励函数定义为r
n
＝t-t'其中r
n
表示uavn在当前状态s
n
下执行动作a
n
后该智能体所得到的奖励，其中t和t’分别表示部署方案执行动作前后的系统响应时间。7.根据权利要求6所述的基于多智能体联邦强化学习的无人机部署优化方法，其特征在于，所述马尔可夫问题模型在训练过程中，每个智能体在运行时从mec环境中获取状态s，再通过最优策略π
*
选择动作a；mdp问题的最优策略π
*
表示为π
*
(s,a)＝arg maxq(s,a；ω)智能体执行动作a之后会从环境中收到相应的奖励值r以及下一个状态s’；接下来基于dqn算法将每一步得到的(s,a,r,s’)存放到经验存放池中；当达到存储阈值后，对神经网络参数进行更新，神经网络的损失函数如下loss＝(r+γmaxq(s',a'；ω')-q(s,a；ω))2其中r是奖励值，γ是折扣因子，maxq(s',a'；ω')为targetnet的输出，用于计算在下一个状态s’下选择动作a’所获得的最大q值，q(s,a；ω)是evalnet的输出，用于计算当前状态-动作对的q值。8.根据权利要求1所述的基于多智能体联邦强化学习的无人机部署优化方法，其特征在于，所述k-mafrl算法包括两个基本部分：(1)分布式训练，每个uav智能体都使用标准的dqn算法与环境交互来训练其本地模型；在本地训练完成后，从每个智能体中提取网络参数发送到中央聚合单元；(2)联邦聚合，当中央单元接收到各智能体的网络参数时，它将聚合这些网络参数生成
一个全局模型，然后将其模型参数传输回所有的智能体以更新其本地网络。9.根据权利要求8所述的基于多智能体联邦强化学习的无人机部署优化方法，其特征在于，使用fedavg方法执行模型聚合：其中，ω
g
和ω
n
分别表示全局网络参数和第n个uav智能体的本地网络参数。10.根据权利要求8所述的基于多智能体联邦强化学习的无人机部署优化方法，其特征在于，所述步骤s3具体为：随机初始化每个uav智能体的evalnet和targetnet的网络权重，并在每个回合初始化无人机的起始位置；在本地模型训练过程中，各智能体与不同场景下的运行时环境交互，观察当前uav周围的局部状态并通过策略π
*
选择飞行动作a
n
；然后计算执行动作a
n
后获得的奖励r
n
并获取下一状态s'
n
；接下来,(s
n
,a
n
,r
n
,s
n’)被存储到经验池中，其中随机抽取最小批量样本并计算目标q值。这些样本可能来自不同的运行时环境以保证了学习的充分性。；然后，根据均方损失函数执行梯度下降并更新evalnet神经网络权重ω，并在到达设定的c轮迭代后更新targetnet神经网络权重；接下来，中央聚合单元从所有智能体中接收网络参数并对全局网络进行训练，具体来说，上传的参数通过联邦平均算法来拟合全局q网络；最后，中央聚合单元将全局q网络的参数分发给各个智能体，每个智能体以此更新它们的本地网络。

技术总结
本发明涉及一种基于多智能体联邦强化学习（K-MAFRL）的大规模无人机部署优化方法，通过优化多无人机的实时部署位置，实现系统平均任务响应时间的最小化。首先，每台UAV被建模为一个智能体，并且可以根据局部信息独立地进行部署决策。接着，利用K-MAFRL算法对决策模型进行训练，通过与环境交互训练各智能体的本地模型，并将模型参数联邦聚合以生成全局模型，然后将其模型参数传输回所有的智能体以更新其本地网络。最后，通过反馈控制和多无人机协同，逐步找到有效的大规模无人机部署方案。本发明实现高效且自适应的大规模无人机部署。实现高效且自适应的大规模无人机部署。实现高效且自适应的大规模无人机部署。


技术研发人员：陈星 傅德泉 郑龙海
受保护的技术使用者：福州大学
技术研发日：2023.04.04
技术公布日：2023/7/18