一种无线传感器网络分簇路由算法

摘要：该文从经典低能量自适应分簇算法的基础出发，探讨了基于蚁群算法的无线传感器网络分簇路由算法。将蚁群算法，应用到簇间路由中，找出簇头到基站的最佳路径，实现离基站较远的簇头节点，能够以最佳路径进行信息传输，达到减少簇头结点的能量开销的目的。仿真结果表明，该算法在延长网络生存期方面相比LEACH算法提高约30%。

关键词：无线传感器网络；蚁群算法；分簇路由

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2013）35-7941-03

1 概述

无线传感器网络能够实时监测和采集网络信息，这些信息是分布区域内的各种监测对象的信息，将这些信息，发送到网关节点。而无线传感器网络路由算法作为一项关键技术已成为目前研究热点，因此也成为本文的研究重点。

蚁群算法在通信网络中，主要目的是建立路由。在蚁群算法应用到无线传感器网络路由，许多新算法由此产生。文章[1]通过节点能量和传输距离，以此作为切入点，引入到蚁群算法的信息素增量公式。使蚁群算法更好适应无线传感器网络路由协议，同时，考虑到有限的存储特性的传感器网络节点，该节点将蚂蚁携带信息融合。但是EEABR没有考虑全网能量均衡使用的问题，对于传感器网络来讲，其具有举足轻重的地位。文献[2]提出了一种蚁群算法（对斯坦纳树）。该算法可以被移植到无线传感器网络的路由。没在一个相应的变化对特定需求的基础上，并没有考虑能耗问题的无线传感器网络性能是至关重要的。该文基于蚁群算法的特点，无线传感器网络（WSN），蚁群算法的无线传感器网络，提出了一种新的可用于无线传感器网络聚类路由算法。

2 无线传感器网络蚁群分簇路由算法

将ACA与无线传感器网络分簇路由相结合组成新的算法，该算法是周期性的，每一轮分成阶段的簇和簇间的路由阶段。在簇的形成阶段，根据公式1确定簇头。在稳定阶段的簇，簇头来收集数据和信息同时，出发点是簇首节点、基站作为终点，运行蚁群算法，找到最好的路线从簇头到基站，通过有效的节点的帮助，更好的实现跳性能。

3 算法的实现过程

3.1 簇形成阶段

在簇首节点的选择部分，首先根据结点仿真面积，和最优簇头数，确定两簇头之间的最小距离，然后再由网络中，簇首节点总数，每个节点已成为簇首的次数和结点能量，由此来决定簇头。具体方案：每一个传感器节点，随机的产生0～1一个值，当其小于阈值T（n），则节点就为簇首。阈值T（n）为：

其中：p为期望的簇头节点的百分比，r是当前轮数，G是在最后的1/p轮中，没有成为簇头节点集合，Ecurrent是节点当前能量，Emax是节点初始能量，该文中p=0.05。

3.2 簇间路由阶段

因为簇头结点在网络中保存一个邻居簇头节点信息表，簇头的邻居信息表记录其相邻的簇首节点的信息，和相邻节点之间的距离。具有竞争簇头资格的节点，其表明具有竞争簇头资格时，这些具有资格的节点，就会查看本节点的路由表，看是否有它的相邻竞争簇头节点的记录，若无则创建新的记录，以及相邻竞争簇头的剩余能量、与基站的距离、两相邻簇头之间的距离和链路上信息素的浓度。如有，则对相邻节点的记录进行更新。但是这信息，想杜宇标记为非簇头的节点来讲是屏蔽性质的。

式中energy是相邻簇头结点的剩余能量，ι表示簇头结点与基站的距离，α1表示邻居节点能量在信息素中所占的比重，α2是邻居节点与基站距离的比重值（总信息素是全体）。从上公式看出，信息素浓度保留了数据传送过程中积累的信息素，并又将考虑了各相邻簇头节点到基站的距离。整个数据传送，路径的选择需要考虑历史经验，又使得数据传输沿着基站方向传输。

簇头结点数据在第一跳距离后被发送到簇首，簇头负责数据融合以减少冗余数据，从而减少业务量。当一个簇首发送数据，根据路由表和相邻的簇头的信息素浓度，计算每个相邻的概率选择簇首。公式3表示簇的概率前往相邻的簇头：

4 仿真实验与结果分析

4.1 能量模型与性能参数

节点间通信能耗采用LEACH算法中的能耗模型。仿真工具采用MATLAB，仿真环境为：在200m×200m的正方形区域内，随机撒200个节点，基站位于（50，175），如图2所示。传输和接收电路工作时能耗定义为Eelec=50nJ/bit，传输放大的单元能为εfs=10 pJ/bit/m2，εmp=0.0013 pJ/bit/m2，数据融合的单元能耗定义为EDA=0.5 nJ/bit；且无线发射模块，可以根据节点间距离远近，来控制功率大小，4.2 仿真结果分析

验证该算法，将该算法和LEACH进行了仿真对比。网络生命周期的长短，能够直接反映无线传感器网络性能的优劣，所以我们对本算法和LEACH算法在平均能量消耗和节点存活数两方面进行比较分析。图3是本算法和LEACH算法的平均能量消耗图，反映了两种不同的算法下，网络的平均能量消耗与时间的关系。横坐标表示轮数，纵坐标表示结点平均能量消耗。为了方便，我们用ACALEACH表示本算法。200个节点的总能量为100J，LEACH在450轮，出现节点死亡，耗能60J，而本算法消耗的能量是12J，在这一阶段降低了48J；当LEACH节点全部死亡时，本算法的能耗为80J，相比之下降低20J，网络性能得到了很大的提升。

5 结论

蚁群算法的自组织、动态和多路径的特性，促使其适合应用于无线传感器网络的路由的广阔前景性。该文在研究LEACH算法的基础上提出一种无线传感器网络蚁群分簇路由算法。该算法具有路由代价低、自适应性好、支持多路径等特点。经过仿真分析，显示该算法与LEACH算法相比，在网络平均能量消耗方面，有很大的优势，对网络生存周期有很大的改善。

参考文献：

[1] Camilo T，Carreto C，Silva J S，Boavida F.An Energy-Efficient Ant-Based Routing Algorithm for Wireless Sensor Networks[C].//ANTS2006，Int.Workshop on Ant Colony Optimization and Swarm Intelligence. Brussels，Bélgica：Springer Verlag，2006：49-59.

[2] Singh G， Das S， Gosavi S V， Pujar S. Ant Colony Algorithms forSteiner Trees：an Application to Routing in Sensor Networks[C].//LN de Castro，F J von Zuben eds.Recent Developments in Biologically Inspired Computing，2003：183-206.

[3] 王结太，许家栋，徐建城.基于蚁群优化算法的无线传感器网络路由协议[J].系统仿真学报，2008，20（18）：4898-4901.