贪婪搜索算法在卫星调度中的应用

doi:10.11772/j.issn.1001-9081.2017.06.1814

计算机应用 ›› 2017, Vol. 37 ›› Issue (6): 1814-1819.DOI: 10.11772/j.issn.1001-9081.2017.06.1814

• 应用前沿尧交叉与综合 • 上一篇下一篇

贪婪搜索算法在卫星调度中的应用

单国厚¹, 刘建², 水艳², 李丽华², 喻光晔²

1. 中国科学技术大学管理学院, 合肥 230026;
2. 淮河流域水资源保护局淮河水资源保护科学研究所, 安徽蚌埠 230000

收稿日期:2016-11-16 修回日期:2017-01-04 出版日期:2017-06-10 发布日期:2017-06-14
通讯作者: 单国厚
作者简介:单国厚(1992-),男,安徽滁州人,硕士研究生,主要研究方向:卫星调度、智能算法优化;刘建(1961-),男,安徽蚌埠人,教授级工程师,博士,主要研究方向:水资源调度、智能算法优化;水艳(1982-),女,安徽繁昌人,高级工程师,硕士,主要研究方向:水资源调度、智能算法优化;李丽华(1990-),女,河南郑州人,工程师,硕士,主要研究方向:水资源调度、智能算法优化;喻光晔(1990-),男,湖北随州人,工程师,硕士,主要研究方向:水资源调度、智能算法优化。
基金资助:
国家自然科学基金资助项目（71671168）；国家重大科技专项（2014ZX07204-006-05）。

Application of greedy search algorithm in satellite scheduling

SHAN Guohou¹, LIU Jian², SHUI Yan², LI Lihua², YU Guangye²

1. School of Management, University of Science and Technology of China, Hefei Anhui 230026, China;
2. Scientific Research Department of Water Resource Preservation on Huaihe River, Water Resource Preservation Deputy of Huaihe River, Bengbu Anhui 230000, China

Received:2016-11-16 Revised:2017-01-04 Online:2017-06-10 Published:2017-06-14
Supported by:
This work is partially supported by the National Natural Science Foundation of China (71671168), the National Science and Technology Major Project (2014ZX07204-006-05).

摘要/Abstract

摘要： 针对采用天气预报的滞后云层进行卫星调度影响观测图像质量和观测收益的问题，提出一种获取实时云层的数学模型，并基于此构建考虑实时变换云层的敏捷观测卫星（AEOS）调度模型。由于贪婪搜索算法（GSA）具有局部优化的特性，能够充分考虑卫星观测的云层和有限存储资源等约束，研究了GSA在该卫星调度问题中的应用。首先，GSA优先考虑观测任务的云层遮挡，并根据云层遮挡大小，计算待观测任务的图像质量，将之排序选择待观测的任务；其次，结合任务的大小、截止时间和卫星的存储资源约束，选择能够给观测收益带来最大化的任务；最后，进行观测和任务传送。仿真实验表明，在任务数为100的情况下，采用GSA进行卫星调度的任务收益比常用于卫星调度的动态规划算法（DPA）所获得任务收益提高了14.82%，比局部搜索算法（LSA）所获得任务收益提高了10.32%，并且同等条件下，采用GSA得到的观测图像的质量比其他两种方法得到的图像质量更高。实验结果表明，GSA在实际卫星调度中，能够有效地提高图像观测质量和任务观测收益。

关键词: 卫星调度, 贪婪搜索算法, 近似实时云层, 任务收益, 图像质量

Abstract: In order to solve the problem that observational image quality and profits are low in satellite scheduling by adopting lagged weather forecast cloud information, a mathematic model capturing real-time cloud distribution was proposed. The Agile Earth Observation Satellite (AEOS) scheduling model was also built based on the real-time cloud information. Considering the local optimization of Greedy Search Algorithm (GSA) and it can give full consideration for constraints such as cloud of satellite observation and limited storage resources, the applications of GSA for the satellite scheduling problem were researched. Firstly, the cloud coverage of observation task was considered in priority order by GSA. The image quality value of observation task was calculated according to the size of cloud coverage and the observation task was selected by the sort of the image quality value. Secondly, the task with the maximize profit was selected according to task size, deadline and satellite storage resource. Finally, satellite observation and task transmission were completed according to their ability of improving profit. The simulation experiments show that, on the case of 100 tasks, the task profit of satellite schedule adopting GSA was improved by 14.82% and 10.32% compared with the Dynamic Programming Algorithm (DPA) and Local Search Algorithm (LSA) respectively. Besides, the image quality of applying GSA is higher than taking DPA and LSA in the same circumstance. The experimental results show that the GSA can effectively improve the image observation quality and task observation profit of satellite scheduling.

Key words: satellite scheduling, Greedy Search Algorithm (GSA), nearly real-time cloud, task profit, image quality

中图分类号:

TN927.2

单国厚, 刘建, 水艳, 李丽华, 喻光晔. 贪婪搜索算法在卫星调度中的应用[J]. 计算机应用, 2017, 37(6): 1814-1819.

SHAN Guohou, LIU Jian, SHUI Yan, LI Lihua, YU Guangye. Application of greedy search algorithm in satellite scheduling[J]. Journal of Computer Applications, 2017, 37(6): 1814-1819.

参考文献

[1] 郑义成,袁茵,邓勇,等.基于Pareto前沿与粒子群优化的卫星资源调度算法[J].计算机工程,2016,42(1):193-198.(ZHENG Y C, YUAN Y, DENG Y, et al. Satellite resource scheduling algorithm based on Pareto front and particle swarm optimization[J]. Computer Engineering, 2016, 42(1):193-198.)
[2] KAUFMAN Y J, TANRÉD, REMER L A, et al. Operational remote sensing of tropospheric aerosol over land from EOS moderate resolution imaging spectroradiometer[J]. Journal of Geophysical Research:Atmospheres, 1997, 102(D14):17051-17067.
[3] 邱涤珊,谈群,马满好,等.卫星成像侦察需求满足度评价方法研究[J].计算机工程,2012,38(8):256-259.(QIU D S, TAN Q, MA M H, et al. Research on satisfied degree evaluation method for satellite imaging reconnaissance requirement[J]. Computer Engineering, 2012, 38(8):256-259.)
[4] 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.
[5] WOLFE W J, SORENSEN S E. Three scheduling algorithms applied to the earth observing systems domain[J]. Management Science, 2000, 46(1):148-166.
[6] BEAUMET G. Continuous planning for the control of an autonomous agile satellite[EB/OL].[2016-10-16]. http://icaps06.icaps-conference.org/dc-papers/paper1.pdf.
[7] CHIEN S, SHERWOOD R, TRAN D, et al. The autonomous sciencecraft embedded systems architecture[C]//Proceedings of the 2005 IEEE International Conference on Systems, Man and Cybernetics. Piscataway, NJ:IEEE, 2005:3927-3932.
[8] TANGPATTANAKUL P, JOZEFOWIEZ N, LOPEZ P. Multi-objective optimization for selecting and scheduling observations by agile earth observing satellites[C]//Proceedings of the 2012 International Conference on Parallel Problem Solving from Nature, LNCS 7492. Berlin:Springer, 2012:112-121.
[9] BEAUMET G, VERFAILLIE G, CHARMEAU M C. Feasibility of autonomous decision making on board an agile earth-observing satellite[J]. Computational Intelligence, 2011, 27(1):123-139.
[10] WANG J J, ZHU X M, YANG L T, et al. Towards dynamic real-time scheduling for multiple earth observation satellites[J]. Journal of Computer and System Sciences, 2015, 81(1):110-124.
[11] CHEN Y, ZHANG D Y, ZHOU M Q, et al. Multi-satellite observation scheduling algorithm based on hybrid genetic particle swarm optimization[M]//Advances in Information Technology and Industry Applications. Berlin:Springer, 2012:441-448.
[12] GRAVES S C. A review of production scheduling[J]. Operations research, 1981, 29(4):646-675.
[13] WANG J, DEMEULEMEESTER E, QIU D. A pure proactive scheduling algorithm for multiple earth observation satellites under uncertainties of clouds[J]. Computers and Operations Research, 2016, 74(C):1-13.
[14] CHARMEAU M C, POULY J, BENSANA E, et al. Testing spacecraft autonomy with AGATA[EB/OL].[2016-10-16]. http://robotics.estec.esa.int/i-SAIRAS/isairas2008/Proceedings/SESSION%2022/m102-Charmeau.pdf.
[15] 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.
[16] TZIRKEL-HANCOCK E. Pattern matching method, apparatus and computer readable memory medium for speech recognition using dynamic programming:US, 5960395[P]. 1999-9-28.
[17] LARSEN B, AONE C. Fast and effective text mining using linear-time document clustering[C]//Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 1999:16-22.
[18] RABIDEAU G, KNIGHT R, CHIEN S, et al. Iterative repair planning for spacecraft operations using the ASPEN system[EB/OL].[2016-10-16]. http://www.metahack.org/isairas99-aspen.pdf.
[19] SMITH D K. Dynamic programming and optimal control. volume 1[J]. Journal of the Operational Research Society, 1996, 47(6):833-834.
[20] DAMIANI S, VERFAILLIE G, CHARMEAU M C. An anytime planning approach for the management of an earth watching satellite[EB/OL].[2016-10-16]. http://robotics.estec.esa.int/IWPSS/IWPSS_2004/workshop/works/6/006-verfaillie.pdfI
[21] AARTS E, LENSTRA J K. Local Search in Combinatorial Optimization[M]. Princeton, NJ:Princeton University Press, 2003:20-40.
[22] BENSANA E, VERFAILLIE G, AGNESE J C, et al. Exact & inexact methods for daily management of earth observation satellite[C]//SpaceOps 1996:Proceedings of the Fourth International Symposium on Space Mission Operations and Ground Data Systems. Paris:European Space Agency, 1996:507-514.

贪婪搜索算法在卫星调度中的应用

Application of greedy search algorithm in satellite scheduling

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	王思宇, 高炜欣, 李璐. 环口焊X射线焊缝图像质量评定模型[J]. 计算机应用, 2020, 40(9): 2748-2753.
[2]	陈佛计, 朱枫, 吴清潇, 郝颖明, 王恩德. 基于生成对抗网络的红外图像数据增强[J]. 计算机应用, 2020, 40(7): 2084-2088.
[3]	张俊升, 徐晶晶, 余伟. 面部美化图像质量无参考评价方法[J]. 计算机应用, 2020, 40(4): 1184-1190.
[4]	曹玉东, 蔡希彪. 基于增强型对抗学习的无参考图像质量评价算法[J]. 计算机应用, 2020, 40(11): 3166-3171.
[5]	程宇, 邓德祥, 颜佳, 范赐恩. 基于卷积神经网络的弱光照图像增强算法[J]. 计算机应用, 2019, 39(4): 1162-1169.
[6]	李秋珍, 栾朝阳, 汪双喜. 基于卷积神经网络的人脸图像质量评价[J]. 计算机应用, 2019, 39(3): 695-699.
[7]	王蔓, 颜佳, 吴敏渊. 基于视觉相似性的去色图像质量评估[J]. 计算机应用, 2017, 37(10): 2926-2931.
[8]	李娜, 周蓬勃, 耿国华, 贾晖. 色彩复原图像的质量评价方法[J]. 计算机应用, 2016, 36(6): 1673-1676.
[9]	马允, 王晓东, 章联军. 基于空域自然场景统计的无参考立体图像质量评价模型[J]. 计算机应用, 2016, 36(3): 783-788.
[10]	田金沙, 韩永国, 吴亚东, 赵小乐, 张红英. 基于尺度不变性的无参考图像质量评价[J]. 计算机应用, 2016, 36(3): 789-794.
[11]	仉静, 桑庆兵. 彩色立体图像质量评价方法[J]. 计算机应用, 2015, 35(3): 816-820.
[12]	陈益刚, 邓家先, 谢凯明. 基于JPEG-LS压缩比控制的图像压缩加密算法[J]. 计算机应用, 2015, 35(1): 93-98.
[13]	李鸿林张琦杨大伟. 无参考模糊图像质量评价改进算法[J]. 计算机应用, 2014, 34(3): 797-800.
[14]	杜少波章冲王超梁晓彬孙士保. 红外模糊图像的无参考质量评价方法[J]. 计算机应用, 2013, 33(08): 2306-2309.
[15]	廖宇郭黎. 基于梯度相关性分解的无参考图像质量评价方法[J]. 计算机应用, 2013, 33(03): 691-694.