能量均衡的无线传感器网络蚁群优化路由协议
孙彦景，何妍君，刘卫东，魏雨辰，赵骏逸
(中国矿业大学 信电学院，江苏 徐州，221008)
摘要：提出一种能量均衡的无线传感器网络蚁群优化路由协议EAntWSN。该路由算法基于节点的剩余能量选择下一跳节点，并提出路径平均能量的思想进行信息素的更新，使用计算有效的蚁群智能路径搜寻方式，找到从源节点到汇聚节点的最优路径，完成网络的通信任务。仿真结果表明：优化的蚁群算法节约了网络中节点的能量消耗，延长了网络的生命周期。
关键词：无线传感器网络；蚁群优化；能量均衡；NS2仿真
中图分类号：TP393 文献标志码：A 文章编号：1672-7207(2011)S1-0888-07
Energy-balanced routing protocol based on ant colony optimization for wireless sensor network
SUN Yan-jing, HE Yan-jun, LIU Wei-dong, WEI Yu-cheng, ZHAO Jun-yi
(School of Information and Electrical Engineering,
China University of Mining and Technology, Xuzhou 221008, China)
Abstract: An Energy-balanced routing protocol based on ant colony optimization for wireless sensor network (EAntWSN) was proposed. Choosing next hop to send data packet was based on node residual energy and updating pheromone was depended on the idea of path average energy. Computationally effective ant colony intelligence was used in the routing to find the best path from source nodes to sink node and accomplish network communication task. Simulation results indicate that the optimal ant colony algorithm saves energy consumption of nodes and prolongs the network lifetime.
Key words: wireless sensor network; ant colony optimization; energy balancing; NS2 simulation
由于无线传感器网络中节点自身具有一定的局限性，如能量、计算能力有限，因此设计无线传感器网络路由协议要求低能耗、低成本和低复杂度[1-2]。蚁群算法是一种新型的模拟蚂蚁觅食行为的群体智能优化算法，依靠相互协作和信息素累积找到从蚁巢到食物源的最短路径，并且能很快克服环境障碍，适应新的环境，重新建立最优路径[3-4]。蚁群算法具有分布式并行计算、较强鲁棒性和易与其他方法结合的特点[5]，在组合优化方面显示出独特的优势，可用于解决包括旅行商问题、二次分配问题、网络路由问题等[6-7]复杂优化问题。
国内外学者对蚁群算法的研究已经渗透到众多领域，并取得了一些研究成果。Xie等[8]提出了一种利用路径延迟和节点能量来建立路由的蚁群优化算法，在选择下一跳节点时削弱了对信息素浓度的依赖，避免节点过早死亡。WANG等[9]提出的混合蚁群优化路由算法(HOPNET)模型主要由节点邻域内的本地主动路由发现和邻居之间的被动通信组成，将一个节点到中心节点的跳数作为本地邻域的半径，蚂蚁在寻路过程中可分为区域内路由发现与区域间路由发现。但是该算法没有考虑网络节点能耗问题，因此难以符合无线传感器网络路由协议对节能的性能要求。王结太等[10]作为一种智能、动态和可扩展性的多路径蚁群算法，通过对算法的改进和加入数据分片机制来优化选路效率，使无线传感器网络获得有效且可靠的通信，均衡全网能量，最大化网络生命周期。Leach-ant的WSN路由机制将LEACH协议与蚁群算法相结合，在簇的形成阶段采用LEACH协议对网络节点进行分簇，进入簇的稳定阶段后采用蚁群算法寻找从簇首到汇聚节点的最优路径[11]。此路由协议比较适合大规模的无线传感器网络环境，但是蚁群算法的搜索时间比较长，只适用于寻找最优路径，不能发送数据。MRP[12]是根据节点剩余能量进行动态分簇，再从均衡节点能量消耗的角度来建立从簇首到Sink节点的最优路径和次优路径，从而达到网络生命周期的最大化。
最具典型的ANTNET算法[13-14]是应用于无线传感器网络的基本蚁群算法，利用对信息素浓度的设置成功解决无线传感器网络路由问题，对网络变化有较高的适应能力，能快速建立优化路径，但是，对于能量的消耗问题没有很好地解决。本文作者在ANTNET基础上提出energy-balanced routing protocol based on ant colony optimization for wireless sensor network (EAntWSN)算法，在路径搜寻和建立的过程中，考虑节点的剩余能量和路径质量，引入信息素蒸发机制来控制算法的收敛速度，有效实现路由维护，从而均衡全局的能量消耗，延长网络的寿命。
1 ANTNET路由协议
ANTNET路由协议通过前向蚂蚁和后向蚂蚁来实现路由优化，并利用网络延时信息更新路径，最终找到从源节点到目的节点的最短路径，完成无线传感器网络的通信任务。采用了3种类型的数据包：传输数据包、蚂蚁数据包和邻居数据包。算法利用邻居数据包找到当前节点的所有邻居节点，而蚂蚁数据包可以找到从源节点到目的节点的最短路径。
但是ANTNET存在一些不足之处。它只是根据信息素浓度选择下一跳，在路由发现过程中没有考虑节点的当前能量状态，数据始终沿着最短路径发送，导致这条路径上的节点因能量消耗快而过早死亡，直接影响网络路由的健壮性，间接缩短网络的生命周期。另外，后向蚂蚁更新信息素时，只对源路径的信息素进行加强，使得算法过早陷入局部最优解。同时，算法没有提出如何对路由进行维护，当链路失效或者损坏时会导致通信失败。
2 EAntWSN路由协议
针对ANTNET存在的问题，本文作者提出的EAntWSN路由协议的数据包在返回途中释放信息素的量不但与到目的节点的跳数有关，而且还考虑了路径的平均能量。另外数据传输时，数据包不是单纯地沿着最短路径传播，还根据当前节点的剩余能量水平，使数据包选择能量更多的下一跳节点和健壮性更好的路径，达到均衡节点能耗的目的。而在进行路由维护的过程中，通过信息素的周期性蒸发有效调整了算法的收敛速度，进而加强蚁群的全局搜索能力，促进新路径的使用。
2.1 数据包分类
在EAntWSN算法中有4种类型的数据包，分别是Hello数据包、查询数据包、应答数据包和探测数据包，所有这些数据包都可以看成是控制数据包。
(1) Hello数据包。Hello数据包的任务是查找当前节点所有的邻居节点，收集它们的相关信息来建立路由表。每一节点向邻居节点广播包含各种参数值(如节点在网络中的坐标位置、能量信息)的Hello数据包，查看邻居节点是否存活。如果邻居节点死亡，则从路由表中删除该邻居节点的信息。
(2) 查询数据包、应答数据包与探测数据包。当节点需要与目的节点通信时，查询数据包(即前向蚂蚁)与应答数据包(即后向蚂蚁)共同建立并确定到目的节点的路由。而探测数据包(即探测蚂蚁)是用来发现目的节点的新的更优路径。
2.2 信息素表
每一个节点都维护一个信息素表，它记录每一个邻居链路的信息素浓度。表1所列为信息素表，τn,d表示邻居节点n到目的节点d的信息素浓度。信息素表开始为空，随着应答数据包在返回途中释放信息素而进行更新。另外，由于记忆空间的限制，节点可能需要限制信息素表的大小。如果信息素表达到满的状态，当增加新的记录时，表就会移除最小浓度的记录来存储新的浓度。
值得注意的是，如果目的节点d是节点n的邻居节点，那么，可以把τn,d的值看成是接近无穷大，节点n就会直接把数据发送到目的节点d。
表1 信息素表
Table 1 Pheromone table
2.3 算法思想
(1) 信息素更新策略每隔一定时间，源节点在网络中释放一定数量的前向蚂蚁，找到从源节点到目的节点的所有有效路径，建立信息素表。当前向蚂蚁达到目的节点，它就自动转换为后向蚂蚁，更新原路径上每一个节点信息素表中的信息素浓度。后向蚂蚁返回源节点之前，目的节点按照公式(1)计算该蚂蚁在返回途中应当释放的信息素踪迹量?τ：
(1)
式中：Nmax为查询数据包与探测数据包在网络中允许的最大跳数；Ncount表示数据包到目的节点的实际跳数，可以从相应的数据包字段中得出。Eavg是数据包即将选择转发的邻居节点到目的节点这条路径上的平均能量水平；c为变量参数，用来允许路由协议调节距离对信息素浓度的影响。后向蚂蚁在链路上释放的信息素浓度是基于到目的节点的距离大小，越靠近目的节点，信息素浓度就越高。
当一个节点收到从邻居节点n发送的后向蚂蚁信息时，自动局部更新信息素表中的信息素浓度，依据式(2)完成对信息素的加强过程：
(2)
其中：ρ为信息素挥发系数；1-ρ为信息素残留因子，ρ的取值范围是[0,1]；ω为控制系数。为了建立更好的信息素分布，即汇聚节点周围的节点有更高的信息素水平，而远端节点能找到更好的路径。当汇聚节点移动时这种策略非常重要，因为此时信息素更新的适应性较强而且迅速。
为了避免因残留信息过多而淹没启发信息，依照式(3)来实现信息素的蒸发，从而降低发送数据包的转移概率，以促进新路径的使用。
(3)
蒸发速率ρ1用来调整信息素浓度蒸发的速度，取值范围是[0,1]。但是，信息素浓度不能降到负值或者0，因此，设定1个参数值τn,d_default来保证在搜寻路径的过程中每一个邻居节点都可能成为下一跳。此外，当节点发现一个新的邻居节点n′时，新的信息素浓度τn′,d的默认值就是τn,d_default。
(2) 状态转移概率规则。为了实现不同节点的能量消耗相对平衡，本算法考虑相邻节点的能量情况来选择下一跳节点。
(4)
其中：E为可见度函数，用1/(Einitial-Es)表示；Einitial为节点的初始能量；Es为节点的实际能量水平。启发式因子α和β是控制信息素对可见度的相对重要性参数。Nm表示节点m的邻居节点，nodes_visitp是已经被数据包p访问过的节点集合。式(4)表示数据包不能向已经被访问过的节点进行传输，如果数据包访问了当前节点的所有邻居节点，数据包就会被节点释放掉，防止了数据包的重复发送和网络陷入死循环状态。
2.4 算法实现
EAntWSN协议主要分为2个过程，分别为路由发现过程和路由维护过程。
24.1 路由发现
在路由发现阶段，源节点定期在网络中释放一定数量(Qnum)的查询数据包选择任意邻居节点作为下一跳节点，建立起所有到目的节点的有效路径。如果超过了最大跳数(Nmax)的转发次数，查询数据包将会被丢弃。
目的节点收到查询数据包时，就会产生应答数据包，沿着反向路径返回到源节点，同时释放信息素，更新信息素表中的τn,d。若源节点收到应答数据包，则路由发现过程成功，数据包就可以从源节点沿着建立起来的路径进行正常的发送，数据总是发送到具有最大转移概率的邻居节点。若源节点没有在规定时间T_SET内接收到应答数据包，则路由发现失败，T_SET表示最大的一次数据发送的循环时间。源节点需要继续发送查询数据包直到可以成功接收到应答数据包。如果超过最大查询次数Qmax，路由发现过程也被认为是失败。
图1所示为路由发现过程。图1(a)所示为节点S与节点D分别为源节点与目的节点，这是网络的初始化情况。图1(b)所示为路由发现的过程，节点S发送查询数据包找到所有达到节点D的路径，而节点D产生应答数据包返回到节点S，沿途释放信息素，实现信息素的更新，完成路径的建立。中间节点从它的邻居节点接收到应答数据包，意味着它可以通过邻居节点向目的节点传输数据包。图1 (c)实线所示为从节点S到节点D有2条可选路径。由于路径P2上根据信息素浓度和节点剩余能量计算所得的转移概率较高，因此节点S将会沿着路径P2发送数据到节点D，如图1 (d)中点划线所示。
图1 路由发现过程
Fig.1 Process of route discovery
2.4.2 路由维护
节点沿着路由移动、节点死亡或者链路损坏，都可能造成路由通信失效，因此需要路由维护来保证网络中的节点可以有效进行通信。当数据正在进行传输时，网络中的每一个节点定期发送一定数量的探测数据包到目的节点，用以监测已经存在路径的质量，同时探测到目的节点的新路由。为了减低数据包开销，探测数据包的数量将会根据当前信息素的浓度受到限制。在中间节点，探测数据包是根据(1-γ)tmac的信息素浓度计算概率来进行转发，tmac是在MAC层成功传输一个数据包所用的平均时间。这一方法帮助蚂蚁可以找到最短距离的新路径。当目的节点接收到探测数据包时，它会产生应答数据包，并以反向路径返回到源节点，使源节点知道路由的变化情况，这一过程类似于路由发现过程。
另外，在最短路径上信息素不断加强，会导致该路径“过热”，加速路径上节点的死亡，并使得网络陷入局部最优。如果对信息素进行定期蒸发，可以减小该路径在随后通信中被选中的概率，促进新路径的 使用。
图2所示为路由维护过程的例子。假设节点A发生移动，如图2(a)所示。在路由维护过程中，节点S周期性地发送探测数据包发现有更优的路径，如图 2(b)所示。节点S可能用更优路径来代替路径P2，如图2(c)所示。图2(d)给出了由于更优路径上有更高转移概率，于是，节点S就沿着这条新路径发送数据。同时可以看出网络中存在着从源节点到目的节点的多 条路径，因此，这一方法增强了无线传感器网络的健 壮性。
3 仿真与结果分析
为了验证EAntWSN的有效性与正确性，利用NS-2仿真软件对算法进行仿真测试，具体软件仿真平台为虚拟机+Linux+ns-allinone-2.33。
图2 路径维护过程
Fig.2 Process of route maintainence
网络由Sink节点、中间节点和Source源节点构成，这3种节点都具有定位功能。Sink节点具有能量和计算能力不受限的特点，而各中间节点和源节点具有简单的计算及通信能力但能量水平受限的特点。本文作者对ANTNET和EAntWSN 2种算法进行仿真、比较和分析。网络规模分别为：200 m×200 m区域大小范围内布置100个节点，300 m×300 m区域范围内布置150个节点，400 m×400 m区域范围内布置200个节点，500 m×500 m区域范围内布置250个节点，600 m×600 m区域范围内分别布置300个节点，每个节点的无线传输距离是40 m。仿真环境参数如表2所列。
蚁群算法中各参数的作用是紧密耦合的，其中对算法性能起着最关键作用的应该是信息素启发式因子α、期望启发式因子β、信息素挥发因子ρ、信息素蒸发速率ρ1等参数。α，β，ρ和ρ1等参数的优化配置可以极大地提高算法的性能。根据文献[15]，α取1.0-2.0，β取4.0-6.0，ρ和ρ1取0.5-0.8时，蚁群算法均能获得较好的搜索结果，算法循环次数少(即收敛速度快)，不易陷入局部最优，具有较强的鲁棒性。表3列出了本文中提出的基于蚁群优化算法的路由协议EAntWSN设定的参数。
表2 实验仿真参数
Table 2 Parameter values for simulation
表3 EAntWSN仿真参数
Table 3 Parameter values for EAntWSN
仿真主要从网络节点的平均剩余能量(average residual energy)和端到端平均时延(end-to-end average delay) 2个方面来考查ANTNET算法与EAntWSN算法的性能。网络节点的平均剩余能量是指网络中所有节点的剩余能量总和与节点数的比值，衡量了路由方法优劣的基本标准。平均时延是指应用层上数据包从源节点发送到汇聚节点接收到数据包所需要的平均等待时间，它同时也反映了网络路由协议的时间准确性。
3.1 平均剩余能量
图3所示为不同网络规模下网络运行100 s，收到200个数据包时节点的平均剩余能量情况。
图3 ANTNET与EAntWSN的平均剩余能量比较
Fig.3 Average residual energy of ANTNET and EAntWSN
EAntWSN算法节点的平均剩余能量明显比ANTNET算法的高。这是由于在EAntWSN路由协议中考虑了能量因素，数据包选择下一跳节点时，依照与距离与能量的权值相关的概率值大小进行数据包的转发，即选择剩余能量较多和路径平均能量较大的下一跳节点，使节点能耗均衡化，从而避免了单一节点因能耗过大而过早死亡，延长了网络的生命周期。而ANTNET路由协议中当路径建立起来之后，数据就通过最短路径发送到汇聚节点，快速地消耗了节点能量。
图4与图5所示为网络规模分别为100个节点和200个节点情况下，随着汇聚节点接收到数据包数量的增加，ANTNET与EAntWSN中节点平均剩余能量的对比。两图比较之后可以看出：当网络规模扩大时，随着汇聚节点接收数据包数量的逐渐增加，EAntWSN性能越发明显优于ANTNET，从而表明EAntWSN算法增强了网络的健壮性，可以适用于较大规模的网络。
3.2 端到端平均时延
图6所示为出在一定区域范围内，网络节点数目分别为100，150，200，250和300时，ANTNET算法的网络平均延时比EAntWSN算法短。这是因为ANTNET采用的是最短路径算法，蚂蚁具有简单的记忆功能，在寻找路径时可以快速地找到最短路径，因此，时延也是最小的。然而，无线传感器网络路由设计主要考虑的是能耗问题，EAntWSN路由算法考虑了最短路径和路径的当前平均剩余能量因素的折中，以牺牲一定网络可以承受的延时代价来换取较小的能量损耗。
图4 100个节点的ANTNET与EAntWSN平均剩余能量比较
Fig.4 Average residual energy of ANTNET and EAntWSN about 100 nodes
图5 200个节点的ANTNET与EAntWSN平均剩余能量比较
Fig.5 Average residual energy of ANTNET and EAntWSN about 200 nodes
图6 ANTNET与EAntWSN的延时比较
Fig.6 End-to-end average delay of ANTNET and EAntWSN
4 结论
(1) 在ANTNET的基础上，提出了对路由维护及优化网络能量的EAntWSN路由协议。这是一种支持多路径的平面路由协议，在路径选择时充分考虑低能量的节点状态来建立较优的路径，使网络的整体性能得到优化，平衡了网络节点的能耗。
(2) 路由维护过程通过发现新路径来修复失效的链路，重新建立网络的通信，提高了网络的鲁棒性与健壮性。
(3) 所提出的具有能量均衡的蚁群优化路由协议EAntWSN可以较好地解决无线传感器网络的路由问题，完成网络的通信任务，同时降低网络的能量消耗，提高网络的可靠性和通信效率，延长网络的生命周期。
参考文献：
[1] Akkaya K, Younis M. A survey on routing protocols for wireless sensor networks[J]. Ad Hoc Networks, 2005, 3(3): 325-349.
[2] Frey H, Rührup S, Stojmenovi? I. Routing in wireless sensor networks[C]//Misra S, Woungang I, Misra S C. Guide to Wireless Sensor Networks. London: Springer, 2009: 81-82.
[3] Di Caro G A. Ant colony optimization and its application to adaptive routing in telecommunication networks[D]. Belgium, Brussels: Applied Sciences. University Libre de Bruxelles, 2004: 23-35.
[4] Saleem M, Di Caro G A, Farooq M. Swarm intelligence based routing protocol for wireless sensor networks: Survey and future directions[J]. Information Sciences, 2010, 7: 1-28.
[5] Di Caro G A, Ducatelle F, Gambardella M L. Theory and practice of ant colony optimization for routing in dynamic telecommunications networks[C]//Sala N, Orsucci F. Reflecting Interfaces: The Complex Coevolution of Information Technology Ecosystems. New York: Information Science Reference, 2008: 11-32.
[6] 段海滨. 蚁群算法原理及应用[M]. 北京: 科学出版社, 2004: 212-332.
DUAN Hai-bin. Ant colony algorithms: Theory and applications [M]. Beijing: Science Press, 2004: 212-332.
[7] Saleem K, Fisal N, Hafizah S, et al. Ant based self-organized routing protocol for wireless sensor networks[J]. International Journal of Communication Networks and Information Security, 2009, 1(2): 42-46.
[8] XIE Hui, ZHANG Zhi-gang, ZHOU Xue-guang. A novel routing protocol in wireless sensor networks based on ant colony optimization[C]//International Conference on Environmental Science and Information Application Technology. Wuhan, China: IEEE, 2009: 646-649.
[9] WANG Jian-ping, Osagie E, Thulasiraman P, et al. HOPNET: A hybrid ant colony optimization routing algorithm for mobile ad hoc network[J]. Ad Hoc Networks, 2009, 7: 690-705.
[10] 王结太, 许家栋, 徐建城. 基于蚁群优化算法的无线传感器网络路由协议[J]. 系统仿真学报, 2008, 20(18): 4898-4901.
WANG Jie-tai, XU Jia-dong, XU Jian-cheng. Wireless sensor networks routing protocol based on ant colony optimized algorithm[J]. Journal of System Simulation, 2008, 20(18): 4898-4901.
[11] 航海存, 郭爱煌, 舒文杰. 基于LEACH与蚁群算法的WSN路由机制及性能分析[J]. 传感器技术学报, 2008, 21(10): 6370-6373.
HANG Hai-cun, GUO Ai-huang, SHU Wen-jie. Performance analysis of WSN routing scheme based on LEACH and ant algorithm[J]. Chinese Journal of Sensors and Actuators, 2008, 21(10): 6370-6373.
[12] YANG Jing, ZHAO Wei, XU Mai, et al. A multipath routing protocol based on clustering and ant colony optimization for wireless sensor networks[J]. Sensors, 2010, 10(5): 4521-4540.
[13] Chowdhury A R, Waterman J. ACO routing in wireless sensor networks[R]. Boston: Harvard University, 2008.
[14] ZHANG Lin, LI Xiao-ping. The research and improvement of antnet algorithm[C]//Proceedings of the 2nd International Asia Conference on Informatics in Control, Automation and Robotics. Piscataway, NJ, USA : IEEE, 2010: 505-508.
[15] 徐红梅, 陈义保, 刘加光, 等. 蚁群算法中参数设置的研究[J]. 山东理工大学学报(自然科学版), 2008, 22(1): 7-11.
XU Hong-mei, CHEN Yi-bao, LIU Jia-guang, et al. The research on the parameters of the ant colony algorithm[J]. Journal of Shandong University of Technology (Natural Science Edition), 2008, 22(1): 7-11.
(编辑 李向群)
收稿日期：2011-04-15；修回日期：2011-06-15
基金项目：国家自然科学基金资助项目(50904070)；中国博士后基金资助项目(20100471412)；中央高校基本科研业务费专项资金资助项目(2010QNA48)；江苏省青蓝工程资助项目；国家大学生创新性实验计划资助项目(101029011)
通信作者：孙彦景(1977-)，男，山东滕州人，博士，副教授，从事无线传感器网络研究；电话：0516-83884819；E-mail：yanjingsun_cn@163.com
