面向动态拓扑网络的深度强化学习路由技术 *

伍元胜

(中国西南电子技术研究所，成都 610036)

0 引 言

无线自组网(例如车联网、无人机网络等)随着网络节点的移动，网络拓扑持续动态变化。传统的动态路由技术通常基于固定的路由策略，难以适应网络的动态变化。例如，目的节点序列距离矢量(Destination Sequenced Distance Vector,DSDV)路由协议[1]以路由跳数为链路权值，计算最短路径，无法适应拓扑变化引起的瓶颈链路变化，从而导致网络拥塞。近年来，深度强化学习在决策与智能化控制问题上取得了巨大的进步。深度强化学习可以适应环境的变化，已被用于求解网络的路由问题[2-12]。现有的深度强化学习路由大多使用传统的神经网络(如多层感知机[4-11]、卷积神经网络[3,12]、长短期记忆神经网络[5])，并不适合学习图结构信息[2]，无法提取网络拓扑图的特征，这导致算法需要针对不同的网络拓扑进行修改和重新训练，无法适应拓扑的动态变化。

在图像识别、自然语言处理领域，深度学习取得了巨大的成功，这得益于深度学习具有自动提取特征的能力。现代的深度学习方法通常遵循“端到端”的设计哲学，强调最小化先验表示与计算假设，并避免显式的结构与手工特征[13]。然而，在网络路由领域，传统的端到端深度学习难以提取网络拓扑特征。文献[8]研究表明,深度学习结合传统的特征工程具有更好的路由性能。另一种思路是使用图神经网络自动提取网络拓扑的特征，实现对不同网络拓扑的泛化[2]。

文献[2]基于K条候选路径路由，使用消息传递神经网络(Message Passing Neural Network,MPNN)近似DQN(Deep Q-Network)强化学习算法中的Q值函数，DQN算法训练完成后，从K条候选路径中选择Q值最大的候选路径作为业务路径。然而，K条候选路径路由需要事先为每对节点计算K条候选路径，拓扑变化将导致事先计算的K条候路径失效，因此并不适用于动态拓扑网络；另外，多约束的K条候选路由问题通常是NP难的，即使采用启发式算法时间复杂度也非常大，候选路径的数量(即K值)难以做到很大，这将严重限制路由的解空间。

针对现有的深度强化学习路由无法用于动态拓扑网络的不足，本文提出面向动态拓扑的深度强化学习路由算法，主要贡献如下：

(1)在PPO(Proximal Policy Optimization)[14]强化学习算法的基础上，使用图网络[13]近似策略函数和值函数，显式地将网络拓扑作为深度强化学习的状态，实现算法对不同拓扑的泛化；

(2)将链路的权值作为策略函数的输出，使用传统的约束最短路由算法实时计算满足约束的最小权值路径，克服了深度学习难以学习约束路径的难题，并避免了K条候选路径路由无法适用于动态拓扑的问题，实现了路径计算对拓扑的适应；

(3)通过仿真实验验证了本文所提方法可用于动态拓扑网络环境，路由智能体可通过强化学习与网络环境交互的经验中自动学习路由策略。仿真结果表明本文所提的方法在网络吞吐量方面优于传统的路由跳数最少的最短路算法。

1 背景介绍

1.1 图网络

图网络[13]是DeepMind在总结大量图神经网络的基础上进一步推广而得到的一种通用图模型。图网络处理的图可表示为G=(u,V,E)，其中，u为图的全局属性；V={vi}i=1:Nv为节点集合，vi是节点属性，Nv是节点的数量；E={(ek,rk,sk)}k=1:Ne为边集合，ek是边属性，rk是边的宿节点索引，sk是边的源节点索引，Ne是边的数量。

图网络的基本构建单元是图网络块，图网络块以图作为输入和输出，实现对输入图的节点、边和全局属性的变换。图网络块包含3个更新函数和3个聚合函数，如式(1)所示,其中，3个更新函数φe、φv、φu分别实现对边属性、节点属性和全局属性的更新，3个聚合函数ρe→v、ρe→u、ρv→u分别实现对节点的所有邻边属性的聚合、图中所有边属性的聚合和图中所有节点属性的聚合。聚合函数需要满足排列不变性，即聚合的边与节点的顺序不影响聚合结果。常用的聚合函数包括逐元素的求和、求平均、求最大值函数。

(1)

其中:

图网络块的计算过程为：首先,使用边属性更新函数φe对图中的每条边的属性进行更新；然后，使用邻边属性聚合函数ρe→v对节点的邻边属性进行聚合，再使用节点更新函数φv对图中的每个节点进行更新；最后，使用节点属性聚合函数ρe→u和边属性聚合函数ρv→u对图中的所有节点属性和图中所有边属性分别进行聚合后，使用全局属性更新函数φu更新全局属性。

图网络由1个或多个图网络块组合而成，每个图网络块相当于传统神经网络中的层，多个图网络块可以序列方式组合(对应传统的多层感知机)，也可以递归的方式组合(对应传统的递归神经网络)。图网络具有很高的灵活性，如式(1)所示，图网络块中的更新函数可以是包含传统的神经网络在内的任意函数，更新函数的参数都是可选的，聚合函数也可以是任何具有排列不变性的函数。图网络中的多个图网络块的配置可以是共享的也可以是各不相同的。图网络的高灵活性使图网络具有很强的表示能力，可以表示很多类型的图神经网络，如MPNN、关系网络、深度集合、信念传播嵌入等。

1.2 深度强化学习

强化学习是一个迭代学习的过程，在每轮迭代中，智能体在回报函数指导下探索状态与动态空间。状态空间用状态集合S表示，动作空间用动作集合A表示，则智能体与环境的交互过程为：给定环境的某个状态s∈S，智能体将执行某个动作a∈A，环境的状态将从s迁移到新状态s′∈S，同时智能体从环境获得回报r。强化学习的目标是学习最大化长期累积回报的最优策略。强化学习算法大体上可分为3类，即值函数方法、策略搜索方法和混合类型的AC(Actor-Critic)算法。值函数方法主要用于求解离散动作空间的强化学习问题，对于连续的动作空间，通常采用策略搜索或AC算法。AC算法是值函数方法与策略搜索方法的结合，其中actor与critic分别对应策略函数与值函数，策略函数从值函数获取反馈进行学习。

深度学习可自动地从高维数据中提取低维的特征，可用于解决“维数灾难”问题，与强化学习结合，即深度强化学习，可解决传统强化学习难以解决的具有高维的状态和动作空间的决策问题。深度强化学习面临的关键问题是深度神经网络引入后算法的不稳定性问题。TRPO(Trust Region Policy Optimization)算法[15]使用信赖域(trust region)方法，阻止与先前的策略偏离太远的策略更新，使策略的性能单调性的改进，防止灾难性的坏的策略更新。PPO算法[14]属于上述的AC算法，是对TRPO算法的改进，使用截断(clipping)的替代目标函数实现了对策略更新的限制，达到与TRPO使用复杂的共轭梯度算法保证策略更新约束类似的效果，但比TRPO算法要简单很多，且通用性更好。

2 深度强化学习路由算法

2.1 深度强化学习路由模型

本文考虑如下动态路由场景：业务逐条到达网络，路由算法需要为每条业务计算路径，如果算路成功，则接受业务并为业务分配带宽资源；如果算路失败则拒绝业务，重复以上业务路由过程，直到连续m个业务被拒绝为止。上述路由问题中，网络的拓扑、链路可用带宽和参数m是给定的、业务的源节点、宿节点、带宽以及路由约束也是给定的，路由算法需要计算合适的路径，让业务路由过程停止时网络的总吞吐量(即已成功路由业务的总带宽)最大。在动态拓扑网络中，网络的拓扑可能因节点移动、节点或链路故障而改变，路由算法需要具有适应拓扑变化的能力，即拓扑变化后也能正常运行。

针对上述动态路由问题，本文提出图网络+PPO算法的面向动态拓扑网络的深度强化学习路由算法。首先，在强化学习路由模型中，将网络拓扑作为环境状态的一部分，让路由智能体进行路由决策时可以显式地考虑网络拓扑的影响。其次，在动作空间设计时，将网络中链路的权值作为路由智能体的动作，然后使用传统的约束最短路算法计算最小成本路径。这样设计具有如下两大优势：

(1)可以处理复杂的路由约束。现有的深度学习技术很难直接输出满足复杂约束的路径，以链路权值作为动作，可有机地将深度学习技术与传统的带约束的最短路由算法结合起来，既可很好地处理路由约束，又不损害深度强化学习对路由的控制，因为一旦链路权值确定后，带约束的最小成本路径也可唯一确定。

(2)可解决K候选路径路由无法用于动态拓扑场景路由的问题。以链路权值为动作，然后实时计算最小权值路径，可避免拓扑变化后K候选路径失效的问题，而且还解决了多约束的K条路径计算难题(NP难问题)，以及K候选路径限制路由解空间损失路由优度的问题。

将链路权值作为动作，会导致连续型的动作空间，将无法使用DQN等值函数强化学习算法，因此本文选择使用PPO算法。PPO算法是目前最先进的连续型深度强化学习算法之一，PPO算法的全面介绍可参阅文献[14]。最后，图网络被用于近似PPO算法框架中的策略函数与值函数，以解决传统的深度神经网络学习路由策略无法适应拓扑变化的问题。

本文将上述动态路由问题建模为如下深度强化学习路由问题。路由智能体通过与网络环境交互学习可最大化网络吞吐量的最优路由策略。环境状态定义为网络的当前拓扑、链路的可用带宽、当前业务的源、宿节点与带宽，智能体的动作定义为当前拓扑中每条链路的权值。网络环境根据路由智能体的动作(即链路权值)使用传统的带约束的最短路算法计算最小成本路径，如果算路成功则下发业务，并向路由智能体反馈回报，回报为业务的带宽；如果算路失败，则回报为0。网络环境从空网开始，当下一个业务到达后，网络环境切换到下一个状态，重复上述过程直到连续m个业务算路失败，则当前幕(episode)结束，累积回报(又称幕回报)即为网络的吞吐量。

2.2 策略函数与值函数的图网络表示

PPO算法属于AC算法，AC算法通过策略函数(即actor)学习环境状态到智能体动作的映射，通过值函数(即critic)评估智能体的当前动作。本文使用图网络参数化PPO算法中的策略函数和值函数，图网络中的参数通过PPO算法进行学习。图网络结构如图1所示，先用输入图网络块GNinp对输入图Ginp进行处理得到图G0，然后使用核心图网络块GNcore对G0重复处理M次得到图GM(M为超参)，最后使用输出图网络块GNout对图GM处理得到输出图Gout。

图1 图网络结构示意图

输入图网络块GNinp的配置如图2所示，e、v和u分别表示输入图Ginp中的边、节点和全局属性，φe、φv和φu分别为边属性、节点属性和全局属性更新函数，更新后的边、节点和全局属性分别表示为e′、v′和u′。输入图网络块中的3个更新函数分别为3个无激活函数的单层神经网络，实现对输入图Ginp的所有边、节点和全局属性的变换，使变换后的属性具有相同的维数d(d为超参)，以便于后续核心图网络块的处理。

图2 输入图网络块Ginp配置

图3 核心图网络块Gcore配置

(2)

(3)

u′=φu(u,ν′,ε′)=MLPu(u,ν′,ε′)，

(4)

(5)

(6)

(7)

输出图网络块GNout的配置如图4所示，只对图GM的边属性和全局属性进行变换，以适配PPO算法框架。边更新函数φe被参数化为1个无激活函数的单层神经网络，输入层有d个神经元，输出层有2个神经元，分别表示边对应的链路的权值均值和对数标准差。全局更新函数φu被参数化为1个无激活函数的单层神经网络，输入层有d个神经元，输出层只有1个神经元，表示值函数的值。

图4 输出图网络块配置

2.3 环境状态的图表示

图网络的输入是图Ginp，因此，需要将环境的状态表示为图。环境的状态包括网络拓扑、网络可用带宽和当前业务源节点、宿节点和带宽。网络拓扑本身可以直接用图表示，其他信息则需要以图的节点属性、边属性和全局属性的形式表示。如图5所示，边属性为1维向量，图5中的8条链路，每链路的可用带宽为5 Mb/s，表示为边属性值都是5。每个节点属性为2维向量，第1个元素为入网带宽，第2个元素表示出网带宽，则业务可表示为节点属性，即业务的源节点1的入网带宽为2，业务宿节点6的出网带宽为2，其他的节点属性都为0。全局属性为1维向量表示网络的总可用带宽，网络共有8条链路，每条链路带宽为5 Mb/s，共40 Mb/s，故全局属性值为40。

图5 环境状态的图表示

3 仿真结果及分析

3.1 仿真场景设置

本文所提的PPO+图网络深度强化学习路由智能体是在Stable Baselines[16]中PPO算法源代码的基础上，继承ActorCriticPolicy类并使用图网络库[13]的相关函数实现的；网络环境则是对OpenAI Gym框架[17]进行扩展以支持可变的拓扑图作为状态空间和动作空间。

路由智能体在随机生成的包含15个节点30条边的网络拓扑上训练完成后，为了验证路由智能体对动态拓扑的适应性，测试使用了随机生成的3个完全不同的拓扑，分别是15个节点30条边的小型网络case1_15n30m、30个节点60条边的中型网络case2_30n60m和50个节点100条边的大型网络case3_50n100m。训练网络和测试网络中，链路的总带宽都为20 Mb/s。在路由智能体的网络环境中，业务逐个到达网络，业务的源宿节点对由重力模型[17]生成，业务的带宽都为1 Mb/s。

路由智能体的超参设置如表1所示。PPO算法训练过程如下：路由智能体与4个网络环境同时交互，路由智能体在每个网络环境执行128步，共得到512个样本，重复使用这些样本进行4次训练，每次训练都将所有样本随机打乱，然后分成4个每批128个样本的迷你批，使用随机梯度下降法优化损失函数。重复以上采样与训练过程，当达到70万步时退出。

表1 图网络的超参设置

仿真测试中使用两个对比路由策略，即RND (Random)和SPR(Shortest Path Routing)。RND在链路权值取值范围内，按均分分布随机设置链路权值，可实现网络的负载均衡。SPR即最短路算法，将每条链路的权值都设置为1，可以最省地使用网络带宽资源。

本节所有的仿真测试都是在英特尔酷睿i7-9750H(12线程，2.6 GHz)、32 GB内存、英伟达Quadro P600显卡、Windows 10家庭版的移动工作站上进行。

3.2 测试结果

图6为路由智能体训练时幕回报随时间步的变化曲线，图7是损失函数随时间步的变化曲线，从图中可看出，训练过程总共运行了70万步，当训练进行到30万步(即23 min)时，路由智能体就收敛了。

图6 路由智能体训练期间的幕回报

图7 路由智能体训练期间的损失函数值

PPO算法的损失函数[14]计算公式如式(8)所示:

(8)

当路由智能体训练完成后，在3个网络拓扑上与对比算法进行了路由性能测试。每种算法测试100次然后对测试结果取平均，结果如表2所示，其中，路由智能体的测试结果在表2中用PPO算法标记。

表2 100次测试的平均路由性能对比

测试结果表明，PPO算法具有最大的网络吞量，与RND算法相比，网络吞吐量提升了15.76%～19.36%。由于RND算法随机设置链路权值，相当于不考虑路由成本极端地做负载均衡，很多路径都不是最短路，因此具有最长的平均路径长度、最大的平均链路利用率，网络吞吐量也是最小的。SPR算法只考虑路由成本最小，完全不考虑负载均衡，因此，平均路径长度和平均链路利用率都比RND算法的小，吞吐量与RND算法相比有很大提升，但吞吐量并不是最大的。PPO算法同时考虑路由成本与负载均衡，可避免SPR算法因所有业务使用最短路造成前面的业务耗尽了某些关键链路带宽，导致后面的业务只能使用很长的路径的问题，因此，PPO算法的平均路径长度比SPR算法的更短，网络吞吐量更大。此外，在以上3个不同规模的测试网例中，PPO算法表现出一致的结果，即在平均吞吐量上都优于对比算法RND和SPR,在平均链路利用率上介于RND与SPR之间，在平均路径长度上都短于RND和SPR。以上结果表明，PPO算法具有对不同拓扑的泛化性，可适用于动态拓扑网络环境。

4 结束语

针对现有的深度强化学习路由算法无法适应网络拓扑变化的问题，本文提出了一种面向动态拓扑网络的深度强化学习路由技术。首先，通过将网络拓扑作为环境状态的一部分，让路由智能体显式考虑网络拓扑对路由策略的影响，有利于路由智能体实现对不同网络拓扑的泛化；其次，通过将动作表示为链路的权值，然后结合传统最小成本路由算法算路，有效解决了深度学习难以直接学习满足复杂约束的路径问题，同时也避免了K候选路径路由无法用于动态拓扑的问题；最后，通过结合最先进的连续型深度强化学习PPO算法与图网络技术，解决了传统的深度神经网络难以提取拓扑特征，模型无法在不同拓扑泛化的问题。本文通过仿真实现验证了所提技术的有效性，结果表明本文所提方法可获得比最短路由算法更大的网络吞吐量，且具有对不同网络拓扑的泛化性，可适用于动态拓扑网络环境。

与其他机器学习模型一样，本文的路由智能体也要求训练环境与测试环境具有相近或一致的业务模型，后续工作将研究能在不同业务模型间迁移的智能路由技术。