基于改进合同网协议的分布式卫星资源调度

doi:10.12305/j.issn.1001-506X.2022.10.20

摘要/Abstract

摘要：

随着卫星和任务的增加以及卫星智能化的提升, 传统的集中式任务规划已无法满足规划需求。本文研究分布式卫星任务规划问题, 首先, 针对分布式任务规划中全局和局部目标的不一致性建立双层规划数学模型, 最大化观测收益、最小化任务观测完成时间、最优化负载均衡。其次, 提出可解约循环合同网, 设计包含全任务投标策略和二次中标策略的并发机制以减少协商次数, 建立多属性评标机制完善评标过程。设计基于自适应退火的可解约循环合同网算法求解分布式卫星任务规划问题。最后, 通过数值实验结果证明所提算法求解问题的有效性和合理性。

关键词: 分布式卫星, 任务规划, 任务协作, 合同网协议

Abstract:

With the increase of satellites and missions and the improvement of satellite intelligence, traditional centralized mission planning can no longer meet the requirements of planning. In this paper, the problem of distributed satellite mission planning is studied. Firstly, a two-level programming mathematical model is established for the inconsistency between global and local objectives in distributed mission planning to maximize observation benefits, minimize mission observation completion time, and optimize load balancing. Secondly, the paper proposes a decomposable circular contract network, designs a concurrent mechanism including full task bidding strategy and second bid winning strategy to reduce the times of negotiation, and establishes a multi-attribute bid evaluation mechanism to improve the bid evaluation process. An algorithm based on adaptive annealing is designed to solve the distributed satellite mission planning problem. Finally, numerical experiment results show the effectiveness and rationality of the proposed algorithm.

Key words: distributed satellite, mission planning, task collaboration, contract network protocol

中图分类号:

靳鹏, 李康. 基于改进合同网协议的分布式卫星资源调度[J]. 系统工程与电子技术, 2022, 44(10): 3164-3173.

Peng JIN, Kang LI. Distributed satellite resource scheduling based on improved contract network protocol[J]. Systems Engineering and Electronics, 2022, 44(10): 3164-3173.

图/表 19

图1

图2

图3

图4

图5

表1

表2

表3

图6

图7

图8

表4

图9

图10

图11

表5

图12

图13

图14

参考文献 31

1	KARTHIKEYAN L , CHAWLA I , MISHRA A K . A review of remote sensing applications in agriculture for food security: crop growth and yield, irrigation, and crop losses[J]. Journal of Hydrology, 2020, 586, 124905. doi: 10.1016/j.jhydrol.2020.124905
2	QI J T , GUO J J , WANG M M , et al. A cooperative autonomous scheduling approach for multiple earth observation satellites with intensive missions[J]. IEEE Access, 2021, 9, 61646- 61661. doi: 10.1109/ACCESS.2021.3075059
3	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, 2020, 71 (9): 1390- 1410. doi: 10.1080/01605682.2019.1609891
4	WOLFE W J , SORENSEN S E . Three scheduling algorithms applied to the earth observing systems domain[J]. Management Science, 2000, 46 (1): 148- 166. doi: 10.1287/mnsc.46.1.148.15134
5	CHIEN S , SHERWOOD R , TRAN D , et al. Using autonomy flight software to improve science return on earth observing one[J]. Journal of Aerospace Computing, Information, and Communication, 2005, 2 (4): 196- 216. doi: 10.2514/1.12923
6	LAVALLEE D B , JEREMY J , OLSEN C , et al. Intelligent control for spacecraft autonomy-an industry survey[J]. Acta Paediatrica, 2008, 65 (4): 565- 569.
7	CHU X G , CHEN Y N , TAN Y J . An anytime branch and bound algorithm for agile earth observation satellite onboard scheduling[J]. Advances in Space Research, 2017, 60 (9): 2077- 2090. doi: 10.1016/j.asr.2017.07.026
8	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 and Operations Research, 2013, 40 (7): 1884- 1894. doi: 10.1016/j.cor.2013.02.009
9	ZHAO Y B , DU B , LI S . Agile Satellite mission planning via task clustering and double-layer tabu algorithm[J]. Computer Modeling in Engineering & Sciences, 2020, 122 (1): 235- 257.
10	CHANG Z X , ZHOU Z , YAO F , et al. Observation scheduling problem for AEOS with a comprehensive task clustering[J]. Journal of Systems Engineering and Electronics, 2021, 32 (2): 347- 364. doi: 10.23919/JSEE.2021.000029
11	张超, 李玉庆, 冯小恩, 等. 星群观测任务自主规划的星地联合运行机制[J]. 哈尔滨工业大学学报, 2018, 50 (4): 56- 61.
	ZHANG C , LI Y Q , FENG X E , et al. Joint operation mechanism of satellite and earth for autonomous planning of constellation observation mission[J]. Journal of Harbin Institute of Technology, 2018, 50 (4): 56- 61.
12	姚敏, 赵敏. 基于模糊神经网络的小卫星任务自主调度设计[J]. 宇航学报, 2007, 28 (2): 385- 388.385-388, 426 doi: 10.3321/j.issn:1000-1328.2007.02.028
	YAO M , ZHAO M . Autonomous task scheduling design of small satellite based on fuzzy neural network[J]. Journal of Astronautics, 2007, 28 (2): 385- 388.385-388, 426 doi: 10.3321/j.issn:1000-1328.2007.02.028
13	LIU L H , DONG Z H , SU H X , et al. A study of distributed earth observation satellites mission scheduling method based on game-negotiation mechanism[J]. Sensors, 2021, 21 (19): 6660. doi: 10.3390/s21196660
14	SKOBELEV P O , SIMONOVA E V , ZHILYAEV A A , et al. Application of multi-agent technology in the scheduling system of swarm of earth remote sensing satellites[J]. Procedia Computer Science, 2017, 103, 396- 402. doi: 10.1016/j.procs.2017.01.127
15	ZHAO M , LI D C . A hierarchical parallel evolutionary algorithm of distributed and multi-threaded two-level structure for multi-satellite task planning[J]. International Journal of Automation and Control, 2020, 14 (5-6): 612- 633.
16	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 and Video Processing, 2018, 2018, 29. doi: 10.1186/s13640-018-0268-8
17	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. doi: 10.1016/j.eswa.2013.10.014
18	ZHENG Z X , GUO J , GILL E . Onboard autonomous mission re-planning for multi-satellite system[J]. Acta Astronautica, 2018, 145 (4): 28- 43.
19	ZHENG Z X , GUO J , GILL E . Distributed onboard mission planning for multi-satellite systems[J]. Aerospace science and Technology, 2019, 89 (6): 111- 122.
20	HE L , LIU X L , CHEN Y W , et al. Hierarchical scheduling for real-time agile satellite task scheduling in a dynamic environment[J]. Advances in Space Research, 2019, 63 (2): 897- 912. doi: 10.1016/j.asr.2018.10.007
21	SMITH R G . The contract net protocol: high-level communication and control in a distributed problem solver[J]. IEEE Trans.on Computers, 1980, C-29 (12): 1104- 1113. doi: 10.1109/TC.1980.1675516
22	SMITH R G , DAVIS R . Frameworks for cooperation in distributed problem Solving[J]. IEEE Trans.on Systems, Man, and Cybernetics, 1981, 11 (1): 61- 70. doi: 10.1109/TSMC.1981.4308579
23	高黎, 沙基昌. 基于合同网的分布式卫星系统任务优化分配研究[J]. 宇航学报, 2009, 30 (2): 815- 820. doi: 10.3873/j.issn.1000-1328.2009.02.072
	GAO L , SHA J C . Research on task optimization assignment of distributed satellite system based on contract network[J]. Journal of Astronautics, 2009, 30 (2): 815- 820. doi: 10.3873/j.issn.1000-1328.2009.02.072
24	PENG P, CHEN H, PENG S, et al. A method of distributed multi-satellite mission scheduling based on improved contract net protocol[C]//Proc. of IEEE the International Conference on Natural Computation, 2015: 1062-1068.
25	陈恺. 遥感卫星分布式任务规划模型与算法研究[D]. 长沙: 国防科技大学, 2011.
	CHEN K. Research on distributed task planning model and algorithm of remote sensing satellite[D]. Changsha: National University of Defense Technology, 2011.
26	YANG W Y , HE L , LIU X L , et al. Onboard coordination and scheduling of multiple autonomous satellites in an uncertain environment[J]. Advances in Space Research, 2021, 68 (11): 4505- 4524. doi: 10.1016/j.asr.2021.09.003
27	张超, 靳鹏, 陈金勇, 等. 面向应急观测的虚拟星座任务规划技术[J]. 系统工程与电子技术, 2019, 41 (4): 819- 825.
	ZHANG C , JIN P , ZHEN J Y , et al. Virtual constellation mission planning technology for emergency observation[J]. Systems Engineering and Electronics, 2019, 41 (4): 819- 825.
28	ZHANG C , CHEN J Y , LI Y B , et al. Satellite group autonomous operation mechanism and planning algorithm for marine target surveillance[J]. Chinese Journal of Aeronautics, 2019, 32 (4): 991- 998. doi: 10.1016/j.cja.2019.02.005
29	DU B , LI S . A new multi-satellite autonomous mission allocation and planning method[J]. Acta Astronautica, 2019, 163, 287- 298. doi: 10.1016/j.actaastro.2018.11.001
30	CHEN Y T , TIAN G Q . Task planning for multiple-satellite-space-situational-awareness systems[J]. Aerospace, 2021, 8 (3): 73- 89. doi: 10.3390/aerospace8030073
31	LI F F , XU Z , LI H T . A multi-agent based cooperative approach to decentralized multi-project scheduling and resource allocation[J]. Computers & Industrial Engineering, 2021, 151, 106961- 106980.

任务编号	任务名称	观测时长/s	经度/(°)	纬度/(°)
0	abjl	28	65.53	62.354 5
1	acsq	14	121.729 5	22.727 5
⋮	⋮	⋮	⋮	⋮
498	njrl	29	121.388	30.617
499	nlkf	21	114.388	22.522

任务规模	CNAA		CPLEX求解器
任务规模	观测收益率/%	规划耗时/s	观测收益率/%	规划耗时/s
50	100.00	0.47	100.00	3.67
100	99.95	0.73	100.00	42.32
150	98.51	1.88	100.00	216.54
200	96.94	3.84	98.75	3 987.83
250	93.96	7.53	-	-
300	91.18	12.63	-	-
350	87.72	16.56	-	-
400	82.89	21.74	-	-
450	81.03	27.28	-	-
500	76.92	39.35	-	-

任务规模	CNAA算法			CNSA算法			CA算法
任务规模	观测收益率/%	任务完成率/%	规划耗时/s	观测收益率/%	任务完成率/%	规划耗时/s	观测收益率/%	任务完成率/%	规划耗时/s
50	100.00	100.00	0.47	92.22	87.20	1.93	100.00	100.00	0.25
100	99.95	99.80	0.73	88.65	81.80	6.37	99.97	99.90	1.03
150	98.51	97.20	1.88	84.22	76.46	17.13	99.05	98.20	8.14
200	96.94	93.35	3.84	82.29	72.10	32.30	97.81	94.80	19.77
250	93.96	88.56	7.53	80.41	68.96	46.53	95.01	90.80	39.12
300	91.18	84.26	12.63	78.88	66.93	60.53	92.57	86.53	66.67
350	87.72	79.68	16.56	76.12	64.09	91.02	89.30	81.91	111.60
400	82.89	75.25	21.74	72.73	61.20	113.72	85.21	77.75	157.58
450	81.03	69.88	27.28	71.08	58.53	166.13	82.56	73.62	203.25
500	76.92	67.61	39.35	67.96	55.84	208.65	78.08	69.10	253.08

任务规模	CNAA			CNSA			CA
任务规模	平均完成时间差/min	负载均衡值	协商次数	平均完成时间差/min	负载均衡值	协商次数	平均完成时间差/min	负载均衡值	协商次数
50	208.15	7.59	4.3	173.20	3.56	64.9	293.65	12.18	—
100	124.28	2.09	12.3	108.34	7.61	134.2	111.16	13.68	—
150	116.22	2.29	40.2	106.25	8.56	209.4	107.25	7.34	—
200	107.22	4.01	56.6	99.18	7.32	285.7	105.76	6.82	—
250	106.72	6.11	93.9	97.91	8.00	363.4	102.56	8.49	—
300	106.02	7.53	122.4	95.32	10.70	439.3	101.46	9.71	—
350	105.12	7.60	148.3	94.50	8.98	514.9	100.83	11.86	—
400	103.11	8.56	176.2	87.86	10.55	602.5	95.01	14.02	—
450	99.74	9.01	212.7	82.63	13.95	681.9	94.28	13.88	—
500	95.94	11.07	229.4	81.93	10.03	767.4	90.12	14.75	—

任务规模	3星			4星			5星
任务规模	规划耗时/s	观测收益率/%	协商次数	规划耗时/s	观测收益率/%	协商次数	规划耗时/s	观测收益率/%	协商次数
50	0.47	100.00	4.3	0.19	100.00	3.5	0.18	100.00	3.2
100	0.73	99.95	12.3	0.51	100.00	6.8	0.39	100.00	5.3
150	1.88	98.51	40.2	1.02	99.90	18.2	0.77	99.96	13.2
200	3.84	96.94	56.6	2.24	99.59	39.1	1.67	99.85	28.5
250	7.53	93.96	93.9	4.57	98.41	63.2	3.33	99.43	54.8
300	12.63	91.18	122.4	7.91	96.85	84.6	5.71	98.69	74.8
350	16.56	87.72	148.3	12.42	94.82	125.7	10.66	97.61	99.2
400	21.74	82.89	176.2	17.63	91.99	152.8	15.13	95.11	136.1
450	27.28	81.03	212.7	24.26	89.72	183.5	20.72	92.88	160.4
500	39.35	76.92	229.4	30.03	86.29	225.6	28.13	90.11	198.1