1.一种多无人机辅助边缘计算联合卸载和部署方法,其特征在于,包括:步骤1:获取地面用户的位置信息,其中,地面用户的数量为K,地面用户的集合表示为对于任意的地面用户sk的水平位置坐标为步骤2:根据每个地面用户的位置信息,采用聚类算法对地面用户聚类,生成M个簇;
步骤3:为每个簇设置一个无人机UAV,每个UAV配备一个空中边缘服务器,以执行簇中地面用户卸载过来的DL任务,其中,每个地面用户与关联的UAV之间的信道为正交通信信道,每个sk产生Nk个DL任务,每个DL任务包含多个子任务,UAV集合表示为步骤4:通过联合优化子任务卸载策略和UAV位置部署,从而使得所有的DL任务的最大完工时间最小化;
步骤5:采用优化后的子任务卸载策略和UAV位置部署结果,对子任务进行卸载以及对无人机的位置进行部署,步骤4中的优化问题,记为P1,用公式表示为:其中,
C1‑C5表示五个约束条件;
表示由地面用户sk生成的第n个DL任务,表示所有的DL任务的集合,即
表示DL任务 的产生时间;
表示DL任务 的可容忍延迟;
表示DL任务 的DAG结构;
是DL任务 的子任务集合,每个子任务对应于深度神经网络的某一层, 表示集合 中元素的个数,即 的子任务的总个数L;
为边集,表征了DL任务 的子任务之间的依赖关系,数据流边 表示子任务 是子任务 的父任务,即子任务 依赖于子任务表示无人机部署, 表示无人机um的水平位置;
表示子任务卸载策略,xkmnl∈{0,1},xkmnl=1表示子任务 将被卸载到无人机um上处理,xkmnl=0则表示子任务 在用户sk本地执行;符号 所在的式子为定义式;
qi和qj表示任意两个无人机ui和uj的水平位置;
dmin表示任何两架无人机之间应该保持的最小安全距离;
表示任务 中所有子任务的最大完成时间;
表示子任务 的完成时间;
表示子任务 在设备d上的开始时间,设备d为地面用户sk或无人机um,由子任务 是否需要被卸载来决定;
表示子任务 所需的计算时间;
所述DAG结构为有向无环图结构,DL任务为深度学习任务。
2.根据权利要求1所述的一种多无人机辅助边缘计算联合卸载和部署方法,其特征在于, 通过下式计算:其中, 表示子任务 所需的FLOP次数,FLOP次数为浮点运算次数,fk和fm分别表示地面用户sk和无人机um的计算能力,即每秒浮点运算次数;
,
其中, 表示子任务 传输到设备d上的传输延迟, 表示子任务在设备d的计算队列中的排队延迟。
3.根据权利要求2所述的一种多无人机辅助边缘计算联合卸载和部署方法,其特征在于,传输延迟 依赖于子任务 依赖的子任务 在设备d′上的完成时间子任务 在传输队列的等待时间 以及子任务 生成的输出结果数据发送到子任务 的执行设备所需的时间 即其中,子任务 依赖子任务 即子任务 是子任务 的一个父任务,表示子任务 的所有父任务的集合,设备d′为地面用户sk或无人机um,由子任务 是否被卸载来决定;
表示具有本地依赖的卸载执行,即,当 时,表示子任务 被卸载到UAV上,而其依赖的子任务 在本地执行,否则 xkmnl′表示子任务 是否被卸载到UAV;
表示子任务 生成的输出结果数据从地面用户sk传输到无人机um的上行传输时长;
, 表示由子任务 生成的输出结果数据的大小, 表示地面用户sk将任务卸载到无人机um时的上行速率;
表示具有卸载依赖的本地执行,即,当 时,表示子任务 在本地执行,而其依赖的子任务 被卸载到UAV上,否则表示将子任务 生成的输出结果数据从无人机um传输到地面用户sk的下行传输时长;
, 表示地面用户sk从无人机um下载数据时的下行速率;
表示子任务 在设备d′的传输队列 中获取信道资源的排队延迟,和 表示由地面用户sk′生成的第n′个DL任务中的第i和第j个子任务;
表示传输子任务 之前,设备d′的传输队列 中的数据流边集合,其中,传输子任务 之前的设备d′的传输队列 也记为表示子任务 传输到设备d′上的传输延迟;
排队延迟 用公式表示为:
其中, 表示子任务 在设备d上的完成时间, 表示设备d在计算子任务 之前,设备d的计算队列 中的子任务集合,其中,在计算子任务 之前,设备d的计算队列 也记为 表示由地面用户sk′生成的第n′个DL任务中的第l′个子任务。
4.根据权利要求3所述的一种多无人机辅助边缘计算联合卸载和部署方法,其特征在于,所述方法还包括步骤4中的P1问题转化为两个子问题,即子任务卸载决策问题和UAV位置部署问题,并利用交替迭代优化方法对两个子问题进行交替迭代优化,从而得到最优的子任务卸载策略和UAV位置部署,其中,交替迭代优化的过程为:S11:初始化UAV位置部署,令迭代次数r=0;
S12:在给定的 条件下,利用基于优先级的子任务卸载算法确定子任务卸载表示第r次迭代时无人机um的位置, 表示第r+1次迭代时的xkmnl;
S14:令t=0并将第r次迭代的 赋值给 的初始值,即 其中rt表示采用SCA方法时的内部迭代次数,所述SCA方法为逐次凸近似方法;
S15:在给定 时,通过SCA方法,用给定的 确定优化解 不断进行内部迭代,直到满足内部迭代终止条件;
S16:将内部迭代终止时得到的 赋值给 并将r+1赋值给r;
S17:回到步骤S12,重复执行步骤S12‑S16,直到满足迭代终止条件,在迭代终止时的子任务卸载和UAV的位置部署结果即为最优解。
5.根据权利要求4所述的一种多无人机辅助边缘计算联合卸载和部署方法,其特征在于,子任务卸载决策问题是在给定的UAV位置部署的条件下,优化卸载策略{xkmnl},将该子问题记为P2,P2表示为:s.t.(C1)‑(C5),
对于P2,采用基于优先级的子任务卸载算法,包括:S1:对所有的DL任务,根据每个DL任务 的可容忍延迟进行排序,根据排序结果确定DL任务的处理顺序;
S2:对于每个DL任务 中的子任务,利用概率上升秩算法确定每个子任务 的优先级即,给依赖数据传输时间更长的子任务设置更高的优先级,并根据优先级对子任务进行优先级排序;
S3:根据S1和S2中的排序结果,对所有的DL任务中的每个子任务 按照优先级顺序进行任务卸载。
6.根据权利要求5所述的一种多无人机辅助边缘计算联合卸载和部署方法,其特征在于,S2中优先级 的确定方式为:其中, 表示所有依赖 的子任务的集合, 是一个二元变量,表示在计算时是否考虑了输出结果 的传输时间; 和 分别为所有链路的平均传输速率和所有设备的平均计算能力,其中, rand()是一个返回[0,1)区间随机值的函数,λ是常数。
7.根据权利要求5所述的一种多无人机辅助边缘计算联合卸载和部署方法,其特征在于,S3具体包括,按照子任务的优先级顺序,对于每个子任务 执行步骤S31‑S40,直至所有DL任务中的所有子任务全部执行完毕,则可以得到 {xkmnl},其中,S31‑S40包括:
S31:判断l=1或者 是否成立,如果成立,执行S32;如果不成立,执行S33;
S32:使得xkmnl=0,并把 放到地面用户sk的计算队列 的队尾;
S33:根据下式确定xkmnl,即:其中, 表示子任务 卸载到其关联的无人机um上时子任务 的完成时间; 表示子任务 在本地执行时的完成时间,接着,执行S34;
S34:判断xkmnl=1是否成立,如果成立,说明子任务 需要被卸载到um上,则执行S35;
如果不成立,说明子任务 在本地执行,不需要卸载,则执行S36;
S35:将 添加到um的计算队列 的队尾,接着,执行S37;
S36:将把 添加到地面用户sk的计算队列的 的队尾,接着,执行S37;
S37:判断 在 里以及 是否成立,如果成立,说明子任务 依赖于子任务 并且,子任务 在本地执行,子任务 需要卸载到无人机um,执行S38;否则,执行S39;
S38:把 加入地面用户sk的传输队列 的队尾;
S39:判断 在 里并且 是否成立,如果成立,说明子任务 依赖于子任务 并且,子任务 被卸载在无人机um,而子任务 需要本地执行,则执行S40;
S40:把 加入无人机um的传输队列 的队尾。
8.根据权利要求4所述的一种多无人机辅助边缘计算联合卸载和部署方法,其特征在于,UAV位置部署问题是在固定卸载决策{xkmnl}的条件下,优化UAV位置部署{qm},将该子问题转化为P3,P3表示为:其中,
C6‑C8表示约束条件;
和 分别表示第r次迭代时的上行和下行速率;
表示上行速率的提升;
表示下行速率的提升;
η表示最小提升速率;
表示用户sk和无人机um之间的链路是否有数据传输,若ykm>0表示用户sk和无人机um之间的链接存在数据传输,否则ykm=0。
9.根据权利要求8所述的一种多无人机辅助边缘计算联合卸载和部署方法,其特征在于,所述方法还包括将问题P3转化为问题P4,P4表示为:其中,
C9‑C11表示约束条件;
表示上行速率 的下界,
表示下行速率 的下界,
H表示无人机距离地面的垂直高度,B为信道带宽, 表示在1米处的接收信噪2
比,Pk为sk的发射功率,σ为背景噪声功率; 其中Pm是um的传输功率;β0是在参考距离为1米的信道功率增益;加了上标rt的q表示在第rt次内部迭代时无人机的水平位置;
和 分别表示在第rt次内部迭代时的两个局部点,问题P4为标准的凸优化问题,则在S15中,在给定 时,通过SCA方法,用给定的求解问题P4,得到优化解