基于Petri网的网上购书流程建模

郝颖,封雪，于世东

（营口理工学院电气工程系，营口115000）

基于Petri网的网上购书流程建模

郝颖,封雪，于世东

（营口理工学院电气工程系，营口115000）

Petri网是一种系统模拟和分析的有力工具，工作流网是基于Petri网对业务流程的形式化描述。首先介绍Petri网和工作流网的基本概念，接着介绍基于Petri网的工作流建模技术，然后给出网上购书流程的Petri网模型，最后使用工作流网分析工具WoPeD对建立的Petri网工作流模型的正确性进行分析。

0 引言

工作流通常与业务流程重组相关，它涉及到工作流的建模、评估、合理性分析、执行等相关的研究[1]。工作流管理联盟给出的工作流定义是：工作流是一类能够完全或者部分自动执行的经营过程，它根据一系列过程规则，文档、信息或任务能够在不同的执行者之间进行传递与执行[2]。

工作流建模就是将业务流程及各流程之间的业务规则抽象出来，并用一种形式化的、计算机可处理的方式来表示，这种形式化的结果就称为工作流模型。工作流模型必须包含执行工作流过程时所需要的全部信息，包括工作流的所有活动间执行的依赖关系，顺序、循环、判断条件，以及资源约束条件[3]。

目前，对工作流模型描述和分析方法的研究正日益受到人们的重视。工作流建模方法主要有以下三种类型（1）基于通信的方法；（2）基于活动的方法；（3）基于Petri网的方法[4]。其中,基于Petri网的方法对工作流建模被广泛接受，主要有以下原因[5-9]：（1）Petri网具有很强的表达能力，能够描述工作流建模过程中涉及到的各种语义。Petri网能够以图形化的方式描述工作流过程。（2）Petri网建模方法是基于状态的，它能描述一个任务是处于何种状态（enabling、execution）。（3）高级Petri网可以进行层次化的建模，有利于对各层次模型独立的进行正确性验证。（4）Petri网具有坚实的数学基础，可以有效地分析模型的各种特性：有界性、活性、安全性、不变量等。

本文首先介绍了Petri网和工作流网的基本概念，描述了基于Petri网建立工作流模型的方法，并使用Petri网建立网上购书流程的模型。最后，使用工作流网的建模、模拟和分析工具WoPeD（Workflow Petri Net Designer）对网上购书业务流程的Petri网模型进行正确性分析。

1 Petri网的基本概念

1962年德国学者C.A.Petri在他的博士论文《用自动机通信》中首次使用网状结构模拟通信系统，系统模型就是Petri网的雏形。经过多年的发展，Petri网已经成为计算机异步成分之间进行通信的理论基础，是描述具有分布、并发、异步特征系统的有效工具[10]。

Petri网定义为四元组PN=（P，T，F，M0），其中：P是库所的有限集合，T是变迁的有限集合，F是有向弧的集合，M0是初始标识。其充分必要条件是（1）P∩T=Φ；（2）P∪T≠Φ；（3）F⊆（P×T）∪（T×P）[5]。

Petri网=（P,T,F,M0）称作工作流网，当且仅当（1）PN有一个起始库所i∈P，使得i=Φ；（2）PN有一个终止库所o∈P，使得o·=Φ；（3）如果给PN增加一个变迁t*，该变迁连接起始库所i和终止库所o，其中o作为变迁t*的输入，i作为变迁t*的输出（即t*={o}并且t*={i}），则Petri网结构是强连通的。工作流网描述的是一个过程实例的生命周期，必须具有一个起始库所i和一个终止库所o。进入起始库所i的标记代表着一个过程实例的开始，而进入终止库所o的标记则意味着一个过程实例的结束[11-13]。

2 基于Petri网的工作流建模方法

工作流是对业务过程的形式化描述，使用Petri对工作流建模比较直观。工作流过程是任务的偏序集合，工作流中的任务用Petri网中的变迁表示，优先关系用库所表示，工作流实例用token表示，token的流动表示工作流的执行。

工作流管理联盟定义了四种基本的工作流路由结构[5]：

（1）顺序路由。表示两个或多个任务之间按先后顺序执行。如图1所示，先执行t1，后执行t2。

（2）并行路由。表示并行的两个或多个任务之间可以按任意顺序执行。如图2所示，t1执行后，按任意顺序执行t2，t3或同时执行t2，t3。

（3）选择路由。表示在流程的某一点，依执行结果判断选择哪一条路径继续执行。如图3所示，t1执行后，执行t2或t3其中之一。

（4）循环路由。表示某一个或多个任务可能需要重复执行多次。如图4所示，t1,t2可能会重复执行多次。

图1 顺序路由

图2 并行路由

图3 选择路由

图4 循环路由

3 网上购书流程的Petri网模型

网上购书流程描述如下：用户登录购书网站，填写购书信息，查询该书的剩余数量。系统检查库存中是否有此书，用户根据系统的提示是否有书信息来选择提交订单或取消购书操作。用户提交订单后，系统会提示用户确认订单及地址等信息，如果用户核查无误则进入付款操作，系统收到返回支付信息，用户购书成功。

图5是网上购书流程的Petri网模型，其中变迁的含义如下：t1：用户登录；t2：系统验证用户的身份是否正确；t3：通过验证，用户填写购书信息；t4：未通过验证，用户选择重新登录或结束购书操作；t5：请求查询书的剩余数量；t6：核查是否有此书；t7：调用此书订单；t8：库存中无此书操作结束；t9：用户填写订单表；t10：系统核对订单表信息；t11：信息正确，用户付费；t12：信息错误，重填订单；t13是否付费；t14：已付费，购书成功；t15：未付费，结束操作或重新要求用户付费。

网上购书流程的Petri网模型采用了顺序路由，选择路由，循环路由三种结构实现了对购书流程中一些异常情况的处理方法。：（1）用户身份验证失败，系统可以结束操作或提示用户重新登录；（2）当系统查不到用户所要购买的书时，系统结束操作。（3）用户填写订单出错时，系统结束操作或要求用户重新修改订单。（4）用户未付款时，系统结束操作或要求用户付款。在上述各种情况中也可以把变迁加入时间触发机制。在一定的时间内，用户未操作，则系统结束操作。

4 网上购书模型的正确性验证

一个工作流网是正确的当且仅当[14]：（1）对起始库所i可达的任意状态M，都存在一个触发序列可以从状态M到终止库所o。（2）库所o是唯一的终止库所，当一个工作流实例运行结束时，只有库所o中有且仅有一个token，其它库所均为空。（3）Petri网中没有死变迁，也就是说任意一个变迁都可被执行，Petri网是活的。正确性表明i到o的所有路径中，每个变迁都触发过，每个库所都经历过，正确性描述的是工作流网的动态特性。

图5 网上购书流程的Petri网模型

WoPeD[15]是基于Java的开源软件，由德国卡尔斯鲁厄大学开发，WoPeD的生成文件是PNML格式的，是一种可以对工作流网描述的过程进行建模，模拟和分析的简单易用的软件。WoPeD可以执行在任何支持Java的系统上。WoPeD[16]提供Petri网和工作流网的图形化界面，包括交互模拟。WoPeD支持模型验证和属性的可视化，并且内置算法可以检测模型正确性，过程度量和定量模拟等。

本文使用WoPeD，采用可达图的方法对图5的网上购书流程的Petri网模型进行正确性进行验证。WoPeD用广度优先算法构造可达图，如图6所示。

从图6中可以观察到状态（0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1）是唯一没有输出的状态，即该状态只有输入弧，没有输出弧，该状态为结束状态。图5的Petri网模型中库所p16是结束库所，由结束状态（0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1）可知除了库所p16中有token之外，其他库所中都没有token，符合工作流网的正确性的定义。

5 结语

Petri网自提出以来，已经发展成为一个庞大的研究领域。利用Petri网建立工作流模型，不仅能够以图形化的方式直观地表现出流程，并且便于用户使用流程建立工作，本文基于Petri网建立了网上购书流程的模型，并且利用Petri网的可达性分析技术，使用WoPeD对网上购书流程模型的正确性进行分析和验证。

图6 网上购书流程的可达图

[1]Workflow Management Coalition.The Workflow Reference Model.Technique Report[R].WFMC-TC00-1003.Hampshire:Workflow Management Coalition,1995.

[2]范玉顺.工作流管理技术基础[M].北京:清华大学出版社，2001．

[3]陈广智，潘嵘，李磊.工作流建模技术综述及其研究趋势[J].计算机科学,2014,41（6A）:11-17.

[4]孙志东.基于Petri网的层次迁移工作流系统模型研究[D].山东大学，2006.

[5]Van Der Aalst W.M.P.The Application of Petri nets to Workflow Management[J].The Journal of Circuits Systems and Computers,1998,8（1）：21-66.

[6]周福明，吴斌等.基于Petri网的工作流建模与正确性分析[J].计算机科学，2005，2.

[7]谷建鑫，仇建伟.基于Petri网的工作流模型[J].计算机工程与设计，2005，2.

[8]陈慧灵等.基于Petri网的工作流过程建模[J].计算机工程与科学，2008，5.

[9]张信一，黎燕.基于Petri网的工作流建模[J].微机发展，2003，6.

[10]袁崇义.Petri网原理[M].北京：电子工业出版社，1997.

[11]杨雯，刘厚泉.基于Petri网的工作流模型的研究[J].计算机工程与设计，2007，9.

[12]W.M.P.van der Aalst.Verification of Workflow Nets.In P.Azéma and G.Balbo,Editors,Application and Theory of Petri Nets 1997,Volume 1248 of Lecture Notes in Computer Science,pages 407-426.Springer-Verlag,Berlin,1997.

[13]胡坚，宋斌恒.一个基于AOP技术的工作流异常处理策略[J].微计算机信息，2005.

[14]何路路，方欢.基于Petri网的保险工作流系统建模及验证[J].牡丹江师范学院学报,2016,1.

[15]The WoPeD project homepage.http:///www.woped.org.

[16]Thomas Freytag,Martin Sanger.WoPeD-An Educational Tool for Workflow Nets.In:Proceedings of the BPM Demo Sessions,Eindhoven,September 2014：31-35.

A Workflow Model for Purchase Books Online Based on Petri Net

HAO Ying，FENG Xue，YU Shi-dong

（Yingkou Institute of Technology,Yingkou 115000）

Petri net is a powerful tool for system simulation and analysis.Workflow is a formal description of the business process based on Petri net.Firstly introduces the basic concept of Petri net and workflow net,then introduces the workflow model technique based on Petri net,takes the Petri net model of online purchase books as an example,uses the workflow Petri net Designer Tool WoPeD to analyze the correctness of the model.

1007-1423（2017）27-0073-04

10.3969/j.issn.1007-1423.2017.27.016

Petri网；工作流；网上购书

郝颖（1984-），女，辽宁鞍山人，硕士，讲师，研究方向为形式化验证、软件工程

封雪（1984-），女，辽宁营口人，硕士，讲师，研究方向为计算几何、机器人路径规划

于世东（1979-），男，辽宁东港人，硕士，副教授，研究方向为数据可视化、数据分析、.NET开发

2017-07-18

2017-09-20

Petri net;Workflow;Online Purchase Books