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

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

?

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

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

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

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

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

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

1 WiFi指紋定位的組合算法

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

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

AP的位置信息增益計(jì)算算式為

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

(1)

式中：L表示位置；InfoGain(APi)表示第i個(gè)AP對(duì)位置的信息增益；H(L)表示位置的信息熵；H(LAPi)表示位置L在給定AP下的條件信息熵。離散隨機(jī)變量的信息熵算式為

(2)

式中：X表示具有N個(gè)可取離散值的隨機(jī)變量；p(xi)表示X取xi的離散概率密度；log10表示取以10為底的對(duì)數(shù)。

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

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

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

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

(3)

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

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

1)對(duì)于N個(gè)AP進(jìn)行兩兩組合，按照式(3)分別計(jì)算每個(gè)組合的互信息，找出互信息最小的組合，其對(duì)應(yīng)的APa,APb作為兩個(gè)初始AP；

2)按照式(4)分別計(jì)算余下的N-2個(gè)AP與兩個(gè)初始AP組合的互信息。

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

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

(4)

找出使得MI最小的AP作為最優(yōu)AP子集的第3個(gè)AP。

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

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

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

(5)

1.2 貝葉斯位置估計(jì)策略

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

貝葉斯后驗(yàn)估計(jì)的基本原理為

(6)

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

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

(7)

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

(8)

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

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

(9)

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

1.3 組合算法

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

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

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

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

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

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

(10)

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

(11)

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

2 實(shí)驗(yàn)分析

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

圖1 實(shí)驗(yàn)方案分布圖

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

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

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

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

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

3 結(jié) 論

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

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

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

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

[4] 鮑建寬, 范興旺, 高成發(fā). 4種全球定位系統(tǒng)的現(xiàn)代化及其坐標(biāo)轉(zhuǎn)化[J]. 黑龍江工程學(xué)院學(xué)報(bào)(自然科學(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] 溫豐, 柴曉杰, 朱智平, 等. 基于單目視覺(jué)的SLAM算法研究[J]. 系統(tǒng)科學(xué)與數(shù)學(xué), 2010, 30(6): 827-939.

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

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

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

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

國(guó)家自然科學(xué)基金資助項(xiàng)目(41174010；41374011)

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

P228

A

1006-7949(2017)03-0014-05

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