基于贪心思想的调度表优化算法设计
|
摘要
时间触发以太网使用时间触发速率单调调度(TT-RMS)算法生成通信调度表时,存在RC消息不能在最大时延内到达、TT消息在错过时间窗后不能到达目的终端的问题。为此,设计一种基于贪心思想的调度表优化算法。通过规划新路径、分包与合包、更改TT消息发送时间3种方式对通信消息进行改进,并构造一种代价函数评价每次生成的调度表,多次迭代直至代价值稳定后得到最终结果。仿真结果表明,相比改进的TT-RMS算法,该算法能够提高RC消息实时性,降低TT消息平均时延百分比。
When Time-Triggered Ethernet( TTE) use Time-Triggered Rate Monotonic Scheduling( TT-RMS) algorithm to generate communication schedules,there is a problem that RC messages cannot arrive at the destination terminal within the maximum delay,and TT messages cannot reach the destination terminal after missing the time window. To solve this problem,a scheduling algorithm based on greedy thought is designed. By planning new paths,subpackages and packages,and changing TT message sending time,the communication messages are improved,and a cost function is constructed to evaluate the scheduling table that is generated each time,and the final result is obtained for multiple iterations until the value is stable. Simulation results show that,compared with the improved TT-RMS algorithm,the proposed algorithm can improve the real-time performance of RC messages and reduce the average delay percentage of TT messages.
When Time-Triggered Ethernet( TTE) use Time-Triggered Rate Monotonic Scheduling( TT-RMS) algorithm to generate communication schedules,there is a problem that RC messages cannot arrive at the destination terminal within the maximum delay,and TT messages cannot reach the destination terminal after missing the time window. To solve this problem,a scheduling algorithm based on greedy thought is designed. By planning new paths,subpackages and packages,and changing TT message sending time,the communication messages are improved,and a cost function is constructed to evaluate the scheduling table that is generated each time,and the final result is obtained for multiple iterations until the value is stable. Simulation results show that,compared with the improved TT-RMS algorithm,the proposed algorithm can improve the real-time performance of RC messages and reduce the average delay percentage of TT messages.
引文
[1]焦文喆,翟正军,王国庆.时间触发AFDX调度设计及实时性分析[J].计算机工程,2016,42(7):42-48.
[2]STEINER W,BAUER G,HALL B,et al.TTEthernet dataflow concept[C]//Proceedings of the 8th IEEE International Symposium on Network Computing and Applications.Washington D.C.,USA:IEEE Press,2009:319-322.
[3]刘晚春,李峭,何峰,等.时间触发以太网同步及调度机制的研究[J].航空计算技术,2011,41(4):122-127.
[4]STEINER W.Synthesis of static communication schedules for mixed-criticality systems[C]//Proceedings of the 14th IEEE International Symposium on Object/Component/Serviceoriented Real-time Distributed Computing.Washington D.C.,USA:IEEE Press,2011:11-18.
[5]TAMAS-SELICEAN D.Design of mixed-criticality applications on distributed real-time systems[D].Copenhagen,Denmark:Technical University of Denmark,2014.
[6]易娟,熊华钢,何峰,等.TTE网络流量转换策略及其延时性能保障调度算法研究[J].航空学报,2014,35(4):1071-1078.
[7]徐晓飞,曹晨,郭骏,等.TT-RMS:时间触发网络通信表生成算法[J].北京航空航天大学学报,2015,41(8):1403-1408.
[8]张超,南建国,褚文奎,等.改进的TT-RMS调度表生成算法[J].空军工程大学学报(自然科学版),2016,17(6):82-87.
[9]KOPETZ H,GRUNSTEIDL G.The time-triggered Ethernet(TTE)design[C]//Proceedings of the 8th IEEE International Symposium on Object Oriented Realtime Distributed Computing.Washington D.C.,USA:IEEE Press,2005:22-33.
[10]欧海斌,尹艳,熊建新.空基自组网中基于负载均衡的路由策略[J].计算机工程,2011,37(14):79-81.
[11]SAKET R,NAVET N.Frame packing algorithms for automotive applications[J].Journal of Embedded Computing,2006,2(1):93-102.
[12]WANG B,HOU J.Multicast routing and its QoS extension:problems,algorithms,and protocols[J].IEEE Network,2000,14(1):22-36.
[13]TAMAS-SELICEAN D,POP P,STEINER W.Synthesis of communication schedules for TTEthernet-based mixedcriticality systems[C]//Proceedings of International Conference on Hardware/Software Codesign and System.New York,USA:ACM Press,2012:473-482.
[14]STEIN S R,FILLER R L.Kalman filter analysis for real time applications of clocks and oscillators[C]//Proceedings of the 42nd Annual Frequency Control Symposium.Washington D.C.,USA:IEEE Press,1988:447-452.
[15]WANG Z,CROWCROFT J.Quality-of-service routing for supporting multimedia applications[J].IEEE Journal on Selected Areas in Communications,1996,14(7):1228-1234.
[16]TAMAS-SELICEAN D,POP P,STEINER W.Timing analysis of rate constrained traffic for the TTEthernet communication protocol[C]//Proceedings of IEEE International Symposium on Real-time Distributed Computing.Washington D.C.,USA:IEEE Press,2015:119-126.
[2]STEINER W,BAUER G,HALL B,et al.TTEthernet dataflow concept[C]//Proceedings of the 8th IEEE International Symposium on Network Computing and Applications.Washington D.C.,USA:IEEE Press,2009:319-322.
[3]刘晚春,李峭,何峰,等.时间触发以太网同步及调度机制的研究[J].航空计算技术,2011,41(4):122-127.
[4]STEINER W.Synthesis of static communication schedules for mixed-criticality systems[C]//Proceedings of the 14th IEEE International Symposium on Object/Component/Serviceoriented Real-time Distributed Computing.Washington D.C.,USA:IEEE Press,2011:11-18.
[5]TAMAS-SELICEAN D.Design of mixed-criticality applications on distributed real-time systems[D].Copenhagen,Denmark:Technical University of Denmark,2014.
[6]易娟,熊华钢,何峰,等.TTE网络流量转换策略及其延时性能保障调度算法研究[J].航空学报,2014,35(4):1071-1078.
[7]徐晓飞,曹晨,郭骏,等.TT-RMS:时间触发网络通信表生成算法[J].北京航空航天大学学报,2015,41(8):1403-1408.
[8]张超,南建国,褚文奎,等.改进的TT-RMS调度表生成算法[J].空军工程大学学报(自然科学版),2016,17(6):82-87.
[9]KOPETZ H,GRUNSTEIDL G.The time-triggered Ethernet(TTE)design[C]//Proceedings of the 8th IEEE International Symposium on Object Oriented Realtime Distributed Computing.Washington D.C.,USA:IEEE Press,2005:22-33.
[10]欧海斌,尹艳,熊建新.空基自组网中基于负载均衡的路由策略[J].计算机工程,2011,37(14):79-81.
[11]SAKET R,NAVET N.Frame packing algorithms for automotive applications[J].Journal of Embedded Computing,2006,2(1):93-102.
[12]WANG B,HOU J.Multicast routing and its QoS extension:problems,algorithms,and protocols[J].IEEE Network,2000,14(1):22-36.
[13]TAMAS-SELICEAN D,POP P,STEINER W.Synthesis of communication schedules for TTEthernet-based mixedcriticality systems[C]//Proceedings of International Conference on Hardware/Software Codesign and System.New York,USA:ACM Press,2012:473-482.
[14]STEIN S R,FILLER R L.Kalman filter analysis for real time applications of clocks and oscillators[C]//Proceedings of the 42nd Annual Frequency Control Symposium.Washington D.C.,USA:IEEE Press,1988:447-452.
[15]WANG Z,CROWCROFT J.Quality-of-service routing for supporting multimedia applications[J].IEEE Journal on Selected Areas in Communications,1996,14(7):1228-1234.
[16]TAMAS-SELICEAN D,POP P,STEINER W.Timing analysis of rate constrained traffic for the TTEthernet communication protocol[C]//Proceedings of IEEE International Symposium on Real-time Distributed Computing.Washington D.C.,USA:IEEE Press,2015:119-126.