基于最小跳数和节点能量的 AODV-HE 路由选择算法

2016-06-28余翔彭帜王诗言刘利

电信科学 2016年6期

关键词：跳数权值报文

余翔，彭帜，王诗言，刘利

（重庆邮电大学宽带移动通信动员中心，重庆 400065）

基于最小跳数和节点能量的 AODV-HE 路由选择算法

余翔，彭帜，王诗言，刘利

（重庆邮电大学宽带移动通信动员中心，重庆 400065）

按需路由协议 AODV 中仅以最小跳数作为路由选择依据，导致网络资源分配不均及网络寿命减少。提出了 AODV-HE 算法，该算法优化路由选择机制，综合最小跳数和节点剩余能量提出一种反向路由判据权值，并根据此权值选择最佳路由。仿真结果表明，该算法能有效提升分组投递率，降低端到端时延，改善网络资源分配问题并有效延长网络寿命。

路由选择机制；最佳路由；资源分配；网络寿命

1 引言

Ad Hoc 网络由同时具有路由和主机功能的节点组成，不利用现有网络基础设施就可以实现终端间通信。AODV（Ad Hoc on-demand distance vector，AODV）协议是 Ad Hoc网络中经典的按需路由协议［1］。

当源节点没有到达目的节点的有效路由时就会启动路由发现过程。AODV 协议是最短路径协议，仅以最小跳数为路由选择判据，导致负载较大时关键节点过早死亡，另一些节点未得到充分利用，资源分配不均造成网络寿命变短。

目前，针对 AODV 路由协议的改进算法有很多。参考文献［2］根据单个节点的能量使用情况及全路径能量消耗情况，选择不同传输路径，提高了路由效率。业务负载较高时，时延改善不佳。参考文献［3］基于路径稳定性和能量有效性提出一种新型节点代价函数，在路由开销和节点死亡率方面有较好表现，但是时延较大。参考文献［4］根据网络中不同时期参量的变化情况选择不同路由，使选路机制达到整体最优化，但在能量均衡选路方面不完善。参考文献［5］在网络中产生多个局部路由，增加网络中的路由冗余度，降低端到端时延，但路由发现频率有所提高。参考文献［6］选择链路中节点的平均邻居数目作为路由选择比较参数，增加了断裂链路修复成功的概率。源节点可随时切换更优路由进行数据传输，在时延上表现良好，但由于传输数据的同时还会寻找更优路由，节点能耗增加。参考文献［7］提出RAODV 算法，采用逆寻机制，在数据传输链路断裂时，源节点从备份路由中选出最优路由进行通信。因此传输可靠性较好，但当网络负载较高时，备份路由失效率高。

针对上述不足，本文提出一种改进协议 AODV-HE（routing algorithm based on minimum hop and energy of node，AODV-HE），该协议综合考虑最小跳数和节点能量。在寻路阶段，中间节点收到 RREQ 报文后，首先通过比较 RREQ 报文中的路由判据权值来建立最优反向路径，保证该节点路由表项中，建立的反向路径综合考虑了最小跳数和节点剩余能量。源节点在一定时间内收到多条路由应答报文 RREP后，根据 RREP中的路由判据权值选择一条最优路由发送数据。改进后的协议能够更好的均衡负载，适应拓扑结构的动态变化，降低关键节点的能耗，从而延长网络寿命。实验表明该改进协议在分组投递率、路由发起频率、归一化路由开销和平均端到端时延等指标上均有所改善。

2 AODV-HE 路由选择算法

2.1 能量模型的建立

设源节点为 S，目的节点为 D，网络中存在一条路径Ri=r1，r2，…，rm（m≥2），分析数据分组从 r1经由路径 Ri成功发送到 rm的能量。考虑节点 ri的 4 个参数：初始能量、当前剩余能量、传输功率和接收功率。在该节点能量模型中，节点初始能量 Einitial均为 30 J［8］，使用 NS2 中能量模块，传输功率 Es为 0.660 W，接收功率 Er为 0.395 W。一条具有 m个节点的路由存储转发 n bit数据时，整条路径上节点消耗的总能量为：

其中，Ecs为节点发送每比特消息所消耗的能量，Ecr为节点接收每比特消息所消耗的能量。

根据节点能耗模型［9］有：

其中，Time 为处理一个分组所需时间：

2.2 复合路由选择算法

每个节点的初始能量 Einitial为 30 J［8］，根据多次实验可知，源节点到目的节点的最大跳数 Maxhop 为 10，hop 是报文分组到达该节点所需跳数，Emin是路径中最小的节点剩余能量，选择 Emin越大的路由，网络的生命周期越长。

设 θ1为路径中所有节点的平均剩余能量：

对其归一化处理，得到：

归一化路径中最小节点剩余能量，得到：

综合考虑路由中最小的节点能量和节点的平均能量，设置能量权重函数：

选择 E值较小的路由，能同时兼顾路径能量和网络剩余能量的均衡。

hop是报文分组到达该节点所需跳数，设置跳数权重函数：

选择 γ值越小的路由，网络顽健性越高。

对能量和跳数指标提供两个权重因子 α 和 β，则路由判据权值为：

其中，α+β=1。

W 值越小代表该路由越好，可根据网络状态对权重因子 α 和 β的值进行调整。当网络节点能量剩余不足时，应优先考虑节点生命，故能量的权重较大；网络规模较大且拓扑结构易变时，跳数的权重较大。

将式（10）等效为：

由于节点的剩余能量为 0时，其不参与数据接收和转发，相当于隐形节点，故有：

又因为：

所以路由判据函数W的取值范围：

2.3 AODV-HE 的分组头改进

在选择最优路由时，为了综合考虑跳数和节点能量，需要对原有 AODV 协议分组头进行改进。在分组头中增加能量和路由判据权值字段，改进后的 RREQ 和 RREP 格式如图1所示。

图1 改进后 RREQ 和 RREP 格式

通过获取路径中节点的能量信息，计算出路由判据权值，由此获得最优路由。

控制报文中字段的增加导致转发每个路由控制报文所消耗的能量增大，第 2.3 节中仿真显示，由于AODV-HE算法选择的路由顽健性高，路由发起频率低，用于路由寻找和路由维护的控制报文数量明显下降，故总能耗下降。

2.4 AODV-HE 算法流程

AODV 协议是最小跳数路由协议，即寻路阶段中间节点收到 RREQ 报文后，首先判断之前是否收到相同报文，若是，则丢弃该报文。这样会导致一些改进协议在寻路阶段效果不够明显。即使中间节点根据改进算法可以选择较优的 RREQ 建立反向路径，但是寻路流程不改变会造成中间节点仍然选择首次收到的 RREQ 来建立反向路径。

AODV 路由协议寻路过程如图 2 所示，源节点 S 泛洪RREQ 给其邻节点，接收到 RREQ 的中间节点将首次收到的 RREQ 泛洪给自己的邻节点，一直到目的节点接收到RREQ 报文为止。假设节点 2 先收到节点 1 转发的 RREQ，即使节点 4 的剩余能量大于节点 1，节点 2 收到节点 4 的RREQ 报文后也会直接丢弃。这样会导致针对 AODV 进行改进的算法效果不明显。

图2 AODV 路由协议寻路过程

针对该问题，本算法优化寻路流程。中间节点收到RREQ 分组后，根据其中的跳数和节点能量信息，利用算法得出新的路由判据权值W。

对比 RREQ 分组中的权值与节点本地路由表项中的反向路由权值，并将较小值对应的反向路由更新于本地路由表项中，如式（16）所示。更新 RREQ 报文后将其广播出去，主要流程如图 3所示。

图3 RREQ 处理流程

目的节点或有到达目的节点路由的中间节点在收到RREQ 报文后，产生 RREP 报文并将其发往源节点。中间节点在收到 RREP 报文后根据本地路由表项中存储的反向路由将此 RREP 单播至源节点，源节点选取路由判据权值最小的路由作为最优路由发送数据，主要流程如图 4所示。

3 仿真实验和性能比较

采用的仿真平台 NS2（Network Simulator，version2），它是一种面向对象的网络仿真器，本质上是一个离散事件模拟器，是目前网络研究领域应用最为广泛的网络仿真软件之一。比较 AODV、RAODV 和 AODV-HE 路由协议在分组投递率和平均端到端时延方面的性能。每次结果取 10次实验的平均值。

图4 RREP 处理流程

3.1 仿真环境配置

仿真场景使用 Random Waypoint模型，无线信号传输模式为 Propagation／TwoRayGround。每个节点通信范围为550 m，节点运动区域为 1 000 m×300 m，仿真时间为 600 s，流量数据分组类型为 CBR 方式，通信节点对数为 10。

3.2 路由算法性能标准

·分组投递率

·平均端到端时延

3.3 仿真流程

安装 NS2 系统后，复制 AODV 文件夹，并且将其命名为 AODV-HE，修改 AODV-HE 目录下的源代码并将AODV-HE 作为一个新协议注册进 NS2 系统中。然后在 tcl文件中设定仿真协议，生成场景文件和流量文件，利用gwak 脚本得到仿真数据。最后利用绘图命令 gnuplot将得到的仿真数据绘制于一张图上。仿真流程如图5所示。

图5 仿真流程

3.4 仿真结果及分析

3.4.1 节点最大速度不同时协议性能的比较

图6 为权重因子相等即 α=β=0.5 时，节点最大速度分别是 2 m／s、4 m／s、6 m／s、8 m／s、10 m／s、12 m／s、14 m／s、16 m／s、18 m／s、20 m／s 时的数据分组投递率、端到端时延仿真结果。

图6 节点速度不同时的分组投递率和端到端时延（α=β=0.5）

由图 6 可以看出，节点最大速度较低时，网络拓扑变化不大，3种协议分组投递率相近。随着节点移动速度加快，网络拓扑变化激烈，AODV-HE 分组投递率明显优于RAODV 和 AODV。因为 AODV-HE 选择的路由更稳定，均衡了网络负载，延长关键节点生命，数据发送成功率更高。节点速度的增大导致 RAODV 协议的备份路由失效率增加，优势逐渐减弱。网络拓扑结构变化激烈，链路断裂次数增多，3 种协议的平均端到端时延呈上升趋势。AODV-HE的时延最低，这是由于 AODV-HE 综合性路由判据使选择的路由具有更好的顽健性，链路断裂次数少，保持连接的时间长，避免了重复寻找路由以及修复断裂路由造成的时延。

3.4.2 CBR 发送速率不同时协议性能的比较

权重因子相等即 α=β=0.5 时，分别使用 10 种 CBR 发送速度：2 分组／s、4 分组／s、6 分组／s、8 分组／s、10 分组／s、12 分组／s、14分组／s、16 分组／s、18 分组／s、20 分组／s 时，数据分组投递率和端到端时延仿真结果如图7所示。

图7 CBR 速率不同时 3 种协议性能比较（α=β=0.5）

由图 7 可知，CBR 发送速率较低时，RAODV 备用路由有效率高，AODV-HE 选择的路由顽健性高，故 RAODV 和AODV-HE 优势明显。CBR 数据发送速率增加，网络负载加重，导致碰撞和拥塞概率增加，3 种协议分组投递率下降。流量负载加重使节点能耗增加，链路断裂次数增多。AODV-HE 选择路由时考虑了最小节点剩余能量，稳定性高，路由保持连接时间长，分组投递率高。CBR 发送速率较低时 3 种协议的平均端到端时延相差不大。CBR 发送速率增大导致节点能量消耗迅速，生命周期变短，路由频繁断裂，平均端到端时延明显增加。RAODV 时延明显增大是因为流量负载增多使其备份路由失效率高，路由寻找和维护花费时间大。AODV-HE 时延明显低于 RAODV 和 AODV，是因为 AODV-HE 选择的路由更加稳定，关键节点的生命周期长，减少了再次发起路由寻找和路由维护所需时间。

3.4.3 α 与 β对 AODV-HE 协议的影响

在路由选择判据权值的设计和分析中，考虑到 α和 β在不同情况下的取值对协议的性能影响。图 8是 α和 β在不同取值情况下 AODV-HE 的性能仿真结果。

图8 AODV 与 α 和 β 不同时的 AODV-HE 协议性能比较

由图 8 可知，在 CBR 发送速率较低的情况下，α=0.2、β=0.8 时协议性能最好。这是由于 CBR 速率较低时，网络负载低，协议更倾向于选择跳数较少的链路，又由于其结合了能量因素，选择的路由更稳定，避免了链路断裂后再次寻找路由带来的时延，故分组投递率和时延的性能最好。随着 CBR 速率增大，网络中数据分组碰撞概率增大，链路断裂次数增多，AODV-HE 协议在 α=0.8、β=0.2 时优势逐渐明显。这是由于在网络流量加重的情况下，其选择的路由顽健性更高，使得数据分组投递率最高，时延最小。

3.4.4 改进后的路由控制报文损益情况

节点生存时间是指，仿真开始到节点能量耗尽为止。网络生存时间是所有节点生存时间的均值，即：

由于 AODV-HE 协议在路由请求报文 RREQ 分组中增加 3 个字段，在路由应答报文 RREP 分组中增加了一个字段，故每处理一个路由控制报文的耗能会较 AODV 中的多。但是，由于 AODV-HE 协议选择的路由综合了最小跳数和节点能量，选择的路由顽健性高，不易断裂。AODV-HE 协议通过实时更新最佳反向路由，保证了寻找的中继节点质量，减少了维护路由或重新寻找路由的次数，从而降低了网络中路由控制报文总数。节点需要转发的路由控制报文数量减小，导致节点能耗降低，生存时间延长。网络中节点的生存时间延长，故网络的生存时间延长。仿真结果如图9所示。

图9 不同 CBR 速率下网络生存时间比较

4 结束语

节点能量有限直接影响到 Ad Hoc 网络的性能和稳定性。本文提出基于最小跳数和节点能量的 AODV-HE 路由选择算法，根据最小跳数和网络中最小节点剩余能量，设置反向路由判据权值，过滤掉多余路由控制报文。节点通过路由判据权值选择更优上一跳节点建立反向路由。中间节点在寻路阶段接收到 RREQ 报文后，将更优的 RREQ 报文发送节点更新为自己的反向节点，使得路由选择依据综合了最小跳数和节点剩余能量，保证路由的顽健性，使网络中节点得到充分利用，平衡了网络资源的分配。理论和仿真结果显示，通信频率适中时该算法在分组投递率和平均端到端时延上有较好表现，有效平衡了网络负载，提升网络性能。

参考文献：

［1］ KUMAR R，GUPTA M.Route stability and energy aware based AODV in MANET ［C］／／The International Conference on High Performance Computing and Applications，Dec 22-24，2014，Bhubaneshwar，India.New Jersey：IEEE Press，2014：1-5.

［2］郑石，吴伟强，张钦宇，等. 基于能量感知的 Ad Hoc 路由算法研究［J］. 通信学报，2012，33（4）：9-16. ZHENG S，WU W Q，ZHANG Q Y，et al.Research on energy-aware Ad Hoc routing protocols ［J］.Journal on Communications，2012，33（4）：9-16.

［3］张明华，张帆. 无线 Ad Hoc 网络中基于稳定性和能量有效性的路由选择算法研究［J］. 齐鲁工业大学学报，2015，6（2）：82-86. ZHANG M H，ZHANG F.Research on routing protocols based on stability and energy efficiency in Ad Hoc networks ［J］. Journal of QILU University of Technology，2015，6（2）：82-86.

［4］ TERDAL S P，MYTRI V D.Multiple metrics based load balancing routing protocol for mobile ad hoc networks［C］／／The Asian Himalayas International Conference on Internet（AH-ICT ’09），Nov 3-5，2009，Kathmundu，Nepal.New Jersey：IEEE Press，2009：1-5.

［5］杜青松，朱江，张尔扬. 基于闲时逆寻和路由学习机制的优化 AODV 路由协议［J］. 通信学报，2011，32（8）：64-71. DU Q S，ZHU J，ZHANG E Y.Optimized AODV routing protocol based on reverse route search in leisure time and route learning［J］.Journal on Communications，2011，32（8）：64-71.

［6］梁建武. 移动 Ad Hoc 网络 AODV 路由协议的研究与优化［J］.重庆大学学报，2015，38（4）：152-158. LIANG J W.Research and optimization of AODV routing protocols in mobile Ad Hoc network ［J］.Journal of Chongqing University，2015，38（4）：152-158.

［7］王龙峰.RAODV：一种基于拥塞跳数改进的 AODV 路由协议［J］.计算机与现代化，2013（8）：133-136. WANG L F.RAODV：An improved AODV routing protocol based on congestion hop count ［J］. Computer and Modernizatioon，2013（8）：133-136.

［8］ XING Y H.A dynamic programming solution for QoS routing in wireless ad hoc network with energy constraints ［J］.The Journal of China University of Posts and Telecommunications，June 2010，19（Suppl.1）：33-37.

［9］ BAEK S J，VECIANA G D.Spatial energy balancing in large-scale wireless multihop networks ［C］／／The 24th Annual Joint Conference of the IEEE Computer and Communications Societies（INFOCOM 2005），March 13-15，2005，Miami，Florida，USA.New Jersey：IEEE Press，2005：126-137.

［10］EZREIK A，GHERYANI A.Design and simulation of wireless network using NS-2 ［C］／／The 2nd International Conference on Computer Science and Information Technology，April 28-29，2012，Singapore.Beijing：China Academic Journal Electronic Publishing House，2012：157-161.

［11］KHARRAZ M， SARBAZI-AZAD H.On-demandmulticast routing protocol with efficient route discovery ［J］.Network and Computer Applications，2012，35（3）：942-950.

AODV-HE routing algorithm based on minimum hop and energy of node

YU Xiang，PENG Zhi，WANG Shiyan，LIU Li
Broadband Mobile Communication Mobilization Center，Chongqing University of Posts and Telecommunications，Chongqing 400065，China

AODV routing protocol takes the minimum hop as the only basis in route selection，causing the uneven allocation of resources and reduction in network lifetime.A routing algorithm based on minimum hops and energy of node （AODV-HE）was proposed.By integrating both minimum hop and residual energy of each node，the algorithm optimized the routing mechanism and presented a selection weight of reverse routing，based on which the best route was chosen.Simulation results show that the algorithm can effectively increase packet delivery ratio and reduce the end-end delay，and it can also improve the allocation of network resources and extend network lifetime.

routing mechanism，best route，allocation of resources，network lifetime

s： The National Science and Technology Specific Program of China （No.2015ZX03004004），Project Foundation of Chongqing Municipal Education Committee （No.KJ1500426），Youth Foundation of Chongqing University of Posts and Telecommunications （No.A2014-96）

TN915

：A

10.11959／j.issn.1000-0801.2016123