一种基于灰关联分析的QoS服务选择方法*

张　皓，王明斐

（河南机电高等专科学校，河南　新乡　453000）

一种基于灰关联分析的QoS服务选择方法*

张皓，王明斐

（河南机电高等专科学校，河南新乡453000）

随着网络中可供选择QoS服务日益增多，在用户请求服务时，为了确保用户获得满足其功能与QoS要求的服务，提出了一种基于灰关联分析的QoS服务选择方法，根据用户对网络服务的QoS需求估计各项QoS指标的主观权重，以用户的偏好感知作为服务选择的约束条件；基于候选服务集合构建候选服务决策矩阵，采用灰关联分析方法从中获得用户QoS满意度最高的服务。仿真和分析表明，该服务选择策略能为服务质量敏感的用户提供有效的满足QoS需求的服务方案。

服务质量，用户体验质量，灰关联，服务选择

0　引言

随着网络技术的不断进步与用户QoS（Quality of Service）业务需求的爆炸性增长，多种多样可选择的QoS网络服务同时涌现。基于网络用户的业务需求，如何建立有效的服务选择策略以确保用户获取满足其实际QoS需求的服务，成为当前网络发展的一个亟待解决的问题。然而，QoS指标仅仅反映了服务技术层面的性能，忽略了用户主观需求与偏好，难以直接反映用户对服务的实际认可程度。因此，近年来基于用户体验质量（Quality of Experience，QoE）进行服务选择的研究开始引起人们越来越多的关注。

综合文献［1-3］的定义，可以将QoE理解为：用户在与服务或者应用交互的过程中，由用户产生的对所使用的服务的整体认可程度［4］。由于QoE综合了服务层面、用户层面、环境层面的影响因素，直接反映了用户对请求服务的QoS属性偏好，基于QoE进行网络服务选择无疑更能满足用户QoS要求。然而，以用户QoE为中心的服务选择算法［5］设计存在着诸多难点，主要表现在：首先，用户要求的网络业务往往包括多维QoS性能属性，从众多不同类型，且具有不同QoS属性值的候选服务中选择满足用户要求的网络服务，存在着QoE的部分影响因素难以确定，用户的主观因素（如用户期望、服务体验）和环境因素对QoE的影响难以量化评价等问题；其次，不同的用户对QoS指标各有偏好，网络所提供的服务也存在差别，如何对各QoS性能指标进行综合分析、处理使得选择的网络服务尽量贴近用户需求，并将算法复杂度控制在可接受的范围内。

针对QoS感知的服务选择问题，文献［6］研究了云计算多数据中心环境下QoS偏好感知的副本选择策略，根据用户的业务偏好对候选服务进行基于模糊准则的综合评判，以获得QoS满意度最高的副本节点。文献［7］综合考虑了运营成本、服务性能等属性，通过灵活调整QoS服务模型中运营商满意度与用户满意度在选择策略中的比重，从而设计有效的服务优选策略来解决服务选择问题。文献［8］提出采用K-means算法对候选服务集合进行聚类，分别计算各聚类中所有候选服务的质量水平 （代表各服务类的服务质量），最后将获得的相关质量参数作为局部约束条件来选择用户需要的服务。文献［9］对于用户QoE的服务选择问题提出了一种新的服务选择优化方法，当网络服务无法满足用户QoE需求时，基于用户与服务提供者之间的QoS参数协商进行二次寻优的服务选择优化，以进一步寻找具有QoS端到端保障的组合服务，从而减少了服务选择失败的概率。上述这些服务选择方法往往注重于降低服务选择的时间复杂度，为用户提供便捷有效的服务组合，但未能充分考虑QoS指标的不确定性和用户偏好，使得最终的服务选择结果往往偏离用户的QoS需求，导致用户满意度下降，甚至服务组合失败。因此，有效的服务选择方案需要能够尽可能地满足用户QoS的需求，从而改善网络的QoS保障能力。

基于此，本文提出了一种基于灰关联分析的QoS服务选择方法，根据用户对网络服务的QoS需求，采用层次分析法（Analytic hierarchy process，AHP）估计QoS各项指标的主观权重，从而间接地获取用户的偏好感知作为服务质量敏感的约束条件；构建满足用户要求的可用候选服务集，采用灰关联分析的方法从候选服务集中获得用户QoS满意度最高的服务。仿真和分析表明，本文提出的基于用户体验质量的服务选择策略能为服务质量敏感的用户提供有效的、切实满足QoS需求的服务方案。

1　基于用户体验质量的服务选择策略

依据解决多属性决策问题的基本思路［10］，本文提出了基于用户体验质量的灰关联服务选择策略，具体流程如图1所示。首先从用户QoE需求出发，建立合理有效的QoS指标主观权重；同时基于承载网络筛选的候选服务集合建立服务决策矩阵，以从用户QoE需求为中心，灰色关联度作为判决指标，分析用户QoE与承载网络提供的各项网络服务的灰关联度，实现从用户体验质量到网络服务的自适应选择过程，以使用户获得最佳的服务体验和满意度。

图1　基于灰关联分析的服务选择策略流程

1.1基于层次分析法估算主观权重

服务选择以确定候选服务各项QoS指标的权重评估为前提，获取各QoS性能指标的主观权重后才能进一步计算承载网络提供的各项服务是否满足用户的QoE需求。QoS指标参数权重设置是为了确定各项QoS指标在某项业务中为用户体验质量所重视的程度，通常来说，用户满意度对某个指标的变化越敏感，越说明该指标对用户满意度的影响越重要，即相对于其他指标权重越大。

本文采用层次分析法估算各项QoS指标的主观权重，其基本思路是：基于用户对各QoS指标重要性的感知，对其进行两两比较，生成判断矩阵，通过求解判断矩阵的最大特征根向量，从而获得基于用户QoE的各QoS指标的主观权重值，为后续的服务策略实现作准备。

首先用户根据对各项QoS指标重要性的主观感知，建立QoS指标重要性判断矩阵。若提供的服务包括n个QoS指标，则重要性判断矩阵为

其中，aij表示第i个指标与第j个指标的重要度比较参考值，且aij=1/aij。

由于不同用户所需要和偏好的QoS指标各有不同，而不同业务的QoS指标的重要性也各不相同，因而需要确定各项业务类型的中QoS指标的重要性。一般而言，会话类业务对抖动和时延较为敏感，而对少量的业务丢包则不太敏感，所以会话类业务中抖动和时延指标对会话质量的影响相比误码率和丢包率要更为重要。基于人们判断事物重要性的主观衡量习惯，设置1～9的标度值作为判断各项QoS指标重要性的量化标准，其具体等级划分如表1所示。

表1　1～9标度值的含义

然后在判断矩阵A的基础上利用特征根法求出各项QoS指标的主观权重值。根据式（2）求解判断矩阵最大特征值所对应的特征向量：

将ωq+1进行归一化处理，比较两相邻阶数的特征向量的距离。对于给定精度ε＞0，当∀i∈N，若满足条件：

1.2构建候选服务决策矩阵

假设对于某项网络服务Si由n项用户所关心的QoS指标组成，表示为Si=｛qi1，qi2，…，qin｝。若当前网络环境可提供的m项不同的网络服务，可表示为：

其中，行向量 ｛qi1，qi2，…，qin｝中各元素分别对应服务Si在n项QoS指标上的属性值，1≤i≤n。列向量表示所有相关服务在QoS属性qj上的值，1≤j≤m。矩阵S确定了实际网络环境下用户可选择的网络服务范围。

由于QoS指标一般可分为效益型和代价型两类，效益型如可用带宽、信号强度等，其测量值越大越好；代价型如时延、抖动等，其测量值越小越好。为了消除不可公度性，采用极变差法对矩阵S进行标准化处理：

用户面临网络切换或移动到新的接入网络时，候选服务决策矩阵往往需要及时更新，要去除服务决策矩阵X中当前网络环境已经无法提供的服务选项，并引入当前网络环境提供的新服务选项以代替旧的服务方案，然后这就要求服务选择策略能够适应复杂、变化的网络环境，及时更新构建服务决策矩阵，为后续的服务选择提供保障。

1.3基于灰关联的服务选择策略

灰关联分析（Gray Correlation Analysis，GRA）［11］是关联度分析方法中性能较好，应用较多的一种代表性算法。由于用户主观的体验质量与网络客观QoS参数相互契合，但又往往存在着差异，可以认为二者也存在着某种灰色关联度。由于业务的不同，用户需求的不同，这种关联也会受到不同程度的波动和影响。因此，可以将用户服务选择的多属性决策问题转化为从当前网络可提供的服务决策标准化矩阵X中寻找与用户需要的体验质量req具有最大灰关联度的服务选项，以实现户主观感知QoE与网络服务的QoS指标能够实现最佳匹配。

基于此，本文采用基于灰关联的服务选择策略分析网络中的用户QoE和承载网络提供QoS服务之间的关联程度，如果某网络服务与用户QoE的灰关联度越大，则认为该服务越能满足用户的QoE需求，从而据此选择最适合的网络服务。该服务选择策略具体步骤如下：

步骤1：根据式（7）获取当前网络提供的服务决策标准化矩阵X后，基于用户QoE的网络服务要求，计算矩阵X中各项服务Xi与用户QoE需求req的灰关联系数。

设基于用户QoE的服务需求为reg=（r1，r2，…，rn），ri表示用户QoE向量req中第i个QoE指标的要求参数，1≤i≤n。φij表示某项服务Xi关于用户体验质量的子属性rj的灰关联系数：

｝，从而获得m个网络服务选择方案的灰色关联系数矩阵为φ=（φij）m×n。

步骤2：计算m个候选QoS网络服务组合与用户体验质量的灰关联度向量。

已知用户对于各项QoS指标的主观权重向量ω=（ω1，ω2，…，ωn）和当前所有网络服务关于用户QoE需求的灰色关联系数矩阵φ，计算网络中m项服务与用户体验质量需求的灰关联度向量cor。

其中，wj表示用户对QoS指标qj主观权重，可以根据1.1节中采用的特征值法通过式（1）～式（4）获得。cor（i）是向量cor的元素，表示第i项服务与用户QoE的灰关联度。

步骤3：从m个候选QoS网络服务组合中获取最能满足用户体验质量，即选择与用户主观权重有最大灰关联贴近度的网络服务。

由于用户对网络服务的各项QoS指标的重视和敏感程度不同，在满足用户QoE的服务需求同时，所选择的网络服务与该用户的QoS指标主观权重必须有最大灰关联度。网络服务按照灰关联度的大小排序，cor（i）值大的服务优先；反之，cor（i）值较小的服务则为劣。选取cor中具有最大的灰联度的网络服务，即为最能满足用户体验质量的服务方案Sslect为：

2　实验仿真与分析

算法的仿真平台为：处理器Interl（R）Core2 2.83 GHz，内存4.00 GB，Microsoft Windows 7 Professional的64位操作系统，编程环境Matlab R2010b。实验采用公共有效数据集QWS［12］和Skyline dataset generator［13］生成数据集。QWS真实数据集来自互联网上的公共Web服务，该数据集包含了多个Web服务及其对应的9个QoS属性值，如响应时间、可用性等。Skyline dataset generator能够生成多种类型的人工服务数据，在国内外的相关研究中应用较为广泛。本文选用其生成的独立数据（independent data），每项服务包含9个QoS属性值，各QoS指标的属性值随机生成。

文献［9］所提出的ASCA算法是QoS感知的服务选择方法领域具有代表性的算法。实验将分别基于QWS数据集和生成数据集，对本文方法与ASCA算法进行比较以验证其性能。实验数据集包含有10个服务类，服务交互次数由100上升至1 000，分别从10个服务类中等量随机抽取。每次服务选择交互都从某服务类随机抽取一项作为基于用户体验质量的服务请求，然后从该服务类中随机抽选等额的服务作为候选。为了验证本文方法在服务选择中的有效性，同时与ASCA方法进行对比，假设sk=sslect为最终的服务选择方案，则定义用户满意度为：

图2　在QWS数据集上用户满意度对比

图3　在生成数据集上用户满意度对比

如图2、图3所示，当服务交互次数较少的时候，受用户QoE中主观因素的影响，两种服务选择方法的用户满意度都呈现出不同程度的波动，而本文方法获得的用户满意度更为稳定；随着服务交互次数的递增，逐步积累的经验数据进一步限制了用户QoE中不确定的主观因素，两种服务选择方法在两个数据集上获得的用户满意度开始逐步趋于稳定。在QWS数据集上，本文方法相对ASCA算法用户满意度更高，波动性更小；在随机生成数据集上，本文方法的用户满意度仍然具有优势，但两种方法在用户满意度方面性能都有所下降，且二者差距在减小。这是因为QWS数据集有效性更强，两种方法的服务选择效果更好；而生成数据集中的候选服务随机性更大，与用户主观的QoE出入较大，因而造成服务选择的用户满意度略有降低。

综合图2、图3可知，本文基于用户体验质量的灰关联服务选择算法比ASCA算法更好地反映了用户QoS感知需求，从而能够选择更能贴近用户需要的网络服务。这是因为本文提出的服务选择策略对用户QoE进行层次性分析以保证QoS指标的主观权重的有效性，并基于灰关联分析获取候选服务中最贴近用户需求的服务，从而剔除不确定性较高的Web服务，减小了实际服务选择与用户主观的QoE需求之间的偏离度，提高了服务选择的可靠性。在开放动态的网络环境中，该方法能够有效克服QoS的不确定性对Web服务选择可靠性的影响，它不仅为用户提供了可靠的QoS约束保障，而且还能够为用户提供高质量的服务选择。

3　结论

本文提出了一种基于灰关联分析的服务选择方法。该方法在选择用户需要的网络服务时既考虑QoS指标的客观特性，也考虑了用户体验质量的主观需求，弥补了以往此类算法仅仅考虑选择策略的不足，算法简单，适用性强，能够有效地满足用户对选择服务的QoS需求。仿真和分析表明，该服务选择策略能为服务质量敏感的用户提供有效的、切实满足QoS需求的服务方案。但在QoS指标选项增多时，计算量会急剧增大；在移动终端频繁切换时，也会增大候选服务集合的更新、选择的计算量，这也是未来工作中需要进一步改善和研究的方向。

［1］SILLER M，WOODS J C.QoS arbitration for improving the QoE in multimedia transmission［C］//Visual Information Engineering，2003.VIE 2003.International Conference on. IET，2003：238-241.

［2］O'Nell Timothy M.Quality of experience and quality of service，for IP video conferencing［C］//Director of Technical Marketing of Polycom Video Communications.White Paper By Polycom，2005.

［3］ITU-T：Definition of quality of experience（QoE）［S］// International Telecommunication Union，Liaison Statement，Ref.：TD 109rev2（PLEN/12），2007.

［4］林闯，胡杰，孔祥震.用户体验质量（QoE）的模型与评价方法综述［J］.计算机学报，2012，35（1）：1-15.

［5］倪萍，廖建新，王纯，等.一种KPI映射到KQI的通用算法［J］.电子与信息学报，2008，30（10）：2503-2506.

［6］熊润群，罗军舟，宋爱波，等.云计算环境下QoS偏好感知的副本选择策略［J］.通信学报，2011，32（7）：93-102.

［7］武蕾，刘玉龙，刘士军.多策略QoS感知的服务选择与排序模型［J］.通信学报，2012，33（1）：141-147.

［8］ ALRIFALM，SKOUTASD，RISSET.Selectingskyline services for QoS-based Web service composition［C］//Proc. of the 19th Int'l Conf.On World Wide Web（WWW 2010）. 2010：11-20.

［9］ADAGNA D，PERNICI B.Adaptive service composition in flexible processes［J］.IEEE Trans.on Software Engineering，2007，33（6）：369-384.

［10］TSAI C H，CHANG C L，CHEN L.Applying grey relational analysis to the vendor evaluation model international journal of the computer［J］.The Internet and Management，2003,11 （3）：45-53.

［11］李军，房雅丁，宋梅，等.异构网络中一种基于灰度关联的动态接入选择策略［J］.北京邮电大学学报，2006 （11）：175-177.

［12］ALMASAR E，Mabmoud Q H.QoS-Based discovery and ranking of Web services［C］//Proc.of the 16th Int'l Conf.on Computer Communications and Networks（ICCCN 2007）. 2007：529-534.

［13］BORZSONYI S，KOSSMANN D，STOCKER K.The skyline operator［C］//Proc.of the 17th Int'l Conf.on Data Engineering （ICDE 2001），2001：421-430.

A Novel Algorithm of Quality of Service Selection Based on Gray Correlation Analysis

ZHANG Hao，WANG Ming-fei
（Henan Mechanical and Electrical Engineering College，Xinxiang 453000，China）

As the increment of QoS services in the internet，in order to select the services that fulfill users'functionality and QoS requirements，a service selection strategy based on users'QoS-aware of Experience is presented.The strategy estimates the subjective weight of each QoS index according with the users'QoS requirements of web services，to make the users'QoS preference as a constraint condition for service selection，and construction of decision matrix based on the candidate service set，to select the service with highest satisfaction on QoS using gray correlation analysis method.Simulation and analysis show that the service selection strategy can provide service schemes which would effectively satisfies QoS users'requirements.

quality of service，quality of experience，gray correlation analysis，service selection

TP393

A

1002-0640（2016）07-0043-05

2015-06-02

2015-07-05
*

河南省教育厅自然科学研究基金（2010A520013）；新乡市科技发展计划基金资助项目（08G072）。

张皓（1983-），男，河南新乡人，硕士，实验师。研究方向：计算机网络、软件工程等。