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只能判定在一个服务组合内受服务编排协议影响的服务，如果一个服务同时也属于另一个服务组合，即涉及到多个服务组合的协同演化，则需要判定该服务的演化是否影响另一个服务组合的其他服务。可以采用递归形式判定，这里不再赘述。

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.］