虚拟机负载均衡问题刍议

1多周期分配的VMLBP的蚁群算法

蚁群算法（ACO）是意大利学者DorigoM等研究蚂蚁寻找路径的自然行为，受到自然界中真实蚁群觅食行为的启发，进而提出的一种路径搜索算法［5－6］．大量的研究发现，蚁群在觅食过程中通过释放信息素、感知信息素的强度来进行交流，从而选择最短搜索食物．蚁群算法是启发式算法，以其鲁棒性强、全局寻优能力强的特点在优化问题中得到广泛的应用．因此针对多周期分配的虚拟机负载均衡问题，本文提出了一种改进的蚁群算法作为求解方法．

1．1对下一个节点的概率选择

仿效自然界的蚁群行为，蚁群算法中人工蚂蚁的行为可以描述如下：多只蚂蚁在相邻的节点间移动，从而协作异步地得到问题的解［7］．在基本的蚁群算法中，每只蚂蚁会根据路径上的信息素，依据一定的概率选择下一个节点，距离越近的点被选择的可能性越大．本文中根据所要达到的优化目标，将概率选择公式中的距离替换为下一个任务的所需服务时间与任务分配周期的比，通过计算概率来选择下一个需要分配的任务，则可知蚂蚁对任务的选择概率应满足以下条件：（1）路径上信息素强度越强，蚂蚁到达的概率越大；（2）所需服务时间与任务分配周期越接近，蚂蚁选择到达的概率越大．

1．2算法描述

基于上述改进，可得多周期分配的VMLBP蚁群算法流程如下：步骤1初始化各参数，设定最大循环次数N，计算η（i，j）并存放于相应的数组中；步骤2初始化任务信息，创建空路径，随机选取一个任务为初始点，令当前点为i；步骤3以当前任务i为出发点，根据式（8）计算转移概率，选取下一个任务j，在路径中添加任务j；步骤4重复步骤3，若已遍历所有的任务，则k＝k＋1，若k＜k＋1，则转步骤2，否则转入步骤5；步骤5每只蚂蚁得到一条以初始分配时刻为起点的路经，每条路经就相当于所有虚拟机分配到的任务的排序，取路径中的每m个任务为一次分配的任务，分配次数l＝1，分配时间为0，开始时间为0，等待时间为0，计算完成时间、空闲时间；步骤6l＝l＋1，分配时间为（l－1）•D，计算等待时间、开始时间、服务时间、完成时间，若完成时间小于下一次任务分配时间l•D，则计算空闲时间，否则空闲时间为0；步骤7重复步骤6，若l＝L，分配时间为（l－1）•D，计算等待时间、开始时间、服务时间、完成时间，记录每个任务的完成时间，若大于最大服务时间T，转到步骤2；步骤8计算每条路径上最后一次分配的m个任务完成时间的方差，并保存方差最小的路径，在该路径上进行信息素更新；步骤9判断循环次数n是否达到N，若n＞N，则终止运算，输出上一步迭代的最优结果，否则转到步骤2．

2实验结果与分析

本文提出的改进的蚁群算法采用C＋＋语言在WindowsXP（P42．8GHz，1GB）平台上编程实现，为了验证算法的性能和有效性，随机选取一个任务为初始点，构造一个包含9个任务的分配网络（设分配周期D＝80单位时间，虚拟机数量m＝3，分配次数l＝3，虚拟机最大服务时间T＝300单位时间），然后利用此数据对算法进行测试．在蚁群算法中设定残留信息的相对重要程度α＝1、预见值的相对重要程度β＝2和信息素的挥发系数ρ＝0．5，运用10只蚂蚁，迭代100次获取结果的最优值．为了进一步分析算法执行的稳定性，本文选择遗传算法进行比较，相关参数设置如下：种群大小popsize＝5，交叉率pc＝0．1，变异率pm＝0．01，最大世代数generation＝100，并将得出的结果与蚁群算法得到的结果进行比较，可见表1．由表1可见，在10组数据上蚁群算法得到的结果的平均值更小，且执行时间的平均值更小．比较表1的第2列和第4列可以看出，在目标函数值相同时，蚁群算法的执行时间更短．由此可见，相对于遗传算法，蚁群算法的平均性能更优，即考虑了时间因素的改进蚁群算法具有更好的全局寻优能力，更易于找到较优的解．由表1的第3列可以看出，10组实验数据算法执行时间均在0．05s以内，总的平均执行时间为0．037s．由此可见，本文提出的改进蚁群算法可以用于求解云计算环境下的虚拟机负载均衡问题，且可在较短的时间内取得满意的结果．残留信息的相对重要程度α、预见值的相对重要程度β和信息素的挥发系数ρ，体现了相关信息痕迹、预见度及挥发对蚂蚁决策的相对影响．为了进一步分析各参数对解的影响，我们选用不同的α、β、ρ取值．实验表明，α、β、ρ的取值变化均会影响问题的求解结果，多次运行后得出本文的最佳参数设定为α＝1，β＝2，ρ＝0．5，此时得到的实验结果最优，且收敛速度最快，具有较强的全局寻优能力．实验结果表明本文针对云计算环境下的虚拟机负载均衡问题建立的模型是可解的，算法是有效的．由表1可以看到由改进的蚁群算法得到的结果更优，而且具有更快的收敛速度，算法的性能更优．

3结束语

本文对云计算环境下的虚拟机负载均衡问题进行了研究，建立了数学模型，并针对其定约束条件进行了研究，最后通过蚁群算法进行了求解，对指导现实生活中的实际情况具有一定的理论意义．

作者：马华伟 吴晓莉 单位：合肥工业大学管理学院