李 劲，周继鹏

（暨南大学 信息科学技术学院，广东 广州510632）

0 引 言

与传统路由算法相比，Ad Hoc网络路由算法的设计面临着网络拓扑动态变化、带宽受限、移动终端有限的可用资源等新问题的挑战。考虑到节点能量的有限性，为了避免由于节点能量耗尽而导致整个网络的瘫痪，本文提出一种基于蚁群优化 （ACO）的Ad Hoc路由算法，较之现有的能量有效路由算法在路由发现和数据转发阶段都具有优势。将路径长度和节点剩余能量同时作为路由选择标准，并采用多路径的数据转发，在减少能量耗费的同时平衡了网络负载，以期延长网络的生存时间。

1 相关工作

对于Ad Hoc网络，延长节点电池能量的使用时间是一个关键问题。传统的路由算法如 AODV［2］、DSR［3］和TORA［4］选择最短路径进行数据转发，并不关注节点的能量问题。这样的路由选择往往会导致处于最短路径上的节点能量消耗更快，从而加速了能量耗尽节点的产生，不利于延长网络的生存期。为了改善传统路由算法的能量限制问题，文献 ［5－11］提出了若干能量有效的Ad Hoc路由算法，以下介绍其中具有代表性的几种算法。

MTPR［5］路由算法根据路径的总能量消耗进行路由选择。路径的能量消耗为，路径上所有节点为完成数据转发所需的能量之和。选择具有最小能量消耗的路径进行数据转发，但是由于没有考虑节点的剩余能量，所以MTPR在达成最小路径能耗时并不能保证节点的生存时间得以延长。MMBCR［6］路由算法为了延长节点的生存期，将节点剩余能量作为路由选择标准，选择具有最大剩余能量的路径完成数据转发。在路由发现过程中，选出路径上剩余能量最小的节点，将其剩余能量作为路径的剩余能量。路径剩余能量越大说明路径的生存期越长。MDR［7］路由算法引入能量消耗速率，根据时下节点的能量消耗速率和剩余能量预测节点的生存时间，以路径上节点的最小生存时间作为路径的生存时间，选择具有最大生存时间的路径进行数据转发。但是能量消耗速率并不能准确得出，而且根据当前能量消耗速率来预测可能会出现较大误差。

基于Aco的路由算法是一种有效的、自适应的路由算法。Aco利用集群智能模仿自然界中真实蚁群的觅食过程。文献 ［1］中实验证明蚂蚁具有搜索从蚁穴到食物间最短路径的集体寻优特性，这是由于蚂蚁会在所经过的路径上留下一种称之为信息素的易挥发物质，而且蚂蚁更倾向于朝着信息素浓度高的方向移动，这使得蚂蚁在群体层次上呈现为一种正反馈现象，路径越短，信息素浓度越高，选择该路径的概率更大。在Aco路由算法中，Ant是由节点独立产生的特殊分组，用来测试到一指定节点的路径，ant从源节点到目的节点的过程中收集路径信息，在到达目的节点后按原路径返回源节点，并根据收集到的路径信息更新源节点到目的节点信息素，路径质量越高信息素越高。每个节点维护一张信息素表，节点根据信息素进行路由选择，既可以贪婪选择信息素最高的路径，也可从不同路径中概率选择，即信息素越高选择该路径的概率越大。路由选择的随机性使得到同一目的节点的数据可分散在不同路径上，越高质量路径上的数据包越多，达到网络负载的平衡。现有Aco路由算法可分为：先应式的路由算法，Accelerated Ants Routing［12］中节点定期产生ant，不需要为ant指定目的节点，ant在网络中漫游的过程中收集信息 （跳数、时延等），利用其更新经过节点到源节点的信息素；反应式的路由算法，在PERA［13］中，ant由节点按需产生，用于寻找到某个目的节点的路径，ant的转发不利用信息素信息，而是向目的节点广播，路由发现过程中形成多条路径，但数据包只贪婪转发至信息素最高的路径；混合式的路由算法，ARA［14］和 AntHocNet［15］具有反应式的路径构造和先应式的路径维护，ant在节点需要建立到目的节点的路径时产生，中间节点根据信息素表概率转发ant，当没有目的节点信息素时将ant广播至所有邻居，在ant到达目的节点后按原路径返回源节点完成信息素更新，路径建立后通过周期性的产生ant维护现有路径，文献 ［16］在此基础上引入地理位置信息辅助路由过程。

本文基于ACO路由算法提出一种能量有效的Ad Hoc路由算法EANT。基于ACO的EANT较之现有的能量有效路由算法在路由发现和数据转发阶段都具有优势。以MMBCR为例，在路由发现阶段，EANT借助信息素表获得所有可能路径，比MMBCR洪泛的方式更加有效和节能；在数据转发阶段，EANT利用概率转发形成多路径的数据传输，比MMBCR唯一路径的方式更好地平衡了网络负载，更多节点的参与延长了节点的生存时间，减缓了能量耗尽节点的出现。EANT在完成信息素更新时，综合了路径跳数和节点剩余能量，路径跳数越少，相同数据量转发所耗费的能量也就越少，路径总能量消耗越低则信息素越高；由路径上所有节点的平均剩余能量和其中的最小剩余能量决定路径的能量水平，优先选择节点剩余能量的多的节点参与数据转发。

2 路由算法

2.1 网络模型

将Ad Hoc网络抽象为一个有向图G＝ （V，E）。其中V是所有移动节点的有限集合，E是无线链路的有限集合。链路 （u，v）∈L表示节点v在节点u的传输范围内，v是u的邻居节点，u可以向v进行数据传输，N （u）表示节点u的邻居集合，E（u）表示节点u的剩余能量。

每个节点维护一张信息素表，用以记录当前链路的信息素。如表1为节点u的信息素表，其中以目的节点为关键字，vd代表节点u经过邻居v到达d的信息素。

表1 节点信息素表

2.2 路由发现

路由发现过程参考了AntHocNet［15］中的一些架构，但与AntHocNet［15］在本质上有着功能性的不同。路由发现是按需的，当源节点信息素表中没有目的节点的信息时，由源节点产生前向蚂蚁Fant进行路由发现。Fant分组结构如下所示，其中源节点和ID唯一确认了一个Fant，节点可丢弃重复接收的Fant以避免回路产生，List域记录了Fant经过的所有节点，TTL限制了Fant的跳数。

源节点 ID 目的节点List TTL

源节点将Fant广播至所有邻居节点，中间节点在收到Fant后，或是广播至所有邻居，或是按照式 （1）选择唯一邻居转发。若中间节点信息素表中没有目的节点信息，则将Fant转发至所有邻居，否则将概率转发Fant。

式 （1）为节点u选择邻居v为下一跳的概率，其中d为目的节点，N （u）为节点u的邻居集合，Φvd为u经v到达的d信息素，γ为放大系数。根据式 （1），若Φvd越大则节点u选择v为下一跳的概率越大。γ较大时，概率大部分集中在信息素较大的链路上，Fant的探测性较小，反之可以使Fant具有较大探测性。

Fant到达目的节点后，由目的节点产生后向蚂蚁Bant按Fant的原路径返回源节点，Bant更新经过节点到目的节点的信息素。Bant的分组结构如下所示，其中List由Fant复制而来，Bant按照List中的节点路径返回源节点，H为Bant经过的路径长度即跳数，Emin为路径最小剩余能量，即Bant经过节点中的最小节点剩余能量，Esum为路径上节点剩余能量之和，H、Emin和Esum由目的节点分别初始化为0、∞和0。

源节点 目的节点 List H Emin Esum_____

Bant到达中间节点后，更新中间节点的信息素表。中间节点n在收到来自邻居n－1的Bant后，节点n利用H、Emin和Eavg更新n信息素表中目的节点的信息素项，若没有相关项则建立新的信息素表项，以目的节点为关键字，Bant的上游节点作为下一跳，根据Bant的跳数和路径能量水平按照式 （2）、（3）更新信息素。本文将路径跳数和路径能量水平同时纳入考量，路径跳数越少，数据包转发次数亦越少，则路径消耗的总量能量越少；在考虑路径上节点剩余能量时，综合了剩余能量的最小值和平均值，路径平均能量越多、路径最小能量越大则路径质量越高。式（3）反应了上述数量关系，路径质量越高则信息素越高，其中α，β为相关系数，调整H、Emin和Eavg所占比重。

中间节点n完成信息素表更新后，按照式 （4）～ （6）更新Bant中的H、和Emin和Esum，其中E（n）为n的剩余能量。

上述路由发现的一般过程可描述为：

步骤1：源节点产生Fant并广播至所有邻居节点。

步骤2：中间节点在收到Fant后，根据Fant的源节点和ID确定是否重复接受，丢弃重复接收的Fant以避免回路和不必要负载的产生。

步骤3：中间节点按照式 （1）概率选择Fant的下一跳节点，若信息素表中没有目的节点的信息，则将Fant转发至所有邻居。

步骤4：Fant到达目的节点后，由目的节点产生Bant按照原路径返回源节点，Bant在中间节点处按照式 （2）、（3）更新节点的信息素表，按照式 （4）～ （6）更新Bant中的相关项。Bant返回源节点后路由发现过程结束。

2.3 路由维护

在路由建立之后，数据包的转发过程就可以对路由进行维护。如同AntHocNet［15］中，当一个数据包由源节点发往目的节点的过程中，经过的中间节点的信息素都会增加，同时没有数据包经过的节点的信息素会以一定的速率挥发，其过程如式 （7）所示，其中δ为挥发速率δ∈ （0，0.5），Δ为每个数据包经过时增加的信息素。这样的路由维护方式使得信息素迭代性的增加，只有在一段时间内都表现良好的路径才能获得较大的信息素。

节点根据信息素表概率转发数据包。数据包同样根据式 （1）所得概率选择下一跳，较之Fant数据包转发不需要较大的探测性，取较大的γ。

当数据包转发过程中检测到链路中断，并且节点信息素表中没有可用链接。首先由路由失败节点产生Fant进行局部路由发现。为了将局部Fant约束在源路径周围，可限制Fant的TTL域，节点设置定时器，一定时间内没有收到Bant则标记路由失败，通知所有受到影响的源节点重新进行路由发现。

3 仿真实验

实验是在NS2仿真平台上完成的，仿真结果如图1、2、3所示。从图1中可以看出，无论节点的移动速度快慢，数据包成功接收所经过的平均跳数比MMBCR均有减少。图2、3显示能量耗尽节点出现的时间都有明显推迟，进而说明网络生存期更长。实验结果与设计原理相符，由于在信息素更新中加入路径能量水平，同时数据传输以多路径的形式完成，能够使节点能量的使用时间延长，进而延长网路的生存期。

图1 仿真结果1

4 结束语

针对Ad Hoc网络中移动设备有限能量的限制，提出了一种基于蚁群优化的能量有效路由算法。较之以往的能量有效路由算法，采用了基于蚁群优化算法的路由发现和多路径的数据传输，避免了洪泛式的路由发现，减少了节点能量耗费，并通过有效的多路径传输平衡了网络负载。实验结果证明，EANT路由算法在性能上优于MMBCR，平均跳数有明显减少，网络生存期延长，蚁群优化算法应用于Ad Hoc网络是很有意义的。

［1］Marco Dorigo，Thomas Stutzle.Ant colony optimization ［J］.Computational Intelligence Magazine，2006，1 （4）：28－39.

［2］Charles E Perkins，Elizabeth M Belding－Royer，Samir Das.Ad－Hoc on－demand distance vector routing ［C］.New Orleans：Proceedings of IEEE WMCSA，1999.

［3］David B Johnson，David A Maltz.Dynamic source routing in Ad Hoc wireless networks ［C］.Norwell：The Kluwer International Series in Engineering and Computer Science，1996.

［4］Vincent D Park，Scott Corson M.A highly adaptive distributed routing algorithm for mobile wireless networks ［C］.Japan：Proceedings of IEEE INFOCOM，1997.

［5］Scott K，Bambos N.Routing and channel assignment for low power transmission in PCS ［C］.Massachusetts：5th IEEE International Conference on Universal Personal Communications，1996.

［6］Suresh Singh，Mike Woo.Power－aware routing in mobile Ad Hoc networks［C］.New York：Proceedings of the 4th Annual ACM／IEEE International Conference on Mobile Computing and Networking，1998.

［7］Dongkyun Kim，Obraczka K，Cano J C，et al.Power－aware routing based on the energy drain rate for mobile Ad Hoc networks［C］.Florida：Proceedings of the 11th International Conference on Computer Communications and Networks，2002.

［8］Anand Srinivas，Eytan Modiano.Finding minimum energy disjoint paths in wireless Ad Hoc networks ［J］.Wireless Networks，2005，11 （4）：401－417.

［9］Kwon S，Ness B Shroff.Energy－efficient interference－based routing for multi－hop wireless networks ［C］.Spain：25th IEEE INFOCOM，2006.

［10］Hassanein H，JING Luo.Reliable energy aware routing in wireless sensor networks ［C］.Columbia：IEEE Workshop DSSNS，2006.

［11］Shresta N.Reception awareness for energy conservation in Ad Hoc networks ［D］.Sydney：Macquarie University，2006：1－175.

［12］Hiroshi Matsuo，Kouichi Mori.Accelerated ants routing in dynamic networks［C］.Korea：Proceedings of the International Conference on Software Engineering Artificial Intelligence Networking and Parallel Distributed Computing，2001.

［13］John S Baras，Harsh Mehta.A probabilistic emergent routing algorithm for mobile Ad Hoc networks［C］.France：Proc of the Conference on Modeling and Optimization in Mobile Ad Hoc and Wireless Networks，2003.

［14］Mesut Gunes，Udo Sorges，Imed Bouazizi.ARA：The ant colony based routing algorithm for MANETS ［C］.Canada：31st International Conference Parallel Processing Workshops，2002.

［15］Gianni Di Caro，Frederick Ducatelle，Luca Maria Gambardella.AntHocNet：An adaptive nature－inspired algorithm for routing in mobile Ad Hoc networks ［J］.European Transactions on Telecommunications，2005，16 （5）：443－455.

［16］Daisuke Kadono，Tomoko Izumi，Fukuhito Ooshita，et al.An ant colony optimization routing based on robustness for Ad Hoc networks with GPSs ［J］.Ad Hoc Networks，2010，8（1）：63－76.