刘笑辰，朱磊，夏苏

　　（ 解放军理工大学 通信工程学院，江苏 南京 210007）

　　摘要：在现实生活中，许多大型的通信网络或电力网络都可以应用复杂网络进行刻画。然而网络中某些“关键节点”一旦遭到攻击极易引发相继故障。这种现象的存在极大降低了网络的可靠性。为了提高网络对相继故障的抵御能力，针对现有基于最短路径的路由算法加以改进，降低“关键节点”在网络中所起的作用，提高了网络负载在各节点间分布的均衡性。通过在典型的复杂网络上进行的仿真实验，证明了改进的路由算法能够大大增强网络对相继故障的抵御能力。

　　关键词：复杂网络；相继故障；路由算法；网络可靠性

0引言

　　现实生活中的诸多网络比如电力网、通信网、交通网以及社交网等都可以用复杂网络模型进行描述。Albert等人提出复杂网络中的相继故障现象［1］，即网络中极少数所谓的“关键节点”遭到破坏将引起连锁反应，导致整个网络呈现雪崩式毁坏。相继故障的存在对社会生活的正常运行构成了极大的威胁。

　　为了减少相继故障的危害，提高网络的可靠性，许多学者进行了卓有成效的研究。参考文献［2］按照一定的规则在网络中选择某些节点执行一次防御策略，如果被保护的节点负载超过阈值则将额外的负载分配给邻居从而避免本身发生故障。参考文献［3-5］注重在网络中发现在相继故障过程中更加重要的节点。由于在现实中，往往多个网络相互作用形成一个耦合的整体，参考文献［6-7］在耦合网络中挖掘重要组成部分并且设计出负载分配策略。

　　在当前复杂网络相继故障的防御策略研究中，大多数学者着眼于发现网络中起到关键作用的节点或组成部分，而缺少对网络中路由算法的改进以提高网络的可靠性。本文通过对现有基于最短路径的路由算法加以改进，将网络拓扑结构的影响体现到传输链路的效率中，降低复杂网络中节点负载的异质性，进而提高网络对相继故障的抵御能力。

1基于最短路径路由算法的改进研究

　　在计算网络中的源节点到目的节点最短路径的过程中，节点间链路的传输耗费是一个关键的参数。本文通过对节点间传输的实际耗费进行修正得到虚拟耗费，然后根据虚拟耗费计算节点之间的最短路径。通过虚拟耗费的计算降低经过度数大的节点的路径数目，从而降低这些节点的负载，进而减少各节点负载之间的异质性使得网络更加健壮。

　　1.1算法的基本思想

　　令网络G中各节点之间的邻接矩阵为A，其中aij为其中的一个元素，并有：

　　其中eij表示节点i与j之间的连边。

　　假设网络中的节点数为n，存在实际耗费因子向量Cr=(λr1,λr2,λr3…λrn)表示各节点对相邻的边传输实际耗费的影响，其中λri为节点i的实际耗费因子，根据节点的实际耗费因子可得边eij传输的实际耗费为：

　　crij=λri·λrj·aij(2)

　　考虑到复杂网络中各节点间度数分布的异质性，为了防止网络中度数大的节点承担过多的负载，根据节点的度数对其实际耗费因子进行修正得到节点的虚拟耗费因子。令节点i的虚拟耗费因子为：

　　λvi=f(λri,ki)(3)

　　式(3)的计算将在下节中讨论。根据式(3)可以得到虚拟耗费因子向量Cr=(λv1,λv2,λv3…λvn)，从而得到eij的虚拟耗费：

　　cvij=λvi·λvj·aij(4)

　　根据网络的虚拟耗费矩阵计算各节点之间传输的最短路径，可以采用Floyd、BellmanFord、SPFA等算法［8］得到网络间节点传输的路由表。运用上述方法得到的结果可以有效降低网络中度数大的节点的负载，提高各节点间负载的均衡性。

　　1.2节点虚拟耗费因子的计算

　　节点的虚拟耗费因子由该点的度数和实际耗费因子决定。在计算节点度的影响时做出如下假设：

　　(1)假设每个节点存在虚拟负载，节点i的负载为lvi  = logk ki，其中ki为节点i的度数，k表示网络中节点的平均度。

　　(2)每个节点在单位时间内可以处理的负载与该节点的度数成正比，并且其比例系数与节点的虚拟负载成反比。

　　(3)整个网络在单位时间内能够处理掉所有节点中的虚拟负载。

　　对于假设(1)，由于在一个完好的网络中不存在孤立的节点，即所有节点的度数都大于等于1，故虚拟负载lvi可以保证有意义；对于假设(2) ，考虑度数大的节点能够与更多的节点进行交流并且算法的最终目的在于均衡节点间的虚拟耗费因子，由上述假设可以得到以下方程组：

　　方程①的左侧表示所有节点单位时间内处理的虚拟负载，其中1表示负载传递给节点本身，βi·ki表示负载传递给周围的邻居；方程的右侧表示网络中所有节点的虚拟负载之和。并有当kj=0时所对应的βj=0。

　　计算方程(5)可以得到：

　　对于节点i而言，最终该点的虚拟耗费因子为：

　　其中h是一个可调参数，该值越大则算法对关键节点作用的削弱就越大。

　　图1表示了在初始实际耗费因子向量Cr(0)=(1,1,1,…,1)时3个不同的无标度网络中节点的虚拟耗费因子与度数的关系。网络1中初始节点个数为7，每次新增加的节点连边数为3，算法中h=0.2。网络2中初始节点个数为8，每次新增加的节点连边数为6，算法中h=0.2 。网络3中初始节点个数为8，每次新增加的节点连边数为6，算法中h=0.6。从图中可以看出，在各节点实际耗费因子相同的情况下，节点的度数越大其虚拟耗费因子就越大。通过网络2与网络3的对比可以发现，参数h增大，拟合曲线的斜率也相应增大。　

2实验仿真及结果研究

　　在仿真实验中，本文分别在BA无标度网络［1］及WS小世界网络［9］中对改进的路由算法的效果进行研究。本文应用参考文献［10］中的相继故障模型，并且令对任意节点i均有λri(0)=1。文中采用平均传输效率E(G)衡量网络状态 ［11］。E(G)越大表示网络在单位时间内传输能力越强，即网络状态越好。

　　图2是3种不同的无标度网络发生相继故障后网络的效率变化。图中网络1表示应用基于最短路径路由算法的网络，网络2表示应用改进路由算法的网络。横坐标表示初始时刻网络中负载最大的前n个节点发生故障，纵坐标表示网络的平均传输效率。图2无标度网络发生相继故障后平均传输效率的变化

　　图(a)、(b)、(c)中的网络初始节点数分别为4、6、8，每个新增加节点的连边数为3、5、6。各网络的节点总数均为1 000。实验选取网络中初始负载最大的若干个节点使之发生故障，并记录发生相继故障后经过30个时间单位后网络的平均传输效率E(G)。结果表明，随着初始故障节点的增多，网络的平均传输效率都会降低。但是在采用传统的路由算法的网络中，网络平均效率下降的速度非常快并且在3种情况下最终都接近于0，即网络已经完全崩溃。在应用改进后的路由算法的网络中，尽管网络的效率也发生了下降，但相比而言其下降速率非常缓慢，根据图2(b)、(c)，在已有15个节点发生故障的情况下，网络仍然保持着相当程度的平均效率，而与其相对的传统网络已经完全崩溃。在图2中，采用改进路由算法的网络的初始平均传输效率要略小于传统的网络，但其结果却大大增强了网络对相继故障的抵抗能力。

　　图3记录了3种不同的小世界网络发生相继故障后的变化。图中网络1表示应用基于最短路径路由算法的网络，网络2表示应用改进路由算法的网络。图(a)、(b)、(c)中网络的平均度分别为4、6、8。各网络随机连边的效率为0.4，节点总数均为1 000。实验同样使网络中初始负载最大的一些节点发生故障。结果显示在WS网络中，改进的路由算法能够明显增强网络对相继故障的抵御能力。在应用改进路由算法的网络中，数目较少的故障节点对网络造成的危害非常轻微。在图3(b)、(c)中可以看出，当小世界网络的平均度数增大时，应用改进路由算法的网络具有更强健壮性。

　　在无标度网络中将本文提出的路由改进算法与参考文献［2］中提供的方法进行比较，两种策略增强网络抵御相继故障能力的效果如图4所示。图中的数据均为网络发生相继故障后的结果。图中网络R表示应用本文改进路由算法的网络；网络P表示应用参考文献［2］中增强网络健壮性方法的网络，其中α表示网络中采用防御策略的节点占总节点的比例。图4(a)、(b)中的网络初始节点数分别为4、8，每个新增加节点的连边数为3、6。各网络的节点总数均为1 000。

　　从图4可以看出，在网络中初始故障节点较少时，本文提出的算法与参考文献［2］中80%的节点采取保护措施所达到的效果相当。但是本文改进的算法并不需要对网络中的节点提出特殊的要求，从经济的角度来讲本文算法更优。值得注意的是，随着网络中故障节点的增多，应用本文所提算法的网络对相继故障抵抗能力下降较快，其在这一点上表现不如参考文献［2］中的策略。

　　在小世界网络中将本文提出的路由改进算法与参考文献［2］中提供的方法进行比较，图5记录了两种策略增强网络抵御相继故障能力的效果。图中的数据均为网络发生相继故障后的结果。网络R表示应用本文改进路由算图5小世界网络中本文算法与参考文献［2］算法比较法的网络；网络P表示应用参考文献［2］中增强网络健壮性方法的网络，α表示网络中采用防御策略的节点占总节点的比例。图5(a)、(b)中的网络的平均度分别为4、6。各网络随机连边的概率为0.4，网络中的节点总数为1 000。从图中可以看出在小世界网络中与参考文献［2］中的方法比较，本文所提出的改进路由策略同样能得到良好的效果。

3结论

　　在复杂网络中存在若干“关键节点”，这些节点对网络的正常运行发挥着重要的作用。然而一旦这些节点遭受攻击则极易引发相继故障。为了减少相继故障的发生，提高网络的可靠性，本文对现有的路由算法加以改进。通过降低网络中度数大的节点的重要性，使得网络中各节点的负载分布更加均衡，从而减少了“关键节点”在网络中发挥的作用，进而增强了网络对蓄意攻击的抵御性能。通过在BA无标度网络及WS小世界网络中进行的实验，验证了在故障节点数不多的情况下改进的路由算法能够大大提高网络对相继故障的抵御能力。但是当网络中初始故障节点数增多时改进路由算法的效果下降比较明显，同时由于改进路由算法的应用，致使网络的初始传输效率有所降低，这也体现了网络的可靠性与有效性之间的辩证关系。

参考文献

　　［1］ BARABAI A L, ALBERT R. Emergence of scaling in random networks［J］. Science, 1999, 286（5439）: 509512.

　　［2］ WANG J. Mitigation strategies on scalefree networks against cascading failures［J］. Physica A: Statistical Mechanics and Its Applications, 2013, 392（9）:22572264.

　　［3］ CHEN D, LV L， SHANG M S， et al. Identifying influential nodes in complex networks［J］. Physica A: Statistical Mechanics and Its Applications,2012, 391(4): 17771787.

　　［4］ 任卓明, 邵凤, 刘建国, 等. 基于度与集聚系数的网络节点重要性度量方法研究［J］. 物理学报, 2013（12）:522526.

　　［5］ ZHANG X, ZHU J, WANG Q, et al. Identifying influential nodes in complex networks with community structure［J］. KnowledgeBased Systems, 2013, 42(2): 7484.

　　［6］ SCHNEIDER C M, YAZDANI N, ARAU＇JO N A, et al. Towards designing robust coupled networks［J］. Scientific Reports, 2011，3(24)： 17.

　　［7］ BRUMMITT C D, D’SOUZA R M, LEICHT E A. Suppressing cascades of load in interdependent networks［J］. Proceedings of the National Academy of Sciences, 2012, 109(12):680689.

　　［8］ ALBERTO L G, INDRA W. Communication networks: fundamental concepts and key architectures［M］. New York: Mc GrawHill, 2000.

　　［9］ WATTS D J, STROGATZ S H. Collective dynamics of ‘smallworld’networks［J］. Nature, 1998(393):440442.

　　［10］ MOTTER A E, LAI Y C. Cascadebased attacks on complex networks［J］. Physical Review E, 2002, 66(6):114129.