QoS約束的代表性Skyline Web服務(wù)選擇*

黃迎春 ，左甜甜

（1.沈陽(yáng)理工大學(xué)信息科學(xué)與工程學(xué)院，沈陽(yáng) 110159；2.東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 110169）

0 引言

在新一代軍事指揮控制系統(tǒng)中，面向服務(wù)的體系結(jié)構(gòu)（SOA，service-Oriented Architecture）應(yīng)用趨勢(shì)明顯增長(zhǎng)，Web service已經(jīng)成為構(gòu)建的SOA指控系統(tǒng)的重要技術(shù)。Web服務(wù)搜索引擎Seekda［1］公開(kāi)發(fā)表的統(tǒng)計(jì)信息表明，近年來(lái)，Web service在數(shù)量上以指數(shù)性指標(biāo)增長(zhǎng)。指控用戶(hù)面對(duì)大量功能相似但QoS不同的服務(wù)信息，如何按需選擇匹配服務(wù)成為亟待解決的問(wèn)題。特別地，當(dāng)前許多服務(wù)匹配、選擇算法在按照QoS指標(biāo)選取服務(wù)時(shí)，將顯著增加服務(wù)選擇的計(jì)算復(fù)雜度，所以實(shí)現(xiàn)快速的服務(wù)選擇就變得非常緊迫。

QoS約束的Web服務(wù)選擇包括兩種策略：局部選擇策略和全局選擇策略，常用的Web服務(wù)局部選擇方法，主要基于多屬性決策理論［2］，包含服務(wù)需求定義、服務(wù)QoS參數(shù)預(yù)處理、服務(wù)QoS指標(biāo)賦權(quán)以及候選服務(wù)排序等服務(wù)選擇過(guò)程。全局選擇策略即組合服務(wù)選擇策略，常用的方法是0-1整數(shù)規(guī)劃、基于全局QoS約束分解的分布式組合服務(wù)選擇方法，分支界限法、啟發(fā)式算法（如遺傳算法、蟻群算法和粒子群優(yōu)化算法等）。

由于傳統(tǒng)的基于全局選擇策略和局部選擇策略均以全部服務(wù)庫(kù)作為候選服務(wù)集合，隨著候選服務(wù)集服務(wù)數(shù)量的增長(zhǎng)，上述策略的服務(wù)選擇時(shí)間顯著增長(zhǎng)。為了去除冗余服務(wù)，吳鍵等［3］引入數(shù)據(jù)庫(kù)查詢(xún)中Skyline方法，利用Skyline中的支配關(guān)系，縮小了候選服務(wù)空間。王尚廣等人［4］首先通過(guò)云模型計(jì)算QoS的不確定性，然后采用整數(shù)規(guī)劃在Skyline服務(wù)中進(jìn)行服務(wù)選擇。吳建等［5］提出一種利用MapReduce思想進(jìn)行并行Skyline服務(wù)選擇的方法，并探討了一種稱(chēng)為紙帶模型的動(dòng)態(tài)Skyline服務(wù)更新方法。

當(dāng)某一服務(wù)類(lèi)的Skyline服務(wù)數(shù)目太大，從而不能有效處理時(shí)，提出在多個(gè)QoS屬性之間進(jìn)行權(quán)衡，并選擇一系列具有代表性的Skyline服務(wù)作為服務(wù)選擇模型的輸入服務(wù)集，使得這些服務(wù)最可能成為優(yōu)化選擇中的服務(wù)，滿(mǎn)足用戶(hù)的QoS約束并使得效用最大化。

1 Skyline服務(wù)選擇

1.1 Skyline服務(wù)

給定一系列N維空間的點(diǎn)，Skyline查詢(xún)選擇那些沒(méi)有被其他任何點(diǎn)支配的點(diǎn)。若某點(diǎn)Pi在所有N個(gè)維度均不劣于另外某個(gè)點(diǎn)Pj，而且至少在某個(gè)維度上優(yōu)于Pj，則稱(chēng)點(diǎn)Pi支配點(diǎn)Pj。借鑒Skyline的思想，可以基于服務(wù)QoS屬性值定義服務(wù)之間的優(yōu)勢(shì)關(guān)系，并將其用于某一類(lèi)服務(wù)中被其他服務(wù)支配的服務(wù)，進(jìn)行服務(wù)選擇時(shí)可以忽略這些被支配的服務(wù)，從而降低服務(wù)選擇時(shí)需要考慮的服務(wù)數(shù)量。

定義1服務(wù)支配：設(shè)某個(gè)服務(wù)候選集存在某種服務(wù)類(lèi)別S，S中的兩個(gè)服務(wù)x，y∈S，每個(gè)服務(wù)包含一組QoS屬性。x支配y，記為，當(dāng)且僅當(dāng)x的所有QoS值不劣于y，且x至少有一個(gè)QoS屬性值嚴(yán)格優(yōu)于y，即

定義2 Skyline服務(wù)集：候選服務(wù)集的某類(lèi)服務(wù)子集，記作SLs，其集合元素是服務(wù)類(lèi)別S中不被其余服務(wù)支配的全部服務(wù)集合，即。SLs中的服務(wù)被稱(chēng)作服務(wù)類(lèi)別S中的Skyline服務(wù)。

圖1 Skyline服務(wù)示例圖

圖1為一個(gè)服務(wù)類(lèi)別中的Skyline服務(wù)示例圖。其中，任何一個(gè)服務(wù)由響應(yīng)時(shí)間和費(fèi)用兩個(gè)QoS屬性組成［11］。所以，可以用平面上的一個(gè)點(diǎn)表示一個(gè)服務(wù)，點(diǎn)的坐標(biāo)對(duì)應(yīng)服務(wù)的QoS屬性的值。從圖1中可以看出：，原因是不存在其他任何服務(wù)支配服務(wù)a，即不存在有其他服務(wù)的服務(wù)費(fèi)用高于a，且響應(yīng)時(shí)間低于a，所以a屬于Skyline服務(wù)集；同樣可以得出b、c、d以及e也是Skyline服務(wù)。反之，服務(wù)f不是一個(gè)Skyline服務(wù)，因?yàn)閒被服務(wù)b、c和d支配。

1.2 Skyline服務(wù)集的選擇命題

文獻(xiàn)［4］給出并證明了Skyline服務(wù)集的選擇命題1，即最優(yōu)服務(wù)必須來(lái)自Skyline服務(wù)集。

命題2基于Skyline服務(wù)集的服務(wù)選擇能夠提高服務(wù)選擇的效率。

證明：因?yàn)橛脩?hù)需求對(duì)QoS屬性的約束條件與確定Skyline服務(wù)不相關(guān)，因此，不需要在進(jìn)行優(yōu)化選擇時(shí)實(shí)時(shí)在線(xiàn)實(shí)時(shí)進(jìn)行Skyline服務(wù)選擇。所以可以在進(jìn)行服務(wù)匹配、選擇、組合時(shí)不再考慮那些不在Skyline中的服務(wù)，從而提高優(yōu)化選擇的效率。

基于上述分析，服務(wù)代理可以為在服務(wù)注冊(cè)中心維護(hù)一個(gè)Skyline服務(wù)列表。該列表在每一次有服務(wù)加入、離開(kāi)、或者已注冊(cè)服務(wù)QoS信息有變化時(shí)進(jìn)行更新。當(dāng)服務(wù)代理收到一個(gè)服務(wù)請(qǐng)求時(shí)，就直接向服務(wù)請(qǐng)求者返回匹配的服務(wù)類(lèi)別中的Skyline服務(wù)。

2 代表性Skyline服務(wù)選擇

在現(xiàn)實(shí)環(huán)境中，Skyline集合中對(duì)象的數(shù)量會(huì)隨著維度的增加呈指數(shù)增長(zhǎng)。因此，在高維空間，盡管Skyline方法已經(jīng)裁剪了大部分的對(duì)象，但是仍然會(huì)向用戶(hù)呈現(xiàn)大量的Skyline對(duì)象，因此，使用Skyline方法只是第一步，本節(jié)對(duì)Skyline服務(wù)集進(jìn)行篩選，得到最具代表性的Skyline服務(wù)達(dá)到縮小Skyline服務(wù)集的目的。

定義3代表性服務(wù)：代表性服務(wù)是在服務(wù)集合中能夠反應(yīng)同一類(lèi)事物共同特征，并能夠代替該服務(wù)集合中服務(wù)的部分服務(wù)，是整個(gè)服務(wù)集服務(wù)主成分的體現(xiàn)。

同理，代表性Skyline服務(wù)即為在Skyline集合中的部分體現(xiàn)服務(wù)主成分的服務(wù)。

2.1 服務(wù)選擇中的效用函數(shù)

QoS約束的局部服務(wù)選擇或全局服務(wù)選擇均為在滿(mǎn)足QoS約束條件下選擇使QoS效用函數(shù)值最大的服務(wù)。服務(wù)選擇中的效用函數(shù)可采用兩個(gè)步驟計(jì)算：首先規(guī)范化服務(wù)QoS屬性值，即將不同量綱與值域的QoS屬性進(jìn)行屬性值尺度上的規(guī)范并統(tǒng)一。其次基于不同指控用戶(hù)對(duì)QoS屬性的偏好進(jìn)行量化并賦權(quán)，通過(guò)加權(quán)計(jì)算服務(wù)效用函數(shù)值［6-8］。QoS約束的局部服務(wù)可采用多屬性決策理論的加權(quán)和法計(jì)算服務(wù)效用函數(shù)值。然而對(duì)于QoS約束的全局服務(wù)選擇，可用抽象組合服務(wù)流程對(duì)應(yīng)的一個(gè)具體組合服務(wù)的第k個(gè)QoS屬性的最大、最小聚合值計(jì)算過(guò)程可以形式化描述為

式（1）、式（2）中，

而組合服務(wù)CS的效用函數(shù)為

式（7）中，ωk∈R+表示用戶(hù)對(duì)組合服務(wù) QoS 屬性 q′k的重視程度（即權(quán)重）。

2）整體效用U′（CS）最大化。

2.2 順序結(jié)構(gòu)組合服務(wù)選擇模型

完全順序結(jié)構(gòu)的服務(wù)組合問(wèn)題是一個(gè)0-1整數(shù)規(guī)劃問(wèn)題，可以采用文獻(xiàn)［6，9-10］提到的方法進(jìn)行求解。在基于0-1整數(shù)規(guī)劃的QoS約束服務(wù)選擇問(wèn)題時(shí)，服務(wù)sji是否被選擇可表示為0，1二元決策變量xji，若xji=1，則表示在服務(wù)集合中包含候選服務(wù)sji，若xji=0，則表示在服務(wù)集合中不包含候選服務(wù)sji。根據(jù)以上分析，基于0-1整數(shù)規(guī)劃的QoS約束服務(wù)選擇問(wèn)題可被轉(zhuǎn)換成為組合服務(wù)整體效用值的最大值求解問(wèn)題，0-1整數(shù)規(guī)劃的目標(biāo)函數(shù)可定義為

為保證被選取的指控服務(wù)聚合值滿(mǎn)足全局QoS約束條件，必須將其他的約束條件引入整數(shù)規(guī)劃模型。具體包括：

1）將以下約束加入模型

式（9）表示聚合的QoS屬性采用累加方式，如響應(yīng)時(shí)間、價(jià)格、信譽(yù)度等QoS屬性。

2）若QoS屬性之間采用乘法運(yùn)算，例如：可用性、可靠性、可能性等指標(biāo)，約束條件可表示為

為計(jì)算方便，也可對(duì)式（10）取自然對(duì)數(shù)，將乘法運(yùn)算轉(zhuǎn)換成加法運(yùn)算，如式（11）所示。

3）將如下約束條件加入模型

式（12）表示基于最小化函數(shù)的QoS屬性約束，如容量等。

2.3 基于代表性Skyline服務(wù)集的選擇分析

命題3如果某個(gè)服務(wù)si屬于服務(wù)類(lèi)S，并且服務(wù)si支配了另一個(gè)服務(wù)sj，則服務(wù)si的效用函數(shù)值必然優(yōu)于服務(wù)sj的效用函數(shù)值。

命題4通過(guò)優(yōu)化Skyline服務(wù)的匹配過(guò)程，QoS約縮短了服務(wù)匹配選擇時(shí)間。

證明：通過(guò)QoS聚類(lèi)操作后，代表性Skyline服務(wù)選出了效用函數(shù)值最優(yōu)的Skyline服務(wù)，進(jìn)而實(shí)現(xiàn)了指控服務(wù)的最優(yōu)匹配，所以通過(guò)提高服務(wù)匹配成功率，縮小了服務(wù)搜索范圍，縮短了服務(wù)選擇時(shí)間。

3 代表性Skyline選擇算法

代表性Skyline服務(wù)選擇算法的基本原理是：首先采取層次聚類(lèi)操作，將Skyline服務(wù)SL聚類(lèi)為k個(gè)簇，k≤|SL|，并且k為偶數(shù)；其次選取服務(wù)效用函數(shù)值最大的服務(wù)作為代表性Skyline服務(wù)。為實(shí)現(xiàn)代表性Skyline服務(wù)選擇算法，采用樹(shù)形結(jié)構(gòu)表示代表性Skyline服務(wù)的層次關(guān)系數(shù)據(jù)結(jié)構(gòu)，如圖2（d）所示。圖2（d）中，樹(shù)結(jié)點(diǎn)對(duì)應(yīng)SL中的一個(gè)Skyline服務(wù)，除葉子外，其余結(jié)點(diǎn)表示在相應(yīng)簇中選擇的代表性服務(wù)。

具體的服務(wù)搜索策略如下：指控服務(wù)選擇服務(wù)器首先接收用戶(hù)服務(wù)請(qǐng)求，從圖2（d）所示的服務(wù)樹(shù)的根結(jié)點(diǎn)開(kāi)始搜索，由于根結(jié)點(diǎn)代表服務(wù)集中的頂層服務(wù)（圖2（d）中的頂層服務(wù)為候選服務(wù)s3），因此，首先搜索頂層服務(wù)。如果位于該層次的服務(wù)不能滿(mǎn)足用戶(hù)的QoS約束的屬性值，則繼續(xù)向樹(shù)的下層進(jìn)行搜索，不斷重復(fù)該過(guò)程，進(jìn)行從根向葉子的路徑搜索，搜索過(guò)程終止于樹(shù)的分支結(jié)點(diǎn)和葉子結(jié)點(diǎn)。如果搜索到葉子結(jié)點(diǎn)，說(shuō)明問(wèn)題無(wú)解，否則，如果問(wèn)題有解，根據(jù)命題1，搜索過(guò)程將終止于分支結(jié)點(diǎn)，因此，必然會(huì)通過(guò)遍歷二叉樹(shù)求解出最佳的服務(wù)選擇結(jié)果。

對(duì)于組合服務(wù)來(lái)說(shuō)，候選服務(wù)則作為組合方案選擇模型的輸入進(jìn)行求解。如果使用給定的代表服務(wù)沒(méi)有得到滿(mǎn)足用戶(hù)的QoS約束條件，則繼續(xù)處理下一個(gè)級(jí)別的代表服務(wù)，不斷重復(fù)該過(guò)程，直到找到一個(gè)解或者已經(jīng)到達(dá)樹(shù)的最底層，即已經(jīng)嘗試了所有的Skyline服務(wù)。如果問(wèn)題有解，根據(jù)命題1，則遍歷完該二叉樹(shù)一定會(huì)找到優(yōu)化選擇結(jié)果。

圖2 利用層次聚類(lèi)確定代表性服務(wù)

建立代表服務(wù)樹(shù)的過(guò)程本文利用k-means聚類(lèi)算法完成。利用k-means算法對(duì)服務(wù)類(lèi)S的Skyline服務(wù)SL進(jìn)行聚類(lèi)，將SL劃分為k個(gè)簇SL={sl1，sl2，…，slk}，其中，使得每個(gè)簇之間的距離平方和最小，即

式（13）中，μi表示簇i中服務(wù)的質(zhì)心，也稱(chēng)為均值。在多維QoS屬性情況下，服務(wù)質(zhì)心的坐標(biāo)定義為各QoS維度的平均值。

代表性Skyline服務(wù)選擇算法主要分為算法1：基于k-means的Skyline服務(wù)聚類(lèi)算法（如下頁(yè)圖3所示）以及算法2：生成代表服務(wù)樹(shù)算法（如圖4所示）。

圖3 基于k-means的Skyline服務(wù)聚類(lèi)算法

圖4 生成代表性服務(wù)樹(shù)

以算法1的k-means算法為基礎(chǔ)，進(jìn)一步設(shè)計(jì)算法2，用來(lái)生成代表性Skyline服務(wù)樹(shù)。算法2的基本原理如下：步驟1，計(jì)算SL中效用函數(shù)值最大的結(jié)點(diǎn)s，然后再以s作為的根結(jié)點(diǎn)子簇上進(jìn)行搜索；步驟2，通過(guò)k-means算法輸入SL，生成兩個(gè)子簇 CLs［1］和 CLs［2］的聚類(lèi)集合，分別計(jì)算 CLs［1］和CLs［2］子簇中效用函數(shù)值最大的兩個(gè)結(jié)點(diǎn)，并將它們分別作為根s的左右孩子結(jié)點(diǎn)構(gòu)造一顆新的二叉樹(shù)；步驟3，不斷對(duì)每個(gè)子簇重復(fù)執(zhí)行步驟2，使二叉樹(shù)不斷生長(zhǎng)，直至最終子簇中的服務(wù)數(shù)量小于2為止，至此，通過(guò)輸入Skyline服務(wù)集合SL，最終輸出以s為根結(jié)點(diǎn)的代表性服務(wù)二叉樹(shù)。

4 試驗(yàn)分析

基于開(kāi)放的QWS數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)以驗(yàn)證算法的有效性。QWS數(shù)據(jù)集包含了2 442個(gè)Web服務(wù)及其參數(shù)，這些服務(wù)分別來(lái)自于服務(wù)門(mén)戶(hù)網(wǎng)站、UDDI服務(wù)注冊(cè)中心、互聯(lián)網(wǎng)搜索引擎等渠道，由Eyhab Al-Masri博士采用 WSCE（Web Service Crawler Engine）工具構(gòu)建。QWS數(shù)據(jù)集中包括了服務(wù)吞吐率、服務(wù)響應(yīng)時(shí)間等8個(gè)QoS屬性參數(shù)值。實(shí)驗(yàn)環(huán)境基于Windows 7操作系統(tǒng)，CPU來(lái)自Inter公司，主頻3.3 GHz，內(nèi)存為4 GB；使用Java、R語(yǔ)言編寫(xiě)了相關(guān)軟件。為了驗(yàn)證算法性能，設(shè)計(jì)了如下兩組實(shí)驗(yàn)。

實(shí)驗(yàn)1：比較3種QoS約束下Web服務(wù)選擇算法執(zhí)行時(shí)間。

1）多屬性決策服務(wù)選擇方法：不采用Skyline服務(wù)，僅使用局部選擇算法。

2）Skyline服務(wù)選擇方法：在多屬性決策方法基礎(chǔ)上，采用Skyline服務(wù)。

3）代表性Skyline服務(wù)選擇方法：由本文算法1和算法2構(gòu)造的基于代表性Skyline服務(wù)選擇方法。

對(duì)于3種服務(wù)選擇方法，當(dāng)服務(wù)數(shù)量在100～1 000之間取值時(shí)，固定QoS維度及其參數(shù)值，測(cè)試服務(wù)選擇的執(zhí)行時(shí)間，實(shí)驗(yàn)結(jié)果如圖5所示。固定候選服務(wù)數(shù)量，當(dāng)QoS屬性維度及其參數(shù)值在2～8之間變化時(shí)，測(cè)試服務(wù)選擇的執(zhí)行時(shí)間，實(shí)驗(yàn)結(jié)果如圖6所示。

圖5 對(duì)比不同候選服務(wù)數(shù)量上的執(zhí)行時(shí)間

圖6 對(duì)比不同QoS屬性維度上的執(zhí)行時(shí)間

從圖5和圖6中可以看出：1）多屬性決策方法由于搜索空間較大，導(dǎo)致對(duì)QoS參數(shù)值的評(píng)價(jià)數(shù)據(jù)量較大，因此，排序時(shí)間較長(zhǎng)，所以多屬性決策方法的服務(wù)選擇執(zhí)行時(shí)間最長(zhǎng)。2）Skyline方法通過(guò)篩選方法過(guò)濾掉不必要的候選服務(wù)，縮小了服務(wù)選擇的目標(biāo)集合，因此，在多屬性決策方法基礎(chǔ)上，縮短了服務(wù)選擇的執(zhí)行時(shí)間。然而，有些情況下其候選服務(wù)集依舊較大時(shí)，其性能處于3種方法的中間水平。3）在Skyline方法的基礎(chǔ)上，由于引入了代表性Skyline算法，當(dāng)服務(wù)數(shù)量和QoS屬性維度增加時(shí)，依然能夠取得3種方法中最短的服務(wù)選擇實(shí)行時(shí)間。

實(shí)驗(yàn)2：比較整數(shù)線(xiàn)性規(guī)劃和代表性Skyline方法的服務(wù)選擇執(zhí)行時(shí)間和QoS約束的服務(wù)效用值。

實(shí)驗(yàn)參數(shù)包括：1）輸入由10個(gè)服務(wù)組成的Web服務(wù)組合組件；2）每個(gè)組件的服務(wù)數(shù)量為100個(gè)～1 000個(gè)。

實(shí)驗(yàn)中的整數(shù)線(xiàn)性規(guī)劃求解基于Skyline服務(wù)選擇方法，采用文獻(xiàn)［4］給出的啟發(fā)式算法。代表性Skyline方法同樣采用求解整數(shù)線(xiàn)性規(guī)劃方法，不同的是在服務(wù)選擇組件中選擇代表性Skyline服務(wù)。實(shí)驗(yàn)2的測(cè)試結(jié)果如圖7和圖8所示。

圖7 對(duì)比不同候選服務(wù)數(shù)量上服務(wù)組合執(zhí)行時(shí)間

從圖7中可以看出：當(dāng)候選服務(wù)數(shù)量在100～1 000范圍內(nèi)變化時(shí)，代表性Skyline服務(wù)選擇算法明顯優(yōu)于僅結(jié)合Skyline服務(wù)的整數(shù)規(guī)劃算法，其服務(wù)選擇執(zhí)行之間至少縮短了25%，且當(dāng)服務(wù)數(shù)量大于800時(shí)，二者的服務(wù)選擇執(zhí)行時(shí)間差距顯著增加。

圖8 對(duì)比不同候選服務(wù)數(shù)量服務(wù)組合效用值

從圖8中也可以得出代表性Skyline服務(wù)選擇算法在效用值指標(biāo)上也明顯優(yōu)于僅結(jié)合Skyline服務(wù)的整數(shù)規(guī)劃算法，其服務(wù)選擇平均效用值約提升10%。

5 結(jié)論

在存在QoS約束的服務(wù)選擇中，不僅需關(guān)注服務(wù)組合的功能，還需考慮服務(wù)選擇的性能優(yōu)選服務(wù)。通過(guò)在傳統(tǒng)的多屬性決策變量的方法基礎(chǔ)上，提出了代表性Skyline服務(wù)選擇算法，該方法基于k-means的Skyline服務(wù)聚類(lèi)算法，通過(guò)生成具有多維QoS屬性的代表性Skyline服務(wù)二叉樹(shù)，在縮小服務(wù)候選集合的基礎(chǔ)上，通過(guò)樹(shù)形結(jié)構(gòu)查找高效的特點(diǎn)提升了服務(wù)選擇性能指標(biāo)。通過(guò)在QWS數(shù)據(jù)集應(yīng)用代表性Skyline服務(wù)選擇算法進(jìn)行了數(shù)據(jù)實(shí)驗(yàn)，結(jié)果表明所提出的方法在服務(wù)選擇執(zhí)行時(shí)間和服務(wù)效用值兩個(gè)指標(biāo)上均優(yōu)于傳統(tǒng)算法。對(duì)于QoS約束的Web服務(wù)選擇的后續(xù)工作，需進(jìn)一步對(duì)組合服務(wù)Skyline計(jì)算以及對(duì)Web服務(wù)的QoS預(yù)測(cè)方面進(jìn)行研究。