2.793

2018影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于优先级分类的工业无线网络确定性调度算法

王恒 朱元杰 杨杭 王平

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

基于优先级分类的工业无线网络确定性调度算法

doi: 10.16383/j.aas.c170722
基金项目: 

国家自然科学基金 61701065

国家高技术研究发展计划(863计划) 2015AA043801

详细信息
    作者简介:

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

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

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

    通讯作者:

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

  • 本文责任编委 付俊

Deterministic Scheduling Algorithm With Priority Classification for Industrial Wireless Networks

Funds: 

National Natural Science Foundation of China 61701065

National High Technology Research and Development Program of China (863 Program) 2015AA043801

More Information
    Author Bio:

    ZHU Yuan-Jie  Master student at the College of Automation, Chongqing University of Posts and Telecommunications. His research interest covers industrial wireless networks

    YANG Hang  Master student at the College of Automation, Chongqing University of Posts and Telecommunications. His research interest covers industrial internet of things

    WANG Ping  Professor at the College of Automation, Chongqing University of Posts and Telecommunications. He received his Ph. D. degree from Southwest Jiaotong University in 1994. His research interest covers industrial internet of things, networked control, and industrial wireless networks

    Corresponding author: WANG Heng  Professor at the College of Automation, Chongqing University of Posts and Telecommunications. He received his Ph. D. degree from Chongqing University in 2010. His research interest covers industrial internet of things, wireless sensor networks, and cooperative communications. Corresponding author of this paper
  • Recommended by Associate Editor FU Jun
  • 摘要: 确定性调度技术对于工业无线网络数据的实时性和确定性传输有着重要意义.本文针对工业无线网络数据流本身存在优先级分类属性的情况, 基于多信道时分多址接入(TDMA)技术, 在分析高优先级数据流对低优先级数据流造成的链路冲突延时和信道竞争延时基础上, 对网络进行调度预处理, 进而排除参数不合理的网络, 并向网络管理者反馈.对于通过预处理的网络, 调度算法优先为高优先级数据流的链路分配时隙和信道资源, 而对属于同一类优先级的数据流, 提出一种基于比例冲突空余时间的调度方案, 在满足可调度性条件的前提下, 根据各链路的比例冲突空余时间值从小到大依次分配时隙和信道资源.实验结果表明, 所提出的调度算法可以取得较高的网络调度成功率.
    Recommended by Associate Editor FU Jun
    1)  本文责任编委 付俊
  • 图  1  工业无线网络数据流示意图

    Fig.  1  Illustration of data flow in industrial wireless network

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

    Fig.  2  Illustration of end-to-end transmission delay for data flow

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

    Fig.  3  The first case of link conflict caused by data flows with different priorities

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

    Fig.  4  The second case of link conflict caused by data flows with different priorities

    图  5  调度预处理流程图

    Fig.  5  Flowchart of the scheduling pre-processing

    图  6  三种调度方法关于截止时间和实际调度平均时延数据对比图

    Fig.  6  Comparisons between the deadlines and the actual scheduled average delays for three scheduling methods

    图  7  不同网络规模下三种调度方法的调度成功率

    Fig.  7  Success probabilities of scheduling for the three scheduling schemes in different network sizes

    图  8  不同丢包情况下三种调度方法的调度结果

    Fig.  8  Successful scheduling ratios of data flows for the three scheduling methods in different packet loss cases

    表  1  模型中参数符号代表的意义

    Table  1  Notations used in the considered model

    符号 意义
    Fi i条数据流
    Ti i条数据流的周期
    hp(Fi) 优先级高于Fi的所有数据流集合
    Di 数据流Fi受到hp(Fi)影响造成的总延时
    Ci 数据流Fi完成传输的截止时隙
    Hi 数据流Fi端到端传输路径上的路由跳数
    Li 数据流Fi的端到端传输延时
    rHt 某条数据流在时隙t下剩余未传输的链路个数
    下载: 导出CSV

    表  2  三种调度方法的平均执行时间(ms)

    Table  2  Average execution time of three scheduling methods (ms)

    网络规模 10个节点,
    5条数据流
    20个节点,
    10条数据流
    30个节点,
    15条数据流
    40个节点,
    20条数据流
    50个节点,
    25条数据流
    60个节点,
    30条数据流
    70个节点,
    35条数据流
    EPD-C 21.4 89.9 195.6 311.6 491.4 737.9 973.9
    LLF 24.7 100.5 215.6 391.6 625.5 943.9 1 215.5
    RM 26.5 113.3 269.4 483.6 859.3 1 340 2 084
    下载: 导出CSV
  • [1] Sha M, Gunailaka D, Wu C J, Lu C Y. Empirical study and enhancements of industrial wireless sensor-actuator network protocols. IEEE Internet of Things Journal, 2017, 4(3): 696-704 doi: 10.1109/JIOT.2017.2653362
    [2] Begum K, Dixit S. Industrial WSN using IoT: a survey. In: Proceedings of the 2016 International Conference on Electrical, Electronics, and Optimization Techniques (ICEEOT). Palnchur, Chen Nai, India: IEEE, 2016. 499-504
    [3] Wang Q, Jiang J. Comparative examination on architecture and protocol of industrial wireless sensor network standards. IEEE Communications Surveys & Tutorials, 2016, 18(3): 2197-2219 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=7b14c25bc9010a525f25c11d6c1db59d
    [4] Toscano E, Lo Bello L. Multichannel superframe scheduling for IEEE 802.15.4 industrial wireless sensor networks. IEEE Transactions on Industrial Informatics, 2012, 8(2): 337-350 doi: 10.1109/TII.2011.2166773
    [5] Saifullah A, Xu Y, Lu C Y, Chen Y X. Real-time scheduling for wirelessHART networks. In: Proceedings of the 31st IEEE Real-Time Systems Symposium (RTSS). San Diego, CA, USA: IEEE, 2010. 150-159
    [6] Kim Y G, Lee M J. Scheduling multi-channel and multi-timeslot in time constrained wireless sensor networks via simulated annealing and particle swarm optimization. IEEE Communications Magazine, 2014, 52(1): 122-129 doi: 10.1109/MCOM.2014.6710073
    [7] Kang H, Zhao Y N, Mei F. A graph coloring based TDMA scheduling algorithm for wireless sensor networks. Wireless Personal Communications, 2013, 72(2): 1005-1022 doi: 10.1007/s11277-013-1052-9
    [8] Kang B, Nguyen P K H, Zalyubovskiy V, Choo H. A distributed delay-efficient data aggregation scheduling for duty-cycled WSNs. IEEE Sensors Journal, 2017, 17(11): 3422-3437 doi: 10.1109/JSEN.2017.2692246
    [9] 贾杰, 代恩亮, 陈剑, 王兴伟, 赵林亮.无线传感器网络中联合路由优化的高能效链路调度.电子学报, 2014, 42(6): 1118-1124 doi: 10.3969/j.issn.0372-2112.2014.06.013

    Jia Jie, Dai En-Liang, Chen Jian, Wang Xing-Wei, Zhao Lin-Liang. Energy-efficient link scheduling combined with routing optimization in wireless sensor network. Acta Electronica Sinica, 2014, 42(6): 1118-1124 doi: 10.3969/j.issn.0372-2112.2014.06.013
    [10] 牛建军, 邓志东.基于马尔可夫链的无线传感器网络分布式调度方法.自动化学报, 2010, 36(5): 685-695 doi: 10.3724/SP.J.1004.2010.00685

    Niu Jian-Jun, Deng Zhi-Dong. Markov chain-based distributed scheduling approach for wireless sensor network. Acta Automatica Sinica, 2010, 36(5): 685-695 doi: 10.3724/SP.J.1004.2010.00685
    [11] Sgora A, Vergados D J, Vergados D D. A survey of TDMA scheduling schemes in wireless multihop networks. ACM Computing Surveys, 2015, 47(3): 1-39 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=84249ad24dcfe9401e41c7781eade0a7
    [12] 张晓玲, 梁炜, 于海斌, 封锡盛.无线传感器网络传输调度方法综述.通信学报, 2012, 33(5): 143-157 doi: 10.3969/j.issn.1000-436X.2012.05.019

    Zhang Xiao-Ling, Liang Wei, Yu Hai-Bin, Feng Xi-Sheng. Survey of transmission scheduling methods in wireless sensor networks. Journal on Communications, 2012, 33(5): 143-157 doi: 10.3969/j.issn.1000-436X.2012.05.019
    [13] Rao S, Keshri S, Gangwar D, Sundar P, Geetha V. A survey and comparison of GTS allocation and scheduling algorithms in IEEE 802.15.4 wireless sensor networks. In: Proceedings of the 2013 IEEE Conference on Information and Communication Technologies (ICT). Thuckalay, Tamil Nadu, India: IEEE, 2013. 98-103
    [14] 李金宝, 王蒙, 郭龙江. MR-MC无线传感器网络最小延迟数据聚集调度研究.通信学报, 2014, 35(10): 192-199 doi: 10.3969/j.issn.1000-436x.2014.10.022

    Li Jin-Bao, Wang Meng, Guo Long-Jiang. Minimum latency data aggregation scheduling in MR-MC wireless sensor networks. Journal on Communications, 2014, 35(10): 192-199 doi: 10.3969/j.issn.1000-436x.2014.10.022
    [15] 牛建军, 邓志东, 李超.无线传感器网络分布式调度方法研究.自动化学报, 2011, 37(5): 517-528 doi: 10.3724/SP.J.1004.2011.00517

    Niu Jian-Jun, Deng Zhi-Dong, Li Chao. Distributed scheduling approaches in wireless sensor network. Acta Automatica Sinica, 2011, 37(5): 517-528 doi: 10.3724/SP.J.1004.2011.00517
    [16] 王恒, 陈鹏飞, 王平.面向WIA-PA工业无线传感器网络的确定性调度算法.电子学报, 2018, 46(1): 68-74 doi: 10.3969/j.issn.0372-2112.2018.01.010

    Wang Heng, Chen Peng-Fei, Wang Ping. Deterministic scheduling algorithms for WIA-PA industrial wireless sensor networks. Acta Electronica Sinica, 2018, 46(1): 68-74 doi: 10.3969/j.issn.0372-2112.2018.01.010
    [17] 王恒, 李敏, 刘其琛, 王平.一种基于确定性调度的工业无线网络路由算法.仪器仪表学报, 2011, 32(9): 1921-1928 http://d.old.wanfangdata.com.cn/Periodical/yqyb201109001

    Wang Heng, Li Min, Liu Qi-Chen, Wang Ping. Routing algorithm for industrial wireless network based on deterministic scheduling. Chinese Journal of Scientific Instrument, 2011, 32(9): 1921-1928 http://d.old.wanfangdata.com.cn/Periodical/yqyb201109001
    [18] Saifullah A, Xu Y, Lu C Y, Chen Y X. End-to-end communication delay analysis in industrial wireless networks. IEEE Transactions on Computers, 2015, 64(5): 1361-1374 doi: 10.1109/TC.2014.2322609
    [19] Industrial networks - Wireless communication network and communication profiles - WIA-PA, IEC 62601, 2015
    [20] Leung J Y, Whitehead J. On the complexity of fixed-priority scheduling of periodic, real-time tasks. Performance Evaluation, 1982, 2(4): 237-250 doi: 10.1016/0166-5316(82)90024-4
    [21] 王永吉, 陈秋萍.单调速率及其扩展算法的可调度性判定.软件学报, 2004, 15(6): 799-814 http://d.old.wanfangdata.com.cn/Periodical/rjxb200406002

    Wang Yong-Ji, Chen Qiu-Ping. On schedulability test of rate monotonic and its extendible algorithms. Journal of Software, 2004, 15(6): 799-814 http://d.old.wanfangdata.com.cn/Periodical/rjxb200406002
    [22] Ayele A A, Rao V S, Dileep K G, Bokka R K. Combining EDF and LST to enhance the performance of real-time task scheduling. In: Proceedings of the 2016 International Conference on ICT in Business, Industry, and Government (ICTBIG). Indore, India: IEEE, 2016.
  • 加载中
图(8) / 表(2)
计量
  • 文章访问数:  701
  • HTML全文浏览量:  359
  • PDF下载量:  98
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-12-22
  • 录用日期:  2018-11-08
  • 刊出日期:  2020-03-06

目录

    /

    返回文章
    返回