复杂网络上的相继故障课件.ppt
2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,1,复杂网络上的相继故障,报告人：苏延森2009年11月7日,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,2,一.问题提出,1).Internet中，由于病毒攻击 少数路由器过载 其他路由器接连过载 很多路由器不能正常工作。,1.现象：,2).铁路网中，由于列车出轨 一段铁路线受阻 其他与之相连的铁路线接连受阻 一部分铁路线不能正常工作。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,3,2.抽象：,相继故障：一个或者少数几个节点或边发生故障，通过节点之间的耦合关系引起其他节点或者边发生故障，这样就会产生连锁效应，最终导致相当一部分节点甚至整个网络崩溃。这一现象称为“相继故障”，也称为“雪崩”。,研究内容：1).什么原因导致相继故障?系统的鲁棒性如何？2).如何预防和控制相继故障？,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,4,研究方法：借助于典型的拓扑结构。针对不同实际问题建立数学模型，分析系统鲁棒性。相继故障属于网络动力学行为，而网络动力学行为与网络自身的拓扑结构联系紧密，为了简便起见，在一些典型的拓扑网络上来研究相继故障。注意：1）BA网络：现实很多网络具有无标度特性，比如Internet网络,新陈代谢网络。2）随机网：易处理,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,5,一.复杂网络相继故障的动态模型分析,1.负荷容量模型 1.1.节点动态模型 1.2.边动态模型 1.3.节点与边混合动态模型2.二值影响模型3.沙堆模型4.OPA模型,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,6,1.1节点动态模型,Moreno模型：（BA网络）1).假设BA网络中有N个节点，每个节点i有一个安全阈值，服从韦伯分布：其中，为形状参数，越大，取值越平均。,2).假设每个节点承担的负荷相同，（F表示总负荷）。3).如果，节点i发生故障，将其负荷平均地传送给与之直接相连的无故障节点，并去除该节点。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,7,这里的m相当于公式里的,它是形状参数，越大，取值的离散程度越小,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,8,4).相继故障规模(间接)：最大连通子图的相对值：,（原因：度量网络的鲁棒性参量：最大连通子图相对值，平均路径长度）,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,9,Moreno模型分析1 选择适当的参数使得对应的网络性能较好,(1)总体趋势：临界值(2)阈值分布较均匀的网络对故障更具承受能力,横轴：每个节点的负荷纵轴：最大连通子图相对值,故障结束时最大连通子图相对值与 的关系图,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,10,Moreno模型分析2,度分布图,取定韦伯分布形状参数=5横轴：度k纵轴：度为k的个数,如何从结构角度分析相继故障的发生？,负荷值大于临界值0.52之后网络中出现大量度小的节点,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,11,Motter模型：(BA网络),1.假设：信息或能量总是在节点对之间沿着最短路径交换。因此，节点的负荷定义为该点的介数。2.节点容量：其中 是一个容许系数,Lj为初始负荷。3.如果，节点i发生故障，将其负荷根据最短路径策略传送给与之直接相连的无故障节点，并去除该节点。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,12,Motter模型分析1如果移除的点的性质不同，对网络鲁棒性有影响？,（BA网络）容许系数最大连通子图相对值,1).横轴：容许系数 纵轴：最大连通子图相对值G,2).鲁棒性：随机移除 任意点度大点随机移除 任意点负荷大点(研究原因？),2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,13,分析：,(1)度大点关键节点,？,例如：行政机构网或者职位关系网中，度小的点不一定不关键。所以分析研究移除负荷大的节点对网络性能的影响。,(2).结果：移除随机选择的节点对网络不会造成很大影响，但是度大或者负荷大的节点对维持网络结构起着重要作用，一旦移除网络连通性降低。所以要预防相继故障要从保护关键节点做起。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,14,Motter模型分析2 均匀网络与非均匀网络（平均度相同）性能好坏比较,研究内容：构造具有相同节点数，相同平均度的均匀网络与BA网络。相同操作：随机移除节点或者移除容量大的节点结果：均匀网络对于攻击的鲁棒性比非均匀网络要好。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,15,一.复杂网络相继故障的动态模型分析,1.负荷容量模型 1.1.节点动态模型 1.2.边动态模型 1.3.节点与边混合动态模型2.二值影响模型3.沙堆模型4.OPA模型,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,16,1.2 边动态模型,在道路交通网络中，道路的拥塞问题不可忽视。Moreno等人研究BA网络中由于边的拥塞而引发的相继故障。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,17,边动态模型：,(1).假设连接节点i、j的边的负荷 服从如下均匀分布，其中表示平均负荷,(2).假设每条边的容量为1,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,18,(3).如果li,jC表明边发生了拥塞，应该将li,j按照一定的动态规则重新分配（平均分配，随机选取一部分分配给其相邻的未拥塞边，如果相邻的所有边都拥塞，将负荷全局分配给整个网络或者直接丢弃）。负荷的重新分配有可能导致其他边拥塞，从而产生相继故障。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,19,边动态模型分析1 故障发生后负荷不同分配策略对网络性能的影响,网络有最大连通子图的概率PG与网络平均负荷的关系,1.横轴：网络平均负荷 纵轴：有最大连通子图的概率,2.各分配方式下均存在阈值 c1，c1时以一定的概率发生拥塞。,3.存在 c2，c2时网络崩溃。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,20,一.复杂网络相继故障的动态模型分析,1.负荷容量模型 1.1.节点动态模型 1.2.边动态模型 1.3.节点与边混合动态模型2.二值影响模型3.沙堆模型4.OPA模型,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,21,1.3 节点与边混合模型,一般的通信、传输网络中既要考虑到节点的容量，又要考虑起运输作用的边的容量。比如：电力网。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,22,模型建立：,(1).t时刻节点i的负荷为Li(t)，表示t时刻通过节点i的效率最优路径的条数。效率最优路径：对于节点对(i,j)之间的所有路径，计算整条路径的调和效率，取最大值(2).节点容量(3).初始，若序对(i,j)间存在边，那么eij=1;否则eij=0;随后eij演化公式为,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,23,(4)某一节点由于故障从网络中去除后，网络中节点间的效率最优路径将会发生改变，导致负荷的重新分布，可能引起其他节点过载，引发新一轮负荷分配。(5).用相继故障结束后网络的平均效率衡量网络的破坏程度,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,24,一.复杂网络相继故障的动态模型分析,1.负荷容量模型 1.1.节点动态模型 1.2.边动态模型 1.3.节点与边混合动态模型2.二值影响模型3.沙堆模型4.OPA模型,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,25,2.二值影响模型,Watts模型：1).构造具有度分布为Pk的随机网络，其网络平均度为=z。2).网络中每个节点状态只能是1（故障）或0（正常）。所有节点的初始状态为0。t=0时刻随机设置部分节点的状态为1,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,26,接下来每一时刻，节点状态由下面的规则决定：若一个节点的k个相邻节点中具有状态1的节点数与k的比值等于或超过赋予这个节点的状态切换阈值（事先设定），则节点状态为1，否则为0；一旦节点状态设置为1，则状态保持不变。如果网络中节点的度分布与阈值分布具有一定的关系，则单个或若干个节点发生故障可以产生雪崩效应。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,27,一.复杂网络相继故障的动态模型分析,1.负荷容量模型 1.1.节点动态模型 1.2.边动态模型 1.3.节点与边混合动态模型2.二值影响模型3.沙堆模型4.OPA模型,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,28,3.沙堆模型,沙堆问题：在平面堆上沙子沙堆逐渐变大沙崩,临界状态：自组织临界（SOC）,临界状态是一种及其不稳定的状态，如果一个系统处于临界状态，其内部的各种力量正在僵持，整个系统很敏感，此时最小的力量也可能发生无比大的影响。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,29,（1）每个节点i有高度hi，同时有阈值zi。（2）每个时序随机选择一个节点i，增高 hi=hi+1。（3）若hi zi，节点处于不稳定状态，执行“倾倒”操作。（4）若上一步产生了新的不稳定节点，则并行地执行“倾倒”操作，直到不再产生新的不稳定节点为止。这就模拟了一次相继故障的全过程。（5）重复（2）到（4）步得到故障规模的分布情况。具有幂律特性。,计算机模拟沙堆模型,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,30,当沙堆越来越陡进入临界状态，沙堆上的沙粒处于将要翻滚下去的边缘，此时，落下的一粒沙子将会导致什么结果？几乎无影响？稍微有些变动？沙崩？,(1)临界状态与不可预测性是连在一起的。(2)由一粒沙子可以引发从小到大任何一种规模的变动(3)不同规模的变动发生的可能性是不一样的,临界状态：,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,31,地震的发生：由于板块的移动，慢慢积累起来的压力使地壳内各种大小不同的岩石处于一种临界状态，当其中的一块岩石终于经受不住压力开始下滑，就会造成地壳岩石的重组，同时也引发了地震。,“沙堆效应”的现象：,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,32,一.复杂网络相继故障的动态模型分析,1.负荷容量模型 1.1.节点动态模型 1.2.边动态模型 1.3.节点与边混合动态模型2.二值影响模型3.沙堆模型4.OPA模型,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,33,4.OPA模型（最优潮流方法模型）,在电网模型中提出的，由初始状态向自组织临界状态转化的模型称为最优潮流方法模型。,现象：假设电力输送网的电压等级是500V,当突然发生超过其负载的冲击电压569V时,为了安全，先切断重工业用户的供应，这种电力供应突然下降，引发了数十个发电站自动关闭，造成普遍停电。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,34,当发电机向受端系统送电时，如果由于某种原因断开了一个线路，如果保持输电方送出的电力不变，余下的线路的传输功率必然会增加，这就是“大负荷转移”。如果超过其安全阈值，必然会出现恶性的连锁反应。,1).分析现象：,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,35,当用电需求增大时，表现为相应节点的负荷增大，要求在输电线能够承受的前提下，提供更多的电量。,措施：第一，部分节点断电（使得其他节点满足需求）。缺点：为生活带来不便。第二，加大发电机功率。缺点:为一次大规模相继故障做积累。(?),2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,36,2).模型建立：,(1)假设网络中有N个节点，节点分为两类：负荷节点（功率为负值）和发电机节点（功率为正值）。,第k天网络出现故障，这时输电线可能有两种故障：没有过载条件下的随机故障；过载下的故障。如何判断是究竟哪种故障？前一种发生的概率比较小，如果是后者，如何分配功率从而满足需求？,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,37,(2).Pik:第k天，节点i的功率 Pk=(P1k,P2k,Pnk)T:第k天所有节点的功率 Fik:第k天，输电线i所承载的功率 Fk=(F1k,F2k,Fmk)T:第k天所有输电线承载的功率(3).假设所有输电线本身无功率损耗；输电线功率不能超过它的最大值。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,38,(4).假设所有的负荷均为直流负荷，节点功率和输电线功率存在线性关系：Fk=A*Pk(A:关联矩阵),(5).系统状态：每条输电线的功率与相应最大功率的比值,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,39,(6).判断输电线故障原因：随机故障？输电线过载？,Pline j outaged=h0(Mjk),Pline j outaged=h1(Mjk),2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,40,(7).假设每天节点功率略大于前一天该节点的功率。设负荷扩增参数为，比如：第l天与第l-1天的负荷比为 那么每个节点在第k天的负荷，以及输电线在第k天的负荷可由在第0天的表示,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,41,(8).如果一条输电线由于过载出现故障，设输电线容量扩增参数为。第j条线整修后,负荷扩增参数容量扩增参数,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,42,利用线性规划方法重新调整电网功率分配,(1)构造代价函数：,限制条件：,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,43,随着负载负荷的增加，发电机节点容量也有相应的增加，逐步向自组织临界状态发展，所有的状态都将趋向于1。,模型中：输电线容量扩增参数 直接影响电网故障的规模和频率。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,44,二.基于耦合映像格子的相继故障模型,2.1 CML相继故障模型2.2 典型拓扑结构中的相继故障,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,45,2.1 CML相继故障模型,例：实际城市交通系统中，经常出现网络上某路段由于突发的事故或者施工活动等造成该路段的拥塞。将路段的交通流状态做为研究对象，要么该路段交通流运行正常，要么该路段交通流拥挤称为路段失效。由于某时刻路段受到外部扰动，其交通流状态从正常状态变化到失效状态，由于城市道路的连通性，某条路段的实效会向它近邻的路段传播，然后逐步蔓延，最终可能导致网络中所有路段失效。,对于城市交通系统这样的时空非线性系统，可以将实际路段映射为网络节点（路名对偶法），利用耦合映像格子进行分析。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,46,包含N个节点的一维耦合映像格子模型：,(1).,体现了时空动力学行为。非线性函数f表示节点自身的动态行为，这里取为混沌Logistic映射：f(x)=4x(1-x)，x在(0,1),则f(x)也在(0,1),(2).根据路名对偶法，节点对应于路段，如果节点i的状态在m个时序内始终在(0,1)内，那么节点i处于正常状态；如果在m时刻，节点i的状态xi(m)1,那么称该节点在此刻发生故障，节点在以后任意时刻状态恒为0.特点：不可逆,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,47,不妨设在时刻m节点c受到外部扰动R=1而发生故障，m+1时刻，c的邻居节点也受到c的影响，可能发生故障。,结果：对所有tm，。在t时刻，网络中发生故障的总数用I(t)表示，当网络中不再有节点发生故障时，网络故障的最终规模用I表示，,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,48,思考：利用耦合映像格子模型分析基因状态的改变？相同：时(随时间演化)空(网络结构)非线性动力学不同：基因状态表达，不表达；若前一状态是0（不表达），后一状态可以是1（表达）。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,49,二.基于耦合映像格子的相继故障模型,2.1 CML相继故障模型2.2 典型拓扑结构中的相继故障,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,50,2.2典型拓扑结构CML的相继故障,在几个典型拓扑结构网络上研究耦合映像模型：全局耦合网络CML,小世界网络CML,无标度网络CML,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,51,研究结果：(1)对全局耦合CML，扰动R存在两个阈值。RRc1时，不会发生相继故障，RRc2时，网络中所有节点都会发生故障。,1).全局耦合CML:随机选取节点使之发生故障，扰动R与相继故障的最终规模的关系,另外还有结果表明：规模非常大的全局耦合CML对较大的局部干扰具有很强的鲁棒性，几乎不可能发生全局故障。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,52,2).小世界耦合CML,研究结果：(1)与最近邻CML相比，小世界CML中更容易发生全局相继故障,横轴：重连概率p纵轴：达到全局相继故障所用时间,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,53,3).无标度CML,研究结果：与全局耦合CML相比，BA无标度CML更容易引发相继故障。,2023/3/21,书山有路勤为径学海无涯苦作舟 专业分享，敬请收藏,54,谢谢！,
