改進(jìn)的WKNN算法研究*

徐錦修，仲 臣，韓雨辰，劉清華

（安徽理工大學(xué) 空間信息與測繪工程學(xué)院，安徽 淮南232001）

隨著社會信息化、科技化，美國的GPS，中國的BDS等室外定位導(dǎo)航系統(tǒng)已經(jīng)取得了顯著進(jìn)展，技術(shù)也比較成熟。研究表明，人們有超過80%的時間在室內(nèi)活動，并且最近市場對大型室內(nèi)環(huán)境特定的位置感知內(nèi)容的興趣有所增加，例如大型購物中心，博物館，展覽中心以及機(jī)場等大型公共場所，人們對室內(nèi)定位技術(shù)產(chǎn)生了濃厚的興趣，對于提供精確的室內(nèi)位置信息將對生產(chǎn)生活產(chǎn)生重要的意義。在室內(nèi)環(huán)境下，衛(wèi)星信號是無法穿透墻體的，GNSS技術(shù)也沒有辦法在室內(nèi)進(jìn)行定位，由此看來，室內(nèi)現(xiàn)在已經(jīng)成為了衛(wèi)星定位系統(tǒng)的盲區(qū)。因此，室內(nèi)定位技術(shù)的研究和發(fā)展已經(jīng)變得尤為重要。我國現(xiàn)階段應(yīng)用比較多的定位技術(shù)主要有藍(lán)牙定位、慣性導(dǎo)航、WiFi定位、地磁定位等。藍(lán)牙室內(nèi)定位技術(shù)的原理是通過采集信號強(qiáng)度來定位。藍(lán)牙具有存在體積小，低功耗并且容易部署的優(yōu)點，但是又存在通信距離短，受噪聲的干擾較大以及信號穩(wěn)定性不好的限制[1]。慣性導(dǎo)航的定位原理是通過慣性傳感器獲取的定位目標(biāo)的加速度，角速度等運(yùn)動狀態(tài)數(shù)據(jù)，推算出目標(biāo)的運(yùn)動軌跡[2]。其中，因為WiFi網(wǎng)布置簡單，價格也比較低廉，并且廣泛應(yīng)用在室內(nèi)環(huán)境中，現(xiàn)在已經(jīng)成為一種普遍適用的定位方法。目前室內(nèi)定位導(dǎo)航系統(tǒng)基本上是通過臨近探測、指紋、多邊定位或三角定位法來實現(xiàn)。

本文主要講述的是目前國內(nèi)外室內(nèi)定位的現(xiàn)狀，其次介紹了目前我國使用較為廣泛的KNN、WKNN算法，并將其與改進(jìn)的WKNN算法進(jìn)行比較，其中，改進(jìn)的WKNN算法也是本文的重點。

1 室內(nèi)定位國內(nèi)外現(xiàn)狀

在文獻(xiàn)[3]中，張媛等人分別對最小均方差估計算法，指紋估計算法及加權(quán)質(zhì)心估計算法進(jìn)行視距、非視距場景分析，并在此基礎(chǔ)上建立了更高精度的測距模型，將基于UWB的指紋估計算法引入室內(nèi)定位。在文獻(xiàn)[4]中，陳良等人提出了一種優(yōu)化人工神經(jīng)網(wǎng)絡(luò)的方法，即粒子群優(yōu)化算法，用此算法來解決射頻識別汽車室內(nèi)定位在復(fù)雜環(huán)境下無法建立信號強(qiáng)度值和傳播距離之間的映射模型問題。使用粒子群優(yōu)化算法可以有效避免人工神經(jīng)網(wǎng)絡(luò)陷入局部最優(yōu)等缺陷，建立一個準(zhǔn)確的RSSI和標(biāo)簽位置的分類模型。在文獻(xiàn)[5]中，單超穎等人針對神經(jīng)網(wǎng)絡(luò)參數(shù)不準(zhǔn)確、室內(nèi)環(huán)境復(fù)雜多變、無線信號的時變性以及支持向量機(jī)的定位性能不高等問題，提出了依據(jù)和聲搜索算法對RBF神經(jīng)網(wǎng)絡(luò)進(jìn)行優(yōu)化的無線網(wǎng)絡(luò)室內(nèi)定位系統(tǒng)，可以有效提高室內(nèi)定位的準(zhǔn)確性。在文獻(xiàn)[6]中，蔡金洋等人設(shè)計的基于擴(kuò)展卡爾曼濾波的WiFi/PDR融合室內(nèi)定位系統(tǒng)有效降低了室內(nèi)定位的成本，提高了室內(nèi)定位的精度，此方法的創(chuàng)新點在于對不易測量的噪聲參數(shù)的自適應(yīng)處理。在文獻(xiàn)[7]中，徐德昌等人提出的基于螢火蟲散發(fā)優(yōu)化粒子濾波的行人航位推算融合地磁匹配的室內(nèi)定位方法相較于傳統(tǒng)的PDR算法，大大降低了計算量，更重要的是此方法有效提高了定位精度。

2 鄰近算法介紹

2.1 KNN算法

K近鄰算法是近鄰算法的發(fā)展和延伸[8]，為了改進(jìn)NN算法中確定定位目標(biāo)位置方法的缺陷，KNN算法利用公式（1）計算出定位目標(biāo)與各個參考點之間的指紋相似度，并將其值按照升序排列。

定位目標(biāo)的K個最近鄰參考點應(yīng)選取前K（K≥2）個值對應(yīng)的參考點，將這K個參考點所對應(yīng)的坐標(biāo)取平均值，進(jìn)而估算出目標(biāo)點的大約位置。

假設(shè)距離目標(biāo)點最近的K個參考點的集合為{B1，B2，…，BK}，這K個參考點對應(yīng)的坐標(biāo)分別為：

那么目標(biāo)點的位置就可以根據(jù)公式（2）計算得到：

其中，（xi，yi）表示選取的K個近鄰參考點中的第i個參考點的坐標(biāo)。KNN算法相較于NN算法而言，它選用了更多的近鄰參考點來確定目標(biāo)點的位置，因而大大降低了定位的誤差。通過使用該算法可以提高定位精度，降低室內(nèi)定位技術(shù)功耗，而且不增加額外成本。盡管如此，目前KNN算法仍然面臨著嚴(yán)峻的挑戰(zhàn)[9]：

（1）空間歧義性：與當(dāng)前位置相比，某些物理上遙遠(yuǎn)的位置可能具有相似的指紋或者相似的指紋距離，這可能會使KNN算法產(chǎn)生更大的誤差。

（2）RSS不穩(wěn)定性：運(yùn)動的物體、周圍的環(huán)境產(chǎn)生的電磁波不斷變化，天線的方向性和射頻干擾等，都會導(dǎo)致WiFi信號的大幅波動。因此在測試階段采集到的某個位置的指紋可能與訓(xùn)練階段收集到的指紋不匹配。

2.2 WKNN算法

WKNN算法對KNN算法進(jìn)行了改進(jìn)，在其基礎(chǔ)上引入了權(quán)重的概念。由于WiFi的信號強(qiáng)度是隨著距離增加而逐漸減小的，所以待測目標(biāo)點與參考點之間的距離越大，參考點的信號波動就越強(qiáng)烈，對定位的作用就越小[10]。因此WKNN算法按照一定的規(guī)則對不同近鄰參考點選取不同的權(quán)重來體現(xiàn)對定位作用的影響大小，近鄰參考點與目標(biāo)點的距離越近，那么它的權(quán)重就會越大，反之，則權(quán)重越小。離線階段與在現(xiàn)階段的定位如圖1所示。

圖1 位置指紋定位流程圖

用WKNN算法進(jìn)行定位，目標(biāo)點的坐標(biāo)可以根據(jù)公式（4）得到：

其中K表示的是最近鄰參考點的個數(shù)；（x^，y^）表示的是定位目標(biāo)的估計位置；ε是一個非零的數(shù)值較小的實數(shù)，它是用來避免出現(xiàn)ωi為0的現(xiàn)象，權(quán)重如公式（5）所示：

KNN算法和WKNN算法相較于NN算法在定位精度上均有所提升，但是選取的K值在多數(shù)情況下都是依靠經(jīng)驗判斷的，不同的K值對試驗的結(jié)果也會產(chǎn)生非常大的影響。而且KNN算法和WKNN算法在定位過程中計算量比較大，當(dāng)在大面積區(qū)域進(jìn)行定位時，定位結(jié)果顯示會有很大延遲。

WKNN算法相較于KNN算法，其根據(jù)的K個最近鄰參考點對定位的貢獻(xiàn)程度，分配不同的權(quán)重，從而大大提高了定位精度。

3 改進(jìn)的WKNN算法介紹

下面介紹的基于方差修正的WKNN算法可以減少上述的錯誤信號強(qiáng)度值對整體指紋距離的影響。用修正權(quán)重值di來表示每項實測值與存儲值的差異量，大幅度修正信號強(qiáng)度值誤差較大的，信號強(qiáng)度值誤差較小的只需要進(jìn)行小幅度的修正，具體的表達(dá)式見式（6）：

式中：D（j）-待測點相對于第j個離線參考點的位置；ri-定位階段在待測點測得的第i個AP信號強(qiáng)度值；sij-離線階段在第j個位置參考點測得并儲存在指紋庫里的第i個AP信號強(qiáng)度值。

由文獻(xiàn)[12-13]可知，測得的某個AP信號強(qiáng)度值的均值Mean和方差Var存在著線性關(guān)系，如式（7）所示：

式中，將離線階段該AP在全部參考位置點所測得的信號強(qiáng)度值，進(jìn)行線性回歸確定參數(shù)m和n的數(shù)值。

參考文獻(xiàn)[12-13]可知，方差會隨著信號強(qiáng)度的均值增大而減小，且該值的準(zhǔn)確率也會隨之提高。所以在參數(shù)m和n確定之后，可以將定位階段中測得的每個AP信號強(qiáng)度值作為均值，也可以通過這個均值預(yù)估出所測得的信號強(qiáng)度的方差。最終結(jié)果會隨著測量值的方差增大而減小，相應(yīng)的測量值可信度也會隨之降低。所以基本的修正權(quán)重可以用方差的倒數(shù)來表示。為了使得指紋距離D（j）中的權(quán)重值di之和為1，需要將權(quán)重值di進(jìn)行標(biāo)準(zhǔn)化，公式參考式（8）：

經(jīng)過標(biāo)準(zhǔn)化之后通過指紋距離D（j）的大小篩選出K個近鄰點。某一參考點的權(quán)重值是：該點指紋距離的倒數(shù)與K個近鄰點指紋距離的倒數(shù)之和作比值，得到的結(jié)果即為該參考點的權(quán)重值，即

最后，將所求得的K個近鄰點的坐標(biāo)加權(quán)平均作為最終的定位結(jié)果。

4 實驗與結(jié)論

將安徽理工大學(xué)義苑四號樓研究生公寓B區(qū)一層作為此次實驗區(qū)域，該定位區(qū)域面積約為70m×20m的室內(nèi)空間，公寓內(nèi)有隔墻、桌椅以及走動的人員等干擾因素。此樓層設(shè)置20個采用TP-Link TL-WR840N型號熱點的AP信號點。

首先把每個房間作為一個參考點，在每個參考點采集WiFi信號強(qiáng)度值，將每個信號強(qiáng)度值與對應(yīng)坐標(biāo)存入位置指紋數(shù)據(jù)庫；其次在20個信號點中隨機(jī)選取12個點作為測試點，記錄每個點的實際坐標(biāo)與各測試點的信號強(qiáng)度值；再采用KNN算法、WKNN算法以及基于方差修正的WKNN算法進(jìn)行定位實驗，將3種算法的定位誤差取平均值進(jìn)行比較，根據(jù)采集到的數(shù)據(jù)得到KNN、WKNN以及改進(jìn)的WKNN算法對平均定位誤差的影響，如圖2所示。

圖2 定位誤差對比

通過圖2的對比數(shù)據(jù)可以得到3種算法的平均誤差，結(jié)果如表1所示：

表1 3種算法的平均定位誤差比較

通過圖2可以看出，改進(jìn)的WKNN算法的誤差在7m左右基本沒有太大變化，WKNN算法的誤差9m以后沒有明顯變化，而KNN算法10m以前誤差仍然比較明顯。再結(jié)合表1，WKNN算法比KNN算法提升了18.48%，而改進(jìn)的WKNN算法比WKNN算法提升了20.10%。對比圖2和表1，改進(jìn)的WKNN算法的平均誤差明顯得到了改善，因此改進(jìn)的WKNN算法有效提高了定位精度。

5 結(jié)束語

當(dāng)今社會互聯(lián)網(wǎng)與通信技術(shù)不斷提高，僅在室外進(jìn)行定位已經(jīng)滿足不了人們?nèi)粘５纳钚枨螅虼耸覂?nèi)定位技術(shù)由此出現(xiàn)并得到了迅速發(fā)展，并且室內(nèi)定位技術(shù)極大提高了人們生活的便利性。本文主要講解了KNN、WKNN算法的原理，分析了目前此方法存在的不足之處，并提出了改進(jìn)的WKNN算法來彌補(bǔ)它們的不足之處，通過實驗表明，改進(jìn)的WKNN算法的平均定位誤差比KNN和WKNN明顯改善，因此改進(jìn)的WKNN算法提高了定位精度。美中不足的是改進(jìn)的WKNN算法的花費(fèi)比較大，之后的研究要著重注意成本的問題。