基于信息決策樹分支剔除的傳感器資源調度＊

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

(1.國防科技大學電子科學與工程學院,湖南長沙 410073;2.北京跟蹤與通信技術研究所,北京 100094;3.國防科技大學訓練部,湖南長沙 410073)

由于低軌星座傳感器動態組網、高速運動及空間廣域分布,探測目標全球隨機出現且時空跨度大等原因,通常少量傳感器不可能完成對高速運動目標的全程連續跟蹤[1].這種情況下,系統需要較多傳感器之間彼此協同、相互接力才能完成對目標的全程連續跟蹤,而解決跟蹤交接問題的關鍵就是傳感器資源調度技術.

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

1 傳感器調度約束條件分析

低軌星座傳感器調度需考慮的約束因素主要有資源約束,任務約束和時間約束.

1.1 資源約束

1)單個傳感器性能

單個傳感器性能約束是指單個傳感器可同時處理的最大目標個數,記為τimax.也就是說,系統要求第i個傳感器同時處理目標個數τi滿足τi≤τimax,i=1,2,…,N,N為傳感器數量.

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

全星座傳感器綜合能力包括星座可觀測能力和全系統處理負荷.低軌星座對特定目標的覆蓋情況稱為星座可觀測能力,傳感器實現對目標跟蹤要首先保證目標處于所選傳感器的探測視場內.也就是說,為第j個目標選擇的傳感器組合是對其可實現有效覆蓋的傳感器集合的子集,即.全系統處理負荷是指整個星座傳感器系統可同時處理的最大目標個數,記為τsmax.

1.2 任務約束

1)單任務約束

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

2)全系統任務約束

全系統任務約束包括多任務處理優先級和多任務處理沖突.整個星座傳感器系統通常要處理多個任務,而多個任務處理的重要性、緊迫性的不同,導致對其處理要有一定的先后次序,該次序稱為多任務處理優先級,記為cj.多任務同時對同一資源的需求會導致需求沖突,稱為多任務處理沖突.此時需要依據任務的優先級等因素對沖突資源進行分配,優先滿足重要任務.

1.3 時間約束

時間約束包括調度算法運算延遲、傳感器交接延遲和交接次數.調度算法運算延遲是指傳感器調度算法對目標和傳感器進行決策分配所消耗的計算時間,記為tcmp.傳感器交接延遲是指從地面信息處理中心作出傳感器調度決策到相關傳感器重新捕獲到目標所消耗時間,記為tsch,主要包括指令和引導信息傳輸延遲、傳感器指向偏轉延遲及目標捕獲延遲3部分.因此,兩次傳感器交接之間的時間間隔tint應滿足tint＞tcmp+tsch.交接次數是對目標全程處理的衡量參數.目標全程處理過程中,過多的交接次數會導致傳感器之間頻繁進行指向偏轉和重新捕獲,可能導致丟失目標;交接次數過少,或者說,只有在目標運動即將離開傳感器視場時才進行調度,由于部分時段所選傳感器可能不是最優處理傳感器,會降低系統處理效果.

2 傳感器調度信息決策樹模型

2.1 信息增量模型

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

誤差協方差矩陣的每個元素是狀態向量的一個特定元素不確定性的度量,或兩個元素間聯合不確定性的度量,因而式(1)的信息增量可以作為傳感器調度的優化準則,通常選擇狀態更新產生信息增量最大的一個目標優先進行跟蹤.為避免復雜計算,可去掉對數運算,這樣處理雖然會影響協方差陣范數的相對增幅,但不影響它們的增幅趨勢,仍可以利用增幅單調性趨勢實現優化搜索.因而,可以用協方差陣范數變化表示信息增量,即:

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

但是式(3)為短時信息增量,只能反映當前時刻最優的跟蹤傳感器選擇,不能反映長期最優的跟蹤傳感器選擇,尤其對于高速運動的低軌星座和目標.因此,本文以一個步長step內的長時信息增量作為傳感器調度的優化目標函數.假定系統要處理目標數為N,第n個目標可選擇傳感器個數為Mn,則第l個傳感器組合對第n個目標的長時信息增量Inl定義為:

式中:Inl,k+i為第k+i時刻第l個傳感器組合對第n個目標跟蹤的信息增量,通過多步預測得到;Ln為第n個目標可選擇傳感器組合數.對于多目標情況,采用聯合信息增量作為傳感器調度的優化目標函數,這里的聯合信息增量IU定義為目標優先級對各目標信息增量的加權和.因此,多目標條件下的優化目標函數為:

式中:cn為第n個目標的優先級;Inl為第l個傳感器組合對第n個目標跟蹤獲得的長時信息增量;L為所有目標可選擇傳感器組合數.

低軌星座實時傳感器優化調度實際上是一個約束最優化問題.根據第1節對約束條件的分析和式(5)的優化目標函數,本文建立如下調度模型:

式中:xnm為傳感器分配情況,xnm=1為第m個傳感器分配給第n個目標,否則xnm=0.

2.2 信息決策樹的建立

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

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

信息決策樹的建立主要有兩個優點[6]:

1)加速了調度過程,不需要每一時刻都進行一次優化調度;

2)一旦深度為p的信息決策樹建立,則任何深度p＜P的子樹同樣可以用來進行傳感器的調度,且步長變為子樹的深度,即step=p.

3 基于決策樹分支剔除的傳感器調度

為克服短時調度方法對應的跟蹤系統性能在時間上穩定性較差的缺點,本文采用長時調度方法對低軌星座傳感器資源進行調度,并引入分支剔除技術搜索最優傳感器組合序列.

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

本文針對目標跟蹤傳感器優化調度問題的特征,引入基于閾值的分支剔除搜索技術(其步驟如圖2所示),進一步減少搜索結點數.其中,閾值的設定如下:

2)設定一個步長內傳感器交接次數閾值為1,若搜索的傳感器組合序列存在超過該閾值次數的交接,則認為搜索失敗,其后的所有結點均認為失敗.

Step1:從根結點開始搜索,代價函數初始值為0.

Step2:從當前結點向下一深度搜索所有路徑;計算直到這一深度的最大信息增量;剔除代價值小于η倍最大信息增量的分支;對于保留的分支,記錄信息增量值和與之對應的搜索路徑.

Step3:將下一深度的每一結點作為根結點并重復Step2的分支剔除.

Step4:當搜索到深度p,或搜索足夠時間時,輸出直到該深度的最大信息增量對應的最優傳感器組合序列.

4 仿真實驗分析

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

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

表1 兩種方法的調度結果Tab.1 Scheduling results of the two methods

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

5 結 論

本文在分析低軌星座對多目標跟蹤應用背景的基礎上,引入傳感器實時調度的長時信息增量模型,提出基于信息決策樹分支剔除的優化求解算法.仿真實驗充分顯示了本文算法相對于短時調度方法的優越性,以及分支剔除搜索在運算量上的優勢.

[1] 王博,安瑋,謝愷,等.基于多模型的低軌星座多目標跟蹤傳感器資源調度[J].航空學報,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] 劉先省,周林,杜曉玉.基于目標權重和信息增量的傳感器管理方法[J].電子學報,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].湖南大學學報:自然科學版,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)