基于最小二乘法和BP神經網絡的TOA定位算法

浦佳祺，陳德旺

(1.福州大學 數學與計算機科學學院，福建 福州 350108； 2.福州大學 軌道交通研究院，福建 福州 350108)

1 概 述

在戶外的應用場景中，GPS定位技術已經得到了廣泛的使用[1-2]。而到了室內，由于室內遮擋物對信號的影響，另一方面室內定位的精度要求比室外高，因此無法滿足室內定位的需求。所以室內無線定位技術受到了重視并有了長足進展，例如：RFID定位[3]、超聲波定位[4]、WIFI定位[5-6]等。

從技術角度來看，現代商用通信網絡對于三維定位的需求，是使用盡可能少的基站完成對終端設備的定位、算法收斂速度快、對干擾和噪聲具有魯棒性等。相比于GPS等商用衛星定位系統，基于通信基站的定位問題具有如下特殊性：通信基站的目標區域是GPS等衛星定位系統無法實現定位的場景。在高樓林立的城區，建筑物內部、地下停車場等區域，GPS等系統是無法滿足定位需求的。而這些應用場景基站、終端密集，是基站定位可以實現突破的地方。

常用的定位技術有到達時間(TOA)、到達時間差(TDOA)、角度到達(AOA)和接受信號強度(RSSI)等[7]。其中對TOA模型的解法有最小二乘法[8]等經典算法。而對TDOA模型，有Chan算法[9]等經典算法進行求解。對RSSI，則有BP神經網絡對其進行研究[10-11]。

由于通信基站所處的電磁信號環境較之GPS等系統更加復雜，以室內環境為例，無線電信號的傳播過程中會經過墻面的多次反射、室內物體的折射和吸收等。這些物理因素會導致通信基站測量得到的諸如距離、角度等信息存在噪聲而產生非視距的環境。基于這些有噪聲的測量，得到對于位置信息的準確估計，也是通信基站實現對終端定位需要解決的問題。對于TDOA的實現算法主要有Chan算法、Fang算法[12]和Taylor算法[13]。而這些算法的不足之處在于，Fang算法不能充分利用多個基站提供的冗余信息；Taylor算法需要一個與實際位置接近的初始值，并且運算量較大；Chan算法雖然計算快捷，但是在非視距(NLOS)環境下定位性能顯著下降。而在改進方法中，有一種方法是基于Elman神經網絡，對NLOS誤差進行修正,再利用Chan算法定位[14]。

對此，文中提出了一種在NLOS環境下的改進算法。先通過最小二乘估計來減小NLOS環境中數據的噪聲，并且獲得一個與實際位置接近的初始值。之后運用BP神經網絡通過訓練學習，再次優化所得到的結果，從而獲得最終結果。

2 算法說明

該算法考慮從減少TOA的噪聲方面入手，主要由兩部分組成。第一部分通過最小二乘法先去除部分NLOS環境下的噪聲，第二部分通過BP神經網絡訓練對最后的模型進行修正。

2.1 誤差項估計

考慮在非視距環境下，在極大似然估計法中基站BSi到移動端MS的距離di存在多種噪聲誤差，包括時間同步噪聲、非視距環境噪聲等，但是其主要因素應該為非視距環境噪聲。TDOA/TOA測量誤差的正均值通常具有隨移動臺與基站之間距離線性增加的趨勢[15]。所以考慮在極大似然估計法中引入一個線性誤差項：

di=di,real+M·di+N

(1)

其中，di,real表示第i個基站BSi到移動端MS的真實距離；M·di+N為一個線性誤差項。則最小二乘法的公式轉化為如下形式：

(2)

對應的方程組變為：

AX=b'

(3)

其中

(4)

X=(x,y,z)T

(5)

(6)

在保證基站個數大于6的情況下，求解上面的式子可以得到初始值(x,y,z)和線性誤差項的系數M,N，這樣就獲得了所需要的數據。

2.2 基于BP神經網絡的定位誤差修正

BP神經網絡的多層前饋網絡應用最為普遍的是單隱層網絡，己經證明單隱層的神經網絡可以模擬任何連續函數。考慮定位模型的復雜度并不是太大，并且經過實驗驗證后，選取單隱層的三層神經網絡結構作為建立的模型。

基于BP神經網絡的定位誤差測量值修正模型，輸入層3個神經元的輸入為前面一部分用帶誤差項的極大似然估計得到的定位的三維坐標，輸出層也由3個神經元構成,為修正后得到的最終定位的三維坐標。其中有一個單隱層，wij為輸入層與隱藏層之間的權值矩陣，wjk為隱藏層與輸出層之間的權值矩陣。之后通過訓練來修改對應的權值，以逼近想要的連續函數。

3 數據集和算法參數設置

3.1 實驗平臺及數據集說明

文中使用的軟件為Matlab R2014a。數據集來自華為公司提供的TOA定位數據。每個場景下的數據集包括：該場景下基站的個數，每個基站的三維坐標，每個終端在該場景中每個基站記錄的TOA時間。

測試數據包括5組不同場景下的TOA數據，給定的基站的x,y軸的范圍是-400～400 m，z軸的范圍為0～6 m。分別給20，30，40，50，60個基站的5組數據，對應每個場景分別包含1 000，1 100，1 200，1 300，1 400個移動端定位信息。

3.2 定位流程

首先對給定的數據進行預處理，用極大似然法，獲得一個初步定位后的三維坐標。然后輸入BP神經網絡進行訓練，獲得最終的定位模型。

BP神經網絡的實驗利用Matlab的神經網絡工具箱，在測試大量的參數(如隱層的節點數、隱層的個數等)后，實驗參數設置為：隱層激活函數sigmoid，隱層節點個數10，單隱層。

對于5組不同場景下的數據，把這些數據抽樣隨機劃分為兩個獨立的數據子集，一部分作為訓練數據集，占總數據的70%，另一部分作為驗證數據集，占30%。

4 實驗結果分析與比較

為了驗證實驗結果，利用統計學中的均方根誤差來檢驗模型的有效性。

RMSE=

(7)

首先對加入誤差項的極大似然估計法與未加入誤差項的極大似然估計法之間的均方根誤差進行對比，如表1所示。

表1 極大似然估計法誤差對比

從表1可以看出，加入線性誤差項后的定位精度大大增加。不過定位誤差還是超過10 m以上，仍不滿足一般情況下的定位要求，所以有進一步減小誤差的可能。

之后對上一步得到的結果隨機劃分為70%的訓練集和30%的測試集，每個場景分別對這些訓練集進行10次訓練，訓練結果的均方根誤差如圖1所示。

可以看到，對于訓練結果，除了第五組的場景，其他場景的訓練誤差都小于0.5 m。而就算是訓練結果最差的第五組，其訓練誤差也不超過1 m，說明訓練效果較好。并且對每個場景而言，10次訓練結果的波動范圍不大，說明訓練有較好的穩定性。同時通過對場景一中訓練集的第1次測試結果的誤差分布可知，場景一中的測試集的點數總計為770個，其中有超過半數的三維坐標誤差平方和小于0.5 m，大致有600個點的誤差平方和小于1，說明BP神經網絡對于誤差的訓練十分之有效。

圖1 各個場景下BP神經網絡訓練后的誤差

對于每個場景，每組實驗得到的測試結果如圖2所示。可以看到，測試結果與訓練結果基本上相近。除了第五組的測試誤差較大，其他各個場景的測試誤差都比較接近，最大的測試誤差也小于1 m，可見BP神經網絡有效修正了初次定位后的誤差。

圖2 各個場景下BP神經網絡測試后的誤差

同時通過對場景一中測試集的第10次測試結果的誤差分布，場景一中的測試集的點數總計為330個，其中有超過半數的三維坐標誤差平方和小于0.5 m，大致有300個點的誤差平方和小于1。可以看出，BP神經網絡對于誤差的訓練十分有效。其他各個場景和每次實驗的測試數據的誤差平方和也與之類似，大部分的誤差值都小于1 m，個別測量點的誤差大于1 m以上，所以就不一一展示了。

然后將定位算法的實驗結果分別與Chan算法和加入誤差項的極大似然估計法進行了比較。由于BP神經網絡的隨機性，文中算法的均方根誤差使用之前10次實驗的平均值作為其最后的誤差平方和。具體結果如圖3所示。

圖3 三種方法的誤差比較

三種方法在各個場景下具體誤差值的比較如表2所示。

表2 三種定位方法的均方根誤差值

很明顯可以看出，文中算法相比經典算法，效果有著顯著的提升，能夠有效地把誤差縮減到1 m甚至更低。這應該主要歸功于BP神經網絡強大的連續函數逼近能力，通過訓練有效地消除極大似然定位中的誤差。

最后對不同場景下測得的模型是否具有通用性進行了測試。對每個場景的模型分別用了另外4組場景的測試集進行測試，并且做了對比，選取場景五下的誤差，具體如圖4所示。

圖4 場景五模型的測試集誤差

從圖4可以看出，在其他場景模型下，即使是不同場景的測試數據最后的定位誤差都小于2 m，與其他兩種算法相比，精確度也較高。在通過BP神經網絡的訓練后，提高了算法針對不同環境的普適性。所以可以通過這種方式來忽略場景的影響。

5 結束語

提出了一種基于最小二乘估計和BP神經網絡的混合定位算法，該算法利用神經網絡的強大非線性映射能力,修正在NLOS環境下最小二乘法的定位誤差,增大了定位精度。實驗結果表明，該算法定位精度高，可靠性好，定位性能好于最小二乘法和Chan算法，并且具有較強的抗NLOS誤差能力，提高了針對不同環境的普適性。

參考文獻：

[1] BAJAJ R,RANANWEERA S L,AGRAWAL D P.GPS:location-tracking technology[J].Computer,2002,35(4):92-94.

[2] PIKANDER M,ESKELINEN P.Differential GPS dynamic location experiments at sea[J].IEEE Aerospace and Electronic Systems Magazine,2004,19(4):36-39.

[3] JO M,YOUN H Y.Intelligent recognition of RFID tag position[J].Electronics Letters,2008,44(4):308-309.

[4] 王 凡,彭 勇.基于TDOA的室內超聲波定位方法的改進[J].計算機技術與發展,2014,24(6):250-252.

[5] 肖金紅,劉 智,楊 陽,等.基于CDMA-TDOA的室內超聲波定位系統[J].吉林大學學報:信息科學版,2012,30(2):213-217.

[6] 黃華晉,秦建息.基于三角定位算法的WiFi室內定位系統設計[J].廣西科學院學報,2016,32(1):59-61.

[7] 范平志,鄧 平,劉 林.蜂窩網無線定位[M].成都：電子工業出版社,2002:80-91.

[8] 孫 瑜．射頻識別(RFID)室內定位算法研究[D].成都：西南交通大學，2005.

[9] CHAN Y T,HO K C.A simple and efficient estimator for hyperbolic location[J].IEEE Transactions on Signal Processing,1994,42(8):1905-1915.

[10] 王 千,金 光,鈕 俊.一種基于RSSI的混合定位算法[J].傳感技術學報,2015,28(12):1823-1829.

[11] 蘭雪梅,朱 健,黃承明,等.BP網絡的MATLAB實現[J].微型電腦應用,2003,19(1):6-8.

[12] FANG B T.Simple solutions for hyperbolic and related position fixes[J].IEEE Transactions on Aerospace & Electronic Systems,1990,26(5):748-753.

[13] FOY W H.Position-location solutions by Taylor-series estimation[J].IEEE Transactions on Aerospace & Electronic Systems,1976,12(2):187-194.

[14] 吳燕紅,關維國,王艷峰.基于Elman神經網絡的TDOA定位算法[J].計算機應用,2011,31(3):629-631.

[15] 楊洪娟.蜂窩網絡無線定位技術的研究[D].哈爾濱：哈爾濱工業大學,2009.