基于松弛函數(shù)擴(kuò)展的二分圖匹配服務(wù)發(fā)現(xiàn)算法

劉冰月，張 永

（大連東軟信息學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，遼寧 大連116023）

0 引 言

傳統(tǒng)的Web服務(wù)注冊(cè)和發(fā)現(xiàn)算法是基于UDDI（universal discovery description and integration）協(xié)議的。UDDI這種基于關(guān)鍵字和簡(jiǎn)單分類(lèi)的服務(wù)發(fā)現(xiàn)機(jī)制是通過(guò)對(duì)用戶(hù)請(qǐng)求和服務(wù)注冊(cè)信息進(jìn)行精確匹配和服務(wù)發(fā)現(xiàn)，并不能很好地支持基于概率和語(yǔ)義約束的模糊匹配，因此也影響了服務(wù)調(diào)用的質(zhì)量和服務(wù)執(zhí)行的效果。另外，UDDI僅能在語(yǔ)法層次上描述服務(wù)，無(wú)法描述服務(wù)的語(yǔ)義信息，很多Web服務(wù)無(wú)法由計(jì)算機(jī)自動(dòng)進(jìn)行查找和匹配。因此，在Web服務(wù)發(fā)現(xiàn)過(guò)程中就存在服務(wù)發(fā)現(xiàn)不全、服務(wù)和請(qǐng)求的匹配度不高的問(wèn)題，語(yǔ)義Web服務(wù)發(fā)現(xiàn)算法則可以有效解決上述問(wèn)題。這是由于基于語(yǔ)義的Web服務(wù)使計(jì)算機(jī)能夠理解并描述Web 服務(wù)，并將之保存為可編程的實(shí)體，因此，計(jì)算機(jī)可以調(diào)用語(yǔ)義推理機(jī)來(lái)實(shí)現(xiàn)自動(dòng)的Web服務(wù)模糊匹配和執(zhí)行，從而提高Web服務(wù)發(fā)現(xiàn)的效率。

本文在前期的二分圖匹配語(yǔ)義Web服務(wù)發(fā)現(xiàn)算法研究的基礎(chǔ)上［1］，在該算法的匹配路徑的尋找上做了相應(yīng)改進(jìn)，引入了松弛函數(shù)值來(lái)擴(kuò)展等價(jià)子圖，以便能夠繼續(xù)尋找新的增廣路徑，進(jìn)而發(fā)現(xiàn)在匹配度閾值內(nèi)的更多服務(wù)，實(shí)現(xiàn)Web服務(wù)的自動(dòng)發(fā)現(xiàn)和匹配。

1 擴(kuò)展的二分圖匹配服務(wù)發(fā)現(xiàn)算法的研究

1.1 相關(guān)工作

目前，關(guān)于語(yǔ)義Web服務(wù)自動(dòng)發(fā)現(xiàn)的匹配算法［2－10］的相關(guān)研究工作描述如下。

在文獻(xiàn) ［2］中，根據(jù)基于本體的Web服務(wù)信任度計(jì)算模型來(lái)計(jì)算語(yǔ)義相似度。在文獻(xiàn) ［3］中，針對(duì)復(fù)雜參數(shù)匹配問(wèn)題，提出了一種基于二分圖匹配的算法。在文獻(xiàn)［4］中，使用OWL－S來(lái)提供語(yǔ)義支持，根據(jù)語(yǔ)義相似度將Web服務(wù)進(jìn)行聚類(lèi)的解決方法。在文獻(xiàn) ［5］中，提出了一種基于自適應(yīng)框架的Web服務(wù)選擇算法以及鏈接分析排序算法。在文獻(xiàn) ［6］中，提出了一種基于DL規(guī)則的Web服務(wù)組合方法。在文獻(xiàn) ［7］中，提出了一種利用模糊理論并通過(guò)定位粒子的位置來(lái)進(jìn)行語(yǔ)義Web服務(wù)發(fā)現(xiàn)的方法。在文獻(xiàn) ［8］中，提出了基于OWLS－S框架的自動(dòng)語(yǔ)義Web服務(wù)發(fā)現(xiàn)算法。在文獻(xiàn) ［9］中，提出了對(duì)現(xiàn)有的語(yǔ)義模糊匹配算法的擴(kuò)展算法。在文獻(xiàn) ［10］中，提出了基于Qos的服務(wù)選擇算法。

1.2 兩個(gè)概念間相似度的計(jì)算算法

這里，首先給出兩個(gè)本體概念間的相似度計(jì)算［11］公式，如式 （1）所示

其中，ir∈Ir，ip∈Ip，α是兩個(gè)本體概念間的語(yǔ)義距離，β是一個(gè)可變參數(shù)，相似度的計(jì)算結(jié)果在 ［0，1］區(qū)間內(nèi)。當(dāng)計(jì)算結(jié)果為1 時(shí)，則認(rèn)為這是兩個(gè)語(yǔ)義相同的本體概念；反之，則認(rèn)為兩個(gè)本體概念不滿足語(yǔ)義包含或相交關(guān)系。

接下來(lái)，給出用于計(jì)算兩個(gè)本體概念相似度的算法SimOntoCpt。

算法：SimOntoCpt

輸入：概念ir，ip以及可變參數(shù)β，其中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?。絥ull）｛

7. firEm＝Qset.remove（0）；

8. path＝PathMap.get（firEm）；

9. fors∈SynoSet（firEm）｛

10. PathMap.put（s，path）；

／／如果概念ip與概念s 屬于同義語(yǔ)義概念

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. ｝

這里首先初始化兩個(gè)集合Qset和Dset，其中，Qset用于保存待擴(kuò)展的節(jié)點(diǎn)，Dset用于保存已擴(kuò)展過(guò)的節(jié)點(diǎn)。使用PathMap做為保存概念路徑長(zhǎng)度的集合，將概念ir的路徑長(zhǎng)度初始化為0并存入PathMap，同時(shí)，也將概念ir添加到待擴(kuò)展節(jié)點(diǎn)集合Qset中。

然后，根據(jù)語(yǔ)義推理機(jī)獲取與待擴(kuò)展節(jié)點(diǎn)集合Qset中的第一個(gè)元素同義的所有概念集合SynoSet（firEm），并且循環(huán)遍歷其中的每一個(gè)元素。使用函數(shù)equal（）來(lái)檢查兩個(gè)概念是否屬于同一語(yǔ)義概念。如果是，則計(jì)算并且返回兩個(gè)概念之間的相似度值，這里使用式 （1）進(jìn)行概念相似度的計(jì)算。根據(jù)語(yǔ)義推理機(jī)獲取與集合Qset中的第一個(gè)元素有直接上、下位關(guān)系的所有概念集合HypoSet（firEm），并且循環(huán)遍歷其中的每一個(gè)元素。

如果某個(gè)HypoSet（firEm）中的元素在集合Qset和Dset中不存在，則將該元素添加到待擴(kuò)展集合Qset中。反之，如果HypoSet（firEm）中的元素已經(jīng)包含在Qset和Dset中，則對(duì)該元素不再繼續(xù)進(jìn)行擴(kuò)展。由于元素firEm屬于已擴(kuò)展過(guò)的節(jié)點(diǎn)，因此將它添加到已擴(kuò)展節(jié)點(diǎn)集合Dset中。

在算法SimOntoCpt中，將待擴(kuò)展的元素保存在集合Qset中，并且使用寬度優(yōu)先的方式從用戶(hù)請(qǐng)求輸入?yún)?shù)集合Ir中的某一概念ir出發(fā)開(kāi)始遍歷整個(gè)待擴(kuò)展節(jié)點(diǎn)集合，再?gòu)母拍頸r逐步擴(kuò)展到和其有直接上、下位關(guān)系的節(jié)點(diǎn)，直到遍歷的節(jié)點(diǎn)中包含已存在的Web服務(wù)的輸入?yún)?shù)ip為止。采用這種寬度優(yōu)先的搜索方式，能保證找的從概念ir到概念ip的路徑為本體中這兩個(gè)節(jié)點(diǎn)間的最短路徑。

另外，使用了已擴(kuò)展集合Dset，能夠保證由概念ir可達(dá)的節(jié)點(diǎn)僅會(huì)被擴(kuò)展一次，這樣就能保證算法最終是可終止的，并且也提高了算法的效率。

同樣的，計(jì)算輸出集合參數(shù)對(duì)應(yīng)概念的相似度時(shí)，向算法SimOntoCpt傳遞要計(jì)算相似度的兩個(gè)本體概念or，op以及可調(diào)節(jié)參數(shù)β，其中or∈Or，op∈Op。

1.3 基于二分圖的服務(wù)請(qǐng)求和服務(wù)操作的相似度計(jì)算

現(xiàn)階段，都是利用服務(wù)匹配來(lái)進(jìn)行Web服務(wù)發(fā)現(xiàn)的。也就是說(shuō)，通過(guò)匹配算法進(jìn)行用戶(hù)請(qǐng)求與注冊(cè)的服務(wù)信息的匹配，從而篩選出相應(yīng)的服務(wù)。

通常，通過(guò)判斷服務(wù)ws中是否存在某一個(gè)操作p，p與r的相似度值大于等于用戶(hù)設(shè)定的閾值θ，來(lái)判斷服務(wù)ws是否和請(qǐng)求r匹配。如果存在這樣的操作p，則認(rèn)為服務(wù)ws是與用戶(hù)請(qǐng)求r匹配的一個(gè)服務(wù)，而操作p稱(chēng)為服務(wù)ws與請(qǐng)求r匹配的一個(gè)操作。

定義1 用戶(hù)請(qǐng)求與服務(wù)操作匹配：假定服務(wù)ws中存在一個(gè)操作p＝ ｛n，d，I，O｝，用戶(hù)的服務(wù)請(qǐng)求r＝ ｛n，I，O，θ｝，若p與r之間的相似度Sim （p，r）≥θ，則稱(chēng)服務(wù)ws與用戶(hù)請(qǐng)求r匹配，并且，服務(wù)ws對(duì)請(qǐng)求r有一個(gè)匹配的操作p。

接下來(lái)，考慮計(jì)算服務(wù)操作輸入輸出參數(shù)集合和請(qǐng)求輸入輸出參數(shù)集合之間的相似度，給出算法Sim （p，r），用于計(jì)算用戶(hù)請(qǐng)求和服務(wù)之間的相似度。

算法：Sim

輸入：p，r

輸出：p和r的相似度值

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

2. return 0；

此處的a和b為計(jì)算相似度時(shí)輸出參數(shù)匹配和輸入?yún)?shù)匹配各自所占的權(quán)重系數(shù)，這里要求a＋b＝1，其值可以根據(jù)實(shí)際情況的需要進(jìn)行調(diào)整。

在Sim （p，r）算法中，將計(jì)算請(qǐng)求和服務(wù)相似度的問(wèn)題，轉(zhuǎn)換為二分圖最佳匹配求解問(wèn)題。也就是說(shuō)，使用二分圖G＝ （X，Y，E）對(duì)匹配問(wèn)題的輸入條件進(jìn)行建模。其中，集合X＝ ｛x1，x2，…，xn｝與集合Y＝ ｛y1，y2，…，ym｝（n≤m）對(duì)應(yīng)要進(jìn)行匹配的兩個(gè)本體概念集合Or、Op（或者Ir、Ip），對(duì)于x∈X，y∈Y，當(dāng)Sim （x，y）＞0時(shí)，就在x和y對(duì)應(yīng)的兩個(gè)頂點(diǎn)之間連一條邊＜x，y＞，并且設(shè)該條邊的權(quán)重Wxy為Sim （x，y），這樣構(gòu)成的邊集稱(chēng)為E。

但是，對(duì)于｜X｜≤｜Y｜的情況，經(jīng)典二分圖最佳匹配算法是不適用的，因此需要對(duì)二分圖最佳匹配算法進(jìn)行擴(kuò)展。

1.4 基于擴(kuò)展最佳匹配定義的二分圖匹配算法

下面給出對(duì)算法進(jìn)行擴(kuò)展后的擴(kuò)展最佳匹配的定義。

定義2 用戶(hù)請(qǐng)求與服務(wù)操作擴(kuò)展最佳匹配：對(duì)于一個(gè)帶權(quán)二分圖G＝ （X，Y，E），其中｜X｜≤｜Y｜，假定M 為G 的一個(gè)匹配。那么，當(dāng)且僅當(dāng)M 滿足以下兩個(gè)條件，則可以稱(chēng)M 為G 的一個(gè)擴(kuò)展的最佳匹配：

（1）當(dāng)｜X｜＝｜Y｜時(shí)，M 即為G 的最佳匹配。

（2）當(dāng)｜X｜＜｜Y｜時(shí)，M 是包含了集合X 中的所有節(jié)點(diǎn)并且使權(quán)和達(dá)到最大的一個(gè)匹配。

根據(jù)經(jīng)典的二分圖最佳匹配算法KM 給出改進(jìn)后的二分圖匹配算法BipartiteMatch。

算法：BipartiteMatch

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

輸出：M （M 是G 的一個(gè)擴(kuò)展最佳匹配）

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是位于當(dāng)前增廣路中的X’中的頂點(diǎn)集合

14. if（Xj∈S）

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

／／T 是位于當(dāng)前增廣路中的Y 中的頂點(diǎn)集合

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 ［］數(shù)組用于存放對(duì)應(yīng)于Y 集合中每個(gè)頂點(diǎn)的松弛函數(shù)值，在DFS（）函數(shù)中會(huì)對(duì)slack數(shù)組的值進(jìn)行調(diào)整，即slack ［n］＝min｛Lx［m］＋Ly［n］－w［m］［n］｝（m∈S，n∈Y）。

函數(shù)DFS （i）為匈牙利算法的深度優(yōu)先實(shí)現(xiàn)［12］，用于尋找圖G’的最大匹配M’，它的返回值表示是否存在以i為起點(diǎn)的增廣路徑。

在KM 算法中，通過(guò)建立G’的等價(jià)子圖，將尋找G’的最佳匹配轉(zhuǎn)化為尋找G’的最大匹配。即圖G’的等價(jià)子圖的最大匹配M’必為圖G’的最佳匹配。另外，集合S和集合T 在尋找以i為起點(diǎn)的增廣路徑的過(guò)程中，會(huì)隨時(shí)進(jìn)行調(diào)整。

當(dāng)找不到以i為起點(diǎn)的增廣路徑時(shí)，將利用松弛函數(shù)值來(lái)修改圖G’中各頂點(diǎn)的頂標(biāo)Lx和Ly的值，這樣，可以給等價(jià)子圖加入一些新的邊，并且不影響現(xiàn)有的等價(jià)子圖，從而使得算法可以繼續(xù)尋找以i為起點(diǎn)的增廣路徑，直到找到為止。

改進(jìn)后的算法的時(shí)間復(fù)雜性為O （m×2n3），其中m是Web服務(wù)中操作的個(gè)數(shù)，n是輸入集合或輸出集合的參數(shù)個(gè)數(shù)。

2 應(yīng)用實(shí)例與實(shí)驗(yàn)結(jié)果分析

本節(jié)將使用本文算法和之前未優(yōu)化的算法［13］進(jìn)行Web服務(wù)發(fā)現(xiàn)的仿真實(shí)驗(yàn)，以驗(yàn)證本算法的執(zhí)行效率。

這里從WordNet加載一組本體概念，并和實(shí)驗(yàn)中生成的包含100個(gè)Web服務(wù)操作的服務(wù)庫(kù)進(jìn)行匹配，在其中查找10個(gè)與給定的用戶(hù)請(qǐng)求相匹配的服務(wù)，一共將進(jìn)行10＊100＝1000次的Web服務(wù)匹配，計(jì)算兩種算法的平均查全率和查準(zhǔn)率。在這里，設(shè)置用戶(hù)請(qǐng)求閾值θ＝0.9。

從圖1中可以看出，當(dāng)Web服務(wù)操作的參數(shù)集合大小與用戶(hù)請(qǐng)求的參數(shù)集合大小相同時(shí)，兩種算法的查全率是相同的。但是當(dāng)參數(shù)個(gè)數(shù)離差增加時(shí)，擴(kuò)展后的二分圖匹配的Web服務(wù)發(fā)現(xiàn)算法的查全率基本不受影響，而未優(yōu)化的二分圖匹配的Web服務(wù)發(fā)現(xiàn)算法的查全率則急劇下降。相應(yīng)的，對(duì)于查準(zhǔn)率的實(shí)驗(yàn)結(jié)果也顯示，本文算法基本不受參數(shù)集合差別的影響。

3 結(jié)束語(yǔ)

由于現(xiàn)有的Web服務(wù)標(biāo)準(zhǔn)及協(xié)議無(wú)法準(zhǔn)確的表達(dá)Web服務(wù)的語(yǔ)義信息，因此，在Web服務(wù)動(dòng)態(tài)發(fā)現(xiàn)的能力方面有所欠缺，尤其當(dāng)服務(wù)與請(qǐng)求的參數(shù)集合的離差增加時(shí)，算法的查全率和查準(zhǔn)率受影響很大。本文提出了一種擴(kuò)展的二分圖匹配Web服務(wù)發(fā)現(xiàn)算法，實(shí)驗(yàn)結(jié)果表明，它比之前未引入松弛函數(shù)進(jìn)行優(yōu)化前的算法提高了服務(wù)的查全率和查準(zhǔn)率。本文下一步的工作將是研究如何進(jìn)行基于語(yǔ)義的Web服務(wù)的自動(dòng)發(fā)現(xiàn)和執(zhí)行，以及如何實(shí)現(xiàn)支持Qos約束的Web服務(wù)模糊匹配算法。

圖1 與未優(yōu)化前的算法的查全率和查準(zhǔn)率對(duì)比

［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）. ［王睿，吳禮發(fā)，張婷婷，等.一種基于本體的Web服務(wù)信任度計(jì)算模型 ［J］.計(jì)算機(jī)應(yīng)用研究，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）.［王義錦，趙耀.用二分圖實(shí)現(xiàn)復(fù)雜參數(shù)類(lèi)型匹配 ［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）. ［袁玉倩，胡曉惠，楊潔.一種基于自適應(yīng)框架的Web 服務(wù)選擇算法［J］.計(jì)算機(jī)工程，2012，38 （2）：11－13.］

［5］ZHANG Jingyu，YU Xueli，F(xiàn)U Fengke.Semantic Web service discovery with clustering ［J］.Computer Engineering and Applications，2009，45 （34）：139－143 （in Chinese）.［張景雨，余雪麗，付豐科.利用聚類(lèi)優(yōu)化語(yǔ)義Web服務(wù)發(fā)現(xiàn)［J］.計(jì)算機(jī)工程與應(yīng)用，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）.［劉思培，劉大有，齊紅，等.基于描述邏輯規(guī)則的語(yǔ)義Web 服務(wù)組合 ［J］.計(jì)算機(jī)研究與發(fā)展，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和模糊粒子群優(yōu)化的語(yǔ)義Web服務(wù)發(fā)現(xiàn) ［J］.計(jì)算機(jī)應(yīng)用，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）.［李禎，楊放春，蘇森.基于模糊多屬性決策理論的語(yǔ)義Web服務(wù)組合算法 ［J］.軟件學(xué)報(bào)，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）.［劉宏哲，須德.基于本體的語(yǔ)義相似度和相關(guān)度計(jì)算研究綜述 ［J］.計(jì)算機(jī)科學(xué)，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.