基于多策略蜜獾算法的TDOA定位

張 岳,蒲紅平*,陳 偉

(1.四川輕化工大學,四川 宜賓 644000;2.人工智能四川省重點實驗室,四川 宜賓 643000)

0 引言

隨著無線傳感器網絡的發展,大規模物聯網已逐漸成型,人們在日常生活中對基于位置服務的需求變多。全球導航衛星系統(Global Navigation Satellite System,GNSS)的定位性能在室外環境下非常可靠和準確,能充分滿足人們的室外定位需求。室內環境或高樓大廈之間的狹窄空間會導致GNSS定位精度下降,無法提供可靠信息,室內定位技術難以依賴GNSS實現。因此,對提高室內定位技術的性能和精確度的研究是非常重要的。室內定位算法可分為測距算法和非測距算法。非測距算法無需額外設備,通過接收和處理來自環境中已有的無線信號,定位精度較低。測距算法通過測量物體與基站之間的距離來確定其位置。測距算法可以分為到達時間、到達時間差、到達角度等。

到達時間差定位算法(Time Difference of Arrival, TDOA)是一種基于信號傳播的測距算法,通過比較不同基站接收到信號的時間差來計算距離。該算法無需基站和移動臺時間同步,僅需基站間同步,降低了信號源與各個基站之間的時間同步要求,定位精度更高[1]。TDOA本質上是求解雙曲線方程組的問題,求解方法分為線性求解和非線性求解2種。Chan氏算法、Taylor算法是傳統的線性求解方法,Chan氏算法在測量誤差服從高斯分布時定位效果較好,但在實際環境中非視距誤差影響下,Chan算法的定位效果不佳[2]。Taylor級數展開的定位算法需要一個與實際位置相近的展開點增加算法的收斂性,對初始值要求較高[3]。粒子群算法、模擬退火、鯨魚算法、哈里斯鷹算法等智能優化算法應用于TDOA定位,是將非線性求解的定位問題轉化成智能優化問題,目標是尋找最優解。智能優化算法在搜索范圍內初始化大量隨機點,通過建立自適應函數評估隨機點和測量值之間的評價體系,通過迭代搜索過程在全局空間中尋找隨機點,進而得到定位目標位置。王田等[4]為了實現算法的局部搜索能力與全局搜索能力的平衡,將免疫過程融入自適應粒子群算法,解決粒子容易陷入局部最優的問題,可以使算法能快速地收斂到全局最優解。李繼明等[5]為了減少非視距環境導致的TDOA定位精度下降,通過信息熵和輪盤賭的改進鯨魚算法,同時將改進的鯨魚算法和泰勒級數展開算法相結合,進一步縮減誤差。唐菁敏等[6]為解決利用時差定位計算困難的問題,通過烏鴉搜索算法設計一種自適應感應概率模型,既保留了算法的優良特性,又避免了算法陷入局部最優,從而提升了算法的收斂速度。Dong等[7]為了降低隨機誤差對定位精度的影響,在麻雀搜索算法的基礎上,引入兩步加權最小二乘算法,搜索邊界自適應調整,生產者-拾荒者數量自適應調整。蜜獾算法(Honey Badger Algorithm,HBA)是Hashim等[8]在2021年提出的一種新型元啟發智能算法[8],是模仿蜜獾捕食和習性的一種優化算法,模擬蜜獾的挖掘和尋找蜂蜜等動態搜索行為的靈活和高效特點,具有較好的應用前景和學術價值[9-10]。但蜜獾算法全局開發能力較弱,在較復雜的優化問題中容易陷入局部最優。本文在文獻[4-7]的基礎上,為解決TDOA定位算法非視距環境中誤差較大的問題,提出多策略改進蜜獾算法并和Taylor級數展開算法結合,增強了蜜獾算法的局部探索能力與全局搜索能力,同時利用Taylor級數展開算法進行進一步迭代,減小定位誤差。

1 TDOA定位

TDOA定位是以無線信號傳播時間為基礎的定位方式,首先固定1個基站為主機站,設備向多個基站發送信號,基站接收信號后,計算信號到達時間,利用空氣中信號傳播速度的一致性,可以得到到達主基站和其他基站之間的距離差。通過距離差可以得到雙曲線方程組,對非線性方程組求解可以得到定位信息,如圖1所示,BS1為主機站,M為定位點[1],式(1)—(2)為理想狀態下的TDOA定位模型。

(1)

圖1 TDOA定位原理

c(tr-t1)=Rr,1=Rr-R1

(2)

其中,(x,y)為定位目標坐標;(xr,yr)為定位基站坐標;Rr,1為各基站到固定基站的距離差;i為基站個數;c為電磁波傳播速度。

2 變異的蜜獾算法

蜜獾算法是根據自然界中蜜獾挖掘和尋找蜂蜜的動態行為,提出的一種新型元啟發式搜索算法,具有實驗效果好和結構簡單的優點。蜜獾算法分為2種模式,通過狂嗅到達食物源進行挖掘食物的挖掘模式和通過跟著向導鳥尋到食物源的采蜜模式[8]。

2.1 改進的初始化種群

傳統的種群初始化是通過公式隨機產生,無法確保初始種群的均勻分布,導致搜尋不充分使算法搜索能力變低。本文引入Tent混沌映射進行種群初始化,通過混沌函數產生混沌序列,以相應的公式轉化到搜索空間,增加種群的隨機性和遍歷性,提高算法的優化速度和求解能力,Tent映射公式如式(3)—(4)所示。

(3)

x=lb+(ub-lb)xn+1

(4)

其中,α為混沌參數;lb和ub為種群的上限和下限。

Tent混沌映射與隨機生成的初始種群在200次迭代下生成的效果對比如圖2所示。

圖2 Tent混沌映射與隨機產生種群對比

蜜獾的嗅覺強度Ii與獵物的集中強度S、獵物和蜜獾的距離di有關,定義公式如式(5)—(7)所示。

(5)

S=(xi-xi+1)2

(6)

di=xprey-xi

(7)

密度因子是蜜獾算法中一個關鍵參數,影響著算法的搜索能力和收斂速度。蜜獾算法的密度因子定義如式(8)所示。

(8)

其中,tmax為迭代最大次數;C為一個大于1的常數,一般設置為2。

2.2 引入正余弦策略位置更新

正余弦策略是通過利用正余弦函數的數學性質,通過正余弦模型震蕩變化的特性對粒子位置擾動,維持個體多樣性,提高算法的全局搜索能力[11],如式(9)所示。

(9)

(10)

其中,η為大于等于1的調節系數;a=1;r1為控制參數,控制正余弦函數的振幅;r2為隨機數,實現正弦方式或余弦方式的位置更新。

在挖掘階段,蜜獾運動范圍類似心形,定義如式(11)所示。

xnew=xprey+FβIxprey+Fr3wdi|(cos(2πr4))[1-cos(2πr5)]|xgnew

(11)

其中 ,xprey為當前獵物的全局最優位置;β為蜜獾獲取食物能力;r3,r4,r5∈(0,1)的隨機數;F為可以搜索方向的標志,定義如式(12)所示。

(12)

其中,r6∈(0,1)內的隨機數。在挖掘階段,蜜獾對嗅覺強度Ii、與獵物之間的距離di、更新密度函數因子w的依賴性很強,同時挖掘期間會受F的干擾,以便找到更好的獵物位置。

在采蜜階段向導鳥到達蜂巢情況可以用式(13)表示。

xbest=xprey+Fr7αdi

(13)

其中,xbest為蜜獾的新位置;xprey為獵物的位置;F和di分別由式(12)和式(7)得出;α為更新密度因子。

2.3 融合Levy飛行

采蜜階段是在深度上盡可能地挖掘最優解,但當搜索陷入局部最優時,是對一個局部范圍展開的局部精細化搜索,無法得到全局最優值,本文引入Levy飛行策略。該策略是一種融合大步長和小步長的隨機游走模型,可提升算法的局部搜索能力和維持種群多樣性,防止出現早熟現象。大概率在小步長游走在局部區域進行細致化探索有利于局部開發,小概率出現大步長在搜索空間快速移動,有利于跳出局部最優,增加解的可靠性。

(14)

其中,xprey為食物源;α為步長收縮因子;⊕為*運算;levy(β)為Levy隨機路徑,并且滿足levy～u=t-λ。由于Levy分布情況復雜,常用正太分布求解隨機數的方法進行,生成的隨機步長的方法如式(15)所示。

(15)

2.4 基于改進蜜獾算法的TDOA定位算法

通過上述多種策略改進蜜獾算法,增加了算法的全局探索能力和局部深挖能力。將上述多策略改進的蜜獾算法與TDOA定位算法結合實現定位。改進蜜獾算法與TDOA算法結合的計算流程如圖3所示。

圖3 IHBA-TDOA定位流程

3 基于變異蜜獾算法的TDOA算法

3.1 變異蜜獾算法與Taylor級數展開算法結合

Taylor級數展開算法是基于加權最小二乘法(Weighted Least Square ,WLS)的一種迭代算法,它是通過不斷迭代修正待定位標簽位置的估計值,逐漸逼近標簽真實的位置坐標。Taylor級數展開算法存在初始值設置不穩定、定位效果不佳的問題。改進的蜜獾優化算法所求的定位目標與真實定位目標存在誤差,而Taylor級數展開算法需要先定義一個初始值,因此兩者結合可以進一步減小誤差,將多策略改進的蜜獾算法得到的最優定位結果作為Taylor級數展開算法的初始值,經過Taylor級數展開算法進行層層迭代處理,可以進一步提高定位精度。

假設標簽和基站之間的約束關系可以用函數f(x,y,xi,yi)表示,將利用改進的蜜獾算法得到的測量值作為初始值為(x0,y0),真實坐標為(x,y)

x=x0+Δx

y=y0+Δy

(16)

基于TDOA的定位方法由公式(2)給出,是理想狀態下的雙曲線公式,在存在非視距誤差環境中,則如公式(17)所示。將fi(x,y,xi,yi)在(x0,y0)處進行Taylor展開,忽略二階以上分量。

f(x,y,xi,yi)=c(ti-t1)=Ri-R1+δi

(17)

fi(x,y,xi,yi)=fi(x0,y0,xi,yi)+

(18)

轉化為矩陣形式:

ψ=hi-Giδ

(19)

其中,ψ為誤差矢量;

(20)

(21)

(22)

當αx+αy<η時可以停止迭代。

3.2 多策略改進蜜獾算法與Taylor級數展開算法結合在TDOA定位中的步驟

步驟1:種群初始化,根據Tent混沌映射函數對種群進行初始化。

步驟2:計算初始適應度值,通過基站布置和TDOA測量,構建適應度最優的個體函數。

步驟3 :位置更新,通過多策略改進的蜜獾函數進行位置更新,輸出最新的位置。

步驟4:結合Taylor級數展開算法,將改進的蜜獾算法得到的最優解作為Taylor級數初始值。

步驟5:求解Taylor級數,迭代方法求解Taylor級數,得到標簽位置的估計值。

步驟6:判斷輸出,用迭代過程中位置估計的誤差是否滿足設定的值來判斷接著迭代還是輸出最終位置。

如圖4所示是將改進的蜜獾算法與Taylor級數展開算法相結合的流程。

圖4 IHBA-Taylor混合TDOA定位

4 實驗仿真結果

本文在MATLAB2021b環境下進行多策略改進的蜜獾算法和結合Taylor級數展開算法的性能仿真測試,仿真場景在10 m×10 m的范圍內進行8個基站的設置,基站位置為(0,0)(0,5)(5,0)(0,10)(10,0)(10,10)搜索上界是[10,10],搜索下界是[0,0],基站布局如圖5所示,BS是定位基站。

圖5 基站布局

本文選用均方根誤差(Root Mean Square Error,RMSE)作為評價指標,如式(23)所示。

(23)

其中,(xi,yi)(x,y)分別為i測試點的真實位置和得到的預測位置;m為總測試數,即種群數。

將本文算法與自動設置初始值的Taylor定位算法進行比較,如圖6所示,可以明顯看出本文算法均方根誤差更小,具有優勢。將改進后的蜜獾算法與傳統的蜜獾算法進行仿真測試,如圖7所示,可以看出隨著誤差增加,均方根誤差不斷增大,但是改進后的蜜獾算法表現更好。

圖6 Taylor-IHBA效果對比

圖7 HBA和IHBA效果對比

將本文算法與Chan算法[2]、鯨魚優化算法(Whale Optimication Algorithm,WOA)[5]、麻雀搜索算法(Sparrow Search Algorithm,SSA)[7]、哈里斯鷹優化(Harris Hawk Optimization,HHO)算法[12]、 鼠群優化(Rat Swarm Optimization,RSO)算法[13]進行對比,不同噪聲下均方根誤差數據如表1所示,與其他算法對比,隨著誤差增加均方根誤差的變化如圖8所示,能夠直觀地看出誤差越大,均方根誤差越大。而與其他算法相比,本文算法誤差更小,因此本文的算法在非視距環境下能夠有效抑制誤差對定位的影響,提高定位效果。

表1 不同距離噪音下均方根誤差數據

圖8 多種智能算法對比測試

基站數目也會影響定位的精確度,仿真基站數目從4個到7個對定位算法有影響,由圖9可知,當基站為4個時均方根誤差為29.265,基站為7個時均方根誤差為13.876,明顯得知基站數為7時具有更小的均方根誤差。

圖9 不同基站數的本文算法誤差影響

5 結語

本文提出一種融合多策略優化蜜獾算法與Taylor級數展開算法的TDOA定位策略。通過多種策略對蜜獾算法進行優化,并通過仿真實驗與多組其他定位算法進行對比分析,結果顯示本文提出的算法定位精度較高且誤差較低。