基于圖的分布式平飛航跡關聯算法

鹿傳國， 馮新喜， 孔云波， 王振興

(空軍工程大學電訊工程學院，西安 710077)

0 引言

航跡關聯作為分布式傳感器信息融合的關鍵技術之一，是一個典型的模式識別問題，主要目的在于判斷來自于不同傳感器的航跡是否來源于同一目標。當前主流算法有統計航跡關聯和模糊航跡關聯等［1－6］。其中，統計關聯的主要思想在于尋求概率上的最近鄰，難以對實際情況進行精細刻畫，而模糊航跡關聯確定各因素權值較為困難。拓撲方法［7］是一種較為新穎的關聯算法，利用航跡數據空間位置的不變性來作為航跡的特征模式。工程應用中為獲得高的關聯精度可綜合利用各類算法，一般可先利用統計方法進行粗關聯，再利用拓撲方法進行精關聯。文獻［7－9］利用目標之間相對位置不變性使得航跡關聯獲得了較好的效果，然而這一方法仍存在一定的缺陷，在信息不完整時效果急劇惡化。

上述方法在構造檢驗統計量時都需要應用目標的方差數據，而實際工程中，受信息傳輸帶寬、存儲容量的限制往往無法實時獲取目標的方差數據，這使得傳統的統計關聯方法難以直接應用，而使用“最近鄰”算法正確率難以滿足應用需求，特別是在出現近距平飛目標時。一般而言，近距離平飛航跡由于傳感器分辨率、測量誤差以及目標在空間位置、速度、航向等各因素較為接近時而導致關聯判決錯誤率較高，是關聯判決的難點所在。

航跡實質上是一個在時空上演變的時間序列，對同一節點獲取的航跡而言，各航跡間關聯關系實質上為航跡提供了一種支持度信息。本文基于圖論的思想，給出了一種適用于平飛航跡關聯的算法。如將各航跡抽象為圖中無分辨的點，將航跡間關聯度信息抽象為各點間距離，即建立了反映航跡間關聯關系的雙向連通圖。圖中節點分布的稠密程度均從一定側面反映了航跡集合的特征。不同傳感器的公共觀測航跡關聯度信息是十分接近的，故而其所對應的鄰接矩陣必然是相似的。補圖的鄰接矩陣的特征值反映了各節點間的散射強度，可作為對應節點的特征值。

在求取節點關聯度信息時，灰色理論是一種度量時間序列間相似關系的經典方法，且對數據的完整性并無苛刻要求，但經典的灰關聯方法只表征趨勢的相似性，忽略了相對距離、方向等因素，故而在實際應用中效果較差。綜合B型灰關聯度是一種較好的改進方法，可全面描述事物發展的異同性［10］。

本文將灰理論和圖論的方法相結合，建立了一種無需方差數據即可解決平飛航跡關聯的關聯模型，該方法關聯使用的信息量較少，既考慮了航跡的發展態勢，又綜合了航跡之間的相對關系，實驗仿真也表明了該算法的正確性。

1 鄰接矩陣的建立

1.1 綜合B型關聯度

灰關聯分析的實質是整體比較，其內涵在于建立分析因子間的差異信息空間，計算差異測度，進而建立因子間的序關系［11］。綜合B型關聯度綜合考慮總體位移差、總體一階斜率差和總體二階斜率差，全面描述事物發展的異同性［12］。

定義1記兩序列分別為Xi=(xi(1)，xi(2)，…，xi(n))，Xj=(xj(1)，xj(2)，…，xj(n))。

令

則B型關聯度的計算公式為

式中，γ(Xi，Xj)= γ(Xj，Xi)且當 Xi=Xj時，有 γ(Xi，Xj)=1。

1.2 鄰接矩陣

對某傳感器獲取的航跡集合而言，將各航跡元素作為灰關聯空間中的點，將綜合B型關聯理論求取各節點關聯信息抽象為各節點間距離。

如式(4)所示，利用綜合B型關聯度建立傳感器i的鄰接矩陣 Gi=(γij)，其中 γij=γ(Xi，Xj)。鄰接矩陣具有如下特點:1)Gi為正定對稱矩陣;2)0≤γij≤1;3)γii=1。其中，γij為雙向連通圖中節點Xi與Xj的距離。

2 分布式航跡關聯

在分布式航跡關聯判決之前，每條航跡在判決者看來均是無區分的點，故直接利用某航跡元素與其余元素的關聯度作為模式向量無法做出判決，因為作為參考的航跡元素對應關系并不明確。不同節點各航跡元素相對關聯關系不變，不同傳感器鄰接矩陣之間必然相似，即必然存在初等變換矩陣X滿足

如能求解出唯一的X，即可成批完成航跡關聯判決，利用這一方法的難度在于X本身的特殊性，式(5)便是具有二次約束的超定方程，求解該方程較為困難，本文采用了矩陣主子式特征值多維分配的方法進行航跡關聯。

2.1 算法思想

由于誤差的影響，必然使得不同傳感器建立的圖中節點的距離存在微小的差異，根據鄰接矩陣定義可知，該矩陣是Hermite陣，依據矩陣擾動分析理論［13］可知，Hermite陣必為良態矩陣，即矩陣數據的擾動不會引起特征值的顯著變化。故可將余子式特征值按大小順序組成列向量，進而作為航跡元素的特征向量。

實質上，利用余子式特征值作為特征向量是一種相對向量，而在節點對應的鄰接矩陣中被刪除的行或列蘊含著該節點與其補集的距離信息，可以視為一種絕對距離信息，可利用該距離信息對主子式特征值向量進行擴維，進而抽象為主子式特征向量。

2.2 關聯唯一性問題

利用以上方法無法保證關聯判決具有絕對唯一性，原因在雙向連通圖中可能存在。故在模式提取之前，須對鄰接矩陣進行預處理，具體流程如下:

1)建立節點i初始灰關聯矩陣Gi;

2)求取Gi各l階主子式特征值向量，利用特征值判斷各主子式是否相似，設定門限，如，則將元素 p、q進行合批的處理;

3)處理后矩陣輸出。

合批具體操作為刪除矩陣Gi對應p或q的行和列，并將兩航跡元素作為一個整體參與關聯，將航跡號標示為較小航跡號。

對合批目標，可以再利用統計等方法進行處理，這里不予贅述。

目標合批出現的原因在于對稱補圖的出現，實際中主要有以下情況。

1)多目標編隊平飛，由于幾何上的對稱性而造成關聯不唯一。此時結合統計關聯方法或尋找特定參考航跡均可進行關聯判決，參考航跡的選擇一般在航跡走勢上與平飛航跡具有一定的夾角，以使得在序關系上不具有明顯的對稱性。

2)目標間距太小不足以對平飛目標關聯度產生顯著影響，此時目標幾近于合批，難以判斷，因此可行方法是利用冗余的屬性信息進行邏輯推斷。

2.3 關聯判決模型

為簡化論述，這里假定 Gi=(γij)，(i=1，2)已預處理，記Gi的各主子式分別為求取的特征值，記列向量

式中，λ1≥λ2≥…≥λN－1。

記節點l對應行記為gl，節點l與其補圖絕對距離信息定義為

引入統計量

3 實驗仿真

實際雷達航跡關聯中難以判決的往往是平飛編隊目標。本文設定了如下場景。

目標平行編隊飛行，航跡編號i=1，2，…，N，相鄰目標飛行間隔 di(i=1，…，N －1)且在區間［0.2，1］間隨機選取;目標速度為1 km/s，航向為π/3;利用兩部雷達組網對目標跟蹤，雷達坐標 O1為(0，50)，O2為(0，100)，單位為 km。

兩部雷達均通過采用卡爾曼濾波對目標進行持續跟蹤得到航跡數據，目標狀態方程為

觀測方程為

分布矩陣分別為

測量向量Z=(x，y)T，其測量矩陣為

對目標跟蹤持續時間為120 s，采樣周期T=3 s，Monte－Carlo 仿真次數為 100。

當目標數N=5時，正確關聯概率曲線及各目標正確關聯曲線如圖1、圖2所示。

圖1 關聯正確率結果對比Fig.1 Comparison of the correct association ratio of different methods

綜合圖1、圖2所得結果曲線進行分析，可得如下結論。

1)由圖1發現，本文算法航跡正確關聯概率比統計關聯算法有較大的改善，且隨著歷史數據的增加，正確關聯概率逐漸增加。這是十分明顯的，因為隨著歷史數據的增加，各航跡之間的關聯度與真實值更加相近，而最近鄰法幾乎無法分辨。

2)觀察圖2發現，目標3關聯正確率最高，其次是目標1、目標5對應的航跡正確關聯概率，而目標2、目標4對應的航跡正確關聯概率相對較小。原因在于灰度理論從實質上描述了一種序關系，目標3在序關系上具有唯一性，故而正確關聯率較高。

由以上實驗結果可以看出，基于圖論的平飛航跡關聯算法較之基于統計的最近鄰關聯算法具有更好的關聯效果，且不需要方差數據參與運算，另外，由于關聯信息對數據并無嚴苛要求，故而在個別數據丟失的情況下不會產生太大影響，進一步增強了算法的魯棒性。

圖2 各目標關聯正確率結果對比Fig.2 Comparison of the correct association of each target

4 結論

本文將傳感器獲取的航跡集合抽象為雙向連通圖，利用鄰接矩陣提取各航跡對應的特征模式。該方法充分利用了航跡數據的時空特征，而在圖上構成了一種關聯拓撲。實質上雙向連通圖表征了航跡集合的“種群特征”，利用群特征進行航跡關聯可保證整體最優，從而避免了傳統航跡關聯方法陷入局部最優而造成的航跡誤關聯，進一步優化了關聯效果。如借鑒序貫航跡關聯的思想，加入航跡管理技術，可進一步提高關聯概率。該算法從航跡的時間序列屬性著手，故而適用于純方位航跡關聯。

［1］ 何友，王國宏，陸大纟金，等.多傳感器信息融合及應用［M］.北京:電子工業出版社，2000.

［2］ 王駿，劉以安.分布式信息融合系統的性能評估方法［J］.計算機工程與設計，2007，8(15):3773－3775.

［3］ AZIZ A M，TUMMALA M，CRISTI R.Fuzzy logic data correlation approach in multi－sensor multi－target tracking systems［J］.Signal Processing，1999，76:195－209.

［4］ CHEN H，BAR－SHALOM Y.Track association and fusion with heterogeneous local trackers［C］//Proceedings of the 46th IEEE Conference on Decision and Control，New Orleans，LA，USA，2007:2675－2680.

［5］ 何友，陸大纟金，彭應寧.分布式多傳感器系統中的航跡關聯算法評述［J］.系統工程與電子技術，1999，21(10):15－18.

［6］ 朱必浩，馮新喜，鹿傳國，等.綜合利用各類信息的異類灰色航跡關聯算法［J］.電光與控制，2011，18(7):35－39.

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

［8］ 余振威，王鉞，張林，等.位置和拓撲信息融合的航跡關聯算法［C］//第十三屆全國信號處理學術年會，山東濟南，2007，23(4A):456－459.

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

［10］ 桂預風，夏桂芳，鄧旅成.賦范空間中的灰色關聯度［J］.武漢理工大學學報:交通科學與工程版，2004，28(3):399－401.

［11］ 鄧聚龍.灰理論基礎［M］.武漢:華中科技大學出版社，2003.

［12］ 黃友澎，周永豐，譚秀湖，等.基于B型灰色關聯度的純方位航跡關聯算法［J］.武漢理工大學學報:交通科學與工程版，2009，33(3):989－991.

［13］ 孫繼廣.矩陣擾動分析［M］.北京:科學出版社，1987:143－177.