一种面向云计算中心的高效负载均衡优化调度方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN109542619A(43)申请公布日2019.03.29(21)申请号201811346198.3(22)申请日2018.11.13(71)申请人河海大学常州校区地址213022江苏省常州市新北区晋陵北路200号(72)发明人韩光洁陈海文(74)专利代理机构南京经纬专利商标代理有限公司32200代理人丁涛(51)Int.Cl.G06F9/50(2006.01)G06F9/455(2006.01)权利要求书2页说明书4页附图2页(54)发明名称一种面向云计算中心的高效负载均衡优化调度方法(57)摘要本发明公开了一种面向云计算中心的高效负载均衡优化调度方法。包括步骤：1）初始化蚁群；2）信息素初始化；3）初始化蚂蚁的禁忌表；4）计算任务与资源的匹配因子，考虑负载均衡；5）采用轮盘赌算法，根据概率随机将任务选择下一个虚拟机节点，记录当前最优解6）随机产生新解，采用模拟退火算法判断是否保留新解，若达到模拟退火条件，进行下一步，否则返回步骤5）；7）更新信息素矩阵；8）判断是否达到蚁群算法迭代次数，是则结束，保留最优解；否则返回步骤3）。本发明能满足云计算环境下的动态性，在求解过程中加快了算法的收敛速度，避免了陷入局部最优解，不仅能够快速寻找到任务分配时间的最优解，还能保证虚拟机环境的负载均衡。CN109542619ACN109542619A权利要求书1/2页1.一种面向云计算中心的高效负载均衡优化调度方法，其特征在于，包括以下具体步骤：1)初始化蚁群；2)信息素初始化，运用贪心算法将蚂蚁随机分布到资源节点上，并且初始化局部信息素矩阵；3)初始化蚂蚁的禁忌表；4)计算任务与资源的匹配因子，考虑负载均衡，根据20％-80％原则局部更新信息素矩阵，根据信息素计算出资源节点被选择的概率；5)采用轮盘赌算法，根据概率随机将任务选择下一个虚拟机节点，记录当前最优解M；6)随机生成新解，采用模拟退火算法判断是否保留新解，若达到模拟退火结束条件，则进行下一步，否则返回步骤5)；7)更新信息素矩阵；8)判断是否达到蚁群算法迭代次数，是则结束，保留最优解；否则返回步骤3)。2.如权利要求1中所述的一种面向云计算中心的高效负载均衡优化调度方法，其特征在于，所述步骤2)中具体过程如下：(2a)信息素的初始化，通过下面的公式(1)初始化各个资源节点的信息素：τij(0)＝w1Mj+w2Bj+w3Rj+w4Sj(1)公式(1)中的τij(0)表示第0时刻，任务i指向资源节点j上的信息素大小，Mj表示节点j的处理速度，Bj表示节点j的带宽，Rj表示节点j的内存大小，Sj表示节点j的磁盘存储大小；w1、w2、w3、w4分别表示对Mj、Bj、Rj、Sj的期望，并满足w1+w2+w3+w4＝1；(2b)根据贪心算法将任务分配到虚拟机上；首先将任务按长度大小降序排列，将虚拟机节点按处理速度大小降序排列；选取排好序的前30％的任务以及排好序的前30％的虚拟机节点，根据贪心策略顺序将前30％的任务分配到前30％虚拟机节点上；然后将后70％的任务随机分配到后70％的虚拟机节点上；然后根据分配情况更新信息素矩阵，公式如下：τij＝τij(0)+Δτ0(2)公式(2)中，τij表示任务i分派到节点j的信息素的值，τij(0)表示第0时刻，任务i指向节点j的的信息素大小，Δτ0是一个常量，表示贪心策略将任务i分配到节点j的信息素增量。3.如权利要求1中所述的一种面向云计算中心的高效负载均衡优化调度方法，其特征在于，所属步骤4)中的具体过程如下：(3a)计算任务与资源的匹配因子：公式(3)中，ηij表示蚂蚁将任务i分配到节点j的期望值大小，dij表示任务i分配到节点j需要的时间；(3b)考虑负载均衡，根据20％-80％原则局部更新信息素矩阵，计算出节点上的负载情况，若节点上负载超过80％则减少该节点上的信息素，让蚂蚁选择该节点的概率降低；若节点上的负载小于20％，增加该节点上的信息素，鼓励蚂蚁将任务分派到该节点上；(3c)根据信息素计算出资源节点被选择的概率。2CN109542619A权利要求书2/2页4.如权利要求1中所述的一种面向云计算中心的高效负载均衡优化调度方法，其特征在于，所属步骤6)中具体过程如下：(4a)对于步骤5)中产生的最优解M，随机交换其中m个资源节点上的任务形成新解M'，m随机取2或者3，并计算新解的目标函数F(M')；(4b)比较F(M')与F(M),令Y＝F(M')-F(M)，若Y<0，那么就用M'替代M；否则根据模拟退火算法原则选择是否保留新解M'，若EXP(-Y/T)>random(0,1)，则用M'替代M，否则保留M；其中T为退火温度，并且按照T(t+1)＝λT(t)进行迭代