田增山，舒月月，劉儀瑤，李玲霞

(重慶郵電大學(xué) 重慶市移動通信技術(shù)重點實驗室，重慶 400065)

改進的蜂窩網(wǎng)室內(nèi)定位匹配算法

田增山，舒月月，劉儀瑤，李玲霞

(重慶郵電大學(xué) 重慶市移動通信技術(shù)重點實驗室，重慶 400065)

針對無線信道的動態(tài)衰落特性，基于蜂窩網(wǎng)的室內(nèi)定位存在較大誤差，提出一種改進的蜂窩網(wǎng)室內(nèi)定位匹配算法——基于主成分分析法(principal component analysis，PCA)的子空間匹配算法，不僅保證系統(tǒng)實時性，而且有效地剔除大誤差點，提高定位精度。該算法利用無線蜂窩信號非視距傳播造成的位置特性構(gòu)建離線指紋數(shù)據(jù)庫，根據(jù)在線接收信號從離線指紋庫中提取子指紋庫，利用PCA算法對在線實測數(shù)據(jù)及子指紋庫進行有效地降維，構(gòu)建子空間，并結(jié)合加權(quán)K近鄰匹配算法(weighted K nearest neighborhood，WKNN)估計出多個位置坐標，利用3σ準則對這些位置做篩選，輸出最終定位結(jié)果。實驗結(jié)果表明，基于PCA的子空間匹配算法在保證定位實時性的前提下，能有效剔除大誤差點，提高整體定位性能。

蜂窩網(wǎng)；子指紋庫；子空間匹配；PCA；3sigma準則

0 引 言

近年來，隨著新型移動設(shè)備如手機、平板電腦、可穿戴設(shè)備的不斷更新?lián)Q代，基于位置感知的應(yīng)用激增，位置服務(wù)的相關(guān)技術(shù)和產(chǎn)業(yè)逐漸轉(zhuǎn)向室內(nèi)發(fā)展。隨著人們越來越關(guān)注自身及設(shè)備的精確位置信息，以及興趣點的定位和導(dǎo)航[1]，室內(nèi)定位逐漸成為定位技術(shù)的一個重要研究方向。

目前，被廣泛關(guān)注的室內(nèi)定位技術(shù)主要有基于藍牙，RFID(radio frequency identification)，超聲波，WLAN(wireless local area networks)，MEMS(micro-electro-mechanical system)，超寬帶定位及蜂窩網(wǎng)指紋定位技術(shù)等[2-7]。與基于其他定位技術(shù)相比，蜂窩網(wǎng)指紋定位技術(shù)具有結(jié)構(gòu)簡單、能充分利用現(xiàn)有網(wǎng)絡(luò)設(shè)施、不需要增加額外的硬件設(shè)備、不存在時間累積誤差等優(yōu)點。現(xiàn)有蜂窩網(wǎng)室內(nèi)指紋定位技術(shù)通過把在線實測數(shù)據(jù)與離線指紋數(shù)據(jù)庫(室內(nèi)人為設(shè)置的網(wǎng)格點坐標聯(lián)合接收信號強度組成指紋數(shù)據(jù)庫)進行匹配，并把匹配算法的結(jié)果作為定位輸出，在實際定位過程中，由于受到無線信道傳播環(huán)境的影響，匹配算法估計出來的目標定位結(jié)果可能存在較大誤差[8]。文獻[9]中提出一種用于被動定位的子空間匹配算法，本文將子空間提取的思想用于蜂窩網(wǎng)主動定位中，對在線實測數(shù)據(jù)和離線指紋數(shù)據(jù)庫采用子空間匹配算法，充分利用移動終端接收到的小區(qū)信息，有效剔除大誤差點，提高定位精度。由于子空間匹配算法定位耗時過長，本文提出一種基于主成份分析法(principal component analysis,PCA)的子空間匹配算法，首先根據(jù)在線接收信號提取子指紋庫，通過對子指紋庫及在線實測數(shù)據(jù)進行降維處理后，構(gòu)建子空間，分別進行加權(quán)K最近鄰(weighted K nearest neighborhood，WKNN)匹配運算，對估計出的多個位置坐標進行3σ準則運算后輸出最終估計位置坐標，從而有效剔除大誤差點、提高整體精度、降低時間開銷。

1 室內(nèi)指紋定位技術(shù)

蜂窩網(wǎng)室內(nèi)指紋定位技術(shù)一般分為2個階段：離線階段和在線階段。離線階段，在室內(nèi)定位區(qū)域內(nèi)各指紋點(即設(shè)置的網(wǎng)格點)處采集多個基站小區(qū)在該點處的接收信號強度(received signal strength indication，RSSI)，并與該指紋點處的位置坐標一起組合成指紋記錄，建立位置指紋數(shù)據(jù)庫，以下簡稱指紋庫；在線階段，移動終端向中心定位服務(wù)器發(fā)送從不同位置接收的小區(qū)RSSI值，服務(wù)器端通過與指紋庫匹配計算出移動終端的位置信息。室內(nèi)指紋定位技術(shù)基本原理如圖1所示。

圖1 室內(nèi)指紋定位技術(shù)基本原理Fig.1 Fingerprint indoor positioning technology fundamentals

2 子指紋庫提取及匹配定位

在線定位階段中，常用的匹配算法主要有最近鄰(nearest neighbor，NN)算法、K最近鄰(K nearest neighbor，KNN)算法以及加權(quán)K最近鄰(weighted K nearest neighborhood，WKNN)算法[10]。實測中由于某些小區(qū)信號太弱，終端無法接收，或因丟包造成終端無法解析出小區(qū)信息，使得這些小區(qū)的RSSI無法獲取，從而導(dǎo)致實測數(shù)據(jù)與指紋數(shù)據(jù)庫維度不匹配，因此，無法直接運用WKNN等算法進行定位。

假設(shè)實測RSSI與離線數(shù)據(jù)庫的對應(yīng)關(guān)系如表1所示。其中，RSSInm表示在離線指紋點n處接收到來自第m個小區(qū)的信號強度；Sm表示在實測點接收到來自第m個小區(qū)的信號強度；空缺處表示未接收到該小區(qū)的RSSI。

表1 實測RSSI與離線數(shù)據(jù)庫的對應(yīng)關(guān)系Tab.1 Corresponding relation of the measured RSSI and offline database

為使在線接收數(shù)據(jù)與指紋庫維度一致，需要根據(jù)移動終端在線階段所監(jiān)測到的小區(qū)信息T(見(1)式)在離線指紋數(shù)據(jù)庫中提取出相應(yīng)小區(qū)的RSSI信息構(gòu)成子指紋庫U(見(2)式)。

(1)

(1)式中，Spj(j=1，…，m)表示移動終端實時采集的第pj個小區(qū)的接收信號強度。

(2)

成功提取子指紋庫后，運用WKNN匹配算法依次計算移動終端實時采集的RSSI向量[sp1,sp2,…,spm]與子指紋庫中第i個子指紋點處RSSI向量[RSSIi,p1,RSSIi,p2,…,RSSIi,pm]之間的歐氏距離

i=1,…,n

(3)

然后，挑選出K個Li值最小的指紋點，并求出這K個指紋點所對應(yīng)的權(quán)重

(4)

(4)式中：ε是為防止Li等于零而設(shè)置的為正的極小量；1/(Li+ε)為測試點到第i個離線指紋點歐氏離的倒數(shù)。

(5)

WKNN匹配算法示意如圖2所示。

3 子空間匹配算法

由于受到無線信道傳播環(huán)境的影響，信號的多徑傳播可能引起移動終端接收到的某些小區(qū)信號強度值的巨大波動，并且實際采集時，可能接收不到某些小區(qū)的信號，從而導(dǎo)致定位結(jié)果存在較大誤差?；诖耍疚奶岢隽俗涌臻g匹配算法，旨在剔除大誤差點、提高定位精度。

圖2 WKNN匹配算法示意圖Fig.2 WKNN matching algorithm schematic

本文所提的子空間匹配算法，其處理流程如圖3所示。

根據(jù)第2節(jié)提取出的子指紋庫U和在線實測數(shù)據(jù)T構(gòu)建子空間，并對相應(yīng)的子空間矩陣運用WKNN匹配算法獲得多個位置估計，利用3σ準則對這些位置做篩選，輸出最終定位結(jié)果，具體步驟描述如下。

圖3 子空間匹配算法流程圖Fig.3 Subspace matching algorithm flow chart

(6)

(7)

(8)

4 基于PCA的子空間匹配算法

子空間匹配算法能夠充分利用移動終端接收到的各小區(qū)信息，剔除大誤差點，提高定位精度，但是子空間匹配算法也大大增加了時間開銷。針對此問題，本文提出基于PCA的子空間的匹配算法，在運用子空間匹配算法之前，先對第3節(jié)提到的實測小區(qū)數(shù)據(jù)T和子指紋庫U運用PCA進行數(shù)據(jù)降維處理，再對降維后的數(shù)據(jù)運用子空間匹配算法?；赑CA的子空間匹配算法相較于子空間匹配算法能夠有效降低運算耗時。

4.1 主成分分析法

主成分分析法是一種最常用的特征提取和數(shù)據(jù)降維技術(shù)，被廣泛應(yīng)用于信號處理、模式識別、人工智能等領(lǐng)域。PCA是一種基于均方差意義上重建誤差和最小的線性分析方法，它提供了將高維數(shù)據(jù)向低維空間映射的方法[12-13]。

主成分分析法的主要目的是進行數(shù)據(jù)的降維，將原來Rm維空間的數(shù)據(jù)投影到Rd維空間中 (m≥d)，并使得降維后的數(shù)據(jù)僅含原數(shù)據(jù)的主要成分。PCA的本質(zhì)是在最小均方差意義下尋找最能代表數(shù)據(jù)特征的投影向量子空間。

PCA算法對數(shù)據(jù)進行降維的處理步驟如下。

步驟4對矩陣V進行特征分解，求取特征值λi和對應(yīng)的特征向量wi，并降序排列特征值λi，使得λ1≥λ2≥…≥λm；

通過以上運算，每一個樣本R均可投影到由Wd張成的空間中，實現(xiàn)對樣本的降維。將PCA算法應(yīng)用于蜂窩網(wǎng)室內(nèi)指紋定位技術(shù)中，實現(xiàn)對高維指紋數(shù)據(jù)庫的降維處理，有效縮短運算耗時。

4.2 基于PCA的子空間匹配算法

基于PCA的子空間匹配算法，實現(xiàn)對數(shù)據(jù)庫降維處理后，利用子空間匹配算法，在保持高精度定位的同時，能夠有效減小時間開銷。

基于PCA的子空間匹配算法處理步驟如下。

步驟1構(gòu)建實測矩陣T和子指紋庫矩陣U。根據(jù)移動終端在線所監(jiān)測到的小區(qū)信息，在離線指紋數(shù)據(jù)庫中提取相應(yīng)子指紋庫構(gòu)成矩陣為U。移動終端在線接收小區(qū)信息構(gòu)成的實測矩陣為T。

步驟2對子指紋庫矩陣U進行特征提取。求取特征值λi和對應(yīng)的特征向量wi。根據(jù)具體需求，取特征值之和占總和一定比例α的前Δ′個特征值對應(yīng)的特征向量構(gòu)成特征矩陣W。

步驟3對實測矩陣T和子指紋庫矩陣U進行降維處理。降維后的實測矩陣為Φ，Φ=TW。降維后的子指紋庫矩陣為D，D=UW。矩陣Φ和矩陣D的列數(shù)維度都為Δ′。

步驟4對矩陣Φ和矩陣D采用子空間匹配算法，求得最終估計位置坐標輸出。

5 算法驗證與結(jié)果分析

5.1 實驗環(huán)境

為了驗證本文提出的基于PCA的子空間匹配算法的有效性和可靠性，選取面積64.6 m×18.5 m的重慶郵電大學(xué)行政樓一樓作為實測環(huán)境，如圖4所示，測試環(huán)境共設(shè)置356個指紋點，左下角五角星為坐標原點。根據(jù)傳播環(huán)境的不同將測試區(qū)域分為5個子區(qū)域，利用帶有合格標識的10 m規(guī)格51系列的鋼卷尺對5個子區(qū)域進行網(wǎng)格劃分和每個指紋點坐標的測量，由于測量由多人進行讀數(shù)和確認，且正確使用卷尺，因此，指紋點坐標誤差在5 cm以內(nèi)，幾乎可以忽略不計。圖4中1區(qū)、2區(qū)、4區(qū)指紋點間隔為0.6 m，3區(qū)、5區(qū)指紋點間隔為0.8 m。之后利用路測軟件在各指紋點采集覆蓋小區(qū)的信號強度參數(shù)，構(gòu)建離線指紋數(shù)據(jù)庫。測試時，Δ根據(jù)特征值之和占總和的不同比例α進行取值；δ取值為Δ-2；隨機采集200組信號強度進行算法驗證。

圖4 重慶郵電大學(xué)行政樓一樓平面圖Fig.4 First floor of administration building of CQUPT

信號采集平臺及采集到的數(shù)據(jù)格式如圖5和圖6所示。測試中使用路測軟件TEMS 9.1和索尼愛立信k800i手機進行數(shù)據(jù)采集。圖6中，RSSI為信號強度，ARFCN為頻點號，BSIC為基站識別色碼，一對ARFCN與BSIC標志一個小區(qū)。

圖5 信號采集平臺Fig.5 Signal acquisition platform

圖6 采集到的數(shù)據(jù)格式Fig.6 Collected data format

5.2 實驗結(jié)果分析

針對上述實驗環(huán)境，本文首先討論WKNN中K值的選擇，確定K值之后，分別從3個方面進行對比分析：①子空間匹配定位算法與WKNN匹配定位算法的定位精度及耗時；②基于PCA的子空間匹配定位算法在α取值不同情況下的定位精度及耗時；③基于PCA的子空間匹配算法與子空間匹配算法的定位精度及耗時。

本文首先討論K值的選擇，后面所有的實驗都是基于此次選擇的K值進行的比較。圖7是不同K值下WKNN的定位誤差。

圖7 不同K值下WKNN的定位誤差Fig.7 Positioning error of WKNN under different K values

由圖7可知，當K=3時，系統(tǒng)的定位精度整體上優(yōu)于其他K值的情況，雖然在小于4 m處的累計誤差概率略低于K=1的概率，但對大誤差點的抑制性能明顯優(yōu)于K=1的情況，因此，本文K取值為3。

得到K值之后，采用本文第3節(jié)所提出的子空間匹配算法進行定位。使用子空間匹配算法時，小區(qū)維度Δ的值為25，δ取值為Δ-2=23。WKNN匹配算法與子空間匹配算法的定位誤差累積分布函數(shù)如圖8所示。

圖8 子空間匹配算法與WKNN匹配算法對比Fig.8 Comparison of the subspace and WKNN matching algorithm

WKNN匹配算法與子空間匹配算法定位精度及耗時對比如表2所示。

由圖8及表2可以看出，子空間匹配算法相較于WKNN匹配算法定位效果提升明顯，平均定位精度提升了0.9 m，67%誤差精度提升了1.0 m，95%誤差精度提升了3.2 m。綜合以上分析可知，子空間匹配算法相較于WKNN匹配算法能夠有效剔除大誤差點，提升整體定位精度，尤其在定位誤差較大時，子空間匹配算法定位效果提升更明顯。但子空間匹配算法耗時過高，嚴重影響系統(tǒng)實時性。

表2 WKNN匹配算法與子空間匹配算法定位精度及耗時比較Tab.2 WKNN matching algorithm and subspace matching localization precision and time-consuming comparison

基于本文第4節(jié)提出的算法，對基于PCA的子空間匹配算法的定位效果進行分析。采用基于PCA的子空間匹配算法進行定位時，α值為進行數(shù)據(jù)庫降維處理時選取的特征值之和占總和的比例。下面對α取值分別為1.00，0.95，0.90，0.85，0.80時的定位精度及耗時進行對比分析。圖9是不同α下的定位誤差比較。

由圖9可以看出，α取值分別為0.90，0.85，0.80時，無論是從整體定位精度上還是對大誤差的抑制效果上都明顯低于α取值分別為1，0.95時的定位效果，這是因為若α取值過低，會損失較多有用信息，導(dǎo)致定位效果變差。α取值不同時的定位精度及耗時如表3所示。

表3的結(jié)果表明，在α取值為0.95時，基于PCA的子空間匹配算法定位精度雖然略低于單純的子空間匹配算法，但耗時相比于原子空間匹配算法大大降低。因此，綜合定位精度和耗時考慮，α取值為0.95時定位性能最優(yōu)。

表3 α取值不同時的定位精度及耗時比較Tab.3 Positioning accuracy and time consuming comparison when α is different

最后，本文對WKNN匹配算法、子空間匹配算法、基于PCA的子空間匹配算法的定位效果從定位精度和耗時進行整體對比分析，如表4所示。

表4中，相較于WKNN匹配算法，子空間匹配算法能夠有效剔除大誤差點，尤其在WKNN匹配算法的定位誤差較大時能夠有效提高定位精度，并從整體上提升定位精度。但是，子空間匹配算法相較于WKNN匹配算法時間開銷過高?；赑CA的子空間匹配算法保留了子空間匹配算法剔除大誤差點、提升定位誤差較大時定位精度的優(yōu)點，并降低了耗時。從定位精度和耗時整體方面考慮，基于PCA的子空間匹配算法相較于WKNN匹配算法、子空間匹配算法具有更優(yōu)的定位性能。

表4 3種匹配算法定位精度及耗時比較Tab.4 Three match algorithm positioning accuracy and time consuming comparison

6 結(jié)束語

本文針對蜂窩網(wǎng)室內(nèi)指紋定位過程中估計出的用戶位置誤差較大的問題，采用子空間匹配算法，針對子空間匹配算法運算耗時嚴重的問題，提出基于PCA的子空間匹配算法，在可以接受的時間開銷下，剔除大誤差點，提升整體定位精度。實驗結(jié)果表明，本文提出的基于PCA的子空間匹配算法可以提高定位精度，具有較好的整體定位性能。

[1] GU Y Y, LO A, NIEMEGEERS I. A survey of indoor positioning systems for wireless personal networks [J]. IEEE COMMUNICATIONS SURVEYS AND TUTORIALS, 2009, 11(1): 12-32.

[2] 趙銳，鐘榜，朱祖禮，等.室內(nèi)定位技術(shù)及應(yīng)用綜述[J]. 電子科技, 2014, 27(3):154-157.

ZHAO Rui, ZHONG Bang, ZHU Zuli, et al. Indoor positioning technology and application summary[J]. Electronic Technology, 2014, 27(3):154-157.

[3] SHOARINEJAD K, SOLTAN M, MOSHFEGHI M. RFID location systems and methods: US, 8294554 B2 [P]. 2012-10-23.

[4] TIAN Z S, ZHANG Y, ZHOU M, et al. Smartphone-based indoor integrated WiFi/MEMS positioning algorithm in a multi-floor environment[J]. Micromachines, 2014, 6(3): 1-9.

[5] 周先贊，熊劍，郭杭，等. 基于超聲波/INS信息融合的室內(nèi)定位方法[J]. 壓電與聲光，2016, 38(2): 316-319.

ZHOU Xianzan, XIONG Jian, GUO Hang, et al. The Indoor Position Method Based on Ultrasonic/INS Information Fusion [J]. Piezoelectrics and Acoustooptics, 2016, 38(2): 316-319.

[6] 楊小鳳，陳鐵軍，黃志文，等. 基于超寬帶的TOA-DOA 聯(lián)合定位方法[J].重慶郵電大學(xué)學(xué)報：自然科學(xué)版，2016, 28(2):194-198.

YANG Xiaofeng, CHEN Tiejun, HUANG Zhiwen, et al. Hybrid TOA-AOA location method based on ultra-wideband[J].Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition，2016, 28(2):194-198.

[7] WANG Y X, YE Q, CEHNG J, et al. RSSI-based bluetooth indoor localization[C]//IEEE.11th International Conference on Mobile Ad-Hoc and Sensor Networks. New York, USA：IEEE Press, 2015:165-171.

[8] LIU X D, HE W, TIAN Z S. The improvement of RSS-based location fingerprint technology for cellular networks[C]//IEEE.2012 International Conference on Computer Science & Service System (CSSS).New York, USA：IEEE Press, 2012:1267-1270.

[9] JIHOON H, TOMOAKI O. Device-free passive localization from signal subspace eigenvectors[C]//IEEE.Global Communications Conference (GLOBECOM).New York, USA：IEEE Press,2014: 430-435.

[10] 王磊，周慧，蔣國平，等. 基于WiFi的自適應(yīng)匹配預(yù)處理WKNN算法[J]. 信號處理, 2015(9):1067-1074.

WANG Lei, ZHOU Hui, JIANG Guoping, et al. The adaptive matching pretreatment WKNN algorithm based on WiFi [J]. Signal Processing, 2015(9):1067-1074.

[11] 正態(tài)分布及3Sigma原理[EB/OL]. (2013-03-25)[2017-01-22].http://wenku.baidu.com/view/ef44d6d528ea81c758f578c5.html.

Normal distribution and 3Sigma principle [EB/OL]. (2013-03-25)[2017-01-22].http://wenku.baidu.com/view/ef44d6d528ea81c758f578c5.html.

[12] PUYATI W, WALAIRACHT A. Efficiency improvement for unconstrained face recognition by weightening probability values of modular PCA and wavelet PCA[C]//IEEE.International Conference on Advanced Communication Technology. New York, USA：IEEE Press, 2008:1449-1453.

[13] 楊開睿，孟凡榮，梁志貞. 一種自適應(yīng)權(quán)值的PCA算法[J]. 計算機工程與應(yīng)用,2012, 48(3):189-191.

YANG Kairui, MENG Fanrong, LIANG Zhizhen. An adaptive weighting of PCA algorithm[J].Computer engineering and application, 2012, 48(3):189-191.

s：The National Natural Science Foundation of China (61301126);The Fundamental and Frontier Research Project of Chongqing (cstc2013jcyjA40041,cstc2015jcyjBX0065);The Young Science Research Program of Chongqing University of Posts and Telecommunications(A2013-31)

Improvedindoorlocalizationmatchingalgorithmforcellularnetworks

TIAN Zengshan, SHU Yueyue, LIU Yiyao, LI Lingxia

Chongqing Key Lab of Mobile Communications Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R. China)

Due to the dynamic fading characteristics of wireless channel, the localization performance will be dramatically deteriorated in cellular network. Therefore, a principal components analysis (PCA) based subspace matching algorithm for indoor localization within cellular networks is proposed, which not only guarantees the real-time localization requirement, but also effectively eliminates the large error points for the sake of accuracy enhancement. Specifically, the off-line fingerprint database is constructed firstly according to the positional characteristics caused by the non-line-of-sight propagation of the wireless cellular signal. Then the sub-fingerprint database is extracted in line with the

signal. Next, PCA algorithm is utilized to reduce the dimension of both on-line received signal strength and sub-fingerprint database, which then forms a new subspace. After that, the weighted K nearest neighbors (WKNN) is adopted for multiple-target localization. Finally, the targets are screened based on 3σrule in order to determine the final location. Experimental results show that the proposed approach can effectively eliminate the outliers and thus improve the overall on-line positioning performance under the premise of ensuring the real-time positioning.

cellular networks; sub-fingerprint database; subspace matching; PCA; 3sigma rule

10.3979/j.issn.1673-825X.2017.06.006

2016-12-21

2017-04-20

舒月月 675522567@qq.com

國家自然科學(xué)基金(61301126)；重慶市基礎(chǔ)與前沿研究計劃項目(cstc2013jcyjA40041,cstc2015jcyjBX0065)；重慶郵電大學(xué)青年科學(xué)研究項目(A2013-31)

TN 929.5

A

1673-825X(2017)06-0744-07

田增山(1968 -)，男，河南固始人，教授，博士生導(dǎo)師，研究方向為移動通信、個人通信、GPS及蜂窩網(wǎng)定位系統(tǒng)及其應(yīng)用技術(shù)研究。E-mail: tianzs@cqupt.edu.cn。

舒月月(1992 -)，女，重慶人，碩士研究生，研究方向為蜂窩網(wǎng)室內(nèi)定位技術(shù)、WiFi室內(nèi)定位。E-mail:675522567@qq.com。

劉儀瑤(1992 -)，女，河南南陽人，碩士研究生，研究方向為室內(nèi)定位技術(shù)與地圖構(gòu)建。E-mail: 953625166@qq.com。

李玲霞(1976 -)，女，湖北武穴人，高級工程師，碩士生導(dǎo)師，研究方向為未來移動通信理論與技術(shù)、寬度無線接入技術(shù)。E-mail: lilx@cqupt.edu.cn。

(編輯：王敏琦)