摘要：針對LIN總線的特點,分析了數(shù)據(jù)打包算法對LIN總線帶寬利用率性能 的影響,提出了一種LIN總線帶寬利用率最優(yōu)的算法——完全搜索樹算法。研究結(jié)果 表明,該算法能夠?qū)崿F(xiàn)LIN總線帶寬利用率的最優(yōu)解,并能進一步降低LIN總線的總線 負載率。
關(guān)鍵詞：LIN總線；數(shù)據(jù)打包算法；帶寬利用率；總線負載率
LIN(Local Interconnent Network)協(xié)議是由汽 車廠商專門為汽車開發(fā)的一種低成本串行通信網(wǎng) 絡(luò)，用于實現(xiàn)汽車分布式電子系統(tǒng)控制。LIN總 線的目標定位于CAN的輔助總線，用于車身控制 網(wǎng)絡(luò)的低端場合，實現(xiàn)車身網(wǎng)絡(luò)的層次化，以降低 汽車網(wǎng)絡(luò)的復(fù)雜程度，保持最低成本⑴。
該低成本的串行通信模式和相應(yīng)的開發(fā)環(huán)境 巳由LIN協(xié)會制定成標準。LIN的標準化為汽車 制造商以及供應(yīng)商在研發(fā)、應(yīng)用電子產(chǎn)品方面降 低了成本，LIN總線也因此在汽車及其他工業(yè)領(lǐng) 域的分布式領(lǐng)域中得到了廣泛應(yīng)用。
1 LIN總線打包算法的提出
根據(jù) LIN Specification 2. 0 的規(guī)定，每個 LIN 的報文幀由LIN總線的幀頭和響應(yīng)兩部分組成 (見圖1)。每個幀頭都固定由3Byte(l個同步間
圖1 LIN報文幀
隔場、1個同步場以及1個標志符場）組成，響應(yīng) 則由1 ~8 Byte數(shù)據(jù)和1 Byte的校驗和場組成[2]。
每個LIN報文幀真正有用的信息只是數(shù)據(jù)字 節(jié)。為傳輸這些數(shù)據(jù)字節(jié)，還須傳輸幀頭、檢驗和 場等與傳送數(shù)據(jù)無關(guān)的位。將報文幀這些無關(guān)的 位占LIN報文幀的比例稱為UN總線的開銷 (Overhead)⑴。表 1 為根據(jù) LIN Specification 2. 0 得到的不同數(shù)據(jù)字節(jié)下報文幀的開銷。
報文幀,能夠節(jié)省總線帶寬（開銷最少），并能夠 節(jié)省發(fā)送節(jié)點的RAM資源;但對于接收節(jié)點來 說，情況恰恰相反:若一個報文幀的數(shù)據(jù)是分配給 不同的接收節(jié)點,每個接收節(jié)點必須讀取跟自己 節(jié)點無關(guān)的那一部分數(shù)據(jù)，這樣就會消耗接收節(jié) 點不必要的RAM資源。相反，若使用1 ~2 Byte 的報文幀,能節(jié)省接收節(jié)點的RAM資源，但同時 卻消耗了總線帶寬[3]。
因此,UN報文幀的不同,會影響UN總線性 能(如總線帶寬利用率、負載率等）。本文針對LIN 總線數(shù)據(jù)打包對LIN總線帶寬利用率的影響，分 析比較現(xiàn)在較常見的LIN總線打包算法,提出了 一種LIN總線帶寬利用率最優(yōu)化的打包算法。
2大字節(jié)優(yōu)先打包算法
打包算法的目的是找到一種合理分配LIN總 線報文幀的方法。每個報文幀都會包含許多不同 特性的信號,這些信號通過在LIN總線上不同節(jié) 點間傳遞信號（如開關(guān)的開與斷）。而打包算法 就是根據(jù)這些信號自身不同特征（大小、截止時 間、發(fā)送節(jié)點等），將它們分配到不同的報文幀。
目前，比較常見的LIN總線數(shù)據(jù)打包算法一 般采用大字節(jié)優(yōu)先打包算法。該算法的基本搜索 思路為:將所有信號打包到盡量小的報文幀中。 若信號能打包到在8 Byte的報文幀中，則將所有 信號打包到最小的報文幀中;若不能,則將截止時 間比較小的信號裝入到8 Byte中，然后再次計算 接下來的信號能否打包到在8 Byte的報文幀中， 一直到將所有的信號完成打包。該算法并不能實 現(xiàn)帶寬利用率的最優(yōu)化,下面舉例說明。若系統(tǒng)需 —30 取波特率為 9. 6 kb/s，根據(jù) LIN Specification 2.0的定義，可計算出不同數(shù)據(jù)字節(jié)下傳輸?shù)睦?論值與最大值（見表3)。由于LIN總線主要被用 作車身輔助總線，其工作環(huán)境比較艱苦，故本文取 LIN報文幀傳輸最大值作為其傳輸時間。
表3不同數(shù)據(jù)字節(jié)下LIN報文幀的理論值及最大值
同時，在實時傳輸總線中，總線帶寬利用率= 每個報文幀在總線上的傳輸時間/報文幀里各個 信號中截止時間的最小值w。據(jù)此,可計算出各 種打包策略下LIN總線的帶寬利用率。
表4列出了不同的打包策略。由表4可知， 打包策略不同,其帶寬利用率差別非常大。
通過大字節(jié)優(yōu)先打包算法,可以將4個信號 全部打包到一個數(shù)據(jù)幀里面（見表4序號4)。由 表4可知,通過大字節(jié)優(yōu)先打包算法得到的帶寬 利用率為27.4 %,與其余的打包策略相比,并非 帶寬利用率的最優(yōu)解。
3完全搜索樹算法
完全搜索樹算法選用短任務(wù)優(yōu)先（EDF)作為 搜索樹的基本假設(shè)條件，以決定哪個信號應(yīng)該被 選中,然后打包到UN的報文幀里面。
搜索樹形成的主要步驟如下：
(1)首先通過截止時間大小給每個信號排 序，截止時間小的信號先進行數(shù)據(jù)打包。
(2)然后選定第一個信息，計算出打包該信 號UN報文幀需要的最小字節(jié)以及打包所有信號 UN報文幀所需要的最大字節(jié)。若最大字節(jié)>8 Byte,完全搜索樹將被分支為最小字節(jié)至8 Byte 之間;若最大字節(jié)<8 Byte,則完全搜索樹將被分 支到最小字節(jié)至最大字節(jié)之間。
(3)選定接下來的信號，計算該信號是否能 被打包到與上一個信息相同的報文幀。若可以， 將該信號打包至這個報文幀;若不能,則計算出打 包該信號需要的最小字節(jié)以及打包余下的所有信 號需要的最大字節(jié)。如果最大字節(jié)&8 Byte,搜 索樹將被分支為最小字節(jié)至8Byte之間；如果最 大字節(jié)<8 Byte,則搜索樹將被分支到最小字節(jié) 至最大字節(jié)之間。
(4)重復(fù)步驟3,直到所有的信號完成打包
為止。
(5)搜索樹形成以后，反轉(zhuǎn)搜索樹，將每一個 搜索樹分支得到的帶寬利用率分別加起來，找出 一個最小的搜索樹分支。
下面用完全搜索樹算法來打包表2的各個信 號，以說明完全搜索樹算法能夠?qū)崿F(xiàn)LIN總線帶 寬利用率的最優(yōu),該算法搜索過程如圖2所示。 同時，在該搜索樹形成過程中，對于每個待打包的 新信號，都需要計算該信號打包到報文幀后總線 帶寬利用率的變化。如圖2中的節(jié)點S3( 1,7. 9/ 50)表示信號S3已經(jīng)被打包到1 Byte的報文幀 中,總線上帶寬利用率的變化為7. 9/50(傳輸時 間/信號的截止時間）。
搜索樹完成以后,總共得到9條分支,將每條 分支得到的帶寬利用率分別加起來，得到每個分 支的帶寬利用率(見表5)。同時，由表5可知，最 優(yōu)的打包策略是分支3 ,得到的帶寬利用率最優(yōu)
