一種基于神經(jīng)網(wǎng)絡(luò)的RSSI定位算法

宗傳林　高作相　賀育茹

摘 要：針對商場、地下室等室內(nèi)環(huán)境GPS室內(nèi)信號較弱、定位誤差較大的問題，本文提出了一種基于神經(jīng)網(wǎng)絡(luò)的RSSI定位算法，通過對基本的BP算法加以改進(jìn)，優(yōu)化其功能，最后進(jìn)行實(shí)驗(yàn)驗(yàn)證。

關(guān)鍵詞：神經(jīng)網(wǎng)絡(luò);指紋庫;RSSI;K聚類算法

中圖分類號：TP212.9文獻(xiàn)標(biāo)識碼：A文章編號：1003-5168（2020）13-0024-03

An RSSI Localization Algorithm Based on Neural Network

ZONG Chuanlin GAO Zuoxiang HE Yuru

（Changchun University of Science and Technology Changchun， Jilin 130022）

Abstract： Aiming at the problem of weak indoor signal and large positioning error of GPS in shopping malls， basements and other indoor environments， this paper put forward a RSSI positioning algorithm based on neural network， improved the basic BP algorithm， optimizes its function， and finally carried out experimental verification.

Keywords： neural network;fingerprint library;RSSI;K clustering algorithm

隨著互聯(lián)網(wǎng)和物聯(lián)網(wǎng)的高速發(fā)展及無線局域網(wǎng)的普及，人們越來越看重信息傳遞的準(zhǔn)確性和即時(shí)性。在該背景下，產(chǎn)生了一個(gè)新型的服務(wù)種類，即基于位置服務(wù)（Location Based Services，LBS），為人們提供了巨大的便利。LBS在日常生活中主要體現(xiàn)在室外定位的應(yīng)用上，如利用全球定位系統(tǒng)（Global Positioning System，GPS）、北斗衛(wèi)星的道路導(dǎo)航、輔助定位服務(wù)等;但在室內(nèi)，因障礙物過多、過厚，導(dǎo)致衛(wèi)星信號無法穿透，加上衛(wèi)星的多徑效應(yīng)等因素，嚴(yán)重影響了室內(nèi)定位的精準(zhǔn)性。通常，GPS室外定位精度能達(dá)到3～5 m，甚至可以更精確，但在結(jié)構(gòu)較為復(fù)雜的室內(nèi)，誤差能夠達(dá)到10 m。目前，室內(nèi)的定位技術(shù)主要有藍(lán)牙定位技術(shù)、射頻定位技術(shù)、無線保真（Wireless Fidelity，WiFi）定位技術(shù)、紅外定位技術(shù)以及超聲波定位技術(shù)等[1]。其中，WiFi定位技術(shù)又包括信道定位技術(shù)和信號強(qiáng)度（Received Signal Strength Indication，RSSI）定位技術(shù)。在我國，通信技術(shù)十分發(fā)達(dá)，在室內(nèi)外公共場所，有著極高的WiFi覆蓋率，使得WiFi室內(nèi)定位具有良好的優(yōu)勢;同時(shí)，WiFi定位技術(shù)不需要額外的傳感器，與GPS相比，速度提高了10倍以上[2]，且通過軟件開發(fā)就能實(shí)現(xiàn)定位，因此WiFi定位技術(shù)發(fā)展較快。

本文結(jié)合梯度下降法原理和神經(jīng)網(wǎng)絡(luò)編寫了一套定位算法，利用無線接入點(diǎn)（Access Point，AP）與用戶之間線性與非線性的關(guān)系，解決了在傳統(tǒng)AP定位中用三個(gè)AP求解三角形法無法解決的多徑效應(yīng)，也解決了傳播過程中依賴傳播衰減公式帶來的較大誤差。同時(shí)，給出了對模型的獎(jiǎng)勵(lì)與懲罰方法，并引入了基本K聚類算法，以提高模型精度。在離線階段給出了不同數(shù)據(jù)量情況下選擇不同的查找方法以提高查找效率，最后通過在特定場景下的簡要實(shí)驗(yàn)，得出此場景下的選擇參數(shù)，其最小誤差為1.42 m。

1 定位系統(tǒng)流程和相關(guān)原理

1.1 定位系統(tǒng)流程

定位系統(tǒng)流程圖如圖1所示。從圖1可以看出，離線階段：初始程序，讀取各點(diǎn)RSSI值并進(jìn)行迭代，將讀取的值保存到指紋庫中，直至迭代完成;在線階段：通過將讀取的RSSI值與指紋庫中的指紋對比找出對應(yīng)位置，并再次依次迭代。

1.2 基本原理

通常情況下，人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Networks，ANNS）主要用來處理非線性問題，例如，在信號傳播過程中涉及多種噪聲、衰減等非線性問題。因此，采用ANNS中的誤差反向傳播算法（Error Back Propagation，BP）具有很大的優(yōu)勢。

在處理數(shù)據(jù)的過程中，研究者采用離差標(biāo)準(zhǔn)化方法對數(shù)據(jù)進(jìn)行歸一化處理，函數(shù)形式為：

式中，[Xmin]為數(shù)據(jù)中最小值;[Xmax]為數(shù)據(jù)中最大值。

BP算法中隱層節(jié)點(diǎn)數(shù)對定位精度具有很大的影響：隱層節(jié)點(diǎn)數(shù)過少，訓(xùn)練精度過低，模型欠擬合;隱層節(jié)點(diǎn)數(shù)過多，訓(xùn)練時(shí)間加長，模型過擬合也會(huì)導(dǎo)致精度降低。推薦隱層節(jié)點(diǎn)數(shù)可由經(jīng)驗(yàn)公式（2）計(jì)算得出：

式中，[neth]為隱層節(jié)點(diǎn)數(shù);[in]為輸入層節(jié)點(diǎn)數(shù);[out]為輸出層節(jié)點(diǎn)數(shù);[β]為0～10的常數(shù)。

1.3 指紋庫相關(guān)算法原理

指紋庫相關(guān)算法包括快速排序、歸并排序和堆排序。快速排序法：先從序列中取一個(gè)值作為標(biāo)準(zhǔn)值，將小于其的值放在左邊，大于其的值放在右邊，以此進(jìn)行迭代至全部排序完成。歸并排序法：采用分治法，其方法將序列分成兩個(gè)序列，再將得到的兩個(gè)子序列繼續(xù)二分下去，直到不能再分，最后再兩兩合并，形成有序序列。堆排序：利用堆這種數(shù)據(jù)結(jié)構(gòu)所涉及的一種排序算法，其原理為堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并滿足堆積性質(zhì)：子節(jié)點(diǎn)的鍵值或索引值總是大于（或者小于）父節(jié)點(diǎn)。此外，采用快速排序法平均只需要[Onlogn]的復(fù)雜度。在相同數(shù)據(jù)規(guī)模下（見表1），快速排序法的效率較高。

1.4 K聚類算法

K聚類算法是聚類算法的一種，其步驟為：第一，隨機(jī)選取[K]個(gè)中心點(diǎn);第二，計(jì)算所有數(shù)據(jù)點(diǎn)距[K]個(gè)中心點(diǎn)的距離，然后將數(shù)據(jù)點(diǎn)分到與其最近的中心點(diǎn)，形成[K]個(gè)簇;第三，計(jì)算每個(gè)簇中所有數(shù)據(jù)的均值，重新定義中心點(diǎn);第四，以此進(jìn)行迭代，直至中心點(diǎn)位置變化小于閾值，劃分結(jié)束。

2 神經(jīng)網(wǎng)絡(luò)訓(xùn)練技術(shù)指標(biāo)

2.1 傳遞函數(shù)的選擇

本文選取Sigmoid函數(shù)作為傳遞函數(shù)，其中：

式中，[fx]為因變量;[x]為自變量;[α]為傾斜參數(shù)，常被默認(rèn)為1。使用Sigmoid函數(shù)（見圖2）作為傳遞函數(shù)的原因?yàn)椋浩漭敵龇秶邢?，Sigmoid函數(shù)的輸出被固定在（0，1），數(shù)據(jù)在傳遞過程中不容易發(fā)散。Sigmoid函數(shù)在（0，1）中存在單調(diào)、處處可導(dǎo)等優(yōu)良性質(zhì)，在（0，0.5）處斜率最大，且中心對稱，兩頭被抑制明顯，因而適合數(shù)據(jù)在多層神經(jīng)元之間傳遞時(shí)使用。同時(shí)，神經(jīng)元中間激活，兩頭克制的表現(xiàn)也與神經(jīng)科學(xué)中的激勵(lì)與抑制行為十分相似，能夠更好地體現(xiàn)神經(jīng)網(wǎng)絡(luò)的特性[3]。

2.2 過擬合與欠擬合

在學(xué)習(xí)過程中模型會(huì)出現(xiàn)過擬合與欠擬合的問題。欠擬合指對樣本訓(xùn)練程度不夠，導(dǎo)致誤差較大。由維度較低的特征或者模型過于簡單引起，通常用增加特征維度與增加訓(xùn)練樣本來解決;過擬合指訓(xùn)練程度過高，特征維度較高，模型過于復(fù)雜引起，常用正則化的方法來解決。

有監(jiān)督學(xué)習(xí)算法訓(xùn)練的目的是最小化損失函數(shù)，本文引入均方誤差損失函數(shù)，其預(yù)測值與樣本真實(shí)值的誤差平方和為：

其中，[yi]是樣本標(biāo)簽值;[fθxi]是預(yù)測函數(shù)的輸出值;[θ]是模型參數(shù);[l]為樣本數(shù)。

為了防止過擬合，可以對復(fù)雜的模型進(jìn)行懲罰，加上一個(gè)懲罰項(xiàng)，使模型參數(shù)盡可能小。加入懲罰項(xiàng)后的損失函數(shù)為：

式中，[λ]為懲罰項(xiàng)系數(shù);[R（θ）]為懲罰函數(shù)，后半部分為正則化項(xiàng)，正則化項(xiàng)可以使用L2范數(shù)，L2范數(shù)相對于L1范數(shù)，在求解最優(yōu)化問題有著更好的數(shù)學(xué)性質(zhì)。

并且懲罰項(xiàng)中L2范數(shù)正則化項(xiàng)的梯度為：

3 解決的問題與實(shí)驗(yàn)簡要分析

3.1 面臨問題

隨著WiFi的普及以及機(jī)器學(xué)習(xí)的高速發(fā)展，室內(nèi)定位技術(shù)如雨后春筍般層出不窮，如可見光定位技術(shù)、無線定位技術(shù)等。但是，都面臨著如何解決定位精度的問題，本文只對自己所編寫B(tài)P算法和聚類算法進(jìn)行闕值的選取。

3.2 樣點(diǎn)的選擇

在一個(gè)長10 m、寬8 m的空間內(nèi)等位置放置6個(gè)AP信號（見圖3），在長、寬分別為0.05 m的地方選取32 000個(gè)點(diǎn)，將其每點(diǎn)作為輸入層，輸入神經(jīng)網(wǎng)絡(luò)中，并將數(shù)據(jù)保存到指紋庫中;另隨機(jī)再選取32 000個(gè)點(diǎn)做同樣的處理，對其在線階段測得位置與其最相近的點(diǎn)取均方差，訓(xùn)練次數(shù)2 000次。采樣方式比較如表2所示。

在取樣方式上，等距取樣隨著點(diǎn)數(shù)的增加誤差逐漸減小，但運(yùn)算時(shí)間相對于非等距取樣時(shí)間要長（見表2）。等間距取樣更有利于定位準(zhǔn)確性，因此后續(xù)實(shí)驗(yàn)采用等距取樣的方法。

3.3 實(shí)驗(yàn)與分析

再次選取32 000個(gè)取樣點(diǎn)做測試，在離線階段測得各個(gè)點(diǎn)的RSSI值，將其保存在指紋庫內(nèi)。在線階段時(shí)再對每個(gè)點(diǎn)RSSI依次運(yùn)算做比較，結(jié)果為：正確點(diǎn)數(shù)為29 865個(gè)，錯(cuò)誤點(diǎn)數(shù)為2 185個(gè)。

依次取不同樣本點(diǎn)數(shù)，如30 000、25 000、15 000、5 000、2 000再次進(jìn)行測量，測得不同誤差下的概率如表3所示。

誤差的大小隨采樣點(diǎn)數(shù)的減少而增大，而較多的采樣點(diǎn)數(shù)會(huì)增加計(jì)算與查找時(shí)間。為此，研究者需要確定一個(gè)合適的點(diǎn)數(shù)來滿足工程中一定的條件，而時(shí)間大部分用于程序的訓(xùn)練。當(dāng)采樣點(diǎn)數(shù)為5 000次時(shí)，訓(xùn)練次數(shù)分別為1 000、2 000、3 000、4 000，比較運(yùn)行時(shí)間與誤差均值的大小可知，在4 000次下有最小的誤差。以4 000次訓(xùn)練次數(shù)為準(zhǔn)，分別取20 000、15 000、10 000、8 000、6 000、4 000、2 000個(gè)點(diǎn)數(shù)。經(jīng)過多次模擬可知，當(dāng)采樣點(diǎn)數(shù)為6 000時(shí)具有最小的誤差，其值為1.42 m。

4 結(jié)論

本文對實(shí)驗(yàn)所需的參數(shù)，如采樣點(diǎn)數(shù)、采樣方式、學(xué)習(xí)次數(shù)以及機(jī)器參數(shù)等，作出一個(gè)合理的選擇，得出良好的定位效果;但因?qū)嶒?yàn)裝備精度、運(yùn)算能力及環(huán)境等因素的影響，無法推廣到所有的應(yīng)用場合中。在后續(xù)的研究中，重點(diǎn)放在AP取點(diǎn)位置、K聚類算法的優(yōu)化、對RSSI濾波的最優(yōu)化等問題的研究上。

參考文獻(xiàn)：

[1]王建林.基于WIFI和多用戶組群的室內(nèi)定位系統(tǒng)[D].西安：西安電子科技大學(xué)，2017.

[2]鄭文翰.基于WLAN的室內(nèi)定位技術(shù)研究與實(shí)現(xiàn)[D].成都：電子科技大學(xué)，2016.

[3]王亞敏.全卷積神經(jīng)網(wǎng)絡(luò)在眼底圖像結(jié)構(gòu)中的應(yīng)用研究[D].成都：電子科技大學(xué)，2019.

收稿日期：2020-04-10

基金項(xiàng)目：吉林省大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練大賽“室內(nèi)導(dǎo)盲機(jī)器人”（201910186088）。

作者簡介：高作相（1998—），男，本科在讀，研究方向：單片機(jī)控制;賀育茹（1999—），女，本科在讀，研究方向：信號的檢測與處理。

通信作者：宗傳林（1998—），男，本科在讀，研究方向：機(jī)器學(xué)習(xí)在通信系統(tǒng)中的應(yīng)用。