齊小剛，張海洋，魏倩

（1. 西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，陜西 西安 710071; 2. 西安電子科技大學(xué) 寧波信息技術(shù)研究院，浙江寧波 315200）

機(jī)器人、無(wú)人機(jī)和其他智能系統(tǒng)[1]無(wú)法在建筑物、地下商場(chǎng)和其他室內(nèi)環(huán)境中利用全球?qū)Ш较到y(tǒng)獲得準(zhǔn)確的位置信息，所以研究室內(nèi)目標(biāo)定位變得更加重要。 近年來(lái)各種基于測(cè)距的智能體(機(jī)器人等)定位技術(shù)已經(jīng)被提出，根據(jù)不同的定位參數(shù)，可以分為基于接受信號(hào)強(qiáng)度(receive signal strength，RSS)、基于到達(dá)時(shí)間差(time difference of arrival，TDOA)、基于到達(dá)角度(angle of angle，AOA)、基于到達(dá)時(shí)間(time of arrival，TOA)以及混合參數(shù)等。其中，基于TOA測(cè)距的定位算法由于測(cè)量精度高和抗干擾性能好等優(yōu)點(diǎn)被廣泛應(yīng)用于室內(nèi)定位系統(tǒng)。本文主要研究非視距(non line of sight，NLOS)環(huán)境下的TOA定位。目前大部分算法在視距(line of sight，LOS)條件下得到了很好的估計(jì)值，但是在含有NLOS的環(huán)境中，由于NLOS誤差一般遠(yuǎn)大于節(jié)點(diǎn)間的測(cè)量噪聲，傳統(tǒng)算法的定位性能大大降低[2]。另一個(gè)原因是在惡劣環(huán)境中，目標(biāo)節(jié)點(diǎn)和傳感器之間的LOS信號(hào)難以提供足夠的信息，不得不求助NLOS信號(hào)[3]。因此，抑制NLOS誤差成為一項(xiàng)緊迫的任務(wù)，解決這個(gè)問(wèn)題最簡(jiǎn)單的辦法是識(shí)別出NLOS路徑，然后丟掉NLOS測(cè)量，用LOS測(cè)量定位源位置[4-5]。然而這種辦法有2個(gè)缺點(diǎn)：1) 如果LOS測(cè)量數(shù)量在二維空間小于3，三維空間小于4，則無(wú)法定位目標(biāo)節(jié)點(diǎn)的位置；2) 目前的技術(shù)下NLOS識(shí)別的成功率還不能達(dá)到100%，存在一定的虛警和漏警，這會(huì)大大地降低定位的性能[2]。

近年來(lái)，基于凸優(yōu)化的方法得到了廣泛的應(yīng)用。Yang 等[6]通過(guò)利用二次規(guī)劃(quadratic programming，QP)方法，提出了一種凸優(yōu)化定位算法，該算法能較好地抑制NLOS誤差，并且不需要知道任何NLOS誤差分布以及識(shí)別NLOS信號(hào)。文獻(xiàn)[7]提出了一種NLOS環(huán)境下RSS和TDOA聯(lián)合的信源被動(dòng)定位方法，通過(guò)建立加權(quán)最小二乘模型來(lái)抑制NLOS誤差對(duì)定位精度的影響，最終的目標(biāo)節(jié)點(diǎn)位置通過(guò)二分法迭代得到。Yu等[8]提出了一種基于非直瞄狀態(tài)信息的優(yōu)化問(wèn)題，并利用序列二次規(guī)劃算法解決了問(wèn)題。Lui等[9]提出了一種最大后驗(yàn)(maximum a posteriori，MAP)方法，該方法假定知道關(guān)于NLOS狀態(tài)的概率和NLOS誤差的準(zhǔn)確分布的先驗(yàn)信息。 王剛等[2]通過(guò)聯(lián)合估計(jì)目標(biāo)節(jié)點(diǎn)的位置和一個(gè)平衡參數(shù)，用于部分減輕NLOS誤差的影響，將估計(jì)問(wèn)題放寬為二階錐規(guī)劃(second order cone programming，SOCP)和半定規(guī)劃(semidefinite programming，SDP)，但是該方法需要知道NLOS誤差的上界。Tome等[10]在王剛等的基礎(chǔ)上，將估計(jì)問(wèn)題表述為一個(gè)廣義信賴域子問(wèn)題(generalized trust region subproblem，GTRS)，并以全局最優(yōu)的方式加以解決，算法計(jì)算復(fù)雜度逼近于線性。 Chen等[11]針對(duì)基于估計(jì)的方法在測(cè)量精確的稀疏NLOS環(huán)境中性能更好，當(dāng)NLOS誤差的上界是緊的時(shí)候，魯棒方法在稠密的NLOS環(huán)境中表現(xiàn)得更好的問(wèn)題，通過(guò)引入平衡參數(shù)，將問(wèn)題建模為一個(gè)魯棒加權(quán)最小二乘問(wèn)題，并利用凸松弛技術(shù)將原問(wèn)題近似為一個(gè)SDP問(wèn)題求解。 目前，雖然基于凸優(yōu)化的方法顯著提高了NLOS環(huán)境下的定位精度，但是這些算法的復(fù)雜度高，一是對(duì)傳感器的內(nèi)存、CPU要求高，二是難以滿足實(shí)時(shí)定位的需求，基于此，本文研究了一種低復(fù)雜度的NLOS環(huán)境下的定位算法。

1 無(wú)線電定位系統(tǒng)模型

在智能體構(gòu)成的局域網(wǎng)中，假設(shè)有N個(gè)錨節(jié)點(diǎn)和一個(gè)未知位置的目標(biāo)節(jié)點(diǎn)，定位就是用N個(gè)錨節(jié)點(diǎn)的位置去估計(jì)目標(biāo)節(jié)點(diǎn)的位置。假設(shè)錨節(jié)點(diǎn)的位置坐標(biāo)為ai(i=1,2,···,N)，目標(biāo)節(jié)點(diǎn)的位置坐標(biāo)為x，目標(biāo)節(jié)點(diǎn)和錨節(jié)點(diǎn)之間的路徑有視距(LOS)和非視距(NLOS)2種，第i個(gè)錨節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間的距離基于TOA模型可以建模為[12-13]

式中：i∈1,2,···,N；ni表示測(cè)量噪聲，大量文獻(xiàn)中均假設(shè)測(cè)量噪聲服從方差為 δ2的Gaussian零均值 分 布，即，ni～N(0,δ2) ；ei(i=1,2,···,N) 表 示NLOS誤差，由于NLOS誤差ei的產(chǎn)生是由于錨節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的障礙物造成的，所以在文獻(xiàn)中均假設(shè)NLOS誤差ei非負(fù)，即ei≥0，并且認(rèn)為NLOS誤差ei遠(yuǎn)大于測(cè)量噪聲ni，即ei>>ni。

如果NLOS狀態(tài)已知，式(1)可以變形為

在一些文獻(xiàn)中，建模過(guò)程中假設(shè)NLOS誤差ei為一些確定的分布，如均勻分布、指數(shù)分布、高斯分布等，或者需要對(duì)NLOS誤差ei加入一個(gè)約束，如NLOS誤差的上界已知等。 本文所提的方法不需要知道NLOS誤差ei的任何信息，適用于所有的分布，也不需要知道NLOS誤差ei的上界等。

2 NLOS誤差抑制的無(wú)線電定位算法

在NLOS狀態(tài)未知的情形下，來(lái)考慮目標(biāo)節(jié)點(diǎn)的定位。首先，通過(guò)對(duì)式(1)進(jìn)行移項(xiàng)和平方恒等變形，得到：

對(duì)式(3)進(jìn)行變形，得：

由于測(cè)量噪聲ni都比較小，所以可以忽略二階測(cè)量噪聲這樣，由式(4)可以得到：

由式(5)可以得到極大似然估計(jì)的概率密度函數(shù)為

關(guān)于x最大化式(6)，得到：

通過(guò)研究發(fā)現(xiàn)，式(7)是一個(gè)高度非凸的表達(dá)式，因?yàn)槠浞肿雍头帜妇莤的函數(shù)，本文沒(méi)有解決式(7)，而是解決了其一個(gè)近似問(wèn)題：

式(8)可以轉(zhuǎn)化為一個(gè)約束最優(yōu)化問(wèn)題：

為了求解式(9)，引入平衡參數(shù)e，用平衡參數(shù)e代替式(9)中的NLOS誤差ei。 由于平衡參數(shù)e可以看成是NLOS誤差的均值，這樣的優(yōu)點(diǎn)是只需估計(jì)一個(gè)平衡參數(shù)e。與文獻(xiàn)[10]不同的是本文并沒(méi)有聯(lián)合估計(jì)目標(biāo)節(jié)點(diǎn)的位置x以及平衡參數(shù)e，僅僅通過(guò)已有的SR-LS[12]算法進(jìn)行了建模，求解得到了平衡參數(shù)e的估計(jì)值e?，這樣會(huì)降低算法的復(fù)雜度，仿真結(jié)果表明，這樣有助于提高定位的性能。

這樣(9)式可以通過(guò)已有的方法求解，通過(guò)式(9)可以得到：

把式(10)轉(zhuǎn)化為一個(gè)約束最小化問(wèn)題：

式(10)轉(zhuǎn)化為式(11)是直接的，本文的目的是把原問(wèn)題轉(zhuǎn)化為一個(gè)廣義信賴域的子問(wèn)題(GTRS)，這樣便可以利用二分法求解該問(wèn)題。 把式(11)用向量的形式表示為

式中

到此為止，建模過(guò)程便完成了，但是有2個(gè)問(wèn)題需要解決，一是如何求解平衡參數(shù)e的估計(jì)值二是怎么求解該模型。下面便正式提出改進(jìn)的算法，解決上述2個(gè)問(wèn)題。

式(12)的模型是一個(gè)GTRS問(wèn)題，可以使用二分法進(jìn)行求解，對(duì)于平衡參數(shù)，首先假設(shè)平衡參數(shù)的估計(jì)值的初始值等于0，即不含有任何NLOS測(cè)量值，這樣便能求出目標(biāo)節(jié)點(diǎn)的一個(gè)初始值x0，然后計(jì)算平衡參數(shù)的方式為

算法1

輸入ai(i=1,2,···,N)，d，m。

輸出源節(jié)點(diǎn)的位置

式中 λmax(·) 代表最大的特征值。

2) 用二分法 在 區(qū) 間I計(jì)算函數(shù) ψ (λ) 的零點(diǎn)λt。其中：

3) 計(jì)算y?(λt) 的值，源節(jié)點(diǎn)的位置等于向量的前2個(gè)分量。

3 算法的復(fù)雜度分析

本節(jié)主要給出一些現(xiàn)有算法的復(fù)雜度以及本文所提算法的復(fù)雜度，參考文獻(xiàn)[10-11]中已有的結(jié)果，表1給出了所有算法最壞結(jié)果下的計(jì)算復(fù)雜度分析。 可以看出，所有方法的計(jì)算復(fù)雜度主要取決于網(wǎng)絡(luò)的規(guī)模，即錨的數(shù)量。

表1 算法的計(jì)算復(fù)雜度Table 1 The computational complexity of the algorithm

本文算法的計(jì)算復(fù)雜度雖然與迭代次數(shù)m有關(guān)系，但該算法與錨節(jié)點(diǎn)的數(shù)量以及迭代次數(shù)之間呈現(xiàn)出一種線性關(guān)系，在后面的仿真實(shí)驗(yàn)中證明，當(dāng)算法迭代次數(shù)m=1 時(shí)，算法便能取得較為良好的定位性能。

4 仿真結(jié)果以及分析

這節(jié)主要利用MTLAB仿真驗(yàn)證所提算法的性能。 為了更好說(shuō)明本文算法的性能，與已有的二次規(guī)劃(quadratic programming，QP)，半定規(guī)劃(semide- finite programming，SDP)，二階錐規(guī)劃(second order cone programming，SOCP)，隨機(jī)高斯(random Guess)，魯棒半定規(guī)劃(robust semidefinite programming，R-SDP)等算法進(jìn)行了比較。 算法的定位性能使用均方根誤差(root mean square error，RMSE)來(lái)衡量，RMSE計(jì)算方式為

式中xi與分別表示第i次定位目標(biāo)節(jié)點(diǎn)的真實(shí)位置與估計(jì)位置。 假設(shè)錨節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)隨機(jī)地分布在 20m×20m 的區(qū)域，執(zhí)行M個(gè)獨(dú)立的Monte Carlo(MC)運(yùn)行，并且在每個(gè)運(yùn)行中，使用隨機(jī)的錨節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)來(lái)定位隨機(jī)定位的目標(biāo)節(jié)點(diǎn)位置。在本文的仿真中，設(shè)置M=5000。假設(shè)節(jié)點(diǎn)間的測(cè)量噪聲ni服從Gaussian零均值分布，即ni～N(0,δ2) 。節(jié)點(diǎn)間的NLOS誤差ei在這里假設(shè)服從均勻分布，即U(0,Bmax)。

為了驗(yàn)證所提算法的性能，主要從以下3個(gè)方面進(jìn)行仿真：1)NLOS測(cè)量的數(shù)量比較少的情形；2)NLOS測(cè)量的數(shù)量比較多的情形；3)算法的計(jì)算復(fù)雜度驗(yàn)證。

1) 驗(yàn)證NLOS測(cè)量的數(shù)量比較少的情形下算法的性能。設(shè)置錨節(jié)點(diǎn)的個(gè)數(shù)N=5，NLOS測(cè)量與LOS測(cè)量的數(shù)量分別為1、4，等價(jià)于NLOS占比為20%，Bmax=7m，m=1，這也就意味著本文所提的算法僅僅迭代1次。仿真RMSE隨 σ 測(cè)量噪聲的關(guān)系，其中設(shè)置 σ 的范圍為0.15～0.90。圖1給出了算法的定位性能，可以看出本文所提算法的定位性能最好，QP、R-SDP19算法的定位性能次之。這是由于NLOS測(cè)量的數(shù)量少，本文所提的算法能計(jì)算出比較準(zhǔn)確的平衡參數(shù)初始值，所以迭代過(guò)程中取得了不錯(cuò)的性能。 當(dāng)測(cè)量噪聲比較小，可以看出本文算法和QP算法的性能基本一致，這是因?yàn)楫?dāng)LOS數(shù)量比較多，測(cè)量噪聲比較小的時(shí)候，對(duì)QP算法的目標(biāo)函數(shù)值影響比較小，從而表現(xiàn)出了優(yōu)異的性能。 本文所提算法在這種環(huán)境下性能優(yōu)于其他的凸優(yōu)化定位算法，這是因?yàn)橹T如SDP、SOCP等算法中含有經(jīng)過(guò)凸松弛處理的約束條件，在大量的LOS測(cè)量中，定位性能自然會(huì)下降。

圖1 不同定位算法性能的比較，NLOS=1，LOS=4Fig. 1 Comparison of performance of different positioning algorithms,where NLOS=1，LOS=4

2) 驗(yàn)證NLOS測(cè)量的數(shù)量比較多的情形下算法的性能。 NLOS測(cè)量與LOS測(cè)量的數(shù)量分別為3、2，等價(jià)于NLOS占比為60%，其他參數(shù)的設(shè)置同1)。 在圖2中顯示了算法的定位性能，可以看出，R-SDP19算法的性能最好，這是由于在含有大量的NLOS測(cè)量時(shí)，大量的約束條件就起到了抑制NLOS誤差的作用，能很好地提高算法的定位性能。 并且在測(cè)量噪聲不是很大的情形下，算法R-SDP14、SDP的定位性能也要好于QP，這也是因?yàn)槠渲械募s束條件發(fā)揮了抑制NLOS誤差的作用。本文的算法中由于加入了平衡參數(shù)，從圖2可以看出，其定位性能仍然要優(yōu)于一般的凸優(yōu)化算法，但次于算法R-SDP19。 但是當(dāng)測(cè)量噪聲增加時(shí)，本文算法的性能比較穩(wěn)定，并且與算法RSDP19的定位精度相差不大，也表現(xiàn)出了不錯(cuò)的性能。

圖2 不同定位算法性能的比較，NLOS=3，LOS=2 Fig. 2 Comparison of performance of different positioning algorithms,where NLOS=3，LOS=2

3)算法的計(jì)算復(fù)雜度驗(yàn)證。軟件：MATALB R2018 b，CPU：Intel(R)Core(TM)i5-7 500 3.40 GHZ，內(nèi)存：4.0 GB，δ=0.2，其他參數(shù)設(shè)置同1)，平均每次定位時(shí)間如表2所示。

表2 算法的平均定位時(shí)間Table 2 Average localization time of the algorithm

從表2可以看出，本文所提算法的定位速度僅次于Random Guess和SR-LS，遠(yuǎn)快于幾種基于凸優(yōu)化的定位算法。

通過(guò)以上仿真實(shí)驗(yàn)可以看出，本文算法在NLOS比例不是很高的時(shí)候占有很大的優(yōu)勢(shì)，在NLOS占比高的情形下雖然定位性能有所下降，但仍然優(yōu)于一些凸優(yōu)化算法。 綜合看來(lái)，本文的算法在定位性能和計(jì)算復(fù)雜度之間有著很好的平衡，可以滿足實(shí)時(shí)定位的需求。

5 結(jié)束語(yǔ)

在關(guān)于機(jī)器人、無(wú)人機(jī)和其他智能體的位置信息的研究領(lǐng)域中，目標(biāo)節(jié)點(diǎn)的位置信息是至關(guān)重要的環(huán)節(jié)。但是在含有NLOS環(huán)境中，節(jié)點(diǎn)的定位精度大大下降。為了抑制NLOS誤差對(duì)定位精度的影響，本文引入了平衡參數(shù)這一關(guān)鍵量，將定位問(wèn)題與一個(gè)GTRS問(wèn)題框架進(jìn)行對(duì)應(yīng)。與已有算法不同的是，本文所提算法并沒(méi)有聯(lián)合估計(jì)目標(biāo)節(jié)點(diǎn)的位置和平衡參數(shù)，而是采用了一種迭代求精的思想，算法用二分法進(jìn)行求解，高速有效。 本文所提算法與已有的算法相比，不需要任何關(guān)于NLOS路徑的信息(NLOS狀態(tài)、NLOS的分布、NLOS誤差的上界等)，另外，與大多數(shù)現(xiàn)有算法不同，所提算法的計(jì)算復(fù)雜度低，能夠滿足實(shí)時(shí)定位的需求。 仿真實(shí)驗(yàn)結(jié)果表明，該算法具有穩(wěn)定的NLOS誤差抑制能力，在定位性能和算法復(fù)雜度之間有著很好的平衡。但不足的是，如果所有的路徑均是NLOS，所提算法表現(xiàn)不佳，還有待后續(xù)研究。