一種新型擴展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.