车载电子系统中场景感知的实时性分析的优化

谢 勇，陈旭辉，许华荣，王晓栋

（厦门理工学院计算机与信息工程学院，福建厦门361024）

车载电子系统中场景感知的实时性分析的优化

谢 勇，陈旭辉，许华荣，王晓栋

（厦门理工学院计算机与信息工程学院，福建厦门361024）

提出基于场景的车载电子系统实时性分析，并设计了一种基于日志信息的自动场景拆分算法，通过以场景局部的最坏情况替代系统全局的最坏情况作为实时性分析的基础来优化实时性分析的结果，以提高系统的可扩展性和降低系统成本.仿真实验证明了该方法的有效性.

车载电子系统；场景拆分；实时性；优化

为满足人们在安全、节能和环保等方面的越来越高的要求，汽车内电子组件的比例逐渐增高，部分高档轿车中ECU（electronic control unit）的数目已经接近100个，其通过CAN、FlexRay等总线互联形成复杂的分布式实时嵌入式系统［1］.主动安全、线控系统和高级辅助驾驶等分布式车载电子功能之间共享ECU、总线等系统资源，但是在不同的运行场景下它们并不会同时运行，如辅助停车和线控转向等，因此，VES（vehicular electronic system）的负载将随着运行场景发生动态变化.但是现有的面向VES等实时嵌入式系统的实时性分析方法一般都假设系统所有的功能同时运行 （满负载），即在系统全局最坏的情况下采用 “过度设计”和静态配置的原则，以保障硬实时时限 （deadline）的满足.故利用现有的实时性分析方法分析得到的结果非常悲观，其可能认为原本可调度的系统不可调度.

在分布式实时系统领域，基于场景的设计方法的相关研究较少.文献 ［2］关注车载电子系统不同场景转换过程中成员管理、转换点时间决策问题等，以支持系统运行时的动态配置.文献 ［3］利用事件模型，从任务触发方式、任务周期大小等方面对场景转换过程中使用的任务调度算法进行扩展，以优化任务的WCRT（worst-case response time）分析.文献 ［4］利用日志和事件流模型等抽取车载电子系统运行过程中不同的通信场景，以优化消息的WCRT分析.上述研究仅仅关注场景转换过程中任务或消息的WCRT分析，而没有从系统整体角度研究场景设计方法对实时性分析的影响.

为优化VES中实时性分析的准确度，本文从系统分析的输入值入手，利用场景的概念对VES负载的变化进行建模和抽象描述.将场景定义为特定场合下系统中运行的功能集合以及所对应的系统性能.在场景概念的基础之上，提出一种有效的自动场景拆分算法，通过组合各场景局部的最坏情况来替代全局最坏情况作为系统实时性分析的基础，来优化实时性分析的准确度.

1 系统模型和假设

利用有向无环图 （directed acyclic graph，DAG）来对车载电子功能APPi进行建模和描述，其中顶点代表任务 taski，边代表任务间的通信消息 mij.任务具备如下属性：周期 Ti、优先级 Pi、WCETCi、WCRTri，假设隶属于同一功能的任务周期相等.消息具备如下属性：周期、优先级最差传输时间消息的周期和优先级与其前驱任务相同.本文假设通信消息通过FlexRay的静态段进行传输，系统采用基于固定优先级的任务调度算法.本文采用图1所示的VES系统架构，其中ECU之间的通信采用的FlexRay网络是公认的下一代车载网络协议标准，它在安全性、时间确定性等方面比CAN具有更大优势［1］.

图1 VES的典型架构Fig.1 A typicaI system architecture for automotive eIectronic system

在DAG图中，从初始任务到目的任务所经历的一条执行路径表示从传感器采集数据，经过中间处理后将结果发送给执行器进行相应控制的过程，该执行路径所产生的端到端时延 （end-to-end，e2e）li决定了车载电子功能的实时性.因此，本文主要关注功能级的端到端时延.根据AUTOSAR标准［5］，本文假设任务周期与FlexRay总线通信周期之间是兼容的，且当ECU分配时隙到来时，各个任务需发送的消息都已经在等待队列中就绪.另外，本文假设在进行场景拆分之前，已经完成所有功能的分配，即各ECU中的任务集和需发送的消息集已确定.

2 基于场景的实时性分析方法

现有的实时性分析方法假设系统所有功能同时运行且在系统的整个生命周期中保持不变，以保障硬实时时限得到满足.但是实际上VES中的许多功能并不会同时运行，可以说它们之间是互斥存在的，因此现有的分析方法分析得到的结果非常悲观.鉴于此，本文提出一种基于场景的实时性分析方法，在已知系统模型、任务和消息分配以及总线配置等前提下，利用系统运行得到的日志信息来辅助系统互斥场景的识别和拆分 （汽车配件厂商推出多种支持系统运行时日志信息获取和分析的FlexRay、CAN总线接口，如 IXXAT公司的FlexRay CCM［6］），从场景局部的最坏情况可组合得到更加精确的系统整体的端到端时延结果，从而可优化实时性分析的准确度，该方法的具体分析流程如图2所示.

图2 基于场景的实时性分析方法流程Fig.2 FIow chart of scenario-based reaI-time anaIysis

图3 车载电子系统的运行场景Fig.3 VES scenario extraction

2.1 场景拆分算法

VES中的功能可分为两类：一类在VES的运行过程中始终存在，即它与场景独立，本文将该类功能表示为AppI；另一类功能与场景相关，即在特定的场景中该功能才会运行，本文将其表示为 AppD，系统的功能集App=AppI∪AppD.本文假设从系统运行的日志中提取出的运行场景如图3所示，在时间段［t0，t5］内，共有7个功能在运行，其中AppI=｛App7｝，AppD=｛App1，App2，App3，App4，App5，App6｝.

在描述场景拆分算法之前，相关概念的定义如下：

定义1功能生存期

将功能Appi在系统运行过程中持续存在的时间段 ［ti，start，ti，end］定义为该功能的生存期 life＿cyclei.当某个功能存在多个不同的生存期时，本文将其作为不同的功能进行处理.如图3中的App1在生存期［t4，t5］中当作App6.

定义2互斥功能对

生存期不存在重叠的两个功能称之为互斥功能对，简称互斥对：Mut＿Pairx=（Appi，Appj），其中ti，end≤tj，start或tj，end≤ ti，start， 如图3中的（App1，App3）.

定义3互斥集

由所有互斥对中功能元素所组成的集合称之为互斥集，Mut＿Set=｛AppiAppi∈Mul＿Pair｝.

定义4忙区间

特定场景中所有功能同时运行的区间称之为该场景的忙区间，如图3中Scenario1=｛App1，App2，App5，App7｝的忙区间为［t1，t2］.

定义5场景局部的最坏情况

由于不同场景中运行的任务集和消息集不同，因此性能分析得到的结果将不同.本文将端到端时延在各个场景忙区间中的最大值作为最终的端到端时延，并将该种情况定义为场景局部的最坏情况.

证明与系统全局的最坏情况相比，基于场景局部的最坏情况进行端到端时延分析将得到更加精确的实时性分析结果.

前提条件：系统总的功能集不变，任务分配和总线配置不变，系统模型不变.

从上述定义可知，与系统全局的最坏情况即假设系统所有功能同时运行不同，特定场景包含的功能集App⊂App，即在该场景中所包含的任务、消息是系统总的任务集、消息集的子集.在该情况下，对任务、消息造成抢占的高优先级任务或消息个数减少，而且由于任务分配，任务、消息的周期和优先级等属性不变，由后面的式 （1）和式 （2）可知，任务或消息被属于同一场景的高优先级任务或消息抢占的次数减小，故任务和消息的WCRT将减小.再由式 （5）可知，端到端时延也将减小.

根据上述的定义和分析，本文提出了一种互斥场景的拆分算法Sce＿Decomp，其具体描述如下：

Algorithm Sce＿Decomp（）

输入：功能集App，功能生存期Life＿Cycle

输出：场景集Scenario

1＜AppI，AppD≥Div（App）；//对功能集App进行分解，得到AppD和AppI

2＜Mut＿Pair，Mut＿Set≥Mut＿Pair＿Extra（AppD）；//从AppD中抽取出互斥对、互斥集

3 Mut＿Set=Ascend＿Order（Mut＿Set）；//互斥集中的元素按ti，start大小进行升序排列

4 For each Appiin Mut＿Set//仿照经典扫描线算法，生成初始场景Init＿Set

5 For any other Appjin Mut＿Set

6 If（［ti，start，ti，end］∩［tj，start，tj，end］！ = ∅）

7 Scei=Scei∪Appj；

8 End If

9 End For

10 Init＿Sce=Init＿Sce∪Scei；

11 End For

12 While（True）//对Init＿Sce进行进一步处理，生成最终的场景集Scenario

13 Init＿Sce=Dup＿Del（Init＿Sce）； //删除Init＿Sce中重合的场景元素

14 Init＿Sce=Subset＿Del（Init＿Sce）；//删除Init＿Sce中作为其他场景元素子集的场景元素

15 For each SceiinInit＿Sce//对存在互斥对元素的初始场景进行进一步拆分

16 If∃Appi，Appj∈Scek&&（Appi，Appj）∈Mut＿Pair

17 Init＿Sce=Init＿Sce∪（Scek-Appi）；

18 Init＿Sce=Init＿Sce∪（Scek-Appj）；

19 End If

20 Init＿Sce=Init＿Sce-Scek；

21 End For

22 If no more change to Init＿Sce

23 break；

24 End If

25 End While

26 Scenario=｛Scei|Scei∈Init＿Sce，Scei=Scei∪AppI｝//加入AppI中的功能，得到最终的场景集

如对于图3中给出的运行场景，利用该算法拆分得到的场景结果如图4所示.

图4 场景拆分结果Fig.4 Division of VES

2.2 系统整体的实时性分析

根据执行路径的定义可知，路径的端到端时延等于任务与消息的WCRT之和.基于本文的系统模型，任务WCRT的计算公式［7］如下：

其中：hp（ti）表示与任务ti处于同一ECU单元且优先级比它高的任务的集合；「（ri+ji）/Ti」表示任务ti从触发到执行结束期间，高优先级任务对其造成抢占的次数.

本文参照文献 ［8］中提出的面向TDMA总线的消息调度分析方法来对FlexRay静态段消息的WCRT进行分析，具体的计算公式为

其中：hp（mij）表示其前驱任务与消息mij的前驱任务处于同一ECU单元且优先级比mij高的消息集合；Tbus表示FlexRay总线通信周期的长度；Tslot表示FlexRay总线静态段时隙的长度；I（mij）表示消息mij在等待队列中产生的时延；Y（mij）表示消息mij和其他优先级高的消息完成发送所需要要的时间长度.通过上述分析，可知消息的WCRT为

根据上述分析结果，可知路径的端到端时延等于：

3 实验与分析

本文参照文献 ［9］中给出的车载电子功能进行抽象和扩展得到实验所需的功能集，并在Matlab中对本文提出的实时性分析算法进行了实现.功能集中包括12个功能 （包括1个场景独立功能）、43个任务、36条消息、25条执行路径，拟设定任务的周期为0.5、1和2三种情况，任务的WCET为0.05，消息的WCTT为0.005.本文给定FlexRay总线配置为：Tbus=0.3，TST=0.16，TDYN=0.14.

为了更好地说明本文提出方法的有效性，首先采用混合整数线性规划算法，完成任务分配 （同时可确定各节点间的通信矩阵）、任务的优先级和周期等属性的分配，在保证满足各路径端到端时限的前提下，以优化端到端时延为目标.从而保证在全局最坏情况下，路径端到端时延已达到比较理想的比较值［10］，如图5、图6中的GWC即是通过该方法得到的结果.然后利用本文提出的算法对场景进行拆分，可得到场景局部的最坏情况，通过对比来对本文提出方法的有效性进行说明.图中的优化率可采用如下公式计算得到：

其中：e2eLatencyGWC表示在系统全局最坏情况下分析得到的路径端到端时延；e2eLatencyLWC表示由场景局部的最坏情况组合得到的路径端到端时延.

图5 任务、消息的WCRT（ECU=6，Scenario=3）Fig.5 WCRT of task and message（ECU=6，Scenario=3）

图6 路径e2e时延优化情况（ECU=6，APP=12）Fig.6 E2e WCRT of each path（ECU=6，APP=12）

图5～图9描述的是在不同场景、ECU单元和功能个数的条件下，通过100次迭代得到的路径端到端时延情况，图中：S代表场景个数；GWC代表全局最坏情况；LWC代表场景局部的最坏情况.本文功能集中共包括11个场景依赖功能，故可能的场景个数的最大值为11.为了使得实验结果图清晰，本文仅列举了场景个数分别为2、4、6、8、10等5种情况下的实验结果.另外，图9对应实验需要的24个功能将通过复用现有12个功能的方式得到.从图5可知，各个场景中任务、消息的WCRT总小于等于全局最坏情况下各自的值.WCRT值为0表示该任务或消息所对应的功能在场景中未运行.

为使实验结果尽量清晰，图6（a）仅给出场景个数为2、4时各个路径的端到端时延情况，图6（b）给出不同场景个数对应的路径时延优化情况.从图6中可知，在给定功能个数的前提下，随着场景个数的增加，优化率基本呈上升趋势.这是因为场景个数增加给本文提出的算法更大的优化空间，故得到的路径端到端时延优化率上升.另外，图6中路径20～23包含在场景独立的功能中，优化率等于0.

图7 不同场景个数对应路径端到端时延优化率的最大值和平均值Fig.7 Maximum and average optimization ratio of e2e WCRT with different scenarios

图8 不同ECU数目对应路径端到端时延优化率的最大值和平均值Fig.8 Maximum and average optimization ratio of e2e WCRT with different ECU

图7对上述情况进行进一步分析，提取出不同场景个数对应时延优化率的最大值和平均值.从图7中可知，优化率的平均值随着场景个数的增加而增加，但是随着场景个数慢慢接近功能个数，增长的幅度慢慢减小，因为此时场景个数变化对各个场景中包含任务、消息个数的影响变弱.所以在给定系统功能集、ECU个数以及任务分配等前提下，系统负载变化的不断加剧使得场景个数增加，路径端到端时延在不同场景中值的变化也增大，从而使得通过场景拆分可能得到的优化率增大.为减小篇幅，后续分析将仅从优化率平均值和最大值变化方面进行描述.

从图8中可知，随着ECU数目增加，优化率持续降低，但是当ECU数目多于7时，变化幅度逐渐变小.因为ECU数目增多，使得每个ECU中分配的任务和总线时隙中分配消息的数目减少，场景拆分给任务、消息的WCRT大小造成的影响变小，故得到的优化率降低.并且随着ECU数目逐渐接近功能个数，优化率基本达到稳定状态.通过上述分析，从另一方面也说明，在一定ECU个数的情况下，新增功能对系统资源的需求其实不必通过增加ECU数目或增强CPU处理能力来达到，而传统的基于全局最坏情况的系统性能分析方法却在某种程度上掩盖了这一事实.

从图9中可知，随着功能个数增加，优化率持续增长.因为在给定ECU和场景个数的前提下，功能个数的增加将使得每个ECU中的任务、总线中需发送消息的个数增加，场景拆分对任务、消息的WCRT影响变大，从而增大了时延的优化空间.通过此分析可知，随着VES的日益复杂，本文提出的场景拆分算法在实时性分析优化方面所发挥的作用将越来越明显.

图9 不同功能个数对应路径e2e时延优化率的最大值和平均值Fig.9 Maximum and average optimization ratio of e2e WCRT with different APP

4 结语

由于系统复杂性的持续增长、与物理环境交互的日益频繁，下一代车载电子系统将在实时性、可靠性等的分析和验证方面面临重大挑战.本文根据VES系统负载动态变化的特点，提出了一种基于场景的实时性分析方法，并设计了相应的场景拆分算法.通过实验证明了该方法可有效降低现有的基于全局最坏情况的实时性分析方法的悲观程度，从而在降低系统成本和优化系统可扩展性方面将发挥积极作用.

［1］NAVET N，SONGY，SIMONOT-LION F，et al.Trends in automotive communication systems［J］.Proceedings of the IEEE，2005，93（6）：1204-1224.

［2］MITZLAFF M，KAPITZA R，SCHRODER-PREIKSCHAT W.Enabling mode changes in a distributed automotive system［C］//Proceedings of the 1st Workshop on Critical Automotive Applications：Robustness&Safety.Valencia：［S.l.］，2010：75-78.

［3］HENIA R，ERNST R.Scenario aware analysis for complex event models and distributed systems［C］//IEEE. Proceedings of the 28th IEEE International Real-Time Systems Symposium.Tucson：IEEE，2007：171-180.

［4］TRAUB M，STREICHERT T，KRASOVYTSKYY O，et al.Scenario extraction for a refined timing analysis of automotive network topologies［C］//Proceedings of Design，Automation Test in Europe Conference Exhibition（DATE）.Dresden：［S.l.］，2010：81-86.

［5］AUTOSAR.AUTOSAR［EB/OL］.［2014-12-25］.http：//www.autosar.org.

［6］IXXAT Automation GmbH Company.FLEXRAY CCM［EB/OL］.［2014-12-20］.http：//www.ixxat.com/flexray＿ccm＿en. html，

［7］HARBOUR M G，KLEIN M，LEHOCZKY J.Timing analysis for fixed-priority scheduling of hard real-time systems［J］. IEEE Transactions on Software Engineering，1994，20（1）：13-28.

［8］TINDELL K，CLARK J.Holistic schedulability analysis for distributed hard real-time systems［J］.Microprocessors& Microprogramming，1994，40：117-134.

［9］KANDASAMY N，HAYES J P，MURRAY B T.Dependable communication synthesis for distributed embedded systems［J］.Journal Reliability Engineering&Systems Safety，2005，89（1）：81-92.

［10］ZHENG W，QI Z，MARCO D N，et al.Definition of task allocation priority assignment in hard real-time distributed systems［C］//IEEE.IEEE International Real-Time Systems Symposium.Tucson：IEEE，2007：166-170.

A Scenario-Aware Method to Optimize the Real-Time Performance Analysis for Automotive Electronic Systems

XIE Yong，CHEN Xu-hui，XU Hua-rong，WANG Xiao-dong
（School of Computer&Information Engineering，Xiamen University of Technology，Xiamen 361024，China）

A scenario-based real-time analysis of AES was introduced and a log-based automatic scenario decomposing algorithm designed by replacing the global worst case with the local worst case as the basis for optimal real-time analysis to enhance the system’s extensibility and decrease its cost.The simulation result has verified the effectiveness of this approach.

automotive electronic system；scneario decomposing；real-time；optimization

TP302；U463.6

A

1673-4432（2015）01-0008-07

（责任编辑 雨 松）

2014-12-26

2015-01-13

国家自然科学基金项目 （61173036）；厦门理工学院高层次人才项目 （YKJ13024R）；厦门理工学院国家自然科学基金预研项目 （XYK201437）；厦门市科技计划高校创新项目 （3502Z20131158，3502Z20133033）

谢勇 （1985-），男，讲师，博士，研究方向为汽车电子系统.E-mail：yongxie@xmut.edu.cn