基于权重和均衡能量的ZigBee改进路由算法

狄万昕,江 明

(安徽工程大学电气工程学院,安徽芜湖 241000)



基于权重和均衡能量的ZigBee改进路由算法

狄万昕,江 明∗

(安徽工程大学电气工程学院,安徽芜湖 241000)

摘要:针对ZigBee路由协议中存在路由不稳定、时延大以及能量不平衡等问题,提出了一种基于权重和均衡能量的ZigBee改进路由算法(ZigBee-new)．在满足权重的路径查找中优先挑选能量高的节点充当中继,而低能量的节点反馈能量状态,由源端主动断开旧链路,进而转变路径．采用NS2平台对ZigBee和ZigBee-new进行了仿真实验和性能分析,仿真实验结果表明,改进后的ZigBee-new路由算法比较明显地改进了原ZigBee路由算法的性能．

关 键 词:ZigBee路由协议;移动自组织网络;权重;均衡能量

无线网络(Wireless Sensor Network)[1-3]是一种不需要基础设施的自组织和自管理网络,网络中所有节点同时具有终端和路由器的功能,节点可通过路由发现机制转发分组,并进行路由维护．随机部署的节点可能由于自然因素损坏或者被人为干扰,需要补充能量,但是网络中的节点通常由电池供电,使得能量不便再次添加,因此,设计一个好的路由协议要考虑维护网络的稳健性和网络中能量损坏的均衡性．

为了满足ZigBee[4-8]网络低功耗、高可靠性、低成本的设计目标,在ZigBee网络按节点身份的不同,采用了两种路由协议:按需距离矢量路由(AODV-jr,Ad-hoc On Demand Distance vector Routing)和按照父子关系选择路径方式的Cluster-Tree路由算法．使用Cluster-Tree路由算法带来了大的数据传输延时和分组递交率的降低．使用AODv-jr路由算法时,网络中的数据传输时延降低,分组递交率得到提高,但是过多的路由发现可能造成更多的能量消耗．

现有研究表明[9-12],传统的ZigBee路由协议对延迟、带宽、丢包率和能量等都没有加以约束,即都没有考虑到QOS因素的限制,如时延、带宽、能量的差异等问题．这会造成网络的节点拥塞、时延大等缺点,某些节点的能量被很快地消耗,缩短了网络的生存周期．为此,在ZigBee路由协议的基础上,提出了基于权重和均衡能量的ZigBee改进路由算法ZigBee-new．通过引入一些QOS参数的约束,以更符合在实际网络中对服务质量的进一步要求．

1 ZigBee-new的算法

1．1 基于权重的策略

在WSN场景下,为了准确讨论QOS问题,把WSN网络看做一个加权图G(V,E)．其中,V可以表示为Ad hoc移动节点的集合;E可代表Ad hoc移动节点间形成的链路的集合;且每一个Ad hoc节点的传输半径一样．假使在已知的源节点与目的节点之间存在路径K(s→i→…→j→d),该路由满足跳数、能量以及链路质量这3个QOS约束条件．则该WSN路由协议可以抽象为在加权图G(V,E)中,在已知的源节点与目的节点之间寻找满足QOS约束要求的可行路由,然后通过计算各条可行路由的路由权重值Weight,再选取Weight值最大的可行路由进行数据传输．权重大的节点获得转发路径的优先级高,更容易被选中成为网络中的中继节点．

1．2 基于链路质量反馈的策略

在路径维护的过程中同时预测链路的生存状态．传统ZigBee路由协议AODV-JR建立路由是参照最小跳数作为度量参数的,忽略了路由上链路的传输质量,造成路由整体性能较差．链路质量的好坏取决于节点繁忙程度,其表示了节点无线信号使用的连续程度,根据无线信道的特性,信道越繁忙则传输质量越差．该参数可以通过统计路径上所有节点的空闲时间Tidk与工作时间Tbusy比得到,即:

1．3 基于均衡能量的策略

当能量低于某一设定值或者发生链路断开的情况时,标记链路的状态,置flag为0．在数据包携带节点的能量信息进行传播的过程中,当节点的能量低于阀值时,认为节点的能量将消耗完,该节点携带低能量的信息被其他节点接收并最终转发至数据包的源节点．当源节点接收此数据包时,从路由表中剔除低能量节点的链路,再重新发起路径请求,寻找更优的路径充当中继．能量阀值的反馈效果对网络的链路状态起到了警示作用,从而让源节点主动变更路径．利用节点的能量特性引入一个参数ETsd(能量的阀值Threshold),系数K为一个和时间成正比的函数,即:

2 基于权重和均衡能量的ZigBee改进路由算法

2．1 数学模型

节点距离协调器的跳数越多,链路代价就越大,因此,在链路的选择过程中,跳数越少越好．将一跳的权重设为β,即路径上每多1个节点其在跳数上的权重就大．节点剩余能量过低说明信道质量太差,这种链路在网络中十分不稳定,因此,在选路过程中要避免通过该类链路通信．仅当节点剩余能量达到一定阈值时,链路信道质量相对较好,链路代价较小,可以作为通信链路．为了对节点碰撞、负载情况进行很好地描述,基于网络测量技术得到最近60 s内的忙与空闲时间之比Tidk/Tbusy,该值越高表明节点越繁忙．

(1)算法的参数模型．为了方便研究,把Ad Hoc网络定义为图G＝(V,E,t),其中,V为节点;E为边; t为边的权值,表示链路的剩余时间,即一条边还能保持通路的时间值．

(2)路由权重函数．为了选择出最佳路由,需要构建一个路由权重函数,t(i,j)代表节点i与j之间链路的剩余时间值．该函数的表示形式为:节点剩余能量Ei、跳数H、节点繁忙程度B,3个因素结合形成路由代价Cti．路由度量计算如下,定义在t时刻,链路通过节点i的代价为:

式中,Ei表示当前时刻节点i的剩余能量,可从节点中直接获取;E为节点初始能量;Hi为跳数;β是加权因子0≤β≤1．

考虑链路质量,则t时刻路径代价为:

式中,Bti为t时刻节点所处物理信道的评价繁忙程度,Bti＝Tidk/Tbusy．

最后选择的路由为F＝min{Dj|j∈Q}的路径,其中Q为可选路由集．

试验中β的值为0．6,取值为试验测试选择的经验值．

从表示形式可看出,此路由权重函数由两部分组成．跳数和能量之所以将跳数也作为代价函数的参数之一,是因为如果只将能量作为函数的考虑因素,虽然可以起到延长网络生存时间的作用,但网络的其他一些性能将会恶化很多．路由的跳数对节省节点能量也起一些作用,数据传输时所用路由的跳数越少,路由就越稳定,越不容易发生路由断裂的情况,从而有效地避免数据重传以及再次发起路由发现过程,这对于节点移动性较强无线网络作用尤为明显．

(3)加权因子．加权因子β决定了跳数和能量这两个参数在路由权重函数中的比重．CM MBCR协议根据网络中节点剩余能量的不同情况采取不同的路由选择策略．借鉴这一思想,加权因子的值将根据路由候选集中各条路由组成节点的剩余能量情况来确定．

假设网络中所有节点的初始能量值相同,则有:

式中,vn、l表示路由rn中的节点;p(vn,l)表示节点vn、l的剩余能量;Po表示节点的初始能量．

可以看出,当各条路由中节点的能量状况较好时,β值较大,此时跳数在路由权重函数中所占的比重较大．该算法倾向于选择跳数较少的路由(反之,当能量状况较差时,β值较小),此时能量参数所占的比重较大．该算法倾向于选择有效生存期较长的路由,从而起到保护剩余能量较低的瓶颈节点,尽可能延长网络生存时间的目的．

2．2 路由算法的描述

该算法的前提是基于网络中所有链路均为双向,且节点可以随时提供剩余能量的假设．

假设S为源节点,D为目的节点．一次数据传输过程的主要步骤如下:

(1)利用ZBR路由机制进行路由发现,但在报文中需添加节点最小剩余能量域re、链路最小剩余时间域rt与节点剩余能量和域sum;

(2)D开启一个定时器,保存该时间内收到的所有RREQ报文中的路由;

(3)D根据路由信息计算出每条路由的路由权值Di,选出具有最大权值的路由F;

(4)D沿反向路由发送RREQ报文到S,进行数据传输;

输入:节点集合和权重参数Di

输出:优化的逻辑树

1 for i←1 to n do//n为要加入的网络节点数

2 Di＝0;//Di位节点i到达协调器的总代价

3 m＝Scan AvailableNetwork();//搜索可加入的网络数目m

4 if m＝＝0 do//如果节点i周围无可加入的节点

5 Node[i]．Sleep(100);//则让节点休眠100 ms

6 Continue;//循环跳入下一个待加入节点继续进行

7 for j←1 to m do

8 if Ei＞ETsd do//节点剩余能量大于节点的能量阀值

9 cij＝0

10 for enery node k in Path[j]do

11 cij＝cij＋Dk

12 k加入到TempPath[j]链表中;

13 end for

14 else do

15 cij＝∞

16 end for

17 选择使得cij最小的可接入节点j作为父节点加入,并使Di＝cij

18 将节点i连接到父节点j上构成逻辑树;

19 Path[i]＝TempPath[j];

20 end for

2．3 仿真工具和仿真参数的设置

目前无线自组网的路由协议仿真国内外大部分科研院校都采用NS2．移植算法在NS2框架下,配置的场景如下:CBR为业务源的通信场景文件的数据流包括一个50个移动节点、10对通信连接和每秒钟发送2个的分组．移动场景设置为一个具有50个节点、节点在每个地点停留0秒(即不停留)、最大移动速度20 m/s、仿真时间300 s、长1 000 m和宽300 m的移动场景文件．其中暂停的时间可变,用于比较ZigBee路由协议改进前向的参数性能．仿真参数列表如表1所示．

在实验过程中,选用setdest工具设定节点传输场景文件和cbrgen工具生成传输负载,使用awk工具来说明tcl脚本生成的trace文件,最后使用Matlab工具绘图．

表1 仿真参数列表

2．4 仿真结果与分析

ZigBee和ZigBee-new分组投递率对比如图1所示．由图1可知,当暂停时间越长表明节点移动性越慢,当节点的移动暂停时间为300 s,而仿真的总时间为300 s,表明节点不移动,此时分组投递率的成功率越高．当节点的移动暂停时间为0 s时,节点一直在移动,此时分组投递率的成功率较低,丢包率比较明显．ZigBee-new由于考虑基于链路质量的反馈作用,避开了繁忙节点,相对于原ZigBee算法选出的路径更加稳定,表现为接收的分组投递率高．

ZigBee和ZigBee-new平均延时对比如2所示．由图2可知,暂停时间越长表明节点移动性越慢、路由越稳定,端到端的平均延时越小．ZigBee-new考虑到删除带宽较小、延时较大、跳数较大的路径,剔除了一些不满足最佳QOS的次要路径,实现选出路径为优化后的结果,表现为ZigBee-new端到端的延时更短．

图1 ZigBee和ZigBee-new分组投递率对比

图2 ZigBee和ZigBee-new平均延时对比

ZigBee和ZigBee-new不同节点剩余能量对比如图3所示．由图3可知,ZigBee-new算法选择的路径更加稳定,用于路由发起的控制包减少,网络中的能量避免了因侦听到过多的控制广播而产生大量能量消耗．使得ZigBee-new相比ZigBee,网络中节点剩余能量得到更好地节省,进一步延长了网络的生存时间．

ZigBee和ZigBee-new网络抖动性比较如图4所示．由图4可知,ZigBee-new由于考虑到网络中节点的能量以及链路的质量通信情况,相比ZigBee进行了预警信息,并且主动变更了即将断开的链路与通信质量不佳的链路,因此路径变更的概率减小,表现为ZigBee-new算法网络稳定,抖动幅度小．

图3 ZigBee和ZigBee-new不同节点剩余能量对比

图4 ZigBee和ZigBee-new网络抖动性比较

3 结论

ZigBee是为WSN网络设计的路由协议,但是没有QOS保障,当节点存在能量差异时,容易选中能量低的节点充当中继,从而缩短网络的生存时间,且低能量节点能量将耗尽时,也无法感知网络的链路即将变更信息．提出了一种ZigBee-new路由算法,该算法在查找路径正向发送路由请求的过程中,选择链路质量、跳数、能量3个方面的因素,满足时延和带宽要求,并且剩余能量大的节点充当中继节点的权重高、延时低,从而获得比较高的优先级．在数据包发送的过程中,低能量的节点反馈能量状态,并且剩余能量大,获取链路质量好的反向路径．当能量较低或者通信质量较差时,主动报告源端,源端主动断开旧链路,变更新路径．仿真结果表明,改进后的ZigBee-new算法有效地改进了ZigBee路由不稳定、时延大和能量不平衡等缺点,有效地提升了ZigBee的性能．

参考文献:

[1] 柯志亨,程荣祥,邓德隽．NS2仿真实验-多媒体和无线网络通信[M]．北京:电子工业出版社,2009．

[2] 孙利民,李建中．无线传感器网络[M]．北京:清华大学出版社,2010．

[3] 高蔚蓝．ZigBee:新一代无线网络的综述[M]．北京:中国学术期刊电子出版社,2010．

[4] 胡柯,郭壮辉,汪镭．无线通信技术ZigBee研究[J]．电脑知识与技术,2008(6):1 049-1 051．

[5] 徐小涛,孙少兰,胡东华,等．ZigBee协议的最新发展[M]．北京:中国学术期刊电子出版社,2009．

[6] 耿萌,于宏毅,张效义．ZigBee路由协议分析与性能评估[J]．计算机工程与应用,2007(43):116-120．

[7] 张栋．ZigBee无线传感器网络路由协议研究与优化[D]．济南:山东大学,2009．

[8] 李文仲,段朝玉．ZigBee无线网络技术入门与实战[M]．北京:北京航空航天大学出版社,2007．

[9] 徐沛成,胡国荣．改进的ZigBee网络路由算法[J]．计算机工程与设计,2013,34(9):3 019-3 023．

[10]徐艳,王茜,武剑．ZigBee路由协议优化仿真研究[J]．计算机仿真,2013,30(60):292-295．

[11]K K Lee,S H Kim,H S Park．Cluster label-based ZigBee routing protocol with high scalability[C]//The Second International Conference on Systems and Networks Communicatio(ICSNC 2007),Cap Esterel:Editions Masson,2007,240:12-16．

[12]A Bhatia,P Kaushik．A cluster based minimum battery cost AODV routing using multipath route for ZigBee[C]//Proceedings of the 2008 16 International Conference on Networks(ICON 2008),New Delhi:Eastem Book Linkers,2008:1-7．

An improved ZigBee routing algorithm based on weight and equilibrium energy

DI Wan-xin,JIANG Ming∗
(College of Electrical Engineering,Anhui Polytechnic University,Wuhu 241000,China)

Abstract:Unstable routing,long delay and unbalanced energy existed in ZigBee routing algorithm．Aiming at these shortages,based on weight and equilibrium energy,an improved routing algorithm is proposed．Nodes with higher energy are selected to act as a repeater in the path of meeting the weight and nodes with lower energy are used to feed back energy state in the process of data packets transmission．The source disconnects actively with the old link,thus changing the path．The NS2 platform is used to conduct a simulation experiment and performance analysis between ZigBee-new and ZigBee．The simulation results show that the improved ZigBee-new algorithm promotes the performance obviously．

Key words:ZigBee routing protocol;ad hoc network;weight;equilibrium energy

中图分类号:TP393

文献标识码:A

收稿日期:2015-10-27

基金项目:国家自然科学基金资助项目(6121377)

作者简介:狄万昕(1990-),男,江苏南京人,硕士研究生．

通讯作者:江 明(1965-),男,安徽芜湖人,教授,硕导．