基于多层图划分的云环境软件部署管理算法  

Hybrid software deployment management algorithm based on multilevel graph partitioning in cloud environment

作　　者：戴伟[1,2] 刘华[1] 

机构地区：[1]华中科技大学管理学院,湖北武汉430074 [2]湖北理工学院经济与管理学院,湖北黄石435003

出　　处：《中南大学学报（自然科学版）》2016年第5期1565-1572,共8页Journal of Central South University:Science and Technology

基　　金：教育部人文社会科学研究青年基金资助项目(13YJCZH028)~~

摘　　要：针对在云服务器上软件构件分配时需要最大限度地减少所需带宽的问题,提出一种基于多层图划分算法的混合算法,来解决云计算环境中的软件部署问题。该算法对重边匹配(HEM)算法进行改进,同时添加1个新的约束条件来进行粗化,且使用类似KL的算法进行细分,最后结合退火算法从而实现对图划分算法的重新设计和评估。与传统的图划分相比,本文提出的算法考虑到基础设施的异构性,因此不局限于平衡划分。实验仿真结果表明:相比传统的KL图划分算法,提出的混合算法在执行时间和求解质量之间取得很好的平衡,综合性能优于传统算法。To allocate the software components to the appropriate cloud servers at the same time of minimizing the required bandwidth, a hybrid algorithm based on multi-layer graph partitioning algorithm was proposed for solving the software deployment issues in cloud computing environment. This algorithm improves the heavy-edge matching（HEM） algorithm, adds a new constraint for coarsening, conducts segmentation using the algorithm similar to KL, and finally achieves the re-design and assessment for graph partitioning algorithm in combination with annealing algorithm. Compared with traditional graph partitioning, the proposed algorithm takes into account the heterogeneity of the infrastructure, and so it is not limited to the balance partitioning. The simulation results of test show that compared with the traditional KL graph partitioning algorithm, the proposed hybrid algorithm can achieve a good balance between execution time and solution quality, and so its overall performance is better than that of the traditional algorithms.

关 键 词：云计算 图划分算法 退火算法 软件部署 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]