近年来,人们在安全、节能和环保等方面对汽车提出的越来越严苛的要求,使得车联网技术在汽车上得到了广泛应用.但是上述发展趋势造成车载网络系统的复杂性骤增,如一些高档轿车车内网络通信节点ECU (electronic control unit)的个数达70多个,由ECU中的计算任务产生的通信信号的个数多达4 716个^[1-3].因此,车载实时网络系统的优化设计,是车联网技术在汽车上得到广泛应用的关键.CAN是在车上应用最为广泛的一种实时网络技术,如宝马7系的中央控制子系统等4个子系统均采用CAN来实现不同ECU之间的通信和协

作^{[2, 4]}.但是CAN的带宽极其有限,其最大带宽仅为1Mbps(在工业应用中,常采用的CAN的带宽配置为500kbps,256kbps或125kbps).针对该问题,虽然汽车工业界相继提出了另外两种网络协议FlexRay和CAN FD,但是在未来较长一段时间内,CAN仍旧是车内实时网络技术的主角^[2].因此,如何对CAN网络系统进行带宽高效的优化设计,是汽车工业界亟待解决的关键问题.

信号打包(signal packing problem,简称SPP)是CAN网络系统设计需解决的首要问题^[5],因为仅当ECU中的计算任务产生的通信信号被打包成符合CAN协议的消息之后,才能在网络上进行调度和传输.SPP问题是典型的NP难问题,现有研究一般将其转化为经典的装箱问题,并提出启发式算法来进行求解.如Sandstrom等人^[6]先依据Deadline对信号进行排序,然后按照Next Fit Decreasing启发式策略依次将信号插入已有消息之中.当已有消息中的剩余负载空间不够容纳当前信号时,新生成一个空消息来容纳该信号.Saket等人^[7]则先按照带宽利用率对信号进行排序,然后交替着对队列中的首信号和尾信号进行处理,以增加周期大小相近的信号打包到同一个消息中的机会,从而实现带宽利用率的优化.Polzlbauer等人^[8]提出了一个基于带宽利用率分析的指标来判断是否将当前信号插入已有消息之中,并提出了基于Next-Fit-Decreasing的启发式策略来对信号进行处理,并且作者通过实验证明,该算法比文献^[6]中的算法更优.Polzlbauer等人^[9]提出了以可扩展性优化为目标的CAN信号打包算法,以兼容未来功能扩展带来的变化.Xie等人^[10]研究了安全感知的CAN信号打包算法,以保障CAN通信的安全性.但是上述算法均以单个信号作为打包处理的基本单元,每 次打包仅完成一个信号的打包,而未就周期大小相同的信号进行统一打包处理,且未就已有消息负载中剩余的空闲带宽进行量化分析和利用,这将造成带宽的浪费.Urul^[11]提出先将信号集按照Best-Fit-Decreasing的策略进行初始打包,然后再尝试将消息拆分插入到其他周期更小的消息中,以优化带宽利用率.但是该算法局限于消息级的带宽利用率的分析和优化,未就周期大小相等的信号进行统一打包.Bordoloi等人^[12]提出了一种基于动态编程的CAN FD信号打包算法,但是一方面,CAN FD与CAN在消息负载配置、消息头和消息内容两部分的传输速率等方面不同;另一方面,该算法仅适用于信号大小为整数个字节的情况,不具备通用性.除此之外,Wang等人^[13]和Hao等人^[14]研究了CAN网络系统设计在消息层拓扑结构和节点分组方面的问题,但是未考虑信号打包问题.Ayed等人^{[15, 16]}和Schlesinger等人^[17]分别研究了面向AFDX和Profinet网络的信号打包算法,但是上述网络协议与CAN完全不同,因此所提出的算法无法直接应用到CAN.综上所述,CAN信号打包问题的现有研究成果在带宽利用率优化方面存在不足,不能满足车联网应用发展的需求.针对该问题,本文采用信号分簇的思想,首先按照周期大小将信号集划分为多个信号簇,在打包的过程中,以信号簇而不是单个信号作为打包的基本单元;然后,按照周期大小升序的启发式过程对信号簇进行打包,并提出两个空闲带宽评价指标来完成信号打包策略的评价和选择.通过尽量降低消息中的带宽浪费,来实现带宽利用率的优化.

第1节介绍本文采用的系统模型和相关的假设前提.第2节借助一个事例来阐述本文的主要思想.第3节为提出的算法的详细描述.第4节为算法的实验验证和分析.最后,对本文的工作进行总结和展望.

1 系统模型和假设前提

如图 1所示,本文假设车联网环境下的汽车电子系统包含的CAN子系统由多个ECU通过CAN互连组成. ECU集合可表示为:E={E₁,E₂,…,E_h,…,E_|E|},每个ECU中包含一个信号集S_h={s_h,1,s_h,2,…,s_h,i,…,s_h,|S|}.由于信号打包是针对单个ECU中包含的信号集,为了简化描述,本文在后续的描述中省略信号标识符中代表其归属ECU的下标h,即,假设ECU中包含的信号集为S={s₁,s₂,…,s_i,…, s_|S|}.信号的时间属性可通过一个三元组进行描述: s_i:{ST_i,SC_i,SD_i},分别表示信号的周期(单位为ms)、大小(单位为bit)和截止时限(deadline,单位为ms),并且本文假设ST_i=SD_i^{[6, 7, 11]}.

信号需要先打包成消息才能在CAN网络中进行调度和传输,本文假设信号集S打包后得到的消息集为: M={m₁,m₂,…,m_j,…,m_|M|}.消息m_j的时间属性同样可通过一个三元组进行描述:{MT_i,MC_i,MD_i},分别表示周期(单位为ms)、大小(单位为bit)和Deadline(单位为ms).根据信号打包结果,消息的上述属性的值可按照如下公式进行计算.

$M{{T}_{j}}=min\left( S{{T}_{i}} \right),{{s}_{i}}\in {{m}_{j}}$

(1)

$M{{C}_{j}}=\sum\limits_{{{s}_{i}}\in {{m}_{j}}}{S{{C}_{i}}}$

(2)

$M{{D}_{j}}=min\left( S{{D}_{i}} \right),{{s}_{i}}\in {{m}_{j}}$

(3)

消息大小等于所包含信号的大小之和,消息周期(或Deadline)等于所包含信号的周期(或Deadline)的最小值^{[8, 11]}.m_j在网络中传输所需的最差传输时间(worst-case transmission time)WCTT_j的计算方法如下^[18]:

$WCT{{T}_{j}}=(55+10{{p}_{j}}){{\tau }_{bit}}$

(4)

其中,t_bit表示每个比特位的传输时间.本文假设CAN的带宽为500kbps,因此,t_bit=2ms.p_j表示m_j的实际负载,CAN协议规定p_j的单位为字节(byte),整数p_j的取值范围为1~8.p_j的计算公式如下:

${{p}_{j}}=\left\lceil \frac{M{{C}_{j}}}{8} \right\rceil $

(5)

通过消息的WCTT计算可知,m_j对应的带宽利用率可通过公式(6)进行计算:

${{U}_{j}}=\frac{WCT{{T}_{j}}}{M{{T}_{j}}}$

(6)

本文定义SPP问题的目标是最小化带宽利用率,以提高CAN系统的可扩展性和降低系统成本.打包得到的消息的调度分析将参照文献^[18]中的研究成果来完成.基于上述的模型定义和分析可知,单个ECU中以带宽利用率最小化为目标的SPP问题可形式化描述为如下数学问题:

$Minimize\ \sum\limits_{j=1}^{|M|}{{{U}_{j}}}$

(7)

其中,该问题的求解需满足以下两个限制条件.

(1) 消息的最大负载为64bits(即8bytes),因此,m_j的大小MC_j需满足如下约束条件:

$M{{C}_{j}}\le 64$

(8)

(2) 每个信号都将被唯一打包到某个消息之中,因此,信号打包需满足如下限制条件:

$\sum\limits_{j=1}^{|M|}{{{\chi }_{i,j}}}=1$

(9)

其中,二进制变量c_i,j表示信号s_i是否打包到消息m_j之中:如果是,则c_i,j=1;否则,c_i,j=0.

2 事例说明

表 1给出了事例信号集,本文将结合该信号集来对已有CAN信号打包算法和本文提出的算法进行对比分析,从而指出本文提出的算法的优势.

文献^{[7, 8]}中,以单个信号为单元来进行打包分析.如:首先将s₁打包到m₁之中,然后对s₂的打包归属进行分析.由公式(4)~公式(6)给出的分析可知:相比较于将s₂打包到另一个空消息之中而言(方案1),将其打包到已有消息m₁之中,在带宽利用方面更高效(方案2).两种方案对应的带宽利用率的计算如下.

· 方案 1 对应的带宽利用率:

$\begin{align} & \left( 1.9+0.65 \right)\acute{\ }{{10}^{-}}^{3}=2.55\acute{\ }{{10}^{-}}^{3}: \\ & \left( \left( 55+10\times \left\lceil \frac{30}{8} \right\rceil \right)\times 2 \right)\div 100000=1.9\times {{10}^{-3}}, \\ & \left( \left( 55+10\times \left\lceil \frac{2}{8} \right\rceil \right)\times 2 \right)\div 200000=6.5\times {{10}^{-4}}; \\ \end{align}$

· 方案 2 对应的带宽利用率:

$\begin{align} & 1.9\acute{\ }{{10}^{-3}}: \\ & \left( \left( 55+10\times \left\lceil \frac{30+2}{8} \right\rceil \right)\times 2 \right)\div 100000=1.9\times {{10}^{-3}} \\ \end{align}$

根据上述分析结果可知,将s₁和s₂打包到一起更高效.按照上述思路对s₃进行打包分析,同样将s₃打包到已有消息m₁之中(带宽利用率为2.1x10^-3)比将其打包到另一个空消息之中(带宽利用率为2.225x10^-3)更高效.同理,对于剩余的信号s₄~s₇而言,将其打包到已有消息m₁之中对应的带宽利用更高效.因此,根据文献^{[7, 8]}中的方法,该事例信号集对应的信号打包结果为m₁,其中,m₁={s₁,s₂,s₃,s₄,s₅,s₆,s₇}.

由公式(6)可知,消息的周期决定了带宽利用率的大小.如果先按照周期对信号集进行分簇,然后以信号簇而不是单个信号为单元进行打包,将得到更优的带宽利用率.事例信号集的分簇结果为s₁},{s₂},{s₃,s₄,s₅,s₆,s₇},{s₁}和{s₂}的打包分析与上面的分析相同.但是通过信号簇{s₃,s₄,s₅,s₆,s₇}的打包分析可知,将其打包到一个新的空消息(方案1)比将其打包到已有消息m₁(方案2)对应的带宽利用更高效.因此,事例信号集的打包结果为

${{m}_{1}}=\left\{ {{s}_{1}},{{s}_{2}} \right\},{{m}_{2}}=\left\{ {{s}_{3}},{{s}_{4}},{{s}_{5}},{{s}_{6}},{{s}_{7}} \right\}.$

· 方案 1 对应的带宽利用率:

$\begin{align} & \left( 1.9+0.425 \right)\acute{\ }{{10}^{-}}^{3}=2.325\acute{\ }{{10}^{-}}^{3}: \\ & \left( \left( 55+10\times \left\lceil \frac{32}{8} \right\rceil \right)\times 2 \right)\div 100000=1.9\times {{10}^{-3}}, \\ & \left( \left( 55+10\times \left\lceil \frac{24}{8} \right\rceil \right)\times 2 \right)\div 400000=4.25\times {{10}^{-4}}; \\ \end{align}$

· 方案 2 对应的带宽利用率:

$\begin{align} & 2.5\acute{\ }{{10}^{-3}}: \\ & \left( \left( 55+10\times \left\lceil \frac{32+24}{8} \right\rceil \right)\times 2 \right)\div 100000=2.5\times {{10}^{-3}} \\ \end{align}$

通过上述对比可知,以周期大小相等的信号组成的信号簇为单元进行打包的方法在带宽利用率方面更优.接下来,本文将对提出的基于分簇的信号打包算法进行详细介绍.

3 基于分簇的CAN信号打包算法

本文提出的基于分簇的信号打包算法(clustering-based signal packing,简称CSP)包括两个关键步骤.

(1) 分簇阶段

按照周期大小对信号集进行分簇,并分别按照周期大小和信号大小的升序对信号簇和簇内的信号进行排序.如信号集S可划分为如下多个信号簇:{S₁,S₂,…,S_k,…,S_N},N表示S包含的信号簇的个数.其中,MT_k<MT_k+1.对于信号簇S_k中的两个信号s_i和s_i+1,SC_i≤SC_i+1.

(2) 启发式打包阶段

按照周期大小升序的顺序,依次对各个信号簇进行打包.为了实现带宽利用率的最优化,在启发式打包阶段应尽量高效利用当前已经打包得到的消息中的负载空间,将信号插入到可实现带宽利用率优化的消息之中.为了实现该目标,本文先给出如下两个空闲带宽评价指标来对已有消息中包含的空闲带宽进行形式化描述,从而可在后续的信号簇打包过程中对不同打包方案对应的带宽利用率进行定量分析.

根据CAN协议,消息的负载p_j以字节为单位,但是打包后得到的消息的大小以比特为单位.由公式(5)可知,p_j由消息包含信号的大小之和对8取上整后得到.因此,在消息的负载中存在字节级的空闲带宽.如果该空闲不被利用,其对应的带宽将被浪费掉.

定义 1(字节级的空闲带宽byte_level bandwidth slack,简称BLBS). CAN消息的实际负载中存在的空闲比特,定义为字节级空闲带宽.

消息m_j中包含的BLBS_j的大小可按照如下公式进行计算:

$BLB{{S}_{j}}=8{{p}_{j}}-M{{C}_{j}}$

(10)

CAN消息可允许的最大负载是8bytes,但是在打包的过程中,已有消息的实际负载可能小于8bytes.因此,在已有消息的负载中存在负载级的空闲带宽.

定义 2(负载级的空闲带宽payload_level bandwidth slack,简称PLBS). CAN消息允许的最大负载中存在的未被占用的空闲字节,定义为负载级的空闲带宽.

消息m_j中包含的PLBS_j的大小可按照如下公式进行计算:

$BLB{{S}_{j}}=5bits,PLB{{S}_{j}}=48bits.$

(11)

假设某个已有消息的负载情况如图 2所示,该消息的实际大小为11bits,因此p_j=2.该消息所包含的两个方面的空闲带宽的值分别为

在信号簇的打包过程中,一方面应该最小化已有消息中的BLBS的大小,以降低带宽的浪费;另一方面,当前信号簇是打包到已有消息之中还是空消息之中,取决于哪一个方案对应的带宽利用率更优.根据上述思想,本文提出的启发式信号打包算法CSP的具体描述如下:

算法 1. 基于分簇的CAN信号打包算法伪代码.

Input: signal set S;

Output: message set M.

1. Divide S into clusters of signals with equal period: S={S₁,S₂,…,S_k,…,S_N} //信号集按周期大小进行分簇

2. Sort signal clusters and signals with increasing period and size //信号簇和信号按周期、大小排序

3. for signal cluster S_k in S do

4. if k==1 then //对周期最小的信号簇进行直接打包,并分析生成的消息的BLBS和PLBS

5. Pack the whole S_k into null messages and add those messages into M

6. Update BLBS and PLBS of the obtained messages

7. else //对其他的信号簇,需分析是插入已有消息还是空消息之中

8. Pack signals of S_k into BLBS of existing messages in M and update the corresponding BLBS

9. Update S_k by deleting the already packed signals

10. while (S_k≠NULL) do

11. if sum(PLBS_j) of m_j in M≥sum(MC_i) of s_i in S_k then //已有消息的PLBS足够容纳S_k

12. Apply Bandwidth_Utilization_Analysis(M) //带宽利用率分析

13. if insert S_k into null messages is better then //插入空消息带宽方面更高效

14. Create a null message m_l and pack signals of S_k into it

15. Add m_l to M and update its BLBS_l and PLBS_l

16. Update S_k by deleting the already packed signals

17. else //插入已有消息带宽方面更高效

18. Pack the whole S_k into existing messages of M and update their BLBS and PLBS

19. Break;

20. end if

21. else //已有消息的PLBS之和不够容纳S_k,需先打包S_k中的部分信号

22. Construct a null message m_l and pack signals of S_k into m_l

23. Add m_l into M and update its BLBS_l and PLBS_l

24. Update S_k by deleting the already packed signals

25. end if

26. end while

27. end if

28. end for

29. if Schedulability_Analysis(M)==TRUE do //分析M的可调度性,如果M可调度

30. return M;

31. else //M不可调度,需就打包方案进行调整

32. Packing_Result_Modify(M);

33. return M;

34. end if

CSP算法首先按照周期大小对信号集S进行分簇,周期大小相等的信号分到同一个簇(第1行).然后,分别按照周期大小和信号大小的升序对信号簇和簇内信号进行排序(第2行).接着,依次对各个信号簇进行打包处理(第3行~第28行).如果当前信号簇S_k的周期最小,直接将S_k按照Next-Fit-Decreasing策略打包到空消息之中(第4行~第6行);否则,需要根据带宽利用率情况对S_k是打包到已有消息还是空消息之中进行分析(第7行~第28行).为了尽量优化带宽利用率,先将S_k中的部分信号直接插入已有消息的BLBS中(第8行、第9行).对于S_k中剩余的其他信号,存在两种可能的打包方案,即,将他们打包到已有消息之中或空消息之中.上述两种方案对应的带宽利用率分析过程(第12行)如下所述.

假设S_k中剩余信号的大小之和为SM_k,S_k的周期为T_k.已经打包得到的消息集为{m_j},m_j当前的实际负载为AP_j,且PLBS_j大于SM_k.当把S_k打包到m_j中时,该方案对应的带宽利用率U₁可按照公式(12)进行计算:

${{U}_{1}}=\frac{(55+10\times (A{{P}_{j}}+S{{M}_{k}}))\times {{\tau }_{bit}}}{{{T}_{j}}}$

(12)

当把S_k打包到空消息时,该方案对应的带宽利用率U₂可按照公式(13)进行计算:

${{U}_{2}}=\frac{(55+10\times A{{P}_{j}})\times {{\tau }_{bit}}}{{{T}_{j}}}+\frac{(55+10\times S{{M}_{k}})\times {{\tau }_{bit}}}{{{T}_{k}}}$

(13)

通过上述分析,可选择带宽利用率更小的方案作为最后的打包方案.必须指出的是:当已有消息集中存在多个已有消息,且他们各自包含的PLBS均大于SM_k(或存在多种已有消息组合的PLBS之和大于SM_k)的时候,仅需选择周期最大的消息(或消息组合)进行分析即可.该结论的证明见定理1.

定理 1. 在对信号簇S_k进行打包分析时,如果同时存在多个已有消息的PLBS可容纳S_k,仅需对S_k是插入周期最大的已有消息还是空消息进行分析即可,无需再对S_k是否插入其他周期更小的已有消息进行分析.

证明:假设信号簇S_k包含的信号大小之和为SM_k,m_j为已有消息之中周期最大的消息,m_j的实际负载为AP_j,且PLBS_j≥SM_k(AP_j和SM_k的单位为byte).在对S_k是否打包到m_j之中进行分析的时候,需对“S_k打包到m_j之中”和“S_k打包到空消息m_l之中”两种方案对应的带宽利用率进行对比分析,从而判断出哪一种方案更优.上述两种方案对应的带宽利用率可分别按照公式(14)和公式(15)进行计算.

${{U}_{1}}=\frac{(55+10\times (A{{P}_{j}}+S{{M}_{k}}))\times {{\tau }_{bit}}}{{{T}_{j}}}$

(14)

${{U}_{2}}=\left( \frac{55+10\times A{{P}_{j}}}{{{T}_{j}}}+\frac{55+10\times S{{M}_{k}}}{{{T}_{k}}} \right)\times {{\tau }_{bit}}$

(15)

如果U₁-U₂>0,后一种方案更优;如果U₁-U₂<0,则前一种方案更优;如果U₁-U₂=0,两种方案等同.U₁-U₂的值可按照如下公式进行计算.

$\begin{align} & {{U}_{1}}-{{U}_{2}}=\left( \frac{55+10\times (A{{P}_{j}}+S{{M}_{k}})}{{{T}_{j}}}-\left( \frac{55+10\times A{{P}_{j}}}{{{T}_{j}}}+\frac{55+10\times S{{M}_{k}}}{{{T}_{k}}} \right) \right)\times {{\tau }_{bit}} \\ & \text{ }=\left( \frac{10\times S{{M}_{k}}}{{{T}_{j}}}-\frac{55+10\times S{{M}_{k}}}{{{T}_{k}}} \right)\times {{\tau }_{bit}}. \\ \end{align}$

通过上述分析可知:当给定S_k的前提下,U₁-U₂是否小于0(即,将S_k打包到m_j之中)主要取决于m_j的周期T_j,且U₁-U₂的大小与T_j成反比.因此,在对S_k的打包归属进行分析的时候,仅需对S_k是否能打包到“PLBS大小能容纳S_k且周期最大的已有消息”进行分析即可,因为此时U₁-U₂才最有可能满足小于0的条件,从而不需再对S_k是否能打包到其他“PLBS大小能容纳S_k但周期更小”的已有消息进行分析.

推论1. 在对S_k的打包归属进行分析的时候,当单个已有消息的PLBS不能容纳S_k而需将S_k包含的信号拆分到多个已有消息之中的时候,仅需按照周期大小降序的顺序选择“PLBS大小之和刚好能容纳S_k的多个已有消息组合”,并对相应的带宽利用率进行分析即可,而不需要再对其他“PLBS大小之和能容纳S_k的已有消息组合”进行分析.

上述推论1的证明过程与定理1类似,本文在此不再赘述.

如果将S_k打包到空消息之中更优,则按照Next-Fit-Decreasing策略将S_k中的信号依次打包到空消息之中(第13行~第16行).由于消息的负载有限,如果当前空消息满载后S_k中还剩下有信号,那么继续下一轮While循环对更新后的S_k的打包归属进行继续分析.如果将S_k打包到已有消息之中更优,则按照Next-Fit-Decreasing策略将S_k中的全部信号依次插入已有消息之中,然后结束当前的While 循环(第17行~第19行).

当已有消息的PLBS大小不够容纳信号簇S_k的时候,按照Next-Fit-Decreasing策略将S_k中的部分信号插入空消息之中,然后继续下一轮While循环,对S_k中剩余信号的打包归属进行分析(第21行~第25行).在每个打包步骤之后,均需更新相关消息的BLBS和PLBS,以备下一步的分析.在信号集打包结束后,利用文献^[18]中给出的算法来对消息集M中的消息进行调度分析 (第29行):如果M中的所有消息均可调度,直接返回M作为CSP算法的结果(第30行);否则,需对打包结果M进行相应的修改.如:对不可调度的消息进行拆分直到所有消息均可调度,然后返回修改后的消息集作为打包算法的结果(第32行、第33行).

CSP算法主要包括两个阶段:(1) 信号分簇和排序阶段,该阶段的时间复杂度为O(nlog₂n);(2) 信号簇打包阶段,该阶段的时间复杂度主要来源于for循环、while循环以及while循环中信号插入已有消息的操作步骤,其时间复杂度为O(n³).因此,CSP算法总体的时间复杂度为O(nlog₂n+n³).

4 实验分析

为了验证CSP算法的有效性,本文分别在CAN子系统包含的两组信号集的基础之上与文献^[7](Sak算法)、文献^[8](Pol算法)和文献^[11](Urul算法)中提出的算法进行了对比分析,其中一组信号集符合汽车整车厂提供的真实信号集的特点,另一组信号集则按照信号的周期和大小均匀分布的特点随机生成.为保证实验结果的有效性,本文设置每组信号集中各包括50个信号集,相关的实验结果均是对上述50个信号集的实验结果求平均后得到.本文设置信号集中的信号个数由40个逐渐增加到240个,其对应的网络带宽利用率由25%逐渐增加到接近100%,以实现不同的网络负载情况下的对比分析.本文在Matlab 2013开发环境下进行实验,运行本实验的PC配置如下:1.8GHz Intel Core i7,4G DDR3.

第1组信号集参照某汽车整车厂提供的真实CAN信号集生成^[19],每个信号集中信号的周期和大小的分布符合该真实信号集的特点(具体情况见表 2和表 3).

图 3给出了第1组信号集对应的实验结果,即,与其他3种已有算法相比CSP可实现的带宽利用率优化情况.图 3中的横坐标表示信号集包含的信号个数,纵坐标表示与其他算法相比CSP算法可实现的带宽利用率的优化率情况.如:CSP-Sak-Avg和CSP-Sak-Max分别表示与文献^[7]相比,CSP可实现的带宽利用率的优化率的平均值和最大值,带宽利用率的优化率U_Opt可按照公式(16)进行计算:

$U\_Opt=\frac{U\_Sak-U\_CSP}{U\_Sak}$

(16)

其中,U_Sak和U_CSP分别表示采用Sak算法和CSP算法对信号集打包后得到的消息集的带宽利用率.

为进一步验证CSP算法的有效性,本文采用随机生成的第2组信号集来进行实验.信号集中信号周期的可能取值为[5,10,20,50,100,200,250,400,500,1000](单位:ms),信号大小的可能取值为[1,2,3,4,5,6,7,8,10,12,16,20, 24,32](单位:bit).与第1组信号集不同的是,该组信号集中信号的周期和大小的取值均符合均匀分布的特点.图 4给出了与其他3种已有算法相比,CSP可实现的带宽利用率的优化情况.

图 3和图 4中,分别用虚线和实线表示优化率的平均值和最大值,同颜色的一组虚线和实线对应于与同一种算法的对比结果.

通过上述分析可知:CSP在带宽利用率优化方面最优,Urul算法次之,Pol算法排第3,Sak算法最差.具体对数据集1而言,CSP可实现的带宽利用率的优化率的平均值范围分别为[2.21%,5.29%](相比较于Sak算法),[1.81%,5.41%](相比较于Pol算法),[0.5%,1.5%](相比较于Urul算法);最大值范围分别为[10.28 %,22.65%](相比较于Sak算法),[10.01%,22.65%](相比较于Sak算法),[2.4%,5.4%](相比较于Urul算法).对数据集2而言,CSP可实现的带宽利用率的优化率的平均值范围分别为[2.19%,6.4%](相比较于Sak算法),[1.89%,5.27%](相比较于Pol算法),[1.09%,3.58%](相比较于Urul算法);最大值范围分别为[8.37%,14.07%](相比较于Sak算法),[8%,13.75%](相比较于Sak算法),[2.74%,7.54%](相比较于Urul算法).在上述两组实验中,CSP算法、Sak算法、Pol算法和Urul算法的执行时间分别约为80s,60s,60s和80s.

为了验证CSP算法打包后得到的消息集的可调度性,本文采用文献^[18]中的算法对上述两组信号集打包后得到的消息集进行了调度分析.图 5以第1组信号集中的某个信号集为例,给出了信号打包调度后的最差反应时间(worst case response time,简称WCRT)和Deadline情况,图中的信号按照周期大小升序的顺序进行编号.该信号集共包含300个信号,打包后得到的消息集的带宽利用率约为94.3%.图 5(a)给出了信号集中全部信号的WCRT和Deadline情况,为使实验结果清晰可见,图 5(b)给出了信号集中周期大小前100的信号的WCRT和Deadline情况.从图 5可知:即使当CAN网络接近满负荷的时候,CSP算法仍可保证打包后得到的消息集可调度.

5 总 结

针对车联网环境下车载CAN网络因数据量急剧增长而造成的带宽受限问题,本文研究了CAN网络系统设计方面的信号打包问题,提出了带宽高效的启发式信号分簇打包算法CSP.与现有研究成果不同的是:该算法以周期大小相等的信号组成的信号簇而不是单个信号作为打包分析的基本单元,并提出了两个空闲带宽评价指标来引导启发式算法选择得到带宽高效的打包方案,从而实现带宽利用率的优化.通过分别在接近真实情况的信号集和模拟信号集上与其他3个研究成果进行的对比分析可知:CSP算法在带宽利用率优化方面最优,且能保证打包后得到的消息集可调度.由于汽车工业具备批量生产的特点,即使1%的CAN网络带宽利用率优化也可能带来很大的经济效益.因此,本文提出的CAN信号打包算法可为CAN网络系统的优化设计提供理论上的借鉴,具有一定的实用价值.车联网环境下车载网络通信的可靠性和信息安全问题是汽车电子系统设计需解决的关键问题,因此,下一步作者将对CSP算法在可靠性和信息安全方面进行考虑和扩展.