基于信息素扩散模型蚁群算法的无线传感网路由研究*

鲍 荣，潘 浩，董齐芬，俞 立，邵 磊

(浙江工业大学信息工程学院，杭州 310023)

无线传感网是指由部署在监测区域内大量的廉价微型传感器节点通过无线通信方式形成的一个多跳自组织网络系统。与传统的移动自组织网络不同，无线传感网中每个节点的能量十分有限，且大规模节点的能量补充通常较为困难，故有必要研究一种能量高效的路由算法，使数据传输选择最优路径的同时，能延长网络的生命周期［1］。无线传感网发展至今，已提出许多路由协议。如LEACH协议［2］、Gossiping协议［3］、PEGASIS 协议［4］等，但这些协议对动态网络的适应性并不理想。

近年来，仿生学最优寻解算法受到广泛关注，如，粒子群优化算法［5］源于鸟群觅食行为，具有易实现、收敛快等特点，但容易陷入局部最优;差分进化算法［6］是基于群体进化的启发式搜索技术，鲁棒性较强、收敛快，但也存在局部优化较弱的缺点;蜂群算法［7］把每个蜜蜂都看做一个智能体，通过蜂群个体协同作用达到群体智能的效果。然而，这些寻优算法由于自身算法模型的局限，在路径优化方面的适用性不强。当前，普遍认为将蚁群算法［8］应用到无线传感网路由协议中是较为可行有效的。文献［9］提出一种基于蚁群的多路径路由算法，通过负荷平衡机制达到平衡节点能耗的目的，提高了能量效率。文献［10］提出一种最优能量消耗蚁群路由算法，通过能量最佳分配机制使得节点能耗降低，延长了网络生存周期。文献［11］的EEABR协议将节点能量水平和传输距离引入信息素更新公式。文献［12］根据路径上最低的能量水平来评估信息素增量。与其它路由算法相比，基于蚁群算法的无线传感网路由协议有以下优点［13］:(1)自适应性好;(2)鲁棒性强;(3)支持多路径;(4)具有局部/全局优化能力;(5)易与其它算法相结合。但目前大多数的蚁群路由算法具有一定的局限性，或没有考虑蚂蚁的反向传输，导致传输时延加大，或没有考虑动态网络的情况。

本文对基于蚁群算法的路由协议进行了深入研究，提出一种能量高效的基于信息素扩散模型的蚁群路由优化算法(Diffusion-based Ant Colony Routing Algorithm，DBACRA)。该算法由实际和虚拟两种信息素共同指引路由包与数据包进行偏向性的路径搜索，并考虑节点剩余能量以平衡全网的能耗，从而延长整个网络的生命周期。最后，通过TOSSIM仿真验证该路由协议的有效性及能耗、时延及网络寿命等方面的性能。

1 预备知识

1.1 蚁群算法概述

蚁群算法［8］(Ant Colony Algorithm，ACA)由意大利学者Dorigo等人提出，其灵感来源于自然界中蚂蚁群体觅食寻径行为:蚂蚁随机搜索蚁穴周围区域，当一只蚂蚁找到食物源，它会在回程中留下一种称为信息素的挥发性分泌物，其他蚂蚁可根据其浓度决定寻食路径。对于一条路径，经过的蚂蚁越多，则信息素浓度越大，从而吸引更多蚂蚁，形成一种正反馈，使得蚂蚁最终可以发现最短路径。

近年来，蚁群算法被广泛应用于路由算法中，以下介绍一种基于基本蚁群的路由算法。

1.2 基本蚁群路由算法数学模型

基本蚁群路由算法(Basic Ant Colony Routing Algorithm，BACRA)中，人工蚂蚁模拟真实蚂蚁，通过信息素量与能量启发因子权衡，寻找最优路径。

源节点创建前向蚂蚁，该蚂蚁按照如式(1)所示的概率选择下一跳节点，并记录沿途节点。

前向蚂蚁到达目的节点后，转换为后向蚂蚁并原路返回。当节点i接收从节点j发送的后向蚂蚁时，节点i所有通信路径的信息素进行挥发，挥发完成后，后向蚂蚁在其经过的路径上释放信息素:

其中，

式中，是挥发完成蚂蚁释放信息素后，该节点的信息素量，ρ是信息素的挥发率，且 0＜ρ≤1。Δτij是后向蚂蚁释放的信息素量，w是调整信息素释放量的权值。是从节点i经节点j到达目的节点d链路代价，标识路径长短的跳数。

在无线传感网中，节点失效、新节点加入或节点移动都会造成网络拓扑结构的动态变化，而BACRA算法易陷入局部最优解，且传输时延长，因此不能适应这种变化。因此，本文提出DBACRA算法，该算法在解决这种局限性的同时，有效减少节点能耗，延长生命周期。

2 改进的蚁群优化算法——DBACRA算法

该算法在BACRA算法基础上引入实际信息素和虚拟信息素的概念，从扩散模型、路由优化和数据传输三方面进行改进。人工蚂蚁结合实际信息素、虚拟信息素及能量信息来寻找最优路径，并能更新实际信息素的分布。虚拟信息素基于扩散模型，能快速反映网络的动态。由于虚拟信息素不断扩散开来，具有不可靠性，故数据包的传输仅根据实际信息素和能量来选择路径。

2.1 扩散模型

建立信息素的扩散模型是可行的，且有利于路由信息的分享。扩散模型是指网络中所有节点在其生命周期内不断广播路由信息及其剩余能量值。任意节点j构造的扩散消息包应包含一张表:目的节点d、到达该目的节点的最佳信息素以及节点j的剩余能量。其中，最佳信息素的计算如式(4)所示:

当节点i接收到节点j广播的扩散包时，更新邻居表中该邻居节点j的能量值。若没有节点j，则将其加入到邻居表。然后，计算节点i经过邻居节点j到达目的节点d的引导信息素，即综合考虑最佳信息素和链路代价得出的信息素:

式中，为节点i到节点j的链路代价，可用跳数表示。由于由扩散过程得到，具有不可靠性，故依赖于的引导信息素也具有不可靠性，故将其更新到虚拟信息素中:

路由系统刚启动时，由目的节点扩散固定的信息素值，经几轮扩散后，整个网络将形成信息素的初始分布，即建立路由梯度。文献［10］发现蚁群路由算法在高动态网络中性能较差，在初始状态下前向蚂蚁缺乏可用信息，导致收敛较慢。本文改进的蚁群算法结合扩散模型，有利于在初始状态指导前向蚂蚁的偏向性搜索，故能快速适应动态变化的网络。

考虑到扩散过程带有通信开销，而无线通信的能耗远大于计算能耗，因此本文采用定时和事件触发的方式来选择发送时机，以减少扩散消息的数量。最近一次扩散消息的发送时间以及包含的信息素值和能量值都会被记录。一旦间隔上次扩散达一定时间，或者当前最佳信息素值或能量值的变化量超过预设的阈值，都会触发扩散行为。扩散过程还可用于检测通信链路的状况，能及时反映出网络结构的动态变化。当节点i连续长时间未接收到节点j的扩散消息，可认为通信链路(i，j)存在问题，或尝试修复，或踢除其邻居关系。

2.2 路由优化

类似于基本蚁群路由算法，源节点发送前向蚂蚁，但前向蚂蚁在选择下一跳节点时应兼顾虚拟信息素，使得系统可以快速启动，并更好地适应网络拓扑和能量水平的动态变化，如式(7)所述。当前向蚂蚁到达目的节点后，则原路返回并更新实际信息素，与基本蚁群路由的更新过程相同。

目的节点d的邻居节点i因扩散过程的作用，总是接收到由d扩散的固定量的信息素，并在路由系统启动时得到与虚拟信息素等值的实际信息素。随着路由优化过程的不断迭代，人工蚂蚁会在节点i上播撒实际信息素，使实际信息素的浓度超过虚拟信息素。于是，实际信息素将被选为最佳信息素，并继续扩散开来，影响外围节点的虚拟信息素。

2.3 数据传输

数据包的传输根据实际信息素来选择下一跳节点，其概率如式(1)所述，但式中的参数α和β可以与路由优化过程有所不同，即根据数据传输的需要来权衡实际信息素和剩余能量的重要性。

随着数据传输的不断进行，目的节点周围区域承受的通信流量较大，使外围节点的能量水平显著大于目标附近的节点，这就可能导致数据包偏向于朝相反方向进行传递。虽然可通过更多的蚂蚁来加大信息素浓度差，但其通信开销较大。由于数据传输本身存在概率选择，且其传输服务的质量可为路由提供参考，因此本文在DBACRA算法的基础上提出带有奖惩机制的DBACRA-PP算法(DBACRA with Premium-Penalty)，根据传输情况对实际信息素进行奖惩，从而优化路由。当某条通信路径的数据流量每达到一定额度就给与其奖励，这使得目的节点附近获得较多奖励，更有利于吸引数据朝目的节点传递。此外，当某条通信链路不稳定，出现较多丢包时，可对其实际信息素采取适当惩罚。这种奖惩机制只需付出较小的计算开销，就能使得数据传输服务支持路由的更新。

3 仿真实验与结果分析

为了验证本文所提路由算法的性能，在TinyOS操作系统中分别实现BACRA协议、DBACRA协议、DBACRA-PP协议以及CTP协议。CTP协议［14］是无线传感网中较为常用的路由协议，它是基于树的，为网络节点提供到根节点的全力的，任意传播的传输机制。本文的仿真环境采用TOSSIM平台，可以支持大规模的网络仿真。为使仿真服务更贴近真实环境，加载斯坦福大学Meyer图书馆的噪声数据，从而模拟出射频噪声及节点间的相互干扰［15］。

仿真采用100个节点，使其均匀随机地分布在100×100单位区域内。节点最大传输距离约为20个单位。假设源节点与目的节点具有充足的能量供应，分别位于正方形区域的左下角与右上角。其他节点的初始能量为10 000单位，发送和接收一个消息消耗5单位。源节点每隔1s产生一个数据包，仿真持续到出现第一个能量耗尽的节点，并将该持续时间定义为网络生命周期。本实验中，其余参数选取如下:α=2，β=4，ρ=0.9，η=0.2(经过多次实验对比，当取得这些参数时系统性能较好);奖惩机制的奖励与惩罚的比例均为5%。假设源节点在发送数据前，已成功完成20次蚂蚁迭代，随后每30个数据包发送一个前向蚂蚁，其仿真性能如表1所示(表中数据均由50次仿真结果取平均值获得)。

表1 路由算法性能比较

由表1可看出，DBACRA协议的生命周期相比BACRA协议提高12%，在端到端的平均时延方面也显著缩短了15%。平均能耗指传输一个数据包需要消耗的全网能量。可见，DBACRA协议由于平均时延大大缩短而使平均能耗减少了10%左右。DBACRA-PP协议与DBACRA协议相比，在生命周期方面的优势较明显，可见奖惩机制具有一定的路由优化能力。与CTP协议的比较可看出，CTP协议在平均时延和能耗方面有着显著优势，这是因为其路径优化没有考虑能量因素，易收敛于局部路径。这会导致其快速耗尽少数节点的能量，故生命周期仅为蚁群算法的一半。考虑到算法差别较大，下面不再与CTP协议作仿真对比。

进一步，研究初始蚂蚁的迭代次数对蚁群路由协议性能的影响。图1给出了不同初始蚂蚁情况下的平均时延。初始蚂蚁越少，改进协议的平均时延与BACRA协议就相差越大。这是由于改进协议的扩散模型可以快速建立路由梯度，而BACRA协议需多次迭代后才能优化信息素的分布。值得注意的是，DBACRA-PP协议相比DBACRA协议只有略微的优势，但在初始蚂蚁较少时效果较明显。

图1 不同数量初始蚂蚁下的平均时延比较

图2表示三种路由协议运行过程中的时延变化情况。BACRA协议在启动后迅速收敛，故时延下降较快，但仍显著大于改进协议。在运行900s后，BACRA协议逐渐收敛于局部较优解，在缩短时延的同时，导致部分节点的能量快速消耗，运行时间缩短。改进协议能更好地适应全网能量的动态变化，故有较长的生命周期。DBACRA-PP协议由于采用奖惩机制降低了数据包反向传递的概率，故其传输时延比DBACRA协议稍好。

图2 端到端传输时延的变化

4 结论

针对无线传感网能量有限、动态变化的特点，本文提出一种基于蚁群算法的路由协议，采用信息素扩散模型，由实际和虚拟两种信息素共同指引蚂蚁和数据的偏向性路径搜索。信息素的扩散有利于路由系统的快速启动，并能及时适应网络拓扑和能量水平的动态变化。另外，根据数据传输的情况对信息素采取适当的奖励与惩罚，使得数据传输支持路由更新。经仿真验证，改进协议具有较强的适应性，能较好地均衡全网能耗，有效延长整个网络的生命周期。

［1］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］//Proc.of the 33rd Annual Hawaii Int Conf.on System Sciences.Maui:IEEE Computer Society，2000:3005－3014.

［2］Jing Yang，Yi Lin，Weili Xiong，et al.Ant Colony-Based Multi-Path Routing Algorithm for Wireless Sensor Networks［C］//Proc.of the International Workshop on Intelligent Systems and Applications.Wuhan，2009:1－4.

［3］Hedetniemi S，Liestman A.A Survey of Gossiping and Broadcasting in Communication Networks［J］.Networks，1988，18(4):319－349.

［4］Lindsey S，Raghavendra C S.PEGASIS:Power-Efficient Gathering in Sensor Information Systems［C］//Proc.of the IEEE Aerospace Conf.Montana:IEEE Aerospace and Electronic Systems Society，2002:1125－1130.

［5］Jelmer van Ast，Robert Babuska，Bart De Schutter.Particle Swarms in Optimization and Control［C］//Proceedings of the 17th World Congress The International Federation of Automatic Control.Seoul，Korea，July 6－11，2008:5131－5136.

［6］Lopez C I L，van Willigenburg L G，van Straten G.Efficient DifferentialEvolution AlgorithmsforMuhimodalOptimalControl Problems［J］.Applied Soft Computing，2003，3(2):97－122.

［7］Liu Lu，Qi Luo，Junyong Liu，et al.An Improved Particle Swarm Optimization Algorithm［C］//Granular Computing，IEEE International Conference.2008:486－490.

［8］段海滨.蚁群算法原理及其应用［M］.北京:科学出版社，2005.

［9］Kalaavathi B，Madhavi S，VijayaRagavan S，et al.Review of ant based routing protocols for manet［C］//Proc.of the 2008 Int Conf on Computing，Communication and Networking.Thomas，2008:1－9.

［10］Wei Gao，Qinglin Sun，Zengqiang Chen.Optimal Energy Consumption in Wireless Sensor Networks by Using the Ant Colony Algorithm(ACA)［C］//Interational Conference on Computer and Communication Technologies in Agriculture Engineering.Chengdu，2010:189－192.

［11］Camilo T，Carreto C，Silva J，et al.An Energy-Efficient Ant-Based Routing Algorithm for Wireless Sensor Networks［C］//Proc.of the International Workshop on Ant Colony Optimization and Swarm Intelligence.Brussels，2006:49－59.

［12］王结太，许家栋，徐建城.基于蚁群优化算法的无线传感器网络路由协议［J］.系统仿真学报，2008，20(18):4898－4901.

［13］Colorni A，Dorigo M，Maniezzo V.Distributed Optimization by Ant Colonies［C］//Proc.of ECAL91-European Conference on Artificial Life.Paris，France:Elsevier Publishing，1991.134－142.

［14］Omprakash Gnawali，Rodrigo Fonseca，Kyle Jamieson，et al.Collection Tree Protocol［C］//Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems(SenSys)，2009.

［15］Philip Levis，Nelson Lee，Matt Welsh，et al.TOSSIM:Accurate and Scalable Simulation of Entire TinyOS Applications.Proc.of the First ACM Conference on Embedded Networked Sensor Systems.New York，2003:126－137.