论文标题
**中文标题：**可扩展调度在时间敏感网络中的应用：一种高效的流冲突检测方法
**英文标题：**Scalable Scheduling in Time-Sensitive Networking: An Efficient Stream Conflict Detection Method
作者信息
Lei Xu, Cailian Chen (Senior Member, IEEE), Yanzhou Zhang, Xin Li, Shouliang Wang, Qimin Xu (Member, IEEE), Xinping Guan (Fellow, IEEE)
论文出处
IEEE Transactions on Industrial Informatics, 2025
摘要
时间敏感网络（TSN）作为一种新兴的通信技术，能够为工业物联网（IIoT）中的实时和确定性交互提供支持。然而，由于计算复杂度高，大规模流的有效和及时调度仍然是一个重大挑战。本文通过调度可行性分析对给定路径的流集合进行预处理，避免无效搜索，并为流路由选择提供优化指导。为了加速潜在解决方案的可行性验证，提出了一种基于流分组和相关性分析的高效流冲突检测方法，以压缩检测空间。结合预处理和高效冲突检测，本文开发了一种可扩展调度算法，通过增量调度合成提高可扩展性，同时确保所有链路的低时隙占用率。评估结果表明，与现有调度方法相比，所提出的算法显著减少了合成时间，并实现了所有链路的低时隙占用率。
引言
工业物联网（IIoT）的出现标志着信息技术与制造业的深度融合，推动了工业4.0和智能制造的发展。随着对实时性和确定性通信需求的增加，IEEE时间敏感网络（TSN）工作组正在开发基于IEEE 802.1以太网的一系列TSN标准。调度机制作为TSN技术的关键部分，近年来得到了广泛研究。由于不同的传输需求，基于门控列表（GCL）的调度整形器主要分为两类：时间感知整形器（TAS）和循环排队与转发（CQF）整形器。然而，现有研究由于计算复杂度高，仅适用于中小型IIoT场景。本文提出了一种可扩展的调度方案，通过调度可行性分析和高效的流冲突检测方法解决大规模和复杂IIoT场景下的可扩展性限制问题。
系统模型与问题描述
网络模型
TSN网络由支持TSN的节点和链路组成，建模为有向图G = {V, ξ}。每个周期性流由周期、路由路径、截止时间和帧大小等属性描述。所有流的路由路径在调度前已计算并给定。
调度模型
本文采用基于CQF的调度机制，通过配置TSN交换机的Ping-Pong队列时间门，将链路的时间资源划分为时隙。每个流根据路由路径逐时隙传输。为了避免多个流在同一时隙汇聚，引入了流的注入时间偏移作为额外的调度变量。调度问题的目标是最大化可调度性，即在相同的网络条件下调度更多流。
问题描述
优化目标是最小化所有链路的最大时隙占用率，从而提高可调度性。由于该问题等价于NP难问题，本文提出了一种可扩展调度方案，包括理论分析和算法设计。
理论分析
调度可行性分析
本文推导出一个必要的调度可行性条件，用于在应用调度算法之前进行初步筛选，避免无效搜索和计算开销。该条件基于流集合的最大时隙占用率和链路容量的约束。
流冲突检测
流冲突检测是CQF调度中的关键环节。本文提出了一种基于流分组和周期相关性分析的高效冲突检测方法，将冲突检测对象从流/帧级别提升到流组级别，显著降低了计算复杂度。通过分析流组之间的周期和链路偏移关系，本文提出了三种情况下的冲突检测定理：相同周期的流组、周期具有倍数关系的流组以及一般关系的流组。
算法设计
快速计算时隙占用率（FCSO）算法
基于理论分析，本文提出了FCSO算法，用于快速计算所有链路的最大时隙占用率，从而验证潜在解决方案的可行性。该算法通过流分组和相关性分析，将计算复杂度降低到线性复杂度O(N)。
基于高效冲突检测的可扩展调度（ESS）算法
ESS算法结合了调度可行性分析和FCSO算法，通过增量调度合成生成可行的网络调度。该算法优化了流的调度顺序和链路偏移量，以实现低时隙占用率，从而在相同的网络条件下容纳更多流。算法的时间复杂度为O(c ∗ N + N ∗ log N)，显著优于现有方法。
性能评估
仿真设置
本文模拟了线性、环形和梯形三种网络拓扑结构，流集合参数涵盖不同的周期和帧大小。仿真在Intel Core i7-9700 CPU和16GB RAM的环境下运行，使用Python编程语言。
可扩展性比较
ESS算法在大规模流调度场景下表现出显著的可扩展性优势。与现有的基于帧和流的冲突检测方法相比，ESS算法的合成时间显著降低，即使在流数量达到1200时，合成时间仍小于1秒。
时隙占用率比较
ESS算法在时隙占用率方面表现优异，仅略高于FLJ方法，但显著优于其他方法。这表明ESS算法在牺牲少量可调度性的情况下，换取了显著的可扩展性提升。
网络拓扑影响
不同网络拓扑对ESS算法的性能有一定影响。梯形拓扑由于链路数量更多，流共享链路的密度更低，因此在时隙占用率和合成时间方面表现最佳。
结论
本文针对大规模流调度问题，提出了一种基于高效冲突检测的可扩展调度算法。通过调度可行性分析和流分组技术，ESS算法在保持低时隙占用率的同时，显著提高了调度的可扩展性。仿真结果表明，该算法在复杂和大规模场景下具有优越的性能，为TSN网络中的实时和确定性通信提供了有效的调度解决方案。
