Web服務(wù)選擇動態(tài)Qos情況下的k-支配skyline改進(jìn)?

何 誠 歐陽中輝 司維超

（海軍航空工程學(xué)院 煙臺 264001）

1 引言

Web服務(wù)技術(shù)［1］是一種分布式計算模型，能使得不同機(jī)器上運(yùn)行的不同應(yīng)用跨越內(nèi)部語言、平臺和協(xié)議的障礙，自由地集成或交換數(shù)據(jù)。這就為各個不同企業(yè)間的Web服務(wù)搭建了一個通用機(jī)制，有效推進(jìn)了電子商務(wù)的發(fā)展。伴隨著人們需求的提高與計算機(jī)技術(shù)的飛速發(fā)展，大量的Web服務(wù)被發(fā)布到Internet中供用戶使用，但因為服務(wù)提供者的不同，往往這些Web服務(wù)中有許多都是功能相同，但服務(wù)質(zhì)量Qos有差別的。針對這些功能相同、Qos有差別的的服務(wù)，如何利用各Web服務(wù)的Qos屬性來進(jìn)行服務(wù)選取成為了學(xué)術(shù)界關(guān)注的熱點(diǎn)。

文獻(xiàn)［2］提出了一種基于模糊層次分析法的多維Qos局部最優(yōu)服務(wù)選擇模型，該模型將Qos的真實度屬性作為Qos屬性向量的分量之一，建立了包含客觀屬性和主觀評價的一種雙重質(zhì)量屬性模糊層次結(jié)構(gòu)，從各方面綜合考察了客觀和主觀的Qos屬性對于服務(wù)選擇的影響，然而這種選擇模型并沒有考慮動態(tài)Qos屬性值的波動問題。文獻(xiàn)［3～4］提出了一種基于上下文感知的服務(wù)選取方法，該方法采用Web本體描述語言/資源描述框架模型，將上下文轉(zhuǎn)化為服務(wù)類別和用戶領(lǐng)域相關(guān)的約束值。以上研究方法在很大程度上提高了服務(wù)選擇的準(zhǔn)確性和可靠性，但是沒有考慮到Web服務(wù)動態(tài)Qos屬性值的波動性。

隨著時間的變化，Web服務(wù)在運(yùn)行過程中Qos屬性值會實時波動，如反應(yīng)時間、可靠性、反應(yīng)成功率等屬性在實時的Web服務(wù)中并不是固定不變的，這些波動的Qos屬性值會影響到Web服務(wù)的選擇，因此根據(jù)固定的Qos屬性值進(jìn)行服務(wù)選取的準(zhǔn)確性還有待改進(jìn)。文獻(xiàn)［5］建立了區(qū)間型Qos模型，引入?yún)^(qū)間數(shù)和相似度概念，提出了一種基于動態(tài)Qos的Web服務(wù)選取方法；文獻(xiàn)［6］為了Qos信息能實時反映出實際服務(wù)質(zhì)量，明確了Qos動態(tài)更新概念利用了完整有效的更新數(shù)據(jù)源，提出了一種基于實時定期修正的Qos動態(tài)更新策略與算法。

本文通過動態(tài)Qos屬性的統(tǒng)計分布，計算Web服務(wù)成為skyline的概率，利用概率建立索引，優(yōu)化k-支配skyline算法。最后實驗驗證改進(jìn)后的Prob?ability index based算法的高效性。

2 Web服務(wù)的動態(tài)Qos屬性

2.1 Qos屬性的概率密度函數(shù)

Web服務(wù)的Qos屬性有許多種，在AL-MASRI E等人通過統(tǒng)計互聯(lián)網(wǎng)上真實的Web服務(wù)Qos屬性就有 13 種［7～9］，這些 Qos屬性從不同的方面反映了Web服務(wù)的服務(wù)質(zhì)量。然而在現(xiàn)實的網(wǎng)絡(luò)環(huán)境中，由于各種不確定因素的影響，Web服務(wù)的Qos屬性具有波動性，呈現(xiàn)了一種動態(tài)現(xiàn)象。在此情況下，本文研究時選取了Web服務(wù)的四種Qos屬性，并且通過周期采集Qos屬性，估計Web服務(wù)的Qos屬性分布。將Web服務(wù)的四種Qos屬性定義為一個四維向量Qos=（T，E，A，R），各個分量的具體含義如下。

1）響應(yīng)時間T：從用戶發(fā)送服務(wù)請求至獲取Web服務(wù)所花費(fèi)的時間。顯然，響應(yīng)時間會隨著網(wǎng)絡(luò)運(yùn)行狀況的不同而動態(tài)變化。

2）信譽(yù)度E：Web服務(wù)的可信程度。Web服務(wù)的信譽(yù)度主要由使用過該Web服務(wù)的用戶評價所決定。由于用戶的個人偏好差異和其他Qos屬性的波動，不同用戶或在不同時間使用同一Web服務(wù)可能會讓用戶對該Web服務(wù)有不同的評價。

3）可用性A：Web服務(wù)被正常使用的概率。隨著網(wǎng)絡(luò)環(huán)境的變化，Web服務(wù)被正常使用的情況也是動態(tài)變化的。

4）可靠性R：Web服務(wù)正確響應(yīng)用戶請求的概率。網(wǎng)絡(luò)環(huán)境的變化同樣影響著服務(wù)的可靠性，較差的網(wǎng)絡(luò)環(huán)境會使服務(wù)信息在傳輸過程中丟失或失效的概率變大。

在Web服務(wù)對外提供服務(wù)的過程中，通過周期T來采樣Qos屬性會得到如表1所示的采樣數(shù)據(jù)，在自然情況下Web服務(wù)的Qos屬性服從高斯分布，采樣數(shù)據(jù)通過參數(shù)估計得到該Web服務(wù)各Qos屬性值的概率密度函數(shù) fWeb(t，e，a，r)。

表1 采樣數(shù)據(jù)表

2.2 Web服務(wù)成為skyline概率計算

為了篩選功能相同，但服務(wù)質(zhì)量Qos不同的Web服務(wù)。文獻(xiàn)［10～13］引用了skyline算法對這一類Web服務(wù)選擇進(jìn)行篩選。有些Web服務(wù)在所有的Qos屬性上都優(yōu)于或等于某些Web服務(wù)，因此這些在所有Qos屬性上都差的Web服務(wù)就沒有參與選擇的價值，這些Web服務(wù)不可能是最優(yōu)選擇，這就引入了skyline算法的支配概念。

定義1 Web服務(wù)Wi與Web服務(wù)Wj的服務(wù)質(zhì)量 Qos屬性分別為 Qosi=（ai1，ai2，…，ain）和 Qosj=（aj1，aj2，…，ajn），如果對于 ? aik∈R，1≤k≤n ，都有aik優(yōu)于或等于ajk，且至少在某一維上aik優(yōu)于ajk，則稱Web 服務(wù) Wi支配 Web 服務(wù) Wj，記為 Wi→Wj；否則稱Web服務(wù) Wi不支配Web服務(wù)Wj，記為 Wi/→Wj。

定義2 對于任意的Web服務(wù)Wi，經(jīng)由skyline算法計算返回的節(jié)點(diǎn)集B滿足B=｛Wi|Wi∈N+，?Wj∈N+，Wj≠Wi，Wj/→Wi｝，稱集合B為skyline節(jié)點(diǎn)集，記為SK。

通過skyline算法計算得到功能相同，Qos屬性不同的Web服務(wù)集即SK。篩選掉被支配的Web服務(wù)后，減小了輸入的規(guī)模，提高了Web服務(wù)選擇效率。

本文取響應(yīng)時間T和信譽(yù)度E的2維Qos屬性作為研究的對象，得出概率的計算方法后將方法引申到多維中。為了定義屬性值取小為優(yōu)，對于信譽(yù)度E在計算過程中取倒數(shù)1/E，信譽(yù)度E越大倒數(shù)1/E越小。

對于Web服務(wù)，在Qos屬性響應(yīng)時間T中，響應(yīng)時間T理論上最小值收斂于0，最大值為+∞，因而Web服務(wù)的概率分布 fWeb(t，1/e)的定義域為（0，+∞）。

設(shè)有 Web 服務(wù)W1和 Web服務(wù) W2，W1和W2的概率分布分別為 fWeb1(t1，e1)和 fWeb2(t2，e2)。Web服務(wù) W1的 Qos屬性 t，e在定義域內(nèi)任意取值 t1，e1時，當(dāng)Web服務(wù)W2的Qos屬性在取值域｛（t，e）|0 ≤ t≤t1，0 ≤ 1/e ≤ 1/e1｝中（即圖1所示陰影面積S2→1），Web服務(wù)W1被W2支配。

則在 t1，1/e1時，W1被W2支配的概率

圖1 支配區(qū)域圖

由Web服務(wù)W1在t1，1/e1時被W2支配的概率可以得到W1被W2支配的概率期望：

同理可得

將Web服務(wù)的Qos屬性引申到n維后，可以得到Web服務(wù)Wi被Wj支 配的期望概率

用Web服務(wù)Wi被Wj支配的期望概率表示W(wǎng)i被Wj支配的概率，則Web服務(wù)i屬于SK的概率可表示為

3 概率索引優(yōu)化k-支配skyline算法

隨著Internet上發(fā)布的Web服務(wù)數(shù)量急劇增加和Web服務(wù)的Qos服務(wù)質(zhì)量增多，數(shù)據(jù)點(diǎn)集中屬于skyline點(diǎn)集的數(shù)據(jù)點(diǎn)增多并且每一個數(shù)據(jù)點(diǎn)支配其他數(shù)據(jù)點(diǎn)的概率會降低，這也就意味著經(jīng)過sky?line操作選出來的skyline點(diǎn)集依然很大，這對于Web服務(wù)選擇來說是十分不友好的。為了解決skyline點(diǎn)集過大的問題，Chee-Yong Chan和H.V.Jagadish等人提出了在高維空間中尋找k-支配sky?line點(diǎn)集的方法［11］，通過所提出的k-支配的概念，從skyline點(diǎn)集中繼續(xù)篩選k-支配點(diǎn)集，隨著k的縮小，這一點(diǎn)集也會越來越小，那么合適的Web服務(wù)數(shù)據(jù)數(shù)量可以通過選取k來控制。

對于一個 n 維空間 S=｛s1，s2…sn｝，當(dāng)且僅當(dāng)每一個pi∈P都是S上的d維數(shù)據(jù)時，一個由點(diǎn)pi組成的集合P=｛p1，p2…pn｝被稱為n維空間S上的數(shù)據(jù)集和。

定義 3.1 k-支配當(dāng)且僅當(dāng)?S′?S，|S′|=k，?sr∈S′，pi.sr≥pj.sr，并且?st∈S′，pi.st＞pj.st時，稱 pi是 k-支配pj。

定義3.2 k-支配skyline集如果一個數(shù)據(jù)點(diǎn)pi不被數(shù)據(jù)集合中任意其他數(shù)據(jù)點(diǎn)pj所k-支配，則數(shù)據(jù)點(diǎn)pi是該數(shù)據(jù)集合中k-支配skyline集的數(shù)據(jù)點(diǎn)。我們用DSP（k，P，S）表示空間S中的數(shù)據(jù)集合的k-支配skyline集。

定義3.3 如果數(shù)據(jù)點(diǎn)集D中存在一個不屬于k-支配skyline集的數(shù)據(jù)點(diǎn)pi，那么可以得到一下兩個結(jié)論。

1）在數(shù)據(jù)點(diǎn)集的skyline集中必然存在一個skyline點(diǎn)k-支配數(shù)據(jù)點(diǎn)pi；

2）數(shù)據(jù)點(diǎn)pi可能不被任何k-支配skyline點(diǎn)支配。

在文獻(xiàn)［11］中提出了利用定義3.3進(jìn)行全表掃描的One-Scan算法。在數(shù)據(jù)點(diǎn)集R中的數(shù)據(jù)點(diǎn)是通過全表掃描、逐個地比較，慢慢趨近最終結(jié)果的。如果被支配的數(shù)據(jù)點(diǎn)pi被過早拿來比較，極有可能因為支配pi的數(shù)據(jù)點(diǎn)pj還未參與算法，而被“錯誤”地放進(jìn)點(diǎn)集R中，這會引起其他的skyline點(diǎn)與非skyline點(diǎn)與這一數(shù)據(jù)點(diǎn)pi進(jìn)行比較，直到支配pi的數(shù)據(jù)點(diǎn)pj參與算法，數(shù)據(jù)點(diǎn)pi才會被移除，而中間過程已經(jīng)造成了許多多余的比較運(yùn)算。

在計算skyline集時可以利用數(shù)據(jù)點(diǎn)各個維度的大小順序建立索引，而在計算k-支配skyline集中，由于圖2所示數(shù)據(jù)點(diǎn)間的非傳遞關(guān)系［11］，數(shù)據(jù)點(diǎn)在某一維所單獨(dú)占有的優(yōu)勢在算法中被弱化，至少在k維占有優(yōu)勢才有說服力。因此，在skyline算法中利用各個維度的數(shù)據(jù)大小建立索引的方式在k-支配skyline算法中失去了應(yīng)有的效益。文獻(xiàn)［11］中One-Scan算法采用了對所有維度值求和，用和值排序的方法。

在Web服務(wù)的動態(tài)Qos屬性中，各Web服務(wù)可能成為skyline點(diǎn)的概率期望可以通過動態(tài)Qos屬性的概率密度函數(shù)得到。通過概率建立如圖3所示的索引，概率越大說明Web服務(wù)在各維度的綜合屬性越好即有越大的概率成為k-支配skyline服務(wù)。改進(jìn)后的算法為Probability index based算法（PIBA），PIBA通過建立概率索引減少“錯誤”服務(wù)的數(shù)量，提高算法效率。

圖2 非傳遞支配關(guān)系圖

圖3 概率索引圖

Probability index based算法如下：

1）establishapossibilityindex for W

2）initializesetof k-dominant skyline points R=0

3）initialize set of unique non-k-domnant sky?line points T=o

4）for every point∈W used index do

5）initialize isUniqueSkyline=true

6） for every point p′∈T do

7）if（p dominates p′）then

8） remove p′from T

9）else if（p′dominates p）or（p=p′）then

10） isUniqueSkyline=false

11） break out of inner for-loop

12）if（isUniqueSkyline）then

13）initialize isDominant=true

14） for every point p′∈R do

15）if（p′k-dominates p）then

16） isDominant=false

17）if（p k-dominates p′）then

18） remove p′from R to T

19）if（isDominant）then

20） insert p into R

21）else

22） insert p into T

23）return R

4 分析與實驗

實驗的軟硬件環(huán)境為：Visual C++6.0，Intel Pentium42.4GHz，4GRAM，Windows7，Matlab R2014a。實驗采用的數(shù)據(jù)集是WS-DREAM數(shù)據(jù)［12］，該數(shù)據(jù)集統(tǒng)計了142個用戶在獲取4500個真實服務(wù)時的Qos屬性值。通過WS-DREAM數(shù)據(jù)集中Web服務(wù)Qos質(zhì)量的統(tǒng)計值，本文采用極大似然估計法得到Web服務(wù)各Qos質(zhì)量的高斯分布，利用Matlab完成概率計算的預(yù)處理步驟，然后建立索引，并且利用各分布隨機(jī)產(chǎn)生Qos屬性值，最后利用Visual C++6.0完成概率索引k支配算法PIBA的仿真實驗。

實驗在相同軟硬件環(huán)境下取Web服務(wù)中的14維Qos屬性，通過實驗比較改進(jìn)后的概率索引算法PIBA與現(xiàn)有的k-支配skyline算法在不同k值情況下處理Web服務(wù)動態(tài)Qos屬性的處理時間，來反應(yīng)概率索引算法的高效性。實驗結(jié)果如圖4所示。

圖4 處理時間結(jié)果圖

由圖4可知，One-Scan算法的綜合表現(xiàn)最差，在實驗的所有k值上處理時間都最長，但因為One-Scan一次計算需要兩次全表掃描，因此表現(xiàn)雖差卻十分穩(wěn)定，不隨k值變化而發(fā)生較大變化，可這種穩(wěn)定性是犧牲時間復(fù)雜度與IO花銷換來的。

Two-Scan算法在12維以下的效率比Sorted re?trieve算法要高，但是隨著k值的增長Two-Scan算法的效率逐漸增高，甚至在k=14時算法效率近似于One-Scan算法，這是由于k越小，支配的約束越強(qiáng)，在第一次掃描中能通過支配關(guān)系淘汰的數(shù)據(jù)點(diǎn)就越多，但是隨著k的增長這種高效性會逐漸降低。

Sorted retrieve算法總體來說效益高，穩(wěn)定性好，在各個k取值情況下的效率都表現(xiàn)較好。

本次實驗結(jié)果顯示改進(jìn)后的Possibility index based算法在各個k取值情況下計算效率都是最高的、計算速度始終是最快的。

5 結(jié)語

由于k-支配定義中關(guān)于支配定義的強(qiáng)化，導(dǎo)致了非傳遞性的支配關(guān)系，這種強(qiáng)化后的支配關(guān)系不能在一個數(shù)據(jù)點(diǎn)被支配后就直接過濾數(shù)據(jù)點(diǎn)所支配的其他數(shù)據(jù)點(diǎn)，因此一般性的索引在k-支配skyline計算中不起作用。

本文考慮了在Web服務(wù)的動態(tài)Qos屬性下，經(jīng)由統(tǒng)計數(shù)據(jù)估計服務(wù)分布，利用分布得到了各Web服務(wù)成為skyline服務(wù)的概率，這種概率綜合反映了Web服務(wù)在各Qos屬性下的綜合能力，利用此概率建立索引來優(yōu)先將較強(qiáng)支配力的數(shù)據(jù)點(diǎn)先加入計算過程，用以提早排除較差數(shù)據(jù)點(diǎn)，實驗證明本算法比現(xiàn)有的3種算法有更高的效率。

對于k-支配skyline算法，能否建立更加高效的索引機(jī)制來提前進(jìn)行數(shù)據(jù)點(diǎn)的過濾是可以進(jìn)一步研究的問題。同時，如何更科學(xué)統(tǒng)計動態(tài)Qos屬性的值與估計Qos屬性的分布也是值得探討的問題。