-
随着移动互联网的高速发展和智能移动终端的普及,移动用户对实时、准确的位置信息需求与日剧增。基于位置的服务(LBS)在民用、商用、军用、应急救援中具有广阔应用前景而受到人们普遍关注。目前国内外LBS应用大多采用GPS卫星定位,由于信号强度受到建筑物、墙壁等的影响而大大衰减,导致GPS接收机在高楼密集的城市或者室内运行时,定位精度降低甚至不能完成定位过程。
基于WiFi的室内定位技术利用移动终端从无线接入点(AP)接收到的信号来确定用户位置,能提高现有设备的利用率,低成本地实现便捷高效的定位服务,成为近年来室内定位技术研究的热点。在WIFi室内定位技术中,相比于基于信号到达时间(TOA)、信号到达角度(AOA)等方法,基于接收信号强度指示(RSSI)的指纹定位技术由于其对设备要求低、实现简单而被普遍采用。
由于WiFi信号传播的时变特性和环境因素的影响,使得终端在线接收RSSI的测量值与离线指纹库存在较大差异。此外,一般的WiFi指纹定位计算需要遍历所有参考点指纹,其在多楼层环境中应用时,定位系统中指纹数量增多,导致匹配计算的复杂度成倍增加。
研究表明,通过利用定位区域环境的先验信息可以降低信号传播过程中由于障碍物导致的信号非视距(NLOS)偏差等而提高定位精度[1-3]。文献[4]应用地图信息建立了用于室内定位的衰减系数(AF)模型,但此模型不适用于指纹定位方法,且缺少基于这种模型的位置估计算法的结果验证,因此在实际应用中其准确性和有效性无法保证。在楼层判别方面,文献[5]提出了联合加速度传感器和气压计计算高度从而判别楼层的方法,然而气压计需要定期校准且其测量值受环境影响较大,因此无法获得稳定的楼层判别准确率。
针对上述问题,本文提出基于地图环境先验信息的WiFi指纹定位方法,首先,建立地图环境信息的统计模型,并采用仿射传播聚类算法对指纹进行离线训练,以减小定位阶段的计算复杂度。进一步,为了弥补WiFi定位在高度上的误差导致楼层判别准确率低,提出了基于RSSI阈值的楼层判别算法,以提高多楼层定位的准确率。最后,利用基于地图信息模型的位置估计算法定位,以减少NLOS偏差、干扰、噪声等的影响,提高WiFi定位的精度和稳定性。
-
WiFi指纹定位包括离线阶段和在线阶段两个步骤,首先在离线阶段建立定位区域的指纹库,使得指纹库尽可能准确地表达每个参考点的信号特征;然后在线阶段通过测量用户终端当前位置的RSSI,利用合适的搜索或匹配算法确定终端位置。下面详细介绍各个阶段的操作步骤。
首先确定遍布定位区域内的N个参考点,即$\text{R}{{\text{P}}_{i}}$,$i\in \{1,2,\cdots ,N\}$。然后,遍历这些参考点进行RSSI采样,并把各参考点的指纹存储为$\text{F}{{\text{P}}_{i}}\text{=(MA}{{\text{C}}_{m}}\text{,RSS}{{\text{I}}_{i}}{{\text{)}}^{\text{T}}},m\in \{1,2,\cdots ,n\}$,其中$\text{MA}{{\text{C}}_{m}}$表示当前参考点搜索到的第m个AP的MAC地址。最后,对每个参考点的RSSI进行多次采样平均,并与其位置坐标$(x,y,z)$存为一组,形成指纹图(radio map,RM)。指纹图的示例如表 1所示,假设定位区域内共能搜索到12个AP,为了计算方便以及减少信号较弱的AP对计算结果造成的影响,将其RSSI统一设置为最小值-110 dBm。
表 1 指纹图
坐标(x,y,z) MAC1 /dBm MAC3/dBm … MAC12/dBm RP1 (0,0,F1) -56 -78 … -110 RP2 (0,3,F1) -43 -110 … -90 RP3 (0,6,F1) -69 -90 … -110 现有的指纹匹配计算方法可分为确定性匹配算法(如K-最近邻居算法,K-NN)和概率匹配算法(如最大后验估计MAP,或最小均方根误差MMSE)[6-7]。K-NN算法作为典型的确定性匹配算法被普遍使用。其基本原理是通过计算当前信号指纹与指纹库中各个参考点的指纹的欧式距离,选出与当前指纹距离最近的k个参考点,取其坐标平均值作为终端位置。具体计算步骤如下。
1) 计算当前位置指纹FPm与指纹图中所有参考点指纹的欧式距离。设RSSI向量φ表示指纹FPm中来自n个AP的RSSI向量,与指纹图中参考点RPi的RSSI向量之间的欧式距离为:
$${{d}_{m}}=||{{\phi }_{i}}-{{\phi }_{m}}|{{|}^{2}}$$ (1) 2) 对dm进行升序排序,选出前k个指纹并平均其平面位置坐标(x,y),得到当前位置坐标。
$$\left\{ \begin{align} & x={1}/{k\sum\limits_{i=1}^{k}{{{x}_{i}}}}\; \\ & y={1}/{k\sum\limits_{i=1}^{k}{{{y}_{i}}}}\; \\ \end{align} \right.$$ (2) -
为了利用地图环境的先验信息进行WiFi定位,需要建立地图环境的数学模型,包括:1) 定位区域模型;2) AP覆盖区域模型;3) 终端与AP之间的距离模型。
1) 定位区域模型
设终端所在位置的二维坐标为$p={{[x,y]}^{\text{T}}}$,则该位置可由均匀概率密度函数表示为:
$$f(p)=\left\{ \begin{align} & 1/{{A}_{R}} \\ & \text{ }0 \\ \end{align} \right.\text{ }\begin{array}{*{35}{l}} p\in R \\ 非定位区域 \\ \end{array}$$ (3) 式中,$p\in R$,R为地图中定位区域;${{A}_{R}}$为此区域面积。式(3)描述了均匀分布的地图模型,只包含一个变量${{A}_{R}}$,即此概率密度函数完全由R所描述。如图 1中,定位区域R为空白部分,AP的位置为$p_{i}^{a}$,$B(R)$为地图边界。通过地图建模得到待定位区域R,则可以避免用户被定位到非定位区域,即图中阴影区域。
2) AP覆盖区域模型
若位于p 点的终端接收到第i 个AP的RSSI超过阈值时,则与第i 个AP建立连接,故每个APi 均有一个固定覆盖区域R(i),但难以准确获取每个AP的AP的实际覆盖区域,故采用如下简化模型来计算AP的覆盖区域。
定义$\text{A}{{\text{P}}_{i}}$覆盖区域半径为${{d}_{\max }}_{\text{,}i}$,其大小依赖于$\text{A}{{\text{P}}_{i}}$辐射功率和信号传播环境。把在某位置处终端能够连接到的AP称为观测AP,记为${{z}_{i}},i\in Z$,Z为与终端相连的观测AP的集合,则观测AP的数量为${{N}_{z}}=\left| Z \right|$。如果终端与APi相连,那么终端位置p满足$p\in {{R}^{(i)}}\bigcap R$,即终端位于区域R与${{R}^{(i)}}$相交的区域。因此,定位算法估计终端位置的搜索区域为:
$${{R}^{(z)}}\overset{\text{ }\!\!\Delta\!\!\text{ }}{\mathop{=}}\,(\underset{i\in z}{\mathop{{{R}^{(i)}}}}\,)\bigcap R$$ (4) 3) 终端与AP的距离模型
WiFi指纹定位系统中,终端与第i个观测AP的距离模型定义为:
$${{z}_{i}}={{d}_{i}}(p)+{{b}_{i}}(p)+{{n}_{i}}(p)$$ (5) 式中,${{d}_{i}}(p)=\left\| p-p_{i}^{a} \right\|$为终端所在位置p与$\text{A}{{\text{P}}_{i}}$的传播距离;${{b}_{i}}(p)$表示障碍物所带来的NLOS偏差,设${{b}_{i}}(p)$服从高斯分布,即${{b}_{i}}(p)\tilde{\ }N({{\mu }_{b,i}}(p),{{\sigma }_{b,i}}(p))$,当视距LOS传播时${{b}_{i}}(p)=0$;${{n}_{i}}(p)$是射频干扰等引入的距离误差,其服从高斯分布,即${{n}_{i}}(p)\tilde{\ }N(0,\sigma _{n,i}^{2}(p))$。该模型中参数${{\mu }_{b,i}}(p)$、$\sigma _{b,i}^{2}(p)$和$\sigma _{n,i}^{2}(p)$的计算见第3.1节。
-
根据建立的室内地图环境模型,提出的多楼层WiFi室内定位系统如图 2所示,具体施步骤如下。
1) 离线阶段:完成定位区域的地图环境信息建模、指纹图的建立与指纹聚类。
① 地图环境建模,具体步骤见1.2节。
② 建立指纹图。
与一般WiFi指纹定位技术相同,包含指纹采集与指纹的平均。记录AP的位置坐标,将定位区域内$\text{A}{{\text{P}}_{i}}$的坐标$(x,y,z)$与$\text{MA}{{\text{C}}_{i}}$存为一组,其中z坐标表示$\text{A}{{\text{P}}_{i}}$所在楼层。并把参考点测量到的第i个AP的RSSI的平均值记为${{P}_{m}}_{(i)}$,m为参考点标号。
③ 指纹聚类。
通过在指纹定位方法中加入指纹聚类,可以降低定位的计算复杂度,提高定位算法的实时性以及精度。文献[8]采用模糊c-均值聚类(FCM)算法对指纹聚类,但此种聚类方法在指纹点个数较大时,会导致计算量大大增加。文献[9]采用经典的k-均值(k-means)算法将指纹聚类,此方法需要通过随机方式选择初始类首,聚类结果依赖于初始聚类中类首的选择,容易陷入局部极值。仿射传播聚类[10]无需随机选择类首,且算法收敛速度快,更适于RSSI指纹图的预处理。
本文利用仿射传播聚类算法对所采集的指纹聚类,聚类结果如图 3所示,聚类完成后将此189个指纹点划分为17个类。其中每个颜色的圆点属于一类,类首与类成员间通过直线连接。从图中可以看出,通过指纹聚类,可将物理位置相近的点划分在一个类中。在定位时,为避免指纹匹配到错误的类中,需选择少数n个类作为位置计算的参考类。定位算法利用参考类的类首及其类成员的位置信息计算终端位置。通过指纹聚类将定位计算的指纹搜索区域缩小至少数类中,既降低了指纹匹配计算的复杂度,也提高了定位精度。
在计算复杂度方面,基于K-NN的全局匹配算法的计算复杂度为$o(Nm)$,其中N为参考点个数,m为每个参考点的信号强度维度。而基于仿射传播聚类的匹配算法的计算复杂度为$o({{n}_{c}}m+{{n}_{m}}m)$,其中${{n}_{c}}$为类首个数,${{n}_{m}}$表示类成员个数。由于${{n}_{c}}+{{n}_{m}}\ll N$,故基于仿射传播聚类的匹配算法大大减少了匹配计算的复杂度。
2) 在线阶段:包含楼层判别和基于地图环境模型的位置估计两部分。
楼层判别中,利用RSSI在楼层间的衰落特征,并通过建立RSSI阈值与AP数量的关系,确定当前终端所在楼层,算法具体步骤见第2节。
采用MAP算法估计终端位置,结合地图建模所得的终端定位区域模型R、AP覆盖区域模型${{R}^{(i)}}$以及终端与AP连接的距离模型${{z}_{i}}$,得到终端位置估计的概率密度函数[11]为:
$$f(z|\tilde{p})=\prod\limits_{i\in Z}{N({{z}_{i}};{{d}_{i}}(\tilde{p})+{{\mu }_{b,i}}(\tilde{p}),\sigma _{n,i}^{2}(\tilde{p})+\sigma _{b,i}^{2}(\tilde{p}))}$$ (6) 式中,$\tilde{p}\in {{R}^{(Z)}}$;${{z}_{i}}\overset{\text{ }\!\!\Delta\!\!\text{ }}{\mathop{=}}\,{{\left\lceil {{z}_{i}},\forall i\in Z \right\rceil }^{\text{T}}}$。利用上式,计算指纹图中各参考点的概率,然后通过MAP估计得到终端的位置。可以看到,地图环境信息模型利用了信号传播环境中的先验信息,对提高定位精度起到重要作用。
-
研究表明,WiFi无线信号穿过建筑墙体时,由于通常楼层间墙壁常使用金属加强的混凝土,信号强度可能出现较大的衰减(15~20 dBm)[12]。此现象表明:1) 当物理距离相等时,来自同楼层的AP的RSSI强于其他楼层AP的RSSI;2) 根据三角定理,当不同AP的平面投影即$(x,y)$坐标相同时,终端与同楼层的AP距离更短。综上两个条件,使得平面位置即$(x,y)$坐标相同时,来自其他楼层的AP的RSSI明显的低于来自于本楼层AP的RSSI。利用楼层间RSSI的差异,提出的楼层判别算法实现步骤如下。
1) 设已知AP的位置坐标为$\mathbf{p}_{i}^{a},i\in \{1,2,\cdots ,{{N}_{a}}\}$,将AP的MAC地址与位置存为一组$\text{(MAC}m\text{, }p_{i}^{a}\text{)}$,$r\in \{1,2,\cdots ,{{n}_{F}}\}$,${{F}_{r}}$代表楼层。
2) 设置RSSI阈值R0,统计各个楼层的阈值内AP数量${{N}_{{{F}_{r}}}}$,并返回${{N}_{{{F}_{r}}}}$最大值对应的楼层Fr:
$${{F}_{r}}=\arg \max ({{N}_{{{F}_{r}}}})$$ (7) 式中,${{N}_{{{F}_{r}}}}\in \{1,2,\cdots ,n\}$;n为定位区域内AP的数量;Fr即为当前终端所在楼层。
-
为了得到概率密度函数$f(z|\tilde{p})$具体的表达式,首先需要估计观测AP距离模型${{z}_{i}}$中的参数,即NLOS偏差的均值${{\mu }_{b,i}}(p)$与方差$\sigma _{b,i}^{2}(p)$和距离误差${{n}_{i}}(p)$的方差$\sigma _{n,i}^{2}(p)$值。
室内环境中,终端的接收信号功率可表示为[13]:
$${{P}_{rx}}(z)={{P}_{0}}-\rho z$$ (8) 式中,$\rho $是正系数;${{P}_{0}}$为给定距离时的参考功率值。故终端与第i个观测AP连接的距离模型为:
$${{z}_{i}}=({{P}_{0}}-{{P}_{rx}}({{z}_{i}}))/\rho $$ (9) 为了得到参数${{\mu }_{b,i}}(p),\sigma _{b,i}^{2}(p)$和$\sigma _{n,i}^{2}(p)$的线性模型,采用基于最大似然估计(ML)和回归分析的参数估计方法,如图 4所示。
首先,利用观测AP集合$\{{{z}_{i}},i\in Z\}$以及位置的概率密度函数$f(p)$,得到距离误差标准差的最大似然估计$\{{{\hat{\sigma }}_{n}}(t)\},t\in \{1,2,\cdots ,{{N}_{d,\max }}\}$,以及${{b}_{i}}(p)$的均值以及方差的最大似然估计$\{{{\hat{\mu }}_{b}}(t),{{\hat{\sigma }}_{b}}(t)\},$$t\in \{1,2,\cdots ,{{N}_{0,\max }}\}$。其中${{N}_{d,\max }}$为误差的量化值,${{N}_{0,\max }}=\max {{N}_{0}}({{p}_{m}},{{p}_{i}})$为${{p}_{i}}$与${{p}_{m}}$间障碍物数量的最大值,${{N}_{0}}({{p}_{m}},{{p}_{i}})$为${{p}_{i}}$与${{p}_{m}}$间障碍物的数量。
进一步,在估计出离散化的参数$\{{{\hat{\mu }}_{b}}(t),\hat{\sigma }_{b}^{2}(t)\}$及$\{{{\hat{\sigma }}_{n}}(t)\}$的基础上,通过最小二乘回归分析得到连续的线性模型。
障碍物偏差${{b}_{i}}(p)$的标准差模型为:
$${{\sigma }_{b,i}}(p)=\max \{{{\sigma }_{b,0}}-{{\sigma }_{b,m}}{{N}_{0}}(p,p_{i}^{a}),0\}$$ (10) 式中,${{\sigma }_{b,0}}$、${{\sigma }_{b,m}}$表示此模型的正系数。
偏差均值模型为:
$${{\mu }_{b,i}}(p)={{\mu }_{b,0}}{{({{N}_{0}}(p,p_{i}^{a}))}^{{{\alpha }_{b}}}}$$ (11) 式中,参数${{\alpha }_{b}}$为乘方系数;${{\mu }_{b,0}}$为正均值。
距离误差标准差模型为:
$${{\sigma }_{n,i}}(p)={{\sigma }_{n,0}}{{({{d}_{i}}(p)/{{d}_{0}})}^{{{\beta }_{n}}}}$$ (12) 式中,${{\sigma }_{n,0}}$为相对于传输距离${{d}_{0}}$的误差值;${{\beta }^{n}}$为路径损耗指数。
把式(10)~式(12)中得到的估计参数,即NLOS偏差均值${{\mu }_{b,i}}(p)$及方差${{\sigma }_{b,i}}^{2}(p)$和距离误差方差${{\sigma }_{n,i}}^{2}(p)$代入式(6),得到基于地图环境信息的位置估计概率密度函数为:
$$\begin{matrix} f(z|\tilde{p})=\prod\limits_{i\in Z}{N({{z}_{i}};{{d}_{i}}(\tilde{p})+{{\mu }_{b,0}}{{({{N}_{0}}(\tilde{p},\tilde{p}_{i}^{a}))}^{{{\alpha }_{b}}}}}, \\ \max \{{{({{\sigma }_{b,0}}-{{\sigma }_{b,m}}{{N}_{0}}(\tilde{p},\tilde{p}_{i}^{a}))}^{2}},0\}+ \\ \sigma _{n,0}^{2}{{({{d}_{i}}(\tilde{p})/{{d}_{0}})}^{2{{\beta }_{n}}}}) \\ \end{matrix}$$ (13) 然后,根据所得概率密度函数$f(z|\tilde{p})$通过MAP算法估计出终端位置。
-
采用MAP位置估计算法得到终端位置为:
$${{\tilde{p}}_{\text{MAP}}}(z)=\underset{{\tilde{p}}}{\mathop{\arg \max \ln f(z|\tilde{p})}}\,$$ (14) 式中,${{\tilde{p}}_{\text{MAP}}}(z)$表示终端位置;$\tilde{p}$为参考点的位置。本文方法在离线阶段进行指纹聚类,并且利用了地图环境信息模型,故在线阶段的定位估计步骤为:
1) 利用第1节中指纹匹配算法K-NN得到当前楼层中与当前指纹最近的n个类首及其所在位置区域${{R}^{(C)}}$;
2) 利用式(3)和贝叶斯准则,得到基于地图环境信息模型的终端位置估计为:
$${{\tilde{p}}_{\text{MAP}}}(z)=\underset{\tilde{p}\in ({{R}^{(Z)}}\bigcap {{R}^{(C)}})}{\mathop{\arg \max \ln f(z|\tilde{p})}}\,$$ (15) 式中,${{R}^{(Z)}}\bigcap {{R}^{(C)}}$为定位搜索区域;$\tilde{p}$为搜索区域内的指纹点;概率密度函数$f(z|\tilde{p})$由式(13)给出。
Indoor Map Information Based WiFi Positioning Technology for Multi-Floor Buildings
-
摘要: 针对多楼层环境的室内定位需求,提出了一种基于地图环境先验信息的WiFi指纹定位方法。首先在离线阶段建立地图环境信息模型并对指纹进行仿射传播聚类,然后在线阶段采用RSSI阈值的楼层判别算法确定楼层,并结合地图信息模型和最大后验估计方法计算出终端位置。实验结果表明,相比于传统的指纹定位方法,室内定位技术不仅能提高定位精度,并且降低了在线阶段指纹匹配计算的复杂度。Abstract: In order to implement multi-floor buildings accurate location, the map information based indoor position scheme is proposed in this paper. Firstly, the map information model and affinity propagation method for fingerprints clustering are explored in offline phase. Then, the received signal strength indication (RSSI) threshold based floor identification method is put forward. Finally, the terminal positions are obtained by using the map information model and maximum posteriori position estimation method. Experimental results show that the proposed indoor position scheme can effectively enhance the location estimation accuracy and reduce the computation complexity for multi-floor buildings.
-
表 1 指纹图
坐标(x,y,z) MAC1 /dBm MAC3/dBm … MAC12/dBm RP1 (0,0,F1) -56 -78 … -110 RP2 (0,3,F1) -43 -110 … -90 RP3 (0,6,F1) -69 -90 … -110 -
[1] DAVIDSON P, COLLIN J, TAKALA J. Application of particle filters for indoor positioning using floor plans[C]//Ubiquitous Positioning Indoor Navigation and Location Based Service. Kirkkonummi, Finland:IEEE, 2010. [2] 周瑞. 应用室内结构布局提高Wi-Fi定位精度和稳定性[J]. 电子科技大学学报, 2013, 42(2):295-299. http://www.cnki.com.cn/Article/CJFDTOTAL-DKDX201302023.htm ZHOU Rui. Improving of WiFi positioning precision and stability based on indoor structure and layout[J]. Journal of University of Electronic Science and Technology, 2013, 42(2):295-299. http://www.cnki.com.cn/Article/CJFDTOTAL-DKDX201302023.htm [3] SANGWOOK B, SEOKSEONG J, YU Chan-su, et al. Characteristics of a large-scale WiFi radiomap and their implications in indoor localization[C]//International Conference on Network of the Future. Paris, France:IEEE, 2013. [4] LOTT M, FORKEL I. A multi-wall-and-floor model for indoor radio propagation[C]//International Conference on Vehicular Technology. Rhodes, Greece:IEEE, 2001. [5] YUNKI K, SEUNGHWAN C, LEE J. Height estimation scheme of low-cost pedestrian dead-reckoning system using Kalman filter and walk condition estimation algorithm[C]//IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM). Wollongong, Australia:IEEE, 2013. [6] HUANG Yung-fa, ZHENG You-ting. Performance of an MMSE based indoor localization with wireless sensor networks[C]//International Conference on Networked Computing and Advanced Information Management (NCM). Gyeongju, South Korea:IEEE, 2010. [7] HARA S, ANZAI D. Use of a simplified maximum likelihood function in a wlan-based location estimation[C]//IEEE Conference on Wireless Communications and Networking. Budapest, Hungary:IEEE, 2009. [8] SUROSO D J, SOORAKSA P. Fingerprint-based technique for indoor localization in wireless sensor networks using fuzzy c-means clustering algorithm[C]//International Symposium on Intelligent Signal Processing and Communications Systems (ISPACS). Chiang Mai, Thailand:IEEE, 2011. [9] THERDPHAPIYANAK J, PIROMSOPA K. An analysis of suitable parameters for efficiently applying K-means clustering to large TCP dump data set using Hadoop framework[C]//International Conference on Electrical Engineering, Computer, Telecommunications and Information Technology. Krabi, Thailand:IEEE, 2013. [10] FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814):972-977. doi: 10.1126/science.1136800 [11] PORRAT D, COX D C. UHF propagation in indoor hallways[C]//International Conference on Communications. Anchorage Alaska, USA:IEEE, 2003. [12] WU C S, ZHENG Y, LIU Y H, et al. WILL:Wireless indoor localization without site survey[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(4):64-72. http://cn.bing.com/academic/profile?id=94b481f95150ac7c2b2f649909fa6b8c&encoded=0&v=paper_preview&mkt=zh-cn [13] MONTORSI F, MAZUELAS S, VITETTA G M, et al. On the performance limits of map-aware localization[J]. IEEE Transactions on Information Theory, 2013, 59(8):5023-5038. doi: 10.1109/TIT.2013.2257915