時間觸發以太網的任務調度算法研究

◆劉國輝 祁志民

時間觸發以太網的任務調度算法研究

◆劉國輝 祁志民

（北方自動控制技術研究所 山西 030006）

在基于時間觸發以太網（time-triggered Ethernet，TTE）的系統中，為了能夠根據通信的任務需求優化組織TTE網絡的任務調度，本文給出了適用于TTE交換網絡的任務分配方法，并使之與互聯構型的設計和規劃相結合，得到相應的TTE網絡任務調度模型。

TTE；任務分配；任務調度

1 引言

時間觸發以太網（Time-Triggered Ethernet，TTE）傳遞時間觸發（Time-Triggered，TT）流量的同時，還可兼容兩種事件觸發的流量——速率約束（Rate Constrant，RC）流量和“盡力傳”（Best Effort，BE）流量[1]。基于調度時刻表（scheduling time-table）的TT流量時分多路訪問（Time Division Multiplexing Access，TDMA）通信機制，保證了嚴格時間確定性和高完整性的網絡流量傳輸，即：合理設計的調度時刻表不僅使TT消息經過交換機時不發生碰撞，還可以避免TT流量過分地阻塞RC流量[2]。為了能夠根據通信的任務需求優化組織TTE網絡的TDMA，提出了適用于TTE交換網絡的任務分配方法，并使之與互聯構型的設計和規劃相結合。

2 網絡與任務模型

2.1 網絡的物理拓撲結構

在標準以太網中，端系統（End System，ES）與交換機以及交換機之間均通過雙向通信鏈路連接，交換機作為轉發結構實現端系統通信。任意兩臺交換機之間的鏈路稱為多跳鏈路，圖1給出一種多跳拓撲的例子。

在靜態路由條件下，對于給定的端到端通信任務，存在一條從源ES經過交換機到目的ES的固定通信路徑。如果從源ES到目的ES有多條通道，則意味著端到端路徑的選擇不是唯一的，則有可能根據路徑規劃方法為每條獨立的虛擬鏈路（Virtual Link，VL）各自指定不同的物理路徑；如果存在多播，則從源ES到多個目的ES形成一個有向的樹狀路徑[4]。

2.2 TTE網絡拓撲的定義

用賦權連通有向圖G=（V，E）表示網絡拓撲，如圖2所示[5]，其中V為所有TTE網絡節點集合，即TTE網絡中處理器和交換機的集合，V=（v1，v2，…，vN），N為節點數量。E為所有連接節點的有向鏈路的集合，節點vi到節點vj（vi∈V，vj∈V）的有向鏈路e（e∈E），可以表示為e=vivj=eij；TTE網絡中采用全雙工鏈路，若有eij∈E，則eji∈E。

這里定義：鄰接矩陣A=（aij）N×N，aij為：

其中，aij=1表示節點vi、vj（vi∈V，vj∈V）為直接相連節點，aij=0表示以上兩節點無直接相連關系。

2.3 處理任務與通信任務參數表示

目前，采取了將通信任務參數轉化為處理任務附帶的代價，運用將多變量優化問題轉換為單目標優化問題的方法解決此問題。運用合理簡化假設法，不計任務分解后可能帶來的額外開銷，此外，不同任務之間存在部分的相關性，將這些具有相關關系的部分轉化為統一量化量，從而實現多目標到單目標優化的轉變。

通信任務是指兩個處理任務對應的應用層“端到端”的有向流量。可將通信任務用一個集合T來表示[6]，對于任意t?T，可以用含三參量（sk，qk，wk）表示，sk指通信任務的發出任務，qk表示通信任務的接收任務，wk表示通信任務的流量。

通過以上通信關系矩陣，可將相應通信任務參數轉換成處理任務附帶的代價，從而能夠將通信任務與處理任務統一分配，達到變量數量簡化的目的。

3 任務分配方法

3.1 任務分配遵循原則

在對TTE網絡進行任務調度的時候，應該考慮到以下幾點準則：

（1）負載均衡原則

在分配通信任務的時候，應該盡量將任務均勻的分配在各條鏈路上，以次避免路由中某些鏈路過于繁忙，造成通信堵塞。

（2）路由“跳數”較少原則。

任務在路由中的轉跳數，影響鏈路資源的利用率，合適的轉“跳數”同時還可以避免鏈路的局部堵塞。

3.2 TTE網絡的任務調度算法

由于TTE網絡中需要考慮的參數較多，因而需要使用迭代算法來簡化整個調度過程，其總體流程如下。

首先，對于分解、映射和調度中的評價指標進行歸納，形成一致的評價體系，基于生成的各種“子任務”間的依賴關系和約束關系，確定初步的約束條件（包括硬約束和軟約束）和目標函數，并運用現代啟發式方法對整個TTE網絡的進行計算，尋找到在當前條件下的最優（次優）解，生成任務與資源分布式綜合的映射。

3.3 目標函數的確定

由于TTE網絡中TT通信本身所具有的時間確定性，在遵循兩個任務分配原則情況下，可以通過定義以下指標進行任務流量的分配：

其中：

這里目標函數的表達采用了概率學中方差的概念，以TTE網絡中節點和鏈路上分配的任務的方差與路由轉“跳數方差”之和為目標函數，其值越小，則說明其分配效果越好。

3.4 通信任務路徑選擇

對通信任務進行配置時，需要考慮任務路徑的相關性，在TTE網絡中，任務路徑配置的次序與計算的影響因子相關，即先配置的任務路徑不考慮后配置任務路徑對它的影響，而后配置的計算所有先配置的影響。因此，在任務路徑配置的過程中，盡可能按照對網絡影響程度的大小，配置相應的任務路徑的次序[7]。

配置任務路徑時，需要考慮節點間通信的自由度，兩個具備通信關系的節點間可供選擇的路徑可能有多條。這里采用兩個參量限制通信的自由度，即負載均衡度和路由轉跳次數，綜合考量這兩個因素的相互約束，以期路徑較好的匹配。由于，每次路徑更新都得在目標函數中重新計算一次，為了更高效進行整網的通信路徑匹配，提出了以下路徑配置的方法和步驟[8]：

步驟1：確定鏈路通路，即兩節點間直接相連的鏈路為一條鏈路通路，構建任務路徑數組；

步驟2：將任務路徑中的元素按照對這個網絡的影響從大到小排序；

步驟3：依據步驟2中的排序，首先確定起始節點，結合目的節點在步驟1數組中的順序逐步生成次優最小代價樹，作為配置的任務路徑；

這種生成通信路徑的方法，較好地實現了鏈路負載均衡度與路由轉跳次數對配置結果平衡影響的目的，其次，采用的算法復雜度較低，能夠快速完成通信路徑的匹配。

3.5 優化問題求解

在TTE網絡拓撲結構中，需要解決任務與資源映射的組合優化問題，根據求解的效率，這里選用模擬退火算法，依靠其較強的局部搜索能力求解任務分配優化問題，具體步驟如圖2。

步驟1：構建TTE網絡的相關信息。即其拓撲結構、各個任務的相關參數、各網絡節點以及鏈路之間的約束條件；

步驟2：數學模型中關鍵變量轉化，鑒于TTE網絡中TT通信的時間確定性，將約束參量進行統一量化，將通信任務轉化為處理任務的相關量，實現統一分配；

圖3 模擬退火算法流程

步驟3：相關參數設定，即設計合適的冷卻進度表。主要有控制參數Temperature的初值T0、控制參數Temperature的衰減函數及markovLength；

步驟4：產生一個初始解X（0）；

步驟5：從X的鄰域中隨機選取一個新解X（b），比較X（b）與當前解X的函數值G（X），并計算?G（X）=G（X（b））-G（X），若?G（X）<0，則接受新解X←X（b）；若?G（X）≥0，則以概率exp（-?G（X）/T）接受新解X←X（b）。然后判斷是否達到內循環終止條件（p=MarkovLength+1），若在該溫度達到內循環終止條件，則執行下一步，否則重復執行步驟5；

步驟7：輸出當前解X。

在上述的過程中，初始解的狀態X（0）是隨機產生的，G（X）為評價函數，終止條件為連續若干個新解都沒有被接受或者增量都非常小時，或迭代次數K大于總迭代次數T時，則終止算法。

4 結論

從TTE網絡的任務分配入手，隨后考慮互連構型對TT消息路徑選擇的影響，在任務分配、路徑規劃的過程中，分階段地使用了以啟發式算法為主的組合優化算法，使得TTE交換網絡的TT通信任務的全面綜合化設計可以取得近似最優的結果。

[1]王家興.時間觸發以太網關鍵技術研究與設計[D].浙江大學，2019.

[2]馮健清. 時間觸發以太網的節點設備軟件設計[D].電子科技大學，2017.

[3]Time-triggered ethernet：SAE AS6802[S].SAE AerospaceStandard，2011-11.

[4]Y Zhang，F. He，G. Lu and H. Xiong. Clock synchronization compensation of Time-Triggered Ethernet based on least squares algorithm[C].2016 IEEE/CIC International Conference on Communications in China（ICCC Workshops）， Chengdu，2016：1-5.

[5]Z. Zheng，F. He and Y Xiong. The research of scheduling algorithm for time-triggered ethernet based on path-hop[C]. 2016 IEEE/AIAA 35th Digital Avionics Systems Conference（DASC），Sacramento，CA，2016：1-6.

[6]湯宇，李峭，賈琪明. 時間觸發以太網的分布式任務負載均衡分配方法[J]. 計算機工程與設計，2014，35（05）：1501-1505.

[7]欒不群.時間觸發以太網中時間觸發業務調度算法的研究[D].西安電子科技大學，2019.

[8]劉美辰. 多跳時間觸發以太網調度優化機制與算法的研究[D].大連理工大學，2019.