基于卡尔曼预测器的云计算资源调度研究

周婉++王移芝

摘要：资源调度是云计算的一个主要研究方向，本文在研究现有云计算资源调度算法的基础上，为了提高云计算资源的利用率，保持负载平衡，设计了基于卡尔曼预测器的云计算资源调度算法，采用卡尔曼预测器预测虚拟资源下一时刻的状态，由此得到虚拟资源的向量，然后计算任务的代价，建立任务与资源的映射模型，将任务分配到合适的虚拟资源进行调度，避免了盲目调度，提出了基于卡尔曼预测器的云计算资源动态调度的具体算法，最后在云计算仿真平台CloudSim上进行仿真实验与分析。仿真实验的结果证明，本文提出的算法在任务执行的跨度和负载均衡离差方面具有一定的优势。

关键词：云计算；虚拟资源调度；卡尔曼预测器

中图分类号：TP311.12

文献标识码：A

DOI：10.3969/j.issn.1003-6970.2015.09.003

0 引言

随着计算机性能的不断提高和互联网规模的不断扩大，人们的计算需求和海量数据处理需求日益增长，出现了云计算这种新兴的计算方式。云计算是在并行计算、分布式计算、网格计算的基础上发展起来的一种商业模型，是虚拟化技术、效用计算、基础设施即服务、平台即服务和软件即服务等概念优化整合的结果。云平台采用虚拟化技术将集群中的各种资源构成资源池，接收用户任务请求，并将任务调度到合适的资源上执行。云环境下的任务数量以海量形式存在，而云计算资源具有动态、异构特性，这就使得云计算环境下的虚拟资源调度成为了云计算研究的一个热点问题。

师雪霖等借鉴网络效用最大化模型，提出了一种资源调度模型——云效用最大化模型，以达到效用最大为调度目标，可以充分提高用户的满意程度。徐文忠等提出了一种基于遗传算法的关于虚拟机负载均衡的调度策略，算法在很大程度上能够解决负载不均衡和高迁移成本问题。王艳平等设计了一种基于改进蚁群的云计算资源调度算法。在算法中添加了查找表，存储其他蚂蚁推荐的节点，缩短了搜寻资源节点的时间，从而使任务可以更快地获得资源并执行，保证了任务能够按时完成。

本文设计了一种基于卡尔曼预测器的云计算资源调度算法，采用卡尔曼预测器预测虚拟资源下一时刻的状态，得到可用资源向量，然后建立任务与资源的映射模型，将任务分配给合适的虚拟资源进行调度，避免了盲目调度，并提出了具体的基于卡尔曼预测器的云计算资源动态调度算法。

l 调度模型

在云计算的虚拟资源调度模型中，主流的是Map-Reduce调度模型。由Google最早提出并应用到云平台中，云用户只需编程实现Map-Reduce接口即以实现计算的并发和分布执行。它由“Map”和”Reduce”两部分组成。具体结构如图1。

Map-Reduce调度模型中，首先根据文件的大小，将其分割。在集群中分为主控制模块和普通模块，主控制模块的主要职责是将工作分配给普通模块。主控制模块的主要工作流程是首先选取空闲状态的服务器，然后将映射或者简化的任务分配到这些空闲的服务器上，分配到映射任务的服务器根据主控制模块传达的指令读取输入文件的分片，之后执行映射操作，将执行结果保存在缓存中。映射阶段的任务完成之后，将中间结果写入硬盘，同时进行分区，将分区信息传递给主控制模块。主控制模块将中间结果保存的分区信息通知分配了简化任务的服务器，这些服务器读取中间结果，同时执行用户定义的简化操作，最后将结果保存在输出文件中，同时将结果通知主控制模块。最终由主控制模块综合所有的输出模块，输出最终的结果。

2 相关描述

2.1 任务描述

Kalman于1960年提出了卡尔曼滤波，采用由状态方程和观测方程组成的线性随机系统的状态空间模型来描述滤波器，并利用状态方程的递推性，按线性无偏最小均方误差估计准则，用递推算法对该滤波器的状态变量作最佳估计，从而求得滤掉噪声的有用信号的最佳估计。

卡尔曼滤波器使用递推的方式来进行预测。滤波器先通过上一时刻系统的状态预测下一时刻系统的状态，然后再通过观测的到的系统运行时表现进行反馈修正，如此反复。

步骤1：获取虚拟机的资源，根据资源分别计算虚拟机的性能。

步骤2：根据卡尔曼滤波预测下一时刻虚拟机的资源。

步骤3：根据步骤1与步骤2的计算结果计算虚拟机与任务的Cost值，按性能与任务从大到小进行对应的映射与绑定，任务数按虚拟机数进行平均分配。

步骤4：迭代次数i是否达到最大值迭代次数n，若达到最大迭代次数，则虚拟资源调度结束；否则i=i+l，并返回步骤2继续运行。

4 实验仿真与分析

为了验证算法，本实验在云仿真平台CloudSim上进行仿真。CloudSim是澳大利亚墨尔本大学开发的云计算仿真器，是一个通用的和可扩展的模拟框架，支持模拟云计算基础设施和管理服务，具有对不同应用和服务模型的调度和分配策略的性能进行量化和比较等优点。CloudSim是在离散事件模拟包Simjava上开发的函数库，CloudSim继承了GridSim的编程模型，并具有以下特点：一个自足的支持数据中心、服务代理人、调度和分配策略的平台.CloudSim的软件结构框架和体系结构组件包括Simjava、GridSim、CloudSim、UserCode4个层次，CloudSim的CIS（CloudInformation Service）和DataCenterBroker实现资源发现和信息交互，是模拟调度的核心，提出的算法主要在DataCenterBroker中实现。

本实验的仿真环境同李园园等，采用李园园等的方法对实例进行仿真，将得到的任务跨度和负载均衡离差进行比较，得出的仿真曲线如图2和图3所示。

从图2中可以看出，本文所研究的方法的任务跨度与李园园等的方法和魏锐等的方法相比，任务跨度比较低，平均任务跨度与李园园等的方法相比，降低了19.87%，与魏锐等的方法相比，降低了29.75%。

从图3中可以看出，负载均衡离差的值随着任务数的增加而增加，随着任务数的增加负载均衡离差呈增加趋势，本文所研究的方法得到的负载均衡离差值较李园园等的方法和魏锐等的方法偏低，说明了该方法较好地实现了资源负载平衡。

5 总结

云计算的资源调度技术是云计算中的关键技术，一个好的调度算法对提高整个云计算系统的性能起着重要作用。本文研究并设计了一种基于卡尔曼预测器的云计算资源调度算法，建立了云资源调度模型，采用卡尔曼预测器预测虚拟资源下一时刻的状态，得到可用资源向量，然后建立任务与资源的映射模型，将任务分配给合适的虚拟资源进行调度，避免了盲目调度，使用cloudsim工具进行仿真，实验结果表明，本研究方法有效地实现云环境下虚拟资源调度，具有较小的负载均衡离差，有效地提高了资源利用率。