王艷麗，楊如民，余成波，孔慶達

(重慶理工大學(xué) 遠程測試與控制研究所，重慶 400054)

相關(guān)性匹配藍牙信標位置指紋庫的室內(nèi)定位*

王艷麗*，楊如民，余成波，孔慶達

(重慶理工大學(xué) 遠程測試與控制研究所，重慶 400054)

針對K近鄰算法(KNN)在對偏向于某個樣本點的未知點進行三角質(zhì)心定位時定位精度變差的情況,提出了應(yīng)用相關(guān)系數(shù)去匹配藍牙信標iBeacon位置指紋庫的室內(nèi)定位算法。通過比較待定位點和位置指紋庫中參考樣點的相似程度，并進行數(shù)據(jù)差異顯著性檢驗，來檢驗采集的待定位點數(shù)據(jù)與指紋庫數(shù)據(jù)是否顯著相關(guān)，然后取相關(guān)性較高的樣本點進行加權(quán)平均匹配定位。實驗結(jié)果顯示，相關(guān)系數(shù)匹配位置指紋庫算法可將2 m以內(nèi)的定位精度從65%提高到92%，相較于傳統(tǒng)的KNN匹配定位算法有著定位精度高、計算量小、定位時間短等優(yōu)勢。

室內(nèi)定位；藍牙信標；位置指紋庫；相關(guān)系數(shù)；顯著性檢驗

1 引 言

近年來，無線通信網(wǎng)絡(luò)、移動互聯(lián)網(wǎng)及智能終端的廣泛應(yīng)用，帶動了基于地理位置信息服務(wù)(Location Based Service，LBS)產(chǎn)業(yè)的快速發(fā)展。雖然室外使用較多的是GPS定位，但在室內(nèi)、地下、高樓林立的市區(qū)等場景中，GPS定位性能變差，不再適用。在低功耗、長距離、低成本定位上，基于藍牙信標iBeacon的定位系統(tǒng)相比GPS存在優(yōu)勢，且大多智能設(shè)備中都有藍牙功能，故藍牙信標iBeacon室內(nèi)定位技術(shù)受到極大推崇。

目前的室內(nèi)定位算法主要是基于接收信號強度指示(Received Signal Strength Indication，RSSI)的測距室內(nèi)定位[1]和基于信號指紋庫的匹配定位[2]。然而，簡單的RSSI測距定位無法滿足室內(nèi)環(huán)境較復(fù)雜的情況[3-4]，故大多采用基于信號指紋庫的匹配定位。典型算法[5-7]有K近鄰算法(K-Nearest Neighbor,KNN)、貝葉斯法、神經(jīng)網(wǎng)絡(luò)算法(Artificial Neural Networks,ANNs)、支持向量機(Support Vector Machine,SVM)等，但容易實現(xiàn)的是KNN算法。

文獻[8]結(jié)合RSSI路徑損耗特征進行了限定區(qū)域的KNN定位，然而此方法前期需對數(shù)據(jù)進行大量處理分析，定位精度依賴于區(qū)域的劃分。文獻[9-10]都用了聚類分析，不同在于一個是主分量分析，然后進行模糊C均值處理，主成分提取和C均值處理比較繁瑣；一個是利用最鄰近點的幾何特性建立約束條件進行聚類，約束準則的選取需要不斷驗證，定位精度也不是很高。上述幾種算法均比較復(fù)雜，耗時長，定位的精度也依賴于各自的分類標準，并且利用KNN進行相似取平均處理，都忽略了未知點偏向于某個樣本點時定位精度變差的情況，所以總體定位精度不高。

本文直接從從未知點與參考樣點RSSI向量相似度出發(fā)，選擇了算法較為簡單且易實現(xiàn)的相關(guān)性分析來進行iBeacon信號RSSI指紋庫的匹配，并用顯著性檢驗再一次驗證，以此避免分類標準的制約以及未知點偏向于某個樣本點時KNN算法帶來的誤差，提高匹配準確度，進而提高定位精度。

2 基于iBeacon的室內(nèi)定位系統(tǒng)設(shè)計

本系統(tǒng)包括一定數(shù)量的iBeacon基站(藍牙4.0低功耗模塊)、帶有藍牙的終端設(shè)備(智能手機)、服務(wù)器Web端(地圖定位)以及數(shù)據(jù)存儲中心，模型如圖1所示。

圖1 基于iBeacon的室內(nèi)定位系統(tǒng)Fig.1 The indoor positioning system based on iBeacon

在室內(nèi)空間均勻部署一定數(shù)量的藍牙4.0低功耗模塊，當智能手機端進入室內(nèi)時便可接收到其對應(yīng)的iBeacon信息，包括藍牙4.0模塊對應(yīng)的通用唯一標識符(Universally Unique Identifier，UUID)、識別某個定位區(qū)域的區(qū)域號Major、識別區(qū)域內(nèi)各個iBeacon的單號Minor以及RSSI值，并對接收到的RSSI進行濾波去噪處理。

本文采用RSSI位置指紋數(shù)據(jù)庫相關(guān)性匹配定位技術(shù)，需建立RSSI位置指紋庫，主要分為以下兩個階段：

(1)離線階段(也稱訓(xùn)練階段)

設(shè)定每次采集數(shù)據(jù)的時間間隔和持續(xù)時間，按照每間隔1 m作為參考點，同一位置進行多次多方向采點，并通過Android手機端App將采集的iBeacon信息上傳到服務(wù)器數(shù)據(jù)中心，與提前繪制好的室內(nèi)環(huán)境地圖結(jié)合，構(gòu)建實驗環(huán)境下iBeacon信號的位置指紋數(shù)據(jù)庫。

(2)在線階段(也稱實時定位階段)

智能手機端進入定位服務(wù)區(qū)的某個位置，與服務(wù)器建立Socket通信，發(fā)出定位請求并將此時采集到的待定位點的iBeacon信息按照一定的時間間隔傳遞給服務(wù)器(圖1的過程1)，服務(wù)器從位置指紋數(shù)據(jù)庫調(diào)用信號指紋庫進行匹配(圖1的過程2、3)，匹配算法采用本文提出的基于相關(guān)性匹配位置指紋庫的算法來得到此時待定位點的位置信息(圖1的過程4)，并在地圖上顯示出這個點。

3 相關(guān)性匹配定位算法

相關(guān)性分析一直以來都是統(tǒng)計信號處理領(lǐng)域的熱潮[11]。1970年，美國地理學(xué)家Tobler的第一定律(Tobler's First Law,TFL)認為[12]，任何事物都存在空間相關(guān)，距離越近，其空間相關(guān)性越大，反之則越小。典型相關(guān)分析(Canonical Correlation Analysis)就是利用綜合變量對之間的相關(guān)關(guān)系來反映兩組指標之間的整體相關(guān)性的多元統(tǒng)計分析方法[13]。基于位置指紋庫匹配的室內(nèi)定位，正是探究采集的目標點數(shù)據(jù)與指紋庫參考點數(shù)據(jù)之間的匹配程度，即相關(guān)程度，從而取相關(guān)性較高的參考樣點的位置進行加權(quán)平均求目標點所在位置。

3.1 相關(guān)系數(shù)

相關(guān)系數(shù)是表征變量之間相關(guān)程度的量，需要計算兩組變量各自的離差。先求得各變量與其本身均值的離差，然后將對應(yīng)的兩個離差相乘，即為相關(guān)系數(shù)， 如公式(1)所示:

(1)

式中:X、Y為兩組變量序列，且序列長度相等均為m。相關(guān)系數(shù)在-1～1之間，即-1≤γ≤1，當γ=1時，兩組變量是正線性相關(guān)；當γ=-1時，兩組變量是負線性相關(guān)。若0<|γ|<0.3，沒有相關(guān)性；若0.3≤|γ|<0.5則為低度相關(guān)；若0.5≤|γ|<0.8則為中度相關(guān)；若0.8≤|γ|<1則為高度相關(guān)。

在iBeacon位置指紋庫(LocationFingerprintDataBase，LFDB)匹配定位中，每個參考點的RSSI指紋信息R都和其位置信息L對應(yīng)，LFDB的組成元素DBE(DataBaseElement)即為DBE=(L,R)。假定定位服務(wù)區(qū)中均勻了布置M個iBeacon基站，則在每個參考點L(x,y)處,可采集到M個iBeacon信號的RSSI值，同時可以采集到每個iBeacon基站獨有的與位置相關(guān)的信息。若采集N個參考樣點，則位置指紋庫具有N個iBeacon參考指紋的集{R1,R2,R3，…,RN}，每個iBeacon指紋都和位置集合{L1,L2,L3，…,LN}中的位置相對應(yīng)。參考iBeacon指紋R和目標點采集信息T可用如下矩陣表示：

(2)

式中：idi是第i個iBeacon基站獨有的信息，ri是參考點接收到的第i個iBeacon基站的RSSI值，dri即在待定位點處采集到的第i個iBeacon基站的RSSI值。

在定位匹配過程中，需探究采樣點與參考點各自在第i個iBeacon信號下的RSSI值的相關(guān)程度，若對應(yīng)的iBeacon基站下的RSSI相關(guān)程度高，則其位置坐標相關(guān)程度高，即通過變量對之間RSSI的相關(guān)關(guān)系來反映變量對之間整體的相關(guān)性。

結(jié)合公式(1)可以推出采樣點與參考點相關(guān)系數(shù)

(3)

3.2 顯著性檢驗

統(tǒng)計假設(shè)檢驗(Test of Hypothesis)，即顯著性檢驗(Significance Test)，是一種比較樣本與總體參數(shù)間存在顯著差異和存在不顯著差異的方法。思路是結(jié)合具體情況對未知的或不完全知道的總體參數(shù)(均值、方差、比例)或分布形式(大樣本正態(tài)分布，小樣本t分布)，作出某種假設(shè)，在一定概率意義下，得出接受或拒絕原假設(shè)的結(jié)論。當樣本容量小于30時，為小樣本，多采用t-檢驗；大樣本則一般采用u-檢驗 。

t統(tǒng)計量如下：

(4)

其中：

(5)

假設(shè)所檢測數(shù)據(jù)存在不顯著差異的概率為P，設(shè)定顯著水平α，即判斷實驗誤差的概率界限。一般α取0.05，當P≤5%，利用“小概率事件實際不可能性原理”，判斷存在顯著差異。更精確判斷時，α取0.01，即P≤1%，判定存在極顯著差異。若試驗中可變因素太多且難以控制，誤差大，則顯著水準選低些，α值取大些；反之，如果試驗中耗費太大，對精確度要求比較高，則顯著水準選高些，α值取小些。

在iBeacon位置指紋庫采點中，影響因素較多，采樣的時間、方向，天氣的陰晴都會有影響，故將判斷標準稍微放寬，選擇α=0.05進行顯著水平判斷。

自由度df=M-1，實驗中M取12，df取11。根據(jù)自由度查表獲取理論的臨界值。在tα-檢驗中，如果雙側(cè)檢驗顯著，則單側(cè)檢驗一定顯著；反之則不然，故選擇t雙側(cè)檢驗。

雙側(cè)：

t0.05/2(M-1)=2.201，t0.01/2(M-1)=3.106。

單側(cè)：

t0.05(M-1)=1.796,t0.01(M-1)=2.718。

將公式(4)中得到的t統(tǒng)計量與理論臨界值2.201比較，當|t|<2.201，這兩組數(shù)據(jù)無顯著差異，即待定位點與參考點接近；當|t|>2.201，這兩組數(shù)據(jù)有顯著差異，即待定位點與參考點相隔較遠。

由于位置指紋庫中具有N個iBeacon參考指紋的集合{R1,R2,R3，…,RN}，每個參考指紋中有M個RSSI值，可得N個相關(guān)系數(shù)，并對之進行顯著性檢驗，取相關(guān)程度γ滿足0.8≤|γ|<1的k個參考樣點，取其位置坐標進行加權(quán)平均即可得所求點的位置，公式如下：

(6)

4 實驗結(jié)果與分析

4.1 實驗環(huán)境部署

在8 m×14 m的實驗環(huán)境中，有一個辦公隔間，20個小辦公分隔區(qū)，室內(nèi)環(huán)境較復(fù)雜，故按照對稱方式均勻布置12個iBeacon基站(iBeacon分布如圖2所示)，使得iBeacon信號覆蓋整個室內(nèi)環(huán)境。由于采集的RSSI在1 m內(nèi)的波動不大，故以橫縱方向上每間隔1 m作為參考點。實驗顯示時間、方向會引起RSSI的波動，故在每個參考點上的分不同方向時間采集了4次共N=438個樣本指紋。

圖2 實驗環(huán)境下的iBeacon分布Fig.2 The arrangement of iBeacon in lab

采集信號時，需采集該位置下所接收到的iBeacon信息，包括UUID、Mac地址、Major、Minor及信號強度值RSSI。iBeacon廣播功率全部設(shè)為0 dBm，UUID為FDA50693-A4E3-4FB1-AFCF-C6EB07647825，如表1所示。

表1 iBeacon節(jié)點配置表Tab.1 iBeacon nodes configuration table

在構(gòu)建iBeacon位置指紋庫數(shù)據(jù)時，除了接收到的各個iBeacon基站對應(yīng)的RSSI外，還需添加二維位置坐標(x,y)，如表2所示。由于實際建指紋數(shù)據(jù)庫時，每個測試點上的RSSI值采樣了4次，故表2對應(yīng)的RSSI有4次數(shù)據(jù)值。

表2 坐標為(500 cm,800 cm)的樣本點采集的指紋庫Tab.2 The fingerprint database of the sample point at (500 cm,800 cm)

4.2 Android手機端定位測試結(jié)果

Android手機端開發(fā)的App如圖3所示。在智能手機端先安裝App，將建好的位置指紋庫信息導(dǎo)入到BLE數(shù)據(jù)庫，室內(nèi)環(huán)境地圖導(dǎo)入室內(nèi)定位測試，如圖4所示。

圖3 Android手機端的AppFig.3 The App of android phone

圖4 BLE數(shù)據(jù)庫和室內(nèi)定位測試Fig.4 The database of BLE and indoor positioning test

在實驗環(huán)境中，隨機取30個測試點，將Android手機端分別放在該測試點上，可獲取其對應(yīng)的iBeacon信息(圖4右列表中)，用相關(guān)性匹配指紋庫算法與位置指紋庫進行匹配，找出相關(guān)性較高的參考點加權(quán)平均得該測試的坐標，同時在定位地圖上顯示出此點，如圖4右。

4.3 實驗結(jié)果分析

同時，對其進行傳統(tǒng)的KNN匹配定位。取兩種算法下得到的坐標值，分別與實際坐標值進行定位誤差分析，比較結(jié)果如圖5所示。

圖5 KNN匹配定位與相關(guān)性匹配定位誤差分布情況Fig.5 The positioning error distribution of KNN algorithm and correlation positioning algorithm

圖5顯示，相關(guān)系數(shù)匹配定位誤差大體上在2 m以內(nèi)，很少有在3 m以外的，而傳統(tǒng)的KNN匹配定位誤差集中在1 ～3 m，還有一部分在3 m以外，具體分析如表3所示。

表3 KNN匹配定位與相關(guān)性匹配定位誤差對比Tab.3 The positioning error comparison between KNN algorithm and correlation positioning algorithm

相比于常用的KNN匹配指紋庫定位算法，相關(guān)系數(shù)匹配指紋庫定位算法可將2 m內(nèi)的定位精度從65%提高到92%，使整體定位精度得到提升，說明相關(guān)系數(shù)匹配指紋庫定位算法能夠有效地提升定位精度。

5 結(jié)束語

本文針對KNN算法進行信號位置指紋匹配時，自身存在的未知點與某個樣本點較鄰近時，取K個較鄰近的進行均值定位，精度變差的情況,同時結(jié)合當前改進算法均比較復(fù)雜、耗時長、定位的精度也依賴于各自的分類標準實際情況，將相關(guān)性匹配應(yīng)用到iBeacon室內(nèi)定位系統(tǒng)中。實驗結(jié)果顯示，相較于傳統(tǒng)的KNN匹配定位算法，相關(guān)性匹配定位定位精度更高，大體上在2 m內(nèi)，且算法易實現(xiàn)，計算量小，定位時間更短，可廣泛應(yīng)用于室內(nèi)定位領(lǐng)域，如機場、醫(yī)院、展覽館、礦井、大型商場及智能家居等。但本系統(tǒng)仍有需要改進的地方以及解決的難題：一是iBeacon節(jié)點數(shù)目及布置方式對于室內(nèi)定位精度的影響；二是采集iBeacon信號時，時間、方向及溫度的變化都會帶來信號的波動，故在建立動態(tài)性位置指紋庫上還需進一步研究。

[1] 詹杰,吳伶錫,唐志軍.無線傳感器網(wǎng)絡(luò)RSSI測距方法與精度分析[J].電訊技術(shù),2010,50(4):83-87. ZHAN Jie,WU Lingxi,TANG Zhijun.Ranging method and accuracy analysis based on RSSI of wireless sensor network[J].Telecommunication Engineering,2010,50(4):83-87.(in Chinese)

[2] 盧恒惠,劉興川,張超,等.基于三角形與位置指紋識別算法的WiFi定位比較[J].移動通信,2010(10):72-76. LU Henghui,LIU Xingchuang,ZHANG Chao，et al.Compare the triangle location algorithm and the fingerprint recognition algorithm based on WiFi positioning[J].Mobile Communication,2010(10):72-76.(in Chinese)

[3] 陳錫劍,程良倫.基于RSSI的功率匹配定位算法的研究與實現(xiàn)[J].傳感技術(shù)學(xué)報,2013(5):709-714. CHEN Xijian,CHENG Lianglun.Study and implementationof power match algorithm based on RSSI[J].Chinese Journal of Sensors and Actuators,2013(5):709-714.(in Chinese)

[4] WANG Y,YE Q,CHENG J,et al.RSSI-based blue-tooth indoor localization[C]//Proceedings of 2015 11th International Conference on Mobile Ad-hoc and Sensor Networks(MSN).Shenzhen:IEEE,2015:165-171.

[5] FRANCE S L,CARROLL J D,XIONG H.Distance metrics for high dimensional nearest neighborhood recovery:compression and normalization[J].Information Sciences,2012,184(1):92-110.

[6] LIANG X,GOU X,LIU Y.Fingerprint-based location positoning using improved KNN[C]//Proceedings of 2012 IEEE International Conference on Networking Infrastruct.Digital Content(ICNIDC).Beijing：IEEE,2012:57-61.

[7] YE M,MING C P,LI C G.The algorithm of thinning fingerprint with BP neural network[C]//Proceedings of the 26th Chinese Control Conference.Zhangjiajie：IEEE,2007:145-148.

[8] 莫倩,熊碩.基于藍牙4.0的接近度分類室內(nèi)定位算法[J].宇航計測技術(shù),2014,34(6):66-70. MO Qian,XIONG Shuo.Close degree classification of indoor positioning algorithm based on bluetooth 4.0[J].Journal of Astronautic Metrologry and Measurement,2014,34(6):66-70.(in Chinese)

[9] 都伊林.一種模糊聚類KNN位置指紋定位算法[J].微型機與應(yīng)用,2012,31(23):55-58.

DU Yilin.A fuzzy clustering KNN location fingerprint p-ositioning algorithm[J].Microcomputer & Its Applications,2012,31(23):55-58.(in Chinese)

[10] 劉春燕,王堅. 基于幾何聚類指紋庫的約束KNN室內(nèi)定位模型[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2014,39(11):1287-1292. LIU Chunyan,WANG Jian. Based on the geometric clustering fingerprint constraints KNN indoor positioning model[J].Geomatics and Information Science of Wuhan University,2014,39(11):1287-1292.(in Chinese)

[11] 胡暉,許浩峰,包偉華.基于相關(guān)性算法的超聲波回波定位[J].自動化儀表,2015(10):96-98,102. HU Hui,XU Haofeng,BAO Weihua.Ultrasonic echo location based on correlation algorithm[J].Process Automation Instrumentation,2015(10):96-98,102.(in Chinese)

[12] 李小文,曹春香,常超一.地理學(xué)第一定律與時空鄰近度的提出[J].自然雜志,2007,29(2):69-71. LI Xiaowen,CAO Chunxiang,CHANG Chayi.The first law of geography and spatial temporal proximity[J].Chinese Journal of Nature,2007,29(2):69-71.(in Chinese)

[13] 樊祜廣.港口與區(qū)域經(jīng)濟互動發(fā)展研究[D].武漢:武漢理工大學(xué),2012. FAN Huguang.The interactive development between port with the regional economic[D].Wuhan:Wuhan University of Technology,2012.(in Chinese)

[14] 張鳳菊,劉曉娟,趙麗平,等.數(shù)據(jù)差異顯著性檢驗[J].農(nóng)機使用與維修,2012(4):51-52. ZHANG Fengju,LIU Xiaojuan,ZHAO Liping,et al.Data difference significance test[J].Agricultural Mechanization Using & Maintenance,2012(4):51-52.(in Chinese)

Indoor Localization of Bluetooth Beacon Position Fingerprint Based on Correlation Algorithm

WANG Yanli，YANG Rumin，YU Chengbo，KONG Qingda
(Institute of Remote Test and Control,Chongqing University of Technology,Chongqing 400054,China)

K-Nearest Neighbor algorithm,or“KNN”for short,often simply uses triangle centroid algorithm to locate.However,once the backlog site is close to a certain sample point,the accuracy of location will be greatly affected.Therefore,this paper proposes a correlation coefficient matching iBeacon position fingerprint algorithm.Firstly,through comparing the similar degree between undetermined point and a certain sample point of received signal strength indication(RSSI) fingerprint,it uses the test of data difference significance to test whether the backlog site data and fingerprint data is significantly correlated.Then,it takes the weighted average of high correlation sample points to get the result.Experimental results show that the positioning accuracy within 2 m can be increased from 65% to 92% with the correlation coefficient matching fingerprint algorithm.Compared with traditional KNN localization algorithm,the proposed correlation matching algorithm has higher positioning precision,smaller calculation amount,and shorter positioning time.

indoor positioning;bluetooth beacon;position fingerprint;correlation coefficient;significance testing

2016-07-11；

2016-10-09 Received date:2016-07-11；Revised date：2016-10-09

國家自然科學(xué)基金資助項目(61402063)；重慶市科技人才培養(yǎng)計劃(新產(chǎn)品研發(fā)團隊)項目(CSJC2013KJRC-TDJS40012)；重慶市高校優(yōu)秀成果轉(zhuǎn)化資助項目(KJZH14213

10.3969/j.issn.1001-893x.2017.02.004

王艷麗，楊如民，余成波，等.相關(guān)性匹配藍牙信標位置指紋庫的室內(nèi)定位[J].電訊技術(shù)，2017,57(2):145-150.[WANG Yanli，YANG Rumin，YU Chengbo，et a.Indoor localization of bluetooth beacon position fingerprint based on correlation algorithm[J].Telecommunication Engineering,2017,57(2):145-150.]

TN967.2

A

1001-893X(2017)02-0145-06

王艷麗(1989—)，女，湖北襄陽人，2014年獲工學(xué)學(xué)士學(xué)位，現(xiàn)為碩士研究生，主要研究方向為室內(nèi)定位算法；

Email:1476646282@qq.com

楊如民(1963—)，男，重慶人，教授、碩士生導(dǎo)師，主要研究方向為無線傳感器網(wǎng)絡(luò)、可再生能源的開發(fā)及利用；

Email:yangrumin@163.com

余成波(1965—)，男，江西波陽人，教授、碩士生導(dǎo)師，主要研究方向為遠程測試與控制技術(shù)、信號與信息處理；

Email:yuchengbo@cqut.edu.cn

孔慶達(1991—)，男，山西呂梁人，2014年獲工學(xué)學(xué)士學(xué)位，現(xiàn)為碩士研究生，主要研究方向為室內(nèi)定位技術(shù)。

Email:1159754385@qq.com

*通信作者：1476646282@qq.com Corresponding author：1476646282@qq.com