Petri网结点精化及其应用

祁方民

(中国人民银行西宁中心支行，青海 西宁 810001)

0 引言

Petri网是一种适合描述异步并发现象的系统模型，它既有严格的数学定义，又有直观的图形表示，既有丰富的系统描述手段和系统行为分析技术，又为计算机科学提供了坚实的概念基础。Petri网的概念最早是由德国的Carl Adam Petri于1962年在其博士论文《自动机通信》中提出来的。

Petri网是一个描述与分析并行系统的优秀模型。但是在实际应用中，如果系统过大或较复杂时，会遇到结点数爆炸的问题。解决Petri网应用中遇到的结点数爆炸问题，最好的方法就是分层。

在文献[1]中，作者列举了可以解决结点数爆炸问题的一些方法，提供了解决该问题的方法和思路，便于我们学习和研究。本文针对文献[1]中提到的有关结点精化方向的一些问题进行讨论和研究，就结点精化在解决Petri网结点爆炸问题上提出自己的见解。

1 结点精化基础

Rainer Fehling在1993年国际Petri网理论与应用大会上首先提出了结点精化的技术，最先在Petri网中引入层次方法。

结点精化的基本思路是将一个Petri网(上层网)中的某个结点用另一个Petri网(下层网)进行精化(即替换)，从而形成分层的Petri网。如果这个结点是库所，就称为库所精化(Place Refinement);结点是变迁，就称为变迁精化(Transition Refinement)。使用结点精化的技术可以使包含众多结点的Petri网在形式上更为简洁，在包含特定的语义时更能帮助理解Petri网。但是，结点精化的方法存在诸多问题。

首先，它对下层网有严格的限制。结点精化子网要求必须只有一个入口一个出口。对于库所精化，入口、出口要求是库所，即所谓P-P网或P型网。对于变迁精化入口、出口要求是变迁，即要求下层网必须是T-T网或T型网。

其次，库所精化还应当要求下层网的功能与上层Petri网中相应结点的功能相匹配。例如，Petri网中的库所所含的Token在没有前面变迁激发的条件下，不能自动增加和减少。这就要求子网执行前入口库所中的Token数必须与执行后出口库所中的Token数相同。

一般系统的模型均由2类元素构成:表示状态的元素和表示变化的元素，Petri网的状态元素和变化元素分别称为S元素和T元素，也简称为S元和T元。

2 结点精化Petri网定义

首先给出Petri网N的定义，在此基础上再给出Petri网的结点精化条件定义:

定义1 三元组N=(S，T，F)为Petri网结构，则有:

(x，y)∈F}，cod(F)={y|∃x:(x，y)∈F}分别是 F 的定义域和值域。

其中，S和T分别被称为N的库所(place)集和变迁(transition)集，F为流关系(flow relation);库所集和变迁集是有向网的基本成分，流关系是从中构造出来的，而连接S和T中元素的叫做弧(arc)，弧是F中的元素，所以弧只能连接库所和变迁，不能连接2个库所或者是2个变迁。

2.1 Petri网库所结点精化(Place Refinement)

定义2 三元组N=(S，T，F)可以作为库所结点精化下一层Petri网结构的必要条件是:

(1)N是一个Petri网结构，S和T分别称为N的库所集和变迁集。F为流关系;

2.2 Petri网变迁结点精化(Transition Refinement)

定义3 三元组N=(S，T，F)为变迁结点精化下一层Petri网的必要条件是:

(1)N是一个基本网系统，S和T分别称为N的库所集和变迁集。F为流关系;

具体结点精化实例如图1和图2所示。

图1 库所结点精化实例

图2 变迁结点精化实例

3 结点精化的Petri网元素

在结点精化的Petri网中，状态元素和变化元素分别用库所和变迁表示，两者是平等的，库所由变迁来改变，而变迁由库所来描述，两者相互依存。

3.1 库所

Petri网中通常通过圆来表示库所，可以反映状态信息。从定义2给出结点精化下一层Petri网的条件，库所是一个递归的概念:库所可以是一个基本Petri网包含库所，也可以是一个库所结点精化后的下一层Petri网，以集中反映某一阶段的状态信息。

定义2中条件(1)保证了在Petri网的库所精化中，各个结点之间的相互关系仍然遵从基本网的要求;条件(2)和条件(3)是对下一层库所结点精化Petri网的限制，它的存在是必要的。

1)库所结点精化网中，下一层网系统代替上一层网系统中的某个待精化的库所结点，从功能上讲要求下一层网能描述一种状态，所以下一层精化网的初始和结束结点要求是库所。

2)按照Petri网N的定义，弧用来连接变迁和库所，作为库所结点精化，其上一层与库所能连接的必然只有变迁，精化后下一层Petri网将替换原来的库所结点，为了保证替换后结果的正确性，要求下一层网的开始和结束结点必须是库所。

在库所精化的Petri网的定义中，通过条件(2)和条件(3)来保证替换后的正确性，即库所精化，入口、出口结点各只有一个，且要求是库所，即所谓P-P网或P型网;条件(4)防止经下一层网替换后出现弧连接2个变迁的情况，是对条件(2)和条件(3)的加强。

3.2 变迁

库所之间是通过变迁来连接的。定义3对下一层Petri网的变迁结点精化提出必要性条件，其中结点精化Petri网的变迁可反映底层状态的变化过程，也可将需要经过多重变迁的2个状态之间的一系列变迁和状态综合表示为一个变迁，整体刻画某2个状态之间的变化过程，但是要求这2个状态之间是有路径可达的。

定义3中条件(2)和条件(3)是在Petri网的定义基础上对变迁结点精化的Petri网的限制:

1)变迁结点精化网代替上一层网系统中的某个待精化的变迁结点，所以从功能上讲一般要求下一层的精华网能满足描述一定变化需要，因此在该精化网的初始和结束结点为变迁结点是必要的。

2)按照Petri网N的定义，作为变迁结点精化，其上一层与变迁能连接的必然只有变迁，精化后下一层Petri网将替换原来的库所结点。为了保证替换后结果的正确性，要求下一层网的开始和结束结点必须是变迁。

在变迁精化的Petri网的定义中，通过条件(2)和条件(3)来保证替换后的正确性，即变迁精化，入口、出口结点各只有一个，且要求是变迁，即所谓T-T网或T型网，条件(4)防止经下一层网替换后出现弧连接2个库所的情况，是对条件(2)和条件(3)的加强。

利用结点精化Petri网还要规范库所、变迁的输入和输出信息，也就是Token信息和权信息。

3.3 Token

结点精化Petri网中，库所结点如果不需要被精化网替换，则该库所中的黑点表示该种资源的数量;如果该库所由一个下层库所精化Petri网来替换，则按照对库所精化Petri网的条件，要求每个变迁必须存在它的前驱库所和后继库所，所以当一个完整的库所精化的Petri子网∑'视作一个库所s置入到上一级的Petri网∑中，为了保证上一级Petri网的正确性，要求库所s的Token分为2类:第1类可以称为输入Token(Input Token)，是所有库所精化的Petri网∑'中无前驱的库所中的Token集合，此时的Token代表整个库所精化的Petri网的子网∑'开始工作时的初始情态;第2类可以称为输出Token(Output Token)，是所有库所精化的Petri网子网∑'中无后继的库所中的Token集合，此时的Token代表整个库所精化的Petri网子网∑'结束工作时的终结情态。

对于库所结点s，设其可被结点精化Petri网N’(S’，T’，F’)进行精化，则其包含的 Token 可以定义如下:

定义4 库所结点s包含一个Token集合R，则:

根据定义4，对于结点精化的Petri网，可以将库所包含的Token信息分为由输入Token集合和输出Token集合组成的有序数对。当该Token没有被精化，则该库所的输入Token集合和输出Token集合相等，即Ri=Ro;否则，Ri代表被精化的某个库所结点的初始状态，Ro代表该库所结点的终结状态。为讨论方便，以下将输入集合与输出集合合并称为Token集合，集合数量为1。

3.4 弧与权

弧用来连接库所和变迁，并且只能由库所到变迁或从变迁到库所，不能用来连接2个库所或2个变迁。在弧上通过权来表示所传递的Token信息。

定义5 W:F→N称为结点精化的Petri网N的权函数，对(x，y)∈F，W(x，y)=W((x，y))称为(x，y)上的权。根据定义4，在结点精化Petri网的图形描述中，变迁传输的是Token集，且传输的Token集合的数量是1，在不引起歧义的情况下对Token集的数量不进行描述。

4 正确性证明

在定义2和定义3中给出了结点精化Petri网的必要条件，定义4和定义5则是对Token信息和权信息的必要补充，结合定义2～定义5，结点精化的Petri网可以与上层结合并与上层结点的原有功能匹配。

首先给出精化层数的概念:

定义6

如果一个结点精化的Petri网N在实际建模过程中没有结点进行精化，则其精化层数为0;

如果一个结点精化的Petri网N在实际建模过程中有结点被下一层结点精化Petri网N’精化，且N’中任何结点没有被再次精化，则Petri网N的精化层数为1;

如果一个结点精化的Petri网N的各个结点的下一层结点精化Petri网中最大的层数为m，则Petri网N的精化层数为m+1。

为便于讨论，将层数为m的结点精化的Petri网N最顶层叫第0层，其下一层叫第1层，…，最后一层叫第m层。

下面给出证明。

证明 设结点精化的Petri网N，其精化层数为m，对其进行归纳假设:

1)当m=0时，此时结点精化的Petri网N没有进行精化，则结点精化的Petri网N本身就是经典网系统;

2)对于结点精化的Petri网N，假设从其最顶层的一层结点精化的Petri网精化到第j层，其中0＜j＜m，其部分(精化层次数小于j的网)与被替换的上层结点的功能匹配;

3)对于第j+1层网，其中库所结点x由下一层结点精化Petri网Nx精化，则x包含输入库所和输出库所，其中根据定义4，x的输入库所是Nx的初始状态，x的输出库所是Nx的结束状态，将x用Nx来替换;设Nx的初始结点为x1，结束结点为x2，则x的输入库所是x1的库所，x的输出库所是x2的库所，使得Nx可以正确描述建模过程并同上一层网紧密联系，精化后的第j+1层准确匹配，又根据假设2)，对于小于j+1的各层已经得到匹配，所以第j+1层的功能和它替换掉的原有结点的功能是可以匹配的。

5 结点精化Petri网的应用

结点精化的过程是将原Petri网中的结点由下一层的Petri网来代替，同时，这项工作是可以逆向的:即对于结点数量过多的网，利用上述定义的条件，可将其中部分的结点组合，由新的一个库所或变迁结点来替换这个组合，从而可以帮助在建模过程中从不同层次观察和验证，满足不同需求的需要。

同时可以利用结点精化方法解决建模过程中引起的结点爆炸问题。

建模的对象通常是一个动态过程，一部分表示状态的信息在初始阶段只能从宏观角度把握，不能够详细得到和了解。这一特点使得Petri网很难对这种动态“属性”进行考虑，精化的Petri网可以根据建模对象的动态变化及时并尽量准确客观反映到实际的建模过程中，指导建模或检验过程实施。例如库所精化，这样精化的现实意义在于利用结点精化Petri网建模，可将某个外部特征明确或暂时只需考虑外部整体特征的对象作为单个库所来对待，使建模前期可以从整体角度对该对象进行分析，排除内在不影响整个模块总体功能部分，加强对整个软件项目的管理和宏观规划，待需要更细化讨论时，由下一层的精化网来代替原有的结点。

变迁结点精化的Petri网对于高层次网而言，可以对相邻的变迁进行整合，在初始建模或描述阶段暂时省略一些相对过程比较完善和成熟的部分，保证在宏观的建模描述阶段能够顺利及时完成。一般对于已经有成功经验的内容可以考虑使用变迁结点精化，在不影响全局的情况下暂缓涉及。

6 结束语

结点精化Petri网可以解决结点爆炸问题，同时，结点精化的思路可以用到对对象建模逐层细化的过程中，这种过程更加符合人们发现事物、认识事物、改造事物和利用事物的认知过程。

[1] 郝克刚.Petri网的分层[DB/OL].http://www.ccf.org.cn/web/resource/haokegang.pdf，2007-08-01.

[2] 祁方民，鱼滨，史立军，等.基于Petri网的软件项目管理建模方法[J].系统仿真学报，2007，19(S1):75-78.

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

[4] Van der Aalst W M P.Workflow verification:Finding control-flow errors using Petri-net-based techniques[C]//Business Process Management，Models，Techniques，and Empirical Studies.2000:161-183.

[5] Stork D G，Van Glabbeek R J.Token-controlled place refinement in hierarchical Petri nets with application to active document workflow[C]//Proceedings of the 23rd International Conference on Applications and Theory of Petri Nets.2002:394-413.

[6] 夏传良，焦莉，陆维明.Petri网共享PP-型子网合成性质分析[J].软件学报，2007，18(1):22-32.

[7] Fehling R.A concept of hierarchical Petri nets with building blocks[C]//Proceedings of the 12th International Conference on Application and Theory of Petri Nets.1993:148-168.

[8] 倪悦，范玉顺.基于着色Petri网的语义Web服务组合形式化验证[J].清华大学学报(自然科学版)，2010，50(5):714-717.

[9] Liu Yongshan，Hao Zhongxiao.Petri net based spatio-temporal relationships for moving objects[J].Journal of Computer Science，2005，1(4):510-514.

[10] 何炎祥，沈华.一种基于随机Petri网的Web服务组合性能瓶颈定位策略[J].计算机学报，2013，36(10):1953-1966.

[11] 高翔，祝跃飞，刘胜利.一种基于广义随机着色Petri网的网络攻击组合模型[J].电子与信息学报，2013，35(11):2608-2614.

[12] 童晓阳，谢红涛，孙明蔚.计及时序信息检查的分层模糊Petri网电网故障诊断模型[J].电力系统自动化，2013，37(6):63-68.

[13] Houhamdi Z，Athamena B.A Petri net based agent behavioral testing[J].American Journal of Applied Sciences，2012，9(11):1876-1883.

[14] 陈曦，周彦，乐晓波，等.Petri网化简新技术研究[J].计算机工程与应用，2012，48(5):47-50.

[15] 汤志伟，殷静.基于扩展Petri网的仿真建模与分析[J].电子科技大学学报，2012，41(1):131-135.

[16] Qudsiya A A，Rangarajan K.Modelling performance monitoring of it infrastructure components using timed Petri nets[J].Indian Journal of Computer Science and Engineering，2012，3(1):94-103.

[17] Ding Zuohua，Ma Jiaying，Kandel A.Petri net representation of switched fuzzy systems[J].IEEE Transactions on Fuzzy Systems，2013，21(1):16-29.