网络系统可靠性研究现状与展望

网络系统可靠性研究现状与展望 ,国防科技大学信息系统与管理学院, 0 引言------------------------------------------------------------------------------------------------------------------------- 2 1 网络系统可靠性的发展历程、概念及特点------------------------------------------------------------------- 3 1.1 网络系统可靠性的发展历程 ----------------------------------------------------------------------------- 3 1.2 网络系统可靠性的概念及特点 -------------------------------------------------------------------------- 3 2 网络系统可靠性研究现状 ------------------------------------------------------------------------------------------ 4 2.1 网络系统可靠性度量参数 --------------------------------------------------------------------------------- 4 2.1.1 基本可靠性 -------------------------------------------------------------------------------------------- 4 2.1.2 任务可靠性 -------------------------------------------------------------------------------------------- 5 2.2 网络系统可靠性分析 ---------------------------------------------------------------------------------------- 7 2.2.1 解析分析方法----------------------------------------------------------------------------------------- 7 2.2.2 仿真分析方法----------------------------------------------------------------------------------------- 9 2.3 网络系统可靠性优化 -------------------------------------------------------------------------------------- 10 3 结论与展望 ------------------------------------------------------------------------------------------------------------ 11 参考文献 ------------------------------------------------------------------------------------------------------------------- 12 摘要:伴随着人类社会的网络化进程～人类赖以生存的网络系统规模越来越庞大、结构越来 越复杂～这导致网络系统可靠性问题越来越严峻。本文首先探讨了网络系统可靠性的发展历 程、概念与特点～进而从度量参数、建模、分析、优化四个方面系统综述了网络系统可靠性 的研究现状～最后对网络系统可靠性研究未来的发展进行了展望。 关键词: 可靠性,网络系统,综述,现状,展望 Status and Prospects on the Network Reliability WU Jun, DUAN Dongli, ZHAO Juan, DENG Hongzhong, TAN Yuejin (College of Information Systems and Management,National University of Defense Technology) 1 Abstract: Along with the networking progress of human society, the network systems, on which we depend, are larger and larger, more and more complex. It leads to that the reliability problems are more and more serious. This survey firstly discusses the development history, concept and characteristics of network reliability, and then reviews the status of network reliability from the respects of measurement, modeling, analysis and optimization, respectively. Lastly, this survey presents the prospects of network reliability. Key words: reliability; network system; survey; status; prospect 0 引言 21 世纪以来，以信息技术的飞速发展为基础，人类社会加快了网络化进程。交通网络、通 信网络、电力网络、物流网络……可以说，“我们被网络包围着”，几乎所有的复杂系统都可 以抽象成网络模型，这些网络往往有着大量的节点，节点之间有着复杂的连接关系。自从小 世界效应[1]和无标度特性[2]发现以来，复杂网络的研究在过去10 年得到了迅速发展，其研 究者来自图论、统计物理、计算机、管理学、社会学以及生物学等各个不同领域，仅发表在 《Nature》和《Science》上的相关 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 就达百篇。对复杂网络系统结构、功能、动力学行为 的深入探索、科学理解以及可能的应用，已成为多个学科领域共同关注的前沿热点[3-14]。 随着复杂网络研究的兴起，作为复杂网络最重要的研究问题之一，网络系统可靠性研究的重 大理论意义和应用价值也日益凸显出来[15, 16]。人们开始关注:这些复杂的网络系统到底有 多可靠,2003 年8 月美加大停电事故导致美国的8 个州和加拿大的2 个省发生大规模停 电，约5000 万居民受到影响，损失负荷量61800MW，经济损失约300 亿美元;2005 年12 月 台湾海峡地震造成多条国际海底通信光缆发生中断，导致整个亚太地区的互联网服务几近瘫 痪，中国大陆至台湾地区、美国、欧洲等方向国际港澳台通信线路受此影响亦大量中断;2008 年1 月，南方冰雪灾害导致我国十余个省市交通瘫痪、电力中断、供水停止、燃料告急、食 物紧张……这些我们赖以生存的网络系统规模越来越庞大，结构越来越复杂，但越来越频繁 发生的事故也将一系列严峻的问题摆在我们面前:一些微不足道的事故隐患是否会导致整个 网络系统的崩溃,在发生严重自然灾害或者敌对势力蓄意破坏的情况下，这些网络系统是否 2 还能正常发挥作用,这些正是网络系统可靠性研究需要面对的问题。 1 网络系统可靠性的发展历程、概念及特点 1.1 网络系统可靠性的发展历程 可靠性作为专门课题始于二战期间对电子元件可靠性的研究。从20 世纪60 年代开始，可靠性研究从单个电子元件可靠性逐步扩展到一般产品的可靠性(例如电视机、洗衣机、计算机等)以及更为复杂的关联系统可靠性(例如火箭发射系统、核反应控制系统，军事指挥控制系统)，同时还逐步形成了可靠性数学、可靠性物理、可靠性工程等重要研究领域与分支学科[17]。 网络系统作为一类特殊的系统，其可靠性研究最早可追溯到1955 年Lee 对电信交换网络的研究，早期主要集中于通信网络领域。其中，20 世纪70 年代以前主要是以网络的连通作为网络可靠性 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 功能来研究。20 世纪80 年代，由于通信网络规模的迅速扩张，使用频度、网络负载的快速增加以及动态路由技术的采用等原因，网络拥塞和延时逐渐成为了网络可靠性主要考虑的因素。这一时期，网络系统可靠性研究主要集中于通信网络基于性能的可靠性。20 世纪90 年代后，伴随着人类社会网络化进程加快，网络系统可靠性逐渐成为可靠性研究领域的热点，研究对象从通信网络扩展到电力网络、交通网络、物流网络等。 1.2 网络系统可靠性的概念及特点 从系统学的观点来看，网络系统是一类特殊的系统形态，其中网络节点是系统的组成元素，网络的边体现了元素之间相互作用、互相依赖[18]。系统可靠性指系统在规定条件下和规定时间内完成规定功能的能力[19]。网络作为一类特殊的系统形态，其基本可靠性可定义为在规定条件下和规定时间内保持连通的能力，其任务可靠性可定义为在规定条件下和规定时间内完成规定的物质流、信息流、能量流传输任务的能力。 网络系统可靠性相对于一般系统可靠性具有以下特点:1)复杂性。一般系统中组成单元(子系统)之间逻辑关系简单、明确，而网络系统中节点之间的相互关系复杂，不能用简单的串联、并联、混连或者表决系统模型来刻画，系统结构呈网络状。这意味着传统的可靠性框图、故障树分析方法很难适用于网络系统可靠性研究。2)网络流。网络系统的主要任务是在网 3 络节点之间通过网络的边传输物质流、信息流、能量流，网络系统可靠性研究不仅关注网络系统保持连通的基本能力，还关注网络系统完成传输网络流任务的能力，例如基于传输时延的可靠性、基于传输容量的可靠性等等。3)动态性。在一般系统可靠性研究中，研究对象大多是静态的、确定的，系统组成单元的数量、组成单元之间的关联方式基本保持不变。但网络系统，特别是大规模复杂网络系统，例如因特网、交通网等，往往都是动态的、不确定的，网络中节点数量会随着时间不断增减，网络结构也会随着时间不断演化。 4)分布性。在一般系统可靠性研究中，无论是单个元件、产品，还是复杂的关联系统，整个系统在空间上都相对集中。但网络系统往往都具有很强的分布特性，网络节点分散在大范围的空间中，每个节点是一个相对集中的元件、产品或者子系统。这种空间上的分布特性导致了网络系统功能的特殊性，在网络系统中常常出现局域故障或者部分功能缺失的现象。 2 网络系统可靠性研究现状 下面，我们从可靠性度量参数、可靠性分析方法、网络可靠性优化方法综述目前网络系统可靠性研究现状。 2.1 网络系统可靠性度量参数 2.1.1 基本可靠性 1)抗毁性 网络抗毁性(Invulnerability)是基于拓扑结构的可靠性参数，不考虑网络节点和边的可 靠度，衡量的是在网络中的节点或边发生自然失效或遭受故意攻击的条件下，网络拓扑结构 保持连通的能力[20]。目前，网络抗毁性研究主要基于两大理论:图论和统计物理。基于传统图论的网络抗毁性参数。图论是组合数学领域最活跃的分支之一，图的抗毁性是图论的重要研究内容。目前，在图论中有很多图的不变量被用来刻画图的抗毁性。例如，连通度(connectivity)，坚韧度(toughness)[21]，完整度(integrity)[22]，粘连度(tenacity) [23]，离散数(scattering number)[24]，核度(coritivity)[25]，膨胀系数(expansion coefficient)[26]，自然连通度(natural connectivity)[27]。基于传统图论的抗毁性度 4 量参数由于侧重对抗毁性的精确刻画导致绝大多数抗毁性测度指标的计算都是NP 问题。这意味着从计算复杂性角度来看，传统图论的抗毁性研究很难适用大规模复杂网络。 基于统计物理的网络抗毁性参数。近年来网络抗毁性研究的焦点出现了一个重要的新变 迁，即从研究小规模简单网络的精确性质转变为研究大规模复杂网络的统计属性，统计物理 的很多方法开始被广泛应用到复杂网络研究中[28-32]。基于统计物理的抗毁性参数通过观察节 点或边移除过程中网络性能的变化，用网络状态发生相变时的临界节点(边)移除比例来刻 画网络的抗毁性，常用的网络性能指标包括连通片数目、最大连通片规模、网络直径、平均 最短路径长度、网络效率[33]、可达节点对数目[34]等。 2)生存性 网络的生存性(survivability)是指对于节点或链路具有一定失效概率的网络，在随机性 破坏作用下，能够保持网络连通的概率[35]。生存性参数是概率性的，它不仅和网络的拓扑 结构有关，也和网络部件的故障概率、外部故障以及维修策略等有关。常用的度量参数包括 端端可靠度、K 端可靠度和全端可靠度。生存性是基于概率论和图论的知识提出来的，描 述了随机性破坏以及网络拓扑结构对网络可靠性的影响。 2.1.2 任务可靠性 基于连通性能的基本可靠性是网络可靠性的一个基本要求，但网络系统一旦投入使用，就要承载一定的业务负荷，如通信网络的数据业务，输电网络的电传送量，交通网络的运输量与流量等，网络部件发生故障时会引起网络性能下降甚至瘫痪，从而不能完成预定任务，在这种情况下网络实际上是不可靠的。所以，与网络所承载的任务相结合，网络系统任务可靠性作为一个综合反映网络系统可靠性的参数更加具有实际意义。对于承载一定任务的网络系统来说，“召之即来、来之能战、战之能胜”，是决定网络系统发挥其性能的决定性要素，也是检验网络系统在任务执行过程中可靠性水平的准绳。“召之即来”需要网络系统在任意时 5 刻的可用性;“来之能战”反映了网络使用过程中的可信性;“战之能胜”则综合衡量了网络的任务完成性。 1)可用性 网络系统的可用性(Availability)是描述网络在外部资源可用的条件下，在规定时间内的任何时刻，处于能执行所需功能的能力[36]。由于中英文翻译的差异，Availability 也翻译 成有效性。可用性的常用度量指标为可用度，包括瞬时可用度、平均可用度、极限平均可用 度和稳态可用度等。经典的系统可用性参数可以用来衡量网络的可用性，但随着网络用户对 网络的可用性要求越来越高，如何较公正地评估承载不同业务的网络系统的可用性成为迫切 的问题[37]。 2)可信性 网络的可信性(dependability)是指网络已经进入开始执行任务的状态条件下，对在执行任务过程中某个瞬间或多个瞬间的网络状态量度。可信性描述了网络在完成任务期间的状态，即持续完成任务的能力。该指标受可靠性、维修性、安全性和生存性等因素的影响。网络系统的可信性问题是近年来随着人们对网络安全的日益重视开始的，主要包括网络与用户的可信性模型[38]、可信网络的体系结构[39]、服务的可生存性[40]及网络的可控性[41]。目前网络的可信性还没有形成完整的体系，许多概念尚处在摸索阶段，尤其对其基本属性和面临的关键问题上并没有清晰一致的描述[42]。 3)完成性 网络完成性(performability)是指系统在任务开始时可用性一定的情况下，在规定的任 务剖面内，系统正常运行或降级完成服务要求的能力。完成性综合考虑了网络系统的可靠性 和业务能力[43]，指出网络在不同业务性能级别上正常或降级地完成规定业务的能力。完成 性的大小主要由网络部件可靠性水平、网络拓扑结构和网络部件的服务能力、网络流量分布 等因素决定[44]。在实际工程应用中，网络系统具有不同的业务性能水平，并且具有全功能、 降级运行、最低运行等特点，经常使用的参数据此分为全功能运行完成度、降级运行完成度、 6 最低运行完成度等。 2.2 网络系统可靠性分析 网络可靠性分析是网络可靠性研究中的一个重要内容，是指在给定网络部件可靠度的条 件下，研究如何计算各种网络系统的可靠性度量参数。目前，计算网络可靠性度量参数的方 法主要有解析方法和仿真方法两大类。 2.2.1 解析分析方法 1)精确解析方法 利用图论和概率论的方法对网络可靠性进行精确分析和计算，包括状态空间法、容斥原 理法、不交积和法、因子分解法、图变换法、定界法、随机过程法等。 ? 状态空间法 状态空间法是计算网络可靠性最简单的方法，通过枚举出网络正常工作的所有互斥的状 态而计算相应的可靠度。网络系统环境的复杂性和任务的不确定性等因素，使得利用数学模 型和方法来分析求解网络任务可靠性很难，因此，状态空间法就成为了评估网络任务可靠性 的有效方法之一。文献[45]在考虑部件失效、网络容量、用户需求的基础上，利用最小路集 法分析了网络的有效状态空间，进而得到网络的任务可靠性;文献[46]在讨论了电信网不同 状态通过量之间的一般性关系后，得到了一种不需枚举所有网络状态来计算网络可行性精确 值的方法。对于n 个部件的网络，该方法需要遍历网络的所有状态，逐一分析是否可靠，其计算复杂度是O(2n)。显然，通过枚举所有状态来计算大规模网络的可靠度是很困难的，状态空间法只适合于较小网络可靠性的计算。 ? 容斥原理法 容斥原理法是按照组合数学的容斥原理公式求网络的可靠度。一个路集对应着网络的一个工 7 作状态，一个割集对应着网络的一个故障状态，因此该方法将网络可靠度表示为全部最小路集的并(或将网络故障度表示为全部最小割集的并)，然后采用容斥原理去掉相容事件相交的部分，进而计算相应的可靠度。当m 较大时，容斥原理公式的计算是非常繁琐，因此研究者提出了很多改进的方法。Lin 等[47]在容斥原理公式的基础上提出了一个新的拓扑公式，改进了直接使用容斥原理公式求网络可靠度。Satyanarayana 和Prabhakar[48]把网络的拓 扑结构和容斥原理公式结合起来，引入p-无圈子图的概念，证明了两终端可靠度的容斥原 理公式中的不相消项恰好和网络的-无圈子图一一对应，使得网络可靠度的容斥原理算法 p 得到简化。随后，Satyanarayana 等[49, 50]又将上述方法推广到计算网络K-终端和全终端的可靠度。 ? 不交积和法 不交积和法是运用不交积和定理来计算网络可靠度，将网络可靠度表示为全部最小路集的并(或将网络故障度表示为全部最小割集的并)，然后将这个并化为彼此不相交项的和，进而计算相应的可靠度。不交积和法是由Fratta 和Mortamari[51]首先提出来的，随后很多学者做了大量的研究，使不交积和法得到不断的改进[52, 53]。算法的改进主要集中在最小路集(或最小割集)的排序问题上[54]以及如何应用布尔代数知识来巧妙的化简[55-58]，比如故障树分析法、BDD 算法、OBDD[59]算法等等。 ? 因子分解法 因子分解法是按照某种准则把网络分解成2 个子网络，并将子网络递归地分解下去，直到不能分解为止，从而迭代获得网络的可靠度。因子分解法是由Moskowitz[60]和Mine[61]最早提出的， Satyanarayana[62]、Wood[63]、Page[64]等许多学者发展了该方法。最初的因子分解 法都只适用于节点可靠的网络，但实际中，需要考虑顶点不可靠的情况，Theologou 和 J.G.Carlier[65]给出了具有不可靠顶点网络的分解及化简，Elmallah[66]给出了一个求具有不可靠顶点网络的K-终端可靠度的因子分解算法。文献[67]利用网络分解技术和组合原理对具有失效节点和链路的E-2Dmesh 网络的可靠性进行了分析。 ? 随机过程法 8 随机过程法是指在网络部件可修复的情况下，用随机过程来描述网络系统的运行行为，然后利用随机过程的理论来分析网络的可靠性。该方法已经成功应用于串并联系统[68, 69]以及k-out-of-n 网络系统[70]的可靠性分析中。但是由于网络规模较大与结构的复杂性，该方法 有较高的复杂度，且随机过程模型的建立和求解有很大困难。 2)近似解析方法 状态空间法、容斥原理法、不交积和法、因子分解法都属于计算网络可靠度的精确算法，是网络可靠性分析计算的重要理论依据。但由于网络规模的增大、结构的复杂化、部件随机 性的增强等因素，精确算法都具有指数复杂性，是NP-hard 问题[71]，因此研究者对高效率的近似算法进行了大量的研究，主要包括图变换法和定界法。 ? 图变换法 图变换法是一种牺牲精度而降低计算难度的方法，先按照某种规则简化网络，再进行可靠度计算。典型的图变换法有Δ-Y 型简化法、串并联简化法[72]、多边形-链简化法[63]、三角 形简化法[73]等。这些方法在串并联网络中可以完全解决网络的可靠性计算问题，而对一般 的非串并联网络可以起到充分简化的作用。 ? 定界法 定界法是通过组合数学方法研究网络可靠性问题的代数结构，计算出绝对的边界值来近似网络可靠度的精确值。研究者根据不同思路提出了大量的界，比较好的界有Colboum 界[74]、Ball-Provan 界[75]、冯海林基于网络连通子网数与断集数的全端可靠性界评估法[76]等等。 2.2.2 仿真分析方法 网络可靠性受到部件失效、任务流变化、软件故障、人为策略等众多因素的影响，而这些因素和行为一般需要在仿真环境中进行模拟，因此计算机仿真成为了分析网络可靠性的重要方法。 1)蒙特卡罗法 蒙特卡罗法是一种应用随机抽样获得问题解的概率统计方法，通过计算机对网络进行模 9 拟，并获取抽样信息，再对网络可靠度进行估计。不同的抽样方式对网络可靠性的估计精度 有很大的影响，因此，设计有利于方差缩减的抽样方法成为了蒙特卡罗模拟法研究中的一个 重要方向。其中，典型的包括Fishman 提出了重要性抽样法和分层抽样法[77, 78]。 2)神经网络法 神经网络法是将网络拓扑结构和网络部件的可靠度作为神经网络的输入，利用它的自适应机制和学习能力，不断逼近可靠性与网络结构等参数之间复杂的映射关系，进而对网络可靠性作出近似估计。网络可靠性是关于网络结构以及网络部件可靠度的高度非线性映射，而神经网络可以实现输入空间到输出空间的非线性映射，因此，神经网络技术在网络可靠性研究中得到了广泛的应用[79-82]。神经网络法受网络结构复杂度和样本精确度的影响较大，而确定网络结构和精确的样本存在困难，需要大量的训练样本才能保证得到好的结果。 3)Petri 网法 Petri 网法是一种能够描述系统动态行为的一种图形工具，在网络可靠性分析和建模方面有很大的潜力。武小悦教授[83]提出了一种用于分析网络可靠性的面向对象的Petri 网模型 GOOPN，并给出了进行可靠性建模分析的工具。该模型可处理网络的连通可靠性问题，也 能较好的适应网络部件的变化。对于复杂的网络系统，Petri 网的描述能力有限，容易造成“状态组合爆炸”的现象。 2.3 网络系统可靠性优化 网络可靠性优化也称网络可靠性综合[84]或网络可靠性设计[85]，其研究内容大致分为两 个方面:一是在给定的一些限制条件下，研究如何构造一个可靠性尽量高的网络;二是在满 足一定可靠性指标下，研究如何使投资成本最小，以取得最大经济效益。网络可靠性优化方 法主要包括基于图论的优化方法、基于启发式的优化方法、基于人工智能的优化方法。 1)基于图论的优化方法 在点和边数相同的一类图中，寻找一致最优可靠图是基于图论的可靠性优化中最早关注 10 的问题。Boesch 和Li[86]等给出了图类Ω(,-1)，Ω(,)，Ω(,+1)，Ω(,+2)中的一nnnnnnnn致最优可靠图;王桂芳[87]给出了图类Ω(,+3)中的一致最优可靠图;Satyanarayana 等[88]nn 给出了图类Ω(n,e)中的一致最优可靠图。因此，Boesch 猜测一致最优可靠图总是存在的，但是Myrvold[89]构造了反例，否定了Boesch 的猜测。一致最优可靠图不总是存在，促使研究者们分析局部最优图以及τ-优图。Petingi 和Boesch 等[90, 91]给出了确定τ-优图的方法，并且找到了图类Ω(n,n(n-1)/2-e)中的τ-优图;有关局部最优图和τ-优图的更多研究参见文献[92, 93]。 2)基于启发式的优化方法 国内外学者利用启发式算法在网络可靠性优化方面作出了卓有成效的工作。Aggarwal 等[94]在考虑整体可靠性的计算机网络设计中应用了贪心启发式方法;Glover 等[95]提出了一种采用禁忌搜索来进行最小费用网络拓扑设计的方法;Shao 等[96]采用一种收缩搜索算法对以端端可靠度为参数的网络优化问题进行求解;Jan 等[97]以全端可靠度小于某一个门限值为约束条件，以最小化网络连接费用为目标，利用分支定界法研究了骨干网的拓扑优化问题;等等。启发式方法在网络规模不是很大时可以有效的解决费用为目标的拓扑优化问题，但当规模增大时，需要搜索的解空间急剧上升，给求解带来了很大的困难。 3)基于人工智能的优化方法 随着进化计算、智能优化算法的广泛应用和不断发展，使网络可靠性优化研究向前迈进 了一大步，出现了大量的研究与应用方面的文章。例如，Kanyapat 等[98]将neighborhood search和re-initialization process 技术引进到传统蚁群算法，解决综合考虑经济性与可靠性的网络拓扑结构设计问题;郭彤城等[99]将一种粗粒度并行遗传算法应用于求解计算机网络可靠性优化设计问题;孙慧丽等[100]利用满意优化方法综合考虑网络可靠性和网络费用，建立网络拓扑结构设计的数学模型，并描述了用并行遗传算法求解该问题的方法。 3 结论与展望 伴随着人类社会的网络化进程，网络系统可靠性研究必将成为可靠性研究领域的重点和难 11 点，同时，因为其广泛的应用背景，网络系统可靠性研究也必将成为多个学科领域共同关注的焦点和热点。本文介绍了网络系统可靠性研究的发展历程，探讨了网络系统可靠性的概念与特点，从度量参数、建模、分析、优化四个方面综述了网络系统可靠性的研究进展。从前文可以看出，网络系统可靠性研究方兴未艾，虽然取得了大量研究成果，但仍有很多需要进一步研究解决的问题。作为本文的结束语，我们对网络系统可靠性研究的未来发展方向进行展望。 1)结构复杂性是网络系统区别于一般系统的本质属性，网络系统可靠性研究要通过对网络系统结构的宏观与微观属性的定性、定量刻画，探索研究网络系统各种结构属性对可靠性的影响，为网络系统可靠性设计、优化、控制提供理论和方法支持。因此，基于复杂网络理论的网络系统结构可靠性将是一个基础研究方向。 2)动态性也是网络系统区别于一般系统的重要属性，具体包括网络系统随时间的演化动态性以及网络失效行为的级联动态性。目前，关于静态网络系统的可靠性研究相对成熟，但对于动态网络系统可靠性的研究才刚刚起步，这将是未来网络系统可靠性研究需要重点解决的问题。 3)网络系统的规模越来越庞大，节点数量少则数百，多则上百万，计算复杂度问题将成为制约网络系统可靠性研究的一个瓶颈。研究提出高效率、低复杂度的可靠性模型和算法是目前网络系统可靠性研究的当务之急，其中近似算法、仿真算法将是主要解决途径。 参考文献 [1] Watts D J, Strogatz S H. Collective dynamics of 'small-world' networks[J]. Nature, 1998, 393 (6684):440-442 [2] Barab醩i A-L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286 (5439): 509-512 [3] 朱涵, 王欣然, 朱建阳. 网络"建筑学"[J]. 物理, 2003, 32 (6): 364-369 [4] 车宏安, 顾基发. 无标度网络及其系统科学意义[J]. 系统工程理论与实践, 2004, 24 (4): 11-16 [5] 吴金闪, 狄增如. 从统计物理学看复杂网络研究[J]. 物理学进展, 2004, 24 (1): 18-46 12 [6] 郑金连, 狄增如. 复杂网络研究与复杂现象[J]. 系统辩证学报, 2005, 13 (4): 8-13 [7] 陈禹. 人类对于网络的认识的新发展[J]. 系统辩证学报, 2005, 13 (4): 18-22 [8] 汪秉宏, 周涛, 何大韧. 统计物理学与复杂系统研究最新发展趋势分析[J]. 中国基础科学, 2005, 7 (3):37-43 [9] 史定华. 网络--探索复杂性的新途径[J]. 系统工程学报, 2005, 20 (2): 115-119 [10] 刘涛, 陈忠, 陈晓荣. 复杂网络理论及其应用研概述[J]. 系统工程, 2005, 23 (6): 1-7 [11] 姜璐, 刘琼慧. 系统科学与复杂网络研究[J]. 系统辩证学学报, 2005, 13 (4): 14-17 [12] 汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用 [M]. 北京: 清华大学出版社, 2006 [13] 方锦清, 汪小帆, 郑志刚, 等. 一门崭新的交叉科学:网络科学(上)[J]. 物理学进展, 2007, 27 (3):239-343 [14] 方锦清, 汪小帆, 郑志刚, et al. 一门崭新的交叉科学:网络科学(下)[J]. 物理学进展, 2007, 27 (4):361-448 [15] 谭跃进, 吕欣, 吴俊, 等. 复杂网络抗毁性研究若干问题的思考[J]. 系统工程理论与实践, 2008, 28(Suppl): 116-120 [16] 谭跃进, 吴俊, 邓宏钟. 复杂网络抗毁性研究综述[J]. 系统工程, 2006, 24 (11): 1-5 [17] 冯海林. 网络系统中可靠性问题的研究 [D]. 西安: 西安电子科技大学学位论文, 2004 [18] 许国志. 系统科学 [M]. 上海: 上海科技教育出版社, 2000 [19] 郭波, 武小悦等. 系统可靠性分析 [M]. 长沙: 国防科技大学出版社, 2003 [20] 吴俊. 复杂网络拓扑结构抗毁性研究[J]. 国防科学技术大学学位论文, 2008, Discrete Mathematics, 1973, 5 215-228 [21] Chvatal V. Tough graphs and hamiltonian circuits[J]. [22] Barefoot C A, Entringer R, Swart H. Vulnerability in graphs - a comparative survey[J]. J. , 1987, 1 13-22 Combin. Math.Combin. Comput. [23] Cozzens M, Moazzami D, Stueckle S. Seventh International Conference on the Theory and 13 Applications ofGraphs [C] // New York: Wiley, 1995. Journal of Combinatorial [24] Jung H A. Class of Posets and Corresponding Comparability Graphs[J]. , 1978, 24 (2): 125-133 TheorySeries B [25] 许进. 系统核与核度理论及其应用 [M]. 西安: 西安电子科技大学出版社, 1994 [26] Bassalygo L A, Pinsker M S. The complexity of an optimal non-blocking commutation scheme withoutreorganization[J]. Problemy Peredaci Informacii, 1973, 9 (1): 84-87 [27] Wu J, Tan Y-J, Deng H-Z, et al. Spectral Measure of Robustness in Complex Networks[J]. arXiv:0802.2564,2008, [28] Albert R, Jeong H, Barab醩i A-L. Error and attack tolerance of complex networks [J]. Nature, 2000, 406(6794): 378-382 [29] Callaway D S, Newman M E J, Strogatz S H, et al. Network robustness and fragility: percolation on randomgraphs[J]. Phys Rev Lett, 2000, 85 (25): 5468-5471 [30] Wu J, Deng H Z, Tan Y J, et al. Vulnerability of complex networks under intentional attack with incompleteinformation[J]. J. Phys. A, 2007, 40 (11): 2665-2671 [31] Wu J, Deng H-Z, Tan Y-J, et al. A Robustness Model of Complex Networks with Tunable Attack Information Parameter[J]. Chin Phys Lett, 2007, 24 (7): 2138-2141 [32] Wu J, Deng H-Z, Tan Y-J, et al. Attack Vulnerability of Complex Networks Based on Local Information[J].Modern Physics Letters B, 2007, 21 (16): 1007-1014 [33] Latora V, Marchiori M. Efficient behavior of small-world networks[J]. Phys. Rev. Lett., 2001, 87 198701 [34] Siganos G, Tauro S L, Faloutsos M. Jellyfish: A Conceptual Model for the AS Internet Topology[J]. J 14 Commun Net, 2006, 8 (3): 339-350 [35] Benjamin R. Analysis of Connection Survivability in Complex Strategic Communications Networks[J]., 1986, 4 (2): 243-253 IEEE Journal on Selected Areas in Communications [36] Wayne G. High availability path design in ring-based optical networks[J]. IEEE/ACM , 1999, 7 (4): 558-574 Transactions onNetworking [37] Glossbrenner K C. Availability and reliability of switched services[J]. IEEE Communications ,1993, 31 (6): 28-32 Magazine [38] Nicol D M, Sanders W H, Trivedi K S. Model-based evaluation: From dependability to security[J]. IEEETransactions on Dependable and Secure Computing, 2004, 48-65 [39] Paulson L D. Stopping intruders outside the gates[J]. Computer, 2002, 35 (11): 20-22 [40] Atighetchi M, Pal P, Webber F, et al. Adaptive cyberdefense for survival and intrusion tolerance[J]. IEEEInternet Computing, 2004, 25-33 [41] Tong A H Y, Lesage G, Bader G D, et al. Global mapping of the yeast genetic interaction network[J].Science, 2004, 303 (5659): 808-813 [42] 林闯, 汪洋, 李泉林. 网络安全的随机模型方法与评价技术[J]. 计算机学报, 2005, 28 (12): 1943-1956 [43] 潘勇. 通信网可靠性指标研究[J]. 电子产品可靠性与环境试验, 2006, 24 (1): 1-5 [44] 熊蔚明, 刘有恒. 关于通信网可靠性的研究进展[J]. 通信学报, 1990, 11 (4): 43-49 [45] Lin Y K. Reliability of a computer network in case capacity weight varying with arcs, nodes and types of commodity[J]. Reliability Engineering & System Safety, 2007, 92 (5): 646-652 [46] 熊庆旭，刘有恒. 基于网络状态之间关系的网络的可靠性分析[J]. 通信学报, 1998, 19 (3): 55-61 [47] Lin P M, Leon B J, Huang T C. A new algorithm for symbolic system reliability analysis[J]. IEEE 15 Transactions on Reliability, 1976, 25 2-15 [48] Satyanarayana A, Prabhakar A. New topological formula and rapid algorithm for reliability analysis of complex networks[J]. IEEE Transactions on Reliability, 1978, 27 82-100 [49] Satyanarayana A. Unified Formula for Analysis of Some Network Reliability Problems[J]. IEEE Transactions on Reliability, 1982, 31 (1): 23-32 [50] Satyanarayana A, Hagstrom J N. New Algorithm for the Reliability Analysis of Multi-Terminal Networks[J].IEEE Transactions on Reliability, 1981, 30 (4): 325-334 [51] Fratta L, Montanari U. A Boolean algebra method for computing the terminal reliability in a communication network[J]. IEEE Transactions on Circuit Theory, 1973, 20 (3): 203-211 IEEE Transactions Circuit [52] Abraham J A. An improved algorithm for network reliability[J]. ,1979, 28 (1): 58-61 Reliability [53] Beichelt F, Spross L. An improved Abraham-method for generating disjoint sums[J]. IEEE , 1987, 36 (1): 70-74 Transactions on Reliability [54] Rai S, Veeraraghavan M, Trivedi K S. A survey of efficient reliability computation using disjoint products approach[J]. Networks, 2006, 25 (3): 147-163 [55] Heidtmann K D. Smaller sums of disjoint products by subproduct inversion[J]. IEEE , 1989, 38 (3): 305-311 Transactions on Reliability [56] Locks M O, Wilson J M. Note on disjoint products algorithms[J]. IEEE Transactions on Reliability, 1992, 41(1): 81-84 [57] Luo T, Trivedi K S. An improved algorithm for coherent-system reliability[J]. IEEE , 1998, 47 (1): 73-78 Transactions on Reliability [58] Veeraraghavan M, Trivedi K S. An improved algorithm for symbolic reliability analysis[J]. 16 IEEE Transactions on Reliability, 1991, 40 (3): 347-358 [59] Kuo S Y, Lu S K, Yeh F M. Determining terminal-pair reliability based on edge expansiondiagrams using OBDD[J]. , 1999, 48 (3): 234-246 IEEE Transactions on Reliability [60] Moskowitz F. The analysis of redundancy networks[J]. AIEE Trans. Commun. Electron, 1958, 39 627-632 [61] Mine H. Reliability of physical system[J]. , 1959, 5 IRE Transactions on Information Theory (5): 138-151 [62] Satyanarayana A, Chang M K. Network reliability and the factoring theorem[J]. Networks, 2006, 13 (1):107-120 [63] Wood R K. A factoring algorithm using polygon-to-chain reductions for computing K-terminal network reliability[J]. Networks, 1985, 15 173-190 [64] Page L B, Perry J E. Combining vertex decompositions with factoring in an all-terminal network reliability algorithm[J]. Microelectronics and Reliability, 1990, 30 (2): 249-263 [65] Theologou O R, Carlier J G. Factoring and reductions for networks with imperfect vertices[J]. IEEE Transactions on Reliability, 1991, 40 (2): 210-217 [66] Elmallah E S. Algorithms for K-terminal reliability problems with node failures[J]. Networks, 1991, 22 (4):369 - 384 [67] 肖杰，黄亿海，梁家荣. 具有失效节点和链路的E-2DMesh 网络可靠性研究[J]. 计算机应用研究, 2009,26 (3): 1036-1038 [68] Finkelstein M S. Multiple availability on stochastic demand[J]. IEEE Transactions on , 1999, 48(1): 19-24 Reliability [69] 冯海林，刘三阳，宋月. 网络系统可靠性分析的马尔可夫过程法[J]. 系统工程与电子技术, 2004, 26 17 (11):1669-1671 International [70] Zhang Y L, Lam Y. Reliability of consecutive-k-out-of-n: G repairable system[J]. , 1998, 29 (12): 1375-1379 Journal of Systems Science [71] Ball M O. Complexity of network reliability computations[J]. Networks, 2006, 10 (2): 153-165 [72] Rosenthal A. Series-parallel reduction for difficult measures of network reliability[J]. , 2006, 11 (4):323-334 Networks [73] Hsu S J, Yuang M. IEEE International conference on communications [C] // 1998. [74] Brecht T B, Colbourn C J. Lower bounds on two-terminal network reliability[J]. Discrete Applied , 1988, 21 (3): 185-198 Mathematics [75] Ball M O, Provan J S. Calculating bounds on reachability and connectedness in stochastic networks[J].Networks, 2006, 13 (2): 253-278 [76] 冯海林 刘, 宋月. 通信网全端可靠性界的一种计算方法[J]. 电子学报, 2004, 32 (11): 1868-1870 [77] Fishman G S. A comparison of four Monte Carlo methods for estimating the probability of s-t connectedness[J]. IEEE Transactions on Reliability, 1986, 35 (2): 145-155 [78] Fishman G S. Estimating the st reliability function using importance and stratified sampling[J]. Operations Research, 1989, 37 (3): 462-473 [79] Srivaree-ratana C, Konak A, Smith A E. Estimation of all-terminal network reliability using an artificial neural network[J]. Computers & Operations Research, 2002, 29 (7): 849-868 [80] Cheng C S, Hsu Y T, Wu C C. An improved neural network realization for reliability analysis[J]. Microelectronics Reliability, 1998, 38 (3): 345-352 [81] Manzoul M A, Suliman M. Neural network for the reliability analysis of simplex systems[J]. 18 Microelectronics Reliability, 1990, 30 (4): 795-800 [82] 王芳, 侯朝桢. 一种用神经网络估计网络可靠性的方法[J]. 北京理工大学学报, 2003, 23 (2): 190-193 [83] 武小悦，张维明，沙基昌. 网络可靠性分析的GOOPN 模型[J]. 系统工程与电子技术, 2000, 22 (3): 84-93 [84] Boesch F T, Thomas R E. On graphs of invulnerable communication nets[J]. IEEE Transcation , 1970, CT-17 (2): 183-192 on Circuit Theory [85] 李晓明. 网络可靠性综合的现状及其展望[J]. 计算机学报, 1990, 13 (9): 699-705 [86] Boesch F T, Li X, Suffel C. On the existence of uniformly optimally reliable networks[J]. Networks, 2006,21 (2): 181-194 [87] Wang G. A proof of Boesch's conjecture[J]. Networks, 2006, 24 (5): 277-284 [88] Satyanarayana A, Schoppmann L, Suffel C L. A reliability-improving graph transformation with applications to network reliability[J]. Networks, 2006, 22 (2): 209-216 [89] Myrvold W, Cheung K H, Page L B, et al. Uniformly-most reliable networks do not always exist[J].Networks, 2006, 21 (4): 417-419 [90] Petingi L, Rodriguez J. A new technique for the characterization of graphs with a maximum number of spanning trees[J]. Discrete Mathematics, 2002, 244 (1): 351-374 [91] Petingi L, Boesch F, Suffel C. On the characterization of graphs with maximum number of spanning trees[J].Discrete Mathematics, 1998, 179 (1): 155-166 [92] Gilbert B, Myrvold W. Maximizing spanning trees in almost complete graphs[J]. Networks, 1998, 30 (2):97-104 [93] Gross D, Saccoman J T. Uniformly optimally reliable graphs[J]. Networks, 1998, 31 (4): 19 217-225 [94] Aggarwal K K, Chopra Y C, Bajwa J S. Topological layout of links for optimizing the s-t Microelectronics and Reliability, 1982, 22 (3): reliability in a computer communication system[J]. 347-351 [95] Glover F, Lee M, Ryan J. Least-cost network topology design for a new service[J]. Annals , 1991, 33 (5): 351-362 of Operations Research [96] Shao F M, Shen X, Ho P H. Reliability optimization of distributed access networks with constrained total cost[J]. , 2005, 54 (3): 421-430 IEEE Transactions on Reliability [97] Jan R H. Design of reliable networks[J]. Computers & Operations Research, 1993, 20 (1): 25-34 [98] Kanyapat W, Paramote W. Reliability optimization of topology communication network design using animproved ant colony optimization[J]. Computers and Electrical Engineering, 2009, 35 (5): 730-747 [99] 郭彤城. 并行遗传算法在一类计算机网络可靠性优化问题中的应用[J]. 系统工程理论与实践, 2003, 23(1): 31-36 [100]孙慧丽，谭献海，温碧丽. 基于可靠性约束的网络多目标满意优化[J]. 微电子学与计算机, 2007, 24 (8):118-12 20