基于嵌入式平臺與kNN算法的室內(nèi)定位研究

張輝 何倩

（安徽師范大學(xué)皖江學(xué)院 電子工程系，安徽 蕪湖 241000）

0 引言

隨著城市的發(fā)展越來越快，高樓林立已成為許多城市的基本配置。有學(xué)者指出，目前對于大多數(shù)人來說，處于室內(nèi)的總時長約為一天的70%左右。由于室內(nèi)建筑的空間復(fù)雜度不斷增加，已有的定位技術(shù)已經(jīng)不滿足當(dāng)前的定位需求，室內(nèi)定位技術(shù)的改革引起了關(guān)注。傳統(tǒng)的室內(nèi)定位技術(shù)硬件成本高、軟件上代碼執(zhí)行效率低。當(dāng)前的定位技術(shù)[1]，定位精確度不高，需要使用其他的算法輔助定位。三邊定位算法是目前使用較多的定位算法。三邊定位的原理簡單，實現(xiàn)也很簡單，但缺點是設(shè)備成本高、可移植性差等。

1 總體結(jié)構(gòu)

本系統(tǒng)的硬件設(shè)計是由電子標(biāo)簽、閱讀器、天線和嵌入式平臺構(gòu)成，總體結(jié)構(gòu)如圖1所示。電子標(biāo)簽通過天線與RFID（Radio Frequency Identification）閱讀器建立無線連接，之后，將測得的數(shù)據(jù)傳送給嵌入式平臺，平臺對數(shù)據(jù)進行處理并輸出最終的定位結(jié)果。軟件設(shè)計是基于嵌入式平臺的Ubuntu MATE環(huán)境下，實現(xiàn)kNN（k-Nearest Neighbour）定位算法。定位精度和數(shù)據(jù)處理速度都在一定的程度上得到提高。本設(shè)計從硬件與軟件兩個角度對室內(nèi)定位的精確度以及算法的數(shù)據(jù)處理速度都進行了一定的提升，適合做大范圍推廣。

圖1 總體結(jié)構(gòu)圖

2 組件簡介

2.1 RFID閱讀器

RFID全稱為射頻識別，即射頻技術(shù)[2]，其組成是閱讀器，電子標(biāo)簽和天線[3]。閱讀器是RFID的讀寫終端設(shè)備，通常與控制終端，比如電腦等處理設(shè)備相連，對接受到的信息進行分析，獲得電子標(biāo)簽的具體位置信息，并且可以更改電子標(biāo)簽的內(nèi)部信息。電子標(biāo)簽的內(nèi)部芯片編碼信息不同，主要用于身份鑒別，當(dāng)其進入磁場中時，可以利用電磁感應(yīng)獲得感應(yīng)電流[4]，從而獲得能量發(fā)送自身內(nèi)部芯片中的信息。天線可以進行模擬信號與數(shù)字信號的雙向轉(zhuǎn)換。發(fā)射器通過天線向某一區(qū)域發(fā)射電磁波，該天線用于查找電子標(biāo)簽并獲取其內(nèi)部信息。在接收到電子標(biāo)簽的響應(yīng)信息后，電磁波信號可以轉(zhuǎn)換成電信號傳輸?shù)桨l(fā)射機。

圖2 超高頻RFID四通道閱讀器

閱讀器作用原理如圖2所示，首先，對設(shè)備進行連接和供電后，閱讀器以天線為介質(zhì)將電磁波發(fā)送到目標(biāo)區(qū)域，電子標(biāo)簽收到信息并響應(yīng)。其次，閱讀器通過天線接收到信息以后，對收到的信息開始進行處理，將其轉(zhuǎn)換成電子標(biāo)簽的位置信息。最后，以信號強度的形式顯示到嵌入式平臺上。此過程連續(xù)循環(huán)，實現(xiàn)位置實時更新。

該技術(shù)具有以下特點：一是具有非接觸性，能夠做到遠距離定位，受到外界的干擾較小，便于維修管理，易于操作。適用于公共場合，方便與其他平臺相結(jié)合，進行開發(fā)應(yīng)用，衍生更多的功能。二是無需人工干預(yù)，系統(tǒng)利用射頻技術(shù)，可自動識別信號覆蓋范圍內(nèi)的多個目標(biāo)的信息，適應(yīng)環(huán)境能力強，定位精度高，準確性好。不僅可以用于對物體的定位，比如車輛，物流等。三是還可以用于對人員的定位，比如在一些重要場合對人員進出進行系統(tǒng)控制，對范圍內(nèi)的某人進行快速的尋找定位;主要通過無線通信技術(shù)對目標(biāo)進行定位，目標(biāo)的具體位置以及身份信息通過閱讀器獲取，相較于當(dāng)下的GPS定位技術(shù)，成本較低且運行簡單，功耗較小，且不受室內(nèi)復(fù)雜環(huán)境的影響等優(yōu)點。本系統(tǒng)的構(gòu)建便是基于此技術(shù)，利用了RFID的室內(nèi)定位優(yōu)勢創(chuàng)建的室內(nèi)定位系統(tǒng)，并將其在具體上層應(yīng)用中實現(xiàn)。

2.2 嵌入式平臺

嵌入式平臺選用的是Raspberry Pi 3B+款。Raspberry Pi是一款基于ARM的微型電腦主板，其結(jié)構(gòu)如圖3所示，自帶4個USB2.0接口、一個以太網(wǎng)接口和MicroSD插槽。內(nèi)存是1GBLPDDR2 SDRAM。CPU是1.4GHz 64位4核ARM Cortex-A53 CPU。存儲使用的是Micro-SD。

3 實驗?zāi)Ｐ徒?/h2>

3.1 實驗場景圖

本實驗基于RFID技術(shù)與Raspberry Pi的平臺技術(shù)進行，在室內(nèi)進行小規(guī)模的實驗，以小方格表示一個最小單元坐標(biāo)單元，每個位置都用三個電子標(biāo)簽進行多次測量取平均數(shù)據(jù)。

劃出一塊10 dm×10 dm的正方形區(qū)域作為實驗，各個邊平均分成10份，也就是將整個區(qū)域分成100個小塊，如圖4。A、B、C三個位置都放置天線，RFID閱讀器連接并控制天線對電子標(biāo)簽信息進行讀寫后轉(zhuǎn)換成RSSI數(shù)據(jù)，且將值傳到Raspberry Pi中進行數(shù)據(jù)處理。

圖3 Raspberry Pi結(jié)構(gòu)圖

圖4 實驗環(huán)境模擬圖

3.2 RSSI信號強度

需要設(shè)置一個RSSI仿真環(huán)境接收RSSI數(shù)據(jù)集，建立一典型的離線數(shù)據(jù)庫，進而實現(xiàn)在線定位。前期對模型進行了數(shù)據(jù)測量，經(jīng)多次測量得到了多組值，構(gòu)成了一個離線數(shù)據(jù)庫。

在正方形區(qū)域上選擇三條邊，分別對應(yīng)著三個方向，實驗中記為A，B，C三個位置。在對應(yīng)的三個位置上分別測得每個小塊的信號強度，并依次進行記錄。實驗數(shù)據(jù)如表1—表3：

A位置：

A位置接收到RSSI數(shù)據(jù)的特點是隨著橫縱坐標(biāo)的增加而增強。

B位置：

B位置接收到RSSI數(shù)據(jù)的特點是隨著縱坐標(biāo)的增加而減弱，隨著橫坐標(biāo)的增加而增強。

C位置：

C位置接收到RSSI數(shù)據(jù)的特點是隨著縱坐標(biāo)的增加而增強。隨著橫坐標(biāo)的增加而減弱到中心點（1，5）（1，6）處 RSSI數(shù)據(jù)減到最小，后隨著橫坐標(biāo)的增加而增強。

表1 A位置測試采集數(shù)據(jù)

表2 B位置測試采集數(shù)據(jù)

表3 C位置測試采集數(shù)據(jù)

3.3 數(shù)學(xué)模型

3.3.1 歐氏距離模型

歐幾里德距離在二維平面內(nèi)都可以表示兩點之間的距離。

二維空間的公式：

其中，ρ為點（x2，y2）與點（x1，y1）之間的歐式距離；|X|為點（x2，y2）到原點的歐氏距離。

3.3.2 kNN數(shù)學(xué)模型

k近鄰中的分類決策規(guī)則通常采用多數(shù)表決，這意味著輸入實例的類由最相似的k個相鄰訓(xùn)練實例中的大多數(shù)類決定的[5]。多數(shù)表決規(guī)則（Majority Voting Rule）有如下解釋：如果分類的損失函數(shù)為0-1損失函數(shù)，分類函數(shù)為：

那么誤分類的概率是：P（Y≠f（X））=1-P（Y=f（X））

對于所給的實例x∈X，它最鄰近的k個訓(xùn)練實例點構(gòu)成的集合 Nk（x）。 如果涵蓋 Nk（x）的區(qū)域類別是cj，那么誤分類率是：

為了使誤分類率最小也就是經(jīng)驗風(fēng)險最小，就要使∑xi∈Nk（x）I（yi≠cj）最大，意即大多表決規(guī)則與經(jīng)驗風(fēng)險的最小化是等同的。

3.3.3 kNN的應(yīng)用

k最近鄰算法（kNN）最常用的應(yīng)用是位置指紋法：使用最近的k個RSSI的指紋位置估計當(dāng)前位置。通過比較特征RSSI數(shù)據(jù)的不同，定位標(biāo)簽的位置。kNN算法的關(guān)鍵就是從數(shù)據(jù)中提取出一個從特征到標(biāo)簽的映射關(guān)系模型[6]。

對于在線RSSI數(shù)據(jù)s，算出它和所建立的指紋庫中每個 RSSI數(shù)據(jù){s1，s2，…，sM}的間隔（比如歐氏距離），選擇最鄰近k個位置指紋（一個指紋是一個RSSI數(shù)據(jù)與一個位置的對應(yīng)）。

對于kNN回歸，選取k個指紋的位置坐標(biāo)X與Y分別計算平均值，即為定位結(jié)果。最終，將標(biāo)簽的位置信息以（X，Y）的形式打印在Raspberry Pi的顯示屏上[7]。

對于kNN劃分，把所取定位的范圍分成10 dm×10 dm大小方格，一個方格視為一個類別，分別用網(wǎng)格標(biāo)號來替代，k個網(wǎng)格標(biāo)號都進行投票和統(tǒng)計，并且選擇具有最大投票數(shù)的網(wǎng)格用于定位結(jié)果。

4 kNN算法實現(xiàn)

一個樣本x與樣本集中k個最鄰近樣本中的多數(shù)都屬于另一個類別Y，那么也就是說這個樣本x也含于類別Y，并且還包含這個類別樣本的特性[8]。簡單來說，就是x屬于類別Y，且具有Y的特性。

依據(jù)該理論可以得到結(jié)論，kNN是用測量不同特征值之間的間隔再進行分類，并在決策樣本類別時，只需要參照樣本周圍k個近鄰樣本的類別。所以該方法更適合用于處理樣本集存在很多重疊的場合，例如聚類分析、預(yù)測分析、文本分類、降維等。算法流程如圖5所示。

圖5 kNN算法流程圖

kNN算法的偽代碼實現(xiàn)：

4.1 具體實現(xiàn)

具體實現(xiàn)分為以下步驟：a.串口傳輸數(shù)據(jù)；b.讀入數(shù)據(jù)；c.數(shù)據(jù)預(yù)測；d.數(shù)據(jù)比較。a.串口傳輸數(shù)據(jù)代碼如下所示。

b.讀入數(shù)據(jù)的部分結(jié)果，如圖6所示。

圖6 讀入數(shù)據(jù)

代碼如下所示。

c.數(shù)據(jù)預(yù)測得到特征值，運行結(jié)果如圖7所示。

圖7 數(shù)據(jù)預(yù)測

代碼如下所示。

d.數(shù)據(jù)比對得出結(jié)果，如圖8所示。

圖8 數(shù)據(jù)處理輸出結(jié)果圖

代碼如下所示。

4.2 實驗過程

（1）Raspberry Pi通過串口接收到RSSI數(shù)據(jù)，并將數(shù)據(jù)存到TXT文檔中。接收到的數(shù)據(jù)如下：A69.3，72.0，72.0B。

A和B是為了保證收到的數(shù)據(jù)的完整性，只有當(dāng)收到的數(shù)據(jù)中以A開頭B結(jié)尾才讀取數(shù)據(jù)，防止因為數(shù)據(jù)丟失等問題造成的定位精度變大。69.3，72.0，72.0是RFID在定位點采集到的三個RSSI數(shù)據(jù)。

（2）導(dǎo)入接收的RSSI數(shù)據(jù)，分析處理。通過串口接收的數(shù)據(jù)可能會產(chǎn)生數(shù)據(jù)丟失的情況，為了解決這個問題我們寫了一個協(xié)議用于處理保存這個數(shù)據(jù)。

（3）將處理好的RSSI數(shù)據(jù)進行分類和處理，并輸出坐標(biāo)信息，如圖9。圖中在TXT文本中存儲接收到的數(shù)據(jù)，在命令行中運行Python程序進行數(shù)據(jù)處理。輸出的第一行顯示的是這組RSSI數(shù)據(jù)的特征值，第二行顯示的是與這組RSSI數(shù)據(jù)的特征值最接近的坐標(biāo)點，最后一行輸出定位結(jié)果，即該組值所定點的坐標(biāo)位置。

4.3 實驗論證

實驗的最后數(shù)據(jù)處理部分選用了三種方法，并對處理后的數(shù)據(jù)進行比對，選取了其中精度最高的方法。比對結(jié)果如表4。

研究發(fā)現(xiàn)，該算法在RFID信號覆蓋范圍較弱的區(qū)域內(nèi)定位精度較低，在RFID信號覆蓋較強的區(qū)域內(nèi)定位精度較高[9]。通過選取16個點（點的位置如圖10），分別測出其RSSI數(shù)據(jù)，運行程序輸出定位結(jié)果，定位結(jié)果如表5所示。

圖9 Raspberry Pi上輸出的定位信息

表4 數(shù)據(jù)處理方法數(shù)據(jù)對比表

圖10 選取的測試點位置

表5 定位結(jié)果圖

通過搭建模型進行測試,得出表1—表3的數(shù)據(jù)，作為離線數(shù)據(jù)庫，用于實驗測量時作為比對數(shù)據(jù)，并且進行多次重復(fù)實驗，取得最為接近的數(shù)據(jù)值。為了驗證該實驗的定位精度，進行了多組實驗數(shù)據(jù)的比對（如表5）和與其他定位算法的定位精度的比對。比對結(jié)果如表6。由此可知，該方法的確在一定程度上提高了定位精度。

表6 定位算法精度對比表

5 結(jié)論

研究主要設(shè)計了一種基于嵌入式平臺與kNN的室內(nèi)定位技術(shù)[10]，較好的解決了室內(nèi)定位精確度不高的問題。由于沒有經(jīng)過更大更復(fù)雜的區(qū)域驗證、實驗數(shù)據(jù)不夠全面等，設(shè)計本身還存在一定不足，有待后續(xù)進一步改進。過程中，通過實驗對kNN算法進行了具體驗證，實驗結(jié)果顯示與嵌入式平臺上代碼運行分析的結(jié)果基本一致。由此可見，兩者的結(jié)合能夠?qū)崿F(xiàn)較高精確度的定位，這也體現(xiàn)了在如今大數(shù)據(jù)時代，特別是伴隨5G網(wǎng)絡(luò)的建設(shè)，嵌入式平臺與邊緣計算的結(jié)合可為人們提供更加智能、便捷的產(chǎn)品和服務(wù)。