尉 歡，劉志慧，王俊義，董 濤

(1.桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林 541004；2.北京衛(wèi)星信息工程研究所天地一體化信息技術(shù)國家重點實驗室，北京 100095)

0 引言

不同于傳統(tǒng)衛(wèi)星，敏捷衛(wèi)星具有三軸姿態(tài)[1]特性。因此，其具有更高的靈活性和更寬的觀測時間窗。敏捷衛(wèi)星的姿態(tài)轉(zhuǎn)換需要轉(zhuǎn)換時間且消耗星載電池電量，對規(guī)劃任務(wù)序列有一定的影響。此外，受衛(wèi)星體積限制，星載電量和內(nèi)存容量是有限的，如何在這種高動態(tài)場景下有效地利用有限的星載資源獲取盡可能多的觀測收益是衛(wèi)星任務(wù)規(guī)劃研究人員不斷追求的目標(biāo)。

對于這種高動態(tài)問題，可以利用滾動水平優(yōu)化策略[2-3]，將動態(tài)過程分解為一系列時間段，通過在時間段內(nèi)優(yōu)化規(guī)劃方案，實現(xiàn)任務(wù)的動態(tài)調(diào)度。而對于觀測任務(wù)時間窗約束和觀測衛(wèi)星星載資源約束，現(xiàn)有的敏捷衛(wèi)星任務(wù)規(guī)劃研究主要包括基于規(guī)則[4-7]或基于圖[8-10]的算法。基于規(guī)則的方法是手工編碼邏輯，計算效率高，但是對于不同的模型適應(yīng)度低?；趫D的方法簡練且適應(yīng)度高，但圖不能直接擴展將星載資源納入規(guī)劃過程。因此，以往針對該問題采用資源預(yù)規(guī)劃[11-12]策略，將問題分解為任務(wù)資源預(yù)分配和時間序列規(guī)劃2個子問題，有效提高規(guī)劃效率。然而由于空間環(huán)境的不確定性，預(yù)規(guī)劃的任務(wù)可能發(fā)生變化，所以重規(guī)劃策略[3,13]的應(yīng)用更為廣泛，通過對預(yù)規(guī)劃后的觀測任務(wù)隊列進行重調(diào)整，更加有利于減短尋優(yōu)所需時間。以上觀測任務(wù)規(guī)劃方法無法從根本上解決星載內(nèi)存有限這一問題，僅考慮了下傳任務(wù)的觀測衛(wèi)星任務(wù)規(guī)劃研究也無法克服我國的地面站多位于國內(nèi)、觀測衛(wèi)星直接將數(shù)據(jù)下傳至地面站的下傳窗口有限的問題。實際應(yīng)用中，一味追求星載內(nèi)存容量會導(dǎo)致衛(wèi)星體積過大和成本過高。目前衛(wèi)星星座已經(jīng)成為研究熱點，聯(lián)合多星任務(wù)卸載的應(yīng)用也突飛猛進，現(xiàn)有的任務(wù)卸載研究[14-15]多是假設(shè)所需要的觀測數(shù)據(jù)已經(jīng)收集并存儲到衛(wèi)星中，研究重點是多星協(xié)同下載數(shù)據(jù)至地面站，而不是觀測任務(wù)的規(guī)劃。理論上，利用衛(wèi)星星座融合任務(wù)卸載的觀測任務(wù)規(guī)劃不但可以減輕衛(wèi)星存儲資源的壓力，而且可以提高地面站接收數(shù)據(jù)的有效性和及時性，具有重要的研究意義。

針對以上問題，本文綜合考慮了衛(wèi)星姿態(tài)轉(zhuǎn)換、時間依賴的觀測收益、星載電池周期性充電，創(chuàng)新性地構(gòu)建了利用下載任務(wù)和卸載任務(wù)優(yōu)化觀測衛(wèi)星任務(wù)規(guī)劃的模型。算法上，提出了包含預(yù)規(guī)劃和重規(guī)劃2級資源分配方法的滾動雙規(guī)劃算法框架。綜合基于規(guī)則和基于圖的算法，提出了采用2級約束的基于圖適應(yīng)度的改進遺傳算法(Graph-based Fitness Evaluation Improved Genetic Algorithm,GFEGA)。

1 系統(tǒng)模型描述及分析

1.1 系統(tǒng)模型

圖1 系統(tǒng)模型Fig.1 System model

集合1：觀測任務(wù)集合

集合2：電池資源集合

Bcap是一個常數(shù)，表示星載電池容量。Bcur也是一個常數(shù)，表示當(dāng)前可用的星載電池電量。C={[cs1,ce1],[cs2,ce2],…,[csk,cek],…}表示電池充電時間區(qū)間的集合，其中csk和cek分別表示第k次充電時間區(qū)間的開始時刻和結(jié)束時刻。Br={br1,br2,…,brk,…}表示充電速率的集合，其元素brk表示在第k個充電時間區(qū)間內(nèi)的充電速率。

集合3：存儲資源集合

Dcap是一個常數(shù)，表示星載存儲容量。Dcur也是一個常數(shù)，表示當(dāng)前可用的星載存儲容量。Down={[ds1,de1],[ds2,de2],…,[dsl,del],…}表示數(shù)據(jù)下載時間區(qū)間集合，其中dsl和del分別表示第l個數(shù)據(jù)下載時間區(qū)間的開始時刻和結(jié)束時刻。Dr={dr1,dr2,…,drl,…}表示數(shù)據(jù)下傳速率集合，其元素drl表示在第l個數(shù)據(jù)下載區(qū)間內(nèi)數(shù)據(jù)下傳的速率。βd表示下載單位數(shù)據(jù)消耗的電量。OFF={[os1,oe1],[os2,oe2],…,[osg,oeg],…}表示數(shù)據(jù)卸載時間區(qū)間集合，其中osg和oeg分別表示第g個數(shù)據(jù)卸載時間區(qū)間的開始時刻和結(jié)束時刻。Or={or1,or2,…,org,…}表示數(shù)據(jù)卸載速率集合，其元素org表示在第g個數(shù)據(jù)卸載區(qū)間內(nèi)數(shù)據(jù)卸載的速率。βo表示卸載單位數(shù)據(jù)消耗的電量。

1.2 問題分析

(1)

(2)

(3)

(4)

三是卸載任務(wù)選擇變量集合A，其元素?ζ，ζ=1,2,3,…，表示觀測衛(wèi)星在時隙ζ內(nèi)是否執(zhí)行卸載任務(wù)，其值為0或1，1表示執(zhí)行卸載任務(wù)，0表示不執(zhí)行卸載任務(wù)：

本文規(guī)定觀測任務(wù)、下傳任務(wù)和卸載任務(wù)在時間上互不影響，可以同時執(zhí)行，它們相互之間不存在時間約束。以上3種任務(wù)之間的沖突源于觀測衛(wèi)星星載存儲資源和電量資源有限。敏捷觀測衛(wèi)星任務(wù)規(guī)劃的約束具體如下所示。

1.2.1 時間約束

(i∈{1,2,…,N},m∈{1,2,…,M})。

(5)

(i,j∈{1,2,…,N},m∈{1,2,…,M}),

(6)

式中，τi,j為衛(wèi)星從觀測目標(biāo)點i所需姿態(tài)轉(zhuǎn)換到觀測目標(biāo)點j所需姿態(tài)的姿態(tài)轉(zhuǎn)換時間。觀測任務(wù)時間約束的詳細信息如圖2所示。

圖2 觀測任務(wù)時間約束Fig.2 Time constraints for observation tasks

1.2.2 資源約束

本文在衛(wèi)星任務(wù)規(guī)劃過程中，將時間劃分成較多個規(guī)劃單元，在處理資源約束的過程中又將規(guī)劃單元劃分成多個較短的時隙，時隙劃分依據(jù)觀測可見窗，保證在每個時隙中最多只有一個觀測任務(wù)。時隙劃分如圖3所示，時隙ζ-1和ζ+1內(nèi)無觀測任務(wù)，時隙ζ內(nèi)有一個觀測任務(wù)。假設(shè)在時隙ζ中，即觀測任務(wù)i的第m個可見窗中，有K個電池充電時間區(qū)間，L個下載任務(wù)可見窗和G個卸載任務(wù)可見窗。

圖3 規(guī)劃單元內(nèi)時隙劃分示意Fig.3 Diagram of time slot division in planning unit

(a) 存儲資源約束

(7)

(8)

式中，αi,j表示衛(wèi)星從觀測目標(biāo)i所需姿態(tài)轉(zhuǎn)換到觀測目標(biāo)j所需姿態(tài)消耗的電量。

1.2.3 優(yōu)化問題

(9)

最終，建立優(yōu)化問題如下：

(10)

2 算法設(shè)計

以上所提的優(yōu)化問題是一個動態(tài)的混合整數(shù)規(guī)劃，求解復(fù)雜度高，屬于NP-hard問題[16-17]。因此，本節(jié)首先建立了一個滾動雙規(guī)劃的框架，將該動態(tài)問題轉(zhuǎn)換為靜態(tài)問題——混合整數(shù)規(guī)劃；然后，設(shè)計了GFEGA來求解該靜態(tài)問題。具體介紹如下。

2.1 滾動雙規(guī)劃框架

滾動雙規(guī)劃框架包括預(yù)規(guī)劃和重規(guī)劃，預(yù)規(guī)劃是為了預(yù)先公平分配電量和存儲資源，重規(guī)劃是為了調(diào)整分配資源。時間被劃分為多個長度為LU的規(guī)劃單元，相鄰規(guī)劃單元之間存在時間交叉避免硬性分割，先對這些規(guī)劃單元內(nèi)進行資源預(yù)規(guī)劃。NU個規(guī)劃單元組成一個規(guī)劃組，對每個規(guī)劃組進行Γ次重規(guī)劃，然后沿時間軸向前移動Ns個規(guī)劃單元，再取NU個規(guī)劃單元重復(fù)上述操作，直到Ω時間段內(nèi)的所有任務(wù)都被規(guī)劃完，具體情況如算法1所示。為方便起見，規(guī)劃單元長度LU小于觀測衛(wèi)星繞地運行周期。

算法1 滾動雙規(guī)劃框架輸入:1: 中的常量, , ,Ω,LU,NU,Γ,Ns(Ns

2.1.1 資源預(yù)規(guī)劃

資源預(yù)規(guī)劃的目的是提前預(yù)估出規(guī)劃范圍內(nèi)所需的總資源量，然后將資源公平地分配給每個規(guī)劃單元，避免時間上靠后的任務(wù)因缺乏星載資源而無法執(zhí)行，資源預(yù)分配的步驟如下：

步驟1以24 h為參考時間，預(yù)估該參考時間內(nèi)可恢復(fù)的資源總量R1和需要消耗的資源總量R2，其中根據(jù)電池充電區(qū)間個數(shù)預(yù)估可恢復(fù)電量，根據(jù)下載可見窗個數(shù)預(yù)估可恢復(fù)存儲容量。根據(jù)觀測可見窗個數(shù)和下載可見窗個數(shù)預(yù)估消耗資源；

步驟2預(yù)估每個規(guī)劃單元內(nèi)可選任務(wù)消耗的資源總量rε，ε=1,2,…,NU；

步驟3預(yù)估每個規(guī)劃單元的預(yù)分配資源reε=rε×(R1/R2)，ε=1,2,…,NU。

2.1.2 資源重規(guī)劃

重規(guī)劃的目的是調(diào)整資源分配，給資源利用率高的任務(wù)分配更多的資源，以提高總觀測收益。資源重分配的步驟如下：

步驟1將所有規(guī)劃單元內(nèi)未使用完的預(yù)規(guī)劃資源相加，形成第一級資源池Pool1，它是一個標(biāo)量；

步驟2將每個規(guī)劃單元已使用了的預(yù)規(guī)劃資源按重規(guī)劃調(diào)優(yōu)參數(shù)ratio(本文ratio仿真中取值0.1)分別取出一部分，不相加，形成第二級資源池Pool2，它是一個矢量；

步驟3給由于資源不足而無法執(zhí)行下載任務(wù)的規(guī)劃單元重新分配資源，先使用第一級資源池Pool1，不夠再使用第二級資源池Pool2；

步驟4將規(guī)劃單元按照資源利用率降序排列，先給資源利用率高的規(guī)劃單元分配資源，同樣優(yōu)先使用第一級資源池Pool1，規(guī)劃單元ε的資源利用率fε表示在規(guī)劃單元ε中，觀測任務(wù)總收益puε與消耗的資源總量ruε的比值，即fε=puε/ruε，ε=1,2,…,NU;

注：以上資源既可以表示電池資源也可以表示存儲資源。

2.2 基于圖適應(yīng)度的改進遺傳算法

圖5 GFEGA流程Fig.5 GFEGA flow chart

2.2.1 基于圖計算適應(yīng)度的規(guī)則

觀測任務(wù)序列的總觀測收益是適應(yīng)度的表征，本文提出利用2級約束求解染色體適應(yīng)度，第1級約束是觀測任務(wù)時間約束，根據(jù)規(guī)劃單元內(nèi)觀測任務(wù)實際開始時間和觀測收益構(gòu)造有向無環(huán)圖，利用最短路徑算法選擇出滿足時間約束的情況下總收益最高的規(guī)劃序列。第2級約束是星載資源約束，按照優(yōu)先分配電量用于下載任務(wù)，若內(nèi)存緊張限制存放觀測數(shù)據(jù)，則執(zhí)行卸載任務(wù)，釋放存儲空間的原則，選擇出滿足資源約束的規(guī)劃序列。具體操作如下：

步驟1設(shè)有向無環(huán)圖G=(V,E)，其中，V是頂點集，E是邊集，初始化V,E=?；

步驟2頂點集V中添加原點v0、終點vn+1，然后依次添加表示觀測任務(wù)的頂點vi，i=1,2,…,n，n為規(guī)劃單元內(nèi)觀測任務(wù)數(shù)量；

步驟5利用Bellman-ford算法[18]求解有向無環(huán)圖G的最短路徑，除原點v0和終點vn+1外，最短路徑上的頂點是滿足時間約束的最佳可執(zhí)行觀測任務(wù)，將相應(yīng)的選擇系數(shù)twi標(biāo)記為1，不滿足的標(biāo)記為0；

步驟6根據(jù)優(yōu)先執(zhí)行下載任務(wù)再執(zhí)行觀測任務(wù)，內(nèi)存資源緊張時執(zhí)行卸載任務(wù)的策略以及式(7)和式(8)，將既滿足時間約束又滿足資源約束的觀測任務(wù)選擇系數(shù)rwi標(biāo)記為1，否則標(biāo)記為0；

步驟7將rwi的值賦值給wi，根據(jù)式(9)更新觀測任務(wù)序列的總觀測收益。

2.2.2 分組輪盤賭選擇

通過計算每個個體的適應(yīng)度可判斷其優(yōu)劣，個體的適應(yīng)度是通過個體的觀測收益來衡量的，觀測收益越高，適應(yīng)度越強，個體越好。傳統(tǒng)的輪盤賭算子中，被選中個體的概率完全由個體的適應(yīng)度決定，這導(dǎo)致適應(yīng)度高的個體不斷繁衍，不利于種群的多樣性，甚至導(dǎo)致過早收斂于局部解。本文中分組輪盤賭選擇算子是傳統(tǒng)輪盤賭算子和隨機選擇的混合，具體操作如下。

步驟1定義種群中個體數(shù)量為ξ，分組數(shù)為ω，0≤ω≤ξ；

步驟2根據(jù)個體觀測收益降序排列；

步驟3將重新排序后的種群劃分成ω組，每組的被選概率等于該組內(nèi)所有個體的觀測收益之和除以種群的總觀測收益；

步驟4利用輪盤選擇出一個組，然后在該組中隨機選擇一個個體。

2.2.3 交叉變異規(guī)則

在規(guī)劃單元中，觀測任務(wù)可見窗序列根據(jù)相應(yīng)的觀測任務(wù)實際開始時間排序編號，因此每個染色體上的每個基因都有一個標(biāo)記編號。每條染色體代表一個觀測任務(wù)可見窗序列，染色體上的每個基因代表一個觀測任務(wù)可見窗，基因中的0和1是任務(wù)選擇變量，1表明該觀測可見窗內(nèi)執(zhí)行觀測任務(wù)，0則表明該觀測時間窗內(nèi)不執(zhí)行觀測任務(wù)。

交叉變異的規(guī)則為，首先隨機選擇交叉基因序列號；通過分組輪盤賭選擇出2條染色體作為父代1和父代2；分別從父代1和父代2中取出交叉基因序列號對應(yīng)的基因；從父代1中取出的基因按順序插入到父代2中，同理，從父代2中取出的基因按序插入到父代1中；每條染色體隨機選擇2個基因改變其任務(wù)選擇變量完成變異操作；最后，將新生成的2個子代加入種群。交叉變異的規(guī)則如圖6所示。

圖6 交叉變異規(guī)則示意Fig.6 Schematic diagram for rules of crossover and variation

3 仿真實驗

為了驗證所提模型的可行性和算法的有效性，本文開展如下仿真實驗。實驗環(huán)境包括配置為Windows 10 Inter(R) Core(TM) i5-10400 CPU @ 2.9 GHz，16 GB RAM的計算機，以及仿真軟件Matlab2018b和STK11。

3.1 參數(shù)設(shè)置

觀測衛(wèi)星軌道相關(guān)參數(shù)如表1所示。通信衛(wèi)星參數(shù)依照銥星星座設(shè)置66顆，即6個軌道面，每個軌道面11顆通信衛(wèi)星，軌道高度780 km，軌道傾角86.4°，設(shè)置觀測衛(wèi)星與通信衛(wèi)星相距1 000 km以內(nèi)且可見即可建立卸載傳輸鏈路。地面站設(shè)置10個，相關(guān)參數(shù)如表2所示。觀測任務(wù)的部分參數(shù)設(shè)置如表3所示。

表1 觀測衛(wèi)星參數(shù)Tab.1 Parameters of observation satellite

表2 地面站參數(shù)Tab.2 Parameters of ground Stations

表3 觀測任務(wù)參數(shù)Tab.3 Parameters of observation tasks

在滾動雙規(guī)劃框架下，將仿真時間范圍Ω設(shè)置為12 h。規(guī)劃單元長度LU是觀測衛(wèi)星繞地運行周期的一半。4個規(guī)劃單元組成一個重規(guī)劃組，即NU=4。重規(guī)劃次數(shù)Γ為5，滾動步長Ns為2。遺傳算法的交叉概率和變異概率如無特殊說明，均分別設(shè)為0.3和0.5。

3.2 仿真結(jié)果

以下設(shè)置了2組仿真實驗，其中用到3.1的參數(shù)如無特殊說明，均不變。

第1組仿真實驗是為了驗證本文設(shè)計的GFEGA的優(yōu)劣性，對比算法EGA[19]未使用任何編解碼規(guī)則，Rule-GA[5]采用了一種基于整數(shù)序列編碼和從后向前解碼的規(guī)則。本文設(shè)計的GFEGA則基于浮點加二進制序列編碼和有向無環(huán)圖解碼的方法。該組對比仿真實驗設(shè)置了5個仿真場景，每個場景對應(yīng)的觀測目標(biāo)點個數(shù)分別為60,70,80,90,100，下傳速率均設(shè)為100 MB/s，卸載速率均設(shè)為300 MB/s，每個場景分別采用EGA,Rule-GA和GFEGA在滾動雙規(guī)劃算法框架下進行15次實驗，并將15次的算法運行時間和總觀測收益取平均值。

平均運行時間如圖7所示，總體來看,隨著觀測目標(biāo)的增加，任務(wù)規(guī)劃所需時間也在增加，這符合數(shù)據(jù)量越大運算時間越長的實際情況。GFEGA的運行時間遠短于EGA，當(dāng)目標(biāo)點較少時，GFEGA與Rule-GA相比差別不大，但當(dāng)目標(biāo)點更多時，GFEGA的運行時間比Rule-GA更短。

圖7 算法運行時間Fig.7 Running time for algorithms

平均總觀測收益如圖8所示，隨著目標(biāo)點的增加，總觀測收益也在增加，然而當(dāng)觀測任務(wù)過多，星載資源無法滿足任務(wù)所需資源時這種增加的趨勢不再保持。

圖8 總觀測收益Fig.8 Total observation profits

時間標(biāo)準(zhǔn)化的收益是指平均總觀測收益除以相應(yīng)的平均運行時間，是對總觀測收益和規(guī)劃時間的綜合考慮，如圖9所示，GFEGA具有最佳的性能。

圖9 時間標(biāo)準(zhǔn)化的總觀測收益Fig.9 Total observation profits with time normalized

第2組實驗是為了驗證觀測任務(wù)規(guī)劃中將數(shù)據(jù)卸載至衛(wèi)星星座釋放內(nèi)存壓力的可行性。僅改變觀測衛(wèi)星數(shù)據(jù)下傳速率和卸載速率，每個場景采用GFEGA在滾動雙規(guī)劃框架下進行15次實驗，并將15次的總觀測收益取平均值，結(jié)果如圖10所示。

圖10 受下傳速率和卸載速率影響的總觀測收益Fig.10 Total observation profits with different download rates and offload rates

由圖10可以看出，相同仿真時間范圍內(nèi)，隨著觀測衛(wèi)星數(shù)據(jù)下傳速率的增大，獲得的總觀測收益增多，在數(shù)據(jù)下傳速率不變的情況下，隨著觀測衛(wèi)星數(shù)據(jù)卸載速率的增大，獲得的總觀測收益也在增多。這表明，觀測衛(wèi)星星載資源有限，及時下傳和卸載數(shù)據(jù)有利于騰出存儲空間用來存放更多的觀測任務(wù)。

4 結(jié)束語

針對時間約束和資源受限的敏捷衛(wèi)星任務(wù)規(guī)劃問題，本文不但綜合考慮了任務(wù)下傳、衛(wèi)星姿態(tài)轉(zhuǎn)換、星載電池充電以及時間依賴的觀測收益，而且創(chuàng)新性地引入了星間數(shù)據(jù)卸載，分析了星間數(shù)據(jù)卸載對觀測衛(wèi)星收益的影響，當(dāng)觀測衛(wèi)星星載存儲資源緊張時，通過將其內(nèi)存數(shù)據(jù)卸載到通信衛(wèi)星星座，可執(zhí)行更多觀測任務(wù)；但是觀測數(shù)據(jù)經(jīng)過通信衛(wèi)星再下載至地面站將會消耗額外的通信資源，增加數(shù)據(jù)傳輸成本。所以任務(wù)卸載實質(zhì)上是一種資源置換，用通信資源和電量資源換取存儲資源。平衡好這種資源置換的關(guān)系就可以獲得不錯的收益，這為今后研究觀測衛(wèi)星任務(wù)規(guī)劃提出了一種新的思路。觀測任務(wù)在不同通信衛(wèi)星間卸載的機制與策略有待進一步研究。