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

　　關鍵詞： 恰當終結的標準Petri網；系統行為序列；正規表達式；建模

0 引言

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

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

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

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

1 基本概念和術語

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

　　定義1[7] 設N=（P，T；G，M0，，h，F）為一個標準Petri網，其中（P，T；G，M0）為一個Petri網，撞為有限字母表，h：T-?撞為標注函數，F為終止狀態集。

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

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

　　定理1[9] 恰當終結的標準Petri網產生的語言為正規語言。

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

　　定理3[9] 正規語言都可以由恰當終結的標準Petri網產生。

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

2 系統行為序列表達式的Petri網建模方法

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

　?。?）根據待建模系統的性質或是文本說明，給出系統所有的行為，為每個行為起一個恰當的名稱。

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

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

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

　?。?）給出網模型中庫所、變遷在被模擬系統中的實際含義。

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

3 基于系統行為序列的Petri網建模方法的機器自動實現

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

　?。?）運算優先級為：；

　　（2）從左向右運算；

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

　　具體優先關系如表1所示。

　　算法1 系統序列表達式轉化為Petri網模型的算符優先算法

　　輸入：被模擬系統行為序列的正規表達式E

　　輸出：產生語言L（E）的恰當終結的標準Petri網模型即被建模系統的Petri網模型

　　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}

　　該算法可以實現機器對系統自動建立Petri網模型。

4 基于行為序列表達式的Petri網建模方法實例

　　本節給出基于協議實體行為序列表達式的Petri網建模方法的一個實例，對電信系統的電話呼叫業務建立用戶Petri網模型，模擬用戶打電話的過程。

　　4.1 電話呼叫系統簡介

　　系統的模型如圖1所示。

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

　　（2）電話：也可以稱為終端，是用戶和網絡的接口，使用終端，用戶可以撥出或接入呼叫。

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

　　4.2電話呼叫系統的用戶Petri網模型

　　系統行為序列表達式的Petri網建模方法如下。

　?。?）總結電話呼叫系統中用戶行為。

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

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

　　①PickUp○HangUp

　?、赑ickUp○Dail○HangUp

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

　?、躊ickUp○Talk*○HangUp

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

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

　　PickUp○HangUp＋PickUp○Dail○HangUp＋PickUp

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

　　根據正規表達式的運算性質，將式（1）化簡，得：

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

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

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

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

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

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

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

5 結論

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

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

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

　　（3）該方法形式化很強，構造出的系統Petri網模型簡單準確，因而可以實現機器對系統的自動建模。文中并給出了易于機器自動實現的建模算法。

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

　　參考文獻

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

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

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

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

　　[7] 吳哲輝.Petri網導論[M].北京：機械工業出版社，2006.

　　[8] 袁崇義.Petri網原理與應用[M].北京：電子工業出版社，2005.

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