基于秩的Q-路由选择算法

王月娟,张苏宁,吴水明,朱 斐

(1.国网江苏省电力有限公司苏州供电分公司,江苏 苏州 215004;2.苏州大学计算机科学与技术学院,江苏 苏州 215006)

0 引 言

近年来，随着网络的规模逐步变大，传统的路由选择算法越来越难以处理日益复杂的网络；同时，网络线路的动态变化、网络负载的不确定性给路由选择算法带来了极大的挑战，因此如何设计有效的路由选择算法是研究人员关注的热点和难点。

传统的静态路由选择算法一般根据某种固定规则进行路由选择，对于网络的变化和波动不能及时作出相应的调整，只能依靠人工更新路由表才能适应新的网络环境，而动态路由选择算法能够根据网络当前的状态进行动态的路由选择。动态路由选择算法分为3种：集中式、分布式与混合式[1]。集中式路由选择算法通过收集全网的状态信息进行路由计算从而得到最优的路由选择策略。这类算法能够适应不同的网络环境并且做出最优的决策，但是需要定期从所有路由中获得数据，并且需要一个网络控制中心对数据进行收集处理，增加了网络的成本。分布式路由选择算法无需其他路由的信息，通过处理获得数据动态地调整策略以适应网路波动，但是复杂的算法会降低处理速度，增加网路负担[2]。

人们开始尝试使用机器学习的方法来进行动态路由选择。在机器学习领域中，强化学习是一类重要的学习算法。强化学习方法的Agent通过与环境的交互来获得奖赏从而改进自身的策略，通过不断地迭代得到最优策略[3]。时间差分学习是强化学习的核心算法之一，被广泛地应用到各类研究与实践中[4]。时间差分学习的主要特点是在缺少环境模型的条件下利用值函数的估计值对值函数进行更新[5]，这使得它能够被用于需要在线更新的任务当中，而不需要等到情节结束之后才可以更新。Q-学习算法[6]是时间差分算法中应用得最广泛的算法之一，它的特点是行动策略与目标策略分离[7]，可以从行动策略中学习到最优的目标策略。由于强化学习能通过在线学习的方式更新，求解最优策略，解决未知环境的最优控制问题，研究人员将分布式路由选择算法与强化学习相结合，从而解决传统动态路由选择算法成本高和复杂度高的问题。Boyan等人[8]提出Q-路由选择(Q-routing)算法，将Q-学习算法引入路由选择算法中，比传统的算法有着更好的性能。但Q-路由选择方法比较单一，难以适应各种应用。针对此，本文提出基于秩的Q-routing(Rank-based Q-routing, RQ-routing)算法，使用具有动态计算功能的秩函数，对状态进行赋予优先级值，求解出最优路由选择，提高传输效率；RQ-routing算法中的秩函数具有灵活性，可以根据实际场景设定不同的秩以满足场景需求。

1 动态路由算法建模

1.1 强化学习

强化学习利用Agent和环境的交互，通过映射动作和场景进行学习以获得最优策略。与其他的机器学习算法不同的是，强化学习方法不会告诉Agent在当前状态下应该采取的最优动作，而是让Agent与环境进行交互，通过不断地尝试来最大化总奖赏值进而获得最优策略。强化学习包含2个最重要的特征——试错探索和延迟奖赏。在强化学习中，由于未告知Agent应该采取的动作，所以Agent需要遍历所有可能的动作。但是为了得到最大的奖赏值，Agent又需要选取最优动作，所以强化学习要在探索和贪心中进行平衡，找到最优解[9]。而延迟奖赏则是为了使动作的选择具有长远性，可能有些动作在立即回报上表现得很好，但是从长远看并不是最优动作，有了延迟奖赏就可以将这些动作的奖赏值降低，从而找到最优动作。强化学习包括了很多经典的常用算法，如Q-学习方法等，也有很多相关的研究和应用[10-13]。

强化学习算法一般由4个基本元素组成：值函数(value function)、策略(policy)、奖赏函数(reward function)和模型(model)。强化学习是一种从交互中学习达到目标问题的简单框架，如图1所示，其中Agent是学习器和决策器，与之进行交互的所有东西是环境。这些交互不断地进行着，Agent选择动作，环境对这些动作做出响应，并产生新的场景给Agent[14]。一个完整的环境规范定义了一个任务，即强化学习问题的一个实例。

图1 强化学习中的交互

在进行强化学习方法的建模时，Agent和环境在每一离散时间步中进行交互，Agent感知到环境的状态St∈S，其中S是所有可能状态的集合，然后根据该状态做出动作At∈A(St)，其中A(St)是在状态St中所有可能做出动作的集合。到下一个时刻，Agent从环境中得到该动作的回报值Rt+1∈，并且到达一个新状态St+1。

Q-学习算法是时间差分算法中的一种控制算法，它使用状态-动作对来进行值函数估计，对于每个时间步t，通过得到的奖赏(Rt+1)、此时刻的状态(St)、动作(At)以及下一个状态(St+1)来计算误差进行迭代直到收敛。在Q-学习中，使用Q(St,At)值来评估状态St下选择动作At的优劣，在学习过程中，Q值的更新公式如下：

Qt+1(St,At)=Qt(St,At)+α(Rt+1+

γmaxAt+1Qt(St+1,At+1)-Qt(St,At))

(1)

其中，α∈(0,1)为学习速率，用于控制学习更新的速度；γ∈(0,1)用于表示未来奖赏的折扣，意味着相较于以后的回报更看重眼前的奖赏。

1.2 算法建模

在使用强化学习方法对路由选择问题进行建模时，需要定义状态、动作集、奖赏函数和值函数。

首先，定义状态。在路由选择算法中，状态为网络中的路由和目标路由，网络智能体则是所有的路由，目标是以最短的时间将所有的数据传输到目标路由[15]，其中定义当前的路由为x，目标路由为d，那么当前的状态为(d,x)。

然后，定义动作集。动作集为当前状态可传输数据的路由集Y，假设算法选择了下一个路由为y∈Y，那么当前的路由选择将数据包发送至y路由，获得奖赏并且到达下一状态(d,y)。

接着，定义奖赏函数。由于网络的目的是尽快地传输数据，那么就将数据传输使用的时间作为奖赏，该奖赏分为2部分，数据包在该路由队列中的等待时间w和数据传输时间t[16]。

最后，定义值函数。为了方便表示，考虑到数据都是传输到同一目标路由d。定义值函数为Qd(x,y)，其中d表示目标路由，x表示当前状态，y表示当前路由x选择的动作即传输数据的路由。通过以上定义，结合公式(1)，可以得到值函数的更新公式：

Qd(x,y)=Qd(x,y)+

α(w+t+γminzQd(y,z)-Qd(x,y))

(2)

Q-学习算法在计算误差时会在下一个状态选取最优动作计算误差，传输数据花费的时间越少动作越好，所以在式(2)中选取对应值函数最小的动作。

2 基于秩的Q-routing算法

Boyan所提出的Q-routing算法对比之前的路由选择算法有着性能上的优势，但是应用场景单一。在实际应用中，不同的网络架构有着不同的需求[17-20]，传统的Q-routing算法很难在不同的场景中作出调整以满足不同的需求。

为了适应不同场景，可以从算法结构与奖赏函数这2个角度进行改进。从算法结构改进的方法中，需要根据不同场景的实际特点重新设计算法，虽然有较强的针对性，能很好地解决该应用场景的问题，但是对不同场景都要重新设计相应算法，因此算法通用性较差，解决问题的范围也受到很大限制；在强化学习的框架下，通过重新定义奖赏函数改进算法，能使算法具有通用性，但需要对问题进行强化学习的建模分析。

根据前文所述的动态路由算法建模，确定了状态、动作集、奖赏函数和值函数以及值函数的更新方式。在模型中引入了秩的概念。秩是一种与状态一一对应的函数，表示当前状态在场景中的优先级，可以动态计算，具有更好的泛化能力。在此基础上，本文提出一种基于秩的Q-routing(Rank-based Q-routing Algorithm, RQ-routing)算法。通过设计秩函数改变奖赏信息，对于不同的场景，算法无需作出较大的改变，只需要替换相应的秩函数，即可适应不同的场景，大大减少设计成本。例如，使用路由的队列长度作为秩函数来进行学习，能够避免队列过长，减少网络拥堵，提高传输速度。算法1描述了基于秩的Q-routing算法执行的主要步骤。

算法1基于秩的Q-routing算法

输入：目标路由d，路由连通信息

输出：训练完毕的Q值

1:for 每个时间步 do

2:for 每个路由x do

3:使用ε-greedy选择动作a

4:执行动作获得传输延时t与数据等待时间w和下一个状态y

5:δ←t+w+γmaxa′Qd(y,a′)-Qd(x,a)

6:根据不同需求计算当前的秩R(x)

7:Qd(x,a)←Qd(x,a)+α(R(x)+δ)

8:end for

9:end for

10:return Q

与Q-routing 算法进行比较可以看出，本文提出的RQ-routing算法可以通过设置不同的秩灵活运用于不同场景中。在RQ-routing算法中，如果改变R(x)的更新公式，将所有的R(x)都置为0，则RQ-routing就退化成了Q-routing。RQ-routing算法可以根据不同的需求设置不同的秩，同时对于网络需求的波动，例如网络波谷时需要提高传输速度，网络波峰时需要减少传输时间，都可以通过调节秩来达到相应的效果，且Q-学习的快速收敛能够保证网络较快地调整到最优状态。

3 实验结果与分析

3.1 问题域

为了比较Q-routing算法与RQ-routing算法的性能，本文设计了一个简单的15路由的网络[16]，如图2所示，其中有3个发射源(12，13，14)和一个目标源(15)。每个路由在每个时间步可以处理一个数据包，每个连接都是双向的且传输延迟为一个时间步。

图2 15路由网络

不难看出每个发射源的最短路径，其中：

路由12的最短路径为12→1→4→15；

路由13的最短路径为13→2→4→15；

路由14的最短路径为14→3→4→15。

但是由于每个路由在每个时间步只能处理一个数据包，当所有发射源只通过最短路径传输数据时，路由4中就会发生拥塞。

一个解决办法是：每个数据源传输数据时都选择不同的路径，且这些路径没有共同的路由。例如，路由12通过12→1→5→6→15发送数据，路由13通过13→2→7→8→9→10→11→15发送数据，路由14通过14→3→4→15发送数据。最优的路由算法要根据每个发射源的情况决定，当网络负载较小时，就可以尽量选择最短路径。当网络负载较大时，为了防止发生拥塞就要考虑选择次优路径避免拥塞。

3.2 实验结果与分析

本文通过仿真实验模拟了上述的网络，实现了Q-routing算法和RQ-routing算法并且在上述仿真网络中进行了对比试验。对比实验分为2个部分，分别为低负载和随机高负载的情况下，通过实验数据与图表分析不同情况下Q-routing算法和RQ-routing算法的异同。

首先，对比低负载情况下RQ-routing算法和Q-routing算法的效果。表1给出了低负载情况下不同时间步传输的数据包的个数，图3给出了RQ-routing算法和Q-routing算法的效果对比曲线。

表1 低负载情况下不同时间步传输数据量

图3 低负载情况下的对比实验效果曲线

在低负载情况的实验中，低负载情况的模拟是所有发射源都隔一段时间传输一个数据包，网络负载较低，很少出现拥堵。RQ-routing算法的秩就是路由的队列长度。从图3中可以看出在低负载网络中，2种算法的差异不明显，说明加入秩之后在低负载网络下不会影响学习算法的效果，2种方法都能较快地学习到最优路径。另一方面，该实验选取的秩是队列长度，在低负载网络下发生拥堵的概率较低，队列长期为空，所以选择的秩不会有太大的影响，这说明选择不同的秩在不同的网络状态下对性能的影响也不同。

接着，对比高负载情况RQ-routing算法和Q-routing算法的效果。低负载网络下的比较试验比较理想化，在实际应用中网络的随机性很强，所以在进行高负载试验时，并不是简单地缩减传输数据的时间，而是通过随机传输的方式进行测试。每个发射源在每个时间步都有0.8的概率产生一个数据包，这就使得2个数据包之间的时间不固定，并且选择固定的线路网络极易发生拥塞，这就要考验算法的动态调整的性能。

表2给出了高负载情况下不同时间步传输的数据包的个数，图4给出了RQ-routing算法和Q-routing算法的效果对比曲线。

表2 高负载情况下不同时间步传输数据量

图4 高负载情况下的对比实验效果曲线

在高负载情况的实验中，仍然使用队列的长度作为秩。在高负载网络中，拥塞是不可避免的，路由要根据不同的情况调整策略从而应对高负载的随机网络。从图4中可以看出，在高负载随机网络中，RQ-routing相较于Q-routing，在大概120步的时候显现出差距，随着时间的增长有着明显的性能优势。随机性的网络使得固定策略不再适用，而是要根据实际情况动态调整，在实际应用中也是如此。RQ-routing通过设定秩，减少了网络波动对于算法的影响，能够在相应的场景动态地调整策略，使得算法可以根据不同的需求进行改变从而应用到不同的场景当中。

通过2组实验的对比，可以得出以下结论：1)RQ-routing在低负载场景中能够与Q-routing达到几乎相同的效果，不会因为加入秩而影响性能；2)对于高负载场景，RQ-routing算法的性能明显优于Q-routing算法，并且随着时间增长差距会拉大；3)RQ-routing算法能够通过设置不同的秩达到不同效果，从而满足多样化需求。

4 结束语

传统的路由算法不能根据网络的波动动态地调整路由选择策略，不能适用于当前日益复杂的网络环境。Q-routing算法虽然能够动态地调整策略，但应对的场景比较单一。本文提出了一种基于秩的Q-routing算法，能够通过调节秩来应对不同的场景，并且在其他场景下没有性能的损失。

本文的工作也有值得进一步深入研究的内容。例如，基于强化学习的路由算法仍然没有大规模的应用，但是其适用于解决动态路由以及网络波动这一类问题，有较强的实用性和广阔的应用前景。现有的算法只适用于小型的网络，对于大型的网络没有进行状态的泛化，不能高效地进行学习。同时对于秩的设定仍然需要人工进行，并没有进行参数的泛化，这是未来的工作之一。为了解决这些问题，需要将状态进行函数近似，通过函数近似的方法来解决大空间的问题。同时对于秩的设定可以参考一些方法(如PBT[21])来进行自动调整，获取最优参数。另外，还可以考虑结合深度学习，使用深度强化学习的方法，来解决更大规模的问题。