一种WSN中分簇路由算法的改进

摘要：在无线传感器网络中，基于分簇的路由协议对提高网络的寿命有着重要作用，LEACH是一种应用比较广泛的层次路由协议。本文提出一种新的基于最优分簇的无线传感器网络分簇路由（LEACH-O）算法，在簇的形成过程考虑到节点的集中程度和节点的剩余能量，从而减少传感器节点的能量消耗，优化资源利用率。仿真实表明，与传统的LEACH算法相比，该算法配传感器节点间数据传输提供了高效路由，从而延长网络的生命周期。

关键词：簇头 分簇 剩余能量 能量高效路由协议

中图分类号：TP393 文献标识码：A 文章编号：1007-9416（2013）12-0125-02

1 引言

目前，无线传感器网络（WSN）在军事、环境监测、医疗应用、防灾救灾以及工业等领域都有着广泛的应用[1]。然而，受技术水平的限制，传感器节点通常采用电池供电，节点电源所能提供的能量十分有限。能量效率已成为无线传感器网络领域研究的重要问题，因此，设计一种高效节能的无线传感器网路由协议具有十分重要的意义。

文献[1]中介绍了各种能量高效的分簇路由协议。LEACH[2][3][4]是WSN中最早提出的分簇路由，现有在分簇路由协议大都借鉴了它的思想，文献[5]考虑了簇问能耗不均衡的问题，将监测区域划分为两个簇域，分簇再分别在两个簇域的基础上进行；文献[6]算法在簇头选择过程中纳入节点剩余能量，文献[7]算法考虑到多跳通信比单跳通信更节能，利用非重叠簇区域均匀分布簇头；本文则在对LEACH协议的基础上，提出了一种基于最优分簇的能量高效的无线传感器网络路由协议机制，节约能量并均衡能耗，从而有效延长网络的生命周期。

2 LEACH算法及其不足

LEACH是MIT的HeinZelman等人为无线传感器网络设计的低功耗自适应聚类路由算法。其基本思想是将网络划分为不同的簇，引入随机选择簇头和轮换簇头达到能量消耗均衡。LEACH选取簇头采用了“轮”的方法，其运行分为两个阶段：簇建立阶段和稳定数据通信阶段。在簇建立阶段，传感器节点选择0和1之间的随机数，如果小于阈值T（n），则广播自己是簇头的消息。已当选过簇头的节点则把T（n）设置为0，这样该节点不会再次当选为簇头。在选举了簇头后，簇头就向网络中的所有节点广播这一消息，通过接收信号的强度，节点选择所要加入的簇并通知该簇头，簇头就产生一个TDMA 定时消息，并且连同本簇中使用的CDMA编码一起发送给该簇中所有节点。在稳定阶段，节点持续采集数据并向簇头传输数据，簇头将该簇节点传来的数据进行融合处理后发送到sink节点。经过一段时间后，整个网络再次进入下一轮的工作周期。

由于LEACH协议采用了动态簇头轮换和分簇思想，使网络能量消耗均匀分布给所有节点，从而有效地延长了网络寿命。但是也同样存在着一些问题：所有节点当选簇头为相同概率，没有考虑节点剩余能量的限制条件；随机选举出来簇头可能导致部分区域簇头太密集而部分区域簇头太少，存在簇头分布不均匀的问题；未考虑簇头轮换所带来的转换开销以及轮换周期值为经验值，不符合实际的应用；簇头与汇聚节点通信采用单跳通信，会导致距离汇聚节点较远的簇头较早死亡，从而引起网络拓扑变化影响网络寿命。

3 LEACH-O算法的描述

针对LEACH协议存在的问题，本文提出了基于最优分簇的路由协议LEACH-O，使得源节点和sink节点之间进行数据传输的能量高效利用。分簇是一个适于无线传感器网进行数据汇聚的方法，其中的簇头作为汇聚节点，将接收到的簇成员的数据进行数据汇聚。此外，基于高斯分布的节点部署完成了感知区域的有效覆盖。

3.1 网络模型建立

3.2 簇的形成

无线传感器网络中簇的形成依赖于节点接收邻居节点信息的持续时间和邻居节点的剩余能量（ER）。因此，分簇协议分为几轮，其中每一轮被触发，就为网络中的传感器节点找到一个最优簇头。假设传感器节点与它的邻居节点交换信息，组成邻居节点和剩余能量的列表，为减少干扰，还定义了两个节点不在相同的时隙传送数据。

簇的形成过程所持续的时间记为TCF。因为取决于多跳分层网络体系结构的WSN，跳距离和层次水平在分簇过程中起着重要作用。 簇的形成步骤过程包含以下四步：（1）第一阶段的操作涉及信息的收集，关于邻居节点广播信息。然后，各个节点从邻居节点收集应答消息，用于广播信标。（2）执行一个排序算法，以获得关于它的跳距离的邻居节点列表。邻居节点列表是以降序排列。（3）当其两跳邻居节点是不封闭的，回到步骤2，分析所有一跳的成员，并使任何一个两跳邻居节点是作为簇的候选人。（4）基于邻居节点的剩余能量执行排序算法。为高效的分簇，每一轮簇的形成过程按这四个步骤执行，给传感器节点和数据汇聚提供更好的通信方式。

3.3 最优簇头选择

假设簇内通信部分足够长，使得一个簇的所有的簇内成员节点有数据可以发送到各自的簇头，使所有簇头有数据可以发送到sink节点。数据发送到sink节点之前在簇头完成数据汇聚。

簇头的能量消耗是相当巨大的，所以传感器节点的剩余能量是选择簇头的主要评判标准。此外，当sink节点是远离源节点时，在一个相对较小的区域内形成一个簇进行数据汇聚可以节省大量的能量，因为相比直接将数据发送到sink点，传感器节点需要更少的能量来发送数据到簇头。

基于以上推导，通过考虑传感器节点的集中程度和进行最优簇头选举的剩余能量来确定一个权重。设无线传感器网络有N个节点{1，2，...，N}。被称为成为节点i的集中程度，即在第r轮能感知环境的节点的数量。

4 仿真结果

本文采用NS2来验证改进的算法，并与LEACH算法进行对比分析。在仿真模型中，选择100个相同的传感器节点，随机部署在100m×100m的环境中，仿真参数设置如（表1）所示。

本实验对LEACH-O和LEACH进行性能分析与比较，主要考虑参数为吞吐量、平均能量利用率。

（图2）充分体现了吞吐量随仿真时间的变化。从图形可以看出，与LEACH模型相比，可以明显看出本文提出的LEACH-O算法产生较高吞吐量，改进的算法提高了通信信道传递的消息速率。

（图3）给出来两种算法的平均能量利用率的比较情况。可以看出，LEACH-O算法比LEACH能耗更少。这是因为改进的算法使用了最佳分簇模型和最优簇头选择，在无线传感器网络中使用能量高效的分簇选择机制来提供最优能量消耗的方法，并提供高效的路由。这个过程表明，在该算法中，由簇头完成数据传输，使得平均能量利用率大大减少。

5 结语

本文提出了一种基于最优分簇的能量高效的路由协议（LEACH-O）。节点部署采用高斯分布模型，使用最优分簇和簇头选择机制使得节点的能量消耗可以大大减少，结合能量有效的路由来完成源节点与sink节点之间的通信，延长了网络寿命。

参考文献

[1]B.Baranidharan and B.Shanthi，“A Survey on Energy Efficient Protocols for Wireless Sensor Networks，” International Journal of Computer Applications，2010，Vol.11，Issue.10，pp.35-40.

[2]W.R.Heinzelman，A.Chandrakasan，H.Balakrishnan，“Energy-EfficientCommunication Protocol for Wireless Microsensor Networks，” Proceedings of the 33rd Hawaii International Conference on System Sciences， 2000.

[3]S.Ozdemir，Y.Xiao，“Secure data aggregation in wireless sensor networks： A comprehensive overview，” Computer Networks，vol.53，pp.2022-2037， August 2009.

[4]H.S.Lee， K.T.Kim，H.Y.Youn，“A New Cluster Head Selection Scheme for Long Lifetime of Wireless Sensor Networks，”ICCSA 2006，vol.3983，2006.

[5]郑文军.无线传感器网络分簇节能路由算法研究[D].武汉：华中科技大学，2008：38.40.

[6]张强，卢潇，崔晓臣.基于能量高效的无线传感器网络LEACH 协议改进[J].计算机工程与设计，2011，32（002）： 427-429.

[7]Ankit Thakkar and Dr K Kotecha，“CVLEACH：Coverage based energyefficient LEACH，”International Journal of Computer Science and Network，2012，Vol.1，Issue.3.