FlexRay靜態(tài)部分基于優(yōu)先級調(diào)度問題的研究

梁佳雯，張劭昀，郭海雙（.貴州師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，貴陽 55000；.貴州師范大學(xué)物理與電子科學(xué)學(xué)院，貴陽　55000）

FlexRay靜態(tài)部分基于優(yōu)先級調(diào)度問題的研究

梁佳雯1，張劭昀2，郭海雙1
（1.貴州師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，貴陽 550001；2.貴州師范大學(xué)物理與電子科學(xué)學(xué)院，貴陽550001）

1　FlexRay介紹

FlexRay車載網(wǎng)絡(luò)標(biāo)準(zhǔn)已經(jīng)成為了同類產(chǎn)品的基準(zhǔn)，并將在未來很多年內(nèi)，引領(lǐng)整個汽車電子產(chǎn)品控制結(jié)構(gòu)的發(fā)展方向。其被認(rèn)為是繼CAN和LIN之后，未來汽車網(wǎng)絡(luò)的主流標(biāo)準(zhǔn)。簡單來說，F(xiàn)lexRay是汽車網(wǎng)絡(luò)中一種混合車載通信協(xié)議，其靜態(tài)部分使用時間觸發(fā)傳輸數(shù)據(jù)，動態(tài)部分使用事件觸發(fā)傳輸數(shù)據(jù)。事件觸發(fā)具有較高的靈活性和較高的利用率，與時間觸發(fā)相比，事件觸發(fā)的協(xié)議傳輸?shù)南⒌捻憫?yīng)時間具有不可預(yù)測性。此外FlexRay總線還具有高速的傳輸速率，能夠適應(yīng)不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，以及集合多種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)安排分布式系統(tǒng)等優(yōu)點。

2　系統(tǒng)模型和定義變量

2.1Flex Ray 協(xié)議模型

FlexRay周期是媒體訪問FlexRay調(diào)度的基本單位。FlexRay周期提供了兩種不同的總線訪問策略，一種是靜態(tài)部分 （SS）應(yīng)對時間觸發(fā)的時分多址訪問（TDMA）調(diào)度，另一種是用在動態(tài)部分用以應(yīng)對事件觸發(fā)的柔性時分多址（FTDMA）訪問。動態(tài)部分（DS）一般不會涉及這個問題。

目前，關(guān)于FlexRay優(yōu)化的研究很少，文獻[1]提出一種通過FlexRay總線靜態(tài)段長度分析FlexRay總線負(fù)載率的方法，文獻[2]提出一種將靜態(tài)段長數(shù)據(jù)幀分配到動態(tài)段的調(diào)度方法來減少總線的負(fù)載率。但是這種方法使得消息發(fā)送具有不確定性。

在靜態(tài)部分，一個周期內(nèi)時隙的長度是固定的，且一個給定的位置總是保留給相同的節(jié)點。靜態(tài)部分的仲裁是通過為每個網(wǎng)絡(luò)節(jié)點的每個消息分配獨特的幀ID來實現(xiàn)的。這種做法阻止了總線的沖突。靜態(tài)時隙的大小是網(wǎng)絡(luò)全局配置的，即可以設(shè)置為能夠通過總線最長消息的大小。也就是說如果ECU在這個時隙沒有數(shù)據(jù)傳輸，靜態(tài)時隙的大小也不能改變，在這種情況下，有效荷載沒有數(shù)據(jù)[3]。為了增加為使用時隙的數(shù)量，通過優(yōu)化通信周期的大小和時隙的大小，反過來增加通信系統(tǒng)帶寬的利用率。文本是為了利用靜態(tài)部分優(yōu)先級關(guān)系調(diào)度消息。此外，本文假設(shè)FlexRay允許時隙復(fù)用，這意味著相同的幀ID能夠被不同節(jié)點的消息利用。在文獻[4]中，通過給每個消息定義一個基礎(chǔ)周期（初始周期）和重復(fù)率（傳輸周期）增加時隙復(fù)用的數(shù)量，從而增加FlexRay總線的利用率的。舉例來說，只有傳輸消息時使用不同的通信周期，相同的幀ID才能被分配給多個節(jié)點。時隙復(fù)用是用重復(fù)率和基礎(chǔ)周期進行描述的：重復(fù)率是用來描述每個幀標(biāo)識符的消息傳輸?shù)念l率，基礎(chǔ)周期表示在FlexRay周期內(nèi)消息發(fā)生的初始通信周期。模型流程圖如圖1所示。

圖1　FlexRay協(xié)議模型流程圖

2.2定義變量

在此篇文章中，需要用到的FlexRay靜態(tài)部分參數(shù)定義如下：H，nslot，lslot，其中H是主周期 （MC）內(nèi)FlexRay周期（FC）的數(shù)量，nslot是通信周期（CC）內(nèi)靜態(tài)部分的時隙數(shù)量，lslot代表靜態(tài)部分時隙的長度。模型由N個節(jié)點組成，N={1，…，N}代表一系列節(jié)點。每個消息mi的傳輸時間為wi，傳輸節(jié)點為ni，重復(fù)率為ri，，基礎(chǔ)周期為bi且bi＜ri。本文假設(shè)消息的長度和時隙的長度相等。ui表示分配給每個消息mi的幀ID。為了解決調(diào)度問題和找到一個可行的時隙裝箱，本文需要決定每個消息的幀標(biāo)識符ui和基礎(chǔ)周期bi。

現(xiàn)有的相關(guān)研究中多采用有向無環(huán)圖對汽車電子系統(tǒng)中的應(yīng)用進行抽象描述，如圖2（a）所示，其中頂點表示任務(wù)，頂點之間的連線表示通信信號。

圖2　

3　裝箱問題

在文獻[5]中，作者為了實現(xiàn)所使用節(jié)點的數(shù)量最少，將問題轉(zhuǎn)化成了一個二維的裝箱問題，但是其沒有考慮到每個消息的獨立性。因此本文將問題轉(zhuǎn)化成為一個二維的條狀裝箱問題的同時，需要充分考慮每個消息間的獨立性。裝箱問題中每條的高度為Hs，且Hs= H.nslot。每條被分成nslot個部分。在所有的FlexRay周期中，被劃分出的每個小部分，用si表示，其中i=1，…，nslot，代表第i個時隙，即第i個幀ID。本文將每個消息mi傳送到一個矩形gi中。gi的寬度就是在總線上單獨完整傳送每個消息的時長。每個矩形gi的高度，用hi表示，gi的高度就是主周期內(nèi)傳輸消息mi所要求的靜態(tài)時隙數(shù)，其中每個矩形的高度：

條狀裝箱問題的目的就是為了給每個獨立矩形找到其所使用條狀的最小高度。本文使用點yi的坐標(biāo)表示每個矩形gi中條狀的位置。用ki表示分配給每個矩形gi的部分，ki用公式（2）表示

點（ki，yi）能夠根據(jù)公式（3）轉(zhuǎn)化成FlexRay靜態(tài)部分的對應(yīng)位置。

其中，ui是消息mi的幀標(biāo)識符。即當(dāng)一個矩形分配給第i個部分時，對應(yīng)的消息就分配給了第i個時隙。圖3展示將圖2中的示例消息利用裝箱問題放置到對應(yīng)的矩形中。表1和表2說明了將舉例消息中的坐標(biāo)（ki，yi）換算成對應(yīng)靜態(tài)部分的坐標(biāo)（ui，ki）。

表1　

圖3　裝箱問題應(yīng)用舉例

本文發(fā)現(xiàn)如果只有單獨的條狀裝箱問題無法完全解決矩形可靠性等問題。為了解決這些問題，本文引入了新的約束，稱為三條約束。

4　三條約束

一個FlexRay通信周期內(nèi)的靜態(tài)部分被分成了若干個相等的時隙。每個ECU能被分配給一個或多個時隙，然而每個時隙只能匹配一個ECU。如果一個時隙被分配給了一個特定的ECU，然后再每個通信周期內(nèi)它都會被分配給同一個ECU。這就是文獻[6]在FlexRay靜態(tài)部分優(yōu)化調(diào)度問題研究中所考慮到的約束。為了解決消息間優(yōu)先級和矩形封裝可行性問題，這個部分本文引入一系列新的約束，分別為高度約束，沖突約束和優(yōu)先級約束。

4.1高度約束

定義高度的約束是為了限制矩形的寬度只能是高度的整數(shù)倍。因此，對于每個矩形gi的高度的約束用以下的公式定義：

這樣防止一個矩形被分配給了兩個相鄰的部分。因為，如果一個矩形被分配給了兩個相鄰的部分，它將有可能被分給兩個連續(xù)的幀ID。這個與FlexRay的規(guī)定每個通信周期內(nèi)一個幀ID只能使用一次是沖突的。。

4.2沖突約束

定義沖突約束是為了防止消息傳輸中發(fā)生沖突，當(dāng)兩個來自不同節(jié)點的消息被分配給同一個幀ID時，消息間的沖突就會發(fā)生。舉例來說，在圖2（a）中，讓本文交換g2和g3g5的位置，交換后y3=4，y5=6，y2=8，此時因為b4=b5=1，所以在周期1的第二個時隙中，消息傳輸時會有沖突發(fā)生。假設(shè)gi和gj都被封裝在同一個部分中，例如ki=kj=k。消息mi和mj之間的沖突能通過定義公式（5）預(yù)防發(fā)生：

4.3優(yōu)先級約束

5　結(jié)語

本文主要研究FlexRay協(xié)議中靜態(tài)部分消息調(diào)度優(yōu)先級關(guān)系的問題。因此為了得到最小的使用時隙數(shù)，即最小幀ID的時隙號本文將優(yōu)先級的消息調(diào)度問題轉(zhuǎn)化成為了一個裝箱問題。其后為解決裝箱問題中的可靠性等問題，引入了關(guān)于傳輸過程中消息間高度、優(yōu)先級以及沖突的約束。對于如何通過建模仿真得到最小時隙數(shù)的最優(yōu)解，將在進一步的研究和實驗中進行。

[1]Minkoo Kang，Kiejin Park，Bongjun Kim.Determining the Size of a Static Segment and Analyzing the Utilization of In-Vehicle FlexRay Network[J].IEEE Computer Society，DOI 10.1109/ICCIT.2008.317:50-53.

[2]Minkoo Kang，Kiejin Park，Bongjun Kim，A Static Message Scheduling Algorithm for Reducing FlexRay Network Utilization[J].IEEE International Symposium on Industrial Electronics，2009:1287-1291.

[3]D.Paret，F(xiàn)lexRay and Its Applications:WILEY，2012.

[4]T.Schenkelaars，B.Vermeulen，K.Goossens.Optimal Scheduling of Switched FlexRay Networks[J]DATE Conf 2011,1-6.

[5]M.Lukasiewycz,M.Glab,J.Teich.FlexRay Schedule Optimization of the Static Segment[J].IEEE International Conference Hardware/Software Codesign and System Synthesis,2009

[6]H.L.Zheng Sun,Min Yao,Nan Li.Scheduling Optimization Techniques for FlexRay[J].IEEE/ACM International Conference on Cyber, Physical and Social Computing,2010.

張劭昀（1987-），陜西咸陽人，碩士研究生，研究方向為智能網(wǎng)絡(luò)控制

郭海雙（1989-），河北唐山人，碩士研究生，研究方向為智能網(wǎng)絡(luò)控制

FlexRay;Static Section;Priority

Research on Priority Scheduling Problem Based on the Static Section of FlexRay

LIANG Jia-wen1，ZHANG Shao-yun2，GUO Hai-shuang1
（1.Guizhou Normal University，School of Mathematics and Computer Science，Guiyang 550001；2.Guizhou Normal University，School of Physics and Electronic Science，Guiyang550001）

1007-1423（2016）06-0007-04

10.3969/j.issn.1007-1423.2016.06.002

梁佳雯（1991-），女，湖北武漢人，碩士研究生，研究方向為智能網(wǎng)絡(luò)控制

2016-01-05

2016-02-16

FlexRay通信周期中包含靜態(tài)部分和動態(tài)部分，使得此種通信方式既支持時間觸發(fā)又支持事件觸發(fā)。為了提高FlexRay通信總線的使用率，研究靜態(tài)部分基于優(yōu)先級的調(diào)度問題，期望得到最大的自由時隙數(shù)，即最小的使用時隙數(shù)，為額外節(jié)點提供更多空間來增加系統(tǒng)的擴展性。因此將其轉(zhuǎn)化成為一個二維的裝箱問題，最后引入約束條件優(yōu)化消息調(diào)度中優(yōu)先級的關(guān)系。為后續(xù)建立模型解決靜態(tài)部分基于優(yōu)先級調(diào)度問題及得到最優(yōu)解奠定理論基礎(chǔ)。

FlexRay；靜態(tài)部分；優(yōu)先級

FlexRay communication cycle includes static section and dynamic section,which makes it possible to support both time trigger and event trigger.In order to improve the utilization of FlexRay bus,studies the priority scheduling problem based on the static section,hopping to get the maximum number of free slots,namely the minimum number of used slot,providing more space for additional nodes to increase the scalability of the system.Converts it into a packing problem,then introduces the constraints to optimize the priority relationship during the process.It lays the theoretical foundation for subsequent establish the model to solve the problem and get the optimal solution.