多目标算法在卫星区域覆盖调度及数传规划上的应用综述

doi:10.11873/j.issn.1004-0323.2023.4.0783

遥感技术与应用

2023, Vol. 38

Issue (4): 783-793 DOI: 10.11873/j.issn.1004-0323.2023.4.0783

宽波段多光谱数据立方专栏

多目标算法在卫星区域覆盖调度及数传规划上的应用综述

何奇恩¹(

),李峰^1,^2,³(

),钟兴¹

^1.长光卫星技术股份有限公司，吉林长春 130102
^2.中国科学院长春光学精密机械与物理研究所，吉林长春 130033
^3.中国科学院大学，北京 100049

A Review of the Application of Multi-objective Algorithms in Satellite Regional Coverage Scheduling and Data Transmission Planning

Qi'en HE¹(

),Feng LI^1,^2,³(

),Xing ZHONG¹

^1.Chang Guang Satellite Technology Company Limited，Changchun 130102，China
^2.Changchun Institute of Optics，Fine Mechanics and Physics，Chinese Academy of Sciences，Changchun 130033，China
^3.University of Chinese Academy of Sciences，Beijing 100049，China

全文: PDF(1688 KB) HTML

摘要：

随着全世界航天事业的不断壮大，卫星成像业务已经向多星协同覆盖大区域目标转型发展。在此过程中需要同时优化如最大覆盖面积、最小卫星资源利用等多个目标函数。围绕地球观测卫星区域覆盖调度及数传规划全流程，首先总结了典型区域分解技术，其作为卫星区域覆盖计划制定的前期准备步骤，在卫星调度中发挥着重要作用。随后分析评述了近年来多目标算法在卫星区域覆盖调度及数传规划领域的代表性工作。最后进行总结并对未来研究提出几点展望，以期为相关任务的多目标算法应用提供可靠参考。

关键词： 地球观测卫星; 区域分解; 卫星调度与规划; 地面站; 多目标进化算法; 多星协同

Abstract:

With the continuous development of the aerospace industry around the world， the satellite imaging business has developed towards the goal of multi-satellite collaboration covering large areas. In this process， multiple objective functions such as maximum coverage area and minimum satellite resource utilization need to be optimized simultaneously. Focusing on the whole process of regional coverage scheduling and data transmission planning of Earth observation satellites， the typical regional decomposition technology is firstly summarized， which plays an important role in satellite scheduling as a preparatory step for satellite regional coverage and makes the solving of combinatorial optimization problems possible. Then， the representative studies of Multi-Objective Evolutionary Algorithm （MOEA） in the field of multi-satellite joint regional coverage scheduling and data transmission planning in recent years are analyzed and reviewed. Common optimization goals include maximizing coverage rate， minimizing overlap ratio， minimizing the number of strips and so on. Finally， we summarize and put forward some prospects for future research， to provide a reliable reference for the application of multi-objective algorithms in related tasks.

Key words: Earth observation satellite Regional decomposition Satellite scheduling and planning Ground station Multi-objective evolutionary algorithm Multi-satellite coordination

收稿日期: 2022-08-25 出版日期: 2023-09-11

ZTFLH:

TP18

基金资助: 吉林省重点研发项目“多星联合大区域覆盖成像关键技术研究”(20210201015GX);国家重点研发计划“国产中高分辨率宽波段多光谱卫星数据集构建和高效国际化服务”(2019YFE0127000)

通讯作者: 李峰 E-mail: heqien777@126.com;lifeng@jl1.cn

作者简介: 何奇恩（1996-），男，吉林吉林人，硕士，主要从事多目标卫星调度与规划算法研究。E?mail: heqien777@126.com

	服务
	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	何奇恩
	李峰
	钟兴

引用本文:

何奇恩,李峰,钟兴. 多目标算法在卫星区域覆盖调度及数传规划上的应用综述[J]. 遥感技术与应用, 2023, 38(4): 783-793.

Qi'en HE,Feng LI,Xing ZHONG. A Review of the Application of Multi-objective Algorithms in Satellite Regional Coverage Scheduling and Data Transmission Planning. Remote Sensing Technology and Application, 2023, 38(4): 783-793.

链接本文:

http://www.rsta.ac.cn/CN/10.11873/j.issn.1004-0323.2023.4.0783 或 http://www.rsta.ac.cn/CN/Y2023/V38/I4/783

图1 卫星数据获取流程图

图2 点目标、区域目标及区域覆盖示意图

图3 等经纬度分解法

图4 等面积分解法

图5 条带分解法

图6 多目标进化算法求解示意图

变量符号	说明
$s i ∈ S$	第i个卫星
$o i j ∈ O i$	第i个卫星的第j次过境
$x i j k$	第i个卫星在第j次过境时的第k个条带
$a r e a i j k$	$x i j k$ 所覆盖的面积
$M i$	第i个卫星的最大数据存储能力
$α m a x i$	第i个卫星的最大侧摆能力
$t q$	观测区域q的任务
$r r q$	任务 $t q$ 的要求分辨率
$[r s t q, ? r e t q]$	任务 $t q$ 的要求开始时间和结束时间
$w i j k ∈ W i j$	第i个卫星第j次过境时第k个条带的可视时间窗口
$[w s t q, ? w e t q]$	$w i j k$ 的开始和结束时间
$m i j k$	$w i j k$ 成像所占用的内存
$g r i j k$	$w i j k$ 获取的图像分辨率
overlap	计算条带重叠率的函数
$g l ∈ G$	第l个地面站
$d t p ∈ D$	第p个数传任务
$t w i l h ∈ H$	第i个卫星和第l个地面站之间的第h个时间窗口
$[c s t i l, ? c e t i l]$	第i个卫星和第l个地面站的实际通信时间

表1 变量及说明

图7 加入目标区域偏好信息的多目标进化算法求解示意图

1	Union of Concerned Scientists （UCS） Satellite Database［DB/OL］. https：∥www.ucsusa.org/resources/satellite-database， 2022-12-31. 2023-07-18.
2	VAZQUEZ A J， ERWIN R S. On the tractability of satellite range scheduling［J］. Optimization Letters， 2015， 9（2）： 311-327. DOI： 10.1007/s11590-014-0744-8 doi: 10.1007/s11590-014-0744-8
3	NIU X， TANG H， WU L. 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：813-825. DOI：10.1016/j.ijdrr. 2018.02.013 doi: 10.1016/j.ijdrr. 2018.02.013
4	GAROUANI A EL， MULLA D J， GAROUANI S EL， et al. Analysis of urban growth and sprawl from remote sensing data： Case of Fez， Morocco［J］. International Journal of Sustainable Built Environment， 2017， 6（1）： 160-169. DOI： 10.1016/j.ijsbe.2017.02.003 doi: 10.1016/j.ijsbe.2017.02.003
5	KHALID N， ULLAH S， AHMAD S S， et al. A remotely sensed tracking of forest cover and associated temperature change in Margalla hills［J］. International Journal of Digital Earth，2019，12（10）：1133-1150. DOI：10.1080/17538947. 2018.1448008 doi: 10.1080/17538947. 2018.1448008
6	RIVETT C， PONTECORVO C. Improving satellite surveillance through optimal assignment of assets［R］. Defence Science and Technology Organisation Edinburgh （Australia） Intelligence Surveillance Reconn Div， 2003.
7	RUAN Qiming， TAN Yuejin， LI Yongtai， et al. Using constraint satisfaction to cooperate satellites' activities for the mission of area target observation［J］. Journal of Astronautics， 2007， 28（1）： 5.阮启明，谭跃进，李永太，等. 基于约束满足的多星对区域目标观测活动协同［J］. 宇航学报， 2007， 28（1）： 5.
8	SHAO X， ZHANG Z， WANG J， et al. NSGA-II-based multi-objective mission planning method for satellite formation system［J］. Journal of Aerospace Technology and Management， 2016， 8： 451-458. DOI： 10.5028/jatm.v8i4.700 doi: 10.5028/jatm.v8i4.700
9	LIU Huajun， CAI Bo， ZHU Qing. Self-adaptive planning method of imaging reconnaissance satellites area coverage［J］. Geomatics and Information Science of Wuhan University， 2017， 42（12）： 1719-1725.
9	刘华俊，蔡波，朱庆. 一种成像卫星区域覆盖的自适应规划方法［J］. 武汉大学学报·信息科学版， 2017， 42（12）： 1719-1725.
10	XU Yudong， ZHOU Jingbo， YIN Jiazhao， et al. Review of mission planning strategies and applications of earth observation satellites［J］. Radio Engineering， 2021， 51（8）： 681-690.
10	许宇栋，周敬博，尹嘉昭，等. 对地观测卫星任务规划策略及应用研究综述［J］. 无线电工程， 2021， 51（8）： 681-690.
11	ZHU W， HU X， XIA W， et al. A three-phase solution method for the scheduling problem of using earth observation satellites to observe polygon requests［J］. Computers & Industrial Engineering， 2019， 130（2019）： 97-107. DOI： 10.1016/j.cie.2019.02.014 doi: 10.1016/j.cie.2019.02.014
12	YANG Jiwei， FU Wei， HAN Li， et al. Regional target planning algorithm of satellite imaging based on global grid［J］. Spacecraft Engineering， 2021， 30（1）： 31-38.
12	杨纪伟，付伟，韩丽，等. 基于全球网格的卫星成像区域目标规划算法［J］. 航天器工程， 2021， 30（1）： 31-38.
13	LI X. Two-archive2 algorithm for large-scale polygon targets observation scheduling problem［C］∥Proceedings of the 2nd International Conference on Information Technology and Management Engineering， Shanghai， 2017： 23-24.
14	XU Y， LIU X， HE R， et al. Multi-objective satellite scheduling approach for very large areal observation［C］∥IOP Conference Series： Materials Science and Engineering. IOP Publishing， 2018， 435（1）： 012037.
15	SHEN Xiajiong， WU Xiaoyang， WANG Gengke， et al. Remote sensing satellite covering method over ground facing to any geometric area［J］. Application Research of Computers， 2016， 33（7）： 1999-2013.
15	沈夏炯，吴晓洋，王更科，等. 面向任意几何区域的遥感卫星对地覆盖法［J］. 计算机应用研究， 2016， 33（7）： 1999-2013.
16	PENG Pan， SONG Zhiming， NI Tao. Application of improved net-point method to solving area coverage problem［J］.Chinese Journal of Engineering Geophysics， 2019， 16（3）： 395-402.
16	彭攀，宋志明，倪涛. 改进的网格点法在区域覆盖问题中的应用［J］. 工程地球物理学报， 2019， 16（3）： 395-402.
17	WANG Rongfeng， HU Min. Algorithm for satellite regional coverage analysis based on scanline［J］. Computer Engineering， 2020， 46（1）： 243-246.
17	汪荣峰，胡敏. 基于扫描线的卫星区域覆盖分析算法［J］. 计算机工程， 2020， 46（1）： 243-246.
18	LIU X D， CHEN Y W， LONG Y J. A MapX-based preprocessing approach for multi-satellite cooperative observation towards area target［J］. Systems Engineering-Theory & Practice， 2010， 30： 2269-2275.
19	HE Y， XU M， YANG Z， et al. Scheduling imaging mission for area target based on satellite constellation［C］∥The 27th Chinese Control and Decision Conference， Qingdao， 2015： 3225-3230.
20	PAN Yao， CHI Zhongming， RAO Qilong， et al. Dynamic segmenting method of polygon target based on FOV for remote sensing satellite imaging［J］. Spacecraft Engineering， 2017，26（3）：38-42.
20	潘耀，池忠明，饶启龙，等. 基于视场角的遥感卫星成像多边形区域目标动态分解方法［J］. 航天器工程， 2017， 26（3）： 38-42.
21	ZHANG G， LI X， HU G， et al. Mission planning issues of imaging satellites： Summary， discussion， and prospects［J］. International Journal of Aerospace Engineering， 2021， 2021： 1-20.
22	BAI Baocun， RUAN Qiming， CHEN Yingwu. Dynamic segmenting method of polygon for remote sensing saltellites observing［J］. Operations Research and Management Science， 2008， 17（2）： 43-48.
22	白保存，阮启明，陈英武. 多星协同观测条件下区域目标的动态划分方法［J］. 运筹与管理， 2008， 17（2）： 43-48.
23	HE R， BAI B， CHEN Y， et al. Multi-satellite mission planning for environmental and disaster monitoring satellite system［C］∥SpaceOps 2008 Conference， Heidelberg， 2008： 3488.
24	YU Jing， XI Jinjun， YU Longjiang， et al. Study of one-orbit multi-strips splicing imaging for agile satellite［J］. Spacecraft Engineering， 2015， 24（2）： 27-34.
24	余婧，喜进军，于龙江，等. 敏捷卫星同轨多条带拼幅成像模式研究［J］. 航天器工程， 2015， 24（2）： 27-34.
25	YAO Jingyu. Research on multiple satellite scheduling method oriented to regional target observation［D］. Hefei： Hefei University of Technology， 2020.
25	姚靖宇. 面向区域目标观测的多星调度方法研究［D］. 合肥：合肥工业大学， 2020.
26	BRANDIMARTE P. Scheduling satellite launch missions： an MILP approach［J］. Journal of Scheduling， 2013， 16（1）： 29-45. DOI： 10.1007/s10951-012-0304-y doi: 10.1007/s10951-012-0304-y
27	RAMAN V， GILL N S. Review of different heuristic algorithms for solving travelling salesman problem ［J］. International Journal of Advanced Research in Computer Science， 2017， 8（5）： 423-425.
28	BEHESHTI Z， SHAMSUDDIN S M H. A review of population-based meta-heuristic algorithms［J］. International Journal of Advances in Soft Computing and its Applications， 2013， 5（1）： 1-35.
29	BIANCHESSI N， CORDEAU J F， DESROSIERS J， et al. A heuristic for the multi-satellite， multi-orbit and multi-user management of earth observation satellites［J］. European Journal of Operational Research， 2007， 177（2）： 750-762. DOI： 10.1016/j.ejor.2005.12.026 doi: 10.1016/j.ejor.2005.12.026
30	MANSOUR M 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. DOI： 10.1016/j.cie.2009.11.012 doi: 10.1016/j.cie.2009.11.012
31	GLOBUS A， CRAWFORD J， LOHN J， et al. Scheduling earth observing satellites with evolutionary algorithms［C］∥International Conference on Space Mission Challenges for Information Technology， California， 2003.
32	CHEN M， WEN J， SONG Y J， et al. A population perturbation and elimination strategy based genetic algorithm for multi-satellite TT&C scheduling problem［J］. Swarm Evolutionary Computation，2021，65：100912. DOI：10.1016/j.swevo.2021. 100912 doi: 10.1016/j.swevo.2021. 100912
33	FONSECA C M， FLEMING P J. An overview of evolutionary algorithms in multiobjective optimization［J］. Evolutionary Computation， 1995， 3（1）： 1-16.
34	DENG W， ZHANG X， ZHOU Y， et al. An enhanced fast non-dominated solution sorting genetic algorithm for multi-objective problems［J］. Information Sciences， 2022， 585： 441-453. DOI： 10.1016/j.ins.2021.11.052 doi: 10.1016/j.ins.2021.11.052
35	DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-II［J］. IEEE Transactions on Evolutionary Computation，2002，6（2）： 182-197.
36	CHEN Y， XU M， SHEN X， et al. A multi-objective modeling method of multi-satellite imaging task planning for large regional mapping［J］. Remote Sensing， 2020， 12（3）： 344. DOI： 10.3390/rs12030344 doi: 10.3390/rs12030344
37	WANG H， JIAO L， YAO X. Two_Arch2： An improved two-archive algorithm for many-objective optimization［J］. IEEE Transactions on Evolutionary Computation， 2014， 19（4）： 524-541.
38	WEI L， XING L， WAN Q， et al. A multi-objective memetic approach for time-dependent agile earth observation satellite scheduling problem［J］. Computers Industrial Engineering， 2021， 159： 107530. DOI： 10.1016/j.cie.2021.107530 doi: 10.1016/j.cie.2021.107530
39	MOSCATO P. On evolution， search， optimization， genetic algorithms and martial arts： Towards memetic algorithms［J］. Caltech Concurrent Computation Program， C3P Report， 1989， 826： 1989.
40	WANG J， JING N， LI J， et al. A multi-objective imaging scheduling approach for earth observing satellites［C］∥Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation， London， 2007： 2211-2218.
41	ZITZLER E， LAUMANNS M， THIELE L. SPEA2： Improving the strength pareto evolutionary algorithm［R］. TIK-report， 2001， 103.
42	DEB K， SUNDAR J. Reference point based multi-objective optimization using evolutionary algorithms［J］ International Journal of Computational Intelligence Research， 2006， 2（3）： 273-286.
43	SAID L B， BECHIKH S， GHÉDIRA K. The R-dominance： A new dominance relation for interactive evolutionary multicriteria decision making［J］. IEEE transactions on Evolutionary Computation，2010，14（5）：801-818. DOI： 10.1109/TEVC. 2010.2041060 doi: 10.1109/TEVC. 2010.2041060
44	MOLINA J， SANTANA L V， HERNÁNDEZ-DÍAZ A G， et al. G-dominance： Reference point based dominance for Mmultiobjective metaheuristics［J］. European Journal of Operational Research， 2009， 197（2）： 685-692. DOI： 10.1016/j.ejor.2008.07.015 doi: 10.1016/j.ejor.2008.07.015
45	THIELE L， MIETTINEN K， KORHONEN P J，et al.A preference-based evolutionary algorithm for multi-objective optimization［J］.Evolutionary Computation，2009，17（3）：411-436.
46	BEUME N， NAUJOKS B， EMMERICH M. SMS-EMOA： Multiobjective selection based on dominated hypervolume［J］. European Journal of Operational Research， 2007， 181（3）： 1653-1669.
47	TRAUTMANN H， WAGNER T， BROCKHOFF D. R2-EMOA： focused multiobjective search using R2-indicator-based selection［C］∥International Conference on Learning and Intelligent Optimization， Berlin， 2013： 70-74.
48	WANG Y， LI L， YANG K， et al. A new approach to target region based multiobjective evolutionary algorithms［C］∥2017 IEEE Congress on Evolutionary Computation （CEC）， San Sebastián， 2017： 1757-1764.
49	LI L， WANG Y， TRAUTMANN H， et al. Multiobjective evolutionary algorithms based on target region preferences［J］. Swarm Evolutionary Computation， 2018， 40： 196-215. DOI： 10.1016/j.swevo.2018.02.006 doi: 10.1016/j.swevo.2018.02.006
50	LI L， CHEN H， LI J， et al. Preference-based evolutionary many-objective optimization for agile satellite mission planning［J］. IEEE Access， 2018， 6： 40963-40978. DOI： 10.1109/ACCESS.2018.2859028 doi: 10.1109/ACCESS.2018.2859028
51	XIONG M， XIONG W， LIU C. A hybrid many-objective evolutionary algorithm with region preference for decision makers ［J］. IEEE Access， 2019， 7： 117699-117715. DOI： 10.1109/ACCESS.2019.2931742 doi: 10.1109/ACCESS.2019.2931742
52	XIONG M， XIONG W. A region preference-based optimization algorithm for satellite mission planning problem［C］∥Journal of Physics：Conference Series，Shenzhen，2022： 012035.
53	XHAFA F， HERRERO X， BAROLLI A，et al. A tabu search algorithm for ground station scheduling problem［C］∥2014 IEEE 28th International Conference on Advanced Information Networking and Applications， Victoria， 2014：1033-1040.
54	XHAFA F， HERRERO X， BAROLLI A， et al. Evaluation of struggle strategy in genetic algorithms for ground stations scheduling problem［J］. Journal of Computer System Sciences，2013，79（7）：1086-1100. DOI：10.1016/j.jcss.2013.01.023 doi: 10.1016/j.jcss.2013.01.023
55	LALA A， KOLICI V， XHAFA F， et al. On local vs. population-based heuristics for ground station scheduling［C］∥2015 Ninth International Conference on Complex， Intelligent， and Software Intensive Systems， Santa Catarina， 2015： 267-275.
56	ZHANG Z， XING L， CHEN Y， et al. Evolutionary algorithms for many-objective ground station scheduling problem［C］∥International Conference on Bio-inspired Computing： Theories and Applications， Singapore， 2016： 265-270.
57	SONG Y J， MA X， LI X J， et al. Learning-guided nondominated sorting genetic algorithm II for multi-objective satellite range scheduling problem［J］. Swarm Evolutionary Computation，2019，49：194-205. DOI：10.1016/j.swevo.2019.06.008 doi: 10.1016/j.swevo.2019.06.008
58	ZHANG J， XING L， PENG G， et al. A large-scale multiobjective satellite data transmission scheduling algorithm based on SVM+ NSGA-II［J］. Swarm Evolutionary Computation， 2019， 50： 100560. DOI： 10.1016/j.swevo.2019.100560 doi: 10.1016/j.swevo.2019.100560
59	PETELIN G， ANTONIOU M， PAPA G. Multi-objective approaches to ground station scheduling for optimization of communication with satellits［J］. Optimization and Engineering， 2021： 1-38. DOI： 10.1007/s11081-021-09617-z doi: 10.1007/s11081-021-09617-z
60	DEB K， JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sortinga approach， part I： Solving problems with box constraints［J］. IEEE Transactions on Evolutionary Computation， 2013， 18（4）： 577-601.
61	KUKKONEN S， LAMPINEN J. GDE3： The third evolution step of generalized differential evolution［C］∥2005 IEEE Congress on Evolutionary Computation， Edinburgh， 2005： 443-450.
62	ZITZLER E， KÜNZLI S. Indicator-based selection in multiobjective search［C］∥International Conference on Parallel Problem Solving from Nature， Berlin， 2004： 832-842.
63	ZHANG Q， LI H. MOEA/D： A multiobjective evolutionary algorithm based on decomposition［J］. IEEE Transactions on Evolutionary Computation， 2007， 11（6）： 712-731. DOI： 10.1109/TEVC.2007.892759 doi: 10.1109/TEVC.2007.892759
64	LIAO Z， GONG W， YAN X， et al. Solving nonlinear equations system with dynamic repulsion-based evolutionary algorithms［J］. IEEE Transactions on Systems， Man， Cybernetics： Systems， 2018， 50（4）： 1590-1601. DOI： 10.1109/TSMC.2018.2852798 doi: 10.1109/TSMC.2018.2852798
65	GONG W， WANG Y， CAI Z， et al. Finding multiple roots of nonlinear equation systems via a repulsion-based adaptive differential evolution［J］. IEEE Transactions on Systems， Man， Cybernetics： Systems， 2018， 50（4）： 1499-1513. DOI： 10.1109/TSMC.2018.2828018 doi: 10.1109/TSMC.2018.2828018

[1]	孟祥强,李峰,钟兴,衣晓宾,魏松岩. 基于多要素叠加的大区域遥感拍摄分解研究[J]. 遥感技术与应用, 2023, 38(4): 767-775.
[2]	安培浚,王雪梅,张志强,高峰. 国外遥感卫星地面站分布及运行特点[J]. 遥感技术与应用, 2008, 23(6): 697-704.
[3]	徐世永. 航空像片在识别适宜的GPS地面测站位置中的应用[J]. 遥感技术与应用, 1993, 8(3): 35-36.

Viewed

Full text

Abstract

Cited

Shared

Discussed