宽窄融合网络切片调度算法的研究与实现

章广梅，王均春，胡金龙，董守玲，徐寅鑫

(1.中国电子科技集团公司第七研究所， 广东 广州 510310 2.国防科技大学 信息通信学院，湖北 武汉 430010 3.华南理工大学 计算机科学与工程学院， 广东 广州 510640)

5G 网络使得网络应用类型变得更加多样，未来必将涌现各种具有差异化性能需求的新型应用，比如，有些应用需要低时延，有些应用需要高带宽，而有些应用则需要更高的可靠性要求。 然而，当前网络一方面还不够灵活，无法充分利用网络资源进行业务服务，导致每引入一种新业务就要单独配备一套独立的网络结构和资源，对网络管理和运营带来了较大不便且资源利用率低，而另一方面则是无法实现业务定制化的数据传输需求，仅能满足已有常见的业务性能。

现有的网络切片调度算法主要包括启发式算法和基于软件定义网络（SDN）架构的调度算法。 传统的调度方式，比如利用遗传算法［1］解决服务功能链（SFC）的部署，以此达到链路之间的公平分配，但是这种方法仅仅是解决单一调度周期的问题，并且现有的网络环境是复杂多变的，传统算法选择的链路很有可能在某一时刻发生堵塞而无法进行流量传输，而其他链路又是处于空闲状态，这就造成了资源的不必要浪费，因此传统算法具有一定的局限性。SDN 的出现为数据中心网络的发展提供了契机［2］，其中，基于SDN 与网络功能虚拟化（NFV）融合的网络切片资源分配优化算法［3］，对不同的业务需求划分对应的虚拟子网节点集合，再根据不同SFC 的要求，对每一类网络切片建模；基于最大最小蚁群的NFV 部署方法［4］，利用SFC 保留历史队列信息以预测网络的未来状态，根据预测结果进行NFV 的调度；基于改进式贪婪算法的5G 网络切片动态资源调度策略［5］，将用户和切片按优先级和服务权重从大到小排列，依次组合起来，完成用户服务；基于GA⁃PSO 优化的网络切片编排算法［6］，通过遗传算法中的杂交变异思想，进行快速随机搜索，更新并优化网络切片，然后利用粒子群追逐局部最优解与全局最优解，从而得到最优的网络切片。 这些方法虽然改变了切换业务与新业务的被动接受的优先级［7］，但是使用固定的调度阈值，一旦网络环境发生变化，上述方法一般需要重新进行搜索求解，且当网络环境复杂时算法收敛速度较慢，难以适应在线或实时的网络切片调度需求。

为了动态调整切片的调度阈值以适应网络环境的变化，本文在预路径规划的切片构造算法［8］的基础上，提出一种基于深度强化学习的切片调度算法，为不同的业务灵活提供定制化服务，在适应多变复杂的网络环境的前提下，尽可能减少切片构造的时间开销，将切片构造和切片调度算法相结合，快速高效地实现业务数据定制化传输和通信网络高效灵活的可管可控。

1 面向业务需求的切片构造方法

1.1 QoS 切片构造

当今网络足够复杂，网络中存在多个用户，并且每个用户可以访问不同类型的应用服务器，网络拓扑图也十分庞大。 如果使用复杂的路由算法［9］，将会耗费很多时间来计算路由，增加了计算的时间开销，因此本文根据业务QoS 需求表、网络拓扑信息和业务流量信息预先构造切片路径，按照业务的优先级从高到低依次执行QoS 切片构造算法，为每一种业务类型构造出专属的网络链路并保留网络切片资源，主要分为信息搜集和切片构造的路径划分两部分。

1.2 信息搜集

主要负责搜集3 类信息，分别是业务的QoS 需求表、网络拓扑信息以及网络流量信息，其中：

（1） 业务的QoS 需求表包括业务的类型、优先级、带宽需求、时延要求、可靠性要求、频率需求等信息。

（2） 网络拓扑信息即网络拓扑有向图，可以从实际的网络拓扑转换而来，有向图中的边代表节点之间的链路，边权重代表链路的带宽大小。

（3） 网络流量信息即根据历史信息得到的每种业务的带宽需求的阈值、各个业务的发送端节点和接收端节点构成的业务矩阵以及网络中分配的频率资源池。

1.3 路径划分

QoS 切片构造的过程可以描述为：给定网络的整体拓扑结构，将业务的QoS 需求、业务矩阵和频率资源池作为输入，根据QoS 切片的构造方法为该业务划分出一组切片资源，将该切片资源分出一部分用于满足该业务的QoS 需求，修改资源池中的有效可用资源，并从频率资源池中选出与业务需求最贴近的频率分配给业务，修改资源池中的剩余频率资源，最后使用贪婪算法将所有的业务全部处理完毕。

单个的QoS 切片构造的目标函数及约束条件如下。

式中：E 表示边集合；b（u，v）表示边（u，v）是否用于传输流量；jQ表示业务的频率需求；kQ表示网络分配的频率；g（u，v）表示某一流量在边（u，v）上传输的量；a（u，v）表示链路的总容量；fQ表示业务的带宽需求。

该算法的目标是在满足业务QoS 需求的前提下，业务传输使用的链路条数最少，以此保证时延，并且把网络中的频率资源最贴合地分配给对应的业务。 约束条件则依次表示某一条链路只能选择传输或者不传输业务流量；业务传输的流量既不能超过链路的总容量，也必须要满足业务的带宽需求；链路的传输总流量不能超过其总容量；中间节点输入输出的流量需要保持一致，发送端和接收端节点的流量也要和业务流量保持一致。

使用贪婪算法完成所有QoS 切片的构造：按优先级高低依次处理各类业务，对每一类业务，选择对应的网络频率进行分配，求得切片路径，保留路径上的节点所要传输的业务流量，修改各节点上剩余资源数量以及修改网络可用频率信息，然后处理下一个业务，直到优先级最低的业务也被处理。

2 基于深度强化学习的调度算法

2.1 研究思路

现有的网络切片调度算法主要采用的是启发式算法，或者是基于精确数学模型的优化算法，然而这些算法并没有考虑到无线网络环境的时变性，目前采用的算法规则大多是固定的、不可变化的，并不具有自我演进的功能。 此外，由于宽窄融合网络拓扑十分复杂，很难在拓扑和切片的选择以及实际效果之间推导出精确的关系表达式即启发式算法的固定规则很难在复杂的网络拓扑环境中推导出来，因此本文以切片构造的结果为基础，采用基于深度强化学习的方法，学习在不同的网络环境下切片调度的最优调度策略，即每个切片的可用带宽阈值，切片调度时，切片可用带宽高于阈值则继续选择该切片进行调度，低于阈值则选择优先级更高的切片进行调度，以此达到业务定制化数据传输的需求。

2.2 问题建模

图1 表示在每个调度周期，切片调度器根据观测到的网络状态以及感知到的业务信息，将其作为策略神经网络的输入，并输出此时选择各个切片的概率向量，然后调度器选择概率最大的切片来执行选择动作，并观察奖励函数的反馈，不断迭代，直到在每一个调度周期，调度器都能执行最优的调度策略，达到定制化服务的要求。

图1 调度周期流程图

2.2.2 深度确定性策略梯度（DDPG）网络模型

采用的DDPG 网络模型有4 个网络，分别是Actor 当前网络、Actor 目标网络、Critic 当前网络、Critic 目标网络，它们的功能分别如下。

Actor 当前网络：实现策略神经网络参数ω的更新，其根据当前状态st选择动作at， 与环境交互后得到下一个状态st＋1和环境反馈的奖励值rt；

Actor 目标网络：从经验回收池中采样下一个状态st＋1， 选择下一个最优动作at＋1， 并且定期将Actor 当前网络参数ω复制给ω′；

Critic 当前网络：实现价值网络参数θ的更新，计算当前Q值和目标Q值；

Critic 目标网络：负责协助计算目标Q值，并且定期将Critic 当前网络参数θ复制给θ′。

状态：假设在第t个调度周期时，系统的状态表示为st＝（st，1，st，2，…，st，n），其中st，i（1 ≤i≤n）表示第i个切片在第t个周期的网络状态。st，i有多个状态参数构成，其定义为st，i＝（xt，i，wt，i，dt，i，ut，i，vt，i，ct，i），其中

xt，i：在第t个调度周期，第i个切片的可用带宽；

wt，i：在第t个调度周期，业务请求的带宽需求；

dt，i：在第t个调度周期，第i个切片的平均往返时延；ut，j：在第t个调度周期，业务请求的时延要求；vt，i：在第t个调度周期，第i个切片的丢包率；ct，i：在第t个调度周期，业务请求的丢包率要求；

动作：智能体观测环境状态后，经过确定性策略返回一组概率向量，表示将该业务调度到某个切片的概率值，切片调度器选择最大概率值的切片进行业务分配，此即为强化学习算法的动作at。

奖励：智能体根据策略选择动作后，在下一个调度周期切片调度器执行该动作选择业务对应的切片，该周期结束时状态更新为下一个状态，同时将本次调度的奖励值rt交给智能体。

策略：本文采用深度强化学习的DDPG 算法，是确定性策略，执行该策略时，得到一个状态st， 智能体就会执行对应的动作at＝μ（st）。 具体来说，切片调度器的调度策略的执行过程可表示为根据当前环境状态的序列选择一系列对应的动作来执行切片调度。 在DDPG 算法中使用人工神经网络来表示策略，网络的输入是状态信息和业务信息，网络的输出则是调度动作。

2.2.3 奖励函数

本文设计的奖励函数如下

式中：0＜λ ＜1，0＜α ＜1，0＜β ＜1 表示权重，奖励函数的第一项代表切片可用带宽与业务的带宽需求的贴合程度，因为本文设计的奖励函数侧重于带宽需求，因此将二者的差值作为分母以提高其权重；奖励函数的第二项代表业务的时延要求与切片当前时延的贴合程度；奖励函数的第三项代表业务的丢包要求和切片当前丢包率的贴合程度。

2.3 算法框架及算法设计

2.3.1 基于深度强化学习的切片调度框架

本文采用人工神经网络表示调度的确定性策略和值函数的估值，将观测到的网络环境状态和业务感知端感知到的业务信息作为神经网络的输入，输出则是值函数的估值信息和一个概率向量，切片调度器选择概率最大的切片进行调度，视为调度动作。

具体的实现过程为：（1） 首先进行网络训练，感知端感知业务类型，得到业务对应的QoS 需求，切片调度器实时监测所有切片的网络状态，将业务和切片的信息作为DDPG 神经网络的初始状态，利用贪心策略选择概率值最大的切片进行调度，得到当前奖励值并更新下一个时刻的神经网络状态，不断训练直到模型收敛，学出较好的调度策略即根据奖励函数的反馈学到每个切片的带宽利用阈值，切片可用带宽高于阈值，则继续选择该切片传输业务，切片带宽低于阈值，则选择更高优先级的切片传输业务。 （2） 然后进行切片调度，使用训练得到的调度策略进行切片调度，并把每次调度的信息以（st，at，rt，st＋1，t） 的形式存入经验回收池，经过一定调度周期后将经验回收池中储存的数据按批次取出，继续训练网络，得到更好的调度策略，如此反复迭代，直到奖励函数值不再提升为止，得到最好的调度策略，整体框架如图2 所示。

图2 基于深度强化学习的网络切片调度算法框架

图2 的控制层实现切片的在线调度，切片调度器将观测到的网络状态和业务感知端感知到的业务信息st作为神经网络的输入，输出层使用softmax 函数，输出一组切片选择的概率向量，调度器选择最大概率的切片进行调度，输出动作at； 然后回报函数会反馈切片调度器本次调度的奖励值rt，同时环境状态转移到调度后的状态st＋1， 这些交互信息会被经验采集器以（st，at，rt，st＋1，t） 的形式保存在经验回收池中，供训练层使用。

图2 的训练层实现神经网络的训练，经验采集器按照规定好的批次大小将经验回收池中的调度信息取出，进行网络训练，更新网络的训练参数。

宽窄融合网络的状态变化时，训练得到的最优调度策略也需要不断变化。 在线调度部分将网络环境的动态变化信息存入经验回收池，训练层中由于网络环境的动态变化导致奖励函数降低或较大波动，DDPG 网络将根据最新的网络状态参数继续训练，直到奖励函数稳定，得到新网络状态下的最优调度策略。

2.3.2 深度强化学习算法

基于深度强化学习算法的DDPG 神经网络的输出有3 项：一个动作a＝α（s ｜θα），一个值函数项V（s ｜ θV） 和一个优势函数项A（s，a ｜ θA）， 其中α（s ｜θα） 表示状态s下的策略网络，θ表示网络参数。 因此神经网络训练得到的当前Q值可由值函数项和优势函数项相加得到，优势函数可以参数化为一个非线性状态特征的二次函数［10］，表达式如下

其中U（s ｜θU） 是关于状态的正定矩阵，可进行楚列斯基分解为

其中τ是学习速率（τ≪1），这种小幅度的“软更新”使得Critic 网络的训练更加稳定。

具体的DDPG 网络训练过程如图3 所示。

图3 DDPG 网络训练流程图

3 仿真实验结果与分析

本文的深度强化学习算法的实验环境是Python 3.6，Pytorch 1.5 配置；宽窄融合网络仿真环境主要由路由器、交换机、宽带移动链路、短波链路等组成，包括8 Mb／s、2 Mb／s、800 kb／s 和500 kp／s 等不同的宽窄无线链路，并在丢包率为0.5%以内随机丢弃报文。 实验共分为两步进行，第一步是切片构造实验，网络信息搜集组件得到切片构造所需要的基本信息，如：业务的QoS 需求信息、由实际网络拓扑图转化的网络拓扑有向图矩阵以及业务流量矩阵。 然后通过构造算法预划分路径，输出一个切片库，降低了实时构造切片的时间开销。 第二步是切片调度实验，针对复杂多变的网络环境，将业务感知端得到的业务信息和实时检测得到的切片状态信息作为神经网络的输入，利用深度强化学习算法训练得到在不同环境状态下的最佳调度策略，均衡网络负载，提高资源利用率的同时满足业务定制化传输的要求。

3.1 切片构造实验结果

业务QoS 需求表包括本文研究的7 种业务的优先级、带宽要求、时延要求、丢包要求等，如表1 所示，其中H 表示要求较高，M 表示要求中等，L 表示要求较低。

表1 业务QoS 需求表

实施QoS 切片构造算法后形成的切片拓扑如图4 所示。

图4 QoS 切片拓扑图

根据构造算法，可以将网络拓扑图大致划分成4 个切片链路，其中第一类链路适用于网络协议类和短信息业务，第二类链路适用于紧急信息业务，第三类链路适用于长信息业务，第四类链路适用于视频文件、管理信息和邮件业务。

3.2 切片调度实验结果与分析

本文设计如下实验，分别从QoS 满足率即业务是否进行定制化传输且没有时间浪费、调度业务传输完成时间、切片带宽平均利用率3 个方面比较本文采用的切片调度算法与对照算法的效果差异。 本文采用3 种对照算法：第一种算法是“尽力而为”调度算法，即先把业务全部调度到一个切片上去，切片负载过大后再调往另一条切片，以此类推；第二种算法是“专路专调”调度算法［8］，即每类业务一开始只能调度到其对应的切片链路，链路堵塞则业务进行等待；第三种算法是对业务采用动态重路由［12］的方式进行调度。

首先模拟网络低负载的情况，8 种业务每隔2 s传输3 轮，持续传输30 s。 然后模拟网络高负载的情况，8 种业务每隔2 s 传输6 轮，持续传输30 s。最终得到的QoS 业务满足率、切片带宽平均利用率、业务调度完成时间分别如图5、6、7 所示。

图5 QoS 业务满足率

图6 切片带宽平均利用率

由实验可以得出如下结论：（1） 4 种方法除了算法一，其余的QoS 业务满足率都很高，这是因为算法一总是尽力而为，并没有考虑到业务的定制化传输需求，算法二虽然专路专调，但是链路堵塞时就会浪费时间资源，没有很好地利用网络资源，算法三虽然能够动态重路由，但是低优先级的业务必须等待高优先级的业务探索路由后才能进行路由，因此这3 种方法的QoS 业务满足率低于本文方法。（2） 本文设计的网络切片调度算法可以使得切片间负载更加均衡，因为算法一和算法三都是先选择一条链路进行业务传输，链路堵塞时才会重新选择链路，因此并不能很好地均衡链路间的负载，算法二也是因为堵塞，造成了时间的浪费，影响了负载均衡的效果。 （3） 因为算法三需要动态划分业务路由，而本文的网络拓扑较为复杂，因此花费了更多时间在划分路由上；算法一和算法二因为一开始只选择一条链路，因此有链路拥塞造成的额外时间开销，由此可见本文设计的算法可以使得业务的调度完成时间更短。

图7 业务调度完成时间

4 结束语

本文通过对异构网络切片技术的研究，根据差异化的业务需求构造基于人工智能构建的网络切片，结合宽窄融合无线实时网络环境的状态，提供定制的网络资源对业务进行服务，实现了切片实例化。实验表明，本文设计的网络切片构造和调度算法在QoS 满足率、切片带宽平均利用率和业务调度完成时间上均有较大提升，均衡网络负载的同时提高了网络资源利用率。