基于RSSI的KNN—PIT室內(nèi)自適應(yīng)定位算法*

唐 瑞， 孫冰潔， 周禮爭(zhēng)， 余 敏

(1.江西師范大學(xué) 軟件學(xué)院，江西 南昌 330022； 2.江西師范大學(xué) 計(jì)算機(jī)信息工程學(xué)院，江西 南昌 330022)

基于RSSI的KNN—PIT室內(nèi)自適應(yīng)定位算法*

唐 瑞1， 孫冰潔1， 周禮爭(zhēng)2， 余 敏2

(1.江西師范大學(xué) 軟件學(xué)院，江西 南昌 330022； 2.江西師范大學(xué) 計(jì)算機(jī)信息工程學(xué)院，江西 南昌 330022)

針對(duì)基于接收信號(hào)強(qiáng)度指示(RSSI)的K最近鄰(KNN)算法在室內(nèi)定位精度較低的問題，提出一種改進(jìn)的KNN—三角形內(nèi)點(diǎn)(KNN—PIT)室內(nèi)定位算法。根據(jù)室內(nèi)空間結(jié)構(gòu)特征，建立具有類標(biāo)號(hào)的位置指紋庫(kù)。引入虛擬參考點(diǎn)，利用PIT原理進(jìn)一步約束目標(biāo)點(diǎn)的定位區(qū)域，自適應(yīng)地使用定位算法進(jìn)行定位。綜合運(yùn)用高斯濾波、均值濾波技術(shù)，降低離線和在線階段的信號(hào)隨機(jī)誤差。結(jié)果表明：改進(jìn)后的KNN—PIT定位算法可以更好地估計(jì)用戶的實(shí)際位置，降低定位誤差，定位精度提高12.5 %。

室內(nèi)定位； K最近鄰； 三角形內(nèi)點(diǎn)； 虛擬參考點(diǎn)； 自適應(yīng)

0 引 言

隨著通信技術(shù)的發(fā)展，全球定位系統(tǒng)(global positioning system，GPS)已成為室外導(dǎo)航定位中的主要技術(shù)。但是，在人類活動(dòng)密集的地方，如,大型購(gòu)物中心、辦公樓、圖書館等復(fù)雜環(huán)境中，GPS因信號(hào)受干擾、遮擋等不能精確定位?；诮邮招盘?hào)強(qiáng)度指示(received signal strength indication，RSSI)的室內(nèi)定位技術(shù)成為研究的熱點(diǎn)[1,2]。目前研究的熱點(diǎn)包括如何降低離線指紋庫(kù)采集的工作量、減少在線匹配的復(fù)雜度、改進(jìn)算法提高定位實(shí)時(shí)性與準(zhǔn)確性[3,4]。

文獻(xiàn)[5]指出K最近鄰(K-nearest neighbor，KNN)算法中K參數(shù)的改變與定位精度不存在單一的正比例關(guān)系；文獻(xiàn)[6]提出表征點(diǎn)位幾何特性的點(diǎn)散發(fā)性強(qiáng)度概念，并利用該強(qiáng)度值動(dòng)態(tài)地選擇KNN參數(shù)K；文獻(xiàn)[7]用主成分分析(principal component analysis，PCA)和最小二乘支持向量回歸機(jī)(least square support vector regression，LSSVR)實(shí)現(xiàn)數(shù)據(jù)降維和位置回歸預(yù)測(cè)；文獻(xiàn)[8]結(jié)合煤礦井下環(huán)境提出一種自適應(yīng)RSSI三角質(zhì)心定位算法；文獻(xiàn)[9]研究了RSSI值與幾何距離的關(guān)系，提出了一種基于特征尺度的KNN。

由于RSSI受到多徑效應(yīng)、陰影效應(yīng)等的影響，本文在離線階段，對(duì)樣本數(shù)據(jù)進(jìn)行高斯濾波，獲得表征較為真實(shí)的位置指紋數(shù)據(jù)，在線階段使用均值濾波降低實(shí)時(shí)采樣RSSI帶來(lái)的較大誤差。利用最佳三角形內(nèi)點(diǎn) (point in triangulation，PIT) 測(cè)試法和虛擬點(diǎn)進(jìn)一步約束定位點(diǎn)的所屬區(qū)域，提出KNN—PIT算法，自適應(yīng)地使用定位算法進(jìn)行定位。

1 具有類標(biāo)號(hào)的位置指紋庫(kù)構(gòu)建

基于RSSI位置指紋的室內(nèi)定位方法分為離線信號(hào)采集構(gòu)建指紋庫(kù)階段和在線實(shí)時(shí)定位兩個(gè)階段。離線階段，在待定位區(qū)域建立平面坐標(biāo)系并劃分網(wǎng)格，以網(wǎng)格點(diǎn)作為參考點(diǎn)(reference point，RP)。在各RP上采集周邊各接入點(diǎn)(access point，AP)的RSSI，建立各個(gè)參考點(diǎn)對(duì)應(yīng)的位置和信號(hào)強(qiáng)度的關(guān)系，即位置指紋庫(kù)。

具有類標(biāo)號(hào)的位置指紋庫(kù)在傳統(tǒng)指紋庫(kù)中添加新的屬性，即類標(biāo)簽。根據(jù)室內(nèi)的空間結(jié)構(gòu)特征，將各區(qū)域的RP歸為一類，位置指紋庫(kù)如表1所示。

表1 具有類標(biāo)號(hào)的指紋庫(kù)

位置指紋集為S={(L1,R1,C1),(L2,R2,C2),…,(Ln,Rn,Cn),Rn={RSSIn1,RSSIn2,…,RSSInm}∈Rm,Cn∈{1,2,…,j)，其中,Ln=(xn,yn)表示參考點(diǎn)n的二維位置坐標(biāo),RSSInm表示參考點(diǎn)n處接收第m個(gè)AP的信號(hào)強(qiáng)度值,Cn表示參考點(diǎn)n的類標(biāo)號(hào)，取值為1～j。

2 KNN與PIT原理

KNN定位算法首先計(jì)算定位點(diǎn)處測(cè)得的RSSI向量與各RP點(diǎn)測(cè)得的RSSI向量的余弦相似度。兩向量的余弦相似度如下所示

(1)

然后在位置指紋庫(kù)中尋找最接近的k個(gè)RSSI向量。由于指紋庫(kù)中每個(gè)RSSI向量唯一對(duì)應(yīng)一個(gè)參考點(diǎn)的二維坐標(biāo)。最終定位點(diǎn)的位置估計(jì)為k個(gè)參考點(diǎn)二維坐標(biāo)的加權(quán)值，第i個(gè)參考點(diǎn)的權(quán)值為wi

(2)

其中，si為第i個(gè)參考點(diǎn)與定位點(diǎn)的空間相似度。最終定位點(diǎn)的位置估計(jì)為

(3)

PIT原理如圖1所示。當(dāng)存在一個(gè)方向，節(jié)點(diǎn)T沿著這個(gè)方向移動(dòng)會(huì)同時(shí)遠(yuǎn)離或接近三角形頂點(diǎn)A,B和C，判定該節(jié)點(diǎn)不在三角形內(nèi);否則,判定該節(jié)點(diǎn)在三角形內(nèi)。

圖1 PIT原理

目前數(shù)學(xué)理論上還有面積法、內(nèi)角和法、同向法等判定一點(diǎn)T是否在三角形ABC中。本文采用面積法定性的判斷定位點(diǎn)是否在三角形內(nèi)，使用空間向量之間的距離代替指紋點(diǎn)之間的距離。

設(shè)三角形頂點(diǎn)坐標(biāo)A,B和C處的位置指紋為： (LA,RA,CA),(LB,RB,CB)和(LC,RC,CC)。定位點(diǎn)處的RSSI向量為RT,則

(4)

由秦九韶—海倫公式得三角形ABC的面積SABC為

(5)

同理，可計(jì)算SABT,SBCT和SACT，若SABC=SABT+SBCT+SACT，判定定位點(diǎn)在三角形ABC內(nèi);否則，判定定位點(diǎn)在三角形外。實(shí)際實(shí)驗(yàn)時(shí)，由于存在信號(hào)的隨機(jī)誤差，假定滿足SABC-(SABT+SBCT+SACT)<δ，δ為設(shè)定的閾值，即認(rèn)為點(diǎn)在三角形內(nèi)。

3 自適應(yīng)的KNN—PIT定位算法

根據(jù)無(wú)線信號(hào)傳播理論，當(dāng)兩點(diǎn)比較近時(shí)，中間點(diǎn)處的RSSI可由兩點(diǎn)RSSI的均值近似代替，因此,可以添加虛擬參考點(diǎn)進(jìn)一步約束定位點(diǎn)的所在區(qū)域，實(shí)現(xiàn)更精確的定位。但是，若參考點(diǎn)不在同一類時(shí)，表明中間有墻體阻隔，引入虛擬點(diǎn)可能帶來(lái)更大的定位誤差。同時(shí)，若k個(gè)參考點(diǎn)在同一直線上則無(wú)法構(gòu)成三角形，因此，需要分類討論。

3.1KNN算法匹配前3個(gè)點(diǎn)屬同一類

如圖2所示，KNN匹配前3個(gè)參考點(diǎn)K1,K2,K3同類但不構(gòu)成三角形，引入K4，且K4與原參考點(diǎn)屬于同一類。增加虛擬參考點(diǎn)P，P點(diǎn)處的RSSI由K1和K4的RSSI均值代替。通過(guò)面積法計(jì)算得定位點(diǎn)在三角形K1K2P內(nèi)，則定位點(diǎn)T的位置估計(jì)為

(6)

圖2 K1,K2,K3不構(gòu)成三角形

如圖3所示，K1,K2和K3屬于同一類且構(gòu)成三角形，通過(guò)面積法計(jì)算得定位點(diǎn)在三角形K1K2P內(nèi)，則定位點(diǎn)T的位置估計(jì)由式(6)得出。

圖3 在未調(diào)整的三角形內(nèi)

如圖4所示，K1,K2和K3屬于同一類且構(gòu)成三角形，但定位點(diǎn)不在虛擬點(diǎn)P組成的三角形K1K2P和K2K3P內(nèi)。引入K4參考點(diǎn)，通過(guò)面積法計(jì)算得定位點(diǎn)在三角形K1K4P內(nèi)，則定位點(diǎn)T的位置估計(jì)為

(7)

圖4 在調(diào)整后的三角形內(nèi)

如圖5所示，K1,K2和K3屬于同一類且構(gòu)成三角形，但定位點(diǎn)不在三角形K1K2P和K2K3P內(nèi)，引入K4與原參考點(diǎn)不屬同一類，則定位點(diǎn)T的位置估計(jì)為

(8)

圖5 K1,K2,K3,K4不同類

3.2 KNN算法匹配前3個(gè)點(diǎn)不屬同一類

如圖6所示，K1,K2和K3不屬于同一類,則定位點(diǎn)T的位置估計(jì)由式(8)得出。

圖6 K1,K2,K3不同類

綜上，自適應(yīng)的KNN—PIT定位模型如圖7所示。

圖7 KNN—PIT定位模型

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

為了檢測(cè)本文提出的KNN—PIT算法在室內(nèi)的定位效果，實(shí)驗(yàn)在先骕樓7樓進(jìn)行。實(shí)驗(yàn)環(huán)境的平面圖如圖8所示，參考點(diǎn)間距為2m，AP型號(hào)為TL—WR885N，移動(dòng)采集終端為華為手機(jī)G606。

圖8 空間結(jié)構(gòu)和AP的布局

為了降低RSSI不穩(wěn)定的影響，各參考點(diǎn)采集各AP的RSSI值300次。通過(guò)大量實(shí)測(cè)數(shù)據(jù)分析，在某一點(diǎn)處測(cè)得某一AP的RSSI值整體呈正態(tài)分布，如圖9所示。

圖9 某點(diǎn)處采集某AP的RSSI值

本文離線階段采用高斯濾波技術(shù)，舍棄發(fā)生概率較低的數(shù)值，對(duì)高概率發(fā)生數(shù)值求均值，降低信號(hào)噪聲影響。在線階段使用均值濾波技術(shù)，將實(shí)時(shí)采集的若干次RSSI求均值作為實(shí)時(shí)RSSI，降低信號(hào)的隨機(jī)誤差。

考慮離線階段樣本采樣次數(shù)影響離線階段的工作量，也可能直接影響室內(nèi)定位的精度。隨機(jī)以RSSI值采樣次數(shù)為30,60,90,120,150,180,210,240,270和300次進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖10所示。

圖10 KNN和KNN—PIT算法對(duì)比

圖10表明:當(dāng)位置指紋點(diǎn)采集的RSSI次數(shù)相同時(shí)，KNN—PIT算法在室內(nèi)定位中具有更高的精度，定位精度平均提高12.5 %。

為了驗(yàn)證在實(shí)時(shí)定位時(shí)均值濾波的效果和必要性，進(jìn)行單次RSSI和3次RSSI作均值濾波處理對(duì)比實(shí)驗(yàn),每次定位誤差的實(shí)驗(yàn)結(jié)果如圖11所示。

由圖11知，使用單次測(cè)得的RSSI進(jìn)行定位，定位誤差波動(dòng)性較大，而使用均值濾波技術(shù)后，定位誤差基本穩(wěn)定在1.40m左右，標(biāo)準(zhǔn)差小，具有更好的適應(yīng)性。

圖11 定位階段是否使用均值濾波技術(shù)的定位誤差

5 結(jié) 論

本文采用KNN—PIT算法進(jìn)行室內(nèi)定位，不僅有效降低了傳統(tǒng)KNN算法在室內(nèi)定位的較大誤差，而且可以在不同環(huán)境下自適應(yīng)地定位。實(shí)驗(yàn)表明:改進(jìn)后的算法具有更高的定位精度和可靠性。

[1]GuYanying,LoANiemegeersI.Asurveyofindoorpositioningsystemsforwirelesspersonalnetworks[J].CommunicationsSurveys&Tutorials,IEEE,2009,11(1):13-32.

[2]PrietoJ,MazuelasS,BahilloA,etal.Adaptivedatafusionforwirelesslocalizationinharshenvironments[J].IEEETransactionsonSignalProcessing,2012,60(4):1585-1596.

[3]JiangJoeAir,ZhengXiangyao,ChenYuan,etal.AdistributedRSS-basedlocalizationusingadynamiccircleexpandingmechanism[J].IEEESensorsJournal,2013,13(10):3754-3766.

[4] 花 超,吉小軍,蔡 萍,等.基于RSSI差分修正的加權(quán)質(zhì)心定位算法[J].傳感器與微系統(tǒng),2012,31(5):139-141.

[5]HonkavirtaV,PeralaT,Ali-LoyttyS,etal.AcomparativesurveyofWLANlocationfingerprintingmethods[C]∥WPNC2009,Hannover,Germany,2009:243- 251.

[6] 劉春燕,王 堅(jiān).基于幾何聚類指紋庫(kù)的約束KNN室內(nèi)定位模型[J].武漢大學(xué)學(xué)報(bào)·信息科學(xué)版，2014,39(11):1287-1292.

[7] 張 勇,黃 杰,徐科宇.基于PCA-LSSVR算法的WLAN室內(nèi)定位方法[J].儀器儀表學(xué)報(bào),2015,36(2):408-414.

[8] 曹開來(lái),余 敏.無(wú)線傳感器網(wǎng)絡(luò)煤礦井下RSSI自適應(yīng)定位算法[J].傳感器與微系統(tǒng),2014,33(6):129-132.

[9]LiDong,ZhangBaoxian,YaoZheng,etal.Afeaturescalingbasedk-Nearestneighboralgorithmforindoorpositioningsyste-m[C]∥GlobalCommunicationsConference,Austin,TX,2014:436-441.

Indoor adaptive KNN-PIT positioning algorithm based on RSSI*

TANG Rui1, SUN Bing-jie1, ZHOU Li-zheng2, YU Min2

(1.School of Software,Jiangxi Normal University,Nanchang 330022,China; 2.School of Computer Information and Engineering,Jiangxi Normal University,Nanchang 330022,China )

Aiming at problem of KNN algorithm low precision of indoor positioning based on RSSI,an improved KNN—PIT indoor positioning algorithm is put forward.According to structure feature of indoor space,establish location fingerprint database which has class labels.Introduce virtual reference points,use theory of PIT to further constrain localization area of target point,use positioning algorithm adaptively to carry out positioning. Comprehensively use Gauss filtering and mean filtering to reduce random errors of signal in online and offline stages.Results show that the improved KNN—PIT algorithm can better estimate the user’s actual location,and decrease significantly localization errors,positioning precision is improved by 12.5 %.

indoor positioning; K-nearest neighbor(KNN); point in triangulation(PIT); visual reference points; adaptive

10.13873/J.1000—9787(2015)07—0128—04

2015—05—11

國(guó)家自然科學(xué)基金資助項(xiàng)目(41374039)； 中國(guó)—波蘭國(guó)際科技合作項(xiàng)目(35—14)

TP 393

A

1000—9787(2015)07—0128—04

唐 瑞(1991-)，男，安徽合肥人，碩士研究生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)、室內(nèi)定位。