基于服務(wù)組合簇集的Web服務(wù)發(fā)現(xiàn)

姚 喜，寧玉輝，趙淑芳，孫 磊

(1.山東省水利勘測(cè)設(shè)計(jì)院 勘測(cè)處，山東 濟(jì)南 250013；2.山東省人防指揮保障中心 應(yīng)急保障科， 山東 濟(jì)南 250014；3.山東協(xié)和學(xué)院 計(jì)算機(jī)學(xué)院，山東 濟(jì)南 250107)

0 引 言

隨著信息技術(shù)的不斷發(fā)展，Web服務(wù)種類與數(shù)量不斷增多。這一方面提高了Web服務(wù)滿足用戶需求的能力；另一方面也增大了服務(wù)發(fā)現(xiàn)和服務(wù)組合的計(jì)算難度，對(duì)服務(wù)查準(zhǔn)率和服務(wù)計(jì)算效率帶來(lái)了一定影響[1]。

為了提高服務(wù)發(fā)現(xiàn)效率，服務(wù)池、服務(wù)簇[2]和服務(wù)社區(qū)[3]等概念被提出。其思想為縮小服務(wù)發(fā)現(xiàn)基數(shù)，但因Web服務(wù)數(shù)量不斷增多，單一依靠服務(wù)聚類顯然不能有效滿足用戶需求。為了提高服務(wù)發(fā)現(xiàn)精度，基于Qos的服務(wù)發(fā)現(xiàn)方法被提出[4,5]。因Web服務(wù)Qos屬性組成較為復(fù)雜，且Qos中的屬性賦值缺少統(tǒng)一標(biāo)準(zhǔn)，影響了技術(shù)應(yīng)用效果。文獻(xiàn)[6]在進(jìn)行服務(wù)發(fā)現(xiàn)時(shí)，將“語(yǔ)義”引入到Web服務(wù)發(fā)現(xiàn)中，定義了服務(wù)本體、構(gòu)建了本體詞匯樹；進(jìn)而基于輸入輸出參數(shù)的相似度比較，發(fā)現(xiàn)與用戶需求匹配度最優(yōu)的Web服務(wù)。因服務(wù)本體較為抽象，其形式化定義還需要進(jìn)一步清晰化。文獻(xiàn)[7]利用Petri網(wǎng)對(duì)Web服務(wù)進(jìn)行形式化建模，將Web服務(wù)的輸入、輸出參數(shù)形式化為Petri網(wǎng)的輸入庫(kù)所和輸出庫(kù)所，統(tǒng)一了Web輸入、輸出接口。此類方法提高了服務(wù)查準(zhǔn)率，但對(duì)于優(yōu)化服務(wù)查找效率缺少考慮。另外，粒子群[8]、遺傳算法[9]、神經(jīng)網(wǎng)絡(luò)[10]等智能尋優(yōu)技術(shù)被引入，但也存在諸如粒子群算法在Web服務(wù)發(fā)現(xiàn)中容易陷入局部最優(yōu)解等問題。

在上述背景下，本文提出了一種基于服務(wù)組合簇集的Web服務(wù)組合綁定方法。給出了Web服務(wù)、服務(wù)組合簇、五維坐標(biāo)系、用戶需求、用戶滿意度等概念的形式化定義，利用邏輯Petri網(wǎng)(LPN)[11]對(duì)Web服務(wù)進(jìn)行了形式化描述，構(gòu)建了面向Web服務(wù)集合的LPN模型，進(jìn)而形成了服務(wù)組合庫(kù)。在面向五維坐標(biāo)系的Web服務(wù)坐標(biāo)映射基礎(chǔ)上構(gòu)建了Web服務(wù)組合簇集合；在考慮Web服務(wù)最大并發(fā)數(shù)的基礎(chǔ)上，面向多用戶需求對(duì)基于服務(wù)組合簇集合的服務(wù)組合發(fā)現(xiàn)方法進(jìn)行了闡述。最后，實(shí)驗(yàn)驗(yàn)證了本文技術(shù)的有效性及先進(jìn)性。

1 構(gòu)建Web服務(wù)組合簇集合

1.1 構(gòu)建Web服務(wù)集合的邏輯Petri網(wǎng)模型

定義1 Web服務(wù)：五元組Wservice=(Identity,Inputs,Outputs,QoS,Com) 為一個(gè)Web服務(wù)，其中，

(1)Identity唯一標(biāo)識(shí)了一個(gè)Web服務(wù)；

(2)Inputs={Input1,Input2,…,Inputj} 標(biāo)識(shí)了Web服務(wù)的輸入?yún)?shù)集；

(3)Outputs={Output1,Output2,…,Outputk} 標(biāo)識(shí)了Web服務(wù)的輸出參數(shù)集；

(4)QoS標(biāo)識(shí)了此Web服務(wù)的服務(wù)質(zhì)量，且0≤QoS≤1，規(guī)定此值越大則代表服務(wù)質(zhì)量情況越優(yōu)；

(5)Com標(biāo)識(shí)了此Web服務(wù)的最大并發(fā)執(zhí)行數(shù)，且1

假設(shè)一個(gè)Web服務(wù)集合由若干Web服務(wù)組成，對(duì)Web服務(wù)集合進(jìn)行形式化建模，首先要對(duì)單個(gè)Web服務(wù)進(jìn)行形式化建模，其方法如算法1所示。

算法1：Web服務(wù)的邏輯Petri網(wǎng)建模算法

輸入：一個(gè)Web服務(wù)Wservicem=(Identity,Inputs,Outputs,Qos,Com)。

輸出：Web服務(wù)的邏輯Petri網(wǎng)模型。

(1)新建一個(gè)邏輯Petri網(wǎng)LPNa=(P,T;F,fI,fO,M)。 假設(shè)Wservicem.Inputs={Input1,Input2,…,Inputi}，Wservicem.Outputs={Output1,Output2,…,Outputj}， 在LPNa中新建一個(gè)變遷t∈TD，標(biāo)記為Wservicem.Identity；令t的前置庫(kù)所有i個(gè)，分別標(biāo)記為Input1,Input2,…,Inputi， 后置庫(kù)所有j個(gè)，分別標(biāo)記為Output1,Output2,…,Outputj。

(2)遍歷LPNa.P，假設(shè)當(dāng)前元素為pi，若pi的標(biāo)記為a，且a還被pj∈LPNa.P標(biāo)記，且pj不等于pi，則在LPNa.P中刪除pi，并將與庫(kù)所pi相連的弧連接到庫(kù)所pj上。令LPNa的初始標(biāo)識(shí)LPNa.M0全部清零。

(3)輸出邏輯Petri網(wǎng)LPNa。

算法1給出了Web服務(wù)的LPN模型構(gòu)建方法，將Web服務(wù)的服務(wù)動(dòng)作形式化為邏輯Petri的變遷觸發(fā)動(dòng)作，將Web服務(wù)的輸入、輸出參數(shù)分別映射為邏輯Petri網(wǎng)變遷的前置庫(kù)所和后置庫(kù)所。Web服務(wù)集合的LPN構(gòu)建方法如算法2所示。

算法2：Web服務(wù)集合的邏輯Petri網(wǎng)建模算法

輸入：Web服務(wù)集合Q。

輸出：Web服務(wù)集的邏輯Petri網(wǎng)模型。

(1)新建一個(gè)邏輯Petri網(wǎng)LPNa=(P,T;F,fI,fO,M)。 假設(shè)Web服務(wù)集Q={Webservice1,Webservice2,…,Webservicem}， 則由算法1為Web服務(wù)集合中的全部Web服務(wù)構(gòu)建LPN模型，假設(shè)得到LPN模型集合LPNs={LPN1,LPN2,…,LPNm}。

(2)將LPN集合中的m個(gè)Web服務(wù)形式化模型合并到LPNa中。首先，將LPNs中所有的變遷合并到LPNa.T中，即LPNa.T=LPNa.T∪LPN1.T∪LPN2.T∪…∪LPNm.T； 將LPNs中所有的庫(kù)所、弧合并到LPNa，基本原理同上。

(3)遍歷LPNa.P，假設(shè)當(dāng)前元素為pi，若pi的標(biāo)識(shí)為a，且a還被pj∈LPNa.P標(biāo)識(shí)，且pj不等于pi，則在LPNa.P中刪除pi，與pi相連的弧連接到pj上。令LPNa的初始標(biāo)識(shí)LPNa.M0全部清零。

(4)輸出邏輯Petri網(wǎng)LPNa。

算法2給出了Web服務(wù)集合的LPN模型構(gòu)建方法，將Web服務(wù)集合中的元素分別進(jìn)行LPN建模后，再將多個(gè)LPN模型的合并，進(jìn)而生成Web服務(wù)集合的LPN模型。

1.2 構(gòu)建Web服務(wù)組合庫(kù)

定義2 服務(wù)組合庫(kù)：兩元組Scomlry=(C_LPNs,C_Relations) 為一個(gè)服務(wù)組合庫(kù)，其中，

(1)C_LPNs為Web服務(wù)集的邏輯Petri網(wǎng)模型；

(2)C_Relations為一個(gè)有限集，標(biāo)識(shí)了Web服務(wù)集的邏輯Petri網(wǎng)模型中的輸入?yún)?shù)、輸出參數(shù)、Web服務(wù)ID序列、Qos之間的關(guān)系；

(3)C_Relations中元素的格式定義為=。 其含義為：如果對(duì)于Web服務(wù)集的邏輯Petri網(wǎng)模型，服務(wù)輸入?yún)?shù)為Inputa、Inputb、…、Inputc，則輸出參數(shù)為Outputd、Outpute、…、Outputf，需觸發(fā)的變遷序列為tg,th,…,ti， 此Web服務(wù)組合的服務(wù)質(zhì)量值為Qos，為所調(diào)用Web服務(wù)平均服務(wù)質(zhì)量，CID唯一標(biāo)識(shí)此服務(wù)組合。

由定義2可知，服務(wù)組合庫(kù)集成了面向Web服務(wù)集合的服務(wù)組合所有情況，并融入服務(wù)組合質(zhì)量屬性，其構(gòu)建方法如算法3所示。

算法3：服務(wù)組合庫(kù)構(gòu)建算法

輸入：Web服務(wù)集及其邏輯Petri網(wǎng)模型LPNi。

輸出：服務(wù)組合庫(kù)Scomlry。

(1)新建一個(gè)服務(wù)組合庫(kù)Scomlry，令C_LPNs為L(zhǎng)PNi。假設(shè)LPNi中所有變遷的前置庫(kù)所集合為P={p1,p2,…,pj}， 令p1,p2,…,pj的組合情況有e種，分別為y1,y2,…,ye， 依次遍歷e種組合情況。

(2)假設(shè)當(dāng)前元素為yi，新建LPNi的初始標(biāo)識(shí)M0，令M0(p)=1， 且p∈yi。 由邏輯Petri網(wǎng)的可達(dá)性動(dòng)態(tài)分析方法[12]，獲取LPNi在初始標(biāo)識(shí)M0下的所有可達(dá)標(biāo)識(shí)及其變遷觸發(fā)序列，假設(shè)可達(dá)標(biāo)識(shí)集合為Ms={M1,M2,…,Mk}。

(3)遍歷Ms，假設(shè)當(dāng)前元素為Mj，新建C_Relations的一個(gè)元素item，由系統(tǒng)生成唯一的檢索號(hào)并賦值給item.CID，令item的輸入?yún)?shù)集為M0中標(biāo)識(shí)為1的庫(kù)所集合，令item的輸出參數(shù)集為Mj中標(biāo)識(shí)為1的庫(kù)所集合，假設(shè)標(biāo)識(shí)M0到Mj觸發(fā)的變遷序列為tg,th,…,ti， 則由變遷標(biāo)記得到Web服務(wù)的調(diào)用序列及其ID號(hào)，假設(shè)tg,th,…,ti所標(biāo)記的Web服務(wù)的Qos值依次為Qosg,Qosh,…,Qosi, 則item.Qos的計(jì)算公式為

(1)

(4)輸出服務(wù)組合庫(kù)Scomlry。

算法3給出了服務(wù)組合庫(kù)的構(gòu)建方法，利用邏輯Petri網(wǎng)的可達(dá)性分析方法獲取了服務(wù)組合簇集LPN模型的全部服務(wù)組合情況，并根據(jù)服務(wù)組合庫(kù)的形式化結(jié)構(gòu)對(duì)相關(guān)屬性進(jìn)行賦值。

1.3 構(gòu)建Web服務(wù)組合簇集合

定義3 五維坐標(biāo)系：五元組Zb={inputs,outputs,Noi,Noo,Qos} 為一個(gè)五維坐標(biāo)系，其中inputs,outputs,Noi,Noo,Qos為5個(gè)坐標(biāo)軸，各坐標(biāo)軸的值均為實(shí)數(shù)。

算法4：服務(wù)組合在五維坐標(biāo)系的映射算法

輸入：服務(wù)組合庫(kù)中的服務(wù)組合item，基準(zhǔn)詞匯Word。

輸出：坐標(biāo)值Zbi。

(1)新建一個(gè)五維坐標(biāo)Zbi=， 假設(shè)item=。 若 (Inputa,Inputb,…,Inputc) 的元素個(gè)數(shù)為a，則令Zbi.Noi=a； 若 (Outputd,Outpute,…,Outputf) 的元素個(gè)數(shù)為b，則令Zbi.Noo=b； 令Zbi.Qos=Qosj。

(2)文獻(xiàn)[9]給出了基于語(yǔ)義的詞匯相似度計(jì)算公式

sim(a,b)=(dismax-dis(a-b))/(dismax-dismin)

(2)

其中，a，b為兩個(gè)語(yǔ)義詞匯，dis(a-b) 為兩個(gè)語(yǔ)義詞匯在本體詞匯樹中的語(yǔ)義距離，dismax為最大語(yǔ)義距離，dismin為最小語(yǔ)義距離?；谑?3)給出Zbi.inputs的計(jì)算公式

Zbi.inputs=dis(Inputa,Word)*wa+dis(Inputb,Word)*wb+…+dis(Inputc,Word)*wc

(3)

其中，Inputa,Inputb,…,Inputc為Web服務(wù)組合的輸入?yún)?shù)，wa,wb,…,wc為權(quán)值，且wa+wb+…+wc=1。 基于式(3)給出Zbi.outputs的計(jì)算公式

Zbi.outputs=dis(Outputd,Word)*wd+dis(Outpute,Word)*we+…+dis(Outputf,Word)*wf

(4)

其中，Outputd,Outpute,…,Outputf為Web服務(wù)組合的輸出參數(shù)，wd,we,…,wf為權(quán)值，且wd+we+…+wf=1。 由式(3)得到Zbi.inputs；由式(4)得到Zbi.outputs。

(3)將item.CID標(biāo)記到Zbi，并輸出五維坐標(biāo)Zbi=。

算法4給出了服務(wù)組合在五維坐標(biāo)系中的映射算法，基于文獻(xiàn)[9]定義的服務(wù)本體及其詞匯樹，將詞匯語(yǔ)義距離應(yīng)用到坐標(biāo)值的計(jì)算中；通過計(jì)算服務(wù)組合輸入?yún)?shù)、輸出參數(shù)、輸入?yún)?shù)個(gè)數(shù)、輸出參數(shù)個(gè)數(shù)、服務(wù)組合質(zhì)量的坐標(biāo)值，達(dá)到服務(wù)組合的坐標(biāo)映射效果。服務(wù)組合簇集的構(gòu)建方法如算法5所述。

定義4 服務(wù)組合簇：八元組Wcluster=(Id,inputs,outputs,Noi,Noo,R,Qos,Zbs) 為一個(gè)服務(wù)組合簇，其中：

(1)Id唯一標(biāo)識(shí)一個(gè)服務(wù)組合簇；

(2)inputs標(biāo)識(shí)了服務(wù)組合輸入?yún)?shù)的語(yǔ)義相對(duì)值；

(3)outputs標(biāo)識(shí)了服務(wù)組合輸出參數(shù)的語(yǔ)義相對(duì)值；

(4)Noi標(biāo)識(shí)了服務(wù)組合輸入?yún)?shù)個(gè)數(shù)；

(5)Noo標(biāo)識(shí)了服務(wù)組合輸出參數(shù)個(gè)數(shù)；

(6)R標(biāo)識(shí)了服務(wù)組合簇的聚類半徑；

(7)Qos標(biāo)識(shí)了服務(wù)組合簇中服務(wù)組合服務(wù)質(zhì)量的最小值；

(8)Zbs標(biāo)識(shí)了服務(wù)組合簇中的服務(wù)組合五維坐標(biāo)值集合。

算法5：服務(wù)組合簇集構(gòu)建算法

輸入：服務(wù)組合庫(kù)Scomlry，聚類半徑Rt，服務(wù)組合質(zhì)量閥值Qosmin。

輸出：服務(wù)組合簇集合Wclusters。

(1)新建一個(gè)服務(wù)組合簇集合Wclusters=?，新建一個(gè)坐標(biāo)集合Q=?，遍歷服務(wù)組合簇集合Wclusters中C_Relations的各個(gè)元素，假設(shè)當(dāng)前元素為item。由算法4將服務(wù)組合item映射在五維坐標(biāo)系中，得到坐標(biāo) ， 并放入集合Q中。

(2)遍歷集合Q中的坐標(biāo)元素，假設(shè)坐標(biāo)元素中Noi的最大值為Inmax，最小值為Inmin；Noo的最大值為Outmax，最小值為Outmin。inputs的最大值為Inputsmax，最小值為inputsmin；outputs的最大值為Ouputstmax，最小值為Outputsmin。Fori=InmintoInmax,j=OutmintoOutmax,k=inputsmintoInputsmax,h=OutputsmintoOuputstmaxdo，設(shè)定k、h的步長(zhǎng)均為Rt，新建服務(wù)組合簇Wcluster=(Id,inputs,outputs,Noi,Noo,R,Qos,Zbs)， 系統(tǒng)生成唯一的檢索號(hào)賦值給Wcluster.Id，令Wcluster.inputs=k，Wcluster.outputs=h，Wcluster.Noi=i，Wcluster.Noo=j，Wcluster.Qos=Qosmin，Wcluster.R=Rt。

(3)遍歷集合Q中的坐標(biāo)元素，假設(shè)當(dāng)前元素為Zbi=， 若Zbi.Noi==Wcluster.Noi， 且Zbi.Noo==Wcluster.Noo， 且Qosmin≤Zbi.Qos， 且Wcluster.R≤|Zbi.Inputs-Wcluster.inputs|， 且Wcluster.R≤|Zbi.outputs-Wcluster.outputs|， 則將Zbi放入Wcluster.Zbs中。

(4)將服務(wù)組合簇Wcluster放入服務(wù)組合簇集合Wclusters中。令Wcluster.Qos=0； 遍歷Wcluster，若當(dāng)前元素為Zbi，由Zbi標(biāo)記的服務(wù)組合ID獲取對(duì)應(yīng)的服務(wù)組合Qos值K，若K

(5)輸出服務(wù)組合簇集合Wclusters。

算法5給出了服務(wù)組合簇集的構(gòu)建方法，首先將服務(wù)組合庫(kù)中的所有元素映射到五維坐標(biāo)系中，然后根據(jù)服務(wù)組合坐標(biāo)的分布情況，將坐標(biāo)按照空間位置聚合成簇。由算法5可知，相同簇中的服務(wù)組合，其輸入?yún)?shù)個(gè)數(shù)相同、輸出參數(shù)個(gè)數(shù)相同、服務(wù)組合的Qos值均大于同一閥值，且輸入?yún)?shù)集合的語(yǔ)義距離在同一閥值范圍內(nèi)，輸出參數(shù)集合的語(yǔ)義距離也在同一閥值范圍內(nèi)。

2 多用戶Web服務(wù)組合發(fā)現(xiàn)

定義5 用戶需求：四元組Udemand=(Id,Uinputs,Uoutputs,Qos) 為一個(gè)用戶需求，其中：

(1)Id唯一標(biāo)識(shí)一個(gè)用戶需求；

(2)Uinputs={Input1,Input2,…,Inputj}標(biāo)識(shí)用戶需求輸入?yún)?shù)的一個(gè)有限集合；

(3)Uoutputs={Output1,Output2,…,Outputk} 標(biāo)識(shí)用戶需求輸出參數(shù)的一個(gè)有限集合；

(4)Qos標(biāo)識(shí)用戶對(duì)服務(wù)組合服務(wù)質(zhì)量的要求，且0≤QoS≤1。規(guī)定此值越大則代表服務(wù)質(zhì)量情況越優(yōu)；

(5)用戶需求的輸入、輸出參數(shù)概念范圍與Web服務(wù)的輸入、輸出參數(shù)概念范圍相一致。

定義5給出了用戶需求的形式化定義，由定義5可知，本文將Web服務(wù)形式化為輸入?yún)?shù)、輸出參數(shù)和服務(wù)組合質(zhì)量，下面對(duì)用戶需求的滿足規(guī)則進(jìn)行定義，并給出用戶需求的可滿足定理。

定義6 用戶需求的滿足規(guī)則：給定Web服務(wù)集合Q及用戶需求Udemand=(Id,Uinputs,Uoutputs,Qos)。 如果用戶需求Udemand的輸出參數(shù)Uoutputs，能夠根據(jù)用戶需求的Uinputs，通過調(diào)用Web服務(wù)集合Q中的Web服務(wù)得到，且調(diào)用的Web服務(wù)Qos的平均值大于等于Udemand.Qos。則用戶需求Udemand對(duì)于Web服務(wù)集合Q是可滿足的。

定義7 運(yùn)算符“?”：令LPNm為一個(gè)Web服務(wù)集的邏輯Petri網(wǎng)模型，假設(shè)P={p1,p2,…,pm} 為其庫(kù)所集，且M∈R(M0)。Q為L(zhǎng)PNm.P的一個(gè)庫(kù)所集合。運(yùn)算符“?”的規(guī)則為：M?Q=M，其中，對(duì)于j∈{1,2,…,m}

(5)

定理1 用戶需求的可滿足定理：Udemandi=(Id,Uinputs,Uoutputs,Qos) 為一個(gè)用戶需求。LPNj為給定Web服務(wù)集合Q的邏輯Petri網(wǎng)模型，且Ma∈R(M0)， 其中M0為L(zhǎng)PNj的初始標(biāo)識(shí)。用戶需求Udemandi在Web服務(wù)集合Q下是可滿足的，當(dāng)且僅當(dāng)：

(1) (M0?Uinputs)[t1t2…ti>(Ma?Uoutputs)；

(2)變遷t1t2…ti標(biāo)記的Web服務(wù)Qos值和的平均值大于等于Udemand.Qos；

(3)變遷t1t2…ti標(biāo)記的Web服務(wù)在用戶調(diào)用時(shí)其并發(fā)數(shù)小于最大并發(fā)數(shù)。

證明：[必要性]由定義5可知，Udemandi.Uinputs、Udemandi.Uoutputs屬于LPNj的庫(kù)所集中的元素。由定義7可知，Ma?Uinputs得到一個(gè)LPNj的標(biāo)識(shí)，此標(biāo)識(shí)蘊(yùn)含了用戶需求Udemandi的輸入?yún)?shù)信息。M0?Uoutputs得到一個(gè)LPNj的標(biāo)識(shí)，此標(biāo)識(shí)蘊(yùn)含了用戶需求Udemandi的輸出參數(shù)信息。因?yàn)橛脩粜枨骍demandi在Web服務(wù)集合Q下是可滿足的。由定義6可知，用戶需求Udemand的輸出參數(shù)Uoutputs，能夠由用戶需求的輸入?yún)?shù)，并通過調(diào)用Web服務(wù)集合Q中的Web服務(wù)得到。則對(duì)于邏輯Petri網(wǎng)LPNj，標(biāo)識(shí)M0?Uoutputs能夠從標(biāo)識(shí)Ma?Uinputs到達(dá)，即 (M0?Uinputs)[t1t2…ti>(Ma?Uoutputs)。 因Web服務(wù)能夠被調(diào)用，所以Web服務(wù)在用戶調(diào)用時(shí)其并發(fā)數(shù)小于最大并發(fā)數(shù)。因滿足用戶需求，故由定義2可知，所調(diào)用的Web服務(wù)Qos值和的平均值大于等于Udemand.Qos。

[充分性]因?yàn)?(M0?Uinputs)[t1t2…ti>(Ma?Uoutputs)， 即 (Ma?Uoutputs)∈R(M0?Uinputs)， 則對(duì)于邏輯Petri網(wǎng)LPNj，標(biāo)識(shí)M0?Uoutputs能夠從標(biāo)識(shí)Ma?Uinputs到達(dá)。因變遷t1t2…ti標(biāo)記的Web服務(wù)在用戶調(diào)用時(shí)其并發(fā)數(shù)小于最大并發(fā)數(shù)，故服務(wù)均可被調(diào)用。因變遷t1t2…ti標(biāo)記的Web服務(wù)Qos值和的平均值大于等于Udemand.Qos，故滿足用戶對(duì)于服務(wù)質(zhì)量的要求。由定義7可知，Ma?Uinputs得到一個(gè)LPNj的標(biāo)識(shí)，此標(biāo)識(shí)蘊(yùn)含了用戶需求Udemandi的輸入?yún)?shù)信息。M0?Uoutputs得到一個(gè)LPNj的標(biāo)識(shí)，此標(biāo)識(shí)蘊(yùn)含了用戶需求Udemandi的輸出參數(shù)信息。則用戶需求Udemand的輸出參數(shù)Uoutputs，能夠由用戶需求的輸入?yún)?shù)Uinputs，并通過調(diào)用Web服務(wù)集合Q中的Web服務(wù)得到。由定義6，用戶需求Udemandi在Web服務(wù)集合Q下是可滿足的。[證畢]

定義8 用戶滿意度：百分?jǐn)?shù)變量Percent為用戶滿意度。其賦值規(guī)則為：給定一個(gè)用戶需求Udemandi=(Id,Uinputs,Uoutputs,Qos)， 假設(shè)其在五維坐標(biāo)系中的坐標(biāo)值為Zbi=； 通過服務(wù)組合發(fā)現(xiàn)得到的服務(wù)組合item的五維坐標(biāo)值為Zbj=， 且調(diào)用的Web服務(wù)所構(gòu)成的集合為Q，則Percent的計(jì)算公式為

(6)

定理1給出了用戶需求的可滿足定理，明確了滿足用戶需求的相關(guān)條件，定義8給出了用戶滿意度的計(jì)算方法，為面向多用戶的服務(wù)組合發(fā)現(xiàn)尋優(yōu)提供了評(píng)價(jià)參考。

算法6：用戶需求在五維坐標(biāo)系的映射算法

輸入：用戶需求Udemand，基準(zhǔn)詞匯Word。

輸出：坐標(biāo)值Zbi。

(1)新建一個(gè)五維坐標(biāo)Zbi=， 假設(shè)Udemand=(Id,Uinputs,Uoutputs,Qos)=(UID，(Inputa,Inputb,…,Inputc)， (Outputd,Outpute,…,Outputf)，Qosj)。 若 (Inputa,Inputb,…,Inputc) 的元素個(gè)數(shù)為a，則令Zbi.Noi=a； 若 (Outputd,Outpute,…,Outputf) 的元素個(gè)數(shù)為b，則令Zbi.Noo=b； 令Zbi.Qos=Qosj。

(2)由式(3)得到Zbi.inputs；由式(4)得到Zbi.outputs。

(3)將UID標(biāo)記到Zbi，并輸出五維坐標(biāo)Zbi=。

定義9 坐標(biāo)點(diǎn)的簇內(nèi)相似度：在服務(wù)組合簇中存在兩個(gè)坐標(biāo)點(diǎn)Zbj,Zbi， 假設(shè)由Zbi標(biāo)記的服務(wù)組合ID對(duì)應(yīng)的服務(wù)組合為 ， 由Zbj標(biāo)記的服務(wù)組合ID對(duì)應(yīng)的服務(wù)組合為 兩個(gè)坐標(biāo)點(diǎn)的簇內(nèi)相似度計(jì)算公式為

(7)

由定義1可知，本文將Web服務(wù)調(diào)用最大并發(fā)數(shù)引入系統(tǒng)中，則在進(jìn)行面向多用戶的Web服務(wù)組合綁定時(shí)在同一時(shí)刻，系統(tǒng)中可能會(huì)出現(xiàn)一個(gè)具有相同優(yōu)先級(jí)的用戶需求集合，同一個(gè)Web服務(wù)可能會(huì)同時(shí)被不同的用戶所調(diào)用，且一個(gè)Web服務(wù)的調(diào)用并發(fā)數(shù)可能會(huì)達(dá)到上線。

算法7：多用戶服務(wù)組合綁定算法

輸入：用戶需求集合Udemands，Web服務(wù)集合Q，并發(fā)數(shù)閥值S。

輸出：服務(wù)組合綁定集合。

(1)Web服務(wù)集合Q的動(dòng)態(tài)調(diào)整。若?Ws∈Q， 且S≤(Ws.Com-Value)， 則在Q中刪除Ws，Value為Ws當(dāng)前服務(wù)并發(fā)數(shù)。由算法5構(gòu)建服務(wù)組合簇集合Wclusters。

(2)新建服務(wù)組合綁定集合Binds=?，遍歷用戶需求集合Udemands，假設(shè)當(dāng)前元素為Udemand，由算法6將用戶需求Udemand映射到五維坐標(biāo)系中，并獲取坐標(biāo)Zbi=。

(3)遍歷服務(wù)組合簇集合Wclusters，假設(shè)當(dāng)前元素為服務(wù)組合簇Wcluster=(Id,inputs,outputs,Noi,Noo,R,Qos,Zbs)， 若Zbi.Noi==Wcluster.Noi， 且Zbi.Noo==Wcluster.Noo， 且Wcluster.R≤|Zbi.Inputs-Wcluster.inputs|， 且Wcluster.R≤|Zbi.outputs-Wcluster.outputs|， 則鎖定服務(wù)組合簇Wcluster。

(4)新建一個(gè)變量flag=0；遍歷Wcluster.Zbs，假設(shè)當(dāng)前元素為Zbj=， 若Zbi.Qos≤Zbj.Qos， 則由定義9計(jì)算坐標(biāo)Zbi與坐標(biāo)Zbj的簇內(nèi)相似度H(Zbj,Zbi)， 若flag

(5)假設(shè)flag標(biāo)記的坐標(biāo)為Zbi，將Zbi標(biāo)記的服務(wù)組合放入集合Binds中，并由系統(tǒng)向用戶反饋服務(wù)組合信息。

(6)輸出Binds。

3 仿真實(shí)驗(yàn)

3.1 搭建實(shí)驗(yàn)仿真平臺(tái)

實(shí)驗(yàn)硬件環(huán)境為i7-6500U CPU @ 2.50 GHZ 2.50 GHZ，8.0 GB內(nèi)存。仿真平臺(tái)運(yùn)行頁(yè)面的設(shè)計(jì)如下所述。在VS 2010中建立C#的項(xiàng)目，進(jìn)行Winform桌面控件的選擇及布局。仿真平臺(tái)頁(yè)面如圖1所示。

圖1 實(shí)驗(yàn)平臺(tái)頁(yè)面

軟件代碼的編寫與按鈕功能實(shí)現(xiàn)如下所述。

(1)生成Web服務(wù)功能。首先在Web服務(wù)個(gè)數(shù)輸入框內(nèi)輸入需生成的Web服務(wù)個(gè)數(shù)，當(dāng)點(diǎn)擊生成Web服務(wù)按鈕時(shí)觸發(fā)生成Web服務(wù)程序。生成Web服務(wù)編程的基本思想是：首先按照本文定義1的結(jié)構(gòu)定義Web服務(wù)類，輸入、輸出集定義為鏈表類型，同步在SQL數(shù)據(jù)庫(kù)中構(gòu)建Web服務(wù)數(shù)據(jù)表，表的屬性結(jié)構(gòu)與Web服務(wù)類中的參數(shù)一致。程序循環(huán)次數(shù)是需生成的Web服務(wù)個(gè)數(shù)，對(duì)于程序的每一次循環(huán)都要生成一個(gè)Web服務(wù)。ID號(hào)、Qos、Com隨機(jī)生成，Web服務(wù)的輸入、輸出參數(shù)集的生成思想是：字母“a”到字母“z”的ASSIC碼區(qū)間為97至122。程序中利用Random.Next(1,100)函數(shù)隨機(jī)確定將要構(gòu)建的參數(shù)集中的參數(shù)個(gè)數(shù)；利用Random.Next(1,50)函數(shù)隨機(jī)確定某個(gè)參數(shù)的長(zhǎng)度；利用Random.Next(97,123)函數(shù)隨機(jī)確定某個(gè)參數(shù)的組成元素，將組成元素的ASSIC碼值的和定為詞匯語(yǔ)義值；生成Web服務(wù)結(jié)束后利用MessageBox.Show()函數(shù)彈出提示框。

(2)生成用戶需求功能。首先在用戶需求個(gè)數(shù)文本框內(nèi)輸入需生成的用戶需求個(gè)數(shù)。當(dāng)點(diǎn)擊生成用戶需求按鈕時(shí)觸發(fā)生成用戶需求程序。用戶需求的生成思想與Web服務(wù)的生成思想相似。

(3)按照本文技術(shù)路線實(shí)現(xiàn)多用戶服務(wù)組合發(fā)現(xiàn)按鈕功能，按照算法2、算法3和算法5構(gòu)建服務(wù)集合的LNP模型、服務(wù)組合庫(kù)及服務(wù)組合簇集，按照算法7進(jìn)行服務(wù)組合發(fā)現(xiàn)。按照文獻(xiàn)[13-15]的技術(shù)路線分別實(shí)現(xiàn)基于服務(wù)簇、服務(wù)組合簇頭、相似度的服務(wù)發(fā)現(xiàn)按鈕功能。

服務(wù)發(fā)現(xiàn)效率計(jì)算的思想是：在點(diǎn)擊相應(yīng)的服務(wù)查找按鈕后，利用System.Diagnostics.Stopwatch類中的start方法開始計(jì)時(shí)；當(dāng)服務(wù)發(fā)現(xiàn)結(jié)束后，利用Stopwatch類中的stop方法結(jié)束計(jì)時(shí)；然后，讀取Stopwatch類中的ElapsedMilliseconds屬性值獲取服務(wù)查找運(yùn)行的總時(shí)間。服務(wù)發(fā)現(xiàn)精確度按照本文定義8給出的用戶滿意度進(jìn)行計(jì)算，并通過在程序中設(shè)置斷點(diǎn)、提示框輸出等方式對(duì)生成的Web服務(wù)、用戶需求、服務(wù)組合庫(kù)、服務(wù)組合簇集、服務(wù)組合發(fā)現(xiàn)效果等進(jìn)行復(fù)核。

3.2 實(shí)驗(yàn)比較及分析

實(shí)驗(yàn)1：在Web服務(wù)總數(shù)不變，用戶需求個(gè)數(shù)變化的情況下進(jìn)行Web服務(wù)組合查找實(shí)驗(yàn)及比較。首先生成兩萬(wàn)個(gè)Web服務(wù)，用戶需求個(gè)數(shù)依次為一至八百個(gè)。每次輸入用戶需求個(gè)數(shù)后，點(diǎn)擊生成用戶需求按鈕生成用戶需求，再點(diǎn)擊4個(gè)服務(wù)發(fā)現(xiàn)按鈕對(duì)方法性能進(jìn)行獲取。實(shí)驗(yàn)一的效率統(tǒng)計(jì)結(jié)果如圖2所示，精度統(tǒng)計(jì)結(jié)果如圖3所示。

圖2 實(shí)驗(yàn)一效率結(jié)果

圖3 實(shí)驗(yàn)一精度結(jié)果

從圖2可知，在服務(wù)總數(shù)不變時(shí)，隨著用戶需求個(gè)數(shù)的增多，基于4種方法的服務(wù)查找時(shí)間都增多。對(duì)4種方法實(shí)驗(yàn)結(jié)果進(jìn)行比較可知，本文所述方法的效率較優(yōu)，并且隨著用戶需求個(gè)數(shù)的增多，本文所述方法的優(yōu)越性越明顯。

從圖3可知，在服務(wù)總數(shù)不變時(shí)，隨著用戶需求個(gè)數(shù)的增多，基于4種方法的服務(wù)查找精確度變化幅度較小。對(duì)4種方法實(shí)驗(yàn)結(jié)果進(jìn)行比較可知，本文所述方法的精度較優(yōu)。

實(shí)驗(yàn)2：在用戶需求個(gè)數(shù)不變，Web服務(wù)總數(shù)變化的情況下進(jìn)行Web服務(wù)查找實(shí)驗(yàn)及比較。固定生成用戶需求為300個(gè)，生成Web服務(wù)個(gè)數(shù)依次為1～8萬(wàn)個(gè)。實(shí)驗(yàn)二效率結(jié)果如圖4所示，精度結(jié)果如圖5所示。

圖4 實(shí)驗(yàn)二效率結(jié)果

圖5 實(shí)驗(yàn)二精度結(jié)果

從圖4可知，在用戶需求個(gè)數(shù)不變，Web服務(wù)總數(shù)變化的情況下，隨著服務(wù)個(gè)數(shù)的增多，基于4種方法的服務(wù)查找時(shí)間不斷變大，服務(wù)查找效率不斷降低。對(duì)4種方法實(shí)驗(yàn)結(jié)果進(jìn)行比較可知，本文所述方法的服務(wù)組合發(fā)現(xiàn)效率較優(yōu)。

從圖5可知，在用戶需求個(gè)數(shù)不變，Web服務(wù)總數(shù)變化的情況下，隨著服務(wù)個(gè)數(shù)的增多，基于4種方法的服務(wù)查找精確度有增大趨勢(shì)。對(duì)4種方法實(shí)驗(yàn)結(jié)果進(jìn)行比較可知，本文所述方法的精度較優(yōu)。

理論分析：本文所述方法在效率上的理論優(yōu)越性體現(xiàn)在：①本文利用邏輯Petri網(wǎng)的可達(dá)性分析方法獲取了面向服務(wù)集合的全部服務(wù)組合，依據(jù)聚類半徑構(gòu)建了結(jié)構(gòu)化的服務(wù)組合簇集合，從服務(wù)集合整體角度優(yōu)化了服務(wù)發(fā)現(xiàn)的基數(shù)。②本文構(gòu)建了五維坐標(biāo)系，將服務(wù)組合及用戶需求映射為坐標(biāo)數(shù)據(jù)，為服務(wù)發(fā)現(xiàn)進(jìn)行充分的數(shù)據(jù)預(yù)處理。并利用計(jì)算坐標(biāo)距離的方法實(shí)現(xiàn)服務(wù)組合發(fā)現(xiàn)，簡(jiǎn)化了服務(wù)組合發(fā)現(xiàn)環(huán)節(jié)。

本文所述方法在精度上的理論優(yōu)越性體現(xiàn)在：①本文對(duì)服務(wù)組合的服務(wù)質(zhì)量計(jì)算方法進(jìn)行了形式化定義，服務(wù)組合綁定中，對(duì)服務(wù)組合的輸入、輸出參數(shù)進(jìn)行了基于語(yǔ)義的全匹配，并考慮了服務(wù)質(zhì)量，優(yōu)化了服務(wù)查準(zhǔn)率。②本文從多用戶需求角度出發(fā)，在進(jìn)行服務(wù)組合發(fā)現(xiàn)時(shí)考慮了服務(wù)最大并發(fā)數(shù)，并動(dòng)態(tài)更新了Web服務(wù)集合，降低了用戶服務(wù)組合調(diào)用失敗的幾率，增大了用戶滿意度。③本文所述方法是基于服務(wù)組合簇集的。服務(wù)組合簇集覆蓋了服務(wù)集合內(nèi)輸入、輸出組合關(guān)系，羅列了所有輸入、輸出可能的對(duì)應(yīng)情況，并且明確了從某一輸入到某一輸出的服務(wù)調(diào)用序列。用戶需求在服務(wù)組合簇集中進(jìn)行服務(wù)查找，可最大程度找到滿足用戶需求的服務(wù)組合。

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

為優(yōu)化服務(wù)發(fā)現(xiàn)效率及精度，本文提出了一種基于服務(wù)組合簇集的多用戶Web服務(wù)組合綁定方法。構(gòu)建了服務(wù)集合的LPN模型及服務(wù)組合庫(kù)，并將服務(wù)組合映射到五維坐標(biāo)系中；利用基于語(yǔ)義的詞匯距離計(jì)算方法構(gòu)建服務(wù)組合簇集合。最后，考慮Web服務(wù)的最大并發(fā)數(shù)，并利用語(yǔ)義相似度計(jì)算方法，在Web服務(wù)組合簇集合中動(dòng)態(tài)發(fā)現(xiàn)了滿足用戶需求的服務(wù)組合。實(shí)驗(yàn)驗(yàn)證了本文方法在優(yōu)化服務(wù)組合發(fā)現(xiàn)性能上具有優(yōu)越性。下一步將對(duì)基于WSDL的Web服務(wù)描述特征提取進(jìn)行研究。