王慧英，周愷卿，周 輝

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

1 引言

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

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

2 Petri網(wǎng)和QOS計算下Web服務(wù)模糊匹配

2.1 Web服務(wù)過程模型的Petri網(wǎng)轉(zhuǎn)換

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

2.2 Web服務(wù)的相似度計算

Petri網(wǎng)即一種有向圖，本文在計算Petri網(wǎng)的相似度時，考慮了網(wǎng)絡(luò)架構(gòu)、節(jié)點與變遷的語義標準[1]。

設(shè)定∑i={S1，T1，F(xiàn)1}和∑j={S2，T2，F(xiàn)2}分別表示服務(wù)webi與webj過程模型形式化的Petri網(wǎng)，映射M1：T1→T2即從∑i節(jié)點集到∑j節(jié)點集的部分單映射，集合sumt即依靠映射M1中每一個節(jié)點集合構(gòu)成。P1表示集合sumt內(nèi)的節(jié)點占據(jù)∑i和∑j內(nèi)節(jié)點總量的比值。

(1)

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

(2)

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

(3)

其中，P4代表映射M1與M2內(nèi)所有節(jié)點的平均語義[3]相似度，而Sim(n1，n2)能夠被描述成節(jié)點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)代表權(quán)重。

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

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

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}內(nèi)的字符串當作定點，使用式(9)計算字符串間存在的語義相似度。同時依靠該相速度當做邊的權(quán)重，組建帶權(quán)二分圖，利用二分圖最優(yōu)匹配方法，得到最優(yōu)匹配子圖

(9)

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

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

2.3 Web服務(wù)Qos指標選擇

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

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

2.3.1 專家對服務(wù)Qos的評測

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

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

(10)

2)通過描述優(yōu)劣性的語言變量[9]，對所有Web服務(wù)的Qos指標表現(xiàn)狀況進行評測，以構(gòu)成一種評測矩陣。

(11)

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

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

(12)

其相似度為：

(13)

(14)

(15)

4)綜合專家的意見

Qos指標關(guān)鍵程度的意見：

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

(16)

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

(17)

2.3.2 用戶偏好對服務(wù)原則的評測

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

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

(18)

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

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

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

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

(19)

(20)

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

(21)

2.4 Web服務(wù)模糊匹配

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

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

(22)

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

依靠權(quán)重結(jié)合用戶對Web服務(wù)的評分，以完成對Web服務(wù)模糊匹配的目的。

3 實驗證明

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

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

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

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

圖2 不同的Web服務(wù)數(shù)匹配最近似比

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

4 結(jié)束語

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