非視距環(huán)境中的無(wú)線網(wǎng)絡(luò)殘差加權(quán)定位算法*

尹燁佳,華驚宇,李 楓,張 昱,余旭濤

(1. 浙江工業(yè)大學(xué)信息工程學(xué)院,杭州 310023;2.浙江工商大學(xué)信息與電子工程學(xué)院,杭州 310018;3.東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室,南京 210096)

近十幾年以來(lái),無(wú)線通信網(wǎng)絡(luò)中目標(biāo)節(jié)點(diǎn)的精確定位已成為人們關(guān)注的熱點(diǎn)。目前,主要的定位技術(shù)可以分為基于衛(wèi)星定位以及基于地面無(wú)線定位兩大類。前者主要用于戶外環(huán)境中,例如基于GPS的導(dǎo)航,其中非軍用用戶可以實(shí)現(xiàn)大約幾十米的定位誤差。但是GPS很難應(yīng)用于室內(nèi)定位以及那些無(wú)法獲取GPS位置的環(huán)境中。因此,我們的研究將關(guān)注于地面無(wú)線定位問(wèn)題,例如基于WSN的無(wú)線定位。

地面無(wú)線定位按照是否基于測(cè)距又可分為range-free和range-based兩大類。前者往往需要高密度的節(jié)點(diǎn)分布作為條件[1],但是,現(xiàn)實(shí)環(huán)境中網(wǎng)絡(luò)規(guī)模和節(jié)點(diǎn)密度差異性非常大,因此,本文主要研究基于range-based的定位方法,這類方法主要取決于選擇何種定位參數(shù)。現(xiàn)有定位技術(shù)中主要有基于到達(dá)時(shí)間(TOA)估計(jì)[2-3],基于到達(dá)時(shí)間差(TDOA)估計(jì)[4-5],基于信號(hào)場(chǎng)強(qiáng)(RSSI)估計(jì)[6],基于到達(dá)方向(AOA)估計(jì)[7],以及基于混合參量估計(jì),比如TOA/AOA,TDOA/AOA和RSS/AOA[8-9]。此外,這類range-based的定位方法存在兩種非理想因素,一種是測(cè)量誤差,另一種是由信號(hào)傳播過(guò)程中折射和反射等現(xiàn)象引起的非視距NLOS(Non-Line Of Sight)誤差。前者一般被定義為均值為零的高斯變量,相對(duì)而言,這種誤差的標(biāo)準(zhǔn)差一般很小[10];而后者NLOS誤差則是無(wú)線定位中最為主要的誤差,NLOS傳播會(huì)導(dǎo)致較大的時(shí)延和角度偏差,因此會(huì)大大降低無(wú)線定位算法的精度。在實(shí)際的無(wú)線網(wǎng)絡(luò)中,它的誤差值可以到達(dá)通信半徑的20%～50%[11],而且由于實(shí)際環(huán)境中無(wú)線網(wǎng)絡(luò)的復(fù)雜性無(wú)法對(duì)其進(jìn)行精確建模,所以NLOS誤差的抑制和消除已成為無(wú)線定位算法能否實(shí)際應(yīng)用的關(guān)鍵。

為提高非視距環(huán)境下的定位精度,目前主要存在以下幾類誤差抑制的算法:第一類叫模型法,就是利用類似訓(xùn)練的方法對(duì)非視距誤差先進(jìn)行精確建模,然后根據(jù)建立的模型來(lái)估計(jì)目標(biāo)節(jié)點(diǎn)的位置[12-13]。但是由于實(shí)際環(huán)境的復(fù)雜性和動(dòng)態(tài)性很難得到一個(gè)精確的模型,因此該類算法很難得到廣泛應(yīng)用。第二類叫檢測(cè)法,首先利用LOS節(jié)點(diǎn)與NLOS節(jié)點(diǎn)的參數(shù)差異,識(shí)別出基于視距傳輸?shù)撵o態(tài)節(jié)點(diǎn)(LOS-SN),剔除非視距傳輸?shù)撵o態(tài)節(jié)點(diǎn)(NLOS-SN),最后只利用LOS傳輸?shù)撵o態(tài)節(jié)點(diǎn)進(jìn)行位置估計(jì)[14-15]。如果能夠正確識(shí)別出所有的視距傳輸?shù)撵o態(tài)節(jié)點(diǎn),且LOS-SN節(jié)點(diǎn)數(shù)足夠多的條件下,那么該算法的定位精度將會(huì)非常高,但是由于虛警率的存在很難做到檢測(cè)的正確性,因此該類算法的實(shí)際定位精度往往很難滿足實(shí)際需求。第三類算法是應(yīng)用所有的SN信息,包括LOS節(jié)點(diǎn)和NLOS節(jié)點(diǎn),然后利用優(yōu)化算法得到目標(biāo)節(jié)點(diǎn)位置,這種方法雖然能得到較高的定位精度,但是計(jì)算復(fù)雜度比較高[3-4],如半正定規(guī)劃SDP算法,其利用的是半正定規(guī)劃的內(nèi)點(diǎn)法,這類方法屬于多項(xiàng)式時(shí)間算法,迭代復(fù)雜性較高。第四類算法叫權(quán)重法,就是對(duì)節(jié)點(diǎn)進(jìn)行分組,并給每一組的臨時(shí)位置估計(jì)分配合適的權(quán)重并求和以提高目標(biāo)節(jié)點(diǎn)位置的估計(jì)精度。我們往往利用幾何關(guān)系和代數(shù)關(guān)系,最典型的就是利用殘差參數(shù)構(gòu)建加權(quán)函數(shù)[16-18]。這類算法的優(yōu)點(diǎn)是能區(qū)別利用LOS及NLOS節(jié)點(diǎn)的信息,對(duì)于LOS節(jié)點(diǎn)的信息給予比較大的權(quán)重值,對(duì)于NLOS節(jié)點(diǎn)就給予較小的權(quán)重值,最終科學(xué)充分地利用LOS節(jié)點(diǎn)信息,提高定位精度。傳統(tǒng)權(quán)重類定位算法的缺點(diǎn)是權(quán)重的選擇設(shè)計(jì)不夠科學(xué),往往不能充分利用LOS節(jié)點(diǎn)信息,所以本文提出了一種改進(jìn)的權(quán)重定位算法。

本文在傳統(tǒng)的權(quán)重算法上進(jìn)行改進(jìn),主要方法如下,首先對(duì)所有靜態(tài)節(jié)點(diǎn)(SN)進(jìn)行分組,由于選用的參數(shù)不同,每組都可得到3個(gè)目標(biāo)節(jié)點(diǎn)估計(jì)位置。同時(shí)因?yàn)榇嬖跍y(cè)距誤差和NLOS誤差,得到的目標(biāo)位置估計(jì)之間必然存在位置差,將該差值定義為臨時(shí)定位殘差。區(qū)別于傳統(tǒng)的殘差加權(quán)定位算法,本文根據(jù)所選殘差特點(diǎn),提出用殘差的高次冪作為加權(quán)函數(shù),并通過(guò)仿真尋找最優(yōu)的加權(quán)函數(shù)。最后給每個(gè)目標(biāo)估計(jì)位置分配相應(yīng)的權(quán)值并加權(quán)求和得到最終的TN估計(jì)位置。主要貢獻(xiàn)有①采用了一種新的殘差定義,即臨時(shí)定位殘差;②結(jié)合該殘差值的特點(diǎn)提出了新的權(quán)重函數(shù),并根據(jù)殘差值對(duì)權(quán)重函數(shù)做了優(yōu)化搜索。計(jì)算機(jī)仿真結(jié)果表明本文提出的算法要優(yōu)于其他對(duì)比的抗NLOS定位算法,尤其是對(duì)比傳統(tǒng)的殘差加權(quán)定位算法,定位精度得到了較大的提高。同時(shí)本文提出的算法屬于線性類算法,其計(jì)算復(fù)雜度與輸入的數(shù)據(jù)規(guī)模成正比,計(jì)算復(fù)雜度較優(yōu)化類算法低。

1 基于臨時(shí)定位的殘差定義

圖1 定位幾何模型

假設(shè)目標(biāo)節(jié)點(diǎn)TN的坐標(biāo)為(x,y),靜態(tài)節(jié)點(diǎn)SN的坐標(biāo)為(xi,yi),那么TN和SN之間的距離可以表示成:

(1)

θi=arctan[(y-yi)/(x-xi)]

(2)

利用靜態(tài)節(jié)點(diǎn)SN1和SN2所得的測(cè)距,可以得到如下方程組:

(3)

(4)

(5)

類似地,點(diǎn)B坐標(biāo)的求解方程為:

(6)

如用矩陣形式表示,以點(diǎn)A為例:

Y=AXA

(7)

如果傳輸環(huán)境中不存在NLOS,那么目標(biāo)節(jié)點(diǎn)TN的位置即可通過(guò)最小二乘算法求解,即

(8)

同樣地,點(diǎn)B的坐標(biāo)也是可以通過(guò)解類似于(8)的方程組得到。因此可以定義點(diǎn)A和B之間距離即為臨時(shí)定位殘差:

(9)

從圖1中我們可知,兩個(gè)定位圓的交點(diǎn)有2個(gè),為簡(jiǎn)便,我們可以簡(jiǎn)單地將殘差定義為

(10)

那么臨時(shí)定位殘差就可以表示成:

(11)

上式中的C′表示在C,F兩點(diǎn)中找出距離A點(diǎn)或B點(diǎn)更近的點(diǎn),將其記為C′。從上述殘差的定義中我們可以看出,如果僅存在測(cè)距噪聲,那么上述得到的三個(gè)TN位置估計(jì)都是相對(duì)較精確的,那么所對(duì)應(yīng)的臨時(shí)殘差值也很小。如果存在NLOS傳輸?shù)撵o態(tài)節(jié)點(diǎn),那么由于利用的定位參數(shù)本身存在很大偏差,據(jù)此得到的估計(jì)位置就會(huì)遠(yuǎn)遠(yuǎn)偏離真實(shí)位置,而且偏離的趨勢(shì)也會(huì)有所不同,這就導(dǎo)致了殘差值的上升。據(jù)上圖1所示,雖然理論上F點(diǎn)也可作為目標(biāo)節(jié)點(diǎn)的臨時(shí)估計(jì)位置,但是所有的臨時(shí)估計(jì)位置應(yīng)該集中在一個(gè)小范圍內(nèi),由于F點(diǎn)距離其余的幾個(gè)臨時(shí)估計(jì)位置較遠(yuǎn),所以本文拋棄了F點(diǎn)。

2 臨時(shí)定位殘差加權(quán)算法

圖2 算法流程圖

得到每個(gè)分組的TN臨時(shí)位置估計(jì)以及相應(yīng)的權(quán)重值后,確定最終目標(biāo)位置估計(jì),如下所示:

(12)

式中:Wi(Δ)表示和臨時(shí)定位殘差相關(guān)的加權(quán)函數(shù),ETNi表示第i個(gè)靜態(tài)節(jié)點(diǎn)組對(duì)TN的估計(jì)位置,它可以表示為

(13)

經(jīng)過(guò)分析可知,臨時(shí)定位殘差較小的靜態(tài)節(jié)點(diǎn)組得到的中間位置估計(jì)應(yīng)當(dāng)獲取較大的權(quán)重,這就說(shuō)明選擇的權(quán)重函數(shù)應(yīng)該是一個(gè)減函數(shù)。在傳統(tǒng)RWGH算法中,直接利用殘差的倒數(shù)作為權(quán)值,這就可能導(dǎo)致在靜態(tài)節(jié)點(diǎn)數(shù)目較少的情況下對(duì)NLOS誤差的抑制不足,我們的仿真結(jié)果也印證了這一點(diǎn)。分析造成上述現(xiàn)象的原因,主要還是因?yàn)镽WGH這種算法的加權(quán)函數(shù)選擇過(guò)于平庸,以及所采用的殘差定義對(duì)于NLOS誤差也不夠敏感,因此我們考慮使用函數(shù)值變動(dòng)更加劇烈的高冪次方作為加權(quán)函數(shù),并通過(guò)實(shí)際仿真驗(yàn)證我們的假設(shè)。

Wi(Δ)=(1/Δ)n,n≥2

(14)

如圖3所示,對(duì)比各條曲線可知,權(quán)重函數(shù)(即臨時(shí)定位殘差的n次方)的n值越大,其對(duì)應(yīng)曲線越陡,表示對(duì)應(yīng)的權(quán)重函數(shù)越靈敏。如此一來(lái),我們就可充分利用LOS-SN的信息,大大提高了最終的定位估計(jì)精度。另外,對(duì)比n=5和n=10的曲線可知兩者趨于重合,所以不再研究n>5的權(quán)重函數(shù)。

圖3 不同權(quán)重函數(shù)的數(shù)值變化

3 計(jì)算機(jī)仿真與分析

本文的仿真全都是在MATLAB中完成,其中靜態(tài)節(jié)點(diǎn)坐標(biāo)如下:(0,0),(100,100),(-100,100),(-100,-100),(100,-100),單位是米。并且假設(shè)測(cè)距和AOA測(cè)量值的誤差均為零均值的高斯變量,假設(shè)NLOS傳輸對(duì)距離測(cè)量帶來(lái)的誤差為0和max之間服從均勻分布的變量[16],而AOA的NLOS誤差則為零均值的高斯變量,但其標(biāo)準(zhǔn)差相對(duì)較大[19]。

3.1 加權(quán)函數(shù)的確定

假設(shè)測(cè)量距離標(biāo)準(zhǔn)差MDSD(Measuring Distance Standard Deviation)為1 m,測(cè)量角度標(biāo)準(zhǔn)差MASD(Measuring Angle Standard Deviation)為1°,NLOS的最大值max為40 m。

通過(guò)對(duì)比圖3中的1次方,2次方和5次方加權(quán)函數(shù)的曲線,可知?dú)埐畹膬绱畏剿鶎?duì)應(yīng)的數(shù)值對(duì)定位精度的影響非常顯著,為進(jìn)一步提高定位精度,接下來(lái)我們以5次方加權(quán)為基準(zhǔn)對(duì)冪次方進(jìn)行小數(shù)搜索。

從圖4可知,冪指數(shù)值選在5附近時(shí)性能差別不大,從仿真結(jié)果看,我們選取最優(yōu)值n=4.8。

圖4 不同冪指數(shù)的CDF圖

接下來(lái)我們選取不同的算法殘差進(jìn)行比較。其中posWk代表以臨時(shí)定位殘差倒數(shù)的k次方作為加權(quán)系數(shù),同時(shí)我們引入最小二乘方法作為對(duì)比算法。

圖5顯示的是選擇不同權(quán)重函數(shù)時(shí)的CDF圖,從圖5(a)和圖5(b)可以發(fā)現(xiàn),posW1的定位誤差小于10 m的概率在2個(gè)LOS-SN條件下達(dá)到了87%,當(dāng)LOS-SN數(shù)量達(dá)到3個(gè)時(shí),概率更是達(dá)到了100%,而且其RMSE曲線在2個(gè)LOS-SN以及3個(gè)LOS-SN的情況下均要明顯優(yōu)于傳統(tǒng)的LS算法,但是和posW4.8相比,后者的定位誤差即使是在2個(gè)LOS-SN的條件下,定位誤差值小于5 m的概率也高達(dá)94%,在3個(gè)LOS-SN的條件下誤差值小于5 m的概率更是達(dá)到了99%,其定位性能顯然要優(yōu)于posW1算法。這就表明,對(duì)于利用定位殘差的加權(quán)定位算法而言,要根據(jù)選擇的殘差定義,選擇函數(shù)值變化較為劇烈的函數(shù)作為加權(quán)函數(shù),從而使LOS估計(jì)位置可以得到充分的加權(quán)。

圖5 選擇不同權(quán)重函數(shù)的CDF圖

圖6 選擇不同權(quán)重函數(shù)的RMSE圖

3.2 不同算法的綜合比較

接下來(lái)我們將分別研究測(cè)量距離標(biāo)準(zhǔn)差MDSD,測(cè)量距離標(biāo)準(zhǔn)差MASD,以及非視距NLOS誤差對(duì)以下不同算法精度的影響,仿真條件為:在 2個(gè)LOS靜態(tài)節(jié)點(diǎn)和3個(gè)LOS靜態(tài)節(jié)點(diǎn)的環(huán)境中進(jìn)行,其中NLOS誤差在0～max之間均勻分布。

表1 對(duì)比算法描述

①測(cè)量距離標(biāo)準(zhǔn)差的影響

圖7給出的是MDSD對(duì)各算法精度的影響。從圖中可以看出,CLS,opt-LLOP,RWG以及HFOP這四種算法產(chǎn)生的估計(jì)誤差較大,相比而言,SDP的定位性能較前四者有了顯著的改進(jìn),特別是當(dāng)環(huán)境中只有2個(gè)LOS-SN的條件下,但是跟本文提出的算法相比還是存在明顯的差距。顯然,我們可以發(fā)現(xiàn)本文提出的算法的定位性能要明顯優(yōu)于其他幾種對(duì)比算法。雖然隨著MDSD的增加,該算法的定位誤差有所上升,但依然低于其他的對(duì)比算法。這是因?yàn)殡S著MDSD的增加,利用LOS-SN求得的目標(biāo)估計(jì)位置所獲得的權(quán)重值也隨之降低,從而造成定位性能有所下降。此外從仿真結(jié)果可以看出,隨著LOS-SN數(shù)量的增加posW4.8曲線接近于克拉美羅下界,也就是說(shuō)本文提出的算法隨著LOS-SN數(shù)量的增多,定位性能更好。

圖7 MDSD對(duì)算法精度的影響

②測(cè)量角度標(biāo)準(zhǔn)差的影響

如圖8所示是測(cè)量角度標(biāo)準(zhǔn)差MASD與定位均方根誤差之間的關(guān)系,我們可以發(fā)現(xiàn),隨著橫坐標(biāo)MASD值的變大,除TOA/AOA-LS算法外,其余對(duì)比算法所對(duì)應(yīng)的曲線基本持平,這是因?yàn)檫@些算法定位過(guò)程中沒(méi)有利用角度信息。但是觀之本文提出的posW4.8和對(duì)比算法TOA/AOA-LS,其對(duì)應(yīng)的曲線隨著橫坐標(biāo)的增大有明顯的上升趨勢(shì),這是因?yàn)闇y(cè)角誤差的增加造成了分配給精度較高的臨時(shí)位置估計(jì)的權(quán)值下降了,使得定位精度也隨之降低。圖8表明本文提出的算法其定位精度遠(yuǎn)高于TOA/AOA-LS算法,這主要得益于新的權(quán)重函數(shù)和殘差的良好適配,同時(shí)對(duì)比其他算法,本文所提算法的性能保持著明顯的優(yōu)勢(shì)。

③不同max值的影響

圖9 NLOS誤差最大值max對(duì)各算法定位精度影響

圖9的橫坐標(biāo)表示測(cè)量距離的NLOS誤差最大值,縱坐標(biāo)是定位均方根誤差(RMSE)。對(duì)比圖中各曲線可知,傳統(tǒng)的殘差權(quán)重算法(RWGH),線性最優(yōu)化算法(opt-LLOP),約束最小二乘算法(CLS)以及運(yùn)用海倫公式最優(yōu)化算法(HFOP)的定位誤差隨著max的增加上升趨勢(shì)都很明顯。觀之SDP算法,隨著max值的增加,其上升幅度雖然沒(méi)有前四者明顯,但還是高于本文提出的posW4.8算法。從圖中可知本文提出算法的精度隨著NLOS誤差的增大只是略有起伏,基本呈平緩趨勢(shì),也就是說(shuō)本文提出的算法即使在NLOS誤差較大的惡劣環(huán)境下也能具有較高的定位精度。

④角度域NLOS誤差的影響

圖10是非視距傳輸?shù)慕嵌葴y(cè)量誤差值與定位均方根誤差之間的關(guān)系。觀察圖中的曲線可知,隨著角度NLOS誤差的增加,各算法的RMSE值的變化并不顯著。因?yàn)樗械膶?duì)比算法都未利用到測(cè)角信息。而對(duì)于posW4.8算法,雖然從理論上分析,角度誤差的增大會(huì)降低該算法的定位性能。但是從上述仿真結(jié)果可知,本文提出的算法的定位精度隨著角度誤差的增加基本趨于平緩,特別是在LOS靜態(tài)節(jié)點(diǎn)數(shù)目為3時(shí)。這是因?yàn)殡S著角度NLOS誤差的增加,雖然使得目標(biāo)臨時(shí)位置估計(jì)的定位誤差值變大,但是由于其對(duì)應(yīng)的權(quán)重函數(shù)值較小,所以最終對(duì)定位性能影響并不大。

圖10 AOA的NLOS誤差對(duì)各算法精度的影響

4 結(jié)論

為提高非視距環(huán)境下的定位精度,本文提出用目標(biāo)臨時(shí)位置估計(jì)之間的差值構(gòu)建新的權(quán)重函數(shù),并以臨時(shí)位置估計(jì)加權(quán)和改善了定位性能。對(duì)比RWGH算法,本文算法不僅在定位精度上有了很大的提高,而且還降低了對(duì)LOS靜態(tài)節(jié)點(diǎn)數(shù)目的要求。對(duì)比SDP類優(yōu)化算法,本文提出的算法大大降低了計(jì)算復(fù)雜度同時(shí)也依然保持了性能優(yōu)勢(shì)。