基于动态自适应蚁群算法的云计算任务调度

摘要：

针对蚁群算法求解云计算任务调度问题存在收敛速度慢和容易陷入局部最优解的缺陷，提出一种动态自适应蚁群算法的云计算任务调度策略。算法在选择资源节点中引入混沌扰乱，依据节点信息素浓度自适应调整信息素挥发因子，由解的优劣性动态更新信息素。当任务数量超过150时，动态自适应蚁群算法与蚁群算法结果相比较，时间效率最大提高319%，资源负载率为0.51。仿真结果表明，所提算法提高了解的收敛速度和全局搜索能力。

关键词：

云计算；蚁群算法；动态自适应；任务调度；混沌扰乱

0引言

云计算任务调度是指在特定的云环境中，根据一定的资源使用规则对用户申请的计算任务进行资源分配和管理[1]。随着云计算技术与应用的迅速发展，云系统规模越来越大，拓扑结构越来越复杂，加上资源的异构性使得如何进行高效云任务调度成为云计算领域中的重要研究课题。已经有文献证明云计算任务调度是一个NP完全问题[2]，可采用启发式算法进行求解，如动态规划算法[3]、遗传算法[4]、免疫进化算法[5]等都取得相应的科研成果。蚁群算法是由意大利学者M.Dorigo等于1991年提出的一种针对难解离散优化问题的元启发式算法[6]，已被广泛应用于旅行商问题（Travelling Salesman Problem， TSP）、多重背包问题、网络路由问题等组合优化问题。众多科研成果表明，蚁群算法求解组合优化问题有明显的自组织性、正反馈性和分布式计算特性，但存在收敛速度慢和易陷入局部最优解的缺陷[7]。

本文结合蚁群算法的不足和云计算任务调度的特点，提出了动态自适应蚁群算法，在云计算资源节点选择策略中引入混沌扰乱算法[8]，使当前解跳离局部极值区，避免局部最优解或停滞。在算法前一阶段，依据资源节点的信息素浓度自适应调整信息素挥发因子，提高解的多样性，保证了资源负载均衡，在算法后期，根据解的优劣性动态更新信息素，显著缩短任务调度时间跨度。

1云计算任务调度问题描述

云计算任务调度本质是将n个相互独立的任务分配到m个异构可用云资源上，使得任务时间跨度最小，资源利用负载均衡。为了深入分析问题，建立如下云任务调度模型。

定义1任务集合J={J1，J2，…，Jn}，表示当前任务队列有n个互相独立的任务，任务大小用百万指令（Million Instructions， MI）衡量，每个任务只能在一个资源上执行。

定义2可用资源，指云计算环境中可用于执行任务的高性能集群、服务器、普通PC或各种处理单元PE。m个可用资源集合表示为P={P1，P2，…，Pm}，资源性能用百万指令每秒（MIPS）表示。

2蚁群算法求解云计算任务调度

蚁群算法的基本原理为：蚂蚁个体间通过信息素交流达到合作。本文以经典的TSP为例说明蚁群算法求解云计算任务调度问题的实现过程。

以G=（V，E）描述平面上n个城市，V为城市集合，E为城市间成本度量集合，假设有m只蚂蚁，Tabuk为禁忌表存放蚂蚁k已访问过的城市，Allowedk={V-Tabuk}为蚂蚁k未经历过的城市。dij表示城市i与城市j的距离，cij（t）为启发函数，表示t时刻蚂蚁从城市i转移到城市j的期望程度，一般取cij（t）=（1/dij）。ηij（t）表示在t时刻城市ij路径上的信息素残留量，初始时刻，各路径上的信息素量相等，设ηij（0）=U（U为常数）。pkij（t）表示在t时刻蚂蚁k从城市i选择城市j的概率：

pkij（t）=[cij（t）]A*[ηij（t）]B∑j∈Allowedk[cij（t）]A*[ηij（t）]B， j∈Allowedk0，其他（1）此处的A和B，是否应该改为希腊字符α和β？这样表达规范些，请明确。

其中：A为期望启发式因子，表示能见度的重要性，反映了蚂蚁在运动过程中启发信息对路径选择的权重影响；B为信息素启发因子，表示轨迹的相对重要性，反映了蚂蚁在行进过程中所积累的信息对运动的影响作用。为了避免信息素残留量过多引起残留信息淹没启发信息，待每只蚂蚁遍历完所有城市后，对残留信息进行更新处理，更新规则如下：

式（2）表示t+n时刻路径ij上的信息素浓度，Q是挥发因子，1-Q为信息素残留因子，Q∈（0，1）。Δηij为本次循环中城市ij间的信息素增量，Δηkij表示蚂蚁k在城市ij间信息素增量，其计算公式为：

Δηkij=W/Lk（4）

其中：W为信息素强度，Lk为蚂蚁k在经过一个迭代的总成本。

基于云计算环境的独特性，本文对TSP与云计算任务调度问题的特征差异进行关联，主要表现在以下3个方面：

1）在TSP中，城市i与城市j有物理路径相连且分布有不同的距离，在云环境中则通过资源活动的相互作用来模拟网络拓扑关系。

2）在TSP中，蚂蚁遍历迭代总成本影响着信息素浓度更新；而在云环境中，通过资源与任务的较优组合相关系数表示信息素浓度。

3）在云环境中以资源的固有属性（计算、存储、通信能力）来表示蚁群算法中的启发信息。

3动态自适应蚁群算法求解云计算任务调度

3.1混沌算法选择策略

混沌现象是一种周期不固定的循环行为，介于确定性与随机性之间，有丰富的时空状态，其动态演变可导致吸引子的转移[9]。混沌算法具有随机性、遍历性、规律性。在组合优化设计研究课题中可利用混沌算法的遍历性克服搜索过程中陷入局部最优解或停滞现象的缺陷。实验采用Logistic映射产生混沌变量[10]，形式如下：

3.2自适应调整信息素挥发因子

在基本蚁群算法中，较优路径上的信息素残留量越来越多，信息素浓度低的路径随挥发因子的作用，浓度越来越低而不被选择，从而降低算法的全局搜索能力。本文算法模拟真实世界蚂蚁信息素挥发现状，自适应调整信息素挥发因子，避免局部最优解。

m只蚂蚁经k次迭代后将云计算环境中所有资源节点按照信息素浓度从大到小顺序排列，存储于数组Pdens中，序号存储于数组Prank中（浓度相同的节点序号相同），假设本次迭代中找到较优分配方案r个，取u=r≠m，则云计算环境中任意有效分配方案有：

3.3动态更新信息素

信息素在较优路径上的不断积累会导致算法求得局部最优解，过早出现停滞现象；反之，过分强调信息素的均匀分布，虽然能提高算法全局搜索能力，在一定程度上避免局部最优和停滞现象，但严重降低收敛速度，破坏算法性能，如何有效保持信息素的适度，成为本研究的又一个突破点。

m只蚂蚁迭代k次后将得到的云任务分配方案存储于数组Psour中，每一种方案的代价从小到大顺序排列存储于数组Pcost中，序号存储于Pnumb中（代价相同的节点序号相同），假设本次迭代中，m只蚂蚁找到有效任务分配方案数量为r，取h=r≠m，则云计算环境中任意有效分配方案有：

3.4算法流程

算法流程描述如下：

4实验仿真

4.1实验模型

实验选择墨尔本大学网格实验室Gridbus项目推出的Cloudsim[12]云计算仿真平台为仿真环境，通过重写DataCenterBroker、Cloudlet等类，对动态自适应蚁群算法进行模拟仿真。在DataCenterBroker类中构造基本蚁群算法，改进蚁群算法[13]和本文算法；创建Test类模拟云系统资源和任务，初始化节点数量为10，资源性能以0.1MIPS递增，任务数量为50，任务大小以1MI递增，Test类调用不同的分配策略来分析各算法的性能差异。实验参数设置如表1所示。