摘  要： 要想用Petri網(wǎng)對系統(tǒng)進(jìn)行有效的模擬和分析,，就必須先建立起可靠準(zhǔn)確的Petri網(wǎng)模型,，目前很少有文獻(xiàn)專門研究Petri網(wǎng)對系統(tǒng)的建模問題。對此,，提出了基于系統(tǒng)行為序列的Petri網(wǎng)自動建模方法,。該方法將系統(tǒng)所有行為序列組合為正規(guī)語言表達(dá)式，對于不同的系統(tǒng),，給出標(biāo)注函數(shù)（即變遷和系統(tǒng)行為的映射關(guān)系）,，就可以建立起系統(tǒng)的Petri網(wǎng)模型。給出了電話呼叫業(yè)務(wù)建立用戶Petri網(wǎng)模型的一個實例,。該方法形式化強,、通用性好，建立的模型標(biāo)準(zhǔn)規(guī)范,，并且可實現(xiàn)機器自動建模,，在目前的系統(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)對系統(tǒng)分析的文獻(xiàn)很多,，但在Petri網(wǎng)模型建立方面，大多文獻(xiàn)是通過對系統(tǒng)的理解憑借個人經(jīng)驗手工建立Petri網(wǎng)模型[1-2],。人工建立系統(tǒng)的Petri網(wǎng)模型,，特別是復(fù)雜系統(tǒng)的Petri網(wǎng)模型，不僅效率低,，而且其準(zhǔn)確性也值得商榷,，因此系統(tǒng)的Petri建模方法是一個非常值得研究的問題,。

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

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

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

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

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

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

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

　　定義3[7，8] 若N為一個恰當(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)生的語言,。

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

　　定理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ī)語言都可以由恰當(dāng)終結(jié)的標(biāo)準(zhǔn)Petri網(wǎng)產(chǎn)生。

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

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

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

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

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

　　（3）對系統(tǒng)行為序列表達(dá)式合并化簡,，使其形式盡量簡單,。

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

　?。?）給出網(wǎng)模型中庫所、變遷在被模擬系統(tǒng)中的實際含義,。

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

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

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

　?。?）運算優(yōu)先級為：,；

　　（2）從左向右運算,；

　?。?）先括號內(nèi),，后括號外。

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

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

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

　　輸出：產(chǎn)生語言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}

　　該算法可以實現(xiàn)機器對系統(tǒng)自動建立Petri網(wǎng)模型。

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

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

　　4.1 電話呼叫系統(tǒng)簡介

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

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

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

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

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

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

　?。?）總結(jié)電話呼叫系統(tǒng)中用戶行為。

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

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

　　①PickUp○HangUp

　?、赑ickUp○Dail○HangUp

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

　　④PickUp○Talk*○HangUp

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

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

　　PickUp○HangUp＋PickUp○Dail○HangUp＋PickUp

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

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

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

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

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

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

　　（6）給出用戶網(wǎng)模型Nuser的可達(dá)圖,，驗證網(wǎng)模型的正確性,。

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

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

5 結(jié)論

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

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

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

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

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

　　參考文獻(xiàn)

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

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

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

　　[4] 郝東，蔣昌俊,，林琳.基于Petri網(wǎng)與GA算法的FMS調(diào)度優(yōu)化[J].計算機學(xué)報,，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].計算機研究與發(fā)展,，2007，44（12）：2130-2135.

　　[7] 吳哲輝.Petri網(wǎng)導(dǎo)論[M].北京：機械工業(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].計算機工程,，2007,，33（17）：13-17.