基于相似度特征的Web服務(wù)匹配算法

王慧英，周愷卿，周 輝

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

1 引言

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

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

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

(4)

(5)

通過(guò)式(4)與(5)計(jì)算，能夠得到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)重。

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

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

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

(7)

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

(8)

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

2)將字符串集合A={Stri1，Stri2，…，Strip}與B={Strj1，Strj2，…，Strjq}內(nèi)的字符串當(dāng)作定點(diǎn)，使用式(9)計(jì)算字符串間存在的語(yǔ)義相似度。同時(shí)依靠該相速度當(dāng)做邊的權(quán)重，組建帶權(quán)二分圖，利用二分圖最優(yōu)匹配方法，得到最優(yōu)匹配子圖

(9)

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

4)針對(duì)M1內(nèi)的所有映射(Ta，Tb)，依靠變遷Ta，Tb相應(yīng)的輸入?yún)?shù)集合ina、inb內(nèi)的參數(shù)當(dāng)作頂點(diǎn)，以參數(shù)間的語(yǔ)義相似度當(dāng)做邊的權(quán)重，組建帶全二分圖，在此基礎(chǔ)上以獲得參數(shù)的最優(yōu)匹配子圖[7]，把最優(yōu)匹配子圖內(nèi)語(yǔ)義相似度超過(guò)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指標(biāo)選擇

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

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

2.3.1 專家對(duì)服務(wù)Qos的評(píng)測(cè)

本文通過(guò)直覺(jué)模糊語(yǔ)言變量對(duì)Web服務(wù)的Qos指標(biāo)進(jìn)行評(píng)測(cè)，專家對(duì)服務(wù)Qos的評(píng)測(cè)流程如下所示：

1)通過(guò)描述關(guān)鍵性的語(yǔ)言變量，對(duì)Qos指標(biāo)的關(guān)鍵程度進(jìn)行評(píng)測(cè)，以構(gòu)成一種評(píng)測(cè)矢量：

(10)

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

(11)

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

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

(12)

其相似度為：

(13)

(14)

(15)

4)綜合專家的意見(jiàn)

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

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

(16)

Qos指標(biāo)滿意程度矩陣如下：

(17)

2.3.2 用戶偏好對(duì)服務(wù)原則的評(píng)測(cè)

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

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

(18)

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

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

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

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

(19)

(20)

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

(21)

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

擬定請(qǐng)求服務(wù)SR={OR={oi}，IR={ij}}，廣告服務(wù)SA={OA={oi}，IA={ij}}。概念的相似度是非對(duì)稱的，因此以一個(gè)網(wǎng)絡(luò)請(qǐng)求服務(wù)當(dāng)做例子。其中網(wǎng)絡(luò)請(qǐng)求結(jié)果是服務(wù)的輸出，在提供的服務(wù)輸出是請(qǐng)求服務(wù)輸出的直接子類時(shí)，服務(wù)是匹配的，在某種意義上來(lái)說(shuō)，服務(wù)的輸出以及輸出正好呈現(xiàn)相反方向。假如請(qǐng)求服務(wù)輸入即供給服務(wù)輸入的直接子類，也就是用戶所擁有的數(shù)據(jù)是所提供的服務(wù)所需要輸入的一種具體表現(xiàn)，所以也是匹配的；另一方面，假如請(qǐng)求服務(wù)輸入總量不超過(guò)提供服務(wù)輸入總量，服務(wù)可能不會(huì)滿足需求，而假如請(qǐng)求服務(wù)的輸出總量沒(méi)超過(guò)提供服務(wù)的總量，則不會(huì)干擾為用戶提供其所需要的服務(wù)內(nèi)容。最后，因?yàn)橛脩糇詈蟮哪康募传@取所需服務(wù)，所以通常狀態(tài)下服務(wù)的輸出匹配程度對(duì)整體服務(wù)的匹配程度會(huì)起到更大的作用?；谏鲜龇治?，本文提出以下方法來(lái)計(jì)算兩種服務(wù)的相似度：

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

(22)

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

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

3 實(shí)驗(yàn)證明

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

圖1 所提算法匹配的時(shí)間耗費(fèi)

通過(guò)圖1能夠看出，使用所提算法在Web服務(wù)數(shù)為5時(shí)，其耗時(shí)最低，隨著Web服務(wù)數(shù)的增多，算法在時(shí)間耗費(fèi)上的數(shù)值也會(huì)不斷提升，但其提升的速度并不算高。這是因?yàn)樗崴惴?，?huì)依靠通過(guò)對(duì)Qos指標(biāo)的選擇，來(lái)減少算法在獲取Qos指標(biāo)時(shí)的時(shí)間，以此進(jìn)一步提升算法了的整體運(yùn)行效率。

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

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

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

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

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