張 源，方 歡

(安徽理工大學(xué)理學(xué)院，安徽淮南 232001)

?

基于行為輪廓的系統(tǒng)故障變化域定位方法研究

張 源，方 歡

(安徽理工大學(xué)理學(xué)院，安徽淮南 232001)

在業(yè)務(wù)流程管理中，系統(tǒng)的故障是系統(tǒng)行為發(fā)生變化的重要原因，如何定位系統(tǒng)故障的影響范圍是業(yè)務(wù)流系統(tǒng)的一項(xiàng)重要研究?jī)?nèi)容。本文基于Petri網(wǎng)的行為輪廓理論，對(duì)自由選擇網(wǎng)進(jìn)行分析和研究，通過(guò)捕捉系統(tǒng)行為的事件軌跡集合，對(duì)比源模型中變遷間的弱序關(guān)系，提出自由選擇網(wǎng)故障變化域定位算法AFCRGL；通過(guò)分析流程中的行為變化，進(jìn)一步精確尋找變化域的位置，可以控制并降低變化域?qū)α鞒棠Ｐ驼w的影響。最后以一個(gè)柔性制造Petri網(wǎng)系統(tǒng)為例，驗(yàn)證本文提出方法的有效性。

變化域；故障變遷；弱序關(guān)系；行為輪廓；Petri網(wǎng)

隨著計(jì)算機(jī)系統(tǒng)和業(yè)務(wù)系統(tǒng)規(guī)模的不斷增大，由系統(tǒng)合成和模型合成所引起的系統(tǒng)發(fā)生錯(cuò)誤的情況也越來(lái)越多，因此針對(duì)業(yè)務(wù)系統(tǒng)的行為變化分析和故障定位的研究是十分必要的。在已有的研究結(jié)論中，大部分有關(guān)行為變換分析的研究成果都出自業(yè)務(wù)流系統(tǒng)的變化域分析領(lǐng)域。業(yè)務(wù)流系統(tǒng)(Business Process Management System，BPMS)在生產(chǎn)實(shí)踐中有著廣泛的應(yīng)用，設(shè)計(jì)業(yè)務(wù)流系統(tǒng)模型的主要目的是為了適應(yīng)不同層次的業(yè)務(wù)需求，由于業(yè)務(wù)需求分析的角度不同，從而導(dǎo)致同一個(gè)模型因?yàn)殛P(guān)注的層次不同而具有不同層次的模型。所謂變化域，是指業(yè)務(wù)流系統(tǒng)中模型的行為目標(biāo)和實(shí)際模型的行為特征之間存在不一致性[1]，這種不一致性可能會(huì)影響業(yè)務(wù)流系統(tǒng)行為的安全性，因此對(duì)業(yè)務(wù)系統(tǒng)的變化域進(jìn)行分析尤為重要。

已有研究結(jié)論表明，使用Petri網(wǎng)和行為輪廓的相關(guān)理論對(duì)變化域分析是十分有效的。目前，國(guó)內(nèi)外有很多利用Petri網(wǎng)對(duì)變化域展開研究的成果，通過(guò)對(duì)流程模型變化域分類，提出了增強(qiáng)系統(tǒng)性功能的變化域模式[2]；M.Weidlich和J.Mending等給出了流程模型的變化域傳播，在已知源模型變化域的前提下，基于邊界變遷與內(nèi)部邊界變遷的變化，確定了目標(biāo)模型的變化域[3-4]；在此基礎(chǔ)上，Küster JM和Gerth C 等通過(guò)使用流程模型間的一致和單輸入、單輸出結(jié)構(gòu)分解的定義來(lái)尋找變化區(qū)域，但此方法是在缺少變化日志的前提下提出的，因此有一定的局限性[5]。定位變化區(qū)域后，分析變化區(qū)域?qū)I(yè)務(wù)流程的影響，可以幫助維護(hù)人員預(yù)測(cè)變化影響的范圍和程度，通常被稱為影響分析，它是解決這些潛在變化影響的方法[4-10]。

系統(tǒng)故障是影響系統(tǒng)行為變化的一個(gè)主要因素。使用Petri網(wǎng)對(duì)故障的研究大都集中在故障的檢測(cè)與診斷上[11]，而使用的方法一般基于狀態(tài)標(biāo)識(shí)圖或者網(wǎng)系統(tǒng)的結(jié)構(gòu)特征，而這些研究方法都與系統(tǒng)的行為關(guān)系理

論緊密聯(lián)系。因此，本文從行為輪廓的角度出發(fā)，探討系統(tǒng)Petri網(wǎng)模型合成時(shí)可能會(huì)產(chǎn)生的錯(cuò)誤與系統(tǒng)行為的變化域之間的關(guān)系。由于業(yè)務(wù)系統(tǒng)Petri網(wǎng)模型的結(jié)構(gòu)特征非常復(fù)雜，本文僅針對(duì)一類特殊的Petri網(wǎng)子類——自由選擇網(wǎng)，研究自由選擇網(wǎng)中模型合成可能存在的故障，并分析該類故障對(duì)系統(tǒng)行為變化域的影響。在已有源模型和事件發(fā)生序列集的基礎(chǔ)上，通過(guò)研究系統(tǒng)的行為軌跡所產(chǎn)生的行為弱序關(guān)系與源模型不一致的地方，分析產(chǎn)生這種變化可能的原因，研究產(chǎn)生該類變化的結(jié)構(gòu)特征，從而對(duì)可能發(fā)生的故障進(jìn)行定位，分析對(duì)應(yīng)系統(tǒng)的變化域。

1 基本定義

定義1[12-14](流程模型Petri網(wǎng))一個(gè)流程模型Petri網(wǎng)PN=(P,T,F,C)是一個(gè)四元組，滿足以下條件：(1)P是有限庫(kù)所集，T是有限變遷集；(2)P≠?,T≠?且P∩T=?；(3)F=(P×T)∪(T×P)表示PN的流關(guān)系且(P∪T,F)是強(qiáng)連通圖；(4)·X={Y(Y∈P∪T)∩((Y,X)∈F)}稱為X的前集，X·={Y(Y∈P∩T)∩((X,Y)∈F)}稱為X的后集；(5)dom(F)∪cod(F)=P∪T,其中dom(F)={x∈P∪T?y∈P∪T,(x,y∈F)}；cod(F)={x∈P∪T|?y∈P∪T,(y,x)∈F}；(6)C={and,xor,or}是流程網(wǎng)的結(jié)構(gòu)類型。

根據(jù)定義1，通過(guò)給出變遷前后集的約束，定義一類特殊的Petri網(wǎng)子類——自由選擇網(wǎng)。

定義2[14](自由選擇網(wǎng))設(shè)N=(S,T,F)是一個(gè)網(wǎng)，若?t1,t2∈T(t1≠t2)，·t1∩·t2≠?→|·t1|=|·t2|=1，則稱N為一個(gè)自由選擇網(wǎng)(free-choice net)。

定義3[15](弱序關(guān)系)一個(gè)流程模型Petri網(wǎng)PN=(P,T,F,C)是一個(gè)四元組，PN中存在一種弱序關(guān)系,即包含T×T所有的變遷對(duì)(x,y)中存在一個(gè)發(fā)生序列δ=t1t2…tn,當(dāng)i∈{1,2,…,n-1}時(shí),i

依據(jù)這種弱序關(guān)系我們定義了行為輪廓。

令ta、tb∈T1，tx、ty∈T2.(1)若ta=tb，那么對(duì)?tx∈T2,ta?tx，有taR1tatxR2tx；(2)若ta≠tb，那么對(duì)?tx、ty∈T2，tx≠ty.

有下列兩種情況中的一種成立：(1)ta?tx，tb?ty，有taR1tbtxR2ty；(2)ta?ty，tb?tx，有taR1tbtyR2tx.

根據(jù)定義4，將不滿足以上條件的變遷區(qū)域稱為變化域，即故障區(qū)域。

定義6[17](目標(biāo)模型N2的變化域)已知源模型Petri網(wǎng)為N1=(P1,T1,F1,C1)，目標(biāo)模型Petri網(wǎng)為N2=(P2,T2,F2,C2)，?tj,tj÷1∈T2對(duì)應(yīng)于ti,ti÷1∈T1，在可疑區(qū)域內(nèi)將目標(biāo)模型中不滿足源模型相應(yīng)變遷間行為輪廓關(guān)系的變遷構(gòu)成的集合{tj,tj÷1,…}稱為目標(biāo)模型N2的變化域，記為。

2 基于弱序關(guān)系的變化域分析

算法1：自由選擇網(wǎng)中故障變化域的定位算法(Algorithm for Fault Change Region Location in Free-choice Net,AFCRGL)

輸入：源模型——行為事件跡集合STrace，自由選擇Petri網(wǎng)(N,M0)；

輸出：故障的變化域范圍∑F=(PF,TF,FF,MF)。

步驟：

Step1 根據(jù)STrace，得到所有事件的行為弱序關(guān)系表table1；

Step2 通過(guò)源模型(N,M0)，得到標(biāo)簽事件間的行為弱序關(guān)系table2；

Step3 ?t∈STrace，確定t與(N,M0)中變遷的對(duì)齊關(guān)系align，滿足?t∈STrace,?ta∈T:t～ta；

Step4 將table2中的變遷進(jìn)行投影操作，即TA={ta|?t∈STrace∧ta∈T:t～ta},得到投影后的表table3；

Step5 尋找table3和table1中行為關(guān)系不一致的變遷對(duì)(tf1,tf2)，找出tf1,tf2在源模型中的對(duì)齊變遷taf1,taf2∈T；

Step6 通過(guò)子網(wǎng)運(yùn)算，得到源模型(N,M0)關(guān)于TF={taf1,taf2|tf1,tf2∈STrace∧tf1～taf1∧tf2～taf1∧R(tf1,tf2)≠R(taf1,taf2)}的子網(wǎng)，記為∑F=(PF,TF,FF,MF)；

Step7 ∑F=(PF,TF,FF,MF)就是所要定位的故障變化域。

下面舉例說(shuō)明上述算法的實(shí)施步驟。圖1給出了一個(gè)自由選擇網(wǎng)Petri網(wǎng)系統(tǒng)，根據(jù)弱序關(guān)系分析并結(jié)合行為輪廓理論，對(duì)源模型中各個(gè)變遷的發(fā)生順序及其發(fā)生的序關(guān)系進(jìn)行分析研究，為了更直觀地表達(dá)源模型中變遷原有的弱序關(guān)系，以表格的形式逐一列舉出各個(gè)變遷的發(fā)生序，圖1中各變遷的弱序關(guān)系見(jiàn)表1。

圖1 一個(gè)自由選擇網(wǎng)∑=(N,M0)

圖2 存在故障變遷后的自由選擇網(wǎng)∑′

由圖1，列出其所有的事件跡STrace1的集合：

STrace1={ABDEG,ABDEF,ABDEGEF,ACDEG,ACDEF,ACDEGEF}.

通過(guò)對(duì)事件跡集合中的變遷弱序關(guān)系分析，可以得到相關(guān)變遷的弱序關(guān)系表，如表1所示。

表1 圖1中的變遷弱序關(guān)系簡(jiǎn)表

現(xiàn)在捕捉到圖1中的事件跡STrace2的集合：

STrace2={ABDEG,ABDEF,ABDEGEF,ACDEG,ACDEF,ACDEGEF,ACF,ACGEF}.

通過(guò)捕捉到的事件跡，根據(jù)定義3可以得到相關(guān)變遷的弱序關(guān)系表(表2)。表2中用深色標(biāo)記出與表1不同的地方。這些不同的地方，就是所要研究的源模型中可能存在變化區(qū)域的位置。

表2 事件跡集合中的變遷弱序關(guān)系簡(jiǎn)表

通過(guò)源模型的事件跡STrace1和捕捉到的事件跡STrace2對(duì)比，將同名變遷進(jìn)行對(duì)齊發(fā)現(xiàn)(圖2)，圖2表明變遷T的發(fā)生影響了原有變遷發(fā)生的弱序關(guān)系，可以看出B、D變成了始終不發(fā)生，但A、C、T一直發(fā)生,當(dāng)E發(fā)生的時(shí)候，G一定發(fā)生，若F發(fā)生則E、G一定不發(fā)生，所以E、F、G共用T提供的發(fā)生權(quán)，E、G存在有序循環(huán)，原有的D、E、F、G存在的順序關(guān)系被影響，D不發(fā)生，E、F、G由于變化變遷T的發(fā)生依然存在發(fā)生的可能，而T的標(biāo)識(shí)來(lái)自于始終發(fā)生的C，推導(dǎo)出圖2，確定了可疑區(qū)域的大致范圍，如圖2中的虛線區(qū)域所示。

這些變遷的弱序關(guān)系發(fā)生變化，可能是由于系統(tǒng)運(yùn)行中產(chǎn)生的故障導(dǎo)致。例如，對(duì)圖1模型中出現(xiàn)新變遷T，稱為故障變遷，用深色標(biāo)記故障變遷，所形成的實(shí)際運(yùn)行模型如圖2所示。在實(shí)際的系統(tǒng)運(yùn)行過(guò)程中，導(dǎo)致事件變遷行為弱序關(guān)系發(fā)生改變的原因可能有很多，在本文由于篇幅限制，不作具體討論，相關(guān)的類型和故障原因分析將另文詳細(xì)闡述。

3 實(shí)例分析

圖3是一個(gè)柔性制造系統(tǒng)，由于其描述的系統(tǒng)具有典型性，因此被很多研究者作為典型案例進(jìn)行研究[17-19]，通過(guò)闡述實(shí)例來(lái)分析本文所給方法的有效性。圖3給出了源模型Petri網(wǎng)N1,根據(jù)定義2和定義3，對(duì)源模型變遷的弱序關(guān)系和捕捉到的可疑軌跡進(jìn)行對(duì)比分析。

源模型中除變遷集{ε13，ε15，ε17，t2}與{ε14，ε16，ε18，t3}是排他序關(guān)系之外，整個(gè)模型為一個(gè)大型的交互循環(huán)系統(tǒng)，變遷與變遷之間有潛在的嚴(yán)格序與逆嚴(yán)格序發(fā)生序列。已知一組得到的可疑軌跡{ε22,ε23,t6,t7,t8,t9,t10,ε24,t11}原本的嚴(yán)格序關(guān)系都不發(fā)生，只有t12發(fā)生，即系統(tǒng)右側(cè)停止運(yùn)行，ε14與{ε16，ε18，t3,ε19,ε20,t4,ε21,t5}由原本的嚴(yán)格序關(guān)系變?yōu)榻徊骊P(guān)系且{ε21，t5，ε24}可能選擇性不發(fā)生，即{ε14，ε16，ε18，t3}與{ε21，t5，ε24}為可能的變化區(qū)域，如圖4中虛線區(qū)域所示。

圖3 一個(gè)FMS生產(chǎn)實(shí)例

通過(guò)算法AFCRGL，可以判斷{ε14，ε16，ε18，t3}與{ε22,ε23,t6,t7,t8,t9,t10,ε24,t11}在t12發(fā)生后存在消耗庫(kù)所中標(biāo)識(shí)，此處為故障變遷ε25的位置，以深色標(biāo)記出故障變遷，ε25與t12為排他序關(guān)系，ε25與{ε16，ε18，t3,ε19,ε20，t4,ε21,t5}為嚴(yán)格序關(guān)系，也就導(dǎo)致了ε14與{ε16，ε18，t3,ε19,ε20,t4,ε21,t5}之間行為的變化。{ε21，t5，ε24}可能無(wú)發(fā)生權(quán)，即此處存在故障變遷ε26與{ε21，t5，ε24}為排他序關(guān)系。綜上所述，得到圖3存在故障變化變遷后的模型，如圖4所示。

圖4 圖3的一種可能故障定位

4 結(jié)語(yǔ)

本文在已有研究的基礎(chǔ)上，依據(jù)Petri網(wǎng)行為輪廓的性質(zhì)，對(duì)比源模型中變遷的弱序關(guān)系與捕捉到的可疑事件軌跡，找出不同，從而進(jìn)一步定位故障區(qū)域，根據(jù)弱序關(guān)系發(fā)生變化的位置及實(shí)際情況改變結(jié)構(gòu)來(lái)控制該變化的發(fā)生程度。未來(lái)關(guān)于業(yè)務(wù)流程模型的變化域，還有許多問(wèn)題需要去研究。例如，如何高效率定位復(fù)雜系統(tǒng)模型中的變化域，并對(duì)查找出的變化域進(jìn)行準(zhǔn)確的控制和精確的改進(jìn)，降低變化域帶來(lái)的影響等，都是將來(lái)要進(jìn)一步研究的問(wèn)題。

[1]Christian Gerth,Jochen M. Küster,Gregor Engels.Language-Independent change management of process models[C]. Denver:12th International Conference on Model Driven Engineering Languages and Systems,2009:152-166.

[2]Weber B,Rinderle S,Reichert M.Changepatterns and change support features in process-aware information systems[C].In 19th International Conference,Heidelberg:Springer Berlin Heidelberg,2007,4495:574-588.

[3]Weidlich M,Weske M,Mendling J.Changepropagation in process models using behavioral profiles[C].In 2009IEEE International Conference on Services Computing,Bangalore:IEEE,2009:33-40.

[4]Weidlich M,Mendling J,Weske M.Propagatingchanges between aligned process models[J].The Journal of Systems and Software,2012,85(8):1885-1898.

[5]Küster J M,Gerth C,F?rster A,et al.Detecting and resolving process model differences in the absence of a change log[C].Proceedings of the 6th International Conference on Business Process Management,Springer-Verlag,2008:244-260.

[6]S.Bohner,R.Arnold.Software change impact analysis[C].Proceedings of IEEE Computer Society Press,Los Alamitos,CA,USA,1996.

[7]R.S.Arnold,S.A.Bohner.Impact analysis-towards a framework for comparison[C].Proceedings of IEEE International Conference on Software Maintenance,1993:292-301.

[8]J.P.Loyall,S.A.Mathisen,C.P.Satterthwaite.Impact analysis and change management for avionics software[C]. Proceedings of IEEE National Aerospace and Electronics Conference,1997:740-747.

[9]S.L.P fleeger.Software engineering:theory and practice[C].Prentice Hall,Englewood Cliffs,NJ,1998.

[10]R.J.Turver,M.Munro.Early impact analysis technique for software maintenance[J].Journal of Software Maintenance:Research and Practice,1994,6(1):35-52.

[11]方歡,方賢文,李德權(quán).基于Petri 網(wǎng)的故障診斷研究理論的綜述[J].計(jì)算機(jī)科學(xué),2014,41(3):17-22.

[12]Smirnov S,Weidlich M,Mendling J.Businessprocess model abstraction based on behavioral profiles[C].In 8th International Conference,Heidelberg:Springer Berlin Heidelberg,2010,6470: 1-16.

[13]Mathias Weidlich,Mahias Weske,Jan Mendling.Change propagation in process models using behavioural profiles: Services Computing[C].Potsdam,Bangalore:IEEE Conference Publications,2009:33-40.

[14]吳哲輝.Petri網(wǎng)理論[M].北京:機(jī)械工業(yè)出版社,2006:6-42.

[15]Weidlich M,Mendling J,Weske M.Efficientconsistency measurement based on behavioral profiles of process models[J].IEEE Transactions on Software Engineer,2011,37(3):410-429.

[16]Weidlich M,Polyvyanyy A,Desai N,et al.Processcompliance measurement based on behavioral profiles[J]. Advanced Information Systems Engineering,2010,6051:499-514.

[17]趙芳,方賢文,方歡.Petri網(wǎng)動(dòng)態(tài)切片的最小變化域分析方法[J].計(jì)算機(jī)科學(xué)與探索,2016,10(4):516-523.

[18]C Mahulea,C Seatzu,M P Cabasino,et al.Fault diagnosis of discrete-event systems using continuous petri nets [J].IEEE Transactions on Systems,Man and Cybernetics A(S1083-4427),2012,42(4):970-984.

[19]F Basile,A Giua,C Seatzu.Petrinet control using event observers and timing information[C].Proceedings of 41th IEEE Conference on Decision Control(S1573-2878).USA:IEEE,2002:787-792.

[20]M P Cabasino,A Giua,M Pocci,et al.Discreteevent diagnosis using labeled petri nets:an application to manufacturing systems[J].Control Engineering and Practice(S0967-0661),2011,19(9):989-1001.

Researching the Method of Locating Change Region of System Fault based on Behavioral Profiles

ZHANG Yuan,FANG Huan

(College of Science,Anhui University of Science and Technology,Huainan Anhui 232001,China)

In business process management,the system fault is an important reason for the change of the system behavior,and how to locate the influence region of the system fault is an important research content of the business workflow system. In this paper,by capturing the event trace set of system behavior,comparing the weak order relation of the original model transitions,and proposing the Algorithm for Fault Change Region Location in free-choice net (AFCRGL) based on behavioral profiles,free -choice net is analyzed and studied. Through the analysis of the workflow in the behavior change of process,further refine search the position of domain changes region,and can control to reduce the influence of changes in the domain of process model. Finally,the effectiveness of the proposed method is verified by an example of a flexible manufacturing Petri net system.

change region;fault transition;weak order relation;behavioral profiles;Petri net

2016-06-07

安徽省自然科學(xué)基金項(xiàng)目“部分可觀系統(tǒng)故障診斷的Petri網(wǎng)理論及在行為變化診斷中的應(yīng)用”(1608085QF149)；國(guó)家自然科學(xué)基金項(xiàng)目“基于Petri網(wǎng)行為輪廓的業(yè)務(wù)流程交互下變化傳播機(jī)理及控制方法研究”(61472003)；國(guó)家自然科學(xué)基金項(xiàng)目“面向過(guò)程的可信Web服務(wù)組合方法及應(yīng)用研究”(61340003)；國(guó)家自然科學(xué)基金項(xiàng)目“基于行為Petri網(wǎng)的業(yè)務(wù)系統(tǒng)變化域分析方法及應(yīng)用研究”(61402011)。

張 源(1990- )，女，碩士研究生，從事Petri網(wǎng)理論與應(yīng)用與智能控制研究。

[作者簡(jiǎn)介]方 歡(1982- )，女，博士，副教授，碩士生導(dǎo)師，從事Petri網(wǎng)理論與應(yīng)用與智能控制研究。

TP301

A

2095-7602(2016)10-0052-07