基于改進樽海鞘群算法的到達時間差定位

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

(1. 上海大學特種光纖與光接入網(wǎng)重點實驗室, 上海 200444; 2. 上海物聯(lián)網(wǎng)有限公司, 上海 201899;3. 華東師范大學軟件工程學院, 上海 200062)

隨著通信和定位技術(shù)的迅速發(fā)展, 單一的定位導(dǎo)航正在向監(jiān)控、交通、救助、娛樂等綜合位置服務(wù)轉(zhuǎn)化, 位置服務(wù)作為新興產(chǎn)業(yè), 在人們的日常生活中起到了重要作用. 在室內(nèi)環(huán)境下,GPS 信號容易被遮擋, 無法實現(xiàn)精確可靠的定位[1], 而室內(nèi)定位技術(shù)可以彌補這一不足. 近年來, 國內(nèi)外學者對室內(nèi)定位技術(shù)進行了大量研究, 其中到達時間差(time difference of arrival,TDOA)定位方式憑借其定位精度高、系統(tǒng)復(fù)雜度低的優(yōu)勢, 成為室內(nèi)定位的一個重要實現(xiàn)手段.

TDOA 定位方式不要求基站與移動臺之間的時間同步, 但需要基站之間保持嚴格的時間同步. WiFi、藍牙、Zigbee 等無線通信技術(shù)無法實現(xiàn)較高的時間分辨率, 超聲波信號穿透能力較弱, 不適合復(fù)雜多變的室內(nèi)環(huán)境. 超寬帶(ultra wide band, UWB)技術(shù)通過發(fā)送納秒或皮秒級的極窄脈沖來傳輸數(shù)據(jù), 具有小于1 ns 的時間分辨率, 可以達到厘米級的理論測距精度, 同時在穿透性和抗多徑方面也有良好的表現(xiàn), 適合用于高精度室內(nèi)定位[2].

TDOA 定位可以轉(zhuǎn)換為非線性雙曲線方程求解問題, 目前已有很多算法可以完成位置解算. 傳統(tǒng)算法中泰勒級數(shù)展開法[3]需要一個接近真實位置的坐標作為初始值以保證算法收斂.Chan 算法[4]忽略了噪聲二次項, 在噪聲方差較大時性能會有所下降. 擴展卡爾曼濾波[5]將非線性系統(tǒng)作線性近似處理, 然后進行跟蹤濾波, 但定位精度容易受實際環(huán)境中的未知信道參數(shù)影響. 兩步最小二乘法[6]、加權(quán)最小二乘法[7]等算法在最小二乘法的基礎(chǔ)上進行改進, 適用于測量誤差較小的情況, 但當誤差大于一定值時定位精度會顯著下降.

除了上述解析算法, 元啟發(fā)式算法也被應(yīng)用于TDOA 定位. 王生亮等[8]提出改進的自適應(yīng)遺傳算法, 在設(shè)計自適應(yīng)交叉率和變異率時考慮種群隨進化代數(shù)的整體變化, 并考慮了每代種群個體適應(yīng)度的作用, 引入最優(yōu)保存策略來保護優(yōu)秀個體. Yue 等[9]提出混沌粒子群算法, 利用混沌序列對粒子群優(yōu)化算法施加擾動, 使算法可以跳出局部最優(yōu)解, 從而達到全局最優(yōu)解. 陳濤等[10]將樽海鞘群算法(salp swarm algorithm, SSA)引入TDOA 定位, 取得了比傳統(tǒng)粒子群優(yōu)化算法更高的定位精度. 王夢馨[11]在SSA 中引入領(lǐng)導(dǎo)者數(shù)量隨迭代次數(shù)衰減的動態(tài)模型, 增強群體前期全局搜索能力, 同時后期能保持較好的收斂能力. 根據(jù)NFL(No-Free-Lunch)理論[12]所述, 不存在適用于所有問題的元啟發(fā)式算法, 因此針對TDOA 定位對不同元啟發(fā)式算法進行比較, 有助于找到更適合TDOA 定位問題的算法.

現(xiàn)有的元啟發(fā)式算法應(yīng)用研究聚焦于回避局部最優(yōu)解[13-14]以及搜索和開發(fā)能力的平衡[15-16]. 對于TDOA 定位問題, 在適應(yīng)度函數(shù)方面缺少進一步研究[8-11]. 此外, 由于元啟發(fā)式算法需要較大的種群規(guī)模和較多的迭代次數(shù), 造成計算量較大, 不利于實時位置解算. 本工作針對以上不足, 提出用改進的樽海鞘群算法(improved salp swarm algorithm, ISSA)進行TDOA 室內(nèi)定位, 通過引入主基站選擇對適應(yīng)度函數(shù)進行改進, 提高算法尋優(yōu)精度, 并在此基礎(chǔ)上引入近似解和自適應(yīng)跟隨策略, 分別加快了算法前期和后期的收斂速度. 將提出的ISSA與其他元啟發(fā)式算法[17-20]進行定位性能仿真比較, 結(jié)果表明, 采用ISSA 進行室內(nèi)TDOA 定位可以取得更高的定位精度和更快的收斂速度.

1 TDOA 定位模型

TDOA 定位幾何模型如圖1 所示, 在2 維平面中部署N個不同位置的基站, 移動臺周期性地向基站發(fā)送無線定位信號. 基站i的定位信號到達時間為

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

式中:i= 1,2,··· ,N; ˙ti為信號到達時間真實值;eti為到達時間誤差, 服從均值為零的高斯分布. 通過測量定位信號從移動臺到達兩個基站的傳播時間差, 再將其乘以電磁波傳播速度c,可以得到移動臺到兩個基站之間的固定距離差. 定義ri為移動臺到基站i的距離,ri,j為移動臺到基站i和基站j的距離差測量值, 則

式中:i,j= 1,2,··· ,N,i ／=j; (x,y) 為未知移動臺坐標; (xi,yi) 為基站i的已知坐標;eri=ceti為測距誤差, 服從均值為0、標準差為σr的高斯分布. 根據(jù)移動臺到兩個基站的距離差可以確定一條雙曲線, 利用多個基站建立雙曲線方程組, 再通過數(shù)學方法求解即可算出未知移動臺的坐標.

定義基站1 為主基站, 其他基站為輔基站. 將信號到達主基站與各個輔基站的時間差乘以電磁波傳播速度c, 得到N-1 個距離差測量值為

當非線性函數(shù)取最小值時, 得到移動臺坐標的估計值, 用解析法求解較為困難, 本工作采用樽海鞘群算法求解. 根據(jù)式(6)推導(dǎo)出評價算法中個體優(yōu)劣程度的適應(yīng)度函數(shù)為

式中:X為樽海鞘個體的位置向量. 適應(yīng)度取值越小代表估計位置越接近真實位置.

2 樽海鞘群算法

樽海鞘是一種海洋生物, 具有透明的桶形身體, 通過吸入噴出海水進行移動. 樽海鞘群體經(jīng)常形成被稱為樽海鞘鏈的鏈狀結(jié)構(gòu), 這種結(jié)構(gòu)可以幫助樽海鞘實現(xiàn)快速協(xié)調(diào)移動和覓食. 樽海鞘鏈由領(lǐng)導(dǎo)者和追隨者組成, 領(lǐng)導(dǎo)者位于樽海鞘鏈的最前端, 其他個體則為追隨者, 朝著前一個樽海鞘的方向移動.

2017 年, Mirjalili 等[17]受樽海鞘的群體行為特征啟發(fā), 建立樽海鞘鏈的數(shù)學模型, 提出SSA 來解決優(yōu)化問題, 該算法具有計算量小、不易陷入局部最優(yōu)的優(yōu)點.

2.1 種群初始化

在求解優(yōu)化問題時, SSA 首先將樽海鞘種群位置在限定范圍內(nèi)隨機初始化,

2.2 領(lǐng)導(dǎo)者位置更新

由于優(yōu)化問題的全局最優(yōu)是未知的, 只能將當前搜索到的最優(yōu)位置作為食物位置, 并在搜索過程中不斷更新食物位置. 領(lǐng)導(dǎo)者在食物位置附近進行搜索開發(fā), 引導(dǎo)整個種群的移動, 位置更新公式為

式中:Xij為第i個樽海鞘的第j維位置,j= 1,2;Fj是食物的第j維位置;ubj和lbj分別是第j維位置的上、下界;c2和c3都是[0,1]之間的隨機數(shù), 保證了領(lǐng)導(dǎo)者移動的隨機性;c1為收斂因子, 負責平衡迭代過程中的搜索與開發(fā)能力. 當收斂因子大于1 時, 進行全局搜索; 當收斂因子小于1 時, 進行局部開發(fā). 通常c1的取值為一個隨迭代次數(shù)遞減的函數(shù). 根據(jù)文獻[17],收斂因子為

式中:τ為當前迭代次數(shù);T為最大迭代次數(shù). 為了權(quán)衡SSA 的隨機性與穩(wěn)定性, 選取50%樽海鞘作為領(lǐng)導(dǎo)者.

2.3 追隨者位置更新

在SSA 中, 追隨者依據(jù)前一個樽海鞘個體的位置進行移動, 該運動方式符合牛頓運動定律,

3 改進樽海鞘群算法

3.1 改進的適應(yīng)度函數(shù)

適應(yīng)度函數(shù)的選取對最終的尋優(yōu)精度有直接影響. 觀察式(4)可以發(fā)現(xiàn), 將主基站信號到達時間t1作為距離差測量值的公共項, 可以對式(7)中的所有平方項產(chǎn)生影響, 而第i個輔基站信號到達時間ti(i=2,3,··· ,N)只會影響式(7)的第i-1 個平方項, 這會導(dǎo)致適應(yīng)度函數(shù)對主基站的測量值相對敏感, 當主基站的測距誤差er1顯著大于或小于輔基站的測距誤差eri時, 適應(yīng)度函數(shù)的最小值會顯著增大. 此時, 可以通過尋找一個最優(yōu)主基站以減小適應(yīng)度函數(shù)的最小值. 定義基站j為主基站時的適應(yīng)度函數(shù)為

式中:j ∈{1,2,··· ,N},i ／=j. 對于不同的主基站, 分別通過最大似然估計計算適應(yīng)度函數(shù),然后選取其中的最小值作為改進的適應(yīng)度函數(shù), 代入方程求解,

3.2 近似解引入

初始種群的位置分布會影響算法的收斂速度, 在沒有任何先驗知識的前提下, 大部分元啟發(fā)式算法的初始種群都采用隨機生成. 為了避免陷入局部最優(yōu), 算法在前期需要對整個搜索空間進行充分的全局搜索, 然后逐步縮小搜索范圍, 轉(zhuǎn)入局部開發(fā), 在一定程度上浪費了計算資源. 本工作提出通過運算量較小的最小二乘法[21]計算一個近似解,

式中:

其中(xi,yi)為基站i的坐標,i=1,2,··· ,N,N為基站數(shù)量,ki=x2i+y2i,rj,1為距離差測量值,j= 2,3,··· ,N. 從初始種群中隨機抽取一個個體用近似解XLS替換, 得到改進后的初始種群. 由于近似解位置與目標位置比較接近, 擁有較優(yōu)的適應(yīng)度值, 對種群起到很好的引導(dǎo)作用, 使全局搜索的步驟得到簡化, 從而加快算法前期收斂速度. 另外, 調(diào)整收斂因子c1的衰減規(guī)律, 能加快c1的前期下降速度, 使算法更快地從全局搜索轉(zhuǎn)入局部開發(fā),

式中:τ為當前迭代次數(shù).

3.3 自適應(yīng)跟隨策略

追隨者的順次跟隨移動使SSA 保有一部分個體不隨機運動, 降低了算法陷入局部最優(yōu)的概率. 但這種盲目跟隨的位置更新策略不能保證追隨者朝著更優(yōu)的個體位置移動, 這會限制局部開發(fā)效率,導(dǎo)致后期食物的適應(yīng)度值下降緩慢.因此本工作提出自適應(yīng)跟隨策略,當?shù)趇-1 個樽海鞘的適應(yīng)度值優(yōu)于第i個樽海鞘時, 按照式(14)進行追隨者位置更新, 否則追隨者將向食物方向運動, 采用下式實現(xiàn)這個過程:

式中:f(·)為適應(yīng)度函數(shù). 采用該策略可以保證追隨者始終跟隨適應(yīng)度更優(yōu)的個體移動, 避免盲目跟隨, 提高局部開發(fā)效率, 加快算法后期收斂速度.

3.4 算法步驟

基于ISSA 的TDOA 定位具體步驟如下.

(1)種群初始化. 確定搜索空間各個維度變化范圍的上界和下界, 利用式(9)初始化種群.

(2)引入近似解. 采用最小二乘法計算近似解并隨機替換種群中的一個個體.

(3)選定食物、領(lǐng)導(dǎo)者、追隨者. 利用式(16)計算每個樽海鞘個體的適應(yīng)度值, 然后將樽海鞘種群按適應(yīng)度升序排序, 排在首位的適應(yīng)度最優(yōu)的個體位置作為當前食物位置. 排在前50%的個體設(shè)為領(lǐng)導(dǎo)者, 其余個體為追隨者.

(4)領(lǐng)導(dǎo)者和追隨者位置更新. 根據(jù)式(10)和(23)分別更新領(lǐng)導(dǎo)者和追隨者位置.

(5)食物位置更新. 通過式(16)計算位置更新后個體的適應(yīng)度, 并與當前食物適應(yīng)度值進行比較, 若更新后個體的適應(yīng)度值優(yōu)于食物適應(yīng)度值, 則將適應(yīng)度值更優(yōu)的樽海鞘個體位置作為新的食物位置.

重復(fù)步驟(4)和步驟(5), 當達到最大迭代次數(shù)時, 輸出當前食物坐標作為目標的估計位置.ISSA 定位流程圖如圖2 所示.

圖2 改進樽海鞘群算法定位流程圖Fig.2 Flowchart of localization based on ISSA

4 定位性能仿真

為了驗證本工作提出的ISSA 對室內(nèi)TDOA 定位的有效性, 將ISSA 與傳統(tǒng)樽海鞘群算法(SSA)[17]、蟻獅優(yōu)化(ant lion optimization, ALO)算法[18]、鯨魚優(yōu)化算法(whale optimization algorithm, WOA)[19]、哈里斯鷹優(yōu)化(Harris hawk optimization, HHO)算法[20]進行比較.仿真實驗的軟件平臺為Matlab 2016b. 硬件平臺: 處理器為Intel (R) Core(TM) i5-7300HQ,頻率2.5 GHz, 內(nèi)存8 GB.

定位場景和仿真參數(shù)設(shè)置如下: 在20 m×20 m 的平面內(nèi)部署8 個基站, 坐標分別為(0, 0)、(0, 20)、(20, 20)、(20, 0)、(0, 10)、(20, 10)、(10, 20)、(10, 0), 定位場景內(nèi)隨機生成1 000 個測試點, 搜索空間的上界ub= [20 20], 下界lb= [0 0], 種群規(guī)模M= 30, 最大迭代次數(shù)T= 60. 測距誤差服從均值為0、標準差為σr的高斯分布. 采用均方根誤差(root mean square error, RMSE)作為定位精度的評價指標,

式(25)～(27)中: trace(·)函數(shù)的作用為矩陣求跡;Q為協(xié)方差矩陣;σr為測距誤差的標準差;(x,y)和(xi,yi)分別為移動臺和基站i的坐標;ri為移動臺到基站i的距離,i= 1,2,··· ,N,N為基站數(shù)量.

雖然UWB 技術(shù)的理論測距精度為厘米級, 但實際應(yīng)用中由于發(fā)送/接收天線延時、移動臺運動等因素, 測距精度無法做到厘米級, 根據(jù)文獻[22-23]的實測數(shù)據(jù), 測距誤差的標準差為分米級. 故將仿真參數(shù)σr的值設(shè)定為0.1～0.8 m, 在定位基站數(shù)量N=8 的條件下進行實驗,得到不同算法的RMSE 與測距誤差標準差的關(guān)系, 如表1 所示. 隨著測距誤差標準差的增大,所有算法的RMSE 逐漸增大, 并逐漸偏離CRLB. ALO 算法、HHO 算法、SSA 的定位誤差比較接近, WOA 的定位誤差相對較大. 本工作提出的ISSA 在不同σr值下都取得了較高的定位精度, RMSE 比其他元啟發(fā)式算法更接近CRLB.

表1 RMSE 與測距誤差標準差的關(guān)系Table 1 Relationship between RMSE and standard deviation of ranging error m

為了測試算法在不同基站數(shù)量下的定位精度, 在σr為0.3 m 的條件下, 分別對N取4～8的情況進行仿真實驗, 得到不同算法的RMSE 與基站數(shù)量的關(guān)系, 如表2 所示. 基站數(shù)量越多, 各算法的RMSE 越小. ISSA 在不同基站數(shù)量下都實現(xiàn)了較低的定位誤差, RMSE 相比其他元啟發(fā)式算法更接近CRLB. 當基站由4 個增加到8 個時, ISSA 的RMSE 相比SSA 分別減小4.89%、8.88%、10.44%、12.08%、16.44%, 在多基站定位場景中優(yōu)勢更明顯, 這是因為基站數(shù)量越多, 選擇最優(yōu)主基站對適應(yīng)度函數(shù)的改進越顯著, 所以ISSA 更適合存在冗余基站的高精度定位場景.

表2 RMSE 與基站數(shù)量的關(guān)系Table 2 Relationship between RMSE and number of base stations m

在N=8、σr為0.3 m 的條件下進行實驗, 為了比較不同算法的收斂能力, 將每次迭代后的估計位置代入式(24), 得到RMSE 隨迭代次數(shù)增加而逐步減小并趨于收斂的曲線(見圖3).圖3(a)為不同SSA 的收斂能力比較, 傳統(tǒng)SSA 由于只有領(lǐng)導(dǎo)者參與隨機運動, 而追隨者缺少評價跟隨目標優(yōu)劣的機制, 導(dǎo)致整體收斂速度較慢. SSA2 為引入近似解的SSA, 由于近似解與真實位置比較接近, 使RMSE 有一個較低的初值, 可以更好地引導(dǎo)種群接近目標位置, 但RMSE 在低于一定值后下降速度趨緩. SSA3 在SSA2 的基礎(chǔ)上引入自適應(yīng)跟隨策略, 使追隨者始終朝適應(yīng)度較優(yōu)的個體方向移動, 解決了RMSE 后期下降緩慢的問題. ISSA 在SSA3 的基礎(chǔ)上引入主基站選擇改進適應(yīng)度函數(shù), 使算法可以收斂到更低的RMSE, 定位精度更高.

圖3(b)為不同元啟發(fā)式算法的收斂能力比較, ALO 算法、WOA、HHO 算法雖然前期收斂速度快于SSA, 但由于初期需要對整個搜索空間進行充分的全局搜索, 仍需要多次迭代才能完成尋優(yōu)工作. ISSA 的定位精度和收斂速度均優(yōu)于其他算法. 定義算法完成收斂的判決條件為經(jīng)過5 次迭代后RMSE 的改善小于0.001 m,

圖3 不同算法收斂能力比較Fig.3 Comparison of convergence ability of different algorithms

式中:τ為完成收斂所需的迭代次數(shù), 5＜τ≤T. 保持仿真參數(shù)不變, 根據(jù)式(28)可以得到ALO 算法、WOA、HHO 算法、SSA、ISSA 完成收斂所需的迭代次數(shù)分別為20、24、45、42、12.表3 比較了不同最大迭代次數(shù)情況下各種算法的RMSE 和平均定位用時. 所有算法在達到收斂后, RMSE 不再隨迭代次數(shù)的增加而明顯下降. 當T= 60 時, ALO 算法、HHO 算法的平均定位用時長于SSA、WOA, 但WOA 定位精度較低. ISSA 在近似解和適應(yīng)度函數(shù)方面相比SSA 增加了一定的計算量, 定位用時有所增加, 但ISSA 在實現(xiàn)高精度的同時, 需要的迭代次數(shù)最少, 可以通過設(shè)置較小的最大迭代次數(shù)實現(xiàn)最少的定位用時, 彌補了元啟發(fā)式算法經(jīng)過多次迭代才能收斂的缺點, 對于實現(xiàn)多用戶的高頻實時位置解算具有實際意義.

表3 RMSE 與平均定位用時比較Table 3 Comparison of RMSE and average localization time

5 結(jié)束語

本工作提出一種改進的樽海鞘群算法(ISSA), 并將其用于TDOA 定位問題. 通過選擇最優(yōu)主基站改進適應(yīng)度函數(shù), 提高了搜索精度, 并引入近似解和自適應(yīng)跟隨策略, 分別加快了算法前期和后期收斂速度. 與其他元啟發(fā)式算法的定位性能仿真比較結(jié)果表明, ISSA 擁有更高的定位精度和更快的收斂速度, 彌補了元啟發(fā)式算法運算量大的缺點, 對室內(nèi)高精度實時定位算法的研究有一定參考價值.