程洪瑋,唐宏斌,李 駿,王 博

(1.國(guó)防科技大學(xué)電子科學(xué)與工程學(xué)院,湖南長(zhǎng)沙 410073;2.北京跟蹤與通信技術(shù)研究所,北京 100094;3.國(guó)防科技大學(xué)訓(xùn)練部,湖南長(zhǎng)沙 410073)

由于低軌星座傳感器動(dòng)態(tài)組網(wǎng)、高速運(yùn)動(dòng)及空間廣域分布,探測(cè)目標(biāo)全球隨機(jī)出現(xiàn)且時(shí)空跨度大等原因,通常少量傳感器不可能完成對(duì)高速運(yùn)動(dòng)目標(biāo)的全程連續(xù)跟蹤[1].這種情況下,系統(tǒng)需要較多傳感器之間彼此協(xié)同、相互接力才能完成對(duì)目標(biāo)的全程連續(xù)跟蹤,而解決跟蹤交接問題的關(guān)鍵就是傳感器資源調(diào)度技術(shù).

傳感器調(diào)度就是依據(jù)一段時(shí)間內(nèi)的代價(jià)函數(shù)最優(yōu)化,對(duì)未來的可用傳感器資源進(jìn)行科學(xué)而合理的分配.其最基本的目的[2]就是在合適的時(shí)候選擇合適的傳感器對(duì)合適的目標(biāo)做合適的服務(wù).傳統(tǒng)的實(shí)時(shí)調(diào)度方法多是短時(shí)(Myopic)調(diào)度,即根據(jù)一步前向預(yù)測(cè)信息進(jìn)行調(diào)度.這種方法運(yùn)算量小,但其調(diào)度結(jié)果對(duì)應(yīng)的跟蹤系統(tǒng)性能在時(shí)間上穩(wěn)定性較差.而長(zhǎng)時(shí)(Non-Myopic)調(diào)度方法有效解決了這一問題,但其可選擇傳感器序列數(shù)隨著步長(zhǎng)的增大而呈指數(shù)增長(zhǎng),相應(yīng)的運(yùn)算量也呈指數(shù)增長(zhǎng).顯然,當(dāng)步長(zhǎng)較大時(shí),運(yùn)算量成為長(zhǎng)時(shí)調(diào)度方法要重點(diǎn)解決的問題.本文針對(duì)高速運(yùn)動(dòng)目標(biāo)連續(xù)跟蹤問題,在分析傳感器調(diào)度約束條件的基礎(chǔ)上,建立了基于長(zhǎng)時(shí)信息增益的傳感器實(shí)時(shí)調(diào)度模型,并提出了基于決策樹分支剔除(Pruning)[3-4]的優(yōu)化求解算法.仿真實(shí)驗(yàn)表明,本文所提出的調(diào)度模型和求解算法可有效進(jìn)行低軌星座的傳感器資源調(diào)度.

1 傳感器調(diào)度約束條件分析

低軌星座傳感器調(diào)度需考慮的約束因素主要有資源約束,任務(wù)約束和時(shí)間約束.

1.1 資源約束

1)單個(gè)傳感器性能

單個(gè)傳感器性能約束是指單個(gè)傳感器可同時(shí)處理的最大目標(biāo)個(gè)數(shù),記為τimax.也就是說,系統(tǒng)要求第i個(gè)傳感器同時(shí)處理目標(biāo)個(gè)數(shù)τi滿足τi≤τimax,i=1,2,…,N,N為傳感器數(shù)量.

2)全星座傳感器綜合能力

全星座傳感器綜合能力包括星座可觀測(cè)能力和全系統(tǒng)處理負(fù)荷.低軌星座對(duì)特定目標(biāo)的覆蓋情況稱為星座可觀測(cè)能力,傳感器實(shí)現(xiàn)對(duì)目標(biāo)跟蹤要首先保證目標(biāo)處于所選傳感器的探測(cè)視場(chǎng)內(nèi).也就是說,為第j個(gè)目標(biāo)選擇的傳感器組合是對(duì)其可實(shí)現(xiàn)有效覆蓋的傳感器集合的子集,即.全系統(tǒng)處理負(fù)荷是指整個(gè)星座傳感器系統(tǒng)可同時(shí)處理的最大目標(biāo)個(gè)數(shù),記為τsmax.

1.2 任務(wù)約束

1)單任務(wù)約束

單任務(wù)約束包括完成單個(gè)處理任務(wù)所需的最小傳感器數(shù)量和系統(tǒng)分給單個(gè)處理任務(wù)的最大傳感器數(shù)量限制,分別記為γjmin,γjmax.則系統(tǒng)為單個(gè)處理任務(wù)所分配的傳感器個(gè)數(shù)γj需滿足γjmin≤γj≤γjmax,j=1,2,…,M,M為系統(tǒng)任務(wù)數(shù)量.

2)全系統(tǒng)任務(wù)約束

全系統(tǒng)任務(wù)約束包括多任務(wù)處理優(yōu)先級(jí)和多任務(wù)處理沖突.整個(gè)星座傳感器系統(tǒng)通常要處理多個(gè)任務(wù),而多個(gè)任務(wù)處理的重要性、緊迫性的不同,導(dǎo)致對(duì)其處理要有一定的先后次序,該次序稱為多任務(wù)處理優(yōu)先級(jí),記為cj.多任務(wù)同時(shí)對(duì)同一資源的需求會(huì)導(dǎo)致需求沖突,稱為多任務(wù)處理沖突.此時(shí)需要依據(jù)任務(wù)的優(yōu)先級(jí)等因素對(duì)沖突資源進(jìn)行分配,優(yōu)先滿足重要任務(wù).

1.3 時(shí)間約束

時(shí)間約束包括調(diào)度算法運(yùn)算延遲、傳感器交接延遲和交接次數(shù).調(diào)度算法運(yùn)算延遲是指?jìng)鞲衅髡{(diào)度算法對(duì)目標(biāo)和傳感器進(jìn)行決策分配所消耗的計(jì)算時(shí)間,記為tcmp.傳感器交接延遲是指從地面信息處理中心作出傳感器調(diào)度決策到相關(guān)傳感器重新捕獲到目標(biāo)所消耗時(shí)間,記為tsch,主要包括指令和引導(dǎo)信息傳輸延遲、傳感器指向偏轉(zhuǎn)延遲及目標(biāo)捕獲延遲3部分.因此,兩次傳感器交接之間的時(shí)間間隔tint應(yīng)滿足tint＞tcmp+tsch.交接次數(shù)是對(duì)目標(biāo)全程處理的衡量參數(shù).目標(biāo)全程處理過程中,過多的交接次數(shù)會(huì)導(dǎo)致傳感器之間頻繁進(jìn)行指向偏轉(zhuǎn)和重新捕獲,可能導(dǎo)致丟失目標(biāo);交接次數(shù)過少,或者說,只有在目標(biāo)運(yùn)動(dòng)即將離開傳感器視場(chǎng)時(shí)才進(jìn)行調(diào)度,由于部分時(shí)段所選傳感器可能不是最優(yōu)處理傳感器,會(huì)降低系統(tǒng)處理效果.

2 傳感器調(diào)度信息決策樹模型

2.1 信息增量模型

對(duì)于目標(biāo)跟蹤來說,信息增量定義為一次量測(cè)前后的信息熵差值[5].由于信息熵是對(duì)目標(biāo)狀態(tài)不確定性的度量,因此信息增量反映了量測(cè)前后目標(biāo)狀態(tài)不確定性的變化,也就是目標(biāo)跟蹤所獲得的信息量.根據(jù)文獻(xiàn)[5]的分析,由于目標(biāo)預(yù)測(cè)誤差矢量X和目標(biāo)估計(jì)誤差矢量均服從目標(biāo)真實(shí)狀態(tài)矢量為中心的高斯分布,則量測(cè)前后的信息增量可表示為:

誤差協(xié)方差矩陣的每個(gè)元素是狀態(tài)向量的一個(gè)特定元素不確定性的度量,或兩個(gè)元素間聯(lián)合不確定性的度量,因而式(1)的信息增量可以作為傳感器調(diào)度的優(yōu)化準(zhǔn)則,通常選擇狀態(tài)更新產(chǎn)生信息增量最大的一個(gè)目標(biāo)優(yōu)先進(jìn)行跟蹤.為避免復(fù)雜計(jì)算,可去掉對(duì)數(shù)運(yùn)算,這樣處理雖然會(huì)影響協(xié)方差陣范數(shù)的相對(duì)增幅,但不影響它們的增幅趨勢(shì),仍可以利用增幅單調(diào)性趨勢(shì)實(shí)現(xiàn)優(yōu)化搜索.因而,可以用協(xié)方差陣范數(shù)變化表示信息增量,即:

由于只需要一個(gè)相對(duì)值來比較信息增量的大小,而并不需要求出一個(gè)絕對(duì)的信息增量值,因此為便于計(jì)算,可用矩陣的跡代替矩陣范數(shù)運(yùn)算[5],即:

但是式(3)為短時(shí)信息增量,只能反映當(dāng)前時(shí)刻最優(yōu)的跟蹤傳感器選擇,不能反映長(zhǎng)期最優(yōu)的跟蹤傳感器選擇,尤其對(duì)于高速運(yùn)動(dòng)的低軌星座和目標(biāo).因此,本文以一個(gè)步長(zhǎng)step內(nèi)的長(zhǎng)時(shí)信息增量作為傳感器調(diào)度的優(yōu)化目標(biāo)函數(shù).假定系統(tǒng)要處理目標(biāo)數(shù)為N,第n個(gè)目標(biāo)可選擇傳感器個(gè)數(shù)為Mn,則第l個(gè)傳感器組合對(duì)第n個(gè)目標(biāo)的長(zhǎng)時(shí)信息增量Inl定義為:

式中:Inl,k+i為第k+i時(shí)刻第l個(gè)傳感器組合對(duì)第n個(gè)目標(biāo)跟蹤的信息增量,通過多步預(yù)測(cè)得到;Ln為第n個(gè)目標(biāo)可選擇傳感器組合數(shù).對(duì)于多目標(biāo)情況,采用聯(lián)合信息增量作為傳感器調(diào)度的優(yōu)化目標(biāo)函數(shù),這里的聯(lián)合信息增量IU定義為目標(biāo)優(yōu)先級(jí)對(duì)各目標(biāo)信息增量的加權(quán)和.因此,多目標(biāo)條件下的優(yōu)化目標(biāo)函數(shù)為:

式中:cn為第n個(gè)目標(biāo)的優(yōu)先級(jí);Inl為第l個(gè)傳感器組合對(duì)第n個(gè)目標(biāo)跟蹤獲得的長(zhǎng)時(shí)信息增量;L為所有目標(biāo)可選擇傳感器組合數(shù).

低軌星座實(shí)時(shí)傳感器優(yōu)化調(diào)度實(shí)際上是一個(gè)約束最優(yōu)化問題.根據(jù)第1節(jié)對(duì)約束條件的分析和式(5)的優(yōu)化目標(biāo)函數(shù),本文建立如下調(diào)度模型:

式中:xnm為傳感器分配情況,xnm=1為第m個(gè)傳感器分配給第n個(gè)目標(biāo),否則xnm=0.

2.2 信息決策樹的建立

當(dāng)實(shí)時(shí)傳感器調(diào)度算法的步長(zhǎng)取step＞1時(shí),由一個(gè)步長(zhǎng)內(nèi)各時(shí)刻可觀測(cè)傳感器組合可以構(gòu)成如圖1所示的深度p=step的決策樹[6].決策樹每個(gè)深度(p,p=1,2,…,p)上任一結(jié)點(diǎn)表示一種傳感器組合選擇st+p-1,實(shí)際上,每個(gè)深度層次(即每時(shí)刻)的可觀測(cè)傳感器組合個(gè)數(shù)是不同的,為簡(jiǎn)便起見,圖1中假定每時(shí)刻可觀測(cè)的傳感器組合個(gè)數(shù)均為3,則決策樹各個(gè)深度層次的結(jié)點(diǎn)個(gè)數(shù)依次為30,31,…,3p,…,3p-1,也就是說,深度為p=step的決策樹所對(duì)應(yīng)的一個(gè)步長(zhǎng)內(nèi)所有可能的傳感器組合選擇方式有3p-1種.決策樹各樹枝的權(quán)重為采用該傳感器組合跟蹤目標(biāo)的信息增量,因此稱所建立的決策樹為信息決策樹.因而傳感器調(diào)度問題就轉(zhuǎn)化為對(duì)信息決策樹的最優(yōu)搜索問題,搜索的目標(biāo)是最大化信息增量(也就是優(yōu)化目標(biāo)函數(shù)).

圖1 信息決策樹Fig.1 Information decision tree

信息決策樹的建立主要有兩個(gè)優(yōu)點(diǎn)[6]:

1)加速了調(diào)度過程,不需要每一時(shí)刻都進(jìn)行一次優(yōu)化調(diào)度;

2)一旦深度為p的信息決策樹建立,則任何深度p＜P的子樹同樣可以用來進(jìn)行傳感器的調(diào)度,且步長(zhǎng)變?yōu)樽訕涞纳疃?即step=p.

3 基于決策樹分支剔除的傳感器調(diào)度

為克服短時(shí)調(diào)度方法對(duì)應(yīng)的跟蹤系統(tǒng)性能在時(shí)間上穩(wěn)定性較差的缺點(diǎn),本文采用長(zhǎng)時(shí)調(diào)度方法對(duì)低軌星座傳感器資源進(jìn)行調(diào)度,并引入分支剔除技術(shù)搜索最優(yōu)傳感器組合序列.

根據(jù)文獻(xiàn)[4]的分析,分支剔除搜索技術(shù)可以在不丟失最優(yōu)傳感器序列的前提下,減少搜索時(shí)間,因此可以應(yīng)用于實(shí)時(shí)傳感器調(diào)度.常用的分支剔除方法主要有平滑窗法和閾值法[4].平滑窗法類似于Viterbi算法的偽實(shí)時(shí)形式;而閾值法實(shí)際上是直覺地認(rèn)為任意深度上過小信息增量對(duì)應(yīng)的傳感器組合序列不可能是整個(gè)步長(zhǎng)內(nèi)生成最大信息增量的傳感器組合序列的一部分,并引入取舍參數(shù)η(η≥1)剔除掉過小信息增量對(duì)應(yīng)的結(jié)點(diǎn).

本文針對(duì)目標(biāo)跟蹤傳感器優(yōu)化調(diào)度問題的特征,引入基于閾值的分支剔除搜索技術(shù)(其步驟如圖2所示),進(jìn)一步減少搜索結(jié)點(diǎn)數(shù).其中,閾值的設(shè)定如下:

2)設(shè)定一個(gè)步長(zhǎng)內(nèi)傳感器交接次數(shù)閾值為1,若搜索的傳感器組合序列存在超過該閾值次數(shù)的交接,則認(rèn)為搜索失敗,其后的所有結(jié)點(diǎn)均認(rèn)為失敗.

Step1:從根結(jié)點(diǎn)開始搜索,代價(jià)函數(shù)初始值為0.

Step2:從當(dāng)前結(jié)點(diǎn)向下一深度搜索所有路徑;計(jì)算直到這一深度的最大信息增量;剔除代價(jià)值小于η倍最大信息增量的分支;對(duì)于保留的分支,記錄信息增量值和與之對(duì)應(yīng)的搜索路徑.

Step3:將下一深度的每一結(jié)點(diǎn)作為根結(jié)點(diǎn)并重復(fù)Step2的分支剔除.

Step4:當(dāng)搜索到深度p,或搜索足夠時(shí)間時(shí),輸出直到該深度的最大信息增量對(duì)應(yīng)的最優(yōu)傳感器組合序列.

4 仿真實(shí)驗(yàn)分析

星座軌道參數(shù)取28/4/2/1596/77.8[7].兩個(gè)目標(biāo)不同時(shí)不同地發(fā)射,其相關(guān)參數(shù)分別為:1)目標(biāo)1:發(fā)射點(diǎn)E143.000°,N37.000°,落點(diǎn)E113°,N40°,遠(yuǎn)地點(diǎn)高度1 770 km;2)目標(biāo)2:發(fā)射點(diǎn)E76°,N21°,落點(diǎn)E111°,N38°,遠(yuǎn)地點(diǎn)高度1 473 km.傳感器觀測(cè)間隔為1 s,視線測(cè)量誤差90 μ rad.式(6)中優(yōu)化模型的參數(shù)取值分別為τimax=1,γjmin=1,γjmax=Nj,c1=1,c2=2,其中Nj為對(duì)第j個(gè)目標(biāo)可覆蓋的傳感器個(gè)數(shù),由可見性分析[8]得到.在CPU為Cuo2 E8400內(nèi)存4 GB的臺(tái)式機(jī)進(jìn)行仿真(50次Monte Carlo實(shí)驗(yàn))實(shí)現(xiàn)本文基于信息決策樹分支剔除的傳感器調(diào)度算法(IDTA),步長(zhǎng)取step=5 s,并與基于短時(shí)信息增量的調(diào)度算法(MIA,也就是step=1 s)的仿真結(jié)果進(jìn)行比較.兩種方法調(diào)度傳感器跟蹤目標(biāo)的誤差如圖2所示;而傳感器調(diào)度結(jié)果如表1所示.

圖2 兩種方法的跟蹤誤差Fig.2 Tracking error of the two methods

表1 兩種方法的調(diào)度結(jié)果Tab.1 Scheduling results of the two methods

由圖2和表1可見:IDTA方法引入長(zhǎng)時(shí)調(diào)度對(duì)系統(tǒng)的跟蹤性能有一定改善;IDTA方法的最小調(diào)度間隔較大,有利于傳感器之間的實(shí)時(shí)跟蹤交接;決策樹分支剔除的引入大大減少了長(zhǎng)時(shí)調(diào)度算法的搜索路徑數(shù),降低了運(yùn)算量.

5 結(jié) 論

本文在分析低軌星座對(duì)多目標(biāo)跟蹤應(yīng)用背景的基礎(chǔ)上,引入傳感器實(shí)時(shí)調(diào)度的長(zhǎng)時(shí)信息增量模型,提出基于信息決策樹分支剔除的優(yōu)化求解算法.仿真實(shí)驗(yàn)充分顯示了本文算法相對(duì)于短時(shí)調(diào)度方法的優(yōu)越性,以及分支剔除搜索在運(yùn)算量上的優(yōu)勢(shì).

[1] 王博,安瑋,謝愷,等.基于多模型的低軌星座多目標(biāo)跟蹤傳感器資源調(diào)度[J].航空學(xué)報(bào),2010,31(5):946-957.WANG Bo,AN Wei,XIE Kai,et al.Multi-object tracking sensor scheduling for low earth orbit constellation based on multi-model[J].ACTA Aeronautica ET Astronautica Sinica,2010,31(5):946-957.(In Chinese)

[2] XIONG N,SVENSSON P.Multi-sensor management for information fusion:issues and approaches[J].Information Fusion,2002,3(2):163-186.

[3] WILLIAMS J L.Information theoretic sensor management[D].Massachusetts,USA:Massachusetts Institute of Technology,2007.

[4] HUBER M F,HANEBECK U D.Priority list sensor scheduling using optimal pruning[C]//Proceedings of the 11th International Conference on Information Fusion.Cologne,Germany:International Society of Information Fusion,2008:1-8.

[5] 劉先省,周林,杜曉玉.基于目標(biāo)權(quán)重和信息增量的傳感器管理方法[J].電子學(xué)報(bào),2005,33(9):1683-1687.LIU Xian-xing,ZHO U Lin,DU Xiao-yu.A method of sensor management based on target priority and information gain[J].ACTA Electronica Sinica,2005,33(9):1683-1687.(In Chinese)

[6] CHHET RI A,M ORRELL D.A papandreou-suppappola energy efficient target tracking in a sensor network using non-myopic sensor scheduling[C]//Proceedings of 8th International Conference on Information Fusion.F ranklin Plaza,Philadelphia,USA:International Society ofInformation Fusion,2005:558-565.

[7] BUDIANTO I A,O LDS J R.A collaborative optimization approach to design and deployment of a space based infrared system constellation[C]∥Proceedings of the IEEE National Aerospace and Electronics Conference.Dayton,Ohio,USA:Institute of Electrical and Electronics Engineers,2000:385-393.

[8] 王博,許丹,陳延軍,等.低軌星座紅外凝視傳感器覆蓋性能分析[J].湖南大學(xué)學(xué)報(bào):自然科學(xué)版,2009,36(10):68-74.WANG Bo,XU Dan,CHEN Yan-jun,et al.Analysis of the coverage of LEO constellation based on infrared staring sensors[J].Journal of Hunan University:Natural Sciences,2009,36(10):68-74.(In Chinese)