基于改進型遺傳蟻群算法的TDOA多點定位研究*

唐菁敏，周 旋，張 偉，王朝陽，王紅彬

（昆明理工大學 信息工程與自動化學院，云南 昆明 650500）

0 引 言

國內外航空運輸業在近幾十年來發展十分迅速。這些年，航空量大大增加，隨之而來的是飛機數量的巨增，特別是大型機場，表現尤為明顯。多點定位系統是通過移動物應答使得多個基站獲取定位的系統。該系統通過基站獲取飛機的各種應答信號，同時也可以接收ADS-B的信號，根據信號到達各個基站產生的時間差確定飛機的位置[1]。從MLAT（多點定位技術）系統優勢性上分析，其具有覆蓋面廣、定位高精度、受環境影響小和成本低等一系列優點。將其和場面雷達相互比較，現今的場面監視選擇MLAT系統會更加合適，也能夠滿足現在場面監視的各項不同需求[2-3]。國外較早便開始多點定位技術及算法的研究，因而其應用的多點定位算法類型較為豐富，但多數是以TDOA（到達時間差）與TOA（到達時間）為基礎，以TDOA為基礎的算法占比較大，以TOA為基礎的算法主要包括Bancroft算法和最小二乘法，而SX和SI算法、Taylor算法、Friedlander算法、Fang算法和Chan算法等都是經典的TDOA算法。我國對MLAT系統的研究較晚，民航第二研究所在站點覆蓋與精度分析技術上成功實現了使用幾何精度衰減因子同地理信息系統相結合的方法，研制了ADS-B全兼容多點定位原理樣機系統，實現了民航應用領域的高精度時差多點定位系統，但算法研究上并沒有實現技術創新，只是針對傳統經典算法開展的研究[4-6]。

多點定位系統中最常用的一種方法是利用迭代法對代數中存在的非線性等式進行求解，以泰勒級數展開法為代表。此方法需要初始猜測值作為保證，對測量誤差求得其局部線性最小二乘解，從而求得更精確的估計位置。該方法的優劣很大程度上取決于初始參考點選取的優劣。初始參考點的準確與否會對算法收斂性產生極大影響，且迭代運算也會因之出現局部極小化問題，計算量大且無法保證算法收斂性[7-8]。針對上述情況，本文的改進思路是提出改進型遺傳蟻群算法搜索空間最優解，并作為初始參考點對泰勒級數展開法提供輔助。首先利用正反饋機制存在的優點和改進型遺傳蟻群算法表現的快速全局收斂性在空間搜尋最優解，將最優解賦值給初始參考點后，以此為基礎運用泰勒級數展開法對定位坐標進行求解，如此對機場場面移動目標實現精確定位。該方法并不受迭代法無初始猜測值的限制，使得遺傳算法與蟻群算法很好地融合，不僅使得蟻群算法和遺傳算法在尋優過程中良好體現了各自特點，而且避免了尋優效率不高的遺傳算法和尋優開始階段信息素不足的蟻群算法存在的缺陷，擁有較好的求解效率和時間效率。該改進算法被稱為基于改進型遺傳蟻群算法的泰勒級數展開多點定位算法，改進思路如圖1所示。

圖1 基于改進型遺傳蟻群算法的泰勒級數展開多點定位算法思路

此外，在TDOA多點定位算法研究中，通常假設Chan算法中定位目標距離各個基站很遠，有Ri≈Ri0，Ri表示從移動目標到基站i的距離，Ri0表示定位目標和基站之間的實際距離，那么Q ≈φ，Q表示TDOA測量噪聲的協方差矩陣，φ表示誤差矢量的協方差矩陣。分別通過第一次和第二次加權最小二乘法（WLS）求解得出定位目標的位置坐標，則一般認為Chan算法不需要初始猜測值。但是，Chan算法中的另一種情況是定位目標距離各個基站較近時，Ri≈Ri0則不成立。此情況下，需要通過假設定位目標距離各個基站很遠，估算一個定位目標的大概位置，再通過假設定位目標距離基站較遠時的第一次WLS表達式，求解初始解估計矩陣B，隨后將矩陣B代入分別進行第一次和第二次WLS求解，最終得出定位目標精確位置。所以，研究Chan算法可以看出，當定位目標距離各個基站較近時，第一次估算也需要初始猜測值，才能求解初始解估計矩陣B[9-10]。

本文的改進思路二是針對Chan算法中定位目標距離各個基站較近時的情況，提出改進型遺傳蟻群算法搜索空間最優解，并對Chan算法提供輔助。首先利用正反饋機制存在的優點和改進型遺傳蟻群算法表現的快速全局收斂性，在空間搜尋最優解；將最優解賦值作為初始猜測值，求解初始解估計矩陣B，之后以此為基礎運用Chan算法進行第一次和第二次WLS求解。如此一來，對于機場場面移動目標，就能夠實現精確的定位。該方法并不受Chan算法中定位目標距離各個基站較近時需要假設得到定位目標大概位置的限制，同時使得遺傳算法與蟻群算法很好地融合，不僅使得蟻群算法和遺傳算法在尋優過程中良好地體現了各自的特點，而且避免了尋優效率不高的遺傳算法和尋優開始階段信息素不足的蟻群算法存在的缺陷，擁有較好的求解效率和時間效率。該改進算法被稱為基于改進型遺傳蟻群算法的Chan多點定位算法，改進思路如圖2所示。

圖2 基于改進型遺傳蟻群算法的Chan多點定位算法思路

1 多點定位數學模型

以TDOA為基礎的雙曲面定位算法，建立如下數學模型。假定目標同地面第i個接收站距離用Ri表示，則距離計算公式為：

其中，[Xi,Yi,Zi]表示地面第i個接收站的三維坐標，[x,y,z]表示目標空間位置。

定位目標與同地面第i個接收站距離用Ri表示，定位目標同地面第1個接收站（即主站）距離R1之差Ri,1計算如下：

其中，Ti,1表示定位目標至地面第i個接收站的時間同到達地面第1個接收站的時間差，c表示電波傳播速度。

于是，有：

其中Xi,1=Xi-X1，Yi,1=Yi-Y1，Zi,1=Zi-Z1。所有 TDOA定位算法都時基于式（1）～式（5）進行的計算。二維空間坐標只需去除z軸坐標，即可得到類似表達式。

2 算法描述

2.1 改進型遺傳蟻群算法

2.1.1 確定種群中每一個體取值范圍

為了讓遺傳算法有更快的運算效率和更高的定位精度，本文首先確定遺傳算法中種群的每一個體的取值范圍。其中，每一個體即表示目標飛機初始猜測位置。設定代碼如下：

FieldDR=[center-searchR;center+searchR]

其中FieldDR表示種群中每個個體的取值范圍，center表示目標位置搜索中心，searchR表示搜索半徑。

2.1.2 初始種群和適應度函數選取

本文采用的遺傳算法需創建實值原始種群Chrom，具體代碼如下：

Chrom=crtrp(cNum,FieldDR)

其中crtrp函數用來創建實值原始種群，cNum表示種群個體數。本文設定cNum值為50，即種群個體數為50。

就初始種群而言，在特定的機場場面坐標范圍內，其初始猜測位置是隨機產生的。為了對優化時種群個體和最優解接近的程度作出評價，本文采用ranking函數作為適應度函數。此函數是基于排序的適應度分配，即從最小化方向對個體進行排序，具體代碼如下：

FitnV=ranking(E)

其中E表示種群初始能量值，是包含與基站坐標Locs、基站測量值Ms和實值原始種群Chrom有關的量。

2.1.3 遺傳算子的選擇

選擇算子。本文選擇“隨機遍歷抽樣”方法，等距離選擇優良個體向下一代群體遺傳。具體代碼如下：

SelCh=select('sus',Chrom,FitnV,GGAP)

其中select表示從種群中選擇個體的函數，sus表示隨機遍歷抽樣方法，GGAP表示進化比例，即為交叉概率Pc，本文設定值為0.9。

交叉算子。為了子代能夠獲取較優解，在其父代中選擇兩個最優個體讓其搭配成對，在兩者間通過交叉概率選定部分基因并兩兩交換，從而獲得新的個體。

變異算子。在種群中選取遺傳算法育種器的變異算子mutbga，這樣種群就會更加多樣，局部搜索能力也會得到很好的提升。

2.1.4 設置信息素的初始值

遺傳算法具有快速全局收斂性，所以據此可得到和最優解相近的一個定位坐標。蟻群算法就是以該坐標作為信息素初始值的。對銜接點初始時刻而言，信息素有如下生成規則：

其中，τc為設置在蟻群算法路徑上的信息素常量；τG為遺傳算法搜索結果通過轉換得來的信息素值。

2.1.5 路徑選擇

蟻群算法具有的正反饋機制是最明顯的優勢。根據之前經過的螞蟻殘留的信息素強度作出下一個節點的選擇，狀態轉移概率函數為：

其中：Pijk(t)為在t時刻第k個螞蟻由i節點向j節點轉移的概率。τij為ij路徑上殘留的信息素強度。ηij為螞蟻由i節點向j節點轉移的期望度。α代表信息啟發式因子，β代表期望啟發式因子，allowedk代表第k個螞蟻下一步能夠選擇的節點。

2.1.6 信息素更新

假設t時刻螞蟻的一次循環已經完成，那t+1時刻信息素的更新方式為：

其中，ρ為信息素的揮發系數，且ρ∈(0,1)；Δτij代表ij路徑上信息素的增量變化；第k個螞蟻在ij路徑上走過的距離長度用Lk表示，殘留的信息素則用Δτijk表示，Q0(x0,y0)代表信息素強度。

本文通過改進的節點編碼方式減少了傳統蟻群算法的求解空間。首先蟻群算法是用來解決旅行商（TSP）等離散問題的，而本文所求定位坐標信息是連續的，故而如何將求解連續坐標問題轉化為蟻群算法解決的離散問題，這是改進算法的一個重點。在實際求解過程中，遺傳蟻群算法在較大的求解空間中尋優，是費時且沒有效果的，基本不可能遍歷所有路線，優化結果全靠遺傳算法保證，蟻群算法基本不能發揮作用。通過改進其編碼方式，遍歷節點數大大減少，提高了搜索效率，蟻群算法可以真正遍歷，甚至多次經過某路線，找到最優路線的概率大大提高。本文程序中設定遺傳算法迭代次數為10次，蟻群算法迭代次數為3次。

本文的改進算法在程序設計首先利用遺傳算法搜索求解得到一個初始估計值，設為P0(x0,y0,z0)。可知，遺傳算法搜索結果精度可達小數點后一位。隨后，將初始估計值P0(x0,y0,z0)代入蟻群算法，進一步優化各坐標值小數點后第2位開始的3位小數，此處即將得到的初始位置估計值坐標進行拆分，運用SplitT函數對位置坐標拆分，具體程序代碼如下：

function num=SplitT(T)

T=abs(10*T-fix(10*T))+0.0001;

strT1=num2str(T(1),'%0.4f');

strT2=num2str(T(2),'%0.4f');

strT3=num2str(T(3),'%0.4f');

num=[str2num(strT1(3)),str2num(strT1(4)),str2 num(strT1(5)),str2num(strT2(3)),str2num(strT2(4)),st r2num(strT2(5)),str2num(strT3(3)),str2num(strT3(4)),str2num(strT3(5))];

end

其中T即表示P0(x0,y0,z0)，abs為絕對值函數，fix函數代表取整數位。

隨后依據遺傳算法的結果得到的拆分數據即為蟻群算法中的最優路徑。以此初始化信息素，并增加該條路徑上的信息素num，具體程序代碼如下：

num=[0,SplitT(Ti)];num=num+1;

更新螞蟻軌跡，合并得到新位置坐標，具體程序代碼如下：

function T=CombT(Ti,num )

Ti2=fix(10*abs(Ti))/10;

T(1)=Ti2(1)+0.01*num(1)+0.001*num(2)+0.0001*num(3);

T(2)=Ti2(2)+0.01*num(4)+0.001*num(5)+0.0001*num(6);

T(3)=Ti2(3)+0.01*num(7)+0.001*num(8)+0.0001*num(9);

T=T.*sign(Ti);

end

其中fix函數代表取整數位。

最后，找出最佳螞蟻，提高其軌跡上的信息素，記錄最佳估計值，并用CombT函數得到新的初始目標P1(x1,y1,z1)，將得到數值作為初始猜測值代入泰勒算法和Chan算法求解。

2.2 基于改進型遺傳蟻群算法的泰勒級數展開多點定位算法

泰勒算法作為遞歸算法需選定一個初始估計值。為了保證其運算速度和收斂性，應當盡量選擇和實際位置較為接近的初始值。所以，以改進型遺傳蟻群算法已經搜索到的P0(x0,y0)作為初始位置，對二維空間有：

在(x0,y0)處進行泰勒展開：

ψ為誤差矢量矩陣，忽略二階以上分量，有：

對式（12）采用加權最小二乘算法（WLS），可以得到δ的最小二乘估計：

其中，Q表示TDOA測量值的協方差矩陣。在第二次遞歸計算中，令x'=x0+Δx，y'=y0+Δy，重復計算多次，直至Δx和Δy達到足夠小的水平且滿那么得到的估計值可以視為飛機的估計位置。

2.3 基于改進型遺傳蟻群算法的Chan多點定位算法

Chan算法中定位目標距離各個基站較遠時，可以按正常算法流程進行2次WLS估計計算。但是，當定位目標距離各個基站較近時，可以通過改進型遺傳蟻群算法搜索空間最優解，并對Chan算法提供輔助。首先利用正反饋機制存在的優點和改進型遺傳蟻群算法表現的快速全局收斂性，在空間搜尋最優解，將最優解賦值作為初始猜測值，再求解初始解估計矩陣B，之后以此為基礎運用Chan算法進行第一次和第二次WLS求解。就場面監控系統而言，考慮到大多數目標運動都是在二維平面進行，所以可以單純從二維上考量目標定位問題，具體求解步驟如下。

先將式（2）展開可得：

誤差矢量為：

其中Q表示TDOA測量噪聲的協方差矩陣。

運用加權最小二乘法得到第一次WLS為：

當定位目標和各個基站的距離較近時，不可以作出Ri≈Ri0的判定。那么，通過改進型遺傳蟻群算法得到一個初始解P0(x0,y0)，然后進行初始解估計矩陣B的求解，再將其代入得到第一次WLS的值。

第二次WLS。鑒于第一次WLS沒有考慮R1和x、y之間的關系，此次WLS中應當考慮Ri和x、y之間的關系，讓定位結果能實現更高的精確度。令P11=x0+e1，P12=y0+e2，P13=R10+e3， 其 中 e1、e2、e3表示P1的估計誤差，則：0

式（28）中，x0、y0可由第一次WLS得到的P1近似估計，則ψ'的協方差矩陣φ'為：

同理，根據WLS可得：

3 仿真分析

本文假設仿真采用星型布站設計，設置在15 km×15 km的矩形區域環境內進行，類似于機場場面監視的參數。接收站點基站個數分別為4個、5個、6個和7個，分布在半徑為12 km的圓上，具體分布如圖3、圖4、圖5和圖6所示。

圖3 四個基站分布

圖4 五個基站分布

圖5 六個基站分布

圖6 七個基站分布

本文仿真考慮了4、5、6、7個基站情況下的定位解均方誤差。設定中心1號基站坐標為（0，0），按圖6所示基站進行分布，故其余各站為相對坐標，各基站坐標值如表1所示。

表1 基站數量和基站坐標

下面針對某一選定區域對其目標位置誤差予以追蹤，從而驗證算法性能。接收站點和圖3、圖4、圖5和圖6的分布一致。算法性能的衡量指標為定位均方誤差（即MSE），可以表征定位誤差具有的穩定性。

3.1 仿真實驗1

TDOA的測量誤差可看成是均值為0且呈理想的高斯分布，標準差分別是5 m、10 m、15 m、20 m、25 m、30 m、35 m、40 m、45 m、50 m、55 m、60 m、65 m、70 m、75 m、80 m、85 m、90 m、100 m。當參與定位的基站為4個、5個、6個以及7個時，選取圖3、圖4、圖5和圖6中所述的地面接收基站來定位目標。圓心設在1號中心基站，半徑則設置為7 000 m。在該圓內隨機選取104個目標位置，用MSE來評估實驗結果。設置遺傳算法中參數種群數M=50，交叉概率Pc=0.9，實值種群的變異算子默認mutbga，通過仿真得出在不同基站數目下，泰勒級數展開法、Chan算法、基于改進型遺傳蟻群算法的泰勒級數展開多點定位算法、基于改進型遺傳蟻群算法的Chan多點定位算法的TDOA定位誤差和MSE之間的關系仿真結果，依次如圖7、圖8、圖9和圖10所示。

圖8 Chan算法仿真結果

圖9 改進型泰勒級數展開多點定位

圖7 Taylor算法仿真結果

圖10 改進型遺傳蟻群算法的Chan多點定位

從仿真圖中統計得到的實驗結果數據可以總結得出，泰勒級數展開法、Chan算法、基于改進型遺傳蟻群算法的泰勒級數展開多點定位算法、基于改進型遺傳蟻群算法的Chan多點定位算法四種算法，在同等定位誤差條件下，隨著定位基站數目的增加，定位均方誤差都會逐漸降低，同時伴隨著定位誤差的不斷增加，其定位均方誤差也不斷增加，即四種算法的MSE隨著TDOA定位誤差從5 m增加到100 m的過程中不斷增大，同時定位精度會隨著基站個數的增加而提高。

3.2 仿真實驗2

為了對四種算法在定位性能方面進行驗證，在圓心設在1號中心基站的半徑為7 000 m的圓內，隨機抽選任意點設為初始猜測位置，對泰勒算法、Chan算法、改進型遺傳蟻群算法的泰勒級數展開多點定位算法和基于改進型遺傳蟻群算法的Chan多點定位算法，在基站個數不同、TDOA定位誤差不同的情況下進行比較仿真。即TDOA的測量誤差可看成是均值為0且呈理想的高斯分布，標準差則是5 m、10 m、15 m、20 m、25 m、30 m、35 m、40 m、45 m、50 m、55 m、60 m、65 m、70 m、75 m、80 m、85 m、90 m、100 m。圓心設在1號中心基站，半徑則設置為7 000 m，在該圓內隨機選取104個目標位置，用MSE來評估實驗結果。用Improved圖標表示改進型遺傳蟻群算法的泰勒級數展開多點定位算法走勢，用Improved_Chan圖標表示改進型遺傳蟻群算法的Chan多點定位算法走勢，地面接收站按照圖3、圖4、圖5和圖6分布，得到的仿真結果如圖11、圖12、圖13和圖14所示。

圖11 四個地面基站四種算法對比

圖12 五個地面基站四種算法對比

圖13 六個地面基站四種算法對比

圖14 七個地面基站四種算法對比

從仿真圖中統計得到的實驗結果數據可以總結出，在同等定位誤差和相同定位基站數目條件下，改進型遺傳蟻群算法的泰勒級數展開多點定位算法定位均方差更小，定位性能優于其他三種算法，且四種算法的定位均方差都隨著TDOA定位誤差的增加而不斷增加。

3.3 運算效率

為了便于統計，驗證基于改進型遺傳蟻群算法的泰勒級數展開多點定位算法和基于改進型遺傳蟻群算法的Chan多點定位算法的運算效率，在仿真實驗2的條件下對四種算法迭代1 000次的時間作了統計，具體如表2所示。

表2 算法運行時間比較/s

對改進型遺傳蟻群算法的泰勒級數展開多點定位算法、改進型遺傳蟻群算法的Chan多點定位算法、Chan算法和泰勒算法四種算法的仿真試驗2和運算時間統計表2分析可以得到：以TDOA的測量誤差可視為呈理想的高斯分布為前提，在同樣的仿真條件下，Chan算法和泰勒算法都有較高的定位精度，但泰勒算法在選擇初值時對真實值范圍太過依賴，局限性大；改進后的兩種算法均提高了定位精度，尤其是隨著基站數的增加，改進后的兩種算法的定位精度優勢更加明顯。改進型遺傳蟻群算法的泰勒級數展開多點定位算法定位精度高于改進型遺傳蟻群算法的Chan多點定位算法。

相對Chan算法來說，改進后的兩種算法因為提高了算法的復雜度，故而有著稍低于Chan算法的運算效率。但是，和泰勒算法相比，改進算法平均都有近1倍的提升，改進型遺傳蟻群算法的泰勒級數展開多點定位算法運行效率要低于改進型遺傳蟻群算法的Chan多點定位算法。

另外，基站個數越多，四種算法自身的定位精度也會越高；TDOA測量值定位誤差越大，其精度會越小。同時，相較于泰勒算法、Chan算法來說，改進后的兩種算法有著更高的定位精準度，算法也趨于更加穩定。運算效率相較于單一的泰勒算法來說，也處于較高水平。總體而言，改進后的兩種算法雖然增加了算法的復雜度和算法運行時間，但獲取了更優的定位精度，性能總體較優，具有一定的實際應用意義。

4 結 語

民用航空交通運輸業伴隨著中國綜合國力的日益增長，發展勢頭迅猛。因此，更好地管理空中交通變得越來越重要，這激增了空中安全壓力。為了能夠提高航空安全水平，保障空中的絕對安全，需要不斷加大對新一代監視技術的研發投入，而多點定位系統是其中重要的一項技術，具有定位精度較高、安裝方便等特點，被廣泛應用于世界各國。本文通過探討兩種傳統泰勒和chan算法的優缺點，相應提出了基于改進型遺傳蟻群算法的泰勒級數展開多點定位算法和基于改進型遺傳蟻群算法的Chan多點定位算法，避免了兩種傳統經典算法存在的局限性。在假設確定的相同仿真條件下，對兩種改進算法從定位精度和算法運行效率兩個方面進行仿真實驗，探討了兩種改進算法具有的優缺點，驗證了改進算法的有效性和可靠性，提高了定位精度。但是，本文未考慮其他因素影響，在今后多點定位算法研究中還需綜合考慮。