基于BP人工神經網絡的室內移動定位技術

劉紹剛 李燕梅 李艷平

摘 ?要： 基于無線傳感器網絡的室內定位技術因為室內復雜的環境，傳感器通信存在著多徑效應，無法使用信號強度衰減模型進行精確定位。文中提出基于ZigBee結合Fingerprinting以及遺傳算法優化的BP神經網絡的方法進行定位。實驗結果證明該方法可以用于室內的精確定位，在定位范圍為2 m×2 m的條件下，非訓練點的定位平均誤差為0.22 m。

關鍵詞： 室內定位; BP神經網絡; 遺傳算法; ZigBee; Fingerprinting; 無線傳感器網絡

中圖分類號： TN915.02?34; V271.4 ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）15?0025?04

Indoor mobile positioning technology based on BP artificial neural network

LIU Shaogang1， LI Yanmei1， LI Yanping2

（1. School of Artificial Intelligence & Information Engineering， West Yunnan University， Lincang 677000， China;

2. School of Mathematics and Information Science， Shaanxi Normal University， Xian 710119， China）

Abstract： With the development of wireless sensor network （WSN） technology， it has become important to obtain the location of sensor nodes in the network. Therefore， a large number of indoor positioning technologies based on WSN emerged. The signal strength decay model cannot be used for precise positioning due to the multipath effect of sensor communication in a complex indoor environment. A method based on ZigBee combined with Fingerprinting and BP neural network optimized by genetic algorithm is proposed in this paper. Experimental results show that this method can be used for indoor precise positioning， whose average location error of non?training points is 0.22 m under the condition in the positioning range of 2 m×2 m.

Keywords： indoor positioning; BackPropagation neural network; genetic algorithm; ZigBee; Fingerprinting; wireless sensor network

0 ?引 ?言

近年來，隨著嵌入式技術和無線通信技術的不斷發展，無線傳感器模塊具有更低的功耗，更快的處理速度，每一個無線傳感器模塊都可以獨立地完成一些任務。例如，監測室內的溫度，系統需要知道人在屋內的確切位置，并測得人所在位置的實際溫度，隨后再把人所在位置的實際溫度調整到最舒適的溫度，這樣就可以避免多余的能源浪費。越智能的室內系統就越需要智能體的位置并做出合理的調整，所以室內定位技術[1]變得越來越重要。

在文獻[2?3]中使用信號衰減模型通過接收信號強度指標（RSSI）計算出距離，再使用距離值計算出位置。這種方法簡單易行，在ZigBee發送的數據包中可以直接提取出RSSI值。提取出需要定位節點到周圍至少三個固定節點的RSSI值，計算出需要定位的節點到這三個固定節點的距離，就可以使用三邊定位的方法計算出該節點的坐標。在計算距離時使用理想情況下的信號衰減模型，然而實際室內環境下由于存在各種干擾和多徑效應，使用信號衰減模型不能準確地表示出RSSI和距離的對應關系。所以，用信號衰減模型計算距離存在很大的誤差，再用此距離計算的位置也存在著不小的誤差。文獻[4?5]中使用Fingerprinting系統，將定位劃分為兩個階段，在預處理階段收集預處理點上的鏈路質量指標（LQI）值儲存進數據庫，用BP神經網絡直接擬合LQI和坐標的關系。通過BP神經網絡直接得到LQI和坐標的對應關系，這種方法的好處是沒有使用信號衰減模型，減小了誤差。但是在訓練過程中，沒有將BP神經網絡的訓練樣本分成訓練樣本和檢驗樣本，無法分析訓練是否出現訓練不足或者訓練過度等問題，且只使用BP神經網絡進行訓練易陷入局部最優，而無法陷入全局最優。

根據文獻[6]中的描述，RSSI值在室內的分布是基本不變的。RSSI的分布并不像磁場的分布那樣均勻、規則，在室內環境中，RSSI的分布是不勻稱的、畸形的。在本文提出的定位系統中，使用基于遺傳算法優化參數的BP神經網絡（以下簡稱GA?BP神經網絡）的Fingerprinting方法進行定位。這種方法對于預先訓練的點定位精度高，對于沒有訓練的點定位具有一定的泛化能力。

1 ?定位原理

1.1 ?RSSI

接收信號強度（RSS）是接收信號的能量的量化。顯然，RSS值會隨著設備之間距離的變化而變化。根據Friis自由空間傳輸公式[7?9]接收到的能量會隨著發送與接收設備之間距離的減小而減小。

式中：[PRX]為接收器的接收能量;[PTX]為發送器的發送能量;[GTX]為發送器的增益;[GRX]為接收器的增益;[λ]為無線發射信號的波長;[d]為發送器到接收器之間的距離。

在嵌入式設備中，接收信號強度RSS被轉化為接收信號強度RSSI指標值，如式（2）所示，定義為接收的能量和從參考距離發送來的接收能量的比值。根據式（1）、式（2）可以得出RSSI值和距離成反比。

式中[PRef]為參考接收能量。在基于RSSI的定位系統中，可以使用信號衰減模型把RSSI值轉化為距離值然后定位。也可以使用Fingerprinting的方法，建立RSSI值和與之對應的位置的數據庫來定位。因為在室內環境中使用信號衰減模型不能準確定位，所以選擇Fingerprinting并通過增加預處理點的個數來提高精度。

1.2 ?Fingerprinting

RSSI值會隨著距離的增加而減小，因為各種干擾的原因，這種變化并不規律。Fingerprinting分為兩個階段。Fingerprinting在預處理階段把RSSI的這種不規律的變化，也就是附加干擾的變化儲存進數據庫。在定位階段，使用數據庫里的RSSI和當前的RSSI值進行比對并定位。數據庫里的RSSI擁有根據環境改變而改變的特性，這種特性雖然減小了Fingerprinting方法的魯棒性，但是增加了Fingerprinting在當前環境下的精確性。

2 ?方案設計

ZigBee可以工作在三種模式下：協調器、路由器和終端模式。協調器負責建立網絡并控制著其他節點的入網，建立網絡之后協調器的功能與路由器相同，都是負責數據的中轉。與路由器不同的是終端只能和父節點進行通信，不能和其他節點直接進行通信。

在定位系統中，位置已知的節點為錨節點，位置未知的節點為移動節點，和電腦相連傳送數據的節點為網關，如圖1所示。因為使用星形拓撲結構組網具有結構簡單的特點，并且滿足本文提出的定位系統的要求。所以定位系統的拓撲結構使用星形結構。錨節點只和移動節點發生通信，所以錨節點使用終端。

圖1 ?定位系統網絡拓撲結構

使用如圖1所示的星形網絡，移動節點收集4個錨節點發送來的RSSI值然后傳送到電腦，由電腦計算出移動節點的坐標。采集RSSI值的步驟如下：

Step1：每個錨節點以200 ms的間隔向移動節點發送設備ID號（1～4號）;

Step2：移動節點接收4個錨節點發送來的ID號并從接收數據包中讀出RSSI值，如果沒收集齊就繼續等待;

Step3：移動節點收集到4個錨節點發送來的ID號，將ID號和與之對應的RSSI值發送到網關;

Step4：網關將數據通過串口發送給電腦。

定位數據處理部分分為兩個階段：預處理階段和定位階段。

如圖2所示，四個角落的大圓形代表錨節點，中間的每個小圓形代表一個預處理點。實驗區域為2 m×2 m的正方形，每隔10 cm設一個預處理點。在預處理階段中，將移動節點放置在預處理點上以采集RSSI數據，每個點采集200次，并求出RSSI的平均值，然后將平均值存入數據庫。RSSI平均值和坐標一一對應，如表1所示。

在測得全部361個點的RSSI平均值之后，把RSSI平均值作為BP神經網絡的輸入，與RSSI平均值對應的坐標作為輸出進行BP神經網絡訓練。

圖2 ?實驗區域

表1 ?RSSI值與坐標對應表

BP神經網絡是一種監督學習型人工神經網絡[10]。學習過程是由信號的正向傳播和誤差的反向修正組成的。典型的三層BP神經網絡包括一個輸入層、一個隱含層和一個輸出層。Kosmogorov定理說明在有合適的結構和恰當的權值條件下，三層BP神經網絡可以擬合任意的連續非線性曲線。但是由于RSSI值和坐標之間的對應關系不連續，所以需要使用四層BP神經網絡，其中包含兩個隱含層。在定位系統中一共需要測量4個RSSI值，所以BP網絡的輸入節點為4個。通過4個RSSI值要獲得對應的坐標（[x，y]），因此輸出節點為2個。在設計隱含層的節點數時沒有固定的規范，根據經驗隱含層1節點數為10個，隱含層2節點數為6個。

只使用BP神經網絡進行訓練容易陷入局部最優而無法達到全局最優，將BP神經網絡與遺傳算法結合，可以解決以上問題。在BP網絡的學習過程中，不再使用梯度向下算法，而是使用遺傳算法進行學習。GA?BP網絡訓練流程如圖3所示。GA編碼方式使用實數編碼，如果使用二進制位串的方式，染色體的長度將會過長不利于計算。將四層BP網絡的權值[W1]，[W2]，[W3]，閾值[B1]，[B2]，[B3]依次排列構成一個染色體，這六個參數代表一個BP神經網絡，染色體中的每個值都有一個上限和一個下限，依次作為約束條件，其初始值可以通過隨機數生成。

用BP人工神經網絡進行訓練，最重要的是人工神經網絡的泛化能力，所以需要將樣本分為兩組，一組用作訓練，另一組用作檢驗。理論上訓練誤差會一直減小，但是隨著訓練誤差的減小泛化能力也會變弱，檢驗誤差如圖4所示。

圖3 ?GA?BP網絡訓練流程圖

圖4 ?BP神經網絡誤差關系圖

由圖4可知，網絡誤差呈現先減小再增大的趨勢，也就是出現了訓練過度。可以看到存在一個最佳訓練次數[t0]，在達到最佳訓練次數之前如果停止訓練將出現訓練不足，在達到最佳訓練次數之后還進行訓練，檢驗誤差增大，將出現訓練過度。所以BP神經網絡訓練的關鍵是尋找最佳訓練次數。為了判斷訓練是否出現以上兩種問題，定義誤差函數為：

式中：[（x0i，y0i）]為第[i]個預處理點的BP網絡輸出坐標值;[（xdi，ydi）]為第[i]個預處理點的實際坐標值。把樣本分為兩組，[n]（[n]=0，1，2，…，361）為樣本號，將（[n]%11==0）的樣本組成訓練組，（[n]%11！=0）的樣本組成檢驗組，訓練組數據用來進行BP神經網絡的訓練，檢驗組數據用來確定訓練是否應該停止。在使用遺傳算法時，需要選擇合適的適應度函數，根據適應度函數的值確定父代中優秀的個體。種群中的每個個體解碼成BP網絡的權值和閾值，將訓練組數據和檢驗組數據送入BP神經網絡進行訓練，根據式（3）得到訓練組中每個點的誤差和檢驗組中每個點的誤差，然后對這兩組誤差取平均值[error]。適應度函數選為訓練組平均誤差的倒數，檢驗組平均誤差用作判斷是否達到全局最優，也就是判斷是否達到最佳訓練次數[t0]。

在設計完BP網絡之后，進行GA參數的設定，種群大小設為50，選擇函數為隨機均勻函數，保證每一代中的最佳個體能直接進入下一代。變異函數為Gaussain，改進算法對重點區域的搜索能力。此外，GA的終止條件設為是否達到設定的遺傳代數。

3 ?實驗測試

GA?BP神經網絡訓練結果如表2所示。

表2 ?GA?BP神經網絡訓練結果表

從表2可以看出，1號BP神經網絡與3號BP神經網絡相比出現了訓練不足，2號BP神經網絡與3號BP神經網絡相比出現了訓練過度，因此選擇3號BP神經網絡進行室內定位。

在預處理階段使用的實驗區域上進行定位實驗，將移動節點放在2 m×2 m的實驗區域內，分別測得移動節點的實際位置、定位系統的觀測值，得出定位誤差如表3所示。

表3 ?移動節點定位誤差表

4 ?結 ?論

本文在無線傳感器網絡的基礎上，提出一種基于遺傳算法優化參數的BP神經網絡的室內定位系統。實驗結果證明，這種方法可以用于室內的精確定位，在定位范圍為2 m×2 m的條件下，非訓練點的定位平均誤差為0.22 m。

參考文獻

[1] 汪苑，林錦國.幾種常用室內定位技術的探討[J].中國儀器儀表，2011（2）：54?57.

WANG Yuan， LIN Jinguo. Discussion of several common indoor location techniques [J]. China instrumentation， 2011（2）： 54?57.

[2] CHEN Y T， YANG C L， CHANG Y K， et al. A RSSI?based algorithm for indoor localization using ZigBee in wireless sensor network [C]// Proceedings of the 15th International Conference on Distributed Multimedia Systems. San Francisco： [[s.n.]]， 2009： 70?75.

[3] HALDER S J， PARK J G， KIM W. Adaptive filtering for indoor localization using ZigBee RSSI and LQI measurement [J]. Adaptive filtering applications， 2011（6）： 305?324.

[4] CHEN R C， LIN Y H. Using ZeeBee sensor network with artifical neural network for indoor location [C]// 2012 Eighth International Conference on Natural Computation （ICNC）. Chongqing： IEEE， 2012： 290?294.

[5] YAO Q M， WANG F Y， GAO H， et al. Location estimation in ZigBee Network based on fingerprinting [C]// 2007 IEEE International Conference on Vehicular Electronics and Safety （ICVES）. Beijing： IEEE， 2007： 1?6.

[6] HUANG C N， CHAN C T. ZigBee?based indoor location system by k?nearest neighbor algorithm with weighted RSSI [J]. Procedia computer science， 2011， 5： 58?65.

[7] HUANG X， BARRALET M， SHARMA D. Accuracy of location identification with antenna polarization on RSSI [C]// Proceedings of the International MultiConference of Engineers and Computer Scientists. Hongkong： [s.n.]， 2009： 1?6.

[8] 楊東勇，顧東袁，傅曉婕.一種基于RSSI相似度的室內定位算法[J].傳感技術學報，2009，22（2）：264?268.

YANG Dongyong， GU Dongyuan， FU Xiaojie. An indoor location algorithm based on RSSI similarity [J]. Journal of sensor technology， 2009， 22（2）： 264?268.

[9] 王琦.基于RSSI測距的室內定位技術[J].電子科技，2012，25（6）：64?66.

WANG Qi. Indoor location technology based on RSSI distance measurement [J]. Journal of electronics， 2012， 25（6）： 64?66.

[10] 李敏強，徐博藝，寇紀淞.遺傳算法與神經網絡的結合[J].系統工程理論與實踐，1999（2）：65?69.

LI Minqiang， XU Boyi， KOU Jisong. Combination of genetic algorithms and neural networks [J]. Systems engineering?theory & practice，1999（2）： 65?69.