[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN105871636A - 基于最小树形图的无人机编队通信拓扑的重构方法及系统 - Google Patents

基于最小树形图的无人机编队通信拓扑的重构方法及系统 Download PDF

Info

Publication number
CN105871636A
CN105871636A CN201610383796.2A CN201610383796A CN105871636A CN 105871636 A CN105871636 A CN 105871636A CN 201610383796 A CN201610383796 A CN 201610383796A CN 105871636 A CN105871636 A CN 105871636A
Authority
CN
China
Prior art keywords
unmanned plane
formation
communication
traffic diagram
node
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN201610383796.2A
Other languages
English (en)
Other versions
CN105871636B (zh
Inventor
罗贺
王国强
胡笑旋
马华伟
靳鹏
夏维
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Hefei University of Technology
Original Assignee
Hefei University of Technology
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Hefei University of Technology filed Critical Hefei University of Technology
Priority to CN201610383796.2A priority Critical patent/CN105871636B/zh
Publication of CN105871636A publication Critical patent/CN105871636A/zh
Priority to US15/460,369 priority patent/US9929914B2/en
Application granted granted Critical
Publication of CN105871636B publication Critical patent/CN105871636B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/10—Simultaneous control of position or course in three dimensions
    • G05D1/101—Simultaneous control of position or course in three dimensions specially adapted for aircraft
    • G05D1/104—Simultaneous control of position or course in three dimensions specially adapted for aircraft involving a plurality of aircrafts, e.g. formation flying
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
    • H04L41/12—Discovery or management of network topologies
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B64—AIRCRAFT; AVIATION; COSMONAUTICS
    • B64U—UNMANNED AERIAL VEHICLES [UAV]; EQUIPMENT THEREFOR
    • B64U10/00—Type of UAV
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04B—TRANSMISSION
    • H04B7/00—Radio transmission systems, i.e. using radiation field
    • H04B7/14—Relay systems
    • H04B7/15—Active relay systems
    • H04B7/185—Space-based or airborne stations; Stations for satellite systems
    • H04B7/18502—Airborne stations
    • H04B7/18506—Communications with or from aircraft, i.e. aeronautical mobile service
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
    • H04L41/06—Management of faults, events, alarms or notifications
    • H04L41/0654—Management of faults, events, alarms or notifications using network fault recovery
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
    • H04L41/06—Management of faults, events, alarms or notifications
    • H04L41/0654—Management of faults, events, alarms or notifications using network fault recovery
    • H04L41/0668—Management of faults, events, alarms or notifications using network fault recovery by dynamic selection of recovery network elements, e.g. replacement by the most appropriate element after failure
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L67/00—Network arrangements or protocols for supporting network services or applications
    • H04L67/01—Protocols
    • H04L67/12—Protocols specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B64—AIRCRAFT; AVIATION; COSMONAUTICS
    • B64U—UNMANNED AERIAL VEHICLES [UAV]; EQUIPMENT THEREFOR
    • B64U2201/00—UAVs characterised by their flight controls
    • B64U2201/10—UAVs characterised by their flight controls autonomous, i.e. by navigating independently from ground or air stations, e.g. by using inertial navigation systems [INS]
    • B64U2201/102—UAVs characterised by their flight controls autonomous, i.e. by navigating independently from ground or air stations, e.g. by using inertial navigation systems [INS] adapted for flying in formations

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Aviation & Aerospace Engineering (AREA)
  • Remote Sensing (AREA)
  • General Physics & Mathematics (AREA)
  • Physics & Mathematics (AREA)
  • Mechanical Engineering (AREA)
  • Astronomy & Astrophysics (AREA)
  • Medical Informatics (AREA)
  • General Health & Medical Sciences (AREA)
  • Computing Systems (AREA)
  • Health & Medical Sciences (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Automation & Control Theory (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

本发明提供了一种基于最小树形图的无人机编队通信拓扑的重构方法及系统，该方法包括：监听广播通信信道，判断编队中的无人机是否出现通信故障；在所述无人机出现通信故障时，根据通信故障的类型修改编队通信图；计算修改后的编队通信图的最小树形图，根据计算结果，重构无人机编队通信拓扑。通过在所述无人机出现通信故障时，根据通信故障的类型修改编队通信图，以及计算修改后的编队通信图的最小树形图以重构无人机编队通信拓扑，实现了在检测到通信故障之后，快速重构通信拓扑以避免发生UAV碰撞事故并恢复编队队形。

Description

基于最小树形图的无人机编队通信拓扑的重构方法及系统
技术领域
本发明涉及无人机通信技术领域，尤其涉及一种基于最小树形图的无人机编队通信拓扑重构方法及系统。
背景技术
在巡航阶段，所有无人机(UAV)使用初始的最优通信拓扑以保持一定的编队队形朝目标区域飞行。此通信拓扑中的通信链接只是UAV之间所有可用的通信链接集合的一部分，即有部分通信链接是没有被使用的，称之为冗余通信链接。由于机械故障或外界干扰等原因，编队飞行过程中某个或多个UAV可能会发生通信故障，使得当前通信拓扑中的某些通信链接不能够被使用，从而导致UAV不能继续保持编队队形，严重时甚至会导致UAV碰撞事故。因此，如何通过重构无人机编队通信拓扑，即选择某些冗余通信链接来代替原有通信拓扑中那些不能被使用的通信链接，以避免发生UAV碰撞事故并恢复编队队形成为了亟需解决的技术问题。
发明内容
针对现有技术中的缺陷，本发明提供了一种基于最小树形图的无人机编队通信拓扑重构方法及系统，实现了在检测到通信故障之后，快速重构通信拓扑以避免发生UAV碰撞事故并恢复编队队形。
第一方面，本发明提供了一种基于最小树形图的无人机编队通信拓扑的重构方法，包括：
监听广播通信信道，判断编队中的无人机是否出现通信故障；
在所述无人机出现通信故障时，根据通信故障的类型修改编队通信图；
计算修改后的编队通信图的最小树形图，根据计算结果，重构无人机编队通信拓扑。
可选的，所述根据通信故障的类型修改编队通信图，包括：
在无人机的广播发射机或广播接收机出现故障时，将所述编队通信图中该无人机的对应节点和该节点的所有边删除；
在无人机的单播发射机出现故障时，将所述编队通信图中该无人机的对应节点的所有出边删除；
在无人机的单播接收机出现故障时，将所述编队通信图中该无人机的对应节点的所有入边删除；
在第一无人机到第二无人机的通信链接出现故障时，将所述编队通信图中第一无人机的对应节点到第二无人机的对应节点的边删除。
可选的，在根据通信故障的类型修改编队通信图之后，所述方法还包括：
在所述修改后的编队通信图中，若无人机的对应节点被删除或无人机的对应节点的所有边被删除，则所述无人机关闭自身的单播发射机，并脱离编队。
可选的，所述编队通信图为增加虚拟领航者节点和该虚拟领航者节点到所有候选的编队领航者的对应节点的边之后的编队通信图；
相应的，计算修改后的编队通信图的最小树形图，根据计算结果，重构无人机编队通信拓扑，包括：
若所述最小树形图存在，则将所述最小树形图中的虚拟领航者节点和相关边删除，得到重构后的无人机编队通信拓扑。
第二方面，本发明还提供了一种基于最小树形图的无人机编队通信拓扑的重构系统，包括：
判断模块，用于监听广播通信信道，判断编队中的无人机是否出现通信故障；
编队通信图修改模块，用于在所述无人机出现通信故障时，根据通信故障的类型修改编队通信图；
计算模块，用于计算修改后的编队通信图的最小树形图；
编队通信拓扑重构模块，用于根据计算结果，重构无人机编队通信拓扑。
可选的，所述编队通信图修改模块，用于：
在无人机的广播发射机或广播接收机出现故障时，将所述编队通信图中该无人机的对应节点和该节点的所有边删除；
在无人机的单播发射机出现故障时，将所述编队通信图中该无人机的对应节点的所有出边删除；
在无人机的单播接收机出现故障时，将所述编队通信图中该无人机的对应节点的所有入边删除；
在第一无人机到第二无人机的通信链接出现故障时，将所述编队通信图中第一无人机的对应节点到第二无人机的对应节点的边删除。
可选的，所述系统还包括：
单播发射机关闭模块，用于在所述修改后的编队通信图中无人机的对应节点被删除或与无人机的对应节点的所有边被删除时，关闭所述无人机的单播发射机，并向所述无人机发送脱离编队的信号。
可选的，所述编队通信图为增加虚拟领航者节点和该虚拟领航者节点到所有候选的编队领航者的对应节点的边之后的编队通信图；
相应的，所述编队通信拓扑重构模块，用于：
在所述最小树形图存在时，将所述最小树形图中的虚拟领航者节点和相关边删除，得到重构后的无人机编队通信拓扑。
由上述技术方案可知，本发明提供一种基于最小树形图的无人机编队通信拓扑重构方法及系统，通过在所述无人机出现通信故障时，根据通信故障的类型修改编队通信图，以及计算修改后的编队通信图的最小树形图以重构无人机编队通信拓扑，实现了在检测到通信故障之后，快速重构通信拓扑以避免发生UAV碰撞事故并恢复编队队形。
附图说明
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些图获得其他的附图。
图1为本发明一实施例提供的基于最小树形图的无人机编队通信拓扑的重构方法的流程示意图；
图2为本发明一实施例提供的基于最小树形图的无人机编队通信拓扑的重构系统的结构示意图。
具体实施方式
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
图1示出了本发明实施例提供的一种基于最小树形图的无人机编队通信拓扑重构方法的流程示意图，如图1所示，该方法包括以下步骤：
101、监听广播通信信道，判断编队中的无人机是否出现通信故障。
102、在所述无人机出现通信故障时，根据通信故障的类型修改编队通信图；
103、计算修改后的编队通信图的最小树形图，根据计算结果，重构无人机编队通信拓扑。
上述方法通过在所述无人机出现通信故障时，根据通信故障的类型修改编队通信图，以及计算修改后的编队通信图的最小树形图以重构无人机编队通信拓扑，实现了在检测到通信故障之后，快速重构通信拓扑以避免发生UAV碰撞事故并恢复编队队形。
上述步骤102中所述根据通信故障的类型修改编队通信图，包括以下几个方面：
在无人机的广播发射机或广播接收机出现故障时，将所述编队通信图中该无人机的对应节点和该节点的所有边删除；
在无人机的单播发射机出现故障时，将所述编队通信图中该无人机的对应节点的所有出边删除；
在无人机的单播接收机出现故障时，将所述编队通信图中该无人机的对应节点的所有入边删除；
在第一无人机到第二无人机的通信链接出现故障时，将所述编队通信图中第一无人机的对应节点到第二无人机的对应节点的边删除。
在步骤102中根据通信故障的类型修改编队通信图之后，所述方法还包括：
在所述修改后的编队通信图中，若无人机的对应节点被删除或无人机的对应节点的所有边被删除，则所述无人机关闭自身的单播发射机，并脱离编队。
其中，所述编队通信图为增加虚拟领航者节点和该虚拟领航者节点到所有候选的编队领航者的对应节点的边之后的编队通信图。
相应的，上述步骤103中计算修改后的编队通信图的最小树形图，根据计算结果，重构无人机编队通信拓扑，包括：
若所述最小树形图存在，则将所述最小树形图中的虚拟领航者节点和相关边删除，得到重构后的无人机编队通信拓扑。
在对上述方法进行详细说明之前，首先对UAV形成和保持编队队形的编队控制方法以及编队通信拓扑进行说明。
UAV形成和保持编队队形的编队控制方法主要有四种：领航-跟随者策略(leader-follower strategy)、虚拟结构策略(virtual structure strategy)、行为策略(behavioral strategy)、一致性策略(consensus-based strategy)。其中，领航-跟随者策略最为成熟，它的基本思想是：编队中的只有一个UAV作为编队领航者(formationleader)，它按照预定的编队参考航迹飞行；其余UAV作为跟随者(follower)，它们直接或间接地跟随编队领航者，比如：一个UAV可能直接跟随编队领航者，也可能跟随另外一个直接或间接跟随编队领航者的UAV。如果第i个无人机UAVi直接跟随第j个无人机UAVj，UAVi称为UAVj的跟随者，UAVj称为UAVi的领航者。UAVj会每隔Tcontrol秒通过点对点的通信链接向UAVi发送自己的位置、速度和方向信息。当UAVi接收到这些信息后，将据此来调整自身的速度和方向以实现和UAVj之间保持预期的相对位置。当所有的UAV都能实现和其领航者保持预期的相对位置时，就实现了编队队形的保持。
假设n个UAV使用领航-跟随者策略来形成和保持一个编队队形S，S中的n个位置分别编号为{1,2,…,n}，每个UAV可以位于S中的任意一个位置，某几个UAV但并不是所有的UAV可以作为编队领航者(这些UAV又被称为候选的编队领航者)，每个UAV可以通过点对点通信链接和其它任意UAV进行信息交互，每个通信链接的通信代价由其相应的通信距离决定。因此，可以用一个加权有向图G＝(V,E,W,P)来表示编队中UAV之间所有可用的通信链接，并简称为编队通信图：
(1)V＝{vi},1≤i≤n是图中的节点集合，其中vi表示第i个无人机UAVi。
(2)1≤i,j≤n是图中的边集合，其中eij表示从UAVi到UAVj有一个可用的通信链接从而使得UAVi能发送信息给UAVj，即UAVi可以成为UAVj的领航者。
(3)W＝{w(eij)},eij∈E是图中每条边的权值集合，其中w(eij)表示eij的通信代价。
(4)P＝{pi},1≤i≤n是每个UAV在编队队形S的具体位置集合，简称为UAV位置配置(UAV position configuration)，其中pi表示UAVi在S中的具体位置。
根据前面的描述可知，每个UAV只需要从其领航者接收信息和发送信息给其跟随者，这意味着不需要使用所有可用的通信链接就可以实现编队队形的形成和保持，其中所使用的通信链接的集合被称为UAV编队的通信拓扑(communication topology)，没有被使用的通信链接被称为冗余通信链接。因此，UAV编队的通信拓扑A＝(V,E*,W*,P)是其编队通信图G＝(V,E,W,P)的一个特殊子图，其中 令w(A)表示通信拓扑A的通信代价，即有通信拓扑A具有如下两个特性。
定理1:基于领航-跟随者策略的UAV编队的通信拓扑A必须是其编队通信图G的一棵生成树(spanning tree)，但是其编队通信图G的一棵生成树并不一定能作为其通信拓扑。
定理2:基于领航-跟随者策略的UAV编队的通信拓扑A必须是其编队通信图G的一棵生成树(spanning tree)，并且其根节点所表示的UAV必须能够作为编队领航者；反之亦然。
由于机械故障或外界干扰等原因，编队飞行过程中某个或多个UAV可能会发生通信故障，使得当前通信拓扑中的某些通信链接变得不可用，从而导致UAV不能继续保持编队队形，严重时甚至会导致UAV碰撞事故。因此，需要通过重构无人机编队通信拓扑，即选择某些冗余通信链接来代替原有通信拓扑中那些不可用的通信链接，以避免发生UAV碰撞事故并恢复编队形；又由于不同的通信链接具有不同的通信代价，因此需要选择合适的冗余通信链接以保证重构后的通信拓扑对应的编队通信代价(即重构后的通信拓扑中的通信链接的代价之和)最小。
因此，通信故障下的通信拓扑重构问题就是找到删除出现通信故障的节点或边之后的编队通信图G的一棵满足如下条件的生成树：具有最小的通信代价并且其根节点代表的UAV能够作为编队领航者。本实施例将此问题建模为图论中的最小树形图(minimum costarborescence，MCA)问题，即求解一个加权有向图的最小生成树。求解MCA问题的第一个算法是Edmonds算法，其计算复杂度为O(|E|×|V|)，后来Gabow等人又提出了一个针对Edmonds算法的更快的实现，其计算复杂度为O(|E|+|V|×log|V|)。
下面通过具体的实施例对本发明提出的一种基于最小树形图的无人机编队通信拓扑重构方法进行详细说明：
通信故障发生之后，通信拓扑重构的执行必须是分布式的以获得更短的执行时间，并且所有UAV的计算结果必须保持一致，因此所有UAV必须及时地获知到同样的通信故障信息。为此，基于现有技术中的方法，假设每个UAV都能使用一个广播通信信道(broadcast communication channel，BC)来获得同样的通信故障信息：(1)每个UAV都有一个单播发射机(unicast transmitter)和一个单播接收机(unicast receiver)以进行点对点通信，每个UAV都有一个广播发射机(broadcast transmitter)和一个广播接收机(broadcast receiver)以通过BC进行广播通信。(2)每个UAV每隔Tactive秒会通过BC上报其状态。(3)当一个UAV检测到某个通信故障时，它会立即通过BC通知其他UAV。
除了现有技术中考虑的四种通信故障外，还考虑另外两种通信故障：广播发射机故障(broadcast transmitter failure)和广播接收机故障(broadcast receiverfailure)。所有六种通信故障类型如表1所示。
表1
针对此六种通信故障，假设所有UAV具有同样的如下所述的通信故障诊断策略：
(1)当UAVi发生单播发射机故障、单播接收机故障、单播收发机故障或者广播接收机故障中的任何一种通信故障时，UAVi自身能够检测到此故障，UAVi将记录下此故障发生时的时间戳并通过BC将此故障和相应的时间戳信息通知其他UAV。
(2)当UAVi发生广播发射机故障时，UAVi自身能够检测到此故障但不能通过BC通知其他UAV，Tactive秒之后，其他UAV由于不能收到UAVi上报的状态将判定UAVi出现了广播发射机故障，并记录下此故障发生时的时间戳。
(3)当eij出现链接中断并且UAVi是UAVj的领航者，UAVj将不能接收到UAVi发送的位置、速度和方向信息.Tactive秒之后，如果UAVj自身没有发生单播接收机故障并且没有通过BC收到UAVi的单播发射机故障信息，UAVj将判定eij出现了链接中断，然后UAVj将记录此故障的时间戳，然后通过BC此故障和相应的时间戳信息通知其他UAV。
(4)如果一个UAV在Tactive秒之内接收到两个及以上的通信故障信息，则只处理时间戳最早的那个通信故障，而把剩余的通信故障留到下一个Tactive秒再去处理。这样可以避免UAV之间的决策出现冲突，从而使得所有UAV能够得到一致的通信故障处理结果。
基于上述的通信故障诊断策略，每个UAV能够及时地获得通信故障的信息，然后每个UAV可以删除编队通信图G中出现故障的边或者节点，再运行Edmonds算法来获得G的最小树形图A。如果A的根节点vi代表的UAV能够作为编队领航者，则A是一个可行的通信拓扑，即所有UAV可以重构通信拓扑为A以继续保持编队队形；否则A不是一个可行的通信拓扑，即所有UAV不能使用A来保持编队队形，但这种情况下并不代表一定不存在另外一个可行的通信拓扑。为了解决这个问题，本实施例首先在原有的编队通信图G上添加一个称为虚拟领航者(Virtual Leader，VL)的特殊节点和其相应的具有特定权值的出边，从而形成一个新的编队通信图G’＝(V’,E’,W’,P’)：
(1)V'＝{v0}∪V是图G’的节点集合，其中v0是虚拟领航者VL，其代表了预定编队参考航迹中的一个虚拟点。
(2)E'＝{e0k}∪E,1≤k≤n是图G’的边集合，其中e0k表示第k个无人机UAVk知道预定编队参考航迹，即UAVk是候选的编队领航者。
(3)W'＝{w(e0k)}∪W,e0k∈E'是图G’的每条边的权值集合，其中v0的所有出边都具有同样的权值即w(e0k)比原有的编队通信图G中的所有边的权值之和还要大1。
(4)P＝{pi},1≤i≤n是每个UAV在编队队形S的具体位置集合，简称为UAV位置配置(UAV position configuration)，其中pi表示UAVi在S中的具体位置。
基于G’的定义，可以得出如下结论。
定理3:如果新的编队通信图G’的最小树形图A’存在并且A’中v0只有一条出边，则在原有的编队通信图G基础上的编队的最优通信拓扑A存在，并且它是A’中删除v0和v0的出边之后的结果。
然后，基于以上分析，本实施例提出了一个分布式的基于最小树形图的通信故障下的通信拓扑重构算法，如表2所示。当通信故障发生时每个UAV将会执行此算法，以UAVi为例，当它通过BC从其他UAV接收到一个通信故障通知或者检测到自身发生通信故障时，它就会运行此算法。
表2
每个UAV执行此算法后，编队中剩余的UAV将迅速切换到重构后的通信拓扑以恢复编队队形。此算法的运行时间主要由Step7所决定，而Step7中使用的是Gabow等人提出的Edmonds算法的更快实现，因此本实施例提出的通信故障下的通信拓扑重构算法的计算复杂度为O(|E'|+|V'|×log|V'|)，其中|E'|≤|E|+|V|，|V'|≤|V|+1。和现有的通信故障下的通信拓扑重构算法相比，此算法具有如下优点：
(1)时间复杂度更低。
(2)重构后的通信拓扑对应的编队通信代价更小。
(3)能够处理更多的通信故障类型。
图2示出了本发明一实施例提供的一种基于最小树形图的无人机编队通信拓扑重构系统的结构示意图，如图2所示，该系统包括：
判断模块21，用于监听广播通信信道，判断编队中的无人机是否出现通信故障；
编队通信图修改模块22，用于在所述无人机出现通信故障时，根据通信故障的类型修改编队通信图；
计算模块23，用于计算修改后的编队通信图的最小树形图；
编队通信拓扑重构模块24，用于根据计算结果，重构无人机编队通信拓扑。
在本实施例的一个优选的实施方式中，所述编队通信图修改模块，用于：
在无人机的广播发射机或广播接收机出现故障时，将所述编队通信图中该无人机的对应节点和该节点的所有边删除；
在无人机的单播发射机出现故障时，将所述编队通信图中该无人机的对应节点的所有出边删除；
在无人机的单播接收机出现故障时，将所述编队通信图中该无人机的对应节点的所有入边删除；
在第一无人机到第二无人机的通信链接出现故障时，将所述编队通信图中第一无人机的对应节点到第二无人机的对应节点的边删除。
在本实施例的一个优选的实施方式中，所述系统还包括：
单播发射机关闭模块，用于在所述修改后的编队通信图中无人机的对应节点被删除或与无人机的对应节点的所有边被删除时，关闭所述无人机的单播发射机，并向所述无人机发送脱离编队的信号。
在本实施例的一个优选的实施方式中，所述编队通信图为增加虚拟领航者节点和该虚拟领航者节点到所有候选的编队领航者的对应节点的边之后的编队通信图；
相应的，所述编队通信拓扑重构模块，用于：
在所述最小树形图存在时，将所述最小树形图中的虚拟领航者节点和相关边删除，得到重构后的无人机编队通信拓扑。
需要说明的是，上述系统与上述方法是一一对应的关系，上述方法的实施细节同样适用于上述系统，本实施例不再对上述系统进行详细说明。
本发明的说明书中，说明了大量具体细节。然而，能够理解，本发明的实施例可以在没有这些具体细节的情况下实践。在一些实例中，并未详细示出公知的方法、结构和技术，以便不模糊对本说明书的理解。
类似地，应当理解，为了精简本发明公开并帮助理解各个发明方面中的一个或多个，在上面对本发明的示例性实施例的描述中，本发明的各个特征有时被一起分组到单个实施例、图、或者对其的描述中。然而，并不应将该公开的方法解释呈反映如下意图：即所要求保护的本发明要求比在每个权利要求中所明确记载的特征更多的特征。更确切地说，如下面的权利要求书所反映的那样，发明方面在于少于前面公开的单个实施例的所有特征。因此，遵循具体实施方式的权利要求书由此明确地并入该具体实施方式，其中每个权利要求本身都作为本发明的单独实施例。
本领域技术人员可以理解，可以对实施例中的设备中的模块进行自适应性地改变并且把它们设置在于该实施例不同的一个或多个设备中。可以把实施例中的模块或单元或组件组合成一个模块或单元或组件，以及此外可以把它们分成多个子模块或子单元或子组件。除了这样的特征和/或过程或者单元中的至少一些是互相排斥之处，可以采用任何组合对本说明书(包括伴随的权利要求、摘要和附图)中公开的所有特征以及如此公开的任何方法或者设备的所有过程或单元进行组合。除非另外明确陈述，本说明书(包括伴随的权利要求、摘要和附图)中公开的每个特征可以由提供相同、等同或相似目的的替代特征来代替。
此外，本领域的技术人员能够理解，尽管在此所述的一些实施例包括其它实施例中所包括的某些特征而不是其它特征，但是不同实施例的特征的组合意味着处于本发明的范围之内并且形成不同的实施例。例如，在下面的权利要求书中，所要求保护的实施例的任意之一都可以以任意的组合方式来使用。
本发明的各个部件实施例可以以硬件实现，或者以在一个或者多个处理器上运行的软件模块实现，或者以它们的组合实现。本领域的技术人员应当理解，可以在实践中使用微处理器或者数字信号处理器(DSP)来实现根据本发明实施例的一种浏览器终端的设备中的一些或者全部部件的一些或者全部功能。本发明还可以实现为用于执行这里所描述的方法的一部分或者全部的设备或者装置程序(例如，计算机程序和计算机程序产品)。这样的实现本发明的程序可以存储在计算机可读介质上，或者可以具有一个或者多个信号的形式。这样的信号可以从因特网网站上下载得到，或者在载体信号上提供，或者以任何其他形式提供。
应该注意的是上述实施例对本发明进行说明而不是对本发明进行限制，并且本领域技术人员在不脱离所附权利要求的范围的情况下可设计出替换实施例。在权利要求中，不应将位于括号之间的任何参考符号构造成对权利要求的限制。单词“包含”不排除存在未列在权利要求中的元件或步骤。位于元件之前的单词“一”或“一个”不排除存在多个这样的元件。本发明可以借助于包括有若干不同元件的硬件以及借助于适当编程的计算机来实现。在列举了若干装置的单元权利要求中，这些装置中的若干个可以是通过同一个硬件项来具体体现。单词第一、第二、以及第三等的使用不表示任何顺序。可将这些单词解释为名称。
最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围，其均应涵盖在本发明的权利要求和说明书的范围当中。

Claims (8)

1.一种基于最小树形图的无人机编队通信拓扑的重构方法，其特征在于，包括：
监听广播通信信道，判断编队中的无人机是否出现通信故障；
在所述无人机出现通信故障时，根据通信故障的类型修改编队通信图；
计算修改后的编队通信图的最小树形图，根据计算结果，重构无人机编队通信拓扑。
2.根据权利要求1所述的方法，其特征在于，所述根据通信故障的类型修改编队通信图，包括：
在无人机的广播发射机或广播接收机出现故障时，将所述编队通信图中该无人机的对应节点和该节点的所有边删除；
在无人机的单播发射机出现故障时，将所述编队通信图中该无人机的对应节点的所有出边删除；
在无人机的单播接收机出现故障时，将所述编队通信图中该无人机的对应节点的所有入边删除；
在第一无人机到第二无人机的通信链接出现故障时，将所述编队通信图中第一无人机的对应节点到第二无人机的对应节点的边删除。
3.根据权利要求1所述的方法，其特征在于，在根据通信故障的类型修改编队通信图之后，所述方法还包括：
在所述修改后的编队通信图中，若无人机的对应节点被删除或无人机的对应节点的所有边被删除，则所述无人机关闭自身的单播发射机，并脱离编队。
4.根据权利要求1所述的方法，其特征在于，所述编队通信图为增加虚拟领航者节点和该虚拟领航者节点到所有候选的编队领航者的对应节点的边之后的编队通信图；
相应的，计算修改后的编队通信图的最小树形图，根据计算结果，重构无人机编队通信拓扑，包括：
若所述最小树形图存在，则将所述最小树形图中的虚拟领航者节点和相关边删除，得到重构后的无人机编队通信拓扑。
5.一种基于最小树形图的无人机编队通信拓扑的重构系统，其特征在于，包括：
判断模块，用于监听广播通信信道，判断编队中的无人机是否出现通信故障；
编队通信图修改模块，用于在所述无人机出现通信故障时，根据通信故障的类型修改编队通信图；
计算模块，用于计算修改后的编队通信图的最小树形图；
编队通信拓扑重构模块，用于根据计算结果，重构无人机编队通信拓扑。
6.根据权利要求5所述的系统，其特征在于，所述编队通信图修改模块，用于：
在无人机的广播发射机或广播接收机出现故障时，将所述编队通信图中该无人机的对应节点和该节点的所有边删除；
在无人机的单播发射机出现故障时，将所述编队通信图中该无人机的对应节点的所有出边删除；
在无人机的单播接收机出现故障时，将所述编队通信图中该无人机的对应节点的所有入边删除；
在第一无人机到第二无人机的通信链接出现故障时，将所述编队通信图中第一无人机的对应节点到第二无人机的对应节点的边删除。
7.根据权利要求5所述的系统，其特征在于，所述系统还包括：
单播发射机关闭模块，用于在所述修改后的编队通信图中无人机的对应节点被删除或与无人机的对应节点的所有边被删除时，关闭所述无人机的单播发射机，并向所述无人机发送脱离编队的信号。
8.根据权利要求5所述的系统，其特征在于，所述编队通信图为增加虚拟领航者节点和该虚拟领航者节点到所有候选的编队领航者的对应节点的边之后的编队通信图；
相应的，所述编队通信拓扑重构模块，用于：
在所述最小树形图存在时，将所述最小树形图中的虚拟领航者节点和相关边删除，得到重构后的无人机编队通信拓扑。
CN201610383796.2A 2016-05-27 2016-05-27 基于最小树形图的无人机编队通信拓扑的重构方法及系统 Active CN105871636B (zh)

Priority Applications (2)

Application Number Priority Date Filing Date Title
CN201610383796.2A CN105871636B (zh) 2016-05-27 2016-05-27 基于最小树形图的无人机编队通信拓扑的重构方法及系统
US15/460,369 US9929914B2 (en) 2016-05-27 2017-03-16 Method and system for reconstructing unmanned aerial vehicle formation communication topology based on minimum cost arborescence

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201610383796.2A CN105871636B (zh) 2016-05-27 2016-05-27 基于最小树形图的无人机编队通信拓扑的重构方法及系统

Publications (2)

Publication Number Publication Date
CN105871636A true CN105871636A (zh) 2016-08-17
CN105871636B CN105871636B (zh) 2017-05-03

Family

ID=56675798

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201610383796.2A Active CN105871636B (zh) 2016-05-27 2016-05-27 基于最小树形图的无人机编队通信拓扑的重构方法及系统

Country Status (2)

Country Link
US (1) US9929914B2 (zh)
CN (1) CN105871636B (zh)

Cited By (17)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106909171A (zh) * 2017-05-08 2017-06-30 合肥工业大学 无人‑有人机编队最优通信拓扑生成方法及装置
CN106940567A (zh) * 2017-05-08 2017-07-11 合肥工业大学 无人机编队最优信息交互拓扑生成方法及装置
CN107092273A (zh) * 2017-05-08 2017-08-25 合肥工业大学 无人‑有人机编队通信拓扑启发式优化方法及装置
CN107135104A (zh) * 2017-05-08 2017-09-05 合肥工业大学 无人‑有人机编队信息交互拓扑优化方法及装置
CN107197474A (zh) * 2017-06-22 2017-09-22 合肥工业大学 多无人机协同编队中的通信拓扑容错优化方法及装置
CN107797564A (zh) * 2017-07-04 2018-03-13 合肥工业大学 多无人机协同编队中信息交互拓扑启发式优化方法及装置
CN108513640A (zh) * 2017-03-21 2018-09-07 深圳市大疆创新科技有限公司 一种可移动平台的控制方法以及可移动平台
CN109586966A (zh) * 2018-12-11 2019-04-05 中国科学院计算技术研究所 一种无人系统网络拓扑连通性恢复方法及系统
CN110673649A (zh) * 2019-11-12 2020-01-10 哈尔滨工业大学（深圳） 基于拓扑优化的时变信道下无人机编队一致性控制方法、系统、装置及存储介质
CN110794867A (zh) * 2019-10-18 2020-02-14 合肥工业大学 通信干扰下无人机编队信息交互拓扑智能决策方法和装置
CN111439382A (zh) * 2020-04-14 2020-07-24 上海航天电子有限公司 一种智能组合无人机系统
CN112000108A (zh) * 2020-09-08 2020-11-27 北京航空航天大学 一种多智能体集群分组时变编队跟踪控制方法及系统
CN112039574A (zh) * 2020-06-10 2020-12-04 合肥工业大学 通信干扰下无人机协同中继网络快速重构方法和系统
CN113759962A (zh) * 2021-08-05 2021-12-07 中国科学院地理科学与资源研究所 一种无人机编队的通信重构方法、装置及存储介质
CN114025434A (zh) * 2021-11-05 2022-02-08 江西洪都航空工业集团有限责任公司 一种通信网络拓扑结构自适应重构方法及装置
CN114519276A (zh) * 2022-02-22 2022-05-20 北京华如科技股份有限公司 一种作战实体编队编辑方法及装置
US11610496B2 (en) 2017-03-21 2023-03-21 SZ DJI Technology Co., Ltd. Monitoring method and system

Families Citing this family (20)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11032148B2 (en) * 2016-04-07 2021-06-08 Qualcomm Incorporated Managing network communication of an unmanned autonomous vehicle
CN108983818B (zh) * 2018-08-10 2021-05-11 电子科技大学 基于虚拟结构的无人机队形变换方法
CN109582040B (zh) * 2019-01-25 2021-08-06 中国人民解放军国防科技大学 一种无人机集群队形及性能脆弱性评估方法及系统
CN110286694B (zh) * 2019-08-05 2022-08-02 重庆邮电大学 一种多领导者的无人机编队协同控制方法
CN110398975A (zh) * 2019-09-04 2019-11-01 西北工业大学 一种基于广播式通信架构的领航跟随型多机编队容错控制方法
CN110879608B (zh) * 2019-10-18 2023-02-28 合肥工业大学 不确定环境下无人系统编队快速自适应决策方法和装置
KR102720108B1 (ko) * 2019-11-18 2024-10-22 현대자동차주식회사 자동차 및 그를 위한 군집 주행 제어 방법
CN111290440B (zh) * 2020-04-07 2023-06-20 中国人民解放军海军航空大学 基于双虚拟结构的多无人机编队Standoff跟踪控制及跟踪方法
CN111651705B (zh) * 2020-05-18 2022-05-13 北京航空航天大学 集群编队跟踪控制方法
CN112987776A (zh) * 2020-12-01 2021-06-18 一飞智控(天津)科技有限公司 单机故障返航路径规划方法、系统、无人机及存储介质
CN113110467B (zh) * 2021-04-22 2024-02-02 大连海事大学 一种切换通讯拓扑下无人船编队规划与制导方法及系统
KR102630845B1 (ko) * 2021-05-28 2024-01-30 광주과학기술원 다중 무인 비행시스템 및 그 시스템의 제어방법
CN114089761A (zh) * 2021-11-22 2022-02-25 江苏科技大学 一种基于ros的领航跟随者多无人船编队控制系统及其方法
CN114153228B (zh) * 2021-11-30 2024-04-16 湖南大学 一种有向交互拓扑下无速度测量的四旋翼编队控制方法
CN114326715B (zh) * 2021-12-09 2023-10-03 东南大学 一种变维多智能体系统的编队控制方法与装置
CN114895703B (zh) * 2022-04-29 2024-07-19 北京航空航天大学 基于拓扑优化重构的分布式容错时变编队控制方法及系统
CN115268492B (zh) * 2022-07-22 2024-08-13 成都飞机工业（集团）有限责任公司 一种多无人机协同编队机间防碰撞控制方法
CN116125881B (zh) * 2023-01-05 2024-04-26 北京航空航天大学 一种有向切换拓扑胸鳍拍动式机器鱼编队切换控制方法
CN116149372B (zh) * 2023-04-17 2023-07-07 西北工业大学 一种故障单机的排除方法、系统和应用
CN116954266B (zh) * 2023-09-21 2023-12-08 北京航空航天大学 一种通信约束的无人机编队鲁棒控制方法及系统

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1961531A (zh) * 2004-02-16 2007-05-09 克里斯多佛·迈克尔·戴维斯 网络体系结构
CN101043267A (zh) * 2006-03-24 2007-09-26 上海交通大学 弹性光突发环的保护与恢复方法及其装置
CN102571417A (zh) * 2011-12-15 2012-07-11 江苏亿通高科技股份有限公司 动态拓扑的实现方法
CN103777640A (zh) * 2014-01-15 2014-05-07 北京航空航天大学 一种分布式控制无人机群集中分簇编队方法
CN105353766A (zh) * 2015-11-10 2016-02-24 合肥工业大学 一种多无人机编队结构的分布式容错管理方法

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101770113B1 (ko) * 2015-08-13 2017-08-22 삼성에스디에스 주식회사 드론의 네트워크 관리 장치 및 방법
US9788260B2 (en) * 2016-02-16 2017-10-10 At&T Intellectual Property I, L.P. Methods and apparatus to network unmanned aerial vehicles (UAVs)
US9848459B2 (en) * 2016-04-06 2017-12-19 Cisco Technology, Inc. Dynamic network connectivity using unmanned aerial vehicles

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1961531A (zh) * 2004-02-16 2007-05-09 克里斯多佛·迈克尔·戴维斯 网络体系结构
CN101043267A (zh) * 2006-03-24 2007-09-26 上海交通大学 弹性光突发环的保护与恢复方法及其装置
CN102571417A (zh) * 2011-12-15 2012-07-11 江苏亿通高科技股份有限公司 动态拓扑的实现方法
CN103777640A (zh) * 2014-01-15 2014-05-07 北京航空航天大学 一种分布式控制无人机群集中分簇编队方法
CN105353766A (zh) * 2015-11-10 2016-02-24 合肥工业大学 一种多无人机编队结构的分布式容错管理方法

Cited By (26)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108513640A (zh) * 2017-03-21 2018-09-07 深圳市大疆创新科技有限公司 一种可移动平台的控制方法以及可移动平台
US11610496B2 (en) 2017-03-21 2023-03-21 SZ DJI Technology Co., Ltd. Monitoring method and system
CN108513640B (zh) * 2017-03-21 2022-01-11 深圳市大疆创新科技有限公司 一种可移动平台的控制方法以及可移动平台
CN106940567B (zh) * 2017-05-08 2020-02-21 合肥工业大学 无人机编队最优信息交互拓扑生成方法及装置
CN107092273B (zh) * 2017-05-08 2020-04-21 合肥工业大学 无人-有人机编队通信拓扑启发式优化方法及装置
CN107135104A (zh) * 2017-05-08 2017-09-05 合肥工业大学 无人‑有人机编队信息交互拓扑优化方法及装置
CN107092273A (zh) * 2017-05-08 2017-08-25 合肥工业大学 无人‑有人机编队通信拓扑启发式优化方法及装置
CN107135104B (zh) * 2017-05-08 2019-10-29 合肥工业大学 无人-有人机编队信息交互拓扑优化方法及装置
CN106940567A (zh) * 2017-05-08 2017-07-11 合肥工业大学 无人机编队最优信息交互拓扑生成方法及装置
CN106909171B (zh) * 2017-05-08 2020-02-21 合肥工业大学 无人-有人机编队最优通信拓扑生成方法及装置
CN106909171A (zh) * 2017-05-08 2017-06-30 合肥工业大学 无人‑有人机编队最优通信拓扑生成方法及装置
CN107197474A (zh) * 2017-06-22 2017-09-22 合肥工业大学 多无人机协同编队中的通信拓扑容错优化方法及装置
CN107797564A (zh) * 2017-07-04 2018-03-13 合肥工业大学 多无人机协同编队中信息交互拓扑启发式优化方法及装置
CN109586966A (zh) * 2018-12-11 2019-04-05 中国科学院计算技术研究所 一种无人系统网络拓扑连通性恢复方法及系统
CN109586966B (zh) * 2018-12-11 2020-08-18 中国科学院计算技术研究所 一种无人系统网络拓扑连通性恢复方法及系统
CN110794867A (zh) * 2019-10-18 2020-02-14 合肥工业大学 通信干扰下无人机编队信息交互拓扑智能决策方法和装置
CN110794867B (zh) * 2019-10-18 2020-10-30 合肥工业大学 通信干扰下无人机编队信息交互拓扑智能决策方法和装置
CN110673649A (zh) * 2019-11-12 2020-01-10 哈尔滨工业大学（深圳） 基于拓扑优化的时变信道下无人机编队一致性控制方法、系统、装置及存储介质
CN110673649B (zh) * 2019-11-12 2022-09-09 哈尔滨工业大学（深圳） 基于拓扑优化的时变信道下无人机编队一致性控制方法、系统、装置及存储介质
CN111439382A (zh) * 2020-04-14 2020-07-24 上海航天电子有限公司 一种智能组合无人机系统
CN112039574A (zh) * 2020-06-10 2020-12-04 合肥工业大学 通信干扰下无人机协同中继网络快速重构方法和系统
CN112000108A (zh) * 2020-09-08 2020-11-27 北京航空航天大学 一种多智能体集群分组时变编队跟踪控制方法及系统
CN113759962A (zh) * 2021-08-05 2021-12-07 中国科学院地理科学与资源研究所 一种无人机编队的通信重构方法、装置及存储介质
CN114025434A (zh) * 2021-11-05 2022-02-08 江西洪都航空工业集团有限责任公司 一种通信网络拓扑结构自适应重构方法及装置
CN114025434B (zh) * 2021-11-05 2024-02-20 江西洪都航空工业集团有限责任公司 一种通信网络拓扑结构自适应重构方法及装置
CN114519276A (zh) * 2022-02-22 2022-05-20 北京华如科技股份有限公司 一种作战实体编队编辑方法及装置

Also Published As

Publication number Publication date
US20170346679A1 (en) 2017-11-30
US9929914B2 (en) 2018-03-27
CN105871636B (zh) 2017-05-03

Similar Documents

Publication Publication Date Title
CN105871636B (zh) 基于最小树形图的无人机编队通信拓扑的重构方法及系统
CN105873171A (zh) 基于最小树形图的无人机编队通信拓扑重优化方法及系统
EP3167571B1 (en) Network topology estimation based on event correlation
CN103703727B (zh) 用于分体式架构系统中控制业务的弹性路由的方法和设备
CN104247344B (zh) 用于拆分式体系结构中快速故障转移的控制器安排
US9769060B2 (en) Simulating, visualizing, and searching traffic in a software defined network
KR101859302B1 (ko) 가상 네트워크 매핑 보호 방법, 시스템 및 컴퓨터 저장 매체
CN107797564A (zh) 多无人机协同编队中信息交互拓扑启发式优化方法及装置
CN105871674B (zh) 环保护链路故障保护方法、设备及系统
CN101160824A (zh) 一种不同级别串接连接监视故障相关性的处理方法和装置
JP2011091464A (ja) ネットワーク構成の想定のための装置、システム
CN106992897A (zh) 多无人机协同编队中的信息交互拓扑优化方法及装置
CN107508632A (zh) 一种同路由光缆故障定位方法和装置
CN103986604A (zh) 网络故障定位方法和装置
Ordoukhanian et al. Resilient multi-UAV operation: key concepts and challenges
CN111884859B (zh) 一种网络故障诊断方法、装置及可读存储介质
CN102281103A (zh) 基于模糊集合解算的光网络多故障恢复方法
EP2709322A1 (en) Node routing method for multi-processor system, controller, and multi-processor system
Imran et al. Application-centric recovery algorithm for wireless sensor and actor networks
JP5687972B2 (ja) 障害リンク特定システムおよびその監視経路設定方法
CN111130850B (zh) 一种故障多层链路恢复方法和控制器
Gupta et al. Fault tolerant wireless mesh network: An approach
CN112866009B (zh) 一种综合服务站虚拟网络故障诊断方法及装置
Halawa et al. Network fabric redundancy in NCS
Falco A smart city internet for autonomous systems

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant