结合负载分流的无线传感器网络簇间数据转发算法①

梁 静,葛 宇

1(成都工业学院计算机工程学院,成都 611730)

2(四川师范大学计算机科学学院,成都 610101)

无线传感器网络中传感器节点最大的能量消耗源于无线通信[1],然而传感器节点一般使用能量十分有限的电池提供能量,且通常运行在恶劣甚至危险的偏远环境中,充电和更换电源的难度很大,因此如何设计有效方法来提高数据通信过程中网络能量的使用效率,避免出现能量空洞[2]成为了当前研究的核心问题.分簇路由[3-7]作为一种平衡网络能量消耗,降低能量空洞出现可能性的重要技术,是近年来国内外学者的研究热点.如:文献[8]提出了基于非均匀分簇和多跳传输的路由算法Energy Efficient Uneven Clustering (EEUC),该算法利用簇头竞争半径来调节簇规模,使靠近基站的簇规模相对较小,这部分簇头收集簇内数据的能耗就会相对减少,从而拥有更多的能量来进行路由转发.这种非均匀成簇路由算法在一定程度上平衡了网络能量消耗,降低了能量空洞出现可能性.文献[9]将非均匀分簇思路与LEACH 结合提出一种新算法,该算法从控制簇头分布以及簇规模的角度出发,根据节点稀疏程度和剩余能量来保证簇头分布均匀,以此平衡网络能耗、减缓能量空洞的出现.文献[10]从控制簇头数据传播路径的角度出发,将簇头间数据转发的思想应用到LEACH算法中,在簇头之间形成了一条通向基站的优化路径,从而均衡了网络能量消耗.文献[11]改进EEUC 机制,引入能量项和距离项,选举簇首时对门限函数进行改进;并对规模较大的簇进行节点分组,由各分组的中心节点执行各自分组内成员节点的数据采集与融合任务,簇首节点只与各分组中心节点进行通信,均衡簇内节点能耗.文献[12]基于EEUC路由协议,以节点剩余能量、簇内成员数目、可用缓存大小、节点信道质量、节点距离为参数,计算多条传输路径,提出基于多路径的非均匀分簇能量优化路由协议.

和以上思路不同,本文从分流簇头负载、平衡节点能耗的角度出发,分析了负载分配不均可能导致的能量空洞问题,并结合上述文献中簇间数据转发思路提出了一种基于负载分流的数据转发策略,以提高网络能量使用效率,降低能量空洞出现的可能性.

1 网络能耗模型

本文采用和文献[8]一样的简单能量消耗模型,忽略节点在计算、存储等过程中的能量消耗,仅计算通信能耗.在传输lbit数据经过距离d的过程中,节点发送数据的能量消耗如式(1)[8]:

节点接收数据的能量消耗如式(2)[8]:

其中,d0为一阈值,本文定义为是发送、接收电路处理每比特数据的能量消耗;εfsd2和εmpd4是发送每比特数据放大器的能量消耗.

2 基于负载分流的数据转发算法

2.1 簇间数据转发中能量空洞问题分析

按照簇间数据转发思路,若簇头Si通过转发方式传输数据到基站(Sink),则Si要从候选中继中选出一个合适的簇头Sj帮助其转发数据.由于所有数据均汇聚到Sink,导致越靠近Sink的节点所担任的转发任务越重,过早失效形成能量空洞的可能性越高.例如图1中,网络区域内的点表示簇头,中心点为基站Sink,所有簇头的数据都将通过S1、S2、S3、S4分别汇聚到Sink.以阴影区域内的簇头为例,S3需要帮助S31、S311、S3111、S312、S32、S321转发数据,而S31只 用帮助S311、S3111、S312转发数据,S32只用帮助S321转发数据,相比而言靠近Sink的簇头S3承担的转发任务量高于上述簇头.另外,对于靠近Sink的簇头S1、S2、S3、S4而言,S3承担的数据转发任务最多,必然导致其先于S1、S2、S4能量耗尽而失效,从而使阴影区域中节点的簇头数据将不能再由S3汇聚到Sink,形成能量空洞.

图1 网络数据转发

2.2 基于负载分流的簇头间数据转发策略设计

2.2.1 负载分流设计思路

负载分流策略通常用于均衡网络资源消耗,如文献[13]针对异构无线网络研究了负载分流机制,提出了一种混合负载均衡算法,实现了保证系统资源利用率的同时提高网络服务质量;文献[14]针对内容分发网络中大规模数据请求发生的情况,研究并设计了服务器间的负载分流策略,有效保证了网络服务质量.文献[15]使用密度控制机制改变节点的工作、休眠状态,使各层网络中的节点能量趋于同时耗尽.同时,引入路由负载平衡分流的思想,让数据发送到下一跳簇头时,分流到多个簇头以平衡簇头间的负载.受以上研究的启发,本文在参考EEUC算法思路基础上,针对Sink附近的簇头容易出现负载分配不均、能量空洞的问题,依据如下策略进行负载分流处理:

假设簇头Si不能直接与Sink 通信,其数据需要中继簇头帮助转发,且候选中继簇头中能一跳转发数据到Sink的簇头个数大于1,此时Si把数据按权重进行分配,发送给能一跳转发数据到Sink的中继簇头(如图2,Sink表示基站,虚线圆表示簇头的通信半径,簇头S1的候选中继有S2、S3、S4.S2和S3均能够一跳转发数据到Sink,S1把数据根据权重转发给S2和S3,在Sink附近的簇头之间实现负载均衡.S4尽管也属于S1的候选中继,但由于S4不能一跳转发到Sink,故S4不参与分流和转发工作).特别说明的是,如果Si的中继簇头中能一跳转发数据到Sink的簇头个数小于等于1,则Si不做分流处理,将数据直接发送到距离Sink 最近的中继簇头.

图2 负载分流思路

2.2.2 分流权重设计

为了控制数据在分流簇头(接收分流数据并帮助转发的簇头)间被合理分配,本小节从分流簇头能耗比角度进行分析,并结合分流数据发送方能耗设计了负载分配权重 λ.

设簇头Si要将数据分流到对应的n个簇头中,其中一个分流簇头Sj的当前能量为Ej,自身已有的数据为lj,从Si分流到Sj的数据为lij,Sj将数据发往Sink的距离是dj.结合式(1)、式(2),Sj接收分流数据和发送所有数据消耗的能量与其剩余能量之比如式(3).其中,分子部分为接收分流数据lij的能耗和发送所有数据(包括自身已有数据lj和分流数据lij)的能耗之和.

为了控制分流数据对Sj能量的影响,以下对式(3)中各调节项的取值趋势进行分析.

(1)式(3)中lj是分流簇头Sj自身待发送的数据,其值越大必然会消耗Sj越多的能量,此时若为Sj分配大量lij,必然导致式(3)比值更大.因此,在lj值较大时应减小lij,以防止簇头Sj的能耗比例过大而提前死亡;反之则可对Sj适当增加lij.

(2)dj是分流簇头Sj中数据的发送距离,其值越大对应能耗越高.式(3)中dj值用Sj与Sink距离d(Sj,Sink)表示,当dj较大时,应减少分配给Sj的数据lij;相反则可增加lij,这样可以让式(3)的比值得到有效控制.

(3)Ej是分流簇头Sj的当前能量.Ej越大的分流簇头,越有能力承担更多的分流任务.因此,当Ej值较高时,可增加分配给Sj的数据lij,相反则应减少lij.

另外,在设计分流权重时还应考虑分流操作中数据发送方Si的能耗.令dij表示Si与分流簇头Sj间的距离.由式(1)可知传输距离和数据量均与能耗成正比,说明:Si向较远的分流簇头分配较多的数据,会加重其能耗.因此,当dij较大时Si应分配较少数据给Sj,相反则可多分配数据给Sj.

基于以上分析,本文设计了负载分配权重 λ如式(4),λij表示Si向分流簇头Sj分配数据的比例.

2.3 簇头间数据转发流程

结合前文提出的负载分流思路,参考文献[8]中的簇构造和簇头选举机制,以下基于簇间数据转发思想,提出了对应的簇头间数据转发流程,其中本文提出的负载分流策略主要体现在Step 4-Step 8.

Step 1.簇内节点以单跳方式将数据发送到簇头,由簇头负责转发.

Step 2.每个簇头广播一条包含其位置信息的NODE_STATE_MSG 消息,其广播范围参考文献[8].

Step 3.针对每个簇头,若当前簇头Si到Sink的距离在其通信范围内,则直接将数据发送到Sink,完成数据传输;否则执行Step 4.

Step 4.针对不能直接发送数据到Sink的簇头Si,根据其收到的NODE_STATE_MSG 消息解析与Sink的距离,比自身小的邻居簇头记入集合Rsi.

Step 5.统计集合Rsi中能在一跳内将数据发送到Sink的簇头记入集合R1si.若|R1si| <1,Si选择Rsi−R1si中离Sink 最近的一个节点作为中继簇头,不进行分流处理,转发完数据后退出流程;若|R1si| =1,Si将所有数据发送给R1si集合中唯一节点,也不分流;否则,把R1si中的簇头作为Si的分流簇头,执行以下Step 6 分流操作.

Step 6.Si向R1si中节点广播请求消息REQUEST,R1si中的簇头将自身的剩余能量和待发送数据量用ACK 消息返回给Si,同时Si记录下自身到各分流簇头的距离以及各分流簇头的相关属性(如:剩余能量、待发送数据量和到Sink的距离).

Step 7.将Si中数据按式(4)比例进行分配,并发送给集合R1si中各分流簇头.

Step 8.R1si中各分流簇头在接收到分流数据后,将分流数据和自身数据一起发送到Sink,结束流程.

3 仿真实验

实验采用Matlab 编写模拟程序对本文提出的基于负载分流的簇间数据转发算法进行验证,实验把本文策略(因本文的负载分流数据转发算法中结合了EEUC算法的簇构造和簇间数据转发机制,故以下将本文算法记为IEEUC)与EEUC算法、LEACH算法从如下3个方面进行比较,以评估本文改进方案性能.

① 比较3种算法对应的首节点死亡时间和网络失效时间,并结合T检验结果评估算法在节点生存周期上的表现.

② 比较3种算法能量剩余情况,评估算法在节点能量使用效率上的表现.

③ 比较3种算法在节点密度(即节点个数)不同时对应的网络失效时间和首节点死亡时间,评估算法在参数值—“节点个数”变化时的效果.

实验中采用理想MAC协议,忽略无线链路中可能发生的丢包错误,同时设传感器节点位于200 m×200 m的正方形网络区域内,Sink位于原点处,即坐标(0,0)位置,其余网络参数如表1.另外,文中未提及的IEEUC、EEUC和LEACH算法相关参数均参考文献[7,8].

表1 网络参数

3.1 节点生存周期对比及T检验分析

实验通过比较3种算法的网络节点生存时间来验证本文改进方案的有效性,对比结果如图3.指定网络节点死亡10%以上表示网络失效,从图3可以看出:IEEUC的第一个节点死亡时间比另外两种算法晚100轮左右、网络失效时间也晚100轮以上.

图3 节点生存周期

另外,为了进一步比较3种算法的节点生存时间,实验运用统计学中成对比较实验法,对EEUC、LEACH和IEEUC的10次运行结果进行T检验.如表2～表5.具体地,表2和表3中的数值越大,说明第一个节点死亡时间和网络失效时间越长.因此,取表2、表3中IEEUC—EEUC和IEEUC—LEACH的结果作为成对数据差ud,对其进行显著性水平为α=0.05的单侧T检验,检验假设为:H0:ud=0,H1:ud>0,样本容量n=10,自由度f=9.T检验结果如表4、表5,其中T为查表临界值.从表4、表5中可以看出:统计量t均大于临界值T,对应接受备择假设H1:ud>0,说明IEEUC算法对应的首节点死亡时间和网络失效时间均优于EEUC和LEACH算法.

3.2 能量使用情况对比

为了对比3种算法的网络剩余能量和节点平均剩余能量随时间的变化情况,实验随机进行10次,取平均结果如图4、图5,从图中可以看出:大约从300轮开始,IEEUC算法的能量消耗速度高于EEUC,说明本文提出的机制利用了Sink附近更多的簇头节点帮助转发数据,在一定程度上造成了能耗增长.但是,文中2.2.1 分析了本文负载分流方案是为均衡Sink附近簇头的能耗,避免相应位置产生能量空洞,延缓网络的整体失效时间.结合没有免费午餐定理(No Free Lunch,NFL)来看,本文方案带来的能耗增加是可接受的.

表2 第一个节点死亡轮数

表3 网络失效轮数

表4 表2数据T检验结果

表5 表3数据T检验结果

3.3 节点密度变化时算法效果对比

在算法涉及的网络参数中,节点个数N直接关系到网络区域内节点密度,以下在节点个数变化时,分别选择10次实验平均结果对比3种算法对应的首节点死亡时间(如图6)和网络失效时间(如图7).

图4 网络剩余能量

图5 节点平均剩余能量

图6 不同节点个数对应的首节点死亡时间

从图6、图7中可以看出:随节点个数的增加,3种算法的首节点死亡轮数和网络失效轮数都有降低趋势,但是IEEUC算法对应的首节点轮数大于其余两种算法40%以上,网络失效轮数晚60%以上.由此说明,IEEUC算法在节点密度变化时对应的网络生存时间仍优于EEUC和LEACH.

图7 不同节点个数对应的网络失效时间

通过以上3个方面实验结果说明:本文基于负载分流的簇间数据转发算法IEEUC与采用直接转发机制的EEUC和LEACH算法相比,负载分流会将本该发给一个簇头的负载分流给n个簇头,这必然会增加分流簇头的能耗.但是,分流方案均衡了Sink附近簇头的负载,能降低能量空洞出现的可能性,从而延长了网络生存时间(在网络失效时间和首节点死亡时间上IEEUC 优于EEUC和LEACH).

4 结束语

本文针对无线传感器网络中,簇间数据转发容易导致靠近Sink的节点提前失效造成能量空洞的问题,提出了一种负载分流策略,并结合了EEUC算法的簇构造和簇头选举机制设计了基于负载分流的簇间数据转发算法.仿真实验结果表明:本文提出的方案通过分流簇头负载,能延长网络寿命,提高了网络能量使用效率,具有良好的性能.