光纤网络实时性可调度算法与多信道分配研究

汤 海

（西安工业大学电子信息工程学院 西安 710021）

1 引言

机载通信需求的快速增长促使机载通信向网络化的方向不断发展，作为连接卫星网络和地面网络的空中通信重要枢纽，光纤网络具有诸多区别于无线移动网络的新特征，包括大尺度三维稀疏分布场景、长传输范围、移动轨迹可预测等。此外，光纤网络传输带宽需求急剧增加，需要支持例如普通消息、音频、视频和多服务通信等多种通信方式。因此，光纤网络的实时性可调度算法和多信道分配架构分析成为研究的热点。国内外文献在实时调度研究方面做了大量研究，文献［1～3］均提出对实时调度领域经典算法-速率单调调度算法/最早截止期限优先调度算法的改进算法，并进行了延迟性能比较。文献［4］证明了单信道轮转调度可应用在强实时环境下，然而带宽碎片的大量存在导致较低的信道利用率。本文给出了机载应用环境下的消息调度模型和实时调度的轮转约束条件，提出一种保证机载网络强实时性的加权轮转调度算法，根据确定性网络演算理论给出实时性能分析和系统能耗模型。

2 机载网络体系结构

机载航空网络的数据流可看作是由紧急消息、周期消息、事件消息和大数据块消息组合而成混合消息数据集。不同类型消息的数据流对实时性要求也不相同。紧急消息用于模拟对实时性要求非常高的关键性数据业务，如飞行控制、武器发射指令等；周期消息用于模拟一般关键性的实时周期性的数据业务，如雷达、传感器的数据采集等；事件消息用于模拟对实时性要求不高的消息，如设备运行状况等；大数据块消息用于模拟对实时性要求最低的、大量的数据传输，如视频数据等。消息调度模型在航空电子系统中，雷达、电子战以及通信等不同种类的机载设备进行周期性数据的采集等。由机载设备采集的信号经航空电子应用程序产生相应的消息［5］。如图1所示，强实时信道组(λ1，λ2，…，λm)采用轮转调度的方式服务于周期性任务模型中的各消息。

图1 消息调度模型

3 消息可调度性模型

在航空机载网络中，消息按其类型可分为周期消息和非周期消息。消息的格式和长度是固定的，且大部分为周期消息，非周期消息也可以确定其发送的最小时间间隔。假设机载网络系统中有n条实时消息流形成一个消息集S=(S1，S2，…，Sn)；采用实时通信中的周期性任务模型，则每条消息流可由一个四维数组表示si=(Ci，Pi，Di，ϕi) ；其中，Ci表示消息流最大长度；Pi表示消息流的发送周期［6］，对于非周期消息，则表示消息产生最小时间间隔；Di表示消息流的最大允许延迟时间，一般取Di=Pi，ϕi表示消息流进入系统时刻，消息流产生周期Pi的最小值用Pmin表示。消息流负载率定义为

设TRL为信道轮转周期，M为强实时信道数目，则轮询权值约束条件可由下式表示：

其中，TRL取小于Pmin，且为正整数。

对于任意时间间隔t，Xi(t)表示消息i发送的最小时间量，则时限约束条件为

为保证消息发送的实时性，单信道WRR算法中消息i分配的权值通常取，我们分别取（ 方 法 1） 和（方法 2），当时，对于任意的i，有

同时，当信道资源数目M和轮转周期TRL的选取满足轮询约束条件时可满足消息的实时发送。然而，由于轮转长度TRL、消息周期Pi和消息长度Ci往往不成比例，这种权值分配方法分配较大权值，造成信道利用率的下降。当wti=[(Ci*TRL) Pi]时，对于任意的i，有：

式（5）不满足时限约束条件。也即消息i在周期Pi的消息发送时间会小于Ci，需要在补偿信道对其进行权值补偿。将权值分配不足部分集中到补偿信道的做法，大大提高了信道利用率，但同时增加了系统的复杂度。

当F(TRL)取最小时，其对应的TRL为此权值分配方法下的轮转周期最优值。此时，消息分配的权值有效利用率最高。

与传统的电信网络和数据网络不同，机载网络要求强实时性以保证消息传输［9～10］。实时性是机载网络的关键性能要求，因而保证机载网络的实时性十分必要。实时调度方法是保证机载网络消息传输性能的关键。然而，通常的网络调度算法往往侧重于调度的公平性、系统负载率和消息的平均延迟等特性，对实时性能的关注较少。基于轮询的加权轮转调度算法以较低的复杂度和高度执行性非常适合具有强实时要求的机载网络系统。在机载网络的设计中，通常需要在满足一定的实时性和可靠性的指标下，尽可能的提高传输有效性。多信道实时加权轮转调度算法步骤如下：

1）确定信道轮转周期TRL；

2）保证实时情况下，根据权值分配方法分别计算每条消息在每轮调度中需要分配的权值wti；

3）计算系统所需信道资源；

4）根据多信道分配策略将权值分配到不同的信道资源上；

5）依据以上参数进行消息发送。

信道轮转周期的选择、权值分配方法和多信道分配策略是多信道实时加权轮转调度算法设计中的重要过程。轮转调度周期的选择是影响系统实时传输性能的关键之一。权值分配方法决定了消息分配权值的大小，并直接影响系统所需分配信道资源数目。消息拆分将不利于系统对消息的管理，在尽量减小拆分次数的前提下，多信道分配策略应实现各信道负载率的均衡。

4 多信道分配方法

在多信道权值分配过程中，当单一信道的剩余权值不足以提供消息预分配的权值时，需要对消息进行拆分，加之消息的排序重组技术，使得调度算法更加复杂。因而，为了简化调度算法，需要尽可能减少消息拆分次数。论文提出一种多信道分配方法，该方法在遵循尽可能少地减少拆分次数的原则前提下，尽量平均每个信道的负载率。

其分配方法如下：系统中所有的消息组成一个消息集合；根据消息所对应的权值，将消息集合划分为尽可能多的权值和恰好等于轮询周期的互斥集；在同一互斥集内的消息分配到同一波长信道上；将剩余消息所分配权值和信道空闲带宽按照从大到小排序；依次选择剩余消息集合中权值最大的消息分配到空闲带宽最大的信道资源上去。若单个信道剩余带宽不足，则再进行消息流的拆分。每分配完一条消息，更新信道空闲带宽顺序。根据多信道分配方法，可以达到每个信道的负载率平均的目的。

5 计算与分析

在式（4）中，所有值的单位都是slot，初始相位是随机的。根据轮转调度算法函数和实时调度约束条件，计算得出了不同权值分配条件下旋转函数和TRL之间的关系，如图2所示。

图2

当使用第一种权重分配方法时，TRL=6时，轮转函数的最小值为F(TRL)min=0.7479，所需的硬实时信道资源数是4。使用第二重分配方法时，TRL=12，轮转函数的最小值为F(TRL)min=0.2521，所需的硬实时信道资源数是3。

消息延迟时间率可用作衡量消息实时性，表示消息传输对系统的容忍度。计算了机载触发网络每条消息对应的延迟时间率，结果如图3所示。

图3 不同权值分配下的平均消息延迟率

消息对应的最大延迟率越小，其容忍度越高，抖动等其他影响因素越不易影响机载触发网络实时性。由图3可知，虽然所有消息其最大延迟率均不超过1，满足系统的实时性需求。然而，权值分配2下的消息最大延迟时间率均为1（此时的容忍度为最低），大于权值分配1下的消息最大延迟时间率。

计算分析了不同权值分配下的信道利用率，如图4所示。

图4 不同权值分配下的信道利用率

由图4可知，第二种权值分配方法下的信道利用率优于权值分配方法1，其平均信道利用率分别为0.8333。而采用权值分配方法2，其补偿信道的信道利用率为0.5857。在考虑补偿信道情况下，由于两种分配方法下的实时调度算法的轮转周期和信道资源数目均相同。因此，两者的平均信道利用率在理论上是相同的。由以上分析得出，在仅考虑强实时信道的情况下，权值分配方法2对应的信道利用率明显高于权值分配1的。但是，若将补偿信道考虑在内，两者对应的信道资源及其占用情况一致，并且分配方法1的最大消息延迟率小于分配方法2的。

5 结语

针对机载网络的强实时性要求，以消息的可调度性理论模型为基础，提出了保证机载光纤网络强实时性要求的加权轮转调度算法，解决了机载光纤多信道网络中消息的实时发送问题，并对影响调度算法参数设计的三个重要过程做了详细分析讨论。结果显示，根据信道利用率最高时确定的轮转周期不能保证最优的最大消息延迟时间率；在平均信道利用率相同情况下，权值分配方法1下的最大消息延迟率优于权值分配方法2的；针对多信道的应用环境，提出的多信道分配方法有效减少了消息拆分次数。本文的研究结果对机载光纤网络的工程设计与优化有一定的指导意义。?