基于Skyline服務的Top-k選擇方法

楊 莉 張文生 許國艷

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

?

基于Skyline服務的Top-k選擇方法

楊 莉1張文生2許國艷3

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

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

Skyline服務 Top-k 服務選擇

0 引 言

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

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

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

1 相關介紹

1.1 Skyline服務

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

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

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

1.2 基于云模型的Skyline服務選擇

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

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

2 基于Skyline服務的Top-k選擇

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

2.1 理論基礎

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

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

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

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

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

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

(1)

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

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

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

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

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

(2)

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

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

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

(3) 最小值：如吞吐量

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

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

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

2.2 相關命題

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

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

證明：反證法

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

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

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

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

證明：設服務s1={x1, x2, …, xk}，服務s2={x1,x2, …,xk}。

由于s1

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

2.3 Skyline服務的Top-k選擇算法

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

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

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

輸入：服務類s

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

list topk_sky(s)

{ list topk=new ArrayList();

Boolean mark;

//標記是否在topk中找到支配點或被支配點

int i=0,j,m;

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

for(m=0;m

{ mark=false;

if(i==0)

//topk中無服務，直接將服務加入topk列表中

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

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

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

i++;

}

else

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

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

//最終不被支配的服務放入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;

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

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

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

if(mark==false)

//第一次找到topk中被支配的服務，插入適當?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); //支配服務s.get(m)已

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

i--;

}

mark=true;

}

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

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

{ mark=true;

break;

}

else continue;

}

}

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

//互不支配

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

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

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

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

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

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

{ topk.remove(0);

//去除QoS值最小的

i--;

//還原i的值

}

else continue;

}

int t;

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

//將候選服務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服務Top-k選擇方法的對比分析以及其對服務組合的影響，進行了兩個實驗。

所有實驗均基于公共Web服務集QWS[7](包含2507條Web數(shù)據(jù)信息，取其4個QoS屬性數(shù)據(jù)——Response Time，Latency，Throughput，Successability)，以及隨機產(chǎn)生的493條Web數(shù)據(jù)，Trustworthiness(Web服務起源可信度)取自文獻[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服務Top-k選擇方法的對比分析

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

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

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

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

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

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

圖3 服務組合流程

表1 組合閾值及權重

圖4 兩種情況下Top-10服務組合結果

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

4 結 語

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

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

[2] 王尚廣,孫其博,張光衛(wèi),等. 基于云模型的不確定性QoS感知的Skyline服務選擇[J]. 軟件學報, 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服務選擇研究[D]. 南京:河海大學, 2014．

[5] 吳健,陳亮,鄧水光,等. 基于Skyline的QoS感知的動態(tài)服務選擇[J]. 計算機學報,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] 劉麗, 方金云, 梁對.基于多目標遺傳算法和理想點法的Top-k服務組合研究[J]. 高技術通訊，2014, 24(2):131-137.

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

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

[12] 王意潔, 李小勇, 楊永滔, 等.不確定Skyline查詢技術研究[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。楊莉，助理工程師，主研領域：Web服務，數(shù)據(jù)起源。張文生，學士。許國艷，副教授。

TP3

A

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