馮秀珍，武高峰

(北京工業(yè)大學(xué)經(jīng)濟(jì)與管理學(xué)院，北京100124)

Web Service是一種新興的分布式計(jì)算模式，它可以在網(wǎng)絡(luò)上被描述、發(fā)布、查找和調(diào)用，由此而形成了一套應(yīng)用程序在Web上實(shí)現(xiàn)互操作的標(biāo)準(zhǔn)。伴隨著Web Service應(yīng)用的拓展，Internet上的Web Service資源不斷豐富，而具有相似功能的Web Service充斥其中，這些嚴(yán)重困擾了服務(wù)請(qǐng)求者對(duì)于服務(wù)的選擇。因此，如何從眾多相似Web Service中按需發(fā)現(xiàn)符合用戶(hù)需求的服務(wù)成為研究者面臨的重要問(wèn)題。

Web Service的屬性可以分為功能屬性和非功能屬性。功能屬性描述Web Service提供的操作，非功能屬性描述Web Service的QoS(quality of service)特性。與現(xiàn)有的基于語(yǔ)法級(jí)的關(guān)鍵字查詢(xún)［1］功能相似的Web Service在 UDDI注冊(cè)中心可以查找到，而用戶(hù)要發(fā)現(xiàn)合乎需求的服務(wù)還必須在多個(gè)功能相似服務(wù)中以靜態(tài)或動(dòng)態(tài)的方式［2－3］進(jìn)行選擇。但是，用戶(hù)對(duì)服務(wù)需求存在認(rèn)識(shí)上的模糊性，其選擇過(guò)程較為盲目。Web Service的QoS屬性能夠描述滿足用戶(hù)需求的服務(wù)，因此，它已經(jīng)成為用戶(hù)按需選擇服務(wù)的重要依據(jù)［4］。筆者以功能屬性匹配研究為基礎(chǔ)，采用區(qū)間表示方式描述QoS的屬性信息，提出了一種基于QoS的按需服務(wù)發(fā)現(xiàn)過(guò)程，即以先聚類(lèi)后排序的方式在一類(lèi)功能屬性相似的服務(wù)集中將Web Service資源的QoS信息和用戶(hù)的QoS需求信息進(jìn)行合并聚類(lèi)，經(jīng)過(guò)相似度計(jì)算，對(duì)同一類(lèi)中Web Service進(jìn)行排序處理，通過(guò)分析對(duì)比剔除不滿足用戶(hù)需求的Web Service，以此實(shí)現(xiàn)“按需定制，量身定做”的服務(wù)發(fā)現(xiàn)。

1 按需服務(wù)發(fā)現(xiàn)過(guò)程分析

1.1 按需服務(wù)發(fā)現(xiàn)過(guò)程

Web Service資源的QoS信息和用戶(hù)的QoS需求信息是實(shí)現(xiàn)Web Service聚類(lèi)的兩類(lèi)重要信息源。前者主要通過(guò)從給定的Web Service信息中抽取WSDL(Web services description language)信息，再經(jīng)過(guò)一系列的提取、篩選和裝載過(guò)程［5］形成Web Service資源庫(kù)，最后通過(guò)語(yǔ)義本體的匹配［6］，將功能相似的一類(lèi)Web Service聚類(lèi)成服務(wù)池而獲得;后者通過(guò)將用戶(hù)需求數(shù)字化而獲得。圖1為按需服務(wù)發(fā)現(xiàn)過(guò)程。

圖1 按需服務(wù)發(fā)現(xiàn)過(guò)程圖

1.2 基于FCM的區(qū)間數(shù)聚類(lèi)算法

網(wǎng)絡(luò)環(huán)境的動(dòng)態(tài)性和不確定性，為基于QoS的服務(wù)發(fā)現(xiàn)帶來(lái)了困難，加之用戶(hù)服務(wù)需求的模糊性和多樣性，使服務(wù)供需雙方都難以用確切的數(shù)值描述QoS信息，因此采用區(qū)間值的表述方式更具可操作性。模糊C均值聚類(lèi)(FCM)算法是一種專(zhuān)門(mén)處理模糊數(shù)據(jù)，根據(jù)一定的隸屬度確定每個(gè)樣本點(diǎn)屬于某個(gè)聚類(lèi)的聚類(lèi)算法。FCM的目標(biāo)是使被劃分在同一類(lèi)中的對(duì)象之間的相似度最大，而不同類(lèi)的對(duì)象之間的相似度最?。?］。FCM算法由DUNN提出［8］，用以解決精確數(shù)值信息模式識(shí)別問(wèn)題和模糊分類(lèi)問(wèn)題。基于區(qū)間數(shù)的聚類(lèi)分析研究［9－10］擴(kuò)展了該方法的應(yīng)用范疇。它可以把n個(gè)樣本向量分為m個(gè)模糊組，通過(guò)反復(fù)修改分類(lèi)矩陣和聚類(lèi)中心，得到各個(gè)樣本對(duì)于各類(lèi)的隸屬度值和各類(lèi)的聚類(lèi)中心，從而實(shí)現(xiàn)模糊聚類(lèi)的劃分。

筆者在服務(wù)池構(gòu)建的基礎(chǔ)上，采用FCM聚類(lèi)算法研究面向服務(wù)的按需服務(wù)發(fā)現(xiàn)過(guò)程。該過(guò)程通過(guò)對(duì)給定服務(wù)的Web Service資源信息和用戶(hù)的服務(wù)需求信息進(jìn)行基于QoS的FCM聚類(lèi)，把具有相似QoS信息的Web服務(wù)聚合為一類(lèi)，把其他聚合為另一類(lèi)，并根據(jù)先聚類(lèi)后排序的方式確定同一類(lèi)服務(wù)中最優(yōu)的Web Service。若同類(lèi)服務(wù)中的對(duì)象至少一個(gè)優(yōu)于需求，則認(rèn)為該對(duì)象是最適合的。反之，無(wú)法找到適合的服務(wù)，則需要調(diào)用協(xié)商算法［11］優(yōu)化聚類(lèi)目標(biāo)，以期按需發(fā)現(xiàn)最適服務(wù)?；贔CM的聚類(lèi)過(guò)程如圖2所示。

圖2 基于FCM的聚類(lèi)過(guò)程圖

基于FCM區(qū)間數(shù)多屬性聚類(lèi)算法可描述為:

已知指標(biāo)集 Q={Q1，Q2，…，Qp}，即 QoS 數(shù)據(jù)信息。樣本集 X={X1，X2，…，Xn/2，…，Xn}，即Web 服務(wù)，其中{X1，X2，…，Xn/2}為服務(wù)信息資源的樣本集，{Xn/2，…，Xn}為用戶(hù)的需求樣本集。樣本Xi針對(duì)Qj的區(qū)間信息可表示為

步驟1 量化和標(biāo)準(zhǔn)化。QoS屬性有定量和定性之分。采用統(tǒng)計(jì)方法［12］對(duì)服務(wù)提供者發(fā)布的內(nèi)容進(jìn)行標(biāo)準(zhǔn)化處理是定量屬性量化的主要方式;定性屬性的量化多采用模糊約束理論，利用專(zhuān)家調(diào)查法或主觀經(jīng)驗(yàn)法在一定的值域內(nèi)將其數(shù)值化。同時(shí)，QoS又有效益和成本之分，前者值愈大，或者后者屬性值愈小，QoS綜合性能愈好。

當(dāng)Qi為效益型指標(biāo)時(shí):

當(dāng)Qi為成本型指標(biāo)時(shí):

步驟2 聚類(lèi)標(biāo)準(zhǔn)集初始化。假定X={X1，X2，…，Xn}為待聚類(lèi)對(duì)象集，對(duì)象集X的類(lèi)別為c，模糊加權(quán)指數(shù)為m(m＞0)，計(jì)算迭代精度為ε(ε＞0)。取初始化聚類(lèi)標(biāo)準(zhǔn)原型，其中，設(shè)初始迭代次數(shù)b為0。

1.3 排序

相離、包含和相交是區(qū)間關(guān)系的3種形式，筆者以區(qū)間吻合程度來(lái)描述區(qū)間關(guān)系的相似度。這里假定用戶(hù)的QoS需求信息為，Web Service資源的QoS信息為相對(duì)長(zhǎng)度法計(jì)算的兩個(gè)區(qū)間屬性值的相似度為:

式中:L為相應(yīng)區(qū)間的長(zhǎng)度;a∩b為a和b的重疊區(qū)間。

同理，可定義如表1所示的相似度度量值。

表1 區(qū)間關(guān)系相似度度量值

在多屬性綜合評(píng)價(jià)中，需要先計(jì)算服務(wù)池中各屬性之和，再進(jìn)行排序。

若sum=p，則表示服務(wù)請(qǐng)求者的需求能夠完全被滿足，此時(shí)存在最優(yōu)服務(wù);若0＜sum＜p，則表示服務(wù)請(qǐng)求者的需求被部分滿足，需要調(diào)用協(xié)商程序?qū)ξ礉M足條件的屬性進(jìn)行協(xié)商;若sum=0，則表示服務(wù)請(qǐng)求者的需求無(wú)法被滿足，進(jìn)一步協(xié)商需要花費(fèi)較大代價(jià)。

2 算例

該算例的目的是通過(guò)先聚類(lèi)后排序的方式驗(yàn)證所提出的按需服務(wù)發(fā)現(xiàn)過(guò)程的可行性。算例采用演繹推理法確定某Web服務(wù)的QoS屬性。所選用的指標(biāo)包括QoS屬性的定性、定量、成本型和效益型指標(biāo)，數(shù)據(jù)描述以區(qū)間形式為主。聚類(lèi)樣本有15個(gè)Web服務(wù)資源和1個(gè)Web服務(wù)需求(即 S01，S02，…，S15，R00)，如表2 所示。聚類(lèi)樣本指標(biāo)有3個(gè)，其中成本(調(diào)用Web服務(wù)資源必須支付的費(fèi)用)為成本型區(qū)間數(shù)指標(biāo)，可用性(Web服務(wù)資源執(zhí)行的正確程度)和易用性(Web服務(wù)資源能夠被用戶(hù)理解和使用的容易程度)為效益型指標(biāo)。易用性指標(biāo)為定性指標(biāo)，打分范圍為0.1(最差)到1.0(最好)之間。因篇幅所限，規(guī)范化后的聚類(lèi)指標(biāo)數(shù)據(jù)不再列出。假設(shè)c=3，m=2，ε=0.000 5，初始聚類(lèi)標(biāo)準(zhǔn)如表3所示。

表2 聚類(lèi)對(duì)象相關(guān)指標(biāo)

表3 初始聚類(lèi)標(biāo)準(zhǔn)V(0)

根據(jù)上述聚類(lèi)步驟，經(jīng)3次迭代，由收斂精度ε3=J［U(2)，V(2)］－ J［U(3)，V(3)］=0.000 231 ＜ε可知，最優(yōu)聚類(lèi)標(biāo)準(zhǔn)V(3)如表4所示和最優(yōu)聚類(lèi)的隸屬度值U(3)如表5所示。根據(jù)最大隸屬度原則，將服務(wù)分為好、中、差3類(lèi)，分別為{S01，S05，S07，S08，S14}、{S06，S09，S11，S13，R00}和{S02，S03，S04，S10，S12，S15}。

表4 最優(yōu)聚類(lèi)標(biāo)準(zhǔn)V(3)

R00在分類(lèi)二中，對(duì)該類(lèi)進(jìn)行排序。根據(jù)式(9)和表1，有4 個(gè) Web 服務(wù)資源(S06，S09，S11，S13)與Web服務(wù)需求R00的相似度分別為3.0、1.5、2.0 和 1.0。排序?yàn)?S06 ＞S11 ＞S09 ＞S13。S06與R00的相似度值等于指標(biāo)個(gè)數(shù)p。因此，不需要進(jìn)行進(jìn)一步協(xié)商，即S06是最符合用戶(hù)需求的Web服務(wù)。

3 結(jié)論

大量涌現(xiàn)的相似的Web服務(wù)對(duì)滿足用戶(hù)的按需服務(wù)發(fā)現(xiàn)提出了嚴(yán)峻的挑戰(zhàn)。傳統(tǒng)的Web服務(wù)發(fā)現(xiàn)是根據(jù)用戶(hù)的需求信息在UDDI中進(jìn)行檢索，但是這種方式效率低下。筆者提出了一種基于QoS的按需服務(wù)發(fā)現(xiàn)過(guò)程，可以通過(guò)FCM聚類(lèi)將用戶(hù)的QoS需求和Web服務(wù)資源的QoS信息進(jìn)行聚合，在已有分類(lèi)的基礎(chǔ)上，對(duì)同類(lèi)中的聚類(lèi)對(duì)象進(jìn)行排序，利用排序結(jié)果做出是否協(xié)商的決定，以滿足用戶(hù)的按需服務(wù)。算例結(jié)果表明，該服務(wù)發(fā)現(xiàn)過(guò)程可行，且能夠快速有效地根據(jù)用戶(hù)QoS需求發(fā)現(xiàn)適合的服務(wù)。

［1］何玲娟，劉連臣，吳澄.一種改進(jìn)的基于WSDL描述的操作相似性度量方法研究［J］.計(jì)算機(jī)學(xué)報(bào)，2008，31(8):1331 －1339.

［2］PATHAK J，KOIL N，CARAGEA D，et al.A framework for semantic Web services discovery［C］//Proceedings of the7thACM InternationalWorkshop on Web Information and Data Management.［S.l.］:ACM Press，2005:45－50.

［3］BIANCHINIA D，ANTONELLISV D.Ontology based methodology for e － service discovery［J］.Information System，2006(31):361 －380.

［4］戴常英，戴明坤，張會(huì)娟.擴(kuò)展Augment UDDI系統(tǒng)以支持QoS的Web服務(wù)發(fā)現(xiàn)模型［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30(2):358 －361.

［5］徐德智，鄭春卉，PASSIK.基于SUMO的概念相似度研究［J］.計(jì)算機(jī)應(yīng)用，2006，26(1):180 －183.

［6］劉譞哲，黃罡，梅宏.用戶(hù)驅(qū)動(dòng)的服務(wù)聚合方法及其支撐框架［J］.軟件學(xué)報(bào)，2007，18(8):1883 －1895.

［7］黃良輝，陳常青，趙婷.一種基于模糊聚類(lèi)思想的評(píng)價(jià)結(jié)果組合模型［C］//2006年中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集.［S.l.］:［s.n.］，2006:1251 －1255.

［8］DUNN JC.A fuzzy relative of the ISODATA process and its use in detecting compactwell－separated clusters［J］.JCybernet，1974(3):32 －57.

［9］孟廣武，張興芳，鄭亞林.基于區(qū)間值模糊集的聚類(lèi)方法［J］.工程數(shù)學(xué)學(xué)報(bào)，2001，18(2):69 －73.

［10］于春海，樊治平.一種基于區(qū)間數(shù)多指標(biāo)信息的FCM聚類(lèi)算法［J］.系統(tǒng)工程學(xué)報(bào)，2004，19(4):387－393.

［11］FENG X，WU G.A study on interval negotiation algorithm for service－oriented QoS［C］//International Conference on Computational Intelligence and Software Engineering.［S.l.］:［s.n.］，2010:1 －4.

［12］李江華，陳淑婷.Web服務(wù)QoS信息獲取與處理方法研究［J］.江西理工大學(xué)學(xué)報(bào)，2008，29(6):24 －28.