基于Petri網(wǎng)的服務(wù)流程結(jié)構(gòu)健壯性判定

高 強(qiáng)，胡 強(qiáng)

(1.山東省人大常委會辦公廳信息中心,山東 濟(jì)南 250011； 2.青島科技大學(xué)信息科學(xué)技術(shù)學(xué)院,山東 青島 266061)

0 引 言

隨著云計算技術(shù)的發(fā)展，軟件服務(wù)化成為了基于互聯(lián)網(wǎng)的軟件開發(fā)與部署表現(xiàn)出來的主要特征。通過互聯(lián)網(wǎng)和云計算平臺尋租符合自己需求的服務(wù)，是用戶調(diào)用企業(yè)業(yè)務(wù)功能的一種流行方式[1]。其中，Web服務(wù)經(jīng)過近30年的發(fā)展，已經(jīng)逐漸成為當(dāng)前企業(yè)通過互聯(lián)網(wǎng)開發(fā)、封裝和發(fā)布業(yè)務(wù)功能的主要模式。

在進(jìn)行業(yè)務(wù)集成時，用戶只需要按照指定的格式調(diào)用發(fā)布在云平臺或者領(lǐng)域服務(wù)注冊中心的Web服務(wù)，即可遠(yuǎn)程使用所綁定服務(wù)的內(nèi)部業(yè)務(wù)功能，不需要了解Web服務(wù)的實現(xiàn)細(xì)節(jié)，進(jìn)而極大地縮減了開發(fā)周期和成本[2]。為了便于用戶調(diào)用，Web服務(wù)內(nèi)部通常不包含復(fù)雜的業(yè)務(wù)邏輯。因此，在應(yīng)對復(fù)雜服務(wù)請求時大多需要通過服務(wù)組合的方式構(gòu)建服務(wù)流程[3]。

已有研究工作中提出了眾多的服務(wù)組合方法[4]，通過上述成果可以構(gòu)建適用不同應(yīng)用場景的組合服務(wù)流程。例如，Lu等[5]提出一種基于知識約束規(guī)則推理的云服務(wù)資源組合方法；朱李楠等[6]提出基于改進(jìn)差分進(jìn)化算法的云制造資源優(yōu)化組合方法；Ye等[7]提出基于貝葉斯網(wǎng)絡(luò)經(jīng)濟(jì)模型的云服務(wù)組合，以及崔立真等[8]提出面向歷史流程軌跡與個性偏好的流程動態(tài)定制方法等。

在構(gòu)建了組合服務(wù)流程后，流程的結(jié)構(gòu)健壯性直接影響到了組合服務(wù)流程的結(jié)構(gòu)質(zhì)量和執(zhí)行效果。在流程健壯性方面，研究者從不同角度給出健壯性的定義和判定方法。例如，Clempner[9]提出一種基于軌跡跟蹤方法檢測流程健壯性的規(guī)則，Du等[10]提出一種基于流程交互行為的健壯性判定標(biāo)準(zhǔn)。Martens[11]提出了一種基于流程可用性的弱健壯性概念，F(xiàn)ahland等[12]將健壯性定義為流程不存在死鎖和同步缺失。余陽等[13]從結(jié)構(gòu)的自由同步與良構(gòu)等角度研究了時態(tài)工作流過程模型的結(jié)構(gòu)合理性。胡強(qiáng)等[14]針對組合服務(wù)流程的結(jié)構(gòu)合理性提出了結(jié)構(gòu)范式概念，并基于邏輯Petri網(wǎng)建立了不同級別結(jié)構(gòu)范式的判定方法。

然而，已有的研究工作通常僅對健壯性給出定性評價，缺乏對服務(wù)流程的結(jié)構(gòu)健壯性分層次定量評價，因此難以精準(zhǔn)評價流程結(jié)構(gòu)質(zhì)量[15]。

本文針對組合服務(wù)流程的結(jié)構(gòu)健壯性判定問題，采用Petri網(wǎng)作為服務(wù)流程建模的形式化工具，借鑒工作流網(wǎng)的健壯性判定思想，提出一種基于Petri網(wǎng)建模的服務(wù)流程結(jié)構(gòu)健壯性分層定量判定方法。

1 服務(wù)網(wǎng)及相關(guān)理論

定義1Petri網(wǎng)[16]。

Petri網(wǎng)是一個四元組S=(P,T,F,M)，P為庫所集合，T為變遷集合，且P∩T=；F(PT)(TP)是弧的集合，映射M:P={0,1,2,…}是Petri網(wǎng)的標(biāo)識函數(shù)，表示了庫所中的托肯數(shù)目，變遷觸發(fā)后可以通過如下公式計算：

定義2服務(wù)網(wǎng)[17]。

服務(wù)網(wǎng)定義為四元組SN=(S, i, o, L)，各組成項含義如下：

1)S是組合服務(wù)流程的過程模型，其中：①P=Pc∪Pd，Pd是表示與外部進(jìn)行數(shù)據(jù)交換的數(shù)據(jù)庫所集合，Pc是控制庫所集合；②T是服務(wù)流程對應(yīng)的Web服務(wù)集合；③F是服務(wù)狀態(tài)流程轉(zhuǎn)換弧的集合；④M為標(biāo)識函數(shù)，初始標(biāo)識為M0，即M0(i)=1。

3)L:T→Θ為標(biāo)記函數(shù)，Θ為操作函數(shù)名稱的集合。

定義3服務(wù)進(jìn)程網(wǎng)。

若SN=(S, i, o, L)為服務(wù)網(wǎng)，令SPN=(S′,i,o,L),其中P′=Pc,T′=T,F′=F-{PdT∪TPd}，則SPN稱為SN的服務(wù)進(jìn)程網(wǎng)。

圖1 服務(wù)網(wǎng)及服務(wù)進(jìn)程網(wǎng)示例

定義4等價服務(wù)流程。

SN1=(S1, i1, o1, L1)和SN2=(S2, i2, o2, L2)為2個服務(wù)網(wǎng)，SN1和SN2稱為等價服務(wù)流程當(dāng)且僅當(dāng)存在映射使得以下條件成立：

定義5投影服務(wù)流程。

SN=(S, i, o, L)為一服務(wù)網(wǎng)，SN′=(S′, i′, o′, L′)稱為SN的投影服務(wù)流程，當(dāng)且僅當(dāng)F′=F∩S′,P′=P∩(1(F′)∪2(F′)),T′=T∩(1(F′)∪2(F′)),L′=Θ(T′)，表示為SN′=S(SN)。此處，1和2定義如下:1(F)={x|y:(x,y)F},2(F)={y|x:(x,y)F}。

定理1

令SN1′=S(SN1),SN2′=(SN2),若SSN1.則

證明：

令S2=T2=P2=;

{S2=S2∪((x),(y)); T2=T2∪((x,y)(SN1′).T); P2=P2∪((x,y)(SN1′).P);}

令L2=Θ(T2),(S)=S2,SN2′=(P2,T2,S2,L2);

[證畢]

2 結(jié)構(gòu)健壯性的層次劃分及其判定

目前，有關(guān)流程結(jié)構(gòu)健壯性的研究均是采用定性判定的方式。就組合服務(wù)流程而言，僅僅以是否健壯來評價服務(wù)流程的結(jié)構(gòu)質(zhì)量是不完善與不合理的。因此，本文提出將服務(wù)流程的結(jié)構(gòu)健壯性劃分為4個層次，并給出4個層次健壯性的判定算法。下面首先給出4個層次的結(jié)構(gòu)健壯性劃分準(zhǔn)則：

1)1LS：服務(wù)流程S是第一層次健壯的，當(dāng)其對應(yīng)的服務(wù)網(wǎng)SN中i至o庫所存在一條可達(dá)路徑。

2)2LS：服務(wù)流程S是第二層次健壯的，當(dāng)其對應(yīng)的服務(wù)網(wǎng)SN中i至o庫所的任意路徑可達(dá)。

3)3LS：服務(wù)流程S是第三層次健壯的，當(dāng)其對應(yīng)的服務(wù)網(wǎng)SN是2LS，且不存在重復(fù)的并發(fā)或選擇服務(wù)流程。

4)4LS：服務(wù)流程S是第四層次健壯的，當(dāng)其對應(yīng)的服務(wù)網(wǎng)SN是3LS，且不存在重復(fù)子服務(wù)流程。

在上述4個層次的健壯性劃分中，第一層次是要求服務(wù)流程存在可達(dá)的連通路徑，該層次可以確保服務(wù)流程存在可以對外提供服務(wù)的業(yè)務(wù)流程路徑；第二層次健壯性則是保障了服務(wù)網(wǎng)中的所有業(yè)務(wù)流程功能路徑是可以執(zhí)行的；第三層次保障在并發(fā)和選擇結(jié)構(gòu)中不存在冗余服務(wù)流程結(jié)構(gòu)；第四層次則是要求服務(wù)流程中不存在重復(fù)服務(wù)流程，對重復(fù)的服務(wù)流程應(yīng)該將其抽象為子服務(wù)流程替代，從而保證結(jié)構(gòu)的清晰與簡潔。

在進(jìn)行服務(wù)流程的健壯性判定時，首先要建立服務(wù)流程所對應(yīng)的服務(wù)網(wǎng)模型，目前組合Web服務(wù)流程多采用WS-BPEL進(jìn)行描述[18]。為了獲得服務(wù)流程的服務(wù)網(wǎng)模型，需要對給定服務(wù)流程的WS-BPEL文件進(jìn)行遍歷，具體轉(zhuǎn)換規(guī)則如圖2所示。

圖2 WS-BPEL與服務(wù)網(wǎng)之間的映射規(guī)則圖

算法1為服務(wù)流程結(jié)構(gòu)健壯性層次判定算法。在該算法執(zhí)行的過程中，首先調(diào)用Petri網(wǎng)的活性判定算法[19]。如果服務(wù)流程對應(yīng)的服務(wù)網(wǎng)為弱活的，則為第一層次健壯性；若對應(yīng)的服務(wù)網(wǎng)是活的，則是第二層次健壯性。然后，對服務(wù)流程文件中所有存在的switch、if、pick以及flow結(jié)構(gòu)進(jìn)行檢測，驗證是否存在冗余的子流程結(jié)構(gòu)。如不存在，則是第三層次健壯性。最后，檢驗是否存在重復(fù)子流程。若不存在，則是第四層次健壯性。

算法1服務(wù)流程結(jié)構(gòu)健壯性判定算法

SoundnessLevel(S)

輸入：WS-BPEL格式描述的服務(wù)流程S

輸出：S的結(jié)構(gòu)健壯性層次

{construct the service net SN of S;

Invoke the live determination algorithm of Petri net

if (SN is weaklive) then LS:=1;

if (SN is live) then LS:=2;

for each structure F in {switch, if, pick, flow}

for each substructure fi and fj in F

if (flag1=true) then LS:=3;

for all the substructure in S

if there is no repetitive one then LS:=4;

return LS;

}

3 算 例

本章以網(wǎng)上在線交易系統(tǒng)所對應(yīng)的服務(wù)流程為例，說明不同服務(wù)流程的結(jié)構(gòu)健壯性層次。圖3給出了交易系統(tǒng)的業(yè)務(wù)邏輯示意圖，圖3左側(cè)部分為賣家流程，右側(cè)部分為買家流程。買家流程業(yè)務(wù)邏輯為：查詢商品，如果不存在滿足需求的商品則處理失??；如存在，則觸發(fā)預(yù)定、購買和接收商品流程。

圖3 第四層次健壯性服務(wù)網(wǎng)

賣家流程業(yè)務(wù)邏輯為：接收用戶查詢，查詢庫存，如果不存在對應(yīng)商品則查詢失??；否則，接收預(yù)定、付款，快遞商品。按照算法1可知，圖3所對應(yīng)的服務(wù)流程的結(jié)構(gòu)健壯性為第四層次。在圖4中，所有的業(yè)務(wù)分支邏輯均與圖3相同，但是買家和賣家使用了相同的子流程，即book-pay-delivery。因此，圖4中的服務(wù)流程結(jié)構(gòu)健壯性為第三層次。

圖4 第三層次健壯性服務(wù)網(wǎng)

圖5 第二層次健壯性服務(wù)網(wǎng)

圖6 第一層次健壯性服務(wù)網(wǎng)

如果在賣家服務(wù)流程中增加一個子服務(wù)流程：reserve-defray-express，則reserve-defray-express與book-pay-delivery子流程并發(fā)冗余，因此圖5中的服務(wù)流程結(jié)構(gòu)健壯性為第二層次。

如果將子流程reserve-defray-express更換為reserve-express-defray，則該流程仍是第三層次健壯。圖6中的服務(wù)流程與圖3相似，但是在買家流程中將express與defray服務(wù)交換，形成死鎖。因此，并不是所有路徑均可達(dá)，其流程結(jié)構(gòu)健壯性為第一層次。

4 結(jié)束語

服務(wù)流程的結(jié)構(gòu)健壯性決定了組合產(chǎn)生的Web服務(wù)業(yè)務(wù)流程的結(jié)構(gòu)質(zhì)量，是Web服務(wù)組合研究中的一個重要問題。本文借助于Petri網(wǎng)將WS-BPEL描述的組合服務(wù)流程建模為服務(wù)網(wǎng)，根據(jù)流程的可達(dá)性與冗余性，提出了4個層次的服務(wù)流程結(jié)構(gòu)健壯性，并借助服務(wù)網(wǎng)的結(jié)構(gòu)性質(zhì)進(jìn)行表征。文中給出了不同層次結(jié)構(gòu)健壯性的判定算法，并通過網(wǎng)上在線交易服務(wù)流程為背景，給出不同層次結(jié)構(gòu)健壯性的算例。下一步工作主要是研究不同級別的結(jié)構(gòu)健壯性在流程業(yè)務(wù)演化過程的健壯性級別保持問題。