基于蚁群优化的能量均衡自适应路由算法

杨大鹏

（海军驻重庆地区军事代表局，成都610100）

随着微处理器技术、传感器和低耗能的无线电收发器技术的高速发展，使得大规模的无线传感器网络（Wireless Sensor Networks，WSNs）拥有广阔的应用前景。针对WSNs路由协议的研究是无线传感器网络的热点研究问题之一。与传统有线计算机网络的路由不同，无线传感器网络的网络流量集中在汇聚节点（sink）和源节点之间，具有多对一（many to one）和一对多（one to many）的路由特点[1]。同时，无线传感器网络节点能量受限，高效利用能量始终是路由设计的首要策略。

近年来，针对上述特点提出了很多基于蚁群算法的路由机制[2-6]。蚁群算法是意大利学者Dorigo 于1991年提出的一种启发式仿生进化算法[7]，具有很好的自组织性、正反馈性和并行性，在解决无线传感器网络这种动态路由时有很好的性能[8]。但是目前基于蚁群算法的路由机制在路由的更新和维护方面多是使用定期重构机制（每隔一段时间重新执行路由算法完全重构路由），这种机制带来了很大的网络开销，研究证明[9]这种机制使网络性能缺乏稳定性。本文基于这一问题，提出一种自适应的能量均衡蚁群优化路由算法（ACO based Energy-Balance Adaptive routing algorithm，AEBAR），通过自适应机制实现路由更新和维护，实验证明该算法能够很好地提高路由性能，降低网络开销。

1 基于蚁群优化的能量均衡自适应路由算法

本节对AEBAR 算法在路由初始化、路由建立和路由维护几个阶段的实现进行详细描述。在初始化阶段，使用简单洪泛广播使网络中的节点获得邻居节点信息和自身距离sink节点的跳数位置，路由的构建通过优化记录有邻居节点信息素强度的路由表实现。路由表的优化使用蚁群优化机制实现，算法派发出寻径蚂蚁在多次迭代过程中使用状态转移概率不断试探最优路径，寻径蚂蚁到达sink节点后转换为回退蚂蚁，对路径上的信息素进行更新，从而使路由表得到优化。本算法在状态转移概率的启发信息和信息素更新的求取中都引入了能量水平和跳数水平的权衡机制，综合考虑这2 个因素来选择源节点与sink节点间的最优路径。通过这个策略可实现均衡网络能量，延长网络寿命的目的。路由构建完成之后，进入路由的维护阶段。本算法使用了间断派发侦测蚂蚁的自适应路由维护策略，通过侦测蚂蚁实时地检查路由状态，及时修正最优路径，以避免最优路径负载过重节点过早死亡，同时与定期重构的路由维护机制相比明显的减少了网络开销，提高了网络性能。

1.1 路由初始化

路由初始阶段，所有节点单跳广播其ID 号，每个节点通过接收到的广播信息构建其邻居节点表。当所有节点完成邻居节点表的建立后，sink 节点在整个网络中洪泛一个跳数消息Hops_Message，其中仅包含一个跳数值Hops。

网络节点构建路径跳数参数Node_Hops=0，用于记录各节点与sink 节点之间的网络路径跳数。当网络节点收到Hops_Message 之后，将Hops 值赋予Node_Hops 并对Hops 值进行更新：Hops=Hops+1，然后继续向下洪泛。为了避免节点跳数被带有高跳数值的洪泛消息修改，可引入了本地判断机制，具体表述见式1。

根据式（1），当节点接收到一个跳数消息后，首先进行判断运算，比较节点当前的跳数与消息中跳数的大小。

上述过程其实质是一个梯度建立过程，通过这个过程，网络中每个节点都存有一个跳数值，从而获知自身在网络中与sink节点的跳数位置。

1.2 路由建立

初始化完成之后，网络开始通过基于蚁群优化的路由算法创建各节点到sink 节点的路由。通过派发各自的寻径蚂蚁并行的使用蚁群路由算法，网络中的节点以其自身建立源节点，sink 节点为目的节点的最优路径。在本算法中，将蚂蚁分为2类，一类是由源节点出发的寻径蚂蚁，另一类是从sink节点回溯到源节点的回退蚂蚁。路由建立过程中，寻径蚂蚁从源节点出发，根据邻居节点的路由信息按照概率转移函数选择下一跳节点，若邻居节点中没有路由信息，寻径蚂蚁就通过洪泛广播将自己的副本发送到邻居节点，这些蚂蚁可定义为一代寻径蚂蚁，当同一代寻径蚂蚁到达sink节点后，就找到多条源节点到sink节点的路径，这一代寻径蚂蚁在sink节点转换成回退蚂蚁，各自按原路径返回源节点。在这个过程中回退蚂蚁对相应路径上的信息素进行更新，使网络中每一个节点都生成一个路由表，表中记录了经由该节点到sink节点的路径中该节点的下一跳节点以及之间的信息素强度。

寻径蚂蚁在路由优化过程中依照转移概率Pk(i,j)随机选择下一跳节点，Pk(i,j)表示寻径蚂蚁k从节点i经由邻居节点j到达sink 节点的转移概率。具体实现如下：

式（2）中：α和β分别是信息素启发因子和期望启发式因子，用来衡量信息素和启发信息的权重（本文设α=1，β=2）；Ni表示节点i的邻居节点集合；τk(i,j)表示由源节点k生成的寻径蚂蚁经过节点i与邻居节点j上的链路后在其上留下的信息素，它的值被记录在路由表中，初始情况下τk(i,j)=const；η(j)是寻径蚂蚁选择邻居节点j为下一跳节点的启发信息，

式（3）中：ej,residual为节点j当前能量；C为节点的初始能量；ΔH表示节点i与邻居节点j之间跳数的差值，可由Hj-Hi求得；Hi表示节点i距离sink节点的跳数，在路由初始阶段求得；λ为权重系数，若λ取较大的值则给予能量更多的权重。

寻径蚂蚁完成一次寻径到达sink 节点后转换成回退蚂蚁对生成的路径进行信息素的更新。每只回退蚂蚁都存储有相应路径上各节点能量的一个均值Eavg(k)和路径上的最小能量Emin(k)，Eavg(k)从整体上衡量了路径的能量水平，显然具有高Eavg(k)值的路径更适合作为最优路径传输数据，但是如果一条高Eavg(k)值的路径上存在能量水平很低的节点则会导致路径过早失效，故可引入Emin(k)用来判断路径是否存在瓶颈。Eavg(k)和Emin(k)的值在寻径蚂蚁的寻径过程中由路径上各个节点计算求得。当寻径结束，寻径蚂蚁由源节点到达sink 节点，将记录的路径能量和跳数信息交给sink 节点，sink 节点得到数据后将寻径蚂蚁消亡生成回退蚂蚁，计算出各路径需要更新的信息素后赋予相应的回退蚂蚁。具体的信息素更新公式为

式（4）中信息增量部分Δτk的计算需要兼顾考虑路径长度（路径上的节点跳数）和整个路径的能量水平，若只考虑其中的任一个因素都会影响网络能量的均衡和网络寿命。故可将路径上的节点跳数hop(k)和Eavg(k)、Emin(k)引入到Δτk的求解中：

式（5）中：φ、γ、μ是3 个权重系数，可根据对网络跳数和能量水平的要求取值；Q表示信息素强度，在一定程度上影响算法的收敛速度（本文设置Q=0.8）。

回退蚂蚁沿原路回退到源节点，在这个过程中对路径上所有节点的路由表即信息素表进行更新。至此，相应的源节点就完成了一次路由优化，源节点将该回退蚂蚁消亡，同时生成一个新的寻径蚂蚁开始新一轮的路径寻优。蚁群路由算法设定了路由优化的迭代次数，完成该迭代次数后得出每个源节点到sink节点的最优路径。

1.3 数据转发和自适应路由维护

经过蚁群路由算法对网络路由优化之后，每个节点的路由表得到优化更新，节点根据路由表记录的邻居节点信息素强度选择转发数据包的下一跳节点。节点路由表中记录的信息素是与源节点相对应的，源节点发出的数据包绑定有源节点的标识，转发节点通过该标识找到匹配的信息素转发数据包。具体的数据转发策略使用下式描述∶

考虑到网络中节点在数据的生成、处理和转发过程中能量不断地消耗，以及传感器网络拓扑结构动态特性，初始创建的最优路由会失去最优性，故在网络的寿命周期里需要对路由进行定期的更新和维护。在以往的基于蚁群优化的路由算法研究中，例如文献[10]提出的一种基于蚁群优化的路由算法EEABR，大多是使用定期重新运行路由生成算法重构整个网络路由的策略，研究证明[4]基于蚁群优化的路由算法在优化过程中引起的网络开销是十分可观的，定期执行算法对路由进行更新对网络能量带来极大消耗，并且在重构期间网络完全停止监控功能处于失效状态严重影响网络效率。本文受文献[11]启发，引入一种自适应的路由更新和维护策略——基于侦测蚂蚁的路由更新和维护机制。该机制针对WSNs中网络节点生成监测数据存在周期性的特性，设置各源节点每发送N个监测数据包就发出一个侦测蚂蚁（N的取值需根据网络的数据生成率情况进行设置），侦测蚂蚁通过转移概率随机选择路径到达sink 节点，概率实现如下：

式（7）中，φ的取值大于式（2）中α的取值（本文设置φ=2）。使用较大的权重系数可以使侦测蚂蚁有更大的概率采集非最优路径的信息，实现对所有可达路径进行侦测，更全面地掌握路径信息。

侦测蚂蚁在侦测过程中采集路径上所有节点的能量和跳数信息，在sink节点计算得到该路径需要更新的信息素后，带着信息素增量沿原路返回，执行与回退蚂蚁相同的功能，对路径的信息素进行更新。通过使用侦测蚂蚁，可以相对实时地获得路径的能量状态，从而能够及时更新路由并使其处于最优状态。同时，基于侦测蚂蚁的路由维护策略带来的网络开销相对于定期重构策略有明显的下降。

2 算法仿真与比较

本节使用NS2 仿真平台对AEBAR 算法进行仿真，并与使用定期重构策略的EEABR 路由算法进行比较。仿真模型假设M个传感器节点随机布置在监测区域中，M在50～500间取值。每个传感器节点的初始能量一致，sink节点能量能够不断补充在仿真时间里，可视为无限，详细配置见表1。

表1 模拟实验环境

仿真使用数据转发率和网络寿命2个指标对2个算法的性能进行比较。数据转发率在本实验中定义为仿真结束后sink 节点接收到的数据包与网络源节点发送数据包的比值。为了全面衡量网络的寿命水平，本文使用了网络节点剩余能量的均值和节点剩余能量的标准差2个指标。节点剩余能量均值能够很好地反映网络整体的能耗状况，而节点剩余能量标准差则能够客观的反映网络能耗的均衡性。故本文将节点剩余能量均值与节点剩余能量标准差的比率均值作为衡量网络寿命的指标。

图1描述了在不同的网络规模下两个算法的数据转发率。通过比较可以看出，随着网络规模的变化AEBAR 算法相对于EEABR 在数据转发率方面具有更稳定地表现。这主要是由于EEABR算法采用定期重构策略的路由更新机制使得网络的控制开销增大，导致网络链路拥塞出现数据丢包；而使用自适应路由维护机制的AEBAR算法只在有监测数据包传输的情况下间断发送少量侦测蚂蚁对网络进行维护和更新，与EEABR 算法相比明显地降低了网络的控制开销，使网络有良好的数据转发率，网络的性能表现更加稳定。

图1 不同网络规模下的数据转发率

图2描述了在几种网络规模下2种算法在网络寿命比率方面的比较。从图2 中的曲线可以看出，AEBAR算法较之EEABR算法有更加平缓的表现。由于本文定义网络寿命比率为网络节点剩余能量均值与节点剩余能量标准差均值的比率，所以，AEBAR算法使网络中节点的能量消耗更加均衡，特别是当网络规模增大时，本文提出的AEBAR 算法在能量均衡方面较之EEABR 算法有明显平稳的表现。同时，网络的绝对寿命也优于EEABR算法。这种性能表现是由于AEBAR算法在信息素增量的求解中引入了能量均衡因子，使得在选择最优路径时兼顾了路径的能量水平，较好地均衡了网络的能量消耗。

3 结论

由于无线传感器网络的特点，能量消耗问题一直是设计路由算法需要考虑的首要因素。本文提出的基于蚁群优化的自适应路由算法（AEBAR），通过改进蚁群优化算法，针对无线传感器网络特点在算法中引入能量均衡因子，从而在能量消耗和能量均衡方面有优良的表现。同时，目前在基于蚁群优化的路由研究方面多使用定期更新的路由维护策略，这种策略带来的网络开销较大在很大程度上影响了网络性能。针对这一情况，本文提出了一种使用侦测蚂蚁的自适应路由维护策略，通过仿真实验证明该策略很好的提升了网络性能。目前，本文提出的算法是针对静止节点的网络结构设计的，下一步研究将主要在引入节点移动性的前提下改进、完善AEBAR算法。

[1] 唐勇，周天明，张欣.无线传感器网络路由协议研究进展[J].软件学报，2006，17（3）：411-412.

TANG YONG，ZHOU TIANMING，ZHANG XIN. Overview of routing protocols in wireless sensor networks[J].Journal of Software，2006，17（3）：411-412.（in Chinese）

[2] SELCUK OKDEM，DERVIS KARABOGA. Routing in wireless sensor networks using ant colony optimization[C]//Proceedings of the First NASA/ESA Conference on Adaptive Hardware and Systems.Istanbul，Turkey，2006：401-404.

[3] QI BING，ZHAO CHUNHUI. Ant algorithm based load balancing for network sessions[C]//3rd International Conference on Natural Computation. Haikou，China，2007：771-775.

[4] SHOKRANI H，JABBEHDARI S. A survey of ant-based routing algorithms for mobile ad-hoc networks[C]//International Conference on Signal Processing Systems.Singapore，2009：323-329.

[5] CAI WENYU，JIN XINYU，ZHANG YU，et al. ACO based qos routing algorithm for wireless sensor networks[C]//International Conference on Ubiquitous and Computing.Wuhan，China，2006：419-428.

[6] YE NING，WANG RUCHUAN，SUN LIJUAN. A routing scheme for data aggregation based on ant-like agent in wireless sensor networks[J]. Chinese Journal of Electronics，2007，16（3）：449-453.

[7] MARCO DORIGO，MAURO BIRATTARI. Ant colony optimization[J]. IEEE Computational Intelligence Magazine，2006，1（4）：29-30.

[8] 段海滨. 蚁群算法原理及其应用[M]. 北京：科学出版社，2005：24-26.

DUAN HAIBIN.Ant colony algorithm and its application[M].Beijing：Science Press，2005：24-26.（in Chinese）

[9] MUHAMMAD SALEEM，MUDDASSAR FAROOQ. A framework for empirical evaluation of nature inspired routing protocols for wireless sensor networks[C]//IEEE Congresson Evolutionary Computation. Singapore，2007：751-758.

[10] TIAGO CAMILO，CARLOS CARRETO，JORGE SA SILVA，et al. An energy-efficient ant-based routing algorithm for wireless sensor networks[C]//Proceedings of the 5thInternational Conference on Ant Colony Optimization and Swarm Intelligence.Brussels，Belgium，2006：50-59.

[11] 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.