一種基于TOA的非視距誤差優(yōu)化定位算法

張 晨，王韋剛，許晨東，孫嘯辰，郭建軍，涂真珍，冒雨龍

(1.南京郵電大學(xué)電子與光學(xué)工程學(xué)院，江蘇 南京 210023 2.南京郵電大學(xué)材料科學(xué)與工程學(xué)院，江蘇 南京 210023)

近年來，隨著無線通信技術(shù)的發(fā)展和物聯(lián)網(wǎng)的廣泛應(yīng)用，基于位置信息的服務(wù)得到了迅速發(fā)展，覆蓋了軍事、農(nóng)業(yè)、工業(yè)等眾多領(lǐng)域。隨著智能終端及設(shè)備的逐漸普及，如何提高室內(nèi)無線定位系統(tǒng)的定位精度成為一個(gè)研究熱點(diǎn)。面對(duì)室內(nèi)環(huán)境復(fù)雜、各種障礙物遮擋、多徑效應(yīng)嚴(yán)重的情況，室內(nèi)定位系統(tǒng)需要進(jìn)一步尋求更好的應(yīng)對(duì)方法以解決定位精度低的問題。

在無線傳感器定位系統(tǒng)中，人們希望獲得實(shí)時(shí)準(zhǔn)確的位置信息，目前許多定位技術(shù)得到了廣泛的研究，主要包括接收信號(hào)強(qiáng)度（RSS）［1］、到達(dá)時(shí)間（TOA）［2］、到達(dá)時(shí)間差（TDOA）［3］、到達(dá)角（AOA）［4］。這些應(yīng)用通常假設(shè)節(jié)點(diǎn)間的距離為直線距離，即假設(shè)信號(hào)通過錨節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的傳播是沒有障礙物遮擋的直線傳播，也稱為視距傳播（Line-of-sight，LOS）。 然而，在室內(nèi)定位場景中往往有很多障礙物，如桌子、墻壁、行人等障礙物都會(huì)干擾信號(hào)的傳播，此時(shí)節(jié)點(diǎn)間的視距傳播路徑會(huì)被阻斷。由于障礙物的存在，非視距（Non-line-of-sight，NLOS）傳播在定位場景中很常見，如圖1所示的室內(nèi)環(huán)境中，發(fā)射信號(hào)到達(dá)各個(gè)接收節(jié)點(diǎn)的傳播過程中同時(shí)存在LOS傳播和NLOS傳播。當(dāng)LOS傳播路徑不存在時(shí)，僅在NLOS環(huán)境中，發(fā)送節(jié)點(diǎn)發(fā)出的無線信號(hào)經(jīng)過反射、衍射、繞射等方式到達(dá)接收節(jié)點(diǎn)，對(duì)定位系統(tǒng)測距精度的影響更嚴(yán)重，并進(jìn)一步降低定位精度。鑒于NLOS傳播對(duì)目標(biāo)節(jié)點(diǎn)的定位影響非常大，人們希望能夠抑制NLOS傳播帶來的誤差，從而減少NLOS誤差對(duì)目標(biāo)節(jié)點(diǎn)定位的影響。

圖1 信號(hào)傳播示意圖

目前有兩種研究思路來減少NLOS誤差。一種是先識(shí)別 LOS／NLOS連接，如采用神經(jīng)網(wǎng)絡(luò)［5-7］、能量檢測［8］等識(shí)別方法。 Wylie 等［9］通過節(jié)點(diǎn)之間的距離結(jié)合測量噪聲標(biāo)準(zhǔn)差以及殘差分析測試，來判斷測量數(shù)據(jù)中是否存在NLOS誤差。若檢測到LOS連接數(shù)量能夠滿足定位要求，可以舍棄NLOS信息并直接采用LOS信息進(jìn)行定位，然后利用LOS數(shù)據(jù)使用最大似然估計(jì)方法進(jìn)行計(jì)算［10］，它可以提供一種逐步優(yōu)化的定位方法，在這種情況下，定位精度可以達(dá)到Cramer-Rao下界（CRLB）。而當(dāng)NLOS連接較多不可忽略時(shí)，可以利用NLOS傳播的信息進(jìn)行定位，Xie 等［11］采用殘差加權(quán)對(duì) NLOS／LOS 混合場景下進(jìn)行定位。文獻(xiàn)［12］提出了一種利用NLOS信號(hào)傳播過程的多徑反射提高定位魯棒性的方法。文獻(xiàn)［13］提出了一種誤差項(xiàng)統(tǒng)計(jì)特征算法。文獻(xiàn)［14］把定位維度擴(kuò)展到三維空間中，利用接收信號(hào)強(qiáng)度與到達(dá)時(shí)間相結(jié)合來進(jìn)行定位。然而，如果觀測數(shù)據(jù)與假設(shè)的概率模型不匹配，也就是沒能準(zhǔn)確識(shí)別出 NLOS／LOS連接時(shí)，上述定位算法的性能下降非常嚴(yán)重。實(shí)際上，在大多數(shù)網(wǎng)絡(luò)中，區(qū)分NLOS／LOS連接非常困難，因?yàn)楹茈y獲得有關(guān)NLOS的先驗(yàn)信息。另一種是不先識(shí)別LOS／NLOS連接而直接進(jìn)行定位。該方法采用基于魯棒的統(tǒng)計(jì)方法［15］，利用NLOS傳播的特性，計(jì)算復(fù)雜度低且易于實(shí)現(xiàn)，但算法實(shí)際效果依賴于目標(biāo)函數(shù)的選擇，實(shí)際的應(yīng)用場景會(huì)影響算法的性能，它需要一定大小的統(tǒng)計(jì)窗口，會(huì)有相應(yīng)的延時(shí)。使用位置濾波［16］的方法，可以遞歸地給出位置估計(jì)結(jié)果，靈活地選擇合適的濾波算法以適應(yīng)不同的應(yīng)用場合，然而一些算法計(jì)算復(fù)雜度較高，在濾波模型與實(shí)際系統(tǒng)不匹配時(shí)，性能會(huì)嚴(yán)重下降。Li等［17］提出了利用數(shù)據(jù)庫對(duì)NLOS誤差進(jìn)行修正的動(dòng)態(tài)定位算法，從坐標(biāo)已知的信標(biāo)節(jié)點(diǎn)中獲得NLOS誤差信息并記錄在數(shù)據(jù)庫中，用來進(jìn)一步生成校正圖。然而，該方法不能覆蓋所有區(qū)域，并且建立數(shù)據(jù)庫的過程復(fù)雜，存在降噪和基準(zhǔn)點(diǎn)檢測的問題。文獻(xiàn)［18］采用三步最優(yōu)化法，利用泰勒級(jí)數(shù)擴(kuò)展，對(duì)非線性方程進(jìn)行線性化處理，并用線性最小二乘得到初始的移動(dòng)節(jié)點(diǎn)位置估計(jì)，在正偏差的約束下，采用基于迭代最優(yōu)化方法估計(jì)非視距誤差，再用估計(jì)誤差修正初始的移動(dòng)節(jié)點(diǎn)位置估計(jì)。由于此方法的成本函數(shù)定義為移動(dòng)節(jié)點(diǎn)位置和多個(gè)距離圓交點(diǎn)之間的距離平方和，但當(dāng)距離圓內(nèi)部交點(diǎn)數(shù)量很大時(shí)，計(jì)算量會(huì)很大。

針對(duì)上述存在的問題，在本文中，提出了一種基于幾何約束的二次規(guī)劃優(yōu)化方法來抑制NLOS誤差。一方面，它不需要任何關(guān)于NLOS連接的先驗(yàn)信息。另一方面，由于采用了更嚴(yán)格的約束，它會(huì)比現(xiàn)有的優(yōu)化方案具有更高的定位精度，可以應(yīng)用于TOA系統(tǒng)中的NLOS誤差抑制。實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有優(yōu)化技術(shù)相比，該方法具有更好的魯棒性和更好的定位精度。

1 相關(guān)工作

1.1 基于三邊定位的方法

三邊定位利用各個(gè)錨節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離進(jìn)行定位。如圖2所示，（xi，yi）表示第i個(gè)錨節(jié)點(diǎn)的坐標(biāo)，di表示第i個(gè)錨節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離，設(shè)未知目標(biāo)節(jié)點(diǎn)坐標(biāo)為（x，y），根據(jù)畢達(dá)哥拉斯定理可以得到以下方程

圖2 三邊定位原理圖

通過求該方程解得到目標(biāo)節(jié)點(diǎn)的坐標(biāo)。然而由于室內(nèi)環(huán)境中NLOS誤差的存在，測得節(jié)點(diǎn)間的距離往往不是準(zhǔn)確的距離，如圖3所示，3個(gè)圓通常不會(huì)交于一點(diǎn)而是形成一個(gè)區(qū)域，這時(shí)候如果利用式（1）求解目標(biāo)節(jié)點(diǎn)的坐標(biāo)必然會(huì)出現(xiàn)較大誤差。

圖3 NLOS情況下的三邊定位原理圖

1.2 基于半正定的優(yōu)化方法

在TOA定位技術(shù)中，得到的數(shù)據(jù)為目標(biāo)節(jié)點(diǎn)和錨節(jié)點(diǎn)之間的距離。通常對(duì)第i個(gè)錨節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的距離建模如下

然而在實(shí)際的室內(nèi)環(huán)境中，目標(biāo)節(jié)點(diǎn)和錨節(jié)點(diǎn)之間既有LOS連接也有NLOS連接，當(dāng)計(jì)算路徑是LOS連接時(shí)，測量誤差會(huì)存在為負(fù)值的情況。在這種情況下，Su等［21］通過加入一個(gè)松弛變量對(duì)不等式進(jìn)行松弛以滿足條件，即ri＋ui＞di，保證不等式的成立。同時(shí)，確定ui的值很重要，這個(gè)變量必須足夠大以確保不等式的可行性，同時(shí)也需足夠小以確保約束方程。約束的目的是使目標(biāo)函數(shù)最小化，以增加優(yōu)化函數(shù)的可行性。模型如下

式中：pi為第i個(gè)錨節(jié)點(diǎn)的坐標(biāo)，ρ和μ為常數(shù)，其取值根據(jù)不同的定位場景設(shè)定。

1.3 基于半正定的合作定位

一個(gè)合作定位網(wǎng)絡(luò)［22］是由一部分已知坐標(biāo)的錨節(jié)點(diǎn)來定位大量坐標(biāo)未知的源節(jié)點(diǎn)，設(shè)xi∈R2，i＝1，2，…，N 是第 i個(gè)坐標(biāo)未知的源節(jié)點(diǎn)，yj∈ R2，j＝1，2，…，M是第j個(gè)坐標(biāo)已知的錨節(jié)點(diǎn)。 Ly和Lx包含了LOS中源-錨連接和源-源連接，Ny和Nx包含了NLOS中源-錨連接和源-源連接。

所運(yùn)用的SDP方法能夠利用節(jié)點(diǎn)之間的合作進(jìn)行定位，當(dāng)大多數(shù)是 NLOS時(shí)，可以改善定位性能。

2 改進(jìn)的二次規(guī)劃算法

2.1 系統(tǒng)模型

系統(tǒng)模型采取二次規(guī)劃［23］的優(yōu)化方法，通過對(duì)不等式的變換，將方程的最小二乘求解過程轉(zhuǎn)化為二次規(guī)劃問題。在NLOS連接中，錨節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的距離如式（3）所示。目標(biāo)節(jié)點(diǎn)與第i個(gè)錨節(jié)點(diǎn)的關(guān)系應(yīng)滿足

式中， B ＝ diag｛d1，d2，…，dN｝，Q 為噪聲方差矩陣。

當(dāng)NLOS誤差不可忽略時(shí)，將式（17）作為約束項(xiàng)加入到式（19）中，可以得到目標(biāo)位置估計(jì)為

2.2 改進(jìn)的二次規(guī)劃模型

在此基礎(chǔ)上，本文提出了一種新的約束條件，利用三角形三邊的關(guān)系，采用幾何的方法對(duì)目標(biāo)函數(shù)的解進(jìn)一步約束。眾所周知，在一個(gè)三角形中，兩條邊之和總是大于第三條邊。如圖4所示，BSi、BSj分別代表第i、j個(gè)錨節(jié)點(diǎn)，各個(gè)錨節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的距離之和總是大于第i、j個(gè)錨節(jié)點(diǎn)之間的距離。

圖4 節(jié)點(diǎn)間的位置關(guān)系

求解二次規(guī)劃的方法有很多種，包括變量消去法［24］、拉格朗日乘子法［25］、積極集法［26］等。 這里采用凸優(yōu)化方法中的內(nèi)點(diǎn)法［27］來解決二次規(guī)劃問題。根據(jù)上面所述，歸納出本文算法的步驟如算法1所示。

算法1 改進(jìn)的二次規(guī)劃算法步驟

3 實(shí)驗(yàn)與分析

在本節(jié)中，我們將評(píng)估所提出的定位算法的性能，并將其與其他定位算法進(jìn)行了比較。定位區(qū)域是一個(gè)8×8的正方形，在這里我們?cè)O(shè)置4個(gè)錨節(jié)點(diǎn)和1個(gè)目標(biāo)節(jié)點(diǎn)。錨節(jié)點(diǎn)的位置是固定的，分別為（0，0）、（0，8）、（8，0）、（8，8），目標(biāo)節(jié)點(diǎn)的位置則不固定，在每一次仿真實(shí)驗(yàn)中隨機(jī)生成，環(huán)境設(shè)置如圖5所示。測量噪聲服從高斯分布，其均值為0，標(biāo)準(zhǔn)差和距離成比例，取實(shí)際距離的2%。NLOS誤差服從指數(shù)分布，我們?cè)O(shè)置了三組不同均值的實(shí)驗(yàn)條件，分別是實(shí)際距離的10%、30%和50%，對(duì)于上述三種情況，分別進(jìn)行1 000次蒙特卡羅實(shí)驗(yàn)。文中提到的幾種優(yōu)化算法通過內(nèi)點(diǎn)法進(jìn)行求解，各個(gè)算法的定位誤差的累積分布函數(shù)（CDF）如圖6所示。圖中“trileration”表示三邊定位算法，“qp”表示原始的二次規(guī)劃求解方法，“the optimized qp”表示增加NLOS誤差約束的算法，“the proposed method”表示本文所提算法。從圖5中可以看出，當(dāng)噪聲為10%時(shí)，基于幾何約束的定位算法與其他算法相比優(yōu)勢(shì)不明顯，隨著NLOS誤差越來越大，噪聲環(huán)境逐漸變差時(shí)，達(dá)到30%、50%的真實(shí)距離，本文提出的定位算法效果相比其他算法優(yōu)勢(shì)越來越明顯。這就表明，本文所提出的算法更適合在低信噪比的環(huán)境中進(jìn)行定位。

圖5 仿真環(huán)境設(shè)置

圖6 不同算法位置誤差CDF分布圖

上述算法在不同噪聲條件下的定位均方根誤差（RMSE）如圖7所示。RMSE計(jì)算方式如下：

其中θi與分別表示第i次蒙特卡羅實(shí)驗(yàn)?zāi)繕?biāo)節(jié)點(diǎn)的真實(shí)坐標(biāo)與估計(jì)坐標(biāo)，M表示蒙特卡洛實(shí)驗(yàn)的次數(shù)。從圖7中可以看出，當(dāng)NLOS誤差較小時(shí)，幾種算法的定位誤差相差不大。然而，隨著誤差的增加，所提出的方法的定位誤差明顯小于其他方法。同時(shí)可以看出，隨著NLOS誤差的變化，本文所提出的方法變化的幅度相對(duì)較小，這意味著其魯棒性更好。

圖7 不同算法的RMSE仿真結(jié)果

為了對(duì)算法的效果進(jìn)行準(zhǔn)確評(píng)估，接下來對(duì)上述算法的復(fù)雜度進(jìn)行分析。本文所提的算法采用內(nèi)點(diǎn)法進(jìn)行求解，首先使用拉格朗日法將不等式去除，然后使用KKT條件將原問題轉(zhuǎn)為方程組，最后使用牛頓法求解。

利用內(nèi)點(diǎn)法求解的通用復(fù)雜度［28］為

式中，m為輸入變量的維度，p*為函數(shù)的最優(yōu)解，M為在進(jìn)行內(nèi)點(diǎn)法求解之前迭代收斂的坐標(biāo)，ε＞0為解的精度，常數(shù)γ取決于回溯參數(shù)α和β，

常數(shù)c只取決于精確度εnt，c＝log2log2（εnt），通常c≈ 6。

最終計(jì)算得到內(nèi)點(diǎn)法的復(fù)雜度為Ο（n3．5L2），其中n輸入是變量的維度，L是輸入的長度。在采用內(nèi)點(diǎn)法計(jì)算式（30）中的坐標(biāo)之前，需要對(duì)初始的坐標(biāo)進(jìn)行迭代收斂，若進(jìn)行迭代N次后收斂，則總體的復(fù)雜度為Ο（Nn3．5L2）。

根據(jù)上述算法，求得不同算法的計(jì)算復(fù)雜度，各個(gè)算法的復(fù)雜度對(duì)比如表1所示。其中trileration和qp少了約束項(xiàng)，不需要采用內(nèi)點(diǎn)法進(jìn)行求解，因此它們的復(fù)雜度都為Ο（1）。而the optimized qp和the proposed method添加了約束項(xiàng)，則需要采用內(nèi)點(diǎn)法進(jìn)行求解。式（30）中的兩項(xiàng)約束的形式是相同的，因此在實(shí)際的求解中，可以把這兩項(xiàng)合并為一項(xiàng)，則the proposed method與 the optimized qp的復(fù)雜度是相同的，都為Ο（Nn3L2）。綜合各個(gè)算法的定位性能來說，在噪聲環(huán)境惡劣的情況下，使用本文所提算法更有優(yōu)勢(shì)。

表1 算法復(fù)雜度對(duì)比

4 結(jié)束語

在本文中，提出一種抑制NLOS誤差的定位算法。該算法采用幾何方法來進(jìn)一步約束原有的目標(biāo)函數(shù)，以提高定位精度。仿真結(jié)果表明，通過加入新的幾何約束，基于二次規(guī)劃的定位算法的性能有了較明顯的提高。將所提出的算法與之前的定位方法在不同NLOS環(huán)境下進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，當(dāng)NLOS的誤差較大時(shí)，基于幾何約束的二次規(guī)劃的定位效果較其他定位方法有一定的優(yōu)勢(shì)。