呂舒園，劉富春，趙 銳，鄧秀勤，崔洪剛,3

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

離散事件系統(tǒng)是一種在離散狀態(tài)和事件上建模的系統(tǒng)。事件集被劃分為可觀事件集(如傳感器的讀數(shù))和不可觀事件集(如無法被觀測(cè)到的信息)，其中故障事件一般屬于不可觀事件。離散事件系統(tǒng)的故障預(yù)測(cè)是通過觀測(cè)一系列可觀事件序列來預(yù)測(cè)故障是否將會(huì)發(fā)生，以提前做出相應(yīng)的預(yù)防措施，因此，研究離散事件系統(tǒng)的故障預(yù)測(cè)問題，可以增強(qiáng)系統(tǒng)的穩(wěn)健性和抗風(fēng)險(xiǎn)的能力，具有重要的研究意義和應(yīng)用價(jià)值。故障預(yù)測(cè)方法被廣泛應(yīng)用于計(jì)算機(jī)文件處理系統(tǒng)、暖通空調(diào)系統(tǒng)、電力系統(tǒng)、智能通訊系統(tǒng)等。

針對(duì)離散事件系統(tǒng)的故障診斷研究，已經(jīng)有大量的相關(guān)文獻(xiàn)提出了各種診斷算法，其中在1995年由Sampath等[1]提出的通過構(gòu)造診斷器的故障診斷方法是最早提出的解決離散事件系統(tǒng)故障診斷問題的算法。近年來還有其他故障診斷方法，Chen Z和Lin F[2]提出的離散事件系統(tǒng)框架下的主動(dòng)診斷方法，也探討了其在電池系統(tǒng)中的實(shí)際應(yīng)用。Reshmila S和Devanathan R[3]提出了一種新的基于觀測(cè)器的離散事件系統(tǒng)框架，并將其應(yīng)用到電力系統(tǒng)。在文獻(xiàn)[4]中，筆者所在課題組提出了一種基于模糊離散事件系統(tǒng)的安全診斷算法，可以用于醫(yī)療診斷系統(tǒng)。

隨著對(duì)故障診斷研究的不斷深入，思考如何在故障未發(fā)生前對(duì)其進(jìn)行提前預(yù)測(cè)，已成為離散事件系統(tǒng)研究中的另一個(gè)熱點(diǎn)方向——故障預(yù)測(cè)。Cao X R[5]首次在離散事件系統(tǒng)框架下提出了可預(yù)測(cè)性的概念，并且給出了離散事件系統(tǒng)基于語言上可預(yù)測(cè)的充分條件。You D和Wang S[6]使用帶標(biāo)記的Petri網(wǎng)的方式驗(yàn)證系統(tǒng)的可預(yù)測(cè)性。Chase C[7]分析了一維離散事件系統(tǒng)的狀態(tài)依賴關(guān)系，提出了一種有監(jiān)督的一維系統(tǒng)的可預(yù)測(cè)性方法。Buss S R[8]在耦合自動(dòng)機(jī)的預(yù)測(cè)問題上提出了一種二分法。Genc S[9]解決了基于語言的部分觀測(cè)離散事件系統(tǒng)中的重要事件的預(yù)測(cè)問題。

然而，現(xiàn)實(shí)社會(huì)中隨著互聯(lián)網(wǎng)的發(fā)展，互聯(lián)網(wǎng)上的信息量的越來越大，用戶對(duì)于系統(tǒng)的需求及應(yīng)用系統(tǒng)的功能越來越多，因此數(shù)據(jù)庫(kù)的規(guī)模和應(yīng)用系統(tǒng)的規(guī)模也變得越來越龐大，集中型的診斷預(yù)測(cè)方法將直接導(dǎo)致組合搜索的空間爆炸，使得其復(fù)雜度隨著系統(tǒng)規(guī)模的擴(kuò)大而升高，所以，近年來分布式系統(tǒng)的診斷和預(yù)測(cè)算法得到廣泛重視。Qiu W[10]針對(duì)分布式離散事件系統(tǒng)提出了一種分布式狀態(tài)估計(jì)協(xié)議，分布式觀察者通過有界延遲信道共享狀態(tài)估計(jì)信息，進(jìn)一步降低了時(shí)間和空間復(fù)雜度；Pencolé Y[11]研究了基于分布式離散事件系統(tǒng)的診斷問題。Yin X[12]提出了兩種分布式協(xié)議來研究分布式離散事件系統(tǒng)的預(yù)測(cè)問題。最近，筆者所在課題組在文獻(xiàn)[13]中提出了一種基于分布式離散事件系統(tǒng)的離線故障預(yù)測(cè)算法，并給出了分布式離散事件系統(tǒng)可預(yù)測(cè)性的充分必要條件，在文獻(xiàn)[14]中本課題組又針對(duì)分布式離散事件系統(tǒng)的可靠性預(yù)測(cè)問題進(jìn)行了研究。

可以看出，上述文獻(xiàn)的離散事件系統(tǒng)都是針對(duì)單個(gè)故障事件進(jìn)行診斷和預(yù)測(cè)，但在實(shí)際應(yīng)用中，有些故障可能不是單個(gè)故障事件，而是由一系列重要事件組成的事件序列造成的故障。例如數(shù)據(jù)庫(kù)系統(tǒng)中，數(shù)據(jù)庫(kù)的讀寫操作都是正常的事件，若程序員操作不當(dāng)，可能造成數(shù)據(jù)的“臟讀”。對(duì)此，人們提出了模式故障診斷的概念。對(duì)于模式故障的診斷，Jéron T，Marchand H等[15]在2006年最先提出了一個(gè)監(jiān)督模式故障模型，該模型被建模為一個(gè)自動(dòng)機(jī)，并且它具有足夠的通用性，能夠捕捉系統(tǒng)過去發(fā)生的特定軌跡，許多文獻(xiàn)中提出的多個(gè)故障、重復(fù)故障、重大事件的順序、故障修復(fù)事件等都可以視為該模式故障的一種特殊情況。之后，Genc S[16]基于形式語言的上下文定義了兩種不同類型的模式故障：S型模式故障和T型模式故障?；陔x散事件系統(tǒng)的模式故障的診斷和預(yù)測(cè)問題越來越引人重視。在文獻(xiàn)[17-18]中，筆者所在課題組對(duì)S型模式故障和T型模式故障分別研究了模糊離散事件系統(tǒng)的故障診斷問題和經(jīng)典離散事件系統(tǒng)安全診斷問題。Dague[19]提出的一種基于分布式系統(tǒng)的模式故障診斷問題的通用性算法。Jéron T[20]提出了一種基于經(jīng)典集中型離散事件系統(tǒng)的模式故障預(yù)測(cè)的方法。最近，Geng X N[21]研究了基于隨機(jī)離散事件系統(tǒng)的模式故障診斷問題。

筆者注意到，關(guān)于分布式離散事件系統(tǒng)的模式故障預(yù)測(cè)問題的研究中依然未見報(bào)道，因此本文對(duì)分布式離散事件系統(tǒng)的模式故障預(yù)測(cè)開展研究，提出一個(gè)基于分布式離散事件系統(tǒng)的模式故障診斷預(yù)測(cè)方法。首先對(duì)分布式離散事件系統(tǒng)的模式故障可預(yù)測(cè)性進(jìn)行形式化。通過構(gòu)造一個(gè)模式故障識(shí)別器，從系統(tǒng)所有行為中識(shí)別出所發(fā)生的模式故障并標(biāo)記。然后，在模式故障識(shí)別器的基礎(chǔ)上構(gòu)建了一個(gè)模式故障預(yù)測(cè)驗(yàn)證器，用于驗(yàn)證分布式系統(tǒng)的可預(yù)測(cè)性。之后，得出了一個(gè)判定分布式離散事件系統(tǒng)模式故障可預(yù)測(cè)性的充分必要條件，并提出了相應(yīng)的模式故障預(yù)測(cè)算法，實(shí)現(xiàn)了對(duì)分布式離散事件系統(tǒng)的模式故障預(yù)測(cè)。最后，對(duì)模式故障預(yù)測(cè)驗(yàn)證器的構(gòu)建和分布式離散事件系統(tǒng)的模式故障預(yù)測(cè)算法進(jìn)行了復(fù)雜度分析，得到了該分布式模式故障預(yù)測(cè)算法的復(fù)雜度為多項(xiàng)式時(shí)間的結(jié)論。

本文接下來分成7節(jié)，第1節(jié)將介紹離散事件系統(tǒng)的一些基礎(chǔ)知識(shí)，第2節(jié)將對(duì)分布式離散事件系統(tǒng)的模式故障預(yù)測(cè)進(jìn)行形式化定義，第3節(jié)將構(gòu)造一個(gè)用于模式故障預(yù)測(cè)的驗(yàn)證器，第4節(jié)將推導(dǎo)模式故障預(yù)測(cè)的充分必要條件，第5節(jié)將對(duì)模式故障預(yù)測(cè)算法的復(fù)雜性進(jìn)行分析，第6節(jié)舉例說明模式故障預(yù)測(cè)算法在三罐水位控制系統(tǒng)中的應(yīng)用，第7節(jié)將總結(jié)本文所做的工作。

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

圖1 汽車中的模式故障示例Fig.1 Example of a pattern fault in an automobile

2 分布式離散事件系統(tǒng)可預(yù)測(cè)的形式化

圖2 可預(yù)測(cè)性的直觀圖表示Fig.2 A direct visual representation of predictability

3 構(gòu)造模式故障預(yù)測(cè)驗(yàn)證器

4 分布式離散事件系統(tǒng)的模式故障預(yù)測(cè)的充分必要條件

5 模式故障可預(yù)測(cè)算法的復(fù)雜性分析

6 實(shí)例分析

下面結(jié)合三罐水位控制系統(tǒng)(A Three-Tank Water Level Control System，TTW)來說明如何檢測(cè)分布式系統(tǒng)的模式故障可預(yù)測(cè)性。

圖3 三罐水位控制系統(tǒng)(TTW)Fig.3 The three tank water level control system

例2如圖3所示，在三罐水位控制系統(tǒng)(TTW)中，有1個(gè)儲(chǔ)水池、3個(gè)儲(chǔ)水罐(T1，T2，T3)、1個(gè)抽水泵和7個(gè)閥門(V0，V1，V2，V3，V4，V5，V6)。故障模式，如圖5所示，其中{A，B，C}表示模式故障的當(dāng)前狀態(tài)的標(biāo)簽，它們的含義是：A-表示正常狀態(tài)；B-表示還未完全被模式故障診斷的中間狀態(tài)；C-表示已經(jīng)確定為模式故障的狀態(tài)。后面在構(gòu)建模式故障預(yù)測(cè)驗(yàn)證器的過程中，這些標(biāo)簽將會(huì)一直存在，以此來說明系統(tǒng)當(dāng)前的狀態(tài)。

圖4 TTW的有限狀態(tài)機(jī)Fig.4 The finite-state machine of TTW

圖5 TTW的模式故障Fig.5 The patterns fault

其次，根據(jù)算法1可以構(gòu)建出三罐水位控制系統(tǒng)的標(biāo)記轉(zhuǎn)移系統(tǒng) Γ如圖9所示。并將標(biāo)記轉(zhuǎn)移系統(tǒng)Γ中的{A，B，C}標(biāo)簽簡(jiǎn)化為{N，F(xiàn)}標(biāo)簽，得到TTW的模式故障預(yù)測(cè)驗(yàn)證器VG，如圖10所示。

最后，根據(jù)圖8可以看出模式故障預(yù)測(cè)驗(yàn)證器的前驅(qū)狀態(tài)為 τ1=(1,N;1,N;1,N)，該前驅(qū)狀態(tài)能被站點(diǎn)1和2同時(shí)診斷到模式故障。滿足所有的前驅(qū)狀態(tài)最終至少有一個(gè)站點(diǎn)可以預(yù)測(cè)到該模式故障，換句話說，所有通過前驅(qū)狀態(tài)的路徑最后都到達(dá)i?F狀態(tài)環(huán)，根據(jù)定理1可以得到三罐水位控制系統(tǒng)是分布式模式故障可預(yù)測(cè)的系統(tǒng)。

然后，根據(jù)算法1可以構(gòu)建出三罐水位控制系統(tǒng)的不可觀測(cè)閉包U(G?)；在站點(diǎn)1(儲(chǔ)水罐T1)不能觀測(cè)到儲(chǔ)水罐T3的閥門V3和V6，因此站點(diǎn)1的不可觀測(cè)閉包為U1(G?)；在站點(diǎn)2(儲(chǔ)水罐T3)不能觀測(cè)到儲(chǔ)水罐T1的閥門V1和V4，因此站點(diǎn)2的不可觀測(cè)閉包為U2(G?)。分別如圖6、圖7、圖8所示。

圖6 TTW的不可觀測(cè)閉包U(G?)Fig.6 The unobservable closure of TTW

圖7 站點(diǎn)1的不可觀測(cè)閉包U1(G?)Fig.7 The unobservable closure of site 1

圖8 站點(diǎn)2的不可觀測(cè)閉包U2(G?)Fig.8 The unobservable closure of site 2

圖9 標(biāo)記轉(zhuǎn)移系統(tǒng)ΓFig.9 The part of the tag transfer system

圖10 模式故障預(yù)測(cè)驗(yàn)證器VGFig.10 The patterns fault prediction verifier

7 結(jié)論

本文筆者對(duì)離散事件系統(tǒng)的模式故障預(yù)測(cè)進(jìn)行了研究，將模式故障看作一個(gè)自動(dòng)機(jī)，從而跟系統(tǒng)G組合成一個(gè)模式故障識(shí)別器。而且考慮到如果集中式的離散事件系統(tǒng)模型狀態(tài)過多，其預(yù)測(cè)模型的驗(yàn)證器的狀態(tài)空間將會(huì)很大的問題，為了降低集中式的模型的復(fù)雜性，筆者采用了分布式的模型分站點(diǎn)來進(jìn)行模式故障預(yù)測(cè)，使得每個(gè)模塊相對(duì)獨(dú)立，進(jìn)而使得各個(gè)站點(diǎn)只需要關(guān)注自己所觀測(cè)到的事件，得到其自身的不可觀測(cè)閉包。再由各個(gè)站點(diǎn)的不可觀測(cè)閉包來聯(lián)合構(gòu)造出系統(tǒng)G的標(biāo)記轉(zhuǎn)移系統(tǒng)，最后根據(jù)該標(biāo)記轉(zhuǎn)移系統(tǒng)簡(jiǎn)化狀態(tài)標(biāo)簽得到系統(tǒng)G的分布式模式故障預(yù)測(cè)驗(yàn)證器，解決了分布式系統(tǒng)中的模式故障預(yù)測(cè)問題。