基于混合遗传算法的云计算虚拟机动态调度方法

摘要

本发明属于基础设施即服务型（Iaas）云计算领域，涉及一种基于混合遗传算法的云计算虚拟机动态调度方法；该方法的步骤为：监控云计算环境中的物理机和虚拟机负载信息，分析每一台主机的负载周期及变化情况，确定负载变化的周期；通过具有多适应度的混合遗传算法，算出云环境中出现的虚拟机放置组合。本发明根据三个优化目标，计算得出最优化的虚拟机放置策略，作为最终的结果；周期性地执行本发明所述算法，通过虚拟机的动态迁移，实现虚拟机合理放置，提高资源利用率，节省资源。本发明能解决当前云计算中心中资源利用率不高的问题，适应当前云计算中心的自动化管理要求。

主权项

一种基于混合遗传算法的云计算虚拟机动态调度方法，其特征在于，所述的方法包括：监控云计算环境中的物理机和虚拟机负载信息及特征提取，分析每一台主机的负载周期及变化情况，确定负载变化的周期；通过具有多适应度的混合遗传算法，算出云环境中可能出现的虚拟机放置组合，其包括步骤：(1)向历史监控数据库发起请求，获得所有虚拟机的各项负载参数，对周期性的应用以一个周期为单位；对实际环境中常见应用以24小时为单位；(2)进行多适应度混合遗传算法的准备工作：计算出“多适应度”中的子适应度函数1、子适应度函数2、子适应度函数3，通过其线性组合得出总的适应度函数；(3)初始化遗传算法的种群，生成200‑500个个体；(4)通过总适应度函数，进行遗传算法中的迭代过程；根据对精度和时间权衡，可迭代500‑2000代；(5)根据遗传算法的迭代结果，得出最终的动态调度方案；(6)根据结果得出的动态调度方案，进行虚拟机的迁移，所述过程结束，得出最终虚拟机配置方案；(7)根据虚拟机负载的变化情况，每24小时运行一次所述算法，保证资源利用率保持最优化状态；其中，所述的子适应度函数1通过下述公式计算得：$E_{i1}=\frac{\frac{pm-{\mathrm{count}}_i}{pm}}{{\Sigma }_{k=1}^p\frac{pm-{\mathrm{count}}_k}{pm}}=\frac{1-\frac{{\mathrm{count}}_i}{pm}}{pm-{\Sigma }_{k=1}^p\frac{{\mathrm{count}}_k}{pm}}---\left(1\right);$其中，对于物理机和虚拟机的特征提取，为：设pm代表云中物理机总数，vm代表云中虚拟机总数，count_i代表遗传算法中第i个染色体里所占用的物理机数量，p为遗传算法群体中个体数；CPU负载、网络负载和磁盘I/O三项负载参数分别以a,b,c表示，对第k台物理机上承载的虚拟机其数目为n，所述三项负载可分别以三个数组[a_k1,a_k2,…,a_kn],[b_k1,b_k2,…,b_kn],[c_k1,c_k2,…,c_kn]表示，每项负载参数均归一化到[0,1]区间；对每一项负载参数分别求平均值所述的子适应度函数2通过下述公式计算得：$\overline{a_k}=\frac{{\Sigma }_{j=0}^n{a}_{kj}}{n}---\left(2\right)$$\overline{b_k}=\frac{{\Sigma }_{j=0}^n{b}_{kj}}{n}---\left(3\right)$$\overline{c_k}=\frac{{\Sigma }_{j=0}^n{c}_{kj}}{n}---\left(4\right)$根据所述式(2)(3)(4)的结果，计算此物理机之上三项负载平均值之间的方差值V_k：$V_k={\left(\overline{a_k}-\frac{\overline{a_k}+\overline{b_k}+\overline{c_k}}{3}\right)}^2+{\left(\overline{b_k}-\frac{\overline{a_k}+\overline{b_k}+\overline{c_k}}{3}\right)}^2+{\left(\overline{c_k}-\frac{\overline{a_k}+\overline{b_k}+\overline{c_k}}{3}\right)}^2---\left(5\right)$式(5)表示某一台特定物理机的负载方差值，将所有物理机的方差值相加，得到所有物理机的方差值，即第i个染色体所表现出的方差值S_i：S_i＝∑V_k     (6)；其中，式(6)的方差值代表的是第i个染色体所代表的放置方案上三项负载之间的偏离度大小，若方差越小，则负载的平均利用率情况越好，若方差越大，表明负载越不平衡；若以∑S代表所有染色体方差的总和，S_i含义同以上公式(6)，则子适应度函数2的计算方法为：$E_{i2}=\frac{\frac{\Sigma S-S_i}{\Sigma S}}{{\Sigma }_{k=1}^p\frac{\Sigma S-S_k}{\Sigma S}}=\frac{1-\frac{S_i}{\Sigma S}}{p-{\Sigma }_{k=1}^p\frac{S_k}{\Sigma S}}---\left(7\right);$所述的子适应度函数3通过下述公式计算得：$E_{i3}=\frac{\frac{\Sigma M-M_i}{\Sigma M}}{{\Sigma }_{k=1}^p\frac{\Sigma M-M_k}{\Sigma M}}=\frac{1-\frac{M_i}{\Sigma M}}{p-{\Sigma }_{k=1}^p\frac{M_k}{\Sigma M}}---\left(8\right),$其中，设M_i代表第i个染色体所代表的放置方案上需要迁移的虚拟机数量，以∑M代表所有染色体迁移数量的总和；所述的总适应度函数通过下述公式计算得：E_i＝xE_i1+yE_i2+zE_i3其中x+y+z＝1          (9)；其中，对某个体，设其三个子适应度值分别为E_i1,E_i2,E_i3，它们的权重分别为x,y,z。