Web服務(wù)描述與組合是實現(xiàn)面向服務(wù)計算的關(guān)鍵，但目前Web服務(wù)描述研究對Web服務(wù)的實時性與智能性因素考慮不多，不適合用于分布式實時系統(tǒng)中的服務(wù)描述。該文首先定義了適合實時服務(wù)描述的實時有色Petri網(wǎng)（RTCPN）與層次實時有色Petri網(wǎng)（HRTCPN），然后建立了原子實時服務(wù)到RTCPN映射描述模型（AS-RTCPN），對服務(wù)組合運算規(guī)則進行了詳細描述與建模，最后形成了服務(wù)組合HRTCPN描述模型的簡化算法，并給出了HRTCPN的可達服務(wù)圖RSG的定義及構(gòu)建算法，證明了HRTCPN模型的正確性。

【關(guān)鍵詞】Web服務(wù) Petri網(wǎng) 形式化描述 實時服務(wù) 服務(wù)描述

1 引言

面向服務(wù)計算是實現(xiàn)跨平臺、跨語言和松藕合的最新分布式計算技術(shù)，Web服務(wù)則是面向服務(wù)計算至今最好實現(xiàn)技術(shù)。目前用Petri網(wǎng)來進行Web服務(wù)描述及組合的研究很多，文獻[1]利用模糊Petri網(wǎng)作為服務(wù)描述語言的基礎(chǔ)，并基于模糊Petri網(wǎng)和本體給出了一個網(wǎng)格服務(wù)發(fā)現(xiàn)的多Agent框架，使用可能性和必然性來表示對一個服務(wù)Agent能為需求Agent提供相關(guān)服務(wù)的信心程度；文獻[2]基于Petri網(wǎng)構(gòu)建了服務(wù)組合網(wǎng)C-Net來分析多個Web服務(wù)之間的交互，把服務(wù)行為相容性問題分析轉(zhuǎn)化為對C-net的結(jié)構(gòu)死鎖問題分析，Web服務(wù)能相容等價于在C-net圖中存在非空最小Siphons。但這些基于Petri網(wǎng)的Web服務(wù)描述研究都沒有考慮Web服務(wù)的實時性與智能性因素，不適合用于分布式實時系統(tǒng)中的服務(wù)描述，為此我們運用層次實時有色Petri網(wǎng)來構(gòu)建實時服務(wù)的形式化描述模型，并采用OWL-S來表示共享領(lǐng)域知識來保證服務(wù)的智能性。

2 層次實時有色Petri網(wǎng)

層次實時有色Petri網(wǎng)是由含時間因素的Petri網(wǎng)[3]與有色Petri網(wǎng)[4]結(jié)合發(fā)展而來，在文獻[5]中運用了層次實時有色Petri網(wǎng)對嵌入式實時硬件電路設(shè)計進行建模與分析，并對應(yīng)用在這種應(yīng)用情況下的層次實時有色Petri網(wǎng)進行了定義。為了能更適合描述分布式實時系統(tǒng)中的實時服務(wù)軟件設(shè)計建模與分析，根據(jù)文獻[5]中定義的層次實時有色Petri網(wǎng)，我們重新定義了層次實時有色Petri網(wǎng)。

定義1：實時有色Petri網(wǎng)（Real-Time Coloured Petri Net，RTCPN）是一個1 3元組：RTCPN=（Ω，P，T，A，N，C，G，E，DI，DT，TS，I）。其中，Ω為是顏色的非空集合（colour set）；P為庫所的非空集合（places）；T為變遷的非空集合（transitions）；A為有向弧的集合（arcs），并且滿足表達式P∩T=P∩A=T∩A=φ；N為節(jié)點，有N：A→P×T∪T×P；C為顏色函數(shù)，定義為C：P∪T→Ω，對于p∈P，C（p）是庫所p上所有可能的托肯色之集合，對于t∈T，C（t）是變遷t上所有可能的出現(xiàn)色之集合；G是變遷的警衛(wèi)函數(shù)，指定變遷觸發(fā)必須滿足的前提條件，定義為G：T→expr（expr即表達式），有t∈T：[Type（G（t））=B∧Type（Var（G（T）））Ω]，其中B是布爾型函數(shù)，Var（.）表示變量，Type（.）表示類型（Type）；E為弧表達式函數(shù)，有E：A→expr.，有x∈A：[Type（E（a））=C（P）MS∧Type（Var（E（a）））Ω]，其中P是N（a）的庫所集元素，下標MS為多重集函數(shù)；DI為關(guān)聯(lián)變遷的實數(shù)對[tmin，tmax]的集合，tmin表示變遷最早觸發(fā)時間，tmax表示變遷最晚觸發(fā)時間；DT網(wǎng)中每個變遷執(zhí)行的持續(xù)時間，當持續(xù)時間為0時，稱之為瞬時變遷，不為0時稱之為時延變遷；TS （Time Stamp）為托肯的時間戳集合，對于t∈T，TS（t）包含了托肯到達庫所p的時間信息，托肯的時間戳信息可以通過計算表達式：TS（p）=max{TS（p）+ D（p）+DT（p）|p∈p}得出，其中D為變遷觸發(fā)的延時函數(shù)；I是初始化函數(shù)，定義為從P到一個封閉表達式I（p），滿足p∈P：[Type（I（p））=C（P）MS] 。

定義2：層次實時有色Petri網(wǎng)（Hierarchical Real-Time Coloured Petri Net，HRTCPN）是一個1 4元組HRTCPN=（Ω，P，T，A，N，C，G，E， DI，DT，TS，I，S）。其中，Ω、P、T、A、N、C、G、E、DI、DT、TS、I表示的含義與實時有色Petri網(wǎng)RTCPN中對應(yīng)元組的含義一樣；S是由子層次實時有色Petri網(wǎng)（Sub—HRTCPN）和實時有色Petri網(wǎng)（RTCPN）構(gòu)成的集合，S={HRTCPN} U{RTCPN}。

3 HRTCPN實時服務(wù)描述模型

目前We b服務(wù)語義描述領(lǐng)域最成熟的語言是OWL-S，在構(gòu)建實時服務(wù)描述模型時，我們以O(shè)WL-S對Web服務(wù)語義描述元素為基礎(chǔ)來進行構(gòu)建。OWL-S把每個服務(wù)看成是一個過程，并且將服務(wù)過程分為原子過程、簡單過程及復合過程。從服務(wù)請求者角度來看，原子過程與簡單過程都是一步就可以完成，我們在此稱這兩者為原子服務(wù)；復合過程是由其它的原子或復合過程通過一些控制構(gòu)造算子來組合而成[8]，我們稱其為組合服務(wù)。故在構(gòu)建實時服務(wù)的描述模型時要分兩個方面進行描述模型設(shè)計，即原子服務(wù)描述模型及組合服務(wù)描述模型。原子服務(wù)描述我們用一個定義1所定義的實時有色Petri網(wǎng)來實現(xiàn)，而對組合服務(wù)描述我們用定義2中所定義的層次實時有色Petri網(wǎng)來表達。

3.1 原子實時服務(wù)到RTCPN映射描述模型（AS-RTCPN）

原子服務(wù)可直接調(diào)用，其內(nèi)部執(zhí)行過程對服務(wù)請求者不可見，故我們可以將原子服務(wù)描述為有一個輸入庫所（Pin）經(jīng)過一個服務(wù)變遷（ts）處理產(chǎn)生結(jié)果到一個輸出庫所（Pout）及一個知識庫所的實時有色Petri網(wǎng)結(jié)構(gòu)。原子服務(wù)到RTCPN的映射規(guī)則：

（1）將原子服務(wù)as的執(zhí)行過程映射為一個服務(wù)變遷ts，并將ts命名為原子服務(wù)的名稱，則T={service}；

（2）原子服務(wù)的輸入狀態(tài)被映射為包含token的輸入庫所Pin；

（3）原子服務(wù)的輸入前置條件被映射成服務(wù)變遷中的警衛(wèi)函數(shù)G；

（4）原子服務(wù)的輸出狀態(tài)和執(zhí)行效果映射為包含token的輸出庫所Pout；

（5）顏色集Ω=ps∪qs，ps表示原子服務(wù)的參數(shù)集，qs表示服務(wù)用戶的QoS需求集[37]；

（6）OWS-L描述的有關(guān)原子服務(wù)的知識庫映射為知識庫所Pk，知識庫內(nèi)容主要包含原子服務(wù)的質(zhì)量屬性、時間屬性及執(zhí)行規(guī)則等靜態(tài)語義信息；

（7）用戶的QoS需求滿足判定映射為有向邊輸入函數(shù)E，服務(wù)變遷執(zhí)行完成后對服務(wù)狀態(tài)產(chǎn)生的影響映射為有向邊輸出果函數(shù)E；

（8）根據(jù)原子服務(wù)時間屬性，對服務(wù)變遷觸發(fā)時延DI及服務(wù)變遷執(zhí)行持續(xù)時間DT賦值；

（9）通過初始化函數(shù)I（p）對輸入庫所Pin進行初始化。

定義3：原子實時服務(wù)的實時有色Petri網(wǎng)模型是一個11元組AS-RTCPN=（Ω，P，T，F(xiàn)，C，G，E，DI，DT，TS，M0），其中：

Ω= ps∪qs，ps表示原子服務(wù)的參數(shù)集，qs表示服務(wù)用戶的QoS需求集；

P={Pin， Pout， Pk}，Pin表示原子服務(wù)的輸入，Pout表示原子服務(wù)的輸出，Pk表示原子服務(wù)的知識庫；

T={ts}，ts表示原子服務(wù)的執(zhí)行；

F={（Pin， ts），（ts， Pout），（Pk， ts），（ts，Pk）}；

C={C（Pin），C（Pout），C（Pk）}；G=G（ts）；

E={E（Pin， ts），E ts， Pout），E（Pk， ts），E（ts， Pk）}；

DI=DI（ts），表示原子服務(wù)的觸發(fā)時間區(qū)間；DT=DT（ts），表示原子服務(wù)執(zhí)行持續(xù)時間；

TS=TS（Pin），顏色Token到達輸入庫所Pin的時間戳；

M0（Pin）=C（Pin），M0（Pout）=0， M0（Pk）=C（Pk）；

AS-RTCPN模型結(jié)構(gòu)圖如圖1所示。

3.2 組合實時服務(wù)HRTCPN映射描述模型（CS-HRTCPN）

組合過程用于表示具有復雜業(yè)務(wù)邏輯的服務(wù)，通常由原子服務(wù)或其他組合服務(wù)通過控制構(gòu)造算子組裝而成，這就形成了組合服務(wù)的層次結(jié)構(gòu)。在構(gòu)建基于HRTCPN的組合實時服務(wù)描述模型時，我們需要對組合服務(wù)模型中的變遷進行分類，用于表示被調(diào)用服務(wù)的變遷稱為服務(wù)變遷，用于把服務(wù)組織成組合服務(wù)的變遷稱為控制變遷。為了便于組合服務(wù)的實時性分析，我們假設(shè)所有控制變遷均為瞬時變遷。通過對OWL-S服務(wù)組合規(guī)范中的控制構(gòu)造算子研究分析，根據(jù)表達語義的不同，可將它們歸為六類服務(wù)組合運算：順序組合運算、任意次序組合運算、選擇組合運算、條件組合運算、并行組合運算及迭代組合運算。下面給出實時服務(wù)迭代組合服務(wù)用HRTCPN描述的模型結(jié)構(gòu)與轉(zhuǎn)換規(guī)則。

根據(jù)OWL-S規(guī)范，實際用來進行迭代運算控制的結(jié)構(gòu)包括Repeate-While及Repeate-Until。其中，它們分別通過屬性whileCondition和untilCondition指定執(zhí)行的初始、結(jié)束和維持條件，實時服務(wù)迭代組合運算符記為α。圖2（a）所示為實時服務(wù)RTS1的Repeat-Until組合運算模型結(jié)構(gòu)，可以表示為αRTS1。圖中變遷分為兩種類型，其中方框中標有ts的變遷表示服務(wù)變遷；方框中標有tc的變遷表示控制變遷，用于執(zhí)行組合運算；為了清晰展示模型結(jié)構(gòu)，模型結(jié)構(gòu)圖中省略了時間、弧表達式、警戒函數(shù)等標識，以下類同。在執(zhí)行過程中，服務(wù)變遷ts1將產(chǎn)生一個判斷條件，根據(jù)該條件值可決定是否終止循環(huán)過程。Repeat-While的語義與此類似，區(qū)別在于控制變遷tc2和tc3的警戒函數(shù)相反。迭代組合規(guī)則為：?=?1， P= Pin∪P1∪Pout，T=T1∪{tc1， tc2， tc3 }， F=F1∪{（Pin， tc1）， （tc1， Pin1）， （tc2， Pin1）， （Pout1， tc2）， （Pout1， tc3）， （tc3， Pout） }， C=C1， E=E1∪{E（Pin， tc1）， E（tc1， Pin1）， E（tc2， Pin1）， E（Pout1， tc2）， E（Pout1， tc3），E（tc3， Pout） }， G=G1∪{G（tc1）， G（tc2）， ， G（tc3）}， DI12=DI1∪{DI（tc1）=0， DI（tc2）=0， DI（tc3）=0}， DT=DT1，TS=TS1， M0=M01∪{M0（Pin）， M0 （Pout）}。

3.3 HRTCPN實時服務(wù)描述模型有效性分析

文獻[7]針對Web服務(wù)的動態(tài)時間有色Petri網(wǎng)（DTCPN）模型給出簡化算法，但只給出了順序、條件、并行及迭代等4種服務(wù)組合模型的簡化方法，沒有給出選擇組合及任意次序組合模型的簡化方法，而且沒有考慮變遷的可觸發(fā)時間區(qū)間。根據(jù)本文中給出的定義2、定義3及各種服務(wù)組合規(guī)則，參考文獻[7]中的簡化算法，我們設(shè)計了服務(wù)組合HRTCPN描述模型的簡化算法。

算法1 服務(wù)組合HRTCPN描述模型的簡化算法

輸入：HRTCPN

輸出：簡化后的HRTCPN

（1）實時服務(wù)迭代組合HRTCPN模型簡化規(guī)則：?=?1， P={Pk1， Pin， Pout}，T={ts1}， F={（Pin， ts1），（ts1， Pout）， （ts1， Pk1）， （Pk1，ts1）}， C（Pin）=C（Pin）， C（Pout）=C（Pout）， C（Pk12）=C（Pk1）+C（Pk2）， E（Pin， ts1）=E（Pin，tc1）， E（Pk1， ts1）= E（Pk1， ts1）， E（ts1，Pout）= E（tc2，Pout）， G（ts1）=G（ts1）， DI（ts1）= DI（ts1）， DT（ts1）=αDT（ts1）， TS（Pin）=TS（Pin）， TS（Pout）=TS（Pout）， M0=（C（Pin）， C（Pk1），0）。簡化后的HRTCPN模型結(jié)構(gòu)如圖2（b）所示。

（2）實時服務(wù)順序組合HRTCPN模型簡化規(guī)則：?=?12， P={Pk12， Pin12， Pout12}，T={ts12}，F(xiàn)={（Pin12，ts12），（ts12，Pout2）}，C（Pin12）=C（Pin1）+C（Pin2）， C（Pout12）=C（Pout1）+C（Pout2）， C（Pk12）=C（Pk1）+C（Pk2）， E（Pin12， ts12）= E（Pin1， ts1）+ E（Pin2， ts2）， E（Pk12， ts12）=E（Pk1，ts1）+ E（Pk2，ts2）， E（ts12，Pout12）=E（ts1，Pout1）+ E（ts2，Pout2）， G（ts12）=G（ts1）∧G（ts2）， DI（ts12）=[tmin1，tmax1+ tmax2-tmin2]， DT（ts12）=DT（ts1）+DT（ts2）， TS（Pin12）=TS（Pin1）， TS（Pout12）=TS（Pout1）， M0=（C（Pin1）+C（Pin2）， C（Pk1）+C（Pk2），0）。簡化后的HRTCPN模型結(jié)構(gòu)如圖3（b）所示。

理論上通過算法1可以將一個復雜的服務(wù)組合描述HRTCPN模型簡化為一個與原子服務(wù)描述RTCPN模型結(jié)構(gòu)相似的簡化模型，但這樣簡化后的模型太抽象，不利于對原服務(wù)系統(tǒng)的理解與分析，所以在實際應(yīng)用此算法簡化HRTCPN模型時，我們規(guī)定組合簡化層級不能超過3層。

對組合服務(wù)HRTCPN模型簡化之后，我們就可以針對簡化模型構(gòu)建可達服務(wù)圖（RSG）。文獻[8]針對網(wǎng)格服務(wù)的有色動態(tài)時延Petri網(wǎng)（CDTPN）構(gòu)建了RSG，在此文獻基礎(chǔ)之上我們給出針對HRTCPN的可達服務(wù)圖RSG的定義及構(gòu)建算法。

定義4 HRTCPN的可達服務(wù)圖RSG是一個帶標識結(jié)點與帶標識有向邊的有向圖，且RSG（HRTCPN）=（V，E，F(xiàn)T，F(xiàn)M）。其中，V={R（M0）；E={（Mi，Mj）|Mi，Mj∈R（M0）}，tk∈T：Mi[tk>Mj；FT（Mi，Mj）=tk/tsk：[tmin，tmax]，tsk表示顏色Token到達庫所tk的時間戳，[tmin，tmax]是變遷tk的可能觸發(fā)時間區(qū)間；FM（Mj）=OP，OP表示服務(wù)變遷執(zhí)行輸出結(jié)果值。

根據(jù)可達服務(wù)圖RSG的定義，我們可以設(shè)計出構(gòu)建RSG的算法。

算法2 HRTCPN的可達服務(wù)圖構(gòu)建

輸入：簡化后的HRTCPN

輸出：RSG（HRTCPN）

（1）令V={M0}，E={φ}，并給結(jié)點M0標記”new”標簽；

（2）如果V中不存在標記為”new”的結(jié)點，則算法結(jié)束，否則轉(zhuǎn)到步驟（3）；

（3）在V中任選一個有”new”標記的結(jié)點，設(shè)為M，再做如下處理：

（3.1）if t∈T：M[t> Then把M的標記改為”end node”；

（3.2）For 每個滿足M[t>的t∈T Do

（3.2.1）計算M[t>M中的M；

（3.2.2）If MV，then V=V+{M}，同時給M標記”new”標簽；

（3.3.3）E=E+（M，M），并給邊（M，M）標注tk/tsk：[tmin，tmax]，tsk表示顏色Token到達庫所tk的時間戳，[tmin，tmax]是變遷tk的可能觸發(fā)時間區(qū)間；

（3.3.4）If tk=sk，then 給結(jié)點M標注服務(wù)變遷執(zhí)行時間及執(zhí)行輸出結(jié)果；

（3.3.5）否則給結(jié)點M標注”[0，0]”或不標注任何標簽；

（3.3）移除結(jié)點M的”new”標簽，并返回到步驟（1）。

算法2與文獻[3]中的可覆蓋性樹構(gòu)造算法原理相同，故對任何組合服務(wù)HRTCPN描述模型，算法2都是可以終止的。同時，根據(jù)HRTCPN與RSG的定義，以及服務(wù)都是按照一定的業(yè)務(wù)邏輯規(guī)則進行組合的，故很容易證明算法2是正確的，在此證明從略。

命題1[3] HRTCPN是有界的當且僅當RSG（HRTCPN）中，每個結(jié)點的標識向量中都不含有無限分量（ω）。

命題2 [8] HRTCPN是組合服務(wù)的層次結(jié)構(gòu)實時有色Petri網(wǎng)描述模型，則HRTCPN是無死鎖的當且僅當M∈RSG（M0），M（Pout）≠0，p≠Pout∈P，M（p）=0。

命題3 HRTCPN無死鎖、RSG（M0）是RSG（HRTCPN）的頂點集，則組合服務(wù)系統(tǒng)的總執(zhí)行時間ET=max{∑（di+dti）}，其中∑（di+dti）是Mi的標識和，Mi是從M0到終端結(jié)點M路徑上的結(jié)點，且M0，Mi，M∈RSG（M0），di是服務(wù)變遷ti的觸發(fā)實際延遲時間，dti是服務(wù)變遷ti的執(zhí)行時間。

根據(jù)命題1、RTCPN的定義及服務(wù)組合規(guī)則，HRTCPN模型是有界的Petri網(wǎng)。同時根據(jù)RSG（HRTCPN）的構(gòu)造算法及命題2可知，HRTCPN模型是無死鎖的Petri網(wǎng)。

定義5 當且僅當HRTCPN模型是有界的與無死鎖的，用HRTCPN模型描述的面向服務(wù)應(yīng)用系統(tǒng)是可靠的。

4 結(jié)束語

Petri網(wǎng)非常適合描述服務(wù)的動態(tài)語議，目前用Petri網(wǎng)來進行Web服務(wù)描述及組合的研究很多，但這些基于Petri網(wǎng)的Web服務(wù)描述研究都沒有考慮Web服務(wù)的實時性與智能性因素，不適合用于分布式實時系統(tǒng)中的服務(wù)描述與組合建模。本文提出的層次實時有色Petri網(wǎng)能很好地對實時服務(wù)進行形式化描述模型，采用OWL-S表示共享領(lǐng)域知識來保證服務(wù)的智能性，并構(gòu)建了模型的簡化算法及證明了。未來工作將構(gòu)建本文提出實時服務(wù)模型在一些典型實時系統(tǒng)中的原型應(yīng)用，進一步優(yōu)化模型的組合算法，更好地滿足實時性與可信性要求。

參考文獻

[1]翟正利，楊楊.基于模糊Petri網(wǎng)和本體的網(wǎng)格服務(wù)發(fā)現(xiàn)[J].北京科技大學學報，2006，12（28）：p1196-1201.

[2]PengCheng Xiong，YuShun and MenChu Zhou.A Petri Net Approach to Analysis and Composition of Web Services[J].IEEE TRANSACTIONS ON SYSTEMS，MAN，AND CYBERNETICS—PART A：SYSTEMS AND HUMANS，VOL.40，NO.2，MARCH201：p376-387.

[3]吳哲輝著.Petri網(wǎng)導論[M].機械工業(yè)出版社，2006：p215-220.

[4]袁崇義著.Petri網(wǎng)原理與應(yīng)用[M].電子工業(yè)出版社，2005：p95-103.

[5]劉銘，張國印等.基于層次實時有色Petri網(wǎng)的實時系統(tǒng)建模與分析方法研究[J].電子與信息學報，2011，3（33）：p580-586.

[6]王璞巍，金芝.Web服務(wù)語義描述研究綜述[J].南京大學學報（自然科學），2005，10（41）：p462-469.

[7]Yaojun Han，Xuemei Luo.Composition and Reduction of Web Service Based on Dynamic Timed Colored Petri Nets[C]//2009 IEEE International Symposium on Parallel and Distributed Processing with Applications.p659-663.

[8]Yaojun Han，Changjun Jiang and Xuemei Luo.Modeling and Analysis for Grid Service Cooperative Scheduling Based on Petri Nets[C]//Cooperative Design， Visualization，and Engineering Lecture Notes in Computer Science Volume 4674，2007：p104-112.

作者簡介

卓國鋒（1974-），男，江西省鄱陽縣人。碩士學位。講師，研究方向為件技術(shù)、信息安全。

作者單位

成都職業(yè)技術(shù)學院軟件分院 四川省成都市 610041