0 引言

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

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

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

1 K-means指紋定位

    K-means指紋定位是在原指紋定位算法的基礎上，先對指紋庫進行聚類分析，再通過匹配算法估計待測點位置的一種算法。即離線階段，構建指紋庫后，通過K-means聚類根據特征參數將指紋庫劃分為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的個數為m，AP的個數為n。由其構建指紋庫的RSSI=[RSSI₁，RSSI₂，…，RSSI_i，…，RSSI_m]^T，i=1，…，m。已知聚類數目為k(k≤m)的前提下，將指紋庫的RSSI分為k類RSSI=[C₁，C₂，…，C_k]，隨機選用k個向量作為初始聚類中心，以歐氏距離作為相似度準則就近分配指紋數據，不斷迭代更新聚類中心，直至算法收斂或達到最大迭代次數。當總的類間離散度最小時認為算法收斂，即：

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

    K-means算法流程：

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

輸出：最終聚類結果。

For  i=1:k

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

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

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

       If Jc最小，即算法收斂

          Break;//跳出循環，結束迭代過程

       End

End

1.2 匹配算法

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

1.2.1 最鄰近法

    最鄰近法(Nearest Neighborhood，NN)是最簡單、最基礎的算法，首先算出待測點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)是對最鄰近法的改進，其區別主要在于K鄰近法并不直接選擇距離最短的一個指紋來估算位置，而是選擇距離最短的前K(K≥2)個指紋，并將這K個指紋的平均坐標作為最后的估計位置。即通過式(2)得到距離后將位置從小到大排序，選取前K個指紋坐標，利用式(3)計算出均值坐標并輸出最后結果。

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

1.2.3 相關系數法

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

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

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

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

2 優化后的指紋定位

2.1 AIC準則

    AIC準則^[11]是日本統計學家赤池宏次提出關于衡量統計模型優良的一種標準，主要在模型復雜度和參數個數之間找到一種平衡，從而選擇最優模型。其定義為：

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

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

2.2 兩步聚類

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

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

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

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

    將預聚類的數目作為數據輸入，使用分層聚類對其進行再聚類不斷合并修剪預聚類結果，通過AIC準則評估現有分類的質量，最終給出符合準則的分類方案。

2.3 優化算法

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

3 實驗布置與結果分析

3.1 實驗環境

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

3.2 實驗分析

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

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

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

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

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

4 總結

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

參考文獻

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

[2] 陳空，宋春雷，陳家斌，等.基于改進WKNN的位置指紋室內定位算法[J].導航定位與授時，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聚類算法的改進與應用[J].電子技術應用，2015，41(1)：125-128.

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

[8] 王艷麗，楊如民，余成波，等.相關性匹配藍牙信標位置指紋庫的室內定位[J].電訊技術，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相關系數的指紋定位技術方法[J].廣東通信技術，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準則的最近鄰聚類模型的優化算法[J].系統工程與電子技術，2005，27(2)：257-259.

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