基于k近鄰平均距離的異步航跡關(guān)聯(lián)算法

衣 曉, 曾 睿,2,*

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

0 引 言

對于分布式多傳感器多目標(biāo)跟蹤系統(tǒng),由于各局部節(jié)點獨立工作,每個局部節(jié)點一般都有多條目標(biāo)航跡信息,如何判斷來自不同局部節(jié)點的航跡是否對應(yīng)同一個目標(biāo),即航跡關(guān)聯(lián),是融合中心需要解決的關(guān)鍵問題之一。而各局部節(jié)點配置傳感器的采樣周期不一致或者開機時機不同,使得融合中心收到的局部航跡往往是異步不等速率的,增加了航跡關(guān)聯(lián)的難度。

對異步航跡關(guān)聯(lián)問題,傳統(tǒng)的解決思路是進行時間配準(zhǔn),將異步航跡轉(zhuǎn)換為同步航跡進行處理。常用的時間配準(zhǔn)方法有最小二乘法和內(nèi)插外推法。文獻[8]通過偽測量技術(shù),將來自不同傳感器的測量值和濾波值重建到一個合適的時間點,再利用經(jīng)典分配算法實現(xiàn)異步關(guān)聯(lián)。文獻[9]利用勻角速度變換率插值法,將多傳感器的時間對齊,再用局部尋優(yōu)方法進行關(guān)聯(lián)。文獻[10]基于灰色關(guān)聯(lián)的思想,以先整體后局部的次序分兩級關(guān)聯(lián)修正灰色關(guān)聯(lián)矩陣,并利用灰色關(guān)聯(lián)度最大值方法實現(xiàn)關(guān)聯(lián)。文獻[12]針對分叉軌跡、交叉軌跡和組合軌跡在關(guān)聯(lián)中正確率不高的問題,基于加權(quán)思想獲取關(guān)聯(lián)質(zhì)量,引入信息散度構(gòu)造加權(quán)關(guān)聯(lián)圖進行關(guān)聯(lián)。文獻[13]基于模糊理論,選取部分關(guān)聯(lián)影響因素進行加權(quán)處理,計算得到綜合模糊隸屬度曲線,利用雙門限檢測確定關(guān)聯(lián)對實現(xiàn)關(guān)聯(lián)。但文獻[8-13]算法均需以時間配準(zhǔn)為前提,導(dǎo)致航跡數(shù)據(jù)的誤差累加,影響航跡關(guān)聯(lián)算法的性能。文獻[14]把不等長實數(shù)序列轉(zhuǎn)換為等長區(qū)間數(shù)序列,再運用灰關(guān)聯(lián)模型和最大關(guān)聯(lián)準(zhǔn)則進行關(guān)聯(lián),算法無需時域配準(zhǔn),但航跡點被區(qū)間數(shù)取代,引入了一定的誤差,影響關(guān)聯(lián)的正確率。

針對上述問題,本文提出一種基于近鄰平均距離的航跡關(guān)聯(lián)算法,定義一種新的序列距離度量,通過計算航跡序列與單一航跡點相距最近的個平均距離作為航跡序列與單一航跡點的距離,進而得到不等長航跡序列之間的灰色關(guān)聯(lián)度,利用多維分配實現(xiàn)航跡關(guān)聯(lián)。該方法無需時域配準(zhǔn),可對異步不等長航跡序列進行直接關(guān)聯(lián),并且很大程度保證了航跡信息的原始性與完整性,可顯著提高正確關(guān)聯(lián)率。

1 序列相似度度量

坐標(biāo)序列與坐標(biāo)點間的近鄰平均距離

設(shè)非空坐標(biāo)序列={(1),(2),…,()},其中坐標(biāo)點()=((),(),())∈,=1,2,…,,若對任意坐標(biāo)點=(,,)∈,有距離

設(shè)≤≤…≤≤…≤按非減次序排列,則稱

(1)

為坐標(biāo)序列與坐標(biāo)點間的近鄰平均距離。

不等長坐標(biāo)序列間的相似度

設(shè)坐標(biāo)序列集合={,,…,,…,}和坐標(biāo)序列={(1),(2),…,()},其中坐標(biāo)點()=((),(),())∈,且序列與長度不等,則坐標(biāo)序列與坐標(biāo)序列的相似度定義為

(2)

式中:

(3)

表示坐標(biāo)序列與坐標(biāo)序列的灰關(guān)聯(lián)系數(shù)。其中,=1,2,…,;=1,2,…,;實數(shù)∈[0,1]表示分辨系數(shù);()=-()=(,())。

定義1與定義2中坐標(biāo)變量均為三維坐標(biāo),因此適用于三維空間;若定義1與定義2中坐標(biāo)變量用二維坐標(biāo)表示,則可適用于二維平面。

2 基于k近鄰平均距離的航跡關(guān)聯(lián)算法

2.1 基本思想

假設(shè)兩局部節(jié)點、對公共觀測區(qū)域內(nèi)的多批目標(biāo)實施跟蹤,輸出的航跡號集合分別為

2.2 異步航跡相似度的計算

假設(shè)各局部節(jié)點異步且采樣速率不同,為融合中心固定的一個時間處理周期,以融合中心第個處理周期[(-1),]為例,局部節(jié)點、跟蹤上報的航跡批數(shù)分別為,,則上報的目標(biāo)航跡集合()可記為

圖1 局部節(jié)點對目標(biāo)的測距和測角示意圖Fig.1 Diagram of cocalnode ranging and angle measurement of target

(4)

利用式(4),可將局部節(jié)點的第條航跡序列記為

則來自局部節(jié)點的第條航跡可記為

以局部節(jié)點的全部航跡作為比較序列,局部節(jié)點的第條航跡作為參考序列,利用坐標(biāo)序列定義航跡點坐標(biāo)關(guān)聯(lián)列向量為

(5)

式中:前行表示比較序列的航跡數(shù)據(jù);第+1行表示參考序列的航跡數(shù)據(jù)。

根據(jù)航跡異步不等速率的不同情況討論的取值問題。

(1) 局部節(jié)點采樣速率一致、開機時機不一致

如圖2所示,可以看出,局部節(jié)點、的航跡點交叉分布,因此,可用局部節(jié)點的航跡點與局部節(jié)點航跡中對應(yīng)時刻前后的臨近兩個航跡點的平均距離作為局部節(jié)點航跡點與局部節(jié)點航跡序列的距離,故取2時關(guān)聯(lián)效果最佳。

圖2 局部節(jié)點時延示意圖Fig.2 Diagram of local node delay

(2) 局部節(jié)點開機時機一致、采樣速率不一致

圖3 不等長航跡示意圖Fig.3 Diagram of unequal length track

(3) 局部節(jié)點采樣速率和開機時機都不一致

(6)

式中:INT[]表示不小于的最小整數(shù)。

根據(jù)定義1中對坐標(biāo)點與坐標(biāo)序列間距離的定義,計算比較序列與參考序列間的近鄰平均距離矩陣為

(7)

式中:

(8)

進一步利用定義2可以求得局部節(jié)點的第條航跡與局部節(jié)點的第條航跡間的灰色關(guān)聯(lián)度為

(9)

式中:

(10)

2.3 異步航跡關(guān)聯(lián)判決

利用經(jīng)典分配法對灰色關(guān)聯(lián)度進行航跡關(guān)聯(lián)判決,先分別對局部節(jié)點上報的條航跡和局部節(jié)點上報的條航跡計算灰色關(guān)聯(lián)度,將其組成×維灰色關(guān)聯(lián)度矩陣,通過對分配問題的求解找出全局最優(yōu)航跡關(guān)聯(lián)對即可。

令變量

(11)

將目標(biāo)函數(shù)記為

(12)

構(gòu)成以下二維分配問題

(13)

圖4給出了基于近鄰平均距離的異步航跡關(guān)聯(lián)算法流程圖。

圖4 異步航跡關(guān)聯(lián)算法流程圖Fig.4 Flow chart of asynchronous track-to-track association algorithm

3 仿真分析與驗證

3.1 仿真環(huán)境

假設(shè)分布式系統(tǒng)中有兩個2局部節(jié)點對公共區(qū)域內(nèi)的20批目標(biāo)持續(xù)跟蹤觀測35 s,若局部節(jié)點1、2異地配置,坐標(biāo)分別為(0,0)km、(100,0)km,局部節(jié)點1的采樣周期為=02 s,局部節(jié)點2的采樣周期為=05 s,局部節(jié)點2開機時機比局部節(jié)點1延遲02 s。

假設(shè)所有觀測目標(biāo)都處于二維平面勻速直線運動狀態(tài),且起始運動方向和初速度隨機分布在0～2π rad、200～400 m/s內(nèi)。局部節(jié)點1的測距和測角誤差分別為1=150 m、1=003 rad;局部節(jié)點2的測距和測角誤差分別為2=180 m、2=002 rad。

采用正確關(guān)聯(lián)率作為航跡關(guān)聯(lián)結(jié)果的評價指標(biāo):

(14)

式中:()為融合中心在第個處理周期內(nèi)正確關(guān)聯(lián)的航跡批數(shù);為仿真實驗的蒙特卡羅次數(shù);為局部節(jié)點觀測目標(biāo)航跡的總批數(shù)。

3.2 k的取值分析

對取值做出簡要理論分析:如若取值為1,相當(dāng)于未對異步航跡情況做出處理。

表1給出了≥2時的正確關(guān)聯(lián)率和耗時對比?？梢钥吹?隨著取值由2增加到7,耗時增加明顯,這是因為取值增大會導(dǎo)致計算量明顯增加。

表1 k取值不同的耗時變化Table 1 Change in time for different values of k

表2給出了不同取值和采樣周期的正確關(guān)聯(lián)率?？梢钥吹?若局部節(jié)點1、2采樣周期比值小于等于1,則正確關(guān)聯(lián)率在取值為2時最大;若局部節(jié)點1、2采樣周期比值大于1小于等于2,則正確關(guān)聯(lián)率在取值為3時最大;若局部節(jié)點1、2采樣周期比值大于2,則正確關(guān)聯(lián)率固定在取值為4時最大。這是由于若采樣周期比值較小,則說明獲得的航跡序列數(shù)目相差甚微,此時若取值過大,則與參考航跡序列點距離較遠的比較航跡序列點也會參與航跡距離的計算,使關(guān)聯(lián)正確率降低;若采樣周期比值較大,則表示航跡序列數(shù)目相差甚多,此時若取值過小,則相當(dāng)于用較少的航跡點間距離代替整條航跡間距離進行計算,易因數(shù)據(jù)不夠充分而導(dǎo)致正確率降低。

表2 不同k取值和采樣周期比的正確關(guān)聯(lián)率變化Table 2 Comparison of correct associating rates for different values on k and the ratio of sampling periods

3.3 算法性能比較與分析

為驗證本文算法的可行性和優(yōu)越性,實施120次蒙特卡羅仿真實驗,改變實驗條件,對不同算法之間的性能進行比較分析。

圖5給出了不同算法的航跡正確關(guān)聯(lián)率對比?？梢钥吹?由于文獻[16]算法中的離散度屬于統(tǒng)計學(xué)度量,需要一定的數(shù)據(jù)量作為前提,因此正確關(guān)聯(lián)率受采樣時間長短的影響較大;文獻[17]算法利用最小二乘法實現(xiàn)異步航跡同步化,估計誤差傳播會導(dǎo)致正確關(guān)聯(lián)率較低;文獻[14]算法由于采用虛實混合變換方法對異步航跡進行同步,沒有誤差傳播,因此正確關(guān)聯(lián)率較高,但將實數(shù)序列變換為區(qū)間數(shù)和實數(shù)的混合序列會使航跡計算精度降低;本文算法利用序列距離度量,對異步航跡直接關(guān)聯(lián),沒有誤差的傳播和引入,因此從采樣初期起就一直保持很高的正確關(guān)聯(lián)率。

圖5 不同算法的正確關(guān)聯(lián)率對比Fig.5 Comparison of correct associating rates for different algorithms

圖6給出了不同目標(biāo)航跡數(shù)目下4種算法的耗時對比。可以看出,隨著目標(biāo)數(shù)目從10增加到40,各算法的耗時也在逐步增大,其中文獻[14]算法耗時最長,這是由于該算法需要對航跡序列的大部分航跡實數(shù)點做區(qū)間數(shù)變換處理,過程較為繁瑣;文獻[16]算法耗時較高,因為算法中的離散度求取包含標(biāo)準(zhǔn)差計算,因此計算量較大;文獻[17]算法作為早期經(jīng)典算法,較為簡單,因此耗時最短;而本文算法沒有對異步航跡序列做變換處理,只需對不等長航跡序列直接計算出航跡點距離的最短平均值即可,因此耗時也較短。

圖6 不同目標(biāo)航跡數(shù)目的耗時Fig.6 Time consum for different target track numbers

3.4 異步航跡關(guān)聯(lián)有效性分析

圖7比較了兩局部節(jié)點采樣率不同情況下4種算法的正確關(guān)聯(lián)率。隨著采樣率相差越來越明顯,即異步航跡序列點的數(shù)目相差變大,可以看出,文獻[16]算法主要比較兩條航跡的空間位置相似性,當(dāng)航跡點數(shù)目不滿足一定的統(tǒng)計學(xué)數(shù)據(jù)量時,正確關(guān)聯(lián)率會有一定波動;文獻[17]算法的正確關(guān)聯(lián)率下降最為明顯,這是因為通過最小二乘法對異步航跡序列同步化,需要對兩條不等長航跡序列進行插值補齊,異步航跡點數(shù)目相差越大,需要補齊的航跡點越多,估計傳播越大;而本文算法和文獻[14]算法的正確關(guān)聯(lián)率受其影響不大,穩(wěn)定性較佳,因為兩個算法都是利用距離度量來判斷兩條航跡的相似性,對航跡點數(shù)目差異不敏感。

圖7 正確關(guān)聯(lián)率隨采樣率之比的變化Fig.7 Change of the correct correlation rate with the ratio of the sampling rate

由表3可知,無論是開機時間還是采樣周期,對本文算法的正確關(guān)聯(lián)率都無明顯影響。這是因為采樣周期不同只是導(dǎo)致航跡點數(shù)目不一致,但本文算法核心是計算單一航跡點與其他航跡序列的近鄰平均距離,并不要求航跡等長;局部節(jié)點開機存在時間差異會導(dǎo)致上傳的航跡點時間不一致,但本文算法中對航跡序列間距離的求解并未利用時間信息,所以不需要航跡點的時刻一一對應(yīng)。

表3 不同采樣周期和開機時機的正確關(guān)聯(lián)率對比Table 3 Comparison of correct associating rates for different sampling periods and startup times

3.5 算法其他性能分析

改變仿真環(huán)境中目標(biāo)航跡總數(shù),目標(biāo)密集程度對算法正確關(guān)聯(lián)率的影響如圖8所示?？梢钥闯?在目標(biāo)數(shù)目增多時,文獻[14]算法的正確關(guān)聯(lián)率下降最為明顯,這是因為異步航跡區(qū)實變換后,區(qū)間重合度較高,以航跡全部數(shù)據(jù)點求解的傳統(tǒng)距離容易在數(shù)值上接近,難以辨別;文獻[17]算法雖然比較穩(wěn)定,但正確關(guān)聯(lián)率較低;文獻[16]算法正確關(guān)聯(lián)率較穩(wěn)定,這是因為該算法基于離散度,涉及均值與方差的求解,單一數(shù)據(jù)對其影響較大,故即便航跡數(shù)目增加,只要航跡非同源,離散度對其辨別能力一直較高;本文算法僅取距離最近的個點計算近鄰平均距離,可有效增加非同源航跡間距離的差異度,故正確關(guān)聯(lián)率受目標(biāo)數(shù)目影響較小。

圖8 不同目標(biāo)數(shù)目的正確關(guān)聯(lián)率Fig.8 Correct associating rates of different targets number

改變仿真環(huán)境中的噪聲分布形式,算法正確關(guān)聯(lián)率的變化如表4所示。由表4中數(shù)據(jù)可知,本文算法在高斯、瑞利、指數(shù)和均勻4種噪聲分布形式下均能保持較高的正確關(guān)聯(lián)率,基本不受噪聲分布形式的影響。

表4 不同噪聲分布形式的正確關(guān)聯(lián)率Table 4 Correct associating rates of different noise distributions forms

4 結(jié) 論

為解決異步不等速率航跡關(guān)聯(lián)問題,本文給出不等長航跡序列間的距離計算規(guī)則,用航跡序列與航跡點的距離取代傳統(tǒng)兩航跡點間距離,可對目標(biāo)航跡序列直接計算距離,最大程度保證了航跡信息的完整性和原始性,避免了誤差的引入,具有很高的關(guān)聯(lián)正確率。

算法無需時域配準(zhǔn),可對異步航跡直接關(guān)聯(lián),能有效克服來自局部節(jié)點采樣周期不一致和開機時間不同造成的影響,且不受目標(biāo)數(shù)目密集程度影響,不受噪聲分布影響,具有良好的抗噪能力。