尤殿龍，申利民，劉 芳

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

0 引言

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

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

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

1 需求及問題

1.1 需求的提出

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

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

1.2 要解決的問題

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

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

（2）演化波及服務的判定 通過內(nèi)部業(yè)務流程內(nèi)受影響狀態(tài)節(jié)點的前驅(qū)狀態(tài)集或后繼狀態(tài)集的歸屬服務來判定波及服務，給出了判定規(guī)則和算法。

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

上面給出的所有判定規(guī)則和算法適用于靜態(tài)演化、動態(tài)演化和級聯(lián)演化。對于服務編排協(xié)議，給出了形式化模型，協(xié)議的編排規(guī)則、服務編排協(xié)議的映射和服務編排演化的實施過程為后續(xù)研究內(nèi)容。

2 基本概念和模型

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

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

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

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

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

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

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

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

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

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

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

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

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

性質(zhì)1 模擬關(guān)系。強模擬一定是弱模擬，強互模擬一定是弱互模擬。非弱模擬一定是非強模擬，非弱互模擬一定是非強互模擬。

證明 根據(jù)定義5，對于sRs，如果

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

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

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

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

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

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

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

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

以服務組合CWS為例，CWS＝〈Service，Bp，p〉，Service＝｛service1，service2，service3｝。其中：Service是服務集合，Bp是業(yè)務流程集合，p是服務編排協(xié)議，。CWS演化前有三個業(yè)務流程（如圖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）內(nèi)部式演化 圖3是服務演化發(fā)起方的內(nèi)部業(yè)務流程演化，演化過程完全在服務service1的內(nèi)部進行，業(yè)務流程b1演化為b′1＝ （s11，s17，s12，s21，s22，s13，s16），但外部可觀察行為（交互行為）沒有發(fā)生變化。該演化對服務編排協(xié)議和伙伴服務無影響，演化可以在不告知服務參與方的情況下直接進行。

（2）增值式演化 在原有業(yè)務流程不變的前提下增加新的業(yè)務流程，并且服務的外部可觀察行為（交互行為）發(fā)生變化。如圖4所示，演化后的業(yè)務流程中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）。該演化過程波及到服務編排協(xié)議和伙伴服務，但演化過程可能需要升級其他業(yè)務流程內(nèi)的功能節(jié)點，如s22和s24，演化前后原有業(yè)務流程不變。

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

（4）全局式演化 原有業(yè)務流程和服務的外部可觀察行為（交互行為）均發(fā)生變化，如圖6所示，業(yè)務流程包括：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），其 中 去 掉 了節(jié)點s23，增加了節(jié)點s27和s28。

4 演化波及服務判定

4.1 前驅(qū)狀態(tài)集和后繼狀態(tài)集

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

定義9 前驅(qū)狀態(tài)集是業(yè)務流程內(nèi)狀態(tài)序列中當前狀態(tài)s的前一狀態(tài)節(jié)點的集合，用PreState（s）表示。

定義10 后繼狀態(tài)集是業(yè)務流程內(nèi)狀態(tài)序列中當前狀態(tài)s的后一狀態(tài)節(jié)點的集合，用NextState（s）表示。

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

4.2 演化波及服務的判定

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

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

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

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

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

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

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

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

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

5 業(yè)務流程演化影響范圍的判定

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

5.1 單個內(nèi)部業(yè)務流程演化影響范圍的判定

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

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

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

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

根據(jù)互模擬理論，可以驗證演化前后狀態(tài)之間的等價關(guān)系。如果狀態(tài)s與s′非強等價，且對應的前驅(qū)狀態(tài)強等價，則s是內(nèi)部業(yè)務流程b的下界；如果狀態(tài)s與s′非強等價，且對應的后繼狀態(tài)強等價，則s是內(nèi)部業(yè)務流程b的上界。

根據(jù)規(guī)則3可以確定單個內(nèi)部業(yè)務流程演化影響范圍的上界和下界，上界和下界構(gòu)成的區(qū)間被稱作單個內(nèi)部業(yè)務流程演化的影響范圍，一個業(yè)務流程中可能有多個這樣的區(qū)間，算法2是單個內(nèi)部業(yè)務流程演化影響范圍的判定算法。

算法2 單個內(nèi)部業(yè)務流程演化影響范圍判定算法。

算法2中的b′由伙伴服務方依據(jù)原始內(nèi)部業(yè)務流程b和服務編排協(xié)議p′得出，然后利用b和b′的狀態(tài)遷移關(guān)系，確定狀態(tài)的互模擬關(guān)系。

5.2 參與演化的單個服務內(nèi)部業(yè)務流程演化影響

范圍的判定

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

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

φ是內(nèi)部業(yè)務流程b的影響范圍數(shù)目，則服務service內(nèi)部業(yè)務流程演化的影響范圍

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

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

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

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

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

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

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

6 實例分析

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

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

（1）演化類型的判定

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

（2）波及服務的判定

因為services發(fā)生了增值式演化，所以增加了狀態(tài)s26和s27，產(chǎn)生了新的內(nèi)部業(yè)務流程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）中的元素，其前驅(qū)狀態(tài)或后繼狀態(tài)的歸屬服務分別是：

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

（3）服務內(nèi)部影響范圍的判定

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

1）服務演化發(fā)起方services單個內(nèi)部業(yè)務流程演化影響范圍的判定

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

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

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

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

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

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

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

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

3）參與演化服務內(nèi)部業(yè)務流程影響范圍的判定

參與演化的服務包括服務發(fā)起方services和演化波及服務servicea，servicel，根據(jù)規(guī)則4和算法3可以分別得出services，servicea和servicel的內(nèi)部影響范圍：

4）服務組合CWS內(nèi)部業(yè)務流程演化影響范圍的判定

根據(jù)規(guī)則5和算法4，服務組合 的演化影響范圍

7 結(jié)束語

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

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

［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服務組合動態(tài)演化的實例可遷移性［J］.計算機學報，2009，32（9）：1816－1831.］

［3］ SU Jianwen，BULTAN T，F(xiàn)U 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服務組合動態(tài)演化技術(shù)研究［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）.［宋 巍，呂 建，馬曉星，等.一種服務編排的動態(tài)演化方法［C］／／第一屆全國服務計算學術(shù)會議.北京：中國計算機學會，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）.［楊書新，王 堅.基于狀態(tài)的工作流實例遷移方法［J］.計算機集成制造系統(tǒng)，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，F(xiàn)ANG Hai，LIN Huimin.Optimization and implementation of a bisimulation checking algorithm for theπ－calculus［J］.Journal 段 Software，2001，12（2）：159－166（in Chinese）.［許 文，方 海，林惠民.π－演算互模擬判定算法的優(yōu)化和實現(xiàn)［J］.軟件學報，2001，12（2）：159－166.］