改进蚁群算法在云环境下路径优化设计

陈真

（韩山师范学院潮州师范分院，广东潮州521021）

改进蚁群算法在云环境下路径优化设计

陈真

（韩山师范学院潮州师范分院，广东潮州521021）

文中针对云计算环境中的资源分配问题，提出一种改进蚁群优化的云计算资源分配算法，通过分析诸如带宽占用、网络负载和响应时间等因素对云端资源分配的影响，并结合云计算平台的特点，优化云环境下路径的选择.仿真实验结果表明，改进后的蚁群算法能够在云中快速、合理地找到云端所需访问的数据库，并能够优化相应的搜索性能，减少搜索时间，降低云数据库整体网络负载，获得比其他一些针对云计算的分配算法具有更优的效率.

云计算；网络负载；蚁群算法

0 引言

随着云计算的应用及推广，云计算的规模将呈现爆发式增长，如何提高用户对云资源的访问，确保对云上的延迟敏感的作业在也能够得以很好地运行是个关键问题.

蚁群算法是一种模拟蚂蚁行为特征的仿生优化算法[1-2].它通过蚂蚁在觅食路径上留下的信息素的积累来寻找复杂的最优途径问题，目前已被广泛应用于旅行商问题(TSP)、网络路由、二次分配、属性约简[3]等问题的求解，具有正反馈、鲁棒性、并行计算及易移植等优点.然而，该算法也存在一些不足，如在处理规模较大的系统时，往往无法实现对全局空间的充分搜索，容易陷入局部最优解，且初期搜索时间偏长等.同样，对于云计算网络服务中，通过某一条服务器路径购买计算资源的人越多，将造成局部网络负载越重，网络中路径搜索陷入局部最优解，无法找到全局最优解，最优路径上用户数量巨大，负载过重，可能导致局部网络拥塞，甚至整个网络瘫痪，使厂商损失惨重，获得的利润剧减甚至出现亏损情况等.

因此，若能根据用户作业需求，将任务资源实时动态的分配到相关计算资源节点将会大大地提高云计算环境中的网络整体性能.文中提出改进蚁群算法在云环境下路径优化设计，该算法利用蚂蚁觅食时具有找到最短路径的特性，将它应用于网络负载平衡数学模型加以模拟，能够在云中快速、合理地找到所需访问的数据库，避免网络路径搜索陷入局部最优解，无法找到全局最优解，导致拥塞，甚至整个网络瘫痪等负面影响，该方法减少云数据库数路由的动态负荷，在一定程度上提高云计算的效率.

1 基本蚁群算法及定义

定义1anti={1，2，…，k,…,m}表示一个蚁群的集合，其中k表示第k只蚂蚁，Pk表示第k只蚂蚁路径，当m只蚂蚁遍历完所有路径，求出解集中最示第k只蚂蚁路径距离，记min(k，Pk，Lk)为此解集中的最优解，则Lk-min为蚂蚁k已走过的最短路径.

推论1蚂蚁家族中m只蚂蚁从起点出发，遍历完所有节点回到原点，将其中遍历最短路径的那只蚂蚁作为繁殖蚂蚁；根据定义1，当繁殖蚂蚁完成一轮迭代更新后，所有弧上的信息素都要挥发，但有下限值，记为τmin（k，Pk，Lk）.

2 云计算基础设施服务的资源分配

由于在整个云环境资源和结构分布及其实际情况比较复杂，任意线路在任意时刻的网络负载存在众多不可预期的大幅度变化，也可能资源需求估计过低，使当前资源的规模无法满足其用户作业需求；也可能对资源需求估计过高，使所租用的资源处于闲置状态，使得资源利用率大大降低.这种物理节点和物理链路的负载极度不平衡，不但造成资源浪费，而且增加了许多成本，同时降低了服务的满意度.因此，要使云计算环境中的资源的利用率提高，需要对可行路径上的节点进行资源分配预估.

在云平台中的每个单元分别由一个主作业调度节点及该单元所辖范围内节点集群中的一个从任务分配节点（slave）共同组成[4].将云计算环境下slave节点域表示为一个完全图G=(V，E)，其中V、E分别表示所有网络节点和所有链路的集合，链路E={(s，m，Qsm)s，m∈N}表示相邻节点s，m间的最优路径.Qsm而为s，m间线路属性集，如：平均带宽、节点费用等.

假设s∈V为源点，M∈｛V-(s)｝终点.对于任一链路e∈E，定义3种属性：时延函数net_delay（e），费用函数net_cost（e），带宽函数net_bandwidth（e）和能量消耗函数E（e）.对于相应的任一网络节点k∈V，也分别为net_delay（k），net_cost（k）及net_E（k）定义3种属性.同时假设esm为网络节点s，m之间的距离，则存在下列关系：

即：Net_bandwidth（Tsm）=net_bandwidthmax-net_bandwidth0

其中，net_bandwidthmax表示全部可用带宽；net_bandwidth0表示服务优先级更高的服务所占用或同时请求的带宽.

根据以上定义：网络问题就是在网络N（V，E）定源点S，终点M，寻找一条路由esm满足：

（1）时延约束：net_delay（Tsm）≤D；

（2）带宽约束：net_bandwidth（Tsm）≥Bmin；

（3）费用约束：net_cost（Tsm）≤Cmin；

其中，Bmin、D、Cmin分别代表业务对网络带宽、时延、费用的约束限制；

在满足前面3个约束的条件下，τ（Tsm）值越小，资源的利用率越高，设资源选择的约束函数为：

3 基于云计算环境下的蚁群优化算法

文中提出在云计算环境的基础上对蚁群算法进行改进，使其能够快速、合理地适应云端最优路径问题的求解.

3.1 算法的改进策略

由于外激素的挥发和聚集是时间的函数，就这就意味着蚂蚁在觅食时所经过的路径随着食物位置的变化过程等效于网络的逻辑拓扑的一个渐变过程，它并不会随着业务的变化而在很短时间内产生大的变化，即保证了拓扑结构在短时间的相似性，从而使网络的逻辑拓扑重配置对网内即将接受或正在进行的服务受损程度得到有效降低.针对上述特征分析，改进后的算法能够解决动态选路和全局性导向问题.

在t时刻探测蚂蚁k从节点s转移到节点m的转移概率函数如下：

其中，Po是ANT转移概率门槛值；tabuk（k=1，2，…，m)用于记录蚂蚁k所经过的节点集合，将获取的节点m加入tabuk中，将m点作为下一个要访问的起点直至构建成一条Hamilton完整的回路；ταsm（t）表示在t时刻蚂蚁在s节点上观察到m节点的信息素浓度；参数μsm用于反映ANT在选择路径上残留信息素浓度的重要程度；α为控制信息素的浓度程度，β是路径长度的重要程度；

ηsm（t）因子的计算公式如下：

当蚂蚁构建完成一条Hamilton完整的回路之后，必须对途径线路上累计的信息素浓度进行更新，同时削弱旧的信息素，即将释放相应访问路径上旧的信息素.

3.2 信息素更新规则

为了诱导所有蚂蚁向满足质量较优的路径靠拢，当蚂蚁完成任意一条路径的(即一个循环结束)搜寻后，要对该路径上的局部信息素和全局信息素进行更新.

3.2.1 节点信息素的定义与更新

在云平台上不同的用户对资源的获取各不相同，而如何高效地获取自身所需类别的资源，将是搜索算法高效与否的关键.以节点作为资源的载体，如果蚂蚁在搜索过程中能够有效地反映其存储的某类资源的信息，无疑会有效提高搜索的效率.因此，利用节点的某类资源的访问成功率作为衡量蚂蚁在该节点的信息素浓度值，能够更精确的反映节点包含某种资源的情况，从而为搜索提供依据.

其中：ζ为信息素的调节因子[8]；n0（key）、Ntotal分别为蚂蚁搜索关键字key成功的次数和同类资源的总检索次数.

3.2.2 路径上信息素的定义与更新

根据文献[9-10]，节点间拥有的资源越多，则相应的通信次数越高，也越利于资源的搜索.文中根据节点间路径上的信息素浓度及相应的节点间通信次数，为蚂蚁搜索提供依据.蚂蚁通过节点路径上的信息素第（t+1）次时计算公式：

式中，Q2为常数[11]；表α示瓶颈带宽对全局信息素的影响强度；Lk-min（s，m）为本次ANT搜索的最佳路径；Φ表示蚂蚁k所走的边s，m属于最佳；

若没有被后续蚂蚁选择的链路上的信息素则更新为：

表示经过一轮迭代更新后，所有弧上的信息素都要挥发，但有下限值τmin.式中，Q1为常数；Lk是蚂蚁k已遍历过的路径的长度.

由式（3）可知，链路上的信息素会随着时间的消逝而减少，为了避免蚂蚁在路径选择时陷入局部最优解，通过采用式（4）和式（6）来更新链路上的信息素强度，从式（4）可看出，当链路剩余带宽越大，信息素浓度就越强.

3.2.3 最优路径选取

在保证用户请求所选路径稳定的前提下，利用蚂蚁在该路径上的信息素浓度值、所选路径距离以及该路径被选取的比重与备选路径进一步优化判断选择.计算公式为：

式中：%Ak为蚂蚁k与其他蚂蚁所选路径为同一路径在全部蚂蚁中占的比例，τk为选择路径Sk的蚂蚁在该路径上留下的信息素浓度均值，L（Sk）为路径Sk的长度.

3.3 算法实现过程

基于改进蚁群算法的云环境下路径搜索步骤如下：

步骤1当用户通过关键字key请求节点point进行资源搜索时，首先检测该节点所包含的资源列表，若存在所需资源，则直接获取资源，搜索结束.否则，进入下一步.

步骤2节点P通过释放搜索蚂蚁择优选取下一节点发出资源请求，并将该节点添加到相应的禁忌表tabuk中.避免重复访问，并根据实际情况做出相应判断，其过程为：

（1）当ANT进入路径搜索，每到达一个节点并收集节点沿途中信息，即终止搜索，并按照式（2）进行一次局部信息素更新.根据定义1，当蚂蚁到达目的后沿原路返回，同时利用式（6）和（7）刷新路径上的信息素浓度.反之，ANT返回上一节点继续搜索，直到直到所有节点访问结束为止.

（2）若下一节点亦不能满足所需资源，则搜索蚂蚁K将从节点信息素表中选取数值最大的节点作为下一节点进行访问，直到找到所需资源或直到本次搜索周期T结束，搜索自动结束.

步骤3当所有蚂蚁搜索请求完毕返回节点后，请求节点利用式（8）对获取的路径方案进行优化筛选，以获取最优满足相关资源的路径.

为了避免蚂蚁在云数据库中无限制的搜寻，造成不必要的网络资源浪费，这里我们对蚂蚁在搜寻过程中设定一个生存值Nodes，当蚂蚁在搜寻过程超出生存值，则蚂蚁不能继续前行，即算法停止，蚂蚁自动消亡，从而实现对资源的有效利用.

蚂蚁在云数据库中生存的Nodes值设定算法：

初始化i=1，Int_Nodes=k；

If(Nodes＜=Int_Nodes)do{

蚂蚁继续向前搜寻；

Nodes++

}while(anti==ture)；

Else if{

算法停止，蚂蚁自动消亡；

}

End

4 仿真实验分析

由于在云计算环境中，网络资源是个没有任何固定的拓扑结构，且网络存在众多具体情况是不可预测的，所以选择一个真实反映云环境的结构、资源的分配情况及其实现的测试环境是相当困难的，这里主要验证该算法能否高效地在云平台下实现的计算资源的搜索及分配工作，并能够优化搜索性能，减少搜索时间，降低网络负载；因此实验是一个模拟云计算的局部域：

配置环境：六台2G以上台式机组成，其中一台设定为服务器;

其他配置：64位Ubuntu操作系统[12]；Hadoop版本为0.20.2[13]；虚拟化平台为Xen，虚拟机管理器为OpenNeBula2.3.0版本.

对比算法：路由算法OSPF、SPF(Shortest Path First)、原ACO以及该蚁群优化算法RACO

使用其中一台PC作为主服务器，用于控制数据库系统数据分布情况.另外使用5台PC作为数据存储节点，安装PostGre_SQL.实验数据为实验室的模拟数据，开始时集中存储在主服务器上，统计将从学院的实验室数据作为测试数据.为了更好证明RACO具有更好的效果，这里同时引入原ACO算法做比较，随着不同数据量的逐渐递增，各算法的延迟性及查询响应时间，如图4，图5.

从图4中可以看到，该算法（RACO）在平均吞吐量明显优于其它3个算法，在参数从0到2逐渐递增的情况下，效果更为明显，经过改进的蚁群算法充分考虑了带宽、传输能量消耗及传输时延等因素，有效的动态调整路径选择，从而保证算法在云环境下的效率.

从图5中可以看出，改进后的RACO算法最优路径的搜寻效率是最高的，且所花费的时间是最短的，相比于其他3个算法，该算法（RACO）在时间延迟性能在具有明显的优势，能够迅速、准确地从云端找到所需访问的数据库，有效的避免陷入局部最优解及收敛速度不稳定等问题.

5 结束语

云计算由大量计算资源组成的IT资源池动态地通过网络以按需、租用的形式提供给各用户，相对网格计算、并行计算等将提出更高基础设施的要求，因此一个好的资源调度算法至关重要.文中将改进蚁群算法（RACO）和云计算技术结合起来，针对云环境的集群性、共享性、动态性及高可用性等特点，将费用、带宽、传输能量消耗及传输时延等作为衡量蚁群资源分配算法性能指标参数，实时根据用户作业的需求搜寻最佳路径.通过仿真模拟实验结果可以得出，该算法相比其他算法能够更好的在云平台中完成对计算资源搜索及分配工作，并能够优化搜索性能，减少搜索时间，降低网络负载，具有很好的全局收敛能力.

[1]Dorigo M，Stutzle T.Ant Colony Optimization[M].UK：The MIT Press，2009．

[2]史恒亮，唐振民，刘传领，等.基于蚁群优化算法的云数据库动态路径规划[J].计算机科学，2010，37(5)：143-147.

[3]XiongPC，Fan Y S，Zhou M C.QoS-aware web service configuration[J].IEEE Transactions on Systems，Man and Cybernetics，2008，38(4)：888-895．

[4]赵肄江，胡蓉.基于虚拟化的绿色云计算[J].湖南科技大学学报：自然科学版，2010，24(3)：41-46.

[5]史恒亮，任崇广，白光一，等.普杰信自适应蚁群优化的云数据库动态路径查询[J].计算机工程与应用，2010，46(9)：10-13.

[6]何雪海，胡小兵，赵吉东，等.基于自适应转移概率的蚁群优化算法[J].计算机工程，2010，36(23)：165-168.

[7]文明波，丁治明.适用于云计算的面向查询数据库数据分布策略[J].计算机科学，2010，37(9)：168-172.

[8]温如春，许樱，王祖麟.改进蚁群算法在迷宫路径规划问题中的研究和应用[J].江西理工大学学报，2010，31(2)：26-28.

[9]王爱静，郝志峰，黄翰，等.双向反馈蚁群算法在网络负载均衡问题的研究[J].计算机工程与应用，2011，47(36)：112-116.

[10]梁爽.基于SOA的云计算框架模型的研究与实现[J].计算机工程与应用，2011，47(35)：92-94.

[11]刘万军，张孟华，郭文越.基于MPSO算法的云计算资源调度策略[J].计算机工程，2011，37(11)：43-46.

[12]Assuncao M，Costanzo A，Buyya R.Evaluating the cost benefit of using cloud computing to extend the capacity of clusters［C］//Proc of the 18th ACM international symposium on High performance distributed computing．New York：ACM，2009：141-150．

[13]郭涛，温少君，陈俊杰.基于个性化的云平台虚拟机部署机制的研究[J].太原理工大学学报，2012(2)：125-129.

The path optimization design of improved ant colony algorithm in cloud environment

CHEN Zhen

(Chaozhou Teachers'College,Hanshan Normal University,Chaozhou 521012,China)

Aiming at the resource allocation problems in cloud computing environmen,the article puts forward an improved ant colony optimization cloud computing resources allocation algorithm through the analyses on bandwidth,the network load and response time factors on the influence of the distribution clouds resources，and combining with the characteristics of cloud computing platform,the choice of the path under the optimization of the cloud environment.Simulation research results show that the improved algorithm can find the required access database in the cloud quickly,optimize search performance,reduce search time and drop the whole network load of cloud database,get better efficiency than some other distribution algorithms of cloud computing.

cloud computing;the network load;ant colony algorithm

TP301.6

A

2012-05-14

陈真（1985-），男，硕士，助教，主要从事云计算机技术、智能网络技术等方面的研究，E-mail：baile035@126.com.

2095-3046（2012）03-0066-05