利用匹配關系圖的Web服務發現方法

張 進，傅秀芬

（廣東工業大學 計算機學院，廣東 廣州510006）

0 引 言

為避免和相似度低的Web服務進行比較，縮小服務的檢索空間，一些學者提出服務聚類的思想［1－10］，將功能相似的服務聚合成類，以增大服務定位的粒度。文獻 ［3］提出語義Web服務聚類方法，將語義功能屬性賦予不同權值，根據其語義相似度進行聚類，有效地減少服務查找的空間；文獻 ［4］利用本體概念間的關系來生成服務的加權圖，并采用圖論聚類的方法對Web服務進行聚類，簡化聚類的計算過程；文獻 ［5］綜合考慮Web服務的功能性參數，采用改進的模糊聚類算法對Web服務進行模糊聚類，有效地提高聚類的精準度。上述研究通過對Web服務進行聚類，提高服務發現的效率，但通過對現有文獻的分析，發現目前基于服務聚類的服務發現方法仍存在如下兩方面的不足：①只注重聚類算法的分析，很少給出具體的服務發現方法：文獻 ［6］利用BIRCH 聚類思想進行用戶情境聚類，提高聚類的準確性，但沒有將服務簇作為一個整體，也沒有給出具體的服務發現方法。②針對具體的服務簇進行服務發現時，將服務請求與簇中的Web服務逐一進行比較，沒有利用簇中Web服務的共性：文獻 ［7］從功能相似和過程相似兩個層面進行服務聚類和服務發現，提高服務發現效率，但在特定的服務簇中進行匹配時，其將所有Web服務依次取出進行比較，制約了發現效率的進一步提高。

針對上述問題，本文定義了簇中Web 服務的匹配關系，并提出一種利用匹配關系圖的服務發現方法。首先利用功能需求的匹配條件定義了同簇中的Web 服務匹配關系，并生成了服務簇的匹配關系圖。當在具體的服務簇中進行服務發現時，通過遍歷匹配關系圖，把多個滿足服務請求功能需求的Web服務加入到候選服務集合中，減少服務匹配的次數，提高服務發現的效率。

1 基本概念

語義Web服務是一種運行在Web上自包含、可調用的應用程序，其采用對領域知識抽象描述的本體進行標注，使服務描述帶有語義［11］。

定義1 Web服務。Web服務是對功能屬性的抽象化描述，可以形式化定義為4 元組WS ＝ （Wid，Wdes，I，O），其中：

（1）Wid是Web服務的名稱，用來唯一標識一個服務。

（2）Wdes是Web服務的功能描述，由多個領域本體標注的概念組成。

（3）I＝ ｛i1，i2，…｝是Web服務輸入參數集，其中每個輸入參數in都用領域本體進行標注。

（4）O＝ ｛o1，o2，…｝是Web服務輸出參數集，其中每個輸出參數on都用領域本體進行標注。

定義2 服務請求。服務請求可形式化定義為三元組WSR＝ ｛WRdes，IR，OR｝，其中：

（1）WRdes是服務請求的功能描述，由多個領域本體標注的概念組成。

（2）IR＝ ｛ir1，ir2，…｝是服務請求的輸入參數集，其中每個輸入參數irn都用領域本體進行標注。

（3）OR＝ ｛or1，or2，…｝是服務請求的輸出參數集，其中每個輸出參數orn都用領域本體進行標注。

服務簇是通過對服務注冊庫中Web服務進行聚類預處理形成的Web服務集合，具有同簇之間高度相似、不同簇之間高度相異的特點［12，13］，其具體定義如下：

定義3 服務簇。將Web服務集S＝ ｛s1，s2，…，sn｝進行聚類操作，獲得多個聚類簇，每個聚類簇則表示一個服務簇。

通過服務簇，可以避免與相關性小或者不相關的服務進行匹配，有效地減少服務發現的檢索空間。當前對于服務簇生成算法已經有了許多的研究，可以直接利用其中提出的一些聚類算法。由于本文是在服務簇基礎之上進行研究，不同的聚類算法，并不會產生影響。

2 Web服務匹配關系及匹配關系圖

服務簇中的Web服務功能高度相似，但現有基于聚類的服務發現方法并沒有利用簇中Web服務存在共性，而是把它當作獨立的個體與服務請求進行逐一的比較。本文利用服務請求與Web服務在功能需求上的匹配條件來定義了簇中Web服務自身存在的關系，并對其進行圖形化建模以便于統一管理。

2.1 Web服務匹配關系

服務請求與Web服務在功能需求上匹配須滿足如下3個條件［7，8］：①Web服務的功能描述與服務請求的功能需求相近或者相同；②Web服務的輸入參數須由服務請求提供，即服務請求須滿足Web服務正常運轉所需參數；③服務請求的輸出參數須由Web服務提供，即服務請求者所需的功能結果可通過調用Web服務來獲得。Web服務與服務請求只是服務的不同描述方式，形式化定義類似，因此可利用服務請求與Web服務的功能需求匹配條件，來定義同簇中的Web服務之間的匹配關系。

服務簇中的Web服務功能相同或者高度相似，因此同簇中的Web服務均滿足匹配的第一個條件，對其進行匹配判斷時，則只需滿足匹配的其余兩個條件。Web服務的輸入輸出功能屬性是由本體標注的參數集組成，可通過其參數的兼容關系來進行匹配判斷［7］。

定義4 概念相容性。在本體樹中，概念M 相容于概念N，記為M N，須滿足如下條件：

（1）M 與N 同義，或者；

（2）M 是N 的一個子類。

參數不僅包含一個概念描述，而且還含有一個數據類型屬性，所以在比較兩個參數的語義關系時，不僅要比較參數概念的相容性，還要比較參數類型的相容性。

定義5 參數兼容關系。參數A 兼容于參數B，記為A→B，當且僅當：

（1）概念A 相容于概念B，即A B。

（2）Type（A）≤Type（B），其中Type（P）表示參數P 的數據類型的取值范圍。如Type（Short）≤Type（Int）≤Type（Double）。

由于概念相容性和數據類型相容性均存在傳遞的特點，可知參數兼容關系也具有傳遞性。下面結合服務簇中功能需求的匹配條件和參數的兼容關系給出Web服務匹配關系的定義：

定義6 同一服務簇中的Web服務匹配關系。Web服務WSa匹配于Web 服務WSb，記為WSaWSb，當且僅當：

（1）對于WSb輸入參數Ib＝ ｛ib1，ib2，…｝中任意一個參數ib，WSa輸入參數Ia＝ ｛ia1，ia2，…｝中均存在一個輸入參數ia，使得ia兼容于ib，記為

（2）對于WSa輸出參數Oa＝ ｛oa1，oa2，…｝中任意一個參數oa，WSb輸出參數Ob＝ ｛ob1，ob2，…｝中均存在一個輸出參數ob，使ob兼容于oa，即

2.2 匹配關系的傳遞特性

假設存在 Web 服務WSn、WSm，使得服務請求WSrequest匹 配 于WSn，WSn匹 配 于WSm，即WSrequestWSn，、WSnWSm。則根據匹配條件和定義6可知存在如下關系：

（1）對于輸入參數有：

其形式化公式為

根據集合理論可知有-in in 關系，將其結合式（3）可得

結合兼容關系的傳遞性有

（2）對于輸出參數有：

其形式化公式為

同理上述輸入參數中的推導可得如下關系

結合式 （5）、式 （7）和匹配關系的定義，服務請求WSrequest也同時匹配于WSm，即WSrequestWSm，因此Web服務匹配關系存在傳遞的特性，而基于其傳遞特性，服務請求能同時查找到多個滿足要求的Web服務。

2.3 匹配關系圖

一個服務簇中可能存在多個Web服務匹配關系，為了能對其進行統一的管理并充分的利用它們之間傳遞特性，本文將服務簇中的Web服務及其匹配關系進行圖形化建模而生成一個有向圖模型，該有向圖模型就稱為匹配關系圖，其具體定義如下：

定義7 匹配關系圖。匹配關系圖是服務簇中Web服務及其匹配關系的有向圖模型，其中節點表示Web服務，節點與節點之間的有向邊表示匹配關系，如圖1所示。

圖1 匹配關系

匹配關系圖是一個有向圖，可用鄰接矩陣或鄰接鏈表進行存儲，通過對簇中的Web服務進行兩兩匹配判斷來構建圖中的有向邊。下面給出匹配關系圖生成的算法，其匹配關系圖采用鄰接矩陣進行存儲：

算法1：匹配關系圖的生成算法

輸入：服務簇中的Web服務

輸出：服務簇的匹配關系圖G

謀事要實，常懷“求是之心”。謀事要實，首在心實，端正心態，樹立正確的事業觀、政績觀和全局觀。謀事要實，貴在情實，摸透實情，提升謀事的質量。謀事要實，重在落實，腳踏實地，做到決策符合實際情況、符合客觀規律、符合科學精神。

（1）G ［n］［n］：＝0，其中n 為服務簇中Web服務的個數。

（2）若服務簇中Web 服務已經比較完畢，則轉步驟（4），否則從服務簇中依次取出WSi、WSj兩個Web服務，其中i≠j。

（3）利用定義6，判斷是否滿足WSiWSj，若滿足則將G［i］［j］：＝1，否則轉步驟 （2）。

（4）返回匹配關系圖G。

利用匹配關系圖，能同時發現多個Web服務，即若服務請求匹配于服務中的某個Web服務，則也匹配于從這個Web服務節點出發，遍歷匹配關系圖所得到的Web服務集合，如圖1所示，若服務請求WSrequest匹配于WSa，則也同時匹配于WSb、WSc和WSd。相比與傳統的逐一比較的方法，利用匹配關系圖能有效地減少了服務比較的次數，而在實際的應用中，匹配關系圖可提前在預處理中進行生成而不會影響服務發現的效率。

3 利用匹配關系圖的服務發現方法

服務簇能有效地減少服務發現的檢索空間，但定位到具體服務簇中進行服務查找時，現有的匹配方法還是逐一將服務請求與簇中的Web服務進行比較。本文提出利用匹配關系圖的服務發現方法 （RGSD）可通過遍歷預先生成的匹配關系圖來減少比較次數，提高服務發現效率。

由于匹配關系圖是定義在服務簇的基礎之上，為了更加有效的在利用匹配關系圖和對服務簇進行統一的管理，首先給出了基于匹配關系圖的服務簇形式化描述，其定義如下：

（1）Cn表示服務簇名稱，來唯一標識一個服務簇。

（2）Cdes是服務簇的語義功能描述。

（3）Cw＝ ｛WS1，WS2，…WSn｝表 示 服 務 簇 中 的Web服務的集合。

（4）I＝ ｛I1∪I2∪…∪In｝是服務簇中Web服務的輸入集合。其中Ik（1≤k≤n）是Web 服務WSk的輸入參數集。

（5）O＝ ｛O1∪O2∪…∪On｝是服務簇中Web服務的輸出集合。其中Ok（1≤k≤n）是Web服務WSk的輸出參數集。

（6）Gr表示服務簇的匹配關系圖。

在服務發現過程中，首先對服務請求的功能描述WRdes和服務簇的功能描述Cdes進行語義相似度計算，來定位到具體的服務簇。由于服務功能描述都是由多個概念參數組成，并且各Web服務的參數的個數和順序都是不同的，在計算功能描述的語義相似度時，須先根據概念語義相似度對參數進行配對的處理。

定義9 概念語義相似度［8］。其計算公式如下

式中：dis（A，B）、dismax、dismin的具體定義請參見文獻［8］。

參數的配對是通過計算兩組參數中的概念概率語義相似度，然后將其值為最小的配為一對。其配對過程可以轉化為二分圖最優配對，其具體的算法請參見文獻 ［14］，這里不再討論。圖2 表示一個天氣預報的服務描述匹配結果示例。

圖2 匹配結果

定義10 功能描述的語義相似度。WRdes，Cdes是由參數集構成，可通過如下公式來計算其語義相似度

式中：l——WRdes、Cdes參數匹配對的個數，如圖2 示例中，l＝2；Dis（WRdes，Cdes）表示WRdes與Cdes之間的語義

當定位到具體的服務簇中進行服務發現時，RGSD 方法可通過如下方式來減少服務比較次數：首先從服務簇中取出的一個Web服務，如果服務請求匹配于該Web服務，從該Web服務所對應的節點出發遍歷匹配關系圖，把遍歷所獲得的Web服務節點集加入到要返回的候選服務集中，如果下次取出的Web服務已經在候選服務集中，則可直接跳過而不參與比較。下面給出其服務發現方法的具體步驟：

算法2：基于匹配關系圖的服務發現

輸入：服務請求WSR＝ ｛WRdes，IR，OR｝；

輸出：候選Web服務集合S。

（1）S：＝ ；

（2）依次取出服務簇RGSC，如果不存在，則轉步驟（7）；

（3）若sim（WRdes，Cdes）＜δ，其中δ為給定閥值，轉步驟 （2）；

（4）從Cw中取出一個Web服務WSk，若S 中已經包含WSk，則重復該步驟，若Cw中Web服務已經比較完畢則轉步驟 （2）；

（5）根據匹配條件，判斷WSk中輸入、輸出參數是否滿足（-ir→ ik）∧（-ok→ or）關系，若不滿足則轉步驟 （4）；

（6）從Web服務WSk出發，遍歷匹配關系圖Gr，把得到的Web服務節點，加入S，轉步驟 （4）；

（7）輸出S。

4 仿真實驗

本文提出的利用匹配關系圖的服務發現方法 （RGSD）是對傳統逐一匹配方法所作的優化，和具體的聚類算法無關。下面將通過仿真程序從發現效率和準確率兩個維度進行測試并和文獻 ［3］提出的基于功能需求聚類服務發現方法 （SWSC）進行比較，從而驗證本文提出方法的有效性，其中仿真程序是采用java EE、Oracle 11g數據庫、Jboss應用服務器進行開發，具體實驗設置如下：

仿真實驗數據：從seekda.com 網站上下載多個WSDL描述的Web服務，這些Web服務來自5個交叉度很低的不同領域，使得每個領域可以作為一個服務簇并且每個類別中包含300～500個Web服務。從WSDL中抽取關鍵概念，利用protege工具生成領域本體樹。通過OWL－S Editor工具將Web服務轉化OWL－S規范，最后將Web服務存入數據庫中。

硬件環境：Cpu 2.13GHZ、內存2GB、操作系統Windows7。

實驗1 （發現效率）：每個類別從數據庫中分別取出若干個Web服務，并生成其對應的匹配關系圖和服務簇模型。針對若干個隨機生成的服務請求，利用RGSD 方法和SWSC方法進行服務發現，記錄其比較次數和匹配時間，取其平均值作為結果值，其實驗結果如圖3、圖4所示。

圖3 服務發現匹配次數比較

從圖3、圖4實驗結果表明，本文所提方法的匹配效率上要優于文獻 ［5］的SWSC 方法，并且隨著Web服務個數的增加，RGSD 方法能同時匹配的Web服務個數也在增加，使得其在匹配效率上的優勢更加明顯。

圖4 服務發現時間效率比較

實驗2 （準確率）：每個類別從數據庫中分別取出若干個Web服務，并生成其對應的匹配關系圖和服務簇模型。針對每個服務簇，自定義一個服務請求，利用RGSD 和SWSC方法進行服務發現，并記錄其返回符合服務請求功能需求的Web服務數與返回的Web服務總數之間的比率，取其平均值作為結果值，其實驗結果如圖5所示。

圖5 準確率比較

圖5實驗結果表明，由于本文所提方法在服務發現過程中，一些匹配Web 服務是通過遍歷匹配關系圖所獲得的，會帶來一定的精度損失，從而造成匹配準確率要微低于文獻 ［4］方法，但在總體上仍然能保證較高的準確率。

5 結束語

本文定義了服務簇中Web服務之間存在的匹配關系，論證了該關系具有傳遞性的特點。在對特定服務簇進行Web服務檢索過程中，通過遍歷服務簇中的匹配關系圖，服務請求可以同時匹配多個滿足需求的Web服務，相對于傳統的匹配方法要逐一比較的方式，有效減少了服務匹配的次數，提高了服務發現的效率。仿真實驗結果表明了該算法的可行性與優越性。接下來的工作將完善匹配關系服務簇模型，將服務質量與服務過程引入服務簇模型。此外，服務的優化組合發現也將是今后的研究重點。

［1］Ngan，Le Duy，Rajaraman Kanagasabai.Semantic Web service discovery：State－of－the－art and research challenges ［J］.Personal and Ubiquitous Computing，2013，17 （8）：1741－1752.

［2］Xu X，Yuruk N，Feng Z，et a1.SCAN：A structural clustering algorithm for networks ［C］／／Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2007：824－833.

［3］Nayak R，Lee B.Web service discovery with additional semantics and clustering ［C］／／Proceedings of IEEE／WIC／ACM International Conference on Web Intelligence.Piscataway：IEEE，2007：555－558.

［4］XU Xiaoliang，CHEN Jinkui，WU You.Web service discovery method based on clustering opmizition ［J］.Computer Engineering，2011，37 （9）：68－70 （in Chinese）.［徐小良，陳金奎，吳優.基于聚類優化的Web服務發現方法 ［J］.計算機工程，2011，37 （9）：68－70.］

［5］WANG Yongming，ZHANG Yingjun，XIE Binhong，et al.Semantic Web service discovery based on fuzzy clustering optimization［J］.Computer Engineering，2013，37 （9）：219－223 （in Chinese）.［王永明，張英俊，謝斌紅，等.基于模糊聚類優化的語義Web服務發現［J］.計算機工程，2013，37 （9）：219－223.］

［6］YANG Yueming，CHEN Lichao，XIE Binhong，et al.Study on approach of Web services discovery based on clustering of users’context information ［J］.Computer Engineering and Design，2012，33 （4）；1442－1146 （in Chinese）. ［楊岳明，陳立潮，謝斌紅，等.基于用戶情境聚類的Web服務發現方法研究 ［J］.計算機工程與設計，2012，33 （4）：1442－1146.］

［7］SUN Ping，JIANG Changjun.User service clustering to facilitate process－oriented semantic Web service discovery ［J］.Chinese Journal of Computers，2008，31 （8）：1340－1353 （in Chinese）.［孫萍，蔣昌俊.利用服務簇聚類優化面向過程模型的語義Web 服務發現 ［J］.計算機學報，2008，31 （8）：1340－1353.］

［8］DENG Shiyang，DU Yuyue.Logic Petri net based model for Web service cluster ［J］.Journal of Computer Applications，2012，32 （8）：2328－2332 （in Chinese）. ［鄧式陽，杜玉越.基于邏輯Petri網的Web 服務簇模型 ［J］.計算機應用，2012，32 （8）：2328－2332.］

［9］Nayak R，Lee B.Web service discovery with additional semantics and clustering ［C］／／Proceedings of IEEE／WIC／ACM International Conference on Web Intelligence.Piscataway：IEEE，2007：555－558.

［10］Wu J，Chen L，Zheng Z，et al.Clustering Web services to facilitate service discovery ［J］.Knowledge and Information Systems，2014，38 （1）：207－229.

［11］WANG Jue，XIANG Chaocan，WANG Meng，et al.Survey on semamtic Web service discovery ［J］.Application Research of Computer，2013，30 （1）：7－12 （in Chinese）.［王玨，向朝參，王萌，等.語義Web服務發現研究現狀與發展 ［J］.計算機應用研究，2013，30 （1）：7－12.］

［12］CHEN Ke，CHENG Yi，XIE Mingxia，et al.Spatial information service automatic discovery based on service cluster ［J］.Computer Engineering，2012，38 （24）：182－190 （in Chinese）.［陳科，成毅，謝明霞，等.基于服務簇的空間信息服務自動發現［J］.計算機工程，2012，38 （24）：182－190.］

［13］LUAN Wenjing，DU Yuyue.Web service discovery method based on net unit model of service cluster［J］.Computer Science，2012，33 （8）：147－152（in Chinese）.［欒文靜，杜玉越.一種基于服務簇網元模型的Web服務發現方法 ［J］.計算機科學，2012，33 （8）：147－152.］

［14］DENG Shuiguang，YI Jianwei，LI Ying，et al.A method of semantic Web service discovery based on bipartite graph matching ［J］.Chinese Journal of Computers，2008，31 （8）：1364－1374 （in Chinese）. ［鄧水光，尹建偉，李瑩，等.基于二分圖匹配的語義Web服務發現方法 ［J］.計算機學報，2008，31 （8）：1364－1374.］