基于粒子群的无人机蜂群网络拓扑快速构建方法.pdf

基于粒子群的无人机蜂群网络拓扑快速构建方法周睿1,2，张翔引1,2*，宋德宇1,2，秦开宇1,2，徐利梅1(1.电子科技大学航空航天学院成都611731；2.飞行器集群智能感知与协同控制四川省重点实验室成都611731)【摘要】高稳定性的网络拓扑是无人机蜂群系统分布式联合感知、分布式信息交互与分布式协同控制等集群功能的重要保障。在三维动态应用场景中，快速稳定的网络拓扑构建对于蜂群系统的可靠应用具有重要意义，而当前的拓扑构建方法在此方面研究并不充分。提出了一种基于粒子群优化算法(PSO)的无人机蜂群分布式拓扑快速构建方法，在满足蜂群网络特定的端到端通信时延性能要求下，最大化网络拓扑的维持时间。为实现分布式拓扑构建方法的快速收敛，根据蜂群节点的静态特性和动态趋势进行初值设计，同时基于特征相似度函数优化更新方向与步长。仿真结果表明，在典型应用场景和系统配置下，该方法具有高拓扑稳定性。在蜂群规模为 100 节点时，传统 PSO 策略需要平均 5.5 次迭代才能获得最优解，而该算法在获得相同端到端时延和网络吞吐性能的同时，平均只需 2 次迭代即可收敛到全局最优解。关键词分布式；拓扑快速构建；粒子群算法；拓扑稳定性；无人机蜂群系统中图分类号TN915;V27文献标志码Adoi:10.12178/1001-0548.2023112FastConstructionMethodofDistributedTopologyforUAVSwarmNetworkZHOURui1,2,ZHANGXiangyin1,2*,SONGDeyu1,2,QINKaiyu1,2,andXULimei1(1.SchoolofAeronauticsandAstronautics,UniversityofElectronicScienceandTechnologyofChinaChengdu611731;2.AircraftSwarmIntelligentSensingandCooperativeControlKeyLaboratoryofSichuanProvinceChengdu611731)AbstractAhighlystablenetworktopologyisanimportantguaranteeforthecollaborativefunctionsoftheUnmannedAerialVehicle(UAV)swarmsystem,includingthedistributedjointsensing,distributedinformationinteraction and distributed cooperative control.In 3D dynamic application scenarios,fast and stable networktopologyconstructioniscrucialforreliableapplicationsofswarmsystems,andcurrenttopologyconstructionmethodsarenotsufficientlystudiedinthisaspect.Inthispaper,afastdistributedtopologyconstructionmethodforUAVswarmsystemisproposed,themethodisbasedonaParticleSwarmOptimization(PSO)algorithmthatmaximizes the duration of network topology under the specific end-to-end communication delay performancerequirement.Toachievefastconvergenceofthedistributedtopologyconstructionmethod,theinitialvaluesaredesignedaccordingtothestaticcharacteristicsanddynamictrendsoftheswarmnodes,whiletheupdatedirectionandstepsizeareoptimizedbasedonthefeaturesimilarityfunction.Thesimulationresultsshowthattheproposedmethodoftopologyconstructionhashighstabilityundertypicalapplicationscenariosandsystemconfigurations.With100nodes,thetraditionalPSOstrategyrequiresanaverageof5.5iterationstoobtaintheoptimalsolution,whiletheproposedalgorithmconvergestotheglobaloptimalsolutioninanaverageof2iterationsobtainingthesameend-to-enddelayandnetworkthroughputperformance.Keywordsdistributed;fasttopologyconstruction;PSO;topologystability;UAVswarmsystems分布式协同技术的快速发展，使无人机蜂群系统在多个领域得到广泛应用1-4，相较于单无人机平台，蜂群系统具备巨大的系统优势与发展潜力。在无人机蜂群系统中，蜂群网络用于实现各无人机节点间的测量、感知和控制等信息的交互，因此其网络拓扑的稳定性是影响蜂群系统能力的重要因素。网络拓扑的稳定性可以用网络拓扑的维持时间来衡量，即网络拓扑从构建完成到下一次重构之间的时收稿日期：20230417；修回日期：20230529基金项目：部级基金(61403120404)作者简介：周睿(1987)，男，博士生，主要从事无人机网络通信、集群智能等方面的研究.*通信作者：张翔引，E-mail：第52卷第4期电子科技大学学报Vol.52No.42023 年 7 月JournalofUniversityofElectronicScienceandTechnologyofChinaJul.2023间间隔。随着应用场景的不同，蜂群网络具备不同的无人机节点数量部署与使用要求，带来了不同网络的拓扑设计需求。从节点交互与控制关系角度，蜂群网络拓扑形式可以划分为分簇式5-7与分布式8-11两种。分簇式拓扑5-7将网络节点划分为骨干节点与普通节点两种类型，普通节点通过其隶属的骨干节点进行对外通信。当前针对无人机的蜂群网络拓扑构建方法多以分簇式为主12-13。主要从优化无人机节点能耗14或蜂群网络的某一特定通信性能进行设计15，并未充分考虑高动态场景下的最大拓扑维持时间的设计。然而，最大拓扑维持时间的建模与优化是蜂群系统在高动态场景下使用时亟需考虑的问题。同时，对于无人机蜂群系统，还存在各无人机节点不依赖于骨干节点进行协同工作的典型应用模式。该种工作模式中，各无人机进行无中心的协同控制与协同信息交互，系统具备较高的鲁棒性与抗毁性，同时也要求相应分布式网络拓扑构建方法8-11与之适配。分布式拓扑虽然具备较高的鲁棒性与抗毁性等优势，但也同样由于其无中心的拓扑特质，导致其拓扑构建速度较慢。在拓扑构建目标模型的基础上，如何高效完成模型求解从而快速实现网络拓扑构建，对于蜂群系统实际应用具有重要意义。针对以上问题，本文提出了一种基于粒子群优化算法(particleswarmoptimization,PSO)的无人机蜂群分布式拓扑快速构建方法。首先，在给出蜂群系统模型的基础上，将蜂群网络分布式拓扑构建问题建模为在保证系统特定端到端时延要求的条件下，最大化网络拓扑维持时间的问题。接着，采用了 PSO 算法对所提模型进行求解。为了克服 PSO算法收敛性慢的问题，设计与无人机节点间位置信息与运动状态等物理特征关联的相似度函数以进行 PSO 初值设定，同时基于特征相似度函数建立对 PSO 的方向与步长迭代的更新算法。最后，完成适配于无人机蜂群系统典型应用场景的分布式拓扑快速构建。仿真结果证明了所提蜂群网络拓扑构建方法的有效性，在网络规模为 100 节点的蜂群网络下，传统的 PSO 群智能求解算法需要平均 5 次以上的迭代才能收敛到最优解，而本文算法平均迭代次数不大于 2 次。1系统模型U(t)=u1(t),u2(t),uN(t)T RN3ui(t)=xi,yi,zi,i=1,2,ND(t)=dij(t)NN RNNdij(t)考虑由分布在三维欧式空间的N个同质无人机节点组成无人机蜂群系统，令表示无人机蜂群节点的位置矩阵，其中第i个节点的位置信息为。无人机节点间的距离矩阵可以表示为，其中为无人机节点i与节点j间的欧式距离，计算公式如下：dij(t)=(xixj)2+(yiyj)2+(zizj)2(1)Rdij R令 为无人机节点的最大通信距离，若，则节点i与节点j间具备通信连通能力。Eo(t)=eoij(t)NN RNNeoijeoij=0eoij=1Go(t)定义为设计的网络拓扑中节点连接关系矩阵，其中表示拓扑中节点i与节点j的连通关系：表示节点i与节点j不连通；表示节点i与节点j连通。将设计的网络拓扑表示为时变函数，即：Go(t)=(U(t),Eo(t)(2)Go(t)需保证拓扑内任意两节点间可通过单跳或多跳传输实现通信连通。蜂群网络分布式拓扑设计示意图如图 1所示。ZYX无人机节点无人机机间连接无人机速度矢量图1无人机蜂群网络分布式拓扑示意图一般情况下，蜂群网络中无人机节点通过视距链路信道进行无线通信，节点间的端到端数据传输通过单跳或多跳方式完成。端到端传输时延主要由无线传输时延、多跳转发时延以及信号处理时延组成。在蜂群网络中，多跳转发时延对端到端时延有着决定性影响，并与网络拓扑的构建状态相关。Go(t)本文的求解目标是在满足蜂群网络特定端到端通信时延前提下，求得最优拓扑，使得网络拓扑维持时间最长，因此可将网络拓扑构建问题描述为：第 4 期周睿，等：基于粒子群的无人机蜂群网络拓扑快速构建方法507arg max T(Go(t)(3a)Go(t)中任意节点i,j连通(3b)ij thi,j且i,j 1,N(3c)T()ijth在式(3a)对应的目标函数中，定义为拓扑维持时间运算符。式(3b)对网络连通性进行了约束，即保证拓扑内的任意两个节点可通过单跳或多跳实现通信连通。式(3c)对蜂群网络的端到端时延进行了约束，其中表示网络中任意两节点间的端到端时延，对应端到端时延门限，N为蜂群系统节点数量。2分布式拓扑快速构建方法PSO16是一种应用广泛的典型群体智能优化算法。该算法中，问题的解由粒子代表，多个粒子构成了种群。其运行思路是在各粒子初始化状态的基础上，将单个粒子的个体最优解寻优与粒子种群的全局最优解寻优进行综合，不断调整各粒子的迭代方向与步长，最终得到求解结果。Go(t)根据式(3)，把拓扑构建分解为 3 个步骤：1)判断拓扑的节点连通性；2)在满足第 1)步连通性要求的前提下，判断节点间端到端时延是否满足要求；3)综合满足上述各约束后，求出拓扑维持时间。各步骤简述如下。1)拓扑连通性判断Eo(t)该步骤中，对于选定的拓扑，首先建立节点连接关系矩阵，并采用 Warshall 算法17对关系矩阵进行解算，通过解算结果判断拓扑中的节点是否都已连通。2)端到端时延计算计算网络拓扑中各节点间的端到端时延，并将各端到端时延值与时延门限进行对比，判断是否满足式(3c)对应的指标要求。3)拓扑维持时间满足上述各步的约束条件后，计算拓扑维持时间，即将拓扑构建完成记为初始时刻，若某一时刻对应式(3b)(3c)中的任一约束条件不满足，则认为本次拓扑维持终止。通过初始与终止时刻，求得拓扑维持时间。基于 PSO 的分布式拓扑构建流程图如图 2 所示。传统 PSO 算法在蜂群网络拓扑构建中，收敛速度较慢，尤其是在蜂群网络节点数较多时。因此，在此拓扑构建流程的基础上，需对 PSO 算法的收敛速度进行优化，图 2 虚线框内为收敛速度优化步骤，主要包括粒子群初始值优化、迭代方向与步长优化等内容。初始化 PSO 算法参数节点 全连通？开始输入拓扑构建基本参数（算法最大迭代次数 iter，无人机节点数 N，节点运动参数与初始位置，时延约束门限）根据初始网络节点信息及 PSO 算法参数，更新每个粒子初始值对于每个粒子 i，i=1,2,.,H计算拓扑维持时间更新 PSO 粒子速度值与位置值计算拓扑连通性计算端到端时延计算拓扑维持时间满足时延要求？更新网络拓扑记录所有粒子各自的最优值，得到种群最优值满足迭代 结束条件？得到最优网络拓扑结束拓扑维持时间置为 0更新拓扑维持时间否否是是是否构建速度优化步骤图2基于 PSO 的分布式拓扑构建流程图构建速度优化的具体内容如下。1)粒子群初始值优化基于 PSO 的快速拓扑构建方法中，每个粒子代表一种网络拓扑连通状态，简化为网络拓扑中的上三角邻接矩阵：A=0A12A1N00.0A(N1)N000NN(4)Aij式中，表示节点间连通状态，即：Aij=1i与j连通0i与j不连通(5)ijsimijsim_pijsim_vij若能在粒子群生成阶段使得每个粒子所代表的拓扑状态更靠近最优解，需使粒子初值所代表的拓扑连通状态中连通的两节点间的位置尽可能靠近，速度尽可能相似。因此，PSO 算法中的粒子初值根据节点间特征相似度生成，节点、的特征相似度函数可表示为，其由节点位置相似度与节点速度相似度加权求得，即：simij=1sim_pij+2sim_vij(6)12式中，、为经验值常数。508电子科技大学学报第52卷sim_pijsim_vij与计算方式如下：sim_pij=1dij Rek(dijR)dij R(7)sim_vij=e(vij(t)2(8)vij(t)=?vi(t)vj(t)?2(9)k式中，、为相似度敏感系数。simijAij接着，将特征相似度数值等价转化为节点间的连通概率，对式(5)中节点连通状态元素进行取值，即：PAij=1=simij(10)可以看出，两节点的位置状态与速度状态越相似，在粒子群初始化时，这两个节点连通的可能性越大。至此，基于 PSO 算法的快速拓扑构建方法中的粒子初始值优化过程完成。基于节点间特征相似度生成的粒子群初始值可以使得每个粒子所代表的连通状态在物理上更接近最优解。2)迭代方向与步长优化1，0，1pop_xpop_vgbestpbest在步骤 1)中所生成的粒子群初值基础上，对粒子群迭代过程中的速度(迭代方向与步长)进行优化。由于每个粒子的数学呈现方式为以 0 或 1 构成的上三角邻接矩阵，粒子的迭代方向与步长只能为构成的上三角矩阵。其中1 表示两节点间连通状态从连通变为不连通；0 表示两节点间连通状态在此次迭代中保持不变；1 表示两节点间连通状态从不连通变为连通。定义粒子当前状态为，粒子的迭代方向与步长为，当前全局最优值为，个体历史最优值为。pop_vgbestpbestpop_xgbestpbestpop_xgbestpbestpop_vpop_v在的计算过程中，本文希望粒子以一种更加合理的方式向与的方向靠拢，算法设计目标如下：1)中连通的两节点间的特征相似度越大，这两个节点越倾向于保持互相连通，即使或中这两个节点间是不连通的；2)中连通的两节点间的特征相似度越小，这两个节点越倾向于断开连接，即使或中这两个节点间是连通的。再次引入式(6)中的节点特征相似度函数值，并对进行计算，中元素的计算方法如下：pop_vij=pop_vij+c1simijg+c2simijp(11a)pop_vij+c1(1simij)g+c2(1simij)p(11b)pop_vij+c1simijg+c2simijp(11c)g=gbestijpop_xij(11d)p=pbestijpop_xij(11e)g=1p=1g=1p=1c1c2pop_v式中，若且，则使用式(11a)进行计算；若且，则使用式(11b)进行计算；其他情况下，使用式(11c)进行计算。其中，为惯性权重，、分别为全局优化与个体优化对应的学习因子。由此得到粒子迭代方向与步长矩阵，该矩阵同样为上三角矩阵。则粒子下一次迭代后状态为：pop_x(t+1)=pop_x(t)+pop_v(t+1)(12)至此，基于 PSO 的拓扑快速构建方法中的迭代方向与步长优化完成。粒子群所求得的最优解所代表的拓扑中，只有连通的节点间都具有相对较高的特征相似度，才能保证拓扑维持时间尽可能长。由于在迭代方向与步长优化算法中引入了节点特征相似度，避免了相似节点在迭代过程中断开连接，以及不相似的节点在迭代过程中重新连通，达到了校正粒子迭代方向的效果。通过此算法，粒子群可以用更快的收敛速度向最优解迭代逼近。在上述优化基础上，建立基于 PSO 的快速拓扑构建方法如下。算法 1基于 PSO 的分布式拓扑快速构建方法th1,2iterk输入：蜂群节点初始状态信息，时延约束门限，经验参数，迭代次数，粒子数Go(t)T(Go(t)输出：最优拓扑及拓扑维持时间simij使用式(6)式(9)，完成各节点间特征相似度值计算使用式(10)计算节点间连通概率值pop_xpop_v初始化各粒子状态，每个粒子代表一个网络拓扑连通状态，如式(4)，初始化各粒子初始速度pbestgbest获得初始最优拓扑及拓扑维持时间、各粒子个体历史最优值、粒子种群全局最优值t thTi计算第 个粒子对应拓扑的最大端到端时延，若，则该粒子拓扑维持时间 值为0iTi若连通性和端到端时延均满足约束，计算第 个粒子拓扑维持时间end第 4 期周睿，等：基于粒子群的无人机蜂群网络拓扑快速构建方法509更新最优拓扑及拓扑维持时间pbest更新各粒子个体历史最优值gbest更新粒子种群全局最优值t=t+1endGo(t)T(Go(t)return，3仿真与结果分析通过 MATLAB 对提出的无人机蜂群分布式拓扑快速构建方法进行验证。选用 Boids 模型18作为蜂群节点的运动模型，主要仿真参数设置如表 1所示。表 1仿真参数设置仿真参数仿真参数参数值参数值节点数量20,40,60,80,100节点有效通信距离/m50节点速度/ms11020节点位置更新间隔/s1运动模型boids1,2经验参数()0.7,0.3PSO粒子数量100,c1,c2PSO学习因子()0.8,0.5,0.5基于表 1，将设计的分布式拓扑快速构建算法与传统 PSO 算法进行对比，对比项包括拓扑维持时间、算法收敛速度、平均端到端时延及网络总吞吐量。图 3 为本文方法运行后得到的网络拓扑图，从图中可以看到，分布式拓扑快速构建方法有效优化了节点间的连接关系，对于蜂群网络系统运行所需的维护开销与节点通信能耗减少均有较好的帮助。图 4 为两种拓扑构建算法的网络拓扑维持时间仿真对比情况，可以看出，随着无人机节点数的增加，两种算法得到的拓扑维持时间均呈下降趋势。同时，本文算法与传统 PSO 算法相比，拓扑维持时间基本相同。图 5 为两种拓扑构建算法的迭代次数对比，从图中可以看出，随着无人机节点数的增加，两种算法收敛所需迭代次数逐步上升，但本文算法对应收敛速度受无人机节点增加的影响较小。同时，本文算法在节点数为 100 时获得全局最优解的平均迭代次数不超过 2 次，远优于传统 PSO 算法的 5.5 次。可以预见，随着无人机节点数量的进一步增加，所提算法可以具备更大的收敛速度优势。5050500005050 50ZYX图3所提算法得到的网络拓扑图204060节点数量801000102030405060708090100110120拓扑维持时间/sPSO改进的 PSO图4拓扑维持时间对比204060节点数量801000123456迭代次数/次PSO改进的 PSO图5算法迭代次数对比图 6 和图 7 分别为两种算法的平均端到端时延与网络总吞吐量仿真对比。随着无人机节点数的增加，两种算法得到的网络端到端时延均增大，同时两种算法得到的网络端到端时延值基本一致。对于网络总吞吐量，两种算法得到的指标也基本一致，并随着无人机节点数的增加而下降。综合上述各仿真结果可以看出，本文算法可以在不降低网络拓扑维持时间、平均端到端时延及网络总吞吐量等网络性能的基础上，有效降低算法收敛所需迭代次数。考虑到本文算法与传统 PSO 策略在每次迭代中的计算量相同，可将迭代次数转化为总收敛速度，即无人机节点数量为 100 时，本文510电子科技大学学报第52卷算法的收敛速度是传统 PSO 算法的约 2.75 倍。200510152025304060节点数量平均端到端时延/ms80100PSO改进的 PSO图6平均端到端时延对比2001020304050607080901004060节点数量网络总吞吐量/Mbps80100PSO改进的 PSO图7网络总吞吐量对比4结束语本文针对无人机蜂群网络应用需求，提出了一种分布式拓扑快速构建方法。该方法针对蜂群系统典型应用场景，在分布式拓扑形式的基础上，以最长拓扑维持时间为模型优化目标，充分考虑蜂群网络端到端时延要求，对 PSO 算法进行了求解速度优化，建立了基于 PSO 的拓扑快速构建方法。仿真结果表明，本文方法满足中等规模节点的使用需求，与传统 PSO 算法相比，在拓扑维持时间、通信性能基本相当的前提下，拓扑构建速度得到了显著提升。参考文献1ZENGY,ZHANGR,LIMTJ.Wirelesscommunicationswithunmannedaerialvehicles:OpportunitiesandchallengesJ.IEEE Communications Magazine,2016,54(5):36-42.2ALAM M M,ARAFAT M Y,MOH S,et al.Topologycontrol algorithms in multi-unmanned aerial vehiclenetworks:AnextensivesurveyJ.JournalofNetworkandComputerApplications,2022,207:103495.3SIDDIQUI A B,AQEEL I,ALKHAYYAT A,et al.Prioritized user association for sum-rate maximization inuav-assisted emergency communication:A reinforcementlearningapproachJ.Drones,2022,6(2):45.4ASLAN M F,DURDU A,SABANCI K,et al.AcomprehensivesurveyoftherecentstudieswithUAVforprecision agriculture in open fields and greenhousesJ.AppliedSciences,2022,12(3):1047.5LIN C R,GERLA M.Adaptive clustering for mobilewireless networksJ.IEEE Journal on Selected Areas inCommunications,1997,15(7):1265-1275.6SASIKUMAR P,KHARA S.K-Means clustering inwirelesssensornetworksC/20124thInternationalConferenceonComputationalIntelligenceandCommunicationNetworks.Mathura:IEEE,2012:140-144.7AFTAB F,KHAN A,ZHANG Z.Hybrid self-organizedclustering scheme for drone based cognitive Internet ofThingsJ.IEEEAccess,2019,7:56217-56227.8路纲,周明天,牛新征,等.无线网络邻近图综述J.计算机学报,2015,38(3):625-647.LUG,ZHOUMT,NIUXZ,etal.Asurveyofproximitygraphs in wireless networksJ.Chinese Journal ofComputers,2015,38(3):625-647.9LIN,HOUJC.FLSS:Afault-toleranttopologycontrolalgorithmforwirelessnetworksC/Proceedingsofthe10thAnnualInternationalConferenceonMobileComputingandNetworking.NewYork:ACM,2004:275-286.10SHENY,CAIY,XUX.Ashortest-path-basedtopologycontrolalgorithminwirelessmultihopnetworksJ.ACMSIGCOMM Computer Communication Review,2007,37(5):29-38.11LIN,HOUJC,SHAL.DesignandanalysisofanMST-basedtopologycontrolalgorithmJ.IEEETransactionsonWirelessCommunications,2005,4(3):1195-1206.12ARAFAT M Y,MOH S.Localization and clusteringbased on swarm intelligence in UAV networks foremergency communicationsJ.IEEE Internet of ThingsJournal,2019,6(5):8958-8976.13Al-ABOODY N A,Al-RAWESHIDY H S.Grey wolfoptimization-based energy-efficient routing protocol forheterogeneous wireless sensor networksC/2016 4thInternationalSymposiumonComputationalandBusinessIntelligence.Olten:IEEE,2016:101-107.14AADILF,RAZAA,KHANMF,etal.Energyawarecluster-based routing in flying Ad-hoc networksJ.Sensors,2018,18(5):1413.15XING N,ZONG Q,DOU L,et al.A game theoreticapproachformobilitypredictionclusteringinunmannedaerialvehiclenetworksJ.IEEETransactionsonVehicularTechnology,2019,68(10):9963-9973.16KENNEDYJ,EBERHARTR.ParticleswarmoptimizationC/Proceedings of ICNN95 InternationalConferenceonNeuralNetworks.Perth:IEEE,1995:1942-1948.17WARSHALL S.A theorem on boolean matricesJ.JournaloftheACM,1962,9(1):11-12.18REYNOLDS C W.Flocks,herds and schools:AdistributedbehavioralmodelC/Proceedingsofthe14thAnnualConferenceonComputerGraphicsandInteractiveTechniques.Anaheim:ACM,1987:25-34.编辑刘飞阳第 4 期周睿，等：基于粒子群的无人机蜂群网络拓扑快速构建方法511