基于多目标演化算法的云计算虚拟机分配策略研究

发布时间：2019-07-20 17:07

【摘要】：分析云计算虚拟机资源模型,针对模型中虚拟机与物理机的映射关系以及虚拟机多资源因子、多优化目标的特点,将虚拟机分配问题转化成多维装箱问题,引入多目标演化算法进行求解。算法设计了基于组的虚拟机分配链式编码和染色体评估函数,并根据编码设计了两种交叉算子和智能变异算子,通过引入基于超体积的种群更新机制,设计了基于SMS-EMOA的云计算虚拟机分配算法。为验证SMS-EMOA的性能,分别使用优先匹配启发式算法、基于物理节点数量的单目标简单遗传算法、SMS-EMOA进行了模拟。实验结果表明,基于SMS-EMOA的虚拟机分配算法在性能上更优。
【图文】：

获取资源。而如何对云计算资源进行合理分配与高效调度，保证云数据中心的均衡负载性能及低能耗已成为当前云计算研究的难点。因此，研究负载均衡、低能耗的云计算资源分配与动态调度算法具有重要的理论意义和应用价值。２云计算虚拟机调度模型虚拟化资源是通过虚拟化技术对物理资源进行抽象后的资源。由于城市数据中心硬件设备间存在差异且兼容性差，进行统一的物理资源管理难以实现。而通过对资源的抽象和虚拟化，屏蔽物理资源间的差异，搭建云计算环境，为实现资源的统一管理提供了科学可行的方案。资源虚拟化结构如图１所示。图１资源虚拟化结构示意图·４８·

将序列中的其他虚拟机按照上述算法放入物理节点中。其伪代码如下。以９个虚拟机分配到５个物理节点为例对编码进行阐述，基于组的链式编码如图３所示。图３基于组的虚拟机分配链式编码２．评估函数均衡负载保证应用系统高性能、物理节点低使用率两个目标，通过两个适应度函数（见式（２））来评估个体。第一个是使用物理节点的使用个数来评估染色体的耗能程度，物理节点占用越少，耗能越小；第二个是按照已使用物理节点的负载方差来评估染色体负载性能，方差值越小，负载性能越好。Ｆｉｔｎｅｓｓ＝｛ｍｉｎ∑ｊＣｊ，ｍｉｎ∑ｄＤξｉｄ｝（２）３．３演化算子１．交叉算子针对虚拟机分配到物理节点的问题，基于组的链式编码包含两个部分：虚拟机编码和物理节点编码。用组及内部链式结构表示染色体的基因，组中虚拟机个数不是固定的，所以交叉涉及长度可变的染色体。本文提出两种交叉因子：最低索引－最大长度交叉、改进单点交叉。（１）最低索引－最大长度交叉的步骤①两个父个体交叉产生一个子个体；②比较两个父个体的最小索引的组中虚拟机分配链式长度，，选取较长的组遗传给子个体；③删除两个父个体中已遗传到子个体中的各虚拟机编号；④循环步骤②，直到所有虚拟机编号都被遗传给子个体。假如父个体１｛（１，３，６），（２，４），（５）｝和父个体２｛（１，２），（３，４，５，６）｝被选取进行交叉。首先父个体１的最小索引组（１，３，６）的链式长度相比父个体２的最小索引组（１，２）的链式长度要长（如果长度相等，则比较组对应的物理节点的可分配资源量，选取值小的组）
【作者单位】：武汉大学计算机学院;九江职业技术学院;
【基金】：国家科技支撑计划(2012BAH35B03)资助
【分类号】：TP302

【参考文献】