0 引言

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

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

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

1 K-means指紋定位

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

1.1 K-means聚類

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

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

    K-means算法流程：

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

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

For  i=1:k

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

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

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

       If Jc最小,，即算法收斂

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

       End

End

1.2 匹配算法

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

1.2.1 最鄰近法

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

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

1.2.2 K鄰近法

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

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

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

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

    在定位范圍內(nèi),，假設(shè)A,、B兩個(gè)待測(cè)點(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個(gè)指紋中第i個(gè)的坐標(biāo)值,。

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

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

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

2.2 兩步聚類

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

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

    首先,，將某一個(gè)觀測(cè)值置于根節(jié)點(diǎn)處并記錄相關(guān)變量信息,，根據(jù)給定的距離公式作為相似性依據(jù)，依次判斷其他測(cè)量值與已有節(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ù)輸入,，使用分層聚類對(duì)其進(jìn)行再聚類不斷合并修剪預(yù)聚類結(jié)果，通過(guò)AIC準(zhǔn)則評(píng)估現(xiàn)有分類的質(zhì)量,，最終給出符合準(zhǔn)則的分類方案,。

2.3 優(yōu)化算法

    K-means隨機(jī)選取聚類個(gè)數(shù)與聚類中心帶來(lái)極大的不穩(wěn)定性，對(duì)此使用兩步聚類算法選擇最優(yōu)聚類數(shù)并對(duì)其分類,。文獻(xiàn)[10]分析實(shí)驗(yàn)數(shù)據(jù)發(fā)現(xiàn)：RSSI相關(guān)系數(shù)匹配法比NN匹配定位精度高,，但是實(shí)時(shí)性差。為提高定位精度,、增強(qiáng)算法實(shí)時(shí)性,，本文使用相關(guān)系數(shù)法選取子指紋庫(kù)，使用KNN算法估計(jì)待測(cè)點(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個(gè)AP。經(jīng)測(cè)試發(fā)現(xiàn),，采集的RSSI數(shù)據(jù)在1 m范圍內(nèi)波動(dòng)較小,，由此可將定位區(qū)域劃分為1 m×1 m的小區(qū)域，并在每個(gè)區(qū)域頂點(diǎn)采集數(shù)據(jù),，為消除方向引起的誤差,，在每個(gè)RP不同方向進(jìn)行采樣。受物體擺放情況的影響,，最終共采集438組數(shù)據(jù),。根據(jù)移動(dòng)路徑(圖4中路徑)，采集107組數(shù)據(jù),。

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

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

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

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

    本文主要考證所提算法在定位精度與實(shí)時(shí)性方面有改善效果,，因而選用定位效果較好的參數(shù)進(jìn)行分析,。即聚類個(gè)數(shù)為9，利用NN算法計(jì)算絕對(duì)距離判斷所屬子指紋庫(kù),，使用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)算時(shí)間縮短了37.84%~46.32%,，即聚類處理后可顯著提高定位的實(shí)時(shí)性。(2)確定聚類數(shù)目后,，不論是用K-means還是兩步聚類對(duì)數(shù)據(jù)進(jìn)行聚類處理,，最終的定位精度與實(shí)時(shí)性都相差無(wú)幾，即聚類需預(yù)先得知最優(yōu)的聚類個(gè)數(shù),。(3)所提算法與K-means指紋定位相比：雖然運(yùn)算時(shí)間略有增加,，但定位精度方面有小幅改善；且K-means指紋定位隨機(jī)性大,、穩(wěn)定型差,，而所提算法使用兩步聚類依據(jù)AIC準(zhǔn)則擇優(yōu)得到聚類數(shù)目，極大提高了算法的穩(wěn)定性,。綜上述,，本文所提算法相比當(dāng)前已有算法在定位精度、實(shí)時(shí)性和穩(wěn)定性方面都有一定的改善效果,。

4 總結(jié)

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