一种改进的基于贝叶斯的位置指纹算法

徐潇潇， 谢林柏 ， 彭 力

(江南大学 物联网工程学院，江苏 无锡214122)

随着移动互联网的高速发展以及智能移动终端的普及，基于LBS 的服务在越来越多的领域得到了应用。目前，GPS 在室外空旷区域进行定位时可以获得很好的效果;然而，在室内环境下，由于建筑结构的复杂性以及人员走动等因素的存在，GPS 往往不能取得较好的定位效果，甚至存在着无法定位的情况［1］。这时，就需要一种能在室内进行定位的方法，以满足人们在室内环境下对位置信息的需求。

基于WiFi 信号强度的定位算法由于其成本低、可扩展性强等因素而成为了近些年的研究热点。与TOA，TDOA 以及AOA 等方法相比，该方法不需要添加额外的设备［2］，利用现有的WiFi 以及智能移动终端，再配合一个APP，即可实现定位，成本较低。基于信号强度的定位方法分为信号传播模型定位以及位置指纹定位。其中，位置指纹算法又分为确定性方法与概率性方法。确定性方法通过计算信号特征之间的欧氏距离选取最接近的参考点，该方法较为简单，但是精确度不够高;而概率性方法则是通过计算出参考点的后验概率来进行定位，该方法具有较高的精度，但是计算比较复杂［3］。

文中提出了一种改进的基于贝叶斯的位置指纹算法。通过选取固定的若干个参考AP，防止突然加入的AP 对定位结果产生的影响。在对采样数据进行处理时，采用高斯概率分布描述取代离散概率描述。在线阶段，通过实测信号特征中强度最大的AP 判断并去除一部分不可能的参考节点，在不影响定位精度的情况下减小计算量，并通过加权处理进一步较小误差。实验结果表明，改进的算法能减小定位算法的计算量，同时有效地提高了定位精度。

1 位置指纹算法的基本原理

位置指纹定位算法通常由两个阶段构成:离线阶段和在线阶段［4］。离线阶段，又称训练阶段，其主要工作是在定位区域中设定若干个参考点，并在每个参考点采集相应的指纹信息。通常每个参考点的指纹信息由该点采集到的各个AP 的信号强度信息和该点的物理坐标构成，参考点一般设置为网格状分布。最终，将每个参考点的指纹信息录入数据库，该数据库称为Radio Map。通常选取的参考点越多，即网格密度越大，采样次数越多，对定位精度的提高越是有利［5］，然而，考虑到工作量的问题，需在可接受的工作量范围内尽可能地提高定位的精度。在线阶段，又称定位阶段，其主要工作是利用智能移动终端在待定位点采集AP 的信号特征信息，再通过匹配算法将其与Radio Map 中的指纹信息进行对比，从而计算出待定位点的物理位置。

根据Radio Map 中指纹信息记录形式的不同，通常将定位方法分为确定性方法和概率性方法［6］。其中，确定性方法将AP 在一段时间内的信号强度平均值记录到指纹信息中，然后由最近邻法(NN)、k 最近邻法(KNN)或者加权的k 最近邻法(WKNN)通过计算曼哈顿距离或者欧氏距离推算出待定位点的物理坐标。距离越小，表示两个指纹的相似度越高。概率性方法则是将AP 的离散采样样本或者信号强度均值以及方差等信息保存在指纹信息中。利用贝叶斯定理，计算在每个参考点的后验概率，选取后验概率最小的一个或者若干个参考节点，从而计算出待定位点的物理坐标。概率性方法相比确定性方法的优势在于该方法可以有效地去除采样信号中较大误差的影响，去噪性优势明显。

Horus 系统首次实现了基于概率的定位解决方案［7］。利用贝叶斯法，通过计算待定位点的后验概率估计该点的物理坐标［8］。假设定位区域所有参考点的位置集合为

式中:n 为定位区域内参考点的个数;li= {xi，yi}，为第i 个参考点对应的物理坐标。与L 一一对应的位置指纹集合为

其中

式中:rssiij为第i 个参考点接收到的来自第j 个AP的信号强度值;m 为参考AP 的个数。

在线阶段，令待定位点测得的指纹信息为A，A中包含m 个AP 的信号强度信息，则指纹A = {a1，a2，…，am}在各个参考点的后验概率为P(li| A)。根据贝叶斯定理，可将后验概率的公式转化为

其中:P(A| li)为在已知位置li处的RSSI 指纹为A的条件概率;P(li)为在定位区域内li位置上的先验概率。由于待定位点在定位区域内任意一点出现的可能性都一样，即P(li)在任意位置出现的概率均相同，所以将其看成一个常量。P(A)对于所有位置而言为常数。所以式(1)可以转化为

由于各个AP 之间相互独立［9］，因此，P(A | li)可采用联合概率分布函数描述为如下形式

即

所以，将问题转化为求P(A| li)值最大时对应的参考点li。

2 改进的位置指纹算法

2.1 特征AP 的选取

由式(4)可知，若在定位区域内加入了某一AP，则在定位阶段，A 中会增加一个该AP 的信号强度信息。使用式(4)进行后验概率计算时，则会出现P(A| li)= 0 的情况，从而导致无法定位。若某一参考AP 在定位阶段发生断电等情况，从而导致无法获取该AP 的信号强度值，则可以继续完成定位，而不会导致无法定位的情况发生。为了避免不相关AP对定位结果的影响，参考AP 应选取若干个固定的AP。

改进的具体实现如下:共选取m 个固定参考AP，即式(1)中的m 为固定值。在参考点进行采样时，分别获取这m 个参考AP 的信号强度特征信息。若在某次采样中并未搜索到某个参考AP，则给其赋值搜索到的AP 中信号强度值最小的值减去3 dBm，即rssimin－3 dBm，确保每个参考位置的指纹信息均包含了所有参考AP 的信息。在线阶段，考虑到信号较强的AP 往往较为稳定，能较好地反映该位置的信号分布情况，故选取指纹信息中信号强度较大的t(t ＜m)个AP 计算后验概率，则公式(4)可以写为

上述改进可有效去除新加入的AP 对定位结果的影响，用于计算后验概率的AP 信息则能较好地反映该位置的无线信号分布特征。

2.2 离线阶段信号特征的描述

若采用离散概率法，则需要较大的存储空间［10］。由于室内环境较为复杂，而且人员走动频繁，所以接收信号强度存在一定的波动;同一位置同一设备在不同时刻测得的数据也往往不一样，所以导致在线阶段测得的信号值并未在离线采样样本中出现，最终出现概率为0 的情况。这是由式(5)右边存在单个概率为0 导致的，因而无法获得定位结果。

针对上述情况，文中在离线阶段记录一定量的采样样本，采用基于分布的概率法代替离散概率法，这样不仅可以节省存储空间，还能避免后验概率为0 的情况的出现。同一位置的WiFi 信号强度值虽然存在着不稳定的现象，但是总体在某一个值的附近波动，故同一位置的信号强度分布可用高斯概率分布描述，其概率密度函数为

其中，x 为实际测得的信号强度值;μ 和σ 分别为函数的均值与标准差。由式(6)可得，出现强度值为r的概率为

考虑到采样时初始的10 s 内信号波动较大［11］，之后便相对趋于稳定，所以文中在离线阶段忽略前10 s 的采样值。此外，WiFi 的信号直方图存在一定的偏左性［12］，这是由于WiFi 在某一时刻由于较为严重的传播损耗造成的。若能将这些较大误差去除，则可以更加精确地使用高斯分布描述信号强度分布情况。文中利用3σ 准则去除误差较大的数据。令终端设备在某一位置对某一AP 按照固定频率进行q 次采样，采样获得的信号强度值集合为{r1，r2，r3，…，rq}。由贝塞尔公式可得采样样本的均方根误差为

若| vi|≥3σ，则其对应的采样值ri应被视为较大误差而剔除。对剩余的数据使用高斯分布进行描述，并将指纹信息录入Radio Map。

2.3 在线阶段匹配算法的改进

贝叶斯算法虽然精度较高，但是相比KNN 等确定性方法而言计算较为复杂。针对这一问题，文中通过去除一部分不可能作为定位结果的参考点以减小搜索范围，在不影响定位精度的前提下尽可能地减小计算量。具体实现为:选取在线阶段在待定位点实测所得的信号强度最强的AP，将Radio Map中信号强度最强的两个AP 为该AP 的指纹信息作为备选参考点，缩小计算的范围。

进行后验概率的计算后，选取计算结果最大的k 个参考点，然后进行加权处理。待定位位置的坐标可表示为

其中，wi为权重，该值取决于参考点后验概率的大小。后验概率越大，则该参考点对定位结果的影响最大。wi的计算公式为

其中，Pi为后验概率。

3 算法测试

为了验证改进算法的有效性，分别对改进前后的算法进行定位测试。针对离线阶段的采样样本，改进前的算法直接对若干次采样样本进行计算，求得样本的均值与方差;而改进后的算法首先利用3σ准则去除采样样本中的较大误差，然后再对剩余的数据求均值与方差。在线阶段，改进前的算法直接采用后验概率最大的参考点作为定位结果;而改进后的算法则选取3 个后验概率最大的参考点，并分别考虑了各个参考点对定位结果的不同贡献，最终得出定位结果。

实验中智能移动终端采用三星Galaxy S4，该终端采用的是Android 系统，具备WiFi 功能。为了采集AP 的信号强度，需要在终端上设计一个APP。该APP 的开发涉及到以下的接口和类:ScanResult，WifiInfo 和WifiManager。主要代码如下:

public void onClick(View v){

wifiAdmin.startScan();

mWifiList = wifiAdmin.getWifiList();

LevelComparator comp = new Level-Comparator();

Collections.sort(mWifiList，comp);

if (mWifiList != null){

for (int i = 0;i ＜mWifiList.size();i++){

mScanResult = mWifiList.get(i);

if (

mScanResult.BSSID.equals( "00:87:36:1e:e9:19")||

mScanResult.BSSID.equals( "00:24:b2:1e:a4:88")||

mScanResult.BSSID.equals( "00:1f:33:b4:b1:4c")||

mScanResult.BSSID.equals( "14:e6:e4:69:f2:42")||

mScanResult.BSSID.equals( "00:24:b2:a0:33:16")||

mScanResult.BSSID.equals( "94:0c:6d:35:80:ea")){

sb = sb.append(mScanResult.BSSID + " ")

.append(mScanResult.SSID + " ")

.append(mScanResult.capabilities + " ")

.append(mScanResult.frequency + " ")

.append(mScanResult.level + " ");

arrayList.add(mScanResult.BSSID);

arrayList.add(mScanResult.level);

}

}

}

}

离线阶段，每个参考点进行50 次采样，即式(8)中的q 取50，采样间隔为2 s。在线阶段，考虑到采样时间不宜过长，所以进行5 次采样，时间间隔为2 s，取中间值作为采样结果。定位区域选择江南大学物联网工程学院C 区516 室附近。定位区域大小为12 ×18 m，采用网格布局，每隔2 m 设置一个参考点，共选取70 个参考点。离线阶段，选取6 个固定参考AP，即式(1)中的m =6。匹配阶段，使用实测的6个AP 中信号最强的3 个进行后验概率的计算，即式(5)中的t = 3。式(9)中的k = 3，即选取后验概率最大的3 个参考点进行加权处理。在完成离线阶段与在线阶段的数据采集后，使用Matlab 对改进前后的算法进行仿真。测试中，选取20 个测试点进行定位测试。测试结果见表1 所示。

表1 测试结果Fig.1 Results of the test

通过实际测试可得，采用改进前的算法进行定位，平均误差为2.568 0 m;采用改进后的算法，平均误差为1.407 0 m。定位精度提高了45.21%，计算量平均减少了64.93%。

4 结 语

文中针对传统的基于贝叶斯的位置指纹算法存在着后验概率可能为0 以及计算量较大等问题，对算法进行了改进。离线阶段，首先选取固定的AP作为指纹信息来源，排除了突然加入的AP 可能对定位造成的影响，进而考虑到信号强度分布的偏左性，先利用3σ 准则去除最小的一部分数据，再对剩余数据采用高斯概率分布进行描述，排除了后验概率可能为0 的情况。在线阶段，通过判断指纹信息中信号最强的AP，排除一部分不可能的参考节点，以此减小了计算量，同时对后验概率最大的3 个参考点进行了加权处理。测试阶段，首先利用Android 终端进行WiFi 指纹信息的采集，最后将测得的数据在Matlab 平台上进行仿真测试，验证了改进算法的有效性。

［1］LUO Jiayou，ZHAN Xingqun. Characterization of smart phone received signal strength indication for WLAN indoor positioning accuracy improvement［J］.Journal of Networks，2014，9(3):739-746.

［2］CHENG Jiantong，YANG Ling，LI Yong，et al. Seamless outdoor/indoor navigation with WIFI/GPS aided low cost inertial navigation system［J］.Physical Communication，2014，13:31-43.

［3］Eunchan K，Kim K. Distance estimation with weighted least squares for mobile beacon-based localization in wireless sensor networks［J］.IEEE Signal Processing Letters，2010，17(6):559-562.

［4］赵聘，陈建新.利用现有无线局域网进行室内定位算法研究［J］.信号处理，2014，30(11):1413-1418.

ZHAO Pin，CHEN Jianxin. A study on indoor localization algorithm using existing wireless local area network［J］. Journal of Signal Processing，2014，30(11):1413-1418.(in Chinese)

［5］张明华.基于WLAN 的室内定位技术研究［D］.上海:上海交通大学，2009.

［6］王赛伟.基于位置指纹的WLAN 室内定位方法研究［D］.哈尔滨:哈尔滨工业大学，2009.［7］徐伟.基于Android 手机的室内定位技术研究与实现［D］.武汉:华中师范大学，2014.

［8］罗利.基于Android 的WIFI 室内定位技术研究［D］.成都:西南交通大学，2014.

［9］杨萌，修春娣，邹坤，等.一种基于感知概率的室内定位匹配算法［J］.导航定位学报，2014，2(4):49-53，57.

YANG Meng，XIU Chundi，ZOU Kun，et al.A sensing probability-based matching algorithm for WiFi indoor positioning systems［J］.Journal of Navigation and Positioning，2014，2(4):49-53，57.(in Chinese)

［10］王忠民，陈振，潘春华.一种改进的位置指纹智能手机室内定位算法［J］.西安邮电大学学报，2014，19(1):17-20.

WANG Zhongmin，CHEN Zhen，PAN Chunhua.Improved fingerprinting algorithm for smart phone indoor positioning［J］.Jonrnal of Xi’an University of Posts and Telecommunications，2014，19(1):17-20.(in Chinese)

［11］孙善武，王楠，陈坚.一种改进的基于信号强度的WLAN 定位方法［J］.计算机科学，2014，41(6):99-103.

SUN Shanwu，WANG Nan，CHEN Jian.Improved RSSI-based localization method using bounding-box algorithm in WLAN［J］.Computer Science，2014，41(6):99-103.(in Chinese)

［12］孙永亮.基于位置指纹的WLAN 室内定位技术研究［D］.哈尔滨:哈尔滨工业大学，2014.