基于二分图匹配的语义Web服务发现方法邓水光,尹建伟+,李莹,吴健,吴朝晖(浙江大学计算机科学与技术学院,浙江杭州310027)摘要:如何从大规模服务集合中快速而准确的发现目标服务是应用Web服务技术的关键。现有基于语义的Web服务发现方法应用实施难度大且效果存在较大提升空间。本文首先提出了Web服务注册的信息模型，该模型不受限于具体的Web服务模型和表达语言，支持接口语义标注和接口依赖关系的申明。进而提出了基于二分图匹配的语义Web服务发现方法，通过对二分图最佳匹配进行扩展，将服务匹配问题转化成二分图的扩展最佳匹配的求解问题，支持服务接口之间的依赖关系，从而提高服务发现的效果。一系列仿真实验表明该方法不仅能较大提高服务发现的召回率和准确率，而且还能以线性时间复杂度满足用户请求。关键词:面向服务的计算、Web服务、服务发现、二分图匹配中图法分类号:TP393文献标识码:A1引言Web服务是一种基于网络环境的自适应、自描述、模块化的应用程序，因其具备良好的互操作能力和可重用性而在电子商务、应用集成、流程管理等领域中扮演越来越重要的角色[1]。近年来，随着Web服务相关标准的持续完善和支持Web服务开发的软件平台的不断成熟，Web服务已经成为互联网中最为重要的一种计算资源和软件资产。而Web服务数量的不断增长，使得用户难以从大规模服务集合中自动、快速、准确的搜索出目标服务。目前，Web服务发现吸引了国内外众多学者的关注，成为面向服务的计算(ServiceOrientedComputing)领域中的关键问题[2]。由于传统的基于UDDI(UniversalDescription,Discovery,andIntegration)的服务注册与发现机制仅支持对服务语法层面的操作，一方面在服务注册阶段无法准确刻画服务能力，另一方面在服务发现过程中因仅提供基于关键字的服务匹配策略，因此服务发现效果无法满足用户要求。特别是在服务数量剧增的情况下，用户急需一种自动、快速和准确的服务发现机制。而语义Web服务的提出，使得Web服务发现的研究进入了一个新的阶段。由于语义Web服务采用领域本体准确刻画了服务功能及其属性，因此基于语义的Web服务发现通过语义推理能自动准确的完成服务匹配，从而提高服务发现的效果。目前，众多的基于语义的Web服务发现的方法被提出来[3-13]，这些方法在一定程度上提高了Web服务发现的准确率、召回率和自动化程度，但普遍存在如下两个问题：1)应用实施难度较大。这是由于这些方法均是建立在全新的语义Web服务模型和描述语言的基础上，如DAML-S/OWL-S、WSMO/WSML或者WSDL-S等。这些方法在特定的服务模型和应用场景中均取得较好的效果，但基于这些新的语义Web模型和语言的服务数量少之又少；而另一方面，WSDL(WebServiceDescriptionLanguage)作为Web服务描述规范而被广泛采用，出现了大量的基于WSDL的Web服务，因此在应用当前这些方法之前，需要将WSDL转化成目标服务模型和语言，因此增大了方法应用的难度和复杂度。2)方法还存在较大的提升空间。这是由于这些方法均遵循了文献[3]中的服务匹配原则，即一个服务SupportedbytheNationalKeyTechnologyR&DProgramundergrantNo.2006BAH02A01(国家科技支撑计划);theNationalNaturalScienceFoundationofChinaunderGrantNo.60603025andNo.60503018(国家自然科学基金);theNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.2006AA01Z171(国家高技术研究发展计划(863));---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---描述s被一个用户请求描述r成功匹配，当且仅当满足：a)s能够提供r中的所有输出；b)r能够提供s中的所有输入。后继很多基于语义的服务发现方法均在该文献的基础上有所改进[4][7][13][17]，但均接受了这一成功匹配的原则。虽然这种匹配原则较为自然，但这一原则过于严谨，在很多情况下将导致很多满足用户要求的服务被过滤掉。考虑这样一个例子：服务s接收两个输入a和b产生两个输出o和p；而用户请求r包含一个输入a和一个输出o。根据上述成功匹配的原则，由于r不能提供输入b，即s和r不满足第二条原则，因此服务s不满足需求r。然而在服务s中可能输入b对输出o是可选的...