域内路由算法综述

王志浩，郗海龙，许萌签，刘晓东*，潘 宁，肖 哲

(1.中国电子科技集团公司第五十四研究所，河北 石家庄 050081；2.北海舰队参谋部，山东 青岛 266000)

0 引言

近年来，随着移动通信技术、云计算技术以及互联网应用的高速发展，大量的移动终端和智能物联网设备不断地接入网络，通信网络中正经历着爆炸式的业务流量增长。由于当前网络中的业务量种类非常复杂并且规模十分庞大，业务流量经常在一个较大的时间范围内波动，传统的网络业务路由策略已难以适应目前不断变化的网络环境。

路由算法通常分为静态路由算法和动态路由算法2类。静态路由算法无法根据网络变化做出相应改变，因此不适用于大型或易变的网络。动态路由算法通过分析网络状态信息，可即时地或周期性地调整路由策略[1]。动态路由算法应用广泛，较为常见的有RIP,IGRP,OSPF和IS-IS等。这些算法已被广泛部署在各类环境中，但无法满足不同特征网络数据流的差异化需求。找到一种高效的、自适应的网络业务路由控制方案来确保网络的服务质量(Quality of Service,QoS)，减少不必要的网络资源开销并提高运营商设备资源利用率，是目前通信网络优化中一个亟待解决的问题。

自2006年以来，机器学习相关技术取得了一系列巨大的突破，使得通过人工智能技术来实现路由优化成为一种可行的方法。软件定义网络(Software Defined Network,SDN)的提出使得对网络进行集中控制得以实现[2]，该架构摆脱了硬件设备对网络的限制，使网络具有灵活可编程性等优点，实现了网络控制平面和数据平面的解耦合，智能路由算法能够作为一个应用运行在SDN服务器中，给机器学习在路由机制方面的应用带来了新的研究方向[3]。

近年来,路由算法依照其所应用的方法类型主要分为传统动态路由算法、基于监督学习的智能路由算法及基于强化学习的智能路由算法。本文通过调研相关研究文献，从传统路由和基于机器学习的路由等角度分析各类智能算法发展，阐述了智能路由研究中面临的机遇与挑战，并展望了未来智能路由算法研究方向。

1 传统动态路由算法

传统动态路由算法可分为基于最优化方法的路由算法及基于启发式方法的路由算法2类:基于最优化方法的路由算法有Dijkstra算法、Floyd算法和LPA*算法等，在给定约束条件条件下，给出使某一(或某些)指标达到最优的路由规划；基于启发式方法的路由算法主要采用蚁群算法、蜂群算法和粒子群算法等，在某些复杂网络中，以可接受的代价给出组合优化问题的一个可行路由解。这些算法由于简单的结构及较高的稳定性，已在大量环境下被部署使用，本节通过调研学术界相关研究，主要介绍传统动态路由算法的研究方向及各类算法应用场景和实验效果。

1.1 基于最优化方法的路由算法

针对可预测无线网络中的路由设计问题，考虑路由成本和路由可靠性，文献[4]提出了分层最短路由算法(Hierarchical Shortest Path Algorithm,HSRA)。该算法将可预测的无线网络描述为一系列静态图并建模为时空图，空间链路为2个节点之间的无线链路，而时间链路表示节点将其数据包从一个时隙传送到下一个时隙。该算法将数据包通过空间链路转发或通过时间链路保存而产生的成本及链路可靠性概率作为优化目标，使用分层最短路径算法查找2个附加权重下的路径，实验表明HSRA在路由成本及可靠性方面均优于传染性路由及距离矢量路由。该算法对网络状态监测要求较高，主要针对可预测无线网络，无法解决传统自组织网络(Ad Hoc)中的可靠路由问题。

除了对可靠性保障的需求，许多应用程序还需要保证差异化的QoS，文献[5]提出混合链路保护(Hybrid Link Protection,HLP)方案，目标是探索路径多样性和预先计算备份路径，以便在发生链路故障时，可以立即激活备份路径以避开这些链路。HLP分2个阶段实施。第1阶段基于无环标准为每个目的地计算多个下一跳，保证诱导转发路径无环路，备用保护路径(Backup Path Protection,BPP)识别链路并计算它们对网络可用性的单独贡献度，确定关键链路，然后贪婪地选择最小数量的关键链路以满足网络可用性要求，并计算相应的多跳备份路径。第2阶段是指在HLP中，当数据包到达故障检测节点(Fault Detection Node,FDN)且由于故障导致其默认下一跳不再可用时，FDN首先检查是否为目的地计算了多个下一跳，并选择可行的下一跳进行转发。如无可行的下一跳，它使用特殊包头沿BPP计算的多跳保护路径传输路由数据包。同时,HLP发起控制面状态同步，在所有节点对网络状态达成共识后重新执行第1阶段。该方案可在效率及网络可用性之间取得较好的平衡，以较低的开销提供较高的网络可用性。

文献[6]针对数据中心网络提出一种基于路径关键度的拥塞避免重路由方法，根据业务流信息判断是否为大流，以链路负载和链路时延表征大流对链路的影响程度，称为链路关键度。将重路由路径分配问题建模为最小化最大链路关键度问题，将拥塞链路上的大流调度到关键度较低的路径上，缓解链路拥塞，进而保证网络性能。实验表明,当网络负载超过30%后，该算法表现出较好的性能，实现了减小大流拥塞、避免小流超时的目标。

1.2 基于启发式方法的路由算法

启发式算法常被应用于传统网络路由规划，在可接受的代价下给出组合优化问题的一个可行解，一般情况下该可行解与最优解的偏离程度无法估计，常用于网络的启发式算法有蚁群算法[7-10]、神经网络和遗传算法[11]等。蚁群算法是一种用来寻找优化路径的概率性算法。文献[12]提出了一种结合蚁群算法和链路加权算法的蚁群链路权值算法，平衡网络负载并选择最佳路径，在多个完整路径中，通过蚁群算法计算与筛选多个可行路径，并选择目标函数值较小的路径为最优路径，在发挥蚁群算法优势的基础上，通过链路权重算法避免蚁群算法陷入局部最优解，仿真实验结果表明,该算法在调整网络负载平衡方面优于等代价多路径路由算法，更适合于电力通信网络等复杂的应用场景。

文献[10]提出了一种基于最小图的蚁群优化算法和一种创新的加权路由方法，通过对具有不同阈值的流量模式和场景进行广泛的模拟，所提出的路由方法可以在满足用户QoS要求的同时提供有效的链路负载均衡，极大地减少了网络能耗。

除此之外，文献[13]还结合了遗传算法和果蝇优化算法对APTEEN路由协议进行了优化。在簇头选择中加入剩余能量、节点到基站的距离、节点到全网几何中心的距离及节点度等选择因素，利用遗传算法和果蝇优化算法对簇头进行选择。仿真结果表明，优化得到的算法提高了网络50%的生命周期、10%的覆盖率和鲁棒性，降低了整个网络系统的能耗，避免了能源热区现象。此外，如粒子群算法[14-15]等其他启发式算法也常被用于求解复杂网络中的路径规划问题，利用遗传算法可以提高收敛速度，但容易陷入局部最优，在应用时通常需要根据场景进行优化。

1.3 小结

传统动态路由算法结构简单、稳定性高，目前已广泛应用于各类商用网络中，然而在复杂网络中收敛速度较慢，无法适应动态变化的网络环境。在数据中心、无线自组网和抗震救灾网络等大流量、高动态网络中，传统路由算法已无法支撑各类业务的差异化QoS保障需求，研究基于网络状态与业务需求的智能化路由策略愈发重要。

2 基于监督学习的智能路由算法

2.1 监督学习方法原理概述

监督学习是机器学习方法中的一种，利用同时包含特征和标签信息的样本训练得到一个最优模型，再利用该模型将输入映射为相应的输出，对输出进行判断从而实现预测和分类等目的。

在深度学习方法研究初始阶段，基于误差反向传播(Back Propagation,BP)算法的深度神经网络(Deep Neural Network,DNN)由于隐藏层数较多，训练效率低下且容易产生局部最优问题，为提高训练效率，有学者研究了替代的激活函数以及小批量梯度下降算法等其他高效的优化算法，然而这些方法对大规模DNN的优化程度十分有限。为此，Hinton等[16]在2006年提出了深度置信网络(Deep Belief Network,DBN)，其结构如图1所示。DBN是一个基于受限玻尔兹曼机(Restricted Boltzmann Machines,RBM)预训练的概率生成模型，由多个RBM层组成，可以被用于多种优化任务。

图1 DBN结构Fig.1 Structure of DBN

在智能路由方案中，很多时候需要处理维度不定的序列化信息，如流量预测和拓扑感知等。此时DNN很难达到预期效果，循环神经网络(Recurrent Neural Network,RNN)可以有效地处理长度不定的序列化输入，如网络流量信息和拓扑信息等。RNN是一类以序列数据为输入，在序列的演进方向进行递归且所有节点(循环单元)按链式连接的RNN。相较于全连接神经网络，RNN添加了一个记忆单元，将上一时刻隐藏层的状态与当前时刻的输入一起传递至循环层。在传统RNN中，每一时刻的输出不仅由当前时刻的输入决定，还与上一时刻隐藏层的值有关。在前向的过程中，开始时刻的输入对后面输出的影响越来越小，最终会丧失“记忆”能力，递归中的系数连乘也带来了梯度爆炸的问题。

长短期记忆(Long Short-Term Memory， LSTM)是一种特殊的RNN，由Hochreiter和Schmidhuber于1997年提出，主要是为了解决上文提到的长序列训练过程中梯度消失和梯度爆炸的问题，能够在更长的序列中有更好的表现，但因参数较多，使得训练难度较大。

门控循环单元是LSTM网络的一种效果很好的变体，它与LSTM效果类似但网络结构更加简单。由于能够保持按照时序序列上的历史信息，LSTM网络在序列模型任务上有较好的表现，然而该模型只能输入线性序列，无法有效处理具有结构信息的数据，如网络拓扑数据等。文献[17]于2009年首次提出了图神经网络(Graph Neural Network,GNN)模型，GNN支持对图节点之间的依赖关系进行建模，使得与图分析相关的研究领域取得了突破。

GNN是一种基于深度学习的处理图域信息的方法，可以有效地处理非欧几里得数据。在GNN的基础上，科学界陆续研究出图卷积网络、图自动编码器、图递归神经网络和图强化学习等一系列学习模型，在社交网络、知识图谱、推荐系统，甚至生命科学等领域都发挥了重要作用。近年来,随着网络技术的发展，GNN在网络领域的研究也不断深入，在网络建模、路由规划和拥塞控制等相关研究中，GNN因其强大的图数据处理能力已被广泛应用。

2.2 基于监督学习的智能路由算法

在路由优化问题中，深度学习算法的作用主要是替换传统的基于数学模型的求解过程，也就是通过将网络状态和拓扑信息输入深度学习模型，使模型输出符合当前网络条件的最合适的路由决策。

2017年Mao等[18]面向骨干网场景提出了一种基于DBN模型的路由方案。该方案将路由器分为边缘路由器和内部路由器，边缘路由器连接到不同的网络，外部网络产生的数据包到达边缘路由器后，被送到目的节点(另一个边缘路由器)进行交付；内部路由器负责路由转发和网络状态信息收集。每个路由器单独训练一个DBN模型，模型参数被分发到所有的边缘路由器，边缘路由器可利用节点信息创建从自己到所有边缘路由器的路径。实验证明，提出的方案信令开销明显降低，可以有效地避免网络拥塞，更好地实现流量控制，提升系统吞吐量。但该方案对设备算力要求较高，不适合大规模部署。

传统的路由协议不会从历史网络特征和性能中学习来做出最佳路由决策。为此，2020年Du等[19]提出了基于卷积神经网络(Convolutional Neural Network,CNN)的深度学习赋能QoS感知自适应(Deep Learning Empowered QoS-aware Adaptive,DLQA)路由算法。该算法在网络特征矩阵中同时包含了网络流量特征和链路状态特征。系统的每个路由策略都由相应的CNN判断当前流量特征是否能够满足传输QoS要求。仿真结果表明，所提出的DLQA路由算法可以根据不断变化的网络特征自适应地调整路由策略，以满足端到端传输时延和丢包率低的传输QoS要求。

Rusek等[20]提出了一种基于GNN的算法——RouteNet，这是首次使用机器学习技术解决网络建模问题。该算法根据对源-目标节点对的平均时延及抖动进行网络性能预测，根据预测结果进行路由规划。RouteNet使用GNN学习网络图中实体之间的关系并解决循环依赖的问题，对收集到的网络状态信息进行抽象，利用其中有价值的信息进行网络性能预测，然后基于预测结果进行路由优化，该算法能有效地降低网络的时延和抖动。将该方法与最短路径路由策略进行比较，最终证明使用RouteNet可以取得更低的网络延迟。但是，RouteNet的扩展性较差，不支持各链路容量不同的网络拓扑，适用场景十分有限。

针对传统的路由算法,例如OSPF和蚁群算法等无法处理网络状态复杂性及组网非平稳性的问题，2020年Zhuang等[21]基于SDN提出了一种集中式深度学习模型进行路由计算，减少网络和模型训练开销。该模型采用了一种图感知神经学习算法(Graph-Aware Deep Learning，GADL)，算法结构如图2所示。

图2 GADL算法结构Fig.2 Algorithm structure of GADL

该算法首先提取网络图中的拓扑信息，然后将处理后的数据作为CNN的输入，经过计算输出合适的下一跳节点。为放松模型对大规模训练样本的需求，提高模型效率，GADL使用了一个特征处理流程：将网络状态测量值转换为适合DNN在路由场景中学习的代表性特征。最终实验表明,GADL比其他最新的基于路由策略的深度学习方法在精度和效率上都很突出，并且可以使用更少的时间去接近最优策略。

2.3 小结

上述分析表明，基于深度学习的智能路由算法能够利用网络状态信息和拓扑信息较为准确地计算出恰当的路由方案，同时在收敛速度提升和信令开销降低方面也展示出了相比于传统方案的优势。然而，DNN会使用大量参数，只能将其看作是黑盒，这导致了基于深度学习的智能算法难以调试。因此，使用基于深度学习的系统在实际使用中可能会有风险。

针对基于深度学习的智能网络算法难以解释的问题，2020年Meng等[22]首次提出了一种智能网络系统解析方法——Metis，该方法能够分析出对路由决策结果起决定性影响的链路，将基于深度学习的智能方案解释为人类可理解的控制策略，从而使网络操作人员能够方便地调试、部署和调整。Metis可以协助开发、运维人员对基于深度学习的网络进行操作设计、故障解决、部署和自适应调整等，但Metis并不能适用于所有基于深度学习的网络系统，例如，Joshi等[23]将深度Q网络(Deep Q-Network,DQN)与RNN相结合进行路径预测，Metis对RNN等包含记忆模块的神经网络无法准确地进行解析，未来将Metis与循环单元相结合或许能解决这个问题。

3 基于强化学习的智能路由算法

3.1 强化学习方法原理概述

强化学习(Reinforcement Learning,RL)方法通过与环境交互，不断学习以达成回报最大化或实现特定目标。在每个时间点t，智能体根据当前状态st采取行动at后得到奖励rt，RL的目标就是找到一个策略π(s)，使得累计奖励最大化。RL不需要预先给定训练数据，它通过接收环境对动作的反馈调整模型参数。

为了处理高维空间上的RL问题，研究者们设计出了多种深度RL模型，DQN便是其中一种。DQN引入一个DNN来替代Q表，通过简单的平方差计算损失并进行优化。DQN通常采用评估Q网络根据当前状态生成估计值Q，目标Q网络的输出对应下一个状态，每隔一定周期使用评估Q网络更新参数。深度RL有一个存储历史经验的记忆缓存。从记忆缓存中随机选择经验来训练神经网络，类似于通常的监督学习，可以简化调试和测试算法。

DQN等值函数估计算法只能用在有限的离散动作空间中，无法应用在较大离散空间或是连续的动作空间。DeepMind的Silver等[24]在2014年提出确定性策略梯度算法(Deterministic Policy Gradient,DPG)，通过函数π直接计算确定的值，获取每一步的行为：at=π(st|θπ)，这个函数π即最优行为策略。随后在2016年提出深度确定性策略梯度(Deep Deterministic Policy Gradient,DDPG)，将DNN用于DPG，其结构如图3所示，图中π表示确定性策略函数，Q表示神经网络生成的Q函数。

图3 DDPG算法框架Fig.3 DDPG algorithm framework

DDPG将DQN和DPG算法结合为演员-评价者框架，其中演员模块使用DPG算法，评价者模块使用DQN算法。有4个网络，分别是演员当前网络、演员目标网络、评价者当前网络和评价者目标网络。目标网络的模型结构和在线网络相同，使用在线网络一段时间之前的参数；演员网络对策略建模，即根据网络状态计算路由决策，并接受环境反馈；评价者网络负责对价值函数建模，评估演员网络的决策优劣，并调整演员网络的模型参数。

DDPG吸收了DQN算法的优点，在连续动作空间的效果优于DQN而且收敛速度更快，因此近几年被广泛用于智能路由优化问题中，通过与环境的交互做出网络配置决策，提升网络性能。

3.2 基于RL的智能路由算法

随着近几年智能算法的不断发展，研究者们尝试将RL算法用于路由决策及其他领域中，结合Q学习和DDPG等算法设计路由方案，针对不同场景提升网络性能。

为了提升域内路由性能，2019年Xu等[25]将基于RL的路由方案分为2类，并分别提出了改进建议。第1类是包级别智能路由，通过实验证明了该方案不适用高速网络场景。为此，Xu等提出有监督的Q网络路由方案，每次更新时Q网络允许执行机尝试一个动作，并且希望多次尝试后，执行机再次遇到该状态时可以做出最佳决策。该方案可将网络拥塞减少约57%。不过，由于动作空间大，基于显式路径的路由都存在可扩展性问题。第2类是基于隐式链路权重的路由(Link Weight-based Routing,LWR)，它有助于识别拥塞链路，并在后续路由决策中避免此类链路。采用具有代表性的DDPG作为底层RL算法进行实验，结果表明LWR方案效果并不理想，因为在链路权重不同时，计算出的路由决策却有可能相同，这导致函数可能会难以收敛。Xu等对此提出了基于离散链路权重的路由，该方案采用离散权重并使用每个神经网络独立训练一个链路权重以加快学习过程，底层RL为多智能体深度确定性策略梯度，输出具有最高概率的确定性链路权重。实验表明，该方案比最短路径路由减少了17%的最大队列长度，比LWR收敛到最佳性能的时间快了5倍。

Valadarsky等[26]通过实验对比了3种有监督的学习算法和2种RL算法后得出以下结论：使用有监督的学习方法进行路由优化，如果网络的流量状态规律性不强，这类方法通常会失效，而RL可以获取网络历史流量需求与路由配置之间的映射关系，可靠性更高。除此之外，算法的输出也很重要，输出完整的规划路径会导致参数量过大，学习过程耗时等问题，相反，逐跳进行路由规划更具稳定性，学习过程也更高效。基于以上分析，设计了一种基于RL的路由优化算法，学习历史流量矩阵与各链路权重之间的映射关系，能有效地降低网络的拥塞率。

为了克服最短路径算法的缺陷，保证数据包在所需时间内到达目的节点，2017年Desai等[27]提出了基于置信度预测的双Q路由方案。传统的基于置信度的Q路由只更新路径中所选节点的置信度值，而在提出的优化版本中，路径中未选择节点的置信度值也会进行更新，从而产生更多的动作探索。实验结果显示，无论是在高负载还是变化的网络条件中，该系统可以达到比Q路由更好的性能，有效降低包投递时间。该方案需要额外的内存来存储过去的经验，相比Q路由算法需要更高的硬件保障。

文献[28]提出利用RL与聚类机制解决认知无线电网络(Cognitive Radio Network,CRN)中的路由问题。CRN中主要用户活动程度不同，信道可用资源呈现出动态性，同时在许可信道上广播路由控制信息会导致高开销且会限制网络可扩展性。基于集群的路由策略可减小路由消息洪泛带来的开销，且RL无需考虑影响网络性能的全部因素，二者相结合可以很好地解决上述问题。实验结果表明，该算法具有更低的路由发现频率和更高的路由稳定性，提高了网络的可拓展性和稳定性。除此之外，文献[29-33]也对RL在CRN路由规划的应用进行了广泛研究，实验证明RL可减少路由中断次数并提高网络吞吐量和数据包交付率，但目前相关研究测试环境通常较为单一，大规模复杂网络下算法收敛也可能会带来较大影响。

2017年Stampa等[34]第一次尝试将DRL用于路由优化，设计了一种全自动的DRL执行机，根据当前网络的流量状态自适应地进行特定配置，达到最小化网络时延的目的。该算法使用2个DNN迭代，学习状态、动作、奖赏之间的关系。与传统的启发式算法和线性/凸优化技术相比，该算法有以下优点：① 一旦训练完成，DRL能够仅通过一个步骤提供近似最优的路由配置。② 不需要建模，自动通过经验学习，能理解非线性、复杂、多维度的系统。③ DRL执行机将系统假定为自动化黑盒，可以使用不同的奖赏函数实现不同的目标，不用再设计新的算法。随后，越来越多的研究尝试使用DRL来解决不同场景下的路由问题[35]。然而，将系统看作自动化黑盒也引入了难以调试和运维等一系列缺点。

2021年Liu等[36]提出了基于深度强化学习的在线路由(Deep Reinforcement Learning-based Online Routing,DRL-OR)，算法以自适应方法将延迟和丢包等性能指标标准化，并结合标准化的指标获得不同服务类型的效用函数。基于效用函数，将路由生成过程建模为多智能体马尔可夫决策过程，设计了一种新颖的DNN结构，该结构具有公共特征提取层以及针对不同服务类型和目标节点的专用输出层。方案采用近端策略优化(Proximal Policy Optimization,PPO)算法，以逐跳方式为每个流计算路由。提出的DNN结构可以轻松扩展以适应新的流类型和网络更新。此外，为了避免DRL随机探索导致的不安全路由(例如路由循环)，Liu等还提出使用离线预训练，将安全学习技术用于在线训练过程。实验结果表明，采用安全学习技术的DRL-OR可以满足时延、吞吐量和丢包率要求，并且表现出很好的适应性和可靠性。然而，当大型网络拓扑中的状态输入空间增加时，DRL-OR需要更多时间来收敛，并且学习到的策略不够理想。

文献[37]提出了一种基于DQN的新型路由策略，在基于SDN的数据中心网络中自主生成最佳路由。为满足网络中老鼠流和大象流的不同需求，分别为其训练DQN以智能地做出路由决策。该算法将网络状态视为图像，将不同的网络特征视为不同的像素通道。状态空间由流表利用率及端口速率组成，动作空间为某业务的路径选择结果。对于大象流，目标是最小化丢包率并最大化吞吐量；对于老鼠流，目标是最小化丢包率和延迟。该文献在模拟数据中心网络中成功验证了所提机制的有效性。仿真结果表明，所提出的路由方案不仅可以智能地提供优化的路由策略，还可以提高网络性能。

与上文类似，针对软件定义数据中心网络中不同类型的流性能需求各异的现状，2020年Liu等[38]提出基于深度强化学习的路由(Deep Reinforcement Learning-based Routing,DRL-R)算法，与传统路由算法相比有效降低流完成时间，提高吞吐量，达到更好的负载均衡和更高的鲁棒性。DRL-R使用DQN和DDPG进行路径规划，使用图像表示网络状态，包括资源分配状态图和资源需求状态图，如图4所示，图中一个像素点表示1单位的网络资源。

图4 网络状态Fig.4 Network states

该算法创新地将带宽与缓存进行资源重组，分别考虑老鼠流、大象流的完成时间，在数据中心网络中取得了良好效果，但仅展示了胖树拓扑结构下的有效性，适用范围有限。

除了单独使用RL方法，近年来有学者尝试将RL与其他智能算法相结合，使得算法另外具备神经网络提供的预测等能力，从不同角度提升网络性能。2021年Bouzidi等[39]提出基于路由优化的深度Q网络和流量预测(Deep Q-Network and Traffic Prediction Based Routing Optimization,DTPRO)算法，对SDN进行路由优化，达到负载均衡、最小化端到端时延和丢包率的效果。在知识平面部署DQN和LSTM，其中DQN负责计算链路权重，LSTM负责学习单位时间内的网络状态数据，预测网络端到端时延，根据时延信息判断是否会发生拥塞。如果有拥塞发生，则对拥塞路径中的最大流进行重路由。最后，将路由问题建模为线性规划，约束条件包括时延约束、链路容量约束、路径容量约束、流优先级约束和需求匹配约束等，使用启发式算法对这个NP-Hard问题进行求解，算法整体框架如图5所示。

图5 DTPRO算法结构Fig.5 Architecture of DTPRO

实验结果表明,LSTM与传统的预测方法相比，准确率有明显提高，将DQN与流量预测结合后，DTPRO算法能有效降低网络时延、丢包率和链路利用率。

2018年Yu等[40]将DDPG算法用于SDN路由优化，提出了DDPG路由优化算法(DDPG Routing Optimization Mechanism,DROM)，每一个演员模块包含2个神经网络:一个在线网络用于训练和学习;另一个目标网络用于屏蔽训练数据间的关联性。通过改变链路权重，执行机可以相应更改数据流的路径。训练目标是根据输入的状态s找到最优动作a最大化奖赏r。DROM根据网络状态s，计算出链路权重集合[W1,W2,…,Wn]，然后根据更新后的权重计算流路径，路径更新后，通过下一次的网络分析测量获取奖赏r和新的网络状态，网络性能不断迭代优化。DROM算法能自动优化性能参数，实现连续时间实时控制，有效减轻运维压力。该算法未来可以结合QoS感知的流量分类和网络测量，自适应生成QoS感知的可靠高效端到端传输策略，进一步提升路由决策的合理性，提升网络性能。

除上文所述，RL也被广泛用于机会物联网(Opportunistic IoT)[41]及Ad Hoc[42-43]等领域的路由规划问题中，通过策略迭代最大限度地提升消息传递的可能性，设计状态空间、动作空间以及奖励函数，从节点移动概率、功耗、位置和速度等因素综合考虑，提高业务送达率，降低控制开销，并已经取得了不错的结果。

3.3 小结

现有的基于DRL的智能路由方法已经取得了一定的成果，相比于传统的路由算法，DRL通常只需要一次运算就能得出近似最优的网络配置方案，并且通过实际网络数据进行学习，不断与环境交互，不需要对环境做任何简化，根据实际信息进行运算，能适应非线性的复杂系统。但是,DRL模型的收敛性与输出维度强相关，大多数算法为了规避这个问题，都通过间接的方式计算路由，例如通过深度强化学习算法计算链路权重，再通过其他传统算法做出路由决策，并没有做到真正的智能选路。近年来,智能路由的研究都致力于特定场景下的网络性能提升，在实际应用场景中，由于网络规模大、环境多变等因素，现有方法的鲁棒性和可靠性都得不到满足，这类算法用于日常网络管控还远远达不到要求。

4 结束语

目前，探寻高效、自主的智能路由算法是通信网络领域的热门研究方向之一，本文对近期学术界研究的各类路由算法进行了全面的调研。人工智能技术的不断兴起使大数据处理和自适应策略调整成为可能，路由策略研究从传统算法不断演进，逐步走向自主化、智能化。

从传统动态路由算法、基于监督学习的路由算法和基于RL的路由算法等3方面对当前学术界最新研究进行分析，其中，传统基于最优化方法及启发式方法的动态路由策略结构简单、技术成熟度高、稳定性好，已有较为广泛的应用，但简单的结构也导致其大数据处理能力与逻辑判断能力较为单一、僵化，灵活性远远不足以支撑现有网络。

随着机器学习算法的发展，路由决策方案也在不断地演进，基于监督学习的智能算法能在一定程度上改善上述问题，这类算法通过对大量标签数据的处理，有效提取当前网络态势及业务需求信息，可较为准确地计算出合理的路由方案，在QoS保障等方面体现出较大的优势。然而，基于监督学习的路由算法需要大量有标签的网络数据，应用场景十分受限，在网络变化或者路由策略改动时，往往需要重新训练合适的神经网络模型。

深度强化学习凭借其无需大量标注样本、实时与环境交互和自主灵活调整等优势，被广泛用于智能路由领域，同时深度强化学习自身也在不断演进，从深度Q学习到确定性策略梯度，其决策能力逐步提升，成为智能路由方向的研究重点。这类算法可适应非线性的复杂系统，但仍面临状态空间及动作空间维度大、奖励函数合理性无法证明等问题，仍需要进一步的研究。

当前，学术界对路由算法的研究主要集中于理论方案设计与仿真验证阶段，对实际网络部署中面临的问题考虑不足，稳定性和可靠性都难以达到实际应用的要求，并且特定数据集训练得到的模型很难移植。未来应结合实际网络环境特征，通过设计新型的路由决策方案，提高路由决策模型泛化性和灵活性，不断优化网络性能，保障网络的QoS，为不同类型的网络和不同用户提供更好的使用体验，以较低成本实现网络智能控制。