paper radar

Solving No-wait Scheduling for Time-Sensitive Networks with Daisy-Chain Topology

求解菊花链拓扑 TSN 的无等待调度问题

Qian Li, Henan Liu, Heng Liu, Yuyi Wang · 2026-02-27

调度算法工业网络

中文摘要

这篇适合解释“为什么拓扑约束能让调度问题变简单”：一般 TSN 调度很难，但某些工业常见拓扑可以找到结构化解法。

这篇论文聚焦菊花链拓扑中的 TSN 无等待调度。TSN 标准并不规定如何计算数据流调度表，因此调度求解仍是开放问题。作者把菊花链无等待调度转化为带颜色限制的区间图着色问题，并证明在该拓扑下可以用关于流数量和网络规模的多项式时间算法求得最优调度。评估显示算法可以扩展到数万条流。

TSN 无等待调度通常复杂度高，工程上很难在大规模流数量下快速求最优解。

论文抓住菊花链拓扑的结构，把多跳无等待约束变成区间图上的着色问题。这个思路对新手有启发：调度算法不是只有暴力求解，拓扑特征本身就是可利用的信息。

如果你的现场网络接近线型/菊花链，这类论文比泛化调度算法更值得看。它的问题是适用范围明确，不应被误解为解决所有拓扑的 TSN 调度。