面向预警场景的大规模星座协同调度标准建模与求解方法

doi:10.7527/S1000-6893.2024.30181

Abstract

Abstract:

Large-scale constellation coordination scheduling is characterized by a large number of remote satellite nodes， large task demands， complex resource utilization constraints， and high requirements for modeling and solving collaborative scheduling between multiple nodes. This paper proposes a top-level framework for phased unified modeling and solving， which includes “task pre-processing， unified modeling， optimization solving， on-orbit instruction generation”. Under the top-level framework， a multi node real-time Collaborative Scheduling Algorithm based on the Improved Contract Network （CSA-ICNP） is proposed for space-based early warning application scenarios， which utilizes fuzzy optimization combined with the local search strategy to improve the overall optimization ability of the algorithm. The correctness and effectiveness of the proposed algorithm are verified by conducting a large number of simulation experiments. Comparison of the method proposed with Random Search algorithm（RS）‍‍‍‍，Greedy Search algorithm（GS）‍‍‍，Task Allocation Algorithm based on Conflict Degree （TAACD）‍‍‍，Minimum Load First Allocation algorithm （MLFA） and Distributed Satellite Resource Scheduling based on Improved Contract Network Protocol （DSRS-ICNP） shows that each experimental case achieves the optimal objective function value， with an average improvement of 42.13%， 41.51%， 37.93%， 37.53% and 18.57%， respectively.

Key words: large-scale constellation, collaborative scheduling, unified modeling, standardized optimization solution, space-based warning, improved contract net protocol

CLC Number:

Zongling LI, Teng LONG, Baojun ZHAO, Tianyu WANG, Guohua WU. Standard modeling and solving methods for large-scale constellation collaborative scheduling for early warning scenarios[J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(22): 330181.

Figures/Tables 10

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Table 1

Table 2

Table 3

Table 4

Comparison of solution results of algorithms under different test cases

目标数量	卫星规模	RSA			GSA			TAACD			MLFA			DSRS-ICNP			CSA-ICNP
目标数量	卫星规模	Avg	Imp/%	Time/s	Avg	Imp/%	Time/s	Avg	Imp/%	Time/s	Avg	Imp/%	Time/s	Avg	Imp/%	Time/s	Avg	Imp/%	Time/s
Imp Avg			42.13			41.51			37.93			37.53			18.57
1	30	0.461	47.6	0.13	0.460	47.5	0.13	0.451	46.5	0.16	0.421	42.7	0.16	0.332	27.4	0.22	0.241	0	0.22
1	45	0.447	44.3	0.19	0.442	43.7	0.19	0.450	44.6	0.22	0.410	39.2	0.22	0.352	29.2	0.31	0.249	0	0.30
1	60	0.392	41.7	0.26	0.391	41.5	0.26	0.401	43.1	0.31	0.376	39.2	0.31	0.330	30.9	0.42	0.228	0	0.41
1	75	0.421	42.2	0.33	0.412	41.1	0.33	0.421	42.3	0.37	0.393	38.2	0.37	0.358	32.2	0.50	0.243	0	0.50
1	90	0.443	42.4	0.36	0.432	40.9	0.36	0.436	41.5	0.41	0.396	35.7	0.41	0.384	33.7	0.55	0.255	0	0.55
2	30	0.472	60.3	0.32	0.466	59.7	0.31	0.435	56.8	0.38	0.409	54.1	0.38	0.306	38.6	0.89	0.188	0	0.83
2	45	0.456	44.8	0.48	0.463	45.6	0.48	0.443	43.1	0.55	0.450	44.0	0.55	0.300	16.1	1.13	0.252	0	1.07
2	60	0.478	45.8	0.51	0.476	45.5	0.51	0.454	42.9	0.58	0.443	41.5	0.58	0.346	25.0	1.43	0.259	0	1.36
2	75	0.443	43.0	0.71	0.439	42.5	0.71	0.422	40.2	0.79	0.416	39.4	0.79	0.336	24.9	2.11	0.252	0	2.01
2	90	0.434	47.0	0.85	0.432	46.7	0.85	0.409	43.7	0.97	0.398	42.1	0.96	0.340	32.4	2.67	0.230	0	2.52
3	30	0.670	45.4	0.42	0.660	44.5	0.43	0.636	42.5	0.52	0.635	42.4	0.52	0.400	8.4	1.29	0.366	0	1.24
3	45	0.609	43.8	0.71	0.604	43.4	0.71	0.584	41.4	0.82	0.577	40.7	0.82	0.396	13.5	1.84	0.342	0	1.75
3	60	0.602	46.1	0.95	0.597	45.6	0.95	0.554	41.4	1.09	0.554	41.5	1.09	0.407	20.3	2.58	0.325	0	2.43
3	75	0.558	44.4	1.20	0.550	43.6	1.20	0.516	39.8	1.36	0.516	39.9	1.36	0.396	21.7	3.51	0.311	0	3.29
3	90	0.591	42.6	1.43	0.583	41.8	1.43	0.545	37.7	1.61	0.542	37.4	1.60	0.438	22.5	4.12	0.339	0	3.85
4	30	0.747	37.5	0.59	0.743	37.2	0.59	0.688	32.2	0.73	0.698	33.1	0.74	0.495	5.7	2.17	0.467	0	2.16
4	45	0.722	33.4	0.95	0.722	33.4	0.97	0.681	29.4	1.12	0.677	29.0	1.12	0.528	8.9	2.60	0.481	0	2.54
4	60	0.676	46.4	1.15	0.671	46.0	1.15	0.607	40.3	1.37	0.613	40.9	1.37	0.435	16.7	3.68	0.362	0	3.47
4	75	0.642	46.4	1.64	0.632	45.5	1.64	0.567	39.3	1.94	0.577	40.4	1.94	0.430	20.0	5.10	0.344	0	4.65
4	90	0.644	43.9	1.92	0.638	43.4	1.91	0.571	36.8	2.22	0.580	37.7	2.24	0.461	21.5	6.42	0.361	0	5.90
5	30	0.754	29.7	0.78	0.753	29.6	0.80	0.704	24.7	1.02	0.710	25.3	1.01	0.552	4.0	3.00	0.530	0	2.90
5	45	0.748	38.3	1.15	0.744	37.9	1.15	0.684	32.5	1.45	0.693	33.4	1.46	0.504	8.5	4.10	0.462	0	4.04
5	60	0.720	41.6	1.61	0.715	41.2	1.63	0.651	35.4	2.01	0.668	37.0	1.98	0.485	13.3	5.37	0.421	0	5.09
5	75	0.698	44.2	2.13	0.697	44.2	2.13	0.629	38.1	2.47	0.636	38.8	2.48	0.466	16.5	6.98	0.389	0	6.45
5	90	0.691	41.8	2.47	0.689	41.6	2.46	0.621	35.2	2.84	0.633	36.5	2.86	0.479	16.1	8.59	0.402	0	7.88
6	30	0.799	23.1	1.04	0.776	20.8	1.08	0.744	17.4	1.30	0.764	19.6	1.29	0.640	3.9	4.38	0.615	0	4.26
6	45	0.834	25.3	1.41	0.815	23.6	1.47	0.777	19.8	1.60	0.796	21.8	1.60	0.648	3.8	4.53	0.623	0	4.42
6	60	0.716	42.9	1.92	0.699	41.6	1.92	0.640	36.2	2.27	0.655	37.6	2.30	0.458	10.8	7.00	0.409	0	6.77
6	75	0.713	42.7	2.58	0.698	41.4	2.65	0.631	35.2	3.15	0.651	37.2	3.17	0.473	13.6	8.19	0.409	0	7.67
6	90	0.723	45.3	3.02	0.707	44.0	3.01	0.634	37.6	3.64	0.654	39.5	3.68	0.476	16.9	9.83	0.396	0	9.22

Table 4

Fig. 6

References 38

1	李宗凌，宋桂萍，汪路元，等. 巨型星座高效管理与智能应用关键技术研究［J］. 航天器工程， 2023， 32（1）： 1-7.
	LI Z L， SONG G P， WANG L Y， et al. Research on Key Technologies of High efficiency management and intelligent application for mega-constellation［J］. Spacecraft Engineering， 2023， 32（1）： 1-7 （in Chinese）.
2	王朝辉，徐瑞，李朝玉，等. 加权负载均衡合同网大规模星座任务分配方法［J］. 航天控制， 2023， 41（4）： 59-66.
	WANG Z H， XU R， LI C Y， et al. Large-scale constellation task allocation method through weighted load balancing contract network［J］. Aerospace Control， 2023， 41（4）： 59-66 （in Chinese）.
3	张逢贵，李舒薇，杨学海，等. 星地系统中的站网资源优化调度综述与展望［J］. 系统仿真技术， 2023， 19（3）： 283-292.
	ZHANG F G， LI S W， YANG X H， et al. Optimal scheduling of ground station network resources in satellite-ground systems： Overview and prospects［J］. System Simulation Technology， 2023， 19（3）： 283-292 （in Chinese）.
4	TARTAKOVSKY A G， BROWN J. Adaptive spatial-temporal filtering methods for clutter removal and target tracking［J］. IEEE Transactions on Aerospace and Electronic Systems， 2008， 44（4）： 1522-1537.
5	HERNANDEZ M L， FARINA A， RISTIC B. PCRLB for tracking in cluttered environments： Measurement sequence conditioning approach［J］. IEEE Transactions on Aerospace and Electronic Systems， 2006， 42（2）： 680-704.
6	WU G H， LUO Q Z， DU X， et al. Ensemble of metaheuristic and exact algorithm based on the divide-and-conquer framework for multisatellite observation scheduling［J］. IEEE Transactions on Aerospace and Electronic Systems， 2022， 58（5）： 4396-4408.
7	GOOLEY T D. Automating the satellite range scheduling process［D］. Ohio： Air Force Institute of Technology， 1993：10-17.
8	GOOLEY T D， BORSI J J， MOORE J T. Automating air force satellite control network （AFSCN） scheduling［J］. Mathematical and Computer Modelling， 1996， 24（2）： 91-101.
9	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： 74-89.
10	康宁，武小悦. 基于拉格朗日松弛的航天测控调度上界求解算法［J］. 国防科技大学学报， 2011， 33（3）： 38-43.
	KANG N， WU X Y. TT & C scheduling upper bound solution algorithm based on Lagrangian relaxation［J］. Journal of National University of Defense Technology， 2011， 33（3）： 38-43 （in Chinese）.
11	刘建平，李晶，张天骄. 航天测控网调度的混合构造启发式算法［J］. 系统工程与电子技术， 2015， 37（7）： 1569-1574.
	LIU J P， LI J， ZHANG T J. Hybrid constructive heuristics of space measurement and control network scheduling problem［J］. Systems Engineering and Electronics， 2015， 37（7）： 1569-1574 （in Chinese）.
12	WU J， YAO F， SONG Y J， et al. Frequent pattern-based parallel search approach for time-dependent agile earth observation satellite scheduling［J］. Information Sciences， 2023， 636： 118924.
13	VAZQUEZ R， PEREA F， GALÁN V J. Resolution of an Antenna-Satellite assignment problem by means of Integer Linear Programming［J］. Aerospace Science and Technology， 2014， 39： 567-574.
14	邱涤珊，张利宁，祝江汉，等. 多星任务规划中的FFFS-DTMB与ADTPC-DTMB算法［J］. 航空学报， 2009， 30（11）： 2178-2184.
	QIU D S， ZHANG L N， ZHU J H， et al. FFFS-DTMB and ADTPC-DTMB algorithmin multi-satellites mission planning［J］. Acta Aeronautica et Astronautica Sinica， 2009， 30（11）： 2178-2184 （in Chinese）.
15	辛立强，张超，赵灵芝，等. 面向复杂关联测控需求的冲突规避调度算法［J］. 系统工程与电子技术， 2022， 44（5）： 1581-1588.
	XIN L Q， ZHANG C， ZHAO L Z， et al. Conflict avoidance scheduling algorithm for complex associated TT & C requirements［J］. Systems Engineering and Electronics， 2022， 44（5）： 1581-1588 （in Chinese）.
16	MANSOUR M A A， DESSOUKY M M. A genetic algorithm approach for solving the daily photograph selection problem of the SPOT5 satellite［J］. Computers & Industrial Engineering， 2010， 58（3）： 509-520.
17	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.
18	ZHANG Z J， ZHANG N， FENG Z R. Multi-satellite control resource scheduling based on ant colony optimization［J］. Expert Systems with Applications， 2014， 41（6）： 2816-2823.
19	SARKHEYLI A， BAGHERI A， GHORBANI-VAGHEI B， et al. Using an effective tabu search in interactive resources scheduling problem for LEO satellites missions［J］. Aerospace Science and Technology， 2013， 29（1）： 287-295.
20	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： 576-588.
21	宋彦杰，王沛，张忠山，等. 面向多星任务规划问题的改进遗传算法［J］. 控制理论与应用， 2019， 36（9）： 1391-1397.
	SONG Y J， WANG P， ZHANG Z S， et al. An improved genetic algorithm for multi-satellite mission planning problem［J］. Control Theory & Applications， 2019， 36（9）： 1391-1397 （in Chinese）.
22	薛乃阳，丁丹，王红敏，等. 基于改进遗传算法的多类测控资源调度方法［J］. 系统工程与电子技术， 2021， 43（9）： 2535-2543.
	XUE N Y， DING D， WANG H M， et al. Multi-type TT & C resource scheduling method based on improved genetic algorithm［J］. Systems Engineering and Electronics， 2021， 43（9）： 2535-2543 （in Chinese）.
23	伍国华，王天宇. 基于自适应模拟退火的大规模星座测控资源调度算法［J］. 航空学报， 2023， 44（12）： 327759.
	WU G H， WANG T Y. Large-scale constellation TT & C resource scheduling algorithm based on adaptive simulated annealing［J］. Acta Aeronautica et Astronautica Sinica， 2023， 44（12）： 327759 （in Chinese）.
24	谢平，杜永浩，姚锋，等. 敏捷成像卫星自主调度技术综述［J］. 宇航学报， 2019， 40（2）： 127-138.
	XIE P， DU Y H， YAO F， et al. Literature review for autonomous scheduling technology of agile earth observation satellites［J］. Journal of Astronautics， 2019， 40（2）： 127-138 （in Chinese）.
25	杜永浩，邢立宁，姚锋，等.航天器任务调度模型、算法与通用求解技术综述［J］. 自动化学报， 2021， 47（12）： 2715-2741.
	DU Y H， XING L N， YAO F. Survey on models， algorithms and general techniques for spacecraft mission scheduling［J］. Acta Automatica Sinica， 2021， 47（12）： 2715-2741. （in Chinese）.
26	刘阳，周笛，盛敏，等. 面向巨型星座系统的多地面站协同测控技术［J］. 天地一体化信息网络， 2023， 4（01）： 2-11.
	LIU Y， ZHOU D， SHEN M， et al. Multi-ground station collaborative measurement and control technology for giant constellation system［J］. Space-Integrated-Ground Information Networks， 2023， 4（01）： 2-11 （in Chinese）.
27	LEMAı̂TRE M， VERFAILLIE G， JOUHAUD F， et al. Selecting and scheduling observations of agile satellites［J］. Aerospace Science and Technology， 2002， 6（5）： 367-381.
28	KODHELI O， LAGUNAS E， MATURO N， et al. Satellite communications in the new space era： A survey and future challenges［J］. IEEE Communications Surveys & Tutorials， 2021， 23（1）： 70-109.
29	DEL PORTILLO I， CAMERON B G， CRAWLEY E F. A technical comparison of three low earth orbit satellite constellation systems to provide global broadband［J］. Acta Astronautica， 2019， 159： 123-135.
30	WANG L， JIANG C X， KUANG L L， et al. Mission scheduling in space network with antenna dynamic setup times［J］. IEEE Transactions on Aerospace and Electronic Systems， 2019， 55（1）： 31-45.
31	贺仁杰，高鹏，白保存，等. 成像卫星任务规划模型、算法及其应用［J］. 系统工程理论与实践， 2011， 31（3）： 411-422.
	HE R J， GAO P， BAI B C， et al. Models， algorithm and applications to the mission planning system of imaging satellites［J］. Systems Engineering Theory and Practice， 2011， 31（3）： 411-422 （in Chinese）.
32	丁冬，何兵，余炜，等. 美国天基导弹预警系统发展及效能仿真研究［J］. 中国电子科学研究院学报， 2022， 17（11）： 1102-1106.
	DING D， HE B， YU W， et al. Development and effectiveness simulation of American space-based missile early warning system［J］. Journal of China Academy of Electronics and Information Technology， 2022， 17（11）： 1102-1106 （in Chinese）.
33	LIU B J， DENG M， WU G H， et al. Bottom-up mechanism and improved contract net protocol for dynamic task planning of heterogeneous earth observation resources［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2022， 52（10）： 6183-6196.
34	WOSNIACK M E， RAPOSO E P， VISWANATHAN G M， et al. A parallel algorithm for random searches［J］. Computer Physics Communications， 2015， 196： 390-397.
35	HIEN V Q， DAO T C， BINH H T T. A greedy search based evolutionary algorithm for electric vehicle routing problem［J］. Applied Intelligence， 2023， 53（3）： 2908-2922.
36	李夏苗，陈新江，伍国华，等. 考虑断点续传的中继卫星调度模型及启发式算法［J］. 航空学报， 2019， 40（11）： 323233.
	LI X M， CHEN X J， WU G H， et al. Scheduling model and heuristic algorithm for tracking and data relay satellite considering breakpoint transmission［J］. Acta Aeronautica et Astronautica Sinica， 2019， 40（11）： 323233 （in Chinese）.
37	李夏苗，廖文昆，伍国华，等. 基于两阶段迭代优化的空天观测资源协同任务规划方法［J］. 控制与决策， 2021， 36（5）： 1147-1156.
	LI X M， LIAO W K， WU G H， et al. A two-stage iterative optimazation method for the coordinated task planning of space and air observation resources［J］. Control and Decision， 2021， 36（5）： 1147-1156 （in Chinese）.
38	靳鹏，李康. 基于改进合同网协议的分布式卫星资源调度［J］. 系统工程与电子技术， 2022， 44（10）： 3164-3173.
	JIN P， LI K. Distributed satellite resource scheduling based on improved contract network protocol［J］. Systems Engineering and Electronics， 2022， 44（10）： 3164-3173 （in Chinese）.

参数类型		取值范围
轨道半长轴/km	LEO MEO HEO	（7 178，7 878）（8 378，26 378）（31 378，41 378）
偏心率		0
倾角/（°）		（0，180）
近地点幅角/（°）		（0，360）
升交点赤经/（°）		（0，360）
平近点角/（°）		0

卫星数量	高/中/低轨卫星数量	高/中/低轨卫星传感器视场角
30	1/3/26	15/20/30
45	2/4/39	15/20/30
60	3/6/51	15/20/30
75	4/8/63	15/20/30
90	5/9/76	15/20/30

Standard modeling and solving methods for large-scale constellation collaborative scheduling for early warning scenarios

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 38

Related Articles 1

Recommended Articles

Metrics

Comments