基于二元決策圖的系統(tǒng)可靠性模塊分析方法

涂序躍

(華東交通大學(xué)軌道交通學(xué)院，江西南昌330013)

故障樹分析[1-2](fault tree analysis，F(xiàn)TA)是一種廣泛應(yīng)用的系統(tǒng)可靠性建模方法。傳統(tǒng)故障樹分析方法隨著系統(tǒng)元件數(shù)增多，最小割集數(shù)會(huì)呈指數(shù)關(guān)系增加，容易產(chǎn)生實(shí)踐中常見的“組合爆炸”問(wèn)題。采用二元決策圖(Binary Decision Diagram，BDD)方法對(duì)故障樹進(jìn)行分析[3-8]，可以簡(jiǎn)化系統(tǒng)可靠性定性、定量的求解過(guò)程。但是，BDD方法分析故障樹亦有不足，即故障樹向BDD的轉(zhuǎn)化受到基本事件排序的影響[3-5]。所以，為使BDD方法有效分析系統(tǒng)可靠性，需找出最優(yōu)的基本事件排序方法，使所得BDD結(jié)構(gòu)最小。可是，至今為止仍沒(méi)有一種普遍適用的最優(yōu)基本事件排序方法，這就給BDD方法求解大型、復(fù)雜系統(tǒng)的可靠性造成困難。針對(duì)BDD方法存在的不足，本文提出了一種基于BDD的模塊方法對(duì)系統(tǒng)可靠性進(jìn)行分析，基本研究思路如下:先把系統(tǒng)故障樹分解成相互獨(dú)立的模塊;其次采用BDD方法對(duì)其進(jìn)行分析;最后向上遞歸綜合模塊的求解結(jié)果，得到整個(gè)系統(tǒng)的可靠性。

1 基于BDD的系統(tǒng)可靠性模塊分析方法

1.1 基于二元決策圖(BDD)的故障樹分析方法

1.1.1 二元決策圖

二元決策圖本質(zhì)是布爾邏輯函數(shù)的圖形表示，即用有向無(wú)環(huán)的二叉樹圖來(lái)表示布爾邏輯函數(shù)[3](如圖1所示)。二元決策圖包括終結(jié)點(diǎn)和非終結(jié)點(diǎn)，結(jié)點(diǎn)間通過(guò)‘1'分支或‘0'分支連接。二元決策圖中每條路徑始于根結(jié)點(diǎn)，終于終結(jié)點(diǎn)，終結(jié)點(diǎn)的‘1'狀態(tài)指系統(tǒng)失效，‘0'狀態(tài)指系統(tǒng)工作[10]。

二元決策圖采用不交化形式表示系統(tǒng)失效邏輯函數(shù)Top。圖2所示的系統(tǒng)失效邏輯函數(shù)為:

圖1 BDD示例

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

遍歷圖2所示的二元決策圖，搜索從根結(jié)點(diǎn)到‘1'終結(jié)點(diǎn)的所有路徑，并保留路徑中沿‘1'分支發(fā)展的非終結(jié)點(diǎn)，則由這些保留的非終結(jié)點(diǎn)組成的一個(gè)集合就是系統(tǒng)的割集。因此，遍歷圖2所示的二元決策圖得到三個(gè)割集可得:{X1}、{X2，X3}、{X2，X4}。

因?yàn)槎獩Q策圖中所有路徑相互排斥，故相應(yīng)故障樹頂事件失效概率表示為

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

1.1.2 故障樹向BDD的轉(zhuǎn)化方法及基本事件的排序

故障樹轉(zhuǎn)化成二元決策圖普遍采用if-then-else(ite)規(guī)則[4]。該規(guī)則由故障樹最底層基本事件開始進(jìn)行ite結(jié)構(gòu)轉(zhuǎn)化，消除最底層的邏輯門;然后逐層向上進(jìn)行ite結(jié)構(gòu)轉(zhuǎn)化，直至故障樹頂事件，消除故障樹所有邏輯門，得到相應(yīng)的二元決策圖。

采用if-then-else規(guī)則將故障樹轉(zhuǎn)化成二元決策圖的過(guò)程中，必須先確定基本事件的順序。令F、G分別表示二元決策圖中的兩個(gè)節(jié)點(diǎn)，其中F=ite(X，f1，f2)，G=ite(Y，g1，g2)，X、Y是故障樹的基本事件，如果X的排序在Y的前面，即X＜Y，則

如果X與Y的排序相同，即X=Y，則

圖2 故障樹轉(zhuǎn)化成BDD范例(變量排序:X1＜X2＜X3＜X4)

式(3)、(4)中，＜o(jì)p＞對(duì)應(yīng)為故障樹中門的類型(AND或OR)的布爾算子，f1，f2，g1，g2分別為故障樹的布爾變量。

由ite結(jié)構(gòu)轉(zhuǎn)化規(guī)則可知，二元決策圖的結(jié)構(gòu)大小受基本事件排序影響。不同的基本事件排序，得到不同大小的二元決策圖[9-12]。以非終節(jié)點(diǎn)數(shù)作為衡量二元決策圖結(jié)構(gòu)大小的標(biāo)準(zhǔn)，二元決策圖結(jié)構(gòu)越小(非終節(jié)點(diǎn)數(shù)越少)，則二元決策圖技術(shù)較之傳統(tǒng)故障樹分析越具有優(yōu)越性。在已有研究成果的基礎(chǔ)上，本文提出下述3條基本事件排序的基本規(guī)則[13-14];

規(guī)則1 根據(jù)從上至下的原則確定基本事件排序，即基本事件在故障樹中的層次越高，排序越前;

規(guī)則2 根據(jù)基本事件重復(fù)次數(shù)確定基本事件排序，即基本事件在故障樹中重復(fù)出現(xiàn)越多，排序越前;

規(guī)則3 故障樹中相同層次、且沒(méi)有重復(fù)的基本事件從左至右排序。

1.2 故障樹的模塊分解

故障樹模塊就是相互獨(dú)立的子故障樹，是故障樹中至少兩個(gè)底事件的集合，向上可到達(dá)同一邏輯門，而且必須通過(guò)此邏輯門才能到達(dá)故障樹頂事件，該邏輯門稱為模塊輸出或模塊頂點(diǎn)，故障樹的所有其它底事件向上均不能到達(dá)該邏輯門[15]。模塊不能有來(lái)自故障樹其余部分的輸入，而且不能有與故障樹其余部分重復(fù)的事件。

模塊分解就是把系統(tǒng)故障樹分解成相互獨(dú)立的模塊(故障子樹)。本文采用線性時(shí)間算法[16]來(lái)確定系統(tǒng)故障樹的模塊。線性時(shí)間算法基本原則敘述如下:對(duì)系統(tǒng)故障樹進(jìn)行深度優(yōu)先，從左至右遍歷;假定V是一非根結(jié)點(diǎn)，t1，t2分別對(duì)應(yīng)結(jié)點(diǎn)V第一次和第二次的訪問(wèn)時(shí)間，如果結(jié)點(diǎn)V的后代結(jié)點(diǎn)不會(huì)早于t1被訪問(wèn)，也不會(huì)晚于t2被訪問(wèn)，則以結(jié)點(diǎn)V為頂事件的故障子樹是一個(gè)模塊。

線性時(shí)間算法確定系統(tǒng)故障樹模塊時(shí)，需要注意兩點(diǎn):(1)每個(gè)非根結(jié)點(diǎn)至少被訪問(wèn)兩次，第一次是由其父結(jié)點(diǎn)朝下遍歷，第二次是由其最右子結(jié)點(diǎn)朝上遍歷;(2)以任一非根結(jié)點(diǎn)為頂事件的故障子樹不會(huì)遍歷兩次[11]。

1.3 基于模塊方法的故障樹分析

1.3.1 基于模塊方法的故障樹定性分析

基于模塊的故障樹定性分析實(shí)質(zhì)是一個(gè)自下而上的遞歸綜合求解過(guò)程。先分析最底層故障樹模塊(該模塊只包含基本事件)，采用BDD方法求出該模塊的所有最小割集和發(fā)生概率;然后將其用基本事件代替，該基本事件故障發(fā)生概率等于模塊故障發(fā)生概率。對(duì)最底層模塊被取代后的故障樹再進(jìn)行模塊分析，分析新故障樹最底層模塊，同樣用基本事件將其代替。分析過(guò)程遞歸進(jìn)行，直至整個(gè)故障樹分析完成。

基于模塊方法的故障樹定性分析依據(jù)上述原理，具體步驟為:

(1)采用BDD方法求出故障樹所有最底層模塊的最小割集，將這些模塊用相同故障發(fā)生概率的基本事件代替，得到新的故障樹;

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

(3)遞歸向上執(zhí)行相同分析過(guò)程，直至求出原故障樹的所有最小割集，這些最小割集中只包含原故障樹的基本事件。

1.3.2 基于模塊方法的故障樹定量分析

基于模塊方法的故障樹定量分析與定性分析原理相同，采用BDD方法求出故障樹最底層模塊的故障發(fā)生概率，用具有相同故障發(fā)生概率的基本事件代替最底層模塊，得到新的故障樹。對(duì)新故障樹進(jìn)行相同分析，求出新故障樹的最底層模塊，用具有相同故障發(fā)生概率的基本事件代替最底層模塊，遞歸重復(fù)該過(guò)程，直至整個(gè)故障樹分析完成。

基于模塊方法的故障樹定量分析具體步驟為:

(1)采用BDD方法求出故障樹所有最底層模塊的故障發(fā)生概率，將這些模塊用相同故障發(fā)生概率的基本事件代替，得到新的故障樹;

(2)采用BDD求出新故障樹所有最底層模塊的故障發(fā)生概率，將這些模塊用相同故障發(fā)生概率的基本事件代替，得到新的故障樹;

(3)遞歸向上執(zhí)行相同分析過(guò)程，直至求出原故障樹頂事件發(fā)生概率。

2 分析實(shí)例

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

所得QM即為故障樹頂事件失效概率。

模塊分析方法求解系統(tǒng)故障樹最小割集如表1所示。模塊M，即系統(tǒng)故障樹的最小割集為:{M1}、{M 2}、{e7}、{e11}、{e1}。{M 1}、{M 2}分別用其子模塊的最小割集代替，得到系統(tǒng)故障樹所有最小割集為

下面以文獻(xiàn)[9]中所示故障樹為例，詳細(xì)闡述基于二元決策圖的系統(tǒng)可靠性模塊分析方法。圖3是來(lái)自文獻(xiàn)[9]的故障樹范例，采用線性時(shí)間算法[16]對(duì)其進(jìn)行模塊分解，模塊分解結(jié)果如圖4所示。整個(gè)故障樹作為一個(gè)最大的模塊M，其中又包括兩個(gè)相互獨(dú)立的子模塊M 1、M 2。

采用二元決策圖方法對(duì)所有模塊進(jìn)行可靠性分析，故障樹基本事件排序?yàn)?e7＜e11＜e1＜e15＜e0＜e8＜e4＜e3＜e12＜e10，模塊M 1、M 2、M對(duì)應(yīng)的BDD如圖5所示。先求出模塊M 1、M 2頂事件失效概率，用相同概率的同名基本事件代替構(gòu)成新的故障樹，并轉(zhuǎn)化成相應(yīng)的BDD。

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

圖3 故障樹范例

圖4 故障樹模塊分解

圖5 模塊對(duì)應(yīng)的二元決策圖(基本事件排序:e7＜e11＜e15＜e8＜e4＜e3＜e12＜e10)

表1 故障樹最小割集列表

基于BDD的系統(tǒng)可靠性模塊分析實(shí)例表明:該方法在定量分析中，求解系統(tǒng)故障樹頂事件失效概率更簡(jiǎn)單;定性分析過(guò)程中，僅得到所有最小割集，沒(méi)有任何非最小割集，免除了BDD方法分析整個(gè)故障樹易產(chǎn)生非最小割集問(wèn)題。

3 結(jié)論

基于BDD的系統(tǒng)可靠性模塊分析方法，采用線性時(shí)間算法將系統(tǒng)故障樹分解成相互獨(dú)立的模塊，分別求出各模塊頂事件發(fā)生概率，然后遞歸綜合求解出系統(tǒng)故障樹頂事件的失效概率。模塊分析方法在定性、定量分析大型、復(fù)雜系統(tǒng)的可靠性過(guò)程中，避免了最小割集不交化求和的繁瑣過(guò)程，又可簡(jiǎn)單、明了的直接得出所有最小割集。相比傳統(tǒng)故障樹分析方法和采用BDD方法直接分析整個(gè)系統(tǒng)故障樹，模塊方法具有明顯優(yōu)越性，適用于大型、復(fù)雜系統(tǒng)可靠性分析。

[1] 曾聲奎.系統(tǒng)可靠性設(shè)計(jì)分析教程[M].北京:北京航空航天大學(xué)出版社，2001:117-144.

[2] 李海泉，李剛.系統(tǒng)可靠性分析與設(shè)計(jì)[M].北京:科學(xué)出版社，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].鐵路計(jì)算機(jī)應(yīng)用，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.