标题 | FlexRay动态段带宽利用率优化研究 |
范文 | 吴俊鹏 周美娇 张凤登 阮彪 庞淞友
摘 要:为提高大型网络的FlexRay动态段带宽利用率,采用时隙复用的方法对FlexRay动态段消息调度进行优化。在深入分析FlexRay动态段带宽利用率表达式及整体消息最坏响应时间的基础上,确定影响动态段带宽利用率的关键因素,并根据可调度分析方法建立动态调度模型。该模型以优化动态段带宽利用率为目标,采用启发式调度算法构建消息的动态调度方案,从而得出最优的动态段长度配置和帧ID配置,以降低负载、提升网络带宽利用率。最后,以FlexRay底盘综合控制与安全系统为对象,对上述算法进行验证。实验结果证明,启发式调度算法可以优化动态段帧ID配置,动态段带宽利用率在总线速率为5Mbit/s、10Mbit/s时分别提高了6.22%与10.23%。 关键词:FlexRay;带宽利用率;最坏响应时间;时隙复用;调度 DOI:10. 11907/rjdk. 192131 开放科学(资源服务)标识码(OSID): 中图分类号:TP393文献标识码:A 文章编号:1672-7800(2020)007-0171-07 Research on Bandwidth Utilization Optimization of FlexRay Dynamic Segment WU Jun-peng, ZHOU Mei-jiao, ZHANG Feng-deng,RUAN Biao,PANG Song-you (School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093,China) Abstract:In order to improve the bandwidth utilization of FlexRay dynamic segments of large networks, this paper optimizes the scheduling of FlexRay dynamic segment messages by using slot multiplexing. Based on the in-depth analysis of the FlexRay dynamic segment bandwidth utilization expression and the worst case response time of the overall message, the key factors affecting the bandwidth utilization of the dynamic segment are determined, and a dynamic scheduling model is established according to the schedulable analysis method. The dynamic segment bandwidth utilization is the target, and a heuristic scheduling algorithm is used to construct a dynamic scheduling scheme of the message, thereby obtaining an optimal dynamic segment length configuration and frame ID configuration to reduce load and increase network bandwidth utilization. Finally, this paper verifies the above algorithm with the FlexRay chassis integrated control and security system as the object. The experiment proves that the heuristic scheduling algorithm can optimize the dynamic segment frame ID configuration, dynamic segment bandwidth utilization were increased by 6.22% and 10.23%, respectively at bus rates of 5 Mbit/s and 10 Mbit/s. Key Words: FlexRay;bandwidth utilization;worst case response time;slot-multi 0 引言 隨着用户对汽车安全性和舒适性的要求不断提高,新增的电子功能模块越来越多,数据通信量也随之增大,传统车载总线已不能满足人们对汽车网络可靠性及确定性的传输需求。FlexRay是汽车应用中的一种高速通信协议,主要遵循冲突避免时间触发通信模式,兼顾了时间触发报文与事件触发报文传输,具有高吞吐量,以及确定性、容错性和灵活性等特点,能够满足未来对先进汽车高速实时控制的需求。 FlexRay动态段主要用于非确定性事件触发的非周期性消息传输,消息传输主要采用基于优先级的动态时隙分配方式,存在较长的响应时间。文献[1]分析了动态段的消息调度,在动态段的可调度性分析基础上提出动态规划的优化调度算法,但没有从整体上考虑通信周期中静态段与动态段的可调度性问题;文献[2]运用保留带宽的思想,为实现最大化周期负载与最小化带宽保留建立相应数学模型,并寻求最优方案;文献[3]对FlexRay动态段内的消息传输特性进行详细分析,并提出构建消息组的调度方法;文献[4]在分析动态消息传输最坏响应时间基础上建立动态消息调度问题模型,以所有动态消息最坏响应时间之和最小为目标,提出基于类DM(截止期单调调度算法,Deadline-Monotonic)的启发式调度算法;文献[5]分析动态段消息调度,在综合考虑动态段带宽利用率和最坏响应时间基础上提出类DM消息调度优化算法,但没有考虑到传输抖动和丢包率问题。本文在深入分析FlexRay动态段带宽利用率表达式和整体消息最坏响应时间的基础上,对帧格式和消息传输规则进行深入研究。采用启发式调度算法构建消息的动态调度方案,从而得出最优的动态段长度配置和帧ID配置。最后,以FlexRay底盘综合控制和安全系统为应用背景,对上述算法进行验证。 1 FlexRay通信协议 FlexRay为汽车提供了高级通信技术,其单个通道上的最大传输速率可达到10Mbps,双通道总数据速率可达到20Mbps。当采用冗余通道通信时,提供了传输容错机制,当采用非冗余通道通信时,提高了带宽,整个协议是基于时间触发架构的,实现了确定性通信。 1.1 帧格式与编码 FlexRay帧格式[6-7]由3部分组成,分别为头段(head segment)、负载段(payload segment)与尾段(trailer segment)。节点在网络上传输数据帧时,首先传递帧的头段,然后是有效负载数据段,最后是帧的尾段。在传输过程中,按照如图1所示从左向右的顺序进行。 (1)头段前5位依次为保留位、有效负载预指示位、空帧指示位、同步帧指示位与启动帧指示位;接下来为11位帧ID(frame ID),用于定义消息帧在每个通信周期里的发送时隙;负载段长度为7位(Payload length),动态段帧的负载段长度根据传输消息的长度而变化;头段CRC校验(Header CRC)长度为11位,用于判断传输数据的正确性;周期计数值(cycle count)长度为6位。 (2)负载段长度可以进行配置,但必须在0~127个字之间。 (3)尾段为3个字节的CRC校验位。 动态帧负载段的数据0、1两个字节通常作为消息ID(message ID),该标识符用于接收节点、滤除数据并获得有效数据部分,如图2所示。 动态帧编码规则如图3所示,编码时会额外加上传输起始位(TSS)、帧起始位(FSS)、字节起始位(BSS)、帧结束位(FES),动态消息帧会再添加动态尾部序列(DTS)。 1.2 FlexRay媒体访问机制 FlexRay的媒体访问控制是基于柔性时分多路的(Flexible Time Division Multiple Access,FTDMA)访问机制[8],其通信周期由4部分组成,分别是静态段(Static Segment,SS)、动态段(Dynamic Segment,DS)、符号窗口(Symbol Window,SW)和网络空闲时间(Network Idle Time,NIT)。 1.3 动态段传输与时间特性 本文针对整个网络动态段的消息调度,在假设已完成具有周期性消息静态调度的基础上,即已知通信周期Tc、静态段长度Tst与所需的静态时隙总个数FA,继续研究动态段的消息调度。该部分主要包括动态段长度、动态微时隙个数优化配置以及动态非周期性消息ID优化方案。 FlexRay动态段由动态时隙构成,而组成动态时隙的是微时隙。微时隙由宏节拍(MT)组成,动态时隙长度随着传输消息的长度而变化。在动态段内,基于动态最小时隙的访问机制用于仲裁传输,并且主要用于非周期性消息传输,动态段的可用带宽可根据实际需求进行动态分配。动态段包含固定数目NDS个微时隙,该参数在设计阶段进行配置,NDS最大值为7 994。FlexRay动态段消息真正的传输起始时刻从微时隙触发点开始,到下一个微时隙触发点终止。微时隙起始点至微时隙触发点之间的时间间隔称为微时隙触发点偏移量(gdMinislotActionPointOffset)。动态时隙由两部分组成:动态时隙传输相与动态时隙空闲相,动态时隙空闲相是指检测通信信道空闲的等待时间。动态段时序如图4所示。 动态段消息不具有严格意义上的发送周期,一般将每个信号独立地封装为消息再进行調度。在FlexRay通信系统中,消息都是以帧的形式进行传输,动态帧编码方式是在静态段编码基础上加上动态尾部序列LDTS,在动态段内传输一个大小为n字节的信号数据,则以微时隙TMS为单位的动态时隙长度如下所示[9]: 其中,29为TSS(这里取15位)、FSS(1位)、FES(2位)与11位的通信空闲间隔符(CID)之和;10n表示帧头、负载段和帧尾位数与添加了字节起始位后所得位数之和;TAPO表示微时隙触发点偏移时间长度(gdActionPointOffset);LDTS的值是变化的,可以取2gdBit~LMS+2gdBit之间的任意值;gdBit表示1个比特位的传输时间。FlexRay通信周期的时间单位是宏节拍(MT),1个宏节拍的取值范围在1~6μs之间。一个微时隙TMS由若干个宏节拍组成,时间长度是可以配置的,一旦确定则不能变化。 动态段带宽利用率主要用于分析配置的动态段长度TDYN对动态带宽利用率的影响[10]。设系统中存在n个动态消息,各消息长度记为li,为了进行数学建模分析,假设动态消息周期pi为消息mi连续两次产生的最短时间间隔,mi截止时间记为di,且满足pi≥di,在本文设计中取每个消息的截止时间等于其周期,即pi=di,pi取最小间隔时间,在静态段设定的NTC个通信周期Tc内计算动态段带宽利用率为: 动态段带宽利用率UDYN反映在整个网络循环周期内所分配的所有动态段内,有多少用于实际动态段的消息传输。通过分析上述公式可知,动态段长度越小,则其带宽利用率越大,但动态段过小又会使得消息延迟更久,影响传输的实时性。由于动态段发送消息的时刻具有不确定性,因此需要进一步分析各个消息的最坏响应时间。 2 动态段消息调度优化方案 由于动态段具有非周期性,所以动态段调度更为复杂,主要通过帧ID确定的优先级实施调度。动态报文的优先级有两层含义:首先报文本身的优先级,由报文的Message ID进行定义,用于节点内部消息报文的排队,相当于事件触发系统中用来表示报文重要性的优先级;其次帧ID所决定的发送优先级,其具有时间触发特性,用于保证系统的实时性。为了简化系统,仅考虑动态报文的发送优先级。 帧ID配置为低的动态消息的优先级更高,高优先级消息传输可能会导致低优先级消息延迟。动态消息长度不同,也会影响其它动态消息传输。为了使动态消息能在对应截止时间之前传输完毕,必须对各消息的最坏响应时间[11]进行分析,并尽量减少延迟,以提高动态消息传输的实时性。 本文采用时隙复用[12]对FlexRay动态段的最坏响应时间进行分析,主要由于两方面原因:首先,其是对之前大多数动态段实时性研究的一个扩展,大多都是假定所有消息在每个周期内都存在调度机会,而新版本提出支持时隙复用的物理层和链路层机制,所以将其作一般化分析,同时也适用于前期的特殊情况;其次,避免了高优先级消息一直触发而使低优先级消息产生延迟,导致低优先级消息不能在截止时内传输出去,影响了系统的实时性。 在对最坏响应时间进行分析时,为了简化分析,对该调度分析前提作出如下假设: (1)各个消息mi的基周期bi、循环周期ri与截止时间di已知。 (2)每个节点的[pLatestTxmi]值已知。 (3)网络忽略抖动因素,以及传输节点与接收节点中的最大延迟。 (4)每个消息mi在一个通信周期内只触发一次,且发送时不存在发送错误的情况[13]。 通信控制器决定消息在固定时隙被发送到总线上。动态段长度和帧ID的分配方式决定了动态段最坏响应时间,动态段最坏响应时间可表示为: σm表示消息被触发当前周期的最长延迟时间。最坏情况是指消息mi在其时隙刚开始之后才被触发,因此消息mi错过了其发送时隙,以及在当前周期不触发其它FID消息,这将使消息m处于等待状态,直到下个周期才可能进行调度,其表达式为: FIDmi表示消息mi所分配的帧ID号,TMS表示动态微时隙。 [ωmi(t)]表示在给定时间间隔t中,因为使用同一帧ID但具有不同ri的动态消息、低帧标示符(更高优先级)消息、不传输消息时所占用的微时隙以及静态帧所导致的最大延迟。 主要从3个方面影响该[ωmi(t)]延迟: (1)消息mi存在时隙复用。 (2)低帧标示符(更高优先级)的消息[mj∈lf(mi)=][{IDmi (3)比消息mi标识符小,但未用于消息传输的动态段时隙。 [lmi]表示消息mi在传输周期内产生的最大延迟,在最坏的情况下,该消息在本周期所能允许的最坏时刻传输,即微时隙计数值为[pLatestTxmi],消息mi才传输至总线上,则存在: Cm表示消息mi通信占用的时间,忽略传输节点与接收节点中的最大延迟,假设消息mi负载段的有效数据长度为n个字节,与公式(1)相结合,则有: 2.2 延迟周期分析 由消息mi时隙复用本身所产生的延迟和具有低帧标示符的消息mi所产生的延迟为一个或多个周期,所以可表示为: 上式由两部分组成,[smi]表示由消息mi时隙复用本身所产生的延迟周期个数,[lsmi]表示具有低帧标示符的消息mi所产生延迟的周期个数。在分析基于时隙复用的动态段消息最坏响应时间之前,首先分析两种情况: (1)[mj∈lf(mi)={IDmj (2)mi消息存在时隙复用,其它消息[mj∈lf(mi)=][{IDmj 对于第一種情况,在每个周期[cc={0,1,?,NTC-1}]中,只要消息mj能满足[ccmodrj=bj],那么该高优先级消息在周期cc可能会对消息mi产生延迟。设满足该条件消息的集合为[mj,cc={?mj∈lf(mi)ccmodrj=bj}],接下来建立相应模型,分析在上述条件下会对消息mi产生几个周期的延迟,设为s1表示延迟的周期数。 如果消息在周期cc正好错过消息的发送时隙,通过上述分析可求解σm。需要讨论在cc=cc+1之后的各个周期里,各消息是否会对消息mi的传输产生延迟,即[mj,cc={?mj∈lf(mi)ccmodrj=bj}]内的各个消息是否对消息mi产生延迟,该问题可以转化为一维装箱问题。设[mj,cc,k,f∈mj.cc],其中k为在该周期可发送的消息编号,f表示该消息的帧ID号,其数据长度为[Cj,cc,k,f]。为每个周期建立一个二进制的变量[Xj,cc,k,f],如果消息[mj,cc,k,f∈mj.cc],在周期cc发送,则为1,不发送则为0,在最坏情况下存在: 其中,二进制变量yi等于1,表示该周期cc对消息mi产生一个周期的延迟。该变量取值受到消息mi的[pLastestTxmi]约束,即如果以下两式成立,则yi为1,会对消息mi产生延迟。 依次讨论在cc=cc+1后的各个周期里,低帧ID的消息在总线上传输是否会造成消息mi的延迟[15],即确定yi的值,再对其累加得到总延迟周期个数s1,直到在某个周期内,如果该周期下的负载[Loadi>pLastestTxi×TMT],消息mi可在该周期内发送。 对于第二种情况,待分析的消息mi是时隙复用的,其它消息在每个周期均具有调度机会,则至少存在ri-1个周期的延迟。在消息mi不能调度的周期内,其它消息不会对其造成延迟,但在能够调度mi的周期内,仍然需要考虑低优先级对其产生的延迟,在该情况下产生的总延迟用s2表示。 同理,在cc+ri周期内分析高优先级消息是否会对消息mi的传输产生延迟,如果该周期下的负载[Loadi>pLastestTxi×TMT],则在该周期仍不能发送,将再延迟ri-1个周期,然后再次分析是否会被延迟,直到消息mi能够发送为止。 基于上述分析可以得到,当消息mi在周期cc错过发送时隙时,则在cc+ri的周期内分析以下变量,当高优先级消息负载超过了消息最后能够调度的截止时间时,zi等于1,否则为0,存在: 在调度周期[cc={0,1?,NTC-1}]内,在每个消息mi能够调度的周期内求解zi的值,一旦存在zi=0则停止,表示消息mi可以被发送,然后对其值求和,表示在消息mi能够调度的周期内发生了延迟,即满足: 由上述分析可知,在该情况下能够产生的延迟周期数为: 上述两种情况属于时隙复用的特殊情况,针对一般消息调度分析动态段的最坏响应时间,在已完成时隙分配的基础上进行分析。假设在调度过程中的延迟期间不存在需要再次发送的消息,即假设q=1,以及各个消息的循环周期为ri∈{2k,k∈[0,1,2,3,4,5,6]},也即2的权重。该假设是为了简化动态段调度的复杂性,同时也与OSEK实时系统完全兼容,具有一定的可行性。设cci0=cci+1为总线周期的初始周期序数值,以及初始化消息延迟的周期个数s=0。该分析过程以cc=cc0+s循环分析各周期产生的延迟情况,下面将通过一个流程图描述求解s的过程,如图5所示。 综合以上分析可知,在时隙复用的条件下存在[smi+lsmi=s],也即[wmi(t)=s×Tc],可得出消息的最坏响应时间。 本文分析的消息mi在最坏响应情况下能够发送,则其必定能在任何时刻完成相应调度。每个消息mi的最坏响应时间满足: 同时可以得出FlexRay动态段消息的整体最坏响应时间WR为: 动态段长度和时隙复用下的FID分配会对消息响应时间和动态段带宽利用率产生影响。假设已知网络中所有动态段消息的时间参数,本文调度方案考虑优化所有消息的最坏响应时间,同时提高动态段带宽利用率。为了得到最佳的动态段长度和基于时隙复用的FID分配方案[16-19],建立如下优化模型: 其中,α、β分别表示动态段未有效利用的带宽利用率1-UDYN和动态段消息整体最坏响应时间WR的权值,可以依据系统进行相应配置。 为了简化调度,设置所有动态段消息的ri∈{1,2,4,8,16,32,64}≤NTC-1取相同值,但各个消息的bi∈{0,1,…,ri-1}以及帧ID是不同的。这里借鉴DM调度算法,截止时间与可调度性有关,任务执行时间同样也会影响可调度性,但任务中所要传输的消息越长,越容易超过截止时间。所以消息长度越长,优先级应该越高,即分配的帧ID应该越小。本文采用截止时间与消息长度之差表示消息的紧急等级,即截止时间越小,动态消息传输时间越长,紧急程度则越高,配置的bi和帧ID也越小。动态段调度优化步骤如下: (1)动态段ri∈{2,4,8,16,32,64}≤NTC-1均取相同值,即最多存在7種循环周期的消息,消息截止时间与消息长度差值越小,对应优先级越高,基周期bi∈{0,1,…,ri-1}和帧ID也越小。 (2)建立该方案下的动态段长度TDYN≤Tc -Tst与消息响应时间WR的拟合关系,选取最小WR及其对应动态段长度作为该方案下的最优动态段长度,并计算该方案下的动态段带宽利用率UDYN。 (3)计算目标函数F,对所有分配方案进行计算后,求出使F取最小值的参数解及其对应的分配调度表。求解过程如图6所示。 3 动态段消息调度优化结果分析 本文以底盘综合控制与安全系统为例,构建具有较多数据量的FlexRay网络,用于验证本文提出的消息调度优化方案的可行性。该系统主要由电子稳定控制系统(ESC)、车辆自适应系统(ACC)、用于汽车发动机管理系统和自动变速器控制系统的FlexRay-CAN网关系统(GW)、电动助力转向系统(EPS)、连续减震控制系统(CDC)、空气悬挂系统(ASC)共6个子系统组成,系统总线结构如图7所示。 每个系统对应不同节点,该系统的动态消息集合如表1所示[15]。 在对该系统进行动态段调度分析时,取微时隙等于一个宏节拍,即TMT=TMS,并且设定LDTS=4bits。由于动态消息的非周期性,为了便于分析与调度,假设动态消息周期pi的值为连续两次产生消息mi的最短时间间隔di,α=β=0.5。为了验证本文提出调度方法的有效性,通过两种方式进行对比验证:一是采用文献[4]的方式进行消息调度,即不进行时隙复用;二是采用本文提出的方法进行验证,分别得出动态消息的消息帧ID配置,以及对应的整体最坏响应时间,在总线速率为5Mbit/s和10Mbit/时,总线利用率分别提高了6.22%和10.23%。对比验证结果如表2所示。 从上述结果可知,本文优化方案计算出的动态段长度TDYN=46μs。同时通过分析可知,本文方案在一定程度上增加了整体最坏响应时间,但提高了动态段带宽利用率,其所对应帧ID配置方案如表3所示。 通过分析表2、表3可知,把相同的帧ID在不同通信周期下分配给不同消息帧时,虽然可以缩短动态段长度,提高动态段带宽利用率,但提升了整体最坏响应时间,在对实时性要求较高的场合,如果网络消息帧不是特别庞大,且所有动态消息可置于一个周期内发送时,可以不采用时隙复用的调度分配方式,以达到更好的效果,即与本例得出的结果相同。同时,本例所用于对比的调度方式其实也是本文提出调度方法中的一个特例,即令所有消息帧的循环周期ri=1,基周期bi=0,所以本文提出的方法具有一定的理论价值。 4 结语 在研究FlexRay的动态段消息调度优化问题时,既考虑最坏响应时间,又考虑动态段带宽利用率,采用启发式调度算法构建整体的动态消息调度方案,得出时隙复用下的FID分配表与最佳动态段长度,使在单位时间内可以发送更多消息,从而降低了系统负载,提升了网络带宽利用率。仿真结果表明,该调度算法为各动态消息配置帧ID,消息时隙复用相比消息时隙不复用的动态带宽利用率,在总线速率为5Mbit/s与10Mbit/s时分别提高了6.22%和10.23%。但是本文提出的动态调度方案主要是进行理论方面的分析与验证,而未在实际系统中进行测试,因此对于实际带宽利用率仍有待进一步研究。 参考文献: [1] 顾嫣,张凤登. FlexRay动态段优化调度算法研究[J]. 自动化仪表,2009,30(12):25-29. [2] 夏凤仙. FlexRay车载网络调度算法研究[D]. 合肥:合肥工业大学,2011. [3] SCHMIDT E G,SCHMIDT K. Message scheduling for the flexray protocol:the dynamic segment[J]. IEEE Transactions on Vehicular Technology,2009,58(5):2160-2169. [4] 郑文学. 车载网络FlexRay调度方案优化设计研究[D]. 杭州:浙江大学,2013. [5] 张良玉,王义,杨乘. FexRay汽车总线调度算法优化研究[D]. 贵阳:贵州师范大学,2019. [6] 张凤登. 分布式实时系统[M]. 北京:科学出版社,2014. [7] 陈珊,尚丽辉,张凤登. FlexRay 静态段消息调度优化研究[J]. 计算机应用研究,2020,37(1):112-117. [8] KIM B, PARK K. Analysis of frame delay probability in the FlexRay dynamic segment[J]. Industrial Informatics, 2011(7):1519-1522. [9] 王越飞,刘红军,吴哗,等. 基于最优传输可靠度的FlexRay网络参数配置[J]. 合肥工业大学学报,2018,47(7):915-920. [10] 王跃飞,殷健力,张利,等. 基于时间约束的汽车FlexRay网络动态段参数设计[J]. 中国机械工程,2014,25(15):2070-2075. [11] ZENG H,GHOSAL A,NATALE M D. Timing analysis and optimization of FlexRay dynamic segment[C]. 10th IEEE International Conference on Computer and Information Technology,2010:1932-1939. [12] NEUKIRCHNER M,NEGREAN M,ERNST R,et al. Response-time analysis of the F1exRay dynamic segment under consideration of slot-multiplexing[C]. 7th IEEE International Symposium on Industrial Embedded Systems(SIES),2012(7):21-30. [13] 陳宇,熊光泽. 单调时限调度算法的可调度分析[J]. 计算机工程与应用,2001(23):19-21. [14] TANASA B,BORDOLOI U D,KOSUCH S,et al. Schedulability analysis for the dynamic segment of F1exRay: a generalization to slot multiplexing[J]. Real-Time and Embedded Technology and Applications Symposium(RTAS), 2012(18): 185-194. [15] 魏志强,张凤登. 基于FlexRay线控转向系统的传输延时算法[J]. 电子测量技术,2016,39(9):82-86. [16] 谢梦如. F1exRay总线系统实时调度方法[D]. 合肥:合肥工业大学,2014. [17] 殷健力. 汽车F1exRay网络动态段调度及优化配置研究[D]. 合肥:合肥工业大学,2014. [18] 张良玉,王义,张育贵,等. FlexRay 动态段消息调度优化算法[J]. 计算机与现代化,2018(5):11-15. [19] PARK I,SUNWOO M.FlexRay network parameter optimization method for automotive applications[J]. IEEE Transactions on Industrial Electronics, 2011,58(4):1449-l459. (责任编辑:黄 健) plexing;scheduling |
随便看 |
|
科学优质学术资源、百科知识分享平台,免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。