1、http:/DOI:10.13700/j.bh.1001-5965.2021.0486考虑任务分配的无人机信息交互拓扑生成薛莹1，何锋1，*，谷晓燕2(1.北京航空航天大学电子信息工程学院，北京100191；2.北京信息科技大学信息管理学院，北京100096)摘要：无人机（UAV）持久编队信息交互拓扑的优化是保证 UAV 编队结构稳定性和任务执行时效性的重要基础。现有的编队生成算法针对距离因素进行权重赋值和拓扑生成，由于未考虑任务分配因素，可能会引起整体任务执行时间过长甚至任务失败的问题，对 UAV 的能量也造成了不必要的损耗。以任务消息传输时间和能量损耗为关键优化目标，在保证 UAV 编队结
2、构稳定的前提下，提出考虑任务分配因素的信息交互拓扑生成算法，优先连接承载实时性要求较高通信任务的关键汇聚链路，对剩余链路通过引入惩罚项，在权重上进一步将任务消息传输量因素考虑在内，生成最终的信息交互拓扑。使用 OMNet+进行仿真验证，相比于只考虑距离因素的信息交互拓扑生成算法，所提算法在 20 架 UAVs 编队场景下，消息传输时间方面最高降低 57.3%，最低降低28.1%，关键任务消息的到达时延降低了 45.2%51.6%，而任务执行过程单 UAV 的能量损耗总体减少了 17.5%，平均每个节点减少损耗 16.1%。关键词：无人机编队；任务分配；信息交互拓扑；刚性矩阵；最优持久图中图分类
3、号：V243.1；N945.15文献标志码：A文章编号：1001-5965（2023）07-1787-09无人机（unmannedaerialvehicle，UAV）与无人机相关技术在近年来的发展越发热门和成熟，其中无人机编队进行任务执行是最值得研究的内容，例如民用领域的消防、救灾等1或军用领域的目标跟踪2、目标打击3等。无人机群在保持编队飞行或进行任务执行的过程中，不管是位置的发送反馈还是任务相关消息的传递，无人机单体之间都需要保持信息交互，建立通信链路。通常，这种通信链接的集合被称为编队的信息交互拓扑4或通信拓扑5。密集的通信链接有时并不必要，保持所有链路的连接需要消耗大量能量，这将会大大
4、影响无人机群的续航与任务的执行。因此，无人机之间信息的交互拓扑可以相对简化，成为编队通信网络拓扑中的一个子集6。无人机群编队作战的过程中，除了拓扑编队消息的传递，还需进行任务相关消息的传输，对于前者，使用“拓扑消息”指代，而后者则使用“任务消息”。如果在生成信息交互拓扑时能够考虑任务消息的传递，在任务消息传输时利用这些链路，那么任务消息的传输效率和机群的续航能力都能得到提升。根据编队结构不同，编队控制方法可以分为领航跟随者编队、一致性编队、刚性编队7、持久编队8等。对于信息交互拓扑的研究也是基于这几类编队控制方法进行。其中持久编队相较于刚性编队，仅需要保持单向通信，可以大大降低能量损耗。持久编
5、队是一种通信代价及能耗小、稳定性高的编队结构9，在保持飞行的过程中，与领航跟随者方法类似，通常有一个节点作为领航者按照预定路线进行运动10，其他节点按照生成的信息交互拓扑或与领航节点保持通信或与特定节点保持通信连接，由于收稿日期：2021-08-25；录用日期：2021-11-26；网络出版时间：2022-01-2508：39网络出版地址： J.北京航空航天大学学报，2023，49（7）：1787-1795.XUE Y，HE F，GU X Y.UAV information interaction topology generation considering task allocationJ
6、.Journal of Beijing University ofAeronautics and Astronautics，2023，49（7）：1787-1795（in Chinese）.2023年7月北京航空航天大学学报July2023第49卷第7期JournalofBeijingUniversityofAeronauticsandAstronauticsVol.49No.7相互的通信连接组成了持久图，且相对位置不变，能够很好的保持队形和编队结构的稳定性11。任务消息的传输与拓扑消息的传输类似，若能充分利用这些通信链接，则无需连通新链路，省掉了连接新链路的时间就相当于节省了执行该总体任务的
7、总时间，也尽可能减少了无人机的能量损耗。针对信息交互拓扑的研究，文献 12 证明，领航跟随者方法下信息交互拓扑是通信网络拓扑的一棵有向生成树，在该方法下，文献 6 提出使用通信距离衡量维持该通信链接的代价，文献 4 在此基础上考虑了位置误差对于拓扑和算法的影响，都使用了基于 Dijkstra 最短路径的领航跟随者编队信息交互拓扑优化算法。Luo 等13在文献 4 的算法下，分别基于相对角度和相对距离，提出了 2 种适用于圆编队的算法。刚性图方法下，信息交互拓扑是通信网络拓扑的一个刚性图12：Priolo等7首先对文献 13 的2 种算法进行比较，最终在通信复杂性和最优性之间进行了折中，提出一种
8、最优刚性网络的构造算法。持久图方法下，信息交互拓扑是通信网络拓扑的一个持久图14，国内外诸多学者对此进行了探索和研究。Hendrickx 等8使用一个有向图来描述节点间距离的约束，定义了持久图：如果所有相应的节点间构造的形状都保持不变，则图就是持久的。不仅推导了持久图的各种性质，给出了判定持久性的一个组合准则，而且证明了在刚性编队的基础上进行单向通信即可进一步保持编队的持久性和强壮性，为后续持久图的研究奠定了基础。罗小元等15-16研究了最小加权持久图的生成方法，利用刚性矩阵证明最小加权刚性图的存在性，给出生成最小加权持久图的算法。文献 17 研究了基础圈为三角形、四边形及圆形圈结构下最小持久
9、拓扑的生成。考虑到更多应用上的场景，文献 18 认为无人机之间的通信拓扑不仅是有向的，而且是可切换的；类似的，程潇19对无人机编队组网技术进行研究，对其进行分簇，考虑在任务执行时无人机是可移动的，提出基于移动控制的机制。现有的对于无人机群信息交互拓扑研究大多围绕在拓扑本身的构建，并未结合任务场景，生成的拓扑在编队飞行执行任务时容易造成能量浪费和因连接新链路而任务超时。本文将在已有任务分配方案情形下，使用持久图方法，以任务消息传输时间和无人机能耗为优化目标，提出考虑任务分配因素的信息交互拓扑生成算法，并通过 OMNet+进行了仿真验证。1信息交互拓扑模型在实际应用中，无人机群编队飞行大多需要共同
10、执行某项或某几项任务，一项任务的完成可能要靠编队中的几架无人机合作完成，这几架无人机内部需要进行感知探测、位置计算、指令下达、目标锁定等信息计算和行为实现，其之间也需要不断进行任务消息的传递。不同的拓扑结构将会影响消息的传输时效性，如若 2 节点间未事先建立链接，在需要进行消息传输时，就要进行链接的建立，而链路的距离不同，新链接建立的时长也不同，因而其成为了除任务规划因素之外，造成无人机任务执行空窗等待期的最主要原因。等待时长越久，任务的实时性就越差，执行任务的耗时越久，需要编队保持的时长越长，就会损耗越多的能量，极有可能影响后继任务20的执行。因此，保证任务及时有效的完成，最小化任务执行所需
11、耗用的能量，是无人机群编队任务执行过程中最主要的优化目标。所有的通信链路可以认为是一个集合 U，集合U 可以分为 3 个集合，如图 1 所示，C 越大代表该编队需要维持的链路越少，越节省能量。其中任务分配方案生成后，B 就是固定的，C 会受到信息交互拓扑集 A 的影响。A 和 B 可能会产生交集 A2，A2中既需要传输拓扑消息，又需要传输任务消息的链路；因此相应的，A 可以对立的分为集合 A1和 A2，A1表示只传输拓扑消息的链路集合；B 可以分为 2 个对立集合 A2和 B2，B2表示需要单独连接只传输任务消息的链路。拓扑链路集A任务链路集B纯拓扑链路集A1纯任务链路集B2交集A2总链路集合
12、U无需连通链路集C图1通信链路集合关系示意图Fig.1Schematicdiagramofrelationshipbetweencommunicationlinksets1.1无人机群编队的通信网络拓扑D=(V,E,W)无人机群编队的通信网络拓扑即集合 A 可以用一个赋权有向图来表示6。V=vi(1 i n)viUAVi1）为有向图中的节点集合，节点 表示，n 为 UAV 总数；E=ei,j（1 i,j n,i j）2）为有向图中弧的1788北 京 航 空 航 天 大 学 学 报2023年ei,jvi vjUAViUAVjvi vii j集合，表示从节点的有向弧，即到的通信链路，由于不考虑节点
13、的环，因此；W=w(ei,j)（ei,j E）w(ei,j)UAViUAVj3)为有向图中所有弧的权重集合，用来衡量到通信链路的代价。1.2无人机群编队的信息交互拓扑T=(V,E,W)EW*T D信息交互拓扑由在维持编队过程中所需要使用的通信链路组成，在持久编队方法下，其是一个最优持久图。信息交互拓扑是编队通信网络拓扑的一个子集，因此，信息交互拓扑图可用来 表 示，V 为 所 有 UAV 的 集 合，和分 别 为E 和 W 的子集，。最优持久图的相关定义如下：d(i)2定义定义 1最优持久图。如果一个有向图中各个节点的出度，且对应的无向图是最优刚性图，则这个有向图是最优持久图。定义定义 2最优
14、刚性图。若一个无向图是最优刚性图，必须满足以下条件：1)对应的基础结构图是最小刚性的；2)在所有节点分布相同的刚性图中，其各边边长加权和最小。m(m 2)e=2m3定义定义3最小刚性图。在二维空间中，当刚性图含有个顶点时，当且仅当其边数时是最小刚性图。最小刚性图并不是唯一的。图 2 为同一组无人机不同的最小刚性图。UAV5UAV1UAV2UAV3UAV4(a)最小刚性图1UAV1UAV2UAV3UAV4UAV5(b)最小刚性图2图2同一组无人机的不同的最小刚性图Fig.2DifferentminimumrigiditydiagramsofsamegroupofUAVse=2m3d(i)2因此，
15、持久图方法下信息交互拓扑模型在某种程度上说是一个最优持久图，首先，需要满足最基础的最小刚性图的性质：若共有 m 个节点，则总边数；其次，在算法中，除去关键链路之后，剩余链路加权和最小，满足最优刚性图；最后，作为最优持久图需满足所有节点的出度。由于拓扑的生成要考虑任务因素，故链路权重不仅仅为 2 节点的距离，本文将会详细说明权重的赋值逻辑。2信息交互拓扑链路权重更新方法e=2m3由第 1 节可知，所有通信连接可以看作一个集合 U，在 U 中若任务分配方案固定，则集合 B 固定；且信息交互拓扑模型属性之一为：若共有 m 个节点，则总边数，也就相当于集合 A 的元素数量固定；因此，本文在生成信息交互
16、拓扑集合A 时，若能将集合 A、B 的交集 A2扩大，使较多的信息交互链路也能传输任务信息，则可使连接的链路减少，节省更多能量。因此，信息交互拓扑的生成需要根据任务分配方案的不同进行调整，而信息交互拓扑生成最主要影响因素就是链路的权重，无人机的位置、距离、信道优劣最终都反映在权重上，故将任务因素的影响也反映在链路权重的赋值，依据链路任务消息的负载量调整权重的大小，使用通信代价来反映权重，通信代价越小，表示权重越大，在生成时越优先考虑。在暂时忽略距离因素影响时，任务消息传递越是频繁的有向链路，认为在生成拓扑时该链路的优先级越高，通信代价也将会越小。在实现上，将会把任务分配因素和距离因素进行结合，在距离项前提上对通信代价增加一个惩罚项，任务消息传输越是频繁的链路，惩罚越小，其中传输次数最多的链路不做惩罚。链路通信代价 weight 为weight=normalization(distance)+punish（1）式中：normalization(distance)为归一化后的 2 节点间距离；punish 为对该链路的惩罚项。D=(V,E,W)对于一个由k 架无人机组成的有向图，由于每条有
