基于任务合成机制的多星调度问题

doi:10.3969/j.issn.1001-506X.2021.01.21

摘要/Abstract

摘要：

传统模式下,卫星采取单任务观测方式,该种方式下任务的成像精度高但任务成像数量少且资源使用率极低。因此,在单任务观测方式的基础上设计了一种多任务合成机制(multi-task merging mechanism, MTMM),在保证用户最低成像要求的情况下对任务合成。首先,基于合成任务集,建立多星调度模型。然后，针对模型提出了基于任务合成的改进蚁群优化(improved ant colony optimization based on task merging, IACO-TM)算法,在算法中设计了自适应蚁窗策略、强制扰动机制以及算法参数动态调节策略,对蚂蚁搜索空间进行有效裁剪,避免算法陷入局部最优的同时提高算法的收敛速度。最后,通过大量仿真实验与不考虑任务合成的改进蚁群优化(improved ant colony optimization, IACO)算法和基于任务合成的传统蚁群优化(traditional ant colony optimization based on task merging, TACO-TM)算法对比,验证了所提MTMM和IACO-TM的有效性。

关键词: 多星调度, 任务合成, 蚁群算法, 自适应

Abstract:

In the traditional pattern, the satellite adopts the single task observation mode, in which the imaging accuracy of the task is high. However, the imaging quantity of the task is small and the utilization rate of the resource is extremely low. Therefore, a multi-task merging mechanism (MTMM) based on the single task observation mode is designed, which adopts the way of task merging in the case of ensuring the minimum imaging requirements of users. Firstly, on the basis of the merging task set, a multi-satellite scheduling model is established, and then an algorithm of improved ant colony optimization based on task merging (IACO-TM) is proposed for the model. In the algorithm, an adaptive ant window strategy, a forced disturbance mechanism and a parameters dynamic adjustment strategy of the algorithm are designed, so as to cut the ant search space effectively, avoid the algorithm falling into the local optimum and improve the convergence speed of the algorithm at the same time. Finally, a large number of simulation experiments are provided to verify the effectiveness of MTMM and IACO-TM, comparing with the algorithm of improved ant colony optimization (IACO) and the algorithm of traditional ant colony optimization based on task merging (TACO-TM).

Key words: multi-satellite scheduling, task merging, ant colony algorithm, self-adaption

中图分类号:

任送莲, 孙海权, 靳鹏. 基于任务合成机制的多星调度问题[J]. 系统工程与电子技术, 2021, 43(1): 171-180.

Songlian REN, Haiquan SUN, Peng JIN. Multi-satellite scheduling problem based on task merging mechanism[J]. Systems Engineering and Electronics, 2021, 43(1): 171-180.

图/表 11

图1

图2

图3

图4

图5

表1

图6

表2

图7

图8

图9

参考文献 32

1	WALTON J . Models for the management of satellite-based sensors[J]. Massachusetts Institute of Technology, 1993, 15 (5): 23- 30.
2	WANG P , GAO P , TAN Y J . A model, a heuristic and a decision support system to solve the earth observing satellites fleet scheduling problem[J]. Computers & Industrial Engineering, 2011, 61 (2): 322- 335.
3	TANGPATTANAKUL P , JOZEFOWIEZ N , LOPEZ P . A multi-objective local search heuristic for scheduling earth observations taken by an agile satellite[J]. European Journal of Opera-tional Research, 2015, 245 (2): 542- 554.
4	CHO D H , KIM J H , CHOI H L , et al. Optimization-Based schedu-ling method for agile earth-observing satellite constellation[J]. Journal of Aerospace Information Systems, 2018, 15 (11): 611- 626.
5	BIANCHESSI N , CORDEAU J F , DESROSIERS J , et al. A heuristic for the multi-satellite, multi-orbit and multi-user mana-gement of earth observation satellites[J]. European Journal of Operational Research, 2007, 177 (2): 750- 762.
6	SONG Y J , HUANG D J , ZHOU Z Y , et al. An emergency task autonomous planning method of agile imaging satellite[J]. EURASIP Journal on Image & Video Processing, 2018, 1 (29): 367- 370.
7	WU G H , LIU J , MA M H , et al. A two-phase scheduling method with the consideration of task clustering for earth observing satellites[J]. Computers & Operations Research, 2013, 40 (7): 1884- 1894.
8	LIU X L , BAI B C , CHEN Y W , et al. Multi satellites scheduling algorithm based on task merging mechanism[J]. Applied Mathematics & Computation, 2014, 230, 687- 700.
9	WANG J J , ZHU X M , YANG L Y , et al. Towards dynamic real-time scheduling for multiple earth observation satellites[J]. Journal of Computer & System Sciences, 2015, 81 (1): 110- 124.
10	邱涤珊, 王建江, 吴朝波, 等. 基于任务合成的对地观测卫星应急调度方法[J]. 系统工程与电子技术, 2013, 35 (7): 1430- 1437.
	QIU D S , WANG J J , WU C B , et al. Emergency scheduling method of earth observation satellites based on task merging[J]. Systems Engineering and Electronics, 2013, 35 (7): 1430- 1437.
11	SUN H Q , XIA W , HU X X , et al. Earth observation satellite scheduling for emergency tasks[J]. Journal of Systems Engineering and Electronics, 2019, 30 (5): 931- 945.
12	WU G H , MA M H , ZHU J H , et al. Multi-satellite observation integrated scheduling method oriented to emergency tasks and common tasks[J]. Journal of Systems Engineering and Electronics, 2012, 23 (5): 723- 733.
13	WANG J J , ZHU X M , QIU D S , et al. Dynamic scheduling for emergency tasks on distributed imaging satellites with task merging[J]. IEEE Trans.on Parallel & Distributed Systems, 2014, 25 (9): 2275- 2285.
14	BATAILLE N , BLUMSTEIN D , BENSANA E , et al. Exact and approximate methods for the daily management of an earth observation satellite[J]. Rairo Operations Research, 2007, 41 (4): 381- 398.
15	HU X X , ZHU W M , AN B , et al. A branch and price algorithm for EOS constellation imaging and downloading integrated scheduling problem[J]. Computers & Operations Research, 2019, 104 (1): 74- 89.
16	WU G H , WANG H L , PEDRYCZ W , et al. Satellite observation scheduling with a novel adaptive simulated annealing algorithm and a dynamic task clustering strategy[J]. Computers & Industrial Engineering, 2017, 113 (1): 576- 588.
17	ZHU W M , HU X X , XIA W , et al. A two-phase genetic annealing method for integrated earth observation satellite schedu-ling problems[J]. Soft Computing, 2019, 23 (1): 181- 196.
18	VASQUEZ M , HAO J K . A "logic-constrained" knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite[J]. Computational Optimization & Applications, 2001, 20 (2): 137- 157.
19	BARKAOUI M , BERGER J . A new hybrid genetic algorithm for the collection scheduling problem for a satellite constellation[J]. Journal of the Operational Research Society, 2019, 71 (9): 1390- 1410.
20	DORIGO, M. Optimization, learning and natural algorithms[D]. Italy: Politecnico di Milano, 1992.
21	DORIGO M. LUCA M . The Ant-Q algorithm applied to the nuclear reload problem[J]. Annals of Nuclear Energy, 2002, 29 (12): 1455- 1470.
22	THOMAS S , HOOS H H . MAX-MIN ant system[J]. Future Generation Computer Systems, 2000, 16 (8): 889- 914.
23	吴庆洪, 张纪会, 徐心和. 具有变异特征的蚁群算法[J]. 计算机研究与发展, 1999, 36 (10): 1240- 1245.
	WU Q H , ZHANG J H , XU X H . Ant colony algorithm with mutation feature[J]. Computer Research and Development, 1999, 36 (10): 1240- 1245.
24	LUO K P . A hybrid binary artificial bee colony algorithm for the satellite photograph scheduling problem[J]. Engineering Optimization, 2020, 52 (8): 1421- 1440.
25	陈崚, 沈洁, 秦玲, 等. 基于分布均匀度的自适应蚁群算法[J]. 软件学报, 2003, 14 (8): 39- 47.
	CHEN L , SHEN J , QING L , et al. Adaptive ant colony algorithm based on equilibrium of distribution[J]. Journal of Software, 2003, 14 (8): 39- 47.
26	陈崚, 秦玲, 陈宏建, 等. 具有感觉和知觉特征的蚁群算法[J]. 系统仿真学报, 2003, 15 (10): 1418- 1425.
	CHEN L , QING L , CHEN J H , et al. Ant colony algorithm with characteristics of sensation and consciousness[J]. Journal of System Simulation, 2003, 15 (10): 1418- 1425.
27	CORDEAU J F , LAPORTE G . Maximizing the value of an earth observation satellite orbit[J]. Journal of the Operational Research Society, 2005, 56 (8): 962- 968.
28	LONG J, CHEN S L, LI C, et al. A task clustering method for multi agile satellite based on clique partition[C]//Proc.of the International Conference on Intelligent Computation Technology & Automation, 2018: 332-336.
29	GABREL V , MOULET A , MURAT C , et al. A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts[J]. Annals of Operations Research, 1997, 69 (1): 115- 134.
30	XU R , CHEN H , LIANG X , et al. Priority-based constructive algorithms for scheduling agile earth observation satellites with total priority maximization[J]. Expert Systems with Application, 2016, 51 (6): 195- 206.
31	CHEN X Y , REINELT G , DAI G M , et al. A mixed integer linear programming model for multi-satellite scheduling[J]. European Journal of Operational Research, 2019, 275 (2): 694- 707.
32	NIU X N , TANG H , WU L X . Satellite scheduling of large areal tasks for rapid response to natural disaster using a multi-objective genetic algorithm[J]. International Journal of Disaster Risk Reduction, 2018, 28 (1): 813- 825.

任务编号	卫星编号	开始时间窗	结束时间窗
afyf	GAOFEN_1_39150	2019/7/24 0:44:43	2019/7/24 0:45:34
mcat	GAOFEN_1_39150	2019/7/24 3:42:09	2019/7/24 3:42:58
xefp	YAOGAN_11_37165	2019/7/24 6:54:14	2019/7/24 6:55:03
⋮	⋮	⋮	⋮
xefp	YAOGAN_11_37165	2019/7/24 17:50:16	2019/7/24 17:51:05
kqsn	YAOGAN_15_38354	2019/7/24 17:50:52	2019/7/24 17:51:42
tmru	YAOGAN_15_38354	2019/7/24 22:22:37	2019/7/24 22:23:29

算例	规模	IACO-TM			IACO			TACO-TM
算例	规模	最佳收益	观测数量	时间/s	最佳收益	观测数量	时间/s	最佳收益	观测数量	时间/s
C1	100	533.67	43	2	555	45	1.67	538	44	3.33
C2		793.33	54	2.67	647.3	41	1.67	773	52	3.33
C3		719	58	3.33	569.67	45	1.33	694.33	53	3
C4	200	1 087.5	90	9	771	61	5.34	973.5	81	8.5
C5		1 050	87	7	766.33	61	5.34	986.5	82	8.5
C6		1 053	88	9	824.67	67	5.67	947.33	79	7
C7	400	1 009.67	83	23	998	80	26.33	892.67	73	22.34
C8		1 420.3	116	38.33	1 048	82	32	1 298.5	107	32
C9		1 354.8	112	30.2	1 009.5	80	28.75	1 188	98	24

[1]	常浩伟, 庞春雷, 郭泽辉, 张良, 吕敏敏, 张闯. 基于自适应免疫算法的欺骗信号检测方法[J]. 系统工程与电子技术, 2022, 44(8): 2419-2426.
[2]	熊元燚, 谢文冲. 基于空时约束的自适应迭代单脉冲估计方法[J]. 系统工程与电子技术, 2022, 44(8): 2506-2514.
[3]	方志耕, 夏悦馨, 张靖如, 熊仪, 陈静邑. 基于Agent的体系过程A-GERT网络“刺激-反应”学习模型[J]. 系统工程与电子技术, 2022, 44(8): 2540-2553.
[4]	王帅, 向建军, 彭芳, 唐书娟, 李志军. 基于新最速下降算法的自适应波束形成[J]. 系统工程与电子技术, 2022, 44(7): 2104-2111.
[5]	闫世瑛, 颜克斐, 方伟, 陆恒杨. 基于差分进化邻域自适应的大规模多目标算法[J]. 系统工程与电子技术, 2022, 44(7): 2112-2124.
[6]	王冠, 茹海忠, 张大力, 马广程, 夏红伟. 弹性高超声速飞行器智能控制系统设计[J]. 系统工程与电子技术, 2022, 44(7): 2276-2285.
[7]	高升, 马广富, 郭延宁. 基于自适应未知输入观测器的多故障快速重构[J]. 系统工程与电子技术, 2022, 44(7): 2364-2373.
[8]	魏法, 杨明磊, 何小静, 周鼎森, 陈伯孝. 基于改进粒子群算法的平面阵同时多波束赋形方法[J]. 系统工程与电子技术, 2022, 44(6): 1789-1797.
[9]	陈江美, 张文德. 基于灰关联分析和时空偏好特征的兴趣点推荐算法[J]. 系统工程与电子技术, 2022, 44(6): 1934-1941.
[10]	董一平, 刘宁, 苏中, 王靖骁, 白宏阳. 基于AEKF的高速自旋飞行体组合导航方法[J]. 系统工程与电子技术, 2022, 44(6): 1977-1983.
[11]	王帅, 向建军, 彭芳, 唐书娟. 基于新最速下降法的目标跟踪算法[J]. 系统工程与电子技术, 2022, 44(5): 1512-1519.
[12]	罗世彬, 李晓栋, 王忠森, 徐骋. 并联式运载器上升段广义超螺旋有限时间控制[J]. 系统工程与电子技术, 2022, 44(5): 1626-1635.
[13]	李海, 程伟杰, 谢瑞杰. 基于同伦稀疏STAP的低空风切变风速估计[J]. 系统工程与电子技术, 2022, 44(4): 1174-1181.
[14]	李园, 史宪铭, 李亚娟, 赵美. 基于Adaboost的作战目标属性判定方法[J]. 系统工程与电子技术, 2022, 44(4): 1256-1262.
[15]	安通, 王鹏, 王建华, 汤国建, 潘玉龙, 陈海山. 弹性高超声速飞行器动态面制导控制一体化设计方法[J]. 系统工程与电子技术, 2022, 44(3): 956-966.