基于傳感器網絡的多目標跟蹤和特征管理方法

王鼎元，邸 興，黨小寶

（中國飛行試驗研究院 陜西 西安 710089）

近來傳感器技術和無線通信技術的發展導致了一個新概念的誕生－傳感器網絡，即一個由本地傳感器節點所組成的具有感知、處理和通信能力的一種廣泛應用的網絡[1]。為了更深入地挖掘傳感器網絡所具有的能力，筆者提出了一種可擴展分布式的多目標跟蹤和特征管理方法，該方法能夠通過一個傳感器網絡對多個目標實現跟蹤和特征管理。

傳統的多目標跟蹤方法，如MHT跟蹤器[2]，不適用于傳感器網絡。而現有基于傳感器網絡的算法[3]僅基于如下情況：所跟蹤目標的數量已知不變，并且它們的運動軌跡對于本地傳感器已知。而在本文中，筆者放寬了以上假設，形成對于分布式多目標的跟蹤和特征管理算法DMTIM。文中在實現數據關聯和多目標跟蹤運用了馬爾科夫鏈蒙特卡羅數據關聯MCMCDA[4]的方法，實時對未知數量的多目標進行跟蹤。MCMCDA方法能夠獨立地對軌跡進行起始和終止，并能夠跟蹤未知數量的多目標。每個傳感器能夠運用MCMCDA有效地跟蹤一組未知數量的目標，并且能夠對目標的特征進行分布式地管理。

本文結構如下：分布式多目標的跟蹤與特征管理算法概述；多目標跟蹤問題及其概率模型；DMTIM關鍵算法敘述：馬爾科夫鏈蒙特卡羅數據關聯算法；DMTIM組成部分介紹，包括數據關聯、多目標跟蹤、特征管理和信息融合；DMTIM算法仿真試驗及評估。

1 分布式多目標跟蹤和特征管理

文中研究重點是傳感器網絡中多目標的跟蹤和特征管理方法。每個傳感器擁有自己的觀測區域，且擁有與其鄰近傳感器通信的能力。如圖1所示一個簡單的二傳感器的系統，大圓圈代表傳感器的觀測區域。每個傳感器能夠對多目標進行跟蹤并在觀測區域內管理目標特征。該問題的難點在于觀測區域內目標的數量會隨時間而變化，因此我們必須尋求一種可擴展的，在相鄰傳感器中具有本地一致性的方法。

圖1 傳感器網絡示意圖Fig.1 Sensor network

筆者提出的可擴展的分布式多目標跟蹤與特征管理DMTIM算法能對未知數量且數量隨時變化的機動目標進行跟蹤，對其特征進行有效的管理。并能夠在一個分布式的傳感器網絡中進行實現。對于每一個傳感器，DMTIM中的多目標跟蹤算法負責估算如下量：目標的數量，觀測區域內所有目標的運動軌跡，以及在特征管理算法中將用到的混合矩陣和本地信息。然后，相鄰的傳感器通過相互通信對本地狀態估算值和信任矩陣進行交換。同時，通過信息融合實現了本地一致性，進而實現全局一致性。

本文的剩余部分對DMTIM的算法模塊進行了詳細描述。并且還對多目標跟蹤問題，以及馬爾科夫鏈蒙特卡洛數據關聯進行了描述。

2 多目標跟蹤

基于每個傳感器視野范圍內的目標數量會隨時間不斷變化，本章提出的DMTIM多目標跟蹤適應于此類多目標數量不確定的情況。

2.1 問題模式

設T∈Z+為傳感器觀測持續的時間，K為該時間內觀測范圍 R中所出現的目標數量。在某時間段[tki，tkf]?[1，T]內，每一個目標都在R范圍內移動，K和{tki，tkf}的值未知。每個目標都是在某時間點tki隨機出現在R范圍內，直到在時間點tkf時消失。對于每個時間點，目標保持其存在的概率為1-pz，消失的概率為pz。對于每一個時間點，在R范圍內所出現目標的數量都具有一個位置分布，該位置分布包含參數λbV，其中λb表示單位時間單位范圍內的出現率，V表示觀測范圍R的大小。并特定每個新目標的初始位置都在R范圍內。

設FkRns→Rns為目標k的離散時間運動，其中nx是狀態變化的維度。并設xk（t）∈Rns為時刻t目標k的狀態。目標t的運動服從公式（1）：

其中 ωk（t）∈Rns屬于白噪聲過程，包含在了目標非直線運動模型。并運用一個探測概率pd來計算目標狀態的噪聲。目標不被發現并被視為跟蹤丟失的概率為1-pd。本文設定了錯誤報警，其數量也遵循含有參數λfV的位置分布，其中λf是單位觀測范圍單位時間內的錯誤報警率。設n（t）為時間點t觀測點的數量，該數量包括了噪聲觀測和錯誤報警。設yj（t）∈Rny為時間點t的第j個觀測值，其中ny是每一個觀測向量的維度。每個被測物體都會在該采樣時間產生一個特定的觀測值，如公式（2）所示，其中 Hj:Rnx→Rny為觀測值模型。

其中 vj（t）∈Rnyvj（t）是白噪聲過程，u（t）是錯誤報警的隨機過程。目標是觀測目標類型或屬性信息，狀態變量可以擴展到包括目標類型的信息。因此多目標識別的問題即是從觀測值中計算出 K、{tki，tkf}、{xk（t）:tki≤t≤tkf}，其中 k=1，…，K。

2.2 多目標跟蹤方法

設 y（t）={yj（t）:j=1，…，n（t）}為時間 t的所有值，Y={y（t）:1≤t≤T}為時間t=1到t=T的所有計算值。設Ω為所有Y的集合，且ω∈Ω，有如下參數：

1）ω∈{τ0，τ1，…，τK}

2）∪Kk=0τk=Y，且 τi∩τj=?，i≠j；

3）τ0為錯誤報警的集合；

4）|τk∩y（t）|≤1，k=1，…，K，t=1，…，T；

5）|τk|≥2，k=1，…，K.

分離的過程如圖2所示，其中K為軌跡數量，|τk|為 τk的基數，當沒有軌跡互擾的情況下認為τk為一個正確的軌跡。假設一條軌跡至少包含兩個觀測值，因為不能由一個單一的觀察值確定一條軌跡。于是再假設e（t-1）為時刻t-1之后目標的數量，z（t）為時刻 t消失的目標的數量，c（t）=e（t-1）-z（t）為時刻t-1到t未消失的數量。設a（t）為時刻t新出現的目標，d（t）為時刻 t的實際目標，g（t）=c（t）+a（t）-d（t）為未識別的目標。 最后，設 f（t）=n（t）-d（t）為錯誤報警數量，有：

其中P（ω|Y）是Y的相似概率。

圖2 軌跡分離示例圖Fig.2 Example of tracks’partition

本文采用了最大后驗MAP算法解決多目標跟蹤問題。該算法對觀測目標進行分割，并根據分割對目標狀態進行估算。

3 馬爾科夫鏈蒙特卡洛數據融合

本節提出一種解決第二節中多目標跟蹤問題的算法，該算法是離散多目標跟蹤與識別算法模塊的核心。

3.1 馬爾科夫鏈蒙特卡洛模型

馬爾科夫鏈蒙特卡洛模型是已知唯一能在多項式時間復雜問題下實現估值計算的方法，同時，還是一種從位于空間Ω的分布π中提取抽樣值的普遍方法，該方法通過狀態值ω∈Ω和穩定分布值π（ω）建立的馬爾科夫鏈M來實現其算法?，F在來描述該算法。在狀態ω∈Ω，假設ω′∈Ω服從分布q（ω，ω′）。 而運動的感知服從感知概率 A（ω，ω′），其中：

然而樣本保持在ω。通過計算，平衡條件得以滿足，例如，對于所有的ω：

其中，P（ω，ω′）=q（ω，ω′）A（ω，ω′）是從 ω 到 ω′的躍遷概率。

如果M具約束性和非周期性，并且M由遍歷定理收斂至均勻分布[5]。因此，對于一個給定的有界函數f:Ω→Rm，樣（ω）收斂于 N→∞。 可以注意到公式（4）只需計算出 π（ω′）/π（ω）的比值，而無需對π進行標準化。

3.2 馬爾科夫鏈蒙特卡洛數據關聯

MCMCDA算法是馬爾科夫鏈蒙特卡洛算法的特殊形式，其狀態空間是上文在第2.2節中提到的，并且其平穩分布服從公式（3）。對于MCMCDA的分布有5類動作組成。它們包括：1）發現∕消失運動；2）分割∕合并運動；3）擴展∕減少運動；4）跟蹤刷新運動；5）跟蹤切換運動。

MCMCDA的運動方式如圖3中所示，每個運動的詳細描述[6]在此省略。MCMCDA的輸入是一系列觀測值Y，樣本觀測值的個數nmc，初始狀態ωinit，以及有界函數X:Ω→Rm。對于該算法的每一步，ω是馬爾科夫鏈的當前狀態。其獲取概率A（ω，ω′）如公式（4），輸出X^接近 MMSE 的估計值 EπX，且ω^接近MAP 的估計值 arg max P（ω|Y）。

4 分布式多目標跟蹤與特征管理算法結構

現在對分布式多目標跟蹤與特征管理算法進行詳細描述。運用一種信念向量來表示目標的特征。對于多目標的情況下，我們需要運用信念矩陣 B（t），其各列由信念向量 Bij（t）所組成。因此，向量表示目標j能被t時刻的i所確定的概率。

4.1 多目標跟蹤（數據關聯）

DMTIM多目標跟蹤（數據關聯）模塊的輸出涉及到混合矩陣、狀態估計值和本地信息三者的計算。

首先需要求得混合矩陣。假設在觀測范圍內有K個目標具有K個特征，因此特征管理意味著對多目標的特征進行匹配。對此，運用Identity-Mass-Flow[7]的方法?；旌暇仃囀且粋€K×K矩陣，其元素 Mij（t）表示目標 i在t-1時刻變成目標 j的概率。而MCMCDA能夠在多項式時間下對混合矩陣進行有效地估算。

圖3 馬爾科夫鏈蒙特卡洛數據關聯示意圖Fig.3 Graphical illustration of MCMCDA

然后需要對狀態估計值進行計算。如上所述，MCMCDA能夠對未知數量的多目標進行跟蹤，并且能夠實現軌跡的發生與終止。在每一個采樣時間段，其測量值與前一段的測量值相疊加，從而構造出測量值集合Y。MCMCDA能求出ω^，其值接近多目標跟蹤的MAP估計值，以及ω^中所有軌跡的狀態估計值。對于每一個軌跡τ∈ω，將它與之前發現的目標軌跡進行比較。如果τ與之前目標軌跡的測量值無任何相同之處，那么我們認定其為新目標。然后，當前傳感器τ對于對相鄰傳感器進行詢問，如果相鄰傳感器對τ已知，那么它的特征將被復制到當前傳感器當中。否則，將對τ創建新的特征。最后，當軌跡結束時，對目標特征進行刪除。在第4.2節，將對目標數量變化情況下信任矩陣如何實現刷新進行描述。

最后計算表示為信任向量的形式的本地信息。MCMCDA方法能夠通過最新的，以及之前的測量值有效地計算出本地信息。當目標和軌跡的數量處于估計值的情況下，本地信息能夠被同時計算出來。對于特征值k，定義Njk為時間點個數，第j個最新觀測值與之前的觀測值合并，觀測值在之前的nbi個采樣值中由k表征，其中nbi為之前的采樣值數量。算法結束時對特征值 k 計算。 然后根據最新的觀測值來對向量進行調整，進而通過γk來形成本地信息。

4.2 特征管理

特征管理模塊包括信任矩陣刷新和本地信息關聯，而多目標跟蹤（數據關聯）的混合矩陣和本地信息被用來刷新信任矩陣。

信任矩陣刷新模塊包含存儲在K×K信任矩陣B（t）中的特征信息。信任矩陣的刷新如下：

可以看出，公式（6）使信任矩陣行、列之和保持不變。然而目標數量的變化使該方法不適用于分布式特征管理。數量的變化有兩種情形：目標離開和進入觀測區域。目標離開，對傳感器中混合矩陣的相應列進行刪除；目標進入，又有兩種情形：1）目標從相鄰傳感器區域進入，2）目標從未知區域進入。

而本地信息被運用來降低由香農信息所得的信任矩陣的不確定性。L×K信任矩陣的香農信息定義如下：

接下來的問題是將該信息關聯到信任矩陣。信任矩陣具有如下性質：各列之和等于1；各行之后保持不變；各列之和的和與各列之和的和相等。如果將某列替換為本地信息，將無法保證以上性質。當且僅當本地信息能夠降低信任矩陣的不確定性時才能與信任矩陣進行關聯。

4.3 信息融合

DMTIM算法通過信息融合來計算本地傳感器網絡的全局信息，具體包括來自不同傳感器的狀態估計值和特征信任向量的融合。

特征信息 （信任向量）的融合能夠被表述為最優化的問題。3個不同的成本函數，香農信息（Shannon information），切爾洛夫信息 （Chernoff information）， 以及萊布勒距離（Kullback-Leibler distances）之和代表了不同的性能指標。本文場景[8]中所有的傳感器都參與協同工作，因此我們采用香農信息的方法。

鑒于每個目標可能具有來自不同傳感器的多重軌跡，運用軌跡數據融合方法[9]來對多重的軌跡進行合并。設ωi為來自傳感器i的軌跡，NBi為包括i并與i相鄰的一系列傳感器。 設 Y′={τk（t）:τk∈ωj，1≤t≤T，1≤k≤ω|ωj|，j∈NBi}為所有確定目標的一系列觀測結果。通過重疊觀測區域，可以由Y′得到一系列合并觀測結果Y。于是得到一系列新的軌跡ωinit。然后對一系列合并觀測結果運行算法，以得出本地穩定的跟蹤軌跡，其初始狀態為ωinit。

5 仿真結果

在該節中，提供一個簡單的場景來說明DMTIM算法的性能。環境中有兩個固定傳感器—空中交通管制雷達，在二維空間中對多架飛機進行跟蹤。假定每個傳感器觀測范圍的半徑為10 km，并且當兩傳感器距離進入20 km的通信范圍，它們之間可以實現相互通信。該場景中包含3架飛機，如圖4所示。被標注為A和B的飛機首先被預注冊，被標注為的飛機對于特征管理系統是未知的。左側傳感器被傳感器1所標注，右側傳感器被傳感器2所標注。每個傳感器中的多目標跟蹤模塊對目標的數量進行估算，并且對每個已知目標的軌跡進行估算。在圖5中，目標數量改變的事件被垂直的點線所標注。在時刻1，傳感器1感知到目標1，并且其信任向量為（）T=（0.8，0.2）T，其中 bij，k是目標 k 能夠被傳感器 i所感知并標定為j的概率；同時傳感器2感知到它的目標1，并且其信任向量為（）T=（0.2，0.8）T。 在時刻 9，傳感器1發現新目標（傳感器1的目標2），并賦予新值X。同時，傳感器2感知到新目標（傳感器2的目標2），該目標的特征值和狀態估計信息從傳感器1轉移過來。以此類推，在時刻30，傳感器2的目標2離開了傳感器2的觀測范圍，其信息隨機從傳感器2刪除。

信息融合能夠降低目標交叉運動所產生的不確定性。鑒于香農信息效率的優越性，在該試驗中我們運用了該方法來實現信息的融合。圖6所示為融合的信任向量，圖7為實現狀態估計融合后各傳感器所估算的軌跡。

圖4 三飛機、雙傳感器系統Fig.4 System of three-aircraft，two-sensor scenario

圖5 傳感器對目標數量的估計值Fig.5 Estimated number of targets by each sensor

圖6 融合處理后的信任向量Fig.6 Fused belief vector

圖7 融合算法后的軌跡Fig.7 Fused tracks

6 結 論

筆者主要對傳感器網絡下多目標的跟蹤和特征管理方法進行了研究。數據關聯和多目標跟蹤的問題能夠由馬爾科夫鏈蒙特卡洛數據關聯算法有效地解決，該算法能夠對數量未知且數量隨時間變化的多目標進行跟蹤。文中還講述了一個可擴展的分布式多目標跟蹤和身份管理（DMTIM）算法，該算法能夠對多目標進行跟蹤，并在分布式傳感器網絡環境下能夠有效地管理目標的特征。DMTIM算法由數據關聯，多目標跟蹤，特征管理，以及信息融合四部分所組成。DMTIM能夠對某目標特征的本地信息進行有效地整合，以降低系統的不確定性，并通過信息融合來保持相鄰傳感器的本地一致性。

[1]Cayirci A.Asurveyonsensornetworks[J].IEEECommunications Magazine，2002，40（8）:102-114.

[2]Reid D.An algorithm for tracking multiple targets[J].IEEE Transaction on Automatic Control，1979，24（6）:843-854.

[3]Hwang I，Balakrishnan H，Roy K，et al， Tomlin.Multiple-Target Tracking and Identity Management Algorithm In clutter[C]//Proceedings of the AACC American Control Conference， Boston，2004:18-20.

[4]Ohs， Russells， Sastrys.Markov Chain Monte Carlo Data Association for Multiple-Target Tracking[J].Tech.Rep，2005，23（5）:45-49.

[5]Roberts G..Markov chain concepts related to sampling algorithms[J].Markov Chain Monte Carlo in Practice，1996:256-267.

[6]Ohs， Russells， Sastrys.Markov Chain Monte Carlo Data Association for General Multiple-Target Tracking Problems[C]//the 43rd IEEE Conference on Decision and Control， 2004，6（3）:12-23.

[7]Shin J， Guibas L J， Zhao F.A distributed algorithm for managing multi-target identities in wireless ad-hoc sensor networks[J].Information Processing in Sensor Networks，2003:223-238.

[8]Hwang I， Roy K， Tomlin C.A Distributed Multiple-Target Identity Management Algorithm in Sensor Networks[C]//the 43nd IEEE Conference on Decision and Control，2004，3（7）:34-39.

[9]Ohs， Schenatos， Sastrys.A Hierarchical Multiple-Target Tracking Algorithm for Sensor Networks[C]//the International Conference on Robotics and Automation，2005:8（2）:12-16.