收稿日期:2002212217基金项目:国家自然科学基金资助项目(69973011)・作者简介:高 飞(1968-),男,辽宁铁岭人,东北大学博士研究生,讲师;王光兴(1937-),男,辽宁沈阳人,东北大学教授,博士生导师・第24卷第6期2003年6月东北大学学报(自然科学版)Journal of Northeastern University (Natural Science )Vol 124,No.6J un.2003文章编号:100523026(2003)0620535204计算无线通信网络K 2终点可靠性的拓扑公式高 飞,王光兴(东北大学信息科学与工程学院,辽宁沈阳 110004)摘 要:提出了无线通信网络(RCN )的K 2终点可靠性问题・给出最简树(S T )的概念,提出计算网络从源点(S )到特定终点集(T )的可靠性的一个新拓扑公式・该公式本质上是将容斥原理公式和不交和公式融合在一起,公式中各项和网络的一类特殊子网络一一对应,与相应的S atyanarayanna 公式比较,该公式包含更少的项和更少的算术运算,并给出一个算例验证上述结论・关 键 词:算法;可靠性;可靠性表达式;容斥原理;无线通信网络中图分类号:TP 30218 文献标识码:A无线通信网络(RCN )的应用日益广泛,它不仅价格便宜,而且适合某些特殊场合,例如:移动通信网络、自组网及数据采集系统等・有线网络的可靠性已有深入研究,但对于RCN 的可靠性研究较少・A boEI Fotoh 和Colbourn 提出一个概率无向图模型,并且证明了计算RCN 的K 2终点可靠性是N P 2难问题,提出一个计算RCN 的22终点可靠性的近似算法[1]・一些特殊的RCN 也被研究[2,3],文献[4]给出了K 2终点可靠性的因子分解算法・文献[5]是网络可靠性研究的重大突破,网络可靠性学者对此已经取得了共识[6～8]・S atyanarayanna 和Probhakar 提出了P 无圈子图的概念[5],使得计算网络的S T 可靠性最终归结为枚举网络中所有P 无圈子图・后来S atyanaraynna 等人将上述思想推广到计算SA T 和SKT 可靠性[6,9]・文献[10]改进了文献[5]的结果,提出了adp 无圈子图的概念,使得网络的S T 可靠性计算归结为网络中所有adp 无圈子图枚举,因为adp 无圈子图是一类特殊的P 无圈子图,一般地说,给定一个网络,其adp 无圈子图的数量远远小于P 无圈子图的数量・因此文献[8]的公式比文献[5]含有更少的项,也就是说,前者比后者更简单・以上的研究结果成立的条件都是边不可靠,但对于无线网络人们研究不多・本文考虑的RCN 网络可用一概率有向图G (V ,E )表示,其结点有两种状态运行和失效,边可靠,结点失效概率已知且相互独立,V 中有两类特殊结点源点S 和汇点集T ,RCN K 2终点可靠性是指S 能传送信息到达T 的概率・由于并联边在RCN 中并不起作用,因此为了讨论方便假定RCN 中无并联边・容斥原理是解决有线网络可靠性的有效方法,该原理对于RCN 同样成立・在本文中提出了最简树概念,结合不交和算法给出一个计算有向RCN 的K 2终点可靠性的拓扑公式,根据该拓扑公式可以计算RCN 的K 2终点可靠性,计算量小,表达式简洁・1 定义、符号定义T i :RCN 网络的含S 和集合T 的一棵树・S T i :RCN 网络的含S 和集合T 的一棵树,且树上所有结点集合没有子集可以组成T j ・P 图:图中每条弧至少在它的一棵从源点S 到汇点集T 的S T 树上・P 无圈子图:一个子图,它是P 图且不含圈・S T 树生成的极大P 子图:设S T 树生成的子图为G ,若有T i 且该树包含的S T i 树的所有结点,当S T i 不在G 上,则添加该S T i 树不在G 上的所有边到G 上,这样生成的图称S T 树生成的极大P 子图・构型:若干S T 树生成G (V ,E )的子图G i ,则称以这些S P 树为元素的集合为他们生成的极大P 子图的一个构型・ASTP 子图:设D ={S T 1,S T 2,…,S T l },S T 1,S T 2,…,S T l ,是结点两两不交的S T 树,G i是RCN 的极大P 无圈子图,若G i 中没有D 中的任意一棵S T 树,则称G i 是ASTP 子图・记号G (V ,E ):RCN 网络,其结点集合为V ,边集合为E ・G (V ,E )是一个概率图,即具有源点S 及汇点T 有向图,每棵弧至少在其一S T 树上,且其每个结点正常工作概率已知・S ,T :分别表示G 的源点和汇点集・P i :结点n i 的可靠性・A +B (A ・B ):事件A 与事件B 的并(交)・ A :表示事件A 的补・m :表示G 的最简树的数量・K P :表示树P 上的结点集合・x i (x i ):表示结点x 的状态为运行(失效)・R (G ):表示RCN 的K 2终点可靠性・2 求RCN K 2终点可靠性的拓扑公式考虑一RCN 网络G (V ,E ),V =(1,2,…,n )和E =(x 1,x 2,…,x e )为G 的结点集合和边集合,n =V ,e =E ・p i 表示结点的运行概率,q i =1-p i 表示结点失效概率・网络RCN K 2终点可靠性的定义为[1]R (G )=RCN 中至少有一从S 到T树每个结点均运行的概率=P (6T i )・(1)式中,T i =1,2,…,n p 为图G 的第i 个S T 树;n p 为树的数目;P ( )表示概率・根据布尔代数公理P (x +xy )=P (x )可知,若T 不是最简树,则T 的结点集合K T 有子集合设为K ST 构成最简树S T ,K T =K ST ∪K ST ,P (T +S T )=P (ST )・因此有定理1 R (G )=P (6S T i ) i =1,2,…,m ,m 为S T 树数目・根据容斥原理可知:R (G )=6mi =1P (S T i )-6i <jP (S T i)P (S T j)+…+(-1)k +16i 1<i 2<…<i kP (S T i 1)…P (S T ik )+…+(-1)m +1P (S T 1)…P (S T m )・共计2m 项,这里有许多重复的子图,由于边是永远正常工作的,所有子图只与点有关,所以添加边不影响结果・把所有子图均变成极大P 子图,并合并相同的极大P 子图,得到如下公式:R (G )=6d i P (G i ),(2)d i 为P (G i )的系数・引理1 若G i 有一棵S T 树不在任何构型中,则式(2)中的G i 的构型相互抵消・证明 设G i 的所有极小构型为A 1,A 2,…,A n ,最简树S T 不在任何构型中,则式(2)中包含G i 的构型为:包含 A 1的构型+包含 A 1 A 2的构型+…+包含 A 1 A 2… A n -1A n 的构型,由于S T 不在任何构型中,每项至少都有2个构型,根据二项式定理所有构型相互抵消,d i =0・定理2 对于有向概率图G 及其特定终点集合{S ,T },设G 所有S T 树为S T 1,S T 2,…,S T m ,则R (G )=6d i P (G i ),其中,d i =(-1)n i +e i +k;n i 和e i 分别是G i 的结点数和边数;k 为T 集合的结点个数;G i 为若干最简树生成的只含S T 树的P 无圈子图・证明 ①若G i 含有圈,根据文献[6]的定理1知道有一棵S 到T 的树,T 对生成该圈没有任何贡献・由于G i 是极大P 子图,因此根据S T 树的定义存在一棵S T 树对生成该圈没有任何贡献,该S T 树不在任何极小构型中・根据引理1所有生成G i 的构型相互抵消,d i =0・②若G i 有某个非S T 树,设为T 1,见图1・根据S T 树的定义知道该树包含一棵S T 树,该树的结点是T 1的结点集合的真子集,且对生成132弧没有任何贡献,该树不在任何最小构型中・根据引理1d i =0・图1 含非ST 树的网络G iFig.1 Networks G i including a tree that isn πt ST tree③若G i 所有树都是S T 树,参看文献[6]的定理2,知道d i =(-1)n i +e i +k,n i 和e i 分别是G i的结点数和边数,k 为T 集合的结点个数・综合式(1),(2),(3),R (G )=6d i P (G i ),其中,d i =(-1)n i +e i +k,n i 和e i 分别是G i 的结635东北大学学报(自然科学版) 第24卷点数和边数;k为T集合的结点个数・G i为若干最简树生成的只含最简S T树的P无圈子图・若结合不交和算法,以上拓扑公式可做进一步化简・设S T1,S T2,…,S T m,是RCN网络的所有S T树,S T1,S T2,…,S T l,是结点两两不交的S T树・R(G)=P{S T1+S T2+,…,+S T m}=P{S T1+,…,+S T l+S T1+,…,+S T l×(S T l+1+,…,+S T m)}=P{S T1+,…,+S T l}+P{S T1+…+S T l×(S T l+1+…+S T m)}=P{S T1+,…,+S T l}+P{S T1+…+S T l×(S T1+…+S T m)}=R1(G)+R2(G),R1(G)=T(S T1)+P(S T1)P(S T2)+…+P(S T1)P(S T2)…P(S T L-1)P(S T L) R2(G)=6d i P{S T1+…+S T l(G i)}=6d i P{S T1…S T l(G i)}这里,G i是所有只含S P树的P无圈子图, R2(G)=6d i P{S T1-G i…S T l-G i(G i)}・由于P( A E AB)=0,所以若G i中含有S P i,1≤i≤l,则该项为0・R2(G)=6d i7P(βij)P(G i),βij=ST i-G i,因此有如下定理:定理3 对于有向概率RCN图G及其特定终点集合S,T,设G所有S T树为S T1,S T2,…, S T m,若D={S T1,S T2,…,S T l},则R(G)= R1(G)+R2(G),其中R1(G)=P(S T1)+ P(S T1)P(S T2)+…+P(S T1)P(S T2)…P(S T l-1)P(S T l),R2(G)=6d i7 P(βij)P(G i)・这里G i中所有不含D中ASTP 子图,βij=S T i-G i,d i=(-1)n i+e i+k,n i为G i 的结点数,e i为G i的边数,k为T集合的结点个数・令由定义知G的ASTP图亦是P无圈子图・所以G中ASTP子图的数量小于图G中只含P 无圈子图的数量・这两类子图数量的差异依赖于图G中的不相交S P树的数量・一般而言,G中不相交S T树越多,它们的数量差距越大・这说明了新的计算K2终点可靠性公式有非常简洁可靠性表达式,含有更少的算术运算,是一个非常有效的拓扑公式・3 例 子下面通过一个例子说明计算K2终点可靠性,新公式比直接利用容斥原理计算简单・考虑图G (见图2)・图2 无线通信网络GFig.2 Radio2communication networks G 图中有4棵S T树:st162t2,st16145t2, st1s345t2,s t1s3412t2・除S T树外的所有树都是S T树的P子图有:62+345,62+6145,62+3412,6145+345,345+3412,62+345+3412,62+345+6145・若用定理3,可靠性的表达式为p2p6+p1p4p5p6+p3p4p5+p1p2p3p4-p2p3p4p5p6-p1p2p4p5p6-p1p2p3p4p6-p1p3p4p5p6-p1p2p3p4p5+p1p2p3p4p5p6+p1p2p3p4p5p6・若直接应用容斥原理计算图2的可靠性,需要计算15项・若应用文献[5]中的公式计算由于公式中必须包含所有的从S到T的树,在这里要包含1棵非S T树,计算量几乎成指数倍增加,需要计算20多项・这里D={62,345},应用定理3,可靠性的表达式为p2p6+p2p6p3p4p5+p2p3p1p4p5p6+p6p5p1p2p3p4・一般说来直接应用容斥原理或枚举S T树然后进行不交化的工作量都是很大的,所以表达式都很长・相比之下上面的拓扑公式计算量要小得多,所得的表达式也短得多,这直观地显示了该公式的优越性・参考文献:[1]Abo EIFotoh H M,Colbourn C puting22terminal735第6期 高 飞等:计算无线通信网络K2终点可靠性的拓扑公式reliability for radio2broadcast networks[J].I EEE TransReliability,1989,38(5):538-555.[2]Abo EIFotoh H M,Colbourn C J.Efficient algorithm forcomputing the reliability of permutation and interval gragh[J].Net works,1990,20:883-899.[3]Abo EIFotoh H M.Algorithm for computing message delayfor wireless networks[J].Net works,1997,29:117-124. [4]孔繁甲,乔百友,王光兴・计算无线广播网络的可靠性[J]・东北大学学报(自然科学版),1998,19(5):492-494・(K ong F J,Qiao B Y,Wang G puting the reliabilityfor Radio2broalcast Networks[J].Journal of NortheasternU niversity(N at ural Science),1998,19(5):492-494.) [5]Satyaranayanna A,Prabhakar A.New topological formulaand rapid algorithm for reliability analysis of complexnetworks[J].I EEE Trans Reliability,1978,27:82-100.[6]Satyaranayanna A,Hagstrom J N.A new algorithm forreliability analysis of multiterminal network[J].I EEE TransReliability,1981,30:25-33.[7]Wood R K.Factoring algorithms for computing K terminalnetwork reliability[J].I EEE Trans Reliability,1986,35:269-278.[8]Barlow R E.Mathematical theory of reliability:a historicalperspective[J].I EEE Trans Reliability,1984,33:16-20.[9]Satyaranayanna A.A unified formula for analysis for somenetworks reliability problems[J].Trans on Reliability,1982,31:23-32.[10]Zhao L C,K ong F J.A new formula and an algorithm forreliability analysis of networks[J].Microelect ron andReliability,1997,37(3):511-518.New Topological Formula for K2Terminal Reliability of Radio2 Communication NetworksGA O Fei,W A N G Guang2xing(School of Information Science&Engineering,Northeastern University,Shenyang110004,China.Corres pondent:G AO Fei, E2mail:gaofei1968@)Abstract:The K2terminal reliability problem of radio2communication networks(RCN)was considered.The concept of the simplest tree(S T)was presented.A new topological formula was presented to compute K2terminal reliability of radio2 communication networks from sources S to terminal set bining inclusion2exclusion principle with disjoint sum of products formula,the formula contains terms corres ponding one by one to a class s pecial subnetworks.For a given network,the terms of the formula are fewer than those of the corres ponding Satyanarayanna formula.Finally an example was given to illustrate our conclusion.K ey w ords:algorithm;reliability;reliability expression;inclusion2exclusion principle;radio2communication network(Received December17,2002)待发表文章摘要预报基于观测器的广义系统H∞可靠性控制器陈跃鹏,张庆灵,翟 丁,徐天群利用广义系统的传感器故障模型,研究广义系统H∞可靠性控制器的设计问题・首先,建立了广义系统传感器故障的一般的模型,在此模型的基础上设计基于观测器的控制器・其次,定义了广义系统的H∞可靠性控制器・接着,用带广义约束的广义代数Riccati不等式(G ARI),给出传感器正常以及出现部分故障时,所设计的控制器使得闭环广义系统容许且传递函数H∞范数有界的充分条件,即存在H∞可靠性控制器的充分条件・同时,还通过对广义系统的受限等价变换,去掉了广义约束,简化了带广义约束的G ARI・进而可以通过解简化后的G ARI来设计H∞可靠性控制器・最后,给出一个数值例子来演示设计过程并说明此方法的有效性・基于输出的供应链分销阶段绩效改进方法殷梅英,王梦光,刘士新总结了标杆学习中目标企业选择和学习途径确定的方法・在此基础上研究了基于输出的绩效评价和改进的标杆方法,给出了特定输出增长等定义和有关数据包络分析(C2GS2)的扩展模型・模型中所有被评价企业均视为具有相同输入、输出的决策单元・指出最小特定输出增长为绩效改进的最短路径,所对应企业为最佳标杆学习对象・在供应链分销阶段,该方法更易于操作:企业可保持现有投入,通过提高输出元素水平改进绩效・835东北大学学报(自然科学版) 第24卷。
