本发明提供了一种无人‑有人机编队信息交互拓扑优化方法及装置。所述方法包括：当无人‑有人机编队发生通信故障时，获取通信故障的类型；根据通信故障的类型在编队通信图中删除通信故障弧或通信故障节点以获取优化编队通信图；获取优化编队通信图的二维最优持久图；若存在一个有人机在二维最优持久图中对应节点的入度为0，则确定二维最优持久图为该无人‑有人机编队的优化信息交互拓扑；否则，通过弧反向操作对二维最优持久图进行调整，确定调整后的二维最优持久图为该无人‑有人机编队的优化信息交互拓扑。本发明可以使无人‑有人机组成的二维持久编队在发生通信故障之后快速优化信息交互拓扑以避免发生碰撞事故并恢复编队队形。
1.一种无人-有人机编队信息交互拓扑优化方法，其特征在于，所述方法包括：当所述无人-有人机编队发生通信故障时，获取所述通信故障的类型；
根据所述通信故障的类型在编队通信图中删除通信故障弧或通信故障节点以获取优化编队通信图；
若存在一个有人机在所述二维最优持久图中对应节点的入度为0，则确定所述二维最优持久图为该无人-有人机编队的优化信息交互拓扑；
否则，通过弧反向操作对所述二维最优持久图进行调整，确定调整后的二维最优持久图为该无人-有人机编队的优化信息交互拓扑。
2.根据权利要求1所述的无人-有人机编队信息交互拓扑优化方法，其特征在于，所述通过弧反向操作对所述二维最优持久图进行调整的步骤包括：判断是否存在一个有人机在所述二维最优持久图中对应节点vi的入度为1；
若是，则在所述二维最优持久图中寻找另外一个入度为1的节点vj，该节点vj与节点vi之间具有一条最少跳数的路；将上述最少跳数的路上所有弧反向后得到新的二维最优持久图即为该无人-有人机编队的优化信息交互拓扑，节点vi对应的有人机为该编队的领航者；
若否，则寻找任意一个有人机，该有人机在二维最优持久图中对应节点vi的入度为2，然后在所述二维最优持久图中寻找一个入度为1的节点vj，该节点vj到节点vi之间具有一条最少跳数的路；将上述最少跳数的路上所有弧反向；继续在所述二维最优持久图中寻找另外一个入度为1的节点vk，该节点vk到节点vi之间具有一条最少跳数的路；将上述最少跳数的路上所有弧反向后得到新的二维最优持久图即为该无人-有人机编队的优化信息交互拓扑，节点vi对应的有人机为该编队的领航者。
3.根据权利要求1所述的无人-有人机编队信息交互拓扑优化方法，其特征在于，所述根据所述通信故障的类型在编队通信图中删除通信故障弧或通信故障节点以获取优化编队通信图的步骤包括：若所述通信故障的类型为单播发射机故障，则删除所述编队通信图中对应节点的所有出弧；
若所述通信故障的类型为单播接收机故障，则删除所述编队通信图中对应节点的所有入弧；
若所述通信故障的类型为单播接收机和发射机故障、广播发射机故障或者广播接收机故障，则删除所述编队通信图中对应节点的所有入弧和出弧以及该节点；
若通信故障的类型为任意两飞机之间的链接中断，则删除所述编队通信图中该链接对应的弧；
在所述编队通信图中，若某个无人机的对应节点被删除或该节点的所有弧被删除，则所述无人机退出编队并独自返回机场；若某个有人机的对应节点被删除或该节点的所有弧被删除，则所述有人机退出编队并在一个不同的飞行高度上跟随编队参考航迹飞行。
4.根据权利要求1所述的无人-有人机编队信息交互拓扑优化方法，其特征在于，所述获取所述优化编队通信图的二维最优持久图的步骤包括：计算所述优化编队通信图的二维最优刚性图；
将所述二维最优刚性图中每条边转换成属于所述优化编队通信图的一条弧或者两条权值相同但方向相反的弧得到第一有向图；
在所述第一有向图中增加一个虚拟领航者节点和所述虚拟领航者节点到每个飞机对应节点的出弧得到第二有向图；
根据所述第二有向图计算其第一最小树形图，并将所述第一最小树形图中的虚拟领航者节点和其出弧删除得到第三有向图；
从所述第二有向图中删除所述第三有向图中的所有弧及其对应的反向弧得到第四有向图；
根据所述第四有向图计算其第二最小树形图，并将所述第二最小树形图中的虚拟领航者节点和其出弧删除得到第五有向图；
合并所述第三有向图和所述第五有向图得到第六有向图及其弧的数量m；
当所述二维最优刚性图的节点数量为n且m满足m＝2n-3时，则所述第六有向图为二维最优持久图。
5.根据权利要求4所述的无人-有人机编队信息交互拓扑优化方法，其特征在于，所述获取所述优化编队通信图的二维最优持久图的步骤还包括：当所述二维最优刚性图的节点数量为n且m满足m<(2n-3)时，获取所述二维最优刚性图中的第l条边对应的属于所述第一有向图中弧集合的一条或者两条弧，符号l的初始值为1；
若该一条或者两条弧都不在所述第六有向图中，获取第l条边对应两节点的入度；
若该第l条边对应的两节点的入度不都等于2且其中一个入度小于2的节点的入弧属于所述第一有向图中弧集合，则将该入度小于2的节点的入弧添加到所述第六有向图中得到第七有向图；
若所述第七有向图中弧的数量等于(2n-3)，则所述第七有向图为二维最优持久图；否则将所述第六有向图中的数据更新为所述第七有向图中的数据。
6.根据权利要求5所述的无人-有人机编队信息交互拓扑优化方法，其特征在于，所述获取所述优化编队通信图的二维最优持久图的步骤还包括：若该第l条边对应的两节点的入度都等于2且该第l条边对应的一条弧属于所述第一有向图中弧集合，将该第l条边对应的一条弧添加到第六有向图中得到第七有向图，记该弧指向的节点为第一节点；
在所述第六有向图中寻找入度小于2的一个第二节点，使得所述第二节点与所述第一节点之间具有最少跳数的路径，并且所述最少跳数的路径对应的所有弧的反向弧都在所述第一有向图中弧集合中，将所述最少跳数的路径对应的所有弧反向得到第八有向图；否则从所述第七有向图中删除已添加的该第l条边对应的一条弧，从优化编队通信图中删除该第l条边对应的两条弧，重新计算；
若所述第八有向图中弧的数量m等于(2n-3)，则所述第八有向图为二维最优持久图；否则将所述第六有向图中的数据更新为所述第八有向图中的数据；
将所述符号l的值增加1，若符号l小于等于(2n-3)，则继续判断第l条边对应的一条或两条弧是否都不在所述第六有向图中。
7.一种无人-有人机编队信息交互拓扑优化装置，其特征在于，所述装置包括：通信故障类型获取模块，用于在所述无人-有人机编队发生通信故障时，获取所述通信故障的类型；
优化编队通信图获取模块，用于根据所述通信故障的类型在编队通信图中删除通信故障弧或通信故障节点以获取优化编队通信图；
二维最优持久图获取模块，用于获取所述优化编队通信图的二维最优持久图；
优化信息交互拓扑获取模块，用于存在一个有人机在所述二维最优持久图中对应节点的入度为0时，确定所述二维最优持久图为该无人-有人机编队的优化信息交互拓扑；
否则，通过弧反向操作对所述二维最优持久图进行调整，确定调整后的二维最优持久图为该无人-有人机编队的优化信息交互拓扑。
8.根据权利要求7所述的无人-有人机编队信息交互拓扑优化装置，其特征在于，所述优化信息交互拓扑获取模块通过以下步骤对所述二维最优持久图进行调整包括：判断是否存在一个有人机在所述二维最优持久图中对应节点vi的入度为1；
若是，则在所述二维最优持久图中寻找另外一个入度为1的节点vj，该节点vj与节点vi之间具有一条最少跳数的路；将上述最少跳数的路上所有弧反向后得到新的二维最优持久图即为该无人-有人机编队的优化信息交互拓扑，节点vi对应的有人机为该编队的领航者；
若否，则寻找任意一个有人机，该有人机在二维最优持久图中对应节点vi的入度为2，然后在所述二维最优持久图中寻找一个入度为1的节点vj，该节点vj到节点vi之间具有一条最少跳数的路；将上述最少跳数的路上所有弧反向；继续在所述二维最优持久图中寻找另外一个入度为1的节点vk，该节点vk到节点vi之间具有一条最少跳数的路；将上述最少跳数的路上所有弧反向后得到新的二维最优持久图即为该无人-有人机编队的优化信息交互拓扑，节点vi对应的有人机为该编队的领航者。
9.根据权利要求7所述的无人-有人机编队信息交互拓扑优化装置，其特征在于，所述二维最优持久图获取模块执行以下步骤获取所述优化编队通信图的二维最优持久图包括：计算所述优化编队通信图的二维最优刚性图；
将所述二维最优刚性图中每条边转换成属于所述优化编队通信图的一条弧或者两条权值相同但方向相反的弧得到第一有向图；
在所述第一有向图中增加一个虚拟领航者节点和所述虚拟领航者节点到每个飞机对应节点的出弧得到第二有向图；
根据所述第二有向图计算其第一最小树形图，并将所述第一最小树形图中的虚拟领航者节点和其出弧删除得到第三有向图；
从所述第二有向图中删除所述第三有向图中的所有弧及其对应的反向弧得到第四有向图；
根据所述第四有向图计算其第二最小树形图，并将所述第二最小树形图中的虚拟领航者节点和其出弧删除得到第五有向图；
合并所述第三有向图和所述第五有向图得到第六有向图及其弧的数量m；
当所述二维最优刚性图的节点数量为n且m满足m＝2n-3时，则所述第六有向图为二维最优持久图。
10.根据权利要求9所述的无人-有人机编队信息交互拓扑优化装置，其特征在于，所述二维最优持久图获取模块还执行以下步骤获取所述优化编队通信图的二维最优持久图包括：当所述二维最优刚性图的节点数量为n且m满足m<(2n-3)时，获取所述二维最优刚性图中的第l条边对应的属于所述第一有向图中弧集合的一条或者两条弧，符号l的初始值为1；
若该一条或者两条弧都不在所述第六有向图中，获取第l条边对应两节点的入度；
若该第l条边对应的两节点的入度不都等于2且其中一个入度小于2的节点的入弧属于所述第一有向图中弧集合，则将该入度小于2的节点的入弧添加到所述第六有向图中得到第七有向图；
若所述第七有向图中弧的数量等于(2n-3)，则所述第七有向图为二维最优持久图；否则将所述第六有向图中的数据更新为所述第七有向图中的数据；
若该第l条边对应的两节点的入度都等于2且该第l条边对应的一条弧属于所述第一有向图中弧集合，将该第l条边对应的一条弧添加到第六有向图中得到第七有向图，记该弧指向的节点为第一节点；
在所述第六有向图中寻找入度小于2的一个第二节点，使得所述第二节点与所述第一节点之间具有最少跳数的路径，并且所述最少跳数的路径对应的所有弧的反向弧都在所述第一有向图中弧集合中，将所述最少跳数的路径对应的所有弧反向得到第八有向图；否则从所述第七有向图中删除已添加的该第l条边对应的一条弧，从优化编队通信图中删除该第l条边对应的两条弧，重新计算；
若所述第八有向图中弧的数量m等于(2n-3)时，则所述第八有向图为二维最优持久图；
否则将所述第六有向图中的数据更新为所述第八有向图中的数据；
将所述符号l的值增加1，若符号l小于等于(2n-3)时，则继续判断第l条边对应的一条或两条弧是否都不在所述第六有向图中。
无人-有人机编队信息交互拓扑优化方法及装置
技术领域
[0001] 本发明涉及通信技术领域，尤其涉及一种无人-有人机编队信息交互拓扑优化方法及装置。
背景技术
[0002] 在起飞巡航阶段，无人-有人机编队中各飞机通常通过点对点的通信链接(communication links)进行信息交互，以形成一定的编队队形(formation shape或者formation geometry)，并保持此编队队形继续朝目标区域飞行。其中所使用的通信链接的集合被称为编队的信息交互拓扑(information exchange topology)、通信拓扑(communication topology)、连接拓扑(connection topology)、信息结构(Information Structure)或者信息拓扑(InformationTopology)，它们只是无人-有人机编队中任意两飞机之间所有可用的通信链接集合中的一部分。为了统一表述，下文采用“信息交互拓扑”这一名称。同时，将无人-有人机编队所有可用的通信链接的集合称为编队的编队通信图(Formation Communication Graph)。
[0003] 由于信息交互拓扑中任何两位置无人机和/或有人机之间的通信距离不同，导致信息交互拓扑中不同飞机之间通信链接具有不同的通信代价并会消耗飞机相应的电池电量或燃料。实际应用中，两架飞机(无人机，有人机)之间通信链接的通信代价受到很多因素影响，例如，任务要求、通信距离、飞行性能、安全性等。为简化说明，上述通信代价直接采用通信距离来表示。同时，每架飞机(无人机，有人机)可用的电池电量或燃料又是有限的。此外，编队飞行过程中某个或多个飞机可能会发生通信故障，使得当前信息交互拓扑中的某些通信链接不能够被使用，从而导致飞机不能继续保持编队队形，严重时甚至会导致飞机碰撞事故。因此，如何通过优化无人-有人机编队信息交互拓扑，以避免发生飞机碰撞事故并恢复编队队形，同时降低飞机的电池电量或燃料的消耗成为了亟需解决的技术问题。
发明内容
[0004] 针对相关技术中的缺陷，本发明提供了一种无人-有人机编队信息交互拓扑优化方法及装置，用于在无人-有人机组成的二维持久编队发生通信故障之后优化此二维持久编队的信息交互拓扑，以避免发生飞机碰撞事故并恢复编队队形，同时降低飞机的电池电量或燃料的消耗。
[0005] 第一方面，本发明实施例提供了一种无人-有人机编队信息交互拓扑优化方法，所述方法包括：
[0006] 当所述无人-有人机编队发生通信故障时，获取所述通信故障的类型；
[0007] 根据所述通信故障的类型在编队通信图中删除通信故障弧或通信故障节点以获取优化编队通信图；
[0008] 获取所述优化编队通信图的二维最优持久图；
[0009] 若存在一个有人机在所述二维最优持久图中对应节点的入度为0，则确定所述二维最优持久图为该无人-有人机编队的优化信息交互拓扑；
[0010] 否则，通过弧反向操作对所述二维最优持久图进行调整，确定调整后的二维最优持久图为该无人-有人机编队的优化信息交互拓扑。
[0011] 可选地，所述通过弧反向操作对所述二维最优持久图进行调整的步骤包括：
[0012] 判断是否存在一个有人机在所述二维最优持久图中对应节点vi的入度为1；
[0013] 若是，则在所述二维最优持久图中寻找另外一个入度为1的节点vj，该节点vj与节点vi之间具有一条最少跳数的路；将上述最少跳数的路上所有弧反向后得到新的二维最优持久图即为该无人-有人机编队的优化信息交互拓扑，节点vi对应的有人机为该编队的领航者；
[0014] 若否，则寻找任意一个有人机，该有人机在二维最优持久图中对应节点vi的入度为2，然后在所述二维最优持久图中寻找一个入度为1的节点vj，该节点vj到节点vi之间具有一条最少跳数的路；将上述最少跳数的路上所有弧反向；继续在所述二维最优持久图中寻找另外一个入度为1的节点vk，该节点vk到节点vi之间具有一条最少跳数的路；将上述最少跳数的路上所有弧反向后得到新的二维最优持久图即为该无人-有人机编队的优化信息交互拓扑，节点vi对应的有人机为该编队的领航者。
[0015] 可选地，所述根据所述通信故障的类型在编队通信图中删除通信故障弧或通信故障节点以获取优化编队通信图的步骤包括：
[0016] 若所述通信故障的类型为单播发射机故障，则删除所述编队通信图中对应节点的所有出弧；
[0017] 若所述通信故障的类型为单播接收机故障，则删除所述编队通信图中对应节点的所有入弧；
[0018] 若所述通信故障的类型为单播接收机和发射机故障、广播发射机故障或者广播接收机故障，则删除所述编队通信图中对应节点的所有入弧和出弧以及该节点；
[0019] 或者，
[0020] 若通信故障的类型为任意两飞机之间的链接中断，则删除所述编队通信图中该链接对应的弧；
[0021] 在所述编队通信图中，若某个无人机的对应节点被删除或该节点的所有弧被删除，则所述无人机退出编队并独自返回机场；若某个有人机的对应节点被删除或该节点的所有弧被删除，则所述有人机退出编队并在一个不同的飞行高度上跟随编队参考航迹飞行。
[0022] 可选地，所述获取所述优化编队通信图的二维最优持久图的步骤包括：
[0023] 计算所述优化编队通信图的二维最优刚性图；
[0024] 将所述二维最优刚性图中每条边转换成属于所述优化编队通信图的一条弧或者两条权值相同但方向相反的弧得到第一有向图；
[0025] 在所述第一有向图中增加一个虚拟领航者节点和所述虚拟领航者节点到每个飞机对应节点的出弧得到第二有向图；
[0026] 根据所述第二有向图计算其第一最小树形图，并将所述第一最小树形图中的虚拟领航者节点和其出弧删除得到第三有向图；
[0027] 从所述第二有向图中删除所述第三有向图中的所有弧及其对应的反向弧得到第四有向图；
[0028] 根据所述第四有向图计算其第二最小树形图，并将所述第二最小树形图中的虚拟领航者节点和其出弧删除得到第五有向图；
[0029] 合并所述第三有向图和所述第五有向图得到第六有向图及其弧的数量m；
[0030] 当所述二维最优刚性图的节点数量为n且m满足m＝2n-3时，则所述第六有向图为二维最优持久图。
[0031] 可选地，所述获取所述优化编队通信图的二维最优持久图的步骤还包括：
[0032] 当所述二维最优刚性图的节点数量为n且m满足m<(2n-3)时，获取所述二维最优刚性图中的第l条边对应的属于所述第一有向图中弧集合的一条或者两条弧，符号l的初始值为1；
[0033] 若该一条或者两条弧都不在所述第六有向图中，获取第l条边对应两节点的入度；
[0034] 若该第l条边对应的两节点的入度不都等于2且其中一个入度小于2的节点的入弧属于所述第一有向图中弧集合，则将该入度小于2的节点的入弧添加到所述第六有向图中得到第七有向图；
[0035] 若所述第七有向图中弧的数量等于(2n-3)，则所述第七有向图为二维最优持久图；否则将所述第六有向图中的数据更新为所述第七有向图中的数据。
[0036] 可选地，所述获取所述优化编队通信图的二维最优持久图的步骤还包括：
[0037] 若该第l条边对应的两节点的入度都等于2且该第l条边对应的一条弧属于所述第一有向图中弧集合，将该第l条边对应的一条弧添加到第六有向图中得到第七有向图，记该弧指向的节点为第一节点；
[0038] 在所述第六有向图中寻找入度小于2的一个第二节点，使得所述第二节点与所述第一节点之间具有最少跳数的路径，并且所述最少跳数的路径对应的所有弧的反向弧都在所述第一有向图中弧集合中，将所述最少跳数的路径对应的所有弧反向得到第八有向图；否则从所述第七有向图中删除已添加的该第l条边对应的一条弧，从优化编队通信图中删除该第l条边对应的两条弧，重新计算；
[0039] 若所述第八有向图中弧的数量m等于(2n-3)，则所述第八有向图为二维最优持久图；否则将所述第六有向图中的数据更新为所述第八有向图中的数据；
[0040] 将所述符号l的值增加1，若符号l小于等于(2n-3)，则继续判断第l条边对应的一条或两条弧是否都不在所述第六有向图中。
[0041] 第二方面，本发明实施例还提供了一种无人-有人机编队信息交互拓扑优化装置，所述装置包括：
[0042] 通信故障类型获取模块，用于在所述无人-有人机编队发生通信故障时，获取所述通信故障的类型；
[0043] 优化编队通信图获取模块，用于根据所述通信故障的类型在编队通信图中删除通信故障弧或通信故障节点以获取优化编队通信图；
[0044] 二维最优持久图获取模块，用于获取所述优化编队通信图的二维最优持久图；
[0045] 优化信息交互拓扑获取模块，用于存在一个有人机在所述二维最优持久图中对应节点的入度为0时，确定所述二维最优持久图为该无人-有人机编队的优化信息交互拓扑；
[0046] 否则，通过弧反向操作对所述二维最优持久图进行调整，确定调整后的二维最优持久图为该无人-有人机编队的优化信息交互拓扑。
[0047] 可选地，所述优化信息交互拓扑获取模块通过以下步骤对所述二维最优持久图进行调整包括：
[0048] 判断是否存在一个有人机在所述二维最优持久图中对应节点vi的入度为1；
[0049] 若是，则在所述二维最优持久图中寻找另外一个入度为1的节点vj，该节点vj与节点vi之间具有一条最少跳数的路；将上述最少跳数的路上所有弧反向后得到新的二维最优持久图即为该无人-有人机编队的优化信息交互拓扑，节点vi对应的有人机为该编队的领航者；
[0050] 若否，则寻找任意一个有人机，该有人机在二维最优持久图中对应节点vi的入度为2，然后在所述二维最优持久图中寻找一个入度为1的节点vj，该节点vj到节点vi之间具有一条最少跳数的路；将上述最少跳数的路上所有弧反向；继续在所述二维最优持久图中寻找另外一个入度为1的节点vk，该节点vk到节点vi之间具有一条最少跳数的路；将上述最少跳数的路上所有弧反向后得到新的二维最优持久图即为该无人-有人机编队的优化信息交互拓扑，节点vi对应的有人机为该编队的领航者。
[0051] 可选地，所述二维最优持久图获取模块执行以下步骤获取所述优化编队通信图的二维最优持久图包括：
[0052] 计算所述优化编队通信图的二维最优刚性图；
[0053] 将所述二维最优刚性图中每条边转换成属于所述优化编队通信图的一条弧或者两条权值相同但方向相反的弧得到第一有向图；
[0054] 在所述第一有向图中增加一个虚拟领航者节点和所述虚拟领航者节点到每个飞机对应节点的出弧得到第二有向图；
[0055] 根据所述第二有向图计算其第一最小树形图，并将所述第一最小树形图中的虚拟领航者节点和其出弧删除得到第三有向图；
[0056] 从所述第二有向图中删除所述第三有向图中的所有弧及其对应的反向弧得到第四有向图；
[0057] 根据所述第四有向图计算其第二最小树形图，并将所述第二最小树形图中的虚拟领航者节点和其出弧删除得到第五有向图；
[0058] 合并所述第三有向图和所述第五有向图得到第六有向图及其弧的数量m；
[0059] 当所述二维最优刚性图的节点数量为n且m满足m＝2n-3时，则所述第六有向图为二维最优持久图。
[0060] 可选地，所述二维最优持久图获取模块还执行以下步骤获取所述优化编队通信图的二维最优持久图包括：
[0061] 当所述二维最优刚性图的节点数量为n且m满足m<(2n-3)时，获取所述二维最优刚性图中的第l条边对应的属于所述第一有向图中弧集合的一条或者两条弧，符号l的初始值为1；
[0062] 若该一条或者两条弧都不在所述第六有向图中，获取第l条边对应两节点的入度；
[0063] 若该第l条边对应的两节点的入度不都等于2且其中一个入度小于2的节点的入弧属于所述第一有向图中弧集合，则将该入度小于2的节点的入弧添加到所述第六有向图中得到第七有向图；
[0064] 若所述第七有向图中弧的数量等于(2n-3)，则所述第七有向图为二维最优持久图；否则将所述第六有向图中的数据更新为所述第七有向图中的数据；
[0065] 若该第l条边对应的两节点的入度都等于2且该第l条边对应的一条弧属于所述第一有向图中弧集合，将该第l条边对应的一条弧添加到第六有向图中得到第七有向图，记该弧指向的节点为第一节点；
[0066] 在所述第六有向图中寻找入度小于2的一个第二节点，使得所述第二节点与所述第一节点之间具有最少跳数的路径，并且所述最少跳数的路径对应的所有弧的反向弧都在所述第一有向图中弧集合中，将所述最少跳数的路径对应的所有弧反向得到第八有向图；否则从所述第七有向图中删除已添加的该第l条边对应的一条弧，从优化编队通信图中删除该第l条边对应的两条弧，重新计算；
[0067] 若所述第八有向图中弧的数量m等于(2n-3)时，则所述第八有向图为二维最优持久图；否则将所述第六有向图中的数据更新为所述第八有向图中的数据；
[0068] 将所述符号l的值增加1，若符号l小于等于(2n-3)时，则继续判断第l条边对应的一条或两条弧是否都不在所述第六有向图中。
[0069] 由上述技术方案可知，本发明在所述无人-有人机编队发生通信故障时，获取所述通信故障的类型；根据所述通信故障的类型在编队通信图中删除通信故障弧或通信故障节点以获取优化编队通信图；获取所述优化编队通信图的二维最优持久图；若存在一个有人机在所述二维最优持久图中对应节点的入度为0，则确定所述二维最优持久图为该无人-有人机编队的优化信息交互拓扑；否则，通过弧反向操作对所述二维最优持久图进行调整，确定调整后的二维最优持久图为该无人-有人机编队的优化信息交互拓扑。与相关技术相比较，本发明实现了在无人-有人机组成的二维持久编队发生通信故障之后，快速优化此二维持久编队的信息交互拓扑，以避免发生飞机碰撞事故并恢复编队队形，同时降低飞机的电池电量或燃料的消耗。
附图说明
[0070] 为了更清楚地说明本发明实施例或相关技术中的技术方案，下面将对实施例或相关技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些图获得其他的附图。
[0071] 图1是本发明实施例提供的无人-有人机编队信息交互拓扑优化方法的流程示意图；
[0072] 图2(a)～(b)是本发明实施例中3架无人机和2架有人机组成的二维持久编队的队形以及相对位置示意图；有人机Fighter1和Fighter2分别在队形的1号和2号位置，无人机UAV1、UAV2和UAV3分别在队形的3号、4号和5号位置；
[0073] 图3为本发明实施例提供的上述无人-有人机编队无通信故障时的最优信息交互拓扑示意图；
[0074] 图4(a)～(d)是上述无人-有人机编队中的Fighter2发生单播接收机故障时采用图1方法获取该无人-有人机编队的优化信息交互拓扑的过程示意图；
[0075] 图5是本发明实施例提供的无人-有人机编队信息交互拓扑优化装置框图。
具体实施方式
[0076] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0077] 图1为本发明一实施例提供的一种无人-有人机编队信息交互拓扑优化方法，所述方法包括：
[0078] S1、当所述无人-有人机编队发生通信故障时，获取所述通信故障的类型。
[0079] S2、根据所述通信故障的类型在编队通信图中删除通信故障弧或通信故障节点以获取优化编队通信图。
[0080] S3、获取所述优化编队通信图的二维最优持久图。
[0081] S4、若存在一个有人机在所述二维最优持久图中对应节点的入度为0，则确定所述二维最优持久图为该无人-有人机编队的优化信息交互拓扑；
[0082] 否则，通过弧反向操作对所述二维最优持久图进行调整，确定调整后的二维最优持久图为该无人-有人机编队的优化信息交互拓扑。
[0083] 在对上述方法进行详细说明之前，首先对无人-有人机组成的二维持久编队的编队控制方法、编队通信图和信息交互拓扑进行说明。
[0084] 无人-有人机组成的二维持久编队的编队控制方法是一种基于距离的编队控制方法，其基本思想是：编队中的一架有人机作为编队领航者(formationleader)按照预定的编队参考航迹飞行，编队中的另外一架飞机(有人机或无人机)在飞行过程中只需要保持与编队领航者的距离恒定，其余的飞机在飞行过程则需要同时保持与另外两架飞机之间的距离恒定，从而实现对二维空间的编队队形的保持。
[0085] 假设n架飞机(以下用PLANE表示，包括有人机或无人机)需要使用二维持久编队的编队控制方法来形成和保持一个二维空间的编队队形S，S中的n个位置分别编号为{1,2,…,n}，只有有人机可以作为编队领航者，每架飞机可以通过点对点通信链接和其它任意飞机进行信息交互，每个通信链接的通信代价由其相应的通信距离决定。因此，可以用一个赋权有向图D＝(V,A,W,P)来表示编队中飞机之间所有可用的通信链接，并简称为编队通信图：
[0086] (1)V＝{vi},1≤i≤n是图中的节点集合，其中vi表示第i架飞机PLANEi。
[0087] (2) 是图中的弧集合，其中aij表示从PLANEi到PLANEj有一个可用的通信链接从而使得PLANEi能发送信息给PLANEj。
[0088] (3)W＝{w(aij)},aij∈A是图中每条弧的权值集合，其中w(aij)表示aij的通信代价。
[0089] (4)P＝{pi},1≤i≤n是每架飞机在编队队形S的具体位置集合，其中将编队队形S中的n个位置分别编号为{1,2,...,n}，则1≤pi≤n表示PLANEi在S中的具体位置。
[0090] 根据前面的描述可知，无人-有人机组成的二维持久编队中的每架飞机最多只需要从其它两架飞机接收信息，这意味着不需要使用所有可用的通信链接就可以实现编队队形的形成和保持。因此，无人-有人机编队的信息交互拓扑T＝(V,A*,W*,P)是其编队通信图D＝(V,A,W,P)的一个特殊子图，其中 令w(T)表示信息交互拓扑T对应的编队通信代价，即有 无人-有人机组成的二维持久编队的信息交互
拓扑T具有如下两个特性。
[0091] 定理1:无人-有人机组成的二维持久编队的信息交互拓扑T必须是其编队通信图D的一个二维持久图，但是其编队通信图D的一个二维持久图并不一定能作为其信息交互拓扑。
[0092] 定理2:无人-有人机组成的二维持久编队的信息交互拓扑T必须是其编队通信图D的一个二维持久图，并且T存在一个入度为0的节点所对应的飞机能够作为编队领航者(即为有人机)；反之亦然。
[0093] 为突出本发明提供的无人-有人机编队信息交互拓扑优化方法的有效性，下面结合实施例和附图对上述方法进行详细说明。
[0094] 实际应用中，通信故障发生之后，对无人-有人机编队的信息交互拓扑的优化应尽量是分布式的以获得更短的执行时间，并且所有PLANE的计算结果必须保持一致，因此所有PLANE需要及时地获知到同样的通信故障信息。
[0095] 为此，基于现有技术中的方法，假设每个PLANE都能使用一个广播通信信道(Broadcast Communication channel，BC)来获得同样的通信故障信息：(1)每个PLANE都有一个单播发射机(unicast transmitter)和一个单播接收机(unicastreceiver)以进行点对点通信，每个PLANE都有一个广播发射机(broadcast transmitter)和一个广播接收机(broadcast receiver)以通过BC进行广播通信。(2)每个PLANE每隔Tactive秒会通过BC上报其状态。(3)当一个PLANE检测到某个通信故障时，它会立即通过BC通知其他PLANE。
[0096] 除了考虑相关技术中的四种通信故障外，还考虑另外两种通信故障：广播发射机故障(broadcast transmitter failure)和广播接收机故障(broadcast receiver failure)。所有六种通信故障类型如表1所示。
[0097] 表1
[0098]
[0099]
[0100] 当所述无人-有人机编队发生通信故障时，本发明实施例采用以下通信故障诊断策略来获取所述通信故障的类型：
[0101] (1)当PLANEi发生单播发射机故障、单播接收机故障、单播收发机故障或者广播接收机故障中的任何一种通信故障时，PLANEi自身能够检测到此通信故障，PLANEi将记录下此通信故障发生时的时间戳并通过BC将此通信故障和相应的时间戳信息通知其他PLANE。
[0102] (2)当PLANEi发生广播发射机故障时，PLANEi自身能够检测到此通信故障但不能通过BC通知其他PLANE，Tactive秒之后，其他PLANE由于不能收到PLANEi上报的状态将判定PLANEi出现了广播发射机故障，并记录下此通信故障发生时的时间戳。
[0103] (3)当从PLANEi到PLANEj的通信链接出现链接中断并且编队保持队形过程中PLANEi需要发送信息给PLANEj，Tactive秒之后，如果PLANEj自身没有发生单播接收机故障并且没有通过BC收到PLANEi的单播发射机故障信息，PLANEj将判定从PLANEi到PLANEj的通信链接出现了链接中断，然后PLANEj将记录此通信故障的时间戳，然后通过BC将此通信故障和相应的时间戳信息通知其他PLANE。
[0104] 基于上述的通信故障诊断策略，每个PLANE能够及时地获得通信故障的信息，然后每个PLANE可以根据所述通信故障的类型在编队通信图中删除通信故障弧或通信故障节点以获取优化编队通信图，再获得所述优化编队通信图的二维最优持久图T。如果T中存在入度为0的节点vi并且vi代表的PLANE是一个有人机，则T是一个可行的信息交互拓扑，即所有飞机可以将信息交互拓扑切换为T以继续保持编队队形；否则T不是一个可行的信息交互拓扑，即所有飞机不能使用T来保持编队队形，但这种情况下并不代表一定不存在另外一个可行的信息交互拓扑。
[0105] 为了解决这个问题，本发明实施例提供了一种基于二维最优刚性图和最小树形图(Two-Dimensional Optimal Rigid Graph and Minimum CostArborescence，2DORG_MCA)的无人-有人机编队信息交互拓扑优化算法。当通信故障发生时每个PLANE将会执行此算法。以PLANEi为例，当PLANEi通过BC从其它PLANE接收到一个通信故障通知或者检测到自身发生通信故障时，它就会运行此算法以得到优化信息交互拓扑Tr。当每个PLANE执行此算法后，将切换到Tr以确保PLANE的安全并快速恢复编队队形。此算法的基本步骤如表2所示。
[0106] 表2
[0107]
[0108]
[0109]
[0110]
[0111] 需要说明的是，表2所提供算法的Step6.2中使用的现有技术中的二维最优刚性图生成算法，其基本步骤如表3所示，时间复杂度约为O(4×|V|4)。
[0112] 表3
[0113]
[0114] 同时需要说明的是，表2所提供算法的Step6.5和Step6.7中的最小树形图(Minimum CostArborescence，MCA)指的是一个赋权有向图的最小生成树，此处使用的是Gabow等人提出的最小树形图生成算法，其计算复杂度为O(|A|+|V|×log|V|)，其中的|A|和|V|分别为赋权有向图中弧的数量和节点的数量。
[0115] 表2所提供算法的时间复杂度主要由Step6的时间复杂度决定，而Step6的时间复杂度主要由Step6.2、Step6.5和Step6.7决定，由于Step6.2的时间复杂度约为O(4×|Vr|4)，Step6.5和Step6.7的时间复杂度都约为O(|Ar|+|Vr|×log|Vr|)，所以表2所提供算法的时4
间复杂度约为O(4×|Vr|+2×(|Ar|+|Vr|×log|Vr|))。
[0116] 假设一个二维持久编队由3架无人机(UAV1、UAV2、UAV3)和2架有人机(Fighter1、Fighter2)组成，其中只有有人机Fighter1和Fighter2可以作为编队的领航者。它们需要形成并保持一个如图2(a)所示的二维空间队形，其中的所有位置分别编号为{1,2,3,4,5}，其中，Fighter1和Fighter2分别在队形的1号和2号位置，UAV1、UAV2和UAV3分别在队形的3号、4号和5号位置；它们之间的距离如图2(a)所示；如果以队形中的4号位置作为平面坐标系的原点，则该无人-有人机编队的队形中的每个位置的坐标如图2(b)所示。当无通信故障时，该无人-有人机编队使用如图3所示的最优信息交互拓扑来形成并保持此队形，其中有人机Fighter1作为该无人-有人机编队的领航者。
[0117] 当有人机Fighter2发生单播接收机故障时，根据表2提供的算法对该无人-有人机编队的信息交互拓扑进行优化，其主要过程如下：
[0118] (1)在Step2中，删除当前编队通信图D＝(V,A,W,P)中v2的所有入弧得到优化编队通信图Dr＝(Vr,Ar,Wr,Pr)。
[0119] (2)在Step6.3中，根据表3所示的二维最优刚性图算法生成得到Dr＝(Vr,Ar,Wr,Pr)对应的二维最优刚性图 如图4(a)所示。
[0120] (3)在Step6.5中，得到第二有向图D'Rr的最小树形图T1'，如图4(b)所示，再将T1'中的v0和v0的出弧删除后得到T1。
[0121] (4)在Step6.7中，得到第四有向图D”Rr的最小树形图T2'，如图4(c)所示，再将T2'中的v0和v0的出弧删除后得到T2。
[0122] (5)在Step6.8中，将T1和T2合并得到有向图Tr，如图4(d)所示。
[0123] (6)由于Tr中弧的总数与Rr中边的总数相同，满足Step6.9的条件，因此Tr是Rr对应的一个二维最优持久图。
[0124] (7)由于Tr中的节点v2的入度为0，且v2所代表的Fighter2可以作为编队领航者，满足Step6.16的条件，因此Tr是此无人-有人编队的优化信息交互拓扑。
[0125] 第二方面，本发明实施例还提供了一种无人-有人机编队信息交互拓扑优化装置，如图5所示，所述装置包括：
[0126] 通信故障类型获取模块M1，用于在所述无人-有人机编队发生通信故障时，获取所述通信故障的类型；
[0127] 优化编队通信图获取模块M2，用于根据所述通信故障的类型在编队通信图中删除通信故障弧或通信故障节点以获取优化编队通信图；
[0128] 二维最优持久图获取模块M3，用于获取所述优化编队通信图的二维最优持久图；
[0129] 优化信息交互拓扑获取模块M4，用于存在一个有人机在所述二维最优持久图中对应节点的入度为0时，确定所述二维最优持久图为该无人-有人机编队的优化信息交互拓扑；
[0130] 否则，通过弧反向操作对所述二维最优持久图进行调整，确定调整后的二维最优持久图为该无人-有人机编队的优化信息交互拓扑。
[0131] 可选地，所述优化信息交互拓扑获取模块M4通过以下步骤对所述二维最优持久图进行调整包括：
[0132] 判断是否存在一个有人机在所述二维最优持久图中对应节点vi的入度为1；
[0133] 若是，则在所述二维最优持久图中寻找另外一个入度为1的节点vj，该节点vj与节点vi之间具有一条最少跳数的路；将上述最少跳数的路上所有弧反向后得到新的二维最优持久图即为该无人-有人机编队的优化信息交互拓扑，节点vi对应的有人机为该编队的领航者；
[0134] 若否，则寻找任意一个有人机，该有人机在二维最优持久图中对应节点vi的入度为2，然后在所述二维最优持久图中寻找一个入度为1的节点vj，该节点vj到节点vi之间具有一条最少跳数的路；将上述最少跳数的路上所有弧反向；继续在所述二维最优持久图中寻找另外一个入度为1的节点vk，该节点vk到节点vi之间具有一条最少跳数的路；将上述最少跳数的路上所有弧反向后得到新的二维最优持久图即为该无人-有人机编队的优化信息交互拓扑，节点vi对应的有人机为该编队的领航者。
[0135] 可选地，所述二维最优持久图获取模块M3执行以下步骤获取所述优化编队通信图的二维最优持久图包括：
[0136] 计算所述优化编队通信图的二维最优刚性图；
[0137] 将所述二维最优刚性图中每条边转换成属于所述优化编队通信图的一条弧或者两条权值相同但方向相反的弧得到第一有向图；
[0138] 在所述第一有向图中增加一个虚拟领航者节点和所述虚拟领航者节点到每个飞机对应节点的出弧得到第二有向图；
[0139] 根据所述第二有向图计算其第一最小树形图，并将所述第一最小树形图中的虚拟领航者节点和其出弧删除得到第三有向图；
[0140] 从所述第二有向图中删除所述第三有向图中的所有弧及其对应的反向弧得到第四有向图；
[0141] 根据所述第四有向图计算其第二最小树形图，并将所述第二最小树形图中的虚拟领航者节点和其出弧删除得到第五有向图；
[0142] 合并所述第三有向图和所述第五有向图得到第六有向图及其弧的数量m；
[0143] 当所述二维最优刚性图的节点数量为n且m满足m＝2n-3时，则所述第六有向图为二维最优持久图。
[0144] 可选地，所述二维最优持久图获取模块M3还执行以下步骤获取所述优化编队通信图的二维最优持久图包括：
[0145] 当所述二维最优刚性图的节点数量为n且m满足m<(2n-3)时，获取所述二维最优刚性图中的第l条边对应的属于所述第一有向图中弧集合的一条或者两条弧，符号l的初始值为1；
[0146] 若该一条或者两条弧都不在所述第六有向图中，获取第l条边对应两节点的入度；
[0147] 若该第l条边对应的两节点的入度不都等于2且其中一个入度小于2的节点的入弧属于所述第一有向图中弧集合，则将该入度小于2的节点的入弧添加到所述第六有向图中得到第七有向图；
[0148] 若所述第七有向图中弧的数量等于(2n-3)，则所述第七有向图为二维最优持久图；否则将所述第六有向图中的数据更新为所述第七有向图中的数据；
[0149] 若该第l条边对应的两节点的入度都等于2且该第l条边对应的一条弧属于所述第一有向图中弧集合，将该第l条边对应的一条弧添加到第六有向图中得到第七有向图，记该弧指向的节点为第一节点；
[0150] 在所述第六有向图中寻找入度小于2的一个第二节点，使得所述第二节点与所述第一节点之间具有最少跳数的路径，并且所述最少跳数的路径对应的所有弧的反向弧都在所述第一有向图中弧集合中，将所述最少跳数的路径对应的所有弧反向得到第八有向图；否则从所述第七有向图中删除已添加的该第l条边对应的一条弧，从优化编队通信图中删除该第l条边对应的两条弧，重新计算；
[0151] 若所述第八有向图中弧的数量m等于(2n-3)时，则所述第八有向图为二维最优持久图；否则将所述第六有向图中的数据更新为所述第八有向图中的数据；
[0152] 将所述符号l的值增加1，若符号l小于等于(2n-3)时，则继续判断第l条边对应的一条或两条弧是否都不在所述第六有向图中。
[0153] 需要说明的是，本发明实施例提供的无人-有人机编队信息交互拓扑优化装置与上述方法一一对应的关系，上述方法的实施细节同样适用于上述装置，本发明实施例不再对上述系统进行详细说明。
[0154] 最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围，其均应涵盖在本发明的权利要求和说明书的范围当中。
