戴 維，劉富春，趙 銳，鄧秀勤，崔洪剛,3

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

離散事件系統(tǒng)(discrete event systems, DESs)是指一類狀態(tài)為離散情形且狀態(tài)演化由事件驅(qū)動的動態(tài)系統(tǒng)。離散事件系統(tǒng)在國防軍事、交通控制、計算機集成制造系統(tǒng)、電子通訊網(wǎng)絡(luò)、物聯(lián)網(wǎng)技術(shù)和機器人技術(shù)等領(lǐng)域被廣泛應(yīng)用。近年來，關(guān)于離散事件系統(tǒng)故障診斷的研究吸引了眾多學(xué)者的注意，涌現(xiàn)出了大量的研究成果，如文獻[1-4]。離散事件系統(tǒng)的故障診斷主要包括2種情形：基于狀態(tài)的診斷和基于事件的診斷。例如，Zad等[5]提出了一種基于狀態(tài)的故障診斷方法。Sampath等[6]則提出了一種基于事件的故障診斷方法，并且給出了基于診斷器的系統(tǒng)可診斷的驗證算法。Yoo等[7]提出了一種新的驗證器算法，將基于診斷器的故障診斷方法的復(fù)雜度降至多項式。文獻[8]將基于事件的故障診斷方法推廣到模糊離散事件系統(tǒng)。Thorsley等[9]研究了隨機離散事件系統(tǒng)的故障診斷問題，并提出了2種故障診斷概念：A-可診斷以及AA可診斷。Chen等[10]則提出了一種具有多項式復(fù)雜度的隨機離散事件系統(tǒng)可診斷算法。葉彬彬等[11]將隨機離散事件系統(tǒng)的故障診斷推廣至故障預(yù)測。文獻[12]通過用Petri網(wǎng)構(gòu)建診斷器的方法，實現(xiàn)了較低復(fù)雜度下的故障診斷。Reshmila等[13]將離散事件系統(tǒng)故障診斷方法應(yīng)用于電網(wǎng)系統(tǒng)的故障診斷。Chen等[14]則對蓄電組系統(tǒng)故障進行了深入研究。

分布式離散事件系統(tǒng)通過多個站點共同監(jiān)督的方式，減少單個站點的信息獲取，提高了離散事件系統(tǒng)整體的診斷效率。Qiu等[15]將Sampath提出的基于事件的方法由集中式推廣至分布式，提出了經(jīng)典分布式離散事件系統(tǒng)的故障診斷。在經(jīng)典分布式離散事件系統(tǒng)的基礎(chǔ)之上，Xu等[16]提出具有通信機制的分布式狀態(tài)估計算法,首次將通信機制引入到分布式系統(tǒng)中去。經(jīng)典分布式系統(tǒng)診斷方法不具有通信機制，這使得系統(tǒng)各站點之間無法接受和傳遞其他站點的信息，一旦發(fā)生站點丟失或站點無法正常工作的情況，就會影響診斷結(jié)果，降低診斷效率?？紤]到經(jīng)典分布式離散事件系統(tǒng)診斷方法存在的部分問題，文獻[17-18]中介紹的具有通信機制的分布式離散事件系統(tǒng)的故障診斷方法可以解決經(jīng)典分布式離散事件系統(tǒng)沒解決的部分問題：分布式離散事件系統(tǒng)中的各個站點可以進行通信，降低了全局系統(tǒng)與各站點之間信息的耦合；允許較小通信延遲的存在，降低各站點之間信息的耦合。

在文獻[15]的基礎(chǔ)之上，Keroglou等[19]將通信機制引入經(jīng)典分布式離散事件系統(tǒng)，提出了一種基于交并集優(yōu)化的診斷算法，利用生成狀態(tài)評估圖進行故障信息的分類與提煉，最后得出故障事件的相關(guān)信息。因此，本文提出的算法不需要各站點間實時同步，也不要求通信機制具有較小的時間延遲，只需通信機制在診斷系統(tǒng)工作的時間段內(nèi)能夠工作就能進行事件信息的交互。與文獻[15]相比，本文系統(tǒng)中各站點之間可以相互進行通信，并且各站點均存儲有分布式系統(tǒng)當(dāng)前所觀察到的事件信息。

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

離散事件系統(tǒng) G通過有限不確定狀態(tài)自動機來表示，可表示為一個四元組[16]

若事件σ ∈Σ可被站點i觀察到，則σ ∈Σi，否則就為?， ?表示事件 σ無法被站點i觀察到，其中 Σi是站點i的可觀事件的集合[19]。

2 分布式離散事件系統(tǒng)的狀態(tài)評估

各站點在觀察到系統(tǒng)發(fā)生事件后，通過通信機制接收其他站點傳來的事件信息以及本站點觀察所得的事件信息進行狀態(tài)評估操作，同時更新本站點的狀態(tài)評估圖。為方便描述和分析，本文假設(shè)系統(tǒng)故障都是永久性故障且不可恢復(fù)。若這些站點的狀態(tài)評估圖中的狀態(tài)集合存在故障狀態(tài)，就需要對狀態(tài)評估圖中的狀態(tài)集合進行故障的分析。本文假設(shè)各站點在信息傳輸過程中無信息丟失，通信時延ω為有限時延，且觀察得到的事件序列具有保序性。站點i在觀察到系統(tǒng)發(fā)生事件后，更新本站點的狀態(tài)評估圖 Ei。

定義1給定站點i的狀態(tài)評估圖 Ei， Ei為 G的子自動機，本文為區(qū)別 G中路徑π，定義 Ei中的路徑為?i，且滿足?i ∈I,L(Ei)?L(G)。

定義 2給定系統(tǒng)G 中 任意一條路徑π=x0σ0x1σ1···σnxn∈Π(G)，其軌跡是指[16]

其中，σ0···σn表示從狀態(tài) x0到狀態(tài) xn所需要經(jīng)過的事件串。

定義3給定站點i當(dāng)前狀態(tài)評估圖 Ei，其中任意一條路徑為?i=xkσk···σqxq，定義狀態(tài)評估圖 Ei的狀態(tài)集合為X(?i)=xk···xq。

定義4給定站點i的標(biāo)簽函數(shù) lbli，I={1,···,m}，其作用是為路徑 ?i中的狀態(tài)集貼標(biāo)簽

其中，X(?i)表示路徑 ?i中的狀態(tài)集。

定義5將站點i的狀態(tài)評估圖 Ei中當(dāng)前到達的狀態(tài)集合定義為

其中， xe為狀態(tài)評估圖 Ei中被標(biāo)簽函數(shù) lbli貼上標(biāo)簽有待診斷的狀態(tài)。

3 分布式離散事件系統(tǒng)的可診斷性

定義6給定一個診斷函數(shù)D:2X→{N,F,A},它滿足如下條件

定義7(可診斷定義)若分布式離散事件系統(tǒng)G可 診斷，則滿足以下條件

其中， Mi為站點i對tr(π)的可觀映射，tr(π)為系統(tǒng) G中路徑 π的軌跡， N 和 F為診斷標(biāo)簽。直觀上，系統(tǒng)G 可診斷，診斷系統(tǒng)中的各站點對系統(tǒng)G 中任意路徑π ∈Π(G)進行觀察之后，更新其狀態(tài)評估圖Ei。再接收來自其他站點的事件信息，其狀態(tài)集合為。對于中的任意元素 xe，經(jīng)診斷函數(shù)診斷之后，有且僅有xe∈N 或xe∈F。

定理1設(shè)G=(X,Σ,α,Xo)是一個離散事件系統(tǒng)，站點索引集合為I={1,···,m}， ?i是站點i狀態(tài)評估圖 Ei中的路徑，為站點i中狀態(tài)評估圖 Ei的狀態(tài)集合，則系統(tǒng)G 可診斷的充分必要條件是

根據(jù)定理1，下面提出用于驗證基于狀態(tài)估計的分布式離散事件系統(tǒng)可診斷性的算法。

步驟1初始化站點i的狀態(tài)評估圖Ei(i ∈I)。

步驟1.1初始化路徑。

站點i從系統(tǒng) G的初始狀態(tài)集合 Xo開始，尋找包含站點i不可觀事件的路徑 π，并從這些路徑 π開始對站點i 的 Ei進行初始化。

步驟1.2初始化標(biāo)簽。

站點i在上一步得到的 Ei中，利用標(biāo)簽函數(shù) lbli對本站點 Ei中路徑 ?i的末狀態(tài) x進行標(biāo)記。

步驟2站點i觀察到可觀事件，更新其 Ei。

步驟2.1站點i 觀察到事件α，α∈Σi，更新 Ei中的路徑 ?i。

它表示系統(tǒng) G的事件α∈Σi能被站點i觀察到，即Mi(α)=α。由步驟1可知，路徑π 屬于舊路徑 ?oild，因此路徑 π的末狀態(tài)應(yīng)標(biāo)記有i標(biāo)簽，即i ∈lbli(last(π))。其中， π′為 Ei中新生成的路徑，包含在更新后的路徑 ?i中。

這一時期屬于印尼建國初期，政府面臨著嚴峻的政治經(jīng)濟形勢，將發(fā)展的重點放在政治與經(jīng)濟上。蘇加諾政府提倡“積極自主”外交，蘇加諾總統(tǒng)先后訪問了很多國家，其中與蘇聯(lián)和中國的關(guān)系較為密切。由于國內(nèi)動亂頻發(fā)，蘇加諾總統(tǒng)認為當(dāng)時的“會議民主”不適合印尼的國家統(tǒng)一，因此于1956年提出“民主、宗教、共產(chǎn)”的民族主義(NASAKOM)組閣方案。根據(jù)該方案，內(nèi)閣由軍隊、宗教組織和印尼共產(chǎn)黨代表組成?？梢姡K加諾總統(tǒng)的政治傾向為社會主義，而中國是社會主義國家，所以華文教育在此時期有良好發(fā)展的政治環(huán)境。

步驟2.2更新標(biāo)簽。

它表示在上一步操作之后，從站點i 的 Ei中得到更新后的路徑 ?i，在其中找到包含事件 α的子路徑sub(?i)，并將原來子路徑sub(?i)中首狀態(tài)的i標(biāo)簽，從路徑π 的首狀態(tài)轉(zhuǎn)移到其末狀態(tài)上去。

步驟3站點i接收到站點 j對事件 β的觀察信息，β∈Σj。

步驟3.1更新路徑。

步驟3.2更新標(biāo)簽。

由于站點i接收到站點 j對事件 β的觀察信息，站點i需要對 Ei進行更新。因此站點i需要在 Ei中，找出上一步更新得到的路徑 ?i，并在 ?i中找到包含事件η的子路徑sub(?i)，同時將路徑 ?i的子路徑中，狀態(tài)的 j標(biāo)簽從路徑π 的首狀態(tài)向末狀態(tài)傳遞。

步驟4對站點i的Ei中冗余歷史記錄進行修剪操作。

站點i 和 j之間進行通信后，站點i 的 Ei中路徑?i的i標(biāo)簽和 j標(biāo)簽都傳遞到更新后的路徑 ?i上。這里的事件 o表示任意站點可觀的事件或事件串(事件α 或事件β,也可能是兩者組成的事件串)。因此，路徑π′的狀態(tài)沒有標(biāo)簽，為無用歷史路徑，站點i需要截去不包含任何標(biāo)簽的路徑 π′，以節(jié)約診斷系統(tǒng)的存儲空間。

步驟5對分布式離散事件故障診斷系統(tǒng)中任意2個站點最后生成的狀態(tài)評估圖進行比較，若(?i,j ∈I)Ei=Ej，則進入到下一步的診斷結(jié)果輸出環(huán)節(jié)，否則重復(fù)以上步驟。

步驟6利用診斷函數(shù)對系統(tǒng)G當(dāng)前狀態(tài)集合進行故障診斷，同時分析系統(tǒng)G的可診斷性。

圖 1 算法流程Figure 1 Algorithm flowchart

文獻[16]僅提出一種分布式狀態(tài)估計算法，沒有將這種算法運用到故障診斷中去；文獻[19]提出利用基于狀態(tài)估計的分布式離散事件系統(tǒng)對系統(tǒng)故障進行診斷，但由于文中對分布式集合交互精煉算法(DiSIR)的構(gòu)造過程過于復(fù)雜，難以將其應(yīng)用到實際系統(tǒng)中。本文在文獻 [19]的基礎(chǔ)上,將文獻[16]提出的具有通信機制的分布式故障診斷方法引入到文獻[19]提出的基于狀態(tài)估計的故障診斷方法中去，提出一種新的分布式離散事件系統(tǒng)可診斷性驗證算法。

4 算例分析

本文結(jié)合上述算法，給出一種對高速公路狀況的可診斷性驗證的方法。由于大霧天氣使得高速公路的能見度降低，危害車輛安全行駛，在本例中視其為故障誘因；同時，高速公路上車速較高，若發(fā)生道路損毀，容易引發(fā)危險，也應(yīng)視為故障誘因。因此，為避免事故的發(fā)生，保證高速公路系統(tǒng)的正常運作，需要利用不同的站點來共同對高速公路中出現(xiàn)的安全隱患進行排查。為簡單起見，將“大霧天氣”視為一類故障誘因，“道路損毀”視為另一類故障誘因。只有2種誘因同時存在，才能引發(fā)道路故障。并設(shè)診斷系統(tǒng)包含有兩類站點(即I={1,2})：第1類站點為站點1，可以觀察高速公路天氣狀況；第2類站點為站點2，可以觀察高速公路路面狀況。

一個完整的系統(tǒng)G=(X,Σ,α,Xo)，表示某一時段內(nèi)高速公路系統(tǒng)的路況(如圖2所示)。

圖 2 系統(tǒng)GFigure 2 System G

站點1和站點2為安裝在車輛上，由相關(guān)通信設(shè)備和傳感器所構(gòu)成的兩類站點，站點1可以識別高速公路的路面狀況，站點2可以識別高速公路的天氣狀況。各站點間可以通過通信機制，同時利用本站點觀察所得的事件信息與其他不同類型的站點進行信息交換。

假設(shè)對站點1，事件a表示雨天，事件b表示大霧天氣，事件c表示雪天，事件d表示道路損毀(站點1無法觀察)，事件u表示道路發(fā)生交通事故(兩類站點均無法觀察)；對站點2，事件a表示路面潮濕，事件b表示大霧天氣(站點2無法觀察)，事件c表示路面積雪，事件d表示道路損毀，事件u表示道路發(fā)生交通事故(兩類站點均無法觀察)，系統(tǒng)G的各狀態(tài)表示事件發(fā)生之后系統(tǒng)所處于的對應(yīng)狀態(tài)。用兩類站點的可觀映射來表示上述事件，即

如表1所示。

表 1 站點與可被此站點觀察到的事件Table 1 Each site and its events that can be observed by this site

假設(shè)系統(tǒng)G在某一時間段內(nèi)發(fā)生了事件串a(chǎn)bdc，診斷系統(tǒng)從當(dāng)前G所處的初始狀態(tài)集合Xo={1,3}，開始對G進行故障診斷。系統(tǒng)G在狀態(tài)1到狀態(tài)3之間發(fā)生了交通事故u，無法被兩類站點所觀察到，為避免事件u對系統(tǒng)G的影響，對系統(tǒng)G的狀態(tài)進行劃分：Xn={1,2,3,4,5,6,7,9,10}，Xf={8}。

從圖1可知，系統(tǒng)G從初始狀態(tài)集合出發(fā)，發(fā)生abdc的事件串后，產(chǎn)生2條不同的路徑：經(jīng)過路徑1a2b4d7c8到達狀態(tài)8；經(jīng)過路徑3a5b9d4c6會到達狀態(tài)6。系統(tǒng)G在狀態(tài)1到狀態(tài)3之間發(fā)生了交通事故u，無法被兩類站點所觀察到，且由路徑1u3a5b9d4c6會到達狀態(tài)6。為避免事件u對系統(tǒng)G的診斷結(jié)果產(chǎn)生影響，對系統(tǒng)G的狀態(tài)進行劃分：Xn={1,2,3,4,5,6,7,9,10}為正常狀態(tài)集合；Xf={8}為故障狀態(tài)集合。

1) 站點1的狀態(tài)評估過程。

(1) 站點1的初始化。事件u表 示高速公路發(fā)生交通事故，對2個站點均不可觀。由算法1，站點1對狀態(tài)的路徑和標(biāo)簽進行初始化。站點1的E1初始化如圖3所示。

圖 3 初始化站點1的E1Figure 3 Initialize E1 for Site 1

(2) 更新路徑和標(biāo)簽(站點1觀察到G發(fā)生事件a)。由于事件a對站點1可觀，站點1從貼上“1”標(biāo)簽的狀態(tài)開始，對E1中的路徑 ?1進行更新；事件d對站點1不可觀，所以E1中存在的路徑為1a2或3a5，3a5d9，3a5d9d4，3a5d9d4d7。由本文算法可知，“1”標(biāo)簽傳遞到狀態(tài)2、5、9、4和7。站點1更新后生成的E1如圖4所示。

圖 4 站點1觀察到 G發(fā)生事件a 后生成的E1Figure 4 E1 generated by Site1 after observing eventa

(3) 更新路徑和標(biāo)簽(站點1觀察到G發(fā)生事件b)。由于站點1和站點2之間存在著通信延遲，假設(shè)此時站點1在收到站點2傳來事件a的信息前，站點1先觀察到G發(fā)生事件b。因事件b對站點1可觀，所以站點1從貼有“1”標(biāo)簽的路徑 ?1開始更新E1。由于事件d對站點1不可觀，因此站點1的E1更新后的路徑為5b9、5b9d4、5b9d4d7或2b4、2b4d7。站點1更新后生成的E1如圖5所示。

圖 5 站點1觀察到事件串 ab后的E1Figure 5 E1generated by Site1 after observing event stringab

(4) 更新路徑和標(biāo)簽(站點1收到站點2對事件a的觀察信息)。由圖4可知，狀態(tài)1和3貼有“2”標(biāo)簽。因事件b對站點2是不可觀的，所以“2”標(biāo)簽的轉(zhuǎn)移路徑為1a2、1a2b4或 3a5、3a5b9，并最終轉(zhuǎn)移到狀態(tài)4和9上。站點1更新后生成的E1如圖6所示。

圖 6 站點1接收到來自站點2的事件a 后生成的E1Figure 6 E1 generated by Site1 after receiving event a from Site 2

(5) 冗余歷史路徑的修剪。由圖6所示，兩站點通信后，狀態(tài)1和3上的標(biāo)簽均已傳遞到更新后的狀態(tài)中去，狀態(tài)1和3沒有標(biāo)簽，應(yīng)將包含狀態(tài)1和3的無用路徑截去。站點1更新后生成的E1如圖7所示。

(6) 重復(fù)步驟(2) ～ (5)，直到兩站點最終生成完全一致的狀態(tài)評估圖，即E1=E2，如步驟(7)所示。

(7) 冗余歷史路徑的修剪。最終得知狀態(tài)4和7上沒有標(biāo)簽，應(yīng)對E1中冗余歷史路徑進行修剪。根據(jù)本文算法，站點1需將包含狀態(tài)4和7的無用路徑截去。站點1最終生成的E1如圖8所示。

圖 7 站點1進行修剪操作后生成的E1Figure 7 E1 generated by Site1 after trim operation

圖 8 站點1進行修剪操作后最終生成的E1Figure 8 The final E1generated by Site1 after trim operation

2) 站點2的狀態(tài)評估過程。

站點2的狀態(tài)評估過程中，除以下步驟外，其余步驟與站點1相同，在此不做贅述。

(1) 更新路徑和標(biāo)簽(站點2觀察到G發(fā)生事件d)。由于站點1和站點2之間存在著通信延遲，假設(shè)此時站點2先觀察到系統(tǒng)發(fā)生了事件d，再從站點1收到站點1對事件a的觀察信息。若此時G在狀態(tài)5發(fā)生事件d，則站點2需要為E2中 5d9的狀態(tài)9貼上“2”標(biāo)簽，若G沿路徑5b9d4行進，E2中的狀態(tài)9不能貼上“2”標(biāo)簽。因為路徑3a5b9d4在標(biāo)簽傳遞的過程中違背了本文算法對標(biāo)簽更新的規(guī)則：在E2中的“ 3a5”和“ 9d4”之間存在對站點2不可觀的事件b。因此將E2中狀態(tài)9分成2兩個狀態(tài)：9和9′，其中 9′看作是9 的克隆。站點2更新后生成的E2如圖9所示。

圖 9 站點2觀察到事件b 后生成的E2Figure 9 E2generated by Site 2 after observing eventb

(2) 更新路徑和標(biāo)簽(站點2接收到站點1對事件a的觀察信息)。站點2在接收到站點1對事件a的觀察信息后，E2中的“1”標(biāo)簽從狀態(tài)1和狀態(tài)3分別傳遞到狀態(tài)2和狀態(tài)5。由于事件d對站點1不可觀，因此“1”標(biāo)簽傳遞到克隆狀態(tài) 9′。站點2更新后生成的E2如圖10所示。

圖 10 站點2接收到來自站點1的事件a 后生成的E2Figure 10 E2generated by Site 2 after receiving event afrom site 1

(3) 冗余歷史路徑的修剪(站點2接收到站點1對事件c的觀察信息)。最終站點2中E2的“1”標(biāo)簽和“2”標(biāo)簽從狀態(tài)4、9和7分別傳遞到狀態(tài)6和8。因此狀態(tài)4、9和7不存在任何標(biāo)簽，站點2截去E2中冗余歷史路徑。站點2最終生成的E2如圖11所示。

圖 11 站點2進行修剪操作后最終生成的E2Figure 11 The final generated by Site 2 after trim operationE2

3) 診斷函數(shù)對系統(tǒng)G當(dāng)前狀態(tài)集合進行故障診斷。

站點1和站點2在系統(tǒng)G發(fā)生事件串a(chǎn)bdc后，兩站點均生成完全一致的狀態(tài)評估圖，即兩站點最后有E1=E2。因系統(tǒng)G在發(fā)生事件串a(chǎn)bdc后，到達故障狀態(tài)8和正常狀態(tài)6，系統(tǒng)G最終到達的狀態(tài)集合X?i中既有屬于Xf的元素，又有屬于Xn的元素，所以D(?i)=A。由定理1得知系統(tǒng)G是不可診斷的，即診斷系統(tǒng)在系統(tǒng)G發(fā)生事件串a(chǎn)bdc后無法判斷高速公路當(dāng)前是否處于因“大霧天氣”和“道路損毀”所引發(fā)的故障狀態(tài)。

若考慮事件u可能對高速公路上運行的車輛產(chǎn)生危害，而將其作為故障誘因，從而將系統(tǒng)狀劃分改為Xf={6,8}，Xn={1,2,3,4,5,7,9,10}，最終可得D(?i)=F。因此，由定理1得知系統(tǒng)G在這種情況下是可診斷的，即分布式離散事件診斷系統(tǒng)在系統(tǒng)G發(fā)生事件串a(chǎn)bdc后得出高速公路當(dāng)前處于由“交通事故”、“大霧天氣”和“道路損毀”所引發(fā)的故障狀態(tài)，此系統(tǒng)具有可診斷性。

5 總結(jié)

本文提出了一種基于狀態(tài)評估的分布式離散事件系統(tǒng)可診斷性的驗證算法，該方法能利用不斷更新狀態(tài)評估圖使分布式離散事件系統(tǒng)中的每個站點都獲得整個系統(tǒng)的狀態(tài)評估信息，從而判斷其是否具有可診斷性。同時，算法中對冗余歷史記錄的修剪操作可以去除對最終診斷結(jié)果無影響的歷史記錄，從而節(jié)約診斷系統(tǒng)的信息存儲空間，進一步提高診斷系統(tǒng)的診斷效率。

在本文的研究基礎(chǔ)之上，下一步將研究基于狀態(tài)評估的分布式模糊離散事件系統(tǒng)故障診斷問題[15,20]，并考慮構(gòu)造驗證器對此類系統(tǒng)的可診斷性進行驗證，使其復(fù)雜度降至多項式級別。