武 睿，夏克文，李国栋，胡钊政

（河北工业大学 信息工程学院，天津，300401）

0 引言

无线传感器网络（WSN,WirelessSensor Network）是当今信息科学中一个新的研究热点和发展方向，具有极其广泛的应用前景.它主要由分布在一个监测区域内的一系列无线传感器，通过自组织和多跳方式组成一个无线通信网络，协作感知、采集和处理网络区域内的有关信息，并发送给用户.传统的WSN的路由协议由于很少考虑传感器节点的能量有限问题[1,2]，致使在网络优化中很难选择出最优路径.我们知道，设计WSN路由协议的重要指标就是要使整个网络的生存周期得到充分延长[3]，即选取的传输路径能量要小,且整个网络的能量是均衡的.鉴于蚁群算法很适宜于求解多维组合优化问题，且具有较强的鲁棒性、全局性、普遍性、优良的分布式并行计算机制.为此，我们采用蚁群算法来研究WSN的路由设计.

1 WSN的体系结构与LEACH协议

1.1 WSN的体系结构

一个典型传感器网络包括监视区域内的传感器节点 (Nodes)、汇聚节点 (SINK)、基本网络 (Internetamp;Satellite)以及WSN任务管理节点[3]，如图1所示.

1.2 LEACH路由协议

低功耗自适应集簇分层型协议（LEACH，Low Energy AdaptiveClustering Hierarchy）[4,5]是第一个关于WSN的层次式路由协议，之后发展起来的层次式路由协议基本都是基于LEACH而改进的.LEACH路由算法思想主要以循环方式随机选择簇头节点，再将网络能量负载均分到各个传感器节点上，因而使得网络能耗降低、网络生存周期得到延长[6].

LEACH路由协议可分为簇的建立（Setup phase）和稳定运行（Ready phase）两个阶段，两阶段的时间总和记为一轮（Round），簇的建立包括簇头节点的选择、簇头节点的广播、簇头节点的建立和调度机制的生成等环节，而稳定阶段持续一段时间后，网络又重新进入簇的建立，进行下一轮的簇重构.

在簇的建立阶段，传感器节点随机生成一个0、1之间的随机数，并且与阈值 做比较，如果小于该阈值，则该节点就会当选为簇头[6]. 按照下列公式计算

图1 典型的无线传感器网络Fig.1 Typicalw irelesssensor network

其中： 为一轮的簇头节点数； 为当前轮数； 为节点总数； 为最近 /轮中没有当选簇头的节点集合.选定簇头节点后，广播告知整个网络，其他节点根据接收信息的信号强度决定从属的簇，完成簇的建立后，节点通过时分多址（TDMA）和单跳方式将信息传给簇头，然后簇头将融合后的信息传至SINK.

实践表明，该LEACH比与以前的路由协议具有较长的网络生命周期.但是它也存在一些不足，需要改进之处主要表现在：

1）簇的建立完全随机，由于它与SINK节点的控制信息无关，且没有各节点之间的协调处理，因此每轮中难以实现簇的优化建立.

2）在单跳方式下由于与SINK节点进行通信的节点数较多，致使能量消耗加大.

3）簇头的选举也是完全随机的，应该考虑其节点的能量受限情形.

为此，我们采用蚁群算法来解决这些问题，因为蚁群算法作为一种用来寻找优化路径技术[7]，其所拥有的鲁棒性、可扩展性和本质的并行性正适合于网络路由的设计.

2 基于蚁群算法的WSN路由算法及实现

2.1 基于蚁群算法的WSN路由算法步骤

1）选举簇头

簇头选举经历以下几步：

Step1：SINK广播一个起始成簇信息，包括这一轮的网络平均能量 .

Step2：各节点接收SINK的成簇信息后，计算自身能量，若大于 ，说明自己可以竞选簇头，否则自己为普通节点.

Step3：SINK根据可参选簇头的节点信息作簇分割.

2）成簇

各节点有可能接收到多个簇头发来的信息，节点依据各信号强度，将最强信号的节点作为簇头，并请求加入其簇.本文中蚁群算法完成簇首到汇聚节点的路由。

3）簇间通信

Step1：参数初始化，设置总的迭代次数以及每个簇首节点所派蚂蚁的个数m：每个簇头节点分别派m只蚂蚁寻找到SINK节点的路径，从中选择最短的路径并增加该路径上的信息素；继续迭代找到簇首到SINK节点的最短路径。

Step2：人工蚂蚁找到最优路径后，进行数据传输。在簇间通信阶段，各簇首可以根据本身与下一跳的距离动态的调节发射功率，在不影响数据传输的前提下达到节约系统能量的目的。

Step3：进行簇间路由，通过选择下一跳簇首完成簇间路由，将数据发送给汇聚节点。

形成或更新的簇头 与簇头 间的信息素浓度计算公式为

式中： 为示信息素挥发量； 为 节点剩余能量； 为两簇头间的距离； 和 分别表示节点能量和节点间距离在信息素中所占的比重。

2.2 仿真实验场景

为检测WSN传感器节点规模对路由性能的影响，在仿真实验中设置100个节点随机分布在100m×100m的区域内，并设一个基站和一个SINK，其中SINK在区域中心，图2为传感器节点分布图.各节点初始能量设置为0.5 J，每一轮中选取簇头节点为10个，若网络中传感器节点过少时，网络则不能继续运行.蚁群算法参数选择为： 取值0.5， 取值为3，信息素挥发量 =0.7.

图2 传感器节点分布图Fig.2 Distribution on sensor nodes

2.3 仿真分析

采用节点的能量消耗和节点存活数等指标可以评价WSN的性能.

图3为LEACH与蚁群算法的能量消耗对比图，从图中我们可以看到，蚁群算法的能量消耗较LEACH有所减小.这表明基于蚁群算法的WSN路由算法使网络的生命周期得到延长，且使能耗均匀分布到每个节点.这是因为采用基于蚁群算法的WSN路由算法使所有簇头均匀分布，这样网络负载也得到均衡.

图4为无线传感器网络死亡节点数目随时间的变化情况.从图4中可以看到基于蚁群算法的WSN路由算法出现死亡节点的时间晚于LEACH算法，而且所有节点死亡的时间也明显晚于LEACH，表明蚁群算法使无线传感器网络的生命周期得到延长.这是因为选取能量大的节点为簇头使得能量低的节点可以延长其生命周期；另外，采用蚁群算法优化簇间路由时，其信息素浓度的计算中加入了簇头能量，这样能够保证以一定概率选出较大能量节点，从而延长了网络的生命周期.

图3 LEACH与蚁群算法的能量消耗对比Fig.3 Comparison on theenergy consumption between LEACH and ACO algorithm

图4 LEACH和蚁群算法的死亡节点数对比Fig.4 Comparison on the death numberof nodes between LEACH and ACO algorithm

3 结论

针对传感器节点在能量受限情况下，现有LEACH协议存在簇头分配不均匀和能量消耗较大等问题，本文采用蚁群算法进行WSN路由的优化设计.基于蚁群算法的路由改进算法可以解决LEACH算法存在的问题，仿真实验也表明了在网络的能量消耗、网络生命周期等方面要优于LEACH算法.

[1]Akyildiz IF，SuW，Sankarasubramaniam Y.A Survey on Sensor Networks[J].IEEECommunicationsMagazine，2002，8（7）：102-114.

[2]RentalaP，MusunuriR，Gandham S，SaxenaU.Surveyon Sensornetworks[R].TechnicalReport，UTDCS-33-02，University of TexasatDallas，2002.

[3]Md Nafees Rahman,M A Matin.Efficient A lgorithm for Prolonging Network Lifetime of Wireless Sensor Networks[J].TsingHua Science and Technology,2011，16（6）：561-568.

[4]于海斌，曾鹏，梁韡.智能无线传感器网络系统 [M].北京：科学出版社，2006.

[5]Lindsey S，Raghavendra C S.Power efficientgathering in sensor information systems[C]//Proceedings of IEEE Aerospace Conference，2002：1125-1130.

[6]赵喜清，秦奋涛，范青.无线传感器网络节能的高效路由算法 [J].微计算机信息，2007，23（19）：188-189.

[7]王镇，刘学军.WSN中基于蚁群算法的Qos路由协议 [J].传感技术学报，2011，24（11）：1625-1630.

[8]汪祥莉.无线传感器网络中高能效路由技术的研究 [D].武汉：武汉理工大学，2011.