祁方民

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

定義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的庫(kù)所(place)集和變遷(transition)集，F(xiàn)為流關(guān)系(flow relation);庫(kù)所集和變遷集是有向網(wǎng)的基本成分，流關(guān)系是從中構(gòu)造出來(lái)的，而連接S和T中元素的叫做弧(arc)，弧是F中的元素，所以弧只能連接庫(kù)所和變遷，不能連接2個(gè)庫(kù)所或者是2個(gè)變遷。

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

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

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

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

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

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

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

圖1 庫(kù)所結(jié)點(diǎn)精化實(shí)例

圖2 變遷結(jié)點(diǎn)精化實(shí)例

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

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

3.1 庫(kù)所

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

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

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

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

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

3.2 變遷

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

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

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

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

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

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

3.3 Token

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

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

定義4 庫(kù)所結(jié)點(diǎn)s包含一個(gè)Token集合R，則:

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

3.4 弧與權(quán)

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

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

4 正確性證明

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

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

定義6

如果一個(gè)結(jié)點(diǎn)精化的Petri網(wǎng)N在實(shí)際建模過(guò)程中沒(méi)有結(jié)點(diǎn)進(jìn)行精化，則其精化層數(shù)為0;

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

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

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

下面給出證明。

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

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

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

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

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

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

同時(shí)可以利用結(jié)點(diǎn)精化方法解決建模過(guò)程中引起的結(jié)點(diǎn)爆炸問(wèn)題。

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

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

6 結(jié)束語(yǔ)

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

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

[2] 祁方民，魚(yú)濱，史立軍，等.基于Petri網(wǎng)的軟件項(xiàng)目管理建模方法[J].系統(tǒng)仿真學(xué)報(bào)，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é)報(bào)，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)的語(yǔ)義Web服務(wù)組合形式化驗(yàn)證[J].清華大學(xué)學(xué)報(bào)(自然科學(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] 何炎祥，沈華.一種基于隨機(jī)Petri網(wǎng)的Web服務(wù)組合性能瓶頸定位策略[J].計(jì)算機(jī)學(xué)報(bào)，2013，36(10):1953-1966.

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

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

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