摘 要

负载均衡是提高分布式系统性能的一种常规手段，而负载预测能为负载均衡提供必要的负载信息，使其更加高效可靠。论文首先介绍了主机负载的七大特性，对其进行分析并得出主机负载是一种时间序列的理论，在此理论基础上提出了一种基于时间序列的负载预测算法。算法使用MA、AR、ARMA三种常见的预测模型对负载序列进行预测，算法使用JAVA语言进行实现，并通过JS/JSP技术将算法的具体流程图形化。研究所使用的负载数据通过Linux虚拟机的/proc文件系统搜集，实验结果表明该算法对短期内的负载序列具有较好的预测效果。

关键词：负载预测；时间序列；JAVA；ARMA

Abstract

Load balancing is a common method to improve the performance of distributed systems, and load forecasting can provide necessary load information for load balancing, making it more efficient and reliable. This paper first introduces the seven characteristics of the host load. Analysis shows that the host load is a time series. Based on this theory, this paper puts forward a load prediction algorithm based on the time series. The algorithm utilizes three common prediction models, MA, AR and ARMA, to predict the time series. The algorithm is implemented by JAVA language, and the specific process of the algorithm is graphed by JS/JSP technology. The load data used in this study are all collected by the proc file system of Linux, and the experimental results show that this algorithm leads to an effective prediction on a single time series.

Key Words：Load Forecasting；Time Series；JAVA；ARMA

目 录

摘 要 I

Abstract II

第1章 绪论 1

1.1 研究目的及意义 1

1.1.1 研究的背景 1

1.1.2 研究的目的和意义 1

1.2 国内外研究现状 1

1.3 研究内容与技术方案分析 2

1.3.1 研究对象 2

1.3.2 待解决的关键问题 2

1.3.3 研究方案 2

1.3.4 关键技术 3

1.3.5 技术路线 3

1.4 论文结构安排 3

第2章 负载的特性分析 5

2.1 负载特性 5

2.2 负载序列的平稳性分析 5

2.2.1 自相关函数（ACF） 5

2.2.2 偏自相关函数（PACF） 6

2.2.2 负载序列的平稳性判断 6

2.3 负载序列的平稳化 6

2.4 本章小结 6

第3章 负载序列的预测模型 8

3.1 三种常见的预测模型 8

3.1.1 MA(q)模型--滑动平均模型 8

3.1.2 AR(p)模型—自回归模型 8

3.1.3 ARMA(p,q)模型—自回归滑动平均模型 8

3.2 负载预测模型的选择 9

3.3 预测模型定阶 9

3.4 预测模型的参数估计 9

3.5 本章小结 10

第4章 基于时间序列的负载预测算法 11

4.1 算法实现及算法流程 11

4.1.1 算法实现 11

4.1.2 算法流程图 12

4.2 负载预测与误差分析 13

4.2.1 负载的预测流程 13

4.2.2 负载的预测案例分析 14

4.2.3 基于时间序列的负载预测算法总结 18

4.3 本章小结 18

第5章 结论 20

5.1 研究成果 20

5.2 展望 20

5.2.1 下一步工作 20

5.2.2 算法的改进 20

5.2.3 关于负载预测与能耗的研究 20

第1章 绪论

1.1 研究目的及意义

1.1.1 研究的背景

在如今大数据时代的背景下，科技高速发展，数码产品日益普及，每时每刻都有海量的数据产生，传统计算机技术无法处理如此大量的数据，于是分布式系统得到越来越广泛地关注，因为它能对海量的数据进行分布式数据挖掘，使数据增值。

对于一个分布式系统，多台服务器之间如何进行动态的任务分配很大程度上影响着系统的整体性能。为解决该问题，各国的研究人员进行了大量的研究，提出了一系列的负载均衡算法。这种算法的目的是避免在一个分布式系统中出现部分节点过载而其他节点空闲的情况，力求公平地分配每个节点的工作负载，从而提高系统资源利用率，降低其响应时间。

负载均衡的核心思想就是衡量分布式系统中各个节点的负载信息，从而选择合适的节点来分配任务。目前的负载均衡算法主要分为动态和静态两类。静态算法主要根据对系统的先验知识来制定任务分配策略，不会根据系统运行时的状态进行调整，所以很难能做到真正的负载均衡。而动态负载均衡算法则是根据系统当前的负载信息来进行任务分配。虽然这种方式能让各个节点之间负载更加均衡，但是却造成了巨大的额外开销，因为系统中的各个节点要在很小的延迟内向前端任务调度器发送自身的负载信息，以帮助其做出负载均衡决策。

基于以上原因，本文提出了基于时间序列的负载预测算法。

1.1.2 研究的目的和意义

本研究的目的是实现一种负载预测算法，该算法能根据历史负载数据，在可接受的误差范围内预测未来的负载数据，从而帮助负载均衡算法做出决策。

该算法的意义在于它很大程度上减轻了分布式系统中通信网络的负担，避免各个节点在每次系统做出任务调度决策时都要向调度器发送自身的负载信息，从而以牺牲小部分可靠性为代价，换取巨大的性能提升并能节约更多系统资源。

1.2 国内外研究现状

目前国内外对于负载预测的研究主要集中在网络流量的预测上，对于主机负载预测的研究比较少。前者主要关心TCP/IP流量的大小和网络延迟，而后者侧重于服务器本身的负载。服务器的负载是指其运行所消耗的资源的综合体，主要包括：CPU利用率、磁盘空闲大小、自由内存大小等。本文主要研究主机负载的预测，在该研究方向上，[1]提出了一种基于ARMA模型的网络流量预测方法，但是却只采用了一种ARMA(2,1)模型，并未根据实际序列的具体特征对预测模型进行动态调整。这样做虽然减轻了算法的复杂度，但是却极大程度地降低了预测的准确性与可靠性，这种舍本逐末的方式对于实际应用来说是不可取的。[2]提出了一种预测主机负载的普适性方法，同样也是利用了时间序列的相关知识，虽然文章给出了算法的整体思路，并提出了一种新型的HLPS负载预测模型，但却并未涉及具体案例，只是简单地用伪码和公式对算法流程进行了大致描述，所以算法的可行性值得怀疑。另外[3]应用动力学的滤波理论预测负载，[4]应用人工智能技术预测负载，但[3][4]均未涉及预测系统模型与其实现策略，其可行性值得怀疑。[12]提出了CPU负载的相关特性和预测CPU利用率的方法，但是对于主机负载的预测不具有普遍意义。

1.3 研究内容与技术方案分析

1.3.1 研究对象

设计一种基于时间序列的负载预测算法，要求该算法能读取并分析特定格式的负载数据，并根据不同负载序列的特征动态地选择预测模型，最后根据历史数据得出预测数据，与真实数据对比并进行误差分析。

1.3.2 待解决的关键问题

（1）负载的特性检测与分析处理。

（2）预测模型的选择与实现。

（3）负载数据的采集。

研究方案

（1）通过/proc文件系统搜集负载数据，使用EViews仿真软件对其自相关函数（ACF）与偏自相关函数（PACF）进行分析，了解负载的平稳性特征与这两者之间的关系。

（2）使用Eclipse进行编程，根据ACF、PACF的计算公式和相关定理完成负载序列的平稳性判断，对于不平稳的负载序列，则进行差分处理直至平稳。

（3）学习时间序列预测模型中的MA，AR，ARMA模型，掌握其工作原理以及实现步骤，包括模型识别，定阶，参数估计等，并弄清如何将它们应用到负载预测中去。

（4）使用Eclipse进行编程，首先根据负载序列的特性判断其适合用哪种模型进行分析，判断依据为Box-Jenkins的模型识别方法。然后根据AIC准则为所选模型进行定阶。最后按照最小二乘原则求得模型的具体参数。

（5）使用最终定型的模型根据历史数据进行预测，通过比较预测结果与真实值进行误差分析。

（6）根据误差分析结果判断算法的准确度与适用性，并进一步分析其可扩展性、是否有其他应用。

1.3.4 关键技术

• （1）ACF与PACF的计算与分析。
• （2）MA、AR 、ARMA模型的定阶与参数估计。
• （3）通过/proc文件系统采集负载信息。

1.3.5 技术路线

图1.1 技术路线

1.4 论文结构安排

论文共由5个章节组成，主要内容及结构安排如下：

第1章，绪论，介绍研究课题的背景、目的及意义，并对研究所涉及到的相关知识以及关键技术做简要分析。

第2章，负载的特性分析，分析负载的特性，对为什么要用时间序列的相关方法进行负载预测做出解释，随后分析负载序列的平稳性，并介绍如何将负载序列平稳化。

第3章，负载序列的预测模型，首先介绍MA、AR、ARMA三种常见的预测模型，包括模型的思路、模型参数等，然后对模型选择、定阶、参数估计的方法进行介绍。

第4章，基于时间序列的负载预测算法，首先介绍算法的具体流程，然后介绍算法是如何预测负载的并进行误差分析的。

第5章，结论，根据实验成果得出最终结论，对算法的可靠性与适用性进行分析，并指出算法需要改进的地方、可扩展的地方。

第2章 负载的特性分析

2.1 负载特性

要准确地预测负载，首先要了解负载的特性，然后才能找出合适的方法。负载特性主要包括以下7各方面：

（1）负载的变化过程是随机的。

（2）负载一般处于较低的水平，但其波动性非常强。

（3）负载均值较高的时候，其绝对波动量也大。

（4）负载值的分布是复杂的，尤其是平均负载量高的，其负载值的分布呈现复合多样性。

（5）负载随时间变化有很强的关联性，即过去的负载值对将来的负载值有很大的影响。

（6）负载的变化有高度的自相似性，即在所有的时间尺度下负载的变化既复杂，又具有长期的依赖性，因此负载的模型化和预测是困难的。

（7）负载的变化具有突变性[5]。

根据以上特征，我们知道了历史负载值对未来负载值有很大影响，而且负载值的变化有高度的自相似性，所以负载序列也是一种时间序列，故使用时间序列的相关知识对负载进行预测是可行的。

本研究中所使用的负载值是一个百分数，表示主机的CPU利用率、内存占用、磁盘IO、网络带宽利用率的综合情况，而负载序列则是一段连续时间内的负载值，负载数据采集间隔为1min。

2.2 负载序列的平稳性分析

本文所使用的预测方法的前提是负载序列是平稳的，而负载序列的平稳性判断需要使用到它的自相关与偏自相关函数。所以下文将介绍如何求得一个负载序列的自相关函数与偏自相关函数，并根据它们的相关特性来判断负载序列是否需要进行平稳化处理。

2.2.1自相关函数（ACF）

（1）定义：衡量。

（2）计算公式：

（2.1）

其中为k阶自相关系数，Z为负载序列，为负载序列的均值，n为序列长度。

2.2.2偏自相关函数（PACF）

（1）定义：除去，，…，的影响后，衡量。

（2）计算公式：

（2.2）

其中为k阶偏自相关系数，为k阶自相关系数，使用该递推公式能比较方便地计算高阶偏自相关系数。

2.2.2 负载序列的平稳性判断

判断负载序列的平稳性涉及到两个定义：“截尾”，“拖尾”。

（1）截尾：如果样本函数在最初的k阶远远大于2倍标准差，而后突然衰减为小值（接近0）波动，并且95%以上的值都落在2倍标准差之间，那么样本函数就是截尾的。

（2）拖尾：如果样本函数落在2倍标准差之外的值超过了总量的5%，或者函数值衰减为小值波动的过程十分缓慢，那么可以认为样本函数是拖尾的。

（3）特殊情况：如果自相关函数或偏自相关函数呈三角对称型，那么负载序列是单调且不平稳的。

（4）判断依据：如果是平稳的负载序列，其自相关函数与偏自相关函数只可能是拖尾或截尾的。

2.3 负载序列的平稳化

当通过上节的方法判断负载序列不平稳后，则需要对负载序列进行平稳化处理以满足建模要求。本文使用多阶差分的方法来对数据进行平稳化处理，通过差分就可除去负载序列中的趋势项与周期项，从而使其达到平稳化标准。

普通一阶差分：

（2.3）

其中为差分后的数据，为负载序列在t时刻的负载值。有时一个负载序列可能需要进行多阶差分后才能平稳。

2.4 本章小结

本章通过分析负载的特性，得出了可以用预测时间序列的手段对负载进行预测的结论，奠定了本研究的理论基础，而且通过本章的研究，我们能判断负载序列的平稳性，并将不平稳的负载序列进行平稳化处理，为后续的工作做好铺垫。负载序列的平稳性判断除了本文所使用的方法外，还有其它途径，如单位根检验（ADF检验）等，但由于在研究过程中未找到关于如何实现ADF检验的资料，所以本文采取了通过分析ACF与PACF判断平稳性的方式，使用该方法判断平稳性的准确度有待提高，在后续的程序优化中，会对此方法进行优化，进一步提高算法的可靠性与精确性。

第3章 负载序列的预测模型

在得到了平稳的负载序列之后，下一步就是通过分析负载序列的相关特性来选择最优的预测模型，并对预测模型进行定阶、参数估计等操作。本研究主要使用了MA，AR，ARMA三种时序模型，它们都旨在解释时间序列内在的自相关性从而预测未来，而在ARMA模型的基础上，还有扩展的ARIMA与SARIMA模型，本文中不再赘述。下文将介绍如何根据不同的负载序列特性，来构建其对应的最优预测模型。

3.1 三种常见的预测模型

首先对三种预测模型的中心思想与定义作简要介绍。

3.1.1 MA(q)模型--滑动平均模型

（1）中心思想：通过历史白噪声的线性组合即可预测当前时间点。

（2）定义：

(3.1)

其中为预测值，为各个时刻的白噪声，β为MA模型的参数，q为MA模型的阶数。所谓白噪声，根据时间序列的定义：

(3.2)

T为趋势项，S为周期项，则是该时刻的白噪声，即一种无规律的变动。

3.1.2 AR(p)模型—自回归模型

（1）中心思想：通过历史时间序列的线性组合加上白噪声即可预测当前时间点。

（2）定义：

(3.3)

其中为预测值，为历史时间序列的值，α为AR模型的参数，p为AR模型的阶数，为当前的白噪声。

3.1.3 ARMA(p,q)模型—自回归滑动平均模型

（1）将AR与MA模型的思想混合起来，就能得到ARMA模型

（2）定义：

(3.4)

从模型的定义可以看出，ARMA模型结合了AR与MA模型的思想，前半段为AR模型的预测值，后半段为MA模型的预测值，所以分别求出AR与MA模型的参数也就求得了ARMA模型的参数。

3.2 负载预测模型的选择

了解了预测模型的基本思路与实现方法，那么接下来就需要为负载序列选择最优的预测模型了，而预测模型的选择我使用Box-Jenkins模型识别方法，该方法需要我们对负载序列的自相关与偏自相关函数特性进行分析，具体情况如表3.1：

表3.1 Box-Jenkins模型识别方法

使用第二章所提出的算法求出负载序列的自相关与偏自相关函数后，即可根据Box-Jenkins模型识别方法在AR、MA、ARMA中选出一种最适合当前负载序列的预测模型。

3.3 预测模型定阶

选取了最优的预测模型之后，下一步就要为预测模型定阶，即确定模型的p，q值，而p，q值不能太大，否则会导致预测结果不够精确，所以在算法中需要对p，q值的上限进行限制，本研究中设定为历史负载数据长度的1/2，之后只需要在给定的范围内选取最优的p，q值，模型的定阶我们使用AIC准则，计算AIC值的公式如下：

（3.5）

其中，为残差的方差，N为负载序列样本的大小。

所谓残差，即预测值与真实值的差值。AIC算法的核心思想，就是将所有给定范围内的p，q值依次代入模型之中，求出模型参数然后进行预测，并统计预测模型在每组p，q值下的残差方差，最后选出残差方差最小的一组p，q值作为最优的预测模型阶数。而通过AIC的定义也不难看出，p，q值越大，AIC的值就越大，预测也就越不准确。

3.4 预测模型的参数估计

构建一个预测模型的最后一步，就是解出模型的参数，本文使用最小二乘原则来求解预测模型的参数。下面以求解AR模型参数的过程为例：