差分进化MVB总线周期扫描表

徐进权,　王宏志,　胡黄水

(长春工业大学 计算机科学与工程学院， 吉林 长春　130012)



差分进化MVB总线周期扫描表

徐进权,王宏志*,胡黄水

(长春工业大学 计算机科学与工程学院， 吉林 长春130012)

摘要：针对多功能车辆总线(Multifunction Vehicle Bus， MVB)周期扫描表提出了一种利用差分进化算法的优化设计方法。根据IEC61375国际标准相关规定，明确了周期扫描表生成规则和约束条件，建立了相应的数学模型，以均匀度为目标函数，对周期扫描表进行建立和优化。最后，通过与国际标准中的逐步填空法进行均匀度对比，显示出差分进化算法的优势。

关键词：多功能车辆总线； 周期扫描表； 差分进化算法

0引言

多功能车辆总线是国际标准IEC61375-1中明确定义的一种数据传输总线。MVB总线传递两种类型数据：周期数据和非周期数据。其中周期数据是在基本周期的周期相中发送的。周期相内，总线主设备按预定顺序轮询各挂载设备以获取周期数据。周期数据的传输过程如图1所示。

在每次轮询中，总线主设备依据周期扫描表来发送一个事先定义好的主帧，所有设备都接收这个主帧，然后进行译码，与主帧中逻辑地址匹配而且端口为源的从设备进行响应，发出从帧，端口为宿的从设备发现总线上有数据便马上进行接收，这就完成了一次MVB数据传输。

图1周期数据传输过程

现在，许多研究人员对于MVB总线传输的实时性进行研究，取得众多成果。如文献[1]提出了利用多目标粒子群算法对MVB总线传输进行优化[1]；文献[2]提出了利用逐步填空法和遗传算法对MVB数据传输进行优化[2]。文中主要研究的内容是利用差分进化算法对周期扫描表进行优化及设计。

1MVB周期扫描表

周期扫描表包括周期数据，主要是过程数据请求，也包含用于特殊要求的监视数据请求或消息数据请求。为了保证MVB总线数据传输的实时性和准确性，MVB总线上的主设备将一个轮回周期划分为固定的时间片，这个时间片称之为“基本周期”，一个基本周期又可以分为两个相：周期相和偶发相。周期扫描表定义了周期发送的主帧以及在轮回中每一基本周期内留给偶发相的剩余时间。在周期查询中，主设备将会按照周期扫描表发送一个预先定义好的主帧序列[3]。

1.1构成周期扫描表基本规则

根据国际标准IEC61375-1的相关规定，周期扫描表格式生成的基本规则如下[4]：

1)周期数据通过特征周期Tip进行分类。

(1)

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

λ----特征周期级别，λ∈{1，2，…，10}。

2)一个循环将具有相同特征周期的周期性数据编成一组，其组名用其特征周期为基本周期的倍数表示。

3)一个宏循环由一个宏周期内所有循环组成。

4)基本周期编号为BP(j)，0≤j≤macro-1。其中，BP(0)为宏循环的第一个周期，BP(macro-1)为宏循环的最后一个周期。

5)一个轮回定义为宏循环的数目，在其之后必须发生主权的转移。在每一个宏循环之后链路监视接口命令可对一个轮回终止。

6)一个循环可分成若干个由多个基本周期组成的子循环，其中的某些或全部可能为空。一个子循环由其索引定义。

7)每个宏循环的最后一个偶发相专为主权的转移而保留，即使在此宏循环中并未用于主权的转移。

1.2生成周期扫描表的约束条件

总线主将根据每个节点要求的特征周期和在初运行期间接收到的过程数据大小来配置生成周期扫描表。

1)在一个基本周期内，所有周期数据传输的总时间不得超过周期相所占时间。

(2)

式中Pt----一个基本周期内，所有周期数据传输需要的总时间；

λpeTbp----一个基本周期内，周期相所占的时间。

2)最长的特征周期成为宏周期。宏周期最大不得超过1 024ms。

3)周期数据的主帧长度固定为33位；从帧长度有5种类型[5]，这5种类型分别为：33、49、81、153、297位。

4)周期数据传输时间为

(3)

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

Nmaster----主帧的长度；

Nslave----从帧的长度；

Treply----主帧发出后到响应该主帧的从帧发出的时间间隔；

Tsm----两个报文之间的传输间隔。

MVB传输系统给定，则Treply和Tsm是固定值。

5)同一源的相同周期数据相邻的两次发送的间隔为一个特征周期，即同一周期数据相邻的两次发送间隔相差的基本周期个数为2λ-1。

2周期扫描表数学模型的建立

不同设备、不同周期的轮询是由总线主设备根据事先设定好的周期扫描表以源寻址广播的方式进行控制的，在每次轮询中，总线主设备依据周期扫描表来发送一个事先定义好的主帧，所有设备都接收这个主帧，然后进行译码。对于第i个周期数据τi={Li,λi,fi}，数据长度Li和特征周期级别λi都是由设备性质决定的，对于给定的MVB总线系统，其值是固定的；fi表示第i个周期数据第一次出现的位置。同一源的相同周期数据会根据特征周期级别在周期扫描表中重复出现，因此，确定各个周期数据在周期扫描表中第一次出现的位置fi，同时结合Li、λi就可以建立起周期扫描表。所以，当MVB总线系统一定时，寻找各周期数据在宏周期中第一次出现的位置fi就是建立周期扫描表的关键。周期扫描表的优化过程是提高其均匀度的过程，以使各周期数据能够更均匀合理的分布在扫描表中。定义均匀度函数

(4)

(5)

式中Li----在整个宏周期中，每个基本周期中周期数据的平均长度。

式(5)表示周期扫描表的整体均匀度。

通过合理配置各周期数据的初始位置fi，使σi的值尽量小，也就是使σ尽量小，σ值越小，表示周期扫描表越均匀，从而实现对周期扫描表的优化。

3算法设计

3.1差分进化算法

差分进化算法[7-8](DifferentialEvolution，DE)是一种基于群体进化的算法，具有记忆个体最优解和种群内信息共享的特点，通过种群内个体间的合作与竞争来实现对优化问题的求解[9]。算法的基本思想是：对当前种群进行变异和交叉操作，产生另一个新种群；然后利用基于贪婪思想的选择操作对这两个种群进行一对一的选择，从而产生最终的新一代种群。DE算法常被用来求解组合优化问题。组合优化问题是指在有限个可行解的集合中找出最优解的一类优化问题。实际上，周期扫描表的优化就是已知周期数据的长度Li、特征周期级别λi，寻找周期数据的最优排列组合过程。

3.2算法的实现

DE算法通过3个基本的操纵：变异、交叉和选择来优化周期扫描表。首先对DE算法中各参数进行初始化，并随机形成含有H个基本周期的种群。

第1步：对DE算法的参数进行初始化。设种群数量NP=20、变异算子F=1、交叉算子CR=0.9、迭代次数G=300。假设特征周期级别最大为6，则周期扫描表的维度为H=25-1=32初始化种群：

(6)

式中：xi(0)----种群中初始状态的第i个基本周期；

xj,i(0)----种群中初始状态的第i个基本周期中第j个周期数据；

第2步：对初始种群进行评价，即计算初始种群中每个个体的目标函数值σ，计算基本周期中周期数据的均匀度。确定具有最好目标值的Xbest。进化代数G=1，开始迭代。

第3步：随机选取种群中两个不同的个体进行差分处理，并与待变异个体进行向量合成，生成中间变量

(7)

其中，i≠r1≠r2≠r3。

为了保证结果的有效性，需要根据周期扫描表的约束条件对各周期数据进行判断，如果不满足限制条件，则重新生成。判断vi(g+1)中各个基本周期是否满足周期扫描表的生成条件；判断各个周期数据是否满足周期数据长度的条件。

第g代种群：

(8)

第g代种群产生的中间体种群：

(9)

第4步：对第g代种群xi(g)及其中间体vi(g+1)进行个体间的交叉操作，生成试验体，并评价其目标函数值σi和σ：

(10)

第5步：进行选择操作。DE算法采用一对一的贪婪选择竞争机制，进入下一代种群：

(11)

第6步：判断是否达到终止条件或进化代数达到最大。若是，则进化终止，将此时的最佳个体xbest作为解输出；若否，进化代数G=G+1，转步骤4。算法流程图如图2所示。

图2　算法流程图

3.3算法仿真和结果分析

设MVB总线基本周期为1ms，周期相长度为0.7ms；电线长度为2km，其中包含2个中继器；从帧最大响应时间Treply设为42μs，报文之间的时间间隔Tsm设为3μs。根据从真长度和式(3)可得表1。

表1　不同从真长度的传输时间

同时，假设MVB总线上挂载20个设备，其从帧长度、特征周期的排列见表2。

表2　MVB总线设备信息

续表2

根据表1和表2，可以生成MVB总线周期数据传输时间表，见表3。

经过300次的迭代，优化目标值σ的变化如图3所示。

由图3可见，随着迭代次数的增加，目标函数值σ逐渐减小，并趋于稳定。说明生成的周期扫描表的均匀度越来越稳定。

生成的周期扫描表如图4所示。

图3　目标函数σ的变化值

图4　DE算法生成的周期扫描表

根据国际标准相关规定，基本周期中周期数据传输所占时间与周期相所占时间的比值定义为总线利用率，表达式为：

(12)

式中Li----周期数据所占时间；

Tspo----基本周期中，周期相所占时间。

一个宏周期内，基本周期传输的利用率越接近，表示周期数据分布越均匀。采用DE算法生成的周期扫描表各基本周期中周期相利用率的变化情况如图5所示。

图5　DE算法的周期相利用

由图5可以看出，其周期相利用率最大为75.86%，最小利用率为60.14%，平均利用率为67%。国际标准IEC61375-1中的逐步填空法生成的周期扫描表各基本周期中周期相利用率的变化情况如图6所示。

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

由图6可以看出，其利用率最大为90%，最小为47%，平均利用率为63%。通过图5与图6的对比可以看出，利用差分进化算法生成的周期扫描表的周期数据分布的更加均匀，周期相的利用率也相对较高。因此，利用差分进化算法不仅满足建立周期扫描表的基本规则和约束条件，也能满足传输过程的实时性要求，同时也提高了周期相的利用率，改善了周期扫描表的均匀度，从而实现了对周期扫描表的优化。

4结语

利用差分进化算法生成周期扫描表。首先介绍了多功能车辆总线周期扫描表的基本内容及其生成规则和约束条件，然后建立起了数学模型，目标函数为均匀度。最后通过差分进化算法与MVB总线系统结合实现对周期扫描表的优化。通过仿真分析可以看出,差分进化算法可以满足建立周期扫描表的生成规则和约束条件，通过与逐步填空法对比，差分进化算法也能够改善周期相的利用率，提高周期扫描表的均匀度，实现对周期扫描表的优化。

参考文献：

[1]陈佳凯，韦巍.基于多目标粒子群优化的多功能车辆总线周期性扫描表的优化[J].铁道学报，2012,34(11)：60-66.

[2]王永翔，王立德.多功能车辆总线周期扫描表的最优化设计[J].铁道学报，2009,31(6)：46-52.

[3]陈特放,曾秋芬.列车微机与网络控制技术及应用[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]朱俊，李芳，王丽芳.基于蚁群算法的多功能车辆周期扫描表的优化设[J].铁道学报，2013,35(7)：57-62.

[7]周钦亚.动态环境中差分进化算法的研究[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

作者简介：徐进权(1990-)，男，汉族，吉林长春人，长春工业大学硕士研究生，主要从事数字信号处理及应用方向研究,E-mail:0507power@163.com. *通讯作者：王宏志(1961-)，男，汉族，黑龙江牡丹江人，长春工业大学教授，博士，主要从事数字信号处理及应用方向研究,E-mail:wanghongzhi@ccut.edu.cn.

基金项目：吉林省科技厅科技攻关计划项目(20140204037GX)

收稿日期：2015-09-24