黑新宏，張陽陽，錢富才，謝　國，何文娟

(1.西安理工大學 計算機科學與工程學院，陜西 西安 710048；2.西安理工大學 自動化與信息工程學院，陜西 西安 710048)

?

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

黑新宏1，張陽陽1，錢富才2，謝國2，何文娟1

(1.西安理工大學 計算機科學與工程學院，陜西 西安 710048；2.西安理工大學 自動化與信息工程學院，陜西 西安 710048)

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

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

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

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

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

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

1　BDD結構

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

圖1　BDD結構圖Fig.1　BDD diagram

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

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

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

2　最小深度子樹法

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

同一個故障樹在轉換為BDD時，不同的底事件排序會得到不同的BDD，則遍歷該圖所消耗的時間和空間復雜度也會有所不同，其所對應的定性、定量分析的效率也會不同。

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

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

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

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

用本文提出的最小深度子樹法對故障樹分析時，可分為故障樹的化簡、BDD排序以及構造BDD三個階段。

2.1故障樹的化簡

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

(1)

(2)

(3)

具體化簡步驟如下。

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

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

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

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

圖5　單個子樹化簡示例Fig.5　Example of a single sub-tree simplified

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

2.2BDD排序

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

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

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

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

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

當整棵樹中的所有底事件都參與排序后，最后即可得到底事件的有序的集合A1，A2，…，An。在得到底事件的有序集合的過程中，對每個節(jié)點的訪問操作都進行了兩遍，該算法的復雜度是線性O(n)。

2.3構造BDD

當排序結束得到有序集合A1，A2，…，An后，則需通過該序列集合和化簡后的故障樹邏輯結構來構造BDD。根據得到的序列集合，依次取得該序列集合中的節(jié)點，并對所取得的節(jié)點依據故障樹的邏輯結構做邏輯運算。因為在排序過程中，一個父節(jié)點其所有的子節(jié)點的順序是相鄰的，所以有以下結論。

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

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

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

2.4軟件實現流程

為了驗證該方法的可行性與可編程實現性，對該方法做了深入研究，并以Microsoft Visual Studio 2010為平臺，以C#為主要編程語言，利用該方法編寫了一個故障樹軟件，該算法在軟件中的具體流程描述如圖6所示。

圖6　計算機排序流程圖Fig.6　The flow chart of the computer sorting

利用該方法編寫的軟件可以非常方便地將一個復雜系統(tǒng)的故障樹化簡為一簡單的樹，通過化簡得到的新故障樹很容易實現對底事件的排序以及構造BDD。

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

通過大量試例分析，可以清晰地看到本文所提方法的優(yōu)勢，即在排序之前盡可能地刪除了樹中的冗余節(jié)點，使得排序過程中極大地避免了重復節(jié)點的影響，構造的BDD在很大程度上減少了冗余節(jié)點的出現，并且結構簡單。

通過兩種方法構造的BDD節(jié)點數目對比統(tǒng)計值如表1所示。

表1　BDD節(jié)點數目對比統(tǒng)計值

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

3　實例分析

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

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

表2　加速時喘振停車故障事件

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

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

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

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

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

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

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

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

1)故障樹的化簡

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

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

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

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

圖8　化簡后的加速時喘振停車故障樹Fig.8　Fault tree of accelerating surge parking after simplification

2)對化簡后的故障樹底事件排序

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

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

③ 按子樹深度，由小到大對其子節(jié)點排序，所以先對子樹B4中的子節(jié)點排序。子樹B4中含有X4和X5兩個底事件且重復出現次數均為2，所以按從左到右排序為A2(X4

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

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

圖9　根據排序結果構造的BDDFig.9　BDD structure based on the sorting results

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

4　結　語

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

[1]郭永基.可靠性工程原理[M].北京:清華大學出版社,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].計算機工程,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)管理學報,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]邢冀.復雜事故樹定性與定量分析算法研究與應用[D].昆明:昆明理工大學,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ā)動機故障診斷[M].北京:北京航空航天大學出版社,2012:187-191.

[13]苗祚雨,牛儒,唐濤.基于二元決策圖的故障樹最小割集求解算法研究[J].中北大學學報(自然科學版),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.

(責任編輯王衛(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

國家自然科學基金資助項目(61273127，U1334211，U1534208)；高等學校博士學科點專項科研基金資助項目(20116118110008)

張陽陽，男，碩士生，研究方向為可靠性分析。E-mail：1005763271@qq.com

黑新宏，男，博士，教授，研究方向為安全關鍵計算機系統(tǒng)、嵌入式系統(tǒng)及應用。E-mail：heixinhong@xaut.edu.cn

TP206.3

A

1006-4710(2016)01-0023-07