基于改进BP神经网络的室内无线定位方法

刘晓晨　张　静

(上海师范大学信息与机电工程学院　上海 200234)



基于改进BP神经网络的室内无线定位方法

刘晓晨张静*

(上海师范大学信息与机电工程学院上海 200234)

摘要针对在室内无线定位中采用加权质心定位法时精度较低且难以克服信号不稳定的问题，提出改进的BP神经网络方法。以接收信号强度(RSSI)为输入、二维平面坐标为输出建立网络结构，网络的初始权值和阈值用思维进化算法优化，并用边长3 m的正方形区域内的196个样本数据训练。实验结果表明，在27个预测点上可达到定位精度0.1 m。相比于BP网络以及BP网络和遗传算法的结合算法，该定位方法训练收敛时间短，定位结果稳定。

关键词室内定位BP神经网络思维进化算法接收信号强度指示

0引言

在一般室内办公场景下进行的无线定位方法主要依赖于无线传感器节点所接收的信号强度(RSSI)，往往通过路径损耗模型获得定位信息。由于室内障碍物的遮蔽，多径效应和室内环境的多样性，会导致信号强度波动较大，而且距离估算不准，这极大地影响了定位精度。针对室内环境的无线定位方法通常是加权质心定位法，但其定位精确还不高。在这种算法中，路径损耗系数对定位精度的影响至关重要。文献[1]提出了差分修正算法来提高定位精度；文献[2]提出动态获取路径损耗指数，这样能够反应巷道不同区域对信号衰落的影响，然后利用加权质心的方式计算待定位节点的位置。在实验室走廊环境下，定位误差为1m。

文献[3]对信标节点所构成的几何图形进行更细致的区域划分，用修正的质心算法提高了定位精度，在边长为6m的等腰直角三角形中的定位精度为1m。

采用计算智能方法对RSSI处理具有一定的容错能力并改善定位精度。文献[4]利用位置传感器节点在工厂环境下室内定位，采用一种线性伙伴式神经网络通过Hebb学习规则训练，减小了多径效应对定位精度的影响，在20m×10m的环境中定位误差为0.5m。文献[5]在RFID设备的定位系统中采用BP神经网络定位，它以接收器的RSSI为输入和位置坐标为输出，用最小均方误差估计来克服算法收敛速度慢和易陷入局部极小点的不足。同时增加RF发射器的数量来提高定位精度，它在576m2的区域中达到定位精度1.75m。文献[6]提出分别建立5个BP神经网络，各自将4个接收器节点的RSSI值进行组合作为5个BP网络的输入，利用遗传算法优化BP神经网络来改善定位精度。文献[7]提出广义回归神经网络(GRNN)和加权质心联合定位的方法，定位精度为1m左右。文献[8]利用BP网络建立移动节点位置与接收信号强度指示(RSSI)和链路质量指示(LQI)之间的关系，在11m×6m的环境中平均定位精度为1.33m。

本文结合一套四个信标节点和一个待定位接收节点的无线定位装置，采用改进的BP神经网络来学习RSSI和两维位置信息间的非线性映射，同时应用思维进化算法优化网络的初始权值和阈值。该方法可以有效地提高定位精度，加快BP神经网络的收敛速度。

1无线定位模型

通常的室内无线定位场景是利用RSSI得到距离值，然后用该距离值为半径以信标节点为圆心画圆，多个圆的重叠部分为待定位节点可能所处的位置。定位结果可通过加权质心定位法采用式(1)得到：

(1)

其中，xi和yi为相交圆的交点位置坐标，ωi加权系数，该系数通常随信标节点与待定位节点间的距离增加而减小，m是信标节点的个数。

由于无线电磁波在室内具有反射、折射等多种传播路径，导致距离与损耗的关系比较复杂，会随室内环境的布局不同而有较大差异。一般情况下，用RSSI来推算距离时，由经验路径损耗模型得出，即：

(2)

其中，d为所推算的待定位节点距离，n为路径损耗系数，A为1m处的参考接收信号强度，RSSI是待定位节点处的接收信号强度。

式(2)表明，n的大小极大地影响到距离推算，将直接影响定位精度。在不同的室内环境下应凭经验选择不同的值。但不论怎样选择，都不能使在不同位置处的信标节点都达到较佳的情况，即RSSI信息存在较大的波动性。同时，距离是经由RSSI推算出来的，在推算过程中会丢失RSSI原始数据所包含的一些信息。因此，本文在设计BP神经网络结构时，考虑到这些因素后，直接采用RSSI作为输入，待定位节点的二维位置信息作为输出。利用BP神经网络的函数逼近能力来建立如下函数关系：

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

(3)

其中，RSSIi，i∈(1,m)为待定位节点处的来自各信标节点的RSSI。

2思维进化优化BP的定位原理

RSSI和位置坐标间的非线性映射可通过人工神经来拟合。BP神经网络[9]能以任意精度逼近一个非线性映射，但式(3)的无线定位模型比较复杂，而且RSSI样本的波动幅度较大，很难得到较小的训练误差，还存在易陷入局部极小点导致定位精度不高的问题。而思维进化[10](EC)算法具有较强的全局搜索和优化能力，该算法主要包括种群初始化、趋同、异化等操作，具有鲁棒性强、并行分布处理的特点。因此本文将EC算法应用于BP神经网络中来改善BP易陷入局部极小点的问题，以更好的拟合性能来建立式(3)的函数关系。

改进的BP神经网络结构如图1所示。它为一个三层前向网络，输入层节点的个数为待定节点可接收的来自信标节点的RSSI个数，输出层节点个数为2，分别为二维坐标x和y，隐层节点个数可依据经验公式适当选择。同时该网络结构中利用EC算法来优化BP神经网络的所有初始权值和阈值。定位处理过程包括四个阶段：样本数据采集、EC算法的离线优化、BP神经网络的训练和预测定位。在数据采集阶段，根据定位区域的大小以及所要求的定位精度，并设置信标节点个数以保证定位精度。设置适当个数的网格点作为样本采集位置，将待定位节点处于网格点时的RSSI值为样本输入，网格节点处的精确位置作为期望输出。由于RSSI值有一定波动，可适当取平均值处理。在离线优化阶段，将网格点的样本输入和期望输出分别作为思维进化算法的输入和输出。BP神经网络的初始权值和阈值通过初始种群产生后，运用趋同、异化等操作计算出最优值。然后将此最优值作为BP网络的初始权值和阈值。在训练阶段，按常规的反向传播学习算法训练网络，使BP网络的训练误差达到要求。在预测定位阶段，将待定位节点放置于区域内的随机位置，预测实际定位结果。

图1　改进的BP神经网络结构

3思维进化算法优化BP网络过程

运用EC算法对BP神经网络的初始权值和阈值进行全局寻优，其流程如图2所示。

图2　思维进化算法流程图

它主要有以下几个步骤：

(1) 初始种群的产生

在确定了BP神经网络的结构后产生初始种群。设网络的输入层、隐层、输出层的节点个数分别为q1、q2和q3，则需优化的初始权值和阈值的个数为j=(q1+1)(q2+(q2+1)×q3。随机产生50～200个个体作为初始种群，每一个个体都包含所有的初始权值和阈值。再将这个初始种群平均分为若干个子种群，设每个子种群里的个体数目为k，则可将一个子种群表示为信息矩阵：

(4)

此信息矩阵P的每一行代表一个个体，分别由输入层与隐层节点之间的权值和隐层与输出层间节点的权值以及隐层节点的阈值和输出层节点的阈值组成。

(2) 计算个体的得分值

对子种群中的个体l，l∈(1,k)所代表的权值和阈值计算网络的实际输出，用实际输出y(l)与期望输出d(l)的差值函数作为得分函数，例如：

(5)

个体的V值越大，则个体所代表的权值与阈值越好。

(3) 权值和阈值的趋同过程

将初始种群中的所有个体按照得分值从大到小排序，依次选择得分值高的个体作为优胜个体和临时个体，其个数分别记为f和r。 再分别以每一个优胜和临时个体为中心，以正态分布的方式产生若干个新个体，形成f个优胜子种群和r个临时子种群，每个子群体依然包含k个个体以保证种群规模不变。该正态分布N(μ,σ2)中的中心μ为优胜个体所在的位置，而σ2的选择需要通过试验方式确定。当σ2选择得太小则搜索范围过小，可能搜索不到最优解，当σ2选择得过大则会降低算法的效率。

优胜子种群和临时子种群中的个体分别位于优胜个体和临时个体的周围。将这些种群中的个体再带入神经网络中计算实际输出并求得分值，然后再选择优胜个体和临时个体。若新选择的优胜个体的得分值比原来的优胜个体得分值低，则保留原来的优胜个体。经过若干次的搜索未找到比优胜个体得分值大的个体，则表明此种群已经成熟。成熟的种群内的最优胜个体是在趋同过程中产生的最优权值和阈值。对临时子种群的操作过程一样。这个趋同操作是子群体内的寻优过程。

(4) 异化过程

待优胜子群体和临时子群体成熟以后，将两个群体中的所有子种群进行全局竞争，即比较其得分值。被替换的子群体或临时子群体数量不足时，按照上述步骤重新形成新的临时子群体，并参与全局竞争。

4实验过程及结果分析

本文的实验环境为正方形3m×3m的室内走廊空旷环境，在正方形的四个角上分别放置4个CC2530信标节点，信标节点的高度距离地面约1m。实验中分别选择6dB、3dB的全向天线和10dB的定向天线在不同位置处做强度测试，测试结果如图3所示。该图表明了在3m的范围内，6dB的全向天线和10dB的定向天线随距离的强度衰减关系基本一致，而3dB的天线强度波动大，因此实验选择了6dB的全向天线。定位样本的选择直接影响着定位精度，过大的采样间隔会造成代表性样本的缺失，过小的采样间隔会造成大量样本中RSSI的重复。本文在正方形区域内以0.2m的网格布局采用196个定位样本，再随机选取27个待定位点作为测试点。

图3　三种天线比较图

图4　隐层节点数与总均方误差(mse)的关系

BP神经网络参数的选取为：训练误差为0.001，训练步长为0.01，迭代次数为2000。思维进化算法的迭代次数为20，初始种群中个体的数量为200，优胜子种群个数为5，临时子种群个数为5，子种群中个体的数量为20。

本文运用3种神经网络预测定位结果如表1所示。EC-BP神经网络预测定位结果的平均定位误差、最小定位误差、最大定位误差均小于BP神经网络和遗传算法与BP的结合网络(GA-BP)。常规BP网络的各项误差均比较大，这是由于它的初始权值和阈值是随机产生的。在训练过程中，BP网络的搜索范围过大，可能会导致训练结果陷入局部极小值，故预测精度不高。

表1　3种神经网络预测定位结果误差(单位m)

图5为EC-BP与GA-BP多次运行的平均定位误差比较图。从图中可以看出，EC-BP的定位误差小于GA-BP。这是因为利用GA优化BP神经网络的权值和阈值虽然在一定程度上减小了搜索范围，提高了平均定位精度，但是算法本身的变异和交叉操作是任意的，导致优化的初始权值和阈值变动大。在12次独立运行计算过程中，GA-BP算法运行结果波动幅度较大，预测定位结果不稳定，平均定位误差为0.1891。而本文的EC-BP算法通过在优胜子种群周围寻找最优子种群，使搜索范围减小，趋同和异化操作避免了子种群向不良方向发展，全局优化能力强。最终网络的预测精度不仅比较稳定而且定位精度有了提高，平均定位精度为0.0983。

图5　GA-BP与EC-BP定位误差比较

对27个随机选取的待定位节点位置的定位结果如图6所示，其中除了7个矩形框表示的待定位节点的定位误差较大以外，其余点定位精度均比较小。

图6　EC-BP算法定位结果图

表2所示为三种算法的收敛时间，从表中可以看出，在采用相同的训练次数(最大训练2000次)和训练误差(0.001)时，通常的BP神经网络在训练次数达到2000时仍未达到目标的训练误差而且训练时间较长。虽然GA-BP算法在训练次数上比较相当，但在前期的离线优化时间上可以看出，EC-BP所用时间较短，因此EC-BP更具有实际应用的意义。

表2　三种算法的收敛时间比较

5结语

本文提出在室内无线定位中采用改进的BP神经网络，它利用思维优化算法来优化网络的初始权值和阈值。实验结果表明，该改进网络在预测待定位节点上，定位精度能明显地提高，定位结果比较稳定以及收敛速度更快。

参考文献

[1] 花超,吉小军,蔡萍,等.基于RSSI差分修正的加权质心定位算法[J].传感器与微系统,2012,31(5):139-141,144.

[2] 韩东升,杨维,刘洋,等.煤矿井下基于RSSI的加权质心定位算法[J].煤炭学报,2013,38(3):522-528.

[3] 田晓燕,闫斌,唐芸芸.基于RSSI的三角形区域最小化的质心定位算法[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].北京:冶金工业出版社,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