基于不均等环带分区的WSN能耗均衡路由协议

郑文军，韩 波

（1.安徽理工大学 计算机科学与工程学院，安徽 淮南 232001；2.阜阳师范大学 计算机与信息工程学院，安徽 阜阳 236037）

无线传感器网络(wireless sensor networks，WSN)是由部署在监测区域内的大量微型传感器节点组成，可用于各种场景，如环境监测[1]、目标跟踪[2]、健康监测[3]、军事[4]、农业[5]和其他许多应用[6-7]。WSN具有能量、处理能力、存储和传输范围等多种资源约束的特点。在这些因素中，传感器的能量一直是无线传感器网络的主要资源约束[8]。为了应对这个挑战，国内外很多研究人员都提出不同的解决方案。

分层或基于成簇的路由算法是众所周知的技术，在伸缩性和高效性方面具有特殊的优势。低能耗自适应分簇协议LEACH[9]是一种流行的机制，它能动态地形成集群并分配簇头，然后将聚集的数据发送到基站，能够有效缓解节点的能量损失。但是LEACH未能考虑到簇头的剩余能量并采用随机选举簇头的方式导致簇头分布随机，最终形成“能量空洞”现象[10-11]。文献[12-13]针对LEACH的缺点提出了改进，文献[12]在LEACH的基础上提出通过双簇头来均衡簇头之间的传输能耗，但是采用基于LEACH协议中的簇头选择方式，未能考虑到簇头分布的随机性问题；文献[13]则在选举簇头时充分考虑了簇头能量并建立簇头与基站之间的多跳传输路径来减少能耗的损失，但是采用均匀分簇的方法，基站附近的节点会因中继数据导致负载过重提前死亡。相对而言，非均匀分簇算法在节点负载均衡与克服“能量空洞”现象方面效果更佳。文献[14]提出了一种能量高效的非均匀分簇算法，基站附近节点直接与基站通信，远距离节点则通过改进的LEACH簇头选择方式建立规模大小不等的簇，有效提高了节点的能量利用率，但是簇头的个数仍旧根据经验来选择，未能寻找出网络中的最优簇首个数。文献[15-17]提出了基于分区思想的路由算法，根据距离基站的远近将网络划分不同的层次，通过合理的分区来达到降低网络能耗的目的；但是文献[15-16]均未能考虑到每层节点的能耗均衡问题，同时基站附近节点成簇会更加损耗能量；文献[17]中首环半径选择过大，会是得原本负载较重的内环节点在中继数据时过快死亡，不利于网络能耗均衡。文献[18]提出一种能量异构的分簇方案，根据节点与基站的距离，在不同的地理位置布置初始能量不同的节点来克服“能量空洞”，达到均衡网络能耗的目的，但是该方法实际操作起来很难实现。

本文借鉴上述算法的优点提出了一种基于不均等环带分区的能耗均衡路由算法UREC，通过对网络进行不均等划分来实现非均匀分簇，并对各环带内节点总能耗进行分析计算得出最佳的区域划分方案，能够有效均衡网络的整体能耗。

1 网络模型与能耗模型

1.1 网络模型

本文首先假设无线传感器网络中有N个节点随机均匀的分布在以基站为中心，半径为R的圆形网络区域中。网络模型具有以下性质：

1)节点都是静止不变的，一旦部署完成便不再变化；

2)基站能量不受限，其余节点初始能量均为E0；

3)节点位置已知，可获取自身的坐标信息，且发射功率可调；

4)每个节点都有唯一的ID号。

1.2 能耗模型

采用与文献[19]相同的能耗模型，仅考虑节点的通信能耗，忽略节点存储与计算等能量消耗。

如图1，节点发送lb数据给相距dm处的另一个节点所消耗的能量为

节点接收lb数据的能耗为

其中Eelec为发送和接收1 b数据时电路的能量损耗。d0为通信阈值，且有εfs和εmp表示相应的衰落系数）。当d＜d0时，采用自由空间模型；当d≥d0时，采用多路径衰减模型。

图1 网络能耗模型

1.3 数据融合模型

本文采用数据融合技术来减少网络中传输的数据量，达到节约网络能耗的目的。由于簇头与簇头间距离相对较远，本文只考虑簇内数据融合。数据融合的模型为：簇头接收到簇内n个成员节点发送的lb数据，最终都会压缩为1个lb数据发送给下一跳簇头，数据融合能耗为EDA。融合lb数据所消耗的能耗为：

2 基于不均等环带的能耗均衡路由协议

2.1UREC算法简述

本文提出的UREC算法能够将节点基于位置划分，建立若干位置分布均匀簇规模大小不等的簇，有效解决了簇头分布随机性大，簇群分布不均匀而导致节点能耗不均衡问题。本文主要分为3个阶段：

1)区域划分阶段。将监测区域划分成若干层圆环，首先计算各环带内的节点总能耗，以各环带能耗均衡为目标来确定每层环带的宽度；其次是将网络进一步划分，每层都划分成相等的若干个分区，分区的面积与距离基站的距离成正比，最终构建出若干面积大小不等的簇，从而实现网络的非均匀分簇，有效缓解了“能量空洞”问题。

2)簇的形成阶段。每个分区内进行非均匀成簇，簇头选择时综合簇内能耗与簇间传输能耗，保证数据传输时簇内能耗与簇间能耗最优；同时在竞争簇头的过程中参考节点自身的剩余能量，确保所选举的簇头能量较高。

3)簇间传输阶段。经过区域划分之后，整个网络在纵向上被划分成若干个扇形区域，每个分区内成员节点通过单跳方式将数据发送给所在簇的簇头节点，簇头节点再将数据进行融合之后发送给同一扇形区域的下一层环带内的簇头节点，以多跳的方式建立合理的簇间路由。

2.2 区域划分

区域划分的基本思想：假设网络以基站为中心被划分成若干环带，每层环带又被划分成相同数量的分区，以环带间能耗均衡为目的确定各个环带的宽度。如图2，将监测区域划分成H层宽度不等的环带，再将每层环带均匀的划分成K个分区，同一层环带内的各个分区面积相等，距离基站越远，分区面积越大，最终形成的簇的面积越大。为了降低网络能耗的损失，应保证簇内成员节点与簇头的距离、簇头与簇头的距离、簇头与基站的距离均符合自由空间模型，区域划分需遵守3个约束条件：

1)第1层环带的宽度小于d0；

2）相邻2层环带的宽度之和应小于d0；

3)任意分区内的任意两个节点之间的最大距离小于d0。图中Ri表示第i个同心圆的半径，ri表示第i个环带的宽度，Ci表示第i个环带区域且R1=r1,Ri=Ri-1+ri。

1)首环半径的确定。已知距离基站较近的节点除了自身的任务外，还需中继距离基站较远的节点的数据任务，这些节点会因负载过重而提前死亡，形成“能量空洞”，影响整个网络的寿命。根据文献[20]可知，在一定距离范围内，相比于通过簇头的转发，节点直接与基站通信的能耗损失会更低。通过改进文献[17]中的首环半径公式，我们可以得到

其中，α为调节系数。

当α=1时，首环半径r1取得最大值，环带内节点直接与基站的通信能耗更少，但是由于范围较大，不利于节点负载均衡。仿真发现，当α=0.5时，网络寿命最长。

图2 区域划分

2)各环带宽度的确定。在理想的网络能耗均衡情况下，各环内的总能耗相同。本文首先计算出各环的节点能耗，然后以理想情况下的网络能耗均衡为目标推导出各环带的最佳宽度的表达式。每个数据采集周期内，各环带内的能耗主要分为2部分：

（ⅰ）簇内成员节点的数据发送能耗和簇头的接收、融合能耗，称之为簇内能耗。

（ⅱ）簇头接收上游簇头数据的接收能耗和簇头转发给下游簇头的转发能耗，称之为簇间能耗。

已知监测区域被划分成了H层环带且节点均匀分布在网络中，那么第i层环带内的节点数Ni

每一轮数据采集周期内，第i(2≤i≤H)层环带内的簇内传输总能耗的期望为：

其中，Ri-cluster为第i(2≤i≤H)层环带内簇半径的近似值，有

当i=1时，将整个第1环看成一个以基站为簇头的簇，簇内其余节点直接将数据发送至基站，那么，第1环内的簇内传输总能耗期望为：

外层环带内的簇头节点需要以内层环带内簇头作为中继节点，最终将感知的数据发送到基站。那么，第i层环带内的每个簇头节点在一轮数据采集周期中接收来自外层簇头的数据总量为(H-i)l，第2～i层内每个簇头转发给下一层簇头的数据总量为(H-i+1)l，第1层簇头转发的数据总量为(H-1)l。那么，第1层环节点将外层数据发送给基站的能耗模型

第2层环带内簇头数据通过首环内成员节点转发给基站。第2层簇头节点到首环转发节点的距离服从均匀分布其平方的期望值为则第2层簇间传输总能耗的期望为：

其中

为减少簇内能量的损耗，簇内能耗最小的理想情况下是各环带内簇头位于环带的几何中心位置，此时同一扇形区域的相邻簇头间的距离满足

则第i(3≤i≤H)层环内簇间传输的能耗

故一个数据采集周期内，每层环带内的总的能量消耗为：

根据各层环带内能耗均衡的准则，可得到各环带宽度的关系式

2.3 簇的形成

2.3.1 构建簇头竞争簇

当节点部署到监测区域之后，基站向全网广播消息通知所有节点开始工作，每个节点根据自己的位置信息判断自己所处分区，同一分区内节点构建成一个簇头竞争簇，参与簇头的竞争。每个节点都在通信范围内广播消息，根据接收到的信息确定处于同一分区内节点的个数、距离及能量信息。

如图2区域划分图所示，整个网络共被分成H×K个分区，其中有H层环带区域和K个扇形区域，每个分区(第1环除外)即一个簇头竞争簇，从中选举出一个簇头节点。

2.3.2 簇头选举

竞争簇内竞选簇头时应该考虑三个因素，首先我们所选出的簇头应该保证簇内能耗较小，其次是簇头能量充足，最后是簇间传输能耗较小。针对这三个影响因素构建相关通信损失函数作为簇头选举时的参考依据，有

网络中所有节点根据公式(17)计算自身的损失函数并广播给分区内其他节点，同一分区内选择损失函数最小的节点最为簇头节点，分区内其他节点作为成员节点向簇头发送数据。

2.4 簇间传输

簇群形成之后，首先簇内成员节点将感知数据发送给所在簇簇头，其次外层簇头需要通过内层簇头中继转发，最终数据被发送到基站。已知整个监测区域被划分成了H层环带和K个扇形区域，为了保证簇间多跳的通信路径最短，以扇形区域为单位，处于同一扇形区域内的各层簇头节点由外向内传输数据，最终将数据发送到基站。

假设 CH(h,k)是第h(1≤h≤H)环中第k(1≤k≤K)个分区内的簇头节点，那么，簇头CH(h,k)的下一跳簇头节点Next(CH)的具体选择规则如下：

3 仿真与分析

为了验证UREC的性能，我们使用MATLAB作为仿真工具，通过与LEACH和EEUC进行性能比较，从网络中节点存活个数、网络剩余能量以及节点死亡率三个方面评估本文提出的UREC算法的性能。根据能耗影响的主次因素，α、β和γ的取值分别为0.5、0.3和0.2，其余实验参数设置如表1。

根据不同的区间数设置，可计算出网络中总的分区数量以及相应的环带宽度，如表2。随着K的取值不同，网络中的簇的数量也不同，分簇数目过少会加快簇头的能耗损失，分簇数目过多则会增加簇间传输的能量损失。如图3，以网络中10%节点死亡时间为参考依据，可以得出，当K=10时，此时网络生存时间最长。

表1 实验仿真参数

表2 各环半径的确定

图4显示了3种算法的存活节点数量的变化曲线，从图中可以看出UREC运行到约1 600轮时才出现第一个死亡节点，而LEACH和EEUC的第一个节点死亡出现在600轮和1 500左右。LEACH首个死亡节点出现最早，可能是由于LEACH选举簇头时未能考虑到簇头的能量问题，而本文在选举簇头时则综合考虑了簇头能量和簇内能耗因素。同时UREC算法下的网络中总的节点存活个数也要明显多于LEACH和EEUC。这表明UREC能够有效均衡网络中节点的能耗，推迟了网络中首个节点死亡出现的时间。

图5是LEACH、EEUC和UREC三种算法下网络剩余能量关系对比图。在整个网络周期中，本文提出的UREC的网络剩余能量要大于LEACH和EEUC，这说明UREC在节省网络能耗，延长网络寿命方面要优于LEACH和EEUC。

图3 不同区间数下的网络生存时间

图4 网络存活节点个数与生命周期的关系

图5 网络剩余能量与生命周期的关系

4 小结

本文提出了一种基于不均等环带分区的能耗均衡路由算法UREC，该算法通过均衡各环带内的能耗负载来达到延长网络寿命的目的，同时在选择簇头时综合考虑到节点的剩余能量与簇内能耗最小等因素，保证了簇首选择的合理性，在同一扇形区域内构建簇间路由树，保证了源节点到基站的距离最短，有效提高了无线传感器网络的可靠性。