基于修正狀態類圖的標簽時間Petri網系統故障診斷

收稿日期：2021-11-22；修回日期：2022-01-12" 基金項目：湖北省自然科學基金資助項目（2021CFB036）；工業控制技術國家重點實驗室開放課題（ICT2021B37）

作者簡介：鄧明喜（1996-），男，貴州遵義人，碩士研究生，主要研究方向為Petri網理論及其應用；黎良（1989-），男（通信作者），講師，博士，主要研究方向為Petri網理論與應用、離散事件系統監督控制、復雜系統的建模分析與控制（liangli@wust.edu.cn）；劉斌（1972-），女，教授，博士，主要研究方向為網絡安全控制、復雜過程建模及預測控制．

摘 要：針對具有不可觀事件的離散事件系統的故障問題，提出了一種基于標簽時間Petri網的診斷方法。首先，對標簽時間Petri網系統現有的修正狀態類圖（modified state class graph，MSCG）進行分析，提出MSCG的改進算法。其次，對于給定的可觀標簽序列和觀測時間，通過求解由改進的MSCG的路徑信息構建的線性規劃問題，獲得所有與可觀標簽序列時間一致的有效路徑，從而分析系統的故障情況。最后，以交替位協議為實例分析驗證了所提方法的有效性，為復雜的實時系統故障診斷問題提供有效方案。

關鍵詞：離散事件系統；時間Petri網；狀態類圖；故障診斷

中圖分類號：TP271"" 文獻標志碼：A

文章編號：1001-3695（2022）06-013-1678-05

doi：10.19734/j.issn.1001-3695.2021.11.0641

Fault diagnosis of labeled time Petri net systems based on modified state class graph

Deng Mingxi，Li Liang，Liu Bin

（School of Information Science amp; Engineering，Wuhan University of Science amp; Technology，Wuhan 430081，China）

Abstract：Based on labeled time Petri nets （LTPNs），this paper proposed a fault diagnosis method for discrete event systems with unobservable events.Firstly，by analyzing the deficiency of the modified state class graph （MSCG） of an LTPN system，this paper provided an improved MSCG.Secondly，it gave an observable label sequence and a time instant，it searched all the timing consistent paths by solving the linear programming problems associated with the paths in an improved MSCG，so as to analyze the system failure.Finally，it verified the effectiveness of the proposed method by taking the alternating bit protocol system as an example，which provided an effective scheme for the fault diagnosis of complex real-time systems.

Key words：discrete event system；time Petri net；state class graph；fault diagnosis

0 引言

離散事件系統（discrete event system）是指狀態演化由事件驅動且狀態空間離散的一類動態系統，比如通信系統、物流系統及各種智能信息系統均可抽象為離散事件系統來研究。通常，系統事件的發生可由特定的傳感器進行檢測。然而，由于傳感器功能有限或者出于成本的考慮，并非所有事件都是可觀測的。為了保障系統安全運行，對系統進行故障診斷和分析具有重要的現實意義。針對部分可觀的離散事件系統故障診斷問題，國內外學者基于系統模型提出了許多有效的診斷方法［1～5］。特別地，一些學者以自動機為建模工具，從不同的角度提出了有效的診斷方法［3～5］。例如，文獻［3］基于有限狀態自動機研究網絡離散事件系統的故障診斷問題，給出了部分可觀網絡可診斷的充要條件，并通過構造有效的診斷器來驗證相應的網絡可診斷性。該方法有助于維護實際網絡物理系統中的信息安全。文獻［4］采用分布式診斷結構，以混合自動機模型表示系統的連續和離散動態特征，減少了構建系統模型的代價。其次，提出一種雙擴展卡爾曼濾波算法對系統的參數進行估計，最終根據對系統事件的觀測和連續動態的可行性分析對系統進行診斷。此外，文獻［5］從提高系統模型可診斷性的角度出發，提出了一種在有限狀態自動機模型下的積極診斷方法。上述基于自動機模型構造診斷器的工作可在有限長度的事件序列發生后檢測系統是否發生故障，但當系統的規模逐漸增大時，模型復雜度也顯著提高。

相比于自動機模型，Petri網在表示系統的異步、并發與沖突等因果關系方面具有良好的建模能力，因此被廣泛應用于制造、電力和通信等系統的故障識別與診斷［6，7］。基于Petri網模型，國內外學者提出了不同的離散事件系統故障診斷算法。文獻［8］根據標簽Petri網可達圖的拓撲結構構造了一種用于在線診斷的拓撲排序診斷圖。當觀測到一個可觀標簽時，按照可達圖的拓撲排序使圖中每個標簽都與一個包含診斷信息的向量相關聯。所提方法與整數線性規劃方法相比，具有較好的診斷效率。文獻［9］將模式故障診斷方法應用于Petri網系統中，提出一種具有多項式空間復雜性的模式故障在線診斷算法，減少了診斷過程的計算復雜度。文獻［10］在診斷函數中增加了包含所有故障變遷的故障類，通過求解線性規劃問題分析系統故障情況。該算法的優勢在于無須窮舉所有與觀測序列一致的可觀序列便可得出診斷結果，具有較高的診斷效率。此外，部分學者基于系統故障發生的概率和置信度，以及網結構信息來分析故障發生的可能性［11～13］。

目前，包括上述在內的大多數診斷方法都是基于系統的邏輯層面，即從離散事件系統的狀態和事件兩個主要因素之間的邏輯順序關系分析系統的故障狀態，沒有考慮時間因素對系統狀態的影響。然而，對于實時系統而言，時間信息對系統的規范和驗證具有重要作用［14，15］。通過添加時間約束到Petri網模型中，可以衍生出稱為時間Petri網的模型，并成功地應用于賦時離散事件系統的建模與控制［16］。

對于部分可觀的時間Petri網系統故障診斷研究，文獻［17］在基于無環的網結構下，通過移除系統狀態類圖（state class graph）［16］中不可觀變遷相關的節點，構建系統的故障診斷圖（fault diagnosis graph，FDG），并基于FDG提出了一種在線故障診斷算法。該算法不要求有限的系統狀態空間，且每次觀測后只更新與可觀變遷相關的FDG，由此減少了計算復雜度。文獻［18］為標簽時間Petri網系統的變遷分配屬性標簽，并在SCG中引入與發射變遷相關的時間變量，由此構建了離線計算的修正狀態類圖（modified state class graph，MSCG）。在此基礎上，提出了一種在線求解線性規劃問題的故障診斷算法，該方法對部分可觀的離散事件系統的故障診斷具有重要意義，并且為實際系統的可診斷性提供了有效的理論依據［19］。

盡管目前關于賦時離散事件系統的故障診斷研究有所進展，但是在基于標簽時間Petri網的故障診斷方法中均未考慮MSCG有界性的缺失問題。因此，本文在文獻［18］工作的基礎上，進一步研究基于MSCG部分的可觀時間Petri網系統的故障診斷算法。首先，探討MSCG的有界性及其邊的表達問題，為此提出了適用性更強的MSCG的改進算法，同時證明其有界性。其次，基于改進的MSCG對交替位協議系統的故障情況進行診斷分析，驗證了所提方法的可行性和有效性。

1 標簽時間Petri網

Petri網可定義為一個四元組N=（P，T，F，W），其中P和T分別表示有限且非空的庫所集和變遷集（P∩T=）；F（P×T）∪（T×P）為庫所和變遷之間的有向弧集；W：f→Euclid Math TwoNAp（f∈F）表示一種映射關系，其為每一條有向弧分配一個大于0的權值，即W（f）gt;0，故稱W為Petri網的權函數［20］。此外，Petri網的關聯矩陣為Ω=Post-Pre，其中Post（Pre）表示網的后置（前置）關聯矩陣。Petri網系統的標識可表示為一個映射M：P→Euclid Math TwoNAp，其含義是為每一個庫所p∈P分配非負整數個托肯（token），則每個庫所擁有的托肯數記為M（p）。標識M反映了系統實時的資源分布狀態。一般情況下，可將標識表示成向量的形式，即M∈Euclid Math TwoNApm。當M≥Pre（·，t）時，稱變遷t在M下是使能的，其發射后可得新標識M′=M+Ω（·，t）。在M標識下使能的變遷集記為E（M）={t∈T|M≥Pre（·，t）}。

定義1［16］ 時間Petri網（time Petri net，TPN）定義為Nt=（N，Q），其中N=（P，T，F，W）代表Petri網，Q：T→Euclid Math TwoQAp×（Euclid Math TwoQAp∪{∞}）是為每個變遷ti∈T分配兩個有理數li和ui的函數。通常，用Q（ti）=［li，ui］表示變遷ti的靜態發射區間，其中li≥0，ui≥li。

具有初始標識M0的TPN稱為TPN系統，記為（Nt，M0）。TPN系統的時間變遷序列（time transition sequence，TTS）定義為σ=（t1，τ1）（t2，τ2）…（th，τh）∈（T×Euclid Math TwoRAp+）*，其中下標為i的變遷ti∈T對應其發射的全局時間點τi，且τ1≤τ2≤…≤τh。因此，可將從M0發射σ到Mh的過程記為M0［σ〉Mh或M0［（t1，τ1）〉M1［（t2，τ2）〉M2…［（th，τh）〉Mh。序列σ中最后一個變遷發射的時間記為tl（σ）=τh。此外，本文用σ=t1t2…th表示與σ相一致的邏輯變遷序列。如果存在一個時間變遷序列σ使得M0［σ〉M，則稱M是TPN系統的可達標識。所有從M0可達的標識組成的集合稱為TPN系統的可達標識集，記為R（Nt，M0）。若在任意可達標識M∈R（Nt，M0）下的所有庫所p∈P滿足M（p）≤k（k∈Euclid Math TwoNAp+）時，則稱TPN系統是有界的。

通常，Petri網系統的標識即狀態。然而，TPN系統的狀態還與變遷的發射域有關。因此，可將TPN系統的狀態表示為Sk=（Mk，Φk），其中Mk代表系統標識，Φk是一組不等式{lki≤φi≤uki|ti∈E（Mk）}（φi表示變遷ti∈E（Mk）在狀態Sk下發射的時間延遲）［21］。

定義2［18］ 標簽時間Petri網（labeled time Petri net，LTPN）是一個三元組（Nt，M0，ζ），其中ζ：T→L∪（ε）是為每個變遷分配一個標簽的函數。特別地，每個變遷ti∈T的標簽由字母集L中一個給定的字母γ或一個空字符ε表示。

本文所考慮的LTPN系統的變遷分為可觀變遷和不可觀變遷，分別用Tu={t∈T|ζ（t）=ε}和To={t∈T|ζ（t）=γ，γ∈L表示。當兩個可觀變遷的標簽相同時，即ζ（t1）=ζ（t2）=γ，則稱它們為不可區分變遷。在LTPN系統中，一個可觀的時間標簽序列（time label sequence，TLS）表示為δ=（γe1，τe1）（γe2，τe2）…（γeh，τeh）∈（L×Euclid Math TwoRAp+）*，它表明了每個標簽及其對應的發射時間。δ中最后發射的可觀變遷發射時間表示為tl（δ）=τeh。若忽略標簽被觀測到的時間信息，可用δ^=γe1γe2…γeh表示與δ一致的邏輯標簽序列。

2 改進的MSCG

修正的狀態類圖MSCG可窮舉出給定LTPN系統的狀態空間。圖的節點表示狀態類，其由可達標識Mk和使能變遷的發射域Dk組成，記為Ck=（Mk，Dk），其中Dk={lki≤θi≤uki|ti∈E（Mk）}且θi表示變遷ti∈E（Mk）在狀態類Ck下發射的時間延遲［18］。MSCG的邊表示頭節點到子節點的連接信息，記為ti，ζ（ti），Δi，其中ζ（ti）為已發射變遷ti∈T的標簽，Δi∈［max{0，lki}，minj：tj∈E（Mk）{ukj}］表示ti的時間約束。在以下假設條件下：A1）LTPN系統是有界的；A2）對于所有的變遷ti∈T，其靜態發射域的上下界均為有理數；A3）不存在可在零持續時間內發射的不可觀變遷環，MSCG已被證明是有界的，并且可用于LTPN系統的故障診斷分析［19］。然而，當給定的LTPN系統存在特定結構時，所得MSCG的有界性會缺失且邊的信息表達具有二義性，詳情如下：

a）以圖1所示的LTPN系統為例，其初始狀態M0=［1 0 0 0］T，To={t1，t2，t3}，Tu={t4}，ζ（t1）=a，ζ（t2）=b，ζ（t3）=c，ζ（t4）=ε。根據文獻［18］中算法1可得如圖2所示的部分MSCG。在初始狀態類C0=（M0，D0）下，發射t1到達C1。在C1中，t2和t4滿足發射條件，且發射t4可到達C2。在C2中，t2和t3滿足發射條件；若發射t3，可到達C3。由C3可知，t2仍然保持可發射狀態，且t4再次滿足發射條件。若t4繼續發射，則在MSCG中會形成一個重復發射的變遷環t4t3t4t3…，且t2一直處于可發射的狀態。根據文獻［18］中的發射規則和假設條件，系統可能產生無限的狀態類集，即不存在有界的MSCG。

上述情況在理論上是存在的，但在實際系統中并不具有現實意義。原因在于變遷表示的某個事件的發生或者某個操作單元的實際操作需耗費一定的時間。所以，為了符合實際需求，改進假設條件A3為不存在可在零持續時間內發射的變遷環［22］。

b）文獻［18］對MSCG的邊ti，ζ（ti），Δi表達在某些情況下會導致Δi的二義性。如圖2所示的C4，其發射域可簡寫為1-2Δ4-Δ3≤θ2≤2-2Δ4-Δ3。然而，在C4的發射域中，第一個Δ （1）4∈［0，2］，而第二個Δ （2）4∈［0，2-Δ （1）4-Δ3］，顯然，兩個變量Δ4的取值范圍不同，因此需要加以區分。

針對上述問題，本文改進了變量Δi的表示形式，即用Δih代替Δi，其中h表示頭節點的下標，i表示變遷ti的下標。因此，Δih表示下標為i的變遷在下標為h的節點下的允許發射時間。Δih這種方式既能準確地反映變遷ti的發射時間，又表明了變遷從哪個狀態類發射的。例如，圖1所示的LTPN系統的改進MSCG如圖3所示。特別地，本文算法1提供了改進的MSCG的生成步驟。

算法1

輸入：LTPN系統結構。

輸出：MSCG。

初始化：狀態類C0=（M0，D0）；將C0標記為“new”。All_Class={C0} //存儲系統狀態類節點

while （存在“new”標記）{

選一個標記為“new”的Ch作為“head_node”

調用函數Explore_new_node（Ch）

去掉Ch的“new”標記}

Func：Explore_new_node（Ch）{ //給定頭節點Ch，生成所有的子節點以及新路徑

for all" ti∈E（Mh）{

if" max{0，lhj}≤minj：tj∈E（Mh）{uhj}{ //判斷ti是否可發射

Mnew=Mh+Ω（·，ti） //計算新標識

for all" tr∈E（Mnew）{ //求Mnew下的發射域Dnew

if ti≠tr且Mh-Pre（·，ti）≥Pre（·，tr） //tr非新使能

令lnewr=max{0，lhr-Δih}；unewr=uhr-Δih

else //tr是新使能

令lnewr=lr，unewr=ur

Cnew=（Mnew，Dnew）

if “Cnew” not in All_Class //Cnew不是重復狀態類

添加路徑Chti，ζ（ti），ΔihCnew

將Cnew標記為“new”

將Cnew添加到All_Class

else //Cnew是重復點Cold

添加路徑Chti，ζ（ti），ΔihCold}}

定理1 給定LTPN系統（Nt，M0，ζ），當系統滿足假設條件A1～A3時，則該系統的MSCG是有界的。

證明 首先，當給定的LTPN系統滿足新的假設條件A3時，則保證了系統變遷的實際意義，同時可避免MSCG產生無限的狀態類節點。其次，若假設給定的系統有界（A1），由Petri網系統的有界性可知LTPN系統的可達標識是有限的。而在LTPN系統中，狀態由標識和發射域組成，故兩個具有相同標識的狀態，如果其發射域不同，則所表達的狀態也不同。此時，若變遷ti∈T的靜態發射區間Q（ti）=［li，ui］的上下界為實數，則LTPN系統的狀態空間可能無限大［16］。當li，ui∈Euclid Math TwoQAp時（A2），則該系統為嚴格有界。而對于嚴格有界的LTPN系統，其狀態空間是有限的［16］。綜上，算法1在假設條件A1～A3下生成的MSCG具有有界性。證畢。

對于任意結構的LTPN系統模型，在保證系統可診斷性［19］的基礎上，改進后的MSCG適用性更強且確保了系統在LTPN模型上的物理意義，能為研究實際系統的故障行為提供更好的保障。

3 LTPN系統故障診斷

3.1 基于改進MSCG的LTPN系統故障診斷

針對部分可觀的LTPN系統故障診斷問題，本節給出一種基于改進MSCG的故障診斷算法。當給定一個可觀標簽序列δ∈（L×Euclid Math TwoRAp+）*和觀測時間τ≥τl（δ）時，下面分別介紹與該可觀序列和觀測時間相關的集合表示［18］。其中，與δ和τ相一致的變遷序列集表示為

∑（δ，τ）={σ∈（T×Euclid Math TwoRAp+）*|M0［σ〉M，ζ（σ）=δ，

tl（σ）=，≤τ，Euclid Math OnesCpt∈Tu，M［t〉，Tr（M0，σ）≤τ-}（1）

其中：Tr（M0，σ）表示在M下變遷t的駐留時間；為序列σ中最后一個變遷的發射時間。與δ和τ相一致的標識集記為

M（δ，τ）={M∈Euclid Math TwoNApm|M0［σ〉M，σ∈∑（δ，τ）}（2）

與δ和τ相一致的狀態集表示為

S（δ，τ）={（Mk，Φk）|Mk∈M（δ，τ）

Φk=（lkl≤Δik≤ukl）：ti∈E（Mk）（3）

定義3［18］ 給定一個可觀標簽序列δ∈（L×Euclid Math TwoRAp+）*、觀測時間τ≥τl（δ）以及故障類Tif，故障診斷器定義如下：Γ：［L×Euclid Math TwoRAp+］*×Euclid Math TwoRAp+×{T1f，T2f，…，Tif}→{N，U，F}

a）Γ（δ，τ，Tif）=N，若σ∈∑（δ，τ）且tf∈Tif，tf。

b）Γ（δ，τ，Tif）=U，若滿足以下兩個條件：σ∈∑（δ，τ）且tf∈Tif，使得tf∈；σ′∈∑（δ，τ），使得tf∈Tif，tf′。

c）Γ（δ，τ，Tif）=F，若σ∈∑（δ，τ），tf∈Tif，tf∈。

診斷器工作原理：給定一個可觀的時間標簽序列δ∈（L×Euclid Math TwoRAp+）*和時間τ≥τl（δ）及故障類Tif：a）若所有的有效序列σ∈∑（δ，τ）都不包含故障變遷，則Γ（δ，τ，Tif）=N表示該系統處于正常的工作狀態；b）若在有效序列集中存在兩個不同的序列σ和σ′，其中σ不包含任何故障變遷，σ′中至少包含一個故障變遷，則Γ（δ，τ，Tif）=U表示無法確定系統是否發生故障；c）若所有的有效序列都至少包含一個故障變遷，則Γ（δ，τ，Tif）=F表示系統一定發生了故障。

本文中，給定TLS序列δ=（γi1，τ1）（γi2，τ2）…（γih，τh）和時間τ≥τh，則該序列在MSCG中的一般路徑可記為

π=Cq1ti1，ζ（ti1），Δi1q1∈［max{0，lq1i1}，minj：tj∈E（Mq1）{uq1j}］

Cq2ti2，ζ（ti2），Δi2q2∈［max{0，lq2i2}，minj：tj∈E（Mq2）{uq2j}］…

Cqktik，ζ（tik），Δikqk∈［max{0，lqkik}，minj：tj∈E（Mqk）{uqkj}］Cqk+1（4）

定理2［18］ 給定一條如式（4）所示的路徑，則與可觀序列δ=（γi1，τ1）（γi2，τ2）…（γih，τh）∈（L×Euclid Math TwoRAp+）*，k≥h和觀測時間τ≥τh相一致的路徑滿足下列約束條件：

∑kl=1Δilql≤τ

τ-∑kl=1Δilqllt;uqk+1r，tr∈E（Mqk+1）

Δilql≥lqlil，l=1，2，…，k

Δilql≥0

Δilql≤uqlj，j：tj∈E（Mql）

∑wl=1Δilql=τw，ζ（tiw）∈δ^，w∈{1，2，…，k}（5）

基于上述定義與描述，算法2給出了基于改進MSCG的故障診斷算法。

算法2 基于改進MSCG的故障診斷算法

輸入：LTPN系統結構及其MSCG，故障類Tif，τ≥τh，δ=（γi1，τ1）（γi2，τ2）…（γih，τh）∈（L×Euclid Math TwoRAp+）*。

輸出：故障診斷結果Γ（δ，τ，Tif），i=1，2，…，r。

初始化：Plog（δ，τ）=，Pcon（δ，τ）=；

在MSCG中搜索出所有與給定序列δ邏輯上一致的路徑并以集合Plog（δ，τ）表示；

通過求解與Plog（δ，τ）相關的線性規劃問題，找出τ=τh且滿足式（5）的可行路徑，并用集合Pcon（δ，τ）表示；

for all i=1，2，…，r do

if" πk∈Pcon（δ，τ）∧tf∈Tif且tfπk

then Γ（δ，τ，Tif）=N

else if" πk∈Pcon（δ，τ）且π′k∈Pcon （δ，τ）（πk ≠π′k）

s.t.：tf∈Tif，tf∈πk

tf∈Tif，tfπ′k

then" Γ（δ，τ，Tif）=U

else" πk∈Pcon（δ，τ），tf∈Tif，tf∈πk

then" Γ（δ，τ，Tif）=F

3.2 算法復雜度分析

本文對于部分可觀的LTPN系統故障診斷是在算法1和2共同作用下完成的。其中，算法1用于構建系統的改進MSCG，其節點（狀態類）數與LTPN系統的復雜度（包括庫所、變遷的數量、網模型結構以及初始標識中托肯數量的分布等）呈指數增長。當前，現有方法很難避免這個問題［17］。

在算法1的基礎上，算法2要求計算出所有與給定的觀測序列δ和觀測時間τ相一致的有效路徑。因此，需先搜索出所有與觀測序列δ相一致的邏輯路徑。假設在MSCG中與給定的δ和τ相一致的最長邏輯路徑長度為d，則在圖中搜索出所有邏輯路徑的計算復雜度為O（|T|d）。此外，對于一條長度為d的邏輯路徑，當考慮時間約束式（5）時，判斷該路徑是否有效需求解的約束方程個數最多為1+|T|+d|T|+3d［18］，因此，如何縮減LTPN系統的狀態空間并減少計算代價是下一步需要考慮的問題。

4 交替位協議離散系統故障診斷分析與驗證

4.1 交替位協議LTPN模型及其改進MSCG

交替位協議離散事件系統主要是指兩個終端之間進行數據交換的工作流程，其基本組成部分主要包括兩個具有接收和發送信息的終端設備和信息傳輸介質［16］。以交替位協議工作過程中的關鍵節點為庫所，以關鍵事件作為變遷可建立其LTPN模型，如圖4所示，其初始標識為M0=［1 0 0 0 0 1］T，各個庫所和變遷的含義如表1所示。

如圖4所示的交替位協議系統的工作流程為：終端1向終端2實時發送數據包，當終端2接收數據包之后，會判斷該數據包是否為重復數據包，如果不是重復的數據包，則接收并存儲，反之將之清除，并向終端1發送確認信息。如果數據包在發送過程中出現數據丟失，或者在規定時間內沒有收到反饋的確認消息，則終端1會重新發送數據包。

根據算法1構建交替位協議LTPN系統的MSCG，如圖5所示。圖5及表2所示Δih的取值范圍可采用Python代碼實現并在PyCharm解釋環境中運行生成。

4.2 診斷結果分析及討論

當給定多組可觀序列與觀測時間（單位時間）時，依據算法2可得表3所示的診斷結果。由表3可知，當給定一個可觀標簽序列和觀測時間時，在MSCG中搜索出符合約束式（5）的有效路徑，并得出診斷結果。如給定可觀標簽序列δ=（a，0）（b，7）和觀測時間τ=7.5，則與觀測序列δ邏輯上一致的路徑為：t1t6t8t3、t1t7t8t3、t1t4t2t6t8t3、t1t4t2t7t8t3、t1t7t8t5t2t7t8t3、t1t7t8t5t2t6t8t3、t1t6t8t5t2t6t8t3、t1t6t8t5t2t7t8t3、t1t4t2t7t8t5t2t7t8t3、t1t4t2t7t8t5t2t6t8t3等。通過求解可得有效路徑為：t1t6t8t3、t1t7t8t3。由于所有有效路徑中不包含故障變遷t4和t5，Γ（δ，τ，t4）=N和Γ（δ，τ，t5）=N，即系統沒有發生故障，處于正常工作狀態。

4.3 算法比較

由上述實例可知，對于滿足給定假設條件的LTPN系統模型，在保證系統可診斷性［19］的基礎上，改進后的MSCG在時間信息準確性方面較文獻［18］提出的MSCG更強。此外，改進的MSCG確保了所構建的LTPN系統模型實際的物理意義，并能為研究實際系統的故障行為提供更好的保障。

為了進一步加強本文算法與同類方法的性能分析，表4從算法的約束條件、狀態空間表示以及診斷方式等方面，綜合對比了現有代表性算法的診斷特點。其中，文獻［17，23］都是在線的診斷算法，需要在動態觀測到可觀變遷發射之后計算系統的FDG和增廣狀態類圖（augmented state class graph，ASCG）。然而，FDG和ASCG在表達系統變遷的發射時間信息等方面存在局限性。文獻［24］針對診斷結果為可能發生故障的實際系統，建立貝葉斯Petri 網模型，進而判斷故障發生的概率，但其需結合離線計算的MSCG對系統進行在線診斷。相比之下，本文算法是基于離線計算的改進MSCG的在線診斷算法，降低了診斷過程的復雜性且具有較好的診斷能力，可有效用于實時系統的故障診斷分析。

5 結束語

本文研究了基于標簽時間Petri網的部分可觀離散事件系統的故障診斷問題。首先，對現有標簽時間Petri網系統的修正狀態類圖MSCG進行分析，提出了適用性更強的改進MSCG，同時證明了其有界性。其次，給出了基于改進的MSCG的故障診斷算法。該算法通過求解由改進的MSCG的路徑信息構建線性規劃問題，可以找出所有與可觀標簽序列時間一致的有效路徑，從而對系統的故障狀態進行診斷和分析。最后，考慮交替位協議離散事件系統運行中各個事件之間的因果關系，以關鍵事件作為變遷建立了部分可觀標簽時間Petri網模型。通過給定不同的觀測序列和時間常量，在改進的MSCG的基礎上對系統的故障狀態進行多次診斷和分析，驗證了所提方法的可行性和有效性。本文所提出的診斷算法是基于改進的MSCG，相對于文獻［18］的算法具有更強的適用性。然而，當該方法應用于大型的復雜系統時，仍需進一步考慮提高算法的診斷效率以及減少線性規劃問題的計算復雜度。

參考文獻：

［1］趙相福，歐陽丹彤.離散事件系統基于模型診斷的研究進展［J］.計算機科學與探索，2011，5（2）：114-127.（Zhao Xiangfu，Ouyang Dantong.Advances in model-based diagnosis of discrete event systems［J］.Computer Science and Exploration，2011，5（2）：114-127.）

［2］方歡，方賢文，李德權.基于Petri網的故障診斷研究理論綜述［J］.計算機科學，2014，41（3）：17-22.（Fang Huan，Fang Xianwen，Li Dequan.Review of fault diagnosis theory based on Petri net［J］.Computer Science，2014，41（3）：17-22.）

［3］Ren Kexin，Zhang Zhipeng，Xia Chengyi.Event-based fault diagnosis of networked discrete event systems［J/OL］.IEEE Trans on Circuits and Systems Ⅱ：Express Briefs，2021.http：//doi.org/10.1109/tcsii.2021.3120486.

［4］Lin Tiantian，Chen Ziqiang，Zheng Changwen，et al.Fault diagnosis of Lithium-ion battery pack based on hybrid system and dual extended Kalman filter algorithm［J］.IEEE Trans on Transportation Electrification，2021，7（1）：26-36.

［5］Hu Yihui，Ma Ziyue，Li Zhiwu.Design of supervisors for active diagnosis in discrete event systems［J］.IEEE Trans on Automatic Control，2020，65（12）：5159-5172.

［6］張治國，劉久富，鄭銳.柔性制造系統的部分可觀時間Petri網故障診斷［J］.計算機技術與發展，2018，28（10）：83-87，134.（Zhang Zhiguo，Liu Jiufu，Zheng Rui.Fault diagnosis of flexible manufacturing system based on partial considerable time Petri net［J］.Computer Technology and Development，2018，28（10）：83-87，134.）

［7］Xu Biao，Yin Xin，Yin Xianggen，et al.Fault diagnosis of power systems based on temporal constrained fuzzy Petri nets［J］.IEEE Access，2019，7：101895-101904.

［8］Wang Ya，Yin Li，Zhu Guanghui.Online fault diagnosis of labeled Petri nets based on reachability graphs and topological sorting［J］.IEEE Access，2020，8：162363-162372.

［9］闕蔡雄，劉富春，趙銳，等.基于Petri網診斷器的離散事件系統模式故障的在線診斷［J］.控制理論與應用，2020，37（7）：1621-1627.（Que Caixiong，Liu Fuchun，Zhao Rui，et al.Online fault diagnosis of discrete event system based on Petri net［J］.Control Theory and Applications，2020，37（7）：1621-1627.）

［10］Zhu Guanghui，Feng Lei，Li Zhiwu，et al.An efficient fault diagnosis approach based on integer linear programming for labeled Petri nets［J］.IEEE Trans on Automatic Control，2021，66（5）：2393-2398.

［11］Lefebvre D，Rachidi S，Leclercq E，et al.Diagnosis of structural and temporal faults for k-bounded non-Markovian stochastic Petri nets［J］.IEEE Trans on Systems，Man，and Cybernetics：Systems，2020，50（9）：3369-3381.

［12］劉久富，張信哲，汪恒宇，等.部分可觀Petri網故障的量子貝葉斯診斷［J/OL］.北京航空航天大學學報.（2021-05-06）［2021-10-15］.https：//doi.org/10.13700/j.bh.1001-5965.2021.0010.（Liu Jiufu，Zhang Xinzhe，Wang Hengyu，et al.Quantum Bayesian diagnosis of partial observable Petri net faults［J/OL］.Journal of Beijing University of Aeronautics and Astronautics.（2021-05-06）［2021-10-15］.https：//doi.org/10.13700/j.bh.1001-5965.2021.0010.）

［13］葉丹丹，吳維敏，蘇宏業.標簽Petri網的路徑信息在故障診斷中的應用［J］.控制與決策，2021，36（2）：325-334.（Ye Dandan，Wu Weimin，Su Hongye.Application of labeled Petri net path information in fault diagnosis［J］.Control and Decision，2021，36（2）：325-334.）

［14］Pan Li，Ding Z J，Zhou M C.A configurable state class method for temporal analysis of time Petri nets［J］.IEEE Trans on Systems，Man，and Cybernetics：Systems，2014，44（4）：482-493.

［15］路光輝，佘維，雍明超，等.一種基于時間約束可能性Petri網的設備狀態分析模型［J］.計算機應用研究，2017，34（11）：3262-3266.（Lu Guanghui，She Wei，Yong Mingchao，et al.An equipment state analysis model based on time constrained possibility Petri net［J］.Application Research of Computers，2017，34（11）：3262-3266.）

［16］Berthomieu B，Diaz M.Modeling and verification of time dependent systems using time Petri nets［J］.IEEE Trans on Software Engineering，1991，17（5）：259-273.

［17］Wang Xu，Mahulea C，Silva M.Diagnosis of time Petri nets using fault diagnosis graph［J］.IEEE Trans on Automatic Control，2015，60（9）：2321-2335.

［18］Basile F，Cabasino M P，Seatzu C.State estimation and fault diagnosis of labeled time Petri net systems with unobservable transitions［J］.IEEE Trans on Automatic Control，2015，60（4）：997-1009.

［19］Basile F，Cabasino M P，Seatzu C.Diagnosability analysis of labeled time Petri net systems［J］.IEEE Trans on Automatic Control，2017，62（3）：1384-1396.

［20］李志武，周孟初.自動制造系統建模、分析與死鎖控制［M］.北京：科學出版社，2009.（Li Zhiwu，Zhou Mengchu.Modeling，analysis and deadlock control of automated manufacturing system［M］.Beijing：Science Press，2009.）

［21］Li Liang，Basile F，Li Zhiwu.Closed-loop deadlock-free supervision for GMECs in time Petri net systems［J］.IEEE Trans on Automatic Control，2021，66（11）：5326-5341.

［22］He Zhou，Li Zhiwu，Giua A，et al.Some remarks on“state estimation and fault diagnosis of labeled time Petri net systems with unobservable transitions”［J］.IEEE Trans on Automatic Control，2019，64（12）：5253-5259.

［23］Liu Baisi，Ghazel M，Toguyéni A.Diagnosis of labeled time Petri nets using time interval splitting［J］.IFAC Proceedings Volumes，2014，47（3）：1784-1789.

［24］張信哲，張治國，丁曉彬，等.部分可觀時間Petri網故障的貝葉斯診斷［J］.應用科技，2020，47（1）：61-67.（Zhang Xinzhe，Zhang Zhiguo，Ding Xiaobin，et al.Bayesian diagnosis of partial observable time Petri net faults［J］.Applied Science and Technology，2020，47（1）：61-67.）