改进的遥感卫星成像任务单轨最优团划分聚类方法

潘 耀，饶启龙，池忠明，孙凯鹏，何赟晟

(1.上海卫星工程研究所，上海 201109；2.上海航天技术研究院，上海 201109)

0 引言

遥感卫星成像任务规划的目标类型主要有点目标、区域目标。其中，点目标的分布具有随机性和不均匀性，不适合采用逐个观测的方式，必须先将满足相关约束条件、需多次观测的点目标聚类成能由卫星1次成像完成观测的聚类任务，这样既减少卫星载荷频繁姿态机动，又能大幅提高卫星对目标的观测效率[1]。

目前，多数研究将遥感卫星成像任务聚类问题看作是团划分问题[2-7]。如：文献[8]提出了一种基于边合并的近似团划分方法，该方法能得到团划分的近似最优解，计算效率和收敛性都优于遗传算法和模拟退火算法[9]，是求解团划分问题的经典方法，但该方法只能随机合并一条边，可能会造成计算结果不明确；文献[10]提出了一种基于点合并的团划分方法，依据完全点合并准则和二分点合并准则，提高了聚类解的准确性，但当目标数量较多时，该算法复杂度将会很高；文献[11]提出了一种基于边点混合合并的团划分方法，在优先考虑边合并的基础上，再考虑点合并准则，提高了计算效率和聚类解的收敛性，但该方法计算复杂度高、耗时长，不利于星上自主任务处理；文献[12]提出了一种单轨最优的动态合成方法，考虑了卫星单轨侧摆的最大次数限制，通过动态回溯的方式寻找最优解，无须循环迭代，计算量小，但该方法只能保证每个观测任务最优，无法保证全局最优。

针对以上任务聚类方法的不足，本文提出了一种改进的遥感卫星成像任务单轨最优团划分聚类方法。该方法首先在任务聚类图模型的基础上构建权值矩阵P、收益矩阵M和终点矩阵N，并将卫星单轨姿态机动的次数与聚类任务的数量对应，再通过循环遍历的方式计算各聚类方案下的总收益，所得总收益最大的方案为最优聚类方案。

1 改进思路

控制力矩陀螺可实现卫星高精度、全方位三轴快速姿态机动，已在卫星姿态控制系统中广泛应用。然而，姿态机动的速度会随着控制力矩陀螺的频繁使用而逐渐减低，因此在卫星整个使用寿命周期内，对控制力矩陀螺在1个轨道圈次内的使用次数往往有所限制，必须要考虑卫星单轨姿态机动的最大次数。

本文在聚类图模型的基础上[13-14]，考虑卫星单轨姿态机动最大次数的限制，将姿态机动的次数与聚类任务的数量对应，并结合任务聚类的约束条件[15-16]，在文献[12]的基础上，提出了一种改进的单轨最优团划分聚类方法。

具体改进的地方有以下几方面：

1) 构建任务聚类的图模型，简单直观地表示各个点目标之间的关系，对图模型中的每一条边赋权值，建立权值矩阵。

2) 将卫星姿态机动的最大次数与聚类任务的数量对应，避免出现由于姿态机动次数不足而导致聚类任务无法完成观测的情况。将卫星在2个观测任务之间进行姿态转换定义为1次姿态机动，包括侧摆和俯仰，将卫星初始姿态定义为零姿态。基于此假设，可将卫星单轨姿态机动的最大次数与单轨聚类任务的数量对应，即聚类任务的数量为卫星姿态机动的最大次数，同时不排除聚类任务的数量小于卫星姿态机动最大次数的情况。

3) 根据点目标的唯一性原则，以循环遍历的方式寻找最优解，从而保证最优解的准确性和全局性，避免出现聚类任务之间存在点目标重叠和冲突的情况。

2 改进的单轨最优团划分聚类方法

聚类任务的基本参数定义如下：

1) 收益。聚类任务中一般都包含多个优先级不同的点目标，因此可将聚类任务中所有点目标的优先级之和作为聚类任务的收益。

2) 侧摆角。假设卫星对点目标(t1,t2,…,ti)的侧摆角范围分别为Δθ1,Δθ2,…,Δθi，则当点目标(t1,t2,…,ti)可聚类生成聚类任务cj时，cj的可用侧摆角范围Δβj=Δθ1∩Δθ2∩…∩Δθi，且Δβj≠∅。为简化计算，取Δβj的平均值作为卫星对聚类任务cj的实际侧摆角，即卫星对cj的实际侧摆角βj=(max(Δβj)+min(Δβj))/2。

3) 可见时间窗口。假设卫星对点目标(t1,t2,…,ti)的可见时间窗口分别为[Ts1,Te1],[Ts2,Te2],…,[Tsi,Tei]，则当点目标(t1,t2,…,ti)可聚类生成聚类任务cj时，对cj的可见时间窗口为Twj=[Ts1,Te1]∩[Ts2,Te2]∩…∩[Tsi,Tei]，且Twj≠∅。

其中，侧摆角和可见时间窗口为任务聚类时需要考虑的主要约束条件。

本文提出的改进的遥感卫星成像任务单轨最优团划分聚类方法的具体步骤如下：

设待聚类的点目标集合Tpoint={t1,t2,…,tn}；点目标的优先级集合p={p1,p2,…,pn}，n为点目标的数量；聚类任务集合Ccluster={c1,c2,…,cm}，m为聚类任务的数量；卫星单轨姿态机动的最大次数为r，r≥m。

1) 对图模型中的每条边赋权值，边的权值为边两端点目标的优先级之和。

2) 根据图模型中每条边的权值，所构建的权值矩阵为

(1)

式中：pii为点目标ti的优先级；pij为ti和tj构成的边的权值，若pij=0，表明ti和tj之间不满足聚类约束条件；为避免重复计算，P对角线左下角元素全为0。

3) 考虑到卫星单轨姿态机动的最大次数限制，聚类任务的数量就是卫星单轨姿态机动的次数。由P依次计算每个聚类任务所有可能的最优聚类方案，生成对应的M和N。

(2)

(3)

式(2)和式(3)中：Mj为第j个聚类任务的收益矩阵，Mj中的元素Mj(i)为第j个聚类任务最早从点目标ti开始的最优聚类方案的收益，第j个聚类任务最早应从点目标tj开始，将前j-1个点目标t1,t2,…,tj-1预留给前j-1个聚类任务；Nj为第j个聚类任务的终点矩阵，Nj中的元素Nj(i)为第j个聚类任务从点目标ti开始的最优聚类方案的终点目标序号。

4) 通过循环遍历的方式寻找最优解。改进的单轨最优团划分聚类方法流程如图1所示。

图1 改进的单轨最优团划分聚类方法流程图Fig.1 Flowchart of improved clustering method based on best clique partition in single orbit

3 仿真分析

利用Matlab和STK软件对本文改进方法进行仿真验证。

3.1 仿真条件设定

根据卫星的轨道周期，选取1个轨道圈次的时间为仿真场景时间。仿真开始时间为2016年3月23日03：41：17(UTCG)，仿真结束时间为2016年3月23日05：28：32(UTCG)。用于仿真的遥感卫星信息见表1。

表1 遥感卫星信息

考虑单个轨道圈次内的任务聚类问题，随机选取18个点目标。这些点目标虽然是随机生成的，但基本上分布在卫星的星下点轨迹两侧，这样设计符合工程实际。

利用STK软件计算卫星对点目标的可见时间窗口和可用观测角度，结果见表2。

表2 卫星对点目标的访问信息

3.2 仿真结果及分析

由表2构建目标聚类图模型，模型如图3所示。图中每1个顶点代表1个点目标，如果2个顶点之间存在边，则表明这2个点目标可聚类生成1个聚类任务。

多个顶点可聚类生成1个聚类任务的充分必要条件为这几个顶点在图模型中可构成1个团(即任意2个不同顶点之间都存在边)。

图3 目标聚类图模型Fig.3 Clustering graph model of spot target

对图3中的每条边赋权值，构建的权值矩阵为

考虑到卫星单轨最多有4次姿态机动的能力，由P计算每个聚类任务的M和N，为

通过循环遍历的方法求得收益最大的解为：M1(2)=18，N1(2)=4；M2(5)=16，N2(5)=6；M3(7)=27，N3(7)=11；M4(12)=24，N4(12)=14。第1个聚类任务为(t2,t3,t4)，收益为18；第2个聚类任务为(t5,t6)，收益为16；第3个聚类任务为(t7,t8,t11)，收益为27；第4个聚类任务为(t12,t13,t14)，收益为24。将卫星沿星下点轨迹方向向左侧摆的角度定义为正，向右侧摆的角度定义为负，最终得到的单轨最优聚类方案，见表3。

从表3可知：采用本文改进的聚类方法，得到的最优聚类方案中共有4个聚类任务，包含了11个点目标，总收益为85。其中：点目标(t1,t9,t10)由于不满足侧摆角约束和姿态调整时间约束而无法观测；点目标(t15,t16,t17,t18)由于其构成的聚类任务的最大收益小于(t5,t6)的收益，考虑到卫星单轨最多只有4次姿态机动的能力，无法完成观测。

表3 单轨最优聚类方案

为验证本文设计的聚类算法，同样以表2中的18个点目标为例，采用文献[12]中动态回溯的方法求解聚类方案，具体过程为：从M1中的最大值出发，得M1(7)=27，N1(7)=11；第1个聚类任务的终点为11，选取M2(12)～M2(18)中的最大值，得M2(12)=24，N2(12)=14；第2个聚类任务的终点为14，选取M3(15)～M3(18)中的最大值，得M3(15)=10，N3(15)=17；第3个聚类任务的终点为17，将M4(18)作为第4个聚类任务，得M4(18)=3，N4(18)=18。最终聚类结果见表4。

表4 采用文献[12]方法得到的聚类方案

将本文聚类方法与文献[12]方法进行比较，结果见表5。从表可见：本文方法在聚类任务数量和覆盖点目标数量上与文献[12]方法相差不大，但在聚类方案的总收益、优先级≥6的点目标数量方面，本文方法明显优于文献[12]方法。文献[12]方法得到的聚类方案总收益为64，优先级≥6的点目标数量为6，而采用本文方法得到的聚类方案总收益为85，提高了21，且优先级≥6的点目标数量达到了11个，比文献[12]方法多5个。

表5 本文方法与文献[12]方法聚类结果比较

文献[12]采用动态回溯的方法，从第1个聚类任务中收益最大的方案出发，即从点目标t7开始，导致点目标(t1～t6)无法观测；求得的最优解不具有全局性，只能保证局部最优，导致最终得到的总收益不高。而本文改进的最优聚类方法以总收益最大为优化目标，通过遍历的方式，保证了聚类方案中尽可能覆盖优先级较大的点目标，在满足姿态机动次数的约束下，使聚类方案总收益最大。

4 结束语

本文研究了遥感卫星成像任务处理中的点目标聚类问题，根据工程应用实际，考虑了控制力矩陀螺的使用次数限制，设计了一种改进的单轨最优团划分聚类方法，具体改进的地方有：1)构建任务聚类的图模型，采用矩阵表示的方法可简单直观地描述成像点目标之间的关系；2)将卫星姿态机动的最大次数与聚类任务的数量对应，避免出现由于姿态机动次数不足而导致聚类任务无法完成观测的情况；3)根据点目标的唯一性原则，以循环遍历的方式寻找最优解，从而保证最优解的准确性和全局性，避免出现聚类任务之间存在点目标重叠和冲突的情况。仿真结果表明：该方法能有效解决遥感卫星成像任务的聚类问题，明显提高了卫星对点目标的观测效率，满足多目标观测等成像需求，有利于实现遥感卫星的自主任务规划，提高卫星的自主管控能力。研究结果可为遥感卫星自主任务规划提供参考。

本文提出的改进方法适用于点目标数量较少的情况，当目标数量达到几百甚至几千个时，通过循环遍历的方法将会增大算法的计算量，不利于星上任务处理。在卫星工程中，对采用控制力矩陀螺进行姿态控制的卫星来说，该方法能够有效地解决卫星对成像任务的聚类问题。考虑到目前大多数卫星都具有俯仰方向姿态机动的能力，后续将进一步求解卫星对聚类任务进行成像时的俯仰角。

[1] 陈占胜. 浦江一号卫星的创新与实践[J].上海航天, 2016, 33(3): 1-10.

[2] 李丽, 魏少军, 杨之廉. 基于图的可测性算子资源分配算法[J].清华大学学报, 1999, 39(增刊1): 42-45.

[3] WANG H S. A two phase ant colony algorithm for multi-echelon defective supply chain network design[J]. European Journal of Operational Research, 2009, 192(1): 243-252.

[4] BRUSCO M, KOHN H F. Clustering qualitative data based on binary equivalence relations: a neighborhood search heuristic for the clique partitioning problem [J]. Psychometrika, 2009, 74(4): 685-703.

[5] KIM J T, SHIN D R. New efficient clique partitioning algorithm for register-transfer synthesis of data paths [J]. Journal Korean Physical Society, 2002, 40: 754-758.

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

[7] WOLFE W J, SORENSEN S E. Three scheduling algorithms applied to the earth observing systems domain [J]. Management Science, 2000, 46(1): 148-168.

[8] TSENG C J, SIEWIOREK D P. Automated synthesis of data paths in digital systems [J]. IEEE Trans, 2006, 5(3): 379-395.

[9] MANDAL C A,CHAKRABATI P P，GHOES S. Allocation and binding for data path synthesis using a genetic algorithm approach[C]// Proc.IEEE VLSI

Design, 1996: 122.

[10] 张鲁峰, 何连跃, 李思昆. 基于优化合并准则的团划分算法[J].电子学报, 2001, 29(8): 1104-1106.

[11] 许语拉. 卫星成像侦察任务聚类方法研究[D].长沙:国防科学技术大学, 2010.

[12] 白保存. 考虑任务合成的成像卫星调度模型与优化算法研究[D].长沙：国防科学技术大学, 2008.

[13] 郝会成. 敏捷卫星任务规划问题建模及求解方法研究[D].哈尔滨:哈尔滨工业大学, 2013.

[14] 郭雷. 敏捷卫星调度问题关键技术研究[D]. 武汉:武汉大学, 2015.

[15] 郭浩, 伍国华, 邱涤珊. 敏捷成像卫星密集任务聚类方法[J]. 系统工程与电子技术, 2012, 34(5): 931-935.

[16] 伍国华, 马满好, 王慧林, 等. 基于任务聚类的多星观测调度方法[J]. 航空学报, 2011, 32(7): 1275-1282.