劉富春 唐順橋 趙 銳 鄧秀勤 崔洪剛

(1.廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,廣東廣州 510006;2.廣東工業(yè)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院,廣東廣州 510006;3.廣東省東源縣科技創(chuàng)新中心,廣東河源 517500)

1 引言

近年來，離散事件系統(tǒng)的故障診斷研究引起了國(guó)內(nèi)外眾多學(xué)者的高度關(guān)注.自Sampath等人在文獻(xiàn)[1]中提出基于診斷器的故障診斷方法以來,這種方法就被廣泛使用.Zad等人[2]提出了一種基于狀態(tài)的故障診斷機(jī)制.Moreira等人[3]將文獻(xiàn)[1]的診斷算法進(jìn)行優(yōu)化,提出了一種具有多項(xiàng)式時(shí)間復(fù)雜度的故障診斷方法.文獻(xiàn)[4]針對(duì)隨機(jī)系統(tǒng)提出了一種隨機(jī)離散事件系統(tǒng)的故障診斷方法.筆者在文獻(xiàn)[5]中提出了一種適用于處理不精確和不確定特性的模糊離散事件系統(tǒng)的模糊故障診斷方法.吉林大學(xué)歐陽丹彤教授等人在文獻(xiàn)[6]中深入研究了不完備離散事件系統(tǒng)的故障診斷等問題.

然而,上述文獻(xiàn)中的故障診斷方法都是將引起故障的操作視為一個(gè)事件(即故障事件).近年來,針對(duì)由多個(gè)事件組成的故障(稱為故障模式),也引起了許多學(xué)者的關(guān)注.例如,Sahika等人在文獻(xiàn)[7]中提出了基于模式的故障診斷方法,將Sampath等人提出基于診斷器的故障診斷方法[1]推廣至對(duì)故障模式的診斷;文獻(xiàn)[8]對(duì)離散事件系統(tǒng)基于模式的故障診斷方法提出了一種語義分析方法,對(duì)文獻(xiàn)[7]中的模式診斷方法進(jìn)行了改進(jìn);文獻(xiàn)[9]對(duì)離散事件系統(tǒng)中的模式語句進(jìn)行了預(yù)測(cè).

雖然運(yùn)用上述不同的故障診斷方法都可以在故障發(fā)生后的一定時(shí)延內(nèi)將所發(fā)生的故障診斷出來,但在故障在發(fā)生后系統(tǒng)仍然可能會(huì)執(zhí)行一些被禁止的非法操作,為此,Paoli等人[10]在文獻(xiàn)[1]的基礎(chǔ)上對(duì)故障診斷提出了安全性要求,得到了一種安全故障診斷方法;隨后,Deng等人[11]也提出了基于狀態(tài)診斷的離散事件系統(tǒng)的安全診斷方法.文獻(xiàn)[12]對(duì)文獻(xiàn)[10]中的方法進(jìn)行了改進(jìn),提出了一種具有多項(xiàng)式時(shí)間復(fù)雜度的安全診斷方法.

本文繼續(xù)文獻(xiàn)[7,10]的工作,針對(duì)離散事件系統(tǒng)基于模式的故障診斷的安全性問題,提出一種基于模式的安全故障診斷方法.先根據(jù)目前最常用的S型和T型兩種模式,引入S型和T型模式的可診斷條件和安全性條件,對(duì)離散事件系統(tǒng)基于模式的安全可診斷性進(jìn)行形式化.再通過構(gòu)造一個(gè)非法語言識(shí)別器對(duì)非法操作進(jìn)行識(shí)別.然后在非法語言識(shí)別器的基礎(chǔ)上,構(gòu)建相應(yīng)的安全診斷器,對(duì)系統(tǒng)發(fā)生的故障模式實(shí)施安全診斷.最后,分別得到一個(gè)關(guān)于S型和T型模式的系統(tǒng)安全可診斷性的充分必要條件.該方法不僅能將觸發(fā)系統(tǒng)的故障模式診斷出來,還保證了系統(tǒng)在診斷期間不會(huì)執(zhí)行任何被禁止的不安全操作.

2 離散事件系統(tǒng)

一個(gè)離散事件系統(tǒng)是指有限狀態(tài)自動(dòng)機(jī)[7]

其中:X為有限狀態(tài)集合;Σ為事件集;x0∈X為系統(tǒng)初始狀態(tài);δ為狀態(tài)轉(zhuǎn)移函數(shù),δ:X ×Σ→2X;F?X為標(biāo)記狀態(tài)集;事件集Σ可分為可觀察事件集Σo和不可觀察事件集Σuo,即Σ=Σo∪Σuo.

定義1給定兩個(gè)事件串t和u,如果u=stv,則稱t為u的子串,記為tΞu;如果刪除事件串u中零個(gè)或多個(gè)事件(可連續(xù)也可不連續(xù))后得到事件串t,則稱t為u的子序列,記為tΥu.給定一個(gè)事件串集K,定義集合S為將K中事件串作為子序列的事件串集合,即S={s∈L|(?u∈K)(uΥs)};定義集合T為將K中的事件串作為子串的事件串集合,即T={s∈L|(?u∈K)(uΞs)}.

它表示S中所有以K中元素結(jié)尾的事件串集;記集合ΨT(K)為T中所有以K中元素結(jié)尾的事件串集,即

3 安全可診斷的形式化

基于模式的安全可診斷的目的是將系統(tǒng)中引發(fā)故障的故障模式及時(shí)診斷出來,并要求在診斷期間不能執(zhí)行被禁止操作.

定義2設(shè)?為離散事件系統(tǒng)G的被禁止事件串集,G的S型非法語言定義為

G的T型非法語言定義為

定義3如果離散事件系統(tǒng)G同時(shí)滿足以下條件,則稱G為基于S型模式的安全可診斷系統(tǒng):

i)S型模式可診斷條件:

其中條件DS為P?1P(st)∩L ?S.

ii)S型模式安全性條件:

其中tc為滿足i)中條件DS中t的最短事件串.

定義4如果離散事件系統(tǒng)G同時(shí)滿足以下條件,則稱G為基于T型模式的安全可診斷系統(tǒng)：

i)T型模式可診斷條件:

其中條件DT為P?1P(st)∩L ?T.

ii)T型模式安全性條件:

其中tc為滿足i)中條件DT中t的最短事件串.

4 基于S型模式的安全故障診斷

先引入一種標(biāo)記自動(dòng)機(jī)及其并行器.

定義5設(shè)G為一個(gè)基于S型模式診斷的離散事件系統(tǒng),s=σ1σ2σ3···σm為一個(gè)觸發(fā)S型模式故障的子序列,則G的標(biāo)記自動(dòng)機(jī)構(gòu)造為有限狀態(tài)自動(dòng)機(jī)HS(s)=(QS,Σ,δS,,FS),其中QS={0,1,2,···,‖s‖}為狀態(tài)集,δS為轉(zhuǎn)移函數(shù)δS:QS×Σ→QS,對(duì)于qS∈QS{‖s‖},σ∈Σ,若σ=σqS+1,則δS(qS,σ)=qS+1;若σ≠σqS+1,則δS(qS,σ)=qS;且δS(‖s‖,σ)=‖s‖.

定義6設(shè)G為一個(gè)基于S型模式診斷的離散事件系統(tǒng),設(shè)所有觸發(fā)S型模式故障的子序列為K={s1,s2,···,si},則G的并行器GlS構(gòu)造為有限狀態(tài)自動(dòng)機(jī),其中狀態(tài)集為,初始狀態(tài)為=(x0,0,···,0),轉(zhuǎn)移函數(shù)δlS:QlS×Σ→QlS定義為δlS(qlS,σ)=(δ(x,σ),δS1(qS1,σ),···,δSi(qSi,σ)),這里qlS=(x,l1,l2,···,li)∈QlS,σ∈Σ.

再構(gòu)造非法語言識(shí)別器以對(duì)非法語言進(jìn)行識(shí)別.先引入一個(gè)標(biāo)識(shí)符ΦS={S1,S2,B},其中:標(biāo)識(shí)S1表示系統(tǒng)沒有發(fā)生S型模式故障;標(biāo)識(shí)S2表示系統(tǒng)發(fā)生了S型模式故障,但此后沒有發(fā)生被禁止事件串;標(biāo)識(shí)B表示系統(tǒng)發(fā)生了S型模式故障,并且其發(fā)生之后又執(zhí)行被禁止操作.

定義7設(shè)G為基于S型模式診斷的離散事件系統(tǒng),所有觸發(fā)S型模式故障的子序列為K={s1,s2,···,si},則非法語言識(shí)別器GrS構(gòu)造為有限狀態(tài)自動(dòng)機(jī)GrS={QrS,Σ,δrS,,FrS},其中:QrS?QlS×ΦS為狀態(tài)集合;為初始狀態(tài);δrS:QrS×Σ→QrS為轉(zhuǎn)移函數(shù),對(duì)任意σ∈Σ,s∈Σ?和s′∈K,δrS的轉(zhuǎn)移規(guī)則如下:

定義8設(shè)G為基于S型模式診斷離散事件系統(tǒng),其S型模式安全診斷器GvS構(gòu)造為有限狀態(tài)自動(dòng)機(jī)GvS=,其中QvS為狀態(tài)集合;=(x0,0,0,···,0,S1)為初始狀態(tài);δvS:QvS×Σo→QvS為轉(zhuǎn)移函數(shù),它滿足

定義9設(shè)GvS是離散事件系統(tǒng)G的S型模式安全診斷器,qvS∈QvS.如果對(duì)任意qrS=(qlS,ΦS)∈qvS,都有F∈qlS,則稱qvS為F-確定狀態(tài).如果存在qrS=(qlS,ΦS),=(,)∈qvS使得F∈qlS,F/∈,則稱qvS為F-不確定狀態(tài).

下面給出S型模式安全可診斷的充分必要條件.

定理1給定基于S型模式診斷的離散事件系統(tǒng)G=(X,Σ,δ,x0,F),其S型模式安全診斷器為GvS. G為S型模式安全可診斷的充分必要條件是S型模式安全診斷器GvS同時(shí)滿足以下條件:

1)不存在F-不確定狀態(tài)qvS∈QvS,使得(qlS,ΦS)∈qvS,其中:F∈qlS,B∈ΦS.

證下面先用反證法證明定理1的充分性.

假設(shè)G滿足定理1中的條件1)和2),但G不是S型模式安全可診斷的.

i)若G不滿足S型模式可診斷性條件,則存在事件串u,v,使P(u)=P(v),u∈ΨS(K),v/∈ΨS(K).并且在GvS中,一定存在狀態(tài)qvS∈QvS,其中qrS,∈qvS,且qrS=δrS(,P(u))=(qlS,ΦS),,F∈qlS,F/∈,那么qvS是F-不確定狀態(tài);并且B∈ΦS,B/∈,這與滿足定理1中的條件1)的這一假設(shè)相矛盾.

ii)若G不滿足安全性條件但滿足診斷條件,不妨設(shè)u=u1u2σ滿足診斷條件,其中:u1∈ΨS(K),u2∈ζfS,σ∈Σo,因?yàn)镚不滿足安全性條件,所以對(duì)任意tc,都有∩ζfS=?,tc為u中滿足診斷條件中DS的最短事件串.令tc=u2σ,即經(jīng)過u1u2σ時(shí)故障剛好能夠被診斷出來;在GvS中存在狀態(tài)qvS,∈QvS,其中:qvS=并且qvS是F-不確定狀態(tài),是F-確定狀態(tài),又因?yàn)閡2∈ζfS,所以在中存在qrS=(qlS,ΦS),B∈ΦS,即不滿足定理1中的條件2),這與假設(shè)相矛盾.

再用反證法證明定理1的必要性.

假設(shè)系統(tǒng)G是S型模式安全可診斷的,但其安全診斷器GvS不滿足定理1中的條件1)或2).

i)若G不滿足條件1),則存在F-不確定狀態(tài)qvS∈QvS,使得(qlS,ΦS)∈qvS,其中F∈qlS,B∈ΦS.由于qvS為F-不確定狀態(tài),則一定存在使qrS=(qlS,ΦS),F∈,由此可知,在G中存在事件串u,v使得P(u)=P(v),其中u∈ΨS(K),v/∈ΨS(K),即不滿足S型模式可診斷條件.

ii)若G不滿足條件2),即存在qvS,∈QvS,其中qvS和為分別F-不確定狀態(tài)和F-確定狀態(tài),且存在e∈Σo,使 得,其中F∈,B∈.取s=ue,令,則存在u′,v使得u′v∈P?1(u),u′∈ΨS(K),v/∈ΨS(K),再令u=u1u2,u1/∈ΨS(K).因?yàn)镚是S 型模式安全可診斷的,所以存在t∈L/u1,且t滿足條件DS,此時(shí)滿足條件DS的最短事件串為tc=u2e.又因?yàn)?其中B∈,即u2e∩ζf≠?,即G不是S型模式安全可診斷的,這與假設(shè)相矛盾. 證畢.

注1設(shè)基于S型模式診斷的離散事件系統(tǒng)G,其系統(tǒng)狀態(tài)數(shù)為‖X|=n1,事件數(shù)‖Σ‖=n2,在安全診斷器GvS中,其狀態(tài)數(shù)與事件數(shù)最多分別為2n1和n2,則構(gòu)造GvS的復(fù)雜度為O(2n1·n2).當(dāng)判斷定理1中的條件1)時(shí),需要遍歷安全診斷器GvS中的所有狀態(tài),所以復(fù)雜度為O(2n1),當(dāng)判斷定理1中的條件2)時(shí),需要遍歷所有的狀態(tài)及事件,即復(fù)雜度為O(2n1×n2).根據(jù)定理1,驗(yàn)證G的S型模式安全可診斷性的復(fù)雜度為O(n2·2n1).

例1考慮圖1中系統(tǒng)G1,其中:Σo={b,d,σs},?={σs},故障模式集K1={d,c}.

圖1 離散事件系統(tǒng)G1Fig.1 Discrete-event system G1

分別構(gòu)造狀態(tài)標(biāo)記器和并行器如圖2和圖3所示.

圖2 標(biāo)記器HS(s)Fig.2 The label automaton HS(s)

分別構(gòu)造S型模式非法語言識(shí)別器和安全診斷器如圖4和圖5所示.

由圖5 可知,狀態(tài){(x3,1,S1),(x6,F,S2)}為F-不確定狀態(tài),并且在(x3,1,S1)與(x6,F,S2)中都沒有標(biāo)識(shí)符B;且由F-不確定狀態(tài){(x3,1,S1),(x6,F,S2)}經(jīng)過可觀事件d 到達(dá)F-確定狀態(tài){(x8,F,S2),(x7,F,S2)},即GvS滿足定理1條件,所以系統(tǒng)G1是S型模式安全可診斷的.

圖3 并行器GlSFig.3 Parallel automaton GlS

圖4 S 型模式非法語言識(shí)別器GrSFig.4 S-type recognizer of illegal language GrS

圖5 S 型安全診斷器GvSFig.5 S-type safe diagnoser GvS

5 基于T型模式的安全故障診斷

定義10設(shè)G為一個(gè)基于T型模式診斷的離散事件系統(tǒng),s=σ1σ2σ3···σm為觸發(fā)T型模式故障的子串,則G的標(biāo)記自動(dòng)機(jī)構(gòu)造為有限狀態(tài)自動(dòng)機(jī)

其中:QT={0,1,···,‖s‖}為狀態(tài)集合,δT為轉(zhuǎn)移函 數(shù),δT:QT×Σ→QT,對(duì) 于qT∈QT{‖s‖},σ∈Σ,如果σ=σqT+1,則δT(qT,σ)=qT+1;如果σ≠σqT+1,則δT(qT,σ)=0;且δT(‖s‖,σ)=‖s‖.

定義11設(shè)G為一個(gè)基于T型模式診斷的離散事件系統(tǒng),所有觸發(fā)T 型模式故障子串為K={s1,s2,···,si},G 的并行自動(dòng)機(jī)GlT構(gòu)造為有限狀態(tài)自動(dòng)機(jī)

下面構(gòu)造非法語言識(shí)別器GrT以對(duì)非法操作進(jìn)行識(shí)別.引入禁止標(biāo)識(shí)符ΦT={S1,S2,B},其中標(biāo)識(shí)S1表示系統(tǒng)沒有發(fā)生T型模式故障;標(biāo)識(shí)S2表示系統(tǒng)發(fā)生了T型模式故障,但其發(fā)生之后沒有發(fā)生被禁止事件串;標(biāo)識(shí)B表示系統(tǒng)即發(fā)生了T型模式故障又執(zhí)行了被禁止事件串.

定義12設(shè)G=(X,Σ,δ,x0,F)為一個(gè)基于T型模式診斷的離散事件系統(tǒng),所有觸發(fā)T型模式故障的子串為K={s1,s2,···,si},G的T型模式非法語言識(shí)別器GrT構(gòu)造為有限狀態(tài)自動(dòng)機(jī)

定義13設(shè)基于T型模式診斷的離散事件系統(tǒng)G=(X,Σ,δ,x0,F),其T 型模式安全診斷器GvT構(gòu)造為有限狀態(tài)自動(dòng)機(jī)GvT=(QvT,Σo,δvT,,FvT),其中:QvT?2QrT為狀態(tài)集;δvT為轉(zhuǎn)移函數(shù),對(duì)于qvT∈QvT,σ∈Σo,其轉(zhuǎn)移規(guī)則如下:

定義14設(shè)GvT為T型模式安全診斷器,如果對(duì)任意qrT=(qlT,ΦT)∈qvT,都有F∈qlT,則稱qvT為F-確定狀態(tài).如果存在qrT=(qlT,ΦT),=(,)∈qvT使得F∈qlT,F/∈,則稱qvT為F-不確定狀態(tài).

下面給出T型模式安全可診斷的充分必要條件.

定理2設(shè)基于T型模式診斷的離散事件系統(tǒng)G=(X,Σ,δ,x0,F),其T型模式安全診斷器為GvT=(QvT,Σo,δvT,,FvT),則G為T型模式安全模式診斷的充分必要條件是GvT同時(shí)滿足以下條件:

1)不存在F-不確定狀態(tài)qvT,使得(qlT,ΦT)∈qvT,其中:F∈qlT,B∈ΦT.

2)不存在狀態(tài)qvT,∈QvT,其中qvT為F-不確定狀態(tài),為F-確定狀態(tài),并且存在e∈Σo和(,)∈,使得=δvT(qvT,e),其中:F∈,B∈.

證利用反證法證明定理2的充分性.

假設(shè)系統(tǒng)G滿足定理2中的條件1)和2),但是G不是T型模式安全模式診斷.

i)若G不滿足可診斷性條件,則存在事件串u,v且P(u)=P(v),u∈ΨT(K),v/∈ΨT(K).在T 型 模式安全診斷器中GvT中存在狀態(tài)qvT∈QvT,其中qrT,∈qvT,且qrT=(qlT,ΦT),=(,),F∈qlT,F/∈,則qvT為F-不確定狀態(tài);由于B∈ΦT,B/∈,這與假設(shè)相矛盾.

ii)若G不滿足安全性條件但滿足診斷條件,設(shè)事件串u=u1u2σ滿足診斷條件,其中:u1∈ΨT(K),u2∈ζfT,σ∈Σo.因G不滿足安全性條件,所以對(duì)任意,有∩ζfT=,為u中滿足診斷條件中DT的最短事件串,令tc=u2σ,即經(jīng)過事件串u1u2σ時(shí)故障剛好能夠被診斷出來,在GvT中存在qvT,∈QvT,使得=δvT(qvT,σ),且qvT為F-不確定狀態(tài),為F-確定狀態(tài),又因?yàn)閡2∈ζfT,所以在中存在qrT=(qlT,ΦT),且B∈ΦT,即不滿足定理2 中的條件2),與假設(shè)相矛盾.

再利用反證法證明定理2的必要性.

i)假設(shè)G是T型模式安全可診斷的系統(tǒng),但是GvT不滿足定理2中的條件1),則在GvT中存在一個(gè)F-不確定狀態(tài)qvT,且(qlT,ΦT),(,Φ′)∈qvT,其中F∈qlT,F/∈,B∈ΦT.設(shè)事件串s∈,且qvT=δvT(,s),則在并行器GlT中必然存在事件串u,v∈P?1(s),使得qlT=;又因?yàn)镕∈qlT,所以設(shè)u=u1u2,且u1∈ΨT(K).存在t∈L/u1,滿足可診斷條件,令t′=u1t(t=u2tc),又因?yàn)锽∈ΦT,所以u(píng)2∈ζfT,u2tc∩ζfT?,這與假設(shè)相矛盾.

ii)假設(shè)G是T型模式安全可診斷的系統(tǒng),但是GvT不滿足定理2中的條件2),即存在qvT,∈QvT,其中qvT是F-不確定狀態(tài);是F-確定狀態(tài),并存在e∈Σo,使;存在∈,其中F∈,B∈;設(shè)事件串s∈,且qvT,則在并行器GlT中存在事件串u,v∈P?1(s),使得qlT1=δlT,qlT2=δlT(,v),F∈qlT1,F/∈qlT2;再令u=u1u2,并且使u1∈ΨT(K),G是T型模式安全可診斷的,存在t∈L/u1,滿足診斷條件DT,因?yàn)槭荈-確定狀態(tài),所以tc=u2e,即診斷器經(jīng)過事件串se時(shí)故障恰好能夠被診斷出來,則存在,因?yàn)锽∈Φ′,所以u(píng)2e∈ζfT,即∩ζfT?,這同樣與假設(shè)相矛盾. 證畢.

注2與S型模式安全可診斷復(fù)雜性類似,構(gòu)造GvT的復(fù)雜度為O(2n1×n2),判斷定理2中的條件1)2)的復(fù)雜度分別為O(2n1)和O(2n1·n2).因此,根據(jù)定理2,驗(yàn)證G的T型模式安全可診斷性的復(fù)雜度為O(n2·2n1),其中n1,n2為G的狀態(tài)數(shù)和事件數(shù).

圖6 離散事件系統(tǒng)G2Fig.6 Discrete-event system G2

例1考慮圖6中系統(tǒng)G2,其中:Σo={a,d,σs},?={σs},故障模式集K2={ab}.

構(gòu)造T型模式標(biāo)記器和安全診斷器如圖7和圖8所示.

圖7 標(biāo)記器HT(s)Fig.7 The label automaton HT(s)

圖8 T型模式安全診斷器GvTFig.8 T-type safe diagnoser GvT

由圖8中可知,GvT中僅有狀態(tài){(x7,F,S1),(x8,0,S1)}為F-不確定狀態(tài),且在(x7,F,S1)與(x8,0,S1)中沒有標(biāo)識(shí)符B,即GvT滿足定理2中條件1);而F-確定狀態(tài){(x9,F,B)}由F-不確定狀態(tài){(x7,F,S1),(x8,0,S1)}經(jīng)過可觀事件σs到達(dá),并且在(x9,F,B)中有標(biāo)識(shí)符B,即GvT不滿足定理2中條件2),所以G2不是T型模式安全可診斷的.

6 總結(jié)

本文討論了離散事件系統(tǒng)基于模式故障診斷的安全性問題,提出了一種對(duì)故障模式進(jìn)行安全診斷的方法,它不僅能將S型模式和T型模式的故障在其發(fā)生之后診斷出來,又能確保系統(tǒng)在模式診斷期間不執(zhí)行任何被禁止的不安全操作.該方法通過構(gòu)造非法語言識(shí)別器和安全診斷器,得到了一個(gè)關(guān)于離散事件系統(tǒng)可安全模式診斷的充分必要條件.