基于行为轮廓的系统故障变化域定位方法研究

张 源，方 欢

(安徽理工大学理学院，安徽淮南 232001)



基于行为轮廓的系统故障变化域定位方法研究

张 源，方 欢

(安徽理工大学理学院，安徽淮南 232001)

在业务流程管理中，系统的故障是系统行为发生变化的重要原因，如何定位系统故障的影响范围是业务流系统的一项重要研究内容。本文基于Petri网的行为轮廓理论，对自由选择网进行分析和研究，通过捕捉系统行为的事件轨迹集合，对比源模型中变迁间的弱序关系，提出自由选择网故障变化域定位算法AFCRGL；通过分析流程中的行为变化，进一步精确寻找变化域的位置，可以控制并降低变化域对流程模型整体的影响。最后以一个柔性制造Petri网系统为例，验证本文提出方法的有效性。

变化域；故障变迁；弱序关系；行为轮廓；Petri网

随着计算机系统和业务系统规模的不断增大，由系统合成和模型合成所引起的系统发生错误的情况也越来越多，因此针对业务系统的行为变化分析和故障定位的研究是十分必要的。在已有的研究结论中，大部分有关行为变换分析的研究成果都出自业务流系统的变化域分析领域。业务流系统(Business Process Management System，BPMS)在生产实践中有着广泛的应用，设计业务流系统模型的主要目的是为了适应不同层次的业务需求，由于业务需求分析的角度不同，从而导致同一个模型因为关注的层次不同而具有不同层次的模型。所谓变化域，是指业务流系统中模型的行为目标和实际模型的行为特征之间存在不一致性[1]，这种不一致性可能会影响业务流系统行为的安全性，因此对业务系统的变化域进行分析尤为重要。

已有研究结论表明，使用Petri网和行为轮廓的相关理论对变化域分析是十分有效的。目前，国内外有很多利用Petri网对变化域展开研究的成果，通过对流程模型变化域分类，提出了增强系统性功能的变化域模式[2]；M.Weidlich和J.Mending等给出了流程模型的变化域传播，在已知源模型变化域的前提下，基于边界变迁与内部边界变迁的变化，确定了目标模型的变化域[3-4]；在此基础上，Küster JM和Gerth C 等通过使用流程模型间的一致和单输入、单输出结构分解的定义来寻找变化区域，但此方法是在缺少变化日志的前提下提出的，因此有一定的局限性[5]。定位变化区域后，分析变化区域对业务流程的影响，可以帮助维护人员预测变化影响的范围和程度，通常被称为影响分析，它是解决这些潜在变化影响的方法[4-10]。

系统故障是影响系统行为变化的一个主要因素。使用Petri网对故障的研究大都集中在故障的检测与诊断上[11]，而使用的方法一般基于状态标识图或者网系统的结构特征，而这些研究方法都与系统的行为关系理

论紧密联系。因此，本文从行为轮廓的角度出发，探讨系统Petri网模型合成时可能会产生的错误与系统行为的变化域之间的关系。由于业务系统Petri网模型的结构特征非常复杂，本文仅针对一类特殊的Petri网子类——自由选择网，研究自由选择网中模型合成可能存在的故障，并分析该类故障对系统行为变化域的影响。在已有源模型和事件发生序列集的基础上，通过研究系统的行为轨迹所产生的行为弱序关系与源模型不一致的地方，分析产生这种变化可能的原因，研究产生该类变化的结构特征，从而对可能发生的故障进行定位，分析对应系统的变化域。

1 基本定义

定义1[12-14](流程模型Petri网)一个流程模型Petri网PN=(P,T,F,C)是一个四元组，满足以下条件：(1)P是有限库所集，T是有限变迁集；(2)P≠Ø,T≠Ø且P∩T=Ø；(3)F=(P×T)∪(T×P)表示PN的流关系且(P∪T,F)是强连通图；(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}是流程网的结构类型。

根据定义1，通过给出变迁前后集的约束，定义一类特殊的Petri网子类——自由选择网。

定义2[14](自由选择网)设N=(S,T,F)是一个网，若∀t1,t2∈T(t1≠t2)，·t1∩·t2≠∅→|·t1|=|·t2|=1，则称N为一个自由选择网(free-choice net)。

定义3[15](弱序关系)一个流程模型Petri网PN=(P,T,F,C)是一个四元组，PN中存在一种弱序关系,即包含T×T所有的变迁对(x,y)中存在一个发生序列δ=t1t2…tn,当i∈{1,2,…,n-1}时,i

依据这种弱序关系我们定义了行为轮廓。

令ta、tb∈T1，tx、ty∈T2.(1)若ta=tb，那么对∀tx∈T2,ta≻tx，有taR1tatxR2tx；(2)若ta≠tb，那么对∀tx、ty∈T2，tx≠ty.

有下列两种情况中的一种成立：(1)ta≻tx，tb≻ty，有taR1tbtxR2ty；(2)ta≻ty，tb≻tx，有taR1tbtyR2tx.

根据定义4，将不满足以上条件的变迁区域称为变化域，即故障区域。

定义6[17](目标模型N2的变化域)已知源模型Petri网为N1=(P1,T1,F1,C1)，目标模型Petri网为N2=(P2,T2,F2,C2)，∀tj,tj÷1∈T2对应于ti,ti÷1∈T1，在可疑区域内将目标模型中不满足源模型相应变迁间行为轮廓关系的变迁构成的集合{tj,tj÷1,…}称为目标模型N2的变化域，记为。

2 基于弱序关系的变化域分析

算法1：自由选择网中故障变化域的定位算法(Algorithm for Fault Change Region Location in Free-choice Net,AFCRGL)

输入：源模型——行为事件迹集合STrace，自由选择Petri网(N,M0)；

输出：故障的变化域范围∑F=(PF,TF,FF,MF)。

步骤：

Step1 根据STrace，得到所有事件的行为弱序关系表table1；

Step2 通过源模型(N,M0)，得到标签事件间的行为弱序关系table2；

Step3 ∀t∈STrace，确定t与(N,M0)中变迁的对齐关系align，满足∀t∈STrace,∃ta∈T:t～ta；

Step4 将table2中的变迁进行投影操作，即TA={ta|∃t∈STrace∧ta∈T:t～ta},得到投影后的表table3；

Step5 寻找table3和table1中行为关系不一致的变迁对(tf1,tf2)，找出tf1,tf2在源模型中的对齐变迁taf1,taf2∈T；

Step6 通过子网运算，得到源模型(N,M0)关于TF={taf1,taf2|tf1,tf2∈STrace∧tf1～taf1∧tf2～taf1∧R(tf1,tf2)≠R(taf1,taf2)}的子网，记为∑F=(PF,TF,FF,MF)；

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

下面举例说明上述算法的实施步骤。图1给出了一个自由选择网Petri网系统，根据弱序关系分析并结合行为轮廓理论，对源模型中各个变迁的发生顺序及其发生的序关系进行分析研究，为了更直观地表达源模型中变迁原有的弱序关系，以表格的形式逐一列举出各个变迁的发生序，图1中各变迁的弱序关系见表1。

图1 一个自由选择网∑=(N,M0)

图2 存在故障变迁后的自由选择网∑′

由图1，列出其所有的事件迹STrace1的集合：

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

通过对事件迹集合中的变迁弱序关系分析，可以得到相关变迁的弱序关系表，如表1所示。

表1 图1中的变迁弱序关系简表

现在捕捉到图1中的事件迹STrace2的集合：

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

通过捕捉到的事件迹，根据定义3可以得到相关变迁的弱序关系表(表2)。表2中用深色标记出与表1不同的地方。这些不同的地方，就是所要研究的源模型中可能存在变化区域的位置。

表2 事件迹集合中的变迁弱序关系简表

通过源模型的事件迹STrace1和捕捉到的事件迹STrace2对比，将同名变迁进行对齐发现(图2)，图2表明变迁T的发生影响了原有变迁发生的弱序关系，可以看出B、D变成了始终不发生，但A、C、T一直发生,当E发生的时候，G一定发生，若F发生则E、G一定不发生，所以E、F、G共用T提供的发生权，E、G存在有序循环，原有的D、E、F、G存在的顺序关系被影响，D不发生，E、F、G由于变化变迁T的发生依然存在发生的可能，而T的标识来自于始终发生的C，推导出图2，确定了可疑区域的大致范围，如图2中的虚线区域所示。

这些变迁的弱序关系发生变化，可能是由于系统运行中产生的故障导致。例如，对图1模型中出现新变迁T，称为故障变迁，用深色标记故障变迁，所形成的实际运行模型如图2所示。在实际的系统运行过程中，导致事件变迁行为弱序关系发生改变的原因可能有很多，在本文由于篇幅限制，不作具体讨论，相关的类型和故障原因分析将另文详细阐述。

3 实例分析

图3是一个柔性制造系统，由于其描述的系统具有典型性，因此被很多研究者作为典型案例进行研究[17-19]，通过阐述实例来分析本文所给方法的有效性。图3给出了源模型Petri网N1,根据定义2和定义3，对源模型变迁的弱序关系和捕捉到的可疑轨迹进行对比分析。

源模型中除变迁集{ε13，ε15，ε17，t2}与{ε14，ε16，ε18，t3}是排他序关系之外，整个模型为一个大型的交互循环系统，变迁与变迁之间有潜在的严格序与逆严格序发生序列。已知一组得到的可疑轨迹{ε22,ε23,t6,t7,t8,t9,t10,ε24,t11}原本的严格序关系都不发生，只有t12发生，即系统右侧停止运行，ε14与{ε16，ε18，t3,ε19,ε20,t4,ε21,t5}由原本的严格序关系变为交叉关系且{ε21，t5，ε24}可能选择性不发生，即{ε14，ε16，ε18，t3}与{ε21，t5，ε24}为可能的变化区域，如图4中虚线区域所示。

图3 一个FMS生产实例

通过算法AFCRGL，可以判断{ε14，ε16，ε18，t3}与{ε22,ε23,t6,t7,t8,t9,t10,ε24,t11}在t12发生后存在消耗库所中标识，此处为故障变迁ε25的位置，以深色标记出故障变迁，ε25与t12为排他序关系，ε25与{ε16，ε18，t3,ε19,ε20，t4,ε21,t5}为严格序关系，也就导致了ε14与{ε16，ε18，t3,ε19,ε20,t4,ε21,t5}之间行为的变化。{ε21，t5，ε24}可能无发生权，即此处存在故障变迁ε26与{ε21，t5，ε24}为排他序关系。综上所述，得到图3存在故障变化变迁后的模型，如图4所示。

图4 图3的一种可能故障定位

4 结语

本文在已有研究的基础上，依据Petri网行为轮廓的性质，对比源模型中变迁的弱序关系与捕捉到的可疑事件轨迹，找出不同，从而进一步定位故障区域，根据弱序关系发生变化的位置及实际情况改变结构来控制该变化的发生程度。未来关于业务流程模型的变化域，还有许多问题需要去研究。例如，如何高效率定位复杂系统模型中的变化域，并对查找出的变化域进行准确的控制和精确的改进，降低变化域带来的影响等，都是将来要进一步研究的问题。

[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]方欢,方贤文,李德权.基于Petri 网的故障诊断研究理论的综述[J].计算机科学,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网理论[M].北京:机械工业出版社,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网动态切片的最小变化域分析方法[J].计算机科学与探索,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

安徽省自然科学基金项目“部分可观系统故障诊断的Petri网理论及在行为变化诊断中的应用”(1608085QF149)；国家自然科学基金项目“基于Petri网行为轮廓的业务流程交互下变化传播机理及控制方法研究”(61472003)；国家自然科学基金项目“面向过程的可信Web服务组合方法及应用研究”(61340003)；国家自然科学基金项目“基于行为Petri网的业务系统变化域分析方法及应用研究”(61402011)。

张 源(1990- )，女，硕士研究生，从事Petri网理论与应用与智能控制研究。

[作者简介]方 欢(1982- )，女，博士，副教授，硕士生导师，从事Petri网理论与应用与智能控制研究。

TP301

A

2095-7602(2016)10-0052-07