ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.ac.cnJournalofSoftware,Vol.18,No.12,December2007,pp.2991−3000:+86-10-62562563©2007byJournalofSoftware.Allrightsreserved.基于Petri网的语义Web服务自动组合方法∗汤宪飞1,2+,蒋昌俊1,2,丁志军1,2,王成1,21(同济大学计算机科学与技术系,上海201804)2(国家高性能计算机工程技术研究中心同济分中心,上海201804)APetriNet-BasedSemanticWebServiceAutomaticCompositionMethodTANGXian-Fei1,2+,JIANGChang-Jun1,2,DINGZhi-Jun1,2,WANGCheng1,21(DepartmentofComputerScienceandTechnology,TongjiUniversity,Shanghai201804,China)2(TongjiBranch,NationalEngineeringandTechnologyCenterofHighPerformanceComputer,Shanghai201804,China)+Correspondingauthor:Phn:+86-21-69589864,E-mail:xianfei.tang@gmail.comTangXF,JiangCJ,DingZJ,WangC.APetrinet-basedsemanticWebserviceautomaticcompositionmethod.JournalofSoftware,2007,18(12):2991−3000.:Webservicecompositionallowsdeveloperstocreateapplicationsrapidly.ButduetothetremendousgrowthinthenumberofWebservicesavailable,theWebservicecompositionproblemisstillachallengingresearchissue.ThispaperintroducesanautomaticWebservicecompositionmethodwhichconsidersbothservices’input/outputtypecompatibilityandbehavioralconstraintcompatibility.TheservicesavailablearetranslatedintoasetofHornclause-likerules.User’sinputandoutputrequirementsaremodeledasasetoffactsandagoalstatementintheHornclausesrespectively.ThenPetrinetischosentomodeltheHornclausesetandT-invarianttechniqueisusedtodeterminetheexistenceofcompositeservicesfulfillingtheuser’sinput/outputrequirements.TwoalgorithmsarepresentedforobtainingthePetrinetmodelsofthecompositeWebserviceswhichsatisfynotonlytheuser’sinput/outputrequirementsbutalsotheuser’sbehavioralconstraints.Keywords:Webservice;Webservicecomposition;Hornclause;Petrinet;T-invariant摘要:Web服务组合使得开发人员可以快速地创建自己的应用程序.但是,随着Internet上可用的Web服务数目的增加,Web服务组合是一项高度复杂的任务.针对语义Web服务的自动组合问题,提出了一种既考虑服务输入/输出又考虑服务行为约束的自动组合方法.首先,注册服务被转化为一组Horn子句形规则,用户的输入和输出请求分别被转化为Horn子句中的事实和目标,从而将寻找满足用户输入/输出请求的合成服务问题转化为Horn子句的逻辑推理问题;然后,用Petri网来为该Horn子句集建模,T-不变量技术被用来判定是否存在满足用户输入/输出请求的合成服务;最后给出了两种算法来获取既满足用户输入/输出请求又满足用户行为约束的合成服务的Petri网模型.关键词:Web服务;Web服务组合;Horn子句;Petri网;T-不变量中图法分类号:TP393文献标识码:A∗SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNos.60534060,60473094(国家自然科学基金);theNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.2007AA01Z136(国家高技术研究发展计划(863));theNationalBasicResearchProgramofChinaunderGrantNo.2003CB317002(国家重点基础研究发展计划(973))Received2007-06-10;Accepted2007-10-162992JournalofSoftware软件学报Vol.18,No.12,December2007随着一系列开放、标准技术的提出,Web服务以其松散耦合、语言中立、平台无关性和开放性有效地解决了平台异构性和互操作等问题,正在成为一个崭新的分布式计算模型和一种新兴的互联网应用模式.作为一种新的分布式计算模式,Web服务技术允许异构软件和应用系统的互联互通,并使得组织可以通过Internet共享数据、软件和硬件资源[1].异构软件和应用系统的功能可作为Web服务统一发布并在服务注册处注册.Internet用户可以使用标准协议来发现并调用注册的服务.但是,为了提高服务的可重用性、分散和简化应用逻辑,单个Web服务一般都不会做得太复杂[2].每个服务所提供的功能一般都比较简单.要实现具体的复杂应用,就必须要实现多个服务的交互协作.可以说,Web服务的真正潜力在于服务组合.如果注册的Web服务不能结合起来形成合成服务以满足用户更加复杂的要求,其用途就很有限.此外,随着支持电子商务解决方案的Web服务的迅速增加,对于整合这些基于Web的自治、异构服务的需求进一步变大.从软件复用的角度来说,当把Web服务视为可复用的软件构件实体时,Web服务组合也可看作是一种在Internet上的基于构件的软件开发[3].由于Internet上有大量的Web服务可用,手工分析这些服务并生成合成服务规划已经超出了人的能力范围[4].因此,实现Web服务的自动或者半自动组合是十分必要的.此外,语义Web服务通过引进语义来帮助消除服务发现和组合等过程中的二义性和模糊性,从而为服务自动发现、组合、执行等提供了良好的基础.目前,主要的语义Web服务描述语言主要有OWL-S,WSMO(Webservicemodelingontology)和SAWSDL(semanticannotationsforWSDLandXMLschema)[5,6]等.本文通过语义Web服务组合建模,将可用的Web服务用一组Horn子句形规则表示,将用户提供的输入表示为Horn子句中的一组事实,用户期待的输出表示为Horn子句中的一个目标,从而将寻找一个满足用户输入/输出要求的合成服务问题转化为一个Horn子句推理问题;然后,我们利用Petri网作为该Horn子句集的形式化模型,使用T-不变量技术来确定是否存在一个满足用户输入/输出要求的合成服务;最后,我们给出了两种算法以获得一个满足用户诸项要求和约束(输入/输出要求、行为约束兼容要求以及服务质量要求)的合成服务的Petri网模型.本文形式上采用SAWSDL作为语义Web服务的外部规范,但是,该方法也可以与其他语义Web服务描述语言相结合.1基本概念1.1语义Web服务我们首先介绍一些在语义Web服务组合中用到的相关概念.定义1(原子服务).一个原子Web服务,即SAWSDL中的一个操作,可以用一个四元组WS=(I,O;BC,QoS)表示,其中:(1)I表示该服务的输入参数所引用的语义概念集合;(2)O表示该服务的输出参数所引用的语义概念集合;(3)BC表示该服务的行为约束集合,行为约束是服务提供者为保证服务正确执行而施加于服务上的一些条件和策略;(4)QoS表示该服务的服务质量参数集合,QoS属性可以考虑价格、响应时间、可用性、可靠性等.在SAWSDL中,Web服务的输入/输出参数可以通过modelReference引用外部语义模型(如本体)中的概念.服务的行为约束也可以通过modelReference加入到SAWSDL中;有多种类型的行为约束,如服务的可用时间、服务的覆盖范围以及其他领域相关的约束.以一个投递服务为例,该服务可能只在7:00~20:00这个时间段内接受服务请求(服务可用时间约束),其投递区域可能局限于上海(服务覆盖范围约束),接受的包裹重量不大于50kg(领域相关的约束)等等.在SAWSDL中,这些约束是用SWRL(semanticwebrulelanguage)来描述的.目前,SAWSDL尚没有提供对于服务的QoS描述的支持,但用户服务提供者可以利用其他协议如SLA(servicelevelagreement)对服务的QoS进行描述.汤宪飞等:基于Petri网的语义Web服务自动组合方法2993定义2(用户请求).一个用户请求可以用一个四元组WS=(Iprov,Oreq;BCuser,QoSuser)来表示,其中:(1)Iprov表示服务请求者提供的输入所引用的语义概念集合;(2)Oreq表示服务请求者渴望得到的输出所引用的语义概念集合;(3)BCuser表示服务请求者定义的行为约束集合;(4)QoSuser表示服务请求者定义的服务质量参数标准.定义3(参数类型兼容).设Ci和Cj分别是参数Pari和Parj所引用的语义概念,如果Ci和Cj是等价概念(在OWL中由owl:equivalentClass或owl:equivalentProperty定义),或者Ci是Cj的子概念(在OWL中由rdfs:subClassof或rdfs:subPropertyof定义),那么参数Pari和Parj类型兼容,参数Pari的值可以安全地传递给参数Parj.定义4(行为约束兼容).两个Web服务WSi和WSj是行为约束兼容的,如果对于这两个服务所有的任何一个同种类型的约束bck,其值的交集不为空.例如,有两个服务WS1和WS2.WS1的可用时间是7:00~20:00,服务覆盖区域是上海;WS2的可用时间是8:00~21:00,服务覆盖区域是北京.那么,这两个服务的可用时间约束是兼容的,但其覆盖区域约束不兼容,因此,其行为约束是不兼容的.行为约束不兼容的服务组合在一起时可能会导致结果的不正确.定义5(服务组合问题).一个服务组合问题就是从可用的服务集合中选出一组服务,该组服务能够按照一定的构造方式形成一个新的可以执行的增值服务,此增值服务能够接受用户提供的输入值(或其子集),生成用户期望的输出,并且要考虑到构成该增值服务的各原子服务之间及其与用户请求规范之间的行为约束兼容,以及原