汪恒宇，張信哲，劉久富

(南京航空航天大學(xué) 自動化學(xué)院，江蘇 南京 211106)

故障可診斷性解釋了故障診斷深層次的內(nèi)涵，為從根本上提升控制系統(tǒng)對故障的診斷能力的研究提供了理論依據(jù).對系統(tǒng)可診斷性進行分析，從系統(tǒng)層面對系統(tǒng)結(jié)構(gòu)進行優(yōu)化，可以提高系統(tǒng)對故障信息獲取、分析能力，從而更加有效地提升系統(tǒng)的安全性[1].Hashtrudi等[2]在自動機建模的時延DES背景下介紹了時間可診斷性的概念，在他們的事件中包含一個全局時鐘的標(biāo)記，同時是可以觀測的.時間可診斷性要求通用故障的點火fi在至多τi次標(biāo)記后可以被檢測和隔離.TripaKis在[3]中提出了帶保護的時延自動機，δ診斷性(基本上和我們的τ診斷性定義是一樣的概念的)提出和證明是在區(qū)間δ∈Q上PSPACE完全問題.對時間的明確考慮對于運輸系統(tǒng)、通信協(xié)議、電路、航空系統(tǒng)或?qū)崟r系統(tǒng)等系統(tǒng)的規(guī)范和驗證至關(guān)重要，是否可以通過觀察有限長度的詞來重構(gòu)故障事件的發(fā)生.

通信系統(tǒng)在出現(xiàn)故障的時候就會導(dǎo)致數(shù)據(jù)傳輸不確定或者不完整，或者還會導(dǎo)致丟失關(guān)鍵信息，同時通信系統(tǒng)存在數(shù)據(jù)交換復(fù)雜，無法全面監(jiān)測，故障征兆不明顯，實際故障數(shù)據(jù)捕捉存在困難等問題，所以如何快速、可靠地對通信系統(tǒng)進行故障診斷保證數(shù)據(jù)傳輸安全完整是一個有待解決的問題[4-5].

早期通信系統(tǒng)的數(shù)據(jù)分析方法主要依靠人工參照協(xié)議規(guī)范分析數(shù)據(jù)的有效性、正確性和數(shù)據(jù)的邏輯是否正確.近年來各種系統(tǒng)的網(wǎng)絡(luò)化互聯(lián)，系統(tǒng)復(fù)雜性的增加導(dǎo)致了大量的不確定性，這種方法層出不窮，如基于模型的不確定非線性大型網(wǎng)絡(luò)系統(tǒng)分布式故障診斷方法[6]，結(jié)合粗糙集和貝葉斯網(wǎng)絡(luò)的電力信息通信系統(tǒng)快速故障診斷方法[7]，通過內(nèi)建的自我測試和一個packet/flit比較模塊，分別嵌入網(wǎng)絡(luò)適配器和路由器的在線搜索、故障檢測和故障定位方法[8]，基于模糊集的動態(tài)故障樹方法評價數(shù)據(jù)通信系統(tǒng)[9]等.文獻[10]建立隨機Petri網(wǎng)(SPN)表示的CTCS無線通信機制模型和列車與無線閉塞中心通信的GSM-R故障恢復(fù)模型，給出對通信故障定位的方發(fā).文獻[11]提出了一種有效的移動網(wǎng)絡(luò)混合故障診斷協(xié)議，采用網(wǎng)絡(luò)編碼技術(shù)來交換診斷信息，從而提供了一個完整概率較高的正確診斷.

本研究考慮故障變遷序列的邏輯模糊并對變遷節(jié)點添加點火時間區(qū)間，提出了一種基于部分可觀時間Petri網(wǎng)的時間可診斷性分析方法，利用多項式時間算法求解多路徑的LPP確定系統(tǒng)中不可觀故障的時間可診斷性，在時間維度對不可觀系統(tǒng)故障進行可診斷性分析，可評估系統(tǒng)的時間可診斷程度，為后續(xù)的系統(tǒng)故障診斷提供一定的理論依據(jù)[11-25].

1 部分可觀時間Petri網(wǎng)的時間可診斷性

1.1 部分可觀時間Petri網(wǎng)

定義1 部分可觀Petri網(wǎng)(partially observed petri nets，POPN)定義為一個6元組NPOPN=(P,T,Pre,Post,To).其中?P,T,Pre,Post?是基礎(chǔ)PN模型，P為元素總數(shù)為m的庫所集合(Place)，T為元素總數(shù)為n的變遷集合(transition)，To?T是可觀變遷集，滿足|To|=0≤no≤n.Pre∈Nm×n、Post∈Nm×n分別為變遷的前向弧矩陣和后向弧矩陣，定義矩陣C=Post-Pre,C∈Nm×n為POPN的關(guān)聯(lián)矩陣(N為非負(fù)整數(shù)集).

其中C(p,t)=Post(p,t)-Pre(p,t)，同時簡寫為Μ[δ〉Μ′.

定義2 時間Petri網(wǎng)(time petri nets systems, TPN)定義為NTPN=(P,T,Pre,Post,Q)，其中N=(P,T,Pre,Post)定義了網(wǎng)絡(luò)結(jié)構(gòu)PN，Q:T→Q×(Q∪∞)定義了與變遷相關(guān)聯(lián)的靜態(tài)間隔集.給定一個變遷ti∈T，函數(shù)Q將兩個有理數(shù)與ti(第二個也可能是∞)相關(guān)聯(lián)，即Q(ti)=(li,ui)，其中l(wèi)i≥0,ui≥li,li≠∞.當(dāng)且僅當(dāng)變遷在時間區(qū)間[li,ui]中邏輯使能時，變遷ti點火.

如果存在一個Μ0[σ?Μ的TTS序列σ，則標(biāo)注Μ在?NTPN,Μ0?上是可達的.從Μ0可達的所有標(biāo)注集定義了時間可達集?NTPN,Μ0?，用Rt(NTPN,Μ0)表示.Rt(NTPN,Μ0)是基礎(chǔ)的非時延PN可達性集的子集.如果存在一個的正整數(shù)k，滿足所有Μ∈Rt(NTPN,Μ0),Μ(p)≤k，TPN系統(tǒng)?NTPN,Μ0?是有界的.

定義3 部分可觀標(biāo)簽時間Petri網(wǎng)(partially observed labeled time petri nets systems, POLTPN)定義為NPOLTPN=(NPOPN,Q,L)，標(biāo)簽函數(shù)L:T→L∪{ε}為每個變遷分配一個標(biāo)簽L或空符號ε.

1.2 時間可診斷性問題

?σ∈∑(σo,τeh)，|σ|≥|σo|,

其中τeh為滿足L(ti)=γeh且最后觸發(fā)變遷的點火時間信息，|σ|為TTS序列中包含的變遷個數(shù)，|σo|為TLS序列中包含的變遷個數(shù).同時存在為σu={ti∈Tu}∈σ的TTS序列中的不可觀子序列且L(σu)=ε，|σ|=|σo|+|σu|.

若L(σ)=L(σo)，忽略點火時間信息有l(wèi)og(σ)=σu1t1σu2t2…σuktk(k≥1)，可觀子序列為log(σo)=t1t2…tk，其中ti∈To,i=1,2,…,k；不可觀子序列l(wèi)og(σu)=σu1σu2…σuk，σui為可觀變遷ti-1和ti之間點火的不可觀變遷序列.

C(Μ0,σo,τp)={Μ∈Nm|Μ0[σ>Μ,σ∈∑(σo,τeh)}.

(1)

S(Μ0,σo,τp)={Μk,Θk|Μk∈C(Μ0,σo,τp)}.

(2)

?σ∈∑(σo,τeh),tf?σ，Diag(σo,tf,τ,τp)=1,

如果沒有關(guān)于任意故障集i∈{1,…,r}的不確定狀態(tài)，那么TPN是τ時間可診斷的(對于任何τ∈R+都成立).

定理1 〈NTPN,Μ0〉為標(biāo)簽函數(shù)是L的標(biāo)簽TPN系統(tǒng)，其中NTPN=(P,T,Pre,Post,Q).假設(shè)〈NTPN,Μ0〉是底層邏輯標(biāo)簽PN系統(tǒng).如果〈NTPN,Μ0〉是可診斷的，那么?τ′∈R+以致〈NTPN,Μ0〉對于任意τ≥τ′是τ可診斷的.

證明：計時結(jié)構(gòu)的影響只能是在底層邏輯模型中啟用的禁用序列.相反，不會出現(xiàn)TPN中具有發(fā)生權(quán)的序列在底層邏輯PN中不具有發(fā)生權(quán)的情況.因此如果底層邏輯PN系統(tǒng)可診斷，總會存在一個正實數(shù)τ′以致TPN系統(tǒng)τ′可診斷，因此對于任意τ≥τ′也是τ可診斷的.

2 部分可觀時間Petri網(wǎng)的時間可診斷性分析方法

2.1 部分可觀時間Petri網(wǎng)的可診斷性分析方法

部分可觀時間Petri網(wǎng)估計系統(tǒng)故障狀態(tài)需要根據(jù)變遷的時間屬性構(gòu)建MSCG圖，計算與MSCG同構(gòu)的非確定型自動機G，遍歷MSCG圖中滿足可觀變遷觸發(fā)序列的路徑是否包含故障變遷，估計系統(tǒng)故障狀態(tài).

G的每個狀態(tài)對應(yīng)于MSCG的一個集.邊緣用MSCG邊緣的第二個元素標(biāo)記，即與變遷相關(guān)的標(biāo)簽.

給定一個TTS集合σ=(ti1,τ1)(ti2,τ2)…(tik,τk)對應(yīng)的MSCG路徑：

(3)

(4)

式中，out(Cq)為狀態(tài)集合Cq的下邊界；Δl表示一個變遷所用時間，這個時間包括：準(zhǔn)備觸發(fā)變遷所用時間、變遷觸發(fā)所用時間、變遷觸發(fā)后在下一個庫所內(nèi)停留時間.給定路徑π不滿足約束條件，則該路徑不可能觸發(fā).

公式(4.1)到公式(4.4)對序列的總長度施加限制.

公式(4.10)表示2個序列的可觀察測得變遷σ和σ′同時瞬間發(fā)生.

定理3 存在關(guān)于一些故障集i∈{1,…,r}的狀態(tài)?σ∈∑(σo,τeh),tf∈σ：

證明：考慮故障發(fā)生后變遷的所有時間約束上限，如果τ大于或等于下限之和，即時間持續(xù)到觀測序列結(jié)束且可通過可觀變遷進行故障分析，那么故障集是τ時間可診斷的，否則不是關(guān)于故障集i的τ時間可診斷.

1)σ和σ′有相同的可觀測投影，即L(σ)=L(σ′)；

證明：當(dāng)存在包含故障變遷的序列和不包含故障的序列對應(yīng)相同的觀測序列，滿足故障發(fā)生后經(jīng)過時間τ到達最后的可觀變遷，此時為不確定狀態(tài)不能判斷故障狀態(tài)，所以故障不是τ時間可診斷的.

2.2 基于MSCG的時間可診斷性分析算法描述

輸入 POLTPN模型，檢測時間點τp，故障變遷tf，時間τ.

輸出 故障診斷結(jié)果diag(σo,tf,τ,τp)∈{0,1}:

1) 頭節(jié)點C0→M0,tag(C0)=new,C0→∑(C,M),

2) while ?tag(C)=new∈∑(C,M) do

新節(jié)點tag(Ck)=new

for 任意ti∈A(Mk) do

Mk[ti>Mk+1，Ck+1→Mk+1

for ?tr∈A(Mk) do

ifMk[tr>Mk+1then

else

ifCk+1∈∑(C,M)then

tag(Ck+1)=exit

else

tag(Ck+1)=new,Ck+1→∑(C,M)

取消新節(jié)點標(biāo)記tag(Ck)=exit

3) 取Ci→∑(C,M)和ti∈A(Mk)，Mk∈∑(C,M) 構(gòu)建MSCG圖

4) 搜索滿足σo=ε,τp=0且滿足公式(4.1)、(4.2)、(4.6)和(4.7)的路徑放入∑(ε,φ)

5) 搜索標(biāo)簽時間序列σo=(γe0,τe0)(γe1,τe1)…(γeh,τeh)的路徑σ并放入∑(σo,φ)，φ表示不考慮檢測時間點τp

6) 給定檢測時間點τp，令所有同時滿足公式(4.1)、(4.2)、(4.6)和(4.7)且σ∈∑(σo,φ)的σ放入集合∑(σo,τp)

7) fori=1,…,rdo

Diag(σo,tf,τ,τp)=1

Diag(σo,tf,τ,τp)=1

else

Diag(σo,tf,τ,τp)=0

if滿足公式(3.4).

thenDiag(σo,tf,τ,τp)=0

elseDiag(σo,tf,τ,τp)=1

修改后的狀態(tài)類圖是一個有向圖，其節(jié)點稱為集.每個集與網(wǎng)絡(luò)的一組狀態(tài)相關(guān)聯(lián)，即可達標(biāo)簽M∈Rt(Nd,M0)和一組定義相對于在M處使能的所有變遷的時序約束的不等式Θ.邊界集合為(t,L(t),Δ∈[l*,u*])，其中t∈T是從尾節(jié)點中的標(biāo)簽引導(dǎo)到頭節(jié)點中的標(biāo)簽的變遷；L(t)是與t相關(guān)的標(biāo)簽函數(shù)，Δ∈[l*,u*]是對從邊緣尾節(jié)點到邊緣的頭節(jié)點的時間約束，l*≤l和u*≤u.

給定有界時間Petri網(wǎng)系統(tǒng)，構(gòu)建的MSCG圖是有界的.

2.3 算法復(fù)雜度分析

3 實例分析與驗證

3.1 通信系統(tǒng)POTPN模型構(gòu)建

通信系統(tǒng)基本由信息源，發(fā)送設(shè)備，信息，接收設(shè)備，受信者等組成.其工作原理為發(fā)送的數(shù)據(jù)信息被分成多組在多個支路上傳輸，進入緩沖區(qū)后收集數(shù)據(jù)包以重構(gòu)原始信息，并向發(fā)送方發(fā)送確認(rèn)信息[13].圖1以通信系統(tǒng)工作過程中關(guān)鍵節(jié)點為庫所，關(guān)鍵動作為變遷建立時間Petri網(wǎng)模型，模擬通信協(xié)議工作過程，各庫所、變遷含義如表1、表2所示.

圖1 通信系統(tǒng)Petri網(wǎng)模型

表1 各庫所物理含義

表2 各變遷物理含義、可觀測性及設(shè)計動作時間

3.2 通信系統(tǒng)故障的時間可診斷性分析

通信系統(tǒng)工作過程為：發(fā)送方的數(shù)據(jù)準(zhǔn)備傳輸(p0)，分離器把數(shù)據(jù)分成兩組并打包(t0)，打包數(shù)據(jù)在2個信道上傳輸，經(jīng)過信道1經(jīng)過路由器((p1,t1;p2,t2)和信道2經(jīng)過路由器(p3,t3;p4,t4) 進入緩沖區(qū)(p5,p6)后收集數(shù)據(jù)包以重構(gòu)原始信息，并向發(fā)送方發(fā)送確認(rèn)信息(t5,t6).

圖2 通信系統(tǒng)的MSCG圖

表3中為多次系統(tǒng)故障的時間可診斷性分析結(jié)果，時間檢測點為4.0時間τ=3時標(biāo)簽時間序列為σo=(e1,0.7)(e2,3.6)，搜索滿足σ∈∑(σo,4.0)的TTS有3條，Δ0+Δ2=2.9，Δ0+Δ1+Δ2=2.9，Δ0+Δ1+Δ3+Δ2=2.9，對于?σ∈∑(σo,4.0)路徑不經(jīng)過故障變遷，由定義7得到該標(biāo)簽時間序列是3個時間單位內(nèi)可診斷的.時間檢測點為5.0時間τ=2時觀測序列為σo=(e1,0.8)(e3,3.1)(e2,4.8)，搜索滿足σ∈∑(σo,5.0)的TTS有1條，Δ0+Δ1+Δ3+Δ2=4.0對于?σ∈∑(σo,4.0)路徑不經(jīng)過故障變遷，則該標(biāo)簽時間序列是2個時間單位內(nèi)可診斷的.

表3 通信系統(tǒng)故障的時間可診斷性分析結(jié)果

時間檢測點為7.0，觀測序列為σo=(e1,0.8)(e2,2.5)(e3,6.1)，搜索滿足σ∈∑(σo,7.0)的TTS序列有8條，有故障存在的TTS有4條，所有TTS滿足∑Δ′=5.6，選擇序列l(wèi)og(σ)=t0t1t2t7t4t3對應(yīng)的時間消耗為∑Δ′=Δ0+Δ2+Δ7+Δ4+Δ1+Δ3=5.6，通過公式(3.4)求解多路徑的LPP問題得到從故障t7開始到下一個可觀變遷最短時間為Δ7+Δ4+Δ1+Δ3=3.6，則故障變遷t7不是3個單位時間內(nèi)可診斷的，是4個單位時間內(nèi)可診斷的.

時間檢測點為8.0，觀測序列為σo=(e1,0.7)(e2,2.6)(e3,5.9)(e4,7.4)，搜索滿足σ∈∑(σo,8.0)的TTS序列共10條，有故障存在的TTS有5條，所有TTS滿足∑Δ′=6.7，其中l(wèi)og(σ)=t0t1t2t4t3t8t5對應(yīng)時間消耗為∑Δ′=Δ0+Δ1+Δ2+Δ4+Δ3+Δ8+Δ5=6.7，從故障t8開始到下一個可觀變遷最短時間為Δ8+Δ5=1.5，則故障變遷t8不是1個時間單位內(nèi)可診斷是4個單位時間內(nèi)可診斷的.

3.3 仿真驗證

為進一步驗證POLTPN模型的時間可診斷分析方法，對多類不可觀故障進行模型構(gòu)建并進行多次仿真，如表4所示.分別對故障變遷的時間可診斷性進行 1 000 次設(shè)定：900次可診斷、100次不可診斷.900次可診斷實驗中，算法實際診斷出887次可診斷、13次不可診斷；100次不可診斷實驗中，算法實際診斷出98次不可診斷，2次可診斷.可診斷分析準(zhǔn)確性為98.5%，不可診斷準(zhǔn)確性為98.0%.實驗說明本研究的時間可診斷性分析方法能夠?qū)OTPN模型中故障的時間可診斷性進行有效確定.

表4 算法運行1 000次后系統(tǒng)行為統(tǒng)計結(jié)果

4 結(jié)語

1) 本文結(jié)合多項式時間算法求解LPP和修正狀態(tài)類圖(MSCG)標(biāo)簽時間序列的搜索方法提出了故障變遷的時間可診斷性分析方法.搜索MSCG圖中所有滿足時間標(biāo)簽序列集合σo的TTS序列σ并求解多路徑的LPP問題分析系統(tǒng)是否在給定時間內(nèi)可診斷.

2) 對不確定狀態(tài)的故障變遷添加時間信息，考慮故障變遷序列的邏輯模糊，在時間角度對系統(tǒng)故障的可診斷性進行分析.補充了故障可診斷性分析基礎(chǔ).

3) 建立通信協(xié)議離散事件系統(tǒng)的部分可觀標(biāo)簽時間Petri網(wǎng)模型，根據(jù)組件之間觸發(fā)關(guān)系修正相應(yīng)變遷時間約束，通過構(gòu)建MSCG圖重構(gòu)故障變遷的發(fā)生，通過本文提出的算法診斷是否能在一定時間內(nèi)診斷出系統(tǒng)故障狀態(tài).模擬多類多次故障變遷驗證了算法的有效性.

本文算法依賴于MSCG圖的復(fù)雜性和LPP求解的，如果系統(tǒng)演算比解決LPP所需的時間快，或者遇到高復(fù)雜性系統(tǒng)時，則算法會出現(xiàn)局部有效性問題.所提方法還需進一步改進.本文僅考慮了變遷時間序列的邏輯模糊情況，對時間模糊沒有明確考慮，忽略了變遷同時觸發(fā)的情況，將對構(gòu)建的MSCG的邊界條件和狀態(tài)集進一步修正來適應(yīng)時間模糊的情況.