非視距環(huán)境下的超寬帶室內(nèi)定位算法

，

(河海大學(xué) 能源與電氣學(xué)院，南京 211100)

0 引言

近年來(lái)，隨著人們需求的增長(zhǎng)，不論是在工業(yè)領(lǐng)域還以日常生活中，越來(lái)越重視室內(nèi)的精確定位與導(dǎo)航。為了滿(mǎn)足人們?nèi)找嬖鲩L(zhǎng)的需求，國(guó)內(nèi)外研究人員將多種技術(shù)應(yīng)用到室內(nèi)定位領(lǐng)域中，例如紅外傳播技術(shù)、超聲波技術(shù)、射頻識(shí)別技術(shù)(FRID)、Wi-Fi技術(shù)、低功耗藍(lán)牙技術(shù)以及超寬帶技術(shù)[1]。超寬帶技術(shù)(UWB)是近年來(lái)新興的無(wú)線(xiàn)通信技術(shù)，無(wú)需用到傳統(tǒng)通信中的載波，利用納秒級(jí)的極窄脈沖傳輸信息，具有多徑分辨能力強(qiáng)、功耗低、穿透能力強(qiáng)等特點(diǎn)[2]，這些優(yōu)勢(shì)使得超寬帶技術(shù)在室內(nèi)定位領(lǐng)域有較好的發(fā)展前景。UWB定位中基于測(cè)距常用的算法有基于信號(hào)到達(dá)強(qiáng)度(RSSI)、到達(dá)信號(hào)角(AOA)、到達(dá)信號(hào)時(shí)間(TOA)、到達(dá)時(shí)間差(TDOA)等方法[3]。其中最常見(jiàn)的是TDOA算法，在該算法中有兩個(gè)主要的誤差來(lái)源：一是系統(tǒng)測(cè)量值誤差，包括隨機(jī)測(cè)量誤差和時(shí)鐘漂移引起的誤差兩部分，相對(duì)而言對(duì)定位結(jié)果精度的影響不大；另一個(gè)影響較大的誤差是由于信號(hào)在復(fù)雜的室內(nèi)環(huán)境下傳播時(shí)，遇到多種障礙物發(fā)生反射、折射、衍射甚至穿墻而過(guò)，從而引起的非視距(non-line of sight，NLOS)誤差[4]，由于該誤差導(dǎo)致的額外時(shí)延對(duì)最終的定位結(jié)果影響較大，是影響定位精度的主要來(lái)源。因此，減弱非視距誤差對(duì)定位精度的影響是研究超寬帶室內(nèi)定位技術(shù)的重要問(wèn)題。

根據(jù)特定NLOS環(huán)境中的參數(shù)建立均方根時(shí)延擴(kuò)展模型，通過(guò)額外時(shí)延和均方根時(shí)延擴(kuò)展的關(guān)系計(jì)算出額外時(shí)延的參數(shù)，用估計(jì)出的額外時(shí)延參數(shù)來(lái)調(diào)整TDOA定位模型。再將重構(gòu)后的TDOA模型轉(zhuǎn)化為粒子群算法中的適應(yīng)度函數(shù)，從而可利用粒子群算法估計(jì)出精確的目標(biāo)位置。本文提出的優(yōu)化算法可以有效抑制NLOS對(duì)測(cè)量值的影響，提高室內(nèi)定位的精度和算法收斂速度。

1 系統(tǒng)模型建立

1.1 TDOA定位模型的建立與重構(gòu)

(1)

(2)

γ(t)=(1+e)t+ψ

其中，t為理想時(shí)間，e為頻率漂移，ψ為頻率偏差，假設(shè)各基站和目標(biāo)節(jié)點(diǎn)的時(shí)鐘漂移速率保持一致，則基站i和基站1到目標(biāo)節(jié)點(diǎn)的信號(hào)傳播時(shí)間差由于時(shí)鐘漂移引起的誤差表示為：

μei,1=E(τei-τe1)=μei-μe1

(3)

(4)

因此，由以上分析可知式(2)可進(jìn)一步改寫(xiě)為：

(5)

由此，實(shí)現(xiàn)了對(duì)TDOA定位模型的重構(gòu)，為了得出τi,1的值，還需要計(jì)算出超寬帶信號(hào)在NLOS環(huán)境中傳播的誤差τei值。

1.2 延遲拓展參數(shù)的求解

NLOS誤差在不同的信道環(huán)境下服從指數(shù)分布、均勻分布以及Delta分布[6]。選擇延遲拓展按照其中的指數(shù)分布模型來(lái)分析非視距誤差，其概率密度函數(shù)為：

(6)

(7)

(8)

(9)

根據(jù)概率論的知識(shí)，結(jié)合式(6)和式(9)可得延遲拓展誤差τei的概率密度函數(shù) ，其中τi,rms≥0：

由此可得τei的均值和方差分別為：

(10)

(11)

由式(10)、(11)進(jìn)一步可得TDOA測(cè)量模型中的式(3)和式(4)中的參數(shù)：

(12)

(13)

1.3 目標(biāo)函數(shù)的建立

(14)

其中:λ=σ2σ3…σM-1

λ2=σ3σ4…σM-1

λM-1=σ2σ3…σM-2

求解使式(14)的似然函數(shù)值最大的解，相當(dāng)于求解滿(mǎn)足下式最小的解：

(x0,y0)=arg{min[(A-B+C-U)T(A-B+C-U)]}

為了求出此函數(shù)的最小值，用一般的解析法解此類(lèi)非線(xiàn)性函數(shù)比較困難，且有較大誤差，為解決這一難題，本文將一種群智能優(yōu)化算法——粒子群優(yōu)化算法應(yīng)用到最優(yōu)解的求解中，將上式函數(shù)作為粒子群算法中的適應(yīng)度函數(shù)，從而可通過(guò)迭代估計(jì)出目標(biāo)節(jié)點(diǎn)的坐標(biāo)值。

2 基于LS-PSO優(yōu)化的NLOS定位算法

2.1 初始位置的估計(jì)

根據(jù)TDOA數(shù)學(xué)模型式(1)并將其進(jìn)行線(xiàn)性化處理可得：

(15)

(16)

其中:Ri,1=Ri-R1

將上式(15)、(16)相減，得：

(17)

xi,1=xk-x1；yi,1=yk-y1

在式(17)中，將x0，y0，R1當(dāng)作未知變量，那么該式則成為線(xiàn)性方程租，此線(xiàn)性方程組的解則作為目標(biāo)節(jié)點(diǎn)的初始估計(jì)位置。將TDOA測(cè)量值看作實(shí)際值代入到下列式子，采用最小二乘法[8]估計(jì)出的目標(biāo)節(jié)點(diǎn)初始粗略位置為：

其中:

2.2 基于粒子群算法的NLOS定位

粒子群優(yōu)化算法(particle swarm optimization，PSO)是一種群體仿生智能算法，起源于對(duì)鳥(niǎo)群覓食過(guò)程中遷徙和聚集的模擬[9]。算法描述為：在一個(gè)給定的D維區(qū)域中，有N個(gè)粒子組成的群體x=[x1,x2,…,xN]，每一個(gè)粒子都視為潛在解且有自身的位置和速度信息，每個(gè)粒子的位置坐標(biāo)為xi=[xi1,xi2,…,xiD]，速度表示為vi=[vi1,vi2,…,viD]。PSO經(jīng)典算法是在D維空間中隨機(jī)初始化一群粒子，此時(shí)的每個(gè)粒子都視為潛在解，將每個(gè)粒子的位置坐標(biāo)代入適應(yīng)度函數(shù)中，通過(guò)適應(yīng)度函數(shù)值反映每個(gè)粒子的優(yōu)劣情況；在每一次的迭代中，粒子根據(jù)局部最優(yōu)解和全局最優(yōu)解來(lái)更新當(dāng)前的位置和速度，從而在給定區(qū)域內(nèi)運(yùn)動(dòng)，在迭代過(guò)程中群體里的所有粒子會(huì)向著適應(yīng)度值最佳的粒子的方向運(yùn)動(dòng)，直到經(jīng)過(guò)若干次迭代后找到最優(yōu)解；局部最優(yōu)解是指每個(gè)粒子在經(jīng)過(guò)目前的迭代次數(shù)后所找到的自身的最優(yōu)解，可以表示Pbesti=[pi1,pi2,…,piD]，全局最優(yōu)解是指全部粒子在經(jīng)過(guò)目前的迭代次數(shù)后所找到的整個(gè)離子群的最優(yōu)解，可以表示為Gbest=[g1,g2,…,gD]；在經(jīng)過(guò)一次自身最優(yōu)解和群體最優(yōu)解的更新過(guò)后，每個(gè)粒子再將自身目前的速度和位置代入下面兩個(gè)公式更新速度和位置：

vi(t+1)=ω*vi(t)+c1*rand()*(Pbesti-xi(t))+

c2*rand()*(Gbest-xi(t))

xi(t+1)=xi(t)+vi(t+1)

式中，t為當(dāng)前迭代次數(shù)；ω為慣性權(quán)重，其值表示粒子對(duì)目前速度、狀態(tài)的依賴(lài)程度；c1，c2為學(xué)習(xí)因子，取值為2；rand()為服從均勻分布的隨機(jī)數(shù)[9]。

由于粒子群算法隨機(jī)初始化一群粒子，導(dǎo)致其初始收斂速度慢的缺陷[7]，在本文2.1節(jié)通過(guò)最小二乘法得出目標(biāo)節(jié)點(diǎn)的初始估計(jì)位置可以有效解決該問(wèn)題，較少了收斂時(shí)間，則粒子群算法的初始位置可表示為：

xi1=Za(1)+rand()

xi2=Za(2)+rand()

其中:rand()的作用是產(chǎn)生分布在[0，1]內(nèi)的隨機(jī)數(shù)，可以使粒子群算法的初始粒子在最小二乘法估計(jì)出的位置附近開(kāi)始搜索，達(dá)到了提高收斂速度的目的。本文中使粒子群算法停止的條件是最大迭代次數(shù)，設(shè)置的最大迭代次數(shù)設(shè)置為itermax=100。

對(duì)于算法中的慣性權(quán)重ω，一般情況下按照線(xiàn)性遞減的方式變化，若函數(shù)一旦進(jìn)入局部極值點(diǎn)就很難跳出，從而陷入局部最優(yōu)[9]。文獻(xiàn)[10]指出，當(dāng)慣性權(quán)重ω服從正態(tài)分布時(shí)，算法的全局搜索能力較傳統(tǒng)的線(xiàn)性遞減時(shí)有明顯提高，可避免陷入局部最優(yōu)，能夠有效協(xié)調(diào)全局和局部搜索在算法中的權(quán)重。高斯函數(shù)服從正太分布，因此本文使慣性權(quán)重按照高斯函數(shù)遞減，表示為：

其中:κ為一常數(shù)，κ的大小影響了曲線(xiàn)的變化率，本文選取κ=0.2。

基于改進(jìn)粒子群算法的NLOS定位算法流程為：

3)將TDOA定位模型轉(zhuǎn)化為粒子群算法中的適應(yīng)度函數(shù)，把修正后的TDOA參數(shù)代入到適應(yīng)度函數(shù)中；

4)利用改進(jìn)慣性權(quán)重的粒子群算法進(jìn)行迭代求解目標(biāo)節(jié)點(diǎn)的精確位置。

3 仿真結(jié)果與分析

本文采用MATLAB對(duì)上述的理論進(jìn)行驗(yàn)證，模擬的仿真環(huán)境如下：假設(shè)室內(nèi)環(huán)境比較復(fù)雜，有多種障礙物和人員的走動(dòng)，無(wú)法檢測(cè)到LOS信號(hào)，只能得到NLOS信號(hào)；在50 m×50 m室內(nèi)二維平面中，有3個(gè)基站和一個(gè)目標(biāo)節(jié)點(diǎn)，基站坐標(biāo)已知且所有基站和目標(biāo)節(jié)點(diǎn)位于同一個(gè)平面中。將本文提出的LS-POS算法與兩步最小二乘法(2LS)和文獻(xiàn)[11]提出的Chan-Taylor算法進(jìn)行比較，采用均方根誤差作為評(píng)價(jià)定位精度的指標(biāo)：

由圖1可以看出隨著測(cè)量噪聲誤差的增大，3種算法的均方根誤差都相應(yīng)增大，但本文提出的LS-PSO算法定位性能要優(yōu)于2LS和Chan-Taylor算法。最小二乘法是一種非迭代定位算法，無(wú)法在迭代的過(guò)程中逐漸減小誤差，因此兩步最小二乘法的定位性能較差。

圖1 測(cè)量噪聲標(biāo)準(zhǔn)差和均方根誤差的關(guān)系

圖2所示為在非視距環(huán)境下，改變均方根時(shí)延拓展中的參數(shù)T1使其逐漸增加，代表著非視距誤差也相應(yīng)的增加，由圖可以看出隨著非視距誤差的增加，3種算法的均方根誤差都受到了較大影響，出現(xiàn)了較大的上升幅度，但相比如另外兩種算法，本文提出的LS-PSO算法受到的影響最小。Chan-Taylor算法受到的影響較大，定位結(jié)果與2LS相當(dāng)，這是因?yàn)镃han算法能夠精確定位的前提是TDOA誤差的均值要盡量小，否則定位結(jié)果將會(huì)受到很大影響[12]，在存在非視距誤差的環(huán)境中TDOA誤差服從的是正均值的高斯分布，且此均值較大，因此Chan定位精度明顯下降，Taylor又是以Chan算法的定位結(jié)果為初始值，從而導(dǎo)致該算法在非視距環(huán)境下性能的降低。

圖2 非視距誤差和均方根誤差的關(guān)系

圖3為本文提出的基于LS初值估計(jì)的POS算法和經(jīng)典PSO算法在收斂能力上的比較，橫軸表示算法的迭代次數(shù)，縱軸表示粒子群算法中的適應(yīng)度值。由圖可以看出，LS-PSO算法在第23次迭代即可收斂，達(dá)到了最佳的適應(yīng)度值，而經(jīng)典PSO算法在41步才達(dá)到最佳適應(yīng)度值，因此LS-PSO算法相對(duì)于經(jīng)典PSO算法提高了收斂速度。

圖3 LS-PSO和經(jīng)典PSO算法收斂速度的比較

圖4展示了粒子群算法中慣性權(quán)重的改進(jìn)對(duì)定位結(jié)果的優(yōu)化作用，當(dāng)慣性權(quán)重按照高斯函數(shù)變化，定位結(jié)果明顯優(yōu)于按照線(xiàn)性遞減的策略，改善了粒子群算法易陷于局部最優(yōu)的缺點(diǎn)，從而提高了定位精度。圖5為慣性權(quán)重按照兩種策略變化時(shí)收斂速度的比較，當(dāng)慣性權(quán)重按照高斯函數(shù)變化時(shí)，經(jīng)過(guò)23步迭代即可收斂，而當(dāng)慣性權(quán)重按照線(xiàn)性遞減策略變化時(shí)，需要經(jīng)過(guò)37步迭代才收斂。因此，對(duì)粒子群算法中的慣性權(quán)重參數(shù)進(jìn)行調(diào)整，使其按照高斯函數(shù)變化，可以顯著改善算法易陷入局部最優(yōu)的缺陷、提高定位精度，并且可以加快算法的收斂速度，優(yōu)化了算法的性能。

圖4 兩種策略定位精度的比較

圖5 兩種策略收斂速度的比較

4 結(jié)語(yǔ)

本文研究了非視距環(huán)境下超寬帶室內(nèi)定位算法。首先對(duì)NLOS室內(nèi)環(huán)境中的TDOA定位模型重構(gòu)；然后由均方根時(shí)延拓展估計(jì)出NLOS誤差的均值和方差，對(duì)重構(gòu)后的TDOA模型參數(shù)作調(diào)整，建立適應(yīng)度函數(shù)；最后通過(guò)LS-PSO算法估計(jì)出目標(biāo)節(jié)點(diǎn)的位置坐標(biāo)，并與2LS和Chan-Taylor算法進(jìn)行定位性能的比較。仿真結(jié)果顯示，本文提出的LS-PSO算法可以較好的抑制非視距誤差，提高非視距環(huán)境下的定位精度，且可以有效提高算法的收斂速度。此外，除了在超寬帶室內(nèi)定位中，本文提出的算法也可應(yīng)用在非視距環(huán)境下的其他無(wú)線(xiàn)定位技術(shù)中，提高其定位精度，因此具有一定的實(shí)際意義。