基于负荷局域择优重新分配原则的复杂网络上的相继故障.doc

物理学报第 58 卷 第 6 期 2009 年 6 月 物 理 学 报 第 58 卷 第 6 期 2009 年 6 月 100023290Π2009Π58 (06) Π3714208 Vol . 58 ,No . 6 ,J une ,2009 ν 2009 Chin. Phys. Soc . ACTA PHYSICA SINICA 基于负荷局域择优重新分配原则的 复杂网络上的相继故障 3 王建伟? 荣莉莉 ( 大连理工大学系统工程研究所 ,大连 116024) (2008 年 11 月 13 日收到 ;2008 年 11 月 20 日收到修改稿) 相继故障普遍存在现实的网络系统中 ,为了更好地探讨复杂网络抵制相继故障的全局鲁棒性 ,采用网络中节 α 点 j 上的初始负荷为 L j = kj ( kj 为节点 j 的度) 的形式 ,并基于崩溃节点上负荷的局域择优重新分配的原则 ,提出了 一个新的相继故障模型. 依据新的度量网络鲁棒性的指标 ,探讨了 4 种典型复杂网络上的相继故障现象. 数值模拟 表明 ,当参数α= 1 时 ,所有的 4 种网络都达到了最强的鲁棒性 ,并且网络的鲁棒性与网络的平均度〈 k 〉正相关. 此 外 ,通过理论解析也验证了数值模拟的结论. 关键词 : 相继故障 , 复杂网络 , 关键阈值 , 相变 PACC : 0520 许多有价值的结论. Motter 等3 提出一个相继故障 模型 ,并研究了复杂网络上的相继故障现象. 在一个 给定的具有 N 个节点的网络中 ,假设信息或能量总 是在节点对之间沿着最短路径交换 ,并且节点的负 荷定义为该节点的介数. 他们发现如果网络的负荷 分布具有非均匀性 ,并且去掉的节点的负荷较高 ,就 会导致相继故障的发生. 后来 ,Crucitti 等4 的研究结 果也表明 ,网络中的流或介数分配越不均匀 ,网络发 生相继故障的范围越大. 因此 ,一个控制相继故障发 生的有效措施是对网络中度大的节点或介数较大的 节点重点保护 ,或者使网络中的流分配得比较均匀. 此外 ,许多的相继故障模型5 —12 被提出 ,并得到了深 入的探讨. 然而 ,在大多数研究中 ,节点上的负荷基 本上都定义为节点的介数 ,而崩溃节点上负荷的重 新分配 ,大多数按照最短路径的路由策略原则 ,这就 要求每个节点必须具有全局的网络信息. 而实际上 , 现实的大多数网络 ,全局信息的获得是非常困难的. 因此 ,寻求较简单的负荷赋予方式以及比较实际的 负荷重新分配的原则是至关重要的. 我们的模型启发于现实复杂系统中. 在 Internet (或交通网络) 上 ,通常来说 ,一方面 ,具有大量连接 边的路由器 ,具有更多的信息流将通过它来路由 ,同 11 引 言 相继故障是与网络上的传播行为有很多相似之 处的一种现象 ,普遍发生在各种关键生命线系统网 络中1 ,2 ,如电网 、供水网 、供气网 、交通网 、通信网 等. 在这些网络中 ,存在着大量的负载 ,这些负载可 以是物质 、信息或能量 ,可以是具体的 ,也可以是抽 象的. 网络上的这些负载都是动态变化的 ,而且网络 中节点承受负载的能力是有限的. 一个节点的失效 会导致网络负载的重新分配 ,而负载的重分配又使 得某些节点上的负载超过其负载容量而失效 ,这些 节点的失效又可能导致其他节点的“接连失效”,产 生连锁反应 ,最终导致相当一部分节点甚至整个网 络的崩溃 ,这种现象就称为相继故障. 大规模的相继 故障一旦发生 ,往往具有极强的破坏力和影响力 ,例 如 2008 年初我国南方电力网络的崩溃 、北美电力网 大崩溃事故 、因特网阻塞以及 20 世纪 90 年代末爆 发的亚洲经济危机等都可以从某种程度上认为是因 相继故障所导致的灾难. 因此 ,相继故障理论的研究 就显得非常重要且具有现实意义. 近年来 ,相继故障得到了广泛的研究并得出了 3 国家自然科学基金( 批准号 资助的课题. ? E2mail :wdut @yahoo . cn 时 ,它也往往具有更强的处理信息流的能力 ;而另一方面 ,当一个路由器崩溃或失效后 ,未处理的信息流 将被重新分配到它的邻居节点上 ,但为了避免进一步的拥挤现象 ,得到重新分配的信息流更倾向于选 择具有较高处理 时 ,它也往往具有更强的处理信息流的能力 ;而另一 方面 ,当一个路由器崩溃或失效后 ,未处理的信息流 将被重新分配到它的邻居节点上 ,但为了避免进一 步的拥挤现象 ,得到重新分配的信息流更倾向于选 择具有较高处理能力的邻居节点 ,以保持网络的整 体流畅. 有鉴于此 ,采用网络中节点上的初始负荷为 节点本身度的负载函数形式 ,并基于崩溃节点负荷 局域择优