2. 陕西学前师范学院 数学与统计学院, 陕西 西安 710100;
3. 空军工程大学 防空反导学院, 陕西 西安 710043
雷达资源调度问题是指在雷达实际应用中，对雷达资源高效配置，其本质上是NP-hard问题。在雷达实际的应用环境中，根据雷达数据通道剩余的雷达资源与任务某些属性的匹配程度把任务分配给最佳通道，不但能提升所获得感知数据的质量，还能在一定程度上提高任务分配的效率。因此，李卓等[1]在满足数据需要时，提出一种与位置相关的多任务分配算法。蒋伟进等[2]将任务所覆盖区域划分成若干个互不冲突的子区间，并求取各个子区间上基于地理位置的最佳用户，最后把这些最佳用户的并集作为最终的任务分配结果；王鑫等[3]提出基于位置的任务分配服务计算框架，最大程度地提高信息质量、减少执行任务的预算和响应时间；仲崇权等[4]结合了生物启发式搜索功能，提升了任务分配的性能；王从文等[5]采用工人信誉度和距离对任务进行分配；熊远武等[6]将改进差分进化算法应用到多智能系统任务分配问题中；王卓昊等[7]提出根据不同任务的特点，将其分别分配给具备特定技能的用户，降低任务分配的成本；孟迪等[8]采用压缩感知方法对雷达任务进行调度。Komorniczak等[9]将任务优先设定工作交给神经网络来完成，大幅减少了主观经验在任务优先级分配问题上的影响，具有一定的先进性；Vine[10]利用模糊逻辑来解决自适应任务调度器的冲突问题，通过比较任务的相对优先级实现任务的自适应调度。
以上任务分配问题的关注点都集中在质量和成本两方面。在实际应用中，相控雷达阵任务通道的时间是固定的。因此，在确保不丢失重要任务的前提下，如何将任务合理地分配给雷达，是资源调度系统需要解决的问题。
针对现有研究的不足，本文综合考虑雷达时间资源、计算资源以及任务完成数量，从相控阵雷达数据通道与任务间的属性匹配程度出发，对多目标的任务分配问题进行了完整建模。鲸鱼优化算法是一种群智能优化算法，其主要特点是参数少、收敛快、易理解[11]。但该算法在全局寻优和收敛精度方面仍有待进一步提高，本文提出了柯西变异的模拟退火鲸鱼优化算法，并将该方法应用到雷达资源调度模型中，仿真结果表明该算法在跟踪任务调度率、平均时间偏移率和调度价值等方面都有较好的表现。
1 相关理论 1.1 多目标的相控阵雷达任务分配模型假设U={u1, u2, …, um}与S={s1, s2, …, sn}分别代表雷达跟踪通道集与任务集。其中, 雷达通道ui=〈Pi, Li, Ti〉, i=1, …, m, Pi为雷达跟踪通道号, Li为雷达通道i可分配的时间长度, Ti=〈Ki, Zi〉为雷达通道i所具备的资源信息, Ki为雷达任务种类集, Zi∈(0, 1)为任务匹配程度集合; 任务si={pi, di, ti, wi, ri, qi, fi, ui, Ei, ki}, pi为任务的优先级, di为波束的期望发射时间, ti为波束的发射持续时间, wi为波束在环境中的传播时间, ri为波束的接收期持续时间, qi为任务的总驻留时间, fi为任务的执行时间窗, ui为任务的执行截止期, Ei为执行该任务消耗的能量, ki为该任务对应的目标识别码。
1.2 鲸鱼优化算法设鲸鱼种群中一共有N个体, 第i只鲸鱼在第t次迭代更新的位置表示为Xit=(xi1t, xi2t, …, xiDt)。鲸鱼优化算法包括如下步骤[12]:
1) 包围猎物
当座头鲸确定最佳位置X*(j)后, 鲸鱼种群向最佳位置靠近, 迭代过程如下所示
|
(1) |
|
(2) |
式中: X(j+1)为第j+1次迭代后鲸鱼种群的位置; A和C为系数, 计算公式如下所示
|
(3) |
式中, a作为一个变量, 以
2) 发泡网攻击
发泡网攻击是鲸鱼攻击鱼群的主要方式。其数学模型包括: ①鲸鱼缩小包围圈, 即减小(3)式中的a值, 达到收缩包围效果；②鲸鱼螺旋变换位置, 即
|
(4) |
式中：l∈[-1, 1], p∈[0, 1]均为随机数; D′是头鲸与当前最优个体间的距离; b为常数。
3) 搜索捕食
鲸鱼的搜索捕食过程建模如(5)~(6)式所示
|
(5) |
|
(6) |
式中, Xrand是一个随机鲸鱼的位置。
2 柯西变异的模拟退火鲸鱼优化算法褚鼎立等[13]在鲸鱼算法中引入自适应权重和模拟退火算法，提高了算法寻优能力，但仍无法解决算法易陷入局部最优问题。在文献[14]的基础上，本文引入柯西分布函数以提高算法局部寻优能力，提出了柯西变异的模拟退火鲸鱼优化算法。图 1给出了算法的流程图。
|
| 图 1 柯西变异的模拟退火鲸鱼优化算法流程图 |
1) 引入非线性收敛因子
在传统鲸鱼算法中, 公式(3)中的收敛因子a呈线性变化, 导致整个算法收敛过慢。采用一种非线性收敛因子a(t), 定义如(7)式所示
|
(7) |
式中，tmax为最大迭代次数。
自适应权重ω(t)随迭代次数动态变化如下所示
|
(8) |
算法更新数学模型为
|
(9) |
2) 加入柯西变异局部抖动
柯西概率密度函数与正态分布函数都可以作为扰动函数, 其中柯西概率密度函数具有较宽的分布范围。故本文将柯西概率密度函数引入到鲸鱼算法中, 见公式(10)。
|
(10) |
3) 模拟退火混合更新策略的鲸鱼优化算法
根据雷达的任务参数模型, 将任务优先级、任务期望发射时间、任务截止时间、任务执行窗口、任务所在调度间隔的开始时间和结束时间以及任务的能量消耗这7个因素列为适应度函数的参数。经过多次试验, 最终确定评价个体的适应度函数为
|
(11) |
式中: pi为任务的优先级; di为波束的期望发射时间; fi为任务的执行时间窗; Ei为执行该任务消耗的能量; B为任务的期望发射时间; D为任务的期望截至时间。
3 算法设计与仿真实验分析 3.1 算法设计针对相控阵雷达的任务调度, 应用柯西变异的模拟退火鲸鱼优化算法进行相控阵雷达资源调度的设计, 流程如图 2所示。
|
| 图 2 相控阵雷达资源调度流程图 |
在算法的追踪模式中, 个体将进行速度和位置的更新, 更新公式为
|
(12) |
式中：L表示局部最优值；G表示全局最优值。
对于中近程警戒类雷达, 其调度周期一般设定为120 ms, 参数S=120 ms。同时考虑到在空域中进行搜索需要覆盖一片空域, 需要花费较多的搜索时间, 设定系统仿真的时间T=60 s。对于地面防空雷达来说, 雷达的辐射能量一般能够满足能量需求, 设置其最大功率Ermax=120 kW。为了验证算法的有效性, 在单载频脉冲的环境下进行验证。根据相控阵雷达的任务不同, 其设置参数如表 1所示。
| 任务类型 | piwm | t | w | r/μs | f/ms | Δt/μs |
| 确认 | 1 | 1 | 待计算 | 2 | 2.3 | |
| 精跟 | 2 | 0.3 | 待计算 | 0.5 | 2.2 | 100~200 |
| 失跟 | 6 | 1 | 待计算 | 2 | 2.2 | 150 |
| 普跟 | 3 | 0.4 | 待计算 | 0.5 | 3.2 | 200~300 |
| 监视 | 5 | 0.5 | 待计算 | 0.5 | 5.4 | 300~400 |
| 搜索 | 4 | 0.4 | 2 | 2 | 4.8 |
针对基于柯西变异的模拟退火鲸鱼优化算法, 此处设置自适应分组率。分组率的计算公式为
|
式中, Mmax, Mmin分别为分组率M的最大值和最小值; I和tc分别表示最大和当前迭代次数。
为验证算法的有效性, 以跟踪任务调度率(TSR)[14]、平均时间偏移率(ATOR)[15]、调度价值(RV)[16]为评估指标。TSR为调度成功的跟踪任务数量与请求的跟踪任务数量的比值, 其计算公式为
|
式中, Ntrack, exe为调度成功的跟踪任务数量, Ntrack, all为系统产生的跟踪任务数量。
ATOR为已调度任务的实际执行时间与请求执行时间的偏移量与任务时间窗的比值, 计算公式为
|
式中：Nexe为调度成功任务的数量; ai为任务的实际执行时间; di为任务的期望波束发射时间; fi为任务的执行时间窗。
RV为已调度任务的综合优先级之和, 公式为
|
式中：Nexe为调度成功任务的数量; pi为任务的综合优先级。
3.2 仿真及结果分析将骆驼算法(MCA)[17]、柯西变异的模拟退火鲸鱼优化算法(W-SA-WOA)和平衡优化(EO)[18]调度算法在相同的调度环境下进行仿真。任务相关参数如表 2所示。
| 任务类型 | piwm | 脉冲个数 | 脉冲宽度 | 脉冲周期 | 时间窗 |
| 验证 | 1 | 29 | 100 | 2.3 | |
| 精跟 | 2 | 21 | 80 | 2.2 | 100~200 |
| 失跟 | 6 | 23 | 90 | 2.2 | 150 |
| 普跟 | 3 | 21 | 110 | 3.2 | 200~300 |
| 监视 | 5 | 26 | 110 | 5.4 | 300~400 |
| 搜索 | 4 | 28 | 100 | 4.8 |
图 3为3种算法的雷达任务调度序列对比图。图中展示了不同数量的任务的时间分布情况。从图中可以看出，EO算法在雷达资源调度过程中全局寻优能力较弱，导致任务在分配期间出现了有些任务分配时间上的重合，由于雷达任务的不可分割性，这些重合的任务就会导致任务调度失败，例如在图 3a)第900~1 000 ms之间有较多任务时间上重合。其次，也会导致某些时间上出现空闲，造成资源的浪费，例如在图 3a)中第400~500 ms之间出现了较多的空闲时间。
|
| 图 3 3种算法的雷达任务调度序列对比图 |
同理，对比发现MCA算法和W-SA-WOA算法都能够执行任务，但是MCA任务调度的执行率不如W-SA-WOA算法。主要原因是W-SA-WOA算法在全局寻优能力上更胜一筹，使得整个任务调度过程中，时间都可以被合理地利用。而MAC算法在雷达任务调度过程中时间轴上明显有空闲的时间没有被分配，例如图 3c)中的100, 150, 250, 400 ms等时间点上明显空闲。
图 4展示了3种调度算法关于评价指标TSR、ATOR、RV的对比。
|
| 图 4 3种算法的评价指标曲线对比图 |
由图 4a)可知，当目标数量增长至30时，W-SA-WOA算法的TSR接近100%，而MCA算法和EO算法开始出现任务丢失；随着目标的增多，3种算法都开始出现任务丢弃。但在同一目标数量时，本文调度算法始终保持着最高的TSR。这表明W-SA-WOA能够最大限度地利用时间资源，在固定的时间间隔内调度更多的任务。
由图 4b)可知，当目标数为13时，W-SA-WOA调度得到的ATOR为12.94%，且随着目标数量增加，始终保持最低的ATOR。当目标数量增加至120时，调度任务的ATOR为32.04%。由图可知，相较于另外2种算方法，W-SA-WOA算法在高效地调度任务的同时，也能最大程度地减少任务的执行时间偏移量。
由图 4c)可知，当目标数量较少(10个及以下)时，3种调度算法的RV相差较小。当目标数量增加时，W-SA-WOA算法的调度价值增长得更快，表明W-SA-WOA算法在高任务负载情况下仍有最好的任务调度能力。
综合分析可知，W-SA-WOA算法在跟踪任务调度率、平均时间偏移率和调度价值方面都优于MCA和EO调度算法。事实上，仿真还记录了不同优先级任务的详细执行率，结果与上述结论一致。总的来说，与目前大多数基于MCA和EO及其衍生的算法相比，基于柯西变异的模拟退火鲸鱼雷达资源调度算法在雷达任务调度问题上具有一定的优势。
4 结论雷达系统的任务调度一直是雷达资源调度领域的热点问题。结合模拟退火算法对鲸鱼优化算法进行改进，并分别对搜索模式和跟踪模式进行了优化，最终形成了基于柯西变异的模拟退火鲸鱼雷达资源调度的防空雷达任务调度算法。与比较流行的骆驼算法和平衡优化算法相比，所提算法在跟踪任务调度率、平均时间偏移率和调度价值等方面都有较好的表现，显示了本文算法在解决雷达任务调度问题上的卓越能力。
| [1] |
李卓, 徐哲, 陈昕, 等. 面向移动群智感知的位置相关在线多任务分配算法[J]. 计算机科学, 2019, 46(6): 102-106.
LI Zhuo, XU Zhe, CHEN Xin, et al. Location-related online multi-task assignment algorithm for mobile crowd sensing[J]. Computer Science, 2019, 46(6): 102-106. (in Chinese) |
| [2] |
蒋伟进, 吕斯健, 刘跃华, 等. 基于城市轨道交通的群智感知任务分发方法[J]. 电子与信息学报, 2021, 43(10): 3035-3042.
JIANG Weijin, LYU Sijian, LIU Yuehua, et al. Task distribution method of participatory sensing based on urban rail transit[J]. Journal of Electronics & Information Technology, 2021, 43(10): 3035-3042. (in Chinese) DOI:10.11999/JEIT200510 |
| [3] |
王鑫, 廖祎玮, 赵国生, 等. 一种面向任务需求的群智感知任务分配模型[J]. 计算机工程与科学, 2021, 43(8): 1512-1520.
WANG Xin, LIAO Yiwei, ZHAO Guosheng, et al. A task assignment model of mobile crowd sensing oriented requirements[J]. Computer Engineering & Science, 2021, 43(8): 1512-1520. (in Chinese) DOI:10.3969/j.issn.1007-130X.2021.08.021 |
| [4] |
仲崇权, 刘正一, 赵亮, 等. 基于启发式最短路径的PAC任务调度算法[J]. 仪表技术与传感器, 2016(12): 129-135.
ZHONG Chongquan, LIU Zhengyi, ZHAO Liang, et al. Task scheduling algorithm in PAC system based on heuristic shortest path[J]. Instrument Technique and Sensor, 2016(12): 129-135. (in Chinese) DOI:10.3969/j.issn.1002-1841.2016.12.032 |
| [5] |
王从文, 王璨, 徐春明, 等. 基于工人信誉度和距离的任务分配算法[J]. 价值工程, 2020, 39(16): 201-203.
WANG Congwen, WANG Can, XU Chunming, et al. Task assignment algorithm based on worker credibility and distance[J]. Value Engineering, 2020, 39(16): 201-203. (in Chinese) DOI:10.3969/j.issn.1006-4311.2020.16.087 |
| [6] |
熊远武, 赵岭忠, 翟仲毅. 基于差分进化算法多智能体任务分配[J]. 计算机工程与设计, 2019, 40(10): 3020-3029.
XIONG Yuanwu, ZHAO Lingzhong, ZHAI Zhongyi. Multi-agent task assignment based on differential evolution algorithm[J]. Computer Engineering and Design, 2019, 40(10): 3020-3029. (in Chinese) |
| [7] |
王卓昊, 杨冬菊, 徐晨阳. 基于ISE算法的分布式ETL任务调度策略研究[J]. 计算机科学, 2019, 46(12): 1-7.
WANG Zhuohao, YANG Dongju, XU Chenyang. Research on distributed ETL tasks scheduling strategy based on ISE algorithm[J]. Computer Science, 2019, 46(12): 1-7. (in Chinese) DOI:10.11896/jsjkx.190100023 |
| [8] |
孟迪, 张群, 罗迎, 等. 基于脉冲交错的数字阵列雷达任务优化调度算法[J]. 航空学报, 2017, 38(8): 172-181.
MENG Di, ZHANG Qun, LUO Ying, et al. An effective scheduling algorithm for digital array radar based on pulse interleaving[J]. Acta Aeronautica et Astronautica Sinica, 2017, 38(8): 172-181. (in Chinese) |
| [9] | KOMORNICZAK W, PIETRASINSKI J. Selected problems of MFR resources management[C]//The 3rd International Conference on Information Fusion, Paris, France, 2000: 10-13 |
| [10] | VINE M T. Fuzzy logic in radar resource management[C]//IEEE Multifunction Radar and Sonar Sensor Management Techniques, 2001 |
| [11] |
蔡雨岑, 杜鹏桢. 基于平衡鲸鱼优化算法的无人车路径规划[J]. 控制与决策, 2021, 36(11): 2647-2655.
CAI Yucen, DU Pengzhen. Path planning of unmanned ground vehicle based on balanced whale optimization algorithm[J]. Control and Decision, 2021, 36(11): 2647-2655. (in Chinese) |
| [12] | KAUR G, ARORA S. Chaotic whale optimization algorithm[J]. Journal of Computational Design and Engineering, 2018, 5(3): 275-284. DOI:10.1016/j.jcde.2017.12.006 |
| [13] |
褚鼎立, 陈红, 王旭光. 基于自适应权重和模拟退火的鲸鱼优化算法[J]. 电子学报, 2019, 47(5): 992-999.
CHU Dingli, CHEN Hong, WANG Xuguang. Whale optimization algorithm based on adaptive weight and simulated annealing[J]. Acta Electronica Sinica, 2019, 47(5): 992-999. (in Chinese) DOI:10.3969/j.issn.0372-2112.2019.05.003 |
| [14] |
孙铭才, 张秦, 袁俊超, 等. 基于改进时间窗的相控阵雷达跟踪任务调度方法[J]. 测控技术, 2017, 36(10): 74-78.
SUN Mingcai, ZHANG Qin, YUAN Junchao, et al. Tracking task scheduling method of phased array radars based on modified time window[J]. Measurement & Control Technology, 2017, 36(10): 74-78. (in Chinese) DOI:10.3969/j.issn.1000-8829.2017.10.018 |
| [15] |
段毅, 谭贤四, 曲智国, 等. 基于偏移影响率的相控阵雷达事件调度方法[J]. 系统工程与电子技术, 2017, 39(11): 2470-2476.
DUAN Yi, TAN Xiansi, QU Zhiguo, et al. Task scheduling algorithm for phased array radar based on shifting impact rate[J]. Systems Engineering and Electronics, 2017, 39(11): 2470-2476. (in Chinese) DOI:10.3969/j.issn.1001-506X.2017.11.12 |
| [16] |
段毅, 谭贤四, 曲智国, 等. 基于价值密度的相控阵雷达事件调度算法[J]. 雷达科学与技术, 2018, 16(3): 291-297.
DUAN Yi, TAN Xiansi, QU Zhiguo, et al. Task scheduling algorithm for phased array radar based on value density[J]. Radar Science and Technology, 2018, 16(3): 291-297. (in Chinese) DOI:10.3969/j.issn.1672-2337.2018.03.010 |
| [17] |
任春慧, 刘升, 张伟康, 等. 柯西变异的骆驼算法优化与应用[J]. 计算机工程与应用, 2021, 57(21): 87-94.
REN Chunhui, LIU Sheng, ZHANG Weikang, et al. Optimization and application of cauchy mutation camel algorithm[J]. Computer Engineering and Applications, 2021, 57(21): 87-94. (in Chinese) DOI:10.3778/j.issn.1002-8331.2010-0007 |
| [18] |
齐洁, 汪定伟. 极值优化算法综述[J]. 控制与决策, 2007, 22(10): 1081-1085.
QI Jie, WANG Dingwei. Overview of extremal optimization algorithm[J]. Control and Decision, 2007, 22(10): 1081-1085. (in Chinese) DOI:10.3321/j.issn:1001-0920.2007.10.001 |
2. School of Mathematics and Statistics, Shaanxi Xueqian Normal University, Xi'an 710100, China;
3. College of Air Defense and Anti-Missile, Air Force Engineering University, Xi'an 710043, China
