分布式综合化航空电子网络拓扑优化技术

邱 征，魏雪菲，王世奎

（中航工业西安航空计算技术研究所，西安 710065）

0 引言

IMA（Integrated Modular Avionics）是一种先进综合航空电子技术。IMA 技术采用统一的通信网络进行互联，采用标准、通用的设备和网络减少航空电子系统开销和重量［1］。IMA 综合化架构带来功能综合、资源集中与系统耦合的问题，目前仅能通过手动方式优化IMA 架构设计与业务分配。国外提出一系列优化算法针对功能分布、互联拓扑和资源分配进行优化［2-4］，能够较好地优化航电架构，但尚需考虑航电网络本身通信延迟、交换容量、线缆重量等开销和性能。这些指标在分布式综合化架构（DIMA）下更加重要。AFDX 网络［5］是一种主流的航电交换网络，采用星型拓扑。AFDX 网络端系统通过交换机互联通信，交换机可以转发端系统、级联交换机的消息。AFDX 网络适合混合安全关键系统，它采用消息静态路由、流量控制、链路划分、带宽分配等手段来保证通信确定性，同时还通过物理连通与逻辑同传的双冗余机制来保证信息的可靠性。

AFDX 网络架构设计核心在于受限条件下路由规划和确定性调度机制［7］：物理链路余度、端到端延迟、带宽预算分配、混合关键业务并发、信息可靠性等限制。Charara 提出一种半自动端到端延迟证明与计算方法［8］。Zhang 提出一种自动最小化平均网络负载的VL 路由方法［9］。Al Sheik［10］提出通过优化消息载荷和速率降低网络负载。Carta 在连接和节点数一定的情况下，考虑带宽隔离约束，提出一种自动生成VL 路由方法［11］。

目前所有网络优化方法均基于网络拓扑。针对规模、延迟、开销等目标，本文提出一种基于多目标优化的最优网络拓扑的计算模型与方法。网络拓扑优化的目标是计算获取一个优化的拓扑，包含交换机数量、交换机位置和物理连接，包括：

1）功能业务特性的大量端系统部署信息；2）功能交互所需的一系列信号，需要带宽、延迟、隔离约束；3）终端物理安装位置和线缆路径的物理长度；4）链路和交换机的属性，包含重量、开销、可靠性和端口数。

本文针对AFDX 网络协议特性作了两处简化假设。首先，路由是作为端到端通信计算，没有采用多播VL。其次，双冗余的AFDX 网络中仅考虑单链路通信，假设两条链路上的通信能力一致。

1 网络拓扑模型与多目标优化算法

1.1 拓扑结构模型

AFDX 拓扑采用设备D 和连接L 描述。设备由一组端系统DE和一组交换机DS组成。两个设备之间的连接是点对点通信。网络拓扑可以通过无向图G=（V，E）进行建模，节点V={DE，DS}，边E={E1，…，En}，其中Ei=（Vp，Vq）。AFDX 拓扑图受更多限制：1）端系统节点通常只有一个边；2）交换机节点有多个边，但是节点边的最大数量=交换机端口数目pmax；3）两个端系统之间不能有边。

AFDX 网络拓扑图可以涵盖业务拓扑、物理拓扑，网络拓扑设计目标包括驻留在端系统DE上的任务T。所有任务T 的信号集S 特定，它是两个任务之间的直接通信，例如Sk=（Ti，Tj）。信号不是一个单独的数据，而是两个任务之间通信预定义蓝图，蓝图需要优化设计。对于每一个信号Sk，它的路由必须能够从源任务驻留设备DE（Ti）到目的任务驻留设备DE（Tj）。一个完整的路由（在图论中为路径P）可以采用设备、链接、交换机列表进行定义，例如Pk=（D1E，L2，D2S，L3，…，D7E）。路由必须由源设备开始，到目的设备终止，并且拓扑中间都是正确完整连接，且没有物理断开。

在网络拓扑中，每个交换机或连接上的信号数量、容量有限，可以通过一个简单的资源模型表达。信号资源需求如式（1）：

索引1 到n 表示网络拓扑中使用不同资源类型，最主要的资源类型为带宽。另外，像CPU 负载、缓冲负载或者信号数等也可以考虑。

交换机和连接提供的每个资源类型ri∈R+，其资源都是一个正数。只有交换机、物理连接（虚拟连接）能满足信号所需最小资源时，信号才能分配到该交换机或连接上。一旦分配完成，需要的资源数量就被消耗，其他信号就不能再使用该资源。交换机和链接上分配的信号所需要资源之和，必须小于等于其对应的每个资源类型所拥有的可用资源。

此外，任务应该考虑隔离约束δ，隔离约束定义：两个任务不能在一样的设备、设备类型、位置或者这三者的组合上。隔离任务的信号，除了有相同的源或目的，在它们的路径中不能再有任何相同的节点或者边。如果需要不同的安装位置，链接必须采用单独的物理线缆。

网络拓扑受限于航电物理构型剖面。剖面可以通过网络安装位置I，线缆路由C 和连接点J 建模。每个端系统的位置已知，交换机位置也是从可供安装的位置中选择。交换机的布局同信号一样，受相似的资源模型限制。安装布局位置为每一个不同类型i 提供基础资源ρi∈R+，ρi为交换机所需要消耗的资源。从而限制每个安装位置的交换机数量。线缆路由是位置之间可能的物理链接，它的属性通过长度进行刻画。线缆路由通过连接点进行分割和连接。位置、线缆路由和连接点形成了剖面图GA=（VA，EA），其中VA={I，J}，EA=C。

1.2 拓扑优化方法

通用的优化方法是生成一个过设计的拓扑，再基于目标函数和约束条件缩小该拓扑。首先需要建立一个能满足需求的初始拓扑，再迭代优化该拓扑。假定采用的输入如下：

1）所有已经分配任务的端系统集合、信号列表、资源需求和隔离约束；2）网络平台：包含由信号、基础资源和端口数量刻画属性的交换机和同样由可用资源进行刻画的链接；3）由位置、基础资源及线缆路由组成的构型剖面。

图1 拓扑优化的一般方法

过设计的拓扑命名为最大化网络，可通过图1进行描述。该最大化网络在每个位置按照基础资源限制，摆放尽可能多的交换机。它为每个端系统和每个交换机引入一个链接，不考虑每个端系统只能有一个链接的限制。此外，为每一对交换机之间引入一个链接。按照此规则建立的最大网络，拥有|DE|个端系统，可以布局|DS|个交换机，|DS|2+1/2|DE|+|DE||DE|条链接。在第2 阶段，所有的信号在最大网络中进行路由，因此，最大网络所有用到的要素形成优化拓扑，如优化目标可以为交换机和链接的最小数目。优化后的拓扑必须满足交换机和端系统的最大端口数目要求。

最大网络的创建是一个预处理步骤。以优化拓扑为目标的信号路由是一个组合优化问题。它可以通过一个二进制程式（binary program，BP）进行公式化。通常BP 是找到一个的二进制向量x，将其最小化。

其中，x 是求解向量，f 是开销向量，A 和Aeq包含一个任意数量的线性等式和不等式。

拓扑优化问题解决向量编码如式（4）：

对每一个交换节点Vj，其资源类型k 的可用资源会限制该交换机上信号的最大数量。同理，表示每个链接Ej存在不等式：

|DS|+|E|资源不等式组成了Ar。

信号Si和Sj之间的隔离可用以下不等式表示：

上述不等式表示对于每对隔离的信号其每个交换机使用。所有的隔离不等式组成矩阵Aδ。

对于每个交换机|Vj|和链接|Ej|需要两个不等式，将xP和xV、xE关联起来。不等式如式（10）：

确保如果至少一个信号用到它，则使用变量为1，另外：

如果没有信号分配给它们，则强制使用变量为0。使用约束由AE和AV组成。

最后，每个交换机和端系统最大链接数由以下不等式限定：

对于端系统b 为1，对于交换机b 为pmax。这个|DS|+|DS|的不等式组成了矩阵Aport。

BP 计算最大网络中每个信号的正确信号路径，该路径包括上述所有等式和不等式：

并且

1.3 优化加速方法

BP 问题属于一类NP 难题。路径编码部分（xP）的x 占变量大部分，它表示每个可能的路径。为了减少变量数目，xP可以通过向量xR简化。xR为每个信号i 编码一个预计算路径集合Ri1，…，Rim。所有信号路径就从该预计算路径集合中选择。xR中变量个数受限于m|S|，用户可以定义m。在Yen 的算法中建议最大网络选择从源到目的设备的m 最短路径［12］。通过使用候选路由，路径约束等式就可以简化。BP中所有其他的等式和不等式，也需要相应修改来适应路由替换。例如，一个路由替换原路径所消耗资源。使用预计算路可能不会达到全局最优。上述问题可以通过混合整数线性规划（MILP）或者布尔可满足性（SAT）解决。通过问题模型化可以计算全局最优解。开销向量f 增加的开销可以分解到所有的交换机、链路或者路径部分。因为航空电子系统的设计（包括网络）遵从多个目标，因此提出一种多目标的扩展。替换掉一个开销变量f，可以假定以下公式已经最小化。

通常这些开销存在部分冲突，不存在一个通用的最优解。因此，在多目标优化中提出了计算Pareto最优解。Pareto 最优解是一个折中最优解的集合。拓扑优化中全局的Pareto 最优解通过Pareto 前沿采样（Pareto-Front-Sampling，PFS）计算。PFS 是由Ozlen［13］提出的一种迭代外部算法。它解决了一系列单目标BP，通过变动约束使得每次迭代都能找到一个有效解。每次迭代使用一个标准的BP 解决器。参见文献［3］中使用的PFS 算法细节。

2 机载网络拓扑与业务

机载网络拓扑规模包含交换机、链接线缆规模。交换机的规模固定，采用mS进行定义。对于线缆链接，需要每种长度的规模，再通过单独线缆长度相乘，得到总长度规模。链接的长度通过剖面模型的最短路径获取。对于每一个链接，其规模为miE。开销向量为：

仅针对交换机计算操作中断开销（Operational Interruption Cost，OIC）。OIC 是因网络失效导致的通信中断延迟开销，依赖于平均失效间隔时间MTBF给定的交换机可靠性。

2.1 A320 场景

通过类320 场景验证网络拓扑优化。希望得到一个涵盖4 个航空子系统，包含信号、任务和端系统的网络优化拓扑。参照A320-200，定义通风控制系统（VCS），放气系统（BAS），充气系统（PS）和过热检测系统（OHDS）。图2 描述了系统的任务和信号。信号由源端到目的端函数的所有参数组成；可以包含几个独立的消息。每个系统有两个独立的线缆，因此，它们的信号必须隔离。总共需要分配52 个信号。每个系统有两个控制器。此外，在PS 和OHDS之间还有一个通用的外置交换机通信。

图2 任务信号及隔离

端系统和交换机有7 个可安装位置，包含鼻翼、中部和尾部。鼻翼位置可以驻留1 个交换机，中部和尾部分别驻留2 个交换机，航空电子中间位置最多可摆放4 个交换机。鼻翼位置到中间位置的访问时间假定为5 min，中间位置到尾部的访问时间假定为45 min。另外，给出可能的线缆拓扑连接。每个线缆路由根据飞机外部尺寸分配一个固定长度。

图3 任务与端系统的映射

图3 展示了IMA 模块的系统功能分配。有4 个拥有控制器功能的核心计算模块（CPM）和10 个连接外围功能的远程数据接口单元（RDC）。

网络由5 个端口，重0.4 kg 的交换机组成，MTBF 设置为100 000 飞行小时，连接线缆指定为0.1 kg/m。交换机没有带宽限制，可以假定这52 条消息在一个单独的交换机或者链路上都可行。优化设计任务是找到具有最低规模和OIC 的网络拓扑结构。初始拓扑和路由可以是手工定义，实现两种自动优化：首先，算法的信号路由优化，基于初始手动拓扑验证改进后的信号路由。其次，拓扑规模和OIC的优化，计算Pareto 优化拓扑。最后，在简化预计算路径的下重复拓扑优化。同时评估所有研究的目标值、拓扑和运行时间。

2.2 类A380 场景

通过类A380 场景来验证大规模的拓扑优化，并得到一个新规模的优化拓扑。目前A380 AFDX网络交换机属性在文献［6］中描述，系统位置信息来源于文献［14］。网络拥有104 个端系统，9 个AFDX 交换机，网络支持100 Mb/s 通信带宽，模拟机载系统业务消息与控制耦合，例如，每个系统域到座舱的高带宽消息。主要的消息接收端有飞行管理（FM）、飞行告警（FW）、飞行控制与数据计算（FCDC）和座舱信息与数据系统（CIDS），可以确定有327 条速率为0.5 到4 Mb/s 的点到点连接。对于冗余系统线缆，存在45 条隔离约束。通过提出的方法和初始的拓扑可以得到一个正确的优化路由。假定交换机重2 kg，线缆重0.037 kg/m，安装机柜规模为25.1 kg（包含9 个交换机和113 条链接）。

3 优化算例

3.1 类A320 场景结果

手动设计优化拓扑如图4 所示，它拥有8 个交换机，4 个位于系统前后缘，在系统中间位置上下分别布局2 个。对称的设计在飞机两边形成两个并行路由，它们分别承载隔离的信号。总共有24 条链路，所有的交换机危险程度都是NOGO。

图4 手动设计拓扑结构

解2 采用PS 系统和OHDS 系统之间的通信路由，替换掉中间位置之间的线缆。减少了两条链接。此外，两个交换机危险程度降低为GOIF。规模和OIC 分别降低为20.1 kg 和746$/a。

解3 中规模达到最优解，如图5 所示。优化后的拓扑与手工设计相似，但是在中间每个位置只有一个交换机，增加了一个长链接。拓扑只有6 个交换机和10 个链接，减少了重量和OIC，所有交换机又都达到NOGO 危险程度。

图5 解3-规模优化拓扑

解4 给出OIC 最优集，如图6 所示。它同样拥有6 个交换机，但是在飞机中间位置引入长卷缆柱（cabling）。这使得只有4 个交换机变为NOGO，2 个变为GO。它的规模为26.2 kg，在这些拓扑中最大。

图6 解4-中断开销优化拓扑

通过预计算路径方法，针对拓扑规模和OIC 分别再次计算拓扑优化。通过选择路径长度最短来创建路径候选，得到最大网络中的最少路径。在本解中，得到的m=21，但这并不是拓扑规模全局最小解，它需要8 个交换机。最终得到的全局最优解m≥30。一个合理预计算路径数目，并没达到OIC 的全局最优解。

通过下页表1 对比可知，预计算路径在运行时间、变量数目和约束给定的情况下，能明显节省时间。计算拓扑优化的Pareto 最优解花费4 h，运行时间最长。每个全局最优拓扑平均花费1 h。使用预计算路径简化后，每个解为3 min，速度提升一个量级。

3.2 类A380 场景结果

类A380 网络优化拓扑，拥有7 个交换机和111条链接，重量约22 kg，比初始减少了12%。减少了座舱域中的两个交换机，中间交换机获得了一个多域的角色，并且移动了位置，因此，位于图的中心。每个交换机平均链接数目从15 条增加到19 条。这种方式打破了系统区域，但是网络负载没有变化。类A380 优化问题有139 071 个变量，相当于类A320 优化规模的15 倍（如表1 所示）。

表1 求解规模与运行时间

3.3 优化结果分析

类A320 场景的优化实验表明提出的方法可以针对不同维度找到优化解。相对手动设计，信号路由改进效果较明显。规模和OIC 都可以通过选择非传统路由方法改进，但通过手动设计方法无法预测。通过拓扑优化的Pareto 最优解能够发现非传统路由的全部潜在可行解。通过改进拓扑，规模可降低9%，OIC 可降低30%，达到规模最优。然而，由于OIC 目标本身的复杂性，手动优化几乎不可能实现。不经过优化（通过手动），即使能够得到一部分最优解，也不能确定该解是否为全局最优解。本文提出的方法可以通过部分的自动设计和设计调整，能够达到全局最优解。此外，通过折中解能显示解的最优特性和目标之间的关系，而手动设计则很难达到这种精度。BP 问题的大小和结果运行时间难以考虑。计算4 个小时获得Pareto 最优解也可以接受，但是本文所研究的只是一个小规模的算例，随着变量数量、交换机数目增长，计算复杂度呈指数值增长。类A380 拓扑优化表明：当目标受限，将消息分组到更少的信号上时，在整个飞机级采用该方法是适用的。同时，可以采用预计算路径方法限制运行时间。但是，预计更多的候选路径，并不能达到全局最优的OIC。如果后续选择候选路径时能够考虑OIC 的话，这一情况可能会得到进一步改进。使用预计算路径不能保证达到全局最优。因此，拓扑优化不能替代网络设计人员，而是一个有效的辅助分析手段。

4 结论

目前分布式综合化航电架构依赖高带宽航电网络，网络规模和开销对航电系统效能影响很大。本文提出一种基于业务拓扑、网络拓扑以及延迟、距离约束下的多目标网络拓扑优化算法，通过最大网络的迭代优化得到最优网络拓扑。优化的输入参数包括功能、信号和资源需求模型、拓扑安装位置、线缆路径的模型。优化模型的计算是一个BP 问题，最优解是面向网络规模和OIC 的线性开销函数的优化拓扑。另外，通过Pareto 采样，能够得出多目标约束下的最佳折中拓扑结构集。类A320 场景架构优化能够提升30%。类A380 架构优化能够提升12%，表明大规模网络优化的可行性。