羅 航，王厚軍，黃建國(guó)，龍 兵

(1. 四川大學(xué)測(cè)量控制系 成都 610065; 2. 電子科技大學(xué)自動(dòng)化工程學(xué)院 成都 611731)

故障樹分析(fault tree analysis, FTA)方法在宇航、核能、電子電力系統(tǒng)等領(lǐng)域中已成為評(píng)價(jià)可靠性和安全性的重要手段[1-5]。早期的Fussell-Vesely算法[6]和Semanderes算法[7]都可以采用布爾吸收策略來(lái)得到頂事件的最小割集(minimum cut set, MCS)，這在故障樹定性分析方面是可行和有效的。然而，要對(duì)故障樹進(jìn)行定量分析，則必須首先對(duì)頂事件的MCS進(jìn)行不交化處理。但是，對(duì)MCS進(jìn)行不交化處理的容斥定理是一個(gè)“NP”困難問題[2]，其主要原因是不同割集中的相同底事件(這樣的割集不能被吸收)在頂事件的交并運(yùn)算中可能導(dǎo)致運(yùn)算量劇烈增加，即所謂“組合爆炸”問題。雖然直接[8]或早期不交化[9]故障樹結(jié)構(gòu)函數(shù)在一定程度上可以減少運(yùn)算量，但是采用不交型積之和定理[10]實(shí)現(xiàn)割集不交運(yùn)算的過程是煩瑣和費(fèi)時(shí)的。

二元決策圖(BDD)技術(shù)最早用于數(shù)字電路的簡(jiǎn)化分析和結(jié)構(gòu)設(shè)計(jì)。作為一種新興的分析工具，BDD技術(shù)已廣泛應(yīng)用于可靠性分析及故障診斷領(lǐng)域。其重要作用在于能直接顯示頂事件故障形成的邏輯路徑；直觀顯示系統(tǒng)故障(頂事件)的薄弱環(huán)節(jié)。本文用BDD技術(shù)快速實(shí)現(xiàn)故障樹的定性分析，討論BDD技術(shù)的相關(guān)理論，研究并實(shí)現(xiàn)其關(guān)鍵算法。進(jìn)行這些研究的主要原因在于：1) 基于Shannon分解定理的BDD技術(shù)能夠直接實(shí)現(xiàn)故障樹結(jié)構(gòu)函數(shù)(本質(zhì)為最小割集的并集形式)的不交化分解[11-13]，而這種分析過程可以同時(shí)得到故障樹的MCS。顯然，這比聯(lián)合運(yùn)用Fussell-Vesely算法(或Semanderes算法)和不交化原理(以下簡(jiǎn)稱聯(lián)合方法)進(jìn)行故障樹分析更方便直接。2) BDD技術(shù)是建立在一定理論基礎(chǔ)上的，需要研究其連接規(guī)則。為了獲得故障樹頂事件的BDD結(jié)構(gòu)，需要分析具體的實(shí)現(xiàn)方法——遞歸方法。3)用BDD技術(shù)獲取故障樹的不交化割集，涉及路徑搜索。本文提出一種繼承父節(jié)點(diǎn)信息的遞歸方法來(lái)快速實(shí)現(xiàn)不交化，需要深入討論并分析其實(shí)現(xiàn)過程。

1 BDD的故障樹原理及其實(shí)現(xiàn)規(guī)則

Shannon分解使得影響頂事件故障(正常)狀態(tài)的基本事件及傳播路徑變得清晰有序，而BDD技術(shù)則是實(shí)現(xiàn)和簡(jiǎn)化Shannon分解的有效工具。

1.1 故障樹結(jié)構(gòu)函數(shù)的Shannon分解

1.2 基于BDD技術(shù)的故障樹分析原理

BDD技術(shù)拓展了Shannon分解的功能，使故障樹結(jié)構(gòu)函數(shù)的產(chǎn)生與割集不交化同時(shí)實(shí)現(xiàn)成為可能。BDD技術(shù)是一系列原理、方法及實(shí)現(xiàn)的有機(jī)整體。三元邏輯運(yùn)算符ite(if-then-else)是分析全過程的有力工具。

1.2.1 ite運(yùn)算符及其在邏輯運(yùn)算中的應(yīng)用

故障樹底事件間的關(guān)系從屬于邏輯門的性質(zhì)，為了用一種方式統(tǒng)一描述底事件自身及其相互間的關(guān)系，定義ite運(yùn)算符[14]為：

圖1 ite(x, y, z)的二叉結(jié)構(gòu)形式

ite結(jié)構(gòu)可以描述以下3種重要關(guān)系：

ite運(yùn)算符為進(jìn)一步分析事件和結(jié)構(gòu)函數(shù)的關(guān)系奠定了同源描述的基礎(chǔ)，也使全面分析故障樹成為可能。

1.2.2 基于ite運(yùn)算符的BDD連接規(guī)則

式中，i1,i2,L,in是{1,2,L,n}的一個(gè)排列，且i1,

顯然，式(9)是具有ite形式的層次結(jié)構(gòu)。如果知道了形如式(9)的兩個(gè)BDD結(jié)構(gòu)形式M和N，需要用ite運(yùn)算符來(lái)連接它們。因?yàn)槿绻軌虻玫竭B接兩個(gè)BDD結(jié)構(gòu)的ite操作形式，再用遞歸方式，將很快得到整個(gè)故障樹的BDD。下面分析這種連接過程。

2) 兩個(gè)重要的連接規(guī)則。

事實(shí)上，M和N一定是通過某種邏輯操作而聯(lián)系起來(lái)的?？紤]到經(jīng)過規(guī)范化處理的故障樹只含有“或”或“與”邏輯門及底事件，則分析M?op?N的ite連接關(guān)系時(shí)，op表示邏輯“或”(用“+”表示)或“與”操作。

假設(shè)兩個(gè)子BDD結(jié)構(gòu)分別為：

將xi和xj作比較，兩者指標(biāo)(下標(biāo))只有相等或不等。當(dāng)不等時(shí)，可以選擇最小根節(jié)點(diǎn)(指標(biāo)最小的節(jié)點(diǎn))作為標(biāo)準(zhǔn)。因此，操作規(guī)則實(shí)質(zhì)上只有兩種。

綜合情況1和情況2，式(13)得證。

式(12)和式(13)是形成故障樹BDD的關(guān)鍵規(guī)則。雖然它們是為連接兩個(gè)子BDD結(jié)構(gòu)而發(fā)展的，但其連接對(duì)象并不局限于子BDD結(jié)構(gòu)，事實(shí)上，它們連接的對(duì)象可以是兩個(gè)基本事件。

2 故障樹BDD分析的遞歸實(shí)現(xiàn)

基于BDD技術(shù)的故障樹分析能夠同時(shí)實(shí)現(xiàn)MCS及其不交化過程，但其實(shí)現(xiàn)要分兩個(gè)步驟：1) 形成頂事件的BDD結(jié)構(gòu)；2) 在獲得的BDD結(jié)構(gòu)基礎(chǔ)上得到割集的不交化形式。

2.1 頂事件BDD結(jié)構(gòu)的遞歸實(shí)現(xiàn)

故障樹結(jié)構(gòu)輸入表描述了基本事件及邏輯門間的關(guān)系。BDD結(jié)構(gòu)的遞歸實(shí)現(xiàn)也正是從結(jié)構(gòu)輸入表的邏輯門開始的。其步驟如下：

1) 建立兩個(gè)n行1列的元胞數(shù)組FTS和BDS(n表示故障樹中邏輯門的個(gè)數(shù))。FTS存儲(chǔ)不同邏輯門的輸入元素，BDS存儲(chǔ)各邏輯門的BDD結(jié)構(gòu)。置i=n。

2) 根據(jù)門i的類型，利用ite運(yùn)算符連接FTS{i}中的底事件；連接后的結(jié)果A保存在BDS{i}中，即BDS{i}=A。

3) 置i=i?1，如果門i?1的輸入中僅有底事件，則重復(fù)步驟2)。

否則，如果輸入是底事件和輸入邏輯門的混合情況(第i?1個(gè)邏輯門的輸入中，一部分是底事件，另一部分是另外的邏輯門)，則重復(fù)步驟2)的前半部分，即得到的結(jié)果置為A；計(jì)算輸入邏輯門的個(gè)數(shù)m，置j=1，A=BDD_ITE_CAL(A,G(j),TYPE)；置j=j+1，重復(fù)A=BDD_ITE_CAL(A,G(j),TYPE)，直到j(luò)=m。

如果輸入全為邏輯門，則置第一個(gè)邏輯門的BDD結(jié)果為A，其余步驟同輸入是部分邏輯門的情況，置BDS{i}=A。

4) 重復(fù)步驟3)，直到i=1，則BDS{1}為頂事件TBDD的BDD結(jié)構(gòu)，即TBDD= BDS{1}。

其中，A=BDD_ITE_CAL(A,G(j),TYPE)是連接兩個(gè)子BDD結(jié)構(gòu)的函數(shù)，它是遞歸實(shí)現(xiàn)頂事件BDD結(jié)構(gòu)的核心函數(shù)。簡(jiǎn)言之，該遞歸函數(shù)的輸入?yún)?shù)A是一個(gè)子BDD結(jié)構(gòu)，它與某子BDD結(jié)構(gòu)中G(j)通過類型TYPE連接后，輸出新的子BDD結(jié)構(gòu)A，為進(jìn)一步連接新的子BDD創(chuàng)造了遞歸基礎(chǔ)。G(j)代表某個(gè)邏輯門的輸入元素BDS{k}，是子BDD結(jié)構(gòu)。

2.2 BDD結(jié)構(gòu)不交化割集的實(shí)現(xiàn)——繼承操作

頂事件BDD結(jié)構(gòu)的實(shí)現(xiàn)精確地描述了底事件對(duì)頂事件影響的狀態(tài)及路徑。本質(zhì)上講，這種狀態(tài)和路徑的表述就是頂事件的不交化割集。實(shí)現(xiàn)頂事件BDD結(jié)構(gòu)的不交化割集的方式是路徑搜索，當(dāng)某條路徑搜索完畢，該路徑上的節(jié)點(diǎn)以某種方式排列成的鏈就形成一個(gè)不交割集(相對(duì)其他割集而言)。不交割集鏈形成的關(guān)鍵在于繼承操作。

在搜索過程中，每個(gè)中間節(jié)點(diǎn)都直接繼承它的父節(jié)點(diǎn)所繼承的全部信息，且以特定方式繼承父節(jié)點(diǎn)的信息。當(dāng)父節(jié)點(diǎn)向左分支(分支邊標(biāo)定“1”)到達(dá)子節(jié)點(diǎn)時(shí)，子節(jié)點(diǎn)直接繼承父節(jié)點(diǎn)的信息；當(dāng)父節(jié)點(diǎn)向右分支(分支邊標(biāo)定“0”)到達(dá)子節(jié)點(diǎn)時(shí)，子節(jié)點(diǎn)繼承的是父節(jié)點(diǎn)的補(bǔ)信息。

繼承關(guān)系是不交化割集形成的一個(gè)重要環(huán)節(jié)。在繼承的作用下，不交化割集的路徑不斷形成(通過不斷分支以深度優(yōu)先方式進(jìn)行搜索)。由于路徑在葉節(jié)點(diǎn)值為“1”的位置結(jié)束，所以BDD結(jié)構(gòu)中葉節(jié)點(diǎn)值為“1”的個(gè)數(shù)就是不交化割集的數(shù)目(雖然在搜索前不一定知道這個(gè)數(shù)目)。每個(gè)不交化割集由某節(jié)點(diǎn)(其左分支的值為“1”的葉節(jié)點(diǎn))和它的繼承信息共同形成(通過“與”關(guān)系)。分析頂事件的BDD結(jié)構(gòu)[15]，如圖2所示，顯然該結(jié)構(gòu)有4個(gè)不交化割集。

圖2 某仿真故障樹的BDD結(jié)構(gòu)

在繼承操作下，不交化割集的形成具有重復(fù)性很高的規(guī)律，因此其搜索過程在本質(zhì)上也是遞歸的。

3 基于BDD的故障樹分析的例子

為了說(shuō)明用BDD分析故障樹的優(yōu)勢(shì)，下面以一個(gè)具體的例子[17]加以說(shuō)明。

3.1 基于BDD技術(shù)的運(yùn)行結(jié)果

故障樹結(jié)構(gòu)如圖3所示，表1是對(duì)應(yīng)的故障樹結(jié)構(gòu)輸入表。

運(yùn)用BDD技術(shù)，得到頂事件(門1的輸出)的BDD結(jié)構(gòu)為：

根據(jù)編程設(shè)置，式(14)實(shí)際上是一個(gè)含有3個(gè)元素嵌套的元胞數(shù)組，其直觀結(jié)構(gòu)如圖4所示。表2列出了基于BDD結(jié)構(gòu)的不交化割集及析出的MCS。

圖3 故障樹結(jié)構(gòu)

如前所述，利用聯(lián)合方法得到不交化割集的過程是煩瑣的，而利用BDD技術(shù)則可直接得到不交化割集。為了比較兩者之間的效率，表3列出了兩種方法的運(yùn)行時(shí)間(CPU為AMD Sempron(tr) Processor 3000+，1.61 GHz主頻，內(nèi)存為512 MB)。

表1 故障樹的結(jié)構(gòu)表

圖4 故障樹的BDD結(jié)構(gòu)

表2 故障樹的不交化割集(割集)

表3 形成不交化割集的運(yùn)行時(shí)間 單位：s

3.2 分析與結(jié)論

與傳統(tǒng)的Fussell-Vesely(F-V)算法及不交化積之和定理相比，基于BDD技術(shù)的故障樹分析具有明顯的優(yōu)勢(shì)。

首先，BDD技術(shù)比聯(lián)合方法的功能更完善。BDD技術(shù)將實(shí)現(xiàn)結(jié)構(gòu)函數(shù)和不交化過程統(tǒng)一起來(lái)，一次性實(shí)現(xiàn)兩方面的要求，直接實(shí)現(xiàn)表2中的不交化割集(已經(jīng)通過化簡(jiǎn)處理)，其最小割集很容易從不交割集中析出(只需將不交割集中的補(bǔ)事件去掉)。而聯(lián)合方法中的F-V算法只能得到頂事件的割集，割集的不交化處理只能在最小割集的基礎(chǔ)上運(yùn)用過程繁復(fù)的不交型積之和定理來(lái)實(shí)現(xiàn)。簡(jiǎn)言之， BDD技術(shù)實(shí)現(xiàn)：不交化割集處理→割集；而后兩者聯(lián)合實(shí)現(xiàn)：割集→不交割集處理。故障樹定量分析的必要條件正是得到不交化割集及其簡(jiǎn)化處理形式。從該意義上講，BDD技術(shù)比另外兩者聯(lián)合運(yùn)用的功能更完善。

最后，用BDD技術(shù)獲得不交化割集的思想比用后兩者聯(lián)合處理得到不交化割集簡(jiǎn)單。用BDD技術(shù)獲得不交型割集的過程僅涉及函數(shù)的遞歸調(diào)用，處理的對(duì)象是事件本身，采用的方式是繼承事件的信息，在遞歸調(diào)用和繼承的作用下，不交型割集的簡(jiǎn)化形式可以直接得到；聯(lián)合方法中的不交化積之和方法處理的對(duì)象首先是割集，是在割集與割集之間進(jìn)行比較和吸收，這種比較和吸收過程不但要遍歷所有割集對(duì)(組合)，還要遍歷割集間的元素對(duì)(組合)。只有完成了這些遍歷，不交化割集的簡(jiǎn)化形式才得以實(shí)現(xiàn)。

4 結(jié) 束 語(yǔ)

BDD技術(shù)是故障樹分析的一種有效技術(shù)。在與傳統(tǒng)故障樹分析方法作比較的基礎(chǔ)上，本文詳細(xì)分析了BDD技術(shù)的原理、方法和實(shí)現(xiàn)過程。繼承技術(shù)的運(yùn)用是實(shí)現(xiàn)割集不交化的關(guān)鍵技術(shù)，本文對(duì)繼承的方法和原因作了詳細(xì)分析，并在具體的例證中驗(yàn)證了BDD技術(shù)優(yōu)于傳統(tǒng)故障樹分析的原因。

[1] 李建平, 余建星. 模糊故障樹分析方法在工程質(zhì)量風(fēng)險(xiǎn)分析中的應(yīng)用[J]. 水利水電技術(shù), 2008, 39(2): 45-49.LI Jian-ping, YU Jian-xing. Application of fuzzy fault tree analysis to risk analysis of construction quality[J]. Water Resources and Hydropower Technology, 2008, 39(2): 45-49.

[2] 王少萍. 工程可靠性[M]. 北京: 北京航空航天大學(xué)出版社, 2000.WANG Shao-ping. Reliability engineering[M]. Beijing:Beijing University of Aeronautics and Astronautics Press,2000.

[3] KRASICH M. Use of fault tree analysis for evaluation of system-reliability improvements in design phase[C]//Proceedings of the Annual Reliability and Maintainability Symposium (S0149-144X). [S.l.]: IEEE, 2000: 1-7.

[4] ARCIDIACONO G. Reliability improvement of a diesel engine using the FMETA approach[J]. Quality and Reliability Engineering International (S0748-8017), 2004,20(2): 143-154.

[5] 宋保維, 毛昭勇, 王雯琴, 等. 基于故障樹分析的魚雷可靠性評(píng)定方法[J]. 系統(tǒng)仿真學(xué)報(bào), 2007, 19(10):2180-2182.SONG Bao-wei, MAO Zhao-yong, WANG Wen-qin, et al.Reliability evaluation method of torpedo based on FTA[J].Journal of System Simulation, 2007, 19(10): 2180-2182.

[6] FUSSELL J B, VESELY W E. A new methodology for obtaining cut sets[J]. Trans Am Nucl Soc Trans, 1972, 15(1):262-263.

[7] SEMANDERES S N. A computer program for the efficient logic reduction analysis of fault trees[J]. IEEE Trans Nuclear Science, 1971, 10: 481-487.

[8] 金星, 武江濤, 洪延姬. 一種新的故障樹定量分析優(yōu)化方法[J]. 中國(guó)空間科學(xué)技術(shù), 2001, 21(3): 60-64.JIN Xing, WU Jiang-tao, HONG Yan-ji. A new optimized method for quantitative analysis of fault tree[J]. Chinese Space Science and Technology, 2001, 21(3): 60-64.

[9] 劉永賓, 陳金水, 謝學(xué)武. 割集矩陣在早期不交化FTA中的應(yīng)用[J]. 天津大學(xué)學(xué)報(bào), 2000, 33(3): 318-323.LIU Yong-bin, CHEN Jin-shui, XIE Xue-wu. Study on the application of cut sets matrix to fault tree system analysis[J].Journal of Tianjin University, 2000, 33(3): 318-323.

[10] 梅啟智, 廖炯生, 孫惠中. 系統(tǒng)可靠性工程基礎(chǔ)[M]. 北京: 科學(xué)出版社, 1987.MEI Qi-zhi，LIAO Jiong-sheng, SUN Hui-zhong.Foundation of system reliability engineering[M]. Beijing:Science Press, 1987.

[11] 盧世榮, 方逵, 周經(jīng)綸. BDD表示下的部件重要度的計(jì)算[J]. 系統(tǒng)工程與電子技術(shù), 1999, 21(3): 70-74.LU Shi-rong, FANG Kui , ZHOU Jing-lun. The computation of importance of elements in fault trees presented by BDD[J]. Systems Engineering and Electronics, 1999, 21(3): 70-74.

[12] 孫毅彪. 基于BDD故障樹分析的海關(guān)風(fēng)險(xiǎn)識(shí)別理論及其應(yīng)用[J]. 運(yùn)籌與管理, 2008, 17(2): 501-505.SUN Yi-biao. A theory and Its application of binary decision dagrams based fault tree analysis in customs risk identification[J]. Operations Research and Management Science, 2008, 17(2): 501-505.

[13] AKERS S B. Binary decision diagrams[J]. IEEE Transaction on Computer, 1978, 27: 509-516.

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

[15] 袁靜, 胡昌華, 徐瑞, 等. 基于改進(jìn)BDD算法的導(dǎo)彈安控系統(tǒng)故障樹仿真分析[J]. 系統(tǒng)仿真學(xué)報(bào), 2007, 19(1):10-11.YUAN Jing, HU Chang-hua, XU Rui, et al. Fault tree simulation analysis of missile safety control system based on improved BDD algorithm[J]. Journal of System Simulation, 2007, 19(1): 10-11.

[16] 王紅梅, 胡明, 王濤. 數(shù)據(jù)結(jié)構(gòu)(C++版)[M]. 北京: 清華大學(xué)出版社, 2005.WANG Hong-mei, HU Ming, WANG Tao. Data structure(C++ version)[M]. Beijing: Tsinghua University Press,2005.

[17] 張超. 基于BDD的動(dòng)態(tài)故障樹優(yōu)化分析研究[D]. 西安:西北工業(yè)大學(xué), 2004.ZHANG Chao. Optimization analysis of the dynamic fault tree based on BDD[D]. Xi’an: Northwestern Polytechnical University, 2004.