基于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选择方法。首先，用数据推理的方式为Skyline服务的Top-k选择提供理论依据，并提出Skyline服务Top-k选择的相关命题；然后，基于这些命题，提出Skyline服务Top-k选择算法，该算法可以得到被选择可能性最大的Top-k Skyline服务集；最后，通过实验证明，该方法能有效降低服务选择的时间，而不影响服务组合的最终结果。

Skyline服务 Top-k 服务选择

0 引 言

伴随着经济的快速发展，服务化成为了产业发展的必然趋势，各种生产活动的成果逐渐开始以服务方式向用户进行交付[1]。进而，互联网上的服务种类越来越丰富，服务数据越来越繁杂，服务选择的优化成为了一个亟需解决的问题。

目前，Skyline服务选择成为了服务选择优化的一大研究热点[2,4,5]。这些研究大多是通过引入Skyline计算，选择出Skyline服务集，去除冗余服务，从而减小候选服务集大小、提高服务选择的效率。但是，这些研究只是去除了被支配的冗余服务，剩下的Skyline服务集仍然是一个非常庞大的服务集，这些服务必定只有少部分才会用于服务组合。所以，对候选服务进行二次筛选，选出能被选择的可能性最大的Skyline服务集，成为Skyline选择方法亟待解决的难题。

为了提高服务选择的效率，缩小Skyline服务集的大小，提出了Skyline服务Top-k选择方法。该方法可快速求解到最优的Top-k Skyline服务，去除冗余的Skyline服务，有效降低服务选择的时间，而不会影响服务组合的结果。

1 相关介绍

1.1 Skyline服务

Skyline 计算(查询)[3]就是从一个数据库中抽取出不被其他任一数据对象所支配的所有数据对象的集合，也称为Pareto (即在不损害他方利益的情况下，使得自身已达最优)。目前，Skyline计算已经被引入到服务领域。

定义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服务选择方法提供了理论依据。

命题1[2]设最优组合服务为S={s1,s2, …,sn} (si是对应组合服务类Si中选择出的服务)，那么对于S中的每一个服务，都属于对应组合服务类的Skyline服务(记为SkySi)，即si∈SkySi。

2 基于Skyline服务的Top-k选择

文献[2]将Skyline计算引入到服务选择中，剔除冗余的候选服务，降低候选服务集的大小，从而提高了服务选择的效率。但是，这只是服务选择的第一步，因为剔除了冗余的候选服务后，得到的Skyline服务集仍然是一个非常庞大的数据集。本节将对Skyline服务集进行筛选，选择出最优的Top-k Skyline服务，达到缩小Skyline服务集大小，而不会影响服务组合的目的。

2.1 理论基础

服务选择最终是为了服务组合，本节从服务组合角度，用数学推理的方式给出了基于Skyline服务的Top-k选择的理论依据。

众所周知，基于QoS全局约束的服务选择的重点是从所有可能的服务组合中选择一个QoS效用函数值最大且满足全局QoS约束的组合。例如，假设最终的最优服务组合为S={s1,s2,…,sn}，那么，它必须满足两个条件：

a) 所有服务类的QoS效用函数值U(S)最大；

b) QoS属性聚合值qj(S)≤Cj，其中qj(S)为S的第j个QoS属性聚合值，Cj为相对应的约束值。

本文设定服务组合的所有可能组合按QoS效用函数排序，取其Top-k，最大限度的容许了条件b)的成立，所以，关键在于条件a)，即使服务的QoS效用函数值最大。

在顺序模型中，服务组合S={s1,s2,…,sn}，服务类si的质量属性为q(si)={q1, q2,…,qj,…,qm}，则S的QoS效用函数值为:

(1)

均按照正属性来处理，其中Qjmax和Qjmin分别为所有服务类的质量属性qj的最大值和最小值，由于其余三种模式均可转化为顺序模式求解[6,8]，仅考虑顺序模式。

如果所有的服务类在进行服务组合之前已经进行了归一化处理(处理后均为正属性)，即每个服务类的每个QoS属性的最大值和最小值均分别为1和0，另外，由于服务组合的QoS属性的计算方式主要分为3种：累和，累积，最小值。所以，分三种情况分析。

(1) 累和：如响应时间，价格，信誉度等

此时，服务组合S的QoS属性的最小值肯定为0，所以效用函数变换为:

又由于对于有系数的QoS属性，例如信誉度，有1/n，因为分子、分母都有，消去。所以，如果考虑的QoS属性均为累和形式，则服务组合的效用函数变换为:

(2)

即，服务组合的效用函数与每个服务类所选择的服务的效用函数相关。所以，可以依据每个服务类中候选服务的效用函数值进行选择服务，而具体的依据或者具体的效用函数值范围的界定，由下节命题给出。

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

可见，看不出与每个服务类所选择的服务的效用函数的关系，但可以肯定，如果此种计算方式的QoS属性个数所占比重较少，且权重不大，其数值相对较小。

(3) 最小值：如吞吐量

也看不出其与每个服务类选择出的服务的效用函数的关系，但是在权重非常小的情况下，其值相对也较小。

综上，如果一个服务组合，有a个属于累和类型的QoS属性(令其属性标签为1至a)，有b个属于累积类型的QoS属性(令其属性标签为a+1至a+b)，有c个属于最小值类型的QoS属性(令其属性标签为a+b+1至a+b+c)，那么服务组合的效用函数可变换为

其中，U(i)表示第i个服务、第1至a个QoS属性的效用函数值。可以看出，如果累积和最小值方式的QoS属性相对比较少(甚至没有)，且其权重也不占主要地位，累和形式的结果就成了最终服务组合的效用函数值最主要的部分。在这种情况下，可以通过候选服务的效用函数值来界定被选择用来进行服务组合的可能性，达到降低Skyline服务集大小、提高服务选择效率的目的。这种方法的误差为:

2.2 相关命题

由上节可知，候选服务的效用函数值与服务组合是存在一定的函数关系的，对服务组合的某一个服务类而言，可以依据候选服务的效用函数值来界定一个范围，该范围内的Skyline服务是最有可能被选择后用于服务组合的。本节将给出基于Skyline服务进行Top-k选择的相关命题及其证明。

命题2如果对服务组合按照效用函数值进行Top-k排序，那么对于任意的服务组合S={s1,s2,…,sn} (si是对应服务类Si中选择出的服务)，si一定属于其对应的Skyline服务集的Top-k(按效用函数排序)。

证明：反证法

假设对于服务组合S={s1,s2,…,sn}，S属于Top-k，si是对应服务类Si中选择出的服务，∃sim∈SkySi(m>k)，sim表示服务类中排名第m的服务。

由于按照QoS效用函数(累和形式的QoS属性效用函数值)排序的，所以对于SkySi服务类，其效用函数排序为si1>si2>…>sik>sim。

又由于在顺序模型中，服务组合的QoS效用函数与各个服务类效用函数值的关系如式(2)所示，所以，有k个服务组合S1={s1,…,si1,…,sn}、S2={s1,…,si2,…,sn}、… 、Sk={s1,…,sik,…,sn}，它们的QoS效用函数一定大于服务S，这与条件“S属于Top-k”相矛盾，所以，假设不成立，命题得证。

命题3对于任一服务类S，如果其中的一个服务s1支配另一个服务s2，那么服务s1的QoS效用函数一定优于服务s2的效用函数。

证明：设服务s1={x1, x2, …, xk}，服务s2={x1,x2, …,xk}。

由于s1

又由于QoS效用函数是各个质量属性的聚合值，聚合值随着各个属性值的越大也越大，所以QoS效用函数也是单调函数，由此可知s1的效用函数一定优于s2的效用函数。得证。

2.3 Skyline服务的Top-k选择算法

根据上一节的命题，本节提出了基于Skyline服务Top-k选择算法，算法流程如图1所示。

图1 基于Skyline服务的Top-k选择算法流程图

该算法是一个并行算法，一边对候选服务集进行Skyline计算，一边根据效用函数进行排序，最终得到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的个数，m为候选服务的指标

for(m=0;m

{ mark=false;

if(i==0)

//topk中无服务，直接将服务加入topk列表中

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

//计算服务s.get(m)的效用函数值

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

i++;

}

else

{ //根据命题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)的效用函数值

//根据命题3，支配服务的效用函数大于被支配服务，

//只需与被支配服务后的效用函数大于它的服务比较

if(mark==false)

//第一次找到topk中被支配的服务，插入适当的位置

{ 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)已

//经插入到topk适当的位置了，只需删除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)的效用函数值

if(i==k) //根据命题2，最终的选择出的服务一定属于

//Top-k，所以，topk列表只需要k个最终不被支配的服务。

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

//效用函数比topk列表中最小效用函数的服务大，删除效用函数最小的服务

{ topk.remove(0);

//去除QoS值最小的

i--;

//还原i的值

}

else continue;

}

int t;

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

//将候选服务s.get(m)插入topk列表合适的位置，实现排序的要求

{ 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数据信息，取其4个QoS属性数据——Response Time，Latency，Throughput，Successability)，以及随机产生的493条Web数据，Trustworthiness(Web服务起源可信度)取自文献[4]的实验数据。

所有算法都用Java实现，硬件环境配置为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所示的组合阈值和权重，选取按效用函数值排序的前Top-k个服务组合(k=10)。两种情况下，最终得到的前10个服务组合如图4所示。

图3 服务组合流程

表1 组合阈值及权重

图4 两种情况下Top-10服务组合结果

由图4可知，在仅考虑累和形式的QoS属性的情况下，本文提出的基于Skyline服务的Top-k选择与文献[2]的Skyline选择后的服务组合结果相同；而在累和形式的QoS属性占绝对优势的前提下，本文提出的基于Skyline服务的Top-k选择与文献[2]的Skyline选择后的服务组合结果相差较小，只有最后排行末尾的服务组合不一致。所以，本文提出的基于Skyline服务的Top-k选择算法是可行的、有效的，不会影响服务组合。

4 结 语

本文在现有Skyline服务选择的研究基础上，提出了基于Skyline服务的Top-k选择方法，具体工作包括：1)从服务组合出发，给出了基于Skyline服务Top-k选择的理论依据；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] 王尚广,孙其博,张光卫,等. 基于云模型的不确定性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] 杨莉. 基于数据起源信息的Web服务选择研究[D]. 南京:河海大学, 2014．

[5] 吴健,陈亮,邓水光,等. 基于Skyline的QoS感知的动态服务选择[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] 曹步青, 李兵, 刘建勋.一种服务质量可信的按需服务组合方法[J]. 西安交通大学学报，2013, 47(2):131-138.

[11] 杨汝涛, 张绍谦, 窦万春.一种基于QoS剪枝的Top-k自动服务组合方法[J]. 电子学报，2012, 40(7):1489-1491.

[12] 王意洁, 李小勇, 杨永滔, 等.不确定Skyline查询技术研究[J]. 计算机研究与发展，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服务，数据起源。张文生，学士。许国艳，副教授。

TP3

A

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