基于滑动时间窗的机载传感器多任务调度算法

冉华明

doi:10.13700/j.bh.1001-5965.2023.0488

基于滑动时间窗的机载传感器多任务调度算法

doi: 10.13700/j.bh.1001-5965.2023.0488

冉华明^{1, 2, ,}

1.
复杂航空系统仿真全国重点实验室，成都 610036
2.
中国电子科技集团公司第十研究所，成都 610036

详细信息

通讯作者:
E-mail：ranhuaming7245@163.com

中图分类号: V243.2；TN959.73；TP272
计量
- 文章访问数: 249
- HTML全文浏览量: 98
- PDF下载量: 18
- 被引次数: 0
出版历程
- 收稿日期: 2023-07-27
- 录用日期: 2023-09-22
- 网络出版日期: 2023-10-13
- 整期出版日期: 2025-09-30

Airborne sensor multi-task scheduling algorithm based on slide time window

RAN Huaming^{1, 2
, ,}

1.
National Key Laboratory of Complex Aviation System Simulation，Chengdu 610036，China
2.
The 10th Research Institute of China Electronics Technology Group Corporation，Chengdu 610036，China

More Information

Corresponding author: E-mail：ranhuaming7245@163.com

摘要

摘要:
针对机载传感器任务管理系统的多任务调度效能受多任务请求之间存在的执行时间窗口冲突所影响的问题，根据各任务请求的可执行时间窗等任务请求信息，描述各任务请求的前滑时间窗、后滑时间窗等任务调度约束信息，并在此基础上设计基于滑动时间窗的机载传感器多任务调度算法。筛选出可在调度周期内执行任务请求，并按优先级排序生成待调度任务列表；计算各待调度任务与各已有调度方案的时间交叠关系，形成多个时间片，通过判断待调度任务能否插入扩展后的时间片，不断更新调度方案集合；从调度方案集合中优选出最佳的机载传感器任务调度方案。仿真结果表明：所设计算法调度效能的中位数可达到最优算法调度效能的96.52%以上，且调度效能和计算耗时受调度规模和任务时间精细度的影响较少，具有较强的适应性。
- 机载传感器 /
- 多任务调度 /
- 前后滑动时间窗 /
- 多任务请求 /
- 执行时间窗口冲突 /
- 任务调度约束信息
Abstract:
Aiming at the problem that the multi-task scheduling efficiency of the airborne sensor task management system was reduced due to the execution time window conflicts among multiple task requests, the task scheduling constraint information, include the forward slide time window and the back slide time window of each task, is depicted according to the task request information, such as the executable time window of each task request, and a multi-task scheduling algorithm for the airborne sensor is designed based on the slide time window. Firstly, task requests that can be executed within the scheduling period are selected, and a list of tasks to be scheduled is generated based on priority sorting. Then, multiple time slices are formed by calculating the time overlap relationship between each task to be scheduled and each existing scheduling scheme, and the scheduling scheme set is continuously updated by determining whether the task to be scheduled can be inserted into the extended time slice. Finally, the optimal airborne sensor task scheduling scheme is selected from the scheduling scheme set. The simulation results show that the median scheduling efficiency of the designed algorithm can reach over 96.52% of the optimal algorithm’s scheduling efficiency, and the scheduling efficiency and computational time of the designed algorithm are rarely affected by the scheduling scale and granularity of the task time, the designed algorithm has strong adaptability.
- airborne sensor /
- multi-task scheduling /
- forward-back slide time window /
- multiple task requests /
- execution time window conflicts /
- task scheduling constraint information

HTML全文

图 1 传感器任务请求信息

Figure 1. Sensor task request informations

下载: 全尺寸图片幻灯片

图 2 任务调度约束信息

Figure 2. Task scheduling constraint informations

下载: 全尺寸图片幻灯片

图 3 机载传感器多任务调度逻辑框

Figure 3. Logic block of airborne sensor multi-task scheduling

下载: 全尺寸图片幻灯片

图 4 传感器多任务最佳调度方案生成流程

Figure 4. Flow-process for sensor generating the optimal scheduling scheme for multi-tasks

下载: 全尺寸图片幻灯片

图 5 时间片划分示意图

Figure 5. Schematic diagram of time slice division

下载: 全尺寸图片幻灯片

图 6 时间片滑动扩展示意图

Figure 6. Schematic diagram of time slice sliding extension

下载: 全尺寸图片幻灯片

图 7 任务实际执行时间窗更新示意图

Figure 7. Schematic diagram of updating of actual execution time window for task

下载: 全尺寸图片幻灯片

图 8 前后滑动时间窗调度算法流程

Figure 8. Flow-process for forward-back slide time window scheduling algorithm

下载: 全尺寸图片幻灯片

图 9 本文算法在场景1中调度效能比值分布

Figure 9. Scheduling efficiency ratio distribution of the proposed algorithm in scene 1

下载: 全尺寸图片幻灯片

图 10 本文算法和对比算法在场景1中计算耗时

Figure 10. Calculation time for the proposed algorithm and comparison algorithm in scene 1

下载: 全尺寸图片幻灯片

图 11 场景1某次实验中各任务的请求信息

Figure 11. Request informations for each task for one test in scene 1

下载: 全尺寸图片幻灯片

图 12 场景1某次实验的任务调度方案

Figure 12. Task scheduling scheme for one test in scene 1

下载: 全尺寸图片幻灯片

图 13 本文算法在场景2中调度效能比值分布

Figure 13. Scheduling efficiency ratio distribution of the proposed algorithm and comparison algorithm in scene 2

下载: 全尺寸图片幻灯片

图 14 本文算法和对比算法在场景2中计算耗时

Figure 14. Calculation time for the proposed algorithm and comparison algorithm in scene 2

下载: 全尺寸图片幻灯片

图 15 本文算法与对比算法在场景3中调度效能比值分布

Figure 15. Statistical graph of scheduling efficiency ratio distribution of the proposed algorithm and comparison algorithm in scene 3

下载: 全尺寸图片幻灯片

图 16 本文算法和对比算法在场景3中计算耗时

Figure 16. Calculation time for the proposed algorithm and comparison algorithm in scene 3

下载: 全尺寸图片幻灯片

图 17 场景3某次实验中各任务的请求信息

Figure 17. Request information for each task for one test in scene 3

下载: 全尺寸图片幻灯片

图 18 场景3某次实验的任务调度方案

Figure 18. Task scheduling scheme for one test in scene 3

下载: 全尺寸图片幻灯片

图 19 2种算法计算耗时随任务时间精细度变化

Figure 19. Computational time of two algorithms versus granularity of task time

下载: 全尺寸图片幻灯片

图 20 2种算法调度效能比值随任务时间精细度变化

Figure 20. Scheduling efficiency ratio of two algorithms versus granularity of the task time

下载: 全尺寸图片幻灯片

表 1 各仿真场景时间精细度参数

Table 1. Time granularity parameters for each simulation scene

场景	任务时间精细度/s
场景1	1.0
场景2	0.5
场景3	0.1

下载: 导出CSV

表 2 各测试集仿真参数

Table 2. Simulation parameters for each test set

测试集编号	调度开始时间/s	调度结束时间/s	任务数
1	0	20	20
2	0	40	40
3	0	60	60
4	0	80	80
5	0	100	100

下载: 导出CSV

表 3 每次测试时随机生成任务请求序列的参数范围

Table 3. Parameters range for randomly generating scheduling task request sequence during each test

持续时间范围/s	滑动时间窗范围/s	任务优先级范围
1～8	0～10	1～10

下载: 导出CSV

表 4 本文算法和对比算法在场景1中调度效能比值

Table 4. Scheduling efficiency ratio distribution of the proposed algorithm and comparison algorithm in scene 1

测试集编号	调度效能比值/%						离群值个数
测试集编号	最大值	上四分位数	中位数	下四分位数	最小值	最小离群值	离群值个数
1	100.00	100.00	99.35	95.39	88.82	86.99	2
2	100.00	98.50	97.02	95.36	91.24		0
3	100.00	98.95	97.73	96.00	91.72	87.26	2
4	100.00	98.19	97.40	95.95	92.65		0
5	99.44	97.68	96.52	95.58	93.56	91.69	2

下载: 导出CSV

表 5 本文算法和对比算法在场景1中计算耗时

Table 5. Calculation time for the proposed algorithm and comparison algorithm in scene 1

测试集编号	本文算法计算耗时/s			对比算法^[21]计算耗时/s
测试集编号	最大值	平均值	最小值	最大值	平均值	最小值
1	0.22	0.05	0.03	0.75	0.16	0.03
2	0.39	0.23	0.12	6.97	1.44	0.34
3	1.14	0.63	0.43	18.05	5.49	2.49
4	1.40	0.90	0.67	33.05	11.99	5.87
5	1.58	1.13	0.90	42.46	20.96	11.12

下载: 导出CSV

表 6 场景1某次实验的任务请求信息表

Table 6. Task request information tables for one test in scene 1

任务编号	优先级	最早开始时间/s	最晚结束时间/s	持续时间/s
1	2.995	10	20	8
2	9.394	1	10	1
3	8.186	0	5	2
4	6.517	5	18	7
5	6.238	2	10	6
6	5.267	8	13	2
7	9.659	0	7	3
8	7.284	2	10	8
9	4.519	15	20	1
10	4.443	13	18	5
11	5.201	13	19	2
12	1.123	13	17	3
13	5.678	5	8	2
14	3.023	7	12	1
15	9.685	9	19	2
16	2.278	5	15	4
17	5.556	1	4	3
18	6.614	0	10	8
19	9.832	7	19	7
20	5.626	5	13	5

下载: 导出CSV

表 7 场景1某次实验的任务调度方案信息

Table 7. Task scheduling scheme information for one test in scene 1

执行顺序	任务编号		实际开始时间/s		实际结束时间/s
执行顺序	本文算法	对比算法^[21]	本文算法	对比算法^[21]	本文算法	对比算法^[21]
1	3	3	0	0	2	2
2	7	7	2	2	5	5
3	13	13	5	5	7	7
4	2	14	7	7	8	8
5	6	2	8	8	10	9
6	14	6	10	9	11	11
7	16	16	11	11	15	15
8	11	15	15	15	17	17
9	15	11	17	17	19	19
10	9	9	19	19	20	20

下载: 导出CSV

表 8 本文算法与对比算法在场景2中调度效能比值分布

Table 8. Scheduling efficiency ratio distribution of the proposed algorithm and comparison algorithm in scene 2

测试集合编号	调度效能比值/%						离群值个数
测试集合编号	最大值	上四分位数	中位数	下四分位数	最小值	最小离群值	离群值个数
1	100.00	100.00	100.00	95.93	90.37	85.14	4
2	100.00	99.75	98.18	96.06	91.17	88.10	2
3	100.00	98.21	96.87	95.63	91.81	91.40	2
4	100.00	98.06	96.79	95.59	92.11	91.41	2
5	99.69	97.61	96.67	95.53	92.58	91.90	2

下载: 导出CSV

表 9 本文算法和对比算法在场景2中计算耗时

Table 9. Calculation time for the algorithm in this paper and the comparison algorithm in scene 2

测试集编号	本文算法计算耗时/s			对比算法^[21]计算耗时/s
测试集编号	最大值	平均值	最小值	最大值	平均值	最小值
1	0.33	0.08	0.03	1.33	0.46	0.07
2	0.51	0.27	0.16	13.22	3.70	1.11
3	0.76	0.55	0.42	35.98	13.88	4.94
4	1.28	0.71	0.47	99.10	25.83	10.81
5	1.24	0.63	0.50	61.44	35.02	16.52

下载: 导出CSV

表 10 本文算法与对比算法在场景3中调度效能比值分布

Table 10. Scheduling efficiency ratio distribution of the proposed algorithm and comparison algorithm and comparison algorithm in scene 3

测试集编号	调度效能比值/%						离群值个数
测试集编号	最大值	上四分位数	中位数	下四分位数	最小值	最小离群值	离群值个数
1	100.00	100.00	100.00	96.80	92.20	83.22	4
2	100.00	99.98	98.07	95.99	90.58	90.00	1
3	100.00	98.78	97.45	96.03	92.65	90.63	3
4	100.00	98.11	96.81	95.65	93.19	90.04	4
5	99.69	97.33	96.61	95.49	94.71	90.77	9

下载: 导出CSV

表 11 本文算法和对比算法在场景3中计算耗时

Table 11. Calculation time for the proposed algorithm and comparison algorithm in scene 3

测试集编号	本文算法计算耗时/s			对比算法^[21]计算耗时/s
测试集编号	最大值	平均值	最小值	最大值	平均值	最小值
1	0.26	0.06	0.02	32.76	6.89	1.24
2	0.35	0.18	0.12	194.34	67.16	21.13
3	0.69	0.37	0.25	869.38	330.02	105.92
4	0.81	0.53	0.37	2285.13	880.06	333.94
5	0.94	0.65	0.52	5550.48	3027.08	1764.79

下载: 导出CSV

表 12 场景3某次实验的任务请求信息

Table 12. Task request information table for one test in scene 3

任务编号	优先级	最早开始时间/s	最晚结束时间/s	持续时间/s
1	1.86	12.20	17.20	4.10
2	7.37	3.80	5.20	1.00
3	6.90	9.60	17.40	3.70
4	5.78	5.30	11.10	5.70
5	8.37	8.90	18.50	4.30
6	1.03	5.70	9.00	2.00
7	4.10	8.70	18.70	2.50
8	8.03	1.90	14.70	5.90
9	7.58	6.70	17.90	7.40
10	1.23	0.20	12.20	6.80
11	7.06	13.00	16.40	1.40
12	3.12	1.80	13.90	4.70
13	5.02	4.60	15.50	1.20
14	8.58	7.20	11.50	4.20
15	2.99	11.50	19.00	1.60
16	4.61	3.00	12.10	2.80
17	8.45	11.80	19.70	3.70
18	7.42	2.90	17.40	6.00
19	8.30	0.70	10.20	1.10
20	9.56	5.70	18.00	6.40

下载: 导出CSV

表 13 场景3某次实验的任务调度方案信息

Table 13. Task scheduling scheme information for one test in scene 3

执行顺序	任务编号		实际开始时间/s		实际结束时间/s
执行顺序	本文算法	对比算法^[21]	本文算法	对比算法^[21]	本文算法	对比算法^[21]
1	19	19	0.70	0.70	1.80	1.80
2	2	2	3.80	3.80	4.80	4.80
3	16	13	4.90	4.80	7.70	6.00
4	13	20	7.70	6.00	8.90	12.40
5	5	15	9.00	13.00	13.30	14.60
6	11	11	13.30	14.60	14.70	16.00
7	17	17	14.70	16.00	18.40	19.70

下载: 导出CSV

参考文献(21)

[1]	HUIZING A G, BLOEMEN A A F. An efficient scheduling algorithm for a multifunction radar[C]//Proceedings of the International Symposium on Phased Array Systems and Technology. Piscataway: IEEE Press, 1996: 359-364.
[2]	黄佳沁, 钮伟, 郑世友. 基于孔径动态重构的多功能雷达任务调度方法[J]. 指挥控制与仿真, 2021, 43(6): 128-134. HUANG J Q, NIU W, ZHENG S Y. Multifunction radar task scheduling method based on dynamic aperture reconstruction[J]. Command Control & Simulation, 2021, 43(6): 128-134(in Chinese).
[3]	胡子军, 翟海涛. 基于任务驱动的机载相控阵雷达TAS调度算法[J]. 系统工程与电子技术, 2017, 39(3): 536-541. HU Z J, ZHAI H T. Task-driven TAS scheduling algorithm for airborne phased array radar[J]. Systems Engineering and Electronics, 2017, 39(3): 536-541(in Chinese).
[4]	杨善超, 田康生, 刘仁争, 等. 基于价值优化的相控阵雷达任务调度算法[J]. 电子与信息学报, 2020, 42(2): 465-471. YANG S C, TIAN K S, LIU R Z, et al. Scheduling algorithm based on value optimization for phased array radar[J]. Journal of Electronics & Information Technology, 2020, 42(2): 465-471(in Chinese).
[5]	ORMAN A J, POTTS C N, SHAHANI A K, et al. Scheduling for a multifunction phased array radar system[J]. European Journal of Operational Research, 1996, 90(1): 13-25. doi: 10.1016/0377-2217(95)00307-X
[6]	MIRANDA S L C, BAKER C J, WOODBRIDGE K, et al. Phased array radar resource management: a comparison of scheduling algorithms[C]//Proceedings of the IEEE Radar Conference. Piscataway: IEEE Press, 2004: 79-84.
[7]	SHIH C S, GANTI P, GOPALAKRISHNAN S, et al. Synthesizing task periods for dwells in multi-function phased array radars[C]// Proceedings of the IEEE Radar Conference. Piscataway: IEEE Press, 2004: 145-150.
[8]	SHIH C S, GOPALAKRISHNAN S, GANTI P, et al. Scheduling real-time dwells using tasks with synthetic periods[C]//Proceedings of the 24th IEEE Real-Time Systems Symposium. Piscataway: IEEE Press, 2003: 210-219.
[9]	GOPALAKRISHNAN S, CACCAMO M, SHIH C S, et al. Finite-horizon scheduling of radar dwells with online template construction[J]. Real-time Systems, 2006, 33(1): 47-75.
[10]	MOSLEHI G, MAHNAM M. A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search[J]. International Journal of Production Economics, 2011, 129(1): 14-22. doi: 10.1016/j.ijpe.2010.08.004
[11]	张浩为, 谢军伟, 师俊朋, 等. 饱和时序下防空相控阵雷达动态优先级调度算法[J]. 北京亚洲成人在线一二三四五六区学报, 2016, 42(12): 2722-2729. ZHANG H W, XIE J W, SHI J P, et al. Dynamic priority scheduling algorithm for air defense phased array radar in overload situations[J]. Journal of Beijing University of Aeronautics and Astronautics, 2016, 42(12): 2722-2729(in Chinese).
[12]	RAHMATI S H A, ZANDIEH M. A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology, 2012, 58(9): 1115-1129.
[13]	陶孙杰, 宋竹. 一种测控数传一体化站网资源调度算法[J]. 电讯技术, 2018, 58(7): 760-767. TAO S J, SONG Z. A ground-station resource scheduling algorithm based on integration of TT&C and data transmission[J]. Telecommunication Engineering, 2018, 58(7): 760-767(in Chinese).
[14]	IZQUIERDO-FUENTE A, CASAR-CORREDERA J R. Approach to multifunction radar scheduling simulation[C]//Proceedings of the IEEE National Telesystems Conference. Piscataway: IEEE Press, 1994: 67-70.
[15]	MIR H S, WILKINSON J D. Task scheduling algorithm for an air and missile defense radar[C]//Proceedings of the IEEE Radar Conference. Piscataway: IEEE Press, 2008: 1629-1634.
[16]	HUIZING A G, BLOEMEN A A F. A high-level multifunction radar simulation for studying the performance of multisensor data fusion systems[C]//Proceedings of the SPIE Conference on Signal Processing, Sensor Fusion, and Target Recognition VII. Bellingham: SPIE, 1998: 129-138.
[17]	YING C L, WANG Y, HE J X. Study on time window of track tasks in multifunction phased array radar tasks scheduling[C]//Proceedings of IET International Radar Conference. London: IET, 2009: 1-4.
[18]	JANG D S, CHOI H L, ROH J E. A time-window-based task scheduling approach for multi-function phased array radars[C]//Proceedings of the International Conference on Control, Automation and Systems. Piscataway: IEEE Press, 2011: 1250-1255.
[19]	SPASOJEVIC Z, DEDEO S, JENSEN R. Dwell scheduling algorithms for phased array antenna[J]. IEEE Transactions on Aerospace and Electronic Systems, 2013, 49(1): 42-54. doi: 10.1109/TAES.2013.6404090
[20]	MIR H S, GUITOUNI A. Variable dwell time task scheduling for multifunction radar[J]. IEEE Transactions on Automation Science and Engineering, 2014, 11(2): 463-472. doi: 10.1109/TASE.2013.2285014
[21]	MCGUFFIN B. Priority scheduling for multi-function apertures with hard- and soft-time constraints[C]//Proceedings of the IEEE Aerospace Conference. Piscataway: IEEE Press, 2021: 1-11.