基于环分块的能耗均衡分簇路由算法

汪汉新 洪思琴

摘 要：针对无线传感器网络（WSN）中节点能耗不均衡和能量效率低而影响网络生命周期的问题，提出了基于环分块的能耗均衡分簇路由算法（EBCR-RP）。首先，计算网络能耗最低的单跳距离，并将其作为环间距;然后，优化每环的簇数目，并对每环进行均匀分块，且在每块中选取能量最高的节点担任簇头，以均衡网络能耗;最后，设计传输代价函数，搜索簇头和汇聚节点之间数据的最佳传输路径，以提高网络能量效率。仿真结果表明，EBCR-RP与模糊理论簇形成协议（FLCFP）和改进的非均匀分簇路由（IUCR）算法相比，网络的生命周期分别延长了51.4%和8.6%。EBCR-RP能够有效地延长网络生命周期，均衡网络能耗，提高能量效率。

关键词：无线传感器网络;能耗均衡;分簇路由;环分块;最佳路径

中图分类号： TP393.04

文献标志码：A

Abstract： A novel Energy-Balanced Clustering Routing algorithm based on Ring Partition （EBCR-RP） was proposed to solve the network lifetime problem of unbalanced energy consumption and low energy efficiency in Wireless Sensor Network （WSN）. Firstly， the one-hop distance with minimize energy consumption was calculated and regarded as ring spacing. Secondly， the number of clusters was optimized and each ring was partitioned uniformly， and the node with highest energy in each block was chosen as cluster header to balance energy consumption. Finally， a cost function was designed to search optimal data transform path to improve energy efficiency. The simulation results show that network lifetime of EBCR-RP is increased by 51.4% and 8.6% compared with Fuzzy Logic Cluster Formation Protocol （FLCFP） and Improved Uneven Clustering Routing （IUCR） algorithms. EBCR-RP can effectively prolong network lifetime， balance energy consumption and improve energy efficiency.

Key words： Wireless Sensor Network （WSN）; energy balance; clustering routing; ring partition; optimal path

0 引言

无线传感器网络（Wireless Sensor Network， WSN）是由大量的传感器节点以无线通信方式组成的一个多跳自组织网络，其主要功能是对指定区域进行监测获取数据，具有自组织、快速展开、动态拓扑等特点，在物联网中有着广泛的用途[1-2]。WSN中的传感器节点一般由电池供电，应用场景比较恶劣，不能及时进行能量补给，因此设计能量高效的路由协议是WSN中研究的重要方面[3]。在无线传感器网络路由协议中，分簇路由算法相比平面路由算法具有更好的节能性，成为近年来研究的热点[4]。

低能耗自适应集簇分层（Low Energy Adaptive Clustering Hierarchy， LEACH）算法[5]是最早被提出的分簇路由算法，之后很多学者对其进行了深入的研究。文献[6]中提出了分布式节能分簇（Distributed Energy-Efficient Clustering， DEEC）算法，在选取簇头时综合考虑了节点的初始能量和剩余能量，能量越高的节点被选为簇头的概率越大。文献[7]中提出了模糊理论簇形成协议（Fuzzy Logic Cluster Formation Protocol， FLCFP），采用模糊理论优化，综合考虑节点剩余能量、与汇聚节点的距离、与邻居节点的距离等因素来选取簇头。虽然这类算法在簇头选取阶段有效地均衡了节点能耗，但在选取簇头时随机性很大，容易造成簇头分布不均匀、簇头数目不固定的问题。文献[8]采用K-means方法对监控区域的节点进行均匀分簇，且选取每个簇中最靠近几何中心的节点担任簇头，以解决簇头分布不均匀的问题。文献[9]中提出了间歇的簇头选择（Intermittent Cluster Head Selection， ICHS）算法，设置了一种新的概率公式来选取簇头，能够选出指定数目的簇头，以解决簇头数目不固定的问题;然而这些算法中簇头直接与汇聚节点通信，当两者的距离较大时，数据传输能耗很大，因此这类算法不适用于大规模的无线传感器网络。文献[10]中提出了多跳的低能耗自适应集簇分层（Multiple-Hop Low Energy Adaptive Clustering Hierarchy， MH-LEACH）算法，该算法中簇头不直接将数据传输给汇聚节点，而是通过中间节点进行信息的转发。虽然MH-LEACH在很大程度上降低了网络能耗，但靠近汇聚节点的簇头需要转发大量数据，会导致网络中能耗不均衡，产生热区问题。文献[11]中提出了能量高效的非均匀分簇（Energy-Efficient Uneven Clustering， EEUC）算法，利用非均匀分簇解决多跳模式下簇头能耗不均衡的问题，但是该算法没有考虑节点的剩余能量、节点到汇聚节点的距离等因素。针对该问题，文献[12]中提出改进的非均匀分簇路由（Improved Uneven Clustering Routing， IUCR）算法，在簇头竞争阶段综合考虑节点的剩余能量、节点到汇聚节点的距离、邻居节点的数目以及能量消耗速度，并在非均勻分簇时引入竞争半径的概念;然而计算竞争半径需要考虑节点到汇聚节点之间的最大和最小距离值，当网络规模较大时，汇聚节点无法直接得到全局最大和最小值，导致簇建立阶段能耗很大，且建立多跳路由时，没有搜索传输代价最小的路径，能量利用率较低。

本文针对网络能耗不均衡、能量效率低的问题，提出了基于环分块的能耗均衡分簇路由算法（Energy-Balanced Clustering Routing algorithm based on Ring Partition， EBCR-RP）。EBCR-RP计算了最佳单跳距离，通过均衡簇头的能耗来均衡网络能耗;不采用传统的概率公式选取簇头的方式，避免了簇头分布不均匀和簇头数目不固定的问题;构建代价函数以寻找最佳数据传输路径，降低通信能耗，提高能量效率。实验结果表明，与FLCFP和IUCR算法相比，EBCR-RP能够有效延长网络生命周期，均衡网络能耗，提高能量效率，改善网络的性能。

1 系统模型

1.1 网络模型

网络模型如图1所示，N个节点均匀部署在半径为R的圆形监测区域内，汇聚节点位于监测区域的中心;所有节点和汇聚节点部署后都是静止的，能够根据接收节点的距离来自动调整发射功率;监测区域内所有的节点同构，且每个节点都具有唯一的ID，节点的初始能量相同;监测区域划分为等间距的同心圆环，且每环被均匀地划分为若干个区块，汇聚节点所在的环为第0环，由汇聚节点向外的环依次编号为1，2，…，M。

图1中灰色区域为直传区[13]，该区域内的节点不进行分簇，直接将采集到的信息传输给汇聚节点，可以减少分簇、簇内通信及数据融合等能耗，改善“热区”问题。

1.2 能耗模型

采用经典的无线电能耗模型[14-15]，发送节点向相距为d的目标节点传输mbit数据的能耗由发射电路和功率放大电路能耗组成：

接收节点接收mbit数据能耗为：

簇头对mbit的数据进行融合的能耗为：

其中：Eelec表示发送单位比特数据的能耗;εfs表示自由空间模式下单位比特的数据能耗;εamp表示多径衰减模式下单位比特的数据能耗。d0=εfs/εamp是划分空间模型的临界值，称为通信半径：当发送距离小于临界值d0时，采用自由空间模式，发射功率呈d2衰减;当发送距离大于或等于临界值d0时，采用多径衰减模式，发射功率呈d4衰减。EDA表示融合单位比特数据的能耗。

2 算法描述

为了均衡整个网络的能耗、提高能量效率、延长网络的生命周期，设计了一种基于环分块的能耗均衡分簇路由算法（EBCR-RP）。EBCR-RP首先计算多跳通信中使网络能耗最低的单跳距离，并将该距离作为环间距，对WSN的监控区域进行分环处理，汇聚节点所在的环为直传区，该区域节点不进行分簇，而是直接将信息传输给汇聚节点;其次，通过让直传区外的簇头的能耗相等，计算出各环簇数目，并根据簇数目对每环进行均匀分块;然后，在每个区块中选取能量最高的节点来担任簇头，普通节点选择离自身较近的簇头成簇;最后，在数据传输阶段，设计考虑传输距离、剩余能量和到汇聚节点距离的传输代价函数，寻找传输代价最小的数据传输路径。

EBCR-RP通过簇头的能耗均衡优化各环簇数目，能够在非均匀分簇的基础上，使网络能耗更加均衡;使用传统的概率公式选取簇头的方式时，簇头数目不固定且簇头随机分布，容易出现簇头集聚的现象，导致网络能耗不均衡，影响网络的生命周期。为了避免该问题，EBCR-RP将每环均匀分区，并在每个区块中选取一个节点担任簇头，进一步均衡了网络能耗;计算最佳单跳距离，且在数据传输阶段设计传输代价函数，寻找传输代价最小的数据传输路径，能够有效地降低网络能耗，提高能量效率，改善网络负载。

2.1 环间距的计算

监控区域首先被划分为等间距的同心圆环。在多跳通信中，求得网络能耗最低的单跳距离，然后将该距离作为同心圆环的环间距。

如图2所示，第M环的节点通过多跳将mbit数据传输给第0环的节点，设每一跳的距离为dr。节点能耗由接收数据、融合数据和转发数据的能耗组成：

其中：Esd表示发送数据的能耗;Erv表示接收数据的能耗;Eag表示融合数据的能耗。

整个传输过程的总能耗为：

为了求得使总能耗最低的单跳距离dopt，将总能耗对dr求导，得到最优单跳距离为：

本文将所求得的dopt作为同心圆环的环间距，对监控区域进行分环处理，汇聚节点所在的环为直传区。

2.2 环分块原则

在多跳通信中，簇头除了簇内通信外，还要融合和转发簇间数据，越靠近汇聚节点的簇头需要转发的数据越多，能耗越大，这样会导致网络中能耗不均衡，产生“热区”问题。为了解决该问题，本文对直传区以外的每环进行均匀分块，且在每个区块中选取一个节点来担任簇头，通过优化每环的簇数目，即每环的区块数目，来均衡网络能耗。由于簇头的能耗远遠大于普通节点的能耗，因此均衡网络能耗可以体现在均衡各环簇头的能耗上，算法通过让每环簇头的能耗相等，来计算出每环的簇数目，因而得到每环的区块数目。

由网络模型可知，监控区域划分为M+1个环，区域半径R=（M+1）dopt，则可求得整个区域的环数M。假设每环的簇头均匀分布，ki表示第i环的簇头数目，由于传感器节点在监控区域是均匀分布的，则第i环的节点数目Ni为：

其中：λ1，λ2，…，λm-1为比例因子，当各环簇头数目的选取比例遵循式（15），就可保证每环簇头的能耗相等，这样就保证了整个网络的能耗均衡。各环簇的数目确定后，各环区块的数目也就确定了，然后对每环进行均匀分区，并在每个区块内选取能量最高的节点担任簇头，避免簇头集聚的问题。

2.3 代价函数的设计

在分簇路由算法中，数据传输阶段的能耗很大，因此寻找传输代价较小的路径十分重要，据此本文设计了一个传输代价函数，在汇聚节点和簇头所组成的有向图中搜索最佳的数据传输路径，以提高网络能量效率。该函数综合考虑了三个因素：1）簇头将采集的数据由外环向内环传输;2）选择剩余能量高的簇头作为中继节点;3）选择离自身较近的相邻内环簇头作为中继节点。

其中： j是i的中继节点;Ej_residual为簇头j的剩余能量;Eint为簇头j的初始能量;Dist（j，sink）表示簇头j到汇聚节点的距离;Dist（i， j）表示簇头i和簇头j之间的距离;d0表示通信半径;α、 β、γ为加权因子。簇头j可能在簇头i的相邻外环，也可能在相邻内环，若簇头j在相邻外环，则Dist（j，sink）较大，传输代价较大，则j不作为i的中继节点。如果簇头j的剩余能量较高、与节点i的距离较近且距离汇聚节点也较近，那么传输代价较小，传输能耗较低，从而有效提高网络的能量效率。

为了搜索数据传输代价最小的路径，对簇头进行编号{1，2，…，n}，汇聚节点编号为0，构成有向图的顶点，通过式（16）可计算有向图每个顶点的边集，如式（17）所示：

其中G为代价函数矩阵，通过G可以知道任意两点间的传输代价。

在构造好代价函数矩阵后，搜索每个簇头到汇聚节点代价最小的数据传输路径，其主要思想是：以汇聚节点为源点，通过搜索算法寻找其到各个簇头的代价最小路径，并将该路径记录下来，由于该搜索方式是反向搜索，所以目标节点到源点的路径还需要进行出栈操作。搜索算法的具体过程：所有顶点分为已知最短路径的顶点集合P和未知最短路径的顶点集合Q，初始时，集合P中只有源点S（汇聚节点）一个顶点，设置源点到自己的最短路径为0，即dis=0;在集合Q的所有顶点中，选择一个离源点S最近的顶点u（簇头）（即dis[u]最小，dis[u]表示顶点u到源点S的直接距离）加入到集合P中，然后观察以u为起点的边，对每一条边进行松弛操作（例如：存在一条从顶点u到顶点v的边，e[u][v]表示这条边的长度，如果d[u]+e[u][v]

搜索算法的伪代码如下：

其中，path记录的下一跳节点是倒序的，因此寻找簇头到汇聚节点的路径时还需要作出栈操作。通过这个搜索过程，就能够找到每个簇头到汇聚节点传输代价最小的路径，然后通过该路径进行数据传输。

2.4 算法复杂度分析

EBCR-RP的时间开销主要包括路由选择和簇头选择两个阶段。在路由选择阶段，集合P中节点数为m，集合Q中节点数为n，并且m

3 实验仿真及分析

为了验证EBCR-RP能够提高网络的性能，本文在Matlab R2017a仿真平台下，对EBCR-RP、FLCFP和IUCR算法进行了对比，仿真环境参数设置如表1所示，选取1%的节点担任簇头。

3.1 衡量指标

本文从网络生命周期、能耗均衡性和网络能量效率这三个方面来衡量网络的性能。一般认为网络中50%节点死亡时，网络生命周期结束，所以将网络中50%节点死亡时的轮数作为网络的生命周期;设第一个节点死亡到最后一个节点死亡经历的时间作为时间跨度，那么时间跨度大小代表了节点能量消耗的均衡度;网络能量效率通过网络能量消耗速率判断。

3.2 网络的生命周期

网络的生命周期是衡量一个网络性能的重要指标，对三种算法的网络生命周期仿真结果如图3所示。从图3中可以看出，本文的EBCR-RP能有效地延长网络的生命周期。FLCFP网络生命周期为839轮，EBCR-RP网络生命周期为1271轮，比FLCFP提高了51.4%。虽然FLCFP采用模糊理论优化，综合考虑节点剩余能量、与汇聚节点的距离、与邻居节点的距离等因素来选取簇头;但是该算法中簇头直接将数据传输给汇聚节点，当网络模型较大时网络能耗很大。IUCR算法网络生命周期为1170轮，EBCR-RP比IUCR算法提高了8.6%。这是因为本文计算了最优单跳距离，并采用了更有效的路由策略来寻找能耗更小的数据传输路径，所以降低了网络能耗，延长了网络生命周期。

同时从图3中还可以看出，EBCR-RP的时间跨度最小，IUCR算法其次，FLCFP最大，这说明本文EBCR-RP的能耗更加均衡。这是因为FLCFP没有考虑整个网络能耗均衡性，IUCR算法采用非均匀分簇和簇间多跳机制来均衡网络的能耗;而本文EBCR-RP通过优化各环的簇数目以均衡网络能耗，在非均匀分簇的基礎上使能耗更加均衡，并对网络进行分块，在每个区块内选取一个节点担任簇头，避免了簇头集聚问题，进一步均衡了网络能耗。

3.3 网络的剩余能量

通过网络的剩余能量曲线来对比算法的能量效率，仿真结果如图4所示。网络的初始能量相同，从三种算法的剩余能量斜率来看，FLCFP>IUCR>本文EBCR-RP，剩余能量曲线斜率代表网络能耗的高低，这表明EBCR-RP优化了网络负载，提高了网络能量效率。这是因为，EBCR-RP通过计算最优单跳距离降低了整个能耗，同时寻找能耗小的最佳数据传输路径，有效降低了网络能耗，优化了网络的负载，提高了网络能量效率。

4 结语

针对无线传感器网络设计中能耗不均衡和能量效率低的问题，本文设计了一种基于环分块的能耗均衡分簇路由算法（EBCR-RP）。EBCR-RP计算了最佳单跳距离，均衡了簇头的能耗，且不采用传统的概率公式选取簇头的方式，避免了簇头数目不固定和簇头集聚的问题，同时设计传输代价函数来构建最佳传输路径以降低能耗。实验结果表明EBCR-RP的网络性能得到了改善。本文算法只考虑了网络能耗，并未考虑网络时延问题，下一步将对如何降低网络时延展开深入研究。

参考文献 （References）

[1] RAWAT P， SINGH K D， CHAOUCHI H， et al. Wireless sensor networks： a survey on recent developments and potential synergies[J]. Journal of Supercomputing， 2014， 68（1）：1-48.

[2] 王冠，王瑞尧.基于簇头优化的自供能无线传感网络路由算法[J].计算机应用，2018，38（6）：1721-1725.（WANG G， WANG R Y. Routing algorithm based on cluster-head optimization for self-energized wireless sensor network[J]. Journal of Computer Applications， 2018， 38（6）：1721-1725.）

[3] USMAN M， HAR D， KOO I. Energy-efficient infrastructure sensor network for Ad Hoc cognitive radio network[J]. IEEE Sensors Journal， 2015， 16（8）：2775-2787.

[4] WARRIER M M， KUMAR A. Energy efficient routing in wireless sensor networks： a survey[C]// Proceedings of the 2016 International Conference on Wireless Communications， Signal Processing and Network. Piscataway， NJ： IEEE， 2016：1987-1992.

[5] HEINZELMAN W B， CHANDRAKASAN A P， BALAKRISHNAN H. An application specific protocol architecture for wireless microsensor networks [J]. IEEE Transactions on Wireless Communications， 2002， 1（4）：660-670.

[6] QING L， ZHU Q， WANG M. Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks[J]. Computer Communications， 2006， 29（12）：2230-2237.

[7] MHEMED R， ASLAM N， PHILLIPS W， et al. An energy efficient fuzzy logic cluster formation protocol in wireless sensor networks [J]. Procedia Computer Science， 2012， 10（1）：255-262.

[8] PARK G Y， KIM H， JEONG H W， et al. A novel cluster head selection method based on k-means algorithm for energy efficient wireless sensor network[C]// Proceedings of the 2013 International Conference on Advanced Information Networking and Applications Workshops. Piscataway， NJ： IEEE， 2013：910-915.

[9] FAWZY A E， AMER A， SHOKAIR M， et al. Proposed intermittent cluster head selection scheme for efficient energy consumption in WSNs[C]// Proceedings of the 2017 Radio Science Conference. Piscataway， NJ： IEEE， 2017： 275-283.

[10] LEI Y， SHANG F J， LONG Z， et al. An energy efficient multiple-hop routing protocol for wireless sensor networks[C]// Proceedings of the 2018 International Conference on Intelligent Networks and Intelligent Systems. Piscataway， NJ： IEEE， 2008：147-150.

[11] 李成法，陳贵海，叶懋，等.一种基于非均匀分簇的无线传感器网络路由协议[J].计算机学报，2007，30（1）：27-36.（LI C F， CHEN G H， YE M， et al. An uneven cluster based routing protocol for wireless sensor networks[J]. Chinese Journal of Computers， 2007， 30（1）：27-36.）

[12] 王磊，谢弯弯，刘志中，等.非均匀分簇路由协议改进算法[J].计算机科学，2017，44（2）：152-156.（WANG L， XIE W W， LIU Z Z， et al. Improved algorithm for uneven clustering routing[J]. Computer Science， 2017， 44（2）：152-156.）

[13] TANESSAKULWATTANA S， PORNAVALAI C， CHAKRABORTY G. Adaptive multi-hop routing for wireless sensor networks[C]// Proceedings of the 2013 International Joint Conference on Computer Science and Software Engineering. Piscataway， NJ： IEEE， 2013：105-110.

[14] JANG S， KIM H Y， KIM N U， et al. Energy-efficient clustering scheme with concentric hierarchy[C]// Proceedings of the 2012 Radio Frequency and Microwave Conference. Piscataway， NJ： IEEE， 2012：79-82.

[15] HUYNH T T， DINH-DUC A V， TRAN C H. Delay-constrained energy-efficient cluster-based multi-hop routing in wireless sensor networks[J]. Journal of Communications & Networks， 2016， 18（4）：580-588.