沈 昀 陳 愛

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

1 引 言

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

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

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

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

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

2.1 指紋的稀疏表示

受到圖像識別領(lǐng)域中特征臉方法的啟發(fā)[6]，我們聯(lián)想到提取指紋的特征來進行指紋分類。稀疏表示作為近年來特征臉方法的主流方法，以其簡單、準確和擴展性強成為了一種有效、快速的特征提取方法。因此我們考慮引入稀疏表示方法提取指紋特征，同時去除噪聲。

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

通過稀疏表示方法，具有相似特征的同一類信號可以被一組特定的不完備基間接表示，而無法被這組基近似完整表示的信號則不具有該特征，因而不屬于該類。與此同時，噪聲由于其本身存在的隨機性而不具有特征，更不具有信號的特征，因此無法被稀疏表示?？梢姡孟∈璞硎痉椒ǖ奶卣魈崛?，既可以將信號進行分類，又具有很好的去噪能力。

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

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

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

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

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

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

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

2.2.1 訓(xùn)練過程

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

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

獲得參考點 i 的大小為 k 的稀疏字典的具體過程如圖 2 所示。

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

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

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

2.2.2 定位匹配過程

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

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

最終選取最小的 distance 對應(yīng)的參考點坐標作為定位結(jié)果。

3 定位實驗設(shè)置

選取一個 16 m×7 m 的辦公區(qū)域(圖 3)進行實驗。我們在該區(qū)域布置了 9 個無線信號發(fā)射源，使用 MOTO XT702 手機進行訓(xùn)練與測試的工作。

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

最后計算定位結(jié)果與實際點的坐標距離作為定位誤差。后面將對整個定位區(qū)域的定位效果做分析。

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

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

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

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

5 結(jié) 論

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

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

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