基于二分图匹配的语义Web服务发现方法

邓水光等:基于二分图匹配的语义Web服务发现方法1基于二分图匹配的语义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));邓水光等:基于二分图匹配的语义Web服务发现方法2述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是可选的。在这种情况下，服务s显然满足r。再以一个真实的天气预报服务为例：该服务提供一个名为GetWeather的操作，该操作接收一个城市名和一个国家名，输出该城市当天的天气情况。然而我们在基于Web服务调用框架WSIF(WebServiceInvocationFramework)开发的Web服务客户端程序调用该服务时发现，尽管我们只给一个城市名作为输入，该服务也能正确的执行并返回结果。一般而言，若一个服务能够接受不同个数的输入参数，往往可以通过提供多个不同操作来实现，每个操作接受一种可能的输入参数。但在实际中确实存在上述类型的服务，这是由于发布在网络上的诸多Web服务大多是由已有的面向对象的方法或者函数分装而成，而在面向对象程序设计中，因支持参数个数可变的函数设计模式，同时也存在函数的参数为空值或者参数使用默认值的情况，因此在将这类函数或者方法封装成Web服务时，服务操作的输入就会出现可选情况。由于当前Web服务描述语言无法刻画接口依赖关系，致使当前的服务发现方法均未能考虑服务中接口的依赖关系，因此服务发现的效果还存在较大的提升空间。本文针对上述两个问题展开研究，首先提出了Web服务注册模型WSRM(WebServiceRegistrationModel)。需要强调的是，该模型并不受限于具体的Web服务描述模型和语言，它仅用于描述Web服务的注册信息，该模型支持服务接口的语义标注和接口依赖关系的申明。基于该注册模型，本文提出了基于二分图匹配的语义Web服务发现方法，该方法在进行服务匹配过程中，通过对二分图最佳匹配进行扩展，支持服务接口之间的依赖关系，从而提高服务发现的效果。仿真实验表明该方法因考虑了服务接口的依赖关系和单射匹配的要求，服务发现的召回率、准确率得到提高，从而更好满足用户服务发现的需求。文章内容安排如下：第2节介绍Web服务注册模型；第3节介绍基于二分图的语义Web服务发现方法，重点阐述了服务操作与服务请求的相似度计算以及服务接口匹配策略；第4节是仿真实验与结果分析；第5节是相关工作介绍；最后是结论与展望。2Web服务注册模型Web服务发现是根据用户对目标服务的需求描述，通过服务匹配算法从服务注册中心查找到与用户需求描述相匹配的服务。因此，Web服务的注册信息对于Web服务匹配的结果至关重要。为了对基于WSDL的Web服务实施语义匹配，同时在匹配过程中考虑接口依赖信息，势必对标准的WSDL注册信息进行扩展。而在扩展过程中不仅要保持原有注册信息模式的完整性，以保证原有服务发现方法的可用性；同时为使信息扩展易于操作，必须保证服务提供者在进行服务注册时能简易方便的提供扩展信息。因此，针对现有WSDL注册信息缺乏语义描述和接口依赖申明，我们作如下两方面的扩展。(1)增加操作的接口语义信息基于WSDL的服务功能均是由各个操作(Operation)完成的，而对于操作而言，输入和输出(这里统称为接口)是最为重要功能元素。在进行服务匹配时，接口匹配尤为重要，它是决定服务是否满足用户目标功能的关键。然而，标准的WSDL注册信息缺乏接口的语义描述。为此，我们对接口进行语义扩展，一方面使其准确刻画服务功能，另一方面使其支持基于语义的接口匹配，提高服务发现准确率。而扩展接口语义的过程可以在服务提供者进行服务注册时，通过浏览领域本体为接口指定本体词汇来完成。因此，接口语义信息的扩展不仅不改变原有注册信息模式，而且扩展信息的获取也简单可行。(2)增加操作的接口依赖关系邓水光等:基于二分图匹配的语义Web服务发现方法3接口依赖关系是指输出接口对于输入接口的依赖。给定操作的一个输出，通过操作的接口依赖关系可得出该输出所依赖的输入集合。对于一个操作，若一个输入i被一个输出o所依赖，则说明调用该服务时，为了得到o这一输出，用户提供的输入集合中必须包含i这一输入。已有的服务发现方法没有考虑接口依赖关系的重要原因在于目前的WSDL注册信息没有提供接口依赖的描述机制。因此，我们对已有WSDL注册信息扩展接口依赖关系，使其具备接口间依赖关系的刻画能力。而接口依赖关系的扩展同样可以在服务注册过程中完成。服务提供者只需在原有注册过程中，为服务的输出指定其依赖的输入即可自动生成服务的接口依赖关系。如对引言部分的天气预报服务进行注册时，只需为操作GetWeather的输出指定其依赖的输入为城市名则可自动生成该操作的一条接口依赖关系，即输出天气依赖于输入城市。通过增加接口依赖关系，一方面便于用户在调用服务时提供合适的输入参数，另一方面使得服务匹配过程中可以通过考虑接口之间的依赖关系而提供服务发现效果。对WSDL的注册信息进行上述两个方面的扩展之后，我们得到如下操作以及服务的形式化定义：定义1操作一个操作p是一个6元组{,,,,,}ppppndtIOf，其中：(1)pn是该服务的名称，在服务内部起到唯一标识作用；(2)pd是该服务的文本描述信息；(3)t是该服务所属的端口类型(PortType)；(4)12{,,...,}nIiii是该服务的输入消息集合；12{,,...,}mOooo是该服务的输出消息集合；IO统称为该服务的接口集合。对于eIO，均与某一本体概念关联。(5):2IpfO是该服务的接口依赖函数，其定义域为输出集合，值域为输入集合的幂集。对于oO,()pfo表示该输出所依赖的输入集合。一个输出o依赖于一个输入集合'I表示为'oI。上述操作的定义相比标准的WSDL注册的操作信息相比，增强了接口关联的本体概念，同时也增加了服务操作的接口依赖关系，而接口依赖关系则是通过接口依赖函数得到。定义2全依赖输出/局部依赖输出给定一个操作{,,,,,}ppppndtIOf和该操作的一个输出oO，若关系oI成立，即()pfoI成立，则输出o是一个全依赖输出；若()pfoI，则输出o是一个局部依赖输出。一个操作的一个全依赖输出是依赖于该操作的所有输入，即要获得该输出，则在调用此服务时，用户需要提供该操作的所有输入；而一个局部依赖输出是依赖于该操作的部分输入，即要获得该输出，则在调用此服务的时候，用户仅需要提供其依赖的输入即可。定义3服务一个服务s是一个3元组(,,)sssndP，其中：(1)sn是该服务的名称；(2)sd是该服务的文本描述信息；(3)12{,,...,}nPppp是该服务中的操作集合；需要注意的是，上述操作和服务的定义仅包含用于服务发现的信息。图1显示的是一个地理信息服务(GIS)的注册模型，包含了GetTimeInfo、GetWeather和GetCapital三个操作。操作内部的有向虚线表示输出到输入之间的依赖，如操作GetWeather，输出Weather依赖于两个输入Date和City，而输出ClimateType仅依赖于输入City。因此，Weather是全依赖输出，而ClimateType是局部依赖输出。邓水光等:基于二分图匹配的语义Web服务发现方法4图例地理信息服务(GIS)ioiiooiiiooCountryWeatherStateCapitalCityiStateLatitudeDateGMTTimeZoneTimeiLongitudeoClimateTypeGetTimeIn