劉 嵩，孔鴻濱

(廣州城市理工學院 計算機工程學院，廣東 廣州 510812)

0 引言

對地觀測衛(wèi)星作為一種重要的對地觀測手段，具有覆蓋區(qū)域廣、可長時間運行和不受飛行空域限制等優(yōu)勢[1-2]，而對地觀測衛(wèi)星任務調(diào)度正是充分發(fā)揮這些優(yōu)勢的關鍵。

對地觀測衛(wèi)星任務調(diào)度負責分配衛(wèi)星觀測資源、制定觀測計劃[3]。傳統(tǒng)的對地觀測衛(wèi)星任務調(diào)度是由地面控制系統(tǒng)完成。首先要預估衛(wèi)星狀態(tài)，根據(jù)用戶需求提前為衛(wèi)星制定觀測方案，然后在特定時間將執(zhí)行指令上注至衛(wèi)星執(zhí)行[4-9]。但該過程會受到地面預估誤差、星地通信時間窗口等限制，而且指令一旦上注便無法變更，這將導致衛(wèi)星很可能錯過對重點目標的最佳成像時機，更加無法快速靈活地根據(jù)自身狀態(tài)應對隨時可能到達的動態(tài)觀測需求。

為了解決上述問題，各國學者越來越重視衛(wèi)星自主調(diào)度技術方面的研究[10-11]。一旦衛(wèi)星具備了自主調(diào)度能力，便可以隨時根據(jù)動態(tài)到達的觀測需求，在星上自主制定觀測方案，真正實現(xiàn)對地觀測數(shù)據(jù)的智能化實時服務，從而克服地面調(diào)度的弊端。

針對對地觀測衛(wèi)星自主任務調(diào)度問題，文獻[12]提出了一種基于任務軸的滾動調(diào)度策略，由于調(diào)度與執(zhí)行任務交替進行，所以調(diào)度占用的時間越長，執(zhí)行任務的時間就越短，二者存在矛盾。文獻[13-17]針對EO-1衛(wèi)星自主任務調(diào)度問題進行了深入研究，通過在星上分析重點目標的地質(zhì)現(xiàn)象是否發(fā)生變化，來決定是否觸發(fā)迭代修復算法，但這種觸發(fā)事件發(fā)生的概率較低，因此該方法對動態(tài)事件的響應能力不強。文獻[18-19]提出了一種星上隨機迭代貪婪算法，能夠解決目標被云層遮擋下的敏捷衛(wèi)星自主任務調(diào)度問題，雖然對動態(tài)事件響應能力有所提升，但是動態(tài)事件主要是指云層遮擋造成的任務取消，并沒有考慮觀測需求隨機到達的情況。文獻[20]利用迭代修復的方法進行自主任務調(diào)度，但衛(wèi)星狀態(tài)實時變化，所以修復時機很難把握，而且每一次調(diào)度的持續(xù)時間無法確定。另外，目前的研究主要針對非敏捷衛(wèi)星，而且大多只考慮觀測任務，沒有結合考慮數(shù)據(jù)回傳任務。

針對上述不足，本文首先提出了一種星上自主調(diào)度策略，明確了星上自主任務調(diào)度的時機，以及每次調(diào)度的范圍，然后針對此策略，設計了一種基于變鄰域搜索的星上自主任務調(diào)度算法，算法不僅考慮了敏捷衛(wèi)星特點，還考慮了數(shù)據(jù)回傳任務，最后通過仿真實驗驗證了該算法的有效性。

1 問題描述與建模

非敏捷對地觀測衛(wèi)星只能對目標實行過頂成像，成像時間是一定的，一旦錯過了過頂時間，將無法完成觀測任務。敏捷對地觀測衛(wèi)星則不同，在衛(wèi)星尚未到達目標正上方時，便可以通過調(diào)整俯仰角度觀測到地面目標。有效觀測范圍示意如圖1所示。

圖1 觀測范圍示意Fig.1 Observation scope

敏捷對地觀測衛(wèi)星的觀測時間窗口更長，觀測時間不再局限于過頂時間，而是可以在觀測時間窗口內(nèi)任意滑動。因此對于非敏捷對地觀測衛(wèi)星一次過境無法完成觀測的區(qū)域目標，敏捷對地觀測衛(wèi)星可以采用同一軌道多次向同一方向進行推掃的方式，完成區(qū)域目標的同軌多條帶拼接成像。條帶長度由掃描時間決定，一次推掃過程如圖2所示。敏捷性提升了衛(wèi)星的觀測能力，但更長的時間窗口也大大增加了任務調(diào)度的優(yōu)化難度。

圖2 對地觀測過程示意Fig.2 Process of earth observation

敏捷對地觀測衛(wèi)星自主任務調(diào)度問題可以描述為：面對隨時可能到達的觀測需求，敏捷對地觀測衛(wèi)星能夠在不需要或較少依靠地面人員干預的情況下，根據(jù)自身的狀態(tài)，星上自主決策調(diào)度時機和調(diào)度范圍，自主制定觀測方案，在快速響應動態(tài)觀測需求、提高觀測時效性的同時，實現(xiàn)以盡可能少的資源消耗獲取盡可能大的觀測收益。

1.1 模型的輸入輸出

模型輸入：調(diào)度開始時間p，調(diào)度結束時間q和觀測任務集合J；J中每個觀測任務j所對應的優(yōu)先級wj、占用固存大小cj、觀測持續(xù)時間oj和數(shù)據(jù)回傳持續(xù)時間dj；能夠?qū)θ蝿誮進行觀測的衛(wèi)星圈次的集合Mj，以及在圈次k對任務j進行觀測時，所對應的觀測時間窗口的開始時間sj,k和結束時間ej,k；數(shù)據(jù)回傳時間窗口集合I，I中每個數(shù)據(jù)回傳時間窗口i所對應的開始時間bi和結束時間ri；衛(wèi)星固存最大值C。

1.2 目標函數(shù)與約束條件

優(yōu)化目標是使得完成觀測任務和數(shù)據(jù)回傳任務的累積收益最大，目標函數(shù)為：

(1)

約束條件：

(2)

bi≤bj,i

(3)

(4)

(5)

0≤Ct≤C，

(6)

(7)

(8)

xj,k≥yj,i，

(9)

(10)

式(2)為觀測時間窗口約束，每個觀測任務必須在其觀測時間窗口內(nèi)被觀測。

式(3)為回傳時間窗口約束，每個數(shù)據(jù)回傳任務必須在回傳時間窗口內(nèi)被回傳。

式(4)為觀測與回傳的時間順序約束，觀測數(shù)據(jù)的回傳開始時間不能早于該目標的觀測結束時間。

式(5)為姿態(tài)轉換時間約束，當任務j與j′在第k個軌道圈次上連續(xù)執(zhí)行，則需要時間TSj,j′來完成衛(wèi)星的姿態(tài)轉換。

式(6)為衛(wèi)星存儲約束，表示任意時刻的衛(wèi)星固存Ct都不能超出衛(wèi)星最大固存C。

式(7)為觀測機會約束，每個目標最多只能被觀測一次。

式(8)為回傳機會約束，每個觀測任務的數(shù)據(jù)最多只能被回傳一次。

式(9)為觀測與回傳的邏輯關系約束，只有完成觀測的任務，其觀測數(shù)據(jù)才會被回傳。

式(10)為任務不間斷約束，任意2個觀測任務j和j′，以及2個任務所對應的數(shù)據(jù)回傳任務不能同時執(zhí)行，觀測任務和數(shù)據(jù)回傳任務不能同時執(zhí)行。

2 星上自主調(diào)度策略

星上自主調(diào)度策略的核心思想是通過縮小調(diào)度周期和調(diào)度范圍，增加調(diào)度次數(shù)，實現(xiàn)用反復進行的小規(guī)模的調(diào)度代替一次性大規(guī)模的調(diào)度。由于調(diào)度次數(shù)大幅增加，所以每一次進行調(diào)度時都能建立在最新任務信息的基礎上，從而應對動態(tài)觀測需求。

本策略規(guī)定每一次調(diào)度都包含3個步驟:步驟1建立調(diào)度窗口，即確定哪些任務參與本次調(diào)度；步驟2調(diào)度求解，即針對調(diào)度窗口內(nèi)的任務進行調(diào)度，輸出觀測任務序列作為調(diào)度結果；步驟3建立執(zhí)行窗口，即在調(diào)度結果中選擇一部分任務作為將要執(zhí)行的任務執(zhí)行方案。

第n次調(diào)度產(chǎn)生的任務執(zhí)行方案的編號為n。每一次調(diào)度都與衛(wèi)星執(zhí)行任務執(zhí)行方案同時進行，即執(zhí)行第n個任務執(zhí)行方案的同時進行第n+1次調(diào)度。第n個任務執(zhí)行方案中的最后1個任務的執(zhí)行結束時間，就是第n+1次調(diào)度的結束時間。每次調(diào)度結束后，立即開始下一次調(diào)度，因此每一次調(diào)度的開始和結束時間可以通過計算得到。自主調(diào)度策略的控制過程如圖3所示。

圖3 自主調(diào)度策略活動圖Fig.3 Activity diagram of autonomous task scheduling strategy

相比文獻[12]中調(diào)度與執(zhí)行交替進行的滾動方式，本策略的最大好處在于調(diào)度過程和任務執(zhí)行過程都是持續(xù)進行的，如圖4所示，該策略下調(diào)度的機會更多，所以能夠?qū)τ^測需求的動態(tài)變化做出快速響應。同時,執(zhí)行的時間也更長了，所以能夠充分發(fā)揮衛(wèi)星的觀測效能。

圖4 對比圖Fig.4 Comparison chart

2.1 調(diào)度窗口

建立調(diào)度窗口是每一次調(diào)度的第1個步驟。調(diào)度窗口有2個控制參數(shù)：“數(shù)量上限”和“時間跨度”。“數(shù)量上限”是指調(diào)度窗口內(nèi)任務數(shù)量的最大值；“時間跨度”要求調(diào)度窗口內(nèi)所有觀測任務時間窗口的開始時間與建立調(diào)度窗口的時間差必須小于該跨度。

建立調(diào)度窗口之前，首先要將星上的觀測任務和數(shù)據(jù)回傳任務分為4類：等待調(diào)度任務、等待執(zhí)行任務、已完成任務和執(zhí)行任務，任務類型隨時間變化。等待調(diào)度任務是指那些沒有被納入任務執(zhí)行方案，沒有確定執(zhí)行時間，正在等待調(diào)度的觀測或數(shù)據(jù)回傳任務。等待執(zhí)行任務是指那些已經(jīng)被納入任務執(zhí)行方案，確定執(zhí)行時間，但尚未被執(zhí)行的觀測或數(shù)據(jù)回傳任務。已完成任務是指那些已經(jīng)完成的觀測或數(shù)據(jù)回傳任務。執(zhí)行任務是指衛(wèi)星正在執(zhí)行的觀測或數(shù)據(jù)回傳任務。

任務分類示意如圖5所示，假設當前建立調(diào)度窗口的時刻為時刻1，即本次調(diào)度開始時刻。時刻2為相鄰的下一個調(diào)度窗口的建立時刻，即下一次調(diào)度的開始時刻。如果以時刻1為基準對任務進行分類，那么觀測任務1和數(shù)據(jù)回傳任務1屬于已完成任務。觀測任務2和數(shù)據(jù)回傳任務2屬于等待執(zhí)行任務，數(shù)據(jù)回傳任務3屬于執(zhí)行任務。等待調(diào)度任務由于沒有被賦予執(zhí)行時間段，因此沒有在圖中標出。在時刻2，圖中全部任務均屬于已完成任務。所以說這種分類方式具有動態(tài)性。

圖5 任務分類示意Fig.5 Task classification

調(diào)度窗口由等待調(diào)度任務構成。假設當前調(diào)度窗口開始時刻為t，相鄰的下一個調(diào)度窗口開始時刻為t″，“時間跨度”為T。在建立調(diào)度窗口之前，首先將所有在t″～t″+T時刻存在觀測時間窗口的等待調(diào)度任務組成觀測任務集合Observe(t)。如果Observe(t)不為空，那么按照時間窗口開始時間的先后順序?qū)τ^測任務進行排序。當任務有多個時間窗口時，依據(jù)其最早可用時間窗口參與排序。如果2個任務的時間窗口開始時間相同，則按照優(yōu)先級從高到低的順序進行排序，如果2個任務的優(yōu)先級相同，則隨機確定2個任務的前后關系。

將所有在t″～t″+T時刻存在數(shù)據(jù)回傳時間窗口的等待調(diào)度任務組成數(shù)據(jù)回傳任務集合Transmission(t)。如果Transmission(t)不為空，則任務按照從前至后，優(yōu)先級由高至低的順序進行排序。如果2個數(shù)據(jù)回傳任務的優(yōu)先級相同，則隨機確定2個任務的前后關系。

最后將Transmission(t)連接在Observe(t)之前構成一個新的任務序列，并從前至后連續(xù)選擇min(Transmission(t)+Observe(t),k)個任務構成任務集合ScheduleWin(t)，ScheduleWin(t)就是t時刻的調(diào)度窗口，k表示“數(shù)量上限”。建立調(diào)度窗口的流程如圖6所示。調(diào)度窗口建立后，即確定了調(diào)度對象，便可以運用算法進行調(diào)度求解。求解結果即調(diào)度結果，用Schedule(t)表示。Schedule(t)是一個按執(zhí)行開始時間排序的任務序列，其中的每一個任務都有明確的執(zhí)行時間段。

圖6 調(diào)度窗口構建流程Fig.6 Flow chart of scheduling window construction

2.2 執(zhí)行窗口

根據(jù)Schedule(t)建立執(zhí)行窗口。執(zhí)行窗口有2個控制參數(shù)：“執(zhí)行上限”和“間隔上限”控制。“執(zhí)行上限”是指任務執(zhí)行方案中所包含的任務數(shù)量的最大值。“間隔上限”要求任務執(zhí)行方案中前一個任務的結束時間和后一個任務的開始時間的時間間隔不能超過此上限，目的是控制任務執(zhí)行方案的松散程度，避免2個任務之間的等待時間過長。

建立執(zhí)行窗口時，在Schedule(t)中從前至后一共選擇min(|Schedule(t)|,k″)個衛(wèi)星任務構成執(zhí)行窗口，執(zhí)行窗口內(nèi)的任務序列就是任務執(zhí)行方案，而k″就是觀測方案的執(zhí)行上限。如果k″比較大，將導致執(zhí)行任務和下一次調(diào)度的持續(xù)時間變長，而調(diào)度的機會變少，最終造成對動態(tài)觀測需求的反應能力減弱。但是如果k″太小，雖然調(diào)度的機會變多，對動態(tài)觀測需求的反應能力得到提高，但調(diào)度持續(xù)時間變短，會導致調(diào)度算法的求解時間受到限制，所以優(yōu)化結果的質(zhì)量難以保證。

通過“執(zhí)行上限”可以控制執(zhí)行和調(diào)度持續(xù)時間長度，但只考慮k″得到的任務執(zhí)行方案可能比較松散。如果任務之間的時間間隔比較大，即使k″很小，整個任務執(zhí)行方案的執(zhí)行持續(xù)時間也可能會很長，從而降低調(diào)度頻率。因此需要使用“間隔上限”對任務執(zhí)行方案做進一步限制。當任務執(zhí)行方案中出現(xiàn)2個連續(xù)任務Task1和Task2，且Task1和Task2的時間間隔大于Task2及其之后的所有任務刪除，保證任務執(zhí)行方案中的任意2個連續(xù)任務的時間間隔都小于等于k?，而k?表示的就是“間隔上限”。

3 算法設計

本算法用于針對調(diào)度窗口內(nèi)的任務進行調(diào)度求解，并輸出Schedule(t)。算法的核心思想是首先利用啟發(fā)式規(guī)則生成一定數(shù)量的初始解，選取其中的最優(yōu)解作為初始解x，即搜索起點，然后進行變鄰域搜索。在每一個鄰域內(nèi)進行搜索的次數(shù)達到lmin時，則視為已經(jīng)陷入局部最優(yōu)，必須改變鄰域結構。搜索過程中，如果搜索到一個更優(yōu)的解y，則說明該鄰域有利于解的改進，并將y替換x作為搜索起點，繼續(xù)在該鄰域內(nèi)搜索。

自主調(diào)度策略根據(jù)調(diào)度的開始時間和結束時間，控制算法的開始和結束，每次調(diào)度結束時輸出當前最優(yōu)解。除此之外算法還設置了最大迭代次數(shù)lmax，當達到該條件則算法也將停止，算法流程如圖7所示。

圖7 算法流程Fig.7 Flow chart of algorithm

3.1 初始解

第1步，任務排序。首先使用文獻[12]所設計的7種排序規(guī)則對調(diào)度窗口的觀測任務進行排序，得到7種觀測任務序列。如果調(diào)度時存在已經(jīng)完成觀測但數(shù)據(jù)尚未被回傳的數(shù)據(jù)回傳任務，那么還要確定當前最早可用數(shù)據(jù)回傳時間窗口的開始時間。在觀測任務序列中從前至后尋找第一個觀測時間窗口開始時間大于該時間的觀測任務。如果存在，將數(shù)據(jù)回傳任務按高優(yōu)先級優(yōu)先規(guī)則插入該任務之前。如果不存在，則將數(shù)據(jù)回傳任務序列按高優(yōu)先級優(yōu)先規(guī)則插入到序列末端。

第2步，確定任務執(zhí)行時間并進行約束檢查。從前至后為隊列中每個任務選擇執(zhí)行的開始和結束時間。在確定任務的執(zhí)行時間時，首先使用文獻[12]所設計的時間窗口裁剪方法對該任務的時間窗口進行裁剪，避免不同任務在時間上發(fā)生重疊。將最早可用的時間窗口的開始時間作為觀測任務的開始時間。將最早可用的數(shù)據(jù)回傳時間窗口的開始時間作為數(shù)據(jù)回傳任務的開始時間。每當一個觀測任務確定了執(zhí)行時間，立即對它進行約束檢查，如果滿足約束條件，增加一個該任務所對應的數(shù)據(jù)回傳任務，否則將該任務刪除。增加的數(shù)據(jù)回傳任務按高優(yōu)先級優(yōu)先規(guī)則插入到已經(jīng)存在的數(shù)據(jù)回傳任務序列中。如果是序列中唯一的數(shù)據(jù)回傳任務，那么排序位置參照第1步中的規(guī)則。

第3步，收益計算。將收益最高的解作為初始解。

3.2 鄰域結構設計

3.2.1 末位插入鄰域

在解中任意選擇n個xj,k=1的觀測任務，將這n個任務轉移至任務序列Sequence的末端，這n個任務分別用x1，x2，…，xn表示，如圖8所示。觀測任務序列改變后，重新插入數(shù)據(jù)回傳任務。插入方法與生成初始解第1步中的插入方法一致。一般來說，如果將某些觀測任務移至序列末尾，那么這些任務能夠被執(zhí)行的可能會變得很小，但從優(yōu)化的角度來看，可以通過末位插入，增大完成其他任務的概率。

圖8 末位插入鄰域Fig.8 Final bit insertion neighborhood

3.2.2 首位插入鄰域

在解中任意選擇n個xj,k=0的觀測任務，這n個任務分別用x1，x2，…，xn表示，如圖9所示。觀測任務序列改變后，重新插入數(shù)據(jù)回傳任務。插入方法與生成初始解第一步中的插入方法一致。一般來說，如果將某些觀測任務移至序列前端，那么這些任務能夠被執(zhí)行的可能性會增加，從而有機會提高解的質(zhì)量。

圖9 首位插入鄰域Fig.9 First bit insert neighborhood

3.2.3 交換鄰域

任意選擇n個xj,k=1的觀測任務。這些任務用x1，x2，…，xn表示。然后任意選擇n個xj,k=0的觀測任務，并用y1，y2，…，yn表示這些任務。先后將x1與y1，x2與y2的位置進行交換，直到最后將xn與yn的位置進行交換，如圖10所示。觀測任務序列改變后，重新插入數(shù)據(jù)回傳任務。插入方法與生成初始解第1步中的插入方法一致。

圖10 交換鄰域Fig.10 Exchange neighborhood

4 實驗結果及分析

實驗中衛(wèi)星的軌道參數(shù)來自北美空防司令部2017年5月公布的WorldView-2衛(wèi)星軌道數(shù)據(jù)。觀測目標為點目標，分布在衛(wèi)星星下點軌跡附近。每個觀測任務都由任務編號、軌道編號、任務優(yōu)先級、觀測時間窗口和觀測持續(xù)時間等相關信息構成。

假設每個觀測任務的觀測持續(xù)時間是5～30 s，每個觀測任務的數(shù)據(jù)回傳持續(xù)時間是觀測持續(xù)時間的2倍，每個觀測任務的優(yōu)先級是1～10。實驗中用觀測持續(xù)時間代替具體的固存占用大小，假設衛(wèi)星固存最大可容納2 400 s的觀測數(shù)據(jù)。假設有1個機動地面站可以提供5個數(shù)據(jù)回傳時間窗口，單個數(shù)據(jù)回傳時間窗口平均長度為720 s。實驗計算機配置為Intel(R) Core(TM) i5-7200U CPU@2.50 GHz，內(nèi)存為8 GB，操作系統(tǒng)為Windows10，編程環(huán)境為Matlab。

4.1 實驗1

利用Simulink模塊中的有限狀態(tài)機模擬自主調(diào)度策略，確定調(diào)度時機、調(diào)度范圍，控制算法的開始和結束，并模擬任務動態(tài)到達場景。實驗場景時間設定為24 h。實驗中，“數(shù)量上限”設置為50，“時間跨度”設置為3 600 s，“執(zhí)行上限”設置為10，“間隔上限”設置為300 s。為了模擬星上有限的運算能力，假設星上算法迭代一次生成一個可行解所花費的時間為10 s。

觀測任務完成數(shù)量如圖11所示。隨著動態(tài)觀測需求數(shù)量的不斷增加，衛(wèi)星每天可以觀測的任務數(shù)量逐漸增加，并在270附近處趨于平穩(wěn)，這說明270個任務接近實驗中每天觀測的最大任務數(shù)量，這主要是由于固存和數(shù)據(jù)回傳時間窗口約束造成的。由于觀測能力限制，隨著觀測需求的不斷增加，任務完成率呈下降趨勢，如圖12所示。但如果在觀測能力范圍內(nèi)，任務完成率還是很高的，可以穩(wěn)定在90%附近。實驗中數(shù)據(jù)回傳時間窗口利用率能夠穩(wěn)定在90%附近，如圖13所示。

圖11 觀測任務完成數(shù)量Fig.11 Completion number of observing tasks

圖12 觀測任務完成率Fig.12 Completion rate of observing tasks

圖13 數(shù)據(jù)回傳時間窗口利用率Fig.13 Use rate of data backhaul time-window

數(shù)據(jù)回傳時間窗口沒有被完全利用，是因為每個數(shù)據(jù)回傳任務的回傳持續(xù)時間不同，數(shù)據(jù)回傳任務不能在不同的回傳窗口中接續(xù)回傳，所以如果數(shù)據(jù)回傳窗口剩余的時間不足以完成一個回傳任務，那么就不能執(zhí)行數(shù)據(jù)回傳。但較高的數(shù)據(jù)回傳時間窗口利用率會導致很多觀測時間窗口與數(shù)據(jù)回傳時間窗口發(fā)生重疊的觀測任務將在發(fā)生重疊的這一軌無法完成觀測，這也是無法完成全部觀測任務的一個原因。

觀測需求數(shù)量對高優(yōu)先級任務(優(yōu)先級在9以上)比例和低優(yōu)先級任務(優(yōu)先級在2以下)比例的影響并不大，如圖14所示。高優(yōu)先級任務比例保持在28%附近，而低優(yōu)先級任務比例保持在15%以下，與優(yōu)化目標一致。

圖14 任務完成率對比Fig.14 Comparison of completion rates

實驗結果表明，面對隨機到達的觀測需求，在考慮數(shù)據(jù)回傳任務和敏捷衛(wèi)星特點的同時，所提出的自主任務調(diào)度策略和自主任務調(diào)度算法能夠較好地解決敏捷對地觀測衛(wèi)星自主任務調(diào)度問題。另外，雖然較多的觀測需求可以充分發(fā)揮衛(wèi)星效能，但有限的數(shù)據(jù)回傳資源將導致大量觀測數(shù)據(jù)無法在當天回傳。

4.2 實驗2

分別使用文獻[12]中的LS算法和本算法對不同規(guī)模的衛(wèi)星任務調(diào)度問題進行求解。實驗根據(jù)任務數(shù)量分為4組，最終取平均值作為實驗結果。各組任務中10%的任務是已經(jīng)存在的數(shù)據(jù)回傳任務，其他為觀測任務。假設衛(wèi)星固存的最大值為參與調(diào)度的觀測任務的固存占用值之和的50%。lmax=100，lmin=lmax/3。實驗結果如表1所示。

表1 算法對比實驗結果Tab.1 Experimental results of algorithms comparison

在有限的迭代次數(shù)下，本算法的求解效果要優(yōu)于LS算法。這是因為本算法在搜索過程中用鄰域結構引導搜索方向。LS算法的初始解比較多，因此根據(jù)每個初始解進行迭代改進的迭代次數(shù)變得非常有限。另外，LS算法在迭代改進過程中，使用的是輪盤賭的思想，沒有明確的鄰域結構，因此在有限的迭代次數(shù)中對解的改進略顯盲目。另外，2種算法的優(yōu)化目標并不相同。LS算法中，如果一個觀測任務和其所對應的數(shù)據(jù)回傳任務不能在調(diào)度結果中同時出現(xiàn)，則沒有收益。這種方式忽略了觀測任務自身的收益，也是結果相對于本算法較差的原因之一。

5 結束語

針對星上自主任務調(diào)度問題展開研究，提出了星上自主調(diào)度策略，建立了問題的約束滿足模型，并根據(jù)星上運算能力弱的實際設計了基于變鄰域搜索的星上自主任務調(diào)度算法，主要取得了以下成果：

① 自主調(diào)度策略能夠保證在合適的時機，針對合適的任務進行星上調(diào)度，并利用反復進行的小規(guī)模的調(diào)度代替一次性大規(guī)模的調(diào)度。由于每一次調(diào)度都能建立在最新任務信息的基礎上，因此可以應對觀測需求的隨機到達。

② 針對問題建立了約束滿足模型，考慮了數(shù)據(jù)回傳任務和敏捷衛(wèi)星特點，并在此基礎上提出了一種基于變鄰域搜索的星上自主任務調(diào)度算法。算法利用鄰域結構引導搜索方向，從而保證了解的質(zhì)量。

③ 實驗結果表明，算法在自主調(diào)度策略的控制下能夠?qū)︻l繁到達的觀測需求進行快速響應，達到了設計預期。另外相比較LS算法，本算法針對不同問題規(guī)模，均有更好的表現(xiàn)。