基于TTE的改进加权轮询调度算法

《基于TTE的改进加权轮询调度算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2017年8月第43卷第8期北京航空航天大学学报JournalofBeijingUniversityofAeronauticsandAstronauticsAugust2017V01．43No．8http：／／bhxb．buaa．edu．cnjbuaa@buaa．edu．cnDOI：10．13700／j．bh．1001—5965．2016．0590基于TTE的改进加权轮询调度算法张英静，何锋+，卢广山，熊华钢(北京航空航天大学电子信息工程学院，北京100083)摘要：在时间触发以太网(TTE)中，TT消息优先级最高，RC消息只能在TT消息调度的

2、离散时间片内传输，因此，TT消息离线调度表的设计会对RC消息调度产生一定影响。针对这一问题，提出了基于最优时间片的改进加权轮询(MWRR)调度算法。首先，通过TT消息约束条件限制获得’Ivr消息离线调度表，进而得到保证RC消息较大资源利用率的时间片信息；其次，在离散时间片对不同类型RC消息进行调度，并运用网络演算方法对其最坏端到端延迟进行分析；最后，通过实验仿真证实了本文算法不仅具有较低的复杂度和较好的公平性，保证了实际应用中算法的可行性，而且在时延性方面均优于先到先得(FIFO)、优先级(PQ)和加权轮询(WRR)调度算法。关键词：时间触发以

3、太网(7丌E)；调度算法；速率约束；加权轮询(WRR)；网络演算中图分类号：V247．5；TN914文献标识码：A文章编号：1001．5965(2017)08．1577-08时间触发以太网(Time—TriggeredEthernet，TTE)利用时钟同步保证全网在统一时钟下进行时间触发服务：通过离线调度表的规定时刻发送时间触发(Time—Triggered，TT)消息，保证TT消息传输的实时性¨‘2。。文献[3—4]提出了“priorischeduleporosity”调度算法，指出在TT消息发送间隔，进行速率约束(RateConstrain

4、t，RC)消息的调度发送。文献[5]在文献[3_4]基础上进～步提出了“posteriorischeduleporosity”调度算法。然而，这些算法均是针对TT消息的静态调度研究，并未对RC消息的动态在线调度进行分析。对于RC消息凋度算法，应从实时性、公平性和复杂度3个方面综合考虑。5⋯。现有调度算法中，先到先得(FirstInputFirstOutput，FIFO)是目前应用最广泛的算法，其调度简单，易于实现，但不能满足不同服务要求下的分组消息调度要求¨⋯；优先级(PriorityQueue，PQ)调度算法考虑到了分组消息的情况’91，然而

5、，高优先级的消息过多到来会严重影响低优先级消息的传输，公平性难以保证；加权公平队列(WeightedFairQueuing，WFQ)¨⋯、最坏情况下加权公平队列(Worst-caseFairWeightedFairQueuing，WF2Q)¨u虽具有较好的时延性和公平性，但其复杂度较大，影响RC消息调度的实时性，不适合其在线调度；加权轮询(WeightedRoundRobin，WRR)调度算法¨2’14。兼具公平性和时间复杂度低的特点。然而，上述调度算法均未考虑TT消息对RC消息的影响，因此不适用于TTE。针对TTE的特点，本文提出了基于最优时

6、间片的改进加权轮询(ModifiedWeightedRoundRobin，MWRR)调度算法。通过可满足性模理论(SatisfiabilityModuloTheories，SMT)E53计算出最利于RC消息传输的TT消息离线调度表，从而得到RC消息传输的最优时间片，在时间片内实现收稿日期：2016-07．13；录用日期：2016-09-02；网络出版时间：2016—11—1616：12网络出版地址：WWW．cnki．net／kcms／detail／11．2625．V．20161116．1612．005．html基金项目：国家自然科学基金(613

7、01086)；航空科学基金(20131951027)女通讯作者：E—mail：robinleo@buaa，edu．err引用格式：张英静，饲锋，卢广山，等．基于ⅡE的改进加权轮询调度算法【j]．北京航空航天大学学报，2017，43(8)：1577—1584．ZHANGYJ，HEF，LuGS，eta1．AmodifiedweightedroundrobinschedulingalgorithminTTE口J．JournalofBeltingUniversityofAeronauticsandAstronautics，2017，43f8)：1577

8、．1584(inChinese)．1578北京航空航天大学学报2017年不同类型RC消息的调度，仿真证明了本文算法在复杂性、公平性和时延性等多个方面均