基于改進人工免疫算法的TDOA定位估計

宋越明， 于宏毅

（解放軍信息工程大學，河南 鄭州 450002）

0 引言

TDOA 定位技術又稱為雙曲線相交法，通過測量信號源到達多個接收機的距離差，進而求解雙曲線方程組就可以得到信號源的估計位置。但求解非線性的雙曲線方程組是很困難的。針對此問題已提出很多算法。文獻[1]中介紹了Fang、SX、SI、Taylor級數展開法、Chan算法等比較常用的求解算法。但是它們都各自存在一些缺點，比如無法利用冗余測量數據提高測量精度，無法求得最優解，對初始解要求較高，或者最優解在測量噪聲較大的情況下性能惡化比較嚴重。

上述定位算法的一般都假設到達時間差的測量誤差服從高斯分布，且似然函數的解析表達式也是可以得到的，因此可以基于最大似然法求解上述TDOA定位問題。但是由于此時似然函數比較復雜，要對其求解必須解決復雜的非線性函數優化問題。

人工免疫算法是一種受免疫學啟發，模擬免疫學功能、原理和模型來解決復雜問題的自適應系統，應用于非線性函數優化問題時具有適用性強，具有學習記憶功能，收斂性能較好等特點。本文分析了TDOA定位問題中的非線性函數優化問題，并有針對性的對人工免疫算法進行了改進，將人工免疫算法應用于TDOA定位估計問題。仿真表明改進的人工免疫算法應用于TDOA定位估計問題，性能穩定，可以保證全局收斂，且收斂速度較快，定位精度優于Chan算法。

1 TDOA雙曲線定位模型

為了敘述簡便，本文僅考慮二維平面情況，但文中的算法很容易推廣到三維情況。以如下頁圖1所示定位系統為例，共有M（本文只討論M＞3，即測量值有冗余的情況）個觀測站分布在平面上，觀測站i坐標為(xi, yi)，信號源坐標為(x,y)。設觀測站i到信號源的距離為ri，信號源到觀測站i和觀測站1之間的距離差為r i1。根據基站和移動臺之間的關系可以得到：

其中di1(i= 2,3…M- 1)，為到達時間差測量值，c為無線電傳播速度。可認為ni1(i= 2,3…M- 1)是獨立同分布，且均值為零，方差為σ的高斯隨機變量。所以有：

記：

其中R1為M-1維列向量。綜合式（1）、（2）得：

因為ΔR中的元素Δri均為獨立同分布，且均值為ri-r1方差為c2σ2的高斯隨機變量。因此似然函數為：

因此移動臺位置坐標的最大似然估計為：

由于式（4）中包含很復雜的非線性函數，使用傳統的求導方法求最大似然解非常困難。如果以式（5）為目標函數，搜索峰值對應坐標也可以求得最大似然估計值，但如果直接搜索會帶來巨大的計算量。人工免疫算法作為一種全局優化算法，對尋優函數基本沒有限制，也不要求參數的連續行和可導性，很適合用于上述非線性函數優化問題的求解。

圖1 定位系統和信號源拓撲示意

2 基于改進人工免疫算法的TDOA定位

人工免疫算法借鑒了生物免疫系統的免疫原理，避免了遺傳算法中的交叉操作引起的模式干擾，同時保證了抗體的多樣性。文獻[2]最早實際應用人工免疫算法，在后來的研究中人工免疫算法逐步發展，被廣泛應用于數據挖掘、計算機安全、模式識別、優化、自動控制等領域，出現了幾種不同類型的人工免疫算法[3],在國內也開始有相關研究將人工免疫算法應用于解決實際問題[4-5]。本文針對 TDOA估計中的非線性函數優化問題提出了一種改進的人工免疫算法，其主要流程如圖2所示。

圖2 改進的人工免疫算法流程

步驟1 初始化。隨機產生Np個抗體組成的初始抗體種群Ap，每個抗體代表信號源位置的一個解(xj,yj),坐標值在信號源可能存在區域內隨機取值。傳統的人工免疫算法和遺傳算法一樣采取二進制編碼，只需對0或1以一定概率取反就可以完成變異操作。但由于計算親和度時必須使用未編碼的數值，這就造成算法迭代中需要不斷的進行編碼和解碼的過程，加大了算法的計算量，同時有限的編碼長度也限制了最優解的精度。這里采取浮點數編碼，直接采用浮點數表示抗體矢量的每個分量，避免了編解碼過程。與之對應的抗體變異過程中也需要做出相應的改變。

步驟2 計算每個抗體的親和度。這里親和度根據式（5）的倒數計算，即：步驟3 選擇。對所有抗體根據其親和度從大到小排列，找出親和度最大的Na個抗體組成集合Aa。

步驟4 根據收斂條件判斷算法是否已經收斂，如果已經收斂，親和度最大的抗體對應的坐標就是所求位置坐標；如果未收斂則繼續。

步驟 5 克隆。克隆過程以一定的概率復制集合Aa中的抗體。為了在保持抗體數量不變的情況下盡量保留親和度較高的抗體，這里采用輪盤賭策略對抗體進行克隆。首先計算克隆概率：

其中fi為抗體i的親和度，wi為克隆概率。然后根據下式計算累積分布：

隨機產生Na個在[0,1]之間均勻分布的數，若該數位于區間[ci-1,ci]，則復制抗體ai作為克隆抗體集合Ac中的抗體。通過以上的克隆策略，親和度較大的抗體被克隆的概率較大，可以盡量保留親和度高的抗體，防止退化現象，保證算法的收斂性。

步驟6 超變異（Hyper-mutation）。超變異過程保證了抗體的多樣性，保證算法向最優解收斂。由于采用了浮點數編碼，這里采用高斯變異，變異抗體由克隆抗體得到。假設第i個克隆抗體中的橫坐標為，對應變異抗體中的橫坐標為，則變異根據下式進行：

其中β和r為可控參數，與搜索區域大小和變異的程度有關，可以影響算法收斂的速度，n為均值為零，方差為1的高斯變量。為克隆抗體的變異率，針對求最大值問題，其計算公式如下：

其中fmax為當前最優解對應抗體的親和度。同理可得到變異抗體中的縱坐標。變異后的抗體組成變異抗體集合Am。上述變異過程中親和度高的抗體其變異率較低，可以避免變異抗體出現退化現象。

步驟7 調整免疫網絡。重新計算變異抗體集合中所有抗體的親和度，和Aa集合中的抗體一起重新進行選擇，找出最優的Na個抗體進入下一代抗體集合。同時，淘汰當前親和度最低的d個抗體，為了保持抗體數量和多樣性，重新初始化含d個新抗體的集合 ，并將它加入下一代抗體集合。在這個過程中優勢抗體被保留，退化的抗體被淘汰。

步驟8 返回步驟2繼續迭代直到算法收斂。

上述改進的人工免疫算法具有記憶學習功能，抗體的進化和變異過程可以保證優勢抗體得到保留，避免退化現象，且每次迭代中最優抗體都能進入下一次迭代，可以確保算法的全局收斂[6]。

3 仿真結果及分析

為了驗證上述改進算法的性能，根據如下的仿真環境進行了計算機仿真。考慮蜂窩網系統的基站分布，其位置坐標分別為(0,0)，(-5000,3000)，(-5000,-3000), (0,-6000)，信號源位置為(1000，2500)，cσ取值根據實際應用環境設定為30～150 m（例如在GSM系統中，到達時間差測量可以達到的精度約135 m[7]，在第三代cdma網絡中到達時間差的測量精度約78 m）。為了加快收斂速度，將Chan算法的估計結果作為初始解，初始抗體在初始解附近隨機取值。仿真中Np= 30,Na= 24,d= 6。搜索參數r= 500,β= 0.05；收斂條件設定為最優解在連續 10次迭代后保持不變，最大迭代次數為 100。較嚴格的收斂條件有效的避免了算法過早收斂于局部最值點。在cσ的每個取值下進行 500次獨立試驗，分別采用Chan算法[8]和本文提出的改進的人工免疫算法進行定位估計。分別取實驗結果的均值與真實值的誤差和均方根誤差作為評價指標。其中均方根誤差由下式確定：

其中N為試驗次數。兩種算法的估計均值和和真實值之間的誤差如表1所示，單位為m。

表1 兩種算法估計均值與真實值的誤差

在不同的到達時間差測量噪聲下，兩種算法定位估計結果的均方根誤差的比較如圖3所示。由表1和圖3可以看出，在測量噪聲cσ較小的情況下，兩種算法的性能基本一致。隨著噪聲的增大，Chan算法的性能迅速惡化，其估計結果的均值和真實值的偏差迅速增大，而改進的人工免疫算法給出的估計位置均值始終較接近真實位置；同時改進的人工免疫算法估計結果的均方根誤差也小于 Chan算法，性能則明顯優于前者。在cσ為120時，Chan算法估計結果橫坐標和縱坐標均值的誤差已達-72.2和92.9，而改進人工免疫算法對應的誤差僅為 4和-5.6。后者的均方根誤差也比 Chan算法小120左右。

圖3 兩種算法的均方根誤差比較

這是由于Chan算法在進行第一次最小二乘法中計算加權系數時忽略了噪聲的二次項，導致該算法只能在噪聲較小的情況下逼近最優解；隨著噪聲的增大，噪聲的二次項的影響也越來越大，無法忽略，造成算法性能下降。而改進的人工免疫算法直接搜索最大似然解，不存在上述現象，性能較Chan算法有很大改善。

4 結語

本文利用最大似然法求解TDOA定位問題，并提出了一種改進的人工免疫算法解決由此產生的非線性優化問題，采用有指導的進化策略，在編碼方式、克隆策略、變異率的設置等方面進行了改進，用于解決TDOA定位估計問題，定位精度較好，性能穩定，在較小的種群規模下仍能較快收斂到全局最優解，與Chan算法相比在噪聲較大的情況下更具優勢。

[1] 范志平，鄧平，劉林. 蜂窩網無線定位[M].北京:電子工業出版社，2002:62-69.

[2] Bersini H, Varela F J. Hints for Adaptive Problem Solving Gleaned from Immune Networks[C]. Dortmod, German: Proceedings of the 1st workshop on Parallel Problem Solving from Nature,1990:343-354.

[3] Castro L N de, Fernando J. Von Zuben. Recent Developments in Biologically Inspired Computing[M]. Hershey, USA: Idear Group Inc., 2004:270-300.

[4] 陳艷玲, 蔡祥寶. 人工免疫算法在光交換網絡分組調度中的應用[J].通信技術,2007,40(12):272-273.

[5] 孫名松,鄭春光,魏欣南.一種基于人工免疫的垃圾郵件過濾算法[J].通信技術,2009,42(02):85-86.

[6] 湯放奇，李茂軍，羅安.人工免疫算法的全局收斂性分析[J].長沙電力學院學報:自然科學版,2004,19(03):1-4.

[7] Silventoinen M I, Rantalainen T. Mobile Station Emergency Locating in GSM[C]. India: IEEE International Conference on Personal Wireless Communications,1996:232-238.

[8] Chan Y T, Ho K C. A Simple and Efficient Estimator for Hyperbolic Location[J].IEEE Trans. on Signal Processing,1994(42):1905-1915.