遙感衛(wèi)星組網(wǎng)觀測(cè)資源調(diào)度中的數(shù)學(xué)建模與優(yōu)化問(wèn)題

劉永信, 王玲琳, 張 暉, 王朝霞, 楊 治

(1.內(nèi)蒙古大學(xué) 電子信息工程學(xué)院,內(nèi)蒙古 呼和浩特 010021;2.內(nèi)蒙古師范大學(xué) 應(yīng)用數(shù)學(xué)中心,內(nèi)蒙古 呼和浩特 010022)

將多顆遙感衛(wèi)星組網(wǎng)可實(shí)現(xiàn)對(duì)地球表面特定區(qū)域的任意時(shí)段、全天候、多要素連續(xù)監(jiān)測(cè),可以滿足應(yīng)對(duì)突發(fā)應(yīng)急事件監(jiān)測(cè)的需要。遙感衛(wèi)星組網(wǎng)觀測(cè)可以利用現(xiàn)有的衛(wèi)星資源,結(jié)合不同軌道衛(wèi)星的優(yōu)化部署和小衛(wèi)星快速發(fā)射補(bǔ)網(wǎng)等手段實(shí)現(xiàn)。衛(wèi)星組網(wǎng)觀測(cè)通過(guò)分析常規(guī)或應(yīng)急觀測(cè)任務(wù)需求,優(yōu)化設(shè)計(jì)資源分配調(diào)度模型和實(shí)現(xiàn)算法,可為感興趣區(qū)域的連續(xù)觀測(cè)提供技術(shù)支持。遙感衛(wèi)星組網(wǎng)觀測(cè)的技術(shù)路線如圖1所示。對(duì)于常規(guī)觀測(cè)任務(wù),根據(jù)現(xiàn)有衛(wèi)星資源構(gòu)建常規(guī)分配調(diào)度模型,設(shè)計(jì)算法進(jìn)行優(yōu)化求解; 針對(duì)突發(fā)應(yīng)急事件,以觀測(cè)任務(wù)對(duì)模式手段、時(shí)空分辨率等的具體技術(shù)指標(biāo)為依據(jù),設(shè)計(jì)衛(wèi)星資源應(yīng)急分配模型和算法,從空間系統(tǒng)的魯棒性出發(fā),優(yōu)化在軌衛(wèi)星和載荷的分配調(diào)度策略,優(yōu)先滿足應(yīng)急任務(wù)的要求; 如果衛(wèi)星和載荷數(shù)無(wú)法達(dá)到任務(wù)要求,視情啟動(dòng)衛(wèi)星軌道優(yōu)化部署機(jī)制或發(fā)射待命小衛(wèi)星重新構(gòu)建網(wǎng)絡(luò),通過(guò)多顆衛(wèi)星組網(wǎng)協(xié)同觀測(cè),實(shí)現(xiàn)對(duì)目標(biāo)任務(wù)的快速應(yīng)急響應(yīng)。

圖1 遙感衛(wèi)星組網(wǎng)觀測(cè)的技術(shù)路線Fig.1 The technology roadmaping of remote sensing satellite network observation

如何實(shí)現(xiàn)快速準(zhǔn)確高效的遙感衛(wèi)星資源組織,最大限度利用衛(wèi)星資源、擴(kuò)大觀測(cè)范圍是目前遙感衛(wèi)星組網(wǎng)觀測(cè)的難點(diǎn)。構(gòu)建資源分配調(diào)度數(shù)學(xué)模型,設(shè)計(jì)問(wèn)題的優(yōu)化求解、分配調(diào)度策略是解決該類問(wèn)題的關(guān)鍵。本文建立了遙感衛(wèi)星組網(wǎng)觀測(cè)資源調(diào)度需解決的資源調(diào)度數(shù)學(xué)建模,并討論了模型優(yōu)化求解的相關(guān)數(shù)學(xué)問(wèn)題。

1 常規(guī)觀測(cè)任務(wù)的數(shù)學(xué)建模

針對(duì)遙感衛(wèi)星組網(wǎng)的常規(guī)觀測(cè),國(guó)內(nèi)外專家發(fā)展了多種數(shù)學(xué)模型。法國(guó)Gabrel等[1]基于圖論思想構(gòu)建了衛(wèi)星調(diào)度問(wèn)題的加權(quán)有向無(wú)環(huán)圖模型,利用有向無(wú)環(huán)圖的成像路徑表示衛(wèi)星在多個(gè)任務(wù)間轉(zhuǎn)換方式,采用最短路徑算法對(duì)問(wèn)題進(jìn)行求解。該模型具有簡(jiǎn)單直觀的優(yōu)勢(shì),不足之處在于未考慮載荷開(kāi)關(guān)機(jī)時(shí)間約束對(duì)有向圖拓?fù)浣Y(jié)構(gòu)的影響。法國(guó)國(guó)家空間研究中心Lematre[2]提出衛(wèi)星觀測(cè)地球任務(wù)指的是根據(jù)客戶觀測(cè)需求獲取地球表面特定圖像,并且把敏捷衛(wèi)星觀測(cè)地球問(wèn)題(AEOS)簡(jiǎn)化為地球軌道選擇和衛(wèi)星資源調(diào)度問(wèn)題,根據(jù)任務(wù)請(qǐng)求的權(quán)重、決策變量、可視性以及角度約束建立最大質(zhì)量準(zhǔn)測(cè)模型,利用動(dòng)態(tài)規(guī)劃算法求解,可以在短時(shí)間內(nèi)獲得良好的解決方案。

美國(guó)加利福尼亞州宇航局艾姆斯研究中心Frank[3]在多顆衛(wèi)星調(diào)度問(wèn)題中考慮任務(wù)優(yōu)先級(jí)、觀測(cè)時(shí)間窗以及衛(wèi)星星上存儲(chǔ)等約束條件,提出了一種基于約束描述模型,鑒于問(wèn)題復(fù)雜度較高,設(shè)計(jì)啟發(fā)式隨機(jī)搜索算法來(lái)解決該問(wèn)題,并且開(kāi)發(fā)了EUROPA調(diào)度系統(tǒng)。2003年5月美國(guó)分析成像公司(AGI)推出一款衛(wèi)星調(diào)度軟件STK/Scheduler,該軟件模塊基本集成了衛(wèi)星觀測(cè)和數(shù)傳過(guò)程中的約束,不僅給出了Neural Network、Random等求解算法,并且具備用戶編寫算法的功能接口,以消除約束的方式獲取任務(wù)最大完成度并且給出分配方案甘特圖。

賀仁杰[4]針對(duì)成像衛(wèi)星調(diào)度問(wèn)題建立了混合整數(shù)規(guī)劃模型和約束滿足模型,使用禁忌搜索算法和Solver求解器結(jié)合的方式來(lái)求解模型,得到令人滿意的結(jié)果。韓傳奇[5]針對(duì)衛(wèi)星組網(wǎng)調(diào)度問(wèn)題建立最長(zhǎng)觀測(cè)時(shí)間簡(jiǎn)單規(guī)劃模型和復(fù)雜規(guī)劃函數(shù),在模型中考慮了用戶觀測(cè)時(shí)間約束,衛(wèi)星時(shí)間窗口約束以及衛(wèi)星存儲(chǔ)約束,簡(jiǎn)單目標(biāo)函數(shù)下的衛(wèi)星整數(shù)規(guī)劃模型分別使用遺傳算法和貪心算法進(jìn)行求解,討論了兩種算法在不同任務(wù)規(guī)模場(chǎng)景下對(duì)求解質(zhì)量和速度方面的適用性。針對(duì)復(fù)雜目標(biāo)函數(shù)下的規(guī)劃模型,使用模擬退火算法改進(jìn)后的遺傳算法對(duì)其求解,提高了求解效率并且優(yōu)化了解的質(zhì)量。蔡德榮[6]根據(jù)衛(wèi)星是否觀測(cè)任務(wù)(決策變量)和任務(wù)收益建立最大任務(wù)優(yōu)先級(jí)調(diào)度模型,模型中考慮的約束比較全面,不僅包括衛(wèi)星觀測(cè)動(dòng)作約束,而且考慮了衛(wèi)星星載存儲(chǔ)器上限約束、數(shù)據(jù)下傳動(dòng)作等約束條件。針對(duì)模型和車輛路線問(wèn)題求解的相似性,使用蟻群算法求解模型。王凌峰[7]為實(shí)現(xiàn)對(duì)熱點(diǎn)目標(biāo)區(qū)域持續(xù)性觀測(cè)和周期性獲取目標(biāo)態(tài)勢(shì)需求,根據(jù)衛(wèi)星觀測(cè)任務(wù)開(kāi)始觀測(cè)和結(jié)束觀測(cè)時(shí)間窗口、任務(wù)優(yōu)先級(jí)以及調(diào)度周期建立了最小超時(shí)程度目標(biāo)函數(shù),模型中考慮了衛(wèi)星兩次開(kāi)機(jī)最短間隔約束、單次開(kāi)機(jī)約束、單圈最長(zhǎng)開(kāi)機(jī)時(shí)間約束以及單天最大開(kāi)機(jī)次數(shù)約束。使用貪心搜索算法求解模型,給出了算法的具體求解思路。實(shí)驗(yàn)結(jié)果表明,貪婪搜索算法能夠有效求解衛(wèi)星組網(wǎng)周期性持續(xù)觀測(cè)任務(wù)問(wèn)題。

衛(wèi)星調(diào)度模型方面主要有圖模型、背包問(wèn)題模型、整數(shù)規(guī)劃模型以及約束滿足模型。其中圖模型利用有向無(wú)環(huán)圖觀測(cè)任務(wù)路徑表示衛(wèi)星在多個(gè)任務(wù)間的轉(zhuǎn)換方式,采用最短路徑算法求解模型,不足之處在于有向無(wú)環(huán)圖本身?xiàng)l件限制無(wú)法加入太多約束條件,因此無(wú)法準(zhǔn)確描述衛(wèi)星調(diào)度問(wèn)題。背包問(wèn)題模型表示衛(wèi)星調(diào)度問(wèn)題時(shí)具有形式簡(jiǎn)單等優(yōu)點(diǎn)[8],可以使用水平約束對(duì)多個(gè)維度的衛(wèi)星資源進(jìn)行約束,其主要缺點(diǎn)是無(wú)法表示一些復(fù)雜實(shí)際約束條件。整數(shù)規(guī)劃模型可以描述衛(wèi)星調(diào)度問(wèn)題中的線性約束條件,但是整數(shù)規(guī)劃問(wèn)題求解較難,問(wèn)題規(guī)模增大時(shí),需要設(shè)計(jì)有效的分支定界策略提高求解效率。此時(shí)通常借助一些復(fù)雜問(wèn)題分解方法,比如使用列生成算法找到問(wèn)題最優(yōu)解的緊湊上界對(duì)尋優(yōu)化過(guò)程進(jìn)行指導(dǎo),主要缺點(diǎn)為無(wú)法處理一些復(fù)雜的非線性約束條件。約束滿足模型可以描述非線性約束條件和非線性目標(biāo),主要描述若干目標(biāo)必須滿足多個(gè)約束條件,該模型能夠簡(jiǎn)單直觀表示變量和約束,可選擇成熟的約束規(guī)劃軟件工具對(duì)該問(wèn)題進(jìn)行求解。雖然模型有較強(qiáng)的描述能力,但模型求解時(shí)需要考慮約束傳播,通用約束傳播算法由于缺乏有效分支定界策略導(dǎo)致求解效率較低。

2 突發(fā)應(yīng)急事件觀測(cè)任務(wù)的數(shù)學(xué)建模

2.1 衛(wèi)星軌道優(yōu)化觀測(cè)的數(shù)學(xué)建模

遙感衛(wèi)星組網(wǎng)在實(shí)現(xiàn)對(duì)地球表面全天時(shí)多方位常態(tài)化觀測(cè)的同時(shí)還要滿足重點(diǎn)地區(qū)的特殊觀測(cè)。在應(yīng)對(duì)突發(fā)應(yīng)急事件時(shí),需要第一時(shí)間獲取事發(fā)地點(diǎn)的實(shí)時(shí)狀態(tài),這對(duì)遙感衛(wèi)星軌道重構(gòu)和優(yōu)化部署的計(jì)算時(shí)間要求很高。針對(duì)重點(diǎn)地區(qū)的突發(fā)應(yīng)急事件,主要由事件發(fā)生的時(shí)間、地點(diǎn)、事件類型等因素來(lái)決定何種傳感器可獲取所需數(shù)據(jù),從而確定哪些衛(wèi)星可執(zhí)行該任務(wù)。在此過(guò)程中,可能出現(xiàn)現(xiàn)有衛(wèi)星無(wú)法監(jiān)測(cè)到的情況,對(duì)于這種狀況就要考慮衛(wèi)星軌道重構(gòu)的方法。

在遙感衛(wèi)星軌道重構(gòu)方面,主要由衛(wèi)星軌道高度以及所使用傳感器工作方式?jīng)Q定,以星載合成孔徑雷達(dá)為例[9-10],低軌道遙感衛(wèi)星由于軌道高度低,入射角和斜視角受到約束大則波束的有效覆蓋范圍較小,與高軌道衛(wèi)星相比,探測(cè)范圍受到極大的影響。理想狀態(tài)下,衛(wèi)星軌道主要由開(kāi)普勒定律的6個(gè)軌道參數(shù)所決定,但在實(shí)際運(yùn)行過(guò)程中還會(huì)受到各種攝動(dòng)力和地球扁平所影響,對(duì)于衛(wèi)星軌道的重構(gòu)也必須考慮衛(wèi)星的運(yùn)行狀態(tài)。在軌道預(yù)測(cè)方面,主要采用SGP4模型對(duì)衛(wèi)星軌跡進(jìn)行預(yù)測(cè)[11-12],模型主要表現(xiàn)為除去計(jì)算六根數(shù),還需考慮地球非球形引力、大氣阻力、月球引力和太陽(yáng)潮汐等多種攝動(dòng)力對(duì)衛(wèi)星運(yùn)行的影響,該模型可較為準(zhǔn)確地對(duì)衛(wèi)星軌道進(jìn)行計(jì)算。此外,遙感衛(wèi)星所攜帶的傳感器觀測(cè)覆蓋范圍也是必須要考慮的因素之一。孟少飛[13]提出了一種基于二維圖理論的模型可快速解決衛(wèi)星覆蓋統(tǒng)計(jì)問(wèn)題,先通過(guò)衛(wèi)星與觀測(cè)點(diǎn)的幾何關(guān)系,建立二維圖的解析數(shù)學(xué)模型,再對(duì)照傳感器覆蓋范圍模型計(jì)算其覆蓋性能,從而減少計(jì)算量,并建立對(duì)于整個(gè)任務(wù)的執(zhí)行性能評(píng)估體系,二維圖理論在針對(duì)覆蓋性能的衛(wèi)星軌道評(píng)估中得到廣泛應(yīng)用[14]。在對(duì)遙感衛(wèi)星的軌道進(jìn)行重構(gòu)后,針對(duì)衛(wèi)星運(yùn)行速度及軌道避障規(guī)劃等性能還可進(jìn)一步優(yōu)化。

在軌道優(yōu)化方面,主要分為兩種模式,一種是針對(duì)具體衛(wèi)星運(yùn)動(dòng)模型,從模型中各參數(shù)著手,進(jìn)行參數(shù)修正以達(dá)到運(yùn)動(dòng)軌跡最優(yōu)的效果[15]。此類方法主要應(yīng)用于特殊衛(wèi)星和飛船,不具有普適性,且依賴于運(yùn)動(dòng)模型,需進(jìn)行精確建模,適用小衛(wèi)星和飛船,計(jì)算精度高,速度較快。但缺點(diǎn)也很明顯,對(duì)于大多數(shù)衛(wèi)星來(lái)說(shuō),運(yùn)動(dòng)模型無(wú)法做到精確的建模,因此方法的準(zhǔn)確性降低。第二種是運(yùn)用神經(jīng)網(wǎng)絡(luò)優(yōu)化各個(gè)參數(shù),從而達(dá)到校正衛(wèi)星運(yùn)動(dòng)軌道誤差的目的,這種方法針對(duì)一些不確定性的規(guī)律現(xiàn)象十分適用,因此也得到了更為廣泛的應(yīng)用。遺傳算法以及通過(guò)遺傳算法優(yōu)化的神經(jīng)網(wǎng)絡(luò)方法效果比較明顯[16-19],通過(guò)迭代優(yōu)化的算法優(yōu)化各個(gè)參數(shù),將其代入軌道模型中,以達(dá)到修正軌道的目的,但相比上一種模式,這類優(yōu)化過(guò)程通常需要大量計(jì)算,以及一定量的數(shù)據(jù)積累,因此計(jì)算速度較慢,對(duì)于一些對(duì)實(shí)時(shí)性要求比較嚴(yán)格的對(duì)象來(lái)說(shuō),該方法不太適用。兩類優(yōu)化模式各有優(yōu)缺點(diǎn),需從實(shí)際需求出發(fā)選擇適合的方法。

2.2 發(fā)射快速響應(yīng)小衛(wèi)星補(bǔ)網(wǎng)模式的數(shù)學(xué)建模

發(fā)射快速響應(yīng)(以下簡(jiǎn)稱“快響”)小衛(wèi)星補(bǔ)網(wǎng)模式是指,當(dāng)現(xiàn)有衛(wèi)星觀測(cè)網(wǎng)絡(luò)中的資源不能滿足觀測(cè)任務(wù)要求,且觀測(cè)任務(wù)持續(xù)周期相對(duì)較長(zhǎng),不便或不能通過(guò)在軌衛(wèi)星優(yōu)化部署的方式完成觀測(cè)任務(wù)時(shí),采用發(fā)射提前儲(chǔ)備的小衛(wèi)星,通過(guò)快速部署衛(wèi)星網(wǎng)絡(luò)資源,以滿足觀測(cè)任務(wù)需要的衛(wèi)星組網(wǎng)應(yīng)急觀測(cè)資源分配調(diào)度方式?；谲娛?、應(yīng)急救援等應(yīng)用的需要,國(guó)內(nèi)外已對(duì)發(fā)射快響衛(wèi)星以滿足監(jiān)測(cè)任務(wù)的方法進(jìn)行了一定的研究。David等[20]提出發(fā)射快響衛(wèi)星的理念,并從體系結(jié)構(gòu)的角度進(jìn)行了闡述。Wertz等[21]針對(duì)重點(diǎn)地區(qū)觀測(cè)的需要,提出如何根據(jù)需求設(shè)計(jì)快響衛(wèi)星的發(fā)射方式。陳盈果等[22]以快響衛(wèi)星為對(duì)象,研究面向任務(wù)的快響系統(tǒng)衛(wèi)星部署優(yōu)化問(wèn)題及求解方法。高璐等[23]探討了快響衛(wèi)星的軌道設(shè)計(jì)問(wèn)題。

發(fā)射快響小衛(wèi)星補(bǔ)網(wǎng)的本質(zhì)是一個(gè)軌道設(shè)計(jì)與資源預(yù)估問(wèn)題,應(yīng)用此模式時(shí)需要重點(diǎn)解決兩個(gè)方面的關(guān)鍵內(nèi)容：如何根據(jù)需要合理選擇小衛(wèi)星在空間運(yùn)行時(shí)的軌道及參數(shù); 對(duì)于多目標(biāo)多任務(wù)的需求,如何確定該衛(wèi)星應(yīng)該攜帶的傳感設(shè)備及技術(shù)參數(shù)。解決問(wèn)題的核心方法就是建模及求解,下面圍繞以上兩方面內(nèi)容中涉及的數(shù)學(xué)問(wèn)題進(jìn)行探討。

衛(wèi)星的軌道形狀和在軌道中位置通常采用星軌道六根數(shù)確定。其中,軌道半長(zhǎng)軸和偏心率決定衛(wèi)星軌道的大小和形狀,軌道傾角和升交點(diǎn)赤經(jīng)決定衛(wèi)星軌道在空間中的平面方位,近地點(diǎn)幅角決定衛(wèi)星相對(duì)于近地點(diǎn)的方向。對(duì)于快響小衛(wèi)星軌道的選擇,需要考慮其傳感器覆蓋范圍、應(yīng)急能力、分辨率、發(fā)射成本等問(wèn)題,如何在滿足觀測(cè)任務(wù)的要求下,設(shè)計(jì)合理的衛(wèi)星軌道或給出幾種衛(wèi)星軌道的設(shè)計(jì)方案是數(shù)學(xué)建模時(shí)需要重點(diǎn)考慮的問(wèn)題。

對(duì)于分辨率要求較高的觀測(cè)地域,要限制軌道高度,最好采用低軌軌道; 而對(duì)于覆蓋能力要求較高,分辨率要求相對(duì)較低的任務(wù),則可考慮采用中高軌道; 對(duì)于響應(yīng)時(shí)間較短的應(yīng)急任務(wù),應(yīng)選擇傾斜軌道,根據(jù)觀測(cè)目標(biāo)的分布特性確定傾角大小,確保能夠全覆蓋; 對(duì)觀測(cè)頻率有嚴(yán)格要求,或者要求連續(xù)觀測(cè)不間斷的任務(wù),設(shè)計(jì)軌道時(shí)必須嚴(yán)格遵循回歸條件,能夠與現(xiàn)有衛(wèi)星資源在觀測(cè)時(shí)間上實(shí)現(xiàn)無(wú)縫對(duì)接。

衛(wèi)星對(duì)地觀測(cè),最終要依靠SAR、可見(jiàn)光相機(jī)、多光譜掃描儀、波譜儀、散射計(jì)、高度計(jì)、鹽度計(jì)等星載傳感器來(lái)實(shí)現(xiàn),衛(wèi)星對(duì)具體目標(biāo)的具體空間和時(shí)間覆蓋屬性也是基于傳感器實(shí)現(xiàn)的。針對(duì)觀測(cè)任務(wù)的需要,如何計(jì)算出快響小衛(wèi)星需要攜帶的具體傳感器及傳感器完成觀測(cè)任務(wù)應(yīng)具備的技術(shù)參數(shù)也是數(shù)學(xué)建模及求解需要重點(diǎn)考慮的問(wèn)題。

如果觀測(cè)任務(wù)需要成像,需要根據(jù)成像要求選擇使用SAR、可見(jiàn)光相機(jī)或紅外成像儀等傳感設(shè)備,并根據(jù)分辨率等細(xì)節(jié)要求計(jì)算設(shè)備的技術(shù)參數(shù); 對(duì)單次觀測(cè)的持續(xù)時(shí)間有明確要求的任務(wù),選取衛(wèi)星傳感器的波束大小及最小覆蓋范圍需要準(zhǔn)確計(jì)算; 對(duì)于觀測(cè)有優(yōu)先級(jí)的任務(wù),建模及計(jì)算傳感設(shè)備技術(shù)參數(shù)時(shí),首先要滿足高優(yōu)先級(jí)的任務(wù); 對(duì)于需持續(xù)觀測(cè)的循環(huán)性任務(wù),要結(jié)合觀測(cè)頻率(或重訪周期)考慮重復(fù)完成觀測(cè)任務(wù)所需的傳感設(shè)備數(shù)量; 基于任務(wù)的最大完成率,確定發(fā)射小衛(wèi)星的數(shù)量及不同小衛(wèi)星需要攜帶的不同傳感器數(shù)量。

除以上建模及優(yōu)化求解時(shí)需要考慮的問(wèn)題外,實(shí)際發(fā)射快響小衛(wèi)星時(shí),還需要考慮如下問(wèn)題：衛(wèi)星及傳感器運(yùn)行時(shí)的能量限制,如傳感器最大開(kāi)機(jī)時(shí)間; 衛(wèi)星自身的信息存儲(chǔ)能力、衛(wèi)星之間以及衛(wèi)星與地面站之間的信息傳輸能力; 觀測(cè)目標(biāo)的建模問(wèn)題,如點(diǎn)、面等; 衛(wèi)星的工作壽命及發(fā)射成本; 發(fā)射及運(yùn)行過(guò)程中的外部因素干擾,如電離層、云層等大氣條件。為使有限的衛(wèi)星資源能夠被最大限度地利用,以滿足應(yīng)急情況下的觀測(cè)需要,同時(shí)兼顧常態(tài)化觀測(cè)任務(wù),需要在合理的假設(shè)條件下,建立一個(gè)包含未知需求解因素的多類衛(wèi)星資源多復(fù)雜觀測(cè)任務(wù)的數(shù)學(xué)模型,并進(jìn)行實(shí)時(shí)優(yōu)化求解,得到發(fā)射快響小衛(wèi)星的數(shù)量、軌道參數(shù)及所攜帶傳感器的數(shù)量及技術(shù)參數(shù),設(shè)計(jì)出能夠取得最大調(diào)度收益的資源分配調(diào)度方案,在較短時(shí)間內(nèi)取得符合客戶需求的結(jié)果。而且,數(shù)學(xué)模型越接近實(shí)際、實(shí)用性越強(qiáng),則要求建模時(shí)考慮的問(wèn)題越復(fù)雜、越精準(zhǔn),模型的參數(shù)、約束條件越多、相互關(guān)系越復(fù)雜,則建模和優(yōu)化求解的難度越大。

為解決這類問(wèn)題,國(guó)內(nèi)外學(xué)者大多構(gòu)建多目標(biāo)優(yōu)化模型,先后提出了多目標(biāo)進(jìn)化、多目標(biāo)差分進(jìn)化等算法尋求優(yōu)化解的方案。也有學(xué)者提出將快速發(fā)射小衛(wèi)星軌道機(jī)動(dòng)模型的機(jī)動(dòng)過(guò)程描述為L(zhǎng)ambert軌道轉(zhuǎn)移問(wèn)題[22],進(jìn)而基于決策者參與的多目標(biāo)差分進(jìn)化算法進(jìn)行求解。然而,在現(xiàn)有的發(fā)射快響小衛(wèi)星補(bǔ)網(wǎng)乃至常態(tài)化多任務(wù)多目標(biāo)衛(wèi)星資源組網(wǎng)觀測(cè)數(shù)學(xué)建模過(guò)程中,大多假設(shè)觀測(cè)目標(biāo)可近似為點(diǎn)目標(biāo),一顆衛(wèi)星只攜帶一個(gè)傳感器,忽略了區(qū)域覆蓋與點(diǎn)覆蓋的差別,將衛(wèi)星協(xié)同與傳感器協(xié)調(diào)近似等同,也忽略了能量、成本、壽命、外界條件等因素的限制[20-25],構(gòu)建出的數(shù)學(xué)模型相對(duì)較為理想化,與實(shí)際應(yīng)用相差較遠(yuǎn),這正是需要重點(diǎn)改進(jìn)的方向。

3 遙感衛(wèi)星組網(wǎng)觀測(cè)資源調(diào)度的優(yōu)化求解問(wèn)題

面對(duì)常規(guī)和應(yīng)急觀測(cè)需求,建立不同的遙感衛(wèi)星組網(wǎng)模型,需要設(shè)計(jì)相應(yīng)的算法進(jìn)行求解,主要用到的算法包括智能優(yōu)化算法、貪婪算法、動(dòng)態(tài)規(guī)劃算法以及樹搜索算法。

智能優(yōu)化算法在衛(wèi)星調(diào)度問(wèn)題中應(yīng)用廣泛,它是一種迭代改進(jìn)的非精確搜索算法,求解結(jié)果的最優(yōu)性往往取決于耗費(fèi)的時(shí)間長(zhǎng)度,并且該算法可在任何迭代的過(guò)程返回一個(gè)可行解[26],設(shè)計(jì)時(shí)需要一定技巧,為了獲取更好的實(shí)驗(yàn)結(jié)果需要對(duì)算法的某些參數(shù)進(jìn)行多次實(shí)驗(yàn)。智能優(yōu)化算法沒(méi)有固定形式,在資源分配、調(diào)度等領(lǐng)域應(yīng)用性較強(qiáng),典型的智能優(yōu)化算法有遺傳算法、粒子群算法、模擬退火算法以及蟻群算法等。

貪婪算法按照提前設(shè)計(jì)好的啟發(fā)式規(guī)則對(duì)可行解進(jìn)行逐步構(gòu)造,在整個(gè)計(jì)算過(guò)程中不需要迭代。主要缺點(diǎn)為不能保證最終求解結(jié)果最優(yōu)性,不能給出可行解和最優(yōu)解之間差異[27]。當(dāng)其它算法在有限時(shí)間內(nèi)無(wú)法求出最優(yōu)解時(shí),可以選擇貪婪算法對(duì)可行解逐步構(gòu)造。在衛(wèi)星調(diào)度問(wèn)題中,設(shè)計(jì)合理的貪婪啟發(fā)式規(guī)則是求解關(guān)鍵因素,一般啟發(fā)式規(guī)則設(shè)計(jì)方式有兩種: 第一種按照衛(wèi)星與任務(wù)之間可見(jiàn)時(shí)間窗口的先后順序?qū)θ蝿?wù)進(jìn)行逐個(gè)安排; 第二種按照任務(wù)優(yōu)先級(jí)的高低順序?qū)σ?guī)劃任務(wù)進(jìn)行逐個(gè)安排?？梢栽谒惴ㄋ阉鬟^(guò)程中引入隨機(jī)機(jī)制對(duì)貪婪算法進(jìn)行改進(jìn)。

動(dòng)態(tài)規(guī)劃算法主要將衛(wèi)星調(diào)度問(wèn)題分解為若干個(gè)子問(wèn)題進(jìn)行求解,動(dòng)態(tài)規(guī)劃算法通常按照衛(wèi)星星下點(diǎn)軌跡與地面目標(biāo)的地理位置關(guān)系確定觀測(cè)任務(wù)的執(zhí)行順序[2],主要從衛(wèi)星調(diào)度時(shí)間、星載存儲(chǔ)容量、衛(wèi)星載荷能力等方面對(duì)問(wèn)題進(jìn)行求解,該問(wèn)題的求解時(shí)間較長(zhǎng),可通過(guò)在每一步保存最優(yōu)解的方式降低時(shí)間復(fù)雜度。該算法缺陷在于當(dāng)待規(guī)劃任務(wù)具有多個(gè)衛(wèi)星觀測(cè)時(shí)間窗口時(shí),即任務(wù)分配的時(shí)間窗口有多個(gè),則不能很好確定全局最優(yōu)解。

樹搜索算法分為深度優(yōu)先搜索和最佳優(yōu)先搜索兩種,深度優(yōu)先搜索可以較快生成初始解,并且算法占用的內(nèi)存空間較小,可以從多個(gè)點(diǎn)出發(fā)搜索,該算法對(duì)初始搜索節(jié)點(diǎn)的選擇依賴性較強(qiáng),導(dǎo)致解的性能不夠理想[28]。最佳優(yōu)先搜索是廣度搜索算法的改進(jìn),使用啟發(fā)函數(shù)對(duì)將要遍歷的點(diǎn)進(jìn)行估價(jià),并且以最小代價(jià)為準(zhǔn)則,直到遍歷完成所有的點(diǎn)。該算法解的性能較優(yōu),需要存儲(chǔ)空間較大,生成解的時(shí)間較長(zhǎng)。

4 結(jié)語(yǔ)

衛(wèi)星組網(wǎng)調(diào)度問(wèn)題主要包括建立衛(wèi)星調(diào)度模型和設(shè)計(jì)相應(yīng)算法求解模型兩部分內(nèi)容。在遙感衛(wèi)星組網(wǎng)觀測(cè)建模過(guò)程中還有許多問(wèn)題有待解決,如何準(zhǔn)確建立衛(wèi)星覆蓋的資源模型仍是最主要的議題,理論與實(shí)際干擾因素相結(jié)合的精確建模目前還沒(méi)有出現(xiàn),是未來(lái)急需解決的問(wèn)題。除此之外,如何處理傳感器工作模式與衛(wèi)星運(yùn)動(dòng)狀態(tài)的關(guān)系也十分重要,這關(guān)系著是否可以最大程度利用傳感器獲取有效信息,希望可以從數(shù)學(xué)關(guān)系中找到對(duì)應(yīng)的解決辦法,以達(dá)到最高的利用率和最大的觀測(cè)范圍。