基于自適應(yīng)改進(jìn)遺傳算法的MVB周期調(diào)度表優(yōu)化

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

(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長(zhǎng)春 130012)

0 引 言

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

為了更智能地調(diào)整算法控制參數(shù)來(lái)處理離散信息調(diào)度問(wèn)題，文中提出一種基于自適應(yīng)改進(jìn)遺傳算法的MVB周期信息實(shí)時(shí)調(diào)度算法，對(duì)周期調(diào)度表進(jìn)行優(yōu)化，然后根據(jù)約束條件及優(yōu)化目標(biāo)對(duì)周期調(diào)度表的寬度和梯度等參數(shù)進(jìn)行調(diào)整，以達(dá)到均勻傳輸信息、提高實(shí)時(shí)性的目的。

1 MVB網(wǎng)絡(luò)的通信原理

MVB通過(guò)網(wǎng)絡(luò)中唯一的主設(shè)備進(jìn)行集中式實(shí)時(shí)調(diào)度管理來(lái)完成過(guò)程數(shù)據(jù)和消息數(shù)據(jù)兩類信息的傳輸，其中過(guò)程數(shù)據(jù)為周期信息。主設(shè)備首先廣播發(fā)送過(guò)程數(shù)據(jù)請(qǐng)求主幀，接收主幀后，與主幀中邏輯端口地址相同的源設(shè)備發(fā)送響應(yīng)從幀，主設(shè)備接收從幀后開(kāi)始發(fā)送數(shù)據(jù)，以此完成一次周期信息的傳輸。因此，源設(shè)備周期數(shù)據(jù)報(bào)文發(fā)送的先后次序是由主幀的排列次序決定的。對(duì)周期數(shù)據(jù)調(diào)度的優(yōu)化，實(shí)際上就是對(duì)周期掃描表的優(yōu)化。MVB周期信息通信過(guò)程如圖1所示。

圖1 MVB周期信息通信過(guò)程

1.1 特征周期

在MVB網(wǎng)絡(luò)中，同一節(jié)點(diǎn)的兩個(gè)連續(xù)輪詢之間的時(shí)間間隔叫做特征周期，用T_ip表示:

T_ip=2n×T_bp

(1)

一般地，基本周期為1 ms，最長(zhǎng)的特征周期不得超過(guò)1 024 ms。

1.2 周期調(diào)度表

周期掃描表本質(zhì)上是一個(gè)宏循環(huán)的每個(gè)周期里要輪詢的節(jié)點(diǎn)、地址及設(shè)備表。宏循環(huán)為一個(gè)宏周期中包含的基本周期數(shù)，而宏周期為最長(zhǎng)的特征周期。

在構(gòu)建周期調(diào)度表時(shí)，一個(gè)宏循環(huán)由一個(gè)宏周期內(nèi)的所有循環(huán)組成，一個(gè)循環(huán)將相同特征周期的周期信息編為一組，組名用n表示；同時(shí)，一個(gè)循環(huán)可分為若干個(gè)由多個(gè)基本周期組成的子循環(huán)。

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

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

(2)

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

(3)

式中：n——周期變量;

λi——周期級(jí)別;

length(i)——第i個(gè)基本周期內(nèi)周期相長(zhǎng)度。

基于此，假設(shè)一個(gè)包含30個(gè)循環(huán)的宏循環(huán)的周期數(shù)據(jù)，其中有7個(gè)周期變量

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

其特征周期級(jí)別分別為

截取前8個(gè)循環(huán)得到的周期掃描表如圖2所示。

圖2 按協(xié)議生成的前8個(gè)循環(huán)的周期掃描表

2 算法設(shè)計(jì)

由于MVB周期信息在一個(gè)宏周期中，會(huì)隨機(jī)傳輸各種時(shí)間長(zhǎng)度不同的數(shù)據(jù)。在基本遺傳算法的基礎(chǔ)上，基于遺傳算法的自適應(yīng)機(jī)制[10]能夠動(dòng)態(tài)調(diào)整策略參數(shù)，即需要處理的MVB周期信息集；該機(jī)制使MVB周期信息集能對(duì)進(jìn)化過(guò)程中事先難以預(yù)料的細(xì)節(jié)產(chǎn)生反應(yīng)，適應(yīng)在各個(gè)階段的不同環(huán)境，從而更靈活地將長(zhǎng)度合適的周期信息排列在調(diào)度表中。在遺傳進(jìn)化過(guò)程中，需調(diào)度的周期信息集以某種方式動(dòng)態(tài)地獲取和利用關(guān)于問(wèn)題的規(guī)律性知識(shí)，進(jìn)行群體的自動(dòng)學(xué)習(xí)，完成周期調(diào)度表的排布，以達(dá)到均勻傳輸信息、提高實(shí)時(shí)性的目的。

2.1 約束條件

IEC61375-1標(biāo)準(zhǔn)中給出了以下約束條件：

1)所有周期信息傳輸?shù)目倳r(shí)間在一個(gè)基本周期內(nèi)應(yīng)小于周期相所占時(shí)間。

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

3)過(guò)程數(shù)據(jù)的主幀長(zhǎng)度固定為33位，從幀長(zhǎng)度有5種類型，分別為33、49、81、153、297位；過(guò)程數(shù)據(jù)傳輸?shù)臅r(shí)間為：

(4)

式中：Nmaster——主幀長(zhǎng)度；

Nslave——從幀長(zhǎng)度；

VMVB——信號(hào)速率，其值取1.5 Mbit/s；

Treply——主幀發(fā)出后到響應(yīng)該主幀的從幀發(fā)出的時(shí)間間隔；

Tsm——兩個(gè)報(bào)文之間的傳輸間隔。

2.2 優(yōu)化目標(biāo)

IEC61375-1標(biāo)準(zhǔn)中要求周期信息均勻分布，則可根據(jù)最大周期相和最短周期相的時(shí)間計(jì)算標(biāo)準(zhǔn)差：

(5)

(6)

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

tave——周期相的平均值；

Nλ——特征級(jí)別為λ的端口數(shù)目；

ti——第i個(gè)周期相的時(shí)間。

2.3 算法流程

從第一個(gè)周期和以第一個(gè)宏周期開(kāi)始，步驟如下：

1)明確實(shí)際問(wèn)題參數(shù)集及約束條件；

2)選擇編碼策略，對(duì)需要調(diào)度的周期信息集進(jìn)行編碼；

3)確定優(yōu)化目標(biāo)；

4)判斷第i個(gè)周期能否發(fā)送信息，若不能，則信息不能放在第i個(gè)周期，若能，則進(jìn)行下一步；

5)判斷能夠發(fā)送的信息是否在周期相內(nèi)，不能則該信息不被調(diào)度，能則將信息安排在調(diào)度表中；

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

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

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

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

圖3 采用自適應(yīng)遺傳算法構(gòu)成MVB周期調(diào)度表的流程

3 仿真分析

為了驗(yàn)證該算法對(duì)生成MVB周期調(diào)度表這一實(shí)際問(wèn)題的有效性，在滿足IEC61375-1標(biāo)準(zhǔn)的基礎(chǔ)上，與文獻(xiàn)[9]中運(yùn)用的改進(jìn)差分算法進(jìn)行仿真對(duì)比，周期變量配置如1.2中所示。采用自適應(yīng)方法生成的前8個(gè)循環(huán)的周期掃描表如圖4所示。

對(duì)比圖2和圖4可以發(fā)現(xiàn)，采用自適應(yīng)算法后的周期掃描表，周期調(diào)度表的梯度小，周期變量排布更均勻。

采用改進(jìn)差分算法和自適應(yīng)遺傳算法傳輸周期信息在一個(gè)宏周期中過(guò)程數(shù)據(jù)通信時(shí)長(zhǎng)的分布如圖5所示。

圖4 采用自適應(yīng)遺傳算法生成的前8個(gè)循環(huán)的周期掃描表

圖5 兩種算法的過(guò)程數(shù)據(jù)通信時(shí)長(zhǎng)

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

4 結(jié) 語(yǔ)

提出了基于自適應(yīng)遺傳算法來(lái)動(dòng)態(tài)調(diào)整參數(shù)以優(yōu)化構(gòu)建MVB周期調(diào)度表，首先對(duì)MVB周期調(diào)度表的構(gòu)建問(wèn)題進(jìn)行研究，然后提出了該算法應(yīng)該滿足的約束條件及期望達(dá)到的目標(biāo)值，最后與文獻(xiàn)[9]中的改進(jìn)遺傳算法進(jìn)行仿真比較，結(jié)果表明，自適應(yīng)遺傳算法改善了周期信息在各基本周期中的均勻度，調(diào)度效果也得到了明顯改善，從而達(dá)到了改善MVB通信實(shí)時(shí)性的目的。