环境模型驱动的服务组合方法

蔡广军等

摘要：针对服务组合动态、开放、复杂度高的特点，提出了一种环境模型驱动的服务组合方法.该文用环境模型中服务作用下客体的变化来描述服务功能，用客户期望的环境变化描述客户需求，构建了一种独立于服务实现和具体客户的组合环境；然后以环境模型为基础分解需求和组合服务.实验结果分析表明，该文方法可以有效提高服务组合的效率.

关键词：服务组合；环境；模型驱动；动态开放；行为

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2015）13-0208-05

Abstract： To address the challenge of service composition that are dynamic， open and with a high complexity， the paper presents a service composition method driven by environment model. In this paper， by projecting service functionalities and the custom requirement into the environment model， a closed and simple problem domain is constructed. And then a composition method through decomposing the requirement is proposed. The test results show that this method is effective.

Key words： Service Composition； Environment； Model Driven； Dynamic and Open； Behavior

服务的标准化和松耦合为提高软件或应用的互操作能力，重用服务提供了基础。服务组合是实现服务集成、重用服务的主要方式，是面向服务计算成功的关键因素[1]。虽然商务的电子化使Web上的服务越来越多，仅单个购物网站就有300多万个店铺，但服务并没有达到预期的发展速度，该文认为一个主要原因在于缺乏一种可以适应这一需要的服务组合方法。

服务组合的面临的困难包括：一是服务的数量和组合问题的复杂度，存在大量服务是服务优势的来源，但是手工组合方法很难应对大量服务的组合，同时组合问题是一种指数复杂度的问题；二是服务组合的动态性和开放性，服务实现的自主性和异构性以及客户的未知性等性质使得服务组合是动态开放的，而当前的很多自动组合方法和工具只支持封闭世界下静态的组合；三是推理和描述之间的矛盾，语言的描述能力与推理能力成反比，比如参考文献[2]中OWL-Little、OWL和OWL-Full的描述能力逐渐增加，但推理复杂度却分别为多项式时间、指数时间和不可推理。

当前对服务组合的研究可以分为对已有工具能力的应用、对推理工具的扩展和组合问题的定义和分析。如[3]中实现了服务组合问题到层次任务规划问题的转换，使得可以借助已有的Shop2工具组合服务；[4]则通过扩充已有的Golog语言，实现了一种客户化通用程序的组合方法。[5]从服务行为描述的重要性出发，提出了一种行为服务组合的方法，并实现了问题到自动机、描述逻辑等描述语言的转换，以借用已有的理论和工具；WSMO[6]则从组合问题的整体性质出发，提出了一种包含服务、本体、目标和中介四类元素的多层次组合框架。这些方法大多基于某种假设，而没有讨论在服务组合时如何满足对应的假设，而且组合的复杂度也比较高，如[4]等基于行为的组合方法都是指数复杂度的。

与以上方法不同，该文从环境建模的思想出发，提出了一种转换服务组合问题和模型驱动的组合方法。该文的主要创新点包括提出了一种通过创建领域环境模型、投影描述解决动态开放组合问题的方法；并提出了一种基于环境知识提高组合效率的方法，使得可以在多项式时间内组合服务，实验结果表明该方法是有效的。

1 环境建模

环境建模是环境模型驱动服务组合方法的基础。本节先介绍了服务的环境概念、描述服务所需的环境本体、创建环境模型的方法以及如何描述服务和需求以把组合问题限定到环境模型中。

1.1 服务的环境

文中环境的概念来源于需求工程[7]，通过定义环境来区分软件实现方案和问题，使得需求工程专注于获取问题而不陷入实现方案的设计。环境建模中环境的含义与[8]等中的环境不同，它们的含义分别如图1（a）和图1（b）所示。[8]中环境指用户和系统间交互的场景及相关因素，环境建模中的环境不仅包括用户和服务之间的媒介或其它要素，还包括服务的用户以及其它客户关心的且服务作用下发生过变化的内容，是服务可能影响到的现实世界中的所有内容。

服务组合是在单个服务不能满足客户需求的情况下组合多个已有服务来满足需求。服务组合是分布式环境下的一种软件开发方法[9]，从所要考虑的内容看，它与传统软件没有本质的区别，仍然要考虑从客户需求到领域知识以及软件性质等内容。

从环境建模的思想看，服务组合需要考虑系统、现实世界和需求三方面的内容。服务组合的动态开放性体现在服务和需求的动态开放性上，服务的动态开放性是由于为了促进服务间的竞争和服务的改善，难以限制服务的实现方式和范围；需求的动态开放性则在于要满足更多需求、争取更大利润的前提导致的客户或客户需求的多样化以及来源的不确定性等。而服务的环境指的是现实世界，它是客观存在的，不受服务和需求变化的影响。

1.2 环境本体

为了统一服务提供者、服务请求者之间的术语，该文采用本体的方法。环境本体中的主要概念如下，其中部分概念的定义或含义可参见[10-11]中的内容。

定义1. 环境，记为Env，定义为二元组：

Env：=

其中，DomSet是建模环境中环境领域的集合，DomRelSet是领域之间关系的集合。

定义2. 环境领域，记为EnvDom，是DomSet的元素，定义为四元组：

EnvDom：=

其中，DomName表示环境中环境领域的名字，DomAtrrSet表示领域的属性集合，用以区分不同的领域，EntSet是此环境领域中环境实体的集合，EntRelSet表示环境实体之间关系的集合。

定义3. 环境领域关系，记为DomRel，是DomRelSet的元素，定义为三元组：

DomRel：=

其中，sdom， tdomDomSet， 表示DomSet中的任意两个领域，domrel表示领域之间的关系，它可以为：

-sdomtdom，表示tdom包含sdom，即ent （entsdom.EntSetenttdom.EntSet）entrel（entrel sdom.EntRelSetentreltdom.EntRelSet）；

-sdomtdom，表示sdom包含tdom，即tdom sdom；

-sdomtdom，表示sdom和tdom具有相同的环境实体，即ent（entsdom.EntSetenttdom. EntSet）；

-sdomtdom，表示sdom和tdom无关，即ent （entsdom.EntSetenttdom.EntSetenttdom.EntSetentsdom.EntSet）。

定义4. 环境实体记为EnvEnt，是EntSet的元素，定义为一个四元组：

EnvEnt：=

其中，EntName是环境实体的名字，它是唯一的。Type表示环境实体的类型，环境实体分为自主实体、符号实体和可控实体三类，分别取值为A、S和C。自主实体时可以接收或发送服务或其它环境实体传递的事件，但没有确定的状态变化和内容变化；符号实体可以接收或发送服务或其它环境实体传递的数据，接收数据会改变环境实体的内容；可控实体可以接收或发送服务或其它环境实体传递的消息（事件或数据），接收或发送消息能改变此环境实体的状态或内容。AttrSet={|attrn和attrv分别表示静态属性的属性名和属性值}是环境实体静态属性的集合，描述环境实体的性质，它们不受服务影响。Eff=Events| Datas|Trans，表示环境实体的效果，它描述环境实体在服务的作用或触发下发生的动态变化，它的取值取决于环境实体的类型，自主实体的Eff为Events={| dir=？|！， event为命令消息}；符号实体的Eff为Datas={|dir =？|！， data为数据消息}；可控实体的Eff取值为Trans={|ss和ts表示环境实体的状态，mes为数据消息或事件消息}。

定义5. 环境实体关系，是EntRelSet的元素，记为EntRel， 描述环境领域中环境实体之间的关系，定义为一个三元组：

EntRel：=

其中，sent， tentEntSet， 表示某个领域内任意两个环境实体，entrel表示环境之间的关系，可以分为：

-is-a关系，表示sent是tent的子类，具有tent的部分性质；

-part-of关系，表示sent是tent的元素；

-dependence关系，表示sent某种变化依赖tent通过服务发送或接收的消息；

-instance关系，表示sent是tent的实例；

-null关系，表示sent和tent无关。

1.3 环境模型的构建

环境建模是环境驱动服务组合的基础，它是以环境本体为基础构建某个领域的问题的模型。在建模中需要考虑领域问题、客户和服务三方面的因素。对于相互之间关联较弱的问题直接分为多个领域分别建模，对于关联较强的领域，其任务如下：

步骤1：确定问题的范围。从领域角度看，要求描述耦合较强的内容。从客户角度看，要描述客户需要解决的问题，要满足的需求范围要适中，描述范围过大会造成领域过于复杂，描述过小则不能单独满足客户需求。从服务角度看，要描述服务能解决的问题，描述服务不能解决的问题不仅无法组合，也会提高描述、组合等的复杂度。

步骤2：确定环境实体。从领域角度看，一要尽可能选择问题领域中概念作为实体；二要选择功能紧密的内容作为同一实体，把耦合较弱的或没有关联的分为不同的实体。从客户角度看，环境实体要与客户需求相适应。从服务角度看，环境实体要适当考虑服务提供的功能之间的耦合。

步骤3：确定环境实体的类型、属性和行为。静态属性用于选择实体，静态属性的选择和取值范围的确定反映了实体性质和提供服务的范围。Eff描述环境实体的变化，其范围确定了可以对这个环境实体施加的功能，行为的粒度确定了服务描述和客户选择的粒度，描述粒度过小会提高描述或推理的复杂度，描述粒度过大或功能单位不一致会造成一些功能无法描述。类型反映领域对环境实体不同变化之间的约束，如变化依赖于实体状态则为可控实体。

步骤4：划分子领域。如果领域内存在不一致，或者领域的复杂度超过了期望的程度则要分解领域。不一致包括环境实体具有不同类型特征，环境实体的行为需要以不同粒度描述或者相同条件下可能发生多个不同的变化等。领域复杂度的要求则取决于具体的描述语言和推理工具以及客户的要求等内容。

以网上购物领域为例，其主要环境实体和实体之间的关系如图2（a）所示，具体行为的描述如图2（b）所示，（b）中虚线代表其它没有描述的变化。其中，确定问题范围是确定要处理的内容，如以买家为客户，是否处理卖家信息取决于购物者除了关心产品的内容外是否关心商家的规模或地址等内容。确定环境实体是确定环境不同变化之间的关系，不一定与现实实体完全对应，如当支持购物、彩票等具有不同行为买家时，可作为多个环境实体。确定环境实体的静态属性是确定服务可能改变的领域实体，比如支持信誉度为什么范围的买家；确定环境实体的动态属性是确定客户可以接收的服务或服务可以提供的服务范围，比如买家是否能够先收货再付款。划分领域是确定可以自动推理的问题范围，涉及多个领域时一般需要人工介入。

1.4 服务描述和需求描述

基于环境描述服务和需求是环境模型驱动服务组合的前提，可以预先进行。服务基于环境的描述定义如下：

Ser：=

其中，ID是服务的标识，DomSet是服务作用的领域集合，是环境领域集合的子集，SerSet表示此服务成员服务的集合，服务为原子服务时是服务自身，FuncSet描述环境实体的变化和服务之间的关系。需求描述是一个没有SerSet和FuncSet部分的服务描述，描述需求时，ID是需求的标识，DomSet是客户期望改变的领域集合。

基于环境本体的服务描述和需求描述是一种投影。服务描述过程中，服务信息、环境模型和相关信息的充分性和形式化程度决定了描述的自动化程度。服务信息包括服务可作用的领域、可作用的实体、与实体间的交互及自身的变化特征等信息。描述可能遇到如下问题：一是服务提供了领域模型之外的功能，这时只描述服务在此领域内提供的且独立于其它功能的功能；二是服务提供的功能依赖于领域外的环境实体，则要求服务可以独立获取这些资源；三是服务提供功能的粒度与环境描述的粒度不一致，在服务提供的功能粒度大于环境模型粒度时按服务提供的功能描述，在服务功能粒度小于环境模型粒度时则根据环境模型描述，在服务功能与环境模型行为之间不存在可对齐的划分时，则无法描述。由于服务描述中各个领域是分别描述的，描述过程与单领域的服务描述一样，可参见[11]中的描述方法。

需求描述与服务描述的主要区别在于需求可能涉及多个领域。当需求属于单一领域时，可以采用与描述服务相似的方法描述需求，选择所需的环境实体、指定环境实体的性质变化以及推导环境实体的变化过程和依赖关系，具体内容可参见[12]；当需求描述涉及多个相互之间无关的领域时，则分为多个领域分别描述；当需求涉及多个相关的领域时，则需要客户、领域专家的介入，以处理不同领域之间的冲突，以获得一个一致的需求描述。

除了需求涉及多个相关领域时需要有领域专家或客户参与外，其它情况下服务组合问题都在单个领域内，新服务和新需求的出现不会改变问题的内容。描述的结果是领域模型的裁剪，如一个基于图2（b）的具体的买家服务描述如图2（c）所示。

2 组合方法

该文假设服务在其所有可以提供功能的领域具有描述，而且服务的不同作用效果之间是独立的。利用环境模型中的知识，采用分解发现的方法来组合服务。

2.1 需求的分解

基于环境本体描述的需求中，不同子需求之间的依赖类型有：

-领域依赖，两个子需求之间存在领域依赖当且仅当两个子需求属于同一个领域，即|req1.DomSet|=1 req1.DomSet= req2. DomSet；

-消息依赖，两个子需求之间存在消息依赖当且仅当一个子需求的满足需要另一个子需求的消息，即mes（mesreq1mesreq2 req1.mes.dirreq2.mes.dir）；

-实体依赖，两个子需求之间存在实体依赖当且仅当两个子需求是关于同一个环境实体的，即req1.DomSet=req2.DomSet|req1.EntSet|=1req1.EntSet = req2.EntSet；

-状态依赖，两个子需求之间存在状态依赖当且仅当两个子需求是关于同一个可控实体的，即req1.DomSet=req2.DomSet|req1.EntSet|=1req1.EntSet=req2.EntSetent（ent req1ent.Type =C）；

不同依赖之间的耦合程度不同。存在领域依赖仅表示需求属于同一个领域；存在消息依赖表示要满足一个需求需要满足另一个需求的过程中发送的消息；存在实体依赖的两个需求则需要改变同一个环境实体，在需要实体消息的同时还有资源上的约束；存在状态依赖时，在以上约束的同时还具有时间上执行次序的约束。以网上购物领域为例，存在领域依赖时，买家张三和支付者工商银行属于同一个领域，但张三不一定通过工商银行支付；存在消息依赖时，张三要通过工商银行支付，但可能涉及多家工商银行，如何转账没有限制；存在实体依赖时，张三的账户只能张三操作；存在状态依赖时，张三只能先存钱再取钱。

据此设计了表1中需求分解规则。其中，规则1根据领域划分需求，把不同领域的需求作为不同的子需求。规则2-5根据需求之间的消息依赖划分需求，规则2划分的是不存在消息依赖的需求；规则3划分的是存在单向消息依赖的需求；规则4划分的是与符号实体或自主实体存在消息依赖的需求；规则5划分的是存在多个环境实体的需求。规则6划分的是包含单个符号实体或自主实体的需求。规则7划分的是含有单个可控实体的需求。划分方法的实现可参见[12]，规则1、规则5和规则6具有线性时间复杂度，其它规则是多项式时间复杂度。

2.2 基于分解的组合

基于环境的描述不仅提供了面向问题的描述，而且可以更加具体地描述服务的非功能属性和客户对各部分问题非功能属性的要求，同时可以支持基于行为的服务发现。其组合过程如算法1所示，分析可知当发现算法的复杂度不超过多项式时间复杂度时，组合算法具有多项式时间复杂度。

算法1： 基于分解的组合算法

输入：req， serviceSet

输出：comSer//组合服务

步骤：

1.if（|req.DomSet|>1）//需求包含多个领域

2. 根据规则1划分需求把各个子需求加入reqSet；

3.else

4. reqSet：={req}；

5.endif

6.while（|reqSet|>0）

7.从reqSet中取一个元素subreq， reqSet=reqSet-{subreq}；

8.ser=discovery（subreq， serviceSet）；

9.if（ser）//发现成功

10.comSer.SerSet：= comSer.SerSet{ser}；

11.comSer，FuncSet= comSer，FuncSet{}；

12.else

13.if（没有规则可以分解subreq）//组合失败

14.return fail；

15.endif

16.根据规则分解需求并把分解结果加入reqSet；

17.endif

18.endwhile

3 实验分析

为实现本文组合方法，基于eclipse平台下开发了对应的组合原型系统。

3.1 实现原型

原型分为应用层、功能层和数据层三个层次。应用层提供了描述需求和组合服务的面板，需求描述过程中支持对环境实体、消息和状态的选择，组合时支持对分解规则以及[12]中转换规则的选择，分别如图3和图4所示。功能层实现描述和组合的推理，可以在客户指定需求下推理可行的实现过程。数据层存放复合环境本体规范的服务描述和各个领域的环境模型。

3.2 组合方法评价分析

为了验证该文方法的实际性能，在所开发平台上进行了性能验证。在服务数从10到110，需求行为数从100到300，没有优化发现算法的情况下（可选服务没有进行索引或排序），进行了多次服务组合，所耗费的平均组合时间如图5所示。从中可以看出，与2n的指数趋势线比，该文方法受服务数的影响较小；组合复杂度随服务数的增加而增加，需求1、需求2和需求3都是上升趋势；组合复杂度随需求行为数的增加而增加，需求3的组合时间大于需求1的组合时间；实验还显示，服务粒度和服务选择次序对组合效率都有影响，当有大粒度服务匹配时，需求行为数的增加不一定导致组合时间的增加，如在服务数是20时，需求3的时间少于需求1的时间；而当采取选取第一个满足子需求服务的发现策略时，选取合适的发现次序能减少组合时间。

3.3 组合方法对比

已有的很多服务组合方法是基于某种假设，但没有讨论实现其假设的方法，只能适用于特定的环境，如 [5]中的Roman模型假设存在一个定义了原子行为的社区，[3]假设存在能分解需求的复合服务或简单服务。在区分描述内容的方法中，[6]是一种开放的多层组合模型，并引入中介作为不同层次、不同内容之间转换的机制，但没有具体的中介实现方法，其复杂度也很难控制。[13]也是基于服务的行为，但建模对象是服务与外部实体的交互信息及其次序；其复杂度依赖于服务间交互的机制，当允许无限消息队列时，它是图灵完全的。[14]侧重于对服务语境信息的处理，其语境该概念的含义与[8]中环境相似，并用不同类型的Agent来处理各类语境信息。在支持行为服务或复合服务的组合方法中，[5，13，15]都是具有指数级或以上的服务度。与前面基于环境的组合方法[16，17]相比，该文更侧重于对环境模型的构建和环境中知识的使用，[16]中方法没有考虑环境的建模，环境仅提供了描述服务语义的统一术语；[17]中服务描述是基于单个领域内的环境模型，但其采用的是一种通用的与[5]中类似的行为组合方法，具有与其相同的指数时间复杂度；[12]则没有考虑多领域需求的服务组合以及环境建模的问题。该文方法是在已有单个领域组合方法的基础上，不仅利用了环境模型的知识以支持高效的组合，而且通过扩充了环境本体的概念，可以支持复杂问题或多个领域问题的组合。

4 总结

环境模型驱动的方法为组合服务提供了一种新的思路，有助于解决服务组合的开放性和动态性和提高组合的效率。前一个问题的解决在于它是以形式化的问题模型为基础，采用了与其它方法不同的描述方式，对一个具体的问题领域，仅描述服务对问题领域的作用效果，使得服务描述不仅不受服务实现方式变化的影响，还不受服务其它方面功能的影响，同时对客户的也具有相同的效果。对效率的提高在于环境模型引入的新知识和对知识的利用，知识的引入不仅限定了服务作用的范围，还限定了不同服务之间的关系，而且分解是降低问题复杂度的有效方法，基于知识的分解不仅可以简化问题，而且限定了组合的位置。

不过，该文方法的有效程度取决于环境模型的性质，如环境模型覆盖问题越多，可以解决的问题越多，环境模型中知识的针对性越强，组合效率越高；但是在覆盖问题范围和效率之间存在矛盾，问题范围过大会增加组合效率。为了进一步改善组合的性能，需要研究如何利用领域特征、如何确定利用的内容和如何选择协作的领域等内容。

参考文献：

[1] Milanovic N.， Malek M. Current Solutions for Web Service Composition[J]. IEEE Internet Computing， 2004， 8（6）：51-59.

[2] W3C. 2009. OWL 2 Web Ontology Language Document Overview[S]. http：//www.w3.org/TR/owl2-overview/.

[3] Sirin E.， Parsia B.， Wu D.， Hendler J.， Nau D. HTN Planning for Web Service Composition using SHOP2[J]. Journal of Web Semantics， 2004， 1（4）： 377-396.

[4] McIlraith S.， Son T.C. Adapting Golog for Composition of Semantic Web Services[C].//Proceedings of the 8th International Conference on Knowledge Representation and Reasoning， Toulouse， France， 2002： 482-496.

[5] Berardi D.， Calvanese D.， Giacomo G.D.， et al. Automatic Composition of Eservices that Export Their Behavior[C].// Proceedings of the 8st International conference on ICSOC 2003. LNCS 2910. Heidelberg： Springer-Verlag， 2003： 43-58.

[6] Roman D.， Scicluna J.， Feier C.， et al. Ontology-based Choreography and Orchestration of WSMO Services[S]. WSMO Final Draft， http：//www.wsmo.org/TR/d14/ v0.4/， 2005.

[7] Jackson M. Problem Frames： Analyzing and Structuring Software Development Problems[M]. Addison-Wesley， 2001.

[8] lv J.， Ma X.， Tao X.， Cao C.， et al. On environment-driven software model for Internetware[J]. Science in China Series F： Information Sciences， 2008， 51（6）： 638-721.

[9] Jian Yang. Web Service Componentization[J]. Communications of the ACM， 46（10）： 35-40， 2003.

[10] Wang P.， Jin Z.， Liu L.， Cai G. Building Towards Capability Specifications of Web Services Based on an Environment Ontology[J]. IEEE Transactions on Knowledge and Data Engineering， 2008， 20（4）： 547-561.

[11] 蔡广军， 金芝. 基于环境本体的Web服务投影描述方法[J]. 计算机科学， 2009， 36（8）： 116-120.

Cai G.， Jin Z. Based on Environment Ontology Web Service Description： a Projection Approach. Computer Science， 2009， 36（8）： 116-120.

[12] Cai G. Requirement Driven Service Composition： An Ontology-Based Approach[C].// Proceedings of 6th International Conference on Intelligent Information Processing. Springer， 2010： 16-25.

[13] Bultan T.， Fu X.， Hull R.， Su J. Conversation Specification： A New Approach to Design and Analysis of E-Service Composition[C].//Proceedings of the 12th international conference on World Wide Web， 2003： 403-410.

[14] Maamar Z.， Mostefaoui S.K.， Yahyaoui H. Toward an Agent-Based and Context-Oriented Approach for Web Services Composition[J]. IEEE Transactions on Knowledge and Data Engineering， 2005， 17（5）： 686-697.

[15] Brogi A.， Corfini S.， Popescu R. Semantics-Based Composition-Oriented Discovery of Web Services[J]. ACM Transactions on Internet Technology， 2008， 8（4）：1-39.

[16] 侯丽珊， 金芝. 基于环境变迁的构件组合模型[J]. 电子学报， 2005， 33（12A）： 82-87.

Hou L.， Jin Z. A Composition Model of Internet Components Based on Environment Transitions. ACTA Electronica Sinica， 2005， 33（12A）： 82-87.

[17] Wang P.， Jin Z. Web Service Composition： An Approach Using Effect-Based Reasoning[C].// Proceedings of the ICSOC 2006. LNCS 4652， Heidelberg： Springer-Verlag， 2007. 62-73.