利用指紋稀疏性的室內(nèi)定位技術(shù)

沈 昀 陳 愛(ài)

(中國(guó)科學(xué)院深圳先進(jìn)技術(shù)研究院實(shí)時(shí)監(jiān)測(cè)與傳輸技術(shù)研究中心 深圳 518055)

1 引 言

隨著移動(dòng)設(shè)備的發(fā)展與普及，基于信息的應(yīng)用服務(wù)層出不窮。 用戶(hù)信息中一個(gè)相當(dāng)有價(jià)值的信息就是用戶(hù)的位置信息，因而室內(nèi)定位技術(shù)也成為了近年來(lái)的一個(gè)熱點(diǎn)問(wèn)題。由于室內(nèi)定位信息可以廣泛應(yīng)用于醫(yī)院、商場(chǎng)和展館等各種大型室內(nèi)場(chǎng)所，因此如何方便地獲得準(zhǔn)確的室內(nèi)定位信息是一個(gè)十分值得研究的課題[1]。

隨著 GPS(Global Positioning System)技術(shù)的不斷完善，室外定位技術(shù)已發(fā)展得十分成熟。然而，由于在室內(nèi)無(wú)法接收 GPS 信號(hào)及存在室內(nèi)環(huán)境復(fù)雜等局限，室內(nèi)定位技術(shù)尚面臨著很多技術(shù)或成本上的難題?，F(xiàn)有的相對(duì)成熟的室內(nèi)定位技術(shù)主要基于 RFID(Radio Frequency Identification)[2]、超聲波和 FM(Frequency Modulation)[3]等設(shè)備。盡管這種方法可以獲得較高的精確度，但需要額外的信號(hào)發(fā)射或接收設(shè)備，所以一方面有著較高的成本限制，另一方面部署也費(fèi)時(shí)費(fèi)力?；谶@些考慮，目前出現(xiàn)的低成本且成熟的室內(nèi)定位技術(shù)則是基于無(wú)線網(wǎng)絡(luò)信號(hào)強(qiáng)度(Received Signal Strength Indication，RSSI)的室內(nèi)定位技術(shù)[4]。由于該技術(shù)可以利用當(dāng)今主流移動(dòng)設(shè)備普遍配備的無(wú)線網(wǎng)絡(luò)信號(hào)接收模塊以及大型室內(nèi)場(chǎng)所普遍存在的無(wú)線網(wǎng)絡(luò)信號(hào)，能做到近乎純軟件實(shí)現(xiàn)的室內(nèi)定位，在目前的市場(chǎng)中擁有比較廣大的應(yīng)用場(chǎng)景。

基于 RSSI 的室內(nèi)定位技術(shù)主要分為基于模型和基于指紋的兩類(lèi)主流算法。其中，基于模型的算法指的是通過(guò)現(xiàn)有的室內(nèi)位置信息以及無(wú)線信號(hào)發(fā)射源信息，建立數(shù)學(xué)模型，根據(jù)模型由信號(hào)強(qiáng)度推算出相應(yīng)的位置坐標(biāo)。該類(lèi)算法簡(jiǎn)單易實(shí)現(xiàn)，但由于室內(nèi)環(huán)境較為復(fù)雜且無(wú)線網(wǎng)絡(luò)信號(hào)容易被干擾和吸收，數(shù)學(xué)模型很難全面且動(dòng)態(tài)地體現(xiàn)位置信息與信號(hào)強(qiáng)度間的關(guān)系，因而存在較大的定位誤差?；谥讣y的室內(nèi)定位算法中，指紋指的是在某個(gè)地點(diǎn)，設(shè)備接收到的數(shù)個(gè)無(wú)線信號(hào)發(fā)射源發(fā)射的信號(hào)強(qiáng)度組成的向量?？梢韵胂?，由于信號(hào)強(qiáng)度隨著距離衰減，每個(gè)點(diǎn)可以獲得不同的指紋。因此應(yīng)用指紋法時(shí)，首先采集一定密度的定位參考點(diǎn)的指紋信息，之后定位時(shí)再將實(shí)時(shí)指紋通過(guò)匹配算法匹配到對(duì)應(yīng)的參考指紋上。指紋法可以獲得較高的定位精度且可以做到純軟件實(shí)現(xiàn)。

目前比較常見(jiàn)的基于指紋的室內(nèi)定位算法包括簡(jiǎn)單的 KNN 算法以及較為復(fù)雜的概率模型算法[4]。KNN 算法指直接用向量距離匹配指紋，而概率模型算法(如高斯模型法)則使用概率模型對(duì)指紋的分布概率進(jìn)行估計(jì)，從而匹配指紋。但是，由于室內(nèi)環(huán)境與室內(nèi)設(shè)備的干擾，指紋并不完全穩(wěn)定，容易受到噪聲的干擾，導(dǎo)致定位精度下降。因此，本文引入稀疏表示方法[5]，提出一種指紋匹配算法，利用指紋的稀疏性，提取指紋的主要特征，從而分離指紋中的噪聲，提高定位匹配精度。

2 利用指紋稀疏性的定位方法

2.1 指紋的稀疏表示

受到圖像識(shí)別領(lǐng)域中特征臉?lè)椒ǖ膯l(fā)[6]，我們聯(lián)想到提取指紋的特征來(lái)進(jìn)行指紋分類(lèi)。稀疏表示作為近年來(lái)特征臉?lè)椒ǖ闹髁鞣椒ǎ云浜?jiǎn)單、準(zhǔn)確和擴(kuò)展性強(qiáng)成為了一種有效、快速的特征提取方法。因此我們考慮引入稀疏表示方法提取指紋特征，同時(shí)去除噪聲。

信號(hào)能夠被稀疏表示，就是將信號(hào)投影到變換基時(shí)絕大部分變換系數(shù)的絕對(duì)值很小或?yàn)榱?，這樣得到的信號(hào)被認(rèn)為是稀疏的。因而信號(hào)的稀疏表示可看作是信號(hào)由一組不完備的基(基的個(gè)數(shù)小于 N)近似完整表示，這是原始信號(hào)的一種間接表達(dá)。

通過(guò)稀疏表示方法，具有相似特征的同一類(lèi)信號(hào)可以被一組特定的不完備基間接表示，而無(wú)法被這組基近似完整表示的信號(hào)則不具有該特征，因而不屬于該類(lèi)。與此同時(shí)，噪聲由于其本身存在的隨機(jī)性而不具有特征，更不具有信號(hào)的特征，因此無(wú)法被稀疏表示?？梢?jiàn)，利用稀疏表示方法的特征提取，既可以將信號(hào)進(jìn)行分類(lèi)，又具有很好的去噪能力。

本文利用稀疏表示算法進(jìn)行指紋匹配，為了驗(yàn)證指紋具有稀疏性，我們引入主成分分析方法[7]進(jìn)行了實(shí)驗(yàn)。主成分分析方法通過(guò)將原有信號(hào)的基進(jìn)行旋轉(zhuǎn)變換，以獲得數(shù)量較少的重要基，這些基即代表了原有信號(hào)的主要成分。主成分的方向越少，則信號(hào)越稀疏。通過(guò)實(shí)驗(yàn)，我們采集了數(shù)個(gè)點(diǎn)的數(shù)百條指紋，對(duì)于每個(gè)定位點(diǎn)，分析出信號(hào)在其維度方向上僅具有一個(gè)能量極強(qiáng)的主成分(如圖 1 所示)，因此可以說(shuō)明指紋本身是具有稀疏性的。

圖1 RSSI 指紋的主成分分析Fig. 1. PCA of RSSI fi ngerprints

2.2 基于指紋稀疏表示的室內(nèi)定位算法

通過(guò)上述分析，我們研究出了一個(gè)利用指紋稀疏表示的室內(nèi)定位算法。該算法利用指紋構(gòu)建稀疏表示所需要的不完備稀疏字典，進(jìn)而使用稀疏字典對(duì)需要被定位的指紋進(jìn)行稀疏表示。通過(guò)稀疏表示一方面對(duì)指紋進(jìn)行了分類(lèi)，另一方面在一定程度上將指紋中的高維噪聲分離出來(lái)。整個(gè)算法流程可以大致分為兩個(gè)過(guò)程：訓(xùn)練過(guò)程和定位匹配過(guò)程。

在訓(xùn)練過(guò)程中，首先采集各個(gè)參考點(diǎn)的訓(xùn)練指紋，然后利用訓(xùn)練指紋訓(xùn)練出每個(gè)參考點(diǎn)的稀疏字典，并且得到該點(diǎn)的主特征指紋及其稀疏表示形式。

在定位匹配過(guò)程中，我們將實(shí)時(shí)指紋向每個(gè)參考點(diǎn)的稀疏字典進(jìn)行投影，獲得相應(yīng)的可以被表示部分的稀疏表示形式以及不能被表示的殘差[8]。殘差越大，代表該指紋與該參考點(diǎn)處的特征指紋不相似程度越大，而稀疏表示形式的近似程度也在一定程度上代表了指紋的相似程度。因此本方法通過(guò)一個(gè)權(quán)重系數(shù)調(diào)整殘差與稀疏表示形式近似程度對(duì)于匹配結(jié)果的影響，從而獲得優(yōu)化的近似程度。最終最大程度上象征了指紋與其對(duì)應(yīng)參考點(diǎn)的匹配程度。

由于指紋本身具有稀疏性，而環(huán)境導(dǎo)致的隨機(jī)噪聲由于其隨機(jī)性，而不具有稀疏性，因此使用稀疏表示方法表示出的特征指紋可在一定程度上去除噪聲，從而提高定位精度以及定位算法的魯棒性。

2.2.1 訓(xùn)練過(guò)程

訓(xùn)練過(guò)程中首先要采集訓(xùn)練指紋。在一個(gè)定位環(huán)境中，我們對(duì)設(shè)備可到達(dá)的區(qū)域每隔一定距離設(shè)置一個(gè)參考點(diǎn) P1, P2, …, PN表示。之后，在每個(gè)參考點(diǎn)，分別用 Pi(i＝1, 2, …, N)均采集 M條訓(xùn)練指紋 Fi1, Fi2, …, FiM存入指紋庫(kù)中。指紋庫(kù)中記錄著每個(gè)定位點(diǎn)的坐標(biāo)(xi, yi)，以及對(duì)應(yīng)的 M 條指紋 Fi1, Fi2, …, FiM。

對(duì)于每個(gè)參考點(diǎn)，我們使用稀疏表示方法提取它的特征指紋，首先需要獲得稀疏表示中的稀疏字典，字典元素可以由采集到的訓(xùn)練指紋構(gòu)成。獲取稀疏字典的求解過(guò)程原本是一個(gè) NP 困難(即無(wú)法在多項(xiàng)式時(shí)間內(nèi)求解)的問(wèn)題，因此我們使用貪心算法獲得該問(wèn)題的次優(yōu)解。正交匹配追蹤法是稀疏表示中比較流行的一種方法[9]，鑒于它速度快、復(fù)雜度低，我們也采取這種算法進(jìn)行稀疏字典的選取。稀疏字典由該點(diǎn)部分訓(xùn)練指紋構(gòu)成，可以以線性方式近似表示該點(diǎn)的所有指紋，并且字典大小小于指紋維度[10]。

獲得參考點(diǎn) i 的大小為 k 的稀疏字典的具體過(guò)程如圖 2 所示。

圖2 獲取參考點(diǎn) i 稀疏字典的流程圖Fig. 2. Flow chart of fi nding the sparse dictionary of position i

在求得稀疏字典后，需要得到該點(diǎn)的特征指紋以及其稀疏表示。我們使用訓(xùn)練指紋的平均指紋作為噪聲較小的主指紋，之后將平均指紋向其字典 Di構(gòu)成的空間上進(jìn)行投影，獲得投影系數(shù)向量 Ci＝(ci1, ci2, …, cik)以及殘差 r，其中殘差作為噪聲直接丟棄。投影系數(shù)作為稀疏表示的表現(xiàn)形式與該點(diǎn)的稀疏字典一起存儲(chǔ)在指紋庫(kù)中。

至此，訓(xùn)練過(guò)程結(jié)束，我們得到了每個(gè)定位點(diǎn)特征指紋的稀疏表示形式以及相應(yīng)的稀疏字典。

2.2.2 定位匹配過(guò)程

匹配過(guò)程中，獲得需要進(jìn)行定位的實(shí)時(shí)指紋后，需要計(jì)算該指紋與每個(gè)參考點(diǎn)特征指紋的近似程度。其中，近似程度由兩部分組成：一是指紋間稀疏表示的相似程度；二是不能被表示的殘差的大小。我們通過(guò)添加一個(gè)權(quán)重參數(shù)來(lái)調(diào)整這兩部分對(duì)近似程度的影響，而這個(gè)權(quán)重參數(shù)由另外采集的一部分訓(xùn)練指紋通過(guò)訓(xùn)練得出。最終，我們將選取近似程度最大的參考點(diǎn)作為定位結(jié)果。

首先我們需要獲得要進(jìn)行定位的實(shí)時(shí)指紋的稀疏表示形式。對(duì)于需定位的指紋 ft，將其往Pi(i＝1, 2, …, N)的每個(gè)參考點(diǎn)的字典 Di上進(jìn)行最小二乘投影，獲得對(duì)應(yīng)的系數(shù) Cit＝(cit1, cit2, …,citk)與殘差 rt。之后使用距離公式(見(jiàn)公式(2))計(jì)算指紋與每個(gè)定位點(diǎn)的距離。

最終選取最小的 distance 對(duì)應(yīng)的參考點(diǎn)坐標(biāo)作為定位結(jié)果。

3 定位實(shí)驗(yàn)設(shè)置

選取一個(gè) 16 m×7 m 的辦公區(qū)域(圖 3)進(jìn)行實(shí)驗(yàn)。我們?cè)谠搮^(qū)域布置了 9 個(gè)無(wú)線信號(hào)發(fā)射源，使用 MOTO XT702 手機(jī)進(jìn)行訓(xùn)練與測(cè)試的工作。

在該區(qū)域里共設(shè)置 141 個(gè)參考點(diǎn)。對(duì)于每個(gè)參考點(diǎn)，采集 30 條訓(xùn)練指紋，其中 25 條用于訓(xùn)練稀疏字典，5 條用于訓(xùn)練參數(shù)。之后選擇了圖3 兩條路徑上的 80 個(gè)點(diǎn)作為測(cè)試點(diǎn)，每個(gè)點(diǎn)采集了 20 次指紋作為測(cè)試指紋。

最后計(jì)算定位結(jié)果與實(shí)際點(diǎn)的坐標(biāo)距離作為定位誤差。后面將對(duì)整個(gè)定位區(qū)域的定位效果做分析。

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

經(jīng)過(guò)實(shí)驗(yàn)，本算法在實(shí)驗(yàn)區(qū)域的平均定位精度達(dá)到 2.78 米，結(jié)果如圖 4 所示。相對(duì)于傳統(tǒng)的常見(jiàn)算法—KNN 定位算法與高斯模型法，本方法的誤差累計(jì)分布圖表現(xiàn)明顯優(yōu)于兩者，平均精度提高 20% 以上。

圖4 中，KSR 代表本文提出的算法，CDF為誤差累計(jì)分布函數(shù)(cumulative distribution function)的英文縮寫(xiě)，根據(jù)圖中的圖例，我們可以清晰的區(qū)分出三種算法得到的定位誤差的表現(xiàn)：本方法的定位結(jié)果可以使 80% 的定位點(diǎn)誤差都在 4 米左右，而另外兩種傳統(tǒng)方法則要達(dá)到6 米左右，并且本算法中 50% 的定位點(diǎn)定位誤差為約 2.5m，而另外兩種算法則達(dá)到 4 米以上。分析誤差出現(xiàn)的原因，主要是由于室內(nèi)定位環(huán)境的復(fù)雜性，導(dǎo)致無(wú)線信號(hào)容易受到干擾或被吸收，導(dǎo)致定位時(shí)的無(wú)線信號(hào)強(qiáng)度包含了一部分噪聲。而本文提出的主要想法就是將無(wú)線信號(hào)強(qiáng)度構(gòu)成的指紋的主要特征提取出來(lái)，利用主要特征進(jìn)行定位，從而減弱噪聲的影響。

從實(shí)驗(yàn)結(jié)果上看，本文相對(duì)于另外兩種傳統(tǒng)算法，減弱了噪聲的影響，并且提高了精度，一定程度上達(dá)到了預(yù)想的效果。不過(guò)本算法還存在改進(jìn)的空間，如指紋構(gòu)成的靈活性。

5 結(jié) 論

本文提出了一種基于指紋稀疏表示的室內(nèi)定位算法。通過(guò)稀疏表示方法中的低維稀疏字典來(lái)將指紋中的高維噪聲進(jìn)行一定程度上的消除。通過(guò)降低噪聲的影響來(lái)提高定位算法的魯棒性以及對(duì)于實(shí)際室內(nèi)環(huán)境的抗噪能力。實(shí)際環(huán)境中的實(shí)驗(yàn)表明本文算法較傳統(tǒng)算法具有更高的定位精度。

目前本文算法中利用的指紋是由可以接收到的整個(gè)空間的所有信號(hào)強(qiáng)度構(gòu)成，在今后的實(shí)驗(yàn)中，我們會(huì)考慮篩選較為穩(wěn)定，并且特征較為明顯的信號(hào)構(gòu)成定位指紋。并且，由于稀疏表示方法并不要求字典元素之間有嚴(yán)格的比例關(guān)系，我們考慮在未來(lái)加入除無(wú)線網(wǎng)絡(luò)信號(hào)以外的信號(hào)來(lái)提高定位效果。

[1]Gu YY, Lo A, Niemegeers I. A survey of indoor positioning systems for wireless personal networks[J]. IEEE Communications Surveys and Tutorials,2009, 11(1): 13-32.

[2]Ni LM, Liu YH, Lau YC, et al. LANDMARC: indoor location sensing using active RFID [C]// Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, 2003:407-415.

[3]Chen Y, Lymberopoulos D, Liu J, et al. FM-based indoor localization [C]// Proceedings of the 10th International Conference on Mobile Systems,Applications and Services, 2012: 169-182.

[4]Kaemarungsi K, Krishnamurthy P. Modeling of indoor positioning systems based on location fingerprinting [C]// Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, 2004, 2: 1012-1022.

[5]Baraniuk RG. Compressive sensing [J]. IEEE Signal Processing Magazine, 2007, 24(4): 118-121.

[6]Wright J, Yang AY, Ganesh A, et al. Robust face recognition via sparse representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2): 210-227.

[7]Jolliffe IT. Principal Component Analysis [M].Chichester: John Wiley & Sons, Inc., 2005.

[8]Zhang L, Yang M, Feng XC. Sparse representation or collaborative representation: which helps face recognition? [C]// 2011 IEEE International Conference on Computer Vision, 2011: 471-478.

[9]Tropp JA, Gilbert AC. Signal recovery from random measurements via orthogonal matching pursuit [J].IEEE Transactions on Information Theory, 2007,53(12): 4655-4666.

[10]Gribonval R, Nielsen M. Sparse representations in unions of bases [J]. IEEE Transactions on Information Theory, 2003, 49(12): 3320-3325.

[11]Lawson CL, Hanson RJ. Solving Least Squares Problems [M]. New Jersey, Englewood Cliffs,:Prentice-hall, 1974.