馬一鳴,石志東,趙 康,貢常磊,單聯(lián)海

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

0 概述

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

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

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

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

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

1 TDOA定位模型

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

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

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

(1)

ri+nri-rj-nrj

(2)

(3)

nri=cnti

(4)

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

2 改進的哈里斯鷹優(yōu)化算法

2.1 改進的適應度函數

(5)

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

(6)

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

(7)

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

定義基站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]之間的隨機數。

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

2.3 哈里斯鷹優(yōu)化算法

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

2.3.1 搜索階段

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

X(τ+1)=

(12)

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

(13)

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

2.3.2 搜索與開發(fā)的轉換

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

(14)

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

2.3.3 開發(fā)階段

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

當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)計算所有個體的適應度值,將適應度最優(yōu)的個體位置設為當前獵物位置。

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

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

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

3 仿真與結果分析

本文在Matlab 2018b環(huán)境下對IHHO算法進行定位性能仿真測試,并與帶有變異機制的動態(tài)哈里斯鷹優(yōu)化算法(Dynamic Harris Hawks Optimization algorithm with Mutation Mechanism,DHHO/M)[17]、增強鯨魚優(yōu)化算法(Enhanced Whale Optimization Algorithm,EWOA)[19]、通過競爭選擇改進的蟻獅優(yōu)化算法(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 定位精度分析

將種群規(guī)模M設為30,基站數量N設為8,考慮實際室內定位系統(tǒng)的測距精度,將距離噪聲標準差σr的值設定在0.1 m～1.0 m范圍內進行實驗,得到不同距離噪聲標準差下的定位精度,如表1所示?？梢钥闯?隨著距離噪聲標準差的增大,不同算法的RMSE和CRLB都逐漸增大,而本文提出的IHHO算法在不同的距離噪聲標準差環(huán)境下都取得了更低的定位誤差,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 收斂性能分析

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

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

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

4 結束語

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