基于松弛函數擴展的二分圖匹配服務發現算法

劉冰月，張 永

（大連東軟信息學院 計算機科學與技術系，遼寧 大連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.