基于多步优化GM（1，1）模型的云计算资源负荷短期预测

张 磊，徐达宇

ZHANG Lei1,XU Dayu2

1.安徽工商职业学院 网络中心，合肥 230009

2.合肥工业大学 过程优化与智能决策教育部重点实验室，合肥 230009

1.Network Centre,Anhui Business Vocational College,Hefei 230009,China

2.Optimization and Intelligent Decision Making,Ministry of Education Key Laboratory of Process,Hefei University of Technology,Hefei 230009,China

1 引言

云计算以承诺向用户提供具有高可扩展性、灵活性和成本效益的计算、存储及其他各类应用服务而受到业界的广泛关注。为了实现这些承诺，云计算服务提供商不仅需要通过构建完善的基础设施、采取迅速有效的管理机制对资源进行规划以提供高质量服务来满足用户需求，同时还需要控制成本、提高利润来谋求自身的长期发展，而云计算数据中心能源消耗所产生的费用是运营成本中一个主要的构成部分。

云计算环境下的资源负荷预测是实现云计算海量异构资源有效管理以应对动态且不确定的多元化用户需求，保证及时、可靠地将各种资源提供给使用者的同时降低运营商、服务供应商自身的成本，以及减少数据中心能源消耗过程中重要的一步[1]。利用历史数据对未来一段时间内资源负荷进行准确的预测，就可以运用服务器运行机制（例如服务器开/关、休眠/挂起）、虚拟化技术（例如虚拟机迁移）和相应的负载均衡策略来实现整个云计算系统资源的合理配置，并为云计算运营商和服务供应商提供有力的决策支持。在先前的云计算资源负荷预测研究中，相关学者使用了如自回归模型（Auto-Regression，AR）[2]、模式匹配[3]、神经网络[4-5]、贝叶斯模型[6]等预测方法。然而，云计算系统是受多种因素影响的复杂非线性系统，其资源负荷也相应地表现出强烈的动态性，以上文献中所提的预测方法都只是简单地使用了传统预测模型展开实验，并未在对云计算资源负荷特征分析的基础上进行对应的预测模型选择和构建；并且单一的预测模型难以准确描述云计算资源负荷复杂的内部变化规律，不能及时调整模型参数以反映外部环境因素发生的变化。文献[7-9]分析了云计算资源负荷的特征，并在资源使用率、任务执行时间、资源请求内容等几个方面与网格计算（Grid Computing）及其他高性能计算（High Performance Computing，HPC）系统进行了全面地比较。本文在这些研究的基础上总结了云计算资源负荷的几个主要特点：（1）大部分云计算中的任务具有较短的执行时间。75%至80%的任务执行时间在3分钟左右；（2）云计算中的每个任务对资源的需求是少量的。大部分单个任务使用的资源约占一台机器总资源量的2.5%。（3）相比于网格计算和其他HPC系统，云计算资源负荷表现出较高的噪声，具有短期内频繁变化的特点。以上这些云计算资源负荷特点决定了其预测模型需要有较强的非线性拟合能力和自适应的模型参数调整能力来不断适应负荷的动态性。

基于以上论述，本文将重点放于云计算资源负荷的短期预测研究中，短期负荷要求模型能够尽可能使用较少的数据量、较短的预测时间去获得准确的预测结果，从而能够及时地为云计算的资源合理配置和调度提供可靠的决策支持，目的是为了能够更有效地对云计算资源进行实时控制和管理，保障云计算系统的稳定运行及其资源的高效供应，保证对云计算用户提供可靠的服务。本文结合云计算资源负荷特点，阐述了GM（1，1）灰色模型在预测性能上的优劣，提出基于多项式回归模型、马尔科夫链和布谷鸟搜索算法多步优化的GM（1，1）预测模型，并将该模型用于云计算环境下资源负荷的短期预测应用中去，也是对GM（1，1）灰色模型的应用范围作进一步的推广。实验结果表明，相比于其他传统时间序列预测模型，本文所建模型具有更高的预测精度，体现出良好的预测性能，适合对具有较强动态性和非线性的云计算资源负荷进行短期预测。

2 基于多步优化的GM（1，1）预测模型

自20世纪80年代我国学者邓聚龙教授[10]创立灰色系统理论以来，灰色系统预测方法得到了国内外学者的广泛关注。其中GM（1，1）模型因其计算简便、应用广泛而在灰色预测中占有重要地位，是运用最早也是迄今为止应用最为广泛的灰色模型，它以部分信息已知、部分信息未知的不确定性系统为研究对象，通过对已知信息的生成、开发，提取有价值的信息，实现对系统运行行为、演化规律的正确描述和有效监控。其建模不依赖于原始数据的分布信息，而是运用累加生成的方法使得序列呈现出整体的灰指数规律，在此基础上构建灰色微分方程并求解。灰色模型不需要大样本数据就能建模预测，且建模过程简单、算法复杂度低，并被证明在短期预测中具有独特的优势[11]。因而，GM（1，1）模型被广泛地用于国民经济的各个领域[12-14]。但是，和其他预测方法一样，GM（1，1）模型也存在一定的局限性，它对非负光滑单调序列的预测精度较高，而对非线性动态振荡序列的预测效果并不理想[15]。因此，为了GM（1，1）模型能更好地应对云计算资源负荷时间序列的预测问题，本文将在阐述GM（1，1）预测模型建模机理的基础上，构建基于多步优化的GM（1，1）灰色预测模型。

2.1 GM（1，1）灰色模型介绍

GM（1，1）灰色预测模型的建模机理如下：设原始序列 为，其 中，。对原始序列进行一次累加得到一组新序列，其中模型的白化微分方程式为：

GM（1，1）模型的差分形式（灰微分方程）为：

从而得出灰色预测公式为：

2.2 P-GM（1，1）模型

其中 βi(i=0，1，2，3)为多项式系数，可由最小二乘法计算出各系数值：

其中，

在确定各系数值后，就可用所建的P-GM（1，1）模型计算得到一组新的预测序列来代替原有的预测序列，并且该组新预测序列会比GM（1，1）预测得到的值更接近实际值。

2.3 MP-GM（1，1）模型

经过三次多项式回归优化后的GM（1，1）模型P-GM（1，1）在预测精度上有了一定的提高，但与实际值依然存在一定的误差，从而形成一个残差序列。因此，在P-GM（1，1）模型拟合结果的基础上，本文利用适合于预测具有较强随机性和波动性数据的马尔科夫链（Markov chain）对P-GM（1，1）模型进行再次改进以进一步提升本文所建模型对于动态云计算负荷时间序列的拟合能力，构建MP-GM（1，1）模型，再次提高云计算资源负荷的预测精度。运用马尔科夫预测法进行预测，主要工作原理是利用初始状态的概率向量和状态转移矩阵来推测预测对象未来某一时间所处的状态。由实际序列及P-GM（1，1）拟合结果可以得到一组残差序列e(i)。其中，

根据残差序列值e(i)的最大、最小值，将残差序列分为S种状态，每种状态代表相应的误差区间（每个区间的误差长度相同），这样就可以获得一个S×S的马尔科夫状态转移概率矩阵，而每个预测误差都可定位在相应的状态中。用表示预测对象从状态i经过m步转移至状态 j的概率，则m步转移概率为：

用as(t)表示第t个时期预测对象处于状态s的概率，则{as(t)，s=1，2，…，S}称为第 t个时期的状态转移向量。设初始的状态转移概率向量为as(0)，利用初始的状态转移概率向量as(0)和一步状态转移矩阵P(1)，可以求出预测对象在任一时间处于任一状态的概率向量。从而得到基于马尔科夫链优化的P-GM（1，1）预测模型：

其中，as(t)=[a1(t)，a2(t)，…，as(t)]=as(t-1)P(1)，为处于特定误差区间范围内的一个灰数，即，ls和us分别为状态s所对应误差区间的下限和上限。

2.4 CMP-GM（1，1）模型

在等式（12）中，若要获得基于MP-GM（1，1）模型的预测结果，就需要确定灰数的值，即需要将灰数白化。根据文献[14]所述，灰数的白化方法为：

其中λs∈[0，1]。从而可将等式（12）改写为：

由等式（14）可知，只要确定向量 [λ1，λ2，…，λS]的值，就可以利用MP-GM（1，1）模型来进行云计算资源负荷短期预测。因此，本文利用布谷鸟搜索算法（Cuckoo Search，CS）来确定向量 [λ1，λ2，…，λS]的最优值，提出基于布谷鸟搜索算法的MP-GM（1，1）预测模型—CMPGM（1，1）预测模型。接下来首先介绍布谷鸟搜索算法的基本原理与算法流程。

2.4.1 布谷鸟搜索算法

2009年，Yang和Deb模拟布谷鸟的寻窝产卵行为，提出一种新的智能优化算法——布谷鸟搜索算法[16]。这种算法主要基于布谷鸟的巢寄生繁殖机理和莱维飞行（Levy flights）搜索原理两个方面，它模拟了布谷鸟寻找鸟窝的随机搜索方式，并模拟出布谷鸟的卵被鸟窝主人发现后的进一步随机搜索过程[17]。在文献[18]中，将布谷鸟搜索算法与粒子群算法、差分进化算法和人工蜂群算法进行了全面的比较，论证了布谷鸟搜索算法在获取全局优化值方面具有优良的性能。把布谷鸟寻窝的方式形成理论，需假定以下3个理想状态：（1）布谷鸟一次只产一个卵，并随机选择鸟窝来孵化它；（2）在随机选择的一组鸟窝中，最好的鸟窝将会被保留到下一代；（3）可利用的鸟窝数量是固定的，一个鸟窝的主人能发现一个外来鸟蛋的概率为 pα∈[0，1]。在这三个理想状态下，布谷鸟算法的基本步骤为：

步骤1 随机产生 S 维向量λ=(λ1，λ2，…，λS)，设定目标函数 f(E)，生成 n个鸟窝位置λi（i=1，2，…，n），设置算法参数。

步骤2计算每个鸟窝的目标函数值，并记录当前的最优解。

步骤3保留上代最优鸟窝位置，并按位置更新公式对其他鸟窝位置进行更新。其中位置更新方式遵循莱维飞行，公式为：

其中，α为步长控制量，α＞0;⊙为点对点乘法；Levy(ε)为随机搜索路径，服从Levy分布：

步骤4产生服从均匀分布的随机数r∈[0，1]，与布谷鸟的卵被鸟窝主人发现的概率 pα对比，若 r＞pα，则对进行随机改变，反之不变。再对改变后的鸟窝进行测试，与上一步得到的一组鸟窝位置比较取对应测试值较好的鸟窝位置，并选出当代的全局最优位置。

步骤5判断是否满足结束要求。若满足，输出结果；若未满足，则返回步骤2。

2.4.2 基于CS算法优化的MP-GM（1，1）模型

在阐述了CS算法基本原理与算法流程的基础上，针对本文云计算资源负荷短期预测的实际应用情况，构建基于CS算法优化的MP-GM（1，1）模型—CMP-GM（1，1）预测模型，即通过CS算法不断搜索最优的参数设置来使得本文所提模型对动态的云计算负荷具有良好的自适应能力，下面给出算法流程。

步骤2 利用布谷鸟搜索算法更新向量[λ1,λ2,…，λS]的值，使得目标函数 f(E)不断逼近其全局最小值。

步骤3检测算法停止条件，若不满足，返回步骤2；若满足，则输出最优的λs值，s=1，2，…，S 。

步骤4 运用等式（14），计算出基于CMP-GM（1，1）模型的最优云计算资源负荷短期预测序列。

在上文论述了基于布谷鸟搜索优化的MP-GM（1，1）算法流程的基础上，下面给出本文所建的基于多步优化GM（1，1）灰色预测模型CMP-GM（1，1）算法的伪代码：

至此，基于多步优化的GM（1，1）灰色预测模型CMP-GM（1，1）已构建完毕。

3 实验及结果分析

本文所用实验数据来自NASA和Clarknet[19]，该数据详细记录了每秒钟两个数据中心接收到的服务请求内容，其资源负荷如引言中所述具有很强的动态非线性性，在[5，20，21]等文献中已被多次用于云计算负荷预测及其性能分析研究。在云计算实际的资源管理过程中，每5至10分钟会实施一次资源重新调度和配置的过程[4，22]。因此，本文中将对两个数据中心提取的数据以10分钟为最小单位进行统计，即每天记录的数据点为144个，以此获得相应的历史资源负荷时间序列数据，并利用前三天的资源负荷数据对未来六小时（36个数据点）的云计算资源负荷进行短期预测，使预测结果能够为云计算资源实现有效的实时配置和调度起到决策支持作用。为了对所建模型在预测性能进行客观的评价和比较，本文选择以绝对平均百分比误差（AMPE）、均方根误差（RMSE）和平均绝对误差（MAE）这三个指标作为衡量预测性能是否优良的评价指标。它们的计算公式为：

在实验过程中，首先利用GM（1，1）模型对历史数据进行第一步拟合，然后再通过P-GM（1，1）模型对获得的数据拟合结果进行优化，结果如图1所示。

图1（a） 基于P-GM(1,1)模型的NASA数据拟合结果

图1（b） 基于P-GM（1，1）模型的Clarknet数据拟合结果

由图1可以看出，云计算环境下的资源负荷时间序列具有极强的动态性，虽然P-GM（1，1）模型能够拟合出数据整体的发展趋势，但对于单个数据点的拟合结果并不是很理想。因而，在获得P-GM（1，1）模型拟合结果的基础上，下一步将结合马尔科夫链来对P-GM（1，1）模型的拟合能力进行进一步提升。根据P-GM（1，1）模型的拟合误差的最大值（Maximum error）和最小值（Minimum error），将误差状态分为五个状态，每个状态的误差区间占区间[Minimum error，Maximum error]的 20%。该五个状态所对应的误差区间如下所示：

在确定了各个状态所对应的误差区间后，就可根据公式（10）分别计算获得两组数据的马尔科夫一步状态转移概率矩阵和：

求得最优的λs值后，运用公式（14）分别计算出基于CMP-GM（1，1）模型的两组数据预测值，结果如图2所示。

为了验证所提CMP-GM（1，1）预测模型的有效性，本文选取GM（1，1）、自回归移动平均（Auto Regressive moving average，ARMA）、BP神经网络及指数平滑（Exponential Smoothing，ES）四个模型作为对比，并且使各个模型在该实验数据环境下预测性能表现最优的模型参数设置。其中ARMA模型的自回归项数 p和模型的移动平均项数q分别设为 p=2和q=1；BP神经网络的输入层、隐含层和输出层神经元的最优个数设置为36∶15∶36；指数平滑采用二次平滑，选取前12个点的平均值作为平滑初值，平滑参数α经过识别、比较后，确定为 α=0.36，此时方差最小；CMP-GM（1，1）模型中布谷鸟算法的终止条件为最大循环次数200。图3给出了CMP-GM（1，1）模型与各模型预测结果的相对误差比较结果。表1给出了CMP-GM（1，1）模型与各预测模型的预测模型综合比较结果。

图2（a） 基于CMP-GM（1，1）模型的NASA数据预测结果

图2（b） 基于CMP-GM（1，1）模型的Clarknet数据预测结果

图3 各模型预测结果的相对误差比较

表1 各模型的预测结果比较

从预测结果比较中可以看出，本文所提的基于多步优化的GM（1，1）模型CMP-GM（1，1）预测模型的预测值与实际值在整体上最为贴近。对于未经改进的GM（1，1）模型，CMP-GM（1，1）模型的预测误差只有其20%～30%，证明了本文所建的多步优化模型是有效的，能明显提升GM（1，1）模型对于动态、非线性数据的预测能力。而相比于ARMA、BP神经网络和ES等在先前云计算资源负荷预测中被用到的模型，CMP-GM（1，1）模型也在预测精度上体现出了一定的优势。综上所述，CMP-GM（1，1）模型不仅在直观上反映出该模型良好的预测性能，而且在各评价指标上也体现出了优势，对具有较强非线性性和动态性的云计算短期资源负荷时间序列展现了优良的预测性能。

4 结论

本文首先介绍了云计算资源负荷特征，论述了资源负荷预测在实现云计算资源高效管理中的作用，并强调了资源负荷短期预测在实现对云系统实时控制和使其稳定运行中的效用。继而阐述了GM（1，1）灰色模型在预测性能上的优劣，提出基于多项式回归模型、马尔科夫链和布谷鸟搜索算法多步优化的GM（1，1）预测模型，并将该模型用于云计算环境下资源负荷的短期预测应用中去。实验结果表明，相比于其他传统时间序列预测模型，本文所建模型具有更高的预测精度，体现出良好的预测性能，适合对具有较强动态性和非线性性的云计算资源负荷进行短期预测。

[1]Ardagna D.Dual time-scale distributed capacity allocation and load redirect algorithms for cloud systems[J].Journal of Parallel and Distributed Computing，2012，72（6）：796-808.

[2]Ching C T M，Dusit N，Tham C K.Evolutionary optimal virtual machine placement and demand forecaster for cloud computing[C]//2011 International Conference on Advanced Information Networking and Applications，2011：348-355.

[3]Caron E，Desprez F，Muresan A.Forecasting for grid and cloud computing on-demand resources based on pattern matching[C]//2nd IEEE International Conference on Cloud Computing Technology and Science，2010：456-463.

[4]Islam S，Keung J，Lee K，et al.Empirical prediction models for adaptive resource provisioning in the cloud[J].Future Generation Computer Systems，2011，28（1）：155-162.

[5]Duy T V T，Sato Y，Inoguchi Y.Performance evaluation of a green scheduling algorithm for energy savings in cloud computing[C]//International Symposium on Parallel Distributed Processing Workshops and Phd Forum IPDPSW，2010：1-8.

[6]Di S，Kondo D，Cirne W.Host load prediction in a Google compute cloud with a Bayesian model[C]//Proceedings oftheInternationalConferenceon High Performance Computing，Networking，Storage and Analysis.[S.l.]：IEEE Computer Society Press，2012：1-11.

[7]Mishra A K.Towards characterizing cloud backend workloads：insights from google compute clusters[J].ACM SIGMETRICS Performance Evaluation Review，2010，37（4）：34-41.

[8]Benson T，Akella A，Maltz D A.Network traffic characteristics of data centers in the wild[C]//Proceedings of the 10th ACM SIGCOMM Conference on Internet Mea-Surement.[S.l.]：ACM，2010：267-280.

[9]Di S，Kondo D，Cirne W.Characterization and comparison of cloud versus grid workloads[C]//International Conference on Cluster Computing（CLUSTER）.[S.l.]：IEEE，2012：230-238.

[10]邓聚龙.灰理论基础[M].武汉：华中科技大学出版社，2002.

[11]王正新，党耀国，练郑伟.无偏GM（1，1）幂模型其及应用[J].中国管理科学，2011，19（4）：144-151.

[12]王宇熹，汪泓，肖峻.基于灰色GM（1，1）模型的上海城镇养老保险人口分布预测[J].系统工程理论与实践，2010（12）：2244-2253.

[13]Li G D.The hybrid grey-based model for cumulative curve prediction in manufacturing system[J].The International Journal of Advanced Manufacturing Technology，2010，47（1/4）：337-349.

[14]王晓佳，杨善林，徐达宇.基于改进粒子群算法的数据预测挖掘应用研究[J].情报学报，2011，30（8）：840-845.

[15]钱吴永，党耀国.基于振荡序列的GM（1，1）模型[J].系统工程理论与实践，2009，29（3）：149-154.

[16]Yang X S，Deb S.Cuckoo search via Lévy flights[C]//World Congress on Nature&Biologically Inspired Computing（NaBIC 2009）.[S.l.]：IEEE，2009：210-214.

[17]李煜，马良.新型元启发式布谷鸟搜索算法[J].系统工程，2012，30（8）：64-69.

[18]Civicioglu P，Besdok E.A conceptual comparison of the Cuckoo-search，particle swarm optimization，differential evolution and artificial bee colony algorithms[J].Artificial Intelligence Review，2013，39（4）：1-32.

[19]Traces in the Internet Traffic Archive[EB/OL].[2013-06-20].http：//ita.ee.lbl.gov/html/traces.html.

[20]Mehta A.Envergy conservation in cloud infrastructures[C]//5th Annual IEEE International Systems Conference，2011：456-460.

[21]Prevost J J.Prediction of cloud data center networks loads using stochastic and neural models[C]//6th International Conference on System of Systems Engineering，2011：27-30.

[22]Ardagna D.Dual time-scale distributed capacity allocation and load redirect algorithms for cloud systems[J].Journal of Parallel and Distributed Computing，2012，72（6）：796-808.