徐進權(quán),　王宏志,　胡黃水

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

?

差分進化MVB總線周期掃描表

徐進權(quán),王宏志*,胡黃水

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

摘要：針對多功能車輛總線(Multifunction Vehicle Bus， MVB)周期掃描表提出了一種利用差分進化算法的優(yōu)化設(shè)計方法。根據(jù)IEC61375國際標準相關(guān)規(guī)定，明確了周期掃描表生成規(guī)則和約束條件，建立了相應的數(shù)學模型，以均勻度為目標函數(shù)，對周期掃描表進行建立和優(yōu)化。最后，通過與國際標準中的逐步填空法進行均勻度對比，顯示出差分進化算法的優(yōu)勢。

關(guān)鍵詞：多功能車輛總線； 周期掃描表； 差分進化算法

0引言

多功能車輛總線是國際標準IEC61375-1中明確定義的一種數(shù)據(jù)傳輸總線。MVB總線傳遞兩種類型數(shù)據(jù)：周期數(shù)據(jù)和非周期數(shù)據(jù)。其中周期數(shù)據(jù)是在基本周期的周期相中發(fā)送的。周期相內(nèi)，總線主設(shè)備按預定順序輪詢各掛載設(shè)備以獲取周期數(shù)據(jù)。周期數(shù)據(jù)的傳輸過程如圖1所示。

在每次輪詢中，總線主設(shè)備依據(jù)周期掃描表來發(fā)送一個事先定義好的主幀，所有設(shè)備都接收這個主幀，然后進行譯碼，與主幀中邏輯地址匹配而且端口為源的從設(shè)備進行響應，發(fā)出從幀，端口為宿的從設(shè)備發(fā)現(xiàn)總線上有數(shù)據(jù)便馬上進行接收，這就完成了一次MVB數(shù)據(jù)傳輸。

圖1周期數(shù)據(jù)傳輸過程

現(xiàn)在，許多研究人員對于MVB總線傳輸?shù)膶崟r性進行研究，取得眾多成果。如文獻[1]提出了利用多目標粒子群算法對MVB總線傳輸進行優(yōu)化[1]；文獻[2]提出了利用逐步填空法和遺傳算法對MVB數(shù)據(jù)傳輸進行優(yōu)化[2]。文中主要研究的內(nèi)容是利用差分進化算法對周期掃描表進行優(yōu)化及設(shè)計。

1MVB周期掃描表

周期掃描表包括周期數(shù)據(jù)，主要是過程數(shù)據(jù)請求，也包含用于特殊要求的監(jiān)視數(shù)據(jù)請求或消息數(shù)據(jù)請求。為了保證MVB總線數(shù)據(jù)傳輸?shù)膶崟r性和準確性，MVB總線上的主設(shè)備將一個輪回周期劃分為固定的時間片，這個時間片稱之為“基本周期”，一個基本周期又可以分為兩個相：周期相和偶發(fā)相。周期掃描表定義了周期發(fā)送的主幀以及在輪回中每一基本周期內(nèi)留給偶發(fā)相的剩余時間。在周期查詢中，主設(shè)備將會按照周期掃描表發(fā)送一個預先定義好的主幀序列[3]。

1.1構(gòu)成周期掃描表基本規(guī)則

根據(jù)國際標準IEC61375-1的相關(guān)規(guī)定，周期掃描表格式生成的基本規(guī)則如下[4]：

1)周期數(shù)據(jù)通過特征周期Tip進行分類。

(1)

式中：Tbp----基本周期；

λ----特征周期級別，λ∈{1，2，…，10}。

2)一個循環(huán)將具有相同特征周期的周期性數(shù)據(jù)編成一組，其組名用其特征周期為基本周期的倍數(shù)表示。

3)一個宏循環(huán)由一個宏周期內(nèi)所有循環(huán)組成。

4)基本周期編號為BP(j)，0≤j≤macro-1。其中，BP(0)為宏循環(huán)的第一個周期，BP(macro-1)為宏循環(huán)的最后一個周期。

5)一個輪回定義為宏循環(huán)的數(shù)目，在其之后必須發(fā)生主權(quán)的轉(zhuǎn)移。在每一個宏循環(huán)之后鏈路監(jiān)視接口命令可對一個輪回終止。

6)一個循環(huán)可分成若干個由多個基本周期組成的子循環(huán)，其中的某些或全部可能為空。一個子循環(huán)由其索引定義。

7)每個宏循環(huán)的最后一個偶發(fā)相專為主權(quán)的轉(zhuǎn)移而保留，即使在此宏循環(huán)中并未用于主權(quán)的轉(zhuǎn)移。

1.2生成周期掃描表的約束條件

總線主將根據(jù)每個節(jié)點要求的特征周期和在初運行期間接收到的過程數(shù)據(jù)大小來配置生成周期掃描表。

1)在一個基本周期內(nèi)，所有周期數(shù)據(jù)傳輸?shù)目倳r間不得超過周期相所占時間。

(2)

式中Pt----一個基本周期內(nèi)，所有周期數(shù)據(jù)傳輸需要的總時間；

λpeTbp----一個基本周期內(nèi)，周期相所占的時間。

2)最長的特征周期成為宏周期。宏周期最大不得超過1 024ms。

3)周期數(shù)據(jù)的主幀長度固定為33位；從幀長度有5種類型[5]，這5種類型分別為：33、49、81、153、297位。

4)周期數(shù)據(jù)傳輸時間為

(3)

式中：Vmvb----信號速率，其值取1.5 Mbit/s；

Nmaster----主幀的長度；

Nslave----從幀的長度；

Treply----主幀發(fā)出后到響應該主幀的從幀發(fā)出的時間間隔；

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

MVB傳輸系統(tǒng)給定，則Treply和Tsm是固定值。

5)同一源的相同周期數(shù)據(jù)相鄰的兩次發(fā)送的間隔為一個特征周期，即同一周期數(shù)據(jù)相鄰的兩次發(fā)送間隔相差的基本周期個數(shù)為2λ-1。

2周期掃描表數(shù)學模型的建立

不同設(shè)備、不同周期的輪詢是由總線主設(shè)備根據(jù)事先設(shè)定好的周期掃描表以源尋址廣播的方式進行控制的，在每次輪詢中，總線主設(shè)備依據(jù)周期掃描表來發(fā)送一個事先定義好的主幀，所有設(shè)備都接收這個主幀，然后進行譯碼。對于第i個周期數(shù)據(jù)τi={Li,λi,fi}，數(shù)據(jù)長度Li和特征周期級別λi都是由設(shè)備性質(zhì)決定的，對于給定的MVB總線系統(tǒng)，其值是固定的；fi表示第i個周期數(shù)據(jù)第一次出現(xiàn)的位置。同一源的相同周期數(shù)據(jù)會根據(jù)特征周期級別在周期掃描表中重復出現(xiàn)，因此，確定各個周期數(shù)據(jù)在周期掃描表中第一次出現(xiàn)的位置fi，同時結(jié)合Li、λi就可以建立起周期掃描表。所以，當MVB總線系統(tǒng)一定時，尋找各周期數(shù)據(jù)在宏周期中第一次出現(xiàn)的位置fi就是建立周期掃描表的關(guān)鍵。周期掃描表的優(yōu)化過程是提高其均勻度的過程，以使各周期數(shù)據(jù)能夠更均勻合理的分布在掃描表中。定義均勻度函數(shù)

(4)

(5)

式中Li----在整個宏周期中，每個基本周期中周期數(shù)據(jù)的平均長度。

式(5)表示周期掃描表的整體均勻度。

通過合理配置各周期數(shù)據(jù)的初始位置fi，使σi的值盡量小，也就是使σ盡量小，σ值越小，表示周期掃描表越均勻，從而實現(xiàn)對周期掃描表的優(yōu)化。

3算法設(shè)計

3.1差分進化算法

差分進化算法[7-8](DifferentialEvolution，DE)是一種基于群體進化的算法，具有記憶個體最優(yōu)解和種群內(nèi)信息共享的特點，通過種群內(nèi)個體間的合作與競爭來實現(xiàn)對優(yōu)化問題的求解[9]。算法的基本思想是：對當前種群進行變異和交叉操作，產(chǎn)生另一個新種群；然后利用基于貪婪思想的選擇操作對這兩個種群進行一對一的選擇，從而產(chǎn)生最終的新一代種群。DE算法常被用來求解組合優(yōu)化問題。組合優(yōu)化問題是指在有限個可行解的集合中找出最優(yōu)解的一類優(yōu)化問題。實際上，周期掃描表的優(yōu)化就是已知周期數(shù)據(jù)的長度Li、特征周期級別λi，尋找周期數(shù)據(jù)的最優(yōu)排列組合過程。

3.2算法的實現(xiàn)

DE算法通過3個基本的操縱：變異、交叉和選擇來優(yōu)化周期掃描表。首先對DE算法中各參數(shù)進行初始化，并隨機形成含有H個基本周期的種群。

第1步：對DE算法的參數(shù)進行初始化。設(shè)種群數(shù)量NP=20、變異算子F=1、交叉算子CR=0.9、迭代次數(shù)G=300。假設(shè)特征周期級別最大為6，則周期掃描表的維度為H=25-1=32初始化種群：

(6)

式中：xi(0)----種群中初始狀態(tài)的第i個基本周期；

xj,i(0)----種群中初始狀態(tài)的第i個基本周期中第j個周期數(shù)據(jù)；

第2步：對初始種群進行評價，即計算初始種群中每個個體的目標函數(shù)值σ，計算基本周期中周期數(shù)據(jù)的均勻度。確定具有最好目標值的Xbest。進化代數(shù)G=1，開始迭代。

第3步：隨機選取種群中兩個不同的個體進行差分處理，并與待變異個體進行向量合成，生成中間變量

(7)

其中，i≠r1≠r2≠r3。

為了保證結(jié)果的有效性，需要根據(jù)周期掃描表的約束條件對各周期數(shù)據(jù)進行判斷，如果不滿足限制條件，則重新生成。判斷vi(g+1)中各個基本周期是否滿足周期掃描表的生成條件；判斷各個周期數(shù)據(jù)是否滿足周期數(shù)據(jù)長度的條件。

第g代種群：

(8)

第g代種群產(chǎn)生的中間體種群：

(9)

第4步：對第g代種群xi(g)及其中間體vi(g+1)進行個體間的交叉操作，生成試驗體，并評價其目標函數(shù)值σi和σ：

(10)

第5步：進行選擇操作。DE算法采用一對一的貪婪選擇競爭機制，進入下一代種群：

(11)

第6步：判斷是否達到終止條件或進化代數(shù)達到最大。若是，則進化終止，將此時的最佳個體xbest作為解輸出；若否，進化代數(shù)G=G+1，轉(zhuǎn)步驟4。算法流程圖如圖2所示。

圖2　算法流程圖

3.3算法仿真和結(jié)果分析

設(shè)MVB總線基本周期為1ms，周期相長度為0.7ms；電線長度為2km，其中包含2個中繼器；從幀最大響應時間Treply設(shè)為42μs，報文之間的時間間隔Tsm設(shè)為3μs。根據(jù)從真長度和式(3)可得表1。

表1　不同從真長度的傳輸時間

同時，假設(shè)MVB總線上掛載20個設(shè)備，其從幀長度、特征周期的排列見表2。

表2　MVB總線設(shè)備信息

續(xù)表2

根據(jù)表1和表2，可以生成MVB總線周期數(shù)據(jù)傳輸時間表，見表3。

經(jīng)過300次的迭代，優(yōu)化目標值σ的變化如圖3所示。

由圖3可見，隨著迭代次數(shù)的增加，目標函數(shù)值σ逐漸減小，并趨于穩(wěn)定。說明生成的周期掃描表的均勻度越來越穩(wěn)定。

生成的周期掃描表如圖4所示。

圖3　目標函數(shù)σ的變化值

圖4　DE算法生成的周期掃描表

根據(jù)國際標準相關(guān)規(guī)定，基本周期中周期數(shù)據(jù)傳輸所占時間與周期相所占時間的比值定義為總線利用率，表達式為：

(12)

式中Li----周期數(shù)據(jù)所占時間；

Tspo----基本周期中，周期相所占時間。

一個宏周期內(nèi)，基本周期傳輸?shù)睦寐试浇咏?，表示周期?shù)據(jù)分布越均勻。采用DE算法生成的周期掃描表各基本周期中周期相利用率的變化情況如圖5所示。

圖5　DE算法的周期相利用

由圖5可以看出，其周期相利用率最大為75.86%，最小利用率為60.14%，平均利用率為67%。國際標準IEC61375-1中的逐步填空法生成的周期掃描表各基本周期中周期相利用率的變化情況如圖6所示。

圖6　逐步填空法的周期相利用率

由圖6可以看出，其利用率最大為90%，最小為47%，平均利用率為63%。通過圖5與圖6的對比可以看出，利用差分進化算法生成的周期掃描表的周期數(shù)據(jù)分布的更加均勻，周期相的利用率也相對較高。因此，利用差分進化算法不僅滿足建立周期掃描表的基本規(guī)則和約束條件，也能滿足傳輸過程的實時性要求，同時也提高了周期相的利用率，改善了周期掃描表的均勻度，從而實現(xiàn)了對周期掃描表的優(yōu)化。

4結(jié)語

利用差分進化算法生成周期掃描表。首先介紹了多功能車輛總線周期掃描表的基本內(nèi)容及其生成規(guī)則和約束條件，然后建立起了數(shù)學模型，目標函數(shù)為均勻度。最后通過差分進化算法與MVB總線系統(tǒng)結(jié)合實現(xiàn)對周期掃描表的優(yōu)化。通過仿真分析可以看出,差分進化算法可以滿足建立周期掃描表的生成規(guī)則和約束條件，通過與逐步填空法對比，差分進化算法也能夠改善周期相的利用率，提高周期掃描表的均勻度，實現(xiàn)對周期掃描表的優(yōu)化。

參考文獻：

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

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

[3]陳特放,曾秋芬.列車微機與網(wǎng)絡控制技術(shù)及應用[M].北京：科學出版社，2012：102-124.

[4]IEC.IEC61375-1:1999.Electric Railway Equipment-Train Bus-Part 1:Train Communication Network[S].Genva，1999.

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

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

[7]周欽亞.動態(tài)環(huán)境中差分進化算法的研究[D].鄭州：鄭州大學，2014.

[8]S Ramesh, S Kannan, S Baskar. An improved generalized differential evolution algorithm for multi-objective reactive power dispatch[J]. Engineering Optimization,2012,44(4):391-405.

[9]黃亞，梁昔明，陳義雄，等.基于多種群離散差分進化的圖像稀疏分解算法[J].模式識別與人工智能，2014,27(10):900-906.

Periodic polling table in multifunction vehicle bus based on the differential evolution algorithm

XU Jinquan,WANG Hongzhi*,HU Huangshui

(School of Computer Science & Engineering, Changchun University of Technology, Changchun 130012， China)

Abstract：To optimize the periodic polling table in Multifunction Vehicle Bus (MVB), a new design based on differential evolution algorithm is proposed. According to the relevant provisions of international standard IEC61375, we set the periodic polling table generation rules and constraints, and establish the mathematical model. With the evenness degree as objective function, periodic polling table is built and optimized. The differential evolution algorithm is compared with the step fill method in the IEC61375-1 to show that the former is with better performance.

Key words：Multifunction Vehicle Bus (MVB); periodic polling table; differential evolution algorithm.

中圖分類號：U 285.5

文獻標志碼：A

文章編號：1674-1374(2016)01-0036-06

DOI:10.15923/j.cnki.cn22-1382/t.2016.1.08

作者簡介：徐進權(quán)(1990-)，男，漢族，吉林長春人，長春工業(yè)大學碩士研究生，主要從事數(shù)字信號處理及應用方向研究,E-mail:0507power@163.com. *通訊作者：王宏志(1961-)，男，漢族，黑龍江牡丹江人，長春工業(yè)大學教授，博士，主要從事數(shù)字信號處理及應用方向研究,E-mail:wanghongzhi@ccut.edu.cn.

基金項目：吉林省科技廳科技攻關(guān)計劃項目(20140204037GX)

收稿日期：2015-09-24