基于Pareto蚁群算法的MVB周期轮询表优化设计

范 超， 于 跃,2， 顾 宏*

( 1.大连理工大学 控制科学与工程学院, 辽宁 大连 116024；2.北车大连电力牵引研发中心有限公司， 辽宁 大连 116045 )

电子与信息工程、管理工程

基于Pareto蚁群算法的MVB周期轮询表优化设计

范 超1， 于 跃1,2， 顾 宏*1

( 1.大连理工大学 控制科学与工程学院, 辽宁 大连 116024；2.北车大连电力牵引研发中心有限公司， 辽宁 大连 116045 )

合理的多功能车辆总线(MVB)周期轮询表有助于均衡网络负荷、提高网络处理偶发信息的能力、保证实时通信的可靠性．为此提出一种有效的轮询表设计方法．将MVB周期轮询表的设计抽象成离散优化问题，根据IEC 61375-1国际标准和可调度性要求建立约束条件，将均匀度和相邻基本周期时间差作为优化目标，利用Pareto蚁群(Pareto ant colony，P-AC)算法求解．每个优化目标对应自己的信息素，信息素采用蚁群系统的规则更新，总信息素由两者加权得到，非劣解基于拥挤距离方法维护．与已有的优化算法相比，Pareto蚁群算法优化得到的轮询表均匀度更好，能够更有效地均衡网络负荷．

Pareto蚁群算法；多功能车辆总线(MVB)；周期轮询表

0 引 言

多功能车辆总线(MVB)是车厢级总线，连接厢内设备以构成局域网．每个设备可以有多个端口，MVB在运行前需要人为配置端口参数，技术人员根据参数设计周期轮询表，运行时主设备按照轮询表读取从设备信息．国内外学者对列车周期轮询表优化构建问题做了卓有成效的研究．文献[1]利用最长报文填最短基本周期的思路提高表的均匀度；当给定数据无法编排时，文献[2]给出一种调整特征周期的方法；文献[3-5]利用遗传算法、多目标粒子群优化(multi-objective particle swarm optimization，MPSO)算法和蚁群算法(ant colony algorithm，AC)，根据各自提出的优化指标建立周期轮询表．但是文献[3]的多目标粒子群优化算法更适用于连续问题，处理离散问题的调度优化需要不断取整，存在缺陷；文献[4]的蚁群算法虽然更适合离散问题，但是优化目标单一，对具体的通信指标无法兼顾．为解决已有算法的众多缺点，本文通过建模将Pareto蚁群算法应用到周期轮询表的优化，引入时间梯度概念，表示最长周期与最短周期时间差，时间梯度与基本周期的周期相方差加权求和表示均匀度．将均匀度作为第一个优化目标，相邻基本周期时间差作为第二个优化目标，利用Pareto蚁群算法求解．

1 MVB通信规则

MVB主设备将时间轴划分成固定长度时间片，这里的固定长度就是基本周期，用Tbp表示，是最小调度粒度，这能保证实时变量确定的响应时间．基本周期取值范围为1.0 ms≤Tbp≤2.5 ms，本文中Tbp=1.0 ms．

特征周期指周期变量被轮询的时间间隔，用Tip表示(i是周期信息编号)，规定特征周期是基本周期的2λi倍，但不超过1 024倍，λi表示特征周期级别．

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

(1)

宏周期是最大的特征周期，用Tmacro表示，即Tmacro=max {Tip}．宏周期包含基本周期，数目为M=Tmacro/Tbp．

一个基本周期包括周期相、监视相、事件相和保护相，后三相合称为偶发相[1]．主设备在周期相中遵照所设计的轮询表对周期数据轮询，监视相中主设备进行设备扫描和主权传递，事件相处理突发报文．不同的基本周期可以有不同的偶发时间，其缺省值为350 μs．

MVB采用主-从工作方式，主帧长度固定为33 bit，从帧F码对应5种长度：33,49,81,153,297 bit，考虑到时间延迟tms和tsm，MVB完成一次报文传输需要的时间为

(2)

MVB通信速率v为1.5 Mbit/s, 由式(2)可以计算每次通信的时长．

2 周期轮询表问题描述与模型建立

2.1 任务描述

考虑对N个周期变量编排，每个周期变量可以表示为

Ci={Tip，Fi，Li}；i∈{1，2，…，N}

(3)

式中：Tip是第i个变量的特征周期；Fi是功能码，取值为0，1，2，3，4，依次对应5个从帧长度，通过从帧长度求出完成一次报文传输时间tmmi；Li为周期变量首次在轮询表中出现的基本周期编号，本文的目的就是确定每个设备的Li．

2.2 约束条件

(1)最大周期相约束．每个基本周期中，周期相所占时间有一定限制，需要留出一定时间完成监视任务和处理突发消息．用k表示周期相在一个基本周期所占比例：

(4)

(2)可调度性条件．周期信息的截止期等于其特征周期，可调度性要求响应时间不大于截止期[6]，所以端口首次在轮询表中出现的时间不大于其特征周期，即

Li≤Tip

(5)

2.3 优化目标

IEC61375-1标准要求周期信息均匀分布，一个重要指标是基本周期周期相的标准差

(6)

(7)

定义时间梯度为轮询表最长周期相和最短周期相之差，用Tgrad表示，用ttotal(i)表示第i个基本周期内周期相长度，则有

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

(8)

Var、Tgrad越小效果越好，利用它们加权作为第一个优化目标以更全面地表达均匀度要求，用Fit1表示为

Fit1=Var+xTgrad

(9)

为提高网络对偶发相处理能力，在保证均匀度的基础上，扩大相邻基本周期的平均时间差[3]， 此度量用Tdiff表示为

(10)

当均匀度相同时，Tdiff越大表明该编排越能将长周期和短周期更好地错开．长周期剩余时间少，短周期剩余时间多，若突发消息在长周期剩余时间无法处理完，在短周期里有足够剩余时间处理，这提高了对偶发相的处理能力，所以Tdiff越大效果越好．构造第二个优化目标Fit2为

Fit2=y(Tmax-Tdiff)

(11)

其中y表征两个优化目标的相对重要性，一般y<0.1．

因为比较Tdiff指标的前提是均匀度相同，当均匀度不同时不能通过简单比较Tdiff来判断某个解的性能．由此引入相对指标用于评价解的性能表现，表达式为

(12)

Relative_diff越大，认为均匀度相同时相邻周期的时间差异越大，说明网络处理偶发消息的能力越强，性能也就越好．

3 基于Pareto蚁群算法建立周期轮询表

3.1 Pareto蚁群算法

蚁群算法利用群体合作和正反馈机制搜索解空间，不易陷入局部最优，在离散的优化调度问题上寻优效果好．蚁群系统(antcolonysystem，ACS)算法[7-8]相比基本蚁群算法和其他改进算法，其全局搜索能力更强．本文的Pareto蚁群算法是在蚁群系统算法的基础上添加规则提出的，能用于多目标优化问题[9]．

蚁群系统算法先利用最近邻思想[2]构造初始游历，其适应值为f0，则信息素增强系数

(13)

信息素矩阵各元素初始化值为Q．蚂蚁从第i个节点选择第k条路径走到第i+1个节点的概率为

(14)

式中：τi,i+1为信息素强度，ηi,i+1为启发函数，α为信息启发因子，β为期望启发因子．由式(5)得第i个节点可选择路径有Tip条，则启发函数表示为

ηi,i+1=1/Tip

(15)

求得每条备选路径概率后，利用轮盘赌方式选择下一条路径．

蚁群系统算法的信息素更新规则包括局部更新和全局更新，如

(16)

(17)

式中：ρ1、ρ2为信息素挥发系数，fb表示最优路径的适应值．蚂蚁每走一步，都利用局部更新规则更新信息素；当所有蚂蚁遍历结束，对全局最优的路径利用全局更新规则更新信息素．

Pareto蚁群算法包含Fit1和Fit2两个目标，两个目标对应信息素τ1和τ2，根据上述规则独立维护各自的信息素，路径上总的信息素由τ1和τ2加权得到：

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

(18)

其中p体现两个目标的重要程度，考虑到Fit1为主要目标，取p>0.7．

蚁群算法与研究问题建立如图1所示的对应关系[4]，图中每个端口对应一个节点，蚂蚁只准从起点依次经过各个节点最后到达端口N．由式(5)得从第i-1个节点走到第i个节点可选择路径有Tip条，如果选择第k条路径则表示第i个端口在轮询表中首次出现的特征周期编号为k．每只蚂蚁走完一遍就会生成一个解向量，每个解向量对应一个轮询表．利用Pareto蚁群算法搜索解空间，就可以得到性能优越的非劣解．

图1 周期轮询表的蚁群算法Fig.1 The ant colony algorithm of period polling table

3.2 非劣解维护

假设解A的两个适应值都小于解B的适应值，称A支配B，否则B不受A支配．不受任何解支配的解，称之为非劣解．

多目标优化问题一般没有绝对的最优解，本文的目标是找出非劣解的集合形成Pareto沿．假设解集的容纳量为Num_nd，当得到的非劣解数目过多，需要根据规则剔除一部分．非劣解集基于拥挤距离[10]来维护，拥挤距离表征该解周围其他解分布的密集程度，点的拥挤距离越小，说明该点周围的解分布越密集，该解被剔除的概率越大．拥挤距离的计算如下：

针对每一个优化目标m

根据适应值升序排序，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沿后，根据下列式子计算沿上每一个点的评价指数ψ：

ψ=0.75Fit1+0.25Fit2

(19)

其中ψ包含了各个指标的信息，将其升序排列，从前3个点中随机选择一个，该点对应的向量L即为最终解，最后以此为依据建立周期轮询表．

综上所述，利用Pareto蚁群算法优化MVB周期轮询表的流程如图2所示．

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

4 方法比较与结果分析

基于文献[3]和[4]的实验数据，将本文算法与已经提出的蚁群算法和多目标粒子群优化算法进行比较．Pareto蚁群算法的参数设定：α=1，β=2，ρ1=0.05，ρ2=0.10，蚂蚁数目为10，信息素增强系数由式(13)求得，非劣解集容纳量为24，程序迭代200次．

文献[3]的设备信息数据如表1所示，式(4)中k=75%，利用文献[3]的多目标粒子群优化算法得到的解向量为(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所示．根据式(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)．两种算法的评价参数见表2．

表1 文献[3]的设备信息表Tab.1 Device information list of Lit. [3]

图3 Pareto蚁群算法基于表1产生的非劣解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，远小于多目标粒子群优化算法的115.75；其Tgrad指标是236.00，同样远小于多目标粒子群优化算法的376.00，说明本文算法能保证各基本周期波动小，在均匀度上的表现更好．Pareto蚁群算法的Relative_diff为1.48，而多目标粒子群优化算法的仅为1.42，说明Pareto蚁群算法得到的解能更好地将长短周期错开，提高网络处理偶发消息的能力．因为Pareto蚁群算法较多目标粒子群优化算法更适合处理离散优化问题，所以它的结果表现更优秀．

图4是两种算法解的周期相利用率分布．Pareto 蚁群轮询表最大利用率为97%，较小的也在70%以上，分布集中；而多目标粒子群优化算法对应表最大利用率为100%，还有多个周期低于65%，分布零散．对比发现，Pareto蚁群算法构建的周期轮询表中各周期相波动较小，均匀度更好，利用率更接近平均值，这样的周期轮询表能够更好地均衡网络负荷，预防局部通信压力过大．

(a) 多目标粒子群优化算法周期相时间散点图

(b) Pareto蚁群算法周期相时间散点图

图4 Pareto蚁群算法与多目标粒子群优化算法的周期相利用率比较

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

文献[4]的设备信息数据如表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所示．根据式(19)计算排序，最终选取的解向量为(1 1 2 1 4 2 3 4 2 4 7 1 7 5 3 6 4 8 5 18)．表4列出对应参数指标．

表3 文献[4]的设备信息表Tab.3 Device information list of Lit. [4]

图5 Pareto蚁群算法基于表3产生的非劣解

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蚁群算法对应的标准差和Tgrad分别为57.89和265.00，明显小于基本蚁群算法的，充分证明Pareto蚁群算法能更好地保证轮询表的均匀度；Pareto蚁群算法的Relative_diff为1.22，大于基本蚁群算法的0.97，证明其能够更有效地错开长短周期，均衡网络负荷．

图6是两种算法解的周期相利用率分布．Pareto 蚁群算法对应轮询表的利用率只有一个超过85%，利用率在70%以下的仅有5个周期；基本蚁群算法轮询表的利用率跨度很大，最大已经达到100%，利用率在70%以下的很多，对比可知Pareto蚁群算法均衡网络负荷能力更强．

(a) 基本蚁群算法周期相时间散点图

(b) Pareto蚁群算法周期相时间散点图

图6 Pareto蚁群算法与基本蚁群算法的周期相利用率比较

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

5 结 语

在IEC 61375-1标准的基础上，构造出两个优化目标，这样既能优化均匀度，又能够保证将长短周期错开，全面提高轮询表质量．在此基础上建立模型并利用Pareto蚁群算法求解．比较证明，本文算法得到的解的性能比基本蚁群算法和多目标粒子群优化算法得到的解的性能更好，证明了利用本文算法构建MVB周期轮询表，更有助于MVB均衡网络负荷，提高网络处理偶发信息的能力，保证实时通信．

[1] 李 锐,李永宗,费巧玲,等. 一种多功能车辆总线周期扫描表优化设计方案[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]陈佳凯,韦 巍. 基于多目标粒子群优化的多功能车辆总线周期性扫描表的优化[J]. 铁道学报, 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]朱 俊,李 芳,王丽芳. 基于蚁群算法的多功能车辆周期扫描表的优化设计[J]. 铁道学报, 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]王永翔, 王立德. 多功能车辆总线周期扫描表的最优化设计 [J]. 铁道学报, 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周期信息的实时调度[J]. 计算机应用, 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]李士勇,陈永强,李 研. 蚁群算法及其应用[M]. 哈尔滨:哈尔滨工业大学出版社, 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.

国家自然科学基金资助项目(61305034)；高等学校博士学科点专项科研基金资助项目(20120041110008).

范 超(1989-)，男，硕士生，E-mail:zidonghuafc@126.com；顾 宏*(1961-)，男，教授，博士生导师，E-mail:guhong@dlut.edu.cn.

U269.9

A

10.7511/dllgxb201503014