一種使用信號(hào)強(qiáng)度排序集合的單信標(biāo)定位算法

李棟孟，羅海勇，吳 彬，陳自力

(1.中國科學(xué)院計(jì)算技術(shù)研究所 移動(dòng)計(jì)算與新型終端北京市重點(diǎn)實(shí)驗(yàn)室，北京 100190；2.北京三星通信研究院，北京 100028)

1 引言

隨著無線網(wǎng)絡(luò)的廣泛部署和應(yīng)用，以及基于位置服務(wù)的應(yīng)用程序如社交網(wǎng)絡(luò)、個(gè)性化推薦等的蓬勃發(fā)展，基于無線保真(wireless fidelity，WiFi)的室內(nèi)定位技術(shù)得到了研究人員的廣泛關(guān)注。現(xiàn)如今廣泛使用的基于WiFi指紋的定位方法都是利用接收信號(hào)強(qiáng)度(received signal strength indicator，RSSI)作為度量[1-2]，但是由于室內(nèi)環(huán)境中的反射、衍射、散射等多徑效應(yīng)的影響，使得在同一位置的RSSI會(huì)有很大區(qū)別[3]，如圖1所示，在同一位置上的RSSI差別可以達(dá)到14 dB左右，RSSI的巨大的波動(dòng)性導(dǎo)致了定位性能不理想。所以，尋求一個(gè)更可靠的度量迫在眉睫。這個(gè)度量應(yīng)該更穩(wěn)定，并且有可以區(qū)分多徑效應(yīng)的能力?，F(xiàn)如今，被廣泛應(yīng)用的正交頻分復(fù)用技術(shù)(orthogonal frequency division multiplexing，OFDM)中，數(shù)據(jù)被調(diào)制在不同的頻率的副載波上，并且同時(shí)傳輸，這很好地表現(xiàn)了多徑效應(yīng)。而在802.11n標(biāo)準(zhǔn)中，信道響應(yīng)可以以信道狀態(tài)信息(channel state information，CSI)的形式從OFDM系統(tǒng)中抽取出來，它反映了每一個(gè)子載波的幅度和相位。和一個(gè)數(shù)據(jù)包只能接收到一個(gè)RSSI值相比，可以得到多個(gè)CSI值，并且這些值隨時(shí)間變化很小。基于CSI，本文利用信道與信道之間的關(guān)系，提出了一個(gè)使用信號(hào)層次化排序集合的單信標(biāo)定位算法，本文的算法包括兩個(gè)部分：首先用一個(gè)簡單并且有效的算法從單個(gè)信標(biāo)的各個(gè)信道中提取出CSI特征值，利用該特征值來建立指紋庫；然后，利用指紋匹配算法進(jìn)行相關(guān)計(jì)算來確定位置。

圖1 RSSI概率分布圖

2 相關(guān)研究

由于OFDM技術(shù)的使用，在802.11n中，信道響應(yīng)可以從OFDM接受器中以CSI的形式提取出來[4-5]。CSI描述了一個(gè)信號(hào)從發(fā)射端到接收端不同傳播路徑的信息，是散射、衍射以及衰減等的結(jié)合效應(yīng)。目前，基于CSI的室內(nèi)定位已經(jīng)吸引了很多研究人員的興趣，一些先前的研究已經(jīng)可以達(dá)到亞米甚至厘米級(jí)的定位精度。

文獻(xiàn)[6]利用細(xì)粒度CSI的頻率差異性建立了基于CSI的信號(hào)傳播衰減模型FIFS，盡管在定位精度上有很大提升，但是由于現(xiàn)如今WiFi協(xié)議的寬帶限制，導(dǎo)致在單個(gè)路徑上的區(qū)分性還不是很理想。

文獻(xiàn)[7]建立了基于CSI的指紋匹配算法PinLoc，通過計(jì)算每個(gè)位置的混合高斯分布，來建立指紋庫進(jìn)行定位，但是沒有利用AP的一個(gè)重要的特性：空間差異性。

文獻(xiàn)[8]則充分利用信標(biāo)的空間差異性和頻率差異性建立了一個(gè)基于概率模型的指紋定位算法，將每個(gè)位置的不同信道的CSI通過處理得到有效CSI，然后通過計(jì)算貝葉斯后驗(yàn)概率得到估計(jì)位置。

以上研究都只是通過抽取多徑分量的射頻功率作為測距或者射頻指紋，并沒有探究多個(gè)信道之間的關(guān)系。本文從不同信道之間的關(guān)系出發(fā)，提出了一種使用CSI的單信標(biāo)指紋定位算法，實(shí)驗(yàn)結(jié)果表明只使用一個(gè)信標(biāo)的定位精度明顯優(yōu)于基于RSSI的算法的定位精度，平均精度可以達(dá)到0.95 m。

3 使用信號(hào)強(qiáng)度排序集合的單信標(biāo)定位算法

使用信號(hào)強(qiáng)度排序集合的單信標(biāo)定位算法包含以下兩個(gè)步驟：

1)離線訓(xùn)練階段：處理從一個(gè)信標(biāo)接收到的30個(gè)信道的原始CSI信息，找到每一個(gè)信道CSI的特征值；然后，基于信道與信道之間特征值的關(guān)系構(gòu)建指紋庫；

2)在線定位階段：基于測試樣本信道與信道之間CSI特征值的關(guān)系，比較它們與指紋庫中數(shù)據(jù)的相似性，找到最相似的K個(gè)，求取這K個(gè)位置的加權(quán)質(zhì)心[9]，即為目標(biāo)位置。

3.1 離線訓(xùn)練階段

構(gòu)建指紋庫需要兩個(gè)步驟。

1)信道特征值提取

圖2為第3信道的信號(hào)變化情況，實(shí)驗(yàn)中，通過在一個(gè)固定位置采集同一個(gè)信標(biāo)的第3信道的CSI值，并畫出CSI的概率分布圖，圖2(a)總共采集50次CSI值，圖2(b)總共采集100次，圖2(c)總共采集200次，采集間隔均為3 s，因?yàn)榻K端的掃描間隔是1 s，間隔3 s采一次可以保證每次的CSI都是新的。

圖2 CSI概率分布圖

從圖2中可以看出，無論采集時(shí)間的長短，那些出現(xiàn)頻率很高的CSI值總是非常接近的，基于這個(gè)發(fā)現(xiàn)，提出了一個(gè)新的描述單一信道特征值的方法為

(1)

式(1)中，cValue表示每一個(gè)獨(dú)立信道的特征值。CSIpeak是這個(gè)信道出現(xiàn)頻率最大的CSI的幅度的值，如果測量獲得信道幅度值出現(xiàn)的概率都一樣，則選取CSI值最大的那個(gè)作為特征值，因?yàn)橹翟酱?，這個(gè)值就越有意義。式(1)是比較理想化的，因?yàn)樵趯?shí)際中wL和wR并不好確定，所以在實(shí)際中使用的公式為

(2)

將式(1)中的wL和wR設(shè)為同一個(gè)值，于是就變成了式(2)，相比式(1)而言，式(2)可以很方便地通過多次測算，找到最優(yōu)的w。

2) 指紋庫構(gòu)建

構(gòu)建指紋庫是基于指紋的定位方法最關(guān)鍵的部分，構(gòu)建指紋庫的方式不同，也就構(gòu)成了不同定位算法。

圖3 不同信道CSI對(duì)比圖

圖3表示的是信道2和信道15的60次采樣的CSI幅度變化情況，雖然在某一信道上的CSI值會(huì)有所變化，但是不同信道之間的CSI差值基本保持穩(wěn)定?；谛诺琅c信道之間的關(guān)系，本文構(gòu)建指紋庫為

fpIDCor{IDCor，(KEY0θ，VALUE0θ，...，
KEYnθ，VALUEnθ)}

(3)

式(3)中，fpIDCor表示的是在IDCor(基準(zhǔn)點(diǎn)坐標(biāo))處的指紋庫，KEYn表示信道n，而VALUEnθ表示的是在位置IDCor處其他信道的幅度值小于信道n處θ個(gè)db的所有信道的集合。式(3)中的θ是最關(guān)鍵的參數(shù)，因?yàn)槊恳粋€(gè)信道處的CSI幅度都有一定的波動(dòng)，所以θ的選取要略大于這個(gè)波動(dòng)值[10]。例如，在位置x測量到了6個(gè)信道的CSI值，按照式(2)計(jì)算每個(gè)信道的特征值，如表1所示。得到每個(gè)信道的特征值后按照式(3)構(gòu)建位置x的指紋，(此處θ的值取3)，最后建立的指紋庫如表2所示。

表1 信道特征值

這種構(gòu)建指紋庫的方式實(shí)質(zhì)是建立信道和信道之間的關(guān)系，使用這種關(guān)系來表示某一特定位置的特征，在定位階段通過這種關(guān)系的相似度來進(jìn)行定位。

表2 信道指紋庫

3.2 在線定位算法

在線定位階段，需要用接收到的CSI的值與離線階段訓(xùn)練得到的指紋庫相比較，找到最為相似的作為定位位置。具體來說就是使用式(3)將在某個(gè)位置實(shí)時(shí)接受到的CSI值構(gòu)建一條未知的指紋cpUnknown，然后在離線訓(xùn)練階段構(gòu)建的指紋庫里面去匹配找到最相似的指紋，該指紋對(duì)應(yīng)的位置即是定位位置。具體的匹配算法如表3所示。

簡單來說，匹配算法就是遍歷指紋庫里每一個(gè)基準(zhǔn)點(diǎn)的指紋，然后針對(duì)每一條指紋查找那些與未知指紋中具有相同key的集合，查找兩個(gè)集合中相同信道的數(shù)目，累計(jì)起來，把這個(gè)累計(jì)的數(shù)作為這個(gè)位置的得分，得分最高的那個(gè)位置即是預(yù)測的位置。由于單一位置會(huì)出現(xiàn)風(fēng)險(xiǎn)較大的情況，這里選取得分最高的K個(gè)位置，然后利用加權(quán)最近鄰算法(k weighted nearest neighbors，KWNN)求出目標(biāo)位置，實(shí)驗(yàn)結(jié)果表明，用KWNN方法定位精度比用最高分作為目標(biāo)位置要高。

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

4.1 實(shí)驗(yàn)設(shè)置

為了評(píng)估算法的定位精度，在中國科學(xué)院計(jì)算技術(shù)研究所科研樓7層的部分區(qū)域進(jìn)行定位實(shí)驗(yàn)，具體部署環(huán)境如圖4所示，定位區(qū)域面積為6 m×6 m，定位區(qū)域劃分為12個(gè)網(wǎng)格，網(wǎng)格間間隔是1 m，紅色五角星處為發(fā)射信標(biāo)。實(shí)驗(yàn)中使用TP-LINK的路由器，利用裝配有Intel WiFi Link 5300 802.11n 網(wǎng)絡(luò)接口卡的Thinkpad x200作為接收端。實(shí)驗(yàn)中修改了驅(qū)動(dòng)來接受CSI的值[11]。采集階段，在每個(gè)網(wǎng)格采樣100次，作為訓(xùn)練數(shù)據(jù)。定位階段每個(gè)點(diǎn)采取20次作為測試樣本。

圖4 實(shí)驗(yàn)環(huán)境布局

實(shí)驗(yàn)對(duì)定位區(qū)域不同θ的影響、不同K值的影響、時(shí)間遷移性的影響以及CSI與RSSI的比較等進(jìn)行實(shí)驗(yàn)，并基于累計(jì)誤差分布函數(shù)(cumulative distribution function，CDF)圖來表示定位性能。

4.2 不同θ值比較

指紋庫建立采用不同θ值的實(shí)驗(yàn)評(píng)估，不同θ的選取對(duì)定位精度有一定的影響，如圖5及圖6所示，實(shí)驗(yàn)分別對(duì)θ大小從1至6進(jìn)行測試，結(jié)果表明在θ值為3時(shí)，定位精度最高，在誤差1.5 m時(shí)，定位精度約為90%。分析其原因是每個(gè)信道的CSI值有一定的波動(dòng)性，當(dāng)θ值略大于該波動(dòng)性時(shí)候，才能區(qū)分不同信道，指紋庫的構(gòu)建才有意義。

圖5 不同θ的定位精度的CDF圖(θ=1，2，3)

圖6 不同θ的定位精度CDF圖(θ=3，4，5)

4.3 不同K值比較

對(duì)KWNN中不同數(shù)目K的實(shí)驗(yàn)，K為選取最相似的點(diǎn)的個(gè)數(shù)，通過對(duì)不同的K值得選取，和不使用KWNN(即K=1，利用得分最高的為定位位置)，分別進(jìn)行實(shí)驗(yàn)并對(duì)結(jié)果分析比較，實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 不同K值定位精度的CDF圖

從圖7可以看出，K=3和K=4時(shí)，定位精度最高，在1.5 m誤差的定位精度大于90%。但是隨著K的增大，定位精度反而下降。分析其原因是隨著K的增加，偏離正確位置的點(diǎn)的數(shù)目也相應(yīng)增多，所以最終加權(quán)得到的位置偏離實(shí)際位置會(huì)相應(yīng)增大，最終導(dǎo)致定位精度下降。因此，利用KWNN，可以提高定位精度，并且在這里K最好取3，因?yàn)镵=3和K=4定位效果相當(dāng)，但隨著K增加，算法計(jì)算復(fù)雜度增加，所以選取3比較合理。

4.4 時(shí)間遷移性

不同時(shí)間段定位性能的穩(wěn)定性是室內(nèi)定位需要考慮的一個(gè)重要問題，為此我們分別在早上8點(diǎn)、下午5點(diǎn)、晚上9點(diǎn)對(duì)目標(biāo)位置進(jìn)行采樣評(píng)估，實(shí)驗(yàn)結(jié)果如圖8所示，從圖中可以看出，不同時(shí)間段的定位性能差別不大，在1.5 m誤差的定位精度基本都可以達(dá)到90%，這表明基于CSI的單信標(biāo)指紋定位算法比較穩(wěn)定，非常適合于室內(nèi)定位。

圖8 時(shí)變性定位精度的CDF圖

4.5 CSI與RSSI比較

實(shí)驗(yàn)還對(duì)RSSI和CSI做了比較，本文采用同樣方法，利用任意10個(gè)信標(biāo)對(duì)RSSI進(jìn)行同樣的實(shí)驗(yàn)，來與CSI作對(duì)比，結(jié)果如圖9所示，從圖中可以看出僅僅用1個(gè)信標(biāo)的CSI的定位效果也要比使用10個(gè)信標(biāo)的RSSI的定位效果好。

圖9 CSI與RSSI定位性能比較

4.6 算法復(fù)雜度分析

基于CSI的單信標(biāo)指紋定位算法的復(fù)雜度主要來源于兩個(gè)方面，一方面是離線階段指紋庫的構(gòu)建，其復(fù)雜度是O(n2)，n是信道的數(shù)目；另一方面是在線定位階段的匹配過程，其復(fù)雜度是O(n×m)，n是信道的數(shù)目，m是指紋庫中信道k對(duì)應(yīng)的指紋，且0≤m≤n。

5 結(jié)束語

本文提出了一種使用信號(hào)強(qiáng)度排序集合的單信標(biāo)定位算法。離線訓(xùn)練階段先提取出樣本中每一個(gè)信道的特征值，利用不同信道的特征值構(gòu)建指紋庫；在線定位階段利用接受到的不同信道的CSI值之間的關(guān)系，與指紋庫中的相匹配，得到最匹配的K個(gè)點(diǎn)，利用KWNN算法得到目標(biāo)位置。然后，通過對(duì)θ值、K數(shù)目、時(shí)間遷移性以及與RSSI對(duì)比等方面實(shí)驗(yàn)進(jìn)行實(shí)驗(yàn)評(píng)估，實(shí)驗(yàn)結(jié)果表明利用單個(gè)信標(biāo)的基于CSI的指紋定位算法的平均定位精度可以達(dá)到0.95 m，適合室內(nèi)定位。下一步研究可以在以下方向進(jìn)行，一方面，可以利用多個(gè)信標(biāo)來改善定位精度；另一方面，由于如今的智能手機(jī)已經(jīng)裝配有802.11n芯片，所以可以嘗試在手機(jī)上實(shí)現(xiàn)本文的定位算法。

[1] KUSHKI A，PLATANIOTIS K N，VENETSANOPOULOS A N.Kernel-based Positioning in Wireless Local Area Networks[J].IEEE Transactions on Mobile Computing，2007，Montreal，2007，6(6)：689-705.

[2] MIKKEL B K，GEORG T，CLAUDIA L.Zone-based RSS Reporting for Location Fringerprinting[C]//Proceedings of the 5th International Conference on Pervasive Computing.Toronto：Springer Berlin Heidelberg，2007：316-333.

[3] MOUSTAFA Y，ASHOK A.The Horus WLAN Location Determination System[EB/OL].[2014-08-02].http：//www.cs.umd.edu/～moustafa/papers/horus_usenix.pdf.

[4] DANIEL H，HU Wen-jun，ANMOL S，et al.Predictable 802.11 Packet Delivery from Wireless Channel Measurements[EB/OL].[2014-08-02].http：//homes.cs.washington.edu/～dhalperi/pubs/comm356s-halperin.pdf.

[5] APURV B，CHEN Yi-chao，SWATI R，et al.Harnessing Frequency Diversity in Wi-Fi Networks[EB/OL].[2014-08-02].//http：//www.cs.utexas.edu/～swati/freq-div-mob11.pdf.

[6] WU Kai-shun，XIAO Jiang，YI You-wen，et al.Fila：Fine-grained Indoor Localization[C]//Proceedings of the 31st IEEE Conference on Computer Communications.Orlando，F(xiàn)lorida：IEEE，2012：2210-2218.

[7] SOUVIK S，ROMIT R C，SRIHARI N.SpinLoc：Spin once to Know Your Location[EB/OL].[2014-08-02].http：//www.cse.sc.edu/～srihari/pubs/SpinLoc_HotMobile12.pdf.

[8] XIAO Jiang，WU Kai-shun，YI You-wen，et al.Fimd：Fine-grained Device-free Motion Detection[C]//Proceedings of the 18th IEEE International Conference on Parallel and Distributed Systems.Singapore：IEEE，2012：229-235.

[9] BAHL P，PADMANABHAN V N.Radar：an In-building RF-based User Location and Tracking System[C]//Proceedings of 19th Annual Joint Conference of the IEEE Computer and Communications Societies.Tel Aviv：IEEE，2000：775-784.

[10] SUNGWON Y，DESSAI P，VERMA M，et al.FreeLoc：Calibration-free Crowdsourced Indoor Localization[C]//Proceedings of the 32nd IEEE International Conference on Computer Communications.Turin：IEEE，2013：2481-2489.

[11] DANIEL H，HU Wen-jun，ANMOL S.Tool Release：Gathering 802.11n Traces with Channel State Information[C]//Proceedings of the ACM SIGCOMM Computer Communication Review.New York：ACM，2011：53-53.