一种非均匀部署传感网的能量空洞缓解方法

陈 欢,沙 超,2,黄海平,王汝传

(1.南京邮电大学 计算机学院，江苏 南京 210003; 2.苏州大学 江苏省计算机信息处理技术重点实验室,江苏 苏州 215006)

一种非均匀部署传感网的能量空洞缓解方法

陈 欢1,沙 超1,2,黄海平1,王汝传1

(1.南京邮电大学 计算机学院，江苏 南京 210003; 2.苏州大学 江苏省计算机信息处理技术重点实验室,江苏 苏州 215006)

在无线传感网中，网络中心附近的节点由于要负责全网数据的接收和转发，将会消耗更多能量，从而造成节点间能耗不均，产生“能量空洞问题”。为延长簇树状无线传感网的网络生命期并均衡网内各节点能耗，提出了一种面向圆形传感器网络的能量空洞缓解方法。该方法将网络划分为虚拟的环状结构以满足多跳数据传输的要求，感知节点非均匀地分布在该圆形网络中，内环中的节点数总是多于外环，以确保数据上传过程中的能耗均衡性，各节点根据其邻近节点的剩余能量和通信距离，选择相邻环内的最优节点作为父节点上传数据。仿真实验结果表明，与其他典型的能量空洞避免方法相比，所提出的方法有效延长了网络生命期，在多跳传感网中较好地实现了能耗均衡，有效地缓解了能量空洞的产生。

无线传感网;能量空洞;能耗均衡;非均匀部署

0 引 言

近年来，无线传感器网络(Wireless Sensor Networks,WSNs)成为研究热点[1-3]。并且许多配备了无线传感器网络的消费产品已被部署在家庭网络之中[4-5]。使用环形拓扑均匀分布节点的无线传感器网络通常是由一组传感器节点和一个sink节点组成的，采用多对一的数据收集模式[6]。

然而，越靠近sink的节点携带越多的流量负载，导致更多的能量消耗。由于节点能量的有限供应，因此靠近sink布置的节点将比远离sink布置的节点更快地耗尽自身能量。节点能量的不平衡消耗将会在sink周围引起能量空洞(Energy Hole)现象[7-8]。能量空洞现象是指网络中由于部分节点过早耗尽自身能量导致网络原有覆盖区域缺失或者数据无法送达sink的现象[9]。在能量空洞问题产生后，将会不再有数据发送给sink，从而使得网络的生命周期过早结束。然而当分布在sink第一半径范围内的节点耗尽了自身能量时，那些远离sink的节点大部分初始能量还没有被使用。Lian等[10]指出，无线传感器网络的生命周期在提前结束时，大约有90%的初始能量还没有被使用。因此上述的能量空洞问题在无线传感器网络中已经成为最显著的问题之一[11-12]。

文献[13]认为，在负载量大的节点周围布置更多数量的节点可以减轻节点的负载量，从而缓解能量空洞的出现。与这个思路相同的是，吴小兵等[14]证明了无线传感器网络的能量均衡耗尽的不可能性，并提出了“次优网络能耗均衡”(Sub-balanced Energy Depletion)的概念，提出了一种非均匀的节点分布策略，用于实现网络中的次平衡能量消耗，即从外环CR-1到内环C1中的节点数量按照比率为q>1的几何级增长，并且在最外环CR中有NR-1/(q-1)个节点，从而实现了网络的次平衡能量消耗。其中，R为总环数，Ni为环Ci中的节点数。然而在此策略中，节点在相邻环中选择数据传输方式时，未定义明确的标准，且环间节点选择具有随机性，使得节点消耗不平衡，仍会造成能量空洞的出现。

在文献[14]的基础上，利用功率自适应机制，对节点的传输半径进行动态调节，以降低其多跳通信的能耗开销。同时，设计实现了环间节点协同数据上传方案，降低了簇树状传感网“多对一”数据上传过程中出现“近中心负载过高”现象的可能性，有效缓解了能量空洞问题。实验结果表明，网络运行结束后，各节点剩余能量均小于自身初始能量的8%，体现出了较好的能耗均衡性，且节点剩余能量的下降速度小于所对比的网络模型，网络生命期得到了有效延长。

1 网络模型描述

1.1 节点能耗模型

不失一般性，采用同文献[15]相同的节点能耗模型。节点发送数据时，其功率损耗如式(1)所示：

Etx(k,d)=kEelec+kεampd2

(1)

在接收数据时，节点功率损耗如式(2)所示：

Erx(k)=kEelec

(2)

其中，Etx、Erx分别为发送、接收数据损耗的功率；k为数据比特数；d为接收端和发射端之间的通信距离；Eelec为发送或接收单位比特数据电路损耗的功耗系数；εamp为功率放大电路的放大系数。

由式(1)和式(2)可知，一个节点发送单位比特的数据量所耗费的能量要大于接收单位比特的数据量。这主要是由于发射数据损耗功率是与发射端和接收端的距离有直接关系的。而且在通信距离较大时，Etx随d的变化会产生巨增。若此时采用单跳直接传输数据的策略，反而会增加节点的能量消耗，而采用多跳数据上传方案则可将负载均衡到网络中其他节点，有利于均衡能耗，推迟能量空洞现象的产生。因此，重点针对多跳传输下的簇树状无线传感网的能量效率问题进行研究。

1.2 网络模型

假设网络中所有的节点分布在一个半径为R的圆形区域中。网络中只有唯一的sink节点，且置于圆心处。令网络中有n个感知节点，定义其标号为Aj(j=1,2,…,n)。该圆形区域使用以sink为原点的直角坐标系，故以A0(0,0)表示sink的位置。为便于选择最优父节点，进一步将网络划分为N(N>1)个宽度均为dw的虚拟环状区域，从内环向外环依次使用Ci(i=1,2,…,N)表示第i个圆环。节点在各环中均匀部署[14]。

由文献[14]可知，圆环CN-1到圆环C1内的节点数目以等比系数q(q>1)递增。而圆环CN和CN-1中的节点数目之比为1/(q-1)，即:

(3)

令所有节点一经部署后便不能移动，其初始能量均为E0且无法进行后续补充。

1.3 相关定义

定义1：最大通信传输距离dx。

处于圆环Ci(2

(a)最大通信传输距离dx (b)节点的最大考察区域

由定义1及图1(a)易知：

(4)

而处于圆环Ci(i<2)内的节点的最大通信传输距离dx，即为其与sink的最短距离。

(5)

定义2：节点最大考察区域B。

以处于圆环Ci(1

定义3：P代价。

P代价是处于圆环Ci(1

(6)

其中，djk表示节点Aj与考察区域B内的节点Ak的距离；Ck表示节点Ak被选择为后继节点的次数；α和β是常量，满足α+β=1。

令节点工作一轮的时间单位为一个时间片T，节点在每个时间片内分为三个阶段：数据采集阶段、数据发送阶段和数据接收阶段，其持续时间分别为t1、t2和t3。网络中每个处于工作状态的节点以相同的数据采集率采集数据，并在这个时间片内进行发送或者接收其他节点数据的工作。处于圆环Ci(i

2 环间数据上传模式

2.1 最优父节点选择方法

节点分布策略采用文献[14]的非均匀分布方案，其基本思想是在靠近sink的圆环布置较多的节点。因此对于某一圆环在其相邻内环选择一个节点传输数据显得尤为重要。这里，给出节点选择其最优下一跳父节点的方法。

(1)网络中的各节点，根据1.3节的定义，构建其各自的最大考察区域。由于已令各环的宽度均相等，故该最大考察区域B的面积将主要取决于节点在环中的位置及环的宽度值dw。在节点部署密度ρ一定的情况下，该面积大小将直接决定可供选择的下一跳父节点个数。

(2)位于最外环中的节点，对于其所构建的B区域中的各节点，分别根据式(6)计算其P值，并从中选取P值最大的一个节点作为其下一跳父节点，向其发送一个包含自身ID和位置信息的消息包。

(3)若当前节点的B区域中无可供选择的父节点，则其选择距离其最近的一个同层节点，作为其父节点。

(4)当最外层节点均完成父节点的选择后，位于次外环的各节点按照上述方式，从第N-2环中(或从与其位于同一环的兄弟节点中)选择P值最大的节点，作为其父节点，并以此类推，最终构建一个以网络中心sink为根，以虚拟圆环和B区域为约束条件的簇树状数据收集结构。

2.2 缓解能量空洞的环间数据上传策略

如前所述，在簇树状无线传感网中，若对于数据上传时机不加限制，则很容易造成信道冲突、加重“近网络中心”的负载，降低数据收集效率且产生能量空洞。为此，在2.1节所选取的最优父节点基础上，进一步给出提升能耗均衡性的环间数据上传策略。

在时间片开始后，各虚拟圆环内的节点首先都以相同的数据采集率在t1时间内采集数据。数据采集结束后，位于圆环Ci(i=N,N-2,N-4…)内的各节点首先向其父节点发送数据，持续时间为t2，如图2(a)所示。此时，位于第Ci-1环内的节点将存在两种可能：

(1)若该节点存在子节点，则其将进入接收模式，等待来自于其Ci环中子节点的数据。

(2)若该节点无子节点，则其将处于休眠状态，以节约能量。

在t2时间片结束后，由位于圆环Ci-1内的节点向其父节点发送数据，此时，位于圆环Ci-2内的父节点将处于接收状态。若该父节点无子节点，则处于休眠状态以节约能量，如图2(b)所示。

(a)Ci环节点向父节点发数据 (b)Ci-1环节点向父节点发数据

3 实验及结果分析

为验证算法性能，在Matlab2013中进行实验，参数如表1所示。

表1 仿真参数值

不失一般性，这里认为，当网络中出现第一个死亡节点时，网络便停止运行。在网络生命期、各节点剩余能量方差、网内节点剩余能量综合等三方面，同文献[14]中提出的环状网络节点非均匀分布下的能量空洞避免方法进行比较。能耗分析采用文献[15]中所提出的传感网能量消耗模型。

当网络生命期结束时，网内各节点剩余能量如图3所示。所采用的圆形网络中非均匀部署了50个节点。

图3 网络中节点剩余能量

由图3可知，在网络停止运行时，各节点的剩余能量都未超过1.5 J，即各节点剩余能量均小于自身初始能量的8%，体现了较好的能耗均衡性。

表2为在环内部署不同数量节点后的节点剩余能量标准差、网络生命期和数据吞吐量。

表2 不同部署情况下节点的能量效率比较

由表2可知，采用的方法对于不同部署模式下的适应性较强，其能耗均衡性和网络生命期的实验效果均较好。而在NumN=10，q=1.3这个方案部署下，网络的能效性能最好，可最大限度地缓解能量空洞现象的产生。

图4为所提出的非均匀部署网络下的能量空洞缓解方法(Energy Hole Mitigation Strategy for non-uniform deployed sensor networks，EHMS)同节点非均匀分布的能量空洞避免方法(Avoiding Energy Holes in sensor networks with non-uniform node distribution，AEH)[14]在节点剩余能量之和方面的实验结果。

图4 节点剩余能量之和的变化比较

由图4可知，在网络运行时间内，由于EHMS方法中的各节点均在t1、t2和t3时间段内均衡地消耗能量，故其剩余能量总和随着网络的运行，基本呈线性下降的趋势。AEH方法也采用环状的非均匀部署方式，以均衡网络能耗，故在网络运行前期，其网内节点剩余能量的下降趋势和EHMS方法基本一致。但其仅考虑到了相邻圆环间的节点分布情况，未能够进一步对父节点的选择做出必要约束。节点每次仅选择剩余能量最多的节点作为其下一跳父节点，未考虑跳距和环数的影响。故在网路运行后期，其网内节点剩余能量之和略低于EHMS方法。而在1 600～1 800 s之间，AEH方法的节点剩余能量总和未发生变化，说明此时该网络已经停止工作。即EHMS方法的网络生命期相对较长。

图5是节点剩余能量方差随网络运行时间变化的比较曲线。

图5 节点剩余能量方差的变化比较

由图5可知，在网络运行初期，两种方法的节点剩余能量方差均较小，体现出了较好的能耗均衡性。然而，随着网络的运行，尽管两种方法下的方差均可有效地控制在0.35 J2以内，但EHMS方法的能耗均衡性相对更好一些。这是由于该方法采用了环间数据交替上传的策略，在避免传输冲突的同时，有效保存了环内各节点的能量，可进一步推迟能量空洞的产生。

4 结束语

以缓解能量空洞出现为目标，在非均匀部署的无线传感网中，提出了一种选择最优父节点开展层间数据上传的方案。同时考虑到了后继父节点的剩余能量、相邻层间节点的通信距离及环内节点密度等因素。与典型的非均匀无线传感网数据收集方式相比，该方案在实现能耗均衡性的同时，较为有效地缓解了能量空洞的产生，延长了网络生命期。

[1] 刘 唐,彭 舰,陈 果,等.基于密度控制的传感器网络能量空洞避免策略[J].计算机学报,2016,39(5):993-1006.

[2] 张 乐,李 栋,崔 莉.一种针对移动全覆盖问题的节点移动策略[J].计算机研究与发展,2013,50(5):901-911.

[3] 田贤忠,阳 胜.基于网络编码的无线传感器网络瓶颈区域生存时间优化策略[J].计算机学报,2016,39(5):1039-1050.

[4] Wang J,Yin Y,Zhang J,et al.Mobility based energy efficient and multi-sink algorithms for consumer home networks[J].IEEE Transactions on Consumer Electronics,2013,59(1):77-84.

[5] Bellido-Outeirino F J,Flores-Arias J M,Linan-Reyes M,et al.Wireless sensor network and stochastic models for household power management[J].IEEE Transactions on Consumer Electronics,2013,59(3):483-491.

[6] 夏先进,李士宁,张 羽,等.一维传感网中混合数据传输的能量均衡[J].软件学报,2015,26(8):1983-2006.

[7] 唐冰清,张玲华.GEAR协议中贪婪算法及查询消息传播优化方法[J].计算机技术与发展,2013,23(1):135-138.

[8] 曾志文,陈志刚,刘安丰.无线传感器网络中基于可调发射功率的能量空洞避免[J].计算机学报,2010,33(1):12-22.

[9] 李继楼,柯家龙.基于压缩感知的WSN数据压缩与重构[J].计算机技术与发展,2015,25(9):111-114.

[10] Lian J,Naik K,Agnew G B.Data capacity improvement of wireless sensor networks using non-uniform sensor distribution[J].International Journal of Distributed Sensor Networks,2006,2(2):121-145.

[11] 刘安丰,任 炬,徐 娟,等.异构传感器网络能量空洞分析与避免研究[J].软件学报,2012,23(9):2438-2448.

[12] 张 琪,管有庆.基于网络编码的无线传感网络自适应数据聚集[J].计算机技术与发展,2015,25(10):123-126.

[13] Ferng H W,Hadiputro M S,Kurniawan A.Design of novel node distribution strategies in corona-based wireless sensor networks[J].IEEE Transactions on Mobile Computing,2011,10(9):1297-1311.

[14] Wu X,Chen G,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.

[15] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless micro-sensor networks[C]//Proceedings of the 33rd annual Hawaii international conference on system sciences.[s.l.]:IEEE,2000:1-10.

A Type of Energy Hole Mitigation Strategy for Non-uniform Deployed Sensor Networks

CHEN Huan1,SHA Chao1,2,HUANG Hai-ping1,WANG Ru-chuan1

(1.College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China; 2.Key Laboratory for Computer Information Processing Technology of Jiangsu Province, Soochow University,Suzhou 215006,China)

In Wireless Sensor Networks (WSN),nodes near the center tend to consume more energy as they are responsible for receiving and forwarding data from the whole network,which leads to a non-uniform energy consumption among nodes,that is so called the “energy hole problem”.To prolong network lifetime and balance energy consumption in the cluster-tree based sensor network,a type of energy hole mitigation strategy in a circular network has been proposed.Network has been divided into several virtual annuluses for multi-hop transmission and nodes have been non-uniformly deployed in it.Moreover,for balancing energy consumption on data uploading,the number of nodes in the inner annulus is more than that in the outer one.According to the residual energy and the communication distance of its neighbor,each node has chosen an optimal parent in the adjacent annulus for data uploading.Simulation results have shown that this method could effectively prolong network lifetime by comparing with other energy hole avoidance algorithms and has also performed well on balancing energy consumption in the multi-hop transmission network and could effectively mitigate the energy hole problem.

wireless sensor networks;energy hole;balance of energy consumption;non-uniform deployment

2016-07-05

2016-10-13 网络出版时间：2017-04-28

国家自然科学基金资助项目(61572260)；江苏省自然科学优秀青年基金(BK20160089)；江苏省普通高校研究生培养创新工程(SJLX15_0382,SJLX15_0383,KYLX15_0842)；江苏省计算机信息处理技术重点实验室开放课题(KJS1327)

陈 欢(1991-)，男，硕士研究生，研究方向为无线传感网能量空洞缓解技术；沙 超，副教授，硕士生导师，通信作者，研究方向为无线传感网能耗均衡技术；黄海平，教授，硕士生导师，研究方向为物联网隐私保护技术；王汝传，教授，博士生导师，研究方向为物联网信息处理技术。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1703.042.html

TP393

A

1673-629X(2017)06-022-05

10.3969/j.issn.1673-629X.2017.06.05