基于簇链结构的节能路由协议

吴子彧, 俞　晖, 归　琳

(上海交通大学 电子信息与电气工程学院,上海 200240)



基于簇链结构的节能路由协议

吴子彧, 俞晖, 归琳

(上海交通大学 电子信息与电气工程学院,上海 200240)

摘要:随着各类智能可穿戴设备越来越多地在无线传感器网络(WSN)中扮演着环境信息采集与传输的角色,为保证网络的性能,路由协议除了兼顾能量效率,还应适应移动的网络环境.然而在移动场景中,由于频繁的拓扑更新,传统的路由方案不能很好地应对移动性所带来的能耗与丢包的挑战,网络性能将会降低.因此,提出了一种新的基于簇链结构的路由协议(CCBRP),利用簇结构和簇头链实现采集信息的汇聚,并由链首节点完成至汇聚节点的最后一跳传输.在此基础上,通过移动节点周期性的成员更新机制完成移动管理与簇头切换.仿真结果表明该路由协议在网络生命周期和数据包传递成功率方面均有优异的表现,且在能量效率和数据传递间达到了性能的平衡.

关键词:路由协议; 簇链结构; 能量效率; 移动管理; 移动无线传感器网络

0引言

无线传感器网络(WSN)[1]是由大量低功耗、多功能的传感节点,通过无线通信的方式形成的多跳自组织网络系统,节点采集的信息通过网络的协同处理和传输,最终抵达汇聚节点,并为终端用户所接入.随着物联网技术的发展与进步,WSN作为连接物理世界和信息空间的重要媒介,在环境监测和工业控制等领域获得了广泛的关注与应用.但受限于节点电池能量的有限性,如何降低能耗、延长网络生命周期成为WSN研究的重要方向,因此能量效率成为衡量网络路由协议性能的关键指标.

随着各类移动智能设备的普及应用,动态信息的交互需求大大增加,如何在移动的场景下实现信息的高效汇聚与传输成为亟待解决的应用课题.在移动网络的环境中,传统的静态路由协议[2]无法应对由于节点移动性和拓扑更新所带来的丢包和网络开销等问题,因此适合移动环境的动态路由协议设计成为新的研究方向.

LEACH和PEGASIS作为分簇路由的典型代表,分别利用簇和链的结构完成数据的汇聚,具有节能、简单和便于分布式计算等优点.LEACH[3]协议中,簇头节点完成本簇内数据的接收与汇聚,并将融合的数据发送给汇聚节点.和LEACH相比,PEGASIS[4]由于其沿链的数据传递与融合,在能量效率方面取得了较为明显的进步,但由于网络节点链状结构所导致的显著延时,使其不能适用于实时性要求较高的应用.因此,基于这两类经典路由协议的优化与改进适应了很多新的网络环境,如CBL[5]实现了LEACH和PEGASIS的融合,通过节点成簇和簇间多跳的路由形式完成大范围覆盖的网络环境下数据的传递与收集,其中簇头节点的轮流选举与链首节点的随机选择保证了网络节点均匀的能耗分布,但是频繁的结构更新给网络带来了额外的开销,且未考虑节点剩余能量与地理位置等信息的随机选择并非是一种最优决策,因此依旧存在优化的空间.LEACH-Mobile[6]提供了一种移动节点的成员更新机制,在TDMA某预分配的时隙内,移动节点根据对簇头发送消息的接收情况,确认能否与其进行通信,如果不可以则在下一时隙进行簇头切换,保证移动网络下数据的准确传递.

本文作者基于混合移动与静态节点的无线传感网场景,提出了一种新的基于簇链的路由协议(CCBRP),利用网络节点的簇链结构和移动管理机制,实现移动环境下数据的汇聚与传输.在协议的每一个操作周期,建立阶段完成簇头选举与簇链结构的建立,稳态阶段实现簇内和簇间数据的融合与传递,并最终通过链首发送至汇聚节点.本协议通过簇链分级结构有效降低了网络因数据传输而带来的能量损耗,且链首资格判决机制在最后一跳传输节点选择中的应用,进一步提升了网络的能量效率,而移动节点的成员更新机制保证了数据包的成功传递.

1系统模型

1.1网络模型

研究场景为包含静态与动态节点的WSN,其中,静态传感节点随机部署在网络区域内,汇聚节点位置固定且距离网络较远;动态节点以随机运动模型[7]在该区域内运动,每一时刻,在(0,2π]内随机选择一个方向运动距离为d,如果抵达边界位置,会在边界处镜面反射运动.假设所有的传感节点都是能量受限的,具有相同的初始能量和通信能力,同时每个节点均以固定速率感知周边环境,并在每一个预分配的TDMA时隙内始终有数据要传送,且会依据传输距离自动调节发射功率.同时,假定无线传输信道具有对称性,即在给定信噪比的要求下,某一消息从节点i到j的传输能耗与从节点j到i的传输能耗相同,为降低相互间的数据干扰,分别利用TDMA和CDMA机制实现簇内和簇间的数据传输.

1.2能耗模型

采用一阶无线电模型[3]来描述通信的能量消耗,在自由空间模型下,传感器节点发送l比特消息,传输距离为d,所消耗的能量为:

(1)

传感器节点接收l比特信息所消耗的能量为:

(2)

其中,εamp是信号放大器的放大倍数,Eelec是发送电路和接收电路所消耗的能量,在自由空间的信道模型条件下,信道传输的能量衰减为d2,即信号的传输距离越短,能量损耗越小.

此外,对数据信号进行融合等处理也将损耗能量[8],由Eda表示融合单位长度数据信号所消耗的能量.因此对于簇头节点,融合本地M个簇成员所采集的数据信号所消耗的能量为:

(3)

2路由协议

CCBRP路由协议按操作周期进行执行,每一周期包含建立阶段和稳态阶段.为降低系统的开销,在时长上,稳态阶段应大于建立阶段,如图1所示.

图1　路由协议的操作周期

结合操作周期的时间分布,图2描述了网络的拓扑结构和协议的操作过程.在建立阶段,分布式选举产生的簇头会招募本簇成员节点,并依照贪婪算法在簇头间形成链状结构.由于分布式簇头选举会导致簇头数目的不确定性,因此如果当前周期的簇头数目Nch小于某一阈值,考虑到因簇头分布的稀疏性而带来的传输能耗增加,为保证系统的能耗性能,定义该结构建立过程无效.因此建立阶段会包含若干无效过程,称之为预建立过程,并最终以一次有效的簇链结构形成作为结束.在稳态阶段的每一帧,首先根据链首资格判决机制,确立当前簇头链的链首节点.当簇内数据完成传输与汇聚后,链首节点利用令牌传输机制,开启沿链的数据传递与融合,最终数据经链首节点发送至汇聚节点.在每一帧的帧尾,移动节点通过成员更新机制完成簇头切换与移动管理.Ncl指代当前簇头链中符合链首条件的簇头节点数,也就是当前周期稳态阶段所包含的帧数.显然,簇链结构的建立降低了数据传输与汇聚所消耗的能量,且分级结构更加便于节点的移动管理.

图2　网络拓扑结构

2.1建立阶段

在建立阶段,各传感节点基于所示阈值[9]T(n)进行分布式簇头选举,独立判断是否在当前周期担任簇头角色,阈值公式为:

(4)

其中,P指代网络预定义的簇头节点比例(5%),rs表示当前节点连续未被选为簇头的周期数,Ei和Emax分别表示当前节点的剩余能量和网络节点中剩余能量的最大值.由于簇头间沿链的数据传递与融合,全局参数Emax可被网络中所有节点获取.

选举所得的簇头首先与汇聚节点通信,并由汇聚节点选择距离自己最远的簇头节点作为成链操作的起始节点.每一个簇头节点依次广播消息以搜寻距离自己最近的邻居簇头,作为簇头链邻居和链上的下一跳节点,该过程依次执行直到所有簇头节点均包含在该链中.非簇头节点根据接收到的来自不同簇头广播消息的信号强度选择对应的簇头,并发送请求消息申请加入该簇,消息包含节点的ID和节点的剩余能量.显然,各个簇头节点只需广播一次消息即可完成簇成员招募和簇头链建立,节省了网络能耗,同时降低系统开销.

2.2数据传输与汇聚

考虑到频繁的网络簇链结构建立会给系统带来额外的开销和能耗,因此为提高已形成簇头链的利用效率,本文作者提出链首节点资格判决机制,通过选定符合能量与位置条件的簇头节点担任链首,来完成最后一跳的数据传输.

2.2.1能耗分析

利用平均能量Eave作为链首节点资格判决机制的判决标准,即在一个周期内,数据由传感节点传输至汇聚节点所消耗的平均能耗.有如下3种资格判决策略:

(1) 每一周期只对应一个链首节点

(5)

(2) 一个周期内,所有簇头节点轮流担任链首角色

(6)

(3) 符合判决条件的簇头节点担任周期稳态阶段中各个帧的链首角色

(7)

其中,Ec,Ef和Et分别表示在网络簇链结构建立阶段、数据汇聚阶段以及最后一跳传输过程中所消耗的能量.可以分别表示为,

(8)

(9)

(10)

其中,lA和l分别表示广播消息和采集信息的大小,Tr表示每个传感节点的传输范围,dt表示簇成员节点与对应簇头的距离或簇头链上相邻簇头邻居节点间的距离,nk表示融合数据的数量,ds指代每个簇头节点与汇聚节点的距离.

显然,策略(1)未能充分利用网络中已形成的簇链结构,导致资源的浪费.关于策略(2),尽管保证了网络内所有节点的能耗均衡,但是一些距离汇聚节点较远或剩余能量不足的簇头节点可能会在数据传输过程中,因能量耗尽而导致簇内数据丢失.综上可知,策略(3)通过对节点剩余能量与位置信息的分析判断,保证了由符合条件的簇头节点完成最后一跳的数据传输,降低平均能耗,延长网络的生命周期.

2.2.2可靠性分析

在沿链的数据传递过程中,每个簇头节点都会接收到上一级节点的数据并进行融合,然后再发送给下一跳的链邻居节点.但发送节点不会立即清除已发送的数据,而是等待接受节点的信息确认反馈,如果一段时间内没有接收到反馈信号,则表明该数据发送丢失,重发一次,如果依旧不成功,则通过路由维护,将数据传送给簇头链的下一跳节点,保证链的完整有效性.

2.3移动性管理

利用移动节点进行入簇请求消息的周期性广播,以此来搜寻新的簇头节点并更新当前簇成员信息.在稳态阶段的簇内数据传输过程中,簇头节点通过本地数据请求消息的传递,开启簇内信息的传输汇聚,只要簇成员节点接收到请求信号,便会根据TDMA时隙表在预分配的时隙内传递采集信息.

对于移动节点,由于位置的变更,其接收到原有簇头节点数据请求消息的信号强度会发生变化,因此首先根据信号强度进行本地的位置更新,即如果移动节点朝向簇头移动,接收到的信号请求消息强度增大,因此可以降低发射功率传递采集信息;反之如果远离簇头运动,需提高发射功率以保证数据包的成功传输.当完成链首节点最后一跳的数据传输后,在当前帧尾,由需要进行位置与成员更新的移动节点,即那些因移出当前簇范围或远离原有簇头的移动节点,主动广播入簇请求消息,根据各个簇头节点反馈消息的强度,进行簇头重新选择,并完成成员更新信息的交互.簇头节点会根据成员变化更新本地的簇信息,重新规划TDMA时隙表,并从下一帧开始按照新的时隙表进行簇内数据的传递与汇聚.

2.4簇头链路由维护

在提出的路由方案中,由于最后一跳传输所需的能量较多,可能会导致簇头节点的意外死亡和簇头链的失效,因此利用链首节点的令牌传输机制进行簇间多跳路由的维护.

当链首节点通过令牌传输进行沿链数据融合请求时,如果一段时间后没有信息反馈,则通过令牌重传以确认邻居簇头的死亡并同时寻找死亡簇头的链邻居节点.由于此时各个簇头已经完成了簇内数据的汇聚,因此利用令牌消息的广播来连结当前簇头节点和死亡节点的上一跳链邻居,完成簇头链的维护,并在当前帧结束后直接开启下一周期,重构网络的簇链结构.

3仿真结果与分析

3.1仿真实验

表1　仿真参数表

为研究所提出路由协议的性能,通过MATLAB进行仿真实验,实验参数设置如表1所示.

本文作者首先定义3个度量标准来衡量路由协议的能量效率与数据包传递成功率,分别是网络存活的节点数目(NAN),网络功能性生命周期(FL)以及数据包接收成功率(SPRR).网络存活的节点数在每一次汇聚节点接收到数据后进行统计,称之为一轮.网络功能性生命周期与存活节点数直接相关,而且其定义也因网络场景而异.在仿真实验中,将网络从开始运转到20%的传感节点死亡所持续的时间定义为网络的功能性生命周期,单位是轮.数据包接收成功率表示簇头实际的数据接收率与预期接受率之比.因节点移动性而导致的丢包主要发生在簇内数据传输阶段,因此在衡量数据包传递性能时,只考虑簇成员节点与对应簇头之间的数据传递.

网络场景中,规定10%的节点是移动的,以此来仿真可穿戴设备和移动智能终端,同时考虑到移动设备的续航能力以及移动簇头给网络协议带来的复杂性,规定所有的移动节点均不可被选举为簇头.

3.2实验结果分析

3.2.1网络生命周期分析

为了衡量所提出路由协议的能量效率,选取LEACH和CCBRP-L两种路由协议作为参考对象,其中CCBRP-L相比CCBRP,缺少了链首节点的资格判决,未定义操作周期中的预建立过程与稳态阶段多帧概念,即依照3.2.1中的策略(1)进行链首节点的选择和数据的汇聚.通过上文分析可知,频繁的簇链结构建立会带来网络开销的增加,而且缺乏预建立过程,会导致在某些簇头选择不合理的情况下依然进行数据的远距离传输与汇聚,带来能耗的剧增。

以NAN和FL作为度量准则对比分析上述3种路由方案,结果由如图3(a)可知提出的路由方案CCBRP显著延长了网络的生命周期,且链首判决与协议周期的设计使得相较于CCBRP-L,网络功能性生命周期延长80%.

3.2.2链首判决机制分析

对照3.2.1中的分析,通过NAN和FL2个度量参量来验证链首判决机制的有效性,即实现平均能耗Eave的降低.在仿真实验中,定义如果簇头节点符合下述条件,即到汇聚节点的距离在当前周期所有簇头中最远且剩余能量低于当前周期簇头节点的平均能量,或剩余能量最低且到汇聚节点的距离大于当前周期簇头节点到汇聚节点的平均距离,则不满足链首节点的条件,不适合完成最后一跳的传输.

如图3所示,依照上述准则进行链首判决条件下的路由协议(CLQJ)对应的NAN曲线始终高于所有的簇头节点均可成为链首条件下的路由协议(ALL),而且FL也提升了9%.因此可以证明提出的链首判决机制在提高路由协议能量效率方面是有效的.

3.2.3移动性管理机制分析

(1) 方法对比.作者评估了两种移动管理方案CHB和MU,其中,CHB利用簇头的消息广播来招募移动节点,MU则是利用移动节点广播入簇请求消息,通过簇头节点的反馈来进行成员的更新.考虑到簇头在提出的路由协议中所承担的责任与消耗的能量,不再适合作为移动管理阶段的主体,因此通过移动节点进行广播可以有效平衡网络的能耗分布.而且经过传输阶段的本地位置更新之后,只有需要进行成员更新的节点才会广播请求消息,因此和被动的重成簇方案CHB相比,MU方案在能效方面更加性能更佳.

如图3(c)所示,MU对应的NAN曲线始终位于CHB曲线的上方,因此,可以证明通过移动节点广播入簇请求消息来实现移动管理的机制拥有更高的能量效率.

图3　路由协议的能量效率分析

(2) MU性能分析.利用成员更新机制来保证数据包的正确传递,但是必然会带来额外的能量消耗.因此在移动场景下分别度量两类路由协议的FL和SPRR:有CCBRP和无移动管理机制的静态路由协议(CCBRP-S).在CCBRP-S的应用场景中,节点移动会导致移动节点与对应簇头间距离的变化,但移动节点不能进行位置更新来调节发射功率和簇头切换,因此数据包的传递无法得到保障,且用更高的发射功率来完成短距离传输,也降低了能量的效率.而且,随着移动节点比例的增加,潜在的簇头比例降低,不均衡的能耗分布也将导致FL的缩短.

如图4(a)所示,随着移动节点比例的增加,对比的两个路由协议的FL曲线均有下降,但CCBRP-S对应的FL曲线始终高于CCBRP.但就数据包传递性能来看,如图4(b)所示,CCBRP保持了一个较为稳定的成功接收率,而CCBRP-S的接收成功率随着移动节点比例的增加急速下降.因此可以得出结论,提出的路由方案CCBRP在数据包传递方面有较稳定的表现,而且因移动管理和保障传递成功率而付出的额外能量损耗也在可接受的范围内,即在能量效率与数据包传递之间达到了较好的平衡.

图4　移动管理机制分析

4结束语

本文作者提出了一种新的基于簇链结构的路由协议,用于提升网络的能量效率并支持节点的移动性.协议的操作按周期进行,包括建立阶段和稳态阶段.在建立阶段完成分布式簇头选举和簇链结构的形成;在稳态阶段各个帧内,具有链首资格的簇头节点将融合的采集信息传输至汇聚节点;且在每帧的结尾,由需要进行成员更新的移动节点主动广播请求消息来完成簇头切换.仿真结果表明,CCBRP路由协议延长了网络的功能性生命周期同时在移动网络环境中保证了数据包的接收成功率,且在能量效率和数据包传递间达到平衡.

参考文献:

[1]Yick J,Biswanath M,Dipak G.Wireless sensor network survey [J].Computer networks,2008,52(12):2292-2330.

[2]Goyal D,Tripathy M R.Routing protocols in wireless sensor networks:a survey[C]//IEEE.Advanced Computing & Communication Technologies (ACCT) 2012 Second International Conference on.Rohtak:IEEE,2012.

[3]Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[C]//IEEE.Proceedings of the 33rd annual Hawaii international conference on.Hawaii:IEEE,2000.

[4]Lindsey S,Raghavendra C S.PEGASIS:Power-efficient gathering in sensor information systems[C]//IEEE.Aerospace conference proceedings 2002.Big Sky:IEEE 2002.

[5]Tabibzadeh M,Mehdi S,Fazlollah A.Hybrid routing protocol for prolonged network lifetime in large scale wireless sensor network[C]//IEEE .Information and Multimedia Technology,2009.ICIMT'09.International Conference on.Jeju Island:IEEE,2009.

[6]Kim D S,Chung Y J.Self-organization routing protocol supporting mobile nodes for wireless sensor network[C]//IEEE.Computer and Computational Sciences 2006 IMSCCS'06 First International Multi-Symposiums on.Hanzhou:IEEE,2006.

[7]Ren B,Ma J,Chen C F.The hybrid mobile wireless sensor networks for data gathering[C]//ACM.Proceedings of the 2006 international conference on Wireless communications and mobile computing.Vancouver: ACM,2006.

[8]Wang A,Heinzelman W B,Sinha A,et al.Energy-scalable protocols for battery-operated microsensor networks [J].Journal of VLSI Signal Processing systems for signal,image and video technology,1999,29(3):223-237.

[9]Handy M J,Haase M,Timmermann D.Low energy adaptive clustering hierarchy with deterministic cluster-head selection[C]//IEEE.Mobile and Wireless Communications Network,2002.4th International Workshop on.Stockholm:IEEE,2002.

(责任编辑：顾浩然)

Cluster chain based energy efficient routing protocol for moblie

WSNWU Ziyu, YU Hui, GUI Lin

(School of Electronic Information and Electrical Engineering,Shanghai Jiao Tong University,Shanghai 200240,China)

Abstract:With the ubiquitous smart devices acting as mobile sensor nodes in the wireless sensor networks(WSNs) to sense and transmit physical information,routing protocols should be designed to accommodate the mobility issues,in addition to conventional considerations on energy efficiency.However,due to frequent topology change,traditional routing schemes cannot perform well.Moreover,existence of mobile nodes poses new challenges on energy dissipation and packet loss.In this paper,a novel routing scheme called cluster chain based routing protocol(CCBRP) is proposed,which employs a combination of cluster and chain structure to accomplish data collection and transmission and thereafter selects qualified cluster heads as chain leaders to transmit data to the sink.Furthermore,node mobility is handled based on periodical membership update of mobile nodes.Simulation results demonstrate that CCBRP has a good performance in terms of network lifetime and packet delivery,also strikes a better balance between successful packet reception and energy consumption.

Key words:routing protocol; cluster chain structure; energy efficiency; mobility management; mobile wireless sensor network

中图分类号:TN 929.5

文献标志码:A

文章编号:1000-5137(2016)02-0215-08

通信作者:俞晖,中国上海市闵行区东川路800号,上海交通大学电子信息与电气工程学院,邮编:200240,E-mail:yuhui@sjtu.edu.cn

收稿日期:2016-03-04