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

張輝 何倩

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

0 引言

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

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

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

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

2 組件簡(jiǎn)介

2.1 RFID閱讀器

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

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

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

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

2.2 嵌入式平臺(tái)

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

3 實(shí)驗(yàn)?zāi)Ｐ徒?/h2>

3.1 實(shí)驗(yàn)場(chǎng)景圖

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

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

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

圖4 實(shí)驗(yàn)環(huán)境模擬圖

3.2 RSSI信號(hào)強(qiáng)度

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

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

A位置：

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

B位置：

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

C位置：

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

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

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

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

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

3.3.1 歐氏距離模型

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

二維空間的公式：

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

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

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

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

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

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

3.3.3 kNN的應(yīng)用

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

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

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

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

4 kNN算法實(shí)現(xiàn)

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

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

圖5 kNN算法流程圖

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

4.1 具體實(shí)現(xiàn)

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

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

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

代碼如下所示。

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

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

代碼如下所示。

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

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

代碼如下所示。

4.2 實(shí)驗(yàn)過(guò)程

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

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

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

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

4.3 實(shí)驗(yàn)論證

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

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

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

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

圖10 選取的測(cè)試點(diǎn)位置

表5 定位結(jié)果圖

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

表6 定位算法精度對(duì)比表

5 結(jié)論

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