基于CSI的區(qū)域粒子化的室內(nèi)定位算法的研究

宋陽光，殷鋒，袁平

（1.四川大學計算機學院，成都610065；2.西南大學計算機科學與技術學院，成都610041；3.重慶大學數(shù)學與信息工程學院，重慶400044）

0 引言

近年來，隨著無線通信技術的發(fā)展以及移動終端設備性能的不斷增強，用戶對于基于位置服務（Location Based Service，LBS）的需求越來越高?，F(xiàn)在的定位主要分為室外定位和室內(nèi)定位。傳統(tǒng)的室外定位系統(tǒng)是衛(wèi)星定位系統(tǒng)，如全球定位系統(tǒng)（Global Positioning System，GPS）[1]、北斗定位系統(tǒng)。但是對于室內(nèi)定位來說，由于建筑物密集。遮擋物較多等因素，GPS衛(wèi)星定位并不能發(fā)揮其作用。因此，利用成本低且使用廣泛的Wi-Fi技術實現(xiàn)室內(nèi)定位具有積極的社會意義。

傳統(tǒng)的室內(nèi)定位技術是基于RSSI的三邊室內(nèi)定位算法[2]，但是這種室內(nèi)定位算法理論上是可行的，但是在實際的應用中，由于測距存在誤差，很難建立準確的、低損耗的定位系統(tǒng)[3]。而且，在實際情況下，三圓交于一點的情況很難存在。因此，三邊定位算法在實際的實施過程中存在很大的問題。

因此，在本文中，我們提出了基于CSI的區(qū)域離子化的室內(nèi)定位算法。首先，我們使用Wi-Fi信號的信道狀態(tài)信息CSI來計算定位區(qū)域，這樣克服了RSSI在復雜室內(nèi)環(huán)境下狀態(tài)不穩(wěn)定的缺點。然后我們將定位區(qū)域進行粒子化，縮小定位區(qū)域，并利用余弦相似度公式得到定位坐標。通過我們最后的實驗驗證，我們的定位系統(tǒng)達到了分米級的定位精度，與傳統(tǒng)的三邊定位算法相比有了很大的提升。

1 理論基礎

在進行此算法實現(xiàn)之前，先說明一下其中的理論基礎。其中一個理論基礎來自于三邊測量法，其思想是通過三個信號接收器R1，R2，R3，接收通過目標P反射的信號信息，測量出目標P與各個接收器之間的距離d1，d2，d3。然后分別以這接收器R1，R2，R3為圓心，d1，d2，d3為半徑做出一個圓，則重疊區(qū)域即為目標P的位置坐標。如圖1所示。

圖1 三邊定位

另一個理論基礎來源于余弦相似度公式。即對于任意的兩個向量來說，可以通過它們之間夾角的余弦值來衡量兩個向量的相似度。兩個向量的余弦相似度公式為：

其中，A和B分別是兩個向量組，A=(A1，A2，A3，…，An)，B=(B1，B2，B3，…，Bn)。

我們假設有兩個節(jié)點R1和R2，以及三個已知節(jié)點A，B，C。R1相對于 A，B，C 的距離為D1A，D1B，D1C，R2相對于 A，B，C的距離為D2A，D2B，D2C。那么在本文中未知節(jié)點R的關系數(shù)組可表示為：

relation-array1(DiA，DiB，DiC)，（其中，i=1，2）

根據(jù)上面的關系數(shù)組公式，節(jié)點R1和R2的相關性可以用向量的余弦相似度公式求解，R1和R2的余弦相似度即關系系數(shù)可以表示為：

且該系數(shù)值越大，節(jié)點R1與節(jié)點R2位置就越相近。

2 算法實現(xiàn)

2.1 區(qū)域粒子化模型

區(qū)域粒子化模型的核心思想是對定位區(qū)域ABC進行劃分，縮小定位區(qū)域的面積。為了能夠?qū)χ丿B區(qū)域進行合理的劃分，可以將曲邊看成一條直線，重疊區(qū)域就近似成了△ABC，這樣對于重疊區(qū)域的質(zhì)心問題就可以轉(zhuǎn)化為求解三角形的質(zhì)心問題。根據(jù)三圓相交公式，我們可以得到交點 A，B，C的坐標A(xa，ya)，B(xb，yb)，A(xc，yc)。利用三角形質(zhì)心公式，求解得到三角形質(zhì)心坐標

過質(zhì)心點O分別連接A，B，C點，將區(qū)域ABC分割成三個面積相等的子區(qū)域，分別為AOB，AOC，BOC三個區(qū)域，然后對這三個區(qū)域分別求出每個區(qū)域的質(zhì)心Oi（i=1，2，3）坐標。轉(zhuǎn)化過程如圖 2（a）、2（b）和 2（c）。

圖2 定位區(qū)域轉(zhuǎn)化圖

三個子區(qū)域的質(zhì)心坐標分別為：

經(jīng)過上述的區(qū)域劃分過程，我們將定位區(qū)域通過質(zhì)心平分了三份。接下來，將平分得到的子區(qū)域再按照同樣的方式進行粒子化劃分，將定位區(qū)域不斷縮小，并求出每個區(qū)域?qū)馁|(zhì)心坐標。最后，我們能夠得到一個定位區(qū)域的粒子區(qū)域的質(zhì)心分布圖，區(qū)域粒子化模型如圖 3（a）和 3（b）：

圖3 區(qū)域粒子化模型

根據(jù)三角形質(zhì)心公式我們可以得到粒子區(qū)域的質(zhì)心 坐 標Oi(xOi，yOi)。 我 們 可 以 根 據(jù) 公 式得到粒子區(qū)域的質(zhì)心坐標與Wi-Fi信號接收器之間的距離dij。其中，i∈[1，2，3，4…]，j?[1，2，3]。由此可知，可以根據(jù)質(zhì)心各個粒子區(qū)域的質(zhì)心坐標建立質(zhì)心的關系矩陣：

（di1，di2，di3）n×3其中i?(1，2，3…n)

對于未知節(jié)點P來說，雖然說其是未知的，但是，通過接收端AP1，AP2，AP3可以獲取節(jié)點P的信號，并且可以根據(jù)以下的信號衰減公式獲取得到P點信號強度：

Pri=Pt-10γlogdi其中 i=1，2，3

其中，Pt表示W(wǎng)i-Fi信號發(fā)射端與接收端相距1m的信號強度，Pri表示W(wǎng)i-Fi信號接收器i接收到的信號強度，γ表示W(wǎng)i-Fi信號傳播環(huán)境的路徑損耗系數(shù)。

2.2 相似度匹配算法

根據(jù)我們已經(jīng)得出的P點的關系數(shù)組，使用余弦相似度公式計算P點的關系數(shù)組與粒子區(qū)域質(zhì)心點的關系數(shù)組的關系系數(shù)。重疊區(qū)域ABC經(jīng)過區(qū)域粒子化過程，得到的子區(qū)域面積相對較小，在該區(qū)域任意位置接收到的信號所受到的干擾可以看成是相同的，那么本文認為信號衰減模型公式表示的未知節(jié)點P與AP節(jié)點的距離與子區(qū)域質(zhì)心節(jié)點與AP的距離的相關性是合理的。那么根據(jù)公式（1）和三圓相交的圓心方程，P的關系數(shù)組與子區(qū)域質(zhì)心點的關系系數(shù)可以表示為：

其中 i=1，2，3，…，dia表示第 i個質(zhì)心點與接收器 a之間的距離。

未知節(jié)點P與粒子區(qū)域質(zhì)心點的關系系數(shù)越大，它們的位置就越接近。由于我們將重疊區(qū)域ABC經(jīng)過區(qū)域粒子化后，每一個粒子區(qū)域面積很小，可近似將粒子區(qū)域中的質(zhì)心信息看作此粒子區(qū)域的信號信息。則未知節(jié)點P在關系系數(shù)最大的質(zhì)心點對應的區(qū)域中，質(zhì)心點位置可以近似為P的位置。綜上，利用CSI的區(qū)域粒子化，可將重疊區(qū)域面積逐漸縮小，并通過余弦相似度估計未知節(jié)點P的坐標（xoi，yoi）。

3 算法驗證與實驗分析

為了能夠?qū)Ρ疚奶岢龅膮^(qū)域粒子化的室內(nèi)定位算法進行評估，本文選用了一個20m×15m的教室作為實驗環(huán)境來獲取CSI數(shù)據(jù)。在教室內(nèi)放置一個普通的商用Wi-Fi設備作為信號發(fā)射器，我們采用ThinkPad X40，配備便宜的現(xiàn)成的Intel 5300 Wi-Fi卡作為信號的接收器，接收器由一組3根接收天線組成，分別分布在教室內(nèi)不同的位置來獲取Wi-Fi信號。并且，我們將Halperin開發(fā)的CSI工具[4]安裝到我們的實驗電腦上，以收集每個接收器接收到的數(shù)據(jù)包的CSI樣本。圖4顯示了實驗環(huán)境的設置。

圖4 實驗環(huán)境

在圖4中，AP是商用路由器，用于發(fā)射Wi-Fi信號，Rx是三根信號接收器，分別放置于室內(nèi)不同的位置，P是室內(nèi)的待定位的運動的人。我們實驗中CSI的采樣率設置為200Hz，以確保人體運動引起的所有多普勒率都能夠被檢測到，因為室內(nèi)環(huán)境中的人體速度通常小于3m/s[5]。為了避免干擾，我們的實驗是帶寬20MHz的未使用的5GHz頻段內(nèi)進行的。

在實驗中，我們?yōu)榱四軌蚋玫赜嬎愠霰疚奶岢龅氖覂?nèi)定位算法的精確度，我們在實驗環(huán)境中安裝了一個攝像機用于記錄人的行走時間與位置的對應關系。然后我們讓5名志愿者在不同的時間段，沿著不同的運動軌跡進行運動，例如直線、矩形、圓形等。然后我們?yōu)槊恳粋€志愿者收集270個運動數(shù)據(jù)，并報告行人的實時的定位數(shù)據(jù)以及定位誤差。圖5（a）和5（b）是系統(tǒng)定位結(jié)果的例子。

在上述的兩幅圖中，紅色點是攝像機拍攝到的定位的位置，即為行人的實際的運動位置，而黑色的點是系統(tǒng)采集CSI數(shù)據(jù)，并計算得出的定位位置。通過觀察我們可以發(fā)現(xiàn)，本文的算法系統(tǒng)對于行人的室內(nèi)定位存在一定的誤差，通過對5名志愿者進行三周的實驗數(shù)據(jù)采集，我們得出了區(qū)域離子化的室內(nèi)定位算法平均誤差在0.85m，達到了亞米級的室內(nèi)定位精度，相比傳統(tǒng)的基于三邊定位原理的室內(nèi)定位算法有了很高的提升精度。

圖5 系統(tǒng)定位結(jié)果

為了獲得對于區(qū)域劃分度n以及粒子區(qū)域面積A與定位精度之間的關系，我們通過實驗，收集300個運動數(shù)據(jù)，計算并得出了定位重疊區(qū)域劃分度n與定位精度之間的關系以及劃分得到的粒子區(qū)域面積A與定位精度之間的關系。如圖6所示。

圖6 區(qū)域粒子化度與定位精度的關系

通過圖6和圖7可以觀察到，定位精度隨著定位重疊區(qū)域的劃分度的逐漸增加而增加，當劃分度n=4時，定位精度趨于穩(wěn)定。而且定位精度隨著粒子區(qū)域面積的減小而逐漸增加，當粒子區(qū)域面積接近0.1m2時，定位精度趨于穩(wěn)定。在第二節(jié)中我們已經(jīng)知道，粒子區(qū)域的劃分與質(zhì)心相關，劃分度每增加1，粒子區(qū)域就會劃分成3個面積相等的子區(qū)域。因此，我們可以得出這樣的結(jié)論，重疊的定位區(qū)域的粒子化的過程，將重疊區(qū)域不斷的劃分，直到將粒子區(qū)域面積劃分成接近0.1m2時。這樣，我們就可以降低系統(tǒng)復雜度，并獲取比較高的定位精度。

圖7 區(qū)域粒子化度與粒子區(qū)域面積的關系

4 結(jié)語

本文我們?yōu)槭覂?nèi)定位提出了一個新的室內(nèi)定位算法，稱為基于CSI的區(qū)域離子化的室內(nèi)定位算法。該算法是通過收集人體運動引起的CSI變化信息，計算出人的定位區(qū)域，然后將定位區(qū)域不斷的劃分，縮小定位區(qū)域面積，并利用余弦相似度匹配獲得更高的定位精度。與傳統(tǒng)的基于RSSI的三邊定位算法相比，不但更適用于復雜的室內(nèi)環(huán)境，而且在定位精度方面有了更高的提升。