汽车FlexRay网络静态段帧封装机制研究

王跃飞　张　恒　张亚生　刘红军

1.合肥工业大学,合肥,230009　2.安全关键工业测控技术教育部工程研究中心,合肥,230009

汽车FlexRay网络静态段帧封装机制研究

王跃飞1,2张恒1,2张亚生1刘红军1

1.合肥工业大学,合肥,2300092.安全关键工业测控技术教育部工程研究中心,合肥,230009

在分析FlexRay消息帧格式和帧编码的基础上,推导出静态时隙长度和总线利用率计算公式,分析了影响总线利用率的主要因素;提出帧封装的前提条件，给出了帧有效负载段上下限精确计算方法；在此基础上，以超周期内总线利用率最高为优化目标，建立了解决帧封装问题的整数线性规划模型，并给出求解该模型的启发式算法。SAE实验结果证明该方法不仅能够提高总线利用率，而且可有效缩短算法执行时间。

FlexRay总线；静态时隙；总线利用率；帧封装

0　引言

随着人们对汽车安全性、舒适性的需求不断增加，现代汽车逐渐向电子化、网络化和智能化方向发展，车内电子控制单元(electronic control unit,ECU)的数量越来越多,ECU间高速实时的通信需求也越来越大[1-2]。相对于CAN总线,具有高带宽、高容错能力的FlexRay总线更能适应现代汽车的需求,是事实上的下一代汽车总线[3-4]。

在FlexRay网络中,信号是以消息帧的形式进行数据传输的。因此，帧封装问题成为整个汽车网络设计的关键问题之一。目前，国内外学者已经开始对汽车FlexRay网络中帧封装问题进行研究[5-12]。文献[5-7]对FlexRay静态段帧封装进行了研究，其中,Kang等[5]提出将数据长度较大的消息分配到动态段发送,以减少带宽消耗,但未给出该方法的数学模型及算法复杂度;Kang等[6]提出基于BCMVPS(band width consumption minimizing with various periodic signals)的信号封装算法,该算法允许不同周期的信号封装在一起,能够有效地降低带宽消耗,但该方法没有考虑因不同周期的信号封装在一起,造成较大周期的信号多次发送,极大地浪费了带宽。文献[8-9]对FlexRay静态段和动态段帧封装进行了研究,其中Schmidt等[8]建立了解决帧封装问题的整数线性规划模型,但该模型没有考虑通信周期的最大范围,并且在帧封装机制上只允许同周期的信号封装在一起。文献[10-12]对FlexRay静态段优化设计进行了研究,其中，Jang等[10]提出优化FlexRay网络参数的两步设计方法,以协议附加载荷和网络空闲浪费最小为目标函数，通过帧封装优化静态时隙长度，通过帧调度优化通信周期长度,但在求解最优静态时隙时,没有考虑静态时隙的精确范围，不能有效地缩短算法执行时间;王跃飞等[11]提出基于最小时间碎片的静态段设计方法，以时间碎片最小为优化目标，在共用时隙的情况下进行信号封装，但没有给出具体的求解算法。

在以上研究的基础上,本文针对FlexRay网络静态段,提出总线利用率概念，以超周期内总线利用率最高为优化目标，建立解决帧封装问题的整数线性规划模型，并给出求解该模型的启发式算法。

1　FlexRay协议

1.1帧格式与帧编码

FlexRay消息帧[13]由帧头、有效负载数据段和帧尾三部分组成。如图1所示,帧头由5个字节(1位保留位、1位有效负载预先指示位、1位空帧指示位、1位同步帧指示位、1位启动帧指示位、11位帧ID、7位有效负载数据长度、11位帧头循环冗余校验(CRC)、6位周期计数)组成,有效负载数据段由0～254个字节组成,帧尾由3个字节的帧CRC组成。

图1　帧格式与帧编码

FlexRay消息帧在传输时需要对其进行编码。图1表示传输一个有效负载数据长度为l个字节的消息帧的编码过程，其中,TSS表示传输起始序列,FSS表示帧起始序列，BSS表示字节起始序列，FES表示帧结束序列。

1.2媒体访问控制

FlexRay总线以通信周期循环的方式传输消息。如图2所示,一个通信周期包括静态段(static segment,SS)、动态段(dynamic segment,DS)、符号窗口(symbol window,SW)和网络空闲时间(network idle time,NIT)四个部分。静态段由若干个等长的静态时隙(static slot)组成，主要用来传输基于时间触发的周期性消息，采用时分多址(time division multiple access,TDMA)媒体访问机制来保证消息传输的确定性；动态段由若干个等长的最小时隙(minislot)组成，主要用来传输基于事件触发的偶发性消息，采用柔性时分多址(flexible TDMA,FTDMA)媒体访问机制进行仲裁传输。

图2　FlexRay通信周期

2　总线利用率计算方法

2.1静态时隙长度

FlexRay静态段被划分为若干等长的静态时隙,每个消息帧对应唯一的时隙。由图1可知,当消息帧在静态段发送时,除了进行帧编码,还需要添加通信空闲分隔符(communication idle delimiter,CID)和行动点偏移量(action point offset,APO)。其中,APO在静态时隙开始处,长度为1～63个宏节拍(macrotick,MT)时间。

设FlexRay网络有n个节点,通信周期长度为Tbus，静态段长度为Tss，静态时隙长度为tst,静态时隙数目为Nst，则

Tss=tstNst

(1)

由FlexRay传输协议可知，静态时隙长度tst必须大于或等于传输最长消息所需的时间。则tst可由下式求得:

(LBSS+8)+δ]+LAPO)

(2)

δ=LTSS+LFSS+LFES+LCID

(3)

其中，LTSS、LFSS、LBSS、LFES、LCID、LAPO分别表示TSS、FSS、BSS、FES、CID、APO的长度。

将表1中FlexRay网络参数值代入式(2)、式(3)，经计算得

(4)

2.2总线利用率

定义1总线利用率(bus utilization rate,BUR)。一段时间内,FlexRay总线用于传输有效数据所占用的时间与总时间之比为总线利用率,用TBUR表示。由于本文只研究静态段帧封装,故总时间只考虑静态段长度。

定义2超周期。FlexRay网络中所有信号发送周期的最小公倍数(least common multiple,LCM)为超周期,其长度记为TSP。则

(5)

式中，LCM()为求最小公倍数函数。

表2所示为一个FlexRay网络信号集合,该网络由3个节点组成,节点1由3个发送周期为2 ms的信号组成,节点2由3个发送周期为3 ms和2个发送周期为1 ms的信号组成,节点3由3个发送周期为4 ms的信号组成,则TSP=LCM(1,2,3,4)=12 ms。

FlexRay网络一个超周期内总线利用率可由下式求得

(6)

由式(6)可知,在信号参数、通信周期已知的情况下,超周期内信号所占用的有效带宽是一定的，总线利用率TBUR与静态段长度Tss成反比，即静态时隙长度tst与时隙数目Nst的乘积越小，总线利用率越高，即总线上传输有效数据所占用的比例越高，带宽浪费越少。

表2　FlexRay信号集合

3　帧封装

帧封装即把节点信号封装成帧的过程。由FlexRay协议可知，如果每个信号单独作为一帧进行数据传输，由于帧格式及帧编码将会造成很大的带宽浪费，因此，在实际网络中，必须将多个信号封装成帧进行数据传输，而这一过程可以抽象为开放式的装箱问题，即将不同长度的信号作为待装物品，而帧的有效负载段作为承载物品的箱子，箱子的容量即帧负载段长度是可变的。如何选取合适的帧负载段长度，使得所有信号封装成帧后的总线利用率最高是解决帧封装问题的关键。

3.1帧封装前提条件

为了更准确地研究该问题，本文作出如下假设：

(1)在FlexRay通信系统内没有出现消息发送失败及数据传输错误等故障；

(2)FlexRay网络中所有信号的发送周期、数据位长度、截止期是已知的,并且发送周期与截止期相等；

(3)所有信号的发送周期都是通信周期Tbus的整数倍;

(4)只有相同ECU的信号才能被封装成一帧，并且每个信号的发送周期必须是帧的发送周期的整数倍。

由假设(3)可知,通信周期长度Tbus为所有信号发送周期的最大公约数(greatest common divisor,GCD),即

(7)

式中，GCD()为求最大公约数函数。

由FlexRay协议可知,通信周期计数器取值范围是0～63，因此，周期性信号的发送周期不能超过64Tbus。

(8)

3.2帧有效负载段长度上下限

帧封装的关键在于帧有效负载段长度的选取。设帧有效负载段长度为Lpl(以字为单位)，由FlexRay协议可知，2字≤Lpl≤127字,为了更精确地确定Lpl上下限，作出如下定义。

(9)

(10)

(11)

(12)

3.3封装模型的建立

(13)

设消息封装后,节点i中帧的数目为Ni,则

(14)

静态时隙数目Nst为

(15)

(16)

(17)

根据上述相关内容,建立解决帧封装问题的整数线性规划(ILP)模型：

(18)

(19)

(20)

(21)

Tss

(22)

(23)

xi(k,j)∈{0,1},∀k=1,2,…,fi,∀j=1,2,…,mi

(24)

(25)

上述帧封装模型以一个超周期内总线利用率最高为优化目标,式(18)为目标函数；式(19)表示信号的唯一性,即每个信号只能封装在一个帧中;式(20)表示封装在一个帧中的信号数据位长度之和不能超过帧有效负载段长度;式(21)为帧有效负载段长度上下限；式(22)表示信号封装后得到的静态段长度要小于通信周期长度。其中的参数可由式(1)～(5)、式(7)、式(8)、式(10)、式(12)、式(14)～(17)求得。

3.4帧封装启发式算法

随着信号和节点数量的不断增多,采用ILP模型来解决帧封装问题的计算复杂度越来越高。为了缩短执行时间，降低算法复杂度，本文提出了基于总线利用率的帧封装启发式算法——首次适应降序算法(first fit decreasing framing packing based on bus utilization rate,FFD-FPBUR)。图3所示为帧封装算法伪代码,具体步骤如下:

(1)获取信号和节点信息,并且将信号按所属节点分类;

(2)对于每个节点i,将信号按数据位长度降序排序；

(4)对于每个节点i,按照FFD算法进行封装,获得帧集合;

(7)返回最终帧集合及其对应的最优帧负载段长度Lpl。

1获取节点及节点所对应的信号信息;2将每个节点中的信号按数据位长度大小降序排列;3计算LLpl和LHpl,初始化LCURpl=LLpl,TBUR=0;4forLCURpl=LLpltoLHpl5for每个ECU节点6按照FFD算法将每个信号封装到帧中,每帧负载段长度不超过LCURpl7endfor8对封装结果进行可调度分析;9if帧集合可调度10计算TCURBUR;11ifTBUR

图3FFD-FPBUR算法

由图3可知,FFD-FPBUR算法主要包括两个部分:一部分是对获取的信号进行排序,按照冒泡排序法,该部分的算法时间复杂度为O(n2);另一部分为信号封装,按照FFD算法封装的时间复杂度为O(nlgn),加上外层嵌套的两个for循环可以得到该部分总的时间复杂度为O(n3lgn)。所以该算法总的时间复杂度为O(n3lgn)。

4　实验验证

为进行对比分析,分别采用文献[6]和文献[8]方法对同样的信号集合进行帧封装。其中，文献[6]结果与本文方法一致。文献[8]结果如图4b所示。

(a)本文算法封装结果

(b)文献[8]封装结果图4　信号封装结果

表3　信号封装结果对比

为了进一步验证当信号数量不断增大时,采用FFD-FPBUR启发式算法能够有效地缩短帧封装执行时间，本文采用美国汽车工程协会(SAE)的基准数据(表4)进行验证。同时,采用MATLAB2013对3.3节ILP模型进行求解。为了增大信号集合,以表4数据为初始数据，采取随机抽取SAE基准数据的方法，将信号添加到初始数据集合中。

表4　SAE基准数据

图5　帧有效负载段上下限

为了进行对比，采用文献[6]和文献[8]方法得到的帧有效负载段取值范围为2字≤Lpl≤127字。这说明采用本文方法能够精确地计算出帧有效负载段取值范围,减少算法的迭代次数,从而缩短算法的执行时间，如图6所示。

图6　三种方法执行时间对比

图7为求解ILP模型所用时间TILP与采用FFD-FPBUR 算法所用时间TFFD-FPBUR比值图。从图7中曲线走势可以看出,当信号规模过大时,已经无法通过求解ILP模型得到最优结果,此时,必须采用近似启发式算法求解。

图7　最优求解与近似求解执行时间比较

图8分别为采用求解ILP模型、FFD-FPBUR算法与文献[6]和文献[8]方法对信号进行封装后的总线利用率。从图8中可以看出，采用FFD-FPBUR算法与求解ILP模型所得结果较为相近,这两种方法都优于文献[6]和文献[8]的方法。

5　结语

本文对FlexRay静态段的帧封装方法进行了研究。首先引入总线利用率概念,分析影响总线利用率的主要因素;其次,提出帧封装的前提条件，给出帧有效负载段上下限精确计算方法，在此基础上，以超周期内总线利用率最高为优化目标，建立解决帧封装问题的整数线性规划模型，并给出求解该模型的FFD-FPBUR算法；最后，通过SAE实验证明了本文方法的有效性，即不仅能够提高总线利用率，而且可有效缩短算法执行时间。

[1]张利,张本宏,王跃飞,等.基于总线占用率的FlexRay消息时隙分配方法研究[J].中国机械工程,2012,23(6):699-703.

Zhang Li,Zhang Benhong,Wang Yuefei,et al.Research on FlexRay Messages Slot Distribution Methods Based on Bus Occupancy Rate[J].China Mechanical Engineering,2012,23(6):699-703.

[2]Navet N,Song Yeqiong ,Simonot-lion F,et al.Trends in Automotive Communication Systems[J].Proceedings of the IEEE,2005,93(6):1204-1223.

[3]王跃飞,殷健力,张利,等.基于时间约束的汽车FlexRay网络动态段参数设计[J].中国机械工程,2014,25(15):2070-2075.

Wang Yuefei,Yin Jianli,Zhang Li,et al.Parameters Design of FlexRay Dynamic Segment under Time Constraints[J].China Mechanical Engineering,2014,25(15):2070-2075.

[4]王跃飞,王子涵,张利,等.基于改进调度算法的新一代汽车总线及其网关[J].电子测量与仪器学报,2011,25(10):894-900.

Wang Yuefei,Wang Zihan,Zhang Li.A New Generation Automotive Bus and Relative Gateway Based on Improved Scheduling Algorithm[J].Journal of Electronic Measurement and Instrument,2011,25(10):894-900.

[5]Kang M,Park K,Kim B.A Static Message Scheduling Algorithm for Reducing FlexRay Network Utilization[C]//IEEE International Symposium on Industrial Electronics.Seoul,2009:1287-1291.

[6]Kang M,Park K,Myong-Kee J.Frame Packing for Minimizing the Bandwidth Consumption of the FlexRay Static Segment[J].IEEE Transactions on Industrial Electronics,2013,60(9):4001-4008.

[7]张建军,于萍,张本宏,等.基于带宽利用率的FlexRay静态段研究[J].计算机应用研究,2012,29(12):4974-4976.

Zhang Jianjun,Yu Ping,Zhang Benhong,et al. Research on FlexRay Static Segment Based on Bandwidth Utilization[J].Application Research of Computers,2012,29(12):4974-4976.

[8]Schmidt K,Schmidt E G.Message Scheduling for the FlexRay Protocol:the Static Segment[J].IEEE Transactions on Vehicular Technology,2009,58(5):2170-2179.

[9]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.

[10]Jang K,Park I,Han J,et al.Design Framework for FlexRay Network Parameter Optimization[J]. International Journal of Automotive Technology,2011,12(4);589-597.

[11]王跃飞,张纯鹏,张利,等.基于最小时间碎片的汽车FlexRay网络设计[J].电子测量与仪器学报,2014,28(3):299-305.

Wang Yuefei,Zhang Chunpeng,Zhang Li,et al.Design of Automative FlexRay Network Based on Minimum Time Debris[J].Journal of Electronic Measurement and Instrument,2014,28(3):299-305.

[12]谢勇,李仁发,阮华斌,等.最优的FlexRay静态段配置算法[J].通信学报,2012,11(33):33-40.

Xie Yong,Li Renfa,Ruan Huabin,et al.Optimal Configuration Algorithm for Static Segment of FlexRay[J].Journal on Communications,2012,11(33):33-40.

[13]FlexRay Consortium,FlexRay Protocol Specification Version 3.0.1.[EB/OL].[2015-04-30].http://www.flexray.com.

(编辑王艳丽)

Research on Frame Packing Mechanism of Static Segment in Automobile FlexRay Network

Wang Yuefei1,2Zhang Heng1,2Zhang Yasheng1Liu Hongjun1

1.Hefei University of Technology,Hefei,230009 2.Engineering Research Center of Safety Critical Industrial Measurement and Control Technology of Ministry of Education,Hefei,230009

On the basis of analyzing FlexRay frame format and coding,the calculation formula of the length of static slot and bus utilization rate were obtained,and main factors that influenced bus utilization rate were given.Some prerequisites of frame packing and exact calculation method of lower and upper bounds of the size of the payload segment were proposed.Finally, with the target of realizing highest bus utilization rate in super cycle,the integer linear programming model was established to solve the problem of frame packing and heuristic algorithm of solving the model was given.The American socity of automotive engineers(SAE) experimental results demonstrate the effectiveness of the proposed method,which raises the bus utilization rate,and reduces the execution time of algorithm.

FlexRay bus;static slot;bus utilization rate;frame packing

2015-04-30

国家自然科学基金资助项目(61202096);教育部留学回国人员科研启动基金资助项目([2013]693);中央高校基本科研业务费专项资金资助项目(2013HGCH0014);安徽省省级高等学校自然科学研究资助项目(KJ2012A226);江淮汽车技术中心资助项目(W2014JSKF0086)

TN915.04DOI：10.3969/j.issn.1004-132X.2015.22.007

王跃飞，男，1977年生。合肥工业大学机械与汽车工程学院、教育部安全关键工业测控技术工程研究中心副教授。主要研究方向为汽车网络、实时系统、网络控制等。发表论文20余篇。张恒,男,1987年生。合肥工业大学机械与汽车工程学院、教育部安全关键工业测控技术工程研究中心硕士研究生。张亚生，男，1990年生。合肥工业大学机械与汽车工程学院硕士研究生。刘红军,男,1990年生。合肥工业大学机械与汽车工程学院硕士研究生。