基于改進BP神經網絡的室內無線定位方法

劉曉晨　張　靜

(上海師范大學信息與機電工程學院　上海 200234)

?

基于改進BP神經網絡的室內無線定位方法

劉曉晨張靜*

(上海師范大學信息與機電工程學院上海 200234)

摘要針對在室內無線定位中采用加權質心定位法時精度較低且難以克服信號不穩(wěn)定的問題，提出改進的BP神經網絡方法。以接收信號強度(RSSI)為輸入、二維平面坐標為輸出建立網絡結構，網絡的初始權值和閾值用思維進化算法優(yōu)化，并用邊長3 m的正方形區(qū)域內的196個樣本數據訓練。實驗結果表明，在27個預測點上可達到定位精度0.1 m。相比于BP網絡以及BP網絡和遺傳算法的結合算法，該定位方法訓練收斂時間短，定位結果穩(wěn)定。

關鍵詞室內定位BP神經網絡思維進化算法接收信號強度指示

0引言

在一般室內辦公場景下進行的無線定位方法主要依賴于無線傳感器節(jié)點所接收的信號強度(RSSI)，往往通過路徑損耗模型獲得定位信息。由于室內障礙物的遮蔽，多徑效應和室內環(huán)境的多樣性，會導致信號強度波動較大，而且距離估算不準，這極大地影響了定位精度。針對室內環(huán)境的無線定位方法通常是加權質心定位法，但其定位精確還不高。在這種算法中，路徑損耗系數對定位精度的影響至關重要。文獻[1]提出了差分修正算法來提高定位精度；文獻[2]提出動態(tài)獲取路徑損耗指數，這樣能夠反應巷道不同區(qū)域對信號衰落的影響，然后利用加權質心的方式計算待定位節(jié)點的位置。在實驗室走廊環(huán)境下，定位誤差為1m。

文獻[3]對信標節(jié)點所構成的幾何圖形進行更細致的區(qū)域劃分，用修正的質心算法提高了定位精度，在邊長為6m的等腰直角三角形中的定位精度為1m。

采用計算智能方法對RSSI處理具有一定的容錯能力并改善定位精度。文獻[4]利用位置傳感器節(jié)點在工廠環(huán)境下室內定位，采用一種線性伙伴式神經網絡通過Hebb學習規(guī)則訓練，減小了多徑效應對定位精度的影響，在20m×10m的環(huán)境中定位誤差為0.5m。文獻[5]在RFID設備的定位系統(tǒng)中采用BP神經網絡定位，它以接收器的RSSI為輸入和位置坐標為輸出，用最小均方誤差估計來克服算法收斂速度慢和易陷入局部極小點的不足。同時增加RF發(fā)射器的數量來提高定位精度，它在576m2的區(qū)域中達到定位精度1.75m。文獻[6]提出分別建立5個BP神經網絡，各自將4個接收器節(jié)點的RSSI值進行組合作為5個BP網絡的輸入，利用遺傳算法優(yōu)化BP神經網絡來改善定位精度。文獻[7]提出廣義回歸神經網絡(GRNN)和加權質心聯(lián)合定位的方法，定位精度為1m左右。文獻[8]利用BP網絡建立移動節(jié)點位置與接收信號強度指示(RSSI)和鏈路質量指示(LQI)之間的關系，在11m×6m的環(huán)境中平均定位精度為1.33m。

本文結合一套四個信標節(jié)點和一個待定位接收節(jié)點的無線定位裝置，采用改進的BP神經網絡來學習RSSI和兩維位置信息間的非線性映射，同時應用思維進化算法優(yōu)化網絡的初始權值和閾值。該方法可以有效地提高定位精度，加快BP神經網絡的收斂速度。

1無線定位模型

通常的室內無線定位場景是利用RSSI得到距離值，然后用該距離值為半徑以信標節(jié)點為圓心畫圓，多個圓的重疊部分為待定位節(jié)點可能所處的位置。定位結果可通過加權質心定位法采用式(1)得到：

(1)

其中，xi和yi為相交圓的交點位置坐標，ωi加權系數，該系數通常隨信標節(jié)點與待定位節(jié)點間的距離增加而減小，m是信標節(jié)點的個數。

由于無線電磁波在室內具有反射、折射等多種傳播路徑，導致距離與損耗的關系比較復雜，會隨室內環(huán)境的布局不同而有較大差異。一般情況下，用RSSI來推算距離時，由經驗路徑損耗模型得出，即：

(2)

其中，d為所推算的待定位節(jié)點距離，n為路徑損耗系數，A為1m處的參考接收信號強度，RSSI是待定位節(jié)點處的接收信號強度。

式(2)表明，n的大小極大地影響到距離推算，將直接影響定位精度。在不同的室內環(huán)境下應憑經驗選擇不同的值。但不論怎樣選擇，都不能使在不同位置處的信標節(jié)點都達到較佳的情況，即RSSI信息存在較大的波動性。同時，距離是經由RSSI推算出來的，在推算過程中會丟失RSSI原始數據所包含的一些信息。因此，本文在設計BP神經網絡結構時，考慮到這些因素后，直接采用RSSI作為輸入，待定位節(jié)點的二維位置信息作為輸出。利用BP神經網絡的函數逼近能力來建立如下函數關系：

(x,y)=f(RSSI1,RSSI2,…,RSSIm)

(3)

其中，RSSIi，i∈(1,m)為待定位節(jié)點處的來自各信標節(jié)點的RSSI。

2思維進化優(yōu)化BP的定位原理

RSSI和位置坐標間的非線性映射可通過人工神經來擬合。BP神經網絡[9]能以任意精度逼近一個非線性映射，但式(3)的無線定位模型比較復雜，而且RSSI樣本的波動幅度較大，很難得到較小的訓練誤差，還存在易陷入局部極小點導致定位精度不高的問題。而思維進化[10](EC)算法具有較強的全局搜索和優(yōu)化能力，該算法主要包括種群初始化、趨同、異化等操作，具有魯棒性強、并行分布處理的特點。因此本文將EC算法應用于BP神經網絡中來改善BP易陷入局部極小點的問題，以更好的擬合性能來建立式(3)的函數關系。

改進的BP神經網絡結構如圖1所示。它為一個三層前向網絡，輸入層節(jié)點的個數為待定節(jié)點可接收的來自信標節(jié)點的RSSI個數，輸出層節(jié)點個數為2，分別為二維坐標x和y，隱層節(jié)點個數可依據經驗公式適當選擇。同時該網絡結構中利用EC算法來優(yōu)化BP神經網絡的所有初始權值和閾值。定位處理過程包括四個階段：樣本數據采集、EC算法的離線優(yōu)化、BP神經網絡的訓練和預測定位。在數據采集階段，根據定位區(qū)域的大小以及所要求的定位精度，并設置信標節(jié)點個數以保證定位精度。設置適當個數的網格點作為樣本采集位置，將待定位節(jié)點處于網格點時的RSSI值為樣本輸入，網格節(jié)點處的精確位置作為期望輸出。由于RSSI值有一定波動，可適當取平均值處理。在離線優(yōu)化階段，將網格點的樣本輸入和期望輸出分別作為思維進化算法的輸入和輸出。BP神經網絡的初始權值和閾值通過初始種群產生后，運用趨同、異化等操作計算出最優(yōu)值。然后將此最優(yōu)值作為BP網絡的初始權值和閾值。在訓練階段，按常規(guī)的反向傳播學習算法訓練網絡，使BP網絡的訓練誤差達到要求。在預測定位階段，將待定位節(jié)點放置于區(qū)域內的隨機位置，預測實際定位結果。

圖1　改進的BP神經網絡結構

3思維進化算法優(yōu)化BP網絡過程

運用EC算法對BP神經網絡的初始權值和閾值進行全局尋優(yōu)，其流程如圖2所示。

圖2　思維進化算法流程圖

它主要有以下幾個步驟：

(1) 初始種群的產生

在確定了BP神經網絡的結構后產生初始種群。設網絡的輸入層、隱層、輸出層的節(jié)點個數分別為q1、q2和q3，則需優(yōu)化的初始權值和閾值的個數為j=(q1+1)(q2+(q2+1)×q3。隨機產生50～200個個體作為初始種群，每一個個體都包含所有的初始權值和閾值。再將這個初始種群平均分為若干個子種群，設每個子種群里的個體數目為k，則可將一個子種群表示為信息矩陣：

(4)

此信息矩陣P的每一行代表一個個體，分別由輸入層與隱層節(jié)點之間的權值和隱層與輸出層間節(jié)點的權值以及隱層節(jié)點的閾值和輸出層節(jié)點的閾值組成。

(2) 計算個體的得分值

對子種群中的個體l，l∈(1,k)所代表的權值和閾值計算網絡的實際輸出，用實際輸出y(l)與期望輸出d(l)的差值函數作為得分函數，例如：

(5)

個體的V值越大，則個體所代表的權值與閾值越好。

(3) 權值和閾值的趨同過程

將初始種群中的所有個體按照得分值從大到小排序，依次選擇得分值高的個體作為優(yōu)勝個體和臨時個體，其個數分別記為f和r。 再分別以每一個優(yōu)勝和臨時個體為中心，以正態(tài)分布的方式產生若干個新個體，形成f個優(yōu)勝子種群和r個臨時子種群，每個子群體依然包含k個個體以保證種群規(guī)模不變。該正態(tài)分布N(μ,σ2)中的中心μ為優(yōu)勝個體所在的位置，而σ2的選擇需要通過試驗方式確定。當σ2選擇得太小則搜索范圍過小，可能搜索不到最優(yōu)解，當σ2選擇得過大則會降低算法的效率。

優(yōu)勝子種群和臨時子種群中的個體分別位于優(yōu)勝個體和臨時個體的周圍。將這些種群中的個體再帶入神經網絡中計算實際輸出并求得分值，然后再選擇優(yōu)勝個體和臨時個體。若新選擇的優(yōu)勝個體的得分值比原來的優(yōu)勝個體得分值低，則保留原來的優(yōu)勝個體。經過若干次的搜索未找到比優(yōu)勝個體得分值大的個體，則表明此種群已經成熟。成熟的種群內的最優(yōu)勝個體是在趨同過程中產生的最優(yōu)權值和閾值。對臨時子種群的操作過程一樣。這個趨同操作是子群體內的尋優(yōu)過程。

(4) 異化過程

待優(yōu)勝子群體和臨時子群體成熟以后，將兩個群體中的所有子種群進行全局競爭，即比較其得分值。被替換的子群體或臨時子群體數量不足時，按照上述步驟重新形成新的臨時子群體，并參與全局競爭。

4實驗過程及結果分析

本文的實驗環(huán)境為正方形3m×3m的室內走廊空曠環(huán)境，在正方形的四個角上分別放置4個CC2530信標節(jié)點，信標節(jié)點的高度距離地面約1m。實驗中分別選擇6dB、3dB的全向天線和10dB的定向天線在不同位置處做強度測試，測試結果如圖3所示。該圖表明了在3m的范圍內，6dB的全向天線和10dB的定向天線隨距離的強度衰減關系基本一致，而3dB的天線強度波動大，因此實驗選擇了6dB的全向天線。定位樣本的選擇直接影響著定位精度，過大的采樣間隔會造成代表性樣本的缺失，過小的采樣間隔會造成大量樣本中RSSI的重復。本文在正方形區(qū)域內以0.2m的網格布局采用196個定位樣本，再隨機選取27個待定位點作為測試點。

圖3　三種天線比較圖

圖4　隱層節(jié)點數與總均方誤差(mse)的關系

BP神經網絡參數的選取為：訓練誤差為0.001，訓練步長為0.01，迭代次數為2000。思維進化算法的迭代次數為20，初始種群中個體的數量為200，優(yōu)勝子種群個數為5，臨時子種群個數為5，子種群中個體的數量為20。

本文運用3種神經網絡預測定位結果如表1所示。EC-BP神經網絡預測定位結果的平均定位誤差、最小定位誤差、最大定位誤差均小于BP神經網絡和遺傳算法與BP的結合網絡(GA-BP)。常規(guī)BP網絡的各項誤差均比較大，這是由于它的初始權值和閾值是隨機產生的。在訓練過程中，BP網絡的搜索范圍過大，可能會導致訓練結果陷入局部極小值，故預測精度不高。

表1　3種神經網絡預測定位結果誤差(單位m)

圖5為EC-BP與GA-BP多次運行的平均定位誤差比較圖。從圖中可以看出，EC-BP的定位誤差小于GA-BP。這是因為利用GA優(yōu)化BP神經網絡的權值和閾值雖然在一定程度上減小了搜索范圍，提高了平均定位精度，但是算法本身的變異和交叉操作是任意的，導致優(yōu)化的初始權值和閾值變動大。在12次獨立運行計算過程中，GA-BP算法運行結果波動幅度較大，預測定位結果不穩(wěn)定，平均定位誤差為0.1891。而本文的EC-BP算法通過在優(yōu)勝子種群周圍尋找最優(yōu)子種群，使搜索范圍減小，趨同和異化操作避免了子種群向不良方向發(fā)展，全局優(yōu)化能力強。最終網絡的預測精度不僅比較穩(wěn)定而且定位精度有了提高，平均定位精度為0.0983。

圖5　GA-BP與EC-BP定位誤差比較

對27個隨機選取的待定位節(jié)點位置的定位結果如圖6所示，其中除了7個矩形框表示的待定位節(jié)點的定位誤差較大以外，其余點定位精度均比較小。

圖6　EC-BP算法定位結果圖

表2所示為三種算法的收斂時間，從表中可以看出，在采用相同的訓練次數(最大訓練2000次)和訓練誤差(0.001)時，通常的BP神經網絡在訓練次數達到2000時仍未達到目標的訓練誤差而且訓練時間較長。雖然GA-BP算法在訓練次數上比較相當，但在前期的離線優(yōu)化時間上可以看出，EC-BP所用時間較短，因此EC-BP更具有實際應用的意義。

表2　三種算法的收斂時間比較

5結語

本文提出在室內無線定位中采用改進的BP神經網絡，它利用思維優(yōu)化算法來優(yōu)化網絡的初始權值和閾值。實驗結果表明，該改進網絡在預測待定位節(jié)點上，定位精度能明顯地提高，定位結果比較穩(wěn)定以及收斂速度更快。

參考文獻

[1] 花超,吉小軍,蔡萍,等.基于RSSI差分修正的加權質心定位算法[J].傳感器與微系統(tǒng),2012,31(5):139-141,144.

[2] 韓東升,楊維,劉洋,等.煤礦井下基于RSSI的加權質心定位算法[J].煤炭學報,2013,38(3):522-528.

[3] 田曉燕,閆斌,唐蕓蕓.基于RSSI的三角形區(qū)域最小化的質心定位算法[J].計算機應用與軟件2014,31(7):112-115,140.

[4]ThongpulK,JindapetchN,TeerapakajorndetW.ANeuralNetworkbasedOptimizationforWirelessSensorNodePositionEstimationinIndustrialEnvironments[C]//InternationalConferenceonElectricalEngineering/ElectronicsComputerTelecommunicationsandInformationTechnology(ECTI-CON),ChaingMai,Thailand:IEEE,2010:249-253.

[5]MartinezSala,AlejandroSantos,GuzmanQuiros,etal.UsingneuralnetworksandActiveRFIDforindoorlocationservices[C]//EuropeanWorkshoponSmartObjects:Systems,TechnologiesandApplications(RFIDSysTech),Ciudad,Spain:VDE,2010:1-9.

[6]YuShuanglin,RungChingchen,YuChenglin.AnIndoorLocationIdentificationSystemBasedonNeuralNetworkandGeneticAlgorithm[C]//InternationalConferenceonAwarenessScienceandTechnology(iCAST),Dalian,Chinese:IEEE,2011:193-198.

[7]MohammadShaifurRahman,YoungilPark,KiDooKim.RSS-BasedIndoorLocalizationAlgorithmforWirelessSensorNetworkUsingGeneralizedRegressionNeuralNetwork[J].ArabianJournalforScienceandEngineering,2012,37(4):1043-1053.

[8]NazishIrfan,MiodragBolic,MustaphaCEYagoub,etal.Neural-basedapproachforlocalizationofsensorsinindoorenvironment[J].SolderingandSurfaceMountTechnology,2010,44(1-2):149-158.

[9]ZhangHuiqing,ShiXiaowei,CaoLuguang,etal.Anewindoorlocationtechnologyusingbackpropagationneuralnetworkandimprovedcentroidalgorithm[C]//ChineseControlConference(CCC),hefei,Chinese:IEEE,2012:5460-5463.

[10] 邱玉霞.進化計算與粗糙集研究及應用[M].北京:冶金工業(yè)出版社,2009.

[11] 韓力群.人工神經網絡理論、設計及應用[M].北京:化學出版社,2007.

INDOOR WIRELESS POSITIONING BASED ON IMPROVED BP NEURAL NETWORK

Liu XiaochenZhang Jing*

(School of Information,Mechenical and Electrical Engineering,Shanghai Normal University,Shanghai 200234,China)

AbstractFor indoor wireless positioning, we used an improved BP neural network to overcome the low accuracy and signal instability when a weighted centroid positioning method being adopted. We established the BP network structure by using the received signal strength indication (RSSI) as input and the two-dimensional position as output. The mind evolutionary computation was used to optimise its initial weights and thresholds. The network was trained by 196 sample data within a square area of 3 m side length. Experimental results showed that it was able to achieve the positioning accuracy by 0.1 m at 27 predictive test points. Compared with a standard BP neural network as well as with a combination of BP network and genetic algorithm, this positioning method had the performance of short training and convergence time, the positioning result was stable as well.

KeywordsIndoor positioningBP neural networkMind evolutionary computation (MEC)Received signal strength indicator

收稿日期：2014-10-18。國家自然科學基金項目(61101209)；上海市自然科學基金項目(11ZR1426600)；上海師范大學一般科研項目(DYL201406)；上海師范大學重點學科基金項目(DZL126)。劉曉晨，碩士生，主研領域：無線室內定位，神經網絡。張靜，副教授。

中圖分類號TP18

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.06.028