, 张晓红东北大学 计算机科学与工程学院, 辽宁 沈阳 110169
收稿日期：2015-09-16
基金项目：国家科技支撑计划项目 (2014BAI17B00)；国家自然科学基金资助项目 (61572116，61572117，61502089)。
作者简介：马安香 (1979-)，女，辽宁沈阳人，东北大学讲师，博士;
张斌 (1964－)，男，辽宁本溪人，东北大学教授，博士生导师。
摘要：为了准确预测云应用负载以便及时执行云应用自适应优化, 从而保证云应用性能的稳定, 根据云环境下应用负载预测问题的特点, 提出了基于深度置信网络的云应用负载预测方法.首先给出能够有效描述负载数据的显式特征和隐式特征并定义了负载预测模型, 进而给出基于深度置信网络的负载预测算法.对算法进行了分析并在真实数据集上与相关算法进行了比较, 结果表明, 本文提出的方法能够更加有效地解决云应用负载预测问题.
关键词：云计算云应用深度置信网络负载预测自适应优化
Load Prediction Approach for Cloud Application Based on Deep Belief Networks
MA An-xiang, ZHANG Chang-sheng, ZHANG Bin
, ZHANG Xiao-hongSchool of Computer Science & Engineering, Northeastern University, Shenyang 110169, China
Corresponding author: ZHANG Bin, E-mail: zhangbin@mail.neu.edu.cn
Abstract: To implement the adaptive optimization to ensure the performance of cloud application, it is necessary to accurately predict the load for cloud application. According to the feature of load prediction in cloud application, an approach is proposed for load prediction based on deep belief networks. Explicit and implicit features for load data are given. Load prediction model is defined. Then, the algorithm of load prediction based on deep belief networks is designed and implemented. This approach is evaluated and compared with some related load prediction algorithms, which reveals very encouraging results in terms of the prediction quality.
Key Words: cloud computingcloud applicationdeep belief networkload predictionadaptive optimization
随着云应用的复杂化、运行环境的开放化和动态化, 服务系统自优化和自适应能力的重要性日益凸显[1-2].云应用的按需付费模式要求为云应用分配能够满足其所需的资源, 并保持资源代价最小.然而云应用的运行环境具有动态变化的特性, 即云应用负载不断波动, 这将导致在给定的资源部署方案下云应用的性能可能会严重偏离应用服务等级约束 (service level agreement, SLA).准确地预测下一周期云应用负载, 并根据负载变化情况及时执行与之相适应的云应用优化可以有效减少SLA违约并持续提供符合用户预期的服务.因此, 如何准确地预测云应用负载对于保证云应用性能稳定具有重要意义.
目前, 研究者对应用负载预测模型构建问题展开了深入的研究.文献[3-4]提出基于时间序列的负载预测方法, 依赖连续负载信息的测量和捕获, 采用线性时间序列模型对负载进行短期的预测.文献[5]提出基于人工神经网络的负载预测算法, 定义了描述负载预测问题的特征, 进而结合人工神经网络和线性回归技术预测负载.文献[6-7]提出基于滤波理论的预测算法, 应用电子或动力学的滤波理论预测负载.文献[8-9]提出基于排队论模型的负载预测方法, 根据服务的CPU需求、I/O需求, 利用开放式排队网络分析预测在线负载; 文献[10]在获取用户和组件服务特征的基础上, 利用协同过滤思想预测应用并发量.从目前的研究可以看出, 在分析预测应用负载时, 主要是利用时间序列分析、人工神经网络、排队论、协同过滤等方法.基于时间序列分析、人工神经网络的负载预测方法, 通常根据历史负载数据建立负载预测模型, 而历史负载数据所隐含的特征并未得到充分分析, 使得负载预测模型的准确率难以提升; 基于排队论和协同过滤的负载预测方法一般需要先对数据进行一定的抽象和假设, 而实际的负载数据并不完全符合假定的模型, 使得相应的负载预测模型的可用性受到影响.
云应用用户访问的随机性导致应用负载不断波动, 仅靠负载信息本身无法描述负载信息的变化情况; 因此, 本文从负载信息本身、负载变化程度和负载变化速度三方面描述负载数据的显式特征, 利用云应用中组件服务的平均CPU利用率描述负载数据的隐式特征, 以解决单一负载信息本身无法全面刻画云应用负载数据特征的问题.深度学习[11]方法能够有效用于解决具有隐性依赖特征的多因素时间序列预测问题, 因此, 提出基于深度学习的云应用负载预测方法；定义了云应用负载预测模型, 给出基于深度学习的云应用负载预测过程, 进而给出基于深度学习的负载预测算法.
1 深度置信网络深度置信网络 (deep belief network, DBN) 是由Hinton等人提出的具有多个隐藏层的无监督学习模型, 已经被成功地应用于解决许多问题, 如分类[12]和降维[13]问题.DBN网络结构是由多个受限玻尔兹曼机 (restricted Boltzmann machine, RBM) 累加构成的, 采用无监督贪婪逐层优化算法学习网络模型[14].DBN的基本思想是采用无监督学习方法逐层训练每一个RBM, 最后对整个网络采用有监督学习进行微调.一个受限玻尔兹曼机RBM是两层的神经网络, 使用对称的加权连接来联系输入单元和输出单元.RBM模型定义了输入单元v、隐单元h和能量函数E的概率分布, 计算公式如下:
 | (1) |
 | (2) |
 | (3) |
2 基于DBN的云应用负载预测机制2.1 云应用负载预测模型云应用负载预测模型描述的是负载历史数据的特征与负载预测值的对应关系, 因此如何有效描述负载数据的特征是构建负载预测模型的关键.云应用的负载历史数据是负载预测问题的基础, 同时云应用中的各组件服务CPU利用率可间接反映云应用的负载变化情况, 因此可从负载数据本身所蕴含的信息及组件服务CPU利用率两方面来描述负载数据的特征.
负载数据的特征分为显式特征和隐式特征.
显式特征包括负载观测值、负载变化程度和负载变化速度.以两个相邻负载观测值之差作为负载的一阶差分值, 用来描述负载的变化程度; 以两个相邻一阶负载值之差作为负载的二阶差分值, 用来描述负载的变化速度.负载观测值序列记为L1, L2, …, Li, Li+1, …, Ln, 则负载变化程度记为{Yi|Yi=Li+1-Li, i=1, 2, …, n-1}, 负载变化速度记为{Ei|Ei=Yi+1-Yi, i=1, 2, …, n-2}.
隐式特征是云应用中组件服务的平均CPU利用率.设云应用中包含m个组件服务si(i=1, 2, …, m), 对应的CPU利用率为ci(i=1, 2, …, m), 则平均CPU利用率为
负载预测问题的输入数据是过去滞后的负载观测值、负载的一阶差分值、负载的二阶差分值和组件服务的平均CPU利用率, 输出是未来负载预测值.依时间序列, 每个输入样本由一个可移动的固定长度的窗口组成.假设L1, L2, …, Ln是训练数据过去n个周期的负载观测值; Y1, Y2, …, Yn-1是训练数据过去n个周期负载的一阶差分值; E1, E2, …, En-2是训练数据过去n个周期负载的二阶差分值; C1, C2, …, Cn是云应用中各组件服务的平均CPU利用率.每一个训练样本数据由一个具有p个周期负载观测值、p-1个负载的一阶差分值、p-2个负载的二阶差分值和p个组件服务的平均CPU利用率作为输入，以及一个周期负载观测值作为输出, 总共有n-p个训练样本数据.依此给出训练数据集的定义.
定义1?训练数据集 (training data sets, TDS).TDS是记录输入与输出的集合, 表示为
通过对负载训练数据集的学习, 可获得负载历史数据特征与负载预测值的映射关系模型.
定义2?负载预测模型 (load prediction model, LPM).LPM是描述前p个周期负载历史数据特征Fp与第p+1个周期负载预测值Lp+1之间映射关系的模型, 表示为Ψ:Fp→Lp+1, 其中, Fp=〈L, Y, E, C〉; L表示云应用的前p个周期负载历史观测值, Y表示L对应的负载一阶差分值, E表示L对应的负载二阶差分值, C表示云应用的前p个周期组件服务的平均CPU利用率.
2.2 负载预测机制根据云应用负载预测问题的特点, 本文采用DBN和有监督学习相结合的方式构建深度预测模型.该模型在逻辑上分为两层, 底层利用DBN进行无监督特征学习以抽取和选择代表性特征作为顶层的输入, 本文采用实值RBM; 顶层利用有监督学习的BP神经网络进行预测.
基于DBN的云应用负载预测主要包括两个阶段:负载预测模型训练和云应用负载预测.
负载预测模型训练阶段主要包括训练数据集获取和模型训练两部分.在训练数据获取阶段, 以半个小时为一个周期, 统计n个周期云应用的负载, 并根据定义1构建训练样本数据集.
在负载预测模型训练阶段, 首先设置网络参数, 包括迭代训练的次数、学习的速率、DBN的层数等; 其次, 确定RBM学习算法, 求出网络权值和隐层偏差, 以拟合给定的训练数据, 采用随机最大化似然方法, 这是一种持续对比散度算法; 最后训练基于DBN的负载预测模型, 主要分为三步:第一步, 分别单独无监督地训练每一层RBM网络, 确保特征向量映射到不同特征空间时都尽可能多地保留特征信息; 第二步, 在DBN的最后一层接收RBM的输出特征向量作为它的输入特征向量, 有监督地训练BP神经网络来解决回归问题; 第三步, 再一次自底向上训练隐层的状态, 更新网络权值和隐层偏差.迭代至规定的次数, 得到DBN的各个参数.
在云应用负载预测阶段, 首先根据训练数据集的定义构造待预测数据集的输入特征; 然后将该特征在基于DBN的负载预测模型中正向传播, 获得下一周期云应用的负载.
3 负载预测算法基于DBN的云应用负载预测模型构建算法的伪代码描述如下.
Function: LoadPredictionModelofDBN ()
Input:
trnX: The training input data sets.
trnY: The training output data sets.
epoch: The current iteration number.
maxepoch: The maximum number of iteration.
eta: The learning rate.
numhid: The number of hidden layer unit.
H: The number of hidden layer.
Output:
model.W, model.b, model.c, model.Wc, model.top, model.labels, model.cc: The connection weight, hidden layer deviation, visible layer deviation, label layer weight, hidden layer value, label layer value and label layer deviation of DBN model.
errsum: The establishing error of each iteration.
Begin
1.? H←length (numhid) //calculate the number of hidden layer
2.? for cycle=1:H do
3.??if cycle==1 then //train the first RBM on data
4.??? for epoch=1:maxepoch do
5.????model{1}.W, model{1}.b, model{1}.c, model{1}.top, errsum←rbmGB (trnX, numhid (1))
6.??? endfor
7.??elseif cycle==H then
8.???for epoch=1:maxepoch do
9.??? model{H}.W, model{H}.b, model{H}.c,
??? model{H}.Wc, model{H}.cc,
??? model{H}.labels,
??? errsum←rbmFit (model{H-1}.top,
??? numhid (H), trnY)
10.?? endfor
11.??else // train all other RBM
12.?? for epoch=1:maxepoch do
13.?? model{cycle}.W, model{cycle}.b, model{cycle}.c, model{cycle}.top, errsum← rbmBB (model{cycle-1}.top, numhid (cycle))
14.?? endfor
15. endif
16. endfor
17. Output models
End
4 实验以实验小组设计的基于组件的景点语音导航云应用系统为实验平台, 验证提出的基于DBN的负载预测方法的性能.
4.1 实验环境基于组件的景点语音导航云应用系统是一个根据一定业务逻辑由多个组件服务构成的面向移动终端的智能旅游应用, 其流程结构如图 1所示.该应用系统共包含8个组件S1~S8.
图 1(Fig. 1)
 | 图 1 景点语音导航系统的业务流程Fig.1 Work flow of voice navigation system to attractions |
实验采用两台惠普Z820工作站搭建系统, 每台工作站上初始部署两台KVM虚拟机, 每台虚拟机初始部署的CPU资源、内存资源和磁盘资源均相同, 记为〈2, 2 G, 50 G〉, 每台虚拟机部署两个服务.
4.2 实验结果及分析学习的速率η=0.02, 最大训练代数θ=60, 权值衰减系数ψ=2e-4; 在本文中, DBN的输入层节点数、隐藏层的层数以及每层的隐藏节点数通过下面的实验确定.
实验中, 隐藏层的候选取值范围为2~8, 输入层节点数的候选取值范围为1~10, 隐藏层的节点数从集合N={4, 8, 16, 32, 64, 128, 256}中选择.采用随机交叉验证法确定最优参数:首先, 从可能的集合中随机选择每一个参数; 然后, 依据1 000次随机运行的平均结果选择最优的参数配置.本文使用平均绝对百分比误差 (mean absolute percentage error, MAPE) 作为评价指标, 它可以通过以下公式计算得到:
 | (4) |
首先, 研究隐藏层层数对构建DBN的影响, 包括云应用负载预测的MAPE和构建DBN的时间代价t, 结果如表 1所示.
表 1(Table 1)
 表 1 隐藏层数的影响Table 1 Effect of the number of hidden layers
| 表 1 隐藏层数的影响 Table 1 Effect of the number of hidden layers |
从表 1可知, 隐藏层层数为3时, MAPE最小.隐藏层节点数对构建DBN的影响见表 2.
表 2(Table 2)
表 2 隐藏层节点数的影响Table 2 Effect of the number of nodes in the hidden layers
| 表 2 隐藏层节点数的影响 Table 2 Effect of the number of nodes in the hidden layers | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
从表 2可以看出, 当第1层隐藏层的节点数为128、第2层隐藏层的节点数为32、第3层隐藏层的节点数为16时, 云应用负载预测的MAPE最低.
输入层节点数取决于训练数据中负载序列长度值, 即定义1中的p值, 因此研究输入层节点数对构建DBN的影响可通过p值对构建DBN的影响来完成, 实验结果如图 2所示, MAPE的最小值出现在p值为8时.
图 2(Fig. 2)
 | 图 2 输入层节点数的影响Fig.2 Effect of the number of nodes in the input layer |
确定DBN的结构以后, 将本文的负载预测算法与时间序列分析方法[4]以及卡尔曼滤波方法[7]进行性能对比.用实际负载值与预测负载值之差作为预测方法的相对误差, 三种预测方法的相对误差结果如图 3所示.
图 3(Fig. 3)
 | 图 3 多种预测方法的预测误差Fig.3 Prediction errors with various prediction methods |
从图 3可以看出, 使用DBN预测云应用负载的相对误差更接近于0, 小于使用时间序列分析方法和卡尔曼滤波方法预测云应用负载的相对误差; 卡尔曼滤波方法的相对误差小于使用时间序列分析方法预测云应用负载的相对误差.
综上, 对于同一组观测值, 基于DBN的云应用负载预测方法具有较高的精度.
5 结语本文针对云环境中应用负载预测问题, 提出了一种基于深度置信网络的负载预测方法.给出了能够有效描述云应用负载数据的显式特征和隐式特征, 定义了云应用负载预测模型, 并给出了基于深度置信网络的云应用负载预测算法.对比实验表明该方法具有较好的性能.本文的负载预测模型目前仅考虑了一种负载隐式特征, 在下一步工作中将会增加一些其他因素, 如云应用网络环境状态等, 从而进一步提高负载预测模型的性能.
参考文献
| [1] | 丁博, 王怀民, 史殿习. 构造具备自适应能力的软件[J].软件学报, 2013, 24(9): 1981–2000. ( Ding Bo, Wang Huai-min, Shi Dian-xi. Constructing software with self-adaptability[J].Journal of Software, 2013, 24(9): 1981–2000.) |
| [2] | Frederico D, Jose C, Anderson F, et al. A systematic review on cloud computing[J].The Journal of Supercomputing, 2014, 68(3): 1321–1346.DOI:10.1007/s11227-014-1089-x |
| [3] | Dinda P A, O'Hallaron D R.An evaluation of linear models for host load prediction[C]//Proceedings of the 8th International Symposium on High Performance Distributed Computing.New York:IEEE, 1999:87-96. |
| [4] | Van Den Bossche R, Vanmechelen K, Broeckhove J.Optimizing IaaS reserved contract procurement using load prediction[C]//The 7th International Conference on Cloud Computing.New York:IEEE, 2014:88-95. |
| [5] | Islam S, Keung J, Lee K, et al. Empirical prediction models for adaptive resource provisioning in the cloud[J].Future Generation Computer Systems, 2012, 28(1): 155–162.DOI:10.1016/j.future.2011.05.027 |
| [6] | 许建峰, 朱晴波, 胡宁, 等. 分布式实时系统中的预测调度算法[J].软件学报, 2000, 11(1): 95–103. ( Xu Jian-feng, Zhu Qing-bo, Hu Ning, et al. Predicting allocation algorithm in distributed real-time systems[J].Journal of Software, 2000, 11(1): 95–103.) |
| [7] | Ali N H, Hassan G M. Kalman filter tracking[J].International Journal of Computer Applications, 2014, 89(9): 15–18.DOI:10.5120/15530-4315 |
| [8] | Xiong K Q, Perros H.Service performance and analysis in cloud computing[C]//Proceedings of the IEEE Congress on Services.New York:IEEE, 2009:693-700. |
| [9] | Bennani M N, Menasce D A.Resource allocation for autonomic data centers using analytic performance models[C]//Second International Conference on Autonomic Computing.New York:IEEE, 2005:229-240. |
| [10] | Zhang Y L, Zheng Z B, Lyu M R.Real-time performance prediction for cloud components[C]//The IEEE 15th International Symposium on Component Real Time Distributed Computing Workshops.New York:IEEE, 2012:106-111. |
| [11] | Li D. A tutorial survey of architectures, algorithms, and applications for deep learning[J].APSIPA Transactions on Signal and Information Processing, 2014, 3(1): 1–29. |
| [12] | Sun S, Liu F, Liu J, et al.Web classification using deep belief networks[C]//Proceedings of the IEEE 17th International Conference on Computational Science and Engineering.New York:IEEE, 2014:768-773. |
| [13] | Hinton G, Salakhutdinov R. Reducing the dimensionality of data with neural networks[J].Science, 2006, 313(5786): 504–507.DOI:10.1126/science.1127647 |
| [14] | Hinton G, Osindero S, Teh Y. A fast learning algorithm for deep belief nets[J].Neural Computation, 2006, 18(7): 1527–1554.DOI:10.1162/neco.2006.18.7.1527 |
