基于Q学习算法的Ad Hoc网络自适应DSR协议研究

迟 凯

（中国电子科技集团公司第20研究所，西安 710068）

0 引 言

Ad Hoc网络区别于传统的有中心的网络，采用临时快速自组织建立网络的形式。由于其去中心化、抗打击，自愈性和鲁棒性强，在军事上得到了广泛应用。通过Ad Hoc网络能够把作战节点（如指挥所、舰船、战机等）有机地结合起来，协调指挥，形成统一的战力；还能够通过消息转发，形成战场共享信息态势，有效避免了电子战中单个节点受到针对性干扰丧失监测能力的发生。由于网络中的节点因为能量受限或者功率控制等原因，通信范围一般受限，需要通过多跳路由的方式实现范围外的通信，则Ad Hoc网络路由协议对网络质量起到关键作用。Ad Hoc网络中无线信道干扰、衰落、节点移动等造成拓扑变化快速、路由质量不稳定等多种问题，对路由算法提出了很大挑战。

路由算法可分为确定性路由算法和自适应路由算法。确定性路由算法是源节点在发送分组之前，预先寻找或者维护一条确定的发送路径，通过中继节点逐次送达至目的节点。自适应路由算法则在建立维护路由过程以及发送分组的过程中监测网络状态，根据中继节点或者邻居节点反馈的信息改变路由选择或者采用其他能够提升分组送达率、降低拥塞的策略来提升服务质量。确定性路由算法虽然简单、有效、容易实现，却极易受到网络拥塞节点或链路的影响，出现短板效应。因为自适应路由能够对拓扑变化迅速、链路状态突变等情况及时作出反应，调整本地节点业务发送，适应网络当前变化，提高网络性能，其在Ad Hoc网络研究领域具有重要的价值。

传统的Ad Hoc网络路由协议可分为表驱动（先应式）路由协议、按需（反应式）路由协议和混合路由协议。主要区别在于路由建立的方式不同。表驱动协议通过定期交换路由信息分组，每个节点维护1张或者多张路由表，记录到其他节点的路由信息。因此，采用表驱动路由协议的节点在产生业务之前就预先准备好了一条发送路径，并定期进行维护，及时对路由情况的变化进行更新，虽然增加了额外的路由维护开销，但业务类消息一旦到达可直接查询路由表发送，时延较小。图1为现有部分表驱动协议［1］。

图1 现有部分表驱动路由协议

这些表驱动协议的区别主要为每个节点维护路由表的大小和个数不同，并且维护路由表的过程中，更新信息在网络中传播的方式不同。

不同于表驱动式协议，按需路由协议是根据发送数据分组的需要按需进行路由发现的过程，即在有业务需要发送之前，并不维护路由，也没有任何开销。当业务分组需要发送而节点没有相应路由信息时，节点发起1个路由发现过程，通过邻居节点不断中继寻找到目的节点的可能路径，建立路由后也只进行简单的维护，并且到达一定生命期就删除路由。按需协议开销极小，只有在有业务需要发送时才带来一定开销，没有产生业务的时间段基本处于静默状态，不容易被发现和定位，在战场环境下有较高的隐蔽性。图2是现有的部分按需路由协议［1］。

图2 现有按需路由协议

按需路由协议之间的主要区别在于选路的标准不同，比如动态源路由（DSR）协议，无线自组网按需距离矢量（AODV）协议以最短路径为选择路由的标准，基于稳定性的路由（ABR）协议以有效时间为选择标准。另外存储路由信息的方式也有所不同，DSR协议完整记录整条路径信息，AODV则只记录逐跳信息。

在Ad Hoc网络中，表驱动路由协议主要应用于业务较均衡、拓扑变化较慢的网络状况下，而按需路由协议则适用于突发业务多、拓扑变化迅速、同时对功率控制、节点能量有特殊要求的网路状况下。

1 DSR协议的研究

DSR协议是一种简单高效的适用于移动Ad Hoc网络（MANET）的按需路由协议，属于卡耐基-梅隆大学Monarch项目的一部分［2］，经过多次修订和订正，已日趋完善。其主要特点是使用源路由机制进行分组转发，即在有业务分组需要发送的时候，源节点发起路由发现过程，建立路由之后在每个数据分组的包头中都包含了这一分组将要通过的完整的路由节点地址列表。转发分组的中继节点也能够完整地获知该分组所经路径的完整信息，从而能够消除路由环路，并且支持单向和非对称路由，源节点还可以根据路由发现阶段形成的完整路径信息以某种策略选择和控制当前数据分组所需路由，有相当的灵活性。然而DSR协议的缺点也很明显，因为数据分组携带了所经过的完整的路由信息，增加了额外的开销，相对于其他按需路由协议开销过大，降低了带宽利用率，扩展性差。IETF MANET工作组建议该协议使用于不大于200个节点的网络。

正因为DSR采用基于源路由的实现方式，源节点在路由建立阶段通过目的节点回溯的路由应答消息获知了整条路径上的节点列表，从而有依据该列表信息采取进一步策略的可能。目前DSR协议的改进算法主要有：基于DSR的分层路由协议，如DOA（DSR over AODV）是一种结 合 DSR 和AODV特点实现的分层路由协议，在层次内使用AODV协议，在各层次间使用DSR 协议［3］；基于DSR的服务质量（Qos）路由协议［4］，在路由发现阶段收集Qos参量用于选择一系列不相重叠的路由，根据不同的Qos要求提供节点使用，并达到减小网络拥塞、平衡负载的目的；基于链路稳定性算法的DSR协议［5］，通过链路稳定性算法选择稳定性高的路由，降低了路由断开次数和丢包率，并且不需要增加额外的节点信息交换报文。

2 自适应DSR协议

2.1 Q学习算法

2.1.1 Q学习算法概述

强化学习，又称增强学习或再励学习，是求解序贯优化决策问题的一种机器学习方法。在强化学习理论和算法研究中，通常将序贯优化决策问题建模为马尔科夫决策过程［6］。强化学习算法并不要求已知马尔科夫决策过程的状态转移模型，因此在不确定的优化决策问题中具有更广泛的应用前景。

强化学习是智能系统从环境到行为映射的学习，以使奖励信号函数值最大化。强化学习中由环境提供的强化信号是对产生动作的好坏作一种评价，智能系统通过评价对行为的反馈进行学习，不断改进行动方案以适应环境。强化学习算法能够在无法获得完整环境信息的情况下根据感知到的状态对网络的各参数进行重配置，进而适应不断变化的网络环境，提高网络的性能。增强学习在与环境相互作用的过程中，通过极大化或极小化累积回报来选择策略，即学习的目标函数是学习一个控制策略，以此建立从状态s到动作a的映射，如图3所示。

图3 Agent与环境交互

Q学习算法是由Watkins提出的一种无模型强化学习算法［7］，被认为是强化学习领域的重要突破。Q-learning选择的策略是选取当前状态s下具有最佳Q值的动作，即选取具有最大反馈奖赏的动作来触发下一次环境反馈。通过直接优化1个可迭代计算的动作值函数Q（s，a）找到一个策略使得期望奖赏总和最大。每次的迭代中都需要考察行为带来的影响，确保学习过程收敛。

Q-learning作为一种强化学习算法，同样通过马尔科夫决策过程来建模，由于转移概率和所获得的环境奖赏未知，其采用迭代的方法，以环境-动作奖赏值Q＊（s，a） 作为动作执行效果的衡量标准。Q＊（s，a） 表示Agent在状态s下采用的策略使得所获得的累积奖赏值最大。最优的策略即在对应给定的状态，选择某个行为使得累计的奖赏值最大。Q值是指在环境状态为x时选择策略π并执行动作a所获得的累计奖赏值。

2.1.2 Q学习算法在路由协议中的应用

目前，Q-learning在复杂的优化控制问题中有了成功的应用，其通过环境反馈来积累策略选择的思想也被一些研究人员应用于网络路由算法设计中。Minsoo Lee等人［8］提出了一种将 Q-learning运用于减小无线网络路由控制开销的方法，如图4所示。

该算法根据源节点在每次路由建立过程中的路由发现时延更新表征网络状况的Q值，根据Q值的变化情况判断网络发展趋势，从而增加或减小路由生存期和hello周期。

图4 Q-learning减小控制开销算法思想

Boyan等人［9］提出了一种将Q-learning运用于路径选择的路由方法，如图5所示。该方法能够根据周围邻居节点的负载情况来选择路径，在网络高负载的情况下能够获得相对较小的时延。

图5 Q-learning路径选择算法思想

Q-learning用于路径选择的算法能够在预先不知道网络的拓扑信息和业务类型的情况下，在动态变化的网络中发现有效的分组传输策略。每个节点保存一个Q值表用于记录通过它的邻居节点到达其所有的目的节点的分组传输时延估计。Qx（d，y）表示分组P经过节点x的邻节点y到达目的节点d所需时间的估计，这包括了分组P在节点x的排队时延。节点首先选择Q值最小的邻居节点作为下一跳节点发送业务分组，之后得到下一跳节点对路径上剩余时间的估计，对Q值进行修正，直到Q值不再变化，则找到最佳路由。

2.2 Q＿DSR协议

DSR协议采用源路由的实现方式，源节点可以获得整条路径的节点信息，当有多条路径同时存在时有较高的自主权，不依赖于中继节点对路径信息的获知和存储。然而开销过大是DSR协议最主要的缺点，为了保证整条路径信息的传递，DSR协议的路由请求和路由应答分组开销较大，在网络拓扑变化迅速、路由信息失效率高、需要不断地发起路由请求的情况下尤为严重。在DSR路由协议中引入Q学习算法，可以较为有效地降低开销，从而提高网络的吞吐量。

2.2.1 路由建立阶段

DSR协议是基于按需驱动的，即每当有业务消息需要发送时查询是否存在到达目的节点的路由信息，如果没有则发起路由请求消息，路由请求消息通过中继节点广播方式扩散到网络中，目的节点收到后则回复路由应答消息逐条回溯到源节点。如果建立的路径不稳定，路由很快失效，则源节点发现路由失效后就需要重新发起路由请求消息重新建立路由，这便会导致开销增大。这里引入Q学习算法，在路由建立阶段借鉴了 Minsoo Lee等［8］提出的方法，当源节点在第1次接收路由应答分组时，根据发送路由请求消息时记录下的时间和接收路由应答分组的时间差计算端到端时延估计Test。

由上述时延估计值Test通过如下公式计算归一化路径时延估计值γ：式中：Tetemax为网络可允许的端到端时延的最大值。

根据归一化路径时延估计值γ，依据t-1时刻Q值对当前时刻描述网络稳定性的Qs值和不稳定性的Quns值分别进行更新，得到更新后的网络稳定性表征值：

式中：Qs［t］ 为节点在t时刻网络稳定性的Qs值；Quns［t］ 为节点在t时刻网络不稳定性的Quns值；α为学习因子，取值范围为0≤α＜1。

源节点根据更新结果执行不同行为，当Qs［t］＞Quns［t］ 时，判断网络状态向不稳定发展，减小本条路由的路由生命期；当Qs［t］ ＜Quns［t］ 时，判断网络状态向稳定发展，增大本条路由的路由生命期。

该方法能够在路由建立阶段自主感知网络的状态，并根据所感知的网络状态自适应配置对应状态下合适的路由生存期，增大稳定路由的存在时间，减小不稳定路由的存在时间，从而当网络状况良好的时候减小路径信息仍然有效，然而因为生存期到达而被销毁的路由数，从而减小发起路由请求消息的次数，即减小开销；当网络状况恶化的时候缩短路由生命期，在一定概率上当路由信息没有完全失效、发送的分组完全没有回复之前就销毁路由，开始新的发起路由请求的流程。虽然缩短路由生命期会增加一定的开销，但是业务分组发出之后没有回应，源节点判断路由已失效之后再重新发起路由请求会带来额外的延时，导致业务消息端到端时延增加，而在网络状况较差的情况下，一条路由往往还没有到达生命期时就已经失效，所以在网络状况较差的情况下适当地减小生命期不会带来过多的开销，同时有助于源节点的路由反应速度。

2.2.2 路由维护阶段

通过在路由建立阶段引入Q学习算法动态调整本次建立的路由生存期，可以在不同的网络状态下自适应地符合当前的需要。然而Ad Hoc网络情况的变化往往是突发的，路由建立阶段作出的对网络状况的评估有时效性，因此需要在路由建立后，发送业务消息阶段（即路由信息的实际使用阶段）对网络状况进行评估并做出自适应的调整。这里采用基于Q-learning的应答（ACK）消息监测方法，对业务消息的应答ACK进行监控，记录收到业务类消息ACK的时延并迭代计算。ACK在路由协议中一般作为发送成功的标志，规定时间内收不到ACK则进行重发或认为发送失败。这里将源节点收到ACK的时刻与发出数据业务的时刻之间时延作为当前路径质量的评估因素。节点开始发送业务类消息时，开始记录每个应答ACK的到达时刻，取最大的时延Tack作为Tmax，并代入计算当前时刻网络稳定性。当连续3次判断网络状态在向不稳定发展时，则尝试路由切换。

路由切换的过程如下：源节点将到达的数据分组，依然采用已建立的路由Rfound发送，同时发起一个路由请求消息；收到路由应答消息后保存至路由应答消息链表中，并提取路由信息形成待切换路由Rswitch［i］，源节点将待切换路由与当前正在使用的路由信息进行比对，通过中继节点相同程度赋予每个待切换路由新鲜度Rf，中继节点与当前路由完全不同Rf为100，完全相同则为0；源节点通过比对每个待切换路由Rswitch［i］的Rf值，选出中继节点最不相同的一条作为最可能的切换路由，当业务分组到达后则采用新的路由发送分组。因为切换路由是当原有路由稳定性不断恶化的情况下在失效前建立的备份路由，则其选择标准为与原有路由中继节点差异最大，从而最大可能避免原有路由中链路状态恶化的中继节点影响。切换路由的生命期与原路由相同，并且只建立1次，视为原有路由的延续。

中继节点转发业务类消息的同时，也监测本地转发的回溯到源节点的ACK回复消息，同时代入Q学习算法迭代计算。当连续3次判断网络状态不稳定后，认为当前路由在向不稳定状态发展，此时中继节点在需要进行转发至源节点的ACK消息上设置一个告警标志位。源节点收到ACK之后读取标志位，尝试进行路由切换。

当源节点每连续3次判断当前网络状态趋于稳定的时候，则增大当前路由生命周期，继续维持当前较好的路由。直到路由生命结束或者连续3次判断网络状态不稳定后发起路由建立过程。通过对业务类消息ACK回复的监测，可以在路由维护阶段实时自适应地对当前路由状态做1个预判，从而及时寻找替代路由。源节点不必当路由失效发送失败后才被动地开始建立路由，在路由状况开始恶化的时候便可以试图建立新路由准备进行路由切换，通过这种策略使得源节点更加灵活，能够自适应地调整路由参数，以契合网络当前状态。源节点处理业务类消息ACK的流程如图6所示。

图6 源节点收到业务消息ACK处理流程

3 仿真和分析

目前使用较为普遍的网络仿真软件有OPNET［10］和NS2。本文采用OPNET对协议进行仿真分析。OPNET Modeler采用了3层建模机制，分别在进程层、节点层和网络层进行建模。进程描述通过状态机的转移体现逻辑状态变化，具有逻辑清晰、维护方便的特点。仿真运行的过程中，OPNET采用了离散事件驱动的模拟机制［10］，即当事件产生时，仿真核心触发事件驱动，推动仿真时间推进。

为比较基于Q-learning的自适应DSR协议的性能，建立一个简单的Ad Hoc网络。在600m×600m的范围内，随机放置了100个节点，节点移动模型采用随机路点移动模型，节点最大通信范围为200m，通信为双向对称链路。图7～图10为仿真结果。

图7 路由请求分组数量

从图7可以看出，加入Q学习算法后DSR协议在业务量较轻的情况下能明显降低路由请求分组的数量。因为网络状况较好的时候Q-DSR能够根据Q学习迭代计算结果动态地增加路由生存期，使得链路质量较好的路由能够更长时间地进行服务，从而降低非必要的路由请求分组（RREQ）发送概率。而路由请求分组是以泛洪的方式在网络中扩散，对网络的影响较大，降低路由请求分组数能够有效降低开销。

从图8可看出，通过Q学习对业务类消息的ACK接收时延的计算，能够判断当前路由质量发生怎样的变化，从而及时调整路由生存期或切换新路由；而传统的DSR协议只有当业务分组发送失败才尝试建立新路由，导致业务分组时延额外增加了等待路由建立时间，浪费时间和开销资源。因为路由反应及时，在业务量增大的情况下，能够保持高于传统DSR协议的吞吐量。

由图9可看出，因为能够及时判断出路由质量，故采取延长生存期或者发起路由切换的策略，从而加快路由反应。在一定概率上，当路由质量高时继续维护本条路由，当路由质量下降时及时采取替补

图8 吞吐量

策略，从而自适应地在节点发送失败之前做出调整。Q＿DSR协议能够保持较低的端到端时延。

图9 端到端时延

选取业务量为4packets／s，通过改变速度测试Q＿DSR与传统DSR协议在拓扑变化情况下的端到端性能，从图10可以看出，随着节点运动速度的增加，拓扑变化加剧，传统DSR路由失效率增加；而当业务消息发送失败后才开始建立新路由，则带来额外的等待时延。基于Q学习算法的DSR协议能够判断路由质量，下降后及时切换新路由，在一定概率上节省了等待时间，保持较低的端到端时延。在网络拓扑变换迅速、链路质量不稳定的网络状况下尤为明显。

图10 节点不同移动速度的端到端时延

4 结束语

自适应Q＿DSR协议的改进是在路由发现阶段能够根据建立路由时刻的网络状态动态调整路由生存期，使得状态良好情况下的路由能够服务更久从而降低开销；同时在路由维护阶段通过监测ACK判断业务消息发送时刻的网络状态主动切换质量开始恶化的路由，从而提高路由反应，提升吞吐量性能，降低端到端时延。通过仿真可以看出自适应Q＿DSR协议能够在网路状态良好的情况下减小开销，而在状态较差的情况下减少路由等待时间，加快路由反应速度，从而提升端到端性能。不足的是，通过ACK监测有时不能准确反应发送业务消息时刻的网络状态，存在误判的可能，需要进一步改进来提高算法的准确度。在网络状态变化较快、节点较多、形成路由的跳数较大的情况下，自适应Q＿DSR协议是较简单和高效的路由协议。

［1］ 张禄林，李承恕.MANET路由选择协议的比较分析研究［J］.电子学报，2000，28（11）：88-92.

［2］ Johnson David B，Maltz David A.Protocols for adaptive wireless and mobile networking［J］.IEEE Personal Communications，1996，3（1）：34-42.

［3］ Rendong Bai，Singhal M.DOA：DSR over AODV routing for mobile Ad Hoc networks［J］.IEEE Transactions Mobile Computing，2006，5（10）：1403-1416.

［4］ Hashim R，Nasir Q，Harous S.Adaptive Multi-path Qos aware dynamic source routing protocol for mobile Ad Hoc network［A］.Innovations in Information Technology［C］.Dubai，2006：1-5.

［5］ 孟利民，吴晚霞.基于链路稳定性算法的DSR协议研究［J］.通信学报，2008，29（11）：46-50.

［6］ Kaelbling L P，Littman M L，Moore A W.Reinforcement learning：a survey［J］.Journal of Artificial Intelligence Research，1996，4：237-285.

［7］ Watkins C，Dayan P.Q-learning［J］.Machine Learning，1992（3-4）：279-292.

［8］ Minsoo Lee，Dan Marconett，Xiaohui Ye，et al.Cognitive network management with reinforcement learning for wireless mesh networks［A］.IPOM 2007LNCS 4786［C］，Berlin，2007：168-179.

［9］ Boyan J A，Littman M L.Packet routing in dynamically changing networks：a reinforcement learning approach［A］.Advances In Neural Information Processing Systems［C］，1994：671-678.

［10］陈敏.OPNET网络仿真［M］.第1版.北京：清华大学出版社，2004.