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

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

1 引言

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

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

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

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

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

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

2 自動機與Petri網

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

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

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

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

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

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

兩個自動機G1和G2的并是一個自動機,其生成和標記的語言分別為

一個標簽Petri網是一個七元組

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

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

3 模式故障的在線診斷

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

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

為方便起見,引入模式故障串標記自動機.

定義2給定一個模式故障串ki∈K及其模式故障類型,定義模式故障串標記自動機

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

對于任意的x ∈Xi和σ ∈Σ,當ki為S型故障時,

當ki為T型故障時,

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

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

和一個模式故障集K,令

則GD定義為

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

下面通過一個例子來說明如何根據GD和定理1對離散事件系統(tǒng)S型模式故障進行在線診斷,T型模式故障在線診斷方法可類似得到.

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

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

圖2 自動機H(ac)Fig.2 Automation H(ac)

圖3 自動機H(bd)Fig.3 Automation H(bd)

圖4 自動機G′Fig.4 Automation G′

4 基于Petri 網診斷器的模式故障在線診斷的驗證算法

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

算法1構造Petri網診斷器ND.

輸入:G,K.

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

步驟1根據定義3構造GD.

步驟2將GD轉換為Petri網.

步驟2.1對于每個狀態(tài)xi∈XD,創(chuàng)建一個對應的庫所pi∈PD.

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

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

步驟3構造ND.

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

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

步驟3.3對于所有pi∈PD,若對應的狀態(tài)xi∈XDXm,D,則令InD(pi,tf)1,否則令InD(pi,tf)0.

步驟3.4令

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

步驟4算法結束.

圖5 自動機GDFig.5 Automaton GD

為了獲得GD的狀態(tài)估計,規(guī)定當GD處于狀態(tài)xi時,對應的庫所pi有一個令牌,否則,pi沒有令牌,即每個庫所只有一個令牌或沒有令牌.因此,規(guī)定ND為一個二元Petri網.

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

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

證由定理1的證明可得

根據定理2,用Petri網診斷器對系統(tǒng)進行在線診斷的過程中,當庫所F中有一個令牌時,可以判定系統(tǒng)出現(xiàn)了故障.

算法2基于Petri網診斷器ND的模式故障在線診斷算法.

輸入:

輸出:Mu(F).

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

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

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

則ti發(fā)生.

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

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

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

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

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

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

變遷數(shù)為

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

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

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

圖6 Petri網診斷器NDFig.6 Petri net diagnosers ND

表1 診斷結果Table 1 Diagnostic result

5 總結

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