Petri網(wǎng)結(jié)點精化及其應(yīng)用

祁方民

(中國人民銀行西寧中心支行，青海 西寧 810001)

0 引言

Petri網(wǎng)是一種適合描述異步并發(fā)現(xiàn)象的系統(tǒng)模型，它既有嚴(yán)格的數(shù)學(xué)定義，又有直觀的圖形表示，既有豐富的系統(tǒng)描述手段和系統(tǒng)行為分析技術(shù)，又為計算機科學(xué)提供了堅實的概念基礎(chǔ)。Petri網(wǎng)的概念最早是由德國的Carl Adam Petri于1962年在其博士論文《自動機通信》中提出來的。

Petri網(wǎng)是一個描述與分析并行系統(tǒng)的優(yōu)秀模型。但是在實際應(yīng)用中，如果系統(tǒng)過大或較復(fù)雜時，會遇到結(jié)點數(shù)爆炸的問題。解決Petri網(wǎng)應(yīng)用中遇到的結(jié)點數(shù)爆炸問題，最好的方法就是分層。

在文獻[1]中，作者列舉了可以解決結(jié)點數(shù)爆炸問題的一些方法，提供了解決該問題的方法和思路，便于我們學(xué)習(xí)和研究。本文針對文獻[1]中提到的有關(guān)結(jié)點精化方向的一些問題進行討論和研究，就結(jié)點精化在解決Petri網(wǎng)結(jié)點爆炸問題上提出自己的見解。

1 結(jié)點精化基礎(chǔ)

Rainer Fehling在1993年國際Petri網(wǎng)理論與應(yīng)用大會上首先提出了結(jié)點精化的技術(shù)，最先在Petri網(wǎng)中引入層次方法。

結(jié)點精化的基本思路是將一個Petri網(wǎng)(上層網(wǎng))中的某個結(jié)點用另一個Petri網(wǎng)(下層網(wǎng))進行精化(即替換)，從而形成分層的Petri網(wǎng)。如果這個結(jié)點是庫所，就稱為庫所精化(Place Refinement);結(jié)點是變遷，就稱為變遷精化(Transition Refinement)。使用結(jié)點精化的技術(shù)可以使包含眾多結(jié)點的Petri網(wǎng)在形式上更為簡潔，在包含特定的語義時更能幫助理解Petri網(wǎng)。但是，結(jié)點精化的方法存在諸多問題。

首先，它對下層網(wǎng)有嚴(yán)格的限制。結(jié)點精化子網(wǎng)要求必須只有一個入口一個出口。對于庫所精化，入口、出口要求是庫所，即所謂P-P網(wǎng)或P型網(wǎng)。對于變遷精化入口、出口要求是變遷，即要求下層網(wǎng)必須是T-T網(wǎng)或T型網(wǎng)。

其次，庫所精化還應(yīng)當(dāng)要求下層網(wǎng)的功能與上層Petri網(wǎng)中相應(yīng)結(jié)點的功能相匹配。例如，Petri網(wǎng)中的庫所所含的Token在沒有前面變遷激發(fā)的條件下，不能自動增加和減少。這就要求子網(wǎng)執(zhí)行前入口庫所中的Token數(shù)必須與執(zhí)行后出口庫所中的Token數(shù)相同。

一般系統(tǒng)的模型均由2類元素構(gòu)成:表示狀態(tài)的元素和表示變化的元素，Petri網(wǎng)的狀態(tài)元素和變化元素分別稱為S元素和T元素，也簡稱為S元和T元。

2 結(jié)點精化Petri網(wǎng)定義

首先給出Petri網(wǎng)N的定義，在此基礎(chǔ)上再給出Petri網(wǎng)的結(jié)點精化條件定義:

定義1 三元組N=(S，T，F(xiàn))為Petri網(wǎng)結(jié)構(gòu)，則有:

(x，y)∈F}，cod(F)={y|?x:(x，y)∈F}分別是 F 的定義域和值域。

其中，S和T分別被稱為N的庫所(place)集和變遷(transition)集，F(xiàn)為流關(guān)系(flow relation);庫所集和變遷集是有向網(wǎng)的基本成分，流關(guān)系是從中構(gòu)造出來的，而連接S和T中元素的叫做弧(arc)，弧是F中的元素，所以弧只能連接庫所和變遷，不能連接2個庫所或者是2個變遷。

2.1 Petri網(wǎng)庫所結(jié)點精化(Place Refinement)

定義2 三元組N=(S，T，F(xiàn))可以作為庫所結(jié)點精化下一層Petri網(wǎng)結(jié)構(gòu)的必要條件是:

(1)N是一個Petri網(wǎng)結(jié)構(gòu)，S和T分別稱為N的庫所集和變遷集。F為流關(guān)系;

2.2 Petri網(wǎng)變遷結(jié)點精化(Transition Refinement)

定義3 三元組N=(S，T，F(xiàn))為變遷結(jié)點精化下一層Petri網(wǎng)的必要條件是:

(1)N是一個基本網(wǎng)系統(tǒng)，S和T分別稱為N的庫所集和變遷集。F為流關(guān)系;

具體結(jié)點精化實例如圖1和圖2所示。

圖1 庫所結(jié)點精化實例

圖2 變遷結(jié)點精化實例

3 結(jié)點精化的Petri網(wǎng)元素

在結(jié)點精化的Petri網(wǎng)中，狀態(tài)元素和變化元素分別用庫所和變遷表示，兩者是平等的，庫所由變遷來改變，而變遷由庫所來描述，兩者相互依存。

3.1 庫所

Petri網(wǎng)中通常通過圓來表示庫所，可以反映狀態(tài)信息。從定義2給出結(jié)點精化下一層Petri網(wǎng)的條件，庫所是一個遞歸的概念:庫所可以是一個基本Petri網(wǎng)包含庫所，也可以是一個庫所結(jié)點精化后的下一層Petri網(wǎng)，以集中反映某一階段的狀態(tài)信息。

定義2中條件(1)保證了在Petri網(wǎng)的庫所精化中，各個結(jié)點之間的相互關(guān)系仍然遵從基本網(wǎng)的要求;條件(2)和條件(3)是對下一層庫所結(jié)點精化Petri網(wǎng)的限制，它的存在是必要的。

1)庫所結(jié)點精化網(wǎng)中，下一層網(wǎng)系統(tǒng)代替上一層網(wǎng)系統(tǒng)中的某個待精化的庫所結(jié)點，從功能上講要求下一層網(wǎng)能描述一種狀態(tài)，所以下一層精化網(wǎng)的初始和結(jié)束結(jié)點要求是庫所。

2)按照Petri網(wǎng)N的定義，弧用來連接變遷和庫所，作為庫所結(jié)點精化，其上一層與庫所能連接的必然只有變遷，精化后下一層Petri網(wǎng)將替換原來的庫所結(jié)點，為了保證替換后結(jié)果的正確性，要求下一層網(wǎng)的開始和結(jié)束結(jié)點必須是庫所。

在庫所精化的Petri網(wǎng)的定義中，通過條件(2)和條件(3)來保證替換后的正確性，即庫所精化，入口、出口結(jié)點各只有一個，且要求是庫所，即所謂P-P網(wǎng)或P型網(wǎng);條件(4)防止經(jīng)下一層網(wǎng)替換后出現(xiàn)弧連接2個變遷的情況，是對條件(2)和條件(3)的加強。

3.2 變遷

庫所之間是通過變遷來連接的。定義3對下一層Petri網(wǎng)的變遷結(jié)點精化提出必要性條件，其中結(jié)點精化Petri網(wǎng)的變遷可反映底層狀態(tài)的變化過程，也可將需要經(jīng)過多重變遷的2個狀態(tài)之間的一系列變遷和狀態(tài)綜合表示為一個變遷，整體刻畫某2個狀態(tài)之間的變化過程，但是要求這2個狀態(tài)之間是有路徑可達的。

定義3中條件(2)和條件(3)是在Petri網(wǎng)的定義基礎(chǔ)上對變遷結(jié)點精化的Petri網(wǎng)的限制:

1)變遷結(jié)點精化網(wǎng)代替上一層網(wǎng)系統(tǒng)中的某個待精化的變遷結(jié)點，所以從功能上講一般要求下一層的精華網(wǎng)能滿足描述一定變化需要，因此在該精化網(wǎng)的初始和結(jié)束結(jié)點為變遷結(jié)點是必要的。

2)按照Petri網(wǎng)N的定義，作為變遷結(jié)點精化，其上一層與變遷能連接的必然只有變遷，精化后下一層Petri網(wǎng)將替換原來的庫所結(jié)點。為了保證替換后結(jié)果的正確性，要求下一層網(wǎng)的開始和結(jié)束結(jié)點必須是變遷。

在變遷精化的Petri網(wǎng)的定義中，通過條件(2)和條件(3)來保證替換后的正確性，即變遷精化，入口、出口結(jié)點各只有一個，且要求是變遷，即所謂T-T網(wǎng)或T型網(wǎng)，條件(4)防止經(jīng)下一層網(wǎng)替換后出現(xiàn)弧連接2個庫所的情況，是對條件(2)和條件(3)的加強。

利用結(jié)點精化Petri網(wǎng)還要規(guī)范庫所、變遷的輸入和輸出信息，也就是Token信息和權(quán)信息。

3.3 Token

結(jié)點精化Petri網(wǎng)中，庫所結(jié)點如果不需要被精化網(wǎng)替換，則該庫所中的黑點表示該種資源的數(shù)量;如果該庫所由一個下層庫所精化Petri網(wǎng)來替換，則按照對庫所精化Petri網(wǎng)的條件，要求每個變遷必須存在它的前驅(qū)庫所和后繼庫所，所以當(dāng)一個完整的庫所精化的Petri子網(wǎng)∑'視作一個庫所s置入到上一級的Petri網(wǎng)∑中，為了保證上一級Petri網(wǎng)的正確性，要求庫所s的Token分為2類:第1類可以稱為輸入Token(Input Token)，是所有庫所精化的Petri網(wǎng)∑'中無前驅(qū)的庫所中的Token集合，此時的Token代表整個庫所精化的Petri網(wǎng)的子網(wǎng)∑'開始工作時的初始情態(tài);第2類可以稱為輸出Token(Output Token)，是所有庫所精化的Petri網(wǎng)子網(wǎng)∑'中無后繼的庫所中的Token集合，此時的Token代表整個庫所精化的Petri網(wǎng)子網(wǎng)∑'結(jié)束工作時的終結(jié)情態(tài)。

對于庫所結(jié)點s，設(shè)其可被結(jié)點精化Petri網(wǎng)N’(S’，T’，F(xiàn)’)進行精化，則其包含的 Token 可以定義如下:

定義4 庫所結(jié)點s包含一個Token集合R，則:

根據(jù)定義4，對于結(jié)點精化的Petri網(wǎng)，可以將庫所包含的Token信息分為由輸入Token集合和輸出Token集合組成的有序數(shù)對。當(dāng)該Token沒有被精化，則該庫所的輸入Token集合和輸出Token集合相等，即Ri=Ro;否則，Ri代表被精化的某個庫所結(jié)點的初始狀態(tài)，Ro代表該庫所結(jié)點的終結(jié)狀態(tài)。為討論方便，以下將輸入集合與輸出集合合并稱為Token集合，集合數(shù)量為1。

3.4 弧與權(quán)

弧用來連接庫所和變遷，并且只能由庫所到變遷或從變遷到庫所，不能用來連接2個庫所或2個變遷。在弧上通過權(quán)來表示所傳遞的Token信息。

定義5 W:F→N稱為結(jié)點精化的Petri網(wǎng)N的權(quán)函數(shù)，對(x，y)∈F，W(x，y)=W((x，y))稱為(x，y)上的權(quán)。根據(jù)定義4，在結(jié)點精化Petri網(wǎng)的圖形描述中，變遷傳輸?shù)氖荰oken集，且傳輸?shù)腡oken集合的數(shù)量是1，在不引起歧義的情況下對Token集的數(shù)量不進行描述。

4 正確性證明

在定義2和定義3中給出了結(jié)點精化Petri網(wǎng)的必要條件，定義4和定義5則是對Token信息和權(quán)信息的必要補充，結(jié)合定義2～定義5，結(jié)點精化的Petri網(wǎng)可以與上層結(jié)合并與上層結(jié)點的原有功能匹配。

首先給出精化層數(shù)的概念:

定義6

如果一個結(jié)點精化的Petri網(wǎng)N在實際建模過程中沒有結(jié)點進行精化，則其精化層數(shù)為0;

如果一個結(jié)點精化的Petri網(wǎng)N在實際建模過程中有結(jié)點被下一層結(jié)點精化Petri網(wǎng)N’精化，且N’中任何結(jié)點沒有被再次精化，則Petri網(wǎng)N的精化層數(shù)為1;

如果一個結(jié)點精化的Petri網(wǎng)N的各個結(jié)點的下一層結(jié)點精化Petri網(wǎng)中最大的層數(shù)為m，則Petri網(wǎng)N的精化層數(shù)為m+1。

為便于討論，將層數(shù)為m的結(jié)點精化的Petri網(wǎng)N最頂層叫第0層，其下一層叫第1層，…，最后一層叫第m層。

下面給出證明。

證明 設(shè)結(jié)點精化的Petri網(wǎng)N，其精化層數(shù)為m，對其進行歸納假設(shè):

1)當(dāng)m=0時，此時結(jié)點精化的Petri網(wǎng)N沒有進行精化，則結(jié)點精化的Petri網(wǎng)N本身就是經(jīng)典網(wǎng)系統(tǒng);

2)對于結(jié)點精化的Petri網(wǎng)N，假設(shè)從其最頂層的一層結(jié)點精化的Petri網(wǎng)精化到第j層，其中0＜j＜m，其部分(精化層次數(shù)小于j的網(wǎng))與被替換的上層結(jié)點的功能匹配;

3)對于第j+1層網(wǎng)，其中庫所結(jié)點x由下一層結(jié)點精化Petri網(wǎng)Nx精化，則x包含輸入庫所和輸出庫所，其中根據(jù)定義4，x的輸入庫所是Nx的初始狀態(tài)，x的輸出庫所是Nx的結(jié)束狀態(tài)，將x用Nx來替換;設(shè)Nx的初始結(jié)點為x1，結(jié)束結(jié)點為x2，則x的輸入庫所是x1的庫所，x的輸出庫所是x2的庫所，使得Nx可以正確描述建模過程并同上一層網(wǎng)緊密聯(lián)系，精化后的第j+1層準(zhǔn)確匹配，又根據(jù)假設(shè)2)，對于小于j+1的各層已經(jīng)得到匹配，所以第j+1層的功能和它替換掉的原有結(jié)點的功能是可以匹配的。

5 結(jié)點精化Petri網(wǎng)的應(yīng)用

結(jié)點精化的過程是將原Petri網(wǎng)中的結(jié)點由下一層的Petri網(wǎng)來代替，同時，這項工作是可以逆向的:即對于結(jié)點數(shù)量過多的網(wǎng)，利用上述定義的條件，可將其中部分的結(jié)點組合，由新的一個庫所或變遷結(jié)點來替換這個組合，從而可以幫助在建模過程中從不同層次觀察和驗證，滿足不同需求的需要。

同時可以利用結(jié)點精化方法解決建模過程中引起的結(jié)點爆炸問題。

建模的對象通常是一個動態(tài)過程，一部分表示狀態(tài)的信息在初始階段只能從宏觀角度把握，不能夠詳細得到和了解。這一特點使得Petri網(wǎng)很難對這種動態(tài)“屬性”進行考慮，精化的Petri網(wǎng)可以根據(jù)建模對象的動態(tài)變化及時并盡量準(zhǔn)確客觀反映到實際的建模過程中，指導(dǎo)建模或檢驗過程實施。例如庫所精化，這樣精化的現(xiàn)實意義在于利用結(jié)點精化Petri網(wǎng)建模，可將某個外部特征明確或暫時只需考慮外部整體特征的對象作為單個庫所來對待，使建模前期可以從整體角度對該對象進行分析，排除內(nèi)在不影響整個模塊總體功能部分，加強對整個軟件項目的管理和宏觀規(guī)劃，待需要更細化討論時，由下一層的精化網(wǎng)來代替原有的結(jié)點。

變遷結(jié)點精化的Petri網(wǎng)對于高層次網(wǎng)而言，可以對相鄰的變遷進行整合，在初始建模或描述階段暫時省略一些相對過程比較完善和成熟的部分，保證在宏觀的建模描述階段能夠順利及時完成。一般對于已經(jīng)有成功經(jīng)驗的內(nèi)容可以考慮使用變遷結(jié)點精化，在不影響全局的情況下暫緩涉及。

6 結(jié)束語

結(jié)點精化Petri網(wǎng)可以解決結(jié)點爆炸問題，同時，結(jié)點精化的思路可以用到對對象建模逐層細化的過程中，這種過程更加符合人們發(fā)現(xiàn)事物、認識事物、改造事物和利用事物的認知過程。

[1] 郝克剛.Petri網(wǎng)的分層[DB/OL].http://www.ccf.org.cn/web/resource/haokegang.pdf，2007-08-01.

[2] 祁方民，魚濱，史立軍，等.基于Petri網(wǎng)的軟件項目管理建模方法[J].系統(tǒng)仿真學(xué)報，2007，19(S1):75-78.

[3] 袁崇義.Petri網(wǎng)原理與應(yīng)用[M].北京:電子工業(yè)出版社，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網(wǎng)共享PP-型子網(wǎng)合成性質(zhì)分析[J].軟件學(xué)報，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網(wǎng)的語義Web服務(wù)組合形式化驗證[J].清華大學(xué)學(xué)報(自然科學(xué)版)，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網(wǎng)的Web服務(wù)組合性能瓶頸定位策略[J].計算機學(xué)報，2013，36(10):1953-1966.

[11] 高翔，祝躍飛，劉勝利.一種基于廣義隨機著色Petri網(wǎng)的網(wǎng)絡(luò)攻擊組合模型[J].電子與信息學(xué)報，2013，35(11):2608-2614.

[12] 童曉陽，謝紅濤，孫明蔚.計及時序信息檢查的分層模糊Petri網(wǎng)電網(wǎng)故障診斷模型[J].電力系統(tǒng)自動化，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網(wǎng)化簡新技術(shù)研究[J].計算機工程與應(yīng)用，2012，48(5):47-50.

[15] 湯志偉，殷靜.基于擴展Petri網(wǎng)的仿真建模與分析[J].電子科技大學(xué)學(xué)報，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.