基于自适应改进遗传算法的MVB周期调度表优化

郑 曼， 胡黄水， 杨兴旺， 卿金辉

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

0 引 言

多功能车辆总线(Mutlifunction Vehicle Bus, MVB)作为列车通信网络(Train Communication Networks, TCN)的标准之一，在地铁、城轨、高铁等车辆上得到了广泛的应用[1-3]。虽然IEC61375-1标准明确规定了MVB数据传输的实时性要求，但如何进一步提高通信实时性能一直是其面临的主要挑战[4-6]。国内学者进行了诸多研究，也相应地提出了一些更优化的算法。如文献[7]提出了多粒子群优化算法，这种算法在处理连续问题上有一定的优越性，但对于离散问题的调度优化则存在一定的缺陷；文献[8]提出了差分进化算法，该算法难以选取变异策略，缺乏局部搜索能力；文献[9]在文献[8]的基础上提出了改进差分进化算法，该算法动态调整了周期信息与非周期信息时长，但在具体指标的优化上未达到理想的效果。

为了更智能地调整算法控制参数来处理离散信息调度问题，文中提出一种基于自适应改进遗传算法的MVB周期信息实时调度算法，对周期调度表进行优化，然后根据约束条件及优化目标对周期调度表的宽度和梯度等参数进行调整，以达到均匀传输信息、提高实时性的目的。

1 MVB网络的通信原理

MVB通过网络中唯一的主设备进行集中式实时调度管理来完成过程数据和消息数据两类信息的传输，其中过程数据为周期信息。主设备首先广播发送过程数据请求主帧，接收主帧后，与主帧中逻辑端口地址相同的源设备发送响应从帧，主设备接收从帧后开始发送数据，以此完成一次周期信息的传输。因此，源设备周期数据报文发送的先后次序是由主帧的排列次序决定的。对周期数据调度的优化，实际上就是对周期扫描表的优化。MVB周期信息通信过程如图1所示。

图1 MVB周期信息通信过程

1.1 特征周期

在MVB网络中，同一节点的两个连续轮询之间的时间间隔叫做特征周期，用T_ip表示:

T_ip=2n×T_bp

(1)

一般地，基本周期为1 ms，最长的特征周期不得超过1 024 ms。

1.2 周期调度表

周期扫描表本质上是一个宏循环的每个周期里要轮询的节点、地址及设备表。宏循环为一个宏周期中包含的基本周期数，而宏周期为最长的特征周期。

在构建周期调度表时，一个宏循环由一个宏周期内的所有循环组成，一个循环将相同特征周期的周期信息编为一组，组名用n表示；同时，一个循环可分为若干个由多个基本周期组成的子循环。

定义W为周期扫描表的宽度，即在周期扫描表各行的最大周期相宽度；G为周期扫描表的时间梯度，即周期扫描表最长周期相和最短周期相之差；H为周期扫描表的高度：

H=2max(λi),i∈{0,1,…,n-1}

(2)

G=max{length(i)}-min{length(i)}

(3)

式中：n——周期变量;

λi——周期级别;

length(i)——第i个基本周期内周期相长度。

基于此，假设一个包含30个循环的宏循环的周期数据，其中有7个周期变量

V=(v0,v1,v2,v3,v4,v5,v6)

其特征周期级别分别为

截取前8个循环得到的周期扫描表如图2所示。

图2 按协议生成的前8个循环的周期扫描表

2 算法设计

由于MVB周期信息在一个宏周期中，会随机传输各种时间长度不同的数据。在基本遗传算法的基础上，基于遗传算法的自适应机制[10]能够动态调整策略参数，即需要处理的MVB周期信息集；该机制使MVB周期信息集能对进化过程中事先难以预料的细节产生反应，适应在各个阶段的不同环境，从而更灵活地将长度合适的周期信息排列在调度表中。在遗传进化过程中，需调度的周期信息集以某种方式动态地获取和利用关于问题的规律性知识，进行群体的自动学习，完成周期调度表的排布，以达到均匀传输信息、提高实时性的目的。

2.1 约束条件

IEC61375-1标准中给出了以下约束条件：

1)所有周期信息传输的总时间在一个基本周期内应小于周期相所占时间。

2)宏周期最大不得超过1 024 ms。

3)过程数据的主帧长度固定为33位，从帧长度有5种类型，分别为33、49、81、153、297位；过程数据传输的时间为：

(4)

式中：Nmaster——主帧长度；

Nslave——从帧长度；

VMVB——信号速率，其值取1.5 Mbit/s；

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

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

2.2 优化目标

IEC61375-1标准中要求周期信息均匀分布，则可根据最大周期相和最短周期相的时间计算标准差：

(5)

(6)

式中：N(m)——第m个基本周期的端口数；

tave——周期相的平均值；

Nλ——特征级别为λ的端口数目；

ti——第i个周期相的时间。

2.3 算法流程

从第一个周期和以第一个宏周期开始，步骤如下：

1)明确实际问题参数集及约束条件；

2)选择编码策略，对需要调度的周期信息集进行编码；

3)确定优化目标；

4)判断第i个周期能否发送信息，若不能，则信息不能放在第i个周期，若能，则进行下一步；

5)判断能够发送的信息是否在周期相内，不能则该信息不被调度，能则将信息安排在调度表中；

6)按照遗传策略，用自适应算子筛选信息群体，以形成下一代信息群体；

7)判断生成的周期调度表是否满足约束条件，不满足则返回5)，或者修改遗传策略再返回6)；

8)宏周期结束，所有周期信息扫描完毕，则生成周期扫描表。

自适应遗传算法生成周期扫描表的基本流程如图3所示。

图3 采用自适应遗传算法构成MVB周期调度表的流程

3 仿真分析

为了验证该算法对生成MVB周期调度表这一实际问题的有效性，在满足IEC61375-1标准的基础上，与文献[9]中运用的改进差分算法进行仿真对比，周期变量配置如1.2中所示。采用自适应方法生成的前8个循环的周期扫描表如图4所示。

对比图2和图4可以发现，采用自适应算法后的周期扫描表，周期调度表的梯度小，周期变量排布更均匀。

采用改进差分算法和自适应遗传算法传输周期信息在一个宏周期中过程数据通信时长的分布如图5所示。

图4 采用自适应遗传算法生成的前8个循环的周期扫描表

图5 两种算法的过程数据通信时长

由图5对比可以发现，改进差分算法生成的周期扫描表中过程数据通信时长最大为450 μs，最小为200 μs，梯度差为250 μs，反映在图上起伏较大，分布较为离散；而采用自适应算法后，过程数据通信时间最大为395 μs，最小为310 μs，梯度差为85 μs，反映在图上即通信时长基本排布在400 μs左右，分布更加均匀。由此可以看出，在同等条件下，自适应遗传算法在一个宏周期中，过程数据传输的时间梯度较小，分布更均匀，反映在周期调度表上，则信息排布更紧密，从而改善了MVB过程数据的传送性能，提高了消息数据传送的有效性。

4 结 语

提出了基于自适应遗传算法来动态调整参数以优化构建MVB周期调度表，首先对MVB周期调度表的构建问题进行研究，然后提出了该算法应该满足的约束条件及期望达到的目标值，最后与文献[9]中的改进遗传算法进行仿真比较，结果表明，自适应遗传算法改善了周期信息在各基本周期中的均匀度，调度效果也得到了明显改善，从而达到了改善MVB通信实时性的目的。