宋亞勤，汪靜（西華大學計算機與軟件工程學院，成都　610039）

一種新型擴展Petri網(wǎng)理論方法研究

宋亞勤，汪靜
（西華大學計算機與軟件工程學院，成都610039）

0　引言

Petri網(wǎng)是一種圖形化的建模方法。使用Petri網(wǎng)對系統(tǒng)建模不僅可以刻畫系統(tǒng)的結(jié)構(gòu)，而且可以描述系統(tǒng)的動態(tài)行為（如系統(tǒng)的狀態(tài)變化等）。此外，Petri網(wǎng)可以清晰地反映系統(tǒng)從一個狀態(tài)過渡到下一個狀態(tài)，準確地描述系統(tǒng)的整體運行狀態(tài)，實現(xiàn)從宏觀上分析建模系統(tǒng)的各項性能指標。在表達、分析方面，Petri網(wǎng)既有直觀的圖形表示，又可以引入許多數(shù)學方法對其性質(zhì)進行準確的數(shù)學分析和嚴格的理論驗證。對于復雜的系統(tǒng)，Petri網(wǎng)可以對其進行分層描述，逐步求精，便于利用面向?qū)ο蟮睦碚摲椒ㄟM行分析、研究。與其他系統(tǒng)網(wǎng)模型比較，對真并發(fā)的恰切描述是Carl Adam Petri的獨特優(yōu)勢之一。然而，隨著Petri網(wǎng)在系統(tǒng)建模中應用的深入，原有的Petri網(wǎng)類型已無法對一些復雜的系統(tǒng)進行建模，抑或使所建模型很復雜，給后續(xù)的分析驗證工作帶來極大的麻煩，在這種情況下，許多新的Petri網(wǎng)類型應運而生。

1　帶抑制弧和使能弧的Petri網(wǎng)

定義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網(wǎng)是一個六元組

其中，N=（P，T；F）是一個網(wǎng)，M是網(wǎng)的一個標識，I?P×T稱為抑制弧集，E?P×T稱為使能弧集，滿足（I∪E）∩F=?（即?p∈P∧∈?t∈T：（p，t）∈F→（p，t）?I））。

（1）對于t∈T，如果

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

則t在標識M下有發(fā)生權(quán)，記為M［t＞。

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

則t在標識M下有發(fā)生權(quán)，同樣記為M［t＞。

（2）若M［t＞，則變遷t在M可以發(fā)生。t在M發(fā)生產(chǎn)生新的標識M'：

從上述表達式上可以看出，變遷在抑制弧和使能弧作用下發(fā)生條件的差別僅在于（2）式和（4）式。而（5）式中表達的標識變化情況與從Σ中刪去抑制弧和使能弧后所得Petri網(wǎng)的標識變化情況一樣。

從定義2可以看出抑制弧和使能弧只對 （在原型Petri網(wǎng)意義下）具備發(fā)生條件的變遷是否允許發(fā)生起控制作用。變遷一旦發(fā)生，抑制弧和使能弧對由此引起的標識變化不產(chǎn)生影響。但可以通過抑制弧和使能弧對某些需要判斷優(yōu)先權(quán)的系統(tǒng)進行準確的描述，以解決Petri網(wǎng)中變遷發(fā)生的隨意性［2］。

2　新型擴展Petri網(wǎng)方法的提出

在定義2中的Petri網(wǎng)中加入顏色元素就構(gòu)成了一種新型的擴展Petri網(wǎng)，即帶抑制弧和使能弧的增廣著色Petri網(wǎng)。由于這類網(wǎng)中加入了顏色元素，它可以對庫所中描述的信息流進行分類，可以表示系統(tǒng)中的多種信息，使用這類Petri網(wǎng)對系統(tǒng)建模，可以實現(xiàn)網(wǎng)系統(tǒng)的折疊，使所建模型簡單、明了。

帶抑制弧和使能弧的著色Petri網(wǎng)是一個十元組

其中

（1）N=（P，T；F）是一個網(wǎng)

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

（3）WF：F→L（C）+表示有限弧集到顏色域函數(shù)的映射

（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）表示庫所到顏色域函數(shù)的映射

在上述定義中，WF、WI、WE分別表示定義在有限弧集F、抑制弧集I、使能弧集E上的權(quán)函數(shù)。L（C）是定義在顏色集C上的一個非負整數(shù)系數(shù)線性函數(shù)，L（C）+表示系數(shù)不全為0的L（C）。

對于t∈T，如果

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

則t在標識M下有發(fā)生權(quán)，記為M［t＞。

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

則t在標識M下有發(fā)生權(quán)，記為M［t＞。

其中L'（M（p））表示由線性方程式M（p）中系數(shù)不為0的元素CK（CK∈C）所組成的集合L'（M（p））?C。

若M［t＞，則t在M下使能發(fā)生，并且產(chǎn)生新的標識M'，則M'為：

從（7）式可以看出當與變遷相連的是抑制弧時，只有當抑制弧上的顏色集合與所連庫所中的顏色集無交集時，該變遷才有可能發(fā)生；（9）式說明當與變遷相連的是使能弧時，只有當使能弧上的顏色集包含于所連庫所的顏色集時，該變遷才有可能發(fā)生。

帶抑制弧和使能弧的著色Petri網(wǎng)與一般Petri網(wǎng)相比，其庫所里的token值以及弧上的權(quán)函數(shù)比較豐富，可以包含多種顏色。雖然這類Petri網(wǎng)的定義比較復雜，但用它對復雜系統(tǒng)建模時，可以使Petri網(wǎng)模型（從某個角度來看）顯得簡單、清晰一些。

3　新型擴展Petri網(wǎng)的圖形表示

帶抑制弧和使能弧的著色網(wǎng)采用加權(quán)有向圖來表示。圖形中的元素包括庫所、變遷和弧，而弧又分為抑制弧、使能弧和有向弧。庫所是表示狀態(tài)的元素，用圓圈來表示，庫所中的token值可以用不同的顏色代表不同的對象或數(shù)據(jù)；變遷是表示變化的元素，用矩形來表示；有向弧上的權(quán)值使用顏色集的線性表達式來表示；從庫所引向變遷的弧以及弧上的空心小圓點表示抑制弧，而從庫所引向變遷的弧以及弧上的實心小圓點表示使能弧，使能弧、抑制弧上面的權(quán)值則用顏色集的子集來表示。如圖1所示，顯示了一個簡單的帶抑制弧和使能弧的著色Petri網(wǎng)。

圖1　帶抑制弧和使能弧的著色Petri網(wǎng)

在上圖所示的帶抑制弧和使能弧的著色Petri網(wǎng)中，變遷T1的控制前集·t為P1，其控制后集t·為P4，與使能弧相連的庫所為P3。在當前標識下，庫所P1的token值為M（P1）=a+3b，從P1到T1的有向弧的權(quán)值函數(shù)為 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擁有發(fā)生權(quán)，且變遷T1發(fā)生之后庫所P1中的token值M（P1）=a+b，庫所P4中的token值M（P4）=c，而庫所P3中的token值不變。由此可知一個變遷的發(fā)生一般只涉及相鄰幾個而不是全部庫所元素的token值。同理，根據(jù)定義3中變遷的觸發(fā)條件，可知變遷T2不具有發(fā)生權(quán)。

4　結(jié)語

傳統(tǒng)的Petri網(wǎng)對數(shù)據(jù)流的描述能力不足、缺少層次性，為此人們在原型Petri網(wǎng)的基礎上引入高級Petri網(wǎng)。其中比較成熟的有顏色Petri網(wǎng)，它具有很強的數(shù)據(jù)描述能力，通過對token進行分類，以實現(xiàn)對網(wǎng)系統(tǒng)的折疊，減少網(wǎng)系統(tǒng)的復雜性。但是，顏色Petri網(wǎng)并不比經(jīng)典的Petri網(wǎng)有更強的模擬能力，所以對一些具有特殊性質(zhì)的系統(tǒng)仍然無法建模。為了提高Petri網(wǎng)的模擬能力，在高級Petri網(wǎng)的基礎上引入了增廣Petri網(wǎng)，它通過增加網(wǎng)系統(tǒng)的元素來增強其模擬能力。如含抑制弧和使能弧的Petri網(wǎng)，抑制弧可以用來控制變遷的發(fā)生順序，描述事件之間的優(yōu)先關系，所以這類網(wǎng)不僅可以對具有優(yōu)先權(quán)的系統(tǒng)進行建模，而且能使模型的描述更加清晰，簡潔。

下一步將這種帶使能弧和抑制弧的著色Petri網(wǎng)應用于城市交通系統(tǒng)中，并通過這種新的方法更加深入地研究交通控制系統(tǒng)，并試圖運用這種擴展Petri網(wǎng)建立一個可靠性高，功能豐富，自適應性更強的城市交通系統(tǒng)模型。

［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-），女，河南鄧州人，碩士，研究方向為嵌入式系統(tǒng)

2015-03-26

2015-04-01

Petri網(wǎng)是一種形式化的建模方法，它非常適合描述系統(tǒng)中進程或部件的順序、并發(fā)、沖突以及同步等關系?？偨Y(jié)各類Petri網(wǎng)在系統(tǒng)建模中的不足和優(yōu)勢，在原有Petri網(wǎng)的基礎上提出一種增廣Petri網(wǎng)，即帶抑止弧和使能弧的著色Petri網(wǎng)，這種新型的Petri網(wǎng)具有很強的模擬描述能力，同時可以對具有優(yōu)先權(quán)性質(zhì)的系統(tǒng)進行建模，因此對該新型擴展Petri網(wǎng)的研究具有十分重要的意義。

原型Petri網(wǎng)；擴展Petri網(wǎng)；抑制弧；使能弧

汪靜（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.