基于RSSI信号特征的室内分区指纹定位算法

高思远，冯秀芳

(太原理工大学 信息与计算机学院，山西 晋中 030600)

0 引 言

常用的基于WiFi的室内定位技术主要有传播模型法和基于WiFi的RSSI(received signal strength indicator)位置指纹法。基于RSSI的位置指纹定位方法在实际环境中有更好的定位效果，且易于部署，因此受到更多学者的青睐，国内外学者相继提出了许多基于WiFi的RSSI位置指纹定位方法。Li Changgeng等将曼哈顿距离引入到WKNN算法中，并根据RSSI值各维的差异是否小于某一特定常数，增大或减小每个维度的RSSI差异[3]，该方法在一定程度上提高了算法与实际物理环境的相似性。XueWeixing等提出了一种利用最大RSSI观测值的平均值来改进RSSI观测值的算法，通过平滑度指数来评价RSSI信号的质量，从而选择合适的RSSI观测值[4]。李华亮等提出了一种基于核函数特征提取的室内定位算法，通过使用核函数特征提取方法训练原始位置指纹，并有效地利用各个接入节点的接收信号强度信息，减少了RSSI信号采集次数和AP个数，降低了平均定位误差[11]。

本文在现有研究的基础上，从离线指纹库构建、子区域划分以及在线位置估计等方面提出了改进的基于RSSI的位置指纹定位方法。

1 基于WiFi的RSSI位置指纹定位算法

基于WiFi的RSSI位置指纹定位算法主要分为两个阶段，离线阶段以及在线阶段[15]。

1.1 离线阶段

构建离线指纹数据库。在待定位区域根据室内环境分布情况，均匀的选取a个参考点RP，标记为RP1、RP2、RP3、…、RPa；b个WiFi信号可接收点AP，标记为AP1、AP2、AP3、…、APb[15]。 在第i个参考点RPi处采集到来自第j个APj的RSSI值标记为：RSSIij=(RSSIi1,RSSIi2,…,RSSIij,…,RSSIib)， 将该参考点所在的区域、物理位置及其RSSI值共同构成一个位置指纹，所有参考点的位置指纹构成离线指纹数据库见表1[15]。

表1 离线指纹库

1.2 在线阶段

在位置指纹定位研究领域中，关于RSSI向量匹配算法的研究成果比较丰富，诸如欧氏距离、概率分布、神经网络、支持向量机、稀疏表示等等[14]。本文采用的匹配算法为欧氏距离法。传统的WKNN算法通常使用欧氏距离进行相似度度量。在线阶段，通过欧式距离(如式(1)所示)计算得出待定位点与离线指纹数据库中所有参考点指纹的欧氏距离

(1)

然后使用KNN算法选择指纹库中与待定位点的欧氏距离最小的K个参考点的物理位置，利用式(2)进行位置估计

(2)

2 基于RSSI信号特征的分区指纹定位算法

基于WiFi的RSSI位置指纹定位算法在取得较高定位精度的同时也存在一定的缺陷。首先，不同类型的AP发射功率不同，在同一位置处的RSSI值存在差异性；同时，在线定位过程中通常使用KNN算法进行位置估计，需要对指纹库中的所有数据进行搜索，计算量较大，搜索效率较低；其次，在定位过程中极易使用两个欧式距离较小而物理距离较大的点进行位置估计从而增大定位误差。为减少以上现象对定位精度的影响，提出基于RSSI信号衰减率(RSSIRATE-SVM)的分区聚类指纹定位算法。算法的主要流程为，首先在离线阶段对待定位区域进行子区域划分，然后使用各参考点处的RSSI信号变化率构建离线指纹数据库；在线定位阶段中，使用SVM算法对待定位点进行区域划分，再使用二级指纹定位算法进行精确定位。

2.1 离线阶段

2.1.1 子区域划分

传统的位置指纹定位算法中在线定位阶段使用KNN算法进行位置估计，需将待定位点处的信号指纹与指纹库中的所有指纹进行对比，根据其差异性进行位置估计。由于人为对待定位区域进行划分时忽略了RSSI信号的分布特性，因此为了提高搜索效率，减少随机性因素的干扰以及减少样本搜索数量，本文依据RSSI信号分布特性提出了基于RSSI信号衰减率的子区域划分法[15]。

(1)粗略划分

由于RSSI信号容易受多径传播以及室内环境的影响而不稳定，通常使用对数路径模型来描述其在室内环境中的传播，如式(3)所示[15]。其中RSSI(d0) 表示距离信号发射点d0m处(通常为1 m)的信号强度值；n表示路径损耗系数，受周围环境影响，Xσ表示无线信号发送节点到接收节点之间的遮蔽影响因子，它受室内环境所影响，是标准差为σ的高斯分布随机变量，d表示待定位节点与信号发射节点间的距离[15]

(3)

根据式(3)可得，RSSI信号与信号发射装置间的距离存在一定的映射关系。研究表明，来自同一AP的RSSI均值在不同物理位置处的表现力不同，尽管RSSI值存在波动，但整体趋势是越靠近AP的位置接收到的RSSI值越强。我们使用RSSI信号衰减率描述RSSI信号随距离的变化情况，根据式(3)可构建RSSI信号衰减率模型，如式(4)所示[15]

rate(d)=-10nd0·(d·ln10)-1

(4)

图1描述了随着距离的变化RSSI信号的变化率情况。根据RSSI信号随着距离变化的分布情况可以看出，随着距离的不断增大RSSI信号强度值逐渐减小，其信号变化幅度逐渐减弱；由RSSI信号变化率分布图可以看出存在一个点p，p点处与信号发射点AP的距离为rm,在该点处RSSI信号变化率发生明显变化，我们称点p为最优衰减率特征点[15]。

根据图1可以看出，当与AP的物理距离d≥r时，RSSI信号变化率逐渐趋于平缓，信号变化幅度不明显，对RSSI信号空间距离度量的贡献度较小。因此以最优衰减率特征点p处对应的距离r为半径进行区域划分以实现最优分区，使得RSSI特征较相似、RSSI信号变化明显的参考节点更为集中。

图1 RSSI信号衰减率变化

以各AP为中心，特征点p处对应的距离r为半径进行粗略区域划分，将室内定位区域划分为l个圆形分类区areal,l∈[1,n]， 如图2所示[15]。

图2 区域划分

(2)精确划分

由于粗略划分阶段，采用圆形分类区进行子区域划分，因此存在部分参考点未被划分进任一子区域，称这部分参考点为孤点；精确划分阶段，采用SVM算法对孤点进行精确分类[15]。

将已分类的参考节点作为训练集对SVM进行多分类训练，得出最优分类模型，训练样本集为 {(xi,ci)},i∈[1,n]， 若xi属于areal，则标记c=1否则标记c=0， 超平面方程为[15]

f(x)=ϖ·φ(x)+b

(5)

(6)

2.1.2 离线指纹库建立

传统的位置指纹定位算法中使用各参考节点处的RSSI值建立信号指纹数据库，然而复杂的室内环境使得RSSI信号极易受到干扰，在线更新指纹数据库需要耗费大量的人力物力；同时不同型号的AP其信号稳定程度及发射功率不同，很容易影响定位精度。因此本文提出使用各参考点处的RSSI信号变化率构建离线指纹数据库。

由式(4)可以看出，信号衰减率与环境影响因子Xσ无关，因此，使用各参考点处的信号衰减率构建离线指纹数据库可以忽略环境影响因子Xσ对定位结果的影响。

在各参考节点处采集来自各AP的RSSI信号值，通过式(4)计算RSSI信号衰减率。参考点RPm处的信号衰减率指纹为ratem=(rate1,rate2,…，raten)， 所有参考点处的信号衰减率及其物理位置构成离线指纹数据库，见表2[15]。

表2 RSSI-RATE指纹库

2.2 定位阶段

在线定位阶段首先使用SVM算法确定待定位点所属子区域，其次使用二级指纹定位算法对待定位点进行位置估计。

2.2.1 RSSID指纹

在线定位阶段引入SSD(single strength difference，SSD)的思想。即利用同一物理位置处，各分量RSSI之间的信号强度差构建RSSID信号序列。

根据式(3)有

(7)

(8)

由式(7)、式(8)可得

(9)

根据式(9)可得ΔRSSI与Xσ无关。即Xσ的变化不会对同一位置处不同AP的信号强度差值ΔRSSI产生影响，可提高RSSID指纹的稳定性。RSSID指纹构造公式如下

RSSIDi,j=RSSIi,j-RSSIi,j+1,j∈[1,n-1]
RSSIDi=(RSSIDi1,RSSIDi2,…,RSSIDi,n-1)

(10)

2.2.2 二级指纹精确定位

在待定位点所属区域中首先使用KNN算法计算出离线指纹库中与待定位点的RSSI信号变化率指纹距离最小的ak个参考点集RPa

RPa={RPa1,RPa2,…,RPak}
RPa⊆RP,1≤ak

(11)

其次，使用KNN算法求出与待定位点的RSSID指纹距离最小的前bk个参考点集RPb

RPb={RPb1,RPb2,…,RPbk}
RPb⊆RP,1≤k≤m

(12)

根据参考点集RPa、RPb求出最相似参考点集RPsim=RPa∩RPb， 最后使用KNN算法利用最相似参考点集对待定位点进行位置估计。

本文所提算法流程如图3所示。

图3 算法流程

3 实验结果与分析

为验证本文所提算法的有效性，使用MATLAB R2014b进行仿真实验与分析。本次实验在一面积为11 m×7 m的实验场地进行，在室内布置3个信号发射装置，物理位置分别为 (2.5,3),(6,5),(9.5,2.5)。 在房间内部以 1 m 为间隔设置60个参考节点，在房间边缘处以0.5 m为间隔设置72个参考点。离线阶段在参考点处采集RSSI信号序列建立离线指纹库，随机生成20个待定位点的指纹数据作为测试数据。将本文所提算法与基于KNN算法、WKNN算法以及贝叶斯算法的定位效果进行对比，实验结果如下所示。

3.1 r的选取

通过实验对子区域划分半径r的选取进行了分析。实验测定了当子区域划分半径分别为2 m、2.5 m、3 m、3.5 m、4 m以及4.5 m时，使用KNN算法对待测点进行位置估计时的定位误差，实验结果见表3[15]。

表3 子区域划分半径及定位误差

表3从定位误差以及计算量等方面对子区域划分半径的定位效果进行了分析。根据表3可以看出，以2 m为子区域划分半径时平均定位误差为3.13 m，以2.5 m为子区域划分半径时其平均定位误差为1.26 m，相比划分半径为2 m时的定位误差下降了约60%，数据计算量是初始计算量的1.73倍；以3 m为子区域划分半径时其平均定位误差为0.88 m，相比以2.5 m为半径进行子区域划分时定位误差下降了约21%，数据计算量是初始计算量的2.5倍；以3.5 m为子区域划分半径时，其平均定位误差为0.77 m，数据计算量是初始计算量的3.13倍；以4 m为半径进行子区域划分时，平均定位误差为0.75 m，数据计算量是初始计算量的4.18倍；以4.5 m为半径进行子区域划分时，平均定位误差为0.71 m，数据计算量是初始计算量的4.78倍[15]。

图4描述了以不同半径进行子区域划分时的定位误差，可以看出当子区域划分半径小于3 m时，定位误差较大且变化较为明显；当子区域划分半径大于3 m时，定位误差较小且变化逐渐趋于平稳。根据实验结果，选择以3 m为半径进行子区域划分，可在计算量较小的情况下取得较高的定位精度[15]。

图4 子区域划分半径及其误差分布

图5描述了以不同半径进行子区域划分时的误差累计分布图。根据图5可以看出子区域划分半径大于3 m时的定位效果明显优于子区域划分半径小于3 m时的情况[15]。

图5 以不同半径进行子区域划分的误差累计分布

3.2 RSSIRATE-SVM算法性能验证

图6为使用本文所提算法RSSIRATE-SVM与使用RSSI信号指纹结合KNN、WKNN、Bayes算法的定位误差分布图。根据图6可以看出，本文所提RSSIRATE-SVM算法定位误差与其它3种算法相比误差较小。

图6 RSSIRATE-SVM、KNN、WKNN、Bayes算法定位误差分布

表4从最大误差、最小误差以及平均误差等方面对RSSIRATE-SVM、KNN、WKNN、Bayes算法的定位效果进行了对比。结合表4可得，KNN算法的平均定位误差为1.85 m，WKNN算法的平均定位误差为1.64 m，Bayes算法的平均定位误差为1.37 m，RSSIRATE-SVM算法的平均定位误差为0.91 m。由此可得，本文提出的基于RSSI信号变化率的区域划分算法及二级指纹定位算法可以有效降低定位误差，提高定位匹配度。

表4 RSSIRATE-SVM、KNN、WKNN、Bayes定位误差对比

4 结束语

本文提出的基于RSSI信号衰减率的分区聚类室内指纹定位算法，通过使用RSSI信号衰减率选择最优区域划分半径，降低了定位过程中出现两个点RSSI指纹欧式距离较小而物理距离较大的情况对定位精度的影响；同时区别于传统的使用RSSI信号值建立离线指纹库的方法，提出使用不同参考点处的RSSI信号衰减率建立离线指纹库，降低了定位过程中由于环境变化干扰RSSI信号而引起的误差。下一步将对离线指纹数据库的实时更新进行深入研究。