基于WordNet和二分图的语义Web服务发现算法

1、技术创新微计算机信息(管控一体化2010年第26卷第8-3期360元/年邮局订阅号:82-946现场总线技术应用200例软件时空基于WordNet 和二分图的语义Web 服务发现算法Semantic Web service discovery Algorithm based on WordNet and bipartite graph(长沙理工大学华建新曹敦HUA Jian-xin CAO Dun摘要:由于Web 服务的描述参数都是有顺序的,而服务提供者和用户之间缺少对服务的共同语义描述约束,服务请求的描述参数都是无序的,它们之间不能直接进行匹配调用。本文在OWL-S 的基础上利用WordNe

2、t 计算参数的相似度,最后引入二分图来解决这一不对称匹配问题。实验结果表明本文算法有较好查准率和查全率,同时本文算法易于实现。关键词:Web 服务;服务发现;WordNet;二分图中图分类号:TP393文献标识码:AAbstract:Because the parameters which described of web services are in order,there exists the lack of a common semantic describ -ing constraints between providers and users of web services,Par

3、ameters which described of the request is disorderly,they can not be used directly matching others.This paper adopts WordNet to calculate the similarity of the parameters based on OWL-S and quotes bipartite graph to solve the problem of asymmetric matching in the end.The experimental results show th

4、at the precision ratio and re -call ratio of this algorithm is better than others and it is easy to implement this algorithm at the same time.Key words:Web Service;service discovery;WordNet;bipartite graph文章编号:1008-0570(201008-3-0198-03引言由于面向服务的体系结构(SOA能够提供更有效性和动态的应用,越来越多的分布、异构信息系统的开发和集成都采用了SOA 技术,而

5、Web 服务发现是SOA 非常重要的组成部分。随着Internet 上可用的Web 服务数量的增加,寻找一个适合的Web服务来满足服务请求者的要求变得越来越困难。如何方便有效地实现服务发现,成为SOA 所要解决的关键问题之一。当前Web 服务发现的主要是采用WSDL 和UDDI 技术,利用基于关键字的匹配方法,该方法在查全率和查准率上都不能够满足用户的需求。为了提高服务发现的查全率和查准率,研究人员在Web 服务的基础上结合语义Web 技术提出了基于语义的Web 服务发现。关于语义Web 服务发现已有不少研究成果,主要是利用Ontology 来描述Web 服务,然后通过这些带有语义信息的描述实

6、现Web 服务来实现服务的自动发现,调用和组装。虽然它们可以获得比较理想的查全率和查准率,但是这些方法实现难度高,对服务语义进行建模的代价大,同时由于服务提供者和用户之间缺少对服务的共同语义描述约束,Web 服务的描述参数都是有顺序的,而服务请求的描述参数都是无序的,它们之间的不对称性不能直接进行匹配调用。本文提出的不对称的语义Web 服务匹配算法是在OWL-S 的基础上利用WordNet 来计算本体之间的相似度,然后利用二分图来解决用户的请求服务与服务操作的不对称匹配问题,最后得到一组满足要求且按照与用户的请求服务的相似度降序排列的Web 服务,每个Web 服务的描述参数都与用户的请求参数一

7、一对应,为实现动态调用打下基础。1理论基础1.1OWL-S 简介OWL-S 是DARPA 组织在OWL 的基础上,构建出来的为Web 服务的发布者和请求者提供了统一的语义基础。在OWL-S 中对Web 服务描述的基本信息主要有三种本体:Service Pro -file 用来发布和发现服务;Service Model 用来对服务操作提供一个详细描述;Service Grounding 描述了服务间如何交互。Service Profile 本体主要描述服务和服务提供者的信息,包括服务提供者的信息、服务的功能信息、服务属性三个方面,其中服务的功能信息主要包括输入、输出、前置条件和效果(简称IOPE

8、。通过Service Profile 本体,服务提供者可以提供自己的服务说明,而服务查询代理可以通过服务提供的Service Profile 信息来判断是否满足服务请求者的需求。1.2二分图简介无向图G=(V,E,其中V 是顶点集,E 是边集,如果该图满足V=V 0V 1,V 0V 1=,且e=(x,yE,均有x V 0,y V 1,则称图G 为二分图。给定一个二分图G,M 为G 边集的一个子集,如果M 满足当中的任意两条边都不依附于同一个顶点,则称M 是一个匹配。如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。如果G 为加权二分图,则权值和最大的完备

9、匹配称为最优匹配。2语义Web 服务发现相关定义本文利用OWL-S 对Web 服务集和服务请求进行预处理,得到一个Profiles 文档,然后基于这些文档实现Web 服务匹配。本文主要是利用Service Profile 中的输入、输出、前置条件和效果(简称IOPE来进行匹配。定义1Web 服务ws 为一个四元组ws=I,O,P,E,其中I=i 1,i 2i n 是该服务的输入消息集合;O=o 1,o 2o n 是该服务的输出华建新:硕士基金项目:湖南省科技计划项目(2009SK4006198-邮局订阅号:82-946360元/年技术创新 软件时空PLC 技术应用200例您的论文得到两院院士关

10、注消息集合;P=p 1,p 2p n 是该服务的前置条件集合;E=e 1,e 2e n 该服务的效果集合。定义2服务请求r 为一个五元组来表示r=I r ,O r ,P r ,E r ,其中Ir =i r 1,i r 2i r m 是该服务请求的输入消息集合;Or =o r 1,o r2o r m是该服务请求的输出消息集合;Pr =p r 1,p r 2p r m是该服务请求的前置条件集合;Er =e r 1,e r 2e r m 该服务请求的效果集合;01是用户设定的阈值,即一个服务与服务请求的相似度大于等于阈值该服务才是匹配的。定义3Web 服务匹配。Web 服务IOPE 分为两类:前提(

11、IP和结果(OE。进行匹配时,用户请求的前提(I r P r 的参数包含Web 服务所需的前提(IP的参数,且Web 服务的结果(OE的参数包含了用户请求的结果(O r E r 的参数,且它们之间的相似度大于等于用户提供的阈值,则匹配成功。由定义3可知,用户请求的前提分量参数必须包含Web 服务的前提分量参数,用户请求的结果分量参数必须被包含于Web 服务的结果分量参数。现有的二分图不能很好解决这一问题,本文对二分图进行扩展,提出一个扩展最优匹配,定义如下:定义4扩展最优匹配。对于一个二分图G 和G 的一个匹配M,G 满足条件|V0|V1|,M 是G 的一个扩展最优匹配,当且仅当:1M 是覆盖

12、V0中所有节点;2M 是所有边的权值加和最大的匹配。3语义Web 服务匹配算法本文提出的匹配算法基本思想是:根据服务请求信息预处理服务请求信息,利用二分图来计算服务集每一个服务与服务请求之间的相似度,将相似度大于等于用户给定阈值的服务添加到结果列表,直到服务集全部匹配完毕,返回按相似度降序排列的结果列表。其流程见图1:图1服务匹配流程3.1概念相似度的计算WordNet 是一个英语字典。由于它包含了语义信息,所以有别于通常意义上的字典。WordNet 根据词条的意义将它们分组,每一个具有相同意义的字条组称为一个synset (同义词集合。WordNet 为每一个synset 提供了简短,概要的

13、定义,并记录不同synset 之间的语义关系。利用WordNet 计算两个元素的语义距离,进而得到它们的相似度。具体计算方法如下:Sim(w1,w2=1/(1+len(w1,w2(1其中len (w1,w2是词w1到w2的路径长度。Sim(w1,w20,1。3.2基于二分图的不对称匹配算法由定义1,对于Web 服务每一个分量,它都是由一组参数表示。由于用户无法感知Web 服务集中服务的每一个分量的参数构成次序,所以无法直接匹配,本文采用二分图技术来解决这种不对称本体之间的匹配。具体算法如下:(1如果|I|>|I r |、|P|>|P r |、|O r |>|O |、|E r

14、|>|E|中有一个成立,由定义3可知匹配不成功,返回;(2利用公式(1计算I=i 1,i 2i n 与Ir =i r 1,i r 2i r m 每个参数之间的相似度;(3初始化二分图G,其中V 0=I,V 1=I r ,边集E 就是I 与I r 的连线,边的权值就是它们之间的相似度;(4根据边的权值,求出G 的扩展最优匹配M 。(5求出M 中所有边的权值的平均值作为I 与Ir 的相似度。(6重复(2到(5求出P 与P r 的相似度。(7利用公式(1计算O=o 1,o 2o n 与Or =o r 1,o r 2o r m 每个参数之间的相似度;(8初始化二分图G,V 0=O r ,V 1=

15、O,边集E 就是O 与O r 的连线,边的权值就是它们之间的相似度;(9根据边的权值,求出G 的扩展最优匹配M 。(10求出M 中所有边的权值的平均值作为O 与O r 的相似度。(11重复(7到(10求出E 与E r 相似度。(12对4个分量相似度求平均,得到两个服务之间的相似度,如果相似度大于用户给的,该服务加入结果集。其中步骤4和9,求二分图最优匹配的经典算法是由Kuhn 和Munkres 独立提出的KM 算法,本文对二分图最优匹配进行了扩展,所以KM 也要做相应改进,算法步骤如下:(1如果|V 0|=|V 1|,则按照KM 算法来求解。(2如果|V 0|<|V 1|,则在V0增加|

16、V 1|-|V 0|个虚拟节点,V 0每增加一节点同时增加V 1中每一节点到该节点的边,边的权值为0。这样G 就转化为。(3按照KM 算法来求解的最优匹配。(4最后去掉刚刚增加的节点和边,把的最优匹配转化为G 的最优匹配。图2基于二分图的不对称匹配算法示意图a 初始建立的二分图b 最后得到的扩展最优匹配4实验结果为了验证文中提出的Web 服务匹配发现方法的有效性,我们用召回率和准确率作为度量Web 服务发现的指标,以评价其性能。召回率是指查询返回符合查询条件的Web 服务与测试样本集中符合查询条件的Web 服务的比率,准确率是指查询返回符合查询条件的Web 服务与查询返回Web 服务总数量的比

17、率。召回率和准确率越高,服务匹配算法越好。本文使用了以下4种开发工具来构建原型系统:Eclipse,199-技术创新微计算机信息(管控一体化2010年第26卷第8-3期360元/年邮局订阅号:82-946现场总线技术应用200例软件时空500个,与经典的argument UDDI Registry 系统进行仿真性能对比。实验结果见表1(表中AUDDIR 代表argument UDDI Reg -istry,Rec 代表召回率,Pre 代表准确率。结果表明本文的算法有比较好的召回率和准确率。表1实验结果统计5结论传统的基于XML 的服务描述语言缺乏对服务的语义描述,文中引入OWL-S 描述服务来

18、解决该问题,并提出一个不对称的语义Web 服务匹配算法。对服务的文本描述、功能描述和参数进行了匹配,最后对候选的服务发布进行排序,得到一组Web 服务描述参数都与用户的请求参数一一对应的Web 服务集,找出相似度最高的服务,从而实现服务的自动发现调用机制。文为Web 服务的动态调用打下基础;而且由于没用使用复杂的逻辑推理,易于编程实现。实验结果表明本文算法查准率和查全率要优于argument UDDI Registry,具有更大的应用范围。本文的下一步工作主要集中于如何在Web 服务发现过程中支持用户的非功能性需求(如QoS。本文创新点:提出了语义Web 服务匹配定义,利用扩展二分图来解决We

19、b 服务与服务请求的IOPE 描述参数不对称性,同时利用WordNet 来降低语义Web 服务建模复杂性。参考文献1岳昆,王晓玲,周傲英.Web 服务核心支撑技术:研究综述J.软件学报,2004,15(3:428-442.3PAOLUCCI M,KAWAMURA T,PAYNE T R,et a1.Importing the semantic Web in UDDIM.London:Springer-Verlag,2002:225-236.5Vaculin,R.;Sycara,K.Semantic Web Services Monitoring:An OWL -S Based Approach

20、 C.Hawaii International Conference on System Sciences,Proceedings of the 41st Annual 7-10Jan.2008Page(s:313313.6Ayse B.Bener,Volkan Ozadali,Erdem Savas Ilhan.Semantic matchmaker with precondition and effect matching using SWRLJ.Expert Systems with Applications,Volume 36,Issue 5,July 2009,Pages 9371-

21、9377.7Matthias Klusch,Benedikt Fries,Katia Sycara.OWLS -MX:A hybrid Semantic Web service matchmaker for OWL-S services.JWeb Semantics:Science,Services and Agents on the World Wide Web,Volume 7,Issue 2,April 2009,Pages 121-133.8钱雪忠,王创伟等.一种扩展Web 服务体系构架下的服务发现技术J.微计算机信息.2008,4-3:p170-172作者简介:华建新(1981-,男

22、,汉,湖南衡南人,硕士,主要研究方向为Web 服务;曹敦(1979-女,汉,湖南衡阳人,助教,主要研究方向:无线信道建模。Biography:HUA Jian -xin (1981-,Male (Han,Hunan Heng -nan,Maste,Special:Web Service.(410076湖南长沙长沙理工大学计算机与通信工程学院华建新曹敦(Institute of Computer and Communication Engineering;Changsha University of Science and Technology,Changsha 410076,ChinaHUA

23、Jian-xin CAO Dun通讯地址:(410076湖南长沙理工大学计算机与通信工程学院华建新(上接第171页连接强度和概念内涵的连接强度使得用户可以进行多条路径的选择,且当一条路径出现临时状况不可用时,可以选择其他路径来进行导航。利用本体对室内环境位置和用户需求的语义描述,以及本体描述的无二义性与逻辑推理的准确性,保证了室内导航的准确率和用户导航的满意度。参考文献1林敏,鲍煦等.改进Monte Carlo 算法用于RFID 标签的室内定位J.微计算机信息.2008,5-2:p203-2042Wille,R.Reconstructing lattice theory:an approach based on hi -erarchies of concepts.In:Rival,Ivan ed.Ordered Sets.Dordrecht -Boston:Reidel,1982:P445-4703Gander B,Wille R.Formal Concept Analysis M.Mathematical Foundations.Berlin:Springer,19994Antoniou,G.,&Harmelen,F.v.“A Semantic Web Primer ”.Massa-chusetts:The MIT Press,20045Gomez-Perez