基于web服务本体的服务组合系统建模与验证

基于web服务本体的服务组合系统建模与验证

0web服务组合近年来，服务计算（套接字，套接字，套）作为一种分布异构环境，实现了不同组织的应用整合，成为学术界和工业界的研究和开发热点。SOC倡导以Web服务及其组合为基础构造应用的开发模式,其核心是研究如何组合已有的、自治的Web服务,高效灵活地构筑企业级服务集成。目前已经开发了各种组合标准和语言,如Web服务业务流程执行语言(BusinessProcessExecutionLanguageForWebService,BPEL4WS)、Web服务编排描述语言(WebServicesChoreographyDescriptionLanguage,WS-CDL)、Web服务本体描述语言(WebOntologyLanguageforService,OWL-S)等,为Web服务组合提供了手工或自动的解决方案。然而,不管采用何种方式组合服务,这些标准只提供了描述规范,没有提供任何验证机制或工具支持来检验组合的有效性。实践应用表明,服务组合通常是一个复杂而易错的过程,如果执行一个错误的组合流程而没有预先对其进行验证,则部署该流程将导致运行期异常,而且往往需要花费很大的代价才能修复。例如,如果在组合中存在死锁,则执行该组合将导致服务间无限的等待,浪费大量共享和有限的网络资源。为解决上述问题,本文提出一种基于有色Petri网(ColoredPetrinets,CP-nets)的分析和验证机制,以提高Web服务组合的可靠性。另外,鉴于目前的语义趋势,即机器可理解的Web内容正在取代人类可识别的Web内容,为各种智能技术的应用提供方便,研究工作以OWL-S为基础,因为它提供了更富有语义的描述,为服务组合的自动化提供了可能。目前,已有一些相关研究使用Petri网及其扩展形式对服务组合进行形式化分析和验证。文献提出了一个基于Petri网的服务组合模型,采用代数元模型描述服务控制流,并建立了从代数元模型向Petri网的关系映射,从而为服务组合过程中的属性验证,以及执行的检测和优化提供了一种形式化工具。文献使用DARPA服务代理标记语言(DARPAAgentMarkupLanguageforService,DAML-S)本体描述Web服务能力,并按照一阶逻辑语言定义了DAML-S的一个相关子集。其组合和验证的基本方法是首先将DAML-S模型映射到情境演算,然后再映射到Petri网。文献基于对象Petri网(PetriNetswithObjects,PNO)组合Web服务,将每个Web服务映射为一个PNO系统,不同的网系统可以通过消息传递机制整合到一起,形成组合服务及控制流。文献使用可扩展标记语言(eXtensibleMarkupLanguage,XML)网建模业务流程间的协作关系,并提取其中的业务流程执行语言(BusinessProcessExecutiveLanguage,BPEL)元素。文献使用CP-nets对基于BPEL4WS的服务组合系统进行验证。本文试图利用CP-nets对根据语义信息自动生成的服务组合进行建模和分析验证。与上述基于Petri网及其他高级形式的研究方法相比,CP-nets结合了一般Petri网的过程互操作特性和高级程序语言的数据类型定义及数据处理的能力,具有更强大的表达力,同时使用有色令牌建模组合流程不同的输入输出信息更自然。文献的研究也是基于CP-nets的,但它使用BPEL4WS作为组合标准,该标准只是一种语法格式,不能表达信息的语义,因此其验证技术也只能局限于检测设计期组合错误。而本文采用的OWL-S通过本体语言对Web服务进行语义标注,从而提供了自动组合的可能性。因此,本文提出的验证方法既适用于设计期组合服务的情况,又适用于运行期组合服务的情况。而后者对目前服务组合的自动化趋势更有意义。1相关技术的总结1.1判断服务的过程作为判断流程的依据OWL-S是一种用来描述Web服务属性和功能的本体规范,采用明确的、计算机可以理解的语言标识来描述Web服务,试图利用语义描述和逻辑推理最终实现服务匹配、组合和执行的自动化和智能化。在OWL-S中,描述服务的基本信息主要有ServiceProfile,ServiceModel和ServiceGrounding三类本体。ServiceProfile描述服务做什么,指明服务的功能与接口,以便于服务代理能够搜索与匹配该服务;ServiceModel描述服务如何工作,指明当服务被调用时的操作,以便于服务代理进一步完成匹配、服务组合和服务的协调工作并监控服务;ServiceGrounding提供访问服务的具体细节,如通信协议、调用端口等。OWL-S把每个服务看成是一个过程(Process),并定义了ServiceModel的一个子类ProcessModel。Process模型中有原子过程、简单过程和复合过程三种。原子过程可以直接调用,没有子过程。从服务请求者的角度来看,一步就可以完成。它们接收一个输入消息,执行,然后返回一个输出消息。服务的执行对服务请求者来说是透明的。简单过程是不可调用的,也没有对应的Grounding,但是它们和原子过程一样,被认为只有一个执行步骤。简单过程一般用于抽象,可以用来提供原子过程的视图或复合过程的简化表示。复合过程可以由其他的原子或通过一些ControlConstruct组合而成。ControlConstruct的集合包括Sequence,Split,Split-Join,Any-Order,Choice,If-Then-Else,Iterate,Repeat-While和Repeat-Until。另外,OWL-S使用IOPRs(Inputs,Outputs,Preconditions,andResults)来描述每个过程的能力。1.2cp-工业模式的优势CP-nets作为Petri网的一种扩展形式,不同于一般Petri网仅有一种令牌(token),并通过一个整数来描述库所的状态,CP-nets的每个令牌被附加上一个称为颜色(color)的数据值。对给定库所,所有令牌必须拥有同属于某一特定类型(type)的颜色,所有这些类型构成库所的颜色集。与传统Petri网相比,CP-nets在系统建模分析上有几个明显优势:①可以对系统模型进行折叠,避免系统模型规模过大或不可控制的现象出现;②模型具有一定的稳定性,模型部件的通用性和可重用性大大提高,原型系统的微小变化不会导致模型大的更改,相似系统的建模仅需要进行简单的调整,使得对系统的建模变得更为简单;③CP-nets中提供了层次概念,对系统的建模过程可以采用自顶向下或自底向上的方式来进行,使得对系统的建模更为标准化和规范化。上述应用优势使得CP-nets特别适用于大规模工业应用领域信息系统,如Web服务这样的分布式软件系统,因此本文将CP-nets理论用于服务组合。2简化组合流程从本质上看,组合Web服务的行为可以看作是运算的一个偏序集。而采用CP-nets来建模数据流,规范控制流的操作语义,将简化组合流程的表示,使其变得更加直观。本节使用图形化的CP-nets建模是基于OWL-S定义的服务组合流程,首先通过服务组合代数来定义组合运算的基本规则,在此基础上,根据OWL-S组合要素的相关语义,给出了其对应的CP-nets的形式化描述。2.1s在单运算符的组合下仍然封闭两个或多个Web服务组合在一起生成一个新的增值Web服务的组合方式可被视作服务之间的代数运算,典型的运算符如顺序、选择、并发、迭代、条件和任意次序等是描述控制流的基础。形式上,Web服务组合代数可按照以下语法定义:WS∷=WS⨂WS|WS♁WS|WS||WS|αWS|WS∶WS|WS■WS。其中,WS表示原子服务或基本服务;⨂是顺序运算符,表示通过顺序执行两个服务WS1和WS2来构造一个组合服务,即先执行WS1再执行WS2;♁是选择运算符,表示通过选择执行两个服务WS1或WS2来构造一个组合服务,即要么执行WS1,要么执行WS2;||是并行运算符,表示通过并行执行两个服务WS1和WS2来构造一个组合服务;α是迭代运算符,表示通过反复执行服务WS到一定次数来构造一个组合服务;∶是条件运算符,表示根据一定的选择条件,通过选择执行服务WS1或WS2来构造一个组合服务,即当条件表达式为真时执行WS1,否则执行WS2;■是任意次序运算符,表示通过以任意次序相继执行两个服务WS1和WS2来构造一个组合服务,即服务WS1和WS2的执行在时间上存在一定的先后关系,但又是非确定的顺序关系,既可以先执行WS1再执行WS2,也可以先执行WS2再执行WS1。定理1令S为所有Web服务构成的集合,O={⨂,♁,||,α,∶,■}为代数运算符的集合,则S是O的闭包。证明根据上述组合服务构造规则,S在单个运算符⨂,♁,||,α,∶和■下分别封闭。因此,只需证明S在这些运算符的组合下仍然封闭。除了迭代运算符α具有最高优先级之外,其他运算符具有相同的优先级,即它们满足先来先计算的原则。运算符的组合是指在构造一个组合服务时涉及两个或多个运算符的情形。通过对服务运算次数使用数学归纳法,可以证明S在这些运算符的组合下也是封闭的。证毕。组合代数的闭包属性确保Web服务运算的结果还是一个Web服务,对其可再次应用代数运算符,从而可通过反复应用这些基本运算符来构造任意复杂的服务。2.2cp-工信网中的元素模型前已述及,CP-nets网进一步扩展了Petri网的令牌机制,使其具有颜色(color)和类型(type),能用于描述复杂的数据对象,而且它结合了Petri网和高级程序语言的优点,为描述、构建和分析分布式系统提供了一种形式化工具,因而非常适合Web环境中建模服务组合与协作方面。本文使用CP-nets形式化描述Web服务组合的语义,并采用相应的支持工具CPNTools进行图解说明。定义1形式上,CP-nets是一个多元组CPN=(Σ,P,T,A,N,C,G,E,I)。其中,Σ是类型的非空有限集,也称颜色集(colorsets);(P,T,A)是基本Petri网,其中P={p1,p2,…,pm}是有限库所集,T={t1,t2,…,tn}是有限变迁集,A⊆(P×T)∪(T×P)是有限弧集;N是节点函数,定义为N:A→P×T∪T×P;C是颜色函数,定义为C:P→Σ;G是警戒函数,定义为G:T→Expression,满足∀t∈T∶Type(G(t))=Boolean∧Type(Var(G(t)))⊆Σ,其中Type(v)表示变量的类型,Var(Exp)表示表达式Exp的变量集;E是弧函数,定义为E:A→Expression,满足∀a∈A∶Type(E(a))=C(p(a))MS∧Type(Var(E(a)))⊆Σ,其中p(a)为N(a)中的库所,C(p(a))MS表示居于C(p)之上的所有多重集的集合,以下类同;I是初始化函数,定义为I:A→ClosedExpression,满足∀p∈P∶Type(I(p))=C(p)MS。定义2Web服务网是一个三元组WSN=(CPN,In,Out)。其中,CPN是一个有色Petri网;In是输入库所,其前集·In={x∈P∪T|(x,In)∈F}=∅;Out是输出库所,其后集Out·={x∈P∪T|(Out,x)∈F}=∅;如果在T中添加一个变迁t*,并且在A中加入元素(In,t*)和(t*,Out)得WSN*,则WSN*是强连通的。定义3组合服务是一个五元组CS=(N,D,E,Ω,WSN)。其中,N是CS的名称,用作其唯一的标志;D是CS的描述,概括了组合服务提供的主要功能;E是构成CS的组件服务的集合,如果E={N},则CS是一个原子服务,否则是一个组合服务;Ω指出组合类型,其值为ControlConstruct集合{Sequence,Split,Split-Join,Any-Order,Choice,If-Then-Else,Iterate,Repeat-While,Repeat-Until}中的某个元素;WSN是CP-nets表示的Web服务流模型。如前所述,在OWL-S中,服务被看作是一个过程。原子过程通常对应一个原子服务,而组合服务则建模为复合过程。图1所示为CP-nets表示的原子过程,它只有一个变迁,称为过程变迁。为简化表示,假设其只有一个输入库所和一个输出库所,即P={In,Out}。警戒函数根据服务的具体语境设定,一般为一个涉及输入变量的布尔表达式,即针对不同输入决定服务调用能否执行。颜色集Σ的定义见图中声明(Declarations)部分,初始化函数I:I(In)=1`dt;∀p∈P∶p≠In⇒I(p)=NULL用来确定CP-nets系统的初始条件。在CP-nets中,颜色代表令牌的不同赋值。变迁根据消耗的令牌数量决定输出库所新产生的令牌数,换言之,变迁决定了输入令牌和输出令牌之间的关系。这些数据值分别匹配原子过程的输入(Inputs)、输出(Outputs)和结果(Results),为简单起见,本文将它们简化为字符串。另外,OWL-S定义中的前提(Preconditions)被映射为与变迁关联的警戒函数。这时,只有当绑定元素的布尔表达式为true时,变迁才会被引发。服务组合过程可以看作是由若干原子过程通过一些ControlConstruct组合而成的复合过程,因此其对应的CP-nets模型由多个变迁和库所按照它们之间的数据流和控制流关系组成。通过对ControlConstruct的研究分析,根据表达语义的不同,可将它们归为六类服务运算。其中,Sequence对应于顺序运算;Split和Split-Join可归为并行运算;Choice对应选择运算;Any-Order对应无序运算;If-Then-Else属于条件运算;Iterate,Repeat-While和Repeat-Until归为迭代运算。下面给出从OWL-S组合规范映射到CP-nets模型的转换规则。(1)库所决定的网络结构在OWL-S中,Sequence定义一组顺序执行的过程列表,从而其对应的CP-nets模型是由多个库所和变迁组成的一种层叠或顺序结构。如图2所示,Process1和Process2依次执行。假设前提条件满足,只有在Process1执行完毕后,Process2才能执行。图中变迁分为两种类型,其中白色表示过程变迁;黑色表示控制变迁,用于执行组合运算,以下类同。(2)选取一个过程执行OWL-S中的Choice定义从给定过程中选出一个过程执行。如图3所示,Process1和Process2都可能被选择,一旦其中的一个被选中而执行,另一个必须被抛弃。(3)split和split-应力OWL-S规范中的Split和Split-Join可归类为并行运算,即两个或多个服务运算同时被一个事件发起。Split和Split-Join之间的区别是后者缺省假设为栅障同步(barriersynchronization),而对于前者,则没有关于等待、同步等进一步的描述说明。图4例解了Split-Join结构,变迁Process1和Process2同时被引发,只有执行完所有子过程才能完成整个组合流程。(4)反复执行语义OWL-S中的Iterate,Repeat-While和Repeat-Until可归类为迭代运算。其中,Iterate是一个抽象类,用来定义反复执行的过程,Repeat-While和Repeat-Until为Iterate的两个特殊子类,分别通过属性whileCondition和untilCondition指定执行的初始、结束和维持条件。图5所示为Repeat-Until的执行语义。其中执行过程变迁Process1将产生一个判断条件,根据该条件值可决定是否终止循环过程。Repeat-While的语义与此类似,区别在于控制变迁t2和t3的警戒函数相反。(5)流程1的使能OWL-S中,If-Then-Else类的语义是根据条件选择执行过程,即TestIf-Condition,ifTruedoThen,ifFalsedoElse。如图6所示,流程的执行分支取决于条件值:条件值为真,则Process1使能;条件值为假,则Process2将被引发。图中,控制变迁t1的作用是依据输入生成选择条件,并基于该条件的取值选择下一步的路由。(6)cp-工具的转换OWL-S的Any-Order允许过程按任意的、非确定的顺序执行,但不能并行执行,同时所有的子过程都必须被执行。如图7所示,给定两个过程Process1和Process2,既可以先执行Process1再执行Process2,也可以先执行Process2再执行Process1,但两者不能同时执行。定理1验证了服务组合代数的闭包属性,据此,可通过反复运用上述ControlConstruct构造任意复杂的服务。与此相应,组合服务的CP-nets模型可按以下步骤递归构建:①对OWL-S组合规范中的每个原子过程,按照图1所示生成CP-nets模型;②对每个ControlConstruct,按照相应的优先级和转换规则生成复合过程的CP-nets模型;③将此结果视作原子过程,再次使用ControlConstruct,生成新的CP-nets模型;④重复②～③,直到组合服务涉及的所有原子过程都被包含到模型中为止。定理2对于给定的组合描述,按照上述方法构建的CP-nets模型是完备的。证明对于组合模型CS,给定初始标志M0,即CS=(CPN,M0),使用下述算法探测所有可能的组合:算法1验证CP-nets模型组合完备性。因为出现在弧表达式函数和警戒函数中的每个变量只包含有限颜色集,而每个库所也只具有有限绑定元素集,所以算法在有限步终止,其输出为表示组合结果的可达图。证明使用上述方法构建的CP-nets模型是完备的,可正确表达给定的组合场景描述,从而可通过遍历模型发现到达给定状态的所有可达路径。证毕。定理2验证了转换的等价性。对于任何基于OWL-S描述的服务组合规范,可按照上述方法,将数据流描述IOPRs映射为CP-nets的对应元素,并根据控制流描述ControlConstruct的不同表达语义,将其归类为六类服务运算,进而映射为相应的CP-nets结构。同时,算法1描述了组合服务的运行时语义与CP-nets变迁引发语义的映射关系,即从初始状态M0开始,总存在一个可引发的变迁序列,使系统运行到达某一终止状态。说明本文定义的转换映射规则,能够保证转换后的模型结构正确和功能等价。至此,可将OWL-S中的组合要素表示为等价的CP-nets模型,从而可通过对相应模型的分析和模拟,验证组合的有效性。3cp-工伤保险模型的有界性及死锁性质一旦组合服务被表示为等价的CP-nets模型,可利用CPNTools工具模拟组合调用执行情况,考察其是否如预期那样运行。同时可采用状态空间法验证组合逻辑与功能上的正确性,分析动态性质。状态空间法在依据算法1生成的可达图基础上,通过计算所有可达状态和研究系统的状态变换来验证服务组合系统的各种行为属性,包括可达性、有界性、活性、家态和公平性等,这些属性是判断组合有效性与正确性的通用标准。定义4可达性(Reachability)。给定初始状态标识M0,标志Mi称为是可达的,当且仅当∃M0∶Mi∈R(M0)。可达性反映了到达给定状态的可能性。实际上,系统自动组合一系列Web服务来完成指定目标描述的过程,可以看成是在CP-nets中找到到达指定状态的变迁发生序列的过程。因此通过分析对应CP-nets模型的可达性,能够验证一个组合流程能否产生预期的执行结果。定义5有界性(Boundedness)。给定库所p∈P,非负整数n∈N,多重集C(p)MS,定义:①n是p的一个整数界,当且仅当∀M∈[M0〉∶|M(p)|≤n;②m是p的一个多重集界,当且仅当∀M∈[M0〉∶M(p)≤m。有界性定义了某一库所能够拥有的令牌最大和最小数目。通常,CP-nets的有界性反映系统运行过程中对资源的需求情况。就服务组合的情况而言,如果库所用来表示组合的状态或条件,则其包含的令牌数目是0或1;否则,说明该组合流程含有错误。如果库所用来表示信息的缓冲区,则有界性可用于判断缓冲区是否溢出。定义6活性(Liveness)。给定标志Mi∈M和绑定元素集X⊆BE,定义:①Mi是终止标志,当且仅当∀x∈X∶¬[Mi〉;②X是终止绑定元素集,当且仅当∀M′∈[Mi〉,∀x∈X∶¬[M′〉;③X是活的绑定元素集,当且仅当∀M′∈[M0〉,∃M″∈[M′〉,∀x∈X∶[M″〉x。通过验证对应CP-nets模型的活性,可以探测组合流程在执行时是否会发生死锁。流程实例的终态是终止标志,即其中没有可使能的绑定元素。如果CP-nets系统是活的,则说明这些终态代表了组合流程的某种预期的结果状态,并且总可能返回一个组合服务。如果状态分析报告中终止标志的数目超过了预期的数目,则表明该组合中存在错误。定义7家态(Home)。给定状态标志Mi∈M和标志集X∈M,定义:①Mi是家态,当且仅当∀M′∈[M0〉∶Mi∈[M′〉;②X是家空间,当且仅当∀M′∈[M0〉∶X∩[M′〉≠∅。家态指从任一可达标志都能到达的标志,即不论之前发生什么情况,该标志所对应的状态始终能够从某些前驱标志达到;而家态的集合形成了家空间。家态属性指出了哪些系统状态总是可能返回的。就服务组合而言,家态的存在说明系统从某一种初始状态下开始运行,总是可能终止在组合服务产生的状态。定义8公平性(Fairness)。给定绑定元素集X⊆BE和形式为σ=M1[t1〉M2[t2〉M3∧的无限发生序列,令ENX,J(σ)表示在标志MJ下使能的绑定元素集X中的元素数目,OCX,J(σ)表示出现在变迁tJ中的绑定元素集X中的元素数目,ENX(σ)和OCX(σ)分别表示在σ中使能和发生的总数,即ENX(σ)=∑i=1∞ENX,J(σ)∑i=1∞EΝX,J(σ)和OCX(σ)=∑i=1∞OCX,J(σ)ΟCX(σ)=∑i=1∞ΟCX,J(σ)。则定义:①X对σ是impartial公平的,当且仅当OCX(σ)=∞;②X对σ是fair公平的,当且仅当ENX(σ)=∞⇒OCX(σ)=∞;③X对σ是just公平的,当且仅当∀i≥1∶[ENX,J(σ)≠0⇒∃k≥i∶[ENX,J(σ)=0∨OCX,J(σ)≠0]]。公平性指出不同绑定元素的出现次数,反映了各变迁发生的频率。在组合服务中,原子服务的执行也许依赖于其他服务的执行,通过对公平性的考察,可发现其中的依赖关系。在CP-nets中,对公平性的分析细分为三个级别:impartial,fair和just。其中,impartial公平表示任一无限发生序列中的各变迁无限频繁地发生,换言之,如果序列中的任一变迁不能被引发,则流程必须终止(在执行某些有限的额外步后)。相对impartial公平而言,fair和just的公平性依次减弱。4组合服务的cp-工具模型下面给出一个E-Manufacturing环境下服务组合的应用实例。盟主企业接到客户订单后,根据客户需求进行产品设计,并不断修改和完善,直到客户满意为止。然后由生产部门进行半成品的生产,同时通知配套厂商进行相关零部件生产。当产品组装完成后,交由双方认可的第三方进行某些特别的测试,以确保该产品能够满足客户要求。