2. 国防科技大学 装备综合保障技术重点实验室, 湖南 长沙 410073
许多系统都可以抽象为复杂网络模型,随着复杂网络的研究逐步深入, 网络级联失效行为[1]和可重构网络[2]由于其现实意义受到广泛关注。网络中一个或多个节点发生的故障, 会通过节点之间的连接关系引起其他节点发生故障, 连锁效应最终导致大部分甚至整个网络崩溃, 这种现象称为级联失效,在交通网络、Internet、电网、无人机集群等都存在这种现象。级联失效的出现让原本具有高关联度的网络设计难度加大。在进行网络结构初始设计时, 不仅要考虑到可能面临冲击的规模和形式, 还要考虑节点间关联度以及失效节点的负载分配[3]与重构。因此, 针对级联失效行为及网络可重构特性进行分析具有重大意义。
近年来, 无人机的协同作战及对抗受到较多关注。无人机自组网设计是未来无人机集群作战的重要研究内容。现有的无人机集群通讯大多采用自组织网络(无人机Ad hoc网络)[4], 其特点在于不完全依赖于地面控制站或者卫星等固定基础通信设施。每台无人机都可作为移动网络节点, 各节点依靠无线通信设备模块实现无线通信的自主管理。而无人机集群网络对数据信息的可靠高速传输有较高要求, 但囿于成本和Ad hoc网络无线多跳路由、网络拓扑结构多变、带宽有限等特性, 无法具有基础设施网络中较为稳定的通讯能力和较大的带宽设置。因此, 基于无人机自组织网络发展现状和一般通用失效模式的假设, 建立通讯模块故障造成的级联失效模型, 并分析和评估无人机通讯网络的性能, 具有重要的理论意义和应用价值。
本文以无人机集群作为研究背景, 该集群自身具有自组织、自适应性, 通讯采用无线通讯[5-6], 是非常典型的可重构网络。在本文中无人机集群由作为节点的无人机和作为边的信息交流通道组成。每个无人机判断不断变化的态势并依据一定的准则调整自己的策略, 进行友方个体间的合作、与敌方的博弈[7]; 从而无人机集群构成了一个可重构、针对特定任务具有级联失效行为的网络。
本文考虑级联失效行为和可重构网络特点, 引入节点最大连接数限制, 提出了一种基于信息载荷分配的多状态级联失效规则与基于概率的动态网络重连规则, 研究级联失效行为的扩散和传播对网络抗毁性影响。
1 无人机集群网络模型 1.1 无人机集群模型概述Tran等[8]提出了无人机集群模型的3个场景: 初始连接阶段、打击阶段以及恢复重连阶段,分别对应打击前、打击完成瞬间、打击之后修复。无人机集群受到攻击有2种方式, 分别是随机移除和定向移除。采用偏好连接算法, 进行无标度网络的构建。同时考虑网络连接和重连的成本, 对不同网络连接模式进行对比。假设给定初始完全连接的节点数为m0, 一个新节点j与网络中已有节点创建m条连接(m≤m0), 则定义节点j与已有节点i连接概率为
(1) |
式中:Nt代表t时刻网络中现有节点数;ki则表示节点i的现有连接数,即节点的度。
在恢复重连阶段, 由于其余节点消失而失去连接的节点j与其他节点进行连接的概率也如(1)式所示。在打击阶段, 无标度网络对于随机移除的攻击模式抗性较高, 但针对定向移除这种移除网络中度值较高的打击行为来说, 无标度网络较为脆弱。
在上述研究基础之上, Barthelemy[9]将距离因素引入连接概率模型中, 基于等式(2)分别提出了不同的调整变量和距离函数。
(2) |
式中:θ表示调整因子;ki表示节点i的现有连接数;F(·)为距离函数,代表物理距离对于无人机集群间的连接状况、信息传输的影响;dj→i表示节点j与i之间的距离。
Bai等[6]考虑到无人机集群具有自组织、自适应的特点, 提出了新的模型: 若在无人机集群中存在孤立节点或孤立分支, 会降低集群的整体性能,并提出了连接概率等式(3)
(3) |
式中:Nt代表网络中现有节点数;ε代表节点度值的调整因子;ki表示节点i的现有连接数即节点度值。函数F(dj→i)如下所示:
(4) |
rc表示通讯范围, dj→i表示节点j与i之间的距离, η表示距离影响因子。需要指出的是, 当
以(1)式偏好连接算法生成的无标度网络, 不可避免地会出现某些度值非常高的节点, 这些节点被称为"Hub"节点[10]。面临随机移除时, "Hub"节点的重要程度并不突出; 而定向打击会定向移除网络中度值较高的节点, "Hub"节点的移除造成集群性能大幅下降, 恢复连接必须承受极高的经济代价和时间成本。
在无人机集群中, 通讯效果是衡量集群工作能力的非常重要的一个指标。现有的无人机集群间通讯模式难以做到大容量的机间信息分发和任意拓扑结构传输, 压缩了集群系统在理论上的最优性能[5]。同时集群内通讯存在多径效应[11-12]的影响, 即多条信息在同一路径传播或单机同一时间接收到多条信息时, 信息间就会相互产生一定程度的干扰或阻塞。
综上所述, 通过添加节点最大连接数限制能减少集群内部通信阻塞,改变集群度分布。因此, 本文提出考虑最大连接数限制的网络构建模型, 其概率连接如(5)式所示
(5) |
式中:最大连接数限制因子δ为ki<ξ的逻辑返回值;ξ是最大连接数, 即网络中每个节点的度值ki都不应该超过ξ; 即节点i的连接数若未达到限制, 则其与节点j便有非零概率建立连接; 而F(dj→i)与(4)式的定义相同。
最大连接数限制因子δ的加入, 增加了节点j处在活跃状态的概率; 当
本文提出的改进模型(见图 2a))与文献[6]模型(见图 2b))给出100个无人机节点完成初始连接时的情况。二者的主要差别具体体现在: ①网络分支数量; ②网络中节点的最大度与网络平均度。
由于最大连接数的限制, 改进模型中不存在连接数超过3的节点, 网络中节点最大度值为3且平均度不超过3;而在文献[6]模型中, 网络中节点最大度值达到了11, 其平均度超过3。网络中节点的最大度越小, 面临定向移除打击时具有更好的鲁棒性[13]。
2 级联失效传播及动态网络重构 2.1 级联失效传播形式Motter与Lai[5]提出了一种基于负载重分配的级联失效定义:
对一给定网络, 其中任2个节点都可以通过二者间相互连接的最短路进行信息或能量交换;每对节点的最短路径经过节点j的次数称为节点j的负载Lj, 同时定义节点的最大负载为这个节点的过载极限Cj。假设节点j的过载极限Cj与其初始负载有如下关系
(6) |
式中,常数μ≥0为容差参数, N为初始的节点数。
现有无人机集群多采用无线通讯作为主要通讯手段。在集群通讯网络中, 级联失效[13]的机理是由于节点过载导致信息的分流, 致使其他节点也有可能发生过载和分流现象;此效应不断传播最终可能导致整个通讯网络的瘫痪, 使集群丧失工作能力。这样的级联失效行为通常会经历3个阶段: 外部扰动、负载分配、过载失效。
2.2 打击事件场景构建无人机集群可能遭遇不同于传统网络定义的节点移除的打击, 存在被病毒、远程控制等手段劫持的可能; 集群中可能会出现被劫持的无人机, 进而影响与其连接的无人机。
基于通讯网络的能量控制, 通讯网络中每单位信息的发送都存在一定能量限制。设置单位信息发送耗用的能量为pi, 其具有一定的强度范围
(7) |
式中, bi为单位信息发送时能量耗损阈值,该值一般是根据集群面向的任务、所需求的通讯强度、续航时长等条件因素综合预设的值。此阈值将会在正常无人机被劫持或失效时发生变化。
当1台无人机被劫持时, 其对集群的影响有2种方式: ①直接物理摧毁;②以远程控制或者注入病毒的方式修改通讯限制参数。对集群而言随机失去单个节点对整个网络影响不大, 而通过修改限制参数bi使得集群因通讯而造成级联失效则后果严重。
2.3 级联失效在无人机集群网络中的传播将无人机集群中的节点状态划分为4种:正常状态G、死亡状态D、失效状态Y和被劫持状态R, 如表 1所示。在一个时段[t, t+1]内, 集群中节点的状态一定且只会是该4种状态中的一个;同时设定节点的状态变迁是瞬间完成的, 节点状态变迁如图 3所示。
正常状态节点G: 可以相互通讯进行信息交流以完成指定任务, 其负载小于过载极限。
被劫持状态节点R: 发送大量无用且优先度较高的信息, 导致相邻节点过载失效, 进而造成级联失效。
失效状态节点Y: 从G状态节点转变而来, 转变的条件为过载失效, 即当G的过载极限C与负载L有C<L的情况发生, G就会转换为Y。
与R节点直接相连的节点在一次负载分配后获得的载荷为
(8) |
式中:RD为被劫持节点负载分配的调整因子;nR为与被劫持节点相连的节点数;LR为被劫持节点在进行负载分配瞬间的负载。
与Y节点直接相连的节点在其进行负载分配后获得的载荷为
(9) |
式中:YD为通讯失效节点负载分配的调整因子;nY为与失效节点相连的节点的数目;LY为失效节点在过载瞬间的负载。图 4和图 5分别给出了被劫持无人机与过载失效无人机的负荷分配机制与状态转移路径。
2.4 动态网络重构假设初始的无人机集群规模为N, 此时集群内每台无人机均处于正常状态, 那么此时的修复概率是最大的, 设其值为P1。设定最低正常状态无人机数目界限Nmin, 仅当遭受打击后正常无人机的数目达到N′G>Nmin时, 失效无人机才有可能得到修复;当N′G≤Nmin时, 失效无人机修复概率均定义为0。
不难得出, 失效无人机修复概率为
(10) |
网络抗毁性描述了网络拓扑结构的可靠性, 通常将网络所能承受的最大节点或边的移除比例称为网络的抗毁性[14]。但利用以往的网络抗毁性的定义, 很难对本文提出的基于动态距离快速变化的无人机集群网络拓扑结构进行评价。
Motter与Lai[5]提出基于最大连通片在级联失效传播后的变化来衡量级联失效对于网络造成的损伤, 从而反映集群的抗毁性的优劣程度
(11) |
式中, N和N′分别代表级联失效传播前后网络中的最大连通片存活节点数目。
本文的无人机集群网络拓扑结构依赖于各无人机间的动态距离, 最大连通片会实时变化; 而一段时间内的最大连通片存活节点数目的平均值指标存在隐藏失效节点变化的风险。因此基于网络中正常状态节点的个数来对网络进行评价显然优于基于最大连通片的节点数目。本文定义当打击事件发生时, 集群能够维持一定的性能同时从该次事件中恢复的能力, 称为该集群的抗毁性。集群的性能体现在正常存活节点的数量上, 因此, 本文采用相对规模这一指标来对网络抗毁性进行评价。当相对规模较大时, 即存活节点数较多, 集群抗毁性就较好;反之集群的抗毁性就相对较差。在本文改进模型中, (11)式中的N和N′分别代表级联失效传播前后网络中的处于正常状态的节点数目。
4 实例仿真 4.1 实验场景设置利用AnyLogic多智能体仿真平台进行动态模型仿真。图 6截取了初始组网后的无人机集群实际状态; 图 7a)表示图 6无人集群初始网络的拓扑结构; 图 7b)表示无人机实际状态变化在网络节点上的对应。
4.2 级联失效传播场景下抗毁性评估实验设计 4.2.1 级联失效传播规则首先将被劫持无人机向周围节点发送无用信息阻塞信道的负载分配方式称为"一次分配"; 失效节点进行负载分配称为"二次分配"。
将无人机现有的负载分为2个部分, 分别是连接负载Ll与分配负载LD, 其中连接负载Ll与其现有连接数即节点度值ki相关;LD为正常无人机从被劫持无人机及失效无人机分配得到的负载。
无人机的过载极限受到每台无人机的固有带宽Lm影响, 其与过载极限关系与(6)式类似
(12) |
式中,μ为负载容差系数。其余参数设置见表 2。
参数 | 含义 | 值 |
N | 集群规模 | 100 |
m1 | 单次打击被劫持无人机数目 | 1 |
RD | 被劫持无人机负载分配系数 | 2 |
YD | 失效无人机负载分配系数 | 1 |
D | 无人机任务执行区域 | 1 000×1 000 |
rc | 通讯距离 | 200 |
η | 距离影响因子 | 0.8 |
ε | 连接数调整因子 | 1 |
Lm | 固有带宽/最大连接负载 | 3 |
C | 过载极限 | 4.2 |
μ | 负载容差系数 | 0.4 |
TR | 被劫持无人机存活时长 | 50 |
TY | 失效无人机修复进程时长 | 50 |
Nmin | 考虑修复情况下最少正常节点数 | 40 |
第1组将负载容差系数μ作为变量, 除与容差系数μ共同变动的过载极限C之外, 其余参数均与表 2相同。最后采集N′, 基于(12)式进行网络遭受级联失效打击前后性能对比评价。
第2组将载荷传播参数RD调整为1, 即初始设置的50%, 该组实验提升了级联失效在网络中传播的难度。
第3组实验将被劫持无人机存活时长TR作为变量, 其他参数均与表 2相同。
第4组实验将通讯距离rc作为变量, 由于rc过小会影响初始网络拓扑结构建立及集群在动态运动中的性能, 让无人机间连接难度更大;出现更多的孤立群体和孤立节点, 此时进行网络的性能评价已经失去了意义。所以设定其实验范围为100至400单位距离。
以上4组实验均未考虑失效无人机的修复情况, 再仿照第1组和第4组实验, 加入失效无人机的修复概率模型, 进行仿真数据的收集;基于第1组考虑修复的实验设为第5组实验;基于第4组考虑的修复实验设为第6组实验, 其余参数均与之前参照的实验参数相同。
4.2.3 级联失效传播影响实验结果及分析图 8a)至8f)为上述6组实验结果折线图,图 8a)在未考虑失效节点修复的情况下, 展示级联失效传播前后网络性能评价指标相对规模S与负载容差系数μ之间的关系。在横轴0~0.2的4组数据中, 由于μ过小, S基本趋近于0, 意味级联失效在网络中的接续传播, 导致了网络中大多数节点的失效;而在二次分配临界极限YD+Lm=4时, 级联失效的影响得到了极大的限制, 相对规模大幅上升而后基本趋于稳定。
图 8b)在未考虑失效节点修复的情况下在第1组实验的基础上, 通过修改级联失效传播系数至之前的一半水平来提高级联失效在集群网络中传播的难度。该实验中有2个临界极限, 分别是μ=0.17时的二次分配极限(YD+Lm)和μ=0.33的一次分配极限(RD+Lm), 可以看到相对规模S在这两处突变, 并在μ增大的过程中一直保持上升趋势。
图 8c)是在未考虑失效节点修复的前提下, 相对规模S与被劫持节点存活时长TR之间的关系;可以观察到当被劫持节点存活时长逐渐增大, 相对规模相应地减小。
图 8d)基于第1组实验, 将通讯距离rc作为与相对规模相关的变量, 其中在rc=150时得到最小值;在此之后相对规模随着通信距离限制的增加而增加。
图 8e)考虑了失效节点的修复, 由于失效节点修复的加入, 在μ=0.33时S值较第1组实验增加25%。
图 8f)与图 8e)类似, 其对照组为图 8d);它表现了考虑修复之后相对规模S与通讯距离rc之间的关系, 相对规模整体得到了提高。
4.2.4 集群规模对于级联失效传播影响基于表 2的参数设置, 针对于集群规模与级联失效传播相关性设计实验, 观察不同集群规模对相对规模的影响。
如图 9所示,当集群规模在0~100内, 集群规模的增大可以有效提升集群打击前后的相对规模,在100处达到了峰值;而在100~200内, 呈现先降后升的趋势, 在N=150左右, 达到了最小值。当集群规模较小时,集群遭受打击后被移除的无人机数量较多。根据修复概率的设定此时集群的修复概率值较小,因此随着多次打击,集群修复能力不断减弱,打击后集群相对规模较小。当集群规模较大时,集群整体冗余度高,遭受打击后状态正常的无人机数量较多,修复概率大,因而集群的修复能力较强。但是当集群规模在100~200时打击前后集群规模出现先降后增的趋势。这是因为级联失效在稠密的集群中连接传播而造成更多的无人机失效。而这一影响在集群规模N=150时达到最高,而后随着N的增加,级联失效的影响逐渐被集群冗余性能抵消。也即,集群规模越大级联失效对网络性能的下降影响越大。但随着时间增加,动态重连使得集群自身的修复能力逐渐增强,网络性能逐渐恢复。
5 结论本文以无人机集群为研究背景,引入了集群节点最大连接数限制,构建了基于概率的集群动态重连规则;以集群通讯网络为研究对象,根据信道阻塞这一现象提出了基于二次载荷分配的级联失效规则,并研究了考虑级联失效与动态重连时集群的抗毁性变化趋势。
通过仿真与数值实验得出如下结论:①为提高集群抗毁性,应根据具体任务优化集群规模;②针对无人机集群通讯网络,应尽量增加单台无人机的固有通讯带宽;③应加快无人机集群中异常个体的识别和清除速度;④在成本允许的情况下,尽量增大通讯范围。
[1] | ZHOU J, HUANG N, COIT W D, et al. Combined effects of load dynamics and dependence clusters on cascading failures in network systems[J]. Reliability Engineering and System Safety, 2018, 170: 116-126. DOI:10.1016/j.ress.2017.10.008 |
[2] | LIU N, JIN Q, WANG D, et al. Reconfigurable network topology design for accelerating parameter server architecture based distributed machine learning[J]. Future Generation Computer Systems, 2020, 106: 320-332. DOI:10.1016/j.future.2020.01.004 |
[3] |
王正武, 况爱武, 王贺杰. 考虑级联失效的交通网络节点重要度测算[J]. 公路交通科技, 2012, 29(5): 96-101.
WANG Zhengwu, KUANG Aiwu, WANG Hejie. Calculation of node important degree for traffic network considering cascading failure[J]. Journal of Highway and Transportation Research and Development, 2012, 29(5): 96-101. (in Chinese) DOI:10.3969/j.issn.1002-0268.2012.05.016 |
[4] |
徐义桂, 陈维义, 吕玉萍. 无人机集群作战通信自组网的关键技术探讨[J]. 无线互联科技, 2019, 16(2): 7-8.
XU Yigui, CHEN Weiyi, LYU Yuping. Discussion on key technologies of UAV cluster combat communication AD-HOC network[J]. Wireless Internet Technology, 2019, 16(2): 7-8. (in Chinese) DOI:10.3969/j.issn.1672-6944.2019.02.004 |
[5] | MOTTER A, LAI Y C. Cascade-based attacks on complex networks[J]. Physical Review E, 2002, 66(6): 065102. DOI:10.1103/PhysRevE.66.065102 |
[6] | BAI G, LI Y, FANG Y, et al. Network approach for resilience evaluation of a UAV swarm by considering communication limits[J]. Reliability Engineering and System Safety, 2020, 193: 106602. DOI:10.1016/j.ress.2019.106602 |
[7] |
罗德林, 张海洋, 谢荣增. 基于多agent系统的大规模无人机集群对抗[J]. 控制理论及应用, 2015, 32(11): 1498-1504.
LUO Delin, ZHANG Haiyang, XIE Rongzeng. Unmanned aerial vehicles swarm conflict based on multi-agent system[J]. Control Theory & Applications, 2015, 32(11): 1498-1504. (in Chinese) |
[8] | TRAN H T, DOMERCANT J C, MAVRIS D N. A network-based cost comparison of resilient and robust system-of-systems[J]. Procedia Computer Science, 2016, 95: 126-133. DOI:10.1016/j.procs.2016.09.302 |
[9] | BARTHELEMY M. Crossover from scale-free to spatial networks[J]. Europhysics letters, 2002, 63(6): 915. |
[10] |
王林, 江秀萍, 柯熙政. 关于无标度网络中Hub节点的研究[J]. 计算机应用, 2010, 11: 208-210.
WANG Lin, JIANG Xiuping, KE Xizheng. Research on hub nodes in scale-free net works[J]. Journal of Computer Applications, 2010, 11: 208-210. (in Chinese) |
[11] |
朱林, 方胜良, 王劲松, 等. 面向体系作战的空间通信网络级联失效模型[J]. 系统仿真学报, 2018, 30(6): 2144-2152.
ZHU Lin, FANG Shengliang, WANG Jinsong. Space communication network cascading failure model oriented system combat[J]. Journal of System Simulation, 2018, 30(6): 2144-2152. (in Chinese) |
[12] | FENG D, JIANG C, LIM G, et al. A survey of energy-efficient wireless communications[J]. IEEE Communications Surveys & Tutorials, 2013, 15(1): 167-178. |
[13] | ALBERT R, JEONG H, BARABÁSI A L. Error and attack tolerance in complex networks[J]. Nature, 2000, 406: 382-387. DOI:10.1038/35019025 |
[14] |
吴俊, 谭跃进. 复杂网络抗毁性测度研究[J]. 系统工程学报, 2005, 20(2): 128-131.
WU Jun, TAN Yuejin. Study on measure of complex network invulnerability[J]. Journal of Systems Engineering, 2005, 20(2): 128-131. (in Chinese) |
2. Laboratory of Science and Technology on Integrated Logistics Support, National University of Defense Technology, Changsha 410073, China