QoS约束的代表性Skyline Web服务选择*

黄迎春 ，左甜甜

（1.沈阳理工大学信息科学与工程学院，沈阳 110159；2.东北大学计算机科学与工程学院，沈阳 110169）

0 引言

在新一代军事指挥控制系统中，面向服务的体系结构（SOA，service-Oriented Architecture）应用趋势明显增长，Web service已经成为构建的SOA指控系统的重要技术。Web服务搜索引擎Seekda［1］公开发表的统计信息表明，近年来，Web service在数量上以指数性指标增长。指控用户面对大量功能相似但QoS不同的服务信息，如何按需选择匹配服务成为亟待解决的问题。特别地，当前许多服务匹配、选择算法在按照QoS指标选取服务时，将显著增加服务选择的计算复杂度，所以实现快速的服务选择就变得非常紧迫。

QoS约束的Web服务选择包括两种策略：局部选择策略和全局选择策略，常用的Web服务局部选择方法，主要基于多属性决策理论［2］，包含服务需求定义、服务QoS参数预处理、服务QoS指标赋权以及候选服务排序等服务选择过程。全局选择策略即组合服务选择策略，常用的方法是0-1整数规划、基于全局QoS约束分解的分布式组合服务选择方法，分支界限法、启发式算法（如遗传算法、蚁群算法和粒子群优化算法等）。

由于传统的基于全局选择策略和局部选择策略均以全部服务库作为候选服务集合，随着候选服务集服务数量的增长，上述策略的服务选择时间显著增长。为了去除冗余服务，吴键等［3］引入数据库查询中Skyline方法，利用Skyline中的支配关系，缩小了候选服务空间。王尚广等人［4］首先通过云模型计算QoS的不确定性，然后采用整数规划在Skyline服务中进行服务选择。吴建等［5］提出一种利用MapReduce思想进行并行Skyline服务选择的方法，并探讨了一种称为纸带模型的动态Skyline服务更新方法。

当某一服务类的Skyline服务数目太大，从而不能有效处理时，提出在多个QoS属性之间进行权衡，并选择一系列具有代表性的Skyline服务作为服务选择模型的输入服务集，使得这些服务最可能成为优化选择中的服务，满足用户的QoS约束并使得效用最大化。

1 Skyline服务选择

1.1 Skyline服务

给定一系列N维空间的点，Skyline查询选择那些没有被其他任何点支配的点。若某点Pi在所有N个维度均不劣于另外某个点Pj，而且至少在某个维度上优于Pj，则称点Pi支配点Pj。借鉴Skyline的思想，可以基于服务QoS属性值定义服务之间的优势关系，并将其用于某一类服务中被其他服务支配的服务，进行服务选择时可以忽略这些被支配的服务，从而降低服务选择时需要考虑的服务数量。

定义1服务支配：设某个服务候选集存在某种服务类别S，S中的两个服务x，y∈S，每个服务包含一组QoS属性。x支配y，记为，当且仅当x的所有QoS值不劣于y，且x至少有一个QoS属性值严格优于y，即

定义2 Skyline服务集：候选服务集的某类服务子集，记作SLs，其集合元素是服务类别S中不被其余服务支配的全部服务集合，即。SLs中的服务被称作服务类别S中的Skyline服务。

图1 Skyline服务示例图

图1为一个服务类别中的Skyline服务示例图。其中，任何一个服务由响应时间和费用两个QoS属性组成［11］。所以，可以用平面上的一个点表示一个服务，点的坐标对应服务的QoS属性的值。从图1中可以看出：，原因是不存在其他任何服务支配服务a，即不存在有其他服务的服务费用高于a，且响应时间低于a，所以a属于Skyline服务集；同样可以得出b、c、d以及e也是Skyline服务。反之，服务f不是一个Skyline服务，因为f被服务b、c和d支配。

1.2 Skyline服务集的选择命题

文献［4］给出并证明了Skyline服务集的选择命题1，即最优服务必须来自Skyline服务集。

命题2基于Skyline服务集的服务选择能够提高服务选择的效率。

证明：因为用户需求对QoS属性的约束条件与确定Skyline服务不相关，因此，不需要在进行优化选择时实时在线实时进行Skyline服务选择。所以可以在进行服务匹配、选择、组合时不再考虑那些不在Skyline中的服务，从而提高优化选择的效率。

基于上述分析，服务代理可以为在服务注册中心维护一个Skyline服务列表。该列表在每一次有服务加入、离开、或者已注册服务QoS信息有变化时进行更新。当服务代理收到一个服务请求时，就直接向服务请求者返回匹配的服务类别中的Skyline服务。

2 代表性Skyline服务选择

在现实环境中，Skyline集合中对象的数量会随着维度的增加呈指数增长。因此，在高维空间，尽管Skyline方法已经裁剪了大部分的对象，但是仍然会向用户呈现大量的Skyline对象，因此，使用Skyline方法只是第一步，本节对Skyline服务集进行筛选，得到最具代表性的Skyline服务达到缩小Skyline服务集的目的。

定义3代表性服务：代表性服务是在服务集合中能够反应同一类事物共同特征，并能够代替该服务集合中服务的部分服务，是整个服务集服务主成分的体现。

同理，代表性Skyline服务即为在Skyline集合中的部分体现服务主成分的服务。

2.1 服务选择中的效用函数

QoS约束的局部服务选择或全局服务选择均为在满足QoS约束条件下选择使QoS效用函数值最大的服务。服务选择中的效用函数可采用两个步骤计算：首先规范化服务QoS属性值，即将不同量纲与值域的QoS属性进行属性值尺度上的规范并统一。其次基于不同指控用户对QoS属性的偏好进行量化并赋权，通过加权计算服务效用函数值［6-8］。QoS约束的局部服务可采用多属性决策理论的加权和法计算服务效用函数值。然而对于QoS约束的全局服务选择，可用抽象组合服务流程对应的一个具体组合服务的第k个QoS属性的最大、最小聚合值计算过程可以形式化描述为

式（1）、式（2）中，

而组合服务CS的效用函数为

式（7）中，ωk∈R+表示用户对组合服务 QoS 属性 q′k的重视程度（即权重）。

2）整体效用U′（CS）最大化。

2.2 顺序结构组合服务选择模型

完全顺序结构的服务组合问题是一个0-1整数规划问题，可以采用文献［6，9-10］提到的方法进行求解。在基于0-1整数规划的QoS约束服务选择问题时，服务sji是否被选择可表示为0，1二元决策变量xji，若xji=1，则表示在服务集合中包含候选服务sji，若xji=0，则表示在服务集合中不包含候选服务sji。根据以上分析，基于0-1整数规划的QoS约束服务选择问题可被转换成为组合服务整体效用值的最大值求解问题，0-1整数规划的目标函数可定义为

为保证被选取的指控服务聚合值满足全局QoS约束条件，必须将其他的约束条件引入整数规划模型。具体包括：

1）将以下约束加入模型

式（9）表示聚合的QoS属性采用累加方式，如响应时间、价格、信誉度等QoS属性。

2）若QoS属性之间采用乘法运算，例如：可用性、可靠性、可能性等指标，约束条件可表示为

为计算方便，也可对式（10）取自然对数，将乘法运算转换成加法运算，如式（11）所示。

3）将如下约束条件加入模型

式（12）表示基于最小化函数的QoS属性约束，如容量等。

2.3 基于代表性Skyline服务集的选择分析

命题3如果某个服务si属于服务类S，并且服务si支配了另一个服务sj，则服务si的效用函数值必然优于服务sj的效用函数值。

命题4通过优化Skyline服务的匹配过程，QoS约缩短了服务匹配选择时间。

证明：通过QoS聚类操作后，代表性Skyline服务选出了效用函数值最优的Skyline服务，进而实现了指控服务的最优匹配，所以通过提高服务匹配成功率，缩小了服务搜索范围，缩短了服务选择时间。

3 代表性Skyline选择算法

代表性Skyline服务选择算法的基本原理是：首先采取层次聚类操作，将Skyline服务SL聚类为k个簇，k≤|SL|，并且k为偶数；其次选取服务效用函数值最大的服务作为代表性Skyline服务。为实现代表性Skyline服务选择算法，采用树形结构表示代表性Skyline服务的层次关系数据结构，如图2（d）所示。图2（d）中，树结点对应SL中的一个Skyline服务，除叶子外，其余结点表示在相应簇中选择的代表性服务。

具体的服务搜索策略如下：指控服务选择服务器首先接收用户服务请求，从图2（d）所示的服务树的根结点开始搜索，由于根结点代表服务集中的顶层服务（图2（d）中的顶层服务为候选服务s3），因此，首先搜索顶层服务。如果位于该层次的服务不能满足用户的QoS约束的属性值，则继续向树的下层进行搜索，不断重复该过程，进行从根向叶子的路径搜索，搜索过程终止于树的分支结点和叶子结点。如果搜索到叶子结点，说明问题无解，否则，如果问题有解，根据命题1，搜索过程将终止于分支结点，因此，必然会通过遍历二叉树求解出最佳的服务选择结果。

对于组合服务来说，候选服务则作为组合方案选择模型的输入进行求解。如果使用给定的代表服务没有得到满足用户的QoS约束条件，则继续处理下一个级别的代表服务，不断重复该过程，直到找到一个解或者已经到达树的最底层，即已经尝试了所有的Skyline服务。如果问题有解，根据命题1，则遍历完该二叉树一定会找到优化选择结果。

图2 利用层次聚类确定代表性服务

建立代表服务树的过程本文利用k-means聚类算法完成。利用k-means算法对服务类S的Skyline服务SL进行聚类，将SL划分为k个簇SL={sl1，sl2，…，slk}，其中，使得每个簇之间的距离平方和最小，即

式（13）中，μi表示簇i中服务的质心，也称为均值。在多维QoS属性情况下，服务质心的坐标定义为各QoS维度的平均值。

代表性Skyline服务选择算法主要分为算法1：基于k-means的Skyline服务聚类算法（如下页图3所示）以及算法2：生成代表服务树算法（如图4所示）。

图3 基于k-means的Skyline服务聚类算法

图4 生成代表性服务树

以算法1的k-means算法为基础，进一步设计算法2，用来生成代表性Skyline服务树。算法2的基本原理如下：步骤1，计算SL中效用函数值最大的结点s，然后再以s作为的根结点子簇上进行搜索；步骤2，通过k-means算法输入SL，生成两个子簇 CLs［1］和 CLs［2］的聚类集合，分别计算 CLs［1］和CLs［2］子簇中效用函数值最大的两个结点，并将它们分别作为根s的左右孩子结点构造一颗新的二叉树；步骤3，不断对每个子簇重复执行步骤2，使二叉树不断生长，直至最终子簇中的服务数量小于2为止，至此，通过输入Skyline服务集合SL，最终输出以s为根结点的代表性服务二叉树。

4 试验分析

基于开放的QWS数据集进行实验以验证算法的有效性。QWS数据集包含了2 442个Web服务及其参数，这些服务分别来自于服务门户网站、UDDI服务注册中心、互联网搜索引擎等渠道，由Eyhab Al-Masri博士采用 WSCE（Web Service Crawler Engine）工具构建。QWS数据集中包括了服务吞吐率、服务响应时间等8个QoS属性参数值。实验环境基于Windows 7操作系统，CPU来自Inter公司，主频3.3 GHz，内存为4 GB；使用Java、R语言编写了相关软件。为了验证算法性能，设计了如下两组实验。

实验1：比较3种QoS约束下Web服务选择算法执行时间。

1）多属性决策服务选择方法：不采用Skyline服务，仅使用局部选择算法。

2）Skyline服务选择方法：在多属性决策方法基础上，采用Skyline服务。

3）代表性Skyline服务选择方法：由本文算法1和算法2构造的基于代表性Skyline服务选择方法。

对于3种服务选择方法，当服务数量在100～1 000之间取值时，固定QoS维度及其参数值，测试服务选择的执行时间，实验结果如图5所示。固定候选服务数量，当QoS属性维度及其参数值在2～8之间变化时，测试服务选择的执行时间，实验结果如图6所示。

图5 对比不同候选服务数量上的执行时间

图6 对比不同QoS属性维度上的执行时间

从图5和图6中可以看出：1）多属性决策方法由于搜索空间较大，导致对QoS参数值的评价数据量较大，因此，排序时间较长，所以多属性决策方法的服务选择执行时间最长。2）Skyline方法通过筛选方法过滤掉不必要的候选服务，缩小了服务选择的目标集合，因此，在多属性决策方法基础上，缩短了服务选择的执行时间。然而，有些情况下其候选服务集依旧较大时，其性能处于3种方法的中间水平。3）在Skyline方法的基础上，由于引入了代表性Skyline算法，当服务数量和QoS属性维度增加时，依然能够取得3种方法中最短的服务选择实行时间。

实验2：比较整数线性规划和代表性Skyline方法的服务选择执行时间和QoS约束的服务效用值。

实验参数包括：1）输入由10个服务组成的Web服务组合组件；2）每个组件的服务数量为100个～1 000个。

实验中的整数线性规划求解基于Skyline服务选择方法，采用文献［4］给出的启发式算法。代表性Skyline方法同样采用求解整数线性规划方法，不同的是在服务选择组件中选择代表性Skyline服务。实验2的测试结果如图7和图8所示。

图7 对比不同候选服务数量上服务组合执行时间

从图7中可以看出：当候选服务数量在100～1 000范围内变化时，代表性Skyline服务选择算法明显优于仅结合Skyline服务的整数规划算法，其服务选择执行之间至少缩短了25%，且当服务数量大于800时，二者的服务选择执行时间差距显著增加。

图8 对比不同候选服务数量服务组合效用值

从图8中也可以得出代表性Skyline服务选择算法在效用值指标上也明显优于仅结合Skyline服务的整数规划算法，其服务选择平均效用值约提升10%。

5 结论

在存在QoS约束的服务选择中，不仅需关注服务组合的功能，还需考虑服务选择的性能优选服务。通过在传统的多属性决策变量的方法基础上，提出了代表性Skyline服务选择算法，该方法基于k-means的Skyline服务聚类算法，通过生成具有多维QoS属性的代表性Skyline服务二叉树，在缩小服务候选集合的基础上，通过树形结构查找高效的特点提升了服务选择性能指标。通过在QWS数据集应用代表性Skyline服务选择算法进行了数据实验，结果表明所提出的方法在服务选择执行时间和服务效用值两个指标上均优于传统算法。对于QoS约束的Web服务选择的后续工作，需进一步对组合服务Skyline计算以及对Web服务的QoS预测方面进行研究。