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

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

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

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

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

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

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

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

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

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

定義1給定站點(diǎn)i的狀態(tài)評(píng)估圖 Ei， Ei為 G的子自動(dòng)機(jī)，本文為區(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給定站點(diǎn)i當(dāng)前狀態(tài)評(píng)估圖 Ei，其中任意一條路徑為?i=xkσk···σqxq，定義狀態(tài)評(píng)估圖 Ei的狀態(tài)集合為X(?i)=xk···xq。

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

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

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

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

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

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

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

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

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

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

步驟1初始化站點(diǎn)i的狀態(tài)評(píng)估圖Ei(i ∈I)。

步驟1.1初始化路徑。

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

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

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

步驟2站點(diǎn)i觀察到可觀事件，更新其 Ei。

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

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

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

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

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

步驟3站點(diǎn)i接收到站點(diǎn) j對(duì)事件 β的觀察信息，β∈Σj。

步驟3.1更新路徑。

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

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

步驟4對(duì)站點(diǎn)i的Ei中冗余歷史記錄進(jìn)行修剪操作。

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

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

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

圖 1 算法流程Figure 1 Algorithm flowchart

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

4 算例分析

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

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

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

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

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

如表1所示。

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

假設(shè)系統(tǒng)G在某一時(shí)間段內(nèi)發(fā)生了事件串a(chǎn)bdc，診斷系統(tǒng)從當(dāng)前G所處的初始狀態(tài)集合Xo={1,3}，開始對(duì)G進(jìn)行故障診斷。系統(tǒng)G在狀態(tài)1到狀態(tài)3之間發(fā)生了交通事故u，無(wú)法被兩類站點(diǎn)所觀察到，為避免事件u對(duì)系統(tǒng)G的影響，對(duì)系統(tǒng)G的狀態(tài)進(jìn)行劃分：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到達(dá)狀態(tài)8；經(jīng)過路徑3a5b9d4c6會(huì)到達(dá)狀態(tài)6。系統(tǒng)G在狀態(tài)1到狀態(tài)3之間發(fā)生了交通事故u，無(wú)法被兩類站點(diǎn)所觀察到，且由路徑1u3a5b9d4c6會(huì)到達(dá)狀態(tài)6。為避免事件u對(duì)系統(tǒng)G的診斷結(jié)果產(chǎn)生影響，對(duì)系統(tǒng)G的狀態(tài)進(jìn)行劃分：Xn={1,2,3,4,5,6,7,9,10}為正常狀態(tài)集合；Xf={8}為故障狀態(tài)集合。

1) 站點(diǎn)1的狀態(tài)評(píng)估過程。

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

圖 3 初始化站點(diǎn)1的E1Figure 3 Initialize E1 for Site 1

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

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

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

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

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

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

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

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

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

圖 7 站點(diǎn)1進(jìn)行修剪操作后生成的E1Figure 7 E1 generated by Site1 after trim operation

圖 8 站點(diǎn)1進(jìn)行修剪操作后最終生成的E1Figure 8 The final E1generated by Site1 after trim operation

2) 站點(diǎn)2的狀態(tài)評(píng)估過程。

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

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

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

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

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

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

圖 11 站點(diǎn)2進(jìn)行修剪操作后最終生成的E2Figure 11 The final generated by Site 2 after trim operationE2

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

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

若考慮事件u可能對(duì)高速公路上運(yùn)行的車輛產(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)評(píng)估的分布式離散事件系統(tǒng)可診斷性的驗(yàn)證算法，該方法能利用不斷更新狀態(tài)評(píng)估圖使分布式離散事件系統(tǒng)中的每個(gè)站點(diǎn)都獲得整個(gè)系統(tǒng)的狀態(tài)評(píng)估信息，從而判斷其是否具有可診斷性。同時(shí)，算法中對(duì)冗余歷史記錄的修剪操作可以去除對(duì)最終診斷結(jié)果無(wú)影響的歷史記錄，從而節(jié)約診斷系統(tǒng)的信息存儲(chǔ)空間，進(jìn)一步提高診斷系統(tǒng)的診斷效率。

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