一种无人机轨迹、用户关联和资源分配联合优化方法

摘要

本发明公开了一种无人机轨迹、用户关联和资源分配联合优化方法，考虑空空通信网络，多架用户无人机与多架MEC无人机组成的支持移动边缘计算的巡查系统，每架用户无人机配备传感器用于数据采集，MEC无人机配备边缘计算服务器用于辅助用户无人机进行计算任务，用户无人机在规定区域中移动以覆盖任务点，其计算任务可以卸载到边缘计算无人机上进行计算，也可以卸载到簇头无人机上进行计算，为了减少用户无人机的能耗，对簇头无人机与MEC无人机的用户关联、计算资源分配以及MEC无人机的轨迹进行了联合优化。本发明可以在保证计算资源和任务完成时间约束下最小化用户无人机总能耗。

权利要求

1.一种无人机轨迹、用户关联和资源分配联合优化方法，其特征在于，设网络中包括用户无人机集合 和MEC无人机集合 任务集合采用S＝{1,2,...,S}来表示；用户无人机集群已事先分好簇，簇头集 簇成员集所述联合优化方法包括以下步骤：S1，将簇头无人机协同访问区域中任务点建模为多旅行商问题，采用遗传算法对簇头轨迹进行规划；

S2，基于步骤S1的规划结果，构建网络模型、计算任务调度模型和能耗模型；

S3，根据构建的网络模型、计算任务调度模型和能耗模型，提出计算资源和任务完成时间约束下最小化用户无人机能耗的问题；

S4，将所提的最小化用户无人机能耗的问题分解为两个子问题，第一个子问题是用户关联和资源分配优化问题，第二个子问题是MEC无人机轨迹优化问题；

S5，通过引入一个连续松弛变量以及采用连续凸逼近的方法，将第二个子问题由非凸问题转换为凸优化问题；

S6，采用Mosek优化求解器对第一个子问题进行求解，采用CVX优化求解器对第二个子问题进行求解，基于块坐标下降法对两个子问题进行迭代求解。

2.根据权利要求1所述的无人机轨迹、用户关联和资源分配联合优化方法，其特征在于，步骤S2中，所述构建网络模型、计算任务调度模型和能耗模型的过程包括以下步骤：S21，在网络模型中，考虑由N架旋翼无人机和M架固定翼无人机组成的无人机辅助移动边缘计算的巡查系统，区域中有S个地面任务点；

S22，在指定的任务期间，将任务周期划分为T个时隙，时隙长度等分为τ，时隙集合表示为T＝{1,2,...,T}；簇头无人机j的位置表示为 其中j∈H，簇成员无人机k的位置表示为 其中k∈CM； MEC无人机在每个时隙内的飞行方向为 飞行距离其中， 为第i架MEC无人机在每个时隙的最大飞行距离，vi为第i架MEC无人机的飞行速度；在计算任务调度模型中，每架用户无人机l在第t时隙产生任务其中l∈(H∪CM)， 表示完成 所需的CPU周期总数， 表示用户无人机l需要计算的数据量； 为1表示在第t时隙内，簇头无人机j上的任务卸载到MEC无人机i上执行，为0表示在第t时隙内，任务在簇头无人机j上执行；

S23，在能耗模型中，将第t个时隙内任务总能耗表示为：其中， 为簇头到MEC服务器的传输能耗， 为簇成员到簇头的传输能耗， 为簇头本地计算消耗的能耗，kj≥0为有效开关电容； 为簇成员k到簇头无人机j的欧式距离；

表示簇头无人机j到MEC无人机i的欧氏距离；B为信道带宽， 为簇头无人机j的节点发

2 2

射功率， 为无人机k的节点发射功率，α＝g0G0/σ，G0≈2.2846，g0为单位距离信道增益，σ为噪声功率； 是簇头无人机j在t时刻自身提供的本地计算资源，vj是本地计算能耗参数，Hi是MEC无人机i的飞行高度，hj为簇头无人机j的飞行高度， 是簇头无人机j的本地计算时间。

3.根据权利要求2所述的无人机轨迹、用户关联和资源分配联合优化方法，其特征在于，步骤S3中，所述提出计算资源和任务完成时间约束下最小化用户无人机能耗的问题的过程包括以下步骤：

S31，将MEC无人机轨迹变量定义为 MEC无人机与簇头无人机的关联变量定义为 计算资源分配变量定义为S32，将最小化用户无人机集群能耗的问题建模为：其中，U、A、F是优化变量，问题(1‑2)C1表示簇头无人机有且仅将任务卸载到某一架边缘计算无人机上或者在自身执行计算任务，问题(1‑2)C2表示每架MEC无人机i最多只能同时服务 架簇头无人机，问题(1‑2)C3表示簇头无人机j的任务卸载量总和不能超过MEC无人机i所能提供的计算资源量，问题(1‑2)C4表示待卸载的簇头无人机要在MEC无人机的通max

信覆盖范围内，问题(1‑2)C5表示每个任务必须在T 时间内完成； 是第i个MEC无人机在max

第t个时隙为第j个簇头无人机提供的计算资源，fi 是第i架MEC无人机在每个时隙能提供的最大计算资源， 为MEC无人机i的通信覆盖范围， 为第j个簇头无人机的任务总完成时间。

4.根据权利要求3所述的无人机轨迹、用户关联和资源分配联合优化方法，其特征在于，步骤S4中，所述将所提的最小化用户无人机能耗的问题分解为两个子问题的过程包括以下两个步骤：

S41，给定MEC无人机轨迹U，将求解用户关联变量A和资源分配变量F的第一个子问题表示为：

S42，给定用户关联变量A和资源分配变量F，将求解MEC无人机轨迹U的第二个子问题表示为：

s.t.

表示簇头无人机j在t时刻的水平坐标。

5.根据权利要求4所述的无人机轨迹、用户关联和资源分配联合优化方法，其特征在于，步骤S5中，所述通过引入一个连续松弛变量以及采用连续凸逼近的方法，将第二个子问题由非凸问题转换为凸优化问题的过程包括以下步骤：S51，引入一个连续松弛变量 其中，经过SCA处理后问题(1‑4)等价转换为：问题(1‑6)是一个凸优化问题，约束条件为关于 的凸函数，其中，是簇头节点的轨迹簇, 是成员k到簇头无人机j的数据传输速率，和 为中间变量无物理含义。

6.根据权利要求4所述的无人机轨迹、用户关联和资源分配联合优化方法，其特征在于，根据任务卸载对象对问题(1‑3)C5进行变形：如果任务卸载到MEC无人机上计算，问题(1‑3)C5写成：表示簇头无人机j到MEC无人机i的上行数据传输速率；

如果任务在簇头无人机本地计算，问题(1‑3)C5可以写成：问题(1‑3))重新表示为：s.t.

其中， 是簇头节点的轨迹簇, 是成员k到簇头无人机j的数据传输速率。

7.根据权利要求1所述的无人机轨迹、用户关联和资源分配联合优化方法，其特征在于，步骤S6中，所述基于块坐标下降法对两个子问题进行迭代求解的过程包括以下步骤：0

S61，对用户关联变量A、计算资源分配变量F、MEC无人机轨迹变量U进行初始化，得到A、

0 0

F、U，迭代次数初始值r为1；

0 0 0 0

S62，计算最小化用户无人机集群能耗问题的目标函数值V＝Obj(A ,F ,U)；

r‑1 r r

S63，固定U ，得到A ,F；

r r r

S64，固定A ,F，得到U；

r r r r

S65，计算V＝Obj(A ,F ,U)；

S66，改变迭代次数r＝r+1；

r– r‑1 r‑1

S67，重复S63至S66，直到满足|V V |/V <＝ε，ε为精度阈值且为常数。

说明书

一种无人机轨迹、用户关联和资源分配联合优化方法

技术领域

[0001] 本发明涉及无人机自组网在移动边缘计算技术领域，具体而言涉及一种分簇架构下移动边缘计算无人机轨迹、用户关联和计算资源分配联合优化方法。

背景技术

[0002] 在区域覆盖问题的应用中，执行计算密集型任务是无人机面临的挑战之一。近年来，随着通信与人工智能的发展，计算密集型应用正在引发一场移动应用革命，可以显著提
高移动用户的体验质量。然而，这给计算能力弱，电池容量有限的移动设备带来了巨大的挑
战。移动边缘计算被认为是解决这一挑战的有前途的技术之一，受到工业界和学术界越来
越多的研究关注。由于移动边缘计算服务器通常部署在接近终端用户的位置，移动用户的
计算性能得到了显著的提高，且具有成本效益，能节省能量消耗。无人机拥有诸多优势，通
过将无人机集成到移动边缘计算网络中，提出了无人机辅助的移动边缘计算架构。在这些
架构中，无人机可以被认为是有计算任务要执行的用户，或是协助用户卸载计算任务的中
继，或是执行计算任务的移动边缘计算服务器。与传统的地面移动边缘计算网络相比，无人
机辅助的移动边缘计算网络有几个突出的优势，可以在大多数情况下灵活部署，甚至在荒
野、沙漠和复杂的地形不能方便和可靠地建立地面边缘移动计算网络的地方。此外，由于存
在用于卸载计算任务和下载计算结果的短距离视距链路的可能性较大，可以提高计算性
能。同时，可以对无人机的轨迹进行优化，进一步提高用户计算性能。当无人机的成本下降
到足够低时，无人机辅助的移动边缘计算网络将被广泛部署。现有的研究大多考虑了系统
能耗、资源分配、计算速率和时延等性能因素。

发明内容

[0003] 本发明针对现有技术中的不足，提供一种无人机轨迹、用户关联和资源分配联合优化方法，考虑空空通信网络，多架用户无人机与多架MEC无人机组成的支持移动边缘计算
的巡查系统，每架用户无人机配备传感器用于数据采集，MEC无人机配备边缘计算服务器用
于辅助用户无人机进行计算任务，用户无人机在规定区域中移动以覆盖任务点，其计算任
务可以卸载到边缘计算无人机上进行计算，也可以卸载到簇头无人机上进行计算，为了减
少用户无人机的能耗，对簇头无人机与MEC无人机的用户关联、计算资源分配以及MEC无人
机的轨迹进行了联合优化。本发明可以在保证计算资源和任务完成时间约束下最小化用户
无人机总能耗。

[0004] 为实现上述目的，本发明采用以下技术方案：

[0005] 一种无人机轨迹、用户关联和资源分配联合优化方法，设网络中包括用户无人机集合 和MEC无人机集合 任务集合采用S＝{1,2,...,S}来表示；用
户无人机集群已事先分好簇，簇头集 簇成员集

[0006] 所述联合优化方法包括以下步骤：

[0007] S1，将簇头无人机协同访问区域中任务点建模为多旅行商问题，采用遗传算法对簇头轨迹进行规划；

[0008] S2，基于步骤S1的规划结果，构建网络模型、计算任务调度模型和能耗模型；

[0009] S3，根据构建的网络模型、计算任务调度模型和能耗模型，提出计算资源和任务完成时间约束下最小化用户无人机能耗的问题；

[0010] S4，将所提的最小化用户无人机能耗的问题分解为两个子问题，第一个子问题是用户关联和资源分配优化问题，第二个子问题是MEC无人机轨迹优化问题；

[0011] S5，通过引入一个连续松弛变量以及采用连续凸逼近的方法，将第二个子问题由非凸问题转换为凸优化问题；

[0012] S6，采用Mosek优化求解器对第一个子问题进行求解，采用CVX优化求解器对第二个子问题进行求解，基于块坐标下降法对两个子问题进行迭代求解。

[0013] 为优化上述技术方案，采取的具体措施还包括：

[0014] 进一步地，步骤S2中，所述构建网络模型、计算任务调度模型和能耗模型的过程包括以下步骤：

[0015] S21，在网络模型中，考虑由N架旋翼无人机和M架固定翼无人机组成的无人机辅助移动边缘计算的巡查系统，区域中有S个地面任务点；

[0016] S22，在指定的任务期间，将任务周期划分为T个时隙，时隙长度等分为τ，时隙集合表示为T＝{1,2,...,T}；簇头无人机j的位置表示为 其中j∈H，簇成员无人机k的
位置表示为 其中k∈CM。MEC无人机在每个时隙内的飞行方向为 飞行距
离 其中， 为第i架MEC无人机在每个时隙的最大飞行距离，vi为第i架
MEC无人机的飞行速度；在计算任务调度模型中，每架用户无人机l在第t时隙产生任务
其中l∈(H∪CM)， 表示完成 所需的CPU周期总数， 表示用户无人机l需要
计算的数据量； 为1表示在第t时隙内，簇头无人机j上的任务卸载到MEC无人机i上执行，
为0表示在第t时隙内，任务在簇头无人机j上执行；

[0017] S23，在能耗模型中，将第t个时隙内任务总能耗表示为：

[0018]

[0019] 其中， 为簇头到MEC服务器的传输能耗， 为簇成员到簇头的传输能耗，为簇头本地计算消耗的能耗，kj≥0为有效开关电容，vj为常数；簇成员到簇头的欧式距离
簇成员k到簇头无人机j的欧式距离； 表示簇头无人机j到MEC无人机i的欧氏距离；B为
2
信道带宽， 为簇头无人机j的节点发射功率， 为无人机k的节点发射功率，α＝g0G0/σ，
2
G0≈2.2846，g0为单位距离信道增益，σ为噪声功率； 是簇头无人机j在t时刻自身提供的
本地计算资源，vj是本地计算能耗参数，vj是本地计算能耗参数，Hi是MEC无人机i的飞行高
度，hj为簇头无人机j的飞行高度。

[0020] 进一步地，步骤S3中，所述提出计算资源和任务完成时间约束下最小化用户无人机能耗的问题的过程包括以下步骤：

[0021] S31，将MEC无人机轨迹变量定义为 MEC无人机与簇头无人机的关联变量定义为 计算资源分配变量定义为

[0022] S32，将最小化用户无人机集群能耗的问题建模为：

[0023]

[0024] 其中，U、A、F是优化变量，问题(1‑2)C1表示簇头无人机有且仅将任务卸载到某一架边缘计算无人机上或者在自身执行计算任务，问题(1‑2)C2表示每架MEC无人机i最多只
能同时服务 架簇头无人机，问题(1‑2)C3表示簇头无人机j的任务卸载量总和不能超过
MEC无人机i所能提供的计算资源量，问题(1‑2)C4表示待卸载的簇头无人机要在MEC无人机
max
的通信覆盖范围内，问题(1‑2)C5表示每个任务必须在T 时间内完成； 是第i个MEC无人
max
机在第t个时隙为第j个簇头无人机提供的计算资源，fi 是第i架MEC无人机在每个时隙能
提供的最大计算资源， 为MEC无人机i的通信覆盖范围， 为第j个簇头无人机的任务总
完成时间。

[0025] 进一步地，步骤S4中，所述将所提的最小化用户无人机能耗的问题分解为两个子问题的过程包括以下两个步骤：

[0026] S41，给定MEC无人机轨迹U，将求解用户关联变量A和资源分配变量F的第一个子问题表示为：

[0027]

[0028] S42，给定用户关联变量A和资源分配变量F，将求解MEC无人机轨迹U的第二个子问题表示为：

[0029]

[0030] s.t.

[0031]

[0032]

[0033] 进一步地，步骤S5中，所述通过引入一个连续松弛变量以及采用连续凸逼近的方法，将第二个子问题由非凸问题转换为凸优化问题的过程包括以下步骤：

[0034] S51，引入一个连续松弛变量 其中，

[0035]

[0036] 经过SCA处理后问题(1‑4)等价转换为：

[0037]

[0038] 问题(1‑6)是一个凸优化问题，约束条件为关于 的凸函数，其中，是簇头节点的轨迹簇, 是成员k到簇头无人机j的数据传输速率。
进一步地，根据任务卸载对象对问题(1‑3)C5进行变形：

[0039] 如果任务卸载到MEC无人机上计算，问题(1‑3)C5写成：

[0040]

[0041] 如果任务在簇头无人机本地计算，问题(1‑3)C5可以写成：

[0042]

[0043] 问题(1‑3))重新表示为：

[0044]

[0045] s.t.

[0046]

[0047]

[0048]

[0049]

[0050]

[0051] 其中， 是簇头节点的轨迹簇, 是成员k到簇头无人机j的数据传输速率。

[0052] 进一步地，步骤S6中，所述基于块坐标下降法对两个子问题进行迭代求解的过程包括以下步骤：

[0053] S61，对用户关联变量A、计算资源分配变量F、MEC无人机轨迹变量U进行初始化，得0 0 0
到A、F、U，迭代次数初始值r为1；

[0054] S62，计算问题P1的目标函数值V0＝Obj(A0,F0,U0)；

[0055] S63，固定Ur‑1，得到Ar,Fr；

[0056] S64，固定Ar,Fr，得到Ur；

[0057] S65，计算Vr＝Obj(Ar,Fr,Ur)；

[0058] S66，改变迭代次数r＝r+1；

[0059] S67，重复S63至S66，直到满足|Vr–Vr‑1|/Vr‑1<＝ε。

[0060] 本发明的有益效果是：

[0061] 本发明在考虑计算资源和任务完成时间约束下以最小化用户无人机总能耗为目标，通过引入一个连续松弛变量以及采用连续凸逼近的方法，将非凸问题转变为凸优化问
题。为了最小化用户无人机总能耗，开发了一种基于块坐标下降方法的迭代优化算法同时
优化MEC无人机轨迹、MEC无人机与簇头无人机的关联以及计算资源分配，本发明可以在保
证计算资源和任务完成时间约束下最小化用户无人机总能耗。

附图说明

[0062] 图1为本发明所涉及的无人机自组网分簇架构下支持移动边缘计算应用的系统示意图。

[0063] 图2为本发明簇头无人机和MEC无人机轨迹规划实验仿真结果图。

[0064] 图3为本发明用户无人机总能耗与不同用户无人机所需CPU周期数关系实验仿真结果图。

[0065] 图4为本发明用户无人机总能耗与不同MEC无人机允许接入的最大簇头无人机数目关系实验仿真结果图。

[0066] 图5为本发明用户无人机总能耗与不同MEC无人机数目关系实验仿真结果图。

[0067] 图6为本发明的无人机轨迹、用户关联和资源分配联合优化方法流程图。

具体实施方式

[0068] 现在结合附图对本发明作进一步详细的说明。

[0069] 需要注意的是，发明中所引用的如“上”、“下”、“左”、“右”、“前”、“后”等的用语，亦仅为便于叙述的明了，而非用以限定本发明可实施的范围，其相对关系的改变或调整，在无
实质变更技术内容下，当亦视为本发明可实施的范畴。

[0070] 结合图6，本发明提及一种无人机轨迹、用户关联和资源分配联合优化方法，设网络中包括用户无人机集合N＝＝{1,2,...,N}和MEC无人机集合M＝＝{1,2,...,M}，任务集
合采用S＝{1,2,...,S}来表示；用户无人机集群已事先分好簇，簇头集 簇成员集

[0071] 所述联合优化方法包括以下步骤：

[0072] S1，将簇头无人机协同访问区域中任务点建模为多旅行商问题，采用遗传算法对簇头轨迹进行规划。

[0073] S2，基于步骤S1的规划结果，构建网络模型、计算任务调度模型和能耗模型。

[0074] S3，根据构建的网络模型、计算任务调度模型和能耗模型，提出计算资源和任务完成时间约束下最小化用户无人机能耗的问题。

[0075] S4，将所提的最小化用户无人机能耗的问题分解为两个子问题，第一个子问题是用户关联和资源分配优化问题，第二个子问题是MEC无人机轨迹优化问题。

[0076] S5，通过引入一个连续松弛变量以及采用连续凸逼近的方法，将第二个子问题由非凸问题转换为凸优化问题。

[0077] S6，采用Mosek优化求解器对第一个子问题进行求解，采用CVX优化求解器对第二个子问题进行求解，基于块坐标下降法对两个子问题进行迭代求解。

[0078] 本发明提供的分簇架构下移动边缘计算无人机轨迹、用户关联和计算资源分配联合优化方法中，N架用户无人机对某区域进行侦查，有M架移动边缘计算无人机(MEC无人机)
为其提供计算服务，地面任务有S个，用户无人机集群已事先分好簇，簇头集 簇成
员集

[0079] 在分簇架构下移动边缘计算无人机轨迹优化中，存在通信性能、时延、用户资源分配等问题，具体有如下挑战：1)如何通过选择适当的用户关联，即簇头无人机是否应该卸载
任务，如果应该，在多个簇头无人机的情况下，将哪些簇头无人机卸载到MEC)来最小化所有
簇头无人机的长期能耗；2)通过考虑有限数量的机载资源，MEC应该分配多少计算资源给每
个簇头无人机卸载的任务；3)如何实时控制每个无人机的飞行轨迹，即飞行方向和距离。

[0080] 具体地，所述分簇架构下移动边缘计算无人机轨迹、用户关联和计算资源分配联合优化方法包括以下步骤：

[0081] 在步骤2中，构建网络模型、计算任务调度模型和能耗模型。在网络模型中，考虑由N架旋翼无人机和M架固定翼无人机组成的无人机辅助移动边缘计算的巡查系统，区域中有
S个地面任务点，用户无人机集合N＝＝{1,2,...,N}，MEC无人机集合M＝＝{1,2,...,M}，任
务集合S＝{1,2,...,S}。用户无人机集群已事先分好簇，簇头集 簇成员集
在指定的任务期间，将任务周期划分为T个时隙，时隙长度等分为τ，时隙集合表
示为T＝{1,2,...,T}。簇头无人机j的位置表示为 其中j∈H，簇成员无人机k的位
置表示为 其中k∈CM。MEC无人机在每个时隙内的飞行方向为 飞行距
离 其中， 为第i架MEC无人机在每个时隙的最大飞行距离，vi为第i架
MEC无人机的飞行速度。假设MEC无人机在初始时的位置为 那么，在第t时刻的位
置表示为 其中t∈T：

[0082]

[0083]

[0084] 簇头无人机与MEC无人机的关联变量 其中i∈M,j∈H,t∈T。 为1表示在第t时隙内，簇头无人机j上的任务卸载到MEC无人机i上执行， 为0表示在第t时隙内，任务
在簇头无人机j上执行。在计算任务调度模型中，每架用户无人机在第t时隙产生任务 其
t
中t∈T。具体来说，可以描述为 其中l∈(H∪CM)，Fl表示完成 所需的CPU周
期总数， 表示用户无人机需要计算的数据量。计算任务既可以卸载到簇头无人机上执行，
也可以卸载到MEC无人机上执行。假设每架MEC无人机都配备了固定波束宽度波束θ的定向
max
天线，每架MEC无人机可提供的最大计算资源量为fi 。如果第j个簇头无人机决定在第t个
时隙将任务卸载给第i个MEC无人机，则簇头无人机应该在MEC无人机i的通信范围内，那么
有：

[0085]

[0086] 其中，MEC无人机i的通信覆盖范围为 簇头j到MEC无人机i的欧氏距离 表示为：

[0087]

[0088] 簇头无人机j到MEC无人机i的上行数据传输速率表示为：

[0089]

[0090] 簇成员到簇头的欧式距离 表示为：

[0091]

[0092] 簇成员k到簇头无人机j的数据传输速率表示为：

[0093]

[0094] 其中，B为信道带宽，PTr为节点发射功率，α＝g0G0/σ2，G0≈2.2846，g0为单位距离信2
道增益，σ为噪声功率。考虑每架无人机采用正交频分复用(OFDM)信道，它们之间没有干
扰。在每个时间段内，假设每架MEC无人机i最多只能同时服务 架用户无人机，那么有：

[0095]

[0096] 在每个时间段内，由于每架MEC无人机i能够提供的计算资源是有限的，有：

[0097]

[0098] 其中， 是第i个MEC无人机在第t个时隙为第j个簇头无人机提供的计算资源，max
fi 是第i架MEC无人机在每个时隙能提供的最大计算资源。

[0099] 假设计算结果返回时间可以忽略，任务完成时间分为传输时间和计算时间。传输时间分为两个阶段，首先由簇成员k传输到簇头无人机j，再由簇头无人机j将整个簇的任务
传输到MEC无人机i。计算时间分为本地簇头计算时间和MEC无人机计算时间。因此，第j个簇
头无人机的任务总完成时间可以表示为：

[0100]

[0101] 其中， 表示在t时隙，簇成员k将其计算任务卸载给簇头无人机j的传输时间，表示为：

[0102]

[0103] 表示在t时隙，簇头无人机j将聚合的整个簇的任务卸载给MEC无人机i的传输时间，表示为：

[0104]

[0105] 表示在t时隙，任务卸载到MEC无人机上执行所需的计算时间，表示为：

[0106]

[0107] 表示在t时隙，任务在簇头无人机上执行所需的计算时间，表示为：

[0108]

[0109] 假设每个任务需要在Tmax时间内完成，即有：

[0110]

[0111] 在能耗模型中，第t个时隙内任务总能耗表示为：

[0112]

[0113] 其中， 为簇头到MEC服务器的传输能耗， 为簇成员到簇头的传输能耗，为簇头本地计算消耗的能耗，kj≥0为有效开关电容，vj为常数。

[0114] 在步骤3中根据构建的模型，提出计算资源和任务完成时间约束下最小化用户无人机能耗的问题。MEC无人机轨迹变量定义为 MEC无人机与簇头无
人机的关联变量定义为 计算资源分配变量定义为
最小化用户无人机集群能耗的问题可以建模为：

[0115]

[0116] 其中，U、A、F是优化变量，问题(1‑2)C1表示簇头无人机有且仅将任务卸载到某一架边缘计算无人机上或者在自身执行计算任务，问题(1‑2)C2表示每架MEC无人机i最多只
能同时服务 架簇头无人机，问题(1‑2)C3表示簇头无人机j的任务卸载量总和不能超过
MEC无人机i所能提供的计算资源量，问题(4‑17)C4表示待卸载的簇头无人机要在MEC无人
max
机的通信覆盖范围内，问题(1‑2)C5表示每个任务必须在T 时间内完成。

[0117] 在步骤4中将所提问题分解为两个子问题，第一个子问题是用户关联和资源分配优化问题，第二个子问题是MEC无人机轨迹优化问题。子问题一，给定MEC无人机轨迹U，求解
用户关联变量A和资源分配变量F的子问题(P1)可以表示为：

[0118]

[0119] 其中，可以根据任务卸载对象对问题(1‑3)C5进行变形，如果任务卸载到MEC无人机上计算，那么问题(1‑3)C5可以写成：

[0120]

[0121] 如果任务在簇头无人机本地计算，那么问题(4‑18)C5可以写成：

[0122]

[0123] 那么问题(4‑18)可以重新表示为：

[0124]

[0125] 其中， 是簇头节点的轨迹。

[0126] 子问题二，给定用户关联变量A和资源分配变量F，求解MEC无人机轨迹U的问题(1‑4)可以表示为：

[0127]

[0128] 在步骤5中，通过引入一个连续松弛变量以及采用连续凸逼近的方法，将第二个子问题由非凸问题转换为凸优化问题。问题(1‑4)是一个关于MEC无人机轨迹变量U的连续函
数，但是这个子问题的目标函数和约束条件都是非凸的。为了求解该问题，引入一个连续松
弛变量 其中，

[0129]

[0130] 那么问题(1‑4)可以转换为问题(1‑28)，

[0131]

[0132] 可以看出，问题(1‑28)的目标函数是凸的，约束条件为关于 的凸函数，因此，约束条件关于变量U是非凸约束，采用连续凸逼近来求解该问题。给定上一次迭代的局
部值 问题(1‑28)中C1和C2的严格下界为：

[0133]

[0134] 其中，

[0135]

[0136]

[0137] 经过SCA处理后问题(1‑28)等价转换为：

[0138]

[0139] 问题(1‑32)是一个凸优化问题。

[0140] 在第6步骤中，采用Mosek优化求解器对子问题一进行求解，采用CVX优化求解器对子问题二进行求解，基于块坐标下降法对两个子问题进行迭代求解。通过问题(1‑3)可以看
出，目标函数和约束条件在A和F上都是线性的，并且问题(1‑3)是一个经典的多维多选择背
包问题(Multiple‑Choice Multi‑Dimensional 0‑1Knapsack Problem,MMKP)问题，虽然
MMKP通常是NP‑hard问题，但是该问题可以使用标准优化器MOSEK[89]，采用分支限定法得
到最优解。问题(1‑4)是一个凸优化问题，采用CVX进行有效求解。基于块坐标下降法对两个
子问题进行迭代求解的步骤如下：

[0141] S61，对用户关联变量A、计算资源分配变量F、MEC无人机轨迹变量U进行初始化，得0 0 0
到A、F、U，迭代次数初始值r为1。

[0142] S62，计算问题P1的目标函数值V0＝Obj(A0,F0,U0)。

[0143] S63，固定Ur‑1，得到Ar,Fr。

[0144] S64，固定Ar,Fr，得到Ur。

[0145] S65，计算Vr＝Obj(Ar,Fr,Ur)。

[0146] S66，改变迭代次数r＝r+1。

[0147] S67，重复S63至S66，直到满足|Vr–Vr‑1|/Vr‑1<＝ε。

[0148] 本发明的分簇架构下移动边缘计算无人机轨迹、用户关联和计算资源分配联合优化方法，图1是本发明提供的分簇架构下支持移动边缘计算应用的无人机自组网的场景。

[0149] 图2是簇头无人机和MEC无人机轨迹图。每架簇头无人机从不同的初始位置出发，最终回到起飞位置，每种闭合线均代表一个簇头无人机的的飞行轨迹。4架簇头无人机以最
短距离总和协同完成覆盖区域任务点的访问。规定两架MEC无人机的起始位置坐标分别为
(200,0)、(200,200)，终点坐标分别为(0,200)、(0,0)，虚线为两架MEC无人机优化轨迹。

[0150] 图3显示了用户无人机总能耗与用户无人机工作负载在所需CPU周期数的关系。随着用户无人机所需的CPU数的增加，由于每架MEC无人机的计算能力相对有限，可能会导致
更多的用户无人机不得不在本地簇头执行任务，从而导致所有用户无人机的总体能耗增
加。而AFU算法的性能优于其他两种基准，且FixU由于Local。这是因为Local方案的计算任
务全在簇头本地执行，导致用户无人机总能耗很高，而FixU方案中，MEC无人机固定对角线
飞行，能为用户无人机提供计算服务，由于没有对MEC无人机轨迹进行优化，不能长时间为
更多用户无人机提供计算服务，因此能耗性能比AFU差。更具体地说，当每个用户无人机的
工作负载从4×108个CPU周期变化到109个CPU周期时，与Local、FixU相比，AFU平均分别降
低了用户无人机总体能耗的294.63％和43.77％。

[0151] 图4显示了用户无人机总能耗与MEC无人机允许接入的最大簇头无人机数目的关系。从图中可以看出，随着MEC无人机允许接入的最大簇头无人机数量的变化，除了全在本
地簇头执行计算任务的算法外，其他算法中用户无人机的总能耗都有所降低，这是因为MEC
无人机通信接入能力越强，簇头无人机可以将更多的任务卸载给MEC无人机执行。可以看出
当允许接入的最大簇头无人机数量大于1时，AFU和FixU算法中的用户无人机总能耗有大幅
下降。AFU与Local、FixU相比，AFU平均分别降低了用户无人机总体能耗的409.21％和
128.14％。

[0152] 图5显示了用户无人机总能耗与MEC无人机数目的关系。从图中可以看出，除了全部

[0153] 任务都在本地簇头上执行的算法外，AFU和FixU两个算法中用户无人机的总能耗随着MEC

[0154] 无人机数量的增多都下降了，且AFU的能耗低于FixU的能耗，当MEC无人机数量增大到4时，AFU和FixU这两种方案的用户无人机总能耗相近。这是因为随着MEC无人机数量的
增多，簇头无人机可以有更多机会在MEC无人机的通信覆盖范围内，也就是说簇头无人机能
将更多计算服务卸载到MEC无人机上，从而降低用户无人机的总能耗。同时，MEC无人机数量
的增大到一定的值，即使没有优化MEC无人机的路径，多架MEC无人机也能够覆盖大部分区
域，为更多簇头无人机提供计算服务，因此，当MEC无人机数量增大到一定值后，AFU和FixU
在能耗性能上趋近。当MEC无人机数量从1增大到4时，AFU与Local、FixU相比，AFU平均分别
降低了用户无人机总体能耗的496.96％和80.66％。

[0155] 以上仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的
普通技术人员来说，在不脱离本发明原理前提下的若干改进和润饰，应视为本发明的保护
范围。