分布式AP选择策略在室内定位中的应用*

葛柳飞，赵秀兰，李克清，戴 欢，张 骞

(1.中国矿业大学计算机科学与技术学院，江苏徐州221116;2.常熟理工学院计算机科学与工程学院，江苏常熟215500)

0 引言

室内定位是一种用于获取室内目标物体位置信息的技术，在民用和军用领域具有广泛的应用前景。常见的定位算法主要基于接收信号强度指示(received signal strength indication，RSSI)、到达时间(time of arrival，TOA)、到达角度(angle of arrival，AOA)等技术［1］。其中，基于 RSSI的定位算法具有低功耗、低成本且易实现的优点［2］，被广泛应用于无线室内定位。

基于RSSI的定位算法通常分为:基于信号传播模型的定位算法［3］和基于指纹模型的定位算法［4］。在具有大量AP节点部署的无线网络中，为了获得目标位置，上述方法所处理的数据都是高维向量(AP节点的个数)。同时，由于物体遮挡和节点故障等因素，导致将所有AP节点作为特征输入的定位效果并不一定最优，冗余的AP节点增加了位置估计的难度，易造成过度拟合，并增加了时间和空间的复杂度。针对该问题，采用合适的选择机制筛选AP节点，获得较优的AP节点作为特征输入，既达到降维的作用，又提高了定位精度。文献［5］提出使用数据挖掘技术选择较优的AP节点，通过筛选的AP节点建立位置指纹库。

本文提出一种分布式AP选择(distributed selection on AP，DSAP)算法，能够有效去除较大噪声或者位置分辨能力弱的AP节点。实验表明:在12 m×12 m的区域范围内，该算法平均定位误差为0.4151 m，较反向传播(back propagation，BP)算法、RADAR［6］算法而言，定位误差低，且降低了定位算法的复杂度。

1 定位模型

不同AP节点的信号强度作为一种可识别的模式(指纹)，被用于区分不同的位置点。假设在位置点A获取D个AP节点的信号强度，构建D维信号向量RSSD

式中 rssi∈［-100，0］为位置点A处接收到第i个AP节点的信号强度。

位置点A与D维信号向量之间存在映射关系，数学表示为

训练数据集中包含N条记录，每条记录可表示为向量r，向量中包含可用AP节点的信号强度和采样点的位置

式中 D为AP节点个数，Li为对应RSS向量的位置标签。

在线定位就是利用离线阶段建立的信号—位置映射模型预测移动目标的位置。

2 深度置信网络

2.1 受限玻耳兹曼机

受限玻耳兹曼机(restricted Boltzmann machine，RBM)由可见层和隐含层两部分构成，神经元之间的连接被限制在不同层，相同层之间不存在神经元的连接，如图1(a)所示。RBM是一种基于能量的模型，其能量函数定义如下

式中 I和J分别为可见层和隐含层的神经元个数，xi和hj分别为可见层第i个神经元与隐含层第j个神经元的值。θ =(wij，ai，bj)为 RBM 的参数，wij为可见层节点 xi与隐含层节点hj之间的连接权值，ai和bj分别为xi和hj的偏置值。

该联合概率分布为

式中 Z(θ)为归一化项。

2.2 深度置信网络模型

为解决BP网络易陷入局部最优的问题，Hinton G等人［7］于2006年提出了深度置信网络(deep belief networks，DBN)，其在图像处理［8］、语音识别［9］等领域发挥了重要作用。

RBM是DBN的基本构建块，如图1(b)所示。当高维数据输入RBM1可见层，隐含层将通过连接权值提取输入数据的特征;同时，RBM1隐含层的输出将作为RBM2可见层的输入，RBM2隐含层将进一步提取数据的深层次特征［10］。若干个RBM模块构成了DBN模型，其在预训练的过程中通过层与层之间的能量函数初始化网络权值，最后通过BP算法来微调网络间的权值。

图1 RBM和DBN模型Fig 1 RBM and DBN models

3 分布式AP选择策略

在复杂的室内环境中，AP节点非全可用的问题增加了位置估计的不确定性。本文提出了一种分布式AP选择策略，首先将定位区域S划分为m个子区域，子区域定义如式(6)所示

式中 c为第c个子区域，k为该子区域中位置点的个数，S为定位区域，m为区域个数。

根据子区域与各个AP节点的相关性，将输入向量RSSD分割为 m 个非空子集 (RSS1，RSS2，RSS3，…，RSSm)，且非空子集RSSc与子区域Rc相对应，最后将非空子集RSSc作为特征输入来训练子区域Rc的定位预测模型。

假设在该子区域中，扫描区域中k个位置点上第j个AP节点的信号，那么，该AP节点在此区域的相关性系数定义如下

式中 Pj为第j个AP节点与该区域的相关性，xi为第i个位置点的X轴坐标，x为该区域中k个位置点的X轴坐标的均值，yi为第i个位置点的Y轴坐标，y为该区域中k个位置点的Y轴坐标的均值，rssji为第i个位置点接收的第j个AP节点信号强度的均值，rssj为该区域中k个位置点接收的第j个AP节点信号强度的均值，k为该区域位置点个数，D为AP节点个数。

在每个子区域中，D个AP节点的相关性系数向量表示为

若Pj＞Pτ表示第j个AP节点与该子区域相关;反之，则不相关。选取相关的AP节点作为特征输入，进行定位模型训练。

基于分布式AP选择策略的定位算法的具体步骤:

1)将定位区域划分为m个子区域，根据式(7)计算每个AP节点与各个子区域的相关性，建立相关性系数矩阵;

2)选择相关性系数大于Pτ的AP节点，并将AP节点划分为m组;

3)在步骤(2)中AP节点分组的基础上，在每个子区域中，利用分组后的训练数据集训练DBN模型，构建定位预测模型;

4)在线预测阶段，获取移动设备接收的RSS指纹信息并作为输入向量，利用分区域模块选择对应子区域;

5)利用子区域中训练的定位预测模型估计目标的位置。

4 实验分析

定位数据的采集实验场景设于综合实验室内，数据采集设备为三星手机(I9228)，系统为Android 4.1.2。实验室长约12.8 m，宽约12.5 m，高约3 m，室内布置有工位、电脑等办公用品，AP节点高度保持1.6 m。在该区域内，能够收集到25个AP节点的信号，部分AP信号的传播路径为非视距的，存在柱子的阻隔。将区域划分为144个小区域，每个小区域大小为1 m×1 m，以小区域中心为信号强度采集点。为保证样本数据的准确性，每个信号采集点获取600次AP信号集，每秒一次。

为不同子区域选择较优的AP节点，首先分析RSSI的分布特征，选择最佳的依赖特征计算相关性。在测试点上获取节点AP9的RSSI的五个分布特征如图2所示。

由图可见，均值、中值、最大值以及最小值的分布特征较相似，但是方差的分布特征变化无明显规律。因此，方差不能作为依赖特征。在缺乏足够信号样本的情况下，利用中值、最大值以及最小值来实时统计的定位效果明显次于均值的效果。因此，本文将信号均值作为依赖特征，计算子区域与AP节点的相关性。

本文在相同训练数据集的情况下，将所提DSAP算法与集中式SAP算法进行对比，实验结果如图3所示。由图可见，本文DSAP算法在不同的误差距离时，均具有较优的定位准确率，且明显优于集中式的SAP算法。

图2 AP9节点的五个信号分布特征图Fig 2 Signal distribution feature diagram of AP9 node with five characteristics

图3 DSAP算法与SAP算法在不同误差距离下的定位准确率Fig 3 Location accuracy of DSAP and SAP algorithms in different error distance

本文将预测位置与实际位置之间的欧氏距离作为定位预测误差，并将区域内位置点的平均预测误差作为算法评判标准。本文将DSAP算法、RADAR算法［6］以及BP算法在不同区域个数下进行对比，实验结果如图4所示。

图4 三种算法在不同区域个数下的平均预测误差Fig 4 Average prediction error of three algorithms in different number of regions

由图可见，随着区域个数增加，三种算法的平均预测误差呈递减趋势变化;本文DSAP算法在不同区域数的情况下，具有较低的平均预测误差且明显优于BP算法和RADAR算法。

在英特尔 i5处理器，2GB内存的 PC环境下，利用Matlab软件执行DSAP算法、RADAR算法以及BP算法，算法执行时间主要包括分区域模块执行时间和位置估计时间，其取值为测试数据运行100次所需时间的均值。三种算法在不同区域个数下的执行时间如图5所示。

图5 三种算法在不同分区域个数下的运行时间Fig 5 Running time of three algorithms in different number of sub regions

由图可见，当区域数为16时，由于分区域模块执行时间较长，导致三种算法的运行时间明显增加;当区域数分别为6和8时，DSAP算法执行时间短且明显低于其它两种算法。由图4和图5可知，当区域数为8时，本文算法定位误差小且运行时间短，较BP算法、RADAR算法而言，平均定位误差分别降低了35.95%，46.78%，运行时间分别减少了22.8%，32.9%。

5 结论

本文提出了一种分布式AP选择策略，并应用于室内定位。针对定位模型的可伸缩性和定位区域内AP的非全可用问题，该方法将室内区域划分为若干个子区域，并计算子区域与AP节点之间的相关性，选取与该区域相关的AP节点作为该子区域的训练节点，最后通过DBN模型进行定位模型训练。该方法能够有效去除较大噪声和位置分辨能力弱的AP节点，降低了AP节点不可用的概率。实验表明:该算法较BP算法、RADAR算法而言，具有运行时间短且平均定位误差小的优点。但在复杂的室内环境中，采集有标记的训练数据将面临较大困难，今后重点将尝试利用半监督学习方法来训练未标记的数据，以提高其与预测能力。

［1］Dai Huan，Zhu Zhaomin，Gu Xiaofeng.Multi-target indoor localization and tracking on video monitoring system in a wireless sensor networks［J］.Journal of Network and Computer Application，2013，36(1):228-234.

［2］孙中廷，华 钢，黄金城.基于进化理论的无线网络室内定位算法［J］.传感器与微系统，2014，33(9):132-134.

［3］文春武，宋 杰，姚家振.基于RSSI校正的无线传感器网络定位算法［J］.传感器与微系统，2014，33(12):134-136.

［4］刘军发，谷 洋，陈益强，等.具有时效机制的增量式无线定位方法［J］.计算机学报，2013，36(7):1448-1455.

［5］Lin Tsungnan，Fang Shihhau，Tseng Weihan，et al.A group-discrimination-based access point selection for WLAN fingerprinting localization［J］.IEEE Transactions on Vehicular Technology，2014，63(8):3967-3975.

［6］Bahl P，Padmanabhan V N.RADAR:An in-building RF-based user location and tracking system［C］∥Proceeding of the IEEE INFOCOM，New York:IEEE Computer and Communications Society，2000:775-784.

［7］Hinton G，Salakhutdinov R.Reducing the dimensionality of data with neural networks［J］.Science，2006，313(5786):504-507.

［8］Chen Yushi，Lin Zhouhan，Zhao Xing，et al.Deep learning-based classification of hyperspectral data［J］.IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing，2014，7(6):2094-2107.

［9］Mohamed A R，Dahl G E，Hinton G.Acoustic modeling using deep belief networks［J］.IEEE Transactions on Audio，Speech and Language Processing，2012，20(1):14-22.

［10］孙志军，薛 磊，许阳明，等.深度学习研究综述［J］.计算机应用研究，2012，29(8):2806-2810.