改进蚁群算法的Storm任务调度优化

Task Scheduling Optimization of Storm Based on Improved Ant Colony Algorithm

摘要:

Apache Storm 默认任务调度机制是采用Round-Robin（轮询）的方法对各个节点平均分配任务，由于默认调度无法获取集群整体的运行状态，导致节点间资源分配不合理。针对该问题，利用蚁群算法在NP-hard问题上的优势结合Storm本身拓扑特点，提出了改进蚁群算法在Storm任务调度中的优化方案。通过大量实验找到了启发因子α与β的最佳取值，并测得改进后蚁群算法在Storm任务调度中的最佳迭代次数；引入Sigmoid函数改进了挥发因子ρ，使其可以随着程序运行自适应调节。从而降低了各个节点CPU的负载，同时提高了各节点之间负载均衡，加快了任务调度效率。实验结果表明改进后的蚁群算法和Storm默认的轮询调度算法在平均CPU负载上降低了26%，同时CPU使用标准差降低了3.5%，在算法效率上比Storm默认的轮询调度算法提高了21.6%。

Abstract:

Apache Storm's default task scheduling mechanism uses Round-Robin (Polling) to distribute tasks to each node evenly. The default scheduling cannot obtain the overall running state of the cluster, resulting in unreasonable resource allocation between nodes. Aiming at this problem, the advantages of ant colony algorithm on NP-hard problem combined with the topology characteristics of Storm itself are proposed. The optimization scheme of improved ant colony algorithm in Storm task scheduling is proposed. The optimal values of heuristic factors α and β were found by a large number of experiments, and the optimal number of iterations of the improved ant colony algorithm in Storm task scheduling was measured. The Sigmoid function was introduced to improve the volatilization factor ρ, so that it can be used with the program. Run adaptive adjustment. Thereby reducing the load of each node CPU, and improving load balancing between nodes, speeding up task scheduling efficiency. The experimental results show that the improved ant colony algorithm and Storm's default polling scheduling algorithm reduce the average CPU load by 26%, while the CPU standard deviation is reduced by 3.5%. The algorithm efficiency is higher than Storm's default polling scheduling algorithm22.6%.