一种新型扩展Petri网理论方法研究

宋亚勤，汪静（西华大学计算机与软件工程学院，成都　610039）

一种新型扩展Petri网理论方法研究

宋亚勤，汪静
（西华大学计算机与软件工程学院，成都610039）

0　引言

Petri网是一种图形化的建模方法。使用Petri网对系统建模不仅可以刻画系统的结构，而且可以描述系统的动态行为（如系统的状态变化等）。此外，Petri网可以清晰地反映系统从一个状态过渡到下一个状态，准确地描述系统的整体运行状态，实现从宏观上分析建模系统的各项性能指标。在表达、分析方面，Petri网既有直观的图形表示，又可以引入许多数学方法对其性质进行准确的数学分析和严格的理论验证。对于复杂的系统，Petri网可以对其进行分层描述，逐步求精，便于利用面向对象的理论方法进行分析、研究。与其他系统网模型比较，对真并发的恰切描述是Carl Adam Petri的独特优势之一。然而，随着Petri网在系统建模中应用的深入，原有的Petri网类型已无法对一些复杂的系统进行建模，抑或使所建模型很复杂，给后续的分析验证工作带来极大的麻烦，在这种情况下，许多新的Petri网类型应运而生。

1　带抑制弧和使能弧的Petri网

定义1·t=｛p∈P|（p，t）∈F｝表示变迁t的控制前集，t·=｛p∈P|（t，p）∈F｝表示变迁t的控制后集，tI=｛p∈P| （p，t）∈I｝表示变迁t的抑制集，tE=｛p∈P|（p，t）∈E｝表示变迁t的使能集。

定义2：带抑制弧和使能弧的Petri网是一个六元组

其中，N=（P，T；F）是一个网，M是网的一个标识，I⊂P×T称为抑制弧集，E⊂P×T称为使能弧集，满足（I∪E）∩F=Ø（即∀p∈P∧∈∀t∈T：（p，t）∈F→（p，t）∉I））。

（1）对于t∈T，如果

①指向它的是抑制弧又满足

则t在标识M下有发生权，记为M［t＞。

②指向它的是使能弧又满足

则t在标识M下有发生权，同样记为M［t＞。

（2）若M［t＞，则变迁t在M可以发生。t在M发生产生新的标识M'：

从上述表达式上可以看出，变迁在抑制弧和使能弧作用下发生条件的差别仅在于（2）式和（4）式。而（5）式中表达的标识变化情况与从Σ中删去抑制弧和使能弧后所得Petri网的标识变化情况一样。

从定义2可以看出抑制弧和使能弧只对 （在原型Petri网意义下）具备发生条件的变迁是否允许发生起控制作用。变迁一旦发生，抑制弧和使能弧对由此引起的标识变化不产生影响。但可以通过抑制弧和使能弧对某些需要判断优先权的系统进行准确的描述，以解决Petri网中变迁发生的随意性［2］。

2　新型扩展Petri网方法的提出

在定义2中的Petri网中加入颜色元素就构成了一种新型的扩展Petri网，即带抑制弧和使能弧的增广着色Petri网。由于这类网中加入了颜色元素，它可以对库所中描述的信息流进行分类，可以表示系统中的多种信息，使用这类Petri网对系统建模，可以实现网系统的折叠，使所建模型简单、明了。

带抑制弧和使能弧的着色Petri网是一个十元组

其中

（1）N=（P，T；F）是一个网

（2）C是颜色的一个有限集合C=｛c1，c2，c3，c4，…，ck｝

（3）WF：F→L（C）+表示有限弧集到颜色域函数的映射

（4）I⊂P×T，E⊂P×T分别为抑制弧集和使能弧集，且I∩E=Ø，（I∪E）∩F=Ø

（5）WI：I→C'（C'⊆C）表示抑制弧集I到颜色集C的真子集C'的映射；WE：E→C'（C'⊆C）表示使能弧集E到颜色集C的真子集C'的映射

（6）M：P→L（C）表示库所到颜色域函数的映射

在上述定义中，WF、WI、WE分别表示定义在有限弧集F、抑制弧集I、使能弧集E上的权函数。L（C）是定义在颜色集C上的一个非负整数系数线性函数，L（C）+表示系数不全为0的L（C）。

对于t∈T，如果

（1）指向它的是抑制弧又满足

则t在标识M下有发生权，记为M［t＞。

②指向它的是使能弧又满足

则t在标识M下有发生权，记为M［t＞。

其中L'（M（p））表示由线性方程式M（p）中系数不为0的元素CK（CK∈C）所组成的集合L'（M（p））⊆C。

若M［t＞，则t在M下使能发生，并且产生新的标识M'，则M'为：

从（7）式可以看出当与变迁相连的是抑制弧时，只有当抑制弧上的颜色集合与所连库所中的颜色集无交集时，该变迁才有可能发生；（9）式说明当与变迁相连的是使能弧时，只有当使能弧上的颜色集包含于所连库所的颜色集时，该变迁才有可能发生。

带抑制弧和使能弧的着色Petri网与一般Petri网相比，其库所里的token值以及弧上的权函数比较丰富，可以包含多种颜色。虽然这类Petri网的定义比较复杂，但用它对复杂系统建模时，可以使Petri网模型（从某个角度来看）显得简单、清晰一些。

3　新型扩展Petri网的图形表示

带抑制弧和使能弧的着色网采用加权有向图来表示。图形中的元素包括库所、变迁和弧，而弧又分为抑制弧、使能弧和有向弧。库所是表示状态的元素，用圆圈来表示，库所中的token值可以用不同的颜色代表不同的对象或数据；变迁是表示变化的元素，用矩形来表示；有向弧上的权值使用颜色集的线性表达式来表示；从库所引向变迁的弧以及弧上的空心小圆点表示抑制弧，而从库所引向变迁的弧以及弧上的实心小圆点表示使能弧，使能弧、抑制弧上面的权值则用颜色集的子集来表示。如图1所示，显示了一个简单的带抑制弧和使能弧的着色Petri网。

图1　带抑制弧和使能弧的着色Petri网

在上图所示的带抑制弧和使能弧的着色Petri网中，变迁T1的控制前集·t为P1，其控制后集t·为P4，与使能弧相连的库所为P3。在当前标识下，库所P1的token值为M（P1）=a+3b，从P1到T1的有向弧的权值函数为 WF（P1，T1）=2b，故有 M（P1）≥WF（P1，T1），而变迁T1的使能库所P3的token值为M（P3）=2a+b，则有L'（M（P3））=｛a，b｝，而WE（C）=｛a｝，所以有L'（M（P3））⊇WE（C）。综上所述可知变迁T1拥有发生权，且变迁T1发生之后库所P1中的token值M（P1）=a+b，库所P4中的token值M（P4）=c，而库所P3中的token值不变。由此可知一个变迁的发生一般只涉及相邻几个而不是全部库所元素的token值。同理，根据定义3中变迁的触发条件，可知变迁T2不具有发生权。

4　结语

传统的Petri网对数据流的描述能力不足、缺少层次性，为此人们在原型Petri网的基础上引入高级Petri网。其中比较成熟的有颜色Petri网，它具有很强的数据描述能力，通过对token进行分类，以实现对网系统的折叠，减少网系统的复杂性。但是，颜色Petri网并不比经典的Petri网有更强的模拟能力，所以对一些具有特殊性质的系统仍然无法建模。为了提高Petri网的模拟能力，在高级Petri网的基础上引入了增广Petri网，它通过增加网系统的元素来增强其模拟能力。如含抑制弧和使能弧的Petri网，抑制弧可以用来控制变迁的发生顺序，描述事件之间的优先关系，所以这类网不仅可以对具有优先权的系统进行建模，而且能使模型的描述更加清晰，简洁。

下一步将这种带使能弧和抑制弧的着色Petri网应用于城市交通系统中，并通过这种新的方法更加深入地研究交通控制系统，并试图运用这种扩展Petri网建立一个可靠性高，功能丰富，自适应性更强的城市交通系统模型。

［1］Azzumar M，Halim A，Harjono M.Performance Evaluation of Two Ways Urban Traffic Control System Based on Macroscopic Hybrid Petri Net Model.ICACSIS，2013

［2］Huang Yi-Sheng，Weng Yi-Shun，Der Jeng Mu，Chen Bo-Yang.Based on Synchronized Timed Petri Nets for Urban Traffic Control Systems.IEEE，SMC，2013

［3］LIN Ci-yun，YANG Zhao-sheng，Gong Bowen.Dynamic Model of Transit Signal Priority on Colored Time Petri Net.ICCTP，2009

［4］Huang Yi-Sheng，Weng Yi-Shun，Zhou Meng-chu.Modular Design of Urban Traffic-Light Control Systems Based on Synchronized Timed Petri Nets.IEEE，2014

［5］Ng，Kok Mun；Reaz，Mamun Bin Lbne；Ali Mohd Alauddin Mohd.A Review on the Applications of Petri Nets in Modeling Analysis and Control of Urban Traffic.IEEE Transactions on Intellient Transportation Systems，2013

Original Petri Net；Extended Colored Petri Nets；Inhibitor Arcs；Enabling Arcs

Research on a Theoretical Method of New Extended Petri Net

SONG Ya-qin，WANG Jing
（School of Computer and Software Engineering，Xihua University，Chengdu 610039）

1007-1423（2015）10-0013-04

10.3969/j.issn.1007-1423.2015.10.004

宋亚勤（1988-），女，河南邓州人，硕士，研究方向为嵌入式系统

2015-03-26

2015-04-01

Petri网是一种形式化的建模方法，它非常适合描述系统中进程或部件的顺序、并发、冲突以及同步等关系。总结各类Petri网在系统建模中的不足和优势，在原有Petri网的基础上提出一种增广Petri网，即带抑止弧和使能弧的着色Petri网，这种新型的Petri网具有很强的模拟描述能力，同时可以对具有优先权性质的系统进行建模，因此对该新型扩展Petri网的研究具有十分重要的意义。

原型Petri网；扩展Petri网；抑制弧；使能弧

汪静（1989-），女，四川南充人，研究生，研究方向为无线电通信中的序列设计

Petri net is a formal modeling method which is very suitable to describe the processes or order，the concurrence，conflict and synchronization parts in the system.Summarizes merit and demerit of some kinds of Petri net，and proposes a new kind of augmented Petri net based on the archetypal Petri net，which is called a colored Petri net with inhibitor arcs and enabling arcs.The new augmented Petri net has strong ability in simulation and description，at the same time it can model systems which has the nature of priority.It is of great importance to study this new augmented Petri net.