基于遗传算法的运载火箭总线消息调度优化设计*

张卓政，王亚平

(1.上海航天控制技术研究所·上海·201109; 2.上海空间推进研究所·上海·201112)

0 引 言

MIL-STD -1553B是一种军用电子总线标准，最初被用于飞机内部时分指令、响应式多路数据传输，具有可确定性、传输可靠的特点。经过40多年的发展，由于具备良好的开放性和适应性, MIL-STD -1553B目前在国外已被广泛应用于航天、航空、航海等领域。国外卫星、主要运载火箭、国内新一代运载火箭等都普遍采用了该总线作为数据传输及共享的通道[1-2]。

作为运载火箭的核心系统,控制系统越来越多地采用了1553B总线作为系统的控制和测试总线[3]。控制和测试信息大多以周期性总线消息的方式在总线上时分复用多路传输，总线消息周期调度表的设计优化对于运载火箭飞行控制的实时性和可靠性而言至关重要。国内外研究人员从不同角度对1553B总线消息周期调度的实现和算法开展了一定研究。在对周期性消息的相位选择上,文献[4-5]每次总是优先考虑当前负载的最小周期，以降低总线平均延迟和均衡总线负载；文献[6]更进一步从消息集角度按周期从小到大、首先刻度较短周期的消息以实现相位均衡；文献[7-8]借鉴单处理器中周期任务的调度方法，来处理1553B总线上的周期消息，将总线消息进行分片传输以避免抢占问题。但是，上述文献对总线负载均衡和最大传输时间进行的综合考虑不多，并且没有考虑最优化设计。因此，本文针对以上问题，采用遗传算法对总线负载和传输时间开展了优化设计研究。

1 1553总线和总线消息

1553B总线的传输速率为1Mbit/s，总线系统由4部分组成，即总线控制器(BC)、远程终端(RT)、总线监视器(BM)、传输介质。BC是指在数据总线上被指定执行、启动或开启信息传输任务的唯一终端；BM是被指定执行接收总线上传输的信息和提取经选择的信息以备后用的终端,它不参与总线的事务处理；所有不作为总线控制器和监视器的终端即为RT,其作为各个分系统与总线的接口，在数量最多时可达31个。

1553B总线标准定义的消息传输格式有BC到RT、RT到BC、RT到RT、系统控制方式、广播方式等共10种，一条1553B消息由3部分组成:命令字、状态字和数据字。每类字的一个字长为20位,有效信息为16 位,每个字的前3位为单字的同步字头。命令字只能由BC发出，状态字只能由RT发出，一条消息的数据字最长不超过32个。以RT到BC消息为例：BC向RT发出1个发送命令字，该RT在核实命令字后，应发回1个状态字给BC，继之以规定数目的数据字。

典型的采用了1553B总线进行设计的运载火箭信息的综合设计方案如图1所示[1]。

图1 运载火箭总线控制系统的拓扑结构示意图Fig.1 Topology diagram of bus control system of launch vehicle

1553B总线命令/响应式的工作方式和箭载计算机信息集中、功能强大的特点，决定了作为总线上唯一的通信控制器，箭载计算机将统一组织总线消息在各单机之间进行传输，以实现控制系统的信息通讯。1553B协议对于物理层和数据链路层做出了严格的规范，而其对应用层的总线消息组织调度则依赖于用户的合理编排。在全箭信息一体化系统中，数据总线上传输的数据信息在传输速度上要受到与该数据有关的任务计算时间的限制，这决定了不同类型的数据传输需要不同的重复周期。例如，典型的姿态控制周期为20ms，遥测数据发送周期为1000ms。最慢的重复周期(最小的更新速率)常被称为大周期Tmax，表征了所有周期消息中允许延迟的最大值；最快的重复周期通常被称为小周期Tmin，表征了所有周期消息中允许延迟的最小值，一般有Tmax=Nmax·Tmin。对于箭上总线传输的任一个周期消息τi,一般有Ti=λi·Tmin，λi为周期特征量，λi∈{1，2，…，Nmax}。总线消息周期循环传输示意图如图2所示。

图2 总线消息周期循环传输示意图Fig.2 Schematic diagram of cyclic transmission of bus messages

在一个大周期内，有Nmax个小周期，所有的周期性消息传输至少在某个小周期内出现1次，较快重复周期的消息传输则可在多个小周期内出现。作为总线控制器，依据所处飞行段的不同，箭机将组织所有周期消息在Tmax内完成1次轮询，在时间刻度上形成1个被称为消息调度表的扫描表，并进行周期性地执行。对于运载火箭上的1553B总线应用而言，消息调度一般采用静态调度方法，即总线控制器(BC)按照预先离线设定的消息调度表逐一组织消息传输。采用静态调度方法的优势是可在飞行时免去执行消息的调度算法，其设计过程简单，消息传输的时延具有确定性。

2 总线消息周期调度表的数学建模

2.1 1553B总线周期消息传输的特性

通过研究1553B总线通信模式和运载火箭消息传输的要求，可以对1553B总线的周期消息传输提取出如下特点：

(1)各总线消息按串行方式传输。1553B总线属于共享式总线，由BC集中控制消息的调度和管理，RT被动响应。与CSMA/CD等必须竞争协议不同，1553B总线消息按调度表、分时获得总线使用权，传输时间取决于消息的长度；

(2)周期性总线消息传输是硬实时任务，基于时间触发，截止期就是消息的周期；

(3)消息传输为非抢占式调度，传输一旦开始便不可中断；

(4)各个周期性总线消息之间彼此独立，无相互依赖，且具有相同的优先级；

(5)由于是静态调度，各个总线消息周期不变，相互之间的传输顺序在一个大周期内可保持不变；

(6)不考虑消息传输过程中的丢包等异常问题。

2.2 1553B总线消息周期调度表的数学模型

对总线消息传输任务进行数学建模，所有周期性总线消息传输任务构成1个任务集，则有

τ={τ1，τ2，…，τn}

一般地，传输任务按周期从小到大排列。

对于第i个周期消息传输任务，可以用3个元素表征其任务性质：

τi={Ci，λi，Pi}

其中，Ci为消息传输时间，包含了命令字、状态字、数据字、消息响应、消息间隔时间；λi为周期消息的周期特征量，λi∈{1，2，…，Nmax}；Pi为相位，即周期消息首次在某个小周期中传输的序号。

2.3 数学模型的约束条件

对于已建立的数学描述，存在一定的约束条件：

(1)在每个小周期内，各个周期性消息传输时间的总和必须小于小周期本身的时间长度，即有：

(2)对任一个周期消息传输任务，其相位为不大于其周期特征量的正整数，即有：

Pi≤λi

(3)规定每个小周期内各个周期性消息的相对次序。

对于1553B总线而言，虽然总线消息没有优先级之分，不可抢占，但是由于消息传输由总线控制器按静态调度表进行控制，所以总是能够通过调度表的设计实现控制，即将周期小的消息优先传输，将周期大的消息滞后传输，这在一定程度上体现了消息传输的优先级；周期相同的消息，对于火箭控制的重要性等级相同，可以按照控制回路(从传感器到执行器)顺序或按照消息长度(从小到大)顺序进行传输。

2.4 消息调度优化设计的目标

对于第i个周期的消息传输任务τi={Ci，λi，Pi}，消息传输时间Ci和周期特征量λi都是由运载火箭控制系统的特点和控制模式决定的。对于特定的运载火箭，其值一般是固定的。消息调度优化设计的任务就是要寻找一种方案，合理分配各个周期性总线消息的相位构成整数向量P={P1,P2,…，Pn}，使得周期消息传输在一个大周期的各个小周期内尽可能均衡地分布。

各个小周期的负载率为：

其中，Mk为在第k个小周期内消息传输的个数。对于航天领域，要求典型的总线负载率小于60%，即σk≤60%。

将任务分解为优化指标：

(1)在一个大周期内，负载率最大值M=max(σk)尽可能小；

(2)在一个大周期内，负载率差距D=max(σk)-min(σk)尽可能小；

算法的目标则是寻找最优的解向量P={Ps}，以实现上述优化指标。

3 消息调度优化算法设计

3.1 可调度性分析

LIU和Layland[9]对可抢优的单处理器周期实时任务调度，提出了单调速率( rate monotonic, RM ) 算法和最小截止期优先( earliest dead-line first, EDF) 算法。这2种算法是后续各种调度算法的基础，并且证明了单调速率调度(RM)算法在静态调度算法中是最优的。网络化控制系统所应用的静态信息调度方式，具有不可抢优的特点，ZHANG[10]给出了非抢优RM调度算法可进行调度的充分非必要条件，由如下定理所述：

一组N个互相独立、非抢优的实时周期任务，任务优先级按照标值递减顺序排列(即下标i为1的信息优先级最高，下标i为N的信息优先级最低)。在RM调度算法下，其可调度条件为，对于所有的i=1,2,…,N，都满足下列不等式：

显然，定理可用于1553B总线控制系统周期消息可调度问题的判定。需要指出的是：由于是充分条件，不满足定理条件的不一定不可调度。不满足定理条件的消息传输任务仍然可以通过调整传输时间和周期来满足定理条件，可调度是可寻优的先决条件。

3.2 必要性

总线消息周期调度优化问题，实际是已知消息传输时间Ci和周期特征量λi，对各周期消息相位合理调度，寻找最优的解向量P={Ps}的组合优化问题。随着未来单机设备的增多和对总线消息传输需求的增加，周期消息传输任务必将更加繁重。对于各周期消息的传输调度，可以用穷举法将所有的可行解列出，但是利用此种方法在庞大的搜索空间中寻找最优解显然是不合适的。遗传算法[11]是一种借鉴了生物界优胜劣汰/适者生存法则的、可自然选择和自然遗传的、高度并行/随机/自适应的搜索方法。遗传算法寻优的机理是：从随机生成的初始种群开始平行进行，采用基于适应度的策略选择优良个体作为父代；通过父代个体的复制、交叉、变异操作，进化生成子代；当迭代优化过程结束时，适应度最优的个体所对应的变量值即为优化问题的最优解。

3.3 算法设计

(1)编码策略

周期消息传输任务τi在周期调度表中第1次出现的位置由相位Pi表征，Pi的值介于1与λi之间，其同时也决定了该周期消息在周期调度表中出现的全部位置。所有周期消息传输任务的相位构成的序列就是消息调度的1个可行解。故遗传算法中个体的基因采用整数向量编码方式，取值为Pj={Pj1,Pj2,…，Pjn}。对于每一个个体，若其满足σk≤60%，则可将其称为有效染色体。1组有效个体则构成了有效的种群。

(2)适应度函数

根据优化指标来构造适应度函数，可用于评价个体的优劣，通常可将最小问题转化为最大问题，且适应度函数一般要求非负。对应优化的3个指标，按一定的权重对其进行分配。于是，适应度函数有：

F(Pi)=U-rm×M-rd×D-rv×ρ

其中U为足够大的常数，以保证适应度函数非负，rm、rd、rv为权重，且有rm+rd+rv=1。

(3)遗传操作

选择操作：首先对种群计算适应度，采用“精英保留”策略对当前种群中适应度最好的2个个体不采取任何操作，而直接将其保留至下一代。经典遗传算法的选择操作依概率而随机进行，而由交叉、变异操作导致的劣质个体无法避免，不能防止适应度函数值较高的个体丢失，存在导致群体评价降低的可能。“精英保留”策略具有更好的健壮性，提高了最优解产生的效率。对于“精英”以外的个体均要按概率进行交叉或变异，同时每个个体具有1个选择概率。针对总线消息调度优化问题，经实际测试发现，种群中个体的适应度函数值相差不大，直接采用适应度函数值进行选择的方法选择压力太小。因此，应采用基于线性排序的选择方法。

设定VNUM为种群大小，Pos为个体在种群中的序位，SP为选择压力，线性排序个体的选择度按下式计算：

得到选择度后，采用轮盘赌选择方法选择个体。

交叉操作：所谓交叉是指把2个父代个体的部分结构进行替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。交叉概率pc越大，生成新个体的速率越快，进而可能引起遗传模式的破坏，适应度较高的个体结构会很快丢失；反之，pc越小，算法搜索效率越低，甚至会出现进化停滞。

由于个体基因采用了整数向量编码，所以交叉操作对2个父代均匀离散重组，对父个体等概率随机交换变量值、形成新的个体。

变异操作：变异的基本内容是个体某些基因座上的基因值变动。对于个体Pj={Pj1,Pj2,…，Pjn}，第i个基因座Pji的可选变异值介于1和λi之间。同交叉概率类似，变异概率py越大，个体更新越快；然而，与单纯的随机搜索算法近似，py越小，则算法搜索越缓慢。

对交叉概率和变异概率的选择，需要根据具体优化的问题试验选择、确定合适的值。无论是由交叉或是变异操作生成的新个体，都必须满足有效个体的限制，这是可行解的最基本的要求。

(4)种群迭代

经过遗传操作的个体集合成下一代新的种群，开始新一轮的迭代。当个体的适应度函数满足收敛条件或是迭代次数达到上限时，计算将终止。优化算法的流程如图3所示。

图3 总线消息优化算法的流程图Fig.3 Flow chart of bus message optimization algorithm

4 消息调度优化算例与验证

针对某总线控制运载火箭一级飞行段的典型消息传输任务采用“精英保留”遗传算法进行操作，共有20条周期性消息传输任务。如表1所示。

表1 消息传输任务表Tab.1 Message Transmission TaskTable

经验证，满足可调度定理的条件。

算法参数如下：

种群个体数：30；

迭代次数：90；

优化权重：rm=0.28，rd=0.41，rv=0.31；

交叉概率：0.62；

变异概率：0.48。

仿真计算结果如图4、图5所示。由图4可知，经过10代种群遗传操作后，种群的适应度最大值趋于最优结果。图5给出了优化结束后前20个Tmin中消息的调度结果，可见每个Tmin中的消

息负载趋于均衡，算法合理有效。

图4 优化迭代过程中每一代适应度最大值的变化趋势Fig.4 Trend of maximum fitness of each generation in optimization iteration

图5 前20个Tmin中的消息调度表Fig.5 Message schedule in Top 20 Tmin

5 结 论

本文在对运载火箭控制系统的1553B总线消息传输的特点进行深入分析的基础上，对总线周期性消息周期调度表进行了数学建模，提出了基于遗传算法的、总线消息周期调度表的优化设计方法，并结合某运载火箭一级飞行段控制系统的总线消息传输任务进行了数学仿真，验证了该优化设计能够有效提升总线负载的均衡度，提高了总线传输的可靠性。