存在级联故障的双层互依网络.docVIP

存在级联故障的双层互依网络 摘要 有的双层互依网络存在由两种常见互依类型导致的级联节点故障，本文定义并分析了这类网络的经典的最小顶点覆盖问题。以前对于互依网络的研究主要着重于从数值模拟的角度来看级联故障问题，而本文提出了一个准确的基于优化的方法确定的一组节点集的最小势，删除这些节点将通过级联故障作用严重影响这两层网络。我们分析了此问题的计算复杂度和线性0-1规则，也证明了推广了知名的对于经典的最小节点覆盖问题的2-近似方法的LP近似的比率结果。同时，我们介绍了“级联深度”的概念（即，给定网络的一系列级联故障的最大可能长度），并说明对于任何问题该参数可以再多项式时间过程内显式导出。 一、介绍 现代设施多由复杂多样的网络系统构成，比如电网，远程通信和交通系统；而且这些系统间相互连接（即，互依网络）。只有每一个基础层都运作才能确保整个互依系统的运行。此情况是一个普遍例子是，有的网络依靠电力作为重要动力提供给它的节点来保证网络的运行（如远程通信或电脑设备），而底层的电力网络中的节点反过来受计算机/通信网络（如SCADA）中的节点控制。 通常，基础设施系统之间的互依模式非常复杂，通过互依连接传递物品或者信息。几乎所有的现代基础设施以各种方式相互依存。因此，研究大规模基础设施系统内的相互作用非常重要。对整个复杂系统的缜密量化分析是很有挑战性的，然而最近的研究已经开始分析其包括双层网络的子系统，比如电力与远程通信网络。 显然，电力网络对现代基础设施具有极为重要的意义。对电力的极端依赖表明了安全可靠的能源供应的决定策略所面临的挑战。随着基础设施处于临近物理极限状态运作，系统的可靠性将减弱。最近，2011年9月8号，由短路导致的电力断供影响了数百万人口。城区的运输体统由于电力短缺也受到极大影响。由于与其他基础设施相互依赖，能源系统更易受到攻击。一个最近的互依基础设施级联故障的例子发生于2003年9月28日，意大利，当时一个电站停止工作导致通信网络的节点失效，该节点本是用来控制电力网络的，这样反过来又引发电力网络更大的故障，结果导致一系列灾难性的级联故障。这类双层互依网络类似的说明性例子如图1所示。电力系统网络用著名的IEEE 118节点测试情况说明，它表示了1960年的美国中西部州部分电力系统网络。为了更具说明性，SCADA网络按幂律度分布随机产生，并离散放置在图中。互依连边连接了两个网络中的节点（仅仅部分此类边为了说明情况而表示出来）。通常，多重的互依连接为外出或者进入一个节点，因此，在不同网络中的节点中将可能出现“一到多”或者“多到一”的关系，这在模式Buldyrev（2010）产生了“一到一”的关系。有可能导致级联故障的相应的互依类型将会在随后的部分规范化，关于定义此问题时的说明性例子的计算性实验也将会被呈现。 虽然网络鲁棒性的量化分析可由多种观点得出，但经典且直观的鲁棒性测量标准是最小节点数（绝对或相对地取决于整个网络的规模），即整个网络的功能丧失所需要破坏的节点个数。显然，如果该数相比于整个网络的节点数较小的话，则可得出此网络面对攻击较脆弱的结论，然而如果该数与整个网络的规模相当，则该网络相比于随机或定向中断更具鲁棒性。从优化的观点来看，如果敌人拥有一个网络拓扑结构的完整信息，那么他可以解决确定节点最集的最小基数的优化问题，这些节点是他为了要限制残余网络运行功能所需要破坏的节点。例如，如果要求是以L为阈值限制剩余连接部分，此问题在cardinality-constrained critical node detection problem有论述。在L=1的特殊情况下，此问题变为典型的最小节点覆盖问题，那些“触摸”了网络中所有边的节点集的最小基数，故而在所有最小覆盖节点都被破坏之后就剩下没有边存在的残余网络。 本文中，我们定义并分析了双层互依网络情况下的最小节点覆盖问题，考虑了由两种常见连接类型导致的级联故障的可能性。据我们所知，这是第一份将经典优化问题拓展至互依网络结构的研究。确定出那些如果被删除将严重破坏整个网络的节点的集的最小基数，这无论在攻击还是预防角度都是极为有用的。在以前的构想中，攻击者确定出最应该摧毁的节点集，然而在之后的构想中，保护者有机会去保护这些已确认出的节点集并防止受到可能出现的级联故障传播的干扰。 在分析互依网络鲁棒性方面已经有大量的工作被做，包括一般的和挑战性的，互依网络在节点或边被移除情况下的性能及相对危险率的评估问题，还有分析和仿真的方法研究互依网络的级联故障。总之，大多数之前的研究主要集中于仿真，缺少基于优化的精确方法。本文在此方面探索。 文章结构。本文后续组织结构如下。第二部分概括了将用到的基本定义；第三部分提出了数学分析结构并证明了所考虑问题的相关分析结果；第四部分证明了所有考虑问题的