基于同构传感器网络的能量空洞避免策略*

龙胜春，卢定乾，池凯凯（浙江工业大学计算机科学与技术学院，杭州310023）



基于同构传感器网络的能量空洞避免策略*

龙胜春*，卢定乾，池凯凯
（浙江工业大学计算机科学与技术学院，杭州310023）

摘要：针对无线传感器网络中网络能量损耗不均匀的问题，提出了基于同构传感器网络的能量空洞避免策略。首先对原有的LEACH路由算法进行改进，得到均衡簇规模的BCS-L分簇算法；然后联合应用BCS-L算法与分环网络结构，以节点能耗均衡为目标，将能量空洞避免问题转化为求相邻环带的外半径的多项式问题，并通过最小化最内层环带节点的能量消耗得到最内层环带的半径，最后得到符合实际网络分布的局部最优解，即除最外层环带的其余环带节点能耗均衡。理论分析和实验结果表明，所提出的策略与传统分环网络相比，大幅地提高了网络寿命，较大地改善了网络的性能，是解决能量空洞问题的有效方案。

关键词：同构传感器网络；能耗均衡；BCS-L算法；环带

无线传感器网络由部署在检测区域内的大量微型、廉价、低功耗的传感器节点组成，这些节点可以是人工布置或用飞行器抛洒，不同的应用场景需要不同的散布方式。节点一旦布置，便通过自组织快速形成一个无线网络。节点既是信息的采集和发出者，也充当信息的路由者，采集到的数据通过多跳路由到达网关。网关（一些文献也称为Sink，以下统称Sink节点）是一个特殊节点，可以通过In⁃ternet、移动通信网络、卫星等与监控中心通信，也可以利用飞行器飞跃网络上空通过网关采集数据。

由于无线传感器网络初始部署的随机性，导致不同的检测区域具有不同的节点密度。当传感器节点进行数据转发时，由于节点通信半径较小，网络中的一部分节点不仅需要发送自身的感知数据，同时还需要为其邻居节点转发数据［1］。特别的，越靠近Sink的传感器节点，所需转发的数据量越大，频繁的数据转发必然会引起大量的能量消耗，因此，这类通信负载较重的传感器节点将在极短的时间内耗尽能量。当靠近Sink的传感器节点因能量耗尽而失效时，其所在区域将成为一个覆盖空洞，通常被称为“能量空洞”［2］现象。一旦发生“能量空洞”现象，网络连通性将遭到严重破坏，其他传感器节点采集的数据将无法传递到Sink节点［3］，整个网络不得不宣告“死亡”，但是此时网络中其他节点仍有大量的能量剩余。如何避免这种“能量空洞”现象，使得整个网络节点的负载平衡，从而延长整个网络的生命周期和提高网络性能，成为当前无线传感器网络研究的一个热点。

1　相关工作

当前解决能量空洞的方法主要是最大限度地均衡网络负载，大部分的研究［4-6］都集中在环状传感器网络，这是因为“能量空洞”现象中提前“死亡”的节点围绕在基站附近近似形成一个环形包围着基站节点，研究环状传感器网络更有利于解决能量空洞问题。

针对环状无线传感器网络的研究大致可以分为两类，一种是基于等环带宽度的异构传感器网络的研究，一种是基于不等环带宽度的同构传感器网络的研究。异构传感器网络通常是给近基站的环带分配更多的传感器节点或者给近基站的传感器节点分配更多的初始能量，以实现能量均衡的效果。

文献［4］提出了一种初始能量不均匀策略。作者假定节点均匀分布于一个矩形区域中，同时根据Sink节点的位置将区域划分为几个小区域，根据网络中不能再传输数据时节点的剩余能量来重新分布节点的初始能量。最终，距离Sink节点越近的节点，分配的初始能量越大。

文献［6］中设WSN中节点不均匀分布，从理论上推导出完全避免能量空洞问题的策略是不存在的，但除最外层之外的各个环带（ring）中节点的能量均衡是可以达成的，并提出了一种能量均衡的路由算法，可使得无线传感器网络所耗费的能量可以降低10%。

这种策略在理论上是可行的，但在布网时，特别是部署大型传感器网络时要专门为特定的区域布置大量的节点或一些初始能量较高的节点，这样就增大了工作难度，特别是在一些极端的环境下布网更为困难。另外，传感器节点的初始能量原本就是制约无线传感器网络发展的一个重要因素，因此这种策略在实际实施起来非常困难。

而同构传感器网络要求节点密度均匀，节点自身的参数都要保持一致，因此在布网时就比异构传感器网络简单的多，而且更加适用于大型传感器网络。而分簇网络由于具有更高的能量效率因而对其进行能量空洞避免的研究往往更具有意义。

LEACH算法［7］是最早提出的分簇路由协议，算法的基本思想是：以循环的方式随机选择簇头节点，将整个网络的能量负载平均分配到每个传感器节点中，从而达到降低网络能源消耗、提高网络整体生存时间的目的。LEACH算法的每轮循环大致包括以下几个阶段：①簇头的选举［8］；②簇的建立；③簇的路由。

LEACH算法簇头的选举过程是：每个节点产生一个0~1之间的随机数，如果这个数小于阈值T （n），则该节点向周围节点广播它是簇头的消息。T （n）的计算公式如下：

其中：p是簇头节点的百分比；r为当前轮数；G是最近1/p轮中未当选簇头的节点集合；mod是求模运算。

簇头节点选定后，广播自己成为簇头的消息，剩余节点根据收到消息的强弱决定加入哪个簇，并告知簇头，完成簇的建立过程。

本文结合LEACH算法，考虑到节点剩余能量，节点到簇头节点的距离等因素提出一种基于LEACH的改进型算法（BCS-L算法），并将此算法应用进环状网络，提出了一种基于环形传感器网络的能量空洞避免策略，来平衡整个网络中节点的能量消耗，最后通过控制各个环带的宽度，使各个环带中的节点的能量消耗最终达到均衡。

2　系统模型

2.1网络结构模型

本文对无线传感器网络做出如下假设：①半径为R的圆形无线传感器网络，节点均匀分布，且密度为ρ，Sink节点位于圆心位置，且具有较强的计算、存储能力，且无能量限制。②节点同构，即除Sink节点外所有的节点拥有相同的特性，如初始总能量Eini、通信半径等，节点可以获知自身的当前能量Er；③每个节点有唯一的ID，可获知自己的坐标信息，都能竞争为簇头或者普通节点；④节点通信功率可以调节，通过接收信号的强度计算出节点之间的距离；⑤在本文中通过增加采集数据的冗余度提高数据的准确性［9］，并通过数据融合压缩技术［10］减少数据传输任务。节点的感知半径一般不超过70 m（参照美国SG-Link®-LXRS无线节点），在密度为平均每平方米布置一个节点的无线传感器网络中，当节点采用较大的感知半径时会导致自身的能耗急剧增加。为了简化计算，本文采用的节点的感知半径为5.7 m，此时临近范围内节点采集到的数据重复率几近达到100倍，这样既能提高数据的准确性，同时也没有增大节点的自身能耗。

2.2能量消耗模型

本文采用典型能量消耗模型［11-12］，不计节点在计算、存储过程中的能量消耗，仅计算通信能耗。在传输l bit信息经过距离d的过程中，发送端能量消耗为：

接收端的能量消耗为：

其中，Eelec是指发送或接收每比特数据消耗的能量，后文中简写成Ee；Efsd2和Empd4是发送每比特数据放大器的能量消耗，d0为一阈值，本文定义为87.7 m，若发送节点与接收节点的距离小于d0，发送方的放大器能量消耗与距离的平方成正比，否则成4次方正比。由于一般布网是节点之间距离不会超过87.7 m，因此本文采用Efsd2作为发送每比特数据的放大器的能量消耗。在本文中，以上参数的具体设置参照文献［12］，见表1。

表1　仿真参数表

3　基于同构网络的能量空洞避免策略

本文定义在密度为ρ的圆形网络中，网络可以被分成n个同心环带，定义M1，M2，…，Mn为从内到外n层相邻同心圆环，环带Mk中节点的总数为Nk（k=1，2，3，…，n），环带外半径为rk（k=1，2，3，…，n），即rn=R。为方便计算令r0=0，表示Sink节点。

设环带Mk中的节点进行平均分簇，簇头节点的覆盖半径为（rk-rk-1）/2，每个簇头节点覆盖的面积为π［（rk-rk-1）/2］2，那么此圆环中应该部署的簇头节点个数Ck为：

此环中平均每个簇中的节点总数Ak（包括簇头节点）为：

因为在同一环带内相邻节点之间所采集的数据具有很大的相关性，因此在每个簇中，簇头对接收到的簇内数据进行融合压缩，减少网络传输的数据量，达到节约网络能量的目的。本文假设每个节点采集到l bit的数据，簇头的压缩率为α，即簇头接收到的Ak×l bit的数据，压缩为Ak×l×α bit数据，且压缩单位比特数据的能量消耗为EDA，根据以上能量消耗模型，可以得知第k环中的单个簇中的簇头接收簇内数据并压缩的能耗ECHK，见式（6）：

簇中非簇头节点的能耗ENCHK为：

其中dtoC表示普通节点到簇头节点的平均传输距离，本文取做簇头节点的覆盖半径。

3.1BCS-L算法

BCS-L（Balanced Cluster Scale-LEACH）算法是针对LEACH协议每轮循环的第一阶段和第二阶段进行改进。

在簇头的选举之前，环带中节点先判断自己的当前能量Er是否能满足作为簇头节点的能耗，即：当Er>ECHK时，该节点参加簇头的选举，否则不参加簇头节点的竞争。

在选择簇头时，将节点的剩余能量考虑进去，调整后的簇头阈值计算方法：

其中：T（n）k为环带Mk中的簇头阈值计算方法；p是簇头节点的百分比，在环带Mk中p=1/Ak；r为当前轮数；G是最近1/p轮中未当选簇头的节点集合；Er为节点自身的当前能量；Eini为节点的初始总能量。

改进后的阈值计算方法降低了当前能量较低的节点当选为簇头节点的几率，使得环带中节点的能量消耗更加均衡。

在环带Mk内，定义CHk为当选为簇头节点的个数，式（4）中Ck为应该部署的簇头节点个数，当CHkCk时，不做任何处理。

簇头节点选定后，簇的循环进入第二阶段：簇的建立。定义Thdis为簇中节点到簇头节点的距离阈值，且Thdis=rk-rk-1；Thcluster为平均每个簇中的节点个数的阈值且Thcluster=Ak，从而有如下算法：

算法：输入：簇头节点的个数（CHk）；节点i到簇头j的距离（DIST［i，j］），簇j中当前节点的个数（CLUSTER［j］）输出：选择簇头节点j加入①节点i向距离DIST［i，j］小于阈值Thdis的簇头节点j发送申请加入的信息；②簇头节点收到消息后判断此时自己簇中的节点个数（CLUSTER［j］）是否小于阈值Thcluster，若小于，则向节点j回复“YES”；否则回复“NO”；③节点i根据收到的信息，向回复了“YES”的簇头中离得最近的那个簇头发送“确认加入”的信息；至此节点i加入簇j中。

簇头节点广播自己成为簇头的消息，普通节点收到消息后，根据上述算法选择加入哪个簇，并告知相应的簇头，完成簇的建立过程。上述算法保证了簇中节点的个数不会超过Thcluster，有效避免了个别簇中节点数量过多导致的能量消耗不均衡的问题。

3.2基于同构网络的分环策略

下面计算环带Mk中的簇头节点处理外层簇头节点发送的消息的能量消耗ET，由于簇头与簇头之间进行数据传输时，不对收到的数据进行压缩，收到外层簇头的消息直接转发至下一跳（内层簇头节点），定义环带Mk中簇头接收到的总数据量为Rk（k=1，2，3，…，n-1）：

所需转发的总数据量为Tk（k=1，2，3，…，n）：

式（10）中Ck×Ak表示环带Mk中的节点总数。最外层的簇头节点只有发送数据，没有接收数据，故Rn=0，最外层簇头节点只需要将自己簇内的数据压缩后传递给环带Mk-1中的簇头节点，故Tn=Nnla，由式（9）和式（10）推导出：

其中Ni表示当i=k时环带Mk中的节点总数。

定义环带Mk内的平均每个簇头节点需要接收的外层数据为Rk（k=1，2，…，n-1），则：

所需发送的平均数据为Tk（1，2，…，n）：

为了简化模型，假设在环带Mk内的簇头节点到下一跳的传输距离等于环带的宽度dk，即：dk=rk

rk-1。定义Ek（l，dk）表示环带Mk内单个簇头节点在单位时间内平均消耗的能量，得到：

展开式（15），得到：

由于最外层环内的簇头节点只处理簇内数据，没有外层环的数据需要转发，因此环带Cn内簇头节点在单位时间内的平均能耗为：

由于大规模无线传感器网络自身的局限性，靠近基站的节点承担了更多的通信负载，消耗了更多的能量，在节点初始能量都相同的情况下，最内层的节点往往最快耗尽能量，并最终导致整个网络的死亡。因此最内层环带节点的生命周期决定了整个网络的生存周期，提高整个网络的生存时间的关键就是降低最内层环带M1内节点在单位时间的平均能耗。

环带M1中，无线通信半径为d1=r1，簇中普通节点的通信半径dtoC=r1/2，r0=0，由式（16）得到：

对式（18）求导得：

最后能够求出使得E1=（l，d1）最小的半径r1为：

结果显示，最内层环带M1的环带宽度不仅与网络半径R有关，还与网络中的节点密度ρ、数据压缩率α和Ee、Efs相关。由求得的r1代入式（18）可求出最内层环带M1内的单个节点在单位时间内的平均消耗的能量E1（l，d1）。

当簇头节点的能量消耗均衡时，其能量效率最高，因此有下式成立：

4　计算与实验结果

本文采用的传感器网络的节点密度为平均每平方米1个节点，在节点的平均感知半径为5.7 m的网络中，同一数据能同时被一百多个节点感知到，为减少这种重复率，定义平均每个节点所采集数据的1%为有效数据，然后对有效数据进行压缩，最后融合压缩率［9］为α=0.001，根据式（20）、式（21）和表1中各参数，可以推导出当无线传感器网络的网络半径为R取不同的值时，各个环带的环带宽度，如图1所示。

图1　各层环带宽度

如图1所示，当圆形网络的半径R固定时，假设节点单位时间产生的数据量为4 000 bit［8］，为使得各层环带的节点平均能耗均衡，环带的宽度由内到外是逐渐增大的，环带M1与环带M2的宽度相差较大，环带M2以上的环带宽度相差不大。图中每条折线的最后一个点都比较低是因为在对网络进行分环时，环带的外半径不能大于网络半径R。当网络半径R越来越大时，在能耗均衡的条件下各层环带的宽度普遍增大，整体变化趋势相似。

从图2可以看出，同一个网络中，不同环带内节点在单位时间内的节点平均能耗基本相同，最外层环带的节点平均能耗均比内层的能耗低，因此本文算法能够实现局部最优。

图2　环带内节点单位时间平均能耗

本文算法采用MATLAB 8.3仿真软件进行建模仿真，仿真的网络半径R=100 m。参考一节普通AA电池至少有1 000 J的能量，当采用电池给节点供电时，理论上节点的初始能量Eini=1 000 J。

图3　最内层环带网络寿命

图3显示本文算法所得到的分环网络和简单分环网络的网络寿命。简单分环网络工作方式如下：传感器节点在各个环带的密度按照从外环到内环呈几何级数递增的方式部署，即越靠近基站的环带布置的节点密度越大，通过增加内层环带节点的密度来降低靠近基站的节点的平均能量消耗。各个环带中的节点既要采集数据，又要接收相邻外层环带转发的数据，然后将所有数据通过最短路径路由算法转发给相邻内层环带，最终将数据汇聚到Sink节点。采用本文均衡网络算法时，最内层环带的节点耗尽所有能量大致需要平均2 133个单位时间；文献［6］中提出的基于环的能量均衡策略在一定程度上能将无线传感器网络的能耗降低10%左右，但是在本文的仿真中，最内层环带的节点在1 006个单位时间时就几乎耗尽能量，因此本文算法在寿命上几乎比单纯的分环网络提高接近一倍多。这是因为在本文的分环网络中，采用分簇算法，簇内数据压缩率为α=0.001，相比于没有分簇的网络，环带与环带之间传递的数据量仅占没有分簇网络的α倍，在很大程度上降低了网络中流通的数据量。

5　总结

无线传感器网络是近几年来兴起的研究热点，其中，无线传感器的能源效率和寿命问题成为人们最为关心的问题之一。

本文提出的基于同构传感器网络的能量空洞避免策略就是将分簇算法融入进环状网络，大量降低了网络中的数据流。本文算法能够根据网络半径和节点密度等参数实现除最外层的其余环带中节点能耗均衡的优化后的分环策略。经过理论分析和实验，结果表明了该策略的有效性。对比以往的研究，本文的创新点在于从网络效率均衡的角度出发，从而得出更适合实际的大型无线传感器网络的应用。进一步工作可以从节点自供能等方面研究解决网络能量空洞问题的策略和机制。

参考文献：

［1］Akyildiz I F，Su W，Sankarasubramaniam Y，et al. Wireless Sen⁃sor Networks：A Survey［J］. Computer Networks，2002，38（4）：393-422.

［2］吴小兵，陈贵海.无线传感器网络中节点非均匀分布的能量空洞问题［J］.计算机学报，2008，31（2）：253-261.

［3］王亮，钟先信，石军锋.无线传感器网络能耗平衡策略的研究［J］.传感器世界，2007（3）：32-36.

［4］Lian J，Chen L，Naik K，et al. Modeling and Enbancing the Data Capacity of Wireless Sensor Networks［C］// Phoha S，La Porta T F，Griffin C，et al. IEEE Monograph on Sensor Network Opera⁃ tions. IEEE Press，2004：91-138.

［5］Li J，Mohapatra P. An Analytical Model for the Energy Hole Prob⁃lem in Many-to-One Sensor Networks［C］//Proceedings of IEEE Vehicular Technology Conference Dallas，TX，2005：2721-2725.

［6］Wu X B，Chen G H，Das S K. Avoiding Energy Holes in Wireless Sensor Networks with Non-Uniform Node Distribution［J］// IEEE Transactions on Parallel and Distributed Systems，2008，19（5）：710-720.

［7］陈晓娟，王卓，吴洁.一种基于LEACH的改进WSN路由算法［J］.传感技术学报，2013，26（1）：116-121.

［8］Raju Pal，Ajay K Sharma. FSEP-E：Enhanced Stable Election Pro⁃tocol Based on Fuzzy Logic for Cluster Head Selection in WSNs ［C］//6th International Conference on Contemporary Computing （IC3），2013：427-432.

［9］Diane I，Kacimi R，Mammeri Z，et al. Energy Optimization Based on the Redundancy in WSNs［C］//Wireless and Mobile Network⁃ing Conference（WMNC），2013：1-7.

［10］张美燕，蔡文郁.基于K均值分簇MST路由的无线传感网压缩采样技术［J］.传感技术学报，2015，28（9）：1402-1407.

［11］Ali D，Majid G，Carey W. On the Optimal Randomized Clustering in Distributed Sensor Networks［J］. Computer Networks，2014 （59）：17-32.

［12］Bo- Chao Cheng，His- Hsun Yeh，Ping- Hai Hsu. Schedulability Analysis for Hard Network Lifetime Wireless Sensor Networks with High Energy First Clustering［J］. IEEE Transactions on Reli⁃ability，2011，60（3）：675-688.

龙胜春（1970-），女，副教授，硕士生导师，主要研究方向是无线传感器网络、医学图像处理等，longsc@zjut.edu.cn；

卢定乾（1990-），男，硕士研究生，主要研究方向是无线传感器网络。

Detection of Coverage Hole in WSN Based on Three-Dimensional Terrain Correction*

SHEN Xianhao*，LI Jun，NAI He
（College of Information Science and Engineering，Guilin University of Technology，Guilin Guangxi 541004，China）

Abstract：Due to the characteristic of undulating terrain，it will produce the coverage holes after randomly deploy⁃ing sensor nodes under the three-dimensional terrain. In order to effectively detect the coverage holes，in this paper，we propose a detection method of coverage holes in wireless sensor networks（WSN）based on three-dimensional ter⁃rain correction. Through establishing the unit ball perception model，randomly deploying the sensor nodes，Delau⁃nay triangulation the sensor nodes. Calculating the circumcircle of the triangle，obtaining coverage holes boundaries based on boundary detection algorithm and eliminating false boundary node，then we obtain the improved boundary. We calculate the information of slope and aspect of sensor nodes. According to the principles of the terrain correc⁃tion，calculate the actual detection radius；Ultimately obtain a minimum boundary of coverage holes. Simulation re⁃sults show that the detection method can effectively detect coverage holes under the three-dimensional terrain. For the undulating obviously terrain，it also has some adaptability.

Key words：coverage holes；three-dimensional terrain correction；slope and aspect；Delaunay triangulation；circum⁃circle

doi：EEACC：6150P10.3969/j.issn.1004-1699.2016.01.019

收稿日期：2015-07-29修改日期：2015-10-26

中图分类号：TP393

文献标识码：A

文章编号：1004-1699（2016）01-0103-06

项目来源：国家自然科学基金项目（61472367）