WSNs基于非均匀分区成簇的多跳路由协议

陈 笑 祁荣宾 钱 锋 Huaglory Tianfield

(化工过程先进控制和优化技术教育部重点实验室(华东理工大学)1，上海 200237;

WSNs基于非均匀分区成簇的多跳路由协议

陈 笑1祁荣宾1钱 锋1Huaglory Tianfield2

(化工过程先进控制和优化技术教育部重点实验室(华东理工大学)1，上海 200237;

针对无线传感器网络中节点能量有限和能量空洞问题，提出了一种基于优化簇半径的非均匀分区成簇多跳路由算法(UZCMR)。在分簇时充分考虑节点的能量和地理位置，通过“逐层分区”的方法将整个网络以Sink为中心划分成若干个区域。每个区域中的节点通过最优簇半径进行分簇，同时使用参数使靠近Sink节点的簇的规模小于远离Sink节点的簇，并采用了最小通信代价的多跳路由。试验表明，与低功耗自适应集簇分层型(LEACH)协议相比，UZCMR形成的簇首分布均匀，有效均衡了节点能量消耗，缓解了能量空洞问题，显著延长了网络生命周期，也扩大了协议的适用规模。

无线传感器网络(WSN) 低功耗自适应集簇分层型(LEACH)协议 能量消耗 Sink节点 多跳路由协议

国家自然科学基金资助项目(编号:20876044);

上海市基础研究重点基金资助项目(编号:10JC1403500);

上海市重点学科建设基金资助项目(编号:B504)。

修改稿收到日期:2012-05-31。

0 引言

无线传感器网络的目的是协作地感知、采集和处理网络覆盖区域里被监测的对象信息。大规模无线传感器网络通常包括三类节点，即传感器节点(sensor node)、汇聚节点(Sink)和管理器节点［1］。鉴于能量平衡或其他总体网络性能指标，节点之间并不是全部一对一进行通信，而是通常借助中间节点以多跳路由的方式将源数据传送至目的节点。

分簇路由是无线传感器网络节省能耗的一种重要方法，采用分簇结构可以提高能量利用效率，达到负载平衡的目的。它的主要思想是在无线传感器网络中选择部分节点作为簇头节点，以此将网络划分成簇。簇内成员节点将数据发送给簇头节点，簇头节点将数据经数据融合后以多跳方式发送给Sink节点。这种分簇方式虽有利于节省能量，但也使得靠近Sink节点的簇头承担了过多的转发任务而过早死亡。通常把这种问题称为“热区”问题［2-3］。

Heinzelman等人提出的低功耗自适应集簇分层型(low energy adaptive clustering hierarchy，LEACH)协议［4］是早期的一种专为无线传感器网络设计的经典分布式低功耗自适应分层路由协议。该协议定义了“轮(round)”的概念。许多研究都沿用了LEACH协议的分簇思想。但是LEACH算法没有考虑节点的能量，采用单跳通信路由造成距离汇聚节点远的节点能量开销过大;也不能保证簇头数目和分布，当簇头与汇聚节点(Sink)相距较远时，通信会消耗较多能量，造成网络能耗不均衡。

继承LEACH协议成簇思想的改进协议有很多。Lindsey S等人提出的PEGASIS(power-efficient gathering in sensor information system)将网络中的所有传感器节点构成链(chain)，全网只选择一个群首节点［5］。Handy M J等人在选择簇首时考虑了节点的能量因素，使具有较多剩余能量的节点有更多机会成为簇头，但未考虑节点的位置［6］。李成法等人提出的节能非均匀簇(energyefficient uneven cluster，EEUC)是一种非均匀的分簇路由协议，它基于地理位置不同对网络进行规模不等的分簇，缓解了“热区”问题，但并没有讨论如何优化簇半径［7］。网络分簇时，簇的规模过大或过小都不利于消减能耗。刘安丰等人提出了一种采用不等簇半径轮换工作的能量空洞避免策略［8］。Faroop M O等人提出了MR-LEACH多跳路由协议，以Sink节点为圆心将网络划分成均匀的圆环区域，圆环内的节点单跳成簇，不同环内的簇头节点以多跳路由的方式将数据传送到Sink节点［9］。该方法假设Sink节点可与所有节点通信。

综合而言路由协议大致可分为两类，一类为选取固定数量的簇头节点，另一类为选取固定长度的簇半径。为此，本文在LEACH算法的基础上，提出一种新型的基于非均匀分区成簇的多跳路由协议(uneven zoned clustering multi-hop routing，UZCMR)。此方法将网络逐层划分区域，解决了大规模网络中Sink节点并不可能与每一个节点通信的问题。另外，用优化的簇半径对网络进行不等规模分层成簇，使靠近Sink节点的簇半径较小，以便均衡靠近Sink节点的簇头的能量消耗，为其转发其他簇头的数据预留能量，从而缓解“热区”问题。

1 LEACH算法简介

LEACH是低功耗自适应分簇路由算法。它的成簇方法简单，是一种经典的分簇协议，被广泛使用和改进。LEACH主要考虑簇内节点的能量消耗问题，其将网络的能量平均到每个传感器节点中。LEACH定义了“轮”的概念，每一轮包括初始化和稳定工作两个阶段。

在初始化阶段，各节点生成一个0～1的随机数。如果该数小于阈值T(n)，则选择该节点作为簇首。T(n)计算方法如下［4］:

式中:P为网络中簇头占总节点的百分比;r为选举轮数;rmod(1/P)代表这一轮循环中当选簇头的节点个数;G为这一轮循环中未当选簇头的节点集合。

在稳定工作阶段，节点持续采集监测数据并传送到簇头，簇头对数据进行必要的融合处理后，发送到汇聚节点。为了避免额外的处理开销，稳定工作状态一般持续相对较长的时间。在本轮工作完成之后，网络将重新进入下一轮的工作周期，完成两个阶段的过程。

基本LEACH协议存在如下问题。

①簇头与汇聚节点间采用直接通信方式，其能量利用效率较低。

②簇头选举由随机数产生，这可能导致簇头分布不合理和个数偏离期望值。

③簇头与汇聚节点的单跳方式使得节点通信范围有限，限制了网络覆盖范围，不适用于大规模部署的网络。

针对这些问题，本文从簇头选举、簇的建立和簇间路由通信这三方面对LEACH进行了改进。

2 UZCMR路由协议

在UZCMR路由协议设计过程中，主要考虑网络总能量消耗最小和使各个区域的能量消耗均衡，避免“热区”问题。UZCMR协议算法也采用了“轮”的概念，每一轮分为初始化阶段和稳定数据传送阶段，其中稳定数据传送阶段分为很多“帧”。初始化阶段包括簇头选举、簇形成以及簇间路由树构造。在数据传输阶段，簇成员节点采集数据并发送给簇头，经过数据融合后发送给Sink节点。

节点部署完成后，每个节点初始化并处于信号监听状态，同时收集汇聚节点以及各区域簇头的广播信息。簇头多跳路由示意图如图1所示。

图1 簇头多跳路由示意图Fig.1 Schematic of cluster-head multi-hop routing

本文引入“区域”的概念，采用逐层划分区域的方法，即Sink节点以一定半径广播信号，监听到Sink节点广播信号的节点组成Z1(Z1=1)，Zi中节点以概率P(Zi)选举出簇头后，以一定的半径广播信息。首次监听到信号的传感器节点若尚未得知层次信息，那么其层次为(Zi+1)，同时以概率P(Zi+1)选举簇头并广播簇头信息。在数据传输阶段，(Zi+1)中的簇头根据监听到的Zi中簇头的信息选择所要加入的下一跳簇头，并在稳定数据传输阶段向其发送数据，经过多跳后将数据发送给Sink节点。

2.1 网络模型

本文对无线传感器网络模型作以下假设。

①假设N个无线传感器节点随机均匀部署在二维平面上的一块方形区域A内，汇聚节点处于该区域范围之外。

②传感器节点同质，能量有限，部署后无法补充能量，其信号传输功率有限，不一定能够直接将信号发送至汇聚节点。

③所有传感器节点同构，在网络中具有相同的重要性。

④网络链路对称，无线电发射功率可控，节点可以根据发送距离选择无线电信号发射功率。

⑤传感器节点的位置未知，且无法采用GPS定位;节点部署后不再移动。

2.2 能耗模型

本文采用的能耗模型如下。定义无线电路发送l bit消息至距离d m消耗的能量为:

式中:Eelec为发射电路能量损耗，由电路本身决定;εfsd2、εmpd4为无线电功率放大损耗。d0由式(3)决定:

而传感器每通过无线电接收 l bit数据，能耗如下:

数据融合1 bit所消耗的能量为EDA。

2.3 网络分层

对于本文提出的基于簇半径优化的非均匀分簇路由协议，采用逐层成簇的方法。该方法中每个传感器节点不需要通过汇聚节点广播或者GPRS的方式获取自身位置信息。

网络分区时，从Sink节点向外将网络区域分别编号为Z1，Z2，…，Zn，由Z1开始逐层划分。汇聚节点广播分层信号并确定网络的Z1。设汇聚节点距离传感器区域距离为d，Z1的区域半径为r1，那么汇聚节点广播半径为R0=d+r1。接收到汇聚节点广播信号的传感器节点S(i).Z=1，并开始选举簇头，下一区域范围由上一层簇头的广播信号确定。因此，Sink节点无需与网络范围内的所有节点通信，更适用于在大规模网络中的应用。

刘明等人对单个簇的能耗进行了分析，最优簇半径推导如下［10］:

式中:A为监测区域的面积;N为区域内节点数量;EDA为融合每比特数据所消耗的能量;εfs为功率放大所需能量。

本文将最优簇半径公式引入簇头竞争半径。

式中:α为梯度因子，α≥1。

上一区域确定簇头后，簇头节点以半径Ri广播相关信息，包括节点ID、区域Zi、与汇聚节点的通信代价、传感器网络节点的平均能量(Eavg)。

在簇头竞选阶段，为了避免由于Sink附近节点转发大量数据而产生能量空洞问题，本文采用非均匀分簇的方法，使得距离汇聚节点远的区域中簇头密度较小，簇的规模相对较大;距离汇聚节点较近的层中簇头分布相对密集，簇的规模相对较小，从而平衡簇头的能量负载。

另外，考虑到节点剩余能量对竞选簇头的影响，使剩余能量较高的节点成为簇头的概率较高。假设初始成簇概率为P0(0.07)，令:

式中:β为簇头非均匀程度参数，0＜β≤1，β越小，层与层之间的成簇概率梯度越大;Eresidual为节点的剩余能量;Eavg为整个网络节点的平均能量。这里由于网络模型中定义所有传感器节点同质，因此，当轮数r=1时，Eavg=Emax;当r＞1时，在每一轮的最后一帧里，传感器节点需要将自身的剩余能量与传感数据一起发送至汇聚节点，汇聚节点计算节点平均能量:

在下一轮的簇头竞选中将Eavg广播给传感器网络Z1的网络区域，后面竞选成为簇头的节点依次广播至网络所有区域。

2.4 簇的建立

当某区域中节点产生的0～1之间的随机数小于

2.5 簇间通信

在某一区域成簇以后，该区域中的所有簇头需要选择上一层的一个簇头作为将数据多跳传送至Sink节点的下一跳节点。为了提高网络的能量效率和网络负载平衡，若Zi-1区域中存在簇头剩余能量大于Eavg，那么选取该部分簇头中通信代价最小的簇头作为Zi中某簇头的下一跳簇头节点，否则，选取剩余能量最大的簇头作为该簇头的下一跳簇头。将Sink节点也看做一个簇头，其所在的区域S(i).Z=0，通信代价为0。节点由Z0开始，若确认自己为簇头，Sink节点则以半径Ropt发送广播信息，包括ID、层次、通信代价。未知层次的节点Ni保存所收到的广播信息，据此计算自己的层次信息，Zi=Zj+1，其中Zi为节点Ni的层，Zj为接收到的簇头所处的层。若Ni在后续的簇头竞选中能够当选，Ni可以根据广播信息选择下一跳簇头。

在簇头竞选过程中，簇头Ni通过上一层 Nj向Sink每发送1 bit数据，整个网络所消耗的总能量为Ccom，称为节点Ni的通信代价。

同层或者下一层非簇头节点可以根据广播信息选择加入合适的簇。假设Ni为簇头，Nj、Nk、Nm为通信范围内的非簇头节点，且满足:

那么Ni根据接收到的Nj、Nk、Nm的广播信息，计算与汇聚节点通信的通信代价。

若Ccom(Ni-m-link)≤Ccom(Ni-j-link)≤Ccom(Ni-k-link)，则Ccom(Ni-link)=Ccom(Ni-m-link)。

簇头Ni选择通信代价最小的下一跳簇头发送加入请求消息，得到确认后，在本轮通过该簇头进行数据转发。

为了保证通信质量，簇头之间的通信采用载波监听多路访问(carrier sense multiple access，CSMA)的MAC协议。这里假设簇间的数据冗余度较低，簇头只是转发其他簇的数据。

2.6 算法步骤

具体的算法步骤如下。

①Sink节点以一定半径广播信息，收到Sink信息的节点i的S(i).Z=1。

③未确定区域的节点接收到广播信号后确定自己为下一区域中的节点。

④重复步骤②、③，直至所有节点都确定自己的层次信息。

⑤网络拓扑选择下一跳节点:若Zi-1区域中存在簇头剩余能量大于Eavg，那么选取该部分簇头中通信代价最小的簇头作为Zi中某簇头的下一跳簇头节点;否则，选取剩余能量最大的簇头作为该簇头的下一跳簇头。

⑥各层中的簇头节点以半径Ri=Roptα(Zi-1)广播信息，本层或下一层中的非簇头节点根据收到的信息，分别计算通过该簇头多跳至Sink的通信代价，并选择通信代价最小的簇头发送加入请求。

若普通节点均找到了所属的簇，每个簇头均找到了下一跳，则簇及多条路由建立阶段至此结束，网络进入数据采集阶段。

⑦本轮数据采集结束后，进行重新分区与分簇，循环步骤①～⑦。

本文主要从以下几个方面改进了LEACH协议。

①LEACH协议要求Sink节点能与所有节点通信。而UZCMR通过逐层划分区域的方式，由上一区域的簇头广播信息来确定下一个区域;汇聚节点无需具有极高的信号发送功率和定位硬件模块。

②成簇过程中引入了最优簇半径的概念。在最优簇半径的基础上每个区域构建不同规模的簇。距离Sink节点较近的簇规模较小。这不但使每个区域能构建规模合理的簇，并且使靠近Sink节点的簇预留了能量来转发相邻簇头的数据，缓解了能量空洞问题。

③簇头节点选择多跳路径时，不仅考虑了通信代价，同时考虑了下一跳节点的剩余能量，从而均衡了网络负载。

3 仿真试验

为了对UZCMR协议的性能进行评估，在此利用Matlab平台对该协议进行仿真试验。将UZCMR算法在网络能量均衡性、能量效率、生命周期等方面的性能表现，与LEACH和EEUC路由协议进行对比。各试验参数如表1所示。

表1 试验参数Tab.1 Experimental parameters

UZCMR的其他参数设置为:α=1.2、β =0.9，通过式(5)可得本文的Ropt=20.771 9 m。

UZCMR网络分区图如图2所示，其中“*”代表Z1内的节点，“。”代表Z2内的节点，“+”代表Z3内的节点。

图2 网络区域划分图Fig.2 Network zones division

图3给出了在相同参数和试验条件下，几种协议中存活节点数目随时间(轮数)变化的情况。

从图3可以看出，LEACH协议第一个节点死亡轮数是第254轮，EEUC是第776轮，而UZCMR协议出现第一个死亡节点轮数是1 217轮，比LEACH协议推迟了近1 000轮;而UZCMR协议最后一个节点死亡的轮数是1 710轮，EEUC是第1 092轮，LEACH是在第1 222轮。由此可知UZCMR由于引进优化的簇半径公式，且采用分区成簇，各节点负载更为均衡，从而延长了网络生命周期。

图3 各种协议的网络存活时间Fig.3 Network survival time of various protocols

每轮中各协议的总网络剩余能量对比图如图4所示。

图4 各协议的网络剩余能量Fig.4 Network residual energy of various protocols

由图4可以看出，由于UZCMR引入了最优簇半径，使得网络中的簇半径大多接近最优化，减少了能量消耗。而LEACH协议由于随机选择簇头节点，簇头与Sink节点采用单跳方式，其能量消耗最快。EEUC协议的簇半径不一定是最优，所以其节点能耗也多于UZCMR协议。

UZCMR在不同簇半径下的网络生命周期的对比图如图5所示。

图5 簇半径vs网络生命周期Fig.5 Cluster radius vs.network life cycle

本文提取所有节点完全死亡时和还存活10个节点时的数据一起做分析比较。从图5可以看出，在本文的环境下，簇半径为20 m时网络生命周期达到最大。当簇半径过大时，节点由于远距离通信会造成能量浪费，验证了本文改进的结果。UZCMR通过优化的簇半径，节省了网络能量消耗。

UZCMR各区域中的节点在200和500轮时的平均能量如图6所示。其中，标号为1的为200轮时的平均能量，标号为2的为500轮时的平均能量。从图6所示的柱状图可以看出，从靠近Sink节点的Z1到远离Sink节点的Z3，各区域中的平均能量基本持平。这表明本文采用的方法缓解了部分“能量空洞”问题。

图6 UZCMR各区域在200、500轮时的网络能量Fig.6 Network energy of UZCMR zones in 200 and 500

4 结束语

本文针对无线传感器网络中能量有限和“热区”问题，提出了一种基于簇半径优化的非均匀分区路由协议。通过逐层划分区域的方式从靠近Sink节点的区域开始将网络分成大小递增的不等区域;在区域的簇头竞争半径中引入了最优簇半径公式，将各区域进行合理大小的成簇，使能量消耗在各个区域中趋于平衡状态。

仿真结果表明，通过改进，UZCMR路由协议平衡了网络负载，缓解了“热区”问题，延长了网络生命周期。

［1］ Akyildiz I F，Su W，Sankarasubramanian Y，et al.A survey on sensor networks［J］.IEEE Communications Magazine，2002，40(8):102-114.

［2］ Soro S，Heinzelman W.Prolonging the lifetime of wireless sensor networks via unequal clustering［C］∥ Proceedings of the 5th International Workshop on Algorithms for Wireless，Mobile，Ad Hoc and Sensor Networks，Denver，CO，2005.

［3］ Gou H，Yoo Y.An energy balancing LEACH algorithm for wireless sensornetworks［C］∥ Seventh InternationalConference on Information Technology，IEEE，2010(12):822-823.

［4］ Heinzelman W R，Chandrakasan A，Balakrishman H.Energy-efficient communication protocol for wireless microsensor networks［C］∥Proceedings of Hawaii International Conference on System Sciences.Hawaii，2000.USA，2000:3005-3014.

［5］ Lindsey S，Raghavendra C.PEGASIS:Power-efficient gathering in sensor information systems［C］∥Proceeding of the IEEE Aerospace Conference on IEEE Aerospace and Electronic Systems Society，Montana，2002:1125-1130.

［6］ Handy M J，Haase M，Timmermann D.Low energy adaptive clustering hierarchy with deterministic cluster-head selection［C］∥ 4th International Workshop on Mobile and Wireless Communications Network，Washington.DC，2002:368-372.

［7］李成法，陈贵海，叶懋，等.一种基于非均匀分簇的无线传感器网络路由协议［J］.计算机学报，2007，30(1):27-36.

［8］刘安丰，阳国军，陈志刚.基于不等簇半径轮换工作的传感器网络能量空洞避免研究［J］.通信学报，2010，31(1):2-8.

［9］ Farooq M O，Dogar a b，Shah G A.MR-LEACH:multi-hop routing with low energy adaptive clustering hierarchy［C］∥2010 Fourth International Conference on Sensor Technologies and Applications，2010.

［10］刘明，曹建农，陈贵海，等.EADEEG:能量感知的无线传感器网络数据收集协议［J］.软件学报，2007，18(5):1092-1109.

Multi-hop Routing Protocol Based on Uneven Zoned Clustering for WSNs

Department of Computer，Communications and Interactive Systems，

School of Engineering and Built Environment，Glasgow Caledonian University2，Glasgow Scotland，U.K.G4 OBA)

To solve the problems in wireless sensor network，i.e.，limit node energy and energy hole，the uneven zoned clustering multi-hop routing(UZCMR)algorithm based on optimized cluster radius is proposed.In clustering，energy and geographic location of the node are fully taken into account.Through the method of“hierarchic partition”，the entire network is divided into several zones with Sink as the center.The nodes in each zone are clustered via optimized cluster radius.In addition，through adopting parameter，to make the scale of clusters near the node of Sink smaller than that of the clusters far from the Sink.Furthermore，the multi-hop routing with minimum communication cost is used.The experiments show that comparing with the LEACH protocol，the cluster heads formed by UZCMR are distributed evenly，thus the energy consumption of the nodes is effectively balanced，and the problem of energy hole is eased.The life cycle of network is obviously extended，and the adaptable scale of the protocol is expanded.

Wireless sensor network(WSN)Low energy adaptive clustering hierarchy(LEACH)protocolEnergy consumption Sink node Multi-hop routing protocol

signal strength indicator，RSSI)来选择它要加入的簇，并告知相应的簇头。簇头收到簇内成员发送的信息后，创建时分多址(time division multiple access，TDMA)时刻表，通知每个节点何时开始传输数据。

TP273

A

陈笑(1988-)，女，2012年毕业于华东理工大学控制科学与工程专业，获硕士学位;主要从事无线传感器网络路由协议方面的研究工作。

成为簇首的节点向周围广播信息，其他非簇头节点根据收到信号的强度(