Hadoop平台下一种改进蚂蚁算法的QoS路由研究

陈志高

(湖南科技职业学院 长沙 410004)

0 引言

云计算是分布式处理、并行处理和网格计算的综合发展，即把存储于个人电脑、移动电话和其他设备上的大量信息和处理器资源集中在一起协同工作，极大规模扩展信息技术能力，向外部客户提供服务的一种计算方式［1］。当前我国正处于云计算的成长期，未来十年，我国许多IT企业以及各中小企业都将分享未来数千亿的“云计算蛋糕”，越来越多的云服务将在网络上应用和运行［2］。我国虽然已经广泛应用了宽带技术，但网速仍低于其他国家［3］。随着云计算网络的扩展和云服务的增多，对我国现有的网络性能提出了更高的要求，云环境下的QoS路由已经至关重要。开放最短路径优先算法(open shortest path first，OSPF)是满足QoS的路由的典型代表，它是现有网络普遍采用的一种路由协议，它采用的路由算法是链路状态路由算法(link state routing，LS).但是LS不是多径路由算法，并且不具有拥塞规避机制［4］，当一条链路即将或者已经发生拥塞时，只有简单的丢弃数据包，即使网络中其他链路还是空闲的，这使得网络资源无法得到充分的利用。

1 云计算的基础架构与蚂蚁算法

1.1 云计算环境介绍

目前，云计算的基础架构技术主要有谷歌非开源的体系GFS(google file system)和Hadoop技术对于GFS的开源实现HDFS(Hadoop Distributed File-System)。Hadoop是一个可靠、高效、可伸缩，并能够对大量数据进行分布处理的软件框架，由于它以并行的方式工作，可以在廉价的PC机上利用群集等技术处理PB级的数据，并自带有JAVA语言编写的框架，可以免费使用。

Hadoop核心部分HDFS和MaPReduee都采用了Master/slave结构，因此整个Hadoop系统也统一成这种两层结构。一个HDFS集群由一个NameNode(名字节点)和若干个DataNode(数据节点)组成。其中，NameNode是主服务器，负责管理文件系统的名字空间和客户端对文件的访问，Datanode是从服务器，在集群中通常是每个物理节点上布置一个，负责它们所在的物理结点上的存储管理。在节点内部，文件通常被分割为一个或多个数据块(block)，这些数据块存储在一组DataNode中。

1.2 蚂蚁算法

蚂蚁算法(Ant Colony Algorithm)是由意大利学者Marco Dorigo等人于1992年提出的一种并行高效的模拟进化算法。该算法是模拟自然界中的蚂蚁在觅食过程中形成的一种用来在图中寻找优化路径的机率型技术，其核心思想是:蚂蚁在寻找食物的路径上会留下一种叫“信息素”的化学物质，这些“信息素”能够为后续寻找食物的蚂蚁提供选择行走路线的启发式信息，通过不断更新信息素，可以在较短时间内找到蚁穴和食物之间的最优路径。该算法具有并行性高、收敛速度快等优点，并在旅行商问题、路由问题和调度问题都取得了一些比较满意的实验结果，但是标准蚂蚁算法容易陷入局部最优解［6］。林国辉等人［7］提出了基于蚂蚁算法的拥塞规避路由算法，对链路的拥塞状态做出快速反应，分散流量，以避免链路的拥塞。后来段海滨等［8］提出了一种利用云模型定性关联规则来有效限制基本蚁群算法陷入局部最优解的方法，并得到比链路状态路由算法(link state routing，LS)更好的结果。

2 连接蚂蚁算法

2.1 模型设计

要实现云环境下的高效的QoS路由，在真实环境下必须实现两个条件:a.数据传送的路径必须是最优路径;b.最优路径所经过的各个节点间必须有足够的带宽运行云服务;如果在最优路径上某些节点间出现拥塞则必须选择次优路径进行分流或拥塞控制。由于蚂蚁算法在选择最短路径上由较快的收敛性，因此条件a.容易实现，但是一旦搜索到了最短路径，所有的云服务都将从该路径上运行，势必将会引起最短路径上的数据流量陡增。在我国目前有限的基础带宽上，各节点之间所能提供的网络最大容量是参差不齐的，一旦所有的业务都放到最优路径上传输，将会使某些网络容量较小的节点提前进入拥塞，目前在我国广泛使用的路由协议都不具备拥塞规避的功能，如果不能及时调节将会使后续业务继续从最优路径上传输，导致拥塞和数据重传加剧，这对云服务的运行是很不利的。

2.2 连接蚂蚁算法

章洋等人［9］提出的LB算法将网络中的每个节点的路由表用一张概率表替换，表中用Pdn表示每个节点到达可能的目标节点d选择相邻节点n的概率，概率即为蚂蚁算法中信息素的强度.以此表中概率值的更新来模拟蚂蚁寻路遗留信息素的行为，即利用蚂蚁算法来更新路由表，本文对此作如下改进:

a.将ρ改为阈值函数

定义:

ε为挥发约束系数，且ε∈(0，1)，ρ1为信息素残留在各节点的最低值。

b.当最优路径出现拥塞时采用何种方法选择新的次优路径规避拥塞等问题，王传臣等人［10］提出采用双向蚂蚁寻路的方法(见图1)，该方法虽然能提高新路径搜索的速度，但运算规模过于复杂，本文提出连接蚂蚁算法(link connection ant algorithm，LM)来规避拥塞路径:当蚂蚁算法搜索到了源节点s到目标节点t的最优路径为s→a→b→c→d→e→f→g→h→t，则意味着节点d与f之间的最优路径为d→e→f，当节点d与f之间出现拥塞时只需要选择另一个节点，使得该节点到d与f之间链路的代价之和最小，并能满足网络QoS要求即可，这样可以让其他的节点都同时向d与f各发送一个连接蚂蚁，并比较这些节点中到d与f之间链路的代价之和，取最小的节点重新连接到d与f形成一条绕过d与f的拥塞链路的新的次优路径。

图1 双向蚂蚁链路拥塞规避示意图

图2 连接蚂蚁拥塞规避选路示意图

在整个云网络中，可将网络模型看成一个有向图G=(V，E)，其中V表示图中所有云节点的集合，E表示图中所有节点之间通信路径连接的边的集合。

如果某条路径L满足以下3个条件，则该路由请求可接受。

a.带宽可用限制:bandwith(j)≤bandwith，其中j为L上的任意一条链路，bandwidth(j)表示相邻节点间的直通链路j的可用带宽。

b.端到端时延限制:

其中i为L上不包括起始节点的其它所有的节点，nodedelay(i)表示经过路径L上的节点i(不包括起始节点)的时延，j为L上的任意一条链路，linkdelay(j)表示经过路径L上的链路j的时延。

c.端到端丢失率限制:

其中i为L上不包括起始节点的其它所有的节点，nodeloss(i)表示为在路径L上的节点i的丢失率。

连接蚂蚁算法(link connection ant algorithm，LM)的具体步骤为:

a.初始化网络参数，判断网络各节点间的链路参数能否满足当前QoS要求，若QoS要求的总时延比任何一条链路上的时延要求的都小，即delay≤nodedelay(i)，则网络无法满足当前QoS链路要求，退出;否则步骤b。

b.删除带宽小于需求带宽的链路，使网络图中保留的各链路带宽均符合QoS要求。

c.初始化各节点间链路上的信息素，设置为最低值ρ1。

d.从源节点发送k只蚂蚁寻路，在每只蚂蚁成功完成选路后在其所经历的路径上进行信息素的更新。

e.对所有蚂蚁重复第d步，直到所有蚂蚁都完成步骤d的选路和信息素更新过程。

f.选择建立最小代价并满足QoS链路要求的路径作为可选路由，然后采用全局更新规则来更新各路径上的信息素浓度。

g.重复第d到f，只到获得全局最优路径。

3 算法仿真

在NS2仿真平台上对本算法进行了仿真，仿真所用的网络结构如图3所示。

图3 云节点拓扑图

3.1 hadoop云环境构建

仿真环境是在vmware workstation 8软件安装ubuntu linux 9.0群集，并在ubuntu linux 9.0操作系统下安装hadoop，每个群集分为master和slave两台虚拟机，每个群集在共享磁盘上安装hadoop，master和slave两台虚拟机各有两块网卡，其中一块设置为心跳线连接，另一块与外界网络通信，两台虚拟机使用一个公共ip与外部网络进行通信，其运行情况如图4所示。

3.2 NS2仿真环境

仿真是在上述ubuntu linux 9.0操作系统下安装NS-2.34版软件，通过下载antnet-1.0，直接对其目录下的antnet.tcl脚本进行修改，并采用tcl脚本设置仿真进行节点0到5的数据测试。数据源的发送速率R取值从2Mb/s开始，以500 kb/s为步长渐增，并且数据源的发送和停止的持续时间的平均值都是100ms。各条链路判断拥塞的上限阈值为0.6，下限阈值为0.3，NS2仿真结果如图5所示。

图4 hadoop群集节点

图5 NS2仿真

另外通过与文献［10］中的方法进行对比网络丢包率和数据包时延如图6和图7所示。

图6 丢包率分析图

从仿真结果图6和图7可以看出，本文算法采取的拥塞规避机制既能大大降低了网络丢包率，又能缩减网络平均延时，在hadoop云网络环境下有较好的适用性。

图7 时延分析图

4 结论

本文提出了在hadoop云平台下一个基于连接蚂蚁能够满足多种QoS约束条件和带有拥塞规避特性的QoS路由算法。通过各节点信息素浓度的概率表来替换路由表，可以快速搜索符合QoS条件的最优路径，并通过连接蚂蚁来解决链路的拥塞问题。通过仿真，结果表明该算法在hadoop云环境下同样具有比目前LS算法更高的优越性。

［1］房秉毅，张云勇，程莹.云计算国内外发展现状分析［J］.电信科学.2010，8A:1-5.

［2］Nezamabadi-pour H，Saryazdi S.and Rashedi E.Edge detection using ant algorithm［J］.Soft Comput.，2006，10(7):623-628.

［3］华夏渝，郑骏，胡文心.基于云计算环境的蚁群优化计算资源分配算法［J］.华东师范大学学报.2010，1:127-134.

［4］范杰，彭舰，黎红友.基于蚁群算法的云计算需求弹性算法［J］.计算机应用.2011，31(1):1-4.

［5］何志东，俞鹤伟，陶铭.双向搜索蚁群算法在QoS单播路由中的应用［J］.计算机工程与应用，2010，46(31):106-108.

［6］田素贞，翟玉梅，刘传领.基于云计算的多目标服务调度算法的改进研究［J］.陕西理工学院学报(自然科学版)，2012，28(1):24-28.

［7］林国辉，马正新，王勇前，等.基于蚂蚁算法的拥塞规避路由算法［J］.清华大学学报，2003，43(1):1-4.

［8］段海滨，王道波，于秀芬，等.基于云模型理论的蚁群算法改进研究［J］.哈尔滨工业大学学报，2005，37(1):115-119.

［9］章洋，范植华，何晓新，徐帆江，王宇心.移动自组网络中多径路由的匿名安全［J］.电子学报，2005，33(11):2022-2030.

［10］李丹丹，张润彤，王传臣，肖东坡.认知网络中基于蚁群算法的网络流量预测模型［J］.电子学报，2011，39(10):2245-2250.