宋越明， 于宏毅

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

0 引言

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

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

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

1 TDOA雙曲線定位模型

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

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

記：

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

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

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

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

圖1 定位系統(tǒng)和信號源拓撲示意

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真結(jié)果及分析

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

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

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

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

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

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

4 結(jié)語

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

[1] 范志平，鄧平，劉林. 蜂窩網(wǎng)無線定位[M].北京:電子工業(yè)出版社，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] 陳艷玲, 蔡祥寶. 人工免疫算法在光交換網(wǎng)絡分組調(diào)度中的應用[J].通信技術(shù),2007,40(12):272-273.

[5] 孫名松,鄭春光,魏欣南.一種基于人工免疫的垃圾郵件過濾算法[J].通信技術(shù),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.