李海玲，黨 琦

(1. 西安航空學(xué)院計算機(jī)學(xué)院，西安 710077； 2. 在軌航天器故障診斷與維修重點實驗室，西安 710043)

1 引言

隨著空間技術(shù)的發(fā)展和空間應(yīng)用不斷的深入，衛(wèi)星成像任務(wù)調(diào)度技術(shù)日漸發(fā)展成為航天應(yīng)用領(lǐng)域的研究熱點。賀仁杰等建立了合成任務(wù)的衛(wèi)星成像調(diào)度模型，提出了快速模擬退火算法[1]；郭玉華等提出了針對NP-Hard特性的組合優(yōu)化問題的復(fù)雜約束成像衛(wèi)星調(diào)度算法[2]；李泓興等提出了一種加入精英策略的改進(jìn)蟻群算法[3]；盧盼等建立了基于貪婪算法原理的衛(wèi)星調(diào)度約束模型[4]；李軍等提出了成像任務(wù)約束圖模型和多目標(biāo)遺傳算法[5]；王鈞等建立了成像衛(wèi)星調(diào)度的多目標(biāo)有向無環(huán)約束圖模型，提出了基于SPEA2(Strength Pareto Evolutionary Algorithm2)的多目標(biāo)成像調(diào)度算法[6]；孫凱等建立了基于階段優(yōu)化的成像衛(wèi)星星地聯(lián)合調(diào)度模型[7]。

這些模型和算法雖然解決了不同條件下成像衛(wèi)星任務(wù)規(guī)劃問題，有些方法也取得了實際的應(yīng)用，但因為考慮約束比較多，算法較為復(fù)雜，計算量比較大，不適合應(yīng)急條件下快速成像任務(wù)規(guī)劃要求。王智勇等實現(xiàn)了衛(wèi)星連續(xù)側(cè)擺成像規(guī)劃算法和基于任務(wù)優(yōu)先級的數(shù)傳任務(wù)調(diào)度算法[8]，但是并沒有對如何確定優(yōu)先級給出分析和討論，目前也尚未發(fā)現(xiàn)有學(xué)者對成像任務(wù)快速規(guī)劃流程進(jìn)行研究。

本文在上述學(xué)者研究成果的基礎(chǔ)上，針對應(yīng)急條件快速規(guī)劃需求，提出一種基于成像任務(wù)優(yōu)先級的快速任務(wù)規(guī)劃流程。通過對成像任務(wù)規(guī)劃中的各個過程的分析和分解，建立星歷和星下點計算模型，從目標(biāo)的重要程度和緊急程度兩個方面出發(fā)，給出成像任務(wù)的優(yōu)先級和優(yōu)先級確定過程，設(shè)計一種基于目標(biāo)優(yōu)先級的快速成像任務(wù)規(guī)劃流程，可通過分布式或并行計算提高任務(wù)規(guī)劃效率。

2 成像目標(biāo)可見預(yù)報

衛(wèi)星成像任務(wù)過程可劃分為成像目標(biāo)確定、目標(biāo)可見預(yù)報、可見條帶生成、成像任務(wù)規(guī)劃、動作編排、成像控制過程注入、成像過程執(zhí)行與成像圖片下傳八步，衛(wèi)星成像規(guī)劃實質(zhì)上是規(guī)劃衛(wèi)星成像控制過程注入和圖片下傳兩個過程之間的衛(wèi)星成像過程，如果已經(jīng)確定了衛(wèi)星成像控制過程注入以及圖片下傳時間，那么衛(wèi)星成像任務(wù)規(guī)劃將變成對這段時間內(nèi)衛(wèi)星可見條帶內(nèi)的目標(biāo)進(jìn)行選擇的一個過程。

成像衛(wèi)星一般設(shè)計為近地軌道，其飛行軌跡提供一維向前運(yùn)動，星載儀器側(cè)視掃描提供另一維的側(cè)向運(yùn)動(側(cè)擺)，這樣，衛(wèi)星在繞地飛行的過程中，會在地球表面產(chǎn)生一條二維掃描帶，衛(wèi)星只能對掃描條帶內(nèi)的目標(biāo)進(jìn)行成像觀測(拍照)，如圖1所示。

圖1 成像衛(wèi)星對地觀測條帶示意圖Fig.1 Schematic diagram of the earth observation band of the imaging satellite

2.1 衛(wèi)星星歷計算

2.2 星下點軌跡計算

成像衛(wèi)星的星下點軌跡一般是一條首尾相接的封閉曲線。根據(jù)2.1節(jié)計算所得到的地心系星歷，由公式(1)、(2)計算得到赤經(jīng)α和赤緯δ[11]。

(1)

(2)

2.3 目標(biāo)可見預(yù)報

根據(jù)星下點軌跡，結(jié)合衛(wèi)星的飛行高度以及衛(wèi)星側(cè)擺能力，由幾何關(guān)系確定衛(wèi)星可視范圍內(nèi)的目標(biāo)，其模型參見圖2。

圖2 相機(jī)可視范圍示意圖Fig.2 Schematic diagram of camera visual range

(3)

3 成像任務(wù)優(yōu)先級確定

衛(wèi)星可觀測條帶內(nèi)會有很多目標(biāo)，由于受衛(wèi)星存儲空間的限制，一般情況下不可能對條帶內(nèi)所有的目標(biāo)都進(jìn)行成像，最好的辦法是根據(jù)目標(biāo)的重要程度和緊急程度確定其觀測優(yōu)先級。

3.1 目標(biāo)重要程度

根據(jù)成像目標(biāo)的重要程度將其劃分為極端重要(extremely)、特別重要(specially)、非常重要(very)、比較重要(fairly)和一般(oftenly)5個級別，其值參見表1。

3.2 目標(biāo)緊急程度

根據(jù)成像目標(biāo)的緊迫程度，將其劃分為緊急(urgency)、高(high)、一般(normally)、較低(bellow normal)、低優(yōu)先級(idle)5個級別，其值參見表2。

表1 目標(biāo)重要程度

表2 目標(biāo)緊急程度

3.3 成像優(yōu)先級確定

構(gòu)造目標(biāo)重要程度矩陣Ii和緊急程度矩陣Uj分別如式(4)、(5)：

(4)

(5)

然后定義優(yōu)先級矩陣Pij如式(6)：

(6)

顯然Pij是一個對稱矩陣，去掉重復(fù)項后，可得14個級別的成像優(yōu)先級，用向量p表示為p=(pi)=(25,20,16,15,12,10,9,8,6,5,4,3,2,1)。pi數(shù)值越大，任務(wù)的優(yōu)先級越大。

4 基于優(yōu)先級的成像任務(wù)規(guī)劃

本節(jié)不考慮衛(wèi)星成像任務(wù)上行注入，單就對某衛(wèi)星可視范圍內(nèi)的目標(biāo)進(jìn)行任務(wù)規(guī)劃。

4.1 點目標(biāo)成像任務(wù)規(guī)劃算法

對于衛(wèi)星Sk，假設(shè)星載存儲器的容量為Mk，在其掃描條帶內(nèi)有nk個目標(biāo)，目標(biāo)ik的圖片所占空間為mki(mki>0)，目標(biāo)ik的價值(優(yōu)先級)為vki(vki>0)，找出一個nk元的0-1向量(x1,x2,…,xnk)，如式(7)所示，使最終拍攝的圖片的總價值最大，且滿足式(8)所示約束條件。

(7)

(8)

假設(shè)衛(wèi)星高度確定，圖像幅寬確定、分辨率和大小也確定，則有mki≡1。在具體解算時，根據(jù)衛(wèi)星有無側(cè)擺能力，分別用兩種計算方法。

4.1.1 衛(wèi)星無側(cè)擺能力

無側(cè)擺能力衛(wèi)星的可見條帶由星下點軌跡和照片幅寬確定，則問題簡化為一維序列問題，目標(biāo)選擇與否完全決定于成像優(yōu)先級。

取vki=Pki，則問題進(jìn)一步簡化為0-1背包問題，即組合優(yōu)化的NP完全問題[12]。該問題可使用貪婪算法、動態(tài)規(guī)劃算法進(jìn)行求解，也可以用蟻群算法、遺傳算法等智能算法求解。貪婪算法做出的選擇只是在某種意義上的局部最優(yōu)選擇，對許多問題都能產(chǎn)生全局最優(yōu)解。動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題，這類須滿足最優(yōu)化原理、無后效性和重疊性。蟻群算法是一種正反饋的算法，求解結(jié)果不依賴于初始路線的選擇，算法的參數(shù)數(shù)目少，設(shè)置簡單，適合多種組合優(yōu)化問題的求解。遺傳算法全局搜索能力強(qiáng)，可快速地搜索出解空間中的全體解，算法具有內(nèi)在并行性，可進(jìn)行分布式計算，但其局部搜索能力較差，后期搜索效率較低，易產(chǎn)生過早收斂的問題[13-14]。

4.1.2 衛(wèi)星有側(cè)擺能力

此時可假設(shè)某時段內(nèi)衛(wèi)星可視條帶內(nèi)分布有如圖3(a)所示的從a到i的觀測目標(biāo)，受衛(wèi)星側(cè)擺、側(cè)擺效率約束。從一個側(cè)擺狀態(tài)到下一個側(cè)擺狀態(tài)，從衛(wèi)星側(cè)擺到載荷穩(wěn)定，需要耗費(fèi)時間和能量，因此不一定能夠?qū)λ心繕?biāo)進(jìn)行觀測。從圖3(a)中目標(biāo)的分布情況看，如果對目標(biāo)b實施觀測，就不能對目標(biāo)c進(jìn)行觀測，如果觀測了目標(biāo)c，則不能對目標(biāo)d進(jìn)行成像觀測。此時問題便轉(zhuǎn)化為有向無環(huán)圖的拓?fù)渑判騿栴}，增加始頂點S和結(jié)束頂點T之后，形成如圖3(b)所示的有向連通圖，加入載荷資源消耗后，可使用拓?fù)渑判颉⑦z傳算法等解決這類規(guī)劃問題[12]。

圖3 衛(wèi)星觀測條帶內(nèi)可選目標(biāo)示意圖Fig.3 Schematic diagram of optional objects in the satellite observation band

4.2 點目標(biāo)成像任務(wù)規(guī)劃流程

成像任務(wù)規(guī)劃過程主要是對衛(wèi)星成像控制過程注入以及衛(wèi)星成像圖片下傳時間段內(nèi)衛(wèi)星可見條帶中的目標(biāo)進(jìn)行選擇的一個過程，由此，我們對衛(wèi)星成像任務(wù)規(guī)劃流程進(jìn)行了梳理和簡化，主要包括：

1)用戶需求收集和受理。收集、確定各用戶目標(biāo)觀測需求，包括確定目標(biāo)觀測時段、分辨率、重訪要求、經(jīng)緯度、優(yōu)先級、下傳時間等內(nèi)容。

2)與測控資源協(xié)調(diào)協(xié)商。主要完成衛(wèi)星成像控制過程注入和衛(wèi)星成像圖片下傳測控資源和時間確定。

3)衛(wèi)星成像任務(wù)規(guī)劃。包括目標(biāo)可見預(yù)報、可見條帶生成、成像任務(wù)規(guī)劃、成像動作編排、成像控制過程注入等。針對各衛(wèi)星的規(guī)劃設(shè)計為獨立的進(jìn)程，由主程序控制、創(chuàng)建，主程序管理并維護(hù)觀測目標(biāo)池，各衛(wèi)星成像任務(wù)進(jìn)程通過與觀測目標(biāo)池交互，確定自己的觀測目標(biāo)序列，并通過與主程序之間的協(xié)商協(xié)調(diào)，對目標(biāo)進(jìn)行置換或要求衛(wèi)星調(diào)整軌道參數(shù)。具體見圖4。

圖4 衛(wèi)星成像任務(wù)規(guī)劃流程Fig.4 Task scheduling process of satellites imaging

5 結(jié)語

本文通過對成像衛(wèi)星可見預(yù)報算法進(jìn)行了討論，通過目標(biāo)的重要程度和緊急程度，計算確定了成像任務(wù)的優(yōu)先級，并設(shè)計了一種基于目標(biāo)優(yōu)先級的快速成像任務(wù)規(guī)劃流程，該流程可通過各衛(wèi)星成像規(guī)劃分布式或并行計算，提高任務(wù)規(guī)劃效率。