王保華，嚴(yán)　翔，王立德, 王　昕

(1.北京交通大學(xué) 電氣工程學(xué)院，北京　100044；2.中國(guó)鐵道科學(xué)研究院 機(jī)車車輛研究所， 北京　100081)

列車級(jí)別的總線WTB(Wire Train Bus)用于連接動(dòng)態(tài)編組的列車，車輛級(jí)別的總線MVB(Multifunction Vehicle Bus)用于車輛內(nèi)部各設(shè)備之間的連接[1-4]。MVB網(wǎng)絡(luò)采用主從方式對(duì)總線設(shè)備進(jìn)行集中控制，由唯一的總線管理器采用非搶占性的方式，通過(guò)輪詢內(nèi)置的周期掃描表，管理和安排各個(gè)從設(shè)備的通信過(guò)程。

文獻(xiàn)[5]提出了同步的單調(diào)速率(Rate Monotonic，RM)調(diào)度算法，但此方法構(gòu)建的周期掃描表過(guò)于龐大，容易增加系統(tǒng)的開(kāi)銷。文獻(xiàn)[6]在此基礎(chǔ)上做了更為深入地研究，給出了基于約束條件構(gòu)建周期掃描表的RM調(diào)度算法方法，有效地減小了調(diào)度表的規(guī)模。為更好地建立周期掃描表，更加合理地對(duì)MVB網(wǎng)絡(luò)通信過(guò)程進(jìn)行調(diào)度，國(guó)內(nèi)外的研究人員對(duì)RM調(diào)度算法進(jìn)行了優(yōu)化。文獻(xiàn)[7]為了能夠?qū)⒅芷趻呙璞韮?nèi)的負(fù)載均勻分布，提出了混合遺傳優(yōu)化算法，此算法的目標(biāo)是降低周期掃描表的寬度和陡度。文獻(xiàn)[8]采用粒子群算法建立周期掃描表，該算法為了達(dá)到“均衡總體、異化個(gè)體”的目的，選用了多個(gè)優(yōu)化目標(biāo)，但該方法存在出現(xiàn)早熟收斂和陷入局部最優(yōu)的危險(xiǎn)。文獻(xiàn)[9]提出對(duì)于傳輸數(shù)據(jù)量最大的端口，其數(shù)據(jù)傳輸安排在當(dāng)前網(wǎng)絡(luò)負(fù)荷最小的基本周期內(nèi)進(jìn)行，從而實(shí)現(xiàn)周期掃描表中周期變量的均勻分布，達(dá)到負(fù)載均衡的目的；但是此方案只在網(wǎng)絡(luò)負(fù)荷較低的情況下適用，一旦網(wǎng)絡(luò)負(fù)荷增多，將出現(xiàn)最小的基本周期和特征周期不匹配的情形。文獻(xiàn)[10]分析了CRH3型高速動(dòng)車組周期輪詢策略存在總線負(fù)載利用率不均勻和周期負(fù)載占用帶寬相差較大等不足，提出了基于周期掃描表的總線負(fù)載率均勻度優(yōu)化算法，但是該算法的多個(gè)約束條件使得其適用范圍過(guò)小。盡管以上各種算法對(duì)RM調(diào)度算法進(jìn)行了許多優(yōu)化，如有的設(shè)計(jì)了多個(gè)優(yōu)化目標(biāo)，有的則設(shè)置了多個(gè)約束條件，但是也增加了優(yōu)化算法的復(fù)雜程度，限制了它們的推廣應(yīng)用。

本文采用以負(fù)載不均衡度最小為單一目標(biāo)的免疫遺傳算法，建立MVB網(wǎng)絡(luò)周期掃描表，同時(shí)基于預(yù)測(cè)域方法進(jìn)一步降低算法的復(fù)雜度，最后通過(guò)仿真和試驗(yàn)驗(yàn)證算法的可行性。

1　問(wèn)題描述

1.1　MVB周期通信模型

如果MVB網(wǎng)絡(luò)管理著多個(gè)從設(shè)備，假設(shè)在整個(gè)網(wǎng)絡(luò)通信過(guò)程中共有N個(gè)周期信息需要進(jìn)行調(diào)度，那么可將周期信息通信任務(wù)抽象為1個(gè)集合P，為

P={P1，P2，…，PN}

(1)

第i個(gè)周期信息通信任務(wù)Pi為

Pi=(Ti，Li，φi)i∈{1，2，…，N}

(2)

式中：Ti為特征周期，ms；Li為報(bào)文長(zhǎng)度，μs；φi為初相，是第i個(gè)周期信息第1次開(kāi)始通信時(shí)基本周期的編號(hào)。

1.2　傳統(tǒng)周期掃描表構(gòu)建方法的缺陷

MVB網(wǎng)絡(luò)進(jìn)行報(bào)文傳輸時(shí)，在某個(gè)時(shí)刻MVB網(wǎng)絡(luò)主設(shè)備會(huì)發(fā)出1個(gè)主幀，網(wǎng)絡(luò)中某個(gè)從設(shè)備的地址如果恰好匹配此主幀中的目的地址，則會(huì)做出響應(yīng)，發(fā)出1個(gè)從幀。主設(shè)備按照周期掃描表的規(guī)定對(duì)從設(shè)備進(jìn)行依次輪詢。

(1)基本周期Tbp：指MVB網(wǎng)絡(luò)主設(shè)備發(fā)起輪詢的最小單位時(shí)間，為

1 ms≤Tbp≤2.5 ms

(3)

(2)特征周期Tip：指周期信息的數(shù)據(jù)被輪詢1次的時(shí)間，它是基本周期的2λ倍，但按照規(guī)定，特征周期不能大于210倍的基本周期，即不能大于1 024 ms，則

Tip=2λTbpλ∈{0，1，…，10}

(4)

(3)宏周期TMp：指所有特征周期中最長(zhǎng)的那個(gè)，也是周期掃描表的循環(huán)周期，即

TMp=max{Tip}

(5)

(4)負(fù)載率η：指某基本周期內(nèi)K個(gè)有效報(bào)文的總時(shí)間占整個(gè)基本周期的比值，即

(6)

(7)

式中：si為第i個(gè)周期信息的特征周期對(duì)于基本周期的倍數(shù)。

以6個(gè)周期信息的通信任務(wù)(各項(xiàng)參數(shù)見(jiàn)表1)為例，根據(jù)MVB的協(xié)議標(biāo)準(zhǔn)，規(guī)定其主幀的報(bào)文長(zhǎng)度由功能碼決定。采用傳統(tǒng)構(gòu)建周期掃描表的RM調(diào)度算法可以快速生成周期掃描表[5]，結(jié)果見(jiàn)表2。表中：1表示此處某個(gè)周期信息需要發(fā)送數(shù)據(jù)；0表示不發(fā)送。

從表2可以看出：網(wǎng)絡(luò)負(fù)載分配的結(jié)果非常不均勻，負(fù)載率的最大值約為最小值的3倍；若將P5的初相從2調(diào)整為4，將P6的初相從3調(diào)整為8，就能更好地實(shí)現(xiàn)負(fù)載率的均衡分布，由此可以看出初相是決定負(fù)載率均衡分布的關(guān)鍵因素。

表1　周期信息各項(xiàng)參數(shù)

表2　周期掃描表

正如很多文獻(xiàn)中描述的那樣，采用TCN標(biāo)準(zhǔn)推薦的RM調(diào)度算法生成周期掃描表，雖然算法簡(jiǎn)單，但并不能達(dá)到最優(yōu)的結(jié)果，而且隨著報(bào)文長(zhǎng)度的增加，這種不平衡的情況會(huì)更加嚴(yán)重[11]。而且由于目前國(guó)內(nèi)鐵路機(jī)車尤其是動(dòng)車組的列車網(wǎng)絡(luò)中控制設(shè)備較多，網(wǎng)絡(luò)通信負(fù)載較大，采用簡(jiǎn)單的RM調(diào)度算法進(jìn)行周期掃描表的構(gòu)建很難滿足要求，需要研究新算法對(duì)掃描表的構(gòu)建過(guò)程進(jìn)行相應(yīng)的優(yōu)化。

2　優(yōu)化模型及算法構(gòu)建

2.1　基于負(fù)載均衡的優(yōu)化模型

對(duì)于1個(gè)已經(jīng)確定的MVB網(wǎng)絡(luò)，如果周期信息的特征已經(jīng)確定，那么第i個(gè)周期信息Pi的特征周期和報(bào)文長(zhǎng)度也是固定的。由于初相φi是負(fù)載率均衡分布最關(guān)鍵的影響因素，因此所有的初相組成初相向量Φ=(φ1,φ2, …,φN)。如果我們能找到一組初相Φ，使得整個(gè)宏周期內(nèi)的周期信息均勻分布，那么就可以達(dá)到負(fù)載率均衡分布的優(yōu)化目標(biāo)。

當(dāng)1組周期信息參數(shù)給定之后，它們的宏周期就是確定的，且經(jīng)過(guò)計(jì)算所得的平均負(fù)載率也是不變的。此時(shí)，可以將整個(gè)宏周期內(nèi)每個(gè)基本周期的負(fù)載θ作為1組考察數(shù)據(jù)，它們相互之間的波動(dòng)程度可以用這組數(shù)據(jù)的標(biāo)準(zhǔn)差(負(fù)載不均衡度)σ衡量。因此，可以以這個(gè)標(biāo)準(zhǔn)差構(gòu)建優(yōu)化目標(biāo)函數(shù)fEq(Φ)，即

fEq(Φ)=σ(θ1，θ2， …，θk， …，θM)=

(8)

式中：M為基本周期的數(shù)量；k為基本周期的序號(hào);l為周期信息在某個(gè)基本周期內(nèi)的序號(hào)；Lkl為第k個(gè)基本周期內(nèi)第l個(gè)周期信息的長(zhǎng)度；rk為第k個(gè)基本周期內(nèi)有效周期信息的總數(shù)。

由式(8)可以看出：尋找全局最優(yōu)解即尋找1組最優(yōu)初相分配達(dá)到負(fù)載率均衡分布的過(guò)程，進(jìn)一步可以轉(zhuǎn)化為尋找最小的基本周期負(fù)載標(biāo)準(zhǔn)差即負(fù)載不均衡度f(wàn)Eq的過(guò)程。也就是說(shuō)fEq越小，最終生成的周期掃描表可使負(fù)載將更加均衡。這顯然是1個(gè)組合最優(yōu)化的問(wèn)題，并且采用單一的目標(biāo)函數(shù)進(jìn)行優(yōu)化可使算法過(guò)程將更加清晰。為了提高計(jì)算效率，采用改進(jìn)的免疫遺傳算法對(duì)此進(jìn)行求解。

2.2　基于預(yù)測(cè)域的免疫遺傳算法

遺傳算法(Geneitc Algoirthm，GA)提供了1種搜索最優(yōu)解的計(jì)算模型，它具有功能強(qiáng)、魯棒特性好等優(yōu)點(diǎn)，并且計(jì)算簡(jiǎn)單，已被廣泛應(yīng)用于很多領(lǐng)域解決一些實(shí)際問(wèn)題[12-14]。隨著遺傳算法以及粒子群算法等優(yōu)化算法在越來(lái)越多的領(lǐng)域使用，它們的一些缺點(diǎn)也逐漸顯現(xiàn)，例如早熟收斂、過(guò)早陷入局部最優(yōu)等問(wèn)題。為了改進(jìn)算法，Chun等[15]提出了1種免疫遺傳算法(Immune Genetic Algorithms，IGA)，它將免疫理論和基本遺傳算法的優(yōu)點(diǎn)結(jié)合起來(lái)，使得求解過(guò)程類似生物免疫調(diào)節(jié)的過(guò)程，如果抗體的 “濃度”過(guò)高，容易發(fā)生早熟收斂時(shí)，就對(duì)高“濃度”的抗體進(jìn)行抑制。針對(duì)MVB網(wǎng)絡(luò)，單個(gè)抗體為周期信息的1組初相向量，抗體濃度與優(yōu)化目標(biāo)函數(shù)即各個(gè)基本周期負(fù)載的標(biāo)準(zhǔn)差相關(guān)，則第n個(gè)抗體的濃度Cn為

(9)

式中：Q為原抗體群中抗體的數(shù)量；R為抗體的新增數(shù)量。

由式(9)可得抗體的復(fù)制概率Pn為

(10)

根據(jù)式(10)所計(jì)算出的概率對(duì)抗體群中的抗體進(jìn)行選擇復(fù)制，形成新的抗體群,這樣能夠使新抗體群中的抗體保持一定的差異性，從而避免早熟收斂的發(fā)生。

(11)

圖1　預(yù)測(cè)域示意圖

本文在標(biāo)準(zhǔn)免疫遺傳算法的基礎(chǔ)上，引入了以平均負(fù)載率為中心的預(yù)測(cè)域，在確定的范圍內(nèi)有選擇地進(jìn)行族群進(jìn)化，使優(yōu)化目標(biāo)更加明確，使尋找全局最優(yōu)解的過(guò)程更快，大大提高優(yōu)化算法的收斂速度。本文優(yōu)化算法流程如圖2所示。

圖2　本文優(yōu)化算法流程圖

步驟2：抗原呈遞。將ωp和fEq(Φn)共同作為算法的抗原，其中周期相比例ωp的約束條件為

(12)

步驟4：生成首代抗體群。隨機(jī)生成Q個(gè)抗體，由它們組成首代父抗體群X0。

步驟5：計(jì)算親和力。因?yàn)閒Eq(Φn)越小，抗體越好，所以使用B-fEq(Φn)表示抗體和抗原之間的親和力(B為大于零的常量)。計(jì)算過(guò)程中如果發(fā)現(xiàn)精英抗體則存入記憶庫(kù)，否則把親和力最優(yōu)的抗體存入記憶庫(kù)。

步驟6：終止條件判斷。若當(dāng)前抗體群Xu滿足條件，則轉(zhuǎn)步驟10；否則轉(zhuǎn)步驟7。

步驟7：遺傳操作。對(duì)當(dāng)前父抗體群Xu進(jìn)行交叉和變異，其中交叉概率和變異概率預(yù)先設(shè)定。

步驟8：免疫調(diào)節(jié)。重新隨機(jī)生成R個(gè)新的抗體，根據(jù)式(10)的計(jì)算結(jié)果在Q+R中選取Q個(gè)抗體建立中間抗體群Yu。

步驟9：抗體群更新。對(duì)中間抗體群Yu進(jìn)行選擇操作形成新一代的抗體群Xu+1，具體過(guò)程是：將抗體群Yu中較差的抗體剔除，并取出記憶庫(kù)中優(yōu)質(zhì)的抗體加入，然后轉(zhuǎn)步驟5。

步驟10：輸出最優(yōu)初相向量和對(duì)應(yīng)的目標(biāo)函數(shù)值作為最終結(jié)果，算法終止。

3　試驗(yàn)及結(jié)果分析

3.1　仿真驗(yàn)證

使用Matlab軟件，以文獻(xiàn)[7]中的算例對(duì)算法進(jìn)行仿真驗(yàn)證。在此算例中共有20個(gè)源端口的周期信息，它們的各項(xiàng)參數(shù)見(jiàn)表3。特征周期越小的通信任務(wù)越需要優(yōu)先處理，因此依據(jù)特征周期從小到大的順序?qū)χ芷谛畔⑦M(jìn)行排序，若特征周期相等，則按照MVB網(wǎng)絡(luò)功能碼由大至小進(jìn)行排序。

表3　周期信息參數(shù)表

圖3　進(jìn)化過(guò)程

同時(shí)圖3中還給出了遺傳算法和免疫遺傳算法的負(fù)載均衡度進(jìn)化過(guò)程。從圖3可以看出：相較于其他2種算法，本文優(yōu)化算法的收斂速度最快，能夠順利地收斂到全局最優(yōu)解，且沒(méi)有陷入局部最優(yōu)。

表4通過(guò)總線占用率對(duì)3種算法進(jìn)行了對(duì)比分析。從表4可以看出：用RM調(diào)度算法建立的周期掃描表其負(fù)載均衡度是最差的，本文和文獻(xiàn)[7]的優(yōu)化算法都能夠獲得1個(gè)較好的結(jié)果，但本文優(yōu)化算法的收斂速度更快，最優(yōu)解也更優(yōu)。雖然本文算法的復(fù)雜度較RM調(diào)度算法高，但是由于加入了預(yù)測(cè)域的限制，其復(fù)雜度較其他優(yōu)化算法仍降低很多。

表4　總線占用率對(duì)比

3.2　試驗(yàn)驗(yàn)證

為了進(jìn)一步驗(yàn)證本文算法，搭建了基于MVB網(wǎng)絡(luò)的實(shí)時(shí)信息周期負(fù)載率測(cè)試試驗(yàn)平臺(tái)，其拓?fù)浣Y(jié)構(gòu)如圖4所示。其中有1個(gè)主設(shè)備和3個(gè)從設(shè)備，另外還有一個(gè)協(xié)議分析儀，用于實(shí)時(shí)監(jiān)聽(tīng)和采集總線數(shù)據(jù)。

試驗(yàn)中采用與仿真驗(yàn)證同樣的算例， 其4個(gè)主、從設(shè)備的地址及20個(gè)周期信息分別對(duì)應(yīng)的源端口見(jiàn)表5。

圖4　MVB網(wǎng)絡(luò)的實(shí)時(shí)信息周期負(fù)載率測(cè)試試驗(yàn)拓?fù)浣Y(jié)構(gòu)

設(shè)備地址源端口主設(shè)備0x010x10110x30020x40030x00040x1005從設(shè)備10x020x30060x20070x30080x20090x000A從設(shè)備20x030x200B0x100C0x000D0x200E0x000F從設(shè)備30x040x10100x10110x10120x20130x2014

另外，試驗(yàn)設(shè)置基本周期為1 ms，周期相比例ωp為90%，宏周期為32 ms，其他參數(shù)不變。分別用RM調(diào)度算法、文獻(xiàn)[7]優(yōu)化算法以及本文優(yōu)化算法得到周期掃描表后，配置此平臺(tái)下MVB網(wǎng)絡(luò)的參數(shù)，然后進(jìn)行連續(xù)20 min的網(wǎng)絡(luò)通信試驗(yàn)，得到1個(gè)宏周期即0.2 s內(nèi)網(wǎng)絡(luò)負(fù)載率變化的對(duì)比情況，如圖5所示。

圖5　3種優(yōu)化算法的結(jié)果比較

由圖5可以看出：采用RM調(diào)度算法時(shí)MVB網(wǎng)絡(luò)的負(fù)載有很大的波動(dòng)性，即MVB網(wǎng)絡(luò)的負(fù)載均衡度非常差，且當(dāng)網(wǎng)絡(luò)負(fù)荷較高時(shí)很容易出現(xiàn)數(shù)據(jù)丟包以及網(wǎng)絡(luò)不可調(diào)度的狀況；采用文獻(xiàn)[7]優(yōu)化算法和本文算法時(shí)結(jié)果均好，而且采用本文算法得到的結(jié)果相對(duì)更加穩(wěn)定，對(duì)于承載更多的網(wǎng)絡(luò)負(fù)荷有很大幫助，試驗(yàn)結(jié)果與仿真結(jié)果一致，證明了本文算法的有效性。

4　結(jié)　語(yǔ)

研究和分析了用RM調(diào)度算法構(gòu)建周期掃描表的方法，發(fā)現(xiàn)其很難實(shí)現(xiàn)負(fù)載均衡分配，對(duì)MVB通信性能產(chǎn)生較大的影響。本文將負(fù)載不均衡度最小作為單一的優(yōu)化目標(biāo)建立優(yōu)化模型，再采用基于預(yù)測(cè)域的免疫遺傳算法進(jìn)行全局最優(yōu)求解。算例的仿真和試驗(yàn)結(jié)果表明，本文優(yōu)化算法能夠更快地收斂到全局最優(yōu)解，使MVB網(wǎng)絡(luò)負(fù)載的均衡，從而有利于基于MVB的列車控制網(wǎng)絡(luò)容納更多的子系統(tǒng)，提升系統(tǒng)的服務(wù)指標(biāo)。

[1]JIMENEZ J, MARTIN J L, ZULOAGA A, et al.Comparison of Two Designs for the Multifunction Vehicle Bus[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 25(5): 797-805.

[2]UNZUETA H, JIMENEZ J, MARTIN J L, et al. An Emulator to Develop the Wire Train Bus Protocol Stack [C]//IECON 2006-2nd Annual Conference on IEEE Industrial Electronics.Paris:IEEE, 2006: 4225-4230.

[3]IEC. IEC61375-1 Electric Railway Equipment Train Bus Part1: Train Communication Network[S]. Geneva: IEC, 1999.

[4]JIMENEZ J, MARTIN J L, BIDARTE U, et al. Design of a Master Device for the Multifunction Vehicle Bus[J]. IEEE Transactions on Vehicular Technology, 2007, 56(6): 3695-3708.

[5]朱琴躍, 謝維達(dá), 譚喜堂,等. MVB周期信息的實(shí)時(shí)調(diào)度[J]. 計(jì)算機(jī)應(yīng)用, 2007, 27(12): 3108-3111, 3115.

(ZHU Qinyue, XIE Weida, TAN Xitang, et al. Real-Time Scheduling of Periodic Messages for MVB[J]. Computer Application, 2007, 27(12): 3108-3111, 3115. in Chinese)

[6]聶曉波. 列車控制網(wǎng)絡(luò)實(shí)時(shí)性能分析及調(diào)度策略研究[D]. 北京: 北京交通大學(xué), 2011.

(NIE Xiaobo. Analysis and Real-Time Scheduling Policy Research Performance Train Control Network[D]. Beijing: Beijing Jiaotong University, 2011. in Chinese)

[7]王永翔, 王立德. 多功能車輛總線周期掃描表的最優(yōu)化設(shè)計(jì)[J]. 鐵道學(xué)報(bào), 2009, 31(6): 46-52.

(WANG Yongxiang, WANG Lide. The Optimization Method of the MVB Period Polling Table[J]. Journal of the China Railway Society, 2009, 31(6): 46-52. in Chinese)

[8]陳佳凱, 韋巍. 基于多目標(biāo)粒子群優(yōu)化的多功能車輛總線周期性掃描表的優(yōu)化[J]. 鐵道學(xué)報(bào), 2012, 34(11): 60-66.

(CHEN Jiakai, WEI Wei. Optimization of the MVB Period Polling Table Based on Multi-Objective Particle Swarm Optimization[J]. Journal of the China Railway Society, 2012, 34(11): 60-66. in Chinese)

[9]李銳, 李永宗, 費(fèi)巧玲，等. 一種多功能車輛總線周期掃描表優(yōu)化設(shè)計(jì)方案[J]. 機(jī)車電傳動(dòng), 2013 (4): 92-94.

(LI Rui, LI Yongzong, FEI Qiaoling, et al. An Optimization Solution of the MVB Periodic Polling Table[J]. Electric Drive for Locomotives, 2013 (4): 92-94. in Chinese)

[10]郭超勇, 劉建強(qiáng), 鄭瓊林，等. 350 km/h動(dòng)車組TCN網(wǎng)絡(luò)周期輪詢優(yōu)化算法研究[J]. 鐵道學(xué)報(bào), 2011, 33(12): 46-50.

(GUO Chaoyong, LIU Jianqiang, ZHENG Qionglin, et al. Research on the TCN Network Periodic Polling Optimization Algorithm for the 350 km/h Electrical Multiple Units[J]. Journal of the China Railway Society, 2011, 33(12): 46-50. in Chinese)

[11]王濤, 王立德, 周潔瓊，等. MVB網(wǎng)絡(luò)周期輪詢算法優(yōu)化與仿真研究[J]. 機(jī)車電傳動(dòng), 2013 (6): 40-45.

(WANG Tao, WANG Lide, ZHOU Jieqiong, et al. Cycle Polling Algorithm Optimization and Simulation Research of MVB Network[J]. Electric Drive for Locomotives, 2013 (6): 40-45. in Chinese)

[12]WHITLEY D. A Genetic Algorithm Tutorial[J]. Statistics and Computing， 1994, 4(2): 65-85.

[13]DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

[14]PETEGHEMA V V, VANHOUCKEA M. A Genetic Algorithm for the Preemptive and Non-Preemptive Multi-Mode Resource-Constrained Project Scheduling Problem[J]. European Journal of Operational Research, 2010, 201(2): 409-418.

[15]CHUN J S, KIM M K, JUNG H K, et al. Shape Optimization of Electromagnetic Devices Using Immune Algorithm[J]. IEEE Transactions on Magnetics, 1997, 33(2): 1876-1879.