章登義 王 爭 蔡 波,2*

1(武漢大學(xué)計(jì)算機(jī)學(xué)院 湖北 武漢 430072) 2(武漢大學(xué)信息中心 湖北 武漢 430072)

實(shí)際復(fù)雜約束條件下多星區(qū)域覆蓋優(yōu)化算法

章登義1王 爭1蔡 波1,2*

1(武漢大學(xué)計(jì)算機(jī)學(xué)院 湖北 武漢 430072)2(武漢大學(xué)信息中心 湖北 武漢 430072)

利用多星協(xié)同對大面積區(qū)域成像偵測，要求在最短的時(shí)間內(nèi)完成對給定目標(biāo)區(qū)域的完全覆蓋，得到衛(wèi)星每次過境最優(yōu)側(cè)視觀測方案?，F(xiàn)有覆蓋算法具低效耗時(shí)技術(shù)瓶頸，有空間覆蓋率及時(shí)效性局限。充分利用衛(wèi)星每次過境觀測機(jī)會(huì)，綜合考慮相機(jī)分辨率、太陽高度角、地面精度等約束條件，依據(jù)不同衛(wèi)星側(cè)擺能力、傳感器可視性能以及衛(wèi)星軌道參數(shù)特征，對區(qū)域目標(biāo)進(jìn)行量化覆蓋分析，建立網(wǎng)格劃分模型，提出基于一次覆蓋策略的覆蓋優(yōu)化算法。該算法能適應(yīng)實(shí)際復(fù)雜約束條件，在實(shí)際問題規(guī)模下，具有良好的效率，能滿足工業(yè)精度要求。在仿真應(yīng)用中檢驗(yàn)了該算法的有效性和適應(yīng)性。

成像衛(wèi)星 區(qū)域目標(biāo) 網(wǎng)格劃分 多星覆蓋

0 引 言

目前，利用成像衛(wèi)星偵測地面目標(biāo)已成為決策部門獲取情報(bào)信息的重要技術(shù)手段。按照與星載傳感器視場的相對大小關(guān)系，成像衛(wèi)星的觀測目標(biāo)可分為點(diǎn)目標(biāo)和區(qū)域目標(biāo)。能夠完全被衛(wèi)星的視場所包含的為點(diǎn)目標(biāo)，衛(wèi)星一次掃描無法完全覆蓋的為區(qū)域目標(biāo)[1]。點(diǎn)目標(biāo)相對星載傳感器瞬間視場較小，其形狀可被忽略并簡化以單點(diǎn)經(jīng)緯度坐標(biāo)表示。區(qū)域目標(biāo)相對星載傳感器瞬間視場較大，通常是由多邊形或封閉曲線指出的地面目標(biāo)，需要多個(gè)觀測條帶才能被完全覆蓋[2]。利用多星協(xié)同對區(qū)域目標(biāo)成像觀測，從而獲取更高的時(shí)效性和完整性，是衛(wèi)星成像任務(wù)必然需求。當(dāng)觀測目標(biāo)為區(qū)域目標(biāo)時(shí), 衛(wèi)星經(jīng)過目標(biāo)上空, 選擇不同的傳感器側(cè)視角可以觀測到目標(biāo)區(qū)域的不同部分。為了達(dá)到對目標(biāo)觀測的零遺漏，使整個(gè)觀測過程耗時(shí)最短，得到質(zhì)量更高的圖像，每次需要合理選定傳感器側(cè)視角度。受衛(wèi)星飛行軌道、區(qū)域范圍、相機(jī)分辨率以及地球自轉(zhuǎn)等空間因素和過境時(shí)間的制約，合理選定一個(gè)觀測方案實(shí)際上是一個(gè)基于時(shí)空約束的動(dòng)態(tài)組合優(yōu)化問題。因此，如何合理地設(shè)定衛(wèi)星每次過境側(cè)視角度,以達(dá)到對偵查區(qū)域較快的完整覆蓋，是衛(wèi)星任務(wù)規(guī)劃領(lǐng)域的重點(diǎn)難題。

本文研究多星協(xié)同對區(qū)域目標(biāo)完全覆蓋問題，在保證目標(biāo)區(qū)域被完全覆蓋的基礎(chǔ)上使觀測方案時(shí)間跨度最短。目前，國內(nèi)外學(xué)者對多星區(qū)域覆蓋問題研究甚少，對衛(wèi)星任務(wù)規(guī)劃和調(diào)度問題研究較多，而且大都是針對點(diǎn)目標(biāo)偵察成像[3-6]，不能保證區(qū)域觀測的完備性，或針對單星的區(qū)域覆蓋[7-8]，只解決了衛(wèi)星單次過境區(qū)域目標(biāo)時(shí)的觀測計(jì)劃編制問題。對于多星區(qū)域目標(biāo)問題的研究，大多僅談任務(wù)調(diào)度，并沒有給出具體的覆蓋量化分析模型[9-11]。白國慶等[12]采取區(qū)域劃分方法, 將大面積區(qū)域分割為可由單顆衛(wèi)星一次性完成的子任務(wù)。阮啟明等[2]采用禁忌搜索算法，應(yīng)用帶最優(yōu)解記錄的禁忌搜索策略減小搜索空間。此兩種方法以最大化多星對區(qū)域目標(biāo)總體覆蓋率為目標(biāo)，并不考慮完全覆蓋及時(shí)效性，不能滿足實(shí)際復(fù)雜條件下多星覆蓋任務(wù)要求。此外，智能優(yōu)化算法中的遺傳算法和模擬退火算法也是覆蓋問題普遍采用的方法[13-14]。這些算法搜索空間大，不確定的因子多，很難確定統(tǒng)一的目標(biāo)函數(shù)。同時(shí)收斂性相當(dāng)依賴初始值的選取，而且都是基于求解一個(gè)完整的觀測方案得到一個(gè)隨機(jī)解，然后在鄰近解空間中迭代尋找更優(yōu)解的算法。隨機(jī)解與解空間都基于完整觀測方案，而一次觀測方案的求解本身是相當(dāng)復(fù)雜且費(fèi)時(shí)的。隨著問題規(guī)模增大，并考慮實(shí)際的精度要求，以上方法的求解在工程實(shí)踐中并沒有多大意義。

本文以成像衛(wèi)星對目標(biāo)區(qū)域完全覆蓋為目標(biāo)構(gòu)建問題模型，提出了一種基于一次覆蓋策略的求解算法。復(fù)雜性不會(huì)隨著問題規(guī)模急劇擴(kuò)大而顯著增加，遠(yuǎn)遠(yuǎn)小于遺傳算法等智能優(yōu)化算法，其搜索空間的大小要比窮舉法和遺傳算法小很多。且該方法只需求解一次完整觀測方案，就可以得到一個(gè)次優(yōu)的滿意解。同時(shí)考慮了覆蓋時(shí)效性，充分發(fā)揮了不同衛(wèi)星觀測能力。

1 問題描述

衛(wèi)星以推掃方式進(jìn)行成像，成像衛(wèi)星以一定空間軌道運(yùn)行，在地面形成以星下點(diǎn)軌跡為軸線，由側(cè)擺角、視場角和俯仰角等共同確定的成像覆蓋條帶。多星區(qū)域覆蓋二維模型如圖1所示。多邊形區(qū)域?yàn)槟繕?biāo)區(qū)域，恰好被三個(gè)黑色條帶重疊推掃覆蓋。

圖1 覆蓋二維模型圖

給定一段足夠長時(shí)間T，編號(hào)為{1,2,…,m}的m顆成像衛(wèi)星觀測某個(gè)區(qū)域目標(biāo)Area，這些衛(wèi)星在時(shí)間T內(nèi)有n次過境，每次過境持續(xù)時(shí)間tw=[start,end]，稱為時(shí)間窗口，n次過境活動(dòng)組成一個(gè)窗口集W={tw1,tw2,…,twn}。一個(gè)時(shí)間窗口twi內(nèi)，相應(yīng)衛(wèi)星以某個(gè)側(cè)擺角度θi推掃形成條帶覆蓋區(qū)域Ai。從W中選出p個(gè)時(shí)間窗口tw1,tw2,…,twp，按開始時(shí)間start先后順序排列，對應(yīng)衛(wèi)星條帶序列{s1,s2,…,sp}，在這p個(gè)時(shí)間窗口內(nèi)條帶覆蓋區(qū)域A1,A2,…,Ap，其相應(yīng)側(cè)擺角序列Θ={θ1,θ2,…,θp}，獲取時(shí)間t=endp-start1。

① 太陽高度角約束;

② 成像分辨率約束;

③ 地面網(wǎng)格劃分精度約束。

此時(shí)Θ={θ1,θ2,…,θp}側(cè)擺角序列是衛(wèi)星序列{s1,s2,…,sp}的側(cè)擺方案。對于該問題，衛(wèi)星每次過境以不同側(cè)視角度觀測，對應(yīng)不同的觀測條帶，取可選的觀測帶數(shù)目為K，取總的觀測時(shí)間窗口數(shù)為N。以計(jì)算一個(gè)觀測方案的時(shí)間為尺度，那么時(shí)間復(fù)雜度為O(KN)，即使K固定不變，該求解也需指數(shù)時(shí)間。因而，可以認(rèn)為該問題為NP完備問題，其精確求解是很困難的，只能通過一定的方法求解一個(gè)近似的滿意解。

2 區(qū)域覆蓋

本文提出基于一次覆蓋策略的搜索算法求解區(qū)域覆蓋問題，一次覆蓋策略是以最大可視覆蓋為目標(biāo)，進(jìn)行一次完整的全覆蓋，找出只被覆蓋一次的區(qū)域。針對一次覆蓋區(qū)域，以不同側(cè)視角進(jìn)行瞬時(shí)覆蓋搜索，選擇覆蓋點(diǎn)數(shù)最多的側(cè)視角度確定實(shí)際覆蓋方案。其復(fù)雜性不會(huì)隨問題規(guī)模急劇擴(kuò)大而顯著增加，遠(yuǎn)小于遺傳算法，其搜索空間小于窮舉法和遺傳算法。特別地，當(dāng)區(qū)域離散網(wǎng)格化精度減小，取點(diǎn)數(shù)成指數(shù)倍增加時(shí)，該算法優(yōu)勢更加凸顯。

圖2為覆蓋總體流程圖。首先輸入仿真參數(shù)和約束參數(shù)，通過預(yù)處理獲取衛(wèi)星過境區(qū)域的時(shí)間窗口，同時(shí)將區(qū)域網(wǎng)格離散化。然后通過區(qū)域覆蓋計(jì)算輸出最終觀測方案。時(shí)間窗口是通過STK軟件access模塊計(jì)算得到。區(qū)域覆蓋計(jì)算包括一次覆蓋、瞬時(shí)覆蓋兩階段組成的區(qū)域覆蓋算法，且該算法依賴條帶計(jì)算及網(wǎng)格值更新。

圖2 覆蓋總體流程圖

2.1 網(wǎng)格劃分

區(qū)域覆蓋問題的精確求解，需要將區(qū)域網(wǎng)格點(diǎn)化，以便在實(shí)現(xiàn)軌道仿真的基礎(chǔ)上，能夠跟蹤分析多顆衛(wèi)星對每一個(gè)網(wǎng)格點(diǎn)的重疊覆蓋特性，從而進(jìn)行量化分析。區(qū)域目標(biāo)被網(wǎng)格劃分如圖3所示。使用等經(jīng)緯度間隔的網(wǎng)格劃分，將單位經(jīng)緯度矩形區(qū)域按邊等比劃分成多個(gè)平面上的網(wǎng)格，用網(wǎng)格中心點(diǎn)代表該網(wǎng)格的整個(gè)區(qū)域。單位經(jīng)緯度矩形區(qū)域劃分比例即為網(wǎng)格精度，不同的劃分比例對應(yīng)不同精度的網(wǎng)格劃分，精度越小，單位經(jīng)緯度區(qū)域劃分的網(wǎng)格點(diǎn)就越多，目標(biāo)區(qū)域能表示更精細(xì)。網(wǎng)格精度取值范圍為(0,1〗，一般取0.5、0.25、0.125、0.062 5。如圖4所示，單位經(jīng)緯度區(qū)域按不同精度劃分。

圖3 區(qū)域劃分示意圖

圖4 網(wǎng)格精度示意圖

定義1網(wǎng)格屬性：P=[x,y,t,s]，x、y為網(wǎng)格點(diǎn)的屏幕坐標(biāo)屬性，t為覆蓋重?cái)?shù)，代表該點(diǎn)被衛(wèi)星條帶覆蓋t次，s為條帶屬性，當(dāng)t=1，s標(biāo)記覆蓋該點(diǎn)的條帶，否則置空。

覆蓋條帶是由邊界多邊形定義的區(qū)域，覆蓋推掃是通過區(qū)域填充更新網(wǎng)格屬性值，每次推掃以多邊形區(qū)域內(nèi)的網(wǎng)格點(diǎn)為集合。

網(wǎng)格精度約束:區(qū)域覆蓋本質(zhì)是對網(wǎng)格點(diǎn)進(jìn)行區(qū)域填充，然而此途徑并不能判斷邊界網(wǎng)格是否嚴(yán)格落入覆蓋填充區(qū)域，因而產(chǎn)生邊界誤差。取一個(gè)更小的網(wǎng)格精度，可以將網(wǎng)格區(qū)域劃分更加精細(xì)，能夠減小覆蓋求解誤差，但覆蓋計(jì)算處理的網(wǎng)格點(diǎn)增多，增加了覆蓋問題求解規(guī)模，影響計(jì)算效率。實(shí)驗(yàn)時(shí)網(wǎng)格精度取0.125，在滿足計(jì)算效率前提下，誤差已相對很小。

2.2 多約束覆蓋條帶計(jì)算算法

覆蓋條帶即衛(wèi)星在地球上推掃軌跡， 條帶由推掃軌跡的邊界點(diǎn)序列表示。有如下問題定義：假定相機(jī)的垂軌向半視場角為θ(θ定義相機(jī)視場邊緣與相機(jī)中心視軸夾角)，沿軌向半視場角為?，衛(wèi)星軌道高度為h=r-R，相機(jī)沿衛(wèi)星本體x軸左右側(cè)擺角±β∈[0,βmax]，求相機(jī)側(cè)擺情況下在地球上的可視投影及給定時(shí)間段內(nèi)的覆蓋條帶。可視投影及推掃軌跡如圖5所示。

圖5 推掃軌跡

衛(wèi)星t時(shí)刻對地可視投影計(jì)算的算法步驟如下：

1) 設(shè)傳感器位置為P，地心為O，根據(jù)半角θ、?，以PO為高線，構(gòu)造代表傳感器視場的四棱錐P-Q1Q2Q3Q4。

p′=q×p×q-1

(1)

Si：地心赤道慣性坐標(biāo)系，So：軌道坐標(biāo)系，Sb：相機(jī)本體坐標(biāo)系。

從So到Si坐標(biāo)變換矩陣：

(2)

從Sb到So坐標(biāo)變換矩陣：

(3)

其中:Ω表示升交點(diǎn)赤經(jīng)，i表示軌道傾角，u表示緯度幅角(u=ω+τ，ω是近地點(diǎn)幅角，τ是真近點(diǎn)角)，θ是側(cè)擺角，φ是俯仰角，ψ是偏航角。

對任意角γ，

(4)

4) 通過線性插值分別求ΔPQ1Q2、ΔPQ2Q3、ΔPQ3Q4、ΔPQ4Q1與地球橢球面交線。例如求ΔPQ1Q2與地球交線，將線段Q1Q2分n等分，每等分取一點(diǎn)Qi，PQi與橢球面相交得交點(diǎn)，交點(diǎn)序列構(gòu)成交線。

5) 若以上交線圍成閉合區(qū)域，則該區(qū)域?yàn)榭梢曂队?，否則以視場邊緣與地球表面相切的切線補(bǔ)齊非閉合部分使之閉合，形成可視投影。如圖6所示。

圖6 可視投影

覆蓋條帶計(jì)算求解步驟如下：

1) 給定起止時(shí)間段[t1,t2],步長Δt。

2)t←t1。

3) 重復(fù)執(zhí)行(1)-(3)直到t>t2。

(1) 計(jì)算t時(shí)刻衛(wèi)星相機(jī)的可視投影;

(2) 以衛(wèi)星運(yùn)動(dòng)方向?yàn)閰⒄?，取投影上極左極右兩點(diǎn)作為條帶左右邊界點(diǎn)。如圖7所示的兩種邊界凸出情形，利用對稱性直接取弧段中點(diǎn)M為極左或極右點(diǎn)。對于圖8所示的邊界凹陷情形，A、B兩點(diǎn)的中點(diǎn)R,地心O與R連線OR，射線OR與球面交點(diǎn)M,取M為極左或極右點(diǎn);

(3)t←t+Δt。

4) 以上邊界點(diǎn)坐標(biāo)依次轉(zhuǎn)化為經(jīng)緯度坐標(biāo)，這些坐標(biāo)點(diǎn)序列即構(gòu)成時(shí)間段[t1,t2]內(nèi)衛(wèi)星覆蓋條帶。

圖7 邊界凸出的投影

圖8 邊界凹陷的投影

相機(jī)分辨率約束：

1) CCD傳感器相機(jī)分辨率計(jì)算。CCD傳感器像元尺寸D，焦距f，以及側(cè)視角度α，H為軌道高度，計(jì)算CCD相機(jī)分辨率b，等式如下：

(5)

2) SAR傳感器相機(jī)分辨率計(jì)算。SAR傳感器側(cè)視角度φ，C為光速，B為信號(hào)帶寬，Re為地球平均半徑，H為軌道高度，計(jì)算SAR相機(jī)分辨率b，等式如下：

(6)

3) 分辨率對覆蓋的約束。在覆蓋分析找一次覆蓋狀態(tài)過程中，衛(wèi)星以最大視場角對目標(biāo)區(qū)域進(jìn)行可視覆蓋，而最大視場角是由最大側(cè)視角度和最大側(cè)擺時(shí)的半視場角決定。最大側(cè)擺時(shí)的半視場角固定，根據(jù)以上等式，側(cè)視角度越大，分辨率越大。所以不滿足分辨率的側(cè)視被忽略。故考慮分辨率的最大視場角度一般比不考慮分辨率的最大視場角度小。體現(xiàn)在一次覆蓋狀態(tài)仿真過程中，覆蓋條帶變窄。

太陽高度角約束：覆蓋過程中，首先要計(jì)算衛(wèi)星對目標(biāo)可視時(shí)間段，來確定可用于覆蓋分析的條帶。太陽高度角約束了可用于覆蓋分析的可視時(shí)間窗口，不滿足太陽高度角范圍的時(shí)間窗口被忽略，使可用條帶數(shù)減少。其約束通過STK接口模塊計(jì)算實(shí)現(xiàn)。

2.3 區(qū)域覆蓋算法

一次覆蓋算法求解該問題雖不具全局最優(yōu)性，但對規(guī)模龐大的NP問題，依然能高效地找到可行解。該算法的搜索起點(diǎn)為最有可能遺漏的點(diǎn)，各衛(wèi)星以最大視場角計(jì)算條帶依次對目標(biāo)區(qū)域推掃覆蓋，直到完全覆蓋。只被覆蓋一次的子區(qū)域?yàn)橐淮胃采w區(qū)域，一次覆蓋區(qū)域中的點(diǎn)為最有可能遺漏的點(diǎn)，應(yīng)該被優(yōu)先覆蓋。要求衛(wèi)星以瞬時(shí)視場角、不同的側(cè)視角度對目標(biāo)區(qū)域瞬時(shí)推掃覆蓋，并根據(jù)覆蓋策略選取合適的側(cè)視角度加入觀測方案。同時(shí)從區(qū)域目標(biāo)中去掉選定觀測角度推掃過的網(wǎng)格點(diǎn)，形成新的目標(biāo)區(qū)域。然后重復(fù)以上過程直至區(qū)域網(wǎng)格點(diǎn)數(shù)為0。

定義2一次覆蓋狀態(tài)：衛(wèi)星以最大視場角對區(qū)域目標(biāo)計(jì)算可視條帶。對于按開始時(shí)間排序的條帶序列，每個(gè)條帶依次去覆蓋目標(biāo)區(qū)域，直到區(qū)域被完全覆蓋。這時(shí)算法的狀態(tài)為一次覆蓋狀態(tài)。

覆蓋策略1衛(wèi)星每次以δλ角度為步長更改側(cè)視角度，以瞬時(shí)視場角對一次覆蓋區(qū)域網(wǎng)格進(jìn)行掃描覆蓋。每次推掃覆蓋到的網(wǎng)格點(diǎn)屬性t加1，未推掃的區(qū)域網(wǎng)格屬性t不變，每次推掃的側(cè)視角和覆蓋面積被記錄后，覆蓋區(qū)域網(wǎng)格屬性值重置。最后選擇覆蓋網(wǎng)格面積最大推掃角度加入側(cè)視方案。

覆蓋策略2如果出現(xiàn)多個(gè)一次覆蓋區(qū)域,并且瞬時(shí)覆蓋后的最大推掃面積相同時(shí)，衛(wèi)星將在目標(biāo)區(qū)域中選擇實(shí)際覆蓋面積最大的側(cè)視覆蓋條帶確定側(cè)視角。否則，選擇最大推掃面積的瞬時(shí)覆蓋確定側(cè)視角。

策略1網(wǎng)格面積統(tǒng)計(jì)僅限于一次覆蓋區(qū)域，策略2計(jì)算實(shí)際網(wǎng)格覆蓋面積，將統(tǒng)計(jì)范圍擴(kuò)大到整個(gè)區(qū)域目標(biāo)。每次瞬時(shí)覆蓋推掃時(shí)，既覆蓋了一次覆蓋區(qū)域，又可能覆蓋了一次覆蓋區(qū)域以外的部分目標(biāo)區(qū)域。

算法步驟如下：

拓展時(shí)間窗口語義，定義五元組D=[開始時(shí)間,結(jié)束時(shí)間,衛(wèi)星代號(hào),側(cè)視角度,一次覆蓋標(biāo)識(shí)]，一次覆蓋標(biāo)識(shí)為-2、-1、0、1，分別表示時(shí)間窗口被分配、不可用、待分配、對應(yīng)條帶為一次覆蓋條帶，初始為0。

1) 預(yù)估并設(shè)定仿真時(shí)間段T，保證這些衛(wèi)星在該時(shí)間內(nèi)足夠完成對目標(biāo)區(qū)域的覆蓋。

2) 設(shè)定網(wǎng)格精度劃分網(wǎng)格，輸入分辨率閾值、太陽高度角上下限、側(cè)視步長δλ。

3) 根據(jù)時(shí)間段T和太陽高度角約束，獲取所有衛(wèi)星對目標(biāo)區(qū)域可視時(shí)間窗口，生成時(shí)間窗口五元組序列DS，這些元組按開始時(shí)間先后順序排序。

4) 區(qū)域M初始為區(qū)域目標(biāo)所包含的網(wǎng)格集，網(wǎng)格屬性t初始為0。

5) 重復(fù)執(zhí)行步驟(1)-步驟(5)，直至M=?。

(1) 重復(fù)執(zhí)行步驟①-步驟③，直至找到一次覆蓋狀態(tài)或DS被遍歷完畢;

① 每次從序列DS中按順序取出一個(gè)元組d,如果元組d覆蓋標(biāo)識(shí)為-2或-1，則跳到①，否則執(zhí)行下一步;

② 元組d覆蓋標(biāo)識(shí)置0，對d所屬衛(wèi)星進(jìn)行分辨率約束檢驗(yàn)，并計(jì)算滿足約束的最大視場角，若無法滿足約束，則置其覆蓋標(biāo)識(shí)為-1;

③d所屬衛(wèi)星以最大視場角計(jì)算條帶，對區(qū)域M進(jìn)行重疊覆蓋。

(2) 如果沒找到一次覆蓋狀態(tài)，則跳到步驟2)，重新預(yù)估T或調(diào)整約束條件。

(3) 掃描區(qū)域M內(nèi)所有網(wǎng)格點(diǎn)，如果網(wǎng)格屬性t=1，則根據(jù)網(wǎng)格條帶屬性s置對應(yīng)時(shí)間窗口五元組的覆蓋標(biāo)識(shí)為1。

(4) 遍歷DS，對一次覆蓋標(biāo)識(shí)為1的時(shí)間窗口五元組d，所屬衛(wèi)星在相同時(shí)間段以確定的瞬時(shí)視場角度，δλ為步長，選擇不同的側(cè)視角度計(jì)算覆蓋條帶依次對區(qū)域M進(jìn)行推掃覆蓋，根據(jù)以上覆蓋策略確定最終的側(cè)視角θ，更新元組d側(cè)視角度為θ，置其覆蓋標(biāo)識(shí)為-2，記側(cè)視角θ時(shí)的推掃區(qū)域網(wǎng)格集為m。

(5) 令M=M-m，網(wǎng)格點(diǎn)屬性值重置。

6) 根據(jù)DS輸出側(cè)視序列方案。

圖9演示了求一次覆蓋區(qū)域過程。圖9(a)表示目標(biāo)區(qū)域，圖9(b)-圖9(e)表示條帶S1、S2、S3、S4依次對目標(biāo)區(qū)域進(jìn)行覆蓋推掃，尋找一次覆蓋狀態(tài)。第五步找到一次覆蓋狀態(tài)，目標(biāo)被完全覆蓋。第六步表示通過推掃覆蓋得到兩個(gè)陰影區(qū)域A1、A2，代表一次覆蓋區(qū)域。A1只能被條帶S2單獨(dú)一次推掃，A2只能被條帶S4單獨(dú)一次推掃。

圖9 一次覆蓋過程

圖10 瞬時(shí)覆蓋過程

圖11 新的目標(biāo)區(qū)域

3 實(shí)驗(yàn)結(jié)果及分析

為檢驗(yàn)本文模型及算法，以運(yùn)行時(shí)間、覆蓋獲取時(shí)間、覆蓋重?cái)?shù)為指標(biāo)，進(jìn)行如下仿真實(shí)驗(yàn)。

仿真時(shí)間：2015/12/21 12:00:00-2016/01/05 12:00:00。

網(wǎng)格精度：0.125。

推掃步長δλ：1°。

軌道參數(shù)：用到四顆光學(xué)衛(wèi)星1-衛(wèi)星4，軌道歷元時(shí)間為2015/7/1 12:00:00。表1為初始軌道根數(shù)。

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

目標(biāo)區(qū)域：Area1-Area3，頂點(diǎn)經(jīng)緯度定義如表2所示。

表2 區(qū)域目標(biāo)定義

成像條件：分辨率閾值取10 m，太陽高度角范圍 (0°,90°)，傳感器垂軌向半視場角5°，沿軌向半視場角1°，最大側(cè)擺角40°。

根據(jù)以上仿真數(shù)據(jù)，應(yīng)用本文算法做了5組實(shí)驗(yàn)，得表3所示結(jié)果。在0.125網(wǎng)格精度下，區(qū)域Area1、Area2、Area3網(wǎng)格點(diǎn)數(shù)分別為414、1 687、3 971。實(shí)例一、二、三用于驗(yàn)證區(qū)域大小對覆蓋的影響，相同衛(wèi)星對不同區(qū)域覆蓋，區(qū)域大小對覆蓋獲取時(shí)間影響顯著，對計(jì)算效率影響不明顯。說明該算法復(fù)雜性沒有隨著問題規(guī)模急劇擴(kuò)大而顯著增加，具有良好適應(yīng)性。實(shí)例三、四、五區(qū)域目標(biāo)均為Area3，衛(wèi)星資源增加，運(yùn)行時(shí)間沒有顯著變化，獲取時(shí)間顯著減小，具有更好的時(shí)效性，衛(wèi)星協(xié)同觀測能力得到充分發(fā)揮。統(tǒng)計(jì)以上5個(gè)實(shí)例區(qū)域的覆蓋結(jié)果，得到圖12所示重?cái)?shù)統(tǒng)計(jì)圖。一重保持較高占比，一重與二重比率能達(dá)到80%～90%，且相對衛(wèi)星數(shù)目，實(shí)例的重?cái)?shù)也不高，說明該算法覆蓋冗余比較理想，覆蓋效果良好，通過該算法可高效獲取滿意解。

表3 仿真結(jié)果

圖12 重?cái)?shù)統(tǒng)計(jì)圖

禁忌搜索算法、遺傳算法、本文算法性能比較如表4所示。其中區(qū)域大小表示算法適宜處理的最大區(qū)域，用區(qū)域網(wǎng)格點(diǎn)數(shù)量級(jí)衡量。從表4中可以看出：本文算法在實(shí)際約束、覆蓋時(shí)效性、運(yùn)算效率、區(qū)域大小等性能方面占較高優(yōu)勢，具良好的適應(yīng)性。表5是以上算法計(jì)算效能的對比。由于禁忌算法及遺傳算法是比較復(fù)雜的智能算法，在規(guī)模較小的實(shí)例下，容易找到最優(yōu)解，本文實(shí)例一、實(shí)例二規(guī)模較小，禁忌算法及遺傳算法求得的解優(yōu)于本文算法，但本文算法運(yùn)算效率較高。隨著問題規(guī)模的增大，本文算法運(yùn)算效率、覆蓋時(shí)效性方面的優(yōu)勢更加凸顯。

表4 算法性能對比

表5 算法計(jì)算效能對比

4 結(jié) 語

本文對多星多約束區(qū)域目標(biāo)覆蓋問題進(jìn)行了研究，構(gòu)造了網(wǎng)格劃分量化分析模型。通過幾何方法計(jì)算衛(wèi)星覆蓋條帶，在此基礎(chǔ)上提出了基于一次覆蓋策略的求解算法。仿真結(jié)果表明：該模型及算法能夠有效求解出一個(gè)滿意解，且相比以往算法，該算法可以有效處理規(guī)模較大的問題。隨著衛(wèi)星數(shù)增加，完成覆蓋所需獲取時(shí)間顯著減小，充分發(fā)揮不同衛(wèi)星的觀測能力且能夠滿足一定的時(shí)效性。然而，考慮到覆蓋衛(wèi)星增多，條帶花費(fèi)有增加的趨勢，且仍存在諸多可編排的衛(wèi)星條帶，資源還有很大節(jié)省空間。下一步可以嘗試覆蓋結(jié)果的二次優(yōu)化，充分發(fā)揮衛(wèi)星觀測能力的同時(shí)，盡可能節(jié)約衛(wèi)星資源。

[1] 白保存,阮啟明，陳英武.多星協(xié)同觀測條件下區(qū)域目標(biāo)的動(dòng)態(tài)劃分方法[J]. 運(yùn)籌與管理, 2008, 17(2):43-47.

[2] 阮啟明,譚躍進(jìn),李永太,等. 基于約束滿足的多星對區(qū)域目標(biāo)觀測活動(dòng)協(xié)同[J]. 宇航學(xué)報(bào), 2007,28(1):238-242.

[3] Globus A, Crawford J, Lohn J, et al. A comparison of techniques for scheduling earth observing satellites[C]//Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence, July 25-29, 2004, San Jose, California, Usa. DBLP, 2004:836-843.

[4] Tinker P, Fox J, Green C, et al. Analogical and case-based reasoning for predicting satellite task schedulability[C]//International Conference on Case-Based Reasoning. Springer Berlin Heidelberg, 2005:566-578.

[5] 李菊芳,譚躍進(jìn).衛(wèi)星觀測系統(tǒng)整體調(diào)度的收發(fā)問題模型及求解[J].系統(tǒng)工程理論與實(shí)踐, 2004, 24(12):65-71.

[6] Chen H, Li J, Jing N, et al. Hybrid Algorithms for Electromagnetic Detection Satellites Scheduling[C]//20th IEEE International Conference on Tools with Artificial Intelligence, 2008:411-418.

[7] Lin W C, Liao D Y, Liu C Y, et al. Daily Imaging Scheduling of an Earth Observation Satellite[J].IEEE Transactions on System, Man, Cybernetics,2005,35(2):213-223.

[8] 章登義，郭雷，王騫，等. 一種面向區(qū)域目標(biāo)的敏捷成像衛(wèi)星單軌調(diào)度方法[J]. 武漢大學(xué)學(xué)報(bào)·信息科學(xué)版，2014,39(8):901-905.

[9] 李曦,祝江漢,毛赤龍.多衛(wèi)星區(qū)域觀測任務(wù)的效率優(yōu)化研究[J].計(jì)算機(jī)仿真, 2006, 23(12):24-27.

[10] 王慧林,黃維,馬滿好.面向區(qū)域的電子偵察衛(wèi)星規(guī)劃系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用, 2010, 46(27):209-213.

[11] 賀川, 朱曉敏, 邱滌珊. 面向應(yīng)急成像觀測任務(wù)的多星協(xié)同調(diào)度方法[J]. 系統(tǒng)工程與電子技術(shù), 2012, 34(4):726-731.

[12] 白國慶,白保存,徐一帆.多星協(xié)同對區(qū)域目標(biāo)觀測的動(dòng)態(tài)劃分方法[J]. 測繪科學(xué), 2010, 35(6): 32-35.

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

[14] 王迪,祝江漢,薛波.基于GA的電子偵察衛(wèi)星任務(wù)規(guī)劃問題研究[J].計(jì)算機(jī)仿真, 2009, 26(8):53-56.

MULTI-SATELLITEREGIONCOVERAGEOPTIMIZATIONALGORITHMUNDERREALCOMPLEXCONSTRAINTS

Zhang Dengyi1Wang Zheng1Cai Bo1,2*

1(SchoolofComputer,WuhanUniversity,Wuhan430072,Hubei,China)2(InformationCenter,WuhanUniversity,Wuhan430072,Hubei,China)

Using multi-satellite co-operation to detect large area, it is required to complete the full coverage of a given target area in the shortest time, and obtain the optimal side-view observation scheme for each transit. The Existing coverage algorithm has the disadvantages of time-consuming and low efficiency technology bottleneck, spatial coverage rate and time limitations. In this paper, we took full advantage of the opportunity of each transit observation of the satellite, considering the constraints such as camera resolution, solar elevation angle and ground precision. Based on the characteristics of satellite side swing, sensor visual performance and satellite orbit parameters, the regional target was covered by quantitative coverage analysis, and the grid partitioning model was established. A coverage optimization algorithm based on one coverage strategy was proposed, which could adapt to the practical complex constraints conditions, in the actual problem scale, with good efficiency, to meet the industrial accuracy requirements. Finally, the effectiveness and adaptability of the algorithm were verified in the simulation application.

Imaging satellite Regional target Grid partition Multi-satellite coverage

2016-11-18。國家科技支撐計(jì)劃項(xiàng)目(2012BAH35B02)；國家自然科學(xué)基金項(xiàng)目(41301409)。章登義，教授，主研領(lǐng)域：空天信息仿真及衛(wèi)星調(diào)度。王爭，碩士生。蔡波，副教授。

TP3

A

10.3969/j.issn.1000-386x.2017.12.001