一种增强复杂网络抵御相继故障能力的路由算法研究*

刘笑辰，朱 磊，夏 苏（解放军理工大学通信工程学院，江苏南京210007）

一种增强复杂网络抵御相继故障能力的路由算法研究*

刘笑辰，朱 磊，夏 苏
（解放军理工大学通信工程学院，江苏南京210007）

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

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

O 引言

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

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

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

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

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

1.1 算法的基本思想

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

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

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

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

式（3）的计算将在下节中讨论。根据式（3）可以得到虚拟耗费因子向量，从而得到eij的虚拟耗费：

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

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

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

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

（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增大，拟合曲线的斜率也相应增大。

图1 耗费因子计算结果

2 实验仿真及结果研究

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

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

图2 无标度网络发生相继故障后平均传输效率的变化

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

图3 小世界网络发生相继故障后平均传输效率的变化

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

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

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

图4 无标度网络本文算法与参考文献［2］中算法效果比较

图5 小世界网络中本文算法与参考文献［2］算法比较

3 结论

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

［1］BARABÁAIA L，ALBERT R.Emergence of sca1ing in random networks［J］.Science，1999，286（5439）：509-512.

［2］WANG J.M itigation strategies on sca1e-free networks against cascading fai1ures［J］.Physica A：Statistica1Mechanics and Its APP1ications，2013，392（9）：2257-2264.

［3］CHEN D，LV L，SHANG M S，et a1.Identifying inf1uentia1 nodes in comP1ex networks［J］.Physica A：Statistica1Mechanics and Its APP1ications，2012，391（4）：1777-1787.

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

［5］ZHANG X，ZHU J，WANG Q，et a1.Identifying inf1uentia1 nodes in comP1ex networks with community structure［J］. Know1edge-Based Systems，2013，42（2）：74-84.

［6］SCHNEIDER C M，YAZDANI N，ARAUJO N A，et a1.Towards designing robust couP1ed networks［J］.Scientific Re-Ports，2011，3（24）：1-7.

［7］BRUMM ITT C D，D'SOUZA R M，LEICHT E A.SuPPressing cascades of 1oad in interdePendent networks［J］.Proceedings of he Nationa1Academy of Sciences，2012，109（12）：680-689.

［8］ALBERTO L G，INDRA W.Communication networks：fundamenta1 concePts and key architectures［M］.New York：Mc GrawHi11，2000.

［9］WATTS D J，STROGATZ S H.Co11ective dynamics of‘sma11-wor1d'networks［J］.Nature，1998（393）：440-442.

［10］MOTTER A E，LAIY C.Cascade-based attacks on comP1ex networks［J］.Physica1Review E，2002，66（6）：114-129.［11］LATORA V，MARCHIORI M.Efficient behavior of sma11-wor1d networks［J］. Physica1 Review Letters，2001，87 （19）：198701-1-4.

刘笑辰（1990 -），通信作者，男，硕士在读，主要研究方向：通信网、复杂网络。E-mai1：1iuxiaochenyt@163.com。

朱磊（1973 -），男，博士，教授，主要研究方向：网络管理、复杂网络、数据工程。

夏苏（1990 -），女，硕士在读，主要研究方向：通信网、复杂网络。

An imProved routing a1gorithm for enhancing the resistance to cascading fai1ures in comP1ex networks

Liu Xiaochen，Zhu Lei，Xia Su
（Co11age of Communications Engineering，PLA University of Science and Techno1ogy，Nanjing 210007，China）

There are usua11y some critica1nodes in comP1ex networks，which wi11 cause cascading fai1ures quite easi1y when these nodes suffer de1iberate attacks.This Phenomenon great1y reduces the re1iabi1ity of the networks.Many researches Pay attention to enhance the resistance of critica1nodes.In order to imProve the resistance of networks to cascading fai1ures we imProve the existing routing a1gorithm.We reduce the ro1e of critica1nodes and try to ba1ance the 1oad distribution.The exPeriments in tyPica1networks show that the imProved routing a1gorithm can enhance the resistance of networks to cascading fai1ures significant1y.

comP1ex network；cascading fai1ure；routing a1gorithm；network re1iabi1ity

TN915

A

10.19358 /j.issn.1674-7720.2016.09.021

刘笑辰，朱磊，夏苏.一种增强复杂网络抵御相继故障能力的路由算法研究［J］.微型机与应用，2016，35（9）：70-73，77.

江苏省自然科学基金（BK20141071）

2016-01-14）