史良树 黄鹏 战鹰 朱政霖 马广彬

(1 中国土地勘测规划院，北京 100081) (2 中国科学院遥感与数字地球研究所，北京 100094)



应用近似算法的光学遥感卫星区域目标成像任务规划方法

史良树1黄鹏2战鹰1朱政霖2马广彬2

(1 中国土地勘测规划院，北京 100081) (2 中国科学院遥感与数字地球研究所，北京 100094)

光学遥感卫星成像任务规划的研究对象多以点目标为主，对于区域目标的处理，多是将其转化为点目标后求解，因此存在精度不高和效率过低等问题。同时，还存在对于长时间周期的规划问题耗时过长，以及大区域长时间任务规划性能较差等问题。文章根据卫星成像任务规划的约束条件，建立成像任务规划模型，分析并归纳光学遥感卫星轨道及星下点轨迹的特点，认为星下点轨迹在中低纬度区域的投影可近似认为是直线；通过将区域目标向直线投影，将二维平面区域转化为一维线状区域，对模型进行求解。该方法能大幅降低求解区域目标问题的复杂度，在一维线状区域的基础上对侧摆进行处理，同时能够提高长时间周期规划的性能。利用环境减灾-1A(HJ-1A)卫星进行验证，结果表明，文章提出的方法能够在较短的时间内解决大区域长时间成像任务规划问题。

光学遥感卫星；星下点；成像任务规划；近似算法；区域目标

1 引言

光学遥感卫星利用遥感器从太空获取地面影像的技术称为卫星成像技术[1]，正在气象、农业和防灾等领域发挥着重要作用。卫星成像任务规划指对地面待成像区域制定拍摄计划，合理安排卫星成像区域，确定遥感器开关机时间，以充分利用有限的卫星资源尽可能多地完成拍摄任务。卫星成像任务规划是卫星运行控制系统的核心[2]，对实现卫星成像任务起决定性作用。

针对卫星成像任务规划技术，国内外已有大量研究。研究结果表明，此类技术可分为成像任务规划模型的建立和求解两部分[3]。其中，常见的成像任务规划模型包括基于图论、整形规划和多维背包问题的模型[4-5]；常见的求解算法以启发式算法为主，包括遗传算法、模拟退火算法等[6-7]。上述模型的研究对象多是基于点目标[8]。但是，在实际情况中，用户的任务请求多为区域目标，例如针对某个省、县等区域目标的成像任务；另外，当拍摄目标较大时，例如森林火灾、旱涝灾害等，此类目标的成像通常无法通过成像卫星一次拍摄获取，规划时不能视为点目标。因此，针对区域目标的成像任务规划具有重要意义。目前，针对区域目标的调度，通常包括网格点法[9]和解析法[10]。网格点法首先将地面任务区域按照一定间隔划分为一系列网格，将区域目标转化为点目标，进行处理。该方法的运算结果受网格大小的影响，网格过大，造成规划结果不准确；网格过小，造成运算量过大，效率降低。解析法是通过卫星与地球的几何拓扑关系，获取条带与地面任务区域的关系。但是，该方法过于依赖二维拓扑计算，计算过境条带与区域目标的拓扑关系时，算法复杂度较高，当调度时间过长、地面任务区域过大时，成像任务规划耗费时间过长。此外，针对点目标的规划算法，调度时间多为一天或几天[11]，地面任务区域多为几百个点目标，如果是长时间周期、大地面任务区域的调度，此类规划方法耗时过长。

本文根据光学遥感卫星成像需要满足的约束条件建立算法模型，然后分析光学遥感卫星轨道及星下点轨迹的特点，在此基础上应用近似算法，针对区域目标进行研究，避开时间复杂度较高的二维拓扑计算[12]，可快速解决大区域长时间成像任务规划问题。

2 成像任务规划模型的建立

卫星成像任务规划是一个组合优化问题，其约束条件较为复杂，考虑到研究对象是大区域长时间的任务规划，本文对成像规划需要满足的基本约束条件进行归纳和简化，并对规划模型进行求解。

本文研究的光学遥感卫星成像任务规划模型可以描述为：已知一组光学遥感卫星和一组地面任务区域，每颗卫星与地面任务区域均有一组可视的时间窗，如何在一定的时间内，对一系列过境条带进行合理组合，用尽可能少的卫星资源对地面任务区域完成覆盖。

对于成像分辨率达到用户需求的一组卫星的集合S，以及地面任务区域R，约束条件包括以下几个方面。

2.1 过境时间窗约束

对于S中的第i颗卫星，在时间段t∈[m1,m2]能够拍摄到的条带为Pi,t，该条带作为规划对象的条件为

(1)

式中：φ为空集。

式(1)表示当卫星在某个时间段的推扫条带与地面任务区域有重叠时，该条带才将成为规划对象。对于不能侧摆的卫星，将遥感器视场角覆盖区域作为条带；对于能够侧摆的卫星，将遥感器通过不同侧摆角拍摄到的所有区域均作为条带。

2.2 条带重叠率约束

为提高资源利用率，规划结果的条带组合应满足

(2)

(3)

式中：决策变量xk,t∈{0,1}，xk,t=1时，表示条带Pk,t被成像，作为规划结果的条带之一，xk,t=0时，表示条带Pk,t未被成像；k1,k2∈{1,2,…,|S|}；α为最大重叠率；β为最小重叠率。

式(2)是最大重叠率约束，表示规划结果条带组合的任意2个条带，其交集与面积之和的比值，即重叠率不能超过最大重叠率。式(3)是最小重叠率约束，表示对于相邻有重叠的2个条带，其重叠率不能低于最小重叠率，增大最小重叠率可减小条带之间的缝隙，即增大覆盖率，但会造成条带个数增多。

2.3 覆盖率约束

对于规划结果的条带组合，要尽可能多地覆盖地面任务区域R，应满足

(4)

式中：c为设定的覆盖率。

式(4)表示所有规划结果的条带，其并集的面积与地面任务区域面积的比值应大于覆盖率。对于大区域长时间的任务规划，任务时间较长，因此能够有足够长的时间完成对地面任务区域的覆盖，覆盖率通常取100%。

基于以上，在一定的资源条件下，以消耗资源尽可能少为目标，本文成像任务规划模型的目标函数为

(5)

式(5)表示成像任务规划的目标是用尽可能少的条带覆盖地面任务区域。

3 成像任务规划模型的求解

本文成像任务规划模型要重点解决的问题包括：①如何对区域目标进行处理；②如何解决大区域长时间任务规划的效率问题，也就是提高规划方法的时间性能。

首先分析卫星轨道六根数及其特点。卫星轨道形状由半长轴a和偏心率e决定，轨道位置由轨道倾角i、升交点赤经Ω和近地点俯角w决定，平近点角M主要决定卫星在轨道内的位置。对于星下点轨迹形状，大多数光学遥感卫星的偏心率e接近0，因此近地点俯角w对星下点轨迹的影响较小。升交点赤经Ω主要决定星下点轨迹的位置，对轨迹的形状没有影响。对星下点轨迹形状影响较大的是半长轴a和轨道倾角i，但大部分光学遥感卫星的半长轴a和轨道倾角i的变化，均保持在一定范围内，相差较小，因此星下点轨迹的形状基本相同。

以美国陆地卫星-5(LandSat-5)为例，图1是其星下点轨迹示意。从图1可见，LandSat-5星下点轨迹有以下特点：在高纬度区域，轨迹呈曲线，而在中纬度和低纬度区域，轨迹基本成直线。中国陆地区域的纬度范围为19°N～53°N，因此LandSat-5星下点轨迹在中国境内的形状大体呈直线。

图1 LandSat-5星下点轨迹Fig.1 LandSat-5 sub-satellite point trace

光学遥感卫星的遥感器类型是可见光遥感器，要求被观测区域有较好的光照条件。因此，光学遥感卫星多采用太阳同步轨道，其降交点地方时多为10：30am前后[13]。该时段处于上午，有较好的光照条件，所以光学遥感卫星均在降轨阶段成像。如上所述，光学遥感卫星在中国纬度范围内成像时，其星下点轨迹在误差允许范围内呈一定角度的直线。

根据星下点轨迹的特点，本文应用近似算法，将二维平面区域转化为一维线状区域，简化研究对象，提高效率，求解过程如图2所示。

图2 成像任务规划模型求解过程Fig.2 Solving process of imaging task scheduling model

1)计算中心纬线

在本文方法中，将待成像区域投影为直线，由于星下点轨迹并不完全为直线，区域离投影线越远，星下点轨迹与轨迹拟合直线的偏差越大，因此，选择区域中心纬线作为投影线，能够减小区域内的点与投影线的距离，提高计算精度。例如，图3为北京市的行政区图，其纬度范围为39.43°N～41.05°N，那么中心纬线为40.24°N。

图3 计算中心纬线和区域线段(北京市)Fig.3 Calculating center latitude and region segment (Beijing)

2)计算区域线段

将光学遥感卫星中国纬度范围内的星下点轨迹所拟合的直线与水平方向的夹角，称为“投影角度”，将待成像区域的所有边界点沿着倾角为投影角度的直线向中心纬线做投影，得到一系列投影点，该系列投影点所在的线段称为“区域线段”，其中最左侧和最右侧的点作为区域线段的边界点。如图3所示，北京区域所有边界点的投影点中，最左侧和最右侧的点依次为A点和B点，线段AB即为区域线段。

3)计算过境线段

光学遥感卫星的观测范围是星下点区域附近具有一定宽度的条带，区域线段与过境条带相交的部分称为“过境线段”。如图4所示，某一时刻的过境条带边界与区域线段AB相交于a1，b1两点，线段a1b1即称为过境线段。根据上文的分析，过境条带的左右两侧边界的形状同星下点轨迹，均近似为直线。因此，过境条带也可以沿倾角为投影角度的直线投影至中心纬线。如果多个过境线段能够覆盖区域线段，那么以上过境线段对应的过境条带可覆盖区域线段对应的待成像区域。

图4 计算过境线段Fig.4 Calculating crossing segment

4)过境线段覆盖区域线段

在一定的时间范围内，光学遥感卫星能够对同一区域实现多次过境，形成多条过境条带，这些过境条带可投影为多条过境线段。要完成对特定区域的全覆盖，须按照一定的规则用得到的过境线段覆盖区域线段。实际上，这是一个一维区间覆盖问题，可用贪心算法快速求解。例如，以过境条带最少为规划指标，可等效于一维区间覆盖问题中用最少的子线段覆盖特定区间的求解问题。解法如下：①起始点T设为区域线段L的左端点，被选取的区域线段的集合M=φ。②寻找所有与起始点T相交的过境线段的集合P。③找出P中右端点经度值最大的过境线段l，M=M∪l。④如果l的右端点经度值大于区域线段L右端点的经度值，则M为最优解集，M中的所有区域线段组成最优解，结束；否则，以l的右端点为起始点T，转至②。

如图5所示，AB是区域线段，1～5是过境线段，按照上述解法进行区间覆盖求解。首先，选择AB的左端点A为起始点，与起始点A相交的过境线段集合是过境线段3和4构成的集合，集合中右端点经度值最大的过境线段是4，因此过境线段4是最优解的第一部分。过境线段4的右端点经度值小于区域线段AB右端点B的经度值，因此以过境线段4的右端点为起始点重复以上过程。

图5 贪心算法解决一维区间覆盖问题Fig.5 Solving one-dimension interval coverage problem by greedy algorithm

5)过境线段还原为过境条带

将得到的最优解集合中的所有过境线段的左、右端点沿投影角度作直线，该直线与待成像区域边界的交点即为过境条带的端点，并根据端点的位置，计算过境条带的起止时间。如图6所示，a1b1为过境线段，分别将左端点a1和右端点b1沿投影角度作直线，根据两条直线与区域边界交点的位置，计算出过境条带的4个顶点的坐标值，就可得到过境条带。

图6 过境线段还原为过境条带Fig.6 Crossing segment converts to crossing strip

4 方法验证与分析

4.1 可行性验证

以我国南方大部分地区作为待成像区域，本文对大区域长时间成像任务规划的可行性，以及通过近似算法得到的条带与真实条带的偏离程度，进行验证分析。这些地区包括浙江、安徽、上海、福建、江苏、广东、湖南、湖北、江西、四川、重庆、云南、贵州、广西、海南(本岛)、香港和澳门，面积约占全国的1/4。假定以2017年1月1日至2017年6月30日为成像时间，以过境条带数最少为任务指标，我国自主研发的环境减灾-1A(HJ-1A)卫星具有较强的侧摆能力，本文选择该卫星作成像任务规划。HJ-1A卫星的轨道参数如表1所示。

表1 HJ-1A卫星轨道参数

4.1.1 成像任务规划结果

用直线拟合HJ-1A星下点轨迹，该卫星在中国纬度范围内星下点轨迹倾角为76.2°，以76.2°为投影角度，按照本文方法做成像任务规划。规划结果由44个条带组成，如图7(a)所示。可见，本文方法规划输出的条带能够覆盖整个待成像区域，说明能够成功完成成像区域覆盖，验证了成像任务规划模型对大区域长时间成像任务规划的可行性。本文方法将星下点轨迹按照直线来近似计算，而星下点轨迹并不完全是直线，因此结果存在一定的偏差。图7(b)是按照星下点轨迹计算得到的条带。对比图7(a)和图7(b)，本文方法得到的条带和实际条带的偏差较小。

表2给出了前4个条带4个顶点的本文方法所得结果与实际的对比。可见，4个顶点中，经度误差均小于0.20°，纬度误差均小于0.10°，说明本文的成像任务规划方法具有较高的准确度。

图7 本文方法输出的过境条带和实际过境条带对比Fig.7 Contrast of crossing strips obtained by this method and accurate crossing strips

Table 2 Vertex positions and errors of crossing strips obtained by this method and accurate crossing strips (°)

4.1.2 误差分析

本文成像任务规划方法采用直线代替星下点轨迹曲线，造成的误差主要有两方面。①如果待成像区域的纬度范围较大，那么星下点轨迹与其拟合的直线的偏差将随之增大，本文方法输出的条带与真实过境条带的位置偏差将提高，所以本文方法对纬度跨度小的地面任务区域精确度较高。②本文方法输出的条带是矩形，条带的左右边界平行，而实际上，由于地球近似为球体，纬度越低的区域，单位经度对应的实际距离越大，因此，在卫星视场角一定的情况下，在北半球，星下点越接近赤道，其扫描线跨越的经度范围越小，造成实际过境条带呈南窄北宽的形状。在实际应用需求中，以上误差主要会造成过境条带之间存在缝隙，使地面任务区域的覆盖率降低。针对这一问题，可通过增加区域线段重叠率的方法解决。实际上，光学遥感卫星对地面覆盖会受到各种不确定性因素的影响，例如任务冲突、天气等，无法对地面任务区域实现完全覆盖也是较为常见的问题。

4.2 时间性能验证

为验证时间性能，将本文方法与文献[3]中提出的规划方法作对比。基于解析法，文献[3]中首先根据地面任务区域和成像卫星的轨道参数，计算过境时间窗，得出所有过境条带；然后根据卫星成像的约束条件，利用智能算法，对得到的过境条带进行筛选和组合，得出最佳的条带组合方案。

选取地面任务区域为矩形，其经度范围为100°～110°，纬度范围为30°～35°。任务时间依次选取为30天、60天和90天。以HJ-1A卫星为例，规划目标为用尽可能少的条带覆盖地面任务区域，同时使得覆盖率尽可能的大。两种方法的规划结果如表3所示。

表3 本文方法和解析法输出结果对比

从表3中可以看出，本文方法和文献[3]中提出的解析法，均能得出成像调度方案，从条带数上看，两种方法得到的条带数一致，说明都能用尽可能少的条带对地面任务区域完成覆盖，能够尽可能少的消耗卫星资源。从耗时上看，本文方法为解析法的5%～11%，说明时间性能较高。这是因为：本文方法将二维平面区域转化为一维线状区域，大大减少了拓扑计算的时间，且利用贪心算法求解一维区间覆盖问题耗时较少。从条带覆盖率上看，本文方法比解析法的略低(4%以内)，这主要是由于近似算法得出的条带组合之间存在缝隙，造成少量地面任务区域未被覆盖。由于绝大部分地面任务区域已经被覆盖，完成了拍摄任务，因此可认为本文方法能够适应实际应用需求。

5 结束语

本文分析了光学遥感卫星轨道及星下点轨迹的特点，得出其在中国纬度范围内星下点轨迹呈直线的结论，并根据这一结论，将待成像的区域和过境条带投影至特定直线，最终完成了成像任务规划。本文方法最大的优点在于：根据星下点轨迹的特点，将二维平面区域映射到一维线状区域，将二维平面覆盖问题转化为一维区间覆盖问题，并通过贪心算法求解，大幅降低了大区域长时间成像任务规划的时间复杂度。验证结果及分析表明，本文方法虽应用近似算法，但准确度较高。另外，采用贪心算法解决一维区间覆盖问题，能够使规划结果具有覆盖率高、重复拍摄率低的优点。

References)

[1] 王沛，谭跃进.卫星对地观测任务规划问题简明综述[J].计算机应用研究，2008，25(10)：2893-2897

Wang Pei， Tan Yuejin. Mission planning problem for earth observing satellites： a survey [J]. Application Research of Computers， 2008， 25(10)： 2893-2897 (in Chinese)

[2]黄瀚，张晓倩.基于图论模型的成像卫星任务规划方法研究[J].桂林航天工业学院学报，2016，21(2)：155-158

Huang Han， Zhang Xiaoqian. Remote sensing satellite task scheduling method based on graphics model [J]. Journal of Guilin University of Aerospace Technology， 2016， 21(2)： 155-158 (in Chinese)

[3]韩琼，章文毅.多星联合成像编程技术研究[J].遥感信息，2013，28(4)：19-23

Han Qiong， Zhang Wenyi. Joint imaging programming of multi-satellites [J]. Remote Sensing Information， 2013， 28(4)： 19-23 (in Chinese)

[4]Gabrel V， Vanderpooten D. Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite [J]. European Journal of Operational Research，2002，139(3)： 533-542

[5]Zufferey N， Amstutz P， Giaccari P. Graph colouring approaches for a satellite range scheduling problem [J]. Journal of Scheduling， 2008， 11(4)： 263-277

[6]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

[7]Marinelli F， Nocella S， Rossi F， et al. A Lagrangian heuristic for satellite range scheduling with resource constraints [J]. Computers & Operations Research， 2011， 38(11)： 1572-1583

[8]Gabrel V. Strengthened 0-1 linear formulation for the daily satellite mission planning [J]. Journal of Combinatorial Optimization， 2006， 11(3)： 341-346

[9]张润.基于重访周期的对地侦察小卫星星座设计[D].西安：西安电子科技大学，2011

Zhang Run.Design of the ground-reconnotired MiniSat constellation based on re-visit cycle [D]. Xi’an： Xi’an Electronic Science and Technology University，2011 (in Chinese)

[10] 沈欣.光学遥感卫星轨道设计若干关键技术研究[D].武汉：武汉大学，2012

Shen Xin. Research on key technologies of orbit design for optical remote sensing satellite [D]. Wuhan： Wuhan University，2012 (in Chinese)

[11]Wolfe W J， Sorensen S E. Three scheduling algorithms applied to the earth observing systems domain [J]. Management Science， 2000， 46(1)： 148-166

[12]汪荣峰.基于多边形布尔运算的卫星区域覆盖分析算法[J].装备学院学报，2016，27(2)：83-87

Wang Rongfeng. Analysis algorithm for satellite regional coverage based on polygonal boolean operation [J]. Journal of Equipment Academy， 2016， 27(2)： 83-87 (in Chinese)

[13]杨维廉.太阳同步回归轨道的长期演变与控制[J].航天器工程，2008，17(2)：26-30

Yang Weilian. Long-term evolution and control for sunsynchronous and recursive orbit [J]. Spacecraft Engineering， 2008， 17(2)：26-30 (in Chinese)

(编辑：夏光)

Region Target Imaging Task Scheduling Method Based on Approximation Algorithm for Optical Remote Sensing Satellite

SHI Liangshu1HUANG Peng2ZHAN Ying1ZHU Zhenglin2MA Guangbin2

(1 China Land Surveying and Planning Institute，Beijing 100081，China) (2 Institute of Remote Sensing and Digital Earth，Chinese Academy of Sciences，Beijing 100094，China)

Most of the imaging task scheduling study objects of optical remote sensing satellite are based on point target. For region target， most of the researches convert them to point target， which has disadvantages of low-precision and low-efficiency. Additionally， solving the problems of long-period scheduling is time-consuming， and large-area and long-period imaging task scheduling is compared with poor performance. In this paper， imaging task scheduling model is built according to constrain conditions， and optical remote sensing satellite orbit and the track of sub-satellite points are induced and analyzed. The projection of track of sub-satellite points is approximately considered as straight line. The model is solved through region target projected to a line，two-dimension surface region converted to one-dimension linear region. The complexity of solving region target problems is reduced significantly. The side swing is handled in one-dimension linear region， and the performance of solving long-period scheduling problem is improved at the same time. The verification results of HJ-1A satellite show that method presented in this paper can solve the large-area and long-period imaging task scheduling problem in a short time.

optical remote sensing satellite； sub-satellite point； imaging task scheduling； approximation algorithm； region target

2017-01-20；

2017-03-16

国家863计划项目(2012AA12A301)

史良树，男，高级工程师，研究方向为土地调查与遥感监测、森林调查与遥感监测。Email：hiliangshu@mail.clspi.org.cn。

V474.2；TP391.9

A

10.3969/j.issn.1673-8748.2017.02.002