基于蚁群优化算法的路由协议的研究

邢 锋 ， 顾 燕 ， 王 超 ， 许小飞

（河海大学 a. 计算机及信息工程学院；b. 电气工程学院 江苏 南京 211100）

0 引言

蚁群算法最早由意大利学者M.Dorigo引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。在自然界中蚂蚁虽然没有视觉，却能发现食物与蚁穴之间的最短路径。蚁群在从蚁穴到食物源并返回的过程中，能在其走过的路径上分泌一种挥发性的化学物质——信息素。蚂蚁在开始时随机选择运动方向，释放的信息素与路径长度成反比。随后的蚂蚁能感知这种信息素的存在及其强度，并倾向于朝着信息素强度高的方向移动。单位时间里在较短的路径上走过的蚂蚁数目较多，则该路径留下的信息素也更多，就会吸引更多的蚂蚁，因此该路径的信息素浓度得到进一步的加强，形成一个正反馈，直到大多数蚂蚁都集中到一条最短的路径。蚁群算法就是通过蚂蚁寻找食物过程中与环境之间的信息交换而实现蚂蚁群体之间的信息传递，并最终达到寻找最优路径的目的[1]。

1 蚁群算法应用到路由的可行性分析

由于蚁群算法具有的多样性和正反馈等特点[2-4]，使得蚂蚁总能找到较优路径，可以很好的应用于通信网络中。

在 Antnet协议中，蚂蚁之间通过信息素这个纽带相联系，当大量蚂蚁选择同一条路径的时候容易造成拥塞。为了有效克服上述问题，本文提出了一种基于蚁群优化算法的负载均衡路由算法Pro-antnet，有效结合了蚁群算法的正反馈、分布式计算和启发性搜索等特点，通过对蚂蚁收集到的网络信息所对应的参数赋予不同加权值的方法对路由表进行控制，有效地缓解了网络的拥塞问题。该算法设计的目标是在选择较短路径的同时又能够避开负载较重的链路，保持网络负载分布平衡。

2 Pro-antnet蚁群算法的路由机制

Pro-antnet算法由路由建立，路由更新和路由维护三部分组成，完全按需操作。

2.1 路由建立

在算法中构造了两类结构相同的人工蚂蚁：前向蚂蚁（Forward Ant）和后向蚂蚁(Bckward Ant)。其中前向蚂蚁表示从源节点到目的节点的蚂蚁，用于收集该路径信息到路由决策表（Memory），包括蚂蚁所经过的节点和到达的时间；而后向蚂蚁表示找到目的节点后从目的节点返回源节点的蚂蚁，在返回途中根据收集的信息对路径上的节点进行信息素更新。

当源节点欲发送数据到目的节点，首先查找路由表，看是否有到达目的节点的路由信息。如果有，数据分组根据决策表中到目的节点概率最大的下一跳邻居节点选择路由；如果没有，则将待发送的数据保存到缓存中，生成前向蚂蚁，通过按需方式广播给所有邻居节点。中间节点i接收到来自i-1的前向蚂蚁后，对没有出现环路的前向蚂蚁进行转发。转发时判断i是否有到目的节点的路由，如果有则按单播的形式转发，否则，继续进行广播。

前向蚂蚁到达目的节点后将被丢弃，节点生成后向蚂蚁以单播形式沿前向蚂蚁的传播路线原路返回。目的节点会在一定时期内，在收到来自同一个源节点的多个前向蚂蚁后返回后向蚂蚁，以此建立源节点到目标节点的多条路径。后向蚂蚁链路队列的处理优先级较高，目的是将收集的路由信息快速传播回去，及时地更新各节点的路由决策表，蚂蚁进行路由寻找的过程如图1所示。

图1 路由寻找过程分析

在Pro-antnet协议中，为了有效地缓解网络的拥塞现象，在选择较短路径的同时希望避开负载较重的链路，保持网络负载分布平衡。源节点到目的节点间维护多条冗余路径，通过对信息素更新来动态进行路由选择，同时利用信息素挥发机制，对节点所维护的路由做老化处理，能够动态适应网络变化。

节点中保存的路由决策表包含节点的本地信息和节点选择下一跳邻居节点的转移概率，蚂蚁选取蚂蚁决策表项中概率最大的邻居节点作为下一跳路由。

为简化问题本文只考虑节点i和j的拥塞情况。假设qij(t)为节点i中发送到j的等待分组长度，qtotal（t）为i到所有相邻节点的等待分组长度总和，q’total是j节点所有等待分组的长度总和，M为节点缓存队列的长度。若用ψij(t)表示路径的拥塞状态，那么有：

其中α为信息素启发因子，表示轨迹的相对重要性，其值越大则蚂蚁越倾向于选择其他蚂蚁己经经过的路径。

设τij（t）表示t时刻节点i到目的节点的路由中，选择j作为下一跳的路径上的信息素的值；ηij(t)是节点i到j的启发式值，该启发式值为到目节点跳数的倒数；那么在t时刻节点i选择下一跳节点j的概率Pij(t)为：

其中β为跳数启发因子,表示跳数的相对重要性，其值越大蚂蚁越倾向于选择较短的跳数到达目的节点。γ为负载启发因子,反映节点负载的相对重要性,该值越大则越倾向于选择负载较轻的节点传送数据。

本算法在式（1）中既考虑了MAC层接口缓冲队列中剩余空间占缓存队列的大小，同时考虑了节点 i发送到节点 j时的堵塞程度。结合二者很好的选择了下一条节点，减少了分组等待时间，很好的预防了网络的拥塞。

2.2 路由更新

首先路由经过初始化，每个节点的信息素初始化为1.0/N，源节点每隔一段时间t发送一个前向蚂蚁，该蚂蚁按决策表中概率来选择下一跳进行单播发送，当前向蚂蚁到达目的节点后，通过后向蚂蚁对路径信息素进行更新。为避免残留信息素过多导致残留信息淹没启发信息，在 Pro-antnet蚁群算法体系中加入信息素挥发机制，通过调整挥发系数使蚂蚁找到的每条路由都有一个恰当的生存时间。在t+△t时刻，在路由的节点i上信息素更新为：

在其他节点(k≠j)更新为：

其中r表示信息挥发系数，取值在（0，1），则1-r表示信息素浓度残留因子。

2.3 路由维护

由于Ad Hoc网络的移动性使得正在使用的路由经常出现中断。当算法检测到所维护的路径上的节点有链路中断时，首先缓存数据分组，看是否有其他的到目的节点的路由，如果有，选择最大转移概率的下一跳进行转发；如果没有，则向源节点发送错误消息进行路由重建。

该算法采用了多条备用路由，增强了网络的稳定性，提高了网络的吞吐量和分组投递率。另外算法考虑了网络的拥塞，自适应的选择负载轻的路由，在一定程度上减少了端到端延时。

3 结语

单纯的基于蚁群优化的路由算法目前存在一些缺点：节点只是单独依靠蚂蚁代理来寻找最短路由，网络动态变化剧烈和路由生命周期较小时，效果不会很好；存在较长的时延；在路由算法执行过程中，容易陷入局部最优。在网络负载较轻但对时延有比较高的要求时需要引入主动式的路由维护来保证路由质量，在路由开销增加不大的情况下达到较短时延和较高的QoS。

本文对蚁群算法应用到路由进行了详细的可行性分析，对蚁群算法的路由机制进行了详细的介绍，并从网络均衡负载方面进行改进，从全局角度对蚁群算法进行了优化。由于信息素增量的计算以及信息素表的更新是建立最优路由以及维护路由的重要方面，怎样采用更好的控制参数来进行信息素表的更新将是进一步研究的方向。将来工作的重点是将算法加到NS2中进行网络模拟，用实验证明算法的有效性。

[1] 段海滨. 蚁群算法原理及其应用[M].北京:科学出版社. 2005.

[2] Caro G D, Dorigo M. AntNet: A Mobile Agents Approach to Adaptive Routing [C].Belgium: Technical Report IRIDIA, 1997.

[3] 左国明,于万钧,胡兆玮,等. 基于改进蚁群算法的 Ad hoc路由算法[J].计算机应用研究,2008,(25)1:59-61.

[4] Ziane S, Mellouk A. A swarm intelligent multi-path routing for multimedia traffic over mobile ad hoc networks[C]. USA:In Proceedings of the 1st ACM international workshop on Quality of service and security in wireless and mobile networks,2005:55-62.