朱 律，沈云中

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

?

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

朱 律，沈云中

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

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

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

0 引言

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

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

1 位置指紋定位

1.1 基本原理

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

1.2 算法

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

(1)

(2)

WKNN算法考慮到K個參考點位置坐標對最后定位的貢獻不同，將權值分別分配給對應的坐標，即

(3)

式中wi表示參考點i的定位權值，它的取值取決于參考點與待測點的RSSI歐式距離，通常其計算公式為

(4)

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

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

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

將在線階段測試點采集的各個AP信號強度RSSI視為參考序列

X0=[RSSI1RSSI2… RSSIm]T。

(5)

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

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

(6)

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

S=[X0┇X1X2…Xn]。

(7)

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

(8)

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

H=[H1H2…Hn]。

(9)

(10)

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

(11)

(12)

(13)

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

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

2 實驗與結果分析

2.1WiFi信號傳播特性及信號預處理

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

2.2 實驗平臺

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

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

表1 七個定位AP相關信息

2.3 結果分析

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

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

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

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

(14)

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

4 結束語

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

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

[2] 席瑞，李玉軍，侯孟書，等.室內定位方法綜述[J].計算機科學，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] 王福偉，黃智剛.室內定位中移動目標軌跡跟蹤研究[J].導航定位學報，2016，4(1)：33-36.

[5] 陳麗娜.基于WLAN的位置指紋室內定位技術[M].北京：科學出版社，2015：10-11.

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

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

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

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

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

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

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

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

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

[15]陳空，宋春雷，陳家斌，等.基于改進WKNN的位置指紋室內定位算法[J].導航定位與授時，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—)，男，碩士研究生，研究方向為測量數(shù)據(jù)處理、室內定位理論與方法。

朱律，沈云中.一種基于灰色關聯(lián)度的改進位置指紋定位方法[J].導航定位學報,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