0 引言

    在智能終端快速更換的時代，人們生活水平不斷提升，圖書館、博物館等室內(nèi)場景需提供精確位置信息來提供服務(wù)。技術(shù)成熟的全球定位系統(tǒng)(Global Positioning System，GPS)已實現(xiàn)了應(yīng)用范圍廣、精度高、實時性好的室外定位^[1]，但在室內(nèi)中受復(fù)雜環(huán)境因素的影響，GPS信號因受阻擋而急速衰減，無法滿足人們的室內(nèi)定位需求，因而催生出很多室內(nèi)定位技術(shù)。其中，配備有藍牙技術(shù)的iBeacon因其功耗低、成本低、效率高等優(yōu)點備受人們的青睞。

    iBeacon主要通過基于接收信號強度指示(Received Signal Strength Indication，RSSI)的位置指紋實現(xiàn)定位，即通過智能終端測量RSSI，依據(jù)采樣點間RSSI的差異構(gòu)建位置指紋庫^[2]，再利用匹配定位算法得到定位結(jié)果。但是當定位區(qū)域較大時，指紋庫中存儲的位置信息較多，導(dǎo)致運算量過大并影響定位精度。對此，文獻[3-6]采用K-means算法對指紋庫進行聚類分析，選出相似度最高的子庫進行匹配定位。該方法不僅可降低計算的負荷與能耗，還可有效提高定位的實時性。然而其多是依據(jù)經(jīng)驗選定聚類的個數(shù)，未對聚類優(yōu)劣進行說明；且通過待測點與聚類中心的歐式聚類判斷其所屬類別，并未考慮各個變量之間的相關(guān)性。

    針對上述存在的問題，本文提出優(yōu)化算法：采用兩步聚類算法根據(jù)AIC準則自動選定最優(yōu)聚類情況，利用相關(guān)系數(shù)法得到與待測點最相似的子庫，最后采用K鄰近法與子庫匹配得到定位結(jié)果。

1 K-means指紋定位

    K-means指紋定位是在原指紋定位算法的基礎(chǔ)上，先對指紋庫進行聚類分析，再通過匹配算法估計待測點位置的一種算法。即離線階段，構(gòu)建指紋庫后，通過K-means聚類根據(jù)特征參數(shù)將指紋庫劃分為k個子庫；匹配階段，首先比較待測點與各聚類中心的相似程度，選取距離最短的聚類中心所在的子庫，再將其與待測點匹配估計最終坐標。具體操作流程如圖1所示。

1.1 K-means聚類

    指紋庫中第i個參考點(Reference Point，RP)接收到接入點(Access Point，AP)的RSSI信號記為RSSI_i=[RSSI_i1，…，RSSI_ij，…，RSSI_in]，j=1，…，n，其中RP的個數(shù)為m，AP的個數(shù)為n。由其構(gòu)建指紋庫的RSSI=[RSSI₁，RSSI₂，…，RSSI_i，…，RSSI_m]^T，i=1，…，m。已知聚類數(shù)目為k(k≤m)的前提下，將指紋庫的RSSI分為k類RSSI=[C₁，C₂，…，C_k]，隨機選用k個向量作為初始聚類中心，以歐氏距離作為相似度準則就近分配指紋數(shù)據(jù)，不斷迭代更新聚類中心，直至算法收斂或達到最大迭代次數(shù)。當總的類間離散度最小時認為算法收斂，即：

式中，k為聚類個數(shù)，Center_t為第t個聚類中心。具體算法流程^[7]如下。

    K-means算法流程：

輸入：從指紋庫的RSSI中隨機選取k個向量作為初始聚類中心；

輸出：最終聚類結(jié)果。

For  i=1:k

    (1)計算樣本中各指紋到每個聚類中心的距離，并根據(jù)就近原則分配指紋到不同類中；

    (2)分配完樣本中指紋后，重新計算k個聚類的中心；

    (3)計算總的類間離散度J_c

       If Jc最小，即算法收斂

          Break;//跳出循環(huán)，結(jié)束迭代過程

       End

End

1.2 匹配算法

    本節(jié)所介紹的算法，主要選取相似度最高的子指紋庫，并估計待測點的最終位置。

1.2.1 最鄰近法

    最鄰近法(Nearest Neighborhood，NN)是最簡單、最基礎(chǔ)的算法，首先算出待測點RSSI與指紋庫中各指紋的RSSI之間的距離，再選取距離最短的指紋坐標值作為待測點的估計位置。其中距離的公式為：

式中，D_i表示待測點與第i個RP的距離，S_j表示待測點接收到第j個AP的信號強度，RSSI_ij表示第i個RP接收到第j個AP的信號強度。q=1時是絕對距離，q=2時是歐式距離，通過實際情況分析后選取合適的距離公式。

1.2.2 K鄰近法

    K鄰近法(K Nearest Neighborhood，KNN)是對最鄰近法的改進，其區(qū)別主要在于K鄰近法并不直接選擇距離最短的一個指紋來估算位置，而是選擇距離最短的前K(K≥2)個指紋，并將這K個指紋的平均坐標作為最后的估計位置。即通過式(2)得到距離后將位置從小到大排序，選取前K個指紋坐標，利用式(3)計算出均值坐標并輸出最后結(jié)果。

式中，(x_i，y_i)表示排序后選取的前K個指紋中第i個指紋的坐標值。

1.2.3 相關(guān)系數(shù)法

    相關(guān)系數(shù)法通過計算兩個物體間的相似程度^[8]，判斷其距離的相對大小。地理學(xué)第一定律^[9]指出，任何兩個物體之間都是相似的，只是相似程度的大小不同，并且其相似程度隨著距離的增加在不斷減少。

    在定位范圍內(nèi)，假設(shè)A、B兩個待測點空間位置很近，其接收到AP的RSSI分別記為RSSI_A=[S_A1，S_A2，…，S_An]和RSSI_B=[S_B1，S_B2，…，S_Bn]，根據(jù)式(4)計算兩點間的相關(guān)系數(shù)：

式中，ρ(A，B)為兩點間相關(guān)系數(shù)，(x_i，y_i)為所取K個指紋中第i個的坐標值。

    由前面分析可知，K-means聚類需要預(yù)先給定聚類的數(shù)目，其多是依據(jù)經(jīng)驗進行選擇并通過定位精度評估聚類的質(zhì)量。而在實際情況中影響定位精度的原因有很多，所以需要一種準則來評估聚類結(jié)果。兩步聚類是一種探索性聚類方法，通過分析數(shù)據(jù)間類別結(jié)構(gòu)來構(gòu)建聚類模型，根據(jù)AIC準則評估聚類質(zhì)量并擇優(yōu)選出聚類個數(shù)。

2 優(yōu)化后的指紋定位

2.1 AIC準則

    AIC準則^[11]是日本統(tǒng)計學(xué)家赤池宏次提出關(guān)于衡量統(tǒng)計模型優(yōu)良的一種標準，主要在模型復(fù)雜度和參數(shù)個數(shù)之間找到一種平衡，從而選擇最優(yōu)模型。其定義為：

其中，k為參數(shù)的個數(shù)，L為樣本集上的極大似然函數(shù)。為優(yōu)化其擬合性可增加參數(shù)的個數(shù)，但要注意防止出現(xiàn)過度擬合。給定一組參數(shù)模型時，要優(yōu)先考慮AIC值最小的模型，因為它包含最少的參數(shù)個數(shù)又最大程度地還原數(shù)據(jù)模型。

    文獻[12]給出了利用AIC準則選取最鄰近聚類模型的具體理論分析，分析發(fā)現(xiàn)：類內(nèi)誤差隨聚類數(shù)目k的增加而越小，為考慮聚類模型的緊湊型與實用性，選擇AIC值最小的聚類模型，即可得到最優(yōu)的分類情況。

2.2 兩步聚類

    兩步聚類是一種探索性聚類方法，主要有兩個階段，其具體流程如圖2所示。

    (1)預(yù)聚類階段：構(gòu)建聚類特征樹(Clustering Feature Tree，CFT)，將指紋庫分為許多子庫。

    首先，將某一個觀測值置于根節(jié)點處并記錄相關(guān)變量信息，根據(jù)給定的距離公式作為相似性依據(jù)，依次判斷其他測量值與已有節(jié)點的相似性并進行分類，若沒有相似節(jié)點，則生成新節(jié)點。所有RP分類后，根據(jù)AIC準則，確定預(yù)聚類的數(shù)目。

    (2)正式聚類階段：合并聚類，給出最終優(yōu)化的聚類數(shù)目。

    將預(yù)聚類的數(shù)目作為數(shù)據(jù)輸入，使用分層聚類對其進行再聚類不斷合并修剪預(yù)聚類結(jié)果，通過AIC準則評估現(xiàn)有分類的質(zhì)量，最終給出符合準則的分類方案。

2.3 優(yōu)化算法

    K-means隨機選取聚類個數(shù)與聚類中心帶來極大的不穩(wěn)定性，對此使用兩步聚類算法選擇最優(yōu)聚類數(shù)并對其分類。文獻[10]分析實驗數(shù)據(jù)發(fā)現(xiàn)：RSSI相關(guān)系數(shù)匹配法比NN匹配定位精度高，但是實時性差。為提高定位精度、增強算法實時性，本文使用相關(guān)系數(shù)法選取子指紋庫，使用KNN算法估計待測點位置。具體操作如圖3所示。

3 實驗布置與結(jié)果分析

3.1 實驗環(huán)境

    本實驗在8 m×14 m的典型辦公環(huán)境中進行，室內(nèi)布局情況如圖4所示，將信標節(jié)點AP呈大致均勻擺放，此區(qū)域放置12個AP。經(jīng)測試發(fā)現(xiàn)，采集的RSSI數(shù)據(jù)在1 m范圍內(nèi)波動較小，由此可將定位區(qū)域劃分為1 m×1 m的小區(qū)域，并在每個區(qū)域頂點采集數(shù)據(jù)，為消除方向引起的誤差，在每個RP不同方向進行采樣。受物體擺放情況的影響，最終共采集438組數(shù)據(jù)。根據(jù)移動路徑(圖4中路徑)，采集107組數(shù)據(jù)。

3.2 實驗分析

    為方便討論定位效果，需選定合適的參數(shù)指標對其進行說明。一定程度上，平均定位誤差可反映算法的整體效果，定位誤差的標準差可說明定位精度的一致性^[13]；運算時間可反映算法的實時性。本文主要從考慮算法的精度和實時性出發(fā)，因而選用平均定位誤差、誤差的標準差和運算時間來判斷算法的定位效果。

    本文重點討論聚類算法對定位結(jié)果的影響，為排除其他因素的影響，首先利用傳統(tǒng)指紋定位選擇最優(yōu)的距離公式與K值，實驗結(jié)果如圖5所示。觀察圖5(a)可發(fā)現(xiàn)：使用NN算法定位時，絕對距離的效果優(yōu)于歐式距離；而使用KNN算法時，歐式距離的效果更加顯著；不論選擇哪個距離公式，使用KNN算法的定位效果都優(yōu)于NN算法，圖5(b)也可得出此結(jié)論。因而，使用NN算法計算絕對距離判斷所屬子庫；使用KNN算法估計最終位置坐標，并令k=5達到較好的定位效果。

    SPSS軟件操作便捷、功能強大、運算速度快，直接使用該軟件對指紋庫RSSI進行兩步聚類分析，根據(jù)AIC準則自動得到最優(yōu)聚類個數(shù)與聚類分布情況。為排除所設(shè)聚類個數(shù)對結(jié)果的影響，設(shè)定最大聚類數(shù)目為100，自動聚類結(jié)果如圖6所示。圖6(a)顯示出自動聚類過程中AIC值的變化情況：聚類效果的好壞并不隨聚類數(shù)目的增加無限增長，而是呈凹曲線變化且最優(yōu)的聚類個數(shù)較小。圖6(b)顯示出擇優(yōu)后的聚類情況：聚類數(shù)目為9，平均Silhouette為0.6，聚類質(zhì)量良好且每類數(shù)目較均勻。圖6(c)顯示分類后每個類別的具體坐標值：同一位置的多個數(shù)據(jù)可能劃分到不同類別，也驗證了同一位置需在多個方向采集數(shù)據(jù)。

    本文主要考證所提算法在定位精度與實時性方面有改善效果，因而選用定位效果較好的參數(shù)進行分析。即聚類個數(shù)為9，利用NN算法計算絕對距離判斷所屬子指紋庫，使用k=5的KNN算法計算歐氏距離估計最終位置坐標。所提算法與KNN算法、K-means指紋定位進行比較，實驗結(jié)果顯示在表1中。

    分析表1中數(shù)據(jù)可發(fā)現(xiàn)：(1)與傳統(tǒng)指紋定位相比，聚類后的定位精度雖僅有較小幅度的改善，但運算時間縮短了37.84%~46.32%，即聚類處理后可顯著提高定位的實時性。(2)確定聚類數(shù)目后，不論是用K-means還是兩步聚類對數(shù)據(jù)進行聚類處理，最終的定位精度與實時性都相差無幾，即聚類需預(yù)先得知最優(yōu)的聚類個數(shù)。(3)所提算法與K-means指紋定位相比：雖然運算時間略有增加，但定位精度方面有小幅改善；且K-means指紋定位隨機性大、穩(wěn)定型差，而所提算法使用兩步聚類依據(jù)AIC準則擇優(yōu)得到聚類數(shù)目，極大提高了算法的穩(wěn)定性。綜上述，本文所提算法相比當前已有算法在定位精度、實時性和穩(wěn)定性方面都有一定的改善效果。

4 總結(jié)

    本文通過藍牙技術(shù)進行數(shù)據(jù)采集，針對K-means算法的定位精度較低、定位實時性差、聚類隨機性導(dǎo)致穩(wěn)定性差等問題，提出使用兩步聚類根據(jù)AIC準則自動擇優(yōu)得到聚類數(shù)目，并使用相關(guān)系數(shù)法選擇相似度最高的子指紋庫來對其進行改進。實驗結(jié)果表明：相關(guān)系數(shù)法可以有效提高算法的定位精度；兩步聚類擇優(yōu)得到聚類個數(shù)后，可有效提高算法的穩(wěn)定性和實時性。從整體來看，本文所提算法在定位精度、實時性和穩(wěn)定性方面都有良好的改善。但本文仍有值得改進的地方，如已知聚類個數(shù)的情況下，本文所提算法是以時間為代價提高了定位精度與穩(wěn)定性，接下來的工作中，需繼續(xù)對其優(yōu)化改進。

參考文獻

[1] 田林青，余成波，孔慶達，等.基于藍牙技術(shù)的推送系統(tǒng)的設(shè)計和實現(xiàn)[J].微型機與應(yīng)用，2016，35(20)：61-64.

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

[3] CRAMARIUC A，HUTTUNEN H，LOHAN E S.Clustering benefits in mobile-centric WiFi positioning in multi-floor buildings[C].International Conference on Localization and Gnss.IEEE，2016.

[4] CUI Y，VOYLES R M.A mechanism for real-time decision making and system maintenance for resource constrained robotic systems through ReFrESH[J].Autonomous Robots，2015，39(4)：487-502.

[5] LAITINEN E，LOHAN E S.On the choice of access point selection criterion and other position estimation characteristics for WLAN-based indoor positioning[J].Sensors，2016，16(5)：737.

[6] 張杰，卓靈，朱韻攸.一種K-means聚類算法的改進與應(yīng)用[J].電子技術(shù)應(yīng)用，2015，41(1)：125-128.

[7] 于睿，陸南.基于K均值聚類算法的位置指紋定位技術(shù)[J].信息技術(shù)，2015，39(10)：185-188，191.

[8] 王艷麗，楊如民，余成波，等.相關(guān)性匹配藍牙信標位置指紋庫的室內(nèi)定位[J].電訊技術(shù)，2017，57(2)：145-150.

[9] TOBLER W R.A computer movie simulating urban growth in the Detroit region[J].Economic Geography，1970，46(Supp 1)：234-240.

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

[11] AKAIKE H.Autoregressive model fitting for control[J].Annals of the Institute of Statistical Mathematics，1971，23(1)：163-180.

[12] 秦宣云.基于AIC準則的最近鄰聚類模型的優(yōu)化算法[J].系統(tǒng)工程與電子技術(shù)，2005，27(2)：257-259.

[13] 石欣，印愛民，陳曦.基于RSSI的多維標度室內(nèi)定位算法[J].儀器儀表學(xué)報，2014，35(2)：261-268.