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

来源：计算机应用杂志2017年第6期北京时间：

作者：单国厚, 刘建, 水艳, 李丽华, 喻光晔

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

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

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

基金资助：国家自然科学基金资助项目（71671168）；国家重大科技专项（2014ZX07204-006-05）。