基于四叉樹的WiFi室內(nèi)定位算法研究*

（61773部隊 烏魯木齊 831400）

1 引言

無線通信和移動智能設備的激增推動了基于的位置服務和需求不斷增長，相比于室外定位，室內(nèi)定位技術可能更能改變?nèi)祟愋袨椋凰窃S多潛在實際應用的推動者，例如建筑物內(nèi)的室內(nèi)導航，智能圖書館或可輕松定位物體的智能工作場所等。雖然諸如GPS、GLONASS、北斗等基于空間衛(wèi)星的導航定位系統(tǒng)在室外提供高的定位系統(tǒng)，但是來自衛(wèi)星的GNSS信號在許多室內(nèi)區(qū)域并不總是可以接受的，這限制了它們的使用［1～2］。WIFI系統(tǒng)已被廣泛應用于室內(nèi)環(huán)境，WIFI提供對固定網(wǎng)路的本地無線接入，固定網(wǎng)絡成本低、部署廣泛，并且其室內(nèi)覆蓋仍然快速增加，使用現(xiàn)有的基礎設施進行定位是非常有吸引力的選擇。

使用WIFI信號定位的技術主要分為兩類，第一類技術要求在系統(tǒng)定位之前離線收集標記數(shù)據(jù)的映射，這主要涉及構建WIFI的RSSI指紋識別環(huán)境的無線電地圖；第二類依賴于數(shù)學建模方法來確定設備位置，如最典型的三邊測量就是通過測量用戶與各個參考點位置的距離來確定用戶的位置，而基于WIFI信號強度RSSI的指紋識別方法一直是近十年研究的熱點，因為不需要接入點的視線測量也不需要角度測量，位置的特征在于其檢測到的信號模式，因此在復雜的室內(nèi)環(huán)境中實現(xiàn)了高適用性。

傳統(tǒng)的KNN算法在計算過程中由于要遍歷所有數(shù)據(jù)，所以存在運算量大，噪聲影響大等缺點［3］。本文將四叉樹RSS算法應用于室內(nèi)WiFi定位中并進行算法改進，解決了在四叉樹分割期間，相同的地理實體最有可能存儲在多個節(jié)點中導致浪費索引存儲空間。同時地理空間物體的分布可能不均衡導致傳統(tǒng)的四叉樹生成非常不平衡的樹，樹結構的不平衡，浪費存儲空間。通過Matlab仿真驗證，與傳統(tǒng)的遍歷算法與KD樹相比，改進的四叉樹算法的精確度明顯更高，速度也更快。

2 WiFi室內(nèi)定位技術

基于WiFi技術的室內(nèi)定位技術，可實現(xiàn)無線局域網(wǎng)（WLAN）的實時定位。它結合了WLAN和實時定位技術，在室內(nèi)空間實現(xiàn)復雜的人員定位，監(jiān)控和跟蹤任務。并準確地找到目標。

2.1 指紋定位

“指紋定位”將實際環(huán)境中的位置與指紋數(shù)據(jù)庫（FP）相關聯(lián)，指紋數(shù)據(jù)庫是對應唯一指紋的特殊位置。指紋可以是一維的或多維的。位置指紋可以是多種類型，并且任何“獨特位置”特征可以用作位置指紋。對于某個位置的通信信號的多徑結構，可以在某個位置檢測到接入點或基站，從某個位置檢測到的基站信號中接收RSS（信號強度），以及在某個位置進行溝通。這些都可以用作位置指紋，或者它們可以組合成指紋。

RSS或信號的接收功率取決于接收器的位置。RSS很容易獲得，因為大多數(shù)無線通信設備需要它才能正常運行。許多通信系統(tǒng)需要RSS信息來感知鏈路的質量，實現(xiàn)切換并適應傳輸速率。因此，RSS是一種非常流行的信號特性并廣泛應用于定位。

假設有一個固定的信號源，在其距離平均不同的距離上，RSS衰減與對數(shù)和距離的平方成正比，在最簡單的情況下，RSS可表示為

α被稱為路徑損耗指數(shù)，Pt是發(fā)射功率，K是一個取決于環(huán)境和頻率的常數(shù)。RSS可用于計算移動設備與AP（基站）之間的距離。雖然提取的距離可用于測量移動設備的三個角來定位，但是由于陰影衰落引起RSS強度變化造成定位較大誤差。因此，這種基于RSS的三邊測距方法并不是一個好的解決方案［5］。

大多數(shù)WiFi網(wǎng)卡可以測量來自多個AP的RSS，可以使用多個接收器的RSS來組成RSS向量作為與位置相關聯(lián)的指紋。

2.2 指紋定位過程

Wi-Fi指紋定位通常分兩個階段進行：離線數(shù)據(jù)采集階段和在線定位階段，在圖1中，我們展示了它的基本操作。在離線階段，進行現(xiàn)場勘測以收集來自已知位置的參考點（RP）處的不同接入點（AP）的所有檢測到的Wi-Fi信號的接收信號強度指示符（RSSI）的矢量，以此類推，直到所有的參考點的數(shù)據(jù)都被記錄到數(shù)據(jù)庫中。所有RSSI向量形成站點的指紋并存儲在數(shù)據(jù)庫中以進行在線查詢。

圖1 指紋的建立

在線定位階段，用戶在他/她的位置采樣或測量RSSI向量并將其報告給服務器［6］。使用信號空間中的一些相似性度量（例如歐幾里德距離），服務器將接收的目標矢量與存儲的指紋數(shù)據(jù)庫進行比較，選擇最相似的“鄰居”作為估計目標位置，其中指紋是與目標的RSSI緊密匹配的參考點的集合。

之后的在線階段系統(tǒng)中，將定位移動設備的位置。移動設備位于此地理區(qū)域，但確切位置未知。它甚至不可能處于網(wǎng)格點。假設移動設備測量來自各種AP的RSS。假設只測量一個樣本，并且從每個AP測量RSS，RSS矢量的值被傳輸?shù)骄W(wǎng)絡。在圖1的示例中，RSS向量是r=［r1，r2］［7］。為了確定移動設備的位置，找到與指紋數(shù)據(jù)庫中的r最佳匹配指紋，則估計移動設備的位置是最佳匹配指紋的位置。隨著待定區(qū)域變大，離線指紋數(shù)據(jù)庫將獲得更多數(shù)據(jù)，這意味著在線計算需要更多的時間和來源，使用數(shù)據(jù)挖掘算法可以大大加快計算速度，提高定位精度。

3 四叉樹

3.1 傳統(tǒng)四叉樹

KD樹僅支持一維數(shù)據(jù)，對于標量值，它不能應用于地圖上有關x和y方向信息的位置。四叉樹（Q-tree）是樹數(shù)據(jù)結構，它每個節(jié)點下最多可以有四個子節(jié)點，通常將二維空間的一部分劃分為四個象限或區(qū)域，并將相關信息存儲在四叉樹節(jié)點中。該區(qū)域可以是正方形，矩形或任何形狀。如圖2中四叉樹的二維空間結構（左）和存儲結構（右）。因此四叉樹在數(shù)據(jù)挖掘中具有重要意義［8～9］。

四叉樹的每個節(jié)點代表一個矩形區(qū)域，如圖2黑色根節(jié)點上方的圖片代表最外圍的黑色邊框矩形，每個矩形區(qū)域可以分為四個小矩形區(qū)域，四個小矩形區(qū)域作為四個子節(jié)點代表一個矩形區(qū)域。

圖2 四叉樹的二維空間結構和存儲結構

通過使用四叉樹分割網(wǎng)格，我們可以建立一個完整的四叉樹如圖3所示，假設矩形區(qū)域中有N個對象，一個黑點代表一個對象，每個對象坐標都是已知的。使用存儲對象的四叉樹節(jié)點構建四叉樹，將所有黑點插入四叉樹［11～12］。

圖3 建立四叉樹

與二叉樹類似，使用盲搜索通過以下順序遍歷或逆序遍歷搜索某個對象，時間復雜度為O（N）。基于區(qū)域中對象的位置的研究，時間復雜度對應于四叉樹的深度。與盲搜索相比，搜索區(qū)域的對象越多，效果越好。

3.2 優(yōu)化四叉樹

四叉樹對區(qū)域查詢更有效。但如果空間物體的分布不均勻，隨著地理空間物體的不斷插入，四叉樹的水平將不斷加深，形成嚴重的不平衡四叉樹。根據(jù)每次增加的查詢深度，它將導致查詢效率急劇下降。

將地理實體信息存儲在最小矩形節(jié)點中，而不是存儲在其父節(jié)點中。每個地理實體僅在樹中存儲一次，以避免浪費存儲空間。首先生成一個完整的四叉樹，避免在插入地理實體時重新分配內(nèi)存。加快插入速度，最后釋放空節(jié)點的內(nèi)存空間。四叉樹的深度通常在4～7之間最佳［13］。

四叉樹面臨邊界點問題，節(jié)點中的每個點必須相鄰，但相鄰點不一定在同一節(jié)點中。如圖4所示，點A和點B非常靠近。如果A點是我們查詢的點，則僅提取節(jié)點A中的所有位置是不夠的。它還需要找到它的鄰居節(jié)點。

圖4 邊界點問題圖

與傳統(tǒng)的窮舉算法和KD樹相比，四叉樹是一種更好的室內(nèi)定位算法，能夠在速度和準確性方面有更好的表現(xiàn)［14］。與傳統(tǒng)算法不同，它有兩個階段。在離線階段，離線FP數(shù)據(jù)庫將無線電地圖保存為2*2，4*4，8*8，… 2n*2n網(wǎng)格。而在線階段計算歐幾里德距離與離線數(shù)據(jù)庫進行比較，可以減少大量計算，加快在線定位，其準確性優(yōu)于一般算法。四叉樹算法定位示意圖如圖5所示。但是，四叉樹算法存在一個很大的問題。如果估計位置劃分為錯誤區(qū)域，則不再進行校正。它可能會導致邊界上的錯誤率非常高，我們必須調整劃分區(qū)域的方法，以降低邊界上的定位錯誤率。同時，四叉樹算法無法找到分裂可以適當停止的時刻，甚至不正確的網(wǎng)格可能會被拆分。因此，需要修改四叉樹算法。本文算法可以提供一種新的基于多元邏輯回歸的算法，具有更高的可靠性和準確性。

圖5 四叉樹算法定位示意圖

在離線階段中，主要任務與前一階段相同。我們需要重新劃分區(qū)域并更正分類，特別是在邊界上，這是值得的。根據(jù)新的分區(qū)定義離線無線電地圖（RM）定義為 2×2，4×4，8×8…2n×2n的正方形。無線電地圖應以四叉樹的形式存儲（Φ）。定位的區(qū)域分為四個子集群，每個子集代表存儲在四叉樹中的子節(jié)點。對于每個FP的子節(jié)點是向量un(n=1，2，3，4)。 Γ ( )tλk表示是否可以拆分當前群集。

在線階段中，定位過程被認為是基于四叉樹的搜索問題。搜索過程描述如表1。

表1 改進四叉樹搜索流程

4 仿真計算及結果分析

在本文中采用Matlab軟件和使用實測數(shù)據(jù)對以上算法進行仿真與驗證，設置8 AP并在16×16網(wǎng)格中選擇隨機4 AP，并與傳統(tǒng)窮舉算法、KD樹算法進行對比研究。

4.1 Matlab仿真分析

采用Matlab仿真后的結果曲線如圖6所示。

使用窮舉算法，KD樹和改進四叉樹的累積分布函數(shù)定位誤差曲線如圖6a所示。

圖6 Matlab仿真結果

縱坐標表示從0%～100%精確定位的概率，而橫坐標表示定位誤差值從0～10m的距離。紅線表示傳統(tǒng)的窮舉算法，綠線表示KD樹，藍線表示改進四叉樹。我們可以看到，這三條曲線是絕對收斂的。但收斂速度不同，改進四叉樹速度最快，窮舉算法最慢。值得注意的是，KD樹的曲線比其他兩種算法更平滑。原因可能是KD樹分類算法的隨機性大于其他兩種算法。改進四叉樹已成功定位，定位率達到100%，定位誤差為4m，而KD樹需要6m定位誤差才能達到同樣的效果。傳統(tǒng)的窮舉算法甚至需要10m的定位誤差。曲線所包圍的區(qū)域越大，定位效果越好。結果表明，使用改進四叉樹算法，位置精度明顯優(yōu)于其他方法。

4.2 實測數(shù)據(jù)驗證

通過用測量數(shù)據(jù)替換模擬數(shù)據(jù)來進行實驗，實驗結果如圖7所示。雖然存在信號噪聲和干擾，但實驗結果仍具有代表性。如圖7（a）所示，三條曲線的收斂速度較慢。這意味著在實際的室內(nèi)定位中，位置的準確性較低，但是改進四叉樹算法仍然比其他兩種算法具有更好的準確性。改進四叉樹成功定位率達到100%，定位誤差為6m。

類似地，隨著計算量的增加，實際的室內(nèi)定位變得越來越大，傳統(tǒng)的窮舉算法仍然需要大量的計算，如圖7（b）所示。當要定位的區(qū)域變得足夠大時需要很多時間。改進四叉樹的性能仍然穩(wěn)定，藍色曲線的上升趨勢保持平穩(wěn)，這意味著改進四叉樹比其他兩種算法使用更少的時間來完成定位。值得注意的是，曲線不如模擬結果穩(wěn)定。原因可能是數(shù)據(jù)收集過程中的錯誤數(shù)據(jù)，但曲線趨勢仍然合理。錯誤數(shù)據(jù)的原因可能是實驗室里走動的人，或者其他人產(chǎn)生的未知WiFi信號，例如有人打開手機熱點。

圖7 實測數(shù)據(jù)驗證結果

5 結語

本文在依據(jù)聚類和分類理論實現(xiàn)室內(nèi)WiFi定位中提出一種基于改進四叉樹RSS定位算法。通過采用傳統(tǒng)窮舉算法、KD樹等傳統(tǒng)算法進行對比，采用Matlab仿真和采集的數(shù)據(jù)進行實測實驗，實驗結果表明，與傳統(tǒng)方法相比基于改進四叉樹RSS定位算法在WiFi室內(nèi)定位中可以提高室內(nèi)定位的準確性，有效地解決邊界條件問題，提高了定位效果，同時可以節(jié)省大量的在線計算時間，加快定位速度，在實際應用中具有重要意義。