- 1 -
中国科技论文在线
改进的 AODVjr 路由算法研究
刘潇花，彭勇，陆娴**
作者简介：刘潇花（1988－），女，硕士研究生，研究领域为无线网络路由算法
（江南大学物联网工程学院 B316，江苏无锡 214122）
5 摘要：针对现有的 AODVjr 算法在网络能量均衡方面的不足，结合节点能量和 Cluster-tree
算法的特点分析，提出了一种改进的 AODVjr 路由算法。改进算法在启动路由发现过程之前
使用邻居表寻找目的节点，在路由发现过程中尽量避免低能量节点的使用，并且添加 flag
标志位对 RREQ 分组的传输范围进行控制，降低网络的总体能量消耗。仿真结果表明，改
进算法能有效降低网络总体能耗，合理分担网络负载，降低死亡节点数，延长网络的生命周10
期。
关键词：计算机应用；路由算法；AODVjr 算法；能量均衡；能量标志位
中图分类号：TP393
The research of improved AODVjr routing algorithm 15
LIU Xiaohua, PENG Yong, LU Xian
(College of IoT Engineering, Jiangnan University, Wuxi, Jiangsu 214122, China)
Abstract: This paper proposes an improved AODVjr routing algorithm because of the
insufficiency energy equilibrium of existing AODVjr algorithm, combined with the characteristics
of the Clust-tree algorithm and the node energy analysis. Improved algorithm using the neighbor 20
table to find the destination node before start the routing discovery process, avoiding the use of
low energy node as far as possible and add flag flags to control the RREQ packet transmission
range in routing discovery process to reduce the network's overall energy
simulation results show that the algorithm can effectively reduce the network energy consumption
and reasonable sharing network load, reduce the number of death, prolong the network life cycle. 25
Key words: computer application;routing algorithms; AODVjr algorithm; the energy equilibrium;
energy flag
0 引言
ZigBee 技术组建的无线个域网（LR-WPAN）以其低成本、网络容量大、适应性强等方面30
的优势，被广泛地应用于军事国防、工业、家庭以及环境监测等无线通信场合[1]。
ZigBee 网络主要采用 AODVjr[2]和 cluster-tree [3-4]两种路由算法。AODVjr 支持端到端的
传输，它是在 AODV 的基础上发展而来的。在路由发现过程中由于 AODVjr 算法没有控制
RREQ 分组的大量洪泛，从而带来额外的能量消耗，使网络总体耗能过大。尽可能地降低 RREQ
分组洪泛开销[5]，是降低网络整体能量消耗的途径之一。为降低 RREQ 分组开销，AODVjr 结35
合 cluster-tree 路由算法的特点对 RREQ 分组的传输范围进行控制，从而节约网络总体能量消
耗。另外，为延长节点的使用寿命，提高节点的使用效率，防止死亡节点引起的网络分割现
象，还将考虑节点的剩余能量，如文献[6]定义节点能使用的最小能量值和文献[7]定义的能量
阈值，都延长了节点的使用寿命，提高了节点的使用效率。
本文在深入分析ZigBee网络路由算法的基础上，针对现有的AODVjr算法容易产生RREQ40
冗余和死亡节点方面的不足，结合 Cluster-tree 算法，提出了一种改进的 AODVjr 路由算法。
- 2 -
中国科技论文在线
1 路由算法
Cluster-tree 路由算法简介
Cluster-tree 路由算法（树路由算法）由主协调器展开生成簇树状网络拓扑，树中的
大部分设备为 FFD（Full Function Device, 全功能设备），包括协调器和路由器，树中的45
叶节点为 RFD（Reduced Function Device 精简功能设备）。如果 RFD 节点要发送数据包到
某目的节点，则直接将该数据包发送给其父节点，由父节点进行转发。每个父节点最多能
有 Cm 个子节点，子节点中最多能有 Rm 个路由节点，网络的最大深度为 Lm。如果一个网
络地址为 A、深度为 d 的 FFD 路由节点向网络地址为 D 的目的节点发送数据，则该路由
器节点首先通过下述表达式(1)判断目的节点是否是其后裔节点[8]。 50
A <D< A + Cskip(d-1) (1)
如果目的节点是该路由节点的后裔节点，则按照公式(2) 转发数据包，下一跳节点地
址即为公式(2)计算出的网络地址。若目的节点是其终端子节点，直接转发数据包，否则计
算其地址再转发。
( 1)
1 . ( ) ( )
( )
skip
skip
D
N D A
A C d otherwise
C d
（目的节点是其终端子节点）
(2) 55
若公式(1)不成立，表示目的节点不是自己的子节点，即下一跳节点是其父节点。
AODVjr 算法
AODVjr 具有 AODV 的主要功能，是 AODV 的简化版本，其基本原理是通过洪
泛 RREQ（路由请求包）分组寻找最优路径。RREQ 分组在源节点与目的节点之间传
递时，目的节点通过回复 RREP（路由回复包）建立与源节点之间的最短的路径，并60
将路径信息保存到路由表中。中间节点收到 RREQ 分组后查找路由表，如果有到目的
地的路由，则按该路由传送 RREQ 分组，如无则启动 AODVjr 查找机制。考虑到降低
路由成本、节约能量、使用方便等特点，AODVjr 还舍弃了 AODV 中的目的节点序列
号，简化了路由表结构。AODVjr 算法虽然能够找到一条最短路径，但洪泛 RREQ 寻址消
息需要大量能量，最短路径的选择也常常使处在特殊位置的节点快速消耗能量，造成网络能65
耗的不均衡。
2 问题的提出
AODVjr 算法按需产生路由寻径，具有灵活的路由查找功能，提高了协议效率，能快速
适应动态链路。AODVjr 算法可以比 cluster-tree 路由算法找到更优路径，但是 AODVjr 算法
在路由发现过程中会产生多余的 RREQ 分组，这些 RREQ 分组虽然也参与路由发现过程，70
但对于寻找目的节点没有作用，浪费网络能量。AODVjr 算法中路由节点都存储路由表，拥
有离自己一跳距离的相邻节点信息，如果目的节点是源节点的邻居节点，可以通过邻居表直
接传输，但 AODVjr 算法没有利用邻居表来选择传输路径。另外，AODVjr 算法中一些节点
由于频繁转发数据而使能量偏低，如果继续使用能量偏低节点会使其成为失效节点，中间节
点的失效，会增大网络能量消耗，甚至会造成 ZigBee 网络瘫痪的问题。因此，为避免剩余75
能量低的节点由于继续转发数据而失效造成网络分割，选择路径时应尽量避开能量不足节
点。
- 3 -
中国科技论文在线
针对以上问题，本文提出改进的 AODVjr 算法，算法首先使用邻居表寻找目的节
点，若目的节点不在邻居表内，则开启路由发现过程寻找目的节点，在路由发现过程
中节点根据等级制进行数据转发且添加标志位控制 RREQ 分组的洪泛方向，从而达到80
均衡并降低网络能量消耗的目的。
3 改进算法设计
减少死亡节点数
为了减少网络死亡节点数，在路由发现过程中使节点严格按照等级制转发 RREQ 分
组，能量充足节点担任主要的路由转发角色，尽量避免能量不足节点的使用。改进算法根85
据剩余能量和能量阈值划分节点等级，使网络能够判断哪些节点为能量不足节点，从而在
路由时尽量避开这些节点，达到减少死亡节点数的目的。剩余能量和能量阈值在下文详细
定义。
剩余能量公式为：
0 1( )
1
i
i
k E
E t
d t
(3) 90
E0 为节点初始能量值，d 表示节点 i 的深度，随着网络的运行节点能量降低，离协
调器越近的节点深度越小，参与转发数据次数越多，为防止其成为死亡节点，应该为
深度越小的节点预留更多的剩余能量[9]。k 表示特定系数，作用在于减缓能量初值 E0
减小的速度。t 表示网络运行时间，从式(3)可以看出节点剩余能量与节点使用时间成
反比。从时间的曲线函数可以得出节点剩余能量值随时间的增大递减幅度变得越来越95
小。在网络运行之初，节点能量充足，Ei(t)递减的幅度大，在网络运行一段时间后，
大部分节点能量偏低，Ei(t) 递减的幅度变小，使低能量节点转为能量充足节点参与数据
转发，剩余能量函数的设定符合网络能量变化的实际情况。
能量阈值公式为：
0
0
N
N
PowerSufficient E
PowerLow E
(4) 100
PowerSufficient 为能量充足阈值，PowerLow 为能量偏低阈值。根据动态更新的能量充足
阈值、偏低阈值，可将节点分为能量充足、能量偏低和能量警戒三个等级。当 Ei(t)>
PowerSufficient 时，节点为能量充足节点，PowerLow<Ei(t)< PowerSufficient 时，节点为
能量偏低节点，Ei(t)<PowerLow 时，节点为能量警戒节点。能量偏低节点和能量警戒节点
均为能量不足节点。 、 为固定系数，用来减缓各阈值的减小速度。N 为初始值为 1 的105
计数值。若节点为警戒节点，则向协调器节点发送该节点成为警戒节点信息，使协调器更新
警戒节点计数。如果警戒节点个数与网络总节点个数比大于临界值 threshold，则 N 计数加
1 从而使得能量阈值更新一次。
冗余 RREQ 分组的处理
AODVjr 算法存在两种冗余 RREQ 分组。一类是 RREQ 分组已找到目的节点，而其他110
节点仍继续广播 RREQ 分组。这类冗余 RREQ 分组不仅浪费网络能量，而且会造成网络拥
塞。解决这类冗余问题是设定 RREQ 分组的最大传输跳数。由于源节点到目的节点的跳数
不超过网络的最大深度 2Lm，所以设定最大传输跳数为 2Lm。当 RREQ 分组的传输距离超
过 2Lm 时，则丢弃该 RREQ 分组。另一类冗余 RREQ 分组的产生是因为节点在传输时没
有考虑父子关系。如通过式(1)已知目的节点是本节点的子节点，就无需向父节点转发115
- 4 -
中国科技论文在线
RREQ 分组,若已知目的节点是本节点的父节点，就无需向子节点转发 RREQ 分组。解决这
类冗余是在 RREQ 分组中添加 flag 标志位。算法根据(1)式判断出 RREQ 的大致方向，flag
=0 表明本节点的父节点不宜转发该分组；flag=1 表明本节点的子节点不宜转发该分组，
从而控制 RREQ 分组的传输范围，减少因 RREQ 分组冗余引起的能量消耗。
算法流程 120
改进的 AODVjr 算法根据节点能量等级确定节点转发机制。在转发 RREQ 分组过程中，
能量充足节点立即转发 RREQ 分组，低能量节点延迟发送 RREQ 分组，警戒节点立即丢弃
RREQ 分组。AODVjr 算法会选择最早达到的 RREQ 分组进行回应，所以当含有低能量节
点的 RREQ 分组达到目的节点时，传输路由已经建立，达到避免使用能量不足节点的目的。
在转发 RREQ 分组时，添加 flag 标志位控制其转发范围，减少能量浪费。算法具体步骤125
如下：
（1）网络节点初始化，每个节点建立并维护自己的邻居表，协调器为每个节点分配一个
网络地址，并广播能量阈值 PowerLow、PowerSufficient。
（2）源节点判断自己是否是 RFD 节点，如果是，则将要发送数据交由其父节点转发，如
果不是，则转(3)。 130
（3）源节点查看邻居表，若目的节点在邻居表中，则直接发送给目的节点；否则转(4)。
（4）目的节点不在源节点邻居表传输范围内，则开启路由发现过程，发送洪泛到目的节
点的 RREQ 分组。洪泛到目的节点的 RREQ 分组需要消耗大量能量，所以源节点首先根据
自身剩余能量判断自己的能量等级，若为警戒节点，则由能量最高的邻居节点发起路由发
现过程，如果不是警戒节点，则由自己开启路由发现过程。RREQ 的目的节点只能是 FFD135
节点，如果目的节点是 RFD 节点，则由目的节点的父节点转交。路由发现过程按以下步
骤执行：
①节点收到 RREQ 分组时，首先判断自己是否是 FFD 节点，因为 RFD 节点不具有路
由转发功能，所以如果不是 FFD 节点，就丢弃 RREQ 分组，如果是 FFD 节点，则转②。
②确定自己是否是目的节点或者 RFD 目的节点的父节点，如果是，则回复 RREP 路由140
确认包建立路由路径，否则转③。
③如果 RREQ 分组传输跳数超过 2Lm，丢弃该 RREQ 分组，否则转④。
④查看自己的剩余能量，并根据能量阈值判断自己的能量等级。如果是警戒节点，则
直接丢弃 RREQ 包，并通知协调器更新警戒节点数，如果是能量充足节点，则转⑤，如果
为低能量节点，则按照公式(5)延迟发送 RREQ 分组,然后转⑤, 145
( ) ( 1)
delay
i i
T
E t d
(5)
为固定系数，用来调整延迟函数变化速度。从公式(5)中看出，剩余能量越低深度越
小的节点，则延迟发送数据时间越长。AODVjr 算法选择最早达到的 RREQ 包回应，也就
变相选择能量充足的一条路径。剩余能量越低深度越小的节点，在路由选择时越有可能被
绕过，达到能量均衡的目的。 150
⑤在转发 RREQ 分组前，查看收到的 RREQ 分组中的 flag 值。若 flag=1，转⑥,若
flag=0，转⑦;
⑥表明本节点不宜转发父节点送来的 RREQ 分组。若本节点是上一跳节点的子节点，
则丢弃 RREQ 分组，否则，根据公式(1)判断目的节点是否是本节点的后裔节点。若是后裔
节点，则本节点的父节点不宜转发 RREQ 分组，需更改 flag 值为 0，若不是后裔节点，表155
明本节点的子节点不宜转发 RREQ 分组，flag 值继续为 1,转⑧；
- 5 -
中国科技论文在线
⑦表明本节点不宜转发子节点送来的 RREQ 分组。若本节点是上一跳节点的父节点，
则丢弃 RREQ 分组，否则，根据公式(1)判断目的节点是否是本节点的后裔节点。若是后裔
节点，则本节点的父节点不宜转发 RREQ 分组，flag 值继续为 0，若不是后裔节点，表明
本节点的子节点不宜转发 RREQ 分组，flag 值更改为 1，转⑧; 160
⑧继续转发 RREQ 分组，转①，直到 RREQ 分组达到目的节点。
（5）目的节点一旦收到 RREQ 分组，则按照该路由发现的路径进行数据传输。
中间节点对 RREQ 包处理的流程图如图 1 所示。
收到RREQ分组
FFD节点？ 丢弃
目的节点或者FRD目
的节点的父节点？
回复RREP
传输跳数超过2Lm 丢弃
根据公式(3)(4)，Ei(t) <PowerLow ？
丢弃RREQ,并向协调
器发送成为警戒节点
信息
根据公式(3)(4)判断是
否为低能量节点
根据公式(5)延
迟发送RREQ
此时节点必为
能量充足节点
查看flag值
flag=1 flag=0
本节点是上一 跳
节点的子节点？
本节点是上一 跳
节点的父节点？
丢
弃
目的节点是否为当前
节点的后裔节点
目的节点是否为当
前节点的后裔节点
flag=0 继续转发RREQ flag=1
Y
N
N
Y
Y
Y
N
N
N
N
Y Y
Y
Y
N
N
N
Y
图 1 中间节点对 RREQ 包处理流程 165
4 仿真实验结果
本文通过仿真实验，在网络整体能量消耗和网络节点生存率方面与改进前算法进行比
较。在仿真环境中，设置网络范围为 300m×300m，数据包长度为 64bit，采用 CBR 作为数
据信息源，网络节点数分别取 40、80、120、160、200，网络参数 Cm=5，Rm=4，Lm=6。
每个节点的初始能量设为 1500J。取公式(3)中的 k=，公式(4)中取 =， =， 170
threshold=，公式(5)中的 =100。仿真实验结果如图 2、图 3 所示。
- 6 -
中国科技论文在线
1 2 3 4 5
0
2
4
6
8
10
12
14
流量/(包s-1)
网
络
总
体
能
量
消
耗
/K
J
传统AODVjr算法
改进的AODVjr算法
图 2 网络总体能量消耗对比 175
图 2 是在网络节点数为 200 时传统 AODVjr 算法和改进的 AODVjr 算法在网络总体能量
消耗上进行的对比。从图中可以看出，改进算法降低了网络总体能量消耗。改进算法首先利
用邻居表搜索目的节点，目的节点不在邻居表内时，开启路由发现，在路由发现过程中对
RREQ 分组进行有效地控制，减少了 RREQ 分组冗余开销，并避免能量不足节点的使用，
减少因网络分割而引起的能量浪费，从而降低了网络能量消耗。 180
40 80 120 160 200
60
65
70
75
80
85
90
95
100
总节点个数
节
点
生
存
率
/%
传统AODVjr算法
改进的AODVjr算法
图 3 节点生存率
图 3 对传统 AODVjr 算法和改进的 AODVjr 算法在节点生存率上进行比较。如果一个
节点的剩余能量低于初始能量的 3%，则被看做是死亡节点。网络运行结束后，计算生存185
节点个数。节点生存率公式为：
= 100%able
total
N
N
（6）
其中，Nable 是网络运行结束后生存节点个数，Ntotal 是网络总节点个数。从图 3 可以
得出，在节点数为 40 的时候因为节点数较少，两种算法都有一些节点由于使用过度而成
为死亡节点，但改进的 AODVjr 算法尽量避免能量不足节点的使用，所以改进算法节点生190
存率较高。由于节点数的增加，数据选择的路径变多，所以每个节点的使用率变低，在网
络运行结束时，节点生存率增大。传统 AODVjr 算法在总节点个数为 120 时节点生存率达
到峰值 82%，之后由于节点数的继续增加网络拥塞现象加剧，死亡节点数增加，节点生存
率开始下降。而改进的 AODVjr 算法使节点严格按照等级制转发数据，减少了死亡几率，
因此，节点生存率随节点个数的增多而增大。 195
- 7 -
中国科技论文在线
5 结束语
本文针对传统 AODVjr 算法在能量均衡上的不足，提出了基于能量均衡的 AODVjr 算
法的改进方案。改进算法使用邻居表转发数据包，结合 cluster-tree 算法的优点，添加标志
位控制 RREQ 分组的转发方向，并且在路由发现过程中有效控制低能量节点和警戒节点的
使用，减少死亡节点，降低网络分割风险，从而使得网络的能量消耗达到均衡，减少网络200
总体能量消耗。但算法还存在一些不足，如算法的适用范围不广，没有考虑节点运动的情
况；同时如何进一步降低网络延迟以及将算法运用到具体实际中是下一步的主要工作。
[参考文献] (References)
[1] 李文仲，段朝玉. ZigBee2006 无线网络与无线定位实战[M]. 北京：北京航空航天大学出版社，
Weng-zhong,DUAN Wireless networks and wireless positioning combat 2006[M].Beijing: 205
BeiHang University press,2008.
[2] Chakeres I D,Klein ,AODV simplfied[J]. Mobile Computing and Communication Review,
2002,6 (3):100-101.
[3] Kim T,Kim tree routing in ZigBee networks [C]// The 2nd International Symposium on Wireless
Pervasive Computing（ISWPC 2007）.United States:IEEE, 2007:42-47. 210
[4] 范世安.ZigBee 网路之捷径式树状路由改进演算法[D].中国台湾:大同大学,2008.
FAN shortcut tree routing algorithm in ZigBee network[D].Taiwan,China: Datong University,
2008.
[5] Akkaya K,Younis Survey on Routing Protocols for Wireless Sensor Networks[J].AdHoc Networks,
2005,3(3): 325-349. 215
[6] 班艳丽,柴乔林,王芳.改进的 zigbee 网络路由算法[J].计算机工程与应用,2009,45 (5):95-97.
BAN Yan-li,CAI Qiao-lin,WANG Fang. Improved routing algorithm for ZigBee networks. Computer Engineering
and Applications,2009,45(5):95-97.
[7] 王俊杰 ,陈其工 , 江明 ,等 . LR-WPAN 捷径式能量均衡树路由算法研究 [J]. 计算机工程与应
用,2012,48(23):95-98. 220
WANG Jun-jie,CHEN Qi-gong,JIANG Ming,et al. Research on shortcut energy balance tree routing algorithm in
Engineering and Applications, 2012, 48(23):95-98.
[8] BARONTI P,PILLAI P,CHOOK V W C,et al. Wirless sensor networks:A survey on the state of the art and the
and Zigbee standards[J].Computer Communications,2007,30(7):1655-1695.
[9] 黄瑞玲，张伟。感知范围可调的 WSN 多属性目标覆盖算法[J].中国科技论文在线精品论文，2012,5（8）：225
701-706.
HUANG Rui-ling,ZHANG Wei. Multiple attribute target coverage algorithm in WSN with adjustable sensing
ranges[J].Highlights of Sciencepaper Online,2012,5(8).
