楊 莉 張文生 許國艷

1(河海大學(xué)信息中心 江蘇 南京 210098)2(華東宜興抽水蓄能有限公司 江蘇 宜興 214205)3(河海大學(xué)計算機與信息學(xué)院 江蘇 南京 211100)

?

基于Skyline服務(wù)的Top-k選擇方法

楊 莉1張文生2許國艷3

1(河海大學(xué)信息中心 江蘇 南京 210098)2(華東宜興抽水蓄能有限公司 江蘇 宜興 214205)3(河海大學(xué)計算機與信息學(xué)院 江蘇 南京 211100)

為縮小Skyline服務(wù)集，提高服務(wù)選擇的效率，提出一種Skyline服務(wù)Top-k選擇方法。首先，用數(shù)據(jù)推理的方式為Skyline服務(wù)的Top-k選擇提供理論依據(jù)，并提出Skyline服務(wù)Top-k選擇的相關(guān)命題；然后，基于這些命題，提出Skyline服務(wù)Top-k選擇算法，該算法可以得到被選擇可能性最大的Top-k Skyline服務(wù)集；最后，通過實驗證明，該方法能有效降低服務(wù)選擇的時間，而不影響服務(wù)組合的最終結(jié)果。

Skyline服務(wù) Top-k 服務(wù)選擇

0 引 言

伴隨著經(jīng)濟的快速發(fā)展，服務(wù)化成為了產(chǎn)業(yè)發(fā)展的必然趨勢，各種生產(chǎn)活動的成果逐漸開始以服務(wù)方式向用戶進行交付[1]。進而，互聯(lián)網(wǎng)上的服務(wù)種類越來越豐富，服務(wù)數(shù)據(jù)越來越繁雜，服務(wù)選擇的優(yōu)化成為了一個亟需解決的問題。

目前，Skyline服務(wù)選擇成為了服務(wù)選擇優(yōu)化的一大研究熱點[2,4,5]。這些研究大多是通過引入Skyline計算，選擇出Skyline服務(wù)集，去除冗余服務(wù)，從而減小候選服務(wù)集大小、提高服務(wù)選擇的效率。但是，這些研究只是去除了被支配的冗余服務(wù)，剩下的Skyline服務(wù)集仍然是一個非常龐大的服務(wù)集，這些服務(wù)必定只有少部分才會用于服務(wù)組合。所以，對候選服務(wù)進行二次篩選，選出能被選擇的可能性最大的Skyline服務(wù)集，成為Skyline選擇方法亟待解決的難題。

為了提高服務(wù)選擇的效率，縮小Skyline服務(wù)集的大小，提出了Skyline服務(wù)Top-k選擇方法。該方法可快速求解到最優(yōu)的Top-k Skyline服務(wù)，去除冗余的Skyline服務(wù)，有效降低服務(wù)選擇的時間，而不會影響服務(wù)組合的結(jié)果。

1 相關(guān)介紹

1.1 Skyline服務(wù)

Skyline 計算(查詢)[3]就是從一個數(shù)據(jù)庫中抽取出不被其他任一數(shù)據(jù)對象所支配的所有數(shù)據(jù)對象的集合，也稱為Pareto (即在不損害他方利益的情況下，使得自身已達最優(yōu))。目前，Skyline計算已經(jīng)被引入到服務(wù)領(lǐng)域。

定義1服務(wù)支配[2]：設(shè)存在一個服務(wù)類S={s1,s2,…,sn}, s1和s2為其中的兩個候選服務(wù)，并且每個服務(wù)都有k個QoS屬性。如果?i∈[1, k] , s1(i)≥s2(i) (≥表示好于或等于)，且?j∈[1, k], 使得s1(j)>s2(j) (>表示好于)，那么就有s1

定義2Skyline服務(wù)集[2]：Skyline服務(wù)集是指在某一服務(wù)類S中不被其他任一服務(wù)所支配的最小候選服務(wù)的集合，記為SkyS，SkyS={si∈S|?sj∈S:sj

1.2 基于云模型的Skyline服務(wù)選擇

文獻[2]將Skyline計算引入到服務(wù)選擇中，通過剔除候選服務(wù)中的冗余服務(wù)，得到Skyline服務(wù)集，從而縮小候選服務(wù)集的大小、提高服務(wù)選擇的效率，并求解出基于QoS全局約束的服務(wù)選擇的解。同時，文獻[2]提出了命題1，即服務(wù)選擇一定選擇自Skyline服務(wù)集，并為它的Skyline服務(wù)選擇方法提供了理論依據(jù)。

命題1[2]設(shè)最優(yōu)組合服務(wù)為S={s1,s2, …,sn} (si是對應(yīng)組合服務(wù)類Si中選擇出的服務(wù))，那么對于S中的每一個服務(wù)，都屬于對應(yīng)組合服務(wù)類的Skyline服務(wù)(記為SkySi)，即si∈SkySi。

2 基于Skyline服務(wù)的Top-k選擇

文獻[2]將Skyline計算引入到服務(wù)選擇中，剔除冗余的候選服務(wù)，降低候選服務(wù)集的大小，從而提高了服務(wù)選擇的效率。但是，這只是服務(wù)選擇的第一步，因為剔除了冗余的候選服務(wù)后，得到的Skyline服務(wù)集仍然是一個非常龐大的數(shù)據(jù)集。本節(jié)將對Skyline服務(wù)集進行篩選，選擇出最優(yōu)的Top-k Skyline服務(wù)，達到縮小Skyline服務(wù)集大小，而不會影響服務(wù)組合的目的。

2.1 理論基礎(chǔ)

服務(wù)選擇最終是為了服務(wù)組合，本節(jié)從服務(wù)組合角度，用數(shù)學(xué)推理的方式給出了基于Skyline服務(wù)的Top-k選擇的理論依據(jù)。

眾所周知，基于QoS全局約束的服務(wù)選擇的重點是從所有可能的服務(wù)組合中選擇一個QoS效用函數(shù)值最大且滿足全局QoS約束的組合。例如，假設(shè)最終的最優(yōu)服務(wù)組合為S={s1,s2,…,sn}，那么，它必須滿足兩個條件：

a) 所有服務(wù)類的QoS效用函數(shù)值U(S)最大；

b) QoS屬性聚合值qj(S)≤Cj，其中qj(S)為S的第j個QoS屬性聚合值，Cj為相對應(yīng)的約束值。

本文設(shè)定服務(wù)組合的所有可能組合按QoS效用函數(shù)排序，取其Top-k，最大限度的容許了條件b)的成立，所以，關(guān)鍵在于條件a)，即使服務(wù)的QoS效用函數(shù)值最大。

在順序模型中，服務(wù)組合S={s1,s2,…,sn}，服務(wù)類si的質(zhì)量屬性為q(si)={q1, q2,…,qj,…,qm}，則S的QoS效用函數(shù)值為:

(1)

均按照正屬性來處理，其中Qjmax和Qjmin分別為所有服務(wù)類的質(zhì)量屬性qj的最大值和最小值，由于其余三種模式均可轉(zhuǎn)化為順序模式求解[6,8]，僅考慮順序模式。

如果所有的服務(wù)類在進行服務(wù)組合之前已經(jīng)進行了歸一化處理(處理后均為正屬性)，即每個服務(wù)類的每個QoS屬性的最大值和最小值均分別為1和0，另外，由于服務(wù)組合的QoS屬性的計算方式主要分為3種：累和，累積，最小值。所以，分三種情況分析。

(1) 累和：如響應(yīng)時間，價格，信譽度等

此時，服務(wù)組合S的QoS屬性的最小值肯定為0，所以效用函數(shù)變換為:

又由于對于有系數(shù)的QoS屬性，例如信譽度，有1/n，因為分子、分母都有，消去。所以，如果考慮的QoS屬性均為累和形式，則服務(wù)組合的效用函數(shù)變換為:

(2)

即，服務(wù)組合的效用函數(shù)與每個服務(wù)類所選擇的服務(wù)的效用函數(shù)相關(guān)。所以，可以依據(jù)每個服務(wù)類中候選服務(wù)的效用函數(shù)值進行選擇服務(wù)，而具體的依據(jù)或者具體的效用函數(shù)值范圍的界定，由下節(jié)命題給出。

(2) 累積：如可用性，可靠性，可能性

可見，看不出與每個服務(wù)類所選擇的服務(wù)的效用函數(shù)的關(guān)系，但可以肯定，如果此種計算方式的QoS屬性個數(shù)所占比重較少，且權(quán)重不大，其數(shù)值相對較小。

(3) 最小值：如吞吐量

也看不出其與每個服務(wù)類選擇出的服務(wù)的效用函數(shù)的關(guān)系，但是在權(quán)重非常小的情況下，其值相對也較小。

綜上，如果一個服務(wù)組合，有a個屬于累和類型的QoS屬性(令其屬性標(biāo)簽為1至a)，有b個屬于累積類型的QoS屬性(令其屬性標(biāo)簽為a+1至a+b)，有c個屬于最小值類型的QoS屬性(令其屬性標(biāo)簽為a+b+1至a+b+c)，那么服務(wù)組合的效用函數(shù)可變換為

其中，U(i)表示第i個服務(wù)、第1至a個QoS屬性的效用函數(shù)值。可以看出，如果累積和最小值方式的QoS屬性相對比較少(甚至沒有)，且其權(quán)重也不占主要地位，累和形式的結(jié)果就成了最終服務(wù)組合的效用函數(shù)值最主要的部分。在這種情況下，可以通過候選服務(wù)的效用函數(shù)值來界定被選擇用來進行服務(wù)組合的可能性，達到降低Skyline服務(wù)集大小、提高服務(wù)選擇效率的目的。這種方法的誤差為:

2.2 相關(guān)命題

由上節(jié)可知，候選服務(wù)的效用函數(shù)值與服務(wù)組合是存在一定的函數(shù)關(guān)系的，對服務(wù)組合的某一個服務(wù)類而言，可以依據(jù)候選服務(wù)的效用函數(shù)值來界定一個范圍，該范圍內(nèi)的Skyline服務(wù)是最有可能被選擇后用于服務(wù)組合的。本節(jié)將給出基于Skyline服務(wù)進行Top-k選擇的相關(guān)命題及其證明。

命題2如果對服務(wù)組合按照效用函數(shù)值進行Top-k排序，那么對于任意的服務(wù)組合S={s1,s2,…,sn} (si是對應(yīng)服務(wù)類Si中選擇出的服務(wù))，si一定屬于其對應(yīng)的Skyline服務(wù)集的Top-k(按效用函數(shù)排序)。

證明：反證法

假設(shè)對于服務(wù)組合S={s1,s2,…,sn}，S屬于Top-k，si是對應(yīng)服務(wù)類Si中選擇出的服務(wù)，?sim∈SkySi(m>k)，sim表示服務(wù)類中排名第m的服務(wù)。

由于按照QoS效用函數(shù)(累和形式的QoS屬性效用函數(shù)值)排序的，所以對于SkySi服務(wù)類，其效用函數(shù)排序為si1>si2>…>sik>sim。

又由于在順序模型中，服務(wù)組合的QoS效用函數(shù)與各個服務(wù)類效用函數(shù)值的關(guān)系如式(2)所示，所以，有k個服務(wù)組合S1={s1,…,si1,…,sn}、S2={s1,…,si2,…,sn}、… 、Sk={s1,…,sik,…,sn}，它們的QoS效用函數(shù)一定大于服務(wù)S，這與條件“S屬于Top-k”相矛盾，所以，假設(shè)不成立，命題得證。

命題3對于任一服務(wù)類S，如果其中的一個服務(wù)s1支配另一個服務(wù)s2，那么服務(wù)s1的QoS效用函數(shù)一定優(yōu)于服務(wù)s2的效用函數(shù)。

證明：設(shè)服務(wù)s1={x1, x2, …, xk}，服務(wù)s2={x1,x2, …,xk}。

由于s1

又由于QoS效用函數(shù)是各個質(zhì)量屬性的聚合值，聚合值隨著各個屬性值的越大也越大，所以QoS效用函數(shù)也是單調(diào)函數(shù)，由此可知s1的效用函數(shù)一定優(yōu)于s2的效用函數(shù)。得證。

2.3 Skyline服務(wù)的Top-k選擇算法

根據(jù)上一節(jié)的命題，本節(jié)提出了基于Skyline服務(wù)Top-k選擇算法，算法流程如圖1所示。

圖1 基于Skyline服務(wù)的Top-k選擇算法流程圖

該算法是一個并行算法，一邊對候選服務(wù)集進行Skyline計算，一邊根據(jù)效用函數(shù)進行排序，最終得到Top-k的Skyline服務(wù)集。算法代碼如下：

輸入：服務(wù)類s

輸出：服務(wù)類s的前top-k個Skyline服務(wù)，即topk

list topk_sky(s)

{ list topk=new ArrayList();

Boolean mark;

//標(biāo)記是否在topk中找到支配點或被支配點

int i=0,j,m;

//i用于標(biāo)記入topk的個數(shù)，m為候選服務(wù)的指標(biāo)

for(m=0;m

{ mark=false;

if(i==0)

//topk中無服務(wù)，直接將服務(wù)加入topk列表中

{ 計算s.get(m).qos;

//計算服務(wù)s.get(m)的效用函數(shù)值

topk.add(s.get(m));

i++;

}

else

{ //根據(jù)命題1，最終被選擇出的服務(wù)一定是不被支配的

//服務(wù)，所以，將候選服務(wù)依次與topk中的暫時不被支配的服務(wù)比較，將

//最終不被支配的服務(wù)放入topk中

for(j=i-1;j>=0;j--)

{ if(match(s.get(m), topk.get(j))

//s.get(m)支配topk.get(j)

{ 計算s.get(m).qos;

//計算服務(wù)s.get(m)的效用函數(shù)值

//根據(jù)命題3，支配服務(wù)的效用函數(shù)大于被支配服務(wù)，

//只需與被支配服務(wù)后的效用函數(shù)大于它的服務(wù)比較

if(mark==false)

//第一次找到topk中被支配的服務(wù)，插入適當(dāng)?shù)奈恢?/p>

{ int t;

for(t=j+1;t

{ if(topk.get(t).getQos()

topk.set(t-1, topk.get(t));

else

{ topk.set(t-1, s.get(m));

break;

}

}

(t==topk.size())topk.set(t-1, s.get(m));

}

else { topk.remove(j); //支配服務(wù)s.get(m)已

//經(jīng)插入到topk適當(dāng)?shù)奈恢昧?，只需刪除topk中其他被支配的服務(wù)

i--;

}

mark=true;

}

else if(match(topk.get(j),s.get(m))

//服務(wù)s.get(m)被topk.get(j)支配

{ mark=true;

break;

}

else continue;

}

}

if(mark==false&&j==-1)

//互不支配

{ 計算s.get(m).qos;

//計算服務(wù)s.get(m)的效用函數(shù)值

if(i==k) //根據(jù)命題2，最終的選擇出的服務(wù)一定屬于

//Top-k，所以，topk列表只需要k個最終不被支配的服務(wù)。

{ if(s.get(m).qos>topk.get(0).qos) //若s.get(m)的

//效用函數(shù)比topk列表中最小效用函數(shù)的服務(wù)大，刪除效用函數(shù)最小的服務(wù)

{ topk.remove(0);

//去除QoS值最小的

i--;

//還原i的值

}

else continue;

}

int t;

for(t=i-1;t>=0;t--)

//將候選服務(wù)s.get(m)插入topk列表合適的位置，實現(xiàn)排序的要求

{ if(topk.get(t).qos

{ if(t+1>=topk.size()) topk.add(new ServiceTest());

topk.set(t+1)=s.get(m);

break;

}

else

{ if(t+1>=topk.size()) topk.add(new ServiceTest());

topk.set(t+1)=topk.get(t);

continue;

}

}

if(t==-1) topk.set(t+1)=s.get(m);

i++;

}

}

return topk;

}

3 實驗與分析

本文對Skyline服務(wù)Top-k選擇方法的對比分析以及其對服務(wù)組合的影響，進行了兩個實驗。

所有實驗均基于公共Web服務(wù)集QWS[7](包含2507條Web數(shù)據(jù)信息，取其4個QoS屬性數(shù)據(jù)——Response Time，Latency，Throughput，Successability)，以及隨機產(chǎn)生的493條Web數(shù)據(jù)，Trustworthiness(Web服務(wù)起源可信度)取自文獻[4]的實驗數(shù)據(jù)。

所有算法都用Java實現(xiàn)，硬件環(huán)境配置為Intel(R) Core(TM) i5-3470 CPU，3.20 GHz，4 GB RAM running Windows 7(32位)。

(1) Skyline服務(wù)Top-k選擇方法的對比分析

對比文獻[2]提出的Skyline選擇方法與本文提出的基于Skyline服務(wù)的Top-k選擇方法，隨機抽取Web服務(wù)，針對不同的k值，計算其服務(wù)選擇的時間耗費，具體的對比如圖2所示。

圖2 不同的k值的服務(wù)選擇時間耗費對比圖

由圖2可知，不管k值如何，隨著候選服務(wù)集的增加，兩種方法時間耗費的差距越來越大，本文提出的基于Skyline服務(wù)的Top-k選擇方法大大減少了服務(wù)選擇的時間耗費，從而能提高服務(wù)選擇的效率。

(2) 基于Skyline服務(wù)的Top-k選擇對服務(wù)組合的影響分析

分兩種情況分析本文提出的基于Skyline服務(wù)的Top-k選擇方法對服務(wù)組合的影響：a)用戶所關(guān)注的QoS屬性均為累和形式的QoS屬性；b)累和形式的QoS屬性相對較多，累積、最小值等其他形式求解的QoS屬性的權(quán)重很小。

對圖3所示的服務(wù)組合流程，以及表1所示的組合閾值和權(quán)重，選取按效用函數(shù)值排序的前Top-k個服務(wù)組合(k=10)。兩種情況下，最終得到的前10個服務(wù)組合如圖4所示。

圖3 服務(wù)組合流程

表1 組合閾值及權(quán)重

圖4 兩種情況下Top-10服務(wù)組合結(jié)果

由圖4可知，在僅考慮累和形式的QoS屬性的情況下，本文提出的基于Skyline服務(wù)的Top-k選擇與文獻[2]的Skyline選擇后的服務(wù)組合結(jié)果相同；而在累和形式的QoS屬性占絕對優(yōu)勢的前提下，本文提出的基于Skyline服務(wù)的Top-k選擇與文獻[2]的Skyline選擇后的服務(wù)組合結(jié)果相差較小，只有最后排行末尾的服務(wù)組合不一致。所以，本文提出的基于Skyline服務(wù)的Top-k選擇算法是可行的、有效的，不會影響服務(wù)組合。

4 結(jié) 語

本文在現(xiàn)有Skyline服務(wù)選擇的研究基礎(chǔ)上，提出了基于Skyline服務(wù)的Top-k選擇方法，具體工作包括：1)從服務(wù)組合出發(fā)，給出了基于Skyline服務(wù)Top-k選擇的理論依據(jù)；2)提出了基于Skyline服務(wù)的Top-k選擇的相關(guān)命題，并證明了這些命題的正確性；3)設(shè)計了基于Skyline服務(wù)的Top-k選擇算法，有效、便捷地計算出被選擇的可能性最大的前Top-k個Skyline服務(wù)；4)通過實驗證明了基于Skyline服務(wù)的Top-k選擇算法能大大縮小服務(wù)選擇的時間，提高服務(wù)選擇的效率，是一種可行的、有效的服務(wù)選擇方法。

[1] http://www.beareyes.com.cn/2/lib/201303/19/20130319126.htm.

[2] 王尚廣,孫其博,張光衛(wèi),等. 基于云模型的不確定性QoS感知的Skyline服務(wù)選擇[J]. 軟件學(xué)報, 2012, 23(6):1397-1412．

[3] Borzsonyi S, Kossmann D, Stocker K. The Skyline operator[C]// Proceeding of the 17thInternational Conference on Data Engineering. Washington, DC, USA. 2001:421-430.

[4] 楊莉. 基于數(shù)據(jù)起源信息的Web服務(wù)選擇研究[D]. 南京:河海大學(xué), 2014．

[5] 吳健,陳亮,鄧水光,等. 基于Skyline的QoS感知的動態(tài)服務(wù)選擇[J]. 計算機學(xué)報,2010, 33(11):2136-2146.

[6] Jang J H, Shin D H, Lee K H Fast quality driven selection of composite Web services[C]//Proceeding of the 4thEuropean Conference on Web Services. Zürich, Switzerland, 2006:87-96.

[7] Eyhab Al-Masri, Qusay H Mahmoud. The QWS dataset[EB/OL].http://www.datatang.com/data/42831.

[8] Ardagna D, Pernici B. Adaptive service composition in flexible processes[J]. IEEE Transactions on Software Engineering,2007, 33(6):369-384.

[9] 劉麗, 方金云, 梁對.基于多目標(biāo)遺傳算法和理想點法的Top-k服務(wù)組合研究[J]. 高技術(shù)通訊，2014, 24(2):131-137.

[10] 曹步青, 李兵, 劉建勛.一種服務(wù)質(zhì)量可信的按需服務(wù)組合方法[J]. 西安交通大學(xué)學(xué)報，2013, 47(2):131-138.

[11] 楊汝濤, 張紹謙, 竇萬春.一種基于QoS剪枝的Top-k自動服務(wù)組合方法[J]. 電子學(xué)報，2012, 40(7):1489-1491.

[12] 王意潔, 李小勇, 楊永滔, 等.不確定Skyline查詢技術(shù)研究[J]. 計算機研究與發(fā)展，2012, 49(10):2045-2053.

[13] Chen Liping. Ensuring reliability and QoS optimizing for Web service composition[C]//Tenth International Conference on Computational Intelligence and Security. Kunming, Yunnan, China,2014:510-513.

[14] Chen Liping. Services selection of QoS-based Skyline computation for Web service composition[C]//Eighth international conference on computational intelligence and security. Leshan, Sichuan, China,2012:601-604.

TOP-K SELECTION METHOD BASED ON SKYLINE SERVICE

Yang Li1Zhang Wensheng2Xu Guoyan3

1(Information Center, HoHai University, Nanjing 210098,Jiangsu,China)2(East China Yixing Pumped Storage Corporation, Yixing 214205,Jiangsu,China)3(College of Computer and Information, Hohai University, Nanjing 211100, Jiangsu, China)

A Top-k selection algorithm based on Skyline service is proposed to decrease the size of Skyline services set and increase the efficiency of service selection. Firstly, the theoretical foundation of the proposed algorithm is provided by mathematical reasoning, and then some related propositions are presented;Secondly, with the proposed propositions, the Skyline service Top-k selection algorithm is put forward, which is able to obtain the Top-k Skyline service set which was most likely to be selected ;Finally, the experiment is conducted to prove that the proposed algorithm is useful to decrease service selection time with no impact on service composition.

Skyline service Top-k Service selection

2015-11-20。楊莉，助理工程師，主研領(lǐng)域：Web服務(wù)，數(shù)據(jù)起源。張文生，學(xué)士。許國艷，副教授。

TP3

A

10.3969/j.issn.1000-386x.2016.11.059