趙 芳

(新鄉(xiāng)學(xué)院 計(jì)算機(jī)與信息工程學(xué)院， 河南 新鄉(xiāng) 453003)

人們對(duì)無線通信的需求隨著網(wǎng)絡(luò)科技的飛速進(jìn)步呈現(xiàn)出多樣化特征，而位置服務(wù)[1-3]就是這些需求中最為關(guān)鍵的一項(xiàng)，然而位置服務(wù)會(huì)受到無線定位技術(shù)的限制.無線定位技術(shù)以地理位置為前提能夠進(jìn)行室內(nèi)和室外定位[4-5].通常情況下能夠經(jīng)過北斗和GPS等衛(wèi)星導(dǎo)航系統(tǒng)加以A-GPS輔助完成室外定位，且具有定位精度良好且效率高等特點(diǎn).然而衛(wèi)星信號(hào)穿透能力非常微弱，與此同時(shí)建筑物的墻壁也會(huì)對(duì)其產(chǎn)生阻撓作用，這在很大程度上使得衛(wèi)星信號(hào)不能為室內(nèi)設(shè)備提供定位服務(wù).另外室內(nèi)無線信號(hào)環(huán)境又非常繁雜，建筑物墻體和房間布局等很多因素都能致使無線信號(hào)產(chǎn)生多徑效應(yīng).

隨著智能手機(jī)等內(nèi)部配置無線接入儀器的迅速發(fā)展，Wi-Fi信號(hào)已運(yùn)用至大部分室內(nèi)環(huán)境，同時(shí)以Wi-Fi技術(shù)為基礎(chǔ)的位置指紋定位可以利用無線接入點(diǎn)在建筑內(nèi)相異坐標(biāo)的信號(hào)強(qiáng)度值，構(gòu)建位置坐標(biāo)和離線信號(hào)強(qiáng)度的指紋數(shù)據(jù)庫，并將其作為在線定位的基礎(chǔ)[6-7].通常情況下此方式的定位精度和效率會(huì)受到離線指紋數(shù)據(jù)庫的有效性和位置相互匹配算法擾動(dòng)的影響，因而本文提出了一種基于Wi-Fi指紋離散程度的WKNN定位算法(DD-WKNN算法).

1 離線位置指紋數(shù)據(jù)聚類

1.1 構(gòu)建初始位置指紋數(shù)據(jù)庫

設(shè)構(gòu)建某個(gè)定位區(qū)域離線位置指紋數(shù)據(jù)庫需有D個(gè)指紋信息采集點(diǎn)數(shù)據(jù)，同時(shí)其二維空間位置坐標(biāo)為L(zhǎng)i=(xi，yi)，i=1，2，…，D.各采樣點(diǎn)可得到N個(gè)無線接入點(diǎn)的信號(hào)強(qiáng)度值，即

Ri=(ri1，ri2，…，riN)

(1)

各組指紋信息的數(shù)據(jù)結(jié)構(gòu)可以表示為

Fi=(Li，Ri)=(xi，yi，ri1，ri2，…，riN)

(2)

將采樣獲得的數(shù)據(jù)運(yùn)用行方式完成保存，進(jìn)而獲得其所有離線位置的數(shù)據(jù)庫，即

(3)

式中，xD和yD分別為D指紋信息采集點(diǎn)的橫坐標(biāo)和縱坐標(biāo).

1.2 基于K-means算法的數(shù)據(jù)聚類

第一步：從D個(gè)指紋信息中隨意擇取K個(gè)指紋作為初始聚類中心集合C，且C=(C1，C2，…，CK)，Ci的數(shù)值與隨意擇取的位置指紋數(shù)據(jù)Ri(i=1，2，…，K)相等，即

C=(R1，R2，…，RK)

(4)

第二步：運(yùn)算剩余的D-K個(gè)指紋和C中每個(gè)聚類中心Ci的歐氏距離，從而獲得與此指紋相對(duì)最為逼近的聚類中心Ci，隨之將其歸至此聚類中，進(jìn)而獲得包括D個(gè)指紋信息的K個(gè)聚類，將各聚類中指紋信息個(gè)數(shù)定義為nCi(i=1，2，…，K).

第三步：重新運(yùn)算K個(gè)聚類各自的聚類中心，隨后用其替換原有的聚類中心，即

(5)

式中，Rm為第i個(gè)聚類中第m個(gè)位置的指紋數(shù)據(jù).

第四步：以此循環(huán)往復(fù)第二、第三步直至運(yùn)算獲得的聚類中心值等于上個(gè)步驟的數(shù)值，換言之就是其收斂至極值，進(jìn)而獲得最終離線位置指紋信息聚類[8-9].

2 DD-WKNN位置指紋定位算法

在基于參考位置指紋離散程度的WKNN定位算法中，需要在上述所得數(shù)據(jù)內(nèi)擇取和在線實(shí)測(cè)RSSI值歐氏距離相對(duì)最為逼近的指紋數(shù)據(jù)，然后依照其離散程度設(shè)置位置估算參考權(quán)重的權(quán)值，令k個(gè)位置指紋的變異系數(shù)代表離散程度，隨之完成歸一化加權(quán)求和，其具體算法流程如下：

1) 在待定位位置實(shí)測(cè)各Wi-Fi無線接入點(diǎn)的RSSI采樣值，記為RL，其表達(dá)式為

RL=(rL1，rL2，…，rLn)

(6)

式中，rLn為第n個(gè)Wi-Fi無線接入點(diǎn)在此待定位位置的信號(hào)強(qiáng)度RSSI采集值.

2) 依照RSSI采集值搜索與之對(duì)應(yīng)的離線位置指紋數(shù)據(jù)庫，利用式(7)擇取k個(gè)和RSSI采樣值歐氏距離最小的離線位置指紋數(shù)據(jù)庫Fk，即

(7)

(8)

(9)

(10)

(11)

4) 將vi歸一化后轉(zhuǎn)化為權(quán)重系數(shù)wi，且二者關(guān)系為

(12)

5) 依照獲得的權(quán)重系數(shù)完成對(duì)每個(gè)參考點(diǎn)的加權(quán)求和運(yùn)算以估算其位置坐標(biāo)，即

(13)

DD-WKNN算法具體實(shí)現(xiàn)流程如圖1所示.

圖1 DD-WKNN算法流程圖

3 結(jié)果分析

擇取實(shí)驗(yàn)地點(diǎn)為某大學(xué)能夠感知多個(gè)Wi-Fi無線接入點(diǎn)RSSI值的辦公區(qū)樓道，其Wi-Fi型號(hào)為AP6476，然后擇取一塊20 m×2 m的條形區(qū)域，此樓道區(qū)間能夠同時(shí)得到大于等于8個(gè)未知位置傳輸出來的接入點(diǎn)信號(hào)，同時(shí)可測(cè)得其RSSI值.擇取(0 m，1 m)～(20 m，1 m)作為待定位位置實(shí)際坐標(biāo)區(qū)間，按照1 m間隔距離設(shè)定17個(gè)待定位位置，每間隔3 s完成一次各接入點(diǎn)信號(hào)的RSSI采樣值記錄，1 min后運(yùn)算其平均值作為最終RSSI采樣值.待定位位置具體布置如圖2所示.

由于存在于所選區(qū)間房間內(nèi)的Wi-Fi型號(hào)相同，同時(shí)每個(gè)房間都包含書桌、電腦和書柜等很多物體，且各房間門均為防盜門，因而所選區(qū)域Wi-Fi無線接入點(diǎn)的RSSI值可以認(rèn)為是均勻分布的.在此區(qū)域內(nèi)利用智能手機(jī)裝置Wi-Fi檢視儀獲取周圍Wi-Fi無線接入點(diǎn)的RSSI值[10].離線位置指紋數(shù)據(jù)的采樣點(diǎn)擇取樓道兩邊房間門所處的兩條直線上，在(0 m，0 m)～(20 m，0 m)和(0 m，2 m)～(20 m，2 m)坐標(biāo)范圍內(nèi)，每間隔1.5 m設(shè)定一個(gè)待測(cè)位置，且待定位位置總數(shù)為28，完成對(duì)8個(gè)Wi-Fi無線接入點(diǎn)RSSI值的采集后，取其平均值保存至指紋數(shù)據(jù)庫，設(shè)K-means算法的聚類數(shù)目為3，最終獲得的數(shù)據(jù)如表1所示.

圖2 待定位位置布置

表1 指紋數(shù)據(jù)庫中的采樣點(diǎn)位置數(shù)據(jù)

為了檢驗(yàn)從各位置采集到的Wi-Fi無線接入點(diǎn)數(shù)目對(duì)算法定位誤差的擾動(dòng)程度，從Wi-Fi無線接入點(diǎn)中擇取4～8個(gè)點(diǎn)與最近鄰NN算法進(jìn)行對(duì)比分析，兩種算法的定位誤差分布如圖3所示.

圖3 無線接入點(diǎn)數(shù)目的擾動(dòng)箱線圖

由圖3可見，當(dāng)參考Wi-Fi無線接入點(diǎn)數(shù)目從4擴(kuò)增至8時(shí)，最近鄰NN算法[11]定位誤差中值約從3.4 m縮減至3 m以下，而DD-WKNN算法則約從2.5 m縮減至0.5 m，可見，參考Wi-Fi無線接入點(diǎn)數(shù)目對(duì)位置指紋定位具有一定擾動(dòng)，同時(shí)表現(xiàn)出正相關(guān)關(guān)系，即隨著Wi-Fi無線接入點(diǎn)數(shù)目的不斷擴(kuò)大，最近鄰NN算法和DD-WKNN算法的定位精度都有所改善.另外，在擇取一致的Wi-Fi無線接入點(diǎn)數(shù)目情況下，DD-WKNN算法定位精度高于NN算法，同時(shí)其誤差波動(dòng)情況相對(duì)更小.

將本文算法、最近鄰NN算法和基于歐氏距離的傳統(tǒng)WKNN算法進(jìn)行定位精度對(duì)比分析.分別在實(shí)驗(yàn)區(qū)域的(0 m，0.5 m)～(20 m，0.5 m)和(0 m，1.5 m)～(20 m，1.5 m)坐標(biāo)范圍內(nèi)每距離1 m完成對(duì)待定位位置的RSSI值采集，且待定位位置總數(shù)為42.各采樣點(diǎn)每間隔1 min完成對(duì)各無線接入點(diǎn)RSSI值的10次采樣，同時(shí)擇取其平均值作為實(shí)際測(cè)量值，分別運(yùn)用三種算法完成對(duì)待定位位置坐標(biāo)的估算，各算法的誤差累積概率分布如圖4所示.

圖4 三種算法的實(shí)測(cè)性能對(duì)比

由圖4可知，最近鄰NN算法定位誤差具有較高的數(shù)值，誤差累積函數(shù)收斂速度相對(duì)最為緩慢，同時(shí)還具有相對(duì)較高的最大誤差值.基于歐氏距離的傳統(tǒng)WKNN算法的定位精度相比NN算法具有較大的優(yōu)勢(shì)，其最大誤差值約為2.5 m.DD-WKNN算法的定位精度表現(xiàn)更加良好，其誤差累積函數(shù)具有很快的收斂速度，同時(shí)其最大定位誤差值約為1.6 m.綜上所述，DD-WKNN算法在很大程度上提高了定位精度，同時(shí)具有相對(duì)更小的誤差波動(dòng)區(qū)間.

4 結(jié) 論

DD-WKNN算法將k個(gè)和待定位位置實(shí)際測(cè)量RSSI值歐氏距離相對(duì)最為逼近的指紋數(shù)據(jù)作為位置估計(jì)參照點(diǎn)，同時(shí)以其離散度作為權(quán)重系數(shù)的基礎(chǔ)，對(duì)k個(gè)位置指紋數(shù)據(jù)進(jìn)行加權(quán)求和運(yùn)算以完成位置估計(jì).依照位置指紋離散度權(quán)重信息將離散度相對(duì)較小的位置指紋數(shù)據(jù)賦予相對(duì)較高的權(quán)重，這能夠在很大程度上防止Wi-Fi無線接入點(diǎn)由于室內(nèi)布局導(dǎo)致RSSI值出現(xiàn)較大改變而引發(fā)的定位誤差問題.實(shí)驗(yàn)分析結(jié)果表明：DD-WKNN算法的定位精度高于以歐氏距離作為權(quán)重系數(shù)的傳統(tǒng)WKNN算法和最近鄰NN算法，且DD-WKNN算法具有更小的誤差波動(dòng).