基于蚁群算法的路由算法研究

翟溪林

(山东农业大学，山东 泰安 271000)

文章基于蚁群算法已有研究成果，提出基于蚁群算法的路由选择算法，对推动在网络路由优化上蚁群算法的应用具有一定的实际应用价值。

1 路由机制的研究

根据OpenFlow网络与传统网络互通的情况，需要这样一种方案来实现OpenFlow网络层的三层通信，即在OpenFlow控制器中加入路由模块，在不同OpenFlow网络拓扑结构中，实现不同IP网段间的通信[1-2]。

2 OpenFIow网络拓扑结构

在本网络中，是利用链路层发现协议(Link Layer Discovery Protocol，LLDP)，OpenFlow交换机实现与对端的链路连接状况和设备类型信息的周期性地互通，而利用交换机上传的状态信息，OpenFlow控制器便能对每一对端口间的连接情况予以掌握，从而将网络的所有拓扑状况获取。依靠传输线，各节点互相连接是本结构的特点，各节点与其他两个及以上节点相接。可靠性高，结构复杂，不过维护与管理不易。利用OpenFlow技术可对网络资源与链路流量进行良好的分配，网状网结构如图1所示。

图1 网状网结构示意

胖树拓扑结构则是OpenFlow网络数据中心另一种常见的结构。中心流量改变不小，而且多是传统的基于树形的网络架构，收敛比存在上下行间的带宽，如此易堵塞网络[3-4]。就树形传统结构，胖树不止一个根节点，有生长向上的多个左右节点，通信瓶颈因根节点而产生，越向上接近根节点，链路占用越大带宽。故而，就中心网络且无堵塞的建立，可用这一结构。而下层节点链路带宽之和，为上层节点带宽，为较理想的胖树结构，其结构如图2所示。

图2 胖树结构示意

胖树结构具有良好的扩展性，且等分带宽高、网络直径短，是十分典型的多级交换网络，其分为从下至上的边缘层、汇聚层和核心层3层。需要注意，从边缘交换机向上连接，上层不少于两个交换机与各个边缘交换机相连，则是依靠链路，各层交换机间相连的。而让边缘及核心交换机间有均衡的流量，是整个网络拥塞率减少的关键。本结构能提供多条从同一源节点至目的节点的路径，使容错性较好，路径多样化。

3 基于蚁群算法的多路径路由算法

本章将传统的路由算法应用到OpenFlow网络中，针对OpenFlow数据中心网络的多路径，给出基于蚁群算法的多路径路由选择算法。

3.1 蚁群算法原理及模型

蚁群算法的基本原理如下。

根据自然界蚂蚁的寻路特征，蚂蚁经过每条路径时留下的信息素有以下特征。

(1)蚂蚁对信息素释放量与路径长度成反比关系。

(2)蚂蚁释放的信息素有挥发性，其质量浓度会随着时间变长而下降，从而对蚂蚁选路的影响性越低。

由于信息素的影响，蚂蚁通过最短路径上留下的信息素浓度最高，而其他路径上的长度比最短路径要长，因此，蚂蚁在其他路径上留下的信息素浓度比最短路径上的信息素质量浓度低，随着时间变长，信息素挥发。最终，所有蚂蚁都会从最短路径上经过。

3.2 OpenFlow多路径路由算法

基于蚁群算法，提出多路径路由算法，整个路由选路过程如图3所示。

图3 路由过程

在整个OpenFlow网络中，当边缘节点有数据流进入时，控制器中会传入有关节点信息，根据这些信息，控制器对源节点是否可直接至目的节点进行检查，若不行，通过蚂蚁进行寻路，最后会把至目的地的全部蚂蚁记下，将最短路由即链路代价最短路径筛选出。

4 仿真及分析

上文提出的多路径算法是一种与OpenFlow数据中心相适应基于蚁群算法的路由算法，本章对其进行仿真。

在选择源节点至目的节点的路径时，基于蚁群算法的原理，经对蚂蚁选路满足的条件予以判断，将对带宽要求满足的后续节点选出，对下一跳节点的选择则依照公式进行，对信息素更新，进行路径筛选，最后是数据发送。

将这种算法应用在复杂数据中心的网络中，能在多路径下创设合理的路由计算与查找以及将节点间的最短路径问题妥善处理。不过，其会引起较长的最短路径搜索时间，局部最优解上也易收敛。为此，将一个条件即带宽限制加入蚂蚁寻路中，进行对带宽要求满足的后续节点搜索，将最优路径选出。

5 结语

文章基于OpenFlow网络路由功能的需求，OpenFlow网络中实现控制器路由机制的必要性及OpenFlow网络的两种不同拓扑结构等基础上，阐述了基于蚂蚁算法的多路径路由算法的特点、流程，并进行了仿真及分析，由于数据中心网络中拓扑复杂，不少转发流量的路径就控制了流量，网络有限，且不可利用多条路由进行流量转发。基于OpenFlow的特征，对提出的算法利用控制器加以调用，对路由集中计算，向多条路径分配流量并转发，使网络链路利用率增加。