文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.180768
中文引用格式: 王培良,張婷,肖英杰. 改進指紋庫精度下的室內(nèi)定位算法研究[J].電子技術應用,2018,44(10):97-101,105.
英文引用格式: Wang Peiliang,Zhang Ting,Xiao Yingjie. Research on indoor positioning algorithm based on improved fingerprint library accuracy[J]. Application of Electronic Technique,2018,44(10):97-101,105.
0 引言
隨著無線傳感器網(wǎng)絡(WSN)技術的不斷發(fā)展,基于位置感知的服務和計算在實際中得到廣泛使用。目前,室內(nèi)定位技術主要有:超聲波[1]、紅外線、RFID[2]、WiFi、UWB[3]等技術。本文使用成本低、功耗低、復雜度低的德州儀器公司CC2530芯片基于ZigBee協(xié)議進行研究,通過節(jié)點間的接收信號強度指示(Received Signal Strength Indication,RSSI)值進行室內(nèi)定位。依據(jù)定位算法過程中是否使用節(jié)點間距離,定位方式分為基于測距和非測距方式兩種,本文使用的指紋數(shù)據(jù)庫即為非測距方式。
指紋數(shù)據(jù)庫定位需經(jīng)歷兩個階段:離線建庫階段和在線定位階段[4-5],其原理如圖1所示。在離線建庫階段,通過采集預設定的接入點(Access Point,AP)與各參考節(jié)點(Reference Point,RP)之間的RSSI值來建立原始指紋庫[6-8]。文獻[9]通過使用K-Means聚類算法,實現(xiàn)眾包指紋庫建模。本文在采集原始數(shù)據(jù)的基礎上,通過離群點檢測發(fā)現(xiàn)其與大部分數(shù)據(jù)存在顯著差別的數(shù)據(jù)對象,將其視為噪聲而丟棄,然后使用雙閾值濾波處理得到最終的高精度指紋數(shù)據(jù)庫。
在線定位階段,通過將實時采集到的待測點RSSI值與指紋數(shù)據(jù)庫中的數(shù)據(jù)集進行比對,計算得到待測節(jié)點的位置坐標。廣泛使用的典型定位算法主要包括核函數(shù)法、最近鄰法、最大似然概率法以及樸素貝葉斯法。文獻[10]-[12]通過研究提出增強型的聚類策略、權值算法以及優(yōu)化質(zhì)心等,可顯著提升定位速度和精度。上述研究方法通常易受待測點RSSI值波動的影響,同時在計算速度和精度上難以滿足要求。本文通過使用FCM算法將待測節(jié)點的RSSI值進行聚類,從而剔除跳變點,然后使用基于頻率因子的加權K最鄰近算法(Weighting K-Nearest Neighbor,WKNN),計算得到待測點的位置,并且給出“備用位置”。
1 理論與方法
1.1 離線建庫階段
高精度指紋數(shù)據(jù)庫的建立是提高定位準確度的前提條件[13]。由于在AP點進行信息采集時,其數(shù)據(jù)存在大量噪聲影響指紋庫的精度,因此本文使用下述方法提高建庫精度。
假定定位區(qū)域網(wǎng)格化后有m個AP和n個RP,其分別記為集合{AP1,AP2,…,APm}、{RP1,RP2,…,RPn},其中m值亦為每個AP點的標簽,且每個AP接收到s組數(shù)據(jù),記為:
1.1.1 離群點檢測方法
本文首先使用基于聚類分析的離群點檢測算法將原始數(shù)據(jù)中噪聲去除,其步驟:
(1)選擇合適的聚類算法對RSSIn進行聚類分析,本文使用K-Means算法。
(2)計算RSSIn中各點與最近質(zhì)心的歐式距離,公式為:
其中,Z表示各類質(zhì)心的坐標。
(3)與給定的閾值η1進行比較,若Di>η1,則該RSSIi視為離群點,并將該點從源數(shù)據(jù)中剔除。
1.1.2 雙閾值濾波方法
在進行離群點檢測時,某些離群點可能形成小簇從而逃避檢測,因此需要使用雙閾值濾波對其進一步處理。首先對數(shù)據(jù)進行數(shù)據(jù)頻率閾值濾波,設頻率閾值為:
1.2 在線定位階段
為剔除待測節(jié)點RSSI值的噪聲,同時為增大數(shù)據(jù)有效性,本文在在線定位階段使用基于FCM與WKNN相結(jié)合的方法對數(shù)據(jù)進行處理。
1.2.1 FCM算法論述
具體過程如下:首先用加權指數(shù)m和分類數(shù)c初始化隸屬度矩陣,然后重復迭代使用式(7)、式(8)求解聚類中心和新的隸屬度矩陣并將結(jié)果待入式(6),直到Jm(U,V)小于給定的正數(shù)ε或者達到最大迭代步長,則聚類過程結(jié)束,得到待測節(jié)點數(shù)據(jù)集X={x1,x2,…,xi},其中i∈(1,l)表示聚類之后的數(shù)據(jù)量。
1.2.2 WKNN算法論述
最鄰近定位算法通過計算待測節(jié)點的RSSI實時測量值與指紋庫中各對應指紋數(shù)據(jù)之間的歐式距離,從中搜尋距離最小的指紋點,然后將各個指紋數(shù)據(jù)通過平均或加權平均作為待測目標的位置。歐式距離計算公式如下:
其中,Ij表示距離最近的前K個AP節(jié)點所分別對應的標簽值。
為防止出現(xiàn)小概率性的錯誤定位問題,本文同時給出待測節(jié)點的“備用位置”作為參考。其原理為使用上述加權K最鄰近定位算法迭代計算出與待測節(jié)點相近的多個節(jié)點并進行排序(其中Lc計算出的位置節(jié)點除外),選擇前2~4位節(jié)點作為待測節(jié)點的方向估計,第1位節(jié)點作為待測節(jié)點的“備用位置”估計。
2 實驗結(jié)果及分析
本文選用信號干擾強、設備多、使用環(huán)境復雜的校園多媒體教室進行實驗,選定其中20 m×20 m的為本次實驗區(qū)域。
在本實驗的離線建庫階段,共設置100個AP節(jié)點,每個AP節(jié)點連續(xù)采集120 s的信號強度值數(shù)據(jù),然后對本段時間內(nèi)的數(shù)據(jù)進行處理從而建立指紋庫。下面選取第4個AP節(jié)點數(shù)據(jù)進行分析,其原始數(shù)據(jù)如圖2所示。
為清晰表達算法處理過程,后續(xù)處理時以本節(jié)點的REF1參考節(jié)點數(shù)據(jù)值為對象,且RSSI值繪圖時使用其絕對值表示。
2.1 指紋庫建立
首先對數(shù)據(jù)值進行離群點檢測,其中設定離散點閾值為0.7,最大迭代次數(shù)設置為500,則處理結(jié)果如圖3所示。
從圖3可知,距離誤差超過閾值的所有點,均視為離群點,應從數(shù)據(jù)集中剔除,以免影響后續(xù)數(shù)據(jù)處理過程。
離群點剔除后對數(shù)據(jù)集進行雙閾值濾波處理,其結(jié)果如圖4所示。
分析圖4可知,數(shù)據(jù)經(jīng)過雙閾值濾波后,能夠進一步抑制噪聲的干擾,并且可降低后續(xù)指紋數(shù)據(jù)庫建立的復雜度。
同理,將此AP點接收的其他REF數(shù)據(jù)進行上述處理,從而得到最終的該AP點對應于每個RP點的指紋數(shù)據(jù),并建立數(shù)據(jù)庫。
2.2 定位結(jié)果
在實驗區(qū)域內(nèi),共設置10個待測節(jié)點,每個節(jié)點連續(xù)采集信號時間亦均為120 s,現(xiàn)選取任意待測點數(shù)據(jù)進行分析,其原始數(shù)據(jù)如圖5所示。
在使用算法對待測節(jié)點數(shù)據(jù)進行分析前,需將其每次接收到的不同RP點的RSSI值進行統(tǒng)一化處理,并將其作為待測節(jié)點數(shù)據(jù)集中的一個觀測值(行屬性),其統(tǒng)計結(jié)果如圖6所示。
然后使用FCM算法對此數(shù)據(jù)集進行處理,其目標函數(shù)中隸屬度冪指數(shù)為3,最大迭代次數(shù)為200,目標函數(shù)的終止容限位1×10-6。經(jīng)反復試驗,最終本文選用分類數(shù)為2,不同分類數(shù)結(jié)果如圖7所示。
對圖7趨勢分析可知,針對本次研究數(shù)據(jù),當分類數(shù)為2時,處理效果優(yōu)于其他分類數(shù)。
最后使用基于頻率因子的WKNN算法對上述分類后的數(shù)據(jù)進行計算,得到待測節(jié)點位置,其定位誤差為1.85 m,備用位置的定位誤差為2.13 m。同理,可得其余待測節(jié)點的位置誤差。通過對比本文研究方法與傳統(tǒng)原始定位方法(未濾波指紋數(shù)據(jù)庫定位和未優(yōu)化FCM+WKNN定位算法),可明顯看出其定位精度的提升,結(jié)果如表1所示。
3 結(jié)論
本文首先通過離群點檢測與雙閾值濾波結(jié)合的方式對不同AP點采集的原始RSSI值數(shù)據(jù)進行處理,建立高精度指紋數(shù)據(jù)庫,然后使用FCM算法對待測節(jié)點的RSSI值進行分類,最后使用WKNN算法計算出待測節(jié)點的位置信息。經(jīng)過實驗證明,本文的研究方法相比于未濾波數(shù)據(jù)庫和未優(yōu)化算法等方式,在定位精度上有明顯提高,并能給出“備用位置”信息。
參考文獻
[1] 葉寶玉,王欽若,熊建斌,等.基于超聲波的模型船舶室內(nèi)定位系統(tǒng)研究[J].計算機工程,2012,38(19):258-260,265.
[2] 馬卜林,楊帆.煤礦井下WiFi人員定位GIS系統(tǒng)設計與實現(xiàn)[J].西安科技大學學報,2012,32(3):301-305.
[3] 肖竹,王勇超,田斌,等.超寬帶定位研究與應用:回顧和展望[J].電子學報,2011,39(1):133-141.
[4] 張翔,熊劍,武和雷,等.基于MNN改進粒子濾波的指紋庫定位算法研究[J].計算機工程與設計,2014,35(7):2283-2288.
[5] 方爽,郭杭,洪海斌,等.一種虛擬空間劃分的室內(nèi)指紋庫定位方法[J].測繪科學,2015,40(1):93-97.
[6] 劉小康,郭杭.基于Zigbee室內(nèi)定位系統(tǒng)的指紋庫優(yōu)化算法[J].計算機工程,2014,40(2):193-198.
[7] HOU Y,SUM G,F(xiàn)AN B.The indoor wireless location technology research based on WiFi[C].International Conference on Natural Computation.IEEE,2014:1044-1049.
[8] GUO S,ZHONG Z,HE T.FIND:faulty node detection for wireless sensor networks[C].ACM Conference on Embedded Networked Sensor Systems.ACM,2009:253-266.
[9] ZHOU M,TIAN Z,XU K,et al.SCaNME: Location tracking system in large-scale campus Wi-Fi environment using unlabeled mobility map[J].Expert Systems with Applications,2014,41(7):3429-3443.
[10] 霍歡,楊滬滬,鄭德原,等.一種改進的RSSI指紋庫定位算法[J].計算機應用研究,2017,34(9):2786-2790.
[11] 戴國華,易靈芝,王根平.一種新的基于ZigBee技術定位算法[J].計算機測量與控制,2012,20(4):1105-1107.
[12] 趙山,彭力.基于ZigBee網(wǎng)絡的移動節(jié)點定位技術研究[J].測控技術,2014,33(10):51-55.
[13] 王頂,馬娟,趙頤軒.基于RSS空時處理的指紋定位算法[J].計算機應用研究,2012,29(12):4726-4728.
作者信息:
王培良1,2,張 婷3,肖英杰1
(1.上海海事大學 商船學院,航運仿真技術教育部工程研究中心,上海201306;
2.濰坊科技學院,山東 濰坊262700;3.山東交通職業(yè)學院,山東 濰坊261206)