一種基于虛擬社交化的Web服務(wù)發(fā)現(xiàn)方法研究*

潘善亮 ，茅琴嬌 ，韓 露

（1．寧波大學(xué)信息科學(xué)與工程學(xué)院 寧波 315211；2．西安交通大學(xué)電子與信息工程學(xué)院 西安 710049）

1 引言

隨著Web服務(wù)的快速發(fā)展，企業(yè)越來越傾向于把公司的業(yè)務(wù)流程作為服務(wù)發(fā)布出去，同時也通過互聯(lián)網(wǎng)尋找滿足特定需求的Web服務(wù)，使得Web服務(wù)的發(fā)布與組合越來越流行。隨著服務(wù)數(shù)量的日益增長，網(wǎng)絡(luò)中存在著大量的可用Web服務(wù)，用戶尋找到合適服務(wù)的效率和準(zhǔn)確率也隨之降低。因此有效的Web服務(wù)發(fā)現(xiàn)機(jī)制對用戶發(fā)現(xiàn)合適的服務(wù)至關(guān)重要[1]。傳統(tǒng)的服務(wù)發(fā)現(xiàn)機(jī)制忽略了服務(wù)之間的關(guān)聯(lián)關(guān)系，認(rèn)為服務(wù)之間是相互獨立的，使得服務(wù)發(fā)現(xiàn)的結(jié)果不能滿足用戶的需求。例如，用戶計劃外出旅行，欲通過網(wǎng)絡(luò)提供的Web服務(wù)完成旅行安排，主要包含訂票服務(wù)和酒店預(yù)訂服務(wù)。在返回的大量服務(wù)中，用戶根據(jù)實際情況選擇滿足需求的服務(wù)。由于Web服務(wù)之間存在業(yè)務(wù)流程關(guān)系，訂票服務(wù)與酒店預(yù)訂服務(wù)之間存在相互協(xié)作關(guān)系（例如，訂票服務(wù)和特定的酒店之間存在不同的折扣關(guān)系），而酒店預(yù)訂服務(wù)之間則存在相互競爭關(guān)系[2]。Web服務(wù)之間的兩種關(guān)系如圖1所示。

圖1 服務(wù)之間的競爭與協(xié)作關(guān)系

圖1中，S3、S4、S5表示服務(wù)之間是相互競爭的關(guān)系，箭頭方向表示 S1、S2、(S3，S4，S5)、S6、S7服務(wù)之間是相互協(xié)作的。因為網(wǎng)絡(luò)中服務(wù)數(shù)量的增加，相同或相似功能的服務(wù)大量存在，某一服務(wù)會與其他功能相似的服務(wù)形成相互競爭的關(guān)系。同樣，網(wǎng)絡(luò)中的Web服務(wù)會應(yīng)服務(wù)調(diào)用者的要求，與其他服務(wù)協(xié)作以滿足用戶關(guān)于復(fù)雜功能的需求，也就是說，服務(wù)之間存在相互協(xié)作的關(guān)系。

本文把社區(qū)網(wǎng)絡(luò)思想[3,4]引入Web服務(wù)研究中，根據(jù)服務(wù)之間的相互關(guān)系構(gòu)建一個“社區(qū)網(wǎng)絡(luò)”，然后利用構(gòu)建的網(wǎng)絡(luò)實現(xiàn)服務(wù)的發(fā)現(xiàn)和綁定。主要分析Web服務(wù)之間存在相互競爭和相互協(xié)作的關(guān)系，通過解析這兩種關(guān)系中Web服務(wù)的表現(xiàn)，實現(xiàn)Web服務(wù)的發(fā)現(xiàn)與選擇。具體方法是：競爭關(guān)系中的服務(wù)發(fā)現(xiàn)，計算的是網(wǎng)絡(luò)中的服務(wù)與被請求服務(wù)的相似度，與用戶需求的服務(wù)相似度最高的服務(wù)被選出；在協(xié)作關(guān)系中，計算的是服務(wù)的交際能力，與其他服務(wù)在相互協(xié)作過程中交際能力好的服務(wù)被選出，這種交際能力是對服務(wù)固有特性的衡量，對于動態(tài)環(huán)境中的服務(wù)發(fā)現(xiàn)很重要。因此本文Web服務(wù)發(fā)現(xiàn)與選擇的策略就是把這兩種關(guān)系中表現(xiàn)好的服務(wù)返回給用戶[5,6]。

2 相關(guān)工作

目前關(guān)于Web服務(wù)發(fā)現(xiàn)的方法主要分為基于功能性和非功能性的匹配方法，框架如圖2所示。

[7]中Kokas N等人利用基于關(guān)鍵字的匹配方法，除去停用詞，取詞干以獲取Web服務(wù)描述文檔（Web services description language,WSDL）中的實意詞，再根據(jù)這些實意詞進(jìn)行Web服務(wù)的語法匹配發(fā)現(xiàn)。參考文獻(xiàn)[8]中利用關(guān)鍵字匹配中基于向量的方法，構(gòu)建Web服務(wù)文檔和查詢請求描述文檔的向量，然后計算向量之間的相似性，得到服務(wù)發(fā)現(xiàn)的集合。參考文獻(xiàn)[9]中采用了Quality Threshold聚類算法對WSDL文檔進(jìn)行分類，首先從網(wǎng)絡(luò)上挖掘 WSDL文件，得到描述 Web服務(wù)的 content、type、messages、ports和service name這5個部分，然后將這些特征整合起來，按照功能相似度對Web服務(wù)進(jìn)行聚類，不僅可以極大地提高Web服務(wù)搜索引擎的準(zhǔn)確度，而且能夠適應(yīng)Web服務(wù)的動態(tài)變化。參考文獻(xiàn)[10]提出了基于服務(wù)操作匹配的Web服務(wù)發(fā)現(xiàn)方法，把Web服務(wù)描述為一個三元組（ns,ds,p），其中ns是該服務(wù)的名稱，ds是該服務(wù)的文本描述，p是該服務(wù)中操作的集合。因為Web服務(wù)發(fā)現(xiàn)過程建立在相似匹配的基礎(chǔ)上，所以采用基于操作的相似性來實現(xiàn)服務(wù)的相似性發(fā)現(xiàn)。首先將Web服務(wù)內(nèi)含的操作建模為DOM標(biāo)簽樹，然后通過采用滿足約束的樹編輯距離量化操作與操作之間的相似度，得到服務(wù)之間的相似度。參考文獻(xiàn)[11]提出了一種基于語義的服務(wù)發(fā)現(xiàn)方法，通過計算本體樹中概念之間的最短路徑獲得概念間的本體距離，利用獲得參數(shù)的本體距離，確定服務(wù)之間的相似度。

但是，以上關(guān)于服務(wù)發(fā)現(xiàn)的方法均不夠全面。參考文獻(xiàn)[7]中只考慮基于關(guān)鍵字的功能性匹配，忽略很多語義相似的服務(wù)，使得服務(wù)發(fā)現(xiàn)的結(jié)果不夠準(zhǔn)確。參考文獻(xiàn)[9]中采用了對WSDL文檔進(jìn)行分類的方法，大大提高了服務(wù)發(fā)現(xiàn)的準(zhǔn)確度，但是并未考慮服務(wù)之間操作的相似度，同樣在服務(wù)發(fā)現(xiàn)的過程中會遺漏很多滿足條件的服務(wù)。參考文獻(xiàn)[10]中通過將服務(wù)內(nèi)含的操作轉(zhuǎn)化為DOM標(biāo)簽樹，提高了服務(wù)發(fā)現(xiàn)的準(zhǔn)確率，但是并未綜合考慮服務(wù)的標(biāo)簽節(jié)點和約束節(jié)點的計算方法。參考文獻(xiàn)[11]中單純考慮服務(wù)發(fā)現(xiàn)方法，并未考慮服務(wù)之間的調(diào)用關(guān)系，忽略了服務(wù)之間存在著業(yè)務(wù)上的關(guān)聯(lián)關(guān)系。

圖2 Web服務(wù)發(fā)現(xiàn)方法的分類

基于以上原因，本文綜合考慮了服務(wù)之間存在相互競爭和相互協(xié)作的關(guān)系，在競爭關(guān)系中結(jié)合用戶的需求，計算用戶與服務(wù)之間文本描述信息的相似度，然后基于WSDL的特點，構(gòu)建schema樹，計算服務(wù)之間的結(jié)構(gòu)相似度，綜合考慮文本相似度和結(jié)構(gòu)相似度得到一組服務(wù)列表，然后分別計算列表中每個服務(wù)的交際能力，選擇交際能力強(qiáng)的服務(wù)推薦給用戶。

3 競爭關(guān)系中的服務(wù)發(fā)現(xiàn)

3.1 問題分析

網(wǎng)絡(luò)中的Web服務(wù)是可被公共訪問和集成的一個巨大的標(biāo)準(zhǔn)組件庫。一個WSDL文檔與一個 Web服務(wù)相對應(yīng)，對服務(wù)的功能與接口進(jìn)行描述。Web服務(wù)與一般的Web網(wǎng)頁包含的大量文本信息不同，只包含非常簡短的文本信息,同時含有大量的復(fù)雜結(jié)構(gòu)信息。因此Web服務(wù)的發(fā)現(xiàn)不僅要考慮到文本描述信息的相似度，還應(yīng)該考慮結(jié)構(gòu)的匹配性。

本文在標(biāo)準(zhǔn)的WSDL基礎(chǔ)上，根據(jù)其特點，從WSDL文檔中解析出關(guān)于服務(wù)的文本描述信息和服務(wù)的結(jié)構(gòu)信息，以實現(xiàn)Web服務(wù)的發(fā)現(xiàn)。同時從用戶關(guān)于服務(wù)的歷史調(diào)用痕跡中總結(jié)出服務(wù)所屬的興趣領(lǐng)域，以期返回的服務(wù)是用戶偏好的服務(wù)。

因此，在競爭關(guān)系中，Web服務(wù)間相似度的計算綜合了服務(wù)間的文本相似度與結(jié)構(gòu)相似度。即對于Web服務(wù)A和B，在競爭的環(huán)境下，它們之間的相似度計算如下：

其中，α+β=1，0≤α≤1，0≤β≤1，ContentSim(A,B)表示兩個服務(wù)的文本相似度，StructureSim(A,B)表示服務(wù)之間結(jié)構(gòu)的相似度。

3.2 服務(wù)的文本相似度

3.2.1 網(wǎng)絡(luò)中Web服務(wù)的文本相似度判斷

在Web服務(wù)的相似度發(fā)現(xiàn)過程中，網(wǎng)絡(luò)中的服務(wù)應(yīng)該與被請求的服務(wù)是相關(guān)的，也就是在基于WSDL語言描述的服務(wù)中，應(yīng)該充分挖掘WSDL文檔中的自然語言信息，并為每個WSDL文檔構(gòu)建代表該Web服務(wù)特征的詞匯集合[12]。

因為WSDL文檔是結(jié)構(gòu)化的文檔，從WSDL文檔的標(biāo)簽內(nèi)容中解析出代表服務(wù)文本描述的信息。從WSDL文檔中提取實意詞的步驟有以下5步。

（1）parsing WSDL：根據(jù)最簡單的空格分詞法，抽取和等標(biāo)簽節(jié)點的描述信息，包含服務(wù)名稱、操作名稱和消息參數(shù)名稱等一系列詞匯信息。

（2）tag removal：去掉得到的詞匯信息中的tag部分。例如，若在得到的一系列名稱信息中包含了XML、HTML或者 WSDL中定義的tag，如 type、message等，則刪去該信息。因為這些tag都是預(yù)先定義的，將其刪去的工作也比較簡單。

（3）word stemming：把得到的名稱信息變?yōu)橹皇Ｏ禄~的單詞，比如 connect、connected、connecting、connection的基詞都是connect，本文只取基詞，出現(xiàn)次數(shù)的多少代表了這個詞的重要性。

（4）function word removal：描述信息中出現(xiàn)的如 of、at、in、without、between 這種輔助詞，對服務(wù)的發(fā)現(xiàn)貢獻(xiàn)很小，因此刪除此類詞。

（5）content word recognition：一些比較常見的詞如data、web、port等，這些詞在大多數(shù)服務(wù)中都會出現(xiàn)，因此在服務(wù)特征的貢獻(xiàn)上沒有什么用處，也將其去掉。

經(jīng)過以上的處理后，就得到文檔特征詞的集合。

3.2.2 用戶歷史特性的考慮

考慮用戶的歷史特性不僅可以挖掘用戶潛在的服務(wù)偏好，同時可以解決用戶描述查詢請求不準(zhǔn)確的問題，由于專業(yè)知識或者使用經(jīng)驗的缺乏，在查詢請求中存在不準(zhǔn)確的問題。因此本文依據(jù)用戶調(diào)用服務(wù)的結(jié)果，獲取用戶歷史調(diào)用服務(wù)的習(xí)慣，獲得用戶的興趣傾向，實現(xiàn)更準(zhǔn)確的服務(wù)發(fā)現(xiàn)。

本節(jié)考慮用戶潛在的對服務(wù)的偏好信息是通過用戶歷史調(diào)用服務(wù)的情況呈現(xiàn)的，也就是用戶的這種偏好存在于調(diào)用過的服務(wù)列表中。通過這個服務(wù)列表，挖掘用戶的興趣傾向?？梢哉J(rèn)為用戶的興趣傾向可以體現(xiàn)在被調(diào)用服務(wù)的文本描述信息中，即服務(wù)名稱、操作名稱、消息的名稱等標(biāo)簽內(nèi)容中[13]。因此，用戶的歷史特性包含在用戶調(diào)用過的服務(wù)的文本描述信息中，這些歷史調(diào)用信息的獲取與前文對網(wǎng)絡(luò)中服務(wù)的文本信息的獲取方法類似。

在得到用戶的歷史特性信息后，結(jié)合當(dāng)前的用戶查詢請求信息，得到帶有用戶偏好的查詢請求?；谠摬樵冋埱螅瑢W(wǎng)絡(luò)中的服務(wù)進(jìn)行初步的相似度計算，參照傳統(tǒng)的向量空間模型實現(xiàn)，計算如下：

其中，wik代表詞匯k在服務(wù)中的權(quán)重，w′ik代表詞匯k在請求中的權(quán)重。SR(s,q)的取值范圍為(0，1)，而且值越大代表用戶的請求與當(dāng)前服務(wù)的相似度越大。

3.3 服務(wù)的結(jié)構(gòu)相似度

3.3.1 Web服務(wù)的簡化

WSDL是一種基于XML的結(jié)構(gòu)化描述語言，是目前被廣泛采用的Web服務(wù)描述語言[14]。WSDL文檔的整體結(jié)構(gòu)如圖3所示。

圖3 WSDL文檔結(jié)構(gòu)

WSDL文檔描述服務(wù)從兩個級別進(jìn)行。在抽象級別，WSDL文檔通過發(fā)送/接收的message描述一個Web服務(wù)，types定義Web服務(wù)中的數(shù)據(jù)類型，一般使用XML schema描述。其中，message中包含的具體消息內(nèi)容用types元素表示，而operation通過消息交換模式將message關(guān)聯(lián)在一起；在具體級別，WSDL文檔描述的是具體如何與Web服務(wù)通信，binding是為portType指定傳輸協(xié)議和交換格式，port把具體網(wǎng)絡(luò)地址與綁定關(guān)聯(lián)在一起，service把針對同一port的端點組織在一起。

簡化后的WSDL文檔如圖4所示，在基于WSDL的服務(wù)中，Web服務(wù)的功能實體是由執(zhí)行服務(wù)的各個操作完成的，而對于操作而言，每個操作又由一組輸入?yún)?shù)和一組輸出參數(shù)組成。輸入和輸出參數(shù)就是用來進(jìn)行數(shù)據(jù)交換的消息內(nèi)容。Web服務(wù)的操作實例見表1。

圖4 簡化后的WSDL文檔

3.3.2 Web服務(wù)結(jié)構(gòu)相似度計算

由前文分析可知，Web服務(wù)的實質(zhì)是實現(xiàn)服務(wù)功能的操作列表。Web服務(wù)之間結(jié)構(gòu)的相似度就是所有服務(wù)操作相似度的加權(quán)和，因此得到的是不同操作之間的相似度。Web服務(wù)操作的相似度就是不同操作之間的輸入?yún)?shù)列表和輸出參數(shù)列表的相似度。Web服務(wù)操作中的輸入?yún)?shù)和輸出參數(shù)的數(shù)據(jù)類型通常是基于XML schema語法定義的，包含數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)類型分為簡單類型和用戶自定義的復(fù)雜類型。因此服務(wù)操作輸入?yún)?shù)中的數(shù)據(jù)類型與另一服務(wù)操作輸入?yún)?shù)的數(shù)據(jù)類型的相似度、服務(wù)操作的輸出參數(shù)的數(shù)據(jù)類型與另一服務(wù)操作的輸出參數(shù)的數(shù)據(jù)類型的相似度是Web服務(wù)結(jié)構(gòu)相似的關(guān)鍵。

本文把操作中的基于XML schema描述的數(shù)據(jù)類型建模為具有標(biāo)記節(jié)點（labeled node）的樹狀結(jié)構(gòu)。樹的節(jié)點根據(jù)標(biāo)記（label）的不同，分為標(biāo)簽節(jié)點（tag node）和約束節(jié)點（constraint node），其中標(biāo)簽節(jié)點對應(yīng)于WSDL文檔中的element標(biāo)簽的節(jié)點，約束節(jié)點即順序節(jié)點（sequence node）、選擇節(jié)點 （union node）和多選節(jié)點（multiplicity node）。順序節(jié)點表示其子節(jié)點是按順序出現(xiàn)的，選擇節(jié)點表示該節(jié)點的實例只能選擇該類型中的一種類型，多選節(jié)點指子節(jié)點可以出現(xiàn)的次數(shù)范圍為[minOccurs，maxOccurs]。

根據(jù)標(biāo)簽樹之間的距離計算可以獲得基于XML schema語法的輸入或輸出參數(shù)的數(shù)據(jù)類型的相似度。本文利用樹編輯距離算法計算兩棵樹之間的相似度，也就是兩個服務(wù)操作之間的相似度[15]。

表1 Web服務(wù)實例

3.3.3 樹編輯距離算法

樹編輯距離算法是一種常用且有效的計算兩樹之間相似度的方法。樹編輯操作包括刪除和修改已存在的節(jié)點標(biāo)簽以及插入新的節(jié)點標(biāo)簽。兩樹之間的編輯距離是指兩棵樹之間的轉(zhuǎn)換所需的最低操作代價[16]。然而傳統(tǒng)的樹編輯距離算法無法處理前文中提到的約束節(jié)點。應(yīng)該在保留其功能的情況下，把這些約束節(jié)點從樹結(jié)構(gòu)中消去。3種約束節(jié)點的消去原則如下。

·順序節(jié)點的分離原則：因為其約束的是子節(jié)點出現(xiàn)順序，因此可以直接消去，但是消去之后對編輯操作的映射代價會有影響。

·選擇節(jié)點的合并原則：所有子節(jié)點合并為一個節(jié)點，將合并的節(jié)點的標(biāo)簽名作為新的節(jié)點的標(biāo)簽，合并以后對編輯操作的映射代價會有影響。

·多選節(jié)點的刪去原則：多選節(jié)點也可以直接刪去，同樣刪去之后對編輯操作的映射代價也會有影響。

樹編輯距離算法的主要思想是通過節(jié)點的刪去、插入、替換3種編輯操作后，所需的花費最小。因此計算兩棵XML模式樹之間的相似度就等價于尋找一個擁有最低代價的映射。而兩棵XML模式樹標(biāo)簽之間的映射必須滿足以下條件。

若 Tx是一棵樹，Tx[i]是樹 Tx上的第 i個節(jié)點,T1、T2之間的映射是有序的節(jié)點對（in，jn）的集合，n=1，2，…，它們必須滿足以下條件：

·若T1[i1]在 T2[i2]的左邊，那么 T2[j1]也在 T2[j2]的左邊，反之亦然；

·若 i1=i2，則 j1=j2；

·若T1[i1]是 T2[i2]的祖先，那么T2[j2]也是 T2[j2]的祖先。兩棵樹之間的映射實例如圖5所示。

由圖5可知，如果目標(biāo)樹中出現(xiàn)了源樹中沒有出現(xiàn)的節(jié)點，則是節(jié)點的插入；如果源樹中的節(jié)點在目標(biāo)樹中沒有出現(xiàn)則是節(jié)點的刪去；如果在同一個位置，源樹中的節(jié)點和目標(biāo)樹中的節(jié)點不同則是節(jié)點的變換。

圖5 樹映射實例

3.3.4 編輯操作代價模型

為了尋找編輯操作花費最小的映射，首先應(yīng)該明確映射中出現(xiàn)的每一步編輯操作的代價，也就是節(jié)點的插入、刪去以及替換時所需的代價。參考文獻(xiàn)[16]中提出的代價模型很簡單，認(rèn)為3種操作的代價均為1，這種算法簡單但不準(zhǔn)確。參考文獻(xiàn)[17]提出對所建的XML模式樹中不同層的節(jié)點分配一個權(quán)重，同時不同層的節(jié)點所分配的權(quán)重應(yīng)該不同，而且越靠近根節(jié)點的節(jié)點獲得的權(quán)重越大，越往下，權(quán)重越小。該方法引入標(biāo)簽節(jié)點的權(quán)重，對不同編輯操作所需的代價影響不同。

首先考慮節(jié)點的插入和刪去時兩棵樹之間相互映射的代價。當(dāng)進(jìn)行schema樹匹配時，節(jié)點的插入代價就是節(jié)點插入后在目標(biāo)子樹中的權(quán)重。而進(jìn)行節(jié)點刪除操作，所花費的代價就是節(jié)點在源樹中的權(quán)重。在節(jié)點的替換操作中，由于節(jié)點處在同一層，權(quán)重都一樣。但是標(biāo)簽節(jié)點由相互連接的單詞組成，例如GetLastTradePrice，含有豐富的語義信息。因此標(biāo)簽節(jié)點在替換操作時，節(jié)點之間語義距離的確定是關(guān)鍵。

在服務(wù)的發(fā)現(xiàn)過程中，服務(wù)操作是Web服務(wù)器功能屬性的簡化。因此計算標(biāo)簽節(jié)點的替換操作的代價時，考慮這兩個標(biāo)簽節(jié)點在服務(wù)發(fā)現(xiàn)時檢索的貢獻(xiàn)。本文使用正規(guī)化 Google 距離（normalized Google distance，NGD）計算兩個標(biāo)簽之間的距離。

綜合以上分析，本文給出樹T1和樹T2的編輯操作的代價如下。

·節(jié)點的插入Cost（T1，T2)=節(jié)點在目標(biāo)樹中的權(quán)重/兩棵樹所有節(jié)點權(quán)重之和。

·節(jié)點的刪去Cost（T1，T2)=節(jié)點在源樹中的權(quán)重/兩棵樹所有節(jié)點權(quán)重之和。

·節(jié)點的替換 Cost（T1，T2)={NGD（節(jié)點 1，節(jié)點 2）}。

其中，關(guān)于標(biāo)簽節(jié)點的權(quán)重定義見參考文獻(xiàn)[18]。若樹的深度為l，標(biāo)簽節(jié)點的權(quán)重的值域落在[2,21]范圍里。因此為了使編輯操作的代價范圍為[0,1]，將節(jié)點的編輯操作的代價都除以兩棵樹的所有節(jié)點的權(quán)重和。

3.3.5 標(biāo)簽節(jié)點之間的語義距離

一般來說，計算詞語之間語義距離的方法可以分成兩種：一種是基于某種世界知識，如Ontology知識，語義相似度的確定依據(jù)詞匯概念間的結(jié)構(gòu)層次關(guān)系確定，但由于構(gòu)建本體花費代價大，本文不使用此法；另一類就是基于統(tǒng)計的方法，假設(shè)兩個詞匯出現(xiàn)在相同的上下文中，就認(rèn)為它們之間具有某種程度的語義相似。

NGD是指在Google搜索中，輸入待計算的兩個詞匯，利用Google搜索發(fā)現(xiàn)含有這兩個詞匯的記錄數(shù)來衡量這兩個詞匯之間的語義距離[19]。兩個詞之間的Google距離的計算如下：

其中，f（a）指的是返回的Web頁面包含詞匯a的頁面數(shù)，f(b)指的是返回的頁面包含詞匯b的頁面數(shù)，f(a，b)表示的是同時含有詞匯a、b的Web頁面數(shù)，而N代表Google索引到的Web頁面總數(shù)。對于詞語a和b，語義距離為NGD(a，b)。NGD計算的詞匯語義距離是對稱的，即詞匯a到b的距離和b到a的距離一樣，不考慮詞匯之間a（b)包含b（a)的情況。通過這種方式得到的詞匯語義距離有以下幾個性質(zhì)。

·得到的詞匯語義距離的取值范圍為[0,∞]。另外假設(shè)a＝b 或 a≠b，且 f（a)=f（b)=f（a,b)＞0，那么 NGD（a,b)為0。代表詞匯a和b含有相同的語義。如果f（a)=0或f（b)=0，那么不論詞匯b相關(guān)的記錄數(shù)為多少，f（a，b)=0，即 NGD（a，b)=∞。

·NGD為非負(fù)數(shù)且對任意詞匯a有NGD（a,a）=0。

·這兩個詞匯概念的相關(guān)度與詞匯間的語義距離成反比，即詞匯語義距離值越小，詞匯的相關(guān)度越大，反之亦然。當(dāng)詞匯語義距離為0時，其相似度為1；詞匯語義距離為∞時，其相關(guān)度為0。

Web服務(wù)描述中有很多組合詞和合成詞，如果用這些合成詞做索引，搜索查詢時很難匹配成功。接下來考慮以下情況。

如果XML模式樹T1和T2之間存在兩對節(jié)點之間的映 射 （i1，j1）和 （i2，j2），其 中 T[i1]=[LocationbyZipCode]，T[j1]=[ZipCode]，T[i2]=[date]，T[j2]=[zone]?？梢钥闯觯?jié)點對（i1，j1）因為標(biāo)簽節(jié)點存在部分的結(jié)構(gòu)相似，顯而易見，它們之間的編輯操作應(yīng)該比節(jié)點對（i2，j2）之間的映射代價要小。而傳統(tǒng)的樹編輯距離算法沒有考慮到標(biāo)簽節(jié)點之間的這種差異，粗略地認(rèn)為所有標(biāo)簽節(jié)點的替換所花費的代價是一樣的，因此是不準(zhǔn)確的。

通過前面的分析，得到了兩個單詞之間的語義距離。標(biāo)簽節(jié)點之間的語義距離應(yīng)該是構(gòu)成標(biāo)簽節(jié)點的幾個單詞之間的語義距離的平均。標(biāo)簽節(jié)點的劃分是依據(jù)大寫字母的劃分原則，然后除去停用詞。這里標(biāo)簽節(jié)點之間語義距離的計算分以下幾種情況。

·如果計算的是類似ValueName和ZipState這樣的標(biāo)簽節(jié)點，構(gòu)成節(jié)點標(biāo)簽的單詞都是各自獨立的，無重復(fù)。標(biāo)簽節(jié)點之間的語義距離就是單詞Value與Zip和State的語義距離以及Name與Zip和State的語義距離的和，除以單詞總數(shù)的一半。

·如果計算的兩個標(biāo)簽節(jié)點的特點與Local-TimeByZipCode和 CityStateToZipCode類似，除去相同的單詞ZipCode，計算的是LocalTime和CityState之間的語義距離。但是它們之間的相似度又比單一的LocalTime和CityState之間的相似度高，因此不能忽略相同單詞的作用。這樣的兩個標(biāo)簽之間的距離就是兩個不同單詞之間的距離再乘以相同單詞對在總單詞樹中的比重，也就是D（a,b）（標(biāo)簽節(jié)點之間的語義距離）×相同單詞數(shù)/總單詞數(shù)。

·如果計算的兩個標(biāo)簽節(jié)點類似LatestDailyValue和DailyValue，相同的單詞就不參與計算，它們之間的距離統(tǒng)一標(biāo)記為1。而總的語義距離就是再乘以相同單詞對在總單詞樹中的比例，即1×相同單詞數(shù)/總單詞數(shù)。

根據(jù)標(biāo)簽節(jié)點之間的距離 D（a,b），由式（4）計算標(biāo)簽節(jié)點之間的語義相似度：

其中，λ是一個可調(diào)節(jié)的參數(shù)，λ值的范圍為（0,1）。利用式（4）可以使得計算得出的相似度在（0，1），因此滿足代價要求的范圍。

而關(guān)于前文約束節(jié)點的消去，對編輯操作產(chǎn)生的影響就是標(biāo)簽節(jié)點權(quán)重的變化，本文參考了參考文獻(xiàn)[20]中的方法。

4 協(xié)作關(guān)系中的服務(wù)發(fā)現(xiàn)

4.1 問題分析

由于網(wǎng)絡(luò)中單個Web服務(wù)的功能簡單，企業(yè)一般都會進(jìn)行服務(wù)的協(xié)作以滿足應(yīng)用流程的集成需求。例如在第1節(jié)的例子中，旅行安排的服務(wù)一般至少包括訂票服務(wù)和酒店預(yù)訂服務(wù)兩種，通過這兩種服務(wù)的相互協(xié)作完成旅行服務(wù)。

協(xié)作關(guān)系中的Web服務(wù)，通過業(yè)務(wù)邏輯的相互協(xié)作，可達(dá)到業(yè)務(wù)增值的目的。在返回給用戶的服務(wù)列表中，用戶期望所選擇的服務(wù)與其他服務(wù)有較好的交際能力。這種交際能力不僅體現(xiàn)出業(yè)務(wù)能力強(qiáng)，而且在完成用戶需求的過程中，該服務(wù)的等級、權(quán)重更高。在服務(wù)協(xié)作關(guān)系分析中，確定一個量化標(biāo)準(zhǔn)來衡量服務(wù)的交際能力是關(guān)鍵問題。

4.2 協(xié)作關(guān)系中服務(wù)的交際能力

由前文的分析可知，Web服務(wù)中的數(shù)據(jù)類型集合和消息集合隱含在服務(wù)的操作列表中，所以把Web服務(wù)簡化為一組服務(wù)操作的集合{opl，op2，…，opn}。Web 服務(wù)提供的功能是通過服務(wù)中的操作列表實現(xiàn)的。而Web服務(wù)的操作又由完成數(shù)據(jù)交流的輸入消息和輸出消息組成。執(zhí)行某一個特定的任務(wù)，并將結(jié)果以消息的形式返回。服務(wù)的操作表示為 opi={(inputi，outputi，i=1,2,…,n)}。其中inputi是該服務(wù)的輸入消息的集合，outputi是該服務(wù)的輸出消息的集合。WSDL文檔定義的消息交換模式有很多，如 in-out、in-multi-out、out-in 等 10 種交換模式。

Web服務(wù)的交際能力是Web服務(wù)功能所有操作的交際能力的綜合。在Web服務(wù)的協(xié)作關(guān)系中，兩個Web服務(wù)的操作可以順利執(zhí)行的前提是源操作的輸出消息outputi與目的操作的輸入消息inputi相匹配。Web服務(wù)的輸出消息與另一個Web服務(wù)輸入消息之間的匹配是兩個Web服務(wù)器連接的紐帶，是服務(wù)之間數(shù)據(jù)交流的關(guān)鍵。

但是如果要求一個服務(wù)操作的輸出集合與另一個服務(wù)的輸入集合完全相似，如同Web服務(wù)組合，這樣的要求太苛刻。在實際應(yīng)用中，也就會失去一些本來可以滿足用戶要求的服務(wù)。例如，一個操作的輸出集合為City、ZipCode和Temperature，假設(shè)網(wǎng)絡(luò)中沒有一個操作的輸入集合與之完全匹配，但如果存在一個操作的輸入集合為City、Weather，顯然，這樣的操作也會滿足需求。因此輸入與輸出不完全相同的服務(wù)也可能存在連接關(guān)系。尤其在企業(yè)的應(yīng)用中，用戶由于專業(yè)知識受限或所處的領(lǐng)域不同，在對所需的服務(wù)描述不夠準(zhǔn)確的情況下，不完全匹配可能更符合實際。

因此服務(wù)操作之間的連接關(guān)系就是源操作的輸出集合與目的操作的輸入集合之間的相似度。相似度的值就是對存在連接關(guān)系的兩個服務(wù)的連接程度的權(quán)重化的衡量。關(guān)于相似度的判斷，同前文在競爭關(guān)系中的計算服務(wù)之間的操作的相似度類似，計算的是源操作的輸入集合中的數(shù)據(jù)類型和目的輸入集合中的數(shù)據(jù)類型的相似度。同樣計算的是兩個服務(wù)操作的數(shù)據(jù)類型所形成的schema樹之間的距離。

網(wǎng)絡(luò)中不同服務(wù)之間的連接關(guān)系，就像人與人之間的聯(lián)系。如果一個人的關(guān)系網(wǎng)很大，并且相互聯(lián)系很頻繁，或者認(rèn)識一個交際能力非常好的人，可以通過他來擴(kuò)大自己的交際圈，本文認(rèn)為這類人的交際能力很好。在社交網(wǎng)中，服務(wù)與服務(wù)之間存在連接關(guān)系，就像人與人之間的聯(lián)系。對于一個服務(wù)，被調(diào)用的次數(shù)越多或者與某個交際能力強(qiáng)的服務(wù)有交互，就認(rèn)為這個服務(wù)的交際能力強(qiáng)。衡量服務(wù)交際能力的思想是基于服務(wù)之間的連接關(guān)系，這個思想剛好與參考文獻(xiàn)[17]中的PageRank思想相似。

利用PageRank的思想對協(xié)作關(guān)系中的Web服務(wù)交際能力進(jìn)行度量，不僅是基于服務(wù)之間的連接關(guān)系，而且該思想滿足了協(xié)作關(guān)系中Web服務(wù)之間交互的2個特性。

·協(xié)作關(guān)系中的遞減屬性：假設(shè)Web服務(wù)1與Web服務(wù)2連接，而Web服務(wù)2又與Web服務(wù)3連接，由于Web服務(wù)3對Web服務(wù)1的交際能力的評斷通過中間服務(wù)的連接傳遞獲得，也就不如Web服務(wù)器2這樣直接與其交互的服務(wù)對其評斷來得準(zhǔn)確。

·協(xié)作關(guān)系中的累加屬性：Web服務(wù)與越多的服務(wù)形成交互連接，就越增強(qiáng)了該Web服務(wù)的交際能力。

在協(xié)作關(guān)系中，基于服務(wù)操作之間的連接，對服務(wù)的交際能力進(jìn)行衡量，通過迭代計算，能夠相對客觀地計算出服務(wù)的交際能力。Web服務(wù)操作的交際能力的計算如下：

服務(wù)與服務(wù)之間的連接關(guān)系與傳統(tǒng)網(wǎng)頁之間的鏈接關(guān)系不同。服務(wù)之間的連接關(guān)系不僅表示服務(wù)之間有連接，同時連接值的大小會影響交際能力的計算，即服務(wù)之間的連接關(guān)系是權(quán)重化的。

綜上所述，網(wǎng)絡(luò)中的服務(wù)存在相互競爭和相互協(xié)作的關(guān)系。在競爭關(guān)系中，解決的是從大量的網(wǎng)絡(luò)服務(wù)中，發(fā)現(xiàn)與用戶需求描述中的文本和結(jié)構(gòu)相似的服務(wù)，得到一組服務(wù)列表。在協(xié)作關(guān)系中，分別計算列表中服務(wù)的交際能力，把網(wǎng)絡(luò)中交際能力好的服務(wù)返回給用戶。通過這兩種關(guān)系實現(xiàn)服務(wù)的發(fā)現(xiàn)，返回最優(yōu)的服務(wù)給當(dāng)前用戶。

5 實驗與分析

因本文提出的是基于WSDL文檔的功能性Web服務(wù)發(fā)現(xiàn)方法，為了證明該方法的有效性，實驗中用到的Web服務(wù)測試數(shù)據(jù)均取自真實的Web服務(wù)庫Webservicelist和xMethods。實驗過程中共搜集了280個來自不同領(lǐng)域的Web服務(wù)，其中包括 1 478個 Web服務(wù)操作，作為實驗中實現(xiàn)Web服務(wù)發(fā)現(xiàn)和搜索的服務(wù)庫。鑒于當(dāng)前Web服務(wù)發(fā)現(xiàn)領(lǐng)域沒有統(tǒng)一的衡量標(biāo)準(zhǔn)，本文利用信息檢索領(lǐng)域的召回率和準(zhǔn)確率作為Web服務(wù)發(fā)現(xiàn)結(jié)果的衡量標(biāo)準(zhǔn)。

實驗流程如圖6所示。

圖6 實驗的總體流程

實驗中獲取的部分WSDL文檔的信息見表2,其中包括服務(wù)的編號、服務(wù)描述文檔的URL、服務(wù)的名稱、服務(wù)提供商以及服務(wù)所在的國家。

本文采用通用的WSDL4J技術(shù)對搜索到的WSDL文檔進(jìn)行解析，WSDL4J是一個開源的工具包，可以解析出WSDL文檔所有的信息，如圖7所示。

圖7 WSDL文檔解析

實驗過程中其他模塊的實現(xiàn)如前文所述，其中對特征的提取、標(biāo)簽節(jié)點的劃分都基于經(jīng)典算法實現(xiàn)。實驗過程中將30個Web服務(wù)、189個操作作為用戶的需求，其他的服務(wù)作為服務(wù)發(fā)現(xiàn)過程中的服務(wù)庫。實驗的召回率和查準(zhǔn)率取這30次實驗的平均。參考文獻(xiàn)[9,21]同樣是實現(xiàn)基于WSDL語言的服務(wù)發(fā)現(xiàn)。參考文獻(xiàn)[9]所使用的Web服務(wù)發(fā)現(xiàn)方法是根據(jù)服務(wù)功能通過WSDL文檔對服務(wù)進(jìn)行分類，將該方法記為CWSD；參考文獻(xiàn)[21]采用改進(jìn)的操作相似性度量方法，記為MOSM；本文的方法記為SWSD。實驗過程中，在實驗的前期對實驗的Web服務(wù)進(jìn)行分類，依據(jù)參考文獻(xiàn)[22]中的方法分為 8 類：（1）金融類服務(wù)；（2）開發(fā)類服務(wù)；（3）政府/正常類服務(wù)；（4）旅游類服務(wù)；（5）電子商務(wù)類服務(wù)；（6）實體銷售類服務(wù)；（7）股票/證券類服務(wù)：（8）驗證類服務(wù)。關(guān)于服務(wù)發(fā)現(xiàn)結(jié)果的召回率和查準(zhǔn)率，實驗的結(jié)果如圖8、圖9所示。

表2 Web服務(wù)信息

圖8 不同服務(wù)領(lǐng)域的查準(zhǔn)率比較

圖9 不同服務(wù)領(lǐng)域的召回率比較

從圖8、圖9中可以看出，在查準(zhǔn)率和召回率上，本文的方法都有明顯提高?？梢钥闯霰疚牡姆椒ǔ浞掷昧薟SDL的特點，考慮了Web服務(wù)競爭關(guān)系和協(xié)作關(guān)系的特性，使返回給用戶的服務(wù)就是用戶傾向的服務(wù)，而不是單純追求返回服務(wù)的Top-K集。

6 結(jié)束語

為了解決Web服務(wù)器發(fā)現(xiàn)的難題，本文考慮到網(wǎng)絡(luò)中某個服務(wù)在調(diào)用過程中會與其他的服務(wù)形成相互競爭或相互協(xié)作的關(guān)系，實現(xiàn)了一種虛擬社交化的服務(wù)發(fā)現(xiàn)與選擇方法。在相互競爭的關(guān)系中，首先通過分析用戶歷史調(diào)用服務(wù)情況，同時結(jié)合當(dāng)前用戶的需求，計算用戶與服務(wù)之間文本描述信息的相似度，然后再基于WSDL的特點，構(gòu)建Web服務(wù)操作的schema樹，利用改進(jìn)的樹編輯距離算法確定服務(wù)之間的結(jié)構(gòu)相似度。其次對于某些用戶的復(fù)雜需求，需要服務(wù)之間的相互協(xié)作才能完成。在相互協(xié)作的關(guān)系中，考慮的是服務(wù)的交際能力，這種交際能力反映在服務(wù)之間的連接上。最后把交際能力強(qiáng)的服務(wù)推薦給當(dāng)前用戶。因此本文利用服務(wù)交互調(diào)用過程中的這兩個特性，從相互競爭和相互協(xié)作的關(guān)系中尋找滿足用戶需求的服務(wù)。通過將本文的方法與其他方法在召回率和查準(zhǔn)率上進(jìn)行比較，驗證了本文方法的可行性和高效性。

參考文獻(xiàn)

1 吳朝暉，鄧水光，吳健.服務(wù)計算與技術(shù).杭州:浙江大學(xué)出版社,2009

2 Barakat L,Miles S,Luck M.Efficient correlation-aware service selection.Proceedings of IEEE 19th International Conference on Web Service,Honolulu,HI,2012:1～8

3 Maamar Z,Wives L K,Badr Y,et al.LinkedWS:a novel web services discovery model based on the metaphor of“social networks”.Simulation Modeling Practice and Theory,2011,19(1):121～132

4 Maamar Z,Hacid H,Huhns M N.Why Web Services need social networks.Internet Computing,IEEE,2011,15(2):90～94

5 Maamar Z,Wives L K,Badr Y,et al.Even Web Services can socialize:a new service-oriented social networking model.Proceedings of Intelligent Networking and Collaborative Systems 2009,Madrid,Spain,2009:24～30

6 Maamar Z,Sheng Q Z,Tata S,et al.Towards an approach to sustain Web Services high-availability using communities of Web Services.International Journal of Web Information Systems,2009,5(1):32～55

7 Kokash N,Van Den Heuvel W J,D’Andrea V.Leveraging Web Services discovery with customizable hybrid matching.Lecture Notes in Computer Science,2006,42(94):522～528

8 Platzer C,Dustdar S.A vector space search engine for Web Services.Proceedings of 3rd European Conference on Web Services,Orlando,Florida,USA,2005:62～71

9 Elgazzar K,Hassan A E,Martin P.Clustering WSDL documents to bootstrap the discovery of Web Services.Proceedings of IEEE International Conference on Web Services,Miami,USA,2010:147～154

10 Hao Y,Zhang Y,Cao J.Web Services discovery and rank:an information retrieval approach.Future Generation Computer Systems,2010,26(8):1053～1062

11 Rajagopal S,Selvi S,Rajagopalan M R,et a1.Semantic grid service discovery approach using clustering of service ontologies.Proceedings of IEEE TENCON,Hong Kong,China,2006:1～4

12 W3C Group.Web Services description language (WSDL)1.1 W3C note 15.http://www.w3.org/TR/wsdl.html

13 Liu W,Wong W.Web Service clustering using text mining techniques.International Journal of Agent-Oriented Software Engineering,2009,3(1):6～26

14 Thomas E.SOA服務(wù)設(shè)計原則.郭耀譯.北京:人民郵電出版社,2009

15 鄧水光，尹建偉，李瑩等.基于二分圖匹配的語義Web服務(wù)器發(fā)現(xiàn)方法.計算機(jī)學(xué)報，2008,31(8):1364～1375

16 Nierman A,Jagadish H V.Evaluating structural similarity in XML documents.Proceedings of 5th Int’l Workshop on the Web and Databases,Madison,Wisconsin,USA,2002:61～66

17 Xie T,Sha C,Wang X,et al.Approximate top-k structural similarity search over XML documents.Proceedings of Frontiers of WWW Research and Development-AP Web 2006,Heidelberg,Berlin,2006:319～330

18 Brin S,Page L.The anatomy of a large-scale hyper textual Web search engine.Computer Networks and ISDN Systems,1998,30(1):107～117

19 張玉芳，艾東梅，黃濤等.結(jié)合編輯距離和Google距離的語義標(biāo)注方法.計算機(jī)應(yīng)用研究，2010,27(2):555～562

20 Sarwar B,Karypis G,Konstan J,et al.Item-based collaborative filtering recommendation algorithms.Proceedings of 10th Int’l WWW Conference,Hong Kong,China,2001:1～5

21 何玲娟,劉連臣,吳澄.一種改進(jìn)的基于WSDL描述的操作相似性度量方法.計算機(jī)學(xué)報,2008,31(8):1331～1339

22 Saha S,Murthy C A,Pal S K.Classification of Web Services using tensor space model and mouth ensemble classifier.Proceedings of the 17th Int’l Symp on Methodologies for Intelligent Systems,Washington DC,USA,2008:508～513