沈海燕，廖惜春，刘玉锟



基于梯度与数据流机制的WSN分簇路由协议

沈海燕，廖惜春，刘玉锟

（五邑大学 信息工程学院，广东 江门 529020）

针对无线传感器网络的能量受限和网络寿命有限的问题，结合梯度和数据流机制，对经典的LEACH分簇路由协议中簇头的选举及簇内通信方式进行了改进. Matlab的仿真结果表明，改进后的基于梯度与数据流机制的分簇路由协议与LEACH协议相比，能更为有效地节约节点能量，使网络寿命延长约50%～65%.

无线传感器网络；分簇路由；LEACH协议；梯度；数据流机制

无线传感器网络（wireless sensor network，WSN）是由大量部署在监测区域内的传感器节点组成的，部署的节点通过采集网络覆盖区域内对象的信息，采用多跳的无线通信方式，将节点收集、处理后的信息提供给目标用户. 路由协议是在路由指导IP数据包发送过程中事先约定好的规定和标准，WSN的路由协议在网络数据的传输过程中起着举足轻重的作用. 由于WSN中的能耗问题影响到整个网络的寿命，因此，低功耗高性能的路由协议一直是研究的热点[1-4]. 目前，针对WSN中的路由机制，国内外的学者己经作了大量的分析和研究，对节点分簇是无线传感器网络中节约能源的一种有效方案，其中LEACH（low-energy adaptive clustering hierarchy）[5]3006是最早的WSN分簇路由协议. 本文研究并改进LEACH协议，针对传感器网络节点能量异构的情况设计更适合于传感器网络特点的分簇路由协议——基于梯度与数据流机制的分簇路由协议.

1 LEACH算法

1.1 LEACH算法的描述

LEACH的基本思想是通过等概率的随机循环选择簇头，使得整个网络的能耗尽可能地平均分配到每个传感器节点，从而达到降低网络能量耗费、延长网络生命周期的目的[5]3005.

LEACH在运行过程中不断地周期性循环执行簇的重构. 算法操作使用“轮”的概念. 每一轮由初始化和稳定的工作两个阶段组成. 初始化阶段，每个节点产生介于0与1之间的一个随机数，若节点产生的这个随机数小于阈值()，则该节点向周围节点广播它成为簇头节点的消息.()的计算公式为：

其中，是簇头占所有节点的百分比，即节点当选簇头的概率；是目前循环已进行的轮数；是最近1/轮中还未当选过簇头的剩余节点的集合. 从式（1）可以看出，当选过簇头的节点在接下来的1/轮循环中将不能成为簇头，剩余节点当选簇头的阈值()增大，节点产生小于()的随机数的概率随之增大，所以节点当选簇头的概率增大[5]3012,[6].

非簇头节点根据接收到各个簇头节点的信号强弱来选择加入到哪个簇，并发出信息通知相应的簇头节点. 当网络进入稳定阶段后，簇内的节点通过TDMA方式与簇头节点进行通信[7]，簇头接收簇内其他节点发送的数据，将这些数据进行融合后发送给汇聚节点，在汇聚节点再次进行数据融合后发送给基站. 其中，数据融合技术是指对有用信息的采集、传输及在一定准则下加以自动分析、综合，以辅助人们进行态势和环境判定、分析的一种信息处理方法. 信息源经由路由协议传输到簇头节点和汇聚节点，在簇头节点及汇聚节点再进行数据融合，这样既定义了信息的传输标准，又简化了需要传输的数据量.

1.2 LEACH算法的不足

LEACH算法是基于这样的假设的：所有传感器节点都可以直接和汇聚节点通信. 但是在实际的应用中，当网络的规模较大时，每个传感器节点都可以直接与汇聚节点通信的概率很小. 由于LEACH算法采用产生随机数与()比较来产生簇头，这样有可能出现簇头非均匀分布[7-8]，如图1所示. 其中，“☆”代表普通节点，“○”代表簇头节点. 可见，LEACH算法不能保证簇头在网络中的均匀性分布. 当簇头节点分布不够均匀时，簇内通信就不能满足自由空间(free space)模型，这将导致较大的能耗.

图1 LEACH簇头分布示意图

2 基于梯度与数据流机制的分簇路由协议

针对LEACH协议存在的问题，本课题研究的目的是让簇头节点尽可能均匀分布，并使每个簇的大小相近，使簇头与汇聚节点的通信距离趋于平衡，进而减少通信开销. 梯度路由与数据流机制结合的分簇路由算法将能有效地解决此问题. 该算法的主要思路是：在簇头的产生和簇内数据传输方面分别运用梯度路由机制和数据流机制作了改进，其余部分与LEACH协议基本一致. 基于梯度的路由机制[9]的原理是在能量模型基础上建立路由梯度，沿梯度变化最快的方向传输数据，减小通信开销. 数据流机制的基本思路是当某节点有数据流通过时，新的数据不再通过该节点，以减少网络延迟和节点能量消耗的不平衡，延长网络寿命[10-13].

本文对LEACH的改进和设计的步骤如下：

Step1：建立梯度和邻居表（梯度机制）

2）当节点收到节点广播梯度的消息时，则节点检查自身的邻居表中是否已经有了节点的信息，若没有，则将节点加入到节点的邻居表，邻居表也同时保存邻居节点的梯度信息. 若已经有了节点的信息，则更新节点的梯度.

4）当节点自身梯度发生改变后，向邻居节点广播自身梯度.

Step2：簇头选举

Step3：簇的形成

Step4：簇内通信（数据流机制）

每个簇头节点产生一个TDMA时隙表，簇成员只在自己的时隙内发送数据，其余时间进入休眠状态以节约能源. 簇头节点整合簇内数据后，从它的邻居表中选择梯度值小于簇头节点的梯度，并从当前处于空闲状态（数据流机制）的节点中选择剩余能量最大的节点作为转发节点. 可见，节点梯度越大，数据经过它传送的几率就越小. 当中间节点的梯度为1时，则直接传递给汇聚节点，完成数据的传输.

3 仿真试验与结果分析

图2 仿真区域节点分布（其中，上边缘的*节点为sink节点，其余节点为普通节点）

图3 LEACH与本文改进算法的存活节点数与簇头数目的对比图

图3结果表明：在第176轮的时候，LEACH协议中出现第一个死亡节点，在1 378轮的时候，LEACH协议中所有节点死亡；而改进后的协议中，出现第一个节点死亡是在211轮，直到2 286轮节点才全部死亡. 由于每次实验节点散布的随机性，经过多次仿真结果表明，LEACH算法基本都是在160轮左右出现第一个节点死亡，在第1 300轮左右现有节点全部死亡；采用本文改进的协议时，第一个节点死亡出现的时间是在220轮左右，全部节点死亡的时间大约出现在第2300轮. 因此，对于正方形检测区域，本文基于梯度与数据流机制的分簇路由协议，与原LEACH协议比较，网络寿命延长了约66%. 当汇聚节点位于检测区域内的其他位置时，仿真实验也表明本协议与原LEACH协议相比网络寿命能延长寿命60%以上. 另外对不同形状侦测区域的仿真结果表明，WSN的拓扑结构变化对本协议的有效性影响很小，并且网络寿命延长均可达到50 %以上. 可见，改进后的协议明显节约能耗，这对于能量有限的WSN来说，是十分重要的.

4 结束语

[1]AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. A survey on sensor networks [J]. IEEE Communications Magazine, 2002, 40(8): 102-114.

[2] 孙利民，李建中，陈渝. 无线传感器网络[M]. 北京：清华大学出版社，2005.

[3] 任丰原，黄海宁，林闯. 无线传感器网络[J]. 软件学报，2003, 14(7): 1282−1291.

[4] 付华，赵刚. 无线传感器网络中一种能量均衡的分簇策略[J]. 计算机应用研究，2009, 26(4): 1494-1496.

[5] HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks [C]// Proc of the 33rd Annual Hawaii International Conf on SystemYounis Sciences. Maui: IEEE Computer Society, 2000: 3005-3014.

[6] 王素娟. 无线传感器网络分簇算法的研究[D]. 太原：太原理工大学，2008.

[7] 龚海刚，刘明，余昌远，等. 无线传感器网络环境下基于事件驱动应用的节能TDMA协议[J]. 电子学报，2007(10): 1843-1848.

[8] 张伟华，李腊元. 无线传感器网络LEACH 协议能耗均衡改进[J]. 传感技术学报，2008, 21(11). 1918-1922.

[9] 张文祥，马银花. 基于梯度和剩余能量的WSN路由算法研究[J]. 传感技术学报，2009, 22(8): 1182-1185.

[10] 徐建波，李仁发. 无线传感器网络中一种新型的混合型数据收集协议[J]. 计算机研究与发展，2008, 45(2): 254-260.

[11] 王声荣. 无线传感器网络LEACH协议的研究与改进[D]. 济南：山东大学信息科学与工程学院，2008.

[12] 顾相平，孙彦景，钱建生. 一种改进的无线传感器网络LEACH-ED算法[J]. 传感技术学报，2008, 21(10): 1770-1774.

[13] 沈波，张世永，钟亦平. 无线传感器网络分簇路由协议[J]. 软件学报，2006, 17(7): 1588-1600.

[14]HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. An Application Specific Protocol Architecture for Wireless Microsensor Networks [J]. IEEE Trans on Wireless Communications, 2002, 1(4): 660-670.

[15] 刘明，龚海刚，毛莺池，等. 高效节能的传感器网络数据收集和聚合协议[J]. 软件学报，2005, 16(12): 2106-2116.

[责任编辑：韦 韬]

WSN Cluster Routing Protocol Based on Grads and Data Flow Mechanism

SHENHai-yan, LIAOXi-chun, LIUYu-kun

(School of Information Engineering, Wuyi University, Jiangmen 529020, China)

In consideration of the limited energy and limited life in wireless sensor network, the election of cluster heads and the communication way within the cluster in the classic LEACH routing protocol are improved based on the grads and data flow mechanism. The Matlab simulation results show that，compared with LEACH，the improved protocol—Cluster Routing Protocol based on grads and data flow mechanism can be more effectively in saving the energy of the nodes，the network life could be prolonged about 50%～65%.

WSN; cluster-based routing; LEACH protocol; grades; data flow mechanism

1006-7302（2013）01-0064-05

TP393

A

2012-11-02

广东省科技计划资助项目（2009B010800012）

沈海燕（1987—），女，河南郑州人，在读硕士生，研究方向为无线传感器网络路由及定位算法；廖惜春，教授，硕士生导师，研究方向为无线传感器网络及应用、物联网技术及应用.