董世鵬，吳韶波

（北京信息科技大學(xué) 信息與通信學(xué)院，北京 100101）

0 引 言

基于WiFi的指紋定位由于具有低成本、易部署、非視距等優(yōu)點(diǎn)，已成為室內(nèi)定位領(lǐng)域研究的熱點(diǎn)[1]。目前典型的WiFi指紋匹配算法是K近鄰（KNearest Neighbor, KNN）算法及其改進(jìn)算法，通過比較待測點(diǎn)與指紋庫中參考點(diǎn)指紋強(qiáng)度距離，推算出待測點(diǎn)位置。但在室內(nèi)環(huán)境中受多徑及障礙物遮擋等因素影響，WiFi信號強(qiáng)度存在波動，導(dǎo)致單純基于信號強(qiáng)度的定位算法將錯誤參考點(diǎn)歸入近鄰點(diǎn)中，增加定位誤差[2]。

文獻(xiàn)[3]在離線階段根據(jù)參考點(diǎn)空間位置進(jìn)行聚類，在線匹配時在同一類簇參考點(diǎn)中選擇近鄰點(diǎn)，避免將偏離空間中心的參考點(diǎn)加入到近鄰點(diǎn)，但離線階段和在線階段聚類標(biāo)準(zhǔn)的不同無法保證在線聚類匹配的準(zhǔn)確性。文獻(xiàn)[4]采用改進(jìn)的組合加權(quán)指紋定位算法，剔除偏離幾何中心的近鄰點(diǎn)，將滿足條件的近鄰點(diǎn)結(jié)合實(shí)際位置與歐氏距離進(jìn)行加權(quán)，沒有考慮不同歐氏距離下近鄰點(diǎn)定位可靠性，使估算出的幾何中心與測試點(diǎn)實(shí)際位置的距離較遠(yuǎn)。

由于基于K近鄰的定位算法需要計(jì)算測試點(diǎn)與指紋庫中所有參考點(diǎn)的距離，當(dāng)指紋庫中參考點(diǎn)數(shù)量過多時，難以保證定位實(shí)時性。因此，通常需要對指紋進(jìn)行聚類，減少在線定位階段需要計(jì)算的參考指紋數(shù)量，提高定位效率。文獻(xiàn)[5]中提出基于FCM聚類及KNN算法的指紋定位方法，文獻(xiàn)[6]中提出一種基于親和力傳播聚類的定位方法，文獻(xiàn)[7]利用層次聚類對指紋庫進(jìn)行劃分，均有效地降低了計(jì)算復(fù)雜度。但以上方法都沒有考慮到聚類邊緣處參考點(diǎn)選取問題。文獻(xiàn)[8]在二分K-means聚類的基礎(chǔ)上，根據(jù)聚類中心與樣本點(diǎn)歐氏距離閾值選擇類簇，將滿足條件類簇的所有指紋數(shù)據(jù)添加到參考點(diǎn)中，提高聚類邊緣處定位精度，但會引入過多指紋。文獻(xiàn)[9]中對數(shù)據(jù)在不同聚類的隸屬度差值進(jìn)行劃分，但不適合樣本位于多個聚類邊緣處的情況。

針對以上問題，本文提出了一種結(jié)合改進(jìn)FCM聚類與動態(tài)K值定位的改進(jìn)算法。離線階段在傳統(tǒng)FCM聚類的基礎(chǔ)上，將隸屬度大于閾值的參考指紋添加到對應(yīng)類中，降低聚類邊緣處指紋數(shù)據(jù)不足引起的誤差。結(jié)合指紋強(qiáng)度信息與近鄰點(diǎn)空間位置，剔除距離預(yù)測中心點(diǎn)較遠(yuǎn)的近鄰點(diǎn)，并根據(jù)WKNN算法得出定位結(jié)果。

1 WiFi指紋定位算法

WiFi指紋定位可以分為離線指紋庫構(gòu)建和在線定位兩個階段。離線指紋庫構(gòu)建階段，采集并保存在各參考點(diǎn)采集到的指紋信息；在線定位階段，根據(jù)離線指紋庫及測試點(diǎn)采集到的指紋信息推算測試點(diǎn)位置。

1.1 離線指紋庫構(gòu)建

在待定位區(qū)域按照一定間隔設(shè)置參考點(diǎn)，并建立相應(yīng)坐標(biāo)系。記錄每一個參考點(diǎn)處采集到的指紋信息強(qiáng)度及對應(yīng)坐標(biāo)，并保存到指紋庫FP中，如下式：

其中：（xi,yi）表示第i個參考點(diǎn)的坐標(biāo)；Rij表示在第i個參考點(diǎn)接收到的第j個AP的指紋強(qiáng)度。

1.2 在線定位匹配

由于KNN算法[10]及WKNN算法[11]都是選取固定K個近鄰點(diǎn)，在判定近鄰點(diǎn)時容易引入信號距離較遠(yuǎn)的點(diǎn)，導(dǎo)致定位精度降低。EWKNN算法[12]通過設(shè)定指紋強(qiáng)度距離閾值確定定位時的近鄰點(diǎn)及K值，有效避免了相似度較小近鄰點(diǎn)的引入，提高了定位精度。故在線定位階段本文選擇在傳統(tǒng)EWKNN算法的基礎(chǔ)上進(jìn)行改進(jìn)，通過結(jié)合指紋強(qiáng)度距離與空間距離對近鄰點(diǎn)進(jìn)行二次篩選，進(jìn)一步提高定位精度。

2 FCM聚類算法及改進(jìn)

2.1 FCM算法原理

FCM聚類算法是一種模糊理論與HCM算法結(jié)合的軟聚類算法，使用[0，1]之間的隸屬度來表示數(shù)據(jù)屬于某個類的概率，并且樣本對于所有類簇的隸屬度之和為1。樣本在類簇中具有越高隸屬度，則屬于該類的可能越大，并將隸屬度最高的類作為樣本所屬聚類[13]。

FCM算法中代價函數(shù)定義為：

其中：J為代價函數(shù)；N為數(shù)據(jù)個數(shù)；c為聚類個數(shù)；uij為第i個數(shù)據(jù)對于第j個聚類的隸屬度；m為權(quán)重系數(shù)；||xi-cj||2為數(shù)據(jù)xi到聚類中心cj的距離。

通過拉格朗日公式對代價函數(shù)求導(dǎo)，最終可以得到聚類中心點(diǎn)和隸屬度的迭代公式分別為：

2.2 FCM算法步驟

FCM聚類算法的基本流程如圖1所示。

離子液體是由離子組成的有機(jī)鹽化合物，在室溫下多為流動狀態(tài)的液體，對纖維素等聚合物具有良好的溶解性能。在纖維素向5-HMF的催化轉(zhuǎn)化過程中，離子液體被廣泛采用[12]。

圖1 FCM聚類流程

2.3 基于隸屬度最小值的聚類劃分

當(dāng)測試樣本在指紋聚類邊緣處時，近鄰點(diǎn)可能被劃分到不同聚類中，使聚類邊緣處的測試樣本無法獲得足夠參考點(diǎn)造成定位精度降低。由于在FCM算法中聚類邊緣處的樣本對于相鄰類別都有較高隸屬度，故在FCM聚類算法中加入最小隸屬度閾值對指紋數(shù)據(jù)進(jìn)行劃分。

在傳統(tǒng)FCM聚類中加入最小隸屬度閾值m，當(dāng)樣本i在該類簇中隸屬度值最大或隸屬度大于固定閾值m時，將樣本i加入到該類中，使在多個類簇中有較高隸屬度的樣本可以劃分到不同聚類。

3 結(jié)合模糊聚類的動態(tài)K值定位

為解決WiFi指紋定位中聚類邊緣處參考點(diǎn)不足造成定位精度降低及部分近鄰點(diǎn)偏離空間中心導(dǎo)致的定位精度下降的問題，提出了一種結(jié)合最小隸屬度的FCM聚類和動態(tài)K值的定位算法。算法的整體流程如圖2所示。

圖2 改進(jìn)算法流程

針對傳統(tǒng)指紋定位算法進(jìn)行在線定位時部分近鄰點(diǎn)偏離空間中心較遠(yuǎn)導(dǎo)致定位精度降低問題，提出一種基于歐氏距離和近鄰點(diǎn)之間空間距離的K值確定方法，對近鄰點(diǎn)進(jìn)行二次篩選。具體算法步驟如下：

（1）將設(shè)備從周圍接入點(diǎn)收集到的信號強(qiáng)度序列與指紋數(shù)據(jù)庫中的指紋序列進(jìn)行計(jì)算，得到測試點(diǎn)信號強(qiáng)度與所有參考指紋序列的距離為：

其中：Aj為第j個AP的RSSI；Ri,j為第i個參考點(diǎn)處第j個AP的RSSI；M為指紋庫中參考點(diǎn)個數(shù)；N為指紋庫中AP個數(shù)。

（2）將Di按照升序排列，即Di中最小值為D1，最大值為DL，設(shè)定閾值D，將序列中大于D的點(diǎn)篩除，得到G個參考點(diǎn)。用Sg表示D1和Dg之間的差（g=2, 3,...,G）。計(jì)算Sg的平均值為：

篩除Sg大于E(S)的參考點(diǎn)，并將剩余參考點(diǎn)數(shù)目設(shè)置為K，按照升序排列為[D1,D2,...,DK]，作為待篩選近鄰點(diǎn)。

（3）定義初始中心坐標(biāo)為（xcen,ycen），且有：

（4）計(jì)算坐標(biāo)D1(x1,y1)與中心點(diǎn)坐標(biāo)（xcen,ycen）距離，若小于閾值L則將中心坐標(biāo)更新為（x1,y1），否則剔除近鄰點(diǎn)D1并對近鄰點(diǎn)D2進(jìn)行判斷。若滿足閾值要求，將中心坐標(biāo)更新為（x2,y2）并執(zhí)行步驟（6），若不滿足則執(zhí)行步驟（5）。

（5）計(jì)算D1與D2坐標(biāo)均值（x12,y12）與中心點(diǎn)坐標(biāo)（xcen,ycen）距離，若小于閾值L則將中心坐標(biāo)更新為（x12,y12）。

（6）計(jì)算下一個近鄰點(diǎn)與中心坐標(biāo)距離：

（7）若l＜L，則將近鄰點(diǎn)Di添加到指紋序列d中，并更新中心點(diǎn)坐標(biāo)為：

其中：k為滿足閾值條件的近鄰點(diǎn)個數(shù)；xj和yj為指紋序列d中的近鄰點(diǎn)。

（8）重復(fù)步驟（6）和步驟（7），判斷其余近鄰點(diǎn)。

（9）對滿足條件的近鄰點(diǎn)序列[d1,d2,...,dk]，通過WKNN算法估計(jì)測試樣本位置（xcen,ycen）。

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

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

實(shí)驗(yàn)設(shè)置在學(xué)院教學(xué)樓6樓走廊進(jìn)行，實(shí)驗(yàn)場地為50 m×2 m的長方形區(qū)域，以1 m×1 m采樣間隔構(gòu)建離線指紋庫。使用紅米Note7手機(jī)進(jìn)行WiFi信號采集，并使用MATLAB2016a軟件對算法有效性進(jìn)行驗(yàn)證。實(shí)驗(yàn)環(huán)境如圖3所示。

圖3 實(shí)驗(yàn)區(qū)域平面

離線階段：使用自主開發(fā)的WiFi信息采集APP在每個參考點(diǎn)處采集WiFi指紋信息，共采集100個參考點(diǎn)，每個參考點(diǎn)采集RSSI信號數(shù)據(jù)30次，將數(shù)據(jù)進(jìn)行高斯均值濾波后存儲到指紋數(shù)據(jù)庫中。

在線階段：在實(shí)驗(yàn)區(qū)域內(nèi)隨機(jī)選擇60個測試點(diǎn)，每個測試點(diǎn)采集RSSI信號10次，將經(jīng)過均值濾波處理后的數(shù)據(jù)存儲為測試樣本。

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

為驗(yàn)證本文提出的動態(tài)K值定位算法，分別使用基于傳統(tǒng)FCM聚類的WKNN算法、EWKNN算法和本文提出的動態(tài)K值算法對測試點(diǎn)進(jìn)行位置估計(jì)，其中改進(jìn)定位算法閾值L設(shè)定為3，定位結(jié)果如圖4及表1所示。基于傳統(tǒng)FCM聚類的動態(tài)K值算法平均誤差為1.25 m，達(dá)到累計(jì)概率80%時的誤差為2.06 m，均低于EWKNN和WKNN算法，其中平均定位誤差分別降低12%和24%。

圖4 三種算法定位誤差

表1 三種算法定位誤差對比

對于聚類邊緣處缺少近鄰點(diǎn)導(dǎo)致的定位精度下降問題，選取不同的m值進(jìn)行多次實(shí)驗(yàn)，發(fā)現(xiàn)當(dāng)m取0.1時基于最小隸屬度的FCM聚類效果最好。故取隸屬度最小閾值m為0.1，并對基于傳統(tǒng)FCM的改進(jìn)EWKNN算法及本文所提算法進(jìn)行位置估計(jì)，實(shí)驗(yàn)結(jié)果如圖5及表2所示。與基于傳統(tǒng)FCM聚類的動態(tài)K值定位方法比較，本文改進(jìn)算法定位平均誤差及達(dá)到相同累計(jì)概率的定位誤差均有所降低，分別減少了5%和3%。

圖5 聚類效果比較

表2 聚類效果比較

將本文改進(jìn)算法與基于傳統(tǒng)FCM聚類的WKNN算法及EWKNN算法進(jìn)行對比，平均定位誤差分別降低27%和16%，累計(jì)概率達(dá)到80%時的定位誤差分別降低26%和15%，提高了定位精度。

5 結(jié) 語

針對傳統(tǒng)指紋定位中近鄰點(diǎn)選擇及聚類邊緣處精度下降問題，本文提出了一種結(jié)合最小閾值聚類與動態(tài)K值的指紋定位算法。在離線階段，根據(jù)最小隸屬度閾值對樣本進(jìn)行聚類，將傳統(tǒng)聚類邊緣點(diǎn)處的樣本點(diǎn)劃分到多個類別中，降低聚類邊緣處因缺少參考點(diǎn)而導(dǎo)致的定位誤差。針對在線階段，提出了一種結(jié)合指紋強(qiáng)度與參考點(diǎn)位置的動態(tài)加權(quán)K近鄰算法，對具有較低指紋序列相似度及偏離空間中心的近鄰點(diǎn)進(jìn)行剔除，有效提高了定位精度。實(shí)驗(yàn)結(jié)果表明，本文提出的改進(jìn)算法雖然在一定程度增加了計(jì)算復(fù)雜度，但相較傳統(tǒng)算法定位精度有了較大提升，驗(yàn)證了算法的有效性。