基于优先级队列的多约束无线链路资源调度算法

罗 宁，刘 峰

(1.南海舰队指挥所，广东 湛江 524000;2.江苏自动化研究所，江苏 连云港 222006)

数据链是各指挥所与武器平台间交联的纽带，它将不同的武器平台有机地连接起来，形成一个高效的作战体系［1］。目前美军已形成多频段覆盖、多功能兼备、多平台并用以及从单机到系统的较成熟的数据链网络。随着军队联合作战水平的提高，在海战场协同防空、近岸协同防御等应用环境中，需要利用数据链完成传感器、指控系统与武器系统之间的目标参数、指控数据等实时信息的交换［2-3］，数据链组网的通信量将越来越高。目前数据链传输速率有限，如美军Link-11标准传输速率为 1200bps，Link-16标准传输速率为28.8kbps～238kbps;如Link-11等轮询数据链在多节点组网时，还存在较长的轮询周期，导致无线链路吞吐量降低，进而影响作战的整体效能。因此在一体化协同作战的背景下，为保持较好的通信时延等无线传输QoS要求，既需要开发更先进、高速的数据链;又需要合理规划数据链组网，改善无线链路资源调度方式，提高现有数据链资源的使用效率。

在当前指控系统中，不同的报文具有不同的无线传输QoS要求，如果指控系统未考虑报文的优先级、节点移动性和无线传输易受干扰等特点，采用先入先出的方式向数据链端机发送数据，会导致低优先级数据占用过多无线链路带宽资源，从而使高优先级报文延迟过大，吞吐量过小，不能有效利用无线链路资源，达到整体指控报文传输效率的优化。

本文将先介绍当前常见的队列调度算法，在此基础上提出基于优先级队列的多约束无线链路资源调度算法，该算法综合利用报文优先级、节点位置信息、链路丢失率形成发送时的多约束条件，通过队列间调度和队列内调度，提高现有数据链资源的使用效率。

1 常见队列算法

常见队列调度算法多数是针对路由器设计，如优先级队列PQ(Priority Queuing)、加权公平队列 WFQ(Weighted Fair Queuing)等，本文算法吸收了优先级队列PQ和加权公平队列WFQ算法的特点，在仿真中将对比分析先入先出队列FIFO和优先队列算法，因此重点介绍这三种算法。

1)先进先出队列 FIFO［4］(First In First Out Queuing)

FIFO依照报文到达时间的先后顺序进行转发。所有报文共享网络带宽资源，得到资源的多少完全取决于报文到达的时机，没有考虑无线环境中的丢失率和节点移动性。

2)优先级队列 PQ［4］(Priority Queuing)

PQ队列是针对关键业务应用设计的。关键业务有一个重要的特点，即在拥塞发生时要求优先获得服务以减小响应的延迟。PQ可以根据网络协议(如IP，IPX)、数据流入接口、报文长短、源地址/目的地址等灵活地指定优先次序。在队列调度时，PQ严格按照优先级从高到低的次序，优先发送较高优先级队列中的分组，当较高优先级队列为空时，再发送较低优先级队列中的分组。这样，将关键业务的分组放入较高优先级的队列，将非关键业务的分组放入较低优先级的队列，可以保证关键业务的分组被优先传送，非关键业务的分组在处理关键业务数据的空闲间隙被传送。PQ的缺点是如果较高优先级队列中长时间有分组存在，那么低优先级队列中的报文将可能一直得不到服务。

3)加权公平队列 WFQ［5］(Weighted Fair Queuing)

首先，WFQ是为了公平地分享网络资源，尽可能使所有流的迟延和延迟抖动达到最优而推出的。它照顾了各方面的利益，主要表现在:不同的队列获得公平的调度机会，从总体上均衡各个流的延迟。短报文和长报文获得公平的调度:如果不同队列间同时存在多个长报文和短报文等待发送，应当顾及短报文的利益，让短报文优先获得调度，从而在总体上减少各个流的报文间的延迟抖动。

其次，WFQ在计算报文调度次序时增加了优先权的考虑。从统计上，WFQ使高优先权的报文获得优先调度的机会多于低优先权的报文。在出队的时候，WFQ按流的优先级来分配每个流应占有出口的带宽。优先级的数值越小，所得的带宽越少。优先级的数值越大，所得的带宽越多。最后，轮询各个队列，按照带宽比例从队列中取出相应数量的报文进行发送。

本文结合上述几种算法的特点，在考虑无线通信环境中存在较高丢失率和节点移动性等特点的基础上，提出下文所述算法。

2 基于优先级队列的多约束无线链路资源调度算法

基于优先级队列的多约束无线链路资源调度算法根据报文优先级设计，通过比较节点当前通信距离与最大通信距离的关系引入对节点移动性的考虑，通过链路报文丢失率引入对无线传输易受干扰特点的考虑;通过设置最大连续发送次数，避免低优先级队列总是得不到服务。本文算法对不满足要求的报文延迟发送，但由于数据链中无线链路的节点位置、链路延迟等链路状态信息的收集存在滞后性，因此本文算法将设置最大延迟发送次数，达到最大延迟发送次数后对报文做试探性发送，防止链路状态信息更新延迟对传输性能的影响。

在对报文做分类归纳的基础上，将报文分为三个优先级:1，2，3。其中优先级1的报文为紧急报文，该类报文在发送时将会被最优先发送;优先级为2的报文为重要报文，该类报文具有强实时性要求;优先级为3的报文为普通报文，对实时性不是特别敏感。

算法具体流程如下所述。

1)将报文按优先级送往三个队列

2)队间调度

优先级为1的队列为紧急队列，如果该队列中有报文，则优先发送。对于优先级为2的实时队列，每次发一个报文后，询问紧急队列是否有报文发送，有则发送紧急队列中报文。为了防止优先级为3的一般队列始终得不到服务，为优先级为2的实时队列设定N实时，实时队列连续发送报文数目n实时达到N实时时，发送优先级为3的队列中的报文，每次发送优先级为3的队列中的报文时n实时都置0;优先级为3的队列得到发送权限后发送一个报文，然后交出发送权。流程图如图1所示。

3)队内调度

流程图如图2所示。首先，通过态势等报文获取数据链报文接收方实时位置信息，设当前数据链最大通信距离为Smax，计算接收方与当前数据链距离S，如果S＞Smax则放弃发送;如果处于丢失通信状态，则延迟发送(设延迟发送次数为m，m加1)。放弃或延迟的报文下一次时会继续判断，但放弃报文维持一个最大超时计时器，超时后删除;

其次，根据使用经验，按照丢失率情形将通信环境划分为:良好、一般、较差、很差四个区间。设Loss为统计计算得到的丢失率，Index为丢失率区间索引，各通信环境丢失率门限为:良好 Loss∈［0，Lth1］，Index为1。;一般 Loss∈［Lth1，Lth2］，Index为 2;较差 Loss∈［Lth2，Lth3］，Index 为 3;很差 Loss∈ ［Lth3，Lth4］，Index为4。

图1 队间调度流程图

图2 队内调度流程图

对于每一个从站维持一个最大延迟发送次数Dmax，Dmax确定规则:Dmax=2*Index，Index为丢失率区间索引，通过在不同丢失率时产生阶梯式的延迟发送次数，用于控制不同通信质量下的链路的发送速率。

然后，计算该从站到接收方链路的丢失率Loss。在Loss≻Lth2时，该报文不发送，m加1，m达到Dmax时报文发送，同时m置0。接着判断该报文之后的报文。

间隔T内(大于报文更新频率)更新一次丢失率Loss和Dmax，如果T内没有收到新报文，则Loss置无效，只用位置信息进行队列内报文调整。

3 仿真验证［6-8］

3.1 仿真场景

本文算法利用报文优先级、节点位置信息、链路丢失率形成发送时的多约束判断条件，本文算法只和目的节点的位置以及该链路上的通信质量有关，与数据链的多少无关，因此为验证本文算法性能，设定仿真场景如图3所示。mobile-node1、mobile-node2、mobilenode3等3个可移动节点和数据链中心节点dlink-center构成轮询式数据链网络，dlink-center与指控节点zk0连接，src1、src2、src3为数据源节点，通过有线网络与指控节点zk0相连。通过该场景仿真轮询数据链典型使用方式。

本文模拟实际作战中具有不同优先级的报文，src1、src2、src3 分别产生优先级为 1、2、3 的数据包，记为P1、P2、P3，通过设定发送速率大于该网络无排队报文时的数据速率，可以模拟数据包在指控节点zk0上的排队情况;为模拟无线环境中的通信干扰，设置jam节点为噪声节点，距离jam节点越近干扰越强，用于仿真在噪声情况下的通信丢包;设定数据链通信范围为200km，速率为 1200bps。

3.2 仿真数据分析

本文将通过对比分析本文算法、优先级队列算法PQ和FIFO算法，验证本文算法的性能。首先研究基于优先级队列的算法在数据链传输中对于重要报文延迟、吞吐率等性能的改善程度，通过在无干扰节点都在通信范围内的理想通信环境中验证;但在实际的通信环境中，会有节点不在通信范围，并且会存在通信干扰，本节将对这两种情况分别仿真研究，通过仿真证实仅仅采用基于优先级队列的算法设计，而不考虑通信干扰和节点不在通信范围的情况，会造成比当前FIFO调用更差的性能。

因此，本文算法基于优先级队列，并且结合通信干扰和节点不在通信范围的传输特性的设计思路是合理的。本节还将通过仿真，验证算法的设计细节。

图3 仿真场景图

仿真中设定src1～src3产生优先级1～优先级3的报文，mobile-node1～mobile-node3分别接收优先级1～优先级3的报文。

1)无干扰节点，都在通信范围内

此时各链路丢失率Loss为0，各移动节点与数据链中心距离都小于最大通信距离。仿真设定src1包产生间隔为100秒/包;src2包产生间隔为8秒/包，持续时间为仿真开始后100～1000秒;src3包产生间隔为10秒/包。

图4为P1报文延迟图，由图可见FIFO在指控端有排队报文时，将会造成重要报文的延迟过大。在作战系统数据链通信中，带宽资源比较有限，存在报文重要性差异，因此必须要基于优先级队列设计指控端的队列算法。本文算法基于优先级设计，通过对报文发送次序的重新调配，使重要报文具有比较好的传输性能。

图4 P1报文延迟图

2)无干扰节点，有节点不在通信范围内

此时各链路丢失率Loss为0，mobile-node1处于通信范围外。图5为P2类报文的延迟图，通过分析可见采用PQ优先级队列算法时，指控仍然大量向mobilenode1发送报文，由于mobile-node1处于通信范围外，造成带宽浪费，算法性能甚至小于FIFO，因此在指控数据向数据链发送时的调度算法中不能只基于优先级进行设计。本文算法兼顾报文的目的地可达性，没有PQ优先级算法的类似问题。本文算法中接收方在通信范围内且优先级高的报文，通信延迟小，提高了无线链路的有效传输带宽。

图5 各算法下P2报文延迟图

3)有干扰节点，都在通信范围内

此时各链路丢失率环境如图6所示，mobile-node1＞mobile-node3＞mobile-node2，各移动节点与数据链中心距离都小于最大通信距离。

图6 各链路上的丢失率环境

在仿真中设定src1～src3产生的报文频率和大小相同。图7为本文算法下各移动节点的吞吐量，可见在图6丢失率环境下，本文算法按照丢失率环境重新调配吞吐率，使得丢失率比较低的链路获得更大的吞吐量，吞吐率与丢失率成反比关系。

图7 本文算法下各节点的吞吐量

图8为各算法下P2报文的发送速率，由于P2报文接收方为丢失率较低的mobile-node2，因此本文算法在存在排队报文时，相比其它两种算法，增加了该链路上的发送速率，增加了数据链的有效传输能力。

4 结束语

本文在吸收轮询调度算法和优先级调度算法优点的基础上，设计了基于优先级队列的多约束无线链路资源调度算法。通过仿真对比分析了FIFO、PQ优先级算法和本文算法，仿真结果表明，本文算法在有一定量报文等待排队发送时，相比FIFO和常规优先级算法PQ，重要报文的延迟较低，数据链通信系统内有效传输率高，提高了数据链的整体传输性能，克服了指控以先入先出发送引发的问题，具有较好的应用和推广价值。

图8 各算法下P2报文的发送速率

［1］骆光明，等.数据链-信息系统连接武器系统的捷径［M］.国防工业出版社，2008:1-10.

［2］赵琪，毛玉泉，任浩.直升机战术数据链的轮询组网方式分析［J］.电讯技术，2010，50(1):5-9.

［3］王文政，周经伦，罗鹏程.战术数据链网络体系结构研究［J］.计算机工程，2008，34(7):123-125.

［4］徐恪，等.高等计算机网络——体系结构，协议机制，算法设计与路由器技术［M］.北京:机械工业出版社，2003.

［5］谭兴晔，黄周松，雷振明.支持实时业务的队列调度机制与网络资源配置原则研究［J］.重庆邮电学院学报，2005，17(3):332-335.

［6］何楚，毛玉泉，王翀.战术数据链组网方式分析［J］.舰船电子工程，2008，28(3):85-86.

［7］陈敏.OPNET网络仿真［M］.北京:清华大学出版社，2004:371-377.

［8］张帅帅，郑龙，王玉文，等.基于OPNET的Link11数据链仿真设计［J］.通信技术，2011，44(2):48-50.