一種基于灰色關(guān)聯(lián)度的改進(jìn)位置指紋定位方法

朱 律，沈云中

(同濟(jì)大學(xué) 測繪與地理信息學(xué)院，上海 200092)

?

一種基于灰色關(guān)聯(lián)度的改進(jìn)位置指紋定位方法

朱 律，沈云中

(同濟(jì)大學(xué) 測繪與地理信息學(xué)院，上海 200092)

針對傳統(tǒng)位置指紋算法中沒有充分挖掘和利用原始數(shù)據(jù)中的方差信息的問題，提出一種基于灰色關(guān)聯(lián)度的改進(jìn)加權(quán)K最近鄰法(WKNN)的定位方法：將方差應(yīng)用到關(guān)聯(lián)度的計(jì)算中，通過對關(guān)聯(lián)系數(shù)求加權(quán)平均值，一定程度上削弱了WiFi信號不穩(wěn)定帶來的影響。實(shí)驗(yàn)結(jié)果表明，該方法能有效提高定位精度。

WKNN；灰色關(guān)聯(lián)度；位置指紋算法；精度分析

0 引言

在室外環(huán)境，衛(wèi)星導(dǎo)航技術(shù)已經(jīng)廣泛應(yīng)用于經(jīng)濟(jì)、軍事、生產(chǎn)和生活的各個領(lǐng)域。隨著移動通信與互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，室內(nèi)環(huán)境的定位需求也越來越多。由于室內(nèi)環(huán)境復(fù)雜，存在較為嚴(yán)重的反射、衍射等非視距(non light of sight，NLOS)傳播以及多徑等情況，導(dǎo)致室內(nèi)定位存在著諸多難題[1]。為了克服這些難題，基于紅外線、超寬帶等專用設(shè)備的定位方法采用特殊信號實(shí)現(xiàn)室內(nèi)定位，雖然定位精度很高，但需要預(yù)先部署特定硬件設(shè)備甚至特定的定位終端，導(dǎo)致定位費(fèi)用過高，普適度過低[2]。另一方面，隨著“無線城市”的發(fā)展，國內(nèi)各大城市的公共場所、商業(yè)圈覆蓋了相當(dāng)密集的無線保真(wireless fidelity，WiFi)節(jié)點(diǎn)，這讓最早由美國微軟研究院開發(fā)的基于無線局域網(wǎng)絡(luò)(wireless local area networks，WLAN)的室內(nèi)定位系統(tǒng)[3]有了更為廣闊的發(fā)展和應(yīng)用空間。基于WiFi的室內(nèi)定位技術(shù)，只要求WiFi接入點(diǎn)(access point, AP)發(fā)射信號，利用移動用戶接收和測量的信號就可實(shí)現(xiàn)室內(nèi)定位；對硬件設(shè)備要求很低，能夠顯著降低建設(shè)與運(yùn)營成本，成為室內(nèi)定位的趨勢[4]。目前，基于接收信號強(qiáng)度(received signal strength indication, RSSI)位置指紋的WiFi定位技術(shù)因其在成本、精度、系統(tǒng)復(fù)雜度以及環(huán)境適應(yīng)性等方面的優(yōu)勢，成為室內(nèi)定位系統(tǒng)主要采用的技術(shù)并被廣泛應(yīng)用[5]。根據(jù)保存在數(shù)據(jù)庫中位置指紋記錄的不同形式，可以將指紋定位分為概率分布法和確定性方法2大類。在確定性方法中，由于傳統(tǒng)的最近鄰法(nearest neighbor，NN)和K最近鄰法(K-nearest neighbor，KNN)對移動終端位置估計(jì)效果不佳[6]，一些學(xué)者相繼提出了一些改進(jìn)：如基于群組的指紋定位算法[7]、基于RSSI相關(guān)系數(shù)的指紋定位算法[8]、基于聚類的位置指紋技術(shù)研究[9]等。這些方法在定位階段中，只采用RSSI均值來計(jì)算信號的空間距離，并沒有充分挖掘和利用原始數(shù)據(jù)中的方差信息。

本文將灰色關(guān)聯(lián)分析法[10]引入到位置指紋定位中，把采集信號指紋與實(shí)測信號之間相似度的匹配問題轉(zhuǎn)化為計(jì)算它們之間關(guān)聯(lián)度的問題，提出改進(jìn)的加權(quán)K最近鄰法(weighted K-nearest neighbor, WKNN)算法。首先計(jì)算實(shí)測信號與每個采集信號的關(guān)聯(lián)度，在關(guān)聯(lián)度的計(jì)算過程中，考慮到采集點(diǎn)信號強(qiáng)度分布的方差信息，設(shè)計(jì)出每個AP的計(jì)算權(quán)值，并對每個AP的關(guān)聯(lián)系數(shù)求加權(quán)平均值得到關(guān)聯(lián)度，以削弱RSSI不穩(wěn)定的接入點(diǎn)對關(guān)聯(lián)度計(jì)算的影響。然后對每個采集信號做出綜合比較和排序，在傳統(tǒng)的WKNN定位方法基礎(chǔ)上，以關(guān)聯(lián)度大小的排序結(jié)果代替歐式距離大小的排序結(jié)果，改進(jìn)傳統(tǒng)的WKNN算法。

1 位置指紋定位

1.1 基本原理

位置指紋定位是指通過前期在參考點(diǎn)(reference place，RP)上采集數(shù)據(jù)，提取參考點(diǎn)信號特征來構(gòu)建指紋數(shù)據(jù)庫，并將待定點(diǎn)的AP信號特征與RP的AP信號特征進(jìn)行對比，利用匹配算法得到待定點(diǎn)的定位結(jié)果。

1.2 算法

位置指紋定位算法是將一定采樣時間內(nèi)的RSSI均值保存到位置指紋記錄中，然后度量RSSI測量值與指紋數(shù)據(jù)庫之間的相似度，找出相似度最高的一個或者幾個指紋位置作為定位目標(biāo)的估計(jì)位置[12]。目前常用歐式距離來進(jìn)行相似度計(jì)算，即

(1)

(2)

WKNN算法考慮到K個參考點(diǎn)位置坐標(biāo)對最后定位的貢獻(xiàn)不同，將權(quán)值分別分配給對應(yīng)的坐標(biāo)，即

(3)

式中wi表示參考點(diǎn)i的定位權(quán)值，它的取值取決于參考點(diǎn)與待測點(diǎn)的RSSI歐式距離，通常其計(jì)算公式為

(4)

式中ε為很小的正數(shù)，防止分母中出現(xiàn)0。

1.3 基于灰色關(guān)聯(lián)度的改進(jìn)WKNN算法

灰色關(guān)聯(lián)分析是對一個系統(tǒng)發(fā)展態(tài)勢的定性描述和比較，它通過參考序列和比較序列各點(diǎn)之間的距離分析來確定各序列之間的接近性和差異性?；疑P(guān)聯(lián)分析的關(guān)鍵在于計(jì)算關(guān)聯(lián)度。傳統(tǒng)的鄧氏關(guān)聯(lián)度本身也存在很多問題，必然影響到權(quán)數(shù)的正確程度。本文將方差的倒數(shù)作為系數(shù)加入到關(guān)聯(lián)度的計(jì)算中，采用灰色加權(quán)平均關(guān)聯(lián)度來匹配離線階段與在線階段數(shù)據(jù)，從而獲得待定點(diǎn)的最優(yōu)位置。

將在線階段測試點(diǎn)采集的各個AP信號強(qiáng)度RSSI視為參考序列

X0=[RSSI1RSSI2… RSSIm]T。

(5)

式中m為AP個數(shù)。離線階段每個采集點(diǎn)采集的各個AP信號強(qiáng)度視為比較序列

(i=1,2,…,n)。

(6)

式中m、n分別為AP個數(shù)和參考點(diǎn)個數(shù)。參考序列和所有采集點(diǎn)的比較序列構(gòu)成比較矩陣

S=[X0┇X1X2…Xn]。

(7)

首先對S中所有元素進(jìn)行均值化處理，即每一個元素除以該元素所在列的均值。該處理方法能保留各變量取值差異程度的信息，得到新的均值矩陣

(8)

從第二列開始，每一列元素分別減去第一列對應(yīng)元素，再求絕對值。得到關(guān)聯(lián)矩陣

H=[H1H2…Hn]。

(9)

(10)

δ=[δ1δ2…δn]。

(11)

(12)

(13)

式中:ε為很小的正數(shù)，防止分母中出現(xiàn)0。通過對i個參考點(diǎn)的γi的大小進(jìn)行排序，將得到的關(guān)聯(lián)度的排序結(jié)果代替歐式距離大小的排序結(jié)果，改進(jìn)了傳統(tǒng)的WKNN算法。具體流程如圖2所示。

計(jì)算關(guān)聯(lián)度時，將方差的倒數(shù)作為系數(shù)加入到關(guān)聯(lián)度的計(jì)算中，降低方差大的AP的接收信號強(qiáng)度在關(guān)聯(lián)度計(jì)算時所占的權(quán)重，從而能一定程度上削弱RSSI波動帶來的影響，提高最終的定位精度。

2 實(shí)驗(yàn)與結(jié)果分析

2.1WiFi信號傳播特性及信號預(yù)處理

為了探究接收信號強(qiáng)度隨時間變化的關(guān)系，利用安卓手機(jī)應(yīng)用程序編程接口(applicationprogramminginterface，API)中提供的方法，在布設(shè)有WiFi節(jié)點(diǎn)的同濟(jì)大學(xué)信息館底樓，采用TP-LINK_0F784E路由器以及HTCD861t手機(jī)進(jìn)行RSSI測試。測試時間在下午1：00左右，人員干擾較少。每更新800次RSSI數(shù)據(jù)自動將采集結(jié)果保存并導(dǎo)出。圖3為距TP-LINK_0F784E路由器1.2m處(均值為-67.687 5dBm，標(biāo)準(zhǔn)差為2.251 4dBm)800個采樣值的處理結(jié)果。實(shí)驗(yàn)結(jié)果表明，同一個路由器，在某個固定位置，長時間對接收信號強(qiáng)度進(jìn)行采樣，其數(shù)值在一定范圍內(nèi)波動，且符合類正態(tài)分布[14]。剔除大于3倍中誤差的值(例如圖3中的-53dBm)后，求取信號強(qiáng)度的平均值作為該點(diǎn)的WiFi信號特征。圖4為經(jīng)過數(shù)據(jù)預(yù)處理之后的RSSI采樣值頻率分布直方圖。

2.2 實(shí)驗(yàn)平臺

實(shí)驗(yàn)環(huán)境搭建在同濟(jì)大學(xué)體育館底樓，場地面積為14.4m×14.4m，右上角為樓梯，占用7.68m2。在樓梯區(qū)域外每隔1.6m采集RSSI信號特征。室內(nèi)平面圖如圖5所示。

在圖5所示位置部署7個AP。在箭頭所示位置采集到的AP信息如表1所示，VAR表示采集到的方差信息。

表1 七個定位AP相關(guān)信息

2.3 結(jié)果分析

采集軟件在安卓手機(jī)端實(shí)現(xiàn)，采樣頻率為1次/s，離線階段每個采集點(diǎn)采集30 s，在線階段每個測試點(diǎn)采樣10 s。以平面圖所示的方向建立坐標(biāo)系，以第一個采集點(diǎn)的位置為原點(diǎn)，在待定位區(qū)域建立密度為1.6 m×1.6 m的網(wǎng)格采樣密度分布。不同的K值定位的誤差不同，K=3時KNN定位誤差最小[8]，所以取K=3時利用基于灰色關(guān)聯(lián)度的改進(jìn)WKNN算法對待定點(diǎn)進(jìn)行定位。測試點(diǎn)真實(shí)坐標(biāo)和定位坐標(biāo)如圖6所示，共測試了88個點(diǎn)，每個點(diǎn)每個AP采集30個RSSI數(shù)據(jù)，預(yù)處理后求得的方差信息保存至位置指紋數(shù)據(jù)庫中。由于圖中右上角為樓梯區(qū)域，此區(qū)域內(nèi)未進(jìn)行數(shù)據(jù)采集與測試，與真實(shí)環(huán)境相同。

為了驗(yàn)證改進(jìn)算法對定位效果有普遍性提高，對所有測試點(diǎn)的定位誤差進(jìn)行統(tǒng)計(jì)，累積分布如圖7所示，定位誤差累積分布曲線上的點(diǎn)表示定位誤差小于橫坐標(biāo)值的概率.

從圖7可以看出，改進(jìn)WKNN算法的誤差集中在0～5 m之間，幾乎沒有5 m以上的誤差，而傳統(tǒng)WKNN算法最大誤差達(dá)到將近7 m。計(jì)算了88個測試點(diǎn)的定位精度，分別和傳統(tǒng)WKNN方法、加權(quán)相關(guān)系數(shù)方法[7]定位效果做對比，如圖8、圖9所示。

從圖7、圖8和圖9可以看出，基于灰色關(guān)聯(lián)度的改進(jìn)WKNN算法能有效提高定位精度。實(shí)驗(yàn)最終實(shí)現(xiàn)了88個測試點(diǎn)的定位誤差均值為1.457 5 m，最大值為5.059 m，90 %的測試點(diǎn)定位誤差在2.343 m以下的定位效果。X和Y坐標(biāo)的中誤差為:

(14)

從圖10可以看出，當(dāng)K≥2時，基于灰色關(guān)聯(lián)度的WKNN方法的定位效果優(yōu)于其余3種方法，傳統(tǒng)WKNN方法只有在K=1的時候優(yōu)于基于灰色關(guān)聯(lián)度的WKNN方法，而K=1的時候WKNN算法已經(jīng)退化為NN算法，并不能作為反例，所以基于灰色關(guān)聯(lián)度的WKNN方法能有效提高定位精度。

4 結(jié)束語

本文將灰色關(guān)聯(lián)分析法引入到位置指紋定位傳統(tǒng)WKNN算法中，并對每個AP的關(guān)聯(lián)系數(shù)求加權(quán)平均值得到關(guān)聯(lián)度，削弱了RSSI不穩(wěn)定的接入點(diǎn)對定位結(jié)果的影響。利用同濟(jì)大學(xué)信息館底樓實(shí)驗(yàn)場地實(shí)際測試數(shù)據(jù)，分析了WiFi信號傳播特性，剔除了波動較大的RSSI值。在同濟(jì)大學(xué)體育館底樓利用88個點(diǎn)的實(shí)測WiFi定位數(shù)據(jù)進(jìn)行了分析，結(jié)果表明基于灰色關(guān)聯(lián)度的改進(jìn)WKNN方法相比于傳統(tǒng)WKNN方法、加權(quán)相關(guān)系數(shù)法以及加權(quán)歐式距離的改進(jìn)WKNN方法，能更加有效地提高定位精度。

[1] 萬群，郭賢生，陳章鑫，等.室內(nèi)定位理論、方法與應(yīng)用[M].北京：電子工業(yè)出版社，2012：2-3.

[2] 席瑞，李玉軍，侯孟書，等.室內(nèi)定位方法綜述[J].計(jì)算機(jī)科學(xué)，2016，43(4)：1-5.

[3] BAHL P, BALACHANDRAN A, PADMANABHAN V N. Enhancements to the RADAR user location and tracking system[R].Seattle:Microsoft Research,2000.

[4] 王福偉，黃智剛.室內(nèi)定位中移動目標(biāo)軌跡跟蹤研究[J].導(dǎo)航定位學(xué)報，2016，4(1)：33-36.

[5] 陳麗娜.基于WLAN的位置指紋室內(nèi)定位技術(shù)[M].北京：科學(xué)出版社，2015：10-11.

[6] 鄧中亮，余彥培，徐連明，等.室內(nèi)外無線定位與導(dǎo)航[M].北京：北京郵電大學(xué)出版社，2013：77-78.

[7] 李樹軍，于建江.基于群組的Wi-Fi指紋室內(nèi)定位研究[J].長春理工大學(xué)學(xué)報(自然科學(xué)版)，2013，36(6)：153-156.

[8] 李奇.一種基于RSSI相關(guān)系數(shù)的指紋定位技術(shù)方法[J].廣東通信技術(shù)，2013 (3)：29-32.

[9] 杜書敏.基于位置指紋的室內(nèi)定位技術(shù)研究與實(shí)現(xiàn)[D].昆明:云南大學(xué)，2013：19-25.

[10]鄧聚龍.農(nóng)業(yè)系統(tǒng)灰色理論與方法[M].濟(jì)南：山東科學(xué)技術(shù)出版社，1988：42-47.

[11]楊萌，修春娣，鄒坤，等.一種基于感知概率的室內(nèi)定位匹配算法[J].導(dǎo)航定位學(xué)報，2014，2(4)：49-57.

[12]李燕君，徐凱鋒，邵劍集.利用眾包更新Wi-Fi室內(nèi)定位指紋庫的方法研究[J].傳感技術(shù)學(xué)報，2014，27(12)：1692-1698.

[13]曹新建，董文洪，任建廣，等.灰色綜合關(guān)聯(lián)分析法的空空導(dǎo)彈武器系統(tǒng)作戰(zhàn)效能評估[J].海軍航空工程學(xué)院學(xué)報，2008，23(2)：203-206.

[14]雷家毅. Android平臺基于WiFi的定位算法與系統(tǒng)設(shè)計(jì)[D].上海:華東理工大學(xué)，2012：26-31.

[15]陳空，宋春雷，陳家斌，等.基于改進(jìn)WKNN的位置指紋室內(nèi)定位算法[J].導(dǎo)航定位與授時，2016，3(4):58-64.

An improved position fingerprinting algorithm based on grey relativity

ZHULv,SHENYunzhong

(College of Surveying and Geo-Informatics, Tongji University, Shanghai 200092, China)

Aiming at the problem that the variance information of the original data is not fully excavated and utilized in the traditional position fingerprinting algorithm, the paper proposed the positioning algorithm that is an improved WKNN method based on grey relativity: the variance information was taken into consideration in the calculation of relativity, and the impact of instable WiFi signal was eliminated to some degree through solving the weighted average values of the correlation coefficients.Experimental result showed that the proposed method could efficiently improve the accuracy of positioning.

WKNN; grey relativity; position fingerprinting algorithm; accuracy analysis

2016-10-21

作者簡介：朱律(1991—)，男，碩士研究生，研究方向?yàn)闇y量數(shù)據(jù)處理、室內(nèi)定位理論與方法。

朱律，沈云中.一種基于灰色關(guān)聯(lián)度的改進(jìn)位置指紋定位方法[J].導(dǎo)航定位學(xué)報,2017,5(2):44-48,71.(ZHULv,SHENYunzhong.Animprovedpositionfingerprintingalgorithmbasedongreyrelativity[J].JournalofNavigationandPositioning,2017,5(2):44-48,71.)DOI：10.16547/j.cnki.10-1096.20170208.

P

A

2095-4999(2017)02-0044-06