基于TDoA網格鄰域匹配的飛機多點定位新方法

戴 敏

(中國民用航空飛行學院計算機學院 四川 廣漢 618307)

0 引 言

隨著航空交通的持續發展，空中交通管制(Air Traffic Control,ATC)需要管理的飛機數量也日趨增加。目前，大型機場的每天起降量超過1 500架次。空中交通管制的關鍵是需要知道飛機在任何時刻的位置。對于地面管制員，獲得飛機位置的傳統手段包括高頻語音通信和一次/二次監視雷達(PSR/SSR)[1-2]。近些年，隨著技術發展和更嚴格的定位要求催生了其他飛機定位方法，主要有廣播式自動相關監視協議(ADS-B)和多點定位(Multi-lateration,MLAT)[3-4]。其中，ADS-B完全依賴于飛機向其他飛機或地面站正確廣播自己的位置，而MLAT則利用多個不同地面站接收到信號的到達時差(Time Difference of Arrival,TDoA)進行獨立定位[5-6]。與以往的雷達監視相比，這兩種定位方法都有效提高了定位精度，其中MLAT的定位獨立性更強，是未來空中交通管制發展的關鍵技術。

MLAT方法主要是利用TDoA進行定位，TDoA測量的準確性直接影響定位精度，其中誤差源主要有無線電非視距(NLoS)傳播中的多徑效應以及測量系統誤差，另外，地面接收站的幾何部署結構也影響著定位精度。目前，一些學者對MLAT方法進行了改進，改進主要有兩個方向：對MLAT中位置求解過程的改進[7-8]和對TDoA數據的后處理[9]。文獻[7]對MLAT中基于TDoA獲得的定位方程組的求解過程進行改進，融入了Bancroft算法使獲得的解更準確。文獻[8]在用于機場地面監視的MLAT模型中，將TDoA數據建模為統計模型，然后使用最小二乘法或奇異值分解等方法對這個模型進行求解，從而獲得飛機位置估計。文獻[9]采用Kalman濾波中遞推估計思想對TDoA進行處理，以此減小噪聲干擾產生的誤差。在上述改進方案中，定位精度仍然不夠理想，有些方法利用復雜的誤差估計算法來提高TDoA測量準確性，運算量很大會影響定位效率。

當前MLAT以及一些改進方法都是通過測量TDoA和距離計算來定位，這樣不可避免地受到地面站分布和TDoA測量過程中各種干擾的直接影響。本文徹底改變了這一做法，不用直接根據TDoA計算距離來定位，而是將測量到的TDoA與預期TDoA進行匹配來定位。該方法的具體思想是：首先將監測空域進行網格分割，計算各網格中心點到各地面接收站的預期TDoA。然后，在實際定位中，根據測量到的TDoA向量，通過提出的加權K-最鄰近(K-Nearest Neighbor,K-NN)算法將測量TDoA值與預期TDoA值進行匹配，通過鄰居加權平均來估計最終的飛機位置。這種方法有以下幾個優點：

(1) 提出一種新的定位技術思想，通過反向推理來進行定位，對擴展定位技術路線具有一定的意義。

(2) 對傳統K-NN進行改進，構建加權K-NN算法，使其在飛機定位應用中具有更高的精度。另外由于采用了鄰域計算，所以在噪聲環境下具有較強的魯棒性。

(3) 由于該方法不是直接根據接收站測量的TDoA進行幾何運算定位，所以對地面接收站的幾何結構依賴性較小。

在一個真實數據集上評估了本文方法，結果表明在廣域環境下的定位性能優于MLAT，特別是存在較大噪聲的情況下。另外，本文方法可擴展性更強，可以提高監視范圍，且不依賴于完美的接收站幾何部署結構。

1 飛機定位問題

飛機定位問題與其他無線定位問題有以下幾點區別：(1) 室外環境，與許多定位問題不同，飛機定位問題是室外的，為此需要為信號損失和傳播構建一個戶外傳播模型。(2) 遠距離，在廣域空中交通管制監視中，覆蓋的距離遠大于局部或室內問題。對于巡航高度飛行的飛機(商用飛機通常為1萬米或更高)，需要觀測400 km或更遠的范圍。

目前實際應用的空中交通管制技術之一是ADS-B協議，其使用兩個潛在的數據鏈路(1090ES或UAT)，飛機自動將其位置和速度信息(每秒2次)以及其標識(每5秒1次)廣播給附近的其他飛機和地面站。由于可以用廉價的無線接收器捕獲無線信號，眾包傳感器網絡近年來也越來越受歡迎。為此，使用無線接收器就可以接收飛機發送的任何信號(包括ADS-B和SSR)，只需要獲得這些信號的接收時間差就可以進行定位，因此出現了MLAT定位方法[10]。

2 MLAT及缺陷分析

2.1 MLAT定位方法

MLAT根據飛機發送信號的TDoA來計算之間距離，然后再根據多個接收站之間的位置關系來定位飛機的位置[11]。

為了使用MLAT定位目標的二維坐標，需要測量至少三個接收站從某個飛機接收相同信息的時間。通過一個TDoA信息所獲得目標的位置軌跡為一個雙曲線，當存在2個TDoA信息時，兩條曲線的交點即為目標的平面二維坐標[12]，如圖1所示。中央處理站根據接收站之間信號的TDoA，通過相交雙曲面計算來獲得飛機位置。當設定目標位置為三維坐標時，則至少需要4個接收站。

圖1 具有三個接收器和兩個雙曲面的基本MLAT結構

假設有M個接收站捕獲到飛機信息，(x,y)為飛機位置二維坐標，(sxi,syi)為接收站i的位置，那么飛機與接收站i的實際距離為：

(1)

定義飛機到接收站i與到基準接收站1的距離之差的實際值為ri,1，表示為：

(2)

(3)

(4)

(5)

式中：向量R=[r2,r3,…,rM]T，R1=[r1,r1,…,r1]T，E=[e2,1,e3,1,…,eM,1]T，ei,1=eni,1+eτi,1。ΔR表示為：

ΔR=R-R1+c·E=

[r2-r1,r3-r1,…,rM-r1]T+c·E

(6)

求解式(5)所示的最小化問題有解析表達式方法和迭代方法，其中常用的解析表達式方法為Chan等[13]提出的算法，該算法計算量小且定位精度較高。

2.2 MLAT存在的問題

盡管MLAT很有效，但它仍存在一些缺陷，描述如下：

(1) MLAT非常容易受到系統噪聲和異常值的影響。由于存在多徑效應和測量系統偏差，測量得到的TDoA中存在隨機波動(噪聲)，這就導致直接根據TDoA計算得到的軌跡曲面存在誤差，限制了定位精度。

(2) MLAT定位精度還受到幾何精度稀釋因子(GDOP)的影響。GDOP是由目標與地面接收站的位置關系決定[14]。在接收站具有相同時間誤差下，不同的布局會導致不同的GDOP。由于MLAT要求至少有三個接收站，而地理上的障礙(如山脈、河流)使在服務空域內安裝一個通過精心規劃幾何結構的廣域系統更加困難，否則不能提供足夠好的GDOP值來實現高服務質量。

圖2舉例描述了存在兩個接收器的部署對目標位置計算誤差的影響。其中，圓環內區域表示各個接收器的距離測量誤差，兩個接收器測量的交集部分表示目標物體真實位置的可能區域。其中：圖2(a)為部署較差時的情況；圖2(b)為部署較合理時的情況。可以看到，圖2(a)中兩個接收器部署較近，存在監測范圍重合情況，導致定位誤差區間較大，嚴重影響定位精度。

(a) 高精度稀釋 (b) 低精度稀釋圖2 不同部署對幾何精度稀釋(GDOP)的影響

本文方法對接收站部署幾何結構的依賴性降低，可以解決MLAT的可伸縮性和覆蓋率問題，特別是在幾何結構不理想的情況下。MLAT中，接收站之間的接收范圍需要重疊來獲得時差，如果接收站部署較近，則會降低總體覆蓋率。更糟糕的是，由于GDOP的增加會導致監測準確性迅速惡化。本文方法通過TDoA數據匹配來實現定位，有效降低了受GDOP的影響，且使用較少的接收站就可以達到精確性要求，提高了MLAT的效率。

3 飛機定位方法

如前所述，傳統MLAT利用多個接收站捕獲信號并計算TDoA來估計目標的位置。本文轉變了這個思想，提出一種基于網格匹配的飛機定位方法。不是直接根據TDoA來計算位置，而是將測量得到的TDoA與根據部署結構預先得到的預期TDoA模型進行匹配，從而得到位置。這種方法具有更高的定位精度，且提高了信號利用率和監測部署的總體覆蓋率。另外，該方法對接收站部署的幾何結構具有很好的適應性，從而可以有效降低成本。

3.1 預期TDoA

本文方法的關鍵之處在于預期TDoA的使用。首先將監測區域進行預先網格劃分。通常情況下，大空域內的飛機定位只需要2維坐標即可，不需要高度信息。為此，為了方便描述，這里將監測空域分割成一個N×M個正方形平面網格，其中：N表示東西方向上網格數量；M表示南北方向上網格數量。如圖3所示。

圖3 空域網格化及預期TDoA計算

然后，根據已知的接收站部署位置信息，計算每個網格中心到多個接收站(i=1,2，…,n)之間的物理距離(d1,d2,…,dn)，然后根據距離計算信號傳播時間，以及各接收站之間的預期TDoA向量，這里的接收站數量由接收站的探測范圍決定。

設定tmin為某個網格點到多個接收站之間的最小時間，那么將到其他接收站的時間減去tmin可以獲得相對于最近接收機的期望TDoA(ETDoA)：

ETDoAi=ti-tmin

(7)

3.2 加權K-NN算法

本文方法中，對于測量得到TDoA向量，會利用K-NN算法來將其與預期TDoA向量進行鄰域匹配，從而來進行定位。然而，傳統K-NN算法在分類應用中對k個鄰居采用相同權重[15]，這對本文飛機定位的應用不太合適。為此，本文提出一種改進的K-NN算法，稱為加權K-NN。也就是在利用鄰域網格點位置估計飛機位置時，根據測試點與網格點之間的歐氏距離的高斯函數來分配權重，得到加權坐標，這樣有利于提高定位精度。

(8)

本文對其進行了改進，利用歐氏距離對參考點坐標進行加權得到測試點坐標(加權K-NN)，表示為：

(9)

(10)

(11)

3.3 飛機定位過程

本文首先利用基于地面接收站部署結構計算得到的預期TDoA和K-NN算法來構建位置估計模型。在實際位置估計中，根據測量的TDoA和位置估計模型來估計飛機的位置，具體過程如下所述。

(1) 離線訓練階段。首先將監視區域平面預先分割成一個N×M的網格，對于每個網格的中心，計算該中心到多個接收站之間預期TDoA向量。設定一個新消息被至少3個接收站接收，即至少存在2個TDoA測量數據構成一個子集，然后組合多個數據子集來創建最終訓練集。例如，對于5個接收站，總共有16個TDoA子集。最后基于訓練集來構建加權K-NN位置估計模型。算法1詳細描述了離線訓練階段的過程。

算法1訓練階段

輸入：接收站和網格坐標。

輸出：根據TDoA訓練的估計模型。

1. Input: 網格數據(gridcoords,squaresize), 接收站位置(receiver)。

2. trainingset←[]；

%構建訓練集

3. grid←constructGrid(gridcoords,squaresize);

%構建網格

4.for?receiver combinationsdo%訓練模型

5. TDoA_training←[];

6.for?square∈griddo

7. TDoAs←compute TDoAs(receivers.coords,square);

8. TDoAtraining.add(TDoAs,gridsquare);

9.endfor

10. trainingset.add(TDoAtraining,receivercombination);

11.endfor

(2) 在線測試階段。在測試階段，接收新消息并計算TDoA測量值。通過加權K-NN位置估計模型，從空域網格中獲得與測試數據匹配的k個最近點。算法2描述了測試階段的過程。匹配過程是根據接收到的物理數據R與預設的網格數據F的歐氏距離進行匹配，表示為：

(12)

算法2測試階段

輸入：位置估計模型，接收消息信息。

輸出：位置估計值。

1. Input: 參數k, 消息(flight)。

2.loop

3.m←new position message(flight);

%接收到新消息

4.r←receivers(m);

5.ifnumber of receivers(m)>2then

6. TDoAs←calculate TDoAs(m);

%計算TDoA

7. testset←get testset(r);

%構建TDoA測試向量

8. WK-NN←run WK-NN(testset,k);

%執行加權K-NN

9. estimate←getCenter(WK-NN);

%估計位置

10.endif

11.endloop

很明顯，在空域網格中，會有多個鄰居網格與實際位置的距離大致相同。因此，k是影響精度的一個重要參數。如果設置k>1，則通過取所有k個鄰居位置坐標的加權平均值來估計飛機的最終位置。

圖4描述了一個存在4個接收站和3個鄰居網格(k=3)時的位置估計案例。其網格中心點位置信息最終的估計位置坐標如表1所示。其中根據4個接收站測量得到的TDoA向量，通過加權K-NN找到了3個最近鄰居(N1,N2,N3)，然后通過加權平均化得到估計的位置E點，其與實際位置T點最為接近。通過后續的性能評估也表明，鄰居位置平均后比任何一個鄰居更接近實際位置。

圖4 加權K-NN定位案例(k=3)

表1 案例中的位置坐標

4 實驗與結果分析

4.1 實驗設置

由于ADS-B在民航領域已經應用多年，為此有大量真實數據可用作實驗數據集。本文從OpenSky網絡獲得的真實空中交通管制數據。截至目前，OpenSky網絡中存在數千億條空中通信數據，每天捕獲超過16 000架飛機的信息。在本文分析中，使用的數據集涵蓋2018年6月至2019年6月期間，選擇了其中分布較近的5個接收器的數據，共包含超過10萬條的ADS-B信息。除了消息內容，主要提取其中的消息接收時間戳，時間戳的時鐘分辨率為50 ns。這些信息對應10萬個位置，且都能被5個接收站接收，為模型訓練和比較分析提供了足夠的TDoA數據。另外，這些數據是通過地面接收機SBS-3傳感器采集，接收器的監測半徑約400 km。

本文在11 500 m的典型飛行高度上構建了一個二維空域，該空域的面積約為150 km×220 km。將該空域進行網格化，構建均勻分布的正方形網格，其中網格數量的確定需要考慮定位效率和定位精度之間折中。另外，所有算法都在MATLAB中實現，運行在配置Intel i5處理器@2.9 GHz/8 GB RAM的PC機上。

4.2 性能評估

為了保證基線定位方法的準確性，通過與飛機ADS-B廣播信息的GPS位置數據進行比較，來評估本文方法的定位精度，并與MLAT算法進行了對比。另外，分析了鄰居數目和網格尺寸對定位精度的影響。

4.2.1網格尺寸對定位性能的影響

首先，分析網格尺寸對定位精度的影響程度。并在定位誤差，對TDoA異常數據的魯棒性和時間效率方面與MLAT進行比較。設置參數k=5，并構建50 m2到600 m2之間5種不同尺寸的網格并進行實驗，統計了定位誤差的平均值、中值、均方根誤差(RMSE)、定位所需的相對時間，結果如表2所示。

表2 不同網格尺寸下的定位誤差(k=5)

對表2所示數據的分析總結如下：

(1) 對于定位誤差。縮小網格尺寸、增加網格密度對定位準確性有積極影響。這是因為網格密度越大，算法得到的鄰居網格中心就越集中且越接近實際位置，加權后得到的位置估計也就更加準確。例如，網格尺寸從600 m2減少到300 m2時，平均定位誤差降低了約21.2%。另外，本文方法的定位精度高于MLAT，當網格尺寸為150 m2時，平均定位誤差為124.2 m，比MLAT降低了約38%。

(2) 對于TDoA異常數據。RMSE指標對離群值的敏感度較高，用來評估TDoA測量中的異常點對定位精度的影響。由于數據集是真實數據，其中存在一些測量異常值。通過比較發現，MLAT的誤差中值較低，但RMSE很高，說明其對異常點敏感。假設數據集中的平均GDOP為24，而MLAT僅考慮GDOP低于10的“好”數據，這就導致90%以上的消息不可用。而本文方法對精度稀釋更具魯棒性，在更大范圍內是有用的。

(3) 對于計算時間。計算時間是準確性和魯棒性的折中表現。當網格尺寸為600 m2時，本文方法的計算時間可與MLAT相媲美，但會隨著空域網格密度的增加而增加。然而，具體計算時間與運行設備相關。在實際應用中，機場的中央處理器通常具有很高的運算效率，即使網格尺寸很小，計算時間也不會造成問題。

由于本文算法的運行平臺為個人計算機，在300 m2網格上以小于7 ms的速度計算一個位置。對于實際應用，空域監測的更新率保持小于1 s就能滿足要求。因此在空中交通管制監視應用中，本文方法的時間復雜性幾乎不會影響監測效果，算法的運行時間不是關鍵問題?？偟膩碚f，本文發現設置網格尺寸小于150 m2時，定位精度不再明顯改善，而計算時間還是會成倍增加。因此設置網格尺寸為150 m2時，在定位精度和時間效率之間提供了一個很好的折中。

4.2.2鄰居數量對定位性能的影響

下面分析加權K-NN中的鄰居數量參數k對定位精度的影響程度，實驗結果如圖5所示?？梢钥吹?，在k小于5時，平均定位誤差會隨著k的增加而顯著改善，特別是對于600 m2大小的網格。當k大于5時，定位誤差進一步降低的空間很小，并且對于較小尺寸的網格還會更小。

圖5 不同鄰居數量k和網格尺寸下的定位精度

4.2.3信號噪聲對定位性能的影響

與MLAT相比，本文方法的一個主要優點是對噪聲的魯棒性。為了分析TDoA測量中噪聲信號的影響，以收集的真實數據為基礎進行了模擬測試。在100 km×100 km的空域上構建網格，地面上隨機分布5個接收器。對每個網格中心，模擬其發送信號到各個接收站來計算TDoA，并在TDoA中添加表示時間測量誤差的高斯白噪聲Zi～N(0,σ)，其中：0為均值；σ為TDoA噪聲的標準差，單位為s。在不同等級的σ下進行實驗，并計算定位誤差的中值，結果如圖6所示。

圖6 不同噪聲水平下的定位誤差中值

可以看到，MLAT算法在沒有或很少TDoA噪聲的情況下性能很好。然而，在噪聲水平較高時，MLAT的性能急劇下降。與之相比，本文方法對噪聲的魯棒性要好很多，在噪聲水平增加時沒有明顯惡化。當噪聲接近σ=10-7s時，MLAT的定位誤差中值達到150 m，超過所有網格尺寸下的本文方法。這是因為MLAT僅在GDOP極低時才表現良好，而本文方法不受此問題的影響。實驗發現在MLAT中，只有GDOP小于5的信號才能提供較低的平均定位誤差。不幸的是，這樣低的精度稀釋只存在于很小部分的監視區域。所以在存在噪聲情況下，本文方法還具有擴展監視區域的作用。

另外，MLAT算法需要非常準確的時鐘同步，并且受到接收器位置幾何結構的嚴重影響。相比之下，本文方法使用低成本的硬件(如SBS-3接收器)也能提供高質量的有效定位。在接收站部署條件有限的情況下，這個特性非常有用。

5 結 語

本文在MLAT的基礎上，提出一種逆向匹配的思路來進行飛機定位。通過對空域進行預先網格化，構建預期TDoA數據集，然后利用一種加權K-NN算法來進行鄰域匹配，獲得最終的飛機位置估計。通過與MLAT方法進行比較，結果表明本文方法明顯提高了定位精度，且在存在TDoA噪聲情況下同樣能實現良好性能。另外，本文方法對地面接收站部署的幾何結構要求不高，可以擴展監測覆蓋率。