楊 莉 張文生 許國艷

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

?

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

楊 莉1張文生2許國艷3

1(河海大學(xué)信息中心 江蘇 南京 210098)2(華東宜興抽水蓄能有限公司 江蘇 宜興 214205)3(河海大學(xué)計(jì)算機(jī)與信息學(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ù)集；最后，通過實(shí)驗(yàn)證明，該方法能有效降低服務(wù)選擇的時(shí)間，而不影響服務(wù)組合的最終結(jié)果。

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

0 引 言

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

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

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

1 相關(guān)介紹

1.1 Skyline服務(wù)

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

定義1服務(wù)支配[2]：設(shè)存在一個(gè)服務(wù)類S={s1,s2,…,sn}, s1和s2為其中的兩個(gè)候選服務(wù)，并且每個(gè)服務(wù)都有k個(gè)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ù)選擇

文獻(xiàn)[2]將Skyline計(jì)算引入到服務(wù)選擇中，通過剔除候選服務(wù)中的冗余服務(wù)，得到Skyline服務(wù)集，從而縮小候選服務(wù)集的大小、提高服務(wù)選擇的效率，并求解出基于QoS全局約束的服務(wù)選擇的解。同時(shí)，文獻(xiàn)[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中的每一個(gè)服務(wù)，都屬于對應(yīng)組合服務(wù)類的Skyline服務(wù)(記為SkySi)，即si∈SkySi。

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

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

2.1 理論基礎(chǔ)

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

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

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

b) QoS屬性聚合值qj(S)≤Cj，其中qj(S)為S的第j個(gè)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ù)類在進(jìn)行服務(wù)組合之前已經(jīng)進(jìn)行了歸一化處理(處理后均為正屬性)，即每個(gè)服務(wù)類的每個(gè)QoS屬性的最大值和最小值均分別為1和0，另外，由于服務(wù)組合的QoS屬性的計(jì)算方式主要分為3種：累和，累積，最小值。所以，分三種情況分析。

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

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

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

(2)

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

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

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

(3) 最小值：如吞吐量

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

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

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

2.2 相關(guān)命題

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

命題2如果對服務(wù)組合按照效用函數(shù)值進(jìn)行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ù)排序?yàn)閟i1>si2>…>sik>sim。

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

命題3對于任一服務(wù)類S，如果其中的一個(gè)服務(wù)s1支配另一個(gè)服務(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ù)是各個(gè)質(zhì)量屬性的聚合值，聚合值隨著各個(gè)屬性值的越大也越大，所以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選擇算法流程圖

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

輸入：服務(wù)類s

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

list topk_sky(s)

{ list topk=new ArrayList();

Boolean mark;

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

int i=0,j,m;

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

for(m=0;m

{ mark=false;

if(i==0)

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

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

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

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

i++;

}

else

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

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

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

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

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

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

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

//計(jì)算服務(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)

//互不支配

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

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

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

//Top-k，所以，topk列表只需要k個(gè)最終不被支配的服務(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列表合適的位置，實(shí)現(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 實(shí)驗(yàn)與分析

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

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

所有算法都用Java實(shí)現(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選擇方法的對比分析

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

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

由圖2可知，不管k值如何，隨著候選服務(wù)集的增加，兩種方法時(shí)間耗費(fèi)的差距越來越大，本文提出的基于Skyline服務(wù)的Top-k選擇方法大大減少了服務(wù)選擇的時(shí)間耗費(fèi)，從而能提高服務(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個(gè)服務(wù)組合(k=10)。兩種情況下，最終得到的前10個(gè)服務(wù)組合如圖4所示。

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

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

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

由圖4可知，在僅考慮累和形式的QoS屬性的情況下，本文提出的基于Skyline服務(wù)的Top-k選擇與文獻(xiàn)[2]的Skyline選擇后的服務(wù)組合結(jié)果相同；而在累和形式的QoS屬性占絕對優(yōu)勢的前提下，本文提出的基于Skyline服務(wù)的Top-k選擇與文獻(xiàn)[2]的Skyline選擇后的服務(wù)組合結(jié)果相差較小，只有最后排行末尾的服務(wù)組合不一致。所以，本文提出的基于Skyline服務(wù)的Top-k選擇算法是可行的、有效的，不會(huì)影響服務(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è)計(jì)了基于Skyline服務(wù)的Top-k選擇算法，有效、便捷地計(jì)算出被選擇的可能性最大的前Top-k個(gè)Skyline服務(wù)；4)通過實(shí)驗(yàn)證明了基于Skyline服務(wù)的Top-k選擇算法能大大縮小服務(wù)選擇的時(shí)間，提高服務(wù)選擇的效率，是一種可行的、有效的服務(wù)選擇方法。

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

[2] 王尚廣,孫其博,張光衛(wèi),等. 基于云模型的不確定性QoS感知的Skyline服務(wù)選擇[J]. 軟件學(xué)報(bào), 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感知的動(dòng)態(tài)服務(wù)選擇[J]. 計(jì)算機(jī)學(xué)報(bào),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)遺傳算法和理想點(diǎn)法的Top-k服務(wù)組合研究[J]. 高技術(shù)通訊，2014, 24(2):131-137.

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

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

[12] 王意潔, 李小勇, 楊永滔, 等.不確定Skyline查詢技術(shù)研究[J]. 計(jì)算機(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