摘  要： 要想用Petri網(wǎng)對(duì)系統(tǒng)進(jìn)行有效的模擬和分析，就必須先建立起可靠準(zhǔn)確的Petri網(wǎng)模型，目前很少有文獻(xiàn)專(zhuān)門(mén)研究Petri網(wǎng)對(duì)系統(tǒng)的建模問(wèn)題。對(duì)此，提出了基于系統(tǒng)行為序列的Petri網(wǎng)自動(dòng)建模方法。該方法將系統(tǒng)所有行為序列組合為正規(guī)語(yǔ)言表達(dá)式，對(duì)于不同的系統(tǒng)，給出標(biāo)注函數(shù)（即變遷和系統(tǒng)行為的映射關(guān)系），就可以建立起系統(tǒng)的Petri網(wǎng)模型。給出了電話(huà)呼叫業(yè)務(wù)建立用戶(hù)Petri網(wǎng)模型的一個(gè)實(shí)例。該方法形式化強(qiáng)、通用性好，建立的模型標(biāo)準(zhǔn)規(guī)范，并且可實(shí)現(xiàn)機(jī)器自動(dòng)建模，在目前的系統(tǒng)建模研究方面取得了進(jìn)展。

　　關(guān)鍵詞： 恰當(dāng)終結(jié)的標(biāo)準(zhǔn)Petri網(wǎng)；系統(tǒng)行為序列；正規(guī)表達(dá)式；建模

0 引言

　　Petri網(wǎng)是一種系統(tǒng)模擬與系統(tǒng)分析的工具，采用Petri網(wǎng)對(duì)系統(tǒng)分析的文獻(xiàn)很多，但在Petri網(wǎng)模型建立方面，大多文獻(xiàn)是通過(guò)對(duì)系統(tǒng)的理解憑借個(gè)人經(jīng)驗(yàn)手工建立Petri網(wǎng)模型[1-2]。人工建立系統(tǒng)的Petri網(wǎng)模型，特別是復(fù)雜系統(tǒng)的Petri網(wǎng)模型，不僅效率低，而且其準(zhǔn)確性也值得商榷，因此系統(tǒng)的Petri建模方法是一個(gè)非常值得研究的問(wèn)題。

　　目前用Petri網(wǎng)對(duì)各類(lèi)系統(tǒng)建模方面主要有以下研究成果。參考文獻(xiàn)[3]、[4]提出了使用Petri網(wǎng)子網(wǎng)為系統(tǒng)建模的方法，參考文獻(xiàn)[5]、[6]給出了對(duì)并行程序建立Petri網(wǎng)模型的方法。上述的各類(lèi)建模方法很大程度上減少了建模過(guò)程的重復(fù)性工作，提高了效率，并且使得模型有一定的規(guī)范性，但還存在一定問(wèn)題：（1）各類(lèi)系統(tǒng)有自己的基本模塊，建模方法不通用，如無(wú)法將并行程序的建模方法應(yīng)用于柔性制造系統(tǒng)中；（2）雖然采用模塊化方法提高了效率，但建模方法不太靈活，很多系統(tǒng)的動(dòng)態(tài)行為很復(fù)雜（如通信協(xié)議），不能或不易總結(jié)出其基本行為模塊的Petri網(wǎng)模型；（3）各個(gè)模塊組合的過(guò)程仍然需要人工干預(yù)，建模過(guò)程難以讓計(jì)算機(jī)自動(dòng)實(shí)現(xiàn)。

　　通過(guò)以上分析，本文提出了一種靈活性高、通用性強(qiáng)、嚴(yán)格、規(guī)范的Petri網(wǎng)自動(dòng)建模方法。該方法的基本思想是：對(duì)于待建模的系統(tǒng)，先總結(jié)出該系統(tǒng)所有的行為，系統(tǒng)所有的行為序列可以組合為一個(gè)語(yǔ)言的表達(dá)式。對(duì)于不同的系統(tǒng)，只要給出其行為序列表達(dá)式，就可以構(gòu)造一個(gè)帶有標(biāo)注的Petri網(wǎng)，使該P(yáng)etri網(wǎng)產(chǎn)生的語(yǔ)言就是系統(tǒng)行為序列表達(dá)式。因此，這種方法建立的模型就可以真實(shí)準(zhǔn)確地模擬系統(tǒng)的運(yùn)行。

　　各類(lèi)需要模擬的系統(tǒng)，其行為往往是有限的，系統(tǒng)的行為序列表達(dá)式也就限定在正規(guī)語(yǔ)言范圍內(nèi)，本文的建模方法是在正規(guī)語(yǔ)言范圍內(nèi)討論的。值得一提的是，本文在正規(guī)表達(dá)式中引入了并發(fā)算子“//”，該方法也就自然地解決了系統(tǒng)并發(fā)行為的建模。

1 基本概念和術(shù)語(yǔ)

　　這里僅給出與本文相關(guān)的基本概念，關(guān)于Petri網(wǎng)的原理請(qǐng)參閱參考文獻(xiàn)[7]、[8]。

　　定義1[7] 設(shè)N=（P，T；G，M0，，h，F(xiàn)）為一個(gè)標(biāo)準(zhǔn)Petri網(wǎng)，其中（P，T；G，M0）為一個(gè)Petri網(wǎng)，撞為有限字母表，h：T-?撞為標(biāo)注函數(shù)，F(xiàn)為終止?fàn)顟B(tài)集。

　　定義2p∈P-{pf}：M（p）=0，則稱(chēng)N為恰當(dāng)終結(jié)的標(biāo)準(zhǔn)Petri網(wǎng)。

　　定義3[7，8] 若N為一個(gè)恰當(dāng)終結(jié)的標(biāo)準(zhǔn)Petri網(wǎng)，（h可帶有ε-空標(biāo)注）為恰當(dāng)終結(jié)的標(biāo)準(zhǔn)Petri網(wǎng)產(chǎn)生的語(yǔ)言。

　　定理1[9] 恰當(dāng)終結(jié)的標(biāo)準(zhǔn)Petri網(wǎng)產(chǎn)生的語(yǔ)言為正規(guī)語(yǔ)言。

　　定理2[9] 若L1和L2可以由恰當(dāng)終結(jié)的標(biāo)準(zhǔn)Petri網(wǎng)產(chǎn)生，則L1○L2、L1∪L2、L1*、L1//L2都可以由恰當(dāng)終結(jié)的標(biāo)準(zhǔn)Petri網(wǎng)產(chǎn)生。

　　定理3[9] 正規(guī)語(yǔ)言都可以由恰當(dāng)終結(jié)的標(biāo)準(zhǔn)Petri網(wǎng)產(chǎn)生。

　　證明：由定理1、2可知，任給一個(gè)正規(guī)語(yǔ)言表達(dá)式都可以構(gòu)造出一個(gè)產(chǎn)生該正規(guī)語(yǔ)言的恰當(dāng)終結(jié)的標(biāo)準(zhǔn)Petri網(wǎng)。關(guān)于連接運(yùn)算“○”、選擇（并）運(yùn)算“∪”、Kleene閉包運(yùn)算“*”、并行運(yùn)算“//”的Petri網(wǎng)模型構(gòu)造方法參閱參考文獻(xiàn)[9]。

2 系統(tǒng)行為序列表達(dá)式的Petri網(wǎng)建模方法

　　根據(jù)定理1、2、3可知，任給一個(gè)正規(guī)語(yǔ)言的表達(dá)式，都可以方便地構(gòu)造出產(chǎn)生該表達(dá)式的Petri網(wǎng)模型。在對(duì)被模擬的系統(tǒng)建模時(shí)，首先根據(jù)系統(tǒng)的文本說(shuō)明或特性給出系統(tǒng)的各種行為序列，可以給每個(gè)行為（或者說(shuō)系統(tǒng)事件）起一個(gè)名字，這樣就相當(dāng)于得到系統(tǒng)的行為序列表達(dá)式，如果該表達(dá)式是一個(gè)正規(guī)表達(dá)式就可以直接構(gòu)造出Petri網(wǎng)模型。系統(tǒng)行為序列表達(dá)式的Petri網(wǎng)建模具體方法如下：

　?。?）根據(jù)待建模系統(tǒng)的性質(zhì)或是文本說(shuō)明，給出系統(tǒng)所有的行為，為每個(gè)行為起一個(gè)恰當(dāng)?shù)拿Q(chēng)。

　?。?）給出系統(tǒng)各種可能的行為序列，構(gòu)建系統(tǒng)行為序列的表達(dá)式。

　?。?）對(duì)系統(tǒng)行為序列表達(dá)式合并化簡(jiǎn)，使其形式盡量簡(jiǎn)單。

　　（4）利用定理3對(duì)化簡(jiǎn)后的系統(tǒng)行為序列表達(dá)式構(gòu)造Petri網(wǎng)模型。

　　（5）給出網(wǎng)模型中庫(kù)所、變遷在被模擬系統(tǒng)中的實(shí)際含義。

　?。?）驗(yàn)證與修改（如果需要）。給出網(wǎng)模型的可達(dá)圖，得到變遷發(fā)生序列H（?滓），將H（?滓）與步驟（2）中的行為序列進(jìn)行比較，若一致，說(shuō)明網(wǎng)模型正確；否則，修改網(wǎng)模型。

3 基于系統(tǒng)行為序列的Petri網(wǎng)建模方法的機(jī)器自動(dòng)實(shí)現(xiàn)

　　首先要了解正規(guī)表達(dá)式關(guān)于連接“○”、并“∪”、閉包“*”、并行“//”運(yùn)算的運(yùn)算規(guī)則，即：

　　（1）運(yùn)算優(yōu)先級(jí)為：；

　　（2）從左向右運(yùn)算；

　?。?）先括號(hào)內(nèi)，后括號(hào)外。

　　具體優(yōu)先關(guān)系如表1所示。

　　算法1 系統(tǒng)序列表達(dá)式轉(zhuǎn)化為Petri網(wǎng)模型的算符優(yōu)先算法

　　輸入：被模擬系統(tǒng)行為序列的正規(guī)表達(dá)式E

　　輸出：產(chǎn)生語(yǔ)言L（E）的恰當(dāng)終結(jié)的標(biāo)準(zhǔn)Petri網(wǎng)模型即被建模系統(tǒng)的Petri網(wǎng)模型

　　FUNC Regular_transition_exp to Petri net

　　INISTACK（OPTR）；PUSH（OPTR，“#”）；INISTACK（OPND）；

　　Read（w）；{read a character from expression E}

　　While NOT（（w=“#”）AND（GETTOP（OPTR）=“#”））Do

　　IF w NOT  IN op THEN

　　[PUSH（OPND，w）；Create（net w）；]

　　ELSE CASE precede（GETTOP（OPTR），w）OF

　　“<”：[PUSH（OPTR，w）；read（w）]；

　　“=”：[x：=POP（OPTR）；read（w）]；

　　“>”：[theta：=POP（OPTR）；

　　IF theta=“*”THEN [c=POP（OPND）；

　　s：=c*；PUSH（OPND，s）；Unite（net c）]

　　ELSE[b：=POP（OPND）；a：=POP（OPND）；

　　s：=operate（a，theta，b）；PUSH（OPND，s）；

　　Unite（net a，theta，net b）]

　　ENDC（end case）；

　　RETURN（GETTOP（OPND），net GETTOP（OPND））

　　ENDF；{exp_reduced}

　　該算法可以實(shí)現(xiàn)機(jī)器對(duì)系統(tǒng)自動(dòng)建立Petri網(wǎng)模型。

4 基于行為序列表達(dá)式的Petri網(wǎng)建模方法實(shí)例

　　本節(jié)給出基于協(xié)議實(shí)體行為序列表達(dá)式的Petri網(wǎng)建模方法的一個(gè)實(shí)例，對(duì)電信系統(tǒng)的電話(huà)呼叫業(yè)務(wù)建立用戶(hù)Petri網(wǎng)模型，模擬用戶(hù)打電話(huà)的過(guò)程。

　　4.1 電話(huà)呼叫系統(tǒng)簡(jiǎn)介

　　系統(tǒng)的模型如圖1所示。

　?。?）用戶(hù)：用戶(hù)可以發(fā)起或接受呼叫，即要么是呼叫者要么是被叫者，如果是呼叫者，可以拿起電話(huà)并播出號(hào)碼；如果是被叫者，當(dāng)鈴聲響起，可以接通電話(huà)。不管是呼叫者還是被叫者，用戶(hù)可以隨時(shí)掛斷電話(huà)。

　?。?）電話(huà)：也可以稱(chēng)為終端，是用戶(hù)和網(wǎng)絡(luò)的接口，使用終端，用戶(hù)可以撥出或接入呼叫。

　?。?）網(wǎng)絡(luò)：由交換機(jī)和線路組成，交換機(jī)控制兩個(gè)用戶(hù)之間連接的建立和釋放以及管理線路。

　　4.2電話(huà)呼叫系統(tǒng)的用戶(hù)Petri網(wǎng)模型

　　系統(tǒng)行為序列表達(dá)式的Petri網(wǎng)建模方法如下。

　　（1）總結(jié)電話(huà)呼叫系統(tǒng)中用戶(hù)行為。

　　（2）給出在電話(huà)呼叫系統(tǒng)中用戶(hù)所有可能的行為序列，構(gòu)建系統(tǒng)行為序列的表達(dá)式。

　　呼叫者所有可能的行為序列如下：①拿起話(huà)筒，掛機(jī)。②拿起話(huà)筒，撥號(hào)，掛機(jī)。③拿起話(huà)筒，撥號(hào)，建立連接，雙方通話(huà)，掛機(jī)。第三種情況是通話(huà)雙方正常的通話(huà)過(guò)程，第二種情況可能是被叫方占線，第一種情況可能是呼叫者不想呼叫被叫方了。再來(lái)考慮被呼叫者的所有可能行為：④拿起話(huà)筒，雙方通話(huà)，掛機(jī)。綜上所述，電話(huà)呼叫系統(tǒng)中用戶(hù)所有可能的行為序列如下：

　?、貾ickUp○HangUp

　?、赑ickUp○Dail○HangUp

　?、跴ickUp○Dail○Connect○Talk*○HangUp

　?、躊ickUp○Talk*○HangUp

　?。?）對(duì)系統(tǒng)行為序列表達(dá)式合并化簡(jiǎn)，使其形式盡量簡(jiǎn)單。

　　顯然，步驟（2）中得出的4個(gè)式子是正規(guī)表達(dá)式，所以電話(huà)呼叫系統(tǒng)中用戶(hù)所有可能的行為序列表示為：

　　PickUp○HangUp＋PickUp○Dail○HangUp＋PickUp

　　○Dail○Connect○Talk*○HangUp+PickUp○Talk*○HangUp（1）

　　根據(jù)正規(guī)表達(dá)式的運(yùn)算性質(zhì)，將式（1）化簡(jiǎn)，得：

　　PickUp○（HangUp＋Dail（HangUp＋Connect○Talk*○HangUp））+PickUp○Talk*○HangUp（2）

　　式（2）中沒(méi)有合并步驟（2）中的④，這是因?yàn)棰?、②、③是呼叫者的行為，④是被呼叫者的行為，不合并④中的PickUp可以使模型更清楚地表達(dá)各自的行為。

　?。?）利用定理3和算法1對(duì)化簡(jiǎn)后的系統(tǒng)行為序列表達(dá)式構(gòu)造Petri網(wǎng)模型，如圖2所示。

　?。?）給出網(wǎng)模型中庫(kù)所、變遷在被模擬系統(tǒng)中的實(shí)際含義，如表2所示。

　?。?）給出用戶(hù)網(wǎng)模型Nuser的可達(dá)圖，驗(yàn)證網(wǎng)模型的正確性。

　　從圖2可以看出，從初始狀態(tài)M0到終止?fàn)顟B(tài)M4有4條路徑，即：

　　它們對(duì)應(yīng)的變遷發(fā)生序列為：這與步驟（2）中總結(jié)的用戶(hù)行為序列是一致的，這說(shuō)明圖2電話(huà)呼叫系統(tǒng)的用戶(hù)Petri網(wǎng)模型是正確的。

5 結(jié)論

　　目前專(zhuān)門(mén)研究Petri網(wǎng)系統(tǒng)建模特別是自動(dòng)化建模的文獻(xiàn)很少。本文在分析現(xiàn)有的方法后，提出了基于系統(tǒng)行為序列的Petri網(wǎng)自動(dòng)建模方法。該方法靈活性高、通用性強(qiáng)、嚴(yán)格、規(guī)范，同以往的方法相比，具有以下優(yōu)勢(shì)：

　　（1）該方法具有嚴(yán)格的理論依據(jù)，建模過(guò)程標(biāo)準(zhǔn)規(guī)范。在描述系統(tǒng)行為時(shí)采用正規(guī)表達(dá)式，在建模過(guò)程中網(wǎng)模型始終保持恰當(dāng)終結(jié)的標(biāo)準(zhǔn)Petri網(wǎng)，每一步都采用正規(guī)表達(dá)式的連接運(yùn)算“?莓”、并運(yùn)算“∪”、Kleene閉包運(yùn)算“*”、并行運(yùn)算“//”等標(biāo)準(zhǔn)算子。這使得建模過(guò)程可以采用遞歸的方法實(shí)現(xiàn)，最終構(gòu)造出的系統(tǒng)Petri網(wǎng)模型仍符合恰當(dāng)終結(jié)的標(biāo)準(zhǔn)Petri網(wǎng)。

　?。?）該建模方法通用性較強(qiáng)，可以應(yīng)用于較多領(lǐng)域，如程序驗(yàn)證、協(xié)議驗(yàn)證、柔性制造系統(tǒng)、離散事件模型、Web服務(wù)組合等。對(duì)于不同的系統(tǒng)只要給出系統(tǒng)行為和Petri變遷的對(duì)應(yīng)關(guān)系（即h：T-?撞標(biāo)注函數(shù)），均可以采用該方法建立Petri網(wǎng)模型。

　　（3）該方法形式化很強(qiáng)，構(gòu)造出的系統(tǒng)Petri網(wǎng)模型簡(jiǎn)單準(zhǔn)確，因而可以實(shí)現(xiàn)機(jī)器對(duì)系統(tǒng)的自動(dòng)建模。文中并給出了易于機(jī)器自動(dòng)實(shí)現(xiàn)的建模算法。

　　綜上所述，本文提出的方法在目前的系統(tǒng)建模研究方面取得了進(jìn)展，有較好的理論和實(shí)際應(yīng)用價(jià)值。

　　參考文獻(xiàn)

　　[1] 王燕，李華，周建濤.基于Petri網(wǎng)的移動(dòng)IPSec快速切換的建模與分析[J].計(jì)算機(jī)研究與發(fā)展，2012，49（1）：82-88.

　　[2] 劉繼承，張愛(ài)茹，李征鴻.基于Petri網(wǎng)的文件審批系統(tǒng)工作流建模[J].微型機(jī)與應(yīng)用，2013，32（2）：77-80.

　　[3] 蘇桂平，孫莎.一種基于有色Petri網(wǎng)的安全協(xié)議分析方法研究[J].微型機(jī)與應(yīng)用，2011，30（15）：1-3.

　　[4] 郝東，蔣昌俊，林琳.基于Petri網(wǎng)與GA算法的FMS調(diào)度優(yōu)化[J].計(jì)算機(jī)學(xué)報(bào)，2005，28（2）：202-208.

　　[5] Zhang Peng， Qi Mei. Modeling parallel MPI programs in Petri nets[C]. Instrumentation， Measurement， Circuits and Systems Advances in Intelligent and Soft Computing， Berlin： Springer， 2012，127：829-836.

　　[6] 崔煥慶，吳哲輝.并行程序Petri網(wǎng)模型的結(jié)構(gòu)性質(zhì)[J].計(jì)算機(jī)研究與發(fā)展，2007，44（12）：2130-2135.

　　[7] 吳哲輝.Petri網(wǎng)導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2006.

　　[8] 袁崇義.Petri網(wǎng)原理與應(yīng)用[M].北京：電子工業(yè)出版社，2005.

　　[9] 范昊，吳哲輝.正規(guī)表達(dá)式與恰當(dāng)終結(jié)的標(biāo)準(zhǔn)Petri網(wǎng)[J].計(jì)算機(jī)工程，2007，33（17）：13-17.