基于二元决策图的系统可靠性模块分析方法

涂序跃

(华东交通大学轨道交通学院，江西南昌330013)

故障树分析[1-2](fault tree analysis，FTA)是一种广泛应用的系统可靠性建模方法。传统故障树分析方法随着系统元件数增多，最小割集数会呈指数关系增加，容易产生实践中常见的“组合爆炸”问题。采用二元决策图(Binary Decision Diagram，BDD)方法对故障树进行分析[3-8]，可以简化系统可靠性定性、定量的求解过程。但是，BDD方法分析故障树亦有不足，即故障树向BDD的转化受到基本事件排序的影响[3-5]。所以，为使BDD方法有效分析系统可靠性，需找出最优的基本事件排序方法，使所得BDD结构最小。可是，至今为止仍没有一种普遍适用的最优基本事件排序方法，这就给BDD方法求解大型、复杂系统的可靠性造成困难。针对BDD方法存在的不足，本文提出了一种基于BDD的模块方法对系统可靠性进行分析，基本研究思路如下:先把系统故障树分解成相互独立的模块;其次采用BDD方法对其进行分析;最后向上递归综合模块的求解结果，得到整个系统的可靠性。

1 基于BDD的系统可靠性模块分析方法

1.1 基于二元决策图(BDD)的故障树分析方法

1.1.1 二元决策图

二元决策图本质是布尔逻辑函数的图形表示，即用有向无环的二叉树图来表示布尔逻辑函数[3](如图1所示)。二元决策图包括终结点和非终结点，结点间通过‘1'分支或‘0'分支连接。二元决策图中每条路径始于根结点，终于终结点，终结点的‘1'状态指系统失效，‘0'状态指系统工作[10]。

二元决策图采用不交化形式表示系统失效逻辑函数Top。图2所示的系统失效逻辑函数为:

图1 BDD示例

式中:“+”表示布尔算子OR，“◦”表示布尔算子AND，X1X2X3X4表示基本事件。

遍历图2所示的二元决策图，搜索从根结点到‘1'终结点的所有路径，并保留路径中沿‘1'分支发展的非终结点，则由这些保留的非终结点组成的一个集合就是系统的割集。因此，遍历图2所示的二元决策图得到三个割集可得:{X1}、{X2，X3}、{X2，X4}。

因为二元决策图中所有路径相互排斥，故相应故障树顶事件失效概率表示为

式中:QSYS表示故障树顶事件失效概率;qXi表示基本事件Xi的失效概率。

1.1.2 故障树向BDD的转化方法及基本事件的排序

故障树转化成二元决策图普遍采用if-then-else(ite)规则[4]。该规则由故障树最底层基本事件开始进行ite结构转化，消除最底层的逻辑门;然后逐层向上进行ite结构转化，直至故障树顶事件，消除故障树所有逻辑门，得到相应的二元决策图。

采用if-then-else规则将故障树转化成二元决策图的过程中，必须先确定基本事件的顺序。令F、G分别表示二元决策图中的两个节点，其中F=ite(X，f1，f2)，G=ite(Y，g1，g2)，X、Y是故障树的基本事件，如果X的排序在Y的前面，即X＜Y，则

如果X与Y的排序相同，即X=Y，则

图2 故障树转化成BDD范例(变量排序:X1＜X2＜X3＜X4)

式(3)、(4)中，＜op＞对应为故障树中门的类型(AND或OR)的布尔算子，f1，f2，g1，g2分别为故障树的布尔变量。

由ite结构转化规则可知，二元决策图的结构大小受基本事件排序影响。不同的基本事件排序，得到不同大小的二元决策图[9-12]。以非终节点数作为衡量二元决策图结构大小的标准，二元决策图结构越小(非终节点数越少)，则二元决策图技术较之传统故障树分析越具有优越性。在已有研究成果的基础上，本文提出下述3条基本事件排序的基本规则[13-14];

规则1 根据从上至下的原则确定基本事件排序，即基本事件在故障树中的层次越高，排序越前;

规则2 根据基本事件重复次数确定基本事件排序，即基本事件在故障树中重复出现越多，排序越前;

规则3 故障树中相同层次、且没有重复的基本事件从左至右排序。

1.2 故障树的模块分解

故障树模块就是相互独立的子故障树，是故障树中至少两个底事件的集合，向上可到达同一逻辑门，而且必须通过此逻辑门才能到达故障树顶事件，该逻辑门称为模块输出或模块顶点，故障树的所有其它底事件向上均不能到达该逻辑门[15]。模块不能有来自故障树其余部分的输入，而且不能有与故障树其余部分重复的事件。

模块分解就是把系统故障树分解成相互独立的模块(故障子树)。本文采用线性时间算法[16]来确定系统故障树的模块。线性时间算法基本原则叙述如下:对系统故障树进行深度优先，从左至右遍历;假定V是一非根结点，t1，t2分别对应结点V第一次和第二次的访问时间，如果结点V的后代结点不会早于t1被访问，也不会晚于t2被访问，则以结点V为顶事件的故障子树是一个模块。

线性时间算法确定系统故障树模块时，需要注意两点:(1)每个非根结点至少被访问两次，第一次是由其父结点朝下遍历，第二次是由其最右子结点朝上遍历;(2)以任一非根结点为顶事件的故障子树不会遍历两次[11]。

1.3 基于模块方法的故障树分析

1.3.1 基于模块方法的故障树定性分析

基于模块的故障树定性分析实质是一个自下而上的递归综合求解过程。先分析最底层故障树模块(该模块只包含基本事件)，采用BDD方法求出该模块的所有最小割集和发生概率;然后将其用基本事件代替，该基本事件故障发生概率等于模块故障发生概率。对最底层模块被取代后的故障树再进行模块分析，分析新故障树最底层模块，同样用基本事件将其代替。分析过程递归进行，直至整个故障树分析完成。

基于模块方法的故障树定性分析依据上述原理，具体步骤为:

(1)采用BDD方法求出故障树所有最底层模块的最小割集，将这些模块用相同故障发生概率的基本事件代替，得到新的故障树;

(2)采用BDD方法求出新故障树所有最底层模块的最小割集，如果这些最小割集中包含代替模块的基本事件，则代替模块的基本事件用其最小割集代替，得到新故障树最底层模块的所有最小割集，并且其中只包含原故障树的基本事件;

(3)递归向上执行相同分析过程，直至求出原故障树的所有最小割集，这些最小割集中只包含原故障树的基本事件。

1.3.2 基于模块方法的故障树定量分析

基于模块方法的故障树定量分析与定性分析原理相同，采用BDD方法求出故障树最底层模块的故障发生概率，用具有相同故障发生概率的基本事件代替最底层模块，得到新的故障树。对新故障树进行相同分析，求出新故障树的最底层模块，用具有相同故障发生概率的基本事件代替最底层模块，递归重复该过程，直至整个故障树分析完成。

基于模块方法的故障树定量分析具体步骤为:

(1)采用BDD方法求出故障树所有最底层模块的故障发生概率，将这些模块用相同故障发生概率的基本事件代替，得到新的故障树;

(2)采用BDD求出新故障树所有最底层模块的故障发生概率，将这些模块用相同故障发生概率的基本事件代替，得到新的故障树;

(3)递归向上执行相同分析过程，直至求出原故障树顶事件发生概率。

2 分析实例

用相同概率且同名的基本事件代替模块M 1、M 2，得出:

所得QM即为故障树顶事件失效概率。

模块分析方法求解系统故障树最小割集如表1所示。模块M，即系统故障树的最小割集为:{M1}、{M 2}、{e7}、{e11}、{e1}。{M 1}、{M 2}分别用其子模块的最小割集代替，得到系统故障树所有最小割集为

下面以文献[9]中所示故障树为例，详细阐述基于二元决策图的系统可靠性模块分析方法。图3是来自文献[9]的故障树范例，采用线性时间算法[16]对其进行模块分解，模块分解结果如图4所示。整个故障树作为一个最大的模块M，其中又包括两个相互独立的子模块M 1、M 2。

采用二元决策图方法对所有模块进行可靠性分析，故障树基本事件排序为:e7＜e11＜e1＜e15＜e0＜e8＜e4＜e3＜e12＜e10，模块M 1、M 2、M对应的BDD如图5所示。先求出模块M 1、M 2顶事件失效概率，用相同概率的同名基本事件代替构成新的故障树，并转化成相应的BDD。

由式(2)可得:{e15，e10}、{e15，e8}、{e4，e3，e12，e10}、{e7}、{e11}、{e1}。

图3 故障树范例

图4 故障树模块分解

图5 模块对应的二元决策图(基本事件排序:e7＜e11＜e15＜e8＜e4＜e3＜e12＜e10)

表1 故障树最小割集列表

基于BDD的系统可靠性模块分析实例表明:该方法在定量分析中，求解系统故障树顶事件失效概率更简单;定性分析过程中，仅得到所有最小割集，没有任何非最小割集，免除了BDD方法分析整个故障树易产生非最小割集问题。

3 结论

基于BDD的系统可靠性模块分析方法，采用线性时间算法将系统故障树分解成相互独立的模块，分别求出各模块顶事件发生概率，然后递归综合求解出系统故障树顶事件的失效概率。模块分析方法在定性、定量分析大型、复杂系统的可靠性过程中，避免了最小割集不交化求和的繁琐过程，又可简单、明了的直接得出所有最小割集。相比传统故障树分析方法和采用BDD方法直接分析整个系统故障树，模块方法具有明显优越性，适用于大型、复杂系统可靠性分析。

[1] 曾声奎.系统可靠性设计分析教程[M].北京:北京航空航天大学出版社，2001:117-144.

[2] 李海泉，李刚.系统可靠性分析与设计[M].北京:科学出版社，2003:136-172.

[3] AKERSSB.Binary decision diagrams，IEEE Transaction on Computers[J].1978，27(2):509-516.

[4] RAUZY A.New Algorithms for Fault Trees Analysis[J].Reliability Engineering and System Safety，1993，30(32).40:203-211.

[5] SINNAMON RM，ANDREWSJD.Fault tree analysis and binary decision diagrams[C].ProceedingsAnnual Reliability andMaintainability Symposium，1996:215-222.

[6] TOWH IDIF，LASHKARIAH，HOSSEINIRS.Binary Decision Diagram(BDD)[C].International Conferenceon Future Computer and Communication，2009:496-499.

[7] CAIYao，LIU Zhengjiang，WU Zhaolin.Improvementof Fau ltTree Analysisin FormalSafety Assessment Using Binary Decision Diagram[C].1st International Conferenceon Information Science and Engineering，2009:4 330-4 333.

[8] MO Yuchang.New Insights Into the BDD-Based Reliability Analysis of Phased-Mission Systems[J].IEEE Transactions on Reliability，2009，58(4):667-678.

[9] DUSuguo，SUNYan.ANovelOrderingMethod of Binary Decision Diagram[C].2007 International Conference onManagementScience&Engineering(14th)，2007:299-304.

[10] 陶勇剑，董德存，任鹏.故障树分析的二元决策图方法[J].铁路计算机应用，2009，18(9):4-7.

[11] MO Yuchang.VariableOrdering to Improve BDDAnalysis of Phased-Mission SystemsWith Multimode Failures[J].IEEE Transactions on Reliability，2009，58(1):53-57.

[12] EBENDT R，DRECHSLERR.Approximate BDDMinimization byWeighted A[C].IEEE InternationalSymposium on Circuits and Systems，2009:2 974-2 977.

[13] MOEINZADEH H，MOHAMMADIM，Mehrbakhsh A.Evolutionary-Reduced Ordered Binary Decision Diagram[C].Third Asia International Conferenceon Modelling&Simulation，2009:142-145.

[14] BARTLETTLM，ANDREWS JD.An ordering heuristic to develop the binary decision diagram based on structure im portance[J].Reliability Engineering and System Safety，2001，72(3):31-38.

[15] GULATIR，DUGAN JB.A modular approach for analyzing static and dynamic fault trees[C].Proceedings Annual Reliability and Maintainability Symposium，1997:57-63.

[16] DUTUITY，RAUZY A.A linear-time algorithm to find modules of fault trees[J].IEEETransactions on Reliability，1996，45(3):422-425.