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

　　關鍵詞： 恰當終結的標準Petri網(wǎng)；系統(tǒng)行為序列；正規(guī)表達式；建模

0 引言

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

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

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

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

1 基本概念和術語

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

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

　　定義2p∈P-{pf}：M（p）=0，則稱N為恰當終結的標準Petri網(wǎng)。

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

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

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

　　定理3[9] 正規(guī)語言都可以由恰當終結的標準Petri網(wǎng)產(chǎn)生。

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

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

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

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

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

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

　?。?）利用定理3對化簡后的系統(tǒng)行為序列表達式構造Petri網(wǎng)模型。

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

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

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

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

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

　　（2）從左向右運算；

　?。?）先括號內，后括號外。

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

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

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

　　輸出：產(chǎn)生語言L（E）的恰當終結的標準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 基于行為序列表達式的Petri網(wǎng)建模方法實例

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

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

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

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

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

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

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

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

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

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

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

　?、貾ickUp○HangUp

　　②PickUp○Dail○HangUp

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

　　④PickUp○Talk*○HangUp

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

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

　　PickUp○HangUp＋PickUp○Dail○HangUp＋PickUp

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

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

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

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

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

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

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

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

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

5 結論

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

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

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

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

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

　　參考文獻

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

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

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

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

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

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

　　[9] 范昊，吳哲輝.正規(guī)表達式與恰當終結的標準Petri網(wǎng)[J].計算機工程，2007，33（17）：13-17.