Software Engineering and Applications
Vol. 08  No. 06 ( 2019 ), Article ID: 33336 , 8 pages
10.12677/SEA.2019.86040

Research on TSN Real-Time Priority Queue Scheduling Algorithm for Industrial Wireless Networks

Zhixuan Chen

School of Information Science and Technology, Zhejiang Sci-Tech University, Hangzhou Zhejiang

Received: Nov. 14th, 2019; accepted: Nov. 29th, 2019; published: Dec. 6th, 2019

ABSTRACT

With the development of industrial and information technology, industrial wireless networks as the basic technology of industrial Internet of Things, have received more and more attention from the industry. It replaces the wired connection with wireless communication, which greatly reduces the cost of installation and maintenance. In complex industrial environment, it provides a flexible configuration solution for field devices, which provides a powerful technical impetus for the development of Industry 4.0. Based on the asynchronous scheduling mode, the distributed graph coloring algorithm and the priority queue scheduling algorithm are used to realize the asynchronous scheduling of multi-hop networks. The validity of the scheduling algorithm is verified on the contiki platform. The experimental result shows that the algorithm guarantees real-time communication of event-triggered flows and time-triggered flows.

Keywords:Industrial Wireless Networks, Asynchronous, Real-Time

工业无线网络TSN实时优先队列调度算法研究

陈志轩

浙江理工大学信息学院,浙江 杭州

收稿日期:2019年11月14日;录用日期:2019年11月29日;发布日期:2019年12月6日

摘 要

随着工业和信息化技术的发展,工业无线网络作为工业物联网的基础性技术,越来越受到业界的广泛关注。它以无线通信代替有线连接,大大减少了安装和维护的成本,在复杂的工业环境中,提供现场设备灵活的配置方案,为工业4.0的发展提供了强大的技术推动力。基于免同步收发调度模式,本文采用分布式图染色算法和优先级队列调度算法实现了多跳网络的免同步调度,并且在contiki平台上验证了调度算法的有效性,实验结果表明该算法保证了事件触发流和时间触发流的实时性通信。

关键词 :工业无线网络,免同步,实时性

Copyright © 2019 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

在工业4.0的环境下,提高制造业智能化生产水平,增强工业现场安全性,为工业物联网(IoT)和网络物理系统(CPS)带来新的挑战。相比于传统的工业以太网,工业无线网络提供了灵活的工业现场设备的配置方案,增强了工业生产的安全性,保障了人身财产安全,目前已广泛应用于工业自动化等领域。随着工业应用对工业无线网络需求的增加,业界制定了多种协议标准以实现工业环境下数据通信的实时性保证,WirelessHART [1],ISA100.11a [2] 和WIA-PA [3] 等工业无线网络标准也已在实践中得到部署。时间敏感网络(TSN)专注于扩展基于IEEE 802.1标准的以太网网络,以实现工业网络中的互联互通和实时通信 [4]。有线TSN应该利用无线TSN进行无缝冗余集成,在TSN现有的技术支持下,开发现有的无线网络技术,并制定共同的协议标准,将无线通信集成到工业操作系统和工业现场环境中,使得工业无线网络可以应用到更多更复杂的场景中。

由于通信媒介的不同,无线通信相较于有线通信更易受到干扰。大气中包括多种类型的电磁信号,障碍物的阻挡、多径效应以及信号源之间的相互干扰,造成传输的不确定性。为了满足工业无线网络数据传输严格的实时性和可靠性要求,业界提出了多种调度算法来有效地分配无线网络的时隙和信道。Ma [5] 提出了一种动态调度策略,基于运行时链路质量和控制性能的反馈进行预测从而分配网络资源,有效地应对了网络的干扰,提升控制系统性能。Kotsiou [6] 提出了一种基于黑名单的信道跳频算法,通过将可靠性较低的信道列入黑名单,并且结合调度算法感知黑名单提高了网络传输的可靠性。Wang [7] 综合考虑数据采样和链路调度,使得网络传输最新的采样数据,保证了数据传输的有效性。然而,这些调度算法实现的条件都需要精确的时钟同步,网络的实时性与可靠性取决于设备间的同步精度,同步精度差会造成设备处于不同信道从而无法进行通信,严重降低网络的稳定性。

本文基于免同步的收发调度模式,综合考虑多跳网络通信的诸多问题,提出了一种基于优先级队列的免同步调度算法,将事件触发流设为高优先级,在保证数据传输可靠性的同时,保证了事件触发流和时间触发流在确定的时延范围内传输到汇聚节点。

2. 系统模型

工业无线网络架构如图1所示,网络包含无线传感节点、路由节点和sink节点。全网所有节点时钟不同步且在同一个信道通信,无线传感节点根据采样周期周期性的生成时间触发流,随机生成事件触发流,以汇聚的形式发送到sink节点,路由节点只进行数据的转发。假定一个数据包可以在一个时隙范围内传输完成,每个周期只完成一跳的传输,所有节点独立异步的工作。在本文中,我们将网络模型限制为4跳,事件触发流的优先级高于时间触发流。表1列出了在本文中使用的符号及其代表意义。

Figure 1. Industrial wireless network topology

图1. 工业无线网络拓扑结构

Table 1. Each symbol represents meaning

表1. 各符号代表意义

3. 问题陈述

工业无线网络现有的调度算法依赖于全网节点时钟同步的精度,同步精度差会造成端到端时延的不确定性。当来自多个无线传感节点向同一个路由节点发送消息,那么会发生排队,端到端时延取决于排队时延,我们利用优先级队列,将事件触发流设为高优先级,保证最小化端到端时延。在本文中,我们将工业无线网络建模为如图1所示的有向图 G = ( V , E ) 。其中,V表示网络中节点的集合,E表示链路的集合。如果节点j在节点i的通信范围内,则存在链路(i, j)和(j, i),节点i和j可以进行通信,表示为 f i , j = 1 ,否则为0。在一个采样周期内,节点i发送数据包的时间为si,sink节点接收此数据包的时间为ti,我们的目标就是要最小化端到端时延,使得时间触发流和事件触发流在确定的时间范围内从源节点传输到sink节点,即:

min i = 1 N ( t i s i ) (1)

i = 1 N f i , j = 1 i = 1 N f j , i = 0 (2)

i = 1 V f i , sin k = 1 i = 1 V f sin k , i = 0 (3)

m M (4)

R N v (5)

C N (6)

ω τ T N (7)

公式(1)表示本文的优化目标是最小化端到端时延;公式(2)表示传感节点即源节点只发送消息不接收消息;公式(3)表示sink节点只接收消息,不以无线的方式发送消息;公式(4)表示子网内节点个数要小于调度模式包含的节点数,保证子网内存在无冲突时隙调度;公式(5)(6)(7)分别表示网络通信速率的约束、采样周期和节点缓存队列的约束,使得数据包在节点排队不会发生溢出的情况。

4. 基于优先级队列的免同步调度算法

4.1. 分布式图染色

我们提出了一种免同步的收发调度模式,利用冗余传输,保证每个节点都存在无冲突发送时隙,保证了节点端到端传输的可靠性与实时性。调度方案 S 的种类与节点数目相关,一种调度方案包含其中每个节点的调度模式。子网内节点个数要小于调度方案包含的节点数,否则会造成子网内个别节点无法可靠地通信。在本节中,我们采用图染色算法为每个节点分配调度模式S,确保每一个节点在任意子网内都是m种不同的调度模式。该算法流程图如图2所示。

4.2. 优先级队列调度

在本节中,我们使用优先级队列调度来实现周期性消息和非周期性消息的实时性通信,非周期性事件触发流的优先级高于周期性时间触发流。传感节点将测量数据分为两种数据类型,按照调度模式通信,当消息传输到下一跳节点,节点首先判断数据类型,然后存入优先级队列,高优先级的消息先被取出传输。我们在保证事件消息传输实时性的同时,保证了周期性数据在确定的时延范围内传输到sink节点,该算法流程图如图3所示。

Figure 2. Flow chart of distributed graph coloring algorithm

图2. 分布式图染色算法流程图

Figure 3. Flow chart of priority queue scheduling algorithm

图3. 优先级队列调度算法流程图

5. 结果评估

本节对文中所提出的调度算法进行仿真,仿真实验基于contiki仿真平台,实验包括可靠性测试和实时性测试,如图4图5所示。由图4可以看出,本文所提出的基于优先级队列的免同步调度算法保证了通信的可靠性,并且随着网络跳数的增加与节点个数的增多,仍然能够保证网络的可靠性通信。图5表示汇聚网络的平均时延,即时间触发流和事件触发流数据从传感节点传输到sink节点的平均时延,结果显示随着节点个数的增加,保证了数据传输的确定的端到端延迟。

Figure 4. Reliability experiment results

图4. 可靠性实验结果

Figure 5. Real-time experimental results

图5. 实时性实验结果

6. 结论

本文基于免同步的调度模式,通过分布式图染色算法为每个节点分配调度模式,并且利用优先级队列调度保证了事件触发流的实时性传输,在不需要全网节点时钟同步的情况下,保证了时间触发流在确定的时间范围内传输到汇聚节点。仿真结果表明,我们提出的基于优先级队列的免同步调度算法在通信的可靠性和实时性方面具有满意的效果。

文章引用

陈志轩. 工业无线网络TSN实时优先队列调度算法研究
Research on TSN Real-Time Priority Queue Scheduling Algorithm for Industrial Wireless Networks[J]. 软件工程与应用, 2019, 08(06): 326-333. https://doi.org/10.12677/SEA.2019.86040

参考文献

  1. 1. Saifullah, A., Xu, Y., Lu, C., et al. (2010) Real-Time Scheduling for Wireless HART Networks. In: 31st IEEE Real-Time Systems Symposium, IEEE, Piscataway, 150-159.
    https://doi.org/10.1109/RTSS.2010.41

  2. 2. Quang, P.T.A. and Kim, D.S. (2013) Throughput-Aware Routing for Industrial Sensor Networks: Application to ISA100.11a. IEEE Transactions on Industrial Informatics, 10, 351-363.
    https://doi.org/10.1109/TII.2013.2255617

  3. 3. Zhang, X., Liang, W., Zheng, M., et al. (2009) Distributed and Dynamic TDMA Channel Scheduling Algorithm for WIA-PA. IEEE International Conference on Intelligent Computing and Intelligent Systems, Vol. 3, 462-466.

  4. 4. Chen, Y., Zhang, H., Fisher, N., et al. (2018) Probabilistic Per-Packet Real-Time Guarantees for Wireless Networked Sensing and Control. IEEE Transactions on Industrial Informatics, 14, 2133-2145.
    https://doi.org/10.1109/TII.2018.2795567

  5. 5. Ma, Y., Guo, J., Wang, Y., et al. (2019) Optimal Dynamic Scheduling of Wireless Networked Control Systems. In: Proceedings of the 10th ACM/IEEE International Conference on Cyber-Physical Systems, ACM, New York, 77-86.
    https://doi.org/10.1145/3302509.3311040

  6. 6. Kotsiou, V., Papadopoulos, G.Z., Zorbas, D., et al. (2019) Blacklist-ing-Based Channel Hopping Approaches in Low-Power and Lossy Networks. IEEE Communications Magazine, 57, 48-53.
    https://doi.org/10.1109/MCOM.2018.1800362

  7. 7. Wang, Z., Qin, X., Liu, B., et al. (2019) Joint Data Sampling and Link Scheduling for Age Minimization in Multihop Cyber-Physical Systems. IEEE Wireless Communications Letters, 8, 765-768.
    https://doi.org/10.1109/LWC.2019.2891598

期刊菜单