一种基于能耗均衡的ZigBee网络高效混合路由算法*

曹建玲，刘文朋，彭 双，任 智

(重庆邮电大学移动通信技术重庆市重点实验室，重庆 400065)

1 引言

随着无线网络通信技术的发展，近距离、低速率、低成本的无线技术吸引了众多人的关注。目前使用较为广泛的近距离无线通信技术有蓝牙、无线局域网、红外等，同时具有发展潜力的近距无线技术标准也备受关注，如 ZigBee、超宽频(Ultra Wide Band，UWB)、短距通信(Near Field Communication，NFC)［1］等。ZigBee 技术［2］是基于 IEEE802.15.4标准的短距离、低功耗、低速率、低成本的无线通信技术，主要适合用于自动控制和远程监控，在工业、农业、军事、医疗等领域有广阔的应用前景。

ZigBee标准提出了树路由算法 (Tree Routing，TR)和AODVjr［3］两种路由算法。TR算法根据树状网络拓扑设计，需与ZigBee标准规定的分布式地址分配机制配合使用，它将数据分组沿着树形结构向上层的父节点或者下层的子节点转发，因此数据分组的传输无需事先建路，但路径不一定最优，时延有可能偏大。AODVjr算法通过在全网范围内广播RREQ分组找到并使用最优路径，但全网性的广播操作会浪费较多的带宽、内存和能量资源，还有可能引起广播风暴。近年来，为了综合利用TR算法的快捷和AODVjr算法能够获得最优路径的优点，在ZigBee网络中出现了表驱动－按需混合路由算法，如Lin等提出的LF－ZAODV(Limited Flooding Zig-Bee Ad－hoc On － demand Distance Vector)算法［4］。钱志鸿等［5］提出基于节点特性的能量优化混合路由算法，限制RREQ分组的转发跳数并借助TR算法减小了RREQ广播的范围，同时在RREQ分组中加入能量标志位，使目的节点选择一条能量充足的路径回复RREP分组，延长了网络寿命;但仍然使用了广播RREQ分组的方式且其能量阈值是人为设定。由上可知，现有基于表驱动－按需混合路由算法在广播寻路分组RREQ的过程中因使用泛洪操作而存在冗余开销，而且建路时未考虑均衡网络节点的能耗，从而影响了路由算法的效率和网络的寿命，有进一步改善的需要。

本文后续内容安排如下:第1节介绍ZigBee技术的特点及其应用，以及相关研究工作;第2节给出ZigBee网络的数学模型、能量模型、问题描述及算法的设计，第3节仿真验证所提协议的性能，最后总结全文并简介未来工作。

2 网络模型

2.1 ZigBee网络数学模型

ZigBee网络的数学模型为:G=(V，E)，其中V表示所有节点的集合，V={t}∪Vr∪Ve，t表示网络协调器/Sink节点，Vr表示所有路由节点的集合，Ve表示所有终端节点的集合;E表示所有对称无线通信链路的集合，网络中存在的每一条链路是E的一个子集;链路的代价可以是数据传输的端到端时延、链路长度(跳数)等。

2.2 能量模型

本文所采用的能量模型如下:当节点A向距离为d的节点B发送k b的信息，A消耗的能量由发射电路损耗和功率放大电路损耗两部分组成(本能量模型具有通用性)，即

式中，Eelec表示发送k b信息发射电路的损耗，εfs表示发送k b信息功率放大所需的能量。当节点B接收A发送的信息时，其无线接收装置所需能量为

2.3 问题描述

网络中节点的能量消耗用于信息的发送(包括转发)和接收，即

式中，Esi、Eti、Eri分别表示网络中节点发送、转发和接收信息所消耗的能量。

在现有的ZigBee网络混合路由算法中，存在大量冗余的RREQ信息，这些冗余的RREQ信息的收发增大了网络中每个节点发送、转发和接收的信息比特数，增加了网络开销和节点的能耗。此外，现有混合路由算法在选路时没有考虑节点的剩余能量，当节点剩余能量不足时，如果继续转发数据，可能会导致网络中节点能耗不均衡，进而导致路径的断裂，影响网络性能。

2.4 能耗均衡的高效混合路由算法设计

针对ZigBee网络现有混合路由算法在寻路开销和节点能耗等方面的不足，本文提出一种基于能耗均衡的ZigBee网络高效混合路由算法——EHCA。EHCA算法采用跨层泛听两跳范围内所有的邻居的信息方式，减少了部分寻路分组的转发;并将节点深度和剩余能量加入选路标准，达到能耗均衡效果。

2.4.1 EHCA 算法描述

EHCA算法在ZigBee网络已使用DAAM机制进行组网和节点地址分配之后运行，包括以下面两个阶段。

2.4.1.1 两跳范围内所有的邻居信息的获取和发布

Step 1:节点在1跳范围内广播RREQ寻路分组，利用RREQ中的保留字段1 b携带是否有横向邻居信息。若节点有横向邻居，标识为“1”;否则，标识为“0”。

Step 2:若源节点通过跨层信息共享感测到横向邻居信息，立即向其父辈节点发布自己的横向邻居信息，直到本节点与横向邻居节点的深度最大的公共父节点。

2.4.1.2 路由建立及数据转发

Step 1:源节点判断目的节点是否是自己或子孙节点的横向邻居，若是则直接或通过子孙节点向该横向邻居节点转发数据分组;否则，执行Step 2。

Step 2:源节点产生并组播1个RREQ寻路分组，它的跳数阈值为源、目的节点之间的树路由跳数减1，组播对象为父节点、横向邻居节点、所在分支有横向邻居节点的子节点;如果上述3类节点中后两类不存在，则向父节点单播RREQ。

Step 3:中间节点收到RREQ后，做如下操作:

(1)判断该RREQ是否曾收到或者经历的跳数大于跳数阈值，若是，则删除该请求;否则执行(2);

(2)若当前节点是目的节点的父辈或者子孙节点，则计算自己到目的节点的跳数，然后判断该值加上RREQ经历跳数是否超出跳数阈值，若是，删除该请求;否则，用树路由向目的节点转发该请求;

(3)若当前节点是RREQ发送节点的横向邻居节点，则参照Step 2处理该请求;

(4)若RREQ的发送节点是当前节点的父节点，则判断当前节点及子孙节点是否有横向邻居，如果有，则向它们组播RREQ;否则，删除该请求;

(5)若RREQ的发送节点是当前节点的子节点，且既不是源、目的节点的公共父节点，也不是源、目的节点的最大深度公共父节点的子节点，则参照Step 2处理该请求;若当前节点是源、目的节点的最大深度公共父节点的子节点，则判断本节点有无横向邻居节点或与源节点不同树枝的子节点，若有，则向它们组播该请求;否则，删除该请求。

Step 4:目的节点收到源节点发来的RREQ后，若RREQ经历的跳数没有超出跳数阈值，则沿用RREQ的来路向源节点发送RREP。RREP中包含中间节点深度和(初值为0)、路径中节点最小剩余能量(初值为目的节点的剩余能量)、路径查找请求经过的与源节点在同一树枝的节点个数等字段。

Step 5:中间节点收到RREP后，建立到目的节点的路由，并更新RREP中相应字段的值，然后用单播方式向源节点转发RREP。

Step 6:源节点收到RREP后，建立到目的节点的路由，并存储RREP携带的中间节点深度和、节点最小剩余能量、跳数等信息。

2.4.2 路由判据新参数——合成深度

在EHCA算法中，我们提出一种新的路由判据参数——合成深度(Integrated Depth)，用于在源节点收到不同路径传来的路由响应的情况下，为源节点选择整体上离协调器更远、节点剩余能量更多的路径。路径的合成深度dI定 义为

式中，dj表示路径上与源节点在同一树枝的第j个节点的深度，0＜j≤f，f为该类节点个数;dk表示路径上与源节点不在同一树枝的第k个节点(不包括目的节点)的深度，0＜k≤n，n为该类节点个数;f和n的值可根据路由响应携带的跳数信息并辅以“地址－位置”关系通过计算得到;E0、Er分别表示节点的初始能量和链路上节点最小剩余能量。

3 仿真与分析

3.1 仿真统计量

(1)节点能耗均方差

节点能耗均方差反映网络中节点能量消耗的离散程度，其值越小，则节点的能耗越均衡。节点能耗均方差的计算公式如下:

式中，Ci表示网络中第i个节点的能量消耗，N表示网络中节点总数。

(2)网络开销

网络开销用于评价算法的效率，两者呈负相关关系，即网络开销越小，算法效率越高。设C为网络开销，有

式中，Ns表示发送和转发的分组包含的比特数，Nd表示到达目的节点的数据分组包含的比特数。

(3)网络寿命

网络寿命指网络的运行时间，是衡量网络性能的一个重要指标。设网络启动时间为TS，终止运行的时间为TE，则网络寿命T为

(4)数据分组传送成功率

数据分组传送成功率指网络中成功接收数据分组数占发送数据分组总数的比例，计算公式为

其中，k表示网络中节点的个数，Ri表示第i个节点成功接收的数据分组的个数，Si表示第i个节点发送的数据分组的个数。

3.2 仿真设置

仿真实验使用OPNET14.5作为软件平台，主要仿真参数设置如表1所示。我们所采用的网络模型是由一个协调器节点和若干个信息采集节点组成的ZigBee网络，定义节点初始能量为10 J，节点能量低于初始能量的5%时节点死亡，当节点死亡个数超过网络中节点总数的20%时，网络结束运行，协调器节点在场景中心，网络中的节点随机均匀分布在协调器周围。

表1 仿真参数设置Table 1 Setting of simulation parameters

3.3 仿真结果及分析

(1)节点能耗均方差

图1为节点能耗均方差比较，与TR算法相比，EHCA算法节点能耗均方差更小(平均减小10.95%);和LF－ZAODV算法相比，EHCA算法节点能耗均方差平均减小5.35%，说明EHCA算法中节点的能量消耗与能耗平均值的差异更小，节点能耗更均衡。在TR算法中，离协调器近的节点业务量较大，能量消耗较快，而下层节点能量消耗相对较慢，网络中节点能耗不够平均，因此能耗均方差相对较大，最大达到2.88。LF－ZAODV算法以树路由的路径长度减1来限制RREQ的泛洪深度，没有考虑到节点的能量消耗。EHCA算法在选路时优先使用深度较大、剩余能量较多的节点，减少了深度小的节点的能量消耗，均衡了网络中节点的能量消耗。所以与TR算法和LF－ZAODV算法相比，EHCA算法的能耗均方差更小，网络中节点能耗更均衡。

图1 节点能耗均方差比较Fig.1Comparison of nodes energy consumption

(2)网络开销

网络开销的仿真结果如图2所示。

图2 网络开销比较Fig.2 Comparison of network overhead

图2显示，与TR算法相比，EHCA算法能够有效减少归一化网络开销(平均21.4%);和 LFZAODV算法相比，EHCA算法能够有效减少网络开销0.7%(25个节点)～11%(150个节点)。LFZAODV算法和EHCA算法能够找到传送数据的最优路径，因此减少了数据分组的转发次数;而且EHCA算法在寻路过程中利用了节点的横向邻居节点信息，无需泛洪RREQ就能找到最优路径，在寻路效果相同的前提下，减少RREQ的转发，从而进一步减小网络开销，具有更高的效率。

(3)网络寿命

网络中节点能量小于初始能量的5%时认为节点死亡，节点不再执行任何功能。当死亡节点数大于网络中总节点个数的20%时，网络停止运行，统计网络寿命。仿真结果如图3所示。

图3 网络寿命比较Fig.3 Comparison of network lifetime

图3显示，EHCA算法较TR算法网络寿命平均延长34.36%，其中50节点的场景增幅最大，达到75.6%，和LF－ZAODV算法相比，EHCA算法平均延长网络的运行时间16.8%。由于EHCA算法在建立路由时，考虑横向邻居节点，尽量在深度较大、节点剩余能量较多的层面上建立路由，减少了深度较小节点的死亡，使节点能耗更均衡，延长了网络寿命。LF－ZAODV算法全网广播RREQ分组，寻找最短路径，并按最短路径发送数据分组，但是没有考虑到节点的剩余能量。当节点能量不足时，若继续转发数据，会导致节点的死亡。TR算法中，离Sink节点(协调器)越近的节点，承担越多的路由任务，消耗更多的能量，节点死亡越快，所以在网络条件相同时，EHCA算法的网络寿命比LF－ZAODV算法和TR算法的网络寿命长。

(4)数据分组传送成功率

在网络中死亡节点出现之前，数据分组的传送成功率如表2所示。

表2 数据分组传送成功率比较Table 2 Comparison of data packet delivery success rate

从表2中数据可看出，与LF－ZAODV算法和TR算法一样，EHCA算法的数据传送成功率也达到100%，说明EHCA算法在减少控制开销和均衡节点能耗的同时保持了数据传送成功率性能。

4 结束语

本文提出EHCA路由算法，在路由建立时利用节点的两跳内横向邻居节点信息，限制RREQ分组转发范围，在一定程度上减少了网络开销;同时，以节点的深度参数和剩余能量参数作为路径选择的因素，尽量在深度较大、节点剩余能量较多的层面建立路由，实现节点能耗均衡。理论分析和仿真结果验证EHCA算法较TR算法和LF－ZAODV算法在节点能耗均衡和网络开销等方面提升了性能。

在未来工作中，我们将以EHCA算法为基础，研究设计绿色的混合路由算法，从整体上减少网络的能量消耗，构建绿色的ZigBee网络。

［1］ Roy W.Near field communication［J］.IEEE Pervasive Computing，2011，10(3):4－7.

［2］ Wang Wei，He Guangyu，Jun Liwan.Research on Zigbee wireless communication technology［C］//Proceedings of 2011 International Conference on Electrical and Control Engineering.Yichang:IEEE，2011:1245 －1249.

［3］ 朱向庆，陈志雄.采用Tree及AODVjr－PB路由算法的无线家庭网络设计［J］.重庆邮电大学学报，2011，21(3):343－348.ZHU Xiang－qing，CHEN Zhi－xiong.Design of home wireless network using routing algorithm of Tree and AODVjr－ PB［J］.Journal of Chongqing University of Posts and Telecommunications，2011，21(3):343 －348.(in Chinese)

［4］ Lin Zijing，Meng Q H，Liang Huawei.A Route Discovery Method based on Limited Flooding in ZigBee Networks［C］//Proceedings of 2008 IEEE International Conference on Automation and Logistics.Qingdao:IEEE，2008:3039 －3044.

［5］ 钱志鸿，张晓帆，王义君，等.基于节点特性的 LRWPAN网络能量优化路由算法［J］.通信学报，2010(10):238－243.QIAN Zhi－hong，ZHANG Xiao－fan，WANG Yi－jun，et al.Node characteristics based LR －WPAN routing algorithm research for network energy optimization［J］.Journal on Communications，2010(10):238 －243.(in Chinese)