FlexRay動(dòng)態(tài)段帶寬利用率優(yōu)化研究

吳俊鵬 周美嬌 張鳳登 阮彪 龐淞友

摘 要：為提高大型網(wǎng)絡(luò)的FlexRay動(dòng)態(tài)段帶寬利用率，采用時(shí)隙復(fù)用的方法對(duì)FlexRay動(dòng)態(tài)段消息調(diào)度進(jìn)行優(yōu)化。在深入分析FlexRay動(dòng)態(tài)段帶寬利用率表達(dá)式及整體消息最壞響應(yīng)時(shí)間的基礎(chǔ)上，確定影響動(dòng)態(tài)段帶寬利用率的關(guān)鍵因素，并根據(jù)可調(diào)度分析方法建立動(dòng)態(tài)調(diào)度模型。該模型以優(yōu)化動(dòng)態(tài)段帶寬利用率為目標(biāo)，采用啟發(fā)式調(diào)度算法構(gòu)建消息的動(dòng)態(tài)調(diào)度方案，從而得出最優(yōu)的動(dòng)態(tài)段長(zhǎng)度配置和幀ID配置，以降低負(fù)載、提升網(wǎng)絡(luò)帶寬利用率。最后，以FlexRay底盤(pán)綜合控制與安全系統(tǒng)為對(duì)象，對(duì)上述算法進(jìn)行驗(yàn)證。實(shí)驗(yàn)結(jié)果證明，啟發(fā)式調(diào)度算法可以優(yōu)化動(dòng)態(tài)段幀ID配置，動(dòng)態(tài)段帶寬利用率在總線速率為5Mbit/s、10Mbit/s時(shí)分別提高了6.22%與10.23%。

關(guān)鍵詞：FlexRay;帶寬利用率;最壞響應(yīng)時(shí)間;時(shí)隙復(fù)用;調(diào)度

DOI：10. 11907/rjdk. 192131 開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2020）007-0171-07

Research on Bandwidth Utilization Optimization of FlexRay Dynamic Segment

WU Jun-peng， ZHOU Mei-jiao， ZHANG Feng-deng，RUAN Biao，PANG Song-you

（School of Optical-Electrical and Computer Engineering， University of Shanghai for Science and Technology，

Shanghai 200093，China）

Abstract：In order to improve the bandwidth utilization of FlexRay dynamic segments of large networks， this paper optimizes the scheduling of FlexRay dynamic segment messages by using slot multiplexing. Based on the in-depth analysis of the FlexRay dynamic segment bandwidth utilization expression and the worst case response time of the overall message， the key factors affecting the bandwidth utilization of the dynamic segment are determined， and a dynamic scheduling model is established according to the schedulable analysis method. The dynamic segment bandwidth utilization is the target， and a heuristic scheduling algorithm is used to construct a dynamic scheduling scheme of the message， thereby obtaining an optimal dynamic segment length configuration and frame ID configuration to reduce load and increase network bandwidth utilization. Finally， this paper verifies the above algorithm with the FlexRay chassis integrated control and security system as the object. The experiment proves that the heuristic scheduling algorithm can optimize the dynamic segment frame ID configuration， dynamic segment bandwidth utilization were increased by 6.22% and 10.23%， respectively at bus rates of 5 Mbit/s and 10 Mbit/s.

Key Words： FlexRay;bandwidth utilization;worst case response time;slot-multi

0 引言

隨著用戶對(duì)汽車(chē)安全性和舒適性的要求不斷提高，新增的電子功能模塊越來(lái)越多，數(shù)據(jù)通信量也隨之增大，傳統(tǒng)車(chē)載總線已不能滿足人們對(duì)汽車(chē)網(wǎng)絡(luò)可靠性及確定性的傳輸需求。FlexRay是汽車(chē)應(yīng)用中的一種高速通信協(xié)議，主要遵循沖突避免時(shí)間觸發(fā)通信模式，兼顧了時(shí)間觸發(fā)報(bào)文與事件觸發(fā)報(bào)文傳輸，具有高吞吐量，以及確定性、容錯(cuò)性和靈活性等特點(diǎn)，能夠滿足未來(lái)對(duì)先進(jìn)汽車(chē)高速實(shí)時(shí)控制的需求。

FlexRay動(dòng)態(tài)段主要用于非確定性事件觸發(fā)的非周期性消息傳輸，消息傳輸主要采用基于優(yōu)先級(jí)的動(dòng)態(tài)時(shí)隙分配方式，存在較長(zhǎng)的響應(yīng)時(shí)間。文獻(xiàn)[1]分析了動(dòng)態(tài)段的消息調(diào)度，在動(dòng)態(tài)段的可調(diào)度性分析基礎(chǔ)上提出動(dòng)態(tài)規(guī)劃的優(yōu)化調(diào)度算法，但沒(méi)有從整體上考慮通信周期中靜態(tài)段與動(dòng)態(tài)段的可調(diào)度性問(wèn)題;文獻(xiàn)[2]運(yùn)用保留帶寬的思想，為實(shí)現(xiàn)最大化周期負(fù)載與最小化帶寬保留建立相應(yīng)數(shù)學(xué)模型，并尋求最優(yōu)方案;文獻(xiàn)[3]對(duì)FlexRay動(dòng)態(tài)段內(nèi)的消息傳輸特性進(jìn)行詳細(xì)分析，并提出構(gòu)建消息組的調(diào)度方法;文獻(xiàn)[4]在分析動(dòng)態(tài)消息傳輸最壞響應(yīng)時(shí)間基礎(chǔ)上建立動(dòng)態(tài)消息調(diào)度問(wèn)題模型，以所有動(dòng)態(tài)消息最壞響應(yīng)時(shí)間之和最小為目標(biāo)，提出基于類DM（截止期單調(diào)調(diào)度算法，Deadline-Monotonic）的啟發(fā)式調(diào)度算法;文獻(xiàn)[5]分析動(dòng)態(tài)段消息調(diào)度，在綜合考慮動(dòng)態(tài)段帶寬利用率和最壞響應(yīng)時(shí)間基礎(chǔ)上提出類DM消息調(diào)度優(yōu)化算法，但沒(méi)有考慮到傳輸抖動(dòng)和丟包率問(wèn)題。本文在深入分析FlexRay動(dòng)態(tài)段帶寬利用率表達(dá)式和整體消息最壞響應(yīng)時(shí)間的基礎(chǔ)上，對(duì)幀格式和消息傳輸規(guī)則進(jìn)行深入研究。采用啟發(fā)式調(diào)度算法構(gòu)建消息的動(dòng)態(tài)調(diào)度方案，從而得出最優(yōu)的動(dòng)態(tài)段長(zhǎng)度配置和幀ID配置。最后，以FlexRay底盤(pán)綜合控制和安全系統(tǒng)為應(yīng)用背景，對(duì)上述算法進(jìn)行驗(yàn)證。

1 FlexRay通信協(xié)議

FlexRay為汽車(chē)提供了高級(jí)通信技術(shù)，其單個(gè)通道上的最大傳輸速率可達(dá)到10Mbps，雙通道總數(shù)據(jù)速率可達(dá)到20Mbps。當(dāng)采用冗余通道通信時(shí)，提供了傳輸容錯(cuò)機(jī)制，當(dāng)采用非冗余通道通信時(shí)，提高了帶寬，整個(gè)協(xié)議是基于時(shí)間觸發(fā)架構(gòu)的，實(shí)現(xiàn)了確定性通信。

1.1 幀格式與編碼

FlexRay幀格式[6-7]由3部分組成，分別為頭段（head segment）、負(fù)載段（payload segment）與尾段（trailer segment）。節(jié)點(diǎn)在網(wǎng)絡(luò)上傳輸數(shù)據(jù)幀時(shí)，首先傳遞幀的頭段，然后是有效負(fù)載數(shù)據(jù)段，最后是幀的尾段。在傳輸過(guò)程中，按照如圖1所示從左向右的順序進(jìn)行。

（1）頭段前5位依次為保留位、有效負(fù)載預(yù)指示位、空幀指示位、同步幀指示位與啟動(dòng)幀指示位;接下來(lái)為11位幀ID（frame ID），用于定義消息幀在每個(gè)通信周期里的發(fā)送時(shí)隙;負(fù)載段長(zhǎng)度為7位（Payload length），動(dòng)態(tài)段幀的負(fù)載段長(zhǎng)度根據(jù)傳輸消息的長(zhǎng)度而變化;頭段CRC校驗(yàn)（Header CRC）長(zhǎng)度為11位，用于判斷傳輸數(shù)據(jù)的正確性;周期計(jì)數(shù)值（cycle count）長(zhǎng)度為6位。

（2）負(fù)載段長(zhǎng)度可以進(jìn)行配置，但必須在0～127個(gè)字之間。

（3）尾段為3個(gè)字節(jié)的CRC校驗(yàn)位。

動(dòng)態(tài)幀負(fù)載段的數(shù)據(jù)0、1兩個(gè)字節(jié)通常作為消息ID（message ID），該標(biāo)識(shí)符用于接收節(jié)點(diǎn)、濾除數(shù)據(jù)并獲得有效數(shù)據(jù)部分，如圖2所示。

動(dòng)態(tài)幀編碼規(guī)則如圖3所示，編碼時(shí)會(huì)額外加上傳輸起始位（TSS）、幀起始位（FSS）、字節(jié)起始位（BSS）、幀結(jié)束位（FES），動(dòng)態(tài)消息幀會(huì)再添加動(dòng)態(tài)尾部序列（DTS）。

1.2 FlexRay媒體訪問(wèn)機(jī)制

FlexRay的媒體訪問(wèn)控制是基于柔性時(shí)分多路的（Flexible Time Division Multiple Access，F(xiàn)TDMA）訪問(wèn)機(jī)制[8]，其通信周期由4部分組成，分別是靜態(tài)段（Static Segment，SS）、動(dòng)態(tài)段（Dynamic Segment，DS）、符號(hào)窗口（Symbol Window，SW）和網(wǎng)絡(luò)空閑時(shí)間（Network Idle Time，NIT）。

1.3 動(dòng)態(tài)段傳輸與時(shí)間特性

本文針對(duì)整個(gè)網(wǎng)絡(luò)動(dòng)態(tài)段的消息調(diào)度，在假設(shè)已完成具有周期性消息靜態(tài)調(diào)度的基礎(chǔ)上，即已知通信周期Tc、靜態(tài)段長(zhǎng)度Tst與所需的靜態(tài)時(shí)隙總個(gè)數(shù)FA，繼續(xù)研究動(dòng)態(tài)段的消息調(diào)度。該部分主要包括動(dòng)態(tài)段長(zhǎng)度、動(dòng)態(tài)微時(shí)隙個(gè)數(shù)優(yōu)化配置以及動(dòng)態(tài)非周期性消息ID優(yōu)化方案。

FlexRay動(dòng)態(tài)段由動(dòng)態(tài)時(shí)隙構(gòu)成，而組成動(dòng)態(tài)時(shí)隙的是微時(shí)隙。微時(shí)隙由宏節(jié)拍（MT）組成，動(dòng)態(tài)時(shí)隙長(zhǎng)度隨著傳輸消息的長(zhǎng)度而變化。在動(dòng)態(tài)段內(nèi)，基于動(dòng)態(tài)最小時(shí)隙的訪問(wèn)機(jī)制用于仲裁傳輸，并且主要用于非周期性消息傳輸，動(dòng)態(tài)段的可用帶寬可根據(jù)實(shí)際需求進(jìn)行動(dòng)態(tài)分配。動(dòng)態(tài)段包含固定數(shù)目NDS個(gè)微時(shí)隙，該參數(shù)在設(shè)計(jì)階段進(jìn)行配置，NDS最大值為7 994。FlexRay動(dòng)態(tài)段消息真正的傳輸起始時(shí)刻從微時(shí)隙觸發(fā)點(diǎn)開(kāi)始，到下一個(gè)微時(shí)隙觸發(fā)點(diǎn)終止。微時(shí)隙起始點(diǎn)至微時(shí)隙觸發(fā)點(diǎn)之間的時(shí)間間隔稱為微時(shí)隙觸發(fā)點(diǎn)偏移量（gdMinislotActionPointOffset）。動(dòng)態(tài)時(shí)隙由兩部分組成：動(dòng)態(tài)時(shí)隙傳輸相與動(dòng)態(tài)時(shí)隙空閑相，動(dòng)態(tài)時(shí)隙空閑相是指檢測(cè)通信信道空閑的等待時(shí)間。動(dòng)態(tài)段時(shí)序如圖4所示。

動(dòng)態(tài)段消息不具有嚴(yán)格意義上的發(fā)送周期，一般將每個(gè)信號(hào)獨(dú)立地封裝為消息再進(jìn)行調(diào)度。在FlexRay通信系統(tǒng)中，消息都是以幀的形式進(jìn)行傳輸，動(dòng)態(tài)幀編碼方式是在靜態(tài)段編碼基礎(chǔ)上加上動(dòng)態(tài)尾部序列LDTS，在動(dòng)態(tài)段內(nèi)傳輸一個(gè)大小為n字節(jié)的信號(hào)數(shù)據(jù)，則以微時(shí)隙TMS為單位的動(dòng)態(tài)時(shí)隙長(zhǎng)度如下所示[9]：

其中，29為T(mén)SS（這里取15位）、FSS（1位）、FES（2位）與11位的通信空閑間隔符（CID）之和;10n表示幀頭、負(fù)載段和幀尾位數(shù)與添加了字節(jié)起始位后所得位數(shù)之和;TAPO表示微時(shí)隙觸發(fā)點(diǎn)偏移時(shí)間長(zhǎng)度（gdActionPointOffset）;LDTS的值是變化的，可以取2gdBit～LMS+2gdBit之間的任意值;gdBit表示1個(gè)比特位的傳輸時(shí)間。FlexRay通信周期的時(shí)間單位是宏節(jié)拍（MT），1個(gè)宏節(jié)拍的取值范圍在1～6μs之間。一個(gè)微時(shí)隙TMS由若干個(gè)宏節(jié)拍組成，時(shí)間長(zhǎng)度是可以配置的，一旦確定則不能變化。

動(dòng)態(tài)段帶寬利用率主要用于分析配置的動(dòng)態(tài)段長(zhǎng)度TDYN對(duì)動(dòng)態(tài)帶寬利用率的影響[10]。設(shè)系統(tǒng)中存在n個(gè)動(dòng)態(tài)消息，各消息長(zhǎng)度記為li，為了進(jìn)行數(shù)學(xué)建模分析，假設(shè)動(dòng)態(tài)消息周期pi為消息mi連續(xù)兩次產(chǎn)生的最短時(shí)間間隔，mi截止時(shí)間記為di，且滿足pi≥di，在本文設(shè)計(jì)中取每個(gè)消息的截止時(shí)間等于其周期，即pi=di，pi取最小間隔時(shí)間，在靜態(tài)段設(shè)定的NTC個(gè)通信周期Tc內(nèi)計(jì)算動(dòng)態(tài)段帶寬利用率為：

動(dòng)態(tài)段帶寬利用率UDYN反映在整個(gè)網(wǎng)絡(luò)循環(huán)周期內(nèi)所分配的所有動(dòng)態(tài)段內(nèi)，有多少用于實(shí)際動(dòng)態(tài)段的消息傳輸。通過(guò)分析上述公式可知，動(dòng)態(tài)段長(zhǎng)度越小，則其帶寬利用率越大，但動(dòng)態(tài)段過(guò)小又會(huì)使得消息延遲更久，影響傳輸?shù)膶?shí)時(shí)性。由于動(dòng)態(tài)段發(fā)送消息的時(shí)刻具有不確定性，因此需要進(jìn)一步分析各個(gè)消息的最壞響應(yīng)時(shí)間。

2 動(dòng)態(tài)段消息調(diào)度優(yōu)化方案

由于動(dòng)態(tài)段具有非周期性，所以動(dòng)態(tài)段調(diào)度更為復(fù)雜，主要通過(guò)幀ID確定的優(yōu)先級(jí)實(shí)施調(diào)度。動(dòng)態(tài)報(bào)文的優(yōu)先級(jí)有兩層含義：首先報(bào)文本身的優(yōu)先級(jí)，由報(bào)文的Message ID進(jìn)行定義，用于節(jié)點(diǎn)內(nèi)部消息報(bào)文的排隊(duì)，相當(dāng)于事件觸發(fā)系統(tǒng)中用來(lái)表示報(bào)文重要性的優(yōu)先級(jí);其次幀ID所決定的發(fā)送優(yōu)先級(jí)，其具有時(shí)間觸發(fā)特性，用于保證系統(tǒng)的實(shí)時(shí)性。為了簡(jiǎn)化系統(tǒng)，僅考慮動(dòng)態(tài)報(bào)文的發(fā)送優(yōu)先級(jí)。

幀ID配置為低的動(dòng)態(tài)消息的優(yōu)先級(jí)更高，高優(yōu)先級(jí)消息傳輸可能會(huì)導(dǎo)致低優(yōu)先級(jí)消息延遲。動(dòng)態(tài)消息長(zhǎng)度不同，也會(huì)影響其它動(dòng)態(tài)消息傳輸。為了使動(dòng)態(tài)消息能在對(duì)應(yīng)截止時(shí)間之前傳輸完畢，必須對(duì)各消息的最壞響應(yīng)時(shí)間[11]進(jìn)行分析，并盡量減少延遲，以提高動(dòng)態(tài)消息傳輸?shù)膶?shí)時(shí)性。

本文采用時(shí)隙復(fù)用[12]對(duì)FlexRay動(dòng)態(tài)段的最壞響應(yīng)時(shí)間進(jìn)行分析，主要由于兩方面原因：首先，其是對(duì)之前大多數(shù)動(dòng)態(tài)段實(shí)時(shí)性研究的一個(gè)擴(kuò)展，大多都是假定所有消息在每個(gè)周期內(nèi)都存在調(diào)度機(jī)會(huì)，而新版本提出支持時(shí)隙復(fù)用的物理層和鏈路層機(jī)制，所以將其作一般化分析，同時(shí)也適用于前期的特殊情況;其次，避免了高優(yōu)先級(jí)消息一直觸發(fā)而使低優(yōu)先級(jí)消息產(chǎn)生延遲，導(dǎo)致低優(yōu)先級(jí)消息不能在截止時(shí)內(nèi)傳輸出去，影響了系統(tǒng)的實(shí)時(shí)性。

在對(duì)最壞響應(yīng)時(shí)間進(jìn)行分析時(shí)，為了簡(jiǎn)化分析，對(duì)該調(diào)度分析前提作出如下假設(shè)：

（1）各個(gè)消息mi的基周期bi、循環(huán)周期ri與截止時(shí)間di已知。

（2）每個(gè)節(jié)點(diǎn)的[pLatestTxmi]值已知。

（3）網(wǎng)絡(luò)忽略抖動(dòng)因素，以及傳輸節(jié)點(diǎn)與接收節(jié)點(diǎn)中的最大延遲。

（4）每個(gè)消息mi在一個(gè)通信周期內(nèi)只觸發(fā)一次，且發(fā)送時(shí)不存在發(fā)送錯(cuò)誤的情況[13]。

通信控制器決定消息在固定時(shí)隙被發(fā)送到總線上。動(dòng)態(tài)段長(zhǎng)度和幀ID的分配方式?jīng)Q定了動(dòng)態(tài)段最壞響應(yīng)時(shí)間，動(dòng)態(tài)段最壞響應(yīng)時(shí)間可表示為：

σm表示消息被觸發(fā)當(dāng)前周期的最長(zhǎng)延遲時(shí)間。最壞情況是指消息mi在其時(shí)隙剛開(kāi)始之后才被觸發(fā)，因此消息mi錯(cuò)過(guò)了其發(fā)送時(shí)隙，以及在當(dāng)前周期不觸發(fā)其它FID消息，這將使消息m處于等待狀態(tài)，直到下個(gè)周期才可能進(jìn)行調(diào)度，其表達(dá)式為：

FIDmi表示消息mi所分配的幀ID號(hào)，TMS表示動(dòng)態(tài)微時(shí)隙。

[ωmi（t）]表示在給定時(shí)間間隔t中，因?yàn)槭褂猛粠琁D但具有不同ri的動(dòng)態(tài)消息、低幀標(biāo)示符（更高優(yōu)先級(jí)）消息、不傳輸消息時(shí)所占用的微時(shí)隙以及靜態(tài)幀所導(dǎo)致的最大延遲。

主要從3個(gè)方面影響該[ωmi（t）]延遲：

（1）消息mi存在時(shí)隙復(fù)用。

（2）低幀標(biāo)示符（更高優(yōu)先級(jí)）的消息[mj∈lf（mi）=][{IDmi

（3）比消息mi標(biāo)識(shí)符小，但未用于消息傳輸?shù)膭?dòng)態(tài)段時(shí)隙。

[lmi]表示消息mi在傳輸周期內(nèi)產(chǎn)生的最大延遲，在最壞的情況下，該消息在本周期所能允許的最壞時(shí)刻傳輸，即微時(shí)隙計(jì)數(shù)值為[pLatestTxmi]，消息mi才傳輸至總線上，則存在：

Cm表示消息mi通信占用的時(shí)間，忽略傳輸節(jié)點(diǎn)與接收節(jié)點(diǎn)中的最大延遲，假設(shè)消息mi負(fù)載段的有效數(shù)據(jù)長(zhǎng)度為n個(gè)字節(jié)，與公式（1）相結(jié)合，則有：

2.2 延遲周期分析

由消息mi時(shí)隙復(fù)用本身所產(chǎn)生的延遲和具有低幀標(biāo)示符的消息mi所產(chǎn)生的延遲為一個(gè)或多個(gè)周期，所以可表示為：

上式由兩部分組成，[smi]表示由消息mi時(shí)隙復(fù)用本身所產(chǎn)生的延遲周期個(gè)數(shù)，[lsmi]表示具有低幀標(biāo)示符的消息mi所產(chǎn)生延遲的周期個(gè)數(shù)。在分析基于時(shí)隙復(fù)用的動(dòng)態(tài)段消息最壞響應(yīng)時(shí)間之前，首先分析兩種情況：

（1）[mj∈lf（mi）={IDmj

（2）mi消息存在時(shí)隙復(fù)用，其它消息[mj∈lf（mi）=][{IDmj

對(duì)于第一種情況，在每個(gè)周期[cc={0，1，？，NTC-1}]中，只要消息mj能滿足[ccmodrj=bj]，那么該高優(yōu)先級(jí)消息在周期cc可能會(huì)對(duì)消息mi產(chǎn)生延遲。設(shè)滿足該條件消息的集合為[mj，cc={？mj∈lf（mi）ccmodrj=bj}]，接下來(lái)建立相應(yīng)模型，分析在上述條件下會(huì)對(duì)消息mi產(chǎn)生幾個(gè)周期的延遲，設(shè)為s1表示延遲的周期數(shù)。

如果消息在周期cc正好錯(cuò)過(guò)消息的發(fā)送時(shí)隙，通過(guò)上述分析可求解σm。需要討論在cc=cc+1之后的各個(gè)周期里，各消息是否會(huì)對(duì)消息mi的傳輸產(chǎn)生延遲，即[mj，cc={？mj∈lf（mi）ccmodrj=bj}]內(nèi)的各個(gè)消息是否對(duì)消息mi產(chǎn)生延遲，該問(wèn)題可以轉(zhuǎn)化為一維裝箱問(wèn)題。設(shè)[mj，cc，k，f∈mj.cc]，其中k為在該周期可發(fā)送的消息編號(hào)，f表示該消息的幀ID號(hào)，其數(shù)據(jù)長(zhǎng)度為[Cj，cc，k，f]。為每個(gè)周期建立一個(gè)二進(jìn)制的變量[Xj，cc，k，f]，如果消息[mj，cc，k，f∈mj.cc]，在周期cc發(fā)送，則為1，不發(fā)送則為0，在最壞情況下存在：

其中，二進(jìn)制變量yi等于1，表示該周期cc對(duì)消息mi產(chǎn)生一個(gè)周期的延遲。該變量取值受到消息mi的[pLastestTxmi]約束，即如果以下兩式成立，則yi為1，會(huì)對(duì)消息mi產(chǎn)生延遲。

依次討論在cc=cc+1后的各個(gè)周期里，低幀ID的消息在總線上傳輸是否會(huì)造成消息mi的延遲[15]，即確定yi的值，再對(duì)其累加得到總延遲周期個(gè)數(shù)s1，直到在某個(gè)周期內(nèi)，如果該周期下的負(fù)載[Loadi>pLastestTxi×TMT]，消息mi可在該周期內(nèi)發(fā)送。

對(duì)于第二種情況，待分析的消息mi是時(shí)隙復(fù)用的，其它消息在每個(gè)周期均具有調(diào)度機(jī)會(huì)，則至少存在ri-1個(gè)周期的延遲。在消息mi不能調(diào)度的周期內(nèi)，其它消息不會(huì)對(duì)其造成延遲，但在能夠調(diào)度mi的周期內(nèi)，仍然需要考慮低優(yōu)先級(jí)對(duì)其產(chǎn)生的延遲，在該情況下產(chǎn)生的總延遲用s2表示。

同理，在cc+ri周期內(nèi)分析高優(yōu)先級(jí)消息是否會(huì)對(duì)消息mi的傳輸產(chǎn)生延遲，如果該周期下的負(fù)載[Loadi>pLastestTxi×TMT]，則在該周期仍不能發(fā)送，將再延遲ri-1個(gè)周期，然后再次分析是否會(huì)被延遲，直到消息mi能夠發(fā)送為止。

基于上述分析可以得到，當(dāng)消息mi在周期cc錯(cuò)過(guò)發(fā)送時(shí)隙時(shí)，則在cc+ri的周期內(nèi)分析以下變量，當(dāng)高優(yōu)先級(jí)消息負(fù)載超過(guò)了消息最后能夠調(diào)度的截止時(shí)間時(shí)，zi等于1，否則為0，存在：

在調(diào)度周期[cc={0，1？，NTC-1}]內(nèi)，在每個(gè)消息mi能夠調(diào)度的周期內(nèi)求解zi的值，一旦存在zi=0則停止，表示消息mi可以被發(fā)送，然后對(duì)其值求和，表示在消息mi能夠調(diào)度的周期內(nèi)發(fā)生了延遲，即滿足：

由上述分析可知，在該情況下能夠產(chǎn)生的延遲周期數(shù)為：

上述兩種情況屬于時(shí)隙復(fù)用的特殊情況，針對(duì)一般消息調(diào)度分析動(dòng)態(tài)段的最壞響應(yīng)時(shí)間，在已完成時(shí)隙分配的基礎(chǔ)上進(jìn)行分析。假設(shè)在調(diào)度過(guò)程中的延遲期間不存在需要再次發(fā)送的消息，即假設(shè)q=1，以及各個(gè)消息的循環(huán)周期為ri∈{2k，k∈[0，1，2，3，4，5，6]}，也即2的權(quán)重。該假設(shè)是為了簡(jiǎn)化動(dòng)態(tài)段調(diào)度的復(fù)雜性，同時(shí)也與OSEK實(shí)時(shí)系統(tǒng)完全兼容，具有一定的可行性。設(shè)cci0=cci+1為總線周期的初始周期序數(shù)值，以及初始化消息延遲的周期個(gè)數(shù)s=0。該分析過(guò)程以cc=cc0+s循環(huán)分析各周期產(chǎn)生的延遲情況，下面將通過(guò)一個(gè)流程圖描述求解s的過(guò)程，如圖5所示。

綜合以上分析可知，在時(shí)隙復(fù)用的條件下存在[smi+lsmi=s]，也即[wmi（t）=s×Tc]，可得出消息的最壞響應(yīng)時(shí)間。

本文分析的消息mi在最壞響應(yīng)情況下能夠發(fā)送，則其必定能在任何時(shí)刻完成相應(yīng)調(diào)度。每個(gè)消息mi的最壞響應(yīng)時(shí)間滿足：

同時(shí)可以得出FlexRay動(dòng)態(tài)段消息的整體最壞響應(yīng)時(shí)間WR為：

動(dòng)態(tài)段長(zhǎng)度和時(shí)隙復(fù)用下的FID分配會(huì)對(duì)消息響應(yīng)時(shí)間和動(dòng)態(tài)段帶寬利用率產(chǎn)生影響。假設(shè)已知網(wǎng)絡(luò)中所有動(dòng)態(tài)段消息的時(shí)間參數(shù)，本文調(diào)度方案考慮優(yōu)化所有消息的最壞響應(yīng)時(shí)間，同時(shí)提高動(dòng)態(tài)段帶寬利用率。為了得到最佳的動(dòng)態(tài)段長(zhǎng)度和基于時(shí)隙復(fù)用的FID分配方案[16-19]，建立如下優(yōu)化模型：

其中，α、β分別表示動(dòng)態(tài)段未有效利用的帶寬利用率1-UDYN和動(dòng)態(tài)段消息整體最壞響應(yīng)時(shí)間WR的權(quán)值，可以依據(jù)系統(tǒng)進(jìn)行相應(yīng)配置。

為了簡(jiǎn)化調(diào)度，設(shè)置所有動(dòng)態(tài)段消息的ri∈{1，2，4，8，16，32，64}≤NTC-1取相同值，但各個(gè)消息的bi∈{0，1，…，ri-1}以及幀ID是不同的。這里借鑒DM調(diào)度算法，截止時(shí)間與可調(diào)度性有關(guān)，任務(wù)執(zhí)行時(shí)間同樣也會(huì)影響可調(diào)度性，但任務(wù)中所要傳輸?shù)南⒃介L(zhǎng)，越容易超過(guò)截止時(shí)間。所以消息長(zhǎng)度越長(zhǎng)，優(yōu)先級(jí)應(yīng)該越高，即分配的幀ID應(yīng)該越小。本文采用截止時(shí)間與消息長(zhǎng)度之差表示消息的緊急等級(jí)，即截止時(shí)間越小，動(dòng)態(tài)消息傳輸時(shí)間越長(zhǎng)，緊急程度則越高，配置的bi和幀ID也越小。動(dòng)態(tài)段調(diào)度優(yōu)化步驟如下：

（1）動(dòng)態(tài)段ri∈{2，4，8，16，32，64}≤NTC-1均取相同值，即最多存在7種循環(huán)周期的消息，消息截止時(shí)間與消息長(zhǎng)度差值越小，對(duì)應(yīng)優(yōu)先級(jí)越高，基周期bi∈{0，1，…，ri-1}和幀ID也越小。

（2）建立該方案下的動(dòng)態(tài)段長(zhǎng)度TDYN≤Tc -Tst與消息響應(yīng)時(shí)間WR的擬合關(guān)系，選取最小WR及其對(duì)應(yīng)動(dòng)態(tài)段長(zhǎng)度作為該方案下的最優(yōu)動(dòng)態(tài)段長(zhǎng)度，并計(jì)算該方案下的動(dòng)態(tài)段帶寬利用率UDYN。

（3）計(jì)算目標(biāo)函數(shù)F，對(duì)所有分配方案進(jìn)行計(jì)算后，求出使F取最小值的參數(shù)解及其對(duì)應(yīng)的分配調(diào)度表。求解過(guò)程如圖6所示。

3 動(dòng)態(tài)段消息調(diào)度優(yōu)化結(jié)果分析

本文以底盤(pán)綜合控制與安全系統(tǒng)為例，構(gòu)建具有較多數(shù)據(jù)量的FlexRay網(wǎng)絡(luò)，用于驗(yàn)證本文提出的消息調(diào)度優(yōu)化方案的可行性。該系統(tǒng)主要由電子穩(wěn)定控制系統(tǒng)（ESC）、車(chē)輛自適應(yīng)系統(tǒng)（ACC）、用于汽車(chē)發(fā)動(dòng)機(jī)管理系統(tǒng)和自動(dòng)變速器控制系統(tǒng)的FlexRay-CAN網(wǎng)關(guān)系統(tǒng)（GW）、電動(dòng)助力轉(zhuǎn)向系統(tǒng)（EPS）、連續(xù)減震控制系統(tǒng)（CDC）、空氣懸掛系統(tǒng)（ASC）共6個(gè)子系統(tǒng)組成，系統(tǒng)總線結(jié)構(gòu)如圖7所示。

每個(gè)系統(tǒng)對(duì)應(yīng)不同節(jié)點(diǎn)，該系統(tǒng)的動(dòng)態(tài)消息集合如表1所示[15]。

在對(duì)該系統(tǒng)進(jìn)行動(dòng)態(tài)段調(diào)度分析時(shí)，取微時(shí)隙等于一個(gè)宏節(jié)拍，即TMT=TMS，并且設(shè)定LDTS=4bits。由于動(dòng)態(tài)消息的非周期性，為了便于分析與調(diào)度，假設(shè)動(dòng)態(tài)消息周期pi的值為連續(xù)兩次產(chǎn)生消息mi的最短時(shí)間間隔di，α=β=0.5。為了驗(yàn)證本文提出調(diào)度方法的有效性，通過(guò)兩種方式進(jìn)行對(duì)比驗(yàn)證：一是采用文獻(xiàn)[4]的方式進(jìn)行消息調(diào)度，即不進(jìn)行時(shí)隙復(fù)用;二是采用本文提出的方法進(jìn)行驗(yàn)證，分別得出動(dòng)態(tài)消息的消息幀ID配置，以及對(duì)應(yīng)的整體最壞響應(yīng)時(shí)間，在總線速率為5Mbit/s和10Mbit/時(shí)，總線利用率分別提高了6.22%和10.23%。對(duì)比驗(yàn)證結(jié)果如表2所示。

從上述結(jié)果可知，本文優(yōu)化方案計(jì)算出的動(dòng)態(tài)段長(zhǎng)度TDYN=46μs。同時(shí)通過(guò)分析可知，本文方案在一定程度上增加了整體最壞響應(yīng)時(shí)間，但提高了動(dòng)態(tài)段帶寬利用率，其所對(duì)應(yīng)幀ID配置方案如表3所示。

通過(guò)分析表2、表3可知，把相同的幀ID在不同通信周期下分配給不同消息幀時(shí)，雖然可以縮短動(dòng)態(tài)段長(zhǎng)度，提高動(dòng)態(tài)段帶寬利用率，但提升了整體最壞響應(yīng)時(shí)間，在對(duì)實(shí)時(shí)性要求較高的場(chǎng)合，如果網(wǎng)絡(luò)消息幀不是特別龐大，且所有動(dòng)態(tài)消息可置于一個(gè)周期內(nèi)發(fā)送時(shí)，可以不采用時(shí)隙復(fù)用的調(diào)度分配方式，以達(dá)到更好的效果，即與本例得出的結(jié)果相同。同時(shí)，本例所用于對(duì)比的調(diào)度方式其實(shí)也是本文提出調(diào)度方法中的一個(gè)特例，即令所有消息幀的循環(huán)周期ri=1，基周期bi=0，所以本文提出的方法具有一定的理論價(jià)值。

4 結(jié)語(yǔ)

在研究FlexRay的動(dòng)態(tài)段消息調(diào)度優(yōu)化問(wèn)題時(shí)，既考慮最壞響應(yīng)時(shí)間，又考慮動(dòng)態(tài)段帶寬利用率，采用啟發(fā)式調(diào)度算法構(gòu)建整體的動(dòng)態(tài)消息調(diào)度方案，得出時(shí)隙復(fù)用下的FID分配表與最佳動(dòng)態(tài)段長(zhǎng)度，使在單位時(shí)間內(nèi)可以發(fā)送更多消息，從而降低了系統(tǒng)負(fù)載，提升了網(wǎng)絡(luò)帶寬利用率。仿真結(jié)果表明，該調(diào)度算法為各動(dòng)態(tài)消息配置幀ID，消息時(shí)隙復(fù)用相比消息時(shí)隙不復(fù)用的動(dòng)態(tài)帶寬利用率，在總線速率為5Mbit/s與10Mbit/s時(shí)分別提高了6.22%和10.23%。但是本文提出的動(dòng)態(tài)調(diào)度方案主要是進(jìn)行理論方面的分析與驗(yàn)證，而未在實(shí)際系統(tǒng)中進(jìn)行測(cè)試，因此對(duì)于實(shí)際帶寬利用率仍有待進(jìn)一步研究。

參考文獻(xiàn)：

[1] 顧嫣，張鳳登. FlexRay動(dòng)態(tài)段優(yōu)化調(diào)度算法研究[J]. 自動(dòng)化儀表，2009，30（12）：25-29.

[2] 夏鳳仙. FlexRay車(chē)載網(wǎng)絡(luò)調(diào)度算法研究[D]. 合肥：合肥工業(yè)大學(xué)，2011.

[3] 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.

[4] 鄭文學(xué). 車(chē)載網(wǎng)絡(luò)FlexRay調(diào)度方案優(yōu)化設(shè)計(jì)研究[D]. 杭州：浙江大學(xué)，2013.

[5] 張良玉，王義，楊乘. FexRay汽車(chē)總線調(diào)度算法優(yōu)化研究[D]. 貴陽(yáng)：貴州師范大學(xué)，2019.

[6] 張鳳登. 分布式實(shí)時(shí)系統(tǒng)[M]. 北京：科學(xué)出版社，2014.

[7] 陳珊，尚麗輝，張鳳登. FlexRay 靜態(tài)段消息調(diào)度優(yōu)化研究[J]. 計(jì)算機(jī)應(yīng)用研究，2020，37（1）：112-117.

[8] KIM B， PARK K. Analysis of frame delay probability in the FlexRay dynamic segment[J]. Industrial Informatics， 2011（7）：1519-1522.

[9] 王越飛，劉紅軍，吳嘩，等. 基于最優(yōu)傳輸可靠度的FlexRay網(wǎng)絡(luò)參數(shù)配置[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)，2018，47（7）：915-920.

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

[11] ZENG H，GHOSAL A，NATALE M D. Timing analysis and optimization of FlexRay dynamic segment[C]. 10th IEEE International Conference on Computer and Information Technology，2010：1932-1939.

[12] NEUKIRCHNER M，NEGREAN M，ERNST R，et al. Response-time analysis of the F1exRay dynamic segment under consideration of slot-multiplexing[C]. 7th IEEE International Symposium on Industrial Embedded Systems（SIES），2012（7）：21-30.

[13] 陳宇，熊光澤. 單調(diào)時(shí)限調(diào)度算法的可調(diào)度分析[J]. 計(jì)算機(jī)工程與應(yīng)用，2001（23）：19-21.

[14] TANASA B，BORDOLOI U D，KOSUCH S，et al. Schedulability analysis for the dynamic segment of F1exRay： a generalization to slot multiplexing[J]. Real-Time and Embedded Technology and Applications Symposium（RTAS）， 2012（18）： 185-194.

[15] 魏志強(qiáng)，張鳳登. 基于FlexRay線控轉(zhuǎn)向系統(tǒng)的傳輸延時(shí)算法[J]. 電子測(cè)量技術(shù)，2016，39（9）：82-86.

[16] 謝夢(mèng)如. F1exRay總線系統(tǒng)實(shí)時(shí)調(diào)度方法[D]. 合肥：合肥工業(yè)大學(xué)，2014.

[17] 殷健力. 汽車(chē)F1exRay網(wǎng)絡(luò)動(dòng)態(tài)段調(diào)度及優(yōu)化配置研究[D]. 合肥：合肥工業(yè)大學(xué)，2014.

[18] 張良玉，王義，張育貴，等. FlexRay 動(dòng)態(tài)段消息調(diào)度優(yōu)化算法[J]. 計(jì)算機(jī)與現(xiàn)代化，2018（5）：11-15.

[19] PARK I，SUNWOO M.FlexRay network parameter optimization method for automotive applications[J]. IEEE Transactions on Industrial Electronics， 2011，58（4）：1449-l459.

（責(zé)任編輯：黃 ?。?/p>

plexing;scheduling