多局部節點異步航跡快速關聯算法

國佳恩, 周 正, 曾 睿

(1. 海軍航空大學, 山東 煙臺 264001； 2. 中國人民解放軍91422部隊, 山東 煙臺 264001; 3. 中國人民解放軍92325部隊， 山西 大同 037001)

0 引 言

分布式多傳感器融合系統依賴精準的航跡關聯結果，以實現目標航跡的融合及多目標跟蹤[1-2]。航跡關聯是航跡融合的基礎,其核心在于尋找可以度量多源航跡的相似性測度,并通過代價函數反映航跡的接近程度,以此實現航跡的同源匹配[3]。

在航跡的相似性度量上,文獻[4]對航跡點坐標進行灰關聯分析,通過灰關聯度刻畫不同航跡組合的相似性。文獻[5]在灰關聯度的基礎上進行了進一步改進,應用虛實混合航跡序列解決航跡異步問題。文獻[6]基于灰色關聯度提出一種兩級實時航跡關聯算法,可有效應對航跡交叉及施放干擾等情形。拓撲理論同樣可應用于航跡間的相似性描述,文獻[7]參考拓撲特征描述航跡相似性,對傳感器誤差具有較強的不敏特性。文獻[8]同樣基于拓撲關系,通過構建拓撲三角形并采用最大系數原則實現了海上目標的航跡關聯,并具有抗差效果。文獻[9]提出基于相干點漂移的概率方法，解決了誤差條件下的關聯-跟蹤問題。針對傳統方法無法有效度量多源異步航跡時空相似性的問題,文獻[10]提出了一種適用于多源異步航跡的相似性度量模型,借助近似時空特征匹配點的思想確定航跡的最優匹配結果。同樣基于航跡的時空相似性,文獻[11]定義了區間序列與區間點的K近鄰區間距離度量,實現了異步航跡的抗差關聯。文獻[12-13]進一步擺脫前人將距離作為航跡相似性度量的固有范式,從航跡數據離散度的角度切入,分別定義區間離散度及概率區間離散度,以刻畫航跡的離散程度,其關聯效果優于當前最優算法,為航跡關聯問題的解決提供了嶄新的思路。

在融合系統中,傳感器數目的增加為獲取準確的目標位置提供了基礎,但如何應對多傳感器背景下的高維航跡數據是當前的一個難題[14]。現有算法多是基于兩局部節點,應用場景較為單一,將其直接應用到多傳感器時關聯效果不佳。針對該問題,文獻[15]將兩局部節點中的二維分配方法擴展為多維分配,并應用灰關聯分析求解關聯結果,首次實現了多節點條件下的航跡準確關聯。文獻[16]提出了一種基于最大似然的殘差估計配準方法和基于目標密度的序列最佳航跡關聯算法,有效解決了由多個傳感器測量的目標數量不一致時的關聯問題。文獻[17]則采用本地聯合概率數據關聯濾波器,將檢測幅度及聚類相結合,完成多傳感器航跡關聯。

在從雙節點到多節點的遷移上,現有算法[18-20]多是采用多維分配的關聯判定方法,而其巨大的運算量使得該類算法在關聯實時性上存在不足。文獻[21]提出的算法具備一定的實時關聯優勢,但其應用范圍較窄,所定義的多普勒頻差加權因數僅在雙基地高頻地波雷達跟蹤系統中具備應用價值,可遷移性不強。因此,目前亟需一種可應用于多節點的且能廣泛移植的航跡快速關聯算法,能以較低的運算量實現密集目標環境下的航跡實時關聯。

為解決航跡異步和多局部節點等復雜環境下航跡關聯困難且關聯效率低下的問題,本文提出了一種基于多維次序匹配的多局部節點異步航跡快速關聯算法。首先,以離散度作為航跡相關性度量指標解決航跡的異步關聯問題,然后在其基礎上進行改進,設計了基于虛實混合序列的時序離散度(temporal discrete degree, TDD)用于刻畫航跡狀態,并采用本文提出的多維次序匹配算法進行關聯判定,從航跡相似性計算及關聯判定兩個階段減少運算量,可實現多節點條件下的航跡快速關聯。同時，設計了用于辨別航跡交叉等誤關聯情形的TDD線性趨勢系數(TDD-linear trend coefficient, TDD-LTC)檢驗,有效提升了正確關聯率。

本文內容安排如下:第1節介紹了基于虛擬航跡重構的虛實混合航跡序列及TDD概念;第2節對多局部節點的航跡快速關聯算法進行了介紹,包括多維次序匹配原理及二次檢驗步驟的具體實現;第3節則對本文提出的算法從正確關聯率及關聯速度的角度進行了仿真檢驗。

1 虛實混合航跡序列的TDD

定義 1虛實混合航跡序列

(1)

假設X,X′分別是某一節點采集的某航跡的狀態估計及該節點的虛擬航跡,其中k=1,2,…,c代表航跡長度,虛擬航跡的設置滿足如下條件:

(1) 每一局部節點對應一個虛擬節點,虛擬航跡由虛擬節點生成,各節點虛擬航跡有且只有一條;

(2) 虛擬節點與對應局部節點的采樣頻率一致但存在固定采樣時延,同一融合周期內虛擬航跡點數與本節點最長航跡點數一致;

(3) 不同局部節點對應的虛擬節點與虛擬航跡均不同;

(4) 虛擬航跡的取值單獨定義。

則由某一節點采集的量測航跡及該節點對應的虛擬航跡所構造的虛實混合航跡序列Z定義為

Z=[Z(1),Z(2),…,Z(k),…,Z(c)]

(2)

由于初始采樣時延的存在,虛實混合航跡序列為虛擬航跡點與真實航跡點按時序交叉排布的航跡序列,Z(k)為真實航跡點與虛擬航跡點構成的二元虛實混合向量,Z(k)=(x(k),x′(k))。

定義 2TDD

虛實混合航跡序列為一組由二元虛實混合向量依照航跡點上報至融合中心的次序進行排布的序列,其TDD定義為

(3)

式中:

式中:A(k),V(k)是采用遞推方式得到的虛實混合航跡序列中前k個元素的均值及方差。初值滿足:

與離散度不同的是,當前時刻TDD的計算僅需依靠當前的航跡數據及上一時刻的TDD數據,無需對所有數據進行重復運算,大大提升了運算效率。

此時,虛實混合航跡序列Z對應的TDD序列G為

G=[G(1),G(2),…,G(c)]

(4)

2 多局部節點異步航跡快速關聯算法

2.1 基于TDD的航跡狀態描述

假設各局部節點的公共觀測區域一致,不存在獨立觀測區域,則對m個異地配置的局部節點H1,H2,…,Hm,其獲取的目標航跡數一致。記各節點觀測的航跡集合為

(5)

(6)

以位移分量x為例,假設觀測區域內共有n個目標,則局部節點i在一個融合周期內獲取的航跡狀態矩陣為

(7)

依照定義1給出的虛擬航跡構造原則,對融合系統中的所有節點構造虛擬航跡,得到虛擬航跡組:

(8)

結合虛擬航跡對原航跡狀態矩陣進行插值重構,得到局部節點i獲取的基于虛實混合航跡序列的狀態矩陣:

(9)

式中:

基于虛實混合航跡序列的狀態矩陣維度與原狀態矩陣維度一致,矩陣元素為虛擬航跡點與真實航跡點構成的二元虛實混合向量,即

(10)

(11)

2.2 基于多維次序匹配的航跡關聯判定

在以往的多局部節點航跡關聯研究中,無論是利用幾何距離或是離散度作為航跡的相似性度量,關聯判定階段都需應用多維分配算法進行同源航跡的匹配運算,雖然該算法可以求得給定條件下的全局最優解,但是約束條件使得其求解過程過于復雜,拉格朗日松弛算法的引入解決了多維分配算法中的組合優化難題,其最優解的逼近過程也十分耗時,在實際應用中關聯速度較慢,亟需快速關聯算法的提出,以實現航跡的實時關聯。

表1隨機模擬了具有相同采樣周期的3個局部節點采集的小批量航跡數據及虛擬航跡(各節點虛擬航跡相同)。按照定義1的方式構造虛擬航跡并對原航跡進行插值重構,可得到9組虛實混合航跡序列,分別求解各航跡序列的離散度并按離散度大小在節點內進行排序(降序),排序結果如表1所示。

表1 航跡數據及離散度排序結果

由表1可以看出,對應同一目標的同源航跡在分別與虛擬航跡構造虛實混合航跡序列后,其離散度在對應節點內的排序結果相同。這是因為離散度衡量的是數據偏離中心的程度,而同一目標在不同節點上的量測數據相差不大,在與同一虛擬航跡進行混合后,其混合航跡序列離散度差異小于非同源航跡,因此可根據離散度的次序進行航跡關聯,將各節點中離散度次序相同的航跡作為對應同一目標的同源航跡。

仿真實驗是對混合航跡序列的全局離散度進行的單維次序匹配,下面結合TDD給出基于多維次序匹配的航跡關聯判定方法。

首先給出虛擬航跡的構造方法。由于不同節點的采樣周期存在差異,依據定義1給出的虛擬航跡構造原則分別構造虛擬航跡。對于不同節點,在各掃描周期內選取坐標最大的位移分量構造虛擬航跡點,并按時序排布構造虛擬航跡,虛擬航跡在位移分量x上的狀態向量為

(12)

(13)

當目標數及節點數較多時,對大批量航跡數據進行單維次序匹配的錯誤關聯率較高,難以滿足實際任務需要。為獲取更為可靠的關聯結果,除利用x,y兩組位移分量進行雙重檢驗,還可從Gi中抽取多組TDD序列進行多維次序匹配,將航跡起始階段的離散度信息納入航跡關聯判定,以實現航跡的精準關聯。

多維次序匹配的維數即進行次序匹配的次數,維數的確定依賴于航跡長度、航跡數目及節點數。一般而言，航跡越長、航跡數或節點數越多,就需要進行更多的次序匹配,以保證關聯效果。在維數確定后,需要抽取不同維度的TDD序列,TDD序列的維度指其在TDD矩陣中的列號。為獲得較高的正確關聯率,給出多維次序匹配的TDD序列抽取原則:

(1) 確保從各TDD矩陣抽取相同維數及相同TDD序列,進行次序匹配;

(2) 盡可能保證各維度間隔相同;

(3) 匹配維數應大于1,同時盡量避免各抽取維度間隔過近;

(4) 原則優先級為(1)>(2)>(3)。

依照TDD序列的抽取原則可避免由單維次序匹配導致的關聯正確率過低,同時避免由匹配次數過多導致的運算量增加。

假定抽取了S組TDD序列進行S維次序匹配,則結合x,y兩組位移分量可得到2×S組關聯航跡組合:

(14)

對S維次序匹配2S組關聯結果,定義關聯判定函數:

(15)

由此,基于多維次序匹配的關聯判定算法步驟可描述如下:

步驟 1根據航跡長度、航跡數目及節點數目,確定多維次序匹配的維數;

步驟 2根據匹配維數抽取TDD序列,進行排序;

步驟 3依據排序結果進行多維次序匹配,確定關聯航跡組合;

步驟 4根據關聯判定函數確定最終關聯結果。

區別于兩局部節點正確關聯率的單一性,多局部節點對應同一目標的觀測航跡有多種關聯結果,需要對多節點情況下的正確關聯率進行分級,以更全面地表征算法關聯效果。

定義 3多局部節點p元正確關聯率

若將每一個目標設定為一個類別,則關聯判定即是將所有航跡針對目標類別進行分類的過程。對于m個局部節點,n個目標,經過關聯判定后每個目標類別內都有m條航跡,假定以節點1的航跡號作為目標類別號,則對于目標類別j,其類內正確分類數為

(16)

式中:

多局部節點p元正確關聯率即各目標類別中類內正確分類數大于等于p的概率,即

(17)

其中，

表示類內p元正確關聯數。

2.3 TDD-LTC檢驗

圖1(a)模擬了航跡的合并(分叉、交叉)現象，其中藍色航跡分別表示節點2中與節點1某航跡對應的同源航跡及合并(分叉、交叉)航跡。在仿真實驗中,航跡起始階段橫坐標相同,為縱向合并、分叉及交叉。分別計算3種特殊情況下混合航跡序列TDD的變化趨勢,計算結果如圖1(b)和圖1(c)所示。

圖1 航跡合并、分叉、交叉及時序離散度變化情況Fig.1 Track merge, fork, cross and temporal discrete degree change trend

由圖1可以看出,無論在位移分量x或y,同源混合航跡序列與合并(分叉、交叉)混合航跡TDD在航跡終點相差不大。這是由于航跡合并(分叉、交叉)時同源航跡與合并(分叉、交叉)航跡的幾何中心存在重疊,導致TDD差異不明顯。若不進行二次檢驗,無法有效區分同源與合并(分叉、交叉)航跡,容易造成誤關聯。

由于航跡起始階段的橫坐標相同,因此同源混合航跡序列與合并(分叉、交叉)混合航跡TDD在x位移分量上相差不大,且均保持了較為平滑的遞增趨勢,而在y位移分量上則顯現出了差異。由此,根據TDD隨航跡獲取過程的趨勢差異,引入TDD-LTC檢驗來進行航跡合并(分叉、交叉)辨別。

定義 4TDD-LTC

定義虛實混合航跡序列前k個元素的TDD-LTC為

(18)

式中:

同源航跡TDD是緩慢遞增的,因此其混合航跡序列TDD-LTC趨近于1;而TDD在航跡合并(分叉、交叉)時具有反向趨勢,因此合并(分叉、交叉)混合航跡序列的TDD-LTC較小。實際判別過程可以以0.9為界,若TDD-LTC大于0.9,則表明混合航跡序列TDD遞增趨勢較強,可視為同源航跡;若TDD-LTC小于等于0.9,表明混合航跡序列TDD趨勢存在波動,認為關聯到合并(分叉、交叉)航跡,不予關聯。圖2是本文算法的流程圖。

圖2 本文算法流程圖Fig.2 Flowchart of the proposed algorithm

3 仿真分析與檢驗

3.1 仿真環境

假設由6個局部節點構成對200 km×200 km目標空域的監視跟蹤系統,各節點位置及技術參數如表2所示。仿真實驗共模擬60批次目標,各目標初始位置隨機,初始航向不定,設定目標做勻速直線運動,速度范圍為[200 m/s,600 m/s]。

表2 各節點位置及技術參數

采用分級正確關聯率對各算法進行性能評價,并采用箱線圖形式對其進行表示,如圖3所示。

圖3 分級正確關聯率圖形表示Fig.3 Graphical representation of hierarchical correct correlation rate

3.2 算法關聯精度分析

圖4是本文算法及文獻[5]和文獻[13]所述異步關聯算法隨仿真步長的分級正確關聯率對比。由于文獻[5]和文獻[13]所述算法無法直接被應用于多局部節點,因此將其分別與多維分配算法進行組合,來檢驗其關聯精度。

圖4 分級正確關聯率隨時間步長的變化情況Fig.4 Change of hierarchical correct correlation rate with time step

從圖4可以看出,本文算法關聯精度隨仿真時長變化不明顯,而文獻[13]算法呈現出了較明顯的下降趨勢。這是由于航跡數據量隨仿真時長的增加不斷增大,而數據規模越大,不同航跡的離散度可辨別性越差,不同航跡間離散度的相似性導致錯誤關聯率增大。而本文算法采用的多維次序匹配方式克服了傳統算法僅進行單次關聯判別帶來的偶然性,多維TDD序列的匹配將航跡起始階段的信息也納入到了關聯判定中,因此對不同規模的量測數據具備不敏特性。由文獻[5]算法得到的各級正確關聯率均低于上述兩種算法,關聯效果不佳。模擬不同數量的目標,觀測算法的關聯效果如圖5所示。

圖5 分級正確關聯率隨目標數的變化情況Fig.5 Change of hierarchical correct correlation rate with target number

由圖5可以看出,多節點情況下隨目標數目的增多,三類算法的關聯質量均有所下降。本文算法采用的多維次序匹配方法在進行單維匹配時的TDD序列元素個數與目標數一致,因此在進行次序匹配時增大了誤匹配率,導致整體正確關聯率出現下降,但由于采用了多維次序匹配,匹配次數的增加在一定程度上抵消了誤關聯概率,使得相同條件下本文算法的關聯效果略遜于多維分配算法,但相差不大。

不同節點數各算法的平均正確關聯率如表3所示。

表3 平均正確關聯率隨節點數的變化情況

從表3可以看出,節點數的增多同樣增大了關聯的難度。在進行多維次序匹配時,TDD次序相同,則其對應的航跡被認為是同源航跡,節點數越多,同源航跡組內的元素個數越多,多節點航跡全部正確關聯的難度就越大。對于具有m個節點的融合跟蹤系統,其m元正確關聯率也就越低。采用多維度的次序匹配同樣在一定程度上抵消了由節點數增加帶來的誤關聯,使得相同條件下本文算法與多維分配算法關聯效果相差不大。

圖6是對不同算法的異步關聯效果的檢驗結果。本文算法是在離散度基礎上進行的改進,僅運算方式存在差別,因此適用于異步航跡的直接關聯,且關聯效果與文獻[13]提出的方法基本相同,驗證了TDD在進行異步關聯時的有效性。

圖6 分級正確關聯率隨采樣率的變化情況Fig.6 Change of hierarchical correct correlation rate with sampling rate

3.3 算法快速關聯效果分析

由于本文算法采用多種方法提升多節點條件下的航跡關聯速度,在航跡相似性計算及關聯判定階段都進行了算法創新,因此采用組合的方式對算法的快速關聯效果進行檢驗。

圖7是對目標空域觀測時間不同時系統的關聯耗時情況。

圖7 關聯運算耗時隨觀測時間的變化情況Fig.7 Change of correlation operation time with observation time

一般而言,觀測時間越長,航跡數據規模越大,關聯解算所需的時間也就越長。可以看出,本文算法在關聯速度上最具優勢,將TDD及多維次序匹配算法分別與傳統算法進行組合后,系統關聯運算耗時亦有所下降。而文獻[5]方法需要對原始航跡數據進行虛實混合序列變換,該步驟及后續灰關聯度的求解均十分耗時,導致算法運算效率較低。

同樣,以m個節點及n個目標為例,假設航跡點數為r,不同組合算法的運算量比較如表4所示,其中①、②、③、④分別代表TDD、離散度、多維次序匹配、多維分配。

多維次序匹配的實現依賴于多維度的TDD序列,若采用文獻[13]的離散度計算方式,則會不可避免地導致數據的重復運算;而本文設計的TDD僅依賴上一時刻運算得到的離散度與當前上報的航跡數據,即可遞推得到當前的離散度,將文獻[13]中離散度的整體運算分散到航跡上報的各個時刻,在獲取不同維度離散度數據的同時降低了運算量,有效提升了關聯速度。

表4 不同組合算法的運算量比較

多維次序匹配則克服了傳統多維分配算法的速度缺陷,巧妙地利用離散度在衡量數據離散程度上的固有特性,用次序匹配替代全局運算,經一次排序便可完成對所有航跡的關聯解算,使算法復雜度大大降低。圖8是不同目標數目下的系統運算耗時。由圖8可以看出,本文算法在不同目標數下均取得了最佳關聯速度,較低的運算耗時也使得融合中心可以一邊接收各節點上報的航跡,一邊進行實時的關聯解算。

圖8 關聯運算耗時隨目標數目的變化情況Fig.8 Change of correlation operation time with the number of targets

繼續改變局部節點數目,檢驗本文算法的快速關聯效果,結果如表5所示。

表5 關聯運算耗時隨節點數變化情況

結合表5及圖4～圖8可以看出,本文提出的TDD及多維次序匹配算法均能有效提升關聯速度,相比傳統算法優勢明顯,在不損失關聯精度的同時實現了航跡的快速關聯。

3.4 對航跡合并、分叉及交叉的辨別

現代戰場空情復雜多變,戰場形勢的要求及飛行器機動性能的提升使得航跡的合并、分叉及交叉等現象愈發普遍。圖9是不同的航跡合并、分叉及交叉比例下各算法的關聯效果。

圖9 分級正確關聯率隨航跡交叉比的變化情況Fig.9 Change of hierarchical correct correlation rate with track crossing ratio

由于增加了TDD-LTC二次檢驗環節,本文算法在不同的空情復雜度下均實現了較高的正確關聯率,對于航跡合并、分叉及交叉的辨別要優于文獻[5]和文獻[13]。文獻[5]采用虛實混合序列的方式進行關聯,并沒有針對航跡交叉等情形提出解決方法,因此當航跡交叉率較高時,其關聯效果較差。文獻[13]針對航跡交叉前、后離散度的變化對航跡序列進行分段,并提出采用分段航跡序列離散度對由航跡交叉導致的關聯困難問題進行解決。但是,從關聯效果來看,文獻[13]所提算法不及本文算法,這是由于分段數目的不同對正確關聯率有很大影響,針對不同場景需要采用恰當的分段數,才能取得較好的關聯效果。

4 結束語

為實現多局部節點條件下的航跡快速關聯,本文采用TDD及多維次序匹配的組合方法降低運算量,采用遞推方式克服了傳統離散度運算方法的冗余性,而多維次序匹配則避免了由傳統多維分配方法的全局運算帶來的運算量爆炸,同時多維度的TDD序列綜合利用了航跡的整體信息,在不損失關聯精度的同時實現了航跡的快速關聯,具有良好的應用前景。下一步,將結合實測數據進行算法檢驗,不斷完善算法,使其具備適應不同戰場環境的魯棒性。