（应用数学专业论文）网络可靠性计算的进一步研究.pdf

东北大学硕士学位论文摘要 网络可靠性计算的进一步研究 摘要 随着信息时代的发展，网络在社会生活中起着越来越重要的作用。丽网络可 靠性是网络运行和设计中的重要参数，因此，网络可靠性的计算是网络研究中的 一个重要课题。本文对大型网络可靠性的计算进行了研究，主要内容如下： 1 分析讨论了网络可靠性的计算问题，提出了一种新的分层抽样法来估计大 型网络可靠性的m o n t ec a r l o 方法。该方法针对各种不同情形提出了相应的分层方 式，避免了已有的分层方法在一般网络可靠性估计中的局限性：同时在相同的抽 样数目的条件下，对于估计误差的减小，本文的方法也比以往的方法优越了很多。 2 讨论了具有不可靠结点网络的可靠性计算问题，将蒙特卡罗方法利用到了 不可靠结点网络中，并结合不可靠结点网络的特征，给出了估计不可靠结点网络 可靠性的有效的蒙特卡罗方法，大大提高了模拟的有效性。 3 提出并证明了关于具有不可靠结点网络两终端可靠性的三角形约简法则。 利用本文所给的约简法则，可以使一些特殊网络可靠性计算的复杂度降低很多。 特别地，对于格网络可靠性计算的复杂度从利用因子分解定理的0 ( 2 ”) 降到0 ( 1 ) ( ”表示网络的边数) 。 关键词：蒙特卡罗方法分层抽样法不可靠节点网络可靠性三角形约简 一i i 东北大学硕士学位论文 t h ef u r t h e rr e s e a r c ho fc a l c u l a t i o na b o u tn e t w o r k r e l i a b i l i t y a b s t r a c t w i t hd e v e l o p i n go ft h ei n f o r m a t i o ne r a ，n e t w o r k st a k em o r ea n dm o r ei m p o r t a n t f u n c t i o n a n dn e t w o r kr e l i a b i l i t yi st h ev e r yi m p o r t a n tp a r a m e t e ri nr u n n i n ga n d d e s i g n i n g s ot h ec a l c u l a t i o no fn e t w o r kr e l i a b i l i t yi sai m p o r t a n tt a s ko ft h en e t w o r k r e s e a r c h t h i st e x ts t u d i e dt h ec a l c u l a t i o no ft h el a r g e - s c a l en e t w o r kr e l i a b i l i t y , a n dt h e f o l l o w i n gi si t sm o s t l yc o n t e n t ： 1 a n a l y z i n g a n dd i s c u s st h ec o m p u t i n gp r o b l e ma b o u tn e t w o r kr e l i a b i l i t y , a n d b r i n g i n g an e ws t r m i f i e ds a m p l em e t h o dt oe s t i m a t er e l i a b i l i t yo ft h e l a r g e s c a l e n e t w o r k t h em e t h o dp u tf o r w a r dd i s p a r t i n gs t r a t u mc o r r e s p o n d i n gt ot h ed i f f e r e n c e c a s e ，w h i c ha v o i d st h eo l dw a yl i m i ti nt h ee s t i m a t i n gu n i v e r s a ln e t w o r kr e l i a b i l i t y , a n d w h e nt h es a m p l i n gn u m b e ri se q u a l ，t h i sm e t h o di sm o r ee x c e l l e n tt or e d u c i n gt h ee r r o r 2 d i s c u s s i n gt h ec a l c u l a t i n go fr e l i a b i l i t ya b o u tt h en e t w o r kw i t hu n r e l i a b l en o d e s a n du t i l i z i n gm o n t ec a r l om e t h o dt ot h en e t w o r kw i t hu n r e l i a b l en o d e s ，m o r e o v e r , p u t t i n gf o r w a r de f f i c i e n tm o n t ec a r l om e t h o d sb yu s i n gt h ec h a r a c t e ro fn e t w o r kw i t h u n r e l i a b l en o d e s ，i m p r o v i n gv a l i d i t yo ft h es i m u l a t i o n 3 g i v i n ga n dp r o o f i n gt h en e t w o r kw i t hu n r e l i a b l en o d e st r i a n g l er e d u c t i o na x i o m f o re f f i c i e n tc o m p u t a t i o no ft e r m i n a l - p a i rr e l i a b i l i t y t h et r i a n g l er e d u c t i o na x i o mm a y e f f i c i e n t l yr e d u c e t h ec o m p u t a t i o n a lc o m p l e x i t yo ft h e g r a p hc o n t a i n i n gt r i a n g l e s u b g r a p h s e s p e c i a l l y , f o rs i m p l i f i e dg r i dn e t w o r k ，i t sc o m p u t a t i o n a lc o m p l e x i t yc a l lb e r e d u c e dt oo ( 1 ) f r o mo ( 2 ”) b yu s i n gd e c o m p o s i n gt h e o r y k e yw o r d s ：m o n t ec a r l om e t h o d n e t w o r kr e l i a b i l i t y s t r a i f i e ds a m p l eu n r e l i a b l en o d e s t r i a n g l er e d u c t i o n 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研 究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成 果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名：参劲良 日期：翮卅刃 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的 规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编 入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名 签字日期： 导师签名： 签字日期： 东北大学硕士学位论文第一章绪论 第一章绪论 “作为一种历史趋势，信息时代的支配性功能与过程日益以网络组织起来。” 随着信息时代的发展，网络不仅在自然科学上，而且在社会科学上也起着核心的 作用。因此网络的设计和维护就非常的重要，而在网络设计和维护过程中，网络 可靠性是一项重要的性能指标。所以网络可靠性的研究电显得非常重要。网络可 靠性的一般定义是：网络在规定条件下和规定时间内的生存能力。网络的生存性 是基于概率论和图论的知识提出来的，它描述了随机破坏以及网络拓扑结构对网 络可靠性的影响。可靠性一般是指网络的连通性，它反映了基础网络拓扑结构支 持网络正常运行的能力，是网络运行和设计中的一个重要参数，因此，如何分析 和计算网络可靠性是网络研究中的一个重要课题。 “网络是一组相互连接的节点”【l 】在网络( 系统) 可靠性的研究中，人们常 常用概率图来表示网络( 系统) 。图的点和边都分配给正常运行的概率。网络可靠 性的计算问题主要有三个问题： 1 两终端可靠性问题，即至少存在一条从一个指定点到另一个指定点正常运 行的路的概率。 2 k 一终端可靠性问题，即至少存在一棵以给定的k 个节点为顶点的正常运 行的子树的概率。 3 全终端可靠性问题，即至少存在一棵正常运行的生成树的概率。 这三方面问题的研究已经取得了大量的结果 2 - 2 4 】。特别是在7 0 年代末8 0 年代初， 网络可靠性的复杂性问题得到解决，对以后的探索有理论指导作用。 网络可靠性计算问题可分为两类：可靠性的精确算法、可靠性的近似算法。 1 1 可靠性的精确算法 可靠性的精确算法一般可以分为四类：l 、容斥原理方法2 、不交和算法3 、 因子分解算法4 、特殊网络的可靠性算法 1 1 1 容斥原理方法 这一类主要是根据概率的容斥原理公式求网络的可靠性： p r g = p r a i u a 2 u u 以) = z p r 4 ) 一p r 4 4 ) + + ( 一1 ) “p r a 1 a ：4 1 1 ) f t 0 有 p ( f 磊- 1 1 筹) a 去p 2 捌 ( 2 2 ) 这表明，不等式 i 霸一水等 ( 2 3 ) 近似的以概率1 一d 成立。并且瓦收敛到，6 向速度的阶为o ( n2 ) 。 如果仃0 ，那么m o n t e c a r l o 方法的误差s 为 占：鸳 ( 2 4 ) 4 n 。 一6 一 东北大学硕士学位论文第二章基础知识 其中正态差五与显著水平0 t 是一一对应的，其对应关系可用n ( 0 ，1 ) 积分表及公式 兰r p j d t ：1 一兰 ) 4 2 z c 。 2 给出。 分析公式( 2 4 ) ，不难看出，m o n t ec a r l o 方法的误差s 是由盯和4 - y 决定的。 如果盯固定，那么要想提高精度一位数字，就要增加1 0 0 倍的工作量。另一个方 面，在固定误差和抽样产生一个x 的平均费用c 不变情况下，如果盯减少1 0 倍， 则可以减少1 0 0 倍的工作量。如果费用c 不是固定的，也就是说，随着方法的改 动而改变时，由于= ( 九形) 2 ，c = ( 九形) 2 c ，因此，m o n t e c a r l o 方法的效 率是与仃2 c 成正比的。总而言之，作为提高m o n t ec a r l o 方法效率的重要方向， 既不是增加抽样数，也不是简单地减小标准差盯，而应该是在减小标准差的同 时兼顾考虑费用的大小，使得方差与费用的乘积盯c 尽量小。当然在平均费用不 变的情况下，我们就只需减小误差旷。 m o n t ec a r l o 方法在计算数学、计算物理等领域已得到广泛的应用，在本文的 后面几章中，我们利用该方法来研究大型网络可靠性的计算问题。 一7 东北大学硕士学位论文第三章一种利用分层抽样法估计网络可靠性的蒙特卡罗方法 第三章一种利用分层抽样法估计网络可靠 性的蒙特卡罗方法 关于大型网络可靠性的近似计算方法已经出现了很多，利用蒙特卡罗方法来 估计网络可靠性的文献也有了不少，本文就在已有成果的基础上进行研究讨论， 提出一种新的分层抽样法。 3 1 符号说明和假设 g ( v ，e )表示一个由顶点集v ，边集e 的无向图所定义的网络 蚓 边集元素的数量 川顶点集元素的数量 kk c v 且足中的顶点为终端点 p ，边集e 中的元素 i1 一x p ，p r e ，工作) s 表示一种网络状态向量( j ，j ：，。) ，其中n = l e j j ，表示边e 。的状态，如果e i 工作，l j s 。= l ；否则s ，= 0 巾( s )可靠性函数，如果网络在s 下处于工作状态，则中( s ) = l ；否则 ( s ) = 0 r ( g )网络g 的可靠性，简记为月 g表示中( s ) 的数学期望即g = e ( 中( s ) ) = e ( m ) q 网络的所有状态集合 c网络工作状态集合 d网络失效状态集合 q 网络状态集合的互不相交的子集 g ，表示( s ) 在q ，条件下的数学期望g ，= e ( c 1 ) ( s ) iq ，) 西( s l q 。) 表示在q 。中的s 的可靠性函数 其他符号在利用时再加以说明。 一8 东北大学硕士学位论文第三章一种利用分层抽样法估计网络可靠性的蒙特卡罗方法 假设网络的每条边都独立地失效和工作，节点都可靠 3 2 问题描述 网络的一个状态是一个胛元组s = ( s 。，j ：，) ，如果e ，工作，则s = 1 ，否则 s = 0 。当k cv ，如果k 中任意两个终端之间都至少存在一条路，即至少存在一 颗k 树，则说明s 是一个网络工作状态，中( s ) = 1 ；否则，网络处于失效状态， o ( s ) = 0 。 网络的所有状态集合q 包含2 “个状态，且可将q 分为两个子集：c 为工作状 态集合，d 为失效状态集合。当s c 时o ( s ) = l ，当s d 时，o ( s ) = 0 。由 假设边工作和失效都是相互独立的，且中是一个随机变量，则 g = e ( m ( s ) ) = ( s ) ( s ) = p r ( s ) 且p r ( s ) = ( 丌只) ( n 曩) = l s i = 0 而 r ( g ) = p 。u 。s ) = p r ( s ) j e l c 。r 所以 r ( g ) = g = e ( ( s ) ) 根据上面的描述，我们知道，网络可靠性就等于可靠性函数的数学期望， 即r = g = e ( m ) ，所以只需计算g 就可以得出可靠性。根据概率论和数理统计的 知识，我们知道，只要对q 中的状态进行n 次模拟抽样，每次计算出西( s ) ，当n 很大的时候，就可以用m p ) 的算术平均来近似代替它的数学期望。这也是蒙特卡 罗方法的一种基本思想。 3 3c r u d em o n t ec a r l o ( c m c ) 方法 最简单的抽样方法就是直接从状态空间q 中模拟个样本爷7 ：l f n ) 并且通过示性函数由( s ) 的算术平均值孽来估计g 营= 寺中 。) v ，一i 显然季为g 的无偏估计且方差、w ( 季) 2 警。 下面给出计算季的算法，一般称为c r u d em o n t ec a r l o 方法。 o 东北大学硕士学位论文第三章一种利用分层抽样法估计网络可靠性的蒙特卡罗方法 算法 1l = 0t = o ： 2 抽取n 个服从 o1 上的均匀分布的随机变量“，i f 疗 3 赋值：s t 卜1 + b j ， s _ ( s l ，j 2 ，矗) 4 计算中( s ) ： 5t - t + ( s ) ，l 卜三+ 1 ，当l n 时转2 ，否则 6 计算二n 则亩就是网络可靠性的一个粗略的估计值。 3 4 计算可靠性的分层抽样法 m o n t ec a r l o 方法就是利用随机模拟试验来获得m ( s ) 的期望。c r u d em o n t e c a r l o 方法所作出的估计误差比较大，由前面的基础知识知道，可以通过减小方差 来减小误差。下面就介绍分层抽样方法来减小误差。 分层抽样法的基础思想就是把整个状态空间分成几个不相交的集合，然后对 每个集合进行抽样，再将所得的结果组合起来得到所求的结果。 例如，可以把状态空间q 按一定的方式分成m 个互不相交的集合 q ，q ：，q 。，然后根据全期望公式，有 g = r ( g ) = e ( o ) = p r ( f 2 ，) e ( oiq ，) ( 3 1 ) 如果分别对q ，( 1 i m ) 进行抽样计算，然后估计出e ( q b l q 。) ( 记为g ，) 的 值，记为蚕，再根据( 3 1 ) 计算出可靠性的估计值营，显然这也是g 的一个无偏 估计。它的方差为 。垂( 驯q ，) v a r ( 萨v a r ( 蕃( 生可一)( 3 2 ) = 和c 蚶簪 其中n ，表示对q ，的抽样次数。根据c a u c h y s c h w a r z 不等式 ( b ) 2 d ，2 b ，2 一1 0 一 东北大学硕士学位论文第三章一种利用分层抽样法估计网络可靠性的蒙特卡罗方法 p m 汗等等 b 。， ( ( q ，) 蜀莓) 2 丛警蛭：，( 3 4 ) n j。 ( q ) 厄蚕 ：丝! ! 竺! 型兰! 墨( 3 5 ) ( q ，) 舀虿， 每层抽样次数按( 3 5 ) 式分配时，3 - 差( 3 2 ) 取值最小。但是每层的期望g ，并不知道， m ：掣n 节( q 。) p r ( q ，) v 嘲= ；| ；舯；) 等 = 扣( 蚴墨争 ( 3 6 ) 2 专善 ( q r ) 毋一( q ，) g ，2 东北大学硕士学位论文第三章一种利用分层抽样法估计网络可靠性的蒙特卡罗方法 9 2 _ 嘻( 咄厅 2 嘻篇厕r ， 喜r 器哮厕，2 = 扣2 将( 3 7 ) 式代入( 3 6 ) 式得 v 盯( 劲万1 ( g _ 9 2 ) = 詈 等号成立的条件是所有的量都相等，显然这一般是不可能的，因此，等号一般不 能取到。所以采取最简单的分配抽样次数的分层抽样法都要比c m c 要优越。 下面就看怎么样分层可以使得方差减小的更多。 3 5 一种估计可靠性的新的分层抽样法 f i s h m a n 已经利用r ( g ) 的上下界来控制( s ) 的期望，并且提出了重要抽样法 和分层抽样法 3 2 - 3 3 1 来解决此类问题。f i s h m a n 在文献 3 3 q a 提出利用r 条边的状态 来作为分层的基础，其分出来的状态空间为2 个，如果选边太多，则会引起分层 太多，在相同的抽样数目下，每部分所分得的数目就越少，这就会使得计算失真 很大。为避免这种情况，本文提出了另外一种新的分层法来估计网络的可靠性。 3 5 1 基本思想 状态空间要求分解成互不相交的集合，在此我们依然以r 条边为分层的基础， 但是分出的状态不再是2 个。假设选择的边为网络g ( v ，e ) 中的边e ，e ：，e ，那 么根据下面r + 1 种情况 e l ，一e j e 2 ，一e l e a 2 p 3 ，e l e 2 瓦一e r l e r ，一e l e 2 一e 3 e r( 1 ) 或者 一e i ，e l e 2 ，e l e 2 己，e l e 2 8 3 e ，一l e r ，e i e 2 e 3 e ， ( 2 ) ( 这里虿表示边e ，失效) ，将状态空间q 分成r + 1 个彼此不相交的状态空间，分别 记为n ，q ：，n 卜。此时，分层依然遵循按概率比例分配抽样次数的原则，但是 如果出现e l q ，) = o 或l ，则此层不分配抽样次数。由上面分层方法知道，如果 所选的边组成了g ( v ，e ) 的一个割集，那么( 1 ) 中必然会出现一些层满足 一1 2 东北大学硕士学位论文第三章一种利用分层抽样法估计网络可靠性的蒙特卡罗方法 e ( 1 q 。) = 0 ，如果选择的边组成了g ( v ，e ) 的一条路，那么( 2 ) 中必然会出现一些 层满足e ( m l q 。) = l ，这种情况下不给分配抽样次数( 不进行抽样) ，因为这些层 的可靠性可以直接精确的计算出来，所以没有误差，方差为0 。这样必然能比前面 所提的一般分层抽样法更多的减小方差。假设只有前m 层需要分配抽样次数，那 么分配情况为 ，= 掣其中，a = l ，2 ，m ，并且m r + 1 ) p r ( f 2 ，) ，= l 利用c a u c h y - s c h w a r z 不等式可以证明，此时 v a r ( g ) p r ( f 2 ，炫 g g 如果p r ( f ，) 越小，那么我们的分层就越有效。因此如何选边对于我们的分层很 j = l 重要，并且，选好边后，是按( 1 ) 还是按( 2 ) 分层，也对方差有很大的影响。下面按 计算两终端可靠性选边时所遇到的情况进行分类讨论。 情形l 选的边只含有割集，不含路的情况( 能构成割集，不能构成路) 所选的边集为如。，e ：，e ，) ，且只含割集，不含路，那么，不失一般性，设 k ，p ：，e 。) ，) 为极小割集， 情形1 1剩下的边不再含有割集的情形( 即所选边不能构成两个及两个以上的 边不交的割集) 把状态空间按 e l ，一e l e 2 ，e i o 一2 e 3 ，一e l e 2 一e 3 一e r i p r ，一e l e ：e 一3 一e r ( 1 ) 分层，按( 1 ) 中记法，q 。表示边e 。工作的情况下网络的状态，q 。表示边p 。，e 。失 效，而e ，工作的条件下网络的状态，那么， e q b ( s ) q ，) = 0( m + 1 i ，+ 1 ) 而此时，根据全期望公式，我们得到 r ( g ) = e ( m ) = p r ( q ，) e ( 巾iq ，) ( 3 8 ) l = l 根据： ! 塑生n ，( 其中f _ 1 2 m ，并且m ，+ 1 ) 分配抽样次数，那么( i q ，) p r ( f 2 ，) l - l 的估计值 东北大学硕士学位论文第三章一种利用分层抽样法估计网络可靠性的蒙特卡罗方法 m e a ( s 旧) 季= 旦f ( 3 9 ) 显然( 3 9 ) 式是e l q ，) 的无偏估计。 将( 3 9 ) 式代入( 3 8 ) 式得出e ( 面) 的估计值季 季= p r ( q ，) 巾( 刚q ，) 显然这个估计值是e ( t 9 ) 的无偏估计 一步的证明出方差减小情况为 n ? 此时我们可以利用c a u c h y s c h a r z 不等式进 ，e a ( s 恤，) ( 舻v a r t e 。t p 蛾) 旦可一】) p r ( q ，) 。m = 型j f 一善f ( nr ) v a r 荟中( 陋) 】) p r ( q ，) 。 2 午i = l ( q 。) 毋( 1 喝) p r ( d ，耀 l p l p 2 p mg g 詈 如果e p r ( q ，) = 1 一五歹：j _ 越小，那么方差减小的范围就小( 因为不能准确 f = l 的求出方差的值，只能给出方差的一个下届，所以不能简单的说方差减小了很多， 只能说此时方差减d , n 了某个很小的范围) 。所以在这种情况下我们选择的边集所 包含的割集应该尽量使得五a 芦。大。 情形1 2 剩下的边还含有割集的情况 不妨设 e 。，b 。e 。) ，) 构成一个极小割集，且剩下的边不含割集。( 也 即所选边集含有仅两个边不相交的割集) 。那么此时分层的情况又可以在( 1 ) 的基础 上进一步的改进。此时先把状态空间分为 e 1 ，e l e 2 ，一e 】e 一2 e 3 ，e l e 2 一e 3 一gr a i e m ，一e l e 2 一e 3 瓦 所对应的状态空间q 。，q ，n 。，之后再在前面某一层的基础上利用剩余边的特征 继续分层，不妨利用第一层再分，此时q 再分为 1 4 东北大学硕士擘位论文第三章一种利用分层抽样法估计网络可靠性的蒙特卡罗方法 e l e r n + l ，e i e m + l e r a + 2 ，e l e m + t e m + 2 - 一e r 所对应的空间。此时分的层数依然是，+ 1 。虽然分层后得到的e o ( s ) i q ，) = 0 的 层数少了很多，但是可以证明在这种分层的情况下，按照前面的方法分配抽样次 数，此时方差减小的情况比上面的方法好了很多。同样利用c a u c h y s c h w a r z 不等 式可以得到 v a r ( 小生垃等必藤 半藤 号 根据上面的分析，我们在选择边的时候，如果割集的边不是很多的情况，可 以选择两个或者以上的割集作为分层的基础，这样有利于减小误差。并且除了极 小割集里的边，其他的边对方差不影响，所以选边时一般应考虑只选极小割集的 边作为分层的基础。 情形2 所选的边只含有路，不含割集的情况 所选的边集为慨，e ：，e ， ，且只含路，不含割，那么，不失一般性，设 慨，口：，e 。 ( m ，) 为极短路，也按上面的方式分两种情况讨论a 情形2 1剩下的边不再含有路的情况 把状态分为 一e j ，e 1 一e 2 ，e l e 2 瓦，e l e 2 e e ，- l 瓦，q p 2 e e r q 。表示边q 失效的情况下网络的状态，q 表示边q e 。工作，而p ，失效的 条件下网络的状态，那么 e 中( s ) l n 。) = 1( m + 1 i r + 1 ) 按照情形1 1 的分析，我们可以得出 v 哟 午p r ( n j ) g g ：半蜉 g g 所以如果p ，( q ，) = 1 一p 。p ：p 。越小，那么越有利于方差的减小a 所以在这 i = 1 种分层情况下，选边应该使得p 。p ：p 。尽量大。 情形2 2 剩下的边还含有且仅有一条路( 也就是说所选的边包含有两条边不重的 路) 的情况 不妨设 e 。，e 。e 。 0 ，) 组成另外一条路。此时先把状态空间按照 一e l ，e l e 一2 ，e l e 2 弓，一，e l p 2 e 3 e m 一1 e m ，e r e 2 e 3 e 分层，然后再在某一层的基础上继续分，不妨利用第一层继续分。那么第一层又 可以继续分为 东北大学硕士学位论丈第三章一种 , l f f l 分层抽样法估计网络可靠性的蒙特卡罗方法 一e i e m 十】，一e l e m 十l e m + 2 ，瓦p m 刈e + 2 p r 此时分层的层数也是，+ 1 。利用这种分层法，按照前面的方法分配抽样次数，我 们同样可以证明方差减小的情况一定优于情形2 1 。 v a t ( g ) 生丝亟善业g g 半藤 堕n 由上式可以看出，我们在选择到底哪一层再分时，应该选择( n ，) 大的那一 层，这样有利于方差的减小。而且方差的减小与组成路以外的边没有关系，所以 选边时一般只选极小路上的边作为分层的基础。 综上所述，我们选边时，在极小路包含的边不是很多的情况下，可以考虑选 择两条边不重的路。但是一般大型网络的路都比较长，所以这种方法也只能提供 一种理论依据。 情形3 所选的边既包含路，又包括割集 在这种情况下我们的分层就应兼顾前面两种情形。为了能较好的与前两种方 法作出比较，在此，我们依然分为两种情况来讨论。为求简洁，假设所选的边仅 含有一条极小路和一条极小割，没有多余的边。 情形3 1 先根据路进行分层 因为极小路和极小割集一定存在一条边相同。设 e ，p ：，e 。) 沏，) 是极小路， 而 e 。，e 。，e ，) 是极小割。那么首先在路的基础上进行分层： 一e i ，e l 瓦，e r e 2 毛，p l e 2 e ”e m - i 弓，e i e 2 e ”e 对于割集，现在选择某一层进行在割集的基础上的再分，不妨在第一层上继续进 行分层，那么第一层分为： 一e l e 。，一e i 瓦口+ 1 ，一e l e r n e m + 1 t 这样也同样分为，+ 1 层。并且同时出现了e 坤( s ) i q ，) = 1 和e a p ( s ) i q 。) = 0 的 情况。同理，按照概率比例给每层分配抽样次数，仿照前面证明我们可以证明得： v a r ( g ) ! 业型等旦坠生藤 半g g g g 这样分层比只按路的情况分层要有效。选择哪一层继续分? 还是应选择( q ) 大 的那一层。所以如果同时选择了路和割作为分层基础的时候，我们一般都采取同 时兼顾的方法，而不用前面只按照路为基础的方法。 1 6 东北大学硕士学位论文第三章一种利用分层抽样法估计网络可靠性的蒙特卡罗方法 情形3 2 先根据割集进行分层 这样分层结果与情形3 1 又不同。为方便说明，不妨设 e l , e ：，e r a ) r ) 为 极小割，而 e m , e 。，e ，) 为极小路。那么首先对割集分层： e l ，一e l e 2 ，一e l c a 2 e 3 ，写瓦己瓦一1 e ，一e l e 2 一e 3 然后再在某一层的基础上继续分，还是选第一层再分： e , e - m + l ，e l e m + l 瓦+ 2 ，e l e 川e m + 2 e r 这样分层依然为，十1 层。同前面的操作，可以得到 v a r ( g ) 生煦型藤 半g g 詈 这种分层要比前面只按割集分层的要有效，选择哪一层继续分依然看( q ，) 的大小。但是到底是情形3 1 还是情形3 2 有效，一般比较 1 一p i p 2 p 。 盟藤和垣色! 凸生蜉的大小。 综上所述，如何选边，选好边之后怎么样分层对方差的影响还是很大的。理 论上层数分得越多，方差应该降得越多，但是，如果层数太多，在抽样总数相同 的情况下，每层分得的抽样数目也就很少，而m o n t ec a r l o 方法是在抽样数目较大 的情况下才有意义，所以分层不宜太细。在选边时，是否同时选择路和割，或者 应该选几个边不重的割和路，需要看实际情况。 如果是k 终端则应讨论彪树和使这k 个节点不连通的割集。方法与两终端类 似，在此就不用再细讨论了。 3 5 2 与f i s h m a n 的分层抽样法的比较 f i s h m a n 的分层抽样法依然是以边为基础作出的分层，但是他的分层是以边 的所有状态来分的，这就使得分层数目是边的指数幂2 7 ，这样，他的分层所选的 边不能太多。而且他依然是对e n , ( s ) l q ， = l 和e p ( s ) i q ，) = 0 不分配抽样次 数，那么要出现这种情况必须含路或割，而一般大型网络的路和割的边数都比较 大，所以要想得到e o ( s ) i q 。 = 1 和e 中( s ) l q ， = 0 的话，会使分层过多，而在 抽样数目相同的情况下每层的抽样数目相对减少许多，不利于误差的降低。并且 在同样选择按照每层的概率比例分配抽样数目时，如果出现路或割的时候，两种 分层抽样法的方差减小情况一致，但是在这种情况下，本文的分层数目要比 f i s h m a n 的小了很多，而且f i s h m a n 的抽样法对一般大型网络不可能同时兼顾路 和割的情况。所以对于一般的大型网络，本文的分层比f i s h m a n 的要实用而且有 效得多。 一1 7 东北大学硕士学位论文第三章一种利用分层抽样法估计网络可靠性的蒙特卡罗方法 3 5 3 本文方法与f i s h m a n 的重要抽样法的结合 f i s h m a n 在文献【3 1 种已经给出了一种利用r ( g ) 的上下界来控制中( s ) 的 望。他的主要思想是： 首先找出边不重的极小路暑，忍，只以及边不重的极小割集q ，c 2 ，q ，将 q 分成3 个不交集q 1 ，q 2 ，q 3 ，其中q 1 表示至少存在e ，b ，b 中的一条路工作的 集合，q 3 表示至少存在c ，c ，c ，中的一个割集失效的集合，那么有 q 1cc q 3cd 。 由全期望公式： g ：3e ( o i q 一) ( s q ，) = p r s q 五 o i q l ) + p r s q 2 e ( o l q 2 ) + p ， s q 3 e ( 中i q 3 ) ( 3 1 0 ) = 丌1 + 孔e ( m i q 2 ) 丌，= p r s q ，( f _ 1 , 2 ，3 ) 由前面的定义知： 雹= 1 一兀( 1 一兀p ，) i j a l e i 5 只 巧+ 石：= 1 一乃= 丌( 1 一兀a ) ， l j j q ，e c ， 可以看出( 3 1 0 ) 给出了g 的一个上下界( 巧g 7 l + 万2 ) 。现在只需对 q 2 中的状态进行抽样，则在样本总数n 不变的情况下，g 的估计值为 ( 瞄) 喜2 巩栅z 午 显然这也是g 的无偏估计。且方差为 v 砥护壁竽芦趔 因此，这种抽样方法比c m c 更有效。 g g ， n 根据上面分析，可以把这种抽样方法用到我们的分层抽样法中。每一层不作 c r u d em o n t ec a r l o 抽样，而用f i s h m a n 的重要抽样法。 为了方便运算和说明，不妨假设我们选择的边是从弓，只，只和c 。，c ：，c ，中 一1 8 东北大学硕士学位论文第三章一种利用分层抽样法估计网络可靠性的蒙特卡罗方法 选择的。设 q ! 表示在第i 层中的至少存在一条路工作的集合 q ? 表示在第i 层中的至少存在一条割失效的集合 死= p r s q ? ) ( 1 i ，+ 1 , 1 3 ) 现在以情形1 1 的情况来说明这种结合方法的有效性。 ，+ 1 ，十1 g = p r ( q ) e ( o | q ，) = ( q ，) 厅。l + 万，2 e ( mq ；) ) f = 1 t = l 此时只需对e ( 中l q ；) 进行抽样模拟，而不再是对e ( o i q ，) 作简单的抽样。再 对满足e 中( s ) i q ，) = 1 和e m ( s ) i q 。) = 0 的每一层不进行抽样，那么此时g 的估 计值应该为 ，+ i 季= ( q 。) e ( 0 1 q ，) m 。中( s i 2 善( 刚k ，蝇： 其中当h i r + 1 时，e m ( s ) l q ，) = 1 或e 西( s ) l q 。) = 0 e ( d = ( q 。) e ( o 旧) 。e p ( s iq ；) 。 = e p ，( q ，) 石l + 万。2 上l 万一】 + e ( o l q ，) = lv ， i = h = p r ( q 。) ( 万，。+ 万，：g ，：) ) + e ( 中i q 。) = g 所以季是g 的一个无偏估计，且 1 9 d0 c ：中 以 = l + 的一 东北大学硕士学位论文第三章一种利用分层抽样法估计网络可靠性的蒙特卡罗方法 v a r ( 季) = v a r 艺p r ( q ，) e ( 巾iq ，) 。兰中( 驯n ；) 。 - v a r 善州嘞 7 9 i 1 + 巧z 生百一) + 萎即i q j ) ) = 喜防 嘶虹型瓮塑! ：挲圭( q j ) ( 吕弧) ( 蝇：唱) j 3 i h f ( q 。) 。 m 时e 。( s ) l q ，) = o 或1 ) 给每一 ( q 。) 层分配抽样次数 7 对于期望不等于0 或1 的每一层进行f i s h m a n 的重要抽样法川。 当i m 时，对于每个i ，有下面步骤： ( 1 ) 初始值如= o ，九= 兀见，= & ，q 。= o ，吩= 丌两，r = q 6 吩 e e c 口 ( 2 ) 重复下面的步骤知道所有的研都等于0 a ) 按照选择原则l 3 1 1 选择边巳 b ) 找出所选边所在的路最和割g c ) 计算成 d ) 抽取服从 01 】均匀分布的随机变量“ e ) = l “+ p 刊 d 如果边在前面已经给出的路中，从中移去它，如果在割中，从r 中 移去它 2 l 一 东北大学硕士学位论文第三章一种利用分层抽样法估计网络可靠性的蒙特卡罗方法 g ) 厶：! 盘，：s n 一( o , j p npn ( 3 ) 对剩余的边执行下面的步骤 a ) 抽取服从【o1 上的均匀分布的随机变量村 b ) s n = + p o j 8 计算出每一个g 9 带入公式( 3 1 0 ) 计算出g 的值。 3 6 关于抽样次数分配的进一步讨论 3 6 1 费用一定时，每层抽样次数的分配 因为使用m o n t ec a r l o 方法所消耗的资源( 费用) 是和抽样次数直接相关的。 在分层抽样法中，如果第，层中每次抽样的费用为c ，那么如果要求总费用不能超 过c 的情况下，有 c ：c ! k l + c 2 k 2 + + c 。k 。 分层抽样法常常采用等分抽样总数的方法，一般情况下所有的c ，都相等。但 是当我们对网络状态按照5 所分层后，所得的每层的费用就不再是一样。因为估 计网络可靠性的费用主要是对每边进行模拟抽样所决定的。按照5 的方法分层后， 每层中，不需抽样的边不一样，而且数目也不一样，所以每层中每次抽样的费用 也应不一样。此时，抽样次数的分配就不仅仅按照每层对整个网络可靠性计算贡 献的大小( 即概率系数) 来分配，而应兼顾每层费用的问题。 因为每层抽样都与边有关，所以不妨假设每对一边抽样所花费用相同，这样 最终费用就只与边的数目相同。而每层中，由于条件不同，需要抽样的边数也就 不同，设每层需要抽样的边数分别为n 1 ，：，n 。，而对每一边抽样的费用都为c ， 那么对于总费用与边的关系，我们有 c = n l k l + 1 1 2 k 2 + 。- + 门。k - f r 1 即有二= 以1 k l + 疗2 足2 + + 聆，足。 ( 3 1 2 ) 0 此时关于分配抽样次数如果仅按照 k ，= 掣k ，其中，( f = l ，2 ，m ，并且川 r + 1 ) ( 3 1 3 ) p r ( f 2 ，) 2 2 东北大学硕士学位论文第三章一种利用分层抽样法估计网络可靠性的蒙特卡罗方法 抽样，而总次数世= k ，n i n ( 3 1 2 ) ，( 3 1 3 ) 式需要同时成立，所以要满足此条 。腿c 邓蜀帆k ：+ 删 ：妻竽坚妇世 。 百芝p r ( q 。) 件，有 k = ，p r ( q ，) l i = l 。羔咿( q ，) n 。= m i n n ，( i = 1 , 2 ，一所) ) n 。= m a x n ，( i = 1 , 2 ，聊) ) 所以有j t _ k 旦 m a x c m i n c 那么方差为 ( q ，) 。m v a - ( g ) = v a r f 二l 孑- p r ( q 。) 巾( s 7 l a ) 】 l i = 1 j = l p r ( f 1 ，) 。 = 旦了一p r ( q ，) g ( 1 一曼) 、 f _ l = 去n , p ，( q ，) p r ( q ，) ( 1 一g ) ) 但是当我们考虑了每层边数不同时，兼顾每层对整个可靠性的贡献大小得出 世：堡垒2 一c 珥p r ( q 。) 。 其中，( f _ l 2 研，并a m ，+ 1 ) 。此时有 。m ( s 怛，) 。 季2 荟州蚴午+ ，要p = 吾哆 ( q ，) 】 m ( s 恤。) 】+ g uf = l i - i j = 1 i * m + l 所以有 一2 3 一 ( 3 1 4 ) 东北大学硕士学位论文第三章一种利用分层抽样法估计n g $ - - 靠性的蒙特卡罗方法 v a r ( 季1 ) = v a r 式 2 p r ( 9 2 ，) 【o ( s 。1 q ，) 】) 乙，= 1i = l，；1 mf ， = 去 ( q 。) r 竹，【m ( s 。盼) 】 l ，1 = 1l = l j = l = 昙匹( q 。) 1 2 p r ( f 2 ，) ? t i g ，( 1 一g t ) o i = li = l o 措1t = l 所以当要求费用一定时，利用此种分层抽样法采用( 3 1 4 ) 的方式分配系数的方 法比( 3 1 3 ) 优越。 而我们一般情况下不是单单只是去追求精确度，而是在保证一定的精确度和费 用的情况下使我们所用的计算机资源消耗更少。f i