基于改進(jìn)鳥群優(yōu)化算法的TDOA定位算法

打開文本圖片集

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A

TDOA Location Algorithm Based on Improved Bird Swarm Optimization Algorithm

YANG Man,REN Zhi-guo，XUE Pan-pan (School of Information Engineering，Lanzhou City University，Lanzhou 73oo7o，China)

Abstract:Aiming at the problems such as the complex solution of nonlinear equations encountered in the positioning of time difference of arrival, this paper proposes a TDOA positioning algorithm based on the improved bird swarm optimization algorithm. Firstly，the effects of different chaotic mappings were compared and analyzed. It was selected to use the Chebyshev chaotic mapping for the initialization of the bird flock to further improve the initial solution effect and enhance the population diversity. Secondly，set the acceleration coeficient in the foraging behavior of the bird flock as a nonlinear dynamic adjustment factor to balance the global search and local development capabilities of the population and avoid the algorithm falling into local optimum. Finally，based on different environmental parameters， the RMSE for positioning and solving by different intelligent algorithms was simulated and analyzed. The experimental results show that， compared with the traditional particle swarm， genetic algorithm and bird swarm optimization algorithm，the improved bird swarm optimization algorithm has a lower RMSE in solving the optimal solution of the TDOA nonlinear equation system.

Key words:time difference of arrival; bird swarm optimization； chaotic mapping；intelligent optimization algorithm

0 引言

20世紀(jì)80年代以來，智能交通系統(tǒng)的快速發(fā)展和蜂窩無線通信的廣泛普及對(duì)無線定位技術(shù)提出新的要求和挑戰(zhàn)，引起了國(guó)內(nèi)外學(xué)者的高度關(guān)注并開展深入研究[1].基于到達(dá)時(shí)間差（TimeDifferenceofArrival，TDOA）的定位系統(tǒng)成本低、定位精度高等優(yōu)勢(shì)，已成為該領(lǐng)域的重要研究方向[2].

TDOA定位技術(shù)通過構(gòu)建非線性雙曲線方程組并對(duì)其進(jìn)行求解，計(jì)算出移動(dòng)臺(tái)的位置坐標(biāo).目前常用算法在求解該方程組時(shí)存在性能受限問題，Chan氏算法[3性能受限于噪聲特性，當(dāng)噪聲為非高斯隨機(jī)變量或非零均值時(shí)，定位性能顯著降低；Taylor級(jí)數(shù)展開法4作為遞歸算法，存在初始解依賴缺陷，當(dāng)初始值設(shè)置不合理時(shí)不能計(jì)算出最終收斂結(jié)果;最小二乘法及其改進(jìn)算法[5]在運(yùn)算過程中涉及矩陣求逆問題，若測(cè)量值數(shù)量不當(dāng)則會(huì)出現(xiàn)矩陣奇異或明顯的門限效應(yīng).智能優(yōu)化算法為解決上述問題提供了新思路，如粒子群算法（Particle Swarm Optimization，PSO)[6]、遺傳算法(GeneticAlgorithm，GA)[7]、樽海鞘群算法[8]、哈里斯鷹優(yōu)化算法[9]和蜉蝣算法[10]等通過并行搜索機(jī)制可以更快找到最優(yōu)解.

鳥群優(yōu)化算法（Bird Swarm Algorithm，BSA)[11是一種基于鳥群覓食行為的群智能優(yōu)化算法，具有操作簡(jiǎn)單、參數(shù)少、運(yùn)算速度快、魯棒性好等優(yōu)點(diǎn)，但也存在尋優(yōu)后期缺乏種群多樣性、尋優(yōu)速度慢、易陷入局部最優(yōu)等問題.文獻(xiàn)［12]通過在BSA中加人自適應(yīng)慣性權(quán)重實(shí)現(xiàn)動(dòng)態(tài)調(diào)整搜索空間、改變收斂速度.文獻(xiàn)[13]提出通過自適應(yīng)感知系數(shù)、社會(huì)系數(shù)及學(xué)習(xí)因子優(yōu)化飛行行為，不僅避免算法陷入局部最優(yōu)，還保證個(gè)體尋優(yōu)能力.

本文首先剖析了TDOA和BSA 的理論基礎(chǔ)，提出一種改進(jìn)鳥群優(yōu)化算法（ImprovedBirdSwarmAlgorithm，IBSA);然后構(gòu)建了基于IB-SA的TDOA非線性方程組求解算法；最后通過仿真實(shí)驗(yàn)，在二維空間中驗(yàn)證了所提算法在收斂速度、定位性能的優(yōu)越性.

TDOA定位模型

1.1 定位原理

TDOA定位通過檢測(cè)移動(dòng)臺(tái)信號(hào)到達(dá)兩個(gè)基站的時(shí)間差實(shí)現(xiàn)移動(dòng)臺(tái)定位.由幾何原理可知，平面內(nèi)到兩定點(diǎn)的距離差的絕對(duì)值為定長(zhǎng)的點(diǎn)的軌跡叫做雙曲線，因此TDOA定位又稱為雙曲線定位.

雙曲線定位原理如圖1所示，已知移動(dòng)臺(tái)MS到基站 BS1 和 BS2 的距離分別是 R1 和 R2 ，根據(jù)幾何原理可知，移動(dòng)臺(tái)位于以 BS1 和 BS2 為焦點(diǎn)、以移動(dòng)臺(tái)MS到兩基站的距離差 R2,1=R2- R1 為焦距的雙曲線上.同理，如果得到移動(dòng)臺(tái)到基站 BS3 與基站 BS1 或 BS2 的距離差 R3,1 或R3,2 ，就可以構(gòu)造出另外一條雙曲線.這兩條雙曲線相交于兩點(diǎn)，其中一個(gè)交點(diǎn)就是移動(dòng)臺(tái)MS的估計(jì)位置.通過求解 R2,1 和 R 3,1 或 R3,2 構(gòu)成的方程組，則可以得到兩個(gè)解，即這兩條雙曲線的交點(diǎn)，再根據(jù)小區(qū)半徑等信息，就可以得到移動(dòng)臺(tái)MS的位置估計(jì)坐標(biāo).

圖1雙曲線定位原理

1.2 TDOA定位模型

二維平面定位系統(tǒng)中基站數(shù)目為 M(M) 3)，移動(dòng)臺(tái)MS的待定位坐標(biāo)為 (x,y) ，第 i 個(gè)基站 BSi 的坐標(biāo)為 (Xi,Yi) ，移動(dòng)臺(tái)MS到第 i 個(gè)基站 BSi 的實(shí)際距離為 Ri ，則

其中： τi 表示定位信號(hào)從移動(dòng)臺(tái)到達(dá)第 i 個(gè)基站

的到達(dá)時(shí)間真實(shí)值； c 為信號(hào)傳播速度即光速.利用公式（1）將其轉(zhuǎn)化為基站與移動(dòng)臺(tái)之間的距離：

Ri=cτi.

以 BS1 為服務(wù)基站，記MS到 BSi(i≠1) 和MS到 BS1 的真實(shí)距離差為 Ri,10 ，其測(cè)量值為Ri,1 ，則

Ri,1=c*τi,1=Ri,1°+c*ni,1=

Ri-R1+c×ni,1,i=2,3,?,M,

其中： τi,1 為MS到 BSi 與 MS 到 BS1 之間的TDOA測(cè)量值； ni,1 為TDOA進(jìn)行測(cè)量時(shí)系統(tǒng)正常存在的噪聲.為了方便后續(xù)分析，將其理想化為服從獨(dú)立同分布，且均值為0、方差為 σ2 的高斯白噪聲，則

c*ni,1,i=1,2,?,M.

求解移動(dòng)臺(tái)MS的位置就是求解由 M-1 個(gè)公式（4）組成的方程組，即

ΔR=(R-R1)+c?n=

其中：

由上可知， ΔR 服從均值為 (Ri-R1) 、方差為σi 的高斯分布，又因各測(cè)量值之間是相互獨(dú)立的，故方程組的最大似然函數(shù)可表示為

求解公式（6）相當(dāng)于求解公式（7）的目標(biāo)函數(shù)，即

(x,y)=

公式（7）的非線性特性導(dǎo)致解析法求解難以獲取，故本文采用改進(jìn)的鳥群優(yōu)化算法求解目標(biāo)函數(shù)的最優(yōu)值，根據(jù)公式（7）可以推導(dǎo)出算法采用的適應(yīng)度函數(shù)為

其中， X 為改進(jìn)的鳥群優(yōu)化算法中鳥群個(gè)體的位置.

2 鳥群優(yōu)化算法

BSA中鳥類主要有3種行為：覓食、警惕和飛行.記 Ψt 時(shí)刻時(shí)第 i 只鳥的位置為 $\{ x _ { i , j } ^ { \ t } ( i \in [ 1 , 2 \$ ?,N],j∈[1,2,?,D]) .其中 N 為鳥群的個(gè)體數(shù)； D 為鳥群個(gè)體的維度.

傳統(tǒng)覓食行為的位置更新公式為

xi,jt+1=xi,jt+(?best-xi,jt)×

C×rand(0,1)+(gbest-xi,jt)×S×rand(0,1),

其中： ρbest 為第 i 只鳥目前最佳位置； gbest 為種群目前最佳位置； rand(0,1) 為服從（0，1）均勻分布的隨機(jī)數(shù)；C和S是兩個(gè)正常數(shù).

警惕行為的位置更新公式為

xi,jt+1=xi,jt+A1×(meanj-xi,jt)×

rand(0,1)+A2×(?k,j-xi,jt)×rand(-1,1),

其中， k(k≠i) 為一個(gè)取值范圍為 [1,N] 的隨機(jī)正整數(shù)； 為兩個(gè)取值范圍為[0，2]的正常數(shù)； ?pFiti 和 ?Fitk 分別為第 i 只鳥和第 k 只鳥的最佳適應(yīng)度值； sumFit 為所有鳥群個(gè)體的適應(yīng)度值之和； ε 是用來避免零除誤差最小的常數(shù)；mean；為第 j 維所有個(gè)體的平均個(gè)體最優(yōu)位置；當(dāng)某一個(gè)體向鳥群的中心位置移動(dòng)時(shí)，周圍環(huán)境引起的影響由 A1 表示，特定干擾引起的影響由A2 表示.

FQ為一個(gè)正整數(shù)，用來表示鳥群飛行的單位間隔.此時(shí)，一些鳥類作為生產(chǎn)者尋找食物塊，而另一些則作為乞食者試圖從生產(chǎn)者找到的食物塊中覓食.它們的位置更新公式分別為

xi,jt+1=xi,jt+(xk,jt-xi,jt)×FL×rand(0,1),

xi,jt+1=xi,jt+randn(0,1)×xi,jt,

其中： randn(0,1) 表示均值為0、標(biāo)準(zhǔn)差為1的高斯分布隨機(jī)數(shù)； k(k≠i) 表示取值范圍為 [1,N] 的隨機(jī)正整數(shù)； FL∈[0,2] 表示搜索者會(huì)跟隨生產(chǎn)者搜索食物.

3改進(jìn)的鳥群優(yōu)化算法

3.1 改進(jìn)的初始種群

針對(duì)BSA算法在問題求解時(shí)因初始化質(zhì)量低而導(dǎo)致的種群多樣性不足問題，提出混沌映射初始化改進(jìn)方法.混沌變量因其隨機(jī)性、遍歷性和規(guī)律性特點(diǎn)，能夠生成均勻性的初始種群，有效保持種群的多樣性.目前比較常用的混沌映射有Chebyshev映射、Logistic映射、Tent映射和Ber-noulli映射[14].4種混沌映射的序列圖和散點(diǎn)圖如圖2和圖3所示.

（a）Chebyshev映射

8 0 。（剩余11544字）