基于改進鳥群優化算法的TDOA定位算法

中圖分類號：TP391 文獻標志碼：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世紀80年代以來，智能交通系統的快速發展和蜂窩無線通信的廣泛普及對無線定位技術提出新的要求和挑戰，引起了國內外學者的高度關注并開展深入研究[1].基于到達時間差（TimeDifferenceofArrival，TDOA）的定位系統成本低、定位精度高等優勢，已成為該領域的重要研究方向[2].

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

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

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

TDOA定位模型

1.1 定位原理

TDOA定位通過檢測移動臺信號到達兩個基站的時間差實現移動臺定位.由幾何原理可知，平面內到兩定點的距離差的絕對值為定長的點的軌跡叫做雙曲線，因此TDOA定位又稱為雙曲線定位.

雙曲線定位原理如圖1所示，已知移動臺MS到基站 BS₁ 和 BS₂ 的距離分別是 R₁ 和 R₂ ，根據幾何原理可知，移動臺位于以 BS₁ 和 BS₂ 為焦點、以移動臺MS到兩基站的距離差 R_2，1=R₂- R₁ 為焦距的雙曲線上.同理，如果得到移動臺到基站 BS₃ 與基站 BS₁ 或 BS₂ 的距離差 R_3，1 或R_3，2 ，就可以構造出另外一條雙曲線.這兩條雙曲線相交于兩點，其中一個交點就是移動臺MS的估計位置.通過求解 R_2，1 和 R _3，1 或 R_3，2 構成的方程組，則可以得到兩個解，即這兩條雙曲線的交點，再根據小區半徑等信息，就可以得到移動臺MS的位置估計坐標.

1.2 TDOA定位模型

二維平面定位系統中基站數目為 M(M) 3)，移動臺MS的待定位坐標為 (x，y) ，第 i 個基站 BS_i 的坐標為 (X_i，Y_i) ，移動臺MS到第 i 個基站 BS_i 的實際距離為 R_i ，則

其中： τ_i 表示定位信號從移動臺到達第 i 個基站

的到達時間真實值； c 為信號傳播速度即光速.利用公式（1）將其轉化為基站與移動臺之間的距離：

R_i=cτ_i.

以 BS₁ 為服務基站，記MS到 BS_i(i≠1) 和MS到 BS₁ 的真實距離差為 R_i，1⁰ ，其測量值為R_i，1 ，則

R_i，1=c*τ_i，1=R_i，1^°+c*n_i，1=

R_i-R₁+c×n_i，1，i=2，3，?，M，

其中： τ_i，1 為MS到 BS_i 與 MS 到 BS₁ 之間的TDOA測量值； n_i，1 為TDOA進行測量時系統正常存在的噪聲.為了方便后續分析，將其理想化為服從獨立同分布，且均值為0、方差為 σ² 的高斯白噪聲，則

c*n_i，1，i=1，2，?，M.

求解移動臺MS的位置就是求解由 M-1 個公式（4）組成的方程組，即

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

其中：

由上可知， ΔR 服從均值為 (R_i-R₁) 、方差為σ_i 的高斯分布，又因各測量值之間是相互獨立的，故方程組的最大似然函數可表示為

求解公式（6）相當于求解公式（7）的目標函數，即

(x，y)=

公式（7）的非線性特性導致解析法求解難以獲取，故本文采用改進的鳥群優化算法求解目標函數的最優值，根據公式（7）可以推導出算法采用的適應度函數為

其中， X 為改進的鳥群優化算法中鳥群個體的位置.

2 鳥群優化算法

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

傳統覓食行為的位置更新公式為

x_i，j^t+1=x_i，j^t+(?_best-x_i，j^t)×

C×rand(0，1)+(g_best-x_i，j^t)×S×rand(0，1)，

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

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

x_i，j^t+1=x_i，j^t+A₁×(mean_j-x_i，j^t)×

rand(0，1)+A₂×(?_k，j-x_i，j^t)×rand(-1，1)，

其中， k(k≠i) 為一個取值范圍為 [1，N] 的隨機正整數； 為兩個取值范圍為[0，2]的正常數； ?_pFiti 和 ?Fit_k 分別為第 i 只鳥和第 k 只鳥的最佳適應度值； sumFit 為所有鳥群個體的適應度值之和； ε 是用來避免零除誤差最小的常數；mean；為第 j 維所有個體的平均個體最優位置；當某一個體向鳥群的中心位置移動時，周圍環境引起的影響由 A₁ 表示，特定干擾引起的影響由A₂ 表示.

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

x_i，j^t+1=x_i，j^t+(x_k，j^t-x_i，j^t)×FL×rand(0，1)，

x_i，j^t+1=x_i，j^t+randn(0，1)×x_i，j^t，

其中： randn(0，1) 表示均值為0、標準差為1的高斯分布隨機數； k(k≠i) 表示取值范圍為 [1，N] 的隨機正整數； FL∈[0，2] 表示搜索者會跟隨生產者搜索食物.

3改進的鳥群優化算法

3.1 改進的初始種群

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

8 0 。 000 。。 。 80。 ③。。 00 0 8日

0.69 8

0.4 °。 。 。 。 。。 。 ? 。。

0.208 0o 。 。 。 。 。 。 。 。 00。 。 。 。 8。 000C 。 0

-0.4 o 00 。 00 。

0 。 8。 。

-1088008

-1-0.8-0.6-0.4-0.2 0 0.2 0.4 0.6 0.8 1

8 188 o0 8 。 8。 。 800000 8。 8 。 。 08

0.8 。 8。

0.7 。 00 。

0.6 。 8 。。 。 。oo。

08 0.59 0. 。 。 oo 。 8。 o。 8。。。 0 。 。 。 80000 。 。 8 。 000 100 0088 800 -000 0.1 0.20.3 0.40.5 0.6 0.7 0.8 0.9 1（b）Logistic 映射

1 。 8

0.9 o。 。 。 0 。0

0.80 0。 。

0. 。 。 0 。。。 。。

0.5 。 。 。。 。 0

0.40 0。

0.3 0 。 。 。 0

0.2 。。 。 。 。0

0.1 。0

00 00 0.10.20.3 0.4 0.5 0.6 0.7 0.80.9 1(c）Tent 映射

cF。 。。8 。 。8 。

0.20 00

0.1 品 。。 8。 8 000 80 00 80

-0.1 000 。

-0.3 8品 。 0 。 。0

-0.4 。 88 8 08 @。 。

-0.5 b

-0.5 0 0.5 1（d）Bernoulli映射

從圖2和圖3可以看出，Chebyshev映射比Logistic、Tent和Bernoulli的均勻性相對較好，故本文采用Chebyshev混沌映射對種群進行初始化，其映射公式為

Cx_n∈[-1，1].

其中： Cx(n+1)_i 為映射的第 i 個混沌變量 C_Xi 在第 n 次混沌變換后的值，當Chebyshev映射的階數 k?2 時，該映射函數處于混沌狀態，故本文取k=2

采用Chebyshev混沌映射初始化種群的具體步驟如下：

(1)隨機產生一個 D 維向量，即 ，Cx₂，?，Cx_D)

(2)按式(15)進行 2N-1 次迭代，產生混沌序列 cx ：

(3)達到最大迭代次數后，停止運行并根據公式(16)將混沌變量映射到解空間.即

其中： _Lb，Ub 為每個個體在每個維度上的上下界；

X 為解空間的優化向量； cx 為混沌向量.

（4）計算個體適應度函數值，從中選擇性能較好的前 N 個個體作為初始的種群.

3.2 改進的鳥群覓食行為

認知加速系數 C 和社會加速系數 S 作為調節BSA中個體運動方向的關鍵參數，當 C 取較大值時，個體傾向于向個體最優位置方向運動，有助于算法的全局尋優；當 S 取較大值時，個體傾向于向種群最優位置方向運動，有助于算法的局部尋優.為平衡全局搜索與局部開發能力[14]，本文設計了非線性遞減的認知加速系數和非線性增加的社會加速系數，在算法初期 C 值較大 S 值較小，促進個體廣泛探索解空間；在算法后期 C 值較小 S 值較大，實現局部開發能力的不斷增強，具體計算公式為

其中： Ψ_t 為當前迭代次數； T 為最大迭代次數.故改進后的鳥群覓食位置的更新公式為

3.3 基于IBSA算法的TDOA定位

使用IBSA算法進行 TDOA定位的流程如圖4所示.

按照上述流程，使用IBSA算法進行TDOA定位的具體步驟如下：

(1)初始化參數.包括種群規模 N ，目標函數的維度 D ，初始值的上下界 ，最大迭代次數 T ，飛行間隔 FQ ，覓食概率 P ，兩個正常數 α_a1 ）a2

(2)初始化種群.根據3.1節分析，采用Chebyshev混沌映射初始化鳥類種群；

(3)計算初始適應度.利用式(8)計算所有個體的適應度，并選出當前個體最優和全局最優；

(4)覓食或者警惕行為.如果當前迭代次數 ，則對于每個個體，生成一個服從(0，1)均勻分布的隨機數，如果其小于覓食概率 P ，則通過式(19)進行覓食，否則通過式(10)保持警惕；

(5)生產者或者乞食者行為.如果當前迭代次數 t%FQ=0 ，則鳥群選擇飛行，對于生產者通過式(13)進行覓食；對于乞食者，通過式(14)進行跟隨；

（6)計算當前適應度.計算更新后種群中個體的適應度值，并更新當前個體最優和全局最優；

（7)判斷算法運行是否達到最大迭代次數，若是則循環結束，輸出尋優結果；否則返回（4).

4實驗及結果分析

4.1 實驗環境

為測試所提算法在求解TDOA定位問題時的性能，通過Matlab軟件對該算法不同的迭代次數、測量誤差、小區半徑和基站個數進行仿真分析，并選擇PSO、GA、BSA作為對比算法.仿真采用典型的7小區蜂窩結構如圖5所示.

其中： R 為小半徑

選取 BS₁ 作為服務基站，以均方根誤差（RootMean SquaredError，RMSE）作為定位精度評價指標（RMSE越小表示定位性能越優），其公式為

其中： (x_i，y_i) 為第 i 次實驗移動臺的估計坐標； (x

y）為移動臺的實際坐標；Num為實驗的總次數.

4.2 實驗結果及分析

4.2.1 收斂性能分析

在小區半徑為 3km 、測量誤差為 0. 03km 、

最大迭代次數為100、基站個數7的相同實驗條件下對PSO、GA、BSA、IBSA的適應度值進行仿真，結果如圖6所示.

隨著迭代次數的增加，4種算法的適應度值隨之降低，并逐漸趨于穩定.其中，IBSA算法相對于其他3種算法收斂速度較快.

4.2.2 定位精度分析

為綜合評估算法性能，本文從迭代次數、處理誤差、小區半徑、基站個數4個維度對比PSO、GA、BSA和IBSA4種算法在求解定位目標時的RMSE，實驗結果如圖7～圖10所示.

隨著迭代次數的增加，定位誤差隨之降低，然后趨于穩定.并且當迭代次數相同時，IBSA算法的RMSE低于其他3種對比算法.

忽略非視距(NonLineofSight，NLOS)誤差，僅僅考慮測量誤差對定位性能的影響，且測量誤差服從理想的高斯分布（均值為0，標準差為

0. 03～0. 09km) .從實驗結果來看，隨著TDOA測量誤差的不斷增大，不同算法的RMSE都逐漸增大，所提IBSA算法的RMSE略低于其他3種算法.

隨著小區半徑的增大 (1～4km)，4 種算法定位的均方根誤差均隨之增大.分析為隨著小區半徑的增大，移動臺與基站之間的距離會隨之增大，從而導致NLOS誤差的增大，定位精度隨之也會下降.但從圖9仍可以看出，IBSA算法的RMSE均低于其他3種算法.

隨著基站個數從4增至7，4種算法定位性能均有一定程度的改善.這是由于基站個數增加帶來了更多的冗余信息，從而使得定位性能得到了提升.從圖10可以看出，無論基站個數的多少，IBSA算法的定位精度均高于其他3種算法.

5 結語

針對TDOA定位系統的非線性方程組求解復雜問題，本文提出了一種對初始種群以及鳥群覓食行為進行優化的改進鳥群優化算法.實驗結果表明，與粒子群算法、遺傳算法、鳥群優化算法相比，改進鳥群優化算法具有定位誤差低、收斂速度快等優點.未來工作將進一步研究三維空間的TDOA定位算法，以及考慮智能優化算法在到達時間差一到達頻率差聯合定位技術中的應用.

參考文獻：

[1]CAMAJOR T B，BRAMBILLA M，ITALIANO L，et al.A feasibility study of 5G positioning with current cellular network deployment[J]. Scientific Reports， 2023，13(1):15281-15296.

[2]SUN Y，HO K C，XING T，et al.Projection-based algorithm and performance analysis for TDOA localization in MPR[J]. IEEE Transactions on Signal Processing，2024，72:896-911.

[3]XING X，ZHONG Z，LI X，et al. Node selection and path optimization for passive target localization via UAVs[J].Sens0rs，2025，25(3):780-806.

[4]湯新民，李帥，周楊.多點定位接收機的設計與實現 [J].西華大學學報（自然科學版），2024，43（1）：28-

35.

[5]KRAVETSI，KAPSHII O，SHUPARSKYYO，etal.A new parametric three stage weighted least squaresalgorithm for TDOA-based localization[J]. IEEE Ac-cess，2024，12:19829-19839.

[6]楊光，屈德新，張更新.基于改進粒子群-牛頓算法級聯的雙星定位方法[J].太赫茲科學與電子信息學報，2024，22(11):1253-1261，1303.

[7]趙越，李贊，李冰，等.面向多源時差定位的魯棒節點部署算法[J].西安電子科技大學學報，2022，49（6)：15-22，163.

[8]韋子輝，王世昭，葉興躍，等.基于超寬帶的 TDOA 相鄰單元協同定位技術[J].電子測量技術，2022，45(1) :77-83.

[9]馬一鳴，石志東，趙康，等.基于改進哈里斯鷹優化算法的TDOA定位[J].計算機工程，2020，46（12）：179-184.

[10］宋湘鈺，任秀麗.基于多策略改進的蜉蝣算法在WSN定位中的應用[J].傳感技術學報，2025，38(2):348-355.

[11] MENG X B，GAO X Z，LU L，et al. A new bio-in-spired optimisation algorithm: bird swarm algorithm[J].Journal of Experimental . Theoretical Artifi-cial Intelligence，2016，28(4) : 673-687.

[12]林焰，辛登月，紀卓尚，等.基于改進鳥群算法的艦船管道路徑設計方法[J].哈爾濱工程大學學報，2025，46(1) :27-37.

[13］陳暄，趙文君，龍丹.面向移動云計算任務調度的改進鳥群算法研究[J].計算機應用研究，2021，38（3)：751-754，781.

[14] YANG J，LIU Z， ZHANG X，et al. Elite chaoticmanta ray algorithm integrated with chaotic initial-ization and opposition-based learning[J]. Mathemat-ics，2022，10(16):2960-2993.

[責任編輯：李 嵐]