邢彪;曹军海;宋太亮;陈守华;董原生
【摘 要】Considering the limitations of needs of acquiring the global information for cascading failures in most traditional networks,the influences of weighting strategies and neighbor nodes degree on cascading failure were considered and a cascading failure model with tunable parameters was established to analyze the robustness of the complex network.Cascade phenomena were studied on four typical networks (NW,WS,BA,ER) for numerical simulation and theoretical analysis,and the feasible and applicability of the proposed model is verified.%针对传统的大多数级联失效模型均需要获知网络全局信息的局限性,在基于节点度函数的级联失效模型基础上,综合考虑节点加权策略和节点的邻居节点度对级联失效的影响,构建加权条件下基于节点扩展度的带有可调权重参数的复杂网络级联失效鲁棒性分析模型.对该模型在4种典型网络(NW,WS,BA,ER)上的级联鲁棒性进行仿真分析,验证了该模型的可行性及有效性.冷却塔平衡管
【期刊名称】《计算机工程与设计》
【年(卷),期】2017(038)010
【总页数】6页(P2595-2599,2659)
【关键词】装备保障;复杂网络;级联失效;鲁棒性;加权网络
【作 者】邢彪;曹军海;宋太亮;陈守华;董原生
【作者单位】装甲兵工程学院技术保障工程系,北京100072;装甲兵工程学院技术保障工程系,北京100072;北京理工大学经管学院,北京102205;装甲兵工程学院技术保障工程系,北京100072;装甲兵工程学院技术保障工程系,北京100072
【正文语种】中 文
【中图分类】TP139
E-mail: ********************
网络鲁棒性是指网络在遭受攻击的条件下，能够保持稳定并维持其部分功能的能力[1-4]。
现实中的Internet网、复杂电力网络、城市交通网络等，级联失效一旦发生，都对网络稳定性的影响十分巨大。级联失效(有时也称相继故障)是指网络中节点和边普遍存在耦合关系，当某一个或某一些节点和边失效时，会通过这种耦合关系引发连锁反应，最终导致网络中大面积的节点和边失效，甚至引起整个网络的崩溃。国外Motter[5]、Crucitti等[6,7]、Li和Wang[8]、Lehmann等[9]分别从不同角度对复杂网络的级联失效进行了研究。
国内学者对考虑级联失效的网络鲁棒性也开展了深入研究，建立了针对不同网络的级联失效模型[10-18]，并取得了一些成果。无论是国内还是国外，绝大多数级联失效建模的研究均是在无权网络框架内进行的，无权网络只能给出节点之间是否存在相互作用，无法表示节点之间相互作用强度的差异[17,18]。而现实中的实际网络多为有权网络，目前针对有权网络的级联失效鲁棒性研究较少，且多为节点权重与该节点度单方面相关。
为更好地研究网络节点的加权特性与级联效应的关系，本文提出一种综合考虑节点度与其邻居节点度的加权方法，并构建了一个基于加权负荷重分配原则的级联失效模型，对该模型在一些典型网络(NW，WS，BA，ER)上的级联鲁棒性进行了仿真验证，并进行了仿真分析。结果表明，本文提出的加权方法符合典型网络的级联鲁棒性度量要求，并能在同等条件下使得网络更具鲁棒性。 传统的级联失效模型，普遍采用的是网络中节点的负荷按介数分布，节点失效后的负荷重新分配原则按最短路径重新分布。但存在两点局限性，一是必须知晓网络的全局信息，才能计算网络中每一节点的介数；二是某些实际网络中，重新分配的负荷更倾向于选择能力值高的节点，而不是最近的节点。
假设网络中在初始阶段每个节点都承载一定的负荷，每个节点的初始负荷均小于其处理能力(最大负荷)，网络处于稳定状态，当对其中某一个节点进行攻击致其故障，失效节点上的负荷会分配到邻居节点上。对于邻居节点而言，当它接受的新增负荷加上原有的初始负荷，超出其所能承受最大负荷时，会导致该节点故障，从而导致负荷的再次重新分配,引发级联失效。直至网络中所有节点的负荷均不超出其能力范围时，级联失效结束，网络到达稳定状态。
定义1 节点初始负荷
式中：α、q为可调参数(取值大于0)， (1+q)表示倍乘系数，默认值q=0； α为指数系数，可控制节点初始负荷的强度，α值越大，不同节点初始负荷的差异性也就越大； k为节点的度，表示网络中与该节点直接相连的其它节点数，也称该节点的边数。
定义2 节点负荷重新分配原则。故障节点j上的负荷重新分配至邻居节点i的择优概率为
式中：n表示故障节点j在网络中的所有邻居节点，Γj表示所有这些邻居节点的集合。因此得到节点i新增负荷如式(3)所示
标准车当量数定义3 节点最大负荷
式中：β为容许系数(取值大于0)。显然β越大，该节点C值越大，表示其承载负荷能力值越高，对应现实网络中网络投入的成本越高。当节点i新增负荷加上本身负荷超出最大值时，即
当满足式(5)时节点i失效，并导致网络中负荷的重新分配，产生级联效应。网络中节点失效后的节点负荷局域择优分配如图1所示。
首先无权网络完全可视为加权网络的一种特例，其次加权并不改变网络中的度、介数、聚类系数等局域几何变量，所以无权网络的许多局域几何量的分析、计算等都可以继续在加权网络上应用。
加权网络可用G=(N,W)表示，N为网络中节点总数，W为加权后的邻接矩阵，如果节点i与节点j是相邻节点，则矩阵中用wij表示节点i、j的边(i,j)的权重(本文中边权与网络拓扑结构无关)，如果节点i与节点j不是相邻节点，则wij=0。因此，定义节点i的点权(也称点强度)Si为其邻居关联的边权之和。即
式中：Γi表示节点i的所有邻居节点之和，因此Si既考虑了节点的度，也考虑了与其邻居节点的权重关系，能更系统更综合地反应节点的局域信息。显然当所有权重值w取值均为1时，网络即为无权网络，此时Si=ki。
定义4 加权网络节点初始负荷
自动化测试脚本
式中：α、q为可调参数(取值大于0)，(1+q)表示倍乘系数，默认值q=0； α为指数系数，控制节点初始负荷的强度；S为节点的强度(点加权)。
定义5 节点负荷的重分配原则。在加权网络中，当故障节点j上的负荷需要重新分配至其邻居节点i时，存在择优概率，如式(8)所示
依据择优概率，节点i收到的新增负荷为
定义6 加权网络节点最大负荷
式中：β为容许系数(取值大于0)。同理，当节点i的新增负荷与其本身固有负荷相加超出其可能的最大值时：Li+ΔLij>Ci，节点i失效；随即导致网络中节点负荷重新分配，此时若引起其它节点相继故障，则称网络发生级联失效。
第一节中，网络节点初始负荷为与该节点度相关函数的方法，很好地解决了以往级联失效模型中仅依据节点介数度量初始负荷的局限性；第二节对其扩展，通过对网络进行加权，考虑了节点强度下的级联失效模型。但以上在赋予节点负荷时，均是基于该节点度(或节点强度)的信息，信息量较少，因此本节在进一步考虑节点邻居信息的基础上，提出节点的加权扩展度级联失效模型，考虑邻居节点度对节点负荷的影响。
定义7 加权网络扩展度节点初始负荷
式中：α、q为可调参数，(1+q)表示节点负荷的倍乘系数，一般默认q=0； α则代表指数系数，用来调节控制节点初始负荷的强度； Si为节点i的强度的点权值； km表示节点m的度， Γi表示节点i的所有邻居节点的集合。
定义8 加权网络扩展度条件下的节点负荷重分配原则。同上加权网络扩展度条件下的节点负荷重分配择优概率为
依据择优概率，节点i收到的新增负荷为
毛皮加工定义9 节点的最大负荷及节点故障触发条件同上，分别为：Ci=(1+β)Li； Li+ΔLij>Ci。
(1)失效节点归一化指标ΔNN
在建立的以上级联失效模型中，显然指数参数α与容许系数β均为可调参数。当α与β均为某一定值时，根据级联失效理论,网络中存在某一节点的失效可能引发整个网络的崩溃。因此，用ΔNi表示节点i失效后所引发的网络中其它节点失效的数量。显然0<ΔNi<N-1。所有失效节点的归一化指标如下所示
视频浪涌保护器式中：ΔNN表示在某一固定的参数α与β下，依次移除网络中的每一个节点最终导致的网络中总失效节点的归一化度量。
(2)阈值βc
模型中，当容许系数β值很大时，节点最大负荷值也很大，此时节点的失效不易触发级联效应；反之当β值很小时，任一节点的失效都极易触发网络的级联失效。但是我们也应看到，β值越大网络投入的成本也会随之增加，因此采用βc表示β的阈值，用来度量网络的鲁棒性。βc越小，网络抵制级联失效的鲁棒性越强。
将以上第一节至第三节的模型分别命名为模型一、模型二和模型三，以模型二加权网络为例，βc的理论解析计算值推导过程如下：
当节点j失效，为避免级联失效的发生，对任意节点i新增负荷加上本身负荷均不能超出其最大值
将式(7)～式(10)代入式(15)并进行简化可得
依据网络度的概念可得
将式(6)、式(17)、式(18)代入式(16)并进行简化可得
<w>表示网络中所有边权的平均值，当边权与网络拓扑结构无关时Sw(k)≈<w>*k；<k>表示网络度的平均值。将不等式分别从α>1、 α=1、 α<1这3方面考虑，可得
对于模型三最终推导可得
(3)βc与α的关系
选取4种典型网络：NW小世界网络、WS小世界网络、BA无标度网络、ER随机网络。首先为对比不同网络拓扑结构上指数参数α与关键阈值βc的关联关系，分别对以上4种网络取相同规模，即节点总数N=1000和平均度<k>=4。当<w>=1时，其仿真结果(每个网络的仿真次数均为50次)分别如图2、图3所示。
导游扩音器图2中，当α=1时，βc最小，即此时网络具有最强的抵抗级联失效的鲁棒性；图3中则是当α=0.5时，βc最小，即考虑扩展度的情况下网络在α=0.5时具有最强的抵抗级联失效的鲁棒性。以上两种仿真结果均与理论计算的结果(式(20)与式(21))相吻合，验证了本模型设立的合理性。
