FlexRay静态部分基于优先级调度问题的研究

梁佳雯，张劭昀，郭海双（.贵州师范大学数学与计算机科学学院，贵阳 55000；.贵州师范大学物理与电子科学学院，贵阳　55000）

FlexRay静态部分基于优先级调度问题的研究

梁佳雯1，张劭昀2，郭海双1
（1.贵州师范大学数学与计算机科学学院，贵阳 550001；2.贵州师范大学物理与电子科学学院，贵阳550001）

1　FlexRay介绍

FlexRay车载网络标准已经成为了同类产品的基准，并将在未来很多年内，引领整个汽车电子产品控制结构的发展方向。其被认为是继CAN和LIN之后，未来汽车网络的主流标准。简单来说，FlexRay是汽车网络中一种混合车载通信协议，其静态部分使用时间触发传输数据，动态部分使用事件触发传输数据。事件触发具有较高的灵活性和较高的利用率，与时间触发相比，事件触发的协议传输的消息的响应时间具有不可预测性。此外FlexRay总线还具有高速的传输速率，能够适应不同网络拓扑结构，以及集合多种网络拓扑结构安排分布式系统等优点。

2　系统模型和定义变量

2.1Flex Ray 协议模型

FlexRay周期是媒体访问FlexRay调度的基本单位。FlexRay周期提供了两种不同的总线访问策略，一种是静态部分 （SS）应对时间触发的时分多址访问（TDMA）调度，另一种是用在动态部分用以应对事件触发的柔性时分多址（FTDMA）访问。动态部分（DS）一般不会涉及这个问题。

目前，关于FlexRay优化的研究很少，文献[1]提出一种通过FlexRay总线静态段长度分析FlexRay总线负载率的方法，文献[2]提出一种将静态段长数据帧分配到动态段的调度方法来减少总线的负载率。但是这种方法使得消息发送具有不确定性。

在静态部分，一个周期内时隙的长度是固定的，且一个给定的位置总是保留给相同的节点。静态部分的仲裁是通过为每个网络节点的每个消息分配独特的帧ID来实现的。这种做法阻止了总线的冲突。静态时隙的大小是网络全局配置的，即可以设置为能够通过总线最长消息的大小。也就是说如果ECU在这个时隙没有数据传输，静态时隙的大小也不能改变，在这种情况下，有效荷载没有数据[3]。为了增加为使用时隙的数量，通过优化通信周期的大小和时隙的大小，反过来增加通信系统带宽的利用率。文本是为了利用静态部分优先级关系调度消息。此外，本文假设FlexRay允许时隙复用，这意味着相同的帧ID能够被不同节点的消息利用。在文献[4]中，通过给每个消息定义一个基础周期（初始周期）和重复率（传输周期）增加时隙复用的数量，从而增加FlexRay总线的利用率的。举例来说，只有传输消息时使用不同的通信周期，相同的帧ID才能被分配给多个节点。时隙复用是用重复率和基础周期进行描述的：重复率是用来描述每个帧标识符的消息传输的频率，基础周期表示在FlexRay周期内消息发生的初始通信周期。模型流程图如图1所示。

图1　FlexRay协议模型流程图

2.2定义变量

在此篇文章中，需要用到的FlexRay静态部分参数定义如下：H，nslot，lslot，其中H是主周期 （MC）内FlexRay周期（FC）的数量，nslot是通信周期（CC）内静态部分的时隙数量，lslot代表静态部分时隙的长度。模型由N个节点组成，N={1，…，N}代表一系列节点。每个消息mi的传输时间为wi，传输节点为ni，重复率为ri，，基础周期为bi且bi＜ri。本文假设消息的长度和时隙的长度相等。ui表示分配给每个消息mi的帧ID。为了解决调度问题和找到一个可行的时隙装箱，本文需要决定每个消息的帧标识符ui和基础周期bi。

现有的相关研究中多采用有向无环图对汽车电子系统中的应用进行抽象描述，如图2（a）所示，其中顶点表示任务，顶点之间的连线表示通信信号。

图2　

3　装箱问题

在文献[5]中，作者为了实现所使用节点的数量最少，将问题转化成了一个二维的装箱问题，但是其没有考虑到每个消息的独立性。因此本文将问题转化成为一个二维的条状装箱问题的同时，需要充分考虑每个消息间的独立性。装箱问题中每条的高度为Hs，且Hs= H.nslot。每条被分成nslot个部分。在所有的FlexRay周期中，被划分出的每个小部分，用si表示，其中i=1，…，nslot，代表第i个时隙，即第i个帧ID。本文将每个消息mi传送到一个矩形gi中。gi的宽度就是在总线上单独完整传送每个消息的时长。每个矩形gi的高度，用hi表示，gi的高度就是主周期内传输消息mi所要求的静态时隙数，其中每个矩形的高度：

条状装箱问题的目的就是为了给每个独立矩形找到其所使用条状的最小高度。本文使用点yi的坐标表示每个矩形gi中条状的位置。用ki表示分配给每个矩形gi的部分，ki用公式（2）表示

点（ki，yi）能够根据公式（3）转化成FlexRay静态部分的对应位置。

其中，ui是消息mi的帧标识符。即当一个矩形分配给第i个部分时，对应的消息就分配给了第i个时隙。图3展示将图2中的示例消息利用装箱问题放置到对应的矩形中。表1和表2说明了将举例消息中的坐标（ki，yi）换算成对应静态部分的坐标（ui，ki）。

表1　

图3　装箱问题应用举例

本文发现如果只有单独的条状装箱问题无法完全解决矩形可靠性等问题。为了解决这些问题，本文引入了新的约束，称为三条约束。

4　三条约束

一个FlexRay通信周期内的静态部分被分成了若干个相等的时隙。每个ECU能被分配给一个或多个时隙，然而每个时隙只能匹配一个ECU。如果一个时隙被分配给了一个特定的ECU，然后再每个通信周期内它都会被分配给同一个ECU。这就是文献[6]在FlexRay静态部分优化调度问题研究中所考虑到的约束。为了解决消息间优先级和矩形封装可行性问题，这个部分本文引入一系列新的约束，分别为高度约束，冲突约束和优先级约束。

4.1高度约束

定义高度的约束是为了限制矩形的宽度只能是高度的整数倍。因此，对于每个矩形gi的高度的约束用以下的公式定义：

这样防止一个矩形被分配给了两个相邻的部分。因为，如果一个矩形被分配给了两个相邻的部分，它将有可能被分给两个连续的帧ID。这个与FlexRay的规定每个通信周期内一个帧ID只能使用一次是冲突的。。

4.2冲突约束

定义冲突约束是为了防止消息传输中发生冲突，当两个来自不同节点的消息被分配给同一个帧ID时，消息间的冲突就会发生。举例来说，在图2（a）中，让本文交换g2和g3g5的位置，交换后y3=4，y5=6，y2=8，此时因为b4=b5=1，所以在周期1的第二个时隙中，消息传输时会有冲突发生。假设gi和gj都被封装在同一个部分中，例如ki=kj=k。消息mi和mj之间的冲突能通过定义公式（5）预防发生：

4.3优先级约束

5　结语

本文主要研究FlexRay协议中静态部分消息调度优先级关系的问题。因此为了得到最小的使用时隙数，即最小帧ID的时隙号本文将优先级的消息调度问题转化成为了一个装箱问题。其后为解决装箱问题中的可靠性等问题，引入了关于传输过程中消息间高度、优先级以及冲突的约束。对于如何通过建模仿真得到最小时隙数的最优解，将在进一步的研究和实验中进行。

[1]Minkoo Kang，Kiejin Park，Bongjun Kim.Determining the Size of a Static Segment and Analyzing the Utilization of In-Vehicle FlexRay Network[J].IEEE Computer Society，DOI 10.1109/ICCIT.2008.317:50-53.

[2]Minkoo Kang，Kiejin Park，Bongjun Kim，A Static Message Scheduling Algorithm for Reducing FlexRay Network Utilization[J].IEEE International Symposium on Industrial Electronics，2009:1287-1291.

[3]D.Paret，FlexRay and Its Applications:WILEY，2012.

[4]T.Schenkelaars，B.Vermeulen，K.Goossens.Optimal Scheduling of Switched FlexRay Networks[J]DATE Conf 2011,1-6.

[5]M.Lukasiewycz,M.Glab,J.Teich.FlexRay Schedule Optimization of the Static Segment[J].IEEE International Conference Hardware/Software Codesign and System Synthesis,2009

[6]H.L.Zheng Sun,Min Yao,Nan Li.Scheduling Optimization Techniques for FlexRay[J].IEEE/ACM International Conference on Cyber, Physical and Social Computing,2010.

张劭昀（1987-），陕西咸阳人，硕士研究生，研究方向为智能网络控制

郭海双（1989-），河北唐山人，硕士研究生，研究方向为智能网络控制

FlexRay;Static Section;Priority

Research on Priority Scheduling Problem Based on the Static Section of FlexRay

LIANG Jia-wen1，ZHANG Shao-yun2，GUO Hai-shuang1
（1.Guizhou Normal University，School of Mathematics and Computer Science，Guiyang 550001；2.Guizhou Normal University，School of Physics and Electronic Science，Guiyang550001）

1007-1423（2016）06-0007-04

10.3969/j.issn.1007-1423.2016.06.002

梁佳雯（1991-），女，湖北武汉人，硕士研究生，研究方向为智能网络控制

2016-01-05

2016-02-16

FlexRay通信周期中包含静态部分和动态部分，使得此种通信方式既支持时间触发又支持事件触发。为了提高FlexRay通信总线的使用率，研究静态部分基于优先级的调度问题，期望得到最大的自由时隙数，即最小的使用时隙数，为额外节点提供更多空间来增加系统的扩展性。因此将其转化成为一个二维的装箱问题，最后引入约束条件优化消息调度中优先级的关系。为后续建立模型解决静态部分基于优先级调度问题及得到最优解奠定理论基础。

FlexRay；静态部分；优先级

FlexRay communication cycle includes static section and dynamic section,which makes it possible to support both time trigger and event trigger.In order to improve the utilization of FlexRay bus,studies the priority scheduling problem based on the static section,hopping to get the maximum number of free slots,namely the minimum number of used slot,providing more space for additional nodes to increase the scalability of the system.Converts it into a packing problem,then introduces the constraints to optimize the priority relationship during the process.It lays the theoretical foundation for subsequent establish the model to solve the problem and get the optimal solution.