WiFi指纹定位的一种新组合算法

张 伟,花向红 ,邱卫宁,薛卫星,周定杰

(1.武汉大学 测绘学院,湖北 武汉 430079；2.武汉大学 灾害监测与防治研究中心，湖北 武汉 430079；3.云南省测绘工程院,云南 昆明 650033)



WiFi指纹定位的一种新组合算法

张 伟1,2,花向红1,2,邱卫宁1,2,薛卫星1,2,周定杰3

(1.武汉大学 测绘学院,湖北 武汉 430079；2.武汉大学 灾害监测与防治研究中心，湖北 武汉 430079；3.云南省测绘工程院,云南 昆明 650033)

探讨AP选取策略和贝叶斯位置估计算法对基于RSS的WiFi室内定位技术位置估计精度的影响。国内外学者分别对AP选取算法和贝叶斯位置估计算法进行了大量的研究。为了进一步深入研究不同算法的优劣性，利用组合优化的思想对不同算法进行组合，通过找出最优算法组合从而提升WiFi室内定位系统的性能。基于互信息最小化的AP选取策略和考虑AP相关性的贝叶斯位置估计算法，提出一种新的WiFi指纹定位组合算法。实验分析表明：新算法具有良好的实用性和定位性能。

WiFi室内定位；AP选取；贝叶斯位置估计；组合优化；定位性能

基于位置服务[1]的快速发展推动着室内定位和导航技术[2]的深入研究。尽管GNSS[3-4]实现了室外高精度定位导航，但是由于室内信号的遮挡，GNSS在室内定位的应用依旧存在着较大的局限[5-6]。目前，不同的室内应用场景通常需要考虑特定的室内定位技术实施方案。已有的室内定位技术，包括基于INS的行人航位推算[7]、基于摄像头或者扫描仪的SLAM(Simultaneous Localization And Mapping)技术[8-9]、基于射频或者声波的交会定位技术[10]、基于地磁匹配的定位技术[11]等。然而，上述技术都需要考虑定位系统的性能和成本。考虑到基于RSS(Received Signal Strength)的WiFi室内定位技术的低成本和简单易行的特性，国内外学者针对WiFi室内定位技术的特定问题进行大量的探讨[12]。文献[13]提出基于贝叶斯后验估计原理的WiFi室内定位方案，然而该方法采用最大均值的AP(Access Point)选取策略，其AP选取策略没有考虑AP之间的相关性。文献[14]考虑AP对指纹点的信息增益提出基于信息增益最大化的AP选取策略，然而其定位算法采用了经典的KNN算法。文献[15]提出一种互信息最小化的线上AP选取策略，该算法在定位阶段需要进行大量的运算以求得最优的AP组合，因此实用性较差。考虑到AP选取算法和位置估计策略对WiFi定位系统性能的影响，本文对4种不同的组合策略进行比较分析，并给出定位性能最佳的最优化组合。

1 WiFi指纹定位的组合算法

近年来，国内外学者对AP选取算法进行大量的研究，其中AP选取的两个常用方法是信息增益最大化策略和互信息最小化策略。此外，位置估计算法中贝叶斯估计的实现策略直接影响WiFi系统的位置估计性能。目前大多数贝叶斯估计实现算法假设可用的AP相互独立，这一条件在现实中是难以满足的。然而基于频率统计算法的多个离散变量的联合概率密度的计算策略能够考虑AP之间的相关性，基于该策略的贝叶斯估计更具有实用性。

1.1 AP选取策略

室内环境复杂多变的特性和AP相互之间的影响严重影响基于RSS的WiFi室内定位系统的性能。选取最优AP组合不但能够提升WiFi室内定位系统的性能，同时还能避免AP数量冗余导致的计算负担。假定一个WiFi定位系统可用的AP个数为N，则选取其中M个AP的优化子集可以将信号空间的维度从N维减少到M维，从而减少计算量。信息增益最大化的AP选取策略和互信息最小化的AP选取策略是目前常用的两种AP选取方法。前者考虑AP对于指纹点区分度的贡献大小，位置信息增益越大，指纹点的区分度越大。后者考虑AP之间的相关性，互信息越小，AP之间的相互影响越小。

AP的位置信息增益计算算式为

InfoGain(APi)=H(L)-H(L|APi).

(1)

式中：L表示位置；InfoGain(APi)表示第i个AP对位置的信息增益；H(L)表示位置的信息熵；H(LAPi)表示位置L在给定AP下的条件信息熵。离散随机变量的信息熵算式为

(2)

式中：X表示具有N个可取离散值的随机变量；p(xi)表示X取xi的离散概率密度；log10表示取以10为底的对数。

基于信息增益最大化的AP选取策略分别计算每个可用AP对位置的信息增益，然后选出M个具有最大信息增益的AP作为最优的AP组合。

同理互信息也是基于信息熵推导出的一种反映随机变量之间相关性的数学指标。一般而言，互信息多指两个随机变量之间的互信息，其算式为

MI(APa,APb)=H(APa)+

H(APb)-H(APa,APb).

(3)

式中：MI(APa,APb)表示两个不同AP的互信息；H(APa,APb)表示两个AP的联合信息熵。

互信息最小化需要同时计算多个AP的互信息，文献[14]给出一种简化的迭代计算方案。从N个AP选取M个AP子集的互信息计算过程分为以下3个步骤：

1)对于N个AP进行两两组合，按照式(3)分别计算每个组合的互信息，找出互信息最小的组合，其对应的APa,APb作为两个初始AP；

2)按照式(4)分别计算余下的N-2个AP与两个初始AP组合的互信息。

MI(APa,APb,APi)=H(APa,APb)+

H(APi)-H(APa,APb,APi).

(4)

找出使得MI最小的AP作为最优AP子集的第3个AP。

3)依次按照第2步的形式选取下一个最优的AP，直到选取出M个最优AP为止。第L个最优AP的选取算式为

MI(AP1,AP2,…,APL)=H(AP1,AP2,…,

APL-1)+H(APL)-H(AP1,AP2,…,APL).

(5)

1.2 贝叶斯位置估计策略

由于室内信号受到多径的影响，存在大量的折射、散射、衍射现象，同时室内环境中的人体会吸收WiFi信号，因此WiFi的RSS信号空间与物理位置之间并非一一映射关系。一般而言，基于RSS的WiFi室内定位采用贝叶斯位置估计算法优于假设信号空间与物理空间一一映射的WKNN(K邻近点加权)算法。目前，常用的贝叶斯后验估计算法计算后验联合概率密度时常常假设AP之间相互独立。为了进一步分析AP之间相关性对位置估计性能的影响，本文分别考虑两种不同的后验概率计算策略，并结合上述两种不同的AP选取方案进行组合优化，从而进一步提升WiFi室内定位系统的性能。

贝叶斯后验估计的基本原理为

(6)

式中：RSS表示多个AP在位置估计点的RSS观测值;p(LiRSS)表示位置Li的在给定RSS下的条件概率，即在观测到RSS向量的情况下，定位点出现在Li的概率;p(RSS|Li)表示位置Li观测到给定RSS的条件概率;p(Li)表示位置Li的概率，通常不考虑指纹点之间的差异，即指纹点等概率;p(RSS)表示RSS出现的全概率，假定AP之间相互独立，其算式为

p(RSS)=p(RSS1)p(RSS2)…p(RSSM)=

(7)

式中：p(RSSi)表示第i个AP的观测值离散概率，式(7)成立的条件为各个AP之间相互独立。为了顾及AP之间的关联性，可采用直方图形式计算联合离散变量的概率密度，其算式为

(8)

式中：Count(RSS1,RSS2,…，RSSM)表示RSS观测向量(RSS1,RSS2,…，RSSM)出现在训练集的次数，即指纹点观测到的指定RSS向量的个数；Size表示训练集的大小，即指纹点的观测历元数。式(8)计算不需要假定AP之间相互独立，而完全按照频率统计方法计算联合离散变量的概率。

将全概率算式(式(7)或者式(8))回代至贝叶斯后验估计式(6)，从而计算出后验条件概率。利用多个指纹点的贝叶斯加权位置估计算式可以快速解算出位置估计点的坐标。

(9)

式中：(x,y)表示位置估计点的二维坐标；(xi,yi)表示第i个指纹点的坐标；wi表示第i个指纹点的权重，即贝叶斯后验条件概率；K表示邻近点个数。

1.3 组合算法

针对WiFi室内定位的特定问题往往具有多种不同的改进算法，从而提升系统的性能。然而，目前鲜有关于不同问题的优化算法之间的组合性能研究。考虑章节1.1和1.2中WiFi室内定位的不同AP选取策略和贝叶斯位置估计策略，本文重点在于利用组合优化进一步改善系统性能，给出一种优化组合策略的WiFi定位新算法。考虑的4个组合分别为：

组合1，信息增益最大化策略和假定AP独立的贝叶斯估计；

组合2，信息增益最大化策略和考虑AP相关性的贝叶斯估计；

组合3，互信息最小化策略和假定AP独立的贝叶斯估计；

组合4，互信息最小化策略和考虑AP相关性的贝叶斯估计。

本文利用组合算法的位置估计精度和可靠度评估分析不同组合的WiFi室内定位系统性能。位置估计精度采用平均定位误差指标，其算式为

(10)

定义可靠度为位置估计误差小于某一限差的百分比为

(11)

式中：N意义同上；nα表示估计误差小于阈值α的位置估计点的个数；β表示可靠度，采用百分比形式表示。

2 实验分析

为了检验不同组合策略的WiFi位置估计算法的性能，本文通过实验对比分析不同组合策略定位算法的性能。实验信号接收器采用小米手机，发射器为所有可接收到信号的AP。线下阶段的数据采集位于一个动态变化的办公环境，室内面积大小约为10 m×7 m。实验采集一个2 m×2 m的小型格网数据，其中包括4个指纹点和21个位置估计点，实验方案分布见图1。

图1 实验方案分布图

图1中，‘*’号表示位置估计点的物理位置；‘●’表示指纹点的物理位置。x轴和y轴分别表示独立坐标系下的x和y方向。表1给出最优AP子集个数分别取4～12时A,B,C,D 4种不同组合的位置估计精度统计表。

从表1中可以看出组合B的位置估计精度高于组合A的精度，即考虑AP相关性的贝叶斯估计算法要优于假设AP独立性的贝叶斯估计策略，同时考虑AP相关性的贝叶斯估计策略存在退化现象，即定位精度不受最优AP个数的影响。此外，组合D的位置估计精度也优于组合C的精度，最优子集个数取4的情况除外。综上所述，考虑AP相关性的贝叶斯估计策略定位精度明显优于假设AP独立的贝叶斯估计策略，但是前者存在严重的退化现象，即找到特定的AP组合后定位精度不再受到AP个数的影响。依据精度均值可以看出，信息增益的方法略优于互信息方法，同时基于信息增益的AP选取方法略优于互信息的AP选取策略。图2分别给出最优AP子集取4～7时不同组合的可靠度统计直方图。

表1 精度统计表 m

图2 AP子集取4～7时不同组合的CDF曲线

从图2中可以看出，组合2的定位误差可靠度明显优于其它3个方法，且CDF曲线与K值无关，即组合2存在明显的退化现象。最优子集AP个数设置为4、5、6时，组合1、3、4差异不大，K=7时，组合4明显优于组合1、3，其CDF曲线接近于组合2，即可靠度性能较优。

3 结 论

本文对不同WiFi定位的组合算法进行研究，重点比较分析不同AP选取策略和位置估计策略的组合对WiFi定位系统性能的影响。实验分析中分别设置最优AP子集个数为K=4～10，通过不同的组合策略进行位置估计点的坐标估计。实验结果表明：实验环境中AP的观测信号之间存在相互干扰，难以满足独立性条件，考虑AP相关性的贝叶斯估计策略精度优于假设AP独立的贝叶斯估计算法。同时不考虑AP独立性的贝叶斯估计策略存在一定的退化现象，其定位结果受到AP子集个数的影响很小。综合可靠度统计曲线，组合4为最优组合策略，即互信息最小化策略和考虑AP相关性的贝叶斯估计为最优的WiFi位置估计算法。基于该优化组合策略的WiFi定位新算法具有很好的位置估计精度和可靠度，同时新组合算法的退化现象较组合1存在一定改善。

[1] 杨靖宇, 谢超, 柯希林, 等. 地理信息服务的思考与探索[J]. 测绘工程, 2009, 18(1): 34-37.

[2] 林雕, 宋国民, 邓晨. 基于图的语义室内导航模型构建研究[J]. 测绘工程, 2015, 24(1): 48-52.

[3] 王建宾. 基于北斗GNSS技术的智慧城管数据采集系统架构与实现[J]. 科技通报, 2016, 32(1): 179-182.

[4] 鲍建宽, 范兴旺, 高成发. 4种全球定位系统的现代化及其坐标转化[J]. 黑龙江工程学院学报(自然科学版), 2013, 27(1): 36-40.

[5] WOO S, JEONG S, MOK E, et al. Application of WiFi-based indoor positioning system for labor tracking at construction sites: A case study in Guangzhou MTR[J]. Automation in Construction, 2011, 20(1): 3-13.

[6] KUL G, ÖZYER T, TAVLI B. IEEE 802.11 WLAN Based Real Time Indoor Positioning: Literature Survey and Experimental Investigations[J]. Procedia Computer Science, 2014, 34(34): 157-164.

[8] 温丰, 柴晓杰, 朱智平, 等. 基于单目视觉的SLAM算法研究[J]. 系统科学与数学, 2010, 30(6): 827-939.

[9] 张国良, 汤文俊, 敬斌, 等. 基于机器人运动模型的EKF-SLAM算法改进[J]. 计算机测量与控制, 2012, 20(4): 1064-1066.

[10] 任博雅, 赵白鸽, 李怡蓓. 基于ZigBee网络和超声定位的智能跟随小车[J]. 计算机测量与控制, 2015, 23(5):1789-1791.

[11] 王向磊, 丁硕, 苏牡丹. 地磁匹配导航算法研究[J]. 测绘工程, 2011, 20(2): 6-14.

[12] 周建国, 张鹏, 冯欣, 等. 基于无线传感器网络的室内定位研究[J]. 测绘地理信息, 2012, 37(5):26-28.

[13] YOUSSEF M A, AGRAWALA A, SHANKAR A U. WLAN Location Determination via Clustering and Probability Distributions[C]. Pervasive Computing and Communications, IEEE, 2003:143-150.

[14] ZHIAN D, LIN M, YUBIN X. Intelligent AP Selection for Indoor Positioning in Wireless Local Area Network[C]. 2011 6th International ICST Conference on Communications and networking in China (CHINACOM), China, 2011: 257-261.

[15] ZOU H, LUO Y, LU X,et al. A mutual information based online access point selection strategy for WiFi indoor localization[C]. Automation Science and Engineering (CASE), 2015 IEEE International Conference on, IEEE, 2015:180-185.

[责任编辑：张德福]

A new combinatorial optimization algorithm for WiFi positioning

ZHANG Wei1,2, HUA Xianghong1,2, QIU Weining1,2, XUE Weixing1,2, ZHOU Dingjie3

(1.School of Geodesy & Geomatics, Wuhan University, Wuhan 430079，China; 2.Hazard Monitoring & Prevention Research Center, Wuhan 430079,China; 3.Yunnan Engineering Institute of Surveying and Mapping, Kunming 650033,China)

This paper explores the influence of AP selection strategy and Bayesian position estimation algorithm on RSS based on WiFi indoor positioning technology. Domestic and foreign scholars have done a lot of research work on the AP selection strategy and Bayesian position estimation algorithm. Based on the idea of combinatorial optimization, further in-depth study of different algorithms is useful for the performance improvement of WiFi indoor positioning system. Based on AP selection strategy with minimization of mutual information and Bayesian estimation algorithm that takes AP correlation into account, a new WiFi fingerprint location algorithm is proposed in this paper. The experiments show that: the new algorithm has good applicability and localization performance.

WiFi indoor positioning; AP selection; Bayesian position estimation; combinatorial optimization; localization performance

10.19349/j.cnki.issn1006-7949.2017.03.003

2015-11-25

国家自然科学基金资助项目(41174010；41374011)

张 伟(1989-)，男，博士研究生.

P228

A

1006-7949(2017)03-0014-05

引用著录：张伟,花向红,邱卫宁，等.WiFi指纹定位的一种新组合算法[J].测绘工程，2017，26(3)：14-18.