基于改进人工蜂算法的无人机编队拓扑生成优化方法

本发明涉及无人机编队拓扑的生成方法，更特别的说，是指一种考虑通信延迟和能量的无人机信息交互的拓扑优化，采用的是改进人工蜂算法来对无人机编队生成中无人机为菱形编队时的多目标信息交互的拓扑结构进行优化的方法。

编队飞行是指两架及两架以上无人机按一定队形编组或排列飞行。在编队飞行中，各机之间必须保持规定的距离、间隔和高度差。基本的编队队形有纵队、横队、楔形队、菱形队。编队飞行的中心问题是保持规定队形并充分发挥飞机性能。长机在选择飞行状态时应给僚机修正偏差的余地，僚机要与长机密切配合。飞行中，长机根据需要发出指令改变编队方案和各机相对位置。编队飞行要求精度高、纪律严、目视能力强，可用于攻击、轰炸、侦察、空投、搜索、掩护、防御、空中摄影、检阅、表演、训练等。

《导弹自主编队协同制导控制技术》，吴森堂，2015年9月第1版，第305-307页。指出了无人机系统结构，如图1所示。图中“编队制导计算机”用于完成无人机编队的队形生成与导引、队形控制与保持，其职责是根据编队决策与管理系统所生成的编队优化指标和编队的队形要求，实时优化并形成队形导引、控制与保持的指令，并通过成员飞行控制保证实现节点的避碰机动控制和高品质的编队队形。

自组织无人机集在执行任务时需要与其他无人机进行信息交互，从而保持无人机之间的距离和相对位置。无人机之间进行信息交互的链路通常叫做信息交互拓扑。

由于无人机之间的距离和通信信道原因，无人机机构成的信息交互中的通信链路存在着多种通信代价。在针对无人机通信代价中，仅考虑链长或平均延迟单一目标，生成拓扑可能不满足低延迟的要求，进而造成延迟大，存在无人机碰撞的风险。不考虑机对能量的分配利用，容易造成能量分配不均，导致部分无人机能量提前用尽，飞行途中多次变换拓扑这样的问题，降低了无人机机的稳定性。所以在降低通信能量的前提下，设计如何降低通信的延迟并且使无人机编队的能量分布利用更加均匀的优化算法，具有非常重要的意义。

为了解决现有无人机编队过程中，由于能量分布不均易致使无人机信息交互拓扑多变，进而可能造成无人机编队发生碰撞的技术问题，本发明提出了一种无人机编队多目标信息交互拓扑优化算法。本发明方法将平均剩余能量纳入无人机信息交互拓扑的构建体系中，综合考虑通信链长、平均网络延迟和平均剩余能量来建立多目标体系。为了以统一的标准衡量多个维度的目标，本发明应用目标规划将三个不同(通信链长、平均网络延迟和平均剩余能量)维度的目标转化为无量纲的偏差值，能够均衡的考虑各个目标对无人机信息交互拓扑构建的影响。依据无人机编队的特点，分析拓扑结构特征。提出了基于深度的邻域搜索算子DSF，从而得到改进的人工蜂算法。然后利用人工蜂算法来求解最优的无人机编队信息交互拓扑。通过验证，经过改进的人工蜂算法，能够快速的寻到最优的信息交互拓扑。本发明能够快速到满意解，能够适应各种编队信息交互拓扑的构建。

本发明是一种基于改进人工蜂算法的无人机编队拓扑生成优化方法，编队制导计算机接收来自导航计算机的同一编队无人机机中进行的各个无人机交互信息；其特征在于具体步骤为：

步骤一：构建无人机编队的二维邻接矩阵；

编队制导计算机依据无人机编队队形信息中的无人机个数来构造边连通图G＝(UAV,MV)；两两无人机之间存在有一条双向的信息交互通道，所述信息交互通道称为边连通图的边，每一个无人机为边连通图的顶点；

从无人机编队连通图G＝(UAV,MV)中获取无人机作为顶点的关联矩阵关系，称为无人机编队二维邻接矩阵，记为LL，且LL＝[Li,j]n×n；

Li,j为第i架无人机uavi与第j架无人机uavj之间的通信关联关系；

所述的无人机编队二维邻接矩阵LL＝[Li,j]n×n是与信息交互拓扑中的通信相对应的；若无人机uavi与无人机uavj存在有通信，则赋值为1；反之，若无人机uavi与无人机uavj不存在通信，则赋值为0；

步骤二：构建无人机编队通信链路的链长矩阵；

在本发明中，两两无人机之间进行的信息交互时的通信链路长度是一个相对通信距离(单位：m)数值；

在本发明中，编队制导计算机从导航计算机处获取各个无人机的通信有效范围，从而建立无人机编队通信链路的链长矩阵，记为CC，且CC＝[Ci,j]n×n；

Ci,j表示第i架无人机uavi与第j架无人机uavj之间通信链路的长度；

n表示一个编队无人机机中无人机的总数目；

在本发明中，Ci,j＝di,j×Li,j，di,j为第i架无人机uavi与第j架无人机uavj之间的通信距离，Li,j为无人机uavi与无人机uavj之间的通信关联关系；

在本发明中，需要计算的通信链路长度的隶属函数，记为μλ(Ci,j)，且

Cmax为当前迭代次数的最长链长；

Cmin为当前迭代次数的最小链长；

Cnew为当前迭代次数的链长；

步骤三：构建无人机编队组网后的平均网络延迟矩阵；

在本发明中，两两无人机之间进行的信息交互时的发生的网络延迟(单位：ms)；

在本发明中，建立的无人机编队组网后的平均网络延迟矩阵，记为DD，且DD＝[Di,j]n×n；

Di,j表示第i架无人机uavi与第j架无人机uavj之间的平均网络延迟；

n表示一个编队无人机机中无人机的总数目；

在本发明中，Di,j＝hi,j×Li,j，hi,j为第i架无人机uavi与第j架无人机uavj之间的平均网络延迟，Li,j为无人机uavi与无人机uavj之间的通信关联关系；

在本发明中，需要计算的平均网络延迟的隶属函数，记为uλ(Di,j)，且

Dmax为当前迭代次数的最大延迟；

Dmin为当前迭代次数的最小延迟；

Dnew为当前迭代次数的延迟；

步骤四：构建无人机编队组网后的平均剩余能量矩阵；

在本发明中，两两无人机之间进行的信息交互时的平均剩余能量(单位：百分比)；

在本发明中，建立的无人机编队组网后的平均剩余能量矩阵，记为EE，且EE＝[Ei,j]n×n；

Ei,j表示第i架无人机uavi与第j架无人机uavj之间的平均剩余能量；

n表示一个编队无人机机中无人机的总数目；

在本发明中，Ei,j＝ri,j×Li,j，ri,j为第i架无人机uavi与第j架无人机uavj之间的平均剩余能量，Li,j为无人机uavi与无人机uavj之间的通信关联关系；

在本发明中，需要计算的平均剩余能量的隶属函数，记为uλ(Ei,j)，且

最大的平均剩余能量记为Emax；所述Emax取值为1；

最小的平均剩余能量记为Emin；所述Emin取值为0.1；所述Emin对应初始解的平均剩余能量；

当前的平均剩余能量记为Enew；

步骤五：计算总的蜜源偏差；

在本发明中，总的蜜源偏差值，记为fit(x)，且

σ1为通信链路长度的权重；

σ2为平均网络延迟的权重；

σ3为平均剩余能量的权重；

fit(x)表示整个链接的偏差，偏差越小表明信息交互拓扑性能越好；

在本发明中针对不同的应用场景，可以调整各目标的权重，以实现更加突出对某一目标的重要性，即调整σ1,σ2,σ3的值；

步骤六：改进人工蜂算法参数初始化以及初始蜜源的建立；

步骤61，初始化改进人工蜂算法各参数；

在本发明中，初始化无人机编队队形中的需要运行改进人工蜂算法的参数有：

设置无人机编队蜂规模，记为NP；

设置最大循环迭代次数，记为λmax，初始时迭代次数λ＝0；

设置作为雇佣蜂身份的无人机uav雇佣蜂对食物源Limit的搜索次数，记为LILimit；

步骤62，生成多叉树树型结构的无人机信息交互；

在本发明中，采用多叉树树型结构对步骤一的无人机编队连通图G＝(UAV,MV)进行首次分层，得到首次无人机信息交互拓扑；所述首次无人机信息交互拓扑对应的是初始无人机食物源，记为Limit初始；

步骤63，生成无人机食物源；

继Limit初始之后，每一次无人机编队连通图G＝(UAV,MV)的变化，就有一个无人机信息交互拓扑，对应的也只有一个当前迭代的无人机食物源Limitλ；

步骤七：雇佣蜂无人机采用基于深度的领域搜索算子(DSF)在当前信息交互拓扑附近进行搜索，得到无人机食物源；

步骤71，计算蜜源偏差值；

在本发明中，依照每一次的信息交互拓扑结构，依据步骤二，三和四，执行步骤五，计算拓扑的当前迭代的蜜源偏差值fitλ(x)；

步骤72，计算适应度值；

在本发明中，作为雇佣蜂身份的无人机uav雇佣蜂在返回编队队形后，在信息交互拓扑展示区用摇摆舞通知编队队形内的身份为跟随蜂的无人机uav跟随蜂，在分享信息交互拓扑信息后，所述uav跟随蜂根据信息交互拓扑的适应度值Wλ，采用适应比例选择机制计算信息交互拓扑选择的概率，记为Pλ，且

Wλ为当前迭代的信息交互拓扑的适应度值；

Wmax表示食物源的最大适应度值；

步骤73，采用深度的领域搜索算子(DSF)搜索无人机食物源；

采用深度的邻域搜索算子DSF进行搜索当前迭代的无人机食物源Limitλ；

身份为雇佣蜂的无人机uav雇佣蜂在当前搜索次数上加1，即

步骤74，作为跟随蜂身份的无人机采用自适应比例选择策略在搜索的信息交互拓扑中进行选择，并变成雇佣峰身份的无人机，执行DSF；

身份为跟随蜂的无人机uav跟随蜂根据概率Pλ选择相应的信息交互拓扑，进而成为身份为雇佣蜂的无人机uav雇佣蜂，执行步骤71至步骤73；

身份为雇佣蜂的无人机uav雇佣蜂搜索次数递增1次；

步骤75，记录迭代次数；

判断身份为雇佣蜂的无人机uav雇佣蜂连续搜索次数LILimit是否大于最大搜索次数若不是，执行步骤71至步骤76，若是，则执行步骤八；

步骤八：作为侦察蜂身份的无人机采用全局随机搜索，完成寻新信息交互拓扑的任务；

身份为雇佣蜂的无人机uav雇佣蜂转变为身份为侦查蜂的无人机uav侦查蜂后，所述uav侦查蜂从无人机编队信息交互拓扑中选择一个信息交互拓扑，重复执行步骤一至步骤五，得到当前信息交互拓扑蜜源偏差值fitλ(x)；若蜜源偏差值fitλ(x)小于上一次的蜜源偏差值fitλ-1(x)，则替换上一次的信息交互拓扑，否则再次从无人机编队信息交互拓扑中选择一个信息交互拓扑，直至达到最大搜索次数执行步骤九；

步骤九：判断循环终止条件，输出最优信息交互拓扑

若迭代计算达到λmax，则停止计算，并且输出信息交互拓扑的位置，也就是最优的信息交互拓扑结构。

本发明的优点在于：

①本发明改进了一种搜索算子，依据无人机编队飞行的特点，建立基于深度的邻域搜索算子DSF，能够更快的发现偏差小的无人机信息交互拓扑。

②本发明综合考虑了三种通信代价，相比于距离这一单一通信代价，以通信链路的链长、平均网络延迟和平均剩余能量能够更加准确的衡量通信代价。

③本发明能够短时间内到满意的信息交互拓扑，在十几架编队的无人机集中能够在0.5秒内出满意的信息交互拓扑。

④本发明能够实现信息交互拓扑推荐，无人机编队可以通过推荐的信息交互拓扑实现无线通信，避免了信息交互拓扑变换次数过多，信息交互延迟较大给无人机编队飞行带来的危险。

图1是无人机系统的结构框图。

图2是无人机菱形编队队形示意图。

图3是目标函数表示目标实现水平的示意图。

图4是本发明基于改进人工蜂算法的无人机编队拓扑生成的流程图。

图5是经本发明方法处理得到的无人机编队信息交互拓扑结构图。

下面将结合附图和实施例对本发明做进一步的详细说明。

依据图1，在已知的无人机菱形编队队形中，无人机编队飞行过程中各无人机之间的通信距离，通信的延迟包括链路延迟和设备延迟以及各无人机当前剩余能量由导航计算机提供。编队制导计算机接收来自导航计算机的同一编队无人机机中进行的各个无人机交互信息，依据改进人工蜂算法进行无人机交互信息拓扑的编队生成及保持。

在本发明中，无人机编队队形是呈现多种多样的，本发明以一种12架无人机按照菱形编队队形(如图2所示)进行说明。图2中，带队的无人机称为长机，跟随长机执行任务的无人机称为僚机。

在本发明中，多个无人机形成的集合，记为无人机集UAV，且UAV＝{uav1,uav2,…,uavi,…,uavj,…,uavn}：

uav1表示编队无人机机中的第一架无人机。

uav2表示编队无人机机中的第二架无人机。

uavi表示编队无人机机中的第i架无人机。

uavj表示编队无人机机中的第j架无人机。

uavn表示编队无人机机中的最后一架无人机。下角标n表示一个编队无人机机中无人机的总数目。

为了方便说明，uavi、uavj和uavn为不同标识号的无人机。也就是说uavi、uavj和uavn不是同一架无人机。uavi也称为编队无人机机中的任意一架无人机；uavj也称为编队无人机机中的任意另一架无人机。

例如，由12架无人机形成的菱形编队队形中，作为长机的是编号为uav1的无人机，即第一架无人机；作为僚机的分别是僚机也称跟随机。

第二架无人机uav2。第三架无人机uav3。第四架无人机uav4。第五架无人机uav5。第六架无人机uav6。第七架无人机uav7。第八架无人机uav8。第九架无人机uav9。第十架无人机uav10。第十一架无人机uav11。第十二架无人机uav12。

人工蜂算法参考了《多目标人工蜂算法及遗传算法的研究与应用》，张长胜，2013年7月第1版，第11－13页。本发明中的无人机之间信息交互拓扑是作为蜂算法中的食物源Limit。然而，无人机信息交互拓扑的变化对应着食物源的变化。

依据人工蜂算法，无人机uavi作为雇佣蜂身份时(即)完成深度邻域搜索DSF任务。

依据人工蜂算法，无人机uavj作为非雇佣蜂身份时(即)，一方面完成寻新食物源任务，另一方面在完成一次寻新食物源任务后身份将转变为雇佣蜂。

依据人工蜂算法，无人机uavn作为侦查蜂身份时(即)完成寻新食物源任务。

依据人工蜂算法，无人机uav1作为跟随蜂时(即)用于完成转变为雇佣蜂的任务。

本发明方法中，如图5所示，作为雇佣蜂的无人机(排序后的第三层χ的无人机)与非雇佣蜂的无人机均需要通过蜜源偏差值fit(x)来判断当前食物源Limitλ的质量如何，通过分别计算通信链路长度的隶属函数μλ(Ci,j)、平均网络延迟的隶属函数uλ(Di,j)、平均剩余能量的隶属函数uλ(Ei,j)，并且归一化为偏差值，是本发明方法每一步迭代所需要计算的结果。对于任意一个给定的无人机交互信息拓扑都需要计算其多目标的总偏差。

在本发明中，当前迭代次数，记为λ。位于所述λ之前的迭代次数，记为λ-1；即前一次迭代。位于所述λ之后的迭代次数，记为λ+1；即后一次迭代。

在本发明中，当前食物源，记为Limitλ。在前一次迭代λ-1的食物源，记为Limitλ-1(即前次食物源)。在后一次迭代λ+1的食物源，记为Limitλ+1(即后次食物源)。

本发明的一种基于改进人工蜂算法的无人机编队拓扑生成优化方法，是运行于编队制导计算机上。编队制导计算机接收来自导航计算机的同一编队无人机机中进行的各个无人机交互信息，依据改进人工蜂算法进行的编队生成过程中的无人机交互信息拓扑的具体步骤为：

步骤一：构建无人机编队的二维邻接矩阵；

编队制导计算机依据无人机编队队形信息中的无人机个数来构造边连通图。在本发明中，两两无人机之间存在有一条双向的信息交互通道，所述信息交互通道称为边连通图的边，每一个无人机为边连通图的顶点。无人机编队队形一般包括有纵队、横队、楔形队、菱形队。

步骤11，构建无人机编队连通图；

依据无人机编队队形中的无人机个数建立的一个连通图，记为G＝(UAV,MV)，简称为无人机编队连通图。UAV表示作为连通图的顶点的无人机集，采用集合形式表示为UAV＝{uav1,uav2,…,uavi,…,uavj,…,uavn}；MV表示作为连通图的边的无人机之间的信息交互通道，即连接边集，采用集合形式表示为MV＝{v1,v2,…,vp,…,vq,…,vm}。

从无人机编队连通图G＝(UAV,MV)中获取无人机作为顶点的关联矩阵关系，称为无人机编队二维邻接矩阵，记为LL，且LL＝[Li,j]n×n。

Li,j为第i架无人机uavi与第j架无人机uavj之间的通信关联关系。

所述无人机集UAV＝{uav1,uav2,…,uavi,…,uavj,…,uavn}。

uav1表示编队无人机机中的第一架无人机。

uav2表示编队无人机机中的第二架无人机。

uavi表示编队无人机机中的第i架无人机。

uavj表示编队无人机机中的第j架无人机。

uavn表示编队无人机机中的最后一架无人机。下角标n表示一个编队无人机机中无人机的总数目。

为了方便说明，uavi、uavj和uavn为不同标识号的无人机。也就是说uavi、uavj和uavn不是同一架无人机。uavi也称为编队无人机机中的任意一架无人机；uavj也称为编队无人机机中的任意另一架无人机。

所述连接边集MV＝{v1,v2,…,vp,…,vq,…,vm}。

v1为无人机编队连通图的第一条边。

v2为无人机编队连通图的第二条边。

vp为无人机编队连通图的第p条边。

vq为无人机编队连通图的第q条边。

vm为无人机编队连通图的最后一条边。下角标m表示无人机编队连通图中边的总数目。

为了方便说明，vp、vq和vm为不同标识号的无人机之间的连接边。也就是说vp、vq和vm不是同一条边。vp也称为无人机编队连通图中任意一条边；vq也称为无人机编队连通图中任意另一条边。

步骤12，以完成通信得到无人机编队二维邻接矩阵；

在本发明中，任意两架无人机实现通信完成信息交互才能构得一条边。

在本发明中，无人机编队二维邻接矩阵LL＝[Li,j]n×n是与信息交互拓扑中的通信相对应的。若无人机uavi与无人机uavj存在有通信，则赋值为1；反之，若无人机uavi与无人机uavj不存在通信，则赋值为0。

步骤二：构建无人机编队通信链路的链长矩阵；

在本发明中，两两无人机之间进行的信息交互时的通信链路长度是一个相对通信距离(单位：m)数值。用表格示意为：

表1通信距离

步骤21，以完成通信得到无人机编队通信链路的链长矩阵；

在本发明中，编队制导计算机从导航计算机处获取各个无人机的通信有效范围，从而建立无人机编队通信链路的链长矩阵，记为CC，且CC＝[Ci,j]n×n。

Ci,j表示第i架无人机uavi与第j架无人机uavj之间通信链路的长度。

n表示一个编队无人机机中无人机的总数目。

在本发明中，Ci,j＝di,j×Li,j，di,j为第i架无人机uavi与第j架无人机uavj之间的通信距离，Li,j为无人机uavi与无人机uavj之间的通信关联关系。

步骤22，通信链路长度的隶属函数；

在本发明中，需要计算的通信链路长度的隶属函数，记为μλ(Ci,j)：

Cmax为当前迭代次数的最长链长。

Cmin为当前迭代次数的最小链长。

Cnew为当前迭代次数的链长。

在本发明中，对于通信链路长度的隶属函数μλ(Ci,j)中最小值为使用单纯考虑链长的生成算法的拓扑的链长。最大值为开始随机生成的初始解的链长。

步骤三：构建无人机编队组网后的平均网络延迟矩阵；

在本发明中，两两无人机之间进行的信息交互时的发生的网络延迟(单位：ms)。用表格示意为：

表2网络延迟

步骤31，无人机编队通信发生的平均网络延迟矩阵；

在本发明中，建立的无人机编队组网后的平均网络延迟矩阵，记为DD，且DD＝[Di,j]n×n。

Di,j表示第i架无人机uavi与第j架无人机uavj之间的平均网络延迟。

n表示一个编队无人机机中无人机的总数目。

在本发明中，Di,j＝hi,j×Li,j，hi,j为第i架无人机uavi与第j架无人机uavj之间的平均网络延迟，Li,j为无人机uavi与无人机uavj之间的通信关联关系。

步骤32，平均网络延迟的隶属函数；

在本发明中，需要计算的平均网络延迟的隶属函数，记为uλ(Di,j)：

Dmax为当前迭代次数的最大延迟。

Dmin为当前迭代次数的最小延迟。

Dnew为当前迭代次数的延迟。

在本发明中，对于最小延迟的计算，使所有的无人机子节点都连接到无人机根节点，忽略约束，然后利用uλ(Di,j)计算平均的网络延迟，以此作为最小的延迟。所述Dmax取随机产生的初始解的平均延迟。所述Dmin取领航无人机直接发送给其他无人机的平均延迟。满足当前的平均网络延迟记为Dnew。

在图3中A点处对应于Dmin，相应地B点处对应于Dmax。

步骤四：构建无人机编队组网后的平均剩余能量矩阵；

在本发明中，两两无人机之间进行的信息交互时的平均剩余能量(单位：百分比)。

表3剩余能量

步骤41，无人机编队通信发生的平均剩余能量矩阵；

在本发明中，建立的无人机编队组网后的平均剩余能量矩阵，记为EE，且EE＝[Ei,j]n×n。

Ei,j表示第i架无人机uavi与第j架无人机uavj之间的平均剩余能量。

n表示一个编队无人机机中无人机的总数目。

在本发明中，Ei,j＝ri,j×Li,j，ri,j为第i架无人机uavi与第j架无人机uavj之间的平均剩余能量，Li,j为无人机uavi与无人机uavj之间的通信关联关系。

步骤42，平均剩余能量的隶属函数；

在本发明中，需要计算的平均剩余能量的隶属函数，记为uλ(Ei,j)：

最大的平均剩余能量记为Emax。所述Emax取值为1。

最小的平均剩余能量记为Emin。所述Emin取值为0.1。所述Emin对应初始解的平均剩余能量。

当前的平均剩余能量记为Enew。

在图3中A点处对应于Emin，相应地B点处对应于Emax。

步骤五：计算总的蜜源偏差；

在本发明中，总的蜜源偏差值，记为fit(x)：

σ1为通信链路长度的权重。

σ2为平均网络延迟的权重。

σ3为平均剩余能量的权重。

fit(x)表示整个链接的偏差，偏差越小表明信息交互拓扑性能越好。

在本发明中针对不同的应用场景，可以调整各目标的权重，以实现更加突出对某一目标的重要性，即调整σ1,σ2,σ3的值。

步骤六：改进人工蜂算法参数初始化以及初始蜜源的建立；

在本发明中，初始化各个参数的设置依据12架无人机构成的菱形编队队形进行设置。又由于传统的人工蜂算法不适合本发明的编队队形的信息交互拓扑的多变化性，因此，在传统人工蜂算法上增加了“树型结构”，从而解决了由于能量分布不均易降低无人机信息交互拓扑多变，进而可能造成无人机编队发生碰撞的技术问题。

在本发明中，增加了“深度邻域搜索算子DSF”的人工蜂算法，称为改进人工蜂算法。

步骤61，初始化改进人工蜂算法各参数；

在本发明中，初始化无人机编队队形中的需要运行改进人工蜂算法的参数有：

设置无人机编队蜂规模，记为NP；例如NP＝12架；

设置最大循环迭代次数，记为λmax，且λmax＝120次；初始时迭代次数λ＝0；

设置作为雇佣蜂身份的无人机uav雇佣蜂对食物源Limit的搜索次数，记为LILimit。最大食物源搜索次数记为且

例如，作为非雇佣蜂身份的无人机有：非雇佣蜂身份的无人机uav非雇佣蜂会对食物源Limit进行深度邻域搜索DSF，在搜索次数内，没有搜索到蜜源偏差值fitλ(x)更小的拓扑的食物源，那么非雇佣蜂的无人机uav非雇佣蜂就会变为侦查蜂身份uav侦查蜂执行全局搜索。fitλ(x)为当前迭代的蜜源偏差值。

步骤62，生成多叉树树型结构的无人机信息交互；

在本发明中，采用多叉树树型结构对步骤一的无人机编队连通图G＝(UAV,MV)进行首次分层，得到首次无人机信息交互拓扑；所述首次无人机信息交互拓扑对应的是初始无人机食物源，记为Limit初始。

步骤63，生成无人机食物源；

继Limit初始之后，每一次无人机编队连通图G＝(UAV,MV)的变化，就有一个无人机信息交互拓扑，对应的也只有一个当前迭代的无人机食物源Limitλ。

在本发明中，将多叉树树型结构的无人机信息交互拓扑作为无人机食物源Limitλ，是为了等待着身份为雇佣蜂的无人机与身份为非雇佣蜂的无人机去搜索采蜜，这些最初的解是随机生成的。初始解须满足最基本的约束。基本约束包括依据通信协议，从源节点到目标节点的最大跳数不超过15，以及依据应用场景的不同，会指定一些约束例如某些节点必须是父节点或者子节点。

多叉树及树的节点表示是参考了严蔚敏，陈文博所著的《数据结构及应用算法教程》，第129－130页，2001年2月第1版。

步骤七：雇佣蜂无人机采用基于深度的领域搜索算子(DSF)在当前信息交互拓扑附近进行搜索，得到无人机食物源；

步骤71，计算蜜源偏差值；

在本发明中，依照每一次的信息交互拓扑结构，依据步骤二，三和四，执行步骤五，计算拓扑的当前迭代的蜜源偏差值fitλ(x)。

步骤72，计算适应度值；

在本发明中，作为雇佣蜂身份的无人机uav雇佣蜂在返回编队队形后，在信息交互拓扑展示区用摇摆舞通知编队队形内的身份为跟随蜂的无人机uav跟随蜂，在分享信息交互拓扑信息后，所述uav跟随蜂根据信息交互拓扑的适应度值Wλ，采用适应比例选择机制计算信息交互拓扑选择的概率，记为Pλ，则有：

Wλ为当前迭代的信息交互拓扑的适应度值。

Wmax表示食物源的最大适应度值。

步骤73，采用深度的领域搜索算子(DSF)搜索无人机食物源；

采用深度的邻域搜索算子DSF进行搜索当前迭代的无人机食物源Limitλ。

身份为雇佣蜂的无人机uav雇佣蜂在当前搜索次数上加1，即

步骤74，作为跟随蜂身份的无人机采用自适应比例选择策略在搜索的信息交互拓扑中进行选择，并变成雇佣峰身份的无人机，执行DSF；

身份为跟随蜂的无人机uav跟随蜂根据概率Pλ选择相应的信息交互拓扑，进而成为身份为雇佣蜂的无人机uav雇佣蜂，执行步骤71至步骤73。

身份为雇佣蜂的无人机uav雇佣蜂搜索次数递增1次。

步骤75，记录迭代次数；

判断身份为雇佣蜂的无人机uav雇佣蜂连续搜索次数LILimit是否大于最大搜索次数若不是，执行步骤71至步骤76，若是，则执行步骤八。

步骤八：作为侦察蜂身份的无人机采用全局随机搜索，完成寻新信息交互拓扑的任务；

身份为雇佣蜂的无人机uav雇佣蜂转变为身份为侦查蜂的无人机uav侦查蜂后，所述uav侦查蜂从无人机编队信息交互拓扑中选择一个信息交互拓扑，重复执行步骤一至步骤五，得到当前信息交互拓扑蜜源偏差值fitλ(x)。若蜜源偏差值fitλ(x)小于上一次的蜜源偏差值fitλ-1(x)，则替换上一次的信息交互拓扑，否则再次从无人机编队信息交互拓扑中选择一个信息交互拓扑，直至达到最大搜索次数执行步骤九。

步骤九：判断循环终止条件，输出最优信息交互拓扑

若迭代计算达到λmax，则停止计算，并且输出信息交互拓扑的位置，也就是最优的信息交互拓扑结构。

在本发明中，最后输出的信息交互拓扑的位置也是蜜源偏差最小的信息交互拓扑。

实施例1

在实施例1中，无人机菱形编队队形所需数据信息是采用JAVA语言开发，使用MySQL作为数据库支撑，仿真环境为Intellij IDEA(版本号2020.1)编译器。

参见图2所示由12架无人机组成的菱形编队队形，无人机的机间距离(表1)，平均网络延迟(表2)和平均剩余能量(表3)。

在实施例1中任意两架无人机之间均可建立无线通信，在本发明的网络拓扑中，相邻两架无人机之间的连接为通信链路，所述连接上的数字1表示存在连接，而数字0表示不存在通信链路。

在实施例1中，相邻两架无人机之间的距离称为机间通信距离。CC矩阵表示12架无人机之间的机间通信距离。EE矩阵表示12架无人机的机间平均剩余能量。DD表示12架无人机的机间网络延迟。

本发明的无人机编队的通信控制模式为领航跟随着，在无人机编队中，由一架无人机进行发送指令，直至所有无人机接收指令。

本实施例1的一种基于改进人工蜂算法的无人机编队多目标信息交互拓扑优化方法，是在已知无人机编队的机间通信距离，机间平均剩余能量和机间网络延迟的参数信息，具体的信息交互拓扑优化的处理。

步骤一：构建无人机编队的二维邻接矩阵；

编队制导计算机依据无人机编队队形信息中的无人机个数构建的无人机编队连通图G＝(UAV,MV)。从无人机编队连通图G＝(UAV,MV)中获取无人机之间的通信关联矩阵关系，称为无人机编队二维邻接矩阵，记为LL，表格示意出LL矩阵中各数值：

表四 邻接矩阵

步骤二：构建无人机编队通信链路的链长矩阵；

编队制导计算机从导航计算机处获取各个无人机的通信有效范围，从而建立无人机编队通信链路的链长矩阵，记为CC，表1中列举了CC矩阵的数值，结合通信链路长度的隶属函数μλ(Ci,j)，得到：

Cmax为当前迭代次数的最长链长，Cmax取值为6990。

Cmin为当前迭代次数的最短链长，Cmin取值为3750。

Cnew为当前迭代次数的链长，Cnew取值为6990。

计算得μλ(Ci,j)＝0

在本发明中，对于通信链路长度的隶属函数μλ(Ci,j)中最小值为使用单纯考虑链长的生成算法的拓扑的链长，取值为3750。最大值为开始随机生成的初始解的链长。

步骤三：构建无人机编队组网后的平均网络延迟矩阵；

编队制导计算机从导航计算机处获取各个无人机的网络延迟，从而建立的无人机编队组网后的平均网络延迟矩阵，记为DD，表2中列举了DD矩阵的数值，结合平均网络延迟的隶属函数uλ(Di,j)，得到：

Dmax为当前迭代次数的最大延迟，Dmax取值为0.4683。

Dmin为当前迭代次数的最小延迟，Dmin取值为0.25。

Dnew为当前迭代次数的延迟，Dnew取值为0.4683。

计算得uλ(Di,j)＝0；

步骤四：构建无人机编队组网后的平均剩余能量矩阵；

编队制导计算机从导航计算机处获取各个无人机的剩余能量，从而建立的无人机编队组网后的平均剩余能量矩阵，记为EE，表3中列举了EE矩阵的数值，结合平均剩余能量的隶属函数uλ(Ei,j)，得到：

最大的平均剩余能量记为Emax。所述Emax取值为1。

最小的平均剩余能量记为Emin。所述Emin取值为0.1。所述Emin对应初始解的平均剩余能量。

当前的平均剩余能量记为Enew，所述Enew取值为0.5892。

计算得uλ(Ei,j)＝0.5435；

步骤五：计算总的蜜源偏差；

在实施例1中，总的蜜源偏差值fit(x)＝1×1+1×1+1×0.3950＝2.4565。σ1,σ2,σ3均取值为1。

步骤六：改进人工蜂算法参数初始化以及初始蜜源的建立；

步骤61，初始化改进人工蜂算法各参数；

在本发明中，初始化无人机编队队形中的需要运行改进人工蜂算法的参数有：

设置无人机编队蜂规模，记为NP；例如NP＝12架；

设置最大循环迭代次数，记为λmax，且λmax＝120次；初始时迭代次数λ＝0；

设置作为雇佣蜂身份的无人机uav雇佣蜂对食物源Limit的搜索次数，记为LILimit。最大次数记为且

例如，作为非雇佣蜂身份的无人机有：非雇佣蜂身份的无人机uav非雇佣蜂会对食物源Limit进行深度邻域搜索DSF，在搜索次数没有搜索到蜜源偏差值fitλ(x)更小的拓扑的食物源，那么非雇佣蜂的无人机uav非雇佣蜂就会变为侦查蜂身份uav侦查蜂执行全局搜索。fitλ(x)为当前迭代的蜜源偏差值。

步骤62，生成多叉树树型结构的无人机信息交互；

在本发明中，采用多叉树树型结构对步骤一的无人机编队连通图G＝(UAV,MV)进行首次分层，得到首次无人机信息交互拓扑；所述首次无人机信息交互拓扑对应的是初始无人机食物源，记为Limit初始，Limit初始用表格表示为。

表5初始食物源1

表6初始食物源2

表7初始食物源3

表8初始食物源4

表9初始食物源5

表10初始食物源6

表11初始食物源7

表12初始食物源8

表13初始食物源9

表14初始食物源10

表15初始食物源11

表16初始食物源12

步骤63，生成无人机食物源；

继Limit初始之后，每一次无人机编队连通图G＝(UAV,MV)的变化，就有一个无人机信息交互拓扑，从Limit初始中抽取一个信息交互拓扑构成一个无人机食物源Limit1。对应的也只有一个当前迭代的无人机食物源Limit0，Limit0用表格示意为。

表17第一次迭代初始食物源

步骤七：雇佣蜂无人机采用基于深度的领域搜索算子(DSF)在当前信息交互拓扑附近进行搜索，得到无人机食物源；

步骤71，计算第一次蜜源偏差值；

在本发明中，依照初始的信息交互拓扑结构，依据步骤二，三和四，执行步骤五，计算拓扑的当前迭代的蜜源偏差值，第一次蜜源偏差值为2.4565。

步骤72，计算第一次适应度值；

在本发明中，作为雇佣蜂身份的无人机uav雇佣蜂在返回编队队形后，在信息交互拓扑展示区用摇摆舞通知编队队形内的身份为跟随蜂的无人机uav跟随蜂，在分享信息交互拓扑信息后，所述uav跟随蜂根据信息交互拓扑的适应度值W1，采用适应比例选择机制计算信息交互拓扑选择的概率，记为

W1为当前迭代的信息交互拓扑的适应度值。

Wmax表示初始食物源中计算的最大适应度值，取值为2.5646

步骤73，采用深度的领域搜索算子(DSF)搜索无人机食物源；

采用深度的邻域搜索算子DSF进行搜索当前迭代的无人机食物源Limit1。

依据多叉树树型结构将12架无人机按照菱形编队队形分为七层，分别是：首层α中有1架无人机第二层β中有2架无人机第三层χ中有2架无人机第四层γ中有4架无人机第五层θ中有1架无人机第六层ζ中有1架无人机尾层δ中有1架无人机

将第四层γ中的4架无人机的位置进行排序交换，得到排序后的第四层γ的无人机这就重新生成了无人机的信息交互拓扑结构了。

然后将排序后的第四层γ的作为第五层θ中的的父节点；

其余树型结构的无人机位置保持不变；修改后无人机编队是以邻接表的形式，然后将临界表转化为邻接矩阵，从而构建得到当前的无人机信息交互拓扑；用表格表示为

表18 DSF后食物源Limit1

身份为雇佣蜂的无人机uav雇佣蜂搜索次数为0+1＝1。

步骤74，作为跟随蜂身份的无人机采用自适应比例选择策略在搜索的信息交互拓扑中进行选择，并变成雇佣峰身份的无人机，执行DSF；

身份为跟随蜂的无人机uav跟随蜂根据概率P1＝0.9621选择相应的信息交互拓扑，因为P1＝0.9621＜0.97进而成为身份为雇佣蜂的无人机uav雇佣蜂，执行步骤71至步骤73。

步骤75，计算第二次蜜源偏差值；

在本发明中，依照第一次的信息交互拓扑结构，依据步骤二，三和四，执行步骤五，计算拓扑的当前迭代的蜜源偏差值，第二次蜜源偏差值为2.3247。

步骤76，计算第二次适应度值；

在本发明中，作为雇佣蜂身份的无人机uav雇佣蜂在返回编队队形后，在信息交互拓扑展示区用摇摆舞通知编队队形内的身份为跟随蜂的无人机uav跟随蜂，在分享信息交互拓扑信息后，所述uav跟随蜂根据信息交互拓扑的适应度值Wλ，采用适应比例选择机制计算信息交互拓扑选择的概率，记为

Wλ为当前迭代的信息交互拓扑的适应度值。

Wmax表示初始食物源中计算的最大适应度值，取值为2.5646

步骤77，采用深度的领域搜索算子(DSF)搜索无人机食物源；

采用深度的邻域搜索算子DSF进行搜索当前迭代的无人机食物源Limit2。

依据多叉树树型结构将12架无人机按照菱形编队队形分为七层，分别是：首层α中有1架无人机第二层β中有2架无人机第三层χ中有2架无人机第四层γ中有4架无人机第五层θ中有1架无人机第六层ζ中有1架无人机尾层δ中有1架无人机

将第四层γ中的4架无人机的位置进行排序交换，得到排序后的第四层γ的无人机这就重新生成了无人机的信息交互拓扑结构了。

然后将排序后的第四层γ的作为第五层θ中的的父节点；

其余树型结构的无人机位置保持不变；修改后无人机编队是以邻接表的形式，然后将临界表转化为邻接矩阵，从而构建得到当前的无人机信息交互拓扑；用表格表示为

表19 DSF后食物源Limit2

身份为雇佣蜂的无人机uav雇佣蜂搜索次数为1+1＝2。

步骤78，记录迭代次数；

身份为雇佣蜂的无人机uav雇佣蜂连续搜索次数LILimit＝2小于最大搜索次数执行步骤71至步骤76。

同样参考步骤71到步骤76，直到身份为雇佣蜂的无人机uav雇佣蜂连续搜索次数LILimit大于最大搜索次数执行步骤八。

步骤八：作为侦察蜂身份的无人机采用全局随机搜索，完成寻新信息交互拓扑的任务；

身份为雇佣蜂的无人机uav雇佣蜂转变为身份为侦查蜂的无人机uav侦查蜂后，所述uav侦查蜂从无人机编队信息交互拓扑中选择一个信息交互拓扑，用表格表示

表20侦察蜂从初始食物源抽取的食物源Limit120

重复执行步骤一至步骤五，得到当前信息交互拓扑蜜源偏差值fit120(x)＝2.3950。蜜源偏差值fit120(x)大于上一次的蜜源偏差值fit119(x)＝0.6798，并且达到最大搜索次数执行步骤九。

步骤九：判断循环终止条件，输出最优信息交互拓扑

若迭代计算达到λmax，则停止计算，并且输出信息交互拓扑的位置，也就是最优的信息交互拓扑结构。用表格表示

表21最优信息交互拓扑

Uav₁ Uav₂ Uav₃ Uav₄ Uav₅ Uav₆ Uav₇ Uav₈ Uav₉ Uav₁₀ Uav₁₁ Uav₁₂ Uav₁ 0 1 0 0 0 1 1 0 0 0 0 0 Uav₂ 1 0 1 0 0 0 0 0 0 0 0 1 Uav₃ 0 1 0 1 0 0 0 0 0 0 0 0 Uav₄ 0 0 1 0 0 0 0 0 0 1 0 0 Uav₅ 0 0 0 0 0 1 0 0 0 0 1 0 Uav₆ 1 0 0 0 1 0 0 0 0 0 0 0 Uav₇ 1 0 0 0 0 0 0 1 0 0 0 0 Uav₈ 0 0 0 0 0 0 1 0 1 0 0 0 Uav₉ 0 0 0 0 0 0 0 1 0 0 0 0 Uav₁₀ 0 0 0 1 0 0 0 0 0 0 0 0 Uav₁₁ 0 0 0 0 1 0 0 0 0 0 0 0 Uav₁₂ 0 1 0 0 0 0 0 0 0 0 0 0

在本发明中，最后输出的信息交互拓扑的位置也是蜜源偏差最小的信息交互拓扑。对应的无人机信息交互拓扑图，如图5所示。

图5中依据多叉树树型结构将12架无人机按照菱形编队队形分为七层，分别是：首层α中有1架无人机第二层β中有2架无人机第三层χ中有2架无人机第四层γ中有4架无人机第五层θ中有1架无人机第六层ζ中有1架无人机尾层δ中有1架无人机

表示位于首层的第一架无人机。

表示位于第二层的第一架无人机。

表示位于第二层的第二架无人机。

表示位于第三层的第一架无人机。

表示位于第三层的第二架无人机。

表示位于第三层的第三架无人机。

表示位于第三层的第四架无人机。

表示位于第四层的第一架无人机。

表示位于第四层的第二架无人机。

表示位于第四层的第三架无人机。

表示位于第四层的第四架无人机。

表示位于第五层的第一架无人机。

表示位于第六层的第一架无人机。

表示位于尾层的第一架无人机。

如果将第三层χ中的2架无人机的位置进行排序交换，得到排序后的第三层χ的无人机这就重新生成了无人机的信息交互拓扑结构了。

然后将排序后的第三层χ的作为第四层γ中的的父节点；

其余树型结构的无人机位置保持不变；修改后无人机编队是以邻接表的形式，然后将临界表转化为邻接矩阵，从而构建得到当前的无人机信息交互拓扑。