现实中孤立、单一网络是不存在的,不同网络之间存在千丝万缕的联系,最终形成相依网络。最近几年以来,对相依网络结构和功能的研究取得重大成果,各种模型和理论被提出以更好地解释复杂网络[1-2]。
文献[3]第一次对相依网络的级联故障进行了研究,得出相依网络移除节点时,其渗流过程表现为一阶形式,而单一网络移除节点时的渗流过程表现为二阶形式;文献[4]采用一种新的相依网络的边权重定义方式,提出相依网络的相依边的故障渗流模型,有效解决了相依网络的连边在目的攻击下的级联故障问题;文献[5]通过定义结构信息和攻击信息,提出信息缺失条件下的相依网络的级联故障模型,据此得出不同情况下的渗流阈值,发现相依网络远远比单一网络脆弱;文献[6]对新英格兰电网和WS(Watts-Strogatz)小世界网络模拟负载重分布情况下的级联故障过程,发现高聚类特性和小世界性质导致故障发生的“局部性”,且在高冗余网络中故障局部性现象更显著;文献[7]构建双层指挥控制相依网络模型,通过对小世界网络和无标度网络的故障攻击模拟,发现相依网络在受到恶意攻击时尤其脆弱,各层子网络的平均度越大,相依网络抵制故障能力越强;文献[8]对相依网络进行回顾,并以经济网络为例解释故障如何对相依网络产生作用;文献[9]提出一种基于邻居节点的负载分配方法和故障主动恢复模型,表明网络结构对降低级联故障规模极其重要;文献[10]和[11]分别提出二维方格网络的级联故障模型和不同耦合方式、强度的相依网络模型,表明相依网络较单一网络脆弱和不同参数对相依网络的不同影响。
上述研究成果相当丰富,但对相依网络的故障研究集中于以下2个不同方面:1) 不考虑负载对级联故障的影响,仅考虑相依边的作用;2) 不考虑相依边的作用,直接将各个子网耦合成的相依网络视作一个整体考虑负载的作用,负载分配采用局部分配原则。基于此,本文同时考虑相依边和负载对相依网络的级联故障的影响:初始子网内考虑负载的作用,负载采用全局分配原则,而子网之间考虑相依边的作用,进而对不同耦合网络模拟和分析。
1 相依网络的级联故障 1.1 相依网络网络与网络之间的耦合非常普遍,比如生活中的电力网络和通信网络之间的耦合,电力网络的正常运行需要通信网络的控制信息进行调控,而通信网络的运行又需要电力网络的供电,2个网络彼此依赖。
构成相依网络的各个网络称为“子网”,子网间不同的耦合方式对相依网络拓扑结构有不同影响。假设有2个子网,分别记作A和B(B为A的副本),一般有3种不同的连边耦合方式:同配耦合、异配耦合和随机耦合。同配耦合指子网A中大度节点与子网B中大度节点连边,子网A中小度节点与子网B中小度节点连边。异配耦合指子网A中大度节点与子网B中小度节点连边。随机耦合指子网A中一节点随机选择子网B中一节点连边。子网内部的边称为“连接边”,而子网之间的边称为“相依边”。图 1中的相依网络由子网A和子网B随机耦合而成,实线代表连接边,虚线代表相依边。
实际社会中大部分网络均存在负载效应,而相依网络各个子网之间又存在依赖关系,本文同时考虑相依边和负载对相依网络的共同影响。首先假定子网A中某一节点i发生故障,则:1) 子网A内其他节点j会因为节点i负载重分配发生过载而故障,2) 子网B中与节点i连接的节点k会因为相依边的作用而故障,即发生在子网内部的故障和发生在子网之间的故障。
方便起见,将初始故障节点所在的子网称为“初始子网”,初始子网内部的故障过程称为“负载故障”,相应的故障节点称为“负载故障节点”;子网之间的故障过程称为“相依故障”,相应的故障节点称为“相依故障节点”。
以图 2为例说明相依网络中级联故障如何发生,选定子网A是初始子网,节点a2是初始故障节点(黑色圆圈代表故障节点,其他颜色圆圈代表非故障节点)。
步骤1 初始子网A中节点a2发生初始故障,连边〈a2, a1〉、〈a2, b2〉、〈a2, a3〉断开。
步骤2
a) 步骤1中节点a2发生负载全局分配导致初始子网A中节点a3过载发生“负载故障”,连边〈a3, b3〉、〈a3, a4〉、〈a3, a5〉断开。
b) 与节点a2存在相依边的子网B中节点b2由于失去依赖节点发生“相依故障”,连边〈b2, b1〉、〈b2, b3〉、〈b2, b5〉断开。
步骤3 步骤2中a)中〈a3, b3〉断开导致子网B中节点b3发生“相依故障”,连边〈b3, b4〉断开。步骤2中b)连边〈b2, b1〉断开导致节点b1成为子网B中孤立节点而故障,连边〈b1, a1〉断开。
步骤4 步骤3中连边〈b1, a1〉断开导致子网A中节点a1发生“相依故障”,进一步连边〈a1, a5〉断开。节点a1发生负载全局分配,但没有节点过载,相依网络的级联故障停止。
级联故障停止后,存在3类不同的故障节点:初始子网中的负载故障节点(比如a2 → a3)、不同子网间的相依故障节点(比如a2 → b2、b1 → a1、a3 → b3)、孤立的单个故障节点(比如b2 → b1)。
1.2.1 相依故障初始子网A中节点i故障,移除子网B中与节点i存在“相依边”的节点k;移除子网B中与节点k存在“连接边”的其他节点h;移除子网A中与节点h存在“相依边”的节点i′, 不断重复上述过程直至没有节点故障。总体思路如下:子网A中某一节点故障会导致子网B中节点失去相依边而故障,而子网B中的节点故障后,亦会导致子网A中其他节点失去相依边而故障,不断迭代。
1.2.2 负载故障初始子网内某一节点故障,故障节点的负载依据全局分配原则,分配给初始子网中的其他节点,导致初始子网内的其他节点过载而故障。
在Internet等网络中,如果一个节点发生故障,经过该节点的信息会路由选择新的线路,该节点周围的其他节点会被分配到多余信息(即负载)。假定节点u为故障节点,新定义负载全局分配原则如下:
$ \Delta {L_j} = {{\rm{e}}^{-w{d_{u, j}}}}{L_u} $ | (1) |
其中:du, j代表故障节点u和j的最短路径长度;w用以调节分配负载的分布,w越小,全局分配效应越强。du, j越大,ΔLj越小,即距离故障节点越远,节点分配到的多余负载越小。图 3是负载全局分配示意图。
图 3中:节点u是初始故障节点;节点m、n距离u比较近,分配的负载较多;而i和j距离u比较远,分配的负载较少。黑色实线说明负载分配给邻居节点,黑色虚线说明负载分配给非邻居节点。
负载故障的完整过程如下。
a) 定义网络节点u的初始负载Lu和容量Cu:
$ {L_u} = {B_u} $ | (2) |
其中Bu为节点u的介数中心性[12],介数中心性刻画经过某一节点的最短路径多少。
$ {C_u} = (1 + t){L_u} $ | (3) |
其中t代表容忍系数[13],用来调节节点的容量大小。t越大节点容量越大,节点越不容易故障,网络越冗余,抵制故障的成本也就越大。当t小于某一值tc时网络处于崩溃状态,t大于tc时网络脱离崩溃逐步趋向完整状态,该值称为阈值tc。tc越小说明网络抵制故障能力越强,抵制成本越低。
b) 故障节点发生后按式(1) 进行负载全局分配,将负载分配给其他节点j,若
$ {L_j}{\rm{ + }}\Delta {L_j} > {C_j} $ | (4) |
则表明节点j过载而故障。
c) 对所有故障节点重复步骤b),直至子网内的所有节点均不过载。
2 网络模型和数据集 2.1 小世界网络模型和随机图模型1) 在复杂网络各种模型中,影响较大的是由Watts等[14]提出的WS(Watts-Strogatz)小世界网络模型。WS小世界网络模型刻画的现实网络有较小的平均路径长度和较大的平均聚类系数。构造过程如下:
步骤1 初始化含有n个节点的环形规则最近邻耦合网络,网络中每个节点与左右各k/2个邻居节点相连。
步骤2 对步骤1中网络的每个条边,保持连边一端不变,另一端以随机概率p选择网络的其他节点。
其中,构造过程中,k必须为偶数,连边随机重连时不能有重边和自连。
2) 随机图理论由Erdos和Renyi所建立,简称ER随机图。虽然ER随机图在某些方面不能很好刻画实际网络,但某种程度上却是实际网络中小世界现象产生的基本机制。构造过程如下:
步骤1 初始化含有n个节点的网络;
步骤2 对步骤1中的网络选择没有连边的节点对进行加边;
步骤3 重复步骤2直至网络中的边数达到指定值m。
在本文中:采用WS小世界网络模型构建WS网络时,参数n=500,k=4,p=0.02;采用ER随机图模型构建ER网络时,参数n=500,m=1 500。
2.2 网络拓扑性质依据2.1节描述,创建相依网络所需的子网:小世界网络WS和随机图ER。IEEE118电网是标准电力系统拓扑,亦作为相依网络所需的子网之一。表 1是单一子网的拓扑性质。其中,N代表节点总数,M代表边总数,〈k〉代表平均度,D代表网络直径,C代表网络平均聚类系数,d代表网络平均路径长度。
采用随机耦合方式,分别将IEEE118电网、WS网络和ER网络作为子网络,形成IEEE118耦合网络、WS耦合网络和ER耦合网络,在不引起歧义的前提下,表中和下文仍简称为IEEE118、WS和ER)。表 2是相依网络的拓扑性质。
由表 2可知,3个耦合网络的平均度、网络直径和平均路径长度均较小,WS耦合网络的平均聚类系数较大。相对表 1而言,相依网络的平均度增大,而其他中心性指标普遍下降(ER耦合网络的平均路径长度例外,小幅增大)。平均度增大是由于耦合操作增加了节点的连边,而其他中心性指标下降是由于随机耦合方式致使节点之间的三角关系被弱化。
3 不同指标的结果分析本文采用python建模,数值模拟相依网络的级联故障,实验结果均为全部节点的结果均值。采用4种指标度量级联故障结果:“平均剩余节点比例”刻画级联故障对网络的破坏程度,“平均负载故障节点比例”刻画负载故障对级联故障的贡献程度,“平均故障迭代步数”刻画级联故障对网络的持续影响力和故障过程的快慢,“第一次迭代中平均最近最短路径长度”刻画初始故障中后续故障节点的分布情况。
3.1 平均剩余节点比例级联故障终止后,网络剩余的正常节点数目与总节点数目的比例用以刻画网络抵制故障的能力,同等容忍系数t下,比例越大抵制能力越强,比例越小抵制能力越弱。图 4是网络的平均剩余节点比例。
分析不同w曲线总体趋势,发现不同的w值对应不同的阈值tc。w越大,tc值越小,负载全局分配对网络破坏越小,网络脱离崩溃状态(纵坐标≈0) 所需要成本越小,网络抵制故障能力越强。当w≤0.01时,3个相依网络的平均故障节点比例≈0,说明负载全局分配效应非常显著时,网络抵制故障能力趋于零。w=0.1,t=1.0时,IEEE118耦合网络保持30%的完整率,WS耦合网络保持9%的完整率,ER耦合网络保持3%的完整率。w越大,w对应tc越小,网络抵制故障能力越强。IEEE118耦合网络相比其他耦合网络,w曲线更靠近左侧,在同一w下有更小的tc,说明IEEE118耦合网络在负载全局分配下有更强的级联故障抵制能力。
3.2 平均负载故障节点比例负载故障节点比例刻画负载故障对级联故障的贡献程度,对应也可知道相依故障对级联故障的贡献程度,结果如图 5所示。
由于负载故障节点只存在于初始子网中,初始子网节点数目是整个网络的一半,所以平均负载故障节点比例最大为0.5。总体趋势:t越大,负载故障节点比例逐渐下降,说明网络冗余既可以增强相依网络抵制故障能力,又可以降低负载故障对级联故障的贡献程度。在同一t值下,w越大,负载全局分配效应越小,平均负载故障节点比例越小,负载故障对级联故障的贡献越小。
3.3 平均故障迭代步数图 6是平均故障迭代步数。显然:在负载全局分配效应较小(w较大)时,不同的w对应的平均故障迭代步数随着容忍系数t的增大,先上升达到峰值再下降;而负载全局分配效应较大(w较小)时,平均故障迭代步数与容忍系数t呈现单调递增关系。
进一步分析初始故障节点负载重分配后,最初瞬间距离初始故障节点最近距离的过载节点的相关性质。
假设初始故障节点i,定义f(n)为第n个迭代步中过载节点集合,|f(n)|代表过载节点集合中节点数目,k∈f(n)。由于在n≥2时,不同迭代步之间存在多个故障触发源,不便于分析,这里取n=1,则
$ ds{t_{\min }}(1) = \left( {\sum {ds{t_{i, k}} \in {f_{\min }}(1)} } \right)/\left| {{f_{\min }}(1)} \right| $ | (5) |
表达为第一次故障迭代步中过载节点的最近最短路径长度。图 7是第一次迭代步中过载节点距离初始故障节点的平均最近最短路径长度。
从图 7可知,总体趋势而言:随着t越大,网络越冗余,过载节点距离初始故障节点越近。当w较小,即负载全局分配效应较明显时,过载节点与初始故障节点较远;而w较大时,即全局负载分配策略较弱时,过载节点靠近在初始故障节点附近。
4 结语不同子网耦合而成的相依网络广泛存在于各种系统和网络中,其故障表现形式与孤立网络不尽相同。文中在相依网络的初始子网内部考虑负载对节点的影响,节点负载分配原则定义为最短路径长度的指数形式,子网之间考虑相依边对节点的影响。通过对IEEE118耦合网络、WS耦合网络和ER耦合网络仿真,对现实网络有以下几点指导意义:1) 不同w值下相依网络的故障结果差异较大且区分显著,提高相依网络的鲁棒性需要降低负载的全局效应程度;2)“平均剩余节点比例”等指标表明WS网络和ER网络构建的相依网络的鲁棒性较弱,应该采用无标度网络(IEEE118已被验证属于无标度网络[15-16],其对应的度分布满足幂律分布)作为子网构建相依网络;3) 当负载的全局效应在一定范围内时(w≥0.5),后续的其他故障节点更倾向于发生在初始故障节点附近,便于有针对性地预防和修复节点故障。
[1] | MIGUEL M S, JOHNSON J H, KERTESZ J, et al. Challenges in complex systems science[J]. European Physical Journal Special Topics, 2012, 214(1): 245-271. DOI:10.1140/epjst/e2012-01694-y |
[2] | KLIMEK P, HAUSMANN R, THURNER S. Empirical confirmation of creative destruction from world trade data[J]. PLOS ONE, 2012, 7(6): e38924. DOI:10.1371/journal.pone.0038924 |
[3] | BULDYREV S V, PARSHANI R, PAUL G, et al. Catastrophic cascade of failures in interdependent networks[J]. Nature, 2010, 464(7291): 1025-1028. DOI:10.1038/nature08932 |
[4] | 李稳国, 崔宪普, 邓曙光, 等. 目的边攻击和防御下的相互依存网络相继故障[J]. 计算机工程与应用, 2014, 50(9): 69-72. (LI W G, CUI X P, DENG S G, et al. Cascade of failures in interdependent networks under targeted attack and defense of interdependent links[J]. Computer Engineering and Applications, 2014, 50(9): 69-72.) |
[5] | 蒋宇翔, 吕晨, 虞红芳. 信息缺失条件下的相互依存网络抗毁性分析[J]. 计算机应用, 2015, 35(5): 1224-1229. (JIANG Y X, LYU C, YU H F. Survivability analysis of interdependent network with incomplete information[J]. Journal of Computer Applications, 2015, 35(5): 1224-1229. DOI:10.11772/j.issn.1001-9081.2015.05.1224) |
[6] | WITTHAUT D, TIMME M. Nonlocal effects and countermeasures in cascading failures[J]. Physical Review E, 2015, 92(3): 032809. DOI:10.1103/PhysRevE.92.032809 |
[7] | 韩海艳, 杨任农, 李浩亮, 等. 双层相依指挥控制网络级联失效研究[J]. 中南大学学报(自然科学版), 2015, 46(12): 4542-4547. (HAN H Y, YANG R N, LI H L, et al. Cascading failure of two-layered interdependent command and control network[J]. Journal of Central South University (Science and Technology), 2015, 46(12): 4542-4547. DOI:10.11817/j.issn.1672-7207.2015.12.022) |
[8] | HAVLIN S, KENETT D Y. Cascading failures in interdependent economic networks[C]//Proceedings of the International Conference on Social Modeling and Simulation, plus Econophysics Colloquium 2014. Berlin:Springer, 2015:87-97. |
[9] | HONG S, LV C, ZHAO T, et al. Cascading failure analysis and restoration strategy in an interdependent network[J]. Journal of Physics A:Mathematical and Theoretical, 2016, 49(19): 195101. DOI:10.1088/1751-8113/49/19/195101 |
[10] | 赵娟, 郭平, 邓宏钟, 等. 节点相依失效下的方格网络可靠性建模与分析[J]. 系统工程与电子技术, 2013, 35(7): 1576-1583. (ZHAO J, GUO P, DENG H Z, et al. Modeling and analysis of reliability for lattice networks with dependent failures[J]. Journal of Systems Engineering and Electronics, 2013, 35(7): 1576-1583. DOI:10.3969/j.issn.1001-506X.2013.07.13.37) |
[11] | 陈世明, 邹小群, 吕辉, 等. 面向级联失效的相依网络鲁棒性研究[J]. 物理学报, 2014, 63(2): 028902. (CHEN S M, ZOU X Q, LYU H, et al. Research on robustness of interdependent network for suppressing cascading failure[J]. Acta Physica Sinica, 2014, 63(2): 028902.) |
[12] | OPSAHL T, AGNEESSENS F, SKVORETZ J. Node centrality in weighted networks:generalizing degree and shortest paths[J]. Social Networks, 2010, 32(3): 245-251. DOI:10.1016/j.socnet.2010.03.006 |
[13] | MOTTER A E, LAI Y C. Cascade-based attacks on complex networks[J]. Physical Review E, 2002, 66(6): 065102. DOI:10.1103/PhysRevE.66.065102 |
[14] | WATTS D J, STROGATZ S H. Collective dynamics of 'small-world' networks[J]. Nature, 1998, 393(6684): 440-442. DOI:10.1038/30918 |
[15] | 苏慧玲, 李扬. 基于准稳态功率转移分布因子的电力系统复杂网络特性分析[J]. 电力自动化设备, 2013, 33(9): 47-53. (SU H L, LI Y. Analysis of complex network characteristics based on quasi-steady PTDF for power system[J]. Electric Power Automation Equipment, 2013, 33(9): 47-53.) |
[16] | 陈晓刚, 孙可, 曹一家. 基于复杂网络理论的大电网结构脆弱性分析[J]. 电工技术学报, 2007, 22(10): 138-144. (CHEN X G, SUN K, CAO Y J. Structural vulnerability analysis of large power grid based on complex network theory[J]. Transactions of China Electrotechnical Society, 2007, 22(10): 138-144. DOI:10.3321/j.issn:1000-6753.2007.10.025) |