基于随机Petri网工作流模型的时间性能分析方法

沈美 于翔

摘 要：工作流Petri网的时间性能分析方法有多种，本文采用加入时间因素的扩展马尔可夫链，建立与随机Petri网同构的有穷马尔可夫链，再根据此过程的稳定概率求解系统的性能参数。

关键词：工作流；Petri网；时间性能分析；马尔可夫链

工作流模型的时间性能分析是工作流研究的重要内容之一，也是分析资源利用率、成本等指标的基础。目前，大多数实用的工作流应用系统，在业务流程的性能分析上，几乎未给出适合各种工作流模型的有效方法。工作流除了正确性之外，还要关心它的性能分析，而这一点又往往被人们所忽视。工作流性能分析主要反映工作流定量方面的特性，比如过程的完成时间，资源利用率等等。定量分析模型之前须确认模型的正确性，即保证模型在业务流程和逻辑结构上没有错误且是合理的。传统的基于马尔可夫链的性能分析方法[1]具有指数时间复杂性，影响了其实用性。对给定的工作流，可以生成一个马尔可夫链，利用它可以分析工作流的某些方面，而且马尔可夫链的分析[2]非常耗时（即使是对本来不难处理的问题）。但是，根据实际应用可以通过成本或时间的引入来扩展马尔可夫链，就能获取一系列性能指标。

本文讨论加入时间因素的扩展马尔可夫链，根据被评价的随机Petri网工作流模型构造出连续时间的马尔可夫链，即随机模型[3]，对其进行时间性能分析。

1 基本概念

1.1 工作流网

对工作流的控制流建模的Petri网被称作工作流网（WF-net），是Aalst在Petri网的基础上提出的概念。

1.2 随机Petri网

随机Petri网（SPN）：一个连续时间SPN是一个六元组SPN=（P，D，F，W，M0，λ），在Petri网基础上，λ={λ1，λ2，…，λm}，是变迁平均实施速率集合。

在连续时间SPN中，一个变迁t从变成可实施的时刻到它实施时刻之间的延时被看成一个连续随机变量，服从以λ为参数的指数分布。λ是变迁t的平均实施速率，表示在可实施的情况下单位时间内平均实施的次数，单位是次数/单位时间。平均实施速率的倒数1/λ称为变迁ti的平均实施延时或平均服务时间。

1.3 工作流-随机Petri网的定义

工作流-随机Petri网（WF-SPN）是在随机Petri网（SPN）和工作流网（WF-net）的基础上提出的，目的是将随机触发时间引入工作流网，使模型具有分析时间性能的能力。

WF-SPN是SPN的真子集，可递归定义为：由一个基本结构组成的SPN是WF-SPN。WF-SPN满足如下性质：（1）有一个初始库所i∈P，·i=φ；（2）有一个终止库所0∈P，o·=φ；（3）每个节点x∈P∪T都在从I到o的一条路径上。

2 工作流-随机Petri 网时间性能分析

基本Petri网模型不能用于系统的性能评价，必须对其扩展。可以在每个变迁的可实施和实施之间联系一个随机的时间延迟。应用随机Petri网对系统评价时分三步：1）构造系统对应的随机Petri网模型。2）构造出该Petri网所同构的马尔可夫过程。3）基于马尔可夫过程的稳定概率求解系统的性能参数。

工作流-随机Petri网和一般工作流网的区别：在变迁中引入平均实施速率λi，每个λi值是从对所模拟系统的实际测量中获得或根据某种要求的预测值，它们具有实际意义。

定理1[4]任何具有有穷个库所、有穷个变迁的连续时间的随机Petri网同构于一个一维连续时间的马尔可夫链。K-有界的随机Petri网同构于有穷马尔可夫链。

假定一个工作流随机网同构于一个马尔可夫链，那么工作流随机网的每一个标识可以达到一个动态平衡状态，即每一个标记有一个确定的值，称为标记Mi的稳定概率，记为P（Mi）， （i=1，2，...，k）。根据马尔可夫链平稳分布的有关理论，得出如下的公式[5]：

其中Q为变迁速率矩阵，其非对角线上的元素qi，j（i≠j）是这样确定的：如果在马尔可夫链中从Mi到Mj有一条有向弧连接时，qi，j为弧上的速率值；如果没有弧，则qi，j（i=j）是从Mi发出的各条弧速率之和的相反数。将工作流随机网同构为马尔可夫链之后，利用公式（1），可以解出P（Mi）的值。由此可以得出工作流模型的一些系统特性和运行特性。

生成一个工作流网的可达图是实现从工作流网到马尔可夫链转换的关键，但要确保工作流网模型是合理的。工作流网是合理的，那么工作流随机网必定有界，该网就可以同构于一个有限的马尔可夫链，保证了计算的可行性。具体的分析步骤如下：

（1）从工作流随机网的定义可以看出，它是工作流网的一个特例。由于任何一个合理的工作流网必将结束于标识（0，0，...，0，1），也就是在马尔可夫链中该结束标识的稳定概率为1，其他标识的稳定概率均为0。这样就不能用来分析其性能，原因是工作流网仅执行一次。因此要将一个工作流网执行多次，然后得出每个标识的稳定概率。现有的工作流网模型不能反映这一特性，在文献[6]中提出在库所o和库所i间增加一个瞬间变迁t*，并连接库所o和变迁t*，连接变迁t*和库所i，由于变迁t*是不需要时间的，实际上标识（0，0，...，0，1）是不存在的。因此，可以考虑将库所o映射为库所i，也就是将库所o和库所i合并，这样在不额外增加变迁的基础上，也能反映工作流网可任意次执行的特性，得出的标识稳定概率可用于分析工作流的性能。因此这一步要完成的任务就是将库所i和库所o合并。

（2）接着要生成可达图。首先可以先生成一个可达树，再将可达树转换成一个可达图。

（3）计算Q矩阵的值。在马尔可夫链中，当从状态Mi到状态Mj有一条弧相连时，则弧上标注的值即是qi，j的值；如果从状态Mi到状态Mj没有弧相连时，则qi，j=0。对角线上的元素qi，j（i=j）是从Mi发出的各条弧速率之和的相反数。

根据公式1得到稳定概率P（Mi）的值；在求得稳定概率的基础上，可进一步分析系统的以下性能指标，如变迁的标记流速，子系统的平均延时时间等，具体可参考文献[5]。

①在每个状态M中的驻留时间：在每个可达标识M∈[M0>的驻留时间是以-γi，i为参数的一个指数分布的随机变量，平均为： 。

②标记概率密度函数：在稳定状态下，每个库所中所包含标记数量的概率。对 ， ，令P{M（S）=i}表示库所s中包含i个标记的概率，则可从标识的稳定概率求得库所s的标记概率密度函数： ，其中Mj∈[M0>且Mj（s）=i。

3 实例分析

本文以ASP平台进销存系统为例对其过程模型进行时间性能分析。此系统的简化过程模型见图1所示，库所集合P=（p1，p2，…，p6），变迁集合T=（t1，t2，…，t5）。其中变迁标识和含义：标识t1代表客户下订单，即当收到客户的订货信息就触发变迁t1，实施创建销售订单的任务；t2表示检查库存，若当前库存能满足订单需求，则实施p2分支，否则实施p3分支；t3代表采购；t4表示出销售单；t5代表出货。标识i是库所开始，o表示库所结束。

因为要采用工作流随机Petri网来分析工作流，首先要确保模型是合理的，通过分析验证方法[7]，可以得出结论，图1模型是正确的、合理的。通过定理1，该网同构于一个有限的马尔可夫链，保证了计算的可行性。如前文所述，对工作流随机Petri网的分析步骤如下：

⑴在库所o和库所i之间增加一个瞬间变迁t*，将库所o和库所i合并，形成图2所示的改进模型。反映工作流网可任意次执行的特性，得出的标识稳定概率可用于分析工作流的性能。

⑵生成可达图，得出图2所示的工作流网的可达状态标识，可用表1来表示。将图2所示的工作流Petri网转换成与其等价的马尔可夫链，见下图3。

⑶Q为变迁速率矩阵，根据前文计算规则，得出图3马尔可夫链对应Q矩阵的值见表2

一旦给出λ的具体值，就可以根据公式（1）得到稳定概率P（Mi）的值。根据对实际问题的预测，该网中的变迁引入平均实施速率λi。给定随机变量集合λ={λ1，λ2，λ3，λ4，λ5，λ*}={2，5，20，3，15，0}。得到P（Mi）={0.2498，0.2145，0.2237，0.187，0.1250，0}。在求得稳定概率P（Mi）的基础上，就可以得出上文中提到的工作流网的其他性能指标。

4 结语

本文采用加入时间因素的扩展马尔可夫链对被评价的随机Petri网工作流模型，首先构造出相应的连续时间的马尔可夫链，再根据此过程的稳定概率对其进行时间性能分析。通过实例分析得出：此方法是有效、可行的，对同类问题的分析和评价具有一定的参考价值。

[参考文献]

[1]王建民，闻立杰，等，译.工作流管理—模型、方法和系统[M].北京：清华大学出版社.2004.

[2]曲扬.基于Petri网的工作流建模和分析方法研究.清华大学学位论文.清华大学，2004.

[3]卫刚.基于Petri网的工作流建模工具的研究与实现.南京航空航天大学学位论文.南京航空航天大学.2005.

[4]林闯.随机Petri网和系统性能评价[M].北京：清华大学出版社.2000.

[5]林闯.计算机网络和计算机系统的性能评价[M].清华大学出版社. 2002，1：3～202.

[6]Lin C，Marinescu D C，Reachability trees for high level Petri nets with marking variables，Computer Sciences Department， Purdue University，CSD-TR-857，February 1989.

[7]沈美.基于高级Petri网的工作流建模研究与仿真分析.计算机工程与应用.2006，42（32）：200～203.