基于排队服务的相控阵雷达任务调度管理方法

鲍鹏飞，黄孝鹏，崔威威，丁世谱

(中国船舶重工集团公司第七二四研究所，南京 211153)

0 引 言

相控阵雷达具有波束快速捷变、资源可控性强等技术特点[1]，可实现同时多功能，具有灵活性高、自适性强的探测优势，同时也对相控阵雷达任务调度管理技术[2]的需求更加凸显。相控阵雷达任务调度需要考虑调度策略选择、任务优先级确定和调度算法设计[3-5]，并直接影响雷达最大效能的发挥。传统任务调度方法根据系统下发任务在一个调度间隔内安排调度序列[6]，缺乏考虑任务总体性，难以总体上使任务到达与调度相适应。本文引入排队服务系统概念[7-8]，提出一种相控阵雷达任务动态排队管控方法，在系统层面考虑相控阵雷达资源服务系统的参数优化设计、任务到达分布、服务时间分布、任务状态转换以及任务-资源动态自适应性，并增强任务排队合理性，保证任务有序执行，提高调度服务水平。

排队论起源于Erlang A K对电话服务系统的研究，是研究系统排队与服务规律的一门学科。它越来越多地渗透到军事、经济、生产与服务等多种部门。[9]随着排队特征、排队规则、服务机构变得越来越复杂，相关研究越来越多。[10-11]利用排队理论构建各种应用服务系统模型，解决复杂现实问题，并分析服务系统最佳运行的各项指标，对于提出服务改进措施、优化服务系统结构、降低系统的研制成本和提高系统服务效率有重要意义。基于排队服务法的任务调度管理方法将雷达任务到达和执行的过程看作是“排队服务”过程，通过“服务台”实现相控阵雷达的任务调度管理。

1 服务系统基本概念

在服务系统中要求得到某种服务的对象称之为顾客，为顾客提供服务的机构称之为服务台。服务系统基本运行过程为：顾客进入服务系统，当服务台繁忙时，按一定规则进行排队，服务台按一定规则对顾客进行服务，服务完成后顾客离开服务系统。可见，一个服务过程由以下几个基本部分组成：输入过程(顾客)与到达规则、排队规则、服务机构、服务时间与服务规则。

服务系统中服务台根据其数量可以分为无服务台、单服务台、有限个服务台以及无限个服务台。根据服务流程关系，多个(有限)服务台又可分为串联与并联形式，主要有单服务台单队列结构、多服务台(并联)单对列结构、多服务台多队列结构、多服务台(串联)单队列结构、多服务台混合结构。[12]实际服务系统可由以上构成各种结构组合组成。图1是相控阵雷达任务调度服务系统的服务流程图。

针对雷达任务调度管理应用场景，基于排队服务理论，给出雷达任务调度服务系统中一些概念：

(1) 顾客：雷达任务；

(2) 服务台：调度器；

(3) 排队规则：从高优先级到低优先级排队；

(4) 服务规则：有优先权的服务(Priority，PR)；

(5) 队长：服务系统中雷达任务数量；

(6) 排队长：系统中排队等待调度的雷达任务数量；

(7) 逗留时间：一个雷达任务在系统中停留时间；

(8) 等待时间：一个雷达任务排队等待执行的时间；

(9) 服务强度：任务到达速率与服务速率之比；

(10) 排队阈值：设定调度服务系统可容纳排队的最大任务数。

2 雷达资源任务调度排队服务系统

将排队论引入雷达资源调度，构建雷达任务排队服务系统模型，分析该系统模型，优化系统的服务指标参数，实现资源的有效调度与管控。

2.1 排队服务系统模型

顾客平均到达速率λ与规律、顾客平均服务速率u与规律和服务通道数目对服务系统的运行有重要影响。1953年，肯达(Kendal)用符号的方式描述服务系统，用[A/B/C]表示一个服务系统的基本模型，其中A、B、C分别表示服务系统的顾客到达规律、服务时间的分布规律和服务通道数目。由于该服务参数基本模型缺少考虑顾客及其系统其他特性对服务运行的重大影响，1966年里氏(Lee)在肯达的基础上完善了服务系统符号化描述，即[A/B/C]：[d/e/f]；d、e、f分别表示服务系统的最大容量、顾客总体数量和服务规则，可以用这样6个符号描述服务系统模型特征。

针对特定空域特定目标的任务，通过大量任务分析，得到雷达任务分布模型。设雷达任务近似泊松流，雷达任务平均到达速率λ、任务平均服务速率u。排队服务系统限制任务数为N，新任务到达且系统任务满时则按一定(优先级)规则删除任务。对于单雷达系统而言，该任务调度模型近似[M/M/1]∶[N/∞/PR]系统模型。多雷达有控制调度中心时，任务调度模型近似[M/M/C]∶[N/∞/PR]系统模型。构建服务模型后，可获得服务系统排队任务数期望值Lq、任务在系统平均停留时间Ws、排队等待时间Wq等关键指标参数。

在处理系统状态不断变化的雷达调度过程时，可以用状态转移图来描述这一过程。调度服务系统的状态可以用系统中的任务数n(n=1,2,3,…)表示，可见系统的状态是一间断、变化的。雷达任务请求的到达或离去都会引起系统状态发生变化。[13]任务调度服务系统的生灭过程状态转移图如图2、图3所示，圈中的数字表示系统的状态，一条箭线表示从状态i到状态j的状态转移关系，箭头方向表示状态转移方向，箭线旁边的符号λ、μ分别表示从一个状态转换到另一状态的任务到达速率和离开速率。

基于服务系统状态转换图，建立稳态的状态平衡方程，得到调度服务系统的运行参数与指标，可为雷达任务调度提供参考。根据稳态平衡方程基本原理，即对于任意状态k，产生该状态与破坏该状态的平均速率相等时系统可达到稳态平衡，可建立稳态平衡方程：

Pk+1uk+1+Pk-1λk-1=Pkλk+Pkuk

(1)

式中Pk表示系统状态为k时的概率，特别是当k=1时有

P1u1=P0λ0

(2)

由此可以得到一组稳态平衡方程。联立方程组可以求出一般服务系统的运行指标：

服务系统空闲时概率为

顾客数为n的概率为

Pn=CnP0

服务系统的任务数量期望值为

排队任务数数学期望为

其中

具体到调度服务系统可以在上面的平衡方程加入适当的条件。

3 基于排队服务的任务管控算法

目前，雷达资源调度有从任务优先级方面考虑，如通过网络加权的方法、优先级表算法、BP神经网络得到任务的优先级，也有从参数设置方面考虑，如设置合理跟踪数据率、波位编排方式、驻留时间等提高任务执行效率。在资源调度服务系统的参数优化设计、服务时间分布、动态自适应等层面的研究相对欠缺。

“排队等待”是服务系统广泛存在的现象。就雷达任务调度系统而言，排队论主要解决任务拥挤问题，通过优化服务系统参数、有效安排任务和动态匹配任务-资源，提高任务管控水平和资源利用率。排队服务法利用雷达先验知识分析计算服务系统参数，并通过反馈控制使任务期望数(队长)控制在一定范围，从而提高相控阵雷达资源调度服务水平。

排队服务资源管控算法：通过分析相控阵雷达任务先验知识，获取资源调度服务系统的参数，如平均等待队长、平均任务等待时间等，再组合应用专家群评分、判断矩阵、加权计算等方法得到任务优先级，生成任务执行序列。通过监控任务排队队长是否超过排队阈值，合理分配任务-资源，并可调整调度间隔，优化系统服务速率，使得任务到达与任务执行的动态平衡，实现最佳服务水平。

设计算法流程如图4所示。

Step1：分析大量相控阵雷达任务的先验知识，得到相控阵雷达任务分布模型。设雷达任务流近似泊松流，计算雷达任务平均到达速率λ、任务平均服务速率u，获取此服务系统排队任务数期望值Lq、任务在系统平均停留时间Ws、排队等待时间Wq等参数。

Step2：初始化系统参数。

Step3：任务到达，判断系统任务是否为空，是则转Step 5。

Step4：根据排队系统参数设置排队阈值，调整相关服务参数。判断服务系统任务是否已满，若已满则先综合优先级排序，从队列中剔除排序最后的任务，保证重要任务优先执行，并根据任务调度规则决定该剔除任务是进入删除链表还是等待下个调度周期执行；若未满则先优先级排序，并根据时间窗准则判断任务是否执行。

Step5：执行任务并统计计数。

Step6：服务效率计算，如调度成功率、排队等待时间等参数。

Step7：判断任务是否执行完毕，若没有则转Step 3。

Step8：调度效能评估，结束调度。

4 仿真分析

仿真条件：单雷达系统仿真时间为1 s，任务平均到达率50个/s，任务服务率60个/s，计算任务平均排队长度4.17。排队阈值分别为N1=4、N2=8，任务时间窗100 ms。任务服务时间为负指数分布，设置搜索、跟踪、协同、确认等任务若干。任务按综合和优先级预先排序完成，进行排队调度仿真。

如图5结果表明，当排队阈值为4时部分任务丢失，调度成功率91.7%(图5中实线部分为丢失的任务)，平均等待时间0.0209 s，排队阈值为8时调度成功率100%，平均等待时间0.0314 s，表明增加系统排队阈值，可提高任务调度成功率，但等待时间有所增加。

仿真图6更直观表明，排队阈值越大任务调度成功数越多，但同时任务排队等待时间越长。任务调度时需要平衡考虑调度成功率与排队等待时间，从而调整服务系统排队阈值、服务速率等参数。

若探测区域S(如图7)的目标到达率由50个/s增加至100个/s，服务率60个/s、排队阈值N=4保持不变时，为保证目标有效探测，需增加探测资源，可利用两部雷达探测，并采用两种调度策略。调度策略分析如下：

策略1：分区扫描，两部雷达扫描区域分别为S1、S2；

策略2：两部雷达联合扫描区域S，由中心节点控制任务分发。

两种策略下系统的服务参数如表1，可以看出策略2调度效果更好。

运行指标策略1策略2系统空闲概率0.25060.1307平均排队任务数2.45881.0678平均系统内任务数3.95772.5895平均排队等待时间(s)0.02730.0117平均系统逗留时间(s)0.04410.0284

5 结束语

本文主要研究基于排队服务的相控阵雷达任务调度管理以及资源动态管控方法。该方法将雷达任务到达与执行看作是“排队服务”过程，通过对相控阵雷达大量任务的先验知识分析，获取任务排队平均长度、平均等待时间等服务系统参数；基于任务截止期、工作方式优先级、驻留时间、期望执行时间等特征参数，计算任务的综合优先级并生成任务队列；动态匹配雷达系统资源，实现任务与资源的动态平衡。仿真分析表明任务排队长度和调度成功率受排队阈值的影响较大，需要平衡考虑排队长度和调度成功率参数，设定合理的排队阈值；同时，设计有效的调度策略，调整排队服务模型，可有效提升调度性能。

参考文献:

[1] 邵春生. 相控阵雷达研究现状与发展趋势[J]. 现代雷达,2016, 38 (6):1-4.

[2] 郑玉军,田康生,邢晓楠,丰坤. 带时间窗的相控阵雷达实时任务调度方法[J]. 火力与指挥控制,2016(10):70-74.

[3] 赵培焱,孙涛,陈鲸. 空间探测相控阵雷达系统的任务优化编排仿真[J]. 计算机仿真,2013(7):21-24.

[4] 姚婧,宋锐,王壮,胡卫东. 空间探测相控阵雷达系统的观测任务编排仿真[J]. 计算机仿真,2006(10):65-68，71.

[5] 田钢,凌牧,汪晋.基于同时多波束跟踪的任务调度方法研究[J].现代雷达,2016, 38(4):46-49.

[6] Hasan SMir, Adel Guitouni. Variable Dwell Time Task Scheduling for Multifunction Radar[J]. IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2014, 11(2):463-472.

[7] 宁宣熙.管理运筹学教程[M].北京：清华大学出版社,2007.

[8] 宗群,牙淑红,王振世.基于排队论的上高峰电梯群控调度的研究[J].系统工程与电子技术,2003, 25(6):722-725.

[9] 郑孟雪. 多服务窗串联排队模型研究[D].重庆师范大学,2015.

[10] 汪浩,黄明和,龙浩. 基于G/G/1-FCFS、M/G/1-PS和M/G/∞排队网络的Web服务组合性能分析[J]. 计算机学报,2013(1):22-38.

[11] 刘名武,杨迎春,马永开. 一类排队服务系统的最优控制策略研究[J]. 控制理论与应用,2012(3):323-330.

[12] 张龙. 基于随机服务理论的施工机群配置对温度离析的影响研究[D].长安大学,2013.

[13] 艾合买提·卡斯木. 几个排队模型的动态分析[D].新疆大学,2013.