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

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

梁佳雯1，張劭昀2，郭海雙1
（1.貴州師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(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)整個(gè)汽車電子產(chǎn)品控制結(jié)構(gòu)的發(fā)展方向。其被認(rèn)為是繼CAN和LIN之后，未來汽車網(wǎng)絡(luò)的主流標(biāo)準(zhǔn)。簡(jiǎn)單來說，F(xiàn)lexRay是汽車網(wǎng)絡(luò)中一種混合車載通信協(xié)議，其靜態(tài)部分使用時(shí)間觸發(fā)傳輸數(shù)據(jù)，動(dòng)態(tài)部分使用事件觸發(fā)傳輸數(shù)據(jù)。事件觸發(fā)具有較高的靈活性和較高的利用率，與時(shí)間觸發(fā)相比，事件觸發(fā)的協(xié)議傳輸?shù)南⒌捻憫?yīng)時(shí)間具有不可預(yù)測(cè)性。此外FlexRay總線還具有高速的傳輸速率，能夠適應(yīng)不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，以及集合多種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)安排分布式系統(tǒng)等優(yōu)點(diǎn)。

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

2.1Flex Ray 協(xié)議模型

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

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

在靜態(tài)部分，一個(gè)周期內(nèi)時(shí)隙的長(zhǎng)度是固定的，且一個(gè)給定的位置總是保留給相同的節(jié)點(diǎn)。靜態(tài)部分的仲裁是通過為每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的每個(gè)消息分配獨(dú)特的幀ID來實(shí)現(xiàn)的。這種做法阻止了總線的沖突。靜態(tài)時(shí)隙的大小是網(wǎng)絡(luò)全局配置的，即可以設(shè)置為能夠通過總線最長(zhǎng)消息的大小。也就是說如果ECU在這個(gè)時(shí)隙沒有數(shù)據(jù)傳輸，靜態(tài)時(shí)隙的大小也不能改變，在這種情況下，有效荷載沒有數(shù)據(jù)[3]。為了增加為使用時(shí)隙的數(shù)量，通過優(yōu)化通信周期的大小和時(shí)隙的大小，反過來增加通信系統(tǒng)帶寬的利用率。文本是為了利用靜態(tài)部分優(yōu)先級(jí)關(guān)系調(diào)度消息。此外，本文假設(shè)FlexRay允許時(shí)隙復(fù)用，這意味著相同的幀ID能夠被不同節(jié)點(diǎn)的消息利用。在文獻(xiàn)[4]中，通過給每個(gè)消息定義一個(gè)基礎(chǔ)周期（初始周期）和重復(fù)率（傳輸周期）增加時(shí)隙復(fù)用的數(shù)量，從而增加FlexRay總線的利用率的。舉例來說，只有傳輸消息時(shí)使用不同的通信周期，相同的幀ID才能被分配給多個(gè)節(jié)點(diǎn)。時(shí)隙復(fù)用是用重復(fù)率和基礎(chǔ)周期進(jìn)行描述的：重復(fù)率是用來描述每個(gè)幀標(biāo)識(shí)符的消息傳輸?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í)隙數(shù)量，lslot代表靜態(tài)部分時(shí)隙的長(zhǎng)度。模型由N個(gè)節(jié)點(diǎn)組成，N={1，…，N}代表一系列節(jié)點(diǎn)。每個(gè)消息mi的傳輸時(shí)間為wi，傳輸節(jié)點(diǎn)為ni，重復(fù)率為ri，，基礎(chǔ)周期為bi且bi＜ri。本文假設(shè)消息的長(zhǎng)度和時(shí)隙的長(zhǎng)度相等。ui表示分配給每個(gè)消息mi的幀ID。為了解決調(diào)度問題和找到一個(gè)可行的時(shí)隙裝箱，本文需要決定每個(gè)消息的幀標(biāo)識(shí)符ui和基礎(chǔ)周期bi。

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

圖2　

3　裝箱問題

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

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

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

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

表1　

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

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

4　三條約束

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

4.1高度約束

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

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

4.2沖突約束

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

4.3優(yōu)先級(jí)約束

5　結(jié)語

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

[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-），陜西咸陽人，碩士研究生，研究方向?yàn)橹悄芫W(wǎng)絡(luò)控制

郭海雙（1989-），河北唐山人，碩士研究生，研究方向?yàn)橹悄芫W(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-），女，湖北武漢人，碩士研究生，研究方向?yàn)橹悄芫W(wǎng)絡(luò)控制

2016-01-05

2016-02-16

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

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

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.