一種層次聚類和自適應加權K近鄰組合的室內定位算法

翟俊杰，李廷會，黃飛江,，袁海波，張虹，胡傳君,3

一種層次聚類和自適應加權K近鄰組合的室內定位算法

翟俊杰1,2,3，李廷會1，黃飛江1,2,3,*，袁海波4，張虹4，胡傳君1,3

（1.廣西師范大學 電子工程學院，桂林 541004；2.廣州航海學院 信息與通信工程學院，廣州 510725；3. 長沙學院 電子信息與電氣工程學院，長沙 410022；4. 中國科學院 國家授時中心，西安 710600）

針對基于接收信號強度的位置指紋室內定位算法定位精度不高的問題，提出了一種均值層次聚類和自適應加權K近鄰（weighted K nearest neighbor，WKNN）的室內定位算法。算法首先在設置的參考點上采集藍牙信號強度構建離線指紋數據庫，然后采用均值層次聚類方法將所有參考點根據各自之間的相似度分為個類，濾除掉相似度較小的參考點，最后根據待定位點和參考點間的信號距離的相似度，計算出距離差的標準差來自適應確定值，并進行位置估算。實驗結果表明，本文提出的算法在定位精度上比WKNN、動態加權K近鄰（enhanced weighted K nearest neighbor，EWKNN）方法分別提升了30.0% 和18.0%，在定位實時性上比WKNN和EWKNN方法分別提高了19.2%和28.4%。將該算法用于室內物體定位，可以同時提高定位精度和定位實時性。

室內定位；接收信號強度；指紋數據庫；均值層次聚類；自適應加權K近鄰

0 引言

隨著互聯網不斷發展，人們對基于位置的服務（location-based sevice，LBS）的需求越來越大，全球定位系統[1]（Global Positioning System，GPS）和北斗衛星導航系統[2-4]（BeiDou Navigation Satellite System，BDS）作為應用最廣泛的室外定位技術，由于其信號容易被城市中高樓、隧道等障礙物遮擋，導致全球衛星導航系統（Global Navigation Satellite System，GNSS）在某些室內環境下無法實現定位，為此需要研究室內定位技術。目前主流的室內定位技術主要有射頻識別技術[5]（radio frequency identification，RFID）、超帶寬技術[6]（ultra-wide bandwidth，UWB）、Wi-Fi[7]和藍牙技術[8]等。藍牙有低功耗、低成本、體積小、易于部署和信號強等優點，而且現有的手持移動設備都可以接收到藍牙信號，使得基于接收信號強度（received signal strength，RSS）的藍牙室內定位技術得到了廣泛的應用[9]。基于RSS的室內定位方法分為基于傳播模型[10]和基于位置指紋定位法[11]，由于室內結構復雜，構造出的室內傳播模型可能不夠準確，而與傳播模型方法相比，對位置指紋定位法的研究更為廣泛。

位置指紋算法在室內定位離線階段時需要在實驗區域劃分出參考點，導致在某些大型室內環境參考點分布密集，數據量非常龐大。為了對參考點進行篩選，濾除誤差較大的點，從而減少定位時間，已有學者將聚類方法應用在位置指紋算法中。文獻[15]提出一種基于K-means的加權KNN算法，通過K-means聚類處理指紋數據庫，然后在KNN算法中加入加權因子進行匹配，實驗表明使用普通KNN算法的平均誤差為3.11 m，在使用了K-means的加權改進算法后，能有效提升40%的定位準確度。K-means算法的缺點是K-means容易陷入局部最優，這跟初始給定的中心值有關，所以要嘗試多個初始值。文獻[16]提出了改進的K-means算法來解決這個問題，但是也需要事先給出聚類的數目，而這個往往難以判斷；如果用戶選擇了不正確的聚類數目，會使本應該在同一個類的數據被判定為兩個大的類別，最終影響定位準確度。文獻[17]提出了使用基于層次聚類中的最大距離法和改進的KNN算法相結合，實驗結果表明改進后算法的平均誤差為2.09 m，最大誤差為8.25 m，最小誤差為0.13 m。與K-means-KNN算法相比，改進后的算法定位準確度更高。但最大距離法以分布在兩個類中最不相似的樣本（距離最遠）作為度量標準進行聚類的方法不夠嚴謹，對離群點的數據比較敏感，降低了指紋數據庫分類的準確度，導致最終的定位準確度不高。

針對以上問題，本文提出了基于均值（mean-link，ML）層次聚類和自適應WKNN組合的定位算法。在離線階段通過ML層次聚類處理數據庫中的參考點，降低搜索范圍，減少了定位時間，也排除了在線階段的錯誤匹配點。在線匹配階段通過求待定位點與參考點的距離集合的標準差來自適應選擇值進行位置估計，提高了定位準確度，減少了定位時間。

1 位置指紋定位算法的原理

位置指紋定位包括離線階段和在線階段，指紋定位算法原理如圖1所示。

圖1 位置指紋定位算法原理圖

離線階段：在實驗區域內劃分好參考點，在每一個參考點上進行藍牙信號強度的采集，并記錄對應的參考點坐標，記錄格式為

在線階段：用戶進入實驗區域內的某一位置，將接收到的藍牙AP信號強度記錄下來，將其與指紋數據庫中的信號強度進行搜尋，尋找最佳的匹配點，并使用定位匹配算法計算出估計位置坐標。常見的匹配算法包括KNN，WKNN，貝葉斯分類算法等。

2 層次聚類算法原理

層次聚類分為凝聚和分裂兩種聚類方法，凝聚算法是自下而上的算法，分裂聚類算法是自上而下的算法，凝聚和分裂兩種方法在本質上是一致的，兩種聚類的每一次迭代都是通過某種特定的規則來作為指標，根據不同的數據分布情況來選擇對應的層次聚類算法。凝聚的層次聚類，開始時將每一個樣本都視為一個類，通過計算每個類之間的距離，按照具體的合并規則將類進行合并，最終將所有類聚類為一個大類或者達到特定的條件則終止聚類。分裂聚類則與凝聚相反，將一個大類逐步分為一個個小類，直到達到終止條件結束聚類。層次聚類的優勢在于它的靈活性，不需要事先指定類的數量，通過加入閾值判斷，可以很好地控制得到想要的聚類結果。并且層次聚類可以很清晰地展現出樣本的劃分過程。層次聚類根據聚類條件不同分為最小距離也稱單連接算法（single-link，SL）、最大距離也稱全連接算法（complete-link，CL）、均值距離（mean-link，ML）和平均距離（average-link，AL）等幾種方法[18]。

本文采用的ML層次聚類屬于凝聚層次聚類，將離線階段的每一個參考點視為不同的類，通過合并規則對參考點進行凝聚，直到達到終止條件停止凝聚。最小距離法和最大距離法使用類間最小距離和類間最大距離作為聚類標準不夠嚴謹，對離群點比較敏感，會過于關注局域連接，應用在室內定位中，聚類結果無法達到預期效果。而采用均值或平均距離聚類法對數據庫進行聚類，可以解決算法對離群點過于敏感的問題，但是平均距離法計算量較大，每次聚類都需要計算類與類包含的所有數據點間相互的歐式距離，所以采用ML層次聚類，更加契合室內定位的場景。

離線階段ML層次聚類算法步驟如下[19]：

① 在實驗區域選取參考點，采集藍牙信號，建立信號指紋數據庫，計算出所有參考點兩兩之間的歐氏距離：

② 計算完成后開始聚類，每一次迭代將歐式距離最小的兩個類合并成一個新的類，并計算出新類的中心點。當類與類之間的中心點距離大于閾值時，停止合并。

③ 聚類結束后，計算所有類中心的信號強度：

3 基于ML層次聚類和自適應WKNN的定位算法

由于藍牙信號強度之間的相似度和歐式距離這個特征量相關，所以本文利用歐式距離這個特征向量來反映出待定位點與參考點之間的相似度，并分別應用在室內定位的離線和在線階段。在空間中，根據信號衰減模型可知，移動終端接收到的藍牙信號強度與移動終端和藍牙AP節點之間的距離成正比，兩個相鄰的參考點如果距離越近，他們采集到的信號強度之間的相似度就越大。根據這個特性，對指紋數據庫進行ML層次聚類，可以將在同一區域內，相似度很高的參考點劃分為同一個類。由于藍牙信號有時不穩定，會導致相距很遠的參考點之間具有相似的信號強度。針對這個問題，ML層次聚類根據數據庫中各參考點之間的歐氏距離對數據庫進行區域劃分，可以將異常數據排除掉，避免了在線匹配階段待定位點需要和實際偏遠的參考點進行匹配。對數據庫進行ML層次聚類后，可以使待定位點直接尋找與自己相似度最高的類進行比較，節省了定位時間，也提高了定位準確度。

自適應WKNN算法是在ML層次聚類的基礎上，根據待定位點與參考點之間的信號距離差的標準差來自適應調整值。在實際的定位空間中，存在狹窄區域，也有寬敞的區域，對于不同面積的定位區域，所設定的參考點數量也不同，若每一次定位都選取固定的值，可能會引入相似度很小的參考點，定位的結果將會帶來很大誤差。本文算法對于每一個不同的待定位點，都會在ML層次聚類的結果上選取相似度最高的類進行匹配，濾除掉誤差點，進而選取最優值，提高定位準確度。自適應WKNN算法是在ML層次聚類對數據庫處理的基礎上進行位置估計，具體實施步驟如下：

式（6）中，為參考點的個數。

④ 對剩余的個參考點使用WKNN算法進行位置估計：

基于ML層次聚類和自適應WKNN定位算法流程如圖2所示。

圖2 ML層次聚類和自適應WKNN定位算法流程圖

基于ML層次聚類和自適應WKNN定位算法詳細流程如下：

① 通過式（3）計算數據庫中參考點兩兩之間的歐氏距離，每一次聚類將距離最小的兩個點進行合并，每一次聚類都自動更新類的中心。設置閾值，當兩個類之間的中心距離大于時，聚類停止；

② 聚類結束后，根據式（4）計算所有類中心的信號強度，用于在線階段的快速匹配；

③ 在線階段，采集待定位點的藍牙信號強度，通過式（5）尋找到離待定位點最近的類C；

⑤ 根據算出的平均值來通過式（7）進一步求出標準差，濾除掉大于標準差的參考點，最終篩選出值，自適應的選取值，并通過式（8）來得出位置估計。

4 實驗和結果分析

為了驗證本文提出算法的定位性能，對ML層次聚類和自適應WKNN組合的定位算法、EWKNN算法與WKNN算法進行定位實驗比較。

4.1 實驗環境

實驗選擇在學院理工樓4樓進行，如圖3所示。圖中的標記點為離線指紋數據庫中的部分參考點，參考點之間間隔1m，使用華為手機利用該樓層安置的藍牙iBeacon設備進行數據采集。使用采集的260個參考點構建指紋數據庫，每個參考點采集40次，東南西北方向各10次（藍牙信號強度會受室內人體走動或受靜態環境的影響，造成信號波動，這么做是為了避免身體遮擋對信號的影響），每一秒采集一次，取平均值以及對應的，坐標（以圖3中的實心點為原點建立直角坐標系）進行儲存。在實驗區域內隨機選擇了40個測試點（每個測試點也采集40次，東西南北方向各10次，每秒采集一次，取平均值以及對應的，坐標進行儲存）作為在線定位實驗樣本。

圖3 實驗區域平面圖以及部分參考點劃分位置

4.2 實驗結果分析

ML層次聚類中閾值的選擇決定了聚類效果的好壞，將會影響最終的定位準確度。本文選取了值為7，8，9，10，11，12來進行實驗對比，圖4為提出的ML層次聚類和自適應WKNN算法對閾值的取值進行的實驗結果。

圖4 閾值T不同取值的定位平均誤差對比

由圖4所得，當值取7，8，9，10，11，12時，定位平均誤差分別為2.22，1.79，1.66，1.60，1.68和1.73 m，表明的值取7，8，9，10時，定位準確度逐漸提高，且= 10時，定位準確度達到最高。當取11，12時，定位準確度又逐漸下降，所以后面實驗的值選擇為10。

為了驗證算法的定位性能，實驗使用相同的指紋數據庫和測試集，分別對提出的算法、WKNN和EWKNN定位算法進行定位實驗。從平均定位誤差，累積定位誤差，單點定位誤差、最大和最小定位誤差、標準差和算法運行時間等方面來分析算法的定位性能。

圖5為本文所提出的ML層次聚類和自適應WKNN定位算法和其他兩種定位方法的平均定位誤差柱狀圖。由圖5可知，ML層次聚類和自適應WKNN定位算法的最終平均定位誤差為1.60m，EWKNN平均定位誤差為1.95m，而WKNN平均定位誤差則為2.29m，提出的算法在定位準確度上和WKNN、EWKNN相比分別提高了30.0％和18.0％。

圖5 3種定位算法的平均定位誤差

ML層次聚類和自適應WKNN定位算法與其他兩種算法的累積定位誤差分布概率如圖6所示，將誤差分布概率數據呈現在表1中。從圖6和表1可以觀察出各種算法的定位準確度的趨勢，從圖6中可以發現本文提出的ML層次聚類和自適應WKNN定位算法定位誤差在1.5 m內達到了67.5％，在定位準確度上較其他兩種定位算法有很大的提升。ML層次聚類和自適應WKNN定位算法的定位誤差在2 m以內達到了77.5％，定位成功率在2.5 m以內達到了90％。綜上所述，本文提出的定位算法在平均定位誤差和累積定位誤差上都要優于其他兩種算法。

圖6 累積定位誤差分析

表1 3種算法定位結果對比

對40個待定位點使用ML層次聚類-自適應WKNN算法與WKNN，EWKNN算法進行位置估計，每一個待定位點的定位誤差比較如圖7所示，定位誤差的最大、最小誤差、定位平均誤差、標準差統計如表2所示。由圖7和表2可知，ML層次聚類-自適應WKNN算法的最大誤差距離為3.48 m，EWKNN算法的最大誤差距離為4.06 m，提出的算法最小誤差也比EWKNN算法要小。從圖7可以看出提出的算法較WKNN和EWKNN算法整體的定位準確度有所提升，而且波動較小，從表2可以看出提出算法的標準差較小，定位的穩定性更好。

圖7 3種算法的單點定位誤差比較

表2 改進算法與其他兩種算法最大、最小誤差、定位平均誤差和標準差對比

采用Matlab軟件對3種定位算法在相同的軟硬件環境下分別運行20次仿真，并對算法運算時間進行統計，將20次結果取平均值，得到3種定位算法的平均運算時間如表3所示。ML層次聚類和自適應WKNN定位算法由于在離線階段對指紋數據庫進行了聚類處理，減小了在線匹配的范圍，降低了在線匹配階段的運算量，最終運算時間較其他兩種算法均有減少。而EWKNN算法在在線匹配階段由于需要通過計算對值進行選擇，并且需要計算測試集與指紋數據庫中所有參考點之間的歐氏距離，大大增加了計算量，所以運算時間較WKNN算法有所增加。WKNN雖然運算時間和EWKNN算法相比有所降低，但傳統的WKNN算法對每一個待定位點都選取相同的值進行定位匹配，導致定位準確度不高。綜上所述和其他兩種算法相比，本文提出的ML層次聚類和自適應WKNN定位算法在定位準確度有了提高，在算法平均運算時間上有減小。

表3 3種算法平均運算時間比較

5 結語

針對WKNN算法采用固定的值，EWKNN算法需要調整閾值來動態確定值而導致的定位時間長、定位準確度低等問題，提出了基于ML層次聚類和自適應WKNN的組合定位算法。算法先通過層次聚類，縮小在線匹配范圍，濾除掉相似度較小的參考點，在線匹配階段，根據距離集合的標準差來自動篩選值。在學院理工樓4樓進行了定位實驗，使用采集的260個參考點構建指紋數據庫，并在實驗區域內隨機選擇了40個測試點作為在線定位實驗樣本。實驗結果表明，ML層次聚類和自適應WKNN定位算法的平均定位誤差為1.60 m，在定位平均誤差上比WKNN算法、EWKNN算法分別降低了30.0%和18.0%。算法的平均運算時間為0.63 s，在運算時間上比WKNN、EWKNN分別降低19.2%和28.4%。本文提出的算法在類似的環境下可以較好地根據各參考點之間的相似度進行聚類劃分，在此基礎上再進行自適應的在線匹配算法，從而提高定位準確度。另外在位置指紋庫數據庫的建立上，本文采用的方法是在每一個參考點上多次采集信號強度，如果實驗區域較大，那么建立數據庫的工作量將會非常大，因此在離線階段如何快捷準確地構建數據庫還需要繼續研究，進一步改善定位效果。

[1] ENGE P K. The global positioning system: signals, measurements, and performance[J]. International Journal of Wireless Information Networks, 1994, 1(2): 83-105.

[2] 魏亞靜, 袁海波, 董紹武, 等.BDS星鐘預報誤差分析及對授時性能的影響[J]. 時間頻率學報, 2016, 39(4): 301-307.

[3] 肖秋龍, 成芳, 沈朋禮, 等. 北斗地基增強系統觀測數據質量分析[J]. 時間頻率學報, 2019, 42(3): 266-273.

[4] 武文俊, 廣偉, 張繼海, 等. 北斗亞歐共視時間比對試驗[J]. 時間頻率學報, 2018, 41(3): 200-205.

[5] 何靜, 劉冉, 肖宇峰, 等. 融合RFID相位差和激光掃描的動態目標定位[J]. 儀器儀表學報, 2018, 39(2): 81-88.

[6] GIGL T, JANSSEN G J M, DIZDAREVIC V, et al. Analysis of a UWB indoor positioning system based on received signal strength[C] // IEEE 2007 4th Workshop on Positioning, Navigation and Communication, Hannover: IEEE, 2007: 97-101.

[7] 李奇越, 李偉, 孫偉, 等. 基于RSSI和輔助節點協作的Wi-Fi室內定位方法[J]. 電子測量與儀器學報, 2016, 30(5): 794-802.

[8] 卞合善. 基于藍牙4.0低功耗室內定位研究[D]. 北京: 北京郵電大學, 2015.

[9] 張凱楠. 低功耗藍牙組網和定位技術研究[D]. 北京: 北京郵電大學, 2018.

[10] ELKAFRAWY K, YOUSSEF M, ELKEYI A, et al. Propagation modeling for accurate indoor WLAN RSS-based localization[C] //IEEE Vehicular Technology Conference(VTC’10),Ottawa: IEEE, 2010.

[11] 夏穎, 馬琳, 張中兆, 等. 基于半監督流形學習的WLAN室內定位算法[J]. 系統工程與電子技術, 2014, 36(7): 1422-1427.

[12] 吳澤泰, 蔡仁欽, 徐書燕, 等. 基于K近鄰法的WiFi定位研究與改進[J]. 計算機工程, 2017, 43(3): 289-293.

[13] FANG Y Q, DENG Z, XUE C, et al. Application of an improved K nearest neighbor algorithm in WiFi indoor positioning[C]//China Satellite Navigation Conference 2015, Xi’an: Organizing Committee of the 6th China Satellite Navigation Academy Annual Conference, 2015: 517-524.

[14] SHIN B, LEE J H, LEE T, et al. Enhanced weighted K-nearest neighbor algorithm for indoor Wi-Fi positioning systems[C]//2012 8th International Conference on Computing Technology and Information Management, Seoul: IEEE, 2012: 574-577.

[15] 吉彩云, 袁明輝, 李瑞祥, 等. 基于K-means的室內定位加權優化k-NN算法[J]. 電子測量技術, 2018, 41(10): 66-69.

[16] 陳望, 賈振紅, 覃錫忠, 等. 基于改進K-means聚類算法的室內WLAN定位研究[J]. 激光雜志, 2014, 35(7): 11-14.

[17] 王怡婷, 郭紅. 基于層次聚類的WiFi室內位置指紋定位算法[J]. 福州大學學報(自然科學版), 2017, 45(1): 8-15.

[18] 段明秀. 層次聚類算法的研究及應用[D]. 長沙: 中南大學, 2009.

[19] 常津銘, 王紅蕾. 基于層次聚類和貝葉斯的室內定位算法[J]. 計算機時代, 2019(2): 5-8.

An indoor positioning algorithm based on hierarchical clustering and adaptive weighted K nearest neighbor combination

ZHAI Jun-jie1,2,3, LI Ting-hui1, HUANG Fei-jiang1,2,3,*, YUAN Hai-bo4, ZHANG Hong4, HU Chuan-jun1,3

(1. College of Electronic Engineering, Guangxi Normal University, Guilin 541004, China;2. College of Information and Communication Engineering, Guangzhou Maritime University, Guangzhou 510725, China;3. College of Electronic Information and Electrical Engineering, Changsha University, Changsha 410022, China;4. National Time Service Center, Chinese Academy of Sciences, Xi’an 710600, China)

Aiming at the problem that the location fingerprint indoor positioning algorithm based on received signal strength (RSS) with low positioning precision, this study proposed an indoor positioning algorithm based on mean-linkage (ML) hierarchical clustering and adaptive weighted K nearest neighbor (WKNN) combination. Firstly, the Bluetooth signal strength is collected at the set reference point to construct an offline fingerprint database. Then, using ML hierarchical clustering method, all reference points are divided intocategories according to the similarity between them, and the reference point with less similarity is filtered out. Finally, according to the similarity of the signal distance between the point to be located and the reference point, the standard deviation of the distance difference is calculated to adaptively determine thevalue and perform the position estimation. The experimental results show that the proposed algorithm improves the positioning precision by 30.0% and 18.0% compared with WKNN and EWKNN respectively, and improves the positioning real-time by 19.2% and 28.4% compared with WKNN and EWKNN respectively. The algorithm is applied to indoor object positioning, which can simultaneously improve positioning precision and positioning real-time.

indoor positioning; received signal strength (RSS); fingerprint database; mean-linkage hierarchical clustering; adaptive weighted K nearest neighbor

10.13875/j.issn.1674-0637.2020-04-0300-10

翟俊杰, 李廷會, 黃飛江, 等. 一種層次聚類和自適應加權K近鄰組合的室內定位算法[J]. 時間頻率學報, 2020, 43(4): 300-309.

2020-05-21；

2020-06-20；

國家自然科學基金資助項目（61964004）；湖南省自然科學基金資助項目（2015JJ2016）；長沙學院“青年英才支持計劃”和科研基金資助項目（SF1615）