RIP距离矢量路由算法优化方案

黄亚玲

摘要：网络的发展刺激路由器的市场需求与日俱增，路由算法也因此备受青睐。该文主要叙述对距离矢量路由算法的基本认识，浅析了它的工作原理和现存的路由缺陷，并利用蚁群算法原理提出优化方案。

关键词：距离矢量路由算法；路由缺陷；蚁群算法

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2015）13-0041-02

Abstract： Stimulate development of the network router's market demand is growing， routing algorithm is becoming popular. This paper mainly described the basic understanding of distance vector routing algorithm， analyses its working principle and the existing routing defects， and use the principle of ant colony algorithm optimization scheme is put forward.

Key words： distance vector routing algorithm； routing defects； ant colony algorithm

距离矢量算法和链路状态算法是现代计算机网络中最为流行两大路由算法。距离矢量路由算法在能够自适应网络拓扑结构和流量变化，简单快速的实现的网络连接。虽然距离矢量路由算法实现简单，但是也存在着一定的缺陷。蚁群算法是通过模拟蚂蚁觅食规律设计出的一种需找最优路径的算法。它具备的正反馈性和并行性等特性可以有效的改善距离矢量算法。本文简单的介绍了距离矢量路由算法的工作过程和原理，并提出利用蚁群算法对距离矢量算法的优化方案。

1 距离矢量路由算法

1.1距离矢量路由算法的基本认识

现在的距离矢量路由算法（Distance Vector Routing，DV算法）主要应用在因特网的路由通信协议（RIP协议）中。同一网络区域中的每个路由器都动态保存着到达其他路由器路径的路由表。然而，这一路径是根据“跳”来计算的，即数据包每经过一个路由器称为一跳。同时各路由器也只能与相邻的路由器进行数据交互，更新路由表信息。这一过程类似于“传话”游戏。

1.2 DV算法的工作过程及缺陷

如上图1，假设A要向B发送一条消息，这个数据包可以利用不同的路径将数据传输到B。根据DV算法的原理，它会选择一条跳数最少的最佳路径，就是从R0传递到R1，再传递到R2，再传递到R5，最后将数据发送到B。

我们很快可以发现一个问题，DV算法仅仅是选择跳数最少的路径，它并没有考虑路线消耗和时延问题。这就是类似我们打出租车是选择路径最短还是用时最少是一样的道理。有时候最短的路出租车走的比较多就会造成拥堵现象，此时绕远一点反而一路畅通，在更短的时间内到达目的地。就如图1所示，R0到R1到R2到R5是四跳，而R0到R3到R4到R2到R5是五跳，看似跳数少的前者更为合理，但是在这条链路拥堵的时候需要更多的等待时间，此时选择后者反而能更快的将数据包发送出去。所以原始的DV算法只适合网络负荷可以预测的简单网络。

此外，原始DV算法在正常的网络中总能够正确传输，但是它的收敛速度非常慢。对于好的消息传输的非常快，对于坏的消息传输的却非常的慢。例如R2去往网络的路由故障了，但是消息没有及时更新，R1依旧保存着R2可以到达网络的旧信息，以至于R2从R1的信息里错误的认为R1可以到达网络。它们同时认为可以通过彼此到达网络，从而形成了路由环路。

2 DV算法的优化方案

2.1 蚁群算法的工作原理

蚁群算法是模拟蚂蚁在复杂的自然环境中觅食过程，通过释放信息素的方式找出最优路径。信息素是蚂蚁在觅食路径上释放的能够互相检测到分泌物。当一只蚂蚁在盲目找路的过程中检测到其他蚂蚁留下的信息素后，就会沿此路线前进并释放信息素，加强信息素浓度方便其他的蚂蚁尽快找到路线。

2.2 利用蚁群算法优化DV算法

蚁群通过个体之间的相互协作和信息交流而具备发现最优解的能力，这种能力的本质在于以下三种机制：

（1） 选择机制：选择信息素浓度大的路径作为移动方向。

（2） 更新机制：路径的上的信息素浓度会因为走过的蚂蚁数量增加而浓，也会因为时间的推移而挥发。

（3） 协作机制：蚁群利用信息素互相协作和交流信息。

为了更好的实现距离矢量算法选择最优路径和路由信息表的更新，我们定义正向蚁群[Rant]和反向蚁群[Bant]这两种人工蚁群。正向蚁群[Rant]主要用来收集从初始路由节点到目的路由节点的跳数和延时等路由开销信息，并释放食物源信息素。反向蚁群[Bant]根据正向蚁群[Rant]收集到的信息从目的路由节点到初始节点途中所有节点的路由信息表，并且反向蚁群[Bant]具有记忆功能，将保存路由节点序号和路由表所有信息，并释放巢穴信息素。将这两种蚂蚁抽象的放到网络拓扑结构中，通过它们频繁的移动探测周围网络信息，选择最优的路由路径以及完成路由表更新。

2.2.1 路由节点的选择

在有n个节点的网络环境中，正向蚁群[Rant]从路由节点i出发，在所有邻接节点选择下一跳的路由节点j，目的路由节点为d。若所有邻接节点都未访问过，则随机选择下一跳，否则选择概率[Pij]最大的邻接节点，那么[P'ij]的表达式为：

[Pij（t）=ωij（t）αξij（t）βs?Nkωis（t）αξis（t）β，j∈Nk]

[ξij=1dij]

其中[Nk]表示[Rant]的下一跳路由节点集合，[ωij]表示路由节点i到路由节点j路径上的信息素值，[ξij]表示从路由节点i移动到路由节点j的启发因子。

若正向蚂蚁[Rant]在移动过程中访问到已访问的路由节点，可判断为进入路由环路，则删除整个环路上的所有信息并返回环路初始节点重新移动。同时若正向蚂蚁[Rant]的移动时间超过了它的生存周期，为了避免将未知路由信息带入网络引发死循环，则丢弃这类正向蚂蚁。最先到达目的路由节点d的正向蚂蚁触发创建逆向蚂蚁[Bant]，并将搜索过程中的路由信息（跳数，时延，路由开销等）传递给逆向蚂蚁后，正向蚂蚁被杀死。

2.2.2 路由信息表的更新

逆向蚂蚁[Bant]接受到正向蚂蚁的所有信息后，沿着正向蚂蚁反向路径随机选择一条可行路径移动，并更新途中的所有路由节点的信息素值。若因路径故障导致逆向蚂蚁无法返回到初始路由节点，则杀死这类逆向蚂蚁，使得优化后的距离矢量算法更好的适应网络环境的变化，及时调整路由路径。

（1）若路由节点i的下一跳节点j是逆向蚂蚁移动过来的节点，则增加下一跳节点的信息素值[ωij]，表达式为：

[ωij（t+1）=（1-η）ωij（t）+ηΔωij（t），η∈（0，1）]

[Δωij（t）=1dij]

其中[η]为信息素挥发因素系数，[dij]是蚂蚁构建的i到j的路径长度。

（2）若路由节点i选择其他邻接路由节点，则需要挥发信息素，保证路由路径中信息素的平衡，挥发信息素表达式为：

[ωij=（1-r）ωij]

其中[i≠j，j∈Nk]。

目前人们对于基于蚁群算法的路由优化并在应用中取得一定的成果，但是怎样更好的提高蚁群算法的收敛性和速度依旧是未来路由优化研究的热点。

3 结束语

距离矢量算法在Internet通信网络中的作用是不容小觑的，虽然在一个静态网络中总能够到达目的地，但是它的收敛性非常慢，尤其是坏消息传递的非常慢。本文通过定义正反向蚂蚁对距离矢量算法的慢收敛性进行分析改进，得以优化距离矢量算法的思想。

参考文献：

[1] 贾云富， 秦勇， 段富， 等. 蚁群算法及其在路由优化中的应用综述[J]. 计算机工程与设计， 2009.

[2] 卫海亮. 蚁群算法及其在网络优化中的应用研究[D]. 西安电子科技大学， 2012.

[3] 朱永利， 李丽芬. 长链树状无线传感器网络中遗传蚁群路由优化算法[J]. 小型微型计算机系统， 2012.