（61773部隊(duì) 烏魯木齊 831400）

1 引言

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

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

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

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

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

2.1 指紋定位

“指紋定位”將實(shí)際環(huán)境中的位置與指紋數(shù)據(jù)庫(kù)（FP）相關(guān)聯(lián)，指紋數(shù)據(jù)庫(kù)是對(duì)應(yīng)唯一指紋的特殊位置。指紋可以是一維的或多維的。位置指紋可以是多種類(lèi)型，并且任何“獨(dú)特位置”特征可以用作位置指紋。對(duì)于某個(gè)位置的通信信號(hào)的多徑結(jié)構(gòu)，可以在某個(gè)位置檢測(cè)到接入點(diǎn)或基站，從某個(gè)位置檢測(cè)到的基站信號(hào)中接收RSS（信號(hào)強(qiáng)度），以及在某個(gè)位置進(jìn)行溝通。這些都可以用作位置指紋，或者它們可以組合成指紋。

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

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

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

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

2.2 指紋定位過(guò)程

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

圖1 指紋的建立

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

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

3 四叉樹(shù)

3.1 傳統(tǒng)四叉樹(shù)

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

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

圖2 四叉樹(shù)的二維空間結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)

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

圖3 建立四叉樹(shù)

與二叉樹(shù)類(lèi)似，使用盲搜索通過(guò)以下順序遍歷或逆序遍歷搜索某個(gè)對(duì)象，時(shí)間復(fù)雜度為O（N）?；趨^(qū)域中對(duì)象的位置的研究，時(shí)間復(fù)雜度對(duì)應(yīng)于四叉樹(shù)的深度。與盲搜索相比，搜索區(qū)域的對(duì)象越多，效果越好。

3.2 優(yōu)化四叉樹(shù)

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

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

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

圖4 邊界點(diǎn)問(wèn)題圖

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

圖5 四叉樹(shù)算法定位示意圖

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

在線階段中，定位過(guò)程被認(rèn)為是基于四叉樹(shù)的搜索問(wèn)題。搜索過(guò)程描述如表1。

表1 改進(jìn)四叉樹(shù)搜索流程

4 仿真計(jì)算及結(jié)果分析

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

4.1 Matlab仿真分析

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

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

圖6 Matlab仿真結(jié)果

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

4.2 實(shí)測(cè)數(shù)據(jù)驗(yàn)證

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

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

圖7 實(shí)測(cè)數(shù)據(jù)驗(yàn)證結(jié)果

5 結(jié)語(yǔ)

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