基于順序失效符的動態故障樹形式規約

王 波 劉 東

(裝備學院復雜電子系統仿真國防科技重點實驗室，北京 101416)

李 藝

(裝備學院科研部，北京 101416)

動態故障樹(DFT，Dynamic Fault Tree)由靜態故障樹(SFT，Static Fault Tree)拓展而來.通過增加新的邏輯門，如 PAND，FDEP，CSP，WSP，HSP(本文將 CSP，WSP，HSP統稱為 XSP)等，DFT提升了SFT對優先失效、儲備失效和功能觸發等動態特性的建模能力［1］.

DFT的研究方法主要有仿真方法和數學分析方法，本文屬于后者.DFT的數學分析方法有間接法和直接法.間接法是將DFT轉換為同構的狀態空間模型，如時序貝葉斯網絡模型(TBN，Temporal Bayesian Network)［2］、連續時間 Markov 鏈模型(CTMC，Continuous Time Markov Chains)［3］和隨機 Petri網模型(SPN，Stochastic Petri Nets)［4］等.狀態空間模型不足之處在于:①欠缺通用性;②存在指數爆炸問題.直接法是從DFT形式規約出發，構建 DFT的結構函數.DFT形式規約是將DFT動態邏輯門定義中模糊的自然語言轉化成嚴謹的數學描述語言，從而構建DFT的嚴密理論體系.DFT形式規約的典型研究有Pandora法、Merle法及割序集(CSS，Cut Sequence Set)模型.Pandora法通過重新定義PAND，提出了新的邏輯門SAND和 POR［5－6］.Pandora 法能對含優先失效關系的DFT進行分析.Merle法定義了2種新的時序符號，BF(?)和 SM(△)，提出了構建DFT結構函數的途徑［7－8］.順序失效符(SFS，Sequence Failure Symbol)“→”表示了事件發生的時序關系，LIU 通過引入 SFS，提出了 CSS模型［9］.CSS直接從基本事件的時序關系出發，給出了動態邏輯門的SFS表示方式.

本文圍繞DFT形式規約，在已有方法上進行了系統研究，提出了基于SFS的DFT形式規約方式.本文主要做了3個方面的工作:①系統地、嚴謹地重新定義了SFS，給出了SFS性質、規則和定理，利用SFS性質定理，證明了布爾邏輯和時序邏輯的統一性;②基于SFS，提出了任意形式DFT動態邏輯門的形式規約方法;③給出了任意形式DFT動態邏輯門SFS轉換的自動化算法.

1 SFS的形式框架

1.1 假 設

1)系統不可維修;

2)基本事件統計獨立.

1.2 定義與性質

定義1 用“→”表示弱偏序符號SFS，“→”用于連接基本事件、靜態或動態邏輯門，表示符號左邊先于右邊發生(即失效).

定義2 設V={v1，v2，…，vn}為含 n個元素的集合，稱{vi→vj}(i，j∈{1，2，…，n})為順序失效表達式(SFE，Sequence Failure Expression)［9］.空 SFE 表示為“?”.SFE 有下述性質(i，j，k，l∈{1，2，…，n}):

將SFE定義拓展為{v1→v2→…→vm}(m∈{1，2，…，n})，稱{v1→vj→…→vm}為長度為 m 的SFE.設給定時間t內，基本事件A的發生時間為T(A).對于基本事件 A1，A2，…，Am，{A1→A2→…→Am}的物理意義可描述為:0≤T(A1)≤T(A2)≤…≤T(Am)≤t，即 A1，A2，…，Am依次發生.同樣，{v1→v2→…→vm}具有性質1)～12)，特別地，強調以下拓展性質:

將性質16)拓展到任意2個SFE.設SFE1={v1→v2→…→vm}，SFE2={w1→w2→…→wn}，有:

定理1 相容性定理［10］.任意 1≤i1＜i2≤m，1≤j1＜ j2≤n，若 vi1=wj2，vi2=wj1，則 SFE1，SFE2是不相容的;否則是相容的.

接著介紹子集定理.先引入函數Element，其定義如下:任意 SFE={v1→v2→…→vm}，Element(SFE)={v1，v2，…，vm}，即 Element函數具有析取SFE中元素的作用，Element函數返回結果為集合.

引理1子集定理.SFE1是SFE2的子集，當且僅當 Element(SFE1)?Element(SFE2)，且 SFE1與SFE2是相容的.

引理2吸收定理.SFE1是 SFE2的子集，則{SFE1+SFE2}={SFE2}，{SFE2→ SFE1}={SFE2}.

至此，完成了SFS形式化框架的描述與構建.

2 SFT基于SFS的形式規約

SFT的邏輯門形式規約較簡單，通常由基本事件和連接基本事件的布爾邏輯符號“∪”“∩”等組成(分別用“+”“·”替換“∪”“∩”，“·”可省略).如輸入為A，B的“與門”的形式規約為A·B.將SFT所有邏輯門的形式規約整合，就得到其結構函數.結構函數溝通了基本事件和頂事件.如圖1所示的SFT［11］，其結構函數可表示為

其中X表示故障樹所有基本事件構成的集合.

運用布爾規則化簡:

圖1 SFT示意圖

于是得到了最小割集{A，B，C}，{C，E}，{A，D}.

將SFT的結構函數轉換為基于SFS代數框架的結構函數，步驟如下:

運用SFE吸收律，進一步化簡，得到

此即SFT在SFS代數框架下的形式規約.

直接利用SFE性質15)，對SFT結構函數的最簡形式φ(X)=ABC+CE+AD等價轉換，也可得到一致結果.由此可知，在SFS的代數框架內，SFT和DFT的形式規約是一致的，這便于將兩者統一起來研究.但一般不將SFT的結構函數轉換為含SFS的結構函數，因為后者形式復雜，不便于應用.

3 PAND，FDEP的SFS形式規約

DFT原始定義中包含了多種動態門，但SEQ與CSP本質上是一樣的［7］，且 CSP應用范圍更廣，因此本文不考慮SEQ.不同動態門有不同的SFS表達方式，以下依次分析.

3.1 PAND

PAND的輸出只與輸入事件的發生順序有關.在進行PAND的SFS轉換時，僅需將其輸入事件逐一列寫.例如:PAND(A，B，C，D，E)={((((A→B)→C)→D)→E)}={A→B→C→D→E}.PAND 的形式規約在文獻［5，7，9］中有較多闡述，這里不做進一步介紹.

3.2 FDEP

FDEP有1個觸發事件(可以是基本事件的輸入，或者其他邏輯門的輸出)和多個依賴事件.依據FDEP定義，觸發事件一旦發生，即使依賴事件未發生，也認為其發生，即依賴事件的失效不獨立影響FDEP結果的輸出.因此FEDP輸出發生的情形有2種:①觸發事件發生;②依賴事件發生，之后觸發事件發生.

如圖2所示FDEP，觸發事件為T，依賴事件為A，B，C.依上述分析，其輸出可以寫成:

圖2 FDEP示意圖

然而，利用SFE性質1)，有:T={T→T};再由性質5)和引理2，有:T+{A→T}={T→T}+{A→T}={T+A}→T={T+A}.于是，FDEP輸出的最簡形式為

上文從理論角度給出了證明:FDEP雖然具有動態特性，但是其形式規約可等價為靜態門.

再考慮一個較復雜的例子［9］.如圖 3a所示的是某系統的DFT，T和A由FDEP門相連，T失效將會導致A失效，而A，B均失效時將會導致頂事件發生.該DFT實際上可以轉換為圖3b所示的故障樹，即T，B均發生或者A，B均發生時將會導致頂事件發生.在此基礎上，得到{(T→B)+(B→T)+(B→A)+(A→B)}={TB+AB}.而利用本小節闡述的方法，FDEP的輸出為T+A，整個故障樹的輸出則為{T+A}·B={TB+AB}.

圖3 FDEP的SFS轉換示例

可見結果是一致的.一般地，在對FDEP門進行SFS轉換時，首先將FDEP門轉換為等價的靜態門.

4 XSP的SFS形式規約

依據儲備件的狀態，備件門分為3類:CSP，WSP和HSP.文獻［9］定義了睡眠因子α，α表示儲備件的工作狀態.當α=0時，儲備件為冷儲備狀態，冷備件不能在儲備期間失效;當α=1時，儲備件為熱儲備狀態，熱備件可以在儲備期間以正常失效率失效;當0＜α＜1時，儲備件為溫儲備狀態，溫備件可在儲備期間失效，但其失效率為正常失效率的α倍.CSP和HSP可以看成WSP的特殊情況，因此先分析WSP的 SFS形式規約.WSP門的儲備件可能被其他WSP共用，先分析無共用的情況.

4.1 無共用備件的WSP

儲備件有2種狀態:活躍(active)和休眠(dormant).若儲備件A在激活狀態失效，則將其記為Aa;在休眠狀態失效，則將其記為Ad［7］.再引進“獨立失效”概念.獨立失效是指:事件的失效與不依賴其他事件的發生［9］，如Bd→A→Ca中的事件B就發生了“獨立失效”.

設WSP的n個輸入事件依次為 x1，x2，…，xn，定義 f(xi)=i(i=1，2，…，n)，即將每個基本事件“綁定”一個非零自然數.轉換算法如下:

1)產生n!個x1，x2，…，xn任意排列的SFEi(i=1，2，…，n);

2)任意SFEi的第1個事件(假設為X)和最后一個事件(假設為Z)分別替換為Xd，Za，如果X=x1或Z=x1，則不作替換;

3)依次檢驗SFEi的第2～第n－1個事件是否發生“獨立失效”，若發生“獨立失效”，則將其替換為xd;否則替換為xa.

例如，若WSP含有輸入 A，B，C和 D，A為主件，B，C 和 D 依次為備件.{〈f(A)，f(B)，f(C)，f(D)〉}={〈1，2，3，4〉}，即 A，B，C 和 D 分別對應1，2，3和4.利用上述算法，首先得到24個SFE.任取A→C→B→D為研究對象，先用Da替換D.考慮C，f(C)＞f(B)，C發生了“獨立失效”，用Cd替換C;考慮B，f(B)＜f(D)，B未發生“獨立失效”，用Ba替換B.于是最終得到A→C→B→D 的 SFE:A→Cd→Ba→Da.類似地，對其他 23 個SFE進行自動化處理，可得到最終的SFE.

4.2 無共用備件的CSP和HSP

無共用備件的CSP的儲備件在儲備期間不能失效，所以任何儲備件都不能在主件失效之前失效，而且儲備件只能依次失效，因此只有1種SFE.如 CSP(A，B，C)={A→B→C}.無共用備件的HSP的儲備件儲備期間一直是“活躍”的，沒有“休眠”狀態，因此由輸入事件產生的任意排列組合即為其 SFE.顯然，利用 SFS性質15)容易知道，它與“與門”是等價的.

4.3 n個WSP共用1個備件

設有 n 個 WSP，WSPi(i=1，2，…，n)，每個WSP對應的主件為 xi，共用溫備件 S.對于任意WSP，易知其主件失效，且其備件失效，或無可替換備件時，WSP輸出產生.于是有:

其中，X表示第1個失效的主件.

4.4 有共用備件的CSP和HSP

對于CSP，只需刪掉與其同構的WSP模型中含Sd的SFE;對于HSP，同樣地，將所有 Sd替換成Sa，并對新生成的SFE簡化吸收即可.其他情況均可類比推導，這里不再贅述.

5 應用

利用本文方法研究HCSE(Hypothetical Computer System Example)［12］系統的形式規約，其結構如圖4所示.

圖4 HCSE系統結構圖

HCSE系統由處理器子系統(PSF，Processing System Failure)、內存子系統(MSF，Memory System Failure)、總線子系統(BSF，Bus System Failure)及應用子系統(AF，Application Failure)等4個子系統構成(對應4個子樹T1～T4).其中，PSF有2個冗余處理器A1，A2和1個冷備份處理器A，當A1，A2中任一處理器失效時，備份處理器A將替換失效處理器進行工作.A1，A2和A都是理想處理器.MSF有5個內存條，有3個正常就能保證內存系統正常.內存條通過內存接口單元與冗余總線相連，當內存接口失效時，與其連接的內存條將無法使用.M3連接了2個內存接口單元，意味著只要有1個內存接口單元正常，M3就能正常使用.BSF比較簡單，僅包含2條冗余總線，冗余總線均失效才導致總線系統失效.AF考慮了操作人員OP、硬件HW和軟件SW對系統的影響.操作人員通過運行在接口設備上的GUI與計算機實現連接，OP，HW和SW有一個失效就將導致系統失效.HCSE系統的DFT如圖5所示.

圖5 HCSE的DFT

5.1 T1

由4.3 節知:

SPARE1，SPARE2的輸出為邏輯“與”:

5.1.1 與 Merle 法比較

文獻［7］中，首先得到

利用不交化算法，進行化簡，得

往證 T1與T'1min是等價的.

證明 由 SFE性質{vi→vj}·{vj→vk}={vi→vj→vk}知:

冷備件不能在主件失效之前失效，因此上式中Aa→A1，Aa→A2是不符合實際物理意義的，于是

這與T'1min是一致的.

證畢

然而，Merle法中邏輯和時序混用，表意冗余、不明確;且Merle法得到的結構函數是子割序的邏輯與，并沒有形成最終的割序.而本文方法直接用時序建模，將布爾邏輯和時序邏輯統一起來，含義清晰，語義無重復.利用本文提出的SFE性質定理，能直接得到最終割序.

5.1.2 與Galileo軟件結果比較

Galileo軟件是DFT分析的主流軟件.將T1輸入 Galileo 軟件，得到割集結果{A，A1，A2}.這個結果包含了{A→A1→A2}和{A→A2→A1}這2個SFE，但這2個SFE是不符合物理意義的，因為冷備件A不能在主件A1，A2之前失效.究其原因，Galileo軟件采用了ZBDD法［13］，該方法將所有動態門轉換成了同構的“與門”，因此得到了相悖結果.而本文方法在建模粒度上較Galileo更細，也更符合實際情況.

5.2 余下子樹及整個DFT

T2中含有FDEP門，已證明FDEP可以等價于靜態門.因此T2～T4均可用SFT方法處理.T2～T4及整個DFT的SFS形式規約結果(TE)為

6 相關研究

Pandora法僅能對含優先失效關系的DFT進行分析，而且由于Pandora法引入的時序符號過多，相關時序表達式往往比較復雜，從而導致定性定量分析難以進行.盡管能利用約簡規則對表達式化簡，但欠缺規范的化簡過程帶來許多新問題.Merle提出了構建任意DFT結構函數的方法，但其同時考慮了基本事件之間的布爾邏輯(靜態)和時序邏輯(動態)關系，如“A先于B失效”在Merle法中表示為(A·B)·(A?B)，這種表達方式存在冗余，因此Merle提出的DFT形式規約方式并不是最優的.Rauzy［10］不考慮基本上事件之間的邏輯關系，直接從時序關系入手，改進了Merle法，但Rauzy方法仍然引進了2個時序符號，“，”和“;”，分別對應于Merle方法中的BF和SM，本質上講，Rauzy法和Merle法是一樣的;而且Rauzy并沒有系統地、完整地提出DFT的形式規約方法.CSS法［9］直接從基本事件的時序關系出發，給出了動態邏輯門的SFS表示方式.CSS法是對Pandora，Merle，Rauzy 等方法的較大改進，但是 CSS法也未提出完整的DFT形式化規約方法，且過于復雜的備件門的建模方法限制了其應用.

7 結論

DFT形式規約避免了DFT基于自然語言定義的模糊性和不一致性，便于更深入理解和研究DFT，特別是產生新的DFT分析思路.基于SFS的DFT形式規約將DFT時序特性的本質給予了精確刻畫，利用本文方法，可以得到任意DFT的基于SFS的形式規約.下一步研究將圍繞基于形式規約的DFT量化分析展開.

References)

［1］ Dugan JB，Bavuso S，Boyd M.Dynamic fault tree models for fault tolerant computer systems［J］.IEEE Transactions on Reliability，1992，41(3):363 －377

［2］ Boudali H，Dugan JB.A continuous-time Bayesian network reliability modeling，and analysis framework［J］.IEEE Transactions on Reliability，2006，55(1):86 －97

［3］ Dugan JB，Bavuso S，Boyd M.Fault trees and Markov models for reliability analysis of fault tolerant systems［J］.Reliability Engineering and System Safety，1993，39(3):291 －307

［4］ Codetta R D.The conversion of dynamic fault trees to stochastic Petri nets，as a case of graph transformation［J］.Electronic Notes in Theoretical Computer Science，2005，127(2):45 －60

［5］ Walker M，Papadopoulos Y.Pandora:the time of priority-AND gates［C］//12th IFAC Symposium on Information Control Problems in Manufacturing(INCOM 2006).Saint-Etienne，France:IFAC，2006:237 －242

［6］ Walker M，Papadopoulos Y.Qualitative temporal analysis:towards a full implementation of the fault tree handbook［J］.Control Engineering Practice，2009，17(10):1115 －1125

［7］ Merle G.Algebraic modeling of dynamic fault trees，contribution to qualitative and quantitative analysis［D］.Paris:Lurpa，ENS de Cachan，2010

［8］ Merle G，Roussel JM，Lesage J J.Algebraic determination of the structure functions of dynamic fault trees［J］.Reliability Engineering and System Safety，2011，96(2):267 －277

［9］ Liu Dong，Xing Weiyan，Zhang Chunyuan，et al.Cut sequence set generation for fault tree analysis［C］//Proceedings of International Conference on Embedded Software and Systems.Daegu，South Korea:［s.n.］，2007:58 －69

［10］ Rauzy A B.Sequence algebra，sequence decision diagrams and dynamic fault trees［J］.Reliability Engineering and System Safety，2011，96(7):785 －792

［11］金星，洪延姬.系統可靠性與可用性分析方法［M］.北京:國防工業出版社，2007:101 Jin Xing，Hong Yanji.Methods of system reliability and availability analysis［M］.Beijing:National Defense Industry Press，2007:101(in Chinese)

［12］ Vesely W E，Stamatelatos M，Dugan JB，et al.Fault tree handbook with aerospace applications［M］.Washington DC:NASA Office of Safety and Mission Assurance，2002:157 －161

［13］ Minato S.Zero-suppressed BDDs for set manipulation in combinatorial problems［C］//Proceedings of 30th Design Automation Conference(DAC＇93).Texas:ACM/IEEE，1993:272 －277