龔志鵬陳特放鄒復(fù)民陳意軍陳軍根

①（中南大學(xué)信息科學(xué)與工程學(xué)院 長(zhǎng)沙 410083）

②（湖南工程學(xué)院電氣與信息工程學(xué)院 湘潭 411104）

③（福建工程學(xué)院福建省汽車電子與電驅(qū)動(dòng)技術(shù)重點(diǎn)實(shí)驗(yàn)室 福州 350108）

基于FlexRay靜態(tài)段快速最優(yōu)調(diào)度算法

龔志鵬*①②陳特放①鄒復(fù)民③陳意軍②陳軍根②

①（中南大學(xué)信息科學(xué)與工程學(xué)院 長(zhǎng)沙 410083）

②（湖南工程學(xué)院電氣與信息工程學(xué)院 湘潭 411104）

③（福建工程學(xué)院福建省汽車電子與電驅(qū)動(dòng)技術(shù)重點(diǎn)實(shí)驗(yàn)室 福州 350108）

FlexRay正成為新一代車載通信網(wǎng)絡(luò)。為解決FlexRay靜態(tài)段調(diào)度（FSSS）的幀標(biāo)志（FID）分配難題，該文提出一種基于周期特征的自動(dòng)模型系數(shù)矩陣生成（AMCMG）算法，在大規(guī)模FSSS時(shí)，可快速得到最優(yōu)調(diào)度模型的各類消息調(diào)度屬性并確定系統(tǒng)所需的最少FID數(shù)；為進(jìn)一步確定消息相位，并最終得到完整的周期調(diào)度表，根據(jù)不同周期消息之間調(diào)度的兼容性，提出了一種可實(shí)現(xiàn)最優(yōu)規(guī)劃的基于相位保留規(guī)則FID分配（PRFIDA）算法；最后，仿真實(shí)驗(yàn)結(jié)果表明AMCMG算法能快速正確地建立調(diào)度模型，同時(shí)PRFIDA算法可以實(shí)現(xiàn)消息在已知調(diào)度屬性時(shí)的FID最優(yōu)分配。

車載通信網(wǎng)絡(luò)；F lexRay；靜態(tài)段；幀標(biāo)志分配；相位保留

1 引言

隨著汽車技術(shù)發(fā)展，整車電子電氣架構(gòu)越來越復(fù)雜龐大，為支持日益增多的車載電子控制單元（Electronic Control Unit， ECU）之間實(shí)時(shí)信息交換的需求，迫切需要一個(gè)高速、高可靠、高確定性的網(wǎng)絡(luò)連接［1，2］。新一代車載通信網(wǎng)絡(luò)FlexRay總線基于TTP協(xié)議和Byteflight協(xié)議，由戴姆勒-克萊斯勒公司推出后得到了廣泛的關(guān)注［3，4］。為保證實(shí)時(shí)性，基于事件觸發(fā)的網(wǎng)絡(luò)控制系統(tǒng)需要復(fù)雜的時(shí)基校正算法和擁塞控制規(guī)則［5，6］，而FlexRay總線兼具時(shí)間觸發(fā)和事件觸發(fā)的特點(diǎn)，通過其全局同步時(shí)鐘可預(yù)知傳感器的數(shù)據(jù)采集和執(zhí)行部件的動(dòng)作時(shí)刻，使系統(tǒng)在建模時(shí)可以忽略數(shù)據(jù)的傳輸過程，大幅提升了系統(tǒng)性能，其各項(xiàng)指標(biāo)全面優(yōu)于原有的CAN總線［7］。但是，F(xiàn)lexRay總線的進(jìn)展目前依舊較慢，只有部分廠商在少量車型的個(gè)別ECU節(jié)點(diǎn)采用FlexRay，如寶馬X 5 的懸掛系統(tǒng)等，對(duì)基于眾多ECU的有大量消息交換的整車廣泛FlexRay連接尚未見報(bào)道。FlexRay協(xié)議的復(fù)雜性是影響其應(yīng)用的一個(gè)主要因素，F(xiàn)lexRay靜態(tài)段的消息調(diào)度類似于多核計(jì)算機(jī)系統(tǒng)的并行調(diào)度問題，但卻有更復(fù)雜的約束條件，使得調(diào)度更難實(shí)現(xiàn)［8］，是目前國(guó)內(nèi)外研究熱點(diǎn)和難點(diǎn)之一。其中文獻(xiàn)［9， 10］對(duì)靜態(tài)段在線和離線調(diào)度的時(shí)序研究，得出了最壞響應(yīng)時(shí)間計(jì)算方法， 文獻(xiàn)［11］對(duì)靜態(tài)段傳輸可靠性進(jìn)行了分析，估計(jì)了消息的最小重傳次數(shù)，文獻(xiàn)［12］討論了靜態(tài)段數(shù)據(jù)封裝對(duì)帶寬利用率的影響和最優(yōu)靜態(tài)時(shí)隙長(zhǎng)度，文獻(xiàn)［13］則提出了靜態(tài)段調(diào)度的混合遺傳算法，但當(dāng)消息多時(shí)由于基因鏈增長(zhǎng)導(dǎo)致調(diào)度效率不高，且只能得到近似解，文獻(xiàn)［14］提出一種2維裝箱算法，但規(guī)劃規(guī)模隨消息增多而增大，最終也只能求助于啟發(fā)式算法，而文獻(xiàn)［15］基于數(shù)論的方法就靜態(tài)段調(diào)度提出了一種消息分類調(diào)度模型，這種模型的輸入規(guī)模與消息數(shù)量無關(guān)，可以較好地確定消息調(diào)度的最優(yōu)幀標(biāo)識(shí)（Frame IDentification， FID）數(shù)，但面臨系數(shù)輸入工作量大、模型生成困難、應(yīng)用不夠靈活等問題，而且優(yōu)化結(jié)果并不能明確每一消息的具體分配。為此，本文針對(duì)該問題擬設(shè)計(jì)一種應(yīng)對(duì)消息數(shù)量多、周期分布廣的大規(guī)模FlexRay靜態(tài)段最優(yōu)調(diào)度實(shí)現(xiàn)算法，并通過采用基于周期特性的大型優(yōu)化問題系數(shù)樹生成方法，使調(diào)度模型能夠自動(dòng)生成，同時(shí)將提出一種基于相位保留規(guī)則的最優(yōu)FID分配方法以完整實(shí)現(xiàn)FlexRay靜態(tài)段的調(diào)度，有望為基于F lexRay的大規(guī)模嵌入式汽車應(yīng)用提供一種實(shí)際可行的最優(yōu)解決方案。

2 靜態(tài)段調(diào)度模型及問題描述

FlexRay的數(shù)據(jù)通信是由不斷重復(fù)的長(zhǎng)度為TC（Time of Cycle）的基本通信周期（FlexRay Cycle，F(xiàn)C）構(gòu)成，一個(gè)FC可以分為靜態(tài)段、動(dòng)態(tài)段、符號(hào)窗口和空閑時(shí)間［16］。其中，靜態(tài)段主要用于硬實(shí)時(shí)性、高度確定性且安全關(guān)鍵的周期性數(shù)據(jù)傳輸，如閉環(huán)控制系統(tǒng)中的傳感器采集數(shù)據(jù)，控制器輸出數(shù)據(jù)等［17］。FlexRay靜態(tài)段采用TDMA訪問方式，其消息傳輸如圖1所示，一個(gè)靜態(tài)段由多個(gè)等長(zhǎng)的時(shí)隙（SLOT）構(gòu)成，對(duì)于每個(gè)周期消息，其周期必須是TC的整數(shù)倍，且要求每個(gè)節(jié)點(diǎn)都保有一張調(diào)度表，消息只有在屬于自己的SLOT到來時(shí)才能發(fā)送，每個(gè)SLOT只能傳輸一個(gè)數(shù)據(jù)幀并對(duì)應(yīng)一個(gè)幀標(biāo)記FID。FlexRay支持SLOT復(fù)用，即一個(gè)SLOT可以用于不同的消息，但必須保證不會(huì)沖突。為表述方便，下文描述周期時(shí)都以TC為單位。

圖1 靜態(tài)段消息傳輸

所有消息都至少完成一次完整調(diào)度所需的FC數(shù)稱為調(diào)度超級(jí)周期（Hyper Period， HP）。以圖1為例，共有9個(gè)消息M 1～M 9， HP=4；其中，消息M 1的周期為1，即每個(gè)FC都必須傳輸，所以單獨(dú)占用了FID 1； M 2和M 3的周期為2，共用一個(gè)幀標(biāo)識(shí)FID 2；消息M 4～M 7的周期都為4，所以共用FID 3。在FlexRay通信中，一個(gè)FC的長(zhǎng)度即TC是有限的，考慮到每個(gè)消息只有一個(gè)FID，所以對(duì)于一個(gè)消息，在給定FID的情況下，確定其在一個(gè)HP中第1次出現(xiàn)在哪個(gè)FC，這個(gè)消息的調(diào)度也就確定了，該FC稱為相位。故靜態(tài)段最優(yōu)調(diào)度的目標(biāo)是為所有消息確定相位，且最后使用的或分配的FID數(shù)目最少。

2.1 消息分類模型

K laus Schm idt等人將消息以周期進(jìn)行分類后，在數(shù)論的基礎(chǔ)上提出了一個(gè)最優(yōu)調(diào)度模型如下［15］：

2.2 問題描述

雖然文獻(xiàn)［15］的消息分類模型輸入規(guī)模不會(huì)隨消息數(shù)量增大，規(guī)劃效率較高，但應(yīng)用中依然存在較大困難，主要問題包括：

（1）消息分類模型的建立十分復(fù)雜，模型系數(shù)矩陣獲取困難，在當(dāng)消息周期類型較多情況下，系數(shù)矩陣較為龐大，每一個(gè)系數(shù)都需要額外的計(jì)算，而且對(duì)于不同應(yīng)用，系數(shù)矩陣都不相同，因此模型缺乏靈活性，實(shí)用性較差，沒有充分利用FlexRay協(xié)議的特性。

（2）消息分類模型對(duì)靜態(tài)段調(diào)度并不是一個(gè)完整方案，只是估計(jì)出在最優(yōu)調(diào)度情況下所需的最小FID數(shù)目以及消息的調(diào)度屬性，并未說明如何才能得到最優(yōu)FID的結(jié)果，即并未給出具體消息調(diào)度，不能直接導(dǎo)出周期調(diào)度表。

所以，消息分類模型可“預(yù)言”消息的最優(yōu)值，但其最優(yōu)解只是消息的分類方法，不能直接提供所需的具體分配方案，且消息分類模型建立十分復(fù)雜。為此，基于該模型與消息數(shù)量無關(guān)的優(yōu)良特性，本文將研究并提出一種模型自動(dòng)生成方案，然后根據(jù)所得的消息分類提出一種基于相位保留法的最優(yōu)分配方案，實(shí)現(xiàn)完整的消息調(diào)度。

3 自動(dòng)模型系數(shù)矩陣生成算法

式（2）中，第1個(gè)約束條件為向上取整線性化規(guī)范操作，第2個(gè)約束條件為各周期消息總數(shù)約束。其中，kp（PRi）表示使用調(diào)度屬性PRi的消息所占FID數(shù)，稱為結(jié)果變量，k（PRi）為松弛變量。假設(shè)整線性規(guī)的一般形式為

其中，A為約束方程系數(shù)矩陣，B為約束邊界（對(duì)于等式約束取上下界相等），C為目標(biāo)函數(shù)矩陣，X為輸入向量，O為適維零向量。為生成整線性規(guī)劃模型，需求出對(duì)應(yīng)的A， B， C 3個(gè)系數(shù)。自動(dòng)模型系數(shù)矩陣生成算法的目標(biāo)是根據(jù)系統(tǒng)周期特性，自動(dòng)產(chǎn)生上述系數(shù)矩陣。約束方程分為取整約束和消息總數(shù)約束兩部分，在求取系數(shù)矩陣式時(shí)需遍歷所有質(zhì)因子構(gòu)成的組合。系數(shù)矩陣生成過程以超級(jí)周期HP=30為例，其周期分布為PS=｛1，2，3，5，6，10，15，30｝，按式（2）可得取整約束方程生成樹如圖2所示。

每個(gè)節(jié)點(diǎn)在所有子節(jié)點(diǎn)的系數(shù)矩陣生成完畢后，再加入本節(jié)點(diǎn)的參數(shù)方程，最后在根節(jié)點(diǎn)合成整個(gè)系數(shù)矩陣，具體過程為：

（2）對(duì)于其他層：

圖 2 取整約束方程生成樹

（b）廣度方向矩陣合成如式（5），其中A（n-2）和A（n-1）為需要合并的系數(shù)矩陣，O1和O2為適維零矩陣，A（n）為合并后的系數(shù)矩陣。

（3）約束邊界B矩陣如式（6），其中O3為適維零向量，B1為各周期消息相應(yīng)的數(shù)量構(gòu)成的列向量。

（4）C為目標(biāo)函數(shù)矩陣，對(duì)應(yīng)素?cái)?shù)周期的元素置為1，其余置為零。

根據(jù)上述分析，自動(dòng)模型系數(shù)矩陣生成算法AMCMG可設(shè)計(jì)如表1所示。

表1 AM CMG算法

表1中，取整約束系數(shù)矩陣生成函數(shù)getcoeff（ ）可設(shè)計(jì)如表2所示。

3 基于相位保留的FID分配

針對(duì)2.2節(jié)中的問題（2），即如何根據(jù)消息分類模型求解后得到的各種調(diào)度屬性的消息數(shù)量，確定每個(gè)消息的具體相位，同時(shí)保證調(diào)度依然是最優(yōu)的，為此首先給出如下定義。

定義 1 同類消息：周期相等且調(diào)度屬性相同的所有消息稱為同類消息。

表2 取整約束系數(shù)矩陣生成函數(shù)getcoeff

（1）如果是同類消息，盡可能保持父級(jí)調(diào)度相位不變，即當(dāng)父級(jí)相位沒用完，保持父級(jí)相位不變，先依次用完當(dāng)前相位；否則如果當(dāng)前父級(jí)相位用完，則開啟下一個(gè)新的父級(jí)相位。

（2）如果是兄弟類消息，當(dāng)下一位置應(yīng)該為新相位，則從新相位開始，否則跳出當(dāng)前父級(jí)相位，從下一個(gè)父級(jí)相位開始。

（3）如果是子類消息，則將本來的下一個(gè)同類消息相位擴(kuò)展一位，新擴(kuò)展位為0，即當(dāng)前相位加上新消息周期作為下一個(gè)消息相位。

（4）如果為父類消息，當(dāng)下一個(gè)位置為新相位，則新相位為下一個(gè)消息相位，否則如果不是新相位，則在當(dāng)前父級(jí)級(jí)相位增量作為下一個(gè)消息相位，同時(shí)收縮相位。

根據(jù)以上分析，基于相位保留的FID分配算法PRFIDA可設(shè)計(jì)如表3所示。

表3 PRFIDA算法

定理1 PRFIDA算法能夠?qū)崿F(xiàn)確定調(diào)度屬性下的最優(yōu)FID分配。

證明 PRFIDA算法是從上而下分配相位，即先分配上級(jí)的父類消息，再分配下級(jí)子類和兄弟類消息。對(duì)同類消息，相位保留法與順序分配方法一樣，能分配使用一個(gè)FID的所有相位而不會(huì)產(chǎn)生浪費(fèi)；對(duì)于下級(jí)消息，PRFIDA算法能夠直接在當(dāng)前相位中擴(kuò)展，低一級(jí)相位不會(huì)產(chǎn)生相位浪費(fèi)；對(duì)于兄弟類消息，PRFIDA算法能最大限度地利用上級(jí)相位，產(chǎn)生最小的相位浪費(fèi)，為并行消息盡可能多的保留上級(jí)相位。綜上所述，PRFIDA算法能產(chǎn)生最小的相位浪費(fèi)，從而實(shí)現(xiàn)最優(yōu)調(diào)度。 證畢

例 假設(shè)超級(jí)周期為HP=30，分配消息n（2，3，5）=30，假設(shè)初始相位從0開始分配，則基于PRFIDA算法的各消息的相位依次為：0 6 12 18 24 2 8 14 20 26 4 10 16 22 28 1 7 13 19 25 3 9 15 21 27 5 11 17 23 29。

4 仿真實(shí)驗(yàn)及其分析

為實(shí)現(xiàn)靜態(tài)段消息的完整調(diào)度，本文首先采用AMCMG進(jìn)行靜態(tài)段的自動(dòng)建模，求解后對(duì)各類消息采用PRFIDA算法進(jìn)行最優(yōu)FID分配。為驗(yàn)證AMCMG+PRFIDA方案的有效性及其性能，仿真實(shí)驗(yàn)的硬件配置為Intel I3 2.3G， RAM 2G，軟件配置為MATLAB 2011a環(huán)境下采用TOM LAB/ CPLEX優(yōu)化工具進(jìn)行整線性規(guī)劃。

首先，為驗(yàn)證本文方案在靜態(tài)段調(diào)度建模時(shí)的準(zhǔn)確性和可用性，選用了一組典型的可預(yù)知結(jié)果的實(shí)例進(jìn)行仿真實(shí)驗(yàn)。根據(jù)文獻(xiàn)［18］，不妨采用一些重要標(biāo)準(zhǔn)規(guī)范常用的周期作為HP，例如2n以及支持多消息周期的2310和30030等，并令每種周期的消息數(shù)剛好等于消息周期，即每一種周期的消息剛好占用一個(gè)FID。根據(jù)FlexRay規(guī)范，只要HP給定，則所支持的消息周期的集合PS也就確定了，所需的最少FID數(shù)即為消息周期數(shù)|PS|，因此只需要檢驗(yàn)AMCMG算法的優(yōu)化結(jié)果與|PS|是否相等，即可確認(rèn)AMCMG建立的模型的正確性。隨后，采用PRFIDA算法進(jìn)行消息的FID分配，如果最終所需的FID數(shù)與|PS|相比沒有增加，即可確定實(shí)現(xiàn)了消息的最優(yōu)分配。

表4給出了在上述條件下，9種典型HP配置應(yīng)用AMCMG算法生成模型并用PRFIDA算法進(jìn)行消息分配的實(shí)驗(yàn)結(jié)果，其中|PS|可作為事先確定的最優(yōu)FID數(shù)，F(xiàn)IDOTP為應(yīng)用AMCMG算法生成模型并采用CPLEX優(yōu)化工具所得的預(yù)期最優(yōu)結(jié)果，F(xiàn)IDPR為采用PRFIDA算法進(jìn)行FID分配實(shí)際所需的FID數(shù)。以HP=64為例，不考慮消息周期為1的情形，則系統(tǒng)所支持的消息周期集為PS=｛2，4，8，16，32，64｝，故有消息周期數(shù)量|PS|=6，各消息周期分別有2， 4， 8， 16， 32和64個(gè)消息需要調(diào)度，每一種消息周期的消息依次占用一個(gè)FID，因此可事先確定的最優(yōu)FID數(shù)|PS|=6。結(jié)果顯示，根據(jù)AMCMG算法建立的模型并求解后，最優(yōu)結(jié)果FIDOTP=6，與事先確定的最優(yōu)FID數(shù)|PS|保持一致，證實(shí)了AMCMG算法的正確性；在此基礎(chǔ)上，進(jìn)行PRFIDA的消息FID分配，可得實(shí)際所需的FID數(shù)FIDPR=6，驗(yàn)證了PRFIDA算法能實(shí)現(xiàn)最優(yōu)FID分配。

建立調(diào)度周期表是實(shí)現(xiàn)最優(yōu)FID分配至關(guān)重要的一個(gè)環(huán)節(jié)，為可靠驗(yàn)證PRFIDA算法的準(zhǔn)確性，本文模擬了一種更為復(fù)雜的調(diào)度情景。不妨令消息周期為pi的消息數(shù)量為周期的rate倍，并向上取整，即N（pi）=ceil（rate×pi），表5給出了7種典型HP配置下rate=10.0～10.4時(shí)的實(shí)驗(yàn)結(jié)果，以HP= 64∧rate=10.4為例，此時(shí)系統(tǒng)所支持的消息周期集為PS=｛2，4，8，16， 32， 64｝，各周期的消息數(shù)分別為21，42， 84， 165， 333和666，采用AMCMG算法建立模型并得到最優(yōu)規(guī)劃結(jié)果FIDOTP=63，即預(yù)期所需的最少FID數(shù)為63，當(dāng)采用PRFIDA算法進(jìn)行具體FID分配時(shí)，其實(shí)際分配結(jié)果FIDPR也正好為63，即所需的FID數(shù)沒有額外增加。表5中實(shí)驗(yàn)結(jié)果顯示，對(duì)所有情況均有FIDPR=FIDOTP，即PRFIDA算法能實(shí)現(xiàn)確定調(diào)度屬性下的最優(yōu)FID分配。

為進(jìn)一步驗(yàn)證本文所提方案的效率，擬對(duì)多種大規(guī)模調(diào)度的應(yīng)用場(chǎng)景進(jìn)行模擬實(shí)驗(yàn)。不妨設(shè)周期為pi的消息數(shù)量為N（pi）=np×pi，取 HP=8， 64， 60，2310共4種典型配置種情況下，使np從1到800依次增大，測(cè)試算法所需時(shí)間。為比較算法性能，本文同時(shí)采用了Martin L提出的2維裝箱算法在同樣的條件下進(jìn)行消息調(diào)度，圖3顯示了各算法所需的時(shí)間。圖3（a）顯示，M artin L提出的2維裝箱算法只能在消息數(shù)量少、周期分布簡(jiǎn)單的情況下能夠獲得最優(yōu)解，如HP =8∧np≤15和HP=64∧np≤2時(shí)能夠求解，在消息數(shù)量增加，周期關(guān)系稍微復(fù)雜時(shí)，2維裝箱算法很快就無法求解。圖3（b）顯示了本文AMCMG+PRFIDA方案所需時(shí)間，在所有假設(shè)的實(shí)驗(yàn)條件中，該方案不僅皆能求得最優(yōu)解，實(shí)現(xiàn)消息最優(yōu)FID分配，而且所需時(shí)間明顯更短。同時(shí)，對(duì)于給定的HP，當(dāng)np增大時(shí)，即消息數(shù)量增大時(shí)，算法時(shí)間基本保持不變，顯示了模型輸入規(guī)模與消息數(shù)量無關(guān)的特性。在實(shí)驗(yàn)中，HP=2310∧np=800、消息總數(shù)量達(dá)24800時(shí)，實(shí)現(xiàn)最優(yōu)調(diào)度所需時(shí)間也只有5.1 s。

負(fù)載均衡是FID分配算法的另外一個(gè)重要的性能指標(biāo)，因?yàn)槿绻?fù)載分布均衡，則剩余SLOT可以更方便地為未來系統(tǒng)擴(kuò)展所利用。根據(jù)FlexRay協(xié)議，一個(gè)FC實(shí)際需要傳輸?shù)南?shù)稱為這個(gè)FC的負(fù)載。消息數(shù)量依舊設(shè)N（pi）=ceil（rate×pi），圖4（a）～4（e）展示了在HP=60且rate=10.0～10.4時(shí)各FC實(shí)際分配的消息數(shù)均衡情況，此時(shí)系統(tǒng)支持的消息周期集為PS=｛2，3，4，5，6，10，12，15， 20，30， 60 ｝，支持的消息周期密度較大，具有較好的研究?jī)r(jià)值。當(dāng)rate=10.0時(shí)，每個(gè)周期的消息剛好能夠填滿整10個(gè)FID，這時(shí)系統(tǒng)所需的FID數(shù)為10×11=110個(gè)，每個(gè)FC的傳輸?shù)南?shù)量完全相等，這時(shí)負(fù)載分配是最均衡的；當(dāng)rate不為整數(shù)時(shí)，即使在最優(yōu)規(guī)劃和PRFIDA算法的FID分配時(shí)，有的FID不再能被完全利用，這時(shí)FC的負(fù)載稍有差異，如圖4（b）所示的rate=10.1時(shí)的負(fù)載均衡情況，各FC負(fù)載差別最大，各負(fù)載分布統(tǒng)計(jì)為：1個(gè)FC負(fù)載為 110， 10個(gè)FC負(fù)載為111， 28個(gè)FC負(fù)載為112， 21個(gè)FC負(fù)載為113，負(fù)載分布也基本處于平衡狀態(tài)。

表5 最優(yōu)規(guī)劃預(yù)期FID與采用PRFIDA算法實(shí)際分配的FID結(jié)果

圖3 AMCMG+PRFIDA方案和2維裝箱算法所需時(shí)間比較

圖4 HP=60時(shí)各通信周期的負(fù)載分布

5 結(jié)束語

本文分析了FlexRay靜態(tài)段在整車ECU互聯(lián)應(yīng)用中所面臨的調(diào)度難題，研究了基于FlexRay傳輸?shù)南⑻匦?，討論了文獻(xiàn)［15］中基于消息分類最優(yōu)調(diào)度模型在實(shí)際應(yīng)用中的不足，并在此基礎(chǔ)上提出了AMCMG+PRFIDA方案。其中，AMCMG算法利用了FlexRay靜態(tài)段消息周期分布特性，使得復(fù)雜的消息分類最優(yōu)調(diào)度模型能夠自動(dòng)生成；為進(jìn)一步確定每一個(gè)消息的具體FID和相位分配，并保持先前的原有模型求解時(shí)預(yù)期的最優(yōu)FID分配數(shù)不變，在給定調(diào)度屬性下的，提出了PRFIDA算法進(jìn)行FlexRay靜態(tài)段消息FID分配。仿真實(shí)驗(yàn)結(jié)果表明，AMCMG算法能快速正確地建立調(diào)度模型，PRFIDA算法能使各消息在調(diào)度時(shí)盡可能共用FID，最大限度地減小FID的浪費(fèi)，最終實(shí)現(xiàn)靜態(tài)段消息的整體最優(yōu)調(diào)度。在實(shí)踐中，根據(jù)本文提出的方案，只需確定調(diào)度超級(jí)周期和各類消息的數(shù)量即可得到最優(yōu)調(diào)度結(jié)果，并將每一個(gè)消息的調(diào)度確定到具體位置，從而能夠得到一個(gè)完整的靜態(tài)段調(diào)度表。

［1］ Flem ing B. New automotive electronics technologies［J］. IEEE Transactions on Vehicular Technology， 2012， 7（4）: 4-12.

［2］ Tuohy S and Glavin M. Next generation w ired intra-vehicle networks， a review［C］. Proceedings of IEEE on Intelligent Vehicles Sym posium， Gold Coast， Australia， 2013: 777-782.

［3］ TTTech. Time-triggered p rotocol ttp/c， high-level specification document， protocol version 1.1［OL］. http:// www.tttech.com， 2014.

［4］ Berwanger J and Peller M. Byteflight -a new p rotocol for safety critical applications ［C］. Proceedings of the 2000 FISITA W orld Automotive Congress， Seou l， Korea， 2000: 1-7.

［5］ 王聰， 張鳳荔， 王瑞錦， 等.一種網(wǎng)絡(luò)時(shí)延矩陣分布式自適應(yīng)重建算法［J］. 電子與信息學(xué)報(bào)， 2014， 36（4）: 840-846.

［6］ 羅成， 謝維信. 傳感器網(wǎng)絡(luò)擁塞避免與控制的模糊AQM算法［J］. 電子學(xué)報(bào)， 2014， 42（4）: 679-684.

［7］ Longo S and Herrmann G. Robust scheduling of sam pleddata networked control system s［J］. IEEE Transactions on Control System s Technology， 2012， 20（6）: 1613-1621.

［8］ 徐超， 何炎祥， 陳勇， 等. 一種多核系統(tǒng)可靠性加強(qiáng)的任務(wù)調(diào)度方法［J］. 電子學(xué)報(bào)， 2013， 41（5）: 1019-1024.

［9］ Oued raogo L and Kumar R. Exact response time of flexray communication protocol［C］. Proceedings of W ireless Communications and Mobile Com puting Conference，Istanbu l， Turkey， 2011: 789-794.

［10］ Lange R and Vasques F. Guaranteeing real-time message deadlines in the flexray static segment using a on-line schedu ling app roach［C］. Proceedings of the 9th IEEE International Workshop on Factory Communication Systems，Lemgo， Germany， 2012: 301-310.

［11］ Tanasa B and Bordoloi U D. Reliability-aware frame packing for the static segment of flexray［C］. Proceedings of Em soft，Taipei， China， 2011: 175-184.

［12］ M inkoo K and Kiejin P. Frame packing for m inimizing the bandw idth consum ption of the flexray static segment［J］. IEEE Transactions on Industrial Electronics， 2013， 60（9）: 4001-4008.

［13］ Shan D. A hybrid GA-based scheduling method for static segment in flexray system s［C］. Proceedings of on Control and Decision， Xuzhou， China， 2010: 1548-1552.

［14］ Martin L and M ichael G. Advances in Real-time System s［M］. Berlin: Sp ringer， 2012: 323-339.

［15］ Schm id t K and Schm idt E G. M essage schedu ling for the flexray protocol: the static segment［J］. IEEE Transactions on Vehicular Technology， 2009， 58（5）: 2170-2179.

［16］ FlexRay Consortium. FlexRay communication system s protocol specification， version 3.0.1［OL］. http: //www. FlexRay. com， 2010.

［17］ G renier M， Havet L， and Navet N. Con figuring the communication on flexray: the case of the static segment［C］. Proceedings of the 4th European Congress on Embedded Real Time Software， Toulouse， France， 2008: 1-18.

［18］ AUTOSAR. Specification of flexray network management.［OL］. http://www.autosar.org ， 2013

龔志鵬： 男，1974年生，博士生，講師，研究方向?yàn)檐囕d通信網(wǎng)絡(luò).

陳特放： 男，1957年生，博士，教授，博士生導(dǎo)師，研究方向?yàn)榻煌ㄐ畔⒐こ碳翱刂?

鄒復(fù)民： 男，1976年生，博士，教授，研究方向?yàn)榻煌ㄐ畔⒐こ碳翱刂?

A Fast Op timal Schedu ling A lgorithm for FlexRay Static Segment

Gong Zhi-peng①②Chen Te-fang①Zou Fu-m in③Chen Yi-jun②Chen Jun-gen②①（School of Information Science and Engineering， Central South University， Changsha 410083， China）
②（College of Electrical and Information Engineering， Hunan Institute of Engineering， Xiangtan 411104， China）
③（Fujian Key Laboratory for Autom otive Electronics and Electric Drive， Fujian University of Techno logy，F(xiàn)uzhou 350108， China）

FlexRay is becom ing the in-vehicle communication network of the next generation. To resolve the prob lem of Frame IDentification （FID） assignment in the FlexRay Static Segment Schedu ling （FSSS）， an Autom atic M odel Coefficient M atrix Generating （AMCMG） algorithm is p roposed to ob tain the coefficient matrix automatically based on the characteristics of period distribution. A large-scale p rogramm ing model of FSSS can be generated automatically， and the scheduling properties of all kinds of messages can be derived as well as the m inimum number of FID required for the system can be determ ined quickly. To assign the phase for each message and obtain the comp lete schedu ling tab le， a Phase Reserving based FID Assignment （PRFIDA） algorithm is designed according to the com patibility of messages scheduling in different periods， which is able to keep the op tim al property of the previous p rogramm ing. Finally， the simulation results dem onstrate that the AMCMG algorithm can build the scheduling model rapidly and correctly， and the PRFIDA algorithm can realize the FID assignment optimally based on the known scheduling p roperties of messages.

In-vehicle communication network； FlexRay； Static segment； Frame IDentification （FID） assignment；Phase reserving

TN 915

： A

：1009-5896（2015）05-1200-07

10.11999/JEIT140933

2014-07-15收到，2014-12-17改回

國(guó)家自然科學(xué)基金（60674003），福建省重大專項(xiàng)（2013HZ0002-1），福建省杰出青年基金（2012J06015），湖南省教育廳高校創(chuàng)新基金（12K 127）和湖南省科技計(jì)劃項(xiàng)目（2012GK 3078）資助課題

*通信作者：龔志鵬 zpgong2000@126.com