工作流Petri网建模在电子合同系统中的应用

摘 要：随着互联网的发展，电子商务模式已很大程度取代传统的交易方式，电子合同的使用范围也越来越广泛。本文基于电子签章技术的电子合同系统的设计与实现，通过使用Petri网对电子合同在线签订流程进行并发模型的建模，为系统实现电子合同在线签订时保证至少有两个单位可以进行合同会签，同时保证信息传输的保密、数据交换的完整性、发送信息的不可否认性、交易者身份的确定性，从而保证系统使用的安全性提供了可靠的依据。

关键词：Petri网；工作流；电子合同；电子商务

中图分类号：TP311.5

随着互联网的发展，网络已经成为我们日常生活的一部分，在不经意间已经改变了很多人的工作、生活。为此，国家经过广泛的征求意见和修改，在2005年4月1日已颁布实施了《中华人民共和国电子签名法》，其中第十四条明确指出“可靠的电子签名与手写签名或者盖章具有同等的法律效力”。电子商务蓬勃发展，电子签章已然成为是我国印章史上的一场革命。电子签章系统将数字认证技术应用于印章管理中，强化对电子签章的制作和应用各个环节的管理，确保电子签章持有者身份真实、可靠、安全。现有的电子合同平台如[1]中所提到的，并未使用Petri网对工作流建模来保证电子合同平台系统代码本身的安全性以及可靠性，本文提出使用Petri网对工作流建模，从而保证系统流程的安全、可靠。

1 关键技术

1.1 工作流技术

1.1.1 工作流的基本概念

根据工作流管理联盟（WfMC）的定义，工作流的定义是：一类能够完全或部分自动执行的业务过程，在此过程中，文档（Paper）、信息（Information）或其它任务按照事先预定的规则进行流转。业务、工作、办事等人员和应用系统之间相互的协调工作，从而来实现业务流程中所要达到的最终目的。换句话说，工作流就是一些能够自动运行的业务活动，它们是相互关联的、相互衔接的。

1.1.2 基于网的工作流建模方法

这类方法适用于流程的可视化建模。网中的结点用来表示流程中的活动，网中的边用来表示控制流。使用这类方法的主要问题在于对模型的描述是否有形式化的语义。大多数工作流产品的可视化建模方法都缺乏形式化语义。具有形式化语义的基于网的方法可以转换成其它建模方法，如基于规则的、时序逻辑的和脚本语言的方法等。在基于网的工作流建模方法中，使用最多的是Petri网和状态图（state charts）， Petri网被广泛用于建立工作流模型，Ellis和Nutt在Petit网的基础上提出了工作流CN模型，它实际上是高级Petri网的一个扩展，在其描述中用库所表示活动，用变迁表示活动间状态的转移。Vander Aalst则在Petri网的基础上定义了WF-Net即工作流网。在工作流网中，变迁被用来表示活动而库所则表示活动的可实施条件。Vander Aalst七还把工作流管理联盟在规范中提出的几种基本的工作流原语映射成相应的Petri模型，由此建立了工作流网的基本组件与触发机制。

因此Petri网作为一种从过程的角度出发描述和分析复杂系统的模型工具，被广泛地应用工作流的系统建模中，用Petri网工作流建模方法研究，始终是一个非常活跃的领域。

1.2 Petri网综述

Petri网理论[2][3]首先是在1961年在Carl Adam Petri的博士论文中提出，他在他的博士论文《用自动机通信》中首先提出将用一种网状结构来模拟了通信系统。

1.2.1 Petri网的引入原因

在分析工作流系统时，我们需要应用数学的分析方法[4]。而Petri网理论正好为我们解决了这些问题。在Petri网理论体系中主要有基于状态方程和代数的分析技术和基于可达树（图）的分析技术的两种建模方法。

1.2.2 Petri网的数学描述

Petri网是一种数学和图形的描述与分析工具，适合于描述并发、异步、分布、并行、不确定性和随机性的信息处理系统，进行系统模型的构造、分析及评价。下面简单介绍本文将使用的与Petri 网有关的基本概念、定义、术语和性质[5]：

定义1（Petri网）

（1）基本Petri网是一个三元组N=（P，T，F），其中，P和T分别为有限非空的库所和变迁集合，P∩T= ；F P×T∪T×P是一个有向弧的集合。

（2）令Σ= （P，T，F）是一个网，对所有x∈P∪T： x ={y∈P∪T|〈y，x〉∈F}是x的前集；x = {y∈P∪T|〈x，y〉∈F}是x的后集。结点集x的前集（或后集）定义为：

。

网中任一库所结点在任何时刻都可能含有0个或多个托肯，称为库所的标记。托肯在网中的分布反映了网的状态，称为网的标识，记为M。标识M实际上反映了网中库所结点向一个整数集合的映射。在M下库所p的标记记为M（p），表示p中含托肯的数量。事实上，M是一个多重集。给定了初始标识M0的网Σ称为Petri网，记为PN =（Σ，M0）。

1.2.3 Petri网的性质

（1）可达性。可达性是任何系统动态特性的基本性质。按照Petri网的转移方法，有效转移的启动将改变标记的分配情况（产生新的状态）。如果存在一个从M0状态到Mn状态的运行序列，那么我们就认为状态M0是可以到达状态Mn的，启动运行顺序表示为：=M0t1M1t2M2…tnMn或简化表示为=t1t2…tn。可用M0 [>Mn表示三者之间的关系，即从M0标识表示经过启动序列到达标识Mn。在网（N，M0）中所有从标识M0可达的标识集合，可表示为S（N，M0）或简化为S（M0），从M0触发的所有可能启动运行顺序的集合可表示为F（N，M0）或简化为F（M0）。这样，Petri网的可达性问题就转化为对于网（N，M0）和给定状态Mn，寻找是否存在Mn∈S（M0）。

（2）有界性。对Petri网（N，M0）若存在一个整数，我们把M0的到任一个可达状态的数设为k，若k申购始终不超过K，即对于每个状态标识M∈S（M0）和每个状态，M（i）≤K均成立，则称Petri网（N，M0）为是以K为界或简称Petri网（N，M0）有界。若Petri网（N，M0）为1有界，即每个系统的状态只有一种时，则称此Petri网是安全的或则说是稳定的。这种网的每一个位置要么只存在一个标记状态，要么没有一个标记状态。

（3）活性。一个Petri网（N，M0）被称为活的，当且仅当从M0可达的任一标识状态出发，都可以通过按照某一种变迁执行的顺序序列而最终启动其它任何一个变迁。这就说明，无论网的开始状态如何，一个活的Petri网都可以保证无死锁发生。

（4）可逆性。一个Petri网（N，M0）被称为可逆的，仅当对S（M0）中的每个状态标识Mi，M0都是可以从Mi达到的。也就是说，一个可逆网是这样一个网，它可以使得状态返回到初始标识或初始状态。在很多应用中，比如在合同流转系统中，当我们要求哪一步合同需要重新审核时，我们只要求合同流转系统回到某个特定状态就可以了，而不必要返回到初始状态。那么我们称这个特定状态当前所返回的状态就为主要状态M′。即对于S（M0）的每个状态标识Mi，主要状态M′都是可达的。

1.3 基于Petri网的工作流建模技术

应用Petri网对工作流进行建模，利用线性结构来研究工作流的流转方式和运行效率。主要方法是先将语义上的工作流进行转换成简单的活动图G=（V，E），再通过活动图进行转换成相应的Petri网模型。采用算法如图1所示[6]，对活动图进行转化，首先对该活动图G=（V，E）进行深度优先遍，将每个节点，分成顺序，与分支，与合并，或分支，或合并五类，然后按照不同的策略进行转化。对于结v∈V，分别定义 v和v 为v的前置结点集和后置结点集，图1算法将合同在线签订流程活动图G转化为对应的Petri网，算法的时间复杂度为O（V）。

Input：活动图G=（V，E），其中V为节点的集合，E为有向弧的集合，其中|V|=n。

Output：Petri网N=（P，T，F）

Initialize：P= ，T= ，F=

begin

广度优先方式遍历G，并且从1开始编号。

将图G复制到G’，把图G’中的结点vi转化为ti，那么就形成了工作流网的变迁集合T。

for（i=0 to n） //循环添加

{

if（ti∈T∧（.ti= ）） //添加开始库所

{

P=P∪{pk}；

F=F∪{pk，ti}；

for each （tj∈ti.）

{

P=P∪{pj}，F=F∪{（ti，pj），（pj，tj）}

}

}

if（ti∈T∧（ti.= ）） //添加结束库所

{

for each （tj∈.ti）

{

if （Pj tj）

{

P=P∪{pj}，F=F∪{（ti，pj）}

}

F=F∪{（pj，ti）}

}

if （tj T）{T=T∪{tj}}

F=F∪{（ti，pk）}

}

if （ti∈T∧|.ti|=1∧|ti.|=1） //处理顺序结构

{

if （tj∈.ti∧pk ）

{

P=P∪{pk}，F=F∪{（tj，pk） }

}

F=F∪{（ pk ，ti） }

if（！（vj∈vi. ∧pk=∈.tj））

{

P=P∪{pk}，F=F∪{（ pk ，tj） }

}

F=F∪{（tj，pk） }

}

if （.vi|=1∧（|vi.|>1∧（vi==1）） //处理与分支结点，“1”代表与分支//

{

if （vj∈.vi∧pk∈tj.） { F=F∪{（ pk ，ti） }

for each （vj∈vi）{ P=P∪{pj}，F=F∪{（ ti ，pj） }}

}

if （.vi|=1∧（|vi.|>1∧（vi==2）） //处理或分支结点，“2”代表或分支//

{

if （vj∈.vi∧pk∈tj.） { F=F∪{（ pk ，ti） }

}

if （.vi|=1∧（|vi.|=1∧（vi==3）） //处理与合并结点，“3”代表与合并//

{

for each （vj∈vi）{ if（pj∈tj.）{ F=F∪{（pk，ti）}}

P=P∪{pk}，F=F∪{（ti，pk）}

}

if （.vi|=1∧（|vi.|=1∧（vi==4）） //处理或合并结点，“4”代表或合并//

{

if （vj∈.vi∧pk∈tj.） { F=F∪{（pk ，ti）}

P=P∪{pk}，F=F∪{（ti，pk）}

}

}

}

end

图1 活动图到Petri网的转化算法

2 电子合同系统应用流程

平台采用J2EE架构进行开发，实现登录平台用户的合同洽谈、合同签订、合同查询等功能，应用流程如图2。

图2 电子合同系统流程图

基于电子签章技术的电子合同平台实现了网上可信电子合同的洽谈、签订等功能，为有协议签订需求的用户提供安全合作的办公平台，确保用户合法权益，对用户登录系统后的操作进行处处留证的监控，为有可能发生的合同纠纷等意外事故提供权威的责任认定功能。

3 基于Petri网电子合同系统建模

从整体上讲，电子合同系统可以分为电子合同在线签订和在线合同洽谈两个部分。这两个流程是整个电子合同系统的核心。对其进行研究具有一定的现实意义，下面对电子合同在线签订流程进行Petri网建模以及模型分析。

3.1 电子合同在线签订流程的Petri网模型

电子合同在线签订的第一步骤，一般是由秘书或办公室主任进行拟稿。这一步是这一流程最主要的部分。

电子合同在线签订流程主要包括：合同拟稿，合同核对，合同相关领导会签、不合格合同回退，合同催办，合格合同归档。

（1）合同拟稿：即审批文档的起草过程。在其中要确定合同名称，拟稿的部门，拟稿人员，主送部门或人员，合同的种类，合同的密级，合同打印限制，以及合同的内容，合同所带的附件等。

（2）合同核对：将拟写好的合同进行核对以后送给领导审核。核对内容包括文字的准确性，合同的合理性，以及其他一些合同的必要属性。

（3）合同领导会签：合同会签是指在同一个步骤上允许一个合同可以由一个或者一个以上的公司领导同时进行签章，并进行在线签章验证。

（4）不合格合同回退：在合同核对和会签的过程中，若合同有错误，就要立即进行合同的回退，以重新拟稿。

（5）合同催办：在合同在某一步骤停留时间超过某一时间时应该生成催办信息，通过邮件系统进行提醒。

（6）合格合同归档：合同审批通过以后及时进行合同归档，以便于可以进行合同的在线洽谈和在线签订。相应的合同在线签订流程如图3所示：

图3 电子合同在线签订流程的活动图

将以上活动图通过图1的算法进行建模，得到图4的Petri网顺序模型：

图4 电子合同在线签订流程的Petri网顺序模型

图4的各个变迁以及状态含义如下：

P0：合同未拟稿状态。

T0：主办人员或者单位合同拟稿。

P1：合同拟稿完成，等待审批。

T1：主送单位进行合同核稿。

P2：合同核稿无误，准备进入下一步。

T2：各个单位进行合同会签并进行验证。

P3：合同会签完成状态。

T3：进行合格合同归档。

T4：合同催办，提醒优先处理该合同，以提高流转效率。

P4：合格合同归档；

T5：不合格合同回退到第一步重新开始拟稿。

3.2电子合同在线签订流程的并发Petri网模型

并发模型主要是指合同在线签订过程中，一个合同同时有两个或两个以上的单位代表在同一步骤上进行会签，如此一来，在同一步骤上的会签人员可以同时打开该公文，相对于只能等待前一个单位代表操作完成才能开始审阅、签订的过程来说，大大增加了工作的效率。会签的同时不受到任何约束。对于开发人员来说，在流程的控制上也可以更方便，更简单。一个最常见的并发模型如图5所示，其中虚线框里的是会签时的一种典型的并发模型。

图5 电子合同在线签订流程的Petri网并发模型

图5的各变迁以及状态含意如下。

P0：合同未拟稿状态。

T0：主办人员或者单位合同拟稿。

P1：合同拟稿完成，等待审批。

T1：主送单位进行合同核稿。

P2：合同核稿无误，准备进入下一步。

T2：各个单位进行合同会签并进行验证。

P3：合同会签完成状态。

T3：进行合格合同归档。

T4：合同催办，提醒优先处理该合同，以提高流转效率。

P4：合格合同归档；

T5：不合格合同回退到第一步重新开始拟稿。

虚线框里的含义：

T21：合同进入会签流程。

P21：合同处于会签状态。

T22：会签人员1签订。

T23：会签人员2签订。

P31：会签完成，进入合同自动检验状态。

T24：检验合同是否合格。

3.3电子合同在线签订流程的Petri网模型分析

Petri网的分析方法主要有可达树分析、可达图分析和矩阵方程来分析，这里我们主要采用可达树和可达图来分析在线签订流程模型。根据可达树生成算法，我们可以得到图6 电子合同在线签订流程的Petri网顺序模型相应的可达树模型。

图6 电子合同在线签订流程的可达树模型

我们可以从图6可以得到电子合同在线签订流程Petri网的特性：

（1）该电子合同在线签订流程Petri网是有界的，因为可达树中没有出现 。（2）该电子合同在线签订流程Petri网是安全的，因为只有“0”，“1”出现在可达树标识中。（3）因图6中所有该发生的变迁都出现在该可达树中，说明了该电子合同在线签订流程Petri网是“活的”，也就是说没有多余变迁。

4 结束语

随着电子合同法律地位的确定、数字签名法律效力的认可，在电子商务活动中已经出现了大量的电子合同。本平台设计集成了PKI/CA技术、电子签章技术和数字水印技术等，采用J2EE架构建立起一套具有适用性、安全性的电子合同平台，有效的弥补书面合同的缺陷，减少人力、物力和财力方面的支出，提高工作效率、降低成本，其经济和社会效益显著。在编写代码之前，对系统流程进行Petri网并发模型建模，保证了系统可以支持两个或者以上的合同涉及方进行同时的合同会签。但同时，因为普通Petri网的一些缺陷，比如会产生空间爆炸等，运用普通Petri网对系统流程建模并不是最好的建模方法，运用高级Petri网进行建模将会成为下一步研究方向与目标。

参考文献：

[1]罗清彩.基于电子签章技术的电子合同平台设计与实现[D].华东师范大学硕士论文，2009（11）.

[2]Sylvie Troncale，Jean-PaulComet，GillesBernot.Modeling and verification with timed hybrid Petri nets.Pattern Recognition，2009（42）：562-566.

[3]H.Ehrig，K.Hoffmann， J.Padberg. Transformations of Petri nets[J].Electronic Notes in Theoretical Computer Science，2006：151-172.

[4]C.Mohan.Tutorial.State of the Art in Workflow Management Systems Research and Applications[DASFAA'97].Australia.1997：544-553.

[5]袁崇义.Petri网原理与应用[M].北京：电子工业出版社，2005.

[6]姜浩.基于Petri网的工作流模型分析与性能评价方法的研究[D].东南大学博士论文，2005.

[7]W.M.P.van der Aalst.Verification of Workflow Nets[C]. Springer-Verlag， Berlin，LNCS 1238.1997：407-426.

[8]W.M.P.van der Aalst. Workflow verification： Finding control-fowl errors using Petri net based techniques[C].Springer-Verlag， Berlin， LNCS 1806，2000：161-183.

[9]E.Badouel，J.Oliver. Reconfigurable nets a class of high level Petri Net Suppotring dynamic Changes within Workflow Systems[EB]. Publication Internet Number 1163，IRISA，France，1998.

[10]D.Moldt， R.volk. Object Oriented Petri nets in business process modeling[C]. Springer，Berlin，LNCS 1806，2000：254-273.

作者简介：谢汉天（1990.07-），男，浙江省金华市，在读硕士研究生，研究方向：信息安全。

作者单位：浙江师范大学数理与信息工程学院，浙江金华 321004

基金项目：国家基金项目，项目名称：多敏感属性微数据隐私保护关键技术研究（项目编号：61170108）。