基于负载均衡的1553B总线消息优化设计

基于负载均衡的 1553B总线消息优化设计

董士崔，王 刚

中国船舶集团有限公司第七一 ○ 研究所，湖 北 宜 昌 443003

摘 要： 针对1553B总线系统中周期性消息和非周期性消息混合传输时出现的总线消息拥塞和饱和现象，本文利用负载均衡原理对1553B上传输的非周期消息进行了优化。首先建立了1553B总线非周期消息传输的数学模型，然后利用改进的遗传算法对总线非周期消息的染色体进行编码，确定初始种群，建立了适应度函数，最后得到了1553B总线非周期消息调度的最优解。实验验证表明，在满足每个非周期消息的最大延迟时间要求和实时通信的前提下，上述方法可以有效地缓解1553B总线消息混合传输中的消息拥塞和饱和问题，提高总线利用率。

关键词：负载均衡；1553B总线；消息拥塞

中图分类号：TP336 文献标识码：A

Message Optimization Design of 1553B Bus Based on Load Balancing

Dong shi cui, Wang gang

Abstract：Aiming at the phenomenon of bus message congestion and saturation in 1553B bus system when periodic and aperiodic messages were transmitted together, this paper optimized the aperiodic messages transmitted on 1553B by using the load balancing principle. Firstly, the mathematical model of 1553B bus aperiodic message transmission was established, then the chromosome of bus aperiodic message was encoded by improved genetic algorithm, the initial population was determined, the fitness function was established, and finally the optimal solution of 1553B bus aperiodic message scheduling was obtained. Experimental results showed that under the premise of satisfying the maximum delay time requirement of each aperiodic message and real-time communication, the above method can effectively alleviate the problem of message congestion and saturation in the mixed transmission of 1553B bus messages and improved the bus utilization rate.

Key words: Load balancing；1553B bus；Message congestion

0 引 言

MIL-STD-1553B总线是一种分时、命令/响应、集中控制式多路半双工串行数据总线，因其更强的实时性、可靠性以及计算处理能力，现已被广泛的应用在舰船等领域上。1553B总线传输速率为l Mbit/s，如何考虑1553 B总线系统的可靠性和有效性，最大限度的发挥其系统性能成为目前学者研究的主要内容。当1553B总线需要处理不同长度、不同周期的各种消息，尤其是有非周期消息需要处理时，系统的实时性一般难以保证。

目前常见的1553b总线消息传输优化算法包括RMS调度算法、计算量向量算法、HTSF算法和长释放时间间隔优先算法。其中，RMS调度算法和计算量向量算法尚未解决消息的动态负载均衡问题，当处理总线上的非周期消息时，很容易阻塞或饱和总线。HTSF算法效率低下，没有考虑多个消息同时到达的情况；长释放间隔优先级算法不能保证非周期性消息或小间隔消息的释放能够在截止日期前完成调度。

为了解决1553B总线混合报文传输中的1553B总线拥塞和饱和现象，提高1553B总线的利用率，本文提出了一种根据负载均衡调度原理优化1553B总线报文传输的算法，减少了总线的平均延迟时间。

1 建立1553B总线非周期性消息传输的数学模型

对于1553B总线这样一个排队服务系统，可以选择排队论、PETRI网等建模分析工具。排队论是计算机通信网络和计算机系统中通信信息研究的基础理论，对信息系统通信问题的定量研究一般需要用排队论来解决。

由于1553B总线系统中非周期性消息（后文简称消息）的到达是一个一个到达的，对时间是齐次的，认为消息的到达强度是强度λ的泊松流，队列为无限长队列，并服从先到先得的服务，服务时间服从指数分布，平均值为1/μ。在1553B总线系统中，假定消息的平均到达率为λ，总线的平均服务速率为μ，消息数为m，消息的平均时间间隔为1/λ，消息的平均传输时间为1/μ。

假定排队系统在状态k处的概率为E_k，总线利用率为u，由M|M|1模型可得：

状态k： (1)

总线利用率为

(2)

若1553B总线消息的平均服务速率大于消息的平均到达率，则有

(3)

则1553B总线系统内消息的平均数为

(4)

若系统内共有k条消息，其余k-1条消息在排队等候，则消息传输需要的时间为

(5)

消息排队等候所需要的平均时间值为

(6)

1553B总线传输系统的平均延迟时间等于总线上消息传输的时间和消息排队等候的时间之和。目标函数L是系统中消息传输时间和消息排队等待时间之和的预期值，即

(7)

其中，c₁是μ = 1时总线消息传输所需要的时间，c₂是总线中每个消息排队所需的时间。将式（5）代入式（7），可得

(8)

式（8）为1553B总线系统中消息传输的数学模型。

2遗传算法得到1553B总线消息调度最优解

遗传算法是一种模拟生物遗传遗传的方法。在遗传算法中，首先通过编码形成初始群体，然后根据群体对环境的适应性对群体中的个体进行处理，最终实现适者生存的进化过程。遗传算法的操作可使问题遗传过程的解，一代又一代的优化，并接近最优的解决方案。

（1）对染色体进行编码

在遗传算法中，首先解决的是个体的编码问题。假设1553B总线上的消息数是m，消息小周期个数是n。

编码方法如下：首先对个体染色体上的每个基因位置进行编号，每个号码代表每条消息的编号；然后用0~(m-1)之间的整数表示每个基因位，该整数表示每条消息所在的小周期编号。若m=5，n=3，染色体编码为(1,1,1,2,2)：表示将第1条消息、第2条消息和第3条消息分配到小周期2上，第4条消息和第5条消息分配到小周期3上。

（2）初始化种群

为有效抑制“早熟”现象，本文采用如下方式初始化种群：

1. 定义个体相似度

随机产生个体长度为Len的N个个体，假设种群内第一个个体是x，第二个个体是y，根据标准海明距离函数得到x和y之间的相似度为：

(9)

初始化种群的个体相似度必须满足如下条件：

(10)

其中，c表示调节常数，用于控制相似度的值。

（3）适应度函数

遗传运算的目标是得到最优的1553B总线延迟时间，因此，将1553B总线传输系统的平均延迟时间函数作为适应度评价函数，

(11)

（4）交叉算子

交叉算子用于实现染色体的重组，为了避免遗传算法在重组的过程中过早丧失进化能力，本文中用父代的最优解与子代染色体池进行交叉操作，具体操作方法如下：

1. 首先在染色体池中分别选出最优染色体和进行交叉操作的子代染色体；

2. 将上述两个染色体的二进制编码基因串分别随机生成交叉片段和区域；

3. 将子代染色体的交叉区域加到最优染色体前面，将最优染色体的交叉区域加到子代染色体前面；

4. 最后将与交叉区域相同的基因删除，得到新的两个子代。

（5）变异算子

变异算子会增强寻找全局最优解的能力，变异运算中变异率通常取0.1，针对每个染色体编码基因串，随机将二进制编码基因串某个位置0变为1，或将1变为0。

6. 复制和选择算子

在对染色体个体进行评价时，将适应度较高的染色体直接复制到下一代染色体中。在得到新一代的染色体种群后，基于适应度函数评估得到的染色体种群，以确定是否符合终止条件，如果不符合终止条件，则重复上述遗传过程；如果符合终止条件，则退出循环，终止遗传优化操作。

获得1553B总线消息调度最优解的流程图如图1所示。

图1 获得1553B总线消息调度最优解的流程图

3 实验验证

为了验证在1553B总线上周期性消息和非周期性消息混合传输的情况下上述方法的有效性和实时性，设定在1553B总线上周期性传输综合导航、时统信息、方式指令等消息， 并随机插入控制命令、系统状态等不同长度的突发消息。在保持负载均衡的原则下，对1553B总线上各种消息的传输进行合理调度。将本文提出的算法与文献1中的算法相比较，在不同的总线利用率的情况下，消息的平均延迟时间的结果见图2所示。

图2 不同总线利用率下两种算法的比较

从图2中可以看出，当总线利用率低于50%时，文献1算法的消息平均延时时间明显优于本文算法；当总线利用率高于60%时，文献1算法的消息平均延时时间急剧增大，表明此时出现了总线拥塞的现象，而本文算法中消息的平均延时时间变化则较为平稳，避免了消息拥塞现象的产生，从这一点看，本文算法在处理总线拥塞上性能占优。但是本文算法也有不足之处，由于遗传算法只能得到局部最优解，而无法保证得到全局最优解，算法收敛速度较慢，可能会影响系统实时性。因此，可以考虑将本文算法与蚁群算法、模拟退火算法等相结合，取长补短，提高算法的收敛性，并能得到全局最优解。

4 结论

本文利用排队论对1553B总线上非周期性消息的传输进行建模，然后通过改进遗传算法，得到了1553B总线上非周期性消息调度的最优解。实验表明，该算法在周期消息和非周期消息混合传输的情况下，具有实时性好、可靠性高、异步事件处理能力强的特点。

参考文献

［1］蒲舰舸, 雷航．MIL-STD-1553B总线上的实时调度算法[J].成都信息工程学院学报，2005, 20(5)：550-554.

［2］刘桂山, 胡军程．1553B总线信息流设计[J].北京理工大学学报，2003, 23(3)：301-304.

［3］陆传来. 排队论[M].北京：北京邮电大学出版社, 2000. 20- 150.

［4］何立居，李启华．基于蚁群算法的航线自动生成研究[J]．中国航海，2009，32(3)：71—75．