留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种成像卫星区域覆盖的自适应规划方法

刘华俊 蔡波 朱庆

刘华俊, 蔡波, 朱庆. 一种成像卫星区域覆盖的自适应规划方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(12): 1719-1724. doi: 10.13203/j.whugis20150120
引用本文: 刘华俊, 蔡波, 朱庆. 一种成像卫星区域覆盖的自适应规划方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(12): 1719-1724. doi: 10.13203/j.whugis20150120
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-1724. doi: 10.13203/j.whugis20150120
Citation: 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-1724. doi: 10.13203/j.whugis20150120

一种成像卫星区域覆盖的自适应规划方法

doi: 10.13203/j.whugis20150120
基金项目: 

国家自然科学基金 41471320

国家自然科学基金 41301409

高等学校博士学科点专项科研基金 20130141120021

详细信息
    作者简介:

    刘华俊, 博士, 副教授, 主要从事虚拟地理环境的理论与方法研究。huajunliu@whu.edu.cn

    通讯作者: 蔡波, 博士, 副教授。bo_cai@yeah.net
  • 中图分类号: P236

Self-adaptive Planning Method of Imaging Reconnaissance Satellites Area Coverage

Funds: 

The National Natural Science Foundation of China 41471320

The National Natural Science Foundation of China 41301409

the Research Fund for the Doctoral Program of Higher Education of China 20130141120021

More Information
    Author Bio:

    LIU Huajun, PhD, associate professor, specializes in virtual geographic environments. E-mail: huajunliu@whu.edu.cn

    Corresponding author: CAI Bo, PhD, associate professor. E-mail: bo_cai@yeah.net
图(4) / 表(2)
计量
  • 文章访问数:  743
  • HTML全文浏览量:  68
  • PDF下载量:  566
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-12-15
  • 刊出日期:  2017-12-05

一种成像卫星区域覆盖的自适应规划方法

doi: 10.13203/j.whugis20150120
    基金项目:

    国家自然科学基金 41471320

    国家自然科学基金 41301409

    高等学校博士学科点专项科研基金 20130141120021

    作者简介:

    刘华俊, 博士, 副教授, 主要从事虚拟地理环境的理论与方法研究。huajunliu@whu.edu.cn

    通讯作者: 蔡波, 博士, 副教授。bo_cai@yeah.net
  • 中图分类号: P236

摘要: 卫星对侦查区域的覆盖语义是影响侦查覆盖效率的关键因素之一。针对现有覆盖算法低效耗时的技术瓶颈,提出了一种针对成像卫星区域覆盖的自适应规划方法,包括自适应的网格划分、平衡成像精度和覆盖效率的最大可视覆盖计算以及窗口优化的卫星区域覆盖策略。通过与常用经典算法对比,验证了本文方法的有效性和鲁棒性。本文方法已成功应用于某些在轨卫星的区域覆盖任务。

English Abstract

刘华俊, 蔡波, 朱庆. 一种成像卫星区域覆盖的自适应规划方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(12): 1719-1724. doi: 10.13203/j.whugis20150120
引用本文: 刘华俊, 蔡波, 朱庆. 一种成像卫星区域覆盖的自适应规划方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(12): 1719-1724. doi: 10.13203/j.whugis20150120
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-1724. doi: 10.13203/j.whugis20150120
Citation: 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-1724. doi: 10.13203/j.whugis20150120
  • 随着在轨卫星数目的不断增加, 多颗成像侦察卫星对单个区域目标进行观测时, 选择不同观测方案会产生不同的空间覆盖率效果[1]。受卫星飞行轨道、侧摆角以及地球自转等空间因素影响以及卫星通过覆盖区域的时间制约, 成像卫星在指定的时间段对单个区域进行最大效率的侦查覆盖实际上是一个基于时空约束的动态组合优化问题。随着网络通讯技术的发展和星载存储容量的快速增加, 卫星与地面站以及中继星之间的数据交换速度已不再对卫星下传数据的效率产生制约。因此, 如何利用空闲卫星资源对侦查区域较快地完全覆盖, 已经成为提高区域侦查效率的主要问题。

    针对成像卫星的区域覆盖规划问题, 国内外相继出现了面向点目标和面目标的区域覆盖方法。面向点目标的多星任务规划可以利用启发式的随机搜索对问题进行求解, 但只能对小规模的规划问题求解, 效率不高[2];有的研究仅讨论调度问题, 并未提及系统具体采用的模型及算法[3, 4];有的研究将规划问题看作是时间约束的调度问题[5], 但并未考虑侦查目标对多颗卫星的空间约束;有研究建立了规划模型[6], 并基于动态惩罚函数的遗传算法进行问题求解。面向点目标与面目标的卫星规划两者的主要区别在于后者要求覆盖区域的完备性得到保障, 因此区域覆盖也不能套用点目标的侦查模式。面向面目标的任务规划问题一般可以分为单星侦察[7-10]和多星协同侦察两种模式。有研究针对单星侦察模式建立了整数规划模型[8], 但该模型只能适用于卫星单次过境并且观测场景无重叠的情况;有研究在建立模型的同时采用邻域搜索来求解问题[9], 但其采用的场景重叠途径会增大问题搜索的空间, 求解的复杂度也会急剧增加。随着在轨卫星数目的增多, 单星侦察的模式已逐渐被多星协同侦察所取代。智能优化算法中的遗传学途径和模拟退火途径是面目标任务规划中普遍采用的方法[11-14], 但是也会存在优化求解时间过长, 算法执行效率不高的问题。针对面目标的多星协同侦察模式通常利用单纯的或改进的智能优化算法来解决成像卫星的区域覆盖问题, 却忽略了多颗卫星区域覆盖的时空约束语义, 且算法的收敛性很大程度依赖初始值的选取, 不收敛的情况时有发生;虽对卫星的侦查进行了组合规划求解, 但是未考虑成像精度和覆盖效率之间的制约关系。

    区域覆盖的常用方法是首先对覆盖区域进行网格划分, 通常是对区域单纯地利用等经纬度划分网格[1, 15], 并不能判断覆盖的边界是否严格落入覆盖范围。为保证计算求解的效率, 划分粒度一般只达到95%的实际覆盖率, 但是此粒度并不能保证当今侦查的要求。基于此, 文献[16]提出了边缘网格再划分方法, 然而, 不规则的侦查区域对于边界的判断以及边界网格的细分标准也需要过多计算量和人机交互。

    基于以上情况, 本文提出了一种针对成像卫星区域覆盖的自适应方法, 同时提出了一种自适应的网格划分标准, 并充分考虑时空覆盖之间的语义约束, 有效解决了不收敛的问题, 有望最大效率地利用卫星资源;还提出了一种顾及成像精度和覆盖效率的评价标准, 自动计算寻找实际覆盖和计算效率之间的平衡点。

    • 图 1是本文提出的算法流程图, 由自适应的网格划分、平衡成像精度和效率的最大可视覆盖计算以及窗口优化的卫星区域覆盖策略3个子部分组成。

      图  1  成像卫星区域覆盖规划算法流程图

      Figure 1.  Flowchart of Planning Algorithm of Imaging Reconnaissance Satellites Area Coverage

    • 基于等经纬度的网格划分是区域覆盖中经常采用的途径, 通常是利用高斯方法将划分网格投影到平面区域。一般来说, 密集的网格划分会提高实际覆盖率, 但计算量也会增大。在以往的应用中, 95%的实际覆盖率即可认为对区域进行了一个完整的覆盖, 而大约5%的未覆盖区域一般产生在边界网格。为了提高网格覆盖率的边界网格再划分方法, 首先要对边界网格进行判断, 然后对其进行4的幂次方的迭代划分计算, 计算代价高, 也需要大量的人机交互干预。在实际覆盖中, 区域网格的划分要充分考虑实际覆盖率以及计算效率。

      网格划分越细, 即网格面积越小, 实际覆盖率越高。因此本文利用正态分布函数来近似模拟两者之间的变化关系, 用式(1) 来评价网格划分后的实际覆盖率C1

      $${C_1} = \frac{\varepsilon }{{\varepsilon + {\rm{ }}\sqrt {{d_{{\rm{lon}}}} \times {d_{{\rm{lat}}}}} }}{e^{ - \frac{{{d_{{\rm{lon}}}} \times {d_{{\rm{lat}}}}}}{{2{\sigma ^2}}}}}$$ (1)

      式中, dlondlat分别表示网格划分的经纬度间隔;dlon×dlat为划分网格的大小。在实验中, 取ε=0.1, σ=0.2。C1的值范围在[0, 1]区间, 值越大表示实际覆盖率越好, 相应的网格划分越密集。

      但是, 密集的网格划分会降低覆盖算法的效率, 计算时间会变长。本文用式(2) 来近似评价算法计算效率C2和网格划分大小之间的关系:

      $${C_2} = {e^{\frac{{{d_{{\rm{lon}}}} \times {d_{{\rm{lat}}}}}}{{2{\mu ^2}}}}}$$ (2)

      在实验中, μ= 0.5。

      由于实际侦察区域的影响, 很难对网格划分标准进行固定。事实上, 综合实际覆盖率和计算量等因素, 本文给出了如下衡量标准来自适应地确定网格划分的大小, 在兼顾实际覆盖率的同时, 确保算法的计算效率:

      $$\arg {\max _{{d_{{\rm{lon}}}} \times {d_{{\rm{lat}}}}}}\sqrt {{C_1}{C_2}} $$ (3)

      通过优化取值, 使得$\sqrt {{C_1}{C_2}} $的值最大的dlon×dlat值即为最佳的网格划分大小的标准。

    • 成像卫星的区域覆盖效果一般从成像质量和完成时间两方面来综合评价, 对规定区域进行短时间高分辨率推扫一直是区域覆盖追求的目标。当需要对区域快速成像时, 首选较大的侧摆角, 但成像的分辨率将会下降;如果保证成像的质量, 卫星侧摆角的活动范围将变小, 也会增加推扫成像的时间。此外, 卫星运行轨道的高度和卫星载有的光学成像器件的参数各有区别。因此, 如何找到具体卫星成像质量和覆盖效率之间的平衡点, 是进行快速高质量区域覆盖的前提。对此, 我们综合求解成像质量和覆盖效率, 给出了顾及两者的卫星侧摆角活动范围的计算标准:

      $$\left\| \alpha \right\| \propto {x^{ - k}}\cdot{e^{\beta x}}$$ (4)

      式中, α为侧摆角的变化范围, 在[-α, α]中取值;x为成像分辨率, x-k用于评价侧摆角对成像质量的影响, k>0;eβx用于评价侧摆角对覆盖效率的影响。通过最大化x-k·eβx, 并依据卫星运行轨道和光学成像器件参数, 求得具体卫星侧摆角α的合适取值范围。根据经验取值, 在实验中, k取2, β取0.3。

      根据式(4) 确定侧摆角的变化范围后, 称卫星的最大侧摆角对应的覆盖范围为此卫星的最大可视覆盖, 用来描述卫星的覆盖信息语义。虽然卫星的运行轨道是固定不变的, 但是随着地球的自转, 单颗卫星每次通过侦查区域时的最大可视覆盖将会动态变化, 需重新计算。

    • 从本质上说, 多颗侦查卫星的区域覆盖问题是一个动态的组合优化问题。如果多颗卫星的一轮推扫未完成区域的覆盖要求, 将会进行下一轮的推扫, 直至对区域完全覆盖。如何对多颗卫星的任务序列进行提前优化(即提前安排卫星的侧摆角), 使其在最短时间内达到对区域的完全覆盖, 是提高侦查效率的关键问题。

      假设K颗卫星协同参与区域覆盖任务, 并且需要多轮的依次推扫来完成区域的完全覆盖。在网格划分后, 设每个网格的初始值为0。当其被最大可视覆盖涵盖一次, 网格值加1, 依次类推。由于卫星之间的最大可视覆盖也会产生重叠区域, 所以, 本文采用表达式(number, (satellite, round), …)来表示网格值以及卫星的覆盖信息语义。其中, number表示网格的覆盖次数, (satellite, round)表示此网格被具体卫星的覆盖轮数。如图 2所示, 椭圆形为需要侦察的区域, 两条Sij线之间为卫星i在第j轮的最大可视覆盖, 其中, 区域A只能被卫星2在第一轮的最大可视覆盖涵盖, 记为(1, (2, 1))。区域B能分别被卫星1和卫星2在第一轮的最大可视覆盖涵盖, 记为(2, (1, 1), (2, 1))。区域C能被卫星1分别在第一轮和第二轮的最大可视覆盖涵盖, 记为(2, (1, 1), (1, 2))。区域D能分别被卫星1、2、3在第一轮的最大可视覆盖涵盖, 记为(3, (1, 1), (2, 1), (3, 1))。考虑卫星的覆盖语义, 可知网格的覆盖次数越小, 被推扫的机会越小。依据覆盖语义, 本文认为值越小的网格需要优先被推扫。

      图  2  区域覆盖实例

      Figure 2.  An Example of Area Coverage

      然而, 网格的具体覆盖次数受不同卫星扫描次数的影响, 侧摆角序列的优化求解本质上是一个NP难问题。实验证明, 当问题不大时, 采用完全搜索算法可以在较短的时间内得到一个最优解, 但当问题规模较大时, 采用完全搜索算法就不能在合理的时间内得到问题的解, 还会耗费大量的求解时间。因此, 本文采用滑动窗口, 在窗口内进行局部组合优化求解。根据覆盖语义, 规定区域被最大可视覆盖一次时的滑动窗口大小为1, 区域被最大可视覆盖两次时的窗口大小为2, 图 2每次考虑4次最大可视覆盖, 因此窗口大小为4。当然, 窗口无限增大时, 求得的解将无限接近全局最优解, 但也趋近于完全搜索算法。

      在滑动窗口中考虑卫星之间的时空语义约束。图 3显示的滑动窗口大小为4(图 3中红点表示多颗卫星通过侦察区域的次序, 绿点表示正在确定侧摆角的卫星, 蓝点表示已经确定侧摆角的卫星, 蓝框表示滑动窗口)。当确定时序上第一个通过的卫星确定侧摆角后, 窗口向前移动一步, 继续给时序上第二个通过的卫星侧摆角, 直至完成区域覆盖为止。面向不同的覆盖区域以及具体参与侦察任务的卫星, 滑动窗口的大小可以自适应地计算选取。在实验中, 综合考虑求解效率和覆盖效果, 根据经验取滑动窗口大小的初值为5, 然后分别在其邻域范围内自动选取不同的窗口大小值计算覆盖时间, 将最短计算时间对应的窗口大小值作为实际问题的滑动窗口值。

      图  3  滑动窗口

      Figure 3.  Sliding Window

      为了较快地完成区域覆盖, 依据卫星最大可视覆盖之间的关联语义, 本文提出了两种窗口优化的区域覆盖选择策略。

      策略1  卫星每次在自己的区域网格值最小的最大可视覆盖中选择未覆盖的面积最大的侧视覆盖条带确定侧摆角, 推扫后的网格值更新为-1, 未推扫的覆盖区域网格值则赋零。

      策略2  如果出现最小网格值的推扫条带面积相同时, 卫星将在其中选择实际未覆盖面积最大的侧视覆盖条带确定侧摆角。

      其中, 覆盖策略1优于覆盖策略2。

      本文算法首先根据式(3), 针对覆盖区域自适应地选择网格划分的大小;并根据式(4) 来计算单颗卫星的最大可视覆盖;然后, 依据具体参与任务的卫星和覆盖侦察区域, 自动地测试滑动窗口的大小, 来自适应地选择合适的滑动窗口用于任务的局部规划。在局部规划过程中, 首先, 在当前的滑动窗口中, 根据每颗卫星的最大可视覆盖语义计算网格值;并根据覆盖策略, 给当前卫星选择合适的侧摆角并更新网格值;然后, 窗口向前滑动一步, 根据滑动后窗口中的卫星最大可视覆盖语义, 计算未覆盖网格的新值, 并依据覆盖策略选择当前卫星的侧摆角。此过程重复执行, 直至网格覆盖完成。

    • 本文测试算法在一台配置为Inter i3-2100 3.10 GHz CPU, NVIDIA Quadro 600显卡、4 GB内存的图形工作站上进行。开发平台为Mi-crosoft Visual Studio.Net 2010, 编程语言为C++, 并利用STK(satellite tool kit)仿真软件模拟验证算法。

    • 自适应的网格划分综合考虑实际覆盖率和完成时间, 并不需要用户的干预。为验证其优越性, 本文针对实际区域(108°E ~ 116°E, 29°N ~ 33°N)分别设计了3种区域形状(方形、圆形和用户随意勾勒的形状), 从平均的实际覆盖率(actual coverage, AC)和平均完成时间上对3种网格划分方法进行了对比, 见表 1表 1中完成时间是统一采用滑动窗口大小为4的覆盖策略在这3种网格划分方法下的运行时间。本文设定等经纬度网格划分对方形区域95.8%实际覆盖率的完成时间为1个单位时间, 其他时间的计算都以此单位时间为标准比较得出。可以看出, 等经纬度网格划分的完成时间是最快的, 但实际覆盖率只有95%左右;边界网格划分的实际覆盖率最高, 但是最耗时;自适应网格划分的实际覆盖率最接近边界网格划分, 完成时间略高于等经纬度网格划分, 但也得到了很好的保证。

      表 1  网格划分方法的平均覆盖率和完成时间

      Table 1.  Average Coverage and Complete Time for Different Mesh Division Approaches

      区域等经纬度网格划分边界网格划分自适应网格网格划分
      AC /% 完成时间AC /% 完成时间AC /% 完成时间
      方形95.81.097.95.297.51.4
      圆形95.31.798.17.897.42.2
      任意94.52.397.610.697.02.6
    • 由于滑动窗口的大小会直接影响网格的覆盖次数, 也会对当前卫星的侧摆角的选择产生影响, 本文比较分析了滑动窗口对覆盖效率的影响, 见表 2。本文测试了该算法在24 h内通过的卫星针对我国境内3个区域A(110°E ~ 113°E, 15°N ~ 17°N))、B(108°E ~ 116°E, 29°N ~ 33°N)、C(78°E ~ 99°E, 26°N ~ 37°N)在不同的滑动窗口下的完成时间, 表 2中的时间计算依然与表 1中等经纬度网格对方形区域的完成时间作对比。通过仿真实验测试发现, 实际完成时间随着滑动窗口变大下降明显, 在窗口为5或6时达到最小, 随后又缓慢逐渐增加。这是因为滑动窗口的增大对当前卫星的一次最大可视覆盖的判断会更精确, 侧视覆盖条带的选择也会更加合理, 所以区域的总体完成时间会大幅减少。但是, 随着窗口的不断增大, 也会有大量时间用于滑动窗口中网格覆盖次数的计算, 所以在窗口大小为6和7时, 网格覆盖次数的计算时间已经超过了由于侧视覆盖条带的优化选择减少的时间, 总体完成时间也会相应增加。

      表 2  滑动窗口大小对完成时间的影响

      Table 2.  The Complete Time for Different Sizes of Sliding Window

      区域1234567
      A4.013.271.921.281.071.231.31
      B5.203.792.431.791.721.631.80
      C7.875.233.662.452.412.482.53
    • 为了验证不同算法的性能, 本文对24 h内通过区域ABC的空闲卫星进行成像侦察。首先, 按照自适应的网格划分方法, 将3种区域形状离散为多个网格并投影到平面直角坐标系中。接着, 将窗口优化的区域覆盖策略和经典的遗传算法、模拟退火算法进行了比较, 3者完成区域覆盖所需的模拟时间如图 4所示。从图 4中可以看出, 遗传算法由于进化迭代的次数耗时最多, 模拟退火算法要略优于遗传算法, 而本文提出的自适应覆盖策略相较于两种经典的算法完成时间更短。

      图  4  算法结果对比

      Figure 4.  Comparison Result of Different Algorithms

    • 卫星对侦查区域的覆盖语义是影响侦查覆盖效率的关键因素之一。现有的大多数区域覆盖算法忽略了卫星实际通过侦查区域的时空语义, 在实际的应用过程中往往不能效益最大化地利用卫星资源。本文提出的区域覆盖动态规划方法可以自适应地计算网格划分标准、成像精度和窗口优化的大小, 减少了用户的交互操作。实验结果表明, 相较于以往的覆盖算法, 本文提出的覆盖策略能够迅速找到优化序列并且大幅提高覆盖效率。但本文基于滑动窗口的优化方法只能找到一个局部最优解, 并不能保证其全局最优性, 下一步的工作将聚焦顾及效率的全局最优规划序列方法的研究。

参考文献 (16)

目录

    /

    返回文章
    返回