黎海濤，齊 雙

?

基于室內(nèi)地圖環(huán)境信息的多樓層WiFi定位技術(shù)研究

黎海濤，齊 雙

(北京工業(yè)大學(xué)電子信息與控制工程 北京朝陽(yáng)區(qū) 100124)

針對(duì)多樓層環(huán)境的室內(nèi)定位需求，提出了一種基于地圖環(huán)境先驗(yàn)信息的WiFi指紋定位方法。首先在離線階段建立地圖環(huán)境信息模型并對(duì)指紋進(jìn)行仿射傳播聚類，然后在線階段采用RSSI閾值的樓層判別算法確定樓層，并結(jié)合地圖信息模型和最大后驗(yàn)估計(jì)方法計(jì)算出終端位置。實(shí)驗(yàn)結(jié)果表明，相比于傳統(tǒng)的指紋定位方法，室內(nèi)定位技術(shù)不僅能提高定位精度，并且降低了在線階段指紋匹配計(jì)算的復(fù)雜度。

仿射傳播聚類; 指紋; 樓層判別; 室內(nèi)定位; 地圖信息

隨著移動(dòng)互聯(lián)網(wǎng)的高速發(fā)展和智能移動(dòng)終端的普及，移動(dòng)用戶對(duì)實(shí)時(shí)、準(zhǔn)確的位置信息需求與日劇增?；谖恢玫姆?wù)(LBS)在民用、商用、軍用、應(yīng)急救援中具有廣闊應(yīng)用前景而受到人們普遍關(guān)注。目前國(guó)內(nèi)外LBS應(yīng)用大多采用GPS衛(wèi)星定位，由于信號(hào)強(qiáng)度受到建筑物、墻壁等的影響而大大衰減，導(dǎo)致GPS接收機(jī)在高樓密集的城市或者室內(nèi)運(yùn)行時(shí)，定位精度降低甚至不能完成定位過(guò)程。

基于WiFi的室內(nèi)定位技術(shù)利用移動(dòng)終端從無(wú)線接入點(diǎn)(AP)接收到的信號(hào)來(lái)確定用戶位置，能提高現(xiàn)有設(shè)備的利用率，低成本地實(shí)現(xiàn)便捷高效的定位服務(wù)，成為近年來(lái)室內(nèi)定位技術(shù)研究的熱點(diǎn)。在WIFi室內(nèi)定位技術(shù)中，相比于基于信號(hào)到達(dá)時(shí)間(TOA)、信號(hào)到達(dá)角度(AOA)等方法，基于接收信號(hào)強(qiáng)度指示(RSSI)的指紋定位技術(shù)由于其對(duì)設(shè)備要求低、實(shí)現(xiàn)簡(jiǎn)單而被普遍采用。

由于WiFi信號(hào)傳播的時(shí)變特性和環(huán)境因素的影響，使得終端在線接收RSSI的測(cè)量值與離線指紋庫(kù)存在較大差異。此外，一般的WiFi指紋定位計(jì)算需要遍歷所有參考點(diǎn)指紋，其在多樓層環(huán)境中應(yīng)用時(shí)，定位系統(tǒng)中指紋數(shù)量增多，導(dǎo)致匹配計(jì)算的復(fù)雜度成倍增加。

研究表明，通過(guò)利用定位區(qū)域環(huán)境的先驗(yàn)信息可以降低信號(hào)傳播過(guò)程中由于障礙物導(dǎo)致的信號(hào)非視距(NLOS)偏差等而提高定位精度[1-3]。文獻(xiàn)[4]應(yīng)用地圖信息建立了用于室內(nèi)定位的衰減系數(shù)(AF)模型，但此模型不適用于指紋定位方法，且缺少基于這種模型的位置估計(jì)算法的結(jié)果驗(yàn)證，因此在實(shí)際應(yīng)用中其準(zhǔn)確性和有效性無(wú)法保證。在樓層判別方面，文獻(xiàn)[5]提出了聯(lián)合加速度傳感器和氣壓計(jì)計(jì)算高度從而判別樓層的方法，然而氣壓計(jì)需要定期校準(zhǔn)且其測(cè)量值受環(huán)境影響較大，因此無(wú)法獲得穩(wěn)定的樓層判別準(zhǔn)確率。

針對(duì)上述問(wèn)題，本文提出基于地圖環(huán)境先驗(yàn)信息的WiFi指紋定位方法，首先，建立地圖環(huán)境信息的統(tǒng)計(jì)模型，并采用仿射傳播聚類算法對(duì)指紋進(jìn)行離線訓(xùn)練，以減小定位階段的計(jì)算復(fù)雜度。進(jìn)一步，為了彌補(bǔ)WiFi定位在高度上的誤差導(dǎo)致樓層判別準(zhǔn)確率低，提出了基于RSSI閾值的樓層判別算法，以提高多樓層定位的準(zhǔn)確率。最后，利用基于地圖信息模型的位置估計(jì)算法定位，以減少NLOS偏差、干擾、噪聲等的影響，提高WiFi定位的精度和穩(wěn)定性。

1 基于地圖環(huán)境信息的WiFi室內(nèi)定位系統(tǒng)

1.1 WiFi指紋室內(nèi)定位

WiFi指紋定位包括離線階段和在線階段兩個(gè)步驟，首先在離線階段建立定位區(qū)域的指紋庫(kù)，使得指紋庫(kù)盡可能準(zhǔn)確地表達(dá)每個(gè)參考點(diǎn)的信號(hào)特征；然后在線階段通過(guò)測(cè)量用戶終端當(dāng)前位置的RSSI，利用合適的搜索或匹配算法確定終端位置。下面詳細(xì)介紹各個(gè)階段的操作步驟。

表1 指紋圖

現(xiàn)有的指紋匹配計(jì)算方法可分為確定性匹配算法(如K-最近鄰居算法，K-NN)和概率匹配算法(如最大后驗(yàn)估計(jì)MAP，或最小均方根誤差MMSE)[6-7]。K-NN算法作為典型的確定性匹配算法被普遍使用。其基本原理是通過(guò)計(jì)算當(dāng)前信號(hào)指紋與指紋庫(kù)中各個(gè)參考點(diǎn)的指紋的歐式距離，選出與當(dāng)前指紋距離最近的個(gè)參考點(diǎn)，取其坐標(biāo)平均值作為終端位置。具體計(jì)算步驟如下。

1)計(jì)算當(dāng)前位置指紋FP與指紋圖中所有參考點(diǎn)指紋的歐式距離。設(shè)RSSI向量表示指紋FP中來(lái)自個(gè)AP的RSSI向量，與指紋圖中參考點(diǎn)RP的RSSI向量之間的歐式距離為：

2) 對(duì)m進(jìn)行升序排序，選出前個(gè)指紋并平均其平面位置坐標(biāo)()，得到當(dāng)前位置坐標(biāo)。

(2)

1.2 室內(nèi)地圖環(huán)境建模

為了利用地圖環(huán)境的先驗(yàn)信息進(jìn)行WiFi定位，需要建立地圖環(huán)境的數(shù)學(xué)模型，包括：1) 定位區(qū)域模型；2) AP覆蓋區(qū)域模型；3) 終端與AP之間的距離模型。

1) 定位區(qū)域模型

圖1 地圖定位區(qū)域

2)AP覆蓋區(qū)域模型

3) 終端與AP的距離模型

1.3 基于地圖環(huán)境的WiFi定位

根據(jù)建立的室內(nèi)地圖環(huán)境模型，提出的多樓層WiFi室內(nèi)定位系統(tǒng)如圖2所示，具體施步驟如下。

圖2 提出的WiFi定位系統(tǒng)

1) 離線階段：完成定位區(qū)域的地圖環(huán)境信息建模、指紋圖的建立與指紋聚類。

①地圖環(huán)境建模，具體步驟見(jiàn)1.2節(jié)。

②建立指紋圖。

與一般WiFi指紋定位技術(shù)相同，包含指紋采集與指紋的平均。記錄AP的位置坐標(biāo)，將定位區(qū)域內(nèi)的坐標(biāo)與存為一組，其中坐標(biāo)表示所在樓層。并把參考點(diǎn)測(cè)量到的第個(gè)AP的RSSI的平均值記為，為參考點(diǎn)標(biāo)號(hào)。

③指紋聚類。

通過(guò)在指紋定位方法中加入指紋聚類，可以降低定位的計(jì)算復(fù)雜度，提高定位算法的實(shí)時(shí)性以及精度。文獻(xiàn)[8]采用模糊c-均值聚類(FCM)算法對(duì)指紋聚類，但此種聚類方法在指紋點(diǎn)個(gè)數(shù)較大時(shí)，會(huì)導(dǎo)致計(jì)算量大大增加。文獻(xiàn)[9]采用經(jīng)典的k-均值(k-means)算法將指紋聚類，此方法需要通過(guò)隨機(jī)方式選擇初始類首，聚類結(jié)果依賴于初始聚類中類首的選擇，容易陷入局部極值。仿射傳播聚類[10]無(wú)需隨機(jī)選擇類首，且算法收斂速度快，更適于RSSI指紋圖的預(yù)處理。

本文利用仿射傳播聚類算法對(duì)所采集的指紋聚類，聚類結(jié)果如圖3所示，聚類完成后將此189個(gè)指紋點(diǎn)劃分為17個(gè)類。其中每個(gè)顏色的圓點(diǎn)屬于一類，類首與類成員間通過(guò)直線連接。從圖中可以看出，通過(guò)指紋聚類，可將物理位置相近的點(diǎn)劃分在一個(gè)類中。在定位時(shí)，為避免指紋匹配到錯(cuò)誤的類中，需選擇少數(shù)個(gè)類作為位置計(jì)算的參考類。定位算法利用參考類的類首及其類成員的位置信息計(jì)算終端位置。通過(guò)指紋聚類將定位計(jì)算的指紋搜索區(qū)域縮小至少數(shù)類中，既降低了指紋匹配計(jì)算的復(fù)雜度，也提高了定位精度。

圖3 指紋聚類結(jié)果

在計(jì)算復(fù)雜度方面，基于K-NN的全局匹配算法的計(jì)算復(fù)雜度為，其中為參考點(diǎn)個(gè)數(shù)，為每個(gè)參考點(diǎn)的信號(hào)強(qiáng)度維度。而基于仿射傳播聚類的匹配算法的計(jì)算復(fù)雜度為，其中為類首個(gè)數(shù)，表示類成員個(gè)數(shù)。由于，故基于仿射傳播聚類的匹配算法大大減少了匹配計(jì)算的復(fù)雜度。

2) 在線階段：包含樓層判別和基于地圖環(huán)境模型的位置估計(jì)兩部分。

樓層判別中，利用RSSI在樓層間的衰落特征，并通過(guò)建立RSSI閾值與AP數(shù)量的關(guān)系，確定當(dāng)前終端所在樓層，算法具體步驟見(jiàn)第2節(jié)。

采用MAP算法估計(jì)終端位置，結(jié)合地圖建模所得的終端定位區(qū)域模型、AP覆蓋區(qū)域模型以及終端與AP連接的距離模型，得到終端位置估計(jì)的概率密度函數(shù)[11]為：

2 樓層判別

研究表明，WiFi無(wú)線信號(hào)穿過(guò)建筑墻體時(shí)，由于通常樓層間墻壁常使用金屬加強(qiáng)的混凝土，信號(hào)強(qiáng)度可能出現(xiàn)較大的衰減(15～20 dBm)[12]。此現(xiàn)象表明：1) 當(dāng)物理距離相等時(shí)，來(lái)自同樓層的AP的RSSI強(qiáng)于其他樓層AP的RSSI；2) 根據(jù)三角定理，當(dāng)不同AP的平面投影即坐標(biāo)相同時(shí)，終端與同樓層的AP距離更短。綜上兩個(gè)條件，使得平面位置即坐標(biāo)相同時(shí)，來(lái)自其他樓層的AP的RSSI明顯的低于來(lái)自于本樓層AP的RSSI。利用樓層間RSSI的差異，提出的樓層判別算法實(shí)現(xiàn)步驟如下。

2) 設(shè)置RSSI閾值0，統(tǒng)計(jì)各個(gè)樓層的閾值內(nèi)AP數(shù)量，并返回最大值對(duì)應(yīng)的樓層F：

3 位置估計(jì)

3.1 模型參數(shù)估計(jì)

室內(nèi)環(huán)境中，終端的接收信號(hào)功率可表示為[13]：

(9)

圖4 模型參數(shù)估計(jì)方法

偏差均值模型為：

距離誤差標(biāo)準(zhǔn)差模型為：

把式(10)～式(12)中得到的估計(jì)參數(shù)，即NLOS偏差均值及方差和距離誤差方差代入式(6)，得到基于地圖環(huán)境信息的位置估計(jì)概率密度函數(shù)為：

3.2 MAP位置估計(jì)

采用MAP位置估計(jì)算法得到終端位置為：

1) 利用第1節(jié)中指紋匹配算法K-NN得到當(dāng)前樓層中與當(dāng)前指紋最近的個(gè)類首及其所在位置區(qū)域；

2) 利用式(3)和貝葉斯準(zhǔn)則，得到基于地圖環(huán)境信息模型的終端位置估計(jì)為：

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證所提算法的定位效果，本文在Eclipse平臺(tái)上利用JAVA語(yǔ)言開(kāi)發(fā)了基于Android 4.0操作系統(tǒng)的定位客戶端，以及基于Windows 7系統(tǒng)的定位服務(wù)器端。在每個(gè)參考點(diǎn)，客戶端掃描AP信號(hào)并記錄其RSSI與MAC地址，并與參考點(diǎn)位置坐標(biāo)一起上傳到服務(wù)器。定位服務(wù)器建立指紋圖后對(duì)所有指紋進(jìn)行聚類，并完成位置估計(jì)。

本次實(shí)驗(yàn)選取三層辦公樓為實(shí)驗(yàn)場(chǎng)所，其中12個(gè)AP分布在3個(gè)樓層內(nèi)，各個(gè)參考點(diǎn)分布在3個(gè)樓層的走廊內(nèi)，兩個(gè)相鄰參考點(diǎn)之間的距離約為2 m，利用信號(hào)采集端對(duì)每個(gè)點(diǎn)進(jìn)行30次間隔為1 s的采樣。并在聚類算法中，將偏向設(shè)為相似度中值。

4.1 樓層判別準(zhǔn)確率

為了研究基于RSSI閾值的樓層判別算法的效果，本文測(cè)試了不同AP分布情況下閾值0改變時(shí)的樓層判別準(zhǔn)確率，如圖5所示。

圖5 不同AP分布情況下樓層判別正確率曲線

從圖5中可以看到，當(dāng)AP在樓層間分布均勻時(shí)，且閾值0取在-82dBm附近時(shí)，基于RSSI閾值的樓層判別方法的準(zhǔn)確率能夠達(dá)到99%；當(dāng)AP在樓層間分布不均勻，且閾值0取在-80dBm附近時(shí)，算法依然能夠達(dá)到97.2%的準(zhǔn)確率。對(duì)于全局匹配算法，當(dāng)AP在樓層間分布均勻時(shí)準(zhǔn)確率為78.2%，而當(dāng)AP在樓層間分布不均勻時(shí)準(zhǔn)確率為67.8%。

由此可見(jiàn)，本文提出的樓層判別算法由于考慮了RSSI在樓層中的衰減特性，相比較于傳統(tǒng)全局匹配算法，極大提高了樓層判斷的準(zhǔn)確率。需要說(shuō)明的是，樓層間高度不同時(shí)AP與用戶的距離會(huì)發(fā)生變化，所以對(duì)定位精度也會(huì)有影響。

4.2 定位精度

為了分析定位計(jì)算時(shí)參考類的個(gè)數(shù)對(duì)定位精度的影響，圖6給出了參考類個(gè)數(shù)從1至17時(shí)算法的定位精度變化。從圖中可以看出，參考類類個(gè)數(shù)取在4附近時(shí)定位精度較高，當(dāng)過(guò)大時(shí)定位精度降低，并且其均方根誤差與K-NN算法的均方根誤差接近。從圖中還可以看出，當(dāng)參考類個(gè)數(shù)為1時(shí)，定位精度反而更低，這是由于當(dāng)兩個(gè)類相鄰時(shí)邊界位置的指紋可能被聚到錯(cuò)誤的類中。因此，選擇少數(shù)幾個(gè)類作為WiFi指紋法位置計(jì)算的參考類，會(huì)提高定位精度。

圖6 不同參考類數(shù)目對(duì)定位精度對(duì)比

為了分析本文基于地圖環(huán)境信息模型的定位算法準(zhǔn)確性，圖7所示為不同算法定位誤差的累計(jì)分布函數(shù)(CDF)曲線。從圖7中可以看出，與傳統(tǒng)的K-NN算法相比，基于仿射傳播聚類的定位算法降低了整體的定位誤差以及最大誤差，并且在引入地圖環(huán)境信息模型后，定位誤差得到進(jìn)一步降低。

圖7 不同方法誤差累計(jì)分布比較

為了分析所提基于地圖環(huán)境信息模型的定位算法的定位精度，圖8示出了不同定位算法的均方根誤差(RMSE)?？梢钥吹剑疚乃惴ǖ腞MSE值低于其他K-NN等未利用地圖環(huán)境信息方法的RMSE值。

圖8 不同方法均方根誤差RMSE對(duì)比

5 結(jié)束語(yǔ)

本文首先基于定位區(qū)域環(huán)境建立了地圖信息模型，并利用仿射傳播聚類算法對(duì)指紋進(jìn)行離線訓(xùn)練，減少了指紋的時(shí)變特性影響和定位階段匹配計(jì)算的復(fù)雜度。進(jìn)一步，基于信號(hào)在樓層間的衰減特性，提出基于RSSI閾值的樓層判別算法。最后，提出基于地圖信息模型的位置估計(jì)算法，以降低非視距偏差對(duì)定位效果的影響。實(shí)驗(yàn)結(jié)果表明，所提的多樓層WiFi定位方法能夠有效提高定位精度和樓層判別的準(zhǔn)確率，并減少了匹配算法計(jì)算復(fù)雜度。

[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] 周瑞. 應(yīng)用室內(nèi)結(jié)構(gòu)布局提高Wi-Fi定位精度和穩(wěn)定性[J]. 電子科技大學(xué)學(xué)報(bào), 2013, 42(2): 295-299.

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.

[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.

[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.

[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.

編 輯 稅 紅

Indoor Map Information Based WiFi Positioning Technology for Multi-Floor Buildings

LI Hai-tao and QI Shuang

(College of Electronic Information and Control Engineering, Beijing University of Technology Chaoyang Beijing 100124)

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.

affinity propagation clustering; fingerprinting; floor-identification; indoor position; map information

TN92

A

10.3969/j.issn.1001-0548.2017.01.006

2014-11-26；

2016-07-07

電子系統(tǒng)綜合技術(shù)重點(diǎn)實(shí)驗(yàn)室和航空科學(xué)基金聯(lián)合資助項(xiàng)目(2013ZC15003)

黎海濤(1972-)，男，博士，副教授，主要從事通信、信號(hào)處理方面的研究.