基于贪婪随机自适应搜索法的TTE通信调度算法  

Scheduling algorithm of TTE network based on greedy randomized adaptive search procedure

作　　者：郑重[1] 何锋[1] 李浩若 熊华钢[1] 卢广山[1] ZHENG Zhong;HE Feng;LI Haoruo;XIONG Huagang;LU Guangshan(School of Electronic and Information Engineering,Beihang University,Beijing 100083,China)

机构地区：[1]北京航空航天大学电子信息工程学院,北京100083

出　　处：《北京航空航天大学学报》2021年第11期2268-2276,共9页Journal of Beijing University of Aeronautics and Astronautics

基　　金：国家自然科学基金(71701020)。

摘　　要：时间触发以太网(TTE)采用全局时间触发机制,使通信任务传输具有严格的时间确定性和无冲突性,适用于航空电子等混合关键应用领域。TTE网络提供3种不同的流量类型:具有低抖动和有界端到端延迟的时间触发(TT)流量,有限制端到端延迟的速率约束(RC)流量和无实时性保证"尽力传"(BE)流量。针对可满足性模理论(SMT)等调度算法在生成TT流量离线时刻调度表的过程中,未综合考虑TT流量路由和时刻调度表对RC流量延迟产生影响的问题,为了优化TTE网络实时性能,提出了一种基于贪婪随机自适应搜索算法的TTE通信任务调度算法。在TT流量离线调度表的生成过程中考虑了RC流量的最坏端到端延迟(WCD),在保证TT流量满足可调度性的前提下,通过路由规划和调度时刻表规划降低了RC流量的WCD。对比实验结果表明:所提算法可以有效的提升整网的实时性能,通过A380拓扑组网案例的对比分析,RC流量的平均延迟减少了14.34%。网络中流量规模越大,所提算法的收益越大。Time-Triggered Ethernet(TTE)makes communication tasks have strict determinacy and conflict free by global time-triggered mechanism,which is suitable for mixed critical application fields such as avionics.TTE network provides three different traffic types:Time-Triggered(TT)traffic with low jitter and bounded end-to-end delay,Rate Constrained(RC)traffic with limited end-to-end delay,and no real-time guaranteed"Best Effort"(BE)traffic.Aiming at the problem that Satisfiability Modulo Theories(SMT)and other methods do not consider the influence of TT traffic routing and scheduling on RC traffic delay in the process of generating the TT traffic scheduling timetable,in order to optimize the real-time performance of TTE network,this paper proposes a scheduling algorithm based on greedy randomized adaptive search procedure.The Worst-Case end-to-end Delay(WCD)of RC traffic is considered in the generation process of TT traffic offline scheduling timetable.Under the premise of ensuring the schedulability of TT traffic,the WCD of RC traffic is reduced by routing strategy and scheduling strategy.The comparative experimental results show that the proposed method can effectively improve the real-time performance of the network.Through the comparative analysis of A380 topology networking cases,the average delay of RC traffic is reduced by 14.34%.Also,the larger the network traffic scale,the greater the income of this method.

关 键 词：时间触发以太网(TTE) 贪婪随机自适应搜索 调度算法 优化设计 实时性分析 

分 类 号：V247[航空宇航科学与技术—飞行器设计] TP393[自动化与计算机技术—计算机应用技术]