Web服務組合中業務流程演化影響范圍判定方法

尤殿龍，申利民，劉 芳

（燕山大學信息科學與工程學院／河北省計算機虛擬技術與系統集成重點實驗室，河北 秦皇島 066004）

0 引言

Web服務組合是指為了特定目標，將多個Web服務按照語義和邏輯關系進行通信和協作，以實現業務功能的增值。為了適應環境變化和持續滿足用戶需求，Web服務組合需要不斷演化。業務流程演化通過調整Web服務組合的業務邏輯和交互規則來適應用戶的業務需求變化，是Web服務組合演化的重要組成部分。

工業界從服務編制（orchestration）和服務編排（choreography）兩個層面來描述 Web服務組合［1］。服務編制描述Web服務組合的業務流程執行，如對消息流、控制流和數據流等的定義和控制；服務編排從全局視角來明確各個服務所扮演的角色和服務間的交互協議，并以該協議為規約指導服務編制的實現，如對角色類型、關系類型、通道類型和會話規則等的描述［1］。業務過程執行語言（Business Process Execution Language，BPEL）和Web服務編排描述語言（Web Services Choreography Description Language，WS－CDL）分別是服務編制和服務編排事實上的標準［2］。服務編制層面的演化發生在單個服務內部，對外不可見，不影響全局，如單個服務的糾錯、優化等。服務編排層面的演化突破單個服務內部，深入到伙伴服務中，演化過程伴隨服務編排協議的調整，需要伙伴服務協同參與［2］。服務編排層面演化是各個波及服務依據新的服務編排協議在各自內部發生服務編制演化。文獻［3］認為編排的可實現性和服務編制對于某一服務編排的遵守性是服務編排演化的重點。

學術界認為，Web服務組合演化可以發生在過程定義層（Process Definition Level，PDL）和過程實例層（Process Instance Level，PIL）［4］。PDL演化需要替換相應的WS－CDL或BPEL程序，演化將影響所有正在運行中的Web服務組合實例；PIL演化通常是服務組合實例由運行過程中遭遇不可預見的異常而引發的，演化只需要修改特定服務組合實例的過程定義，因此演化只影響特定的服務組合實例［4］。另外，文獻［5］提出了兩類服務組合的演化——淺演化和深演化。淺演化是僅涉及單個服務的演化，深演化是突破單個服務范圍、深入到伙伴服務中并產生級聯的演化。Web服務組合中的業務流程貫穿于各個服務，當某個服務發起業務流程演化時，需要伙伴服務的協同參與，即演化波及到其他服務，因此對業務流程的演化發生在服務編排演化層面，屬于深演化。同時，因為涉及WS－CDL或BPEL程序的變化，所以業務流程演化也屬于過程定義層面的演化。

1 需求及問題

1.1 需求的提出

無論是靜態演化還是動態演化，業務流程演化波及范圍的判定都是實施Web服務組合演化的前提。當前，服務組合演化的研究主要在服務編制和過程實例層面。文獻［2］考慮了局部的服務編制演化不能影響到服務編排中其他的伙伴服務，其影響范圍只局限在單個服務內部，沒有波及到伙伴服務，屬于服務編制層面的演化。服務編排層面的演化由于波及到Web服務組合中的伙伴服務，業務流程演化影響范圍的判定要在多個服務中進行，而發起演化的服務方對演化所波及的服務的內部業務流程不可知。因此，服務編排層面的業務流程演化一直是服務組合演化中的難點［2－5］。本文主要解決演化發生在服務編排層面時，服務組合中業務流程影響范圍的判定問題，并將服務編制層面的演化看成服務編排層面演化的一個特例。

對服務編排層面業務流程演化影響范圍的判定存在以下難點問題：①參與演化的各服務不知道彼此內部的業務流程細節，發起演化的服務無法直接判定伙伴服務內部業務流程的受影響范圍［6］。②演化往往只影響業務流程中特定區間下的狀態節點（狀態節點指由輸入動作引起狀態變化的功能點，如構件、功能模塊等），但是目前還不能完全做到演化僅在特定區間內的狀態節點發生，并且使受影響的狀態節點都能參與演化，不被遺漏。目前，服務演化的常見方法（如業務流程的完全替換和狀態替換）是通過改變完整業務流程或單個狀態節點的方式實現的。例如，文獻［7］提出了支持Web服務業務流程協議的動態演化方法，將協議演化分為完全替換、狀態替換、路徑替換、基于相關歷史替換和基于客戶協議分析替換，然而對于業務流程路徑內部分區間的演化采用完全替換或路徑替換的方法，會使演化發生在未受波及的狀態節點。③演化發生前缺少對演化類型的判定。服務演化過程與演化類型密切相關，依據演化類型確定演化規則可以降低演化成本和復雜度。例如，增值式演化可以在擴展原有服務編排協議的基礎上開展業務流程的演化；削減式演化可以在原有服務編排協議不變的前提下，直接對服務內部業務流程進行刪減。④針對服務編排層面業務流程演化波及服務及其影響范圍的判定規則和算法，還缺少系統的研究。文獻［8］首先查找工作流內的變化區域，如果工作流實例不在變化區域中執行，則允許遷移。該方法可以判定演化發生后，哪些工作流實例可以正常執行，但并沒有給出具體的判定變化區域的規則和算法。⑤缺少發生級聯演化情況下，演化影響范圍的判定規則和算法。所謂級聯演化是指當發起演化的服務影響到與其直接通信的受波及服務時，因受波及服務業務流程變化而引發其他服務參與協同演化的過程。文獻［6］給出了服務編排的動態演化方法，方法中的服務演化影響范圍僅涉及發起服務波及范圍的判定，對由伙伴服務演化引起的其他服務改變未做分析。

1.2 要解決的問題

針對Web服務組合中業務流程演化影響范圍的判定，主要解決的問題（如圖1）包括：

（1）服務組合演化類型的判定 通過互模擬理論，分析服務發起方內部業務流程變化，提出了內部式、增值式、削減式和全局式四種演化類型，并給出了判定規則。

（2）演化波及服務的判定 通過內部業務流程內受影響狀態節點的前驅狀態集或后繼狀態集的歸屬服務來判定波及服務，給出了判定規則和算法。

（3）業務流程演化影響范圍的判定 針對發起演化的服務對伙伴服務內部業務流程不可知的特點［9］，提出首先由各個服務通過對演化前內部業務流程的狀態節點與演化后預期內部業務流程的狀態節點的互模擬（伙伴服務預期內部業務流程可以通過服務發起方業務流程演化請求文檔和新的服務編排協議映射得出），得出各自的單個內部業務流程演化影響范圍，然后以單個內部業務流程演化的影響范圍為基礎，判定單個服務內部業務流程演化的影響范圍，最后得出Web服務組合業務流程演化的影響范圍。

上面給出的所有判定規則和算法適用于靜態演化、動態演化和級聯演化。對于服務編排協議，給出了形式化模型，協議的編排規則、服務編排協議的映射和服務編排演化的實施過程為后續研究內容。

2 基本概念和模型

本文提出的Web服務組合演化的影響范圍判定方法是以狀態遷移模型和互模擬理論為基礎［10－11］。首先，將服務組合的執行過程用狀態遷移模型來描述，模型有一個狀態集合，通過動作實現狀態遷移；其次，給出了業務流程、服務和Web服務組合的形式化定義；最后，運用互模擬等價理論判定演化前后Web服務組合業務流程的變化關系。為了便于討論，本章給出了相關概念。

定義1 狀態遷移模型。動作集合active上的一個狀態遷移系統是一個二元組（state，relation），其中：active是一個動作集合，動作被定義為引發服務狀態變化的一次執行；state是一個狀態集合；relation是一個遷移關系，relation?state×active×state，如果a∈active，s，s′∈state，滿足（s，a，s′）∈relation，則記為。

定義2 業務流程。業務流程b是由動作引起的從開始狀態si到結束狀態sj的狀態遷移，即，記作 （si，si＋1，…，sj）或（si?sj）。fn（b）表示由b中狀態組成的集合。一般用s0表示初始狀態，用sf表示結束狀態，對于狀態序列 （si，si＋1，…，sj），有s0＝si，sf＝sj。服務組合的業務流程可能存在多個，依次命名為b1，b2，…，bn。服務組合單個業務流程bi的狀態節點可能分布在各服務內部，如果服務services中存在bi的狀態節點，則這些節點組成的狀態遷移序列（也可能是單個節點，稱為bi）存在于services中的內部業務流程，這樣的內部業務流程在services中也可能存在多個，其中的第k個內部業務流程記作bi（s）：k，它表示業務流程bi在服務services中的第k個內部業務流程。

定義3 服務。服務是服務組合的參與者，定義為五元組service＝（name，active，state，message，port）。其中：name是服務名，active是服務的動作集合，state是服務的狀態集合，message是服務的消息集合，port是服務的端口集合。

定義4 Web服務組合WSC。Web服務組合是一個二元組WSC＝ 〈Service，Bp，p｝〉。

其中：Service ＝ ｛service1，service2，…，servicen｝是由服務組合內所有的伙伴服務組成的集合，簡稱服務集，n是服務組合中伙伴服務的個數。

Bp＝｛b1，b2，…，bm｝是服務組合的全部業務流程組成的集合，m是業務流程數目。

p是服務編排協議，p＝〈role，channel，rules〉，role是服務的角色類型，描述參與方為了交互可能表現出的可觀察行為；rules表示交互規則；channel是服務間的交互通道，交互通道可以通過服務間的交互端口來描述。服務協同演化過程不是本文的重點，因此，對交互規則、交互通道以及消息的發送和處理機制等不做系統地描述。

定義6 強互模擬、強等價。如果二元關系R和它的逆R－1是狀態遷移系統（state，relation）上的強模擬，則稱R是（state，relation）上的一個強互模擬。令sp，sq∈state，如果存在一個強互模擬R，使得spRsq，則稱兩個狀態sp和sq是強互模擬或強等價，記作sp～sq。

定義8 弱互模擬、弱等價或觀察等價。如果二元關系S和它的逆S－1是狀態遷移系統（state，relation）上的弱模擬，則稱S是（state，relation）上的一個弱互模擬。令sp，sq∈state，如果存在一個弱互模擬S使得spSsq，則稱兩個狀態sp和sq是弱互模擬、弱等價或觀察等價，記作sp≈sq。

互模擬等價是進程代數中最常用的等價關系，并且根據是否忽略內部動作分為強互模擬等價和弱互模擬等價。強互模擬平等看待所有動作（包括內部不可見動作），弱互模擬是忽略內部動作、可觀察外部動作的等價［12］。

3 服務組合演化類型的判定

演化類型判定是確定服務組合業務流程演化影響范圍的基礎，服務組合演化可能只是單個服務內部或各個服務之間業務流程的增加、刪減或修改，也可能是服務內部業務流程的重新編制、服務間交互協議的重新編排［9－10］。因此，依據演化類型確定演化規則，可以提升演化效率，降低演化成本。

性質1 模擬關系。強模擬一定是弱模擬，強互模擬一定是弱互模擬。非弱模擬一定是非強模擬，非弱互模擬一定是非強互模擬。

證明 根據定義5，對于sRs，如果

pq，則存在其中，動作α可能是內部（不可見）動作，也可能是外部（可見）動作，而定義7只關注外部（可觀察）動作。如果α是內部動作，則相當于0個外部動作，存在s′p使得sp?s′p，滿足定義7；如果α是外部可見動作，相當于1個外部動作，存在s′q使得sq?s′q，亦滿足定義7。因此，強模擬一定是弱模擬。證畢。

同理可證，強互模擬一定是弱互模擬，非弱模擬一定是非強模擬，非弱互模擬一定是非強互模擬。

規則1 服務組合演化類型的判定。Service＝｛service1，service2，…，servicen｝ 是 服 務 集 合，service是發起演化的服務，service∈Service，service′是service演化后的服務。如果service，service′的狀態遷移模型分別是（state，relation）和（state′，relation′），對于 ?s∈state，?s′∈state′，存在如下判定規則：

（1）如果滿足 （sSs′∧s′Ss）∧ （sR ／s′∨s′R／s），即s與s′弱等價，且s非強模擬s′或s′非強模擬s，則表明從service演化到service′的是服務內部行為發生變化，而外部可觀察行為沒有發生變化，原有服務編排協議繼續有效，演化未波及到其他伙伴服務，則該演化過程稱為服務的內部式演化或服務編制層面演化。

（2）如果滿足sRs′∧s′R／s，即s′強模擬s，且s非弱模擬s′，則表明從service演化到service′是在原有業務流程不變情況下的服務增值，原有編排協議需要調整，演化波及到其他伙伴服務，則該演化過程稱為服務的增值式演化。

（4）如果滿足s＄s′∧s′＄s（亦可記作s?s′），即s與s′非弱等價，則表明從service演化到service′的是服務內部行為和外部可觀察行為都發生變化，服務演化波及到了服務組合中的其他伙伴服務，則該演化過程稱為服務的全局式演化。

表1給出了四種服務組合演化類型，對服務編排協議、發起演化服務及參與演化服務業務流程影響的對比。內部式演化發生在單個服務內部，屬于服務編制層面的演化；增值式演化、削減式演化、全局式演化發生在多個服務之間，演化波及到服務編排協議，屬于服務編排層面的演化。

表1 服務演化行為類型及影響

以服務組合CWS為例，CWS＝〈Service，Bp，p〉，Service＝｛service1，service2，service3｝。其中：Service是服務集合，Bp是業務流程集合，p是服務編排協議，。CWS演化前有三個業務流程（如圖2），分別是b1＝ （s11，s12，s21，s22，s13），b2＝ （s11，s12，s21，s22，s23，s24，s31，s32，s15，s26）和b3＝ （s11，s12，s21，s22，s23，s24，s31，s25，s14，s26）。圖3～圖6所示為服務組合的四種服務演化類型。

（1）內部式演化 圖3是服務演化發起方的內部業務流程演化，演化過程完全在服務service1的內部進行，業務流程b1演化為b′1＝ （s11，s17，s12，s21，s22，s13，s16），但外部可觀察行為（交互行為）沒有發生變化。該演化對服務編排協議和伙伴服務無影響，演化可以在不告知服務參與方的情況下直接進行。

（2）增值式演化 在原有業務流程不變的前提下增加新的業務流程，并且服務的外部可觀察行為（交互行為）發生變化。如圖4所示，演化后的業務流程中b1，b2和b3不變，增加了b4＝ （s11，s12，s21，s22，s27，s28，s24，s31，s25，s14，s26）和b5＝ （s11，s12，s21，s22，s27，s28，s24，s31，s32，s15，s26）。該演化過程波及到服務編排協議和伙伴服務，但演化過程可能需要升級其他業務流程內的功能節點，如s22和s24，演化前后原有業務流程不變。

（3）削減式演化 原有業務流程在數量和功能上的縮減，并且服務的外部可觀察行為（交互行為）發生變化。如圖5所示，刪減b3，保留b1和b2。因為b3的業務節點包含于service1，service2和service3中，所以演化對其他伙伴服務產生影響。但是，演化后的服務編排協議p′與原始服務編排協議p相比，存在p′?p，即p中具備完成演化后的業務流程b1和b2的編排協議，因此演化后的業務流程可以在p下運行。

（4）全局式演化 原有業務流程和服務的外部可觀察行為（交互行為）均發生變化，如圖6所示，業務流程包括：b1＝ （s11，s12，s21，s22，s13），b′2＝ （s11，s12，s21，s27，s28，s23，s24，s31，s32，s15，s26）和b′3＝ （s11，s12，s21，s22，s27，s28，s24，s31，s25，s14，s26），其 中 去 掉 了節點s23，增加了節點s27和s28。

4 演化波及服務判定

4.1 前驅狀態集和后繼狀態集

Web服務組合中，演化波及服務的判定是通過確定演化前后對應狀態節點的互模擬關系以及受波及狀態節點的歸屬服務得出的。由于業務流程中的狀態節點部署在各個參與服務中，一個服務中狀態節點的演化所波及到的相鄰狀態節點可能在其他服務內部，需要首先判定受波及相鄰狀態節點的歸屬服務。因此，引入了狀態節點的前驅狀態集和后繼狀態集概念，作為判定相鄰狀態節點的歸屬服務的基礎。

定義9 前驅狀態集是業務流程內狀態序列中當前狀態s的前一狀態節點的集合，用PreState（s）表示。

定義10 后繼狀態集是業務流程內狀態序列中當前狀態s的后一狀態節點的集合，用NextState（s）表示。

以上實例中，狀態s12，s13，s14，s15∈service1，s31∈service3，對service2而言并不可知。但可以在service2內判定其內部狀態的前驅或后繼狀態歸屬于哪個服務（簡稱歸屬服務）。令belSer（state）＝Service表示狀態集state的歸屬服務集是Service。則以上示例中前驅狀態集或后繼狀態集對應的歸屬服務集分別是：

4.2 演化波及服務的判定

增值式演化、削減式演化或全局式演化發生時，服務的內部業務流程和外部交互行為均發生變化，演化波及到伙伴服務，服務編排協議和業務流程都需要改變（削減式演化在服務編排協議不做修改的情況下也可能運行）。因此，將三種演化的判定規則結合，即可得出伙伴服務的編排協議和業務流程是否需要協同演化的判定公式

演化波及服務的判定只與外部交互行為有關，可以不考慮內部活動的變化。因此，根據性質1，強模擬一定是弱模擬。將上式中的sRs′用sSs′替代，將s′Rs用s′Ss替代，得出演化波及服務的判定公式

將式（2）化簡，得出式（3）：

演化波及服務的判定公式s＄s′∨s′＄s說明，如果s和s′至少一方非弱模擬對方，則演化波及到了伙伴服務。規則2給出了演化波及服務的判定規則，算法1給出了判定算法。

規則2 演化波及服務判定。令服務組合WS＝ （Service，Bp，p），Service＝ ｛servicei1≤i≤n｝是WS的服務集，n是WS的服務總數。p和p′分別是演化前后的服務編排協議。令servicea是服務演化的發起方，servicea∈Service，serviceα＝（nameα，activeα，stateα，messageα，portα），其中stateα是服務serviceα的狀態集。Bp是WS的業務流程集合。Bα＝ ｛bj（α）1≤j≤m｝是serviceα演化前的內部業務流程集合，m是serviceα的內部業務流程數，對于serviceα任意的內部業務流程bi（a）演化到b′i（a），s∈bi（a），s′∈b′i（a）。fn（bi（a））和fn（b′i（a））分別是由bi（a）和b′i（a）狀態構成的集合，serviceα波及到的伙伴服務集合Serviceα~滿足以下三個條件：

（1）Serviceα~?Service－｛serviceα｝，表示伙伴服務集合Serviceα~的元素屬于Service，但不包括發起服務serviceα。

（2）s＄s′∨s′＄s，根據式（3），如果s和s′至少一方非弱模擬對方，則表示演化波及到了伙伴服務。

算法1 演化波及服務判定算法。

當算法1的第二個入口參數為發起演化的服務時，判定的是演化發起服務引起的受波及服務，當入口參數為伙伴服務時，可以判定因伙伴服務參與演化而引起的受波及服務，即產生級聯演化情況下的波及服務判定。另外，算法1只能判定在一個服務組合內受服務編排協議影響的服務，如果一個服務同時也屬于另一個服務組合，即涉及到多個服務組合的協同演化，則需要判定該服務的演化是否影響另一個服務組合的其他服務?？梢圆捎眠f歸形式判定，這里不再贅述。

5 業務流程演化影響范圍的判定

服務組合中業務流程的狀態節點部署在不同的服務中，演化過程需要各伙伴服務在內部依據協商得到的新的服務編排協議單獨進行，演化進行前需要判定各個服務內部受演化影響的業務流程邊界，以此確定業務流程演化的影響范圍。為了書寫簡便，本章將“內部業務流程”標記為b和bi等。

5.1 單個內部業務流程演化影響范圍的判定

單個服務內部可能包含多個內部業務流程，單個內部業務流程演化是服務演化的基礎。單個內部業務流程演化的影響范圍以運用互模擬理論判定演化影響范圍邊界的方式確定。規則3給出了單個內部業務流程演化影響范圍邊界判定規則，算法2給出了單個內部業務流程演化影響范圍判定算法。

規則3 單個內部業務流程演化影響范圍邊界的判定。在編排協議p下，服務service的內部業務流程b的狀態序列是s0?sf。如果存在狀態?s，則pre（s）是s的前驅狀態，PreState（s）是s的前驅狀態集，pre（s）∈PreState（s）；next（s）是后繼狀態，NextState（s）是s的后繼狀態集，next（s）∈NextState（s）。s′是當服務編排協議為p′時s演化后的狀態，pre（s′）是s′的前驅狀態，PreState（s′）是s′ 的 前 驅 狀 態 集，pre（s′）∈ PreState（s′）；next（s′）是后繼狀態，NextState（s′）是s′的后繼狀態集，next（s′）∈NextState（s′）：

（1）如果s■s′，且pre（s）～pre（s′），則s是服務service內部業務流程b演化影響范圍的下界，記作ranged＝s。

（2）如果s■s′，且next（s）～next（s′），則s是服務service內部業務流程b演化影響范圍的上界，記作rangeu＝s。

根據互模擬理論，可以驗證演化前后狀態之間的等價關系。如果狀態s與s′非強等價，且對應的前驅狀態強等價，則s是內部業務流程b的下界；如果狀態s與s′非強等價，且對應的后繼狀態強等價，則s是內部業務流程b的上界。

根據規則3可以確定單個內部業務流程演化影響范圍的上界和下界，上界和下界構成的區間被稱作單個內部業務流程演化的影響范圍，一個業務流程中可能有多個這樣的區間，算法2是單個內部業務流程演化影響范圍的判定算法。

算法2 單個內部業務流程演化影響范圍判定算法。

算法2中的b′由伙伴服務方依據原始內部業務流程b和服務編排協議p′得出，然后利用b和b′的狀態遷移關系，確定狀態的互模擬關系。

5.2 參與演化的單個服務內部業務流程演化影響

范圍的判定

就業務流程演化而言，單個服務內部業務流程演化影響范圍是以服務中所有內部業務流程演化影響范圍為元素的集合。規則4給出了單個服務內部業務流程演化影響范圍判定規則，算法3給出了單個服務內部業務流程演化影響范圍的判定方法。

規則4 參與演化的單個服務內部業務流程演化影響范圍的判定。令bpservice＝ ｛b1，b2，…，bτ｝是服務service的內部業務流程集合，τ是業務流程的數目，令b∈bpservice，b的影響范圍

φ是內部業務流程b的影響范圍數目，則服務service內部業務流程演化的影響范圍

參與演化的單個服務內部業務流程影響范圍是由該服務的所有內部業務流程影響范圍構成的集合，其判定算法如下：

算法3 參與演化的單個服務內部業務流程演化影響范圍的判定。

5.3 服務組合業務流程演化影響范圍的判定

服務組合業務流程演化影響范圍從全局視角描述了服務組合演化的波及范圍，是以參與演化的單個服務內部業務流程演化影響范圍為元素的集合。規則5給出了服務組合業務流程演化影響范圍的判定規則，算法4給出了服務組合業務流程演化影響范圍的判定方法。

規則5 服務組合業務流程演化業務流程影響范圍的判定。對于服務組合ws，?s∈ws，服務組合業務流程演化影響范圍WS－Boundary ＝｛S－Boundary1，S－Boundary2，…，S－Boundaryλ｝，其中λ是參與演化的服務數目。

根據規則5，服務組合業務流程演化影響范圍集以參與服務演化的業務流程演化影響范圍集為元素構成，因此只要判定各個參與服務業務流程演化的影響范圍即可得出。服務組合業務流程演化影響范圍的判定過程如下：

算法4 服務組合業務流程演化影響范圍的判定。

6 實例分析

下面通過例子說明服務編排層面業務流程演化的影響范圍判定問題，圖7描述的是網上銷售高端工藝品的訂單管理服務組合CWS系統，該系統由客戶代理、供貨服務、物流服務和銀行四個服務系統構成。Service ＝ ｛servicea，services，servicel，serviceb｝是CWS的服務集，Bp＝｛b1，b2｝是CWS的業務流程集。其中，業務流程b1＝ （s11，s12，s13，s41，s14），b2＝（s11，s12，s13，（（s41，s42）‖s21），s22，s23，s24，s31，s32，s25，（s15‖（s33，s16）），‖表示并行執行。

供貨服務services為了在降低銷售風險的前提下盡可能地擴大銷售規模，吸引更多的消費者，在原有的先網上支付、后發貨交易模式的基礎上，又引入了基于對消費者信任檢查的貨到付款的模式。因此，供貨服務（services）作為演化的發起者，根據這一新增的銷售模式，在供貨服務（services）內部增加了信用檢查和返款功能，然后開展演化類型、波及服務及影響范圍的判定，并根據判定結果向參與演化的伙伴服務發送演化請求和協同演化所需要的編排協議和業務信息。

（1）演化類型的判定

服務組合中，各伙伴服務之間無法互知對方的內部業務流程。因此，services發起演化后，需要根據自身內部的業務流程變化來判定演化類型和波及服務。因為b2（s）：1＝b′2（s）：1＝ （（s21，s22）‖s22），s23，s24），b2（s）：2＝b′2（s）：2＝ （s25），但services演化前的內部業務流程中沒有與b′2（s）：3和b′2（s）：4對應的業務流程，所以對于 ?s∈state，?s′∈state′，滿足sRs′∧s′R／s，即s′強模擬s，且s非強模擬s′，services發生了增值式演化，表明從services演化到services是在原有業務流程不變情況下的服務增值，原有編排協議需要調整，演化波及到其他伙伴服務。

（2）波及服務的判定

因為services發生了增值式演化，所以增加了狀態s26和s27，產生了新的內部業務流程b′2（s）：3＝（s21，s26，s23，s24）和b′2（s）：4＝ （s27），且fn（b′2（s）：3）＝｛s21，s26，s23，s24｝， fn（b′2（s）：4） ＝ ｛s27｝。 對 于fn（b′2（s）：3）和fn（b′2（s）：4）中的元素，其前驅狀態或后繼狀態的歸屬服務分別是：

由計算結果可知，services作為服務演化發起方，因新增業務流程b′23和b′24而產生的演化波及服務集 （Service~s）為 Service~s＝ ｛servicea，servicel｝。

（3）服務內部影響范圍的判定

services演化波及到的外部服務集合是Service~s＝ ｛servicea，servicel｝，因此在服務組合CWS中，參與協同演化的伙伴服務是services，servicea和servicel。下面對三個服務的內部影響范圍分別進行分析和判定。

1）服務演化發起方services單個內部業務流程演化影響范圍的判定

services演化后的服務service′s增加了狀態s26和s27，與s26交互的服務內部狀態是s21和s23，對應的內 部 業 務 流 程 是b2（s）：1＝ （（s21，s22）‖s22），s23，s24），根據規則5和算法3，業務流程b2（s）：1影響范圍下 界 是 rangeb2（s）：1d＝ s21， 影 響 范 圍 上 界 是rangeb2（s）：1u＝s26。狀態s27直接與外部服務交互，與服務內部無直接交互，因此在服務services內部無波及。

由規則3和算法2可知，演化引起的業務流程b21的變化范圍是：

2）參與演化的伙伴服務servicea和servicel單個內部業務流程影響范圍的判定

由于演化發起方services對參與演化的伙伴服務的內部業務流程不可知，需要services將變化傳播給受波及的伙伴服務，該變化是以調整后的服務編排協議p′（包含角色、交互規則、交互通道、端口等信息）和服務自身演化信息（如狀態、消息、端口等變化）的形式發送給伙伴服務，其過程需要按照服務編排演化的過程進行，這里不再贅述。各伙伴服務以此為依據，確定受services直接波及的狀態節點集合，再根據規則3和算法2，分別計算這些節點演化所引起的伙伴服務自身業務流程的波及范圍。

servicea演化前的內部業務流程包括b1（a）：1＝（s11，s12，s13），b1（a）：2＝ （s14），b1（a）：3＝ （s15）和b1（a）：4＝ （s16）。

由規則3和算法2可知，演化引起的內部業務流程b11的變化范圍是 BP－Boundaryb1（a）：1＝ （s12，s13），BP－Boundaryb1（a）：2＝ ?，BP－Boundaryb1（a）：3＝（s15，s15）和BP－Boundaryb1（a）：4＝ （s16，s16）。

servicel演化前的內部業務流程包括b3（l）：1＝（s31，s32）和b3（l）：2＝ （s33）。由規則5和算法3可知，演 化 引 起 的 業 務 流 程 b3（l）：1的 變 化 范 圍BP－Boundaryb3（l）：1＝ ?，b3（l）：2的 變 化 范 圍BP－Boundaryb3（l）：2＝ （s33，s33）。

servicea或servicel的內部演化同樣可能會波及到其他外部服務，此時可以將其作為服務演化發起方，按照圖1的判定流程以及相關判定規則和算法進行，在此不再贅述。

3）參與演化服務內部業務流程影響范圍的判定

參與演化的服務包括服務發起方services和演化波及服務servicea，servicel，根據規則4和算法3可以分別得出services，servicea和servicel的內部影響范圍：

4）服務組合CWS內部業務流程演化影響范圍的判定

根據規則5和算法4，服務組合 的演化影響范圍

7 結束語

本文首次提出了業務流程演化影響范圍的判定與服務組合演化類型密切相關，并運用互模擬理論，將服務組合演化劃分為內部式、增值式、削減式和全局式演化四種類型，給出了判定規則；針對服務編排層面的業務流程演化波及到其他伙伴服務，各服務方對伙伴服務的內部狀態和流程不可知，無法直接通過發起服務方判定伙伴服務的內部業務流程影響范圍的特點，提出依據發起演化服務內部業務流程演化前后的變化來判定波及服務，再將變化以初始服務編排協議的形式發送給伙伴服務，由各伙伴服務判定自身的服務組合業務流程演化影響范圍，并給出了單個內部業務流程演化影響范圍、參與演化的單個服務內部業務流程演化影響范圍和服務組合演化影響范圍的判定規則和算法。通過實例說明了該方法在保證演化僅在受波及區域內發生和在保證受影響的狀態節點都參與演化方面的有效性。

業務流程演化影響范圍判定是服務組合在服務編排層面協同演化機制研究的關鍵問題之一，下一步將從業務流程演化范圍的動態判定機制、服務編排協議的映射規則、服務組合的協同演化及其可實現性方面開展研究；同時可以運用互模擬理論，從狀態節點、單個服務和服務組合三個層面深入判定服務組合演化的類型。

［1］ PELTZ C.Web services orchestration and choreography［J］.IEEE Computer，2003，36（10）：46－52.

［2］ SONG Wei，MA Xiaoxing，LU Jian.Instance migration in dynamic evolution of Web service compositions ［J］.Chinese Journal of Computers，2009，32（9）：1816－1831（in Chinese）.［宋 巍，馬曉星，呂 建.Web服務組合動態演化的實例可遷移性［J］.計算機學報，2009，32（9）：1816－1831.］

［3］ SU Jianwen，BULTAN T，FU Xiang，et al.Towards a theory of Web service choreographies［J］.Lecture Notes in Computer Science，2007，4937：1－16.

［4］ SONG Wei.Research on dynamic evolution of Web service compositions［D］.Nanjing：Nanjing University，2010（in Chinese）.［宋 巍.Web服務組合動態演化技術研究［D］.南京：南京大學，2010.］

［5］ CAMBRONERO 段 ，DíAZ G，VALERO V，et al.Validation and verification 段 Web services choreographies by using timed automata［J］.The Journal of Logic and Algebraic Programming，2011，80（1）：25－49.

［6］ SONG Wei，LU Jian，MA Xiaoxing，et al.A method of dynamic evolution of Web service choreography［C］／／Proceedings of 2010CCF National Conference on Service Computing.Beijing：China Computer Federation，2010：274－286（in Chinese）.［宋 巍，呂 建，馬曉星，等.一種服務編排的動態演化方法［C］／／第一屆全國服務計算學術會議.北京：中國計算機學會，2010：274－286.］

［7］ RYU 段 ，CASATI F，SKOGSRUD H.Supporting the dynamic evolution of Web service protocols in service－oriented architectures［J］.ACM Transactions on the Web，2007，2（2）：1－43.

［8］ SUN Ping，JIANG Changjun.Analysis of workflow dynamic changes based on Petri net［J］.Information and Software Technology，2009，51（2）：284－292.

［9］ PAPAZOGLOU 段 .The challenges of service evolution［C］／／Proceedings of the 20th International Conference on Advanced Information Systems Engineering.New York，N.Y.，USA：ACM，2008：1－15.

［10］ YANG Shuxin，WANG Jian.Workflow instances migration approach based on state［J］.Computer Integrated Manufacturing Systems，2008，14（2）：372－378（Iin Chinese）.［楊書新，王 堅.基于狀態的工作流實例遷移方法［J］.計算機集成制造系統，2008，14（2）：372－378.］

［11］ XU Xian.On the bisimulation theory and axiomatization of higher－order process calculi［D］.Shanghai：Shanghai Jiaotong University，2008（in Chinese）.［徐 賢.高階進程演算的互模擬理論和公理化的研究［D］.上海：上海交通大學，2008.］

［12］ XU Wen，FANG Hai，LIN Huimin.Optimization and implementation of a bisimulation checking algorithm for theπ－calculus［J］.Journal 段 Software，2001，12（2）：159－166（in Chinese）.［許 文，方 海，林惠民.π－演算互模擬判定算法的優化和實現［J］.軟件學報，2001，12（2）：159－166.］