離散事件系統故障的極小觀測序列

歐陽丹彤　李江娜　耿雪娜

摘要：為了提高可診斷離散事件系統故障的在線診斷效率，本文從判定故障發生的可觀測事件的角度，提出了故障極小觀測序列方法。文中選取有限狀態自動機對離散事件系統進行建模。首先，在離線狀態下，建立系統的故障模型，以排除對于判定系統故障無關的路徑。然后，根據故障模型進一步建立判定系統故障的極小觀測序列模型。當離散事件系統在線診斷時，僅需將逐步增加的在線觀測事件序列與故障的極小觀測序列模型進行比對。若能找到滿足該模型的任何一條路徑，則說明路徑終止狀態上故障標簽對應的系統故障發生；否則，說明系統無故障發生。文中對可診斷離散事件系統進行實驗對比，通過故障的極小觀測序列模型能盡快判定有無故障發生，以及發生了哪些故障。該模型能有效地縮小系統在線診斷的時間，提高系統在線診斷的效率。

關鍵詞：離散事件系統；故障模型；極小觀測序列模型；故障診斷

中圖分類號：TP301 文獻標識碼：A

近些年來，基于模型診斷方法成為人工智能領域比較熱門的研究課題。基于模型診斷方法具有設備獨立性，易于更新和維護。因而，不少領域使用基于模型診斷方法對離散事件系統進行診斷研究，比如大型通信網絡故障診斷、配電站故障診斷、航天器故障診斷、汽車故障診斷、軟件測試等。基于模型診斷中診斷相關的極小化研究增強了診斷的精細程度。診斷相關的極小化研究包括：極小診斷、極小故障事件集、判定可診斷性的極小事件集等。極小診斷是在部件級別上對故障部件的候選沖突集進行求碰集，從而得到故障部件的診斷結果。使用不同的方法求碰集，得到系統極小診斷的效率有所不同。例如，通過減少一致性檢測的數量，避免對極小化沖突集的計算，求解系統的極小診斷。極小故障事件集則考慮故障事件的先后順序對系統的影響，將故障事件構成的序列進行極小化，從而得到系統故障事件的極小序列診斷。而可診斷性的極小事件集則是通過減少可觀測事件的種類，使系統仍保持可診斷性，求解保證系統可診斷性的極小事件集。以上極小化相關研究都未曾從在線診斷角度考慮如何盡快地確定發生的故障。為了提高系統在線診斷的效率，使在線診斷時盡快地判定出故障的發生，本文對判定故障發生的可觀測事件序列進行研究并建立相應的模型，使得在系統故障發生后盡快確定該故障的發生。假定待測的離散事件系統是完備且可診斷的。

本文給出了判定系統故障發生的極小觀測序列模型G_mos以及建立故障極小觀測序列模型的算法（約束轉換法）。對于給定的離散事件系統，首先建立該系統模型相對應的故障模型G_f，然后在故障模型基礎上求得系統故障的極小觀測序列模型G_mos。通過故障的極小觀測序列模型可以得到某個或某類故障發生的極小觀測序列集。這樣，系統在線實時診斷時，將傳感器逐步接收到的觀測與系統故障的極小觀測序列模型進行比對，若滿足該模型中的某個觀測序列，則說明系統發生了該序列終止狀態標簽相對應的故障；否則，系統判定沒有故障發生。根據系統故障的極小觀測序列模型，能在故障發生后盡快地判定出系統發生了哪些故障。

本文結構如下：第1部分給出了相關概念和定義；第2部分給出了故障極小觀測序列模型的構建算法（約束轉換法）；第3部分給出了相關證明；第4部分給出了實驗及分析；第5部分對本文工作進行總結。

1 預備知識

本部分給出了文中相關的概念及模型的定義。

定義1（系統模型）

系統模型是一個有限自動機G_s=（S，E，T，S₀，S_f）。其中S為狀態集合；S₀為初始狀態；S_f為終止狀態集合；T為狀態轉換函數集合，T→S×E×S。E為事件集合，包括可觀測事件集E和不可觀測事件集E_uo，E_uo又分為故障事件集和非故障事件集。

定義2（觀測可達） 狀態s_i∈S經事件e∈E。可達狀態s_i∈s（其中s_i和s_j間事件除e外還可存在非連續的不可觀測事件）則稱s_i在e下可達，記作s_i[e]。狀態s_i稱為觀測可達狀態，記作R（s_i，e）。

圖2中表示觀測可達的幾種情況，其中a，b∈E_o，v，u∈E_uo，則有R（S₀，a）={S₁}，R（S₁，b）={S₂，S₃}，R（S₃，c）={S₅}。

為了便于對系統模型中故障進行篩選，給出了故障模型的定義。

為提出建立故障模型的算法，給出以下定義。

由于傳感器無法觀測到不可觀測事件，現定義觀測。

本文目的是求解系統故障的極小觀測序列模型，因此定義了故障的極小觀測序列以及故障的極小觀測序列模型。

定義7（故障的極小觀測序列）

存在可觀測事件序列o₁o₂…o_n和o₁o₂…o_no_n+1…o_n+k（其中o₁，…，o_n+k∈E₀且k>0）均可判定某故障發生，而序列o₁o₂…o_n-1無法確定該故障發生，則稱序列o₁o₂…o_n為該故障的極小觀測序列。所有故障的極小觀測序列構成的模型稱為系統故障的極小觀測序列模型。

圖1當接收到觀測a，無法判定f發生，a6能判斷f發生，abc也可以，可見a6為判定f發生的一個極小觀測序列。

根據模型中狀態標簽的不同，提出了定義模糊狀態和標簽可達。

定義9（模糊狀態） 狀態x_i∈X中既含標簽F∈F^*又含標簽N，則x_i為模糊狀態。

定義10（標簽可達） 模糊狀態x_i∈X，存在可觀測事件e∈E_o'，若僅使得帶標簽N的狀態s_ij其中（s_ij，N）∈i）可達，稱x_i在e下N標簽可達；若僅使帶標簽F∈F^*的狀態可達，稱x_i在e下F標簽可達；若同時存在，稱x_i在e下NF標簽可達。

T_mos（x_i，e）定義之前，先定義局部轉換函數T_mos（（s_ij，l（s_ij）），e），來表示狀態間通過事件連接的關系（其中（s_ij，l（s_ij））∈x_i）。

根據以上對3種狀態下轉換函數的定義，可知終止狀態可由僅含N標簽狀態、模糊狀態以及僅含F標簽狀態經轉換函數T_mos得到。

2 故障的極小觀測序列模型

2.1 故障模型

建立系統故障的極小觀測序列模型需要給定系統的故障模型，本節首先給出了算法1（篩選法）用于構建系統的故障模型。

算法1構建系統模型Gra_s的故障模型Gra_f

算法1中2-5行將系統模型圖Gra_s中故障路徑集合t_f加入到圖Gra_f。7-9行每條故障路徑t_fi∈t_f，找到其預故障路徑t_pf，取得與觀測obs（t_pfi）有相同部分觀測的路徑t，將t加入到圖Gra_f中。

2.2 極小觀測序列模型構建算法

根據系統的故障模型建立判定故障發生的極小觀測序列模型。本節給出了算法2（約束轉換法）用于構建系統故障模型的極小觀測序列模型。

算法2 構建系統故障模型Gra_f的極小觀測序列模型Gra_mos

算法2中第2行的isNotEnd（X_i）表示X_i節點不為終止節點，isTerminal（X_i）表示X_i節點為終端節點。第7行的Gra_mos←（X_i-→xH_i+1）表示將由狀態X_i通過事件e到狀態XH_i+1的狀態轉換加入到極小觀測序列模型的圖Gra_mos中。3-9行表示Gra_mos中僅含N標簽的節點進行狀態轉換。10-23行表示模糊節點進行狀態轉換，包括NF標簽可達（12-16行）和F標簽可達（17-21行）。24-30行表示Gra_mos中僅含F標簽的節點進行狀態轉換。

算法2中trans（（s_i，z（s_i）），P）表示狀態的局部轉換函數。

函數trans（（s_i，l（s_i）），P）的第1行R（s_i，e）表示狀態s_i通過事件e所有可達狀態構成的集合；2-3行指故障不包含在路徑t（s_i，r）時，轉換后標簽不變；4-8行指故障包含在路徑時，轉換后狀態標簽的情況：5-6行指原有狀態標簽為N時，轉換后狀態標簽為故障標簽；7-8行指原有狀態標簽為故障標簽時，轉換后狀態標簽為兩個標簽的并集。

3 證明

算法2求得的極小觀測序列模型包含系統中所有故障的所有極小觀測序列。

證（正確性） 極小觀測序列模型中終止狀態出現在三種狀態轉換后：模糊狀態、僅含有N標簽的狀態以及僅含有F標簽的狀態。由于系統是可診斷的，則故障標簽一定可以分離。對于模糊狀態（或者僅含有F標簽的狀態）經轉換到終止狀態的過程為故障分離的過程，而且首次進行分離，所以滿足極小性；而對于僅含有N標簽的狀態，經轉換到終止狀態的過程為正常狀態首次到達的含有F標簽的狀態，所以滿足極小性。可見，極小觀測序列模型中的序列滿足極小性。

（完備性） 極小觀測序列模型是根據故障模型得到的，需要證明故障模型是完備的。故障模型由系統模型中的故障路徑以及與預故障路徑相同部分觀測的路徑組成。故障的極小觀測序列一定存在于故障路徑中，故障發生后，影響故障發生判定的路徑只有與預故障路徑相同部分觀測的路徑，所以故障模型是完備的，則極小觀測序列模型也是完備的。

（復雜性分析） 極小觀測序列模型的在線診斷時間取決于實時接收的觀測與離線建立的極小序列模型的比較時間，當觀測序列長度為n時，比較時間復雜度為0（n），故在線診斷的時間復雜度為0（n）。

4 實驗及實例分析

4.1 實驗

由于本文的研究建立在完備且可診斷的離散事件系統基礎上，且此類研究沒有統一的benchmark數據測試集，故選取相關論文中滿足本文假設的部分系統模型以及滿足條件的系統模型進行以下兩種對比實驗。情形1：使用系統故障的極小觀測序列模型，記作Mos；情形2：不使用故障的極小觀測序列模型，記作Ori。對于相同長度的故障極小觀測序列且相同節點個數的系統（單故障系統）進行實驗，分別得到Mos和Ori的在線診斷的時間如表1所示：

實驗數據表明，在相同條件的系統中，Mos診斷時間均比Ori短，為了更形象地說明兩者的時間差距，診斷時間差圖3如下。

由圖3可得，對于單故障系統，Mos的故障診斷時間均比Ori的故障診斷時間短，即Mos下，系統有較高的診斷效率。尤其對于節點個數多且故障極小觀測序列較長的系統模型，Mos比Ori在線診斷時間有更好的優勢。

實驗表明：離線建立系統的極小觀測序列模型用于在線故障診斷，能有效地提高系統在線故障診斷的效率。既能夠盡快地發現故障發生，也能盡快地排除故障的發生。

4.2 實例分析

圖4為多故障系統模型G5，根據算法2得到該系統故障的極小觀測序列模型G_mos，如圖5所示。可得故障f₁的極小觀測序列為abc，acb，故障f_i的極小觀測序列為abb。

系統在初始狀態0下，當接收到觀測a時，在G_mos中存在可達狀態，當再接收到觀測c，也有可達狀態，若繼續接收到觀測6到達G_mos中的帶標簽F₁的終止節點，此時可以判定故障f₁發生。同理，當接收到觀測序列abc，可判定故障f₁發生；接收到觀測abb，可判定故障f_i發生。

5 結論

本文提出了系統故障的極小觀測序列模型，用于提高系統在線故障診斷的效率。文中給出了相關概念定義以及構建系統故障的極小觀測序列模型的算法，而且通過對比實驗證明了將故障的極小觀測序列模型用于系統在線故障診斷，可以有效地減少系統故障診斷的時間，從而使系統盡快地判定有無故障發生。