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

宋亞勤，汪靜（西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，成都　610039）

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

宋亞勤，汪靜
（西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，成都610039）

0　引言

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

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)是一個(gè)六元組

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

（1）對(duì)于t∈T，如果

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

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

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

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

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

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

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

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

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

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

其中

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

（2）C是顏色的一個(gè)有限集合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）表示庫(kù)所到顏色域函數(shù)的映射

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

對(duì)于t∈T，如果

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

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

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

則t在標(biāo)識(shí)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)生新的標(biāo)識(shí)M'，則M'為：

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

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

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

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

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

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

4　結(jié)語(yǔ)

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

下一步將這種帶使能弧和抑制弧的著色Petri網(wǎng)應(yīng)用于城市交通系統(tǒng)中，并通過(guò)這種新的方法更加深入地研究交通控制系統(tǒng)，并試圖運(yùn)用這種擴(kuò)展Petri網(wǎng)建立一個(gè)可靠性高，功能豐富，自適應(yīng)性更強(qiá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-），女，河南鄧州人，碩士，研究方向?yàn)榍度胧较到y(tǒng)

2015-03-26

2015-04-01

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

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

汪靜（1989-），女，四川南充人，研究生，研究方向?yàn)闊o(wú)線電通信中的序列設(shè)計(jì)

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.