面向WIA-PA工业无线传感器网络的确定性调度算法
|
摘要
WIA-PA(Wireless Networks for Industrial Automation-Process Automation)是我国自主制定的工业无线传感器网络标准,确定性调度技术是其中一项关键技术.但目前已有的确定性调度算法主要集中在通用传感器网络或Wireless HART,ISA100.11a等遵循国外标准的工业无线传感器网络中,未能针对WIA-PA网络进行优化设计.鉴于此,本文提出了一种适用于WIA-PA网络的基于回溯法的最优确定性调度算法,能够获取调度解的最大成功率;并以此为基础,进一步提出了一种基于最小时间裕度优先的时分多址调度算法(Least Slack First on Time Division Multiple Access,LSF-TDMA).仿真实验结果表明,所提出的LSF-TDMA算法能够满足WIA-PA网络端到端数据传输的确定性需求,在调度解获取成功率接近于最优的同时,有效降低了算法复杂度.
Wireless Networks for Industrial Automation Process Automation( WIA-PA) is China's national standard for industrial wireless sensor networks. Deterministic scheduling is one of the key technologies for WIA-PA networks. However,current deterministic scheduling algorithms mainly focus on the common wireless sensor networks or WirelessHART and ISA100. 11 a networks, and they are not optimized for WIA-PA networks. Therefore, an optimal backtracking scheduling algorithm is proposed and achieves the optimal schedulable ratio for WIA-PA networks. And based on this, another deterministic scheduling algorithm called Least Slack First on Time Division Multiple Access( LSF-TDMA) is further presented.Simulation results demonstrate that LSF-TDMA algorithm can meet the deterministic demand of end-to-end data transmissions in WIA-PA networks. It obtains a near-optimal schedulable ratio while effectively reducing the algorithm complexity.
Wireless Networks for Industrial Automation Process Automation( WIA-PA) is China's national standard for industrial wireless sensor networks. Deterministic scheduling is one of the key technologies for WIA-PA networks. However,current deterministic scheduling algorithms mainly focus on the common wireless sensor networks or WirelessHART and ISA100. 11 a networks, and they are not optimized for WIA-PA networks. Therefore, an optimal backtracking scheduling algorithm is proposed and achieves the optimal schedulable ratio for WIA-PA networks. And based on this, another deterministic scheduling algorithm called Least Slack First on Time Division Multiple Access( LSF-TDMA) is further presented.Simulation results demonstrate that LSF-TDMA algorithm can meet the deterministic demand of end-to-end data transmissions in WIA-PA networks. It obtains a near-optimal schedulable ratio while effectively reducing the algorithm complexity.
引文
[1]高汉荣,冯冬芹.工业无线网络的现状及发展趋势[J].中国仪器仪表,2008,(S1):87-89,95.GAO Han-rong,FENG Dong-qin.The situation and future development of w ireless industrial netw orks[J].China Instrumentation,2008,(S1):87-89,95.(in Chinese)
[2]LIANG W,ZHANG X,XIAO Y,et al.Survey and experiments of WIA-PA specification of industrial w ireless netw ork[J].Wireless Communications and M obile Computing,2011,11(8):1197-1212.
[3]CHOI H,WANG J,HUGHES E.Scheduling on sensor hybrid netw ork[A].Proceedings of International Conference on Computer Communications and Netw orks[C].San Diego:IEEE,2005.503-508.
[4]SAIFULLAH A,XU Y,LU C,et al.Real-time scheduling for Wireless HART netw orks[A].Proceedings of 31st IEEE Real-Time Systems Symposium[C].San Diego:IEEE,2010.150-159.
[5]LI Q,NEGI R.Greedy maximal scheduling in wireless netw orks[A].Proceedings of 2010 Global Telecommunications Conference[C].M iami:IEEE,2010.1-5.
[6]KANG H,ZHAO Y,MEI F.A graph coloring based TDM A scheduling algorithm for w ireless sensor netw orks[J].Wireless Personal Communications,2013,72(2):1005-1022.
[7]王沁,赵金东.WIA-PA网络中的无冲突资源调度算法[J].小型微型计算机系统,2010,31(9):1726-1730.WANG Qin,ZHAO Jin-dong.Non-collision resources scheduling algorithm for WIA-PA netw orks[J].Journal of Chinese Computer Systems,2010,31(9):1726-1730.(in Chinese)
[8]KIM Y,LEE M.Scheduling multi-channel and multi-timeslot in time constrained w ireless sensor netw orks via simulated annealing and particle sw arm optimization[J].IEEE Communications M agazine,2014,52(1):122-129.
[9]VITTURI S,TRAMARIN F,SENO L.Industrial wireless netw orks:the significance of timeliness in communication systems[J].IEEE Industrial Electronics M agazine,2013,7(2):40-51.
[10]贾杰,代恩亮,陈剑,等.无线传感器网络中联合路由优化的高能效链路调度[J].电子学报,2014,42(6):1118-1124.JIA Jie,DAI En-liang,CHEN Jian,et al.Energy-efficient link scheduling combined w ith routing optimization in w ireless sensor netw ork[J].Acta Electronica Sinica,2014,42(6):1118-1124.(in Chinese)
[11]任俊亮,邢清华,李龙跃,等.分布式传感器调度模型与自适应概率粒子群优化算法[J].电子学报,2015,43(9):1756-1762.REN Jun-liang,XING Qing-hua,LI Long-yue,et al.A model of distributed sensors’scheduling and self-adaptive probability particle sw arm optimization algorithm[J].Acta Electronica Sinica,2015,43(9):1756-1762.(in Chinese)
[12]HUANG J,LIN C,CHENG B.Energy efficient speed scaling and task scheduling for distributed computing systems[J].Chinese Journal of Electronics,2015,24(3):468-473.
[13]SOLDATI P,ZHANG H,JOHANSSON M.Deadline-constrained transmission scheduling and data evacuation in Wireless HART netw orks[A].Proceedings of 2009 European Control Conference[C].Budapest:IEEE,2009.4320-4325.
[14]DOBSLAW F,ZHANG T,GIDLUND M.End-to-end reliability-aw are scheduling for w ireless sensor netw orks[J].IEEE Transactions on Industrial Informatics,2016,12(2):758-767.
[15]NHON T,KIM D.Real-time message scheduling for ISA100.11a networks[J].Computer Standards&Interfaces,2015,37:73-79.
[16]ZHANG X,LIANG W,YU H,et al.Optimal convergecast scheduling limits for clustered industrial w ireless sensor netw orks[J/OL].International Journal of Distributed Sensor Netw orks,2012,http://dx.doi.org/10.1155/2012/891321,2012-11-27.
[17]YANG Y,ZHANG X,LUO Q,et al.Dynamic time division multiple access algorithm for industrial w ireless hierarchical sensor netw orks[J].China Communications,2013,10(5):137-145.
[18]ZHANG X,LIANG W,YU H,et al.Optimal convergecast scheduling for hierarchical w ireless industrial systems:performance bounds and tw o-stage algorithms[J].IET Communications,2015,9(1):88-100.
[19]TANG Z,CHENG M,ZENG P,et al.Real-time communication in WIA-PA industrial w ireless netw orks[A].Proceedings of 2010 3rd Computer Science and Information Technology[C].Chengdu:IEEE,2010.600-605.
[20]BUTTAZZO G.Hard Real-time Computing Systems:Predictable Scheduling Algorithms and Applications(Third Edition)[M].Virginia:Springer,2011.79-117.
[2]LIANG W,ZHANG X,XIAO Y,et al.Survey and experiments of WIA-PA specification of industrial w ireless netw ork[J].Wireless Communications and M obile Computing,2011,11(8):1197-1212.
[3]CHOI H,WANG J,HUGHES E.Scheduling on sensor hybrid netw ork[A].Proceedings of International Conference on Computer Communications and Netw orks[C].San Diego:IEEE,2005.503-508.
[4]SAIFULLAH A,XU Y,LU C,et al.Real-time scheduling for Wireless HART netw orks[A].Proceedings of 31st IEEE Real-Time Systems Symposium[C].San Diego:IEEE,2010.150-159.
[5]LI Q,NEGI R.Greedy maximal scheduling in wireless netw orks[A].Proceedings of 2010 Global Telecommunications Conference[C].M iami:IEEE,2010.1-5.
[6]KANG H,ZHAO Y,MEI F.A graph coloring based TDM A scheduling algorithm for w ireless sensor netw orks[J].Wireless Personal Communications,2013,72(2):1005-1022.
[7]王沁,赵金东.WIA-PA网络中的无冲突资源调度算法[J].小型微型计算机系统,2010,31(9):1726-1730.WANG Qin,ZHAO Jin-dong.Non-collision resources scheduling algorithm for WIA-PA netw orks[J].Journal of Chinese Computer Systems,2010,31(9):1726-1730.(in Chinese)
[8]KIM Y,LEE M.Scheduling multi-channel and multi-timeslot in time constrained w ireless sensor netw orks via simulated annealing and particle sw arm optimization[J].IEEE Communications M agazine,2014,52(1):122-129.
[9]VITTURI S,TRAMARIN F,SENO L.Industrial wireless netw orks:the significance of timeliness in communication systems[J].IEEE Industrial Electronics M agazine,2013,7(2):40-51.
[10]贾杰,代恩亮,陈剑,等.无线传感器网络中联合路由优化的高能效链路调度[J].电子学报,2014,42(6):1118-1124.JIA Jie,DAI En-liang,CHEN Jian,et al.Energy-efficient link scheduling combined w ith routing optimization in w ireless sensor netw ork[J].Acta Electronica Sinica,2014,42(6):1118-1124.(in Chinese)
[11]任俊亮,邢清华,李龙跃,等.分布式传感器调度模型与自适应概率粒子群优化算法[J].电子学报,2015,43(9):1756-1762.REN Jun-liang,XING Qing-hua,LI Long-yue,et al.A model of distributed sensors’scheduling and self-adaptive probability particle sw arm optimization algorithm[J].Acta Electronica Sinica,2015,43(9):1756-1762.(in Chinese)
[12]HUANG J,LIN C,CHENG B.Energy efficient speed scaling and task scheduling for distributed computing systems[J].Chinese Journal of Electronics,2015,24(3):468-473.
[13]SOLDATI P,ZHANG H,JOHANSSON M.Deadline-constrained transmission scheduling and data evacuation in Wireless HART netw orks[A].Proceedings of 2009 European Control Conference[C].Budapest:IEEE,2009.4320-4325.
[14]DOBSLAW F,ZHANG T,GIDLUND M.End-to-end reliability-aw are scheduling for w ireless sensor netw orks[J].IEEE Transactions on Industrial Informatics,2016,12(2):758-767.
[15]NHON T,KIM D.Real-time message scheduling for ISA100.11a networks[J].Computer Standards&Interfaces,2015,37:73-79.
[16]ZHANG X,LIANG W,YU H,et al.Optimal convergecast scheduling limits for clustered industrial w ireless sensor netw orks[J/OL].International Journal of Distributed Sensor Netw orks,2012,http://dx.doi.org/10.1155/2012/891321,2012-11-27.
[17]YANG Y,ZHANG X,LUO Q,et al.Dynamic time division multiple access algorithm for industrial w ireless hierarchical sensor netw orks[J].China Communications,2013,10(5):137-145.
[18]ZHANG X,LIANG W,YU H,et al.Optimal convergecast scheduling for hierarchical w ireless industrial systems:performance bounds and tw o-stage algorithms[J].IET Communications,2015,9(1):88-100.
[19]TANG Z,CHENG M,ZENG P,et al.Real-time communication in WIA-PA industrial w ireless netw orks[A].Proceedings of 2010 3rd Computer Science and Information Technology[C].Chengdu:IEEE,2010.600-605.
[20]BUTTAZZO G.Hard Real-time Computing Systems:Predictable Scheduling Algorithms and Applications(Third Edition)[M].Virginia:Springer,2011.79-117.