苗祚雨，牛 儒，唐 濤

(北京交通大學(xué)軌道交通控制與安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京100044)

隨著控制技術(shù)的發(fā)展，工業(yè)生產(chǎn)的各個(gè)領(lǐng)域都越來越依賴于復(fù)雜交互的自動(dòng)化設(shè)備.自動(dòng)化在帶來便利的同時(shí)也帶來一系列安全問題，特別是安全苛求系統(tǒng)，更需要重視系統(tǒng)的可靠性.安全苛求系統(tǒng)設(shè)計(jì)需要依賴安全分析進(jìn)行引導(dǎo)和評(píng)價(jià).故障樹是工程中安全分析的常用方法之一.隨著系統(tǒng)規(guī)模的逐漸龐大，傳統(tǒng)的人工分析方式不僅工作量龐大，結(jié)果的正確度也得不到保證.因此，越來越多的研究關(guān)注計(jì)算機(jī)輔助安全分析的研究.故障樹分析自動(dòng)化的研究熱點(diǎn)是最小割集的自動(dòng)生成算法.

國(guó)際上，很多學(xué)者對(duì)故障樹最小割集的生成算法進(jìn)行了深入研究［1］.除了 A.Rauzy將二元決策圖［2］引入到故障樹分析之中［3］，其他方法(包括馬爾可夫鏈［4］、Petri網(wǎng)［5］以及最小路集［6］)都不可避免地碰到了組合爆炸的問題.二元決策圖方法的運(yùn)用提高了故障樹分析的效率，該方法在諸多可靠性分析領(lǐng)域都有應(yīng)用，例如多相任務(wù)系統(tǒng)(PMS)［7-8］包括核電、航空、交通和電子系統(tǒng)以及海洋工程［9］.

但是，傳統(tǒng)的二元決策圖方法需要將基本事件排序以獲得良好的分析效率，而基本事件排序的過程本身就是一個(gè) NP問題［10］.R.Remenyte和J.D.Andrews提出將故障樹轉(zhuǎn)化為二元決策圖的元素連接法來提高轉(zhuǎn)化效率［11］，該方法可以不用考慮基本事件的排序情況.其他學(xué)者運(yùn)用二元決策圖的權(quán)值比較對(duì)該方法進(jìn)行了改進(jìn)［12］，但是以上方法沒有解決故障樹最小割集生成的問題.本文以元素連接法為基礎(chǔ)，提出了故障樹向二元決策圖轉(zhuǎn)換以及最小割集生成的新方法.該方法具有運(yùn)算速度快，占用內(nèi)存空間小的特點(diǎn).以CBTC(基于通信的列車控制系統(tǒng))的區(qū)域控制器子系統(tǒng)為實(shí)際案例將該方法與傳統(tǒng)的窮舉法進(jìn)行了對(duì)比，展現(xiàn)了本方法在分析處理復(fù)雜系統(tǒng)故障樹時(shí)的快速性和準(zhǔn)確性.

1 元素連接法

這種構(gòu)造二元決策圖的方法是將故障樹中的每一個(gè)邏輯門作為最小元素，然后再將這些元素按照組合規(guī)則組成一個(gè)完整的二元決策圖［11］.該方法遵循兩條構(gòu)造規(guī)則.

規(guī)則1:若是與門，二元決策圖節(jié)點(diǎn)間通過1分支相連;若是或門，二元決策圖節(jié)點(diǎn)間通過0分支相連.如圖1所示.

圖1 規(guī)則1示例Fig.1 Example of rule 1

規(guī)則2:當(dāng)融合兩個(gè)二元決策圖的分支時(shí)，其中的一個(gè)將作為主二元決策圖.分為兩種情況:如果兩個(gè)分支作為一個(gè)與門的輸入，那么第二個(gè)分支將連接在主二元決策圖的分支的每個(gè)1分支上;如果兩個(gè)分支作為一個(gè)或門的輸入，那么第二個(gè)分支將連接在主二元決策圖的分支的每個(gè)0分支上.如圖2所示.

圖2 規(guī)則2示例Fig.2 Example of rule 2

2 新最小割集生成算法

這部分是以元素連接法為基礎(chǔ)介紹新的構(gòu)造原則和化簡(jiǎn)原則，然后通過深度優(yōu)先搜索遍歷該圖得到最小割集.另外，為了區(qū)別和原方法構(gòu)造的二元決策圖的不同，將新方法構(gòu)造的二元決策圖與其進(jìn)行了對(duì)比.

2.1 二元決策圖的構(gòu)造

新的構(gòu)造方法用規(guī)則A和規(guī)則B代替了原元素連接法中的規(guī)則2.

規(guī)則A:若是先交后并的形式，如 ab+bed，如圖3所示.

根據(jù)元素連接法的構(gòu)造原則，ab和 bcd兩個(gè)子二元決策圖都可以作為組合時(shí)的主子圖，圖3中選擇了bcd作為主子圖.

規(guī)則 B:是先并后交的形式，如 (a+b)(b+c+d).選擇一個(gè)多項(xiàng)式作為第一排，其中每項(xiàng)出現(xiàn)的次數(shù)由第二個(gè)多項(xiàng)式中的項(xiàng)數(shù)決定，第二排中每項(xiàng)出現(xiàn)的個(gè)數(shù)由第一個(gè)多項(xiàng)式的項(xiàng)數(shù)決定，如圖4所示.

以上的關(guān)于融合子二元決策圖的方法能夠?qū)⒍鄠€(gè)子圖構(gòu)造成形式整齊的二元決策圖.下面將通過兩個(gè)一般性的例子說明運(yùn)用的具體過程.

例1 x1(x2+x3+x4)(x2+x5)，按照運(yùn)算順序，從左往右先構(gòu)造x1(x2+x3+x4)的二元決策圖，按照“先并后交”的形式，第一個(gè)子圖是單項(xiàng)，第二個(gè)多項(xiàng)式含有三項(xiàng).因此，第一排將有3個(gè)x1出現(xiàn)，第二排x2，x3，x4各出現(xiàn)一次，如圖5所示.

圖3 規(guī)則A示例Fig.3 Example of rule A

圖4 規(guī)則B示例Fig.4 Example of rule B

圖5 例1第一步Fig.5 Step 1 of example 1

接著將這部分的二元決策圖作為整體與第三個(gè)多項(xiàng)式x2+x5構(gòu)造圖形.這里，根據(jù)以上原則，由于x2和x5是兩項(xiàng)，圖5將作為主圖出現(xiàn)兩次，x2和x5將分別與每次出現(xiàn)的主二元決策圖的1分支相連，如圖6所示.

例2 a(c+de(a+f))，按照運(yùn)算優(yōu)先級(jí)，先構(gòu)造de(a+f)，其中de作為主圖由于第二個(gè)多項(xiàng)式項(xiàng)數(shù)為2出現(xiàn)兩次，而 a和 f將分別連接在每個(gè)主圖的1分支上，如圖7所示.

圖6 例1第二步Fig.6 Step 2 of example 1

圖7 例2第一步Fig.7 Step 1 of example 2

接下來第二步構(gòu)造a(c+X)，X表示de(a+f)，根據(jù)規(guī)則B得到圖8.

圖8 例2第二步Fig.8 Step 2 of example 2

2.2 二元決策圖的化簡(jiǎn)

在應(yīng)用以上規(guī)則將故障樹轉(zhuǎn)化為二元決策圖后，進(jìn)一步對(duì)其化簡(jiǎn)，下面是針對(duì)本文算法而提出的簡(jiǎn)化原則.

1)若1分支中出現(xiàn)的中間結(jié)點(diǎn)是重復(fù)的，則可以省略，如圖9所示.

圖9 化簡(jiǎn)規(guī)則1示例Fig.9 Example of reduction rule 1

2)連接共享結(jié)點(diǎn)的連線(圖9用虛連線表示)可以在構(gòu)造圖中省略.

3)0元素的節(jié)點(diǎn)可以刪掉，這樣只剩下1元素的節(jié)點(diǎn)，圖變成“割集圖”.

根據(jù)以上的簡(jiǎn)化原則，形如a(c+de(a+f))比較復(fù)雜的表達(dá)式可以表示成如下的二元決策圖的形式，如圖10所示.

圖10 例2經(jīng)化簡(jiǎn)后Fig.10 Example 2 after reduction

2.3 由二元決策圖得到最小割集

在得到化簡(jiǎn)后的二元決策圖后，就可以用深度優(yōu)先搜索的方法對(duì)圖進(jìn)行一遍搜索以得到割集.這里還是以例2來說明.

搜索過程由從左至右、從上至下開始，節(jié)點(diǎn)訪問順序如圖11中標(biāo)注所示.由事件a開始，記錄該事件并標(biāo)記它，接下來訪問節(jié)點(diǎn) c代表的事件，檢查是否標(biāo)記(這里沒有)，沒有標(biāo)記則記錄標(biāo)記，否則跳過.接下來一直訪問到該路徑的盡頭1節(jié)點(diǎn)，然后沿原來的路徑返回到上一個(gè)訪問節(jié)點(diǎn)并檢查是否標(biāo)記，這樣依次檢查到第一行第二列并且重復(fù)上述過程.最終記錄的訪問節(jié)點(diǎn)為ac1ade1adef1.

搜索完畢后，以1為分隔符可以得到割集是ac，ade，adef，然后按照布爾代數(shù)的吸收率法則，可以最終得到最小割集是 ac，ade.

圖11 例2進(jìn)行深度優(yōu)先搜索Fig.11 Depth first search on example 2

在得到最小割集的過程中，由于每個(gè)決策節(jié)點(diǎn)的訪問操作只進(jìn)行一遍，該算法復(fù)雜度是線性O(shè)(n).

2.4 與原有方法的構(gòu)造比較

本方法區(qū)別于現(xiàn)有的元素連接法主要在以下兩點(diǎn):

1)去掉多余的0分支連線，使二元決策圖的決策點(diǎn)不一定有兩個(gè)分支.

2)搜索過程不用區(qū)分1和0分支，方便處理.以例2說明新方法和元素連接法的區(qū)別，如圖12所示.

圖12 不同的二元決策圖形式Fig.12 Different binary decision diagram forms

圖12(a)為原方法構(gòu)造的二元決策圖，圖12(b)是新方法的二元決策圖形式.

3 案例分析

CBTC系統(tǒng)主要包括列車自動(dòng)監(jiān)控系統(tǒng)，區(qū)域控制器，計(jì)算機(jī)連鎖系統(tǒng)，車載控制器，數(shù)據(jù)存儲(chǔ)單元，軌旁設(shè)備和數(shù)據(jù)通信系統(tǒng).其中區(qū)域控制器與其它各個(gè)部分進(jìn)行數(shù)據(jù)通信，為控制區(qū)域內(nèi)的運(yùn)行列車提供列車管理以及移動(dòng)授權(quán)的服務(wù).區(qū)域控制器作為地面設(shè)備支持整個(gè)系統(tǒng)高效安全地運(yùn)轉(zhuǎn)，它的功能主要有列車管理，移動(dòng)授權(quán)計(jì)算，封閉區(qū)域管理，臨時(shí)限速管理以及通信等.

用兩種最小割集生成算法分別分析區(qū)域控制器中混合MA錯(cuò)誤的故障樹(見附錄A1).為方便起見，故障樹的基本事件用字母表示(表1).

表1 字母對(duì)應(yīng)基本事件Tab.1 Letters representing events

本故障樹作為標(biāo)準(zhǔn)故障樹，包含11個(gè)邏輯門，31個(gè)節(jié)點(diǎn)事件.其中有19個(gè)獨(dú)立基本事件.并且，其最大深度為5層.

分別用新方法(轉(zhuǎn)化后的二元決尺圖見附錄A2)和窮舉法求解故障樹的最小割集.新算法的二元決策圖使用了鄰接表的數(shù)據(jù)墊儲(chǔ)結(jié)構(gòu)，相關(guān)操作都以鄰接表的形式完成.首先根據(jù)轉(zhuǎn)換規(guī)則將原故障樹從底至頂轉(zhuǎn)換成二元決策圖，然后用深度優(yōu)先搜索得到割集，進(jìn)一步由布爾代數(shù)吸收律得到最小割集.而窮舉法是實(shí)際工程中經(jīng)常使用的故障樹最小割集求解的經(jīng)典算法，在該算法中首先遍歷故障樹生成結(jié)構(gòu)函數(shù)，然后逐個(gè)檢驗(yàn)所有的底事件組合.雖然兩種方法不同，但得到了相同的最小割集:

3.1 處理規(guī)模比較

兩種算法在實(shí)現(xiàn)過程中占用的存儲(chǔ)空間是不相同的.兩種算法都將故障樹構(gòu)造成另外一種表示形式，轉(zhuǎn)換后的形式分別是二叉樹和二元決策圖.窮舉法在處理過程中中間事件和底事件一共占用了39個(gè)存儲(chǔ)節(jié)點(diǎn)，而基于二元決策圖的方法構(gòu)造的二元決策圖也同樣占用了39個(gè)存儲(chǔ)節(jié)點(diǎn).但是，在處理得到最小割集的過程中，窮舉算法產(chǎn)生了633個(gè)待篩選的符合條件的割集，而新方法產(chǎn)生的待篩選的割集數(shù)目是17個(gè).

3.2 處理速度比較

從算法時(shí)間復(fù)雜度來分析，本算法中的二元決策圖存儲(chǔ)方式為鄰接表，對(duì)其進(jìn)行一次深度優(yōu)先搜索的復(fù)雜度是O(n+m)，其中n為頂點(diǎn)的個(gè)數(shù)，m為弧的個(gè)數(shù)，整體來看其復(fù)雜度可表示為線性，即O(n);而窮舉法的原理是將原故障樹轉(zhuǎn)化成二叉樹，然后通過后序遍歷生成故障樹的布爾表達(dá)式，再依次驗(yàn)證所有底事件的割集組合.其中后序遍歷的復(fù)雜度為O(n)，n為轉(zhuǎn)化后二叉樹的節(jié)點(diǎn)數(shù).割集組合驗(yàn)證的復(fù)雜度是 O(2n×N)，其中n表示底事件的個(gè)數(shù)，N表示后序遍歷生成后綴表達(dá)式中包括運(yùn)算符和數(shù)字在內(nèi)的數(shù)據(jù)項(xiàng)數(shù).因此，綜合來看，窮舉法的整體復(fù)雜度為指數(shù)級(jí)別，即O(2n).

實(shí)驗(yàn)中，將兩種算法在eclipse環(huán)境下在同一臺(tái)電腦上分別運(yùn)行50次，通過對(duì)比圖可以直觀地觀察到算法之間的速度差異.

圖13 消耗時(shí)間對(duì)比Fig.13 Time cost comparison

圖13中，橫坐標(biāo)表示實(shí)驗(yàn)對(duì)比次數(shù)，縱坐標(biāo)表示算法運(yùn)行時(shí)間.通過對(duì)比發(fā)現(xiàn)，窮舉算法的每次處理時(shí)間在16 s左右，而基于二元決策圖方法的處理時(shí)間在幾毫秒左右.新方法相對(duì)于窮舉算法來說有很大的速度優(yōu)勢(shì).

4 結(jié)論

1)本文提出了一種新的故障樹最小割集算法，該算法包括二元決策圖構(gòu)造規(guī)則、化簡(jiǎn)規(guī)則以及相應(yīng)的最小割集生成方法.傳統(tǒng)的窮舉法是指數(shù)級(jí)別的復(fù)雜度，而本文提出的新方法則是線性復(fù)雜度，相比之下更加高效.

2)運(yùn)用不同的故障樹作為例子逐步演示了該新方法的實(shí)施過程.在案例分析中，對(duì)CBTC系統(tǒng)中區(qū)域控制器故障樹的分析更加顯示了該新方法相比傳統(tǒng)方法在處理大型故障樹時(shí)的時(shí)間和空間上的巨大優(yōu)勢(shì).

附錄A1 混合MA錯(cuò)誤故障樹Appendix A1 Fault tree of hybrid MA error

附錄A2 與故障樹對(duì)應(yīng)的二元決策圖Appendix A2 Fault tree＇s corresponding binary decision diagram

［1］ Rauzy A.Mathematical foundations of minimal cutsets［J］.Reliability，IEEE Transactions on，2001，50(4):389-396.

［2］Akers S B.Binary decision diagrams［J］.IEEE Trans.Comput.，1978(C-27):509-516.

［3］Rauzy A.New algorithms for fault trees analysis［J］.Reliability Engineering＆ System Safety，1993，40(3):203-211.

［4］Dugan J B，Salvatore J B，Mark A B.Fault trees and Markov models for reliability analysis of fault-tolerant digital systems［J］.Reliability Engineering ＆ System Safety，1993，39(3):291-307.

［5］Zhang Xiaojie，Miao Qiang，F(xiàn)an Xianfeng，et al.Dynamic fault tree analysis based on Petri nets［C］.Reliability，Maintainability and Safety，8th International Conference on，2009:138-142.

［6］Shier D R，Whited D E.Algorithms for generating minimal cutsets by inversion［J］.Reliability，IEEE Transactions on，1985，34(4):314-319.

［7］Du Suguo，Wang Nan.A novel binary decision diagram variable ordering approach on phased mission system［C］.Management Science and Engineering(ICMSE)，International Conference on，2010:116-122.

［8］Andrews J D，Remenyte P R，Prescott D R.Reliability analysis of missions with cooperating platforms［C］.Reliability and Maintainability Symposium(RAMS)，Proceedings-Annual，2010:25-28.

［9］Cai Yao，Liu Zhengjiang，Wu Zhaolin.Improvement of fault tree analysis in formal safety assessment using binary decision diagram［C］.Information Science and Engineering(ICISE)，1st International Conference on，2009:4330-4333.

［10］Bryant R.Graph based algorithms for Boolean function manipulation［J］.IEEE Transactions on Computer，1987，35(8):677-691.

［11］Remenyte R，Andrews J D.A simple component connection approach for fault tree conversion to binary decision diagram［C］.Availability，Reliability and Security.The First International Conference on，2006.

［12］Yuan Kan，Hu Shousong.Multiple-fault diagnosis based on binary decision diagram［C］.Industrial Engineering and Engineering Management，IEEE International Conference on，2009:1658-1662.