FlexRay靜態部分基于優先級調度問題的研究

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

FlexRay靜態部分基于優先級調度問題的研究

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

1　FlexRay介紹

FlexRay車載網絡標準已經成為了同類產品的基準，并將在未來很多年內，引領整個汽車電子產品控制結構的發展方向。其被認為是繼CAN和LIN之后，未來汽車網絡的主流標準。簡單來說，FlexRay是汽車網絡中一種混合車載通信協議，其靜態部分使用時間觸發傳輸數據，動態部分使用事件觸發傳輸數據。事件觸發具有較高的靈活性和較高的利用率，與時間觸發相比，事件觸發的協議傳輸的消息的響應時間具有不可預測性。此外FlexRay總線還具有高速的傳輸速率，能夠適應不同網絡拓撲結構，以及集合多種網絡拓撲結構安排分布式系統等優點。

2　系統模型和定義變量

2.1Flex Ray 協議模型

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

目前，關于FlexRay優化的研究很少，文獻[1]提出一種通過FlexRay總線靜態段長度分析FlexRay總線負載率的方法，文獻[2]提出一種將靜態段長數據幀分配到動態段的調度方法來減少總線的負載率。但是這種方法使得消息發送具有不確定性。

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

圖1　FlexRay協議模型流程圖

2.2定義變量

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

現有的相關研究中多采用有向無環圖對汽車電子系統中的應用進行抽象描述，如圖2（a）所示，其中頂點表示任務，頂點之間的連線表示通信信號。

圖2　

3　裝箱問題

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

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

點（ki，yi）能夠根據公式（3）轉化成FlexRay靜態部分的對應位置。

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

表1　

圖3　裝箱問題應用舉例

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

4　三條約束

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

4.1高度約束

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

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

4.2沖突約束

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

4.3優先級約束

5　結語

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

[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，FlexRay 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-），陜西咸陽人，碩士研究生，研究方向為智能網絡控制

郭海雙（1989-），河北唐山人，碩士研究生，研究方向為智能網絡控制

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-），女，湖北武漢人，碩士研究生，研究方向為智能網絡控制

2016-01-05

2016-02-16

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

FlexRay；靜態部分；優先級

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.