不交和公式及其在网络可靠度计算中的应用

摘要：提出了不交和公式及其在网络可靠度计算中的应用，和传统的算法相比，该算法操作简便，易于实现，计算复杂度小的点，从而适合于大型网络可靠度的计算。

关键词：网络可靠度；不交和；极小路

中图分类号：TP393 文献标识码：A文章编号：1007-9599 (2011) 12-0000-01

Disjoint Sum Formula and Applications in the Calculation of Network Reliability

Liu Yubao1,Guan Lihong2,Zhu Haiying3

（1.Software College,Changchun University,Changchun130022,China;2.College of Science,Changchun University,Changchun130022,China;3.Information Technology Branch,Changchun Vocational Institute of Technology,Changchun130033,China）

Abstract:Given the disjoint products formula and the application in network reliability pared with the traditional algorithm,it is easy to operation,andrealize and compute simply,thus suitable for calculating reliability of large network.

Keywords:Networkreliability;Disjoint Sum;Minimal path

一、引言

在网络的分析与设计中，可靠度是衡量网络质量的一个重要指标。计算网络可靠度的方法有：真值表法、卡诺图法、容斥定理、因子分解定理、不交和布尔代数法[1]。而利用不交和法求网络可靠度是一种普遍而有效的方法。现给出一种计算网络可靠度的不交和算法，该算法能简便地在计算机上实现，从而适用于大型网络可靠度的计算。

二、不交和公式

不交和算法是系统可靠性分析中的一种重要的方法，它是代表系统可靠工作的逻辑多项式，由于不交和公式中的各个项都是不相交的，因此系统的可靠度可以用这些项的概率之和来进行计算[2]。

（一）多事件的概率计算公式

设A1，A2，…，An是任意n个事件，若A=A1∪A2∪…∪An，则

显然当n比较大时，上述概率公式（1）极为繁杂。如果首先对事件A1，A2，…，An进行不交化，得所有不交项为B1，B2，…，Bm，则

设A=P1+P2+…+Pm，则A的发生概率P（A）为

P（A）=P（P1+P2+…+Pm）

为了计算上式，需对P1，P2，…，Pm进行不交化[3]：

上式中各项是不相交的，有

如：

则：

其中，Pa，Pb，Pc分别是每一个元件正常工作的概率。从上面的式子可以看得出来，经过不交化处理以后，能够很容易地计算出 的发生概率，得到的 即为系统的可靠度。

（二）极小通路

极小通路定义为系统结构单元的一个集合里面的各个单元如果能构成一条从起点到终点的一条通路，那么构成这条通路的单元的数目是最小的，即去掉集合内的任何一个单元都不能构成通路[4]。

（三）布尔运算

吸收律：M+MN=M，m+mN=m

分配律：（M+N）P=MP+NP，（m+n）p=mp+np

摩根律：M+N=M+ N， =（其中M和MN是不相交的）。

三、网络可靠度的计算

设P1，P2，…，Pn是网络 中由源点S到汇点T的所有极小通路，则网 的两终端可靠度为[5]：

RS，T（G）=Pr（P1+P2+…+Pn）

为了计算上式，运用摩根律对P1+P2+…+Pm进行不交和运算：

P1+P2+…+Pm=P1+ P2+…+... Pm.。

上式中各项是不交的，从而有：

RS，T（G）=Pr（P1+P2+…+Pm）=Pr（P1）+Pr（ P2）+...+Pr（... Pm）。

由此可见，在不交化的基础上很容易计算出网络的可靠度。运算后所得的不交和项即是网络正常工作的不交和表达式，直接代入各个变量工作的概率即可得到网络的可靠度。

四、结论

计算网络可靠度一直是网络设计与实现问题中的一个重要问题，本文给出一种计算网络可靠度的不交和算法，该算法计算简单，易于实现，从而适合应用于大型网络设计中的可靠度的计算。

参考文献：

[1]梅启智,廖炯生,孙惠中.系统可靠性工程基础[J].北京:科学出版社,1987:76-110

[2]Wils on J M.An improved minimizing algorithm for sum of disjoint products.IEEE Trans Reliab,1990

[3]LocksM O,Wils on J M.Note on disjoint products algorithm.IEEE Trans Reliab,1992

[4]Zhao Lian2 chang,Xu Jun2 chen.An efficient minimizing algorithm for sum of disjoint products.Micro electron Reliab,1995

[5]Locks M O.A minimizing algorithm for sum of disjoint products.IEEE Trans Reliable,1987

[基金项目]吉林省教育厅“十一五”科学技术研究项目（吉教科合字［2010］第162号）

[作者简介]刘玉宝（1975-），男，讲师，硕士，博士生，主要研究方向为系统可靠性。