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

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

?

差分進(jìn)化MVB總線周期掃描表

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

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

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

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

0引言

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

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

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

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

1MVB周期掃描表

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

(2)

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

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

2)最長(zhǎng)的特征周期成為宏周期。宏周期最大不得超過(guò)1 024ms。

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

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

(3)

式中：Vmvb----信號(hào)速率，其值取1.5 Mbit/s；

Nmaster----主幀的長(zhǎng)度；

Nslave----從幀的長(zhǎng)度；

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

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

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

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

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

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

(4)

(5)

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

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

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

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

3.1差分進(jìn)化算法

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

3.2算法的實(shí)現(xiàn)

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

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

(6)

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

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

第2步：對(duì)初始種群進(jìn)行評(píng)價(jià)，即計(jì)算初始種群中每個(gè)個(gè)體的目標(biāo)函數(shù)值σ，計(jì)算基本周期中周期數(shù)據(jù)的均勻度。確定具有最好目標(biāo)值的Xbest。進(jìn)化代數(shù)G=1，開(kāi)始迭代。

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

(7)

其中，i≠r1≠r2≠r3。

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

第g代種群：

(8)

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

(9)

第4步：對(duì)第g代種群xi(g)及其中間體vi(g+1)進(jìn)行個(gè)體間的交叉操作，生成試驗(yàn)體，并評(píng)價(jià)其目標(biāo)函數(shù)值σi和σ：

(10)

第5步：進(jìn)行選擇操作。DE算法采用一對(duì)一的貪婪選擇競(jìng)爭(zhēng)機(jī)制，進(jìn)入下一代種群：

(11)

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

圖2　算法流程圖

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

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

表1　不同從真長(zhǎng)度的傳輸時(shí)間

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

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

續(xù)表2

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

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

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

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

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

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

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

(12)

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

Tspo----基本周期中，周期相所占時(shí)間。

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

圖5　DE算法的周期相利用

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

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

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

4結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

[7]周欽亞.動(dòng)態(tài)環(huán)境中差分進(jìn)化算法的研究[D].鄭州：鄭州大學(xué)，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ìn)化的圖像稀疏分解算法[J].模式識(shí)別與人工智能，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.

中圖分類號(hào)：U 285.5

文獻(xiàn)標(biāo)志碼：A

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

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

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

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

收稿日期：2015-09-24