改進(jìn)的遙感衛(wèi)星成像任務(wù)單軌最優(yōu)團(tuán)劃分聚類方法

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

(1.上海衛(wèi)星工程研究所，上海 201109；2.上海航天技術(shù)研究院，上海 201109)

0 引言

遙感衛(wèi)星成像任務(wù)規(guī)劃的目標(biāo)類型主要有點(diǎn)目標(biāo)、區(qū)域目標(biāo)。其中，點(diǎn)目標(biāo)的分布具有隨機(jī)性和不均勻性，不適合采用逐個(gè)觀測(cè)的方式，必須先將滿足相關(guān)約束條件、需多次觀測(cè)的點(diǎn)目標(biāo)聚類成能由衛(wèi)星1次成像完成觀測(cè)的聚類任務(wù)，這樣既減少衛(wèi)星載荷頻繁姿態(tài)機(jī)動(dòng)，又能大幅提高衛(wèi)星對(duì)目標(biāo)的觀測(cè)效率[1]。

目前，多數(shù)研究將遙感衛(wèi)星成像任務(wù)聚類問(wèn)題看作是團(tuán)劃分問(wèn)題[2-7]。如：文獻(xiàn)[8]提出了一種基于邊合并的近似團(tuán)劃分方法，該方法能得到團(tuán)劃分的近似最優(yōu)解，計(jì)算效率和收斂性都優(yōu)于遺傳算法和模擬退火算法[9]，是求解團(tuán)劃分問(wèn)題的經(jīng)典方法，但該方法只能隨機(jī)合并一條邊，可能會(huì)造成計(jì)算結(jié)果不明確；文獻(xiàn)[10]提出了一種基于點(diǎn)合并的團(tuán)劃分方法，依據(jù)完全點(diǎn)合并準(zhǔn)則和二分點(diǎn)合并準(zhǔn)則，提高了聚類解的準(zhǔn)確性，但當(dāng)目標(biāo)數(shù)量較多時(shí)，該算法復(fù)雜度將會(huì)很高；文獻(xiàn)[11]提出了一種基于邊點(diǎn)混合合并的團(tuán)劃分方法，在優(yōu)先考慮邊合并的基礎(chǔ)上，再考慮點(diǎn)合并準(zhǔn)則，提高了計(jì)算效率和聚類解的收斂性，但該方法計(jì)算復(fù)雜度高、耗時(shí)長(zhǎng)，不利于星上自主任務(wù)處理；文獻(xiàn)[12]提出了一種單軌最優(yōu)的動(dòng)態(tài)合成方法，考慮了衛(wèi)星單軌側(cè)擺的最大次數(shù)限制，通過(guò)動(dòng)態(tài)回溯的方式尋找最優(yōu)解，無(wú)須循環(huán)迭代，計(jì)算量小，但該方法只能保證每個(gè)觀測(cè)任務(wù)最優(yōu)，無(wú)法保證全局最優(yōu)。

針對(duì)以上任務(wù)聚類方法的不足，本文提出了一種改進(jìn)的遙感衛(wèi)星成像任務(wù)單軌最優(yōu)團(tuán)劃分聚類方法。該方法首先在任務(wù)聚類圖模型的基礎(chǔ)上構(gòu)建權(quán)值矩陣P、收益矩陣M和終點(diǎn)矩陣N，并將衛(wèi)星單軌姿態(tài)機(jī)動(dòng)的次數(shù)與聚類任務(wù)的數(shù)量對(duì)應(yīng)，再通過(guò)循環(huán)遍歷的方式計(jì)算各聚類方案下的總收益，所得總收益最大的方案為最優(yōu)聚類方案。

1 改進(jìn)思路

控制力矩陀螺可實(shí)現(xiàn)衛(wèi)星高精度、全方位三軸快速姿態(tài)機(jī)動(dòng)，已在衛(wèi)星姿態(tài)控制系統(tǒng)中廣泛應(yīng)用。然而，姿態(tài)機(jī)動(dòng)的速度會(huì)隨著控制力矩陀螺的頻繁使用而逐漸減低，因此在衛(wèi)星整個(gè)使用壽命周期內(nèi)，對(duì)控制力矩陀螺在1個(gè)軌道圈次內(nèi)的使用次數(shù)往往有所限制，必須要考慮衛(wèi)星單軌姿態(tài)機(jī)動(dòng)的最大次數(shù)。

本文在聚類圖模型的基礎(chǔ)上[13-14]，考慮衛(wèi)星單軌姿態(tài)機(jī)動(dòng)最大次數(shù)的限制，將姿態(tài)機(jī)動(dòng)的次數(shù)與聚類任務(wù)的數(shù)量對(duì)應(yīng)，并結(jié)合任務(wù)聚類的約束條件[15-16]，在文獻(xiàn)[12]的基礎(chǔ)上，提出了一種改進(jìn)的單軌最優(yōu)團(tuán)劃分聚類方法。

具體改進(jìn)的地方有以下幾方面：

1) 構(gòu)建任務(wù)聚類的圖模型，簡(jiǎn)單直觀地表示各個(gè)點(diǎn)目標(biāo)之間的關(guān)系，對(duì)圖模型中的每一條邊賦權(quán)值，建立權(quán)值矩陣。

2) 將衛(wèi)星姿態(tài)機(jī)動(dòng)的最大次數(shù)與聚類任務(wù)的數(shù)量對(duì)應(yīng)，避免出現(xiàn)由于姿態(tài)機(jī)動(dòng)次數(shù)不足而導(dǎo)致聚類任務(wù)無(wú)法完成觀測(cè)的情況。將衛(wèi)星在2個(gè)觀測(cè)任務(wù)之間進(jìn)行姿態(tài)轉(zhuǎn)換定義為1次姿態(tài)機(jī)動(dòng)，包括側(cè)擺和俯仰，將衛(wèi)星初始姿態(tài)定義為零姿態(tài)。基于此假設(shè)，可將衛(wèi)星單軌姿態(tài)機(jī)動(dòng)的最大次數(shù)與單軌聚類任務(wù)的數(shù)量對(duì)應(yīng)，即聚類任務(wù)的數(shù)量為衛(wèi)星姿態(tài)機(jī)動(dòng)的最大次數(shù)，同時(shí)不排除聚類任務(wù)的數(shù)量小于衛(wèi)星姿態(tài)機(jī)動(dòng)最大次數(shù)的情況。

3) 根據(jù)點(diǎn)目標(biāo)的唯一性原則，以循環(huán)遍歷的方式尋找最優(yōu)解，從而保證最優(yōu)解的準(zhǔn)確性和全局性，避免出現(xiàn)聚類任務(wù)之間存在點(diǎn)目標(biāo)重疊和沖突的情況。

2 改進(jìn)的單軌最優(yōu)團(tuán)劃分聚類方法

聚類任務(wù)的基本參數(shù)定義如下：

1) 收益。聚類任務(wù)中一般都包含多個(gè)優(yōu)先級(jí)不同的點(diǎn)目標(biāo)，因此可將聚類任務(wù)中所有點(diǎn)目標(biāo)的優(yōu)先級(jí)之和作為聚類任務(wù)的收益。

2) 側(cè)擺角。假設(shè)衛(wèi)星對(duì)點(diǎn)目標(biāo)(t1,t2,…,ti)的側(cè)擺角范圍分別為Δθ1,Δθ2,…,Δθi，則當(dāng)點(diǎn)目標(biāo)(t1,t2,…,ti)可聚類生成聚類任務(wù)cj時(shí)，cj的可用側(cè)擺角范圍Δβj=Δθ1∩Δθ2∩…∩Δθi，且Δβj≠?。為簡(jiǎn)化計(jì)算，取Δβj的平均值作為衛(wèi)星對(duì)聚類任務(wù)cj的實(shí)際側(cè)擺角，即衛(wèi)星對(duì)cj的實(shí)際側(cè)擺角βj=(max(Δβj)+min(Δβj))/2。

3) 可見(jiàn)時(shí)間窗口。假設(shè)衛(wèi)星對(duì)點(diǎn)目標(biāo)(t1,t2,…,ti)的可見(jiàn)時(shí)間窗口分別為[Ts1,Te1],[Ts2,Te2],…,[Tsi,Tei]，則當(dāng)點(diǎn)目標(biāo)(t1,t2,…,ti)可聚類生成聚類任務(wù)cj時(shí)，對(duì)cj的可見(jiàn)時(shí)間窗口為T(mén)wj=[Ts1,Te1]∩[Ts2,Te2]∩…∩[Tsi,Tei]，且Twj≠?。

其中，側(cè)擺角和可見(jiàn)時(shí)間窗口為任務(wù)聚類時(shí)需要考慮的主要約束條件。

本文提出的改進(jìn)的遙感衛(wèi)星成像任務(wù)單軌最優(yōu)團(tuán)劃分聚類方法的具體步驟如下：

設(shè)待聚類的點(diǎn)目標(biāo)集合Tpoint={t1,t2,…,tn}；點(diǎn)目標(biāo)的優(yōu)先級(jí)集合p={p1,p2,…,pn}，n為點(diǎn)目標(biāo)的數(shù)量；聚類任務(wù)集合Ccluster={c1,c2,…,cm}，m為聚類任務(wù)的數(shù)量；衛(wèi)星單軌姿態(tài)機(jī)動(dòng)的最大次數(shù)為r，r≥m。

1) 對(duì)圖模型中的每條邊賦權(quán)值，邊的權(quán)值為邊兩端點(diǎn)目標(biāo)的優(yōu)先級(jí)之和。

2) 根據(jù)圖模型中每條邊的權(quán)值，所構(gòu)建的權(quán)值矩陣為

(1)

式中：pii為點(diǎn)目標(biāo)ti的優(yōu)先級(jí)；pij為ti和tj構(gòu)成的邊的權(quán)值，若pij=0，表明ti和tj之間不滿足聚類約束條件；為避免重復(fù)計(jì)算，P對(duì)角線左下角元素全為0。

3) 考慮到衛(wèi)星單軌姿態(tài)機(jī)動(dòng)的最大次數(shù)限制，聚類任務(wù)的數(shù)量就是衛(wèi)星單軌姿態(tài)機(jī)動(dòng)的次數(shù)。由P依次計(jì)算每個(gè)聚類任務(wù)所有可能的最優(yōu)聚類方案，生成對(duì)應(yīng)的M和N。

(2)

(3)

式(2)和式(3)中：Mj為第j個(gè)聚類任務(wù)的收益矩陣，Mj中的元素Mj(i)為第j個(gè)聚類任務(wù)最早從點(diǎn)目標(biāo)ti開(kāi)始的最優(yōu)聚類方案的收益，第j個(gè)聚類任務(wù)最早應(yīng)從點(diǎn)目標(biāo)tj開(kāi)始，將前j-1個(gè)點(diǎn)目標(biāo)t1,t2,…,tj-1預(yù)留給前j-1個(gè)聚類任務(wù)；Nj為第j個(gè)聚類任務(wù)的終點(diǎn)矩陣，Nj中的元素Nj(i)為第j個(gè)聚類任務(wù)從點(diǎn)目標(biāo)ti開(kāi)始的最優(yōu)聚類方案的終點(diǎn)目標(biāo)序號(hào)。

4) 通過(guò)循環(huán)遍歷的方式尋找最優(yōu)解。改進(jìn)的單軌最優(yōu)團(tuán)劃分聚類方法流程如圖1所示。

圖1 改進(jìn)的單軌最優(yōu)團(tuán)劃分聚類方法流程圖Fig.1 Flowchart of improved clustering method based on best clique partition in single orbit

3 仿真分析

利用Matlab和STK軟件對(duì)本文改進(jìn)方法進(jìn)行仿真驗(yàn)證。

3.1 仿真條件設(shè)定

根據(jù)衛(wèi)星的軌道周期，選取1個(gè)軌道圈次的時(shí)間為仿真場(chǎng)景時(shí)間。仿真開(kāi)始時(shí)間為2016年3月23日03：41：17(UTCG)，仿真結(jié)束時(shí)間為2016年3月23日05：28：32(UTCG)。用于仿真的遙感衛(wèi)星信息見(jiàn)表1。

表1 遙感衛(wèi)星信息

考慮單個(gè)軌道圈次內(nèi)的任務(wù)聚類問(wèn)題，隨機(jī)選取18個(gè)點(diǎn)目標(biāo)。這些點(diǎn)目標(biāo)雖然是隨機(jī)生成的，但基本上分布在衛(wèi)星的星下點(diǎn)軌跡兩側(cè)，這樣設(shè)計(jì)符合工程實(shí)際。

利用STK軟件計(jì)算衛(wèi)星對(duì)點(diǎn)目標(biāo)的可見(jiàn)時(shí)間窗口和可用觀測(cè)角度，結(jié)果見(jiàn)表2。

表2 衛(wèi)星對(duì)點(diǎn)目標(biāo)的訪問(wèn)信息

3.2 仿真結(jié)果及分析

由表2構(gòu)建目標(biāo)聚類圖模型，模型如圖3所示。圖中每1個(gè)頂點(diǎn)代表1個(gè)點(diǎn)目標(biāo)，如果2個(gè)頂點(diǎn)之間存在邊，則表明這2個(gè)點(diǎn)目標(biāo)可聚類生成1個(gè)聚類任務(wù)。

多個(gè)頂點(diǎn)可聚類生成1個(gè)聚類任務(wù)的充分必要條件為這幾個(gè)頂點(diǎn)在圖模型中可構(gòu)成1個(gè)團(tuán)(即任意2個(gè)不同頂點(diǎn)之間都存在邊)。

圖3 目標(biāo)聚類圖模型Fig.3 Clustering graph model of spot target

對(duì)圖3中的每條邊賦權(quán)值，構(gòu)建的權(quán)值矩陣為

考慮到衛(wèi)星單軌最多有4次姿態(tài)機(jī)動(dòng)的能力，由P計(jì)算每個(gè)聚類任務(wù)的M和N，為

通過(guò)循環(huá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個(gè)聚類任務(wù)為(t2,t3,t4)，收益為18；第2個(gè)聚類任務(wù)為(t5,t6)，收益為16；第3個(gè)聚類任務(wù)為(t7,t8,t11)，收益為27；第4個(gè)聚類任務(wù)為(t12,t13,t14)，收益為24。將衛(wèi)星沿星下點(diǎn)軌跡方向向左側(cè)擺的角度定義為正，向右側(cè)擺的角度定義為負(fù)，最終得到的單軌最優(yōu)聚類方案，見(jiàn)表3。

從表3可知：采用本文改進(jìn)的聚類方法，得到的最優(yōu)聚類方案中共有4個(gè)聚類任務(wù)，包含了11個(gè)點(diǎn)目標(biāo)，總收益為85。其中：點(diǎn)目標(biāo)(t1,t9,t10)由于不滿足側(cè)擺角約束和姿態(tài)調(diào)整時(shí)間約束而無(wú)法觀測(cè)；點(diǎn)目標(biāo)(t15,t16,t17,t18)由于其構(gòu)成的聚類任務(wù)的最大收益小于(t5,t6)的收益，考慮到衛(wèi)星單軌最多只有4次姿態(tài)機(jī)動(dòng)的能力，無(wú)法完成觀測(cè)。

表3 單軌最優(yōu)聚類方案

為驗(yàn)證本文設(shè)計(jì)的聚類算法，同樣以表2中的18個(gè)點(diǎn)目標(biāo)為例，采用文獻(xiàn)[12]中動(dòng)態(tài)回溯的方法求解聚類方案，具體過(guò)程為：從M1中的最大值出發(fā)，得M1(7)=27，N1(7)=11；第1個(gè)聚類任務(wù)的終點(diǎn)為11，選取M2(12)～M2(18)中的最大值，得M2(12)=24，N2(12)=14；第2個(gè)聚類任務(wù)的終點(diǎn)為14，選取M3(15)～M3(18)中的最大值，得M3(15)=10，N3(15)=17；第3個(gè)聚類任務(wù)的終點(diǎn)為17，將M4(18)作為第4個(gè)聚類任務(wù)，得M4(18)=3，N4(18)=18。最終聚類結(jié)果見(jiàn)表4。

表4 采用文獻(xiàn)[12]方法得到的聚類方案

將本文聚類方法與文獻(xiàn)[12]方法進(jìn)行比較，結(jié)果見(jiàn)表5。從表可見(jiàn)：本文方法在聚類任務(wù)數(shù)量和覆蓋點(diǎn)目標(biāo)數(shù)量上與文獻(xiàn)[12]方法相差不大，但在聚類方案的總收益、優(yōu)先級(jí)≥6的點(diǎn)目標(biāo)數(shù)量方面，本文方法明顯優(yōu)于文獻(xiàn)[12]方法。文獻(xiàn)[12]方法得到的聚類方案總收益為64，優(yōu)先級(jí)≥6的點(diǎn)目標(biāo)數(shù)量為6，而采用本文方法得到的聚類方案總收益為85，提高了21，且優(yōu)先級(jí)≥6的點(diǎn)目標(biāo)數(shù)量達(dá)到了11個(gè)，比文獻(xiàn)[12]方法多5個(gè)。

表5 本文方法與文獻(xiàn)[12]方法聚類結(jié)果比較

文獻(xiàn)[12]采用動(dòng)態(tài)回溯的方法，從第1個(gè)聚類任務(wù)中收益最大的方案出發(fā)，即從點(diǎn)目標(biāo)t7開(kāi)始，導(dǎo)致點(diǎn)目標(biāo)(t1～t6)無(wú)法觀測(cè)；求得的最優(yōu)解不具有全局性，只能保證局部最優(yōu)，導(dǎo)致最終得到的總收益不高。而本文改進(jìn)的最優(yōu)聚類方法以總收益最大為優(yōu)化目標(biāo)，通過(guò)遍歷的方式，保證了聚類方案中盡可能覆蓋優(yōu)先級(jí)較大的點(diǎn)目標(biāo)，在滿足姿態(tài)機(jī)動(dòng)次數(shù)的約束下，使聚類方案總收益最大。

4 結(jié)束語(yǔ)

本文研究了遙感衛(wèi)星成像任務(wù)處理中的點(diǎn)目標(biāo)聚類問(wèn)題，根據(jù)工程應(yīng)用實(shí)際，考慮了控制力矩陀螺的使用次數(shù)限制，設(shè)計(jì)了一種改進(jìn)的單軌最優(yōu)團(tuán)劃分聚類方法，具體改進(jìn)的地方有：1)構(gòu)建任務(wù)聚類的圖模型，采用矩陣表示的方法可簡(jiǎn)單直觀地描述成像點(diǎn)目標(biāo)之間的關(guān)系；2)將衛(wèi)星姿態(tài)機(jī)動(dòng)的最大次數(shù)與聚類任務(wù)的數(shù)量對(duì)應(yīng)，避免出現(xiàn)由于姿態(tài)機(jī)動(dòng)次數(shù)不足而導(dǎo)致聚類任務(wù)無(wú)法完成觀測(cè)的情況；3)根據(jù)點(diǎn)目標(biāo)的唯一性原則，以循環(huán)遍歷的方式尋找最優(yōu)解，從而保證最優(yōu)解的準(zhǔn)確性和全局性，避免出現(xiàn)聚類任務(wù)之間存在點(diǎn)目標(biāo)重疊和沖突的情況。仿真結(jié)果表明：該方法能有效解決遙感衛(wèi)星成像任務(wù)的聚類問(wèn)題，明顯提高了衛(wèi)星對(duì)點(diǎn)目標(biāo)的觀測(cè)效率，滿足多目標(biāo)觀測(cè)等成像需求，有利于實(shí)現(xiàn)遙感衛(wèi)星的自主任務(wù)規(guī)劃，提高衛(wèi)星的自主管控能力。研究結(jié)果可為遙感衛(wèi)星自主任務(wù)規(guī)劃提供參考。

本文提出的改進(jìn)方法適用于點(diǎn)目標(biāo)數(shù)量較少的情況，當(dāng)目標(biāo)數(shù)量達(dá)到幾百甚至幾千個(gè)時(shí)，通過(guò)循環(huán)遍歷的方法將會(huì)增大算法的計(jì)算量，不利于星上任務(wù)處理。在衛(wèi)星工程中，對(duì)采用控制力矩陀螺進(jìn)行姿態(tài)控制的衛(wèi)星來(lái)說(shuō)，該方法能夠有效地解決衛(wèi)星對(duì)成像任務(wù)的聚類問(wèn)題?？紤]到目前大多數(shù)衛(wèi)星都具有俯仰方向姿態(tài)機(jī)動(dòng)的能力，后續(xù)將進(jìn)一步求解衛(wèi)星對(duì)聚類任務(wù)進(jìn)行成像時(shí)的俯仰角。

[1] 陳占勝. 浦江一號(hào)衛(wèi)星的創(chuàng)新與實(shí)踐[J].上海航天, 2016, 33(3): 1-10.

[2] 李麗, 魏少軍, 楊之廉. 基于圖的可測(cè)性算子資源分配算法[J].清華大學(xué)學(xué)報(bào), 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] 張魯峰, 何連躍, 李思昆. 基于優(yōu)化合并準(zhǔn)則的團(tuán)劃分算法[J].電子學(xué)報(bào), 2001, 29(8): 1104-1106.

[11] 許語(yǔ)拉. 衛(wèi)星成像偵察任務(wù)聚類方法研究[D].長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué), 2010.

[12] 白保存. 考慮任務(wù)合成的成像衛(wèi)星調(diào)度模型與優(yōu)化算法研究[D].長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué), 2008.

[13] 郝會(huì)成. 敏捷衛(wèi)星任務(wù)規(guī)劃問(wèn)題建模及求解方法研究[D].哈爾濱:哈爾濱工業(yè)大學(xué), 2013.

[14] 郭雷. 敏捷衛(wèi)星調(diào)度問(wèn)題關(guān)鍵技術(shù)研究[D]. 武漢:武漢大學(xué), 2015.

[15] 郭浩, 伍國(guó)華, 邱滌珊. 敏捷成像衛(wèi)星密集任務(wù)聚類方法[J]. 系統(tǒng)工程與電子技術(shù), 2012, 34(5): 931-935.

[16] 伍國(guó)華, 馬滿好, 王慧林, 等. 基于任務(wù)聚類的多星觀測(cè)調(diào)度方法[J]. 航空學(xué)報(bào), 2011, 32(7): 1275-1282.