一種基于BP-GA的室內定位模型*

王立輝 ，王佳斌

（1.華僑大學 信息科學與工程學院，福建 廈門361021；2.華僑大學 工學院，福建 泉州362021）

室內定位技術按所借助的手段不同可以分為[1-2]基于無線電信號的定位技術、基于紅外線的定位技術、基于超聲波的定位技術、基于藍牙的定位技術、基于激光的定位技術、基于射頻識別技術的定位技術以及基于WiFi的定位技術等。由于室內環境存在非視距、多徑、干擾多變等因素,同時考慮到設備費用和實現的復雜程度等,本文選擇了利用ZigBee技術基于RSSI值的定位算法。

當前，廣泛使用的ZigBee技術無線定位系統主要通過測量節點間的距離來實現[3]。基于RSSI的測距是無線傳感網絡定位技術中較常采用的方法，該類方法大多數通過設置已知參考節點。首先利用待定位節點接收到的RSSI值計算出該節點到各個參考節點的距離，再通過各類定位算法推導出目標點的坐標。傳統的基于RSSI的室內定位技術基本上都是以無線信號傳播模型為基礎的，在不同的定位環境中，通過擬合或直接根據經驗得出無線信號傳播模型中未知參數A和n，再根據一些位置距離算法來最終實現定位。但這些算法過于依賴一些經驗模型，對于不同的環境的適應性不強，在一些室內情況復雜的條件下會有很大的誤差。本文在基于ZigBee組成的網絡的基礎上，使用BP神經網絡和GA算法融合來初步算出待定位物體的位置，再融入泰勒級數定位算法來算出最終待定位物體的位置。

1 RSSI測距原理

無線信號的發射功率與接收功率之間的關系可以用式(1)表示：

式中，Pr是無線信號的接收功率，Pt是無線信號的發射功率，r是收發單元之間的距離，n是傳播因子，數值大小取決于無線信號傳播的環境[4]。

在式(1)兩邊取對數可得：

節點的發射功率是已知的,將發送功率代入式(2)中可得：

式 (3)的左半部分10×lgPr是接收信號功率轉換為dBm的表達式，可以直接寫成式(4)，在式(4)中A可以看作信號傳輸1 m遠時接收信號的功率：

由式(4)可以得到常數A和n的數值決定了接收信號的強度與信號傳輸距離的關系。

由此可以看出，A和n為值直接影響到了根據RSSI值得到的距離，進一步影響到定位的精度。無論是理想環境還是室內環境下，傳輸信號與傳輸距離之間有一定的關系，在實際環境下RSSI值的變化有一定的規律可循，RSSI值與距離d之間是一個連續的非線性關系，而Kolmogorov定理也已經證明[5-6]，任意一連續函數可由一個3層BP網絡來實現，所以可由一個3層的BP網絡來代替RSSI經驗公式來得到RSSI值與d之間的關系，并且可以直接由BP網絡直接得到待測節點的坐標值。

2 BP神經網絡模型的確定

根據RSSI與坐標值之間的一一對應關系，本系統設計由4個參考節點確定一個盲節點位置，所以BP神經網絡的輸入有4個(即4個參考節點到盲節點的RSSI值)，輸出有 2個(x，y)(即盲節點的坐標值)，對于隱含層層數和神經元數的選擇是一個難點，目前還沒有理論上的指導，只有經過大量的實驗來選擇最佳的隱含層層數。

本文采用4:35:2結構的BP神經網絡，如圖1所示。使用相似的方法可以確定出計算RSSI值與d之間關系的BP網絡結構圖,與圖1結構相似，采用1:20:1的結構。傳統的BP神經網絡[6-7]算法確定權重時所采用的學習算法是基于梯度下降的，不可避免地存在著訓練時間長、收斂速度慢、易陷于局部極小值以及完全不能訓練等問題。所以本文結合使用遺傳算法來優化BP神經網絡，改善BP神經網絡的缺陷，使算法避免陷入局部極小值、收斂速度慢等問題。

圖1 用于計算坐標的BP網絡結圖

3 BP-GA算法

在GA每一代進行遺傳操作之前，對群體中的最優個體進行次數較多的BP訓練[8-10]，使最優個體得到足夠的訓練后目標誤差能很快地下降，作為混合學習算法指導誤差下降的主導搜索方向，然后將經BP訓練后的最優個體與群體中的其他個體逐一進行啟發式的交叉式算法，能在最優個體與群體的其他個體所形成的尋優空間中并行尋優，再從交叉子代和經BP訓練后的原最優個體中選出當代最優個體進行下一次的BP訓練。

4 泰勒級數定位算法

泰勒級數定位方法[11-12]是一種基于泰勒級數展開的加權最小二乘估計迭代算法。它適用于所有的定位系統，并利用所有的測量參量來改善定位精度。該方法的核心思想為：(1)在目標位置的初始估計點利用泰勒級數展開，并忽略二次及以上項，將非線性方程變為線性方程，并采用最小二乘算法對偏移量進行估計；(2)利用估計的偏移量修正估計的目標位置，并不斷迭代，使估計的目標位置逼近真實位置，從而得到對目標位置的最優估計。

5 ZigBee定位系統模型

本系統設計的這套二維室內無線定位系統主要由主機、網關、定位節點、參考節點4個部分組成。主機是一臺筆記本電腦，負責處理網關發送的信息，計算出盲節點坐標和顯示盲節點位置等。網關由CC3430組成，負責網絡的組建、節點地址的分配和負責主機與參考節點、盲節點之間的通信等，參考節點由CC2430組成，是位置已知且固定不動的節點。盲節點由CC2431組成，是位置未知的移動節點。

5.1 系統模型定位流程圖

系統總體流程圖如圖2所示。首先建立ZigBee網絡，然后待測節點收到各個參考節點的RSSI值，將RSSI值發送到網關，由網關送入主機中的BP-GA算法計算得到待測節點的初始坐標，將此坐標值確定為送入泰勒級數定位算法的初始值，進行循環泰勒級數展開，泰勒級數定位算法的計算達到要求的精度值后，輸出最終待測節點坐標，發送到監控軟件界面顯示。

圖2 系統模型定位流程圖

5.2 實驗仿真結果分析

由ZigBee網絡中盲節點收集到的各個參考節點到其RSSI值送入到算法網絡中作為輸入，該RSSI值所在節點的實際坐標為輸出標準進行訓練,將得到的初始坐標值送入泰勒級數定位算法中進行二次優化得到最終的盲節點坐標。

首先，選用 4 個參考節點 a、b、c、d，其坐標（0，0）、（0，13）、（7，13）、（7，0）組成一個實驗環境，其中每格為30 cm。在其中隨機選取20個點作為測試點，將這些值分別送入BP算法、BP-GA算法和本文算法，得到盲節點的坐標如圖3所示。

圖3 BP算法結果與實際坐標位置對比圖

圖4 BP-GA算法結果與實際坐標位置對比圖

由圖3、圖 4、圖5可以看出在本文算法用于定位優于單獨使用BP算法或是使用BP-GA算法進行定位。使用本文算法所得到的盲節點坐標值與盲節點的實際坐標值非常接近，較好地克服了定位時環境中的各種干擾因素的影響。

圖5 本文算法測試結果與實際節點坐標位置對比圖

本文通過在ZigBee組成網絡基礎上，通過使用BPGA算法和泰勒級數定位算法相結合的定位方法，并且通過引入BP網絡來代替RSSI經驗公式來得到RSSI值與d之間的關系，避免了對環境中復雜參數A和n的擬合，很好地減弱了環境因素對定位精度的影響，且通過上面的仿真可以發現，只要在一個室內環境中采集足夠多的RSSI值，利用該算法就能夠達到很好的定位精度，誤差能夠控制在30 cm內。

[1]Yu Kengen，SHARP L，GUO Y J.Ground-based wireless positioning[M].Wiley-IEEE Press，2009.

[2]萬群，郭賢生，陳章鑫.室內定位理論、方法和應用[M].北京：電子工業出版社，2012.

[3]呂源，李軍.基于 CC2431的室內定位系統[J].現代電子技術，2009(2)：95-101.

[4]朱明輝，張會清.基于RSSI的室內測距模型的研究[J].傳感器與為系統，2010，29(8)：19-22.

[5]KHOSHGOFTAAR T M，PANDYA A S，LANNING D L.Applicationof neural networks for predicting defects[J].An nals of Software Engineering，1995，1(1)：141－154.

[6]HAYKIN S.Neural Networks[M].Prentice Hall，1998.

[7]陸瓊瑜，童學鋒.BP算法改進研究[J].計算機工程與設計，2007，28(3)：648-649.

[8]陳永龍，何國良，徐宗昌.基于BP-GA的融合算法實現[J].裝備指揮技術學報，2007，18(4)：107-110.

[9]Lu Chun，Shi Bingxue，Chen Lu.Hybrid BP-GA for multilayer feedforward neural network[J].ICECS 2000，2002(2)：958-961.

[10]Li Jianping，BALAZS M E，PARKS G T，et al.A species conserving genetic algorithm for multimodal function optimization[J].Evol Comput.，2002，10(3)：207-234.

[11]張會清，石曉偉，鄧貴華，等.基于BP神經網絡和泰勒級數的室內定位算法研究[J].電子學報，2012，40(9)：1876-1879.

[12]田孝華，周義建.無線電定位理論與技術[M].北京：國防工業出版社，2011.