随着因特网的快速发展，网络服务呈现出爆炸式的增长，尤其是云媒体服务，大量具有相同或相似功能的云媒体服务部署在网络上供服务请求者使用.如何从众多的服务中选择合适的服务提供给用户，即进行有效的服务选择，从而提高服务质量(QoS, quality of service) 及用户满意度，成为现今云媒体服务研究重点.

夏虹等^[1]针对现有Web服务组合中服务选择技术的不足，提出了一种基于粒子群优化算法的多目标优化策略，用于解决Web服务组合中基于QoS的服务选择全局最优化问题；Shao等^[2]提出了一种基于协同过滤的QoS值预测算法，通过标准化用户-服务矩阵来优化近邻用户，从而提高QoS的准确性，为用户提供更好的服务.Zhao等^[3]依据QoS指标进行过滤，结合用户偏好提出了面向服务架构的云服务选择算法，从而提高服务选择的动态性能.

笔者提出一种基于QoS预测机制的个性化云媒体服务选择(PCSSQP, personalized cloud-media services selection based on QoS prediction) 算法.首先，基于信任度模型为当前调用服务的用户找到最佳近邻用户，再利用协同过滤对未调用过的服务进行QoS值预测，选出能够提供较高质量的候选服务；其次，利用逼近理想解排序(TOPSIS, technique for order preference by similarity to an ideal solution) 方法，结合用户偏好，计算候选服务相似指数，获得最符合用户偏好的服务并提供给用户.仿真结果表明，PCSSQP算法的QoS预测准确度和提供的服务的QoS及用户满意度优于现有算法.

1 基于信任度的QoS值预测算法

云媒体服务的非功能属性通常描述为QoS，当从功能相同的服务集合中进行服务选择时，用户没有全部可用服务的QoS值，因此QoS的预测对于决策的制定显得尤为重要.协同过滤广泛应用于各种推荐系统中以提升用户的体验，它根据用户以前的QoS历史记录，找到近邻用户，并根据近邻用户的QoS值来对当前用户的未知服务的QoS值进行预测.在协同过滤算法的基础上，引入用户信任度，优化近邻用户的选取，获得更加准确的QoS预测值.

1.1 信任度模型建立

对于一个云媒体服务调度系统，其中含有n_u个用户，n_s个服务，用户调用服务的历史记录信息记录在一个n_u×n_s的矩阵中，称为用户-服务矩阵，用R表示.其中r_{i, j}表示第i个用户调用第j个服务的QoS记录，r_{i, j}=C=(C₁, C₂, …, C_n)，C_k(k∈[1, n]) 为QoS指标.

由于皮尔逊相关系数(PCC, Pearson correlation coefficient)^[4]计算简单，准确度较高，广泛应用在各种推荐系统中.对于用户a和用户b，采用PCC求解用户之间的相似度为

$ \text{Sim}\left(a, b \right)=\sum \text{ }\frac{\sum\limits_{j\in J}{({{r}_{a, \text{ }j}}-{{{\bar{r}}}_{a}})({{r}_{b, j}}-{{{\bar{r}}}_{b}})}}{\sum\limits_{j\in J}{{{({{r}_{a, j}}-{{{\bar{r}}}_{a}})}^{2}}}\sqrt{\sum\limits_{j\in J}{{{({{r}_{a, j}}-{{{\bar{r}}}_{b}})}^{2}}}}} $

(1)

其中：J=J_a∩J_b为用户a和用户b共同使用的服务，r_{a, j}为用户a调用服务j时得到的QoS值，r_a为用户a调用云媒体服务的平均QoS值，r_{b, j}为用户b调用服务j时得到的QoS值，r_b为用户b调用云媒体服务的平均QoS值.从相似度的定义可以看出，Sim (a, b) 的取值在[-1,1]之间，值越大，则表示用户a和用户b的相似度越高.

利用相似度计算公式可以为当前用户u建立近邻用户集合.常用的方法是利用Top-K算法选取相似度最高的K个用户.在Top-K算法的基础上，引入信任度模型，用来对当前用户的近邻用户进行信任度评价，达到优化近邻用户集合的目的.

近邻用户的求解如下：

$ \begin{matrix} S\left(u \right)=\{{{u}_{l}}|\text{Sim}(u, {{u}_{l}})\times {{f}_{u, {{u}_{l}}}}\left(t \right)\in \text{Top}-K, \\ \text{Sim}({{u}_{l}}, u)>0, {{u}_{l}}\ne u\} \\ \end{matrix} $

(2)

得到的集合S(u) 即为当前用户u的近邻用户集合，其中f_{u, u}(t) 为用户u和其近邻用户u_l之间在t时刻的信任度，它是一个变量，计算公式为

$ \begin{matrix} {{f}_{u, {{u}_{l}}}}\left(t \right)={{f}_{u, {{u}_{l}}}}\left(t-1 \right)+\text{R}{{\text{d}}_{{{u}_{l}}}}\left(t \right)|\text{P}{{\text{t}}_{{{u}_{l}}}}\left(t \right)\\ ({{u}_{l}}\in S\left(u \right))\\ \end{matrix} $

且

$ \left.\begin{align} &{{f}_{u, {{u}_{l}}}}\left(0 \right)=1 \\ &{{f}_{u, {{u}_{l}}}}\left(t \right)={{f}_{{{u}_{l}}, u}}\left(t \right)\\ \end{align} \right\} $

(3)

其中：f_{u, u}(t-1) 为用户u和其近邻用户u_l前一时间内的信任度，初始值为1，每经过一次预测，都会对用户u和u_l之间的信任度进行更新；Rd^_ul(^t)|Pt^_ul(^t) 为更新参数，会根据预测结果进行相应更新.

1.2 QoS值预测

利用信任度模型计算出用户u的近邻用户集合S(u)，然后使用S(u) 来预测当前用户u的QoS值P(r_{u, j})，计算公式为

$ P({{r}_{u, \text{ }j}})=\bar{u}+\frac{\sum\limits_{{{u}_{l}}\in S\left(u \right)}{\text{Sim}(u, {{u}_{l}})}({{r}_{{{u}_{l}}, \text{ }j}}-{{{\bar{u}}}_{l}})}{\sum\limits_{{{u}_{l}}\in S\left(u \right)}{\text{Sim}(u, {{u}_{l}})}} $

(4)

其中：u为当前用户u观测到的不同云媒体服务的QoS平均值，u_l为近邻用户u_l(u_l∈S(u)) 观测到的不同云媒体服务的QoS平均值.通过上述公式即可算出用户u对服务j的预测QoS值.

当预测出用户u对服务j的QoS值之后，就可以根据式(5) 更新用户u和其近邻用户u_l之间的信任度了.更新参数Rd_ul(t)|Pt_ul(t) 的计算公式为

$ \underset{{{u}_{l}}\in S\left(u \right)}{\mathop{\text{R}{{\text{d}}_{{{u}_{l}}}}\left(t \right)|\text{P}{{\text{t}}_{{{u}_{l}}}}\left(t \right)}}\, =~\frac{\text{Si}{{\text{m}}_{j}}(u, {{u}_{l}})-\text{Sim}(u, {{u}_{l}})}{|\text{Si}{{\text{m}}_{j}}(u, {{u}_{l}})\left|+\right|\text{Sim}(u, {{u}_{l}})|} $

(5)

其中Sim_j(u, u_l) 表示对于预测的服务j用户u和用户u_l的相似度，它的取值范围是[-1,1].

1.3 近邻用户优化

当信任度更新以后，即可为当前用户u需要预测的服务j重新选择近邻用户集合S(u)，再利用S(u) 预测服务j的QoS值，并重新更新信任度，不断循环此过程，当满足式(6) 时，即认为此时的S(u) 为最佳近邻用户集合.

$ 1-\varepsilon <\frac{{{{\bar{j}}}_{{{u}_{l}}}}}{{{{\bar{j}}}_{u{{'}_{l}}}}}<1+\varepsilon, \text{ }\forall \varepsilon >0~ $

(6)

其中：j_ul为本次计算得到的近邻用户集合S(u) 关于服务j的平均QoS值，j_u′l为上次计算得到的近邻用户S′(u) 的平均QoS值.对于∀ε>0，1±ε→1，此时j_ul→j_u′l，即近邻用户集合不再改变，此时的S(u) 为最优集合.

获得当前用户u的最佳近邻用户集合S(u) 后，即可利用式(4) 对当前用户u的未知服务j进行预测，从而得到用户u对服务j的最佳预测值.

获得当前用户u的所有可提供服务的集合S_u，再利用阈值σ对服务进行过滤，得到可以为用户提供较高QoS值的候选服务S(m)，计算公式为

$ S\left(m \right)=\{{{s}_{j}}|{{s}_{j}}\in {{S}_{u}}, {{s}_{j}}>\sigma \} $

(7)

其中σ=S_u为可以提供服务集合的平均QoS值，留下的服务作为候选服务集合S(m).

2 基于用户偏好的云媒体服务选择算法

得到可以提供较高QoS的候选服务集合S(m) 后，以往服务选择时倾向于选择QoS值最大服务给用户，但并未考虑到用户的偏好，因此并不是最合适的服务.为此，将用户的需求考虑进来，利用偏好权重对候选服务进行排序，选出最适合用户的服务，进而提高用户满意度.

笔者利用TOPSIS^[5]方法结合用户QoS偏好权重求出候选服务的相似指数，进而选取相似指数最大的服务提供给用户.

2.1 用户偏好

用户偏好定义为用户对于服务的各个QoS指标的一种主观意愿.用户偏好的动态性直接表现为用户需求的动态性，为用户提供符合其偏好的服务是个性化服务选择的任务.

用户偏好可以表示为一个权重向量W：

$ W=({{W}_{1}}, {{W}_{2}}, \ldots, {{W}_{n}}), \sum{{{W}_{k}}=1}, k\in \left[1, n \right] $

(8)

其中：n为QoS指标的数目，W_k为用户对于QoS指标C_k的偏好权重.

2.2 用户相似指数求解

计算m个候选服务集合S(m) 的所有云媒体服务的相似指数G_i(i∈S(m))，由大到小对云媒体服务进行排序，G_i值最大的服务S_o将作为最佳服务提供给用户.用户相似指数G_i的计算公式为

$ {{G}_{i}}=\frac{D_{^{j}}^{'}}{D_{j}^{*}+D_{^{j}}^{'}} $

(9)

其中D_j^*和D′_j分别为云媒体服务针对各个QoS指标的理想解A^*与负理想解A′的距离，计算公式为

$ {{D}^{*}}={{\left(\sum\limits_{i\in \left[1, n \right]}{{{({{v}_{ij}}-v_{j}^{*})}^{2}}} \right)}^{\frac{1}{2}}} $

(10)

$ D_{^{j}}^{'}={{\left(\sum\limits_{i\in \left[1, n \right]}{{{({{v}_{ij}}-v_{j}^{'})}^{2}}} \right)}^{\frac{1}{2}}} $

(11)

其中：v_ij为加权标准化后的QoS评估矩阵V的第i个服务的第j个QoS指标评估值，v_j^*为第j个指标的理想解，v′_j为负理想解，计算公式为

$ v_{j}^{*}=\{\underset{i\in \left[1, m \right]}{\mathop{\text{Max}({{v}_{ij}})}}\, , i=1, 2, \ldots m\}, \text{ }j=1, 2, \ldots, n~ $

(12)

$ v_{j}^{'}=\{\underset{i\in \left[1, m \right]}{\mathop{\text{Min}({{v}_{ij}})}}\, , i=1, 2, \ldots m\}, \text{ }j=1, 2, \ldots, n~ $

(13)

需要注意的是，每一种QoS指标的评价标准是不一致的.例如，假设服务S_j的QoS指标C_j为视频质量，则其理想解为所有候选服务中质量最大值，负理想解为所有候选服务中质量最小值.所以式(12) 和式(13) 会随着QoS指标的评价标准进行调整.

3 仿真实验

为了对真实环境下云媒体服务的QoS属性进行研究，需要对不同位置和不同网络下云媒体服务进行评估.郑子彬等^[6]提出了一种Web服务分布式评估框架，并对真实Web服务进行多次大范围的分布评估，笔者利用其收集的数据集WS-DREAM来验证算法的有效性.它是一个142×50的用户-服务矩阵，即R_142×50，记录了142位用户调用50个服务的响应时间和吞吐量的值.

3.1 预测准确性

在衡量不同预测算法的准确性上，归一化平均绝对误差(NMAE, normalized mean absolute error) 因其计算简单、通俗易懂得到了广泛应用，计算公式为

$ \frac{M}{\sum\limits_{i, j}{{{r}_{i, j}}/N}}=\frac{\sum\limits_{i, j}{\left| {{r}_{i, j}}-{{{\hat{r}}}_{i, j}} \right|}}{\sum\limits_{i, j}{{{r}_{i, j}}}} $

(14)

其中：r_{i, j}为用户i调用服务j的QoS真实值，${{{\hat{r}}}_{i, j}}$为QoS预测值，N为服务的QoS预测值的个数.

为了比较不同算法的预测准确性，将R_142×50分成两部分：一部分作为预测的训练集；另一部分作为预测的测试集.通过将所提的PCSSQP算法与基于用户的皮尔逊相关系数(UPCC, user-based pearson correlation coefficient) 和基于项目的皮尔逊相关系数(IPCC, item-based pearson correlation coefficient) 算法^[7]进行对比，不同K值的的实验结果如图 1所示.

从图 1可以看出，随着K值的增加，3种算法的NMAE值都减小，并逐渐趋于稳定.对于选取不同的K值时，PCSSQP算法的NMAE值明显低于其他2种算法，因此所提出的PCSSQP算法在QoS预测准确性上优于UPCC算法和IPCC算法.

3.2 用户满意度

服务选择算法是否可以满足用户个性化的需求是非常重要的，这也决定了服务选择算法的优劣.下面利用用户满意度^[8]来衡量算法选择的服务跟用户需求的匹配程度.

在进行服务选择时，选取了常用的随机算法(RA, random algorithm)、贪婪算法(GA, greedy algorithm) 和服务提供商搜索引擎(SPSE, service providers search engine) 算法^[3]与所提的PCSSQP算法进行对比，仿真结果如图 2~图 4所示.

从图 2和图 3可以看出，RA随机选择服务提供给用户，因此它的性能最差，平均时延最大，平均带宽最低；GA则是选取QoS值最高的服务提供给用户，因此GA的性能最好，选取的服务具有最小时延和最高带宽；所提PCSSQP算法较SPSE算法在进行服务选择时随机的平均时延更小，平均带宽更高，所以选出的服务QoS值更高.

从图 4可以看出，PCSSQP算法具有最高的用户满意度，SPSE算法次之，而GA和RA的用户满意度较差.RA的性能最差，QoS值最低，用户的满意度也最低，而GA的用户满意度较低.PCSSQP和SPSE算法能较好地满足用户的需求，PCSSQP算法较SPSE算法有更高的QoS值和更大的用户满意度，因此可以有效提高云媒体服务选择的质量和用户满意度.

4 结束语

针对云媒体的服务选择算法问题，提出了PCSSQP算法.重点研究了未知服务的QoS值预测问题和用户偏好的服务选择问题.实验结果表明，PCSSQP算法较现有算法可以更准确地预测未知服务的QoS值，并满足用户的偏好，提高用户满意度.如何进一步提高服务选择的效率是下一步研究工作的重点.