宋陽光，殷鋒，袁平

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

0 引言

近年來，隨著無線通信技術(shù)的發(fā)展以及移動終端設(shè)備性能的不斷增強(qiáng)，用戶對于基于位置服務(wù)（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技術(shù)實(shí)現(xiàn)室內(nèi)定位具有積極的社會意義。

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

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

1 理論基礎(chǔ)

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

圖1 三邊定位

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

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

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

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

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

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

2 算法實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

2.2 相似度匹配算法

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

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

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

3 算法驗(yàn)證與實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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