無線傳感器網絡中基于BP-UKF的室內定位算法

賀 彬 ，呂曉軍 ，張春家 ，楊 波

（1.山西大學 數學科學學院，太原 030006；2.中國鐵道科學研究院 電子計算技術研究所，北京 100081）

無線傳感器網絡中基于BP-UKF的室內定位算法

賀 彬1，呂曉軍2，張春家2，楊 波1

（1.山西大學 數學科學學院，太原 030006；2.中國鐵道科學研究院 電子計算技術研究所，北京 100081）

針對復雜室內環境中的定位噪聲問題，文中提出一種基于BP-UKF的室內定位算法。利用BP神經網絡擬合任意非線性函數的特性訓練樣本集，以確定接收信號強度指示（RSSI）和距離之間非線性關系，進而估計待定位節點與錨節點間的距離；采用三邊定位法計算待定位節點的坐標初始值，并利用無跡卡爾曼濾波（UKF）處理非線性系統方程；通過設距離的估計值為觀測變量，對待定位節點坐標的初值進行精確化處理。仿真試驗結果表明，對于較復雜環境的室內定位，與傳統的定位算法相比較，文中所提BP-UKF算法實現達到更可靠和準確的位置估計。

室內定位；BP神經網絡；三邊定位；無跡卡爾曼濾波；非線性函數；無線傳感器網絡

目前的研究中，基于RSSI的定位算法分為兩類：一類是基于模型的定位如基于路徑損耗模型[4]，由于在不確定且時變噪聲的室內定位環境中，RSSI的準確測量會受到很大的影響，使得在使用某一確定模型進行定位時，距離的估計誤差增大，進而影響對未知節點坐標的估計。另一類是基于映射的定位[5]，該方法是通過已知數據信息建立RSSI與節點間距離的映射關系，雖然在映射關系建立的過程中，需要消耗一定的時間，但克服了基于模型算法的一些局限性，適用范圍較廣，定位更準確。

在基于映射的定位中，神經網絡已經取得非常廣泛的使用，其中BP（back-propagation）神經網絡的優勢尤為明顯[6]。文中使用BP神經網絡對RSSI與距離之間的非線性關系進行擬合。為了更精確化BP神經網絡的定位結果[7]，提出了多種濾波方法如卡爾曼濾波、粒子濾波等[8]。其中，粒子濾波有較大的時間復雜度，不適于能量有限的WSN（wireless sensor network）中，而卡爾曼濾波在噪聲存在的環境下是一種優選的狀態估計器，且運行速度較其他濾波器快[9]。由于在室內環境中噪聲的不確定性，傳統的卡爾曼濾波器已不再適用，文中選擇無跡卡爾曼濾波算法進行定位結果的優化。相比于擴展卡爾曼濾波器，該濾波器不需要對非線性函數進行線性化，因為線性化的過程會導致節點定位不準確。

1 室內定位模型

1.1 BP神經網絡

在此選擇BP神經網絡來擬合RSSI和距離之間的非線性關系。BP神經網絡是神經網絡中使用最廣泛的模型之一，經Kolmogorov定理驗證BP神經網絡可以逼近任何非線性函數[10]。BP算法可以是一個三維結構或更多結構的神經網絡，通過驗證，文中所取三維結構的神經網絡可以達到預設的精度要求，具體包括輸入層、一層隱含層和輸出層，如圖1所示。

圖1 三層BP神經網絡結構Fig.1 Three-layer BP neural network structure

BP神經網絡的訓練過程包括數據的正向傳播和誤差的反向傳播。文中Irss，i為第i個錨節點與所有信標節點之間的RSSI；作為BP神經網絡的輸入向量，試驗中設置4個錨節點即輸入向量的維度為4，如圖所示；相應地，di為節點間的物理距離即輸出向量。大量試驗驗證文中隱含層的神經元數取26。

BP神經網絡的流程如2所示。

圖2 BP神經網絡訓練權值的流程Fig.2 BP neural network training weights flow chart

1.2 三邊定位法

利用三邊定位法，在已知錨節點、未知節點與錨節點間的物理距離的情況下，計算未知節點的坐標以實現定位。即取3個錨節點為圓心，待定位節點i與3個錨節點間的距離為半徑作圓，則3個圓的交點坐標即為未知節點i的估計坐標（Xi，Yi）。一般來說，因為對節點間距離的估計存在偏差，3個圓并不能相交于1個點而是形成一個區域，故很難決定準確的位置尤其是在大的噪聲存在的情況下，如圖3所示。

圖3 三邊定位的原理Fig.3 Trilateration principle

1.3 無跡卡爾曼濾波

取未知節點的坐標值（X，Y）為狀態向量Xk，BP神經網絡的輸出向量即未知節點與錨節點間的距離估計值d為觀測向量Yk，則以上所求的坐標為狀態向量的初始值X0。

考慮非線性系統方程為

式中：Xk∈Rn為狀態向量；Yk∈Rm為觀測向量；Wk-1，Vk-1分別為相互獨立的系統過程噪聲和測量噪聲，均為非加性噪聲并滿足約束：p（W）～N（0，Q），p（V）～N（0，R），其中Q，R分別為兩類噪聲的協方差矩陣。系數矩陣 A=［1， 0 ；0，1 ］T，非線性函數 h（·）為節點間的歐幾里得距離公式。

無跡卡爾曼濾波UKF（unscented Kalman filter）的具體過程如下：

步驟 1 sigma 點集｛χi，i=0，1，2，…，2n｝的選擇。

對k-1時刻的狀態向量Xk-1進行采樣時，取第1 個 sigma點 χ0，k-1=μ，余下的 2n 個 sigma點關于均值對稱，即

其中

式中：μ，Σ分別為狀態向量的均值和協方差矩陣；α，κ，λ分別為3個可調參數。

用sigma點表示k-1時刻狀態向量Xk-1的均值和協方差分別為

步驟2 時間預測階段為

式（6）和式（7）為k時刻的一步預測sigma點集｛χi，k∣k-1，i＝0，1，…，2n｝的計算，并通過加權處理后獲得一步預測狀態向量k∣k-1。 Pk∣k-1為一步預測狀態向量的誤差協方差矩陣。

步驟3 測量值更新階段為

式（10）和式（11）為基于一步預測sigma點集通過非線性觀測方程傳遞，并加權后獲得k時刻的觀測向量估計值k∣k-1。

式（13）和式（14）分別為k時刻觀測向量的協方差矩陣及觀測向量和狀態向量之間的交叉協方差矩陣。

經過計算，測量方程是線性的，因此可以使用與經典卡爾曼濾波器相同的方程實現更新。具體過程如下：

步驟4 設置迭代次數和目標誤差，重復步驟1到步驟3，直至達到預設的目標誤差或迭代次數，最終獲得精確化后的狀態向量，即未知節點的坐標（，）。

2 BP-UKF算法

所提出的BP-UKF算法，首先基于BP神經網絡算法，將RSSI與距離之間的非線性關系通過訓練已知數據信息進行逼近，進而估計待定位節點與錨節點間的物理距離，并在三邊定位法的計算下獲得待定位節點的初始坐標，隨后利用無跡卡爾曼可以應用于非線性系統方程的特性，通過選取合適的迭代次數對坐標初始值進行精確化，以提高算法的定位精度。BP-UKF算法的流程如圖4所示。

圖4 BP-UKF算法流程Fig.4 BP-UKF algorithm flow chart

3 試驗分析

3.1 試驗設計

試驗在寬敞的大廳中進行，由于存在障礙物，選取6 m×6 m的試驗場地如圖5所示。建立坐標系時取該區域的中心為原點，以便于計算。

圖5 試驗現場Fig.5 Experimental background

具體的試驗步驟如下：

步驟1 在圖5所示的試驗場地中，分別放置4 個錨節點 AP1，AP2，AP3，AP4作為發射節點； 將可移動位置的接收節點放置在由錨節點圍成的區域內，用于采集收發節點之間的RSSI。

步驟2 打開發射節點和接收節點，用上位機發送指令修改發射節點的本地時間，使4個發射節點實現時間同步；在上位機保存一段時間內收集到的RSSI值；移動接收節點在29個不同位置，并選取RSSI穩定后的200個RSSI值建立數據集，記RSSI數據集為，其中：i=1，2，…，200； j=1，2，…，29。

步驟3 對RSSI數據集進行均值濾波處理，作為 BP 神經網絡的訓練集， 記為 T=｛（Irss1，d1），（Irss2，d2），（Irss3，d3），（Irss4，d4）｝。

步驟 4 在區域內選取［X，Y］＝［-2，-1；-1，0］為待定位節點，將上位機接收到的Irss作為BP-UKF算法的輸入值，并輸出坐標估計值［，］及相應的坐標定位誤差

步驟5 比較BP神經網絡與傳統的模型定位算法對非線性函數的擬合程度，選擇距離估計誤差MSEdis為判斷依據并進行分析。

步驟6 為了驗證精確化階段UKF算法的定位精度優于擴展卡爾曼濾波EKF（extended Kalman filter），使用EKF算法對未知節點的初始坐標值進行優化，并獲得估計坐標［X″，Y″］及相應的定位誤差

3.2 數據分析

3.2.1 BP神經網絡與傳統定位算法的定位性能

在室內環境中RSSI易受到干擾、反射等外界因素的影響，并而影響定位性能。固定1個接收節點，移動發送節點，使發送節點和接收節點間距離的變化范圍為1～18 m，移動間隔為1 m且在每個位置的采樣次數為200，在均值濾波處理后繪制距離和帶有噪聲的Irss測量值之間的非線性函數關系。獲得該環境下的路徑損耗函數Irss=A-10nlgd的系數為A=-45，n=2.68，同時根據確定系數的路徑損耗函數繪制出RSSE的理想值，如圖6所示。

由圖6可見，在室內環境下，RSSE測量值很容易受到環境的影響。直接使用傳統的定位方法可能帶來大的定位誤差，且路徑損耗函數的系數隨著定位環境的改變而變化，需要進行實時更新。

BP神經網絡與傳統定位算法的定位誤差見表1。分析可知，BP神經網絡對Irss與距離之間非線性的擬合度，相較于傳統的定位函數更精確，待定位節點的坐標估計更加可靠。

圖6 室內定位性能分析Fig.6 Indoor positioning algorithm performance analysis

表1 兩種算法的定位誤差Tab.1 Positioning errors of the two algorithms

3.2.2 兩種算法對未知節點坐標精確化的作用

取卡爾曼濾波器的狀態估計誤差協方差，測量噪聲與過程噪聲協方差的對角線元素分別為10-4，10-7，50。從算法運行的時間復雜度和定位誤差兩方面，分析BP-EKF與BP-UKF的性能。

（1）時間復雜度的不同

因為傳感器節點的能量有限性，運行時間復雜度成為一個重要的衡量標準。對于BP-UKF和BPEKF算法，只需考慮EKF算法和UKF算法對初始坐標精確化過程的時間損耗。在不同的迭代次數下，2種定位算法所需時間如圖7所示。

圖7 不同迭代次數下EKF與UKF的運行時間Fig.7 Running time of EKF and UKF under different iterations

由圖可見，隨著迭代次數的增加，UKF和EKF 2種算法的運行時間都增加，但在相同的迭代次數下，UKF算法的運行時間明顯小于EKF算法2個量級。所以，在時間損耗方面，UKF算法優于EKF算法。

（2）定位誤差的分析

在不同的迭代次數下對EKF和UKF算法的精確化性能進行比較，仿真結果如圖8所示。

圖8 不同迭代次數下算法的位置估計誤差Fig.8 Position estimation error of algorithm under different iterations

圖8 中，EKF和UKF 2種算法的定位誤差分別為0.1561，0.1882；BP-EKF算法甚至增大了三邊定位算法的初始估計誤差；在迭代次數最大取10的情況下，BP-UKF算法便可很大程度地提高定位準確度。

3.2.3 坐標初始值對UKF算法定位精度的影響

為了更直觀地分析BP-UKF算法中坐標初始值的選擇對定位精度的影響，在10 m×10 m的區域內隨機生成50個節點，并使用路徑損耗函數獲得噪聲為5的RSSI數據集；取4個待定位節點，且未知節點的RSSI已知；狀態估計誤差協方差、測量噪聲與過程噪聲協方差取值為3，5，0.1；分別使用EKF和UKF，對該初始坐標進行精確化，與初始坐標為任意小值［0.1；0.1］作對比。大量試驗表明，BP-UKF算法中使用三邊定位法初始化坐標的方法，大大減少了濾波算法的迭代次數，更加驗證了BP-UKF算法的有效性。

圖9 不同初始坐標下EKF與UKF的定位誤差Fig.9 Positioning error of EKF and UKF under different initial coordinates

由圖 9 可見，設置［0.1；0.1］為坐標初始值，隨著迭代次數的增加則算法的定位誤差不斷減小，充分體現了卡爾曼濾波算法的性能，且在迭代15次后才能達到與三邊-KF算法同等的定位精度。經大量試驗驗證，當過程噪聲協方差的取值不等于RSSI的噪聲協方差時，為達到與三邊-KF算法同等定位精度，［0.1；0.1］-KF算法需要的迭代次數遠大于BP-UKF算法，很顯然，BP-UKF算法中的坐標初始值的選擇方法有較小的時間復雜度。

4 結語

文中提出BP-UKF定位算法，首先利用BP神經網絡可以擬合任意非線性函數的特性，確定更加準確的Irss和距離之間的關系，進而通過量測的RSSI獲得未知節點與錨節點間的距離，并用三邊定位法估計未知節點的初始坐標，然后進一步采用無跡卡爾曼濾波算法對三邊定位獲得的坐標初始值進行精確化。BP-UKF算法一方面提高了對Irss與距離之間的非線性函數的擬合程度，對節點間距離的估計更加準確，另一方面選擇無跡卡爾曼濾波對坐標的初始值進行精確化，降低了在擴展卡爾曼濾波中因為線性化導致的節點定位的估計偏差。同時，無跡卡爾曼濾波有較小的時間復雜度，適合應用到有限計算的無線傳感器網絡中。經過大量仿真試驗驗證了該算法的有效性。該算法具有一定的應用前景

參考文獻：

[1] Qinghua L，Yu P，Junbao L，et al.RSSI-based localization through uncertain data mapping for wireless sensor network[J].IEEE SENSOR JOURNAL，2016，16（9）：3155-3162.

[2] Bensky A.Wireless positioning technologies and applications[J].Artech House，2016，9（6）：218-268.

[3] Malyavej V，Kumkeaw W，Aorpimai M.Indoor robot localization by RSSI/IMU sensor fusion[C]//Proc 10th Int Conf Electr Eng/Electron，Comput，Telecommun.Inf Technol，2013：1-6.

[4] YedavalliK，KrishnamachariB，RavulaS，etal.Ecolocation：a sequence based technique for RF localization in wireless sensor networks[C]//Proc Fourth Int Symp Information Processing in Sensor Networks.2005：1-8.

[5]Chen L-H，Wu E H-K，Jin M-H，et al.Homogeneous features utilization to address the device heterogeneity problem in fingerprint localization[J].IEEE Sensors J，2014，24（4），998-1005.

[6] Liu R，Sun K，Shen J.BP localization algorithm based on virtual nodes in wireless sensor networks[C]//6th International Conference on Wireless Communications Networking and Mobile Computing.2010：1-4.

[7] Yang Y，Zhao Y，Kyas M.A grid-scan maximum likelihood estimation with a bias function for indoor network localization[C]//International Conference on Indoor Positioning and Indoor Navigation.2014：1-9.

[8] Xiao Q，Xiao B，Bu K，et al.Iterative lo calization of wireless sensor networks：an accurate and robust approach[J].IEEE/ACM Trans Netw，2014，22（2）：608-621.

[9] Fang X，Jiang Z，Nan L，et al.Noise-aware localization algorithms for wireless sensor networks based on multidimensional scaling and adaptive Kalman filtering[J].Computer Communications，2017，101：57-68.

[10]Haykin S.神經網絡原理[M].葉世偉，史忠植，譯.北京：機械工業出版社，2004.

Indoor Localization Algorithm Based on BP-UKF for Wireless Sensor Network

HE Bin1，LV Xiao-jun2，ZHANG Chun-jia2，YANG Bo1
（1.School of Mathematical Sciences，Shanxi University，Taiyuan 030006，China；2.Institute of Computing Technologies，China Academy of Railway Sciences，Beijing 100081，China）

In order to solve the localization problem at the complex interior environment，indoor localization algorithm based on BP-UKF algorithm is proposed.This algorithm uses the BP neural network algorithm to obtain the relationship between the distance and Received Signal Strength Indication（RSSI） accurately by use of the characteristic in fitting any no-linear function.Then the distances between the unknown nodes and anchor nodes can be calculated.The coordinates of the nodes are initialized by using the trilateration with those distances.It uses the unscented kalman filter algorithm to deal non-linear system equation.The initial value of the coordinates of the positioning node is treated accurately by the estimated value of the distance as the observation variable.The result of simulation shows that BP-UKF algorithm can achieves reliable and accurate solution in interior environment than the traditional positioning algorithm.

indoor localization；BP neural network；trilateration；unscented kalman filter；non-linear function；wireless sensor network（WSN）

在室內定位研究中，基于接收信號強度指示[1]RSSI（received signal strength indication）的室內定位算法受到廣泛的關注，但是基于RSSI的定位精度易受到多徑效應、陰影衰落等影響[2]，使得室內定位技術向著更低能耗、更少實施成本、更好可測量性，以及更高定位精度等方向展開研究[3]。

TP183

A

1001-9944（2018）04-0071-05

10.19557/j.cnki.1001-9944.2018.04.017

2017-12-18；

2018-02-26

國家自然科學基金項目（U1334210，U1334210，61374059，61573230）

賀彬（1994—），女，碩士，研究方向為卡爾曼濾波、神經網絡。