引用本文
范大娟, 黄志球, 肖芳雄, 祝义, 王进. 面向多服务交互的相容性分析与适配器生成. 2014, 44(4): 1094-1103
[FAN Da-juan, HUANG Zhi-qiu, XIAO Fang-xiong, ZHU Yi, WANG Jin. Compatibility analysis and adaptor generation for multi-service interaction. Journal of Jilin University Engineering and Technology Edition, 2014, 44(4): 1094-1103]  
Permissions
Copyright©2014, 吉林大学学报编辑部
版权所有.吉林大学学报编辑部
面向多服务交互的相容性分析与适配器生成
范大娟1,2, 黄志球1, 肖芳雄1, 祝义1, 王进1
1.南京航空航天大学 计算机科学与技术学院,南京 210016
2.南京工程学院 计算机工程学院,南京 211167

作者简介：范大娟（1982-）,女,博士研究生.研究方向:软件工程,形式化方法,服务计算. E-mail:fanbingjie523@126.com

基金:国家自然科学基金项目(61272083, 61170043); “863”国家高技术研究发展计划项目(2009AA010307); 中国博士后科学基金项目; (20110491411); 江苏省博士后科研资助计划项目(1101092C);
摘要

针对已有服务适配方法大多只考虑两个服务交互的简单场景且不支持BPEL代码的自动生成的问题,提出了一种面向多个服务交互的适配器自动生成方法。在通过对有限自动机进行扩展以建模服务的签名和行为信息的基础上,给出了分析多个服务之间相容性的方法。对于不相容的情况,定义了适配器模型的语法和操作语义,给出了适配器模型的自动生成算法,并对得到的适配器模型进行约简以支持适配器BPEL代码的自动生成。通过一个实例分析说明本文所提方法的可行性。

关键词: 计算机软件; 服务组合; 适配器模型; 相容性分析; 多服务交互; 消息映射
中图分类号:TP311 文献标志码:A 文章编号:1671-5497(2014)04-1094-10
Compatibility analysis and adaptor generation for multi-service interaction
FAN Da-juan1,2, HUANG Zhi-qiu1, XIAO Fang-xiong1, ZHU Yi1, WANG Jin1
1.College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China
2.School of Computer Engineering,Nanjing Institute of Technology,Nanjing 211167,China
Abstract

Most existing service adaptation methods only consider the simple scenarios where two services interact and do not support the automatic generation of BPEL codes. To overcome these shortcomings, an automatic service adaptation approach for multi-service interactions is proposed. The signatures and behaviors of services are modeled by extending the finite automata. Based on the extended model, the compatibility for multiple services is analyzed. For incompatible cases, the syntax and operational semantic of the adaptor model are defined and the automatic generation algorithm for the adaptor model is presented. The generated adaptor model is then reduced in order to be automatically mapped into the BPEL codes. The feasibility of the proposed approach is validated by a case analysis.

Keyword: computer software; service composition; adaptor model; compatibility analysis; multi-service interactions; message mapping
0 引 言

Web服务作为实现SOA架构的重要技术有效地解决了在分布、动态、异构环境下的应用集成问题。由于单个Web服务提供的功能有限,为了满足实际应用的需要,常常通过组合已有Web服务以形成增值的、具有更大粒度的Web服务。近年来,关于Web服务组合的研究工作取得了重要进展,已逐渐从只侧重于组合的功能方面的研究转向支持QOS,比如代价、时间属性[ 1],可信性[ 2]和能耗[ 3]等方面的研究;同时由于服务自身和需求的动态变化特点,传统的静态服务组合的研究也逐渐向动态服务组合的方向转变[ 4]。

在进行服务组合时,由于不同的Web服务常常由不同的提供者独立开发,它们在签名层或行为层上可能不相容而导致不能直接组合。如何消除Web服务在签名层和行为层上的不相容,从而实现服务的正确组合非常关键。服务之间的不相容表明交互的服务之间发生了失配(Mismatch),失配包括签名层失配(Signature-level mismatches)和行为层失配(Behavioral-level mismatches)。服务适配技术通过构造适配器的方法来消除服务之间的不相容而不改变服务内部代码,以支持服务的正确组合[ 5, 6]。

目前,有关服务适配的研究引起了国内外的广泛关注。如文献[7]对服务之间WSDL签名层上的不相容进行适配,假定功能相似的服务的签名只在组成消息的部件上不一致,而在消息名上相同,即不考虑消息名称失配的情况。文献[8]对于在签名层不相容的服务,通过改变WSDL签名描述使得服务之间可以正确交互。文献[9]利用YAWL工作流语言作为中介语言,对于两个BPEL流程,通过合并两者的对偶服务执行树(Dual service execution trees)的方法自动生成适配器以消除它们在行为层上的失配。文献[10]针对两个异步通信的流程服务,生成最小适配器以消除流程服务之间行为层上的不相容,最小适配器只处理引起失配的消息,可以降低服务组合运行时的通信开销。文献[11]定义了若干个基于BPEL代码的适配模板,每一个模板对应一种失配的输入。开发者可以根据Web服务之间签名层和行为层不相容的情况,利用适配模板生成BPEL适配代码。文献[12]利用模式匹配技术识别签名层和行为层的失配,并通过生成失配树的方法得到适配器规约。

以上研究工作主要存在如下不足:①文献[7-10]只关注服务签名层或行为层上的适配。而由于需要组合的多个服务通常是由不同提供者独立开发,它们往往在签名层和行为层上均不相容,只考虑某一层上的适配难以有效支持服务组合的正确执行。②上述方法[ 7, 8, 9, 10, 11, 12]主要针对的是两个服务交互的简单场景,而实际的Web服务组合往往是多个服务参与的复杂交互场景。③上述方法[ 7, 8, 9, 10, 11, 12]所生成的适配器模型可能包含BPEL不能实现的部分,因此不能直接映射生成实际的适配器BPEL代码,且文献[11-12]所提出的方法不支持服务的自动适配,需要开发者的介入以生成相应的适配器。

针对以上问题,本文研究了面向多个服务参与的复杂交互情形下的适配器自动生成方法。首先对有限自动机(Finite automata,FA)进行签名和行为的扩展(称其为SBA模型)以同时建模服务的签名和行为信息,给出了基于SBA模型分析多个服务之间相容性的方法。定义了适配器模型的语法和操作语义,根据服务的SBA模型和服务之间的消息映射给出了适配器模型的自动生成算法,并讨论如何针对适配器模型中不能实现的部分(比如不确定、不可达等部分)进行约简的方法。最后通过一个实例分析说明了本文所提方法的可行性。与已有服务适配方法相比,通过该方法生成的适配器可以消除多个服务之间在签名层和行为层上的不相容以支持服务组合的正确执行。另一方面,该方法考虑如何对生成的适配器模型中BPEL不能实现的部分进行约简,因此可以支持从适配器模型到BPEL代码的自动生成。

1 服务的签名、行为建模

服务的签名包括服务的一组操作,由服务的WSDL文件描述。服务的每一个操作都可以看作是一个输入或输出消息。服务的每一个消息均由一个或多个部件组成,每一个部件对应一个类型。因此消息的类型常常是由其部件的数目、顺序和类型所决定的结构体类型。基于上述讨论可知,服务的签名可以看作是由服务所包含的消息以及消息的类型所组成的集合。

服务的行为定义了服务的操作调用的顺序,即该服务与其他服务交互时该服务发送或接收消息的动作序列,通常由服务的抽象BPEL流程描述。基于WSDL、抽象BPEL流程描述的服务的签名和行为缺乏精确的语义,需要转换为相应的形式模型表示。

由于有限自动机FA简单、直观、易于理解,具有精确的语义,因此,本文通过对FA模型进行相应的扩展分别用于形式化描述参与组合的单个服务(称为SBA模型)和它们的适配器(称为AM模型),通过SBA模型的组合运算描述SBA模型的组合(称为CBA模型)。下面给出几个关于FA模型的基本概念。

定义1 FA模型。FA模型是一个五元组 M=( S, s0, F, L, T),其中 S是状态集合; s0∈ S是初始状态; F⊆ S是终止状态集合; L是标签集合; T⊆ S×L×S是迁移集合。迁移 t=( s, μ, s')可以表示为 t=s s'。

定义2 迹。FA模型 M=( S, s0, F, L, T)中从状态 s1到状态 sn的迹 μ=μ1 μ2… μn-1∧ s1 … sn,其中, s1,…, sn∈ S, μ1,…, μn-1∈ L。从状态 s1到状态 sn的迹集合记作tr( s1, sn),从初始状态 s0到结束状态 s的迹称为模型 M的迹,模型 M的迹集合记作tr( M),其中, s∈ F。

定义3 死锁状态和死锁迹。FA模型 M=( S, s0, F, L, T),状态 s∈ S是一个死锁状态,当且仅当 s∉ F∧􀱑∃ μ∈ L, s'∈ S:( s, μ, s')∈ T。若模型 M存在死锁状态,记作Deadlock( M)=True,反之,Deadlock( M)=False。模型 M的死锁状态集合记作 Sdead( M)。模型 M中的一个死锁迹 μ, μ=μ1 μ2… μn-1∧ s0 … sn,其中, s0,…, sn∈ S; sn∈ Sdead( M); μ1,…, μn-1∈ L。

由于本文的SBA模型、AM模型、组合模型CBA均基于FA模型进行扩展,因此,定义1~3同样适用于以上模型。比如在SBA模型中标签集合 L对应SBA模型中的动作集合 A,即 μ1,…, μn-1∈ A;在AM模型中标签集合 L对应AM模型中的内部动作集合 AI和外部动作集合 AO,即 μ1,…, μn-1∈ AO∪ AI;在组合模型CBA中标签集合 L对应组合模型中的动作同步集合 AS,即 μ1,…, μn-1∈ AS。

本文对FA模型进行签名和行为的扩展,称其为签名行为自动机,用于形式化描述单个服务的签名和行为信息。

定义4 签名行为自动机(Signature,behavioral automata,SBA)。SBA模型是一个扩展的FA模型SBA =( S, s0, F, ΣM, fT, CD, A, T),其中: S表示状态集合; s0表示初始状态, s0∈ S; F表示正常终止状态集合, F⊆ S; ΣM表示消息集合; fT: ΣM→ DT为消息集合 ΣM到类型集合 DT的映射函数; CD为迁移触发的条件集合; A表示动作集合, A⊆{?,!} ×ΣM×DT; T表示迁移关系, T⊆ S×CD×A×S。其中,若发送动作 a=! m: d,其互补动作为 =? m: d;若接收动作 a=? m: d,则其互补动作 =! m: d。SBA模型的迁移触发条件可为空,表示为 ε∈ CD。若条件 cd1, cd2∈ CD,则条件 cd1∧ cd2表示同时满足 cd1和 cd2的条件。若条件 cd∈ CD,有 cd∧ ε=cd成立。

服务的SBA模型同时包含服务的签名和行为信息,因此利用SBA模型可以自动识别服务在签名层和行为层上的失配,并自动生成适配器进行失配的消解,从而保证了服务组合的正确执行。

2 多个服务之间相容性分析

参与组合的Web服务通常是由不同开发者提供,使用不同的命名空间和类型定义来描述服务的签名,使用不一致的消息交互序列来描述服务的行为。因此,Web服务之间在签名层和行为层上的不相容的现象常常发生。对多个不相容的服务进行组合将使得组合系统不能正确执行。在进行服务组合之前,需要分析服务之间的相容性。

已有分析服务之间相容性的方法大多只考虑两个服务之间在行为上的相容性[ 5, 13],通常根据这两个服务之间的行为是否是完全相反的或者通过一个服务在某一状态下发送消息的集合和与另一服务在相应的状态下接收消息的集合是否存在包含关系来确定。因此,此类(基于二元运算)相容性判定方法不适合用于判定多个服务之间的相容性。此外,已有相容性判定方法常常忽略了服务的签名信息,它们假设相同消息名的消息具有相同的类型,在此假设下通过消息名匹配来分析服务之间的相容性,因此不能识别签名层的某些失配,比如消息类型失配等。

在实际应用中,服务组合往往是多个服务参与的复杂交互场景,且服务同时包含静态的签名信息和动态的行为信息,由于服务的SBA模型同时刻画了服务的签名和行为信息,因此本文基于SBA模型来分析服务之间在签名层和行为层上的相容性。服务之间的不相容意味着它们的组合系统会发生死锁,因此,可以通过检测 N个服务的SBA模型的组合模型是否存在死锁状态来判定这 N个服务是否相容。

定义5 SBA的组合模型(Composition model of N SBA models,CBA)。 N个SBA模型SBA i=( Si, , Fi, , , CDi, Ai, Ti), i={1,…, N},它们的组合模型SBA1 |SBA2 |… |SBA N可以被表示一个扩展的FA模型CBA =( S, s0, F, ΣM, CD, AS, T),其中: S⊆ S1 ×… ×SN, s0 =( ,…, ), F⊆ F1 ×… ×FN, ΣM⊆ , CD⊆ CD1 ×… ×CDN, AS是动作同步集合, AS⊆ ΣM×{1,…, N} ×{1,…, N} ×DT,(( s1,…, sN), cdi∧ cdj, m( i, j): d,( s'1,…, s'N))∈ T⇔∀( s1,…, sN)∈ S,∃ i, j∈{1,…, N},∃( si, cdi,! m: ( m), s'i)∈ Ti∧∃( sj, cdj,? m: ( m), s'j)∈ Tj∧ ( m) = ( m) =d∧( cdi∧ cdj≠ F):∀ k∈{1,…, N}:( k≠ i, j⇒ s'k=sk)。

其中, DT是消息的类型集合,公式 ( m) = ( m)表明消息 m在服务 i和服务 j中具有相同的类型。 cdi∧ cdj≠ F表示条件 cdi与条件 cdj相交,即表达式 cdi∧ cdj不是永假式。

N个SBA模型的组合模型CBA反映了这 N个服务的所有交互行为。因此,组合模型的状态对应着各个SBA模型的状态的组合。对于组合模型的某一状态 s=( s1,…, sN),从该状态 s出发,在条件 ci∧ cj下存在迁移 t: s s',当且仅当服务 i在其状态 si和条件 cdi下执行发送消息动作! m: d,服务 j在其状态 sj和条件 cdj下执行互补的接收消息动作? m: d, m( i, j): d∈ AS表示服务 i与服务 j在发送消息动作! m: d和其互补动作? m: d上的同步。

定义6 服务相容。 N个服务的SBA模型为SBA i=( Si, , Fi, , , CDi, Ai, Ti), i={1,…, N},称这 N个服务相容当且仅当它们的组合模型CBA不存在死锁状态,即 Deadlock(CBA) =False。

判定 N个服务是否相容的步骤:①首先根据定义5的计算方法,自动生成这 N个服务的SBA模型的组合模型CBA;②利用定义3中有关死锁状态的形式化定义,自动判断该CBA模型是否存在死锁状态。若不存在死锁状态,则表明这 N个服务之间是相容的,因此可以直接进行组合;若存在死锁状态,则意味着这 N个服务在签名层或行为层不相容,需要生成适配器消除服务之间的不相容,使得服务组合能够正确执行。

若 N个服务的SBA模型的最大状态数为 ,则上述多个服务之间相容性方法的时间复杂度为计算 N个SBA模型的组合模型CBA的时间复杂度( O( |S|N))与判断CBA模型是否存在死锁状态的时间复杂度( O( N))(在生成CBA模型的过程中,若某一状态下无迁移,则通过判断该状态是否为终止状态的方法来确定是否为死锁状态)之和。通常,有 N≪ |S|N,因此本文的多个服务之间相容性分析方法的时间复杂度为 O( |S|N)。

3 多个服务之间适配器的自动生成

已有服务适配方法大多针对只有两个服务参与组合的情形,未考虑多个服务参与组合的复杂交互场景[ 7, 8, 9, 10, 11, 12],且文献[7-10]仅仅针对的是签名层(或行为层)上的适配问题。比如文献[7-8]只关注两个服务之间在签名层上的适配,该方法只适合于简单的无状态服务,而在实际应用中,绝大多数服务是具有行为信息的有状态服务。文献[9-10]研究的是两个服务之间行为层的适配问题,适配器仅通过消息交互的外部动作来消除服务之间的失配,未考虑适配器的有关消息处理的内部动作,因此不能处理签名层上的失配。

此外,文献[11-12]中适配器的生成方法是半自动化的。在文献[11]中,开发者需要根据两个服务之间不相容的情况,人工识别并组合适配模板以生成相应的适配器。文献[12]在适配器的生成过程中需要开发者选择消解失配的方式并提供相应的消息构造信息。以上服务适配方法[ 7, 8, 9, 10, 11, 12]均没有涉及如何对得到的适配器模型中BPEL代码不能实现的部分进行约简,从而不能直接从适配器模型映射生成实际的适配器BPEL代码。

由于SBA模型同时刻画了服务的签名信息和行为信息,因此,本文将基于SBA模型提出一种面向多服务交互的适配器自动生成方法。首先引入多个服务之间的消息映射概念,给出具有消息处理的内部动作和消息交互的外部动作的适配器模型的语法和操作语义,使得适配器可以同时处理多个服务之间签名层和行为层的失配情况。在此基础上给出适配器模型的自动生成算法,讨论如何对得到的适配器模型进行约简的方法以支持实际BPEL代码的自动映射。

3.1 服务之间的消息映射

服务之间的消息映射是一组消息转换规则,即某个服务所需要接收的消息如何通过其他服务的发送消息来构造。消息映射表明了消息之间的语义依赖关系,可以利用语义Web和本体论的相关知识构造服务之间的消息映射[ 14]。由于本文主要关注的是服务适配方法本身,即如何根据给定的服务的SBA模型和服务之间的消息映射 M生成相应的适配器,因此假定消息映射 M已经由开发者给出。

定义7 服务之间的消息映射 M。服务之间的消息映射 M由 N个消息转换规则集合 MT构成,即 M=MT1∪…∪ MTN,其中, N为参与组合的服务的数目,每个消息转换规则集合 MTi由多个消息转换规则 mt构成,集合 MTi表示如下:

MTi={ w1 .sm1,…, wK.smK or NULL i. rm|∀ j∈{1… K}: wj∈{1… i-1}∪{ i+1… N}∧ smj∈ , rm∈ },1≤ i≤ N。

其中,函数 Systh给出如何根据 K个分别隶属于服务 w1,…, wK的发送消息 sm1,…, smK来构造隶属于服务 i的接收消息 rm的方法。若消息转换规则 mt的左部为空,即 NULL i.rm,则表示接收消息 rm可以自动生成(此时, Systh为消息生成函数 Create)。此类消息一般为简单的控制消息,比如确认消息(Acknowledgement message)或具有默认值的消息[ 15]。

文献[ 16]研究的是组件之间的适配问题,利用同步矢量作为适配契约并根据各个组件的接口描述自动生成适配器来消除组件之间的失配。但由于同步矢量只能表达两个消息之间的匹配关系(是一种特殊的映射关系),该方法不能处理消息分裂/合并失配等情况。而本节中引入的多个服务之间的消息映射概念不仅给出了涉及多个消息之间的映射关系,并且指明适配器如何对接收到的多个消息进行处理以生成另一服务需要的消息的方法,因此可以处理服务之间更多的、更复杂的失配情况。

3.2 适配器模型描述及其自动生成

适配器本质上是服务组合的编制器(Orchestrator),服务之间所有交互的消息必须通过适配器进行转发。为了描述适配器与服务之间的交互情况,需要将适配器的发送/接收动作与具体的服务相关联,即对发送/接收动作进行标记。

定义8 标记函数 fi。服务的SBA模型SBA i=( Si, , Fi, , , CDi, Ai, Ti), fi为标记函数, i={1,…, N},则有: fi( Ai) ={ a( i) , fi( ) ={ ( i) 。

其中,标记动作? m( i): d表示适配器接收从第 i个服务发送的类型为 d的消息 m,标记动作! m( j): d表示适配器发送类型为 d的消息 m至第 j个服务, i, j∈{1,…, N}。

定义9 适配器模型(Adaptor model),简称AM。 N个服务的SBA模型SBA i=( Si, , Fi, , , CDi, Ai, Ti), i={1,…, N},它们的适配器模型AM可形式化定义为一个扩展的FA模型AM =( S, s0, F, AO, AI, T),其中: S表示适配器的状态集合, S=S1 ×… ×SN×δ, s0表示适配器的初始状态, s0 =( ,…, ,), F表示适配器的正常终止状态集合, F⊆ F1 ×… ×FN×δF, AO表示适配器的外部动作集合, AO⊆ fi( ), AI表示适配器的内部动作集合, AI⊆ MT1∪…∪ MTN, T表示迁移关系, T⊆ S×(( CD×AO)∪ AI) ×S。

其中, δ为适配器的消息配置集合,适配器的消息配置 σ∈ δ是指适配器在某一时刻存储的消息对应的相关信息集合(包括消息名、消息类型和消息隶属的服务),有 δ=2 γ, γ= {( m, d, i) ∧ d∈ ( m)}。 δF为适配器处于结束状态时的消息配置集合, δF⊆ δ。初始时, σ=∅。适配器到达其结束状态时, σ∈ δF不一定为∅,若不为∅,则表示存在某服务发送的消息未被另一服务接收的情况,这个(些)消息由适配器拦截。

适配器的动作分为外部动作和内部动作,外部动作 a∈ AO是指适配器从某一服务接收消息或发送消息至某一服务。内部动作 a∈ AI为服务之间的消息映射 M中某一消息映射规则 mt,表示适配器根据该消息映射规则对接收到的消息进行相应的内部处理。

下面将通过定义AM模型的操作语义来给出它的形式化语义,在操作语义中,通过形如 s s'的形式描述适配器执行相应动作 a时的状态变化,这里的动作 a可以是适配器的外部动作或内部动作。

定义10 AM模型的操作语义。AM模型的操作语义被描述为迁移系统( S, s0,→),迁移关系→定义如下:

发送消息:

( s1,…, sN, σ) ( s'1,…, s'N, σ-{( m, d, i)}),其中,∃ t=( si, cdi,? m: d, s'i)∈ Ti,∀ j∈{1,…, N}: j≠ i⇒ sj=s'j,( m, d, i)∈ σ, i∈{1,…, N}。

接收消息:

( s1,…, sN, σ) ( s'1,…, s'N, σ∪{( m, d, i)}),其中,∃ t=( si, cdi,! m: d, s'i)∈ Ti,∀ j∈{1,…, N}: j≠ i⇒ sj=s'j, i∈{1,…, N}。

内部处理:

①( s1,…, sN, σ) ( s'1,…, s'N,( σ-{( sm1, d1, w1),…,( smK, dK, wK)})∪{( rm, d, w)}),其中, mt=w1 .sm1,…, wK.smK w.rm,∀ i∈{1,…, N}: si=s'i∧∀ j∈{1,…, K}: dj= ( smj)∧( smj, dj, wj)∈ σ。

②( s1,…, sN, σ) ( s'1,…, s'N, σ)∪{( rm, d, w)}),其中, mt=NULL w.rm,∀ i∈{1,…, N}: si=s'i。

若给定 N个服务的SBA模型和服务之间的消息映射 M,按照算法1可以得到相应的AM模型。

算法1.The automatic generation algorithm for the adaptor model

Input:the SBA models of N services and the message mapping M among these services

Output:the AM model of the adaptor Initialization:AO=,AI=,T=,s0=( ,…, ,),S={s0};

Call the Method CreateAdaptor(s0);

CreateAdaptor(s){

visited[]=True;

For i=1 to N

If((si,cdi,!m:d,s'i)∈Ti)Then//适配器接收服务发送的消息m

AO=AO∪{?m(i):d};σ=σ∪{(m,d,i)};

Generate new state s'=(s1,…,s'i,…,sN,σ);

T=T∪(s,cdi,?m(i):d,s');S=S∪{s'};Update si by s'i;Update s by s';

If(s∉Final∧visited[s]==false)Then

CreateAdaptor(s);

Endfor

For i=1 to N

If((si,cdi,?m:d,s'i)∈Ti)Then

If (m,d,w)∈σ Then//若适配器之前存储消息m,则发送该消息至服务

AO=AO∪{!m(i):d};σ=σ/{(m,d,w)};

Generate new state s'=(s1,…,s'i,…,sN,σ);

T=T∪{(s,cdi,!m(i):d,s')};S=S∪{s'};Update si by s'i;Update s by s';

If (sFinal∧visited[s]==false)Then

CreateAdaptor(s);

ElseIf(mt∈M∧(mt=w1.sm1,…,wK.smK

i.m∨mt=NULL i.m))Then//若消息映射M中存在关于消息m的转换规则mt

If((mt=NULL i.m)∨((sm1,d1,w1)∈σ∧…∧(smK,dK,wK)∈σ))Then//适配器按照转换规则mt进行内部处理生成消息m,并发送至相应的服务

AI=AI∪{mt};AO=AO∪{!m(i):d};

σ'=σ▷mt;σ″=σ'!m(i):d;

Generate two new states s'=(s1,…,si,…,sN,σ'),s″=(s1,…,s'i,…,sN,σ″);

T=T∪{(s,mt,s'),(s',cdi,!m(i):d,s″)};S=S∪{s',s″};Update si by s'i;Update s by s″;

If (s∉Final∧visited[s]==false)Then CreateAdaptor(s);

EndFor

}

其中,算法1中的表达式 σ▷ a为在消息配置 σ下执行动作 a后的消息配置情况,计算方法参见定义10。算法思想如下:①适配器接收每一个从服务 i发送的消息 m,1≤ i≤ N, ②对于服务 j需要接收的消息 m,1≤ j≤ N,则判断当前消息配置 σ中是否存在与消息 m匹配的消息,若存在,则发送该消息至服务 j,否则根据消息映射 M中有关消息 m的消息转换规则 mt,判断当前消息配置 σ中是否存在生成消息 m的 K个消息 sm1,…, smK或消息 m是否可以由适配器自动生成,若存在这 K个消息或消息 m可以自动生成,则适配器按照消息转换规则 mt构造消息 m并发送至服务 j。然后把新的状态作为当前状态递归调用自身,直到到达适配器的终止状态或当前状态下没有新的迁移可以加入。根据上述对算法1的分析可知,若 N个服务的SBA模型的最大状态数为 ,则该算法的时间复杂度为 O( |S|N)。

3.3 适配器模型约简

根据算法1得到的AM模型不是最终的AM模型,需要对其进行约简,去除模型中BPEL不能实现的部分,如不确定行为的部分、不可达的部分和死锁部分,约简后的AM模型可以自动映射生成适配器的BPEL代码。

定义11 不确定状态。AM =( S, s0, F, AO, AI, T),状态 s∈ S,若状态 s不符合以下几种情况之一,则称状态 s为不确定状态。①从状态 s出发的迁移数目等于1;②从状态 s出发的接收迁移数目大于等于2,发送迁移数目等于0,这些接收迁移均为有条件约束的迁移,且迁移上的条件两两之间互不相交,即∀ i, j∈{1,…, K}, cdi∧ cdj=F, K为从状态 s出发的接收迁移数目;③从状态 s出发的接收迁移数目和发送迁移数目均大于等于1,这些迁移均为有条件约束的迁移,且迁移上的条件两两之间互不相交,即∀ i, j∈{1,…, K}, cdi∧ cdj=F, K为从状态 s出发的迁移数目。

在不确定状态 s下如何选择某一迁移进行触发是不确定的,需要对该状态下多个冲突的迁移进行去除,使得该状态下迁移的触发是确定的。

约简规则1(状态确定化)。对于AM模型中的所有不确定状态 s,逐步去除从状态 s出发的某个迁移,直到状态 s符合定义11给出的三种情况之一。

对AM模型应用约简规则1后的模型中可能存在不可达状态,因此需要引入约简规则2去除AM模型中的不可达状态。

定义12 不可达状态。AM =( S, s0, F, AO, AI, T)状态 s∈ S是不可达状态,当且仅当不存在从初始状态 s0到状态 s的迹,即tr( s0, s) =∅。约简规则2(去除不可达状态)。在AM模型中去除所有不可达状态 s以及从该状态 s出发或到达该状态 s的迁移。

若AM模型存在死锁状态,则表明对于给定的 N个服务,它们之间存在某些交互情况下的失配是不能通过适配器进行消解的,因此,在利用约简规则1和约简规则2去除模型中具有不确定行为的部分、不可达的部分之后,若AM模型中存在死锁状态,则需要利用约简规则3去除AM模型中的死锁状态以得到最终的AM模型。

约简规则3(去除死锁状态)。在AM模型中去除所有死锁状态以及从该状态 s出发或到达该状态 s的迁移。

利用本节的约简规则1、2、3对AM模型中BPEL不能实现的部分进行约简,使得约简后的AM模型可以直接映射生成适配器的BPEL代码,用于在实际的BPEL执行引擎上运行。

4 实例分析

本节以一个网上医院的应用为例来说明本文方法的可行性,该应用包括Client服务、Specialist服务和Doctor服务,它们的SBA模型见图1,其中:

(1)Client服务通过发送用户名(! mUN)和门诊名称(! mDN)进行登记,然后选择预约专家(! mRS)或门诊挂号(! mRD)。若选择预约专家,则将收到相应门诊的专家信息(? mSL)或收到该门诊暂无专家的提示(? mNS),若暂无专家,则流程结束,若有专家可以预约,则Client发送预约信息(! mRSI),并收到是否预约成功的提示(? mV或? mIV),若预约成功,则流程结束,若预约失败,则可以重新预约(! mRS)或退出预约流程(! mEX)。若Client选择门诊挂号,则将收到挂号信息(? mRLD),Client可以选择接受或取消此次挂号(! mOP),若取消挂号( mOP=0),则收到挂号已取消的提示信息(? mCC),Client将选择重新挂号(! mRD)或退出流程(! mEX),若接受此次挂号( mOP=1),则将收到挂号成功的提示后(? mDS)结束挂号流程。

(2)Specialist服务首先接收预约专家的请求(? mRS),然后接收Client的登记信息(? mRI),根据登记信息中的门诊信息,选择发送相应门诊的专家信息(! mSL)或给出该门诊暂无专家的提示(! mNS),若暂无专家,则流程结束,若有专家可以预约,则发送专家信息,随后接收Client选定的专家姓名(? mSN)和预约时间(? mRT),并判断Client的预约是否有效,若有效,则发送预约成功提示(! mV)并等待Client的确认消息(? mCF),若无效,则给出预约无效的提示(! mIV),等待Client的再次请求(? mRS)或退出预约流程(? mEX)。

(3)Doctor服务首先接收Client的用户名(? mUN)和门诊名称(? mDN),然后接收门诊挂号的请求(? mRD),将生成的挂号信息发送至Client(! mRLD)并等待Client接受或取消此次挂号(? mCO),若Client接受此次挂号( mCO=1),则给出挂号成功的提示信息(! mDS),随后接收来自Client的付款信息(? mPM)并结束流程,若Client取消挂号( mCO=0),则发送挂号已取消的提示信息(! mCC)并结束流程。

图1 网上医院实例中三个服务的SBA模型Fig.1 SBA models for three services composing the online hospital example

Client服务、Specialist服务和Doctor服务之间存在如下消息映射 M=MTSpecialist∪ MTDoctor∪ MTClient:

MTSpecialist ={Client .mUN,Client .mDN Specialist .mRI, NULL Specialist .mCF,Client .mRSI Specialist .mSN,Client .mRSI Specialist .mRT};

MTDoctor ={Client .mOP Doctor .mCO};

MTClient ={Doctor .mRLD Client .mRLD}。

根据第2节提出的相容性分析方法判断出这三个服务之间是不相容的,即这三个服务之间发生了签名层失配,比如消息合并失配(Client服务发送消息 mUN和消息 mDN进行登记而Specialist服务通过消息 mRI接收Client的登记信息)等失配和行为层失配, 比如未指定接收适配(Client服务先发送消息 mUN和消息 mDN进行登记,再发送消息 mRS选择预约专家;Specialist服务先通过接收消息 mRS接受预约,再通过消息 mRI接收Client的登记信息)等失配,因此需要生成适配器以消除这些签名层和行为层的失配。

图2 应用约简规则1前后的AM模型片段Fig.2 The AM model fragments before and after applying reduction rule 1

根据以上三个服务的SBA模型和消息映射 M,利用3.2节的算法1得到的适配器AM模型中包含不确定状态,图2(a)(b)分别为本节实例按照算法1生成的AM模型中含有不确定状态的约简前后模型片段的结果。

对AM模型应用约简规则1-2后得到Specialist服务、Client服务和Doctor服务的适配器的AM模型如图3。其中,图3中的标记s,c,d分别表示Specialist服务、Client服务和Doctor服务。AM模型通过对服务之间的消息进行缓存、消息合并(应用消息转换规则 mt1Specialist)、提取(应用消息转换规则 mt3pecialist和 mt4pecialist)、转换消息类型(应用消息转换规则 mtclient)、生成消息(应用消息转换规则 mt2specialist)等消除了三个服务之间上述签名层和行为层失配。其中, mtNw表示集合 MTw的第 N个消息转换规则。

图3中的AM模型存在死锁状态(灰色状态显示)表示Client服务和Doctor服务的交互过程中发生了不可消解的失配(Doctor服务在通过消息 mDS发送挂号成功的提示信息后将通过消息 mPM接收Client服务的付款信息,而Client服务无相应的付款消息发送,且根据消息映射 M可知消息 mPM不能由适配器自动生成)。因此,需要利用约简规则3去除AM模型中的死锁状态(需去除虚线显示的两个状态)以得到最终的无死锁状态的AM模型。

图3 网上医院实例的最终适配器模型Fig.3 The final AM model for the online hospital example

5 结束语

本文首先提出了SBA模型以形式化描述服务的签名和行为信息,并基于SBA模型给出了多个服务之间相容性的分析方法。对于不相容的情况,则给出了自动生成适配器模型以及对得到的适配器模型进行约简的方法。通过一个实例分析说明本文所提方法的可行性。与已有服务适配方法相比,该方法针对的是多个服务交互的复杂场景,通过该方法生成的适配器可以消除多个服务之间在签名层和行为层上的不相容,以支持服务组合的正确执行。此外,通过对适配器模型进行约简以去除BPEL不能执行的部分,使得约简后的适配器模型可以直接映射生成适配器BPEL代码。

The authors have declared that no competing interests exist.

参考文献
[1] 朱勇, 罗军舟, 李伟. 一种工作流环境下能耗感知的多路径服务组合方法[J]. 计算机学报, 2012, 35(3): 627-638.
Zhu Yong, Luo Jun-zhou, Li Wei. An approach for energy aware multipath service composition based on workflow[J]. Chinese Journal of Computers, 2012, 35(3): 627-638. [本文引用:1] [CJCR: 1.796]
[2] 龙军, 刘昕民, 袁鑫攀, 等. 一种基于信任推理与演化的Web服务组合策略[J]. 计算机学报, 2012, 35(2): 298-314.
Long Jun, Liu Xin-min, Yuan Xin-pan, et al. A web services composition strategy based on trust reasoning and evolution[J]. Chinese Journal of Computers, 2012, 35(2): 298-314. [本文引用:1] [CJCR: 1.796]
[3] 肖芳雄, 李燕, 黄志球, 等. 基于时间概率代价进程代数的Web服务组合建模和分析[J]. 计算机学报, 2012, 35(5): 918-936.
Xiao Fang-xiong, Li Yan, Huang Zhi-qiu, et al. Modeling and analyzing web services composition using timed probabilistic priced process slgebra[J]. Chinese Journal of Computers, 2012, 35(5): 918-936. [本文引用:1] [CJCR: 1.796]
[4] Li Gang, Han Yan-bo, Wang Jing, et al. Facilitating dynamic service compositions by adaptable service connectors[J]. International Journal of Web Services Research, 2006, 3(1): 68-84. [本文引用:1] [JCR: 0.182]
[5] Dumas M, Benatallah B, Nezhad H R M. Web service protocols: Compatibility and adaptation[J]. IEEE Data Engineering Bulletin, 2008, 31(3): 40-44. [本文引用:2]
[6] 张广泉, 戎玫, 王昇. 时间感知Web 服务交互行为建模与失配检测方法研究[J]. 电子学报, 2011, 39(11): 2568-2575.
Zhang Guang-quan, Rong Mei, Wang Sheng. Research on interaction modeling and mismatch checking of time-aware web services[J]. Acta Electronica Sinica, 2011, 39(11): 2568-2575. [本文引用:1] [CJCR: 0.686]
[7] Ponnekanti S, Fox A. Interoperability among independently evolving web services[C]∥Proc of the 5th International Middleware Conference. LNCS 3231, Berlin: Springer-Verlag, 2004: 331-351. [本文引用:4]
[8] Fuchs M. Adapting web services in a heterogeneous environment[C]∥Proc of the 2th IEEE International Conference on Web Services (ICWS 2004). Washington DC: IEEE Computer Society, 2004: 656-664. [本文引用:4]
[9] Brogi A, Popescu R. Automated generation of BPEL adapters[C]∥Proc of the 4th International Conference on Service-Oriented Computing( ICSOC 2006). LNCS 4294, Berlin: Springer-Verlag, 2006: 27-39. [本文引用:4]
[10] Seguel R, Eshuis R, Grefen P. Generating minimal protocol adaptors for loosely coupled services[C]∥Proc of the 8th IEEE International Conference on Web Services (ICWS 2008). Washington DC: IEEE Computer Society, 2010: 417-424. [本文引用:4]
[11] Benatallah B, Casati F, Grigori D, et al. Developing adapters for web services integration[C]∥Proc of the International Conference on Advanced Information Systems Engineering(CAiSE 2005). Berlin: Springer-Verlag, 2005: 415-429. [本文引用:4]
[12] Nezhad H R M, Benatallah B, Martens A, et al. Semi-automated adaptation of service interactions[C]∥Proc of the 16th International Conference on World Wide Web. New York: ACM2007: 993-1002. [本文引用:4]
[13] Bordeaux L, Salaün G, Berardi D, et al. When are two web services compatible?[C]∥Proc of the TES. Berlin : Springer, 2004: 15-28. [本文引用:1]
[14] Van der Aalst WMP, Mooij A J, Stahl C, et al. Service interaction: Patterns, formalization, and analysis[C]∥Proc of the 9th International School on Formal Methods for the Design of Computer, Communication, and Software Systems (SFM 2009). LNCS 5569, Berlin: Springer, 2009: 42-88. [本文引用:1]
[15] Zhou Z, Bhiri S, Gaaloul W, et al. Developing process mediator for supporting mediated web service interactions[C]∥Proc of the 6th IEEE European Conference on Web Services (ECOWS 2008). Washington, DC: IEEE Computer Society . 2008: 155-164. [本文引用:2]
[16] Carlos Canal, Pascal Poizat, Gwen Salaün. Model-Based adaptation of behavioral mismatching components[J]. IEEE Transaction on Software Engineering, 2008, 34(4): 546-563. [本文引用:1] [JCR: 2.588]