基于拓撲相似度的航跡關聯算法＊

郭 強 符 拯

（1.海裝西安局 西安 710054）（2.海軍駐航天三院軍事代表室 北京 100074）

1 引言

在多雷達跟蹤系統中，融合來自多部雷達對同一目標的觀測信息可以獲得更為精確的目標狀態估計。實際系統多采用分布式的融合體系結構，即單部雷達產生局部航跡傳送到融合中心，在融合中心進行航跡關聯；對同一目標的航跡進行融合，得到系統航跡。多目標環境中，航跡關聯是多雷達數據融合中的一個關鍵問題，也是實現航跡融合的前提，關聯判決結果將直接影響整個融合系統的性能［1～2］。系統中的多種不確定性，包括雷達自身的系統誤差、隨機誤差以及密集的雜波干擾，是航跡關聯實際應用中面臨的主要問題。

用于航跡關聯的算法通常可分為兩類：一類是基于統計的方法，另一類是基于模糊數學的方法。統計方法的思想是將航跡關聯問題轉換為假設檢驗問題，構造利用兩局部節點的航跡估計服從特定分布的檢驗統計量，并根據事先確定的門限值來判斷兩航跡是否來自同一目標。在文獻［3］中，提出了一系列基于統計方法的航跡關聯算法。模糊方法的思想是利用在航跡關聯判決中存在的模糊性，用模糊數學的隸屬度函數來表示，也就是用隸屬度概念來描述兩個航跡的相似程度。為此，文獻［4］又研究了模糊航跡關聯算法，討論了多傳感器航跡關聯中模糊因素集與隸屬度函數選擇，研究模糊因素的確定與模糊權集的動態分配等問題。然而，當系統包含較大的導航、傳感器校準及轉換和延遲誤差時，有時統計和模糊的方法均顯得力不從心。

本文提出了一種新的航跡關聯算法——拓撲相似法［5］，該算法充分利用目標之間的拓撲信息來衡量航跡間接近的程度，對樣本量的大小沒有太高的要求，分析時也不需要典型的分布規律，為航跡關聯問題探索一條新的途徑。

2 問題的描述

設目標狀態矢量由目標的位置、目標的速度、目標航向以及目標加速度等p個特征參數構成。

為了討論問題的方便，假設送至融合中心的所有狀態估計＾Xij（i＝1，2，…M；j＝1，2，…ni）都在相同的坐標系里，并且各傳感器同步采樣，這里M是局部節點數，ni是節點i的航跡個數。對于特殊的應用可以定義需要的坐標轉換和恰當的時間校正，另外，還假設數據的傳輸延遲時間為零。統一的坐標轉換是容易實現的工作，時間延遲可以通過延遲修正和外推補償，而采樣與更新的不同步可通過平滑、插值及外推完成目標狀態估計點的時間校準。為了進一步簡化分析這里假定M＝2討論。

設局部節點1、2的航跡號集合分別為

把來自局部節點2的n2條航跡看成是n2個已知模式，而把局部節點1的航跡i（i∈U1）看成是待識別模式，那么航跡關聯問題實際上就是一個典型的模式識別問題。

3 拓撲相似法的原理

3.1 目標拓撲結構

受到人工判別過程的啟發：將待關聯目標周邊的其他目標作為參照物，目標間的空間信息就可為關聯判決提供更多的參考。定義這種新的信息稱為目標的拓撲結構［6］，即以待判目標為原點，周邊的目標作為參照物所構成的拓撲結構，空間上相距較近的目標，拓撲結構是截然不同的。因此，拓撲結構是區分目標的一個有效的特征。將不同雷達觀測到的同一個目標的拓撲結構進行比較，實際上就是把雷達觀測坐標進行了平移變換，把坐標原點平移到了待判決目標上。圖1中顯示了5個目標在空間的分布情況，圖2（a）中比較了不同雷達對目標C觀測的拓撲結構，方位偏差導致了拓撲結構之間的旋轉，雖然觀測的目標的絕對位置有較大差異，但拓撲結構的差別卻不大；圖2（b）是兩部雷達看到的不同目標（B目標和C目標）的拓撲結構之間的比較，差異很大。

圖1 目標空間分布

圖2 拓撲結構

3.2 計算拓撲相似度

依據每個雷達在k時刻探測到的目標，以任一目標為參考點，其他目標到參考點的距離差向量為成員，可以計算出每個目標的拓撲。這個拓撲表示為一個向量序列，其中的每一個成員是鄰居到該目標參考點的距離差向量，而且按方位角遞增順序排列［7］。

假設雷達監視區內有N個目標，則局部節點1的目標參考點t及其N－1個鄰居的坐標向量序列是

拓撲序列是

同理，局部節點2的目標參考點r及其N－1個鄰居的坐標向量序列是

拓撲序列是

所以對局部節點1來說，目標到參考點的距離可以表示為

同理，對局部節點2來說，目標到參考點的距離可以表示為

這樣，航跡與航跡之間的相似程度用拓撲相似度來表示

這里，abs為求絕對值運算，計算拓撲相似度的拓撲算子為St，r（k）

3.3 拓撲相似法關聯準則

當計算出描述兩航跡接近程度的拓撲相似度之后，下一步就是如何判決兩航跡間的相似性。為了給出航跡i（i∈U1）與航跡j（j∈U2）間的相似性判決，需要對拓撲相似度按從大到小進行排序，即得相似序。這里我們采用最大相似度識別原則，即

則判決航跡t在l時刻與航跡r＊關聯，并且r＊在l時刻不再與其他航跡關聯；否則來自局部節點的航跡t在l時刻不與來自局部節點2的任何一條航跡關聯。其中ε為閾值參數，0.5≤ε＜1，閾值可以通過仿真來確定。

4 仿真分析

為了討論問題的方便，這里僅考慮兩個局部節點，并且每個局部節點配有一部2D雷達。仿真環境1：雷達測距和測角誤差分別為σρ1＝170m，σθ1＝1°，σρ2＝180m，σθ2＝1°用蒙特卡洛方法進行50次仿真，每次仿真14步，采樣間隔T＝4s，假設在兩傳感器的公共觀測區域內有60批目標，模擬目標在一個二維平面上具有變速、存在有意和無意機動，具有可以認為在速度上變化的過程噪聲，目標初始速度在4m／s～1200m／s之間均勻分布，初始航向在0～2π之間均勻分布，目標初始位置在x＝190km，y＝135km處按正態分布產生，兩局部節點的位置分別為（125km，125km）和（235km，130km）。

仿真結果1：

仿真分析1：圖3給出了在公共觀測區域60批目標的運動軌跡，圖4～6分別給出的是對圖3所示的公共區域目標的航跡分別采用拓撲相似法和加權法仿真50次后的平均正確關聯率、錯誤關聯率和遺漏關聯率曲線，由圖3可以看出拓撲相似法的正確關聯率明顯高于加權法，并且它的正確關聯率相當的高，幾乎趨近于1，由圖6可以看出拓撲相似法的漏關聯率等于0，而加權法在一定程度上則存在著漏關聯率，通過上面的比較，可見拓撲相似法較好的關聯性能。

圖3 60批目標的運動軌跡

圖4 拓撲相似法與加權法正確關聯率對比

圖5 拓撲相似法與加權法錯誤關聯率對比

圖6 拓撲相似法與加權法漏關聯率對比

仿真環境1：雷達測距和測角誤差分別為σρ1＝120m，σθ1＝0.6°，σρ2＝110m，σθ2＝0.6°，用蒙特卡洛方法進行50次仿真，每次仿真14步，采樣間隔T＝4s，假設在兩傳感器的公共觀測區域內有N＝10批目標，模擬目標在一個二維平面上做勻速直線運動，具有可以認為在速度上變化的過程噪聲，目標速度為vx＝600m／s，vy＝600m／s，目標初始位置在x＝165km，y＝115km附近產生，目標之間的間距設為d＝2000m，兩局部節點的位置分別為（125km，125km）和（235km，130km）。

在模擬目標運動時，取

仿真結果2：

圖7 10批目標的運動軌跡

仿真分析2：圖7給出了在公共觀測區域10批目標的運動軌跡，表1給出了拓撲相似法的正確關聯率隨目標間距變化情況，從表1可以看出拓撲相似法的正確關聯率對目標的間距不敏感，當目標間距變化時，它的正確關聯率指標基本保持穩定，只有少量的提升，特別是正確關聯率都保持在95%以上，表2給出了拓撲相似法的正確關聯率隨目標個數變化情況，從表2可以看出拓撲相似法的正確關聯率隨目標個數的遞增有少許的下降，當目標個數達到120時，它的正確關聯率仍可以維持在91%以上，說明該算法能夠很好的適應密集目標環境，表1和表2綜合說明了拓撲相似法較高的關聯精度和魯棒性。

表1 拓撲相似法正確關聯率隨目標間距變化情況（N＝10）

表2 拓撲相似法正確關聯率隨目標個數變化情況（d＝2000m）

5 結語

目標之間的拓撲關系可以為航跡關聯提供更多的有用信息，利用目標拓撲結構這一新的特征進行判決與人工數據關聯判決過程非常相似。本文提出了一種基于拓撲相似度的航跡關聯算法，該算法充分利用了目標之間的拓撲信息來衡量航跡間接近的程度，避免空間劃分不均勻、算法經驗性太強、對密集航跡場景不適應等多種問題，仿真結果表明該方法具有很好的有效性和魯棒性，值得推廣。

［1］Bar－Shalom.Y.， William.D.B.， Multitarget－Multisensor Tracking，Applications and Advances［M］.Artech House，2001：225－231.

［2］Bar－Shalom.Y.A Tutorial on Multitarget－Multisensor Tracking and Fusion.1997，IEEE National Radar Conference，15 May 1997，Syracuse，NY：153－156.

［3］Chong，C.－Y.，Mori，S.，Barker，W.H.，and Chang，K.－C.Architectures and algorithms for track association and fusion.IEEE Aerospace and Electronic Systems Magazine，15，1（Jan.2000）：5－13.

［4］Rao，B.S.，and Durrant－Whyte，H.F.Fully decentralized algorithm for multisensor Kalman filtering.IEEE Proceedings，Pt.D，138，5（1991）：413－420.

［5］Bar－Shalom.Y.， William.D.B.， Multitarget－Multisensor Tracking，Applications and Advances［M］.Artech House，2001：155－157.

［6］何友.分布式多傳感信息融合算法研究［D］.清華大學，2006.

［7］何友，王國宏，陸大金，等.多傳感器信息融合及應用［M］.第二版.北京：電子工業出版社，2000：7－13.

［8］楊哲，韓崇昭，李晨，等.基于目標之間拓撲信息的數據關聯方法［J］.系統仿真學報，2008，20（9）：2357－2360.

［9］石玥，王鉞，王樹剛，等.基于目標參照拓撲的模糊航跡關聯方法［J］.國防科技大學學報，2006，28（4）：105－109.

［10］李啟元，段立，李亞楠.海戰場目標航跡間距離聚類方法［J］.計算機與數字工程，2010（5）.

［11］熊瑜，饒躍東.基于改進蟻群算法的無人飛行器航跡規劃［J］.計算機與數字工程，2010（7）.

［12］吳澤民，任姝婕，劉熹.基于拓撲序列法的航跡關聯算法［J］.航空學報，2009，30（10）：1937－1942.