（计算机应用技术专业论文）基于分解定理的网络k终端可靠性分析算法研究.pdf

摘要 y3 9 8 1 6 2 f f 网络端到端可靠性计算是网络可靠性分析、评估和可靠网络设计的基 础，无论对于点不可靠、边不可靠和混合模型的网络其计算都为n p - h a r d 问 题，特别对于现代网络( 尤其是数据通信网，例如i i l t e m e t ) 的规模不断扩大， 快速精确计算大规模网络的端到端可靠性是摆在我们目前的现实难题。y 。 本文首先讨论了计算网络可靠性评测指标和研究现状，描述了计算任意 k 结点( 典型为2 - t e r m i n a l ) l 盲q 存在至少一条可靠通路进行通信的概率以及判 定给定网络的容错度的一个最常用的有效算法一分解定理。针对通信链路 可能失效、通信节点都为无故障的边随机模型我们设计了一个分析可靠性计 算算法，算法采用了递归应用分解定理为基础，在递归内部应用简化手段来 使导出图尽可能简单，并用软件实现该算法分析网络的可靠度。 针对现实塑笙垫姿更精确的通信节点和逗信整监都可能卷垫温金圆络 模型，在边随机无向网络k 一终端可靠度算法的基础上，我们描述了混合随 机无向网络k 一终端可靠度算法的悬挂边简化等简化手段，使之能适用于混 合随机无向网终。提出了混合随机无向网络的“多边形一链”简化，并证明了 它的正确性。性混合随机无向网络l o 一终端可靠度算法中，我们对链节应用 分解定理，并说明了应用分解定理所得到的两个导出图仍保持点、边失效概 率统计独立的方法。算法分析表明混合模型下的可靠性计算算法时间复杂度 和边不可靠模型的可靠性分析算法是相同的。 新的应用对网络q o s 提出了要求，基于q o s 的网络可靠性计算是可靠性 研究领域的新问题，进一步的研究正在进行中。b 一一、一 1 a b s t r a c t t h en e t w o r ke n d t o e n dr e l i a b i l i t yc o m p u t a t i o ni st h ef o u n d a t i o no ft h e n e t w o r kr e l l a b i l i t ya n a l y s is e v a l u a t i o na n dr e l i a b l en e t w o r kd e s i g n i tis an p h a r dp r o b l e mt oc o m p u t a t i o nt h er e l l a b i l i t yo fan e t w o r kw i t hu n r e l i a b l e c o m m u n i c a t i o n1 i n k so ru n r e l l a b l ec o m m u n i o a t i o nn o d e so rb o t h w h a t sm o r e 。 w l t ht h eu n c e a s i n g l ye x p a n s i o no ft h es c a l eo fm o d e r nn e t w o r k ( i np a r t i c u l a r d a t ac o m m u n i c a t i o nn e t w o r k ，f o re x a m p l et h e i n t e r n e t ) ，m o r ef a s ta n dp r e o i s e i ：；l ic u a t i o no ft h el a r g es c a l en e t w o r ke n d t o e n d r e l i a b i l i t yb e c o m e s a s u s p e n d i n gp r a c t i c a ld i f f i c u l tt a s k 。f h isa r t i c l ef i r s t l yd i s c u s s e st h ee v a l u a t i o nm e t r i c sa n dp r e s e n tr e s e a r c h s 【t u a t i o no ft h en e 伽o r ke n d t o e n dr e i i a b i l i t yc o m p u t a t i o n t h ef a c t o r i n g f h e o r e m 一一am o s tc b m m o n l yu s e de f f e c t i v ea l g o r i t h mi sd e s c r i b e dw h i c hp o i n t s o u t h a tt h e r ee x i s t sa tl e a s to n er e l i a b l ep a t hb e t w e e ng i v e nkt e r m i n a l s ( 1y p i c a l l y2 一t e r m i n a l ) t oc a r r yo f ft h ec o r r e s p o n d e n c ep o s s i b i l i t ya sw e l la s t h ed e t e r m i n a t i o no ft h ef a u l t - t o l e r a n c eo fg i v e nn e t w o r k a na l g o r i t h mh a s b e e nd e s i g n e df o ra n a l y s i sn e t w o r kr e l i a b i l i t yi nv i e wo ft h ec o m m u n i c a t i o n l i n k ss t o c h a s t i cm o d e lw i t hr e l i a b l ec o m m u n i c a t i o nn o d e sa n du n r e l i a b l el i n k s r h ea l g o r i t h ma d o p t sr e c u r s i v ef a c t o r i n gt h e o r e m ap r o g r a mh a sb e e nd e s i g n e d t oc o m p u t et h er e l i a b i l i t yo fn e t w o r ki nt h em l g o r i t h m b a s e do nt h er e l i a b i l i t ya n a l y s i sa l g o r i t h mo ft h ek - t e r m i n a lo f l i n k s s t o c h a s t i cn e t w o r k ，w ea l s od e s c r i b es o m es i m p l i f i c a t i o nw a y sf o re x a m p l et h e h a r l g i n gl i n k ss i m p l i f i c a t i o no ft h er e l i a b i l i t ya n a l y s i sa l g o r i t h mf o rt h e kt e r m i n a lo fm i xs t o c h a s t i cn o n d i r e c t i o nn e t w o r kw it hu n r e l l a b l el i n k sa n d n o d e s ，a n dm a k ei tf i tt h em i xs t o c h a s t i cn o n d i r e c t i o nn e t w o r k w ep r o p o s e t h e “p o l y g o n 一 c h a i n ”s i m p l i f i c a t i o no ft h em i xs t o c h a s t i cn o n d i r e c t i o n 1 1 ”t w o r k a n dp r o v ei t sa c c u r a c y i nt h er e l l a b i l i t ya l g o r i t h mo ft h ek - t e r m i n a l n 1 - m i xs t o c h a s t i cn o n d i r e c t i o nn e t w o r k ，w eu s et h ef a c t o r i n gt h e o r e mt od e a i 、it ht h ec h a i nk n o t i na d d i t i o n ，w ee x p l a i nt h a tt h e t w oc h a r t e r sg o t t e nb v t m ) p t i n gt h ea p p l i c a t i o nf a c t o r i n gt h e o r e ms t i l l k e e pt h ec o u n t i n go ft h e e x p i r a t i o np r o b a b i l i t yo ft h e i rd o t sa n ds i d e s i n d e p e n d e n t l y ，a l g o r i t h m a n a l y s i si n d i c a t e st h a tt h et i m ec o m p l e x i t yo ft h i sa l g o r i t h mi se q u a lt ot h a t o l t h er e l i a b i l i t ya l g o r i t h mo ft h e1 i n ku n r e l i a b l em o d e l 1 h em o r ea p p l l c a t l o n p r o p o s e sr e q u e s t st on e t w o r kq o s b e c a u s et h en e t w o r k r e i i a b i l i t yc o m p u t a t i o no fq o si san e wp r o b l e mi nt h ef i e l do fr e l i a b i l i t v r e s e a r c h ，f u r t h e rr e s e a r c hi sb e i n gc a r r l e do n 1 1 引言 第一章绪论 网络可靠陛问题一直倍受人们关注，网络可靠、安全、高效运行是许多应用完成 的基础，网络可靠 生分析、网络故障检测和管理近来成为人们研究的热点。这主要有 两个原因造成的：其一，许多业务的完成必须依赖网络进行，网络成为必不可缺的基 础设施；其二，随着网络规模的不断扩大和异构程度的提高，网络日益复杂，网络性 能下降、故障不断出现，传统网络可靠性研究方法受到很大的挑战。 网络可靠性的问题涉及网络设各、协议可靠性，网络规划设计的可靠性问题，网 络与系统管理技术等多方面的问题，目前研究主要有四个方面：1 ) 容错网络设备设 计：2 ) 健壮的网络协议设计与实现：3 ) 可靠网络规划与仿真模拟；4 ) 网络维护 与网络技术。网络的规划设计是保证网络可靠性的重要环节，网络仿真越来越成为大 中型网络规划和升级有效的分析方法( 例如俄克拉荷马州银行使用i td e c i s i o n g u r u 设 计其网络干线和2 0 0 0l a n 节点的拓扑，t x u 公司依靠i td e c i s i o n g u r u 预先的i t 设计和快速的故障检修) 。随着国内对网络仿真认识的加深和网络的复杂化、构建网络 的规范化，网络仿真分析必然成为网络构建、升级和日常胜能分析的必要手段。网络 仿真需要解决的一个主要问题就是分析计算给定拓扑结构的网络端到端可靠通信盯概 率。众所周知，k 终端网络可靠性问题是一个n p h a r d 问题随着网络规模的扩大， 采用一般的方法计算系统可靠性是不可能的，因此设计高效的k - 终端可靠陛计算算法 是进行高可靠网络设计的基础。 8 0 年代以来，人们提出了大量的k 终端可靠陛分忻算法，这些算法主要分为两类： 精确性分折算法和概率分析算法。概率分沂方法一般比精确性分析方法更适合于大型 的网络系统，但是对分析结果的正确性评估一直是一个非常复杂的问题。一些算法对 特定的网终拓扑结构能取得满意的结果，但是不适于任惹网络拓扑结构。在这些算法 中，分解定理一直是人们常用的一种重要分析手段。分解定理的关键是简化网络的拓 扑终陶降低网络的规模。但是在具体的网络可靠性分析算法中，分解定理以前较少 采用我们认为主要有三方面的原因造成的：1 ) 分解定莲简化顺序具有较大的随意性， 对任意的网络拓扑图不适用：2 ) 作为优化策略算法一直缺乏有效的算法复杂性分折方 法：3 ) 作为一种递归方法，需要大量的计算内存，特别对于大型的网络，随着计算技 术的发展，以上的缺陷正在削减，特别是计算内存问题；分解定理目前是精确分忻网 络可靠陛的唯一方法，因此设计基于分解定理的高效的网络可靠陛分析算法是仿真殴 汁高可靠网络的关键。 1 。2 图论基础与网络模型 图论是应用极为广泛的一门学科。在通讯网络、运输网络、线! 生规划及运筹 学中的应用中更为引人注目。涉及通讯网络的问题主要是系统可靠性和连通性，在研 究这类问题时，需要用到图论的知识。 一个图g = e ) 由两个特定集合组成：v 是点集，e 是边集，每条边e e 和两个 点关联。也就是说e = ( u ，v ) ，这里t 1 ) v v ，点u 和v 被称为e 的端点。如果两条或多条 边与同一对端点蓑联，则这些边称为平行边。我们称边e = ( u ，u ) 为自环。在图g 中允许 自环和平行边存在。 如果在图g 中存在一条边e _ ( u ，v ) ，那么点u 和v 被说成相邻，边e 与u 和v 关联。 与点v 关联的边数被称为点v 的度数用d e g ( v ) 表示。如果存在一种点边序列形式为： u ，沁”1 ) ，7 l ，“，0 2 ) ( v 1 i ，v i ) ，v i ，( ”i ，v j ，这样的序列称为链。如果链中无重复点， 我们称它为初等链；如果它的首尾点相同，这条链就为圈；如果仅有首尾点相同，那 么它为初等圈。如果在点集k e v 中所有的点对之间都存在链，那么点集k 被连通如 果点集v 连通，那么称g 是连通图，一个树是无圈连通图。 如果v v 和e e ，那么图g = ( 矿，e ) 为g = e ) 的子图。g v 表示从g 中 删除点v 所得到的子图，即g - v = ( v - v , e - e o ) ，其中e 。： p ei v 是p 的一个顶点 。如 果g 是连通图，但g - v 不连通，那么v 是o 的割点，一个不可分图式二连通图不含割 点，一个图的块( b l o c k ) ，是最大不可分子图。 从图中删除一条边也能使图分离，g - e 表示从g 中删除一条边e 所获得的子图， 即g - e = ( v e - e ) ，如果g e 不连通，那么e 是图g 中的桥。 v 2 对于各种网络，在具体找出其可靠度算法 之前，均可采用一个图来代表该网络，这个图就 是网络模型 3 4 。在图的每条边上赋权，称之为 概率图。例如用一个概率图g = ( v ，e ) 表示一个计 算机通讯网络。v 表示n 个点的集合e 表示m 条边的集合，( 有向或无向) ：点表示网络各个中 心站，边表示单向或双向的通讯线路。p i 表示边 的可靠度。当图g 中含有有同( 或仅含无向) 边时， 称为有向( 或无向) 图。对于网络模型，假设其各个分支的概率是相互独立的，整个网 络的各个分支只有两种状态：好与坏。 在网络中节点和边都会发生故障，在成本许可的情况下，精心的设计和设备的备 份可以在很大程度上消除节点的故障，而边的故障是偶然发生的。网络可靠度的计算 应：陌节专故障和边的故障区别开来，节点故障的情形可转化为边的故障情形来处理。 因而我虻可不考虑节点故障，只考虑边出现故障的情况下，网络可靠度的计算。 本文中我们使用的网络模型为：认为通信网具有双向通信能力的通信线路，它们连 接着具有收发能力的通信站。通信网中的通信线路和通信站都有可能失效。如果通信 线路能有效工作，那么它能传递两个方向的通信信息；如果线路失效那么任何一个方向 的信息都不能通过。如果通信站能有效工作那么它既能接收信息也能发送信息和转接 信息：如果通信站失效，那么它既不能接收信息和发送信息也不能转接信息。如果某些 特定的通洁站之间可以通信，那么我们认为网络能有效工作。 1 3 本文所做的工作 本文从网络拓扑结构入手分析研究网络的可靠性问题，文章以下章节安排如下： 在第二章给出可靠性定义，详细探讨了网络可靠性测度和测度的的指标，描述了当前 主要研究的网络可靠性的算法。第三章讨论在点可靠的网络模型下的分解定理和现有 的几种简化网络可靠度计算的可靠度计算简化的算法。论文第四章在第三章的基础上 提出利用可靠度计算简化技术及割点剖分计算网络可靠度的方法，并详细设计和实现 了对于边随机无向网络k 一终端可靠性的计算分析算法，并将其与已有的f a c t o r s r e d u c e 算法进行了比较。实验结果表明此算法优于f a c t o r s & r e d u c e 算法。论文第五 章介绍了混和随机无向网络概念，给出了具有不可靠点网络的分解定理并修正了可靠 度计算简化的算法，在此基础上给出了有不可靠点网络的“多边形一链”化简的方法， 并提出了一个计算混和随机无向网络的k 一终端网络可靠度算法。文章的第六章总结 全文，提出需要进一步研究的问题。 3 第二章网络可靠性测度及其算法 随着社会的不断进步，各种各样的产品、设备变得越来越与人们的生活密不可 分，其结构的复杂程度越高。我们知道，系统的复杂程度越高，所含的部件数越多， 如不采取相应的措施，系统工作的可靠性就可能大大降低，因为只要某个或某些部件 发生故障，就可能损害系统的整体功能的实现。为此，人们对可靠陛问题开始了研究。 通信网可靠| 生问题是一个复杂的系统工程问题 2 7 。可靠性理论的迅速发展是在二战 以后，并在军工、能源等许多领域得到了广泛的应用。随着科学技术的进步，通信瞬 也渗透到社会的方方面面，通信网的可靠陛问题也越来越为人们所关注。 2 1 可靠性的定义 可靠性是指在一定运行环境下系统在特定时间内适当实现它的功能的概率f 3 4 。 对于通信网的可靠性，一个被广泛接受的定义就是：“在特定的条件和时间内，网 络部件存在失效时网络依然能够完成预定功能的能力 ：6 】。”从通信网的功能和特点出 发。这里的“能力”可以从以下几个角度来解释： 1 、通信网中的部件( 设备和线路) 能够正常工作； 2 、网络中的全部或部分结点之间能够相互通信； 3 、 通信网保持一定的通信能力( 如吞吐量、信道数等) ： 4 、通信网满足一定的通信质量要求( 如呼损、时延等) 。 上述3 、4 往往是相互联系的。 通涪网可靠性的特点： ( 1 ) 用户对通信的需求是随机的，在时间和空间上的分布是不均匀的，同时，通 信网中各种破坏| 生作用的发生也是随机的，“这就决定了通信网可靠性的动态陛”。 ( 2 ) 由于通信网是由许多设备组成的不可分割的一个整体因此，即使发生部分 故障也会波及到很大范围，“这是通信网可靠陛的系统性”。 ( 3 ) 通信网的物理结构不同于逻辑结陶，且网络中存在许多共享资源( 如电源系 统等) ，因此通信网中大量存在失效相关的情况“另外，各种网络设备所处的环境条件 不尽相同，有的条件差别很大”这就决定了通信网可靠胜的复杂陛。 通常认为，通信网的可靠陛与下列因素有关 4 0 1 ： ( d 构成网络部件( 节点) 的可靠性： 网络的拓朴结构： 网络采用的路由选择算法；网络的管理控制系统等。 2 2 通信网可靠性的测度及测度指标 确定可靠性测定指标是分析和评估可靠陛的前提 2 5 1 ，其旨在建立一整套科学的 评价体系，以便量化人们对网络可靠洼的要求。从而正确评价网络可靠陛、明确可靠 性恬动中的方方面面，确认提高可靠性的经济性能。【2 2 1 1 2 3 2 7 】 2 2 1 通信网可靠性评价 首先，通信网的基本功能是向网络用户提供通信服务，没有用户就没有通信，而 没有通信也就无从谈起可靠性，这就决定了用户在可靠陛研究中的核心地位，所以可 靠性的研究应面向用户。尽管数据通信网运营部门和用户都关心可靠性问题，然而目 的有所不同，运营者期望的是好的经济效益，用户则是希望获得量的服务，但从经济 效益的获取来看，只有尽量满足用户需求，才可能获得市场占有率，创造好的经济效 蘸。所以不管运营者还是用户，关心的是用户得到很好的服务的问题。需要得到较好 服务的用户，可能是两个用户间，也可能是多个用户间的服务。据此不同，通常将可 靠性问题分为： ( 1 ) 全端问题：有关网络中所有用户闻的通信功能； ( 2 ) k 端问题：有源问题：有关k 个用户中的一个( 源s ) 与其它k - 1 个用户 间的通信功能；无源问题：有关k 个用户之间的通信功能： ( 3 ) 两端问题：有关源用户s 和目的用户t 之间的通信功能： 其次，用户间要传送信息，最起码需要可用的物理路径，所以人们最初以网络存 在物理路径的能力作为可靠性的研究内容，这就是网络连通睦的研究里称之为连通可 靠性。网络一旦建成，即使还没有运营，连通可靠性即以确定，所以此为网络固有可 靠陛，通常如同一般产品，网络连通可靠陛的研究通常以可靠度、不可靠度、失效( 故 障) 率、m t t r 、婀b f 以及可用度指标进行。 由于信息的传送还与路径上的容量有关，所以有以在路径存在一定的能力作为可 靠胜的研究内容! 1 ，这是网络连通性和容量综合的研究。 第三，用户间传送信息时，即便存在物理路径，在路径上也存在一定量，然而如 累是容量不可用，即容量并不空闲，用户也不能彼此传送信息，。存在物理路径及路径 容量仅是网络完成功能目必要条件网络要顺利完成任还需在可用物理路径上存在空 闪容量，如果有时延限制，则还有路径不能过冬顺利完成功能的能力，更能表征网络 可靠l 生。一般网络能顺利完成功能表明的业务陛能较好，所以这 研究是与业务性能 有关的可靠| 生研究。 从这可以看到可靠陛的研究也是遵循一股的原则，即由简到繁。而研究内容越 复杂，其实用性越强。 2 2 2 通信网可靠性测度指标 为建立一套完整、科学的通信网可靠陛评价体系，建立可靠性测度及其体系是必 要的。通信网可靠睦的测度指标，i 其研究历史看f 十类繁多，体现在可靠陛研究中的 着眼点和侧重面不同 2 6 。从研究问题入手的角度来看，通信网可靠陛的测度试可分 为两类：图论意义上的连通性研究和以网络的某种性能指标为基础的可用度 ( a v a i l a b i l i t y ) 研究。 2 1 】 1 与连通性有关的可靠性( c o r m e c t i v i t y - r e l a t e dr e l i a b i l i t y ) 测度： 此可靠性测度又可分为确定性测度( d e t e r m i n i s t i cm e a s u r e s ) 和概率性测度 ( p r o b a b i l i s t i cm e a s u r e s ) ： 2 确定性测度：指网络遭到破坏变成两个或以上不相连的子网的难易程度仅与网 络的拓扑结构有关，即与节点、链路的数目及其连接方式有关，这是所说的网络脆弱 性或抗毁性( i n v u l n e r a b i l i t y ) 。其测度指标有： 连通度( c o n n e c t i v i t y ) 和聚合度( c o h e s i o n ) ，这是基于网络分割的指标： 所谓网络的连通度( c o n n e c t i v i t y ) 是对网络的节点而言的，它是指使网络成为不 连通所需去掉的网络的最少节点数，它等于网络的最小割端所含的端数。所谓聚合度 ( c o h e s i o n ) 是指使网络变为不连通所需去掉的网络的某些边的最小值，它等于网络 最小割边集所含的边数。 概率性测度：概率性可靠陛是指某种结构的网络，处在外在的失效“应力”作 用下，使得网络的部件以某种概率失效时网络反映出的可靠性，它不仅与网络的结构 有关，也与网络的部件( 节点、链路) 的失效概率有关，所谓失效应力是指网络部件 的自身的可靠性因素( 如设备的老化等) ，以及环境因素( 如自然灾害，人力破坏等) 的影响，使网络部件( 节点、链路) 可能产生失效。指网络部件谴机失效下网络的连 通概率，根据时间性的不同而分为： ( a ) 生存性( s u r b v i v a b i l i t y ) ：讨论是网络在规定的时间内一直连通的问题， 其指标为可靠度，表明网络在规定的时间内一直正常工作的概率，目前大多研究的是 部件不可修复隋况下的可靠度对于部件可修复下的可靠度研究很少，而且通常需采 硐计算机模拟的方法分析。生存性现在又常常称作网络的概率眭可靠| 生网络的 ( s u r v i v a b i l i t y ) ，主要的可靠| 生测试指标有： k 端可靠陛：任意k 个节点对间存在至少一条路程的概率，最常见的是双端可靠 性， 全端可靠- 陛：网络所有节点间相连接的概率 ( b ) 可用性( a v a i l i l i t y ) ：讨论的是网络在规定时间内的某时刻或任意时刻连 j j ! l i 弛问题由于在部件不可修复的隋况下网络在规定时间内的某时刻正常工作的概率 也就是规定时间的初始时刻至此时刻之间的时间内正常 ：作的概率，所以可_ e 性通常 是讨论部件可修复清况，有瞬时可用度和稳态可用度另外还有由稳态可月= 度密切相 关的时间量指际：平均无故障工作时间( t b f ) 和平均修复时间( m t t r ) ， 2 与业务性能有关的可靠性( p e r f o r m a n c e r e l a t e dr e l i a b l i l i t y ) 测度： 数据通信网业务| 生能指标通常有吞吐量( t h o u g h p u t ) 、服务质量( q o s ) 等。把表 址与炷能相关的可靠陛测度，定义为网络的完成性，其指标有： 网络发生失效生网络的某种业务性能，如吞吐量( t h r o u g h p u t ) 、呼损、时延 的l 们望直： 6 有效度( e f f e c t i v e n e s s ) ：网络在部件失效情况下某种眭能指标的期望值： 完成度( t i e r f o r m a b l l i t y ) ：网络的边的失效序列为网络的一个可靠性状态。 每个可靠性状态又对应某个网络性能测度( 如吞吐量、呼损、时延等) 的取值。若我 们规定一个闽值，当相应网络可靠睦：映态对应的性能优于规定的闯值时则计此网络 可靠陛状态为有效态：于是网络的完成度可定义为所有有效态出现的概率之和。 另外，对于动态自组织网或考虑网络是可修复的，又有网络的综合可用度 ( a v a i l a b i l i t y ) 。它的定义与完成性类似，只是考虑网络的有效状态时加入了网络的 自组织或修复过程的影响。 为一目了然，将可靠性测度及其指标绘成如下图： 图2 1 通信网可靠眭测度及其指标 f 面我们对上面讲到的确定可靠陛及概奎可靠陛进行进一步的讨论。 网络在图论意义上是连通是通信网能够进行通信刍勺首要前提。所谓连通，即汪一 7 青点对间至少存在一条路径。网络的聚合度和连通度反映的是网络最小连接性能的好 坏。聚合度和连通度越高，则使网络变为不连通所需破坏的边就越多，网络的总体连 接性能就越好。显然，对于网络的拓扑结构而言，连接性能最好的网是全连通网。而 连接性能最差的网所有节点间只存在一条径的树形网，因为只需破坏一条边网络就会 变得不连通。而多数网络考虑到性能、费用及可靠性三者的折衷，其连通性通常是介 于此二者之间的。对于确定性连通性测试，即网络的抗毁性测试，它给出的是网络平 均意义上的连通性好坏，无法刻划出网络的连通结构的潜在缺陷。而对于网络连通性 的概率性测试，即网络的生存性测试，其分析的基础就是必须给定链路或节点的生存 概率，以此为起点，通过相应的分析过程得到网络的某节点对或所有节点对间连通的 概率。 2 3 可靠性的算法 为了得到系统的可靠性，系统用一个可靠性概率图g ( v ，e ) ( 无向图，或有向图) 来表示，我们通常假定图g ( v ，e ) 中节点和边只有工作和失效两种状态，并进一步假设 失败是相互独立的。网络可靠性的计算，特别是寻找大型复杂网络的有效算法，以及 各类算法优劣的比较一直理论和实际都感兴趣的问题。 2 3 1 可靠性的精确算法 可靠性精确算法又可粗略地分为四类： 。 容斥原理：不交和算法；分解算法；特殊网络的可靠性算法 1 容斥原理：这一类算法的出发点是将可靠性用包括所有成功事件的并来表示，主 要是根据概率容斥原理公式求网络的可靠性。 尸，( g ) = 只ua ：u ua 。) = p r a ，) - p r a a ： ， ( 1 2 + + ( - 1 ) ”1 p a l a 2 a 。) ( 1 ) ( 这里a 表示最小路或晟小割( 即最小的成功事件) ，两终端表示s t 最小路，k 终端表示k 点生成树。) 星然，对于给定的网络，只要找到所有最小路或最小割代入( 1 ) ，就可求出网络的可靠 性。但是对j 二有m 个最小路( 最小割) ，( 1 ) 中共含2 。项。如果m 较大时，这方法就不 适州了。1 9 7 6 ，p m l i n 和其合作者在( 1 ) 基础上提出了一个新的拓扑公式 4l ，改 进了直接应用公式( 1 ) 求网络的可靠性。1 9 7 8 a s a t y a n a r ay a n a a p r a b h a k a r 把网 络的拓扑结构和容斥原理巧妙直接联系起来 3 ，得到 只( g ) = ( 一1 ) ”p r ( g 。) ( 2 ) 8 ( 这里g 。表示网络g 的无圈子图，n ，v 分别是网络g 的顶点数和边数) 。在公式( 2 ) 中抵消和合并了在公式( 1 ) 中没有抵消和合并的项，这样公式( 2 ) 中的项就比公式( 1 ) 中的项大大减少了。利用公式( 2 ) ，hs a t y a n a r ay a n a ，a p r a b h a k e r 提出一个高效算法 2 ，这个算法从网络拓扑结构出发，不需要找网络的所有道路，巧妙生成了所有p 一 圈子图，进而利用它求得网络可靠性。1 9 8 1 和1 9 8 2 ，a s a t y a n a r ay a n a 和其合作者 以将这个思想推广到求k 一终点可靠性问题和全终点可靠性问题上，得到了相应于2 一 终点可靠性的结果 4 ，5 3 。到现在为止，还没有看到文献发表对 3 3 改进或推广的结果， 这足以说明，应用容斥原理求网络的可靠性， 3 是个比较完美的结果。1 9 8 7 ， j ，a b u z a c o t t 对于割集进行相应 3 的研究，给出了相应割集的容斥原理结果 5 ，这 个算法不是很适用的。截止目前，用此方法求网络可靠性没有新的突破。 2 不交和算法 这类算法是利用b o o l e 代数方法以概率公式( 3 ) 为基础。 e ( a l u a ：u u 如) = 只 4 1 ) + 只 a i a ：) + + 只( a l a ：爿m 一- 爿。) ( 3 ) 算法形成内外循环。外循环是指计算p r a 1 ) 到p r a - ，柚而形成的循环。内 循环是指算法处理某一项p _ 丸a i 而形成的循环。1 9 7 3f r a t t a 和m o n t a n a r i 发 表丁第一个这类型的算法 6 。以后相继出现了大量的这类型算法。算法的主要焦点是 集中在一时排序以及在内循中如何巧妙地应用布尔代数结果来简化内循环运算。 m i t c h e l l0 l o c k s 在 2 0 中发表了对不交和算法的评论，他认为算法 2 0 产生的不交 平项数很可能是最少。即使不是最少，要找到更优的算法不必在排序问题 以及布尔运算上下功夫，应该探索新的途径。 3 分解算法 这类型的算法依靠贝叶斯公式进行分解。 r ( g ) = 只r ( g + p ) + q 。尺( g g ) ( 4 ) ( 这里g * e 表示在网络g 中把边e 的两个顶点合并成一个新的顶点，g e 表示在 网络g 中去掉边e ) 。 这一类分解是依照某种准则把网络g 分成若干个小网络。 2 ，d e g ( v ) 2 。j 是两条链x j 和x j ”组成，即兮= 巧7 u x j ”，此时 和x ”的公共端点为u 。v ，如表31 所示，我们可以用一条端点为u ，v 的链来代替 j 得g k 且使r ( o 。) = q r ( g ；) 。这就是“多边形一链”简化。 定理3 1 ：假设g k 含有一个j # 型多边形，在图g k 中用链x j 来代替多边形】，导出图 用g ? ，表示。正确决定链x 的边可靠度，让q ，表示相应的乘积因子，如表 3l 所示，那么r ( g f ) = q r ( g ：，) 。【1 5 】 6 多乏形 越_ 甚口矗芽 。 乏= ，j 譬 岱= g 。p a 叮c 少 一e r 一& 一，= p 。吼q 。 ( 向 占 d = p 。p j p 。0 + g 。，p ，+ 穹，p ，上吼p 。) 只2 i 万 a = g 。p 日。 y 一e t e 3 一 8 = p ，q q ： 见。瓦石 ( 鸯 。 艿= p 。p 。p 。( 1 + g 。p 。+ g 。，+ 吼，p = ) a = p 。q b q 。p d 七qd p o p c qd + q 。p b qc pd n ：坚二丛生：曼 d 9 昏e 3 一 p = p 。q p ：qd 6 = p ，p ，p ? q 。( 1 + q ，p ，tq ， p 、。q ：fp ：q ， p 。、 a 2 q 。p b q 。pj q 一e f 氐e r 8 = p ，q 、q ：p 。+ q ，p ，p ：q 6 = p ，qh p ：qa ， p ，。一 ( 4 ) r = p 。p p ：qj q - q ，p 。q 、p ，+ q ：fp ；- qj fp 。1 岱一， r 厂飞 j k i 2球= 吼p ，p 。吼 以2 百万 一e ，一e 5e t 一 p = p d qb p c q | ， j ! k ：= ：时， 6 = p ；q s q ：q 。 p ，2 = o 十， ( 珂 ( i # ：紊 r = p ，p p ：p j ( 1 一日