范 超， 于 躍,2， 顧 宏*

( 1.大連理工大學(xué) 控制科學(xué)與工程學(xué)院, 遼寧 大連 116024；2.北車大連電力牽引研發(fā)中心有限公司， 遼寧 大連 116045 )

電子與信息工程、管理工程

基于Pareto蟻群算法的MVB周期輪詢表優(yōu)化設(shè)計

范 超1， 于 躍1,2， 顧 宏*1

( 1.大連理工大學(xué) 控制科學(xué)與工程學(xué)院, 遼寧 大連 116024；2.北車大連電力牽引研發(fā)中心有限公司， 遼寧 大連 116045 )

合理的多功能車輛總線(MVB)周期輪詢表有助于均衡網(wǎng)絡(luò)負荷、提高網(wǎng)絡(luò)處理偶發(fā)信息的能力、保證實時通信的可靠性．為此提出一種有效的輪詢表設(shè)計方法．將MVB周期輪詢表的設(shè)計抽象成離散優(yōu)化問題，根據(jù)IEC 61375-1國際標準和可調(diào)度性要求建立約束條件，將均勻度和相鄰基本周期時間差作為優(yōu)化目標，利用Pareto蟻群(Pareto ant colony，P-AC)算法求解．每個優(yōu)化目標對應(yīng)自己的信息素，信息素采用蟻群系統(tǒng)的規(guī)則更新，總信息素由兩者加權(quán)得到，非劣解基于擁擠距離方法維護．與已有的優(yōu)化算法相比，Pareto蟻群算法優(yōu)化得到的輪詢表均勻度更好，能夠更有效地均衡網(wǎng)絡(luò)負荷．

Pareto蟻群算法；多功能車輛總線(MVB)；周期輪詢表

0 引 言

多功能車輛總線(MVB)是車廂級總線，連接廂內(nèi)設(shè)備以構(gòu)成局域網(wǎng)．每個設(shè)備可以有多個端口，MVB在運行前需要人為配置端口參數(shù)，技術(shù)人員根據(jù)參數(shù)設(shè)計周期輪詢表，運行時主設(shè)備按照輪詢表讀取從設(shè)備信息．國內(nèi)外學(xué)者對列車周期輪詢表優(yōu)化構(gòu)建問題做了卓有成效的研究．文獻[1]利用最長報文填最短基本周期的思路提高表的均勻度；當給定數(shù)據(jù)無法編排時，文獻[2]給出一種調(diào)整特征周期的方法；文獻[3-5]利用遺傳算法、多目標粒子群優(yōu)化(multi-objective particle swarm optimization，MPSO)算法和蟻群算法(ant colony algorithm，AC)，根據(jù)各自提出的優(yōu)化指標建立周期輪詢表．但是文獻[3]的多目標粒子群優(yōu)化算法更適用于連續(xù)問題，處理離散問題的調(diào)度優(yōu)化需要不斷取整，存在缺陷；文獻[4]的蟻群算法雖然更適合離散問題，但是優(yōu)化目標單一，對具體的通信指標無法兼顧．為解決已有算法的眾多缺點，本文通過建模將Pareto蟻群算法應(yīng)用到周期輪詢表的優(yōu)化，引入時間梯度概念，表示最長周期與最短周期時間差，時間梯度與基本周期的周期相方差加權(quán)求和表示均勻度．將均勻度作為第一個優(yōu)化目標，相鄰基本周期時間差作為第二個優(yōu)化目標，利用Pareto蟻群算法求解．

1 MVB通信規(guī)則

MVB主設(shè)備將時間軸劃分成固定長度時間片，這里的固定長度就是基本周期，用Tbp表示，是最小調(diào)度粒度，這能保證實時變量確定的響應(yīng)時間．基本周期取值范圍為1.0 ms≤Tbp≤2.5 ms，本文中Tbp=1.0 ms．

特征周期指周期變量被輪詢的時間間隔，用Tip表示(i是周期信息編號)，規(guī)定特征周期是基本周期的2λi倍，但不超過1 024倍，λi表示特征周期級別．

Tip=2λiTbp;λi∈{0,1,…,10}

(1)

宏周期是最大的特征周期，用Tmacro表示，即Tmacro=max {Tip}．宏周期包含基本周期，數(shù)目為M=Tmacro/Tbp．

一個基本周期包括周期相、監(jiān)視相、事件相和保護相，后三相合稱為偶發(fā)相[1]．主設(shè)備在周期相中遵照所設(shè)計的輪詢表對周期數(shù)據(jù)輪詢，監(jiān)視相中主設(shè)備進行設(shè)備掃描和主權(quán)傳遞，事件相處理突發(fā)報文．不同的基本周期可以有不同的偶發(fā)時間，其缺省值為350 μs．

MVB采用主-從工作方式，主幀長度固定為33 bit，從幀F(xiàn)碼對應(yīng)5種長度：33,49,81,153,297 bit，考慮到時間延遲tms和tsm，MVB完成一次報文傳輸需要的時間為

(2)

MVB通信速率v為1.5 Mbit/s, 由式(2)可以計算每次通信的時長．

2 周期輪詢表問題描述與模型建立

2.1 任務(wù)描述

考慮對N個周期變量編排，每個周期變量可以表示為

Ci={Tip，F(xiàn)i，Li}；i∈{1，2，…，N}

(3)

式中：Tip是第i個變量的特征周期；Fi是功能碼，取值為0，1，2，3，4，依次對應(yīng)5個從幀長度，通過從幀長度求出完成一次報文傳輸時間tmmi；Li為周期變量首次在輪詢表中出現(xiàn)的基本周期編號，本文的目的就是確定每個設(shè)備的Li．

2.2 約束條件

(1)最大周期相約束．每個基本周期中，周期相所占時間有一定限制，需要留出一定時間完成監(jiān)視任務(wù)和處理突發(fā)消息．用k表示周期相在一個基本周期所占比例：

(4)

(2)可調(diào)度性條件．周期信息的截止期等于其特征周期，可調(diào)度性要求響應(yīng)時間不大于截止期[6]，所以端口首次在輪詢表中出現(xiàn)的時間不大于其特征周期，即

Li≤Tip

(5)

2.3 優(yōu)化目標

IEC61375-1標準要求周期信息均勻分布，一個重要指標是基本周期周期相的標準差

(6)

(7)

定義時間梯度為輪詢表最長周期相和最短周期相之差，用Tgrad表示，用ttotal(i)表示第i個基本周期內(nèi)周期相長度，則有

Tgrad=max {ttotal(i)}-min {ttotal(i)}

(8)

Var、Tgrad越小效果越好，利用它們加權(quán)作為第一個優(yōu)化目標以更全面地表達均勻度要求，用Fit1表示為

Fit1=Var+xTgrad

(9)

為提高網(wǎng)絡(luò)對偶發(fā)相處理能力，在保證均勻度的基礎(chǔ)上，擴大相鄰基本周期的平均時間差[3]， 此度量用Tdiff表示為

(10)

當均勻度相同時，Tdiff越大表明該編排越能將長周期和短周期更好地錯開．長周期剩余時間少，短周期剩余時間多，若突發(fā)消息在長周期剩余時間無法處理完，在短周期里有足夠剩余時間處理，這提高了對偶發(fā)相的處理能力，所以Tdiff越大效果越好．構(gòu)造第二個優(yōu)化目標Fit2為

Fit2=y(Tmax-Tdiff)

(11)

其中y表征兩個優(yōu)化目標的相對重要性，一般y<0.1．

因為比較Tdiff指標的前提是均勻度相同，當均勻度不同時不能通過簡單比較Tdiff來判斷某個解的性能．由此引入相對指標用于評價解的性能表現(xiàn)，表達式為

(12)

Relative_diff越大，認為均勻度相同時相鄰周期的時間差異越大，說明網(wǎng)絡(luò)處理偶發(fā)消息的能力越強，性能也就越好．

3 基于Pareto蟻群算法建立周期輪詢表

3.1 Pareto蟻群算法

蟻群算法利用群體合作和正反饋機制搜索解空間，不易陷入局部最優(yōu)，在離散的優(yōu)化調(diào)度問題上尋優(yōu)效果好．蟻群系統(tǒng)(antcolonysystem，ACS)算法[7-8]相比基本蟻群算法和其他改進算法，其全局搜索能力更強．本文的Pareto蟻群算法是在蟻群系統(tǒng)算法的基礎(chǔ)上添加規(guī)則提出的，能用于多目標優(yōu)化問題[9]．

蟻群系統(tǒng)算法先利用最近鄰思想[2]構(gòu)造初始游歷，其適應(yīng)值為f0，則信息素增強系數(shù)

(13)

信息素矩陣各元素初始化值為Q．螞蟻從第i個節(jié)點選擇第k條路徑走到第i+1個節(jié)點的概率為

(14)

式中：τi,i+1為信息素強度，ηi,i+1為啟發(fā)函數(shù)，α為信息啟發(fā)因子，β為期望啟發(fā)因子．由式(5)得第i個節(jié)點可選擇路徑有Tip條，則啟發(fā)函數(shù)表示為

ηi,i+1=1/Tip

(15)

求得每條備選路徑概率后，利用輪盤賭方式選擇下一條路徑．

蟻群系統(tǒng)算法的信息素更新規(guī)則包括局部更新和全局更新，如

(16)

(17)

式中：ρ1、ρ2為信息素揮發(fā)系數(shù)，fb表示最優(yōu)路徑的適應(yīng)值．螞蟻每走一步，都利用局部更新規(guī)則更新信息素；當所有螞蟻遍歷結(jié)束，對全局最優(yōu)的路徑利用全局更新規(guī)則更新信息素．

Pareto蟻群算法包含F(xiàn)it1和Fit2兩個目標，兩個目標對應(yīng)信息素τ1和τ2，根據(jù)上述規(guī)則獨立維護各自的信息素，路徑上總的信息素由τ1和τ2加權(quán)得到：

τ=pτ1+(1-p)τ2

(18)

其中p體現(xiàn)兩個目標的重要程度，考慮到Fit1為主要目標，取p>0.7．

蟻群算法與研究問題建立如圖1所示的對應(yīng)關(guān)系[4]，圖中每個端口對應(yīng)一個節(jié)點，螞蟻只準從起點依次經(jīng)過各個節(jié)點最后到達端口N．由式(5)得從第i-1個節(jié)點走到第i個節(jié)點可選擇路徑有Tip條，如果選擇第k條路徑則表示第i個端口在輪詢表中首次出現(xiàn)的特征周期編號為k．每只螞蟻走完一遍就會生成一個解向量，每個解向量對應(yīng)一個輪詢表．利用Pareto蟻群算法搜索解空間，就可以得到性能優(yōu)越的非劣解．

圖1 周期輪詢表的蟻群算法Fig.1 The ant colony algorithm of period polling table

3.2 非劣解維護

假設(shè)解A的兩個適應(yīng)值都小于解B的適應(yīng)值，稱A支配B，否則B不受A支配．不受任何解支配的解，稱之為非劣解．

多目標優(yōu)化問題一般沒有絕對的最優(yōu)解，本文的目標是找出非劣解的集合形成Pareto沿．假設(shè)解集的容納量為Num_nd，當?shù)玫降姆橇咏鈹?shù)目過多，需要根據(jù)規(guī)則剔除一部分．非劣解集基于擁擠距離[10]來維護，擁擠距離表征該解周圍其他解分布的密集程度，點的擁擠距離越小，說明該點周圍的解分布越密集，該解被剔除的概率越大．擁擠距離的計算如下：

針對每一個優(yōu)化目標m

根據(jù)適應(yīng)值升序排序，S=sort(S,m)

fori=2 to (Num_nd-1)S[i].distance=S[i].distance+(S[i+1].m-S[i-1].m)

對于邊界點，S[1].distance=S[Num_nd].distance=maximumdistance

獲得Pareto沿后，根據(jù)下列式子計算沿上每一個點的評價指數(shù)ψ：

ψ=0.75Fit1+0.25Fit2

(19)

其中ψ包含了各個指標的信息，將其升序排列，從前3個點中隨機選擇一個，該點對應(yīng)的向量L即為最終解，最后以此為依據(jù)建立周期輪詢表．

綜上所述，利用Pareto蟻群算法優(yōu)化MVB周期輪詢表的流程如圖2所示．

圖2 Pareto蟻群算法流程圖Fig.2 Flow chart of the P-AC algorithm

4 方法比較與結(jié)果分析

基于文獻[3]和[4]的實驗數(shù)據(jù)，將本文算法與已經(jīng)提出的蟻群算法和多目標粒子群優(yōu)化算法進行比較．Pareto蟻群算法的參數(shù)設(shè)定：α=1，β=2，ρ1=0.05，ρ2=0.10，螞蟻數(shù)目為10，信息素增強系數(shù)由式(13)求得，非劣解集容納量為24，程序迭代200次．

文獻[3]的設(shè)備信息數(shù)據(jù)如表1所示，式(4)中k=75%，利用文獻[3]的多目標粒子群優(yōu)化算法得到的解向量為(2 2 1 2 2 4 3 1 6 3 6 1 5 16 3 3 4 16 13 1 9 11 7 23)．利用本文的Pareto蟻群算法仿真生成的非劣解如圖3所示．根據(jù)式(19)計算排序，最終選取的解向量為(2 1 2 2 4 4 3 1 7 7 6 2 1 7 14 11 2 10 11 3 13 5 1 15)．兩種算法的評價參數(shù)見表2．

表1 文獻[3]的設(shè)備信息表Tab.1 Device information list of Lit. [3]

圖3 Pareto蟻群算法基于表1產(chǎn)生的非劣解Fig.3 Non-dominated solutions created by P-AC algorithm based on Tab. 1

表2 標準解性能指標Tab.2 Performance indicators of the standard solutions

由表2可得，Pareto蟻群算法得到解的標準差是67.79，遠小于多目標粒子群優(yōu)化算法的115.75；其Tgrad指標是236.00，同樣遠小于多目標粒子群優(yōu)化算法的376.00，說明本文算法能保證各基本周期波動小，在均勻度上的表現(xiàn)更好．Pareto蟻群算法的Relative_diff為1.48，而多目標粒子群優(yōu)化算法的僅為1.42，說明Pareto蟻群算法得到的解能更好地將長短周期錯開，提高網(wǎng)絡(luò)處理偶發(fā)消息的能力．因為Pareto蟻群算法較多目標粒子群優(yōu)化算法更適合處理離散優(yōu)化問題，所以它的結(jié)果表現(xiàn)更優(yōu)秀．

圖4是兩種算法解的周期相利用率分布．Pareto 蟻群輪詢表最大利用率為97%，較小的也在70%以上，分布集中；而多目標粒子群優(yōu)化算法對應(yīng)表最大利用率為100%，還有多個周期低于65%，分布零散．對比發(fā)現(xiàn)，Pareto蟻群算法構(gòu)建的周期輪詢表中各周期相波動較小，均勻度更好，利用率更接近平均值，這樣的周期輪詢表能夠更好地均衡網(wǎng)絡(luò)負荷，預(yù)防局部通信壓力過大．

(a) 多目標粒子群優(yōu)化算法周期相時間散點圖

(b) Pareto蟻群算法周期相時間散點圖

圖4 Pareto蟻群算法與多目標粒子群優(yōu)化算法的周期相利用率比較

Fig.4 Comparison of cycle phase utilization between P-AC and MPSO algorithms

文獻[4]的設(shè)備信息數(shù)據(jù)如表3所示，式(4)中k=65%，利用文獻[4]的蟻群算法得到的向量為(1 1 1 3 3 2 4 4 3 6 7 5 5 4 6 1 8 10 2 10)．利用Pareto蟻群算法仿真生成的Pareto沿如圖5所示．根據(jù)式(19)計算排序，最終選取的解向量為(1 1 2 1 4 2 3 4 2 4 7 1 7 5 3 6 4 8 5 18)．表4列出對應(yīng)參數(shù)指標．

表3 文獻[4]的設(shè)備信息表Tab.3 Device information list of Lit. [4]

圖5 Pareto蟻群算法基于表3產(chǎn)生的非劣解

Fig.5 Non-dominated solutions created by P-AC algorithm based on Tab.3

表4 兩個解的性能指標Tab.4 Performance indicators of the two solutions

由表4可得，Pareto蟻群算法對應(yīng)的標準差和Tgrad分別為57.89和265.00，明顯小于基本蟻群算法的，充分證明Pareto蟻群算法能更好地保證輪詢表的均勻度；Pareto蟻群算法的Relative_diff為1.22，大于基本蟻群算法的0.97，證明其能夠更有效地錯開長短周期，均衡網(wǎng)絡(luò)負荷．

圖6是兩種算法解的周期相利用率分布．Pareto 蟻群算法對應(yīng)輪詢表的利用率只有一個超過85%，利用率在70%以下的僅有5個周期；基本蟻群算法輪詢表的利用率跨度很大，最大已經(jīng)達到100%，利用率在70%以下的很多，對比可知Pareto蟻群算法均衡網(wǎng)絡(luò)負荷能力更強．

(a) 基本蟻群算法周期相時間散點圖

(b) Pareto蟻群算法周期相時間散點圖

圖6 Pareto蟻群算法與基本蟻群算法的周期相利用率比較

Fig.6 Comparison of cycle phase utilization between P-AC and AC algorithms

5 結(jié) 語

在IEC 61375-1標準的基礎(chǔ)上，構(gòu)造出兩個優(yōu)化目標，這樣既能優(yōu)化均勻度，又能夠保證將長短周期錯開，全面提高輪詢表質(zhì)量．在此基礎(chǔ)上建立模型并利用Pareto蟻群算法求解．比較證明，本文算法得到的解的性能比基本蟻群算法和多目標粒子群優(yōu)化算法得到的解的性能更好，證明了利用本文算法構(gòu)建MVB周期輪詢表，更有助于MVB均衡網(wǎng)絡(luò)負荷，提高網(wǎng)絡(luò)處理偶發(fā)信息的能力，保證實時通信．

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

LI Rui, LI Yong-zong, FEI Qiao-ling,etal. An optimization solution of the MVB periodic polling table [J]. Electric Drive for Locomotives, 2013(4):92-94. (in Chinese)

[2]蔣 瑾,王長林. 多功能車輛總線MVB周期掃描表配置分析[J]. 鐵道機車車輛, 2011, 31(3):34-36.

JIANG Jin, WANG Chang-lin. Analysis on periodic polling table configuration of multifunction vehicle bus MVB [J]. Railway Locomotive & Car, 2011, 31(3):34-36. (in Chinese)

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

CHEN Jia-kai, 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)

[4]朱 俊,李 芳,王麗芳. 基于蟻群算法的多功能車輛周期掃描表的優(yōu)化設(shè)計[J]. 鐵道學(xué)報, 2013, 35(7):57-62.

ZHU Jun, LI Fang, WANG Li-fang. Optimized design method of periodic list in multifunction vehicle bus based on the ant colony algorithm [J]. Journal of the China Railway Society, 2013, 35(7):57-62. (in Chinese)

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

WANG Yong-xiang, WANG Li-de. The optimization method of the MVB period polling table [J]. Journal of the China Railway Society, 2009, 31(6):46-52. (in Chinese)

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

ZHU Qin-yue, XIE Wei-da, TAN Xi-tang,etal. Real-time scheduling of periodic messages for MVB [J]. Computer Applications, 2007, 27(12):3108-3111. (in Chinese)

[7]Dorigo M, Gambardella L M. Ant colony system:a cooperative learning approach to the traveling salesman problem [J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1):53-66.

[8]李士勇,陳永強,李 研. 蟻群算法及其應(yīng)用[M]. 哈爾濱:哈爾濱工業(yè)大學(xué)出版社, 2004:29-40.

LI Shi-yong, CHEN Yong-qiang, LI Yan. Ant Colony Algorithms with Applications [M]. Harbin:Harbin Institute of Technology Press, 2004:29-40. (in Chinese)

[9]Doerner K F, Gutjahr W J, Hartl R F,etal. Pareto ant colony optimization with ILP preprocessing in multiobjective project portfolio selection [J]. European Journal of Operational Research, 2006, 171(3):830-841.

[10]Raquel C R, Naval P C Jr. An effective use of crowding distance in multiobjective particle swarm optimization [C] // GECCO 2005 - Genetic and Evolutionary Computation Conference. New York:Association for Computing Machinery, 2005:257-264.

Optimization design of MVB period polling table based on Pareto ant colony algorithm

FAN Chao1, YU Yue1,2, GU Hong*1

( 1.School of Control Science and Engineering, Dalian University of Technology, Dalian 116024, China；2.CNR Dalian Electric Traction R&D Center Co.,Ltd., Dalian 116045, China )

Good multifunction vehicle bus (MVB) period polling table contributes to balancing the network load and improving the ability of network processing sporadic messages, which can ensure the reliability of the real time communication. An effective polling table design method is proposed. The design of the MVB period polling table is abstracted into a discrete optimization problem. Constraints are obtained according to the IEC 61375-1 international standard and request of schedulability. The optimal objective consists of uniformity and adjacent basic period time interval. The solution is achieved by Pareto ant colony algorithm. In this algorithm, every objective has updated its own pheromone independently by rule of the ant colony system algorithm and the total pheromone is calculated by weighted summation of the two pheromones. The non-dominated solutions sets are maintained by the crowding distance method in this multi-objective problem. The experimental results show that the Pareto ant colony algorithm can perform better than the existing algorithms in uniformity and balancing the network load.

Pareto ant colony algorithm; multifunction vehicle bus (MVB); period polling table

1000-8608(2015)03-0319-07

2014-09-09；

2014-11-08.

國家自然科學(xué)基金資助項目(61305034)；高等學(xué)校博士學(xué)科點專項科研基金資助項目(20120041110008).

范 超(1989-)，男，碩士生，E-mail:zidonghuafc@126.com；顧 宏*(1961-)，男，教授，博士生導(dǎo)師，E-mail:guhong@dlut.edu.cn.

U269.9

A

10.7511/dllgxb201503014