基于FlexRay静态段快速最优调度算法

龚志鹏陈特放邹复民陈意军陈军根

①（中南大学信息科学与工程学院 长沙 410083）

②（湖南工程学院电气与信息工程学院 湘潭 411104）

③（福建工程学院福建省汽车电子与电驱动技术重点实验室 福州 350108）

基于FlexRay静态段快速最优调度算法

龚志鹏*①②陈特放①邹复民③陈意军②陈军根②

①（中南大学信息科学与工程学院 长沙 410083）

②（湖南工程学院电气与信息工程学院 湘潭 411104）

③（福建工程学院福建省汽车电子与电驱动技术重点实验室 福州 350108）

FlexRay正成为新一代车载通信网络。为解决FlexRay静态段调度（FSSS）的帧标志（FID）分配难题，该文提出一种基于周期特征的自动模型系数矩阵生成（AMCMG）算法，在大规模FSSS时，可快速得到最优调度模型的各类消息调度属性并确定系统所需的最少FID数；为进一步确定消息相位，并最终得到完整的周期调度表，根据不同周期消息之间调度的兼容性，提出了一种可实现最优规划的基于相位保留规则FID分配（PRFIDA）算法；最后，仿真实验结果表明AMCMG算法能快速正确地建立调度模型，同时PRFIDA算法可以实现消息在已知调度属性时的FID最优分配。

车载通信网络；F lexRay；静态段；帧标志分配；相位保留

1 引言

随着汽车技术发展，整车电子电气架构越来越复杂庞大，为支持日益增多的车载电子控制单元（Electronic Control Unit， ECU）之间实时信息交换的需求，迫切需要一个高速、高可靠、高确定性的网络连接［1，2］。新一代车载通信网络FlexRay总线基于TTP协议和Byteflight协议，由戴姆勒-克莱斯勒公司推出后得到了广泛的关注［3，4］。为保证实时性，基于事件触发的网络控制系统需要复杂的时基校正算法和拥塞控制规则［5，6］，而FlexRay总线兼具时间触发和事件触发的特点，通过其全局同步时钟可预知传感器的数据采集和执行部件的动作时刻，使系统在建模时可以忽略数据的传输过程，大幅提升了系统性能，其各项指标全面优于原有的CAN总线［7］。但是，FlexRay总线的进展目前依旧较慢，只有部分厂商在少量车型的个别ECU节点采用FlexRay，如宝马X 5 的悬挂系统等，对基于众多ECU的有大量消息交换的整车广泛FlexRay连接尚未见报道。FlexRay协议的复杂性是影响其应用的一个主要因素，FlexRay静态段的消息调度类似于多核计算机系统的并行调度问题，但却有更复杂的约束条件，使得调度更难实现［8］，是目前国内外研究热点和难点之一。其中文献［9， 10］对静态段在线和离线调度的时序研究，得出了最坏响应时间计算方法， 文献［11］对静态段传输可靠性进行了分析，估计了消息的最小重传次数，文献［12］讨论了静态段数据封装对带宽利用率的影响和最优静态时隙长度，文献［13］则提出了静态段调度的混合遗传算法，但当消息多时由于基因链增长导致调度效率不高，且只能得到近似解，文献［14］提出一种2维装箱算法，但规划规模随消息增多而增大，最终也只能求助于启发式算法，而文献［15］基于数论的方法就静态段调度提出了一种消息分类调度模型，这种模型的输入规模与消息数量无关，可以较好地确定消息调度的最优帧标识（Frame IDentification， FID）数，但面临系数输入工作量大、模型生成困难、应用不够灵活等问题，而且优化结果并不能明确每一消息的具体分配。为此，本文针对该问题拟设计一种应对消息数量多、周期分布广的大规模FlexRay静态段最优调度实现算法，并通过采用基于周期特性的大型优化问题系数树生成方法，使调度模型能够自动生成，同时将提出一种基于相位保留规则的最优FID分配方法以完整实现FlexRay静态段的调度，有望为基于F lexRay的大规模嵌入式汽车应用提供一种实际可行的最优解决方案。

2 静态段调度模型及问题描述

FlexRay的数据通信是由不断重复的长度为TC（Time of Cycle）的基本通信周期（FlexRay Cycle，FC）构成，一个FC可以分为静态段、动态段、符号窗口和空闲时间［16］。其中，静态段主要用于硬实时性、高度确定性且安全关键的周期性数据传输，如闭环控制系统中的传感器采集数据，控制器输出数据等［17］。FlexRay静态段采用TDMA访问方式，其消息传输如图1所示，一个静态段由多个等长的时隙（SLOT）构成，对于每个周期消息，其周期必须是TC的整数倍，且要求每个节点都保有一张调度表，消息只有在属于自己的SLOT到来时才能发送，每个SLOT只能传输一个数据帧并对应一个帧标记FID。FlexRay支持SLOT复用，即一个SLOT可以用于不同的消息，但必须保证不会冲突。为表述方便，下文描述周期时都以TC为单位。

图1 静态段消息传输

所有消息都至少完成一次完整调度所需的FC数称为调度超级周期（Hyper Period， HP）。以图1为例，共有9个消息M 1～M 9， HP=4；其中，消息M 1的周期为1，即每个FC都必须传输，所以单独占用了FID 1； M 2和M 3的周期为2，共用一个帧标识FID 2；消息M 4～M 7的周期都为4，所以共用FID 3。在FlexRay通信中，一个FC的长度即TC是有限的，考虑到每个消息只有一个FID，所以对于一个消息，在给定FID的情况下，确定其在一个HP中第1次出现在哪个FC，这个消息的调度也就确定了，该FC称为相位。故静态段最优调度的目标是为所有消息确定相位，且最后使用的或分配的FID数目最少。

2.1 消息分类模型

K laus Schm idt等人将消息以周期进行分类后，在数论的基础上提出了一个最优调度模型如下［15］：

2.2 问题描述

虽然文献［15］的消息分类模型输入规模不会随消息数量增大，规划效率较高，但应用中依然存在较大困难，主要问题包括：

（1）消息分类模型的建立十分复杂，模型系数矩阵获取困难，在当消息周期类型较多情况下，系数矩阵较为庞大，每一个系数都需要额外的计算，而且对于不同应用，系数矩阵都不相同，因此模型缺乏灵活性，实用性较差，没有充分利用FlexRay协议的特性。

（2）消息分类模型对静态段调度并不是一个完整方案，只是估计出在最优调度情况下所需的最小FID数目以及消息的调度属性，并未说明如何才能得到最优FID的结果，即并未给出具体消息调度，不能直接导出周期调度表。

所以，消息分类模型可“预言”消息的最优值，但其最优解只是消息的分类方法，不能直接提供所需的具体分配方案，且消息分类模型建立十分复杂。为此，基于该模型与消息数量无关的优良特性，本文将研究并提出一种模型自动生成方案，然后根据所得的消息分类提出一种基于相位保留法的最优分配方案，实现完整的消息调度。

3 自动模型系数矩阵生成算法

式（2）中，第1个约束条件为向上取整线性化规范操作，第2个约束条件为各周期消息总数约束。其中，kp（PRi）表示使用调度属性PRi的消息所占FID数，称为结果变量，k（PRi）为松弛变量。假设整线性规的一般形式为

其中，A为约束方程系数矩阵，B为约束边界（对于等式约束取上下界相等），C为目标函数矩阵，X为输入向量，O为适维零向量。为生成整线性规划模型，需求出对应的A， B， C 3个系数。自动模型系数矩阵生成算法的目标是根据系统周期特性，自动产生上述系数矩阵。约束方程分为取整约束和消息总数约束两部分，在求取系数矩阵式时需遍历所有质因子构成的组合。系数矩阵生成过程以超级周期HP=30为例，其周期分布为PS=｛1，2，3，5，6，10，15，30｝，按式（2）可得取整约束方程生成树如图2所示。

每个节点在所有子节点的系数矩阵生成完毕后，再加入本节点的参数方程，最后在根节点合成整个系数矩阵，具体过程为：

（2）对于其他层：

图 2 取整约束方程生成树

（b）广度方向矩阵合成如式（5），其中A（n-2）和A（n-1）为需要合并的系数矩阵，O1和O2为适维零矩阵，A（n）为合并后的系数矩阵。

（3）约束边界B矩阵如式（6），其中O3为适维零向量，B1为各周期消息相应的数量构成的列向量。

（4）C为目标函数矩阵，对应素数周期的元素置为1，其余置为零。

根据上述分析，自动模型系数矩阵生成算法AMCMG可设计如表1所示。

表1 AM CMG算法

表1中，取整约束系数矩阵生成函数getcoeff（ ）可设计如表2所示。

3 基于相位保留的FID分配

针对2.2节中的问题（2），即如何根据消息分类模型求解后得到的各种调度属性的消息数量，确定每个消息的具体相位，同时保证调度依然是最优的，为此首先给出如下定义。

定义 1 同类消息：周期相等且调度属性相同的所有消息称为同类消息。

表2 取整约束系数矩阵生成函数getcoeff

（1）如果是同类消息，尽可能保持父级调度相位不变，即当父级相位没用完，保持父级相位不变，先依次用完当前相位；否则如果当前父级相位用完，则开启下一个新的父级相位。

（2）如果是兄弟类消息，当下一位置应该为新相位，则从新相位开始，否则跳出当前父级相位，从下一个父级相位开始。

（3）如果是子类消息，则将本来的下一个同类消息相位扩展一位，新扩展位为0，即当前相位加上新消息周期作为下一个消息相位。

（4）如果为父类消息，当下一个位置为新相位，则新相位为下一个消息相位，否则如果不是新相位，则在当前父级级相位增量作为下一个消息相位，同时收缩相位。

根据以上分析，基于相位保留的FID分配算法PRFIDA可设计如表3所示。

表3 PRFIDA算法

定理1 PRFIDA算法能够实现确定调度属性下的最优FID分配。

证明 PRFIDA算法是从上而下分配相位，即先分配上级的父类消息，再分配下级子类和兄弟类消息。对同类消息，相位保留法与顺序分配方法一样，能分配使用一个FID的所有相位而不会产生浪费；对于下级消息，PRFIDA算法能够直接在当前相位中扩展，低一级相位不会产生相位浪费；对于兄弟类消息，PRFIDA算法能最大限度地利用上级相位，产生最小的相位浪费，为并行消息尽可能多的保留上级相位。综上所述，PRFIDA算法能产生最小的相位浪费，从而实现最优调度。 证毕

例 假设超级周期为HP=30，分配消息n（2，3，5）=30，假设初始相位从0开始分配，则基于PRFIDA算法的各消息的相位依次为：0 6 12 18 24 2 8 14 20 26 4 10 16 22 28 1 7 13 19 25 3 9 15 21 27 5 11 17 23 29。

4 仿真实验及其分析

为实现静态段消息的完整调度，本文首先采用AMCMG进行静态段的自动建模，求解后对各类消息采用PRFIDA算法进行最优FID分配。为验证AMCMG+PRFIDA方案的有效性及其性能，仿真实验的硬件配置为Intel I3 2.3G， RAM 2G，软件配置为MATLAB 2011a环境下采用TOM LAB/ CPLEX优化工具进行整线性规划。

首先，为验证本文方案在静态段调度建模时的准确性和可用性，选用了一组典型的可预知结果的实例进行仿真实验。根据文献［18］，不妨采用一些重要标准规范常用的周期作为HP，例如2n以及支持多消息周期的2310和30030等，并令每种周期的消息数刚好等于消息周期，即每一种周期的消息刚好占用一个FID。根据FlexRay规范，只要HP给定，则所支持的消息周期的集合PS也就确定了，所需的最少FID数即为消息周期数|PS|，因此只需要检验AMCMG算法的优化结果与|PS|是否相等，即可确认AMCMG建立的模型的正确性。随后，采用PRFIDA算法进行消息的FID分配，如果最终所需的FID数与|PS|相比没有增加，即可确定实现了消息的最优分配。

表4给出了在上述条件下，9种典型HP配置应用AMCMG算法生成模型并用PRFIDA算法进行消息分配的实验结果，其中|PS|可作为事先确定的最优FID数，FIDOTP为应用AMCMG算法生成模型并采用CPLEX优化工具所得的预期最优结果，FIDPR为采用PRFIDA算法进行FID分配实际所需的FID数。以HP=64为例，不考虑消息周期为1的情形，则系统所支持的消息周期集为PS=｛2，4，8，16，32，64｝，故有消息周期数量|PS|=6，各消息周期分别有2， 4， 8， 16， 32和64个消息需要调度，每一种消息周期的消息依次占用一个FID，因此可事先确定的最优FID数|PS|=6。结果显示，根据AMCMG算法建立的模型并求解后，最优结果FIDOTP=6，与事先确定的最优FID数|PS|保持一致，证实了AMCMG算法的正确性；在此基础上，进行PRFIDA的消息FID分配，可得实际所需的FID数FIDPR=6，验证了PRFIDA算法能实现最优FID分配。

建立调度周期表是实现最优FID分配至关重要的一个环节，为可靠验证PRFIDA算法的准确性，本文模拟了一种更为复杂的调度情景。不妨令消息周期为pi的消息数量为周期的rate倍，并向上取整，即N（pi）=ceil（rate×pi），表5给出了7种典型HP配置下rate=10.0～10.4时的实验结果，以HP= 64∧rate=10.4为例，此时系统所支持的消息周期集为PS=｛2，4，8，16， 32， 64｝，各周期的消息数分别为21，42， 84， 165， 333和666，采用AMCMG算法建立模型并得到最优规划结果FIDOTP=63，即预期所需的最少FID数为63，当采用PRFIDA算法进行具体FID分配时，其实际分配结果FIDPR也正好为63，即所需的FID数没有额外增加。表5中实验结果显示，对所有情况均有FIDPR=FIDOTP，即PRFIDA算法能实现确定调度属性下的最优FID分配。

为进一步验证本文所提方案的效率，拟对多种大规模调度的应用场景进行模拟实验。不妨设周期为pi的消息数量为N（pi）=np×pi，取 HP=8， 64， 60，2310共4种典型配置种情况下，使np从1到800依次增大，测试算法所需时间。为比较算法性能，本文同时采用了Martin L提出的2维装箱算法在同样的条件下进行消息调度，图3显示了各算法所需的时间。图3（a）显示，M artin L提出的2维装箱算法只能在消息数量少、周期分布简单的情况下能够获得最优解，如HP =8∧np≤15和HP=64∧np≤2时能够求解，在消息数量增加，周期关系稍微复杂时，2维装箱算法很快就无法求解。图3（b）显示了本文AMCMG+PRFIDA方案所需时间，在所有假设的实验条件中，该方案不仅皆能求得最优解，实现消息最优FID分配，而且所需时间明显更短。同时，对于给定的HP，当np增大时，即消息数量增大时，算法时间基本保持不变，显示了模型输入规模与消息数量无关的特性。在实验中，HP=2310∧np=800、消息总数量达24800时，实现最优调度所需时间也只有5.1 s。

负载均衡是FID分配算法的另外一个重要的性能指标，因为如果负载分布均衡，则剩余SLOT可以更方便地为未来系统扩展所利用。根据FlexRay协议，一个FC实际需要传输的消息数称为这个FC的负载。消息数量依旧设N（pi）=ceil（rate×pi），图4（a）～4（e）展示了在HP=60且rate=10.0～10.4时各FC实际分配的消息数均衡情况，此时系统支持的消息周期集为PS=｛2，3，4，5，6，10，12，15， 20，30， 60 ｝，支持的消息周期密度较大，具有较好的研究价值。当rate=10.0时，每个周期的消息刚好能够填满整10个FID，这时系统所需的FID数为10×11=110个，每个FC的传输的消息数量完全相等，这时负载分配是最均衡的；当rate不为整数时，即使在最优规划和PRFIDA算法的FID分配时，有的FID不再能被完全利用，这时FC的负载稍有差异，如图4（b）所示的rate=10.1时的负载均衡情况，各FC负载差别最大，各负载分布统计为：1个FC负载为 110， 10个FC负载为111， 28个FC负载为112， 21个FC负载为113，负载分布也基本处于平衡状态。

表5 最优规划预期FID与采用PRFIDA算法实际分配的FID结果

图3 AMCMG+PRFIDA方案和2维装箱算法所需时间比较

图4 HP=60时各通信周期的负载分布

5 结束语

本文分析了FlexRay静态段在整车ECU互联应用中所面临的调度难题，研究了基于FlexRay传输的消息特性，讨论了文献［15］中基于消息分类最优调度模型在实际应用中的不足，并在此基础上提出了AMCMG+PRFIDA方案。其中，AMCMG算法利用了FlexRay静态段消息周期分布特性，使得复杂的消息分类最优调度模型能够自动生成；为进一步确定每一个消息的具体FID和相位分配，并保持先前的原有模型求解时预期的最优FID分配数不变，在给定调度属性下的，提出了PRFIDA算法进行FlexRay静态段消息FID分配。仿真实验结果表明，AMCMG算法能快速正确地建立调度模型，PRFIDA算法能使各消息在调度时尽可能共用FID，最大限度地减小FID的浪费，最终实现静态段消息的整体最优调度。在实践中，根据本文提出的方案，只需确定调度超级周期和各类消息的数量即可得到最优调度结果，并将每一个消息的调度确定到具体位置，从而能够得到一个完整的静态段调度表。

［1］ Flem ing B. New automotive electronics technologies［J］. IEEE Transactions on Vehicular Technology， 2012， 7（4）: 4-12.

［2］ Tuohy S and Glavin M. Next generation w ired intra-vehicle networks， a review［C］. Proceedings of IEEE on Intelligent Vehicles Sym posium， Gold Coast， Australia， 2013: 777-782.

［3］ TTTech. Time-triggered p rotocol ttp/c， high-level specification document， protocol version 1.1［OL］. http:// www.tttech.com， 2014.

［4］ Berwanger J and Peller M. Byteflight -a new p rotocol for safety critical applications ［C］. Proceedings of the 2000 FISITA W orld Automotive Congress， Seou l， Korea， 2000: 1-7.

［5］ 王聪， 张凤荔， 王瑞锦， 等.一种网络时延矩阵分布式自适应重建算法［J］. 电子与信息学报， 2014， 36（4）: 840-846.

［6］ 罗成， 谢维信. 传感器网络拥塞避免与控制的模糊AQM算法［J］. 电子学报， 2014， 42（4）: 679-684.

［7］ Longo S and Herrmann G. Robust scheduling of sam pleddata networked control system s［J］. IEEE Transactions on Control System s Technology， 2012， 20（6）: 1613-1621.

［8］ 徐超， 何炎祥， 陈勇， 等. 一种多核系统可靠性加强的任务调度方法［J］. 电子学报， 2013， 41（5）: 1019-1024.

［9］ Oued raogo L and Kumar R. Exact response time of flexray communication protocol［C］. Proceedings of W ireless Communications and Mobile Com puting Conference，Istanbu l， Turkey， 2011: 789-794.

［10］ Lange R and Vasques F. Guaranteeing real-time message deadlines in the flexray static segment using a on-line schedu ling app roach［C］. Proceedings of the 9th IEEE International Workshop on Factory Communication Systems，Lemgo， Germany， 2012: 301-310.

［11］ Tanasa B and Bordoloi U D. Reliability-aware frame packing for the static segment of flexray［C］. Proceedings of Em soft，Taipei， China， 2011: 175-184.

［12］ M inkoo K and Kiejin P. Frame packing for m inimizing the bandw idth consum ption of the flexray static segment［J］. IEEE Transactions on Industrial Electronics， 2013， 60（9）: 4001-4008.

［13］ Shan D. A hybrid GA-based scheduling method for static segment in flexray system s［C］. Proceedings of on Control and Decision， Xuzhou， China， 2010: 1548-1552.

［14］ Martin L and M ichael G. Advances in Real-time System s［M］. Berlin: Sp ringer， 2012: 323-339.

［15］ Schm id t K and Schm idt E G. M essage schedu ling for the flexray protocol: the static segment［J］. IEEE Transactions on Vehicular Technology， 2009， 58（5）: 2170-2179.

［16］ FlexRay Consortium. FlexRay communication system s protocol specification， version 3.0.1［OL］. http: //www. FlexRay. com， 2010.

［17］ G renier M， Havet L， and Navet N. Con figuring the communication on flexray: the case of the static segment［C］. Proceedings of the 4th European Congress on Embedded Real Time Software， Toulouse， France， 2008: 1-18.

［18］ AUTOSAR. Specification of flexray network management.［OL］. http://www.autosar.org ， 2013

龚志鹏： 男，1974年生，博士生，讲师，研究方向为车载通信网络.

陈特放： 男，1957年生，博士，教授，博士生导师，研究方向为交通信息工程及控制.

邹复民： 男，1976年生，博士，教授，研究方向为交通信息工程及控制.

A Fast Op timal Schedu ling A lgorithm for FlexRay Static Segment

Gong Zhi-peng①②Chen Te-fang①Zou Fu-m in③Chen Yi-jun②Chen Jun-gen②①（School of Information Science and Engineering， Central South University， Changsha 410083， China）
②（College of Electrical and Information Engineering， Hunan Institute of Engineering， Xiangtan 411104， China）
③（Fujian Key Laboratory for Autom otive Electronics and Electric Drive， Fujian University of Techno logy，Fuzhou 350108， China）

FlexRay is becom ing the in-vehicle communication network of the next generation. To resolve the prob lem of Frame IDentification （FID） assignment in the FlexRay Static Segment Schedu ling （FSSS）， an Autom atic M odel Coefficient M atrix Generating （AMCMG） algorithm is p roposed to ob tain the coefficient matrix automatically based on the characteristics of period distribution. A large-scale p rogramm ing model of FSSS can be generated automatically， and the scheduling properties of all kinds of messages can be derived as well as the m inimum number of FID required for the system can be determ ined quickly. To assign the phase for each message and obtain the comp lete schedu ling tab le， a Phase Reserving based FID Assignment （PRFIDA） algorithm is designed according to the com patibility of messages scheduling in different periods， which is able to keep the op tim al property of the previous p rogramm ing. Finally， the simulation results dem onstrate that the AMCMG algorithm can build the scheduling model rapidly and correctly， and the PRFIDA algorithm can realize the FID assignment optimally based on the known scheduling p roperties of messages.

In-vehicle communication network； FlexRay； Static segment； Frame IDentification （FID） assignment；Phase reserving

TN 915

： A

：1009-5896（2015）05-1200-07

10.11999/JEIT140933

2014-07-15收到，2014-12-17改回

国家自然科学基金（60674003），福建省重大专项（2013HZ0002-1），福建省杰出青年基金（2012J06015），湖南省教育厅高校创新基金（12K 127）和湖南省科技计划项目（2012GK 3078）资助课题

*通信作者：龚志鹏 zpgong2000@126.com