引用本文

王恒, 朱元杰, 杨杭, 王平. 基于优先级分类的工业无线网络确定性调度算法. 自动化学报, 2020, 46(2): 373-384. doi: 10.16383/j.aas.c170722

WANG Heng, ZHU Yuan-Jie, YANG Hang, WANG Ping. Deterministic Scheduling Algorithm With Priority Classification for Industrial Wireless Networks. ACTA AUTOMATICA SINICA, 2020, 46(2): 373-384. doi: 10.16383/j.aas.c170722

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c170722

关键词

工业无线网络，确定性调度，优先级分类，调度预处理 

摘要

确定性调度技术对于工业无线网络数据的实时性和确定性传输有着重要意义.本文针对工业无线网络数据流本身存在优先级分类属性的情况, 基于多信道时分多址接入(TDMA)技术, 在分析高优先级数据流对低优先级数据流造成的链路冲突延时和信道竞争延时基础上, 对网络进行调度预处理, 进而排除参数不合理的网络, 并向网络管理者反馈.对于通过预处理的网络, 调度算法优先为高优先级数据流的链路分配时隙和信道资源, 而对属于同一类优先级的数据流, 提出一种基于比例冲突空余时间的调度方案, 在满足可调度性条件的前提下, 根据各链路的比例冲突空余时间值从小到大依次分配时隙和信道资源.实验结果表明, 所提出的调度算法可以取得较高的网络调度成功率.

文章导读

工业无线网络是对现有工业通信技术的一种强有力的补充, 具有快速部署、高可靠性以及节约成本等特性.随着工业物联网的不断发展, 工业无线网络将会被更大范围的应用[1-2].当前国际上出现了三项主流的工业无线网络技术, 分别是WirelessHART标准、ISA100.11a标准以及我国自主制定的WIA-PA (Wireless networks for industrial automation-process automation)标准[3].其中确定性调度问题作为工业无线网络的一个重要研究方向, 在三项标准中通过多信道时分多址接入(Time division multiple access, TDMA)机制来提供调度所需要的时隙和信道资源[4].目前, 工业无线网络的确定性调度问题已经被证明是一个NP-hard问题[5].

在与工业无线网络密切相关的无线传感器网络领域, 网络调度问题被广泛研究, 其研究成果对于解决工业无线网络的调度问题, 具有一定的参考价值.在无线传感器网络中, 已有的网络调度算法包括元启发式算法(例如粒子群算法)、图着色法等调度方法[6-7], 以及考虑数据聚合、能量消耗、优先级策略等目标的调度算法[8-10].其中, 确定性调度问题的研究目标是考虑如何合理的分配时隙、信道等通信资源, 使网络中的数据流满足规定的端到端时延约束[11-15]. Kim等采用模拟退火法和粒子群算法对无线传感器网络中的调度问题进行了优化研究, 并对两种算法进行了分析比较[6]. Kang等探索了分簇无线传感器网络下基于TDMA机制的分布式图着色调度算法, 该算法包含着色和调度两个阶段, 增加簇内吞吐量的同时也降低了簇内传输延时, 但此算法没有考虑网络存在多信道资源的情况[7].贾杰等提出一种基于最大干扰度优先的链路调度算法, 令尽可能多的链路并行传输, 在调度周期以及能量消耗双重优化目标下获得不错的性能[9].李金宝等面向多信道无线传感器网络, 提出了最小化数据聚集延迟的调度算法[14].牛建军等对无线传感器网络中的分布式调度方法进行了系统讨论和分析[15].

具体到各种工业无线网络, 针对确定性调度问题的研究, 也取得了一定进展.针对WIA-PA网络, 文献[16]提出了面向中小规模网络和大规模网络的两种确定性调度方法, 结合WIA-PA网络的分层分簇特征进行了优化设计.针对ISA100.11a网络, 文献[17]研究了基于确定性调度的路径选择方法, 保障了传输路径的端到端时延.针对WirelessHART网络, Saifullah等提出了C-LLF (Conflict-aware least laxity first)调度算法[5], 该算法计算网络中当前时隙下所有处于释放态链路的冲突觉知松散度值, 越小的冲突觉知松散度就会优先在当前时隙的剩余可用信道上安排此链路.算法在网络可调度率上取得了良好的性能, 该算法考虑了多信道的情况, 但没有考虑数据流存在固有优先级属性的情况.文献[18]同样围绕WirelessHART网络, 对固定优先级下网络中端到端数据流的时延进行了分析, 为当前网络在基于时隙信道分配技术下是否可调度提供了一种指导思路, 但没有给出数据流存在固定优先级下具体的调度方法.综上所述, 以上针对工业无线网络和无线传感器网络调度问题的研究文献, 要么基于TDMA机制对优化目标进行启发式或元启发式调度, 但没有考虑工业无线网络中存在多信道时的情况; 要么研究了多信道TDMA机制下链路调度, 但没有考虑网络中数据流存在固有优先级属性的情况.此外, 对于同一优先级下存在多条数据流的情况很少有文献进行研究.

在工业无线网络中, 网络中的数据流本身是具有优先级属性的, 数据的优先级根据其业务应用的特点决定.例如WIA-PA标准规定了数据的四种优先级[19], 优先级从高到低排列分别为:处理网络管理控制与紧急告警的命令帧、用于工业自动化生产监控的过程数据、一般数据和非紧急的报警数据.在给定优先级个数限制下, 网络中会存在多条数据流具有同一个优先级的情况.此时对于确定性调度问题, 不仅要考虑时隙和信道资源的分配能满足网络所有数据流的时延约束要求, 还应该在全部数据流满足时延约束的前提下, 尽量保障高优先级的数据流优先分配时隙和信道.

因此, 本文针对多信道TDMA机制下数据流存在优先级分类属性的情况, 通过分析网络中高优先级数据流对低优先级数据流在最坏情况下造成的时延, 利用时延分析的结果对网络进行调度预处理, 达到排除一些参数不合理的网络的效果, 并反馈给网络管理者处理.对于通过预处理的网络, 在进行时隙和信道的分配时, 优先分配给高优先级数据流的链路; 对于优先级相同的链路, 则提出了一种基于比例冲突空余时间值的调度方案, 根据该值从小到大按序对各条链路进行调度.最终的仿真结果验证了提出的调度方案的正确性, 以及相比经典的优先级调度方法具有更高的调度成功率.

图 1  工业无线网络数据流示意图

图 2  数据流端到端传输时延示意图

图 3  不同优先级数据流发生链路冲突情况一

本文研究了工业无线网络下基于优先级分类的数据流确定性调度问题, 在对数据流模型数学化描述的基础上, 分析了造成低优先级数据流传输延迟的两个因素:链路冲突和信道竞争.根据数据流时延分析结果对网络的数据流进行调度预处理, 从而达到排除一些参数不合理的网络的效果, 并可以反馈给网络管理者.针对同一优先级下可能包含多条数据流, 提出一种基于最小比例冲突时间的动态EPD-C调度算法, 仿真结果表明相比经典的RM算法和LLF算法, EPD-C算法可以取得更高的调度解成功率, 而且具有较低的算法时间执行.不足之处是当网络规模较大时, 计算效率和调度成功率下降明显, 未来将对EPD-C算法在大规模网络下的性能进行进一步的优化研究.此外, 本文仿真采用了随机生成网络的方式, 将来可进一步结合有代表性的过程控制应用场景进行仿真分析, 并可搭建实物网络, 在真实的工业环境下进行测试验证, 以进一步提高调度算法的实用性.

作者简介

朱元杰  

重庆邮电大学自动化学院硕士研究生.主要研究方向为工业无线网络. E-mail: zhuyuanjie2016@163.com

杨杭  

重庆邮电大学自动化学院硕士研究生.主要研究方向为工业物联网. E-mail: 18716322620@163.com

王平  

重庆邮电大学自动化学院教授. 1994年获得西南交通大学博士学位.主要研究方向为工业物联网, 网络化控制, 工业无线网络. E-mail: wangping@cqupt.edu.cn

王恒  

重庆邮电大学自动化学院教授. 2010年获得重庆大学博士学位.主要研究方向为工业物联网, 无线传感器网络, 协作通信.本文通信作者. E-mail: wangheng@cqupt.edu.cn