基于LANDMARK系統的KNN室內定位改進算法

李連亮（重慶郵電大學信息無障礙工程研發中心,重慶　400065）

基于LANDMARK系統的KNN室內定位改進算法

李連亮
（重慶郵電大學信息無障礙工程研發中心,重慶400065）

摘要：針對LANDMARC系統中傳統k最近鄰算法（KNN）中定位精度不高計算量大的問題，提出了一種改進的定位算法，通過利用MICA2傳感網絡協助，把整個定位區域分成若干個分區，利用傳感網絡確定目標節點在哪一個分區，消除遠離目標節點的參考節點，縮小了k值的選取范圍，在分區內再采用基于泰勒級數展開法的KNN算法計算出目標節點的坐標提高精度，并依據改進后的算法開發出了相應的軟件界面實測表明本文提出的算法在精度上比原算法有了明顯的提高。

關鍵詞：射頻識別技術（RFID）;無線傳感網絡;最近鄰算法（KNN）;接收信號強度指示（RSSI）

0　引言

隨著物聯網的發展，位置服務（LPS）受到人們越來越多的關注，對移動目標定位方法的研究也隨之深入。針對室內復雜環境的定位技術一直是研究的難點。目前，RFID定位技術[1]以其非接觸、非視距、高靈敏度和低成本的優點，正在成為室內定位系統的優選技術，受到了更多的關注。目前，出現了許多利用RFID進行定位的定位系統，如LANDMARC[2]、SpotOn[3]、BVIRE等。K-最近鄰算法（KNN）作為常用的定位算法，通過比較目標節點信號強度值（RSSI）與各個參考節點信號強度值（RSSI）的相對大小，計算目標節點的坐標。由于RSSI容易受環境中溫度和噪聲的影響，在選擇K個參考節點時常常會包含那些偏離目標節點較遠的參考節點，對定位精度造成很大影響。本文針對K-最近鄰算法存在的這些問題提出一種改進方法，首先利用傳感器信息建立網絡協助，確定目標節點所在的區域，計算目標節點的初步坐標，最后利用Taylor級數展開方法對坐標迭代，得到目標節點的精確位置，提高定位精度。

1　K-最近鄰定位算法

假設有m個讀寫器和n個參考節點以及u個目標節點。對任一目標節點，其場強值向量表示為，其中Tj代表第j個讀寫器采集到的目標節點場強值；對第i個參考節點，其場強值向量表示為，其中代表第j個讀寫器采集到的參考節點i的場強值。為了判斷參考節點與目標節點之間的差值程度，對于任一目標節點p，，有

在公式（1）中Ei表示第i個參考節點與目標節點之間的距離大小，Ei越小表示距離越近，。通過比較Ei值的大小，將K個離目標節點最近的參考節點（即最近鄰節點）放入同一集合，并定義K個最近鄰節點的權值為

2　改進KNN算法

2.1利用傳感器建立網絡協助

首先利用傳感器信息將環境區域劃分為多個分區。在初始化階段中，首先在靜態環境（沒有定位目標和噪聲的干擾）下，通過傳感節點建立靜態表（即在靜態環境下傳感節點與其它傳感節點之間的平均信號強度），并存儲靜態RSSI值。當待定位的目標節點在傳感網絡覆蓋區域內時，傳感節點之間的RSSI值會出現波動。當無待定位目標節點時，RSSI會出現3～5dBm的波動；當有目標節點時，RSSI值在18～20dBm之間波動。所以根據RSSI值的波動值大小確定有效鏈路。如果某一鏈路的RSSI波動值大于18dBm值，表示該鏈路為一個有效的鏈路[4]。

定位階段利用交叉方法確定待定位目標節點所在分區，當某一分區內存在多條有效鏈路，則表示待定位目標節點在該分區內。通過對每個分區分配權值，權值越大則越靠近待定位目標節點。對所有交點的權值取平均值來計算定位節點的位置。

假設傳感器網格有c個分區，每分區的權值Wi，對于所有分區的權值可以表示為一組，則Wi表示為：

2.2Taylor級數展開法

為使公式整潔，上式（6）中后兩項的Fi表示。當測量距離與估計距離之間距離差為足夠小時說明估計點準確，于是可將（6）式寫成矩陣形式：

3　實驗驗證

在實驗室構建實時定位系統，傳感節點選擇MICA2。選擇MICA2的原因是一是其具有很強的路由能力；二是MICA2的頻率是870MHz，這樣不會與RFID收發信號造成干擾。傳感器節點以廣播的形式周期性地發送信號，默認時間間隔為0.3s。在10m×10m的實驗環境下，參考節點、讀寫器和傳感節點擺放方式如圖1所示。在測試環境下對20個定位節點（其中①②③位于邊界）進行測試，定義誤差為，其中表示目標節點的實際位置，表示目標節點的系統得出的估計位置。其中參考節點間距為1.5m。為評估本文提出的定位方法，通過和KNN[5]對照來評估本文提出方法的性能。

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

從圖4可以看出本文提出的改進算法比典型的KNN算法在計算時間明顯減少很多，而且參考節點數目越多，效果越顯著。實驗結果表明，KNN算法通過計算目標節點的最近鄰節點數目進行定位，參考節點越多，計算花費時間越多，而本文提出的改進方法利用建立傳感網絡協助，這樣就減少要計算的參考節點數目，進而減少了所需計算時間，提高了算法的效率。

4　結束語

本文基于最近鄰定位算法，提出了一種改進算法，直接消除了遠離目標節點的參考節點，縮小了k值的選取范圍，克服了隨機誤差，減少了算法的計算量，并對邊界定位具有很好的效果。本文的測試是在實驗室的環境下模擬真實的環境中進行的，貼近實際應用的室內環境。實測表明本文提出的改進算法精度在1.5m以內，定位的最大誤差減小，且平均精度較之原算法有了很大的提高。

參考文獻：

[1]李程,錢松榮.射頻識別動態定位方法[J].通信學報,2013, 34(04):144-148.

[2]秦爽.參數化多維標度定位方法研究[D].成都：電子科技大學,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量度的無線鏈路質量評估模型[J].東北大學學報:自然科學版,2008,29(09):1262-1265.

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

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