LM算法在TDOA三維定位中的應用研究

韋子輝,張要發(fā),趙計勛,解云龍,李小亭,方立德

(河北大學 質量技術監(jiān)督學院,河北 保定 071002)

0 概述

隨著現代通信技術和TDOA定位技術的快速發(fā)展,TDOA定位技術憑借其獨特的優(yōu)勢成為最流行的定位方法之一。如何準確高效地求解TDOA定位技術中的定位方程組,得到移動節(jié)點的解坐標是實現準確定位的根本,因此定位求解算法成為研究熱點。本質上,求解TDOA定位方程組就是求解一組非線性方程,是一個復雜的非線性尋優(yōu)過程。求解非線性方程的方法有很多,遺傳算法(GA)是一種基于生物界規(guī)律和自然遺傳機制的并行搜索算法[1]。GA是通過模擬自然進化過程,在潛在存在解的空間中搜索最優(yōu)解的優(yōu)化算法[2],但在應用該算法過程中,交叉率和變異率可能導致優(yōu)質個體遭到破壞,對解的質量造成嚴重影響并且可能導致結果不收斂。最優(yōu)保存策略也是優(yōu)化算法中的一種,且其在人工智能[3]、工程計算[4]等領域均得到了應用。FANG算法[5]只能用于3個基站對目標平面位置進行確定,不能充分利用冗余的TDOA測量值。FRIEDLANDER算法[6]、SX算法[7]、SI算法[8]均忽略了變量之間的相關性,不能達到最優(yōu)估計。在TDOA的測量值誤差滿足理想的高斯分布的情況下,CHAN算法[9]可以達到理論最優(yōu)值,若TDOA測量值中包含非視距誤差,則該算法的性能將會顯著下降。Taylor算法[10]需給定一個與實際位置較為接近的初始迭代值,否則無法保證算法的收斂。文獻[11-12]的仿真結果表明,在實際蜂窩網通信系統(tǒng)中,解析法中定位性能最好的2種算法為CHAN算法與Taylor算法。

在實際定位環(huán)境中,多徑干擾現象普遍存在,這將會在TDOA測量值中引入非視距誤差,CHAN算法在這種情況下不再適用。因此,相比于CHAN算法,Taylor算法更加適合在實際定位環(huán)境中應用。Taylor算法是求解非線性方程的有效方法,具有精度高等特性[13]。目前,已經實現Taylor算法在TDOA二維定位中的應用且取得了很好的求解效果,但將Taylor算法在TDOA三維定位中應用時,在某些情況下,Taylor算法會出現大面積無法求解的現象。因此,找到一種更好的求解算法對于實現高精度的三維定位是十分必要且有意義的。

本文對TDOA三維定位的求解算法進行研究,開發(fā)TDOA三維定位算法仿真軟件并對Taylor算法在TDOA三維定位中的應用進行仿真實驗。在分析Taylor算法應用受到限制的基礎上,為實現高精度的TDOA三維定位,本文提出將列文伯格-馬夸爾特(Levenberg-Marquardt,LM)算法作為TDOA三維定位的求解算法來彌補Taylor算法的缺陷和不足,并且在不同的TDOA三維定位模擬環(huán)境中進行仿真實驗,對比Taylor算法和LM算法的性能。

1 Taylor算法在TDOA三維定位中的應用

二維定位只能夠顯示出目標的平面位置,而三維定位可以顯示出目標的空間位置。TDOA三維定位可以實現室內高精度的定位,這需要一種優(yōu)良的求解算法來解算一組TDOA三維定位方程組,而該方程組是由幾個非線性方程所組成,因此可以理解為求解一組非線性方程組。

目前求解非線性方程的典型方法是迭代算法,Taylor算法作為一種典型的迭代算法,在一般情況下均可以求得較為準確的非線性方程組結果。但該方法需要一個初始值作為Taylor算法執(zhí)行的初始點,初始值的選擇需要接近真實值以防止泰勒級數收斂到局部最優(yōu)[14]。若選擇的初始值不恰當,計算量將會增大且可能導致不收斂,將會無法得到移動節(jié)點的準確位置。Taylor算法在TDOA二維定位中取得了良好的求解效果,但將該算法應用到TDOA三維定位時,在定位現場的復雜環(huán)境下其應用受到多種條件的限制,導致不能準確可靠地求得移動節(jié)點的解坐標。針對這一問題,利用TDOA三維定位算法仿真軟件對Taylor算法在TDOA三維定位中的應用進行仿真分析。仿真實驗中,在仿真軟件中設置4個定位基站的初始坐標,主基站A(200,200,200)、從基站B(600,200,600)、從基站C(200,600,200)、從基站D(600,600,200),將移動節(jié)點的Z坐標設置為固定值,層高的設置值就是Z坐標的值,將X坐標和Y坐標的取值范圍都設定為0 cm～800 cm,X、Y、Z的初始點坐標為(0,0,Z),將X和Y的步距設為40 cm,參與定位計算的目標點總共有441個,每當得到一個移動節(jié)點的坐標(X,Y,Z)后,就分別計算(X,Y,Z)到4個基站的距離,進而計算得到距離差,這個距離差在實際定位中是由時間差計算所得。在距離差上加上設定的白噪聲得到新的距離差,利用白噪聲模擬工況下的實際噪聲。再將新的距離差作為已知條件應用到TDOA定位方程組的求解當中,利用Taylor算法計算得到移動節(jié)點的定位坐標(X*,Y*,Z*),用(X,Y,Z)與(X*,Y*,Z*)之間的距離表示定位誤差。

Taylor算法的流程如圖1所示。

圖1 Taylor算法流程Fig.1 Procedure of the Taylor algorithm

1.1 迭代步距對Taylor算法的影響

基站的初始坐標不變,將移動節(jié)點的Z坐標值設定為350 cm,白噪聲的取值范圍設定為-5 cm～5 cm。實驗對Taylor算法在迭代步距分別為0.1、0.3、0.5、0.7、0.9、1.0、1.5時進行仿真,將不同迭代步距下的仿真結果分為20組,在相同條件下,每組進行100次仿真實驗,將100次仿真結果的平均值作為該組最終的仿真結果,結果如圖2、圖3所示。Taylor算法在求解TDOA定位方程組的過程中,求解逆矩陣失敗代表求解失敗,也就意味著不能求得移動節(jié)點的定位坐標(X*,Y*,Z*)。在每一個迭代步距下進行100次仿真實驗,記錄每一次的運行時間,將仿真結果的平均值作為最終結果,如圖4所示。

圖2 求解失敗的點數折線圖Fig.2 Line chart with failed points

圖3 誤差分布折線圖Fig.3 Line chart of error distribution

圖4 運行時間的折線圖Fig.4 Line chart of running time

由圖2可知,在相同的初始條件下,當迭代步距為0.1、0.3、0.5、0.7時,求解失敗的點數較少且相差不大,隨著迭代步距的繼續(xù)增加,求解失敗的點數明顯增加,這說明無法求得移動節(jié)點定位坐標的范圍增大。由圖3可知,隨著迭代步距的增加,定位結果的精度呈降低趨勢。圖2和圖4表明,在誤差范圍允許的情況下,迭代步距越小,可以求得移動節(jié)點坐標的概率越大,但是增加了計算量和計算時間,這說明Taylor算法在TDOA三維定位中的應用在很大程度上受到迭代步距的影響。

1.2 基站布局對Taylor算法的影響

在仿真實驗的基礎上只改變從基站D的坐標為(600,600,600),其他條件保持不變,在相同的層高和噪聲條件下,在每一個迭代步距下進行100次仿真,將仿真結果的平均值作為最終結果。結果發(fā)現,當迭代步距為0.1、0.3、0.5、0.7、0.9、1.0、1.5時,參與定位的441個點全部求解失敗。

在相同的層高與迭代步距條件下,在不同的噪聲下進行100次仿真,將仿真結果的平均值作為最終結果。結果發(fā)現,當噪聲分別為10、20、30、40、50、60、70時,參與定位的441個點全部求解失敗。

仿真結果表明,當基站C和基站D的高度相同時,由于基站布局的變化,Taylor算法在不同的迭代步距及噪聲條件下,參與定位的441個點全部求解失敗,不能求得移動節(jié)點的坐標位置。因此Taylor算法在TDOA三維定位中的應用受到基站布局的嚴重影響。為了降低外部環(huán)境對定位結果的影響,避免出現大范圍求解失敗的現象,提高定位解的精度,本文提出將LM算法作為TDOA三維定位的求解算法并進行仿真驗證。

2 LM算法在TDOA三維定位中的應用分析

對于求解非線性方程得到最優(yōu)解來說,除了Taylor算法以外,典型方法還有梯度下降算法、高斯牛頓算法以及LM算法。

梯度下降算法是求解最優(yōu)化問題的最重要、最基礎的方法,其一般求解步驟為:

步驟2采用xk+1=xk+h進行新的迭代。

步驟3若|G(xk+1)-G(xk)|<ε,其中ε足夠小,則認為G(x)收斂,退出迭代,否則重復步驟1。

在利用梯度下降算法尋找非線性方程的最優(yōu)解時,并不是在任何條件下均可以得到方程的全局最優(yōu)解。該算法的實現存在前提條件,首先,要確保目標函數G(x)是凸函數且是可收斂的,若目標函數G(x)不是凸函數,梯度下降的最終點就有可能不是全局最小點[15]。其次,該算法的收斂速度以及最優(yōu)解的質量受到迭代步距的影響,迭代步距較小時,該算法將會收斂得較慢,而迭代步距過大時,該算法會使得結果偏離最優(yōu)解。

高斯牛頓算法被廣泛應用于非線性方程的求解問題,該算法的邏輯過程是使用目標函數的泰勒級數展開式近似地代替已有的非線性回歸模型,然后循環(huán)迭代、修正參數,直至達到最優(yōu)解或超過迭代限制[16]。高斯牛頓算法的一般求解步驟為:

步驟2采用xk+1=xk+h進行新的迭代。

步驟3若|F(xk+1)-F(xk)|<ε,其中ε足夠小,則認為F(x)收斂,退出迭代,否則重復步驟1。

高斯牛頓算法在求解非線性方程時并不總能保證收斂,要使該算法在求解時收斂,必須保證以下2個條件:

1)F(x)是有界函數。

2)在進行每一次迭代時,雅克比矩陣必須是滿秩的。

當不滿足以上2個條件時,該算法無法保證收斂,且不能得到方程的全局最優(yōu)解。

由于Taylor算法無法滿足所有系數矩陣都為非奇異的情況,梯度下降算法和高斯牛頓算法又受到不同使用條件的限制,因此本文引入新的求解算法——LM算法。LM算法對于求解非線性方程是一個很好的選擇,尤其是在奇異或者非孤立解的情況下[17]。

文獻[18-19]提出一種改進的GN算法,通過添加阻尼因子(LM參數)使得改進的GN算法具有更寬的收斂域,可以解決病態(tài)非線性最小二乘擬合問題,稱為LM算法。傳統(tǒng)LM參數的取值是預先設定的,而文獻[20]提出了一種LM參數更新方法,證明了改進的LM算法具有全局及二次收斂性。LM算法可以通過修改參數達到結合高斯牛頓算法以及梯度下降算法的優(yōu)點,并且不需要固定γ值來確定精度和收斂速度,同時對兩者的不足加以改善,如高斯牛頓算法中逆矩陣不存在時將無法繼續(xù)迭代的問題[21]。LM算法的可靠性優(yōu)于高斯牛頓算法,這意味著在很多情況下,即使從距離實際值很遠的地方開始計算,LM算法也能找到解決方案。LM算法的具體實現過程如下:

步驟1初始化μ0=τ×max{aii},ν0=2。

對于ε1、ε2可以選取一個任意小的值(如10-12),其只是作為迭代的終止條件,對于最終的收斂結果影響不大。

為了驗證LM算法的可靠性、優(yōu)劣性及實用性,在相同條件下分別對Taylor算法和LM算法在TDOA三維定位中的應用進行了仿真。在多徑干擾環(huán)境下,由于在距離差中引入了非視距誤差,如果以CHAN算法的計算結果作為迭代初值,將會引入新的不確定性因素。因此,將基站空間位置中心作為Taylor算法的迭代初始值。

仿真時參與定位計算的總共有441個點,在不同的條件下分別進行100次的仿真實驗并記錄仿真結果,將仿真結果的平均值作為最終結果。其中,N(T)為Taylor算法求解失敗點數的平均值,N(L)為LM算法求解失敗點數的平均值,E(T)為Taylor算法結果誤差平均值,E(L)為LM算法結果誤差平均值,P(T)為Taylor算法的求解率,P(L)為LM算法的求解率。

實驗1基站坐標設置為初始坐標,層高為50,噪聲為10,在不同迭代步距下對Taylor算法與LM算法進行仿真實驗,結果如表1所示。

表1 2種算法在不同迭代步距下的N、E和PTable 1 N,E and P of two algorithms under differentiteration steps

由表1可以看出,隨著迭代步距的不斷增加,Taylor算法中無法求得解坐標的點數和解算結果的誤差平均值均在逐漸增加。LM算法的求解成功率均高于Taylor算法,當迭代步距大于等于0.5時,該算法的誤差值均小于Taylor算法且相對穩(wěn)定,這說明LM算法求得解坐標的質量優(yōu)于Taylor算法的解算結果。因此,與Taylor算法相比,LM算法在迭代步距改變時求解率更高、表現得更加穩(wěn)定,且解算的結果精度也更高。

實驗2基站坐標設置為初始坐標,迭代步距為1.0,層高為50,在不同噪聲下對Taylor算法與LM算法進行仿真實驗,結果如表2所示。

表2 2種算法在不同噪聲下的N、E和PTable 2 N,E and P of two algorithms underdifferent noises

由表2可知,隨著外界噪聲值的增加,Taylor算法和LM算法中求解失敗的點數以及結果的誤差平均值均呈增加的趨勢,且Taylor算法的增加量大于LM算法,同時,Taylor算法求解失敗的點數以及誤差平均值均大于LM算法,但Taylor算法的求解率均小于LM算法。因此,相比Taylor算法,LM算法在不同噪聲條件下求得解坐標的質量優(yōu)于Taylor算法,且求解率更高、精度更高。

實驗3基站坐標設置為初始坐標,迭代步距為1.0,噪聲為50,在不同層高下對2種算法進行仿真實驗,結果如表3所示。

表3 2種算法在不同層高下的N、E和PTable 3 N,E and P of two algorithms under different heights

由表3可知,2種算法對于不同高度上的點的求解效果有明顯的差別。相比在基站空間外的點,當目標點在基站空間內時,2種算法的解算效果相對較好。與Taylor算法相比,LM算法不能完成求解的點數更少,且誤差平均值也更小。這說明LM算法在不同層高條件下求得坐標解的精度更高。

實驗4改變基站D的坐標為(600,600,600),進行以下3種條件的仿真實驗:

1)設置迭代步距為0.5和1.0,噪聲為10,層高為50。

2)設置噪聲為10和50,迭代步距為1.0,層高為50。

3)設置層高為50和100,迭代步距為1.0,噪聲為20。

在上述3種實驗條件下對2種算法進行仿真實驗,結果如表4所示。

表4 改變基站D坐標后2種算法的N、E和PTable 4 N,E and P of two algorithms changingthe D coordinate of the base station

實驗4的結果表明,基站D與基站C的高度相同時,由于基站布局發(fā)生了變化,Taylor算法雖然全部得到了誤差小于1 000的結果,誤差值相對較大,而且得到的全部是偽解算結果及偽成功率,仍然認為求解失敗。但是LM算法只有少數點無法求得解坐標,求解率依然可以保證在80%以上,在這種條件下,LM算法表現出了更好的穩(wěn)定性、可靠性。

3 結束語

本文在模擬不同的工況環(huán)境下,對Taylor算法以及LM算法在TDOA三維定位中的應用進行了仿真實驗,結果表明,Taylor算法在TDOA三維定位中的應用受到迭代步距和基站布局的嚴重影響使得大范圍的目標點無法求得解坐標。相比Taylor算法,在相同條件下,LM算法可以高效地完成TDOA三維定位方程組的求解過程,且求解率更高,解算結果的精度也更高。在不同評價指標方面,LM算法均表現最好,驗證了LM算法在TDOA三維定位中應用的可行性及實用性。目前研究工作均是在獨立單元內的定位,下一步將放在基于TDOA的多單元以及跨單元定位,以驗證LM算法的可靠性與有效性。