《复杂网络第五讲相继故障》由会员分享，可在线阅读，更多相关《复杂网络第五讲相继故障（53页珍藏版）》请在金锄头文库上搜索。
1、复杂网络上的相继故障报告人：孙龙霄引言相继故障的定义在很多实际网络中，一个或少数几个节点或边发生故障(这种故障可能是随机 发生的，也可能是由蓄意攻击造成的)会通过节点之间的耦合关系引起其它节 点发生故障，这样就会产生连锁效应，最终导致相当一部分节点甚至整个网络 的崩溃。这种现象就称为相继故障，有时也称为“雪崩(avalanche) ”。相继故障的危害在Internet网络中，对少数路由器进行病毒攻击会导致路由器过载，迫使数据 包重新路由，从而引起其他路由器接连过载，产生雪崩效应。在电力网络中， 断路器故障.输电线路故障和电站发电单元故障常常导致大范围停电事故。大 规模的相继故障一旦发生，往往具
2、有极强的破坏力和影响力。例如，2003年8 月,由美国俄亥俄州克利夫兰市的3条超高压输电线路相继过载烧断引起的北 美大停电事故，使得数千万人一时陷入黑暗，经济损失估计高达数百亿美元。亚洲金在社会与经济网络中也会发生类似的雪崩效应，20世垒90乎代 融危机就是一个典型的例子。t复杂网络相继故障的动态模型分析负荷一容量模型A二值影响模型A沙堆模型 OP A模型A CASCADE模型A其他模型负荷容量模型总述当由于某种原因某个节点的负荷超过其容量 就把该节点的负荷按照一定的策略分配给网 这些节点接受了额外的负荷，其总负荷也有 从而导致新一轮的负荷重新分配。这个过程赋予网络中每个节点（或）边一定的初始
3、负荷和容量（也 成为安全阈值）。 从而产生故障时， 络中的其他节点。 可能超过其容量，反复进行，影响的节点有可能逐渐扩散，从而产生相继故障。1、节点动态模型含有N个节点的网络，赋予每个节点满足某种统计分布的安全阈值込丿=12,N。假设每个节点承担相同的负荷a = F/N 若bq ,则表明节点亍发生故障，于是将负荷平均的传给与 之直接相连的无故障节点，并从网络的最大连通子图中去除这 个故障节点，故障的重新分配可能引发其他节点产生故障，从 而导致相继故障。当网络中所有剩下节点的负荷都低于其安全 阈值时，相继故障结束，此时也称网络达到了平衡状态。在给 节点赋妥全阈值时使用weibull分布：p（cr
4、.）= _-（5）。 其中q称为weibull指数，它可以控制阈值分布的杂乱程度。这 样就可以比较妥全阈值具有不同层次的非均匀性的影响。下图是N =的BA无标度网络，在相继故障结束时最大连通子图相对大小与负荷 的关系，最大连通子图相对儘 定义算= 其中”表示相继故障结束后网络的最大连通子图包含的节点的个数。（最大连通子图相对值和相继故障规模是成反比的）结论：对较小的，相继故障的规模也比较小，当0增加时,相继故障规模持续增加到一个临r uodlusCQ6 圭 joCDZ 一 s明阈值分布较均匀的网络对故障更具有承受力。2界值。然后曲线突然下降至零附 近，表明系统已经分裂为许多孤 立的部分而无法正
5、常工作。P 值的增加会导致临界点右移，说用控制参数变化时拓扑结构的变化来分析相继故障的发生过程。给定 参数N = （f,p = 5，下图现实了 CF取不同值时，对应的平衡状态下度为k 的节点个数以与騒关系图。当外界压力比较小，如cr = 005时，网路拓 扑结构基本维持不变（BA无标度网络模型的度分布为猱律分布）;番 大于临 界傲=0.52 ,系统将崩溃，网络中不再有度彳艮大的节点。Nd是在节点对之间沿着最短路径交换，节点的负荷定义为该节点的 介数(betweenness centrality, BC)、它反映了网络中通过该 节点的最短路径的数目。定义节点丿的容量(可承载的最大负荷) 正比于其
6、初始负荷5即 其中常数Q0是一个容许系数。正常情况下，网络运行于一种自 由流(freeflow)状态。当网络中某个节点发生相继故障时， 可以认为它脱离了网络的最大连通子图。这样一般会导致网络的 最短路径发生变化，每个节点的负荷也可能发生变化。当节点的 负荷超过其容量时就会发生故障，从而引发新一轮的负荷重分布。如果网络的负荷分布具有非均匀性(一般与度分布的非均匀性有关),并且去掉的节点负荷较高，就会导.随机选择的节点1.00.8G0.6a & e e-度最大的节点T /jT I丿 1 1 1负荷最大的节点0.00.20.40.60.81.0a无标度网络中的相继故障结论：如果最初移去的节点是随机选
7、择 的,则网络的性能几乎没有变化；如果 移去的节点是负荷最大的节点，G会大 大的减少，即便是理增加到1,网络性能 也会下降20%。在基于负荷和基于度的攻 击情况下，G越小，网络的性能损失也越 大。原因：网络中度和负荷比较小的节点居 多，因此随机故障大多发生在这些节点 上，并且对整个网络不会造成很大的影 响。而蓄意攻击则针对那些度或负荷较 大的关键节点，因为这些节点对于维持 网络的结构和功能起着重超舉囲。结论：当&小至005时，无G1.00.8D.6D.40.20.00.00.2D.40.60.81.0障，而关键节点受到攻击的非均匀网络的相继故障规模均匀网络与无标度网络相继故障的比较论是随机故障
8、还是恶意攻击, 均匀网络都不会发生相继故高达90%。由此可以看出， 均匀网络对攻击的鲁棒性比 非均匀网络要好的多。均匀网络（外图）与非均匀无标度网络（内图）的 相继故障比较网络增长过程中相继故障的产生条件网络节点的负荷仍然用介数定义，而节点负荷的最大值（容量）分两种情况定义：一种情况下容量随着网络节点数线性增长（ICA式），另一种情况下容量保持一个常数（ECA模式）。在ICA模式下，节点和边增加到一定程 度就会有节点过载。这是将过载节点以及与之相连的边去掉，重新计算每个 节点的介数。这个过程反复进行，直到不再有节点过载。0.90.807 k 0-6 、,0.5 0-40.30.20.10010
9、00200030004C00500060007000ECA模式下优先连接增长网络ECA模式下随机连接增长网络三条曲线（最大联通子图规模 G、网络的边数平均路径长度匕） 随网络增长时间疋的变化都是先上升后下降的，这型弐网岁磐4定 程度时，由于网络中不断有节点过载失效，使得网络溺渍耦歸茎碎片。2. 边动态模型给连接节点爲丿的边而不是节点本身赋予了负荷/O.(0/7.1), 以模拟网络中沿着边传播的数据包的通信量。负荷服从如下分布: 平均负荷用表示 & 0?2(Q, if 0.5.定义每条边的容量为C = 1,若lijC、则表明这条边发生 了拥塞，于是将R按照一定的动态规则重新分配，如果平均分配厶,
10、感者随机选取l的一部分分配给其相邻的未拥塞边；如果相邻的所有边都拥塞，那么就将负荷全局分配给整个网络里其他未拥塞的边或者直接丢弃，负荷的重新分配有可能导致其他边拥塞，从而产生相继故障。如果拥塞的边较多，网络很可能不存在最大连通子图。对BA无标度 网络应用上述过程发现，当系统稳定时,（即相继故障發束时），对应不 同的负荷动态分布规则均有一个临第賈 济：时,网络会以一定的概率处于拥塞状約淺Z“a082时，任何不稳定性都会导致整个网络中所有边拥塞。“1.00.80.20.60.4 (a)- (b) (0 .0.00.20.40.60.8左图中三条曲线分别对应三种负荷 分配策略：（a）随机分配负荷或
11、丢弃；（b ）随机分配或者全局分 配；（c）平均分配或者全局分配 结论：当平均负荷比较小时，发生 大规模相继故障的可能性比较小（存在最大连通子图的可能性比较 大）。分配策略越随机，则发生相 继故障的可能性越大。0.01.0网络有最大联通子图的概率&与网络平均负徐/的关系网络包含N = 1（/个节点，和3x10条边，对于中等大小的同时发生过载的边的数目s的概率分布近似服从赛指数为1的赛律分布： P（5）OO5_1OO.二 1.0、0.460.864A2o刍二三二0.010101010网络承受不同的平均负荷时，故障规模S的累积网络增长过程中的相继故障从上图可以看出，随机连接情况下，网络出现过载的时
12、刻比优先连接情形的要晚,S的稳态值也比有限连接情况下的要大，这种情况下边过载不会对网络结构造成大的影 响。M曲线中有一小段的区域,其下降趋势没有S曲线下降明显，也就是说很少的边过 载就可以导致s大幅度下降。这种现象的原因在于网络中连接各部分连通子图的那些数量彳艮少的边上具有彳艮高的负荷，因此当网络规模不算增加的时候会首先发生过载。网络 的平均路径长度L在网络增长的早期就下降到最小值；然后，随着网络碎片的形成，L持 续上升。(a)(b)01000 2000 3000 4000集团。强的抵抗性。比较节点过载和边过载的结论可以看出，节点过载的情况下，相继故障发生以后网 络中只有互不相连的小规模的节点
13、集团，而边过载的情l 此外，如果网络增长采用随机连接方式，那么网络对于还扌3. 节点与边的混合动态模型该模型用无向加权图G来代表一般的通信.传输网络，其中节点（爲丿）之间的边的权e,. e 0,1。弓j越大，这条边上的信息传递的效率越高。N x N 的关联矩阵知j就建立了节点之间边的效率值矩阵。初始状态下对于任意节 点对（门）,知=1。定义丫时刻节点i的负荷为厶，其物理含义是F时刻通 过节点力的效率最优路径的条数。这里的效率最有路径定义为，对节点对匕丿） 之间的所有路径,计算整条路径的调和效率（S%）-1其最大值 竄x即为效率最优路径。节点负荷容许值q =oc是一个容许参数。定义的演化公式如下
14、：if f)Gif.(z+i)= Z7Tj 丨切(0)当某一节点由于故障被从网络中去除后，网络中的节点之间的效率最有路 径将会改变，导致负荷的重新分布，从而可能导致其他节点出现过载（这些过 载节点不会被移除），引发新一轮负荷重新分布，最终导致相继故障。可以用 相继故障结束后整个网络的平均效率来衡量网络破坏的程度：(G) = MT)X将这种模型应用与具有同样节点数和边数的ER随机图和B A无标度网络模型， 比较 取苓同值时平均效率的变化情况。随机去除节点或去掉负荷最大的节点的相继故障的E结论：两种网络模型均存在一 个临界的容许系值ac; aac 时系统将崩溃。图对应 的临界值比BA无标度网络的临 界值要小，这表明ERl图抵 抗相继故障的能力比B A无标度 网络强。此外，对于BA无标度 网络基于负荷的去点方式比随 机去节点更容易引发相继故障。a = 1.0251010*1010102 Damage (D)Q 二 1.210网络中节点按照其对网络效率的影响可以分为三种：移去那些度和负荷都 比较小的节点，对网络整体效率不会造成影响，这类节点占网络总体的近60%; 若移去那些度或者负荷较大的节点，则对网络效率会造成较大影响(去掉度和 负荷最大的单个节点就可以对网络造成25%的效率损失
