摘  要： 要想用Petri網(wǎng)對系統(tǒng)進(jìn)行有效的模擬和分析，就必須先建立起可靠準(zhǔn)確的Petri網(wǎng)模型,，目前很少有文獻(xiàn)專門研究Petri網(wǎng)對系統(tǒng)的建模問題,。對此,，提出了基于系統(tǒng)行為序列的Petri網(wǎng)自動(dòng)建模方法。該方法將系統(tǒng)所有行為序列組合為正規(guī)語言表達(dá)式,，對于不同的系統(tǒng),，給出標(biāo)注函數(shù)（即變遷和系統(tǒng)行為的映射關(guān)系），就可以建立起系統(tǒng)的Petri網(wǎng)模型,。給出了電話呼叫業(yè)務(wù)建立用戶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)對系統(tǒng)分析的文獻(xiàn)很多，但在Petri網(wǎng)模型建立方面,，大多文獻(xiàn)是通過對系統(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è)非常值得研究的問題,。

　　目前用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)的動(dòng)態(tài)行為很復(fù)雜（如通信協(xié)議），不能或不易總結(jié)出其基本行為模塊的Petri網(wǎng)模型,；（3）各個(gè)模塊組合的過程仍然需要人工干預(yù),，建模過程難以讓計(jì)算機(jī)自動(dòng)實(shí)現(xiàn)。

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

　　各類需要模擬的系統(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)）為一個(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,，則稱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)生的語言。

　　定理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可知，任給一個(gè)正規(guī)語言表達(dá)式都可以構(gòu)造出一個(gè)產(chǎn)生該正規(guī)語言的恰當(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ī)語言的表達(dá)式，都可以方便地構(gòu)造出產(chǎn)生該表達(dá)式的Petri網(wǎng)模型,。在對被模擬的系統(tǒng)建模時(shí),，首先根據(jù)系統(tǒng)的文本說明或特性給出系統(tǒng)的各種行為序列，可以給每個(gè)行為（或者說系統(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ì)或是文本說明,，給出系統(tǒng)所有的行為，為每個(gè)行為起一個(gè)恰當(dāng)?shù)拿Q,。

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

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

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

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

　　（6）驗(yàn)證與修改（如果需要）,。給出網(wǎng)模型的可達(dá)圖，得到變遷發(fā)生序列H（?滓）,，將H（?滓）與步驟（2）中的行為序列進(jìn)行比較,，若一致，說明網(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ī)則,，即：

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

　?。?）從左向右運(yùn)算,；

　　（3）先括號內(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}

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

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

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

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

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

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

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

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

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

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

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

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

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

　?、貾ickUp○HangUp

　　②PickUp○Dail○HangUp

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

　?、躊ickUp○Talk*○HangUp

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

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

　　PickUp○HangUp＋PickUp○Dail○HangUp＋PickUp

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

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

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

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

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

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

　?。?）給出用戶網(wǎng)模型Nuser的可達(dá)圖,，驗(yàn)證網(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)建模特別是自動(dòng)化建模的文獻(xiàn)很少,。本文在分析現(xiàn)有的方法后，提出了基于系統(tǒng)行為序列的Petri網(wǎng)自動(dòng)建模方法,。該方法靈活性高,、通用性強(qiáng)、嚴(yán)格,、規(guī)范,，同以往的方法相比，具有以下優(yōu)勢：

　?。?）該方法具有嚴(yán)格的理論依據(jù),，建模過程標(biāo)準(zhǔn)規(guī)范。在描述系統(tǒng)行為時(shí)采用正規(guī)表達(dá)式,，在建模過程中網(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)算子。這使得建模過程可以采用遞歸的方法實(shí)現(xiàn),，最終構(gòu)造出的系統(tǒng)Petri網(wǎng)模型仍符合恰當(dāng)終結(jié)的標(biāo)準(zhǔn)Petri網(wǎng),。

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

　　（3）該方法形式化很強(qiáng),，構(gòu)造出的系統(tǒng)Petri網(wǎng)模型簡單準(zhǔn)確,，因而可以實(shí)現(xiàn)機(jī)器對系統(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] 劉繼承，張愛茹,，李征鴻.基于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.