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

黎海濤，齊 雙

?

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

黎海濤，齊 雙

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

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

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

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

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

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

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

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

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

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

WiFi指紋定位包括離線階段和在線階段兩個步驟，首先在離線階段建立定位區(qū)域的指紋庫，使得指紋庫盡可能準確地表達每個參考點的信號特征；然后在線階段通過測量用戶終端當前位置的RSSI，利用合適的搜索或匹配算法確定終端位置。下面詳細介紹各個階段的操作步驟。

表1 指紋圖

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

1)計算當前位置指紋FP與指紋圖中所有參考點指紋的歐式距離。設(shè)RSSI向量表示指紋FP中來自個AP的RSSI向量，與指紋圖中參考點RP的RSSI向量之間的歐式距離為：

2) 對m進行升序排序，選出前個指紋并平均其平面位置坐標()，得到當前位置坐標。

(2)

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

為了利用地圖環(huá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)境建模，具體步驟見1.2節(jié)。

②建立指紋圖。

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

③指紋聚類。

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

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

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

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

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

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

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

2 樓層判別

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

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

3 位置估計

3.1 模型參數(shù)估計

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

(9)

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

偏差均值模型為：

距離誤差標準差模型為：

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

3.2 MAP位置估計

采用MAP位置估計算法得到終端位置為：

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

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

4 實驗結(jié)果與分析

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

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

4.1 樓層判別準確率

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

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

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

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

4.2 定位精度

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

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

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

圖7 不同方法誤差累計分布比較

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

圖8 不同方法均方根誤差RMSE對比

5 結(jié)束語

本文首先基于定位區(qū)域環(huán)境建立了地圖信息模型，并利用仿射傳播聚類算法對指紋進行離線訓(xùn)練，減少了指紋的時變特性影響和定位階段匹配計算的復(fù)雜度。進一步，基于信號在樓層間的衰減特性，提出基于RSSI閾值的樓層判別算法。最后，提出基于地圖信息模型的位置估計算法，以降低非視距偏差對定位效果的影響。實驗結(jié)果表明，所提的多樓層WiFi定位方法能夠有效提高定位精度和樓層判別的準確率，并減少了匹配算法計算復(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é)報, 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ù)重點實驗室和航空科學(xué)基金聯(lián)合資助項目(2013ZC15003)

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