Web服务选择动态Qos情况下的k-支配skyline改进∗

何 诚 欧阳中辉 司维超

（海军航空工程学院 烟台 264001）

1 引言

Web服务技术［1］是一种分布式计算模型，能使得不同机器上运行的不同应用跨越内部语言、平台和协议的障碍，自由地集成或交换数据。这就为各个不同企业间的Web服务搭建了一个通用机制，有效推进了电子商务的发展。伴随着人们需求的提高与计算机技术的飞速发展，大量的Web服务被发布到Internet中供用户使用，但因为服务提供者的不同，往往这些Web服务中有许多都是功能相同，但服务质量Qos有差别的。针对这些功能相同、Qos有差别的的服务，如何利用各Web服务的Qos属性来进行服务选取成为了学术界关注的热点。

文献［2］提出了一种基于模糊层次分析法的多维Qos局部最优服务选择模型，该模型将Qos的真实度属性作为Qos属性向量的分量之一，建立了包含客观属性和主观评价的一种双重质量属性模糊层次结构，从各方面综合考察了客观和主观的Qos属性对于服务选择的影响，然而这种选择模型并没有考虑动态Qos属性值的波动问题。文献［3～4］提出了一种基于上下文感知的服务选取方法，该方法采用Web本体描述语言/资源描述框架模型，将上下文转化为服务类别和用户领域相关的约束值。以上研究方法在很大程度上提高了服务选择的准确性和可靠性，但是没有考虑到Web服务动态Qos属性值的波动性。

随着时间的变化，Web服务在运行过程中Qos属性值会实时波动，如反应时间、可靠性、反应成功率等属性在实时的Web服务中并不是固定不变的，这些波动的Qos属性值会影响到Web服务的选择，因此根据固定的Qos属性值进行服务选取的准确性还有待改进。文献［5］建立了区间型Qos模型，引入区间数和相似度概念，提出了一种基于动态Qos的Web服务选取方法；文献［6］为了Qos信息能实时反映出实际服务质量，明确了Qos动态更新概念利用了完整有效的更新数据源，提出了一种基于实时定期修正的Qos动态更新策略与算法。

本文通过动态Qos属性的统计分布，计算Web服务成为skyline的概率，利用概率建立索引，优化k-支配skyline算法。最后实验验证改进后的Prob⁃ability index based算法的高效性。

2 Web服务的动态Qos属性

2.1 Qos属性的概率密度函数

Web服务的Qos属性有许多种，在AL-MASRI E等人通过统计互联网上真实的Web服务Qos属性就有 13 种［7～9］，这些 Qos属性从不同的方面反映了Web服务的服务质量。然而在现实的网络环境中，由于各种不确定因素的影响，Web服务的Qos属性具有波动性，呈现了一种动态现象。在此情况下，本文研究时选取了Web服务的四种Qos属性，并且通过周期采集Qos属性，估计Web服务的Qos属性分布。将Web服务的四种Qos属性定义为一个四维向量Qos=（T，E，A，R），各个分量的具体含义如下。

1）响应时间T：从用户发送服务请求至获取Web服务所花费的时间。显然，响应时间会随着网络运行状况的不同而动态变化。

2）信誉度E：Web服务的可信程度。Web服务的信誉度主要由使用过该Web服务的用户评价所决定。由于用户的个人偏好差异和其他Qos属性的波动，不同用户或在不同时间使用同一Web服务可能会让用户对该Web服务有不同的评价。

3）可用性A：Web服务被正常使用的概率。随着网络环境的变化，Web服务被正常使用的情况也是动态变化的。

4）可靠性R：Web服务正确响应用户请求的概率。网络环境的变化同样影响着服务的可靠性，较差的网络环境会使服务信息在传输过程中丢失或失效的概率变大。

在Web服务对外提供服务的过程中，通过周期T来采样Qos属性会得到如表1所示的采样数据，在自然情况下Web服务的Qos属性服从高斯分布，采样数据通过参数估计得到该Web服务各Qos属性值的概率密度函数 fWeb(t，e，a，r)。

表1 采样数据表

2.2 Web服务成为skyline概率计算

为了筛选功能相同，但服务质量Qos不同的Web服务。文献［10～13］引用了skyline算法对这一类Web服务选择进行筛选。有些Web服务在所有的Qos属性上都优于或等于某些Web服务，因此这些在所有Qos属性上都差的Web服务就没有参与选择的价值，这些Web服务不可能是最优选择，这就引入了skyline算法的支配概念。

定义1 Web服务Wi与Web服务Wj的服务质量 Qos属性分别为 Qosi=（ai1，ai2，…，ain）和 Qosj=（aj1，aj2，…，ajn），如果对于 ∀ aik∈R，1≤k≤n ，都有aik优于或等于ajk，且至少在某一维上aik优于ajk，则称Web 服务 Wi支配 Web 服务 Wj，记为 Wi→Wj；否则称Web服务 Wi不支配Web服务Wj，记为 Wi/→Wj。

定义2 对于任意的Web服务Wi，经由skyline算法计算返回的节点集B满足B=｛Wi|Wi∈N+，∀Wj∈N+，Wj≠Wi，Wj/→Wi｝，称集合B为skyline节点集，记为SK。

通过skyline算法计算得到功能相同，Qos属性不同的Web服务集即SK。筛选掉被支配的Web服务后，减小了输入的规模，提高了Web服务选择效率。

本文取响应时间T和信誉度E的2维Qos属性作为研究的对象，得出概率的计算方法后将方法引申到多维中。为了定义属性值取小为优，对于信誉度E在计算过程中取倒数1/E，信誉度E越大倒数1/E越小。

对于Web服务，在Qos属性响应时间T中，响应时间T理论上最小值收敛于0，最大值为+∞，因而Web服务的概率分布 fWeb(t，1/e)的定义域为（0，+∞）。

设有 Web 服务W1和 Web服务 W2，W1和W2的概率分布分别为 fWeb1(t1，e1)和 fWeb2(t2，e2)。Web服务 W1的 Qos属性 t，e在定义域内任意取值 t1，e1时，当Web服务W2的Qos属性在取值域｛（t，e）|0 ≤ t≤t1，0 ≤ 1/e ≤ 1/e1｝中（即图1所示阴影面积S2→1），Web服务W1被W2支配。

则在 t1，1/e1时，W1被W2支配的概率

图1 支配区域图

由Web服务W1在t1，1/e1时被W2支配的概率可以得到W1被W2支配的概率期望：

同理可得

将Web服务的Qos属性引申到n维后，可以得到Web服务Wi被Wj支 配的期望概率

用Web服务Wi被Wj支配的期望概率表示Wi被Wj支配的概率，则Web服务i属于SK的概率可表示为

3 概率索引优化k-支配skyline算法

随着Internet上发布的Web服务数量急剧增加和Web服务的Qos服务质量增多，数据点集中属于skyline点集的数据点增多并且每一个数据点支配其他数据点的概率会降低，这也就意味着经过sky⁃line操作选出来的skyline点集依然很大，这对于Web服务选择来说是十分不友好的。为了解决skyline点集过大的问题，Chee-Yong Chan和H.V.Jagadish等人提出了在高维空间中寻找k-支配sky⁃line点集的方法［11］，通过所提出的k-支配的概念，从skyline点集中继续筛选k-支配点集，随着k的缩小，这一点集也会越来越小，那么合适的Web服务数据数量可以通过选取k来控制。

对于一个 n 维空间 S=｛s1，s2…sn｝，当且仅当每一个pi∈P都是S上的d维数据时，一个由点pi组成的集合P=｛p1，p2…pn｝被称为n维空间S上的数据集和。

定义 3.1 k-支配当且仅当∃S′⊆S，|S′|=k，∀sr∈S′，pi.sr≥pj.sr，并且∃st∈S′，pi.st＞pj.st时，称 pi是 k-支配pj。

定义3.2 k-支配skyline集如果一个数据点pi不被数据集合中任意其他数据点pj所k-支配，则数据点pi是该数据集合中k-支配skyline集的数据点。我们用DSP（k，P，S）表示空间S中的数据集合的k-支配skyline集。

定义3.3 如果数据点集D中存在一个不属于k-支配skyline集的数据点pi，那么可以得到一下两个结论。

1）在数据点集的skyline集中必然存在一个skyline点k-支配数据点pi；

2）数据点pi可能不被任何k-支配skyline点支配。

在文献［11］中提出了利用定义3.3进行全表扫描的One-Scan算法。在数据点集R中的数据点是通过全表扫描、逐个地比较，慢慢趋近最终结果的。如果被支配的数据点pi被过早拿来比较，极有可能因为支配pi的数据点pj还未参与算法，而被“错误”地放进点集R中，这会引起其他的skyline点与非skyline点与这一数据点pi进行比较，直到支配pi的数据点pj参与算法，数据点pi才会被移除，而中间过程已经造成了许多多余的比较运算。

在计算skyline集时可以利用数据点各个维度的大小顺序建立索引，而在计算k-支配skyline集中，由于图2所示数据点间的非传递关系［11］，数据点在某一维所单独占有的优势在算法中被弱化，至少在k维占有优势才有说服力。因此，在skyline算法中利用各个维度的数据大小建立索引的方式在k-支配skyline算法中失去了应有的效益。文献［11］中One-Scan算法采用了对所有维度值求和，用和值排序的方法。

在Web服务的动态Qos属性中，各Web服务可能成为skyline点的概率期望可以通过动态Qos属性的概率密度函数得到。通过概率建立如图3所示的索引，概率越大说明Web服务在各维度的综合属性越好即有越大的概率成为k-支配skyline服务。改进后的算法为Probability index based算法（PIBA），PIBA通过建立概率索引减少“错误”服务的数量，提高算法效率。

图2 非传递支配关系图

图3 概率索引图

Probability index based算法如下：

1）establishapossibilityindex for W

2）initializesetof k-dominant skyline points R=0

3）initialize set of unique non-k-domnant sky⁃line points T=o

4）for every point∈W used index do

5）initialize isUniqueSkyline=true

6） for every point p′∈T do

7）if（p dominates p′）then

8） remove p′from T

9）else if（p′dominates p）or（p=p′）then

10） isUniqueSkyline=false

11） break out of inner for-loop

12）if（isUniqueSkyline）then

13）initialize isDominant=true

14） for every point p′∈R do

15）if（p′k-dominates p）then

16） isDominant=false

17）if（p k-dominates p′）then

18） remove p′from R to T

19）if（isDominant）then

20） insert p into R

21）else

22） insert p into T

23）return R

4 分析与实验

实验的软硬件环境为：Visual C++6.0，Intel Pentium42.4GHz，4GRAM，Windows7，Matlab R2014a。实验采用的数据集是WS-DREAM数据［12］，该数据集统计了142个用户在获取4500个真实服务时的Qos属性值。通过WS-DREAM数据集中Web服务Qos质量的统计值，本文采用极大似然估计法得到Web服务各Qos质量的高斯分布，利用Matlab完成概率计算的预处理步骤，然后建立索引，并且利用各分布随机产生Qos属性值，最后利用Visual C++6.0完成概率索引k支配算法PIBA的仿真实验。

实验在相同软硬件环境下取Web服务中的14维Qos属性，通过实验比较改进后的概率索引算法PIBA与现有的k-支配skyline算法在不同k值情况下处理Web服务动态Qos属性的处理时间，来反应概率索引算法的高效性。实验结果如图4所示。

图4 处理时间结果图

由图4可知，One-Scan算法的综合表现最差，在实验的所有k值上处理时间都最长，但因为One-Scan一次计算需要两次全表扫描，因此表现虽差却十分稳定，不随k值变化而发生较大变化，可这种稳定性是牺牲时间复杂度与IO花销换来的。

Two-Scan算法在12维以下的效率比Sorted re⁃trieve算法要高，但是随着k值的增长Two-Scan算法的效率逐渐增高，甚至在k=14时算法效率近似于One-Scan算法，这是由于k越小，支配的约束越强，在第一次扫描中能通过支配关系淘汰的数据点就越多，但是随着k的增长这种高效性会逐渐降低。

Sorted retrieve算法总体来说效益高，稳定性好，在各个k取值情况下的效率都表现较好。

本次实验结果显示改进后的Possibility index based算法在各个k取值情况下计算效率都是最高的、计算速度始终是最快的。

5 结语

由于k-支配定义中关于支配定义的强化，导致了非传递性的支配关系，这种强化后的支配关系不能在一个数据点被支配后就直接过滤数据点所支配的其他数据点，因此一般性的索引在k-支配skyline计算中不起作用。

本文考虑了在Web服务的动态Qos属性下，经由统计数据估计服务分布，利用分布得到了各Web服务成为skyline服务的概率，这种概率综合反映了Web服务在各Qos属性下的综合能力，利用此概率建立索引来优先将较强支配力的数据点先加入计算过程，用以提早排除较差数据点，实验证明本算法比现有的3种算法有更高的效率。

对于k-支配skyline算法，能否建立更加高效的索引机制来提前进行数据点的过滤是可以进一步研究的问题。同时，如何更科学统计动态Qos属性的值与估计Qos属性的分布也是值得探讨的问题。