敏捷對(duì)地觀測衛(wèi)星自主任務(wù)調(diào)度方法

劉 嵩，孔鴻濱

(廣州城市理工學(xué)院 計(jì)算機(jī)工程學(xué)院，廣東 廣州 510812)

0 引言

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

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

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

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

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

1 問題描述與建模

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

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

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

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

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

1.1 模型的輸入輸出

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

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

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

(1)

約束條件：

(2)

bi≤bj,i

(3)

(4)

(5)

0≤Ct≤C，

(6)

(7)

(8)

xj,k≥yj,i，

(9)

(10)

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

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

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

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

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

式(7)為觀測機(jī)會(huì)約束，每個(gè)目標(biāo)最多只能被觀測一次。

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

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

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

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

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

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

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

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

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

圖4 對(duì)比圖Fig.4 Comparison chart

2.1 調(diào)度窗口

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

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

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

圖5 任務(wù)分類示意Fig.5 Task classification

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

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

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

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

2.2 執(zhí)行窗口

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

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

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

3 算法設(shè)計(jì)

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

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

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

3.1 初始解

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

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

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

3.2 鄰域結(jié)構(gòu)設(shè)計(jì)

3.2.1 末位插入鄰域

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

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

3.2.2 首位插入鄰域

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

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

3.2.3 交換鄰域

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

圖10 交換鄰域Fig.10 Exchange neighborhood

4 實(shí)驗(yàn)結(jié)果及分析

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

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

4.1 實(shí)驗(yàn)1

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

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

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

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

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

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

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

圖14 任務(wù)完成率對(duì)比Fig.14 Comparison of completion rates

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

4.2 實(shí)驗(yàn)2

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

表1 算法對(duì)比實(shí)驗(yàn)結(jié)果Tab.1 Experimental results of algorithms comparison

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

5 結(jié)束語

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

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

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

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