面向集中式 TSN 流调度的目标保持并行加速
《Computer Communications》:Objective-preserving parallel acceleration for centralized TSN flow scheduling
【字体:
大
中
小
】
时间:2026年10月21日
来源:Computer Communications 4.2
编辑推荐:
**摘要**
本文提出了一种面向集中式时间敏感网络(TSN)流调度的目标保持型并行加速框架。所谓"目标保持",是指在保留底层调度器原始目标函数的前提下进行加速,而并行化策略本身与具体的目标函数无关。该方法不重新设计调度目标,而是作为求解器端的封装层,可与现有的增量式调度器集
**摘要**本文提出了一种面向集中式时间敏感网络(TSN)流调度的目标保持型并行加速框架。所谓"目标保持",是指在保留底层调度器原始目标函数的前提下进行加速,而并行化策略本身与具体的目标函数无关。该方法不重新设计调度目标,而是作为求解器端的封装层,可与现有的增量式调度器集成。我们通过冲突图分析了调度中的时空耦合关系,以此论证将调度问题分解为可并行子问题的可行性。基于这一观察,我们将冲突图划分为若干可并行处理的子问题,在保持底层调度器所定义原始优化目标的同时并行执行调度。我们在多种拓扑和流量设置下,将该方法与具有代表性的增量式基线进行了对比评测。每个实验设置均独立重复五次运行,并以平均值作为报告结果。结果表明,该方法在运行时间上取得了显著降低,同时通过成功率、链路利用率和端到端时延等指标评估了调度质量。总体而言,所提方法为提升集中式控制器中TSN调度效率提供了一种实用且与具体目标无关的途径。---**引言**时间敏感网络(TSN)日益被视为工业自动化、汽车及控制系统中确定性通信的关键使能技术。这些领域对时延、抖动和可靠性约束有着严格要求。流调度是确保各类TSN网络中端到端服务质量(QoS)的核心环节。普通的 shortest-path 计算可在多项式时间内求解。然而,额外的约束条件和耦合的调度决策会使路由相关问题在计算上更加困难。例如,带有多个可加性约束的QoS路由[1]以及具有固定包路径和无冲突注入时刻选择的无缓冲直接路由[2]已被证明是NP难的。在TSN中,路由和传输时间分配必须满足链路容量和截止时间约束。Yang等人提出了改进的Multi-CQF模型,并证明了其中时间区间分配优化问题的NP难性[3]。近期的TSN规划研究将路由、调度顺序和传输时间联合考虑[4],通过耦合的空间和时间决策扩大了搜索空间。Falk等人的整数线性规划研究展示了由此产生的计算负担和实际可扩展性限制[5]。因此,随着网络规模和流量负载的增加,需要高效的优化和启发式方法来在可控计算时间内获得可行调度。为此,各种优化和启发式策略应运而生。早期工作探索了增量式调度[6]、稳定性感知建模[7]和负载均衡MIP模型[8],随后发展了在线优化[9]、多路径路由[10]和强化学习[11]。针对时间触发流[12]和车载网络[13]的启发式方法进一步表明,实用方案可以在可接受的求解时间内实现高利用率。与此同时,基于CQF(循环排队与转发)的调度也日益受到关注,相关研究提出了联合路由与调度算法[14]、保护带与偏移配置[15]以及注入时间规划[16],以应对同步和周期对齐方面的挑战。近期,可扩展调度成为解决大规模工业TSN中集中式和精确方法局限性的热门方向。在线可扩展框架[17]、超流图调度(GH2)[18]和流图分布式方案(GFD)[19]在效率、可调度性和资源利用率方面取得了显著提升。互补研究聚焦于高效冲突检测[20]、可分性理论[21]和任务冲突度量[22],旨在在扩展调度可行域的同时降低计算开销。综上所述,TSN调度研究呈现从复杂性基础[1]、[2]、[5]、[23]、[24]、[25],到基于优化和启发式的方法[6]、[8]、[9]、[10]、[12]、[13]、[14]、[15],再到智能与冲突感知策略[11]、[16]、[21]、[22]、[26],最终到近期可扩展框架[17]、[18]、[19]、[20]的发展脉络。提升运行效率一直是TSN调度器设计的核心目标之一。在集中式方法中,增量式调度被广泛认为是最具时间效率的实用基线之一,在保证可接受可调度性的同时具有显著的运行时间优势。尽管取得了上述进展,大多数现有方法主要侧重于在有限计算预算下优化调度质量,而求解器端的加速本身仍未得到充分探索。这促使我们将研究重点放在调度过程层面的计算加速上,而非重新设计原始优化目标。具体而言,我们引入了一种冲突感知的并行化层,该层将调度任务分解为可并发执行的子问题,并能与现有的集中式TSN调度器集成。并行化策略与具体的调度目标无关,并保持底层增量式调度器所使用的目标函数。主要贡献如下:- 我们提供了基于冲突图的TSN流间依赖关系分析,识别出可独立调度的子集以及需要协同资源分配的耦合子集。- 我们提出了一种并行分解策略,将流集划分为可并发调度的子集,在不改变原始调度目标的前提下实现显著的运行时间减少。- 我们对运行时间和非运行时间指标(包括成功率、链路利用率和端到端时延)进行了全面评估。每个实验设置独立重复五次运行并以平均值报告。结果表明,在所报告的场景下,所提并行调度策略相比增量式调度将调度时间减少了25%–50%,并通过经验对比展示了调度质量。本文其余部分组织如下:第2节总结相关工作;第3节介绍TSN流调度模型;第4节分析TSN流调度的复杂度;第5节介绍并行调度策略;第6节报告仿真结果;第7节总结全文。---**章节摘要****相关工作**TSN调度建立在关于网络结构和资源约束如何影响路由与调度算法的研究基础之上。基于图匹配的路由研究[27]提供了算法基础,而关于干扰受限信道分配[23]、半双工中继网络最大容量路由[24]和拓扑特定路由调度[25]的研究考察了带有额外资源或运行约束的问题。在TSN中,这一研究脉络延伸至更复杂的场景。**TSN模型与调度建模**本节提供TSN调度框架的基本描述,概述调度模型的基本公式,并给出相应的模型约束。模型及后续分析中使用的主要符号总结于表1中。**TSN流调度分析**本节考察时空冲突如何耦合调度决策,以及由此产生的图结构如何支持将问题分解为可独立调度的子集。调度难度取决于流量特征以及由共享资源和重叠传输时间窗引入的依赖关系。冲突图使这些依赖关系显式化,有助于识别并行处理的机会。图3展示了当流量集合具有不同特性时冲突结构的变化。**并行调度策略**本节介绍了一种基于冲突图划分的并行调度策略。核心思想是将流集分解为组间无冲突的组,从而使这些组的调度子问题可以并发求解,进而提升整体运行效率。我们提出了两种划分算法以实现该分解:一种基于接近度中心性,另一种使用图拉普拉斯矩阵的Fiedler向量。**仿真与评估**我们的评估旨在回答两个问题:(i) 所提并行加速层能实现多大的运行时间缩减;(ii) 在所测试场景中,所得调度质量与增量式基线相比如何。因此,运行时间被视为主要指标,而成功率、链路利用率和端到端时延作为补充性质量指标予以报告。为进行公平且实用的对比,我们将该方法与**结论**本文提出了一种面向集中式TSN流调度的目标保持型并行加速策略。通过利用冲突图分解,该方法在不改变底层调度器优化目标的前提下,将调度重新组织为可并行处理的子问题,并显著降低了运行时间。实验结果以每个设置五次独立运行的平均值报告,展示了时间效率的提升,并通过成功率的经验对比进行了补充评估。---**CRediT作者贡献声明****康凯旋:** 原稿撰写、验证、方法论、概念构思。**孟宁:** 审稿与编辑。**张京华:** 审稿与编辑。**曹素芝:** 审稿与编辑、资金获取。**吕从民:** 审稿与编辑。**刘鹏:** 验证、指导。**利益冲突声明**作者声明不存在可能影响本文工作的已知竞争性财务利益或个人关系。---康凯旋|孟宁|张京华|曹素芝|吕从民|刘鹏
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号