潘云嵩，周崇亮，万晓冬

(南京航空航天大学 自动化学院，江苏 南京 211106)

0 引言

航空电子系统是飞行器所有电子系统的总和。其系统大致经历了分立式、联合式、综合模块化(IMA)3个阶段[1]。目前，航空电子正从IMA走向分布式综合模块化航空电子系统(DIMA)的发展阶段。

DIMA继承了已应用在B787、A380上的IMA的模块化概念，制定具有标准统一接口的核心处理器模块，分别为数据处理模块(DPM)、信号处理模块(SPM)、图像处理模块(GPM)、网络支持模块(NPM)、存储器模块(MMM)、电源模块(PCM)。同时克服了IMA存在的集中式大机柜带来的可靠性较差、线缆过长、不宜冷却、故障容易扩散等缺点[2]。核心处理模块根据需求分布在飞机的各个位置，各个模块之间通过实时高容错通信网络互连。

通过实时高容错通信网络连接起来的通用核心处理模块、传感器和作动器构成DIMA的硬件物理层[3]。硬件物理层为系统运行提供计算资源、存储资源、IO资源、能源等。通用核心处理模块如何分布在飞机上，称之为硬件模块映射问题。在DIMA系统中，飞行任务被细分成原子化的子任务模块，每个子任务只能由一个特定的处理器模块处理。为在完成一个飞行任务需要多个多种类型的处理器模块协同合作，即功能应用软件在多个多种处理器模块加注和运算，并根据需要驱动传感器或是作动器完成子任务。飞行任务的子任务模块如何加载到分布在物理层上的通用处理模块，称之为软件模块映射问题。

Hamburg Univetsity of Technology的BjörnAnnighöfer从成本的角度出发，提出了基于遗传算法求解Pareto多目标优化的方案[4-5]。清华大学Chao Zhang从成本和可靠性的角度出发，对多个优化目标赋予不同的权值转换成基于遗传算法的单一目标优化问题[6]。上述文献均未对处理器模块做细分，把六大类处理器模块当作同一实体讨论，且把子任务模块和硬件模块作为一个整体同时进行优化。在航空电子系统运行期间，子任务模块是动态加注到已经分布在飞机物理层上的通用处理器模块上，因此把硬件模块映射和软件模块映射分成独立的两个阶段更适合。本文在采用多种群遗传算法[7]求解六大类通用处理模块映射问题的基础上，采用贪心算法求解软件映射优化问题。

1 DIMA资源映射问题描述

1.1 硬件模块映射

DIMA采用模块化的设计理念。航电功能系统模块化设计，分出DPM、SPM、GPM、NPM、MMM、PCM六大模块，每个模块完成特定的功能。这六大类型模块要分别安装到分布在飞机不同位置的机架上，如图1所示。

1.2 硬件映射数学模型

机架定义为L1,N1,L2,N2,…,Lm,Nm,其中Lm,Nm表示第m个机架具有Nm个安装槽位供处理器模块安装。处理器模块统一标记为D1,D2,…,DND, 其中ND等于处理器模块总数量。处理器模块安装在机架上，则可以表示为x向量：

X=[X1,Xi,…,XND]

(1)

其中，Xi表示为第i个模块的安装向量。

Xi=[xi,L1,…,xi,Lm]

(2)

其中，xi,Lm=1则表示第i个模块安装在第Lm机架上。xi,Lm=0，则表示不安装。

约束条件1：每个模块只能安装在一个机架的一个安装槽位上，一个机架可以安装多个模块，即：

AXT≤B

(3)

其中，B为长度为m的一维向量B=[1,1,…,1],A=diag(I,I,…,I),I=[1,1,…,1],长度为ND。

约束条件2：一个机架可以安装多个模块，但不能超过机架的总安装槽位，即：

(4)

其中，1≤j≤m,，Nj表示第j个机架的槽位数量。

硬件映射方案的散热用向量H表示:

H=[H1,Hi,…,HND]

(5)

其中，Hi表示为第i个模块的安装向量。

Hi=[Hi,L1,…,Hi,Lm]

(6)

其中，Hi,Lm≠0则表示第i模块安装在第lm机架上且散热量为Hi,Lm≠0，Hi,Lm=0，则表示此槽位没有模块。

约束条件3：机架上安装的处理器模块总散热量不能超过机架的最大冷却能力，即：

AHT≤C

(7)

其中，C为长度为m的一维向量C=[C1,…Cm]，Cm为机架的最大冷却能力，A=diag(I,I,…,I),I=[1,1,…,1],长度为ND。

在航电系统运行期间，处理器模块会与外围设备(传感器或是作动器)产生交互，机架到外围设备的距离用矩阵L表示：

(8)

其中，lqp表示q机架到第p个外围设备的距离，lqp=lpq，则所有安装在机架里的处理器到外围设备的距离用Dis表示，即：

(9)

(10)

1.3 软件模块映射问题

DIMA分成3个层次结构，分别为功能层、任务层、处理器模块层。系统功能被分成多个子任务。这些子任务是原子化，即一个子任务只能分配给一个处理器模块处理。但一个处理器模块可以处理多个来自不同系统功能的子任务。软件模块映射问题就是系统所有的子任务如何加注到模块上，如图2所示。

图2 软件映射示意图

系统任务用F表示，原子任务用T表示，式(11)表示第i个系统功能可分成m个子任务。式(12)表示整个DIMA共有N个系统功能。

FI=(Ti,1,Ti,2,…,Ti,m)

(11)

F=(F1,F2,…,FN)

(12)

处理器模块用M表示，MT表示该模块能处理T类型的任务。

软件映射问题就是给出功能Fi，依据怎样的规则在DIMA模块层中找出能完成该功能所需的处理器模块集合Mset={MT1,…,MTm}。

2 问题优化求解

2.1 硬件映射的优化

上文已对硬件映射做了数学描述，建立如式(13)所示的数学模型，即求Dis最小值：

(13)

St.AXT≤B

AHT≤C

该模型是带3个约束条件的单一目标优化问题。优化的目标为处理器模块到外围设备的距离Dis最短。Dis在DIMA系统中是个很关键的指标，直接关系到通信效率、线缆费用等方面。本文采用带有修复因子的多种群遗传算法求解该硬件映射的最优解。

染色体采用自然数编码形式[8]。总共有m个模块需要安装，记为(1，2，3，…，m)。所有的机架共有n个安装槽位，编号为(1，2，3，…，n)。染色体编码形式如图3所示，其中标记为“0”表示此槽位不安装任何模块。采用自然数编码形式能保证满足式(3)和式(4)的约束条件。

图3 染色体编码形式

随机产生染色体交叉位置k，然后交换1～k的染色体体位，并记下两条1～k染色体体位的对应关系。依照1～k对应关系，交换k～n两条染色体体位。

随机产生2个染色体的突变位置，然后交换这2个位置的编码，完成染色体的突变。

修复策略：对生成的每一代染色体，计算其对应机架上所有模块产生的散热量，如果超过了机架的冷却能力，随机把该机架上的模块放入具有剩余冷却能力最大的机架内，直至满足式(7)对机架冷却能力的约束条件。

多种群遗传算法在常规的标准遗传算法(SGA)的基础上引入多个种群。每个种群配置不同的交叉概率pc和突变概率pm，这样能扩大算法的搜索范围。每个种群通过移民算法，把最优的个体引入其他种群，实现多个种群的协同进化。其算法框架如图4所示。

图4 多种群算法流程图

对硬件映射问题的求解，需要的数据有机架的数量、每个机架的槽位、每个机架与外围设备的距离和处理器模块的散热量，限于篇幅就不列出了。如图5和图6所示，采用多种群算法求解硬件映射问题约进化到80代时收敛。

图5 每一代种群进化结果

图6 每一代精英个体适应度

对精英个体的染色体通过解码就得到该问题的最优解，如表1所示。表1中表示150个硬件处理模块在3个机架上的映射，自然数是硬件处理模块的编号，0值表示该机架该位置不安装任何处理器模块。限于篇幅，未能列出全部数据。

表1 硬件模块映射结果

2.2 软件模块映射优化

求解软件映射问题时确定如下3个优化目标：

1) 要能保证完成系统功能。

2) 子任务加注到处理器模块尽可能靠近外围设备。处理器靠近外围设备就地处理，避免了数据在通信网络上的远程传输。

3) 协同合作完成系统功能的多个多种类型的处理器模块在空间上尽可能接近。处理器模块聚集度高，将直接缩短处理器模块之间数据的传输距离，这就能提高DIMA通信效率和可靠性。

其中x，y为模块在飞机平面上的空间位置坐标。

本文采用基于优先级的贪心算法[9]解决软件映射问题。首先依据任务紧迫性、运算数据大小等因素事先排出子任务的优先级，然后采用贪心的策略遍历所有可行解依次找到满足上述3个优化目标的解。其算法过程如下：

a) 遍历所有的核心处理模块，没有剩余运算能力的核心处理模块排除在搜索范围之外。

b) 依据子任务的优先级，从高到低逐个选择处理器模块，依据以下2个优先级准则：

1) 若子任务需要用到某种外围设备，则采用遍历方式寻找离该外围最近的模块。

3) 模块m加入集群，更新集群中心。

c) 如果还有子任务没有分配，则继续步骤a)和步骤b)，否则结束遍历。

在硬件映射完成的基础上，采用贪心策略依次满足软件模块映射的3个优化目标，最终必定能找到一个近似最优的软件模块映射问题解，即求得子任务加载到通用处理器模块的方案。限于篇幅，未能列出优化软件模块映射问题的输入数据，软件模块映射优化结果，见表2所示。表2表示4个具有不同优先级的子任务软件模块被加注到4个硬件模块之上。

表2 软件模块映射结果

3 结语

分布式综合化模块化航空电子系统(DIMA)是在联合式航空电子系统和综合化模块化航空电子系统的基础上发展起来面向未来的下一代航空电子系统。从国内外公开发表的文献来看，DIMA的资料还不是很多，知识点非常零散。本文采用多种群遗传算法解决DIMA硬件映射问题，实验结果显示是有效果的。对软件映射问题，本文提出了基于优先级贪心算法。其实质是用贪心算法找到合适的映射方案，以期满足尽可能缩短数据在处理器模块之间、处理器模块与传感器作动器之间的传输距离3个优化目标。

[1] 徐科华, 陈谋, 徐扬,等. 民用飞机机载电子系统分布式体系架构研究[J]. 工程设计学报, 2012, 19(6):494-498.

[2] 朱闻渊, 尹家伟, 蒋祺明. 新型航空电子系统总线互连技术发展综述[J]. 计算机工程, 2011(s1):398-402.

[3] Wolfig R, Jakovljevic M. Distributed IMA and DO-297: Architectural, communication and certification attributes [C] //Digital Avionics Systems Conference, IEEE/AIAA 27th. IEEE, 2008(1): 4-10.

[4] Annighofer B, Thielecke F. Multi-objective mapping optimization for distributed Integrated Modular Avionics[J]. Digital Avionics Systems Conference, 2012,6B2:1-13.

[5] B. Annighöfer, Thielecke F. A systems architecting framework for optimal distributed integrated modular avionics architectures[J]. CEAS Aeronautical Journal, 2015, 6(3):1-12.

[6] Zhang C, Xiao J. Modeling and optimization in Distributed Integrated Modular Avionics[J]. Digital Avionics Systems Conference, 2013:1-20.

[7] 刘鹏程, 李新利. 基于多种群遗传算法的含分布式电源的配电网故障区段定位算法[J]. 电力系统保护与控制, 2016, 44(2):36-41.

[8] 邹琳, 夏巨谌, 胡国安. 基于实数编码的多种群并行遗传算法研究[J]. 小型微型计算机系统, 2004, 25(6):982-986.

[9] 代文强, 李晓荣, 冯毅. 最大和搜索结果多样性问题及其贪婪算法分析[J]. 系统工程理论与实践, 2016(3):706-711.