基于数据引流的无线传感器网络能量空洞避免研究

王施雨， 刘 唐

(1. 东北师范大学 物理学院, 吉林 长春 130024； 2. 四川师范大学 基础教学学院, 四川 成都 610066)

近年来,随着无线通信技术与微电子技术的持续发展,无线传感器网络(WSN)[1]得到越来越广泛的应用.传感器网络中的节点通常由能量有限的电池供电,这些节点在部署后难以更换电池,所以无线传感器网络有着严重的能量约束问题[2].

在采用多跳数据传输的无线传感器网络中,如果某些节点承担了更大的数据转发任务,它们的能量消耗速度会明显快于其他节点,因而这些节点会首先死亡.在这些节点死亡后,它们负责转发的数据将很难再有效传输至sink,此时网络寿命结束,而网络中其他节点内大量的剩余能量被浪费,这种现象被称为“能量空洞”[3-4].文献[5]的实验结果表明当网络中出现能量空洞,网络寿命结束时,网络中还剩余高达90%的能量被浪费.

在无线传感器网络的真实应用场景下,传感器节点的数据产生量会根据环境实时发生变化.例如,对用于面向人群监控任务的传感器网络,节点的数据产生速率与被监控的人员数量密切相关.由于人类出行的时空规律性[6],在不同时间被某个节点监控的人员数量会有所不同,这使得该节点的数据产生速率会呈现有规律的动态变化.因此,网络中的节点的能耗负载也呈现出动态变化的特点.

近年来,尽管能量空洞现象已经引起了研究者们的广泛关注,并取得了一定的研究成果,但是还没有面向由真实场景下节点的数据产生速率动态变化造成的能量空洞问题的解决方案.

在对前人工作进行总结的基础上,为有效避免由节点数据产生速率动态发生变化造成的节点能量空洞现象,提出了一种数据引流的非均匀分簇算法FRUC.本文主要工作如下：

1) 利用分簇进行数据收集与传输,但与传统的非均匀分簇不同,FRUC算法在网络初始阶段对网络进行分层,每层网络层高不等,簇的范围限制在层内；

2) 考虑所有节点的数据平均产生率,给出网络各层内的簇头节点完成一次簇内、簇间数据处理所消耗能量的计算方法,并让网络各层的层高取值满足各层之间的所有簇头节点的能耗均衡；

3) 考虑节点数据产生率的动态变化对路由负载的影响,引入基于数据引流的数据传输方法,让一个簇的发送数据量发生变化时,数据不再只发送给一个固定的簇头,而是动态地将数据引流到多个簇头.

1 相关工作

目前,能量空洞作为无线传感器网络中一个瓶颈性的问题,国内外许多研究者进行了大量研究.

为了有效均衡网络内节点能耗,解决能量空洞问题,研究者们提出了许多不同的策略来缓解能量空洞现象造成的影响.其中,研究者利用的技术包括：部署移动sink、利用非均匀分簇算法、采用不同的传输策略、传感器节点的非均匀分布等.下面介绍与本文研究相关的非均匀分簇算法研究.

与LEACH[7]、HEED[8]这样的传统分簇算法不同,非均匀分簇算法让网络中的各个簇具有不等的簇规模,以使有更大能耗的区域簇规模减小,有更小能耗的区域簇规模增大,从而均衡网络内各区域的节点负载,延迟能量空洞的出现并延长网络寿命.

文献[9]提出了一种分布式分簇路由协议DEBUC,该协议采用基于时间的簇头竞争算法,节点的广播时间由其邻居节点和候选簇头的当前剩余能量决定.同时,通过控制不同网络区域的候选簇头的竞争半径,使得距离sink较近的簇规模较小.与之相类似的还包括文献[10]提出的EEUC算法,该算法通过控制簇头的竞争半径来调整簇的规模,使靠近sink的簇比远离sink的簇拥有更小的簇半径.

文献[11]将非均匀分簇引入节点非均匀分布的网络,以避免能量空洞问题，并提出了一个最小化网络内所有节点能耗的最优簇结构方法，还设计了一个简单的分布式路由协议以实现所有节点能耗均衡.

文献[12]提出了ACT分簇路由协议.该协议将网络分层,簇的规模限制在层内.文献[12]计算了簇头节点的能耗,并让网络各层的大小满足在一个簇周期,各层内的单个簇头节点的能耗相等.但是,由于各层规模不同,各层内的簇头节点数目也不同.因此该算法并没有保证在一个簇周期内各层中所有的节点能耗之和相等,因而该协议并不能真正均衡各层的能耗.

文献[6]研究了异构网络中如何避免能量空洞.针对异构环境下各个簇产生的数据量不等且未知的条件,文献[6]提出了一种基于反馈机制的分均匀成簇算法.

文献[13]的研究针对由初始能量较大节点担任簇头、初始能量较小的节点作为簇内成员节点的异构传感器网络,提出了基于不等簇半径的能量空洞避免策略.文献[13]从理论上推导出距离sink不同距离处簇半径的大小,并给出了不等簇半径的取值与优化方法.

文献[14]提出了一个能量有效的分布式成簇算法,该算法根据与sink节点的数据转发距离确定适当的簇半径,以实现节点寿命的大致均衡.文献[14]还提出了一个简单的高效节能多跳数据收集协议来对成簇算法进行评价,并计算出该协议的能耗.

文献[15]提出了一个模糊能量感知的非均匀分簇算法EAUCF.该算法为降低靠近sink的簇头节点和低剩余能量簇头节点的工作负载,引入模糊逻辑方法以处理簇头半径估计的不确定性.

文献[16]提出了一种流量均衡路由算法FBR.与已有的路由算法不同,FBR的骨干网络构造算法构建了一种新的多层次骨干网络,该网络不同于传统树形的簇头通信拓扑结构,而是每个簇头拥有多个父节点.簇头间进行数据传递时,簇头将待发送数据分发给多个父节点,以平衡父节点的能耗,延长网络寿命.但是该分簇算法让每个簇的簇半径相等,因此各簇能耗很难实现完全均衡.同时,该算法并未让所有的节点轮流担当簇头,因此簇头节点能耗速度明显快于普通节点.

2 网络模型

2.1网络模型本文定义W×L(m)的矩形网络中分布着N个传感器节点.图1给出了网络模型示意图,表1为相关符号说明.设该传感器网络性质如下：

1) 唯一的sink节点位于网络边缘,sink以基站形式部署；

2) 网络中所有的传感器节点满足随机分布,节点的发射功率可调,且在部署后静止不动；

3) 传感器节点被组织成簇的形式,各簇的范围限制在网络分层内,簇头节点在完成簇内数据收集后,以簇间多跳形式将数据发送到sink节点；

4) 传感器节点在不同时刻的数据产生率动态变化,根据监控区域的历史数据,在网络生命周期内的节点平均数据产生率可知.

2.2能耗模型本文采用典型的能量消耗模型[17],在数据传输过程中,传感器节点传输lbit数据经过距离d,产生的能耗为

ETx(l,d)=ETx_elec(k)+ETTx_amp(l,d)=

(1)

接收端所产生的能耗为

ERx(l)=ERx_elec(l)=lEelec，

(2)

其中,d0为一阈值,当数据传输距离小于d0时,发送方的能耗与距离的平方成正比,否则与距离的4次方成正比.Eelec表示发送或接收1 bit数据时的能量消耗,εfsd2和εmpd4是发送1 bit数据放大器的能量消耗.

图 1 网络模型结构

符号含义W网络宽度L网络长度Li第i层网络Hi第i层网络的层高Ci第i层网络中的簇‖Ci‖簇Ci的面积r(Cj)簇Ci的半径ρ网络中的节点密度ECHi簇Ci的簇头节点在一个簇周期内的能耗Eini簇Ci的簇头节点一个簇周期内用于完成簇内数据处理的能耗Eiti簇Ci的簇头节点一个簇周期内用于完成簇间数据处理的能耗Ei第i层网络中所有簇头节点在一个簇周期的总能耗

3 网络能耗分析与非均匀分层

在多跳传感器网络中,靠近sink的簇头节点由于承担更多的数据转发任务,因而有着更大的能耗.通过传感器节点的平均数据产生率,建立网络各簇头节点的能耗计算模型,提出基于网络层次划分的非均匀分簇模型,让靠近sink的网络分层内的簇规模更小,让远离sink的网络分层内的簇规模更大.

π(r(Ci))2ρlEelec.

(3)

因此,簇头节点CHi接收外层网络的数据所消耗的能量为

簇头节点CHi发送到内层网络的数据包括接收的外层网络数据及簇内节点发送到簇头的数据,因此CHi需要发送到内层网络的数据总量为

根据能量消耗模型,簇头节点CHi发送所有数据所消耗的能量为

根据(5)和(7)式能得出簇头节点CHi在一个簇周期完成簇间数据处理所消耗的能量为

传感器网络中,簇头节点承担了数据收集和转发任务,它们的能耗远大于簇内普通节点.为避免能量空洞现象的出现,应着重考察在一个簇周期内,簇内节点的能耗.由于网络各层的簇头节点数量不等,因而仅仅比较网络各层内单个簇头节点的能耗,并不能有效平衡网络各层的总能耗.因此,为避免能量空洞现象的出现,平衡网络各层的能耗,在一个簇周期内网络各层内的所有簇头节点的能耗之和应相等.

对第i层网络,其所有簇头节点的总能耗为

(9)

(10)式给出了为平衡网络各层的能耗,各层层高应满足的条件

(10)

4 基于数据引流的路由算法描述

下面首先讨论如何选择簇头,进一步给出基于数据引流的路由算法.

4.1簇头选择在网络首轮成簇前,网络内的所有节点使用一定的传输能量进行全网广播,利用信号强度在传输过程中的衰减,节点可以感知相互之间的距离.文献[17]给出了节点通过信号发送强度和接收强度之间的关系得出节点间相互距离的计算方法

(11)

sink在网络初始阶段以覆盖全网络范围的广播强度进行一次广播,网络中的各节点在收到sink的广播后根据(11)式得到自身与sink的距离,确定所属网络层次.进一步,各节点在所属网络分层内广播包含自身当前剩余能量信息的簇头竞争消息.如果某节点发现自身的当前剩余能量大于收到广播的其他节点能量,该节点就发布成为簇头的广播.

4.2数据引流簇头节点在每个簇周期收到簇内各节点的数据后,需要将这些数据在网络分层中进行转发,以最终发送至sink.在传统的多跳传感器网络中,一个数据包到sink之间只有一条固定的簇间路由路径,如图2所示.

图 2 固定路由示意图

这种固定簇间路由存在的问题如下：

1) 由于网络各层的层高不等,各层内的簇头数量也不等,因而在簇头数量较多的内层网络中,各簇头的负载必然不均衡,会出现某些簇头承担了较多的数据转发任务而某些簇头没有承担转发任务.如图2所示,越靠近sink的簇头节点会呈现更大的路由负载不均衡现象.以最内层网络为例,路由负载最大的节点,承担了来自5个簇的数据转发量,而该层网络中有的簇头并未承担外层网络的数据转发.

2) 难以适应节点的数据产生率随网络环境变化的动态场景.在节点数据产生率动态变化的场景下,每个簇头节点在每个簇周期接收到的簇内成员产生的数据量也会随之改变.如果采用传统的固定簇间路由方法,数据转发量的动态变化会加重同层内的各个簇头间的能耗负载不均现象,从而更快的导致节点的死亡并出现能量空洞.

为解决上述问题,平衡网络内各簇簇头的路由负载,本文提出一种基于数据引流的路由方法,让一个簇的数据转发到下一层时,不再只转发到一个簇头,而是根据各个簇当前需要转发的数据量,实时将数据引流到多个簇头.数据引流的思想如下：

1) 每个簇头进行数据转发时,将本簇产生的数据和收到的来自外层簇头发送来的数据,引流到内层网络中的多个簇头；

2) 为实现避免个别节点提前死亡的目的,让有更多剩余能量的簇头承担更大的数据转发任务.在每个簇周期,各个簇产生的数据量会动态变化,因此在每个簇周期开始簇间数据传输时,考察每个簇头的剩余能量和每个簇头所在簇内的数据产生量.在某个簇头有数据需要转发时,将更多的数据引流到剩余能量更多、簇内数据量更少的簇头,以平衡下层网络内的各个簇头的能耗.

对Li(i≠1)层网络中的第j个簇头节点CHi,j,设当前簇周期需传输至下一层网络的数据量为li,j,CHi,j首先启动路由发现过程,向下一层网络中发出路由请求消息.Li-1层网络中所有簇头在收到请求后,以一定功率发出包含自身能量信息和当前簇周期所在簇的簇内数据量的应答消息.

簇头节点CHi,j根据计算得出的引流值,将数据分为大小不等的若干份,发送至下一层的各个簇头节点.当新一轮簇周期,各个簇产生的数据量和各个簇头的剩余能量发生变化时,数据引流量也会动态更新.

图 3 数据引流示意图

图3给出了在一个簇周期进行簇间路由时的数据引流示意图.可以看出,各簇的数据被引流到下一层网络的多个簇头,以平衡每一层内的各簇之间的能量消耗,避免部分节点能量耗尽形成能量空洞.数据引流算法流程如下：

For 每一个簇周期

For 每一个簇

选举能量最大的节点成为簇头节点

End for

For 从外到内的每一层网络

For 每一个簇头节点

计算簇头需要发送的数据量

启动路由发现过程

收到下一层网络的应答消息

计算引流到下一层每个簇头节点的数据量

End for

End for

各个簇头进行数据发送

End for

5 仿真实验

将在Matlab仿真实验平台下,验证提出的算法是否能有效避免.首先对网络分均匀分层进行验证,给出在默认网络环境下,网络各层层高的取值；其次,将讨论在网络非均匀分层的情况下,数据引流对网络性能提升的影响；进一步,将对比LEACH、DEBUC、FBR和本文提出的FRUC4种算法不同的表现.选择这3个算法进行对比的原因是LEACH是经典的分簇算法；DEBUC为了实现网络内节点能量均匀消耗,通过给出每个簇头不同的簇头竞争半径值以实现非均匀分簇；FBR则是首先提出数据引流思想的路由算法.

表 2 实验参数

在仿真实验中,网络默认规模为250 m×150 m的矩形区域,唯一的sink位于网络的边缘位置.网络带宽为10 kbps,其他网络参数以及相应的缺省值见表2.实验结果若未特别说明,均为100次独立实验结果的均值.

5.1网络分层性能首先,在节点的数据产生率不变的条件下,考察网络分层的情况,并对网络最优分层时各层内的簇头节点的能耗情况进行分析.

表3给出了每个节点产生的数据消息大小为1 000 bit时,由(10)式得出的网络各层规模.

表 3 分层高度

从表3可以看出,在250 m×150 m的网络分为了4层,越靠近sink的网络分层层高越小,越远离sink的网络分层层高越大.此时网络寿命(第一个节点的死亡时间)为371轮.进一步,随机选择了10轮簇周期,分布考察每个网络分层内的簇头节点的总能耗.图4给出了各网络各层内的簇头节点在随机选择的10个簇周期的总能耗.可以看出,网络4层内的簇头节点,在这10个簇周期的总能耗,一直处于相对均衡的状态,能耗值基本上在39～52 mJ之间.这说明了,随着网络被划分成了高度不等的分层,非均匀分簇能有效平衡网络各区域节点的能耗.

图 4 各层簇头总能耗

进一步,图5显示了在这10个簇周期,网络各层簇头节点总能耗的标准差.可以看出,在随机选取的10个簇周期中,除了2个簇周期以外,其他8个簇周期各层簇头节点的总能耗差异都很小,其标准差都在3以内,而层间能耗差异较大的2个簇周期,标准差也在4.5以内.这表明了,FRUC算法能有效平衡层间的簇头能耗.

图6显示了每个网络分层内的簇头节点在10个簇周期的总能耗标准差.可以看出,在更靠近sink的内层网络内,各簇头节点总能耗在各个簇周期差异很小,而在远离sink的外层网络,各个簇周期节点能耗差异较大.

图 5 层间簇头节点能耗标准差

图 6 层内簇头节点能耗标准差

5.2数据引流性能下面在对数据引流对网络性能的影响进行分析.首先,比较在默认网络环境下有无数据引流时的网络寿命.

表 4 数据引流对网络寿命的影响

从表4可以看出,数据引流能有效提升网络寿命,延缓节点死亡时间.由于数据引流能有效平衡簇头节点间的能耗负载,并能让具有更多剩余能量和更小数据传输距离的簇头节点承担更多的数据转发任务,因而更有利于节省数据路由过程中的能耗开销.因此,在层间路由未进行负载引流时,网络寿命仅为211轮,而采用数据引流后,网络寿命提升到376轮.

图7给出了未采用数据引流时,网络各分层中的簇头节点在一个簇周期的能耗.可以看出,在内层网络中由于不同的簇头节点承担了不均衡的数据转发任务,因而各簇头节点间的能耗差异极大.以L1层网络为例,能耗最高的一个簇头节点在一个簇周期消耗了24.215 mJ能量,这是能耗最低的簇头节点的20.875倍.

图 7 无数据引流时簇头节点能耗

图8显示了采用数据引流后,网络各层中的簇头节点在一个簇周期的能耗.显然可以从图8看出,与图7相比，L1层和L2层网络中的簇头节点的能耗得到了相当大的平衡.这是因为通过引流,L1层和L2层网络中的所有簇头节点都承担了数据转发任务,因而有效均衡了所有簇头节点的能耗负载,这也有助于避免某些簇头节点因能耗过大提前死亡而造成的能量空洞现象.

图 8 数据引流时簇头节点能耗

5.34种算法对比通过实验比较本文提出的基于数据引流的非均匀分簇算法FRUC、LEACH算法、DEBUC算法及FBR算法在网络寿命和网络首节点死亡时节点能量剩余率方面的性能.

图9给出了在默认网络环境下,4个算法所取得的网络寿命.可以看出LEACH算法由于是簇间单跳路由,因此有着最低的网络寿命.DEBUC算法作为一种典型的非均匀分簇算法,网络寿命相对于LEACH算法得到了明显提升.FBR算法由于引入了引流机制,网络寿命高于LEACH和DEBUC,但是FBR由于让固定的节点担当簇头,同时网络内所有簇规模相等,因此靠近sink的簇头节点的死亡时间会早于其他普通节点,从而使网络寿命低于本文提出的FRUC算法.

图 9 网络寿命对比

图10比较了4个算法在默认网络参数下,首节点死亡时所有节点的平均剩余能量.可以看到,对于LEACH算法,在网络寿命结束时所有节点平均剩余能量最高,达到了0.472 8 J,这也与文献[5]的实验结论相符.DEBUC算法和FBR算法的节点平均剩余能量分别为0.341 1 J和0.247 8 J.本文提出的FRUC算法能最好地利用节点能量,非均匀分簇保证了网络各层之间簇头节点能耗均衡,数据引流又保证了网络各层内的簇头节点能量均衡消耗,因此当网络中出现第一个死亡节点时,网络所有节点平均剩余能量仅为0.193 8 J.

图 10 节点平均剩余能量对比

进一步,改变节点初始能量,对4个算法的网络寿命进行比较,图11给出了实验结果.可以看到,随着节点初始能量的增加,4个算法所取得的网络寿命均得到了提升,其中FRUC、DEBUC、FRB等3个算法网络寿命的提升明显.而节点初始能量取值不同时,FRUC算法均有着最高的网络寿命.

图 11 不同节点初始能量下的网络寿命

图12给出了改变网络中的节点密度,4个算法所取得的网络寿命.可以看到,随着节点数目的增加,LEACH和DEBUC算法的网路寿命均下降明显,这是因为节点数目越多,网络内产生的监控数据也随之增加,节点消耗了更多的能量进行数据传输,从而降低了网络寿命.FBR算法由于数据引流的作用,网络寿命在节点数目增加到350个以后,才出现下降,且下降趋势明显缓于DEBUC算法.本文提出的FRUC算法在网络节点密度较低节点数目仅为300个时,网络寿命略低于DEBUC和FBR算法.这是因为FRUC算法对网络进行了分层,且越靠近sink的网络分层规模越小,这样在节点低密度状态下,L1层网络内节点数目很少,从而少量的节点承担了簇头节点的工作,影响了网络寿命.而在其他节点密度下,FRUC算法均有着最高的网络寿命，并且由于数据引流平衡了簇头节点的能耗,因此在节点数目大于400个以后,网络寿命才出现了下降.

图 12 不同节点密度下的网络寿命

6 结束语

本文对无线传感器网络的能量空洞问题进行了研究,提出了一种基于数据引流的非均匀分簇能量空洞避免策略FRUC.与已有工作相比,FRUC的主要贡献表现在以下2个方面：

1) 不同于传统的非均匀分簇算法DEBUC与EEUC,FRUC不再通过计算不同节点的不同簇头竞争半径，从而实现非均匀分簇.FRUC在网络初始阶段对网络进行非均匀分层,并让簇的范围限制在层内,以实现非均匀分簇,从而保证了网络各层之间簇头节点的能耗均衡；

2) FRUC算法引入了数据引流,让一个簇的数据发送给下一层时,不再只发送给一个簇头,而是将数据引流到多个簇头,这样平衡了网络各层内各个簇头节点的能耗均衡.

仿真实验结果表明,FRUC算法能够获得比LEACH、DEBUC、FBR等主要数据传输算法更均衡的节点能耗负载、更长的网络寿命,并能有效避免能量空洞现象的出现.