基于負載均衡的MVB周期數(shù)據(jù)調(diào)度優(yōu)化

王保華，嚴　翔，王立德, 王　昕

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

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

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

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

1　問題描述

1.1　MVB周期通信模型

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

P={P1，P2，…，PN}

(1)

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

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

(2)

式中：Ti為特征周期，ms；Li為報文長度，μs；φi為初相，是第i個周期信息第1次開始通信時基本周期的編號。

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

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

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

1 ms≤Tbp≤2.5 ms

(3)

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

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

(4)

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

TMp=max{Tip}

(5)

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

(6)

(7)

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

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

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

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

表2　周期掃描表

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

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

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

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

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

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

(8)

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

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

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

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

(9)

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

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

(10)

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

(11)

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

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

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

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

(12)

步驟4：生成首代抗體群。隨機生成Q個抗體，由它們組成首代父抗體群X0。

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

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

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

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

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

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

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

3.1　仿真驗證

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

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

圖3　進化過程

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

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

表4　總線占用率對比

3.2　試驗驗證

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

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

圖4　MVB網(wǎng)絡(luò)的實時信息周期負載率測試試驗拓撲結(jié)構(gòu)

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

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

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

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

4　結(jié)　語

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

[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]朱琴躍, 謝維達, 譚喜堂,等. MVB周期信息的實時調(diào)度[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ò)實時性能分析及調(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]. 鐵道學(xué)報, 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]陳佳凱, 韋巍. 基于多目標粒子群優(yōu)化的多功能車輛總線周期性掃描表的優(yōu)化[J]. 鐵道學(xué)報, 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]李銳, 李永宗, 費巧玲，等. 一種多功能車輛總線周期掃描表優(yōu)化設(shè)計方案[J]. 機車電傳動, 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]郭超勇, 劉建強, 鄭瓊林，等. 350 km/h動車組TCN網(wǎng)絡(luò)周期輪詢優(yōu)化算法研究[J]. 鐵道學(xué)報, 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]. 機車電傳動, 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.