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

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

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

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

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

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

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

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

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

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

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

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

圖2 可預測性的直觀圖表示Fig.2 A direct visual representation of predictability

3 構(gòu)造模式故障預測驗證器

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

5 模式故障可預測算法的復雜性分析

6 實例分析

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

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

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

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

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

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

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

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

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

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

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

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

圖10 模式故障預測驗證器VGFig.10 The patterns fault prediction verifier

7 結(jié)論

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