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

黄敏，魏伟

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

摘要：在面向对象技术和时间约束Petri网的基础上，给出面向对象时间Petri网的定义、变迁发生的条件、后果等动态运行规则及建模方法，以降低有时间约束复杂系统的建模难度；提出时延关联矩阵的概念和计算方法，用于判断变迁是否有发生权以及计算变迁发生效果，证明相关定理，以增强系统的分析能力。在实际建模过程中，通过计算时延关联矩阵，找出系统的时间瓶颈，为改进和优化系统提供理论依据。通过保险索赔过程的建模和实例分析，证明了本文所提方法的有效性。

关键词：面向对象；时间约束；动态运行规则；时延关联矩阵

中图分类号：TP391            文献标志码：A         文章编号：1672-7207(2012)03-1027-06

One modeling method research of complex Petri nets with timing constraint

HUANG Min, WEI Wei

(College of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha 410014, China)

Abstract: Oriented object timing constraint Petri nets were defined. Dynamic working rules and modeling methods were proposed based on object-oriented technology and time constraints of Petri nets to reduce the difficulty of complex Petri nets with timing constraint. The conception of delay time related matrix and its computing method were proposed. The happening right of transition can be judged and its effect can be computed. The related theorem was proved. So the analysis ability was increased. The delay time related matrix was computed to find the system’s bottleneck in the process of modeling. Therefore, the theory evidence was obtained to improve and optimize the system. The example of insurance claiming process shows that the proposed method is effective.

Key words: object-oriented; time constraints; dynamic working rules; delay time related matrix

用传统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个时间延迟T_del，它遵循强触发规则^[8]，即一个变迁t_j对应1个时间延迟T_del，如果在时间T₀，t_j的所有输入库所的Token均准备就绪，那么变迁 t_j立即执行。在时间(T₀，T₀+ T_del)内，所有输入库所的Token都归t_j所使用，其余变迁不能使用。在时刻T₀+T_del到来时，t_j输入库所的Token就被转移到相应的输出库所中。Timed Petri Nets及其相关模型主要用于并发系统的性能分析。Stochastic Petri Nets^[9]是对Timed Petri Nets的改进，由于在变迁发生之前，无法给出每个变迁的准确时间延迟，但可以通过以前的经验或者期望来推断变迁的执行延迟符合某种概率分布，因此，可以利用变迁执行的平均时间代表变迁的延迟。Stochastic Petri Nets主要用于性能评价，林闯^[9]在这方面做了许多工作。Time Petri Net(TPN)由Merlin等首先提出。它将Timed Petri Nets中变迁的时间延迟替换为一个使能区间(T_Cmin, T_Cmax) (其中，T_Cmin表示相应变迁使能前所必须流逝的最小时间，T_Cmax表示相应变迁触发前可以经历的最长时间)，它遵循强触发规则，但变迁的执行是瞬间完成的，而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, T_C)称为面向对象时间约束Petri网，其中O={O_i , i=1, 2, …, I, I∈N}, O_i为系统中的对象，O为系统对象的集合；R为对象之间关系的集合；T_C为时间约束。

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

定义2  对象O_i定义为：O_i=(P_i，T_i，F_i)。

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

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

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

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

P_i和T_i必须满足条件T_i∪P_i≠，T_i∩P_i=。

(3) F_i是对象O_i内关系的集合，F_i={P_i×T_i T_i×P_i}。

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

(1) 。和分别为与门g_k相连接的对象的输出消息库所和输入消息库所，其实质就是对象的输出消息库所和输入消息库所。

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

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

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

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

(1) C为与库所或门相关联的正实数对集合，用[E_ft(g_k), L_ft(g_k)]表示, 且满足条件L_ft(g_k)≥E_ft(g_k)。表示门变迁在时间区间[E_ft(g_k), L_ft(g_k)]内触发。

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

图1  对象及其之间的关系

Fig.1  Objects and their relationship

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

3  OOTCPN's的动态运行规则

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

3.1  OOTCPN’s的状态

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

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

3.2  前集后集的概念

(1) ^.g_k={O_i│()∈R且}称为g_k的前集或输入集，用^.g_k表示；

(2) g_k^.={O_j│()∈R且∈O_j}称为g_k的后集或输出集，用g_k^.表示。

(3) ^·g_k^·=^·g_k∪g_k ^·称为g_k的外延。

3.3  门变迁的使能条件

在T₀时刻，若，，则g_k使能，记为enable(g_k)。

3.4  门变迁的触发条件

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

(1) enable(g_k);

(2) L_ft(g_k)-E_ft(g_k)＞0;

(3) L_ft(g_k)≤F_IRE(T)≤E_ft(g_k))，其中F_IRE(T)叫触发时刻。

3.5  门变迁的发生后果

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

W'的定义是：

T_C'的定义为：

3.6  门变迁的可达性

若存在变迁序列g₁, g₂, …, g_k和状态序列M₁, M₂, …, M_k使得

M₁[g₁＞M₂[g₂＞…M _K-1 [g_K-1＞M_K      (1)

则称M_K是从M₁可达的。若变迁序列g₁, g₂, …, g_k为σ，则式(1)可以记为M₁[σ＞M_K。

3.7  变迁时延

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

delay(T_C)=∑T [i]                   (2)

3.8  关联矩阵

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

定义5  状态关联矩阵C。

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

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

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

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

C(O_i, g_k)=W(O_i, g_k)-W(g_k, O_i)

定义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的时延关联矩阵，其矩阵元素表示变迁所需的最短时延。

T(O_i, g_k)=D()+E_ft()+E_ft(g_k)

T(g_k, O_i)=D(g_k)+E_ft()

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

M=M₀+C·U                (3)

             (4)

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

证明：根据定义5，状态关联矩阵元素的值W(O_i, g_k)-W(g_k, O_i)描述的是门变迁g_k发生时输入输出的最终效果，g₁发生后，M₁=M₀+C，而U(g_k)表示门变迁g_k在变迁序列σ中的触发次数，很明显，经过变迁序列σ后M=M₀+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模型，下面使用本文提出的方法对其进行分析。

系统初始状态M₀=(1,0,0,0,0,0,0,0,0)^T。

行向量V={O₁,O₂,O₃,O₄,O₅,O₆,O₇,O₈,O₉}。

列向量U={g₁,g₂,g₃,g₄,g₅,g₆,g₇,g₈}^T。

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

表1  门变迁及其含义

Table 1  Transitions and their meaning

状态关联矩阵为：

时延关联矩阵为：

由图2知：由申请索赔到索赔成功并记录赔付有2种变迁序列，σ₁=g₁g₄g₅，即U₁=(1,0,0,1,1,0,0,0)^T以及σ₂=g₁g₄g₆，即U₂=(1,0,0,1,0,1,0,0)^T。

初始时延，根据式(4)，时延

根据式(2)，delay()=1+8+9+4+3=25；时延(1,8,0,4,9,0,3,0,0)^T；delay()= 1+8+4+9+3=25。

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

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

图2  基于OOTCPN's的保险索赔过程建模

Fig.2  Process modeling of insurance claim based on OOTCPN’s

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.

(编辑 陈灿华)

收稿日期：2011-06-06；修回日期：2011-08-10

基金项目：湖南省科技计划项目资助(2011GK3113)

通信作者：黄敏(1968-)，女，重庆人，副教授，硕士研究生导师，从事Petri网理论及其应用研究；电话：13548718081；E-mail: huangmin_09@yahoo.com.cn