基于實時調度與圖分割的汽車網絡結構設計研究

王躍飛 韓江洪 張建軍 彭 浩

合肥工業大學,合肥,230009

0 引言

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

汽車中與安全密切相關的ECU(如剎車防抱死系統等)對消息傳輸時間有著嚴格要求,網絡結構設計應該考慮這些時間約束。但目前已有的設計方法主要以降低總線及網關負載為目標,而對網絡傳輸的實時性考慮較少。文獻[5]提出了兩個網段下CAN總線拓撲設計的多目標優化方法,但沒有考慮多網段劃分和消息傳輸實時性要求。文獻[6]將單調速率算法應用于混合動力汽車CAN網絡的實時性分析,給出了通過調整數據優先級來改善網絡實時性的方法,但該方法只適用于單一網段的網絡設計。

針對上述方法不足,本文以滿足消息傳輸的可調度性和降低網關負載量為出發點,利用圖分割理論和遺傳算法建立了汽車網絡結構設計方法。該方法可應用在CAN網絡及其他汽車網絡設計中,具有一定適應性。

1 汽車網絡中的實時調度

多網段結構汽車網絡由網關和各個網段所組成,如圖1所示。同一網段內節點通過網絡直接通信,不同網段中的節點通過網關進行交互。為保證消息傳輸的實時性,需要采用一定的網絡調度方法。該類調度方法一般是指應用層調度,與底層網絡協議(CAN、LIN)無關,具有較強靈活性和適應性[7]。

圖1 多網段結構汽車網絡

圖1 所示網絡中消息可以分為兩類：網段間消息和網段內部消息。其中,網段間消息被節點發送后直接進入到網關內部緩沖隊列。設在網關內部針對每個子網段都設置一個虛擬網絡服務器(virtual network server,VNS),負責內部緩沖隊列中消息的發送。每個VNS都是一個總帶寬服務器(total bandwidth server),運行機制如圖2所示[8]。在網段內部,各個節點中的消息與VNS一起采用非搶占最早時限優先(earliest deadline first,EDF)算法調度。

圖2 VNS的預算補充和時限設置

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

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

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

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

因網段i為任意網段,故已知條件成立時,網絡中所有消息都是可調度的。

證畢。

2 網段劃分的圖分割模型

在汽車網絡結構設計時,將不同的節點放入不同的網段,對網絡負載量和消息傳輸實時性有著直接的影響。因此,在網段劃分時需要綜合考慮網絡負載量和消息傳輸實時性兩方面的約束,具體可按以下原則進行劃分：

(1)將相互間通信量較大的節點盡量分配到同一網段中,以降低不同網段間消息傳輸的轉發時間,減輕網關負擔。

(2)對網段內部節點通信量進行限制,以保持各網段負載均衡,避免懸殊過大。

(3)保證網絡中消息的可調度性,確保在其時限內完成傳送。

設汽車網絡中具有n個節點,每個節點周期性地向總線發送數據。對于多網段結構的汽車網絡可以用圖分割模型來描述[10-11]。定義無向圖：

G={V,E,W}

式中,V為汽車網絡節點集合,V={v1,v2,…,vn};E為節點間的相互通信關系,E={e1,e2,…,ek};W為G邊上的權值集合,W={wij};wij為節點vi與節點vj之間的通信量,令 wii=0。

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

根據網絡劃分原則,子圖劃分就是在保證各網段可調度的基礎上,實現子圖間流量最小化和各子圖負載均衡。因此可以建立如下目標優化模型：

式中,μ1、μ2為權重因子,有 μ1+μ2=1。

約束條件：

式(2)的目標函數由兩部分組成,第1部分表示子圖間流量,第2部分表示各子圖內部負載的差異,它們分別與網段劃分原則(1)和原則(2)對應。而式(3)表示子圖中節點消息傳輸可調度的條件,與原則(3)對應。

上述優化問題實際上屬于NP完全問題,采用遺傳算法(GA)求解是較好的選擇。本文引入參數自適應策略來擴大搜索空間,引入小生境策略創造小生境進化環境,維持群體多樣性,建立了小生境自適應遺傳算法(niched adapative genetic algorithm,NAGA)[11-12]。算法步驟如下：

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

(2)適應度函數。本文采用由解空間中某一點的目標函數F(x)到搜索空間相應個體適應度函數值轉換的方法。即適應度函數為

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

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

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

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

(7)終止條件。當前代數達到設定最大代數或個體適應度連續若干次未發生增長時終止算法。

4 設計方法的應用

國內某自主品牌汽車的一款車型配置包括發動機ECU、自動變速箱ECU、汽車空調ECU、安全氣囊ECU、組合儀表ECU、車身ECU和電動助力等多個電子系統。

設其網絡中ECU數目為20個,擬劃分為3個網段。汽車網絡使用CAN總線,通信協議采用Bosch CAN2.0B,數據幀采用標準CAN數據幀,CAN網絡帶寬為125kbit/s,節點消息的相關參數如表1所示。如果節點間通信量用單位時間內各節點發送的消息數量來表示,則節點通信矩陣為

表1 各節點消息的相關參數

為驗證所提出的方法,分別采用普通遺傳算法和本文NAGA算法對該網絡劃分問題進行了求解。設定群體規模均為100,GA的交叉概率為0.9,變異概率為0.05,NAGA的初始交叉概率和變異概率也分別為0.9和0.05。

求解過程中個體適應度和目標函數變化如圖3和圖4所示。從圖3和圖4看出：GA在進化到50代時開始收斂,最大的個體適應度值為0.032 143,目標函數最小值為30.20;NAGA在進化到85代時開始收斂,最大的個體適應度值為0.035 651,目標函數最小值為 27.05。同時NAGA所獲得最優個體的數目也遠多于GA。這說明小生境策略和參數自適應策略的引入,擴大了NAGA的搜索空間,避免了早熟現象,所獲得解的質量要優于GA獲得結果。

選取NAGA優化過程中10個最優個體,按照目標函數從大到小順序排列得到的結果如表2所示 。 如果網關內各 VNS 的規模 ?u1 、?u2 、?u3 均等于0.25,通過計算可知,所有染色體均能滿足式(3)。這說明所獲得的網段劃分方案能夠確保消息傳輸的網絡可調度要求。

圖3 適應度函數f的優化過程

圖4 目標函數F的優化過程

為得到最優網絡結構,需進一步分析該10個方案。根據網段劃分原則(1),即盡量減小子網間的通信量,顯然方案 5、方案 7、方案 8、方案 9和方案10符合要求。考慮到劃分原則(2),即保持各子網負載均衡,方案5、方案8和方案10是更可取的方案。對比這3個方案,由于方案10的目標函數值最小,故方案10為最佳方案。即將20個節點按照以下方式劃分到3個網段中(括號中數字為各節點的節點號)：網段1：(9,10,11,12,15,20),網段 2：(1,2,3,7,8,13,18),網段 3：(4,5,6,14,16,17,19)。

表2 NAGA求解結果分析

4 結語

汽車網絡結構設計問題本質上屬于多目標優化問題,在實際設計中需要考慮多方面的約束。其中,網絡負載率和傳輸實時性是兩個需要重點考慮的因素,它們直接關系到消息傳輸的安全性和可靠性。本文以滿足消息可調度性和降低網段間通信量為出發點,采用圖分割模型來描述網絡劃分問題,建立了汽車網絡結構優化設計方法。這種方法降低了網絡結構分析與設計的難度,為建立多目標約束下的汽車網絡結構設計方法進行了有益的探索和嘗試。

[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通信的混合動力系統硬件在環仿真實驗[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] 曲鳳麗.汽車網絡研究及CAN總線網絡拓撲的優化[D].杭州：浙江大學,2008.

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

[7] 岳東,彭晨,Qinglong Han.網絡控制系統分析與綜合[M].北京：科學出版社,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].計算機科學,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].中國機械工程,2008,19(1)：61-63.