基于自適應改進遺傳算法的MVB周期調度表優化

鄭 曼， 胡黃水， 楊興旺， 卿金輝

(長春工業大學 計算機科學與工程學院， 吉林 長春 130012)

0 引 言

多功能車輛總線(Mutlifunction Vehicle Bus, MVB)作為列車通信網絡(Train Communication Networks, TCN)的標準之一，在地鐵、城軌、高鐵等車輛上得到了廣泛的應用[1-3]。雖然IEC61375-1標準明確規定了MVB數據傳輸的實時性要求，但如何進一步提高通信實時性能一直是其面臨的主要挑戰[4-6]。國內學者進行了諸多研究，也相應地提出了一些更優化的算法。如文獻[7]提出了多粒子群優化算法，這種算法在處理連續問題上有一定的優越性，但對于離散問題的調度優化則存在一定的缺陷；文獻[8]提出了差分進化算法，該算法難以選取變異策略，缺乏局部搜索能力；文獻[9]在文獻[8]的基礎上提出了改進差分進化算法，該算法動態調整了周期信息與非周期信息時長，但在具體指標的優化上未達到理想的效果。

為了更智能地調整算法控制參數來處理離散信息調度問題，文中提出一種基于自適應改進遺傳算法的MVB周期信息實時調度算法，對周期調度表進行優化，然后根據約束條件及優化目標對周期調度表的寬度和梯度等參數進行調整，以達到均勻傳輸信息、提高實時性的目的。

1 MVB網絡的通信原理

MVB通過網絡中唯一的主設備進行集中式實時調度管理來完成過程數據和消息數據兩類信息的傳輸，其中過程數據為周期信息。主設備首先廣播發送過程數據請求主幀，接收主幀后，與主幀中邏輯端口地址相同的源設備發送響應從幀，主設備接收從幀后開始發送數據，以此完成一次周期信息的傳輸。因此，源設備周期數據報文發送的先后次序是由主幀的排列次序決定的。對周期數據調度的優化，實際上就是對周期掃描表的優化。MVB周期信息通信過程如圖1所示。

圖1 MVB周期信息通信過程

1.1 特征周期

在MVB網絡中，同一節點的兩個連續輪詢之間的時間間隔叫做特征周期，用T_ip表示:

T_ip=2n×T_bp

(1)

一般地，基本周期為1 ms，最長的特征周期不得超過1 024 ms。

1.2 周期調度表

周期掃描表本質上是一個宏循環的每個周期里要輪詢的節點、地址及設備表。宏循環為一個宏周期中包含的基本周期數，而宏周期為最長的特征周期。

在構建周期調度表時，一個宏循環由一個宏周期內的所有循環組成，一個循環將相同特征周期的周期信息編為一組，組名用n表示；同時，一個循環可分為若干個由多個基本周期組成的子循環。

定義W為周期掃描表的寬度，即在周期掃描表各行的最大周期相寬度；G為周期掃描表的時間梯度，即周期掃描表最長周期相和最短周期相之差；H為周期掃描表的高度：

H=2max(λi),i∈{0,1,…,n-1}

(2)

G=max{length(i)}-min{length(i)}

(3)

式中：n——周期變量;

λi——周期級別;

length(i)——第i個基本周期內周期相長度。

基于此，假設一個包含30個循環的宏循環的周期數據，其中有7個周期變量

V=(v0,v1,v2,v3,v4,v5,v6)

其特征周期級別分別為

截取前8個循環得到的周期掃描表如圖2所示。

圖2 按協議生成的前8個循環的周期掃描表

2 算法設計

由于MVB周期信息在一個宏周期中，會隨機傳輸各種時間長度不同的數據。在基本遺傳算法的基礎上，基于遺傳算法的自適應機制[10]能夠動態調整策略參數，即需要處理的MVB周期信息集；該機制使MVB周期信息集能對進化過程中事先難以預料的細節產生反應，適應在各個階段的不同環境，從而更靈活地將長度合適的周期信息排列在調度表中。在遺傳進化過程中，需調度的周期信息集以某種方式動態地獲取和利用關于問題的規律性知識，進行群體的自動學習，完成周期調度表的排布，以達到均勻傳輸信息、提高實時性的目的。

2.1 約束條件

IEC61375-1標準中給出了以下約束條件：

1)所有周期信息傳輸的總時間在一個基本周期內應小于周期相所占時間。

2)宏周期最大不得超過1 024 ms。

3)過程數據的主幀長度固定為33位，從幀長度有5種類型，分別為33、49、81、153、297位；過程數據傳輸的時間為：

(4)

式中：Nmaster——主幀長度；

Nslave——從幀長度；

VMVB——信號速率，其值取1.5 Mbit/s；

Treply——主幀發出后到響應該主幀的從幀發出的時間間隔；

Tsm——兩個報文之間的傳輸間隔。

2.2 優化目標

IEC61375-1標準中要求周期信息均勻分布，則可根據最大周期相和最短周期相的時間計算標準差：

(5)

(6)

式中：N(m)——第m個基本周期的端口數；

tave——周期相的平均值；

Nλ——特征級別為λ的端口數目；

ti——第i個周期相的時間。

2.3 算法流程

從第一個周期和以第一個宏周期開始，步驟如下：

1)明確實際問題參數集及約束條件；

2)選擇編碼策略，對需要調度的周期信息集進行編碼；

3)確定優化目標；

4)判斷第i個周期能否發送信息，若不能，則信息不能放在第i個周期，若能，則進行下一步；

5)判斷能夠發送的信息是否在周期相內，不能則該信息不被調度，能則將信息安排在調度表中；

6)按照遺傳策略，用自適應算子篩選信息群體，以形成下一代信息群體；

7)判斷生成的周期調度表是否滿足約束條件，不滿足則返回5)，或者修改遺傳策略再返回6)；

8)宏周期結束，所有周期信息掃描完畢，則生成周期掃描表。

自適應遺傳算法生成周期掃描表的基本流程如圖3所示。

圖3 采用自適應遺傳算法構成MVB周期調度表的流程

3 仿真分析

為了驗證該算法對生成MVB周期調度表這一實際問題的有效性，在滿足IEC61375-1標準的基礎上，與文獻[9]中運用的改進差分算法進行仿真對比，周期變量配置如1.2中所示。采用自適應方法生成的前8個循環的周期掃描表如圖4所示。

對比圖2和圖4可以發現，采用自適應算法后的周期掃描表，周期調度表的梯度小，周期變量排布更均勻。

采用改進差分算法和自適應遺傳算法傳輸周期信息在一個宏周期中過程數據通信時長的分布如圖5所示。

圖4 采用自適應遺傳算法生成的前8個循環的周期掃描表

圖5 兩種算法的過程數據通信時長

由圖5對比可以發現，改進差分算法生成的周期掃描表中過程數據通信時長最大為450 μs，最小為200 μs，梯度差為250 μs，反映在圖上起伏較大，分布較為離散；而采用自適應算法后，過程數據通信時間最大為395 μs，最小為310 μs，梯度差為85 μs，反映在圖上即通信時長基本排布在400 μs左右，分布更加均勻。由此可以看出，在同等條件下，自適應遺傳算法在一個宏周期中，過程數據傳輸的時間梯度較小，分布更均勻，反映在周期調度表上，則信息排布更緊密，從而改善了MVB過程數據的傳送性能，提高了消息數據傳送的有效性。

4 結 語

提出了基于自適應遺傳算法來動態調整參數以優化構建MVB周期調度表，首先對MVB周期調度表的構建問題進行研究，然后提出了該算法應該滿足的約束條件及期望達到的目標值，最后與文獻[9]中的改進遺傳算法進行仿真比較，結果表明，自適應遺傳算法改善了周期信息在各基本周期中的均勻度，調度效果也得到了明顯改善，從而達到了改善MVB通信實時性的目的。