基于LANDMARK系統(tǒng)的KNN室內(nèi)定位改進(jìn)算法

李連亮（重慶郵電大學(xué)信息無(wú)障礙工程研發(fā)中心,重慶　400065）

基于LANDMARK系統(tǒng)的KNN室內(nèi)定位改進(jìn)算法

李連亮
（重慶郵電大學(xué)信息無(wú)障礙工程研發(fā)中心,重慶400065）

摘要：針對(duì)LANDMARC系統(tǒng)中傳統(tǒng)k最近鄰算法（KNN）中定位精度不高計(jì)算量大的問(wèn)題，提出了一種改進(jìn)的定位算法，通過(guò)利用MICA2傳感網(wǎng)絡(luò)協(xié)助，把整個(gè)定位區(qū)域分成若干個(gè)分區(qū)，利用傳感網(wǎng)絡(luò)確定目標(biāo)節(jié)點(diǎn)在哪一個(gè)分區(qū)，消除遠(yuǎn)離目標(biāo)節(jié)點(diǎn)的參考節(jié)點(diǎn)，縮小了k值的選取范圍，在分區(qū)內(nèi)再采用基于泰勒級(jí)數(shù)展開(kāi)法的KNN算法計(jì)算出目標(biāo)節(jié)點(diǎn)的坐標(biāo)提高精度，并依據(jù)改進(jìn)后的算法開(kāi)發(fā)出了相應(yīng)的軟件界面實(shí)測(cè)表明本文提出的算法在精度上比原算法有了明顯的提高。

關(guān)鍵詞：射頻識(shí)別技術(shù)（RFID）;無(wú)線傳感網(wǎng)絡(luò);最近鄰算法（KNN）;接收信號(hào)強(qiáng)度指示（RSSI）

0　引言

隨著物聯(lián)網(wǎng)的發(fā)展，位置服務(wù)（LPS）受到人們?cè)絹?lái)越多的關(guān)注，對(duì)移動(dòng)目標(biāo)定位方法的研究也隨之深入。針對(duì)室內(nèi)復(fù)雜環(huán)境的定位技術(shù)一直是研究的難點(diǎn)。目前，RFID定位技術(shù)[1]以其非接觸、非視距、高靈敏度和低成本的優(yōu)點(diǎn)，正在成為室內(nèi)定位系統(tǒng)的優(yōu)選技術(shù)，受到了更多的關(guān)注。目前，出現(xiàn)了許多利用RFID進(jìn)行定位的定位系統(tǒng)，如LANDMARC[2]、SpotOn[3]、BVIRE等。K-最近鄰算法（KNN）作為常用的定位算法，通過(guò)比較目標(biāo)節(jié)點(diǎn)信號(hào)強(qiáng)度值（RSSI）與各個(gè)參考節(jié)點(diǎn)信號(hào)強(qiáng)度值（RSSI）的相對(duì)大小，計(jì)算目標(biāo)節(jié)點(diǎn)的坐標(biāo)。由于RSSI容易受環(huán)境中溫度和噪聲的影響，在選擇K個(gè)參考節(jié)點(diǎn)時(shí)常常會(huì)包含那些偏離目標(biāo)節(jié)點(diǎn)較遠(yuǎn)的參考節(jié)點(diǎn)，對(duì)定位精度造成很大影響。本文針對(duì)K-最近鄰算法存在的這些問(wèn)題提出一種改進(jìn)方法，首先利用傳感器信息建立網(wǎng)絡(luò)協(xié)助，確定目標(biāo)節(jié)點(diǎn)所在的區(qū)域，計(jì)算目標(biāo)節(jié)點(diǎn)的初步坐標(biāo)，最后利用Taylor級(jí)數(shù)展開(kāi)方法對(duì)坐標(biāo)迭代，得到目標(biāo)節(jié)點(diǎn)的精確位置，提高定位精度。

1　K-最近鄰定位算法

假設(shè)有m個(gè)讀寫(xiě)器和n個(gè)參考節(jié)點(diǎn)以及u個(gè)目標(biāo)節(jié)點(diǎn)。對(duì)任一目標(biāo)節(jié)點(diǎn)，其場(chǎng)強(qiáng)值向量表示為，其中Tj代表第j個(gè)讀寫(xiě)器采集到的目標(biāo)節(jié)點(diǎn)場(chǎng)強(qiáng)值；對(duì)第i個(gè)參考節(jié)點(diǎn)，其場(chǎng)強(qiáng)值向量表示為，其中代表第j個(gè)讀寫(xiě)器采集到的參考節(jié)點(diǎn)i的場(chǎng)強(qiáng)值。為了判斷參考節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的差值程度，對(duì)于任一目標(biāo)節(jié)點(diǎn)p，，有

在公式（1）中Ei表示第i個(gè)參考節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的距離大小，Ei越小表示距離越近，。通過(guò)比較Ei值的大小，將K個(gè)離目標(biāo)節(jié)點(diǎn)最近的參考節(jié)點(diǎn)（即最近鄰節(jié)點(diǎn)）放入同一集合，并定義K個(gè)最近鄰節(jié)點(diǎn)的權(quán)值為

2　改進(jìn)KNN算法

2.1利用傳感器建立網(wǎng)絡(luò)協(xié)助

首先利用傳感器信息將環(huán)境區(qū)域劃分為多個(gè)分區(qū)。在初始化階段中，首先在靜態(tài)環(huán)境（沒(méi)有定位目標(biāo)和噪聲的干擾）下，通過(guò)傳感節(jié)點(diǎn)建立靜態(tài)表（即在靜態(tài)環(huán)境下傳感節(jié)點(diǎn)與其它傳感節(jié)點(diǎn)之間的平均信號(hào)強(qiáng)度），并存儲(chǔ)靜態(tài)RSSI值。當(dāng)待定位的目標(biāo)節(jié)點(diǎn)在傳感網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)時(shí)，傳感節(jié)點(diǎn)之間的RSSI值會(huì)出現(xiàn)波動(dòng)。當(dāng)無(wú)待定位目標(biāo)節(jié)點(diǎn)時(shí)，RSSI會(huì)出現(xiàn)3～5dBm的波動(dòng)；當(dāng)有目標(biāo)節(jié)點(diǎn)時(shí)，RSSI值在18～20dBm之間波動(dòng)。所以根據(jù)RSSI值的波動(dòng)值大小確定有效鏈路。如果某一鏈路的RSSI波動(dòng)值大于18dBm值，表示該鏈路為一個(gè)有效的鏈路[4]。

定位階段利用交叉方法確定待定位目標(biāo)節(jié)點(diǎn)所在分區(qū)，當(dāng)某一分區(qū)內(nèi)存在多條有效鏈路，則表示待定位目標(biāo)節(jié)點(diǎn)在該分區(qū)內(nèi)。通過(guò)對(duì)每個(gè)分區(qū)分配權(quán)值，權(quán)值越大則越靠近待定位目標(biāo)節(jié)點(diǎn)。對(duì)所有交點(diǎn)的權(quán)值取平均值來(lái)計(jì)算定位節(jié)點(diǎn)的位置。

假設(shè)傳感器網(wǎng)格有c個(gè)分區(qū)，每分區(qū)的權(quán)值Wi，對(duì)于所有分區(qū)的權(quán)值可以表示為一組，則Wi表示為：

2.2Taylor級(jí)數(shù)展開(kāi)法

為使公式整潔，上式（6）中后兩項(xiàng)的Fi表示。當(dāng)測(cè)量距離與估計(jì)距離之間距離差為足夠小時(shí)說(shuō)明估計(jì)點(diǎn)準(zhǔn)確，于是可將（6）式寫(xiě)成矩陣形式：

3　實(shí)驗(yàn)驗(yàn)證

在實(shí)驗(yàn)室構(gòu)建實(shí)時(shí)定位系統(tǒng)，傳感節(jié)點(diǎn)選擇MICA2。選擇MICA2的原因是一是其具有很強(qiáng)的路由能力；二是MICA2的頻率是870MHz，這樣不會(huì)與RFID收發(fā)信號(hào)造成干擾。傳感器節(jié)點(diǎn)以廣播的形式周期性地發(fā)送信號(hào)，默認(rèn)時(shí)間間隔為0.3s。在10m×10m的實(shí)驗(yàn)環(huán)境下，參考節(jié)點(diǎn)、讀寫(xiě)器和傳感節(jié)點(diǎn)擺放方式如圖1所示。在測(cè)試環(huán)境下對(duì)20個(gè)定位節(jié)點(diǎn)（其中①②③位于邊界）進(jìn)行測(cè)試，定義誤差為，其中表示目標(biāo)節(jié)點(diǎn)的實(shí)際位置，表示目標(biāo)節(jié)點(diǎn)的系統(tǒng)得出的估計(jì)位置。其中參考節(jié)點(diǎn)間距為1.5m。為評(píng)估本文提出的定位方法，通過(guò)和KNN[5]對(duì)照來(lái)評(píng)估本文提出方法的性能。

通過(guò)圖2可以看到，在同樣環(huán)境下，使用最近鄰居算法定位的平均估計(jì)誤差是1.34m，最大平均估計(jì)誤差是2.2m；使用本文改進(jìn)算法定位的平均估計(jì)誤差是0.95m，最大平均估計(jì)誤差是1.8m。同時(shí)對(duì)位于邊界的（①②③??）節(jié)點(diǎn)的兩種定位方法誤差進(jìn)行對(duì)比，可以看出，本文提出的算法跟最近鄰算法相比在邊界定位方面同樣具有很好的效果。而通過(guò)圖3可以看到，對(duì)比LANDMARC系統(tǒng)的最近鄰算法和本方法可以發(fā)現(xiàn)，統(tǒng)計(jì)誤差小于1m，僅用KNN算法的累積誤差概率為82.5%，而本文提出的方法為89.2%，由此看出后者具有較好的定位精度。之后還對(duì)兩種算法的計(jì)算效率進(jìn)行了對(duì)比，利用KNN定位算法和本文提出的定位算法計(jì)算100個(gè)目標(biāo)節(jié)點(diǎn)，各自所需時(shí)間如圖4所示

從圖4可以看出本文提出的改進(jìn)算法比典型的KNN算法在計(jì)算時(shí)間明顯減少很多，而且參考節(jié)點(diǎn)數(shù)目越多，效果越顯著。實(shí)驗(yàn)結(jié)果表明，KNN算法通過(guò)計(jì)算目標(biāo)節(jié)點(diǎn)的最近鄰節(jié)點(diǎn)數(shù)目進(jìn)行定位，參考節(jié)點(diǎn)越多，計(jì)算花費(fèi)時(shí)間越多，而本文提出的改進(jìn)方法利用建立傳感網(wǎng)絡(luò)協(xié)助，這樣就減少要計(jì)算的參考節(jié)點(diǎn)數(shù)目，進(jìn)而減少了所需計(jì)算時(shí)間，提高了算法的效率。

4　結(jié)束語(yǔ)

本文基于最近鄰定位算法，提出了一種改進(jìn)算法，直接消除了遠(yuǎn)離目標(biāo)節(jié)點(diǎn)的參考節(jié)點(diǎn)，縮小了k值的選取范圍，克服了隨機(jī)誤差，減少了算法的計(jì)算量，并對(duì)邊界定位具有很好的效果。本文的測(cè)試是在實(shí)驗(yàn)室的環(huán)境下模擬真實(shí)的環(huán)境中進(jìn)行的，貼近實(shí)際應(yīng)用的室內(nèi)環(huán)境。實(shí)測(cè)表明本文提出的改進(jìn)算法精度在1.5m以內(nèi)，定位的最大誤差減小，且平均精度較之原算法有了很大的提高。

參考文獻(xiàn)：

[1]李程,錢(qián)松榮.射頻識(shí)別動(dòng)態(tài)定位方法[J].通信學(xué)報(bào),2013, 34(04):144-148.

[2]秦爽.參數(shù)化多維標(biāo)度定位方法研究[D].成都：電子科技大學(xué),2013.

[3]SANSANAYUTHT,SUKSOMPONGP,CHAREONLARPNOPPARUTC,etal. RFID2D-localizationimprovementusingmodif iedLANDMARCwi th l inearMMSEest imation[C].Communicat ionsandInformat ion Technologies(ISCIT),201313thInternationalSymposiumon. IEEE,2013:133-137.

[4]朱劍,趙海,張希元等.基于LQI量度的無(wú)線鏈路質(zhì)量評(píng)估模型[J].東北大學(xué)學(xué)報(bào):自然科學(xué)版,2008,29(09):1262-1265.

[5]閆保中,姜琛,尹偉偉.基于RFID技術(shù)的室內(nèi)定位算法研究[J].計(jì)算機(jī)仿真,2010(02):320-324.

作者簡(jiǎn)介:李連亮(1987-)，男，山東菏澤人，碩士研究生，主要研究方向：射頻識(shí)別，無(wú)線定位。