复杂网络上的相继故障课件.ppt

1、2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏1复杂网络上的相继故障复杂网络上的相继故障报告人：苏延森2009年11月7日2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏2一一.问题提出问题提出 1).Internet中，由于病毒攻击 少数路由器过载 其他路由器接连过载 很多路由器不能正常工作。 1.现象：2).铁路网中，由于列车出轨 一段铁路线受阻 其他与之相连的铁路线接连受阻 一部分铁路线不能正常工作。2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏32.抽象： 相继故障相继故障：一个或者少数一个或者少数几个节点或边节点或边发生故障，通过节

2、点之间的耦合关系耦合关系引起其他节点或者边发生故障，这样就会产生连锁效应，最终导致相当一部分节点甚至整个网络崩溃。这一现象称为“相继故障”，也称为“雪崩”。研究内容：1).什么原因导致相继故障?系统的鲁棒性如何？ 2).如何预防和控制相继故障？2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏4研究方法：借助于典型的拓扑结构。针对不同实际问题建立数学模型，分析系统鲁棒性。相继故障属于网络动力学行为，而网络动力学行为与网络自身的拓扑结构联系紧密，为了简便起见，在一些典型的拓扑网络上来研究相继故障。注意：1）BA网络：现实很多网络具有无标度特性，比如Internet网络, 新陈代谢网

3、络。 2）随机网：易处理2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏5一一.复杂网络相继故障的动态模型分析复杂网络相继故障的动态模型分析1.负荷容量模型 1.1.节点动态模型 1.2.边动态模型 1.3.节点与边混合动态模型2.二值影响模型3.沙堆模型4.OPA模型2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏61.1节点动态模型Moreno模型： （BA网络）1).假设BA网络网络中有N个节点，每个节点i有一个安全阈值 ， 服从韦伯分布： 其中， 为形状参数， 越大， 取值越平均。 Nii,.,2 , 1, n,.,21)(1)(iePii2).假设每个

4、节点承担的负荷相同， （F表示总负荷）。3).如果 ，节点i发生故障，将其负荷平均地平均地传送给与之直接相连的无故障节点，并去除该节点。NFi2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏7这里的m相当于公式里的它是形状参数，越大，取值的离散程度越小2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏84).相继故障规模(间接)： 最大连通子图的相对值：NNG/（原因：度量网络的鲁棒性参量：最大连通子图相对值，平均路径长度）2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏9Moreno模型分析1 选择适当的参数使得对应的网络性能较好(1)总体趋势：

5、临界值(2)阈值分布较均匀的网络对故障更具承受能力横轴：每个节点的负荷纵轴：最大连通子图相对值故障结束时最大连通子图相对值与 的关系图2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏10Moreno模型分析2度分布图取定韦伯分布形状参数=5横轴：度k纵轴：度为k的个数如何从结构角度分析相继故障的发生？负荷值大于临界值0.52之后网络中出现大量度小的节点2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏11Motter模型： (BA网络)1.假设：信息或能量总是在节点对之间沿着最短路径交换。因此，节点的负荷定义为该点的介数。2.节点容量：其中 是一个容许系数,Lj为

6、初始负荷。3.如果 ，节点i发生故障，将其负荷根据最短路径策略传送给与之直接相连的无故障节点，并去除该节点。NjLCjj,.,2 , 1,)1 (0iC2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏12Motter模型分析1如果移除的点的性质不同，对网络鲁棒性有影响？（BA网络）容许系数最大连通子图相对值随机选择节点选择度大的点选择负荷大的点1).横轴：容许系数 纵轴：最大连通子图相对值G2).鲁棒性：随机移除 任意点度大点随机移除 任意点负荷大点(研究原因？)2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏13分析：(1)度大点关键节点 ？ 例如：行政机构网

7、或者职位关系网中，度小的点不一定不关键。所以分析研究移除负荷大的节点对网络性能的影响。(2).结果：移除随机选择的节点对网络不会造成很大影响，但是度大或者负荷大的节点对维持网络结构起着重要作用，一旦移除网络连通性降低。所以要预防相继故障要从保护关键节点做起。2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏14Motter模型分析2 均匀网络与非均匀网络（平均度相同）性能好坏比较研究内容：构造具有相同节点数，相同平均度的均匀网络与BA网络。相同操作：随机移除节点随机移除节点或者移除容量大的节移除容量大的节点点结果：均匀网络对于攻击的鲁棒性比非均匀网络要好。2022-6-5书山有路

8、勤为径学海无涯苦作舟 专业分享，敬请收藏15一一.复杂网络相继故障的动态模型分析复杂网络相继故障的动态模型分析1.负荷容量模型 1.1.节点动态模型 1.2.边动态模型 1.3.节点与边混合动态模型2.二值影响模型3.沙堆模型4.OPA模型2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏161.2 边动态模型在道路交通网络中，道路的拥塞问题不可忽视。Moreno等人研究BA网络中由于边的拥塞而引发的相继故障。2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏17边动态模型：(1).假设连接节点i、j的边的负荷 服从如下均匀分布，其中表示平均负荷) 10(,jiji

9、ll(2).假设每条边的容量为12022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏18(3).如果li,jC表明边发生了拥塞，应该将li,j按照一定的动态规则重新分配（平均分配，随机选取一部分分配给其相邻的未拥塞边，如果相邻的所有边都拥塞，将负荷全局分配给整个网络全局分配给整个网络或者直接丢弃）。 负荷的重新分配有可能导致其他边拥塞，从而产生相继故障。 2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏19边动态模型分析1 故障发生后负荷不同分配策略对网络性能的影响网络有最大连通子图的概率PG与网络平均负荷的关系随机分配+直接丢弃平均分配+全局分配随机分配+全局分配

10、1.横轴：网络平均负荷 纵轴：有最大连通子图的概率2.各分配方式下均存在阈值 c1， c1时以一定的概率发生拥塞。3.存在 c2， c2时网络崩溃。2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏20一一.复杂网络相继故障的动态模型分析复杂网络相继故障的动态模型分析1.负荷容量模型 1.1.节点动态模型 1.2.边动态模型 1.3.节点与边混合动态模型2.二值影响模型3.沙堆模型4.OPA模型2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏211.3 节点与边混合模型一般的通信、传输网络中既要考虑到节点的容量，又要考虑起运输作用的边的容量。比如：电力网。2022

11、-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏22模型建立：(1). t时刻节点i的负荷为Li(t)，表示t时刻通过节点i的效率最优路径的条数。效率最优路径：对于节点对(i,j)之间的所有路径，计算整条路径的调和效率，取最大值(2).节点容量(3). 初始，若序对(i,j)间存在边，那么eij=1;否则eij=0;随后eij演化公式为0),0(*iiLC1*)1(kee2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏23(4)某一节点由于故障从网络中去除后，网络中节点间的效率最优路径将会发生改变，导致负荷的重新分布，可能引起其他节点过载，引发新一轮负荷分配。(5).用

12、相继故障结束后网络的平均效率衡量网络的破坏程度2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏24一一.复杂网络相继故障的动态模型分析复杂网络相继故障的动态模型分析1.负荷容量模型 1.1.节点动态模型 1.2.边动态模型 1.3.节点与边混合动态模型2.二值影响模型3.沙堆模型4.OPA模型2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏252.二值影响模型Watts模型：1).构造具有度分布为Pk的随机网络随机网络，其网络平均度为=z。2).网络中每个节点状态只能是1（故障）或0（正常）。 所有节点的初始状态为0。 t=0时刻随机设置随机设置部分节点的状态为

13、1 2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏26接下来每一时刻，节点状态由下面的规则决定：若一个节点的k个相邻节点中具有状态1的节点数与k的比值等于或超过赋予这个节点的状态切换阈值（事先设定），则节点状态为1，否则为0；一旦节点状态设置为1，则状态保持不变。 如果网络中节点的度分布与阈值分布具有一定的关系，则单个或若干个节点发生故障可以产生雪崩效应。2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏27一一.复杂网络相继故障的动态模型分析复杂网络相继故障的动态模型分析1.负荷容量模型 1.1.节点动态模型 1.2.边动态模型 1.3.节点与边混合动态模型2

14、.二值影响模型3.沙堆模型4.OPA模型2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏283.沙堆模型沙堆问题：在平面堆上沙子沙堆逐渐变大沙崩临界状态：自组织临界（SOC） 临界状态是一种及其不稳定的状态，如果一个系统处于临界状态，其内部的各种力量正在僵持，整个系统很敏感，此时最小的力量也可能发生无比大的影响。2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏29（1）每个节点i有高度hi，同时有阈值zi。（2）每个时序随机选择选择一个节点i ，增高增高 hi = hi +1。（3）若hi zi ，节点处于不稳定状态，执行“倾倒倾倒”操作。（4）若上一步产生了新

15、的不稳定节点，则并行地执行“倾倒”操作，直到不再产生新的不稳定节点为止。这就模拟了一次相继故障的全过程。（5）重复（2）到（4）步得到故障规模的分布情况。具有幂律特性。计算机模拟沙堆模型2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏30 当沙堆越来越陡进入临界状态，沙堆上的沙粒处于将要翻滚下去的边缘，此时，落下的一粒沙子将会导致什么结果？几乎无影响？稍微有些变动？沙崩？(1)临界状态与不可预测性是连在一起的 。(2)由一粒沙子可以引发从小到大任何一种规模的变动 (3)不同规模的变动发生的可能性是不一样的临界状态：2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏

16、31 地震的发生：由于板块的移动，慢慢积累起来的压力使地壳内各种大小不同的岩石处于一种临界状态临界状态，当其中的一块岩石终于经受不住压力开始下滑，就会造成地壳岩石的重组，同时也引发了地震。 “沙堆效应”的现象：2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏32一一.复杂网络相继故障的动态模型分析复杂网络相继故障的动态模型分析1.负荷容量模型 1.1.节点动态模型 1.2.边动态模型 1.3.节点与边混合动态模型2.二值影响模型3.沙堆模型4.OPA模型2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏334.OPA模型（最优潮流方法模型） 在电网模型中提出的，由

17、初始状态向自组自组织临界状态织临界状态转化的模型称为最优潮流方法模型。现象：假设电力输送网的电压等级是500V, 当突然发生超过其负载的冲击电压569V时,为了安全，先切断重工业用户的供应，这种电力供应突然下降，引发了数十个发电站自动关闭，造成普遍停电。2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏34 当发电机向受端系统送电时，如果由于某种原因断开了一个线路，如果保持输电方送出的电力不变，余下的线路的传输功率必然会增加，这就是“大负荷转移”。如果超过其安全阈值，必然会出现恶性的连锁反应。1).分析现象：2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏35当用

18、电需求增大时，表现为相应节点的负荷增大，要求在输电线能够承受的前提下，提供更多的电量。措施：第一，部分节点断电（使得其他节点满足需求）。缺点：为生活带来不便。 第二，加大发电机功率。缺点:为一次大规模相继故障做积累。(?)2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏362).模型建立：(1)假设网络中有N个节点，节点分为两类：负荷节点（功率为负值）和发电机节点（功率为正值）。 第k天网络出现故障，这时输电线可能有两种故障：没有过载条件下的随机故障；过载下的故障。如何判断是究竟哪种故障？前一种发生的概率比较小，如果是后者，如何分配功率从而满足需求？2022-6-5书山有路勤为

19、径学海无涯苦作舟 专业分享，敬请收藏37(2). Pik:第k天，节点i的功率 Pk=(P1k,P2k,Pnk)T:第k天所有节点的功率 Fik:第k天，输电线i所承载的功率 Fk=(F1k,F2k,Fmk)T:第k天所有输电线承载的功率(3).假设所有输电线本身无功率损耗；输电线功率不能超过它的最大值。2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏38(4).假设所有的负荷均为直流负荷，节点功率和输电线功率存在线性关系：Fk=A*Pk (A:关联矩阵)(5).系统状态：每条输电线的功率与相应最大功率的比值maxjkjkjkFFM2022-6-5书山有路勤为径学海无涯苦作舟

20、专业分享，敬请收藏39(6).判断输电线故障原因： 随机故障？ 输电线过载？Pline j outaged=h0(Mjk)Pline j outaged=h1(Mjk)2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏40(7).假设每天节点功率略大于前一天该节点的功率。 设负荷扩增参数负荷扩增参数为 ，比如：第l天与第l-1天的负荷比为 那么每个节点在第k天的负荷，以及输电线在第k天的负荷可由在第0天的表示l2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏41(8).如果一条输电线由于过载出现故障，设输电线容量扩增参数容量扩增参数为 。第j条线整修后maxmax

21、)1(jkkkjFFminmax1负荷扩增参数1,那么称该节点在此刻发生故障，节点在以后任意时刻状态恒为0.特点：不可逆2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏47不妨设在时刻m节点c受到外部扰动R=1而发生故障，m+1时刻，c的邻居节点也受到c的影响，可能发生故障。结果：对所有tm， 。在t时刻，网络中发生故障的总数用I(t)表示，当网络中不再有节点发生故障时，网络故障的最终规模用I表示，)(limtIIt0)(txc2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏48思考：利用耦合映像格子模型分析基因状态的改变？相同：时(随时间演化)空(网络结构)非

22、线性动力学不同：基因状态表达，不表达；若前一状态是0（不表达），后一状态可以是1（表达）。?)()()1 () 1(tXftxftxii2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏49二二.基于耦合映像格子的相继故障模型基于耦合映像格子的相继故障模型l2.1 CML相继故障模型l2.2 典型拓扑结构中的相继故障 2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏502.2典型拓扑结构CML的相继故障在几个典型拓扑结构网络上研究耦合映像模型：全局耦合网络CML,小世界网络CML,无标度网络CML2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏51

23、研究结果：(1)对全局耦合CML，扰动R存在两个阈值。RRc1时，不会发生相继故障，RRc2时，网络中所有节点都会发生故障。1).全局耦合CML: 随机选取节点使之发生故障，扰动R与相继故障的最终规模的关系另外还有结果表明：规模非常大的全局耦合CML对较大的局部干扰具有很强的鲁棒性，几乎不可能发生全局故障。2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏522).小世界耦合CML研究结果：(1)与最近邻CML相比，小世界CML中更容易发生全局相继故障横轴：重连概率p纵轴：达到全局相继故障所用时间2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏533).无标度CML研究结果：与全局耦合CML相比，BA无标度CML更容易引发相继故障。2022-6-5书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏54