基于改进型遗传算法的动态更新TTCAN系统技术

王飞平，洪 慧

(杭州电子科技大学 微电子CAD研究所，浙江 杭州 310018)



基于改进型遗传算法的动态更新TTCAN系统技术

王飞平，洪 慧

(杭州电子科技大学 微电子CAD研究所，浙江 杭州 310018)

作为CAN协议的扩展，TTCAN显著提升了总线的实时性和可靠性，但其运用的静态调度表在实际应用中灵活性较差，无法应用于网络频繁改变的动态系统。针对该缺陷，文中提出了一种基于改进型遗传算法的动态构造和更新TTCAN系统矩阵技术。改进了遗传算法编码、初始种群生成、突变步骤来优化TTCAN系统矩阵，并且特别适合在网络发生改变时动态在线更新系统矩阵。仿真和实际测试结果表明，改进型优化技术在动态网络中可以使总线带宽利用率始终保持在较高水平。

TTCAN；带宽利用率；动态更新；遗传算法

CAN总线基于事件触发，无法满足实时性要求较高的系统，因而实时性系统一般采用时间触发的TTCAN协议。TTCAN中周期型的消息的队列延迟为0，事件型的消息的队列延迟是由TTCAN调度表中消息窗口的分布所决定的，因而建立一个高效的时间调度表是优化TTCAN协议的关键[1-3]。但在实际总线系统中，网络经常需要发生改变，TTCAN的静态调度表在此时无法满足实际需要。

本文设计了一种在线动态更新TTCAN系统矩阵的方法，并针对该方法的实现改进了生成TTCAN系统矩阵的遗传算法。最后采用PSA消息集，以带宽利用率为性能指标验证了改进型遗传算法优化TTCAN系统矩阵的性能，并将算法应用于实际的动态网络中，验证了该算法的实际使用性能。

1 TTCAN系统矩阵

1.1 TTCAN协议结构

TTCAN 协议在CAN协议基础上，采用以时间为基准来控制网络中节点消息传输。在系统运行前生成静态调度表，可以保证在任一时间总线上只有一个周期消息在传输，避免由于竞争失败导致低优先级消息产生延时，消息的传输时间是确定可控的。系统运行时，TTCAN协议中的时间主节点发送参考消息，其余从节点在接受到参考消息时，开始同步自身的系统时钟。然后按照事先设定好的时间调度表，在指定的时间窗口内进行自身的消息传输，这个时间调度表就是TTCAN的系统矩阵(SM)。系统矩阵分为3种窗口：(1)独占窗。在该窗口范围内，只能有一个节点的一个消息在总线上传输；(2)仲裁窗。在该窗口内，可能有多个节点的消息准备发送，采用传统CAN总线的帧ID优先级仲裁决定发送次序；(3)自由窗。不传送任何消息，留待以后扩展总线使用。

1.2 TTCAN系统矩阵构造

本文算法分为两部分，首先是确定矩阵的基本参数，然后将矩阵的基本参数传入算法中运行，生成目标矩阵。为了更加直观，本文用国际标准PSA消息集[4]来验证。在构造系统矩阵前，需要确定以下系统矩阵基本参数，其中MG={M1,M2…M11,M12}表示消息集合,dm表示周期消息的截止期，pm代表消息的传输周期。dm≤pm表示每个消息的截止周期最大不超过其传输周期[5-6]。

(1)基本循环周期BC。有BC=pmin=Min{p1,p2…p12}，即选择消息集中所有消息的最小传输周期作为BC；

(2)系统矩阵时间T。由多个BC组成的调度表称为TTCAN系统矩阵，本文用符号T来表示一个系统矩阵从开始到结束的总时间，有T=LCM{p1,p2…p12}，其中，LCM表示最小公倍数。可以保证在一个系统矩阵内，所有消息的等待时间都不会超过其截止期；

(3)矩阵行数Row。根据TTCAN协议Row=2n(n≤6)，又有T=BC×Row，可得Row=8；

(4)矩阵列数Col。矩阵列数等于周期型的消息所需列数加上仲裁窗的列数，根据TTCAN标准，多个相邻的仲裁窗可以合并成一个，本文把系统矩阵最后一列设为仲裁窗。所以Col=Cmin+1，其中Cmin表示周期型的消息所需的列数，如式(1)所示

(1)

根据以上参数，构造的初始系统矩阵如图1所示。其中Part 1部分表示传输周期等于BC的消息，该部分的每一列只能放置一种消息；Part 2部分表示传输周期不等于BC的消息，由图可以看出，由于该部分的每一列中存放的消息的传输时间不同，导致该部分窗口有空闲的部分，通过优化矩阵中消息的分布，可以减少空闲部分，提高带宽利用率，这也是本文提出的算法优化的目标[7-9]。

图1 系统初始矩阵

2 改进型遗传算法

随着消息个数的增加，TTCAN系统矩阵组合的数量指数性增加。构造系统矩阵属于NPC 问题，适合采用遗传算法来解决[10]。TTCAN系统矩阵的优化目标明确，就是减小独占窗部分的宽度，增加仲裁窗的宽度，从而提高图1中Part 2部分的带宽利用率。本文算法采用带宽利用率作为适应度函数来控制进化方向，考虑到算法需满足TTCAN系统矩阵的约束条件，改进了遗传算法的初始种群生成、交叉和突变步骤。同时为了适用于动态更新系统矩阵的需求，采用矩阵编码和实数编码相结合的机制。下面分别介绍改进型TTCAN系统矩阵优化算法的几个关键步骤。

2.1 编码

编码是将一个问题可能的解从其解的空间转换到遗传算法所能处理的搜索空间[10-12]。针对于利用遗传算法动态更新系统矩阵问题，不能采用传统的符号、二进制等编码。这里采用矩阵编码和实数编码相结合的编码方案，矩阵编码可以用最直接的方法将个体基因的组合情况表示出来，具有比一维数据结构更大的数据存储空间[13]。实数结构体存储了网络中节点的所有信息，通过主节点发送轮询信息获得，当节点发生更新时，更新对应的数据即可重新运行算法生成一个系统矩阵。图2是采用矩阵编码代表一个系统矩阵的染色体，其中Mes代表周期型消息；Arb代表仲裁窗；Free代表自由窗。其中每个Mes消息体的结构如图3所示。

图2 染色体结构

图3 Mes 消息结构体

2.2 随机生成初始种群

图4 初始种群生成流程图

图4中Popsize为种群中个体数量；Row为矩阵行数；Col为列数；R，J，I表示当前的行数，列数和个体数。按照图5的流程图可以保证生成的个体满足TTCAN系统矩阵的3个约束条件。

2.3 适应度函数

遗传算法在进化搜索中基本不利用外部信息，仅以种群中每个个体的适应度值来进行搜索，从而确定进行交叉突变操作的个体，因此适应度函数的选取至关重要。本文选取Part 2部分总线带宽利用率U和Part 2部分所需的最小列数Cmin相加之和作为适应度函数[6]。适应度函数为

(2)

其中，带宽利用率部分只考虑系统矩阵独占窗部分，即独占窗中周期消息的传输总时间与独占窗的总宽度的比值。CLi表示第i列的列宽，取该列所有消息中最大的传输时间，在实际应用中，列宽应略>CLi，以确保消息传输完全，n为系统矩阵的列数。

2.4 交叉

交叉是传统遗传算法的关键步骤，将随机选择而来的两个个体部分基因进行交叉操作，从而产生新的个体。对于TTCAN系统矩阵，该操作不能进行，因为上文提到的系统矩阵限制，当进行交叉操作后系统矩阵就不能再满足要求[14]。

2.5 突变

在传统遗传算法中突变操作是按照突变率随机选择一个或多个基因，在合理的范围内随机的突变成另一个值。对于本文采用的矩阵编码染色体，影响适应度的因素是基因在系统矩阵的分布，改变其位置就会改变适应度值，所以本文采用的突变操作是随机选取两个消息，但两者的截止期和传输周期都要相同，然后交换它们的位置。

3 动态更新系统矩阵

TTCAN协议中的系统矩阵是静态离线构建的，当网络发生以下3种改变时，静态调度表的工作会受到影响，具体如下：(1)如果网络中新加入节点，当静态调度表中预留的自由窗口无法满足新增加节点的需求，则系统矩阵就无法再使用，只有关闭系统重新部署调度表；(2)如果网络中节点被删除，静态调度表只能将被删除节点所属的窗口闲置，导致带宽利用率降低；(3)节点的周期或者传输时间发生改变，会出现总线冲突导致静态调度表无法继续工作。为克服TTCAN的以上3种缺陷，本文设计了基于遗传算法的在线动态更新系统矩阵算法，流程如图5所示。

图5 动态更新系统流程图

系统开始运行时，启动并行监测网络的状态，一旦网络发生改变时，处理器会启用动态更新机制，利用当前 TTCAN 的空闲窗口发送网络轮询消息获得当前网络节点的参数信息，然后后台调用遗传算法计算新的调度表，计算完成后利用空闲窗发送网络更新消息，节点更新完毕后，开始运行新的系统矩阵。

4 实验

根据以上设计的改进型TTCAN系统矩阵优化算法，这里对其进行了性能评估和参数对比分析。首先，使用Matlab验证了遗传算法对于提高CAN总线带宽利用率的性能，算法参数中的种群个数选择50个，进化次数选择100次，突变率为8%。仿真结果如图6所示，其中横坐标代表种群进化的代数，纵坐标表示每代种群所有个体的平均适应度。如图6所示从最初一代到最后一代，种群的适应度稳步增加，最后趋于稳定。Part 2 部分的带宽利用率增加了4.3%，对于PSA消息集的TTCAN系统矩阵型的消息的实时性不变的情况下，减小了仲裁窗中发生总线竞争的几率，提高了总线的可靠性。并且算法对于带宽利用率的提高会随着网络节点数量的增加而增大。来说，意味着每秒增加了9.56 ms的仲裁窗时间，可以多发送73个非周期型的报文。

图6 种群适应度变化趋势图

图7 实际系统运行图

图8 节点增删时算法运行图

图7是采用改进型算法搭建的实际系统，主节点采用TQ3358开发板，从节点采用STM32F105芯片，系统有2路CAN总线冗余备份。在此硬件系统平台，模拟了网络发生改变时的性能测试。由图8所示，当网络中发生了节点的增删时，本文算法会根据网络中节点的改变自动重新生成新的系统矩阵，可以避免由于节点改变，系统矩阵中出现窗口闲置或者发生节点冲突，保证网络的正常运行。当节点增加时，改进型算法可以在线重新生成系统矩阵。但在传统静态调度表中，如果预留的自由窗口不满足新增消息的需求，则必须停止系统然后重新生成调度表。当删除节点时，改进型算法可以使总线带宽利用率保持在较高的水平，而传统算法只能闲置被删节点的窗口，导致带宽利用率降低。

5 结束语

本文以改进型遗传算法为基础提出了动态在线更新TTCAN系统矩阵技术。不仅优化了TTCAN的静态调度表，同时满足动态在线更新系统矩阵的需求。在网络需要发生改变的动态系统中，克服了静态调度表的缺陷，可以使得总线带宽利用率始终保持在较高水平。在实际的总线系统中，为提高总线的资源利用率提供了参考。

[1] Wang S,Zhang T.Scheduling design of auto-motive TTCAN control system based on average loading[C].Jinan:Intelligent Control and Automation,2010.

[2] Jang D, Han S, Kang S, et al. Communication channel modeling of controller area network (CAN)[C].Taiyuan:Seventh International Conference on Ubiquitous and Future Networks,2015.

[3] 李佳,朱元.CAN与 TTCAN通信延迟 时间的分析[J].清华大学学报,2006,46(2):261-265.

[4] 李运生,窦金生.TTCAN 系统矩阵的优化算法[J].自动化仪表,2012,33(6):8-11.

[5] 刘强,刘银年.基于时间触发的TTCAN协议[J].自动化仪表,2008,29(1):37-40.

[6] Schmidt K,Schmidt E G.Systematic message schedule construction for time-triggered CAN[J].IEEE Transactions on Vehicular Technology,2007,56(6):3431-3441.

[7] 夏鹏,朱琳,叶杰.变频器监控系统TTCAN调度优化算法研究[J].电气传动,2015,45(3):72-76.

[8] 刘鲁源,万仁君.TTCAN 调度算法及其在汽车控制系统中的应用[J].汽车工程,2005,25(1):60-63.

[9] 冯晓东,果艳红.TTCAN动态调度算法实现与仿真[J].电子测量与仪器学报,2008,22(2):81-85.

[10] 刘鲭洁,陈桂明,刘小方.基于矩阵编码的遗传算法研究[J].计算机工程,2011,37(13):160-162.

[11] 任子武,伞冶.实数遗传算法的改进及性能研究[J].电子学报,2007,35(2): 269-274.

[12] 郑权,忻尚芝,钱建秋.基于改进遗传算法的PID参数研究[J].电子科技,2015,28(11):5-8.

[13] 张超群,郑建国,钱洁.遗传算法编码方案比较[J].计算机应用研究,2011,28(3):820-822.

[14] Qiao X, Wang K F, Sun Y, et al. A genetic algorithms based optimization for TTCAN[C].Beijing:IEEE International Conference on Vehicular Electronics and Safety. IEEE Xplore, 2008.

Dynamic Update TTCAN System Technique Based on Improved Genetic Algorithm

WANG Feiping，HONG Hui

( Institute of Microelectronic CAD, Hangzhou Dianzi University，Hangzhou 310018,China)

As an extension of the CAN protocol, TTCAN improves the real-time performance and reliability of the CAN bus significantly. However, its static scheduling table is not flexible to be applied in dynamic network. A dynamic construct and update TTCAN system matrix technique based on improved genetic algorithm is proposed to solve this defect. The improved coding, the initialization population generation and the mutation steps were modified to optimization of TTCAN system matrix, and suitable for the dynamic online update system when the network nodes were changed. Finally, the simulation and the actual test results showed that the improved optimization technique could keep the bandwidth utilization at a high level in the dynamic system.

TTCAN；bandwidth utilization ratio；dynamic update; genetic algorithm

2016- 10- 09

国家自然科学基金(61107025)

王飞平(1992-)，男，硕士研究生。研究方向：嵌入式系统。洪慧(1979-)，男，博士，副教授。研究方向：嵌入式系统。

10.16180/j.cnki.issn1007-7820.2017.08.011

TN926；TP336

A

1007-7820(2017)08-040-04