基于不等簇半径分簇的无线传感器网络能量空洞避免
杨宛楠，陈志刚，赵明
(中南大学 信息科学与工程学院，湖南 长沙，410083)
摘要：基于无线传感器网络特性，提出一种不等簇半径非均匀分簇策略，根据各节点至Sink的距离，由近至远依次采用等比递增的不等簇半径进行分簇。并从理论上证明该策略可有效地均衡无线传感器网络的能量消耗。实验结果表明：距离Sink较近的节点，采用较小的簇半径成簇，使得簇头节点可保留更多能量进行簇间数据转发；距离Sink较远的节点，采用较大的簇半径成簇，使得簇头节点可保留更多能量覆盖更大范围的节点进行簇内数据收集，从而使得整个网络的负载比簇半径恒定的分簇网络更加均衡。
关键词：无线传感器网络；能量空洞；不等簇半径；分簇
中图分类号：TP393 文献标志码：A 文章编号：1672-7207(2014)04-1137-06
Energy hole avoid by clustering with unequal cluster-radius in wireless sensor networks
YANG Wannan, CHEN Zhigang, ZHAO Ming
(School of Information Science and Engineering, Central South University, Changsha 410083, China)
Abstract: Based on the characteristics of wireless sensor networks, clustering with unequal cluster-radius was proposed. It is proved that according to the distance between sensors and the Sink from near to far, clustering with geometric increments cluster-radius can effectively balance the network energy consumption. Sensors near the Sink should be clustered with a smaller cluster-radius, which makes the headers of the cluster save more energy to relay data from outer headers. Sensors far from the Sink should be clustered with a bigger cluster-radius, and then the headers of the cluster can save more energies to cover more sensors, and thus can collect more data in the cluster. Consequently the whole network load can be more balanced than the network clustered with fixed cluster-radius.
Key words: wireless sensor networks; energy hole; inequality cluster- radius; clustering
在无线传感器网络中，由于数据是基于多对一(many-to-one)的多跳路由通信模型进行中继和转发的，节点既产生数据也转发数据[1]，网络中通常存在能量消耗不均衡的现象，靠近Sink的节点由于要转发更多的外层数据而过早地耗尽能量死亡，死亡节点附近的节点因此需要中继已死亡节点的数据转发任务，从而进一步加快这一区域其他节点的死亡速度，形成漏斗效应(funneling effect)[2]，使得外层其他节点的数据不能传送到Sink，导致整个网络过早死亡或陷于瘫痪，缩短了网络寿命。这一现象被称为无线传感器网络的能量空洞问题(Energy Hole Problem)[3-6]。有关研究表明，能量空洞形成后，网络中的剩余能量高达90%[7]。因此，如何均衡网络负载，延长网络寿命，提高网络的能量利用率，具有重要的应用前景与实际价值。国内外研究人员己经提出许多有效的无线传感器网络的能量空洞避免方法[2-5]。吴小兵等[8]论述了离Sink不同距离处的节点密度比例关系，Lian等[9]通过在Sink附近区域部署初始能量更大的节点来避免能量空洞。曾志文等[10]给出在满足应用延迟前提下使网络寿命最长的节点发射功率选择算法。Wang等[11]使用一个移动中继节点来延长网络生存周期。Luo等[12]证明若采用移动Sink方式，Sink沿网络边缘移动最符合节能要求。Soro等[13]首次运用非均匀分簇思想来解决能量空洞问题，证明非均匀分簇算法[13-14]能够起到使网络能量消耗均匀，延长网络寿命的作用。Soro等[13]的研究思想主要为通过减少靠近Sink节点的簇成员数目，来降低簇内数据收集能耗，从而预留更多的能量进行簇间的数据转发，但各簇头为超级节点，且位置是事先计算好的，无法动态建簇，适应性较弱。本文在其研究基础上，从理论分析出发，提出基于递增簇半径的非均匀动态分簇策略，有效解决了距离Sink不同距离的簇头簇内通信与簇间通信能量消耗不平衡的问题，均衡了网络负载，延长了网络寿命。
1 网络模型
1.1 网络结构模型
N个传感器节点以密度ρ随机均匀分布在1个半径为R的圆形监测区域中，Sink位于圆心，对各节点进行非均匀分簇，形成周期性的数据收集分簇网络。从内向外，相邻的簇半径等比递增，处于同一层中的各簇簇半径相等，如图1所示。用Ci表示位于第i层的簇，各簇簇头居于簇中心位置，Ri表示第i层圆环外边界至Sink的距离(同时也是第i+1层圆环内边界至Sink的距离)，di表示Ci的簇头至Sink的距离，τi为Ci的簇半径。图1中阴影部分所示即为处于第3层的1个簇C3。节点可以调整其发射功率以降低能量消耗，例如，Berkeley Motes节点具有100个发射功率等级[14]。
图1 网络结构模型
Fig. 1 Network model structure
每一轮生命周期由Sink广播建簇信息开始，各节点成簇后通过单跳通信向簇头发送数据，各簇头负责簇内数据收集以及簇外数据转发，通过多跳通信将数据发送至Sink，当全部数据均转发至Sink后，即1次全局数据收集完成，各簇解散，1轮生命周期结束。
1.2 网络能耗模型
采用典型的能量消耗模型[8]，发送数据的能量消耗公式如式(1)所示，接收数据的能量消耗公式如式(2)所示。
(1)
ER(l)=lEelec (2)
式中：Eelec表示发射电路损耗的能量，若传输距离小于阈值do，功率放大损耗采用自由空间模型，当传输距离大于等于阈值do时，采用多路径衰减模型；εfs和εamp分别为这2种模型中功率放大所需的能量。ER(l)为节点接收l bit的数据消耗的能量。在本文中，以上参数的具体设置取自文献[15]，如表1所示。
网络中Sink没有能量限制。每个节点具有相同的初始能量，在1轮生存周期中产生并向簇头发送1 bit数据。处于非最外层的簇(Ci|i≠R)需向Sink转发自身以及来自外层簇(Cj|(i+1)≤j≤R)的数据。以图1中的C3为例，C3的簇头除承担簇内节点的数据收集与转发任务外，还承担由射线OC与射线OD所确定的扇形区域外层簇的数据转发任务。
表1 网络参数
Table 1 Network parameters
2 不等簇半径分簇策略理论分析
本节从能量的角度对在无线传感器网络中采用基于不等簇半径分簇的策略进行理论分析，证明根据各节点至Sink距离的由近至远，采用依次等比递增的不等簇半径进行分簇，实现整个网络负载均衡，缓解能量空洞问题是可能的。
2.1 能耗分析
用Ni表示簇Ci中传感器节点的数目；Ei表示簇Ci中簇头在1轮生命周期中的能耗，簇Ci中簇头发送1 bit数据消耗能量ei1，接收1比特数据消耗能量ei2；假设各簇中数据由簇头收集后，能够经过1跳传递给相邻的内层簇，最终经过i跳后到达Sink。
定理1：簇Ci中的簇头在每一轮生命周期中，消耗的能量为
，1≤i≤R (3)
证明：处于最外层的簇CR仅对簇内数据进行收集与转发，没有外层簇间数据的转发任务，所以，簇CR在1轮生命周期中簇头的能量消耗为
ER=NRleR2+NRleR1 (4)
其他处于非最外层的簇既要对簇内数据进行收集和转发，还要对来自外层的簇间数据进行收集和转发。所以，在1轮生命周期中，次外层簇CR-1中的簇头能量消耗为
ER-1=NR-1le(R-1)2+NR-1le(R-1)1+NRle(R-1)2+NRle(R-1)1=
(5)
在1轮生命周期中，簇CR-2中的簇头能量消耗为
(6)
由以上2式可得：在1轮生命周期中，非最外层簇Ci中的簇头能量消耗为
，1≤i≤R-1 (7)
经验证，ER也符合上式，所以簇Ci中的簇头在1轮生命周期中的能量消耗为
，1≤i≤R (8)
证毕。
2.2 分簇策略理论分析
定理2：当各簇簇头能量消耗均衡时，各层外边界至Sink的距离满足不等式：
Ri-Ri-2＜Ri+1-Ri-1，3≤i≤R-1 (9)
证明：各簇簇头能量消耗均衡，即Ei=Ei-1。
将式(3)带入上式，得
(10)
又因为
(11)
(12)
由式(2)，可得
ei2=e(i+1)2=Eelec (13)
将式(11)~(13)带入式(10)，可得
(14)
即为
(15)
所以，
ei1＜ei(l+1) (16)
由式(1)，可得：
(17)
将上带入式(16)，可得：
(18)
无论d＜d0还是d≥d0，化简后均为
Ri-Ri-2＜Ri+1-Ri-1，3≤i≤R-1 (19)
证毕。
定理3：当各簇所在圆环的外边界至Sink的距离与内边界至Sink的距离以等比q(q＞1)递增时，满足各簇簇头能量消耗均衡条件。
证明：由命题知
Ri=qRi-1 (20)
将式(20)带入式(9)，可得：
q2Ri-2-Ri-2＜q2Ri-1-Ri-1，3≤i≤R-1 (21)
化简，可得：Ri-2＜Ri-1。
上式显然成立，证毕。
定理4：当内层簇与相邻外层簇的簇半径以等比q(q＞1)递增时，满足各簇簇头能量消耗均衡条件。
证明：各层簇半径τi为：
，2≤i≤R。
所以，
。
根据定理3，可得
证毕。
由定理4可知，采用内层簇与相邻外层簇的簇半径以等比递增的策略进行分簇，可达到各层簇头能耗平衡，避免网络空洞问题。
3 仿真结果与分析
基于OMNet++4.1对理论分析结论进行实验场景仿真，并选用经典的固定簇半径分簇的LEACH算法进行仿真结果对比。
将1 000个节点均匀分布在半径为400 m的圆形网络中，LEACH算法采用固定的簇半径50 m成簇；本文的能量空洞避免算法称为UCR算法，采用初始簇半径为50 m，从Sink至最外层相邻层之间的簇半径以2.5为系数等比递增成簇。其他参数设置参如表1所示。
实验场景的每轮生命周期分为簇内数据收集和簇间数据转发2个阶段。在簇内收据收集阶段，2种算法分别按各自策略成簇，簇内采用TDMA协议对其覆盖范围内的节点进行数据收集。在簇间数据转发阶段，各簇头采用CDMA协议进行数据传输，将自己簇内数据以及外层簇间数据转发至内层临近簇头。
当网络中出现有簇头在临近内层中无法找到中继簇头完成数据转发时，此时网络分离，宣告网络死亡。
3.1 节点死亡时间与网络寿命分析
2种策略下每轮节点死亡之数目对比见图2。由图2可知：当网络出现分离宣告死亡时，基于LEACH算法网络中还有524个节点未死亡，占节点总数的52.4%，网络生存周期为432轮，可知能量空洞问题对该网络的生命周期有较大影响，因为能量空洞较早出现，致使在还有超过1/2节点存活的情况下，网络就已经分离而无法继续传输数据，导致网络死亡。
而在基于UCR算法的网络中，当网络分离死亡时，仅有61个节点未死亡，占节点总数的6.1%，网络生存周期为718轮。可知，相对于固定簇半径分簇，不等簇半径分簇策略可以有效均衡网络中各簇头负载，从而延缓能量空洞现象的出现，延长网络寿命约66%。
图2 2种策略下每轮节点死亡数目对比
Fig. 2 Comparison of node numbers of deaths per round under two strategies
3.2 网络能耗分析
2种策略下每轮能量消耗情况对比见图3。由图3可见：当网络出现分离宣告死亡时，基于LEACH算法网络中还有约40%的剩余能量。而在基于UCR算法的网络中，当网络分离死亡时，还有约3%的剩余能量。这表明相对于固定簇半径分簇，不等簇半径分簇策略可以有效均衡网络的能量负载。
同时，由图3所示线条走势可知：在每一轮生命周期中，基于不等簇半径分簇的网络能量消耗要比基于固定簇半径分簇的网络能量消耗大。这主要是因为基于不等簇半径分簇的网络，在网络外层的成簇半径较大，甚至簇半径超过了传输阈值do，导致簇内数据收集与簇间数据转发采用了多路径衰减能耗模型，增加了能量开销，但却有效地避免了网络中能量空洞的出现。
图3 2种策略下每轮能量消耗情况对比
Fig. 3 Comparison of energy consumption per round under two strategies
3.3 节点死亡位置分析
图4与图5所示分别为2个网络各轮节点死亡信息统计图，其中X轴代表节点在圆形分布区域中的X坐标，Y轴代表节点在圆形分布区域中的Y坐标，即X-Y平面为节点分布平面；Z轴为各节点的死亡轮数，由上往下轮数增加。
上层的波峰区域表示处于该位置的节点在较早的轮数中就已死亡，主要为Sink附近区域以及各层簇头所在区域；下层的波谷区域表示处于该位置的节点在网络分离死亡时还未死亡。
在固定簇半径分簇网络中，各簇头的簇内数据收集能量消耗基本相同，而簇间数据转发能量消耗差距较大，距离Sink越近的节点承担越多的外层数据转发任务，整体能量消耗既大且快，因此，图4中Sink附近区域颜色最深，由Sink附近区域向外，各层簇头所在的上部波峰区域颜色依次变淡，说明距离Sink越近的内层簇头越早死亡，距离Sink越远的外层簇头越晚死亡，甚至最外层的一些簇头在网络分离死亡时仍未死亡。正是由于各层簇头节点死亡时间的不均衡，导致了能量空洞出现，内层簇头多在较早轮数内死亡；而此时外层簇头还未死亡，仍具有较大的数据转发需求，进一步加剧内层簇头能量消耗，促使内层簇头死亡，形成能量空洞，导致网络分离死亡。在网络死亡时，大量节点存活，主要集中在外层区域，即为图4中的底部波谷区域。
图4 固定簇半径分簇策略下每轮死亡节点位置信息
Fig. 4 Death node position information per round using equivalent cluster-radius clustering
图5 不等簇半径分簇策略下每轮死亡节点位置信息
Fig. 5 Death node position information per round using unequal cluster-radius clustering
在不等簇半径分簇网络中，不同层间的簇头簇内数据收集能量消耗不同，簇间数据转发能量消耗也不同。距离Sink较近的节点依然承担较多的外层数据转发任务，但由于其簇半径较小，簇内数据收集能耗较小。距离Sink较远的节点，承担较少的簇间数据转发任务，但由于其簇半径较大，簇内数据收集能耗较大。整体而言，不等簇半径分簇网络中的不同层簇头节点整体能量消耗基本相同，所以，图5中Sink附近以及各层簇头所在的蓝色区域颜色深度基本一致。正是由于各层簇头节点的死亡节奏一致，保证了网络数据的收集与转发，有效避免了能量空洞的出现。
4 结论
(1) 采用簇半径不等的非均匀分簇策略，对比固定簇半径分簇策略，可实现各层簇头的能量均衡消耗，提高能量使用效率，避免能量空洞的产生，延长网络寿命。
(2) 采用等比递增的簇半径分簇策略，各簇根据网络实际情况动态构建，对前期的网络拓扑设计和节点部署工作的依赖性较低，具有较强的适应性和广泛的适用性。
参考文献：
[1] Akyildiz I F, Su W, Sankarasubramaniam Y, et al. A survey on sensor networks[J]. IEEE Communications Magazine, 2002, 40(8): 102-114.
[2] Cheng T E，Bajcsy R. Congestion control and fairness for many-to-one routing in sensor networks[C]//Proc of ACM SenSys'04, Baltimore, USA: ACM, 2004: 148-161.
[3] Wu X B, Chen G H, DAS S K. Avoiding energy holes in wireless sensor networks with nonuniform node distribution[J]. IEEE Transactions on Parallel and Distributed Systems, 2008, 19(5): 710-720.
[4] Olariu S, Stojmenovic I. Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting[C]//Proc of the IEEE INFOCOM. New York, USA: IEEE Communications Society, 2006: 1-12.
[5] Li J, Mohapatra P. An analytical model for the energy hole problem in many-to-one sensor networks[C]//Proc of IEEE Conference on Vehicular Technology, 2005: 2721-2725.
[6] Lian J, Naik K, Agnew G. Data capacity improvement of wireless sensor networks using non-uniform sensor distribution[J]. International Journal of Distributed Sensor Networks, 2006, 2(2): 121-145.
[7] Li J, Mohapatra P. Analytical modeling and mitigation techniques for the energy hole problem in sensor networks[J]. Pervasive and Mobile Computing, 2007, 3(3): 233-254.
[8] 吴小兵, 陈贵海. 无线传感器网络中节点非均匀分布的能量空洞问题[J]. 计算机学报, 2008, 31(2): 253-261.
WU Xiaobing, CHEN Guihai. The energy hole problem of nonuniform node distribution in Wireless Sensor Networks[J]. Chinese Journal of Computers, 2008, 31(2): 253-261.
[9] Lian J, Chen L, Naik K, et al. Modeling and enhancing the data capacity of Wireless Sensor Networks[C]//Proc of the IEEE Monograph on Sensor Network Operations, IEEE Press, 2004: 91-183.
[10] 曾志文, 陈志刚, 刘安丰. 无线传感器网络中基于可调发射功率的能量空洞避免[J]. 计算机学报, 2010, 33(1): 12-22.
ZENG Zhiwen, CHEN Zhigang, LIU Anfeng. Energy-Hole avoidance for WSN based on adjust transmission power[J]. Chinese Journal of Computers, 2010, 33(1): 12-22.
[11] Wang W, Srinivasan V, Chua KC. Using mobile relays to prolong the lifetime of wireless sensor networks[C]//Proc of ACM MobiCom. Cologne, Germany, 2005: 270-283.
[12] Luo J, Hubaux J P. Joint mobility and routing for lifetime elongation in wireless sensor networks[C]//Proc of the IEEE INFOCOM. Seattle, WA: IEEE Press, 2005: 819-830.
[13] Soro S, Heinzelman W. Prolonging the lifetime of wireless sensor networks via unequal clustering[C]//Proc of the 5th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks. Denver: ACM, 2005: 236-240.
[14] Chen G, LI C F, Ye M, et al. An unequal cluster-based routing strategy in wireless sensor networks[J]. Wireless Networks (JS), 2009, 15(2): 193-207.
[15] 刘安丰, 任炬, 陈志刚. 异构传感器网络能量空洞分析与避免研究[J]. 软件学报, 2012, 23(9): 2438-2448.
LIU Anfeng, RENG Ju, CHEN Zhigang. Analysis and Avoidance of Energy Hole Problem in Heterogeneous Wireless Sensor Networks[J]. Journal of Software, 2012, 23(9): 2438-2448.
(编辑 邓履翔)
收稿日期：2013-05-14；修回日期：2013-07-21
基金项目：国家自然科学基金资助项目(61073186)；国家自然科学基金委员会国际(地区)合作与交流项目(61111140391)
通信作者：陈志刚(1964-)，男，湖南益阳人，博士，教授，从事网格计算，分布式系统研究；电话：0731-88830797；E-mail：czg@csu.edu.cn
