基于二元決策圖的故障樹底事件排序

黑新宏，張陽(yáng)陽(yáng)，錢富才，謝　國(guó)，何文娟

(1.西安理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，陜西 西安 710048；2.西安理工大學(xué) 自動(dòng)化與信息工程學(xué)院，陜西 西安 710048)

?

基于二元決策圖的故障樹底事件排序

黑新宏1，張陽(yáng)陽(yáng)1，錢富才2，謝國(guó)2，何文娟1

(1.西安理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，陜西 西安 710048；2.西安理工大學(xué) 自動(dòng)化與信息工程學(xué)院，陜西 西安 710048)

提出了一種底事件排序的新方法——最小深度子樹法。該方法先將結(jié)構(gòu)復(fù)雜的故障樹化簡(jiǎn)為一棵簡(jiǎn)單的樹，然后基于各子樹的深度、節(jié)點(diǎn)數(shù)及節(jié)點(diǎn)間的位置關(guān)系對(duì)底事件進(jìn)行靜態(tài)排序，并根據(jù)排序結(jié)果動(dòng)態(tài)構(gòu)造BDD。最后，通過(guò)對(duì)航空發(fā)動(dòng)機(jī)加速時(shí)喘振停車的故障樹分析，證明該方法可快速構(gòu)建BDD，而且構(gòu)建的BDD產(chǎn)生的冗余節(jié)點(diǎn)數(shù)目較少。

故障樹分析；二元決策圖；底事件排序

故障樹分析(Fault Tree Analysis,FTA)是用于處理大型復(fù)雜系統(tǒng)可靠性、安全性及風(fēng)險(xiǎn)評(píng)估的一種有效方法，在航空、航天、核能、化工等領(lǐng)域得到了廣泛應(yīng)用。傳統(tǒng)基于割集的故障樹分析[1]方法其時(shí)間及空間的復(fù)雜度較高且不易編程實(shí)現(xiàn)，而且在分析過(guò)程中會(huì)產(chǎn)生明顯的“組合爆炸”，因而難以勝任對(duì)大型復(fù)雜系統(tǒng)的分析。為解決這一問(wèn)題，Andrews提出了基于二元決策圖(Binary Decision Diagrams,BDD)的故障樹分析方法[2]，一次性實(shí)現(xiàn)割集的不交化。當(dāng)故障樹是最簡(jiǎn)割集BDD時(shí)，可以從不交化割集中直接析出最小割集[3]，避免了割集的不交化運(yùn)算和化簡(jiǎn)。另外，BDD方法在模型定量分析時(shí)不需要近似和刪減計(jì)算，在不能確定最小割集的情況下具有準(zhǔn)確進(jìn)行概率量化的可能性，能夠正確處理負(fù)面邏輯(成功分支)[4]，減小了分析計(jì)算時(shí)的時(shí)間和空間復(fù)雜度。

對(duì)于大型復(fù)雜系統(tǒng)的故障樹，可以利用BDD和計(jì)算機(jī)技術(shù)自動(dòng)地進(jìn)行分析與處理，但首先需要將故障樹轉(zhuǎn)換為BDD，然后再通過(guò)BDD對(duì)故障樹進(jìn)行定性與定量計(jì)算。而將故障樹轉(zhuǎn)換為BDD時(shí)，需要先對(duì)故障樹進(jìn)行預(yù)處理，即對(duì)其底事件進(jìn)行排序，底事件節(jié)點(diǎn)順序直接影響最后生成的BDD節(jié)點(diǎn)數(shù)量。因此，如何對(duì)故障樹的底事件排序，成為了利用BDD對(duì)故障樹進(jìn)行分析的一個(gè)難題[5]。

近年來(lái)，國(guó)際上許多學(xué)者對(duì)故障樹底事件排序進(jìn)行了大量研究，主要有從上向下、從左到右法[6]，深度優(yōu)先法[7]，事件重要度方法[8]，相鄰底事件優(yōu)先法[5]等等。但所有這些方法都只適用于一些簡(jiǎn)單的故障樹或者某種特定類型的故障樹，很難存在一種對(duì)所有類型的故障樹都有效的排序方法。

在對(duì)前人方法研究的基礎(chǔ)上，本文提出了一種新的底事件排序方法——最小深度子樹法。該方法是基于各子樹的深度、節(jié)點(diǎn)數(shù)以及底事件節(jié)點(diǎn)間的位置關(guān)系來(lái)為其排序，能夠在很大程度上減少構(gòu)造BDD時(shí)冗余節(jié)點(diǎn)的產(chǎn)生，靜態(tài)排序動(dòng)態(tài)構(gòu)造[9]。實(shí)例結(jié)果證明，利用該方法構(gòu)造的BDD，其節(jié)點(diǎn)數(shù)目大多少于現(xiàn)有的其它方法所構(gòu)造的BDD，而節(jié)點(diǎn)數(shù)量更少的BDD可有效提高對(duì)故障樹分析計(jì)算的性能。

1　BDD結(jié)構(gòu)

BDD是一有向無(wú)環(huán)圖，它主要由頂節(jié)點(diǎn)、中間節(jié)點(diǎn)、葉子節(jié)點(diǎn)及連接兩節(jié)點(diǎn)間的分支組成，其結(jié)構(gòu)如圖1所示。

圖1　BDD結(jié)構(gòu)圖Fig.1　BDD diagram

BDD中的頂節(jié)點(diǎn)(X1)和中間節(jié)點(diǎn)(X2、X3、X4)代表故障樹中的底事件，即系統(tǒng)中的基本事件，葉子節(jié)點(diǎn)(y、z)表示對(duì)應(yīng)故障樹頂事件的狀態(tài)。由圖1，頂節(jié)點(diǎn)和中間節(jié)點(diǎn)包含有1和0兩個(gè)分支，分別表示基本事件的發(fā)生和不發(fā)生；而葉子節(jié)點(diǎn)為1和0兩種狀態(tài)之一，用以表示頂事件的發(fā)生與否，即系統(tǒng)是否發(fā)生故障。

在構(gòu)造好BDD后，從頂節(jié)點(diǎn)開始遍歷該BDD，到達(dá)葉子節(jié)點(diǎn)時(shí)，若葉子節(jié)點(diǎn)的值為1，則其所在路徑上的所有非終結(jié)點(diǎn)的集合組成一個(gè)割集；若葉子節(jié)點(diǎn)的值為0，則向上繼續(xù)遍歷其它未被遍歷過(guò)的節(jié)點(diǎn)。當(dāng)整個(gè)BDD遍歷完成后，可找到所有值為1的葉子節(jié)點(diǎn)所在的路徑，即可得到BDD所對(duì)應(yīng)故障樹的所有最小割集。由此可知，圖1中BDD所對(duì)應(yīng)故障樹的最小割集為{X1,X2,X4}，{X3}。

與傳統(tǒng)方法相比，通過(guò)BDD技術(shù)求解的結(jié)果就是最小割集，不需進(jìn)行多次近似和刪減計(jì)算，可極大提高分析計(jì)算效率。而利用傳統(tǒng)基于割集的上行法[10]、下行法[10]、刪去留下法[11]等方法分析求解大規(guī)模故障樹時(shí)，在分析計(jì)算過(guò)程中會(huì)產(chǎn)生明顯的“組合爆炸”，且在求解最小割集時(shí)還需要進(jìn)行多次近似和刪減計(jì)算，造成了時(shí)間和空間復(fù)雜度的增加，降低了分析計(jì)算的效率。

2　最小深度子樹法

在現(xiàn)實(shí)中，一個(gè)大型復(fù)雜系統(tǒng)其各個(gè)子系統(tǒng)之間常常會(huì)受到大量重復(fù)事件的影響，即一個(gè)基本事件可能會(huì)出現(xiàn)在多個(gè)子系統(tǒng)中，若該事件發(fā)生故障，則可能會(huì)導(dǎo)致多個(gè)子系統(tǒng)失效，而這些重復(fù)事件對(duì)于故障樹的求解及從故障樹到BDD的轉(zhuǎn)換都帶來(lái)了諸多困難，所以在故障樹轉(zhuǎn)換為BDD之前，化簡(jiǎn)故障樹，刪除故障樹中的重復(fù)事件就變得非常必要。

同一個(gè)故障樹在轉(zhuǎn)換為BDD時(shí)，不同的底事件排序會(huì)得到不同的BDD，則遍歷該圖所消耗的時(shí)間和空間復(fù)雜度也會(huì)有所不同，其所對(duì)應(yīng)的定性、定量分析的效率也會(huì)不同。

本文提出的最小深度子樹法是基于子樹深度和節(jié)點(diǎn)數(shù)的排序方法，繼承了結(jié)構(gòu)式方法的特點(diǎn)，著重強(qiáng)調(diào)了樹的結(jié)構(gòu)特征及節(jié)點(diǎn)之間的相互關(guān)聯(lián)關(guān)系，減小了因故障樹畫法的不同而對(duì)構(gòu)造BDD的影響。

在本文提出的方法中，最重要的就是要減小重復(fù)事件對(duì)于構(gòu)造BDD的影響。首先根據(jù)故障樹的結(jié)構(gòu)特征，化簡(jiǎn)該故障樹，最大程度地刪除樹中的重復(fù)節(jié)點(diǎn)、冗余節(jié)點(diǎn)及中間節(jié)點(diǎn)，使樹結(jié)構(gòu)變得更加簡(jiǎn)單，然后再根據(jù)化簡(jiǎn)之后得到的故障樹，利用子樹深度及其所含節(jié)點(diǎn)個(gè)數(shù)對(duì)底事件進(jìn)行排序并構(gòu)造BDD。在構(gòu)造BDD時(shí)，文獻(xiàn)[9]介紹了漸進(jìn)式的排序方法。該方法基于靜態(tài)排序動(dòng)態(tài)構(gòu)造這一思想，即對(duì)于故障樹的所有底事件采用一定的規(guī)則排序，而在構(gòu)造BDD時(shí)，根據(jù)各個(gè)分支的不同特點(diǎn)采用不同的底事件順序，從而使得構(gòu)造的BDD節(jié)點(diǎn)數(shù)目極大減少。受此啟發(fā)，本文提出的方法也采用了靜態(tài)排序動(dòng)態(tài)構(gòu)造這一思想。

在對(duì)故障樹分析之前，根據(jù)圖2對(duì)下文中提到的父節(jié)點(diǎn)、子節(jié)點(diǎn)等名詞做一簡(jiǎn)單介紹。在該故障樹中T1為該樹的根節(jié)點(diǎn)，也稱為整棵樹的頂事件，同時(shí)T1是X1、X2和T2的父節(jié)點(diǎn)，X1、X2、T2為T1的子節(jié)點(diǎn)，X1、X2、T2互為兄弟節(jié)點(diǎn)，以T2為根節(jié)點(diǎn)的樹稱為以T1為根節(jié)點(diǎn)的樹的子樹。同理，X3、X4為T2的子節(jié)點(diǎn)，T2是它們的父節(jié)點(diǎn)，X3、X4互為兄弟節(jié)點(diǎn)。在該樹中節(jié)點(diǎn)X1、X2、X3、X4均無(wú)子節(jié)點(diǎn)，將其稱為整棵樹的底事件。

圖2　故障樹概念模型Fig.2　Fault Tree conceptual model

用本文提出的最小深度子樹法對(duì)故障樹分析時(shí)，可分為故障樹的化簡(jiǎn)、BDD排序以及構(gòu)造BDD三個(gè)階段。

2.1故障樹的化簡(jiǎn)

在對(duì)故障樹的底事件排序之前，首先對(duì)該樹進(jìn)行化簡(jiǎn)，刪除樹中與頂事件無(wú)關(guān)的節(jié)點(diǎn)事件。故障樹的化簡(jiǎn)大多基于吸收律(1)、(2)和冪等律(3)進(jìn)行。

(1)

(2)

(3)

具體化簡(jiǎn)步驟如下。

1)遍歷該故障樹，若在樹中子節(jié)點(diǎn)G2的邏輯門類型與其父節(jié)點(diǎn)G1的邏輯門類型相同，則可將G2節(jié)點(diǎn)下的所有子節(jié)點(diǎn)添加到節(jié)點(diǎn)G1中，使G2節(jié)點(diǎn)的子節(jié)點(diǎn)成為G1節(jié)點(diǎn)的子節(jié)點(diǎn)，并在故障樹中刪除以G2節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹，如圖3所示。

圖3　同門合并示例Fig.3　Example of combining the same gate

2)在整棵樹中，若以G1為根節(jié)點(diǎn)的子樹下只有一個(gè)子節(jié)點(diǎn)X1，則將X1節(jié)點(diǎn)添加到G1節(jié)點(diǎn)的父節(jié)點(diǎn)中，使其成為G1的父節(jié)點(diǎn)的子節(jié)點(diǎn)，刪除以G1為根節(jié)點(diǎn)的子樹，如圖4所示；若G1節(jié)點(diǎn)下只有一個(gè)以節(jié)點(diǎn)G2為根節(jié)點(diǎn)的子樹再無(wú)其它子節(jié)點(diǎn)，則將以G2為根節(jié)點(diǎn)的子樹添加到節(jié)點(diǎn)G1的父節(jié)點(diǎn)中，使其成為節(jié)點(diǎn)G1的父節(jié)點(diǎn)的一個(gè)子樹，刪除以G1為根節(jié)點(diǎn)的子樹，如圖5所示。

圖4　單個(gè)子節(jié)點(diǎn)化簡(jiǎn)示例Fig.4　Example of a single child node simplified

圖5　單個(gè)子樹化簡(jiǎn)示例Fig.5　Example of a single sub-tree simplified

3)利用冪等律和吸收律對(duì)步驟1)和2)處理后的故障樹再次化簡(jiǎn)，如圖3所示。

2.2BDD排序

在對(duì)故障樹化簡(jiǎn)后，即可利用以下規(guī)則對(duì)化簡(jiǎn)后的故障樹底事件進(jìn)行排序，其具體排序規(guī)則如下。

1)從故障樹的頂事件開始，遍歷整棵故障樹，統(tǒng)計(jì)樹中所有底事件重復(fù)出現(xiàn)次數(shù)。

2)從樹的根節(jié)點(diǎn)開始，計(jì)算以根節(jié)點(diǎn)的各個(gè)子節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹深度，首先，將所有子樹深度為1的節(jié)點(diǎn)即底事件節(jié)點(diǎn)在已經(jīng)排好的序列中查找，若該節(jié)點(diǎn)存在于已排好的序列中，則無(wú)需重復(fù)加入，若該節(jié)點(diǎn)尚未參與排序，則按其重復(fù)出現(xiàn)的次數(shù)，重復(fù)出現(xiàn)次數(shù)多者優(yōu)先加入到已排好的序列中；其次，將所有深度非1的子樹，按其深度由小到大排序，并依次重復(fù)規(guī)則2)。

3)若以同一父節(jié)點(diǎn)下的兩個(gè)子節(jié)點(diǎn)為根節(jié)點(diǎn)的兩棵子樹的深度相同，則子樹中所含底事件節(jié)點(diǎn)數(shù)目少者優(yōu)先參與排列，如果底事件節(jié)點(diǎn)數(shù)目相同，則按從左向右的順序依次重復(fù)規(guī)則2)。

4)在同一顆子樹中，對(duì)其所有底事件節(jié)點(diǎn)按其重復(fù)出現(xiàn)次數(shù)排序，重復(fù)出現(xiàn)次數(shù)多者優(yōu)先排列，若重復(fù)出現(xiàn)次數(shù)相同，則按從上向下、從左向右的順序排序。

當(dāng)整棵樹中的所有底事件都參與排序后，最后即可得到底事件的有序的集合A1，A2，…，An。在得到底事件的有序集合的過(guò)程中，對(duì)每個(gè)節(jié)點(diǎn)的訪問(wèn)操作都進(jìn)行了兩遍，該算法的復(fù)雜度是線性O(shè)(n)。

2.3構(gòu)造BDD

當(dāng)排序結(jié)束得到有序集合A1，A2，…，An后，則需通過(guò)該序列集合和化簡(jiǎn)后的故障樹邏輯結(jié)構(gòu)來(lái)構(gòu)造BDD。根據(jù)得到的序列集合，依次取得該序列集合中的節(jié)點(diǎn)，并對(duì)所取得的節(jié)點(diǎn)依據(jù)故障樹的邏輯結(jié)構(gòu)做邏輯運(yùn)算。因?yàn)樵谂判蜻^(guò)程中，一個(gè)父節(jié)點(diǎn)其所有的子節(jié)點(diǎn)的順序是相鄰的，所以有以下結(jié)論。

1)若節(jié)點(diǎn)所代表的事件發(fā)生：如果該節(jié)點(diǎn)的父節(jié)點(diǎn)的邏輯門為“與”門，則需對(duì)該節(jié)點(diǎn)的其它兄弟節(jié)點(diǎn)做邏輯運(yùn)算；如果該節(jié)點(diǎn)的父節(jié)點(diǎn)的邏輯門為“或”門，則無(wú)需對(duì)該節(jié)點(diǎn)的其它兄弟節(jié)點(diǎn)做邏輯運(yùn)算。

2)若節(jié)點(diǎn)所代表的事件沒(méi)有發(fā)生：如果該節(jié)點(diǎn)的父節(jié)點(diǎn)的邏輯門為“與”門，則無(wú)需對(duì)該節(jié)點(diǎn)的其它兄弟節(jié)點(diǎn)做邏輯運(yùn)算；如果該節(jié)點(diǎn)的父節(jié)點(diǎn)的邏輯門為“或”門，則需對(duì)該節(jié)點(diǎn)的其它兄弟節(jié)點(diǎn)做邏輯運(yùn)算。

以上對(duì)本文提出的最小深度子樹法做了詳細(xì)的闡述，即每次首先對(duì)深度最小的子樹中的節(jié)點(diǎn)排序，若子樹深度相同，則先對(duì)所含節(jié)點(diǎn)數(shù)目少的排序。利用該方法分析故障樹時(shí)，對(duì)原始故障樹進(jìn)行化簡(jiǎn)，刪除樹中的冗余節(jié)點(diǎn)，可以提高對(duì)底事件排序的效率。在構(gòu)造BDD時(shí)采用動(dòng)態(tài)構(gòu)造的方法，極大減少了BDD中冗余節(jié)點(diǎn)的產(chǎn)生，簡(jiǎn)化了所構(gòu)造BDD的結(jié)構(gòu)，因而該方法不僅在某些方面提高了分析計(jì)算的效率，同時(shí)也易于用軟件實(shí)現(xiàn)。

2.4軟件實(shí)現(xiàn)流程

為了驗(yàn)證該方法的可行性與可編程實(shí)現(xiàn)性，對(duì)該方法做了深入研究，并以Microsoft Visual Studio 2010為平臺(tái)，以C#為主要編程語(yǔ)言，利用該方法編寫了一個(gè)故障樹軟件，該算法在軟件中的具體流程描述如圖6所示。

圖6　計(jì)算機(jī)排序流程圖Fig.6　The flow chart of the computer sorting

利用該方法編寫的軟件可以非常方便地將一個(gè)復(fù)雜系統(tǒng)的故障樹化簡(jiǎn)為一簡(jiǎn)單的樹，通過(guò)化簡(jiǎn)得到的新故障樹很容易實(shí)現(xiàn)對(duì)底事件的排序以及構(gòu)造BDD。

為了驗(yàn)證該方法的高效性，本文選取了31棵各種類型的故障樹，如子節(jié)點(diǎn)和父節(jié)點(diǎn)的邏輯門不相同但樹中有重復(fù)節(jié)點(diǎn)、子節(jié)點(diǎn)和父節(jié)點(diǎn)的邏輯門相同但樹中無(wú)重復(fù)節(jié)點(diǎn)等等，與用相鄰底事件優(yōu)先法[5]構(gòu)造的BDD做了對(duì)比。

通過(guò)大量試?yán)治?，可以清晰地看到本文所提方法的?yōu)勢(shì)，即在排序之前盡可能地刪除了樹中的冗余節(jié)點(diǎn)，使得排序過(guò)程中極大地避免了重復(fù)節(jié)點(diǎn)的影響，構(gòu)造的BDD在很大程度上減少了冗余節(jié)點(diǎn)的出現(xiàn)，并且結(jié)構(gòu)簡(jiǎn)單。

通過(guò)兩種方法構(gòu)造的BDD節(jié)點(diǎn)數(shù)目對(duì)比統(tǒng)計(jì)值如表1所示。

表1　BDD節(jié)點(diǎn)數(shù)目對(duì)比統(tǒng)計(jì)值

通過(guò)表1也可清晰直觀地看到，在對(duì)31棵各種類型的故障樹分別使用兩種方法構(gòu)造BDD后，使用最小深度子樹法構(gòu)造的BDD中有80.6%的BDD所含節(jié)點(diǎn)數(shù)少于或等于相鄰底事件優(yōu)先法構(gòu)造的BDD。同時(shí)通過(guò)軟件的自動(dòng)化處理使得本文中提出的新方法不管是對(duì)底事件進(jìn)行排序還是構(gòu)造BDD，相比以前的方法在效率上都有了很大提升。

3　實(shí)例分析

為更加直觀清晰地理解這一方法，以航空發(fā)動(dòng)機(jī)WP7主燃油系統(tǒng)的子系統(tǒng)——加速調(diào)節(jié)系統(tǒng)中的加速時(shí)喘振停車[12]為例，說(shuō)明本文所提方法的應(yīng)用。

為方便建立故障樹，將基本事件進(jìn)行了編碼，如表2所示。

表2　加速時(shí)喘振停車故障事件

加速時(shí)喘振停車Top是由模塊B1升壓限制器控制的加速時(shí)間短或B2延遲控制器的加速時(shí)間短引起的。其中：

1)模塊B1的失效是由B3、B4、B5、X1、X2其中任意一個(gè)的失效而引發(fā)；

2)模塊B3是因B7和B8的共同失效而失效的，而B7的失效是由X6或X7的失效造成的，B8的失效是由X4或X5的失效引發(fā)的；

3)X4和X5的共同失效造成了B4的失效；

4)B5的失效是由于X6、X7、B9中的某一個(gè)發(fā)生失效而引起的，而B9是由于X6和X7的共同失效而引發(fā)的；

5)模塊B2的失效是由X3、X1、B6中任意一個(gè)的失效引發(fā)的，而B6的失效是由于X8或X9的失效而造成的。

基于以上分析，建立了圖7航空發(fā)動(dòng)機(jī)加速時(shí)喘振停車的故障樹。

圖7　加速時(shí)喘振停車故障樹Fig.7　Fault tree of accelerating surge parking

1)故障樹的化簡(jiǎn)

① 在故障樹中，由于頂事件Top與其子節(jié)點(diǎn)B1、B2的邏輯門均相同為“或門”，所以可將B1子樹、B2子樹下的子節(jié)點(diǎn)添加到頂事件Top的子節(jié)點(diǎn)中，同時(shí)刪除中間節(jié)點(diǎn)B1、B2及其邏輯門；

② 經(jīng)過(guò)①處理后，以B5為根節(jié)點(diǎn)的樹和以B6為根節(jié)點(diǎn)的樹成為了根節(jié)點(diǎn)Top的子樹，而節(jié)點(diǎn)B5和B6的邏輯門與其父節(jié)點(diǎn)Top的邏輯門相同，所以對(duì)其做與①相同的處理，并刪除中間節(jié)點(diǎn)B5、B6及其邏輯門；

③ 相同邏輯門合并后，以B9為根節(jié)點(diǎn)的樹成為了根節(jié)點(diǎn)Top的子樹，而節(jié)點(diǎn)B9的孩子節(jié)點(diǎn)與B9的兄弟節(jié)點(diǎn)有若干個(gè)是相同的，所以利用吸收律運(yùn)算，可以刪除以B9為根節(jié)點(diǎn)的子樹。

化簡(jiǎn)時(shí)最大程度地刪除了樹中的重復(fù)節(jié)點(diǎn)和冗余節(jié)點(diǎn)，使得化簡(jiǎn)后的樹更加精煉，求解更加快速，在經(jīng)過(guò)化簡(jiǎn)后，得到與原故障樹相等價(jià)的新的故障樹，如圖8所示。

圖8　化簡(jiǎn)后的加速時(shí)喘振停車故障樹Fig.8　Fault tree of accelerating surge parking after simplification

2)對(duì)化簡(jiǎn)后的故障樹底事件排序

① 在化簡(jiǎn)后的這棵新故障樹中，從根節(jié)點(diǎn)Top開始遍歷整棵故障樹，計(jì)算出樹中各底事件重復(fù)出現(xiàn)次數(shù)recount，其中節(jié)點(diǎn)X4、X5、X6、X7出現(xiàn)次數(shù)均為2，其它節(jié)點(diǎn)均為1。

② 從樹根節(jié)點(diǎn)Top開始，計(jì)算以根節(jié)點(diǎn)的子節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹深度，得到結(jié)果為以B3節(jié)點(diǎn)為根的子樹深度為3，以B4節(jié)點(diǎn)為根的子樹深度為2，其余節(jié)點(diǎn)均為底事件節(jié)點(diǎn)，其深度為1。首先對(duì)深度為1的底事件節(jié)點(diǎn)按重復(fù)出現(xiàn)次數(shù)由大到小排序，若重復(fù)出現(xiàn)次數(shù)相同，則按從左向右的順序排序。所以對(duì)這七個(gè)底事件節(jié)點(diǎn)排序結(jié)果為A1(X6

③ 按子樹深度，由小到大對(duì)其子節(jié)點(diǎn)排序，所以先對(duì)子樹B4中的子節(jié)點(diǎn)排序。子樹B4中含有X4和X5兩個(gè)底事件且重復(fù)出現(xiàn)次數(shù)均為2，所以按從左到右排序?yàn)锳2(X4

④ 在經(jīng)過(guò)③處理后，只剩下以節(jié)點(diǎn)B3為根節(jié)點(diǎn)的子樹，經(jīng)遍歷可知該子樹中的底事件均已參加排序，所以無(wú)需再次對(duì)其排序。

至此整棵樹中的所有底事件節(jié)點(diǎn)均已參與排序，根據(jù)排序結(jié)果構(gòu)造BDD，得到如圖9所示的BDD。

圖9　根據(jù)排序結(jié)果構(gòu)造的BDDFig.9　BDD structure based on the sorting results

由遍歷構(gòu)造出的BDD可以很容易地得到對(duì)應(yīng)故障樹的最小割集為：{X6}，{X7}，{X1}，{X2}，{X3}，{X8}，{X9}，{X4,X5 }共8個(gè)。

4　結(jié)　語(yǔ)

本文提出了一種對(duì)故障樹底事件排序的新方法——最小深度子樹法，利用該方法能夠快速高效地將故障樹轉(zhuǎn)換為BDD。該方法主要是將一棵子樹作為一個(gè)整體進(jìn)行分析，在簡(jiǎn)化原故障樹的基礎(chǔ)上利用子樹中節(jié)點(diǎn)間的相互關(guān)系進(jìn)行排序，然后再構(gòu)造BDD。該方法在故障樹的化簡(jiǎn)過(guò)程中，針對(duì)不能將整棵樹中的所有冗余重復(fù)節(jié)點(diǎn)都刪除掉的問(wèn)題，可以從重復(fù)節(jié)點(diǎn)位置逐層向上，找到包含所有相同重復(fù)節(jié)點(diǎn)的最小子樹，可以通過(guò)在子樹中提取該重復(fù)節(jié)點(diǎn)，重新構(gòu)造該子樹的方法予以解決。

[1]郭永基.可靠性工程原理[M].北京:清華大學(xué)出版社,2002:60-82.

[2]KAREN A R，ANDREWS J D.A fault tree analysis strategy using binary decision diagrams [J].Reliability Engineering and System Safety,2002,78(1):45-56.

[3]周斌,黃元亮,黃威.基于模塊化分解的故障樹分析方法[J].計(jì)算機(jī)工程,2015,14(2):141-144.

ZHOU Bin,HUANG Yuanliang,HUANG Wei.Fault tree analysis method based on modular decomposition[J].Computer Engineering,2015,14(2):141-144.

[4]IBANEZ-LLANO C,RAUZY A,MELENDEZ E,et al.A reduction approach to improve the quantification of linked fault trees through binary decision diagrams[J].Reliability Engineering and System Safety,2010,95:1314-1323.

[5]孫艷,杜素果.一種二元決策圖底事件排序的新方法[J].系統(tǒng)管理學(xué)報(bào),2008,17(2):210-216.

SUN Yan,DU Suguo.A novel ordering method of binary decision diagram[J].Journal of Systems and Management,2008,17(2):210-216.

[6]SINNAMON R M,ANDREWS J D.New approaches to evaluating fault trees[J].Quality and Reliability Engineering International,1997,58(2):89-96.

[7]RAUZY A.New algorithms for fault tree analysis[J].Reliability Engineering and System Safety,1993,40(3):203-211.

[8]BARTLETT L M,ANDREWS J D.An ordering heuristic to develop the binary decision diagram based on structural importance[J].Reliability Engineering and System Safety,2001,72(1):31-38.

[9]BARTLETT L M,Du S.New progressive variable ordering for binary decision diagram analysis of fault trees[J].Quality and Reliability Engineering International,2005,21(4):413-425.

[10]徐宗昌.保障性工程[M ].北京:兵器工業(yè)出版社,2002.

[11]邢冀.復(fù)雜事故樹定性與定量分析算法研究與應(yīng)用[D].昆明:昆明理工大學(xué),2009:22-36.

XING Ji.Complex fault tree qualitative and quantitative analysis of the algorithm research and application[D].Kunming:Kunming University of Technology,2009:22-36.

[12]鄧明,金業(yè)壯.航空發(fā)動(dòng)機(jī)故障診斷[M].北京:北京航空航天大學(xué)出版社,2012:187-191.

[13]苗祚雨,牛儒,唐濤.基于二元決策圖的故障樹最小割集求解算法研究[J].中北大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,35(2):141-146.

MIAO Zuoyu,NIU Ru,TANG Tao.Research on fault tree minimal cut set generation algorithm based on binary decision diagram[J].Journal of North University of China(Natural Science Edition),2014,35(2):141-146.

(責(zé)任編輯王衛(wèi)勛)

Variable ordering in fault tree analysis based on binary decision diagrams

HEI Xinhong1，ZHANG Yangyang1，QIAN Fucai2，XIE Guo2，HE Wenjuan1

(1.School of Computer Science and Engineering,Xi’an University of Technology,Xi’an 710048，China;2.School of Automation and Information Engineering,Xi’an University of Technology,Xi’an 710048,China)

In this paper,a novel ordering method,namely the minimum depth of the sub-tree method,is proposed.This method reduces a complex fault tree to be a simple tree,and then makes static variable ordering based on the sub-tree's depth,node numbers and the positional relationship between the nodes,and finally dynamically construct a BDD according to the sorting result.In the end,the aviation engine acceleration surge parking fault tree shows that this method can quickly build a BDD,and the BDD has less redundant nodes.

fault tree analysis (FTA); binary decision diagram (BDD); variable ordering heuristics

10.19322/j.cnki.issn.1006-4710.2016.01.005

2015-04-23

國(guó)家自然科學(xué)基金資助項(xiàng)目(61273127，U1334211，U1534208)；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(20116118110008)

張陽(yáng)陽(yáng)，男，碩士生，研究方向?yàn)榭煽啃苑治觥-mail：1005763271@qq.com

黑新宏，男，博士，教授，研究方向?yàn)榘踩P(guān)鍵計(jì)算機(jī)系統(tǒng)、嵌入式系統(tǒng)及應(yīng)用。E-mail：heixinhong@xaut.edu.cn

TP206.3

A

1006-4710(2016)01-0023-07