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

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

CLC Number:

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

Figures/Tables 19

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Table 1

Table 2

Table 3

Fig.6

Fig.7

Fig.8

Table 4

Fig.9

Fig.10

Fig.11

Table 5

Fig.12

Fig.13

Fig.14

References 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

Distributed satellite resource scheduling based on improved contract network protocol

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 19

References 31

Related Articles 14

Recommended Articles

Metrics

Comments

[1]	Jing YU, Enmi YONG, Hanyang CHEN, Dong HAO, Xiancai ZHANG. Bi-level mission planning method for multi-cooperative UAV air-to-ground attack [J]. Systems Engineering and Electronics, 2022, 44(9): 2849-2857.
[2]	Shengyu ZHANG, Yukun SUN, Zhencai ZHU, Haiying HU. Heuristic optimized forward-backward chains combination method for on-board multi-targets observation planning [J]. Systems Engineering and Electronics, 2021, 43(5): 1262-1269.
[3]	Kai CHENG, Gang CHEN, Xiaohan YU, Man LIU, Tianhao SHAO. Knowledge traction and data-driven wargame AI design and key technologies [J]. Systems Engineering and Electronics, 2021, 43(10): 2911-2917.
[4]	Gaowei JIA, Jianfeng WANG. Research review of UAV swarm mission planning method [J]. Systems Engineering and Electronics, 2021, 43(1): 99-111.
[5]	JIN Peng, WANG Chaochao, XIA Wei, YANG Bin, TANG Hang. Two phase emergency mission planning with satellite instruction release [J]. Systems Engineering and Electronics, 2019, 41(4): 810-818.
[6]	ZHANG Chao, JIN Peng, CHEN Jinyong, LI Yanbin, MA Wanquan. Virtual constellation task planning technology for emergency observation [J]. Systems Engineering and Electronics, 2019, 41(4): 819-825.
[7]	HE Yongming, CHEN Yingwu, XING Lining, YUAN Zang, LI Guoliang. Autonomous mission planning system design for novel imaging satellite [J]. Systems Engineering and Electronics, 2017, 39(4): 806-813.
[8]	NI Peng1,2, LIU Jinmang1, FU Qiang1, GAO Jiale1. #br# Research on layered decisionmaking of multisensor planning based onheterogeneous MAS in antiTBM combat [J]. Systems Engineering and Electronics, 2016, 38(8): 1816-1825.
[9]	HE Lei, LIU Xiao-lu, CHEN Ying-wu, XING Li-ning. Cloud modeling and processing method for agile observing satellite mission planning [J]. Systems Engineering and Electronics, 2016, 38(4): 852-858.
[10]	ZHANG Jia-ming, LIU Zhong, SHI Jian-mai, HE Yun-yue. Schedule of multiple satellite launch missions in multiple launch centers considering failures [J]. Systems Engineering and Electronics, 2015, 37(8): 1803-1809.
[11]	HU Xiao-xuan， ZHU Wai-ming， MA Hua-wei. Method of satellite and aerostat cooperative reconnaissance mission planning [J]. Systems Engineering and Electronics, 2015, 37(7): 1562-1568.
[12]	GUO Jiao, LI Zhenfang, LIU Yan-yang, BAO Zheng. InSAR signal processing for distributed satellites in the case of squint [J]. Journal of Systems Engineering and Electronics, 2011, 33(6): 1243-1246.
[13]	WANG Hui-lin, HUANG Xiao-jun, MA Man-hao, QIU Di-shan. Mission scheduling technique for electronic reconnaissance satellites [J]. Journal of Systems Engineering and Electronics, 2010, 32(8): 1695-1699.
[14]	LI Yuan, PENG Hui, SHEN Lin-cheng. Constraint satisfaction based resource conflicts detection and resolution in collaborative mission planning [J]. Journal of Systems Engineering and Electronics, 2009, 31(4): 868-873.