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

《基于二分图匹配的语义web 服务发现方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

邓水光等:基于二分图匹配的语义Web服务发现方法1基于二分图匹配的语义Web服务发现方法*SupportedbytheNationalKeyTechnologyR&DProgramundergrantNo.2006BAH02A01(国家科技支撑计划);theNationalNaturalScienceFoundationofChinaunderGrantNo.60603025andNo.60503018(国家自然科学基金);theNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.2006AA01Z171(国家高技术研究发展计划(863));邓水光,尹建伟+,李莹,吴健,吴朝晖(浙江大学计算机科学与技术学院,浙江杭州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]中的服务匹配原则，即一个服务描述 邓水光等:基于二分图匹配的语义Web服务发现方法1s被一个用户请求描述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。再以一个真实的天气预报服务http://www.webservicex.com/globalweather.asmx?WSDL为例：该服务提供一个名为GetWeather的操作，该操作接收一个城市名和一个国家名，输出该城市当天的天气情况。然而我们在基于Web服务调用框架WSIF(WebServiceInvocationFramework)开发的Web服务客户端程序调用该服务时发现，尽管我们只给一个城市名作为输入，该服务也能正确的执行并返回结果。一般而言，若一个服务能够接受不同个数的输入参数，往往可以通过提供多个不同操作来实现，每个操作接受一种可能的输入参数。但在实际中确实存在上述类型的服务，这是由于发布在网络上的诸多Web服务大多是由已有的面向对象的方法或者函数分装而成，而在面向对象程序设计中，因支持参数个数可变的函数设计模式，同时也存在函数的参数为空值或者参数使用默认值的情况，因此在将这类函数或者方法封装成Web服务时，服务操作的输入就会出现可选情况。由于当前Web服务描述语言无法刻画接口依赖关系，致使当前的服务发现方法均未能考虑服务中接口的依赖关系，因此服务发现的效果还存在较大的提升空间。本文针对上述两个问题展开研究，首先提出了Web服务注册模型WSRM(WebServiceRegistrationModel)。需要强调的是，该模型并不受限于具体的Web服务描述模型和语言，它仅用于描述Web服务的注册信息，该模型支持服务接口的语义标注和接口依赖关系的申明。基于该注册模型，本文提出了基于二分图匹配的语义Web服务发现方法，该方法在进行服务匹配过程中，通过对二分图最佳匹配进行扩展，支持服务接口之间的依赖关系，从而提高服务发现的效果。仿真实验表明该方法因考虑了服务接口的依赖关系和单射匹配的要求，服务发现的召回率、准确率得到提高，从而更好满足用户服务发现的需求。文章内容安排如下：第2节介绍Web服务注册模型；第3节介绍基于二分图的语义Web服务发现方法，重点阐述了服务操作与服务请求的相似度计算以及服务接口匹配策略；第4节是仿真实验与结果分析；第5节是相关工作介绍；最后是结论与展望。1Web服务注册模型Web服务发现是根据用户对目标服务的需求描述，通过服务匹配算法从服务注册中心查找到与用户需求描述相匹配的服务。因此，Web服务的注册信息对于Web服务匹配的结果至关重要。为了对基于WSDL的Web服务实施语义匹配，同时在匹配过程中考虑接口依赖信息，势必对标准的WSDL注册信息进行扩展。而在扩展过程中不仅要保持原有注册信息模式的完整性，以保证原有服务发现方法的可用性；同时为使信息扩展易于操作，必须保证服务提供者在进行服务注册时能简易方便的提供扩展信息。因此，针对现有WSDL注册信息缺乏语义描述和接口依赖申明，我们作如下两方面的扩展。(1)增加操作的接口语义信息基于WSDL的服务功能均是由各个操作(Operation)完成的，而对于操作而言，输入和输出(这里统称为接口)是最为重要功能元素。在进行服务匹配时，接口匹配尤为重要，它是决定服务是否满足用户目标功能的关键。然而，标准的WSDL注册信息缺乏接口的语义描述。为此，我们对接口进行语义扩展，一方面使其准确刻画服务功能，另一方面使其支持基于语义的接口匹配，提高服务发现准确率。而扩展接口语义的过程可以在服务提供者进行服务注册时，通过浏览领域本体为接口指定本体词汇来完成。因此，接口语义信息的扩展不仅不改变原有注册信息模式，而且扩展信息的获取也简单可行。(2)增加操作的接口依赖关系接口依赖关系是指输出接口对于输入接口的依赖。给定操作的一个输出，通过操作的接口依赖关系可 邓水光等:基于二分图匹配的语义Web服务发现方法1得出该输出所依赖的输入集合。对于一个操作，若一个输入i被一个输出o所依赖，则说明调用该服务时，为了得到o这一输出，用户提供的输入集合中必须包含i这一输入。已有的服务发现方法没有考虑接口依赖关系的重要原因在于目前的WSDL注册信息没有提供接口依赖的描述机制。因此，我们对已有WSDL注册信息扩展接口依赖关系，使其具备接口间依赖关系的刻画能力。而接口依赖关系的扩展同样可以在服务注册过程中完成。服务提供者只需在原有注册过程中，为服务的输出指定其依赖的输入即可自动生成服务的接口依赖关系。如对引言部分的天气预报服务进行注册时，只需为操作GetWeather的输出指定其依赖的输入为城市名则可自动生成该操作的一条接口依赖关系，即输出天气依赖于输入城市。通过增加接口依赖关系，一方面便于用户在调用服务时提供合适的输入参数，另一方面使得服务匹配过程中可以通过考虑接口之间的依赖关系而提供服务发现效果。对WSDL的注册信息进行上述两个方面的扩展之后，我们得到如下操作以及服务的形式化定义：定义1操作一个操作p是一个6元组，其中：(1)是该服务的名称，在服务内部起到唯一标识作用；(2)是该服务的文本描述信息；(3)是该服务所属的端口类型(PortType)；(4)是该服务的输入消息集合；是该服务的输出消息集合；统称为该服务的接口集合。对于，均与某一本体概念关联。(5)是该服务的接口依赖函数，其定义域为输出集合，值域为输入集合的幂集。对于,表示该输出所依赖的输入集合。一个输出o依赖于一个输入集合表示为。上述操作的定义相比标准的WSDL注册的操作信息相比，增强了接口关联的本体概念，同时也增加了服务操作的接口依赖关系，而接口依赖关系则是通过接口依赖函数得到。定义2全依赖输出/局部依赖输出给定一个操作和该操作的一个输出，若关系成立，即成立，则输出o是一个全依赖输出；若，则输出o是一个局部依赖输出。一个操作的一个全依赖输出是依赖于该操作的所有输入，即要获得该输出，则在调用此服务时，用户需要提供该操作的所有输入；而一个局部依赖输出是依赖于该操作的部分输入，即要获得该输出，则在调用此服务的时候，用户仅需要提供其依赖的输入即可。定义3服务一个服务s是一个3元组，其中：(1)是该服务的名称；(2)是该服务的文本描述信息；(3)是该服务中的操作集合；需要注意的是，上述操作和服务的定义仅包含用于服务发现的信息。图1显示的是一个地理信息服务(GIS)的注册模型，包含了GetTimeInfo、GetWeather和GetCapital三个操作。操作内部的有向虚线表示输出到输入之间的依赖，如操作GetWeather，输出Weather依赖于两个输入Date和City，而输出ClimateType仅依赖于输入City。因此，Weather是全依赖输出，而ClimateType是局部依赖输出。 邓水光等:基于二分图匹配的语义Web服务发现方法1图1.具有接口依赖信息的Web服务注册信息为实现基于语义的服务匹配，不仅要求服务描述采用语义刻画，同时也要求用户请求也具备语义信息。服务请求是指用户对目标服务的需求描述，由于本文重点关注用户的功能需求，因此暂时忽略用户的非功能需求，如服务质量等，给出如下服务请求定义。定义4服务请求一个服务请求r可形式化为一个3元组，其中：(1)是用户能够提供的输入集合；(2)是用户期望得到的输出集合；(3)对于均与某一本体概念关联。(4)是用户设定的接受阀值，即一个服务(实质上是指服务的操作)与服务请求的相似度大于等于该阀值时，该服务才被认为是可接受的目标服务；1基于二分图匹配的Web服务发现Web服务发现是建立服务匹配的基础上，即通过将用户请求与服务注册信息进行匹配，从而选出被匹配的服务，因此，服务匹配是服务发现重要环节。1.1服务与服务请求的匹配一般而言，对于给定的一个服务s和一个服务请求r，判定s是否满足r的过程是判定在s中是否存在某一个操作p与r的相似度值大于等于用户设定的阀值，如果存在这样的操作，则表明服务s满足用户请求r，而这一判定的过程即为服务与服务请求之间的匹配过程。定义5匹配操作给定服务s的一个操作和一个服务请求，若p与r之间的相似度，则称操作p为服务s对r的一个匹配操作。定义6最佳匹配操作给定服务s的一个操作p和一个服务请求r，p是s对r的一个最佳匹配操作，当且仅当。算法ServiceMatchmaking以一个服务和一个服务请求作为输入，返回该服务中对该服务请求的最佳匹配操作的集合。第3至11行分别计算服务中的每一个操作与服务请求的相似度(计算方法见3.2节)，选出具有最高相似度的操作。接着判断选出的操作与服务请求的相似度是否大于等于用户设定的阀值。如果大于等于这个阀值，则将选出的操作作为最佳匹配操作返回；否则返回NULL，此时表明该服务中不满足用户请求。Algorithm:ServiceMatchmakingInput:Aserviceandarequest;Output:Best-Matched-OperationsorNULL;1.SET;2.SETBMOasthesetofBest-Matched-Operations; 邓水光等:基于二分图匹配的语义Web服务发现方法11.FOReachoperation{2.IF(){3.;4.BMO.clear;//deletealltheelementsinBMO5.BMO.add(p);//insertpwhichhasthenewmaxSimPR6.}ElseIF(){7.BMO.add(p);//insertpwhoseSimPRequalstoMaxSimPR8.}9.}10.IF(){11.RETURNBMO;12.}ELSE{13.RETURNNULL;14.}1.1服务操作与服务请求的相似度计算给定一个服务操作和一个服务请求，我们设计如下算法CalSimPR计算两者之间的相似度。该算法依据WSRM模型考虑局部依赖输出和全依赖输出在匹配上的差异性，通过调用接口匹配算法(见3.3节)实现服务操作与服务请求之间的输入/输出接口的匹配。Algorithm:CalSimPRInput:Anoperationandarequest;Output:;1.IF(){2.RETURN0;3.}4.Findaninjectionthatensuresreachesitsmax;5.SET;6.SET;7.IF(){8.RETURN0;9.}10.Findaninjectionthatensuresreachesitsmax;11.RETURN;算法CalSimPR按照如下6个步骤来计算服务操作与服务请求之间的相似度:(1)第1至3行：判断不等式是否成立，即检验操作p产生的输出在数量是否能够满足用户期望得到的输出数量。若p的输出数量比期望的输出数少，则说明操作p无法满足用户需求，此时返回；否则进入下一步骤； 邓水光等:基于二分图匹配的语义Web服务发现方法1(1)第4至5行：求出从集合Or到O的单射，使得和式达到其最大值。该步骤的目标是为用户请求的每一个输出在服务产生的输出集合中找到一个不同的输出与之匹配，使得匹配的全局相似度最大。从这一步骤可以得到操作中的与用户要求的输出匹配的输出集合，即。该步骤可通过3.3中的算法InterfaceMatch来求解单射f；(2)第6行：根据操作的接口依赖函数得到用户必须提供的输入集合，也就是输出集合O'中的每一个输出所依赖的输入集合的并集，即；(3)第7至9行：判断不等式是否成立，即检验用户能否提供必要的输入用于调用操作p。如果用户提供的输入数量比集合I'的元素个数少，则说明用户无法调用该操作，此时返回；否则进入下一步骤；(4)第10行：求出从集合I'到Ir的单射，使得和式达到其最大值。该步骤的目标是为集合I'中的每一个输入在用户请求提供的输入集合中找到一个不同的输入与之匹配，使得匹配的全局相似度最大。与步骤(2)相同，可通过3.3节的算法InterfaceMatch求解单射g；(5)第11行：在完成服务操作与服务请求的接口匹配之后，按公式(1)计算两者的相似度，其中函数用于计算两个本体概念之间的相似度，可按照文献[8]中所述方法进行计算。(1)算法CalSimPR在调用3.3节的算法InterfaceMatc进行接口匹配时，既保证了服务请求的输出与服务操作的输出之间的全局匹配度最大，同时也保证了服务操作的输入与服务请求的输入之间的全局匹配度最大，因此可得到如下定理，即通过算法CalSimPR求得的服务操作与服务请求的相似度值为最大值。限于篇幅，证明过程略。定理1一般而言，服务匹配所得的相似度值的范围为[0,1]。由于概念之间的相似度，易得如下定理，限于篇幅，证明过程略。定理2对于一个服务操作p与一个服务请求r，可通过算法CalSimPR求解两者之间的相似度，其值为0表示该操作不满足服务请求(主要指在功能上不满足服务请求，如操作不能提供用户期望的某些输出，或者用户无法提供用于调用该操作的必要的输入)；值为1表示操作在功能上和语义上完全与服务请求匹配；值位于0与1之间表示操作在结构上满足服务请求，但在语义上是局部满足服务请求的。1.1基于二分图的服务接口匹配在算法CalSimPR中，步骤(2)和(5)最为关键，其目标分别要实现服务请求的输出与服务操作的输出之间的匹配，以及操作的输入与服务请求的输入之间的匹配。我们将两者统称为接口匹配，并将其定义如下。定义7接口匹配问题给定两个本体概念集合和且，任一属于X的本体概念x与任一属于Y的本体概念y之间的相似度值满足，则接口匹配的问题可定义为： 邓水光等:基于二分图匹配的语义Web服务发现方法1求一个从集合X到集合Y的单射，使得和式取得最大值。为求解接口匹配问题，我们借鉴二分图的概念，在其匹配理论上进行扩展来求解。我们可将接口匹配问题的输入条件建模成一个二分图，其中X和Y分别对应上述两个本体概念集合X和Y；边集E可以按照如下规则来构造：对于，若，则在二分图G中x和y对应的两个顶点之间连一条边，并给该边一个权重。通过二分图建模之后，接口匹配问题就可以转化为在二分图G上求解从顶点集合X到Y的一个匹配M，使得M能覆盖集合X中所有节点，同时要求M的权和最大，即M为接口匹配问题中需要求解的单射f。鉴于二分图建模过程较为简单，其算法复杂度为，因此本文不作赘述。尽管二分图的构造过程较为简单，但为避免每进行一次服务匹配都需要重复一次服务到二分图的转换过程，可以在第一次转换之后将服务对应的二分图存储于服务注册库中。由于二分图仅包含两个顶点集合与一个边集合，因此存储空间小，维护方便。由于二分图的最佳匹配是针对满足条件(即)的二分图而言，无法直接应用于的情况，因此我们将二分图的最佳匹配的定义进行扩充，给出二分图的扩展最佳匹配的定义：定义8二分图的扩展最佳匹配给定一个带权二分图和G的一个匹配M，二分图满足条件，M是G的一个扩展最佳匹配，当且仅当：(1)若，M是G的最佳匹配；(2)若，M是覆盖集合X中的所有节点，且权和最大的匹配。因此，接口匹配问题就转化为求解二分图的扩展最佳匹配问题。我们通过扩展Kuhn-Munkres(KM)算法来求解该问题。KM算法是一个经典的用于求解二分图的最佳匹配的高效算法[16]，它通过求解二分图的等价子图的完备匹配来获得二分图的最佳匹配，其正确性源于如下定理。定理3二分图G的等价子图的完备匹配即为G的最佳匹配。由于KM算法中的二分图满足条件，因此无法直接使用该算法求解二分图的扩展最佳匹配。为此，我们提出基于KM算法的接口匹配算法InterfaceMatch。Algorithm:InterfaceMatchInput:and;Output:AnExtended-Optimal-MatchingforG;1.IF(){2.UseKMalgorithmtofindanOptimalMatchingMforG;3.}ELSE{4.TransformG(X,Y,E)toG'(X',Y,E')where:and;5.UseKMalgorithmtofindanOptimalMatchingM’forG’;6.TransformM’toMbyeliminatingfromM’;7.}8.RETURNM;算法InterfaceMatch的工作过程描述如下：(1)第1至3行：当，直接使用KM算法求解G的一个最佳匹配M。根据二分图的扩展最佳匹配的定义，M同样也是G的一个扩展最佳匹配；(2)第4至6行：当，InterfaceMatch通过二分图变换使得该二分图满足条件。为此，在 邓水光等:基于二分图匹配的语义Web服务发现方法1X集合中增加个虚拟顶点，并且在新增的每一个节点与集合Y中的每一个节点之间增加一条权重为0的边。因此，二分图G经过转化之后变成。由于，所以此时可使用KM算法为G'求得最佳匹配M'，之后再通过去除M'中覆盖了虚拟节点的所有的边而将M'转化成M。由如下定理可知M是G的一个扩展最佳匹配。定理4给定一个带权二分图和该图的一个最佳匹配M，记M中权重为0的边组成的集合为，集合X被覆盖的顶点组成的集合为，若集合X中任意一个被权重为0的边覆盖的顶点与Y中的任意顶点之间均存在边，则在去除匹配M中所有权重为0的边之后形成的匹配是二分图的扩展最佳匹配，其中，。证明：在中，因，所以根据二分图扩展最佳匹配的定义，需要证明：1)覆盖集合中的所有节点；2)的权和是最大的。对于第一点：由于，而所覆盖的顶点集合也为，因此覆盖了集合中的所有节点；对于第二点：若的权和不是中最大的，假设中另一个不同于的匹配具有最大权和，且覆盖集合中所有顶点，那么总可以在中添加条权重为0的边覆盖集合中顶点(这是由于中的顶点中的每一个顶点与集合Y中的任意顶点之间均有边)，从而使得变成，而到的转化过程中仅添加权和为0的边，因此的权和与的权和相同。根据假设，的权和大于的权和，而的权和与M的权和相同，因此的权和大于M，这说明是二分图G的一个最佳匹配，其权和大于M，这与M是G的一个最佳匹配矛盾，因此假设不成，从而证明了匹配是二分图中权和最大的匹配。证毕！定理4说明了算法InterfaceMatch的正确性，即通过该算法可以正确得到接口匹配问题的解。KM算法的时间复杂度为[16]，其中，因而算法CalSimPR的时间复杂度为，其中是服务输入或者输出接口个数，为一常数，所以算法ServiceMatchmaking的时间复杂度为，其中n为服务中的操作数。对一个服务集合而言，由于m和n均为常数，因此算法ServiceMatchmaking的时间开销为常数。1.1一个示例由于服务操作与服务请求之间的相似度计算是实施服务匹配的重要依据，因此本节以图2所示的一个示例来说明如何计算服务操作与服务请求之间的相似度，同时说明如何基于二分图完成接口匹配。图2.操作与服务请求匹配的示例在图2所示的服务操作p和服务请求r中，有向连线表示连接的两个概念之间的语义相似度。我们根据算法CalSimPR分步阐述如下：(1)由于且，因此，从而进入步骤(2)；(2)利用算法InterfaceMatch算法得到从集合到集合O的接口匹配的解，即单射。为此，我们将输出间的接口匹配问题建模成二分图，如图3左侧所示，其中：,， 邓水光等:基于二分图匹配的语义Web服务发现方法1。由于，InterfaceMatch通过增加虚拟节点z以及三条权重为0的边，和，将二分图G转换成，如图3右侧所示。InterfaceMatch利用KM算法得到的最佳匹配，其权和为：。之后，InterfaceMatch将匹配M中覆盖虚拟节点的边去除而变为匹配，因此是所求的二分图G的扩展最佳匹配，从得到单射f，即和，由此得到；图3.二分图转换(1)依据操作的接口依赖关系得出输出集合所依赖的输入集合，即；(2)由于且，因此，进入步骤(5)；(3)利用算法InterfaceMatch得到从集合I'到集合I的接口匹配的解，即单射。如同步骤(2)，我们将输入间的接口匹配问题建模成求二分图的扩展最佳匹配问题。由于建模后的二分图满足条件，根据InterfaceMatch，直接使用KM算法求得二分图的扩展最佳匹配，最大权和值为：。由此，得到单射g，且、和；(4)根据公式(1)计算操作p与服务请求r之间的语义相似度，即：若用户请求的阀值小于等于0.84，则操作p与用户请求r成功匹配，即p是对r的一个匹配操作，则该操作所属的服务被返回给用户作为可选服务。对于一个服务s，若存在多个操作都与服务请求成功匹配，算法ServiceMatchmaking选择最佳匹配操作作为用户调用的目标操作。若对于某用户请求返回了多个服务，则选择最佳匹配操作的匹配相似度最大者为目标服务。值得注意的是，用户在选择最终调用的目标服务时，除了考虑语义相似度外，还可以综合服务质量等因素进行选取，基于服务质量等因素进行服务排序和选取将是我们今后的进一步工作，而国内外诸多研究成果为我们提供了很好的借鉴价值[11][12][14][15]。1仿真实验与结果分析本节从Web服务发现的召回率(RecallRate)、准确率(Precision)和可扩展性(Scalability)三个方面进行仿真实验。召回率是指从服务库中返回的满足用户请求的服务数占服务库中满足用户请求的服务总数的比例；准确率是指从服务库中返回的所有服务中，能满足用户请求的服务数占返回的所有服务数的比例。若对于某个用户请求，服务库中存在满足用户请求的服务数量为n，服务发现方法从该库中返回m个，但这m个中只有k真正满足用户请求，则该方法的召回率为k/n，而准确率为k/m。服务发现的可扩展性是指该方法在不同规模的服务库中的可用性，主要是指服务发现方法的速度。 邓水光等:基于二分图匹配的语义Web服务发现方法11.1实验准备由于缺乏统一的标准服务库，因此我们采用模拟程序自动生成服务构造服务库。而采用模拟程序构造服务库的一个好处在于可以设定不同的服务集合的参数。该模拟程序是基于IBMXMLGeneratorhttp://www.alphaworks.ibm.com/tech/xmlgenerator工具开发，依据服务注册信息的概念模型WSRM产生服务。我们从WordNet的概念库中选取一个具有200个词汇的子概念树作为服务接口语义标注的本体源。在生成每一个服务操作时，对该操作的每一个接口随机从200个词汇中选取一个词汇作为该接口对应的本体概念。在生成每一个服务请求时，我们从200个概念中随机选取2-5个作为用户提供的输入，从剩下的198-195个概念中选取2-3个作为用户期望的输出。我们采用JDK1.5实现基于二分图匹配的语义Web服务发现方法。仿真实验运行于IBMx60服务器上，软硬件配置为：2.0-GHzIntelXeonMP处理器；2G内存；Redhat9.0操作系统；MySQL5.0数据库。1.2实验结果与分析为分析基于二分图匹配的语义Web服务发现方法的召回率和准确率，同时分析局部依赖输出对Web服务发现效果的影响，我们选择课题组前期开发的未考虑局部依赖输出的服务发现方法[8]作为比较。我们生成如表1所示的5个服务库。我们在每一个服务库中提交10个不同的用户请求，设定用户请求阀值，计算出平均召回率和准确率，实验结果如图4所示。表1局部依赖输出比例不同的服务库服务库服务数量局部依赖输出比例()G-11000%G-210020%G-310060%G-410080%G-5100100%图4.局部依赖输出对服务发现的影响图4的结果表明，从第2至第5组实验中，考虑了局部依赖输出的服务发现方法的召回率和准确率均比未考虑局部依赖输出的服务发现方法有较明显的提高，其中召回率平均提高20%，准确率平均提高10%；而且提高的幅度随着服务集合中的局部依赖输出的比例的增长而提高，这是由于本文所提的方法在实施服务匹配的过程中，一方面考虑了接口依赖关系，从而提高了服务发现的召回率；二方面在基于二分图实施接口匹配过程中满足了单射匹配的要求，从而提供了服务发现的准确率。值得注意的是，在第1组试验中，两者的召回率基本相同，这是由于服务库G-1中不存在局部依赖输出，因此是否考虑接口依赖关系对于服务召回率影响较小；但准确率有所提高，这是由于本文方法考虑了单射匹配的要求，避免了接口匹配是多个接口匹配同一个接口的情况，从而提高了匹配的准确率。为分析基于二分图匹配的语义Web服务发现方法的可扩展性，我们生成如表2所示的6个不同规模的服务库，在每一个服务库中，我们分别提交3组服务请求(每组10个)，设定用户请求阀值分别为,和 邓水光等:基于二分图匹配的语义Web服务发现方法1，计算平均时间开销。实验结果如图5所示。表2不同规模的服务库服务库服务数量局部依赖输出比例()G-110020%G-220020%G-340020%G-460020%G-580020%G-6100020%图5.服务库规模对服务发现的性能影响图5的实验结果表明基于二分图匹配的语义Web服务发现方法的用户响应时间随着服务库中服务数量的增加而成线性增长，这与第3节中提出的服务与服务请求之间匹配算法的时间复杂度为常数是一致的。此外，实验结果也表明对于同样规模的服务库，用户阀值越大，用户响应时间越短。这是由于用户阀值越大，返回的无关或者无效服务越少，因此可以避免对这些服务的处理时间，从而提高了用户响应速度。以上两个实验结果表明了基于二分图匹配的语义Web服务发现不仅能提高服务发现的召回率和准确率，同时能在较短时间内为用户自动、快速返回可用的服务集合，从而较好的满足用户对于服务发现的需求.1相关工作当前，Web服务发现相关的研究成果层出不穷，而这些成果可以划分为两大类：基于关键字的Web服务发现和基于语义的Web服务发现。前者以UDDI为典型代表，由于仅支持关键词匹配，所以服务发现效果差；而后者则是在Web服务与语义网相结合产生的，并被学术界视为最有前景的服务发现方法。本文根据语义Web服务模型的不同，将语义Web服务发现方法大致分成如下三类，而鉴于篇幅有限，本节在每一类中仅介绍具有代表性的工作。(1)基于OWL-S/DAML-S的语义Web服务发现方法。其中最具代表性的工作是文献[3]提出的一个基于ServiceProfile的Web服务发现方法，该方法采用ServiceProfile描述用户请求，并将该描述与已注册Web服务的ServiceProfile进行匹配。匹配过程分为输出之间的匹配与输入之间的匹配。每一次匹配中，利用OWL所描述的本体知识，对服务的输入/输出概念与用户请求的输入/输出概念进行语义匹配。该方法开辟了基于DAML-S/OWL-S的服务发现方向，随后引起了众多研究人员在这一方向下展开服务发现研究，他们对OWL-S/DAML-S的ServiceProfile进行属性扩展(如QoS属性、信用属性)等，以提高服务发现效果，如文献[11][12]等。(2)基于WSMO/WSML的语义Web服务发现方法。其中最具代表性的工作是文献[18]提出的基于WSMO/WSML的Web服务发现框架，它分析了自动Web服务发现涵盖的主要概念问题之后，提出了在该框架下实施Web服务发现的概念模型，并且采用集合论实现用户目标与Web服务语义之间的匹配从而完成语义Web服务的发现。该框架奠定了基于WSMO/WSML的Web服务发现的基本过程和方法。文献[19]在该框架 邓水光等:基于二分图匹配的语义Web服务发现方法1模型的指导下，采用WSML和逻辑表达式对Web服务的行为知识和所操作的对象知识进行建模，并采用概念模型中基于集合论的匹配方法实施Web服务发现。(3)基于WSDL扩展的语义Web服务发现方法。其中最具代表性的工作包括：文献[9]提出了基于WSDL-S的语义Web服务发现方法，该方法从领域本体和领域无关本体两个角度进行服务匹配，并将两方面的匹配结果综合起来度量最终的服务匹配结果。文献[20]在WSDL基础上增加语义、功能和行为约束以及服务质量，提出轻量级Web服务描述语言QWSDL，针对现有匹配算法过多依赖逻辑推理和缺乏匹配灵活性，而构造相似函数度量服务相似的程度，将Web服务匹配问题转化成数值计算，进而提出了支持基本匹配、基调匹配和规约匹配的Web匹配模型。以上工作对基于语义的Web服务发现起到了重要的推动作用，而通过对已有工作进行分析，本文认为已有的语义Web服务模型因没有提供服务接口依赖的描述机制，在服务匹配的过程中没有考虑服务接口依赖关系，因此服务发现的效果存在提高的潜力，而本文工作则是对现有工作的一个重要补充和改进。相比本文工作，基于DAML-S/OWL-S和WSMO/WSML的语义Web服务发现方法实施难度较大，实现过程较为复杂，算法复杂度高；而基于WSDL-S、QWSDL等的语义Web服务发现方法要求服务描述本身符合WSDL-S或者QWSDL等模型，因此实际应用范围受限。1结束语高效的Web服务发现方法是推动Web服务技术进一步发展与应用的关键。本文工作可视为对其它基于语义的Web服务发现工作的重要补充和完善，其主要贡献包括：1)提出了Web服务注册信息模型WSRM，该模型不受限于特定的服务模型和表达语言，支持接口的语义标注和接口依赖关系的申明。2)提出了基于二分图匹配的语义Web服务发现方法，将服务接口的匹配问题转换成二分图的扩展最佳匹配问题，不仅考虑了局部依赖输出的特殊性，而且还满足接口匹配的单射要求，从而提高了服务发现的效果。仿真实验结果表明该方法不仅能提高服务发现的召回率和准确率，而且还能以线性时间复杂度满足用户请求。本文的将来工作主要集中于如何在服务发现过程中支持用户非功能性需求(如QoS)，而国内外已有的基于QoS的服务选取等相关研究成果[11][12][14][15]为开展这一方面的工作提供了较好的参考。References:[1]KunY,WangXL,ZhouAY.Underlyingtechniquesforwebservices:asurvey.JournalofSoftware,2004,15(3):428-442(inChinesewithEnglishabstract).[岳昆,王晓玲,周傲英.Web服务核心支撑技术:研究综述.软件学报,2004,15(3):428-442.][2]PapazoglouM,GeorgakopoulosD.Serviceorientedcomputing.CommunicationsoftheACM,2003,46(10):25-28.[3]PaolucciM,KawamuraT,PayneTR,SycaraK.SemanticmatchingofWebservicescapabilities.InternationalSemanticWebConference,p333-347,2002.[4]AliA,MajithiaS,RanaO,WalkerD.Reputation-basedsemanticservicediscovery.ConcurrencyandComputation:Practice&Experience,2006,18(8):817-826.[5]BrogiA,CorfiniS,PopescuR.Composition-orientedservicediscovery.InternationalConferenceonSoftwareComposition,p15-30,2005.[6]StollbergM,KellerU,FenselD.PartnerandservicediscoveryforcollaborationEstablishmentwithSemanticWebServices.InternationalConferenceonWebServices,p480,2005.[7]LiuZZ,WangHM,ZhouB.AtwolayeredP2Pmodelforsemanticservicediscovery.JournalofSoftware,2007,18(8):1922-1932.[刘志忠,王怀民,周斌.一种双层P2P结构的语义服务发现模型.软件学报.2007,18(8):1922-1932.][8]WuJ,WuZH,LiY,DengSG.Webservicediscoverybasedonontologyandsimilarityofword.ChineseJournalofComputers,2005,28(4):595-602(inChinesewithEnglishabstract).吴健,吴朝晖,李莹,邓水光.基于本体论和词汇语义相似度的Web服务发现.计算机学报,2005,28(4):595-602.[9]Syeda-MahmoodT,ShahG,AkkirajuT,IvanA.searchingservicerepositoriesbycombiningsemanticandontologicalmatching.InternationalConferenceonWebService.p13-20,2005. 邓水光等:基于二分图匹配的语义Web服务发现方法1[1]ChenDW,XuB,CaiYR,LiJZ.AP2Pbasedwebservicediscoverymechanismwithboundingdeploymentandpublication.ChineseJournalofComputers,2005,28(4):615-626(inChinesewithEnglishabstract)[陈德伟许斌蔡月茹李涓子.服务部署与发布绑定的基于P2P网络的Web服务发现机制.计算机学报,2005,28(4):615-626.][2]XuZ,MartinP,PowleyW,ZulkernineF.Reputation-EnhancedQoS-basedWebservicesdiscovery.InternationalConferenceonWebService.p249-256,2007.[3]WangX,VitvarT,KerriganM,TomaI.AQoS-awareselectionmodelforsemanticwebservices.The4thInternationalConferenceonService-OrientedComputing,p12-24,2006.[4]KüsterU,König-RiesB,SternM,KleinM.DIANE:anintegratedapproachtoautomatedservicediscovery,matchmakingandcomposition.InternationalConferenceonService-OrientedComputing,p1033-1042,2007.[5]YangSW,ShiML.AmodelforWebservicediscoverywithQoSconstraints.ChineseJournalofComputers,2005,28(4):589-594(inChinesewithEnglishabstract).[杨胜文,史美林.一种支持QoS约束的Web服务发现模型.计算机学报,2005,28(4):589-594.][6]ZhangCW,SuS,ChenJL.GeneticAlgorithmonWebServicesSelectionSupportingQoS.ChineseJournalofComputers,2005,29(7):1020-1028(inChinesewithEnglishabstract).[张成文苏森陈俊亮.基于遗传算法的QoS感知的Web服务选择.计算机学报,2005,29(7):1020-1028.][7]LovaszL,PlummerM.MatchingTheory.Amsterdam:North-Holland,1986.[8]PaliwalA,AdamN,BornhövdC.WebServiceDiscovery:AddingSemanticsthroughServiceRequestExpansionandLatentSemanticIndexing.InternationalConferenceonServicesComputing,p106-113,2007.[9]KellerU,LaraR,PolleresA.WSMOWebServiceDiscovery.2004.[10]StollbergM,KellerU,FenselD.PartnerandServiceDiscoveryforCollaborationEstablishmentwithSemanticWebServices.ProceedingsofIEEEInternationalConferenceonWebServices,p480,2005.[11]HuJQ,ZouP,WangHM,ZhouB.ResearchonWebservicedescriptionlanguageQWSDLandservicematchingmodel.ChineseJournalofComputers,2005,28(4):505-513(inChinesewithEnglishabstract).[胡建强,邹鹏,王怀民,周斌.Web服务描述语言QWSDL和服务匹配模型研究.计算机学报,2005.28(4).]AMethodofSemanticWebServiceDiscoverybasedonBipartiteGraphMatchingDENGShui-Guang,YINJian-Wei+,LIYing,WUJian,WuZhao-Hui(CollegeofComputerScienceandTechnology,ZhejiangUniversity,Hangzhou310027,China)Abstract:HowtodiscoverservicesforusersefficientlyisthekeyfortheapplicationoftheWebservicetechnology.Thecurrentsemantic-basedservicediscoverymethodsareofgreatinconveniencetobeusedandhavemuchpotentialimprovementfortheirperformance.Thispaperproposesaninformationmodelofregisteredservicesthatisn’tlimitedtospecificservicemodelsandlanguagesandsupportssemantic-annotationandinterface-dependencydeclaration.Then,amethodofservicediscoverybasedonbipartitegraphmatchingisproposedthattranslatestheservicematchmakingtotheproblemofextendedoptimalmatchingforbipartitegraph.Itenhancestherecallrateandprecisionasitconsiderstheinterfacedependencyrelationswithinaserviceinmatchmaking.Aserialofexperimentsillustratethemethodnotonlyimprovesitsefficiencymuch,butalsohasalinearcomplexityintimeconsumptiontofulfillusers’requests.Keywords:ServiceOrientedComputing,WebService,ServiceDiscovery,BipartiteGraphMatching 邓水光等:基于二分图匹配的语义Web服务发现方法1BackgroundService-OrientedComputing(SOC)isanewcomputingparadigmthatutilizesservicesasfundamentalelementstoconstructapplications.Itsupportsthedevelopmentofrapid,low-costandeasycompositionofdistributedapplicationseveninheterogeneousenvironmentsandalsoenablesenterprisestoflexiblysolveenterprise-wideandcross-enterpriseintegrationproblems.Theindustry’spromotionofWebservicesinSOAhaspromptedproviderstodevelopandpublishmanyWebservices,whichareusedinmanyareassuchasbusiness,financeandtourism.Asaresult,thenumberofservicespresentedontheopenInternetisgrowingatanexplosivespeed,whichsubsequentlybringsgreatchallengestotheaccurate,efficientandautomaticretrievaloftargetservicesforconsumers.Muchworkaspirestomeetthischallenge.Amongthoseefforts,SWS(SemanticWebService)isregardedasthemostpromisingtechnologytoretrieveservicesinanaccurateandautomaticway.However,mostoftheservicematchmakingalgorithmsassumethateachoutputfullydependsonalltheinputsinaservice.Inotherwords,itisimperativeforserviceconsumerstoprovidealltheinputsoftheserviceinordertogetevenoneoutputoftheservice.Accordingtothecurrentmatchmakingrules,aservicerequestmatchesaserviceadvertisementiftherequestprovidesalltheinputs(possiblymore)neededbytheadvertisementwhiletheadvertisementgeneratesalltheoutputs(possiblymore)neededbytherequester.Inotherwords,thesuccessfulmatchcriteriondemandstherequesttoprovidealltheinputsoftheadvertisedserviceinordertogetevenapartofoutputsoftheservice.Thisrequirementhasbeenwidelyacceptedbymostmatchmakingalgorithms.However,itistoostrictandcanleadtosomeunwantedsituations.Iftheyareused,somedeservedtargetservicesarenotreturnedonlybecausethenumberofeachservice’sinputislessthantheonespecifiedintheservicerequest,evenifotherinformationisthesame.Inordertoovercometheshortcomingofthecurrentmethods,inthispaper,weproposeaninformationmodelofregisteredservicesthatisn’tlimitedtospecificservicemodelsandlanguagesandsupportssemantic-annotationandinterface-dependencydeclaration.Then,weuseproposeamethodofservicediscoverybasedonbipartitegraphmatchingthattranslatestheservicematchmakingtotheproblemofextendedoptimalmatchingforbipartitegraph.Duringmatchmaking,weconsidertheinterfacedependencyrelationswithinaserviceinmatchmaking.Thesimulationsresultshowsthatthemethodhasbetterperformanceindecisionandrecallratethanothers. 邓水光等:基于二分图匹配的语义Web服务发现方法1作者简介邓水光，男，1979年生，博士后，讲师。2002年和2007分别于浙江大学获得学士学位和博士学位，目前的主要研究领域为流程管理和面向服务的计算。ShuiguangDengwasbornin1979.HereceivedtheBSandPhDinComputerSciencefromZhejiangUniversityin2002and2007,respectively.Atpresent,heisapost-docandlecturerintheCollegeofComputerScienceandTechnologyofZhejiangUniversity.HisresearchinterestincludesBusinessProcessManagement(BPM)andServiceOrientedComputing(SOC).尹建伟，男，1975年生，博士，副教授，主要研究领域为中间件技术。JianweiYinwasbornin1975.Atpresent,heisanassistantprofessorintheCollegeofComputerScienceandTechnologyofZhejiangUniversity.Hisresearchinterestismiddlewaretechnology.李莹，男，1973年生，博士，副教授，主要研究领域为软件体系架构和构件技术。YingLiwasbornin1973.Atpresent,heisanassistantprofessorintheCollegeofComputerScienceandTechnologyofZhejiangUniversity.Hisresearchinterestsincludesoftwaresystemarchitectureandcomponenttechnology.吴健，男，1976年生，博士，副教授，主要研究领域为Web服务、网格计算和数据挖掘。JianWuwasbornin1976.Atpresent,heisanassistantprofessorintheCollegeofComputerScienceandTechnologyofZhejiangUniversity.HisresearchinterestsareinSemanticWeb,WebService,andDataMining.吴朝晖，男，1966年生，博士，教授，博士生导师，主要研究领域为网格计算，嵌入式计算和普适计算。ZhaohuiWuwasbornin1966.Atpresent,hisisaprofessoranddoctoraladvisorintheCollegeofComputerScienceandTechnologyofZhejiangUniversity.Hisresearchinterestsincludegridcomputing,embeddedcomputingandpervasivecomputing.联系人邓水光，联系电话13588421105，Email：dengsg@zju.edu.cn。