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

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

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

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

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

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

2 鄰近算法介紹

2.1 KNN算法

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

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

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

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

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

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

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

2.2 WKNN算法

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

圖1 位置指紋定位流程圖

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

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

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

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

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

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

式中：D（j）-待測(cè)點(diǎn)相對(duì)于第j個(gè)離線參考點(diǎn)的位置；ri-定位階段在待測(cè)點(diǎn)測(cè)得的第i個(gè)AP信號(hào)強(qiáng)度值；sij-離線階段在第j個(gè)位置參考點(diǎn)測(cè)得并儲(chǔ)存在指紋庫(kù)里的第i個(gè)AP信號(hào)強(qiáng)度值。

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

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

參考文獻(xiàn)[12-13]可知，方差會(huì)隨著信號(hào)強(qiáng)度的均值增大而減小，且該值的準(zhǔn)確率也會(huì)隨之提高。所以在參數(shù)m和n確定之后，可以將定位階段中測(cè)得的每個(gè)AP信號(hào)強(qiáng)度值作為均值，也可以通過這個(gè)均值預(yù)估出所測(cè)得的信號(hào)強(qiáng)度的方差。最終結(jié)果會(huì)隨著測(cè)量值的方差增大而減小，相應(yīng)的測(cè)量值可信度也會(huì)隨之降低。所以基本的修正權(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個(gè)近鄰點(diǎn)。某一參考點(diǎn)的權(quán)重值是：該點(diǎn)指紋距離的倒數(shù)與K個(gè)近鄰點(diǎn)指紋距離的倒數(shù)之和作比值，得到的結(jié)果即為該參考點(diǎn)的權(quán)重值，即

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

4 實(shí)驗(yàn)與結(jié)論

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

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

圖2 定位誤差對(duì)比

通過圖2的對(duì)比數(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%。對(duì)比圖2和表1，改進(jìn)的WKNN算法的平均誤差明顯得到了改善，因此改進(jìn)的WKNN算法有效提高了定位精度。

5 結(jié)束語

當(dāng)今社會(huì)互聯(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ǔ)它們的不足之處，通過實(shí)驗(yàn)表明，改進(jìn)的WKNN算法的平均定位誤差比KNN和WKNN明顯改善，因此改進(jìn)的WKNN算法提高了定位精度。美中不足的是改進(jìn)的WKNN算法的花費(fèi)比較大，之后的研究要著重注意成本的問題。