基于改進(jìn)人工免疫算法的TDOA定位估計(jì)

宋越明， 于宏毅

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

0 引言

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

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

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

1 TDOA雙曲線定位模型

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

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

記：

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

因?yàn)棣中的元素Δri均為獨(dú)立同分布，且均值為ri-r1方差為c2σ2的高斯隨機(jī)變量。因此似然函數(shù)為：

因此移動(dòng)臺(tái)位置坐標(biāo)的最大似然估計(jì)為：

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

圖1 定位系統(tǒng)和信號(hào)源拓?fù)涫疽?/p>

2 基于改進(jìn)人工免疫算法的TDOA定位

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

圖2 改進(jìn)的人工免疫算法流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 兩種算法估計(jì)均值與真實(shí)值的誤差

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

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

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

4 結(jié)語

本文利用最大似然法求解TDOA定位問題，并提出了一種改進(jìn)的人工免疫算法解決由此產(chǎn)生的非線性優(yōu)化問題，采用有指導(dǎo)的進(jìn)化策略，在編碼方式、克隆策略、變異率的設(shè)置等方面進(jìn)行了改進(jìn)，用于解決TDOA定位估計(jì)問題，定位精度較好，性能穩(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)絡(luò)分組調(diào)度中的應(yīng)用[J].通信技術(shù),2007,40(12):272-273.

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

[6] 湯放奇，李茂軍，羅安.人工免疫算法的全局收斂性分析[J].長沙電力學(xué)院學(xué)報(bào):自然科學(xué)版,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.