机载网络时间触发通信调度设计优化与评价方法

2021-08-03何锋李二帅周璇李浩若龚子杰

航空学报 2021年7期

何锋，李二帅，周璇，李浩若，龚子杰

北京航空航天大学电子信息工程学院，北京 100191

航空电子系统(以下简称航电系统)涵盖飞机通信、导航、探测、管理、控制等所有电子系统以及支撑各系统间信息交换和资源共享的网络系统，是具有苛刻空间限制和功能/性能约束条件的信息密集型系统[1]。机载网络是航电系统的重要组成部分，其连接飞机物理结构空间中的相关电子设备，支持电子系统间的信息综合与功能综合，从而使航电系统成为有机整体，并标志着航电系统架构代际演化[2]。

随着计算机、通信等技术的飞速发展，航电系统对机载网络提出了更高的性能要求。采用时间触发(Time-Triggered，TT)通信机制可以避免传统事件触发(Event-Triggered，ET)通信机制下的资源竞争与共享冲突问题，从而提高信息传输的实时性，并保证信息交互的确定性。目前，以时间触发以太网[3](Time-Triggered Ethernet, TTE)等为代表的时间触发通信技术方案已得到广泛关注，但将其应用于机载环境中需首要保证合理的时间触发通信调度。这种通信调度设计协调TT消息，规划时间偏置，以避免TT消息争用物理链路影响其确定性传输，具有NP求解复杂度[4]，难以在多项式时间内完成，因此需要探寻求解优化技术。此外，从航电系统功能实现的角度出发，机载网络支持混合关键性流量以匹配不同优先级别任务，通信调度设计应关注消息延迟影响，保证消息尽快在规定时间内完成传输；并进一步支持应用层面任务执行，以拓展应用-网络联动调度，由此也对调度设计提出了进一步优化诉求。

目前，通信调度设计多基于有约束引导的启发式方法或者求解方法进行，通过设置网络拓扑和流量关系等约束，生成满足约束的TT调度表，典型包括可满足性模理论[5-8](Satisfiability Modulo Theories，SMT)、混合整数规划[9-12](Mixed Integer Programming，MIP)以及启发式算法[13-16]，这些方法在求解过程中具有不同的解算速度和优化能力，但一般都比较耗时。采用强化学习[17](Reinforcement Learning，RL)方法在多领域算法优化方面具备了一些成功案例，可以考虑利用马尔可夫过程描述增量化调度任务，通过设置调度状态、动作和奖励，以实现快速优化设计。不同的调度设计方法遵循不同的数学模型，采用不同的求解方式，同时也具有不同的运算特征和评价性能。为指导工程实际应用中调度方法的适应性选择与进一步发展，应结合调度求解能力与性能保障两个角度，从求解时间、可求解规模以及实时通信影响等多个维度开展对比分析研究。

为此，本文首先概要介绍时间触发通信的过程与特征；在其基础上给出不同约束引导下的调度模型，并发展出基于强化学习的调度方法；然后从求解能力和性能保障角度出发，建立具有普适性的调度设计评价指标；最后以典型网络拓扑为应用背景，针对不同调度设计方法开展对比研究，分析并归纳实际应用特征，以期探寻机载网络时间触发调度模式，并给出调度算法选择参考建议。

本文的创新点在于：形成了对时间触发通信调度设计方法的一致符号与模型描述，提出了时间触发通信调度设计评价指标体系与计算公式，针对不同调度设计方法应用特征并结合典型案例进行了性能对比和建议。

1 时间触发通信机制

时间触发通信着重满足安全关键任务中消息传输的实时性要求，并致力于保证数据传输的确定性与可靠性，在机载网络升级换代中扮演关键角色。典型时间触发通信组网方案包括MIL-STD-1553B[18-19]、时间触发协议[20](Time-Triggered Protocol，TTP)、时间触发控制器局域网[21](Time-Triggered-Controller Area Network，TTCAN)[22]、TTE以及时间敏感网络[23](Time-Sensitive Network，TSN)，其主要技术汇总如表1所示。这些组网方案基于时间触发通信进行调度设计，各个节点设备根据固定时刻驱动网络上的所有活动，可以有效保证航电系统对信息交互的实时性和确定性要求。TTE、TSN等新一代交换式互连技术更是凭借着高带宽利用率、可扩展组网规模等优势，能够很好地满足机载系统发展需求。

表1 典型时间触发通信组网方案技术汇总

本文以典型TTE网络为应用背景进行时间触发通信调度设计与评价研究，其可支持TT流量、速率约束(Rate Constrained，RC)流量和尽力传输(Best Effort，BE)流量混合关键性传输[24]。图1给出包含三个端系统与一个交换机的TTE网络示例，其中发送端1发送一条周期为3 ms的TT流量以及BE流量，发送端2发送一条周期为2 ms的TT流量以及BE、RC流量，交换机对来自于2个发送端的流量进行综合，向接收端发送集成流量。

图1 TTE网络中流量的传输过程

考虑时间触发通信的具体过程，当多条流量在交换网络中传输综合时，TT流量在全局时钟同步机制基础上，通过静态规划传输时间窗口并离线生成时间调度表，可以实现无冲突传输，从而有效改善时间确定性和传输可靠性。RC流量遵循事件触发通信机制，缺乏事先规划好的传输时间窗口，势必会与其它事件触发消息竞争端口输出，导致传输过程存在很大的不确定性；而且其与更高优先级的TT流量在传输过程中相遇时，采取避让(集成)策略，将进一步增加传输不确定性。BE流量为传统以太网通信方式，具有最低优先级且无需服务质量(Quality of Service,QoS)保证。

2 基于约束引导的调度设计

2.1 SMT方法

SMT问题是布尔可满足问题的拓展，用于求解SMT问题的自动化工具被称为SMT求解器，常用的有Yices、Z3等。由于TT消息在传输过程中受到严格时间约束，可以根据网络拓扑及配置参数表示约束条件，将其转换成SMT一阶逻辑形式，并利用SMT求解器求解，从而实现TT通信调度设计。文献[5]首先提出这种基于SMT的调度设计方法，其针对多跳网络给出了背靠背传输模式下的调度约束条件，并通过增量化的方式提高了求解速度；进一步，为了兼顾RC消息传输实时性，将TT消息间隔视作孔隙，提出了多孔传输模式下的调度求解方法。文献[6]改进了传统基于静态SMT的TT调度方法，以获得最佳离散间隔来减小RC的端到端延迟。

1)基本周期约束：任意消息fi在其传输路径pi,j上的任意输出端口τr处的发送时刻非负，且能保证fi在其传输周期内发送完成。

2)路径依赖约束：任意消息fi在其传输路径pi,j上两个相邻的输出端口τr、τs的调度时刻受到交换机缓冲区深度、存储空间大小以及技术延迟等限制。

3)端到端传输约束：任意消息fi的端到端传输延迟fi,j,r·etedelay不超过其截止期限。

4)同步转发约束：考虑多播消息fi在输出端口τr首次出现传输路径分离，其在τr及前序端口处的调度时刻均应相同[25]。

5)传输开销约束：任意输出端口τr处TT时间片数量最小，也即TT消息背靠背传输[6]。

6)无冲突约束：任意两条消息fi、fk，若其传输路径pi,j、pk,l均经过输出端口τr，则fi、fk的发送时刻应保证两消息在τr处不发生竞争冲突，可表示为

∀τr∈pi,j∩pk,l,

{fi,j,r·offset+a×fi·period≥fk,l,r·

offset+b×fk·period+fk·length}∨

{fk,l,r·offset+b×fk·period≥

fi,j,r·offset+a×fi·period+fi·length}

(1)

式中：HPr表示流经τr的所有消息的超周期。

2.2 MIP方法

MIP方法是一种线性规划方法，其在给定线性约束条件下，研究线性目标函数的极值问题，目前有Gurobi、CPLEX等多种求解器，可实现大规模约束变量和约束条件下的MIP问题快速规划。由于其天然支持带目标条件的性能优化求解，已被许多学者用来实施通信调度设计研究。例如，文献[9]引入帧间间隔和同步误差等时间参数，并考虑与应用层匹配，实现了应用响应时间和端到端延迟的多目标优化；文献[10]进一步强调消息对任务的依赖关系，通过预先处理减少约束变量，可在合理时间内完成工业规模的消息调度设计；文献[11]分析TT消息发送、传输和接收的完整过程，以消息流累积端到端延迟为目标进行优化设计；在此基础上，文献[12]将网络与分区联合考虑，给出了保证分区层端到端延迟最小时的通信调度结果。

基于MIP方法进行调度设计也应满足与SMT方法相似的约束条件。但应注意两种方法所针对的求解域不同，MIP方法无法实现SMT方法中无冲突约束的Either-Or语句，所以需对式(1)进行转换表述，针对端口τr处的任意2条TT消息fi、fk引入二进制决策变量βi,k,r有

∀τr∈pi,j∩pk,l,

{fi,j,r·offset+a×fi·period+βi,k,r×φ≥

fk,l,r·offset+b×fk·period+fk·

length}∧{fk,l,r·offset+b×fk·

period+(1-βi,k,r)×φ≥fi,j,r·offset+

a×fi·period+fi·length}

(2)

式中：φ取值足够大以保证βi,k,r=1时第1个不等式恒成立，而βi,k,r=0时第2个不等式恒成立。此外，MIP方法支持优化设计，常用优化目标是最小化消息平均端到端传输延迟，即

(3)

因为该优化目标的引入，应用MIP进行调度设计的过程中通常可以省略端到端传输约束。

2.3 启发式方法

启发式算法也是解优化问题的一种常用方法，其根据某种启发式信息对已知的可行解进行改进，通过若干次迭代在相对短的时间内获得满意解，典型包括遗传算法(Genetic Algorithm，GA)等。通常启发式算法获得的解极有可能是近似解，而不一定是最优解，但由于启发式算法实现简单，且支持大规模快速运算，所以目前也已被广泛应用于时间触发通信调度研究中。例如，文献[13]综合考虑TT与RC消息的可调度性，以RC端到端延迟最小为优化目标，进行TT消息调度设计；文献[14]在此基础上，结合消息分包、VL分配与路由等因素影响，通过设置消息候选列表，进一步提高了消息可调度性及传输紧性；文献[15]针对系统应用、分区或计算模块增加导致通信流量增加的情况，完成了通信消息的增量式调度设计；文献[16]在分区模型基础上，设计TT消息的非多孔性调度表，可以大幅减少RC消息的端到端传输延迟。

基于启发式方法进行调度设计同样也应满足与前文一致的约束条件，其公式化描述可以直接借鉴前文经验。值得注意的是SMT或MIP方法可直接应用相应的求解器，在设定求解变量、输入约束条件后进行黑盒运算，便能获得满足约束的调度方案；而启发式算法还应设计迭代搜索策略以保证优化设计的运行速度和近似程度。一种通用方法是首先比较消息fi的端到端延迟与其截止期限，以判定是否存在可行调度解。令

(4)

显然，若cTT/RC>0，则存在fi使得

fi,j·etedelay>fi,j·deadline

(5)

即不可调度；若cTT/RC=0，则恒有

fi,j·etedelay≤fi,j·deadline

(6)

即可调度。在此基础上，定义

(7)

以表征不同可行调度解之间的性能差距，并设置代价函数

Cost=ωTT×δTT+ωRC×δRC

(8)

式中：δTT/RC为调度可行度，有

(9)

其中:ωTT/RC为TT或RC帧的惩罚权重。当不可调度时，ωTT/RC取较大数值以保证搜索快速向可行区域推进；当可调度时，ωTT=0以保证搜索向RC延迟更小的性能优化方向推进。

3 基于强化学习的调度设计

基于约束引导的调度设计应用于工业规模机载网络往往存在耗时较长的缺陷，为实现工业规模下机载网络的快速调度设计，可采用基于强化学习的设计方法。强化学习通过与动态环境的即时交互获取状态信息，并反馈强化信号对所采取的行动进行评价，经过不断学习和选择实现最优策略。将其应用于时间触发通信调度设计，需要首先进行适应性定义，例如文献[17]将状态state定义为输出端口当前的消息排布方式，将动作action定义为TT消息在端口的调度发送时刻，即若干fi,j,r·offset，将奖励reward定义为调度成功与否以及端到端传输延迟。

在训练初期，为了能够尽快找到端到端延迟较小的调度表作为训练样本，使用树搜索方法结合深度优先与最优优先进行初始搜索，并剪掉明显不能找到结果的分支加快搜索。

在训练阶段，首先用初始搜索所得样本对神经网络进行预训练，以改进均方差为目标函数

(10)

获得一条完整的训练轨迹，即可保证在每个状态state(t)，神经网络的输出out(t)逼近action(t)。为便于进一步探索和适应，需要对输出out提供一定噪声，可以out为中心，取宽度有限区间均匀采样作为fi,j,r·offset。然后改进贪婪策略进行轨迹收集，在每个状态处选择尽量减小端到端延迟的动作action，将策略参数化并寻找最优参数保证所有消息的端到端延迟最小。由于此时搜索空间较训练初期较小，应使用较小的学习率，可设置目标函数为轨迹总奖励值，有

(11)

式中：P(t,θ)为t时刻策略选择已执行动作action的概率;reward(t)为t时刻执行action的奖励值。在此基础上，对目标函数求梯度以构造损失函数，从而保证目标函数以最快的速度向端到端延迟最小的方向收敛。考虑到fi,j,r·offset可选择范围极大，直接计算梯度会导致梯度过大而无法优化，故对其进行对数化处理，有

(12)

为了获得更多样化的样本，可以采用n步展开方法进行搜索，即每到一个状态时，模拟之后n步搜索。如果在n步之后可以满足预先设定的最低端到端延迟要求，则继续采用这一条轨迹；如果没有满足要求或者消息无法调度，则选择其他轨迹。注意模拟最大深度n根据消息总数等特征确定，以避免n较小时过早收敛到初始轨迹而陷入局部最优解，而n过大时导致计算开销庞大；预先设定的阈值通过动态方法确定，可以根据搜索的深度进行自适应调整。

此外，这种基于强化学习的调度方法具备一定的泛化能力，在训练完成后可以直接应用于消息分布相近的调度求解问题中。

4 调度设计评价

航电系统综合化程度的不断提高导致机载网络在组网拓扑、消息通信规模、消息传输干扰等方面的复杂性日益增加，为时间触发通信调度的设计及优化也带来了巨大的挑战。应回归时间触发通信调度设计的求解能力与性能保障两个角度，建立合理的评价指标体系以开展不同调度设计方法的有效性评估。

4.1 求解能力

调度设计的求解优化重点关注调度方法的求解时间T和可求解规模S，是判定调度方法是否适用的最根本指标。

求解时间是调度方法开始运行到结束运行的时间跨度，可表征调度方法的执行效率。受限于求解器自身运算速度或者迭代搜索策略设置等因素影响，可能存在调度算法长时间运算而无法获得封闭解的情况，考虑到这无法满足工业实际应用需求，对求解时间加上限约束T≤Th，典型可取Th=10 h等[11]。求解时间达到该上限而仍未获得封闭解则可等价认为此时无法调度，所以应注意结束运行时并不一定能够获得可行调度解。

可求解规模具体通过网络负载体现，强调在相同网络拓扑结构的基础上，增加消息条数以提高网络负载，判断调度方法在求解时间上限范围内能否获得封闭解，或者统计能得到封闭解时所对应的最大平均负载[11]。假设网络输出端口总数为Nport，且有Nr条消息流经端口τr，记作{f1,f2,…,fNr}，则网络平均负载

(13)

4.2 传输延迟

调度设计的性能优化重点关注调度结果对系统实时性的影响[26]。消息在网络传输过程中的端到端延迟是一项重要衡量依据，显然消息在规定的截止期限内越快到达目的节点，则网络系统的实时性保障潜力越强。

fi,j,lasti,j·offset-fi,j,firsti,j·offset

(14)

式中：firsti,j,lasti,j分别表示fi在传输路径pi,j上的第一个输出端口和最后一个输出端口。

(15)

RC的服务曲线受到TT强制抢占的影响，有

(16)

(17)

通过对比RC消息最坏延迟与截止期限的相对大小关系，即可进行消息是否满足实时要求的基本判断，并可在实时要求保障条件下进一步计算消息传输时间裕量开展评价分析[1]。

在此基础上，可以分别计算TT消息和RC消息的端到端最坏延迟DTT和DRC的平均值以反映调度设计对延迟影响的统计特征。

4.3 调度模式

背靠背[7]和多孔[29]两种调度模式的不同也会极大影响系统的实时性能。图3以不同直线表示不同端口，不同色块表示不同TT消息调度窗口，给出了两种调度模式的对比。背靠背模式下TT消息在周期内紧密排列，RC消息有较长的完整传输时间窗口；多孔模式下TT消息在周期内分散排列，RC消息可利用TT间隔迅速响应。

图3 时间触发通信调度模式

对于调度模式的评价指标可统一表征为TT窗口的均匀程度ζTT。考虑HPr内流经τr的TT帧个数

(18)

这些帧按时间顺序排列从而构成有序集合{f1,f2,…,fNfr}，将帧fi与下一帧的孔隙间隔记为θi，则有

θi=fi+1·offset-fi·offset-fi·length

(19)

特殊地

θNfr=HPr+f1·offset-fNfr·offset-

fNfr·length

(20)

此时，TT调度窗口孔隙间隔的标准差

(21)

由于所有帧间隔之和为定值

(22)

可推导得到λr取值范围

(23)

当

{θi}={0,0,…,φr}

(24)

时，λr取最大值，对应于完全紧密调度。当

(25)

时，λr取最小值，对应于均匀多孔调度。为便于TT窗口均匀程度概念直观理解，即ζTT越大，程度越高，考虑λr为成本型指标，对其进行归一化处理，并综合全网端口有

(26)

5 实验分析

5.1 案例设计

考虑一个典型工业规模下的组网案例[12]，拓扑结构如图4所示，由10个端系统和7个交换机构成。设计8种不同规模流量配置的实验案例，其TT/RC消息条数NTT/RC、骨干网络负载率STT/RC以及网络总负载S如表2所示。其中，消息参数配置采用随机方法生成，源节点和目的节点从拓扑结构端系统列表中随机选取，消息帧长在[127,1 538]bytes内随机选择，且TT周期和RC带宽分配间隔在[2,128]ms内按照2的幂次率随机生成；消息传输路径结合最短路径算法和流量均衡策略进行自动分配，以避免因为某条链路或某个区域过于拥堵，而出现系统无法调度求解或调度性能极差等极端情况；各案例采用相同RC配置信息，以充分体现TT调度设计对RC通信延迟影响。

表2 实验案例配置

图4 工业规模组网案例

为有效评价调度方法性能，在Eclipse环境下集成SMT求解器Z3和MIP求解器Gurobi，搭建综合调度设计平台，开发实现基于SMT、MIP、GA以及RL的设计方法，并分别应用各种方法针对上述各实验案例进行调度设计与结果统计对比。

5.2 求解能力对比

调度方法基本求解能力体现于求解时间和可求解规模。由于案例设计中已给出流量规模，且不同调度方法能否求解可通过求解时间是否达到允许上界进行统一表征，故此处仅给出不同案例配置下的求解时间对比，如图5所示。

图5 不同调度方法求解时间对比

对于规模较小的配置情况，SMT和MIP方法应用成熟求解器可以在1 min内快速完成调度设计，GA和RL方法相对时间较长，但仍可在20 min 内完成调度求解。随着消息条数增加，SMT方法最先无法完成调度，在本实验研究过程中最多可调度180条TT消息；MIP方法借助于Gurobi的强运算能力，具有优于SMT的可求解规模，但其求解时间随消息条数增多而急剧增加，在时间上限内最多可调度300条TT消息;GA和RL的求解能力逐渐凸显，尤其RL可以实现更快速的调度设计。当TT消息条数达到400时，仅有GA和RL方法可以进行调度设计，其求解时间分别为4.5 h和30 min。

此外，应注意SMT和MIP方法可得到稳定的调度设计，即相同配置情况下多次运行结果高度一致。而GA和RL方法需要搜索迭代，具有一定的随机性，故相同配置情况下多次运行结果存在明显差异，且求解时间与设置的迭代次数正相关。

5.3 传输延迟对比

为全面对比不同调度算法对消息网络传输延迟的影响，对各算法下TT端到端延迟和RC最坏端到端延迟进行统计，如图6所示。其中SMT方法和MIP无法支持所有案例配置，仅给出其所支持配置情况统计结果。

针对TT延迟，不同调度方法对比如图6(a)所示。SMT方法仅给出可行调度方案，而没有优化策略，故其TT延迟远高于其他调度方法，在规模较小的配置情况下也达到毫秒级别。MIP以TT延迟最优为目标进行优化调度设计，故其TT延迟明显优于其他调度方法；并且随网络规模扩大TT延迟保持在200 μs附近小幅波动而未体现明显增加趋势，这是由于实验配置中TT带宽占比在20%以下，MIP调度方法可在各端口处找到合适的时间窗口，保证TT及时转发传输。GA和RL方法的统计曲线重合度很高，在TT条数不超过200条的较小规模配置情况下，其延迟明显低于SMT方法且略高于MIP方法；在中等规模配置情况下，会随网络规模扩大而增加但仍可保证亚毫秒级别；在TT条数超过300条的大规模配置情况下也可保证延迟不超过1.5 ms。

图6 不同调度方法传输延迟对比

针对RC延迟，不同调度方法对比如图6(b)所示。由于RC延迟受到高优先级TT流量影响，故不同调度方法下的RC统计曲线均体现出随TT规模扩大而增加的整体趋势。SMT和MIP 两种算法下RC最坏端到端延迟分布基本相同，这是由于2种算法均采用背靠背调度策略，可用于RC传输的TT调度窗口间隔相似。GA和RL方法在调度过程中考虑以RC延迟为优化目标调整调度策略，较SMT方法和MIP方法具有明显的RC传输优势，平均优化程度分别可达到7.97%和12.35%。

5.4 调度模式对比

调度模式通过TT窗口均匀程度ζTT反映，不同实验案例配置下各种调度方法的ζTT以及TT和RC平均端到端延迟DTT/RC(ms)如表2所示，其中“—”对应表示该案例配置下该调度算法无法求解。可以发现SMT和MIP方法的ζTT较GA和RL方法更小，这表明前两者更倾向于背靠背调度模式而后两者更倾向于多孔调度模式。注意即使背靠背调度模式下，TT窗口间也会天然存在图1所示消息帧周期传输所带来的孔隙，所以SMT和MIP 两种算法的ζTT并不是一味偏向于较小的数值，此处仅以相对大小给出调度模式的倾向性。

在此基础上，为进一步直观展示ζTT对流量传输延迟的影响，利用表3数据绘制4种调度方法下的TT窗口均匀程度与传输延迟关系图，如图7所示。蓝色折线对应于TT流量，可以发现ζTT与DTT无明显相关性，这是由于ζTT以端口为对象，分析特定端口处所有TT帧的窗口排布，而DTT以消息为对象，分析特定消息在其传输路径上的调度时刻。红色折线对应于RC流量，从图7(a)至图7(f)中均可观察到DRC随ζTT增加呈先减小后增加的趋势，且存在明显转折点保证DRC更小，这说明较背靠背调度或均匀调度而言，TT窗口孔隙适度的调度更利于RC流量在网络中的传输；图7(g)～图7(h)的折线虽然仅有增加的趋势，但也符合上述结论。