WiFi指紋定位的一種新組合算法

張 偉,花向紅 ,邱衛(wèi)寧,薛衛(wèi)星,周定杰

(1.武漢大學(xué) 測繪學(xué)院,湖北 武漢 430079；2.武漢大學(xué) 災(zāi)害監(jiān)測與防治研究中心，湖北 武漢 430079；3.云南省測繪工程院,云南 昆明 650033)

?

WiFi指紋定位的一種新組合算法

張 偉1,2,花向紅1,2,邱衛(wèi)寧1,2,薛衛(wèi)星1,2,周定杰3

(1.武漢大學(xué) 測繪學(xué)院,湖北 武漢 430079；2.武漢大學(xué) 災(zāi)害監(jiān)測與防治研究中心，湖北 武漢 430079；3.云南省測繪工程院,云南 昆明 650033)

探討AP選取策略和貝葉斯位置估計算法對基于RSS的WiFi室內(nèi)定位技術(shù)位置估計精度的影響。國內(nèi)外學(xué)者分別對AP選取算法和貝葉斯位置估計算法進(jìn)行了大量的研究。為了進(jìn)一步深入研究不同算法的優(yōu)劣性，利用組合優(yōu)化的思想對不同算法進(jìn)行組合，通過找出最優(yōu)算法組合從而提升WiFi室內(nèi)定位系統(tǒng)的性能。基于互信息最小化的AP選取策略和考慮AP相關(guān)性的貝葉斯位置估計算法，提出一種新的WiFi指紋定位組合算法。實驗分析表明：新算法具有良好的實用性和定位性能。

WiFi室內(nèi)定位；AP選取；貝葉斯位置估計；組合優(yōu)化；定位性能

基于位置服務(wù)[1]的快速發(fā)展推動著室內(nèi)定位和導(dǎo)航技術(shù)[2]的深入研究。盡管GNSS[3-4]實現(xiàn)了室外高精度定位導(dǎo)航，但是由于室內(nèi)信號的遮擋，GNSS在室內(nèi)定位的應(yīng)用依舊存在著較大的局限[5-6]。目前，不同的室內(nèi)應(yīng)用場景通常需要考慮特定的室內(nèi)定位技術(shù)實施方案。已有的室內(nèi)定位技術(shù)，包括基于INS的行人航位推算[7]、基于攝像頭或者掃描儀的SLAM(Simultaneous Localization And Mapping)技術(shù)[8-9]、基于射頻或者聲波的交會定位技術(shù)[10]、基于地磁匹配的定位技術(shù)[11]等。然而，上述技術(shù)都需要考慮定位系統(tǒng)的性能和成本。考慮到基于RSS(Received Signal Strength)的WiFi室內(nèi)定位技術(shù)的低成本和簡單易行的特性，國內(nèi)外學(xué)者針對WiFi室內(nèi)定位技術(shù)的特定問題進(jìn)行大量的探討[12]。文獻(xiàn)[13]提出基于貝葉斯后驗估計原理的WiFi室內(nèi)定位方案，然而該方法采用最大均值的AP(Access Point)選取策略，其AP選取策略沒有考慮AP之間的相關(guān)性。文獻(xiàn)[14]考慮AP對指紋點的信息增益提出基于信息增益最大化的AP選取策略，然而其定位算法采用了經(jīng)典的KNN算法。文獻(xiàn)[15]提出一種互信息最小化的線上AP選取策略，該算法在定位階段需要進(jìn)行大量的運算以求得最優(yōu)的AP組合，因此實用性較差。考慮到AP選取算法和位置估計策略對WiFi定位系統(tǒng)性能的影響，本文對4種不同的組合策略進(jìn)行比較分析，并給出定位性能最佳的最優(yōu)化組合。

1 WiFi指紋定位的組合算法

近年來，國內(nèi)外學(xué)者對AP選取算法進(jìn)行大量的研究，其中AP選取的兩個常用方法是信息增益最大化策略和互信息最小化策略。此外，位置估計算法中貝葉斯估計的實現(xiàn)策略直接影響WiFi系統(tǒng)的位置估計性能。目前大多數(shù)貝葉斯估計實現(xiàn)算法假設(shè)可用的AP相互獨立，這一條件在現(xiàn)實中是難以滿足的。然而基于頻率統(tǒng)計算法的多個離散變量的聯(lián)合概率密度的計算策略能夠考慮AP之間的相關(guān)性，基于該策略的貝葉斯估計更具有實用性。

1.1 AP選取策略

室內(nèi)環(huán)境復(fù)雜多變的特性和AP相互之間的影響嚴(yán)重影響基于RSS的WiFi室內(nèi)定位系統(tǒng)的性能。選取最優(yōu)AP組合不但能夠提升WiFi室內(nèi)定位系統(tǒng)的性能，同時還能避免AP數(shù)量冗余導(dǎo)致的計算負(fù)擔(dān)。假定一個WiFi定位系統(tǒng)可用的AP個數(shù)為N，則選取其中M個AP的優(yōu)化子集可以將信號空間的維度從N維減少到M維，從而減少計算量。信息增益最大化的AP選取策略和互信息最小化的AP選取策略是目前常用的兩種AP選取方法。前者考慮AP對于指紋點區(qū)分度的貢獻(xiàn)大小，位置信息增益越大，指紋點的區(qū)分度越大。后者考慮AP之間的相關(guān)性，互信息越小，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為底的對數(shù)。

基于信息增益最大化的AP選取策略分別計算每個可用AP對位置的信息增益，然后選出M個具有最大信息增益的AP作為最優(yōu)的AP組合。

同理互信息也是基于信息熵推導(dǎo)出的一種反映隨機變量之間相關(guān)性的數(shù)學(xué)指標(biāo)。一般而言，互信息多指兩個隨機變量之間的互信息，其算式為

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

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

(3)

式中：MI(APa,APb)表示兩個不同AP的互信息；H(APa,APb)表示兩個AP的聯(lián)合信息熵。

互信息最小化需要同時計算多個AP的互信息，文獻(xiàn)[14]給出一種簡化的迭代計算方案。從N個AP選取M個AP子集的互信息計算過程分為以下3個步驟：

1)對于N個AP進(jìn)行兩兩組合，按照式(3)分別計算每個組合的互信息，找出互信息最小的組合，其對應(yīng)的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作為最優(yōu)AP子集的第3個AP。

3)依次按照第2步的形式選取下一個最優(yōu)的AP，直到選取出M個最優(yōu)AP為止。第L個最優(yōu)AP的選取算式為

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

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

(5)

1.2 貝葉斯位置估計策略

由于室內(nèi)信號受到多徑的影響，存在大量的折射、散射、衍射現(xiàn)象，同時室內(nèi)環(huán)境中的人體會吸收WiFi信號，因此WiFi的RSS信號空間與物理位置之間并非一一映射關(guān)系。一般而言，基于RSS的WiFi室內(nèi)定位采用貝葉斯位置估計算法優(yōu)于假設(shè)信號空間與物理空間一一映射的WKNN(K鄰近點加權(quán))算法。目前，常用的貝葉斯后驗估計算法計算后驗聯(lián)合概率密度時常常假設(shè)AP之間相互獨立。為了進(jìn)一步分析AP之間相關(guān)性對位置估計性能的影響，本文分別考慮兩種不同的后驗概率計算策略，并結(jié)合上述兩種不同的AP選取方案進(jìn)行組合優(yōu)化，從而進(jìn)一步提升WiFi室內(nèi)定位系統(tǒng)的性能。

貝葉斯后驗估計的基本原理為

(6)

式中：RSS表示多個AP在位置估計點的RSS觀測值;p(LiRSS)表示位置Li的在給定RSS下的條件概率，即在觀測到RSS向量的情況下，定位點出現(xiàn)在Li的概率;p(RSS|Li)表示位置Li觀測到給定RSS的條件概率;p(Li)表示位置Li的概率，通常不考慮指紋點之間的差異，即指紋點等概率;p(RSS)表示RSS出現(xiàn)的全概率，假定AP之間相互獨立，其算式為

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

(7)

式中：p(RSSi)表示第i個AP的觀測值離散概率，式(7)成立的條件為各個AP之間相互獨立。為了顧及AP之間的關(guān)聯(lián)性，可采用直方圖形式計算聯(lián)合離散變量的概率密度，其算式為

(8)

式中：Count(RSS1,RSS2,…，RSSM)表示RSS觀測向量(RSS1,RSS2,…，RSSM)出現(xiàn)在訓(xùn)練集的次數(shù)，即指紋點觀測到的指定RSS向量的個數(shù)；Size表示訓(xùn)練集的大小，即指紋點的觀測歷元數(shù)。式(8)計算不需要假定AP之間相互獨立，而完全按照頻率統(tǒng)計方法計算聯(lián)合離散變量的概率。

將全概率算式(式(7)或者式(8))回代至貝葉斯后驗估計式(6)，從而計算出后驗條件概率。利用多個指紋點的貝葉斯加權(quán)位置估計算式可以快速解算出位置估計點的坐標(biāo)。

(9)

式中：(x,y)表示位置估計點的二維坐標(biāo)；(xi,yi)表示第i個指紋點的坐標(biāo)；wi表示第i個指紋點的權(quán)重，即貝葉斯后驗條件概率；K表示鄰近點個數(shù)。

1.3 組合算法

針對WiFi室內(nèi)定位的特定問題往往具有多種不同的改進(jìn)算法，從而提升系統(tǒng)的性能。然而，目前鮮有關(guān)于不同問題的優(yōu)化算法之間的組合性能研究。考慮章節(jié)1.1和1.2中WiFi室內(nèi)定位的不同AP選取策略和貝葉斯位置估計策略，本文重點在于利用組合優(yōu)化進(jìn)一步改善系統(tǒng)性能，給出一種優(yōu)化組合策略的WiFi定位新算法。考慮的4個組合分別為：

組合1，信息增益最大化策略和假定AP獨立的貝葉斯估計；

組合2，信息增益最大化策略和考慮AP相關(guān)性的貝葉斯估計；

組合3，互信息最小化策略和假定AP獨立的貝葉斯估計；

組合4，互信息最小化策略和考慮AP相關(guān)性的貝葉斯估計。

本文利用組合算法的位置估計精度和可靠度評估分析不同組合的WiFi室內(nèi)定位系統(tǒng)性能。位置估計精度采用平均定位誤差指標(biāo)，其算式為

(10)

定義可靠度為位置估計誤差小于某一限差的百分比為

(11)

式中：N意義同上；nα表示估計誤差小于閾值α的位置估計點的個數(shù)；β表示可靠度，采用百分比形式表示。

2 實驗分析

為了檢驗不同組合策略的WiFi位置估計算法的性能，本文通過實驗對比分析不同組合策略定位算法的性能。實驗信號接收器采用小米手機，發(fā)射器為所有可接收到信號的AP。線下階段的數(shù)據(jù)采集位于一個動態(tài)變化的辦公環(huán)境，室內(nèi)面積大小約為10 m×7 m。實驗采集一個2 m×2 m的小型格網(wǎng)數(shù)據(jù)，其中包括4個指紋點和21個位置估計點，實驗方案分布見圖1。

圖1 實驗方案分布圖

圖1中，‘*’號表示位置估計點的物理位置；‘●’表示指紋點的物理位置。x軸和y軸分別表示獨立坐標(biāo)系下的x和y方向。表1給出最優(yōu)AP子集個數(shù)分別取4～12時A,B,C,D 4種不同組合的位置估計精度統(tǒng)計表。

從表1中可以看出組合B的位置估計精度高于組合A的精度，即考慮AP相關(guān)性的貝葉斯估計算法要優(yōu)于假設(shè)AP獨立性的貝葉斯估計策略，同時考慮AP相關(guān)性的貝葉斯估計策略存在退化現(xiàn)象，即定位精度不受最優(yōu)AP個數(shù)的影響。此外，組合D的位置估計精度也優(yōu)于組合C的精度，最優(yōu)子集個數(shù)取4的情況除外。綜上所述，考慮AP相關(guān)性的貝葉斯估計策略定位精度明顯優(yōu)于假設(shè)AP獨立的貝葉斯估計策略，但是前者存在嚴(yán)重的退化現(xiàn)象，即找到特定的AP組合后定位精度不再受到AP個數(shù)的影響。依據(jù)精度均值可以看出，信息增益的方法略優(yōu)于互信息方法，同時基于信息增益的AP選取方法略優(yōu)于互信息的AP選取策略。圖2分別給出最優(yōu)AP子集取4～7時不同組合的可靠度統(tǒng)計直方圖。

表1 精度統(tǒng)計表 m

圖2 AP子集取4～7時不同組合的CDF曲線

從圖2中可以看出，組合2的定位誤差可靠度明顯優(yōu)于其它3個方法，且CDF曲線與K值無關(guān)，即組合2存在明顯的退化現(xiàn)象。最優(yōu)子集AP個數(shù)設(shè)置為4、5、6時，組合1、3、4差異不大，K=7時，組合4明顯優(yōu)于組合1、3，其CDF曲線接近于組合2，即可靠度性能較優(yōu)。

3 結(jié) 論

本文對不同WiFi定位的組合算法進(jìn)行研究，重點比較分析不同AP選取策略和位置估計策略的組合對WiFi定位系統(tǒng)性能的影響。實驗分析中分別設(shè)置最優(yōu)AP子集個數(shù)為K=4～10，通過不同的組合策略進(jìn)行位置估計點的坐標(biāo)估計。實驗結(jié)果表明：實驗環(huán)境中AP的觀測信號之間存在相互干擾，難以滿足獨立性條件，考慮AP相關(guān)性的貝葉斯估計策略精度優(yōu)于假設(shè)AP獨立的貝葉斯估計算法。同時不考慮AP獨立性的貝葉斯估計策略存在一定的退化現(xiàn)象，其定位結(jié)果受到AP子集個數(shù)的影響很小。綜合可靠度統(tǒng)計曲線，組合4為最優(yōu)組合策略，即互信息最小化策略和考慮AP相關(guān)性的貝葉斯估計為最優(yōu)的WiFi位置估計算法。基于該優(yōu)化組合策略的WiFi定位新算法具有很好的位置估計精度和可靠度，同時新組合算法的退化現(xiàn)象較組合1存在一定改善。

[1] 楊靖宇, 謝超, 柯希林, 等. 地理信息服務(wù)的思考與探索[J]. 測繪工程, 2009, 18(1): 34-37.

[2] 林雕, 宋國民, 鄧晨. 基于圖的語義室內(nèi)導(dǎo)航模型構(gòu)建研究[J]. 測繪工程, 2015, 24(1): 48-52.

[3] 王建賓. 基于北斗GNSS技術(shù)的智慧城管數(shù)據(jù)采集系統(tǒng)架構(gòu)與實現(xiàn)[J]. 科技通報, 2016, 32(1): 179-182.

[4] 鮑建寬, 范興旺, 高成發(fā). 4種全球定位系統(tǒng)的現(xiàn)代化及其坐標(biāo)轉(zhuǎn)化[J]. 黑龍江工程學(xué)院學(xué)報(自然科學(xué)版), 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]. 系統(tǒng)科學(xué)與數(shù)學(xué), 2010, 30(6): 827-939.

[9] 張國良, 湯文俊, 敬斌, 等. 基于機器人運動模型的EKF-SLAM算法改進(jìn)[J]. 計算機測量與控制, 2012, 20(4): 1064-1066.

[10] 任博雅, 趙白鴿, 李怡蓓. 基于ZigBee網(wǎng)絡(luò)和超聲定位的智能跟隨小車[J]. 計算機測量與控制, 2015, 23(5):1789-1791.

[11] 王向磊, 丁碩, 蘇牡丹. 地磁匹配導(dǎo)航算法研究[J]. 測繪工程, 2011, 20(2): 6-14.

[12] 周建國, 張鵬, 馮欣, 等. 基于無線傳感器網(wǎng)絡(luò)的室內(nèi)定位研究[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.

[責(zé)任編輯：張德福]

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

國家自然科學(xué)基金資助項目(41174010；41374011)

張 偉(1989-)，男，博士研究生.

P228

A

1006-7949(2017)03-0014-05

引用著錄：張偉,花向紅,邱衛(wèi)寧，等.WiFi指紋定位的一種新組合算法[J].測繪工程，2017，26(3)：14-18.