基于分层结构的WSN路由算法改进*

刘 静，荆瑞俊

(山西农业大学软件学院，山西 晋中 030801)

基于分层结构的WSN路由算法改进*

刘 静，荆瑞俊

(山西农业大学软件学院，山西 晋中 030801)

为了延长无线传感网络(Wireless Sensor Network)的生命周期，提出一种基于分层结构的WSN路由算法改进。在著名的LEACH算法基础上,提出其中关于簇头选择所存在的问题，将原算法中的簇头节点占比p变为一个随节点与基站距离变化的动态比率(通过two-ray模型计算得出)，并通过参考节点剩余能量与原始能量比值优化了簇头选择的阈值；接着修改了路由算法的单跳为多跳，并且以基于虚拟栅格的路由算法得以实现，从而使得整个改进算法得以在更大的网络里应用。

WSN路由算法；分层结构；LEACH；多跳；虚拟栅格

在当今社会中，由于越来越多的现象需要人们去检测, 使得无线传感网络(Wireless Sensor Network)得到了空前的发展。到现在，WSN已被人们广泛应用于环境监测，健康检查，工业控制，干扰探测，以及地震监测等众多领域[1]。

一个标准的WSN网络通常由许多传感器节点组成，这些节点一般都是依靠电池提供能量，但是经过一段时间的使用之后，电池的更换一般都很难实现，除了电能资源稀少珍贵之外，包括处理能力，无线通信带宽，储存空间都十分有限， 所以传感器节点的节能工作就成为延长WSN生命周期最主要的部分。在任何一种网络中，路由算法的优劣在一定程度上决定了整个网络系统的性能，一个好的路由算法能够有效地降低网络节点的能耗[2]。

本文旨在通过改进路由算法降低WSN网络的能耗。首先简单分析了基于分层结构的路由算法，然后重点分析了LEACH算法，对其中关于簇头选择上的问题提出改进算法，再针对传感器节点之间的通信模式提出改进方案，最后在Matlab进行了仿真验证。

1 路由协议

1.1 传统路由协议

经过多年的研究发展人们已经开发出了多种WSN路由协议，传统路由协议的代表是洪泛法，这种简单的方法存在很多的问题，比如信息爆炸和信息重叠，由于这些原因这种简单的方法也很难被应用于实践[3]。现在人们应用较多的路由协议基本可以分为三大类：平面路由协议，分层路由协议和基于地理位置的路由协议[4]。平面路由协议的代表为SPIN，DD，Rumor，基于地理位置的路由协议则以GEAR和GEM为代表。

1.2 基于分层结构的路由协议

在实践中，人们应用更多的是分层的WSN路由协议，在这项路由协议中通过簇的划分，使整个系统的能量消耗得以降低，并且使能耗分布也更加均匀，而由于减少了参与运算的传感器节点数，整个通信的开销也降低了。并且基于簇形成的策略网络，拓扑结构的变化对于网络的影响也会降低，使网络整体变得更加稳定。在目前的分层路由算法中，低功耗自适应集簇分层型协议LEACH(Low Energy Adaptive Clustering Hierarchy)是最早最成熟的算法，也是几乎所有分层路由协议的基础。

2 LEACH算法改进

LEACH在执行过程中不停的循环执行簇的重构过程，一个簇的重构过程可以理解为一个回合，每个回合可以分为建立阶段和数据传输的稳定阶段。簇的建立过程可分成四个阶段：簇头节点的选择、簇头节点的广播、簇头节点的建立和调度机制的生成[5]。在簇头建立的过程中，优化簇头节点的选择是重要也是最能有效延长WSN生命周期的手段。

在簇头的选择中，LEACH以轮为周期工作，在每一轮，所有的节点都会生成一个介于0到1范围内的随机数，然后将随机数跟阈值T(n)做比较[6]：

(1)

式中的P是簇头节点占整个节点的比率，r代表轮数，G是在最后的1/P轮中没有成为簇头的节点的集合。如果随机数小于T(n)，这个节点则成为一个簇头，产生簇头之后其他的节点会根据距离关系选择加入最近的簇，在形成的簇内，非簇头节点将会向簇头发送信息，由簇头进行数据融合再与基站通信，到此就完成了簇头的选择过程。对比与其他的路由协议，LEACH在很大程度上提高了效率，但是它依旧存在一些问题，在簇头的选择过程中，由于选择的随机性，使得簇头节点的分布不均匀，整个系统的能耗就不均匀，而剩余能量大的节点不能获得比低能节点更高的概率来成为一个簇头，这样将会大大地缩短网络的生命周期。所以需要修改原先的阈值T(n)为[7]：

(2)

式中的Ec代表节点的剩余能量，Ei代表节点的初始能量。很明显通过添加这个比值，高能的节点将获得更高的成为簇头的概率，而Phead在这里也不再是一个定值，而是一个随着节点距基站距离变化的值(通过two-ray模型计算得出)，具体关系为：

(3)

选择了簇头之后，就进入通信阶段，在传统的LEACH算法中传感器节点的通信通常为单跳，这意味着簇头只能直接与基站进行通信，这就带来了很多问题，且不说当网络的规模很大时，节点的传输能力不能达到那样的距离，就算是可以做到也需要消耗大量的能量，所以必须要修改路由算法的单跳为多跳，相比于单跳，多跳可以降低节点上能量的消耗。在选择了簇头之后，各个传感器节点会根据地理位置关系选择加入最近的簇(在这里设定距离基站最近的节点会自动成为簇头)以TDMA形式完成簇内的通信。

在之后的通信阶段就需要引入一个新的通信模式——基于栅格的多跳模式[8]。这种算法的基本思想是将整个系统区域划分为一个一个的栅格，并对这些栅格进行标号，每个栅格内部都有一些传感器节点。现在设定一个通信机制，先计算节点的数目尽量保证一个栅格内由LEACH算法选出的簇头数目大于等于1，然后根据剩余能量大小选出一个剩余能量大的传感器节点作为此栅格的簇头，接着根据地理位置关系和邻居栅格簇头剩余能量大小选择中继来进行多跳传输。实现多跳的方式有很多，选择栅格的方式可以在网络内部运算上节省大量的开支，更加便于应用于实践。在实际的操作中可根据经验设定栅格数，或设定一个最大栅格数，如果栅格内不存在传感器节点，再逐步缩小栅格数直至每个栅格内都有传感器节点存在。实现多跳的过程如图1所示，例如基站位于3号栅格，则周围2、5、6号栅格成为第一圈栅格，栅格内能量最大的簇头先进行数据融合再与基站进行通信，之后的1、4、7、8、9便成为第二圈栅格，第二圈栅格要与基站通信必须通过第一圈，且下一跳的栅格为所有邻区栅格内距离基站最近的栅格，以此类推，直至与基站通信。

图1 基于栅格的多跳算法

3 算法仿真

在M为100 m的范围内随机放置100个节点，每个节点的原始能量为0.5 J，仿真原LEACH算法的p为0.08，其他功耗数据见表1[9]。

表1 仿真参数

图2表示原LEACH的仿真结果，以半数节点的消亡轮数和全部节点消亡轮数为参考，大约在500轮左右有半数的节点耗尽了能量，而在1 000轮之前几乎所有的节点已经耗尽能量。

图2 原LEACH算法

图3表示改进簇头选择方式后的仿真结果，可以看出通过对阈值的改变，簇头的分布和能耗的分布更加均匀，大约在1 200轮左右耗尽了一半的节点能量，而全部节点消亡轮数也达到了2 500轮以上，比原LEACH提高了1.5倍的网络生存时间。

图3 改进的算法

图4表示基于栅格多跳的改进后算法仿真结果， 这里设定最大栅格数为16，如果相邻栅格内没有已生成簇头，则自动减小栅格数直到每个栅格内至少包含一个簇头。由于在图3的基础上添加了基于栅格的多跳之后半数节点消亡轮数增加到了约1 800轮，全部节点消亡轮数更是达到了5 000轮左右，相比于单跳提高了近1倍的网络生存时间。

图4 基于栅格的改进算法

4 结论

改进后的LEACH算法在原算法基础上使得剩余能量高且距离基站近的传感器节点更容易成为一个簇头，从而使得整个网络能耗分布更加均匀，提高了网络生存时间。在实际的传感网中由于网络较大造成了过多的网络通信能耗，将节点通信方式从单跳改为多跳更加节能，使网络具有更好的扩展性，使得该算法得以应用在更大的网络里。而基于栅格的多跳相比于其他多跳方式在网络内部运算上开销较小，更容易应用于实践当中。

[1] 尹湘源.无线传感器网络低能耗分簇路由算法关键技术研究[D].上海：华东理工大学,2014.

[2] 尚兴宏.无线传感器网络若干关键技术的研究[D].南京：南京理工大学,2013.

[3] 施家煌，赵成林.无线传感器网络(WSN)路由协议的分析与比较[A].中国通信学会，2008通信理论与技术新发展——第十三届全国青年通信学术会议论文集(下)[C].中国通信学会,2008:4.

[4] 赵强利，蒋艳凰，徐明.无线传感器网络路由协议的分析与比较[J].计算机科学,2009(2):35-41.

[5] 郑顾平，朱维.基于LEACH协议的安全性改进与建模分析[J].软件导刊,2014(7):131-133.

[6] 胡艳华，张建军.LEACH协议的簇头多跳(LEACH-M)改进算法[J].计算机工程与应用,2009(34):107-109.

[7] Xu Jia,Jin Ning,Lou Xizhong,et al.2012 9th Improvement of LEACH Protocol for WSN[C].International Conference on Fuzzy Systems and Knowledge Discovery (FSKD 2012),2012.

[8] 云春峰，王培康.基于虚拟栅格的无线传感器网络路由协议[J].计算机应用与软件,2009(9):200-202+218.

[9] Saini P,Sharma A K.E-DEEC-enhanced Distributed Energy Efficientclustering Scheme for Heterogeneous WSN[C].2010 1st InternationalConference on Parallel,Distributed and Grid Computing，2010：205-210.

Research on Routing Algorithm for WSN Based on Hierarchical Architecture

Liu Jing, Jing Ruijun

(SchoolofSoftware,ShanxiAgriculturalUniversity,JinzhongShanxi030801,China)

In order to prolong the life cycle of WSN (Wireless Sensor Network), an improved WSN routing algorithm based on hierarchical architecture is proposed. On the basis of famous LEACH algorithm, the problem about cluster head selection is pointed out. It changes the proportion p of cluster nodes in the original algorithm into a dynamic proportion varying along with the distance between node and sink (calculated by two-ray model), and optimizes the threshold of cluster head selection using the ratio between residual energy and original energy. Then the routing algorithm is modified from single hop to multiple hop that realized by using the virtual grid routing algorithm, so that the improved algorithm can be used in larger networks.

WSN routing algorithm; hierarchical architecture; LEACH; multi-hop; virtual grid

2016-11-09

山西农业大学科技创新基金(2016004)

刘 静(1990- )，女，山西榆社县人，助教，硕士，研究方向：无线通信及物联网。

1674- 4578(2016)06- 0045- 03

TN929.5；TP 212.9

A