计算机工程 ›› 2018, Vol. 44 ›› Issue (9): 280-285.doi: 10.19678/j.issn.1000-3428.0048623

• 开发研究与工程应用 • 上一篇    下一篇

基于贪心思想的调度表优化算法设计

方挺,王勇,褚文奎,谭小虎   

  1. 空军工程大学 航空工程学院,西安 710038
  • 收稿日期:2017-09-11 出版日期:2018-09-15 发布日期:2018-09-15
  • 作者简介:方挺(1993—),男,硕士研究生,主研方向为航电网络;王勇,副教授;褚文奎,讲师;谭小虎,硕士研究生。
  • 基金项目:

    航空科学基金(20165515001)。

Design of Scheduling Table Optimization Algorithm Based on Greedy Thought

FANG Ting,WANG Yong,CHU Wenkui,TAN Xiaohu   

  1. College of Aeronautics Engineering,Air Force Engineering University,Xi’an 710038,China
  • Received:2017-09-11 Online:2018-09-15 Published:2018-09-15

摘要:

时间触发以太网使用时间触发速率单调调度(TT-RMS)算法生成通信调度表时,存在RC消息不能在最大时延内到达、TT消息在错过时间窗后不能到达目的终端的问题。为此,设计一种基于贪心思想的调度表优化算法。通过规划新路径、分包与合包、更改TT消息发送时间3种方 式对通信消息进行改进,并构造一种代价函数评价每次生成的调度表,多次迭代直至代价值稳定后得到最终结果。仿真结果表明,相比改进的TT-RMS算法,该算法能够提高RC消息实时性,降低TT消息平均时延百分比。

关键词: 时间触发以太网, 速率单调调度, 贪心思想, 平均时延, 调度表

Abstract:

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.

Key words: Time-Triggered Ethernet(TTE), rate monotonic scheduling, greedy thought, average delay, scheduling table

中图分类号: