SDWN中基于多智能体深度强化学习的智能组播路由方法

sdwn中基于多智能体深度强化学习的智能组播路由方法
技术领域
1.本发明涉及软件定义网络(software defined network，sdn)技术领域，具体涉及一种sdwn中基于多智能体深度强化学习的智能组播路由方法。


背景技术：

2.无线网络技术的飞速发展，它可以应用于视频直播、多媒体会议、实时数据传输和网络游戏等业务中。在这些业务当中，随着用户数量的激增和用户需求的不断提高，在发送相同数据时，如果采用单播通信的方式将会对信息源和网络带宽造成巨大的压力，导致网络容易产生拥塞，无法满足用户的需求；如果采用广播的方式会使不需要此信息的用户也收到该信息，这样不仅信息的安全得不到保障，而且也浪费了大量的带宽，对于这样点到多点的业务，组播技术能够更好的解决上述问题。
3.传统的无线网络通常采用分布式管理的方式，网络资源和功能被分布在各个无线网络中间设备(如无线接入点ap、路由器、交换机等)上，并且每个设备独立执行控制决策。这样的方式虽然灵活，但存在管理效率低、难以实现全局网络的及时优化和协调的问题。随着网络规模的不断扩大，网络设备转发的流量数据越来越大，这样转发与控制紧密耦合的传统网络设备难以实时获取全局网络的状态信息，传统的组播树构造方法无法适应动态变化的无线网络环境，只能利用单一的网络资源来构建组播树，对网络的动态变化感知性差，难以满足当下网络服务质量的需求。
4.由于深度强化学习在高维度和复杂决策方面具有显著的优势，研究者们将深度强化学习与sdn架构相结合，以充分发挥其灵活性和自适应网络动态变化的优势，从而更好的提高网络的效率和性能。然而，目前将深度强化学习应用于sdn组播的研究多数局限于单智能体强化学习方法的讨论，相比多智能体强化学习方法，其收敛速度较慢，此外在网络状态频繁动态变化的情况下，单智能体方式难以快速响应数据流转发的需求。


技术实现要素：

5.本发明所要解决的是现有单智能体强化学习方法应用于sdn的组播路由所存在的收敛速度较慢和难以快速响应数据流转发的需求的问题，提供一种sdwn中基于多智能体深度强化学习的智能组播路由方法。
6.为解决上述问题，本发明是通过以下技术方案实现的：
7.sdwn中基于多智能体深度强化学习的智能组播路由方法，包括步骤如下：
8.步骤1、初始化actor网络参数和critic网络参数；初始化经验缓存区；设置最大回合数；
9.步骤2、在相同的状态空间、动作空间和奖励函数设置下，预训练一个源节点到所有目的节点的单播路由初始智能体权重，并将强化学习开始之前为每个智能体加载该初始智能体权重；
10.步骤3、先将源节点到目的节点集合的组播路由任务根据目的节点集合中目的节
点的数量分解为相应数量的单播路由任务，再将这些单播路由任务均等且随机地形成子组播路由任务分配给多个智能体；
11.步骤4、采集sdwn的网络拓扑信息和网络状态信息；将网络拓扑信息转换为无向加权连通图，并将网络状态信息转换为流量矩阵；无向加权连通图和流量矩阵形成与智能体交互的环境；
12.步骤5、初始化强化学习智能体环境，将智能体与环境进行交互得到智能体的当前状态s
t
，其中当前状态s
t
由当前流量矩阵和当前组播树构建矩阵组成；
13.步骤6、智能体将当前状态s
t
输入actor网络中，根据重要性采样选择出一个当前动作a
t
；智能体执行当前动作a
t
，并与环境交互得到当前奖励值r
t
和下一状态s
t+1
，并将(s
t
，a
t
，r
t
，s
t+1
)存入经验缓存区；
14.步骤7、智能体从经验缓存区中采样经验数据集进行学习，并从采样出的经验数据集中取出当前状态s
t
和下一状态s
t+1
；将这个两个状态分别输入critic网络中，得到当前状态s
t
的价值函数和下一状态s
t+1
的价值函数，并通过时序差分误差方法计算出时序差分误差，使用均方误差损失函数更新critic网络参数；再根据上述得到的当前状态s
t
的价值函数、下一状态s
t+1
的价值函数和时序差分误差，通过actor的策略梯度更新函数更新actor网络参数；
15.步骤8、清空经验缓存区，并判断所有智能体是否均完成了所分配的子组播路由任务，即找到了子组播路由任务中源节点到所有目的节点的子组播路树：如果是，则利用这些子组播路树构建最优组播树，并转入步骤9；否则，利用下一网络状态信息更新当前状态s
t
，并返回步骤6；
16.步骤9、判断当前回合数是否达到最大回合数：如果是，则将最后一次所构建的最优组播树输出；否则，令当前回合数加1，并返回步骤5。
17.上述步骤3中，网络状态信息包括各链路的剩余带宽、各链路的延时、各链路的丢包率、各链路的已用带宽、各链路的错包率、各链路的弃包率和各链路的距离。
18.上述步骤6中，智能体执行当前动作a
t
，并与环境交互会产生四种结果，即过程状态、无效动作、产生回路和终止状态；
19.过程状态：智能体执行的当前动作a
t
为有效动作，即往组播树中新添加了一个节点，则下一状态s
t+1
根据下一网络状态信息进行更新，当前奖励值r
t
为：
20.r
t
＝β1bw
ij
+β2(1-delay
ij
)+β3(1-loss
ij
)+β4(1-used_bw
ij
)+β5(1-errors
ij
)+β6(1-drop
ij
)+β7(1-distance
ij
)
21.无效动作：智能体执行的当前动作a
t
为无效动作，即选择了一个非邻居节点或者当前节点已在组播树当中，则下一状态s
t+1
维持当前状态s
t
不变，当前奖励值r
t
为设定的第一固定惩罚值c1；
22.产生回路：智能体执行的当前动作a
t
后，导致智能体陷入死循环无法探索出最优的路径，则下一状态s
t+1
回退到当前状态s
t
，当前奖励值r
t
为设定的第二固定惩罚值c2；
23.终止状态：智能体执行的当前动作a
t
后，源节点到所有目的节点的路径均已找到，组播树构建完成，则下一状态s
t+1
置空，当前奖励值r
t
为：
24.r
t
＝β1bw
tree
+β2(1-delay
tree
)+β3(1-loss
tree
)+β4(1-used_bw
tree
)+β5(1-errors
tree
)+β6(1-drop
tree
)+β7(1-distance
tree
)
25.式中，bw
ij
表示节点i与节点j间链路剩余带宽，delay
ij
表示节点i与节点j间链路延时，loss
ij
表示节点i与节点j间链路丢包率，used_bw
ij
表示节点i与节点j间链路已用带宽，errors
ij
表示节点i与节点j间链路错包率，drop
ij
表示节点i与节点j间链路弃包率，distance
ij
表示节点i与节点j间链路距离；bw
tree
表示组播树的总剩余带宽，delay
tree
表示组播树的总延时，loss
tree
表示组播树的总丢包率，used_bw
tree
表示组播树的总已用带宽，errors
tree
表示组播树的总错包率，drop
tree
表示组播树的总弃包率，distance
tree
表示组播树的总距离；β1表示剩余带宽权重，β2表示延时权重，β3表示丢包率权重，β4表示已用带权重，β5表示错包率权重，β6表示弃包率权重，β7表示距离权重。
26.与现有技术相比，本发明具有如下特点：
27.1)基于sdwn的高效组播路由，能够提高网络资源的利用效率，降低网络开销；sdwn控制器的集中式管理和控制，能够简化网络管理，提高网络的可维护性和灵活性；
28.2)通过sdwn架构采集的网络链路状态信息设计出智能体的状态空间、动作空间和奖励函数，使得智能体能够根据当前网络状态动态的调整组播树，能够更加智能的下发组播路由，避免组播数据包的环路产生，提高了网络的可靠性；
29.3)采用迁移学习技术，并将其与多智能体相结合，使智能体能够快速计算组播树，提高了组播路由的收敛速度。
附图说明
30.图1为组播树数据流向图。
31.图2为sdwn智能组播路由策略的系统构架图。
32.图3为多智能体协作构建组播树。
33.图4为智能体的状态矩阵图。
34.图5为sdwn中基于多智能体深度强化学习的智能组播路由方法的流程图。
35.图6为madrl-mr算法的伪代码。
具体实施方式
36.为使本发明的目的、技术方案和优点更加清楚明白，以下结合具体实例，对本发明进一步详细说明。
37.本发明提出一种sdwn中基于多智能体深度强化学习的智能组播路由方法，利用深度强化学习自适应性和灵活性的特点来适应网络的动态变化，采用多个智能体协作构建从源节点到所有目的节点的组播路径，通过南向接口向路径中的交换机下发流表，从而实现组播路由。另外，利用sdwn监控全局网络链路状态信息的特点，来实现管理无线网络并获取其全局拓扑和链路状态信息，使智能体能够根据动态网络的状态信息变化来智能的调整组播路由。
38.组播(multicast)，也叫多播、多点广播或群播，允许把信息同时传递给一组指定的目的地址。组播的数据报文在网络的传输层链路上仅需要传递一次，当且仅当遇到分叉链路时，组播数据报文才会被复制。组播网络通信的数据流向示意图如图1所示。组播网络通信的数据流向是一个树形结构，称为组播树(或斯坦纳树)，源节点src是树的根节点，组播的目的节点dst是树的叶子结点。组播路由的优化是寻找到一棵能达到最优性能的组播
树。
39.最优组播树实际上对应了数学上最优斯坦纳树问题的求解，它是一个经典的np-hard问题。假设给定的一个无向加权连通图用g(v，e，w)表示，其中v是节点集合，e是边的集合，w是边的权重，节点i和节点j之间的边e
ij
∈e都有一个权重w(e
ij
)。给定一个节点子集s∈v，s是组播的源节点src和目的节点dst＝{dst1，dst2，
…
，dstn}的集合。图g
′
是图g中包含顶点集s的子图。其中，图g
′
还包含一些不在顶点集合s中的节点，这些节点称为斯坦纳节点。最优斯坦纳树问题的目标就是在图g
′
中找出一棵包含s中所有节点的生成树t，并使其边的权值之和最小，如公式所示：
[0040][0041]
其中，v
t
表示树t中的所有节点，e
t
表示树t所有的边。
[0042]
严格来讲要求解这样np难的组播树问题的精确最优解是非常难的，现有方法都是讨论如何求解其近似最优解，对此我们做了如下一些近似处理，将其分解成一组从一个源节点到多个目的节点的路由。如公式所示：
[0043]
t＝{path1(src，dst1)，
…
，pathk(src，dstk)，
…
，pathn(src，dstn)}
[0044]
其中，pathk为组播树t中源节点src到dstk的路径，k＝1，2，
…
，n，dstk属于组播树的目的节点dst，n是目的节点的数量。
[0045]
如果每条路径pathk∈t均有一个最小代价，那么组播树t就是一个端到端的最小代价树。构建这样的一棵组播树，每条path(src，dstk)都可以采用单播路径的方式构建，最终由这些路径组合并去除冗余链路构建出最小代价的组播树。
[0046]
每条路径的优化目标由f(pathk)表示，组播树就是要为所有的目的节点都找到这样的一条路径，这些任务相互独立，由此可以将组播树的构建转换成数学上的多目标优化问题，如公式所示。
[0047]
max f(t)＝[f(path1)，
…
，f(pathk)，
…
，f(pathn)]
[0048]
其中，t是实现组播网络通信路径的组播树，pathk为每个目的节点的最优路径，且pathk∈t，n是目的节点的数量。
[0049]
结合sdn能够监控全局网络资源的特点，我们对于每条路径的最小代价f(pathk)，使用如下参数进行计算：
[0050]
1)bwk是pathk的剩余带宽，即源节点src到目的节点dstk的最小剩余带宽。其定义如公式所示：
[0051][0052]
其中，bw
ij
节点i和和节点j之间链路的剩余带宽。
[0053]
2)delayk是pathk的总时延，表示为pathk中所有链路的时延之和。其定义如公式所示：
[0054][0055]
其中，delay
ij
节点i和和节点j之间链路的时延。
[0056]
3)lossk是pathk的丢包率，由于部分链路的丢包率为0，所以对其通过公式计算：
[0057][0058]
其中，loss
ij
节点i和和节点j之间链路的丢包率。
[0059]
4)used_bwk是pathk的已用带宽，表示为源节点src到目的节点dstk的最大已用带宽。其定义如公式所示：
[0060][0061]
其中，used_bw
ij
节点i和和节点j之间链路的已用带宽。
[0062]
5)errorsk是pathk的错包率，通过公式计算：
[0063][0064]
其中，errors
ij
是节点i和节点j之间链路的错包率。
[0065]
6)dropsk是pathk的弃包率，通过公式计算：
[0066][0067]
其中，drops
ij
是节点i和和节点j之间链路的弃包率。
[0068]
7)distancek是pathk每条链路的平均距离。在无线中，ap间的距离远近会影响数据的转发，通过平均距离可以衡量每个ap节点的发送数据所耗费的平均能量，其定义如公式所示：
[0069][0070]
其中，distance
ij
是节点i和和节点j之间链路的距离。
[0071]
f(pathk)的目标是最大化剩余带宽bwk，最小化时延delayk、丢包率lossk、已用带宽used_bwk、错包率errorsk、弃包率dropsk和无线接入点ap间的距离distancek。如公式所示：
[0072]
f(pathk)＝ω1bwk+ω2delayk+ω3lossk+ω4used_bwk+ω5errorsk+ω6dropsk+ω7distancek[0073]
其中，ω
l
是每个参数的权重，l＝1，2，
…
，7。在优选实施例中，ω1＝0.7，ω2＝0.3，ω3＝0.1，ω4＝0.1，ω5＝0.1，ω6＝0.1，ω7＝0.1。
[0074]
由于对全局动态网络状态信息的及时获取是构建最优组播树的基本前提之一，而sdwn(software defined wireless networking，sdwn)是将软件定义网络与无线网络相结合，其利用sdn控制逻辑集中、转发与控制解耦合等特点解决了传统无线网络结构中网络管理和控制效率低、难以实现全局优化和协调等问题，可以充分利用集中式管理的优势，实现网络资源的全局优化和协调，因此本发明采用sdwn智能组播路由策略的系统构架，如图2所示，其包含4个平面，即数据平面、控制平面、应用平面、知识平面。
[0075]
(1)数据平面
[0076]
数据平面由无线接入节点(access point，ap)和站点(station，sta)组成，这些无线接入节点执行一组基本任务，例如根据控制器下发的指令完成ap与控制器的映射、报文路由和站点迁移等任务。数据平面的ap在不知道无线网络中其他ap的情况下运行，完全依赖于控制平面、应用平面和知识平面执行相关操作.并周期性的与控制器交互，将无线网络的状态信息传递给控制平面。
[0077]
(2)控制平面
[0078]
控制平面包含集中控制器，控制器通过南向接口对数据平面进行控制和管理，并且根据收集网络流和无线ap的状态信息来构建网络的全局视图，从而进一步实现对网络资源进行调度。控制器提供北向接口与知识平面交互，方便知识平面策略的下发和部署。控制平面包括三个模块：网络拓扑发现模块、链路信息检测模块和流表安装模块。
[0079]
网络拓扑发现模块：通过openflow发现协议(openflow discovery protocol，ofdp)进行拓扑发现，控制器向数据平面周期性的发送lldp(link layer discovery protocol，lldp)请求数据包，获取当前的网络拓扑结构，并收集有关网络设备之间连接的信息。其中，主要过程是控制器向无线ap发送features-request消息请求设备的配置信息。无线ap收到后，将自己的端口信息、mac地址信息和datapathid信息封装到features-reply包中，发送到控制器，控制器解析该数据包确定建立与无线ap之间的连接。该模块根据收集到信息，将网络中每个设备进行关联，借此推断出网络拓扑。并将收集到的网络设备状态信息和配置信息存储备用。
[0080]
链路状态信息检测模块：周期性的向数据平面上的设备发送状态请求数据包。当设备接收到状态请求信息时，将自身当前状态信息(如发送数据流大小、接受数据流大小、丢弃数据包数、拥塞情况和ap间的距离等)封装进数据包，并发送至控制器。该模块接收并统计回复消息，从消息数据包中解析出包含网络状态的原始数据。解析后的数据还被提供给应用平面进行处理。
[0081]
流表安装模块：首先通过北向接口接收来自知识平面选出的最优组播路由。然后在下一数据流到达之前，由控制器通过南向接口向无线ap下发并安装流表项，最后由数据平面完成流量的转发。
[0082]
(3)应用平面
[0083]
应用平面用于处理控制平面和知识平面之间的数据处理逻辑，主要将控制平面向数据平面采集到的网络状态原始数据处理成我们所需要的网络流量矩阵。
[0084]
(4)知识平面
[0085]
知识平面是在sdwn结构上增加的核心模块，本发明解决组播路由的算法核心就运行在该平面。在知识平面中通过多智能体相互协作进行组播路径的计算。知识平面通过从应用平面获取处理好的流量矩阵，将流量矩阵转换成智能体训练的数据，经过训练，使智能体获得的奖励值收敛，即每个智能体使用这些流量矩阵探索出最优的执行策略，通过多个智能体协作完成组播路径的构建，再将该组播路径通过北向接口发送给控制平面。
[0086]
知识平面中多智能体构建组播树的方案，将构造最小端到端代价的组播树问题分解为构造多个从源节点到单个目的节点的单播路径，最终组播树为这多个单播路径的集合。对于构建这样一棵组播树，我们将其抽象化为马尔科夫决策(mdp)。利用全局网络拓扑
和链路状态信息设计智能体的状态空间、动作空间和奖励函数。如图3所示。首先，将src到dst＝{dst1，dst2，
…
，dst6}的组播路由分解为{(src，dst1)，
…
，(src，dst6)}6个单播路由。其次，随机的划分成三个子任务{(src，dst2)，(src，dst3)}、{(src，dst1)，(src，dst5)}、{(src，dst4)，(src，dst6)}。然后再随机分配给3个智能体。最后，由智能体agent1、agent2和agent3分别完成相应目的节点的单播路由构建，即{path1，path2，
…
，path6}。最终得到由多个智能体协作完成的组播树。
[0087]
为了解决单一智能体构建组播树收敛速度较慢，以及难以快速响应数据流转发需求等问题，本发明提出一个多智能体深度强化学习算法来构建组播树，每个智能体都可以独立地学习和适应网络状态的变化，通过协作来实现更好的路由策略。多智能体是单智能体到多智能体的推广，其每个智能体的状态空间、动作空间、奖励函数以及内部结构是相同的，下面介绍强化学习的智能体的设计：
[0088]
(1)状态空间
[0089]
状态空间是对于环境和智能体的描述，智能体可以通过对环境的观测得到当前状态。强化学习的环境由数据平面构成，其中智能体的状态空间则由数据平面的链路状态信息和当前源节点到所有目的节点的路径的构建情况组成，我们将其为多通道的矩阵g
t
。如图4所示，多通道的矩阵g
t
由8个通道的矩阵组成，其中n是网络拓扑的节点个数。将从数据平面采集到的链路状态信息即剩余带宽、延时、丢包率、已用带宽、错包率、弃包率和路距离等7个数据转换成带权无向图的邻接矩阵，得到7个不同矩阵即剩余带宽bw矩阵、延时delay矩阵、丢包率loss矩阵、已用带宽sed_bw矩阵、错包率errors矩阵、弃包率drops矩阵和距离distance矩阵所组成的流量矩阵tm。将组播树的构建情况转换成对1个对称矩阵即组播树构建矩阵m
tree
，其中src是源节点，{dst1，dst2，dst3}是组播树的目的节点，将节点i和节点j之间的边置1，则代表这条边加入组播树中。
[0090]
多通道的矩阵g
t
改变的所有可能性的集合则为状态空间s。每个状态对应于一个多通道的矩阵。状态转移对应着向路径中添加了一条边，即添加了从一个节点到另一个节点之间的链路。根据g
t
的改变将当前状态s
t
转变为下一状态s
t+1
。当源节点到所有目的节点的路径均找到时(即组播树构建完成)，将s
t+1
设为终止状态，即s
t+1
＝none。
[0091]
(2)动作空间
[0092]
动作空间是智能体根据观测得到当前状态后所能采取的动作的集合本发明将数据平面的无线ap节点(即下一跳)作为动作，即数据平面的无线ap节点(即下一跳)作为动作，即其中nk表示ap节点i，i＝1，2，...n，ai与ni一一对应。采取某一动作的含义是将动作(无线ap节点)加入到相对应源节点到目的节点的路径中。对于状态空间中的每个状态si∈s，智能体采取任意动作a，当动作a被执行将导致状态的变化。理论上所有节点都作为一个动作，但并不是所有动作都会被执行，为了符合神经网络需要输入张量的需求，选择动作时就会产生一些无效动作。假设智能体在状态s
t
下，选择一个不与当前状态下节点相邻的节点作为动作a
t
后，与环境交互产生的状态s
t+1
并不能推进路径的构建，则不能将此节点加入到组播树中。所以智能体的有效动作为当前状态下的相邻节点集合，即该状态下节点的度dr(ni)。
[0093]
(3)奖励函数
[0094]
奖励函数是指导智能体选择最大的回报，以获得最优的策略。它可以用来衡量智
能体所采取的某个动作在某个状态下的价值，从而帮助智能体朝着最优的策略发展。通过奖励函数向智能体传达最大化剩余带宽，最小化时延、丢包率、已用带宽、错包率、弃包率和ap之间的距离的优化目标。每个时刻，智能体根据其策略π，在当前状态s
t
选择一个动作a
t
，环境对这些动作做出相应的响应，状态转移为s
t+1
，获得一个奖励值r
t+1
。由于在选择动作时会选择出有效动作和无效动作，且执行有效动作会产生环路、正常状态变化和终止状态。所以智能体与环境交互会产生四种结果：过程状态part；无效动作hell；产生回路loop；终止状态end。下面将对这四种结果分别介绍和设计奖励函数。
[0095]
过程状态part：智能体执行一个有效动作，往路径中新添加了一个节点，状态转变为非终止状态的过程状态，此时智能体更新策略继续探索学习，奖励值为r
part
。为了适应动态的网络状态，使智能体选择出最优的动作组合，我们使用节点i与节点j的网络链路的剩余带宽bw
ij
、时延delay
ij
、丢包率loss
ij
、已用带宽used_bw
ij
、错包率errors
ij
、弃包率drop
ij
和ap之间的距离distance
ij
计算奖励值，β
l
∈[0，1]，l＝1，2，
…
，7是这些参数的权重因子。
[0096]rpart
＝β1bw
ij
+β2(1-delay
ij
)+β3(1-loss
ij
)+β4(1-used_bw
ij
)+β5(1-errors
ij
)+β6(1-drop
ij
)+β7(1-distance
ij
)
[0097]
无效动作hell：智能体选择无效动作，即选择了一个非邻居节点或者当前节点已在组播树当中，这个动作将不被执行，状态维持不变。为了避免智能体选择出无效动作，这里给予固定惩罚值，为r
hel
＝c1。
[0098]
产生回路loop：执行的有效动作中除了能够产生过程状态，也会有一定的几率使路径产生环路，该动作虽然是当前状态的邻居节点，但一旦执行该动作，将会导致智能体陷入死循环无法探索出最优的路径，所以在此将状态回退到s
t
，并且给一个定值惩罚，即r
loop
＝c2。
[0099]
终止状态end：当执行动作后，此时源节点到所有目的节点的路径均已找到时，即组播树构建完成，则将状态设置为终止状态，即s
t+1
＝none。在此状态下奖励函数采用整个组播树路径的网络链路状态来计算奖励值，如公式所示：
[0100]rend
＝β1bw
tree
+β2(1-delay
tree
)+β3(1-loss
tree
)+β4(1-used_bw
tree
)+β5(1-errors
tree
)+β6(1-drop
tree
)+β7(1-distance
tree
)
[0101]
(4)a2c网络参数更新
[0102]
actor网络是策略函数π
θ
(a|s)，策略被参数化为神经网络，用θ表示，输入当前状态，输出下一个采取的动作。该网络的训练目标是最大化累计回报的期望。其策略梯度如公式所示：
[0103][0104]
其中，是累计回报的期望，是在状态下，执行所有动作所产生的期望值。
[0105]
在actor-critic(ac)中会产生高方差问题，因为一个动作轨迹中假如所有的动作回报都为正，这并不代表着所有动作都是优的，它也可能是个次优动作，所以advantage actor-critic引入基线的方式来解决，即在原有的奖励值上减去一个baseline，baseline
由v
π
(s)担任。这个计算方式称为advantage。因此公式中有一项被定义为比较优势(advantage function)，如公式所示：
[0106][0107]
从上式中可看出需要完成两种估计，动作值函数估计和状态值函数估计而q值的期望值计算方式是r
t
+γv(s
t+1
)，γ是衰减因子，γ∈[0，1]。因为执行一个动作的下一个回合必定更新到s
t+1
状态，再加上本回合所获得的奖励r
t
，即是q的期望值。并且结合时序差分误差方法(td)，得到如公式所示：
[0108][0109]
td
error
＝r+γv(s
t+1
)-v(s
t
)
[0110][0111]
critic是指价值函数v
π
(s)，表示智能体从状态s开始所能期望获得的未来收益，通过这个期望收益对当前策略的值函数进行估计，即评估演员的好坏。借助于价值函数，actor-critic算法可以进行单步参数更新，不需要等到回合结束才更新。其计算方式如公式所示：
[0112]vπ
(s)＝e
π
{r
t
|s
t
＝s}
[0113]
对于critic网络参数ω更新使用均方差损失函数来进行梯度反向传播更新，其均方差损失函数如公式所示：
[0114]
mse＝∑(r+γv
π
(s
t+1
)-v
π
(s
t
，ω))2[0115]
根据上述所分析的策略梯度公式，a2c的比较优势函数，再结合时序差分方法(td)，由此得出actor的策略函数参数θ更新的公式为：
[0116][0117]
其中，α1是学习率。
[0118]
多智能体强化学习的挑战主要体现在训练的非平稳性、可伸缩性、部分可观察性和隐私和安全等四个方面上。基于上述的挑战多智能体的训练方式主要分为以下三种：完全去中心化(fully decentralized，il)、完全集中(fully centralized)和集中训练分散执行(centralized training and decentralized execution，ctde)。考虑到完全集中式训练减轻了部分可观察性和非平稳性问题，对于大规模和实时系统是不可取的。同时集中训练分散执行的训练方法虽然有一个集中控制单元收集各智能体的训练信息，但难以扩展到大规模的智能体环境当中，随着智能体数量的增加，集中式critic网络会积累高方差问题，值函数很难收敛。所以本发明采用完全去中心化的训练方式，该方法是单个智能体到多个智能体的直接推广，其中每个代理独立于其他参与者优化其策略，忽略了非平稳性问题，对于该方法的智能体的收敛性问题，我们采用迁移强化学习的策略来解决。实践表明il方法在无线通信网络中的几个资源分配和控制问题取得了令人满意的结果。
[0119]
本发明的路由算法首先将输入的源节点src和目的节点dst均等分成若干个子任务，即每个智能体会被分配src到若干个dst∈dst的任务。其次根据当前网络拓扑图graph
的环境状态，每智能体学习出最优的src到若干个dst的单播路径。最后直到所有智能体均完成任务，将所学习到的src到所有dst的路径组合，得到src到dst在graph中最优的组播树。
[0120]
为加快多智能体的训练速度，解决多智能体在训练阶段不稳定和收敛困难的问题，将迁移学习应用到强化学习当中。迁移学习(transfer learning，tl)可以将专家或其他过程中获取的知识迁移到当前任务中，达到加速学习的作用。迁移学习在强化学习中的应用按照迁移的设置主要分为以下三类：
①
从单一源任务到目标任务的固定域迁移。
②
跨多个源任务到目标任务的固定域迁移。
③
源任务和目标任务不同域迁移。本发明设计的是第二种方案，在任务域相同的情况下，跨多个源域到目标任务的固定域迁移。即在相同的状态空间、动作空间和奖励函数设置下，由sdwn获取无线网络的拓扑和链路状态信息，根据生成的网络拓扑和流量矩阵形成与智能体交互的环境，并预训练一个源节点到所有目的节点的单播路由初始智能体权重。在每个智能体在学习开始之前先加载这个初始权重，也就是知识迁移，减少智能体在训练之初的无效探索，再在训练学习过程中根据不同的任务调整算法参数，加快多智能体的收敛速度，使得多智能体之间配合更加稳定，更能适应动态变化的网络。
[0121]
一种sdwn中基于多智能体深度强化学习的智能组播路由方法(madrl-mr)，如图5所示，其具体包括步骤如下：
[0122]
步骤1、初始化每个智能体的权重即actor网络参数和critic网络参数，初始化经验缓存区，该经验缓存区在每次更新后丢弃。
[0123]
每个智能体的权重的初始化可以采用常用初始化方法，也可以采用利用迁移学习技术，加载在训练开始之前预训练一个所有源节点到所有目的节点的智能体权重。
[0124]
步骤2、在相同的状态空间、动作空间和奖励函数设置下，预训练一个所有源节点到所有目的节点的单播路由初始智能体权重，并将强化学习开始之前为每个智能体加载该初始智能体权重。
[0125]
步骤3、先将源节点src到目的节点集合dst的组播路由任务根据目的节点集合dst中目的节点的数量分解为相应数量的单播路由任务，再将这些单播路由任务均等且随机地形成子组播路由任务分配给多个智能体。
[0126]
根据目的节点集合dst中目的节点的数量分解为相应数量的单播路由任务，即目的节点集合dst中具有多少个目的节点就分解为多少个单播路由任务。
[0127]
单播路由任务均等且随机地分配给多个智能体，就是根据智能体的数目对单播路由任务进行均分，如3个智能体，7个单播路由任务，就会将7个按3：2：2比例进行分配，其中1个智能体分配3个单播路由任务，另外2个智能体各分配2个单播路由任务。
[0128]
步骤4、采集sdwn的网络拓扑信息和网络状态信息；将网络拓扑信息转换为无向加权连通图g(v，e，w)，并将网络状态信息转换为流量矩阵tm；无向加权连通图g(v，e，w)和流量矩阵tm形成与智能体交互的环境。
[0129]
无向加权连通图g(v，e，w)中，v是节点集合，e是边的集合，w是边的权重，
[0130]
由于网络状态信息包括各链路的剩余带宽、各链路的延时、各链路的丢包率、各链路的已用带宽、各链路的错包率、各链路的弃包率和各链路的距离，因此流量矩阵tm包括剩余带宽矩阵、延时矩阵、丢包率矩阵、已用带宽矩阵、错包率矩阵、弃包率矩阵和距离矩阵。
[0131]
步骤5、将智能体与环境进行交互得到智能体的当前状态s
t
，其中当前状态s
t
由当前流量矩阵tm和当前组播树构建矩阵m
tree
组成。
[0132]
步骤6、智能体将当前状态s
t
输入actor网络中，根据重要性采样选择出一个当前动作a
t
；智能体执行当前动作a
t
，并与环境交互得到当前奖励值r
t
和下一状态s
t+1
，并将(s
t
，a
t
，r
t
，s
t+1
)存入经验缓存区。
[0133]
智能体执行当前动作a
t
，并与环境交互会产生四种结果，即过程状态、无效动作、产生回路和终止状态；
[0134]
过程状态：智能体执行的当前动作a
t
为有效动作，即往组播树中新添加了一个节点，则下一状态s
t+1
根据下一网络状态信息进行更新，当前奖励值r
t
为：
[0135]rt
＝β1bw
ij
+β2(1-delay
ij
)+β3(1-loss
ij
)+β4(1-used_bw
ij
)+β5(1-errors
ij
)+β6(1-drop
ij
)+β7(1-distance
ij
)
[0136]
无效动作：智能体执行的当前动作a
t
为无效动作，即选择了一个非邻居节点或者当前节点已在组播树当中，则下一状态s
t+1
维持当前状态s
t
不变，当前奖励值r
t
为固定的惩罚值c1；
[0137]
产生回路：智能体执行的当前动作a
t
后，导致智能体陷入死循环无法探索出最优的路径，则下一状态s
t+1
回退到当前状态s
t
，当前奖励值r
t
为固定的惩罚值c2；
[0138]
终止状态：智能体执行的当前动作a
t
后，源节点到所有目的节点的路径均已找到，组播树构建完成，则下一状态s
t+1
置空，当前奖励值r
t
为：
[0139]rt
＝β1bw
tree
+β2(1-delay
tree
)+β3(1-loss
tree
)+β4(1-used_bw
tree
)+β5(1-errors
tree
)+β6(1-drop
tree
)+β7(1-distance
tree
)
[0140]
式中，bw
ij
表示节点i与节点j间链路剩余带宽，delay
ij
表示节点i与节点j问链路延时，loss
ij
表示节点i与节点j间链路丢包率，used_bw
ij
表示节点i与节点j间链路已用带宽，errors
ij
表示节点i与节点j间链路错包率，drop
ij
表示节点i与节点j间链路弃包率，distance
ij
表示节点i与节点j间链路距离；bw
tree
表示组播树的总剩余带宽，delay
tree
表示组播树的总延时，loss
tree
表示组播树的总丢包率，used_bw
tree
表示组播树的总已用带宽，errors
tree
表示组播树的总错包率，drop
tree
表示组播树的总弃包率，distance
tree
表示组播树的总距离；β1表示剩余带宽权重，β2表示延时权重，β3表示丢包率权重，β4表示已用带权重，β5表示错包率权重，β6表示弃包率权重，β7表示距离权重。
[0141]
步骤7、智能体从经验缓存区中采样出批量大小为k的经验数据集进行学习，并从采样出的经验数据集中取出当前状态s
t
和下一状态s
t+1
，将这个两个状态分别输入critic网络中，得到当前状态s
t
的价值函数v
π
(s
t
)和下一状态s
t+1
的价值函数v
π
(s
t+1
)，并通过时序差分误差方法计算出时序差分误差td
error
，使用均方误差损失函数更新critic网络参数ω，再根据上述计算得到的v
π
(s
t
)、v
π
(s
t+1
)和td
error
，通过actor的策略梯度更新函数更新actor网络参数θ。
[0142]
步骤8、清空经验缓存区，并判断所有智能体是否均完成了所分配的子组播路由任务，即找到了子组播路由任务中源节点到所有目的节点的子组播路树：如果是，则利用子组播路树构建最优组播树，并转入步骤9；否则，利用下一网络状态信息更新当前状态s
t
，并返回步骤6。
[0143]
步骤9、判断当前回合数是否达到最大回合数：如果是，则将最后一次所构建的最
优组播树输出；否则，令当前回合数加1，并返回步骤5。
[0144]
madrl-mr多智能体深度强化学习组播路由算法的详细实现见图6。算法输入的是网络拓扑g(v，e)，流量矩阵tm，组播的源节点和目的节点(src，dst)，以及强化学习算法的超参数。算法的输出是从源节点src到目的节点集合dst的一棵最优的组播树。
[0145]
第1行到第3行是分别初始化actor网络参数、critic网络参数和经验缓存区，此经验缓存区在每次更新后丢弃。
[0146]
第4行是利用迁移学习技术，加载在训练开始之前预训练一个所有源节点到所有目的节点的智能体权重，即为知识迁移。
[0147]
第5行是将组播组中的目的节点依据输入的智能体数量均等且随机拆分成若干个子任务，并分配给每个智能体。
[0148]
第8行到第9行是初始化环境，获得初始化状态s
t
。第11行到第13行是将状态s
t
输入actor网络中，根据重要性采样选择出一个动作a
t
。再执行这个动作与环境交互得到奖励值r
t
和下一个状态s
t+1
，并将(s
t
，a
t
，r
t
，s
t+1
)存入经验缓存区。第14行到第18行是根据经验缓存区中的经验进行学习，通过将其中存储的s
t
和s
t+1
输入critic网络得到v
π
(s
t
)和v
π
(s
t+1
)，通过计算出时序差分误差td
error
。第19行是计算均方误差，使用均方差损失函数作为critic网络参数ω的梯度更新。第20行是根据计算得到的v
π
(s
t
)、v
π
(s
t+1
)和td
error
，更新actor网络参数θ。第21行是清空经验缓存区。第24行到第27行是判断所有智能体是否都找到了源节点到目的节点的路径，通过将这些路径去除冗余链路得到最优组播树。最后第28行更新状态s
t
，进入下一个episode。
[0149]
需要说明的是，尽管以上本发明所述的实施例是说明性的，但这并非是对本发明的限制，因此本发明并不局限于上述具体实施方式中。在不脱离本发明原理的情况下，凡是本领域技术人员在本发明的启示下获得的其它实施方式，均视为在本发明的保护之内。

技术特征：
1.sdwn中基于多智能体深度强化学习的智能组播路由方法，其特征是，包括步骤如下：步骤1、初始化actor网络参数和critic网络参数；初始化经验缓存区；设置最大回合数；步骤2、在相同的状态空间、动作空间和奖励函数设置下，预训练一个源节点到所有目的节点的单播路由初始智能体权重，并将强化学习开始之前为每个智能体加载该初始智能体权重；步骤3、先将源节点到目的节点集合的组播路由任务根据目的节点集合中目的节点的数量分解为相应数量的单播路由任务，再将这些单播路由任务均等且随机地形成子组播路由任务分配给多个智能体；步骤4、采集sdwn的网络拓扑信息和网络状态信息；将网络拓扑信息转换为无向加权连通图，并将网络状态信息转换为流量矩阵；无向加权连通图和流量矩阵形成与智能体交互的环境；步骤5、初始化强化学习智能体环境，将智能体与环境进行交互得到智能体的当前状态s
t
，其中当前状态s
t
由当前流量矩阵和当前组播树构建矩阵组成；步骤6、智能体将当前状态s
t
输入actor网络中，根据重要性采样选择出一个当前动作a
t
；智能体执行当前动作a
t
，并与环境交互得到当前奖励值r
t
和下一状态s
t+1
，并将(s
t
，a
t
，r
t
，s
t+1
)存入经验缓存区；步骤7、智能体从经验缓存区中采样经验数据集进行学习，并从采样出的经验数据集中取出当前状态s
t
和下一状态s
t+1
；将这个两个状态分别输入critic网络中，得到当前状态s
t
的价值函数和下一状态s
tt1
的价值函数，并通过时序差分误差方法计算出时序差分误差，使用均方误差损失函数更新critic网络参数；再根据上述得到的当前状态s
t
的价值函数、下一状态s
t+1
的价值函数和时序差分误差，通过actor的策略梯度更新函数更新actor网络参数；步骤8、清空经验缓存区，并判断所有智能体是否均完成了所分配的子组播路由任务，即找到了子组播路由任务中源节点到所有目的节点的子组播路树：如果是，则利用这些子组播路树构建最优组播树，并转入步骤9；否则，利用下一网络状态信息更新当前状态s
t
，并返回步骤6；步骤9、判断当前回合数是否达到最大回合数：如果是，则将最后一次所构建的最优组播树输出；否则，令当前回合数加1，并返回步骤5。2.根据权利要求1所述的sdwn中基于多智能体深度强化学习的智能组播路由方法，其特征是，步骤3中，网络状态信息包括各链路的剩余带宽、各链路的延时、各链路的丢包率、各链路的已用带宽、各链路的错包率、各链路的弃包率和各链路的距离。3.根据权利要求1所述的sdwn中基于多智能体深度强化学习的智能组播路由方法，其特征是，步骤6中，智能体执行当前动作a
t
，并与环境交互会产生四种结果，即过程状态、无效动作、产生回路和终止状态；过程状态：智能体执行的当前动作a
t
为有效动作，即往组播树中新添加了一个节点，则下一状态s
t+1
根据下一网络状态信息进行更新，当前奖励值r
t
为：r
t
＝β1bw
ij
+β2(1-delay
ij
)+β3(1-loss
ij
)+β4(1-used_bw
ij
)+β5(1-errors
ij
)+β6(1-drop
ij
)+β7(1-distance
ij
)
无效动作：智能体执行的当前动作a
t
为无效动作，即选择了一个非邻居节点或者当前节点已在组播树当中，则下一状态s
t+1
维持当前状态s
t
不变，当前奖励值r
t
为设定的第一固定惩罚值c1；产生回路：智能体执行的当前动作a
t
后，导致智能体陷入死循环无法探索出最优的路径，则下一状态s
t+1
回退到当前状态s
t
，当前奖励值r
t
为设定的第二固定惩罚值c2；终止状态：智能体执行的当前动作a
t
后，源节点到所有目的节点的路径均已找到，组播树构建完成，则下一状态s
t+1
置空，当前奖励值r
t
为：r
t
＝β1bw
tree
+β2(1-delay
tree
)+β3(1-loss
tree
)+β4(1-used_bw
tree
)+β5(1-errors
tree
)+β6(1-drop
tree
)+β7(1-distance
tree
)式中，bw
ij
表示节点i与节点j间链路剩余带宽，delay
ij
表示节点i与节点j间链路延时，loss
ij
表示节点i与节点j间链路丢包率，used_bw
ij
表示节点i与节点j间链路已用带宽，errors
ij
表示节点i与节点j间链路错包率，drop
ij
表示节点i与节点j间链路弃包率，distance
ij
表示节点i与节点j间链路距离；bw
tree
表示组播树的总剩余带宽，delay
tree
表示组播树的总延时，loss
tree
表示组播树的总丢包率，used_bw
tree
表示组播树的总已用带宽，errors
tree
表示组播树的总错包率，drop
tree
表示组播树的总弃包率，distance
tree
表示组播树的总距离；β1表示剩余带宽权重，β2表示延时权重，β3表示丢包率权重，β4表示已用带权重，β5表示错包率权重，β6表示弃包率权重，β7表示距离权重。

技术总结
本发明公开一种SDWN中基于多智能体深度强化学习的智能组播路由方法，利用深度强化学习自适应性和灵活性的特点来适应网络的动态变化，采用多个智能体协作构建从源节点到所有目的节点的组播路径，通过南向接口向路径中的交换机下发流表，从而实现组播路由。另外，利用SDWN监控全局网络链路状态信息的特点，来实现管理无线网络并获取其全局拓扑和链路状态信息，使智能体能够根据动态网络的状态信息变化来智能的调整组播路由。来智能的调整组播路由。来智能的调整组播路由。


技术研发人员：胡洪文 叶苗 蒋秋香 王勇
受保护的技术使用者：桂林电子科技大学
技术研发日：2023.06.12
技术公布日：2023/8/4