汪恒宇，張信哲，劉久富

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

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

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

早期通信系統(tǒng)的數(shù)據(jù)分析方法主要依靠人工參照協(xié)議規(guī)范分析數(shù)據(jù)的有效性、正確性和數(shù)據(jù)的邏輯是否正確.近年來(lái)各種系統(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]，通過(guò)內(nèi)建的自我測(cè)試和一個(gè)packet/flit比較模塊，分別嵌入網(wǎng)絡(luò)適配器和路由器的在線搜索、故障檢測(cè)和故障定位方法[8]，基于模糊集的動(dòng)態(tài)故障樹(shù)方法評(píng)價(jià)數(shù)據(jù)通信系統(tǒng)[9]等.文獻(xiàn)[10]建立隨機(jī)Petri網(wǎng)(SPN)表示的CTCS無(wú)線通信機(jī)制模型和列車與無(wú)線閉塞中心通信的GSM-R故障恢復(fù)模型，給出對(duì)通信故障定位的方發(fā).文獻(xiàn)[11]提出了一種有效的移動(dòng)網(wǎng)絡(luò)混合故障診斷協(xié)議，采用網(wǎng)絡(luò)編碼技術(shù)來(lái)交換診斷信息，從而提供了一個(gè)完整概率較高的正確診斷.

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

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

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

定義1 部分可觀Petri網(wǎng)(partially observed petri nets，POPN)定義為一個(gè)6元組NPOPN=(P,T,Pre,Post,To).其中?P,T,Pre,Post?是基礎(chǔ)PN模型，P為元素總數(shù)為m的庫(kù)所集合(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)，同時(shí)簡(jiǎn)寫(xiě)為Μ[δ〉Μ′.

定義2 時(shí)間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)間隔集.給定一個(gè)變遷ti∈T，函數(shù)Q將兩個(gè)有理數(shù)與ti(第二個(gè)也可能是∞)相關(guān)聯(lián)，即Q(ti)=(li,ui)，其中l(wèi)i≥0,ui≥li,li≠∞.當(dāng)且僅當(dāng)變遷在時(shí)間區(qū)間[li,ui]中邏輯使能時(shí)，變遷ti點(diǎn)火.

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

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

1.2 時(shí)間可診斷性問(wèn)題

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

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

若L(σ)=L(σo)，忽略點(diǎn)火時(shí)間信息有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之間點(diǎn)火的不可觀變遷序列.

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,

如果沒(méi)有關(guān)于任意故障集i∈{1,…,r}的不確定狀態(tài)，那么TPN是τ時(shí)間可診斷的(對(duì)于任何τ∈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〉對(duì)于任意τ≥τ′是τ可診斷的.

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

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

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

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

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

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

(3)

(4)

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

公式(4.1)到公式(4.4)對(duì)序列的總長(zhǎng)度施加限制.

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

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

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

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

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

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

輸入 POLTPN模型，檢測(cè)時(shí)間點(diǎn)τp，故障變遷tf，時(shí)間τ.

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

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

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

新節(jié)點(diǎn)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é)點(diǎn)標(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)簽時(shí)間序列σo=(γe0,τe0)(γe1,τe1)…(γeh,τeh)的路徑σ并放入∑(σo,φ)，φ表示不考慮檢測(cè)時(shí)間點(diǎn)τp

6) 給定檢測(cè)時(shí)間點(diǎn)τp，令所有同時(shí)滿足公式(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)類圖是一個(gè)有向圖，其節(jié)點(diǎn)稱為集.每個(gè)集與網(wǎng)絡(luò)的一組狀態(tài)相關(guān)聯(lián)，即可達(dá)標(biāo)簽M∈Rt(Nd,M0)和一組定義相對(duì)于在M處使能的所有變遷的時(shí)序約束的不等式Θ.邊界集合為(t,L(t),Δ∈[l*,u*])，其中t∈T是從尾節(jié)點(diǎn)中的標(biāo)簽引導(dǎo)到頭節(jié)點(diǎn)中的標(biāo)簽的變遷；L(t)是與t相關(guān)的標(biāo)簽函數(shù)，Δ∈[l*,u*]是對(duì)從邊緣尾節(jié)點(diǎn)到邊緣的頭節(jié)點(diǎn)的時(shí)間約束，l*≤l和u*≤u.

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

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

3 實(shí)例分析與驗(yàn)證

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

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

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

表1 各庫(kù)所物理含義

表2 各變遷物理含義、可觀測(cè)性及設(shè)計(jì)動(dòng)作時(shí)間

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

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

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

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

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

時(shí)間檢測(cè)點(diǎn)為7.0，觀測(cè)序列為σ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對(duì)應(yīng)的時(shí)間消耗為∑Δ′=Δ0+Δ2+Δ7+Δ4+Δ1+Δ3=5.6，通過(guò)公式(3.4)求解多路徑的LPP問(wèn)題得到從故障t7開(kāi)始到下一個(gè)可觀變遷最短時(shí)間為Δ7+Δ4+Δ1+Δ3=3.6，則故障變遷t7不是3個(gè)單位時(shí)間內(nèi)可診斷的，是4個(gè)單位時(shí)間內(nèi)可診斷的.

時(shí)間檢測(cè)點(diǎn)為8.0，觀測(cè)序列為σ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對(duì)應(yīng)時(shí)間消耗為∑Δ′=Δ0+Δ1+Δ2+Δ4+Δ3+Δ8+Δ5=6.7，從故障t8開(kāi)始到下一個(gè)可觀變遷最短時(shí)間為Δ8+Δ5=1.5，則故障變遷t8不是1個(gè)時(shí)間單位內(nèi)可診斷是4個(gè)單位時(shí)間內(nèi)可診斷的.

3.3 仿真驗(yàn)證

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

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

4 結(jié)語(yǔ)

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

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

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

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