一种无人机集群数字孪生仿真系统网络连通性修复方法转让专利
申请号 : CN202111159152.2
文献号 : CN113612528B
文献日 : 2022-01-18
发明人 : 雷磊 , 李志林 , 宋晓勤 , 蔡圣所 , 王成华 , 张莉涓 , 周建江 , 朱晓浪
申请人 : 南京航空航天大学
摘要 :
权利要求 :
1.一种无人机集群数字孪生仿真系统网络连通性修复方法,其特征在于,所采用的步骤是:
步骤1:由每个分区中剩余能量最多的无人机利用机载计算机求得每个分区的候选代表节点集合;
求分区候选代表节点的步骤如下:步骤1.1:根据心跳包的坐标信息,将纵坐标最小的无人机坐标作为凸包的起始点P0,并令P0为原点,构建坐标系;
步骤1.2:计算各个点相对于P0的幅角α,按幅角从小到大的顺序对各个点排序,当α相同时,距离P0近的排在前面,得到所有节点的排序结果,由几何知识可以知道,排序结果中第一个点和最后一个点一定是凸包上的点,把它们压入栈,然后将第一个点后面的点作为当前点;
步骤1.3:连接P0和栈顶的那个点,得到直线L,判断当前点是在直线L的右边还是左边,如果在直线的右边就执行步骤1.4;如果在直线上,或者在直线的左边就执行步骤1.5;
步骤1.4:如果在右边,则栈顶的那个元素不是凸包上的点,把栈顶元素出栈,执行步骤
1.3;
步骤1.5:当前点是凸包上的点,把它压入栈,执行步骤1.6;
步骤1.6:检查当前点是不是步骤1.2排序结果的最后一个元素,如果是,则求分区凸包结束,如果不是,则把当前点压入栈,把当前点后面那个点作为新的当前点,并返回执行步骤1.3;
求得每个分区的凸包后,凸包上的点就是分区候选代表节点,以所有凸包上的候选代表节点中的任意节点作为起始节点生成最小生成树,将最小生成树上的节点编号构成的集合记作U,表示全部分区的候选代表节点集合;
步骤2:利用基于“切线避障”的斯坦纳树方法计算出存在障碍物时的中继部署链路的无人机坐标,首先利用四边形斯坦纳树算法修复代表节点连通,如果集合U中还有未连通的代表节点,接着利用三角形斯坦纳树算法修复代表节点连通,如果此时已经实现代表节点全连通,则算法结束,否则一定还剩一个代表节点没有实现连通,因此只需要从已连通的代表节点中选择一个最近的代表节点,将两者连接即可实现代表节点全连通,在利用四边形和三角形斯坦纳树算法修复代表节点连通性时,需要另外判断斯坦纳点和代表节点间是否存在障碍物,如果不存在障碍物,可以直接部署中继节点,否则需要利用“切线避障”算法实现中继节点的避障部署;
步骤3:根据调度选择因子,从非代表节点集合中选择合适的无人机,利用虚拟势场法对被选择的无人机进行调度,使被选择的无人机飞到指定的中继节点位置,从而快速实现全网的连通性恢复;
调度节点的选取和移动步骤如下:步骤3.1:初始化非代表节点集合I中所有无人机为可调度;
步骤3.2:选取中继节点坐标集合C中的第一个中继节点坐标,记为C1,接着从集合I中选取所有可调度的无人机,依次计算它们的调度选择因子,最后求出调度选择因子最小的无人机j,无人机j就是C1的调度无人机,最后将I中编号为j的无人机标记为不可调度;
步骤3.3:从集合C中依次选取剩余的中继节点坐标,并求出其所对应的用于调度的中继无人机;
步骤3.4:在求得每一个中继节点坐标和用于调度的无人机后,将用于调度的无人机的坐标设置为起点,中继节点坐标为终点后,在虚拟势场法作用下,调度无人机向中继节点坐标运动,最后到达中继节点实现网络的连通性恢复。
2.根据权利要求1所述的一种无人机集群数字孪生仿真系统网络连通性修复方法,其特征在于:所述步骤2中构造基于“切线避障”的斯坦纳树的具体方法为:斯坦纳点的求解方法如下:
定义代表节点A,B,C,D构成的四边形ABCD为非退化凸四边形,找到对角α小于90°,其对应的两条边为AD,BC,对AD和BC向外作正三角形ADE和BCF,并连接两个正三角形的另外两个顶点E和F,最后再分别作正三角形ADE和BCF的外接圆,与直线EF分别相交于S1和S2两点,则S1和S2即为四边形斯坦纳点,记A,D两点的坐标分别为(xA, yA),(xD, yD),则AD所在直线的夹角可以表示为
(1)
记A,D两点之间的距离为
(2)
已知正三角形ADE中A,D两点坐标,第三点E的坐标计算公式为(3)
已知正三角形两点求第三点,会存在两个解,此处选择距离线段BC更远的解E,其坐标为 (xE, yE),同理可计算出正三角形BCF中的F点坐标(xF, yF),已知E,F两点坐标,直线EF的方程可以表示为:
(4)
正三角形ADE的外接圆圆心坐标记为 (5)
外接圆半径记为
(6)
则正三角形ADE外接圆OADE的标准方程为 (7)
联立式(4)和(7)可以得出直线EF和圆OADE的交点坐标,其中一交点是E点,另一交点是斯坦纳点S1;
连接代表节点与斯坦纳点,即可得到中继部署链路,如果斯坦纳点和代表节点间存在障碍物,则利用“切线避障”算法实现中继节点的避障部署;
“切线避障”算法如下:
假设节点Q1、Q2的中继节点部署链路与障碍物直线连接时相交,圆形障碍物的圆心为O,首先在线段Q1 Q2所在圆心的同侧寻找Q1,Q2两点与圆O的切点,记为Q3,Q4,线段Q1 Q3+ 弧Q3 Q4+ 线段Q4 Q2即为Q1,Q2两点间的最短中继节点部署链路,然后在线段Q1 Q3和线段Q4 Q2线段上按照通信半径r的距离部署无人机,并在圆O的周长上沿着弧Q3 Q4按照同样的方式部署中继无人机。
3.根据权利要求1所述的一种无人机集群数字孪生仿真系统网络连通性修复方法,其特征在于:所述步骤3中计算可调度无人机节点j其调度因子的具体方法为:(8)
其中,Ci表示中继节点i坐标,Ij表示编号为j的可用于调度的无人机的节点度,Ei,j表示中继节点i的坐标和编号为j的可用于调度的无人机节点坐标之间的欧拉距离,λ1和λ2分别为距离权重和节点度权重系数,值均在0到1之间,且和为1,在不同的任务场景中,可以通过改变λ1和λ2为无人机的调度做出最优选择。
说明书 :
一种无人机集群数字孪生仿真系统网络连通性修复方法
技术领域
背景技术
功能分布化的多智能体系统,通过多个无人机之间的协同效应,完成单架无人机难以应对
的复杂任务,极大的丰富了无人机的应用场景。近年来,无人机集群已成为了民用和军用领
域的研究热点之一。
于机器学习的协同控制算法。研究人员在设计这些算法之后,通常都是通过仿真的手段来
验证算法的性能,并对算法进一步改进。然而,现有的仿真技术手段多采用数值模拟法,缺
乏物理世界环境状态数据的支撑,仿真有效性差,无法反映集群协同控制算法在物理世界
的真实性能,大大增加了集群协同控制算法由仿真应用到现实的难度。
信息域。信息域集成多维物理实体的数据,通过建模和分析,最终形成多学科、多物理量、多
时间尺度、多概率的仿真,从而近乎实时地呈现物理实体在真实场景中的全生命周期过程,
并通过虚实交互接口对物理实体进行控制。数字孪生技术为无人机集群协同控制算法的仿
真验证提供了新思路。通过在信息域构建无人机集群物理实体的高保真孪生模型,获取集
群物理实体的实时状态信息,并在决策模型中实现待验证的集群协同控制算法,可以实现
对集群协同控制算法的高保真仿真验证,优化集群协同控制算法。综上可知,无人机集群数
字孪生仿真系统将是未来实现集群智能协同的重要保障。
仿真系统的可靠性。例如,由于地形障碍以及外在干扰的存在,无人机集群出现分区,即部
分无人机与汇聚无人机(用于和地面基站传输数据)的通信链路断开。部分无人机的信息未
能传输给汇聚无人机,导致集群数字孪生仿真系统接收到的信息不全面,无法为集群协同
控制算法提供准确的物理状态信息,仿真可靠性下降。由此可见,网络连通性修复对无人机
集群数字孪生仿真系统的仿真可靠性至关重要。
制。当网络遭到破坏而形成分区时,最重要的是如何部署最少的中继节点恢复网络的全连
通,其中斯坦纳树是最常见的解决方案。斯坦纳树与最小生成树类似,是最短网络的一种。
最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给
定点外增加额外的点,使生成的最短网络开销最小。针对无人机集群的高移动性特点和面
向任务的特性,如何以低开销,高效率和高连通性的方法实现拓扑管理显得十分重要。目前
大多数现有的中继节点部署方法都是直接添加额外的中继节点,但是在无人机集群网络
中,部署额外中继无人机不仅极大地增大开销和时间,在某些情况下,还可能因为无人机数
量不够或者因为环境因素不可达等原因造成部署失败。同时相比较于一般的无线传感器网
络,无人机集群网络对于拓扑管理后的网络连通性要求更高,因为更高的网络连通性意味
着网络有更高的二次抗毁性,对于处于复杂地形环境下的无人机集群网络这一点十分重
要。
发明内容
性。
中第一个点和最后一个点一定是凸包上的点,把它们压入栈,然后将第一个点后面的点作
为当前点;
1.5;
步骤1.3;
的集合记作U,表示全部分区的候选代表节点集合;
通的代表节点,接着利用三角形斯坦纳树算法修复代表节点连通,如果此时已经实现代表
节点全连通,则算法结束,否则一定还剩一个代表节点没有实现连通,因此只需要从已连通
的代表节点中选择一个最近的代表节点,将两者连接即可实现代表节点全连通,在利用四
边形和三角形斯坦纳树算法修复代表节点连通性时,需要另外判断斯坦纳点和代表节点间
是否存在障碍物,如果不存在障碍物,可以直接部署中继节点,否则需要利用“切线避障”算
法实现中继节点的避障部署;
快速实现全网的连通性恢复;
的无人机j,无人机j就是C1的调度无人机,最后将I中编号为j的无人机标记为不可调度;
点坐标运动,最后到达中继节点实现网络的连通性恢复。
两个顶点E和F,最后再分别作正三角形ADE和BCF的外接圆,与直线EF分别相交于S1和S2两
点,则S1和S2即为四边形斯坦纳点,记A,D两点的坐标分别为(xA, yA),(xD, yD),则AD所在直
线的夹角可以表示为
线EF的方程可以表示为:
弧Q3 Q4+ 线段Q4 Q2即为Q1,Q2两点间的最短中继节点部署链路,然后在线段Q1 Q3和线段Q4
Q2线段上按照通信半径r的距离部署无人机,并在圆O的周长上沿着弧Q3 Q4按照同样的方式
部署中继无人机。
分别为距离权重和节点度权重系数,值均在0到1之间,且和为1,在不同的任务场景中,可以
通过改变λ1和λ2为无人机的调度做出最优选择。
附图说明
具体实施方式
态信息在内的集群参数和环境数据,并通过连接通道发送给集群孪生仿真系统,为集群协
同控制算法的仿真验证提供高保真的物理世界状态数据。考虑到复杂地形环境的干扰及无
人机高速运动的特点,集群网络拓扑快速动态变化,无线传输链路容易断开。如果集群孪生
仿真系统接收到的观测数据不完整,无法为集群协同控制算法提供准确的物理状态信息,
仿真可靠性下降。由此可见,网络连通性修复对无人机集群数字孪生仿真系统的仿真可靠
性至关重要。
通信,每个无人机都可以作为中继无人机将数据包中继到它的邻居节点。
下就会导致网络产生分区,无人机集群与集群孪生仿真系统之间的连接通道出现漏洞,影
响集群孪生仿真系统的仿真有效性。假设有一个由N架具有移动和定位能力的无人机构成
的无人机集群通信网络,其中有一架汇聚无人机,负责周期性的和集群孪生仿真系统通信。
如附图2所示,在某一时刻,由于障碍物或者外在的电子干扰,无人机集群通信网络分割成M
个分区。本方法提出一种无人机集群数字孪生仿真系统网络连通性修复方法,目标是以更
少数量的中继节点、更高的平均节点度,和更少的开销实现多个分区的连通性恢复。
形就是非退化四边形。
无人机后,由每个分区中剩余能量最多的无人机利用机载计算机根据Graham扫描法求得每
个分区的凸包。
识可以知道,结果中第一个点P1和最后一个点P4一定是凸包上的点。已经知道了凸包上的第
一个点P0和第二个点P1,把它们放在栈里面。然后将P1后面的点P2作为当前点。
1.5。
连通,则算法结束,否则一定还剩一个代表节点没有实现连通,因此只需要从已连通的代表
节点中选择一个最近的代表节点,将两者连接即可实现代表节点全连通。在利用四边形和
三角形斯坦纳树算法修复代表节点连通性时,需要另外判断斯坦纳点和代表节点间是否存
在障碍物,如果不存在障碍物,可以直接部署中继节点,否则需要利用“切线避障”算法实现
中继节点的避障部署。
另外两个顶点E和F,最后再分别作正三角形ADE和BCF的外接圆,与直线EF分别相交于S1和S2
两点,则S1和S2即为四边形斯坦纳点。附图5在附图4的基础上添加了两个障碍物(灰色圆
圈),中继节点标记为黑色圆点。
圆,两个外接圆在三角形内部的交点S即为斯坦纳点。附图7在附图6的基础上添加了两个障
碍物(灰色圆圈),中继节点标记为黑色圆点。
标,直线EF的方程可以表示为:
机个数也是最少的。
Q1 Q2所在圆心的同侧寻找Q1,Q2两点与圆O的切点,记为Q3,Q4。线段Q1 Q3+ 弧Q3 Q4+ 线段Q4
Q2即为Q1,Q2两点间的最短中继节点部署链路,接下来只需要按照无人机的通信半径r在中
继节点链路上部署中继无人机即可。首先在线段Q1 Q3和线段Q4 Q2线段上按照通信半径r的
距离部署无人机,接着在圆O的周长上沿着弧Q3 Q4按照同样的方式部署中继无人机。
实现全网的连通性恢复。
势场中相互作用的结果。虚拟势场法的基本思想是将环境抽象为虚拟势场,无人机在虚拟
力的作用下运动。如附图9所示,无人机所受的力可分为三种类型:导航力、拓扑力、避障力。
导航力驱动无人机到达指定的点,该点可以是路径计划中的一个临时点,也可以是整个运
动的终点。拓扑力不仅对保持集群的拓扑结构起着关键作用,而且能有效避免无人机之间
的碰撞事故。避障力阻碍了集群向障碍物的运动。将上述三种力进行矢量相加,则可以计算
出无人机在虚拟势场中,最终受到的虚拟力合力 为:
分别为距离权重和节点度权重系数,值均在0到1之间,且和为1。在不同的任务场景中,可以
通过改变λ1和λ2为无人机的调度做出最优选择。
就是C1的调度无人机,最后将I中编号为j的无人机标记为不可调度。
标运动,最后到达中继节点实现网络的连通性恢复。
通信范围默认设置为250m。为了数据的可靠性和真实性,针对不同的分区个数和通信半径
的情况,随机产生了50种拓扑情况,圆柱形障碍物(半径为150米)随机部署在其中,并计算
其平均值作为最后的数据。附图10和附图11给出了随着分区数量逐渐上升的条件下,本发
明提出的无人机集群数字孪生仿真系统网络连通性修复方法与现有网络连通性修复方法
仿真结果的对比。由附图10和附图11所示的仿真结果可以看出,本发明提出的无人机集群
数字孪生仿真系统网络连通性修复方法相较于现有方法需要的中继节点更少,中继节点的
移动距离更短,提高了中继效率。