第4卷第6期 智能系统学报 Vol.4 No.6 2009年12月 CAAI Transactions on Intelligent Systems Dec.2009 doi:10.3969/j.issn.16734785.2009.06.004 语义Web服务组合中的服务建模及规划算法 万长林12，陈立民12，王竹晓12，王文杰2，史忠植 (1.中国科学院计算技术研究所智能信息处理重点实验室，北京100190：2.中国科学院研究生院，北京100049) 摘要：Wb服务的语义建模是指对Wb服务的属性、功能和结构等进行语义描述，使用户能够对服务自动地定位、 选择、使用和组合.本文以动作理论和描述逻辑为基础对服务的逻辑层信息（控制流和数据流）进行语义建模，用带 前提和结果的原子动作描述简单服务，复杂动作描述组合服务的控制流，服务间的依赖关系描述数据流，并提出一 个基本的Wb服务自动组合框架.在该框架中，Wb服务自动组合被划分为逻辑层和实现层2部分，于是服务的自 动组合问题在逻辑上归结为一个动作规划问题，在实现上归结为一个根据动作选择具体服务的服务选择问题.最后 给出一种新的自动组合规划算法，该算法充分考虑了语义推理和智能规划的结合，在对问题的描述能力和运行效率 上做了较好的平衡. 关键词：语义Wb;动态描述逻辑；自动服务组合 中图分类号：TP393文献标识码：A文章编号：16734785(2009)060490-07 Semantic model and planning algorithm for Web service composition WAN Chang-lin'2,CHEN Li-min'2,WANG Zhu-xiao2,WANG Wen-jie2,SHI Zhong-zhi' (1.Key Laboratory of Intelligent Information Processing,Institute of Computing Technology,CAS,Beijing 100190,China;2.Gradu- ate University of Chinese Academy of Sciences,Beijing 100049,China) Abstract:This paper proposed a semantic model for Web service based on dynamic description logic (DDL), mainly concern about the logic/functional facets.In this model,a simple service was modelled as an atomic action with some preconditions and effects.The control flows of composite service were modelled by using complicated ac- tion,and the data flows were modelled as dependent relationship between atomic actions.A basic framework for au- tomated Web service composition was introduced.In this framework,service composition was divided into two sta- ges:logic planning stage and grounding stage.Therefore,a service composition problem was reduced to an action planning problem at planning stage and a service selection problem at grounding stage.At last,a new planning al- gorithm for automated composition was proposed.The algorithm achieves good balance between DDL reasoning and AI planning. Keywords:semantic Web;dynamic description logic;onogy;automated service composition 万维网(Wb)正从最初的一个单纯提供文本和用户和其他应用程序提供服务2].服务组合是S0A 图像的容器向提供服务发展.Wb服务被定义为 的重要特征，即将多个基本服务组合成一个新的复 能够在万维网上被发布、定位和调用的自包含、自描 杂服务来提供单个基本服务所不具备的聚合的功 述的模块化应用程序.W©b面向服务计算体系结构 能.早期的服务组合多为手工方式，服务提供者在设 (SOA)是一种设计软件系统的合理方法，它在网络 计服务的商务逻辑的同时选择具体的组件服务.但 中发布可被发现的接口，通过这些接口同时为最终 随着服务提供商(WSP)和服务数量持续增长，以及 服务运行环境的动态性，服务组合的自动化变得极 收稿日期：一 基金项目：国家自然科学基金资助项目(60775035,60970088)；国家 为关键，当前对自动服务组合的研究大概可归于两 “863"计划资助项目(2007AA01Z132):国家“973”计划资 助项目(2003CB317004,2007CB311004);国家科技支撑计 大类.一类基于工作流组合，代表性工作是BEA系 划资助项目(2006BAC08B06);中国科学院研究生院院长 统公司、BM公司和微软公司等提出的 基金资助项目(085101JM03). 通信作者：万长林.E-mail:wancl@ics.ict.ac.cm. BPEL4WSI3].BPEL4WS是一种Wb组合服务的工
第6期 万长林，等：语义Wb服务组合中的服务建模及规划算法 ·491· 业标准，它提供了一种对业务流程和交互协议正式 个Web服务提供商提供具有相似功能的Web服 规范的语言.另一类基于智能规划，代表性工作是斯 务，不同的Wb服务提供商提供的逻辑上功能相同 坦福大学、马里兰大学和卡内基梅隆大学等机构提 的服务可能输入/输出接口不兼容或者服务质量不 出的OWL-S4.OWL-S采用基于描述逻辑的0WL 同.本文对Wb服务的建模将逻辑功能和具体实现 语言对Wb服务的属性、功能和结构进行形式化描 区分开来，即用动态描述逻辑中的一个动作来描述 述使其可被计算机理解.通过将Wb服务描述与 具有相同逻辑功能的一类Wb服务，而不是对每个 PDDLIS)之间的转换来将Wb服务组合问题转化为 Wb服务都描述其前提、结果、输入和输出等信息. 智能规划问题，于是就可以利用现有的多种规划器 对于任一原子Wb服务，通过为其关联一个原子动 来实现Web服务组合.比如，Schuster6]等人提出多 作来进行语义建模.动态描述逻辑DDL中的原子动 态过程模型PPM将服务模式化为状态机来描述服 作可定义如下： 务的可能状态及状态间的转换，就可以通过状态机 a(x1,…,xn)=(P,E). (1) 的推理来实现.Keller等将Web服务的可实现性 式中：4为原子动作名；P和E分别为动作的前提条 以及包含关系归结为谓词演算的定理证明问题 件和执行结果，它们都用DDL中的公式(Formula) Narayanan等「8]用Petri网模拟原子组件的复合过 表示；x,…,x。为在P和E中出现的所有个体名 程，将服务组合归结为Petri网的可达性问题.Mcil- (也可称之为动作定义式中的变量).DDL中的公 raih等I9]利用Golog刻画复合过程，应用现有Golog 式由如下产生式定义： 的规划算法和工具解决服务的组合问题.但以上这 p,业：=C(u)IR(u,)|=vT(w,e)1pl 些方法都没有考虑领域本体在规划中的作用.S pVψl<T>p. (2) reno]认为层次任务网HTN规划中的任务分解和 式中：p、业为公式名，u、v为个体名，e为有型域的个 OWL-S中的过程分解十分相似，将OWL-S与HTN 体名，C为概念名，R为抽象角色，T为有型角色，T 结合来解决服务组合问题，该方法在先验知识足够 为动作.且形如R(u,v),R(u,),T(u,v), 的条件下效率很高，但在实际应用中往往缺乏必要 一T(4,),C(u),C(u)的公式被称为简单公式 的先验知识.Gu等结合情景演算和描述逻辑来 primitive formula). 解决服务组合问题，具有很强的描述能力且避免了 下面以OWLS联盟基于OWL-S1.2的图书购 对先验知识的依赖，但该方法的计算复杂度较高.为 买原子服务ExpressCongoBuy为例说明上述的原子 提高效率，Hoffman等12]用简化的本体形式化语言 服务语义建模方法.对ExpressCongoBuy服务，将其 刻画服务及状态，然后用前向规划方法解决服务组 关联到一个原子动作ExpressBuyBook,该原子动作 合问题 可简单描述如下： 本文首先从服务描述的层面，提出了基于动态描 define atomic action ExpressBuyBook 述逻辑DDL的Wb服务模型，动态描述逻辑 variables:ECB_BookISBN,ECB_SignInInfo, DDLB4将动作理论和描述逻辑有机地结合在一起， ECB CreditCardNumber,ECB Ac- 即能描述静态知识，也能描述动态知识，是描述逻辑的 ctID,ECB_CreditCard,ECB_Output 一种动态扩展.基于该Wb服务模型研究了基于动态 preconditions:hasAcctID(ECB_SignInInfo,ECB_ 描述逻辑的语义W©b服务自动组合，重点是基于DDL AcctID)&validity ECB_Credit- 推理算法的Wb服务组合规划算法. Card,Valid )creditNumber 1 语义Web服务建模 (ECB_CreditCard,ECB_Credit- CardNumber)&InStockBook(ECB 1.1原子Web服务建模 _Book)hasISBN ECB_Book, 在OWL-S中Wb服务的功能、输入输出等信 ECB BookISBN) 息的语义描述是通过在OWL-S本体的ServiceProfile effects:type ECB_Output,OrderShippedAc- 概念中hasPrecondition、hasResult、hasInput和ha- knowledgement)&shipment(ECB_Ship- sOutput等属性来实现的，在对Web服务语义建模 ment)&shippedTo (ECB_Shipment, 时每个具体的服务都需要为其指定包括前提、结果 ECB_AcctID)&shippedBook ECB_ 输入和输出等的语义描述.因为互联网上通常有多 Shipment,ECB_Book)
·492 智能系统学报 第4卷 1.2组合Wb服务建模 础上引人了6个控制流(Sequence、Switch、Repeat-- 组合Web服务是多个Web服务的聚集，如将 While、Repeat-Until、Fow和Pick)的宏定义： 其类比于工作流，组合服务中成员服务触发的控制 Sequence({s1,…,sn}):=s1;…;sn, 逻辑即为组合服务的控制流，成员服务之间的数据 Switch({p1,…,pn}),（{s1,…,sn})= (消息)传递即为组合服务的数据流。 (p1?sn)U…U(pn?;sn）, 1.2.1控制流语义建模 Repeat--While(p,s）:=(p?s)*;(p）?, BPEL4WS和OWL-S采用特定的结构化的构造 Repeat-Until(,s):=s;(()?;s)*,,(4) 子（活动）来描述一组基本服务执行的顺序，这些构 Pikc({s1,…,sn})=sU…Usn, 造子说明了组合服务是如何通过将基本服务组合在 Flow({s1,…,8n}):=s1∩…∩5n 一起而创建得来的.用动态描述逻辑中的复杂动作 式中：s,1,…,5n为构成复杂动作的成员动作，p, 对服务进行语义建模，通过描述逻辑中的动作构造 p1,…,P.为条件式，ow的构造符“∩”为本文在 子，由基本服务逐步构造成复杂服务，即通过DDL DDL(SHON(D))中引入的动作构造子，表示n个 中的动作构造符“？”、“；”、“U”以及“*”由原子动 动作s1,…,sn可以同时发生，它等同0WLS中的 作逐步构造成复杂动作.DDL中的动作由如下产生 Split+Join,而忽略不检查并发结果导致不确定逻辑 式生成： 结果的Split控制流.本文不在DDL中为Any-Order T,T'→a(1,…,xn) 引入宏定义是因为Any-Order的语义是它的成员服 p?1πUr'|T;π'|π*. (3) 务.可以以任意顺序执行，也就是说，如果一个Ay 式中：a(x1,…,xn)是原子动作，”是一个公式形如 Order成立，那么任意指定的一个有同样成员服务的 p?,πU',T;'以及T·的动作分别为测试(test)、选 Sequence控制流也成立，且具有相同的逻辑结果.最 择(choice)、顺序(sequence)及迭代(iteration)动作. 后，If-Then-Else控制流是Switch控制流的一种特 表1列出了BPEL4WS、OWL-S和DDL的控制 例，它们可以简单地等价替换.基于上述DDL复杂 流，并显示了它们之间的对应关系（其中π；'为服 动作宏定义的服务可以被定义如下： 务定义式，”为条件式) stI Sequence(S)I Switch(S)I Pick(S)I Flow(S)I, 表1BPEL4WS、OWL-S和DDL控制流的简单比较 Repeat-While(,s)I Repeat-Until(,s).(5) Table 1 A brief comparison of control-flows in 式中：s是服务的名称，t表示基本服务，Sequence、 BPELAWS,OWL-S and DDL Repeat--While、Repeat--Until、Switch、Pick和Flow是控 BPELAWS OWLS DDL 制流的名称，S表示一组服务，称为s的“成员服 (Structured Activity）(Control Construct)） (Action Construct) 务”，亚表示一组条件式 Sequence Sequence T;π 1.2.2数据流语义建模 Any-Order (m;π)U(π；x) 除了控制结构，OWL-S使用绑定类来描述进程 Switch If-Then-Else (e？;T)U((7p)?;r) 之间的数据流.绑定被描述为使用其他进程数据的 While Repeat-While (?;T)*;(p)? 过程，并使这种过程及数据来源的具体参数明确化， Repeat-Until T;(7g?;)*;(p)? BPEL4WS通过对活动之间的交互状态建模来处理 数据流.交互状态由接收和发送的消息及其他的相 Pick Choice TUT 关数据组成.但是，OWL-S和BPEL4WS都不对复杂 Flow Split 的数据流进行显式声明，而复杂数据流是包含复杂 Split Join 控制流的组合服务必然将会导致的结果.以图1所 由表1可以看出BPEL4WS和OWL-S中的控制 示的一个简单场景为例. 流除了Flow、Split和Split+Join都可以在DDL中 如图1所示，任务PayRental的输入是任务Car 找到等价描述.相对于BPEL4WS和OWL-S侧重对 Rental或BikeRental的输出.尽管BPEL4WS和 组合服务中基本服务执行顺序的描述，DDL侧重于 OWL-S可以显式声明CarRental和PayRental的数据 对基本服务的动态内涵刻画，以及组合服务内部组 流以及BikeRental和PayRental之间的数据流，但它 合的逻辑关系的描述.对组合服务控制流的语义建 们没有给出声明2个数据流之间的可选关系的方法。 模综合表1所述，控制流做适当取舍，在DDL的基 为解决该问题，在数据流的声明引入AND,OR2个结
第6期 万长林，等：语义Wb服务组合中的服务建模及规划算法 ·493· 构进行扩展.考虑一个包含n个基本服务任务的组合 需的概念和概念之间的关联，如图2所示。 服务s,可以定义服务s的数据流如下所示： f→(t:,〉IAND(F)IOR(F). (6) 式中：1≤iJ≤n∫是数据流的名称，：和专是基本服 carrental 务任务的名称，F表示一组数据流.一个元组〈(， 〉，或简记为f,表示一个从起点服务任务到目 Carrental OR BikeRental 标服务任务专的简单数据流.AND、OR是2个用来 定义复杂数据流的结构.例如，AND({f,f})表示 服务任务应具有从6：和2个服务任务的输入数 PayRental 据流；OR({fkf})表示服务应具有从服务任务 或专的输入数据流。 1.3Web服务动作建模本体 根据以上服务建模的定义，提出了一个基于动态 图1一个含有可选数据流依赖关系的组合服务 描述逻辑的语义Wb服务动作建模本体WSAMO Fig.1 A composite service including optional data-flow de- (Web service action modeling ontology).该本体包括 pendence relationship Wb服务的控制流定义、数据流定义和服务参与者所 Thing /is-a is-a is-a LogicLanguage Expression Agent is-a is-a is-a is-a is-a SWRL-Expression Condition DDL-Expression Server (Client) 7 is-a is-a is-a is-a is-a is-a is-a SWRL-Condition(DDL-Condition Formula) is-a is-a Precondition Effect Haspreconditipnnas Effect ①ataFlow (List) Action fristData-Plow To isa is-a is-a frist is-a ①ataFlowList is-a (AtomicAction) (ActionList ComplexAction components is-a components targetaction componcnts is-a componentsnents is-ais-a is-a ComplexDataFlow AtomicDataFlow FlowAction (PickAction SwitchAction SequenceAction (TterateAction) 1s-a Nis-a AndDataFlow OrDataFlow 图2Web服务建模本体概念和关联 Fig.2 The concepts and roles of Web service action modeling ontology (WSAMO) 2自动服务组合框架 逻辑上就等价于构造并判断若干原子动作组合成的 复杂动作在给定状态下是否成立.一个基本的自动 通过给基本的Wb服务添加前提和结果等语 服务组合框架由规划器(Planner)、匹配器(Matc- 义信息，可以将Wb服务在逻辑上等价于一个原子 her)、选择器(Selector)和部署器(Deployer)等部分 动作，而由基本服务自动组合成复杂服务的过程在 构成，如图3所示
494· 智能系统学报 第4卷 发布服务WSAMO 等符号对静态知识进行了结构化的描述；Aact和 知识库D D-(R.T.A.Act.CAct.A) Cact表示的关于动作的知识，其中Aact为原子动作 集合，Cact为根据前述控制流宏定义的复杂动作的 服务提供者 集合；A刻画的关于具体状态的知识，类似于情景演 匹配器 发布Qo Matcher 棉萄器 算中对情景的刻画.用户提交的初始输人信息为！= WSOO DDL推理机 DDL推理机心 DDLR DDLR (R',T,A')表达用户具有的静态知识和具体状态， 用户的目标状态表达为一个DDL公式goal.根据知 QoS数据库 服务选择 识库D和用户输入I及目标公式gol可建立规划域 、Selector P=(S。,Ac,goal),其中初始状态集S,=(RDR',T 服务部署 ⊕T,A⊕A)为2个静态知识库(R,T,A)和(R',T', Deployer A')的融合，动作集Ac=AAct U CAct..基于以上定 图3基于DDL的自动服务组合框架 义，自动服务组合规划算法可描述如图4. Fig.3 An automated service composition framework based Algorithm 1 ActionPlan(S,Acts,goal,plan on dynamic description logic (DDL) Input:the state S,the action list,Acts,the planning 图3中的Web服务用WSAMO本体描述其功 goal,and aplan that is a sequence action. Output:a plan that meets the goal,or an empty plan. 能性信息，并发布到DDL知识库中；匹配器负责在 1:create an empty plan list:plansi 2:for each action a e Acts do 知识库中查找匹配用户需求的动作；规划器负责由 3: create a new plan:new +-plan +a; 基本动作构造复杂动作，并由DDL推理机判断复杂 4: if IsPlanExecutable newp)then evaluate how close nep to the goalby using function 动作是否满足任务要求.如果复杂动作不可满足，则 Evaluate Plan(newp,S,goal)-d; if d=1.ie.newp meets the goal then 规划器继续尝试构造新的复杂动作，直至发现一个 returen newp 匹配用户需求的复杂动作.如果匹配器发现了匹配 8 else 9: insert newp into the plan is decrease order of evaluation 的动作，则由服务选择根据QoS数据集中的信息为 valure d; 10: end if 该动作指定具体服务，并供客户调用；如果规划器发 11:end if 12:end for 现了匹配的复杂动作，则由服务选择根据QS数据 13:if plan s is empty then 集中的信息为复杂动作中的原子动作指定具体服 14: returen NULL: 15:else 务，然后将复杂动作在工作流引擎上部署为工作流 16:for each new p e plans do 17: return Actionplan S,Acts,goal,new p) 服务供客户调用， 18:end for 19:end if 3自动服务组合规划算法 (a)算法l:自动服务组合规划算法ActionPlan Algorithm 2 EvaluatePlan(S,Acts,goal,plan) 本文的自动服务组合方法类似文献[12]，主要 Input:the state S,the planning goal goal,and a plan that is a sequence action 区别在于本文的服务建模具有更严格的逻辑基础和 Output:a numeric value between 0 and 1. 更强的描述能力，且更多地结合了智能规划中的优 1:mr←-1 2:rewrite formula goal to a disjunctive normal form formula 化技术以提高算法效率，包括：1)通过将自动服务 G=Vt1(Ao=p）i 3:count←-0； 组合划分为逻辑和实现2层，避免了规划过程中对 4:for each clause C =Ado 类似服务重复考虑的问题；2)在规划过程中定义了 5: for each primitive formulaCdo 6 formula+Conj(S)A plan>; 启发函数提高搜索效率.本文的自动服务组合方法 if formula is satisfiable then 8 count +count +1 i 首先将用户提交的需求和已有知识转化成一个智能 9 end if 10: 规划问题域，通过解决这个逻辑上的规划问题得到 end for 11 if max count/m then 一个满足用户需求的动作序列，然后从各个动作关 12 max←一count/m； 13: end if 联的服务中选取合适的服务，组成一个实际可执行 14 if max 1 then 15: 的组合服务[516，比自动组合规划算法就是解决在 return 1; 16:end if 规划域中发现满足要求的动作序列的问题.该算法 17:end for 18:return max 的核心是一个启发式搜索算法，启发规则为候选动 (b)算法2：组合评估算法EvaluatePlan 作序列目标.已知一个DDL知识库D=(R,T,Aa, 图4自动服务组合规划算法 Fig.4 The planning algorithm for DDL based automated service C,A),其中R和T通过角色构造符、概念构造符 composition