Please wait a minute...
img

官方微信

遥感技术与应用  2023, Vol. 38 Issue (4): 783-793    DOI: 10.11873/j.issn.1004-0323.2023.4.0783
宽波段多光谱数据立方专栏     
多目标算法在卫星区域覆盖调度及数传规划上的应用综述
何奇恩1(),李峰1,2,3(),钟兴1
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 HE1(),Feng LI1,2,3(),Xing ZHONG1
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  多目标进化算法求解示意图
变量符号说明
siSi个卫星
oijOii个卫星的第j次过境
xijki个卫星在第j次过境时的第k个条带
areaijkxijk所覆盖的面积
Mii个卫星的最大数据存储能力
αmaxii个卫星的最大侧摆能力
tq观测区域q的任务
rrq任务tq的要求分辨率
[rstq,?retq]任务tq的要求开始时间和结束时间
wijkWiji个卫星第j次过境时第k个条带的可视时间窗口
[wstq,?wetq]wijk的开始和结束时间
mijkwijk成像所占用的内存
grijkwijk获取的图像分辨率
overlap计算条带重叠率的函数
glGl个地面站
dtpDp个数传任务
twilhHi个卫星和第l个地面站之间的第h个时间窗口
[cstil,?cetil]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.