一種基于鯨魚優(yōu)化的TOA/AOA最優(yōu)化定位算法

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

一種基于鯨魚優(yōu)化的TOA/AOA最優(yōu)化定位算法

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

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

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

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

0 引言

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

基于最優(yōu)化理論的無線定位算法因其良好的定位性能一直受到廣泛關(guān)注[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]中的算法進行改進，通過在目標(biāo)函數(shù)中加入散射體的位置坐標(biāo)信息，提出了混合TOA/AOA約束算法（TOA/AOA constraint algorithm，TACA）；但該算法采用最優(yōu)化理論中的內(nèi)點法[4]來估計移動臺的位置，性能受初始值影響較大，且容易陷入局部最優(yōu)解。文獻[5]中提出了一種應(yīng)用于雙基站場景的NEWTACA最優(yōu)化定位算法，在原TACA算法的基礎(chǔ)上，引入了一個隱藏的有關(guān)角度的非線性等式約束；但由于目標(biāo)函數(shù)的高非線性和非凸性，NEWTACA算法同樣可能會收斂到局部最優(yōu)。為此，文獻[5]中還通過引入智能優(yōu)化算法，提出了一種網(wǎng)格搜索算法[6]，通過引入2個尺度因子進行搜索及最優(yōu)化求解。除了上述解析算法外，粒子群算法（particle swarm optimization，PSO）[7]、人工神經(jīng)網(wǎng)絡(luò)（artificial neural network，ANN）[8-9]、哈里斯鷹算法（Harris hawk optimization，HHO）[10]等智能優(yōu)化算法也被應(yīng)用于最優(yōu)化定位領(lǐng)域，并在一定程度上改善了定位性能。如文獻[11]中提出了一種基于混沌粒子群優(yōu)化算法的混合TOA/AOA定位算法，利用混沌理論進一步對PSO算法進行優(yōu)化和改進，并且引入了自適應(yīng)慣性權(quán)重策略，對算法中的慣性權(quán)重參數(shù)采用動態(tài)自適應(yīng)變化的方式，在迭代過程中根據(jù)粒子所處的位置選擇適合的慣性權(quán)重值，能夠達到全局最優(yōu)；但是該算法計算復(fù)雜度高，存在收斂速度慢的問題。文獻[12]中將哈里斯鷹優(yōu)化算法用于TDOA定位的非線性問題求解，對初始種群和適應(yīng)度函數(shù)進行了優(yōu)化，在一定程度上增強了搜索能力；但是仍然存在算法迭代運算后期容易陷入局部最優(yōu)的問題，導(dǎo)致無法達到全局最優(yōu)解。

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

1 TOA/AOA混合定位模型

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

圖2 AOA角度約束

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

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

2 自適應(yīng)動態(tài)權(quán)重鯨魚優(yōu)化定位算法

2.1 鯨魚優(yōu)化基本原理

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

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

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

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

2.2 計算MS初始位置

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

2.3 自適應(yīng)動態(tài)慣性權(quán)重策略

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

2.4 定位算法流程

本文提出基于自適應(yīng)動態(tài)慣性權(quán)重的鯨魚優(yōu)化定位算法（adaptive whale optimization algorithm，AWOA），算法流程如圖3所示。具體步驟如下：

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

步驟2）計算種群適應(yīng)度值。根據(jù)MS目標(biāo)初始值計算出個體適應(yīng)度值，并將最優(yōu)個體設(shè)置為全局最優(yōu)值。

圖3 AWOA定位算法流程

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

3 實驗與結(jié)果分析

3.1 基準(zhǔn)函數(shù)測試

為了檢驗本文提出的基于非線性自適應(yīng)動態(tài)慣性權(quán)重的鯨魚優(yōu)化算法（AWOA）和其他群體智能優(yōu)化算法的尋優(yōu)性能，采用基準(zhǔn)函數(shù)[20]進行仿真測試，并進行對比分析。

圖4 基準(zhǔn)測試函數(shù)收斂曲線

3.2 定位性能分析

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

[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環(huán)境定位算法[J]. 西南交通大學(xué)學(xué)報, 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] 趙志剛, 林玉嬌, 尹兆遠(yuǎn). 基于自適應(yīng)慣性權(quán)重的均值粒子群優(yōu)化算法[J]. 計算機工程與科學(xué), 2016, 38(3): 501-506.

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

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

[19] 徐剛, 楊玉群, 黃先玖. 一種非線性權(quán)重的自適應(yīng)粒子群優(yōu)化算法[J]. 計算機工程與應(yīng)用, 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

秦杰，鄧平，羅銳，等. 一種基于鯨魚優(yōu)化的TOA/AOA最優(yōu)化定位算法[J]. 導(dǎo)航定位學(xué)報, 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

國家自然科學(xué)基金（61871332）。

秦杰（1995—），女，四川宜賓人，碩士研究生，研究方向為無線網(wǎng)絡(luò)定位技術(shù)。

鄧平（1964—），男，四川宜賓人，博士，教授，研究方向為無線網(wǎng)絡(luò)定位技術(shù)、統(tǒng)計信號處理等。