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

摘要:針對低軌星座對高速運動目標連續跟蹤的傳感器調度問題，將傳感器調度的長時信息增量模型描述為信息決策樹，并通過分支剔除技術搜索最優解，提出一種基于信息決策樹分支剔除的傳感器調度方法。仿真實驗表明，長時信息增量有效克服了短時信息增量過于頻繁調度的問題，且決策樹分支剔除的引入大大降低了長時信息增量最優搜索的運算量。

關鍵詞:衛星;傳感器;調度算法;信息增量;決策樹

中圖分類號:TP212.9 文獻標識碼:A

Sensor Resource Scheduling Based on the Pruning of Information Decision Tree

CHENG Hong-wei1，2， TANG Hong-bin3， LI Jun1， WANG Bo1

(1. College of Electronic Science and Engineering， National Univ. of Defense Technology， Changsha 410073， China; 2. Beijing Institute of Tracking and Telecommunications Technology， Beijing 100094， China; 3. Training Division， National Univ. of Defense Technology， Changsha 410073， China;)

Abstract: To deal with the sensor scheduling in high-speed object tracking of low earth orbit constellation， the non-myopic information increment is described as an information decision tree. Afterwards， the optimal solution is searched by pruning technology， and a method based on the pruning of information decision tree is proposed. The simulation results indicate that the excessive scheduling has been reduced effectively by the non-myopic information increment; furthermore， the introduction of pruning technology has reduced the computation burden greatly.

Key words: Satellites; Sensors; Scheduling algorithms; Information increment; Decision tree

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

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

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

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

1.1資源約束

(1) 單個傳感器性能

單個傳感器性能約束是指單個傳感器可同時處理的最大目標個數，記為 。也就是說，系統要求第 個傳感器同時處理目標個數 滿足 ， 為傳感器數量。

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

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

1.2任務約束

(1) 單任務約束

單任務約束包括完成單個處理任務所需的最小傳感器數量和系統分給單個處理任務的最大傳感器數量限制，分別記為 。則系統為單個處理任務所分配的傳感器個數 需滿足 ， 為系統任務數量。

(2) 全系統任務約束

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

1.3時間約束

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

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

2.1信息增量模型

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

(1)

式中， 和 分別表示先驗信息熵和后驗信息熵， 和 分別表示目標預測誤差協方差陣和估計誤差協方差陣。

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

(2)

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

(3)

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

(4)

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

(5)

其中， 表示第 個目標的優先級， 表示第 個傳感器組合對第 個目標跟蹤獲得的長時信息增量; 為所有目標可選擇傳感器組合數。

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

(6)

式中 表示傳感器分配情況， 表示第 個傳感器分配給第 個目標，否則 。

對于式(6)的優化模型， 個目標可選擇的傳感器組合數 ，顯然隨著目標個數的增長而呈指數增長，相應的運算量也呈現指數增長趨勢。因而，當目標個數 較大時，通過遍歷搜索求解優化模型的運算量將超過系統的運算負載，難以實時實現，需要探索高效求解該模型的優化搜索技術。

2.2信息決策樹的建立

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

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

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

(2) 一旦深度為 的信息決策樹建立，則任何深度 的子樹同樣可以用來進行傳感器的調度，且步長變為子樹的深度，即 。

圖1信息決策樹

Fig.1Information decision tree

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

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

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

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

(1) 設定信息增量的閾值取舍參數為 ，若搜索的傳感器組合序列對應的信息增量 滿足 ，則剔除該結點，其后的所有結點均認為失敗;

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

圖2分支剔除的步驟

Fig.2Process of pruning

4 仿真實驗分析

星座軌道參數取28/4/2/1596/77.8[7]。兩個目標不同時不同地發射，其相關參數分別為:(1) 目標1:發射點 ，落點 ，遠地點高度1770km;(2) 目標2:發射點 ，落點 ，遠地點高度1473km。傳感器觀測間隔為1秒，視線測量誤差90micro;rad。式(6)中優化模型的參數取值分別為 ，其中 為對第 個目標可覆蓋的傳感器個數，由可見性分析[8]得到。在CPU為Cuo2 E8400內存4GB的臺式機進行仿真(50次Monte Carlo實驗)實現本文基于信息決策樹分支剔除的傳感器調度算法(IDTA)，步長取 ，并與基于短時信息增量的調度算法(MIA，也就是 )的仿真結果進行比較。兩種方法調度傳感器跟蹤目標的誤差如圖3所示;而傳感器調度結果如表1所示。

由表1和圖3可見: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]N. Xiong， P. Svensson. Multi-sensor Management for Information Fusion: Issues and Approaches[J]. Information Fusion， 2002， 3(2):163-186.

[3]J. L. Williams. Information Theoretic Sensor Management[D]. Massachusetts， USA: Doctor of Philosophy in Electrical Engineering and Computer Science at the Massachusetts Institute of Technology， 2007.

[4]M. F. Huber， U. D. Hanebeck. 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， ZHOU 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]A. Chhetri， D. Morrell， 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. Franklin Plaza， Philadelphia， USA: International Society of Information Fusion， 2005: 558-565.

[7]Budianto I A.， Olds 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)