计算通信网络可靠性的分解技术

1996年第11卷第3

系统工程学JOURNALOFSYSTEMSENGINEERIN 1996Vol.11No.①计算通信网络可靠性的①沈元隆(邮电学院基础课部,本文应用分离节点的概念将图分解成两个子图,使通信网络端对可靠性的成功函数简化为两个子网络的可靠性成功子函数并且进一步导出由子网络不交化表示的原网络的不交化表达式最后得到通信网络更简便更紧凑的端对可靠性表达式,此简化方法适用于任意系统可靠性的计算.:节点分离,子图最小路集,最小割集不相交项,端对可靠性:NCOMMUNICATIONNETWORKRELIABILITYShen(NanjingUniversityofPosts munications,NanjingThis posesagraphintotwosubgraphs,usingtheofseparablenodes.Thesuccessfunctionofthesymbolicterminal-pairofcommunicationnetworksissimplifiedtothesuccessfunctionoftwosubnet-works.Andfurther,thedisjointexpressionoforiginalnetworkisderivedfromsubnetworks.Finally,theterminal-pairreliabilityofthecommunicationnetworkisgiven.Thissimplemethodisappropriateforrelabilityevaluationofallsys-:separationofanode,subgraph,minimalpathset,minimalcutset,disjointterm,terminal-pairreliability引计算网络可靠性的大部分方法首先需要计算出其全部最小路集或最小割集,然后进行不交化工作69,经验,含有V个节点、E条支路的网络其最小割集的阶为2V-2,最小路集的阶为2E-V+2(见文献[3]),计算量的指数增长给可靠性计算带来了.分解技术是降低计算复杂度的好办法Nakazawa[1,Rushdi2提出了Bayes分解方法①本文得到94邮电部24项目 49岁,男,,.49,male,M.,associatepro本文1995年9月22但对较大型的网络并不适用,deMercado[3、Aggarwal[割集分解法,使用邻接矩阵不同次幂的计算,并利用卡诺图进行化简等方法,Nakazawa[5提出了分解节点法,但这些方法仍然停留在手工计算上,并不适合于计算机计算.本文描述的一种应用分离节点概念将大型通信网分解成两个子网络同时导出了分解后通信网络端对可靠性的不交化统一.该的最大优点是把一个复杂的求整个网络端对可靠性的不交化问题分解为若干独立的较简单的子网络的不交化问题.在具体完成子网络不交化问题的过程中,本文采用能同时求取网络(或子网络)最小路集(或子路集)以及最小割集(或子割集)的方法[10.最后得到网络不交化的可靠性表达式,,此方法大大减少了计算时间和计算误差,并使整个系统的可靠性表达更加简单、更加紧凑,且易于在计算机上实现.分解技术的描述和算法步不可约图G(V,E)有V个节点,E条支路.其中s是源节点,t是终节点,采用分离节点将sCG2包含终节tCNcG1和G2的分离节点集,KNc的节点数,称G1G2是通过分离Nc中所有节点形成的.NjG1snj(nj∈NcMjG2njnj∈Nct的全部路的并GE条支路,G1E1条支路G2E2条支路,E=E1+GXx表示,G1G2的状态可用最小项XxXx来表示,显然,这是G的一种划分,即对任一个最小项Xx可以划分成两部分XxXx.SaXa的集合a,G12E1XxG22E2个Xx2E12E2=2EGXx,G1G2的组合可以表示图G的特性,即系统的成功函数F表示如下F nj∈

Nj (a1b1a2b2a3b3,…为系统的全部最小路集,F=a1b1∪a2b2∪a3b3∪得到系统成功函数F的不交

表达-

Fdis=a1b1 (a+a1b)a2b2 (

+a1b)(a+a

)a3b3+ ( 类此,(1)可改写

F=N1M1 (N1+N1-1)N2+(N1+N1M1)(N2+N2M2)N3M3+ (需要说明的是式2)和式(3)中的“加号表明了各项之间是互不相交的,但应注意到式2)aibi是独立的网络元素,故式2)是不交化的,而式(3)NiMi却不是.所以要得到式(3)最后的不交化,必需对其每一项进行不交化工作,即Fdis=(N1M1)dis ((N1+N1M1)N2M2)+((N1+N1M1)(N2+N2M2)N3M3)dis+ (式(4中每一项均是一些N和M交集,任何一项的N的交集与其余的M的交集部分是统计独立的,原因是N交集部分所有元素只出现在G1,而M交集部分的所有元素只出现在G2的统一为Fdis=(N1)dis(M1)dis ((N1N2)dis(M2)dis (N1N2)dis(M1M2)dis( (N1N2N3)dis(M2M3)d+(N1N2N3)dis(M1M3)dis+(N1N2N3)dis(M1M2M3)dis)+ (式(5)中每一项与该网络端对可靠性表达一一对应,布尔和积可以用算术的和积来替代,即iRs,t=(Fdis){xi,x-,+,}→{pi,qi,+ (i算法步骤将所描述的系统用可靠性逻辑图(RLG)表示,简化RLG为不可约图GV,E)Nc中的所有节点Nj(NjG2njtMj(或最小割集-j).为了便于算法比较,采用文献6中的方法进行式(5)各项的不交化工作代入式(6),得到网络的可靠性表达式 1可靠性逻辑图如图1,s=1,t= 1d1d2是并联支路,可简化成一条支路d,pd=0.8,pd=0.5,pd=1 qd1d=209e1、e2是串联支路,epe=pepe121、b2、b3路,可简化成一条支路b,即得不可约图,如图2所示图 可靠性逻辑 图 不可约图2Cbcd}Nc={3,4}3,3(aG1,3b3F=NM∪N3NG1的{s4}最小子路集MG2的4,t最小子路集.10]N=b+ M=f+N3G1的s3最小子路集M3G23,t最小子路集.N3=ab+ M3=g+步骤 由式(5)图3图G关于Nc={34}的分 Fdis=(N)dis(M)dis (NN3)dis(M3)dis+(NN3)dis(MM3)由文献6或文献9])中的方法进行不交化工作, (N)dis=b+(M3)dis=g+ef

(M)dis=f+egNG1s4最小子割集,3(a虚线子图得s4N=a-b-+b-NN3)表示要同时满N=a-+b-N3=ad+即(

-N3)=(-

-N3)dis=ab-同理MG24,t最小割集,3b虚线子图得4,tM=e-f-+f--M=e-f-+f-M3=g+e即MM3)=(MM3dis=gef,而NN3表示要同时满N=b+N3=ad+3(aNN3s为始节点3为终节点的最小子路集.得NN3)=abd+acd+bcd得(NN3)dis=abd+abc-d+步骤 代入式(5)、式(6)Rs,t=(pb+papcqb)(pf+pepgqf)+paqbqcpd(pg+pepfqg+(papbpd paqbpcpd+qapbpcpd)pg2可靠性逻辑图如图CafjNc={2,6}G1分别如图5(a和(F=N6M6∪N210中方法可计算得N6M6N2M2N6=kj+cbj+acfjM6=1+ghi+N2=ac+kf+abk+bcfM2=dh+egh+eil+dgil得不交化表达( - 图 可靠性逻辑图6)dis=kj+cbjk+acfjk(M6)dis=1+ghil-+dehil-(M2)dis=(dh+eil+egh+dgil)deilidgil-N6表示G1s,6),由图5a虚线子图得s,6)子割集-N6N2表示要同时满足 - -- --N6=j+ck+abk+bfN2=ac+kf+abk+即(N6N2)=acj+acb-f-k-+kfj-+abkj-+bcf得不交化表达(N6N2)dis=kfj+acjk-+ac-jkf-+abkjf-+bcfjk-a-+acb-k-f-M6G2的(6,t)最小子割集,由图5b)虚线子图得6,tM6=i-l-+l-h-+l-ge-+l--d--6M2表示同时满足M2=dh+ghe+eil+即(M6M2)=dhil-+dhle-+ghei-得不交化表达M6M2dis=dhi-l-+dhl-i+ghei-l-d-N6N2)表示同时满足N6=kj+cbj+acfN2=ac+kf+abk+5(aN6N2s为始节点2,6节点为终节点的最小子路集,得N6N2)=jkf+abk+ack+bcf+acf+abc)得不交化表达最后Fdis=(N6)dis(M6)dis+(N6N2)dis(M2)dis (N6N2)dis(-6M2)dRs.t=(pkpj+pcpbpjqk+papcpfpjqkqb)(pl+pgphpiql+pdpephpiqlqg)+(pkpf+papcqjqk+papcqjpkqf papcqjpkqf+pbpcpfqjqkqa+papcqbqkqfpj)(pd pepiplqd pepiplpdqh pepgphqdqi pepgphqdpiql pdpgpiplqhqe)pj(pk+papkpbqf papcpkqbqf+pbpcpfqkpapbpcqfqk)(pdphqi+pdphpiqlqgqe+pgphpeqdqiql图5图G关于Nc=2,6的分 1NjMj的排列分解的一般方法一致[6～9目的也一样;使不交化计算量减少,最后的表达式更为紧凑、简单.(1)通常情况下,等式右边恰好是图G的全部最小路,但有时这些并中会出现个别非最小路(1N3M3bcdef

62G关于Nc={3,4,5}的分由于要进行分项不交化处理,所以这冗余的表达式并不会影响最后的计算结果K2时,式1～5是精确解,直观意义是图G的任一最小路不可能同时经过边界节点.K3时,式1)有可能会丢失图G的个别最小路,1)～5)有可能是近似解,2中,C={def,bk}Nc={3,4,5}K=3.式(1G的最小路{d,e,hi,jk{b,cdeh,i,j见图6,但丢失的是大长度最小路,只会给可靠性表达产很小的舍入误差但并不是所有K≥3时式(1)都是近,如图7(a)分解为图7(b)(c)Nc={23456K=5,这时原图的最小路并未丢失,式(1～式(5仍是精确解G图分解为G1、G2,理论上与C没有什么关系,但为了减少计算量,并获得精确解,应尽可能选取K=2的分解方法,并尽可能使G1G2复杂程度相当.图 不丢失最小路的实例及其分分解法比直接计算,工段量要少得多,可靠性表达式也要简单得多,本文例2仅就文6的方法进行了计算,671项相比,2中用到的6个因式分别是3项,3项,6项,6项,6项和3项.NakazawaH.Bayesian positionmethodforcomputingthereliabilityofanorientednetwork.IEEETransReliability,1976,25(1):77～80RushdiAM.SymbolicreliabilityysiswiththeaidofvariableenteredKarnaughmaps.IEEETransReliability,1983,32(2):14139DemercadoJ,SpyratosN,BowenBA.Amethodforcalculationofnetworkreliability.IEEETransReliability,1976,25(1):71～76AggarwalKK,ChopraYC,BajwaJS.Asimplemethodforreliabilityevaluationbynetworkposition.IEEETransReliability,1982,31(4):355358NakazawaH.Reliabilityequivalentseparationofanode.IE