可靠服務(wù)組合的協(xié)調(diào)策略與分析

1、可靠服務(wù)組合的協(xié)調(diào)策略與分析* 本課題得到國家自然科學(xué)基金(60473055，60773094)及上海市曙光計劃（07SG32）資助范貴生，男，1980年生，博士研究生，主要研究方向為軟件工程，面向服務(wù)計算，形式化方法，E-mail: gs_fan；劉冬梅，女，1970年生，博士研究生，主要研究方向為軟件工程，面向服務(wù)計算，形式化方法；陳麗瓊，女，1982年生，博士研究生，主要研究方向為分布式計算，嵌入式系統(tǒng)，形式化方法；虞慧群，男，1967年生，博士，教授，博士生導(dǎo)師，IEEE高級會員，ACM會員，. 主要研究方向為軟件工程，信息安全，形式化方法范貴生 劉冬梅 陳麗瓊 虞慧群(華東理工大學(xué)計

2、算機(jī)科學(xué)與工程系, 上海 200237)摘 要：服務(wù)組合是構(gòu)建復(fù)雜Web軟件的有效方法，但服務(wù)事務(wù)狀態(tài)的多樣性使得服務(wù)組合的可靠性難以保證。為此，提出一種構(gòu)造可靠服務(wù)組合的協(xié)調(diào)方法。該方法采用Petri網(wǎng)對工作流建模，以清晰地表達(dá)任務(wù)及任務(wù)之間的邏輯關(guān)系。在此基礎(chǔ)上，根據(jù)服務(wù)的事務(wù)屬性及服務(wù)組合的失效處理機(jī)制建立服務(wù)組合的失效處理模型，并提出一種構(gòu)造可靠服務(wù)組合的協(xié)調(diào)策略及實施方法。利用Petri網(wǎng)相關(guān)理論證明該策略的有效性。旅游服務(wù)實例演示了協(xié)調(diào)技術(shù)的應(yīng)用方法及其可行性。關(guān)鍵詞Petri網(wǎng)；Web服務(wù)；服務(wù)組合；事務(wù)；可靠性1 引言隨著Internet技術(shù)應(yīng)用的迅速發(fā)展，基于Web服務(wù)的分布

3、式計算模式已經(jīng)成為軟件發(fā)展的趨勢。Web服務(wù)能夠統(tǒng)一地封裝信息、行為以及業(yè)務(wù)流程，而無需考慮應(yīng)用所在的環(huán)境。通過Web服務(wù)組合來動態(tài)生成新的應(yīng)用系統(tǒng)，以滿足實際的需要，已成為Web服務(wù)技術(shù)不斷向前發(fā)展的技術(shù)動力1。然而，Web服務(wù)事務(wù)狀態(tài)的多樣性使得服務(wù)組合變得更為可靠和有效之前，還有一些問題需要處理。其中關(guān)鍵問題就是如何構(gòu)建可靠服務(wù)組合，即如何根據(jù)服務(wù)的事務(wù)屬性來分配可用服務(wù)以滿足服務(wù)消費(fèi)者的需求。雖然傳統(tǒng)的事務(wù)技術(shù)在數(shù)據(jù)庫系統(tǒng)和分布式系統(tǒng)中得到了廣泛的應(yīng)用，但由于Web服務(wù)自身的松耦合性、運(yùn)行時間長、長事務(wù)等特點(diǎn)，使其在系統(tǒng)的可靠性和一致性方面面臨新的挑戰(zhàn)，如何對服務(wù)的事務(wù)屬性進(jìn)行形式化分

4、析成為業(yè)界廣泛討論并關(guān)注的問題2。Petri網(wǎng)作為一種直觀的圖形建模工具和一種具有豐富數(shù)學(xué)基礎(chǔ)的形式化模型，可以廣泛應(yīng)用于描述和研究并發(fā)、異步和分布式特征的系統(tǒng)，并提供了一種可操作語義及定性和定量分析3。最近的研究表明，Petri網(wǎng)適合用來描述服務(wù)組合的特性4,17。而可靠服務(wù)組合的構(gòu)建不僅可以滿足服務(wù)消費(fèi)者的功能需求，同時也能反應(yīng)出服務(wù)的事務(wù)屬性及失效處理。Petri網(wǎng)及其相關(guān)的分析方法為這些目標(biāo)實現(xiàn)提供了理論基礎(chǔ)。本文要解決的就是如何根據(jù)服務(wù)消費(fèi)者的需求來動態(tài)地分配可用服務(wù)，以構(gòu)建所需的可靠服務(wù)組合。為此，提出一種基于Petri網(wǎng)構(gòu)建可靠服務(wù)組合的方法。基本思路為：首先利用Petri網(wǎng)對任

5、務(wù)及任務(wù)間的關(guān)系進(jìn)行建模，生成相應(yīng)的工作流模型；其次針對服務(wù)的事務(wù)屬性，構(gòu)建服務(wù)組合的失效處理模型（Service Compositions Failure Processing, SCFP），并分析SCFP模型的動態(tài)性質(zhì)，從而保證所得到模型的正確性；最后給出可靠服務(wù)組合的定義，分析可靠服務(wù)組合構(gòu)造的充分必要條件，提出相應(yīng)的協(xié)調(diào)策略并證明其有效性，同時給出協(xié)調(diào)策略的具體實施。本文第2節(jié)給出了工作流的Petri網(wǎng)模型；第3節(jié)分析服務(wù)的事務(wù)屬性和服務(wù)組合的失效處理機(jī)制，生成相應(yīng)的SCFP模型；第4節(jié)提出可靠服務(wù)組合的協(xié)調(diào)策略及實施方法；第5節(jié)通過具體實例說明可靠服務(wù)組合的構(gòu)建與分析過程；第6節(jié)闡述

6、了相關(guān)的研究工作；最后是結(jié)論和下一步工作。2 工作流的Petri網(wǎng)模型服務(wù)組合的功能可以由多個獨(dú)立運(yùn)行的子功能構(gòu)成，本文將每個子功能稱為任務(wù)。在服務(wù)組合流程中，每個任務(wù)會有多個可用服務(wù)與之對應(yīng)。本文假設(shè)每個服務(wù)只能完成一個任務(wù)的功能，因此在服務(wù)組合中服務(wù)和任務(wù)是一一對應(yīng)的。帶事務(wù)屬性的服務(wù)組合流程可以從工作流和失效處理兩方面進(jìn)行描述15，工作流描述任務(wù)之間的數(shù)據(jù)通信或同步，具體說明了任務(wù)組件之間的關(guān)系，直觀上可以理解為一系列任務(wù)的依賴關(guān)系。而服務(wù)組合的失效處理則規(guī)約了服務(wù)運(yùn)行失敗時的處理機(jī)制，定義了服務(wù)的事務(wù)屬性和服務(wù)的失敗處理。兩者主要區(qū)別是：前者假設(shè)服務(wù)還沒分配，僅僅描述服務(wù)組合流程的數(shù)據(jù)

7、依賴；后者假設(shè)服務(wù)已經(jīng)分配，主要考慮服務(wù)的事務(wù)屬性和服務(wù)失敗處理。本節(jié)依據(jù)服務(wù)消費(fèi)者提供的功能需求，利用Petri網(wǎng)的基本原理，按接口匹配的原則建立系統(tǒng)的工作流模型。2.1 任務(wù)Petri網(wǎng)模型由于系統(tǒng)的功能是由一系列任務(wù)組合而成，而任務(wù)的組合又可以構(gòu)成一個新的任務(wù)，如此嵌套可以構(gòu)造出任意復(fù)雜的系統(tǒng)。因此，可利用Petri網(wǎng)對任務(wù)進(jìn)行建模，且每個任務(wù)在運(yùn)行過程中需要輸入某些參數(shù)和輸出一定的結(jié)果。下面給出任務(wù)的形式化定義。定義1：有界Petri網(wǎng)C=(P,T,F)稱作任務(wù)，其中：（1）P=PSPI是一個有限庫所集，PI表示任務(wù)的接口，PS表示任務(wù)的位置，其中PSPI=F；（2）T是一個有限的變遷

8、集，m0，并且PTF, PT=F；（3）F(PT)(TP)是有向弧集合，F(xiàn)稱為流關(guān)系；圖1 帶有接口的任務(wù)C1在任務(wù)模型中，接口代表該任務(wù)輸入或輸出（參數(shù)則映射為庫所中的令牌）。本文假設(shè)任務(wù)只有獲得所需參數(shù)才能運(yùn)行開始操作，且運(yùn)行結(jié)束后統(tǒng)一輸出參數(shù)，具體接口個數(shù)可以根據(jù)實際情況增減。圖1中的任務(wù)C1有三個接口：庫所Pi1和Pi2存放任務(wù)開始操作（tin）所需的參數(shù)，而庫所Pi3則存放任務(wù)結(jié)束（tin）的輸出結(jié)果。Pin, Pe表示任務(wù)C1的開始和結(jié)束位置。某時刻各庫所中令牌的分布狀況稱為任務(wù)的標(biāo)識，在標(biāo)識M下，庫所p中的令牌數(shù)量記為M(p)；變遷t在標(biāo)識M下使能的，記做Mt，否則記做Mt表示順

9、序：CiCj表示任務(wù)Ci和Cj順序運(yùn)行，即Cj只有在Ci運(yùn)行結(jié)束后才能開始。（2）算子+表示選擇：Ci+Cj表示任務(wù)Ci和Cj只有一個可以運(yùn)行。（3）算子|表示并行：Ci|Cj表示任務(wù)Ci和Cj可以同時運(yùn)行，但要它們都執(zhí)行結(jié)束后整個組合才算執(zhí)行結(jié)束。通過采用上述的算子可以將任務(wù)間的關(guān)系描述為一個表達(dá)式。將在任務(wù)Ci運(yùn)行時刻已經(jīng)結(jié)束的任務(wù)稱為Ci的前向任務(wù)，而Ci運(yùn)行結(jié)束時還未開始的任務(wù)稱為Ci的后向任務(wù)。為了區(qū)別任務(wù)的操作，在相應(yīng)的變遷和庫所前標(biāo)注對應(yīng)的任務(wù)。如任務(wù)Ci中的開始變遷，表示為Citin。如果變遷是為了描述任務(wù)間關(guān)系而引入，則不標(biāo)注。順序結(jié)構(gòu)允許兩個任務(wù)Ci和Cj順序地執(zhí)行，當(dāng)一個

10、任務(wù)需要用到另外一個任務(wù)的輸出時就要使用順序結(jié)構(gòu)來組合。順序運(yùn)行CiCj的Petri網(wǎng)模型如圖2所示。在Ci和Cj中引入接口Pij使得，Pij=Cite，Pij=Cjtin。Pij的存在使得任務(wù)Cj只能在Ci結(jié)束之后開始運(yùn)行。圖2 順序關(guān)系的建模為了構(gòu)造任務(wù)間的并行，選擇和循環(huán)關(guān)系，需要分別對任務(wù)間的兩對基本組件即AND-split和OR-split，AND-join和OR-join進(jìn)行建模，具體的Petri網(wǎng)模型如圖3所示（設(shè)任務(wù)Ck是Ci1,Ci2, ,Cim的共同前向/后向任務(wù)）。AND-split的Petri網(wǎng)模型如圖3（a）所示：在Ck中引入接口Pki1, Pki2, , Pkim，

11、每個并行的任務(wù)Cij中引入接口Pkij。其中Pkij=Ckte, Pkij=Cijtin, j=1, 2, , n。OR-split的Petri網(wǎng)模型如圖3（b）所示：在Ck和所有的選擇任務(wù)中引入接口Pij使得Pij=Ckte, Pij=Ci1tin, Ci2tin, , Cimtin。AND-join的Petri網(wǎng)模型如圖3（c）所示：在Ck中引入接口Pki1, Pki2, , Pkim，每個并行的任務(wù)Cij中引入接口Pkij。其中Pkij=Cktin, Pkij=Cijte, j=1, 2, n。OR-join的Petri網(wǎng)模型如圖3（d）所示：在Ck和所有的選擇任務(wù)中引入接口Pij使得P

12、ij=Cktin, Pij=Ci1te, Ci2te, Cimte。圖3 基本組件的建模下面結(jié)合Petri網(wǎng)的合成運(yùn)算，匹配相應(yīng)的接口以構(gòu)造整個系統(tǒng)的工作流模型。定義2：設(shè)系統(tǒng)中的任務(wù)Ci=(Pi,Ti,Fi)，則按照下列步驟構(gòu)造的五元組S=(C;P,T,F,M0)稱為系統(tǒng)的工作流模型： （1）C=C1, C2, , Cn，n為系統(tǒng)中任務(wù)的個數(shù)；（2）依據(jù)任務(wù)間關(guān)系，合成C1, C2, , Cn的對應(yīng)接口；（3）引入變遷Tstart和庫所Pstart分別描述整個系統(tǒng)的初始位置和開始操作，且：Tstart=Pstart, Tstart=Ci1Pin, Ci2Pin, , CinPin, Psta

13、rt=F, Pstart=Tstart；（4）設(shè)置初始標(biāo)識M0(Pstart)=1，其余庫所為0。工作流模型描述整個系統(tǒng)所能完成的功能，對工作流模型中每個任務(wù)分配具體的服務(wù)則構(gòu)成了服務(wù)組合。如果分配過程中考慮服務(wù)的事務(wù)屬性，則稱它為帶事務(wù)屬性的服務(wù)組合。本文中如無特殊說明，服務(wù)組合均指帶事務(wù)屬性的服務(wù)組合。下面根據(jù)所得的工作流模型構(gòu)造服務(wù)組合的失效處理模型。3 服務(wù)組合的失效處理模型3.1 服務(wù)的事務(wù)屬性由于Web服務(wù)自身的特點(diǎn)，使得傳統(tǒng)的事務(wù)處理技術(shù)無法直接應(yīng)用在Web服務(wù)事務(wù)的處理過程，文獻(xiàn)7提出的模型指明了服務(wù)事務(wù)屬性的語義，該模型是基于文獻(xiàn)8所考慮的三種不同的類型的事務(wù)屬性。由此可以延

14、伸Web服務(wù)執(zhí)行任務(wù)時主要有下面三種特性：可重復(fù)的（r），可補(bǔ)償?shù)模╟p），不可補(bǔ)償也不可重復(fù)的（p）。相應(yīng)的服務(wù)事務(wù)屬性可以有以下幾種情況：cp、p、r、r,cp。根據(jù)服務(wù)的事務(wù)屬性，可以建立如圖4所示的模型。圖4（a）是對可補(bǔ)償?shù)姆?wù)進(jìn)行建模，PItr表示該服務(wù)事務(wù)處理的條件。庫所SiPItr中有令牌表示服務(wù)組合中有其它服務(wù)失敗，需要根據(jù)服務(wù)Si的事務(wù)屬性進(jìn)行相應(yīng)的協(xié)調(diào)。而服務(wù)的輸入和輸出（PIin, PIe）根據(jù)實際需要可以進(jìn)行增減。可補(bǔ)償服務(wù)的運(yùn)行過程可能處于初始、運(yùn)行、結(jié)束、中斷、取消、補(bǔ)償和失敗位置，其中Pin, Pac, Pe,Pab, Pca, Pcp, Pfa稱為任務(wù)的位置庫

15、所。其它的事務(wù)屬性可以用類似的方法進(jìn)行描述，具體的模型如圖4(b)圖4(d)。圖4 服務(wù)的事務(wù)屬性模型 通過對圖4的分析可知，事務(wù)屬性不同的服務(wù)，運(yùn)行過程可能到達(dá)的位置集和操作也不同。圖4中庫所和變遷的實際映射如表1所示：表1 事務(wù)屬性模型中變遷和庫所的對照P/T位置/操作P/T位置/操作P/T位置/操作Pin初始位置Pab中斷位置Pfa失敗位置Pe結(jié)束位置Pca取消位置Pcp補(bǔ)償位置Pac運(yùn)行位置PIe結(jié)束輸出PIc失敗輸出PItr事務(wù)輸入PIin運(yùn)行輸入tin運(yùn)行操作tca取消操作trt重試操作tfa失敗操作tcp補(bǔ)償操作tab中斷操作te結(jié)束操作從表1可知，采用Petri網(wǎng)可以精確地描述

16、服務(wù)的事務(wù)屬性。將初始、運(yùn)行、結(jié)束和失敗位置稱為服務(wù)的運(yùn)行位置，而中斷、取消和補(bǔ)償位置稱為服務(wù)的事務(wù)位置。3.2 服務(wù)組合的失效處理模型由于每個服務(wù)具有自身的事務(wù)屬性。當(dāng)某個服務(wù)運(yùn)行失敗時，如何協(xié)調(diào)其它服務(wù)，保證整個系統(tǒng)的可靠運(yùn)行，成為服務(wù)組合中必須解決的一個問題。本文引入失效處理模塊（FCM）來處理該問題。假設(shè)同一時刻系統(tǒng)中最多有一個服務(wù)失敗，其服務(wù)失敗處理時間可以忽略。由于實際情況中有些任務(wù)是不可取消的也不可以補(bǔ)償?shù)模∟CC），這類任務(wù)所對應(yīng)的服務(wù)協(xié)調(diào)操作比較特殊。如其它服務(wù)失敗的時刻該服務(wù)處于運(yùn)行位置，則協(xié)調(diào)其到達(dá)結(jié)束位置。其對應(yīng)的服務(wù)模型如圖5所示，其中tce是服務(wù)的協(xié)調(diào)操作。與結(jié)束操

17、作te不同的是，該操作雖然也能讓服務(wù)運(yùn)行結(jié)束，但不輸出結(jié)果。圖5 不可取消任務(wù)對應(yīng)的服務(wù)模型不妨設(shè)服務(wù)Si是完成Ci的功能，則服務(wù)組合的失效處理機(jī)制有：（1）設(shè)任務(wù)Ci是Cj的前向任務(wù)，若服務(wù)Si失敗，則中斷服務(wù)Sj。（2）設(shè)任務(wù)Ci是Cj的前向任務(wù)，若服務(wù)Sj失敗，分兩種情況協(xié)調(diào)Si：服務(wù)Si是可補(bǔ)償?shù)?，則對Si進(jìn)行補(bǔ)償；服務(wù)Si是不可補(bǔ)償?shù)?，則不做任何操作，服務(wù)Sj停留在結(jié)束位置。（3）設(shè)任務(wù)Ci是Cj并行運(yùn)行，若服務(wù)Si失敗，分四種情況協(xié)調(diào)Sj：服務(wù)Sj處在運(yùn)行位置且任務(wù)Cj可取消的，則取消Sj的運(yùn)行；服務(wù)Sj處在運(yùn)行位置且任務(wù)Cj不可取消的，則協(xié)調(diào)Sj的運(yùn)行使其到達(dá)結(jié)束位置；服務(wù)Sj處

18、在結(jié)束位置且Sj是可補(bǔ)償?shù)?，則對Sj運(yùn)行補(bǔ)償；服務(wù)Sj處在結(jié)束位置且Sj是不可補(bǔ)償?shù)?，則不做任何操作，服務(wù)Sj停留在結(jié)束位置。失效處理模塊的功能為：當(dāng)系統(tǒng)中某個服務(wù)運(yùn)行失敗時，基于上述處理機(jī)制，依據(jù)其它服務(wù)的事務(wù)屬性協(xié)調(diào)系統(tǒng)結(jié)束。下面對FCM進(jìn)行建模（同理在變遷和庫所之前標(biāo)注對應(yīng)的服務(wù)）。引進(jìn)庫所Pc和變遷tc分別表示系統(tǒng)協(xié)調(diào)的初始位置和協(xié)調(diào)操作，使得：（1）Pc=S1tfa, S2tfa, , Sktfa, Pc=tc（2）tc=Pc, tc=S1PItr, S2PItr, , SnPItr條件（1）表明服務(wù)組合中若有服務(wù)失敗則調(diào)用FCM模型；條件（2）描述了FCM模塊給每個服務(wù)都輸入事務(wù)處

19、理參數(shù)。若對工作流模型S中的每個任務(wù)都分配一個服務(wù)，則構(gòu)成了具體的服務(wù)組合，不妨設(shè)S為分配好的服務(wù)集?；诖?，下面給出服務(wù)組合的失效處理模型形式化定義：定義3：工作流模型S，S是所分配的服務(wù)集，則按照下列步驟構(gòu)造的四元組SS=(Ps,Ts,Fs;Ms0)稱為服務(wù)組合的失效處理模型（Service Compositions Failure Processing, SCFP）：（1）根據(jù)服務(wù)的事務(wù)屬性建模構(gòu)造S集合中每個服務(wù)的Petri網(wǎng)模型；（2）按照S中的數(shù)據(jù)流程合成服務(wù)的Petri網(wǎng)模型；（3）依據(jù)上述FCM模型的建模方式添加相應(yīng)的變遷和庫所。（4）保持S中的初始狀態(tài)不變。從定義3可以看出S

20、CFP模型是在工作流模型S的基礎(chǔ)上對帶事務(wù)特性的服務(wù)組合進(jìn)行建模。3.3 模型性質(zhì)本文中系統(tǒng)狀態(tài)由標(biāo)識M表示，如M(CiPe )=1表示在狀態(tài)M下，任務(wù)Ci已經(jīng)運(yùn)行結(jié)束。將任務(wù)Ci在狀態(tài)Ma中不為零的庫所記作Mai。下面分析SCFP模型的一些主要性質(zhì)。性質(zhì)1：SCFP模型SS中，任一可達(dá)狀態(tài)M下的每個服務(wù)都只能處于一個位置。證明：從建模過程SS可知，服務(wù)Si的位置庫所滿足庫所不變量：M(SiPin)+M(SiPac)+M(SiPca)+M(SiPfa)+ M(SiPe)+M(SiPab)+M(SiPcp)=1。而服務(wù)組合一旦運(yùn)行，會對每個服務(wù)進(jìn)行初始化（變遷Tstart），即輸入令牌到庫所Si

21、Pin。根據(jù)Petri網(wǎng)的運(yùn)行機(jī)制可得：服務(wù)只能處于初始、運(yùn)行、取消、失敗、結(jié)束、中斷和補(bǔ)償位置中的一個。 證畢同一個SCFP模型由于任務(wù)對應(yīng)的服務(wù)失敗時刻不同，系統(tǒng)的終止位置也會不同。按照任務(wù)間的關(guān)系計算出工作流模型S的所有可能終止?fàn)顟B(tài)，記為TS(S)。其中TS(S)=METSF(S)：（1）正常終止?fàn)顟B(tài)ME：i1,nME(CiPe)=1，ME表示系統(tǒng)中所有任務(wù)都正常結(jié)束的狀態(tài)。對于一個工作流模型，其正常終止?fàn)顟B(tài)唯一。（2）失敗終止?fàn)顟B(tài)集合TSF(S)：MFTSF(S)有$i1,nMF(CiPfa)=1，MF(CiPfa)表示系統(tǒng)中任務(wù)Ci失敗，經(jīng)過系統(tǒng)協(xié)調(diào)到達(dá)的終止?fàn)顟B(tài)，也稱MF(CiPf

22、a)是Ci的失敗終止?fàn)顟B(tài)。記集合TSF(S,Ci)是任務(wù)Ci在TSF(S)中的所有失敗終止?fàn)顟B(tài)集合。在服務(wù)組合中，失效處理機(jī)制是系統(tǒng)的核心。因此有必要分析建立的模型是否保證該處理機(jī)制。性質(zhì)2：SCFP模型SS保證了服務(wù)組合的失效處理機(jī)制。證明：（1）證明SS保證了服務(wù)組合的失效處理機(jī)制（1）設(shè)任務(wù)Ci是Cj的前向任務(wù)，在狀態(tài)M下服務(wù)Si失敗M(Pc)=1Pc=tc, tc=Pc, tc=S1PItr, S2PItr, , SnPItrMtcM, 其中M(SjPItr)=1任務(wù)Ci是Cj的前向任務(wù)M(SjPin)=1MSjtabMSjtabM, 其中M(SjPab)=1系統(tǒng)中斷了服務(wù)Sj即SS保

23、證了服務(wù)組合的失效處理機(jī)制（1）。同理根據(jù)任務(wù)間的關(guān)系，可以分別證明SS保證了服務(wù)組合的失效處理機(jī)制（2）和（3）。綜上所述，SCFP模型SS保證了服務(wù)組合的失效處理機(jī)制。 證畢性質(zhì)2指出本文建立的模型可以確保服務(wù)組合的失效處理機(jī)制正確運(yùn)行，從而說明了失效處理機(jī)制建模方式的正確性。性質(zhì)3：SCFP模型SS中，任一可達(dá)狀態(tài)M下若存在某個服務(wù)是處于事務(wù)位置，則存在唯一的服務(wù)處于失敗位置。證明：不妨設(shè)在終止?fàn)顟B(tài)M下，服務(wù)Si處于事務(wù)位置，即中斷、取消或補(bǔ)償。M(SiPca)+M(SiPab)+M(SiPcp)=1(SiPca)=Sitca(SiPab)=Sitab(SiPcp)=Sitcp且(Sit

24、ca)(Sitab)(Sitcp)=SiPItr(SiPItr)=tc, tc=Pc, Pc=S1tfa, S2tfa, , Sntfa$SjS, M(SjPfa)=1服務(wù)組合中同一時刻最多有一個服務(wù)失敗$!SjS, M(SjPfa)=1即存在唯一的服務(wù)Sj處于失敗位置 證畢 上述主要分析了SCFP模型的基本性質(zhì)和特征，下面基于上述性質(zhì)深入分析SCFP模型的一致性。定義4：任意兩個終止?fàn)顟B(tài)Ma, MbTSF(S,Ci)，若對于所有任務(wù)Cj(ij)，Ma, Mb滿足下列兩個條件之一：（1）Maj=Mbj（2）Ma(CjPe)+Ma(CjPcp)=Mb(CjPca)+Mb(CjPab)=1稱狀態(tài)M

25、a和Mb是相容的，記做MaMb。否則稱狀態(tài)Ma和Mb是不相容的，記做MaMb。記TS(S)中與狀態(tài)Ma相容的狀態(tài)集合為CS(Ma)。從定義4可知，兩個終止?fàn)顟B(tài)不相容必須同時滿足下列兩個條件：（1）屬于同一個任務(wù)的失敗終止?fàn)顟B(tài)；（2）存在某個任務(wù)在這兩個狀態(tài)下分別處于結(jié)束和補(bǔ)償位置。否則Ma和Mb是相容的，顯然狀態(tài)和自己本身是相容的。定義5：終止?fàn)顟B(tài)集合S，若任意的失敗終止?fàn)顟B(tài)Ma，MbS(ab)滿足下列條件之一，則稱S是一致的：（1）Ci, Cj, Ma(CiPfa)=Mb(CjPfa)=1CiCj（2）$i, Ma(CiPfa)=Mb(CiPfa)=1MaMb終止?fàn)顟B(tài)集合S是一致的指該集合中

26、任意兩個狀態(tài)要么不屬于同一個任務(wù)的失敗終止?fàn)顟B(tài)集，要么相容。下面通過判斷模型終止?fàn)顟B(tài)集的一致性來分析模型的正確性。定義6：集合STS(SS)稱為服務(wù)組合SS的可達(dá)終止?fàn)顟B(tài)集合，若對于任意STSiSTS(SS)有：（1）存在變遷序列d，使得M0dSTSi（2）tT, STSit (C1+C2)C3(C4|C5)C6，假設(shè)任務(wù)C5是不可取消的。按照工作流模型的建模步驟，可以構(gòu)造出整個系統(tǒng)的所對應(yīng)工作流模型S=(C;P,T,F,M0)，如圖6所示。圖中的庫所和變遷刻畫了任務(wù)的相應(yīng)位置及任務(wù)之間的關(guān)系。圖6 旅游服務(wù)的工作流模型假設(shè)目前的可用服務(wù)有22個，具體的事務(wù)屬性如表3所示： 表3 服務(wù)的事務(wù)屬

27、性任務(wù)WSTP任務(wù)WSTPC0S01pC1S11cpS02r,cpS12PS03cpS13r,cpC2S21pC3S31r,cpS22pS32PS23pS33cpC4S41rC5S51cpS42cpS52pS43pS53r,cpS54rC6S61cpS62pS63cp下面給出服務(wù)消費(fèi)者的當(dāng)前可接受狀態(tài)集，如表4所示。其中M8=C0cp, C1cp/C2e, C3cp, C4e, C5e, C6fa表示服務(wù)S6失敗時，服務(wù)消費(fèi)者可接受服務(wù)S0，S1，S3得到補(bǔ)償，而其余服務(wù)不能補(bǔ)償。表4 可接受狀態(tài)集ATSM CATSC0C1/C2C3C4C5C6M1eeeeeeM2faabababababM3

28、cpfaababababM4cpcpfaabababM5cpcpcpfaeabM6cpcpcpefaabM7cpcpcpcafaabM8cpcp/ecpeefa首先計算該工作流模型的協(xié)調(diào)集，根據(jù)可接受狀態(tài)集的有效性定義可知ATS是有效的。下面基于ATS，按照協(xié)調(diào)策略構(gòu)造服務(wù)組合，具體步驟如下：步驟1：應(yīng)用協(xié)調(diào)策略1，分配可重復(fù)服務(wù)所對應(yīng)的任務(wù)，并按照策略1中可接受狀態(tài)集的計算公式調(diào)整ATS。首先分配服務(wù)S02給任務(wù)C0，相應(yīng)地ATS調(diào)整為M1, M3, M4,M5,M6, M7, M8, M10, M11,M12, M13, M14,M15。同理對任務(wù)C1, C3, C4, C5分別分配服務(wù)S

29、13, S31, S41, S54，最后ATS調(diào)整為M1, M8步驟2：應(yīng)用協(xié)調(diào)策略2，基于可接受狀態(tài)集M1, M8，對剩下的任務(wù)C2和C6分配服務(wù)。最后分配結(jié)果為S2=S23, S6=S62。至此，工作流模型中的每個任務(wù)都分配一個服務(wù)。根據(jù)服務(wù)的事務(wù)屬性和服務(wù)組合的失效處理機(jī)制，可以得到旅游服務(wù)的SCFP模型SS=(Ps,Ts,Fs;Ms0)，如圖7所示。該模型的可達(dá)終止?fàn)顟B(tài)集合STS(SS)=M1, M3, M8ATS，因此服務(wù)組合SS是可靠的。圖7 旅游服務(wù)的SCFP模型由于篇幅的限制，本文僅僅對簡化的旅游服務(wù)進(jìn)行模擬。但是它足以說明服務(wù)組合的建模方法和協(xié)調(diào)策略的正確性。實例模擬過程可知

30、，應(yīng)用本文所提出方法可以達(dá)到如下效果：（1）可以清晰地描述任務(wù)及任務(wù)之間的關(guān)系。（2）正確刻畫了服務(wù)的事務(wù)屬性，所構(gòu)造的模型可以確保服務(wù)組合的失效處理機(jī)制正確運(yùn)行。如服務(wù)S6運(yùn)行失敗，根據(jù)Petri網(wǎng)的運(yùn)行機(jī)制SS模型會到達(dá)終止?fàn)顟B(tài)M8或M15。（3）協(xié)調(diào)策略的有效性，按照協(xié)調(diào)策略所構(gòu)造的服務(wù)組合是可靠的。如圖7中的STS(SS)=M1, M3, M8，滿足可靠服務(wù)組合的定義。因此，SS是可靠的。（4）動態(tài)調(diào)整可接受狀態(tài)集，以減少計算量。若每次分配可重復(fù)服務(wù)后可接受狀態(tài)集沒有進(jìn)行調(diào)整，則每次分配服務(wù)都要搜索整個可接受狀態(tài)集。因此，對于大型服務(wù)組合，該方法可以在較快的時間內(nèi)構(gòu)造可靠服務(wù)組合。6

31、相關(guān)工作現(xiàn)在Web服務(wù)事務(wù)處理技術(shù)正處于不斷發(fā)展之中，許多公司已經(jīng)推出處理Web服務(wù)事務(wù)的協(xié)議。Limthanmaphon對這些協(xié)議進(jìn)行總結(jié)10，但這些協(xié)議是主要是為Web服務(wù)技術(shù)制定基于XML的標(biāo)準(zhǔn)，并沒有考慮到服務(wù)消費(fèi)者的實際需要，且不容易根據(jù)服務(wù)消費(fèi)者的需要來動態(tài)調(diào)整。而使用形式化方法對服務(wù)組合事務(wù)進(jìn)行分析也開始有了一些研究成果和工作。在這些工作中，有基于進(jìn)程代數(shù)的11-13，也有基于p演算14的。Butler提出使用CCS與CSP結(jié)合的方法來描述Web事務(wù)11，它的優(yōu)點(diǎn)是對結(jié)構(gòu)化活動的恢復(fù)機(jī)制進(jìn)行描述，但是它所采用的語法比較復(fù)雜，不利于對相關(guān)的特性進(jìn)行推導(dǎo)。Butler等對該方法進(jìn)行改

32、進(jìn)12，并采用進(jìn)程代數(shù)來描述相應(yīng)的語義，但它沒有考慮事務(wù)運(yùn)行的不同狀態(tài)，對模型的正確性驗證還沒有具體論述。Hashemian采用進(jìn)程代數(shù)的方法來描述無狀態(tài)的服務(wù)13，進(jìn)而描述服務(wù)組合的語義，通過使用圖的框架可以表示服務(wù)組合的過程，但是它沒有考慮服務(wù)的狀態(tài)，而實際中，服務(wù)的狀態(tài)卻是服務(wù)消費(fèi)者比較關(guān)心的結(jié)果。采用p演算主要是對服務(wù)協(xié)議進(jìn)行研究，給出擴(kuò)展p演算的形式化語義。廖軍等利用Pi-演算建立Web服務(wù)組合模型的規(guī)則14，并使用形式化工具分析所建立組合模型的正確性，但是它沒有分析服務(wù)消費(fèi)者可接受狀態(tài)的多樣性，且p演算對設(shè)計人員的數(shù)學(xué)功底要求較高，不利于方法的擴(kuò)展。最近也出現(xiàn)了一些采用事務(wù)模式的方

33、法來分析服務(wù)的事務(wù)屬性15,16。Bhiri提出了事務(wù)模式的方法描述可靠服務(wù)組合15，但它沒有對模型進(jìn)行驗證，而且不易對所建立的模型進(jìn)行分析。Montagut提出一種事務(wù)需求的服務(wù)組合方法，它考慮了服務(wù)的事務(wù)屬性。但是該方法沒考慮服務(wù)的失敗處理，且采用狀態(tài)圖描述服務(wù)的特性，造成模型性質(zhì)分析的復(fù)雜性，使得方法難以推廣。與本文相近的工作還有文獻(xiàn)17-19，它們均采用Petri網(wǎng)對服務(wù)組合進(jìn)行形式化分析。文獻(xiàn)17提出使用Petri網(wǎng)對服務(wù)的行為進(jìn)行分析，以便驗證組合過程是否能得到預(yù)期的結(jié)果，但是，它在驗證的過程中沒有考慮服務(wù)的事務(wù)特性，導(dǎo)致服務(wù)失敗時，很難對其語義比較準(zhǔn)確的形式化分析。文獻(xiàn)18使用著

34、色Petri網(wǎng)的語義來描述Web服務(wù)，進(jìn)而描述了服務(wù)之間的關(guān)系，其優(yōu)點(diǎn)是考慮了服務(wù)的QoS屬性，但它沒有考慮服務(wù)的動態(tài)性且沒有對其相關(guān)的性質(zhì)進(jìn)行驗證。文獻(xiàn)19使用Petri網(wǎng)的語義來描述Web服務(wù)的原子事務(wù)和聚合事務(wù)，進(jìn)而使用Petri網(wǎng)的可達(dá)圖對相關(guān)算法進(jìn)行驗證，它的優(yōu)點(diǎn)是分析了事務(wù)的一致性，但是它沒有描述服務(wù)的補(bǔ)償和取消等重要特性。7 結(jié)束語本文針對帶事務(wù)屬性的服務(wù)組合，提出利用Petri網(wǎng)來構(gòu)造服務(wù)組合的工作流模型和SCFP模型，給出可靠服務(wù)組合的協(xié)調(diào)策略及其實施。與現(xiàn)有方法相比，本文工作具有如下優(yōu)點(diǎn)：（1）使用形式化方法（Petri網(wǎng)）來描述，Petri網(wǎng)相關(guān)的理論可以準(zhǔn)確地刻畫服務(wù)運(yùn)

35、行的不同狀態(tài)，且可以清晰地表達(dá)服務(wù)組合的邏輯及服務(wù)之間的關(guān)系，利用相關(guān)工具可對系統(tǒng)進(jìn)行模擬，使得該方法易于推廣；（2）充分考慮了服務(wù)的事務(wù)屬性和服務(wù)組合的失效處理機(jī)制，保證服務(wù)失敗時可得到相應(yīng)的處理；（3）提出了協(xié)調(diào)策略，該策略可減少可靠服務(wù)組合構(gòu)造的復(fù)雜度，并從理論上證明了該策略的有效性。同時給出了協(xié)調(diào)策略的具體實施，為構(gòu)建大型復(fù)雜的服務(wù)組合系統(tǒng)奠定基礎(chǔ)。本文在服務(wù)的事務(wù)特性建模方面取得了進(jìn)展，但沒有考慮服務(wù)組合流程中的資源調(diào)度問題，對SCFP模型的推理機(jī)制和工具也沒有涉及。另外，本文對可用服務(wù)的選擇沒有考慮服務(wù)的QoS。我們將在這些方面進(jìn)一步探索。參 考 文 獻(xiàn)1 Ambrogio A D, Bocciarelli P. A model-driven approach to describe and predict the performance of composite services/Pro