《存在级联故障的双层互依网络.doc》由会员分享，可在线阅读，更多相关《存在级联故障的双层互依网络.doc（20页珍藏版）》请在金锄头文库上搜索。
1、存在级联故障的双层互依网络摘要有的双层互依网络存在由两种常见互依类型导致的级联节点故障，本文定义并分析了这类网络的经典的最小顶点覆盖问题。以前对于互依网络的研究主要着重于从数值模拟的角度来看级联故障问题，而本文提出了一个准确的基于优化的方法确定的一组节点集的最小势，删除这些节点将通过级联故障作用严重影响这两层网络。我们分析了此问题的计算复杂度和线性0-1规则，也证明了推广了知名的对于经典的最小节点覆盖问题的2-近似方法的LP近似的比率结果。同时，我们介绍了“级联深度”的概念（即，给定网络的一系列级联故障的最大可能长度），并说明对于任何问题该参数可以再多项式时间过程内显式导出。一、介绍现代设施多
2、由复杂多样的网络系统构成，比如电网，远程通信和交通系统；而且这些系统间相互连接（即，互依网络）。只有每一个基础层都运作才能确保整个互依系统的运行。此情况是一个普遍例子是，有的网络依靠电力作为重要动力提供给它的节点来保证网络的运行（如远程通信或电脑设备），而底层的电力网络中的节点反过来受计算机/通信网络（如SCADA）中的节点控制。通常，基础设施系统之间的互依模式非常复杂，通过互依连接传递物品或者信息。几乎所有的现代基础设施以各种方式相互依存。因此，研究大规模基础设施系统内的相互作用非常重要。对整个复杂系统的缜密量化分析是很有挑战性的，然而最近的研究已经开始分析其包括双层网络的子系统，比如电力与
3、远程通信网络。显然，电力网络对现代基础设施具有极为重要的意义。对电力的极端依赖表明了安全可靠的能源供应的决定策略所面临的挑战。随着基础设施处于临近物理极限状态运作，系统的可靠性将减弱。最近，2011年9月8号，由短路导致的电力断供影响了数百万人口。城区的运输体统由于电力短缺也受到极大影响。由于与其他基础设施相互依赖，能源系统更易受到攻击。一个最近的互依基础设施级联故障的例子发生于2003年9月28日，意大利，当时一个电站停止工作导致通信网络的节点失效，该节点本是用来控制电力网络的，这样反过来又引发电力网络更大的故障，结果导致一系列灾难性的级联故障。这类双层互依网络类似的说明性例子如图1所示。电
4、力系统网络用著名的IEEE 118节点测试情况说明，它表示了1960年的美国中西部州部分电力系统网络。为了更具说明性，SCADA网络按幂律度分布随机产生，并离散放置在图中。互依连边连接了两个网络中的节点（仅仅部分此类边为了说明情况而表示出来）。通常，多重的互依连接为外出或者进入一个节点，因此，在不同网络中的节点中将可能出现“一到多”或者“多到一”的关系，这在模式Buldyrev（2010）产生了“一到一”的关系。有可能导致级联故障的相应的互依类型将会在随后的部分规范化，关于定义此问题时的说明性例子的计算性实验也将会被呈现。虽然网络鲁棒性的量化分析可由多种观点得出，但经典且直观的鲁棒性测量标准是
5、最小节点数（绝对或相对地取决于整个网络的规模），即整个网络的功能丧失所需要破坏的节点个数。显然，如果该数相比于整个网络的节点数较小的话，则可得出此网络面对攻击较脆弱的结论，然而如果该数与整个网络的规模相当，则该网络相比于随机或定向中断更具鲁棒性。从优化的观点来看，如果敌人拥有一个网络拓扑结构的完整信息，那么他可以解决确定节点最集的最小基数的优化问题，这些节点是他为了要限制残余网络运行功能所需要破坏的节点。例如，如果要求是以L为阈值限制剩余连接部分，此问题在cardinality-constrainedcritical node detection problem有论述。在L=1的特殊情况下，此
6、问题变为典型的最小节点覆盖问题，那些“触摸”了网络中所有边的节点集的最小基数，故而在所有最小覆盖节点都被破坏之后就剩下没有边存在的残余网络。本文中，我们定义并分析了双层互依网络情况下的最小节点覆盖问题，考虑了由两种常见连接类型导致的级联故障的可能性。据我们所知，这是第一份将经典优化问题拓展至互依网络结构的研究。确定出那些如果被删除将严重破坏整个网络的节点的集的最小基数，这无论在攻击还是预防角度都是极为有用的。在以前的构想中，攻击者确定出最应该摧毁的节点集，然而在之后的构想中，保护者有机会去保护这些已确认出的节点集并防止受到可能出现的级联故障传播的干扰。在分析互依网络鲁棒性方面已经有大量的工作被
7、做，包括一般的和挑战性的，互依网络在节点或边被移除情况下的性能及相对危险率的评估问题，还有分析和仿真的方法研究互依网络的级联故障。总之，大多数之前的研究主要集中于仿真，缺少基于优化的精确方法。本文在此方面探索。文章结构。本文后续组织结构如下。第二部分概括了将用到的基本定义；第三部分提出了数学分析结构并证明了所考虑问题的相关分析结果；第四部分证明了所有考虑问题的NP完备性的推断；第五部分给出了计算性实验的结果；第六部分总结了讨论过程并确定了未来工作的大致方向。图1 由电网和SCADA网络组成的双层互依网络。二、级联故障：基本概念我们建立一个双层互依网络的模型，图G1 = (V1,E1)，G2 =
8、 (V2,E2)为它的层，V1 = 1, . . . , n1，V2 = 1, . . . , n2 (n1 + n2 = n)为节点集，E1, E2为边。我们假设，某一层中的一个节点依赖于另一层中的某些节点，用E12,，E21表示互依连边的集合。如果（i,j）E12 ，则节点 jV2依赖于节点iV1 。例如，在图2 描述的网络中，和。为简单起见，我们将整个双层互依网络表示为。我们假设，最初的失效节点集由于互依关系（集合（E12, E21）逐步导致随后其他节点的失效，这类似于Buldyrev中的假设。这个假设的动机是，事实上在很多情况下级联故障并不立即传播，而是在各级联阶段之间有些许延迟。假设
9、级联阶段数由已定参数S限制。本文中我们考虑两种常见的互依关系：类型1（一到多）；类型2（多到一）。定义1.如果一个节点的失效导致所有依赖它的节点都失效，则这个互依网络具有类型1失效关系。图2 双层互依网络的例子定义2.如果一个节点的失效只能由它所依赖的所有节点的失效引起，则该互依网络具有类型2失效关系。对于一个给定的互依网络G（2），相互连接类型和级联阶段S数，级联的各阶段和节点覆盖的定义如下。定义3（级联阶段）.使初始失效/受攻击的节点集属于阶段0 。对于任意，阶段s包含属于阶段（s-1）或者由于依赖于阶段（s-1）的节点而被破坏的节点。定义4（节点覆盖）. G（2）节点覆盖是中节点的集合，
10、这些节点的失效将通过相应的级联故障作用导致阶段S，图G1和G2中节点覆盖集的失效。对于给定的互依网络G（2），互依的类型和级联阶段S数，求最小节点覆盖问题需要的最小节点覆盖集的势都在G（2）中。图3 类型1互依方式逐步导致的节点失效图3显示了阶段0时2个失效节点（图3 （b）阴影线）逐步导致的其它节点失效，假设为类型1，S=2.在阶段2，各层中的每一条边都被失效节点“触摸”，因此最初的失效节点表现为这个互依网络的一个节点覆盖（图3 （a）。图4 说明相同情况下假设为类型2互依。由于不同的互依类型，节点覆盖中的节点数为3，这意味着更多的节点需要在阶段0成为失效节点以在阶段2实现相同的结果。注意，
11、如果集合E12 ，E21均为空，则没有失效扩展发生，所考虑的问题将变为一个简单无向图G1G2的经典最小覆盖问题。三、优化模式3.1 类型1互依3.1.1 IP结构用表示边集E1,E2，互依连边集E12 ，E21，分别对应相应的元素。定义二元变量，说明层l（l=1,2）中的节点i至阶段s是否失效（若失效则=1；否则=0）。由这些变量，图G（2）最小节点覆盖问题的线性0-1结构可被表示如下：约束式（2）保证，阶段S时失效节点在整个两层网络中组成一个节点覆盖。约束式（3）和（4）递归地逐步构建由属于阶段0的节点失效导致的节点失效（在各层中）。约束式（5）和（6）显示了至阶段s时未受级联故障影响的节点
12、在阶段s仍保持运作所需要的条件。式子（1）-（7）包含(S+1)n个二元变量和个约束条件。接下来的部分描述了利用类型1互依方式的性质对于同一问题得到更简洁的式子，它包含n个二元变量和个约束条件（即，个体数不再取决于S）。同时，对于严格LP松弛，约束式（3）有而非n2 ，约束式（4）有而非n1.虽然我们在计算实验中使用了这些结果，但为了确保可靠性，我们使用前文中的规范系数进行更深入的讨论。3.1.2 更简洁的IP结构对于层m（m=1,2）中任一节点i，定义Drm（i）为层r（r=1,2）中节点的集合，在阶段0时Drm（i）中的任一节点的失效都会导致节点i在阶段S失效，这可一般性地表示为 Drm（
13、i）=kVr：若k在阶段0失效，则iVm在阶段S失效 （8）为了进一步简化，定义如果要强调它对于所考虑级联阶段S数的依赖性，我们将用到表达式 或。所以，当且仅当对于层1中的任意边（i，j），在集合中至少存在一个失效（被攻击）节点，并对于层2中的任意边（i，j），在集合中至少存在一个失效（被攻击）节点，则阶段S时所有受影响的节点构成一个节点覆盖。利用这个结论以及Drm（i）的定义，该问题可表示如下：这个表达式需要对网络中每一个节点i的Drm（i）集合进行确认。这个过程通过反向宽度优先从i到阶段S搜索很容易完成，因为Drm（i）是Vr中节点的集合，由此处存在lenghtS通过至节点iVm的最短直接
14、路径。3.1.3 LP松弛近似总所周知，最小节点覆盖问题的LP松弛提供了2-近似算法。在本部分中，分析了基于式（9）-（11）的LP松弛在互依网络中的最小节点覆盖问题的近似算法。推论1. 定义1和2为且则，式（9）-（11）的LP松弛提供了一个-近似。证明。使作为IP式（9）-（11）的LP松弛的一个最优解，使为LP和IP的最优目标值。显然，wLPwIP 。对l=1,2定义因为（9）-（11）每一个约束式中的变量数都不比大，矢量是IP（9）-（11）的一个可行解。使wIPLP为这个结果相应的目标函数，则同时，由（14）式，有结合最后两个不等式，有注意，如果各层之间不存在互依连接则=2，问题（9
15、）-（11）减少为标准的最小节点覆盖问题。因此，推论1包含了最为特殊情况的标准最小节点覆盖问题的经典的2-近似结果。3.1.4 级联深度S*如前所述，级联故障过程中总的阶段数不可能超过S=n-1（“最长的可能级联”），因为在每一个阶段级联或者停止或者导致多于一个的节点失效。故，如果要“无约束”失效阶段数的该问题，则应该被用在之前提到的问题公式化中。然而，由于计算的原因，使用最大可能S并不一定有效，因为这可能需要大量不必要计算和变量的调用。我们给出了怎样选择这样一个失效阶段S*数，S*n-1。问题公式化F1(S)和F1c(S)对所有SS*有相同的最优解。在表达式F1(S)和F1c(S)中，我们用论点S帮助问题公式化F1，有给定参数S的F1c。定义5. 级联深度S*是给定的互依网络G（2）的级联故障序列的最大可能长度。下一个推论显示在类型1互依情况下，对于任意给定的例题，级联深度可被明确地确定。推论2. 使为类型1互依连接的互依网络，dist（i，j）为在图G中从节点i到j的最短直接路径的长度（若从i至j不存在路径则dist（i，j）=）。则，网络G（2）的级联深度由下式给出而且，规范式F1c(S)对于所有是相同的。图5 推论3中S=5, S*=7的结构化互依网络。虚线部分只包含了孤立节点。表1 随机产生的均匀及幂律度随机图，的问题规范化F1c
