一种改进的移动无线自组织网络路由算法

滕艳平，周浩令，王海珍，李丽丽

(齐齐哈尔大学计算机与控制工程学院，黑龙江 齐齐哈尔 161006)

1 引言

移动无线自组织网络(Mobile Ad Hoc Network，MANET)是一组带有无线收发装置的移动节点组成的无线通信网络，无需固定基础设施，网络中的节点利用自身的收发装置交换信息，MANET因组网灵活使其在军事和民用领域都得到了广泛的应用。但随着网络规模越来越大，节点的高速移动导致网络拓扑频繁变化，路由协议的研究已成为MANET最重要的核心内容。

按需距离矢量路由算法(Ad Hoc On-Demand Distance Vector，AODV)是一种专为MANET设计的路由协议，AODV路由协议结合了DSR路由协议和DSDV路由协议的优点，对高速移动的环境适应性高，但是其在路由请求时直接使用洪泛广播RREQ，且直接选择路由跳数最少的链路，并没有考虑到网络拓扑的频繁变化导致链路中断，以及在节点数量较多时，由于网络洪泛导致的广播风暴对网络性能的影响。选择稳定性高的路由是提高网络性能的一个有效措施。文中提出了一种基于GPS信息和Q学习相结合的AODV改进算法，即GQ-AODV。该算法同时考虑了节点位置和节点速度，采用节点位置计算偏差角度和前程值，节点与下一跳节点的相对速度来确定链路稳定度，最优下一跳选取可通过下一跳节点与其邻居节点的平均相对速度以及Q学习训练的下一跳节点与其邻居节点的历史平均相对速度来确定，从而提高了网络的整体性能。

2 基于距离和速度的度量定义

当地理位置可用的时候，下一跳选择主要依赖两个指标：有效度量和稳定度量。下面分别给出有效度量和稳定度量的相关定义。

2.1 有效度量

下一跳节点选取在目的节点方向上具备较大前程量并且偏差角度较小的邻居节点。文献[5]提出了二维前程策略，如图1所示，为当前节点，为目的节点，为的某邻居节点。有效度量如式(1)所示。其中前程值(如式(3))为节点在直线上的投影长度，偏差量(如式(4))为节点到直线的距离。由于∈(-，)，∈(0，)(其中为节点通信半径)，所以对其做(0，1)标准化(如式(5))，前程值和偏差量(0，1)标准化的结果如式(6)和式(7)。

图1 二维前程策略

=(+(1-))

(1)

其中∈(0，1)，式中及下文中的sigmoid函数(如式(2))，主要是为了归一化各项数据，便于各项指标的叠加。

(2)

(3)

(4)

其中表示节点和节点之间的距离。

(5)

(6)

(7)

2.2 稳定度量

当地理位置可用的时候，下一跳节点应选取稳定的邻居节点，这样链路更稳定，路径不易断开，网络更加健壮。稳定度量 (如式(8))使用三个指标：此节点和下一跳节点的相对速度、下一跳节点与邻居节点的平均相对速度以及下一跳节点与邻居节点的历史平均相对速度。其中下一跳节点与邻居节点的平均相对速度和下一跳节点与邻居节点的历史平均相对速度是为了避免路由下一跳选择陷入局部最优。

=-(·()+

·()+·())

(8)

其中++=1。

221 相对速度

相对速度指此节点和下一跳节点的相对速度，见图1，当节点在邻居节点中选取下一跳节点时，相对于的速度，见式(9)，下一跳选取相对速度越小的节点，则链路越稳定，越不容易中断，网络越健壮。

(9)

222 平均相对速度

平均相对速度指下一跳节点与邻居节点的平均相对速度，见式(10)。当邻居节点与其所有邻居节点的平均相对速度越小，则节点越稳定；选取稳定的节点作为下一跳节点，链路不易断开，其网络性能越好。

(10)

其中代表节点邻居节点的总数，代表第个节点。

223 历史平均相对速度

历史平均相对速度指下一跳节点与邻居节点的相对稳定程度，见式(11)，通过接收HELLO包采用强化学习中的Q学习来训练QB。

+1(，)=

((，)+(+1+max(+1，)))

(11)

其中是学习因子，且∈(0，1)。是折扣因子，且∈(0，1)。+1是+1时刻的奖赏，见式(12)。当节点收到包时，获取其当前平均相对速度+1，然后与上一时刻的作差，当时刻的平均相对速度和+1时刻的平均相对速度相差较小时，其相对稳定程度越大；同时，接收包越频繁，其稳定程度越大。

(12)

3 GQ-AODV算法的设计与实现

3.1 数据包结构的修改

为了使用节点的位置和速度信息，在原有包结构的基础上，对RREQ和RREP两个包结构进行了修改，增加了位置和速度等相关信息。

3.1.1 定义路由请求(RREQ)包数据结构

为了降低网络开销，避免网络拥塞，在路由请求()包消息格式中增加目的节点坐标和速度信息(、、、、)、源节点坐标和速度信息(、、、、)以及路由度量值(、)16个字节的信息。

312 定义路由回复()包数据结构

在路由请求()包消息格式中增加目的节点坐标和速度信息(、、、)、邻居节点的平均相对速度(NeighborAverageRelativeSpeed)和路由度量值(、)11个字节的信息。消息格式被包复用。

313 定义邻居表和路由表数据结构

当接收到包时，新增的信息格式有邻居节点的位置及速度信息、平均相对速度和历史平均相对速度，为了存储这些信息，邻居表增加、、、、平均相对速度和历史平均相对速度。

当接收到包和包时，新增的信息格式有节点的位置及速度信息，为了存储这些信息，路由表新增、、、和变量。

3.2 GQ-AODV算法的实现流程

321 下一跳节点选取策略

GQ-AODV算法是在AODV的基础上进行改进。加入了节点坐标和节点速度的地理位置信息。GQ-AODV算法改进了邻居表和路由表，当地理位置不可用时使用原AODV洪泛请求目的节点位置信息。当地理位置可用的时候使用Q学习转发策略，其下一跳选取应满足以下条件：

1) 在目的节点方向上较小偏差角度；

2) 在目的节点方向上较大前程值；

3) 在所有邻居节点中此节点和下一跳节点的相对速度较小；

4) 下一跳节点与其邻居节点的当前平均速度较小；

5) 下一跳节点与其邻居节点的历史平均速度较小(Q值)。

GQ-AODV算法使用地理位置信息以及节点间相对速度作为下一跳选择的度量，考虑到下一跳节点位置能够在目的节点方向上更靠近目的节点，同时考虑到节点移动性对网络拓扑稳定性的影响，当地理位置可用的时候，下一跳选取主要依赖两个指标：有效度量和稳定度量。使用学习选择最优下一跳，如式(13)所示。

+1(，)=

((，)+(+1+max(+1，)))

(13)

其中是学习因子，且∈(0，1)。是折扣因子，且∈(0，1)。为路由度量，在生成时初始化为0。+1是+1时刻的奖赏，见式(14)。

+1=(·+(1-)·)

(14)

其中∈(0，1)。

3.2.2 HELLO包的发送与接收

位置和速度信息的获取主要依赖HELLO包，同时RREQ和RREP两数据包也会携带位置和速度信息。所有节点间隔HELLO＿INTERVAL定时广播一跳HELLO包，HELLO包中携带节点的位置和速度等信息广播到邻居节点。

节点监测上一个HELLO＿INTERVAL内是否发送HELLO包广播，如果没有，节点会广播TTL=1的RREP，即HELLO消息。节点获取自身的GPS信息，并通过式(11)计算平均相对速度ARS，由于NS3缓存写入和读取不支持有符号类型，所以在这里对其做一个拆解，使用字段Sign记录符号类型。广播HELLO包的流程如图2所示。

当节点接收到HELLO包时，首先对包中的无符号类型整合还原成原有符号类型。然后节点查找自己的邻居表，若存在此节点的邻居条目，则通过原条目中平均相对速度ARS与本次平均相对速度ARS计算出奖励值，并通过Q学习训练历史平均相对速度QB；否则直接更新邻居表和路由表。接收HELLO包的流程如图3所示。

图2 广播包流程 图3 接收HELLO包流程

3.2.3 RREQ包的发送与接收

当需要发送数据时，没有到达目的节点的有效路由，就需要发起路由请求。在AODV的基础上保留了原RREQ洪泛模式，当目的节点GPS信息不可用的时候，采用原AODV路由请求洪泛，寻找目的节点，并通过RREP带回目的节点的GPS信息。

发送RREQ消息流程如图4所示。当需要发送RREQ包时，首先获取节点自身的GPS信息；当不存在目的节点GPS信息时，节点采用原AODV 洪泛模式寻找目的节点；当目的节点GPS信息可用时，根据式(1)选择最优下一跳，调用SendRequest()，初始化RREQ并发送。

图4 发送RREQ包流程

图5 接收RREQ包流程

当节点接收到RREQ包时，其流程如图5所示。首先更新路由表和邻居表。若此节点是目的节点或者存在到目的节点的路由时，回复RREP；否则，判断RREQ消息中目的节点GPS信息是否有效，如果无效，则收到的RREQ是原始AODV洪泛的消息，则采取原AODV洪泛时的路由策略；若RREQ消息中目的节点的GPS信息有效，则根据式(1)选择最优下一跳，转发RREQ消息。

4 NS3仿真与对比分析

为了验证GQ-AODV算法与AODV性能优劣，在Ubuntu18.04下使用Network Simulator 3(3.29)仿真平台。对两种算法进行仿真及对比分析。仿真场景参数如表1所示。

无线网络协议性能评价指标使用平均端到端延时、抖动、平均分组投递率、平均吞吐量和归一化路由开销。

表1 仿真场景参数

4.1 节点数量对网络性能的影响

本节仿真主要观察节点数量对路由协议性能的影响，实验变量设置如表2所示。在表1仿真场景下进行的实验。仿真结果如图6所示。

表2 实验变量

对比分析：图6(a)显示了平均端到端时延与节点数量的关系。图6(b)显示了网络抖动与节点数量的关系。由图6(a)(b)可知，随着节点数量的增加，AODV协议抖动和端到端时延都随之增加，GQ-AODV协议抖动和端到端时延基本保持平稳，且GQ-AODV的端到端时延和抖动远低于AODV。这是因为随着节点密度的增大，路由请求洪泛会造成链路占用率高，可能会造成拥塞，增加端到端时延和抖动。而GQ-AODV选择最优下一跳节点，避免洪泛引起的拥塞。GQ-AODV算法在选择下一跳时，其跳数并不会随着节点密度的增加而增加，在节点密集时，路由下一跳可选择的节点多，会选择出更优的下一跳节点，所以其端到端时延和抖动基本保持平稳并且低于AODV。

图6(c)显示了平均分组投递率与节点数量的关系。图6(d)显示了平均吞吐量与节点数量的关系。由图6(c)(d)可知，随着节点数量的增加，两种协议分组投递率和吞吐量都会随着减少，其中GQ-AODV的分组投递率和吞吐量基本高于AODV。相比AODV的洪泛机制，GQ-AODV在选择下一跳节点时，考虑了与下一跳节点的相对速度、下一跳节点与其邻居节点的平均相对速度以及下一跳节点与其邻居节点的历史平均相对速度，所以其链路稳定性更强，不容易中断，可以维持一个比较好的分组投递率和吞吐量。

图6 不同节点数量对两路由协议性能影响

图6(e)显示了归一化路由开销与节点数量的关系。由图6(e)可知，AODV协议的归一化路由开销远大于GQ-AODV协议，且随着节点数量的增加，AODV归一化开销的增长速度原大于GQ-AODV协议。随着节点数量的增加，节点密度随着增大，节点的邻居节点也会增加，AODV协议路由请求时采用洪泛机制，邻居节点广播导致了其路由包数量也随着增加。而GQ-AODV协议在地理位置可用时，避免使用广播，直接选择最优下一跳节点，这就有效降低了归一化路由开销。

4.2 节点最大移动速度对网络性能的影响

本节仿真主要观察节点最大移动速度对路由协议性能的影响，实验变量设置如表3所示。在表1仿真场景下进行的实验。仿真结果如图7所示。

表3 实验变量

对比分析：图7(a)显示了平均端到端时延与节点最大移动速度的关系。图7(b)显示了网络抖动与最大移动速度的关系。由图7(a)(b)可知，GQ-AODV协议的时延和抖动远低于AODV协议，且随着节点最大移动速度的增加而缓慢增大。这是因为当地理位置可用时，节点选择最优下一跳，链路不易断开，更稳定，端到端时延和抖动主要来自于队列分组等待和重传机制，所以GQ-AODV协议的端到端时延和抖动远小于AODV协议，但是随着节点最大移动速度的增加，链路中断的概率增大，所以其随着节点最大移动速度的增大而缓慢增大。

图7 不同节点最大移动速度对两路由协议性能影响

图7(c)显示了平均分组投递率与节点最大移动速度的关系。图7(d)显示了平均吞吐量与节点最大移动速度的关系。由图7(c)(d)可知，GQ-AODV协议的平均投递率和吞吐量均大于AODV协议，这是因为AODV在路由请求阶段采用了洪泛，而GQ-AODV使用GPS信息选取稳定的最优下一跳，所以其平均分组投递率和吞吐量要大于AODV协议。

图7(e)显示了归一化路由开销与节点最大移动速度的关系。由图7(e)可知，GQ-AODV协议的归一化路由开销远小于AODV协议，这是因为AODV协议在路由请求阶段采用洪泛，而GQ-AODV协议使用GPS信息选取最优下一跳，这样就会省去很多的开销，而且GQ-AODV协议通过节点与其下一跳节点的相对速度、下一跳节点与其邻居节点的平均相对速度以及下一跳节点与其邻居节点间的历史平均相对速度选取最稳定的链路，这样链路稳定性增大，链路断开的可能性减小，避免了频繁的路由请求，从而使得GQ-AODV协议的归一化路由开销低于AODV协议。

5 结论

在对现有的AODV路由算法分析和研究基础上，本文提出了一种基于GPS信息和Q学习相结合的AODV改进方案。GQ-AODV算法使用有效度量和稳定度量来选择最优下一跳节点，对接收的HELLO包通过Q学习训练邻居节点的历史平均相对速度，以便在发送RREQ包时可获取最优路由。NS3仿真结果表明，随着节点数量的增加以及节点最大移动速度的增大，GQ-AODV算法比AODV算法能更好的适应移动无线自组织网络的各种场景，其网络性能各项指标均有很大提升。