基于蚁群算法的典型路由协议的比较研究

郭彦芳

（重庆邮电大学重庆市移动通信重点实验室，重庆400065）

基于蚁群算法的典型路由协议的比较研究

郭彦芳

（重庆邮电大学重庆市移动通信重点实验室，重庆400065）

针对Ad hoc网络拓扑结构的多变和基本蚁群算法易失去多解的情况，在对算法的节点选择进行改进后，提出把蚁群算法与DSR、AODV和DSDV相结合，即ant－DSR、ant－AODV和ant－DSDV。利用改进的蚁群算法寻找最优路径，在节点速率、停留时间这2种不同场景下分析比较了端到端时延、吞吐量、路由开销和跳数等参数的性能。仿真结果表明，先应式路由协议比按需路由协议在提高性能上更适合于蚁群算法，但却增加了路由开销，并且每个节点产生最优路径时需要更多的计算。

Ad Hoc网络；DSR；AODV；DSDV；蚁群算法；路由

0 引言

Ad hoc网络中，每个节点能通过路由协议找到最优路径来进行彼此通信。因为寻找最优路径的过程比较复杂，所以路由协议对网络性能的要求极大。目前Ad Hoc网络中已经在使用的路由协议有DSR、AODV和DSDV等。DSDV代表了基于表驱动的先应式路由协议，而AODV和DSR代表了按需的反应式路由协议。路由协议中的算法是用于改善发送消息的节点寻找出最优路由的过程，而蚁群算法是目前路由协议选择的算法之一。重点讨论了采用改进蚁群算法寻找最佳路径的3种典型路由性能的比较研究。基于改进蚁群算法的DSR、AODV和DSDV称为ant－DSR、ant－AODV和ant－DSDV。用QoS参数中的时延和吞吐量对3种基于蚁群算法的路由协议的性能进行衡量，而为了了解寻找最优和最短路由过程的复杂性，使用路由开销和跳数衡量路由协议的性能。若路由协议能产生较好的路由开销和最短跳数、较高的吞吐量和较短的时延则此算法比较可行。

1 3种路由协议简单介绍

1.1 Ad Hoc网络

Ad Hoc网络是有一组带有无线收发装置的移动节点组成的一个多跳临时性的自治系统，它不依赖预设的基础设施而临时组建，网络中的移动节点利用自身的无线收发设备交换信息，当它们之间不在彼此的通信范围内时，可以借助于其他中间节点来实现多跳通信。网络上的每个节点通信均是依赖于路由协议进行，路由协议在Ad Hoc网络中是不可或缺的。

1.2 DSDV、DSR和AODV

目的距离路由矢量（DSDV）是一种先应式路由协议。DSDV中，每个节点都保存一个路由表，路由表维护本节点到网络内所有可达目的节点的路由。路由更新是通过检查每个节点到来的序列号进行的。动态源路由协议（DSR）是一种反应式路由协议，最重要的特点就是利用了源路由算法，每一个给定路线的数据分组都在报头带有完整、有序的此分组必经节点列表。每个节点把自己所知的任何新的路由信息都存储在Cache中，而不管是以何种方式获得路由信息的。自组织网按需距离矢量路由（AODV）是一种反应式路由协议。在AODV协议中，当一段时期内不用一个路由时将会失效或被丢弃，这减少了路由维护需求并使得路由数量最小化。当一个路由被使用时，其周期表将进行更新。

例如在图1中，节点1若向节点6发送一条消息，但路由表中不存在此路由信息，然后它将发送RREQ到它的邻居节点，即节点2和节点3。由于还没有找到目的节点，节点3将把RREQ发送到它的邻居节点，即节点4和节点5。由于节点4中已有关于节点6的消息，那么节点6将发送RREP到节点3，接着到节点1。当节点1更新路由表后，一条消息就能被发送到节点6。

图1 AODV路由请求消息发送和路由应答

2 蚁群算法

2.1 蚁群算法思想

蚁群算法首先由意大利学者Dorigo［1－3］于1991年提出，并用该方法解决了一系列的组合优化问题。通过分析发现，蚂蚁觅食过程，与Ad Hoc网络路由问题有很多相似之处。结合Ad Hoc网络环境进行模拟，将蚂蚁觅食过程中的“蚁穴”和“食物源”当作Ad Hoc网络中的源结点和目的结点，将蚂蚁的行为当作网络中的数据通信，蚁群算法中有一个蚂蚁决策表，它包括所有结点选择下一路径的转移概率和关于结点的本地信息，蚂蚁使用这个表来指导其搜索朝着搜索空间中最有吸引力的区域移动，这正是网络通信中路由表的形成过程。因此，蚁群算法能够应用于Ad Hoc网络的路由，通过信息素的释放寻找并维护从源结点到达目的结点的最优路由，按照信息素的挥发算法不断对各结点的信息素值进行更新，以适应网络动态变化的需要。

2.2 改进蚁群算法的数学模型

首先引入一些符号参数［4，5］。设总结点数n，所组成的集合是C，坐标系（x，y），源节点s，目的节点d，m只蚂蚁，用dij（i，j＝1，2，…，n）表示节点i和节点j之间的距离。τij（t）表示t时刻在节点i和节点j之间的路径上残留的信息素强度。初始时刻，各条路径上信息素强度相等，设τij（0）＝const（const）。蚂蚁k（k＝1，2，…，m）在运动过程中，根据各条路径上的信息素强度决定转移方向，同时用禁忌表tab uk（k＝1，2，…，n）来记录蚂蚁k当前已走过的节点，禁忌表tab uk随进化过程作动态调整。pkij（t）表示在t时刻蚂蚁k由节点i转移到节点j的状态转移概率，其表达为［6，7］：

而为了避免蚂蚁一开始就失去解的多样性，在式（1）的基础上，第k只蚂蚁按以下概率从位置i到位置j：

式中：r和λ为（0，1）中均匀分布的随机数，参数λ的大小决定了利用先验知识与探索新路径之间的相对重要性；每当一只位于位置i的蚂蚁选择下一个要达到的位置j时，它选取一个随机数r，如果r≤λ，则根据式（2）选择最好的路径，否则按式（1）的概率来选择一条路径，因此增加了所得解的多样性，在一定程度上削弱了蚁群陷入局部最优的趋势。

为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一个循环后，要对残留信息进行更新处理。引入信息素挥发系数ρ，1－ρ称为信息素残留因子且0＜ρ≤1，以防止痕迹上无穷大的信息素。经过n时刻，蚂蚁完成一次循环，各路径上信息素强度进行以下调整，表达式为［4］：

式中，Δτij表示本次循环留在路径（i，j）上的信息素强度；表示第k只蚂蚁在本次循环中留在路径（i，j）上的信息素强度的增量，其表达式为［5，6］：

式中，Q是与第k只蚂蚁所携带的信息度强度和本次循环所走过路径长度有关的量，它影响算法的收敛速度；Lk是蚂蚁k在本次循环中所走路径的长度，其计算公式为：

2.3 改进蚁群算法的实现步骤

基于上述计算公式，下面给出蚁群算法的实现步骤：

①参数初始化。令t＝0时，循环次数NC＝0，循环次数的最大值为NCmax，将m只蚂蚁随机放到n个初始节点处，Δτij（0）＝0；

②循环次数NC＝NC＋1；

③蚂蚁数目k＝k＋1；

④选取r值，与λ进行比较判断；

⑤每只蚂蚁根据式（1）或（2）选择下一节点j并前进；

⑥更新禁忌表，并将蚂蚁移到新的节点；

⑦若节点j不是目的节点，则跳转⑤继续执行；

⑧若k＜m，则跳转③继续执行；

⑨根据式（3）、式（4）和式（5）对路径上的信息素进行更新；

⑩如果蚂蚁全部收敛到一条路径上或NC＞NCmax，则结束。并输出结果，否则清空禁忌表并跳转②继续执行。

3 仿真场景

在MANET中，DSR、AODV和DSDV已被广泛进行研究。蚁群算法在寻找最短路径的路由协议中得到了广泛的应用，研究和分析在各种测试情况下的路由协议的性能，并且比较QoS的一些参数的性能。

3.1 仿真参数设置

仿真工具选用NS2，模拟环境使用的MAC层采用IEEE802.11协议，天线模式全方位，排队模型Droptail，节点总数为50个，所有节点随机分布在500×500 m2的范围内，节点可以随机移动，物理层采用TwoRayGround无线传播模型，并且模拟持续时间为100 s。挥发系数ρ取0.5，信息启发式因子α取1，期望启发式因子β取0.7。由延迟、吞吐量、路由开销、跳数来对ant－DSR、ant－AODV和ant－DSDV的路由协议性能进行仿真分析。

3.2 仿真环境

使用2个场景分别对MANET中ant－DSR、ant－AODV和ant－DSDV的网络性能进行评估。每次结果都取5次仿真的平均值。

第1个场景：增加节点运动速度。这种情况下，使用2～18 m/s的9种不同的速度对路由协议性能进行评估。

第2个场景：不同停留时间。这种情况下使用停顿时间在10～100 s之间，以评估在动态网络中的路由协议的性能。停留时间取值为0时对应最大移动性场景，取值为100 s对应静止场景，随着停留时间的增加，节点移动性随之减弱。越小的暂停时间值将会造成更加复杂的网络拓扑变化，对寻找最佳路径的过程也会产生影响。

4 结果分析

4.1 速率方案

图2显示了不同速率下3种路由协议的仿真结果。ant－DSDV有最小的延迟和跳数，然而有最高的路由开销，ant－DSR可能是较高的吞吐量和最低的路由开销。ant－AODV具有最高的跳数参数。

在这个场景中可以看出在较高吞吐量和较小路由开销是上ant－DSR性能要优于ant－AODV和ant－DSDV。同时，找到最佳路径的复杂过程依赖于设备的功耗。路由开销的增加表示为了在网络上分组发送，路由协议找到最佳路由需要额外的能量。此外，ant－DSDV由于增加了复杂的流程，导致路由开销和额外能量的增加。此种情况下，ant－AODV是最高的跳数参数，但性能最低，而对于按需路由协议，ant－DSR比ant－AODV好。由于数据传输路径上的改变，用户速度的改变可能影响网络配置，这些状况也可能导致较高的误比特率和短暂性的网络分区。

图2 不同速率下各个参数的性能

4.2 停留时间方案

图3显示了不同停留时间下3种路由协议的仿真结果。ant－DSDV在延迟、路由开销和跳数方面比其他的路由协议有较好的性能。

图3 不同停留时间下各个参数的性能

由于网络拓扑可以随意地改变，停留时间的减少会引起路由改变。在这种情况下，路由算法必须解决复杂的情况才能，ant－AODV有最高的路由开销和跳数，而ant－DSR有较长的延迟。这一结果表明，ant－AODV或ant－DSR这2种协议由于网络的复杂性在找到最好的路径情况下可能效果较小，此种情况下ant－DSDV路由协议比按需路由协议更好。

5 结束语

引入的蚁群算法能较好地适应Ad Hoc网络的动态变化，比较了在使用不同的仿真场景下路由协议的整体性能。仿真结果表明，在提高性能方面，ant－DSDV比ant－DSR和ant－AODV较好些。然而由于挥发系数的存在，今后蚁群算法的改进必须考虑路径规划的最优性和寻找最佳路线过程的复杂性。下一步可以对信息素的更新进行改进，使得算法的性能达到更好的效果。

［1］Dorigo M，Gambardella L M.Ant Colonies for the Traveling Salesman Problem［J］.BioSystems，1997，43（2）：73－81.

［2］Dorigo M，Di C G，Gambardella L M.Ant Algorithms for Discrete Optimization.［J］.Artif Life，2000，5（2）：137－72.

［3］Dorigo M，Gambardella L M.Ant Colonies for the Traveling Salesman Problem［J］.BioSystems，1996（3）1－10.

［4］吴华锋，陈信强，毛奇凰，等.基于自然选择策略的蚁群算法求解TSP问题［J］.通信学报，2013，34（4）：165－170.

［5］王越，叶秋冬.蚁群算法在求解最短路径问题上的改进策略［J］.计算机工程与应用，2012，48（13）：35－38.

［6］任兴田，王勇.基于蚁群算法的自适应Ad hoc路由协议［J］.北京工业大学学报，2012，38（5）：744－748.

［7］王学峰，周继鹏.基于蚁群算法的Ad Hoc网络能量均衡路由协议［J］.计算机技术与发展，2014，24（2）：25－28.

［8］周少琼，徐祎，姜丽，等.蚁群优化算法在Ad Hoc网络路由中的应用［J］.计算机应用，2011，31（2）：332－334.

［9］任敬安，涂亚庆.基于蚁群优化的Ad Hoc网络路由协议实现［J］.计算机工程，2012，38（21）：114－118，122.

［10］冯勇，廖瑞华，饶妮妮，等.基于改进蚁群算法的Ad Hoc路由协议的研究［J］.电子与信息学报，2008，30（10）：2472－2475.

［11］郑卫国，田其冲，张磊..基于信息素强度的改进蚁群算法［J］.计算机仿真，2010.27（7）：191－193.

［12］曹洁，王思乐，帅立国.多机器人Ad Hoc路由协议中蚁群算法的改进［J］.兰州理工大学学报，2012，38（6）：73－77.

Comparative Research on Typical Routing Protocols Based on Ant Colony Algorithm

GUO Yan－fang
（Chongqing Key lab of Mobile Communications Technology，Chongqing University of Posts and Telecommunications，Chongqing 400065，China）

Aiming at Ad hoc network changing topology and basic ant colony easy to losemultiple solutions，this paper proposes the combiningmethod of ant colony algorithm and DSR，AODV and DSDV，called ant－DSR，ant－AODV and ant－DSDV after improving the next hop node selection.The improved ant colony algorithm is used to find the optimal path.The end to end delay，throughput，routing overhead，and hop count performance parameters are analyzed and compared in such two scenarios as node rate and pause time.The simulation results show that the first routing protocol ismore adaptable to the ant colony algorithm to improve performance compared with on－demand routing protocols，but it increases routing overhead and requiresmore calculation to find the optimal path in each node.

Ad hoc network；DSR；AODV；DSDV；ant colony algorithm；routing

TP393

A

1003－3114（2015）04－08－4

10.3969/j.issn.1003－3114.2015.04.02

郭彦芳.基于蚁群算法的典型路由协议的比较研究［J］.无线电通信技术，2015，41（4）：08－11.

2015－01－21

长江学者和创新团队发展计划（IRT1299）；重庆市科委项目（CSTC2012jjA40044，cstc2013yykfA40010）；重庆市科委重点实验室专项经费

郭彦芳（1989—），女，硕士研究生，主要研究方向：移动通信、无线Ad Hoc网络。