Web服务仍然是产业界和学术界的研究热点^[1]，而基于服务质量 (QoS，quality of service) 的服务提供技术显得尤为突出，因为QoS取决服务提供者行为、软硬件环境、传输网络、用户终端环境及认知程度等众多因素，对准确的QoS度量造成巨大困难.目前QoS度量方法主要有实数^[2]、区间数^[3]、模糊数^[4]、随机数^[5]等，并且设计了相应的服务选择算法和服务Skyline计算方法^[6].已有方法不能很好地描述QoS属性的风险，故提出用均值标准差描述QoS，使用均衡收益和风险的服务Skyline查询方法.

1 QoS模型

面向终端用户的服务，QoS由用户感知，属性应能反映用户的需求和影响用户的满意度，选择有代表性5个，在具体应用中可视情况调整.

定义1  Q=[q_co, q_res, q_rep, q_av, q_rel]，描述服务在执行过程中的一些性能信息，包括成本、响应时间、可信度、可用性、可靠性.

q_co代表用户执行服务所付出的成本，包括购买服务、网络流量、终端软硬件支持、能源消耗等.

q_res代表用户发送请求到结果呈现过程中的时间，包括执行时间、传输时间、显示时间等.

q_rep代表用户对服务的评价以及由评价而产生的服务态度，取决于用户对服务功能与成本之间关系的估计及用户对服务与自己之间关系的估计.

q_av描述服务对用户来说有效、易学、高效、好记、少错和令人满意的程度，即用户能否用服务完成任务，效率如何，主观感受怎样，是从用户角度所看到的服务的综合质量，是服务竞争力的核心.

q_rel是服务在规定的条件下和规定的时间区间完成规定功能的能力，服务的可靠性受软件设计、服务器负载、网络、终端环境等复杂因素制约.

上述属性由用户以评分方式给出，按照用户对属性评价的好坏程度分为11个等级，依次为10分、9分、8分、…、1分、无法访问为0分.属性用均值E和标准差S描述，E为用户评分序列的平均值，S为用户评分序列的标准差.

实例1  有k个图书检索服务s₁, s₂, …, s_k，QoS属性包括成本和可信度，其值由用户评分获得 (表 1是4个服务的用户评分信息，分值可为10分、9分、…、0分).用实数、区间数、模糊数、均值标准差表示的服务评价结果见表 2.其中评分转化三角模糊数依次为 (10，10，10)、(8，9，10)、(7，8，9)、(6，7，8)、(5，6，7)、(4，5，6)、(3，4，5)、(2，3，4)、(1，2，3)、(0，1，2)、(0，0，0)，其对应语言短语是 (尽善尽美、极高、非常高、很高、高、一般、低、很低、非常低、极低、一无是处).

s₁的可信度评分为5、6、4、3、5、7、3、5、4、5，用实数 (均值) 表示，没有体现出评分的风险 (动态变化)；用区间数 (3，7) 和三角模糊数 (3.7，4.7，5.7) 表示，虽然体现了风险，但降低了评分精度；用均值标准差 (4.7，1.41) 表示，均值体现收益, 即评分的整体倾向，标准差描述风险 (评分偏离均值的程度)，该方法具有更好的描述特性.

2 服务Skyline计算 (SSC)

QoS用均值标准差表示的服务间存在支配关系，称该过程为服务Skyline计算.

定义2(支配)  N维空间的点p(p₁, p₂, …, p_N) 和q(q₁, q₂, …, q_N)，∀i∈[1, N], (p_i≈q_i)∨(p_i$ \succ $q_i)($ \succ $表示好于，≈表示等于)，并且∃i∈[1, N], p_i$ \succ $q_i，称p支配q，用q$ \prec $_Np.

定义3(均值标准差优劣比较算子“$ \prec $”)  设t=(E, S) 和k=(E, S) 描述QoS属性，服务QoS属性有效益型指标O和成本型指标I；效益型指标越大，对评估结果越有利；成本型指标越小，对评估结果越有利. t, k∈O，有 (t.E≤k.E)∧(t.S≥k.S)，则t$ \prec $k；t, k∈I，有 (t.E≥k.E)∧(t.S≥k.S)，则t$ \prec $k；即均值标准差描述的变量k优于t.

定义4(服务支配)  设服务s₁、s₂由n个均值标准差描述的QoS属性构成；∀j∈[1, n], (s_1j$ \prec $s_2j)，称s₁$ \prec $_ns₂(“$ \prec $_n”称服务支配).

定义5(Skyline服务集)  服务全集X，n个属性上的Skyline服务集是那些不被备选服务集S中任何服务支配的服务构成的集合，s, r为X集中的服务：y(n, X)={s|(s∈X)∧(﹁∃r∈X), s$ \prec $_nr}.

实例2  表 1中有4个服务，QoS包括成本和可信度，属性值来源于10个用户的打分，其均值标准差计算见表 2，根据Skyline服务集定义 (见定义5) 可得y(2, X)={s₁, s₃, s₄}.

3 服务Skyline查询算法 (SSQA)

选取对数据点的无分布要求、无顺序要求、适应性强的4个Skyline查询算法^[7]——块嵌套循环 (BNL，block nested loop)、分而治之 (D & C，divide-and-conquer)、最近邻 (NN，nearest neighbor)、分支界定 (BBS，branch and bound Skyline) 作为基础，提出4种基于均值标准差的服务Skyline查询算法：1) 基于均值标准差的BNL算法 (BNL_MS，block nested loop based on mean and standard deviation)，2) 基于均值标准差的D & C算法 (DC_MS，divide-and-conquer based on mean and standard deviation)，3) 基于均值标准差的NN算法 (NN_MS，nearest neighbor based on mean and standard deviation)，4) 基于均值标准差的BBS算法 (BBS_MS，branch and bound Skyline based on mean and standard deviation).

3.1 BNL_MS

算法1  BNL_MS

输入：备选服务集X；输出：Skyline服务集Y

步骤：1) 依次从X中读取服务s_i，设置s_i为Skyline点标识flag=False；如果s_i不为空，执行步骤2)；否则，执行步骤3)；

2) 依次从Y中读取服务r_j；

① 如果r_j为空，并且flag=True，将s_i加入Y中，执行步骤1)；

② 如果r_j$ \prec $_ns_i，删除Y中点r_j，设置s_i为Skyline点标识flag=True，执行步骤2)；

③ 如果s_i$ \prec $_nr_j，丢弃s_i，执行步骤1)；

④ 如果t_j、s_i互相不支配，flag=True，执行步骤2)；

3) 输出SP.

3.2 DC_MS

算法2  DC_MS

输入：备选服务集X；输出：Skyline服务集Y

步骤：1) 如果X中有0或者1个备选服务，则执行步骤2)；否则求服务集X的中点位置$l = \frac{m}{2}$，从中点位置l分为集合P₁=S[1, l]和P₂=S[l, m]，对集合P₁和P₂执行步骤1)；

2) 根据定义5的不确定服务支配关系，通过比较运算合并P₁和P₂中的Skyline服务到Y集中，去掉那些被支配的点；

3) 输出Y.

3.3 NN_MS

NN、BBS算法是R树的数据结构，不确定服务是均值标准差表示，非数值型，因此需要定义基于均值标准差的R树，称为R-M树.

1) R-M树

R-M树的叶子结点所保存的数据形式为 (I, s, C)，其中：s表示一个n维属性的服务；I是一个n维空间的矩形，并可以恰好框住这个叶子结点，I=(I₁, I₂, …, I_n)；C是描述矩形的附加信息，C=(E_min, E_max, S_min, S_max)，E_min=(E_min1, E_min2, …, E_{min n}) 和E_max=(E_max1, E_max2, …, E_{max n}) 是矩形所覆盖数据子集在各维度上均值的最小值和最大值，S_min=(S_min1, S_min2, …, S_{min n}) 和S_max=(S_max1, S_max2, …, S_{max n}) 是矩形所覆盖数据子集在各维度上标准差的最小值和最大值，并且满足：

E_{min, i}≤I_iE≤E_{max, i}且S_{min, i}≤I_iS≤S_{max, i}

R-M树的非叶子结点的结构与叶子结点非常类似，R-M树的非叶子结点存放的数据结构为 (I, p, C)，其中p指向孩子结点的指针，I、C与叶子结点描述相同.

2) 距离公式

最近邻算法需要计算两个点间的距离，需要定义两个属性间的距离.

定义6  设i、j由均值标准差描述，其向量分别为c_i=(E_i, S_i) 和c_j=(E_j, S_j)，则i和j之间的欧氏距离为

$ \begin{gathered} d\left( {i, j} \right) = d\left( {{\mathit{\boldsymbol{c}}_i}, {\mathit{\boldsymbol{c}}_j}} \right) = \sqrt {{{\left( {{E_i} - {E_j}} \right)}^2} + {{\left( {{S_i} - {S_j}} \right)}^2}}, \hfill \\ 0 \leqslant d\left( {i, j} \right) \leqslant 1 \hfill \\ \end{gathered} $

欧氏距离越小，i, j距离越近.

定义7  对于效益型指标 (可信度、可用性、可靠性)，从均值标准差的数字特征可以发现，当所有用户给出该指标的评分为10分时，是最好结果，即E=1、S=0；当所有用户给出的评分为0分时，是最坏结果，即E=0、S=0.对于成本型指标 (成本、响应时间)，当所有用户给出该指标的评分为0分时，是最好结果，即E=0、S=0；当所有用户给出的评分为10分时，是最坏结果，即E=10、S=0.因此，原点的计算公式如下：

$ {\mathit{\boldsymbol{s}}_o} = \left\{ {\left( {{\mathit{\boldsymbol{c}}_1}, {\mathit{\boldsymbol{c}}_2}, \cdots, {\mathit{\boldsymbol{c}}_n}} \right)} \right\} $

其中${\mathit{\boldsymbol{c}}_j} = \left\{ \begin{gathered} \left( {10, 0, 0} \right)|j = O \hfill \\ \left( {0, 0, 0} \right)|j = I \hfill \\ \end{gathered} \right.$.

算法3  NN_MS

输入：备选服务集X (R-M树)；输出：Skyline服务集Y

步骤：1) 定义区间划分集合T={(∞₁, ∞₂, …, ∞_n)}；

2) 如果T不为空，从集合T中取出划分区间；否则，执行步骤3)；

① 在R-M树中读取划分空间范围的结点，如果划分空间中有结点，计算空间中所有结点到原点距离，取距离最近点为原点并划分空间，将划分空间加入集合T中，执行步骤③；

② 如果划分空间无结点，执行步骤2)；

③ 如果距离最近点为叶子结点，则将其加入Y中；否则，执行步骤2)；

3) 输出Y.

3.4 BBS_MS

算法4  BBS_MS

输入：备选服务集X (R-M树)；输出：Skyline服务集Y

步骤：1) 从根结点开始取R-M树中结点放入堆中；2) 当堆为空，执行步骤3)；否则，执行下列步骤：

① 移除堆顶元素e；

② 如果e被SP某些结点支配，则丢弃e，执行步骤2)；否则，执行步骤③；

③ 如果e是非叶子结点，计算e的所有孩子结点是否被SP中某些结点支配，如果支配不成立，则将相应孩子结点加入堆中；否则，执行步骤④；

④ 插入e到SP中，执行步骤2)；

3) 输出SP.

4 实验分析 4.1 查询算法正确性分析

有10个图书检索服务s₁、s₂、…、s₁₀，Q=[q_co(s_i), q_res(s_i), q_rep(s_i), q_av(s_i), q_rel(s_i)](见定义1)；4万名师生中有1万名师生提交了10个服务的QoS评价，随机取部分评价数据 (见表 3)，生成均值标准差QoS (见表 4).根据服务Skyline计算定义，s₁支配s₅、s₆、s₇、s₈、s₁₀并且s₂支配s₉，服务Skyline集为s₁、s₂、s₃、s₄. BNL_MS、DC_MS、NN_MS和BBS_MS能获得正确结果.

BNL、D & C、NN、BBS只支持QoS属性为实数的服务，在不考虑标准差时，上述4种算法获得Skyline集的结果相同，为Y=(s₁, s₂, s₃, s₄).在本实例中基于均值的4种算法与基于均值标准差的4种算法获得相同Skyline服务，但在服务数量较多时基于均值的4种算法获得的Skyline服务数量少于基于均值标准差的4种算法；当服务数量非常大时，在执行时间上才会有微小的不足，可以忽略.

表 5是真实服务QoS数据集WSDream^[2]中QoSDataset2的5个服务的响应时间和吞吐量，转换为均值标准差后，4种算法的服务Skyline集为 (1、2、4、5)，与服务Skyline集定义结果相同.

4.2 查询算法性能比较

图 1所示为4种Skyline查询、在独立数据集 (即QoS属性值随机产生) 上的时间复杂度比较，BBS_MS和NN_MS运行时间相近，优于BNL_MS和DC_MS；随着数据集扩大，时间性能变化不大，稳定性也优于BNL_MS和DC_MS. 图 2所示为在正向数据集 (即QoS属性值都较好) 上4种查询算法的时间性能比较，BBS_MS运行时间明显低于其他3种算法；BBS_MS和BNL_MS和DC_MS随着样本数的增多，搜索时间变化不大，稳定性较高，但NN_MS运行时间性能会有较大波动. 图 3所示为在反向数据集 (即QoS属性值一部分较好，一部分较差) 上的时间性能的比较，4种算法都呈线性增长的趋势，BBS_MS运行时间均低于其他3种算法，NN_MS也有较好时间性能.

5 结束语

传统基于QoS的服务评价方法只考虑QoS的效益没有考虑QoS的风险，使用均值标准差描述QoS指标，该方法相对于均值、区间数、模糊数等方法不仅能够体现QoS的效益也能体现QoS的风险；提出的基于均值标准差的Skyline计算方法，缩小服务搜索空间，提高效率；在服务Skyline计算基础上，改进4种常用的Skyline查询算法 (BNL、D & C、NN和BBS)，使其适应服务Skyline计算，实验证明基于BBS的BBS_MS具有较好性能.

用户评分由用户反馈，其可信性需要被充分考虑，需要研究一种方法有效识别用户评分是否可信；用户评分反馈需要占用资源和时间，不可避免出现用户不愿意对其使用过的服务QoS进行评价，需要建立一种激励机制抑制用户搭便车行为.