王躍飛 韓江洪 張建軍 彭 浩

合肥工業(yè)大學(xué),合肥,230009

0 引言

隨著汽車電子控制單元(electronic control unit,ECU)數(shù)量不斷增多,汽車網(wǎng)絡(luò)(如CAN、Flexray)多網(wǎng)段化成為了必然[1-3]。在該結(jié)構(gòu)汽車網(wǎng)絡(luò)中,將ECU放置到不同網(wǎng)段中會直接影響車輛總體性能和成本。因此,汽車網(wǎng)絡(luò)結(jié)構(gòu)的設(shè)計與優(yōu)化是整車網(wǎng)絡(luò)設(shè)計需要重點(diǎn)考慮的問題之一[4]。

汽車中與安全密切相關(guān)的ECU(如剎車防抱死系統(tǒng)等)對消息傳輸時間有著嚴(yán)格要求,網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計應(yīng)該考慮這些時間約束。但目前已有的設(shè)計方法主要以降低總線及網(wǎng)關(guān)負(fù)載為目標(biāo),而對網(wǎng)絡(luò)傳輸?shù)膶?shí)時性考慮較少。文獻(xiàn)[5]提出了兩個網(wǎng)段下CAN總線拓?fù)湓O(shè)計的多目標(biāo)優(yōu)化方法,但沒有考慮多網(wǎng)段劃分和消息傳輸實(shí)時性要求。文獻(xiàn)[6]將單調(diào)速率算法應(yīng)用于混合動力汽車CAN網(wǎng)絡(luò)的實(shí)時性分析,給出了通過調(diào)整數(shù)據(jù)優(yōu)先級來改善網(wǎng)絡(luò)實(shí)時性的方法,但該方法只適用于單一網(wǎng)段的網(wǎng)絡(luò)設(shè)計。

針對上述方法不足,本文以滿足消息傳輸?shù)目烧{(diào)度性和降低網(wǎng)關(guān)負(fù)載量為出發(fā)點(diǎn),利用圖分割理論和遺傳算法建立了汽車網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計方法。該方法可應(yīng)用在CAN網(wǎng)絡(luò)及其他汽車網(wǎng)絡(luò)設(shè)計中,具有一定適應(yīng)性。

1 汽車網(wǎng)絡(luò)中的實(shí)時調(diào)度

多網(wǎng)段結(jié)構(gòu)汽車網(wǎng)絡(luò)由網(wǎng)關(guān)和各個網(wǎng)段所組成,如圖1所示。同一網(wǎng)段內(nèi)節(jié)點(diǎn)通過網(wǎng)絡(luò)直接通信,不同網(wǎng)段中的節(jié)點(diǎn)通過網(wǎng)關(guān)進(jìn)行交互。為保證消息傳輸?shù)膶?shí)時性,需要采用一定的網(wǎng)絡(luò)調(diào)度方法。該類調(diào)度方法一般是指應(yīng)用層調(diào)度,與底層網(wǎng)絡(luò)協(xié)議(CAN、LIN)無關(guān),具有較強(qiáng)靈活性和適應(yīng)性[7]。

圖1 多網(wǎng)段結(jié)構(gòu)汽車網(wǎng)絡(luò)

圖1 所示網(wǎng)絡(luò)中消息可以分為兩類：網(wǎng)段間消息和網(wǎng)段內(nèi)部消息。其中,網(wǎng)段間消息被節(jié)點(diǎn)發(fā)送后直接進(jìn)入到網(wǎng)關(guān)內(nèi)部緩沖隊(duì)列。設(shè)在網(wǎng)關(guān)內(nèi)部針對每個子網(wǎng)段都設(shè)置一個虛擬網(wǎng)絡(luò)服務(wù)器(virtual network server,VNS),負(fù)責(zé)內(nèi)部緩沖隊(duì)列中消息的發(fā)送。每個VNS都是一個總帶寬服務(wù)器(total bandwidth server),運(yùn)行機(jī)制如圖2所示[8]。在網(wǎng)段內(nèi)部,各個節(jié)點(diǎn)中的消息與VNS一起采用非搶占最早時限優(yōu)先(earliest deadline first,EDF)算法調(diào)度。

圖2 VNS的預(yù)算補(bǔ)充和時限設(shè)置

網(wǎng)絡(luò)中任何消息均可用三元組(t c,T,t D)表示,其中,tc為消息的網(wǎng)絡(luò)傳輸時間,T為消息的傳輸周期,t D為消息的相對傳輸時限,且T=t D。任意 VNS 用二元組(?u,es)表示,其中 ,?u為 VNS的規(guī)模,e s為它的執(zhí)行預(yù)算。設(shè)n為網(wǎng)絡(luò)中網(wǎng)段的數(shù)目,Mi={m1,m2,…,mr}為網(wǎng)段i中節(jié)點(diǎn)發(fā)送消息集合,Mgi={m1,m2,…,mh}為網(wǎng)關(guān)內(nèi)網(wǎng)段i所對應(yīng)緩沖隊(duì)列中的消息集合,α為網(wǎng)絡(luò)傳輸能力,它等于實(shí)際網(wǎng)絡(luò)帶寬與標(biāo)準(zhǔn)網(wǎng)絡(luò)帶寬的比值。

定理 對于任意網(wǎng)段i,假設(shè)集合Mgi中消息在網(wǎng)絡(luò)傳輸能力αi(αi≤1)的實(shí)際網(wǎng)絡(luò)中是可調(diào)度的,如果存在?ui=αi且式(1)成立,則圖1所示的網(wǎng)絡(luò)中消息一定能滿足其傳輸時限,即都是可調(diào)度的。

證明 對于任意網(wǎng)段i,網(wǎng)絡(luò)中消息分別來自內(nèi)部節(jié)點(diǎn)和網(wǎng)關(guān)。從調(diào)度角度來看,如果把對應(yīng)的VNS看成一個非周期消息,則該消息與節(jié)點(diǎn)消息只要滿足非搶占EDF算法的可調(diào)度條件,就可保證VNS與節(jié)點(diǎn)消息的時限;但是對于網(wǎng)關(guān)內(nèi)消息而言,僅能保證其VNS可調(diào)度是不夠的,還需要保證消息在VNS內(nèi)部可調(diào)度。

由文獻(xiàn)[8]推論可知：如果式(1)成立,節(jié)點(diǎn)消息與規(guī)模為?ui的VNS在非搶占EDF算法下都是可絡(luò)傳輸不可搶占性帶來的影響,els/?ui實(shí)際上是第i個VNS的時限。分析式(1)可知,當(dāng)其成立時,必有?ui≤1,同時,M g i中所有消息在網(wǎng)絡(luò)傳輸能力αi(αi≤1)的實(shí)際網(wǎng)絡(luò)中是可調(diào)度的,且?ui=αi。根據(jù)上述推理結(jié)果,仿照文獻(xiàn)[9]定理3證明過程可以推出M g i中的消息也是可調(diào)度的。

因網(wǎng)段i為任意網(wǎng)段,故已知條件成立時,網(wǎng)絡(luò)中所有消息都是可調(diào)度的。

證畢。

2 網(wǎng)段劃分的圖分割模型

在汽車網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計時,將不同的節(jié)點(diǎn)放入不同的網(wǎng)段,對網(wǎng)絡(luò)負(fù)載量和消息傳輸實(shí)時性有著直接的影響。因此,在網(wǎng)段劃分時需要綜合考慮網(wǎng)絡(luò)負(fù)載量和消息傳輸實(shí)時性兩方面的約束,具體可按以下原則進(jìn)行劃分：

(1)將相互間通信量較大的節(jié)點(diǎn)盡量分配到同一網(wǎng)段中,以降低不同網(wǎng)段間消息傳輸?shù)霓D(zhuǎn)發(fā)時間,減輕網(wǎng)關(guān)負(fù)擔(dān)。

(2)對網(wǎng)段內(nèi)部節(jié)點(diǎn)通信量進(jìn)行限制,以保持各網(wǎng)段負(fù)載均衡,避免懸殊過大。

(3)保證網(wǎng)絡(luò)中消息的可調(diào)度性,確保在其時限內(nèi)完成傳送。

設(shè)汽車網(wǎng)絡(luò)中具有n個節(jié)點(diǎn),每個節(jié)點(diǎn)周期性地向總線發(fā)送數(shù)據(jù)。對于多網(wǎng)段結(jié)構(gòu)的汽車網(wǎng)絡(luò)可以用圖分割模型來描述[10-11]。定義無向圖：

G={V,E,W}

式中,V為汽車網(wǎng)絡(luò)節(jié)點(diǎn)集合,V={v1,v2,…,vn};E為節(jié)點(diǎn)間的相互通信關(guān)系,E={e1,e2,…,ek};W為G邊上的權(quán)值集合,W={wij};wij為節(jié)點(diǎn)vi與節(jié)點(diǎn)vj之間的通信量,令 wii=0。

汽車網(wǎng)絡(luò)劃分實(shí)際上可以看成子圖劃分問題,即在滿足一定條件下將集合V分解成m個無交集的子集V1,V2,…,Vm,即

根據(jù)網(wǎng)絡(luò)劃分原則,子圖劃分就是在保證各網(wǎng)段可調(diào)度的基礎(chǔ)上,實(shí)現(xiàn)子圖間流量最小化和各子圖負(fù)載均衡。因此可以建立如下目標(biāo)優(yōu)化模型：

式中,μ1、μ2為權(quán)重因子,有 μ1+μ2=1。

約束條件：

式(2)的目標(biāo)函數(shù)由兩部分組成,第1部分表示子圖間流量,第2部分表示各子圖內(nèi)部負(fù)載的差異,它們分別與網(wǎng)段劃分原則(1)和原則(2)對應(yīng)。而式(3)表示子圖中節(jié)點(diǎn)消息傳輸可調(diào)度的條件,與原則(3)對應(yīng)。

上述優(yōu)化問題實(shí)際上屬于NP完全問題,采用遺傳算法(GA)求解是較好的選擇。本文引入?yún)?shù)自適應(yīng)策略來擴(kuò)大搜索空間,引入小生境策略創(chuàng)造小生境進(jìn)化環(huán)境,維持群體多樣性,建立了小生境自適應(yīng)遺傳算法(niched adapative genetic algorithm,NAGA)[11-12]。算法步驟如下：

(1)編碼方法。本文采用符號編碼方式。假設(shè)網(wǎng)絡(luò)中共有n個網(wǎng)絡(luò)節(jié)點(diǎn),劃分的子圖數(shù)為m個,則編碼長度為n的編碼串x=(λ1,λ2,…,λn)表示問題的一個解,其中λi=q表示第i個節(jié)點(diǎn)分配至第q個子圖中。

(2)適應(yīng)度函數(shù)。本文采用由解空間中某一點(diǎn)的目標(biāo)函數(shù)F(x)到搜索空間相應(yīng)個體適應(yīng)度函數(shù)值轉(zhuǎn)換的方法。即適應(yīng)度函數(shù)為

(3)遺傳算子。為了簡化操作過程,本文采用比例選擇算子,對于交叉和變異操作分別采用單點(diǎn)交叉操作和簡單對換變異操作。

(4)染色體有效性驗(yàn)證。為保證進(jìn)化中染色體滿足式(3)的約束條件,在交叉和變異操作后必須對染色體進(jìn)行有效性驗(yàn)證。通過驗(yàn)證的個體為合法染色體;反之為非法染色體,需重新進(jìn)行相關(guān)遺傳操作。

(5)控制參數(shù)的動態(tài)調(diào)整。采用自適應(yīng)策略來動態(tài)調(diào)整交叉概率Pc和變異概率Pm。設(shè)偏差δ分別為某一代種群中最大個體適應(yīng)度和個體平均適應(yīng)度值。當(dāng)δ較小時,種群趨向早熟,應(yīng)該增大 Pc、Pm;而當(dāng) δ較大時,種群早熟不顯著,為提高搜索速度可以減小

(6)小生境計算。為維護(hù)群體多樣性,使得最優(yōu)個體在約束空間中分散開來,需要計算個體間的海明距離[11];在該距離內(nèi),適應(yīng)度小的個體降低適應(yīng)度,增加被淘汰的機(jī)率。

(7)終止條件。當(dāng)前代數(shù)達(dá)到設(shè)定最大代數(shù)或個體適應(yīng)度連續(xù)若干次未發(fā)生增長時終止算法。

4 設(shè)計方法的應(yīng)用

國內(nèi)某自主品牌汽車的一款車型配置包括發(fā)動機(jī)ECU、自動變速箱ECU、汽車空調(diào)ECU、安全氣囊ECU、組合儀表ECU、車身ECU和電動助力等多個電子系統(tǒng)。

設(shè)其網(wǎng)絡(luò)中ECU數(shù)目為20個,擬劃分為3個網(wǎng)段。汽車網(wǎng)絡(luò)使用CAN總線,通信協(xié)議采用Bosch CAN2.0B,數(shù)據(jù)幀采用標(biāo)準(zhǔn)CAN數(shù)據(jù)幀,CAN網(wǎng)絡(luò)帶寬為125kbit/s,節(jié)點(diǎn)消息的相關(guān)參數(shù)如表1所示。如果節(jié)點(diǎn)間通信量用單位時間內(nèi)各節(jié)點(diǎn)發(fā)送的消息數(shù)量來表示,則節(jié)點(diǎn)通信矩陣為

表1 各節(jié)點(diǎn)消息的相關(guān)參數(shù)

為驗(yàn)證所提出的方法,分別采用普通遺傳算法和本文NAGA算法對該網(wǎng)絡(luò)劃分問題進(jìn)行了求解。設(shè)定群體規(guī)模均為100,GA的交叉概率為0.9,變異概率為0.05,NAGA的初始交叉概率和變異概率也分別為0.9和0.05。

求解過程中個體適應(yīng)度和目標(biāo)函數(shù)變化如圖3和圖4所示。從圖3和圖4看出：GA在進(jìn)化到50代時開始收斂,最大的個體適應(yīng)度值為0.032 143,目標(biāo)函數(shù)最小值為30.20;NAGA在進(jìn)化到85代時開始收斂,最大的個體適應(yīng)度值為0.035 651,目標(biāo)函數(shù)最小值為 27.05。同時NAGA所獲得最優(yōu)個體的數(shù)目也遠(yuǎn)多于GA。這說明小生境策略和參數(shù)自適應(yīng)策略的引入,擴(kuò)大了NAGA的搜索空間,避免了早熟現(xiàn)象,所獲得解的質(zhì)量要優(yōu)于GA獲得結(jié)果。

選取NAGA優(yōu)化過程中10個最優(yōu)個體,按照目標(biāo)函數(shù)從大到小順序排列得到的結(jié)果如表2所示 。 如果網(wǎng)關(guān)內(nèi)各 VNS 的規(guī)模 ?u1 、?u2 、?u3 均等于0.25,通過計算可知,所有染色體均能滿足式(3)。這說明所獲得的網(wǎng)段劃分方案能夠確保消息傳輸?shù)木W(wǎng)絡(luò)可調(diào)度要求。

圖3 適應(yīng)度函數(shù)f的優(yōu)化過程

圖4 目標(biāo)函數(shù)F的優(yōu)化過程

為得到最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu),需進(jìn)一步分析該10個方案。根據(jù)網(wǎng)段劃分原則(1),即盡量減小子網(wǎng)間的通信量,顯然方案 5、方案 7、方案 8、方案 9和方案10符合要求?？紤]到劃分原則(2),即保持各子網(wǎng)負(fù)載均衡,方案5、方案8和方案10是更可取的方案。對比這3個方案,由于方案10的目標(biāo)函數(shù)值最小,故方案10為最佳方案。即將20個節(jié)點(diǎn)按照以下方式劃分到3個網(wǎng)段中(括號中數(shù)字為各節(jié)點(diǎn)的節(jié)點(diǎn)號)：網(wǎng)段1：(9,10,11,12,15,20),網(wǎng)段 2：(1,2,3,7,8,13,18),網(wǎng)段 3：(4,5,6,14,16,17,19)。

表2 NAGA求解結(jié)果分析

4 結(jié)語

汽車網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計問題本質(zhì)上屬于多目標(biāo)優(yōu)化問題,在實(shí)際設(shè)計中需要考慮多方面的約束。其中,網(wǎng)絡(luò)負(fù)載率和傳輸實(shí)時性是兩個需要重點(diǎn)考慮的因素,它們直接關(guān)系到消息傳輸?shù)陌踩院涂煽啃?。本文以滿足消息可調(diào)度性和降低網(wǎng)段間通信量為出發(fā)點(diǎn),采用圖分割模型來描述網(wǎng)絡(luò)劃分問題,建立了汽車網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計方法。這種方法降低了網(wǎng)絡(luò)結(jié)構(gòu)分析與設(shè)計的難度,為建立多目標(biāo)約束下的汽車網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計方法進(jìn)行了有益的探索和嘗試。

[1] Li Renjun,Liu Chu.Design for Automotive CAN Bus Monitoring System[C]//IEEE Vehicle Power and Propulsion Conference.Harbin：IEEE,2008：1-5.

[2] 胡建軍,趙玉省,秦大同.基于CAN通信的混合動力系統(tǒng)硬件在環(huán)仿真實(shí)驗(yàn)[J].中國機(jī)械工程,2008,19(3)：300-304.

[3] Luo Feng,Chen Zhiqi.Research on Flexray Communication System[C]//IEEE Vehicle Power and Propulsion Conference.Harbin：IEEE,2008：4547-4550.

[4] Navet N,Song Y.Trends in Automotive Communication Systems[J].Proceedings of the IEEE,2005,93(6)：1204-1223.

[5] 曲鳳麗.汽車網(wǎng)絡(luò)研究及CAN總線網(wǎng)絡(luò)拓?fù)涞膬?yōu)化[D].杭州：浙江大學(xué),2008.

[6] 李稚博,張俊智,盧青春.混合動力電動汽車車上CAN網(wǎng)絡(luò)設(shè)計實(shí)時性分析[J].汽車工程,2005,27(1)：16-19.

[7] 岳東,彭晨,Qinglong Han.網(wǎng)絡(luò)控制系統(tǒng)分析與綜合[M].北京：科學(xué)出版社,2007.

[8] Liu J W S.Real-time Systems[M].Upper Saddle River,New Jersey：Prentice Hall,2003.

[9] Deng Z,Liu J W S.A Scheme for Scheduling Hard Real-time Applications in Open System Environment[C]//Euromicro Workshop on Real-time Systems.Toledo,1997：191-199.

[10] 陳國龍.基于遺傳算法的計算機(jī)通信網(wǎng)的拓?fù)鋬?yōu)化設(shè)計[J].計算機(jī)科學(xué),2002,29(11)：141-143.

[11] Han Jianghong,Wang Yuefei,Hou Zhengfeng,et al.An Approach of Industrial Ethernet Network System Design with Hybrid Niche Genetic Algorithm[C]//World Congress on Intelligent Control and Automation.Dalian：IEEE,2006：3699-3703.

[12] 于蘭峰,王金諾.基于遺傳算法和神經(jīng)網(wǎng)絡(luò)的塔機(jī)結(jié)構(gòu)動態(tài)優(yōu)化設(shè)計[J].中國機(jī)械工程,2008,19(1)：61-63.