基于时间序列的感知QoS的云服务组合*

2014-09-13肖文娟段玉聪

计算机工程与科学 2014年11期

关键词：欧几里得范数度量

肖文娟，段玉聪

(海南大学信息科学技术学院，海南海口 570228)

基于时间序列的感知QoS的云服务组合*

肖文娟，段玉聪

(海南大学信息科学技术学院，海南海口 570228)

研究基于时间序列的感知QoS的云服务组合，将服务的QoS偏好随时间不断变化的过程纳入云服务组合的研究范围，将云服务组合建模成时间序列的相似度对比问题。分别用欧几里得距离和扩展Frobenius范数距离度量二维时间序列的相似度，继而用基于主成分分析的扩展Frobenius范数距离和欧几里得距离、Brute-Force等方法度量多维时间序列的相似度，通过实验对比验证扩展Frobenius范数距离度量相似度在时间和准确性上的优越性。

时间序列;QoS;云服务组合;相似度对比

1 引言

云计算(Cloud Computing)由分布式计算(Distributed Computing)、并行计算(Parallel Computing)、效用计算(Utility Computing)、网络存储技术(Network Storage Technologies)、虚拟化(Virtualization)、负载均衡(Load Balance)等传统计算技术和网络技术发展融合形成，是基于互联网的相关服务的增加、使用和交互模式。

云计算包括的服务类型有：基础设施即服务(IaaS)、平台即服务(PaaS)和软件即服务(SaaS)。IaaS是指消费者通过Internet可以从完善的计算机基础设施获得服务。PaaS是指将软件研发的平台作为一种服务，以SaaS的模式提交给用户，因此也是SaaS模式的一种应用。SaaS是一种通过Internet提供软件的模式，用户无需购买软件，而是向提供商租用基于Web的软件来管理企业经营活动。

随着云计算环境的广泛应用，公有、私有及混合云提供了大量具有相同功能和不同服务质量的云服务。同时，单个服务往往不能满足任务需求,而多个服务的组合却可以派生出新的服务从而满足需求。因此，如何构建能够满足用户QoS需求的组合云服务是云服务应用领域亟待解决的难题。

本文的主要研究内容是：(1)通过时间序列建模将云服务组合转化成时间序列的相似度对比问题；(2)采用基于主成分分析的扩展Frobenius范数距离/欧几里得距离、Brute-Force等方法等度量方法进行求解；(3)通过对比实验说明基于主成分分析的扩展Frobenius范数距离度量方法在时间和准确性上的优越性。

2 国内外研究现状

随着对QoS感知的云服务组合问题的研究日益深入，已经提出了大量相关算法[1]。QoS感知的云服务组合问题分为两类：一是在同一时刻的服务组合，二是不同时刻的服务组合。对于同一时刻能够提供的多种服务组合研究成果有很多，如Canfora G等人[2]提出了基于遗传算法的云服务组合方法，将组合服务编码成染色体，适应度值是服务的综合QoS。基于遗传算法的QoS感知的云服务组合算法在文献[3～6]中进行了许多改进。文献[3]提出了可用于QoS感知服务组合的树编码遗传算法(TGA)，对染色体进行树形编码。实验结果表明，TGA的运行速度与一维编码GA的最佳结果是一样的，并且树编码算法在运行时支持服务组合进行重新规划。文献[4]提出了基于种群的多样性和关系矩阵编码方案的遗传算法(CoDiGA)，该算法有效克服了早熟,并大大提高了遗传算法的收敛性和稳定性、服务选择组合的有效性。文献[5]提出的混合遗传算法可以有效解决大规模服务和限制下的服务组合优化问题。文献[6]提出的基于处罚的遗传算法，可以将组合服务分解为多个服务组件，便于组合服务的分散执行，以提高服务组合的效率。文献[7]提出可用于现有服务组合算法的缓存机制，以减少各服务组合算法的计算时间，提高服务组合的时间性能。文献[8]中基于免疫遗传算法的服务组合方法，将免疫原理引入遗传算法(GA)中，免疫选择可有效地防止早熟，基于免疫记忆的子群体信息交换策略可加速收敛，从而提高服务组合的质量和收敛速度。文献[9]中遵循精英蚂蚁保留策略的蚁群系统被应用于组合问题求解。文献[10]提出了一种基于移动代理的蚁群优化算法以提高组合的效率。文献[11,12]中用蚁群算法自动进行服务组合。文献[13]提出一种基于QoS 的启发式算法，可以动态调用Web Service来自动生成满足用户所需目标的Web Service组合。文献[14]基于模拟退火算法求解QoS约束Web服务组合。文献[15]提出了混合QoS模型感知的语义Web服务组合决策算法。文献[16]用改进的社会认知算法对QoS感知的云服务优化组合问题进行求解。文献[17]提出的基于扩展图规划的Top-K服务组合方法,通过服务索引和增加图规划中的辅助节点, 使得经过一次规划搜索即可找到Top-K个满足用户QoS要求的组合服务。

以上提出的算法都没有考虑组合的长期性目标问题而仅仅是满足当前目标，忽略了云服务组合的时间因素[18,19]，这是第二类云服务组合问题—不同时刻的云服务组合的重点。事实上某些组合服务的性能在当前并非是最好的，但在几年后会表现良好。文献[18]利用贝叶斯网络构建终端用户的经济模型，将云服务组合转化成影响图问题求解；时间序列可以描述各个因素随时间变化的过程，非常利于感知QoS的云服务组合问题的求解；文献[19]用欧几里得距离度量随时间变化的QoS因素及其因素间联系。本文研究基于时间序列的感知QoS的云服务组合，将服务的QoS偏好随时间不断变化的过程纳入云服务组合的研究范围，将云服务组合建模成时间序列的相似度对比问题，并通过实验验证扩展Frobenius范数距离度量相似度[20]在时间和准确性上的优越性。

3 云服务组合架构

考虑云服务组合的四种重要因素：服务的使用者、服务组合、SaaS提供者和IaaS(包含PaaS平台即服务)提供者，构建四层云服务组合架构，如图1所示。其中，服务使用者通常是大的公司或组织机构,如学校、政府等。服务组合层包含多种服务组合框架。SaaS和IaaS提供者分别为使用者软件及基础设施服务，基础设施服务通常包括CPU、存储空间和网络等服务。服务组合为使用者提供组合服务，组合服务是指由不同SaaS和IaaS提供方提供的多种服务的组合。服务组合层直接作用于SaaS层，并通过SaaS层间接作用于IaaS层，因为若要使用CPU、存储空间和网络等服务资源，必须通过相应的软件接口。

Figure 1 Architecture of cloud service composition图1 云服务组合架构

4 问题描述

单个服务无法满足复杂应用需求，故需要通过上述云服务组合架构为用户提供组合应用。如图2所示，该应用包含对应于各个任务的抽象SaaS，同时需要由IaaS提供方提供CPU、网络和存储等服务资源。CPU服务主要用于数据计算，存储服务用于保存中间数据结果，网络服务用于传输数据。

对于任务Tk所需的软件服务有众多候选SaaS提供者Sk={Sk1，Sk2,…}，还有候选IaaS提供者S={S1,S2,…}可以提供基础设施服务，因此可以形成多个组合方案。例如，一种备选组合方案Plan={Si,S1i,S2i,S3i,…}，由Si提供IaaS，各任务所需的SaaS服务分别由S1i、S2i、S3i、……提供。

考虑到用户对应用的QoS需求是随时变化的，服务提供方所提供的服务所满足的QoS约束也是随时变化的，因此，需将该系统提供的QoS服务转化为基于时间的服务序列并存储，然后将用户的QoS需求也转化为基于时间的请求序列。将上述两种序列进行对比，相似度最大的时间序列所对应的组合服务就是问题的最优解。

Figure 2 Application on the cloud service composition architecture图2 云服务组合架构上的应用

5 时间序列建模

时间序列是按照时间顺序取得的一系列观测值，能够体现观测值不断随时间变化的过程，表示为Xi(t)=[i=1,2,…,n;t=1,2,…,m]，当n=1时称为一元时间序列，当n≥2时表示多元时间序列MTS(Multiple Time Series)。用户QoS需求是时时变化的，服务提供方提供的服务所满足的QoS约束也是随时间而变化的。因此，需将提供的QoS服务转化为基于时间的服务序列并存储，然后将用户的QoS需求也转化为基于时间的请求序列。

QoS偏好因素建模成时间序列MTS={Q1,Q2,Q3,…,Qm}。该序列的一元Qi={Vi1，Vi2，…,Vin}对应一种QoS因素，m是因素个数，Vij代表因素i在时刻tj的值，n是时间序列长度。组合型服务的QoS偏好所对应的时间序列中，Vij由各个服务的相应值聚合形成。将QoS偏好建模成时间序列的基本步骤如下：

(1)设定QoS偏好因素的类型，如流通量(Throughput)、信誉度(Reputation)、价格(Cost)等等；

(2)设定QoS偏好因素变化的一系列时间点(t=t1,t2,t3,t4,…)；

(3)获取QoS偏好在不同时间点的值，并按照时间顺序表示成一元/多元时间序列。

建模完成后，服务组合问题就转化成了时间序列的相似度比较，目标是找到与用户请求序列最为相似的服务时间序列。

6 时间序列相似度对比

6.1 欧几里得距离

欧几里得距离即欧几里得度量。欧几里得度量(Euclidean Metric)是一个常用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度(即该点到原点的距离)。在二维和三维空间中的欧几里得距离就是两点之间的实际距离。

二维空间的欧几里得距离计算公式为：

(1)

三维空间的欧几里得距离计算公式为:

(2)

以此类推，序列长度为n、包含m个QoS指标的两个多元时间序列MTS1={a11,a12,…,a1m;a21,a22,…,a2m;…；an1,an2,…,anm}和MTS2={b11,b12,…,b1m;b21,b22,…,b2m;…；bn1,bn2,…,bnm}相似度对比的欧几里得距离计算公式为：

(3)

6.2 扩展Frobenius范数距离

m×n维度矩阵A的Frobenius范数为：

(4)

矩阵A的扩展Frobenius范数为：

(5)

其中，wij表示第i列对应权重。

两个矩阵A=[a1,a2,…,an]，B=[b1,b2,…,bn]，ai和bi分别表示A和B的单位正交向量，θi是向量ai和bi间的夹角，则矩阵C=A-B的扩展Frobenius范数是：

(6)

假定两个多元时间序列MA和MB均为m×n维矩阵。求得其对应的协方差矩阵是A′和B′，再通过奇异值分解(SVD)得到相应的特征向量矩阵VA′=[a1,a2,…,an]和VB′=[b1,b2,…,bn]，则这两个MTS间的扩展Frobenius范数距离为：

(7)

为了方便计算，扩展Frobenius范数(相似度)也可以定义为：

(8)

因此，两个MTS具有较大DEros(MA′,MB′,W)就有较小的Eros，代表它们的相似度低；否则，这两个MTS越相似。

假定已对所有的MTS进行了主成分分析，抽取出了前K个主成分，对应的权重系数向量wii也已获得，则两个MTS间的扩展Frobenius范数距离为：

(9)

6.3 主成分分析

QoS因素及其联系是复杂的，穷举性的对比是非常耗时的过程，故用主程序分析进行序列的降维操作，以此提取出互不相干的若干维数据成分替代原序列。

主成分分析过程：

(1)标准化：不同QoS指标有不同量纲，标准化可消除量纲差异；

(2)求协方差矩阵；

(3)奇异值分解，获取特征值和特征向量；

(4)计算权向量，并保留K个主成分及其特征值和特征向量。

7 实验结果与分析

本文在VS及Matlab环境下进行了一系列实验，以此评估二维和多维时间序列相似度对比方法的时间性能及准确性。

(1)二维时间序列相似度对比。

用欧几里得距离和扩展Frobenius范数距离度量二维时间序列的相似度，并进行准确性对比。为保证实验结果的真实可靠性，选取的数据来源于ZhengZi-bin等多位学者专家研究提供的开放WebService数据集。实验过程如下：

第1步数据抽取。从数据源中按序抽取格式为IntervalIDWebServiceID esponse-time hroughput、时间序列长度为142，分别包含五种服务类型及其QoS指标的请求数据集query和包含30种服务及其QoS指标的数据集link。

第2步数据处理和变换。将两个数据集中的数据按照WebServiceID提取出对应的QoS时间序列，格式为WebServiceIDIntervalID esponse-time hrougput，并将link数据集的服务分为五组，每组中的六个服务可提供相同功能，例如，0～5号服务可以满足请求服务类型0,6～11号服务可以满足请求服务类型1，以此类推。

第3步用欧几里得距离度量时间序列相似度，以选取最接近请求序列的服务组合。

第4步用扩展Frobenius范数距离度量时间序列相似度。可以改变两个QoS指标的权重，以选取最接近请求序列的服务组合。

实验结果如表1所示，结果的格式为服务编号/距离,而0.1/0.9表示response-time/througput的权重比率。

由实验结果可知，采用扩展Frobenius范数距离度量相似度在准确性上更有优势，原因有以下两点：①QoS权重比率会影响实验结果，采用不同QoS权重比率可以获得不同的实验结果，通过改变QoS权重比率、多次测试取得最频繁出现的结果会更准确。②扩展Frobenius范数距离度量相似度会考虑不同QoS向量的夹角，使计算结果更精准。

(2)多维时间序列相似度对比。

用基于主成分分析的扩展Frobenius范数距离(MTS算法)和欧几里得距离(TSG算法)、Brute-Force等方法度量多维时间序列的相似度，并进行了时间性能的比较。其中，Brute-Force算法通过穷举计算所有QoS因素对的距离进行相似度对比。

多维时间序列的相似度对比的目的是进行时间性能的对比，故数据集采用随机生成方式，并将每一类QoS指标的测量结果值限定在一定范围内。首先随机生成较大的用于比较的数据集表示服务提供方的服务所满足的QoS，然后生成较小的MTS数据集用以代表用户的QoS偏好请求，建模的MTS范例如表2所示。

Table 2 MTS sample(part)表2 MTS范例(部分)

用平均时间消耗进行算法比较，通过不断改变数据集的大小计算各算法平均时间消耗(单位s)，对比结果如表3所示。由表3可知，基于主成分分析的扩展Frobenius范数距离(MTS算法)的时间性能明显优于基于主成分分析的欧几里得距离(TSG算法)和Brute-Force(BF)算法，也即说明了基于

主成分分析的扩展Frobenius范数距离度量相似度的时间优越性。

Table 3 Comparison of algorithms’ time performance表3 算法的时间性能对比

8 结束语

本文研究基于时间序列的感知QoS的云服务组合，将服务的QoS偏好随时间不断变化的过程纳入云服务组合的研究范围，将云服务组合建模成时间序列的相似度对比问题，继而通过时间序列相似度的比较找寻符合用户需求的组合型云服务。一系列实验结果验证了扩展Frobenius范数距离度量相似度在时间和准确性上的优越性。以后的研究工作可从以下几点进行：(1)本文建立了时间序列模型，但进行相信度对比的两个时间序列的维度和时间间隔均一致，故略显简单和粗糙，可以考虑建立更为复杂且贴切的时间序列模型；(2)时间序列的比较可以包含时间序列的预测，进而筛选出更适合的组合服务以满足用户的未来需求；(3)本文所研究的云服务组合仅考虑服务的QoS需求，可以进一步将服务的功能性及事务性需求纳入服务组合的因素范围。

[1] Strunk A. QoS-aware service composition:A survey[C]∥Proc of the 2010 8th IEEE European Conference on Web Services(ECOWS’10), 2010:67-74.

[2] Canfora G, Di Penta M, Esposito R, et al. An approach for QoS-aware service composition based on genetic algorithms[C]∥ Proc of the 2005 ACM Conference on Genetic and Evolutionary Computation(GECCO’05), 2005:1069-1075.

[3] Gao C,Cai M,Chen H.QoS-aware service composition based on tree-coded genetic algorithm [C]∥Proc of the 31st IEEE Annual International Computer Software and Applications Conference(COMPSAC),2007:361-367.

Table 1 Comparison of similarity on two-dimensional time series表1 二维时间序列相似度对比结果

[4] Ma Y,Zhang C.Quick convergence of genetic algorithm for QoS-driven web service selection [J]. Computer Networks, 2008,52 (5):1093-1104.

[5] Tang M,Ai L.A hybrid genetic algorithm for the optimal constrained web service selection problem in web service composition[C]∥ Proc of IEEE Congress on Evolutionary Computation, 2010:1-8.

[6] Ai L, Tang M, Fidge C. Partitioning composite web services for decentralized execution using a genetic algorithm [J]. Future Generation Computer Systems, 2011, 27 (2):157-172.

[7] Wu Q, Zhu Q, Li P. A caching mechanism for QoS-aware service composition [J]. Journal of Web Engineering ,2012,11 (2):119-130.

[8] Chen Liang,Sun Min.Web services composition method based on immune genetic algorithm[J]. Computer Engineering, 2010, 36(10):226-230.(in Chinese)

[9] Zheng X,Luo J,Song A.Ant colony system based algorithm for QoS-aware web service selection[C]∥ Proc of the 4th International Conference on Grid Service Engineering and Management( GSEM), 2007:39-50.

[10] Dhore S R, Kharat M. QoS based web services composition using ant colony optimization:Mobile agent approach [J]. International Journal of Advanced Research in Computer and Communication Engineering, 2012, 1(7):519-527.

[11] Zhou Xian-zhong,Wu Kui,Xiao Yi-hong.Automatic web service composition based on any colony algorithm[C]∥Proc of Decision Evaluation and Science, 2009:228-236.(in Chinese)

[12] Shen Ji-quan, Zheng Xue-feng, Tu Xu-yan. An approach to service composition based on ant colony algorithm[J].Journal of Wuhan University of Technology (Transportation Science & Engineering), 2009, 33(6):1179-1182.(in Chinese)

[13] Yin Rong-wang,Mao Zhi-jian.A QoS-guaranteed web service composition[J]. Computer Knowledge and Technology (Network Communication and Security), 2007(11):1276-1278.(in Chinese)

[14] Liu Qing, Zhang Shi-long, Yang Rui, et al. Web service composition with QoS bound based on simulated annealing algorithm[J]. Journal of Southeast University(English Edition),2008,24(3):308-311.

[15] Li Zhen. Research on hybrid QoS-aware semantic web service composition decision making algorithm [D]. Beijing:Beijing University of Posts and Telecommunications, 2008.(in Chinese)

[16] Liu Zhi-zhong, Lei Guan-jun, Xue Xiao, et al. Research on QoS-aware cloud service optimal composition [J]. Application Research of Computers, 2012, 29(10):3919-3921.(in Chinese)

[17] Xu Meng, Cui Li-zhen, Li Qing-zhong. An extend graph-planning based ontop-Kservice composition method[J]. Acta Electronica Sinica, 2012, 40(7):1404-1409.(in Chinese)

[18] Zhen Ye,Bouguettaya A,Zhou Xiao-fang.QoS-aware cloud service composition based on economic models[C]∥Proc of the 10th International Conference on Service-Oriented Computing (ICSOC),2012:111-126.

[19] Zhen Ye,Bouguettaya A,Zhou Xiao-fang.QoS-aware cloud service composition using time series[C]∥Proc of the 11th International Conference on Service-Oriented Computing (ICSOC), 2013:9-22.

[20] Guo Xiao-fang, Li Feng. Analysis on similarity of multivariate time series based on Eros [J]. Computer Engineering and Applications, 2012, 48(23):111-114.(in Chinese)

附中文参考文献：

[8] 陈亮,孙敏.基于免疫遗传算法的Web 服务组合方法[J].计算机工程,2010,36(10):226-230.

[11] 周献中,吴奎,萧毅鸿.基于蚁群算法的Web服务自动组合[C]∥决策科学与评价,2009:228-236.

[12] 沈记全,郑雪峰,涂序彦.一种基于蚁群算法的服务组合方法[J].武汉理工大学学报(交通科学与工程版),2009,33(6):1179-1182.

[13] 殷荣网,冒志建.一种有QoS保障的服务组合方法[J].电脑知识与技术(网络通讯与安全),2007(11):1276-1278.

[15] 李祯.混合QoS模型感知的语义Web服务组合决策算法研究[D].北京：北京邮电大学,2008.

[16] 刘志中,雷冠军,薛霄,等.QoS感知的云服务优化组合研究[J].计算机应用研究,2012, 29(10):3919-3921.

[17] 徐猛,崔立真,李庆忠.基于扩展图规划的top-K服务组合方法研究[J].电子学报,2012,40(7):1404-1409.

[20] 郭小芳,李锋.基于Eros的多元时间序列相似度分析[J].计算机工程与应用,2012,48(23):111-114.

XIAOWen-juan,born in 1991,MS candidate,her research interest includes service computing.

段玉聪(1977),男，河南南阳人，博士后，教授，CCF会员(E200033712M)，研究方向为服务计算。E-mail:duanyucong@hotmail.com

DUANYu-cong,born in 1977,post doctor,professor,CCF member(E200033712M)，his research interest includes service computing.

QoS-awarecloudservicecompositionbasedontimeseries

XIAO Wen-juan，DUAN Yu-cong

(College of Information Science and Technology,Hainan University,Haikou 570228,China)

In this paper, we study QoS-aware cloud service composition based on time series, taking the sustaining change process of service QoS preference into research scope of cloud service composition,and transform the composition of cloud services into similarity comparison problems between time series.Euclidean distance and the extend Frobenius norm distance are used to measure similarity between two-dimensional time series respectively. In the next,the extend Frobenius norm distance or Euclidean distance based on principal component analysis and Brute-Force method are adopted to measure the similarity between multidimensional time series. Experiments show that the extend Frobenius norm distance has better performance on similarity measurement in time and accuracy.

time series;QoS;cloud service composition;similarity comparison

1007-130X(2014)11-2061-06

2014-06-09;

：2014-08-19

国家自然科学基金资助项目(61363007);海南大学资助项目(HDSF201310,kyqd1242)

TP393.027

：A

10.3969/j.issn.1007-130X.2014.11.003