基于相似度特征的Web服務匹配算法

王慧英，周愷卿，周 輝

(1.重慶工程學院 計算機與物聯網學院，重慶 400056；2.吉首大學 信息科學與工程學院，湖南 吉首 416000；3.湖南中醫藥大學，湖南 長沙 410208)

1 引言

由于Web服務技術的高速發展與標準服務的出現，互聯網內中的Web服務數量越來越多，質量越來越高，因此怎樣從海量互聯網服務內搜索和用戶要求一致的Web服務就變成了廣受關注的一個問題。所謂服務發現就是憑借Web服務請求者的需求，從眾多Web服務內搜索出可以滿足請求者Web服務的過程。Web服務匹配即將服務請求者所需要的服務描述和已有的進行對比，以搜索是否存在已有的Web服務。目前，Web服務的描述文件主要是以調用操作的形式對Web服務進行處理，缺乏對Web服務功能的描述，其服務注冊機制憑借服務注冊信息與關鍵詞進行匹配服務，但這種服務匹配機制并不能全面滿足用戶需求。

針對上述問題，提出一種基于Petri網和QOS計算的Web服務模糊匹配算法，以期提升Web服務模糊匹配效果。

2 Petri網和QOS計算下Web服務模糊匹配

2.1 Web服務過程模型的Petri網轉換

OWL-S表示Web服務的過程模型，該模型具有三種主要方向即：控制流、狀態轉移與信息轉換。信息轉化用IO描述，也為Web服務的輸出與輸入；狀態轉移利用PE描述，也表示Web服務的某種狀態；而控制流代表互相合作時所有服務間的時序關系，因此可以將OWL-S看作一種流程模型，其描述了包含服務之間存在的執行順序關系，因此能夠通過該模型將Web服務轉換成Petri網表示。

2.2 Web服務的相似度計算

Petri網即一種有向圖，本文在計算Petri網的相似度時，考慮了網絡架構、節點與變遷的語義標準[1]。

設定∑i={S1，T1，F1}和∑j={S2，T2，F2}分別表示服務webi與webj過程模型形式化的Petri網，映射M1：T1→T2即從∑i節點集到∑j節點集的部分單映射，集合sumt即依靠映射M1中每一個節點集合構成。P1表示集合sumt內的節點占據∑i和∑j內節點總量的比值。

(1)

同理，映射M3：F1→F2代表∑i庫所變遷集至∑j庫所庫所集的部分單映射[2]，集合sump通過映射M3內存在的全部庫所構成，P2代表集合sump內庫所變遷集占∑i與∑j內庫所總量的比值。

(2)

映射M3：F1→F3代表∑i流集合至∑j流集合的部分單映射，集合sume通過映射M3內所存在的全部流構成，P3代表集合sume內的流占∑i與∑j內流總量的比值。

(3)

其中，P4代表映射M1與M2內所有節點的平均語義[3]相似度，而Sim(n1，n2)能夠被描述成節點n1和n2的語義相似度。

(4)

(5)

通過式(4)與(5)計算，能夠得到webi與webj的模型相似度是：

S(∑i，∑j)=ω1×P1+ω2×P2+ω3×P3+ω4×P4

(6)

式中，ω1，ω2，ω3，ω4(ω1+ω2+ω3+ω4=1)代表權重。

計算∑i與∑j的節點集、變遷集與流集[4]間具有多種映射，是為了便于查找Petri網內庫所與變遷坐標之間的關聯，庫所、流與變遷間的映射能夠通過以下方法獲得：

1)通過服務webi與webj的Petri網模型∑i與∑j生成Petri網的語言表達式：

L(∑i)=Str+StrΩ+…+Strjm+…+Strjp

(7)

L(∑j)=Stj1r+Strj2+…+Strjn+…+Strjq

(8)

式中，Strjm、Strjn均為利用變遷語義[5]表示的本體字符串。

2)將字符串集合A={Stri1，Stri2，…，Strip}與B={Strj1，Strj2，…，Strjq}內的字符串當作定點，使用式(9)計算字符串間存在的語義相似度。同時依靠該相速度當做邊的權重，組建帶權二分圖，利用二分圖最優匹配方法，得到最優匹配子圖

(9)

3)對最優匹配子圖內的響應速度超過某種閾值的字符串Strjm、Strjn，憑借字符串間的編輯距離[6]方法對其進行處理，在此過程中需要考慮字符的前后位置關系，以此獲得其最差公共子串str，并分別記錄str內的所有字符在Strjm、Strjn內相應坐標的字符a、b，把a、b在Petri網內相應的變遷(Ta，Tb)融入映射M1內。

4)針對M1內的所有映射(Ta，Tb)，依靠變遷Ta，Tb相應的輸入參數集合ina、inb內的參數當作頂點，以參數間的語義相似度當做邊的權重，組建帶全二分圖，在此基礎上以獲得參數的最優匹配子圖[7]，把最優匹配子圖內語義相似度超過s的參數(x，y)融入映射M2內，并將鏈接Ta和x的流f1以及鏈接Tb和y的流f2構成的流(f1，f2)映射至M3內，以此處理Ta、Tb相應的輸出參數集合outa與outb。

2.3 Web服務Qos指標選擇

Web服務的Qos指標較多且復雜，對大多數用戶來說，一方面，他們通常只關注其中的一些指標，但是服務的總體質量是通過多個指標得出的；另一方面，他們通常并不存在專業的Web服務知識，所以不能要求他們對所有Qos指標給出合理的反饋以及請求。因此本文提出一種能夠同時有效地考慮這兩種情況的Web服務模糊匹配方法，即融合了專家意見與用戶偏好的Web服務Qos選擇方法。

專家通過直覺模糊語言變量對Web服務的所有Qos指標進行評測，將其結果儲存到數據中心內。Web服務功能選擇為用戶供給一種待選服務列表，用戶通過直覺模糊語言變量表述對服務Qos的期望，算法把用戶的偏好作用到專家意見內，構成一種新的評測矩陣，同時對評測矩陣進行集成[8]，最后為服務的Qos獲得一種評分，用戶在結束服務之后，還能夠對服務質量進行總體評測，形成第二次評分，Qos選擇算法綜合上述兩種評分，進而為用戶選擇綜合評分最高的服務。

2.3.1 專家對服務Qos的評測

本文通過直覺模糊語言變量對Web服務的Qos指標進行評測，專家對服務Qos的評測流程如下所示：

1)通過描述關鍵性的語言變量，對Qos指標的關鍵程度進行評測，以構成一種評測矢量：

(10)

2)通過描述優劣性的語言變量[9]，對所有Web服務的Qos指標表現狀況進行評測，以構成一種評測矩陣。

(11)

3)依靠相似度運算專家的意見權重，給出Web服務的Qos總體評測的結果，需要盡可能地映射多數專家的意見，所以假如專家的意見都非常相似，就說明意見越有分量，也表明其權重更高。

擬定x，y代表兩種模糊值，二者的直覺模糊數為x=[μx，vx]，y=[μy，vy]其海明距離為：

(12)

其相似度為：

(13)

(14)

(15)

4)綜合專家的意見

Qos指標關鍵程度的意見：

W={W1，W2，…，Wk，…，Wn}

(16)

Qos指標滿意程度矩陣如下：

(17)

2.3.2 用戶偏好對服務原則的評測

用戶偏好會在服務選擇過程中影響專家綜合意見結果，包括Qos指標的關鍵程度W與所有服務的Qos指標的滿意程度G。如果用戶對第k種指標給出了自身的意見，就能夠認定其關鍵程度是Ik，同時利用該思想計算Vk，Ik與Vk等不同的語言變量，其能夠對W與G產生以下影響：

Wk=Wk∨Ik=[max(μWk，μIk)，min(vWk，vIk)]

(18)

這樣，用戶所關注的Qos指標會被得到一定程度的重視，并且假如服務的Qos指標能夠滿足用戶要求，其評測評分就會被增加，但如果Qos指標不能滿足客戶要求，其評測評分也會被相應減小。

依靠以下方法獲得服務的Qos綜合排名：

W={W1，W2，…，Wn}反映了結合專家建議以及用戶偏好的Qos關鍵程度整體意見，對Wi進行非模糊化處理獲得ωi，ωi映射了第i種指標的權重。

根據指標權重，則存在G′ij=ωj×G′11，其表示映射了指標j對服務i的貢獻，G′i代表服務i的整體表現。則存在：

(19)

(20)

式中，L(x)=1-μx-vx，L(y)=1-μy-vy，m種候選服務的排序適量e={e1，e2，…，em}，其運算過程如下所示：

(21)

2.4 Web服務模糊匹配

擬定請求服務SR={OR={oi}，IR={ij}}，廣告服務SA={OA={oi}，IA={ij}}。概念的相似度是非對稱的，因此以一個網絡請求服務當做例子。其中網絡請求結果是服務的輸出，在提供的服務輸出是請求服務輸出的直接子類時，服務是匹配的，在某種意義上來說，服務的輸出以及輸出正好呈現相反方向。假如請求服務輸入即供給服務輸入的直接子類，也就是用戶所擁有的數據是所提供的服務所需要輸入的一種具體表現，所以也是匹配的；另一方面，假如請求服務輸入總量不超過提供服務輸入總量，服務可能不會滿足需求，而假如請求服務的輸出總量沒超過提供服務的總量，則不會干擾為用戶提供其所需要的服務內容。最后，因為用戶最后的目的即獲取所需服務，所以通常狀態下服務的輸出匹配程度對整體服務的匹配程度會起到更大的作用。基于上述分析，本文提出以下方法來計算兩種服務的相似度：

Sim(SA，SR)=wi·maxBipart(IR，IA)

(22)

其中，|IA|，|IR|和|OA|，|OR|分別代表廣告服務和請求服務的輸出以及輸入概念總量。wi和wo代表輸入與輸出概念機相似度對整體服務相似度的影響權重。

依靠權重結合用戶對Web服務的評分，以完成對Web服務模糊匹配的目的。

3 實驗證明

為了證明所提算法的有效性，進行實驗，實驗的測試環境是：Intel Pentiuym4，2.8GHz，512MB RAM。Windows XP與J2SDK1.5，實驗程序通過Java語言開發，鑒于當前沒有相關標準平臺與數據集，因此每個Web候選服務的服務質量參數與語義匹配值是依靠隨機方法產生的。對Web服務數為5，10，15，20，25，30的服務組合流程進行實驗，所有Web服務都存在4中Qos指標值，具體的指標值會放在一定范圍中隨機生成。擬定6種不同的Web服務數的服務組合流程，所有服務流程都會采用所提算法運行10次，平均時間耗費結果如圖1所示。

圖1 所提算法匹配的時間耗費

通過圖1能夠看出，使用所提算法在Web服務數為5時，其耗時最低，隨著Web服務數的增多，算法在時間耗費上的數值也會不斷提升，但其提升的速度并不算高。這是因為所提算法，會依靠通過對Qos指標的選擇，來減少算法在獲取Qos指標時的時間，以此進一步提升算法了的整體運行效率。

對于上述6種不同Web服務數的服務組合流程，所有流程通過所提算法進行1000次，所得到的匹配結果最靠近的平均比例如圖2所示。

圖2 不同的Web服務數匹配最近似比

通過圖2的結果能夠看出，服務組合流程匹配結果最靠近最優解的比率在97.3%以上，能夠使Web服務匹配能夠達到最大值，同時Qos指標滿足用戶的需求，可以很好的實了Web服務的模糊匹配。

4 結束語

為了使用戶的Web服務過程更為便捷，提出一種基于Petri網和QOS計算的Web服務模糊匹配算法，實驗結果表明該算法有著匹配效率較高的優點。為了進一步為用戶提供個性化服務，未來的工作會嘗試設計更為有效的服務匹配方法，融合動態描述邏輯的推理功能與可判斷性，進一步優化語義匹配方法，以更好的推動Web服務的動態組合，以期可以進一步提升用戶滿意度，促進Web服務領域的進一步發展。