基于节点负载等级的自组网AOMDV路由协议改进方法

郭少雄 李正伟 宋志群

摘 要：为了增强自组网AOMDV路由协议的负载均衡能力，根据队列缓存比将网络中节点分为2个等级Normal和Danger，针对不同等级进行不同的处理。对Danger级节点直接弃用，对Normal级节点通过阈值比较赋予相应的虚拟跳数，队列缓存比越高则相应的虚拟跳数越高。对RREP和Hello报文进行了拓展，均加入了节点队列缓存比项，来更新和收集最新路径节点状态信息。改进后的协议通过包含节点负载信息的最小虚拟跳数作为最优路径选择依据，使用OPNET在不同网络负载下以固定的节点速率进行仿真。结果表明，改进路由协议在牺牲有限的路由开销前提下，起到了对节点的负载均衡作用，缓解了网络拥塞，提高了数据包投递率，有效降低了端到端的传输时延，为提升自组网网络性能提供了一种较为简单的方法。

关键词：无线通信技术;移动自组网;AOMDV;节点拥塞;负载均衡

中图分类号：TN924   文献标识码：A

DOI： 10.7535/hbgykj.2021yx02007

Improved method of AOMDV routing protocol in Ad Hoc network based on node load level

GUO Shaoxiong，LI Zhengwei， SONG Zhiqun

（The 54th Research Institute of CETC， Shijiazhuang， Hebei 050081，China）

Abstract：

In order to enhance the load balancing capability of the AOMDV routing protocol in Ad Hoc network，according to the queue buffer ratio，the nodes in the network were divided into two levels，Normal and Danger，and the corresponding processing was performed for different levels.Danger-level nodes were directly abandoned，and Normal nodes were assigned corresponding virtual hops through the threshold comparison.The higher the queue cache ratio was，the higher the corresponding virtual hops were.The RREP and Hello messages were expanded，and the node queue cache ratio was added to update and collect the latest path node status information.The minimum number of virtual hops containing node load information was used as the basis for optimal path selection in the improved protocol.At different network loads and a fixed node rate， the OPNET was adopted to simulate.The results show that the improved routing protocol has a load balancing effect on nodes at the expense of limited routing overhead，which alleviates network congestion，increases the data packet delivery rate，and effectively reduces the end-to-end transmission delay.It provides a relatively simple method for improving the performance of the Ad Hoc network.

Keywords：

wireless communication technology; mobile Ad Hoc network; AOMDV; node congestion; load balancing

自組网又可称为Ad Hoc网络，具有无中心、组网迅速、多跳路由、不依赖固定基站等特点，近年来其在军事指挥、抢险救灾、临时会议等场合发挥着越来越重要的作用。但是由于移动自组网的网络拓扑变化较快且节点能量和网络带宽受限，如何发现并维护可靠的传输路径成为了研究的热点和难点[1-4]。

按需多路径距离矢量协议（ad hoc on-demand distance multipath vector routing，AOMDV）是基于按需单路径距离矢量协议（ad hoc on-demand distance vector routing，AODV）改进的一种平面多径路由协议[5]，能够找到多条开环的链路不相交路径，采用备份路由机制，当检测到当前路径中断时能够快速切换到备用路径，相比于单路径路由协议具有较好的容错能力和通信恢复能力，可以快速并且有效地恢复因Ad Hoc网络中拓扑不断变化引起的路径中断。但是由于其序列号机制，只把跳数最小作为路径判别标准，使得最先发现的路径往往不是最优路径，某些节点由于位置等原因频繁使用，过多的数据在节点缓冲区排队等待复制转发，溢出丢失的概率较大，严重影响着网络的性能，有必要进行网络负载均衡处理[6-9]。

基于AOMDV路由协议的移动自组网负载均衡研究已经有了一定的研究成果。文献[10]引入节点拥塞度概念，对中间繁忙节点采用旁路路由算法，提出了一种基于AOMDV路由协议的AQMP路由协议;文献[11]通过对AOMDV路由协议中Drop-Tail队列模型采取预判机制，及时感知节点当前的负载状态，有效缓解了拥塞问题和节点的不均衡负载;文献[12]在AOMDV路由协议基础上提出了一种基于分流传输和拥塞预警的BAOMDV协议，采用多径并行分流传输方法控制网络负载等。

为实现网络资源的均衡优化，上述文献中网络的均衡算法都较为复杂，算法本身对节点的能量消耗过多同时路由开销较大。考虑到节点的功率计算能力有限，依托原AOMDV协议控制报文，提出一种采用新的跳数计数方式（以下統一称为虚拟跳数）的路由协议（line based AOMDV，LB-AOMDV）。

1 节点等级划分

1.1 AOMDV路由策略

与AODV路由协议相同，AOMDV多径路由协议中也存在3种消息报文，分别是路由请求消息报文（route request，RREQ），路由应答消息报文（route response， RREP），路由错误消息报文（route error， RERR）。通过这3种消息报文的发送和接收实现对网络拓扑中传输路径的选择和维护。

AOMDV协议的路由发现过程分为两部分：前向路由路径的建立和反向路由路径的建立。反向路由是通过RREQ消息建立的，当中间节点收到源节点或者上一节点广播的RREQ消息时，由该节点指向源节点或者上一节点的反向路由相应建立;前向路由是通过RREP消息建立的，目的节点对收到的RREQ消息作出回复处理，即向前一节点发送RREP消息，同时由前一节点指向目的节点的前向路由建立。源节点能否找到一条最新路由是通过到达源节点的RREP消息来确定的。S是源节点，D是目的节点，路由的发现过程如图1所示。

路由表建立之后，路径中的每个节点都需要进行路由维护和管理等任务来实现逐跳转发和多跳通信。在路由表的维护过程中，除了要删除失效、不需要的节点路由外，当检测到出现链路中断，即有节点在相应周期内接收不到Hello包，上游节点会向更上游的节点发送RERR包。在每一个RERR包的路由表中，存储了由于链路中断而导致无法到达目的节点的IP地址，同时每个节点都保留了一个前驱列表来帮助完成RERR包顺利到达源节点的过程。

移动Ad Hoc网络在进行信息传输时，部分节点由于位置等原因被频繁地选为中间节点，导致这些节点处有更多的信息在排队等待复制转发，从而长期处于一种高负载情况[13-17]。当节点的拥塞情况十分严重时，还会造成信息的溢出丢失，严重影响整个网络的性能。

1.2 节点等级

定义节点的信息排队等级（队列缓存占用比）：M=q/Q，其中：q表示节点处当前数据包队列长度;Q表示节点处能够处理和容纳的数据包最大队列长度。

在LB-AOMDV协议中，将网络中节点处的负载排队情况按照百分比分为2个等级，分别是Normal和Danger，这2个等级的界限标准由阈值Level决定，节点的等级设置如表1所示。

当节点的排队等级达到Danger时，此时节点处的信息排队队列过长，继续传输将导致链路中断或者非常大的时延，此时判定此节点不可用，路由包直接返回上一节点选择其他的中间节点进行传输。

通过查阅文献[15-16]和实际应用中的仿真分析，在此LB-AOMDV路由协议中设定Level为0.8，即当节点处的数据包队列缓存比超过0.8时，判定此节点失效。当节点的排队等级介于0和0.8之间时，设定：

CountM=1，      0≤M≤0.3，

2，      0.3

当节点处于Normal级别时，LB-AOMDV路由协议的路由发现过程和原AOMDV协议是相同的。而当节点处的信息排队等级处于Danger级别时，此时的节点已经处于高负载情况，原AOMDV路由协议是节点转发一次RREP包的跳数计数方式Hop_Count+1，LB-AOMDV路由协议在原来基础上综合考虑了节点处的信息排队情况，节点转发一次RREP的虚拟跳数为

Hop_Count+Count_M。（2）

综上所述，LB-AOMDV路由协议以虚拟跳数作为路径判别依据，虚拟跳数中包含节点的负载信息，节点处的信息排队越长，负载越大，虚拟跳数越大，这样在进行路由选择时能够有效避开高负载节点，起到了负载均衡的作用。

2 节点状态的更新与上报

一般情况下移动自组网都是多跳传输，即从源节点到目的节点经过中间节点的中继，每个中间节点或者一条活动路由的状态是不断变化的。怎样把这种状态变化收集，使得当源节点或者目的节点能及时掌握所在链路的状态信息时，才能及时做出相应的改变[18-21]，如避开高负载的节点、及时切换衰落链路等。通过报文RREQ和RREP能够分别产生反向路由和正向路由，每次经过一个节点，这2种报文都会及时做出更新，而源节点能否找到一条最新路由是通过RREP来反馈确定的，RREP报文可以存储经过节点的最新状态信息，当RREP报文到达源节点时，确定前向路由，所在路径的最新信息也随之全部更新到源节点。基于RREP的这种机制，本文选择改进的Hello消息包和RREP消息包来进行节点状态的收集、更新与上报。

2.1 通过改进Hello消息来更新路径状况

Hello消息是TTL=1的RREP包，用来监测一条活动路由的连接状态。生存周期只有一跳，是自组网在路由维护过程中十分重要的消息包，能够为网络节点提供关于链路状态的信息。一条活动路由通过使用Hello消息包来确认网络链路的连接状态。每个Hello消息发送的间隔周期时间设置为Hello_interval，若节点在检查中发现在上一个周期时间内没有发送广播消息，那么该节点就会广播一个Hello消息包。Hello消息报文的格式如图2所示。

Hello消息报文中的目的节点IP地址为本节点的IP地址，目的节点序列号就是本节点的最新目的节点序列号，Hop_Count值设置为0，周期时间（Lifetime）值设置为

Allow_Hello_Loss×Hello_interval。（3）

用Hello消息来动态监测路径连接状态，既能比较简单地获取动态的路径连接状态信息，又可以避免控制项增加导致开销的额外增加。在AOMDV路由协议中，Hello包是路由维护的重要控制包，它通过周期性的广播检测与其他节点的连通，虽然不能像RREP消息报文一样将路径的状态信息更新至源节点，但这种路由维护机制为路径的状态监测提供了可能，Hello包的生存周期只有一跳，为了使其能够在一跳的范围内起到传递路径状态信息的作用，对Hello报文的格式进行了相应扩展，添加了节点队列缓存比，改进后的Hello包格式如图3所示。

改进后的Hello消息处理步骤如下。

1）节点在规定周期时间（Lifetime）收到邻居节点的Hello消息。

2）对Hello消息格式中的节点队列缓存比项进行判别：

①缓存比大于缓存閾值，判定节点失效;

②缓存比小于阈值，根据式（1）计算新的跳数。

3）节点有效，增加该路由生存时间，增加生存时间至少为

Allow_Hello_Loss×Hello_interval。

4）更新序列号。

每个节点收到Hello消息都进行如上的处理，从而维护并确认出一条基于节点缓存信息最小的跳数最短路径。

2.2 通过改进RREP消息来收集路径状况

在AOMDV协议中，RREP消息报文是由一条路径的目的节点或者含有到目的节点路由的中间节点产生和发送的控制报文，同时也能够建立正向的路由路径。RREP消息报文的这种特点能够实现对路径状态的收集和上报，在LB-AOMDV路由协议中对RREP消息报文进行了拓展，加入了节点处信息队列缓存比项，当节点接收到RREP消息报文时，除了更新跳数等信息外，还需要将节点当前的链路状态与RREP消息报文中的状态项作对比，将在节点前等待发送数据包的队列长度添加到RREP消息报文中，当RREP消息报文沿着一条活动路由传送到源节点吋，源节点会获取其路由表中存储收集到的路径状态信息，有利于进行路径在本协议选定策略下的最优选择，拓展后的RREP消息格式如图4所示。

假设目的节点接收到了由源节点产生的经过中间节点转发的RREQ包。目的节点接收到针对自己的RREQ包之后，进行以下操作。

1）比较RREQ包中的目的节点序列号和自己的序列号。

2）如果自己的序列号比目的序列号小，则会将自己的序列号加1。

3）目的节点将其序列号或者加1更新后的序列号插入RREP包的目的节点序列号域中，同时将Hop Count域清零。

4）RREP按照路由表规则向源节点传送，每经过一个节点更新队列缓存比项，根据式（1）更新跳数。

当源节点接收到路径消息时，已经对每条路径的Level等级和作比较，选择Level等级小、跳数小、节点处排队信息相对较少的路径进行传输。改进后的RREP消息处理如图5所示。

3 仿真结果和讨论

3.1 仿真环境和仿真参数介绍

1986年麻省理工学院几位教授联合开发了OPNET（optimized network engineer tool），这是一种进行网络优化的工程工具，本文使用的是其仿真产品OPNET Modeler，与Windows系统兼容，使用起来比较方便，有以下几个特点。

1）仿真器符合经典的OSI七层模型机制，层与层之间是以相对独立的方式存在的，能够实现对分层协议的单独仿真。

2）采用三层建模机制，最上层与实际网络相对应，中间为节点层，最底层为进程层，是最重要的层，可以实现对上层各种模块的功能描述。

3）具有十分强大的数据运算和统计能力。

使用OPNET Modeler仿真平台，信道采用Mobile-to-Mobile模型，节点采用随机路径移动模型，MAC层采用IEEE 802.11标准。使用恒定比特率（CBR）进行仿真，节点数为18个，仿真时间为300 s，试验次数为10次，具体参数设置如表2所示。

为了衡量自组网的网络性能，采取了以下3个仿真参量。

1）分组投递率

目的节点接收到的数据包个数与源发送的数据包个数之比反映了网络传输的可靠性，网络的投递率越高，传输可靠性越大。

分组投递率=接收数据包个数发送数据包个数。 （4）

2）端到端的平均时延

一个数据包从源节点传输到目的节点耗费的总时间称为端到端传输时延，是Ad Hoc网络非常重要的性能，反映出了路由的有效性。

平均时延=∑接收时间-发送时间发送数据包个数。（5）

3）路由开销

网络中用于路由发现和维护的有效控制数据包的数量与节点接收到的总的数据包数量的比值称为路由开销。

路由開销=控制包个数接收到数据包个数。（6）

3.2 仿真结果分析

为测试LB-AOMDV路由协议的负载均衡性能，在设置固定最大移动速率4 m/s情况下，使数据包发包速率在1～10 packets/s变化来改变网络的负载状况，其他参数如3.1节所述，图6显示了当数据包发包速率变化时数据包传输时延的变化情况;图7显示了数据包发包速率变化时数据包投递成功率的变化情况;图8显示了LB-AOMDV路由协议和原协议工作时的路由开销情况。

由图6可知，在发包速率在1～5 packets/s时，网络中各节点的负载较小，网络拥塞现象不明显，LB-AOMDV协议与原AOMDV协议的传输时延基本相同，在发包速率大于6 packets/s时，LB-AOMDV路由协议的时延增速较缓，状况明显好于AOMDV协议，这是因为在中间节点处产生了网络拥塞，LB-AOMDV路由协议能够通过虚拟跳数尽量避开高负载节点，提高了网络的性能。

由图7可知，随着发包速率的增加，2种协议的投递率都在减小，总体上LB-AOMDV协议的投递率情况要优于原AOMDV路由协议，LB-AOMDV路由协议的变化速度也较慢，尤其是在发包速率大于6 packets/s时，原AOMDV协议的投递率急剧减小，这是由于中间节点在高负载下产生了数据包的丢失，LB-AOMDV路由协议通过对节点资源更合理的应用，对提高数据包的投递率取得了一定的效果。

由图8可知，LB-AOMDV协议的路由开销有所增加，这是因为虽然使用改进的RREP和Hello消息来检测和更新链路状态信息，没有增加额外的控制项，但是由于增加了控制报文的长度和判别次数，使得路由开销有所增加。

4 结 语

通过仿真分析得出相比于传统AOMDV路由协议，为了解决中间节点的频繁使用造成的节点拥塞，LB-AOMDV协议定义了节点处的队列缓存比，将节点状态分级处理，然后结合原AOMDV的最小跳数的路径选择依据，采用新的包含节点负载信息的虚拟跳数，并且通过对RREP，Hello包的拓展实现了对路径信息的更新和收集，方法较为简便且没有增加额外的控制项，能够有效提高网络的端到端时延，降低丢包率。特别是数据包发送速率较高时，LB-AOMDV算法的优势更为明显。但是改进算法和AOMDV协议一样，都属于备份多径路由协议，即当前路径中断时才启用备用路径，实际上是对有限资源的一定浪费，采用多条路径并行传输能有效提高链路的利用率，同时能提高无线网络的抗干扰性，AOMDV路由协议的改进优化还值得进一步深入研究。

参考文献/References：

[1] 肖宇，陈乐，肖楠.无线移动自组网及其关键技术[J].通讯世界，2020，27（7）：81-82.

[2] 舒伟彬.Ad hoc网络路由协议及度量准则的探究[J].山东工业技术，2018（24）：122.

[3] 杨君芳.Ad Hoc网络路由协议的研究与仿真[D].天津：天津职业技术师范大学，2018.

YANG Junfang.Research and Simulation of Ad Hoc Network Routing Protocols[D].Tianjin：Tianjin University of Techno-logy and Education，2018.

[4] 杜青松.战术MANET中的路由协议及QoS路由算法研究[D].长沙：国防科学技术大学，2015.

DU Qingsong. Research on Routing Protocols and QoS Routing Algorithms for Tactical MANETs[D].Changsha：National University  of Defense Technology， 2015.

[5] 任春利.移动自组网AOMDV协议改进研究[D].南昌：南昌航空大学，2014.

REN Chunli. Study on the Improvement of AOMDV Protocol in Mobile Ad Hoc Networks[D].Nanchang：Nanchang Hang-kong University，2014.

[6] 陈雪莹.Ad Hoc网络基于AODV路由协议的拥塞控制研究[D].长春：吉林大学，2019.

CHEN Xueying.Research on Congestion Control Based on AODV Routing Protocol in Ad Hoc Network[D].Changchun：Jilin University， 2019.

[7] 杨海博.无线Mesh网络中AOMDV路由协议的研究[J].电子世界，2020（21）：61-62.

[8] MAKHLOUF A M，GUIZANI M. SE-AOMDV secure and efficient AOMDV routing protocol for vehicular communications[J].International Journal of Information Security，2019，18（5）：665-676.

[9] BADDARI I，RIAHLA M A，MEZGHICHE M.A new AOMDV lifetime prolonging routing algorithm for Ad-Hoc networks[J].International Journal of Interdisciplinary Telecommunications and Networking，2019，11（4）：48-62.

[10]韩智洋.Ad Hoc网络中基于负载均衡的节能路由协议[D]. 合肥：安徽大学，2013.

HAN Zhiyang. Research of Load Balancing and  Energy Saving Routing Protocol in Ad Hoc Networks[D].Hefei：Anhui University，2013.

[11]周甜甜.多路径无线Mesh网络AOMDV协议分析与研究[D].沈阳：沈阳建筑大学，2019.

ZHOU Tiantian.The Analysis and Research on AOMDV Protocol of Multipath Wireless Mesh Networks[D].Shenyang：Shenyang Jianzhu University，2019.

[12]周毅.Ad Hoc网络中多径负载均衡协议研究[D].长沙：长沙理工大学，2014.

ZHOU Yi.The Research on Multipath Load Balancing Protocol in Ad Hoc Network[D].Changsha：Changsha University of Science and Technology， 2014.

[13]张敏.负载能量均衡的移动Ad Hoc网络多路径路由协议[D].西安：西安电子科技大学，2017.

ZHANG Min.Load and Energy Balanced Multipath Routing Protocol for Mobile Ad Hoc Network[D].Xi′an：Xi dian University，2017.

[14]李莉莉，张晓勇，岳伟.移动自组织网中基于贪婪蚁群算法的广播策略[J].系统工程与电子技术，2020，42（4）：926-932.

LI Lili， ZHANG Xiaoyong， YUE Wei. Broadcasting strategy based on greedy and ant colony algorithm in mobile ad hoc networks[J].Systems Engineering and Electronics， 2020， 42（4）：926-932.

[15]KAUR M，GANGAL A.Comparative analysis of various routing protocol in MANET[J].International Journal of Computer Applications，2015，118（8）：26-29.

[16]PARK  J. Congestion aware geographic routing protocol for wireless Ad Hoc and sensor networks[J].Wireless Personal Communications，2014，78（4）：1905-1916.

[17]赵新伟，刘伟.一种基于节点状态的MANET路由发现和建立策略[J].计算机科学，2019，46（6）：112-117.

ZHAO Xinwei，LIU Wei. MANET routing discovery and establishment strategy based on node state[J].Computer Science，2019，46（6）：112-117.

[18]孟艳群.MANET中带宽时延约束路由算法研究[D].重庆：重庆邮电大学，2018.

MENG Yanqun.Research on Bandwidth Delay Constrained Routing Algorithm in MANET[D].Chongqing：Chongqing University of Posts and Telecommunications，2018.

[19]彭幟.应急通信中基站自组织网络路由算法研究[D].重庆：重庆邮电大学，2017.

PENG Zhi. Research on Routing Algorithm of Self-organizing Network for Base Stationin Emergency Communication[D].Chongqing：Chongqing University of Posts and Telecommunications，2017.

[20]黄豪磊.基于链路感知的MANET和DTN混合路由协议的研究[D].北京：北京邮电大学，2017.

HUANG Haolei. Research on MANET and DTN Hybrid Routing Protocol Based on Link Sensing[D].Beijing：Beijing University of Posts and Telecommunications， 2017.

[21]RAJANA  U，RAJA K S V，JEYASEKAR A，et al. Energy-efficient predictive congestion control for wireless sensor networks[J].IET Wireless Sensor Systems，2015，5（3）：115-123.

收稿日期：2021-01-28;修回日期：2021-03-04;责任编辑：陈书欣

第一作者简介：郭少雄（1994—），男，河北石家庄人，硕士研究生，主要从事信号与信息处理方面的研究。

通讯作者：宋志群研究员。E-mail：zhiqunsy@163.com

郭少雄，李正伟，宋志群.

基于节点负载等级的自组网AOMDV路由协议改进方法[J].河北工业科技，2021，38（2）：109-115.

GUO Shaoxiong，LI Zhengwei， SONG Zhiqun.

Improved method of AOMDV routing protocol in Ad Hoc network based on node load level[J].Hebei Journal of Industrial Science and Technology，2021，38（2）：109-115.