基于Q学习的Ad Hoc网络路由协议的改进与研究∗

刘 芬 隋天宇 王叶群

（1.西南通信研究所 成都 610041）（2.空军工程大学 西安 710038）

1 引言

移动Ad-Hoc网络是一种节点可以自由移动通信的无线网络，建网形式比较灵活多变，网络配置也比较方便，成本低廉［1］。由于Ad-Hoc网络自身特点和外界条件的约束，要求路由协议具有较好的自适应性、稳定性和确保通信质量。

现有的Ad-Hoc网络路由协议从路由探索的角度可分为表驱动型和按需型两大类。表驱动型路由协议主要有OLSR、FSR、DSDV等，按需型路由协议主要有DSR、AODV、TORA等，本文以AODV协议的思想为例进行改进和探索。文献［2］提出的一种将Q学习方法依靠邻近节点提供的局部网络信息进行迭代并更新的动态算法。文献［3］根据Q值的变化调整路由生存时间和hello包的发送周期，以便减小网络的路由控制开销。文献［4］提出了一种高效节能的多路径传输的办法提高端到端的链路可靠性，本文拟融合Q算法应用在延长生命期的同时采用备用路径的想法平衡网络负载从而提高网络性能［5］。

2 Q学习的多路径路由协议

2.1 多径路由建立过程

源节点广播RREQ分组开始路由寻找过程，最短路径上的中间节点维护多条和其他路径没有交点的路径，这条路径称之为备用路径［6］，具体操作是在分组发送过程中，将节点消耗能量消耗过大的路径进行分流和权衡，采用备用路径进行数据包的分流或者通信。文献［7～8］中表明多径并行传输路径可用带宽对吞吐量的影响比较大，利用Q学习算法提高带宽的利用率。

2.2 Q学习路由协议框架建构

Q学习方法是强化学习中采用逐步迭代的方式逼近最优解的方法，目标是达到需要的状态并获取最高收益［9］。

文献［10］提供了一种Q学习算法在车载Ad Hoc网络中的应用，启发式Q学习算法可以解决文献中算法收敛过慢的问题。

基于路由协议建立的Q值更新公式如式（1）所示［11］：

其中，Qs( )d,x表示节点s选择邻居节点x作为下一跳节点，将分组转发到目的节点d的Q值，Γ(x)表示节点x的邻居集合，α为学习率，R为奖励值，若邻居节点x恰好是目的节点d，那么R=1，否则R=0，γx为动态折扣率。

步骤1 源节点广播RREQ分组：

源节点需要向目的节点发送数据包，发起路径寻找，向网络中广播RREQ分组，并记录下本次的发送时间。

步骤2 中继节点转发RREQ包：

由中间节点进行转发，整个过程中要加入一个时延避免拥塞，若找到目的节点，则直接回复RREP分组，并记录转发时间，尽可能多地寻找可用路径。

步骤3 更新网络的路由信息：

当RREP分组传播到源节点的时候，更新路由表信息。

步骤4 计算并启发最优下一个节点［12］：

在路径寻找过程中，将最小的时延作为反馈信息沿对应路径原路返回源节点，计算到达目的节点的总时延，如式（2）所示。

Delay( s,d,x)表示从源节点s，经过的下一跳节点为x，将分组传输到目的节点d的时延。时延最短，路径最优，用a*表示。

定义启发函数Hs( d,x)，从而启发当前节点选择当前最优下一节点，并更新相应的Q值。定义，如式（3）所示。

其中，Qs(d,x)表示s通过下一跳节点x到达目的节点d的Q值，y∈mΓ(asx)Qs(d,y)表示点s的所有邻居节点中到达目的节点的最高Q值。η是一个很小的正实数，取值0.01。

步骤5 源节点根据Q学习路由更新网络的路由生存期：

Q学习算法根据时延估计值评估当前的网络路径来设置路径的生存寿命，用Qs描述网络的稳定性，用Quns描述网络的不稳定性，根据归一化的端到端时延估计值γ更新网络值，如式（4）所示。

其中t代表当前时刻。

整个过程中根据图1的流程进行路由寿命的增加或者减少。

图1 路由寿命更新

步骤6 路由维护：

由于本文的改进协议是按需型协议，考虑业务量和负载超量的情况或者备用路径无法使用的情况，原链路中断的情况，当前节点发送一个分组，内容有拥塞节点的地址以及队列长度，方便备用路径的节点解决处理拥塞问题。为了保证通信更好地进行，引入Q学习的目标函数G［13］：为

式 一（5跳）中平均L f时为延当，前T估r是计 丢得系 包统后的等平待均重丢传包的率时，间。节点根据自己的情况进行学习，G表现了网络当前状态的趋势，G越小，网络回报越好。

2.3 路由协议性能指标体系

为了分析路由协议性能的好坏，可以通过一些指标来直观地描述出一种路由协议的优劣。常见的性能指标如下：吞吐量为单位时间内传送的数据量，越大越好；路由建立开销越小越好；平均端到端时延就是所有成功传送分组时延的平均数［14］，时延越小越好；目的节点应用层所丢弃的分组数目与源节点应用层所发送的分组数目的比值是分组丢弃率。

3 路由协议实验结果分析

本文使用NS3通过对网络整体吞吐量、分组丢包概率、端到端的平均时延、路由建立开销［15］等参数的性能进行计算机仿真，具体的网络环境如表1所示。

表1 仿真参数配置

为了讨论路由生存时间对路由协议性能的影响，使用优化后的路由协议，仿真的网络环境设置与表1相同，发包速率选取每秒6个包和10个包，节点移动速率为10m/s。

图2 路由生存周期与路由协议指标关系图

总的来说，图2表明随着路由生存周期的延长，网络的端到端时延和吞吐量变化趋势不是特别明朗，在路由寿命为5s的情况下，端到端的平均时延最小，11s之后整体平均时延呈下降趋势；在路由寿命为5s时，吞吐量最大，11s之后，吞吐量是上升趋势。

选取初始路由生存周期为5s，参数发包速率为10个/s进行之后的仿真。在不同的节点移动速度下，网络中的分组丢弃概率如图3（a）所示，多路径协议能够有效地改善分组丢弃情况，但是随着节点移动速度的增加，网络拓扑结构的多变，分组丢弃的概率变大。

节点移动速率与端到端的平均时延的关系如图3（b）所示，节点的移动速度越来越快，网络拓扑随之变化，路由的链路存在因为更新速率加快，寻找的频率增加，优化之后的协议缩短了分组的传送距离，提高了建立路径的概率。

图3 节点移动速率与路由协议性能关系图

节点的移动速率与吞吐量的关系如图3（c）所示，相比于传统的AODV协议来说，多条路径发送的原理虽然能避免碰撞和浪费等问题，但是降低了信道的利用率，导致吞吐量下降，分组丢弃概率的降低补偿了吞吐量，移动速率差距大，补偿效果越好。

节点移动速率与路由建立开销之间的关系如图3（d）所示，路由生存时间越大，路由寻找过程的频率就会越低，路由开销就越低，Q学习通过提高网络的稳定性，增加端到端的可靠性，降低开销。

4 结语

在网络需求和网络流量日益增长的今天，对路由的智能性要求也提高了，本文在按需AODV协议的思想基础上，将启发式Q学习算法应用在路径寻找和路径选择的过程中，传统Q学习算法应用在路由寿命调整中，详细描述了整个路由操作的过程，备用路径则是在发生网络拓扑变化，原网络链路等情况下，进行临时通信作用，改进后的路由协议优化了网络性能，降低路由控制开销，避免了持续性的网络拥塞，然后使用NS3网络对相关的路由协议参数进行了仿真，直接验证了备用路径思想和Q学习方法在路由协议运行过程中的优势。