應(yīng)用近似算法的光學(xué)遙感衛(wèi)星區(qū)域目標(biāo)成像任務(wù)規(guī)劃方法

史良樹(shù) 黃鵬 戰(zhàn)鷹 朱政霖 馬廣彬

(1 中國(guó)土地勘測(cè)規(guī)劃院，北京 100081) (2 中國(guó)科學(xué)院遙感與數(shù)字地球研究所，北京 100094)

?

應(yīng)用近似算法的光學(xué)遙感衛(wèi)星區(qū)域目標(biāo)成像任務(wù)規(guī)劃方法

史良樹(shù)1黃鵬2戰(zhàn)鷹1朱政霖2馬廣彬2

(1 中國(guó)土地勘測(cè)規(guī)劃院，北京 100081) (2 中國(guó)科學(xué)院遙感與數(shù)字地球研究所，北京 100094)

光學(xué)遙感衛(wèi)星成像任務(wù)規(guī)劃的研究對(duì)象多以點(diǎn)目標(biāo)為主，對(duì)于區(qū)域目標(biāo)的處理，多是將其轉(zhuǎn)化為點(diǎn)目標(biāo)后求解，因此存在精度不高和效率過(guò)低等問(wèn)題。同時(shí)，還存在對(duì)于長(zhǎng)時(shí)間周期的規(guī)劃問(wèn)題耗時(shí)過(guò)長(zhǎng)，以及大區(qū)域長(zhǎng)時(shí)間任務(wù)規(guī)劃性能較差等問(wèn)題。文章根據(jù)衛(wèi)星成像任務(wù)規(guī)劃的約束條件，建立成像任務(wù)規(guī)劃模型，分析并歸納光學(xué)遙感衛(wèi)星軌道及星下點(diǎn)軌跡的特點(diǎn)，認(rèn)為星下點(diǎn)軌跡在中低緯度區(qū)域的投影可近似認(rèn)為是直線；通過(guò)將區(qū)域目標(biāo)向直線投影，將二維平面區(qū)域轉(zhuǎn)化為一維線狀區(qū)域，對(duì)模型進(jìn)行求解。該方法能大幅降低求解區(qū)域目標(biāo)問(wèn)題的復(fù)雜度，在一維線狀區(qū)域的基礎(chǔ)上對(duì)側(cè)擺進(jìn)行處理，同時(shí)能夠提高長(zhǎng)時(shí)間周期規(guī)劃的性能。利用環(huán)境減災(zāi)-1A(HJ-1A)衛(wèi)星進(jìn)行驗(yàn)證，結(jié)果表明，文章提出的方法能夠在較短的時(shí)間內(nèi)解決大區(qū)域長(zhǎng)時(shí)間成像任務(wù)規(guī)劃問(wèn)題。

光學(xué)遙感衛(wèi)星；星下點(diǎn)；成像任務(wù)規(guī)劃；近似算法；區(qū)域目標(biāo)

1 引言

光學(xué)遙感衛(wèi)星利用遙感器從太空獲取地面影像的技術(shù)稱(chēng)為衛(wèi)星成像技術(shù)[1]，正在氣象、農(nóng)業(yè)和防災(zāi)等領(lǐng)域發(fā)揮著重要作用。衛(wèi)星成像任務(wù)規(guī)劃指對(duì)地面待成像區(qū)域制定拍攝計(jì)劃，合理安排衛(wèi)星成像區(qū)域，確定遙感器開(kāi)關(guān)機(jī)時(shí)間，以充分利用有限的衛(wèi)星資源盡可能多地完成拍攝任務(wù)。衛(wèi)星成像任務(wù)規(guī)劃是衛(wèi)星運(yùn)行控制系統(tǒng)的核心[2]，對(duì)實(shí)現(xiàn)衛(wèi)星成像任務(wù)起決定性作用。

針對(duì)衛(wèi)星成像任務(wù)規(guī)劃技術(shù)，國(guó)內(nèi)外已有大量研究。研究結(jié)果表明，此類(lèi)技術(shù)可分為成像任務(wù)規(guī)劃模型的建立和求解兩部分[3]。其中，常見(jiàn)的成像任務(wù)規(guī)劃模型包括基于圖論、整形規(guī)劃和多維背包問(wèn)題的模型[4-5]；常見(jiàn)的求解算法以啟發(fā)式算法為主，包括遺傳算法、模擬退火算法等[6-7]。上述模型的研究對(duì)象多是基于點(diǎn)目標(biāo)[8]。但是，在實(shí)際情況中，用戶(hù)的任務(wù)請(qǐng)求多為區(qū)域目標(biāo)，例如針對(duì)某個(gè)省、縣等區(qū)域目標(biāo)的成像任務(wù)；另外，當(dāng)拍攝目標(biāo)較大時(shí)，例如森林火災(zāi)、旱澇災(zāi)害等，此類(lèi)目標(biāo)的成像通常無(wú)法通過(guò)成像衛(wèi)星一次拍攝獲取，規(guī)劃時(shí)不能視為點(diǎn)目標(biāo)。因此，針對(duì)區(qū)域目標(biāo)的成像任務(wù)規(guī)劃具有重要意義。目前，針對(duì)區(qū)域目標(biāo)的調(diào)度，通常包括網(wǎng)格點(diǎn)法[9]和解析法[10]。網(wǎng)格點(diǎn)法首先將地面任務(wù)區(qū)域按照一定間隔劃分為一系列網(wǎng)格，將區(qū)域目標(biāo)轉(zhuǎn)化為點(diǎn)目標(biāo)，進(jìn)行處理。該方法的運(yùn)算結(jié)果受網(wǎng)格大小的影響，網(wǎng)格過(guò)大，造成規(guī)劃結(jié)果不準(zhǔn)確；網(wǎng)格過(guò)小，造成運(yùn)算量過(guò)大，效率降低。解析法是通過(guò)衛(wèi)星與地球的幾何拓?fù)潢P(guān)系，獲取條帶與地面任務(wù)區(qū)域的關(guān)系。但是，該方法過(guò)于依賴(lài)二維拓?fù)溆?jì)算，計(jì)算過(guò)境條帶與區(qū)域目標(biāo)的拓?fù)潢P(guān)系時(shí)，算法復(fù)雜度較高，當(dāng)調(diào)度時(shí)間過(guò)長(zhǎng)、地面任務(wù)區(qū)域過(guò)大時(shí)，成像任務(wù)規(guī)劃耗費(fèi)時(shí)間過(guò)長(zhǎng)。此外，針對(duì)點(diǎn)目標(biāo)的規(guī)劃算法，調(diào)度時(shí)間多為一天或幾天[11]，地面任務(wù)區(qū)域多為幾百個(gè)點(diǎn)目標(biāo)，如果是長(zhǎng)時(shí)間周期、大地面任務(wù)區(qū)域的調(diào)度，此類(lèi)規(guī)劃方法耗時(shí)過(guò)長(zhǎng)。

本文根據(jù)光學(xué)遙感衛(wèi)星成像需要滿(mǎn)足的約束條件建立算法模型，然后分析光學(xué)遙感衛(wèi)星軌道及星下點(diǎn)軌跡的特點(diǎn)，在此基礎(chǔ)上應(yīng)用近似算法，針對(duì)區(qū)域目標(biāo)進(jìn)行研究，避開(kāi)時(shí)間復(fù)雜度較高的二維拓?fù)溆?jì)算[12]，可快速解決大區(qū)域長(zhǎng)時(shí)間成像任務(wù)規(guī)劃問(wèn)題。

2 成像任務(wù)規(guī)劃模型的建立

衛(wèi)星成像任務(wù)規(guī)劃是一個(gè)組合優(yōu)化問(wèn)題，其約束條件較為復(fù)雜，考慮到研究對(duì)象是大區(qū)域長(zhǎng)時(shí)間的任務(wù)規(guī)劃，本文對(duì)成像規(guī)劃需要滿(mǎn)足的基本約束條件進(jìn)行歸納和簡(jiǎn)化，并對(duì)規(guī)劃模型進(jìn)行求解。

本文研究的光學(xué)遙感衛(wèi)星成像任務(wù)規(guī)劃模型可以描述為：已知一組光學(xué)遙感衛(wèi)星和一組地面任務(wù)區(qū)域，每顆衛(wèi)星與地面任務(wù)區(qū)域均有一組可視的時(shí)間窗，如何在一定的時(shí)間內(nèi)，對(duì)一系列過(guò)境條帶進(jìn)行合理組合，用盡可能少的衛(wèi)星資源對(duì)地面任務(wù)區(qū)域完成覆蓋。

對(duì)于成像分辨率達(dá)到用戶(hù)需求的一組衛(wèi)星的集合S，以及地面任務(wù)區(qū)域R，約束條件包括以下幾個(gè)方面。

2.1 過(guò)境時(shí)間窗約束

對(duì)于S中的第i顆衛(wèi)星，在時(shí)間段t∈[m1,m2]能夠拍攝到的條帶為Pi,t，該條帶作為規(guī)劃對(duì)象的條件為

(1)

式中：φ為空集。

式(1)表示當(dāng)衛(wèi)星在某個(gè)時(shí)間段的推掃條帶與地面任務(wù)區(qū)域有重疊時(shí)，該條帶才將成為規(guī)劃對(duì)象。對(duì)于不能側(cè)擺的衛(wèi)星，將遙感器視場(chǎng)角覆蓋區(qū)域作為條帶；對(duì)于能夠側(cè)擺的衛(wèi)星，將遙感器通過(guò)不同側(cè)擺角拍攝到的所有區(qū)域均作為條帶。

2.2 條帶重疊率約束

為提高資源利用率，規(guī)劃結(jié)果的條帶組合應(yīng)滿(mǎn)足

(2)

(3)

式中：決策變量xk,t∈{0,1}，xk,t=1時(shí)，表示條帶Pk,t被成像，作為規(guī)劃結(jié)果的條帶之一，xk,t=0時(shí)，表示條帶Pk,t未被成像；k1,k2∈{1,2,…,|S|}；α為最大重疊率；β為最小重疊率。

式(2)是最大重疊率約束，表示規(guī)劃結(jié)果條帶組合的任意2個(gè)條帶，其交集與面積之和的比值，即重疊率不能超過(guò)最大重疊率。式(3)是最小重疊率約束，表示對(duì)于相鄰有重疊的2個(gè)條帶，其重疊率不能低于最小重疊率，增大最小重疊率可減小條帶之間的縫隙，即增大覆蓋率，但會(huì)造成條帶個(gè)數(shù)增多。

2.3 覆蓋率約束

對(duì)于規(guī)劃結(jié)果的條帶組合，要盡可能多地覆蓋地面任務(wù)區(qū)域R，應(yīng)滿(mǎn)足

(4)

式中：c為設(shè)定的覆蓋率。

式(4)表示所有規(guī)劃結(jié)果的條帶，其并集的面積與地面任務(wù)區(qū)域面積的比值應(yīng)大于覆蓋率。對(duì)于大區(qū)域長(zhǎng)時(shí)間的任務(wù)規(guī)劃，任務(wù)時(shí)間較長(zhǎng)，因此能夠有足夠長(zhǎng)的時(shí)間完成對(duì)地面任務(wù)區(qū)域的覆蓋，覆蓋率通常取100%。

基于以上，在一定的資源條件下，以消耗資源盡可能少為目標(biāo)，本文成像任務(wù)規(guī)劃模型的目標(biāo)函數(shù)為

(5)

式(5)表示成像任務(wù)規(guī)劃的目標(biāo)是用盡可能少的條帶覆蓋地面任務(wù)區(qū)域。

3 成像任務(wù)規(guī)劃模型的求解

本文成像任務(wù)規(guī)劃模型要重點(diǎn)解決的問(wèn)題包括：①如何對(duì)區(qū)域目標(biāo)進(jìn)行處理；②如何解決大區(qū)域長(zhǎng)時(shí)間任務(wù)規(guī)劃的效率問(wèn)題，也就是提高規(guī)劃方法的時(shí)間性能。

首先分析衛(wèi)星軌道六根數(shù)及其特點(diǎn)。衛(wèi)星軌道形狀由半長(zhǎng)軸a和偏心率e決定，軌道位置由軌道傾角i、升交點(diǎn)赤經(jīng)Ω和近地點(diǎn)俯角w決定，平近點(diǎn)角M主要決定衛(wèi)星在軌道內(nèi)的位置。對(duì)于星下點(diǎn)軌跡形狀，大多數(shù)光學(xué)遙感衛(wèi)星的偏心率e接近0，因此近地點(diǎn)俯角w對(duì)星下點(diǎn)軌跡的影響較小。升交點(diǎn)赤經(jīng)Ω主要決定星下點(diǎn)軌跡的位置，對(duì)軌跡的形狀沒(méi)有影響。對(duì)星下點(diǎn)軌跡形狀影響較大的是半長(zhǎng)軸a和軌道傾角i，但大部分光學(xué)遙感衛(wèi)星的半長(zhǎng)軸a和軌道傾角i的變化，均保持在一定范圍內(nèi)，相差較小，因此星下點(diǎn)軌跡的形狀基本相同。

以美國(guó)陸地衛(wèi)星-5(LandSat-5)為例，圖1是其星下點(diǎn)軌跡示意。從圖1可見(jiàn)，LandSat-5星下點(diǎn)軌跡有以下特點(diǎn)：在高緯度區(qū)域，軌跡呈曲線，而在中緯度和低緯度區(qū)域，軌跡基本成直線。中國(guó)陸地區(qū)域的緯度范圍為19°N～53°N，因此LandSat-5星下點(diǎn)軌跡在中國(guó)境內(nèi)的形狀大體呈直線。

圖1 LandSat-5星下點(diǎn)軌跡Fig.1 LandSat-5 sub-satellite point trace

光學(xué)遙感衛(wèi)星的遙感器類(lèi)型是可見(jiàn)光遙感器，要求被觀測(cè)區(qū)域有較好的光照條件。因此，光學(xué)遙感衛(wèi)星多采用太陽(yáng)同步軌道，其降交點(diǎn)地方時(shí)多為10：30am前后[13]。該時(shí)段處于上午，有較好的光照條件，所以光學(xué)遙感衛(wèi)星均在降軌階段成像。如上所述，光學(xué)遙感衛(wèi)星在中國(guó)緯度范圍內(nèi)成像時(shí)，其星下點(diǎn)軌跡在誤差允許范圍內(nèi)呈一定角度的直線。

根據(jù)星下點(diǎn)軌跡的特點(diǎn)，本文應(yīng)用近似算法，將二維平面區(qū)域轉(zhuǎn)化為一維線狀區(qū)域，簡(jiǎn)化研究對(duì)象，提高效率，求解過(guò)程如圖2所示。

圖2 成像任務(wù)規(guī)劃模型求解過(guò)程Fig.2 Solving process of imaging task scheduling model

1)計(jì)算中心緯線

在本文方法中，將待成像區(qū)域投影為直線，由于星下點(diǎn)軌跡并不完全為直線，區(qū)域離投影線越遠(yuǎn)，星下點(diǎn)軌跡與軌跡擬合直線的偏差越大，因此，選擇區(qū)域中心緯線作為投影線，能夠減小區(qū)域內(nèi)的點(diǎn)與投影線的距離，提高計(jì)算精度。例如，圖3為北京市的行政區(qū)圖，其緯度范圍為39.43°N～41.05°N，那么中心緯線為40.24°N。

圖3 計(jì)算中心緯線和區(qū)域線段(北京市)Fig.3 Calculating center latitude and region segment (Beijing)

2)計(jì)算區(qū)域線段

將光學(xué)遙感衛(wèi)星中國(guó)緯度范圍內(nèi)的星下點(diǎn)軌跡所擬合的直線與水平方向的夾角，稱(chēng)為“投影角度”，將待成像區(qū)域的所有邊界點(diǎn)沿著傾角為投影角度的直線向中心緯線做投影，得到一系列投影點(diǎn)，該系列投影點(diǎn)所在的線段稱(chēng)為“區(qū)域線段”，其中最左側(cè)和最右側(cè)的點(diǎn)作為區(qū)域線段的邊界點(diǎn)。如圖3所示，北京區(qū)域所有邊界點(diǎn)的投影點(diǎn)中，最左側(cè)和最右側(cè)的點(diǎn)依次為A點(diǎn)和B點(diǎn)，線段AB即為區(qū)域線段。

3)計(jì)算過(guò)境線段

光學(xué)遙感衛(wèi)星的觀測(cè)范圍是星下點(diǎn)區(qū)域附近具有一定寬度的條帶，區(qū)域線段與過(guò)境條帶相交的部分稱(chēng)為“過(guò)境線段”。如圖4所示，某一時(shí)刻的過(guò)境條帶邊界與區(qū)域線段AB相交于a1，b1兩點(diǎn)，線段a1b1即稱(chēng)為過(guò)境線段。根據(jù)上文的分析，過(guò)境條帶的左右兩側(cè)邊界的形狀同星下點(diǎn)軌跡，均近似為直線。因此，過(guò)境條帶也可以沿傾角為投影角度的直線投影至中心緯線。如果多個(gè)過(guò)境線段能夠覆蓋區(qū)域線段，那么以上過(guò)境線段對(duì)應(yīng)的過(guò)境條帶可覆蓋區(qū)域線段對(duì)應(yīng)的待成像區(qū)域。

圖4 計(jì)算過(guò)境線段Fig.4 Calculating crossing segment

4)過(guò)境線段覆蓋區(qū)域線段

在一定的時(shí)間范圍內(nèi)，光學(xué)遙感衛(wèi)星能夠?qū)ν粎^(qū)域?qū)崿F(xiàn)多次過(guò)境，形成多條過(guò)境條帶，這些過(guò)境條帶可投影為多條過(guò)境線段。要完成對(duì)特定區(qū)域的全覆蓋，須按照一定的規(guī)則用得到的過(guò)境線段覆蓋區(qū)域線段。實(shí)際上，這是一個(gè)一維區(qū)間覆蓋問(wèn)題，可用貪心算法快速求解。例如，以過(guò)境條帶最少為規(guī)劃指標(biāo)，可等效于一維區(qū)間覆蓋問(wèn)題中用最少的子線段覆蓋特定區(qū)間的求解問(wèn)題。解法如下：①起始點(diǎn)T設(shè)為區(qū)域線段L的左端點(diǎn)，被選取的區(qū)域線段的集合M=φ。②尋找所有與起始點(diǎn)T相交的過(guò)境線段的集合P。③找出P中右端點(diǎn)經(jīng)度值最大的過(guò)境線段l，M=M∪l。④如果l的右端點(diǎn)經(jīng)度值大于區(qū)域線段L右端點(diǎn)的經(jīng)度值，則M為最優(yōu)解集，M中的所有區(qū)域線段組成最優(yōu)解，結(jié)束；否則，以l的右端點(diǎn)為起始點(diǎn)T，轉(zhuǎn)至②。

如圖5所示，AB是區(qū)域線段，1～5是過(guò)境線段，按照上述解法進(jìn)行區(qū)間覆蓋求解。首先，選擇AB的左端點(diǎn)A為起始點(diǎn)，與起始點(diǎn)A相交的過(guò)境線段集合是過(guò)境線段3和4構(gòu)成的集合，集合中右端點(diǎn)經(jīng)度值最大的過(guò)境線段是4，因此過(guò)境線段4是最優(yōu)解的第一部分。過(guò)境線段4的右端點(diǎn)經(jīng)度值小于區(qū)域線段AB右端點(diǎn)B的經(jīng)度值，因此以過(guò)境線段4的右端點(diǎn)為起始點(diǎn)重復(fù)以上過(guò)程。

圖5 貪心算法解決一維區(qū)間覆蓋問(wèn)題Fig.5 Solving one-dimension interval coverage problem by greedy algorithm

5)過(guò)境線段還原為過(guò)境條帶

將得到的最優(yōu)解集合中的所有過(guò)境線段的左、右端點(diǎn)沿投影角度作直線，該直線與待成像區(qū)域邊界的交點(diǎn)即為過(guò)境條帶的端點(diǎn)，并根據(jù)端點(diǎn)的位置，計(jì)算過(guò)境條帶的起止時(shí)間。如圖6所示，a1b1為過(guò)境線段，分別將左端點(diǎn)a1和右端點(diǎn)b1沿投影角度作直線，根據(jù)兩條直線與區(qū)域邊界交點(diǎn)的位置，計(jì)算出過(guò)境條帶的4個(gè)頂點(diǎn)的坐標(biāo)值，就可得到過(guò)境條帶。

圖6 過(guò)境線段還原為過(guò)境條帶Fig.6 Crossing segment converts to crossing strip

4 方法驗(yàn)證與分析

4.1 可行性驗(yàn)證

以我國(guó)南方大部分地區(qū)作為待成像區(qū)域，本文對(duì)大區(qū)域長(zhǎng)時(shí)間成像任務(wù)規(guī)劃的可行性，以及通過(guò)近似算法得到的條帶與真實(shí)條帶的偏離程度，進(jìn)行驗(yàn)證分析。這些地區(qū)包括浙江、安徽、上海、福建、江蘇、廣東、湖南、湖北、江西、四川、重慶、云南、貴州、廣西、海南(本島)、香港和澳門(mén)，面積約占全國(guó)的1/4。假定以2017年1月1日至2017年6月30日為成像時(shí)間，以過(guò)境條帶數(shù)最少為任務(wù)指標(biāo)，我國(guó)自主研發(fā)的環(huán)境減災(zāi)-1A(HJ-1A)衛(wèi)星具有較強(qiáng)的側(cè)擺能力，本文選擇該衛(wèi)星作成像任務(wù)規(guī)劃。HJ-1A衛(wèi)星的軌道參數(shù)如表1所示。

表1 HJ-1A衛(wèi)星軌道參數(shù)

4.1.1 成像任務(wù)規(guī)劃結(jié)果

用直線擬合HJ-1A星下點(diǎn)軌跡，該衛(wèi)星在中國(guó)緯度范圍內(nèi)星下點(diǎn)軌跡傾角為76.2°，以76.2°為投影角度，按照本文方法做成像任務(wù)規(guī)劃。規(guī)劃結(jié)果由44個(gè)條帶組成，如圖7(a)所示?？梢?jiàn)，本文方法規(guī)劃輸出的條帶能夠覆蓋整個(gè)待成像區(qū)域，說(shuō)明能夠成功完成成像區(qū)域覆蓋，驗(yàn)證了成像任務(wù)規(guī)劃模型對(duì)大區(qū)域長(zhǎng)時(shí)間成像任務(wù)規(guī)劃的可行性。本文方法將星下點(diǎn)軌跡按照直線來(lái)近似計(jì)算，而星下點(diǎn)軌跡并不完全是直線，因此結(jié)果存在一定的偏差。圖7(b)是按照星下點(diǎn)軌跡計(jì)算得到的條帶。對(duì)比圖7(a)和圖7(b)，本文方法得到的條帶和實(shí)際條帶的偏差較小。

表2給出了前4個(gè)條帶4個(gè)頂點(diǎn)的本文方法所得結(jié)果與實(shí)際的對(duì)比?？梢?jiàn)，4個(gè)頂點(diǎn)中，經(jīng)度誤差均小于0.20°，緯度誤差均小于0.10°，說(shuō)明本文的成像任務(wù)規(guī)劃方法具有較高的準(zhǔn)確度。

圖7 本文方法輸出的過(guò)境條帶和實(shí)際過(guò)境條帶對(duì)比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 誤差分析

本文成像任務(wù)規(guī)劃方法采用直線代替星下點(diǎn)軌跡曲線，造成的誤差主要有兩方面。①如果待成像區(qū)域的緯度范圍較大，那么星下點(diǎn)軌跡與其擬合的直線的偏差將隨之增大，本文方法輸出的條帶與真實(shí)過(guò)境條帶的位置偏差將提高，所以本文方法對(duì)緯度跨度小的地面任務(wù)區(qū)域精確度較高。②本文方法輸出的條帶是矩形，條帶的左右邊界平行，而實(shí)際上，由于地球近似為球體，緯度越低的區(qū)域，單位經(jīng)度對(duì)應(yīng)的實(shí)際距離越大，因此，在衛(wèi)星視場(chǎng)角一定的情況下，在北半球，星下點(diǎn)越接近赤道，其掃描線跨越的經(jīng)度范圍越小，造成實(shí)際過(guò)境條帶呈南窄北寬的形狀。在實(shí)際應(yīng)用需求中，以上誤差主要會(huì)造成過(guò)境條帶之間存在縫隙，使地面任務(wù)區(qū)域的覆蓋率降低。針對(duì)這一問(wèn)題，可通過(guò)增加區(qū)域線段重疊率的方法解決。實(shí)際上，光學(xué)遙感衛(wèi)星對(duì)地面覆蓋會(huì)受到各種不確定性因素的影響，例如任務(wù)沖突、天氣等，無(wú)法對(duì)地面任務(wù)區(qū)域?qū)崿F(xiàn)完全覆蓋也是較為常見(jiàn)的問(wèn)題。

4.2 時(shí)間性能驗(yàn)證

為驗(yàn)證時(shí)間性能，將本文方法與文獻(xiàn)[3]中提出的規(guī)劃方法作對(duì)比?；诮馕龇?，文獻(xiàn)[3]中首先根據(jù)地面任務(wù)區(qū)域和成像衛(wèi)星的軌道參數(shù)，計(jì)算過(guò)境時(shí)間窗，得出所有過(guò)境條帶；然后根據(jù)衛(wèi)星成像的約束條件，利用智能算法，對(duì)得到的過(guò)境條帶進(jìn)行篩選和組合，得出最佳的條帶組合方案。

選取地面任務(wù)區(qū)域?yàn)榫匦危浣?jīng)度范圍為100°～110°，緯度范圍為30°～35°。任務(wù)時(shí)間依次選取為30天、60天和90天。以HJ-1A衛(wèi)星為例，規(guī)劃目標(biāo)為用盡可能少的條帶覆蓋地面任務(wù)區(qū)域，同時(shí)使得覆蓋率盡可能的大。兩種方法的規(guī)劃結(jié)果如表3所示。

表3 本文方法和解析法輸出結(jié)果對(duì)比

從表3中可以看出，本文方法和文獻(xiàn)[3]中提出的解析法，均能得出成像調(diào)度方案，從條帶數(shù)上看，兩種方法得到的條帶數(shù)一致，說(shuō)明都能用盡可能少的條帶對(duì)地面任務(wù)區(qū)域完成覆蓋，能夠盡可能少的消耗衛(wèi)星資源。從耗時(shí)上看，本文方法為解析法的5%～11%，說(shuō)明時(shí)間性能較高。這是因?yàn)椋罕疚姆椒▽⒍S平面區(qū)域轉(zhuǎn)化為一維線狀區(qū)域，大大減少了拓?fù)溆?jì)算的時(shí)間，且利用貪心算法求解一維區(qū)間覆蓋問(wèn)題耗時(shí)較少。從條帶覆蓋率上看，本文方法比解析法的略低(4%以?xún)?nèi))，這主要是由于近似算法得出的條帶組合之間存在縫隙，造成少量地面任務(wù)區(qū)域未被覆蓋。由于絕大部分地面任務(wù)區(qū)域已經(jīng)被覆蓋，完成了拍攝任務(wù)，因此可認(rèn)為本文方法能夠適應(yīng)實(shí)際應(yīng)用需求。

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

本文分析了光學(xué)遙感衛(wèi)星軌道及星下點(diǎn)軌跡的特點(diǎn)，得出其在中國(guó)緯度范圍內(nèi)星下點(diǎn)軌跡呈直線的結(jié)論，并根據(jù)這一結(jié)論，將待成像的區(qū)域和過(guò)境條帶投影至特定直線，最終完成了成像任務(wù)規(guī)劃。本文方法最大的優(yōu)點(diǎn)在于：根據(jù)星下點(diǎn)軌跡的特點(diǎn)，將二維平面區(qū)域映射到一維線狀區(qū)域，將二維平面覆蓋問(wèn)題轉(zhuǎn)化為一維區(qū)間覆蓋問(wèn)題，并通過(guò)貪心算法求解，大幅降低了大區(qū)域長(zhǎng)時(shí)間成像任務(wù)規(guī)劃的時(shí)間復(fù)雜度。驗(yàn)證結(jié)果及分析表明，本文方法雖應(yīng)用近似算法，但準(zhǔn)確度較高。另外，采用貪心算法解決一維區(qū)間覆蓋問(wèn)題，能夠使規(guī)劃結(jié)果具有覆蓋率高、重復(fù)拍攝率低的優(yōu)點(diǎn)。

References)

[1] 王沛，譚躍進(jìn).衛(wèi)星對(duì)地觀測(cè)任務(wù)規(guī)劃問(wèn)題簡(jiǎn)明綜述[J].計(jì)算機(jī)應(yīng)用研究，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]黃瀚，張曉倩.基于圖論模型的成像衛(wèi)星任務(wù)規(guī)劃方法研究[J].桂林航天工業(yè)學(xué)院學(xué)報(bào)，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]韓瓊，章文毅.多星聯(lián)合成像編程技術(shù)研究[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]張潤(rùn).基于重訪周期的對(duì)地偵察小衛(wèi)星星座設(shè)計(jì)[D].西安：西安電子科技大學(xué)，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] 沈欣.光學(xué)遙感衛(wèi)星軌道設(shè)計(jì)若干關(guān)鍵技術(shù)研究[D].武漢：武漢大學(xué)，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]汪榮峰.基于多邊形布爾運(yùn)算的衛(wèi)星區(qū)域覆蓋分析算法[J].裝備學(xué)院學(xué)報(bào)，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]楊維廉.太陽(yáng)同步回歸軌道的長(zhǎng)期演變與控制[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

國(guó)家863計(jì)劃項(xiàng)目(2012AA12A301)

史良樹(shù)，男，高級(jí)工程師，研究方向?yàn)橥恋卣{(diào)查與遙感監(jiān)測(cè)、森林調(diào)查與遙感監(jiān)測(cè)。Email：hiliangshu@mail.clspi.org.cn。

V474.2；TP391.9

A

10.3969/j.issn.1673-8748.2017.02.002