流體隨機(jī)Petri網(wǎng)的混雜自動(dòng)機(jī)模型

1、流體隨機(jī)Petri網(wǎng)的混雜自動(dòng)機(jī)模型近年來,Petri網(wǎng)正逐漸成為描述和分析那些具有同步、并發(fā)和沖突等特征的離散事件動(dòng)態(tài)系統(tǒng)的有力工具,在柔性制造系統(tǒng)、計(jì)算機(jī)及通訊系統(tǒng)等領(lǐng)域都得到了廣泛的應(yīng)用.然而,許多系統(tǒng)本質(zhì)上是混雜的,混合系統(tǒng)由離散子系統(tǒng)和連續(xù)子系統(tǒng)組成,且連續(xù)和離散部分相互作用,對(duì)這類系統(tǒng)的建模,傳統(tǒng)的Petri網(wǎng)其離散的本質(zhì)對(duì)此無能為力.另一方面,Petri網(wǎng)的標(biāo)識(shí)可達(dá)集隨所含元素?cái)?shù)呈指數(shù)增長(zhǎng),容易產(chǎn)生狀態(tài)空間爆炸問題.為了解決狀態(tài)空間爆炸問題及用Petri網(wǎng)建?；旌舷到y(tǒng),混雜Petri網(wǎng)(Hybrid Petri nets)和流體隨機(jī)Petri網(wǎng)(Fluid stochastic

2、Petri nets)先后被提出,并得到了成功的應(yīng)用1.流體隨機(jī)Petri網(wǎng)是將在通信及制造系統(tǒng)建模中使用的隨機(jī)流體模型引入到廣義隨機(jī)Petri網(wǎng)(Generalized stochastic Petri nets)而得到的,首先被T rivedi和Kulka提出2,隨后文獻(xiàn)3-4對(duì)流體隨機(jī)Petri網(wǎng)進(jìn)行了進(jìn)一步的拓展.通過建立描述隨機(jī)標(biāo)識(shí)過程狀態(tài)的動(dòng)態(tài)方程,用數(shù)值方法求出系統(tǒng)的性能量度,從而實(shí)現(xiàn)流體隨機(jī)Petri網(wǎng)模型的分析,但數(shù)值方法不易實(shí)現(xiàn)系統(tǒng)有無死鎖、系統(tǒng)是否安全等等一些性質(zhì)的判定及FSPN模型的驗(yàn)證.本文通過構(gòu)造流體隨機(jī)Petri網(wǎng)的一階混雜Petri網(wǎng)及混雜自動(dòng)機(jī)模型以借助一階混

3、雜Petri網(wǎng)的行為演變圖及混雜自動(dòng)機(jī)的驗(yàn)證技術(shù)和工具實(shí)現(xiàn)流體隨機(jī)Petri網(wǎng)模型的分析與驗(yàn)證,主要工作包括:(1)介紹了由FSPN轉(zhuǎn)換為一階混雜Petri網(wǎng)的形式化方法;(2)給出了一階混雜Petri網(wǎng)模型的混雜自動(dòng)機(jī)模型的構(gòu)造方法;(3)通過實(shí)例分析與驗(yàn)證說明了利用流體隨機(jī)Petri網(wǎng)的一階混雜Petri網(wǎng)及混雜自動(dòng)機(jī)模型能夠有效地實(shí)現(xiàn)流體隨機(jī)Petri網(wǎng)的分析與驗(yàn)證.1FSPN的一階混雜Petri網(wǎng)形式化轉(zhuǎn)換方法5Becker和Bessey首先對(duì)兩種Petri網(wǎng)的建模能力進(jìn)行了比較,結(jié)果發(fā)現(xiàn)這兩種Petri網(wǎng)模型之間可以相互模擬1.文獻(xiàn)6也討論了這兩種Petri網(wǎng)的定義、連續(xù)標(biāo)識(shí)、分析方

4、法以及相互轉(zhuǎn)換的可能性.然而上述文獻(xiàn)均未給出兩者之間轉(zhuǎn)換的形式化描述,也未對(duì)其轉(zhuǎn)換的正確性進(jìn)行證明.為此文獻(xiàn)5給出了流體隨機(jī)Petri網(wǎng)轉(zhuǎn)換成一階混雜Petri網(wǎng)的形式化描述方法.對(duì)于給定的FSPN,通過確定與之等價(jià)的一階混雜Petri網(wǎng)的離散庫(kù)所、連續(xù)庫(kù)所、離散遷移、連續(xù)遷移,建立遷移與庫(kù)所之間的弧及其權(quán)重,確定連續(xù)遷移的引發(fā)速率區(qū)間等等,從而實(shí)現(xiàn)FSPN的一階混雜Petri網(wǎng)模型的求解.同時(shí)對(duì)其轉(zhuǎn)換的正確性進(jìn)行證明.詳細(xì)內(nèi)容見文獻(xiàn)5,在此不再贅述.2基于一階混雜Petri網(wǎng)的FSPN的混雜自動(dòng)機(jī)模型2.1一階混雜Petri網(wǎng)模型行為演變算法把FSPN轉(zhuǎn)換成一階混雜Petri網(wǎng)后,就可以借助

5、一階混雜Petri網(wǎng)的模型分析技術(shù)來實(shí)現(xiàn)流體隨機(jī)Petri網(wǎng)模型的分析與驗(yàn)證.由于混雜Petri網(wǎng)的連續(xù)庫(kù)所標(biāo)識(shí)的為實(shí)數(shù),因此混雜Petri網(wǎng)不能象離散Pe-tri網(wǎng)那樣可通過構(gòu)造可達(dá)樹來分析模型的動(dòng)態(tài)行為.通過定義不變行為狀態(tài)(Invariant behavior state)構(gòu)造模型動(dòng)態(tài)演變圖是混雜Petri網(wǎng)一種重要的也是有效的分析方法,混雜Petri網(wǎng)模型行為演變的求解過程是一個(gè)確定不變行為(Invariant behavior,IB)狀態(tài)及確定改變不變行為狀態(tài)事件的過程.文獻(xiàn)7首先給出了一階混雜Petri網(wǎng)模型行為演變的求解過程,但求解過程在改變IB狀態(tài)事件之間的產(chǎn)生相互作用情形下是

6、不正確的8,為此本文利用文獻(xiàn)8確定IB狀態(tài)事件的方法給出一階混雜Petri網(wǎng)模型行為演變的求解過程.算法1一階混雜Petri網(wǎng)模型行為演變算法輸入:一階混雜Petri網(wǎng)模型,輸出:模型行為演變.方法如下:步驟1:初始化一階混雜Petri網(wǎng)模型參數(shù);步驟2:若模型符合一階混雜Petri網(wǎng)模型則轉(zhuǎn)到步驟3,否則返回步驟1修改參數(shù);步驟3:i=0,i=0,初始化md(i)和mc(i);步驟4:根據(jù)文獻(xiàn)7的公式(5)計(jì)算可行瞬時(shí)引發(fā)速率集S(N,m(i);步驟5:根據(jù)引發(fā)模式從S(N,m(i)中選一引發(fā)速率向量v,令v(i)=v;步驟6:在不考慮改變IB狀態(tài)事件間相互作用的情況下按文獻(xiàn)8方法求解改變I

7、B狀態(tài)事件集E-VENT_SET;步驟7:基于EVENT_SET,根據(jù)文獻(xiàn)8的表1,2確定改變第i個(gè)IB狀態(tài)(IBi)的事件eventi;若無改變IB狀態(tài)的事件,則轉(zhuǎn)至步驟12;步驟8:根據(jù)eventi確定IBi的時(shí)間區(qū)間i,i+1;步驟9:i=i+1;步驟10:mc(i*)=mc(i-1)+Cccv(i)(i-i-1),mc(i)=mc(i*)+Ccd(i),md(i)=md(i-1)+Cdd(i);步驟11:檢查是否存在m(j)(0ji-1),使得m(j)=m(i),若存在演變結(jié)束,否則轉(zhuǎn)至步驟4;步驟12:算法結(jié)束.根據(jù)上一節(jié)的形式化轉(zhuǎn)換的方法可把FSPN轉(zhuǎn)換成一階混雜Petri網(wǎng),然后

8、利用算法1可求出一階混雜Petri網(wǎng)的行為演變過程,根據(jù)演變過程就能夠借助一階混雜Petri網(wǎng)來實(shí)現(xiàn)FSPN的分析與檢驗(yàn),具體的實(shí)例見第3節(jié).2.2一階混雜Petri網(wǎng)模型行為演變的混雜自動(dòng)機(jī)模型一階混雜Petri網(wǎng)的行為演變過程并不能提供FSPN模型分析與檢驗(yàn)的所有結(jié)果,為了能對(duì)FSPN模型行為進(jìn)行有效地分析,本節(jié)借鑒文獻(xiàn)9的方法在算法1的基礎(chǔ)上給出構(gòu)造一階混雜Petri網(wǎng)行為演變的混雜自動(dòng)機(jī)模型,從而可以借助混雜自動(dòng)機(jī)的驗(yàn)證技術(shù)實(shí)現(xiàn)FSPN模型的分析.2.2.1混雜自動(dòng)機(jī)9-10定義1混雜自動(dòng)機(jī)是一個(gè)七元組HA=,其中X是實(shí)變量有限集合,其中用x來表示變量向量,并用V來表示變量狀態(tài)集;Q為

9、有限離散位置集;為描述變量隨時(shí)間變化的函數(shù):l(x,f):.x(f)=f(x,f);Inv為描述庫(kù)所變遷條件的函數(shù);A為有限遷移集合;Ev為描述遷移引發(fā)條件的函數(shù),若遷移為a=(l,l1),引發(fā)條件記為Eva,即當(dāng)Eva條件得到滿足,則遷移a可引發(fā);As為遷移的分配函數(shù),每個(gè)遷移a的分配Asa用來描述變量的離散變化:Asa:x:=g(x).2.2.2行為演變的混雜自動(dòng)機(jī)模型構(gòu)造算法行為演變的混雜自動(dòng)機(jī)的變量包含兩部分:每個(gè)庫(kù)所pi的標(biāo)識(shí)mi以及最小的0級(jí)使能遷移延時(shí)yi;行為演變的混雜自動(dòng)機(jī)的位置包含兩部分:.mi=庫(kù)所pi的動(dòng)態(tài)平衡量Bi;.yi=時(shí)鐘變化的單位;行為演變的混雜自動(dòng)機(jī)的遷移標(biāo)

10、簽包含兩部分:一部分是遷移引發(fā)的條件,對(duì)應(yīng)于改變演變圖中區(qū)域狀態(tài)的事件;另一部分是各個(gè)庫(kù)所標(biāo)識(shí)在遷移引發(fā)后變化的情況,不妨稱為演變向量.設(shè)E為演變向量集,Vk為位置lk的變量集,Q、A分別為位置級(jí)和遷移集.下面給出構(gòu)造一階混雜Petri網(wǎng)行為演變的混雜自動(dòng)機(jī)模型的算法.算法2一階混雜Petri網(wǎng)行為演變的混雜自動(dòng)機(jī)模型構(gòu)造算法輸入:指定的一階混雜Petri網(wǎng)及引發(fā)模式,輸出:混雜自動(dòng)機(jī).具體方法如下:步驟1:計(jì)算初始演變向量集E1和構(gòu)造與之相關(guān)聯(lián)的位置l1:E1=各個(gè)庫(kù)所的初始標(biāo)識(shí);根據(jù)算法1及指定的引發(fā)模式確定在E1下位置l1中的變量集V1;構(gòu)建指向位置l1的遷移,其標(biāo)簽為E1;令E=EE1

11、,Q=Ql1.步驟2:若有改變IB狀態(tài)的事件event發(fā)生,則轉(zhuǎn)至步驟3,否則轉(zhuǎn)至步驟4.步驟3:根據(jù)引發(fā)規(guī)則及引發(fā)模式計(jì)算事件發(fā)生后的Ek+1,若E中已包含有Ek+1則轉(zhuǎn)至步驟2,否則按如下方法運(yùn)行:1)令E=EEk+1,按步驟1中的方法構(gòu)造新位置lk+1及位置中的變量集Vk+1,令Q=Qlk+1.構(gòu)造引發(fā)條件為event的遷移a(lk,lk+1),令A(yù)=Aa(lk,lk+1),k=k+1,轉(zhuǎn)至步驟2.2)設(shè)Ek+1與位置ls相關(guān)聯(lián).若遷移a(ls,lk+1)的引發(fā)條件亦為event,則轉(zhuǎn)至(ii),否則按如下方法運(yùn)行:(i)構(gòu)造引發(fā)條件為event的遷移a(lk,ls),令A(yù)=Aa(lk,

12、ls).(ii)根據(jù)算法1及指定的引發(fā)模式確定在Ek+1下位置ls中的變量集Vs1,若Vs1 Vs,轉(zhuǎn)至步驟4,否則轉(zhuǎn)至步驟2.步驟4:算法結(jié)束.上述算法在一階混雜Petri網(wǎng)為有界的情況下能夠正常終止.由于無界的一階混雜Petri網(wǎng)表明系統(tǒng)不具穩(wěn)定性,而對(duì)于不穩(wěn)定系統(tǒng)的性質(zhì)不作討論.3FSPN模型檢驗(yàn)實(shí)例實(shí)例1考察文獻(xiàn)2的某生產(chǎn)系統(tǒng)的FSPN模型.通過建立微分方程可利用數(shù)值分析方法對(duì)該系統(tǒng)的一些性能進(jìn)行分析,但數(shù)值方法的有效性僅局限于連續(xù)庫(kù)所為較少的情況且不能對(duì)系統(tǒng)有無死鎖、系統(tǒng)各個(gè)操作周期及系統(tǒng)是否安全等進(jìn)行分析,為此首先把FSPN模型轉(zhuǎn)化為與之等價(jià)的一階混雜Petri網(wǎng)模型如圖1,然后通

13、過一階混雜Petri網(wǎng)的演變圖來進(jìn)行分析.圖1FSPN的一階混雜Petri網(wǎng)模型Fig.1The first-order hybrid Petri nets modle of FSPN圖2演變圖Fig.2The evolution map nverlution根據(jù)一階混雜Petri網(wǎng)演變圖的構(gòu)造方法可得到如圖2的演變圖.其中IB0=(md0=1,1,0T, mc0=0,0T,v0=0T,0,2200),IB1=(md1=1,1,0T, mc1=4000,0T,v1=2T,2200,4200),IB2=(md2=1,1,0T, mc2=0,4000T,v2=0T,4200,6400),IB3=(

14、md3=1,0,1T, mc3=4000,0T,v3=0T,6400,6600).通過演變圖對(duì)系統(tǒng)進(jìn)行分析有如下結(jié)果:(1)在4個(gè)區(qū)域狀態(tài)之內(nèi)所有的離散遷移均可引發(fā),且連續(xù)遷移能以非0速率引發(fā),因此該一階混雜Petri網(wǎng)是活的,即該系統(tǒng)無死鎖. (2)Td和Tcoff引發(fā)的周期為2 200,Tcon引發(fā)的周期為200,mIC標(biāo)識(shí)變?yōu)?的周期為2 000.(3)考察連續(xù)庫(kù)所PIC,由于該庫(kù)所的標(biāo)識(shí)mIC變?yōu)?的周期為2 000,因此庫(kù)所PIC不會(huì)出現(xiàn)一直為負(fù)增長(zhǎng)和一直為正增長(zhǎng)的情況;而離散庫(kù)所一直在0和1之間變化,亦不會(huì)出現(xiàn)一直為負(fù)增長(zhǎng)和一直為正增長(zhǎng)的情況,所以系統(tǒng)是安全的.實(shí)例2圖3為一經(jīng)典的

15、混雜系統(tǒng)三水箱系統(tǒng)的流體隨機(jī)Petri網(wǎng)模型,采用數(shù)值分析方法不能判斷存儲(chǔ)罐中水的平均體積(即庫(kù)所P1的平均標(biāo)識(shí))、水箱中水的平均體積(即庫(kù)所P1的平均標(biāo)識(shí))、及閥門出水的平均速率(即Flow2、Flow4、Flow5、Flow6的平均流速),為此可通過本文的轉(zhuǎn)換方法把流體隨機(jī)Petri網(wǎng)模型轉(zhuǎn)換成如圖4的一階混雜Petri網(wǎng)模型,然而通過該混雜Petri網(wǎng)模型的行為演變?nèi)圆荒芡耆o出上述3個(gè)問題的答案,進(jìn)一步利用算法2構(gòu)造該混雜Petri網(wǎng)模型的行為演變的混雜自動(dòng)機(jī)模型如圖5.根據(jù)如圖5的混雜自動(dòng)機(jī),利用混雜自動(dòng)機(jī)的模型分析軟件SIRPHYCO可得出上述3個(gè)問題的答案9,即儲(chǔ)罐中水的平均體積為0.6個(gè)單位、水箱中水的平均體積為4.4個(gè)單位、閥門出水的平均速率2個(gè)單位/秒.討論:上述兩個(gè)實(shí)例表明本文所提出的非數(shù)值分析法在分析流體隨機(jī)Petri網(wǎng)模型一些性質(zhì)是有效的,可以作為一種有效的分析方法和傳統(tǒng)的數(shù)值分析方法相結(jié)合,從而能夠有效地實(shí)現(xiàn)對(duì)流體隨機(jī)Petri網(wǎng)模型進(jìn)行分析.另一方面,盡管流體隨機(jī)Petri網(wǎng)和一階混雜Petri網(wǎng)之間可以相互模擬,但不同的模型其有效的分析方法是有區(qū)別的,如何根據(jù)實(shí)際混雜系統(tǒng)分析的需要選擇合適的模型進(jìn)行分析仍需作更深入的研究.4結(jié)論針對(duì)流體隨機(jī)Petri網(wǎng)模型數(shù)值分析方法的問