CN116634452A - 无人机辅助边缘计算网络的部署与卸载方法 - Google Patents

Abstract

本发明公开了一种无人机辅助边缘计算网络的部署与卸载方法，主要解决现有配备有边缘计算服务器的无人机中没有根据用户数目部署无人机个数而造成的成本大的问题，其实现方案为：设置用户和无人机辅助网络相关参数；据网络特性设置约束条件；根据初始化网络参数和约束条件建立最小化能耗问题P；利用上下层迭代法确定问题P中的无人机个数N、关联矩阵C、卸载矩阵U、计算资源矩阵F及无人机位置矩阵Z；根据计算得到的这五个参数进行网络部署和计算任务卸载。本发明能在满足计算任务的可容忍时延和无人机计算资源上限的约束条件下，根据用户的位置及计算任务信息优化卸载决策和部署方案，使用最少数量的无人机完成任务，可在降低系统总能耗的同时最小化网络成本。

Description

无人机辅助边缘计算网络的部署与卸载方法

技术领域

本发明属于通信技术领域，特别涉及一种无人机辅助边缘计算网络部署与卸载方法，可用于无人机能耗受限条件下的应急通信和边缘计算服务。

背景技术

随着通信技术的发展，互联网已经从点对点网络发展到万维网，从移动互联网发展到物联网。随即对数据服务、计算资源以及网络基础设置的需求大幅提升，以满足大量互联设备的需求。为了给用户提供更好的沉浸式服务体验，移动边缘计算MEC在无线接入网的边缘部署云资源。无人机UAV信道质量好、机动性强、部署灵活，将其作为空中基站快速部署在指定位置，是地面通信网络的有效补充和扩展。这两者结合起来不仅能够更进一步地扩大MEC的服务范围，还可以提升服务质量，为网络瘫痪、基站受损、不受覆盖的山区及时提供低时延，高可靠性的通信和计算服务。常规的边缘计算系统通常在地面的固定基础建设上部署边缘服务器，但为了更好地支持无人机辅助的边缘计算网络，必须更加灵活的部署无人机。但由于无人机携带的电量有限，无法支撑长期的悬停和通信计算服务，并且购买一架无人机的经济成本不可忽视，使用的无人机数目越多，总成本也就越大。因此在无人机辅助的边缘计算系统中需要通过合理的部署和任务调度方案来减少部署的UAV个数，节约成本，减小能耗。

为了保障目标区域内用户的服务质量，避免出现通信中断的问题，需要基于用户的位置和计算任务合理部署无人机位置确定计算卸载方案。Zhaohui Yang在2019年于IEEETransactions on Wireless Communications中发表了Energy Efficient ResourceAllocation in UAV-Enabled Mobile Edge Computing Networks[J]，考虑多无人机辅助移动边缘计算网络，通过联合优化用户关联、功率控制、计算资源分配和位置规划，从而最大限度地降低总功耗。为了求解非凸问题，其提出了一种复杂度低的算法，通过迭代来求解三个子问题。该方案中，由于仅考虑由固定个数无人机来辅助边缘计算网络为用户提供计算服务，没有考虑无人机携带的边缘计算服务器计算能力有限，故无法满足大量用户需求的问题，同时由于没有根据具体的用户数目合理安排部署无人机UAV的个数，因而成本较大。

发明内容

本发明的目的在于针对上述现有技术的不足，提出一种无人机辅助边缘计算网络的部署与卸载方法，以在满足计算任务可容忍时延约束的条件下，满足大量用户的服务需求，减少网络成本，降低系统能耗。

本发明的技术方案是：根据用户的位置以及计算任务信息，优化部署无人机的个数、位置、用户与UAV的关联、用户计算任务的卸载方案及UAV分配给卸载任务的计算资源。其实现步骤包括如下：

(1)设置用户相关参数和无人机辅助网络相关参数：

在半径为L的圆形故障区域Y内随机分布了M个地面用户，其集合为O＝{1,…,m,…,M}，用户m的位置为(x_m,y_m,0)；用户m需要完成计算任务A_m＝(F_m,D_m,T)，其中F_m表示计算所需的CPU转数；D_m表示计算数据量；T为时延约束；

设无人机集合为G＝{1,…,n,…,N}，N为待确定的无人机总数，第n个无人机的坐标为(x_n,y_n,H_n)，俯角固定为θ，最大覆盖半径R为H_ntanθ，设U_n为无人机n能够接入用户数的最大值，f_n,max为无人机n的计算资源上限，发射功率为悬停功率为P^H，均不可调；设邻居基站的坐标为(x₀,y₀,H)；

(2)根据上述初始化参数建立最小化能耗问题P：

s.t.C1:

C2:

C3:u_mn≤c_mn,m∈O,n∈G，

C4:

C5:c_mnd_mn≤R,m∈O,n∈G，

C6:t_m≤T,m∈O，

C7:(x_n,y_n)∈Y,

其中，C为无人机与用户的关联矩阵，c_mn为C中的第m行第n列元素；

U为卸载矩阵，u_mn为U中的第m行第n列元素，Z为无人机的位置矩阵；

F为无人机计算资源分配矩阵，f_mn为F中的第m行第n列元素，

为用户m将计算任务发送给无人机n的通信能耗；/>为无人机n完成用户m任务的计算能耗，/>为无人机n将用户m的计算任务中转给邻居基站的通信能耗，/>为无人机n的悬停能耗；α表示与用户能耗相比无人机能耗的权重系数，t_m为用户m计算任务完成的总时间，d_mn是用户m与无人机n之间的水平距离；

(3)确定无人机的初始个数N⁰及无人机的初始位置Z⁰；根据M⁰，Z⁰确定初始关联矩阵C⁰、关联矩阵是否为可行解fsb_C、初始卸载矩阵U⁰、卸载矩阵是否是可行解为fsb_U、初始资源分配矩阵F⁰、最小能耗E_min和完成的最多任务数num_max；

(4)使用上下层迭代法求解问题P中的N、Z、C、U、F：

(4a)设置求解次数为NoS，最多迭代求解次数为NoS_max，停止删减无人机个数为flag，当前解的不可行次数为not，初始化NoS＝0，flag＝0，not＝0，NoS_max＝1000；

(4b)判断当前解是否是可行解以及无人机个数是否可以继续减少：

如果fsb_C＝fsb_U＝1且flag＝0，则当前解为可行解且无人机个数可以继续减少，执行(4c)；否则，跳转到步骤(4f)；

(4c)对当前可行解N、Z、C、U、F进行保存，并去掉一个冗余的无人机得到当前的无人机个数N和无人机部署位置Z；

(4d)根据当前的N和Z，更新上述参数C、fsb_C、U、fsb_U、F、E_min、num_max，并令NoS＝NoS+1，执行步骤(4g)；

(4f)利用改进的差分进化算法确定当前无人机个数N下的参数Z、fsb_C、U、fsb_U、F、E_min、num_max；

(4g)判断NoS＜NoS_max是否成立，如果成立，则返回步骤(4b)继续迭代求解；否则迭代终止，得到最终解无人机数目N'、无人机位置Z'、关联矩阵C'、卸载矩阵U'、计算资源分配矩阵F'；

(5)选择N'个无人机按照部署矩阵Z'进行部署；

(6)根据关联矩阵C'确定用户与无人机的关联性：若C'中的元素c_mn＝1，则将用户m与无人机n关联，并将用户m的计算任务传输至无人机n处；否则，用户m与无人机n不关联；

(7)根据卸载决策矩阵U'中的元素值u_mn，确定用户计算任务的执行对象：

若u_mn＝1，则由无人机n按照资源分配矩阵F'中的元素f_mn给用户分配计算资源，完成用户m的计算任务；

否则，由关联无人机n将用户m的计算任务中转给邻居基站，由邻居基站完成计算任务。

本发明与现有技术相比，具有如下优点：

第一，本发明由于将计算能力更强的邻居基站与无人机联合为服务受损地区的用户提供通信和计算服务，提高了网络的稳定性，满足大量用户的服务需求。

第二，本发明基于上下层迭代法的联合优化方法，由于将问题分成两层求解，即上层优化无人机部署问题，其包括无人机的个数以及每个无人机的位置；下层针对上层的部署方案优化任务调度，其包括用户与无人机的关联、计算任务的卸载方案及无人机分配给卸载任务的计算资源，得到网络的部署和卸载方案，因而可降低系统能耗，解决用户服务受阻的问题。

第三，本发明由于根据用户的位置及计算任务量求解能够完成所有任务所需的最小无人机个数，故可在降低能耗的同时，减小部署过多无人机带来的经济成本，最小化网络成本。

仿真结果证明，本发明在满足用户任务时延约束的前提下，降低了系统能耗，减少了网络成本，能为用户提供稳定的服务。

附图说明

图1为本发明的实现流程图；

图2为本发明的系统场景图；

图3为本发明和对比方法在不同用户数时完成所有任务消耗的系统总能耗和部署的无人机个数对比图；

图4为本发明和对比方法在用户可容忍时延为1s时，在不同时间点完成任务的情况对比图。

具体实施方式

以下结合附图对本发明的实施例和效果作进一步详细描述。

参照图2，本实例使用的场景为两个相邻蜂窝网，其中一个蜂窝网内基站出现故障无法为用户提供服务，本实例将另一个配备有移动边缘计算服务器的无人机作为临时应急基站，由无人机和邻居基站联合为故障区域用户服务。用户的计算任务转发给关联无人机，无人机可以自己计算，也可以将任务中继给邻居基站，以保证网络的稳定性。根据控制中心保存的各个基站服务区域内地面用户的位置及计算任务等信息，确定无人机的个数、部署位置及计算任务的执行方案，整个过程在控制中心完成，并在得到实施方案后由控制中心驱动无人机执行任务。

参照图1，本实例的实现步骤包括如下：

步骤1，初始化参数。

针对图2的使用场景，初始化如下网络参数：

(1.1)用户相关参数设置：

在半径为L的圆形故障区域Y内随机分布了M个地面用户，其集合为O＝{1,…,m,,M}，用户m的位置为(x_m,y_m,0)；用户m需要完成计算任务A_m＝(F_m,D_m,T)，其中F_m表示计算所需的CPU转数；D_m表示计算数据量；T为时延约束；

(1.2)无人机辅助网络相关参数设置：

设N个配备有边缘计算服务器的无人机以及邻居基站一起为故障区域用户提供计算服务，无人机集合为G＝{1,…,n,,N}，N为待确定的无人机总数，第n个无人机的坐标为(x_n,y_n,H_n)，俯角固定为θ，最大覆盖半径R为H_ntanθ，设U_n为无人机n能够接入用户数的最大值，f_n,max为无人机n的计算资源上限，发射功率为悬停功率为P^H，均不可调；

设邻居基站的坐标为(x₀,y₀,H)。

步骤2，根据上述初始化参数建立最小化能耗问题P。

(2.1)根据用户m与无人机n的位置坐标，得到两者之间的水平距离d_mn和无人机n与邻居基站之间的水平距离d_nB：

(2.2)根据(2.1)中的水平距离d_mn和无人机n与邻居基站之间的水平距离d_nB，建立基于自由空间路径损耗的信道模型，即用户m到无人机n的信道功率增益h_mn及无人机n到邻居基站之间的信道功率增益h_nB：

其中β^G2A和β^A2A分别表示参考距离为一米时的空地信道增益和空空信道增益；

(2.3)根据(2.2)中用户m到无人机n的信道功率增益h_mn及无人机n到邻居基站之间的信道功率增益h_nB，利用香农定理得到用户m到无人机n的传输速率r_mn及无人机n到邻居基站之间的传输速率r_nB：

其中，B₁表示用户与无人机之间的传输带宽，B₂表示无人机与邻居基站之间的传输带宽，P_m为用户m设备的发射功率，为无人机n的发射功率，N₀为噪声功率谱密度；

(2.4)计算用户m将计算任务发送给无人机n的通信传输时间及通信能耗/>

(2.5)计算无人机m将用户n的计算任务中转给邻居基站的通信传输时间及通信能耗/>

(2.6)计算无人机n完成用户m的任务所需处理时间及计算能耗/>

其中，f_mn表示无人机n分给用户m的CPU频率，ε表示无人机机载服务器芯片的有效电容系数；

(2.7)计算无人机n的悬停能耗

(2.8)设置如下相关矩阵和变量：

设C＝[c_mn]_M×N为无人机与用户的关联矩阵，c_mn＝1表示用户m与无人机n关联，c_mn＝0表示不关联；

设U＝[u_mn]_M×N为用户的计算卸载决策矩阵，当c_mn＝1且u_mn＝1表示无人机n为用户m提供服务，c_mn＝1且u_mn＝0表示关联无人机n将用户m的计算任务中转给邻居基站，由邻居基站完成计算任务；

设F＝[f_mn]_M×N为计算资源分配矩阵；

设Z＝[(x_n,y_n)]_N×1为无人机的位置矩阵；

设用户的计算任务完成总时间为：

由(2.4)(2.5)(2.6)(2.7)的结果得到系统总能耗为：

(2.9)设置约束条件：

根据一个用户只能与一个无人机关联且所有用户需要被覆盖的特性，设第一个约束条件：

根据每个无人机接入的用户数不能超过最大接入用户数的限制，设置第二个约束条件

根据无人机只能为其关联的用户提供服务的特性，设置第三个约束条件u_mn≤c_mn；

根据无人机m分配给覆盖范围内用户的计算资源之和不超过其计算资源最大值的限制，设置第四个约束

根据无人机关联的用户需在其覆盖范围内的情况，设置第五个约束c_mnd_mn≤R；

根据用户n的任务完成时间不超过最大容忍时延的限制，设置第六个约束t_m≤T；

根据无人机的水平位置需在故障基站范围内的限制，得到第七个约束条件(x_n,y_n)∈Y；

(2.10)结合上述约束条件和参数，将能耗最小化问题P表示如下：

s.t.C1:

C2:

C3:u_mn≤c_mn,m∈O,n∈G，

C4:

C5:c_mnd_mn≤R,m∈O,n∈G，

C6:t_m≤T,m∈O，

C7:(x_n,y_n)∈Y,

其中，α表示与用户能耗相比无人机能耗的权重系数。

本实例中取但不限于L＝300米，F_m＝100～200cycles/bit，D_m＝[10,800]KB，H_n＝100m，θ＝π/4，R＝H_ntanθ＝100m，β^G2A＝β^A2A＝1.42×10^-4，B₁＝B₂＝1MHz，P^H＝100W，N₀＝10^-20W/Hz，U_n＝20，f_n,max＝2GHz，ε＝10^-28，(x₀,y₀,H₀)＝(600,300,100)。

步骤3，确定无人机的初始个数N⁰及无人机的初始位置Z⁰；

(3.1)初始化无人机的个数为一个较大值N⁰＝2×(M/U_n)；

(3.2)通过Kmeans++算法确定无人机的初始位置Z⁰，设置循环次数iter＝0：

(3.2.1)借助Kmeans++算法，将无人机的个数N⁰作为类数，根据用户的位置进行聚类，将聚类中心作为无人机的部署位置；

(3.2.2)根据(3.2.1)得到的无人机部署位置确定每个用户m执行任务的候选集V_m：

(3.2.2.1)计算用户m到无人机n之间的距离d_mn；

(3.2.2.2)判断d_mn＜R是否成立：若成立，则表示无人机到用户之间的距离小于无人机的覆盖半径，则将无人机n列入用户m的候选集V_m中；

(3.2.3)确定无人机的初始位置Z⁰：

(3.2.3.1)判断所有用户的候选集是否为空：若不为空，则将当前的无人机位置作为初始位置Z⁰；否则，令iter＝iter+1，执行步骤(3.2.3.2)；

(3.2.3.2)判断iter＞1000是否成立：

若成立，则表示经过多次聚类始终没有找到满足约束的无人机初始位置，将最后一次迭代得到的聚类中心作为无人机的初始位置；

否则，返回至步骤(3.2.1)重新求解无人机的初始位置。

步骤4，根据N⁰，Z⁰确定初始关联矩阵C⁰、关联矩阵是否为可行解fsb_C。

(4.1)采用贪心的关联策略得到关联矩阵C⁰及该关联是否是可行解fsb_C：

(4.1.1)计算用户m到无人机n之间的距离d_mn，将d_mn＜R的无人机n列入用户m的候选集V_m中；

(4.1.2)根据以下准则将所有用户分为两类：

第一类：候选集V_m中只有一个无人机备选，即该用户只在一个无人机的覆盖半径内；

第二类：候选集V_m中有多个无人机备选，表示该用户在多个无人机的覆盖范围内；

第一类任务的关联优先级高于第二类任务；

(4.1.3)按照如下关联准则进行关联，得到关联矩阵C⁰以及该解是否是可行解fsb_C：

(4.1.3.1)判断第一类用户候选集中的无人机是否接满：若没有接满，令对应的c_mn＝1，表示关联；否则，c_mn＝0，表示不关联；

(4.1.3.2)根据第二类用户候选集V_m中的元素数，对其进行升序排序，优先给候选集小的用户确定关联情况，对于用户m，根据其候选集V_m中每个候选无人机到用户m的距离，按照升序排序，如果距离相等则按照无人机接入用户数升序排序，将用户优先关联到距离近且接入用户数少的无人机；

(4.1.3.3)按照上述策略，判断是否存在候选集为空或候选集中可关联的无人机均接满的情况：

若是，则关联失败，fsb_C＝0；

否则，关联成功，fsb_C＝1。

步骤5，根据N⁰、Z⁰、C⁰确定初始卸载矩阵U⁰、卸载矩阵是否是可行解为fsb_U、初始资源分配矩阵F⁰、最小能耗E_min和完成的最多任务数num_max。

(5.1)由下式推导出每个用户在不同无人机处计算所需的最小资源f_mn,min：

(5.2)求解初始化卸载矩阵U⁰：

(5.2.1)根据N⁰，Z⁰，C⁰和f_mn,min将问题P化简为关于卸载矩阵U⁰的0-1规划问题P1：

P1:

s.t.P1:C3,C4,C6

(5.2.2)利用分枝定界法对P1进行求解，得到U⁰以及表示该卸载矩阵是否是可行解的fsb_U，即用仿真软件中关于分支定界法的库函数进行求解；

(5.3)根据U⁰中的元素u_mn计算F⁰中的元素：f_mn＝u_mnf_mn,min，最终得到计算资源分配矩阵F⁰＝[f_mn]_M×N；

(5.4)判断初始解是否是可行解，即fsb_C＝fsb_U＝1是否成立：

若是可行解，则根据N⁰、Z⁰、C⁰、U⁰、F⁰计算当前解对应的系统总能耗E⁰，初始化系统最小能耗E_min＝E⁰，完成最多任务数num_max＝M；

否则，计算时延约束内完成任务的用户个数num⁰，初始化系统最小能耗E_min为一个极大的值，完成最多任务数num_max＝num⁰。

步骤6，使用上下层迭代法求解问题P中的N，Z，C，U，F。

(6.1)设置求解次数为NoS，最多迭代求解次数为NoS_max，停止删减无人机个数为flag，当前解的不可行次数为not，初始化NoS＝0，flag＝0，not＝0，NoS_max＝1000，初始化N、Z、C、U、F分别等于N⁰、Z⁰、C⁰、U⁰、F⁰；

(6.2)判断当前解是否是可行解以及无人机个数是否可以继续减少：

如果fsb_C＝fsb_U＝1且flag＝0，则当前解为可行解且无人机个数可以继续减少，执行(6.3)；否则，跳转到步骤(6.5)；

(6.3)对当前可行解N、Z、C、U、F进行保存，并去掉一个冗余的无人机得到当前的无人机个数N和无人机部署位置Z：

(6.3.1)设置N_temp，Z_temp，C_temp，U_temp，F_temp这五个临时值并赋值为0，用于保存可行的N，Z，C，U，F；

(6.3.2)令N_temp，Z_temp，C_temp，U_temp，F_temp分别等于N，Z，C，U，F；

(6.3.3)计算Z中各个无人机之间的欧式距离d_n1-n2，该d_n1-n2表示无人机n1与无人机n2之间的距离；

(6.3.4)根据计算的欧式距离d_n1-n2找出各个无人机之间距离最小的两个无人机n1'和n2'；

(6.3.5)用无人机n1'与其他无人机之间的距离构成第一集合{d_n1'-1,d_n1'-2,…,d_n1'-n}，将无人机n2'与其他无人机之间的距离构成第二集合{d_n2'-1,d_n2'-3,…,d_n2'-n}，并对这两个集合内元素按照升序排序；

(6.3.6)比较无人机n1'的距离集合中最小的距离值和无人机n2'距离集合中最小的距离值：

若无人机n1'中的最小距离值小于无人机n2'中的最小的距离值，则删掉无人机n1'；

若无人机n1'中的最小距离值大于无人机n2'中的最小的距离值，则删掉无人机n2'；

若两者相等，则比较两个无人机集合中次小的距离值；

以此类推，直到两者不相等，最终得到删减之后的无人机个数和部署位置，即为当前的无人机个数N和部署位置Z；

(6.4)根据当前的N和Z，更新上述参数C、fsb_C、U、fsb_U、F、E_min、num_max：

(6.4.1)根据贪心的关联策略确定关联矩阵C以及该关联是否是可行解fsb_C：

(6.4.1.1)根据用户m到无人机n之间的距离d_mn，构造每个用户m完成任务的候选无人机集合V_m：

首先，计算用户m到无人机n之间的距离d_mn；

然后，判断d_mn＜R是否成立：

若成立，则表示无人机到用户之间的距离小于无人机的覆盖半径，将无人机n列入用户m的候选集V_m中；

否则，不将无人机n列入用户m的候选集V_m中；

(6.4.1.2)根据以下准则将所有用户分为两类：

将候选集V_m中只有一个无人机备选的集合作为第一类；

将候选集V_m中有多个无人机备选的集合作为第二类；

第一类任务的关联优先级高于第二类任务；

(6.4.1.3)按照如下关联准则进行关联，得到关联矩阵C以及该关联矩阵是否是可行解fsb_C：

首先，判断第一类用户候选集中的无人机是否接满：若没有接满，令对应的c_mn＝1，表示关联；否则，c_mn＝0；

然后，根据第二类用户候选集V_m中的元素数，对其进行升序排序，优先给候选集小的用户确定关联情况，对于用户m，根据其候选集V_m中每个候选无人机到用户m的距离，按照升序排序，如果距离相等则按照无人机接入用户数升序排序，将用户优先关联到距离

近且接入用户数少的无人机；

(6.4.1.4)按照上述策略，判断是否存在候选集为空或候选集中可关联的无人机均接满的情况：

若是，则关联失败，fsb_C＝0；

否则，关联成功，fsb_C＝1；

(6.4.2)由下式推导出每个用户在不同无人机处计算所需的最小资源f_mn,min：

(6.4.3)求解初始化卸载矩阵U：

(6.4.3.1)根据N，Z，C和f_mn,min将问题P化简为关于卸载矩阵U的0-1规划问题P1：

P1:

s.t.P1:C3,C4,C6

(6.4.3.2)利用分枝定界法对P1进行求解，得到U以及表示该决策是否是可行解的fsb_U，即用仿真软件中关于分支定界法的库函数进行求解；

(6.4.4)根据U中的元素u_mn计算F中的元素：f_mn＝u_mnf_mn,min，最终得到计算资源分配矩阵F＝[f_mn]_M×N，并令NoS＝NoS+1；

(6.4.5)判断初始解是否是可行解，即fsb_C＝fsb_U＝1是否成立：

如果成立，则根据N、Z、C、U、F计算当前解对应的系统总能耗E，令E_min＝E，完成最多任务数num_max＝M；

如果不成立，则求这组解完成的计算任务数num，并判断num＞num_max是否成立：

若是，则令num_max＝num，返回到步骤(6.2)；

否则，不修改num_max，直接返回到步骤(6.2)；

(6.5)利用改进的差分进化算法确定当前无人机个数N下的参数Z、C、fsb_C、U、fsb_U、F、E_min、num_max：

(6.5.1)将当前的无人机部署位置Z作为父代种群Q，故种群大小为N，将种群中的第i个个体值对应无人机的部署位置，得到种群中第i个个体q_i为：q_i＝[q_ix,q_iy]；

(6.5.2)对种群Q进行N次变异和交叉操作得到N个实验向量个体，形成实验向量种群A：

(6.5.2.1)按照下式进行变异操作，得到变异向量e_i：

其中，λ₁,λ₂,λ₃为Q中随机选出的三个互不相等的个体，g是差分变异因子，取值为0.4。

(6.5.2.2)在建立变异向量后，将变异向量e_i与Q中的一个随机个体q_i交叉，得到一个实验个体向量a_i：

其中，实验个体向量a_i的第一个维度a_ix为：

实验个体向量a_i的第二个维度a_iy为：

在上式中rate_c∈[0,1]是交叉率，J_r是在x和y中随机选择一个维度；

(6.5.2.3)由N个实验个体向量a_i组成实验向量种群A；

(6.5.3)依次用A中的个体随机替换Q中的某一个个体，得到新的种群W；

(6.5.4)根据种群W对应的无人机部署位置Z_W和无人机个数N，采用(6.2)中的方法确定对应的关联矩阵C_W，卸载矩阵U_W，资源分配矩阵F_W，fsb_C和fsb_U；

(6.5.5)根据N、Z_W、C_W、U_W、F_W，计算完成任务数num_W，令NoS＝NoS+1；

(6.5.6)判断num_W＞num_max是否成立：若是，则令完成最多用户任务数num_max＝num_W，并让Z，C，U，F分别等于Z_W，C_W，U_W，F_W；否则，不进行操作；

(6.5.7)判断num_W＝M是否成立：

如果成立，则表示当前解为可行解，再根据N、Z_W、C_W、U_W、F_W计算对应的系统能耗E_W，执行(6.5.8)；

如果不成立，表示当前解为不可行解，即num_W＜M，令not＝not+1，执行(6.5.9)；

(6.5.8)判断E_W＞E_min是否成立：

如果成立，则表示当前种群对应部署位置求得的解为可行解，且能耗更低，令E_min＝E_W，并令五个临时解N_temp、Z_temp、C_temp、U_temp、F_temp分别等于N、Z_W、C_W、U_W、F_W，判断此时flag是否为0：若是，则表示可以继续删减无人机个数，令not＝0；否则，执行步骤(6.5.9)；

如果不成立，不进行操作；

(6.5.9)判断不可行解次数not＝100是否成立：

若成立，则表示当前无人机个数经过多次迭代仍然没有找到一组可行解，令flag＝1，表示停止删减无人机个数，执行(6.5.10)；

若不成立，直接执行(6.5.10)；

(6.5.10)判断N_temp，Z_temp，C_temp，U_temp，F_temp是否有保存的可行解：

如果没有，则表示始终没有找到问题的可行解，将最多完成任务数num_max输出，算法结束；

否则，令N，Z，C，U，F分别等于N_temp，Z_temp，C_temp，U_temp，F_temp；

(6.6)判断NoS＜NoS_max是否成立：

如果成立，则返回步骤(6.2)继续迭代求解；

否则迭代终止，得到最终解无人机数目N'、无人机位置Z'、关联矩阵C'、卸载矩阵U'、计算资源分配矩阵F'。

步骤7，根据N'、Z'、C'、U'、F'的值实施部署和计算卸载。

(7.1)选择N'个无人机按照部署矩阵Z'进行部署；

(7.2)根据关联矩阵C'确定用户与无人机的关联性：

若C'中的元素c_mn＝1，则将用户m与无人机n关联，并将用户m的计算任务传输至无人机n处；

否则，用户m与无人机n不关联；

(7.3)根据卸载决策矩阵U'中的元素值u_mn，确定用户计算任务的执行对象：

若u_mn＝1，则由无人机n按照资源分配矩阵F'中的元素f_mn给用户分配计算资源，完成用户m的计算任务；

否则，由关联无人机n将用户m的计算任务中转给邻居基站，由邻居基站完成计算任务。

以下结合仿真实验对本发明的技术效果作进一步说明：

一、仿真条件

仿真采用Matlab2019软件平台进行，用户随机的分布在一个半径为300m的圆形区域中，用户个数设为100～300，用户的计算任务的数据量D_m＝[10,800]KB、所需计算资源数F_m＝100～200cycles/bit，可容忍时延T＝1s；无人机的高度H_n＝100m、最大俯角θ＝π/4、覆盖半径为R＝H_n tanθ＝100m、悬停功率P^H＝100W、接入用户上限U_n＝20、计算资源上限f_n,max＝2GHz，参考距离为一米时的空地信道增益β^G2A和空空信道增益β^A2A均为1.42×10^-4，用户与无人机的发射功率邻居基站的坐标为(x₀,y₀,H₀)＝(600,300,100)。

由于本发明考虑的是一个新的场景，没有现有方法能够直接求解，因此将求解框架均为上下层迭代法，但在求解的卸载矩阵U，无人机位置Z这两个参数时采用其他方法的两种算法作为对比算法，其中，prior UAV算法在求解卸载决策U时，将计算任务优先卸载到无人机处执行，而本发明采用分支定界法；PSO-Z在求解无人机位置Z时采用粒子群优化算法，而本发明采用差分进化法。

二、仿真内容与结果：

仿真1，分别取用户个数为100～300，对本发明和的对比算法分别为指定区域中用户提供服务，得到各自消耗的系统总能耗和部署的无人机个数，结果如图3所示。其中：

图3(a)为系统总能耗的对比图，

图3(b)为部署的无人机个数对比图。

观察图3(a)可以发现，当用户数为100时，prior UAV的总能耗与本发明的总能耗相差不多，但是随着用户数的增加，基于分枝定界法的本发明求得的卸载决策对应的系统总能耗与优先卸载到无人机的prior UAV算法对应的系统总能耗之间的差距越来远大，本发明的节能优点逐渐体现出来。从图3(a)中可以明显看到利用改进PSO求解无人机位置的PSO-Z算法的系统能耗明显大于基于改进差分进化算法的本发明，这主要因为PSO算法在搜索时随机性更大，算法性能不如改进差分进化算法。

从图3(b)中可以看出，当用户数为200时，本发明需要部署15个无人机就能完成所有计算任务，而prior UAV则需要部署16个无人机，PSO-Z需要部署18个无人机才能完成所有计算任务，且无论用户的个数多还是少，本发明部署的无人机个数均最少，成本最小。

仿真2，当可容忍时延为1s，用户数为300时，在不同时间点对本发明和对比方法prior UAV和PSO-Z为指定区域中用户提供服务的任务率进行仿真，其结果如图4所示。

从图4中可以看出，在不同时间点本发明的任务完成率始终高于prior UAV算法，在部分时间点本发明与PSO-Z的任务完成率相同。

图3和图4表明，本发明在减少成本的同时，能尽早完成用户的计算任务，给用户提供一个很好的体验。

Claims (10)

1.一种无人机辅助边缘计算网络的部署与卸载方法，其特征在于，包括如下：

(1)设置用户相关参数和无人机辅助网络相关参数：

在半径为L的圆形故障区域Y内随机分布了M个地面用户，其集合为O＝{1,…,m,…,M}，用户m的位置为(x_m,y_m,0)；用户m需要完成计算任务A_m＝(F_m,D_m,T)，其中F_m表示计算所需的CPU转数；D_m表示计算数据量；T为时延约束；

设无人机集合为G＝{1,…,n,…,N}，N为待确定的无人机总数，第n个无人机的坐标为(x_n,y_n,H_n)，俯角固定为θ，最大覆盖半径R为H_ntanθ，设U_n为无人机n能够接入用户数的最大值，f_n,max为无人机n的计算资源上限，发射功率为悬停功率为P^H，均不可调；设邻居基站的坐标为(x₀,y₀,H)；

(2)根据上述初始化参数建立最小化能耗问题P：

C3:u_mn≤c_mn,m∈O,n∈G，

C5:c_mnd_mn≤R,m∈O,n∈G，

C6:t_m≤T,m∈O，

C7:(x_n,y_n)∈Y,

其中，C为无人机与用户的关联矩阵，c_mn为C中的第m行第n列元素；

U为卸载矩阵，u_mn为U中的第m行第n列元素，Z为无人机的位置矩阵；

F为无人机计算资源分配矩阵，f_mn为F中的第m行第n列元素，

为用户m将计算任务发送给无人机n的通信能耗；/>为无人机n完成用户m任务的计算能耗，/>为无人机n将用户m的计算任务中转给邻居基站的通信能耗，/>为无人机n的悬停能耗；α表示与用户能耗相比无人机能耗的权重系数，t_m为用户m计算任务完成的总时间，d_mn是用户m与无人机n之间的水平距离；

(3)确定无人机的初始个数N⁰及无人机的初始位置Z⁰；根据M⁰，Z⁰确定初始关联矩阵C⁰、关联矩阵是否为可行解fsb_C、初始卸载矩阵U⁰、卸载矩阵是否是可行解为fsb_U、初始资源分配矩阵F⁰、最小能耗E_min和完成的最多任务数num_max；

(4)使用上下层迭代法求解问题P中的N、Z、C、U、F：

(4a)设置求解次数为NoS，最多迭代求解次数为NoS_max，停止删减无人机个数为flag，当前解的不可行次数为not，初始化NoS＝0，flag＝0，not＝0，NoS_max＝1000，初始化N、Z、C、U、F分别等于N⁰、Z⁰、C⁰、U⁰、F⁰；

(4b)判断当前解是否是可行解以及无人机个数是否可以继续减少：

如果fsb_C＝fsb_U＝1且flag＝0，则当前解为可行解且无人机个数可以继续减少，执行(4c)；否则，跳转到步骤(4e)；

(4c)对当前可行解N、Z、C、U、F进行保存，并去掉一个冗余的无人机得到当前的无人机个数N和无人机部署位置Z；

(4d)根据当前的N和Z，更新上述参数C、fsb_C、U、fsb_U、F、E_min、num_max，并令NoS＝NoS+1，执行步骤(4f)；

(4e)利用改进的差分进化算法确定当前无人机个数N下的参数Z、C fsb_C、U、fsb_U、F、E_min、num_max；

(4f)判断NoS＜NoS_max是否成立，如果成立，则返回步骤(4b)继续迭代求解；否则迭代终止，得到最终解无人机数目N'、无人机位置Z'、关联矩阵C'、卸载矩阵U'、计算资源分配矩阵F'；

(5)选择N'个无人机按照部署矩阵Z'进行部署；

(6)根据关联矩阵C'确定用户与无人机的关联性：若C'中的元素c_mn＝1，则将用户m与无人机n关联，并将用户m的计算任务传输至无人机n处；否则，用户m与无人机n不关联；

(7)根据卸载决策矩阵U'中的元素值u_mn，确定用户计算任务的执行对象：

若u_mn＝1，则由无人机n按照资源分配矩阵F'中的元素f_mn给用户分配计算资源，完成用户m的计算任务；

否则，由关联无人机n将用户m的计算任务中转给邻居基站，由邻居基站完成计算任务。

2.根据权利要求1所述的方法，其特征在于，步骤(2)中根据初始化参数建立最小化能耗问题P，实现如下：

(2a)根据用户m与无人机n的位置坐标，得到两者之间的水平距离d_mn和无人机n与邻居基站之间的水平距离d_nB：

(2b)根据(2a)中的水平距离d_mn和无人机n与邻居基站之间的水平距离d_nB，建立基于自由空间路径损耗的信道模型，即用户m到无人机n的信道功率增益h_mn及无人机n到邻居基站之间的信道功率增益h_nB：

其中β^G2A和β^A2A分别表示参考距离为一米时的空地信道增益和空空信道增益；

(2c)根据(2b)中用户m到无人机n的信道功率增益h_mn及无人机n到邻居基站之间的信道功率增益h_nB，利用香农定理得到用户m到无人机n的传输速率r_mn及无人机n到邻居基站之间的传输速率r_nB：

其中，B₁表示用户与无人机之间的传输带宽，B₂表示无人机与邻居基站之间的传输带宽，P_m为用户m设备的发射功率，为无人机n的发射功率，N₀为噪声功率谱密度；

(2d)计算用户m将计算任务发送给无人机n的通信传输时间及通信能耗/>

(2e)计算无人机m将用户n的计算任务中转给邻居基站的通信传输时间及通信能耗

(2f)计算无人机n完成用户m的任务所需处理时间及计算能耗/>

其中，f_mn表示无人机n分给用户m的CPU频率，ε表示无人机机载服务器芯片的有效电容系数；

(2g)计算无人机n的悬停能耗

(2h)设置如下相关矩阵和变量：

设C＝[c_mn]_M×N为无人机与用户的关联矩阵，c_mn＝1表示用户m与无人机n关联，c_mn＝0表示不关联；

设U＝[u_mn]_M×N为用户的计算卸载决策矩阵，当c_mn＝1且u_mn＝1表示无人机n为用户m提供服务，c_mn＝1且u_mn＝0表示关联无人机n将用户m的计算任务中转给邻居基站，由邻居基站完成计算任务；

设F＝[f_mn]_M×N为计算资源分配矩阵；

设Z＝[(x_n,y_n)]_N×1为无人机的位置矩阵；

设用户的计算任务完成总时间为：

由(2d)(2e)(2f)(2g)的结果得到系统总能耗为：

(2i)设置约束条件：

根据一个用户只能与一个无人机关联且所有用户需要被覆盖的特性，设第一个约束条件：

根据每个无人机接入的用户数不能超过最大接入用户数的限制，设置第二个约束条件

根据无人机只能为其关联的用户提供服务的特性，设置第三个约束条件u_mn≤c_mn；

根据无人机m分配给覆盖范围内用户的计算资源之和不超过其计算资源最大值的限制，设置第四个约束

根据无人机关联的用户需在其覆盖范围内的情况，设置第五个约束c_mnd_mn≤R；

根据用户n的任务完成时间不超过最大容忍时延的限制，设置第六个约束t_m≤T；

根据无人机的水平位置需在故障基站范围内的限制，得到第七个约束条件(x_n,y_n)∈Y；

(2j)结合上述约束条件和参数，将能耗最小化问题P表示如下：

C3:u_mn≤c_mn,m∈O,n∈G，

C5:c_mnd_mn≤R,m∈O,n∈G，

C6:t_m≤T,m∈O，

C7:(x_n,y_n)∈Y,

其中，α表示与用户能耗相比无人机能耗的权重系数。

3.根据权利要求1所述的方法，其特征在于，步骤(3)中确定无人机的个数N⁰及无人机的位置Z⁰，实现如下：

(3a)初始化无人机的个数为一个较大值N⁰＝2×(M/U_n)；

(3b)通过Kmeans++算法确定无人机的初始位置Z⁰，设置循环次数iter＝0：

(3b1)借助Kmeans++算法，将无人机的个数N⁰作为类数，根据用户的位置进行聚类，将聚类中心作为无人机的部署位置；

(3b2)根据(3b1)得到的无人机部署位置确定每个用户m执行任务的候选集V_m：

(3b2a)计算用户m到无人机n之间的距离d_mn；

(3b2b)判断d_mn＜R是否成立：若成立，则表示无人机到用户之间的距离小于无人机的覆盖半径，则将无人机n列入用户m的候选集V_m中；

(3b3)确定无人机的初始位置Z⁰：

(3b3a)判断所有用户的候选集是否为空：若不为空，则将当前的无人机位置作为初始位置Z⁰；否则，令iter＝iter+1，执行步骤(3b3b)；

(3b3b)判断iter＞1000是否成立：

若成立，则表示经过多次聚类始终没有找到满足约束的无人机初始位置，将最后一次迭代得到的聚类中心作为无人机的初始位置；

否则，返回至步骤(3b1)重新求解无人机的初始位置。

4.根据权利要求1所述的方法，其特征在于，步骤(3)中根据N⁰，Z⁰确定关联矩阵C⁰以及该关联是否是可行解fsb_C，实现如下：

(3c)采用贪心的关联策略得到关联矩阵C⁰及该关联是否是可行解fsb_C：

(3c1)计算用户m到无人机n之间的距离d_mn，将d_mn＜R的无人机n列入用户m的候选集V_m中；

(3c2)根据以下准则将所有用户分为两类：

第一类：候选集V_m中只有一个无人机备选，即该用户只在一个无人机的覆盖半径内；

第二类：候选集V_m中有多个无人机备选，表示该用户在多个无人机的覆盖范围内；

第一类任务的关联优先级高于第二类任务；

(3c3)按照如下关联准则进行关联，得到关联矩阵C⁰以及该解是否是可行解fsb_C：

(3c3a)判断第一类用户候选集中的无人机是否接满：若没有接满，令对应的c_mn＝1，表示关联；

(3c3b)根据第二类用户候选集V_m中的元素数，对其进行升序排序，优先给候选集小的用户确定关联情况，对于用户m，根据其候选集V_m中每个候选无人机到用户m的距离，按照升序排序，如果距离相等则按照无人机接入用户数升序排序，将用户优先关联到距离近且接入用户数少的无人机；

(3c4)按照上述策略，判断是否存在候选集为空或候选集中可关联的无人机均接满的情况：

若是，则关联失败，fsb_C＝0；

否则，关联成功，fsb_C＝1。

5.根据权利要求1所述的方法，其特征在于，步骤(3)中根据N⁰，Z⁰确定卸载矩阵U⁰、卸载矩阵是否是可行解fsb_U、资源分配矩阵F⁰，实现如下：

(3d)由下式推导出每个用户在不同无人机处计算所需的最小资源f_mn,min：

(3e)求解初始化卸载矩阵U⁰：

(3e1)根据N⁰，Z⁰，C⁰和f_mn,min将问题P化简为关于卸载矩阵U⁰的0-1规划问题P1：

s.t.P1:C3,C4,C6

(3e2)利用分枝定界法对P1进行求解，得到U⁰以及表示该卸载矩阵是否是可行解的fsb_U，即用仿真软件中关于分支定界法的库函数进行求解；

(3f)根据U⁰中的元素u_mn计算F⁰中的元素：f_mn＝u_mnf_mn,min，最终得到计算资源分配矩阵F⁰＝[f_mn]_M×N。

6.根据权利要求1所述的方法，其特征在于，步骤(3)中根据N⁰，Z⁰确定最小能耗E_min和完成最多任务数num_max，实现如下：

(3g)判断初始解是否是可行解，即fsb_C＝fsb_U＝1是否成立：

若是可行解，则根据N⁰、Z⁰、C⁰、U⁰、F⁰计算当前解对应的系统总能耗E⁰，初始化系统最小能耗E_min＝E⁰，完成最多任务数num_max＝M；

否则，计算时延约束内完成任务的用户个数num⁰，初始化系统最小能耗E_min为一个极大的值，完成最多任务数num_max＝num⁰。

7.根据权利要求1所述的方法，其特征在于，步骤(4c)对当前可行解N，Z，C，U，F进行保存，并去掉一个冗余的无人机得到当前的N和Z，实现如下：

(4c1)设置N_temp，Z_temp，C_temp，U_temp，F_temp这五个临时值并赋值为0，用于保存可行的N，Z，C，U，F；

(4c2)令N_temp，Z_temp，C_temp，U_temp，F_temp分别等于N，Z，C，U，F；

(4c3)计算Z中各个无人机之间的欧式距离d_n1-n2，该d_n1-n2表示无人机n1与无人机n2之间的距离；

(4c4)根据计算的欧式距离d_n1-n2找出各个无人机之间距离最小的两个无人机n1'和n2'；

(4c5)用无人机n1'与其他无人机之间的距离构成第一集合{d_n1'-1,d_n1'-2,…,d_n1'-n}，将无人机n2'与其他无人机之间的距离构成第二集合{d_n2'-1,d_n2'-3,…,d_n2'-n}，并对这两个集合内元素按照升序排序；

(4c6)比较无人机n1'的距离集合中最小的距离值和无人机n2'距离集合中最小的距离值：

若无人机n1'中的最小距离值小于无人机n2'中的最小的距离值，则删掉无人机n1'；

若无人机n1'中的最小距离值大于无人机n2'中的最小的距离值，则删掉无人机n2'；

若两者相等，则比较两个无人机集合中次小的距离值，以此类推，直到两者不相等；

最终得到删减之后的无人机个数和部署位置，即为当前的无人机个数N和部署位置Z。

8.根据权利要求1所述的方法，其特征在于，步骤(4d)根据当前的无人机个数N和部署位置Z，确定关联矩阵C以及该关联是否是可行解fsb_C，实现如下：

(4d1)根据贪心的关联策略确定关联矩阵C以及该关联是否是可行解fsb_C：

(4d1a)根据用户m到无人机n之间的距离d_mn，构造每个用户m完成任务的候选无人机集合V_m：

首先，计算用户m到无人机n之间的距离d_mn；

然后，判断d_mn＜R是否成立：

若成立，则表示无人机到用户之间的距离小于无人机的覆盖半径，将无人机n列入用户m的候选集V_m中；

否则，不将无人机n列入用户m的候选集V_m中；

(4d1b)根据以下准则将所有用户分为两类：

将候选集V_m中只有一个无人机备选的集合作为第一类；

将候选集V_m中有多个无人机备选的集合作为第二类；

第一类任务的关联优先级高于第二类任务；

(4d1c)按照如下关联准则进行关联，得到关联矩阵C以及该关联矩阵是否是可行解fsb_C：

首先，判断第一类用户候选集中的无人机是否接满：若没有接满，令对应的c_mn＝1，表示关联；否则，c_mn＝0；

然后，根据第二类用户候选集V_m中的元素数，对其进行升序排序，优先给候选集小的用户确定关联情况，对于用户m，根据其候选集V_m中每个候选无人机到用户m的距离，按照升序排序，如果距离相等则按照无人机接入用户数升序排序，将用户优先关联到距离近且接入用户数少的无人机；

(4d1d)按照上述策略，判断是否存在候选集为空或候选集中可关联的无人机均接满的情况：

若是，则关联失败，fsb_C＝0；

否则，关联成功，fsb_C＝1。

9.根据权利要求1所述的方法，其特征在于，步骤(4d)根据当前的无人机个数N和部署位置Z，确定卸载矩阵U、卸载矩阵是否是可行解fsb_U、资源分配矩阵F、最小能耗E_min和完成最多任务数num_max，实现如下：

(4d2)由下式推导出每个用户在不同无人机处计算所需的最小资源f_mn,min：

(4d3)求解初始化卸载矩阵U：

(4d3a)根据N，Z，C和f_mn,min将问题P化简为关于卸载矩阵U的0-1规划问题P1：

s.t.P1:C3,C4,C6

(4d3b)利用分枝定界法对P1进行求解得到U以及表示该决策是否是可行解的fsb_U，即用仿真软件中关于分支定界法的库函数进行求解；

(4d4)根据U中的元素u_mn计算F⁰中的元素：f_mn＝u_mnf_mn,min，最终得到计算资源分配矩阵F＝[f_mn]_M×N；

(4d5)判断初始解是否是可行解，即fsb_C＝fsb_U＝1是否成立：

若是，则根据N、Z、C、U、F计算当前解对应的系统总能耗E，令E_min＝E，完成最多任务数num_max＝M；

否则，求这组解完成的计算任务数num，判断num＞num_max是否成立，若是，令num_max＝num；返回到步骤(4b)。

10.根据权利要求1所述的方法，其特征在于，步骤(4e)中利用改进的差分进化算法求当前无人机个数N下的Z、C、fsb_C、U、fsb_U、F、E_min、num_max，实现如下：

(4e1)将当前的无人机部署位置Z作为父代种群Q，故种群大小为N，种群中的第i个个体值对应无人机的部署位置，故种群中第i个个体q_i为：q_i＝[q_ix,q_iy]；

(4e2)对种群Q进行N次变异和交叉操作得到N个实验向量个体，形成实验向量种群A：

(4e2a)按照下式进行变异操作，得到变异向量e_i：

其中，λ₁,λ₂,λ₃为Q中随机选出的三个互不相等的个体，g是差分变异因子，取值为0.4。

(4e2b)在建立变异向量后，将变异向量e_i与Q中的一个随机个体q_i交叉，得到一个实验个体向量a_i：

其中，实验个体向量a_i的第一个维度a_ix为：

实验个体向量a_i的第二个维度a_iy为：

在上式中rate_c∈[0,1]是交叉率，J_r是在x和y中随机选择一个维度；

(4e2c)由N个实验个体向量a_i组成实验向量种群A；

(4e3)依次用A中的个体随机替换Q中的某一个个体，得到新的种群W；

(4e4)根据种群W对应的无人机部署位置Z_W和无人机个数N，采用(4b)中的方法确定对应的关联矩阵C_W，卸载矩阵U_W，资源分配矩阵F_W，fsb_C和fsb_U；

(4e5)根据N、Z_W、C_W、U_W、F_W，计算完成任务数num_W，令NoS＝NoS+1；

(4e6)判断num_W＞num_max是否成立：若是，则令完成最多用户任务数num_max＝num_W，并让Z，C，U，F分别等于Z_W，C_W，U_W，F_W；否则，不进行操作；

(4e7)判断num_W＝M是否成立：

如果成立，则表示当前解为可行解，再根据N、Z_W、C_W、U_W、F_W计算对应的系统能耗E_W，执行(4e8)；

如果不成立，表示当前解为不可行解，即num_W＜M，令not＝not+1，执行(4e9)；

(4e8)判断E_W＞E_min是否成立：

如果成立，则表示当前种群对应部署位置求得的解为可行解，且能耗更低，令E_min＝E_W，并令五个临时解N_temp、Z_temp、C_temp、U_temp、F_temp分别等于N、Z_W、C_W、U_W、F_W，判断此时flag是否为0：若是，则表示可以继续删减无人机个数，令not＝0；否则，执行步骤(4e9)；

如果不成立，不进行操作；

(4e9)判断不可行解次数not＝100是否成立：若成立，则表示当前无人机个数经过多次迭代仍然没有找到一组可行解，令flag＝1，表示停止删减无人机个数，执行(4e10)；

(4e10)判断N_temp，Z_temp，C_temp，U_temp，F_temp是否有保存的可行解：

如果没有，则表示始终没有找到问题的可行解，将最多完成任务数num_max输出，算法结束；

否则，令N，Z，C，U，F分别等于N_temp，Z_temp，C_temp，U_temp，F_temp。