基于線性化數(shù)據(jù)處理的位置指紋算法

丁緒星，王兵兵

(安徽師范大學(xué) 物理與電子信息學(xué)院,安徽 蕪湖 241000)

基于線性化數(shù)據(jù)處理的位置指紋算法

丁緒星，王兵兵

(安徽師范大學(xué) 物理與電子信息學(xué)院,安徽 蕪湖 241000)

為了進(jìn)一步提高室內(nèi)定位精度，提出了一種改進(jìn)的位置指紋定位算法。該算法離線階段采集采樣點信號強度構(gòu)建數(shù)據(jù)庫，在線階段采用線性擬合和最小二乘法相結(jié)合求出待測點的估計位置。仿真結(jié)果表明，改進(jìn)的算法尤其適用于不大于10 m*10 m的小區(qū)域網(wǎng)絡(luò)的高精度定位，與傳統(tǒng)的位置指紋算法相比較，改進(jìn)的位置指紋定位算法使得平均定位誤差降低了22.2%，提高了定位精度。

位置指紋算法；線性擬合；最小二乘法；高精度

0 引言

隨著移動通信和無線網(wǎng)絡(luò)的發(fā)展，位置服務(wù)已經(jīng)在大型停車場、物品查找、醫(yī)療和商場等大眾公共服務(wù)領(lǐng)域得到越來越多的應(yīng)用[1-3]，其中，定位的精度是決定位置服務(wù)質(zhì)量的關(guān)鍵。目前，室內(nèi)定位應(yīng)用較多的算法是位置指紋定位算法。

位置指紋是根據(jù)接收的信號強度[4-5]矢量與定位位置存在一一對應(yīng)關(guān)系，而進(jìn)行的位置估計。位置指紋定位算法根據(jù)數(shù)據(jù)庫信號指紋表示的不同可分為2類：① 基于概率的定位方法，該方法通過條件概率為位置指紋建立模型，采用貝葉斯方法來估計待測點的位置[6]；② 確定性定位算法，該方法常見的算法有最近鄰法、KNN算法及WKNN算法等。針對傳統(tǒng)位置指紋定位算法定位精度不夠，近年來,很對學(xué)者們提出很多不同的改進(jìn)算法。文獻(xiàn)[7]提出了EKNN算法，該算法提高了定位精度，但運算量較大。文獻(xiàn)[8]基于能效的WLAN室內(nèi)定位系統(tǒng)模型設(shè)計與實現(xiàn)采用分步定位：粗定位和精定位，在一定程度上減小了計算量，提高了定位精度。文獻(xiàn)[9]提出了指數(shù)加權(quán)KNN算法，對定位精度有一定程度的提高。文獻(xiàn)[10]提出采用位置指紋與粒子群和克里金(Kriging)空間插值算法相結(jié)合的方法，其減小了定位誤差，但算法比較復(fù)雜。針對位置指紋定位精確度有待提高，或者定位精度高但是算法復(fù)雜，提出了在位置指紋定位算法的在線階段采用線性化擬合的方法來進(jìn)行數(shù)據(jù)處理，然后改用最大似然估計算法思想對待測點進(jìn)行位置估計，并與最大似然估計和加權(quán)KNN算法比較，仿真結(jié)果證明，在小區(qū)域范圍定位中，改進(jìn)的算法進(jìn)一步提高了定位精度。

1 位置指紋定位算法

1.1 位置指紋算法

位置指紋[11-12]定位是采用RSSI信號強度，進(jìn)行特征匹配的算法。其算法分為2個階段：離線階段和在線階段。

離線階段：該階段主要確定參考點和各個采樣點的信號強度與位置來構(gòu)建指紋數(shù)據(jù)庫。數(shù)據(jù)庫如表1所示。

表1 位置指紋數(shù)據(jù)庫

在線階段：該階段通過采集待測點的信號強度值，利用歐式距離匹配算法與指紋數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行比較、匹配，從而找到最佳相似點，最后得到待測點的位置估計。其中，待測點的信號強度為(RSS1,RSS2,…,RSSn)，則與第i個的采樣點的歐氏距離如下所示：

(1)

1.2 改進(jìn)算法采用的信號傳播模型

在本文仿真中，選用的是室內(nèi)對數(shù)損耗傳播模型[13-14]，該模型綜合考慮室內(nèi)的復(fù)雜環(huán)境，能比較精確地反應(yīng)無線信號在室內(nèi)的傳播損耗，公式如下：

(2)

式中，PL(d)為接收信號強度，PL(d0)為d0m處接收信號強度，n為路徑損耗系數(shù)，XdBm為噪聲誤差。

1.3 改進(jìn)算法的算法過程

首先，對于距離比較近的2點，其信號強度與距離之間可以看成線性關(guān)系。對于位置指紋定位在線階段，找到k個相似點，假定k= 2，則這2個點接收到各個AP點的信號強度分別為(RSS1i,RSS2i,…,RSSni)和(RSS1j,RSS2j,…,RSSnj)，這2個點的位置分別為(xi,yi)和(xj,yj)。待測點測得的信號強度為(RSS1,RSS2,…,RSSn)，其位置為(x,y)。因為待測點和這2個相似點的距離較近，它們的信號強度變化與距離變化近似成線性關(guān)系。可以由相似點的信號強度和到AP點的距離建立一個線性方程，之后把待測點的信號強度帶入方程得到待測點到AP點的距離。例如：如果相似點到AP1的距離已知為分別為d1i和d1j，因為其接受到AP1的信號強度分別為RSS1i和RSS1j，從而得出線性方程為：

(3)

其次，將待測點對于AP1的信號強度RSS1帶入式(3)中，得到該待測點到AP1的距離d1，同理可以得出待測點到其他各個AP點的距離，假定分別為d2、d3、…、dn。每一個錨節(jié)點AP的位置點已知，分別為(xAP1,yAP1)、(xAP2,yAP2)、…、(xAPn,yAPn),由此可以得出如下方程組：

(4)

因為上面方程組為非線性方程組，不易求解。將式(4)線性化處理后，其轉(zhuǎn)化求下面方程組：

(5)

考慮到誤差的存在，因為方程組不一定有解，將上面方程組的每個方程右側(cè)加上一個誤差，使得方程組有解，改后的方程如下所示：

(6)

令：

(7)

得：

(8)

最后,最小二乘法使δ22+δ32+…+δn2的結(jié)果最小，由式(8)解出x、y的值，即可得出待測點的估計位置。

2 仿真實驗

采用無線傳感網(wǎng)絡(luò)仿真平臺Atos—SensorSim對本文算法進(jìn)行仿真，同時與最大似然估計算法和加權(quán)KNN算法進(jìn)行了仿真對比。在10m*10m環(huán)境中設(shè)置100個采樣節(jié)點，節(jié)點間間隔1m，如圖1所示。同時，在該區(qū)域的邊緣設(shè)置4個錨節(jié)點(標(biāo)號AP1、AP2、AP3和AP4)，區(qū)域內(nèi)設(shè)置6個待測點(標(biāo)號TP1、TP2、TP3、TP4、TP5和TP6)，分布如圖2所示。

圖1 離線階段采樣點位置

圖2 在線階段待測點位置

采用式(2)信號傳播模型，各參數(shù)設(shè)置如下：

d0=1 m;PL(d0)=-62dBm;n = 2.4;

XdBm=N(0,2)。

對于改進(jìn)的定位算法當(dāng)k取不同值時，其定位誤差如圖3所示。

當(dāng)k取值越小，則參考點離測試點越近，則其線性度越好，定位誤差越小。如圖3所示，當(dāng)k=2時定位誤差最大值為0.28 m，平均定位誤差是0.21 m；當(dāng)k= 3時，定位誤差的最大值是0.68 m，平均定位誤差是0.44 m；當(dāng)k= 4時，定位誤差的最大值是0.72 m，平均定位誤差是0.48 m，理論與實際相符。綜合上述，在10 m*10 m的小區(qū)域定位中，本文算法在k取2時取得最佳定位精度。以下仿真中k取值為2。

圖3 改進(jìn)算法在不同網(wǎng)絡(luò)中定位誤差

對于改進(jìn)的算法，在不同的網(wǎng)絡(luò)中進(jìn)行仿真，其各個點的位置與網(wǎng)絡(luò)按照同比例放大。其仿真結(jié)果如圖4所示。

圖4 不同網(wǎng)絡(luò)定位誤差

由式(2)所示，隨著距離的增加，信號強度迅速減小，在10 m內(nèi)，其信號強度隨距離變化明顯。當(dāng)距離達(dá)到一定程度，距離增加，信號強度幾乎不變，這就會造成其定位誤差較大。

如圖4所示，可以看出，隨著網(wǎng)絡(luò)規(guī)格的增大，本文算法的定位誤差隨之增大，在15 m*15 m大小的網(wǎng)絡(luò)中，該算法的平均定位誤差為1.86 m，在20 m*20 m的網(wǎng)絡(luò)中，算法的平均定位誤差達(dá)到了4.46 m，而在10 m*10 m大小的網(wǎng)絡(luò)中，該算法的定位誤差小于0.3 m。由上述易知，理論與實際相符，本文改進(jìn)的定位算法適用于10 m*10 m的小區(qū)域定位，且具有較高的定位精度。

在10 m*10 m的網(wǎng)絡(luò)中，分別使用最大似然估計，傳統(tǒng)的位置指紋定位加權(quán)算法和改進(jìn)的位置指紋定位算法測得待測點位置誤差結(jié)果如圖5所示。

圖5 不同算法測量誤差

如圖5所示，在k=2情況下，加權(quán)KNN算法定位誤差平均值為0.35 m，而本文提出的算法定位的平均誤差為0.28 m，最大似然估計算法定位的平均誤差為0.7 m。相較于最大似然估計算法，本文提出的算法定位精確度提高了近60%；相較于加權(quán)KNN算法，本文提出的定位算法定位精確度提高了22.2%。綜上所述，在10 m*10 m的小區(qū)域室內(nèi)定位中，相較于最大似然估計和傳統(tǒng)的位置指紋定位加權(quán)算法，本文算法降低了定位誤差，提高了定位精確度。

3 結(jié)束語

本文對位置指紋定位算法在線階段的處理數(shù)據(jù)，提出一種新算法。這種算法前期處理和傳統(tǒng)KNN算法相同，根據(jù)歐氏距離找到與待測點最相似的k(k= 2定位誤差最小)個點，之后本算法使用線性擬合的方法，算出待測點到錨節(jié)點的距離，因為錨節(jié)點坐標(biāo)已知，所以列出方程組求解未知數(shù)即可得到待測點的位置，其位置定位比傳統(tǒng)KNN算法定位精度更高。在研究過程中發(fā)現(xiàn)，該改進(jìn)算法只適用不大于10 m*10 m的小區(qū)域網(wǎng)絡(luò)的高精度定位，可應(yīng)用于倉庫管理、圖書管理及物品查找等場合。當(dāng)網(wǎng)絡(luò)較大時，可以使用蜂窩技術(shù)，將大網(wǎng)絡(luò)化為若干個小網(wǎng)絡(luò)進(jìn)行高精度定位。

[1] Rodriguez M D,Favela J,Martinez E A,et al.Location-aware Access to Hospital Information and Services[J].Information Technology in Biomedicine IEEE Transactions on,2004,8(4):448-455.

[2] Harroud H,Ahmed M,Karmouch A.Policy-driven Personalized Multimedia Services for Mobile Users[J].Mobile Computing IEEE Transactions on,2003,2(1):16-24.

[3] Krumm J,Scott J,Hazas M.Location-Aware Computing Comes of Age[J].Computer,2004,37(2):95-97.

[4] Yu F,Jiang M,Liang J,et al.An Indoor Localization of WiFi Based on Branch-bound Algorithm[C]∥ International Conference on Information Science,Electronics and Electrical Engineering.IEEE,2014:1306-1308.

[5] Serodio C,Coutinho L,Pinto H,et al.A Fuzzy Logic Approach to Indoor Location Using Fingerprinting[M].New York:Springer,2013:155-169.

[6] Seigoi I,Nobuo K.Bayesian Based Location Estimation System Using Wireless LAN[C]∥ Pervasive Computing and Communications Workshops,2005.PerCom 2005 Workshops.Third IEEE International Conference on IEEE,2005:273-278.

[7] Shin B,Lee J H,Lee T,et al.Enhanced Weighted K-nearest Neighbor Algorithm for Indoor Wi-Fi Positioning Systems[C]∥ International Conference on Computing Technology and Information Management.IEEE,2012:574-577.

[8] 劉洺辛,孫建利.基于能效的WLAN室內(nèi)定位系統(tǒng)模型設(shè)計與實現(xiàn)[J].儀器儀表學(xué)報,2014,35(5):1169-1178.

[9] Abusara A,Hassan M.Enhanced Fingerprinting in WLAN-based Indoor Positioning Using Hybrid Search Techniques[C]∥ Communications,Signal Processing,and their Applications (ICCSPA),2015 International Conference on IEEE,2015:1-6.

[10]Manirabona A,Fourati L C.A Kriged Fingerprinting for Wireless Body Area Network Indoor Localization[J].Wireless Personal Communications,2014,80(4):1501-1515.

[11]高 鵬,石為人,周 偉,等.基于圖論模糊聚類的室內(nèi)自適應(yīng)RSSI定位算法[J].儀器儀表學(xué)報,2013,34(9):1998-2004.

[12]Widyawan K M,Pesch D.Influence of Predicted and Measured Fingerprint on the Accuracy of RSSI-based Indoor Location Systems[C]∥ in Positioning,Navigation and Communication,2007.WPNC ’07.4th Workshop on 2007:145-151.

[13]Wang X,Qiu J,Ye S,et al.An Advanced Fingerprint-based Indoor Localization Scheme for WSNs[C]∥ Industrial Electronics and Applications (ICIEA),2014 IEEE 9th Conference on IEEE,2014:2164-2169.

[14]Wang B,Zhou S,Liu W,et al.Indoor Localization Based on Curve Fitting and Location Search Using Received Signal Strength[J].IEEE Transactions on Industrial Electronics,2015,62(1):572-582.

Location Fingerprint Algorithm Based on Linear Data Processing

DING Xu-xing,WANG Bing-bing

(School of Physics and Electronic Engineering,Anhui Normal University,Wuhu Anhui 241000,China)

In order to further improve the indoor positioning accuracy,the paper presents an improved location fingerprint positioning algorithm.In the offline stage,the signal strength of the sampling points is collected to build up the database.In the online stage,the linear fitting and the least square method are combined to calculate the estimated location of the test points.The result shows that the improved algorithm is especially suitable for the high-accuracy positioning of small-area networks not more than 10 m10 m.As compared with conventional fingerprinting algorithms,the average positioning error of the improved algorithm is reduced by 22.2%,and the positioning accuracy is improved.

location fingerprint algorithm;linear fitting;least square method;high-accuracy

10.3969/j.issn.1003-3114.2017.02.05

丁緒星,王兵兵.基于線性化數(shù)據(jù)處理的位置指紋算法[J].無線電通信技術(shù),2017,43(2):21-24.

2016-10-10

國家自然科學(xué)基金項目(61401004)；安徽師范大學(xué)創(chuàng)新基金項目(2015cxsj121)

丁緒星(1971—)，男，博士，教授,碩士生導(dǎo)師，主要研究方向:物聯(lián)網(wǎng)技術(shù)、汽車電子、數(shù)字信號處理。王兵兵(1988—)，男，碩士研究生，主要研究方向：物聯(lián)網(wǎng)技術(shù)。

TP393

A

1003-3114(2017)02-21-4