基于改進哈里斯鷹優化算法的TDOA定位

馬一鳴,石志東,趙 康,貢常磊,單聯海

(1.上海大學 特種光纖與光接入網重點實驗室,上海 200444; 2.上海物聯網有限公司,上海 201899; 3.華東師范大學 計算機科學與軟件工程學院,上海 200062; 4.中國科學院上海微系統與信息技術研究所,上海 200050)

0 概述

位置信息在基于位置的服務和應用中起到關鍵作用。由于到達時差(Time Difference of Arrival,TDOA)定位方式不需要在發送的信號中加入時間戳,具有硬件復雜度低、定位精度高的優勢[1],因此其在室內定位中得到廣泛應用。

TDOA定位實質上是對雙曲線方程組的求解,然而傳統算法多存在不足,例如:Taylor級數展開法[2]需要選取一個與實際位置較為接近的展開點以保證算法的收斂;Chan算法[3]在測量值誤差服從高斯分布時能達到理論最優值,但當測量值存在非視距誤差時性能會顯著下降;擴展卡爾曼濾波[4-5]是一種對非線性系統進行線性近似處理的目標跟蹤算法,但跟蹤精度容易受信道條件的影響;加權最小二乘法[6]和約束總體最小二乘法[7]等基于最小二乘的改進算法在運算過程中存在矩陣求逆,當測量值較少或測量誤差較大時易產生矩陣奇異的情況。

除了上述傳統解析算法以外,粒子群優化算法[8]、遺傳算法[9]和樽海鞘群算法[10]等智能優化算法也被應用于TDOA定位。此類算法在搜索范圍內初始化大量隨機點,通過建立隨機點與測量值之間的適應度函數來評價其優劣程度,再通過算法的尋優機制迭代更新隨機點的位置,最終收斂于最優的目標估計位置。智能優化算法省略了復雜的求解過程,不存在解析算法不可導或無解的問題。由NFL(No-Free-Lunch)理論[11]可知,少有適用于所有優化問題的智能優化算法,例如在應用過程中可能存在后期收斂速度慢、陷入局部最優的問題。對此,研究者相繼提出解決方案:文獻[12]提出自適應權重策略以平衡算法的全局搜索和局部開發能力,提高收斂速度;文獻[13]通過引入變異機制,使粒子在優化過程中向不同方向運動,從而保證算法可以跳出局部最優;文獻[14]提出將人工蜂群算法與模糊C均值聚類算法相結合的改進算法,提高了尋優精度。

2019年,HEIDARI等人提出哈里斯鷹優化(Harris Hawk Optimization,HHO)算法[15],該算法有較強的全局搜索能力,并且需要調節的參數較少。文獻[16]將長期記憶引入HHO算法,使個體參考過去的經驗進行運動,增強了種群多樣性。文獻[17]采用動態控制參數減小HHO算法陷入局部最優的概率,并通過變異算子進一步提高全局搜索效率。

本文提出一種改進的哈里斯鷹優化(Improved HHO,IHHO)算法用于TDOA定位,通過對適應度函數和初始種群進行優化,提高算法的尋優精度和收斂速度。

1 TDOA定位模型

TDOA定位幾何模型如圖1所示,其中,標簽周期性地向基站發送定位信號。

圖1 TDOA定位幾何模型Fig.1 Geometric model of TDOA localization

假設基站數量為N,則定位信號到達基站i的時間為:

(1)

ri+nri-rj-nrj

(2)

(3)

nri=cnti

(4)

根據標簽到兩個不同基站的距離差能建立唯一的一條雙曲線,然后憑借多基站建立雙曲線方程組,在此基礎上,利用數學方法求解即可得到未知標簽的估計位置。

2 改進的哈里斯鷹優化算法

2.1 改進的適應度函數

(5)

求解使似然函數最大的坐標值,等價于求解下式:

(6)

當該非線性函數方程值最小時,得到標簽坐標的估計值,用解析法求解比較困難。因此,本文采用哈里斯鷹優化算法求解。利用式(7)推導出基站1為主基站時的適應度函數:

(7)

其中,X為哈里斯鷹個體的位置矢量。適應度函數的選取對算法的尋優精度有直接影響。結合式(2)和式(7)可以發現,主基站的信號到達時間t1會影響適應度函數中的所有平方項,而從基站的信號到達時間ti只會影響其中第(i-1)個平方項,這使得適應度函數對主基站的信號到達時間較為敏感,尤其是當主基站測量誤差較大時,適應度值會明顯增大,此時適應度函數會失真,不能很好地反映解的優劣程度。

定義基站i作為主基站時的適應度函數為:

(8)

其中,j≠i,i∈{1,2,…,N}。首先將每個基站作為主基站,按照最大似然法計算一個適應度函數值,然后將其中的最小值作為改進的適應度函數f(X)代入非線性函數方程進行求解,表達式為:

f(X)=min[f1(X),f2(X),…,fN(X)]

(9)

(10)

2.2 改進的初始種群

X=rand(1,2)×(ub-lb)+lb

(11)

其中,rand(1,2)表示生成2維隨機向量,其中元素為[0,1]之間的隨機數。

初始種群的分布對算法的收斂速度有很大的影響。由于沒有任何先驗知識,因此大部分智能優化算法的初始位置都隨機生成。利用混沌映射產生初始種群對提高收斂速度有一定幫助[18],但對于TDOA定位問題不是最佳解決方案。本文通過計算復雜度較低的Chan算法[3]計算出一個初始解,然后從生成的初始種群中隨機挑選出一個個體用初始解代替,從而得到改進的初始種群。由于初始解距離最終優化結果較近,因此該算法可以減少不必要的全局搜索,在不影響種群多樣性的前提下,達到快速收斂的目的。

2.3 哈里斯鷹優化算法

哈里斯鷹優化算法[15]是一種模擬哈里斯鷹捕食行為的智能優化算法,主要由搜索階段、搜索與開發的轉換和開發階段三部分組成。

2.3.1 搜索階段

哈里斯鷹隨機棲息在某個地方,通過2種策略找到獵物,可表示為:

X(τ+1)=

(12)

在式(12)中,X(τ)和X(τ+1)分別為當前和下一次迭代時個體的位置,τ為迭代次數,Xrand(τ)為隨機選出的個體位置,Xrabbit(τ)為獵物位置,即擁有最優適應度的個體位置,r1～r4和q都是[0,1]之間的隨機數,q用于隨機選擇要采用的策略,Xm(τ)為個體平均位置,表達式為:

(13)

其中,Xk(τ)為種群中第k個個體的位置,M表示種群規模。

2.3.2 搜索與開發的轉換

HHO算法根據獵物的逃逸能量在搜索和不同的開發行為之間轉換,逃逸能量定義為:

(14)

其中,E0是獵物的初始能量,為[-1,1]之間的隨機數,每次迭代時自動更新,τ為迭代次數,T為最大迭代次數。當|E|≥1時,進入搜索階段;當|E|<1時,進入開發階段。

2.3.3 開發階段

定義r為[0,1]之間的隨機數,用于選擇不同的開發策略。

當0.5≤|E|<1且r≥0.5時,采取軟圍攻策略進行位置更新:

X(τ+1)=ΔX(τ)-E|JXrabbit(τ)-X(τ)|

(15)

其中,ΔX(τ)=Xrabbit(τ)-X(τ)表示獵物位置與個體當前位置的差值,J為[0,2]之間的隨機數。

當|E|<0.5且r≥0.5時,采取硬圍攻策略進行位置更新:

X(τ+1)=Xrabbit(τ)-E|ΔX(τ)|

(16)

當0.5≤|E|<1且r<0.5時,采取漸近式快速俯沖的軟包圍策略進行位置更新:

(17)

Y=Xrabbit(τ)-E|JXrabbit(τ)-X(τ)|

(18)

Z=Y+S×LF(2)

(19)

其中,f(·)為適應度函數,S為二維隨機向量,其中元素為[0,1]之間的隨機數,LF(·)是萊維飛行的數學表達式。

當|E|<0.5且r<0.5時,采取漸近式快速俯沖的硬包圍策略進行位置更新:

(20)

Y=Xrabbit(τ)-E|JXrabbit(τ)-Xm(τ)|

(21)

Z=Y+S×LF(2)

(22)

2.4 基于IHHO算法的TDOA定位

使用IHHO算法進行TDOA定位的具體步驟如下:

步驟1種群初始化。根據搜索空間每一維的上界和下界,利用式(11)初始化每個個體,然后利用Chan算法計算一個初始解隨機代替種群中的一個個體。

步驟2計算初始適應度。利用式(9)計算所有個體的適應度值,將適應度最優的個體位置設為當前獵物位置。

步驟3位置更新。通過式(14)更新獵物逃逸能量,然后根據逃逸能量和生成的隨機數執行搜索或開發行為中對應的位置更新策略。

步驟4計算適應度。通過式(9)計算位置更新后的個體適應度,并與獵物適應度值進行比較,若位置更新后的個體適應度值優于獵物,則以適應度值更優的個體位置作為新的獵物位置。

重復步驟3和步驟4,當算法迭代次數達到最大迭代次數時,輸出當前獵物位置作為目標的估計位置。

3 仿真與結果分析

本文在Matlab 2018b環境下對IHHO算法進行定位性能仿真測試,并與帶有變異機制的動態哈里斯鷹優化算法(Dynamic Harris Hawks Optimization algorithm with Mutation Mechanism,DHHO/M)[17]、增強鯨魚優化算法(Enhanced Whale Optimization Algorithm,EWOA)[19]、通過競爭選擇改進的蟻獅優化算法(Improved AntLion Optimizer algorithm via Tournament Selection,IALOT)[20]以及混沌樽海鞘群算法(Chaotic Salp Swarm Algorithm,CSSA)[21]進行比較。

仿真場景和參數設置如下:在20 m×20 m的范圍內部署8個基站,基站坐標分別為(0,0)、(0,10)、(0,20)、(10,20)、(20,20)、(20,10)、(20,0)、(10,0),1 000個測試點均勻分布在定位場景內,搜索空間上界ub=[20,20],下界lb=[0,0],最大迭代次數T=60。選取均方根誤差(Root Mean Square Error,RMSE)作為定位精度評價指標:

(23)

(24)

(25)

(26)

其中,trace(·)函數用于求矩陣的跡,σr為距離噪聲標準差,(x,y)和(xi,yi)分別為標簽和基站i的坐標,ri為標簽到基站i的距離,i=1,2,…,N,N為基站數量。

3.1 定位精度分析

將種群規模M設為30,基站數量N設為8,考慮實際室內定位系統的測距精度,將距離噪聲標準差σr的值設定在0.1 m～1.0 m范圍內進行實驗,得到不同距離噪聲標準差下的定位精度,如表1所示。可以看出,隨著距離噪聲標準差的增大,不同算法的RMSE和CRLB都逐漸增大,而本文提出的IHHO算法在不同的距離噪聲標準差環境下都取得了更低的定位誤差,RMSE相比其他算法更接近CRLB,具有較高的定位精度。

表1 不同距離噪聲標準差下的定位精度比較Table 1 Localization accuracy comparison underdifferent distance noise standard deviation m

在距離噪聲標準差σr為0.5 m的條件下,分析基站數量對定位效果的影響,分別在4個～8個基站參與定位的情況下進行實驗,得到不同基站數量的定位精度,如表2所示。可以看出,不同算法的RMSE和CRLB隨著基站數量增加而減小,在不同基站數量情況下,IHHO算法都達到了較低的RMSE,相比其他算法更接近CRLB。當基站數量由4個逐漸增加到8個時,IHHO算法的RMSE相比DHHO/M算法分別減小了2.79%、10.07%、10.56%、13.92%和16.87%,RMSE減小的比例隨著基站數量增加而增大,與EWOA、IALOT和CSSA算法對比也可以得出同樣的結論,這說明IHHO算法可以更充分地利用測量值的冗余來減小定位誤差,在基站數量較多的高精度定位場景中具有更好的定位性能。

表2 不同基站數量下的定位精度比較Table 2 Localization accuracy comparison underdifferent number of base stations m

3.2 收斂性能分析

智能優化算法需要一定的種群規模和迭代次數來完成全局最優解的搜索。收斂能力好的智能優化算法可以在較小種群規模或較少迭代次數的條件下完成收斂,降低計算量。在N=8、σr=0.5 m的條件下,改變種群規模M進行實驗,得到RMSE與種群規模的關系,如圖2所示。可以看出,EWOA算法的RMSE在種群規模達到25以上時不再顯著下降,DHHO/M和IALOT算法的RMSE在種群規模達到15以上時趨于穩定,CSSA和IHHO算法可以在M=5的條件下完成位置解算,定位精度對種群規模不敏感。IHHO算法由于引入了初始解,使種群個體可以迅速集中到全局最優解附近進行搜索,因此提高了尋優效率。

圖2 RMSE與種群規模的關系Fig.2 Relationship between RMSE and population size

將種群規模M設為30,在迭代次數不斷增加的情況下,比較不同算法適應度值和RMSE的收斂情況,各算法適應度值和RMSE與迭代次數的關系如圖3和圖4所示。

圖3 適應度值與迭代次數的關系Fig.3 Relationship between fitness value and iteration time

圖4 RMSE與迭代次數的關系Fig.4 Relationship between RMSE and iteration time

可以看出,適應度值和RMSE都隨著迭代次數的增加呈降低趨勢,然后逐漸趨于穩定。DHHO/M、EWOA、IALOT和CSSA算法由于都采用基于最大似然估計的適應度函數,在達到最大迭代次數后得到的定位效果比較接近。IHHO算法由于采用了改進的適應度函數,可以對個體位置優劣做出更準確的評價,使算法可以收斂到更小的適應度值,并計算出RMSE更小的定位結果。CSSA算法在每次迭代中都保有一部分個體不隨機運動,降低了種群總體的隨機性,導致收斂速度較慢。DHHO/M、EWOA和IALOT算法由于前期要在整個二維空間做充分的全局搜索,因此需要較多次迭代才能完成收斂。IHHO算法通過引入初始解簡化全局搜索的步驟,使適應度值和RMSE有一個較小的初始值,可以通過較少的迭代次數計算出目標的位置,克服了智能優化算法需要多次迭代的缺點。

4 結束語

本文設計一種改進的哈里斯鷹優化算法用于TDOA定位的非線性問題求解,并對初始種群和適應度函數進行優化。與其他智能優化算法的定位性能比較結果表明,改進的哈里斯鷹優化算法具有定位精度高、收斂速度快的優勢。下一步將把該算法應用于到達時差-到達角度聯合定位,進一步提升定位精度。