一種基于鯨魚優化的TOA/AOA最優化定位算法

秦 杰，鄧 平，羅 銳，夏漁平

一種基于鯨魚優化的TOA/AOA最優化定位算法

秦 杰1，鄧 平1，羅 銳2，夏漁平1

（1.西南交通大學 信息科學與技術學院，成都 610097；2.成都師范學院 計算機學院，成都 611130）

針對非視距（NLOS）環境下，基于最優化原理的無線定位算法在迭代運算后期容易陷入局部最優，進而導致定位精度下降的問題，提出一種基于非線性、自適應、動態慣性權重的鯨魚優化到達時間（TOA）/到達角（AOA）最優化定位算法：基于雙基站定位場景建立TOA/AOA混合定位模型；并且在對種群位置進行初始化時，在混合線性定位算法中增加角度約束條件避免種群在定位初期陷入局部最優；然后在搜索更新最優個體時，引入自適應動態慣性權重系數對鯨魚優化算法進行改進，以更好地協調優化算法的全局隨機搜索與局部尋優能力。仿真結果表明，與現有的粒子群優化（PSO）、鯨魚優化（WOA）和改進的鯨魚優化（MWOA）等智能優化算法相比，所提算法在迭代尋優過程中具有更快的收斂速度和更優的收斂精度；相較于WOA算法，其平均消耗時間可降低約50%，平均定位誤差可降低約41%，定位性能更優。

鯨魚優化算法（WOA）；非視距（NLOS）；智能優化；無線定位

0 引言

在移動互聯網時代，基于位置的目標跟蹤、智能交通、物聯網和緊急救援等定位服務更加普及。隨著第五代移動通信技術（fifth-generation，5G）基站在室內外環境大量部署，基于5G網絡的無線定位技術在定位服務中得到更廣泛的應用。然而無線定位中電波的非視距（non line of sight，NLOS）傳播嚴重影響定位性能。如何抑制無線定位中無線信號NLOS傳播導致的定位誤差成為人們關注的熱點。

基于最優化理論的無線定位算法因其良好的定位性能一直受到廣泛關注[1]。文獻[2]提出了2種基于多基站的混合到達時間（time of arrival，TOA）和到達角（angle of arrival，AOA）的定位算法，即混合TOA/AOA（hybrid TOA/AOA，HTA）算法和混合線性定位（hybrid lines of position，HLOP）算法，但這2種算法抑制NLOS誤差的能力有限。文獻[3]對文獻[2]中的算法進行改進，通過在目標函數中加入散射體的位置坐標信息，提出了混合TOA/AOA約束算法（TOA/AOA constraint algorithm，TACA）；但該算法采用最優化理論中的內點法[4]來估計移動臺的位置，性能受初始值影響較大，且容易陷入局部最優解。文獻[5]中提出了一種應用于雙基站場景的NEWTACA最優化定位算法，在原TACA算法的基礎上，引入了一個隱藏的有關角度的非線性等式約束；但由于目標函數的高非線性和非凸性，NEWTACA算法同樣可能會收斂到局部最優。為此，文獻[5]中還通過引入智能優化算法，提出了一種網格搜索算法[6]，通過引入2個尺度因子進行搜索及最優化求解。除了上述解析算法外，粒子群算法（particle swarm optimization，PSO）[7]、人工神經網絡（artificial neural network，ANN）[8-9]、哈里斯鷹算法（Harris hawk optimization，HHO）[10]等智能優化算法也被應用于最優化定位領域，并在一定程度上改善了定位性能。如文獻[11]中提出了一種基于混沌粒子群優化算法的混合TOA/AOA定位算法，利用混沌理論進一步對PSO算法進行優化和改進，并且引入了自適應慣性權重策略，對算法中的慣性權重參數采用動態自適應變化的方式，在迭代過程中根據粒子所處的位置選擇適合的慣性權重值，能夠達到全局最優；但是該算法計算復雜度高，存在收斂速度慢的問題。文獻[12]中將哈里斯鷹優化算法用于TDOA定位的非線性問題求解，對初始種群和適應度函數進行了優化，在一定程度上增強了搜索能力；但是仍然存在算法迭代運算后期容易陷入局部最優的問題，導致無法達到全局最優解。

如何解決最優化定位算法可能陷入局部最優的問題，一直是相關領域的重要課題。為此，本文提出一種基于鯨魚優化的TOA/AOA最優化定位算法。首先在雙基站定位場景下，建立TOA/AOA混合定位模型；接著提出一種基于自適應動態慣性權重的鯨魚優化算法，并利用基站、移動臺與散射體之間的幾何位置關系，建立新的最優化目標函數和約束條件；然后在目標可行域內利用上述鯨魚優化算法進行移動臺最優位置的估計。

1 TOA/AOA混合定位模型

圖1 基站與移動臺幾何分布

圖2 AOA角度約束

因此，雙基站場景下的TOA/AOA混合定位模型可以建立為

求解式（6）的常用方法是最優化理論中的內點法，但該方法的不足是容易陷入局部最優[14]，導致MS定位精度受損。

2 自適應動態權重鯨魚優化定位算法

2.1 鯨魚優化基本原理

鯨魚優化算法（whale optimization algorithm，WOA）[15]是2016年由Mirjalili等人提出的一種模仿座頭鯨的捕食行為的新型啟發式優化算法，也是一種群體智能優化算法，其優點在于有較強的全局搜索能力和開發能力。基于鯨魚捕食策略的WOA算法主要包含3個部分，即圍獵場、泡泡網攻擊（開發階段）和搜尋獵物（探索階段）。前2個部分通過收縮包圍機制達到局部優化目的，而搜尋獵物通過隨機搜索進行全局尋優。

包圍獵場階段：鯨魚可以識別獵物的位置并包圍它們，這種行為可以表示為：

泡泡網攻擊（開發階段）：需要計算鯨魚離目前群體最優值的距離，然后構建螺旋方程，模擬鯨魚通過噴出氣泡來驅趕獵物，進而更新位置，更新公式為

在鯨魚更新位置時，包圍獵場和泡泡網攻擊機制是同步進行的，選擇2種策略進行更新的概率均為50%，其數學模型表示為

2.2 計算MS初始位置

HLOP算法[1]是一種混合TOA/AOA的線性定位算法。不同于HTA算法[1]和TACA算法[2]使用目標函數和約束條件，該算法將測距問題一階線性化，計算過程簡單且計算復雜度較低。本文采用文獻[2]中的HLOP算法估計MS的初始位置，同時增加式（5）中的角度約束條件，命名為NEWHLOP算法。

2.3 自適應動態慣性權重策略

2）非線性自適應動態慣性權重策略。受文獻[18]和[19]的啟示，非線性自適應動態慣性權重策略可能更適合WOA算法實際搜索優化過程。本文在該文獻基礎上引入了變量迭代次數并且增加慣性權重的閾值判斷，基于此提出本文的第二種自適應動態慣性權重策略。具體表達式為

2.4 定位算法流程

本文提出基于自適應動態慣性權重的鯨魚優化定位算法（adaptive whale optimization algorithm，AWOA），算法流程如圖3所示。具體步驟如下：

步驟1）初始化種群。將初始值設為NEWHLOP算法所確定的MS初始位置。

步驟2）計算種群適應度值。根據MS目標初始值計算出個體適應度值，并將最優個體設置為全局最優值。

圖3 AWOA定位算法流程

步驟5）判斷是否達到最大迭代數，如果是則輸出最優估計值并終止迭代；否則返回步驟3）。

3 實驗與結果分析

3.1 基準函數測試

為了檢驗本文提出的基于非線性自適應動態慣性權重的鯨魚優化算法（AWOA）和其他群體智能優化算法的尋優性能，采用基準函數[20]進行仿真測試，并進行對比分析。

圖4 基準測試函數收斂曲線

3.2 定位性能分析

將加入線性和非線性自適應動態慣性權重策略的鯨魚優化定位算法（AWOA1和AWOA2算法）與傳統的WOA算法、TACA算法、NEWTACA算法、網格搜索算法（grid-search-based algorithm，GSA）和NEWHLOP算法進行定位性能仿真分析。由3.1節中的仿真結果可知，針對大部分測試函數，最大迭代次數為40時即可收斂到最優值，因此本文算法迭代次數設置為40。此外，2種AWOA算法的其他參數設置與3.1節的參數相同。

如圖5所示為圓盤模型（disk of scatter，DOS）[13]下不同算法的定位誤差累積分布函數（cumulative distribution function，CDF）曲線。從圖中可以看出，本文中AWOA2算法的平均定位誤差小于130 m以下的概率能達到100%，定位性能優于GSA智能優化算法和NEWTACA算法。

圖5 DOS模型下的定位誤差累計分布

固定AOA角度測量誤差和TOA距離測量誤差，改變散射體半徑使其從100～300 m遞增。如圖6所示為DOS模型下不同算法相對于不同散射半徑的平均定位誤差（average location error，ALE）。從圖可以看出，各算法的ALE均隨著散射半徑的增加而增加，這是散射半徑的增加使得NLOS誤差變大而導致的結果。本文AWOA2算法隨著散射半徑的增加始終表現出最低的ALE，從曲線總體趨勢上看，本文算法誤差增加得更為緩慢，說明AWOA2算法具有更強的NLOS誤差抑制能力。

圖6 DOS模型下ALE隨散射半徑的變化曲線

在DOS模型下，各算法相對于不同AOA角度測量誤差和TOA距離測量誤差的ALE性能曲線如圖7和圖8所示。從圖中可以看出，ALE對TOA和AOA測量誤差的變化均不敏感，但TACA算法和NEWTACA算法的ALE性能曲線相對波動較大，這是因為它們是基于內點法進行定位解算，容易陷入局部最優解；而智能優化算法由于良好的全局搜索能力表現出較強的魯棒性，且在不同測量誤差下，AWOA2算法平均定位誤差明顯低于其他對比算法，驗證了本文算法具有較優的定位性能。

圖7 ALE隨角度測量誤差的變化曲線

圖8 ALE隨距離測量誤差的變化曲線

如表1所示為幾種不同的定位算法在中央處理器（central processing unit，CPU）為AMD Ryzen74800U、主頻為1.80 GHz的電腦上使用矩陣實驗室（matrix laboratory，MATLAB）軟件于同一仿真環境下進行1000次獨立定位的平均消耗時間和平均定位誤差。從表中可以看出，雖然本文的AWOA算法計算復雜度略高于NEWHLOP算法和GSA算法，但定位性能最佳。在傳統的WOA算法基礎上引入自適應動態慣性權重策略之后，AWOA2算法的平均消耗時間降低了約50%，而平均定位誤差則降低了約41%，具有更好的定位性能。

表1 算法平均消耗時間及平均定位誤差

4 結束語

[1] LIU Y, WANG Y, SHEN Y, et al. Hybrid TOA-AOA WLS estimator for aircraft network decentralized cooperative localization[J]. IEEE Transactions on Vehicular Technology, 2023, 72(7): 9670-9675.

[2] VENKATRAMAN S, CAFFERY J. Hybrid TOA/AOA techniques for mobile location in non-line-of-sight environments[C]// Wireless Communications & Networking Conference. IEEE, 2004.

[3] Al-JAZZAR S, GHOGHO M, MCLERNON D. A joint TOA/AOA constrained minimization method for locating wireless devices in non-line-of-sight environment[J]. IEEE Transactions on Vehicular Technology, 2009, 58(1): 468-472.

[4] BOYD S P, VANDENBERGHE L. Convex optimization[M]. Cambridge University Press, 2004.

[5] WU S, XU D, WANG H. Joint TOA/AOA location algorithms with two BSs in circular scattering environments[J]. WSEAS Transactions on Communications, 2015, 14: 235-240.

[6] XIE Y, WANG Y, ZHU P, et al. Grid-search-based hybrid TOA/AOA location techniques for NLOS environments[J]. IEEE Communications Letters, 2009, 13(4): 254-256.

[7] GAD A G. Particle swarm optimization algorithm and its applications:A systematic review[J]. Archives of Computational Methods in Engineering, 2022, 29(5): 2531-2561.

[8] WYE K, ZAKARIA S, KAMARUDIN L M, et al. RSS-based fingerprinting localization with artificial neural network[J]. Journal of Physics:Conference Series, 2021, 1755(1): 012033.

[9] CHENG C H, WANG T P, HUANG Y F. Indoor positioning system using artificial neural network with swarm intelligence[J]. IEEE Access, 2020, 8: 84248-84257.

[10] HEIDARI A A, MIRJALILI S, FARIS H, et al. Harris hawks optimization:Algorithm and applications[J]. Future Generation Computer Systems, 2019, 97: 849-872.

[11] TAGNE F E, NYABEYE P D K, TONYE E. A new hybrid localization approach in wireless sensor networks based on particle swarm optimization and tabu search[J]. Applied Intelligence, 2022: 1-16.

[12] MIHOUBI M, RAHMOUN A, LORENZ P. Node localization in WSN and IoT using harris hawks optimization algorithm[J]. 2021 IEEE Global Communications Conference (GLOBECOM), 2021: 1-6.

[13] ERTEL R B, REED J H. Angle and time of arrival statistics for circular and elliptical scattering models[J]. IEEE Journal on Selected Areas in Communications, 1999, 17(11): 1829-1840.

[14] 鄧平, 謝雪. 基于幾何約束及迭代的NLOS環境定位算法[J]. 西南交通大學學報, 2021, 56(3): 666-672.

[15] GHAREHCHOPOGH F S, GHOLIZADEH H. A comprehensive survey:Whale optimization algorithm and its applications[J]. Swarm and Evolutionary Computation, 2019, 48: 1-24.

[16] 趙志剛, 林玉嬌, 尹兆遠. 基于自適應慣性權重的均值粒子群優化算法[J]. 計算機工程與科學, 2016, 38(3): 501-506.

[17] 董文永, 康嵐蘭, 劉宇航, 等. 帶自適應精英擾動及慣性權重的反向粒子群優化算法[J]. 通信學報, 2016, 37(12): 1-10.

[18] 張永, 陳鋒. 一種改進的鯨魚優化算法[J]. 計算機工程, 2018, 44(3): 208-213,219.

[19] 徐剛, 楊玉群, 黃先玖. 一種非線性權重的自適應粒子群優化算法[J]. 計算機工程與應用, 2010, 46(35): 49-51.

[20] MIRJALILI S, LEWIS A. The whale optimization algorithm[J]. Advances in Engineering Software, 2016, 95: 51-67.

A TOA/AOA optimization localization algorithm based on whale optimization

QIN Jie1, DENG Ping1, LUO Rui2, XIA Yuping1

（1. School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610097, China;2. School of Computer Science, Chengdu Normal Institute, Chengdu 611130, China）

Aiming at the problem that wireless localization algorithm based on optimization theory in non-line-of-sight (NLOS) environment is prone to fall into local optimum at the late stage of iterative operation, which leads to the degradation of localization accuracy, the paper proposed a whale-optimized time of arrival (TOA)/angle of arrival (AOA) optimal localization algorithm based on nonlinear, adaptive dynamic inertia weights: the hybrid TOA/AOA localization model based on double base stations localization scenario was built; and in the localization process, a hybrid linear localization algorithm with angle constraint condition was used to initialize the population position for avoiding the population from falling into local optimum at the early localization stage; then, when searching and updating the optimal individuals, adaptive dynamic inertia weight coefficient was introduced to improve the performance of whale optimization algorithm, in order to better coordinate and optimize the global stochastic search and local optimization-seeking capability of the algorithm. Simulational results showed that compared with existing intelligent optimization algorithms such as particle swarm optimization (PSO), whale optimization algorithm (WOA) and modified whale optimization algorithm (MWOA), the proposed algorithm would exhibit faster convergence speed and better convergence accuracy in the iterative optimization search process; moreover, compared with WOA algorithm, the average consumption time could be reduced by about 50%, the average positioning error could be reduced by about 41%, indicating a better localization performance.

whale optimization algorithm (WOA); non-line-of-sight (NLOS); intelligent optimization; wireless localization

秦杰，鄧平，羅銳，等. 一種基于鯨魚優化的TOA/AOA最優化定位算法[J]. 導航定位學報, 2023, 11(6): 93-101.（QIN Jie, DENG Ping, LUO Rui, et al. A TOA/AOA optimization localization algorithm based on whale optimization[J]. Journal of Navigation and Positioning, 2023, 11(6): 93-101.）DOI:10.16547/j.cnki.10-1096.20230612.

P228

A

2095-4999(2023)06-0093-09

2023-02-08

國家自然科學基金（61871332）。

秦杰（1995—），女，四川宜賓人，碩士研究生，研究方向為無線網絡定位技術。

鄧平（1964—），男，四川宜賓人，博士，教授，研究方向為無線網絡定位技術、統計信號處理等。