改進的遙感衛星成像任務單軌最優團劃分聚類方法

潘 耀，饒啟龍，池忠明，孫凱鵬，何赟晟

(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.