基于全球網(wǎng)格的衛(wèi)星成像區(qū)域目標規(guī)劃算法

楊紀偉 付偉 韓麗 顏博 岳群彬 張麗霞

(1 中國電子科技集團公司第五十四研究所，石家莊 050081)(2 北京市遙感信息研究所，北京 100192)

隨著全球遙感行業(yè)的蓬勃發(fā)展，衛(wèi)星成像已成為戰(zhàn)場監(jiān)視、國土測量、環(huán)境監(jiān)測、氣象預測等工作必不可少的一種手段。通過成像衛(wèi)星對地面區(qū)域進行觀測、測繪等工作，具有不受空間位置限制、成像范圍廣、單次成像區(qū)域大等優(yōu)點，對于合成孔徑雷達(SAR)衛(wèi)星等成像衛(wèi)星，還兼有全天時、全天候、不受天氣影響等特點。當前全球在軌成像衛(wèi)星數(shù)以千計，成像衛(wèi)星對地面的觀測需求，已逐漸由單星成像轉(zhuǎn)為多星協(xié)同成像[1-2]。對區(qū)域目標的觀察，需要對區(qū)域目標進行分解，不同的分解方式在一定程度上影響著衛(wèi)星對區(qū)域目標的觀測效率。因此各國研究者針對不同的衛(wèi)星及其載荷，提出了多種區(qū)域目標分解規(guī)劃方法。目前主要包括以下幾類：一是基于獨立場景的點目標覆蓋方法，該方法依據(jù)獨立單景將區(qū)域目標分解化為集合覆蓋問題；二是基于固定寬度的條帶分解方法，該方法依據(jù)衛(wèi)星飛行方向和成像幅寬將區(qū)域目標分解為固定寬度的平行條帶；三是基于高斯投影的條帶分解方法，該方法利用高斯投影區(qū)域目標從大地坐標系轉(zhuǎn)換到平面坐標系，在平面坐標系下對目標進行分解再利用高斯反算將其轉(zhuǎn)換到大地坐標系下；四是基于預定義參考系的單景分解方法，依據(jù)定義的全球參考系，該方法將區(qū)域目標分解多個獨立的場景[3]。這些方法處理的區(qū)域目標面積相對較小，對于經(jīng)度差較大的區(qū)域目標分解誤差較大，另外采用高斯投影的分解方法時要進行多次高斯投影及反向運算，計算量大效率低。針對以上區(qū)域目標分解算法的不足，本文提出了一種基于全球網(wǎng)格的區(qū)域目標規(guī)劃算法，旨在將區(qū)域規(guī)劃算法反應速度限制在10秒量級，并能適應不同面積的區(qū)域目標規(guī)劃，滿足小范圍精確觀測、大范圍廣域搜索的需求。

1 基于全球網(wǎng)格的區(qū)域目標規(guī)劃算法

基于全球網(wǎng)格的區(qū)域目標規(guī)劃算法通過全球網(wǎng)格預先計算、任務區(qū)域分解、可見區(qū)域匹配、條帶選取等步驟最終生成多星協(xié)同方案,流程如圖1所示。通過貪婪算法，每次選取的條帶都是當前看來最好的選擇，也就是說，不從整體最優(yōu)加以考慮，算法得到的是某種意義上的局部最優(yōu)解。流程中涉及到的關(guān)鍵技術(shù)包括分幅比例尺的選擇、全球數(shù)據(jù)更新、多星協(xié)同策略生成及網(wǎng)格金字塔算法。

1.1 分幅比例尺的選擇

基于全球網(wǎng)格的區(qū)域目標規(guī)劃算法首先采用軍用分幅標準對全球進行網(wǎng)格劃分，比例尺的選擇既要兼顧精度又要兼顧數(shù)據(jù)量。本算法選擇的比例尺大小為1∶50 000，在1∶50 000比例尺下，全球約分為112萬個大小約為22 km×17.8 km的網(wǎng)格，如果以衛(wèi)星最大覆蓋范圍1000 km計算，一天的數(shù)據(jù)量約為190萬條(光學成像衛(wèi)星由于受太陽高度角限制，約為90萬條)，更新數(shù)據(jù)時間受訪問計算能力限制，以20個訪問計算節(jié)點計，更新一天數(shù)據(jù)約需要2～3 min[4]。

1.2 全球數(shù)據(jù)更新

全球數(shù)據(jù)更新，需要預先計算衛(wèi)星在未來特定時段對地面目標的訪問情況，并進行記錄。首先根據(jù)衛(wèi)星的軌道高度、衛(wèi)星側(cè)視能力計算特定時間段(可配置，本算法中取2 min)衛(wèi)星覆蓋區(qū)域，由所求得的衛(wèi)星覆蓋的區(qū)域計算覆蓋的網(wǎng)格，然后通過點目標訪問計算算法計算所有網(wǎng)格在當前時間段內(nèi)的訪問情況[5]。計算特定時間段衛(wèi)星覆蓋區(qū)域示意如圖2所示。

圖2 衛(wèi)星覆蓋距離示意圖Fig.2 Scheme diagram of the coverage distance of satellite

圖2中R代表地球半徑，h為衛(wèi)星軌道高度，θ為衛(wèi)星最大側(cè)擺能力，Φ為衛(wèi)星覆蓋范圍的球心角，單位為(°)，L為最大覆蓋距離，單位km，由正弦定理有

(1)

由式(1)得

(2)

經(jīng)簡單運算可得

L=φ·111

(3)

圖2計算了空間位置的可見性，考慮到光學成像衛(wèi)星對太陽高度角的要求，計算完四角點后，首先計算四角點在當前時間段內(nèi)的太陽高度角是否滿足要求，如果全部不滿足太陽高度角要求，則不計算當前時間段內(nèi)衛(wèi)星對當前區(qū)域的可視情況[6]。

通過并行目標訪問計算對所有需要計算的點目標進行可見性分析，并行目標訪問計算架構(gòu)如圖3所示。

并行計算調(diào)度服務器將收到的訪問計算申請分發(fā)到訪問計算節(jié)點，訪問計算節(jié)點計算完成后將結(jié)果返回。

訪問計算結(jié)果返回后，讀取訪問計算結(jié)果，將目標位置、目標編號、衛(wèi)星代號、訪問時刻、側(cè)擺角信息保存。

圖3 并行目標訪問計算架構(gòu)圖Fig.3 Architecture diagram of parallel target access computing

1.3 多星協(xié)同策略

根據(jù)區(qū)域范圍，計算在當前區(qū)域范圍內(nèi)的所有網(wǎng)格，按照衛(wèi)星信息、時間段范圍取出所有網(wǎng)格的訪問情況，對所有訪問情況進行分組，得到所有可能的衛(wèi)星對當前區(qū)域的訪問時段，對所有條帶按照訪問開始時間升序排序，按照策略依次選定當前處理條帶的側(cè)擺角，生成協(xié)同方案采用貪婪算法，之所以選擇貪婪算法作為生成協(xié)同方案的算法，是因為貪婪算法選擇條帶更簡單更迅速，能夠以較快的速度生成局部最優(yōu)的區(qū)域協(xié)同觀測方案。

選擇條帶側(cè)擺角的策略總共有3種：覆蓋面積最大、單次成像最優(yōu)、加權(quán)最優(yōu)。

覆蓋面積最大考慮的是衛(wèi)星單次覆蓋面積。即根據(jù)當前衛(wèi)星訪問區(qū)域的側(cè)擺角范圍，以0.1°為步進，計數(shù)不同側(cè)擺角下衛(wèi)星覆蓋的網(wǎng)格數(shù)，取衛(wèi)星覆蓋網(wǎng)格數(shù)最多的側(cè)擺角作為當前條帶的側(cè)擺角。其中，對于已被之前條帶覆蓋過的網(wǎng)格，不再計數(shù)，即計數(shù)的網(wǎng)格為沒有被覆蓋過的網(wǎng)格。

單次成像最優(yōu)考慮的是衛(wèi)星成像的效果。對于光學成像衛(wèi)星，一般來說，側(cè)擺角的絕對值越大，所成圖像質(zhì)量越差。單次成像最優(yōu)即優(yōu)先選擇側(cè)擺角絕對值最小的條帶。如某衛(wèi)星視場角范圍為左右各1°，如果某次訪問，能夠覆蓋區(qū)域的側(cè)擺角范圍為-10°～+10°，則選擇的條帶為0°；如果某次訪問，能夠覆蓋區(qū)域的側(cè)擺角范圍為0～10°，則選擇的條帶為1°，因為其中考慮到衛(wèi)星還有1°的視場角。

加權(quán)最優(yōu)既考慮單次覆蓋面積，又考慮衛(wèi)星成像效果。加權(quán)最優(yōu)對衛(wèi)星覆蓋面積進行正加權(quán)，對側(cè)擺角的絕對值進行負加權(quán)。首先計算不同側(cè)擺角下衛(wèi)星的覆蓋面積，記為m，取單位面積的加權(quán)為1/m，對于規(guī)則四邊形區(qū)域，選任意側(cè)擺角的概率相同。覆蓋面積m的計算，可以用覆蓋距離L代替[7-9]。計算不同側(cè)擺角下覆蓋距離L的示意如圖4所示。

圖4 求某側(cè)擺角下衛(wèi)星覆蓋距離Fig.4 Calculate the satellite coverage distance under a certain roll angle

記衛(wèi)星視場角為α(半場角)，L單位為(km)，φ′、φ″單位均為(°)。由公式得

(4)

(5)

則覆蓋距離為

L=(φ″-φ′)·111

(6)

在計算加權(quán)得分時，同樣需要將覆蓋過的網(wǎng)格排除。如果選擇不同側(cè)擺角時加權(quán)得分相同，則按照特定規(guī)則(覆蓋面積最大或單次成像最優(yōu))選定側(cè)擺角。

進一步對覆蓋面積最大、單次成像最優(yōu)、加權(quán)最優(yōu)3種策略進行解釋說明：由于覆蓋面積最大策略每次選擇的條帶都是有效覆蓋面積(排除已經(jīng)覆蓋過的面積)最大的條帶，該策略更適合于最快覆蓋的需求，可以以較短的時間達到指定的覆蓋率；單次成像最優(yōu)策略，由于每次選擇的條帶都是成像效果最優(yōu)的條帶，該策略更適合于總成像時間要求較低，但成像質(zhì)量要求較高的需求；加權(quán)最優(yōu)策略則是對以上兩種策略的一種中和考慮，同時考慮了成像效果以及總成像時間。此3種策略基本上能夠覆蓋區(qū)域觀測時間最快、效果最優(yōu)等需求。

1.4 網(wǎng)格金字塔

按照固定的比例尺對全球預先分點，計算并記錄所有網(wǎng)格的觀測情況；對于區(qū)域規(guī)劃任務，首先獲取區(qū)域所包含的當前比例尺下的所有網(wǎng)格的訪問情況，對所有網(wǎng)格的訪問情況按照特定規(guī)則、采用貪婪算法，生成觀測條帶集合。

按照上述過程進行區(qū)域規(guī)劃，存在一個準備數(shù)據(jù)時長和條帶精度的矛盾。如果比例尺小，相應的每個網(wǎng)格的面積小，全球網(wǎng)格數(shù)多，提前準備的數(shù)據(jù)量大，但是條帶精度會高；如果比例尺大，相應的每個網(wǎng)格的面積大，全球網(wǎng)格數(shù)少，提前準備的數(shù)據(jù)量小，但是條帶精度低。為了解決上述矛盾，本文提出一種網(wǎng)格金字塔算法。

對于預先計算網(wǎng)格訪問情況，采用的比例尺大，全球網(wǎng)格數(shù)少，對所有網(wǎng)格進行訪問計算并記錄訪問計算結(jié)果；在進行區(qū)域規(guī)劃時，采用的比例尺小，精度高。只有當一個較大網(wǎng)格包含的所有較小網(wǎng)格都被覆蓋，才認為該較大網(wǎng)格被完全覆蓋。以1∶25 000和1∶50 000為例，每個1∶50 000的網(wǎng)格由4個1∶25 000的小網(wǎng)格組成，如圖5所示。

圖5 相鄰比例尺網(wǎng)格關(guān)系Fig.5 Relationship of adjacent scale

處理時，只有4個1∶25 000的小網(wǎng)格均被覆蓋，才認為該1∶50 000的網(wǎng)格完全被覆蓋。本文采用的比例尺為計算訪問可能性采用1∶100 000的比例尺，生成條帶采用1∶25 000的比例尺。

2 仿真試驗分析

2.1 仿真條件設定

隨機選擇了3塊矩形區(qū)域作為試驗對象，區(qū)域大小分別約為100 km×100 km、1000 km×1000 km、2000 km×2000 km；10顆成像衛(wèi)星，預先計算5天的網(wǎng)格可見性，對區(qū)域從小到大分別采用單次成像最優(yōu)、加權(quán)最優(yōu)、覆蓋面積最大算法進行區(qū)域規(guī)劃；衛(wèi)星根數(shù)信息、側(cè)擺角信息及視場角信息參見表1。

表1 試驗數(shù)據(jù)表Table 1 Data table of experiment

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

試驗1用單次成像最優(yōu)的算法對約100 km×100 km區(qū)域采用3顆衛(wèi)星進行24 h區(qū)域目標規(guī)劃，觀測覆蓋率和計算耗時如表2所示。

試驗2用加權(quán)最優(yōu)策略對約1000 km×1000 km區(qū)域采用6顆衛(wèi)星進行72 h區(qū)域目標規(guī)劃，覆蓋率和計算耗時如表3所示，區(qū)域覆蓋效果如圖6所示。

試驗3用覆蓋面積最大策略對約2000 km×2000 km區(qū)域采用10顆衛(wèi)星進行72 h區(qū)域目標規(guī)劃，區(qū)域覆蓋效果如圖7所示，覆蓋率和計算耗時如表4所示。

3次試驗的結(jié)果說明：對于小區(qū)域(約100 km×100 km)，同等條件下容易達到指定的覆蓋率，本文采用單次成像最優(yōu)策略(單次成像效果好，但單次覆蓋率相對較小)進行試驗分析，并且記錄了相應條帶信息，覆蓋率為61.50%，計算耗時為8.2 s；對于大區(qū)域(約2000 km×2000 km)，同等條件下需要更多的條帶才能達到指定覆蓋率，采用覆蓋面積最大策略(單次成像覆蓋率大，但成像效果相對較差)進行實驗分析，覆蓋率為69.56%，計算耗時為24.5 s，由于條帶過多未記錄條帶具體信息；對于約1000 km×1000 km區(qū)域，作為比較試驗中的大小適中區(qū)域，采用加權(quán)最優(yōu)策略(同時考慮了成像效果和覆蓋率)進行實驗分析，覆蓋率為64.58%，計算耗時為17 s，由于條帶過多未記錄條帶具體信息。

從3個區(qū)域覆蓋性試驗可以看出：該算法對不同衛(wèi)星數(shù)量、不同大小的區(qū)域采用不同的規(guī)劃策略，計算時間可以達到10秒量級，滿足小范圍快速精確觀測、大范圍廣域快速搜索的工程使用需求。

表2 試驗1數(shù)據(jù)表Table 2 Data table of experiment 1

表3 試驗2數(shù)據(jù)表Table 3 Data table of experiment 2

圖6 試驗2效果圖Fig.6 Effect map of experiment 2

圖7 試驗3效果圖Fig.7 Effect map of experiment 3

3 結(jié)束語

本文設計了基于全球網(wǎng)格的區(qū)域目標規(guī)劃算法，能夠?qū)崿F(xiàn)成像衛(wèi)星對同一區(qū)域的多星協(xié)同觀測。在采用貪婪算法的前提下，針對不同大小區(qū)域設計單次成像最優(yōu)、加權(quán)最優(yōu)、覆蓋面積最大3種模式，計算24 h區(qū)域觀測情況，反應時間數(shù)量級在10秒量級。同時該區(qū)域目標規(guī)劃算法已應用于某衛(wèi)星任務規(guī)劃系統(tǒng)，規(guī)劃出的多星協(xié)同規(guī)劃方案，能夠滿足觀測可見性要求。但是據(jù)試驗觀察，有不低于50%反應時間消耗在網(wǎng)格可見性數(shù)據(jù)獲取上，基于此，后續(xù)將探索使用大并發(fā)數(shù)據(jù)庫存儲網(wǎng)格可見性數(shù)據(jù)，以進一步提高反應速度。同時，基于貪婪算法的區(qū)域規(guī)劃算法，生成的條帶集合并非全局最優(yōu)組合，后續(xù)將探索使用遺傳算法對條帶進行組合，以期獲得全局最優(yōu)組合。