论文部分内容阅读
摘要：针对云计算中的资源分配问题，提出了一种改进的蚁群算法。由于传统的蚁群算法在解决负载均衡问题上存在不足，改进的蚁群算法加入了信息素调节因子，来防止数据中心的计算资源过载。在CloudSim仿真平台上进行实验，结果表明改进蚁群算法的任务时间跨度和负载均衡度都要优于传统的蚁群算法。
关键词：云计算；资源分配；蚁群优化；负载均衡
中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2017）29-0179-02
1 概述
隨着互联网越来越普及，人们日常工作离不开对互联网中海量数据的接收和处理，可是单个计算机的数据处理能力已经无法满足人们工作需求。云计算技术的出现，可以有效地解决这类问题。云计算作为一种创新型的计算方式，通过互联网的高速传送能力，把对数据的处理操作从单个计算机转移到互联网的计算机集群中，这样可以大大缩短数据处理的时间。云计算采用的是按需付费的模式，客户无需自己动手搭建云平台，可以直接在云服务运营商所提供的云平台上部署自己的应用程序。这样减少了很多前期准备工作，节省了时间。同时打破时间和地点的限制，客户可以随时随地在云平台上调试自己的应用程序。云计算作为分布式计算的一种特殊形式，可以使计算能力大幅提升。
算法是解决云计算资源分配问题的一个重要手段，目前一些学者已经对云计算资源分配算法进行了研究，并取得了一定的成果。文献[1]提出了一种基于蚁群优化的资源分配方法，考虑云计算的特点，对任务量进行预测，从而得到最优分配方案。文献[2]针对传统遗传算法收敛慢和早熟的缺点，对遗传算法的染色体编码和适应度函数进行了修改，使得改进后的遗传算法能够更好的解决资源分配问题。文献[3]为了对服务集群的负载均衡进行优化，提出了一种改进粒子群算法的优化策略，将多群体协作和变异粒子逆向运行的思想引入到粒子群算法中，提高了算法的执行效率。文献[4]提出了引入模拟退火算法中的Metropolis接受准则的蚁群算法，根据Metropolis接受准则来接受一部分“劣质”新解，来避免算法陷入局部最优和资源分配更均衡。本文在传统蚁群算法的基础上，对转移概率公式进行了修改，同时加入了信息素调节因子。力求使改进后的蚁群算法执行效率更好，同时负载均衡度更优。
2 改进蚁群算法的资源分配
2.1 问题描述
资源分配可以具体化为将n个云任务有序分配给m个计算资源的过程。
（1） 云任务集合表示为：，表示第i个云任务。
（2） 计算资源的集合为：，表示第j个计算资源。
一个云任务只能在一个计算资源上执行，我们用一个矩阵来表示每个云任务与每个计算资源之间的映射关系：
其中，表示将云任务分配给计算资源执行。
资源分配的宗旨就是确定云任务与计算资源之间合理的分配关系，云任务完成时间和计算资源的负载均衡度是衡量资源分配是否合理的重要指标。
是任务在计算资源上的执行时间。
是计算资源执行任务的时间跨度。
2.2 改进算法描述
（1） 初始化信息素强度和能见度
公式（3）中信息素强度和能见度与节点的计算能力成正比，N是常量。
（2） 蚂蚁下一跳选择城市的概率
公式（4）定义了蚂蚁k从任务i出发，选择资源节点j的概率。
这里我们定义一个，值由公式（4）决定，对路径上残留信息素有重大的影响。根据我们新定义的，转移概率能够通过和自适应地调整。是所有边信息素的平均值，因此可以作为一个调节因子。如果值越小，蚂蚁选择信息素较小路径通过的可能性越大。的设定可以使算法随机搜索，有效避免算法陷入局部最优。
（3） 信息素更新规则
为了满足云计算资源分配的实际需求，我们对信息素更新公式进行了修改。公式（6）和公式（7）分别是修改以后的局部信息素更新公式和全局信息素更新公式。这里，D是常量，表示计算资源执行任务的完成时间，表示计算资源执行任务的最短完成时间。
（4） 负载均衡调节机制
为了避免过多的任务都分配到一个计算资源上，从而造成该计算资源过载。我们在这里定义了一个信息素调节因子FA。假如将任务i分配给计算资源j执行，计算资源j的信息素我们通过公式（9）去更新，而未被分配任务i计算资源的信息素我们通过公式（10）去更新。如果计算资源在之前的迭代中超载，计算资源的将比其他计算资源的大，这样一来计算资源的信息素调节因子FA将比其他计算资源的小。那么，在下次迭代中再把任务分配给计算资源可能性就会降低。这种负载均衡调节机制保证了在多次迭代中，为计算资源均匀分配任务。我们通过公式（11）来评价负载均衡度，表示计算资源分配到云任务的数量，表示计算资源处理云任务的能力。
3 仿真实验及结果分析
为了证明改进后的蚁群算法的有效性，我们对云仿真软件CloudSim 3.1进行了功能扩展，并重写了Cloudlet等类方法，同时对实验参数进行了设置。计算节点处理能力的取值范围是300MIPS～600MIPS，云任务的大小30000MB～80000MB，输出数据量300MB/S。启发因子是0.7，期望启发因子是0.7，信息素浓度挥发系数是0.3，蚂蚁的个数是60，最大迭代次数是60。
任务数从20增加到100，传统蚁群算法（ACO）、文献[7]提出的引入Metropolis接受准则的蚁群算法（MACO）和本文提出的改进后的蚁群算法（LBACO）的任务时间跨度如图1所示。从图1可以看出，在任务数量规模较小的时候，三种算法的任务时间跨度相差不大。在任务数量为30的时候，三种算法的任务时间跨度基本相同。而当任务数量逐渐增加到80以上的时候，LBACO算法的任务时间跨度明显要小于ACO算法和MACO算法。
接下来我们看任务规模较大的情况，我们将任务数从50逐渐增加至350，ACO算法、MACO算法和LBACO算法的负载均衡度如图2所示。从图2可以看出，在任务数量较小的时候，三种算法的负载均衡度之间相差不多。但在任务规模较大的时候，LBACO算法的负载均衡度要比ACO算法和MACO算法更好。
4 结束语
本文对传统蚁群算法进行改进，来解决云计算资源分配问题。改进后的算法在任务时间跨度和负载均衡度这两方面，都有较大改善。可是改进后的算法还存在两点不足：第一，改进后的算法仍然存在迭代初期盲目性的问题，这个需要使用其他算法与蚁群算法融合。第二，改进后的算法只是以任务完成时间最小为原则，而没有考虑执行开销等其他因素。
参考文献：
[1] 华夏渝，郑骏，胡文心. 基于云计算环境的蚁群优化计算资源分配算法[J].华东师范大学学报：自然科学版，2010，1（1）：127-134.
[2] 刘愉，赵志文，李小兰，等. 云计算环境中优化遗传算法的资源调度策略[J].北京师范大学学报：自然科学版，2012，48（4）：378-383.
[3] 刘万军，张孟华. 云中基于MPSO算法的云计算资源调度策略[J].计算机工程，2011，37（11）：43-45.
[4] 苗培. 蚁群优化算法在云计算资源分配上的应用[J].山东师范大学，2015.
关键词：云计算；资源分配；蚁群优化；负载均衡
中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2017）29-0179-02
1 概述
隨着互联网越来越普及，人们日常工作离不开对互联网中海量数据的接收和处理，可是单个计算机的数据处理能力已经无法满足人们工作需求。云计算技术的出现，可以有效地解决这类问题。云计算作为一种创新型的计算方式，通过互联网的高速传送能力，把对数据的处理操作从单个计算机转移到互联网的计算机集群中，这样可以大大缩短数据处理的时间。云计算采用的是按需付费的模式，客户无需自己动手搭建云平台，可以直接在云服务运营商所提供的云平台上部署自己的应用程序。这样减少了很多前期准备工作，节省了时间。同时打破时间和地点的限制，客户可以随时随地在云平台上调试自己的应用程序。云计算作为分布式计算的一种特殊形式，可以使计算能力大幅提升。
算法是解决云计算资源分配问题的一个重要手段，目前一些学者已经对云计算资源分配算法进行了研究，并取得了一定的成果。文献[1]提出了一种基于蚁群优化的资源分配方法，考虑云计算的特点，对任务量进行预测，从而得到最优分配方案。文献[2]针对传统遗传算法收敛慢和早熟的缺点，对遗传算法的染色体编码和适应度函数进行了修改，使得改进后的遗传算法能够更好的解决资源分配问题。文献[3]为了对服务集群的负载均衡进行优化，提出了一种改进粒子群算法的优化策略，将多群体协作和变异粒子逆向运行的思想引入到粒子群算法中，提高了算法的执行效率。文献[4]提出了引入模拟退火算法中的Metropolis接受准则的蚁群算法，根据Metropolis接受准则来接受一部分“劣质”新解，来避免算法陷入局部最优和资源分配更均衡。本文在传统蚁群算法的基础上，对转移概率公式进行了修改，同时加入了信息素调节因子。力求使改进后的蚁群算法执行效率更好，同时负载均衡度更优。
2 改进蚁群算法的资源分配
2.1 问题描述
资源分配可以具体化为将n个云任务有序分配给m个计算资源的过程。
（1） 云任务集合表示为：，表示第i个云任务。
（2） 计算资源的集合为：，表示第j个计算资源。
一个云任务只能在一个计算资源上执行，我们用一个矩阵来表示每个云任务与每个计算资源之间的映射关系：
其中，表示将云任务分配给计算资源执行。
资源分配的宗旨就是确定云任务与计算资源之间合理的分配关系，云任务完成时间和计算资源的负载均衡度是衡量资源分配是否合理的重要指标。
是任务在计算资源上的执行时间。
是计算资源执行任务的时间跨度。
2.2 改进算法描述
（1） 初始化信息素强度和能见度
公式（3）中信息素强度和能见度与节点的计算能力成正比，N是常量。
（2） 蚂蚁下一跳选择城市的概率
公式（4）定义了蚂蚁k从任务i出发，选择资源节点j的概率。
这里我们定义一个，值由公式（4）决定，对路径上残留信息素有重大的影响。根据我们新定义的，转移概率能够通过和自适应地调整。是所有边信息素的平均值，因此可以作为一个调节因子。如果值越小，蚂蚁选择信息素较小路径通过的可能性越大。的设定可以使算法随机搜索，有效避免算法陷入局部最优。
（3） 信息素更新规则
为了满足云计算资源分配的实际需求，我们对信息素更新公式进行了修改。公式（6）和公式（7）分别是修改以后的局部信息素更新公式和全局信息素更新公式。这里，D是常量，表示计算资源执行任务的完成时间，表示计算资源执行任务的最短完成时间。
（4） 负载均衡调节机制
为了避免过多的任务都分配到一个计算资源上，从而造成该计算资源过载。我们在这里定义了一个信息素调节因子FA。假如将任务i分配给计算资源j执行，计算资源j的信息素我们通过公式（9）去更新，而未被分配任务i计算资源的信息素我们通过公式（10）去更新。如果计算资源在之前的迭代中超载，计算资源的将比其他计算资源的大，这样一来计算资源的信息素调节因子FA将比其他计算资源的小。那么，在下次迭代中再把任务分配给计算资源可能性就会降低。这种负载均衡调节机制保证了在多次迭代中，为计算资源均匀分配任务。我们通过公式（11）来评价负载均衡度，表示计算资源分配到云任务的数量，表示计算资源处理云任务的能力。
3 仿真实验及结果分析
为了证明改进后的蚁群算法的有效性，我们对云仿真软件CloudSim 3.1进行了功能扩展，并重写了Cloudlet等类方法，同时对实验参数进行了设置。计算节点处理能力的取值范围是300MIPS～600MIPS，云任务的大小30000MB～80000MB，输出数据量300MB/S。启发因子是0.7，期望启发因子是0.7，信息素浓度挥发系数是0.3，蚂蚁的个数是60，最大迭代次数是60。
任务数从20增加到100，传统蚁群算法（ACO）、文献[7]提出的引入Metropolis接受准则的蚁群算法（MACO）和本文提出的改进后的蚁群算法（LBACO）的任务时间跨度如图1所示。从图1可以看出，在任务数量规模较小的时候，三种算法的任务时间跨度相差不大。在任务数量为30的时候，三种算法的任务时间跨度基本相同。而当任务数量逐渐增加到80以上的时候，LBACO算法的任务时间跨度明显要小于ACO算法和MACO算法。
接下来我们看任务规模较大的情况，我们将任务数从50逐渐增加至350，ACO算法、MACO算法和LBACO算法的负载均衡度如图2所示。从图2可以看出，在任务数量较小的时候，三种算法的负载均衡度之间相差不多。但在任务规模较大的时候，LBACO算法的负载均衡度要比ACO算法和MACO算法更好。
4 结束语
本文对传统蚁群算法进行改进，来解决云计算资源分配问题。改进后的算法在任务时间跨度和负载均衡度这两方面，都有较大改善。可是改进后的算法还存在两点不足：第一，改进后的算法仍然存在迭代初期盲目性的问题，这个需要使用其他算法与蚁群算法融合。第二，改进后的算法只是以任务完成时间最小为原则，而没有考虑执行开销等其他因素。
参考文献：
[1] 华夏渝，郑骏，胡文心. 基于云计算环境的蚁群优化计算资源分配算法[J].华东师范大学学报：自然科学版，2010，1（1）：127-134.
[2] 刘愉，赵志文，李小兰，等. 云计算环境中优化遗传算法的资源调度策略[J].北京师范大学学报：自然科学版，2012，48（4）：378-383.
[3] 刘万军，张孟华. 云中基于MPSO算法的云计算资源调度策略[J].计算机工程，2011，37（11）：43-45.
[4] 苗培. 蚁群优化算法在云计算资源分配上的应用[J].山东师范大学，2015.