王躍飛　張　恒　張亞生　劉紅軍

1.合肥工業(yè)大學(xué),合肥,230009　2.安全關(guān)鍵工業(yè)測控技術(shù)教育部工程研究中心,合肥,230009

汽車FlexRay網(wǎng)絡(luò)靜態(tài)段幀封裝機(jī)制研究

王躍飛1,2張恒1,2張亞生1劉紅軍1

1.合肥工業(yè)大學(xué),合肥,2300092.安全關(guān)鍵工業(yè)測控技術(shù)教育部工程研究中心,合肥,230009

在分析FlexRay消息幀格式和幀編碼的基礎(chǔ)上,推導(dǎo)出靜態(tài)時隙長度和總線利用率計(jì)算公式,分析了影響總線利用率的主要因素;提出幀封裝的前提條件，給出了幀有效負(fù)載段上下限精確計(jì)算方法；在此基礎(chǔ)上，以超周期內(nèi)總線利用率最高為優(yōu)化目標(biāo)，建立了解決幀封裝問題的整數(shù)線性規(guī)劃模型，并給出求解該模型的啟發(fā)式算法。SAE實(shí)驗(yàn)結(jié)果證明該方法不僅能夠提高總線利用率，而且可有效縮短算法執(zhí)行時間。

FlexRay總線；靜態(tài)時隙；總線利用率；幀封裝

0　引言

隨著人們對汽車安全性、舒適性的需求不斷增加，現(xiàn)代汽車逐漸向電子化、網(wǎng)絡(luò)化和智能化方向發(fā)展，車內(nèi)電子控制單元(electronic control unit,ECU)的數(shù)量越來越多,ECU間高速實(shí)時的通信需求也越來越大[1-2]。相對于CAN總線,具有高帶寬、高容錯能力的FlexRay總線更能適應(yīng)現(xiàn)代汽車的需求,是事實(shí)上的下一代汽車總線[3-4]。

在FlexRay網(wǎng)絡(luò)中,信號是以消息幀的形式進(jìn)行數(shù)據(jù)傳輸?shù)?。因此，幀封裝問題成為整個汽車網(wǎng)絡(luò)設(shè)計(jì)的關(guān)鍵問題之一。目前，國內(nèi)外學(xué)者已經(jīng)開始對汽車FlexRay網(wǎng)絡(luò)中幀封裝問題進(jìn)行研究[5-12]。文獻(xiàn)[5-7]對FlexRay靜態(tài)段幀封裝進(jìn)行了研究，其中,Kang等[5]提出將數(shù)據(jù)長度較大的消息分配到動態(tài)段發(fā)送,以減少帶寬消耗,但未給出該方法的數(shù)學(xué)模型及算法復(fù)雜度;Kang等[6]提出基于BCMVPS(band width consumption minimizing with various periodic signals)的信號封裝算法,該算法允許不同周期的信號封裝在一起,能夠有效地降低帶寬消耗,但該方法沒有考慮因不同周期的信號封裝在一起,造成較大周期的信號多次發(fā)送,極大地浪費(fèi)了帶寬。文獻(xiàn)[8-9]對FlexRay靜態(tài)段和動態(tài)段幀封裝進(jìn)行了研究,其中Schmidt等[8]建立了解決幀封裝問題的整數(shù)線性規(guī)劃模型,但該模型沒有考慮通信周期的最大范圍,并且在幀封裝機(jī)制上只允許同周期的信號封裝在一起。文獻(xiàn)[10-12]對FlexRay靜態(tài)段優(yōu)化設(shè)計(jì)進(jìn)行了研究,其中，Jang等[10]提出優(yōu)化FlexRay網(wǎng)絡(luò)參數(shù)的兩步設(shè)計(jì)方法,以協(xié)議附加載荷和網(wǎng)絡(luò)空閑浪費(fèi)最小為目標(biāo)函數(shù)，通過幀封裝優(yōu)化靜態(tài)時隙長度，通過幀調(diào)度優(yōu)化通信周期長度,但在求解最優(yōu)靜態(tài)時隙時,沒有考慮靜態(tài)時隙的精確范圍，不能有效地縮短算法執(zhí)行時間;王躍飛等[11]提出基于最小時間碎片的靜態(tài)段設(shè)計(jì)方法，以時間碎片最小為優(yōu)化目標(biāo)，在共用時隙的情況下進(jìn)行信號封裝，但沒有給出具體的求解算法。

在以上研究的基礎(chǔ)上,本文針對FlexRay網(wǎng)絡(luò)靜態(tài)段,提出總線利用率概念，以超周期內(nèi)總線利用率最高為優(yōu)化目標(biāo)，建立解決幀封裝問題的整數(shù)線性規(guī)劃模型，并給出求解該模型的啟發(fā)式算法。

1　FlexRay協(xié)議

1.1幀格式與幀編碼

FlexRay消息幀[13]由幀頭、有效負(fù)載數(shù)據(jù)段和幀尾三部分組成。如圖1所示,幀頭由5個字節(jié)(1位保留位、1位有效負(fù)載預(yù)先指示位、1位空幀指示位、1位同步幀指示位、1位啟動幀指示位、11位幀ID、7位有效負(fù)載數(shù)據(jù)長度、11位幀頭循環(huán)冗余校驗(yàn)(CRC)、6位周期計(jì)數(shù))組成,有效負(fù)載數(shù)據(jù)段由0～254個字節(jié)組成,幀尾由3個字節(jié)的幀CRC組成。

圖1　幀格式與幀編碼

FlexRay消息幀在傳輸時需要對其進(jìn)行編碼。圖1表示傳輸一個有效負(fù)載數(shù)據(jù)長度為l個字節(jié)的消息幀的編碼過程，其中,TSS表示傳輸起始序列,FSS表示幀起始序列，BSS表示字節(jié)起始序列，F(xiàn)ES表示幀結(jié)束序列。

1.2媒體訪問控制

FlexRay總線以通信周期循環(huán)的方式傳輸消息。如圖2所示,一個通信周期包括靜態(tài)段(static segment,SS)、動態(tài)段(dynamic segment,DS)、符號窗口(symbol window,SW)和網(wǎng)絡(luò)空閑時間(network idle time,NIT)四個部分。靜態(tài)段由若干個等長的靜態(tài)時隙(static slot)組成，主要用來傳輸基于時間觸發(fā)的周期性消息，采用時分多址(time division multiple access,TDMA)媒體訪問機(jī)制來保證消息傳輸?shù)拇_定性；動態(tài)段由若干個等長的最小時隙(minislot)組成，主要用來傳輸基于事件觸發(fā)的偶發(fā)性消息，采用柔性時分多址(flexible TDMA,FTDMA)媒體訪問機(jī)制進(jìn)行仲裁傳輸。

圖2　FlexRay通信周期

2　總線利用率計(jì)算方法

2.1靜態(tài)時隙長度

FlexRay靜態(tài)段被劃分為若干等長的靜態(tài)時隙,每個消息幀對應(yīng)唯一的時隙。由圖1可知,當(dāng)消息幀在靜態(tài)段發(fā)送時,除了進(jìn)行幀編碼,還需要添加通信空閑分隔符(communication idle delimiter,CID)和行動點(diǎn)偏移量(action point offset,APO)。其中,APO在靜態(tài)時隙開始處,長度為1～63個宏節(jié)拍(macrotick,MT)時間。

設(shè)FlexRay網(wǎng)絡(luò)有n個節(jié)點(diǎn),通信周期長度為Tbus，靜態(tài)段長度為Tss，靜態(tài)時隙長度為tst,靜態(tài)時隙數(shù)目為Nst，則

Tss=tstNst

(1)

由FlexRay傳輸協(xié)議可知，靜態(tài)時隙長度tst必須大于或等于傳輸最長消息所需的時間。則tst可由下式求得:

(LBSS+8)+δ]+LAPO)

(2)

δ=LTSS+LFSS+LFES+LCID

(3)

其中，LTSS、LFSS、LBSS、LFES、LCID、LAPO分別表示TSS、FSS、BSS、FES、CID、APO的長度。

將表1中FlexRay網(wǎng)絡(luò)參數(shù)值代入式(2)、式(3)，經(jīng)計(jì)算得

(4)

2.2總線利用率

定義1總線利用率(bus utilization rate,BUR)。一段時間內(nèi),FlexRay總線用于傳輸有效數(shù)據(jù)所占用的時間與總時間之比為總線利用率,用TBUR表示。由于本文只研究靜態(tài)段幀封裝,故總時間只考慮靜態(tài)段長度。

定義2超周期。FlexRay網(wǎng)絡(luò)中所有信號發(fā)送周期的最小公倍數(shù)(least common multiple,LCM)為超周期,其長度記為TSP。則

(5)

式中，LCM()為求最小公倍數(shù)函數(shù)。

表2所示為一個FlexRay網(wǎng)絡(luò)信號集合,該網(wǎng)絡(luò)由3個節(jié)點(diǎn)組成,節(jié)點(diǎn)1由3個發(fā)送周期為2 ms的信號組成,節(jié)點(diǎn)2由3個發(fā)送周期為3 ms和2個發(fā)送周期為1 ms的信號組成,節(jié)點(diǎn)3由3個發(fā)送周期為4 ms的信號組成,則TSP=LCM(1,2,3,4)=12 ms。

FlexRay網(wǎng)絡(luò)一個超周期內(nèi)總線利用率可由下式求得

(6)

由式(6)可知,在信號參數(shù)、通信周期已知的情況下,超周期內(nèi)信號所占用的有效帶寬是一定的，總線利用率TBUR與靜態(tài)段長度Tss成反比，即靜態(tài)時隙長度tst與時隙數(shù)目Nst的乘積越小，總線利用率越高，即總線上傳輸有效數(shù)據(jù)所占用的比例越高，帶寬浪費(fèi)越少。

表2　FlexRay信號集合

3　幀封裝

幀封裝即把節(jié)點(diǎn)信號封裝成幀的過程。由FlexRay協(xié)議可知，如果每個信號單獨(dú)作為一幀進(jìn)行數(shù)據(jù)傳輸，由于幀格式及幀編碼將會造成很大的帶寬浪費(fèi)，因此，在實(shí)際網(wǎng)絡(luò)中，必須將多個信號封裝成幀進(jìn)行數(shù)據(jù)傳輸，而這一過程可以抽象為開放式的裝箱問題，即將不同長度的信號作為待裝物品，而幀的有效負(fù)載段作為承載物品的箱子，箱子的容量即幀負(fù)載段長度是可變的。如何選取合適的幀負(fù)載段長度，使得所有信號封裝成幀后的總線利用率最高是解決幀封裝問題的關(guān)鍵。

3.1幀封裝前提條件

為了更準(zhǔn)確地研究該問題，本文作出如下假設(shè)：

(1)在FlexRay通信系統(tǒng)內(nèi)沒有出現(xiàn)消息發(fā)送失敗及數(shù)據(jù)傳輸錯誤等故障；

(2)FlexRay網(wǎng)絡(luò)中所有信號的發(fā)送周期、數(shù)據(jù)位長度、截止期是已知的,并且發(fā)送周期與截止期相等；

(3)所有信號的發(fā)送周期都是通信周期Tbus的整數(shù)倍;

(4)只有相同ECU的信號才能被封裝成一幀，并且每個信號的發(fā)送周期必須是幀的發(fā)送周期的整數(shù)倍。

由假設(shè)(3)可知,通信周期長度Tbus為所有信號發(fā)送周期的最大公約數(shù)(greatest common divisor,GCD),即

(7)

式中，GCD()為求最大公約數(shù)函數(shù)。

由FlexRay協(xié)議可知,通信周期計(jì)數(shù)器取值范圍是0～63，因此，周期性信號的發(fā)送周期不能超過64Tbus。

(8)

3.2幀有效負(fù)載段長度上下限

幀封裝的關(guān)鍵在于幀有效負(fù)載段長度的選取。設(shè)幀有效負(fù)載段長度為Lpl(以字為單位)，由FlexRay協(xié)議可知，2字≤Lpl≤127字,為了更精確地確定Lpl上下限，作出如下定義。

(9)

(10)

(11)

(12)

3.3封裝模型的建立

(13)

設(shè)消息封裝后,節(jié)點(diǎn)i中幀的數(shù)目為Ni,則

(14)

靜態(tài)時隙數(shù)目Nst為

(15)

(16)

(17)

根據(jù)上述相關(guān)內(nèi)容,建立解決幀封裝問題的整數(shù)線性規(guī)劃(ILP)模型：

(18)

(19)

(20)

(21)

Tss

(22)

(23)

xi(k,j)∈{0,1},?k=1,2,…,fi,?j=1,2,…,mi

(24)

(25)

上述幀封裝模型以一個超周期內(nèi)總線利用率最高為優(yōu)化目標(biāo),式(18)為目標(biāo)函數(shù)；式(19)表示信號的唯一性,即每個信號只能封裝在一個幀中;式(20)表示封裝在一個幀中的信號數(shù)據(jù)位長度之和不能超過幀有效負(fù)載段長度;式(21)為幀有效負(fù)載段長度上下限；式(22)表示信號封裝后得到的靜態(tài)段長度要小于通信周期長度。其中的參數(shù)可由式(1)～(5)、式(7)、式(8)、式(10)、式(12)、式(14)～(17)求得。

3.4幀封裝啟發(fā)式算法

隨著信號和節(jié)點(diǎn)數(shù)量的不斷增多,采用ILP模型來解決幀封裝問題的計(jì)算復(fù)雜度越來越高。為了縮短執(zhí)行時間，降低算法復(fù)雜度，本文提出了基于總線利用率的幀封裝啟發(fā)式算法——首次適應(yīng)降序算法(first fit decreasing framing packing based on bus utilization rate,FFD-FPBUR)。圖3所示為幀封裝算法偽代碼,具體步驟如下:

(1)獲取信號和節(jié)點(diǎn)信息,并且將信號按所屬節(jié)點(diǎn)分類;

(2)對于每個節(jié)點(diǎn)i,將信號按數(shù)據(jù)位長度降序排序；

(4)對于每個節(jié)點(diǎn)i,按照FFD算法進(jìn)行封裝,獲得幀集合;

(7)返回最終幀集合及其對應(yīng)的最優(yōu)幀負(fù)載段長度Lpl。

1獲取節(jié)點(diǎn)及節(jié)點(diǎn)所對應(yīng)的信號信息;2將每個節(jié)點(diǎn)中的信號按數(shù)據(jù)位長度大小降序排列;3計(jì)算LLpl和LHpl,初始化LCURpl=LLpl,TBUR=0;4forLCURpl=LLpltoLHpl5for每個ECU節(jié)點(diǎn)6按照FFD算法將每個信號封裝到幀中,每幀負(fù)載段長度不超過LCURpl7endfor8對封裝結(jié)果進(jìn)行可調(diào)度分析;9if幀集合可調(diào)度10計(jì)算TCURBUR;11ifTBUR

圖3FFD-FPBUR算法

由圖3可知,FFD-FPBUR算法主要包括兩個部分:一部分是對獲取的信號進(jìn)行排序,按照冒泡排序法,該部分的算法時間復(fù)雜度為O(n2);另一部分為信號封裝,按照FFD算法封裝的時間復(fù)雜度為O(nlgn),加上外層嵌套的兩個for循環(huán)可以得到該部分總的時間復(fù)雜度為O(n3lgn)。所以該算法總的時間復(fù)雜度為O(n3lgn)。

4　實(shí)驗(yàn)驗(yàn)證

為進(jìn)行對比分析,分別采用文獻(xiàn)[6]和文獻(xiàn)[8]方法對同樣的信號集合進(jìn)行幀封裝。其中，文獻(xiàn)[6]結(jié)果與本文方法一致。文獻(xiàn)[8]結(jié)果如圖4b所示。

(a)本文算法封裝結(jié)果

(b)文獻(xiàn)[8]封裝結(jié)果圖4　信號封裝結(jié)果

表3　信號封裝結(jié)果對比

為了進(jìn)一步驗(yàn)證當(dāng)信號數(shù)量不斷增大時,采用FFD-FPBUR啟發(fā)式算法能夠有效地縮短幀封裝執(zhí)行時間，本文采用美國汽車工程協(xié)會(SAE)的基準(zhǔn)數(shù)據(jù)(表4)進(jìn)行驗(yàn)證。同時,采用MATLAB2013對3.3節(jié)ILP模型進(jìn)行求解。為了增大信號集合,以表4數(shù)據(jù)為初始數(shù)據(jù)，采取隨機(jī)抽取SAE基準(zhǔn)數(shù)據(jù)的方法，將信號添加到初始數(shù)據(jù)集合中。

表4　SAE基準(zhǔn)數(shù)據(jù)

圖5　幀有效負(fù)載段上下限

為了進(jìn)行對比，采用文獻(xiàn)[6]和文獻(xiàn)[8]方法得到的幀有效負(fù)載段取值范圍為2字≤Lpl≤127字。這說明采用本文方法能夠精確地計(jì)算出幀有效負(fù)載段取值范圍,減少算法的迭代次數(shù),從而縮短算法的執(zhí)行時間，如圖6所示。

圖6　三種方法執(zhí)行時間對比

圖7為求解ILP模型所用時間TILP與采用FFD-FPBUR 算法所用時間TFFD-FPBUR比值圖。從圖7中曲線走勢可以看出,當(dāng)信號規(guī)模過大時,已經(jīng)無法通過求解ILP模型得到最優(yōu)結(jié)果,此時,必須采用近似啟發(fā)式算法求解。

圖7　最優(yōu)求解與近似求解執(zhí)行時間比較

圖8分別為采用求解ILP模型、FFD-FPBUR算法與文獻(xiàn)[6]和文獻(xiàn)[8]方法對信號進(jìn)行封裝后的總線利用率。從圖8中可以看出，采用FFD-FPBUR算法與求解ILP模型所得結(jié)果較為相近,這兩種方法都優(yōu)于文獻(xiàn)[6]和文獻(xiàn)[8]的方法。

5　結(jié)語

本文對FlexRay靜態(tài)段的幀封裝方法進(jìn)行了研究。首先引入總線利用率概念,分析影響總線利用率的主要因素;其次,提出幀封裝的前提條件，給出幀有效負(fù)載段上下限精確計(jì)算方法，在此基礎(chǔ)上，以超周期內(nèi)總線利用率最高為優(yōu)化目標(biāo)，建立解決幀封裝問題的整數(shù)線性規(guī)劃模型，并給出求解該模型的FFD-FPBUR算法；最后，通過SAE實(shí)驗(yàn)證明了本文方法的有效性，即不僅能夠提高總線利用率，而且可有效縮短算法執(zhí)行時間。

[1]張利,張本宏,王躍飛,等.基于總線占用率的FlexRay消息時隙分配方法研究[J].中國機(jī)械工程,2012,23(6):699-703.

Zhang Li,Zhang Benhong,Wang Yuefei,et al.Research on FlexRay Messages Slot Distribution Methods Based on Bus Occupancy Rate[J].China Mechanical Engineering,2012,23(6):699-703.

[2]Navet N,Song Yeqiong ,Simonot-lion F,et al.Trends in Automotive Communication Systems[J].Proceedings of the IEEE,2005,93(6):1204-1223.

[3]王躍飛,殷健力,張利,等.基于時間約束的汽車FlexRay網(wǎng)絡(luò)動態(tài)段參數(shù)設(shè)計(jì)[J].中國機(jī)械工程,2014,25(15):2070-2075.

Wang Yuefei,Yin Jianli,Zhang Li,et al.Parameters Design of FlexRay Dynamic Segment under Time Constraints[J].China Mechanical Engineering,2014,25(15):2070-2075.

[4]王躍飛,王子涵,張利,等.基于改進(jìn)調(diào)度算法的新一代汽車總線及其網(wǎng)關(guān)[J].電子測量與儀器學(xué)報(bào),2011,25(10):894-900.

Wang Yuefei,Wang Zihan,Zhang Li.A New Generation Automotive Bus and Relative Gateway Based on Improved Scheduling Algorithm[J].Journal of Electronic Measurement and Instrument,2011,25(10):894-900.

[5]Kang M,Park K,Kim B.A Static Message Scheduling Algorithm for Reducing FlexRay Network Utilization[C]//IEEE International Symposium on Industrial Electronics.Seoul,2009:1287-1291.

[6]Kang M,Park K,Myong-Kee J.Frame Packing for Minimizing the Bandwidth Consumption of the FlexRay Static Segment[J].IEEE Transactions on Industrial Electronics,2013,60(9):4001-4008.

[7]張建軍,于萍,張本宏,等.基于帶寬利用率的FlexRay靜態(tài)段研究[J].計(jì)算機(jī)應(yīng)用研究,2012,29(12):4974-4976.

Zhang Jianjun,Yu Ping,Zhang Benhong,et al. Research on FlexRay Static Segment Based on Bandwidth Utilization[J].Application Research of Computers,2012,29(12):4974-4976.

[8]Schmidt K,Schmidt E G.Message Scheduling for the FlexRay Protocol:the Static Segment[J].IEEE Transactions on Vehicular Technology,2009,58(5):2170-2179.

[9]Schmidt E G,Schmidt K.Message Scheduling for the FlexRay Protocol:the Dynamic Segment[J].IEEE Transactions on Vehicular Technology,2009,58(5):2160-2169.

[10]Jang K,Park I,Han J,et al.Design Framework for FlexRay Network Parameter Optimization[J]. International Journal of Automotive Technology,2011,12(4);589-597.

[11]王躍飛,張純鵬,張利,等.基于最小時間碎片的汽車FlexRay網(wǎng)絡(luò)設(shè)計(jì)[J].電子測量與儀器學(xué)報(bào),2014,28(3):299-305.

Wang Yuefei,Zhang Chunpeng,Zhang Li,et al.Design of Automative FlexRay Network Based on Minimum Time Debris[J].Journal of Electronic Measurement and Instrument,2014,28(3):299-305.

[12]謝勇,李仁發(fā),阮華斌,等.最優(yōu)的FlexRay靜態(tài)段配置算法[J].通信學(xué)報(bào),2012,11(33):33-40.

Xie Yong,Li Renfa,Ruan Huabin,et al.Optimal Configuration Algorithm for Static Segment of FlexRay[J].Journal on Communications,2012,11(33):33-40.

[13]FlexRay Consortium,FlexRay Protocol Specification Version 3.0.1.[EB/OL].[2015-04-30].http://www.flexray.com.

(編輯王艷麗)

Research on Frame Packing Mechanism of Static Segment in Automobile FlexRay Network

Wang Yuefei1,2Zhang Heng1,2Zhang Yasheng1Liu Hongjun1

1.Hefei University of Technology,Hefei,230009 2.Engineering Research Center of Safety Critical Industrial Measurement and Control Technology of Ministry of Education,Hefei,230009

On the basis of analyzing FlexRay frame format and coding,the calculation formula of the length of static slot and bus utilization rate were obtained,and main factors that influenced bus utilization rate were given.Some prerequisites of frame packing and exact calculation method of lower and upper bounds of the size of the payload segment were proposed.Finally, with the target of realizing highest bus utilization rate in super cycle,the integer linear programming model was established to solve the problem of frame packing and heuristic algorithm of solving the model was given.The American socity of automotive engineers(SAE) experimental results demonstrate the effectiveness of the proposed method,which raises the bus utilization rate,and reduces the execution time of algorithm.

FlexRay bus;static slot;bus utilization rate;frame packing

2015-04-30

國家自然科學(xué)基金資助項(xiàng)目(61202096);教育部留學(xué)回國人員科研啟動基金資助項(xiàng)目([2013]693);中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(2013HGCH0014);安徽省省級高等學(xué)校自然科學(xué)研究資助項(xiàng)目(KJ2012A226);江淮汽車技術(shù)中心資助項(xiàng)目(W2014JSKF0086)

TN915.04DOI：10.3969/j.issn.1004-132X.2015.22.007

王躍飛，男，1977年生。合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院、教育部安全關(guān)鍵工業(yè)測控技術(shù)工程研究中心副教授。主要研究方向?yàn)槠嚲W(wǎng)絡(luò)、實(shí)時系統(tǒng)、網(wǎng)絡(luò)控制等。發(fā)表論文20余篇。張恒,男,1987年生。合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院、教育部安全關(guān)鍵工業(yè)測控技術(shù)工程研究中心碩士研究生。張亞生，男，1990年生。合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院碩士研究生。劉紅軍,男,1990年生。合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院碩士研究生。