可靠服务组合的协调策略与分析

1、可靠服务组合的协调策略与分析* 本课题得到国家自然科学基金(60473055，60773094)及上海市曙光计划（07SG32）资助范贵生，男，1980年生，博士研究生，主要研究方向为软件工程，面向服务计算，形式化方法，E-mail: gs_fan；刘冬梅，女，1970年生，博士研究生，主要研究方向为软件工程，面向服务计算，形式化方法；陈丽琼，女，1982年生，博士研究生，主要研究方向为分布式计算，嵌入式系统，形式化方法；虞慧群，男，1967年生，博士，教授，博士生导师，IEEE高级会员，ACM会员，. 主要研究方向为软件工程，信息安全，形式化方法范贵生 刘冬梅 陈丽琼 虞慧群(华东理工大学计

2、算机科学与工程系, 上海 200237)摘 要：服务组合是构建复杂Web软件的有效方法，但服务事务状态的多样性使得服务组合的可靠性难以保证。为此，提出一种构造可靠服务组合的协调方法。该方法采用Petri网对工作流建模，以清晰地表达任务及任务之间的逻辑关系。在此基础上，根据服务的事务属性及服务组合的失效处理机制建立服务组合的失效处理模型，并提出一种构造可靠服务组合的协调策略及实施方法。利用Petri网相关理论证明该策略的有效性。旅游服务实例演示了协调技术的应用方法及其可行性。关键词Petri网；Web服务；服务组合；事务；可靠性- 12 -1 引言随着Internet技术应用的迅速发展，基于We

3、b服务的分布式计算模式已经成为软件发展的趋势。Web服务能够统一地封装信息、行为以及业务流程，而无需考虑应用所在的环境。通过Web服务组合来动态生成新的应用系统，以满足实际的需要，已成为Web服务技术不断向前发展的技术动力1。然而，Web服务事务状态的多样性使得服务组合变得更为可靠和有效之前，还有一些问题需要处理。其中关键问题就是如何构建可靠服务组合，即如何根据服务的事务属性来分配可用服务以满足服务消费者的需求。虽然传统的事务技术在数据库系统和分布式系统中得到了广泛的应用，但由于Web服务自身的松耦合性、运行时间长、长事务等特点，使其在系统的可靠性和一致性方面面临新的挑战，如何对服务的事务属性

4、进行形式化分析成为业界广泛讨论并关注的问题2。Petri网作为一种直观的图形建模工具和一种具有丰富数学基础的形式化模型，可以广泛应用于描述和研究并发、异步和分布式特征的系统，并提供了一种可操作语义及定性和定量分析3。最近的研究表明，Petri网适合用来描述服务组合的特性4,17。而可靠服务组合的构建不仅可以满足服务消费者的功能需求，同时也能反应出服务的事务属性及失效处理。Petri网及其相关的分析方法为这些目标实现提供了理论基础。本文要解决的就是如何根据服务消费者的需求来动态地分配可用服务，以构建所需的可靠服务组合。为此，提出一种基于Petri网构建可靠服务组合的方法。基本思路为：首先利用Pe

5、tri网对任务及任务间的关系进行建模，生成相应的工作流模型；其次针对服务的事务属性，构建服务组合的失效处理模型（Service Compositions Failure Processing, SCFP），并分析SCFP模型的动态性质，从而保证所得到模型的正确性；最后给出可靠服务组合的定义，分析可靠服务组合构造的充分必要条件，提出相应的协调策略并证明其有效性，同时给出协调策略的具体实施。本文第2节给出了工作流的Petri网模型；第3节分析服务的事务属性和服务组合的失效处理机制，生成相应的SCFP模型；第4节提出可靠服务组合的协调策略及实施方法；第5节通过具体实例说明可靠服务组合的构建与分析过程

6、；第6节阐述了相关的研究工作；最后是结论和下一步工作。2 工作流的Petri网模型服务组合的功能可以由多个独立运行的子功能构成，本文将每个子功能称为任务。在服务组合流程中，每个任务会有多个可用服务与之对应。本文假设每个服务只能完成一个任务的功能，因此在服务组合中服务和任务是一一对应的。带事务属性的服务组合流程可以从工作流和失效处理两方面进行描述15，工作流描述任务之间的数据通信或同步，具体说明了任务组件之间的关系，直观上可以理解为一系列任务的依赖关系。而服务组合的失效处理则规约了服务运行失败时的处理机制，定义了服务的事务属性和服务的失败处理。两者主要区别是：前者假设服务还没分配，仅仅描述服务组

7、合流程的数据依赖；后者假设服务已经分配，主要考虑服务的事务属性和服务失败处理。本节依据服务消费者提供的功能需求，利用Petri网的基本原理，按接口匹配的原则建立系统的工作流模型。2.1 任务Petri网模型由于系统的功能是由一系列任务组合而成，而任务的组合又可以构成一个新的任务，如此嵌套可以构造出任意复杂的系统。因此，可利用Petri网对任务进行建模，且每个任务在运行过程中需要输入某些参数和输出一定的结果。下面给出任务的形式化定义。定义1：有界Petri网C=(P,T,F)称作任务，其中：（1）P=PSÈPI是一个有限库所集，PI表示任务的接口，PS表示任务的位置，其中PSÇ

8、;PI=F；（2）T是一个有限的变迁集，m0，并且PÈTF, PÇT=F；（3）FÍ(P×T)È(T×P)是有向弧集合，F称为流关系；图1 带有接口的任务C1在任务模型中，接口代表该任务输入或输出（参数则映射为库所中的令牌）。本文假设任务只有获得所需参数才能运行开始操作，且运行结束后统一输出参数，具体接口个数可以根据实际情况增减。图1中的任务C1有三个接口：库所Pi1和Pi2存放任务开始操作（tin）所需的参数，而库所Pi3则存放任务结束（tin）的输出结果。Pin, Pe表示任务C1的开始和结束位置。某时刻各库所中令牌的分布状况称为

9、任务的标识，在标识M下，库所p中的令牌数量记为M(p)；变迁t在标识M下使能的，记做Mt>，否则记做Mt<；任意xÎ(PÈT)，集合x=y|yÎ(PÈT)Ù(y,x)ÎF和x=y|yÎ(PÈT)Ù(x,y)ÎF分别对应于x的输入和输出；其它的定义和触发规则与基本Petri网的定义一样，具体参照文献3。2.2 工作流模型本文采用了进程代数的一种扩展机制来描述工作流中各个任务之间的关系，形成整个系统所对应的表达式5。在应用算子的过程中，可以用括弧来表达作用的顺序（其中顺序算子的优先级最高

10、）。由于模型中的循环结构，可以利用文献6介绍的“解循环”操作，即通过统计任务的历史数据，计算循环的平均执行次数n。因此，本文主要对任务间的顺序、选择和并发关系建模，循环结构可以通过任务的顺序执行来完成。假设Ci和Cj为两个任务，下面先描述任务间的基本关系：（1）算子>表示顺序：Ci>Cj表示任务Ci和Cj顺序运行，即Cj只有在Ci运行结束后才能开始。（2）算子+表示选择：Ci+Cj表示任务Ci和Cj只有一个可以运行。（3）算子|表示并行：Ci|Cj表示任务Ci和Cj可以同时运行，但要它们都执行结束后整个组合才算执行结束。通过采用上述的算子可以将任务间的关系描述为一个表达式。将在任务

11、Ci运行时刻已经结束的任务称为Ci的前向任务，而Ci运行结束时还未开始的任务称为Ci的后向任务。为了区别任务的操作，在相应的变迁和库所前标注对应的任务。如任务Ci中的开始变迁，表示为Ci·tin。如果变迁是为了描述任务间关系而引入，则不标注。顺序结构允许两个任务Ci和Cj顺序地执行，当一个任务需要用到另外一个任务的输出时就要使用顺序结构来组合。顺序运行Ci>Cj的Petri网模型如图2所示。在Ci和Cj中引入接口Pij使得，Pij=Ci·te，Pij=Cj·tin。Pij的存在使得任务Cj只能在Ci结束之后开始运行。图2 顺序关系的建模为了构造任务间的并行，

12、选择和循环关系，需要分别对任务间的两对基本组件即AND-split和OR-split，AND-join和OR-join进行建模，具体的Petri网模型如图3所示（设任务Ck是Ci1,Ci2, ,Cim的共同前向/后向任务）。AND-split的Petri网模型如图3（a）所示：在Ck中引入接口Pki1, Pki2, , Pkim，每个并行的任务Cij中引入接口Pkij。其中Pkij=Ck·te, Pkij=Cij·tin, j=1, 2, , n。OR-split的Petri网模型如图3（b）所示：在Ck和所有的选择任务中引入接口Pij使得Pij=Ck·te, P

13、ij=Ci1·tin, Ci2·tin, , Cim·tin。AND-join的Petri网模型如图3（c）所示：在Ck中引入接口Pki1, Pki2, , Pkim，每个并行的任务Cij中引入接口Pkij。其中Pkij=Ck·tin, Pkij=Cij·te, j=1, 2, n。OR-join的Petri网模型如图3（d）所示：在Ck和所有的选择任务中引入接口Pij使得Pij=Ck·tin, Pij=Ci1·te, Ci2·te, Cim·te。图3 基本组件的建模下面结合Petri网的合成运算，匹配

14、相应的接口以构造整个系统的工作流模型。定义2：设系统中的任务Ci=(Pi,Ti,Fi)，则按照下列步骤构造的五元组S=(C;P,T,F,M0)称为系统的工作流模型： （1）C=C1, C2, , Cn，n为系统中任务的个数；（2）依据任务间关系，合成C1, C2, , Cn的对应接口；（3）引入变迁Tstart和库所Pstart分别描述整个系统的初始位置和开始操作，且：Tstart=Pstart, Tstart=Ci1·Pin, Ci2·Pin, , Cin·Pin, Pstart=F, Pstart=Tstart；（4）设置初始标识M0(Pstart)=1，其余

15、库所为0。工作流模型描述整个系统所能完成的功能，对工作流模型中每个任务分配具体的服务则构成了服务组合。如果分配过程中考虑服务的事务属性，则称它为带事务属性的服务组合。本文中如无特殊说明，服务组合均指带事务属性的服务组合。下面根据所得的工作流模型构造服务组合的失效处理模型。3 服务组合的失效处理模型3.1 服务的事务属性由于Web服务自身的特点，使得传统的事务处理技术无法直接应用在Web服务事务的处理过程，文献7提出的模型指明了服务事务属性的语义，该模型是基于文献8所考虑的三种不同的类型的事务属性。由此可以延伸Web服务执行任务时主要有下面三种特性：可重复的（r），可补偿的（cp），不可补偿也不

16、可重复的（p）。相应的服务事务属性可以有以下几种情况：cp、p、r、r,cp。根据服务的事务属性，可以建立如图4所示的模型。图4（a）是对可补偿的服务进行建模，PItr表示该服务事务处理的条件。库所Si·PItr中有令牌表示服务组合中有其它服务失败，需要根据服务Si的事务属性进行相应的协调。而服务的输入和输出（PIin, PIe）根据实际需要可以进行增减。可补偿服务的运行过程可能处于初始、运行、结束、中断、取消、补偿和失败位置，其中Pin, Pac, Pe,Pab, Pca, Pcp, Pfa称为任务的位置库所。其它的事务属性可以用类似的方法进行描述，具体的模型如图4(b)图4(d)

17、。图4 服务的事务属性模型 通过对图4的分析可知，事务属性不同的服务，运行过程可能到达的位置集和操作也不同。图4中库所和变迁的实际映射如表1所示：表1 事务属性模型中变迁和库所的对照P/T位置/操作P/T位置/操作P/T位置/操作Pin初始位置Pab中断位置Pfa失败位置Pe结束位置Pca取消位置Pcp补偿位置Pac运行位置PIe结束输出PIc失败输出PItr事务输入PIin运行输入tin运行操作tca取消操作trt重试操作tfa失败操作tcp补偿操作tab中断操作te结束操作从表1可知，采用Petri网可以精确地描述服务的事务属性。将初始、运行、结束和失败位置称为服务的运行位置，而中断、取消

18、和补偿位置称为服务的事务位置。3.2 服务组合的失效处理模型由于每个服务具有自身的事务属性。当某个服务运行失败时，如何协调其它服务，保证整个系统的可靠运行，成为服务组合中必须解决的一个问题。本文引入失效处理模块（FCM）来处理该问题。假设同一时刻系统中最多有一个服务失败，其服务失败处理时间可以忽略。由于实际情况中有些任务是不可取消的也不可以补偿的（NCC），这类任务所对应的服务协调操作比较特殊。如其它服务失败的时刻该服务处于运行位置，则协调其到达结束位置。其对应的服务模型如图5所示，其中tce是服务的协调操作。与结束操作te不同的是，该操作虽然也能让服务运行结束，但不输出结果。图5 不可取消任

19、务对应的服务模型不妨设服务Si是完成Ci的功能，则服务组合的失效处理机制有：（1）设任务Ci是Cj的前向任务，若服务Si失败，则中断服务Sj。（2）设任务Ci是Cj的前向任务，若服务Sj失败，分两种情况协调Si：服务Si是可补偿的，则对Si进行补偿；服务Si是不可补偿的，则不做任何操作，服务Sj停留在结束位置。（3）设任务Ci是Cj并行运行，若服务Si失败，分四种情况协调Sj：服务Sj处在运行位置且任务Cj可取消的，则取消Sj的运行；服务Sj处在运行位置且任务Cj不可取消的，则协调Sj的运行使其到达结束位置；服务Sj处在结束位置且Sj是可补偿的，则对Sj运行补偿；服务Sj处在结束位置且Sj是不

20、可补偿的，则不做任何操作，服务Sj停留在结束位置。失效处理模块的功能为：当系统中某个服务运行失败时，基于上述处理机制，依据其它服务的事务属性协调系统结束。下面对FCM进行建模（同理在变迁和库所之前标注对应的服务）。引进库所Pc和变迁tc分别表示系统协调的初始位置和协调操作，使得：（1）·Pc=S1·tfa, S2·tfa, , Sk·tfa, Pc·=tc（2）·tc=Pc, ·tc=S1·PItr, S2·PItr, , Sn·PItr条件（1）表明服务组合中若有服务失败则调用FCM模型；条件

21、（2）描述了FCM模块给每个服务都输入事务处理参数。若对工作流模型S中的每个任务都分配一个服务，则构成了具体的服务组合，不妨设S为分配好的服务集。基于此，下面给出服务组合的失效处理模型形式化定义：定义3：工作流模型S，S是所分配的服务集，则按照下列步骤构造的四元组SS=(Ps,Ts,Fs;Ms0)称为服务组合的失效处理模型（Service Compositions Failure Processing, SCFP）：（1）根据服务的事务属性建模构造S集合中每个服务的Petri网模型；（2）按照S中的数据流程合成服务的Petri网模型；（3）依据上述FCM模型的建模方式添加相应的变迁和库所。（4

22、）保持S中的初始状态不变。从定义3可以看出SCFP模型是在工作流模型S的基础上对带事务特性的服务组合进行建模。3.3 模型性质本文中系统状态由标识M表示，如M(Ci·Pe )=1表示在状态M下，任务Ci已经运行结束。将任务Ci在状态Ma中不为零的库所记作Mai。下面分析SCFP模型的一些主要性质。性质1：SCFP模型SS中，任一可达状态M下的每个服务都只能处于一个位置。证明：从建模过程SS可知，服务Si的位置库所满足库所不变量：M(Si·Pin)+M(Si·Pac)+M(Si·Pca)+M(Si·Pfa)+ M(Si·Pe)+M(Si

23、·Pab)+M(Si·Pcp)=1。而服务组合一旦运行，会对每个服务进行初始化（变迁Tstart），即输入令牌到库所Si·Pin。根据Petri网的运行机制可得：服务只能处于初始、运行、取消、失败、结束、中断和补偿位置中的一个。 证毕ÿ同一个SCFP模型由于任务对应的服务失败时刻不同，系统的终止位置也会不同。按照任务间的关系计算出工作流模型S的所有可能终止状态，记为TS(S)。其中TS(S)=MEÈTSF(S)：（1）正常终止状态ME："iÎ1,n®ME(Ci·Pe)=1，ME表示系统中所有任务都正常结束

24、的状态。对于一个工作流模型，其正常终止状态唯一。（2）失败终止状态集合TSF(S)："MFÎTSF(S)有$iÎ1,n®MF(Ci·Pfa)=1，MF(Ci·Pfa)表示系统中任务Ci失败，经过系统协调到达的终止状态，也称MF(Ci·Pfa)是Ci的失败终止状态。记集合TSF(S,Ci)是任务Ci在TSF(S)中的所有失败终止状态集合。在服务组合中，失效处理机制是系统的核心。因此有必要分析建立的模型是否保证该处理机制。性质2：SCFP模型SS保证了服务组合的失效处理机制。证明：（1）证明SS保证了服务组合的失效处理机制（1）

25、设任务Ci是Cj的前向任务，在状态M下服务Si失败M(Pc)=1Pc·=tc, ·tc=Pc, ·tc=S1·PItr, S2·PItr, , Sn·PItrMtc>M, 其中M(Sj·PItr)=1任务Ci是Cj的前向任务M(Sj·Pin)=1MSj·tab>MSj·tab>M, 其中M(Sj·Pab)=1系统中断了服务Sj即SS保证了服务组合的失效处理机制（1）。同理根据任务间的关系，可以分别证明SS保证了服务组合的失效处理机制（2）和（3）。综上所述，SCFP模

26、型SS保证了服务组合的失效处理机制。 证毕ÿ性质2指出本文建立的模型可以确保服务组合的失效处理机制正确运行，从而说明了失效处理机制建模方式的正确性。性质3：SCFP模型SS中，任一可达状态M下若存在某个服务是处于事务位置，则存在唯一的服务处于失败位置。证明：不妨设在终止状态M下，服务Si处于事务位置，即中断、取消或补偿。M(Si·Pca)+M(Si·Pab)+M(Si·Pcp)=1(Si·Pca)=Si·tcaÙ(Si·Pab)=Si·tabÙ(Si·Pcp)=Si·tcp且

27、(Si·tca)Ç(Si·tab)Ç(Si·tcp)=Si·PItr(Si·PItr)=tc, ·tc=Pc, ·Pc=S1·tfa, S2·tfa, , Sn·tfa$SjÎS, M(Sj·Pfa)=1服务组合中同一时刻最多有一个服务失败$!SjÎS, M(Sj·Pfa)=1即存在唯一的服务Sj处于失败位置 证毕 上述主要分析了SCFP模型的基本性质和特征，下面基于上述性质深入分析SCFP模型的一致性。定义4：任意两个终止状态Ma,

28、MbÎTSF(S,Ci)，若对于所有任务Cj(i¹j)，Ma, Mb满足下列两个条件之一：（1）Maj=Mbj（2）Ma(Cj·Pe)+Ma(Cj·Pcp)=Mb(Cj·Pca)+Mb(Cj·Pab)=1称状态Ma和Mb是相容的，记做MaÄMb。否则称状态Ma和Mb是不相容的，记做MaàMb。记TS(S)中与状态Ma相容的状态集合为CS(Ma)。从定义4可知，两个终止状态不相容必须同时满足下列两个条件：（1）属于同一个任务的失败终止状态；（2）存在某个任务在这两个状态下分别处于结束和补偿位置。否则Ma和Mb是相容的

29、，显然状态和自己本身是相容的。定义5：终止状态集合S，若任意的失败终止状态Ma，MbÎS(a¹b)满足下列条件之一，则称S是一致的：（1）"Ci, Cj, Ma(Ci·Pfa)=Mb(Cj·Pfa)=1®Ci¹Cj（2）$i, Ma(Ci·Pfa)=Mb(Ci·Pfa)=1®MaÄMb终止状态集合S是一致的指该集合中任意两个状态要么不属于同一个任务的失败终止状态集，要么相容。下面通过判断模型终止状态集的一致性来分析模型的正确性。定义6：集合STS(SS)称为服务组合SS的可达终止状态集

30、合，若对于任意STSiÎSTS(SS)有：（1）存在变迁序列d，使得M0d>STSi（2）"tÎT, STSit<由于Petri网的特性，服务组合的可达状态可以表示各个可用服务的运行终止状态。如M1=S1·fa, S2·cp, , Sn·ca表示服务组合某次运行终止时：S1处于失败位置，S2处于补偿位置，Sn处于取消位置。而任务与服务是一一对应的，因此可以把状态M1中的服务用所对应的任务来表示。下面从理论上分析SCFP模型所到达的终止状态集合是一致的。定理1：SCFP模型SS的终止状态集合具有一致性。证明：反证法，假设SC

31、FP模型SS的终止状态集合不具有一致性。不妨设Ma, MbÎSTS(SS), MaàMb$SiÎS: Ma(Ci·Pfa)=Mb(Ci·Pfa)=1Ma和Mb不相容$SjÎS(i¹j),使得Ma(Cj·Pe)=Mb(Cj·Pcp)=1依据任务Cj和Ci的关系，下面分三种情况来分析：首先设Cj是Ci的前向任务根据性质1可知，在Si失败时Sj处于结束位置Ma(Cj·Pe)=1Ma(Ci·Pfa)=1Ma(Pc)=1Sj是不可补偿的Mb(Cj·Pcp)=1Sj是可补偿的，与上面推出

32、来Sj是不可补偿的矛盾。同理可以证明当Cj和Ci是并行关系时（服务Sj分可取消的和不可取消的）也存在矛盾。综上所述，SS的终止状态集合具有一致性。 证毕ÿ基于服务组合的失效处理机制，结合任务间的关系可以证明服务组合的终止状态集合满足一致性定义。从而说明SCFP模型的正确性。4 可靠服务组合的协调技术本节给出可靠服务组合的定义，分析可靠性的内在条件，提出服务组合的协调策略并证明其有效性，最后给出协调策略的实施方法。4.1 服务组合的可靠性设可用服务集合WS=WS1, WS2, WSn，其中WSi为任务Ci的可用服务集合，"i¹j有WSiÇWSj=F。服务组

33、合的构造过程就是WSi中服务与任务Ci的匹配过程。对于具体的服务组合流程，服务消费者的需求可以归结为可接受状态集合。下面给出该集合在SCFP模型中的映射。定义7：集合ATS(S)ÌTS(S)表示服务消费者对工作流模型S的可接受状态集。可接受状态Mi=Mi(C1), Mi(C2), ,Mi(Cn), Mi(Cj)Îab, ca, e, fa, cp。记ATS(S,Ci)表示可接受状态集中任务Ci的失败终止状态。显然MEÎATS(S)，ATS(S,Ci)ÌTSF(S,Ci)。同样只有一致的可接受状态集才是有效的，下面给出可接受状态集有效性的形式化定义：定义8

34、：可接受状态集ATS(S)是有效的，若"MÎATS(S)有：$CiÎC, M(Ci·Pfa)=1®存在唯一的状态MÎATS(S), M是Ci的协调状态且CCS(M,Ci)=ATS(S,Ci)。同理，可以将服务消费者的可接受状态中对任务的终止状态要求转化为对可用服务的终止状态要求。可靠服务组合不仅可以完成系统的功能要求，而且某个服务失败时会到达服务消费者可接受的状态9。下面结合服务组合的工作流模型，给出服务组合可靠性的定义。定义9：设服务组合的工作流模型S=(C;P,T,F,M0)， Ss是基于S的一个服务组合，且服务消费者的可接受状态

35、集为ATS(S)。若Ss满足如下条件，则称服务组合Ss是可靠的：（1）MEÎSTS(SS)（2）STS(SS)ÍATS(S);其中，条件（1）要求服务组合可以完成服务消费者的功能需求，而条件（2）表示SS的所有可达终止状态都是服务消费者可接受的，即在任何情况下，服务组合都能达到服务消费者的可接受状态。根据ME的定义并结合Petri网的运行机制可知，按照第3节方法所构造的Ss模型必定可以到达正常终止状态ME。因此在后面分析服务组合可靠性时，仅需要考虑条件（2）。4.2 服务组合的协调策略本节引入协调集的概念，并分析服务组合可靠性与协调集的关系；其次结合服务消费者的可接受状态集

36、，提出协调策略。定义10：同时满足下列两个条件的终止状态M称为任务Ci的协调状态： s（1）M(Ci·Pfa)=1（2）"CjÎC: Ci|Cj®M(Cj·Pe)+M(Cj·Pcp)=1在任务Ci的协调状态下，其并行任务都处于结束或补偿位置。协调状态是基于任务的失败状态定义的，所以同一个任务的协调状态不唯一。设在工作流模型中任务Ci和Cj是并行关系，若Cj是不可取消的，则称状态集合FS(Ci,Cj)为Cj针对Ci的错误终止状态。其中"MÎFS(Ci,Cj)，使得：M(Ci·Pfa)=M(Cj·P

37、ca)+M(Cj·Pcp)=1。FS(Ci,Cj)指系统中Ci失败而Cj处于取消或补偿的位置。由于Cj是不可取消的，所以在任何情况下Cj都不会到达取消或补偿的位置。定义11：同时满足下列三个条件的终止状态集合CCS(M,Ci)称为系统在Ci失败情况下的协调集：（1）M是Ci的协调状态（2）"MiÎCCS(M,Ci)有MiÄM（3）"CjÎC: Ci|Cj且Cj不能取消，则"MiÎCCS(M,Ci)有Mi(Cj·Pca)+Mi(Cj·Pcp)=0从定义11可知CCS(M,Ci)=CS(M)-

38、00;kj=1FS(Ci,Cj)，其中k为与Ci并行且不可取消的任务个数。对于分配了可重复服务的任务，其CCS(M,Ci)=F。由于同一个工作流模型S中任务的协调状态不唯一，因此协调集也不唯一。系统在任务Ci失败的情况下，依据目前各个任务的位置，协调系统到达协调集中的一个状态。下面分析协调集与SCFP模型状态一致性的关系。引理1：在服务组合模型SS中，若任意服务Si失败，则系统存在唯一与之对应的协调集。证明：反证法 假设服务组合模型SS，在服务Si失败的情况下，系统存在多个协调集。不妨设服务Si失败时，服务组合SS可以依据协调集CCS(Ma,Ci)和CCS(Mb,Ci)对其它服务进行协调。Ma

39、ÎSTS(SS)ÙMbÎSTS(SS)Ma和Mb都是任务Ci的协调状态"CjÎC: Ci|Cj有Ma(Sj·Pe)+Ma(Sj·Pcp)=1，Mb(Sj·Pe)+Mb(Sj·Pcp)=1Ma¹Mb$CjÎC: Ci|Cj且Ma(Sj·Pe)=Mb(Sj·Pcp)=1，即MaàMbMa(Si·Pfa)=Mb(Si·Pfa)=1STS(SS)不一致与定理1矛盾在服务组合模型SS中，若任意服务Si失败，则系统存在唯一与之对应的协调集。 证毕定

40、理2：在服务组合SS中，STS(SS)ÍATS(S)当且仅当任意SS中不可重复的服务Si，存在Ci的协调状态MÎSTS(SS)且CCS(M,Ci)=ATS(S,Ci)。证明：Þ不妨设任务Ci在SS由不可重复的服务Si来完成$MÎSTS(SS)，M是Ci的协调状态由引理1可知：CCS(M,Ci)ÌSTS(SS)STS(SS)ÍATS(S)CCS(M,Ci)ÌATS(S)Ü对于"MaÎSTS(SS)(1) "SiÎS, Ma(Ci·Pfa)¹1即"C

41、iÎC, Ma(Ci·Pfa)¹1Ma=MFMaÎATS(S)(2)$SiÎS, Ma(Ci·Pfa)¹1，即Ci在服务组合SS中分配了不可重复的服务Si服务组合具有一致性$唯一的Ci的协调状态Ma，使得MaÎCCS(Ma,Ci)$SiÎS, Ma(Ci·Pfa)¹1服务Si是不可重复的对于SS中不可重复的服务Si，存在Ci的协调状态MÎSTS(SS)SS中对于不可重复的服务Si只存在一个协调集Ma=MMaÎCCS(M,Ci)CCS(M,Ci)=ATS(S,Ci)M

42、aÎATS(S)综上，"MaÎSTS(SS)®MaÎATS(S)在服务组合SS中，STS(SS)ÍATS(S)当且仅当任意SS中不可重复的服务Si，存在Ci的协调状态MÎSTS(SS)且CCS(M,Ci)=ATS(S,Ci)。 证毕从定理2可知，服务组合可靠性的问题可以通过分析协调集与可接受状态集的关系来实现。由于可靠服务组合SS的可能终止状态集合STS(SS)ÍATS(S)。因此，根据SS的运行机制可知，ATS(S)对SS中调用的服务事务属性存在如下关系：（1）$MÎATS(S),使得M(Ci·

43、;Pfa)=1，则rÏTP(Si)；（2）"MÎATS(S),使得M(Ci·Pfa)=0，则rÎTP(Si)；（3）$MÎATS(S),使得M(Ci·Pcp)=1，则cpÎTP(Si)；（4）"MÎATS(S),使得M(Ci·Pcp)=0，则cpÏTP(Si)。定义12：根据定理2和上述关系，构造可靠服务组合的协调策略为：策略1：调整可接受状态集ATS(S)（1）若$MÎATS(S),M(Ci·Pcp)=1，且$SiÎWSi,TP(Si)=cp,

44、r，则将服务Si分配给任务Ci，ATS(S)=ATS(S)-TSF(S,Ci)；（2）若"MÎATS(S),M(Ci·Pcp)=0，且$SiÎWSi,TP(Si)=r，则将Si分配给任务Ci，ATS(S)=ATS(S)-TSF(S,Ci)。策略2：对未分配服务的任务分配服务（1）若$MÎATS(S)，M(Ci·Pcp)=1，且$SiÎWSi,TP(Si)=cp，则将Si分配给任务Ci，否则出错（可靠服务组合不存在）；（2）若"MÎATS(S), M(Ci·Pcp)=0，且$SiÎWSi

45、,TP(Si)=p，则将Si分配给任务Ci，否则出错；（3）若"MÎATS(S), M(Ci·Pfa)=0，且$SiÎWSi,TP(Si)=r，则将Si分配给任务Ci，否则出错；（4）若"MÎATS(S), M(Ci·Pab)=1，任选WSi中的一个可用服务Si，将Si分配给任务Ci。 其中，策略1的优先级大于策略2，即优先使用策略1，只有策略1不能使用时才调用策略2。利用协调策略构造可靠服务组合的基本思想是：针对特定的服务消费者的需求（可接受状态集），按照协调策略分配服务给任务。4.3 协调策略的有效性协调策略作用是在服务

46、组合流程中如何根据服务消费者的需求来动态地分配服务。因此有必要分析协调策略的有效性，即根据协调策略构造的服务组合是可靠的。定理3：针对有效的ATS(S)，按照协调策略构造出来的服务组合SS是可靠的。证明：不妨设任务Ci在服务组合SS中分配了不可重复的服务SiMaÎSTS(SS), Ma(Ci·Pfa)=1服务组合SS对于Si失败的协调集唯一$唯一的Ci的协调状态Ma，使得MaÎCCS(Ma,Ci)任务Ci在服务组合SS中分配了不可重复的服务Si$MbÎATS(S), Mb(Ci·Pcp)=1（由步骤2（1）推出）可接受状态集ATS(S)有效的$

47、唯一的Ci的协调状态Mb，使得CCS(Mb,Ci)=ATS(S,Ci)定理证明转化为证Ma=Mb反证法，假设Ma¹MbMa, Mb为任务Ci的两个不同的协调状态$CjÎC: Ci|Cj, 有Ma(Sj·Pcp)=Mb(Sj·Pe)=1Mb(Si·Pe)=1"MÎATS(S)，M(Ci·Pcp)=0给任务Cj分配的Sj具有不可补偿的事务属性Ma(Sj·Pcp)=1Sj具有可补偿的事务属性，与上述结果矛盾Ma=MbSS中任意不可重复的服务Si，存在Ci的协调状态MÎSTS(SS)且CCS(M,Ci)

48、=ATS(S,Ci)根据定理2有STS(SS)ÍATS(S)服务组合SS是可靠的。综上所述，针对有效的ATS(S)，按照协调规策略构造出来的服务组合SS是可靠的。 证毕ÿ因此，针对特定的用户需求，采用协调策略生成整个系统的服务组合具有可靠性。4.4 协调策略的实施根据上述分析，采用协调策略构造可靠服务组合的实施步骤如下：（1）构造工作流模型的协调集。该集合不随服务消费者改变而改变。对于同一个流程，协调集是可重复使用的。（2）分析服务消费者可接受状态集是否有效。如果无效，即服务消费者的可接受状态集本身是矛盾的，则提示服务消费者修改可接受状态集。（3）结合服务消费者的可接受状态

49、集，按照协调策略构造可靠服务组合，实施算法如表2所示。该算法首先按照策略1对任务尽可能分配满足条件的可重复服务，并调整可接受状态集；其次基于新的可接受状态集，按照协调策略2继续分配服务，直到所有任务都有相应的可用服务可以满足；若某个任务不存在满足要求的服务则报错。表2 可靠服务组合的构造算法1:Update_ATS(ATS,C,WS) /调整可接受状态2:If $MÎATS(S) and M(Ci·Pcp)=1 /可补偿的3: If $SiÎWSi and TP(Si)=cp,r4: Si®Ci; / ®表示分配操作5: ATS(S)=ATS(

50、S)-TS(S,Ci);6: C=C-Ci; S=SÈSi;/ C和S分别表示任务集和服务集7: Update_ATS(ATS,C,WS) /进行下一轮的调整8: Else If "MÎATS(S) and M(Ci·Pcp)=0) /不可补偿的End If9: If $SiÎWSi and TP(Si)=r10: Si®Ci; ATS(S)=ATS(S)-TS(S,Ci); C=C-Ci; S= S-Si;11: Update_ATS(ATS,C,WS)12:Else return ATS;End IfEnd If13:Match_

51、Service(ATS,C,WS) /对剩下的任务分配服务14:If $MÎATS(S) and M(Ci·Pcp)=115: If $SiÎWSi and TP(Si)=cp16: Si®Ci; C=C-Ci;17: Match_Service(ATS,C,WS);18: Else return False;End If19: Else if "MÎATS(S) and M(Ci·Pcp)=020: If $SiÎWSi and TP(Si)=p21: Si®Ci; C=C-Ci;22: Match_S

52、ervice(ATS,C,WS);23: Else return False;End If24: Else if "MÎATS(S) and M(Ci·Pfa)=025: If $SiÎWSi and TP(Si)=r26: Si®Ci; C=C-Ci;27: Match_Service(ATS,C,WS);28: Else return False;End If29: Else if "MÎATS(S) and M(Ci·Pab)=130: "SiÎWSi; Si®Ci; C=C-C

53、i;31: Match_Service(ATS,C,WS);End IfEnd If5 实例研究本节通过简化的旅游服务来演示协调策略的实施过程。对旅游服务来说，它包括飞机票或火车订购、汽车租赁和行程规划等相关业务。具体服务组合流程为：当客户准备旅游时，首先查阅信息并选择目的地（C0），订购火车票(C1)负责处理客户的火车票，订购飞机票(C2)根据服务消费者的要求订购合适的航班，行程规划(C3)负责目的地具体的行程安排，汽车租赁(C4)安排客户到达火车站或者飞机场，宾馆预订(C5)是客户到达目的地后对所住地方的安排，最后通过当地旅游(C6)负责客户的当地旅游相关事宜。利用第2节介绍的算子，该组合

54、流程可表示为表达式：C0> (C1+C2)>C3>(C4|C5)>C6，假设任务C5是不可取消的。按照工作流模型的建模步骤，可以构造出整个系统的所对应工作流模型S=(C;P,T,F,M0)，如图6所示。图中的库所和变迁刻画了任务的相应位置及任务之间的关系。图6 旅游服务的工作流模型假设目前的可用服务有22个，具体的事务属性如表3所示： 表3 服务的事务属性任务WSTP任务WSTPC0S01pC1S11cpS02r,cpS12PS03cpS13r,cpC2S21pC3S31r,cpS22pS32PS23pS33cpC4S41rC5S51cpS42cpS52pS43pS53

55、r,cpS54rC6S61cpS62pS63cp下面给出服务消费者的当前可接受状态集，如表4所示。其中M8=C0·cp, C1·cp/C2·e, C3·cp, C4·e, C5·e, C6·fa表示服务S6失败时，服务消费者可接受服务S0，S1，S3得到补偿，而其余服务不能补偿。表4 可接受状态集ATSM CATSC0C1/C2C3C4C5C6M1eeeeeeM2faabababababM3cpfaababababM4cpcpfaabababM5cpcpcpfaeabM6cpcpcpefaabM7cpcpcpcafaabM8

56、cpcp/ecpeefa首先计算该工作流模型的协调集，根据可接受状态集的有效性定义可知ATS是有效的。下面基于ATS，按照协调策略构造服务组合，具体步骤如下：步骤1：应用协调策略1，分配可重复服务所对应的任务，并按照策略1中可接受状态集的计算公式调整ATS。首先分配服务S02给任务C0，相应地ATS调整为M1, M3, M4,M5,M6, M7, M8, M10, M11,M12, M13, M14,M15。同理对任务C1, C3, C4, C5分别分配服务S13, S31, S41, S54，最后ATS调整为M1, M8步骤2：应用协调策略2，基于可接受状态集M1, M8，对剩下的任务C2和

57、C6分配服务。最后分配结果为S2=S23, S6=S62。至此，工作流模型中的每个任务都分配一个服务。根据服务的事务属性和服务组合的失效处理机制，可以得到旅游服务的SCFP模型SS=(Ps,Ts,Fs;Ms0)，如图7所示。该模型的可达终止状态集合STS(SS)=M1, M3, M8ÌATS，因此服务组合SS是可靠的。图7 旅游服务的SCFP模型由于篇幅的限制，本文仅仅对简化的旅游服务进行模拟。但是它足以说明服务组合的建模方法和协调策略的正确性。实例模拟过程可知，应用本文所提出方法可以达到如下效果：（1）可以清晰地描述任务及任务之间的关系。（2）正确刻画了服务的事务属性，所构造的模型

58、可以确保服务组合的失效处理机制正确运行。如服务S6运行失败，根据Petri网的运行机制SS模型会到达终止状态M8或M15。（3）协调策略的有效性，按照协调策略所构造的服务组合是可靠的。如图7中的STS(SS)=M1, M3, M8，满足可靠服务组合的定义。因此，SS是可靠的。（4）动态调整可接受状态集，以减少计算量。若每次分配可重复服务后可接受状态集没有进行调整，则每次分配服务都要搜索整个可接受状态集。因此，对于大型服务组合，该方法可以在较快的时间内构造可靠服务组合。6 相关工作现在Web服务事务处理技术正处于不断发展之中，许多公司已经推出处理Web服务事务的协议。Limthanmaphon对

59、这些协议进行总结10，但这些协议是主要是为Web服务技术制定基于XML的标准，并没有考虑到服务消费者的实际需要，且不容易根据服务消费者的需要来动态调整。而使用形式化方法对服务组合事务进行分析也开始有了一些研究成果和工作。在这些工作中，有基于进程代数的11-13，也有基于p演算14的。Butler提出使用CCS与CSP结合的方法来描述Web事务11，它的优点是对结构化活动的恢复机制进行描述，但是它所采用的语法比较复杂，不利于对相关的特性进行推导。Butler等对该方法进行改进12，并采用进程代数来描述相应的语义，但它没有考虑事务运行的不同状态，对模型的正确性验证还没有具体论述。Hashemian

60、采用进程代数的方法来描述无状态的服务13，进而描述服务组合的语义，通过使用图的框架可以表示服务组合的过程，但是它没有考虑服务的状态，而实际中，服务的状态却是服务消费者比较关心的结果。采用p演算主要是对服务协议进行研究，给出扩展p演算的形式化语义。廖军等利用Pi-演算建立Web服务组合模型的规则14，并使用形式化工具分析所建立组合模型的正确性，但是它没有分析服务消费者可接受状态的多样性，且p演算对设计人员的数学功底要求较高，不利于方法的扩展。最近也出现了一些采用事务模式的方法来分析服务的事务属性15,16。Bhiri提出了事务模式的方法描述可靠服务组合15，但它没有对模型进行验证，而且不易对所建立的模型进行分析。Montagut提出一种事务需求的服务组合方法，它考虑了服务的事务属性。但是该方法没考虑服务的失败处理，且采用状态图描述服务的特性，造成模型性质分析的复杂性，使得方法难以推广。与本文相近的