可扩展调度在时间敏感网络中的应用:一种高效的流冲突检测方法

news/2025/2/26 18:53:51

论文标题

**中文标题:**可扩展调度在时间敏感网络中的应用:一种高效的流冲突检测方法
**英文标题:**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网络中的实时和确定性通信提供了有效的调度解决方案。


http://www.niftyadmin.cn/n/5869079.html

相关文章

Android 字体大小自动处理 AppCompactTextView 和 自定义 TextView

背景 来自于 需求的视觉设计要求 限制字段长度为320px超长时按宽度缩小字号TextView底色高度固定字体缩小步进1sp难点 课程卡片为自定义View,封装信息层组件,通过锚定基准比例实时计算获取以下对应信息: RadiusImageWidthImageHeightMaginPaddingTextSize动态数据加载,等…

网络安全漏洞管理要求 网络安全产品漏洞

一、漏洞类型 缓冲区溢出、跨站脚本、DOS攻击、扫描、SQL 注入、木马后门、病毒蠕虫、web攻击、僵尸网络、跨站请求伪造、文件包含、文件读取、目录遍历攻击、敏感信息泄露、暴力破解、代码执行漏洞、命令执行、弱口令、上传漏洞利用、webshell利用、配置不当/错误、逻辑/涉及错…

【C++设计模式】观察者模式(1/2):从基础到优化实现

1. 引言 在 C++ 软件与设计系列课程中,观察者模式是一个重要的设计模式。本系列课程旨在深入探讨该模式的实现与优化。在之前的课程里,我们已对观察者模式有了初步认识,本次将在前两次课程的基础上,进一步深入研究,着重解决观察者生命周期问题,提升代码的安全性、灵活性…

设计模式-(装饰器,适配器,观察者,外观)

装饰器模式 概念: 它允许在不改变对象自身的情况下,动态地给对象添加额外的功能。通过使用装饰器模式,可以在运行时对对象进行扩展,而不需要创建大量的子类 应用: 当你希望在不修改原有类的情况下,给对…

高中数学基础-统计和概率

文章目录 一、统计基础二、概率三、计数原理四、随机变量 高中数学基础-统计和概率 一、统计基础 总体、个体:所有元素称为总体,其中一个元素称为个体普查、抽查:所有元素都检查一遍称为普查,对部分样本进行抽取检查称为抽查&…

BUG: 解决新版本SpringBoot3.4.3在创建项目时勾选lombok但无法使用的问题

前言 当使用Spring Boot 3.4.3创建新项目时,即使正确勾选Lombok依赖,编译时仍出现找不到符号的错误,但代码中Lombok注解的使用完全正确。 原因 Spring Boot 3.4.3在自动生成的pom.xml中新增了maven-compiler-plugin的配置,该插件…

精美登录注册UI,登录页面设计模板

精美登录注册UI,登录页面设计模板 引言 在网页设计中,按钮是用户交互的重要元素之一。一个炫酷的按钮特效不仅能提升用户体验,还能为网页增添独特的视觉吸引力。今天,我们将通过CSS和JavaScript来实现一个“精美登录注册UI,登录页面设计模板”。该素材呈现了数据符号排版…

父组件用的是原生监听,子组件用的是onClick,子组件添加了stopPropagation还是没有阻止传播

父组件用事件监听,子组件用onClick,即使子组件加了stopPropagation还是没有阻止冒泡。父组件可能使用原生的addEventListener来绑定事件,而子组件用的是React的onClick事件。这时候,虽然子组件调用了e.stopPropagation()&#xff…