面向時(shí)間敏感網(wǎng)絡(luò)的車(chē)載以太網(wǎng)網(wǎng)絡(luò)架構(gòu)多目標(biāo)優(yōu)化*

鄒 淵，孫文景，張旭東，溫 雅，曹萬(wàn)科，張兆龍

（1.北京理工大學(xué)機(jī)械與車(chē)輛學(xué)院，北京 100081；2.北京理工大學(xué)，電動(dòng)車(chē)輛國(guó)家工程研究中心，北京 100081；3.北京新能源汽車(chē)股份有限公司，北京 100176）

前言

隨著車(chē)輛向智能化、網(wǎng)聯(lián)化發(fā)展，車(chē)輛功能變得更加復(fù)雜，控制器之間需要更大的通信帶寬來(lái)傳輸越來(lái)越復(fù)雜的信息，軟件定義、數(shù)據(jù)驅(qū)動(dòng)汽車(chē)推動(dòng)了新型電子電氣架構(gòu)的發(fā)展［1］。新型電子電氣架構(gòu)逐步從基于域控制器的電子電氣架構(gòu)（domain based architectures）演化到基于區(qū)域-功能域控制器架構(gòu)（zone-domain based architectures）［2］。

區(qū)域-功能域架構(gòu)的基本思想將功能處理集中在車(chē)輛的單個(gè)或多個(gè)域控制器中，如圖1 所示，該架構(gòu)將車(chē)輛在幾何上分成了多個(gè)區(qū)域，每個(gè)區(qū)域配備一個(gè)區(qū)域控制器（zone control unit，ZCU）負(fù)責(zé)對(duì)該區(qū)域內(nèi)的傳感器和執(zhí)行器進(jìn)行信息采集和控制，但是ZCU 并不進(jìn)行復(fù)雜功能處理而是將數(shù)據(jù)上傳到相應(yīng)的功能域控制器（domain control unit，DCU）中，DCU和ZCU 之間通過(guò)高速通信網(wǎng)絡(luò)互聯(lián)。為了提高車(chē)輛處理復(fù)雜功能能力，區(qū)域-功能域架構(gòu)將一種典型復(fù)雜功能的處理集中到一個(gè)DCU 中，并在該DCU 中進(jìn)行相應(yīng)軟件組件的聚類(lèi)，目前被業(yè)界廣泛認(rèn)可的功能域包括：自動(dòng)駕駛域控制器（MDC）負(fù)責(zé)進(jìn)行高級(jí)別自動(dòng)駕駛、座艙域控制器（CDC）負(fù)責(zé)進(jìn)行顯示和娛樂(lè)系統(tǒng)，以及車(chē)控域控制器（VDC）負(fù)責(zé)進(jìn)行車(chē)輛的底盤(pán)和動(dòng)力控制［3］。區(qū)域-功能域架構(gòu)功能升級(jí)僅需要在ZCU 中增加接口或在DCU 中增加軟件組件即可完成，相比于傳統(tǒng)的分布式架構(gòu)，有效提高了架構(gòu)的可擴(kuò)展性。隨著功能復(fù)雜性的增加，ZCU和DCU 的大規(guī)模數(shù)據(jù)交互需要架構(gòu)具有更強(qiáng)的通信性能，一個(gè)既能保證傳輸?shù)脱訒r(shí)同時(shí)又能實(shí)現(xiàn)傳輸?shù)拇_定性、安全性的通信網(wǎng)絡(luò)成為了架構(gòu)實(shí)施的基礎(chǔ)［4］。引入時(shí)間敏感網(wǎng)絡(luò)（time sensitive network，TSN）的以太網(wǎng)在目前被認(rèn)為是最優(yōu)潛力的解決方案［5］。TSN 定義了一個(gè)IEEE 標(biāo)準(zhǔn)化協(xié)議組，是一種確保以太網(wǎng)流量實(shí)時(shí)傳輸?shù)臋C(jī)制。其主要特點(diǎn)是能夠滿(mǎn)足多種信息流的需求，如低延遲、低抖動(dòng)和高可靠性等［6］。

圖1 區(qū)域-控制域架構(gòu)

基于IEEE 802.1Qbv 協(xié)議的流量調(diào)度機(jī)制是TSN 實(shí)現(xiàn)低延時(shí)的核心機(jī)制［7］。該協(xié)議定義了一種時(shí)間感知整形器（TAS），如圖2 所示。TAS 為端口中的每個(gè)隊(duì)列設(shè)置一個(gè)“門(mén)”進(jìn)行控制，只用門(mén)打開(kāi)的時(shí)候信息才能傳輸，否則必須排隊(duì)等待。通過(guò)調(diào)度算法確定所有數(shù)據(jù)幀的傳輸順序和傳輸時(shí)間，生成門(mén)控制列表（GCL）是TAS 實(shí)現(xiàn)TSN 確定性和低延時(shí)的關(guān)鍵［8］。流量調(diào)度問(wèn)題是一個(gè)典型的NP-Hard 問(wèn)題［9］，在可接受時(shí)間內(nèi)獲得可行的調(diào)度方案是評(píng)估架構(gòu)合理性的基礎(chǔ)。程希文等［10］提出了一種禁忌搜索算法，在無(wú)等待調(diào)度模型下優(yōu)化流量調(diào)度的最大完成時(shí)間。Wang 等［11］提出了一種蟻群算法能夠較好地調(diào)度TSN中的時(shí)間觸發(fā)流，在收斂速度、優(yōu)化能力和跳出局部最優(yōu)方面具有優(yōu)勢(shì)。但是以上研究并未考慮車(chē)載網(wǎng)絡(luò)的特殊性，并未在車(chē)內(nèi)網(wǎng)絡(luò)環(huán)境下進(jìn)行驗(yàn)證。Kim 等［12］提出了一種基于小規(guī)模車(chē)內(nèi)網(wǎng)的啟發(fā)式車(chē)載TSN 網(wǎng)絡(luò)調(diào)度策略，仿真證明了該算法相比于嚴(yán)格按照優(yōu)先級(jí)進(jìn)行調(diào)度的算法能夠有效降低延時(shí)。Patti 等［13］提出了一種基于截止時(shí)間的TSN 在線調(diào)度策略并構(gòu)建了基于域控制器的現(xiàn)實(shí)車(chē)輛環(huán)境進(jìn)行仿真。然而以上研究主要通過(guò)改進(jìn)求解策略以提高調(diào)度效果減少延時(shí)，而忽略了網(wǎng)絡(luò)架構(gòu)本身對(duì)延時(shí)的影響，進(jìn)一步降低延時(shí)需要考慮架構(gòu)優(yōu)化設(shè)計(jì)。

圖2 時(shí)間感知整形器

車(chē)載網(wǎng)絡(luò)中眾多傳感器、執(zhí)行器和控制器的連接關(guān)系構(gòu)成了車(chē)輛網(wǎng)絡(luò)架構(gòu)。網(wǎng)絡(luò)架構(gòu)對(duì)成本、網(wǎng)絡(luò)負(fù)載分布和網(wǎng)絡(luò)延時(shí)有著直接影響。目前針對(duì)電子電氣架構(gòu)的網(wǎng)絡(luò)架構(gòu)已有許多研究。關(guān)志偉等［14-15］以線束成本最低、線束質(zhì)量最小和線路負(fù)載最小作為優(yōu)化目標(biāo)，將CAN、以太網(wǎng)、LIN 和LVDS 的總線長(zhǎng)度作為變量，使用NSGA-II 算法針對(duì)傳統(tǒng)電子電氣架構(gòu)進(jìn)行了多目標(biāo)優(yōu)化。魏翼鷹等［16］對(duì)優(yōu)化目標(biāo)進(jìn)行了擴(kuò)展，以擴(kuò)展率、安全性和設(shè)計(jì)成本為優(yōu)化目標(biāo)使用NSGA-III 進(jìn)行多目標(biāo)參數(shù)優(yōu)化。Klee等［17］在優(yōu)化架構(gòu)的通信開(kāi)銷(xiāo)的同時(shí)考慮了新架構(gòu)的接受度，并在實(shí)際案例研究中進(jìn)行了測(cè)試，結(jié)果表明只需對(duì)系統(tǒng)進(jìn)行微小的更改即可實(shí)現(xiàn)高度改進(jìn)。Huang 等［18］將無(wú)線通信引入車(chē)內(nèi)網(wǎng)絡(luò)來(lái)取代某些設(shè)備之間的布線電纜，在考慮傳輸延遲的同時(shí)最小化布線質(zhì)量和無(wú)線發(fā)射功率。然而以上工作都沒(méi)有將TSN 引入到架構(gòu)優(yōu)化設(shè)計(jì)中。與基于CAN、FlexRay和傳統(tǒng)以太網(wǎng)的架構(gòu)不同，面向TSN的區(qū)域-功能域架構(gòu)引入了新的優(yōu)化問(wèn)題。首先TSN的流量調(diào)度機(jī)制讓信息流的端到端延時(shí)成為優(yōu)化的重點(diǎn)［19］，快速求解車(chē)載網(wǎng)絡(luò)的流量調(diào)度，同時(shí)根據(jù)網(wǎng)絡(luò)架構(gòu)進(jìn)一步優(yōu)化延時(shí)是成為車(chē)載TSN網(wǎng)絡(luò)架構(gòu)設(shè)計(jì)的研究重點(diǎn)。其次區(qū)域-功能域架構(gòu)的環(huán)網(wǎng)拓?fù)涫沟面溌坟?fù)載設(shè)計(jì)上從分布式架構(gòu)的總線負(fù)載設(shè)計(jì)轉(zhuǎn)變?yōu)楣歉删W(wǎng)絡(luò)上的負(fù)載分布的設(shè)計(jì)。最后車(chē)載傳感器和執(zhí)行器的分布位置與功能具有很強(qiáng)的相關(guān)性，單純地按照空間距離將傳感器與ZCU 就近連接不一定能夠獲得最好的傳輸效果和成本，因此確定合理的連接關(guān)系和switch 端口數(shù)也是電子電氣架構(gòu)優(yōu)化設(shè)計(jì)的關(guān)鍵。

基于以上問(wèn)題，本文中提出了面向TSN的區(qū)域-功能域架構(gòu)的以太網(wǎng)網(wǎng)絡(luò)架構(gòu)多目標(biāo)優(yōu)化設(shè)計(jì)框架。首先，抽象了車(chē)輛架構(gòu)模型和信息流模型，基于該模型構(gòu)建了基于ZCU 的switch 端口數(shù)均勻、骨干網(wǎng)負(fù)載均衡和信息流端到端延時(shí)最低的多目標(biāo)優(yōu)化數(shù)學(xué)模型。其次，為了有效評(píng)估信息流延時(shí)，將TSN流量調(diào)度問(wèn)題抽象為周期性車(chē)間調(diào)度問(wèn)題（JSP），提出適用于流量調(diào)度的MPGA 算法進(jìn)行求解，該算法極大地提高了求解速度和調(diào)度效果。然后，基于改進(jìn)NSGA-II 算法求解網(wǎng)絡(luò)架構(gòu)多目標(biāo)優(yōu)化，為提高算法的求解效率，對(duì)NSGA-II 的交叉變異概率進(jìn)行基于擁擠程度和迭代次數(shù)的自適應(yīng)改進(jìn)。最后對(duì)試驗(yàn)結(jié)果進(jìn)行分析，厘清了端口數(shù)、負(fù)載占用和延時(shí)對(duì)架構(gòu)設(shè)計(jì)的影響，并提出了一種網(wǎng)絡(luò)架構(gòu)設(shè)計(jì)思路。

1 車(chē)載以太網(wǎng)網(wǎng)絡(luò)架構(gòu)數(shù)學(xué)建模

1.1 車(chē)載以太網(wǎng)網(wǎng)絡(luò)拓?fù)浣?/h3>

隨著高級(jí)別自動(dòng)駕駛的發(fā)展，負(fù)責(zé)環(huán)境感知的傳感器越來(lái)越多，傳輸?shù)臄?shù)據(jù)量也越來(lái)越大。本文中傳感器分布參考北汽集團(tuán)正在研發(fā)的一款A(yù)RCFOX車(chē)型，接入以太網(wǎng)的傳感器有3個(gè)激光雷達(dá)（Lidar）、6 個(gè)毫米波雷達(dá)（Radar）和11 個(gè)攝像頭（Camera）。定義4 個(gè)區(qū)域控制器（ZCU）均勻地分布在車(chē)身4 個(gè)區(qū)域，組成一個(gè)環(huán)形拓?fù)?。定義3 個(gè)DCU 分別是VDC、MDC和CDC。圖3是傳感器、ZCU和DCU分布示意圖。

圖3 傳感器與域控制器分布示意圖

本文中將架構(gòu)拓?fù)涑橄鬄橐粋€(gè)有向圖［20］，如式（1）所示：

式中：V表示N個(gè)節(jié)點(diǎn)的集合；E表示物理鏈路的集合。定義A∈RN×N為鄰接矩陣，該矩陣由0 和1 組成，Aij=1 表示i，j兩個(gè)節(jié)點(diǎn)可以連接，Aij=0 表示i，j兩個(gè)節(jié)點(diǎn)不可以連接。為每條邊eij賦予權(quán)重uij代表鏈路的帶寬。cij表示在一個(gè)超周期內(nèi)負(fù)載占用的帶寬。一種基于專(zhuān)家經(jīng)驗(yàn)設(shè)計(jì)的網(wǎng)絡(luò)拓?fù)淠Ｐ蛨D如圖4所示。

圖4 架構(gòu)拓?fù)淠Ｐ蛨D

將ZCU 抽象為兩個(gè)節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)代表具備收發(fā)功能的控制終端節(jié)點(diǎn)，另一個(gè)節(jié)點(diǎn)代表switch 功能，負(fù)責(zé)連接其余節(jié)點(diǎn)完成信號(hào)交換，這兩個(gè)節(jié)點(diǎn)直接相連。將DCU 抽象為具有收發(fā)功能的終端節(jié)點(diǎn)，將傳感器抽象為發(fā)送感知數(shù)據(jù)的終端節(jié)點(diǎn)。DCU的節(jié)點(diǎn)和傳感器節(jié)點(diǎn)均可以與鄰近矩陣中Aij=1 的一個(gè)switch節(jié)點(diǎn)相連。

1.2 車(chē)載以太網(wǎng)網(wǎng)絡(luò)信息流建模

信息流是周期性從一個(gè)節(jié)點(diǎn)向另一個(gè)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)，圖4 中展示了3 條流的示意。如式（2）所示使用六維元組來(lái)表示信息流［21］：

式 中：ns，k表示源節(jié)點(diǎn)；nd，k表示終端節(jié)點(diǎn)，ns，k，nd，k∈V；ck表示fk需要占用的帶寬大小；pk表示發(fā)送周期；Dk表示截至期限；τk表示優(yōu)先級(jí)。

對(duì)于fk的路由選擇，通過(guò)兩個(gè)單一節(jié)點(diǎn)的最短路徑法獲得，如式（3）所示。

式中：P表示路由路徑；G表示網(wǎng)絡(luò)拓?fù)溆邢驁D。

信息流端到端延時(shí)是信息流從源節(jié)點(diǎn)發(fā)送到終端節(jié)點(diǎn)接收的時(shí)間差，以太網(wǎng)延時(shí)主要由4 部分組成：傳輸延時(shí)、排隊(duì)延時(shí)、傳播延時(shí)和處理延時(shí)［20］。傳輸延時(shí)主要是發(fā)送一個(gè)信息流所需要的時(shí)間，與帶寬和信息流大小有關(guān)；當(dāng)多個(gè)信息流在同一時(shí)間需要通過(guò)同一個(gè)端口發(fā)送時(shí)會(huì)產(chǎn)生排隊(duì)延時(shí)；處理延時(shí)主要取決于switch 的設(shè)計(jì)，是switch 的固有屬性；傳播延時(shí)主要取決于信號(hào)在線束中的傳輸速度和線束長(zhǎng)度。處理延時(shí)是固定值對(duì)優(yōu)化設(shè)計(jì)并沒(méi)有任何的影響，因此不做考慮。車(chē)內(nèi)網(wǎng)絡(luò)中線束長(zhǎng)度很短因此傳播延時(shí)也忽略不計(jì)，所以對(duì)延時(shí)的計(jì)算重點(diǎn)考慮傳輸延時(shí)和排隊(duì)延時(shí)。端到端延時(shí)如式（4）所示：

表1 中列出了網(wǎng)絡(luò)中各類(lèi)信息流參數(shù)。每個(gè)域控制器相對(duì)于其他域控制器都以10、20 和50 ms 周期發(fā)送控制信號(hào)、生命信號(hào)、狀態(tài)信號(hào)和非安全相關(guān)信號(hào)等，通過(guò)這種高頻率、大數(shù)據(jù)量的信息模擬車(chē)內(nèi)高負(fù)載網(wǎng)絡(luò)通信。為了區(qū)分信息的優(yōu)先級(jí)，將信息流分為以下3 類(lèi)：（1）安全相關(guān)控制信號(hào)流，此類(lèi)信號(hào)優(yōu)先級(jí)最高，要求延時(shí)極低；（2）傳感器信號(hào)流，此類(lèi)信號(hào)流也與安全相關(guān)，優(yōu)先級(jí)中等，要求延時(shí)盡可能低；（3）安全不相關(guān)信號(hào)流，此類(lèi)信號(hào)延時(shí)主要影響行駛的體驗(yàn)感，優(yōu)先級(jí)低。

表1 信息流參數(shù)

1.3 網(wǎng)絡(luò)架構(gòu)多目標(biāo)優(yōu)化問(wèn)題構(gòu)建

汽車(chē)電子電氣架構(gòu)優(yōu)化中設(shè)計(jì)變量和目標(biāo)函數(shù)眾多，往往在多個(gè)目標(biāo)函數(shù)之間存在相關(guān)性或者相互沖突，因此需要使用高效的多目標(biāo)優(yōu)化算法進(jìn)行求解。新一代網(wǎng)絡(luò)架構(gòu)以支持TSN的以太網(wǎng)作為骨干網(wǎng)絡(luò)，具有傳輸數(shù)據(jù)量大、傳輸?shù)脱訒r(shí)和傳輸確定性高等優(yōu)勢(shì)，因此針對(duì)通信性能選擇骨干網(wǎng)負(fù)載均衡和信息流端到端延時(shí)最低這兩個(gè)表征通信特性的參數(shù)進(jìn)行優(yōu)化。ZCU 的switch 端口數(shù)既直接影響網(wǎng)絡(luò)架構(gòu)的連接關(guān)系從而對(duì)通信性能產(chǎn)生影響也對(duì)架構(gòu)的可擴(kuò)展性和成本有著直接影響，因此選擇ZCU的switch 端口數(shù)作為另一個(gè)優(yōu)化目標(biāo)。在下文對(duì)3個(gè)優(yōu)化目標(biāo)的建模進(jìn)行詳細(xì)的說(shuō)明。

（1）端口模型

ZCU 端口數(shù)量是由switch 芯片決定的，關(guān)系到網(wǎng)絡(luò)架構(gòu)的成本，端口數(shù)越多，芯片價(jià)格越高。從整車(chē)設(shè)計(jì)的角度考慮，端口數(shù)過(guò)多往往會(huì)對(duì)ZCU 造成很高的通信負(fù)載，設(shè)計(jì)復(fù)雜度變高，一旦崩潰會(huì)危及車(chē)輛安全［3］。同時(shí)端口數(shù)均衡，有利于整車(chē)總體設(shè)計(jì)時(shí)switch 的統(tǒng)一選型，提高ZCU 的通用性和后續(xù)架構(gòu)升級(jí)的可擴(kuò)展性，有效避免資源浪費(fèi)，降低成本。但是考慮到總體設(shè)計(jì)，某些位置的傳感器可能確實(shí)多于其他位置，因此允許有一個(gè)switch 的端口數(shù)較多，其余switch 的端口數(shù)要盡可能的平均。為了保證環(huán)網(wǎng)架構(gòu)和每個(gè)ZCU 的有效性，保證每個(gè)ZCU 必須與至少一個(gè)傳感器或DCU 連接，將最小端口數(shù)約束為4。為了避免出現(xiàn)端口數(shù)極端分散的情況，提高求解效率，約束最多只能有兩個(gè)ZCU 可能出現(xiàn)連接1 個(gè)傳感器或DCU 的情況，將最大端口數(shù)約束為13。最終得到switch 端口數(shù)量的適應(yīng)度函數(shù)和約束如式（5）所示：

式 中：port_numberi表示第i個(gè)switch 的端口數(shù)；port_numberi′表示去掉最大端口數(shù)之后的第i個(gè)switch的端口數(shù)。

（2）負(fù)載模型

骨干網(wǎng)絡(luò)上的負(fù)載分布均衡可以有利于減少信息流之間的影響，提高架構(gòu)總體的安全性。骨干網(wǎng)負(fù)載分配的適應(yīng)度函數(shù)被定義為

（3）延時(shí)模型

在車(chē)載通信中希望信息流的端到端延時(shí)越低越好，延時(shí)適應(yīng)度的求解就是對(duì)流量調(diào)度問(wèn)題的求解，具體建模和求解過(guò)程在下一章詳細(xì)說(shuō)明。用式（7）表示端到端延時(shí)的適應(yīng)度函數(shù)。

根據(jù)以上推導(dǎo)，對(duì)于3 個(gè)目標(biāo)函數(shù)都取最小值，輸入變量為DCU和傳感器相對(duì)于4個(gè)ZCU的連接關(guān)系，連接關(guān)系必須遵從鄰接矩陣，因此確定多目標(biāo)優(yōu)化的約束函數(shù)及約束如式（8）所示：

式中α，β，γ為權(quán)重系數(shù)。

2 基于多種群遺傳算法求解TSN流量調(diào)度問(wèn)題

2.1 TSN流量調(diào)度問(wèn)題數(shù)學(xué)構(gòu)建

本文中對(duì)TSN 信息流的流量調(diào)度基于TAS，車(chē)載網(wǎng)絡(luò)一經(jīng)確定通常不會(huì)發(fā)生改變，基于TAS 的流量調(diào)度能夠確定每個(gè)信息流的每次傳輸?shù)膫鬏敃r(shí)間和延時(shí)，信息流實(shí)時(shí)性和確定性極高。傳統(tǒng)JSP 問(wèn)題不考慮周期問(wèn)題因此不能直接用于流量調(diào)度問(wèn)題的求解，本文在傳統(tǒng)JSP 模型基礎(chǔ)上添加周期性約束，將流量調(diào)度問(wèn)題抽象為周期性的JSP 模型，如圖5 所示。將信息流抽象為需要作業(yè)的工件，將每個(gè)發(fā)送端口抽象為機(jī)器，將信息流的路由過(guò)程抽象為工序。流量調(diào)度問(wèn)題需要滿(mǎn)足JSP 問(wèn)題的基本規(guī)則［22］：（1）每個(gè)switch 的端口同一時(shí)刻只能發(fā)送一幀數(shù)據(jù)，同一幀數(shù)據(jù)同一時(shí)刻只能在一個(gè)發(fā)送端口中；（2）信息流的發(fā)送過(guò)程一旦開(kāi)始不得中斷，數(shù)據(jù)流的抖動(dòng)為0。流量調(diào)度問(wèn)題也引入了一下新規(guī)則：（1）不同于JSP 問(wèn)題工件必須在上一步加工時(shí)間全部完成后才可以進(jìn)行下一步加工，流量調(diào)度問(wèn)題的信息路由下一跳在信息流的第一幀發(fā)送完成后就可以開(kāi)始；（2）周期性的信息首次發(fā)送的時(shí)間是自由的但是后續(xù)周期的發(fā)送時(shí)間需要滿(mǎn)足的約束如式（9）所示。

圖5 流量調(diào)度問(wèn)題抽象的JSP模型

式中：tk，n，1表示fk的第n個(gè)周期第一跳的發(fā)送開(kāi)始時(shí)間；tk，n，last表示fk的第n個(gè)周期最后一跳的發(fā)送開(kāi)始時(shí)間；tk，1，1表示fk首次發(fā)送時(shí)間；tlast_arrive表示超周期內(nèi)的最后一幀信息到達(dá)的時(shí)間；Hyper_Period代表信息流的超周期，是所有流發(fā)送周期的最小公倍數(shù)，一個(gè)超周期內(nèi)的最后一幀信息到達(dá)的時(shí)間必須小于超周期，這樣避免影響新周期在零時(shí)刻開(kāi)始。

流量調(diào)度問(wèn)題的約束函數(shù)為各優(yōu)先級(jí)的通信流的端到端延遲最小，如式（10）所示：

式中：ω1、ω2和ω3是3種信息流延時(shí)的權(quán)重系數(shù)；FH、FM、FL分別代表上述3 種優(yōu)先級(jí)的信息流的集合；dfk表示fk的端到端延時(shí)；D表示信息流的截止時(shí)間。

2.2 適用于流量調(diào)度的多種群遺傳算法求解

遺傳算法（GA）是一種模擬生物邏輯進(jìn)化的隨機(jī)搜索技術(shù)，具有很強(qiáng)的全局搜索能力［23］。但是種群的初始化、交叉算子Pc和變異算子Pm對(duì)于算法能否獲得全局最優(yōu)的影響極大［24］。為了擺脫對(duì)初始化和交叉變異概率的依賴(lài)，本文中提出適用于流量調(diào)度的多種群遺傳算法（MPGA），該算法突破單個(gè)種群的進(jìn)化框架，引入多個(gè)種群進(jìn)行優(yōu)化搜索的同時(shí)為不同種群賦予同的交叉變異概率，使算法兼顧全局搜索和局部搜索。各個(gè)種群之間通過(guò)移民算子實(shí)現(xiàn)協(xié)同優(yōu)化。

成千上萬(wàn)匹蒙古馬聚集在一起，呼嘯奔騰，那是一幅奔騰的美、力量的美交織在一起的奇異畫(huà)面。如今，經(jīng)過(guò)歷史的沉淀與實(shí)踐的熔鑄，“蒙古馬精神”已融入各族人民的血脈，成為各族群眾團(tuán)結(jié)奮斗、開(kāi)拓進(jìn)取的重要精神源泉與紐帶。隨著時(shí)代的發(fā)展，“蒙古馬精神”的內(nèi)在價(jià)值和重要性更加凸顯出來(lái)。弘揚(yáng)“蒙古馬精神”，已經(jīng)成為時(shí)代的需要。

MPGA 的總體架構(gòu)如圖6 所示。以NP個(gè)種群為例，這些種群收尾相連，每個(gè)種群都是單獨(dú)進(jìn)化的，但是在每次迭代后，將Pi+1的最差解替換為Pi的最優(yōu)解，對(duì)于PNp則是將最優(yōu)解傳遞給P1。通過(guò)最優(yōu)種群的遷移和各種種群獨(dú)立進(jìn)化，MPGA 能夠避免陷入局部最優(yōu)，提高優(yōu)化效果，加快了收斂速度。

圖6 MPGA總體框架

本文的編碼方式采用基于工序的編碼方式，每個(gè)染色體是所有信息流發(fā)送順序的一個(gè)排列，例如34321表示先傳輸流3的第1跳，接著傳輸流4的第1跳，再接著傳輸流3 的第2 跳，依此類(lèi)推。不同于傳統(tǒng)的JSP 問(wèn)題，流量調(diào)度問(wèn)題必須考慮周期問(wèn)題，在編碼時(shí)需要將超周期內(nèi)的信息流fi的所有傳輸都進(jìn)行考慮，在一個(gè)染色體中fi出現(xiàn)次數(shù)與自身周期有關(guān)，如式（11）所示：

式中：Ki是染色體中fi總的出現(xiàn)次數(shù)；ki是fi每次發(fā)送需要經(jīng)過(guò)的switch 端口數(shù)。在解碼過(guò)程中第n次出現(xiàn)的第i個(gè)信息流，通過(guò)n與ki相除的商和余數(shù)獲得發(fā)送周期和發(fā)送節(jié)點(diǎn)。根據(jù)發(fā)送周期、上一跳完成的時(shí)間和發(fā)送端口的占用情況確定本次發(fā)送的開(kāi)始時(shí)間。

選擇操作選用混合錦標(biāo)選擇和最佳個(gè)體保存兩種方式。交叉方式選擇基于工序編碼的交叉算子（POX），它能夠很好地繼承父代的優(yōu)良特征同時(shí)保證子代的可行性［25］。變異操作采用互換變異，隨機(jī)選擇一個(gè)基因然后將其插入到一個(gè)隨機(jī)的位置。由于大規(guī)模網(wǎng)絡(luò)的染色體長(zhǎng)度通常很長(zhǎng)，因此本文選擇每次變異的基因個(gè)數(shù)為染色體總長(zhǎng)度的2%。在迭代結(jié)束后，對(duì)所有種群的最優(yōu)解進(jìn)行比較，選擇適應(yīng)度最低染色體所代表的調(diào)度策略作為本次求解的最優(yōu)解。

3 網(wǎng)絡(luò)架構(gòu)多目標(biāo)優(yōu)化框架與求解

3.1 網(wǎng)絡(luò)架構(gòu)多目標(biāo)優(yōu)化框架構(gòu)建

本文中構(gòu)建了基于改進(jìn)NSGA-II算法求解的網(wǎng)絡(luò)架構(gòu)多目標(biāo)優(yōu)化框架，優(yōu)化框架如圖7 所示。優(yōu)化輸入的初值為傳感器、控制器的鄰接矩陣，對(duì)于鄰接矩陣定義以下連接原則：（1）傳感器與switch 的連接并不是以距離最近為連接依據(jù)而是兼顧周?chē)膕witch，位于車(chē)身的傳感器都與相鄰的兩個(gè)switch 存在連接的可能，而位于車(chē)內(nèi)的攝像頭等傳感器與4個(gè)switch 都存在連接的可能；（2）DCU 的位置是自由的，因此也與4個(gè)ZCU都存在連接的可能。

圖7 網(wǎng)絡(luò)架構(gòu)多目標(biāo)優(yōu)化框架

根據(jù)鄰接矩陣，首先通過(guò)NSGA-II 算法的編碼過(guò)程獲得可行的網(wǎng)絡(luò)架構(gòu)模型，生成初始種群。然后使用MPGA 算法求解每個(gè)架構(gòu)的TSN 流量調(diào)度，獲得各信息流延時(shí)。接著將MPGA 的求解結(jié)果用于計(jì)算NSGA-II 的延時(shí)適應(yīng)度。根據(jù)負(fù)載、端口和延時(shí)的適應(yīng)度對(duì)架構(gòu)進(jìn)行非支配排序選擇，通過(guò)改進(jìn)的自適應(yīng)交叉變異因子對(duì)種群進(jìn)行反復(fù)迭代。在NSGA-II收斂后輸出Pareto前沿解的網(wǎng)絡(luò)架構(gòu)。

3.2 基于改進(jìn)NSGA-II算法的多目標(biāo)優(yōu)化求解

NSGA-II 算法是一種基于Pareto 最優(yōu)解的多目標(biāo)優(yōu)化算法。傳統(tǒng)的NSGA-II算法的交叉變異通常是盲目的，這可能會(huì)破壞最優(yōu)解，同時(shí)使迭代結(jié)果陷入局部最優(yōu)［26］。因此本文中提出具有自適應(yīng)交叉變異的改進(jìn)NSGA-II 算法，加強(qiáng)算法的搜索能力和加快收斂速度。

本算法的編碼方式為染色體中第i個(gè)基因所代表的數(shù)值j代表節(jié)點(diǎn)i與節(jié)點(diǎn)j連接，其中i∈N，j∈Ns，i≠j且Aij=1。例如4321 的染色體表示傳感器1 與ZCU4 相連，傳感器2 與ZCU3 相連，依此類(lèi)推。在種群的初始化設(shè)計(jì)中考慮端口數(shù)的約束，保證所有染色體都滿(mǎn)足約束可以快速過(guò)濾到很多無(wú)效解，提高種群質(zhì)量，加快求解速率。采用快速非支配排序算法進(jìn)行排序，使用錦標(biāo)賽選擇算法，優(yōu)先選擇支配等級(jí)低的個(gè)體，當(dāng)支配等級(jí)相同時(shí)，選擇擁擠距離大的個(gè)體。

為了提高求解效果，加快收斂速度，將個(gè)體擁擠距離與該個(gè)體所在的支配等級(jí)的擁擠距離的平均值作對(duì)比，引入迭代因子I和擁擠因子D，實(shí)現(xiàn)交叉變異概率根據(jù)擁擠距離和進(jìn)化次數(shù)的自適應(yīng)調(diào)節(jié)。I和D分別如式（12）和式（13）所示：

式中：G表示總的迭代次數(shù)；t表示當(dāng)前代數(shù)；Dj（t）表示當(dāng)前解的擁擠距離。自適應(yīng)調(diào)節(jié)的基本理念是在進(jìn)化初期使用較大的交叉變異概率提高搜索能力，在進(jìn)化后期使概率趨向于平均值。對(duì)擁擠距離較小的個(gè)體，選擇較大的交叉和變異概率，提高搜索能力；對(duì)擁擠距離較大的個(gè)體，選用小的交叉和變異概率防止破壞該解。因此自適應(yīng)交叉和變異概率如式（14）和式（15）所示：

式中：Pc代表交叉概率；Pm代表變異概率。改進(jìn)NSGA-II 算法求解網(wǎng)絡(luò)架構(gòu)多目標(biāo)優(yōu)化的流程如圖8所示。

圖8 改進(jìn)NSGA-II求解網(wǎng)絡(luò)架構(gòu)多目標(biāo)優(yōu)化流程

4 仿真驗(yàn)證

因?yàn)榱髁空{(diào)度問(wèn)題輸出的延時(shí)是架構(gòu)多目標(biāo)參數(shù)優(yōu)化的基礎(chǔ)，所以在本章首先驗(yàn)證MPGA 求解的優(yōu)越性。選用的仿真場(chǎng)景為基于專(zhuān)家經(jīng)驗(yàn)設(shè)計(jì)的架構(gòu)拓?fù)洌鐖D9 所示。鏈路上的信息流如表1 所示。然后對(duì)網(wǎng)絡(luò)架構(gòu)多目標(biāo)優(yōu)化框架進(jìn)行驗(yàn)證，驗(yàn)證場(chǎng)景是圖 3 介紹的車(chē)輛。最后對(duì)Pareto 前沿解所代表的網(wǎng)絡(luò)架構(gòu)進(jìn)行了分析比較，提出了一種網(wǎng)絡(luò)架構(gòu)設(shè)計(jì)思路。

圖9 基于專(zhuān)家經(jīng)驗(yàn)設(shè)計(jì)的網(wǎng)絡(luò)架構(gòu)示意圖

4.1 基于MPGA求解TSN流量調(diào)度驗(yàn)證

（1）仿真參數(shù)

本部分選用的對(duì)比算法是已經(jīng)在其他流量調(diào)度求解研究中使用的禁忌搜索算法（TS）［10］、蟻群優(yōu)化算法（ACO）［11］和傳統(tǒng)遺傳算法（GA）［19］。本文中提出的MPGA 使用4個(gè)種群，每個(gè)種群數(shù)100，4個(gè)種群的交叉概率分別為（0.7，0.85，0.9，0.95），變異概率分別為（0.3，0.15，0.1，0.05）。

（2）仿真結(jié)果

MPGA 與對(duì)比算法的收斂結(jié)果對(duì)比如圖10 所示。從圖中可見(jiàn)，MPGA 在前20 回合適應(yīng)度下降速率明顯高于其他算法，是所有算法中收斂最快的。MPGA 收斂后的適應(yīng)度是所有算法中最低的，相比于GA提升了16%，調(diào)度效果最好。同時(shí)MPGA 的初始適應(yīng)度最高，初始種群質(zhì)量最差，但是結(jié)果最優(yōu)，這說(shuō)明相比于其他對(duì)比算法，MPGA 擺脫初始種群限制的能力更強(qiáng)。

圖10 MPGA與對(duì)比算法的收斂結(jié)果對(duì)比

MPGA 與對(duì)比算法的各類(lèi)信息流的端到端平均延時(shí)如圖11 所示?？傮w來(lái)看所有算法求解的優(yōu)先級(jí)最高的兩個(gè)控制信號(hào)延時(shí)都很低，遠(yuǎn)遠(yuǎn)小于其他信號(hào)。安全不相關(guān)的50 ms 信號(hào)延時(shí)高于周期和數(shù)據(jù)量都相同毫米波雷達(dá)和數(shù)據(jù)量更大的攝像頭信息流，說(shuō)明了調(diào)度策略能夠滿(mǎn)足優(yōu)先級(jí)要求。激光雷達(dá)的平均延時(shí)大于同優(yōu)先級(jí)的其他數(shù)據(jù)，甚至大于低優(yōu)先級(jí)信息的原因是：信息流一旦開(kāi)始傳輸，不允許被打斷，傳輸抖動(dòng)為0。激光雷達(dá)的數(shù)據(jù)量非常大，一旦優(yōu)先傳輸會(huì)增加其他數(shù)據(jù)流的傳輸延時(shí)。另外在確定信息流在某一跳的傳輸開(kāi)始時(shí)間時(shí)，會(huì)在滿(mǎn)足最小開(kāi)始時(shí)間且不影響已經(jīng)調(diào)度的流的前提下，將信息流插入到switch兩個(gè)信息流的發(fā)送間隔中，而激光雷達(dá)的傳輸時(shí)間過(guò)長(zhǎng)導(dǎo)致很難被插入，因此通常會(huì)被放置在該switch的已經(jīng)調(diào)度的最后一個(gè)流的結(jié)束，這也導(dǎo)致排隊(duì)延時(shí)增大。MPGA 求解的激光雷達(dá)的平均延時(shí)是發(fā)送周期的4%，但是由于文中的策略保證了零抖動(dòng)，所以認(rèn)為該現(xiàn)象是可以接受的。相比于對(duì)比策略，MPGA 在保證激光雷達(dá)延時(shí)明顯降低的同時(shí)，保證了其他信息流的延時(shí)，尤其是高優(yōu)先級(jí)控制信息流的延時(shí)是最低的，調(diào)度效果明顯提升。

圖11 MPGA與對(duì)比策略中信號(hào)流平均延時(shí)對(duì)比

以上結(jié)果得益于移民因子定期會(huì)將種群中的較差解移除，同時(shí)引入了別的種群的較優(yōu)解，使得每個(gè)種群在每次迭代中都有更大概率探索出更優(yōu)解。另外每個(gè)種群不同的交叉變異參數(shù)讓算法兼顧全局探索與局部探索，保證了種群的多樣性，解決了容易早熟、對(duì)初始化種群依賴(lài)性較強(qiáng)的問(wèn)題。

4.2 面向TSN的網(wǎng)絡(luò)架構(gòu)多目標(biāo)優(yōu)化驗(yàn)證

（1）仿真參數(shù)

Improved-NSAG-II 的最大交叉概率為0.95，最小交叉概率為0.75，最大變異概率為0.2，最小變異概率為0.1。作為對(duì)比算法的NSAG-II 的交叉變異概率是改進(jìn)算法的平均值分別為0.85 和0.15。兩種算法的種群數(shù)都設(shè)置為200。

（2）自適應(yīng)交叉變異有效性驗(yàn)證

Improved-NSAG-II 和NSGA-II 的負(fù)載適應(yīng)度與延時(shí)適應(yīng)度對(duì)比如圖12 和圖13 所示。兩個(gè)算法求解的兩個(gè)適應(yīng)度的最低值是相等的，但是改進(jìn)算法在兩個(gè)適應(yīng)度上獲得最低值的回合數(shù)均提升25%左右，充分說(shuō)明改進(jìn)的交叉變異概率能夠更合理地進(jìn)行全局和局部探索，使算法更快收斂到最優(yōu)點(diǎn)。

圖12 負(fù)載適應(yīng)度對(duì)比

圖13 延時(shí)適應(yīng)度對(duì)比

（3）Pareto前沿解對(duì)比分析

本部分首先根據(jù)仿真結(jié)果分析負(fù)載、端口和延時(shí)之間的聯(lián)系，然后對(duì)Pareto 前沿中的幾個(gè)典型拓?fù)溥M(jìn)行對(duì)比分析，最后總結(jié)了負(fù)載占用、端口數(shù)和延時(shí)對(duì)架構(gòu)設(shè)計(jì)的影響。

Improved-NSAG-II 的Pareto 前沿解分布如圖14～圖16 所示。從圖14 中可以看出Pareto 前沿解的端口適應(yīng)度與延時(shí)適應(yīng)度基本成反比。從圖15 中可以看出端口數(shù)適應(yīng)度越大，負(fù)載利用適應(yīng)度越小。延時(shí)適應(yīng)度越小代表各種信息流的總體延時(shí)越小，負(fù)載適應(yīng)度越小代表負(fù)載的分布更加均勻。端口數(shù)目的適應(yīng)度函數(shù)主要與最大端口數(shù)和剩余端口數(shù)的均方差有關(guān)，其中最大端口數(shù)主要影響了端口的適應(yīng)度函數(shù)的整數(shù)部分，端口適應(yīng)度函數(shù)越大，最大端口上連接的傳感器數(shù)量越多。這導(dǎo)致更多的傳感器與功能域控制器能夠直接連在同一個(gè)switch 上，信息路由的跳數(shù)少，降低了排隊(duì)延時(shí)。同時(shí)需要通過(guò)骨干網(wǎng)絡(luò)傳輸?shù)男畔⒘恳矔?huì)減少，這也更有利于骨干網(wǎng)絡(luò)的負(fù)載均勻分配。圖16 中延時(shí)適應(yīng)度較低的個(gè)體集中在負(fù)載利用適應(yīng)度較低的區(qū)域，這是因?yàn)榫鶆虻呢?fù)載分配能夠減小每條線路上的排隊(duì)延時(shí)。

圖14 延時(shí)與端口Pareto前沿圖

圖15 負(fù)載與端口Pareto前沿圖

圖16 延時(shí)與負(fù)載Pareto前沿圖

表2 中分別列出了負(fù)載最均衡、延時(shí)最低、端口數(shù)均衡的解，端口分配的數(shù)組中分別對(duì)應(yīng)4 個(gè)域控制器連接的傳感器數(shù)量，Pareto 端口均衡拓?fù)?-3都是僅有兩種不同的端口數(shù)，因此認(rèn)為它們具有相同的價(jià)值。

表2 Pareto前沿解拓?fù)鋵?duì)比

相比于上文基于專(zhuān)家經(jīng)驗(yàn)設(shè)計(jì)的拓?fù)?，通過(guò)Improved-NSAG-II 求解的拓?fù)湓谘訒r(shí)上都具有明顯的優(yōu)勢(shì)。延時(shí)最低拓?fù)浜拓?fù)載最均衡拓?fù)涠汲霈F(xiàn)在ZCU2 達(dá)到最大端口數(shù)約束時(shí)，但是它們端口分布過(guò)于分散。此外，負(fù)載適應(yīng)度降低雖然有助降低延時(shí)適應(yīng)度，但是負(fù)載適應(yīng)度低并不代表著延時(shí)適應(yīng)度一定低。這是因?yàn)闇p少路由距離可以有效減小排隊(duì)延時(shí)，因此算法會(huì)將無(wú)法直接連接在同一個(gè)域控制器上的兩個(gè)終端盡可能地連接在相鄰的區(qū)域控制器上，對(duì)于必須進(jìn)行多跳路由的信號(hào)則選擇數(shù)據(jù)量小的。這導(dǎo)致信息集中在連接兩個(gè)控制器之間的骨干網(wǎng)上，從而造成負(fù)載分配不均，最大負(fù)載變大。

圖17 對(duì)比了這6 個(gè)拓?fù)涞母黝?lèi)信息流的延時(shí)。延時(shí)最低拓?fù)涞母鱾€(gè)信息流的延時(shí)都是最低的，負(fù)載均衡拓?fù)浯沃?。隨著最大端口數(shù)的增大，端口均衡拓?fù)? 相比于拓?fù)? 和拓?fù)? 各個(gè)信息流的平均延時(shí)也明顯降低。不同于基于專(zhuān)家經(jīng)驗(yàn)設(shè)計(jì)拓?fù)涞难訒r(shí)，這5 個(gè)拓?fù)渲屑す饫走_(dá)的平均延時(shí)非常低，只有傳輸延時(shí)12 μs，這是因?yàn)檫@5 種拓?fù)涠歼x擇將激光雷達(dá)與MDC 連接到同一個(gè)switch 上，沒(méi)有排隊(duì)延時(shí)，同時(shí)激光雷達(dá)的信息流對(duì)其余信息流的影響也降到了最低。因此雖然專(zhuān)家設(shè)計(jì)拓?fù)涞钠溆嘈畔⒘鞯难訒r(shí)都低，但是由于激光雷達(dá)的高延時(shí)導(dǎo)致總體延時(shí)高于端口均衡拓?fù)?，這也說(shuō)明了對(duì)于傳輸效果的優(yōu)化不僅在于提升調(diào)度算法，更重要的是對(duì)網(wǎng)絡(luò)拓?fù)溥M(jìn)行優(yōu)化。

圖17 各類(lèi)信號(hào)流平均延時(shí)對(duì)比圖

根據(jù)以上試驗(yàn)結(jié)果，對(duì)端口數(shù)、負(fù)載占用和延時(shí)對(duì)架構(gòu)設(shè)計(jì)的影響進(jìn)行歸納并提出以下設(shè)計(jì)思路：（1）延時(shí)最低和負(fù)載分配最均勻的情況下通常switch 的端口數(shù)分配分散，會(huì)出現(xiàn)一個(gè)switch 的端口數(shù)很多，與它不直接相連的switch 的端口數(shù)很少的情況，但是這不利于ZCU 設(shè)計(jì)的成本、可拓展性和安全性，在設(shè)計(jì)時(shí)，ZCU 的switch 端口數(shù)目應(yīng)當(dāng)盡可能設(shè)計(jì)的一致；（2）在保證端口數(shù)分布均勻的情況下，為了降低總體延時(shí)，可以提高最大端口數(shù)，將數(shù)據(jù)量大的信息流與接收終端連接到同一個(gè)switch上，例如本文的仿真結(jié)果將激光雷達(dá)與MDC 連接到同一個(gè)ZCU 上，總體延時(shí)降低明顯；（3）負(fù)載均勻通常可以降低延時(shí)，但是也存在為了降低排隊(duì)延時(shí)而造成的某段網(wǎng)絡(luò)負(fù)載變高的情況。在延時(shí)能夠接受的情況下，應(yīng)選擇負(fù)載均衡的拓?fù)?，這更有助于應(yīng)對(duì)突發(fā)的數(shù)據(jù)流。

5 結(jié)論

本文針對(duì)面向TSN 的區(qū)域-功能域電子電氣架構(gòu)從端口、負(fù)載和延時(shí)3 個(gè)角度構(gòu)建了網(wǎng)絡(luò)架構(gòu)多目標(biāo)優(yōu)化框架。提出了適用于流量調(diào)度問(wèn)題的多種群遺傳算法求解信息流延時(shí)，并將求解的延時(shí)用于多目標(biāo)優(yōu)化中延時(shí)適應(yīng)度的計(jì)算，相比于傳統(tǒng)遺傳算法求解效果提高16%?；诟倪M(jìn)NSGA-II算法求解了架構(gòu)拓?fù)涠嗄繕?biāo)優(yōu)化，引入自適應(yīng)交叉變異概率對(duì)算法進(jìn)行改進(jìn)，優(yōu)化效率提高了25%。最后仿真結(jié)果證明了該優(yōu)化框架的有效性，總結(jié)了端口、負(fù)載和延時(shí)對(duì)架構(gòu)設(shè)計(jì)的影響并提出了面向TSN的車(chē)載以太網(wǎng)網(wǎng)絡(luò)架構(gòu)設(shè)計(jì)思路。在未來(lái)的研究中，將進(jìn)一步考慮成本、功能安全等更多的優(yōu)化目標(biāo)。將TSN 的冗余機(jī)制引入架構(gòu)優(yōu)化設(shè)計(jì)，進(jìn)一步提高架構(gòu)設(shè)計(jì)的可靠性和安全性。