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