歐陽丹彤, 羅知雨, 耿雪娜, 張立明

(1. 吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室, 長春 130012; 2. 長春理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 長春 130022)

基于模型診斷(model-based diagnosis, MBD)方法具有設(shè)備獨(dú)立性、 易更新和維護(hù)等特點(diǎn), 因此已逐漸成為故障診斷領(lǐng)域的核心方法, 很多領(lǐng)域都使用該方法進(jìn)行系統(tǒng)診斷[1], 而且MBD問題可以轉(zhuǎn)換為可滿足性(SAT)[2-3]問題, 或使用文獻(xiàn)[4]的方法進(jìn)行求解. 文獻(xiàn)[4]給出了可診斷性的充要條件. 在MBD中, 模型是否正確影響診斷的效果及效率, 不同模型條件下的可診斷性主要針對(duì)不同系統(tǒng)下的可診斷性問題. 常見的系統(tǒng)模型有離散事件系統(tǒng)(discrete event systems, DES)[5]、 模糊DES[4]及分布式DES[6]等. 由于系統(tǒng)的復(fù)雜性逐漸增加, 模型的規(guī)模也逐漸增加, 為了降低模型規(guī)模及復(fù)雜系統(tǒng)的計(jì)算量, 人們提出了分布式系統(tǒng). 在分布式系統(tǒng)中, 為了解決對(duì)大規(guī)模系統(tǒng)的全局模型進(jìn)行可診斷性分析的困難, 全局模型被分割成多個(gè)有相同通信事件的局部模型或組件, 每個(gè)局部模型獨(dú)立分析其可診斷性, 由于硬件原因, 局部可診斷性與全局可診斷性不一定相同, 因此分布式系統(tǒng)通過通信事件進(jìn)行同步, 以獲得全局模型的可診斷性. 一些經(jīng)典的DES診斷方法同樣在分布式系統(tǒng)診斷中使用, 如診斷器[4]、 同步[7]等方法. 同時(shí), 對(duì)分布式系統(tǒng)的診斷方法進(jìn)行了許多改進(jìn)[8-10], 從而更快速、 更準(zhǔn)確地判定系統(tǒng)的可診斷性.

盡管在故障發(fā)生一段時(shí)間后可診斷的系統(tǒng)才能檢測到該故障發(fā)生, 但如果沒有及時(shí)完成檢測, 則發(fā)生的故障可能會(huì)危害系統(tǒng)本身及人身財(cái)產(chǎn)安全. 為了避免安全事件的發(fā)生, 人們希望在系統(tǒng)執(zhí)行被禁止事件序列前檢測到故障的發(fā)生, 基于此, Paoli等[11]提出了判定DES的安全可診斷性. 在文獻(xiàn)[11]的基礎(chǔ)上, 劉富春等[12-14]提出了判定模糊DES、 隨機(jī)DES的安全可診斷性問題及對(duì)DES安全可診斷性的改進(jìn)算法.

本文提出一種分布式DES的安全可診斷性算法. 對(duì)于給定的分布式系統(tǒng)及被禁止事件序列集合, 首先使用同步[4]的方法得到系統(tǒng)的全局模型, 然后判斷系統(tǒng)對(duì)給定故障是否可診斷, 確定系統(tǒng)對(duì)給定故障可診斷后, 構(gòu)建系統(tǒng)對(duì)給定故障及相應(yīng)被禁止事件集合的安全診斷器來判斷系統(tǒng)在故障發(fā)生后是否發(fā)生被禁止事件序列, 假設(shè)未發(fā)生故障或故障發(fā)生后未發(fā)生被禁止事件序列, 則系統(tǒng)是可診斷的且是安全可診斷的, 否則系統(tǒng)不是安全可診斷的.

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

1.1 分布式離散事件系統(tǒng)及其可診斷性

圖1 由3個(gè)局部模型構(gòu)成的系統(tǒng)S1Fig.1 System S1 composed of three local models

定義1(局部模型)[6]第i個(gè)局部模型Γi定義為一個(gè)有限狀態(tài)自動(dòng)機(jī)Γi=(Qi,Ei,Ti,q0i), 其中:Qi為有限狀態(tài)的集合;Ei為事件的集合, 包含3個(gè)互不相交的集合, 分別為故障事件集合Fi、 可觀測事件集合Oi和通信事件集合Ci;Ei,Oi,Fi只發(fā)生在Γi中;Ti為轉(zhuǎn)移函數(shù)集合,Ti?Qi×Ei×Qi;q0i為系統(tǒng)的初始狀態(tài).

其中:ψ表示同步事件集合且ε?ψ;ev(ti)表示ti的事件標(biāo)簽.

圖2 局部模型Γ2自同步得到的系統(tǒng)GFig.2 System G obtained by self-synchronizing local model Γ2

圖2為圖1中Γ2的診斷器以可觀測事件為同步事件, 自同步得到系統(tǒng)G. 系統(tǒng)內(nèi)不同的局部模型間通過兩個(gè)局部模型間相同的通信事件進(jìn)行同步轉(zhuǎn)換, 可得到系統(tǒng)的全局模型. 假設(shè)系統(tǒng)由n(n≥1)個(gè)局部模型組成, 則系統(tǒng){Γ1,Γ2,…,Γn}的全局模型定義如下.

Cj為通信事件.

定義3(局部可診斷性)[6]若局部模型Γ中發(fā)生故障fi后又發(fā)生了有限個(gè)可觀測事件, 則fi在該局部模型中是可診斷的, 即fi是局部可診斷的, 即

其中:pf表示以初始狀態(tài)p0為起點(diǎn), 以fi發(fā)生后的狀態(tài)為終點(diǎn)的路徑;sf表示pf的后續(xù)路徑; Obs表示可觀測投影的映射函數(shù); Obs-1表示可觀測投影的逆映射函數(shù)[2].

由文獻(xiàn)[6]知, 如果fi是局部可診斷的, 則fi是全局可診斷的.

1.2 離散事件系統(tǒng)的安全可診斷性

系統(tǒng)中可以發(fā)生多類故障事件, 每類故障事件包含多個(gè)故障事件, 假設(shè)對(duì)于第i類型故障fi的被禁止事件序列集合為Φi,Φi∈E*, 其中E*為E的閉包[2]. 為了滿足安全性, 在某類故障fi發(fā)生后, 避免系統(tǒng)執(zhí)行Φi.

其中[s∈Ψ(Efi)](i=1,2,…,m)}([v∈Φi,v為u的子序列]),

其中:Ψ(Efi)表示以第i類故障事件結(jié)尾的路徑;L/s表示語言L中發(fā)生在事件s的后續(xù)路徑.

如果一個(gè)系統(tǒng)是安全可診斷的, 則該系統(tǒng)首先是可診斷的.

定義5(可診斷性)[4]語言L可診斷的條件如下:

(?i∈Πf)(?ni∈)(?s∈Ψ(Efi))(?t∈L/s)(‖t‖≥ni?D),

其中D為ω∈Obs-1[Obs(st)]?Efi∈ω.

定義6(Fi確定與不確定性)[4]若診斷器中存在狀態(tài)q, ?(x,l)∈q滿足Fi∈l, 則稱q是Fi確定的. 反之, 若診斷器中存在狀態(tài)q,?(x,l),(y,l′)∈q且Fi∈l,Fi?l′, 則稱q是Fi不確定的.

定義7(安全可診斷)[11]語言L安全可診斷的條件如下:

1) 可診斷性條件同定義5;

2 安全診斷器的構(gòu)造

定義8(非法語言標(biāo)簽)[11]非法語言的標(biāo)簽函數(shù)為

其中：Bi表示故障發(fā)生后又執(zhí)行了相應(yīng)的被禁止事件串;S表示無故障事件發(fā)生或故障事件發(fā)生后未執(zhí)行相應(yīng)的被禁止事件.

通過非法語言的標(biāo)簽函數(shù)能構(gòu)造系統(tǒng)的非法語言識(shí)別器.

定義9(非法語言識(shí)別器) 對(duì)系統(tǒng)Γi中發(fā)生的故障fi及對(duì)應(yīng)的被禁止事件集合Φi構(gòu)造的非法語言識(shí)別器Gr為有限狀態(tài)自動(dòng)機(jī)Gr={Qr,E,Tr,q0r}, 其中：Qr為狀態(tài)空間,

Qr∈Q×πl(wèi)(s),πl(wèi)(s)=π(s)×l(s),

l(s)為故障標(biāo)簽,

q0r=(ε,N-S);Tr：Qr×E×Qr為狀態(tài)轉(zhuǎn)換函數(shù),

Tr((s,πl(wèi)(s)),σ)=(t,πl(wèi)(t)),s,t∈Qr,σ∈E,

轉(zhuǎn)換規(guī)則為

通過非法語言識(shí)別器可獲得添加安全標(biāo)簽的自動(dòng)機(jī)：

Γm=Γi×G1×…×Gm=(Qm,E,Tm,q0m),

其中Γm中的一個(gè)狀態(tài)

z=[q,(s1,π(s1)),…,(sm,π(sm))].

圖3為G對(duì)f2,{o3}構(gòu)造的非法語言識(shí)別器Gr.

定義10(安全診斷器) 若存在自動(dòng)機(jī)γ=(Q,E,T,q0), 則該自動(dòng)機(jī)對(duì)fi和Φi的安全診斷器為

圖3 非法語言識(shí)別器GrFig.3 Illegal language recognizer Gr

圖4 安全診斷器

1)q為Fi不確定狀態(tài);

2)q,q′狀態(tài)如下:

①q為Fi確定狀態(tài);

②q′為Fi不確定狀態(tài).

因圖4中存在F2不確定狀態(tài)[(y3,F2-B2),(y3,N-S)], 因此由定理1知該系統(tǒng)不是安全可診斷的.

3 分布式離散事件系統(tǒng)判定安全可診斷算法

3.1 分布式離散事件系統(tǒng)的安全可診斷性

判斷系統(tǒng)是否安全可診斷前, 首先需將局部模型通過同步操作構(gòu)成系統(tǒng)的全局模型, 根據(jù)定義2, 可由下列算法構(gòu)建系統(tǒng)的全局模型.

算法1構(gòu)建全局模型算法.

Function: GS( );

Input: 局部模型{Γ1,Γ2,…,Γn};

Output:Γ;

if 系統(tǒng)安全可診斷, return系統(tǒng)可診斷;

if系統(tǒng)不可診斷, return 系統(tǒng)不可診斷;

Begin

1) Initialization:A←{Γ1,Γ2,…,Γn}{Γi};

2) whileA≠? do

3) 從A取出與Γ1有相同通信事件Ci的Γi;

4)Γi←Synch(Γi,Γj,Sync(ti,tj),Ci);

5) end while

6) AbstractKeyPath(Γi);

7)Γ←Γi;

8) DR(Γ);

9) Check1(Γ);

End.

算法1中步驟4)使用函數(shù)Synch(Γi,Γj,Sync(ti,tj))先將兩個(gè)局部模型同步獲得一個(gè)新的模型, 再將結(jié)果保存在Γi中； 步驟6)中AbstractKeyPath(Γi)為對(duì)系統(tǒng)剪枝保留關(guān)鍵路徑, 即只保留包含故障的語言及可診斷性與其相同的語言; 步驟8)中DR(Γ)為構(gòu)建診斷器； 步驟9)中Check1(Γ)為檢查系統(tǒng)是否安全可診斷, Check1( )可能有兩種結(jié)果：

1) 若系統(tǒng)包含F(xiàn)i不確定狀態(tài)環(huán), 則返回系統(tǒng)不可診斷;

2) 若系統(tǒng)不包含F(xiàn)i不確定狀態(tài)環(huán), 則返回系統(tǒng)可診斷.

若系統(tǒng)可診斷, 則根據(jù)定義8和定理1構(gòu)建系統(tǒng)的安全診斷器, 用以判斷系統(tǒng)是否安全可診斷.

算法2安全可診斷性判斷算法.

Function: SDR( );

Inputs:Γ;

故障事件fi;

被禁止事件集合Φi;

Outputs: if 系統(tǒng)安全可診斷, return系統(tǒng)安全可診斷;

if 系統(tǒng)不可安全診斷, return系統(tǒng)不可安全診斷;

Begin

1) Lable(Γ);

2) DeleteUnobEvents(Γ);

3) Check(Γ);

End.

算法2中步驟1)函數(shù)Lable(Γ)為使用前狀態(tài)與相應(yīng)事件, 根據(jù)定義9計(jì)算非法語言標(biāo)簽; 步驟2)中函數(shù)DeleteUnobEvents(Γ)為刪除系統(tǒng)中的不可觀察事件, 只保留可觀測路徑; 步驟3)中函數(shù)Check( )為檢查系統(tǒng)是否安全可診斷, Check( )可能有兩種結(jié)果:

1) 若系統(tǒng)不滿足定理1, 則返回系統(tǒng)不可安全診斷;

2) 若系統(tǒng)滿足定理1, 則返回系統(tǒng)安全可診斷.

3.2 復(fù)雜性分析

設(shè)全局系統(tǒng)最大狀態(tài)數(shù)量為

(|Q1|×|Q2|×…×|Qm|×…×|Qn|),

最大轉(zhuǎn)換數(shù)量為

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

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

實(shí)驗(yàn)采用的測試環(huán)境為: Dell Intel(R) Core(TM) i5-3470 CPU @ 3.20 GHz, Windows 64位系統(tǒng), 8 GB內(nèi)存, 920 GB硬盤, eclipse編譯器.

圖5 系統(tǒng)模型S2Fig.5 Model of system S2

圖6 系統(tǒng)模型S3Fig.6 Model of system S3

表1 診斷前后狀態(tài)數(shù)對(duì)比

4.2 實(shí)例分析

圖7 全局模型G1Fig.7 Global model G1

圖8 安全診斷器

綜上所述, 本文提出了一種分布式DES安全可診斷性的判斷算法, 通過使用非法語言識(shí)別器, 添加安全標(biāo)簽獲得安全診斷器, 從而得到診斷結(jié)果. 實(shí)驗(yàn)結(jié)果表明: 用該算法進(jìn)行安全可診斷性判斷的時(shí)間在可接受范圍內(nèi); 在空間上, 最好的實(shí)例狀態(tài)數(shù)縮減到7倍, 平均狀態(tài)數(shù)縮減了5.45倍.