一种基于网络特征的强化学习下的SDN路由收敛方法

摘要

本发明公开一种基于网络特征的强化学习下的SDN路由收敛方法，该方法将强化学习应用于SDN路由收敛中，使用QLearning算法作为强化学习模型，根据输入的网络拓扑，定义一个方向因子θ来描述路径中每一次转移的方向。根据路径转移过程中θ值来引导强化学习agent探索。在早期的episode中允许agent在探索阶段选择对应θ值为负的动作，而随着episode的不断迭代减少agent探索对应θ值为负的动作的概率。以此来保证在agent从环境中充分获得经验的同时提高探索效率，并减少在训练阶段环路的产生。本发明利用强化学习与网络环境不断交互、调整策略的特点，相比于传统的路由收敛算法，能在路由收敛过程中找到最优路径。

权利要求

1.一种基于网络特征的强化学习下的SDN路由收敛方法，其特征在于，该方法包括以下步骤：步骤1：建立SDN网络区域拓扑图，细粒度划分网络区域；

步骤2：定义方向因子θ，并设定源节点，方向因子θ的取值为{‑1，0，1}，当拓扑图中一个节点到另一个节点的方向因子θ取值为‑1时，代表靠近源节点，当拓扑图中一个节点到另一个节点的方向因子θ取值为1时，代表远离源节点，当拓扑图中一个节点到另一个节点的方向因子θ取值为0时，代表两个节点与源节点的最短距离均相同，依据拓扑图中不同节点之间的θ值以及和源节点之间的关系，构建网络拓扑分层图，每层中的所有节点与源节点的最短距离均相同；

步骤3：使用Qlearning算法作为强化学习模型，将步骤2得到的网络拓扑分层图输入到强化学习模型中引导agent探索；当高度差取向0，表示各节点在同一层，这时同一层的节点与节点之间的转移更少的受分层的影响，表现为agent的随机探索状态；当不断提高分层之间的高度差，引导agent向下层探索，表现为agent的高效探索状态；

设定如下公式：

h(θ)＝f(θt)

其中，t代表episode迭代的次数，step为设定的阈值； 函数f(t)根据episode迭代进度对θ取绝对值，h(θ)通过对应动作的状态具体决定θ的具体取值；随着episode的不断迭代，在可选动作中靠近源节点的动作对应的θ值会变小，远离源节点的动作所对应的θ值会变大，定义公式D：区间D取值范围为0到所有当前可选动作对应的θ值之和，区间划分成n份，n为当前可选动作的数量，各子区间的长度为对应动作的θ值；

η＝random(D)

通过在区间D上等概率取值，得到随机数η；

通过以下公式计算：

函数g(D，η)为随机数η所在区间D对应的动作，即agent探索将要选择的动作a；

强化学习基于网络区域特征的策略公式为：

ε‑贪心策略基于探索因子ε(ε∈[0，1])来平衡探索和利用；生成一个随机数σ(σ∈[0，

1])，当σ≤ε，agent使用随机策略，通过随机的选取动作探索环境以获取经验；当σ＞ε，agent使用贪婪策略利用已获得的经验；

当agent发生状态转移，将当前状态s和所选动作a输入函数R，生成奖励来评价该状态转移，设定奖励函数：Rt(s，a)＝αB‑βt+γδ(s_‑d)‑δ

R为在节点i，选择链路到节点j所获得的奖励；α、β、γ、δ作为四个正值参数来权衡四部分奖励的权值； B为所选动作对应链路的剩余带宽，t为对应链路时延； δ(s_‑d)为激励函数，s_表示基于状态s在选择动作a后所转移的状态；

根据设定的奖励函数对Q值表进行训练，训练好的Q值表得到一条路径Routing，该路径即为链路故障后收敛的最优路径。

2.根据权利要求1所述的一种基于网络特征的强化学习下的SDN路由收敛方法，其特征在于，所述细粒度划分网络区域，具体为：依据SDN网络拓扑，构建网络连接矩阵，网络连接矩阵中包含网络的各结点间的邻接关系；将网络连接矩阵和网络拓扑中的节点数m输入到枢纽节点竞选算法中，记录节点的连接数，表示为：其中，node_link[i]为节点i，T[i][j]为i节点连接的链路，选出具有最高链路连接数的节点作为枢纽节点；枢纽节点以及其邻接节点作为一个划分后的网络区域。

3.根据权利要求1所述的一种基于网络特征的强化学习下的SDN路由收敛方法，其特征在于，所述QLeaming算法训练Q值表的过程具体如下：设置单次训练最大步数；

(1)初始化Q值表和奖励函数R；

(2)采取基于网络区域特征的策略，选择动作a；

(3)执行动作a，转移到状态s_，用奖励函数R计算奖励值，更新Q值表；

(4)判断s_是否为目的节点；若不是，使s＝s_，回到(2)；若s_是目的节点，则训练结束。

4.根据权利要求1所述的一种基于网络特征的强化学习下的SDN路由收敛方法，其特征在于，在规划备用路径时关注链路带宽性能和链路时延，因此设置α＝0.4，β＝0.3，γ＝

0.1，δ＝0.2。

说明书

一种基于网络特征的强化学习下的SDN路由收敛方法

技术领域

[0001] 本发明涉及网络通信技术和强化学习领域，具体涉及一种基于网络特征的强化学习下的SDN路由收敛方法。

背景技术

[0002] 强化学习过程可以概括为智能体从环境状态到行为动作形成映射关系使得累计的奖励值达到最大。在路由规划中，智能体从路由系统中接收当前状态信息和奖励信息，而智能体选择的动作可以认为是路由系统从智能体接收到的输入，当前路由系统中的动作与奖励信息会在之后较长的时间内对智能体的动作选择产生影响。智能体在整个路由规划系统中，必须学习到最优的动作来使得自身累计的奖励值达到最大，此时智能体选择的动作即流量的最优路径。在强化学习任务中，Q‑learning不依赖于环境模型，且在有限马尔科夫决策过程中，Q‑learning可以找到最优的策略，agent要做的就是不断在系统中尝试而学得一个策略。策略的好坏取决于执行这个策略后得到的累计奖励，我们的最佳策略就是在每一个状态下，选取Q值最大的动作。探索指的是智能体选择之前未执行过的动作，利用指的是智能体从以前习得的经验中取得当前的最优动作。在本发明中，探索即选择之前未选择过的链路，从而寻找更多的可能性；利用即选择目前已选择过的链路，从而对已知的规划线路进行完善。

[0003] 若使用强化学习实现最短路径规划，agent的探索趋势是寻找深度越来越小的节点。在网络中，除了链路长度，链路带宽、延时、跳数等都可以作为显性特征，各种特征通过权值加成也可以作为一个新的特征。通过网络拓扑的显性特征，可以引导agent从探索阶段的高随机行为转变成高效探索，以此使学习网络更快的达到收敛。为了避免网络收敛到次优解，在训练的初始阶段，我们允许agent的探索行为具有高度随机性。随着训练步数的递增，通过增大各链路显性特征的梯度差，agent可以实现高随机探索到高效探索的过渡，在提高收敛速度的同时保证能收敛最优解。

发明内容

[0004] 围绕当前传统路由收敛算法容易形成环路，可能无法找到最优路径等问题，本发明结合强化学习，提出了一种基于网络特征的强化学习下的SDN路由收敛方法。

[0005] 本发明解决技术问题所采用的技术方案如下：一种基于网络特征的强化学习下的SDN路由收敛方法，该方法包括以下步骤：

[0006] 步骤1：建立SDN网络区域拓扑图，细粒度划分网络区域；

[0007] 步骤2：定义方向因子θ，并设定源节点，方向因子θ的取值为{‑1，0，1}，当拓扑图中一个节点到另一个节点的方向因子θ取值为‑1时，代表靠近源节点，当拓扑图中一个节点到另一个节点的方向因子θ取值为1时，代表远离源节点，当拓扑图中一个节点到另一个节点的方向因子θ取值为0时，代表两个节点与源节点的最短距离均相同，依据拓扑图中不同节点之间的θ值以及和源节点之间的关系，构建网络拓扑分层图，每层中的所有节点与源节点的最短距离均相同；

[0008] 步骤3：使用Qlearning算法作为强化学习模型，将步骤2得到的网络拓扑分层图输入到强化学习模型中引导agent探索；当高度差取向0，表示各节点在同一层，这时同一层的节点与节点之间的转移更少的受分层的影响，表现为agent的随机探索状态。当不断提高分层之间的高度差，引导agent向下层探索，表现为agent的高效探索状态。

[0009] 设定如下公式：

[0010]

[0011] h(θ)＝f(θt)

[0012] 其中，t代表episode迭代的次数，step为设定的阈值。函数f(t)根据episode迭代进度对θ取绝对值，h(θ)通过对应动作的状态具体决定θ的具体取值。随着episode的不断迭代，在可选动作中靠近源节点的动作对应的θ值会变小，远离源节点的动作所对应的θ值会变大，定义公式D：

[0013]

[0014] 区间D取值范围为0到所有当前可选动作对应的θ值之和，区间划分成n份，n为当前可选动作的数量，各子区间的长度为对应动作的θ值。

[0015] η＝random(D)

[0016] 通过在区间D上等概率取值，得到随机数η。

[0017] 通过以下公式计算：

[0018]

[0019] 函数g(D,η)为随机数η所在区间D对应的动作，即agent探索将要选择的动作a。

[0020] 强化学习基于网络区域特征的策略公式为：

[0021]

[0022] ε‑贪心策略(theε‑greedy policy)基于探索因子ε(ε∈[0,1])来平衡探索和利用。生成一个随机数σ(σ∈[0,1])，当σ≤ε，agent使用随机策略，通过随机的选取动作探索环境以获取经验；当σ＞ε，agent使用贪婪策略利用已获得的经验。

[0023] 当agent发生状态转移，将当前状态s和所选动作a输入函数R，生成奖励来评价该状态转移，设定奖励函数：

[0024] Rt(s,a)＝αB‑βt+γδ(s_‑d)‑δ

[0025] R为在节点i，选择链路到节点j所获得的奖励。α、β、γ、δ作为四个正值参数来权衡四部分奖励的权值。B为所选动作对应链路的剩余带宽，t为对应链路时延。δ(s_‑d)为激励函数，s_表示基于状态s在选择动作a后所转移的状态。

[0026] 根据设定的奖励函数对Q值表进行训练，训练好的Q值表得到一条路径Routing，该路径即为链路故障后收敛的最优路径。

[0027] 进一步地，所述细粒度划分网络区域，具体为：依据SDN网络拓扑，构建网络连接矩阵，网络连接矩阵中包含网络的各结点间的邻接关系。将网络连接矩阵和网络拓扑中的节点数n输入到枢纽节点竞选算法中，记录节点的连接数，表示为：

[0028]

[0029] 其中，node_link[i]为节点i，T[i][j]为i节点连接的链路，选出具有最高链路连接数的节点作为枢纽节点。枢纽节点以及其邻接节点作为一个划分后的网络区域。

[0030] 进一步地，所述QLearning算法训练Q值表的过程具体如下：

[0031] 设置单次训练最大步数。

[0032] (1)初始化Q值表和奖励函数R；

[0033] (2)采取基于网络区域特征的策略，选择动作a；

[0034] (3)执行动作a，转移到状态s_，用奖励函数R计算奖励值，更新Q值表；

[0035] (4)判断s_是否为目的节点。若不是，使s＝s_，回到(2)。若s_是目的节点，则训练结束。

[0036] 进一步地，在规划备用路径时关注链路带宽性能和链路时延，因此设置α＝0.4，β＝0.3，γ＝0.1，δ＝0.2。

[0037] 本发明的有益效果：本发明定义一个方向因子θ来描述路径中每一次转移的方向。根据路径转移过程中θ值来引导强化学习agent探索。以此来保证在agent从环境中充分获得经验的同时提高探索效率，并减少在训练阶段环路的产生。利用强化学习与网络环境不断交互、调整策略的特点，相比于传统的路由收敛算法，能在路由收敛过程中找到最优路径。

附图说明

[0038] 图1为SDN网络拓扑图；

[0039] 图2为网络拓扑分层结构图。

具体实施方式

[0040] 以下结合附图对本发明具体实施方式作进一步详细说明。

[0041] 针对现有的SDN控制均采用Dijkstra算法作为最短路由收敛算法，本发明尝试将强化学习应用到SDN路由收敛中。利用SDN转发控制分离的特点，直接将网络拓扑环境用于Q值表的训练。考虑到随着不同流的转发操作，拓扑中的各链路剩余带宽是随时间动态变化的，该发明引入强化学习技术，利用强化学习自我探索环境的优势来应对网络环境的动态性，从而在保证路由收敛速度情况下找到最优路由收敛路径。

[0042] 本发明提供了一种基于网络特征的强化学习下的SDN路由收敛方法，该方法包括以下步骤：

[0043] 步骤1：建立SDN网络区域拓扑图，细粒度划分网络区域；具体为：依据SDN网络拓扑，构建网络连接矩阵，网络连接矩阵中包含网络的各结点间的邻接关系。将网络连接矩阵和网络拓扑中的节点数n输入到枢纽节点竞选算法中，记录节点的连接数，表示为：

[0044]

[0045] 其中，node_link[i]为节点i，T[i][j]为i节点连接的链路，选出具有最高链路连接数的节点作为枢纽节点。枢纽节点以及其邻接节点作为一个划分后的网络区域，如图1所示。

[0046] 步骤2：定义方向因子θ，并设定源节点，方向因子θ的取值为{‑1，0，1}，当拓扑图中一个节点到另一个节点的方向因子θ取值为‑1时，代表靠近源节点，当拓扑图中一个节点到另一个节点的方向因子θ取值为1时，代表远离源节点，当拓扑图中一个节点到另一个节点的方向因子θ取值为0时，代表两个节点与源节点的最短距离均相同，依据拓扑图中不同节点之间的θ值以及和源节点之间的关系，构建网络拓扑分层图，如图2所示，每层中的所有节点与源节点的最短距离均相同；

[0047] 步骤3：使用Qlearning算法作为强化学习模型，将步骤2得到的网络拓扑分层图输入到强化学习模型中引导agent探索；当高度差取向0，表示各节点几乎在同一层，这时同一层的节点与节点之间的转移更少的受分层的影响，表现为agent的随机探索状态。当不断提高分层之间的高度差，引导agent向下层探索，表现为agent的高效探索状态。

[0048] 设定如下公式：

[0049]

[0050] h(θ)＝f(θt)

[0051] 其中，t代表episode迭代的次数，step为设定的阈值。函数f(t)根据episode迭代进度对θ取绝对值，h(θ)通过对应动作的状态具体决定θ的具体取值。随着episode的不断迭代，在可选动作中靠近源节点的动作对应的θ值会变小，远离源节点的动作所对应的θ值会变大，定义公式D：

[0052]

[0053] 区间D取值范围为0到所有当前可选动作对应的θ值之和，区间划分成n份，n为当前可选动作的数量，各子区间的长度为对应动作的θ值。

[0054] η＝random(D)

[0055] 通过在区间D上等概率取值，得到随机数η。

[0056] 通过以下公式计算：

[0057]

[0058] 函数g(D,η)为随机数η所在区间D对应的动作，即agent探索将要选择的动作a。

[0059] 强化学习基于网络区域特征的策略公式为：

[0060]

[0061] ε‑贪心策略(theε‑greedy policy)基于探索因子ε(ε∈[0,1])来平衡探索和利用。生成一个随机数σ(σ∈[0,1])，当σ≤ε，agent使用随机策略，通过随机的选取动作探索环境以获取经验；当σ＞ε，agent使用贪婪策略利用已获得的经验。

[0062] 当agent发生状态转移，将当前状态s和所选动作a输入函数R，生成奖励来评价该状态转移，设定奖励函数：

[0063] Rt(s,a)＝αB‑βt+γδ(s_‑d)‑δ

[0064] R为在节点i，选择链路到节点j所获得的奖励。α、β、γ、δ作为四个正值参数来权衡四部分奖励的权值。B为所选动作对应链路的剩余带宽，t为对应链路时延。δ(s_‑d)为激励函数，s_表示基于状态s在选择动作a后所转移的状态。

[0065] 根据设定的奖励函数对Q值表进行训练，具体如下：

[0066] 设置单次训练最大步数。

[0067] (1)初始化Q值表和奖励函数R；

[0068] (2)采取基于网络区域特征的策略，选择动作a；

[0069] (3)执行动作a，转移到状态s_，用奖励函数R计算奖励值，更新Q值表；

[0070] (4)判断s_是否为目的节点。若不是，使s＝s_，回到(2)。若s_是目的节点，则训练结束。

[0071] 训练好的Q值表得到一条路径Routing，该路径即为链路故障后收敛的最优路径。

[0072] 本发明一个具体应用实例如下：

[0073] 步骤1：构建SDN网络区域拓扑图，使用Mininet搭建如图1的网络拓扑图，其中包括16台OpenFlow交换机和5台主机。步骤2：使用QLearning算法作为强化学习模型，本发明提出的路由收敛方法使用马尔可夫决策过程来进行建模，因此，本发明提出的模型MDP四元组定义如下：

[0074] (1)状态集合：在网络拓扑中，每一个交换机就表示着一个状态，因此，根据网络拓扑，本发明定义网络状态集描述如下：

[0075] S＝[s1,s2,s3,…s16]

[0076] 其中，s1～s16表示该网络中的16台OpenFlow交换机。数据包的源节点信息表示该数据包的初始状态，目的节点信息表示该数据包的终止状态。当某一数据包到达目的节点时，即为该数据包到达终止状态。一旦当前数据包到达终止状态，则表示一轮训练的结束，数据包将重新回到初始状态，进行下一轮的训练。

[0077] (2)动作空间：在SDN网络中，数据包的传输路径由网络状态来决定，即数据包只能在相连的网络节点进行传输。根据网络拓扑图，本发明定义网络连接状态如以下公式所示：

[0078]

[0079] 由于数据包只能在相连的网络节点进行传输，因此，本发明根据网络状态集与网络连接状态可定义每个状态s[i]∈S的动作集如下：

[0080] A(si)＝{sj|T[si][sj]＝1}

[0081] 表示当前状态在si时，该状态可选的动作集在网络拓扑上的表现为与si直接相连的节点sj，即当前状态si的下一跳状态只会选择与该状态相连的状态sj。例如：状态s1的动作集为：A(s1)＝{s2,s4}。

[0082] (3)状态迁移：在每一轮训练中，当数据包在状态si时在动作集合中选择某一动作后，若该动作不是该轮已经选择过的状态，则数据包就向下一个状态移动。

[0083] (4)奖励函数：

[0084] Rt(s,a)＝αB‑βt+γδ(s_‑d)‑δ

[0085] 本发明在规划备用路径时关注链路带宽性能和链路时延，因此设置α＝0.4，β＝0.3，γ＝0.1，δ＝0.2。

[0086] 在本发明系统模型中，数据包每经过一个交换机，将会得到一个为负的奖励，表示数据包转发的代价，转发时经过的交换机越多，则累计的负奖励越多，代价越高；为了增大链路带宽利用率，鼓励数据包选择链路带宽利用率大的链路，则每经过一个交换机，会得到大小等于该链路利用率大小的奖励；为了迫使数据包尽快到达目的节点，当数据包到达目的节点时会得到一个额外大小为1的奖励，用公式表示为：

[0087]

[0088] 式中si表示当前状态，即当前数据包在编号为i的交换机上，aj表示选择编号为j的交换机。

[0089] 在本发明中，采用网络区域特征策略进行强化学习模型训练。

[0090] 在确定了MDP四元组后，当某条链路故障后，从源节点到目的节点寻找一条新路径，使用QLearning算法训练Q值表：

[0091] 设置单次训练最大步数。

[0092] (1)初始化Q值表和奖励函数R；

[0093] (2)采取基于网络区域特征的策略，选择动作a；

[0094] (3)执行动作a，转移到状态s_，用奖励函数R计算奖励值，更新Q值表；

[0095] (4)判断s’是否为目的节点。若不是，使s＝s_，回到(2)。

[0096] 基于强化学习的路由收敛规划过程中，学习率α设置为0.8，折扣率γ设置为0.6，动作策略ε‑贪心策略ε的取值为ε＝0.3。

[0097] 根据训练好的Q值表得到一条路径Routing，该路径即为链路故障后收敛的最优路径。

[0098] 上述实施例用来解释说明本发明，而不是对本发明进行限制，在本发明的精神和权利要求的保护范围内，对本发明作出的任何修改和改变，都落入本发明的保护范围。