相继故障模型的一种改进

张 昕， 孙江辉， 刘建华

(1.西安邮电大学 信息中心,陕西 西安 710121;2.西安邮电大学 通信与信息工程学院,陕西 西安 710121)

相继故障模型的一种改进

张 昕1， 孙江辉2， 刘建华1

(1.西安邮电大学 信息中心,陕西 西安 710121;2.西安邮电大学 通信与信息工程学院,陕西 西安 710121)

针对复杂网络中存在的相继故障问题，给出一个改进的相继故障模型。在基于耦合映像格子的相继故障模型中引入影响因子，将节点间的相互影响反映在节点的状态变化中，并在两种典型网络中进行仿真分析，结果表明具有较大影响因子的节点易引发相继故障，应作为网络风险控制的重要节点。

复杂网络;相继故障;耦合映像格子；影响因子

网络中的节点间存在耦合关系，当节点发生故障时会引起连锁反应，从而导致其他节点也随之出现故障，甚至进一步恶化导致整个网络瘫痪，这种现象称为相继故障，也叫雪崩[1]。在Internet中，对一些路由器进行攻击会导致系统过载，当网络对流量进行重新路由时，则会引起其他路由器接连过载，继而引发相继故障。因此，基于相继故障模型研究网络节点对周围节点的影响，能够对网络风险进行评估。

研究复杂网络相继故障常见的模型是基于负荷-容量的模型和基于耦合映像格子的模型。目前主要从网络负载以及网络冗余对网络鲁棒性的影响[2]、边级联故障蔓延的动力学演化机制[3]、网络初始负荷的分布与失效后节点负荷的分配规则对相继故障的影响[4]、有向网络耦合映像格子的相继故障模型[5]等方面进行了研究，取得了一些成效。但负荷-容量模型仅研究节点负荷与容量的关系[6-8]，适用范围有限；基于耦合映像格子的模型[9]能反映某一节点失效后对周围节点的影响，但是对于具有同样度分布的节点，却不能反映所引起的相继故障的差异。

根据网络在发生故障时节点的状态变化不仅与自身的度有关，同时还与节点的负载有关，本文在基于耦合映像格子的相继故障模型中引入影响因子，将互相连接的网络节点间的负载关系反应在节点状态的变化中，建立一个改进的模型；此外还通过将阈值倒数定义为风险指标，对网络产出相继故障的风险进行研究。

1 基于耦合映像格子的相继故障模型

对于一个包含N个节点的网络，基于耦合映像格子(Coupled Map Lattice，CML)的相继故障模型[9]为

(1)

其中xi(t)表示第i个节点在t时刻的状态，i=1,2,…,N。k(i)是节点i的度，ε∈(0,1)表示耦合强度，绝对值符号则保证各节点的状态非负。设矩阵A=(aij)N×N表示N个节点的连接信息。若节点i和j之间有边相连，则aij=aji=1；否则aij=aji=0。规定任意不同的两个节点最多只能有一条边相连，且节点不能与自身相连。这样矩阵A就成为一个对称阵，且只有0,1两种元素，其对角线取值均为0。选择混沌Logistic映射f(x)=4x(1-x)作为非线性函数，用以表征节点自身的动态行为。当0≤x≤1时，0≤f(x)≤1。

对于节点i的状态，如果在m个时序内始终满足0m)。

一个有N个节点的网络，其节点状态按式(1)迭代演化，如果所有节点的初始状态都在(0，1)范围内，并且不发生外部扰动，那么网络中的全部节点都将始终维持在正常状态。如果某节点在时刻m受到冲击，即对节点c施加一个外部扰动R≥1,节点状态为

(2)

在这种情况下，节点c的状态xc(m)将满足xc(m)>1，即发生故障，进而对于所有的t>m有xc(t)≡0，即节点不可用。在m+1时刻，所有节点c的邻居节点，都会受到xc(m)的影响，这些节点的状态值可由式(1)得出，此时节点状态值可能大于1而发生故障，从而引起局部或全局相继故障。

2 一种改进的相继故障模型

依据现实计算机风险网络模型，对计算机网络节点的评估不仅要考虑节点自身存在的漏洞等风险，还要考虑该节点对周围节点的影响即考虑相邻两节点之间的互相作用产生的风险，由此给出一种改进的模型。给出如下定义。

定义1 影响因子：相连的两计算机设备节点i和j，在某一时间t，由i发出至j的数据总量与由j发出至i的数据总量的比例定义为节点i对节点j的影响因子，记为σi,j(t)，σi,j(t)>0，反之为σj,i(t)。显然σi,j(t)σj,i(t)=1，并令σi,i(t)≡0。N个节点的动态影响矩阵为Σ(t)=(σi,j(t))N×N。

对于式(1)，改进的模型为

xi(t+1)=

i=1,2,…,N

(3)

对于节点i，在t+1时刻的状态xi(t+1)由当前t时刻的本身状态xi(t)和与节点i相连的所有节点状态共同影响。其中σj,i(t)为t时刻节点j对节点i的影响因子，ε∈(0,1)表示耦合强度，非线性函数f(x)为节点自身动态行为。这里依旧选择混沌Logistic映射f(x)=4x(1-x)。当0≤x≤1时，0≤f(x)≤1。

式(3)中(1-ε)f(xi(t))反应了节点对自身状态的影响，相对于式(1)只考虑了节点间是否有相互连接关系(即节点i的度k(i))对节点状态产生的影响，式(3)中的影响因子σi,j(t)不仅能反映节点间的连接关系，还能量化表示节点j和节点i之间的负荷关系，从而能更好的描述节点的状态变化。

在第m时刻，对某个节点c施加一个外部扰动因子R≥1后，节点状态为

此时xi(m)>1，即节点c发生故障，对于所有的t>m有xc(t)≡0。在第m+1时刻，所有节点c的邻居节点，都将受到xc(m)的影响，其状态值可由式(3)得出。

对于不同的Σ(t)，Rc1和Rc2的值不同，说明了不同的节点出现故障，虽然其出入度情况相同，但其在整个网络中作用不同，因而造成的风险也不同。

3 仿真分析

全耦合网络中的任意两个节点之间都存在连接，是一种理想的网络拓扑，用于研究理想网络状态下的相继故障。而现实中，考虑到系统性能、安全、成本等因素，不可能真正实现全耦合连接。许多网络包括Internet、WWW以及新陈代谢网络等的连接度分布函数具有幂律形式[1,10]，符合无标度网络的特征。幂律分布特性对于 Internet 网络拓扑结构生成以及网络性能改进影响很大，BA 模型从动态增长观点研究复杂网络具有幂律度分布特性的模型,拓扑建模研究中普遍将其作为无标度网络基本模型。BA无标度网络中大部分节点的度很小，同时也存在少量度非常大的节点，这与Internet的拓扑情况十分相似。故将改进模型应用于全耦合网络和BA无标度网络进行仿真。

实验平台为Windows XP Professional，仿真工具使用NetLogo 4.0.4和Matlab 7.0。

3.1 全耦合风险网络

将改进模型应用于具有全耦合性质的风险网络中。

假设一个N=2 000,ε=0.6的全局耦合映像格子(CML)，其影响因子矩阵Σ(t)(关于矩阵主对角线互为倒数)为

其中第一列表示所有节点对第一个节点的影响因子向量，以此类推。

对于给定的网络规模N和耦合强度ε∈(0,1)，节点C存在两个阈值Rc1、Rc2(Rc1

随机选择一个设备节点，施加一个扰动R≥1，重复进行100次实验，平均相继故障规模如图1所示。

图1 随机对一个节点扰动产生的相继故障

由于改进模型中采用影响因子作为权重，因此不同节点抵御相继故障的能力不同。图2所示为对节点943进行扰动，产生相继故障的规模。

图2 对节点943扰动产生的相继故障

对于给定的Σ(t)，计算机设备节点943被攻击或意外而出现故障，节点943对其他节点的影响因子向量为

可计算得出，向量各分量所表示前942个节点的阈值比后1 057个节点阈值大，且前后两组节点的阈值依次递增。从图2中可看出，在RRc2=44.7后，出现全局相继故障。节点943的风险可记为 [1/30.76,1/44.7]。

图3为对节点1357进行扰动，产生相继故障的规模。

图3 对节点1357扰动产生的相继故障

与图2所示相比，只是选取的扰动节点不同，而该节点对其他节点的影响因子向量为

显然∑σ1 357,x<∑σ943,x，因此其它节点抗相继故障的能力增加，说明节点1 357的风险影响较小。由图3可知，两阈值分别为Rc1=34.6，Rc2=51.7，节点1 357风险为[1/34.6,1/51.7]。

由实验可知，在改进模型中度相同的节点由于其对周围节点影响因子的不同，产生相继故障规模也就不同。对于影响因子向量大的节点应重点采取安全防御措施，因为这些节点使得其他节点的抗相继故障能力下降，造成的相继故障规模较大，因而风险大，而对于影响因子小的节点，由于造成的风险小，则可节约成本而采取相应的防御措施。

3.2 BA无标度风险网络

将改进模型应用于具有幂律分布的BA无标度网络中。

根据BA无标度网络生成算法，取m0=2，m=2生成一个BA无标度网络，生成的网络如图4所示。

图4 N=2 000的风险网络

检测生成的网络节点度的分布，其节点度分布p(k)∝1/k3，与BA网络度分布函数2m2k-3接近。

基于BA无标度网络中度分布的非均匀性，引入随机故障和蓄意攻击这两种引发相继故障的策略。前者模拟网络中随机发生的节点故障，初始的扰动施加给随机选择的一个节点；后者模拟网络遭受攻击，攻击者一般总会选择那些相对重要的节点，因此把扰动施加给网络中度最大的节点。

选择度最大的节点对其施加扰动，其影响因子Σ(t)为

影响因子为0表示节点之间没有连接。其相继故障规模如图5所示,Rc1≈1.0，Rc2≈1.5。

图5 过载度最大的节点产生相继故障规模

选择一个一般节点施加扰动，其相继故障规模如图6所示，其中Rc1≈25.0，Rc2≈28.0。由图5和图6可知，其对应的Rc1和Rc2两个阈值小于全耦合网络，并且两阈值之差也较小，说明BA无标度网络抗相继故障的能力比全耦合网络的能力要低很多，因此各个节点所产生的风险相应较大。连接越多，承担较大负荷的节点一旦发生故障，发生相继故障的概率就越大，产生的风险影响就越大。

图6 过载一般节点产生相继故障规模

4 结束语

通过引入反映网络节点间相互作用的影响因子，对基于耦合映像格子的相继故障模型进行了改进，同时也在网络系统中定义了计算机设备节点的风险大小，并在全耦合网络和BA无标度网络中对该改进模型进行了仿真。结果表明，在度相同的情况下，对具有不同影响因子的节点施加扰动，产生的相继故障规模也不相同。同时模型给出的风险指标可用于对网络风险进行评估。

[1] 汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社，2006:72-130.

[2] 徐野,王瑶.复杂网络相继故障的节点动态分析[J].沈阳理工大学学报,2015,34(1):17-21.

[3] 王建伟,蒋晨,孙恩慧.耦合网络边相继故障模型研究[J].管理科学,2014,27(6):132-142.

[4] 段东立.基于负载最近邻偏好分配的复杂网络连锁效应[J].复杂系统与复杂性科学,2015,12(1):33-39.

[5] 马秀娟,马福祥,赵海兴.基于耦合映像格子的有向网络相继故障[J].计算机应用,2011,31(7):1952-1955.

[6] 郭迟,王丽娜,李玉，等.基于负荷-容量模型的网络相继故障研究[J].计算机研究与发展,2012,49(12):2529- 2538.

[7] Moreno Y, Gómez J B, Pacheco A F. Instability of scale-free networks under node-breaking avalanches [J]. Epl, 2002, 58(4):630-636.

[8] Moreno Y, Pastor-Satorras R, Vazquez A, et al. Critical load and congestion instabilities in scale-free networks[J]. Epl, 2002, 62(2):292-298.

[9] Wang X F, Xu J. Cascading failures in coupled map lattices [J]. Physical Review E, 2004, 70(5):056113.

[10] 丁琳,张嗣瀛.复杂网络上相继故障研究综述[J]. 计算机科学,2012,39(8):8-13.

[责任编辑：祝剑]

An improvement of the cascading failure model

ZHANG Xin1， SUN Jianghui2， LIU Jianhua1

(1. Information Center, Xi’an University of Posts and Telecommunications, Xi’an 710121, China; 2. School of Communication and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

An improved cascading failure model in complex networks is proposed in this paper. Some impact factors are introduced into the cascading failure model based on coupled map lattices, thus, the interrelationship of various nodes can be drawn from their status changing. Simulation analysis in two typical networks shows that, the node with greater impact factor is easier to suffer cascading failure, and must be paid more attentions to in networks risk management.

complex network, cascading failure, coupled map lattice(CML)，influence factor

10.13682/j.issn.2095-6533.2015.04.004

2015-04-23

工业与信息化部软科学研究计划资助项目(2014-R-31)

张昕(1979-)，男，硕士，工程师，从事网络管理和网络安全研究。 E-mail: zhxin@xupt.edu.cn 孙江辉(1990-)，男,硕士研究生，研究方向为移动终端的可信计算。E-mail:960259591@qq.com

TP393.0

A

2095-6533(2015)04-0019-05