基于云计算的ACO-K中心点资源优化算法

孟 颖，罗 可，刘建华，姚丽娟

长沙理工大学 计算机与通信工程学院，长沙 410114

基于云计算的ACO-K中心点资源优化算法

孟 颖，罗 可，刘建华，姚丽娟

长沙理工大学 计算机与通信工程学院，长沙 410114

1 引言

云计算[1]作为当前的一个研究热点，主流的信息技术公司，如Amazon，IBM，Google，都对此先后提出各自的云计算基础架构。云计算（cloud computing）是指通过互联网连接的超级计算模式，包含分布式处理（distributed computing）、并行处理（parallel computing）和网格计算（grid computing）的相关技术。云计算是一种新兴的计算模型，是集分布式操作系统、分布式数据库、网格计算等技术于一体的计算机网络模型，它可以充分地利用硬件资源和软件资源。

云计算代表IT领域向集约化、规模化与专业化道路发展的趋势，是IT领域正在发生的深刻变革[2]。当前，云计算发展还面临着许多问题。随着云计算的不断普及，计算资源问题的重要性逐步上升，已成为制约其发展的重要因素。然而，存储资源如何快速地路由，减少路由间的动态负荷，兼顾全局负载平衡，得到一组最优的计算资源，是人们有待解决的难题。

ACO（Ant Colony algorithm）是一种仿生优化算法，它模拟蚂蚁的觅食行为来解决复杂的组合优化问题，具有智能搜索、全局优化、鲁棒性、分布式计算和容易与其他算法相结合等优点。ACO的应用范围几乎已经涉及到各个优化领域。K中心点（K-medoids）算法属于划分方法的一种，在处理异常数据和噪声数据方面更为鲁棒，不易受极端数据的影响，在聚类算法中应用很广泛。

ACO-K中心点算法是一种新的聚类算法，它结合这两种算法的优点，全局搜索能力强，处理异常数据优越，数据之间的差异性更小。根据云计算环境的特点，本文提出一种基于云计算环境下的ACO-K中心点资源分配优化算法。该算法能够在云计算中快速、合理地路由，减少动态负荷，兼顾全局负载平衡，得到最优的计算资源，提高云计算的效率。

2 预备知识

2.1 云计算简介

IBM公司在技术白皮书“Cloud Computing”中对云计算的定义[3]：云计算一词用来同时描述一个系统平台或者一种类型的应用程序。一个云计算的平台按需进行动态地部署（provision）、配置（configuration）、重新配置（reconfigure）以及取消服务（deprivation）等。高级的云计算通常包含一些其他的计算资源，例如存储区域网络（SANs）、网络设备、防火墙以及其他安全设备等。云计算描述了一种可以通过互联网Internet进行访问的可扩展应用程序，使用大规模的数据中心以及功能强劲的服务器来运行网络应用程序与网络服务。

根据云计算环境的特点[4]，提供设备的规模会根据用户对资源的需求量来动态地增大或者缩小。比如用户需要用N个进程，云计算环境就分配给该用户R的计算资源；如果用户将进程数增加到2N，则用户的计算资源占有量将动态地扩展到2R。云计算体现了“网络就是计算机”的思想。将大量计算资源、存储资源与软件资源链接在一起，形成巨大规模的共享虚拟IT资源[5]。在云计算环境中，带宽需要被充分地利用，一个行之有效的方法便是尽量为存储节点的数据资源分配本地的计算资源。所以，云计算对计算资源分配算法有着苛刻的要求。

本文综合考虑云计算的特点，提出ACO-K中心点资源分配优化算法。通过对存储节点分配最合适的计算资源，来最大程度地提高云计算的效率。尽量为存有用户镜像的存储节点，分配本地或邻近带宽需求少的计算节点。

2.2 ACO算法简介

蚁群算法是一种受自然界生物的行为启发而产生的“自然”算法[6]，它模拟蚂蚁的觅食行为来解决复杂的组合优化问题。蚁群算法具有智能搜索、全局优化、鲁棒性、分布式计算和容易与其他算法相结合等优点，基本原理如图1。其中，A为蚁穴，B为食源。

图1 蚁群聚类示意图

蚂蚁在觅食过程中能在所经过的路径上留下一种称为信息素的物质，而蚂蚁能够感知这种物质及其强度，并以此指导自己的运动方向，它们会朝着该物质强度高的方向移动[7]。因此，由大量蚂蚁组成的集体觅食行为表现出：某一路径越短，该路径上走过的蚂蚁就越多，则留下的信息素强度就越大，后来的蚂蚁选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息交流来选择最短路径并达到搜索食物的目的。

2.3 K中心点算法简介

K-中心点聚类算法的核心是中心点的选择[8]。假设聚类C原先的中心点是Oc_old，现拟改为Oc_new，根据数据对象属于和其距离最近的聚类原则，可能引起各数据对象所属聚类的情况发生调整。对于原先聚类C中的数据对象p可能有如下情况：

（1）p与Oc_new的距离仍然小于其他聚类的中心点的距离，因此p仍属于聚类C如图2（a），用Oc_new代替Oc_old，数据对象p的代价为：d(p，Oc_new)-d(p，Oc_old)，d表示两点之间的距离。

（2）p与其他某一聚类r的中心点的距离最短，则p将改属于聚类r如图2（b），用Oc_new代替Oc_old，数据对象p的代价为：d(p，Or)-d(p，Oc_old)，其中Or为聚类r的中心点，此时代价为正值。

类似地，原先聚类C外的任意数据对象 p也可能有两种情况：

（1）p仍然与它原先所属的聚类的中心点距离最短，则p仍将属于原先的聚类如图2（c），用Oc_new代替Oc_old，数据对象p的代价不变。

（2）在所有聚类的中心点中，p与Oc_new的距离最短，则p将改属于聚类Oc_new如图2（d），用Oc_new代替Oc_old，数据对象p的代价为：d(p，Oc_new)-d(p，Or)，其中Or为聚类r的中心点，此时代价为负值。

图2 K中心优化示意图

2.4 ACO-K中心点算法简介

ACO-K中心点算法基本原理是从蚁群中随机选取m个对象，计算任意两个对象之间的距离，确定蚁群间的距离和最初的聚类中心，并将此中心作为蚁群的历史最优位置，使用K中心点法对历史最优位置进行聚类分析，找到新的聚类中心，来代替蚁群聚类中心。

ACO-K中心点聚类算法：

步骤1对蚁群进行初始化操作，选择蚂蚁数目为m，NC-max为最大迭代次数，m个蚂蚁作为初始中心点，设初始中心点为(M1，M2，…，Mm)。

步骤3根据K-medoids法对蚁群的历史最优位置进行新的聚类分析，确定每只蚂蚁所在的聚类以及类与类之间的中心点。

步骤4对形成的新蚁群按照步骤2的方法，计算每只蚂蚁代表的最优解，更新蚁群的历史最优位置和全局最优解。

步骤5重新计算任意蚂蚁之间的欧氏距离，确定新的聚类中心Oj，找到最优路径。

步骤6如果达到结束条件（取得最终的最优聚类中心或者最优路径），则结束，否则转向步骤3。

3 算法描述

3.1 资源分配策略

云计算的框架是每个单元由一个单独的主作业调度节点和该单元所辖各个节点集群中的一个从任务分配节点共同组成[9]。主节点负责调度构成一个作业的所有任务，这些任务的数据资源分布在不同从节点的存储资源上的用户镜像分片中，主节点监控它们的执行。从节点负责执行由主节点指派的任务。在接到主节点的指派之后，从节点开始为其下属的存储节点寻找合适的计算节点。首先，从节点开始检测自身的计算资源余量，如果其剩余计算资源足以满足用户提交作业的用量，则优先分配自身的计算资源；如果资源已经耗尽或者已不足以满足给用户的最小计算资源量，则从节点报请主节点搜寻云环境中其他合适的计算资源。

本文将ACO-K中心点资源分配优化算法应用到这一环节中。为了减少网络开销，在一定范围内进行搜索。如果云环境中仍然没有合适资源，则主节点移走该节点集群中的用户数据镜像分片。

3.2 资源优劣度分析

将节点域（Slave）看作是一个无向图G(V，E)[10]，其中，V是区域Area中所有Slave节点的集合，E是连接各Slave节点的网络集合。寻找合适的计算节点，即在E中寻找一条最优的路径e∈Area。从以下几个方面分析资源优劣度。

执行时间：time_cost(e)，指路径e尽头的计算资源处理该作业预计的耗费时间。

网络带宽：bandwidth(e)，指路径e所提供的网络最大带宽。

网络延迟：delay(e)，指路径e产生的最大网络延迟。选择资源和路径的过程就是寻找满足限制条件的尽量小的路径和资源。资源选择的约束函数为：

其中，A，B，C为三个约束条件的权重；TL，EL和DL为其边界限制条件。

当各个计算资源完成本次作业执行速度，对其速度进行预测时，由于每个计算节点当前的负载程度已知，并且上一次完成作业时的平均负载程度也能够查阅。设定执行速度为：

其中，RVakm(k)为第m号计算资源的第k次预测执行速度，ak为第k次预测时的系统负载程度，RVakm(k)为第m号计算资源的第k次实际的执行速度，θ为调节参数，用来调节在不同云环境中经验值和预测值的比重，使预测达到最优。

3.3 ACO-K中心点算法找最优计算资源

3.3.1 算法思想

由于在云计算环境中，资源的具体情况不可知，利用ACO-K中心点算法，能够在未知的网络拓扑中查找出计算资源，并选择最合适的一个或者几个分配给用户作业，直到满足用户需求。当查找开始时，由所有的Slave节点发出查询消息，这些消息扮演着蚁群算法中蚂蚁的角色，所有的蚂蚁都遵从信息素多的节点概率大，信息素少的节点概率小的原则选择下一跳的节点，并在经过的路径节点上留下信息素。

假设t时刻，在i节点的蚂蚁k遵循公式（3），计算下一跳各个节点n的可能性：

其中，τij(t)为t时刻蚂蚁在i节点上观察到 j节点的信息素强度，在分布式环境下充分利用蚁群算法的分布式特性及本质并行性进行操作和实现；pkij为蚂蚁k在i节点选择j节点的概率；avid(k)为蚂蚁k的回避列表，avid(k)以单项列表的形式给出，大小为蚁群的最大规模，Lqij为从i节点到 j节点的线路质量，α、β、γ分别为信息素、线路质量和计算能力预测值相对权重；q在0至1之间随机选取，q0为初始化时所给的阈值。

3.3.2 信息素更新

随着时间的推移，以前留下的信息素逐渐消失，为了及时反映信息素的变化，用局部更新策略来改变节点上的信息素强度。

本次觅食相遇并完成用户连接，将本次觅食最短通道上的信息素按下式调整，更新全局信息素。

其中，ρ为局部信息素挥发系数，ε为全局信息素挥发系数，α为信息素的相对权重。

3.4 算法步骤与流程图

算法步骤：

步骤1对蚁群进行初始化操作。设置蚁群最大规模，选择蚂蚁Ai数目，初始中心点为(M1，M2，…，Mm)。

步骤2在存储资源所在从节点中选择带信息素的蚂蚁，并判断信息素强度。

步骤3该蚁群通过公式（3）、（4）、（5）来选择下一跳的节点。

步骤4当蚂蚁Ai进入一个Slave节点Vj时，Vj将 Ai设置到回避列表avid(k)中，回避列表大小由蚂蚁的数量决定，并通过限制条件公式（1），判断Vj是否为有效节点。如果Vj满足限制条件，则标记为有效节点，并用公式（6）、（7）更新信息素。如果Vj不是有效节点，则转向步骤3。

步骤5将步骤4得到的有效节点进行资源分配，分配给用户作业调度，为防止算法过快收敛，用公式（2）对其速度进行预测。

步骤6当Ai全在回避列表或者Slave节点未与第二个节点相连，蚂蚁Ai无法继续前进，该蚂蚁自动消亡。若Ai满足终止条件，算法结束，否则转向步骤2；若Ai不全在回避列表，则转向步骤3。

步骤7如果达到终止条件（找到的计算资源不满足用户要求或者蚂蚁全部消亡），则算法结束，否则转向步骤2。

算法结束时，所有计算资源不足以满足协议（SLA）中的用户要求，则考虑转移该存储节点的用户镜像分片至其他存储节点。按有效资源集将作业分配到相关计算资源节点，并尽量为高有效度的节点分配多的作业，以减低网络的负载。算法流程图如图3。

图3 算法流程图

3.5 算法复杂度分析

3.5.1 算法的空间复杂度

算法的空间复杂度：蚁群最大规模Max_m，中心点个数m，节点数Num_Slave，聚类个数n。由于蚁群最大规模Max_m比聚类个数n要大得多，所以，算法总体的空间复杂度T=O(Max_m×Num_Slave×m)。

3.5.2 算法的时间复杂度

初始化种群时间复杂度为T=O(n×Max_m)，执行速度时间复杂度为T=O(V2×n)，选择下一跳节点时间复杂度为T=O(k×p)，信息素更新时间复杂度为：T=O(τ2×ρ+ τ×ρ)，所以本文算法的总体时间复杂度可写为：To=O(n3)。

4 仿真实验

4.1 实验环境

实验环境为Inter®CoreTM2 Duo 2.93 GHz，RAM3 GB，硬盘320 GB，100 MB网络带宽，操作系统Windows XP。用Gridsim来模拟一个云计算的局部域，以检查ACO-K中心点算法在这种特殊的网格环境中的运行情况。

通过Gridsim中的GridResource类和一系列的辅助类，模拟云计算的网络资源，构建较拟真的云环境。通过设定Grid Information Services类来管理资源。

4.2 实验结果

下面分别用退火算法（SA）、遗传算法（GA）、蚁群算法（ACO）[11]与本文的ACO-K中心点算法进行对比分析，每种算法运行20次取其平均值，来比较实验结果的优越性。

[12]对蚂蚁数据结构进行设置如表1。对上述四种算法主要参数的设置如表2，考虑到开销问题本文选取50只蚂蚁。每种算法搜寻20%可用节点的仿真结果如图4，搜寻5%可用节点的仿真结果如图5，四种算法的模拟结果连续曲线图如图6。

表1 蚂蚁数据结构表

表2 算法主要参数取值表

图4 搜寻20%可用节点仿真图

在1 000个节点中模拟在一定比例的有效节点中搜寻50%节点分配给用户作业。比如有效节点比例为20%，其数量为200个。只要搜寻到100个有效节点即认为分配成功。

图5 搜寻5%可用节点仿真图

图6 仿真结果曲线图

从图6中可以看出，横坐标为有效节点的比率，纵坐标为有效节点成功分配作业的耗时，ACO-K中心点算法在节点较多，有效资源较少的情况下，鼓励蚂蚁选择负载小的链路，以达到网络负载平衡，工作效率明显比另外几种算法效率高。所以本文ACO-K中心点算法在云计算环境中更具有优势，大大提高了云计算的效率。

5 结束语

本文提出了基于云计算环境下的ACO-K中心点资源分配优化算法，该算法能够针对云环境的大规模性、共享性和动态性等特点，在云计算中快速、合理地路由，为用户分配最优资源，通过蚂蚁选择负载小的链路，克服云计算不能兼顾全局负载平衡的问题。最后，通过仿真实验，分析带宽占用、线路质量和响应时间等因素对资源分配的影响，并将SA、GA、ACO与ACO-K中心点算法进行对比分析，验证了ACO-K中心点资源分配优化算法能够在云计算环境中动态地为用户的作业分片搜寻并分配计算资源，有效地完成计算资源搜索与分配的工作，从而提高云计算的效率。但是，如何减少蚁群搜索时间，降低搜索成本和时间复杂度，将是下一步研究的重点。

参考文献：

[1]Tian Guanhua，Meng Dan，Zhan Jianfeng.Reliable resource provision policy for cloud computing[J].Chinese Journal of Computers，2010，33（10）：1859-1872.

[2]Chen Kang，Zheng Weimin.Cloud computing：system instances and current research[J].Journal of Software，2009，20（5）：1337-1348.

[3]Boss G，Malladi P，Quan D，et al.Cloud computing[Z].[S.l.]：IBM，2007：4-6.

[4]Ian F，Yong Z，Ioan R，et a1.Cloud computing and grid computing 360-degree compared[C]//Grid Computing Environments Workshop.[S.l.]：IEEE Press，2008：1-10.

[5]Feng D G，Zhang M，Zhang Y，et al.Study on cloud computing security[J].Journal of Software，2011，22（1）：71-83.

[6]徐晓华，陈凌.一种自适应的蚂蚁聚类算法[J].软件学报，2006，17（9）：1884-1889.

[7]刘波，潘久辉.基于蚁群优化的分类算法的研究[J].计算机应用与软件，2007（24）：50-53.

[8]孙胜，王元珍.基于核的自适应K-Medoids聚类[J].计算机工程与设计，2009，30（3）：674-688.

[9]郑湃，崔立真，王海洋，等.云计算环境下面向数据密集型应用的数据布局策略与方法[J].计算机学报，2010，33（8）：1472-1480.

[10]史恒亮，白光一，唐振民，等.基于蚁群优化算法的云数据库动态路径规划[J].计算机科学，2010，37（5）：143-145.

[11]华夏渝，郑骏，胡文心.基于云计算环境的蚁群优化计算资源分配算法[J].华东师范大学学报，2010（1）：127-134.

[12]Pan Daru，Yuan Yanbo.ImprovedQoS routing algorithm based on the AntNet[J].Mini-Micro Systems，2006，27（7）：1169-1174.

MENG Ying,LUO Ke,LIU Jianhua,YAO Lijuan

Institute of Computer and Communication Engineering,Changsha University of Sciences and Technology,Changsha 410114,China

Cloud computing has

increasingly attention from network computing model research,which can realize several kinds of resource sharing and dynamic resource allocation.However,how to effectively route storage resource in cloud,reduce dynamic load and take into account global load balancing are important problems to be solved.ACO is a bionics optimization algorithm with advantages of strong robustness,intelligent search,global optimization,easy to combine with other algorithms. K-medoids is an improved algorithm of k-means,of strong robustness and less susceptible to the impact of extreme data.Combined with priorities of these two algorithms,this paper proposes a kind of ACO-K-medoids resource allocation and optimization algorithm based on cloud computing.The algorithm can get the optimal computing resources and improve efficiency of cloud computing.Simulation experiments in the end of paper verify the efficiency of this algorithm.

cloud computing;resource allocation;K-medoids algorithm;ant colony algorithm;dynamic load

云计算是计算网络模型研究的热点领域，能实现几种资源共享和资源动态配置。然而，云计算中存储资源如何快速路由，减少动态负荷，兼顾全局负载平衡是有待解决的问题。ACO是一种仿生优化算法，具有健壮性强、智能搜索、全局优化、易与其他算法结合等优点。K中心点算法是K均值的改进算法，鲁棒性强，不易受极端数据的影响。结合这两种算法的优点，提出一种基于云计算环境下的ACO-K中心点资源分配优化算法，得到最优的计算资源，提高云计算的效率。通过仿真验证了该算法的有效性。

云计算；资源分配；K中心点算法；蚁群算法（ACO）；动态负荷

A

TP391

10.3778/j.issn.1002-8331.1108-0378

MENG Ying,LUO Ke,LIU Jianhua,et al.ACO-K medoids resource optimization algorithm based on cloud computing. Computer Engineering and Applications,2013,49（5）：103-107.

国家自然科学基金（No.11171095，No.10871031）；湖南省自然科学衡阳联合基金（No.10JJ8008）；湖南省科技计划项目（No.2011FJ3051）；湖南省教育厅重点项目（No.10A015）。

孟颖（1984—），女，硕士，主要研究方向为数据挖掘、计算机网络等；罗可（1961—），男，博士，教授，研究方向为数据挖掘、计算机应用等；刘建华（1985—），男，硕士，研究方向为电力系统运行与控制；姚丽娟（1985—），女，硕士，研究方向为数据挖掘。E-mail：kfmengying@126.com

2011-08-26

2011-10-14

1002-8331（2013）05-0103-05