離散事件系統(tǒng)故障的極小觀測序列

歐陽丹彤　李江娜　耿雪娜

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

關(guān)鍵詞：離散事件系統(tǒng)；故障模型；極小觀測序列模型；故障診斷

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A

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

本文給出了判定系統(tǒng)故障發(fā)生的極小觀測序列模型G_mos以及建立故障極小觀測序列模型的算法（約束轉(zhuǎn)換法）。對(duì)于給定的離散事件系統(tǒng)，首先建立該系統(tǒng)模型相對(duì)應(yīng)的故障模型G_f，然后在故障模型基礎(chǔ)上求得系統(tǒng)故障的極小觀測序列模型G_mos。通過故障的極小觀測序列模型可以得到某個(gè)或某類故障發(fā)生的極小觀測序列集。這樣，系統(tǒng)在線實(shí)時(shí)診斷時(shí)，將傳感器逐步接收到的觀測與系統(tǒng)故障的極小觀測序列模型進(jìn)行比對(duì)，若滿足該模型中的某個(gè)觀測序列，則說明系統(tǒng)發(fā)生了該序列終止?fàn)顟B(tài)標(biāo)簽相對(duì)應(yīng)的故障；否則，系統(tǒng)判定沒有故障發(fā)生。根據(jù)系統(tǒng)故障的極小觀測序列模型，能在故障發(fā)生后盡快地判定出系統(tǒng)發(fā)生了哪些故障。

本文結(jié)構(gòu)如下：第1部分給出了相關(guān)概念和定義；第2部分給出了故障極小觀測序列模型的構(gòu)建算法（約束轉(zhuǎn)換法）；第3部分給出了相關(guān)證明；第4部分給出了實(shí)驗(yàn)及分析；第5部分對(duì)本文工作進(jìn)行總結(jié)。

1 預(yù)備知識(shí)

本部分給出了文中相關(guān)的概念及模型的定義。

定義1（系統(tǒng)模型）

系統(tǒng)模型是一個(gè)有限自動(dòng)機(jī)G_s=（S，E，T，S₀，S_f）。其中S為狀態(tài)集合；S₀為初始狀態(tài)；S_f為終止?fàn)顟B(tài)集合；T為狀態(tài)轉(zhuǎn)換函數(shù)集合，T→S×E×S。E為事件集合，包括可觀測事件集E和不可觀測事件集E_uo，E_uo又分為故障事件集和非故障事件集。

定義2（觀測可達(dá)） 狀態(tài)s_i∈S經(jīng)事件e∈E。可達(dá)狀態(tài)s_i∈s（其中s_i和s_j間事件除e外還可存在非連續(xù)的不可觀測事件）則稱s_i在e下可達(dá)，記作s_i[e]。狀態(tài)s_i稱為觀測可達(dá)狀態(tài)，記作R（s_i，e）。

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

為了便于對(duì)系統(tǒng)模型中故障進(jìn)行篩選，給出了故障模型的定義。

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

由于傳感器無法觀測到不可觀測事件，現(xiàn)定義觀測。

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

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

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

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

根據(jù)模型中狀態(tài)標(biāo)簽的不同，提出了定義模糊狀態(tài)和標(biāo)簽可達(dá)。

定義9（模糊狀態(tài)） 狀態(tài)x_i∈X中既含標(biāo)簽F∈F^*又含標(biāo)簽N，則x_i為模糊狀態(tài)。

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

T_mos（x_i，e）定義之前，先定義局部轉(zhuǎn)換函數(shù)T_mos（（s_ij，l（s_ij）），e），來表示狀態(tài)間通過事件連接的關(guān)系（其中（s_ij，l（s_ij））∈x_i）。

根據(jù)以上對(duì)3種狀態(tài)下轉(zhuǎn)換函數(shù)的定義，可知終止?fàn)顟B(tài)可由僅含N標(biāo)簽狀態(tài)、模糊狀態(tài)以及僅含F(xiàn)標(biāo)簽狀態(tài)經(jīng)轉(zhuǎn)換函數(shù)T_mos得到。

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

2.1 故障模型

建立系統(tǒng)故障的極小觀測序列模型需要給定系統(tǒng)的故障模型，本節(jié)首先給出了算法1（篩選法）用于構(gòu)建系統(tǒng)的故障模型。

算法1構(gòu)建系統(tǒng)模型Gra_s的故障模型Gra_f

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

2.2 極小觀測序列模型構(gòu)建算法

根據(jù)系統(tǒng)的故障模型建立判定故障發(fā)生的極小觀測序列模型。本節(jié)給出了算法2（約束轉(zhuǎn)換法）用于構(gòu)建系統(tǒng)故障模型的極小觀測序列模型。

算法2 構(gòu)建系統(tǒng)故障模型Gra_f的極小觀測序列模型Gra_mos

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

算法2中trans（（s_i，z（s_i）），P）表示狀態(tài)的局部轉(zhuǎn)換函數(shù)。

函數(shù)trans（（s_i，l（s_i）），P）的第1行R（s_i，e）表示狀態(tài)s_i通過事件e所有可達(dá)狀態(tài)構(gòu)成的集合；2-3行指故障不包含在路徑t（s_i，r）時(shí)，轉(zhuǎn)換后標(biāo)簽不變；4-8行指故障包含在路徑時(shí)，轉(zhuǎn)換后狀態(tài)標(biāo)簽的情況：5-6行指原有狀態(tài)標(biāo)簽為N時(shí)，轉(zhuǎn)換后狀態(tài)標(biāo)簽為故障標(biāo)簽；7-8行指原有狀態(tài)標(biāo)簽為故障標(biāo)簽時(shí)，轉(zhuǎn)換后狀態(tài)標(biāo)簽為兩個(gè)標(biāo)簽的并集。

3 證明

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

證（正確性） 極小觀測序列模型中終止?fàn)顟B(tài)出現(xiàn)在三種狀態(tài)轉(zhuǎn)換后：模糊狀態(tài)、僅含有N標(biāo)簽的狀態(tài)以及僅含有F標(biāo)簽的狀態(tài)。由于系統(tǒng)是可診斷的，則故障標(biāo)簽一定可以分離。對(duì)于模糊狀態(tài)（或者僅含有F標(biāo)簽的狀態(tài)）經(jīng)轉(zhuǎn)換到終止?fàn)顟B(tài)的過程為故障分離的過程，而且首次進(jìn)行分離，所以滿足極小性；而對(duì)于僅含有N標(biāo)簽的狀態(tài)，經(jīng)轉(zhuǎn)換到終止?fàn)顟B(tài)的過程為正常狀態(tài)首次到達(dá)的含有F標(biāo)簽的狀態(tài)，所以滿足極小性?？梢?，極小觀測序列模型中的序列滿足極小性。

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

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

4 實(shí)驗(yàn)及實(shí)例分析

4.1 實(shí)驗(yàn)

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

實(shí)驗(yàn)數(shù)據(jù)表明，在相同條件的系統(tǒng)中，Mos診斷時(shí)間均比Ori短，為了更形象地說明兩者的時(shí)間差距，診斷時(shí)間差圖3如下。

由圖3可得，對(duì)于單故障系統(tǒng)，Mos的故障診斷時(shí)間均比Ori的故障診斷時(shí)間短，即Mos下，系統(tǒng)有較高的診斷效率。尤其對(duì)于節(jié)點(diǎn)個(gè)數(shù)多且故障極小觀測序列較長的系統(tǒng)模型，Mos比Ori在線診斷時(shí)間有更好的優(yōu)勢(shì)。

實(shí)驗(yàn)表明：離線建立系統(tǒng)的極小觀測序列模型用于在線故障診斷，能有效地提高系統(tǒng)在線故障診斷的效率。既能夠盡快地發(fā)現(xiàn)故障發(fā)生，也能盡快地排除故障的發(fā)生。

4.2 實(shí)例分析

圖4為多故障系統(tǒng)模型G5，根據(jù)算法2得到該系統(tǒng)故障的極小觀測序列模型G_mos，如圖5所示?？傻霉收蟜₁的極小觀測序列為abc，acb，故障f_i的極小觀測序列為abb。

系統(tǒng)在初始狀態(tài)0下，當(dāng)接收到觀測a時(shí)，在G_mos中存在可達(dá)狀態(tài)，當(dāng)再接收到觀測c，也有可達(dá)狀態(tài)，若繼續(xù)接收到觀測6到達(dá)G_mos中的帶標(biāo)簽F₁的終止節(jié)點(diǎn)，此時(shí)可以判定故障f₁發(fā)生。同理，當(dāng)接收到觀測序列abc，可判定故障f₁發(fā)生；接收到觀測abb，可判定故障f_i發(fā)生。

5 結(jié)論

本文提出了系統(tǒng)故障的極小觀測序列模型，用于提高系統(tǒng)在線故障診斷的效率。文中給出了相關(guān)概念定義以及構(gòu)建系統(tǒng)故障的極小觀測序列模型的算法，而且通過對(duì)比實(shí)驗(yàn)證明了將故障的極小觀測序列模型用于系統(tǒng)在線故障診斷，可以有效地減少系統(tǒng)故障診斷的時(shí)間，從而使系統(tǒng)盡快地判定有無故障發(fā)生。