基于贝叶斯概率优化的Wi-Fi室内定位算法

杨如民 陈 敏 余成波

(重庆理工大学远程测试与控制研究所 重庆 400054)

0 引 言

随着无线电通信技术、移动互联网技术的发展，移动终端智能化水平的提升，基于位置的服务正逐渐成为各行各业和现实生活的日常需求，对室内移动用户的定位技术也提出更高的要求。由于室内复杂的空间架构，各种办公设施及人员的遮挡阻碍，使得以无线电信号为主的各种定位系统在室内环境下的定位精度变差。当前主流的定位技术，如超宽带无线电(Ultra Wide Band，UWB)、Wi-Fi、蓝牙、射频识别(Radio Frequency Identification，RFID)和红外线等技术中，各自有其局限性。譬如：超宽带无线电的范围覆盖太小，定位成本较高且智能终端暂时不支持该技术；蓝牙定位技术需要预先配置大量信标节点，易受噪声信号影响，传输距离短；射频识别技术作用距离短，抗干扰性差，定位成本较高；红外线定位技术易受环境干扰定位效果差。相比而言，Wi-Fi定位技术因其无须增加额外的发射基站，且覆盖范围广[1]，无疑是最简单快捷、方便而经济的室内定位技术。

一般而言，定位技术采用的基本方法包括三边测量、三角测量和信号强度测量[2]。考虑到室内环境复杂性导致的非视距[3]和多径传输等问题，测量时间和测量角度均会产生较大的偏差，因而室内Wi-Fi定位技术采用了最简单易行、基于信号强度测量(Received Signal Strength Indication，RSSI)的定位算法，通过离线阶段预先建立的Wi-Fi信号强度指纹库，与移动终端在线测量所得到的实时信号强度进行匹配，从而对移动终端进行在线定位。目前，基于Wi-Fi信号指纹匹配的定位技术，仍然存在定位欠佳的问题，主要原因除了前面提到的人体遮挡、非视距、多径传输影响等因素外，还存在着当需要进行匹配的位置空间较大时，离线指纹库存储的指纹信息随之增多，导致运算量增加从而影响定位时间。

文献[4]提出一种基于主成分分析结合加权贝叶斯的Wi-Fi室内定位算法，对离线指纹库进行去相关性、降维处理；匹配定位阶段采用加权贝叶斯算法估算待测点位置，提高定位精度但大大增加运算时间。文献[5]提出一种新的基于方差的指纹距离调整算法，根据当前的位置变化，不同的置信度对应不同的Wi-Fi接入点，该算法提高室内定位精度，但在运行期间，随机存储器和只读存储器占比较大，计算成本较高。文献[6]使用改进的KNN算法筛选出若干个采样点，再使用朴素贝叶斯算法确定待测点最终位置，该算法将室内定位精确度提高16.7%。

上述研究表明，提高指纹匹配定位精度有两个有效技术措施：对离线指纹库进行去相关及降维；利用移动终端在线测量获得后验概率对匹配过程进行贝叶斯加权估计，但是随之产生了运算时间增加过大的问题。

为了综合考虑定位精度与计算执行时间问题，本文提出一种融合贝叶斯估计与加权K近邻算法的贝叶斯概率优化算法，在提高定位精度的同时，也能相应地降低计算时间代价。

1 贝叶斯指纹定位

贝叶斯指纹定位是在离线阶段[7]建立指纹库的基础上，先对指纹库中任意一个指纹信息在接收到RSSI条件下，该指纹位置发生的后验概率进行求解。再通过对指纹库所有指纹信息发生的后验概率与其指纹位置一一对应相乘求和。最后得到结果即为进行贝叶斯概率算法实现的位置估计。具体实现原理如图1所示。

图1 贝叶斯指纹定位原理图

1.1 加权K近邻算法[8]

传统加权K近邻算法(Weighted K-Nearest Neighborhood，WKNN)是K近邻法[9](K-Nearest Neighborhood，KNN)的进一步优化。考虑到所选K个指纹与待测点距离值不尽相同，而采取KNN求取K个指纹对应位置信息平均值作为待测点位置信息有所欠缺。WKNN依据K个指纹与待测点距离值Di作为选取K个指纹的位置信息(xi,yi)的权值系数[10]，通过式(1)求出权值系数wi，通过式(2)求解出待测点位置。

(1)

(2)

针对Wi-Fi指纹匹配使用传统WKNN算法定位精度低的情况，本文对传统WKNN算法中位置信息权值系数进行改进，通过式(3)和式(4)求出权值系数wi1和wi2，通过式(5)求解出待测点位置信息。

(3)

(4)

(5)

式中：Di为第i个指纹点与待测点距离；Di+1为第i+1个指纹点与待测点距离。

1.2 贝叶斯概率算法[11]

指纹库中第i个参考点(Reference Point，RP)接收到接入点(Access Point，AP)RSSI信号为Si=[Si1,Si2,…,Sij,…,Sin],j=1,2，…,n，其中：RP个数为m，AP个数为n。构建指纹库Si=[Si1,Si2,…,Sij,…,Sin],i=1,2，…,m，其中第i个参考点的位置信息Li=(xi,yi)，通过式(6)计算出实测信号在第i个参考点出现的后验概率[12]P(Li/S)。

(6)

式中：P(S/Li)为第i个参考点在该位置处接收到实测信号S的条件概率；P(Li)为第i个参考点位置信息发生的概率事件，一般认为出现在任意一个参考点的位置信息概率相等，即服从均匀分布P(Li)=1/m。假设n个接入点在第i个参考点发出的实测信号S均相互独立[13]且互不干扰，即：

P(S/Li)=P(s1/Li)P(s2/Li)P(sn/Li)

(7)

从概率统计的相关理论可以得出，任意第i个待测点接收到第j个接入点的实测信号sj均满足高斯正态分布[14]，通过在实验环境中选择任意一个待测点与接入点进行100次测试验证，如图2所示。

(a) 待测点与接入点距离为1 m时

(8)

(9)

贝叶斯概率算法流程如算法1所示。

算法1贝叶斯概率算法

输入：指纹库中m个RP接收到的AP实测信号S和位置信息(xi,yi)，移动终端接收到的AP实测信号Sk。

Fori=1：m

(1) 计算任意一个RP的P(S/Li)。

(2) 计算任意一个RP对应位置信息的权值系数P(Li/S)。

End

2 贝叶斯概率优化算法

针对贝叶斯概率算法在估算最终位置时需要计算每一个RP对应的P(Li/S)后验概率，导致运算量大兼定位时效性较差的问题，本文提出一种贝叶斯概率优化算法，融合WKNN和贝叶斯概率算法。

在离线建库阶段，指纹库中m个RP的AP实测信号S集合为[S1,S2,…,Sm]T，其中第i个RP的数据集合为{(Si1,Si2,…,Sim),(xi,yi)},(Si1,Si2,…,Sim)表示第i个RP接收到的AP实测信号S，(xi,yi)表示第i个RP的当前位置Li。匹配定位阶段，第k个待测点RSSI信号记为Sk=[Sk1,Sk2,…,Skj,…,Skn],k∈N*，可通过式(10)计算待测点与指纹库中各个RP的距离。

(10)

式中：q=1时表示绝对距离公式，q=2时表示欧氏距离公式[15]。本文选择q=2来表示待测点与第i个RP的距离，Di值越小表示两者之间的相似程度越大。

图3 贝叶斯概率优化算法流程图

算法2贝叶斯概率优化算法

输入：指纹库中m个RP接收到的AP实测信号S和位置信息(xi,yi)，移动终端接收到的AP实测信号Sk。

Fori=1：m

(1) 计算待测点与各个RP欧氏距离公式。

(2) 按照距离大小升序排序选择前t个Dk对应的实测信号Sk与Lk。

End

Fori=1：m

(1) 计算前t-1个RP的P(S/Li)。

(2) 计算前t-1个RP对应位置信息的权值系数P(Li/S)。

End

3 实 验

3.1 实验环境布置

本文选取建筑面积为32 m×10 m的一层典型办公环境，其中包括办公室和走廊。本实验使用TP-LINK无线路由器作为AP接入点，华为P10手机终端作为RP参考点采集器与后续进行测试的待测点。为了确保实验区域内RP参考点采集的来自各个AP接入点的RSSI序列有差异，实验测试各个AP节点的信号“距离-损耗”情况。如图4所示，AP节点的距离在8～10 m范围内实测信号强度值趋于平缓，但结合实际成本问题，布置10 m以内即可。

图4 AP接入点“距离-损耗”折线图

按照1 m×1 m规格将实验区域划分成若干个正方形网格，将每一个正方形网格顶点作为RP参考点并从左往右、从下向上依次标注好序号，一共标注363个RP参考点，并且在每个RP参考点不同方向处采集了四次，指纹库指纹数量共1 452个，AP接入点布置如图5所示。

图5 32 m×10 m实验区域图

构建指纹库信息时，不仅需要记录当前位置接收来自每个AP接入点对应的RSSI，而且需要记录当前二维位置坐标(x,y)。在实际采集过程中由于从不同方向处采集四次，因此表1采集(13.8,9)处的指纹信息有4组。

表1 坐标为(13.8,9)处参考点采集的指纹库

3.2 静止状态与运动状态定位实验

为验证本文所提的贝叶斯概率优化算法优越性，实验将行人定位状态分为静止状态与运动状态，同时在实验区域分别对每个状态进行了测试，两种实验状态测试具体步骤如下：

(1) 实验室选择2个待测点(tx1,ty1)和(tx2,ty2)，在设备处于静止状态下每个点测量15组定位结果，并记录下真实坐标与采用传统WKNN算法、贝叶斯概率算法、贝叶斯概率优化算法下的定位坐标。

(2) 行人处于运动状态下，按照设定的真实路径行走，并记录下真实路径与采用传统WKNN算法、贝叶斯概率算法、贝叶斯概率优化算法下的定位路径。

根据步骤(1)，分别测试出静止状态下2个待测点的定位结果，如图6和图7所示。

(a) WKNN与贝叶斯概率算法

(a) WKNN与贝叶斯概率算法

在上述测试中，分别对两个待测点的真实坐标与各算法匹配的定位坐标进行比较，设备处于静止状态下，贝叶斯概率优化算法下的定位坐标相比于WKNN、贝叶斯概率算法更接近真实坐标且未存在较大偏差，稳定性较强。

根据步骤(2)，测试出运动状态下的定位路径对比图，如图8所示。

图8 运动状态下的定位路径图

当行人手持设备处于运动状态下，贝叶斯概率优化算法下的定位路径相比于WKNN波动较小，虽相比贝叶斯概率算法定位稳定性稍差，但整体定位路径相比于WKNN、贝叶斯概率算法更贴近真实路径。

智能手机端安装App后，将指纹信息依次录入指纹库，同时将室内地图导入App中，如图9所示。

图9 数据库采集与室内定位测试

3.3 实验结果比较

(11)

本文选取实验区域内的100个独立且互不相关待测点进行实验。根据实验计算出平均定位误差。图10为WNNN、贝叶斯概率算法和贝叶斯概率优化算法的累积分布函数情况。

图10 定位结果误差曲线

在1 m内WKNN算法定位精度可达57%，贝叶斯概率优化算法定位精度可达73%；在2 m内WKNN定位精度可达88%，贝叶斯概率优化算法定位精度可达92%。表2为算法定位精度与实时性的比较。

表2 算法定位精度与实时性的比较

对表2进行分析：平均定位精度方面，贝叶斯概率优化算法相对于WKNN算法、贝叶斯概率算法分别提高21.49%、18.41%；平均运行时间方面，贝叶斯概率优化算法相对于贝叶斯概率算法减少约61%；定位稳定性方面，贝叶斯概率优化算法虽相对于WKNN算法有所增强，但相对于贝叶斯概率算法稳定性仍需加强。综上所述，本文所提贝叶斯概率优化算法相比当前已有算法在定位精度、稳定性和实时性方面都有一定的改善效果。

4 结 语

本文提出一种贝叶斯概率优化算法，融合贝叶斯概率算法与WKNN算法，相对于传统WKNN、贝叶斯概率算法具有显著优势。实验结果显示，本文算法相比于传统WKNN平均定位精度提高约21.49%，运行稳定性也有所加强。但本文算法仍有值得改进的地方,譬如平均运行时间相对于WKNN算法仅增加约0.54%。未来将进一步改进该算法的实时性与稳定性。