一种双层树型高能效多链路由算法*

胡中栋,张 康,王振东

(江西理工大学信息工程学院,江西 赣州 341000)

无线传感器网络WSN(Wireless Sensor Networks)是广泛应用于气象、环境、农业和军事等领域[1]的一种信息获取及处理技术,其综合了传感器技术、微电子技术和无线通信技术等多学科技术,被认为是本世纪改变世界的十大技术之一[2]。WSN的主要组成部分是作为微电子设备的传感器节点,一般外形小巧,功耗较低,能量有限且不可再生,因目前对节点生存时间有较大影响的电池技术没有突破性发展,于是对网络结构特性和传输协议的研究是提高网络寿命的重要研究方向。

为减少网络能耗、提高网络寿命,Lindsey S等人在LEACH算法[3]的基础上改进提出了PEGASIS算法[4],该算法采用链式结构,网络结构固定,减少了簇结构算法的频繁重构开销,但由于网络结构是一条长链,时延[5]较大,不适用实时性要求高的场景,且一旦链中某一节点失效,则整个网络瘫痪,鲁棒性[6]差。为此,Quazi等人又改进提出了COSEN算法[7],其采用多链组网,有效降低网络时延,增强了网络鲁棒性,但多链组网也未能解决交叉链和长链多、数据逆传递严重等问题。鉴于上述,本文提出一种双层树型高能效多链路由算法TTEMR(A Two-layer Tree-type Energy Efficient Multi-link Routing Algorithm)。

1 相关研究

1.1 经典协议

经典的平面型路由协议由于传输跳数过多,导致传输时延高、能量浪费严重,而层次路由协议的分簇、成链等思想能有效聚合数据,降低传输平均路径长度,减小时延,已成为当前路由算法研究的热点。

1.1.1 LEACH协议描述

LEACH协议算法采用分簇思想,成簇阶段,通过随机选取节点来作为簇头,非簇头节点就近加入簇。数据传输阶段,簇内节点将数据发送给簇头,然后簇头将数据汇聚融合[8]后直接发给Sink节点。

1.1.2 PEGASIS协议描述

PEGASIS协议算法采用链式结构,建链阶段通过贪婪算法将网络中的所有节点组织成一条链路,每轮随机选择一个节点充当与Sink通信的链头。数据传输阶段,采用令牌机制,沿形成的链路逐跳收集、融合数据,直至传送至链头,最后由链头将数据直接发送给Sink节点。

1.1.3 COSEN协议描述

COSEN协议算法在建链阶段采用贪婪算法,当形成的链上节点数占全网节点数20%时,终止建链,从下跳节点开始重复上述步骤建立新链,直至全网节点皆已成链。然后选取每条链上节点剩余能量最大的节点为链头,各链头再建立链头链,链头链选取剩余能量最大的为主链头。数据传输阶段,各链头分别发送令牌以控制本链节点数据收集传输,最终主链头将各分链链头数据收集融合并传递至Sink节点。

1.2 算法分析

对上述三种协议算法进行优缺点分析:

1.2.1 LEACH算法

簇头随机周期性选取可有效减少网络能耗分部不均,实现网络能耗负载均衡。但仍存在以下缺点:①簇头以单跳通信方式与Sink传输数据,造成簇头节点能量的大量浪费;②由于簇头是随机选取,易导致簇头位置过偏或过于集中。

1.2.2 PEGASIS算法

算法采用链式结构,网络结构固定,节点间平均路径长度短,数据传输阶段每次只有一个节点与Sink通信,减少了簇结构算法的频繁重构开销,但 PEGASIS 算法仍存在着以下不足:①在成链过程中容易形成长链,位于长链上的节点死亡较快;②总链路较长,从链两端到链头的传输时延长;③选择链头未考虑距离影响造成远离Sink的链头节点过快死亡;④一旦有节点死亡,整个WSN需要重新构建链路,网络维护成本高。

1.2.3 COSEN算法

算法采用多链方式,每个分链数据收集和发送同时进行,可大大降低网络时延。当网络中某个节点失效死亡时,只对当前分链和链头链进行维护即可,维护成本低,鲁棒性高。但依然有以下不足:①交叉链多,成链陷入局部最优;②分链构造中后期链端为寻找下一跳未入链的节点易形成长链结构;③链头选取未考虑距离和位置问题易导致链头链形成超长链,加重数据逆传递[9]。

2 TTEMR算法

2.1 分链成链

首先对Sink附近的节点进行不入链操作,然后采用贪婪算法进行成链,但在成链过程中采用启发式算法进行优化,对孤立点[10]进行树型[11]结构化处理。

2.1.1 不入链处理

由于链的单向传递特点,会使部分节点集将数据向远离Sink的方向传递,然后通过某几个节点汇聚融合后再向Sink发送,这称为数据的逆传递。

因为Sink节点靠近WSN但不位于其内,若靠近Sink的普通节点不将其作为数据传递的下一跳,而是选择与距离较远的节点成链,则会造成该节点数据最终逆传递至主链头,不但加重了该分链和链头链能耗,而且增加了网络时延,所以合理分配Sink附近节点的传递路径可有效降低全网能耗。如图1所示,因为dbS≤dba、dcS≤dcd,所以节点b、c直接向Sink传递数据而不选择与其他节点成链。

图1 Sink附近节点路径处理

2.1.2 启发式算法

①消除链内交叉

最优链路中必定不含有交叉路径[12],因此对于一条链内出现交叉情况时要将它消除。如图2所示,找到两个交叉路径af和de,删除其连接后连接ae和df。

②消除链间交叉

虽然通过消除链内交叉可保证WSN局部区域不再出现交叉,但由于整个区域内存在多条链中,分链之间还会出现交叉情况,链间交叉是算法局部最优而非全局最优的直接表现。如图3所示,找到交叉链路bf和ec,删除其连接,建立bc和ef链接。

图2 消除链内交叉

图3 消除链间交叉

③消除长路径

长链的产生一般是由于静态规则化分建链空间或算法陷入局部最优造成的,原本相距较近的节点却因为所属空间不同而不能够加入同一条链,这造成了数据传递能耗浪费、时延增长。如图4所示,找到长链ab,删除ab连接,连接ac,并将节点b加入距离较近的节点f所在的链路。

图4 消除长链

设dbound为长短链界限值,定义如式(1),两节点间距离小于等于dbound则为短链,超过dbound则为长链。

dbound=αE(dij)

(1)

式中:α为长链系数,E(dij)为节点i到下一跳节点j距离的期望。根据文献[13]实验可知,α初始值为1.5时效果最好,但当遇到以下两种情况时,长链系数的取值应该适当增大:①WSN稀疏时,网络中短链较少,长链较多,导致成链数较多、孤立点较多,此时链的维护成本将增大。②在WSN运行的中后期,由于出现了大量节点死亡,导致网络节点间距增大,此时可适当增大长链系数避免形成过多分链和孤立点。

2.1.3 孤立点树型结构化处理

孤立点直接与Sink节点通信会造成能量损耗过快,因此将孤立点以合适的方式加入附近的分链才是首选,产生孤立点主要有下面几种情况:①在消除链内、链间交叉时,导致个别节点孤立于分链附近;②在网络边缘或稀疏区域产生的长链,通过删除长链会产生离周围分链都较远的孤立点;③中后期网络中节点不断死亡,导致产生距离过远的孤立点。

如图5(a)所示,节点d为消除交叉链时产生的孤立点,节点e为上述②、③情况产生的孤立点。文献[13]中对孤立点的处理是首先找到距离孤立点d最近的节点b,判断节点b的上一跳节点a和下一跳节点c到孤立点d的距离,将孤立点d插入节点b和距离较近节点a之间,形成如图5(b)所示的链路。

TTEMR算法运用树的思想,直接比较孤立点d到节点a、b、c的距离,建立如图5(c)所示距离较近的bd连接,b为父节点,d为其子节点。对于孤立点e,由于到周围节点距离都为长链,则寻找距离孤立点e最近的分链节点或Sink节点构建链路,如图5(c)建立ec链路,c为父节点,e为其子节点。

图5 孤立点入链

本文采用文献[14]中的能量模型,假设每个数据包有kbit的数据,则发送端消耗的能量为式(2):

(2)

(3)

接收端消耗的能量为式(4):

ERX=kEelec

(4)

数据汇聚融合消耗的能量为式(5):

EDA=kEda

(5)

式中:Eelec=50 nJ/bit,表示收发电路能耗;Eda=5 nJ/bit,表示单位数据融合能耗;dij表示节点i到节点j的距离;d0表示能量损耗的界限值。

设节点a为靠近链头方向,则图5(b)链路段bda能耗为式(6),图5(c)链路树dba能耗为式(7):

(6)

(7)

因为dab

2.2 链头链成链

2.2.1 选取主链头

在链式协议算法中,主链头和分链链头的选取会对WSN中节点数据的整体传递方向产生较大影响,若主链头和分链链头靠近Sink,则网络中数据总体向Sink方向移动;若主链头和分链链头远离Sink,则网络中数据总体向远离Sink方向移动,最后通过主链头转发至Sink,因此合理选取主链头和分链链头可减少WSN内的数据逆传递。

在COSEN算法中,主链头和分链链头的选取只考虑了剩余能量,这导致距离Sink较远的节点被选为主链头、不同分链中距离较远的两个节点可能会被选为相邻链头,形成如图6(b)中ed、db、主链头c到Sink这样的长链,且ed链会引起严重的数据逆传递。TTEMR算法综合考虑了节点剩余能量和到Sink的距离,根据式(8)在全网节点中选取主链头C0。

(8)

式中:Ei为节点i的剩余能量,di to S为节点i到Sink节点的距离,N为全网节点数,η越大被选为主链头概率越大。

2.2.2 选取分链链头

分链链头选取步骤如下:①令主链头C0所在分链编号为0,主链头所在的链称为主分链,主链头也是主分链的分链链头。

②确定距主分链最近分链的链头Ck。距离C0最近的非本链节点所在的链就是与主分链最近的分链,令该分链为当前链,链号为k,根据式(9)选取链头Ck。

③确定距当前链最近的分链的链头Ck+1。距离当前链链头最近的无链头非本链节点所在的链就是与当前链最近的分链,令该分链为当前链,链号为k+1,根据式(9)选取链头Ck+1。

④重复步骤③,直至每个分链确定链头。

(9)

2.2.3 链头链成链规则

TTEMR算法链头链成链规则如下:①若某一分链链头到主链头或其他分链链头的距离大于等于到Sink节点的距离,则应直接与Sink通信以减少数据逆传递。如图1,链头C3到相邻链头的距离d(C3,C0)≥d(C3,S)、d(C3,C1)≥d(C3,S),所以链头C3直接向Sink传递数据而不参与链头链成链。②采用贪婪算法以主链头为起始点,将其余各分链链头组成链头链;③对成链过程中产生的链内交叉按2.1.2①节消除链内交叉进行优化;④对成链过程中产生的孤立点链头作如下处理:(a)若相邻链头间为短链则将孤立点链头按2.1.3节孤立点树型结构化处理;(b)若相邻链头间皆为长链则首先寻找距离孤立点链头最近的相邻链头Ck(k=0,1,2,…),链头Ck所在分链编号k,然后寻找孤立点链头距离分链k上最近的节点j,将孤立点链头作为子节点加入分链k,j为其父节点,最后孤立点链头通过分链k中的普通节点中转传递数据至相邻链头Ck。

在数据传输阶段,各分链链头控制本链令牌,收集融合本链数据。主链头控制链头链令牌,收集融合各分链链头数据并最终传递至Sink节点。

3 算法仿真与分析

为了验证TTEMR算法的性能,本文对该算法进行了MATLAB 模拟仿真实验,并与LEACH、PEGASIS、COSEN算法进行对比。仿真区域为100 m×100 m,区域内节点随机分布且不能移动,当节点剩余能量低于1%后则认为该节点死亡,仿真参数见表1。

3.1 节点成链情况分析

图6(a)、6(b)分别为PEGASIS和COSEN算法的链式结构,可以看出这两种算法成链杂乱无章,交叉链、长链多。图6(b)中COSEN算法链头链几乎全是长链,其中ed链将数据向远离Sink方向传递,数据逆传递严重。图6(c)、6(d)分别为TTEMR算法底层分链结构和顶层链头链结构,有明显树型特征,节点间跨度小,成链区域自适应,分链长度适中且没有交叉链,长链较少,且长链长度比PEGASIS和COSEN算法中的长链短,图6(d)中链头数据总体向Sink方向传递,因为链头g到Sink节点的距离小于等于到其他链头的距离,所以链头g不参与链头链成链,有效避免了逆传递带来的能量消耗。

3.2 能耗分析

本文以全网节点向Sink发送一次数据为一“轮”,对比四种算法每轮存活节点数,从图7可以看出,TTEMR算法相对于LEACH、PEGASIS、COSEN算法,首节点死亡轮数和最后一个节点死亡轮数都有明显的延长,节点死亡轮数曲线在最上方。这是由于TTEMR算法采用了树型成链方法,优化了主链头、分链链头选取策略,有效减少了长链节点传输能耗和网络数据逆传递情况。

图7 每轮存活节点对比

从WSN开始运行到第一个节点死亡所经历的轮数称为稳定周期,从网络开始运行到50%的节点死亡所经历的轮数称为生命周期。由表2可知,TTEMR算法稳定稳定周期比LEACH、PEGASIS、COSEN提升约145%、227%、37%,生命周期提升约89%、44%、12%,在网络20%、80%节点死亡情况下,TTEMR算法仍比上述三种算法有较明显的提升。

由图8可知,在每轮收集数据后,COSEN算法全网剩余能量仅比PEGASIS略高,这是因为其并没有从根本上解决能耗浪费严重的长链和数据逆传递问题,而TTEMR每轮全网剩余能量均高于LEACH、PEGASIS、COSEN这三种算法,这表明TTEMR在网络节能方面更加优越。

表2 网络生存周期对比

图8 网络剩余总能量对比

3.3 单位链路段平均路径长度分析

本文称两个相连接的底层节点间的链路为单位链路段,则所有单位链路段路径长度之和除以单位链路段数量为单位链路段平均路径长度,简称平均路径长度。其反应成链规则的优劣,平均路径长度越短则成链规则越合理,传递数据越节约能量。

图9中,PEGASIS、COSEN、LEACH算法前期平均路径长度没有改变是因为网络中没有节点死亡,网络结构没有变化,而LEACH算法每几轮便重新随机选取簇头,导致网络结构变化频繁,因此平均路径长度变动幅度大,且LEACH算法的平均路径最长,这是因为其普通节点以单跳方式向簇头传递数据;COSEN算法的节点间平均路径比PEGASIS略短,因为其未从根本上减少交叉链和长链;而TTEMR算法的平均路径长度较其他算法有较明显降低,这是因为在链路中采用了启发式算法和树型结构优化,消除了交叉链,减少了长链路。

图9 单位链路段平均路径长度对比

4 结束语

本文在分析了LEACH、PEGASIS、COSEN协议算法优缺点的基础上,提出了TTEMR算法。TTEMR将网络构造成双层树型多链路结构,分链和链头链均通过启发式算法优化,并对网络孤立点进行树型结构化处理,降低了数据传递路径长度;通过优化主链头和分链链头的选取策略及成链规则,并对Sink附近的普通节点和链头作不入链操作,减弱了网络的数据逆传递。本文对每轮节点的存活数量、网络的稳定周期和生命周期、每轮剩余总能量及单位链路段平均路径长度这五项性能指标进行仿真实验,仿真实验结果显示,TTEMR算法在上述五项性能指标对比中表现比其他三种算法优异。但TTEMR需要构造树型结构,计算量比COSEN要大,链头链需要多跳中转,所以延迟略大于COSEN,在实时传输场景下有所受限。