基于松弛函数扩展的二分图匹配服务发现算法

刘冰月，张 永

（大连东软信息学院 计算机科学与技术系，辽宁 大连116023）

0 引 言

传统的Web服务注册和发现算法是基于UDDI（universal discovery description and integration）协议的。UDDI这种基于关键字和简单分类的服务发现机制是通过对用户请求和服务注册信息进行精确匹配和服务发现，并不能很好地支持基于概率和语义约束的模糊匹配，因此也影响了服务调用的质量和服务执行的效果。另外，UDDI仅能在语法层次上描述服务，无法描述服务的语义信息，很多Web服务无法由计算机自动进行查找和匹配。因此，在Web服务发现过程中就存在服务发现不全、服务和请求的匹配度不高的问题，语义Web服务发现算法则可以有效解决上述问题。这是由于基于语义的Web服务使计算机能够理解并描述Web 服务，并将之保存为可编程的实体，因此，计算机可以调用语义推理机来实现自动的Web服务模糊匹配和执行，从而提高Web服务发现的效率。

本文在前期的二分图匹配语义Web服务发现算法研究的基础上［1］，在该算法的匹配路径的寻找上做了相应改进，引入了松弛函数值来扩展等价子图，以便能够继续寻找新的增广路径，进而发现在匹配度阈值内的更多服务，实现Web服务的自动发现和匹配。

1 扩展的二分图匹配服务发现算法的研究

1.1 相关工作

目前，关于语义Web服务自动发现的匹配算法［2－10］的相关研究工作描述如下。

在文献 ［2］中，根据基于本体的Web服务信任度计算模型来计算语义相似度。在文献 ［3］中，针对复杂参数匹配问题，提出了一种基于二分图匹配的算法。在文献［4］中，使用OWL－S来提供语义支持，根据语义相似度将Web服务进行聚类的解决方法。在文献 ［5］中，提出了一种基于自适应框架的Web服务选择算法以及链接分析排序算法。在文献 ［6］中，提出了一种基于DL规则的Web服务组合方法。在文献 ［7］中，提出了一种利用模糊理论并通过定位粒子的位置来进行语义Web服务发现的方法。在文献 ［8］中，提出了基于OWLS－S框架的自动语义Web服务发现算法。在文献 ［9］中，提出了对现有的语义模糊匹配算法的扩展算法。在文献 ［10］中，提出了基于Qos的服务选择算法。

1.2 两个概念间相似度的计算算法

这里，首先给出两个本体概念间的相似度计算［11］公式，如式 （1）所示

其中，ir∈Ir，ip∈Ip，α是两个本体概念间的语义距离，β是一个可变参数，相似度的计算结果在 ［0，1］区间内。当计算结果为1 时，则认为这是两个语义相同的本体概念；反之，则认为两个本体概念不满足语义包含或相交关系。

接下来，给出用于计算两个本体概念相似度的算法SimOntoCpt。

算法：SimOntoCpt

输入：概念ir，ip以及可变参数β，其中ir∈Ir，ip∈Ip

输出：概念ir，ip之间的相似度

1. Qset＝null；

2. Dset＝null；

3. PathMap＝null；

4. PathMap.put（ir，0）；

5. Qset.add （ir）；

6. while（Qset！＝null）｛

7. firEm＝Qset.remove（0）；

8. path＝PathMap.get（firEm）；

9. fors∈SynoSet（firEm）｛

10. PathMap.put（s，path）；

／／如果概念ip与概念s 属于同义语义概念

11. if（equal（ip，s））

12. returnβ／ （PathMap.get（s）＋β）；

13. ｝

14. forh∈HypoSet（firEm）｛

15. PathMap.put（h，path＋1）；

16. if（equal（ip，h））

17. returnβ／ （PathMap.get（h）＋β）；

18. if（h∈Qset∪Dset）

19. continue；

20. else

21. Qset.add （h）；

22. ｝

23. Dset.add （firEm）；

24. ｝

这里首先初始化两个集合Qset和Dset，其中，Qset用于保存待扩展的节点，Dset用于保存已扩展过的节点。使用PathMap做为保存概念路径长度的集合，将概念ir的路径长度初始化为0并存入PathMap，同时，也将概念ir添加到待扩展节点集合Qset中。

然后，根据语义推理机获取与待扩展节点集合Qset中的第一个元素同义的所有概念集合SynoSet（firEm），并且循环遍历其中的每一个元素。使用函数equal（）来检查两个概念是否属于同一语义概念。如果是，则计算并且返回两个概念之间的相似度值，这里使用式 （1）进行概念相似度的计算。根据语义推理机获取与集合Qset中的第一个元素有直接上、下位关系的所有概念集合HypoSet（firEm），并且循环遍历其中的每一个元素。

如果某个HypoSet（firEm）中的元素在集合Qset和Dset中不存在，则将该元素添加到待扩展集合Qset中。反之，如果HypoSet（firEm）中的元素已经包含在Qset和Dset中，则对该元素不再继续进行扩展。由于元素firEm属于已扩展过的节点，因此将它添加到已扩展节点集合Dset中。

在算法SimOntoCpt中，将待扩展的元素保存在集合Qset中，并且使用宽度优先的方式从用户请求输入参数集合Ir中的某一概念ir出发开始遍历整个待扩展节点集合，再从概念ir逐步扩展到和其有直接上、下位关系的节点，直到遍历的节点中包含已存在的Web服务的输入参数ip为止。采用这种宽度优先的搜索方式，能保证找的从概念ir到概念ip的路径为本体中这两个节点间的最短路径。

另外，使用了已扩展集合Dset，能够保证由概念ir可达的节点仅会被扩展一次，这样就能保证算法最终是可终止的，并且也提高了算法的效率。

同样的，计算输出集合参数对应概念的相似度时，向算法SimOntoCpt传递要计算相似度的两个本体概念or，op以及可调节参数β，其中or∈Or，op∈Op。

1.3 基于二分图的服务请求和服务操作的相似度计算

现阶段，都是利用服务匹配来进行Web服务发现的。也就是说，通过匹配算法进行用户请求与注册的服务信息的匹配，从而筛选出相应的服务。

通常，通过判断服务ws中是否存在某一个操作p，p与r的相似度值大于等于用户设定的阈值θ，来判断服务ws是否和请求r匹配。如果存在这样的操作p，则认为服务ws是与用户请求r匹配的一个服务，而操作p称为服务ws与请求r匹配的一个操作。

定义1 用户请求与服务操作匹配：假定服务ws中存在一个操作p＝ ｛n，d，I，O｝，用户的服务请求r＝ ｛n，I，O，θ｝，若p与r之间的相似度Sim （p，r）≥θ，则称服务ws与用户请求r匹配，并且，服务ws对请求r有一个匹配的操作p。

接下来，考虑计算服务操作输入输出参数集合和请求输入输出参数集合之间的相似度，给出算法Sim （p，r），用于计算用户请求和服务之间的相似度。

算法：Sim

输入：p，r

输出：p和r的相似度值

1.if（｜Or｜＞｜Op｜ ｜Ir｜＜｜Ip｜）

2. return 0；

此处的a和b为计算相似度时输出参数匹配和输入参数匹配各自所占的权重系数，这里要求a＋b＝1，其值可以根据实际情况的需要进行调整。

在Sim （p，r）算法中，将计算请求和服务相似度的问题，转换为二分图最佳匹配求解问题。也就是说，使用二分图G＝ （X，Y，E）对匹配问题的输入条件进行建模。其中，集合X＝ ｛x1，x2，…，xn｝与集合Y＝ ｛y1，y2，…，ym｝（n≤m）对应要进行匹配的两个本体概念集合Or、Op（或者Ir、Ip），对于x∈X，y∈Y，当Sim （x，y）＞0时，就在x和y对应的两个顶点之间连一条边＜x，y＞，并且设该条边的权重Wxy为Sim （x，y），这样构成的边集称为E。

但是，对于｜X｜≤｜Y｜的情况，经典二分图最佳匹配算法是不适用的，因此需要对二分图最佳匹配算法进行扩展。

1.4 基于扩展最佳匹配定义的二分图匹配算法

下面给出对算法进行扩展后的扩展最佳匹配的定义。

定义2 用户请求与服务操作扩展最佳匹配：对于一个带权二分图G＝ （X，Y，E），其中｜X｜≤｜Y｜，假定M 为G 的一个匹配。那么，当且仅当M 满足以下两个条件，则可以称M 为G 的一个扩展的最佳匹配：

（1）当｜X｜＝｜Y｜时，M 即为G 的最佳匹配。

（2）当｜X｜＜｜Y｜时，M 是包含了集合X 中的所有节点并且使权和达到最大的一个匹配。

根据经典的二分图最佳匹配算法KM 给出改进后的二分图匹配算法BipartiteMatch。

算法：BipartiteMatch

输入：G＝ （X，Y，E），其中｜X｜≤｜Y｜

输出：M （M 是G 的一个扩展最佳匹配）

1. if（｜X｜＜｜Y｜）｛

2. transform：G （X，Y，E）→G’（X’，Y，E’）

／／其中X’＝X∪Z，Z＝ ｛z1，z2，…，zk｝ （k＝－ X ）／／and E’＝E∪ ｛＜zi，yj＞｜1≤i≤｜Z｜，1≤j≤｜Y｜，／／Wziyj＝0｝

3. ｝

4. w ［i］ ［j］＝SimOntoCpt（i，j）； （i∈X’，j∈Y）

5. Lx［i］＝max ｛w ［i］［j］｝；

Ly［j］＝0；（i∈X’，j∈Y）

6. fori∈X’｛

7. for（j＝0；j＜｜X’｜；j＋＋）

8. slack ［j］＝INF；

9. while（true）｛

10. if（DFS （i））

11. break；

12. delta＝min ｛slack ［j］｝；（0≤j≤｜Y｜，YjT）

13. for（j＝0；j＜｜X’｜；j＋＋）｛

／／S是位于当前增广路中的X’中的顶点集合

14. if（Xj∈S）

15. Lx［j］＝Lx［j］－delta；

／／T 是位于当前增广路中的Y 中的顶点集合

16. if（Yj∈T）

17. Ly［j］＝Ly［j］＋delta；

18. else

19. slack ［j］＝slack ［j］－delta；

20. ｝

21. ｝

22. ｝

23. if（｜X｜＜｜Y｜）｛

／／M 是M’去掉集合E’’＝ ｛＜zi，yj＞｜zi∈Z｝并且

／／M’是G’的最佳匹配

24. transform：M’→M

25. ｝

26. return M；

此算法中使用了slack ［］数组用于存放对应于Y 集合中每个顶点的松弛函数值，在DFS（）函数中会对slack数组的值进行调整，即slack ［n］＝min｛Lx［m］＋Ly［n］－w［m］［n］｝（m∈S，n∈Y）。

函数DFS （i）为匈牙利算法的深度优先实现［12］，用于寻找图G’的最大匹配M’，它的返回值表示是否存在以i为起点的增广路径。

在KM 算法中，通过建立G’的等价子图，将寻找G’的最佳匹配转化为寻找G’的最大匹配。即图G’的等价子图的最大匹配M’必为图G’的最佳匹配。另外，集合S和集合T 在寻找以i为起点的增广路径的过程中，会随时进行调整。

当找不到以i为起点的增广路径时，将利用松弛函数值来修改图G’中各顶点的顶标Lx和Ly的值，这样，可以给等价子图加入一些新的边，并且不影响现有的等价子图，从而使得算法可以继续寻找以i为起点的增广路径，直到找到为止。

改进后的算法的时间复杂性为O （m×2n3），其中m是Web服务中操作的个数，n是输入集合或输出集合的参数个数。

2 应用实例与实验结果分析

本节将使用本文算法和之前未优化的算法［13］进行Web服务发现的仿真实验，以验证本算法的执行效率。

这里从WordNet加载一组本体概念，并和实验中生成的包含100个Web服务操作的服务库进行匹配，在其中查找10个与给定的用户请求相匹配的服务，一共将进行10＊100＝1000次的Web服务匹配，计算两种算法的平均查全率和查准率。在这里，设置用户请求阈值θ＝0.9。

从图1中可以看出，当Web服务操作的参数集合大小与用户请求的参数集合大小相同时，两种算法的查全率是相同的。但是当参数个数离差增加时，扩展后的二分图匹配的Web服务发现算法的查全率基本不受影响，而未优化的二分图匹配的Web服务发现算法的查全率则急剧下降。相应的，对于查准率的实验结果也显示，本文算法基本不受参数集合差别的影响。

3 结束语

由于现有的Web服务标准及协议无法准确的表达Web服务的语义信息，因此，在Web服务动态发现的能力方面有所欠缺，尤其当服务与请求的参数集合的离差增加时，算法的查全率和查准率受影响很大。本文提出了一种扩展的二分图匹配Web服务发现算法，实验结果表明，它比之前未引入松弛函数进行优化前的算法提高了服务的查全率和查准率。本文下一步的工作将是研究如何进行基于语义的Web服务的自动发现和执行，以及如何实现支持Qos约束的Web服务模糊匹配算法。

图1 与未优化前的算法的查全率和查准率对比

［1］Zhang Yang，Liu Bingyue，Wang Hong.Automatic matchmaking of Web services ［J］.Journal of Theoretical and Applied Electronic Commerce Research，2009，4 （2）：32－36.

［2］WANG Rui，WU Lifa，ZHANG Tingting，et al.Trust computation model based on ontology for Web service［J］.Application Research of Computers，2013，30 （7）：2077－2081 （in Chinese）. ［王睿，吴礼发，张婷婷，等.一种基于本体的Web服务信任度计算模型 ［J］.计算机应用研究，2013，30（7）：2077－2081.］

［3］WANG Yijin，ZHAO Yao.Complex parameter types matching based on bipartite graph ［J］.Software，2012，33 （11）：198－201 （in Chinese）.［王义锦，赵耀.用二分图实现复杂参数类型匹配 ［J］.软件，2012，33 （11）：198－201.］

［4］YUAN Yuqian，HU Xiaohui，YANG Jie.Web service selection algorithm based on adaptive framework ［J］.Computer Engineering，2012，38 （2）：11－13 （in Chinese）. ［袁玉倩，胡晓惠，杨洁.一种基于自适应框架的Web 服务选择算法［J］.计算机工程，2012，38 （2）：11－13.］

［5］ZHANG Jingyu，YU Xueli，FU Fengke.Semantic Web service discovery with clustering ［J］.Computer Engineering and Applications，2009，45 （34）：139－143 （in Chinese）.［张景雨，余雪丽，付丰科.利用聚类优化语义Web服务发现［J］.计算机工程与应用，2009，45 （34）：139－143.］

［6］LIU Sipei，LIU Dayou，QI Hong，et al.Composing semantic Web service with description logic rules［J］.Journal of Computer Research and Development，2011，48 （5）：831－840 （in Chinese）.［刘思培，刘大有，齐红，等.基于描述逻辑规则的语义Web 服务组合 ［J］.计算机研究与发展，2011，48（5）：831－840.］

［7］LI Shuyu.New semantic Web service discovery approach based on QoS and fuzzy particle swarm optimization ［J］.Journal of Computer Applications，2012，32 （5）：1347－1350 （in Chinese）.［李蜀瑜.基于QoS和模糊粒子群优化的语义Web服务发现 ［J］.计算机应用，2012，32 （5）：1347－1350.］

［8］Meditskos，Georgios.Structural and role－oriented Web service discovery with taxonomies in OWL－S ［J］.IEEE Transactions on Knowledge and Data Engineering，2010，22 （2）：203－205.

［9］LI Zhen，YANG Fangchun，SU Sen.Fuzzy multi－attribute decision making－based algorithm for semantic Web service composition ［J］.Journal of Software，2009，20 （3）：583－596（in Chinese）.［李祯，杨放春，苏森.基于模糊多属性决策理论的语义Web服务组合算法 ［J］.软件学报，2009，20 （3）：583－596.］

［10］Beniamino Di Martino.Semantic Web services discovery based on structural ontology matching ［J］.International Journal of Web and Grid Services，2009，5 （1）：46－65.

［11］LIU Hongzhe，XU De.Ontology based semantic similarity and relatedness measures review ［J］.Computer Science，2012，39 （2）：8－13 （in Chinese）.［刘宏哲，须德.基于本体的语义相似度和相关度计算研究综述 ［J］.计算机科学，2012，39 （2）：8－13.］

［12］Dossey JA.Discrete Mathematics［M］.Mechanical Industry Press，2007.

［13］Liu Bingyue.The improvement of the method of semantic Web service discovery based on bipartite graph matching ［J］.Recent Advances in Computer Science and Information Engineering，2012，3 （1）：99－104.