基于遗传算法的时间敏感网络调度方法

陆以勤 黄成海 陈嘉睿 王海瀚 覃健诚 方婷

（1.华南理工大学 电子与信息学院，广东 广州 510640；2.华南理工大学 信息网络工程研究中心，广东 广州 510640；3.华南理工大学 微电子学院，广东 广州 511442）

随着现代网络（如智能驾驶车载网、工业互联网和5G通信等场景）的快速发展，越来越多的数据采集节点和计算节点导致网络设计复杂化和通信链路上大量的数据负载。目前，虽然以太网具备了高带宽的要求以及各种专用设备的无缝连接，但并不提供实时的时间敏感功能，如低抖动、低网络延时以及高效带宽分配等功能。而低延时的实时确定性传输功能是网络物理系统必不可少的，现存的工业和车载网络由于不能互通而增加了网络结构的复杂性。IEEE802.1 工作组开发的TSN（时间敏感网络）标准协议［1］作为涵盖确定性网络不同方面的标准，包括提高可靠性、延迟控制、时间同步和资源管理，希望以统一的网络结构解决现代网络中关键型任务应用程序的严格时间限制问题。

时间敏感网络的核心基本组件包括时间同步、流量调度、流量整形、路由策略以及冗余预留和容错机制等。其中，TSN流量调度机制定义了门控列表（GCL）表示队列门在每个时刻的状态，要求数据链路在严格的时间同步条件下将时间划分为时隙，通过GCL让时间敏感流的每一帧都在计划时隙内进行无争用通信。求解合成GCL要求调度算法根据不同网络拓扑以及流量模型计算出符合调度约束的调度方案，这类似装箱问题［2］，是NP难问题，尤其是当需要考虑到流的路由和流量联合调度的多跳网络时。当前求解流量调度的数学优化方法主要有可满足性模理论（SMT）和优化模理论（OMT）、启发式算法和元启发式算法、整数线性规划（ILP）。文献［3］是最早在时间触发以太网（TTE）中，针对多跳网络利用SMT求解器来综合路由和调度的研究之一；而在TSN离线调度规划中，文献［4］在采用SMT寻找满足调度和时间约束的解决方案的同时，使用OMT指定最小化所使用队列的数量作为优化目标；一种基于时间感知整形器（TAS）的实时自适应门控调度方案在文献［5］中提出，它将调度问题表述为布尔可满足性问题（SAT），并提出采用基于现场可编程门阵列（FPGA）的求解器实现运行时快速计算。它们是TSN寻找可行GCL的主要研究方向，但缺点是具有较高的算法复杂度，特别是当它们应用于具有路由规划和调度综合的大规模网络模型时。与前面的求解方法相比，文献［6］和［7］分别采用启发式列表调度（HLS）和元启发式遗传算法，基于无等待方法［8］进行路由和调度约束联合调度。使用同为元启发式算法的禁忌搜索进行无等待的时间敏感流调度也在文献［8］中提出。他们都采用具有更低算法复杂度的流量调度方法，但大都是基于无等待的方法进行调度计算，求解空间有所减小，实际应用效率低。

本研究建立在GCL 调度部署的网络管理基础上，其相关的协议主要有IEEE 802.1Qbv增强型流量调度和以IEEE 802.1Qcc为背景的集中管理机制。TSN 中的网络管理需要针对GCL 进行部署，因此IEEE 802.1Qbv 标准［9］描述了以时分多址技术（TDMA）为基本原理的TAS。GCL除了要保证数据无争用传输之外，还需要实现关键流量的低延时零抖动传输以及遵从时间敏感网络的调度约束。文献［4］基于TSN关键参数进行离线推导约束，以此保证关键通信流的低抖动和端到端确定时延，但是这种方法忽略了由于多个流选择相同路径带来的负载不平衡。而考虑流的各种路径来确定优化调度方案极其困难，因此低复杂度算法对其十分重要，如贪婪随机自适应搜索算法［10］、遗传算法［11］等调度方法，均为寻求更低复杂度的GCL计算方案。

此外，IEEE 802.1Qbv 的另一个重要机制是保护带，其在队列关闭之前一定时间内限制数据包的传输，以防止与传输槽关联的流量延迟分配给后续传输窗口导致关键流的数据传输未完成而延迟。但是保护带是一个不能传输流量的时间间隔，存在带宽浪费的现象，因此有关文献［12］采用基于大小的队列（SBQ）提高带宽利用率。在运行时重构TAS 方面，文献［13］中提出了一种包含自适应带宽共享（ABS）和自适应槽位窗口（ASW）机制。文献［14］提出了一种方法，它可以根据需求动态地重新配置具有时间感知能力的整形器，该方法采用TSN集中式网络和分布式用户混合模型进行控制。上述文献均以较高复杂度的算法进行精确解的计算，忽视了采用牺牲部分精度降低算法复杂度的元启发式算法。

针对上述TSN调度中存在的问题，本文设计了一种性能更优的路由优化遗传算法Routing-GA。Routing-GA 综合考虑算法的收敛速度、适应度函数设计、实时路由约束和可扩展性等因素，通过设计针对TSN流量调度问题的遗传算法编码、交叉和变异机制，在严格遵守TSN调度约束的同时解决现存大规模路由与约束联合调度问题。本文第1节简要介绍时间敏感网络相关机制；第2节详述调度系统以及调度约束公式化表述；第3节提出低复杂度的Routing-GA，详述流状态编码的算法结构设计及建模，并分析相对于传统遗传算法的种群初始化和交叉变异过程的优化；最后在第4节验证算法的相关性能。

1 时间敏感网络

TSN 由一系列IEEE 802.1Q［1］标准提供支持，目的是确保满足时间要求，但实际的具体功能特性依赖于应用的需求。本文主要研究TSN中基于GCL调度部署的网络管理，其相关的协议主要有IEEE 802.1Qbv增强型流量调度和以IEEE 802.1Qcc为背景的集中管理机制。另外，时间敏感网络的调度约束也是关注的重点，下文会对他们进行简要介绍。

1.1 时间感知整形器

本文采用TAS 结构框图，具体如图1 所示。时间同步技术的精度和效率直接影响TAS 的功能和TSN 的性能，因此TAS 设备需要IEEE 802.1AS 提供时间同步工作机制支持。时间感知整形器会划分时隙，并将已定义的8个分组队列绑定设备对应的传输端口。接着在对应队列的端口传输中，为了保证无争用数据传输，即避免对来自其他队列的数据包的干扰，802.1Qbv 引入了门控机制，相当于给每个队列出口安装了开关，并且为不同队列分配不重叠的传输时隙。当门状态为1时，队列数据从对应端口中输出；相反地，当门状态变为0时，数据停止从队列中输出。而门在对应时刻的开启和关闭由GCL决定，TAS会根据门控周期以及GCL进行周期重复的控制。

图1 时间感知整形器结构框图［14］Fig.1 Structure of time-aware shaper［14］

本文提出的Routing-GA 支持由IEEE 802.1Qbv定义的流量调度增强部分功能，通过输出GCL来控制设备端口在指定的时隙内选择所输出的队列。如图1（引用文献［14］的结构图）中GCL 所示，T3时刻“1000 0000”表示队列门控0 打开，数据从端口传输，队列门控1-7关闭。本文提出的调度方法支持由IEEE 802.1Qbv流量调度增强功能。

1.2 集中网络配置和集中用户配置

为了对复杂的TSN功能进行配置，以保证预期的服务质量（QoS），IEEE 802.1Qcc 定义的集中用户配置（CUC）和支持NETCONF 或RESTCONF 协议的集中网络配置（CNC）为本文提供集中管理机制支持，类似软件定义网络（SDN）的方式［15］，如图2（引用文献［16］的框架图）所示的集中式管理框架。CUC 给关键应用程序提供时间敏感流的注册服务，收集流的周期、长度、发送和接收节点、最大时延等信息，并通过用户网络接口（UNI）与CNC 进行新设备注册交换信息。CNC负责计算和配置GCL，当在大规模的网络模型中进行动态调度时，要求其核心的调度方案计算方法具有较低的时间复杂度以应对严格的实时要求。

图2 集中管理框架［16］Fig.2 Centralized management framework［16］

集中管理还需要能保证流确定性的TSN 交换机，要求具备支持IEEE 802.1Qbv 门控制机制、IEEE 802.1AS 时间同步协议以及NETCONF［17］或者OPC-UA 统一架构等能力。集中式管理机制对比分布式方法在TSN流量或网络配置发生变化时具有更高的灵活性和效率，因为集中管理的计算和部署GCL或者自动配置机制都必须要求获得流和整个网络的信息。

2 时间敏感流量调度问题

2.1 时间敏感流量调度系统

在前面所提的时间感知整形器以及集中式配置机制的基础上，本文提出TSN调度系统。可以认为TSN流量调度是一个NP难问题［4］，时间敏感的流信息、端设备和交换机处理能力以及路由拓扑由基于IEEE802.1Qcc标准的TSN控制器集中采集。如图3所示，主要对输入网络拓扑节点能力以及流信息进行处理，可以采用精确求解或启发式算法等方法，计算输出时间敏感流的门控列表。

图3 时间敏感流量调度处理过程Fig.3 Time-sensitive traffic scheduling process

TSN是建立在全双工的以太网基础上的，链路[na，nb]可由一个三元组定义：

其分别代表链路带宽、传播速率以及出端口队列数。

时间敏感流可以由一个六元组定义：

其分别代表发送节点、接收节点、最大所能容忍的抖动时延、最大端到端时延、周期以及每周期所发送的数据量。

最后输出的结果可以定义三元组表示：

流量调度算法负责保证计算得出的门控列表方案在满足第1节调度约束的前提下，所有实例帧无冲突地传输，并尽可能优化端到端时延等传输指标。

2.2 时间敏感流量调度约束

为保证计算出来的GCL满足TSN的确定性低时延要求，即时间敏感流在其传输周期内进行无链路争用的超低延时传输，调度算法需要满足以下的约束条件。

（1）帧约束。针对每一段链路[na，nb]，保证对于每个帧必须在其对应周期内完成传输，即在一个周期内的最迟开始传输时间小于的周期减去对应链路所需的传输时长。数学表达如下：

（2）链路约束。对于任意两个需要通过同一段链路[na，nb]的帧和，要求其在超周期Thyper时域上没有重合，也就是帧的传输需要提供其独占链路的时间。

α、β为整数，且，Thyper为所有流周期的最小公倍数，称为超周期。Tx、Ty分别为流x和流y的周期。

（3）流传输约束。同一个帧在通过其路径上的不同链路段时，需要按照链路段的物理连接次序依次进行传输。也就是帧fij开始在[nx′，nb]链路段传输的时间要求大于fij在前一段链路[na，nx′]传输结束的时间。而fij在对应链路段[na，nx′]传输结束的时间等于fij在该链路段的开始传输时间Φij加上帧传输时长tij、处理时长tp，ax′、时钟的最大误差tsyn。具体如下所示：

（4）端到端约束。该约束表示对于每一个流Fi的最大端到端时延小于其最大能容忍的端到端时延De2e，i，也就是该流的最后一帧到达接收端的时间与第1帧开始传输的时间之差小于De2e，i：

式中，LMTU为一个MTU 的数据量，为流i每次发送的帧数。

（5）帧隔离约束。当同个队列的帧同时到达交换机节点的时候会出现帧交织，或者传输途中出现帧缺失而导致调度的时隙出现偏差。因为TSN调度需要引入帧隔离约束以避免上述情况，所以帧隔离要求同一个队列在同一时刻只能存储一条流的帧，也就是需要当一个帧离开队列时，另外一个帧才可以进入队列，但是如果两个帧分别在不同的队列当中就没有此约束：

（6）抖动约束。实际与理想状态的传输以及处理总时延差不能大于其所能容忍的最大抖动时延：

其中，Di为理想状态下流i从发送端到接收端前一个节点之前的总传输、传播和处理时延，Wi为理想状态下流i的总等待时延。

2.3 时间敏感流量路由约束

时间敏感网络流量调度中，路由约束指的是网络流量在传输过程中必须满足的约束条件。这些约束条件通常包括以下几个方面。

（1）拓扑约束。每个实例帧在网络中传输的节点必须在拓扑中有连接。针对每个帧fij的传输路由中的任意节点na，其下一个目标节点ηija等于nb的条件是[na，nb]∈ri。即

（2）无环约束。指定流的传输路径不能形成环路，以避免数据包重复传输和死锁等问题。可以等价为对于每个帧fij传输路由中任意两个节点na、nb的下一个目标节点ηija、ηijb不相等，具体而言，可以通过以下公式表达无环约束：

（3）路由约束。该约束确保从源节点到终节点找到完整且连接的路径。假设帧fij在节点na时的下一个目标节点ηija为nb，且nb不是终节点，那么必定存在与nb相连的节点及链路[nb，nx]：

（4）链路负载约束。保证交换机间传输时间敏感流所占用的链路负载不会小于某个阈值，防止带宽资源被过度占用，从而导致网络拥塞和性能下降：

3 基于遗传算法的时间敏感流量调度算法

本文提出一种模拟生物进化的随机搜索算法Routing-GA用于计算调度方案。遗传算法在文献［7］的工作中被证实可以很好地解决时间敏感网络中的调度问题，但是其难点在于遗传算法问题建模。这需要在同时考虑调度的性能和质量情况下，为不同的复杂问题找到最优或近似最优解。

3.1 遗传算法的实现

本文根据时间敏感网络调度问题的特性，设计对应的编码、群体初始化、交叉、变异，以最小端到端时延为优化目标：

式中，C为流的总数量。严格遵守TSN 中路由和调度约束，寻找近似最优解。Routing-GA的个体代表一个调度方案，也可以体现为一个超周期内的GCL门控表。而该个体是由一系列基因组成的，每个基因对应每个时间敏感任务流当前所处的节点位置。根据调度约束要求，每个个体可以计算出一个描述个体素质的适应度值，该适应度体现为端到端时延。同时，为了创造新的个体，Routing-GA提供不依赖第三方库的交叉、变异方法来进行配对和进化种群中的个体。并且为了优化种群，采用基于适应度的评价和替换方法，使子代中适应度较好的个体取代父代中的劣势个体。

具体的生成流程如图4所示。图中实线为传统GA 的迭代流程，虚线为本文提出的路由优化Routing-GA。具体步骤如下：

图4 遗传算法实现流程图Fig.4 Flow chart of genetic algorithm

步骤1设置遗传算法的参数，参数包含种群数量、交叉概率、变异概率以及最大迭代次数。另外以端到端时延为适应度值，通过1.2节中集中式网络管理机制进行流量以及网络拓扑信息采集。每当流量或者网络拓扑发生变化时，通过该管理机制能及时更新算法相关参数，并调整个体基因以保证算法的正常迭代。

步骤2进行种群初始化，采用随机和路由优化组合方式生成初始种群。

步骤3对群体进行变异和交叉操作，并按照适应度值的优胜劣汰原则筛选种群中的个体。

步骤4经过一定次数的迭代后，输出最小端到端时延的调度方案。图5 所示为按照9 节点网格拓扑随机5 条时间敏感流调度结果的时间窗示例。图例中f1 包括f1.0-f1.1 所有超周期内的流，以此类推。可根据调度规模以及求解时间要求适当调整算法的基本参数，以得到最理想解。

图5 调度时间窗示例Fig.5 An example of schedule window

基于上述流程，本文所提出的调度方法采用的初始化、交叉和变异算子能有效加速算法的收敛过程，并在一定的时间内找到近最优解。因此，该方案具有低算法复杂度、高性能、高灵活性等优点。Routing-GA的核心机制将在如下详述。

3.2 基因编码

如图6 所示，本文定义TSN 时间表在染色体中的编码为一个二维数组。数组的横坐标的作用是记录流的单步前进的次序，例如当从τi′到τi′+1时，F0到Fm中只变化其中一个流的位置，代表其中一条流的某一步骤前进一步。数组的纵坐标为流的编号，记为Fi，代表第i条流。而二维数组上的元素代表的是Fi流在所有流总步数中第τi′步所处的节点位置，记为si，i′。通过这样一个二维数组记录个体，把每个步骤次序中各个流所在的节点位置作为基因，这样既可以充分记录个体路由和流约束的联合调度方案，又能够降低适应度计算函数的时间复杂度。计算适应度函数时仅需按照个体基因逐步计算对应满足TSN调度约束的可行时间窗，并采用贪心算法计算出最早开始传输的时间。假设约束计算与现有研究的时间复杂度相同且忽略不计，则本文采用贪心算法计算填充时间窗的时间复杂度为O（n）。另外，该编码方式在遗传算法的核心步骤交叉、变异中约束限制较小，操作方便，降低了交叉和变异的时间复杂度。在本例中，算法仅假设每个流都有一个接收端。但在多播流的情况下，只需将流拆分为多个以同个节点为起点但不同节点为终点的流分开单独进行基因的编码即可。

图6 编码方式Fig.6 Encoding method

基于上述的基因编码方式，个体对应的适应度函数可以直接体现为调度方案的端到端时延，即算法采取一个个体基因对应一个调度方案，因此算法在优化迭代的过程中任意一个个体均是可行解，能准确且实时地反映出流量调度过程中的时延。当输入时间敏感流或网络拓扑发生变化时，对应生成的基因编码也会随之变化，不影响算法的迭代搜索功能。另外，采用该方式仅需起始节点和终止节点就可根据网络拓扑进行调度方案的编码生成，可以应用于TSN流量调度中分布式遗传算法的计算，具有高拓展性。与现有在TSN领域的遗传算法相比，它还可以不受路由长度影响，即不同长度的个体基因仍可以比较方便地进行交叉和变异操作。

3.3 种群初始化

种群的初始化对遗传算法全局搜索效率和优化收敛速度具有十分重要的影响，而基于遗传算法的车间调度方法［18］在许多工作中被证明是很好的，因此参考文献［11］中采用的车间调度算法，本文种群的初始化采用随机和路由优化联合生成的方法，在符合TSN约束要求的条件下生成可以保证初始群体的多样性和合法性。

具体的初始化流程如图7所示，步骤如下。

图7 初始化过程Fig.7 Initialization procedure

步骤1随机初始化根据每一个流的发送端和接收端遍历两点之间的所有可行路由。

步骤2计算每个流所选路由的笛卡尔积，也就是各个流选择路由的组合。

步骤3从中选出算法所需初始化的种群数量即可，无需完全遍历笛卡尔积。验证生成的个体是否符合约束，若符合则生成对应的个体基因，否则丢弃。

路由优化初始化会对每个链路中的负载数据量进行累加，选出最大负载链路负载值并与路由总长度进行加权和，从中选择最小的个体作为种群的初始化成员：

式中，L(ri)为ri的长度，为节点na与nb间的传输速率。

随机和路由优化组合初始化方式在保证种群的随机多样同时，确保种群中具有较好适应度的个体作为收敛的参考方向，减少无效搜索的几率，大大提高了算法的迭代效率。

3.4 交叉

遗传算法中的交叉运算是借鉴达尔文的进化论以及孟德尔的遗传定律的原理，也是控制搜索的核心支撑之一。按照前面所提出的编码方式，本文开发出对应的随机交叉和路由优化的组合交叉互换机制。由于TSN 流量调度问题的复杂性，不同个体的基因长度可能不同，这是因为每个流可选的路由之间长度可能不同，本文提出的编码方式可对任意满足条件的基因进行交叉，无需额外对不同长度的基因进行处理，提高了交叉机制的效率，具体步骤如下。

步骤1根据预先设置的交叉几率判断对应个体是否发生交叉。

步骤2若发生交叉，则交叉机制会进行比较，求出两个父代个体中基因的交集，并随机选出其中的一段基因作为交叉的参考基因。如图8所示，假设ai，i′、bi，i′分别是父代A 和B 的基因元素，交叉开始时会查找父代中相同基因段，如图8中虚线框所示，ai，i′=bi，i′=si，i′。这个基因代表的是父母中有完全相同的一个时刻，这个时刻父母个体的所有时间敏感流对应其所在节点的位置相同。

图8 基因交叉Fig.8 Gene crossing

步骤3如图8 中所示的交换示例，算法将父母个体中以此基因作为分界的前后所有基因进行交叉互换。

步骤4判断交叉后子代基因的路由是否使链路最大数据负载量增加以及路由长度增加，若增加则放弃对应子代；否则保留该子代并添加到群体当中。

步骤5交换操作完成之后判断个体基因是否重复出现和是否符合TSN流量调度约束，若出现以上情况则舍弃该新个体基因。

本文提出的路由优化的交叉机制在随机交叉的基础上约束子代基因的链路负载均衡度。该操作降低了交叉机制搜索无效解的几率，提高了算法求解效率。本文所提出的交换机制不依赖第三方的交叉算子库，并且解决了遗传算法在TSN流量调度领域由于基因长度不同而引起的交叉算法复杂度较高等问题。交叉之后既可以保证了个体的可行性，又提高了交叉算法的搜索效率。

3.5 变异

为了避免局部最优收敛，遗传算法的变异机制可以使某个染色体段突变，从而产生新的个体。这有助于搜索最优解的时候跳出局部最优解，提供仅靠交叉无法搜索到的解，达到全局最优或似最优。

图9 所示是本文开发的变异示例。具体步骤如下：

图9 基因变异Fig.9 Gene mutation

步骤1根据预设定的变异几率，判断个体是否发生基因变异；

步骤2当发生变异时，在发生变异的个体中随机选出变异起始和变异终止基因段，图9中虚线框为选取基因段中一条流的变异起始基因和变异终止基因；

步骤3根据基因段中每个流的变异起始节点和变异终止节点重新随机选择一条对应的路由进行替换，生成新的基因段，如图9，虚线框内及其之间的新基因取代其原基因生成变异基因；

步骤4判断基因是否符合约束，最后再生成新的个体。

本文提出的路由优化变异方法与传统遗传算法相比，主要区别在于变异所选择的新路由在不增加路由长度的基础上，遵从不增加链路最大数据负载量的原则进行变异，这不仅保证了变异机制能有效跳出局部最优解，并且约束变异的方向，减少了无效搜索的概率，提高了算法进化率。此过程的变异操作在染色体中引入了一个大小随机的变化，既可以产生较大的基因段变异，也可以只引起最小3个基因长度的变异。

4 仿真设计与结果分析

4.1 仿真设计

算法实验采用Python 实现，运行在配备3.7 GHz AMD Ryzen 7 八核CPU 和64 GB 内存的计算机上。本文实验求解输入不同数量时间敏感流条件下的调度问题。实验遗传算法基本参数设置如下：种群的个体数量为30，突变概率和交叉概率分别为0.1 和0.8，迭代的最大次数为200。图10 为实验所用的网格拓扑，本文主要为了评估算法联合路由和TSN约束调度时算法的收敛能力、求解质量和速度，而网格拓扑在连通性上具有较好的代表性，为每条时间敏感流提供了更多的路由可能，因此实验采用网格拓扑来评估联合路由和约束调度的性能。每个网格由9个交换机组成，而每个交换机连接3个端系统设备，链路上的数据传输速度假设为125 byte/μs。在不同的调度规模问题上进行了实验，设置不同数量、周期和大小的流以及迭代次数，目的是为了验证算法应对不同规模问题的有效性，同时评估求解算法性能以及灵活性。

图10 最优解分布对比Fig.10 Distribution of optimal solution

仿真实验随机生成不同周期及长度的时间敏感流，如表1所示。其中生成的流周期主要为500 μs、750 μs 以及1 500 μs，目的是为了设置超周期以及GCL周期为1 500 μs，流大小在350 byte到3 350 byte之间随机产生，流的发送端和接收端从27 个端系统中随机均匀选择，使执行传输任务的收发节点均匀分配到整个拓扑的端系统。

表1 仿真业务流设置Table 1 Simulate service flow setting

实验通过XML 文件将流和拓扑信息输入调度器，并采用一个基于Web的交互式用户界面来显示模型和解决方案，包括路由图和时间表。流信息主要包括流的周期和长度、流对应的发送端和接收端以及最大可容忍时延；拓扑信息包括端系统和交换机处理能力、链路传输速率以及拓扑情况。本文主要对比传统遗传算法（未加入优化机制的方法）与Routing-GA的静态离线调度性能，其主要以端到端时延作为优化目标。

4.2 仿真结果分析

表2 为传统GA 和Routing-GA 分别进行10 次仿真实验得出的端到端时延及其进化率。可以看出本文设计的Routing-GA可以有效减少时间敏感流的端到端时延；与传统GA 相比，Routing-GA 具有更低的端到端时延和更高的进化率，并且在相同的条件下随着调度的时间敏感流数量增加进化率也有明显的提高，最高可达到24.42%。这里需要注意的是，调度50 条流时进化率发生下降是因为达到近最优解所需的迭代次数超出了200，但仍能够达到平均10%以上。这说明Routing-GA的优势随着调度规模扩大而更加显著。

表2 端到端时延对比实验结果Table 2 End-to-end delay comparison experimental results

图11所示为传统GA与Routing-GA的端到端时延进化迭代对比曲线。在9个交换机节点的网格拓扑图中调度50 条流时，可以看出传统GA 从第1 个可行解到近最优解时间敏感流的端到端时延从8 076 μs 降低到6 814 μs，Routing-GA 从6 488 μs 降低到4 757 μs，算法均有效地减少了TSN流量调度中的端到端时延。Routing-GA进化停滞的代数不超过5，而传统GA进化停滞状态最长可达到20代，可以看出Routing-GA中交叉、变异方法能有效解决TSN流量调度中的进化停滞问题，有效跳出局部最优状态，使端到端时延整体上保持逐渐缩小的趋势。另外，第1个可行解最短可以在560.75 ms内找到。

图11 端到端时延进化迭代对比曲线Fig.11 Evolution iteration comparison curve of end-to-end time delay

设置10 组实验组，每组随机生成40 条流，输入两种算法中分别迭代200次所得到的最优解情况如图12所示。可以看出，传统GA的结果离散程度比Routing-GA更大，这是由于Routing-GA的初始化以及交叉变异策略具有更好的稳定性。Routing-GA最优解情况普遍比传统GA 更加优秀，这是因为在相同的迭代次数下Routing-GA的初始化策略提供了更好的初始解，并且在优化的交叉变异策略下向最优解迭代的速度也同步提高。

图12 最优解分布对比Fig.12 Comparison of optimal solution distribution

实验对比采用传统GA 和Routing-GA 的调度方法，图13 所示为不同时间敏感流数量（20、30、40、50 条流）算例下的算法平均运行时间结果。可以看出经过交叉变异过程的优化，Routing-GA的每次迭代所需计算时间平均仅为传统GA 计算时间的12%。这表明Routing-GA可以有效减少单次迭代中所需的计算时间。另外，随着时间敏感流数量增加，传统GA 单次迭代所需计算时间增长由30%增加到83%，而Routing-GA平均增长为45%。这说明Routing-GA能有效减少大规模调度计算时间。

图13 算法单次迭代运行时间Fig.13 Running time of a single iteration of algorithm

5 结论

时间敏感网络是当今和未来网络应用的主要需求之一，其中包括无人驾驶、VR 技术以及5G/6G移动设备。本文研究了如何通过遗传算法解决TSN流量调度中复杂的路由和约束联合调度优化问题；提出一套编码方案以优化求解速度，通过交叉变异以找到一个接近最优的调度方案，并且与传统GA进行实验对比。实验结果表明Routing-GA相较于传统GA 具有更优的性能，且能够有效解决现存大规模路由与约束联合调度复杂问题，其简单且高效的问题建模和迭代机制为实际的流量调度应用提供了可行的参考方案。该方案在满足时延确定性要求的前提下具有灵活性高、计算速率快的优点，以上结论通过计算机仿真得到了验证。

未来的工作将更多地关注处理动态变化时间敏感流的方法，该方法能够根据每次新增或减少时间敏感流的数量，实现有效的局部调度计算；另外，可以考虑采用软硬件协同调度的方法优化调度性能，其中用硬件处理动态变化的局部调度计算、软件实现全局的调度计算。