一种能量有效的WSN分簇路由算法

【摘要】(Pingdingshan University, Pingdingshan 467000, China) Abstract: According to the disadvantages the paper designs the new energy efficient clustering routing algorithm E...

摘要：在对现有无线传感器网络分簇路由协议研究的基础上，针对其存在缺陷，提出了一种新的能量有效的分簇路由算法――EECRA。算法设计思想为：簇首选择时根据节点剩余能量与节点位置进行竞争，成簇时在簇首选择基础上选择较近簇加入，簇内簇间采用单跳多跳相结合的传输方式。仿真结果表明：EECRA算法可以有效的减少每轮能耗，延长网络生存周期，并均衡全网能耗。

关键词：无线传感器网络；路由协议；能量有效；簇首选择；轮

中图分类号：TP311文献标识码：A文章编号：1009-3044(2011)24-5896-03

An Energy Efficient Clustering Routing Algorithm For Wireless Sensor Networks

WANG Fei-fei, CHANG Xin-feng

(Pingdingshan University, Pingdingshan 467000, China)

Abstract: According to the disadvantages the paper designs the new energy efficient clustering routing algorithm EECRA based on the research of the routing protocol for wireless sensor networks. The design of EECRA is that: the algorithm elects head clusters according on the residual energy and the position of node, forms cluster based on electing head cluster to join in the nearest cluster, and the algorithm transmits data using one-hop or multi-hop at intra-cluster and inner-cluster. Simulation results show that EECRA can effectively reduce the energy consumption every round, achieve an obvious improvement on the network lifetime and balance the total energy consumption.

Key words: wireless sensor networks; routing protocol; energy efficient; cluster-head selection; round

无线传感器网络[1] （wireless sensor networks，wsn）是由大量部署在监测区域内的微型传感器节点组成，各节点通过无线通信方式形成一个单跳或多跳的自组织网络，目的是协作地感知、采集和处理监测区域内感知对象的信息，并发送给汇聚节点Sink。WSN在环境监测、工业生产和军事等方面的应用前景十分广阔，但是与传统无线网络相比，也存在诸多限制，如节点数目多不易管理，节点通常使用能量有限、不易更换的电池而令其能量、存储能力有限等，因此在WSN中，能量有效是首要问题，通过研究表明，无线通信所消耗的能量远远大于感知和计算消耗的能量，为了降低能耗，在进行无线传感器网络路由协议的研究和设计时，应以有效的利用能量，均衡节点能耗，延长网络生存周期为主要目标。目前，国内外学者在对WSN路由协议的研究过程中，提出了多种路由算法，根据网络逻辑结构可以大致分为两类：平面路由协议和分簇路由协议[2-3]，由于分簇路由自身的优势，研究人员对它的研究一直不曾中断，典型的分簇路由协议有LEACH[4](Low Energy Adaptive Clustering Hierarchy)，HEED[5](Hybrid Energy-efficient Distributed Clustering)、PEGASIS[6] (Power efficient gathering in sensor information system)、LEACH-C[7] (LEACH-centralized)、Proposed[8]、CPRE[9]等。本文在对现有分簇路由协议研究分析的基础上，提出了一种新的可以减少节点能耗，延长网络生存周期的能量有效的分簇路由算法――Energy Efficient Clustering Routing Algorithm，EECRA)。

1 相关工作

1.1 经典协议分析

LEACH协议是最早提出的WSN分簇路由协议，它在每轮工作中动态选举簇首，选出的簇首在数据传输过程中对收到的数据进行融合，之后的很多分簇路由协议都借鉴了这两种思想。PEGASIS协议是在LEACH协议分簇思想的基础上，提出的一种特殊的分簇协议，该协议中全网仅有一条通过贪婪算法而形成的链（即簇），仅有一个簇首，容易形成瓶颈。LEACH-C在簇首选举时采用集中式的算法，节点是否成为簇首不是由自己决定，而是由汇聚节点根据节点的剩余能量与地理位置进行选取，因此在成簇之前所有节点需要与汇聚节点直接通信以传递自己的相关信息，虽然在一定程度上形成的簇结构比较合理，但是能耗较大。Proposed协议于2007年提出，它在LEACH协议的基础上对如何选择簇首、如何成簇进行了改进，并对何时传输数据加以限制。

1.2 网络模型

假定一个无线传感器网络区域为M*M，有N个随机部署的节点。用ni表示网络中第i 个节点，则全网节点集合为N={n1,n2,…nn},|n|=N，假设：

1) 数据汇聚节点Sink位于M*M监测区域的外侧。Sink节点和传感器节点在部署后位置均不再改变；

2) 节点具有全网唯一的ID号，节点同构，具备数据融合的功能，但节点能量有限；

3) 根据接收者的距离远近，节点可以自由调整其发射功率以节约能量；

4) 信道对称。若已知对方发射功率，节点可以根据接收信号的强度RSSI计算出发送节点到自己的近似距离[10]。

5) 传感器节点可以通过单跳或者多跳与汇聚节点进行通信。

EECRA算法采用了LEACH协议中的无线通信模块。在该通信模块中，发送节点发送 bit信息到距离为d的接收节点时，消耗能量为：

每个节点接收kbit信息消耗能量为：

ERX(k)=k*Eelec(2)

由式(1)(2)可知，当d>d0时，节点发送能耗随着距离为四次方增长，当d

2 EECRA算法描述

EECRA算法设计思想如下：该算法由簇首选择，簇的形成以及数据传输所需路由构建三部分组成。首先，选择簇首，簇首个数主要根据监测区域大小及区域内的节点个数得出，根据簇首个数可以得出节点的理想发射半径，簇首选择成功后，节点选择合适簇加入，数据传输时，簇内簇间采取单跳与多跳相结合的方式。

2.1 簇首选择

在网络中产生合适的簇首个数对形成合理的簇结构、降低能耗至关重要，由文献[11]可知，网络监测区域中理想的簇首个数为：

簇的理想半径为： (4)

由于簇首个数kopt与簇的半径R为理想状况下的数据，因此可能存在某些节点不在任何簇的范围内，所以实际簇首个数应比理想簇首个数稍多才能令网络处于连通状态，因此实际簇首数K=c*kopt (c>1)。在簇首选择阶段，首先汇聚节点在网络覆盖区域内广播一个信号，传感器节点收到信号后，根据接收信号强度计算出到汇聚节点Sink的近似距离dtoS，同时Sink节点将整个网络以其为圆心，划分成半径r（r=R）相等的圆环。综合考虑节点剩余能量Eresidual，其到圆环中心线的距离dtoC以及环内总平均能量Etotal。当Eresidual>=Etotal时，则该节点成为候选簇首，然后根据R=Eresidual/dtoC产生计时数T，R越大，则T越小，即Eresidual值越大，dtoC值越小，则节点成为簇首的几率越大。首轮簇首选择时，每个节点的初始能量E相同，节点距离环的中心线越近，则节点形成的倒计时越小，每个传感器节点以相同半径发送消息，以节点ni为例，当节点计时器归0时，仍没有接收到来自同个圆环内其它节点的消息，则由候选簇首成为簇首节点，如果在计时器归0前收到了来自同个圆环内其它节点的消息，则其状态由候选簇首成为普通节点，由此方式可以确认每个圆环内的簇首节点。

2.2 簇的形成

簇首选择完毕，成为簇首的节点以相同功率向四周发射信息（信息中包含簇首ID――niID，所在圆环ID――niCID），节点接收到来自簇首的信息后，首先要判断是否在同一圆环内，如果不是，则对接收到的信息不进行回应，如果是，则需要判断加入哪个簇合适，由于簇首选择时已将能量作为条件限制，簇首能量得到保证，因此可以选择簇首较近的簇加入。

2.3 数据传输

成簇后，需要进行路由构建以传输数据，EECRA算法中分为簇内数据传输与簇间数据传输，在成簇时，每个节点均选择距离自己较近的簇首所在簇加入，因此簇内节点可以直接发送数据到簇首。簇间数据传输：除位于最外层圆环的簇首节点外每个簇首以R为半径广播信息MSG，信息中包含簇首ID niID，到汇聚节点的距离dtoS，所处圆环ID niCID，簇首ni接收到来自簇首nj的消息后，需做出如下判断：

1）如果niCID- njCID=0，即两节点位于同一圆环，则不做任何处理；

2）如果niCID- njCID =1，则将nj加入到ni的下一跳节点集合中；

3）如果niCID- njCID =-1，则不做任何处理。

另外，对于第2层圆环内的节点，如果ni的能量大于nj则ni直接发送信息至汇聚节点Sink。路由构建完毕后，每一个节点中均保存多个下一跳节点组成的集合，在数据传输时，可以从集合中选择合适的簇首进行数据转发，此为动态路由构建。许多分簇路由协议采用静态路由，虽然构建简单，但是并不能有效的降低能耗，因为网络能量消耗中数据传输所消耗的能量远远大于计算和感知所消耗的。同时，为了尽可能减少构建路由所消耗的能量，在本文中，借鉴已有的研究算法，不再每轮均成簇，而是多轮数据传输后再重新成簇。

2.4算法分析

EECRA算法在簇首选择时充分考虑到簇首的剩余能量以及到圆环中心线的距离，从而使剩余能量较多且位置比较合适的节点成为簇首，在一定程度上延长网络生命周期且避免网络空洞的出现，成簇时节点选择距离较近的簇首所在簇加入，可以减少簇内传输数据时的能耗，簇间路由动态构建，可以有效减少某些节点能耗过快而提前死亡，同时，多轮传输后再重新成簇的方法可以减少簇首选择及路由构建的能耗，并且动态路由的构建在一定程度上减少了节点的死亡率。

3 仿真

3.1 仿真说明

为了对EECRA算法的有效性进行验证，本文在OMNET++环境下对EECRA、HEED、LEACH进行仿真并分析。

具体参数如下：网络监测区域中有400个传感器节点，随机部署在(x=0,y=0)到(x=200,y=200)的区域内，Sink所在位置坐标为(x=50,y=250)。节点的初始能量为0.5J，数据包大小为4000bit，数据融合能耗为5nJ/bit/signal，传输放大器的能耗为10 pJ/bit/m2。

3.2 仿真结果

主要从全网能量消耗与网络生存周期两方面进行分析比较，具体如图1。

图1显示了全网存活节点个数随传时间变化的趋势，由图可知，EECRA算法的第一个节点死亡最晚，且第一个节点与最后一个节点死亡时间相差最小，因此，EECRA算法在有效延长网络生存周期的同时也延迟了第一个节点的死亡时间，即均衡了全网能耗。

图2 可以看出EECRA算法在刚开始工作时能耗与LEACH、HEED接近，但是接下来每轮数据传输结束后EECRA算法的剩余能量比LEACH、HEED都要多，剩余能量越多，说明在相同时间内使用的能量越少，这是因为虽然EECRA 算法在首轮成簇时消耗能量较多，但是一旦开始稳定的数据传输，多轮成簇以及动态的路由传输都会减少能耗，延长网络的生存周期。

4 小结

本文主要对现有的WSN分簇路由协议进行研究，借鉴其优点，针对其存在缺陷，提出了一种新的分簇路由算法EECRA，该算法在簇首选择时充分考虑节点剩余能量与节点到圆环中心的距离，成簇时选择距离较近的簇加入，传输数据时采用路由动态构建的方法。通过对仿真结果分析可知，该算法在一定程度上减少了网络能耗，延长了网络生存周期，并且第一个节点死亡与最后一个节点死亡时间相距最短，提高了网络的工作效率。

参考文献：

[1] 孙建民.无线传感器网络[M].北京:清华大学出版社,2006.

[2] 于海滨,曾鹏.智能无线传感器网络系统[M].北京:科学出版社,2006.

[3] 余勇昌,韦岗.无线传感器网络路由协议研究进展及发展趋势[J].计算机应用研究,2008,25(6):1616-1621.

[4] Heinzelman W, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless sensor networks[A].IEEE Proceedings of the Hawaii International Conference System Sciences'00[C].Hawaii,2000:3005-3014.

[5] Younis O, Fahmy S. Heed: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks[J].IEEE Trans. on Mobile Computing, 2004,3(4):660-669.

[6] Lindsey S, Raghavendra C.PEGASIS: power efficient gathering in sensor information systems[A].Proceedings of the IEEE Aerospace Conference'02[C].Big Sky, Montana, 2002:1125-1130.

[7] Lin CR, Gerla M. Adaptive clustering for mobile wireless networks[J].IEEE Journal on Selected Areas in Communications,1997,15(7):1265-1275.

[8] Ki Young Jang, Kyung Tae Kim, Hee Yong Youn. "An Energy Efficient Routing Scheme for Wireless Sensor Networks". Fifth International Conference on Computational Science and Applications. DOI 10.1109/ICCSA.2007.10:399-404.

[9] 龚本灿,李腊元,蒋廷耀,等.一种基于剩余能量的无线传感器网络分簇路由协议[J].计算机工程与应用,20086,44(8):31-33.

[10] Gibson J. The Mobile Communication Handbook. Boca Raton: CRC Press,1999.

[11] W.R. Heinzelman, A. P. Chandrakasan, H. Balakrishnan. An application-specific protocol architecture for wireless microsensor networks. IEEE Trans. on Wireless Communications,2002,1(4):660-670.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文