0 引言

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

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

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

1 K-means指紋定位

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

1.1 K-means聚類

    指紋庫中第i個參考點(diǎn)(Reference Point，RP)接收到接入點(diǎn)(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]，隨機(jī)選用k個向量作為初始聚類中心，以歐氏距離作為相似度準(zhǔn)則就近分配指紋數(shù)據(jù)，不斷迭代更新聚類中心，直至算法收斂或達(dá)到最大迭代次數(shù)。當(dāng)總的類間離散度最小時認(rèn)為算法收斂，即：

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

    K-means算法流程：

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

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

For  i=1:k

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

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

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

       If Jc最小，即算法收斂

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

       End

End

1.2 匹配算法

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

1.2.1 最鄰近法

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

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

1.2.2 K鄰近法

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

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

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

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

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

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

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

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

2.1 AIC準(zhǔn)則

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

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

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

2.2 兩步聚類

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

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

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

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

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

2.3 優(yōu)化算法

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

3 實(shí)驗(yàn)布置與結(jié)果分析

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

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

3.2 實(shí)驗(yàn)分析

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

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

    SPSS軟件操作便捷、功能強(qiáng)大、運(yùn)算速度快，直接使用該軟件對指紋庫RSSI進(jìn)行兩步聚類分析，根據(jù)AIC準(zhǔn)則自動得到最優(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)顯示分類后每個類別的具體坐標(biāo)值：同一位置的多個數(shù)據(jù)可能劃分到不同類別，也驗(yàn)證了同一位置需在多個方向采集數(shù)據(jù)。

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

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

4 總結(jié)

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

參考文獻(xiàn)

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

[2] 陳空，宋春雷，陳家斌，等.基于改進(jìn)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聚類算法的改進(jìn)與應(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)性匹配藍(lán)牙信標(biāo)位置指紋庫的室內(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準(zhǔn)則的最近鄰聚類模型的優(yōu)化算法[J].系統(tǒng)工程與電子技術(shù)，2005，27(2)：257-259.

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