一種層次聚類和自適應(yīng)加權(quán)K近鄰組合的室內(nèi)定位算法

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

一種層次聚類和自適應(yīng)加權(quán)K近鄰組合的室內(nèi)定位算法

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

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

針對(duì)基于接收信號(hào)強(qiáng)度的位置指紋室內(nèi)定位算法定位精度不高的問(wèn)題，提出了一種均值層次聚類和自適應(yīng)加權(quán)K近鄰（weighted K nearest neighbor，WKNN）的室內(nèi)定位算法。算法首先在設(shè)置的參考點(diǎn)上采集藍(lán)牙信號(hào)強(qiáng)度構(gòu)建離線指紋數(shù)據(jù)庫(kù)，然后采用均值層次聚類方法將所有參考點(diǎn)根據(jù)各自之間的相似度分為個(gè)類，濾除掉相似度較小的參考點(diǎn)，最后根據(jù)待定位點(diǎn)和參考點(diǎn)間的信號(hào)距離的相似度，計(jì)算出距離差的標(biāo)準(zhǔn)差來(lái)自適應(yīng)確定值，并進(jìn)行位置估算。實(shí)驗(yàn)結(jié)果表明，本文提出的算法在定位精度上比WKNN、動(dòng)態(tài)加權(quán)K近鄰（enhanced weighted K nearest neighbor，EWKNN）方法分別提升了30.0% 和18.0%，在定位實(shí)時(shí)性上比WKNN和EWKNN方法分別提高了19.2%和28.4%。將該算法用于室內(nèi)物體定位，可以同時(shí)提高定位精度和定位實(shí)時(shí)性。

室內(nèi)定位；接收信號(hào)強(qiáng)度；指紋數(shù)據(jù)庫(kù)；均值層次聚類；自適應(yīng)加權(quán)K近鄰

0 引言

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

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

針對(duì)以上問(wèn)題，本文提出了基于均值（mean-link，ML）層次聚類和自適應(yīng)WKNN組合的定位算法。在離線階段通過(guò)ML層次聚類處理數(shù)據(jù)庫(kù)中的參考點(diǎn)，降低搜索范圍，減少了定位時(shí)間，也排除了在線階段的錯(cuò)誤匹配點(diǎn)。在線匹配階段通過(guò)求待定位點(diǎn)與參考點(diǎn)的距離集合的標(biāo)準(zhǔn)差來(lái)自適應(yīng)選擇值進(jìn)行位置估計(jì)，提高了定位準(zhǔn)確度，減少了定位時(shí)間。

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

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

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

離線階段：在實(shí)驗(yàn)區(qū)域內(nèi)劃分好參考點(diǎn)，在每一個(gè)參考點(diǎn)上進(jìn)行藍(lán)牙信號(hào)強(qiáng)度的采集，并記錄對(duì)應(yīng)的參考點(diǎn)坐標(biāo)，記錄格式為

在線階段：用戶進(jìn)入實(shí)驗(yàn)區(qū)域內(nèi)的某一位置，將接收到的藍(lán)牙AP信號(hào)強(qiáng)度記錄下來(lái)，將其與指紋數(shù)據(jù)庫(kù)中的信號(hào)強(qiáng)度進(jìn)行搜尋，尋找最佳的匹配點(diǎn)，并使用定位匹配算法計(jì)算出估計(jì)位置坐標(biāo)。常見的匹配算法包括KNN，WKNN，貝葉斯分類算法等。

2 層次聚類算法原理

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

本文采用的ML層次聚類屬于凝聚層次聚類，將離線階段的每一個(gè)參考點(diǎn)視為不同的類，通過(guò)合并規(guī)則對(duì)參考點(diǎn)進(jìn)行凝聚，直到達(dá)到終止條件停止凝聚。最小距離法和最大距離法使用類間最小距離和類間最大距離作為聚類標(biāo)準(zhǔn)不夠嚴(yán)謹(jǐn)，對(duì)離群點(diǎn)比較敏感，會(huì)過(guò)于關(guān)注局域連接，應(yīng)用在室內(nèi)定位中，聚類結(jié)果無(wú)法達(dá)到預(yù)期效果。而采用均值或平均距離聚類法對(duì)數(shù)據(jù)庫(kù)進(jìn)行聚類，可以解決算法對(duì)離群點(diǎn)過(guò)于敏感的問(wèn)題，但是平均距離法計(jì)算量較大，每次聚類都需要計(jì)算類與類包含的所有數(shù)據(jù)點(diǎn)間相互的歐式距離，所以采用ML層次聚類，更加契合室內(nèi)定位的場(chǎng)景。

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

① 在實(shí)驗(yàn)區(qū)域選取參考點(diǎn)，采集藍(lán)牙信號(hào)，建立信號(hào)指紋數(shù)據(jù)庫(kù)，計(jì)算出所有參考點(diǎn)兩兩之間的歐氏距離：

② 計(jì)算完成后開始聚類，每一次迭代將歐式距離最小的兩個(gè)類合并成一個(gè)新的類，并計(jì)算出新類的中心點(diǎn)。當(dāng)類與類之間的中心點(diǎn)距離大于閾值時(shí)，停止合并。

③ 聚類結(jié)束后，計(jì)算所有類中心的信號(hào)強(qiáng)度：

3 基于ML層次聚類和自適應(yīng)WKNN的定位算法

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

自適應(yīng)WKNN算法是在ML層次聚類的基礎(chǔ)上，根據(jù)待定位點(diǎn)與參考點(diǎn)之間的信號(hào)距離差的標(biāo)準(zhǔn)差來(lái)自適應(yīng)調(diào)整值。在實(shí)際的定位空間中，存在狹窄區(qū)域，也有寬敞的區(qū)域，對(duì)于不同面積的定位區(qū)域，所設(shè)定的參考點(diǎn)數(shù)量也不同，若每一次定位都選取固定的值，可能會(huì)引入相似度很小的參考點(diǎn)，定位的結(jié)果將會(huì)帶來(lái)很大誤差。本文算法對(duì)于每一個(gè)不同的待定位點(diǎn)，都會(huì)在ML層次聚類的結(jié)果上選取相似度最高的類進(jìn)行匹配，濾除掉誤差點(diǎn)，進(jìn)而選取最優(yōu)值，提高定位準(zhǔn)確度。自適應(yīng)WKNN算法是在ML層次聚類對(duì)數(shù)據(jù)庫(kù)處理的基礎(chǔ)上進(jìn)行位置估計(jì)，具體實(shí)施步驟如下：

式（6）中，為參考點(diǎn)的個(gè)數(shù)。

④ 對(duì)剩余的個(gè)參考點(diǎn)使用WKNN算法進(jìn)行位置估計(jì)：

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

圖2 ML層次聚類和自適應(yīng)WKNN定位算法流程圖

基于ML層次聚類和自適應(yīng)WKNN定位算法詳細(xì)流程如下：

① 通過(guò)式（3）計(jì)算數(shù)據(jù)庫(kù)中參考點(diǎn)兩兩之間的歐氏距離，每一次聚類將距離最小的兩個(gè)點(diǎn)進(jìn)行合并，每一次聚類都自動(dòng)更新類的中心。設(shè)置閾值，當(dāng)兩個(gè)類之間的中心距離大于時(shí)，聚類停止；

② 聚類結(jié)束后，根據(jù)式（4）計(jì)算所有類中心的信號(hào)強(qiáng)度，用于在線階段的快速匹配；

③ 在線階段，采集待定位點(diǎn)的藍(lán)牙信號(hào)強(qiáng)度，通過(guò)式（5）尋找到離待定位點(diǎn)最近的類C；

⑤ 根據(jù)算出的平均值來(lái)通過(guò)式（7）進(jìn)一步求出標(biāo)準(zhǔn)差，濾除掉大于標(biāo)準(zhǔn)差的參考點(diǎn)，最終篩選出值，自適應(yīng)的選取值，并通過(guò)式（8）來(lái)得出位置估計(jì)。

4 實(shí)驗(yàn)和結(jié)果分析

為了驗(yàn)證本文提出算法的定位性能，對(duì)ML層次聚類和自適應(yīng)WKNN組合的定位算法、EWKNN算法與WKNN算法進(jìn)行定位實(shí)驗(yàn)比較。

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)選擇在學(xué)院理工樓4樓進(jìn)行，如圖3所示。圖中的標(biāo)記點(diǎn)為離線指紋數(shù)據(jù)庫(kù)中的部分參考點(diǎn)，參考點(diǎn)之間間隔1m，使用華為手機(jī)利用該樓層安置的藍(lán)牙iBeacon設(shè)備進(jìn)行數(shù)據(jù)采集。使用采集的260個(gè)參考點(diǎn)構(gòu)建指紋數(shù)據(jù)庫(kù)，每個(gè)參考點(diǎn)采集40次，東南西北方向各10次（藍(lán)牙信號(hào)強(qiáng)度會(huì)受室內(nèi)人體走動(dòng)或受靜態(tài)環(huán)境的影響，造成信號(hào)波動(dòng)，這么做是為了避免身體遮擋對(duì)信號(hào)的影響），每一秒采集一次，取平均值以及對(duì)應(yīng)的，坐標(biāo)（以圖3中的實(shí)心點(diǎn)為原點(diǎn)建立直角坐標(biāo)系）進(jìn)行儲(chǔ)存。在實(shí)驗(yàn)區(qū)域內(nèi)隨機(jī)選擇了40個(gè)測(cè)試點(diǎn)（每個(gè)測(cè)試點(diǎn)也采集40次，東西南北方向各10次，每秒采集一次，取平均值以及對(duì)應(yīng)的，坐標(biāo)進(jìn)行儲(chǔ)存）作為在線定位實(shí)驗(yàn)樣本。

圖3 實(shí)驗(yàn)區(qū)域平面圖以及部分參考點(diǎn)劃分位置

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

ML層次聚類中閾值的選擇決定了聚類效果的好壞，將會(huì)影響最終的定位準(zhǔn)確度。本文選取了值為7，8，9，10，11，12來(lái)進(jìn)行實(shí)驗(yàn)對(duì)比，圖4為提出的ML層次聚類和自適應(yīng)WKNN算法對(duì)閾值的取值進(jìn)行的實(shí)驗(yàn)結(jié)果。

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

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

為了驗(yàn)證算法的定位性能，實(shí)驗(yàn)使用相同的指紋數(shù)據(jù)庫(kù)和測(cè)試集，分別對(duì)提出的算法、WKNN和EWKNN定位算法進(jìn)行定位實(shí)驗(yàn)。從平均定位誤差，累積定位誤差，單點(diǎn)定位誤差、最大和最小定位誤差、標(biāo)準(zhǔn)差和算法運(yùn)行時(shí)間等方面來(lái)分析算法的定位性能。

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

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

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

圖6 累積定位誤差分析

表1 3種算法定位結(jié)果對(duì)比

對(duì)40個(gè)待定位點(diǎn)使用ML層次聚類-自適應(yīng)WKNN算法與WKNN，EWKNN算法進(jìn)行位置估計(jì)，每一個(gè)待定位點(diǎn)的定位誤差比較如圖7所示，定位誤差的最大、最小誤差、定位平均誤差、標(biāo)準(zhǔn)差統(tǒng)計(jì)如表2所示。由圖7和表2可知，ML層次聚類-自適應(yīng)WKNN算法的最大誤差距離為3.48 m，EWKNN算法的最大誤差距離為4.06 m，提出的算法最小誤差也比EWKNN算法要小。從圖7可以看出提出的算法較WKNN和EWKNN算法整體的定位準(zhǔn)確度有所提升，而且波動(dòng)較小，從表2可以看出提出算法的標(biāo)準(zhǔn)差較小，定位的穩(wěn)定性更好。

圖7 3種算法的單點(diǎn)定位誤差比較

表2 改進(jìn)算法與其他兩種算法最大、最小誤差、定位平均誤差和標(biāo)準(zhǔn)差對(duì)比

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

表3 3種算法平均運(yùn)算時(shí)間比較

5 結(jié)語(yǔ)

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

[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星鐘預(yù)報(bào)誤差分析及對(duì)授時(shí)性能的影響[J]. 時(shí)間頻率學(xué)報(bào), 2016, 39(4): 301-307.

[3] 肖秋龍, 成芳, 沈朋禮, 等. 北斗地基增強(qiáng)系統(tǒng)觀測(cè)數(shù)據(jù)質(zhì)量分析[J]. 時(shí)間頻率學(xué)報(bào), 2019, 42(3): 266-273.

[4] 武文俊, 廣偉, 張繼海, 等. 北斗亞歐共視時(shí)間比對(duì)試驗(yàn)[J]. 時(shí)間頻率學(xué)報(bào), 2018, 41(3): 200-205.

[5] 何靜, 劉冉, 肖宇峰, 等. 融合RFID相位差和激光掃描的動(dòng)態(tài)目標(biāo)定位[J]. 儀器儀表學(xué)報(bào), 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和輔助節(jié)點(diǎn)協(xié)作的Wi-Fi室內(nèi)定位方法[J]. 電子測(cè)量與儀器學(xué)報(bào), 2016, 30(5): 794-802.

[8] 卞合善. 基于藍(lán)牙4.0低功耗室內(nèi)定位研究[D]. 北京: 北京郵電大學(xué), 2015.

[9] 張凱楠. 低功耗藍(lán)牙組網(wǎng)和定位技術(shù)研究[D]. 北京: 北京郵電大學(xué), 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] 夏穎, 馬琳, 張中兆, 等. 基于半監(jiān)督流形學(xué)習(xí)的WLAN室內(nèi)定位算法[J]. 系統(tǒng)工程與電子技術(shù), 2014, 36(7): 1422-1427.

[12] 吳澤泰, 蔡仁欽, 徐書燕, 等. 基于K近鄰法的WiFi定位研究與改進(jìn)[J]. 計(jì)算機(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的室內(nèi)定位加權(quán)優(yōu)化k-NN算法[J]. 電子測(cè)量技術(shù), 2018, 41(10): 66-69.

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

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

[18] 段明秀. 層次聚類算法的研究及應(yīng)用[D]. 長(zhǎng)沙: 中南大學(xué), 2009.

[19] 常津銘, 王紅蕾. 基于層次聚類和貝葉斯的室內(nèi)定位算法[J]. 計(jì)算機(jī)時(shí)代, 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

翟俊杰, 李廷會(huì), 黃飛江, 等. 一種層次聚類和自適應(yīng)加權(quán)K近鄰組合的室內(nèi)定位算法[J]. 時(shí)間頻率學(xué)報(bào), 2020, 43(4): 300-309.

2020-05-21；

2020-06-20；

國(guó)家自然科學(xué)基金資助項(xiàng)目（61964004）；湖南省自然科學(xué)基金資助項(xiàng)目（2015JJ2016）；長(zhǎng)沙學(xué)院“青年英才支持計(jì)劃”和科研基金資助項(xiàng)目（SF1615）