何川東，王 鵬，劉曉東，崔 莉

(北京遙感信息研究所，北京 100192)

面向區(qū)域覆蓋的遙感衛(wèi)星軌道布設(shè)優(yōu)化算法

何川東，王 鵬，劉曉東，崔 莉

(北京遙感信息研究所，北京 100192)

面向區(qū)域覆蓋的遙感衛(wèi)星軌道布設(shè)是典型的多目標(biāo)優(yōu)化問題，設(shè)計(jì)具有針對(duì)性的求解模型和高效的求解算法是解決該問題的關(guān)鍵。通過分析體現(xiàn)區(qū)域覆蓋的主要評(píng)價(jià)指標(biāo)，明確問題的基本輸入輸出和先決條件，建立了該問題的多目標(biāo)優(yōu)化數(shù)學(xué)模型。根據(jù)模型特點(diǎn)，基于快速非支配排序遺傳算法NSGA-II設(shè)計(jì)了優(yōu)化算法，采用快速非支配排序、精英保持、擁擠度距離等策略，減少了計(jì)算復(fù)雜性，提高了搜索速度。仿真結(jié)果表明，基于NSGA-II的衛(wèi)星軌道布設(shè)優(yōu)化算法可以有效解決面向區(qū)域覆蓋的衛(wèi)星軌道布設(shè)問題。

區(qū)域覆蓋；遙感衛(wèi)星；軌道布設(shè)；優(yōu)化算法

AbstractIt is a typical multi-objective optimization problem to design the orbit of remote sensing satellites for the regional coverage.It is the key to solve this problem by designing a targeted model and an efficient algorithm.By analyzing the main evaluation indicator,the basic input-output and prerequisites of the problem is clarified,and the multi-objective optimization model of the problem is established.According to the characteristics of the model,the optimization algorithm is designed based on NSGA-II,which reduces the computational complexity and improves the searching speed.Simulation results show that the optimization algorithm for satellite orbit design based on NSGA-II can effectively solve the problem of satellite orbit design for regional coverage.

Keywordsregional coverage;remote sensing satellites;satellite orbit design;optimization algorithm

0 引言

針對(duì)特定區(qū)域的覆蓋成像是遙感衛(wèi)星成像任務(wù)中一類重要的成像任務(wù)，如針對(duì)重大自然災(zāi)害監(jiān)測(cè)(如地震區(qū)域覆蓋、森林火災(zāi)覆蓋、河流/近海浮冰監(jiān)測(cè)等)的區(qū)域覆蓋、國土資源普查和海洋環(huán)境監(jiān)視等，這些任務(wù)都是針對(duì)特定區(qū)域、在特定時(shí)間范圍內(nèi)、具有特定成像要求的成像任務(wù)。區(qū)域覆蓋任務(wù)一般都具有較高的時(shí)效性要求，如針對(duì)重大自然災(zāi)害的遙感圖像保障，一般具有持續(xù)時(shí)間短、范圍有限的特點(diǎn)，這就要求遙感衛(wèi)星能在較短的時(shí)間內(nèi)，對(duì)特定區(qū)域進(jìn)行無縫覆蓋?，F(xiàn)代遙感衛(wèi)星都具有軌道機(jī)動(dòng)能力，通過軌道機(jī)動(dòng)，將多顆衛(wèi)星星下點(diǎn)軌跡合理布設(shè)，可以實(shí)現(xiàn)對(duì)特定區(qū)域的無縫覆蓋。

近年來，隨著智能優(yōu)化算法的發(fā)展，采用遺傳、模擬退火和神經(jīng)網(wǎng)絡(luò)等現(xiàn)代智能優(yōu)化算法進(jìn)行衛(wèi)星軌道設(shè)計(jì)，可以在更廣泛的解空間進(jìn)行搜索，使搜索速度加快，同時(shí)搜索出的方案也更優(yōu)。文獻(xiàn)[1]針對(duì)全球連續(xù)覆蓋衛(wèi)星軌道的優(yōu)化設(shè)計(jì)，采用多目標(biāo)遺傳算法，并與 STK集成，實(shí)現(xiàn)了星座覆蓋特性的評(píng)價(jià)。文獻(xiàn)[2]以提高星座覆蓋特性與減小衛(wèi)星數(shù)量為優(yōu)化目標(biāo)，提出了基于啟發(fā)式的遺傳算法進(jìn)行區(qū)域覆蓋星座的設(shè)計(jì)。文獻(xiàn)[3]針對(duì)最大覆蓋間隙和平均覆蓋間隙2個(gè)優(yōu)化目標(biāo)，利用遺傳算法解決了稀疏星座設(shè)計(jì)問題。國內(nèi)在衛(wèi)星軌道布設(shè)及星座設(shè)計(jì)方法上也進(jìn)行了廣泛研究。文獻(xiàn)[4]研究了針對(duì)全球和區(qū)域覆蓋星座的覆蓋原理和設(shè)計(jì)方法。文獻(xiàn)[5]基于遺傳算法對(duì)區(qū)域覆蓋衛(wèi)星星座優(yōu)化設(shè)計(jì)進(jìn)行了研究。文獻(xiàn)[6]提出了一種能同時(shí)兼顧星座結(jié)構(gòu)和參數(shù)的進(jìn)化算法解決區(qū)域覆蓋衛(wèi)星星座的設(shè)計(jì)問題。

本文針對(duì)區(qū)域覆蓋的特點(diǎn)，設(shè)計(jì)了考慮最大化覆蓋次數(shù)、覆蓋率與最小化衛(wèi)星數(shù)量3個(gè)優(yōu)化目標(biāo)的數(shù)學(xué)優(yōu)化模型，提出了基于NSGA-II的衛(wèi)星軌道布設(shè)優(yōu)化算法，在有限的時(shí)間內(nèi)解決了面向區(qū)域覆蓋的遙感衛(wèi)星軌道布設(shè)問題，滿足了工程應(yīng)用的要求。

1 模型建立

數(shù)學(xué)模型是求解面向區(qū)域覆蓋的遙感衛(wèi)星軌道布設(shè)問題的基礎(chǔ)，只有將問題準(zhǔn)確的描述和界定，才能解決所提出的問題。該問題可以描述為：給定一區(qū)域和若干遙感衛(wèi)星，在一定軌道布設(shè)策略指導(dǎo)下，得到目標(biāo)區(qū)域覆蓋率最大、最大重訪時(shí)間間隔最小、衛(wèi)星數(shù)量最少的衛(wèi)星軌道布設(shè)方案，從而實(shí)現(xiàn)在特定時(shí)間段內(nèi)對(duì)特定區(qū)域的無縫覆蓋。

1.1 評(píng)價(jià)指標(biāo)

不同的遙感衛(wèi)星成像系統(tǒng)對(duì)某一個(gè)特定區(qū)域的成像能力不一樣，為了方便對(duì)不同遙感衛(wèi)星軌道布設(shè)方案進(jìn)行評(píng)價(jià)，必須定量化評(píng)價(jià)遙感衛(wèi)星對(duì)特定區(qū)域的成像能力，這種定量尺度就稱為衛(wèi)星成像能力評(píng)價(jià)指標(biāo)。為了充分比較不同遙感衛(wèi)星軌道布設(shè)方案的優(yōu)劣、體現(xiàn)特定區(qū)域目標(biāo)的成像要求，建立合適的衛(wèi)星成像能力指標(biāo)并能夠量化計(jì)算是該問題求解的關(guān)鍵[7]。從區(qū)域覆蓋角度揭示遙感衛(wèi)星對(duì)特定區(qū)域成像能力的能力指標(biāo)主要有：覆蓋次數(shù)、覆蓋率和覆蓋面積等[8]。

1.1.1 有效覆蓋面積Se

在特定時(shí)間段內(nèi)，遙感衛(wèi)星對(duì)特定區(qū)域的無重復(fù)覆蓋面積之和，即有效面積。計(jì)算有效覆蓋面積不僅需要去除單顆衛(wèi)星不同條帶之間的重復(fù)面積，還需要去除不同衛(wèi)星同一目標(biāo)點(diǎn)之間的重復(fù)面積。設(shè)衛(wèi)星e的有效覆蓋面積為：

(1)

1.1.2 覆蓋次數(shù)Cnumber(j)

遙感衛(wèi)星對(duì)特定區(qū)域內(nèi)目標(biāo)點(diǎn)覆蓋一次，稱為一次覆蓋。所有衛(wèi)星對(duì)目標(biāo)點(diǎn)只有一次覆蓋即為單重覆蓋，單顆衛(wèi)星多次或多顆衛(wèi)星覆蓋同一目標(biāo)點(diǎn)即為多重覆蓋。對(duì)于目標(biāo)區(qū)域中第j個(gè)目標(biāo)點(diǎn)的覆蓋次數(shù)Cj即為各顆衛(wèi)星覆蓋第j個(gè)目標(biāo)點(diǎn)的時(shí)間窗口數(shù)目的總和：

(2)

式中，TNej為第e(e=1,2,…k)顆衛(wèi)星對(duì)目標(biāo)點(diǎn)j的可見時(shí)間窗口的個(gè)數(shù)。

1.1.3 覆蓋率Crate

在特定時(shí)間段內(nèi)，遙感衛(wèi)星對(duì)特定區(qū)域的有效覆蓋面積之和與特定區(qū)域的面積比值即為覆蓋率。設(shè)特定區(qū)域的總面積為S，則覆蓋率定義為：

(3)

1.2 數(shù)學(xué)模型

遙感衛(wèi)星對(duì)特定區(qū)域覆蓋的軌道布設(shè)問題首先需滿足以下約束條件：

① 最大重訪時(shí)間間隔滿足用戶需求；

② 覆蓋率滿足用戶需求；

③ 地面分辨率滿足用戶需求；

④ 傳感器類型滿足用戶需求。

根據(jù)區(qū)域覆蓋的主要評(píng)價(jià)指標(biāo)，該問題求解的優(yōu)化目標(biāo)需滿足：最大化覆蓋次數(shù)、最大化覆蓋率和最小化衛(wèi)星數(shù)量。這樣，面向區(qū)域覆蓋的遙感衛(wèi)星軌道布設(shè)目標(biāo)函數(shù)為：

Max(Cnumber)，

(4)

Max(Crate)，

(5)

Min(S)。

(6)

s.t.

(7)

Crate≥Cuser，

(8)

VRmin≥VRuser，

(9)

VS≥VSuser。

(10)

2 算法研究

多目標(biāo)優(yōu)化問題由于其多個(gè)優(yōu)化目標(biāo)之間常常存在沖突，很難找到一個(gè)解在各個(gè)優(yōu)化目標(biāo)上都優(yōu)于其他解，傳統(tǒng)完全搜索算法難以滿足求解要求，現(xiàn)代智能搜索算法(隨機(jī)搜索算法)便應(yīng)運(yùn)而生，遺傳算法(GA)[9]即是現(xiàn)代智能搜索算法的一種。遺傳算法具有內(nèi)在并行性，可以對(duì)整個(gè)解空間進(jìn)行并行搜索，常用來求解傳統(tǒng)搜索算法難以解決的復(fù)雜的、非線性的問題。本文基于快速非支配排序遺傳算法設(shè)計(jì)了問題求解算法。

2.1 快速非支配排序遺傳算法NSGA-II

多目標(biāo)遺傳算法的核心就是協(xié)調(diào)各目標(biāo)函數(shù)之間的關(guān)系，找出使各目標(biāo)函數(shù)能盡量達(dá)到比較大(或比較小)的最優(yōu)解集[10]。經(jīng)典遺傳算法主要采用簡單的選擇、交叉和變異等操作步驟，對(duì)復(fù)雜應(yīng)用場(chǎng)合的求解效果并不理想，后來通過不同的遺傳基因表達(dá)方式，不同的交叉、變異算子的設(shè)計(jì)，以及一些特殊算子的引用等方式，產(chǎn)生了以經(jīng)典遺傳算法為核心的各種優(yōu)化算法。

快速非支配排序遺傳算法NSGA-II (Non-dominated Sorting Genetic Algorithm)[11]就是一種基于經(jīng)典遺傳算法產(chǎn)生的智能搜索算法?？焖俜侵渑判蜻z傳算法通過采用快速非支配排序策略、精英策略和擁擠距離策略而得到的一種多目標(biāo)進(jìn)化算法，其最顯著優(yōu)點(diǎn)就是采用了快速非支配排序和排擠機(jī)制，從而減少了計(jì)算復(fù)雜性，提高了算法搜索速度。

2.2 基于NSGA-II的衛(wèi)星軌道布設(shè)算法流程

2.2.1 染色體設(shè)計(jì)

圖1 軌道布設(shè)方案編碼表示方法

2.2.2 種群初始化

種群初始化主要有2種方式：啟發(fā)式方法和隨機(jī)方法。2種方式各有優(yōu)缺點(diǎn)，啟發(fā)式方法可以提高算法搜索速度，但可能導(dǎo)致局部最優(yōu)；隨機(jī)方法可以保證種群的多樣性，但可能降低搜索速度。本文種群初始化時(shí)采用2種方式的結(jié)合：一方面種群初始化時(shí)考慮到衛(wèi)星星下點(diǎn)軌跡的平均分布，這些解的優(yōu)化性較好，能加快搜索速度；另一方面，種群初始化時(shí)采用隨機(jī)方法，這些解的個(gè)體分布性較好，能擴(kuò)大候選解空間。

2.2.3 快速非支配排序

快速非支配遺傳算法在進(jìn)行選擇、交叉和變異等經(jīng)典遺傳算法操作步驟前，首先根據(jù)個(gè)體的支配關(guān)系對(duì)候選種群進(jìn)行分層。該步驟需要計(jì)算種群P中每個(gè)個(gè)體i的2個(gè)參數(shù)ni和Si，其中ni為種群中支配個(gè)體i的個(gè)體數(shù)，Si為種群中被個(gè)體i支配的個(gè)體集合。快速非支配排序后每個(gè)個(gè)體都得到一個(gè)屬性值，即非支配層數(shù)irank，快速非支配排序的流程如圖2所示。

圖2 快速非支配排序流程

2.2.4 擁擠距離計(jì)算

擁擠度距離的概念即：種群中給定候選解i的周圍個(gè)體密度，設(shè)為L[i]d。擁擠度距離越大說明周圍其他個(gè)體距離個(gè)體i越遠(yuǎn)，種群分布較分散，有利于擴(kuò)大解空間找到全局最優(yōu)解；擁擠度距離越小說明周圍其他個(gè)體距離個(gè)體i越近，種群分布較集中，不利于擴(kuò)大解空間搜索范圍，容易陷入局部最優(yōu)。擁擠度距離計(jì)算流程如圖3所示。

圖3 擁擠度距離計(jì)算流程

2.2.5 擁擠度選擇

經(jīng)過上述非支配排序和擁擠距離計(jì)算2個(gè)步驟，種群中的每個(gè)個(gè)體i都得到2個(gè)屬性值：非支配層數(shù)irank和擁擠距離id。隨機(jī)選擇2個(gè)個(gè)體進(jìn)行比較，選擇規(guī)則定義為：

當(dāng)irankjd時(shí)，選擇個(gè)體i。

即優(yōu)先選擇非支配層數(shù)低的；如果非支配層數(shù)一樣，則選擇擁擠度距離大的。

2.2.6 精英保持

精英保持策略是遺傳算法確保收斂的必要條件，是提高全局收斂性和搜索速度的重要方法。精英保持策略即將父代種群與其產(chǎn)生的子代種群進(jìn)行合并，共同競(jìng)爭產(chǎn)生子種群，為了防止優(yōu)良個(gè)體由于交叉、變異操作而破壞，對(duì)適應(yīng)度高的個(gè)體不進(jìn)行交叉和變異，直接復(fù)制進(jìn)入下一代子種群，這樣有利于保持父代種群中的優(yōu)良個(gè)體進(jìn)入下一代，迅速提高種群水平。精英保持的流程如圖4所示。

圖4 精英保持流程

2.2.7 算法流程

基于NSGA-II的面向區(qū)域覆蓋的遙感衛(wèi)星軌道布設(shè)優(yōu)化算法的基本流程如圖5所示。

圖5 算法流程

3 仿真實(shí)驗(yàn)

本文對(duì)算法進(jìn)行了仿真實(shí)驗(yàn)以驗(yàn)證算法的有效性，采用Windows XP操作系統(tǒng)，編程工具為VisualStudio2010。仿真中，設(shè)針對(duì)西南某地重大自然災(zāi)害監(jiān)測(cè)任務(wù)，該目標(biāo)的區(qū)域范圍為：左上角頂點(diǎn)經(jīng)緯度為(106.68°，24.27°)，右下角頂點(diǎn)經(jīng)緯度為(108.68°,22.4°)。設(shè)該任務(wù)的成像要求為最大重訪間隔時(shí)間小于10 h，面積覆蓋率大于80%，最小分辨率為3 m，傳感器類型為光學(xué)、雷達(dá)與電子3類。仿真周期設(shè)為7 d，2016年7月22日～2016年7月29日。假設(shè)總共有15顆遙感衛(wèi)星可以用于對(duì)該任務(wù)實(shí)施成像，軌道根數(shù)設(shè)為太陽同步軌道數(shù)據(jù)[12]。

上述區(qū)域任務(wù)的目標(biāo)區(qū)域范圍、成像要求以及仿真周期可以根據(jù)具體應(yīng)用要求進(jìn)行設(shè)置，只是數(shù)值變化而已，并不影響本文建立的求解模型、算法對(duì)問題求解的適用性。算法運(yùn)行后，衛(wèi)星星下點(diǎn)軌跡布設(shè)情況如圖6所示，針對(duì)該任務(wù)的軌道布設(shè)前后主要評(píng)估指標(biāo)如表1所示。

圖6 衛(wèi)星星下點(diǎn)軌跡分布示意

表1 調(diào)配方案指標(biāo)評(píng)估值

指標(biāo)調(diào)配前評(píng)價(jià)值調(diào)配后評(píng)價(jià)值變化率/%最大重訪間隔19小時(shí)3分50秒7小時(shí)10分45秒+62.34平均重訪間隔2小時(shí)49分29秒1小時(shí)47分8秒+36.78覆蓋率0.7240.916667+26.61傳感器類型330衛(wèi)星數(shù)量157-53.33

從仿真結(jié)果可以看出，針對(duì)特定區(qū)域任務(wù)，采用面向區(qū)域覆蓋策略的軌道布設(shè)模型，利用基于快速非支配排序遺傳算法的優(yōu)化算法，在較短的時(shí)間內(nèi)獲得了滿足特定任務(wù)要求的衛(wèi)星軌道布設(shè)方案。

4 結(jié)束語

本文針對(duì)面向區(qū)域覆蓋的遙感衛(wèi)星軌道布設(shè)問題，從區(qū)域覆蓋方面建立了衛(wèi)星成像能力評(píng)估指標(biāo)，并通過分析問題求解的約束條件與優(yōu)化目標(biāo)，建立了數(shù)學(xué)模型。基于快速非支配排序遺傳算法，建立了面向區(qū)域覆蓋的遙感衛(wèi)星軌道布設(shè)求解算法。仿真實(shí)驗(yàn)表明，基于快速非支配排序遺傳算法設(shè)計(jì)的衛(wèi)星軌道布設(shè)優(yōu)化算法，能考慮區(qū)域覆蓋的覆蓋次數(shù)、覆蓋率和衛(wèi)星數(shù)量等多目標(biāo)特性，能在有限時(shí)間內(nèi)快速找到符合任務(wù)要求的優(yōu)化布設(shè)方案。

[1] MASON W J,COVERSTONE-CARROLL V,HARTMANN J W.OptimalEarth orbiting satellite constellations via a Pareto Genetic Algorithm[C]∥AIAA/AAS Astrodynamics Specialist Conference and Exhibit,Boston,MA,1998:169-177.

[2] ELY T A,CROSSLEY W A,WILLIAMS E A.Satellite Constellation Design for Zonalcoverage Using Genetic Algorithms[C]∥Proceedings of the AAS/AIAA Space Flight Mechanics Meeting,Monterey,CA,1998:443-460.

[3] WILLIAMS E A,CROSSLEY W A,LANG Th J.Average and Maximum Revisit Timetrade Studies for Satellite Constellations Using a Multiobjective Geneticalgorithm[J].Journal of Astronautical Sciences,2001,49：385-400.

[4] 白鶴峰.衛(wèi)星星座的分析設(shè)計(jì)與控制方法研究[D].長沙:國防科學(xué)技術(shù)大學(xué),1999.

[5] 王瑞,馬興瑞,李明.采用遺傳算法進(jìn)行區(qū)域覆蓋衛(wèi)星星座優(yōu)化設(shè)計(jì)[J].宇航學(xué)報(bào),2002,5(3)：24-28.

[6] 陳琪鋒,戴金海,張玉琨.區(qū)域覆蓋星座結(jié)構(gòu)與參數(shù)同時(shí)優(yōu)化的進(jìn)化算法[J].系統(tǒng)工程與電子技術(shù),2004,6(3)：550-553.

[7] 李長春.成像觀測(cè)小衛(wèi)星應(yīng)急組網(wǎng)方法研究[D].長沙:國防科學(xué)技術(shù)大學(xué),2010.

[8] 魏蛟龍,岑朝輝.基于蟻群算法的區(qū)域覆蓋衛(wèi)星星座優(yōu)化設(shè)計(jì)[J].通信學(xué)報(bào),2006,27(8):68-72.

[9] 王小平,曹立明.遺傳算法[M].西安:西安交通大學(xué)出版社,2002.

[10] 雷德明,嚴(yán)新平.多目標(biāo)智能優(yōu)化算法及其應(yīng)用[M].北京:科學(xué)出版社,1985.

[11] 高媛.非支配排序遺傳算法(NSGA)的研究與應(yīng)用[D].杭州:浙江大學(xué)碩,2006.

[12] 范麗,張育林.區(qū)域覆蓋混合星座設(shè)計(jì)[J].航天控制,2007,25(6):52-55.

OptimizationAlgorithmofRemoteSensingSatellitesOrbitDesignforRegionalCoverage

HE Chuan-dong,WANG Peng,LIU Xiao-dong,CUI Li

(BeijingInstituteofRemoteSensingInformation,Beijing100192,China)

TP391

A

1003-3106(2017)11-0031-05

何川東男，(1982—)，碩士，工程師。主要研究方向：衛(wèi)星任務(wù)管理控制技術(shù)、遙感與地理信息集成技術(shù)。

10.3969/j.issn.1003-3106.2017.11.07

何川東,王鵬,劉曉東,等.面向區(qū)域覆蓋的遙感衛(wèi)星軌道布設(shè)優(yōu)化算法[J].無線電工程,2017,47(11):31-35.[HE Chuandong,WANG Peng,LIU Xiaodong,et al.Optimization Algorithm of Remote Sensing Satellites Orbit Design for Regional Coverage[J].Radio Engineering,2017,47(11):31-35.]

2016-12-09

王鵬男，(1977—)，碩士，高級(jí)工程師。主要研究方向：衛(wèi)星任務(wù)管理控制技術(shù)、規(guī)劃調(diào)度優(yōu)化算法。