一种有时间约束的复杂Petri网建模方法

黄敏，魏伟

(长沙理工大学 计算机与通信工程学院，湖南 长沙，410014)

用传统Petri网对系统过程进行建模和分析时[1]，随着系统复杂性的增加，其状态空间呈指数级增长，分析难度急剧增加，造成 Petri网对复杂系统的建模和分析很困难。尤其是当系统具有时间约束时，传统Petri网的描述能力有限，分析方法和手段不够完善。为此，如何降低Petri网的建模复杂性和增强分析能力已成为研究热点和难点。

1 相关的研究基础

为降低复杂系统的建模和分析难度，一些研究者[2-4]主要从3个方面对传统Petri网进行改进：一是利用面向对象[2]的概念，将逻辑上相对独立的过程抽象为一个对象，其中的变化细节封装在对象内部，这样就能在相对较大的粒度上对系统进行建模和分析，达到降低难度的目的，同时增强系统的可重用性和可剪裁性；二是利用分层[3]的概念，将一个大系统划分为几个子网，子网又可以细分为更小的子网，通过对子网性质的分析来反映原网的部分或全部性质，以此达到降低建模和分析的难度。以上2种方法主要用于对实际系统的建模和分析。三是各种化简技术[4]，最早提出化简思想的是Hack；Lipton 引入D-化简技术，并用于化简并行程序；Kowalk和Valk推广了化简思想，建立化简定理；Murata等[5]针对T图提出若干化简规则，并讨论这些规则对活性、安全性的保持关系；Lee等提出Petri网的等级化简和分解方法，定义可化简子网、子网的等级以及宏结点等概念；Ramamoorthy等[6]提出新概念SWBM。SWBM是满足一定条件的子网，将其化简成为单一的变迁，并且化简后的 Petri网保持原网的所有性质。第3种方法主要用于理论研究。为增强对时间的描述能力，通常在库所、变迁以及连接库所和变迁的有向弧上添加时间信息，从而形成各种时间 Petri网模型，其中 Timed Petri Nets，Stochastic Petri Nets，Time Petri Nets与 Timing Constraint Petri Nets等模型的影响较大。Timed Petri Nets由 Ramchandnai[7]提出，在每一个变迁上添加 1个时间延迟Tdel，它遵循强触发规则[8]，即一个变迁tj对应1个时间延迟Tdel，如果在时间T0，tj的所有输入库所的Token均准备就绪，那么变迁 tj立即执行。在时间(T0，T0+ Tdel)内，所有输入库所的 Token都归 tj所使用，其余变迁不能使用。在时刻T0+Tdel到来时，tj输入库所的 Token就被转移到相应的输出库所中。Timed Petri Nets及其相关模型主要用于并发系统的性能分析。Stochastic Petri Nets[9]是对Timed Petri Nets的改进，由于在变迁发生之前，无法给出每个变迁的准确时间延迟，但可以通过以前的经验或者期望来推断变迁的执行延迟符合某种概率分布，因此，可以利用变迁执行的平均时间代表变迁的延迟。Stochastic Petri Nets主要用于性能评价，林闯[9]在这方面做了许多工作。Time Petri Net(TPN)由Merlin等首先提出。它将Timed Petri Nets中变迁的时间延迟替换为一个使能区间(TCmin, TCmax) (其中，TCmin表示相应变迁使能前所必须流逝的最小时间，TCmax表示相应变迁触发前可以经历的最长时间)，它遵循强触发规则，但变迁的执行是瞬间完成的，而Timed Petri Nets和Stochastic Petri Nets中变迁的执行均需要一段时间。TPN已被证明可比较方便地表示并发系统中的时间约束，应用于各种实时系统的时间行为分析和性能评估等方面。Timing Constraint Petri Nets(TCPN)由 Tsai[10]提出。鉴于事件的发生条件有时也有时间要求，因此，TCPN中库所和变迁上均有时间约束信息。库所的时间约束借鉴TPN的思路，变迁的时间约束借鉴 Timed Petri Nets和TPN。TCPN遵循弱触发规则，即变迁的触发不仅受制于变迁的外延，而且与变迁及其输入库所上的时间约束信息密切相关。本文作者在面向对象和Timing Constraint Petri Nets的基础上，提出面向对象时间Petri网(Oriented Object Timing Constraint Petri Nets，简称OOTCPN’s)的定义及其建模方法，通过建立时延关联矩阵等措施，试图在降低系统复杂性的同时，分析系统的时间约束特性，找出系统的瓶颈，从理论角度为系统改进和优化提供决策依据。

2 OOTCPN’s的定义

在 OOTCPN’s中，系统由相互通信的物理对象和它们之间的联系构成，物理对象是协议的参与者[10-16]。

定义1 系统S是一个三元组，S=(O, R, TC)称为面向对象时间约束Petri网，其中O={Oi, i=1, 2, …, I,I∈N}, Oi为系统中的对象，O为系统对象的集合；R为对象之间关系的集合；TC为时间约束。

对象的动态行为表现为内部活动变迁和外部信息传递。前者由对象内的状态库所和活动变迁表示，后者通过各对象间发送和接收信息的消息库所获得。对象行为受时间约束。

定义 2 对象 Oi定义为：Oi=(Pi，Ti，Fi)。

(1) Pi= { APi,PIi, POi}。其中：APi， PIi和 POi分别为对象内状态库所集、对象输入消息库所集和对象输出消息库所集，消息库所是对象与外界进行通信的接口，消息库所之间传递的消息用托肯表示。

(2) Ti= { ATi, OTi}。其中： ATi为对象内状态变迁有限集合； OTi为对象的操作，对象的操作是对对象内状态变迁进行抽象。

复杂的对象可以细化为1个TCPN’s。

对象由消息库所和对象的操作之间的弧线封闭而成，对象的数据、结构都被限制在这个边界内，对外不可见，外界只能通过消息库所和对象的操作与对象进行通信，从而实现对象的封装。

Pi和 Ti必须满足条件 Ti∪Pi≠∅ ，Ti∩Pi=∅ 。

(3) Fi是对象 Oi内关系的集合，Fi={Pi×Ti∪Ti×Pi}。

定义3 对象间关系定义为：R={P, G, F}。其中：

(1) P= { POk, PIk}。POk和PIk分别为与门gk相连接的对象的输出消息库所和输入消息库所，其实质就是对象的输出消息库所 POi和输入消息库所 PIi。

(2) G为对象间信息传递门gk的有限集合。

门实现对象之间的消息传递，被看作是一种特殊的变迁。门gk与前一对象的输出消息库所 POk和后一对象的输入消息库所 PIk相关联。若 POk中至少有1个消息(或托肯)，则 gk使能，并在时间区间[Eft(gk),Lft(gk)]内触发(其中Eft(gk)表示门变迁gk的最早触发事件，Lft(gk)表示gk的最晚触发时间)，若能成功触发，则消息(或托肯)传递到 PIk。从外界看，1个门能否成功触发表现为与之相关的对象之间能否进行消息传递。

(3) F是对象间的流关系，F=P×G∪G×P。

定义4 对象的时间约束TC={C，D}。其中：

(2) D表示对象内状态改变或对象间消息传递所需的时间，用[D(TG)]表示，且[D(TG)]≥0。以对象间消息传递门gk为例，D=[D(gk)]≥0，表示门gk接收到消息并触发，需要占用 D(gk)时间，才能将消息发往另一对象。对象内状态改变记为D=[D(OT)]≥0，表示需占用D(OT)时间，对象Oi才能从一个状态改变到另一状态。

图1 对象及其之间的关系Fig.1 Objects and their relationship

面向对象时间约束Petri网如图1所示，该模型有4个对象(O1, O2, O3, O4),对象内通过 OTi(i=1, 2, 3, 4)进行状态改变，所需要的时间分别为 20，20，25和20。对象间通过门变迁 g1和 g2进行信息传递。当 2个门变迁在时刻T0使能，因竞争对象O1资源，而g1的触发区间是(T0+5, T0+10)，g2的触发区间是(T0+10,T0+20)，可知T0+Eft(g1)＜T0+Eft(g2)，因此，门变迁g1有优先触发权。若门变迁g1在触发区间(T0+5, T0+10)内未成功触发，则失去触发权，此时，到达门变迁g2的触发区间，则g2有触发权。

3 OOTCPN's的动态运行规则

OOTCPN’s中的 token依照动态运行规则不断地在对象中传递，这个过程描述了系统的动态特性，也反映了消息在系统中的产生和传递过程。

3.1 OOTCPN’s的状态

OOTCPN’s中一个状态 M 是一个二元组{W,TC}，其中W为对象状态。由于在信息系统中，消息有“输入”、“输出”和“无”3种状态，所以，规定W(Oi)=“1”表示对象 Oi有消息要输入，W(Oi)=“-1”表示对象Oi有消息要输出；否则，W(Oi)=“0”。

TC为系统状态发生的时间特性。

3.2 前集后集的概念

3.3 门变迁的使能条件

在T0时刻，若， W ( Oi)=1，则gk使能，记为enable(gk)。

3.4 门变迁的触发条件

门变迁gk在时刻T 触发需满足以下3个条件，记为M[gk＞：

(1) enable(gk);

(2) Lft(gk)-Eft(gk)＞0;

(3) Lft(gk)≤FIRE(T)≤Eft(gk))，其中 FIRE(T)叫触发时刻。

3.5 门变迁的发生后果

若M[gk＞，则gk在M可以发生，将标识M={W,TC}改变为 M 的后继 M′={W′, TC'}。

W'的定义是：

TC'的定义为：

3.6 门变迁的可达性

若存在变迁序列 g1, g2, …, gk和状态序列 M1,M2, …, Mk使得

则称MK是从M1可达的。若变迁序列g1, g2, …, gk为σ，则式(1)可以记为 M1[σ＞MK。

3.7 变迁时延

用delay(TC)表示运行所需的时延之和，则

3.8 关联矩阵

关联矩阵是 Petri网中用于判断变迁是否有发生权以及计算变迁发生效果的有力工具，为使OOTCPN's具有较强的系统分析能力，定义状态关联矩阵C和时延关联矩阵T。

定义5 状态关联矩阵C。

(1) 以对象集O为序标集的行向量V：O→Z叫做S的O-向量，其中Z是整数集。

(2) 以门集G为序标集的列向量U：G→Z叫做S的G-向量。

对于gk∈G, U(gk)表示门变迁gk在变迁序列σ中的触发次数。

(3) 以O×G为序标集的矩阵C：O×G→Z叫做S的状态关联矩阵，其矩阵元素为：

定义6 时延关联矩阵T。

(1) 以对象集O为序标集的行向量V：O→Z叫做S的O-向量，其中Z是整数集。

(2) 以门集G为序标集的列向量U：G→Z叫做S的G-向量。

(3) 以O×G为序标集的矩阵T：O×G→Z叫做S的时延关联矩阵，其矩阵元素表示变迁所需的最短时延。

定理1 对于M={W, TC}，M0为初始状态，TC0为初始时延，C为状态关联矩阵，T为时延关联矩阵，若经过变迁序列σ后达到状态M，则存在非负整数n维向量U使得：

式(2)称为系统状态方程；式(3)称为系统时间特性方程。

证明：根据定义5，状态关联矩阵元素的值W(Oi,gk)-W(gk, Oi)描述的是门变迁gk发生时输入输出的最终效果，g1发生后，M1=M0+C，而 U(gk)表示门变迁gk在变迁序列σ中的触发次数，很明显，经过变迁序列 σ后M=M0+C·U。

定理1得证。

4 OOTCPN’s的建模分析步骤

(1) 建立对象模型。根据系统的运行规则，将一些相对独立的过程抽象为“对象”或“门”变迁，以简化系统的建模规模，明确对象或门的名称、属性、操作，并确定时间约束。一些复杂的对象、门可以细化为一个系统。

(2) 确定对象消息库所及对象间的通信网关(即门变迁)。根据现实系统中实体对象以及它们与周围环境的关系，建立消息库所和对象之间的消息关系。

(3) 构建完整的OOTCPN’s模型。根据确定的对象，消息库所和对象间关系建立OOTCPN’s网模型；

(4) 模型分析。根据 OOTCPN’s网模型，建立模型状态关联矩阵C和时延关联矩阵T，分析模型运行时间，为系统或流程改进提供参考依据。

5 应用实例

本文以保险索赔过程为例进行建模与分析。该实例原型请参见文献[8]。由于保险索赔过程比较复杂，将一些相对独立的过程抽象为门变迁，见表1所示。根据OOTCPN’s建模步骤，建立如图2所示的保险索赔过程OOTCPN’s模型，下面使用本文提出的方法对其进行分析。

系统初始状态M0=(1,0,0,0,0,0,0,0,0)T。

行向量V={O1,O2,O3,O4,O5,O6,O7,O8,O9}。

列向量U={g1,g2,g3,g4,g5,g6,g7,g8}T。

根据定义5和定义6可得模型状态关联矩阵C和时延关联矩阵T。

表1 门变迁及其含义Table 1 Transitions and their meaning

状态关联矩阵为：

时延关联矩阵为：

由图2知：由申请索赔到索赔成功并记录赔付有2种变迁序列，σ1=g1g4g5，即U1=(1,0,0,1,1,0,0,0)T以及σ2=g1g4g6，即 U2=(1,0,0,1,0,1,0,0)T。

初始时延 TC0={0}，根据式(4)，时延 TC′1=T+ T ×U=(1,8,0,9,4,3,0,0,0)T

根据式(2)，delay(TC1)=1+8+9+4+3=25；时延TC′2=TC0+T×U2=(1,8,0,4,9,0,3,0,0)T；delay(TC2)=1+8+4+9+3=25。

可知：delay(TC1)=delay(TC2)，即索赔过程中定损与材料整理所需时间相同，可在同一时间进入记录赔付阶段而无需等待。图 2确定的时间约束是合理的(注：建模过程中时间约束 C未标注，则表示默认为(0,∞)，D 默认为[0])。

如果计算结果是delay(TC1)≠delay(TC2)，就要减小delay值小的分支的资源配置(包括人力、物力、财力)，增大delay值大的分支的资源配置，使两者趋于平衡。增大与减小的具体数值可根据相应的比例来计算。

6 结论

(1) 在面向对象和Timing Constraint Petri Nets的基础上，提出面向对象时间 Petri网(OOTCPN’s)的概念、动态运行规则和建模方法，增强了Petri网对有时间约束的复杂系统的模拟和分析能力。

(2) 提出了描述 OOTCPN’s模型关联矩阵和时延关联矩阵，用于判断变迁是否有发生权以及计算变迁发生的后果，使得OOTCPN’s具有较强的系统分析能力。通过对保险索赔过程的实例分析，表明本文所提方法能较好地模拟和分析复杂系统的时间约束特性。

[1] Tasi J J P, Yang S J. Timing constraint Petri nets and their application to schedulability analysis of real-time system specifications[J]. IEEE Trans Software Engineering, 1995, 21(1):32-49.

[2] 顾妍午, 王遵彤, 吴启迪. 面向对象 Petri网技术在系统建模中的应用[J]. 同济大学学报: 自然科学版, 2010, 38(3):437-441.GU Yan-wu, WANG Zun-tong, WU Qi-di, Application of object-oriented Petri-nets in system modeling[J]. Journal of Tongji University: Natural Science, 2010, 38(3): 437-441.

[3] 杨雪, 蒋昌俊. Petri网化简规则在系统中的实现[J]. 算机工程与应用, 2003, 40(32): 66-68.YANG Xue, JIANG Chang-jun. Realization of the reduction methods of Petri net in the system[J]. Computer Engineering and Application, 2003, 40(32): 66-68.

[4] 汪琳, 乐晓波, 陈国平. Petri网化简技术的研究[J]. 系统仿真学报, 2007, 19(S1): 110-113.WANG Lin, YUE Xiao-bo, CHEN Guo-ping. The research of Petri net’s simplified technology[J]. Journal of System Simulation, 2007, 19(S1): 110-113.

[5] Murata I, Suzuki T, Shatz S. Fuzzy-timing high-level Petri nets(FTHNs) for time-critical systems[J]. J Cardoso and Camargo,1999, 22(3): 88-114.

[6] Ramamoorthy C V, Yaw Y. A petri net reduction algorithm for protocol analysis[C]//SIGCOMM ’86 Proceedings of the ACM SIGCOMM Conference on Communications Architectures &Protocols. 1986, 8(16): 157-166.

[7] Ramchandani C. Analysis of asynchronous concurrent system by timed Petri nets[D]. Cambridge: MIT, 1974: 10-20.

[8] 宋巍, 窦万春, 刘西萍. 时间约束 Petri网及其可调度性分析与验证[J]. 软件学报, 2007, 18(1): 11-21.SONG Wei, DOU Wan-chun, LIU Xi-ping. Timing constraint Petri nets and their schedulability analysis and verification[J].Journal of Software, 2007, 18(1): 11-21.

[9] 林闯. 随机Petri网和系统性能评价[M]. 2版. 北京: 清华大学出版社, 2005: 35-48.LIN Chuang. Stochastic Petri nets and system performance evaluation[M]. 2nd ed. Beijing: Tsinghua University Press, 2005:35-48.

[10] Tsai J J P, Yang S J, Chang Y H. Timing constraint Petri nets and their application to schedulability analysis of real-time system specifications[J]. IEEE Transactions on Software Engineering,1995, 21(1): 32-49.

[11] CHENG Bin, WANG Xin-gang, Li Ying. Study on parallel system performance modeling based on TCPN[J]. High Performance Computing and Applications, 2010, 45(21):108-113.

[12] CHENG Bin, Xin gang, WANG Wei-qin. Formal modeling of parallel system based on TCPN[J]. Network and Parallel Computing, 2009, 6(11): 464-470.

[13] JIANG Ping, GAO Liang, LI Pei-gen. Collaborative execution mechanisms for the TCPN-enhanced process-view approach based inter-enterprises workflow[J]. 2009 13th International Conference on Computer Supported Cooperative Work in Design,2009, 15(23): 480-485.

[14] PANG Hui, FANG Zong-de, ZHAO Yong. Simplification analysis and schedulability verification of timing constraint workflow model[J]. Computer Integrated Manufacturing System,2008, 34(2): 4532-4538.

[15] GUO Yin-zhang, ZENG Jian-chao. A temporal logic inference for collaborative product design process based on time constraint Petri nets[J]. Journal of Computer-Aided Design &Computer Graphics, 2010, 33(9): 405-415.

[16] 刘韬, 傅卫平, 王雯, 等. 基于面向对象赋时Petri网的出入库系统建模[J]. 系统仿真学报, 2006, 18(3): 537-541.LIU Tao, FU Wei-ping, WANG Wen, et al. Modeling of loading and unloading scheduling system based on object-oriented timed Petri net[J]. Journal of System Simulation, 2006, 18(3):537-541.