基于Petri網(wǎng)診斷器的離散事件系統(tǒng)模式故障的在線診斷

闕蔡雄 劉富春 趙 銳 鄧秀勤 崔洪剛

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

1 引言

近年來(lái),離散事件系統(tǒng)的故障診斷成為一個(gè)熱門的研究領(lǐng)域,備受國(guó)內(nèi)外專家學(xué)者的關(guān)注.Sampath等提出了一種故障診斷方法[1],是目前離散事件系統(tǒng)故障診斷研究中最為廣泛使用的方法.在文獻(xiàn)[1]中,離散事件系統(tǒng)被建模為一個(gè)有限狀態(tài)自動(dòng)機(jī),其故障診斷的目的在于當(dāng)系統(tǒng)發(fā)生故障之后,在一定的延遲之內(nèi)將其檢測(cè)出并加以隔離.文獻(xiàn)[2]將故障診斷方法由集中式系統(tǒng)推廣至分布系統(tǒng),提出一種分布式離散事件系統(tǒng)的故障診斷方法.文獻(xiàn)[3]提出了一種異步診斷方法,允許診斷器與系統(tǒng)不在同一時(shí)刻初始化.文獻(xiàn)[4]針對(duì)隨機(jī)離散事件系統(tǒng)提出了一種穩(wěn)健診斷方法,它允許系統(tǒng)的實(shí)際模型是不確定模型.文獻(xiàn)[5]提出了一種雙模糊離散事件系統(tǒng),并基于該框架研究了基于狀態(tài)的分布式診斷問(wèn)題.本文作者也對(duì)離散事件系統(tǒng)的故障診斷問(wèn)題及與之密切相關(guān)的不透明性問(wèn)題進(jìn)行了相關(guān)研究,提出一種隨機(jī)離散事件系統(tǒng)的安全診斷方法[6]和一種不完備系統(tǒng)當(dāng)前狀態(tài)不透明性的驗(yàn)證算法[7].

上述文獻(xiàn)考慮的均為對(duì)單個(gè)故障事件的診斷,然而在許多應(yīng)用中,例如網(wǎng)絡(luò)入侵探測(cè),需要診斷的往往是一連串事件(稱為一個(gè)模式).Genc等[8]和Jeron等[9]提出了模式診斷的概念和相應(yīng)算法.Genc等提出了兩種模式故障類型:S型模式故障和T型模式故障,其中S型模式故障考慮的是在語(yǔ)言中以子序列的形式發(fā)生的故障,而T型模式故障考慮的是在語(yǔ)言中以子串的形式發(fā)生的故障.Jeron等提出了監(jiān)督模式的概念,一個(gè)監(jiān)督模式指的是一個(gè)自動(dòng)機(jī),其標(biāo)記的語(yǔ)言是需要診斷的模式的集合.本文作者也對(duì)模式故障診斷進(jìn)行了研究,考慮了基于模式的安全故障診斷問(wèn)題[10]和模糊離散事件系統(tǒng)的模式故障診斷問(wèn)題[11].

離散事件系統(tǒng)的故障診斷問(wèn)題又可以分為離線診斷和在線診斷.關(guān)于在線診斷,文獻(xiàn)[1]給出的在線診斷方法不需要儲(chǔ)存整個(gè)診斷器而只需儲(chǔ)存診斷器的當(dāng)前狀態(tài),但具體算法沒(méi)有給出.文獻(xiàn)[2]提出了一種在多項(xiàng)式的時(shí)間內(nèi)即可得出診斷結(jié)果的在線診斷算法.文獻(xiàn)[12]提出一種針對(duì)隨機(jī)離散事件系統(tǒng)在線診斷方法.文獻(xiàn)[13]構(gòu)造了一種Petri網(wǎng)診斷器對(duì)離散系統(tǒng)進(jìn)行在線診斷,這種Petri網(wǎng)診斷器可在多項(xiàng)式時(shí)間內(nèi)構(gòu)造完成,而且可以方便地應(yīng)用于可編程邏輯控制器(programmable logic controller,PLC).文獻(xiàn)[14]研究了離散事件系統(tǒng)的主動(dòng)診斷問(wèn)題,研究了一種N–可診斷性.

值得指出的是,近年來(lái)以Petri網(wǎng)為診斷器模型的故障診斷方法也引起了國(guó)內(nèi)外的重視.文獻(xiàn)[15]提出一種基于Petri網(wǎng)的在線診斷算法,該算法使用基于g-標(biāo)記的線性編程方法來(lái)對(duì)故障事件進(jìn)行在線診斷,避免了預(yù)先的離線計(jì)算.文獻(xiàn)[16]提出一種基于網(wǎng)展開(kāi)的在線診斷算法,有效地控制了狀態(tài)爆炸問(wèn)題,但這種方法也導(dǎo)致其在線診斷過(guò)程需進(jìn)行大量的計(jì)算.文獻(xiàn)[17]研究了以部分可觀Petri網(wǎng)為模型的離散事件系統(tǒng)的在線診斷問(wèn)題,提出一種整合廣義互斥約束和整數(shù)線性編程的在線故障診斷算法.Gougam等[18]研究了基于Petri 網(wǎng)模型的離散事件系統(tǒng)模式故障診斷問(wèn)題.文獻(xiàn)[19]將模式故障診斷推廣到了隨機(jī)Petri網(wǎng)模型.文獻(xiàn)[20]研究了定時(shí)系統(tǒng)中的模式診斷問(wèn)題.

據(jù)大家所知,目前尚無(wú)用于模式故障的基于Petri網(wǎng)診斷器的在線診斷方法.本文繼續(xù)了作者在文獻(xiàn)[10–11]的工作,提出了一種用于模式故障的基于Petri網(wǎng)診斷器的在線診斷方法.首先討論了離散事件系統(tǒng)的模式故障在線診斷問(wèn)題,提出了自動(dòng)機(jī)GD來(lái)對(duì)離散事件系統(tǒng)進(jìn)行在線診斷.然后在GD的基礎(chǔ)上,提出了Petri網(wǎng)診斷器的構(gòu)造算法及在線診斷算法.本文將故障在線診斷問(wèn)題推廣至模式故障,得益于Petri網(wǎng)的分布性質(zhì)(distributed nature),有效的避免了文獻(xiàn)[1]中出現(xiàn)的狀態(tài)爆炸問(wèn)題,亦避免了使用諸如文獻(xiàn)[16]的網(wǎng)展開(kāi)方法,減少了診斷過(guò)程中的計(jì)算.本文提出的Petri網(wǎng)診斷器具有多項(xiàng)式時(shí)間的空間復(fù)雜度,具有所需空間小、效率高等特點(diǎn).

本文接下來(lái)分為4節(jié):第2節(jié)將介紹離散事件系統(tǒng)和Petri網(wǎng)的一些相關(guān)知識(shí);第3節(jié)研究模式故障的在線診斷問(wèn)題,提出一種用于S型模式故障診斷和T型模式故障診斷的有限狀態(tài)自動(dòng)機(jī)GD;第4節(jié)提出基于Petri網(wǎng)診斷器的模式故障在線診斷的驗(yàn)證算法并給出復(fù)雜度分析;第5節(jié)總結(jié)本文工作.

2 自動(dòng)機(jī)與Petri網(wǎng)

為方便起見(jiàn),引入以下符號(hào):∥ω∥表示事件串ω的長(zhǎng)度,σ ∈ω表示σ至少在ω中出現(xiàn)了一次,ωf表示事件串的最后一個(gè)事件,s ∈Sω表示s為ω的子序列,記號(hào)τ ∈Tω表示τ為ω的子串.投影P :Σ?→是指一個(gè)滿足如下規(guī)則的映射:對(duì)于任意σ ∈Σ,如果σ ∈Σo,則P(σ)σ,否則P(σ)ε,且P(ωσ)P(ω)P(σ).

集合Ψ(Σθ){ω ∈L:?σ ∈Σθ,ωfσ},即L中以Σθ中任一事件結(jié)尾的串的集合.集合

即L中包含集合Σθ中任一事件的串的集合.模式故障串組成的集合記為K,

即S和T分別表示L中包含S型模式故障和T型模式故障的串的集合.集合

即ΨS(K)和ΨT(K)分別表示恰好發(fā)生S型模式故障和T 型模式故障的串的集合.

記號(hào)δ(x,σ)!表示轉(zhuǎn)移δ(x,σ)在G中有定義.有效事件函數(shù)Γ :X →2Σ定義為Γ(x){σ :δ(x,σ)!}.對(duì)于任意x ∈X,

兩個(gè)自動(dòng)機(jī)G1和G2的并是一個(gè)自動(dòng)機(jī),其生成和標(biāo)記的語(yǔ)言分別為

一個(gè)標(biāo)簽Petri網(wǎng)是一個(gè)七元組

其中: P是庫(kù)所的有限集,T是變遷的有限集,Pre(P×T)→{0,1,2,···}是連接庫(kù)所和變遷的有向弧函數(shù),Post:(T ×P)→{0,1,2,···}是連接變遷和庫(kù)所的有向弧函數(shù),M0:P →{0,1,2,···}是初始標(biāo)識(shí)函數(shù),l :T →2Σ為標(biāo)簽分配函數(shù).庫(kù)所pi含有的令牌數(shù)量表示為M(pi).標(biāo)識(shí)

輸出庫(kù)所集為O(ti){pi∈P :Post(ti,pi)>0}.類似地,

3 模式故障的在線診斷

文獻(xiàn)[8]給出了一種模式故障的離線診斷方法,在本節(jié)中作者將提出一種在線診斷方法,其主要思路如下:假設(shè)觀察到的系統(tǒng)歷史運(yùn)行路徑為ω(已發(fā)生的事件串),在每次觀察到新事件σ發(fā)生后,計(jì)算出系統(tǒng)可能的實(shí)際運(yùn)行路徑?{P?1(ωσ)∩L(G)}.若?中所有的串都不包含故障,那么可以判定系統(tǒng)沒(méi)有發(fā)生故障;若?中既有包含故障的串,也有不包含故障的串,那么不能確定系統(tǒng)是否發(fā)生了故障;若?中所有的串都包含故障,則可以判定系統(tǒng)發(fā)生了故障.用符號(hào)N表示系統(tǒng)沒(méi)有發(fā)生故障,A表示不確定系統(tǒng)是否發(fā)生了故障,F表示確定系統(tǒng)發(fā)生了故障,則以上診斷過(guò)程可定義為函數(shù)diag.

定義1diag:→{N,A,F}為一個(gè)滿足如下規(guī)則的函數(shù):對(duì)于任意ωσ ∈

為方便起見(jiàn),引入模式故障串標(biāo)記自動(dòng)機(jī).

定義2給定一個(gè)模式故障串ki∈K及其模式故障類型,定義模式故障串標(biāo)記自動(dòng)機(jī)

其中: Xi{0,1,2,···,∥ki∥},

對(duì)于任意的x ∈Xi和σ ∈Σ,當(dāng)ki為S型故障時(shí),

當(dāng)ki為T型故障時(shí),

定義2中的Θ函數(shù)用來(lái)匹配當(dāng)前已發(fā)生的串與模式串ki,其具體的算法可使用克努特–莫里斯–普拉特操作(Knuth-Morris-Pratt,KMP)算法.

定義3給定一個(gè)離散事件系統(tǒng)

和一個(gè)模式故障集K,令

則GD定義為

定理1給定一個(gè)離散事件系統(tǒng)G,一個(gè)模式故障集K及其模式故障類型,記L(G)L,

下面通過(guò)一個(gè)例子來(lái)說(shuō)明如何根據(jù)GD和定理1對(duì)離散事件系統(tǒng)S型模式故障進(jìn)行在線診斷,T型模式故障在線診斷方法可類似得到.

例1如圖1所示,設(shè)系統(tǒng)G生成的語(yǔ)言為L(zhǎng),可觀事件集為Σo{c,d,e},不可觀事件集為Σuo{a,b},故障模式集為K{ac,bd},G關(guān)于L 是S 型模式故障可診斷的.根據(jù)定義2構(gòu)造H(ac),H(bd)如圖2–3所示,根據(jù)定義3構(gòu)造G′,GD如圖4–5所示.現(xiàn)在根據(jù)定理1用GD對(duì)系統(tǒng)進(jìn)行在線診斷:假設(shè)歷史運(yùn)行路徑ωcec,當(dāng)觀察到事件σd,可計(jì)算出δD(0,cecd){11,12},而{11,12}∩Xm,D{11}且{11,12}Xm,D,根據(jù)定理1,此時(shí)不能確定系統(tǒng)是否發(fā)生故障.同理,當(dāng)繼續(xù)觀察到事件d后,計(jì)算出δD(0,cecdd){11},而{11}?Xm,D,根據(jù)定理1,可以確定系統(tǒng)發(fā)生了故障,診斷結(jié)束.其余路徑的診斷過(guò)程相同.

圖1 一個(gè)離散事件系統(tǒng)GFig.1 A discrete-event system G

圖2 自動(dòng)機(jī)H(ac)Fig.2 Automation H(ac)

圖3 自動(dòng)機(jī)H(bd)Fig.3 Automation H(bd)

圖4 自動(dòng)機(jī)G′Fig.4 Automation G′

4 基于Petri 網(wǎng)診斷器的模式故障在線診斷的驗(yàn)證算法

為驗(yàn)證定理1中的條件,下面提出構(gòu)建Petri網(wǎng)診斷器ND的方法(算法1)并給出基于Petri網(wǎng)診斷器的模式故障在線診斷的驗(yàn)證算法(算法2).

算法1構(gòu)造Petri網(wǎng)診斷器ND.

輸入:G,K.

輸出:ND(PD∪{N,F},TD∪{tf},PreD,PostD,M0,D,Σo,lD,InD).

步驟1根據(jù)定義3構(gòu)造GD.

步驟2將GD轉(zhuǎn)換為Petri網(wǎng).

步驟2.1對(duì)于每個(gè)狀態(tài)xi∈XD,創(chuàng)建一個(gè)對(duì)應(yīng)的庫(kù)所pi∈PD.

步驟2.2對(duì)于每個(gè)庫(kù)所pi∈PD,若對(duì)應(yīng)的狀態(tài)xi有δD(xi,σ),則創(chuàng)建一個(gè)變遷tj∈TD并分配標(biāo)簽lD(tj){σ},令PreD(pi,tj)1.對(duì)于所有的xl∈δD(xi,σ),令PostD(tj,pl)1.

步驟2.3對(duì)于所有pi∈PD,若對(duì)應(yīng)的狀態(tài)xi∈x0,D,則令M0,D(pi)1,否則M0,D(pi)0.

步驟3構(gòu)造ND.

步驟3.1對(duì)于每個(gè)庫(kù)所pi∈PD,若對(duì)應(yīng)的狀態(tài)xi∈XD有Γ(xi)∩ΣoΣo,則創(chuàng)建一個(gè)變遷

步驟3.2創(chuàng)建一個(gè)變遷tf,創(chuàng)建庫(kù)所N和F.令lD(tf){λ},PreD(N,tf)PostD(tf,F)1.

步驟3.3對(duì)于所有pi∈PD,若對(duì)應(yīng)的狀態(tài)xi∈XDXm,D,則令I(lǐng)nD(pi,tf)1,否則令I(lǐng)nD(pi,tf)0.

步驟3.4令

步驟3.5所有未定義的PreD(p,t),PostD(t,p),令PreD(p,t)0,PostD(t,p)0.

步驟4算法結(jié)束.

圖5 自動(dòng)機(jī)GDFig.5 Automaton GD

為了獲得GD的狀態(tài)估計(jì),規(guī)定當(dāng)GD處于狀態(tài)xi時(shí),對(duì)應(yīng)的庫(kù)所pi有一個(gè)令牌,否則,pi沒(méi)有令牌,即每個(gè)庫(kù)所只有一個(gè)令牌或沒(méi)有令牌.因此,規(guī)定ND為一個(gè)二元Petri網(wǎng).

定理2給定一個(gè)離散事件系統(tǒng)G,一個(gè)模式故障集K及其模式故障類型,記L(G)L,

若L關(guān)于K是S型(或T型)模式故障可診斷的,則對(duì)于任意的u∈P(L),diag{u}F當(dāng)且僅當(dāng)Mu(F)1.

證由定理1的證明可得

根據(jù)定理2,用Petri網(wǎng)診斷器對(duì)系統(tǒng)進(jìn)行在線診斷的過(guò)程中,當(dāng)庫(kù)所F中有一個(gè)令牌時(shí),可以判定系統(tǒng)出現(xiàn)了故障.

算法2基于Petri網(wǎng)診斷器ND的模式故障在線診斷算法.

輸入:

輸出:Mu(F).

步驟1初始化系統(tǒng),令uωσσ′ε,

步驟2記錄系統(tǒng)事件σ,當(dāng)σσ′,跳轉(zhuǎn)到步驟3.

步驟3令uωσ,對(duì)于所有ti∈TD,若

則ti發(fā)生.

步驟4對(duì)于所有?pi∈I(ti)∪O(ti),進(jìn)行計(jì)算Mu(pi).

步驟5若所有pi∈PIn都有Mu(pi)0,則有Mu(F)1,否則Mu(F)0.

步驟6令σ′σ, ωωσ.

步驟7若Mu(F)1則算法結(jié)束,否則跳轉(zhuǎn)到步驟2.

轉(zhuǎn)移數(shù)在最壞的情況下為

GD的狀態(tài)數(shù)和轉(zhuǎn)移數(shù)與G′相同.Petri網(wǎng)診斷器ND由GD轉(zhuǎn)換得到的Petri網(wǎng)構(gòu)造而成,在最壞的情況下,ND的庫(kù)所數(shù)與抑制弧數(shù)相同,為

變遷數(shù)為

有向弧數(shù)為n(2m+1)(λ+r)+2.

因此,算法1步驟1的復(fù)雜性(即構(gòu)造GD的復(fù)雜性)為O(λnm);步驟2的復(fù)雜性(即將GD轉(zhuǎn)換為Petri網(wǎng)的復(fù)雜性)與構(gòu)造的復(fù)雜性相同;步驟3的復(fù)雜性(即構(gòu)造診斷器ND的復(fù)雜性)為O(λnm).綜上可得,算法1的復(fù)雜性為O(λnm),它與系統(tǒng)的狀態(tài)數(shù)和事件數(shù)為線性關(guān)系.

例2考慮圖1的離散事件系統(tǒng)G,根據(jù)算法1構(gòu)造Petri網(wǎng)診斷器ND如圖6所示.

圖6 Petri網(wǎng)診斷器NDFig.6 Petri net diagnosers ND

表1 診斷結(jié)果Table 1 Diagnostic result

5 總結(jié)

本文研究了離散事件系統(tǒng)的模式故障在線診斷問(wèn)題,提出自動(dòng)機(jī)GD可用于S型模式故障和T型模式故障在線診斷.根據(jù)GD提出Petri網(wǎng)診斷器ND的構(gòu)造算法及在線診斷算法.本文提出的Petri網(wǎng)診斷器具有多項(xiàng)式的空間復(fù)雜性,在在線診斷的過(guò)程中根據(jù)庫(kù)所的令牌數(shù)便可判斷系統(tǒng)是否發(fā)生了故障,具有所需儲(chǔ)存空間小、效率高等優(yōu)點(diǎn).