0 引言

    时间触发以太网^[1]能够很好地满足工业的实时通信，以其较强的实时特性和确定性引起了航空电子技术领域的广泛关注^[2]。时间触发以太网中，时间触发（TT）消息由离线生成的通信调度表控制发送，调度表生成的好坏直接影响到网络通信的质量。正常状态下，调度表离线生成无法实现实时的重新调度，但网络中任一系统的变化都将需要新的调度表。从之前研究的成果来看^[3-5]，由于调度表生成其指数级增长的时间复杂度，表的变化将引起灾难性的情况，直接影响航空器的飞行和任务安全。避免已生成的调度表变化，重新在预留时间段进行消息调度就可以妥善解决TTE中TT消息的灵活调度问题，由此需要一种能够快速准确地寻找全局最优解的调度表生成方法降低已有消息的时间占用，以实现预留资源，应对随机产生的网络结构异变。

    遗传算法是一种利用自然选择理论和自然遗传理论设计的优化算法。在模拟自然界生物进化的过程中表现出很好的全局搜索能力，实现特定方向的最优化结果^[6-8]。通过对问题的深入分析，将调度问题转化为典型装箱问题并用相关算法进行求解，可以进一步提升对解的局部搜索能力，更快更为准确地找到全局最优解。

1 基本概念和模型定义

    参考STEINER W^[3]的模型设计并加以转化，将双向消息帧和虚链路作为重点考虑的因素，下面对TTE网络模型的具体概念进行定义。图1所示是一个简单的TTE示例网络，其中粗实线表示网络连接的实际物理线路，带箭头的细实线表示消息帧的发送链路，具有从起点到目的节点的方向性。

    数据流链接表示为l_ij=[v_i，v_j]，其中v_i和v_j分别表示链路两端的源节点和目的节点。P表示消息传输路径，是消息传输过程所需要的全部数据流链接矢量加和，如下式：

    虚链路由多个数据流路径P组成，在拓扑结构中，同一虚链路vl中的路径P具有相同的起始端节点和部分重合的消息传输链路，数学符号表述虚链路vl如下式：

    为准确描述时间触发消息在网络中的行为，下面对时间触发消息帧的传输参数进行定义：f{id，period，source，destin，timepoint，length}，其中id是帧的标识，period表示自源节点source至目的节点destin的时间触发消息发送周期。消息帧的调度用帧发送时刻进行描述，因此定义TT消息帧的在某一节点发送的发送时刻为参数timepoint，同时以时间单位为度量定义帧的长度length。参数包括id、source、destin和length等是由消息帧传输路径决定的常数。时间触发网络的TT消息调度即为对TT消息帧在节点处发送时刻的调度安排。

2 问题转化和算法设计

    为解决消息调度问题，将时间触发消息调度问题转化为典型的装箱问题，利用装箱算法可以实现原有遗传算法在解域局部搜索效率的大幅提高，形成混合遗传算法。

2.1 调度问题的描述和转化

    在一相对复杂的拓扑结构中，时间触发消息调度即为对于时间资源的调度利用，可以被转化为二维装箱问题。

    用参数periodmin表示需要调度消息的最小消息周期。在AS6802协议^[9]中的簇周期（cluster cycle）用LCM(period)表示，即为所有消息周期的最小公倍数，簇周期在整个消息传输过程中周期性地重复实现时间触发消息的连续传输。同时设置所有消息周期的最大公约数，用GCD(period)表示。通过折叠未进行资源分配的一维时间轴线(如图2)，将问题转化为二维图形^[5]，见图3(a)、(b)。

    为简化模型，引入时间片（time slot）的概念，假设在每一链路l中，消息最多利用一个时间片即可实现长度length的全部传输，设置时间片长度为T_STS，由此可以得出时间段的时间片个数为N_STS：

    当拓扑结构中两条路径P_a和P_b之间任一传输链接均不产生重合，节点就可以实现帧的同时传输。在时域范围内，假使将这样路径中的节点消息分为不同区域，时间片就可以实现交叠或部分交叠。问题转化的关键在于将路径不交叠可同时传输的消息进行派发，这需要对拓扑结构进行分区操作。对于讨论的星形和树型拓扑结构，定义了组（Group）的概念,在某一时刻根据消息传输的分布将互相联系的节点组成集合，以便于对网络拓扑结构的节点进行分区操作。在两个同属一个组的两个子组之间，若子组内的消息传输相互独立且不经过上层中心节点，则两子组内消息可以共享时域资源，实现同时传输，避免消息冲突的发生。

    对消息调度问题的转化减少了时间触发以太网中静态段消息传输的时间资源利用，同时很好地避免了消息传输冲突的发生，见图3(c)。

2.2 混合遗传算法设计

    装箱问题是一个典型的NP问题，无法通过准确的解法解决，遗传算法在复杂系统优化计算中的高效搜索可以适应大规模非线性不连续多模态功能^[10]。通过将遗传算法和装箱算法相融合，可以达到算法的全局和局部搜索能力的平衡。

    图4是混合遗传算法的流程图，包括初始化和遗传迭代的简要过程描述，下面将就混合遗传算法的具体实现进行详细描述。

2.2.1 个体设计

    个体参数应当包括以下几个关键数据：时间片分配、每一节点的时间分配、节点状态、目标函数值和适应度函数值等。

    在算法起始进行参数设置时应当对个体进行初始化，节点状态初始设置为State_Idle状态并且随机分配任务。消息集中的不同消息根据其所属组的ID分类安置，如果消息独立于其他消息，则将其放入Message_of_independent_group阵列；如果消息与其他消息同属某一组，则将其放入时间片进行资源分配。调度节点时间片分配，避免时间节点超出周期设置，最终确定节点所处工作状态，完成初始化操作。

2.2.2 适应度函数

    利用惩罚函数对调度条件进行约束，实现适应度函数功能，有向控制调节下一代子个体的生成。

    (1)避免冲突约束

    在时间触发以太网调度表生成过程中，实现链路中数据流传输互斥，避免冲突是至关重要的。因此，在设计惩罚函数时必须考虑保证避免冲突约束的实现。利用上文定义的相关模型参数，完成避免冲突约束的定义如下：

    根据约束条件的公式描述，定义惩罚函数，公式描述如下：

    式(7)中的ε表示极小的正值常数，以保证分母非零且为正。可知，两点间时刻间距越小，函数值随着时刻差的降低成倒数形式增加。

    (2)路径和内存约束

    链路在消息传输和收发过程中必然会由于链路端点在分发和接收消息产生相应的延时，控制中继链路节点在消息传输过程中的帧派发时间和存储延迟时间对于描述通信模型十分重要，利用式(8)～(10)描述消息帧通过某一节点的收发时刻保持在一定范围。

    max(hopdelay)表示消息经过节点的最大延迟上限，[vertex_x，vertex_j]和[vertex_j，vertex_y]分别表示某一传输路径中两个毗邻的链路端点特征，它们共享一个公共节点vertex_j。Membound由已知硬件参数决定，这一约束是区别于异步触发传输方式的时间触发通信的特性。惩罚函数设置如下：

    式（11）中，为保证惩罚函数对算法产生正作用，参数a和b设置为大于1的常数。

    (3)起点端到终点端约束

    为避免生成未能实现消息送达的调度，设置约束规范由链路起点到终点间的时间延迟，保证调度方案在规定时间内使TT消息送达。约束公式描述如下：

    根据算法设计需求，起点端到终点端约束的公式描述转化为惩罚函数Pnlt₃，见式（13），其中参数c是大于1的常数。

    为实现妥当的时间触发消息流安排，式（14）中得到的函数值Cost能很好地反映调度方案的综合性能表现。

其中，参数ω₁、ω₂和ω₃是调整3个惩罚函数影响比例的和为1的常数。从设计目标可知，Cost越大，遗传算法中基因保留在子代的可能性越小，因此设置适应度函数如式（15），个体适应度越大，表示越适应外部环境的需求。

2.2.3 遗传算子设计

    基于比例的选择算子设计保证了遗传概率和适应度函数的正相关。交叉算子根据遗传算法为下一代更好地遗传父代基因所设计，选择个体生成子代之前，使个体根据适应度值降序排列为一列。接着，个体j和个体j+1进行交配产生子代个体j，其中，参数j的范围在1～(PopSize+1)/2之间。剩下的子代个体由父代个体j和父代个体(PopSize+1-j)交配生成，其中，参数j的范围在1～(PopSize+1)/2之间。

3 仿真及结果分析

    为了进一步实现对混合遗传算法在时间触发消息调度的测试，对试验仿真环境进行了设置，树形的拓扑结构较为复杂，见图5(a)，能有效测试算法性能。

    图5(a)中每个交叉点表示一个交换机或终端系统，从图中可以看到，树形结构通过交换节点进行级联，由此可以根据核心交换节点的位置，人工对拓扑结构进行分区，见图5(b)。经过仿真得到用甘特图表示的消息调度结果，见图6。X轴表示时间片，Y轴表示树形结构的节点。在满足实时性要求的情况下，消耗时间片降低到96个。

    此外，对单纯遗传算法和混合遗传算法的适应性函数最终收敛情况进行比较，遗传代数和适应函数的关系可以清楚地反映在图7中。混合遗传算法在收敛速度较快，很快收敛到最优解附近，而遗传算法则收敛至局部解附近，收敛速度不佳。在遗传2 000代时，混合遗传算法收敛于适应函数值79.68，遗传算法2 000代时则收敛于适应函数值83.54。

    遗传算法与装箱算法融合产生的混合遗传算法克服了传统过早收敛于某一局部解的问题，并实现了全局最优解的快速搜索。

    每次仿真重复进行10次实验，记录如表1所示，可以看到，遗传算法在13节点1 300消息数的情况下表现不佳，这是单纯遗传算法陷于局部最优解和时间溢出造成的，反之混合遗传算法表现良好，由此可以看出其具有能够克服原有方法缺陷的特性。

    另外，通过表2的两种算法消耗的时间片可以比较得出，混合遗传算法较单纯遗传算法能利用更少的时间片实现完整TT消息通信功能。

    通过实验得出的静态段平均时间消耗统计对比，相对于遗传算法，混合遗传算法可以最大减少24.28%的时间资源浪费。

4 结论

    为实现时间资源的预留，保证网络传输灵活性，提出了一种基于混合遗传算法的TT消息调度表生成方法。通过问题转化和算法在解域空间的优化搜索，得到最优的调度方案。仿真实验对单纯遗传算法和混合遗传算法进行比较，混合遗传算法在搜索结果、收敛速度和时间片占用上都超越了纯遗传算法性能，能够满足灵活性设计要求，适应未来机载航空环境的消息调度。下一阶段将对TTE网络灵活性配置，实现调度表变化等方面的进一步研究。

参考文献

[1] KOPETZ H，ADEMAJ A，GRILLINGER P，et al.The time-triggered Ethernet(TTE) design[C].8th IEEE International Symposium on Object-oriented Realtime Distributed Computing(ISORC)．Seattle，Washington，2005：22-23.

[2] HATLEY D，IMTIAZ P.Strategies for real-time system specification[M].New York：Addison-Wesley，2013.

[3] STEINER W.An Evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks[C].31st IEEE Real-Time Systems Symposium，2010：375-384.

[4] STEINER W，DUTERTRE B.SMT-based formal verification of a TTEthernet synchronization function[C].FMICS 2010，Verlag Berlin Heidelberg：Springer，2010：148-163.

[5] Huang Jia，BLECH J O，RAABE A，et al.Static scheduling of a time-triggered network-on-chip based on SMT solving[C].Proceedings of Design，Automation＆Test in Europe Conference＆ Exhibition，DATE．Piscata way，NJ：IEEE Press，2012：509-514.

[6] 王庆祥，陈家琪.利用遗传算法优化TTCAN网络的时间调度系统矩阵[J].航空计算技术，2004，34(4)：24-27.

[7] 朱智林，刘晓华，韩俊刚.TTCAN周期性任务的优化调度算法[J].兰州大学学报，2005，41(4)：73-76.

[8] DING S，TOMIYAMA H，TAKADA H.An effective ga-based schedualing algorithm for flexray systems[J].Ieice Transactions on Ingormation and Systems，2008，91(8)：2115-2123.

[9] AREOSPACE S.AS6802：Aerospace standard Time-Triggered Ethernet[S]，2011.

[10] ROLICH T，DOMOVIC D，GRUNDLER D.Testing of sereval overlapping optimization methods for bin-packing problem[C].Information & Communication Technology Electronic & Microelectronics(MIPRO).Opatija：IEEE，2013：975-980.