摘要：针对LIN总线的特点,分析了数据打包算法对LIN总线带宽利用率性能 的影响,提出了一种LIN总线带宽利用率最优的算法——完全搜索树算法。研究结果 表明,该算法能够实现LIN总线带宽利用率的最优解,并能进一步降低LIN总线的总线 负载率。

 

关键词：LIN总线；数据打包算法；带宽利用率；总线负载率

 

LIN(Local Interconnent Network)协议是由汽 车厂商专门为汽车开发的一种低成本串行通信网 络，用于实现汽车分布式电子系统控制。LIN总 线的目标定位于CAN的辅助总线，用于车身控制 网络的低端场合，实现车身网络的层次化，以降低 汽车网络的复杂程度，保持最低成本⑴。

 

该低成本的串行通信模式和相应的开发环境 巳由LIN协会制定成标准。LIN的标准化为汽车 制造商以及供应商在研发、应用电子产品方面降 低了成本，LIN总线也因此在汽车及其他工业领 域的分布式领域中得到了广泛应用。

 

1 LIN总线打包算法的提出

 

根据 LIN Specification 2. 0 的规定，每个 LIN 的报文帧由LIN总线的帧头和响应两部分组成 (见图1)。每个帧头都固定由3Byte(l个同步间

图1 LIN报文帧

 

隔场、1个同步场以及1个标志符场）组成，响应 则由1 ~8 Byte数据和1 Byte的校验和场组成[2]。

 

每个LIN报文帧真正有用的信息只是数据字 节。为传输这些数据字节，还须传输帧头、检验和 场等与传送数据无关的位。将报文帧这些无关的 位占LIN报文帧的比例称为UN总线的开销 (Overhead)⑴。表 1 为根据 LIN Specification 2. 0 得到的不同数据字节下报文帧的开销。

 

报文帧,能够节省总线带宽（开销最少），并能够 节省发送节点的RAM资源;但对于接收节点来 说，情况恰恰相反:若一个报文帧的数据是分配给 不同的接收节点,每个接收节点必须读取跟自己 节点无关的那一部分数据，这样就会消耗接收节 点不必要的RAM资源。相反，若使用1 ~2 Byte 的报文帧,能节省接收节点的RAM资源，但同时 却消耗了总线带宽[3]。

 

因此,UN报文帧的不同,会影响UN总线性 能(如总线带宽利用率、负载率等）。本文针对LIN 总线数据打包对LIN总线带宽利用率的影响，分 析比较现在较常见的LIN总线打包算法,提出了 一种LIN总线带宽利用率最优化的打包算法。

 

2大字节优先打包算法

 

打包算法的目的是找到一种合理分配LIN总 线报文帧的方法。每个报文帧都会包含许多不同 特性的信号,这些信号通过在LIN总线上不同节 点间传递信号（如开关的开与断）。而打包算法 就是根据这些信号自身不同特征（大小、截止时 间、发送节点等），将它们分配到不同的报文帧。

 

目前，比较常见的LIN总线数据打包算法一 般采用大字节优先打包算法。该算法的基本搜索 思路为:将所有信号打包到尽量小的报文帧中。 若信号能打包到在8 Byte的报文帧中，则将所有 信号打包到最小的报文帧中;若不能,则将截止时 间比较小的信号装入到8 Byte中，然后再次计算 接下来的信号能否打包到在8 Byte的报文帧中， 一直到将所有的信号完成打包。该算法并不能实 现带宽利用率的最优化,下面举例说明。若系统需 —30 取波特率为 9. 6 kb/s，根据 LIN Specification 2.0的定义，可计算出不同数据字节下传输的理 论值与最大值（见表3)。由于LIN总线主要被用 作车身辅助总线，其工作环境比较艰苦，故本文取 LIN报文帧传输最大值作为其传输时间。

 

表3不同数据字节下LIN报文帧的理论值及最大值

 

同时，在实时传输总线中，总线带宽利用率= 每个报文帧在总线上的传输时间/报文帧里各个 信号中截止时间的最小值w。据此,可计算出各 种打包策略下LIN总线的带宽利用率。

 

表4列出了不同的打包策略。由表4可知， 打包策略不同,其带宽利用率差别非常大。

 

通过大字节优先打包算法,可以将4个信号 全部打包到一个数据帧里面（见表4序号4)。由 表4可知,通过大字节优先打包算法得到的带宽 利用率为27.4 %,与其余的打包策略相比,并非 带宽利用率的最优解。

 

3完全搜索树算法

 

完全搜索树算法选用短任务优先（EDF)作为 搜索树的基本假设条件，以决定哪个信号应该被 选中,然后打包到UN的报文帧里面。

 

搜索树形成的主要步骤如下：

 

(1)首先通过截止时间大小给每个信号排 序，截止时间小的信号先进行数据打包。

 

(2)然后选定第一个信息，计算出打包该信 号UN报文帧需要的最小字节以及打包所有信号 UN报文帧所需要的最大字节。若最大字节>8 Byte,完全搜索树将被分支为最小字节至8 Byte 之间;若最大字节<8 Byte,则完全搜索树将被分 支到最小字节至最大字节之间。

 

(3)选定接下来的信号，计算该信号是否能 被打包到与上一个信息相同的报文帧。若可以， 将该信号打包至这个报文帧;若不能,则计算出打 包该信号需要的最小字节以及打包余下的所有信 号需要的最大字节。如果最大字节&8 Byte,搜 索树将被分支为最小字节至8Byte之间；如果最 大字节<8 Byte,则搜索树将被分支到最小字节 至最大字节之间。

 

(4)重复步骤3,直到所有的信号完成打包

为止。

 

(5)搜索树形成以后，反转搜索树，将每一个 搜索树分支得到的带宽利用率分别加起来，找出 一个最小的搜索树分支。

 

下面用完全搜索树算法来打包表2的各个信 号，以说明完全搜索树算法能够实现LIN总线带 宽利用率的最优,该算法搜索过程如图2所示。 同时，在该搜索树形成过程中，对于每个待打包的 新信号，都需要计算该信号打包到报文帧后总线 带宽利用率的变化。如图2中的节点S3( 1,7. 9/ 50)表示信号S3已经被打包到1 Byte的报文帧 中,总线上带宽利用率的变化为7. 9/50(传输时 间/信号的截止时间）。

 

搜索树完成以后,总共得到9条分支,将每条 分支得到的带宽利用率分别加起来，得到每个分 支的带宽利用率(见表5)。同时，由表5可知，最 优的打包策略是分支3 ,得到的带宽利用率最优