一種有時間約束的復(fù)雜Petri網(wǎng)建模方法

黃敏，魏偉

(長沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，湖南 長沙，410014)

用傳統(tǒng)Petri網(wǎng)對系統(tǒng)過程進(jìn)行建模和分析時[1]，隨著系統(tǒng)復(fù)雜性的增加，其狀態(tài)空間呈指數(shù)級增長，分析難度急劇增加，造成 Petri網(wǎng)對復(fù)雜系統(tǒng)的建模和分析很困難。尤其是當(dāng)系統(tǒng)具有時間約束時，傳統(tǒng)Petri網(wǎng)的描述能力有限，分析方法和手段不夠完善。為此，如何降低Petri網(wǎng)的建模復(fù)雜性和增強(qiáng)分析能力已成為研究熱點(diǎn)和難點(diǎn)。

1 相關(guān)的研究基礎(chǔ)

為降低復(fù)雜系統(tǒng)的建模和分析難度，一些研究者[2-4]主要從3個方面對傳統(tǒng)Petri網(wǎng)進(jìn)行改進(jìn)：一是利用面向?qū)ο骩2]的概念，將邏輯上相對獨(dú)立的過程抽象為一個對象，其中的變化細(xì)節(jié)封裝在對象內(nèi)部，這樣就能在相對較大的粒度上對系統(tǒng)進(jìn)行建模和分析，達(dá)到降低難度的目的，同時增強(qiáng)系統(tǒng)的可重用性和可剪裁性；二是利用分層[3]的概念，將一個大系統(tǒng)劃分為幾個子網(wǎng)，子網(wǎng)又可以細(xì)分為更小的子網(wǎng)，通過對子網(wǎng)性質(zhì)的分析來反映原網(wǎng)的部分或全部性質(zhì)，以此達(dá)到降低建模和分析的難度。以上2種方法主要用于對實(shí)際系統(tǒng)的建模和分析。三是各種化簡技術(shù)[4]，最早提出化簡思想的是Hack；Lipton 引入D-化簡技術(shù)，并用于化簡并行程序；Kowalk和Valk推廣了化簡思想，建立化簡定理；Murata等[5]針對T圖提出若干化簡規(guī)則，并討論這些規(guī)則對活性、安全性的保持關(guān)系；Lee等提出Petri網(wǎng)的等級化簡和分解方法，定義可化簡子網(wǎng)、子網(wǎng)的等級以及宏結(jié)點(diǎn)等概念；Ramamoorthy等[6]提出新概念SWBM。SWBM是滿足一定條件的子網(wǎng)，將其化簡成為單一的變遷，并且化簡后的 Petri網(wǎng)保持原網(wǎng)的所有性質(zhì)。第3種方法主要用于理論研究。為增強(qiáng)對時間的描述能力，通常在庫所、變遷以及連接庫所和變遷的有向弧上添加時間信息，從而形成各種時間 Petri網(wǎng)模型，其中 Timed Petri Nets，Stochastic Petri Nets，Time Petri Nets與 Timing Constraint Petri Nets等模型的影響較大。Timed Petri Nets由 Ramchandnai[7]提出，在每一個變遷上添加 1個時間延遲Tdel，它遵循強(qiáng)觸發(fā)規(guī)則[8]，即一個變遷tj對應(yīng)1個時間延遲Tdel，如果在時間T0，tj的所有輸入庫所的Token均準(zhǔn)備就緒，那么變遷 tj立即執(zhí)行。在時間(T0，T0+ Tdel)內(nèi)，所有輸入庫所的 Token都?xì)w tj所使用，其余變遷不能使用。在時刻T0+Tdel到來時，tj輸入庫所的 Token就被轉(zhuǎn)移到相應(yīng)的輸出庫所中。Timed Petri Nets及其相關(guān)模型主要用于并發(fā)系統(tǒng)的性能分析。Stochastic Petri Nets[9]是對Timed Petri Nets的改進(jìn)，由于在變遷發(fā)生之前，無法給出每個變遷的準(zhǔn)確時間延遲，但可以通過以前的經(jīng)驗(yàn)或者期望來推斷變遷的執(zhí)行延遲符合某種概率分布，因此，可以利用變遷執(zhí)行的平均時間代表變遷的延遲。Stochastic Petri Nets主要用于性能評價(jià)，林闖[9]在這方面做了許多工作。Time Petri Net(TPN)由Merlin等首先提出。它將Timed Petri Nets中變遷的時間延遲替換為一個使能區(qū)間(TCmin, TCmax) (其中，TCmin表示相應(yīng)變遷使能前所必須流逝的最小時間，TCmax表示相應(yīng)變遷觸發(fā)前可以經(jīng)歷的最長時間)，它遵循強(qiáng)觸發(fā)規(guī)則，但變遷的執(zhí)行是瞬間完成的，而Timed Petri Nets和Stochastic Petri Nets中變遷的執(zhí)行均需要一段時間。TPN已被證明可比較方便地表示并發(fā)系統(tǒng)中的時間約束，應(yīng)用于各種實(shí)時系統(tǒng)的時間行為分析和性能評估等方面。Timing Constraint Petri Nets(TCPN)由 Tsai[10]提出。鑒于事件的發(fā)生條件有時也有時間要求，因此，TCPN中庫所和變遷上均有時間約束信息。庫所的時間約束借鑒TPN的思路，變遷的時間約束借鑒 Timed Petri Nets和TPN。TCPN遵循弱觸發(fā)規(guī)則，即變遷的觸發(fā)不僅受制于變遷的外延，而且與變遷及其輸入庫所上的時間約束信息密切相關(guān)。本文作者在面向?qū)ο蠛蚑iming Constraint Petri Nets的基礎(chǔ)上，提出面向?qū)ο髸r間Petri網(wǎng)(Oriented Object Timing Constraint Petri Nets，簡稱OOTCPN’s)的定義及其建模方法，通過建立時延關(guān)聯(lián)矩陣等措施，試圖在降低系統(tǒng)復(fù)雜性的同時，分析系統(tǒng)的時間約束特性，找出系統(tǒng)的瓶頸，從理論角度為系統(tǒng)改進(jìn)和優(yōu)化提供決策依據(jù)。

2 OOTCPN’s的定義

在 OOTCPN’s中，系統(tǒng)由相互通信的物理對象和它們之間的聯(lián)系構(gòu)成，物理對象是協(xié)議的參與者[10-16]。

定義1 系統(tǒng)S是一個三元組，S=(O, R, TC)稱為面向?qū)ο髸r間約束Petri網(wǎng)，其中O={Oi, i=1, 2, …, I,I∈N}, Oi為系統(tǒng)中的對象，O為系統(tǒng)對象的集合；R為對象之間關(guān)系的集合；TC為時間約束。

對象的動態(tài)行為表現(xiàn)為內(nèi)部活動變遷和外部信息傳遞。前者由對象內(nèi)的狀態(tài)庫所和活動變遷表示，后者通過各對象間發(fā)送和接收信息的消息庫所獲得。對象行為受時間約束。

定義 2 對象 Oi定義為：Oi=(Pi，Ti，F(xiàn)i)。

(1) Pi= { APi,PIi, POi}。其中：APi， PIi和 POi分別為對象內(nèi)狀態(tài)庫所集、對象輸入消息庫所集和對象輸出消息庫所集，消息庫所是對象與外界進(jìn)行通信的接口，消息庫所之間傳遞的消息用托肯表示。

(2) Ti= { ATi, OTi}。其中： ATi為對象內(nèi)狀態(tài)變遷有限集合； OTi為對象的操作，對象的操作是對對象內(nèi)狀態(tài)變遷進(jìn)行抽象。

復(fù)雜的對象可以細(xì)化為1個TCPN’s。

對象由消息庫所和對象的操作之間的弧線封閉而成，對象的數(shù)據(jù)、結(jié)構(gòu)都被限制在這個邊界內(nèi)，對外不可見，外界只能通過消息庫所和對象的操作與對象進(jìn)行通信，從而實(shí)現(xiàn)對象的封裝。

Pi和 Ti必須滿足條件 Ti∪Pi≠? ，Ti∩Pi=? 。

(3) Fi是對象 Oi內(nèi)關(guān)系的集合，F(xiàn)i={Pi×Ti∪Ti×Pi}。

定義3 對象間關(guān)系定義為：R={P, G, F}。其中：

(1) P= { POk, PIk}。POk和PIk分別為與門gk相連接的對象的輸出消息庫所和輸入消息庫所，其實(shí)質(zhì)就是對象的輸出消息庫所 POi和輸入消息庫所 PIi。

(2) G為對象間信息傳遞門gk的有限集合。

門實(shí)現(xiàn)對象之間的消息傳遞，被看作是一種特殊的變遷。門gk與前一對象的輸出消息庫所 POk和后一對象的輸入消息庫所 PIk相關(guān)聯(lián)。若 POk中至少有1個消息(或托肯)，則 gk使能，并在時間區(qū)間[Eft(gk),Lft(gk)]內(nèi)觸發(fā)(其中Eft(gk)表示門變遷gk的最早觸發(fā)事件，Lft(gk)表示gk的最晚觸發(fā)時間)，若能成功觸發(fā)，則消息(或托肯)傳遞到 PIk。從外界看，1個門能否成功觸發(fā)表現(xiàn)為與之相關(guān)的對象之間能否進(jìn)行消息傳遞。

(3) F是對象間的流關(guān)系，F(xiàn)=P×G∪G×P。

定義4 對象的時間約束TC={C，D}。其中：

(2) D表示對象內(nèi)狀態(tài)改變或?qū)ο箝g消息傳遞所需的時間，用[D(TG)]表示，且[D(TG)]≥0。以對象間消息傳遞門gk為例，D=[D(gk)]≥0，表示門gk接收到消息并觸發(fā)，需要占用 D(gk)時間，才能將消息發(fā)往另一對象。對象內(nèi)狀態(tài)改變記為D=[D(OT)]≥0，表示需占用D(OT)時間，對象Oi才能從一個狀態(tài)改變到另一狀態(tài)。

圖1 對象及其之間的關(guān)系Fig.1 Objects and their relationship

面向?qū)ο髸r間約束Petri網(wǎng)如圖1所示，該模型有4個對象(O1, O2, O3, O4),對象內(nèi)通過 OTi(i=1, 2, 3, 4)進(jìn)行狀態(tài)改變，所需要的時間分別為 20，20，25和20。對象間通過門變遷 g1和 g2進(jìn)行信息傳遞。當(dāng) 2個門變遷在時刻T0使能，因競爭對象O1資源，而g1的觸發(fā)區(qū)間是(T0+5, T0+10)，g2的觸發(fā)區(qū)間是(T0+10,T0+20)，可知T0+Eft(g1)＜T0+Eft(g2)，因此，門變遷g1有優(yōu)先觸發(fā)權(quán)。若門變遷g1在觸發(fā)區(qū)間(T0+5, T0+10)內(nèi)未成功觸發(fā)，則失去觸發(fā)權(quán)，此時，到達(dá)門變遷g2的觸發(fā)區(qū)間，則g2有觸發(fā)權(quán)。

3 OOTCPN's的動態(tài)運(yùn)行規(guī)則

OOTCPN’s中的 token依照動態(tài)運(yùn)行規(guī)則不斷地在對象中傳遞，這個過程描述了系統(tǒng)的動態(tài)特性，也反映了消息在系統(tǒng)中的產(chǎn)生和傳遞過程。

3.1 OOTCPN’s的狀態(tài)

OOTCPN’s中一個狀態(tài) M 是一個二元組{W,TC}，其中W為對象狀態(tài)。由于在信息系統(tǒng)中，消息有“輸入”、“輸出”和“無”3種狀態(tài)，所以，規(guī)定W(Oi)=“1”表示對象 Oi有消息要輸入，W(Oi)=“-1”表示對象Oi有消息要輸出；否則，W(Oi)=“0”。

TC為系統(tǒng)狀態(tài)發(fā)生的時間特性。

3.2 前集后集的概念

3.3 門變遷的使能條件

在T0時刻，若， W ( Oi)=1，則gk使能，記為enable(gk)。

3.4 門變遷的觸發(fā)條件

門變遷gk在時刻T 觸發(fā)需滿足以下3個條件，記為M[gk＞：

(1) enable(gk);

(2) Lft(gk)-Eft(gk)＞0;

(3) Lft(gk)≤FIRE(T)≤Eft(gk))，其中 FIRE(T)叫觸發(fā)時刻。

3.5 門變遷的發(fā)生后果

若M[gk＞，則gk在M可以發(fā)生，將標(biāo)識M={W,TC}改變?yōu)?M 的后繼 M′={W′, TC'}。

W'的定義是：

TC'的定義為：

3.6 門變遷的可達(dá)性

若存在變遷序列 g1, g2, …, gk和狀態(tài)序列 M1,M2, …, Mk使得

則稱MK是從M1可達(dá)的。若變遷序列g(shù)1, g2, …, gk為σ，則式(1)可以記為 M1[σ＞MK。

3.7 變遷時延

用delay(TC)表示運(yùn)行所需的時延之和，則

3.8 關(guān)聯(lián)矩陣

關(guān)聯(lián)矩陣是 Petri網(wǎng)中用于判斷變遷是否有發(fā)生權(quán)以及計(jì)算變遷發(fā)生效果的有力工具，為使OOTCPN's具有較強(qiáng)的系統(tǒng)分析能力，定義狀態(tài)關(guān)聯(lián)矩陣C和時延關(guān)聯(lián)矩陣T。

定義5 狀態(tài)關(guān)聯(lián)矩陣C。

(1) 以對象集O為序標(biāo)集的行向量V：O→Z叫做S的O-向量，其中Z是整數(shù)集。

(2) 以門集G為序標(biāo)集的列向量U：G→Z叫做S的G-向量。

對于gk∈G, U(gk)表示門變遷gk在變遷序列σ中的觸發(fā)次數(shù)。

(3) 以O(shè)×G為序標(biāo)集的矩陣C：O×G→Z叫做S的狀態(tài)關(guān)聯(lián)矩陣，其矩陣元素為：

定義6 時延關(guān)聯(lián)矩陣T。

(1) 以對象集O為序標(biāo)集的行向量V：O→Z叫做S的O-向量，其中Z是整數(shù)集。

(2) 以門集G為序標(biāo)集的列向量U：G→Z叫做S的G-向量。

(3) 以O(shè)×G為序標(biāo)集的矩陣T：O×G→Z叫做S的時延關(guān)聯(lián)矩陣，其矩陣元素表示變遷所需的最短時延。

定理1 對于M={W, TC}，M0為初始狀態(tài)，TC0為初始時延，C為狀態(tài)關(guān)聯(lián)矩陣，T為時延關(guān)聯(lián)矩陣，若經(jīng)過變遷序列σ后達(dá)到狀態(tài)M，則存在非負(fù)整數(shù)n維向量U使得：

式(2)稱為系統(tǒng)狀態(tài)方程；式(3)稱為系統(tǒng)時間特性方程。

證明：根據(jù)定義5，狀態(tài)關(guān)聯(lián)矩陣元素的值W(Oi,gk)-W(gk, Oi)描述的是門變遷gk發(fā)生時輸入輸出的最終效果，g1發(fā)生后，M1=M0+C，而 U(gk)表示門變遷gk在變遷序列σ中的觸發(fā)次數(shù)，很明顯，經(jīng)過變遷序列 σ后M=M0+C·U。

定理1得證。

4 OOTCPN’s的建模分析步驟

(1) 建立對象模型。根據(jù)系統(tǒng)的運(yùn)行規(guī)則，將一些相對獨(dú)立的過程抽象為“對象”或“門”變遷，以簡化系統(tǒng)的建模規(guī)模，明確對象或門的名稱、屬性、操作，并確定時間約束。一些復(fù)雜的對象、門可以細(xì)化為一個系統(tǒng)。

(2) 確定對象消息庫所及對象間的通信網(wǎng)關(guān)(即門變遷)。根據(jù)現(xiàn)實(shí)系統(tǒng)中實(shí)體對象以及它們與周圍環(huán)境的關(guān)系，建立消息庫所和對象之間的消息關(guān)系。

(3) 構(gòu)建完整的OOTCPN’s模型。根據(jù)確定的對象，消息庫所和對象間關(guān)系建立OOTCPN’s網(wǎng)模型；

(4) 模型分析。根據(jù) OOTCPN’s網(wǎng)模型，建立模型狀態(tài)關(guān)聯(lián)矩陣C和時延關(guān)聯(lián)矩陣T，分析模型運(yùn)行時間，為系統(tǒng)或流程改進(jìn)提供參考依據(jù)。

5 應(yīng)用實(shí)例

本文以保險(xiǎn)索賠過程為例進(jìn)行建模與分析。該實(shí)例原型請參見文獻(xiàn)[8]。由于保險(xiǎn)索賠過程比較復(fù)雜，將一些相對獨(dú)立的過程抽象為門變遷，見表1所示。根據(jù)OOTCPN’s建模步驟，建立如圖2所示的保險(xiǎn)索賠過程OOTCPN’s模型，下面使用本文提出的方法對其進(jìn)行分析。

系統(tǒng)初始狀態(tài)M0=(1,0,0,0,0,0,0,0,0)T。

行向量V={O1,O2,O3,O4,O5,O6,O7,O8,O9}。

列向量U={g1,g2,g3,g4,g5,g6,g7,g8}T。

根據(jù)定義5和定義6可得模型狀態(tài)關(guān)聯(lián)矩陣C和時延關(guān)聯(lián)矩陣T。

表1 門變遷及其含義Table 1 Transitions and their meaning

狀態(tài)關(guān)聯(lián)矩陣為：

時延關(guān)聯(lián)矩陣為：

由圖2知：由申請索賠到索賠成功并記錄賠付有2種變遷序列，σ1=g1g4g5，即U1=(1,0,0,1,1,0,0,0)T以及σ2=g1g4g6，即 U2=(1,0,0,1,0,1,0,0)T。

初始時延 TC0={0}，根據(jù)式(4)，時延 TC′1=T+ T ×U=(1,8,0,9,4,3,0,0,0)T

根據(jù)式(2)，delay(TC1)=1+8+9+4+3=25；時延TC′2=TC0+T×U2=(1,8,0,4,9,0,3,0,0)T；delay(TC2)=1+8+4+9+3=25。

可知：delay(TC1)=delay(TC2)，即索賠過程中定損與材料整理所需時間相同，可在同一時間進(jìn)入記錄賠付階段而無需等待。圖 2確定的時間約束是合理的(注：建模過程中時間約束 C未標(biāo)注，則表示默認(rèn)為(0,∞)，D 默認(rèn)為[0])。

如果計(jì)算結(jié)果是delay(TC1)≠delay(TC2)，就要減小delay值小的分支的資源配置(包括人力、物力、財(cái)力)，增大delay值大的分支的資源配置，使兩者趨于平衡。增大與減小的具體數(shù)值可根據(jù)相應(yīng)的比例來計(jì)算。

6 結(jié)論

(1) 在面向?qū)ο蠛蚑iming Constraint Petri Nets的基礎(chǔ)上，提出面向?qū)ο髸r間 Petri網(wǎng)(OOTCPN’s)的概念、動態(tài)運(yùn)行規(guī)則和建模方法，增強(qiáng)了Petri網(wǎng)對有時間約束的復(fù)雜系統(tǒng)的模擬和分析能力。

(2) 提出了描述 OOTCPN’s模型關(guān)聯(lián)矩陣和時延關(guān)聯(lián)矩陣，用于判斷變遷是否有發(fā)生權(quán)以及計(jì)算變遷發(fā)生的后果，使得OOTCPN’s具有較強(qiáng)的系統(tǒng)分析能力。通過對保險(xiǎn)索賠過程的實(shí)例分析，表明本文所提方法能較好地模擬和分析復(fù)雜系統(tǒng)的時間約束特性。

[1] Tasi J J P, Yang S J. Timing constraint Petri nets and their application to schedulability analysis of real-time system specifications[J]. IEEE Trans Software Engineering, 1995, 21(1):32-49.

[2] 顧妍午, 王遵彤, 吳啟迪. 面向?qū)ο?Petri網(wǎng)技術(shù)在系統(tǒng)建模中的應(yīng)用[J]. 同濟(jì)大學(xué)學(xué)報(bào): 自然科學(xué)版, 2010, 38(3):437-441.GU Yan-wu, WANG Zun-tong, WU Qi-di, Application of object-oriented Petri-nets in system modeling[J]. Journal of Tongji University: Natural Science, 2010, 38(3): 437-441.

[3] 楊雪, 蔣昌俊. Petri網(wǎng)化簡規(guī)則在系統(tǒng)中的實(shí)現(xiàn)[J]. 算機(jī)工程與應(yīng)用, 2003, 40(32): 66-68.YANG Xue, JIANG Chang-jun. Realization of the reduction methods of Petri net in the system[J]. Computer Engineering and Application, 2003, 40(32): 66-68.

[4] 汪琳, 樂曉波, 陳國平. Petri網(wǎng)化簡技術(shù)的研究[J]. 系統(tǒng)仿真學(xué)報(bào), 2007, 19(S1): 110-113.WANG Lin, YUE Xiao-bo, CHEN Guo-ping. The research of Petri net’s simplified technology[J]. Journal of System Simulation, 2007, 19(S1): 110-113.

[5] Murata I, Suzuki T, Shatz S. Fuzzy-timing high-level Petri nets(FTHNs) for time-critical systems[J]. J Cardoso and Camargo,1999, 22(3): 88-114.

[6] Ramamoorthy C V, Yaw Y. A petri net reduction algorithm for protocol analysis[C]//SIGCOMM ’86 Proceedings of the ACM SIGCOMM Conference on Communications Architectures &Protocols. 1986, 8(16): 157-166.

[7] Ramchandani C. Analysis of asynchronous concurrent system by timed Petri nets[D]. Cambridge: MIT, 1974: 10-20.

[8] 宋巍, 竇萬春, 劉西萍. 時間約束 Petri網(wǎng)及其可調(diào)度性分析與驗(yàn)證[J]. 軟件學(xué)報(bào), 2007, 18(1): 11-21.SONG Wei, DOU Wan-chun, LIU Xi-ping. Timing constraint Petri nets and their schedulability analysis and verification[J].Journal of Software, 2007, 18(1): 11-21.

[9] 林闖. 隨機(jī)Petri網(wǎng)和系統(tǒng)性能評價(jià)[M]. 2版. 北京: 清華大學(xué)出版社, 2005: 35-48.LIN Chuang. Stochastic Petri nets and system performance evaluation[M]. 2nd ed. Beijing: Tsinghua University Press, 2005:35-48.

[10] Tsai J J P, Yang S J, Chang Y H. Timing constraint Petri nets and their application to schedulability analysis of real-time system specifications[J]. IEEE Transactions on Software Engineering,1995, 21(1): 32-49.

[11] CHENG Bin, WANG Xin-gang, Li Ying. Study on parallel system performance modeling based on TCPN[J]. High Performance Computing and Applications, 2010, 45(21):108-113.

[12] CHENG Bin, Xin gang, WANG Wei-qin. Formal modeling of parallel system based on TCPN[J]. Network and Parallel Computing, 2009, 6(11): 464-470.

[13] JIANG Ping, GAO Liang, LI Pei-gen. Collaborative execution mechanisms for the TCPN-enhanced process-view approach based inter-enterprises workflow[J]. 2009 13th International Conference on Computer Supported Cooperative Work in Design,2009, 15(23): 480-485.

[14] PANG Hui, FANG Zong-de, ZHAO Yong. Simplification analysis and schedulability verification of timing constraint workflow model[J]. Computer Integrated Manufacturing System,2008, 34(2): 4532-4538.

[15] GUO Yin-zhang, ZENG Jian-chao. A temporal logic inference for collaborative product design process based on time constraint Petri nets[J]. Journal of Computer-Aided Design &Computer Graphics, 2010, 33(9): 405-415.

[16] 劉韜, 傅衛(wèi)平, 王雯, 等. 基于面向?qū)ο筚x時Petri網(wǎng)的出入庫系統(tǒng)建模[J]. 系統(tǒng)仿真學(xué)報(bào), 2006, 18(3): 537-541.LIU Tao, FU Wei-ping, WANG Wen, et al. Modeling of loading and unloading scheduling system based on object-oriented timed Petri net[J]. Journal of System Simulation, 2006, 18(3):537-541.