全文HTML
--> --> -->
图 1 电力基础设施依赖关系[9]Figure1. Dependencies among power infrastructures[9].
| 地点 | 日期 | 受灾人数/百万 |
| 巴西 | 1999/3/11 | 97 |
| 印度 | 2001/1/2 | 230 |
| 美国, 加拿大 | 2003/8/14-15 | 55 |
| 意大利, 瑞士 | 2003/9/28 | 55 |
| 印度尼西亚 | 2005/8/18 | 100 |
| 巴西, 巴拉圭 | 2009/11/10-11 | 87 |
| 土耳其 | 2015/3/31 | 70 |
| 印度 | 2012/7/30-31 | 620 |
| 孟加拉 | 2014/11/1/ | 150 |
| 肯尼亚 | 2016/6/7 | 44 |
表1重大停电事故数据[11]
Table1.Data on major power outages[11].
如何才能避免相互依赖系统级联效应的发生呢? 在这些系统发生级联失效后, 如何在系统完全崩溃之前修复并减小级联失效所带来的损失呢[14]? 常用策略和方案通常分为两种类型: 1)通过故障检测和保护关键节点等预防措施来减少故障发生的可能性; 2)当故障发生时采用合适的恢复策略, 对故障进行恢复.
接下来, 本文第2节介绍相依网络级联失效的经典模型. 第3, 4节则分别梳理了预防多层网络级联失效的方法和级联失效发生后的网络恢复策略, 而第5节是讨论部分.
图 2 级联失效迭代过程的建模[10] (a) 网络在初始状态下遭到攻击; (b), (c)和(d) 网络在遭受攻击后网络级联失效的不同阶段, 并最终达到了稳态, 级联过程结束Figure2. Modeling of cascading failure iterative processes[10]: (a) The network is attacked in the initial state; (b), (c), and (d) are the cascading failure processes of the network due to the dependencies between dependent networks after the attack, respectively. Eventually reached a steady state.
经典相依网络级联失效模型的提出引发了更多****开展对多层网络的动力学研究. 在两层网络的基础上, Gao等[15,16]进一步提出了多个网络存在相互依赖的“网络的网络(network of network, NON)”模型. 随着对相依网络级联失效模型研究的推进, 关于网络鲁棒性的研究[17]以及多层网络之间的动力学研究也吸引了愈来愈多的****并取得丰硕成果. Baxter等[18]阐明了一阶相变的本质其实是混合相变, 当临界节点形成的临界簇发散的时候, 一旦其中的“基石”节点(keystone vertex)失效, 整个临界簇就会发生雪崩现象, 导致多层网络互连巨分量出现不连续的跳跃. 多层网络的结构特性也对网络的鲁棒性有着重要的影响, 如簇结构和度关联等. Faqeeh等[19]在具有模块的网络中发现了不止一个渗流簇(coexist percolation cluster, CPC), 对理解网络的鲁棒性以及传染病模型中的疾病爆发具有重要意义. 在网络的同配性研究方面[20,21], 文献[20]比较了同配性对单层网络和多层网络上动力学过程的不同影响, 发现在多层网络上, 增加层间同配程度可以提高信息扩散效率; 而增加层间异配程度则可以分散链路通信负载, 增强网络鲁棒性. 此外还有一些****研究了空间地理效应[22,23]和有向网络[24-27]等因素对网络的鲁棒性所产生的影响. 通过考虑多层网络层内节点的不同耦合方式, 一些文献也研究了多层网络上的扩展渗流模型, 例如k-core渗流[28]、 靴攀渗流(bootstrap percolation)[29,30]和弱渗流[31]等, 极大地丰富了相依网络级联失效方面的研究.
2
3.1.故障检测
故障检测是指定期查找设备或系统是否出现故障并对这些故障进行修复的过程. 很多时候这些故障可能不会立即产生可以觉察的危害和损失, 但如果不加以排除, 则会在关键时刻或者随着时间积累对系统产生严重损害, 所以应该定期加以排查. 这里将各种基础设施抽象成了网络, 但在现实生活中不同的系统根据其自身特点有不同侧重点和相应的检测方法, 不能一概而论. 比如, 对于电力网络来说需要检测的可能会发生的故障包括发电机组故障、母线故障、输电线路故障和变电所故障等, 而对于计算机网络来说其故障检测则包括硬件故障、软件故障、人为故障和病毒故障等. 通过故障检测可以提前排查系统中存在的问题, 减少其对系统造成的危害. 故障检测是事前采取针对性措施, 减少和防范故障发生的策略.2
3.2.预先保护重要节点
重要节点一般是指少量对网络结构或功能非常重要, 且其影响可以快速地波及到网络中大部分节点的节点[32], 关于重要节点的衡量方法有很多[33,34]. 通过保护重要节点, 可以大大提高复杂网络的鲁棒性[35-37].文献[38]研究在相互依赖的网络上, 分别以其中一个网络中的大度节点或者小度节点为攻击目标时网络鲁棒性的变化, 他们发现即使是在较低的攻击概率下, 在相互依赖的无标度(scale-free)网络[39]上采取保护大度节点的策略后, 网络仍是十分脆弱的. Du等[40]发现具有较大数量的相连边(同一层网络节点之间的连边)和相依边(不同层网络具有相互依赖关系节点之间的连边)的节点很重要, 所以不仅要保护层内或层间连接程度较高的节点, 而且要保护层内和层间连边数量之和较大的节点, 以此来增加系统的鲁棒性.
另一方面, 应该优先对那些能够使得网络快速瓦解的节点进行保护. Osat等[41]将单层网络的最优渗流推广到多层网络上, 并通过最优渗流找到那些被删除后网络不会再出现
另有文献[17]将两层网络看成一个整体, 将单层网络上一些衡量节点重要性的指标运用在了双层网络(或更多层的网络)上, 从而找到在多层网络中需要保护的重要节点, 提高了相依网络的鲁棒性, 主要包括以下方法.
1) T-度中心性保护策略. 将单层网络中的度中心性概念推广到两层网络上, 得T-度(two-layer-degree)保护策略. 在T-度中心性保护策略中, 将不同层中的节点同等看待, 计算每个节点在各自层内的度值大小, 节点的重要性按它的T-度从大到小依次递减. 例如, 图3(a)给出了一个由网络A和网络B组成的相依网络. 传统的方法是选择网络A中的节点1和节点2 (度值分别为5和4), 使它们和其依赖节点在故障发生时能够正常工作. 而实验表明, 在保护节点比例不变的情况下, 保护网络A中的节点1和网络B中的节点1(度值分别为5和5)效果更好, 这正是因为它们的T-度最大.
图 3 基于相依网络的保护节点模型[17]Figure3. Nodes protection model based on interdependent networks[17].
2) T-介数中心性保护策略. 给定两层网络G = (C, (LA, LB, LAB)), 其中LA表示包含
3) T-社团(two-layer-comm)保护策略[50]. ① 同上, 将两个相依的网络A和网络B看作一个网络C, 初始时假设每个节点本身就是一个社团, 当出现最大的模块度增量[51]后, 合并相应的社团i和j. 当达到了局部最大模块度时, 此步骤停止. ② 将此时的每个社区继续当作一个“节点”, 重复步骤直到模块度停止变化. 节点i的模块度增益
2
3.3.优化层间耦合机制
不同的网络拓扑结构使多层网络的鲁棒性之间存在较大差异. Reis等[52]针对随机连接的相依模型网络鲁棒性低, 而自然界中的真实相依网络鲁棒性却相对较高的问题进行研究, 发现多层网络的鲁棒性由每一层的内部结构和层间的节点连接模式共同决定. 他们指出一个网络的中心节点(hub nodes)与另一个网络中心节点之间存在度同配相关性的相依网络在随机故障中具有更好的鲁棒性. Parshani等[35]提出了部分依赖模型, 通过降低相互依赖节点的数量, 降低级联失效的危害. Liu等[31]提出的弱依赖模型则降低了相互依赖网络之间的依赖程度, 这也使得网络的破碎形式从一阶相变变成二阶相变, 增强了网络的鲁棒性. 文献[53]则提出多层网络间非对称性的依赖, 来控制网络层间的依赖程度, 从而增加网络的鲁棒性. Hu等[54]分析了相依网络结构相似性对级联故障带来的影响, 他们发现增加结构相似性会减弱级联故障的程度. 文献[55]也指出网络间的相似性越高, 则发生节点随机失效时系统的鲁棒性也越高. 文献[56]提出网络同配性研究可以为提高网络鲁棒性带来新的启发, 从而提高关键基础设施的保护水平. Radicchi等[57]将具有相互依赖关系的节点在一个失效后其余节点也会失效这一规则更改为: 当一个节点有至少两个副本节点(多层网络的不同层中具有相互依赖关系的节点)存活时, 这个节点就不会失效. 在多层(> 2)网络中建立冗余的相互依赖关系可以提高整个系统的鲁棒性. 除此之外还可以通过减弱网络层间的相关性[58]、设置加强节点[59]等策略抑制系统的级联效应.2
3.4.节点备份
节点备份也是一个有效预防级联效应的措施, 它是指对多层网络中的少数重要节点预先从结构或功能方面设计并添加它们的备份, 万一这些节点日后失效, 这些备用节点能够立即启用代替失效的节点, 维持网络功能正常运行[60]. Valdez等[61]认为对一些节点备份后, 即使在缺少其他网络支持的情况下, 这些节点仍然能保留功能, 从而增加了系统的鲁棒性. Quattrociocchi等[62]通过引入节点的自愈(self-healing)机制, 即增加网络固有的冗余度来增强网络的鲁棒性. Schneider等[37]选择最少的自治节点[63,64] (通过k-shell, 介数中心性等方法进行筛选节点) 进行备份, 以避免网络在遭受攻击时发生突然瓦解和破碎.然而节点备份的策略也有一些不足之处. 文献[60]提出在自修复网络中通过相互复制进行自我修复是一把“双刃剑”. 除此之外, 在现实应用中, 节点备份策略和网络冗余设计还需要增加网络的设计和维护成本(有些情况下节点的备份还面临技术难题), 付出一定的时间和经济代价, 造成一定的浪费, 因此在实际应用中往往需要考虑这一策略的代价和效果的平衡.
2
4.1.边界节点恢复策略
Muro等[14]提出相依网络恢复策略, 旨在对未被级联失效波及的剩余网络进行保护. 这一策略使得级联失效过程和恢复过程动态交替进行, 其核心是找到两个相依网络中的共同边界节点. 共同边界节点是指两个网络中距离各自巨分支距离为1的一对失效的相互依赖节点. 图4中节点1和2即为共同边界节点. 初始网络A发生了故障, 网络B中所对应的节点也会失效, 在网络B将故障传递回网络A之前, 恢复机制会介入并找出当前的共同边界节点, 每轮恢复阶段以概率γ对共同边界节点进行恢复, 从而尽可能地遏制级联失效在相依网络上的传播. Muro等发现, 最终网络有以下三种情况, 第一是系统不被修复也不会崩溃; 第二是部分节点在这一过程中失效, 但恢复策略避免了系统的崩溃; 第三是恢复过程也不能阻断级联失效过程, 最终系统崩溃.
图 4 故障恢复策略图解[14] 网络A和网络B的巨分支如图所示. 情况1: 两个通过相依边连接的失效节点(节点1和节点2)分别距离其巨分支的距离l = 1, 然后以恢复概率γ进行修复; 情况2: 如果两个相互依赖的故障节点(节点3和节点5)中至少有一个与其巨分支的距离大于1, 则不符合恢复的条件, 所以放弃恢复这一对节点Figure4. Illustration of failure recovery strategy[14]. The giant components of network A and network B are shown in the figure. Case 1: Two failed nodes (nodes 1 and 2) connected by dependent edges are respectively at a distance of l = 1 from their maximal cluster, and then repaired with recovery probability γ. Case 2: If at least one of the two interdependentdent failed nodes (nodes 3 and 5) is more than 1 away from its maximal cluster, the recovery condition is not met, so the pair of nodes is abandoned to be restored.
选择共同边界节点进行恢复有以下两个原因: 第一, 当故障发生时, 通常都是优先抢修正常区域周边的基础设施; 第二, 如果候选恢复目标不是共同边界节点, 其对应的相依节点若是脱离巨分支的节点, 这个节点就会因其依赖节点的失效而失效, 那么对该节点的修复就没有意义.
吴佳键等[69]对此策略进行了一些修改, 他们认为用恢复概率γ来随机选择恢复节点不是最优方案. 于是提出利用共同边界节点在巨分支内外的连接边数计算和定义边界节点的重要性, 也就是基于相连边的择优恢复算法(preferential recovery based on connectivity link, PRCL). 实验显示, PRCL算法的恢复策略更好, 可以识别出恢复过程中更重要的边界节点.
2
4.2.空闲连边恢复策略
在Buldyrev提出的相依网络级联失效模型的基础上, La Rocca等[67] 2018年提出在两个相依网络中对相较而言恢复代价更低的那个网络进行恢复的策略. 这里假设网络B为符合条件的网络, 在步骤n = 0时, 从网络A中移走1－p比例的节点, 得到网络A的巨分支. 因为网络A与网络B的节点一对一依赖, 所以可以得到网络B此时的巨分支. 以概率γ同时恢复网络B中某个有限簇(其规模不小于2)中的两个节点与巨分支之间的连边. 但如果该有限簇只有单个节点, 那么就以相同方式恢复其与巨分支之间的一条连边. 需要注意的是所有可能被恢复的有限簇中的节点必须有空闲连边. 空闲连边是一种虚拟连边, 指的是那些在级联失效过程中断开的连边. 当一条连边断开以后, 则它两端的节点各自得到一条空闲连边, 如图5(a)中的虚线边所示.
图 5 网络B中恢复策略的实现示意图[67] (a) GC表示网络巨分支, 虚线表示空闲连边, 带有空闲连边的簇表示可修复的簇, 没有空闲连边的簇表示无法进行恢复的簇; (b)网络B完成重连后的巨分支Figure5. Schematic diagram of the implementation of recovery strategy in network B[67]: (a) GC represents the giant component of the network, the dashed lines indicate idle connected edges, clusters with free connected edges repre-sent repairable clusters, and clusters without free connected edges represent clusters that cannot be recovered; (b) the giant component of network B after reconnection.
之所以选择一个有限簇里面的两个节点与巨分支相连接, 是为了减少这个有限簇再次脱离巨分支的概率. 增加有限簇与巨分支相连的节点数量虽然可以提高网络的鲁棒性, 但是在现实应用中也会增加成本. 阶段n = 0结束后, 以概率1－γ (γ是恢复概率)删掉网络B中没有被恢复的有限簇, 如图5(a)中没有空闲连边的深色节点. 至此第一轮网络B恢复过程结束. 当网络B将这个结果反馈给网络A的时候, 与网络B中失效节点相连接的网络A中的节点就会失效, 然后又反馈到网络B, 与网络A中失效节点相依赖的网络B中的节点失效, 对此时的网络B开启新一轮的恢复过程. 以此类推, 两个网络就这样迭代下去, 直至两个网络构成的系统达到稳态.
La Rocca等[67]指出随着γ的增加, 临界阈值pc降低, 网络破碎的形式也会从一阶相变转变为二阶相变, 这就使得两个网络在发生网络崩溃前可以克服更多节点的失效. 这也是为什么La Rocca等认为将此恢复策略应用在两个相依网络中较为脆弱的那个网络, 会使整个系统的抗毁性提高. 根据不同的恢复概率γ和网络的初始保留概率p, 就可以知道网络是能被恢复的, 还是不能避免它最终的崩溃.
2
4.3.加边恢复策略
加边恢复策略是以相依网络级联失效模型[15]为基础通过进行一系列的加边, 来增加网络鲁棒性的恢复策略[72]. 过程如下: 在晶格网络A中, 对于一个被移除的节点, 将其邻居中没有被移除的具有功能性的两个节点以概率w相连. 网络B中与网络A中的失效节点具有依赖关系的节点也会失效, 因此网络B也需要实施上述的恢复过程, 即失效节点的两个未失效且不直连的邻居以概率w进行连接. 其实恢复步骤是将每个失效节点的所有邻居对当作候选者以概率w连接, 节点失效, 找出邻居对连接, 再有节点失效······, 整个过程待两个相依网络达到动态平衡, 即没有连边或者节点再失效后结束. 随着时间的推移, 修复连接可能会极大地改变拓扑结构, 新建立连接的两个节点之间在原始晶格网络上的距离可能越来越大.2
4.4.优先恢复重要节点策略
Gong等[73]提出在级联失效后, 优先恢复重要节点的策略. 通过在三个不同类型的耦合网络(随机网络-随机网络(ER-ER)[74], 随机网络-无标度网络(ER-SF)[73], 电力网络-无标度网络(power-SF)[73]上分别应用6种不同的重要节点识别指标(随机、度中心性、介数中心性、PageRank、LeaderRank)来确定优先恢复的节点, 结果发现只需恢复网络中5%的重要节点就可以显著恢复网络功能, 尤其是介数中心性指标效果最优. 而基于度中心性指标和PageRank指标的恢复策略的优点在于其较低的计算复杂度, 可用于具有数百万节点的大规模相依网络.相依网络的恢复过程如下(例如按照随机选择): 对于一个已经级联失效的网络, 初始时假设图中的节点均为失效节点. 如图6(a)所示, 假设恢复网络C中的节点1, 2, 3和4, 那么网络D中与网络C相依赖的节点5, 6, 7和8 被触发而恢复正常(图6(b)). 然后, 由于网络C中已恢复节点4和它在D网络中的依赖节点8不在各自网络的巨分支中, 所以它们会再次失效(图6(c)). 同理, 网络D中的节点5由于孤立失效, 而导致与其依赖的C网络中的节点1也再次失效(图6(d)). 此时网络达到稳态, 网络中的节点2, 3, 6和7就是本次恢复过程执行后最终被真正恢复的节点.
图 6 恢复模型Figure6. Schematic diagram of recovery model.
2
4.5.更改拓扑结构策略
Schneider等[66]提出了一种有效恢复电力网络故障的方法, 他们发现在不增加连边数量的情况下, 只要对给定网络的拓扑结构进行相对较小的修改, 就有可能大大降低恶意攻击的危害. 这一结论在两个真实网络, 即欧洲电网和互联网中得到了验证. 这一发现, 一方面可以指导现有网络通过结构的优化来提升鲁棒性, 另一方面也可以用来设计未来的基础设施, 使其具有更好的鲁棒性. 我们通常是用临界阈值来衡量网络的鲁棒性. 而这种方法忽略了如果网络受到了攻击但是并没有崩溃的情况. 所以他们引进了一个独特的测量鲁棒性的方法,
2
4.6.局域攻击修复策略
局域攻击也叫局部攻击, 指的是网络位于某个地理空间范围内的节点受到了攻击. 在现实生活中, 局域攻击比随机攻击更为普遍, 如军事打击、自然和人为的灾害等[75]. 文献[71]提出了优先最小度修复策略(the healing strategy by prioritizing minimum degrees, HPMD), 空间相依网络出现局部攻击时可以采用此策略. 失效网络的模型依托于文献[76], 优先最小度策略是将一个失效节点的两个度值最低的邻居相连进行恢复, 对比度中心性、随机选择和局部中心性, 此方法更优.2
4.7.自适应边恢复策略
Liu等[77]提出在多层网络中添加自适应边的恢复策略. 为了增加多层网络的鲁棒性, 抵御大规模节点失效而导致的网络崩溃, 在多层网络中, 网络A定义为控制层网络, 而网络B, C, ···是非控制层(不能人为干预), 当网络A中的节点ai脱离其巨分支时, 我们规定节点ai会随机产生M条边连接在网络A中的其他节点上, 也就是说产生的M条自适应边中只要有一条连接在了网络A的巨分支上, 节点ai就会从失效状态恢复成具有正常功能的状态(在此过程中假设与ai相依赖的其他网络层中的节点均没有失效, 都具有正常功能). 根据经典的相依网络级联失效模型, 我们知道当ai脱离巨分支时, 其他网络层中与之相互依赖的节点也要失效, 而在节点ai脱离时, 产生的M条自适应边会很大程度上保证这个节点被修复, 这意味着其他层中与节点ai具有依赖关系的节点会因为这个自适应边的加入而以很大概率避免了脱离其各自网络的巨分支. 所以对其中一个网络层的自适应扰动不仅可以增强控制层网络自身的鲁棒性, 还可以增强其他互连网络层的鲁棒性.多层网络级联失效的抑制策略研究同样建立在对多层网络破碎机理的理解之上, 如边界节点恢复模型、加边恢复策略等. 无论是对节点的恢复, 还是对网络进行加边, 都需要一定的代价. 如何达到效用和代价的最优? 为什么需要恢复边界节点? 哪些节点需要优先加边恢复? 回答这些问题同样需要理解多层网络的破碎规律和特点. 对于不同的多层网络发生级联失效的时候, 该采用什么样的决策方法来选用恢复策略呢? 目前来说, 回答这一问题尚有比较大的挑战, 但可以肯定的是恢复策略的选用需要结合具体的情况, 如多层网络拓扑结构特性、耦合机制、网络损害规模和实际需求, 以及恢复的代价限制和速度要求等. 随着对多层网络级联效应研究的深入, 相信对这一问题的研究会不断取得突破, 而且会有更多的、更加贴合现实情景的预防和恢复策略被提出.
