基于GA-SA的低軌星座傳感器資源調度算法

劉建業(yè), 王 華, 周晚萌

(國防科技大學空天科學學院, 湖南 長沙 410073)

0 引 言

天基預警衛(wèi)星系統(tǒng)是完整彈道導彈防御體系中的一個重要環(huán)節(jié),它可以近實時地發(fā)現(xiàn)并監(jiān)視彈道導彈等目標。其中,天基紅外低軌星座(如STSS)能夠對自由段彈道進行全程跟蹤監(jiān)視,可以無縫接力高軌星座對目標的觀測,因此受到越來越多的重視,成為導彈防御體系中的重要一環(huán)。低軌星座一般采取24星部署,分布于3個軌道面,軌道高度約1 600 km。因此,在對目標進行跟蹤監(jiān)視時,系統(tǒng)不可避免的需要進行多傳感器對多目標調度問題的求解,這是一個典型的組合優(yōu)化NP-hard問題。目前,受保密條例限制,很難獲取國外有關預警衛(wèi)星傳感器方面的資源,只能查閱借鑒一些一般領域的調度方法,Fatos等[1]利用遺傳算法對對地觀測衛(wèi)星的傳感器資源調度管理進行了研究,相較隨機搜索其計算效率有了很大提升;Ayed等[2]針對衛(wèi)星廣播調度問題,以衛(wèi)星成功調度次數(shù)為目標函數(shù),采用二進制編碼的差分進化算法對該調度問題進行求解;文獻[3-4]提出了一種基于任務合并的蟻群優(yōu)化算法,可以將調度問題規(guī)模減少從而提高求解效;文獻[5]采用分布式凸優(yōu)化方法,提出了一種針對N維離散線性時間系統(tǒng)的隨機調度策略;Hernadez M L[6]針對單目標跟蹤問題,提出了一種基于后驗克拉美-羅下界(posterior Cramer-Rao lower bound,PCRLB)的傳感器管理方法,是一種以跟蹤精度為優(yōu)化目標的傳感器管理方法;Shudai等[7]針對柔性車間調度問題,提出了一種高效的啟發(fā)式遺傳算法,可以有效的降低加工成本;文獻[8]針對多目標貝葉斯濾波,以后驗期望誤差為優(yōu)化目標,基于部分可觀察馬爾可夫決策過程,提出了一種傳感器控制方法;文獻[9]以目標跟蹤過程中的預測協(xié)方差矩陣為控制變量,同時考慮傳感器使用時的能量消耗,設計了一種可以延長傳感器使用生命周期的調度方法。

國內針對預警系統(tǒng)傳感器資源調度問題的研究也還處于發(fā)展階段。李國輝等[10]以調度成功率、目標跟蹤精度以及傳感器網絡的能源消耗為指標,提出了一種分群粒子群優(yōu)化的傳感器調度方法,但該方法是一種全局最優(yōu)解,需要全部的彈道信息,而實際的預警過程中無法提前獲取全部信息,且全局優(yōu)化比較耗時;趙硯等[11]利用PCRLB計算不同傳感器調度方案帶來的信息增量差別,設計了基于PCRLB的傳感器滾動時域調度算法,然而僅考慮跟蹤精度的調度策略,可能會使衛(wèi)星工作超載導致系統(tǒng)產生故障;文獻[12]提出了衛(wèi)星貢獻度的概念,并以衛(wèi)星貢獻度、觀測切換率以及衛(wèi)星松弛度為目標函數(shù),采用遺傳算法求解衛(wèi)星調度策略,但是其需假設目標彈道為提前已知;文獻[13]通過分析預警實際需求,設計了一種預警衛(wèi)星傳感器資源調度策略,但是該方法只能針對一些特殊的場景,應用范圍有限;文獻[14-15]采用改進的粒子群算法對預警任務進行規(guī)劃調度,但是其均缺少對目標的跟蹤能力研究,與實際需求有所偏頗;文獻[16]基于預警衛(wèi)星傳感器探測原理,設計了一種基于聚類的預警衛(wèi)星傳感器資源調度方法,但是其調度策略僅考慮了跟蹤精度,缺少對系統(tǒng)工作效率的考量;目前,針對調度問題研究比較成熟的是車間調度問題,文獻[17-18]采用了遺傳算法對車間調度問題進行求解,該求解方法對于衛(wèi)星傳感器資源調度具有一定的參考性。

上述研究為預警衛(wèi)星傳感器資源的調度建立了基礎,有效提高了預警系統(tǒng)的工作性能,但是在預警任務規(guī)劃的實時性與系統(tǒng)利用的全面性方面還有改進之處:①文獻[11,16]缺乏對系統(tǒng)工作效率的考慮,其調度策略可能會使系統(tǒng)負載過大以致產生故障,文獻[14-15]的關注點為任務的成功執(zhí)行,缺乏對跟蹤精度的考慮,這與實際需求有所不符;②文獻[10,12]需要假設目標彈道為已知,然后進行全彈道預警任務規(guī)劃,與預警真實約束是不符的。

因此,本文綜合考慮了調度的實時性與性能評價的全面性,采用滾動周期調度的方法,以調度周期內的PCRLB變化率表征系統(tǒng)信息增量,以衛(wèi)星跟蹤目標的切換率衡量系統(tǒng)工作效率,建立了以跟蹤精度與衛(wèi)星切換率為目標的傳感器調度混合整數(shù)規(guī)劃模型,然后采用GA-SA混合優(yōu)化算法求解傳感器調度策略。最后,仿真實驗表明本文算法可以在保證跟蹤精度的同時,很好的兼顧到系統(tǒng)效率,對未來的預警衛(wèi)星反導具有一定的參考價值。

1 目標跟蹤模型

對于目標跟蹤,假設在某一時刻選擇衛(wèi)星傳感器對該目標進行探測,則對目標進行跟蹤的過程就是利用各傳感器在某時刻探測到的目標信息,基于一定的跟蹤模型并采用相應的濾波器進行該時刻目標狀態(tài)估計的過程。

(1)

對于目標觀測,本文采用雙衛(wèi)星對運動目標進行探測,通過衛(wèi)星上的紅外敏感器測量機動目標相對衛(wèi)星的方位角與仰角。目標相對各衛(wèi)星的視線矢量方向在衛(wèi)星軌道坐標系中用方位角A與仰角E表示,如圖1所示。

圖1 觀測模型Fig.1 Observation model

(2)

由圖1可知,目標方位角、仰角計算為

(3)

從而目標雙星觀測模型為

νk+1,i=1,2

(4)

基于上述目標跟蹤模型,在結合相應的濾波器,就可以實現(xiàn)對目標的跟蹤估計。

2 調度評價指標

建立合理的評價指標是進行調度的前提和依據?？紤]到跟蹤精度與系統(tǒng)工作效率,從兩個方面建立評價指標。首先從跟蹤精度的角度出發(fā),需要保證每個調度周期內傳感器系統(tǒng)獲取足夠的目標跟蹤信息,這一指標以調度周期內目標跟蹤的PCRLB變化率來定量描述;其次,從傳感器系統(tǒng)工作效率的角度出發(fā),需要盡可能減少傳感器的損耗并提高跟蹤的穩(wěn)定性,這一指標以傳感器切換率來定量描述。因此,調度評價指標就由表示系統(tǒng)信息量獲取的PCRLB變化率,表示系統(tǒng)效率的傳感器切換率構成。目標函數(shù)由它們加權求和計算,各指標的權值通過經驗確定。

PCRLB是系統(tǒng)可達最佳跟蹤性能的一種度量,作為任何無偏估計方差的下界,它給出了一定假設條件下狀態(tài)估計的方差極限,在狀態(tài)估計的統(tǒng)計性能分析中扮演著重要角色。所以本文以每個調度周期內PCRLB的變化率來衡量系統(tǒng)跟蹤性能。

PCRLB代表了某時刻對目標估計值與真值的誤差協(xié)方差陣的下界,即

(5)

(6)

式中,Qk-1為系統(tǒng)過程噪聲噪聲方差;Rk為觀測噪聲方差,Φk-1為狀態(tài)轉移矩陣;Hk為觀測矩陣。每個狀態(tài)變量的PCRLB定義為信息矩陣逆的相應對角線元素的平方根,即

(7)

同時,考慮到衛(wèi)星紅外探測器的觀測量只與目標狀態(tài)的位置分量有關,進行目標狀態(tài)濾波的測量更新時,觀測量只對位置分量的估計有貢獻,因此最終定義調度周期內PCRLB變化率,即系統(tǒng)信息增量為

(8)

式中,M表示調度周期內追蹤目標數(shù)量,分母項表示調度周期開始時刻所有追蹤目標的位置分量的PCRLB之和,分子項表示調度周期內所有追蹤目標位置分量的PCRLB變化量之和。

在整個調度周期內,在考慮跟蹤精度的同時,也需要兼顧系統(tǒng)效率,由此引入可以用于描述參與調度的所有衛(wèi)星傳感器資源運行效率的指標,本文通過統(tǒng)計衛(wèi)星觀測目標變換次數(shù),進而確定衛(wèi)星切換率來描述預警系統(tǒng)的工作效率。

考慮到PCRLB變化率指標為越大調度效果越好,因此衛(wèi)星傳感器切換率計算按式(9)計算,SS越大,表明衛(wèi)星切換率越低,衛(wèi)星監(jiān)視效率越高。

(9)

式中,M表示跟蹤的目標數(shù)量;switchi表示第i個參與跟蹤的衛(wèi)星在整個調度周期內更換跟蹤目標的次數(shù);Ni表示目標i的觀測任務數(shù)量。

3 調度優(yōu)化算法

3.1 調度模型

以調度周期內系統(tǒng)跟蹤目標的PCRLB變化率與衛(wèi)星切換率加權求和得到目標函數(shù),進一步考慮衛(wèi)星與目標運動狀態(tài)的可預測性,建立預警系統(tǒng)周期調度優(yōu)化模型,具體為

maxf=ω1ΔI+ω2SS

s.t.ω1+ω2=1

(10)

3.2 基于GA-SA的混合優(yōu)化算法

GA算法[18]是一種基于“適者生存”的進化算法,它把問題參數(shù)編碼為染色體,再利用迭代方式進行選擇、交叉及變異等運算來交換種群中染色體的信息,最終生成符合優(yōu)化目標的染色體。該算法具有編碼與遺傳操作簡單,隱含并行和全局搜索的優(yōu)點,但是其進化緩慢、易早熟、局部尋優(yōu)能力差等缺點。SA算法[18]的出發(fā)點是基于物理物理固體物質的退火過程與一般組合優(yōu)化問題之間的相似性,利用Metropolis準則以一定概率接受惡化解從而跳離局部最優(yōu)的陷阱,但是其全部收斂的時間性能較差。GA-SA算法結合了二者的特點,使兩種算法優(yōu)勢互補,提高了問題求解的效率。

基于GA-SA算法的特點,本文采用該算法求解預警系統(tǒng)傳感器資源調度策略,算法流程如下:

步驟1建立衛(wèi)星傳感器資源集S與目標集T。

步驟2建立調度周期內各目標觀測子任務集OPi,j。

步驟3目標與衛(wèi)星軌跡預測,根據各種約束條件建立各目標觀測子任務集OPi,j對應的傳感器資源集OPSi,j,其中傳感器資源的建立采用均勻劃分可見時間弧段的方法進行,具體方法如圖2所示。

圖2 目標觀測子任務劃分示意圖Fig.2 Submission partitioning of target observation

其中,針對在子任務時間弧段內衛(wèi)星觀測時間不足的傳感器資源,如[0,10]窗口內的衛(wèi)星S2,如果其可見時長不足任務時間弧段的一半,則將其舍棄,否則將其作為該子任務的偽傳感器資源,使用時在該資源不可見時段內采用單星濾波的方法對目標進行跟蹤。

步驟4執(zhí)行GA-SA優(yōu)化算法,計算調度決策,如圖3所示,然后當預警時間推進到當前調度周期時,執(zhí)行該調度決策,進行目標的跟蹤估計。

圖3 GA-SA算法流程Fig.3 Flow chart of GA-SA

步驟5預警未結束則重復執(zhí)行步驟3到步驟4,否則預警結束。

除此之外,采用GA-SA算法,其優(yōu)化算子需要特別的設計,具體方法為:

(1) 調度染色體編碼策略

染色體采用基于觀測任務與預警傳感器資源一一對應的多層整數(shù)編碼技術,每條染色體表示調度周期內所有衛(wèi)星傳感器對目標的觀測序列。設每個目標在調度周期內的觀測序列為P個,則染色體個體長度為3MP。其中,染色體前1/3表示所有目標的觀測序列,后2/3表示每次觀測對應的衛(wèi)星編號,且當目標的某次觀測只有一顆衛(wèi)星或沒有可用衛(wèi)星時,在染色體衛(wèi)星編號處將該次觀測的衛(wèi)星編號以0取兩次表示,編碼實例如圖4所示。

圖4 編碼示意圖
Fig.4 Sketch map of encoding

(2) 適應度函數(shù):最優(yōu)調度就是使得目標函數(shù)f取得最大值的調度,因此將目標函數(shù)f作為染色體個體的適應度函數(shù)。

(3) 交叉、變異操作:以交叉概率Pc隨機從父代中選擇兩個個體進行交叉運算。從編碼設計可以看出,染色體目標序列代表了觀測時間順序,因此交叉點發(fā)生在目標序列位置處,同時其對應的觀測衛(wèi)星也一同交叉。本文基于此原理采用順序交叉方法,可以保留并融合不同排列的染色體結構;變異操作采用單點位置變異方式,首先從父代種群中隨機選擇變異個體,并以變異概率Pm選擇變異的目標序列位置,然后利用該序列處觀測目標的當前可用衛(wèi)星進行隨機置換。

(4) Metropolis準則抽樣:計算交叉變異前后的個體適應度變化量,即

Δf=f(father)-f(son)

(11)

如果Δf<0,則接受新的個體為當前個體;否則計算p=exp(-Δf/T),其中T為當前溫度,如果p>rand,也接受新的個體為當前個體;否則保留父代個體為當前個體。

(5) 算法終止:結束條件設置為當連續(xù)10代種群的平均適應度值小于某一極小閾值時,算法終止,否則按照Tk=αTk-1進行退溫,并疊加進化代數(shù),繼續(xù)執(zhí)行算法。

4 仿真結果及分析

本文仿真場景中,天基預警系統(tǒng)星座采用3×8部署,包含3條軌道,每條軌道上均勻布置8顆衛(wèi)星,衛(wèi)星間隔45°,衛(wèi)星高度1 600 km,軌道傾角103°,衛(wèi)星傳感器采樣頻率設置為1 s,觀測誤差σLOS=100 μrad,調度周期70 s,目標跟蹤估計采用UKF算法。利用STK軟件生成3個待跟蹤目標,在發(fā)射后40 s進入自由段。目標具體參數(shù)如表1所示。

表1 目標參數(shù)表

針對上述場景設置,本文利用8.00 GB RAM的Intel(R)/3.40 GHz進行仿真,以Matlab R2016b為仿真軟件。算法參數(shù)設置為:交叉概率Pc=0.6,變異概率Pm=0.5,種群規(guī)模N=100,最大進化代數(shù)Gen=50,初溫T0=80°,退溫速率α=0.8,目標函數(shù)權值的取法為:當ΔI>0.75時,ω1=0.7、ω2=0.3;當ΔI≤0.75時,ω1=0.2、ω2=0.8。這是因為隨著目標跟蹤估計的穩(wěn)定,目標估計的PCRLB變化率,即ΔI會逐漸減少,甚至當跟蹤收斂時,ΔI會趨于零,此時需將ΔI的權值減少。

仿真計算時將目標的預警觀測任務等時間間隔(10 s)劃分為21個子任務,并分別采用GA與GA-SA混合算法進行迭代求解,第一個調度周期內的迭代過程如圖5所示。

圖5 GA-SA與GA算法迭代過程Fig.5 Iteration of GA and GA-SA

由圖4可以看出,GA-SA混合算法相較GA算法,其對最優(yōu)解的搜索具有更高的效率,在相同的迭代次數(shù)內擴大解的搜索范圍,從而可以得到更優(yōu)的解。

第1個調度周期內各調度方案下優(yōu)化指標見表2。

表2 GA與GA-SA優(yōu)化結果

可知對于本文場景下的預警系統(tǒng)低軌星座傳感器資源調度,GA-SA的優(yōu)化結果總體上較GA優(yōu)一些,對于表中的切換率,由式(9)可知,GA-SA與GA的實際切換率分別為0.112 9和0.095 2,可見GA-SA算法切換率指標也更優(yōu)。之后的調度周期內,隨著預警系統(tǒng)對目標跟蹤估計的逐漸收斂,指標ΔI會逐漸減少至趨于零,此時通過判斷ΔI大小更換目標函數(shù)權值,算法更注重系統(tǒng)切換率水平,從而提高跟蹤效率。

預警全過程內目標的跟蹤誤差如圖6所示。

圖6 GA-SA與GA算法跟蹤誤差圖Fig.6 Target tracking errors of GA-SA and GA

從圖6中可以看出,相較GA算法,GA-SA混合算法在跟蹤精度方面具有更大的優(yōu)勢,同時,GA-SA算法優(yōu)化的調度策略跟蹤收斂速度也更快一些,這是因為GA-SA優(yōu)化結果下的調度策略,其衛(wèi)星切換率低,對目標的跟蹤較穩(wěn)定。除此之外,調度周期與觀測子任務時長的選取,其直接影響優(yōu)化染色體規(guī)模大小,調度周期越短,觀測子任務時長越長,則調度周期內的待調度任務規(guī)模就越小,從而降低染色體規(guī)模減少計算時間。但是調度周期太短,即調度策略頻繁計算,會使得預警全過程中的衛(wèi)星切換率大大增加,觀測子任務時長太長,則會使衛(wèi)星資源靈活性下 降,隨著目標數(shù)量的增加,會使得目標長期無法分配觀測資源,二者的確定是下一步研究的重點。

5 結 論

本文針對預警衛(wèi)星低軌星座跟蹤中段多目標時的傳感器調度問題,建立了預警衛(wèi)星低軌星座傳感器資源調度混合整數(shù)規(guī)劃模型,以跟蹤PCRLB變化率和傳感器切換率為優(yōu)化指標,設計了求解調度模型的GA-SA混合優(yōu)化算法,該算法結合了遺傳算法優(yōu)化操作簡單、全局尋優(yōu)能力強和模擬退火使用Metropolis準則抽樣跳離局部最優(yōu)的特點。仿真試驗表明,本文所建立的低軌星座傳感器資源調度模型和GA-SA混合優(yōu)化算法是有效的,提高了調度策略計算的效率。