WiFi指紋定位中改進(jìn)的加權(quán)k近鄰算法

王博遠(yuǎn)，劉學(xué)林，蔚保國(guó)，賈瑞才，甘興利，黃 璐

(1.哈爾濱工程大學(xué) 信息與通信工程學(xué)院，黑龍江 哈爾濱 150001；2.中國(guó)電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081；3.衛(wèi)星導(dǎo)航系統(tǒng)與裝備技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，河北 石家莊 050081)

由于室內(nèi)環(huán)境中衛(wèi)星導(dǎo)航信號(hào)的可用性無(wú)法得到保證，全球?qū)Ш叫l(wèi)星系統(tǒng)在室內(nèi)定位領(lǐng)域的應(yīng)用受到限制[1]，因此建立一套準(zhǔn)確可靠的室內(nèi)定位系統(tǒng)以滿足室內(nèi)位置服務(wù)的需求非常重要。隨著智能手機(jī)的快速發(fā)展，WiFi信號(hào)接收模塊已內(nèi)置于智能手機(jī)中，同時(shí)在一些公共場(chǎng)所，如辦公樓、車(chē)站、商場(chǎng)等，無(wú)線局域網(wǎng)也已經(jīng)實(shí)現(xiàn)了廣泛的覆蓋，WiFi信號(hào)指紋定位已成為目前最流行的室內(nèi)定位方案之一。WiFi指紋定位可大體分為離線階段和在線階段。在離線階段，工作人員在實(shí)際場(chǎng)地采集WiFi指紋，包括每個(gè)參考點(diǎn)的位置坐標(biāo)及每個(gè)參考點(diǎn)處的接收信號(hào)強(qiáng)度值。每一對(duì)接收信號(hào)強(qiáng)度值和位置坐標(biāo)確定了一個(gè)獨(dú)一無(wú)二的參考點(diǎn)，并按照一定的數(shù)據(jù)格式存入指紋數(shù)據(jù)庫(kù)中[2]。在在線階段，用戶在接收端獲得當(dāng)前位置的信號(hào)強(qiáng)度，通過(guò)搜索指紋庫(kù)找到與信號(hào)強(qiáng)度讀數(shù)最匹配的幾個(gè)參考點(diǎn)，將匹配到的參考點(diǎn)坐標(biāo)進(jìn)行平均或者加權(quán)平均，估計(jì)出用戶當(dāng)前的位置坐標(biāo)。

現(xiàn)存的WiFi指紋定位方法大都采用確定性方法，包括最近鄰算法，k近鄰算法和加權(quán)k近鄰算法。微軟公司設(shè)計(jì)的RADAR系統(tǒng)[3]是較早使用WiFi指紋定位的室內(nèi)定位系統(tǒng)，其利用k近鄰算法使得系統(tǒng)可以滿足房間級(jí)別的定位精度。為了提高WiFi指紋定位系統(tǒng)的定位精度和系統(tǒng)穩(wěn)定性，研究人員提出了許多WiFi指紋定位算法。文獻(xiàn)[4]針對(duì)定位系統(tǒng)因多路徑效應(yīng)等因素所導(dǎo)致定位精度降低的問(wèn)題，提出了一種基于到達(dá)時(shí)差的混合定位算法。文獻(xiàn)[5]根據(jù)位置距離使用相似性傳播聚類(lèi)對(duì)最近鄰參考點(diǎn)進(jìn)行聚類(lèi)。通過(guò)比較聚類(lèi)中心和在線接收信號(hào)強(qiáng)度讀數(shù)之間的信號(hào)距離以及參考點(diǎn)的數(shù)目，保留可能性最大的參考點(diǎn)類(lèi)別，然后使用加權(quán)k近鄰算法估計(jì)用戶位置。文獻(xiàn)[6]通過(guò)對(duì)室內(nèi)環(huán)境的分析，利用信號(hào)傳播損耗模型建立了似然函數(shù)模型，運(yùn)用馬爾可夫蒙特卡羅算法對(duì)似然函數(shù)中的位置坐標(biāo)進(jìn)行了估計(jì)，具有快速收斂和高精度的優(yōu)勢(shì)。文獻(xiàn)[7]采用k均值算法把在每個(gè)參考點(diǎn)處來(lái)自每個(gè)無(wú)線接入點(diǎn)的一組信號(hào)作為一個(gè)類(lèi)進(jìn)行計(jì)算，將不屬于該類(lèi)的數(shù)據(jù)剔除掉，從而提高了WiFi指紋數(shù)據(jù)庫(kù)的質(zhì)量。文獻(xiàn)[8]指出在WiFi指紋定位中小的接收信號(hào)強(qiáng)度值具有和大的接收信號(hào)強(qiáng)度值同等的意義，以用來(lái)表示與無(wú)線接入點(diǎn)距離的不同，因此不應(yīng)該簡(jiǎn)單地將數(shù)值小的接收信號(hào)強(qiáng)度舍掉。文獻(xiàn)[9]設(shè)計(jì)了3種不同加權(quán)距離的k近鄰算法，發(fā)現(xiàn)基于曼哈頓距離的k近鄰算法性能最好。文獻(xiàn)[10]通過(guò)實(shí)驗(yàn)證明，傳統(tǒng)的加權(quán)k近鄰算法將參考點(diǎn)接收信號(hào)強(qiáng)度與測(cè)試點(diǎn)接收信號(hào)強(qiáng)度差值的倒數(shù)作為參考點(diǎn)的權(quán)值進(jìn)行加權(quán)平均，這并不符合WiFi信號(hào)具有不均勻空間分辨率的特性，因而降低了定位精度。根據(jù)上述提到的方法可知，現(xiàn)存的基于最近鄰機(jī)制的定位方法大都利用不同點(diǎn)間的信號(hào)距離來(lái)判斷相互之間的物理距離，并將其作為指紋匹配和位置估計(jì)的依據(jù)。然而，由于室內(nèi)環(huán)境會(huì)受到反射、折射以及多徑效應(yīng)的影響，WiFi信號(hào)具有很強(qiáng)的波動(dòng)性，這將給信號(hào)距離的計(jì)算帶來(lái)誤差。同時(shí)根據(jù)WiFi信號(hào)的損耗模型可知，接收信號(hào)強(qiáng)度的變化值與傳播距離呈對(duì)數(shù)關(guān)系，即兩者的關(guān)系是非線性的[11]。因此，為了解決WiFi指紋定位系統(tǒng)中由于WiFi信號(hào)的波動(dòng)性和衰減特性導(dǎo)致傳統(tǒng)的信號(hào)距離不能很好地反映物理距離的問(wèn)題，筆者提出了一種改進(jìn)的加權(quán)k近鄰算法。將WiFi信號(hào)的波動(dòng)性以及接收信號(hào)強(qiáng)度與物理距離的非線性關(guān)系引入到信號(hào)距離的計(jì)算中，給不同的信號(hào)強(qiáng)度差值分配不同的加權(quán)系數(shù)，使用信號(hào)的加權(quán)歐氏距離作為加權(quán)k近鄰算法的距離度量，提高傳統(tǒng)的加權(quán)k近鄰算法的定位精度。

1 指紋數(shù)據(jù)庫(kù)構(gòu)建

(1)

(2)

表1 指紋庫(kù)數(shù)據(jù)格式

2 改進(jìn)的WiFi指紋定位算法

根據(jù)室內(nèi)WiFi信號(hào)的波動(dòng)性、接收信號(hào)強(qiáng)度與物理距離的非線性關(guān)系，使用信號(hào)加權(quán)歐氏距離作為加權(quán)k近鄰定位算法的距離度量，提出了一種改進(jìn)的加權(quán)k近鄰算法。現(xiàn)存的加權(quán)k近鄰算法大多利用參考點(diǎn)和測(cè)試點(diǎn)之間的信號(hào)歐氏距離來(lái)判定其間的物理距離di,可表示為

(3)

(4)

(5)

經(jīng)典信號(hào)對(duì)數(shù)損耗模型[12]可表示為

PL(d)=PL(d0)-10ηlg(d/d0)+χσ,

(6)

其中，PL(d)表示距離無(wú)線接入點(diǎn)為d處的信號(hào)強(qiáng)度值；d0為參考距離，一般設(shè)為1 m；PL(d0)為參考距離處的信號(hào)強(qiáng)度值；η為路徑損耗指數(shù)；χσ代表標(biāo)準(zhǔn)差為σ的高斯隨機(jī)變量。

圖1 接收信號(hào)強(qiáng)度與物理距離的關(guān)系示意圖

理想WiFi信號(hào)環(huán)境下的信號(hào)損耗曲線如圖1所示，其中d0=1 m，PL(d0)=-31.7 dBm，路徑損耗指數(shù)η=2.76[13]。如式(3)所示，現(xiàn)存的信號(hào)歐氏距離只考慮了信號(hào)強(qiáng)度差值。然而從圖1可以看出，信號(hào)強(qiáng)度差值與物理距離關(guān)系是非線性的，隨著離無(wú)線接入點(diǎn)的距離的增加，信號(hào)衰減速度變慢，相同大小的信號(hào)強(qiáng)度差值也可以代表不同的物理距離。因此要想使信號(hào)距離更準(zhǔn)確地反映物理距離，不僅要考慮信號(hào)強(qiáng)度的差值，還要考慮每一對(duì)位置點(diǎn)信號(hào)強(qiáng)度值的總體大小。因此，文中設(shè)計(jì)了一種加權(quán)歐氏距離，通過(guò)給不同的信號(hào)強(qiáng)度差值分配不同的權(quán)值來(lái)平衡信號(hào)距離和物理距離之間的差異，計(jì)算如下：

(7)

(8)

(9)

根據(jù)測(cè)試點(diǎn)與所有參考點(diǎn)的信號(hào)加權(quán)歐氏距離的大小，選出距離最小的k個(gè)參考點(diǎn)作為最近鄰參考點(diǎn)估計(jì)用戶的位置：

(10)

(11)

其中，(X,Y)為估計(jì)的位置坐標(biāo)，(Xi,Yi)為第i個(gè)參考點(diǎn)位置坐標(biāo)，ωi為第i個(gè)參考點(diǎn)位置坐標(biāo)的權(quán)重。相比于現(xiàn)存的加權(quán)k近鄰算法，使用加權(quán)歐氏距離選出的最近鄰參考點(diǎn)以及參考點(diǎn)的坐標(biāo)權(quán)重更加合理，可以大大提高定位精度。

為了確定提出的算法滿足實(shí)時(shí)定位需求，可計(jì)算算法的時(shí)間復(fù)雜度：

(1)計(jì)算測(cè)試點(diǎn)與N個(gè)參考點(diǎn)的信號(hào)強(qiáng)度平均值以及來(lái)自不同無(wú)線接入點(diǎn)的信號(hào)強(qiáng)度差值的加權(quán)系數(shù)，時(shí)間復(fù)雜度為O(N+NM)，即O(NM)。

(2)計(jì)算測(cè)試點(diǎn)與N個(gè)參考點(diǎn)的加權(quán)歐氏距離，時(shí)間復(fù)雜度為O(N)。

(3)對(duì)所有加權(quán)歐氏距離排序，時(shí)間復(fù)雜度為O(NlbN)。

(4)計(jì)算k個(gè)最近鄰參考點(diǎn)的坐標(biāo)權(quán)重以及對(duì)最近鄰參考點(diǎn)坐標(biāo)進(jìn)行加權(quán)平均，時(shí)間復(fù)雜度為O(k)。

傳統(tǒng)的加權(quán)k近鄰算法的時(shí)間復(fù)雜度為O(NlbN)+O(k)。因此，只有當(dāng)M>lbN時(shí)，所提出算法的時(shí)間復(fù)雜度O(NM)+O(k)才會(huì)大于傳統(tǒng)的加權(quán)k近鄰算法的，但仍可以滿足實(shí)時(shí)定位的需求。在其他情況下，文中所提出的算法的時(shí)間復(fù)雜度為O(NlbN)+O(k)，與傳統(tǒng)算法處于同一個(gè)量級(jí)。

此外，為了更直觀地說(shuō)明所提出的加權(quán)歐氏距離的優(yōu)勢(shì)，筆者基于仿真數(shù)據(jù)對(duì)比了改進(jìn)的加權(quán)k近鄰算法與傳統(tǒng)的加權(quán)k近鄰算法。考慮一維坐標(biāo)系中的2個(gè)無(wú)線接入點(diǎn)、2個(gè)參考點(diǎn)和5個(gè)測(cè)試點(diǎn)，根據(jù)式(6)的信號(hào)對(duì)數(shù)損耗模型，可以得到不同距離處的各點(diǎn)接收信號(hào)強(qiáng)度值，模型參數(shù)設(shè)置與圖1相同。表2列舉了5個(gè)測(cè)試點(diǎn)與2個(gè)參考點(diǎn)間的信號(hào)歐氏距離和信號(hào)加權(quán)歐氏距離，以及每個(gè)測(cè)試點(diǎn)與2個(gè)參考點(diǎn)的兩種信號(hào)距離的比值。可以看出，相比于傳統(tǒng)的信號(hào)歐氏距離，測(cè)試點(diǎn)與兩個(gè)參考點(diǎn)的信號(hào)加權(quán)歐氏距離的比值更接近于相應(yīng)的物理距離的比值。這說(shuō)明加權(quán)歐氏距離更能反映位置點(diǎn)間的物理距離，因此在尋找最近參考點(diǎn)以及計(jì)算不同參考點(diǎn)的坐標(biāo)權(quán)重的過(guò)程中，其定位性能優(yōu)于傳統(tǒng)的加權(quán)k近鄰算法的。

表2 基于仿真數(shù)據(jù)的測(cè)試點(diǎn)與參考點(diǎn)間信號(hào)歐氏距離和信號(hào)加權(quán)歐氏距離

3 實(shí)驗(yàn)結(jié)果及評(píng)估

3.1 實(shí)驗(yàn)環(huán)境及實(shí)驗(yàn)設(shè)置

圖2 WiFi指紋定位實(shí)驗(yàn)環(huán)境

為了驗(yàn)證文中提出的定位方法性能，在某實(shí)驗(yàn)樓2樓進(jìn)行WiFi指紋室內(nèi)定位實(shí)驗(yàn)。如圖2所示，實(shí)驗(yàn)場(chǎng)地內(nèi)共布置7個(gè)無(wú)線接入點(diǎn)，200個(gè)參考點(diǎn)和50個(gè)測(cè)試點(diǎn)，相鄰參考點(diǎn)的距離為1.2 m。實(shí)驗(yàn)設(shè)備為小米MIX 2智能手機(jī)，WiFi信號(hào)采樣頻率為1 Hz。每個(gè)測(cè)試點(diǎn)處采集接收信號(hào)強(qiáng)度數(shù)據(jù)的時(shí)間為60 s，并取其平均值作為在線接收信號(hào)強(qiáng)度量測(cè)值。

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

為了驗(yàn)證WiFi信號(hào)的衰減特性，筆者采集了所有無(wú)線接入點(diǎn)在不同距離處的信號(hào)強(qiáng)度值，每個(gè)距離處采集時(shí)間為60 s，平均后的信號(hào)強(qiáng)度值如圖3所示。

圖3 無(wú)線接入點(diǎn)1～3在不同距離處的信號(hào)強(qiáng)度值

圖4 無(wú)線接入點(diǎn)4～7在不同距離處的信號(hào)強(qiáng)度值

從圖3和圖4可以看出，由于在室內(nèi)環(huán)境中WiFi信號(hào)受到反射、折射、繞射以及多徑效應(yīng)的影響，實(shí)測(cè)的接收信號(hào)強(qiáng)度值呈現(xiàn)出波動(dòng)性，但仍然可以很好地逼近WiFi信號(hào)損耗模型曲線，即隨著距離無(wú)線接入點(diǎn)距離的增加，信號(hào)衰減速率變慢。這證明了筆者提出的信號(hào)加權(quán)歐氏距離能夠適用于真實(shí)的定位場(chǎng)景。

為了更直觀地展示改進(jìn)的加權(quán)k近鄰算法在搜索最近鄰參考點(diǎn)和位置加權(quán)估計(jì)的優(yōu)勢(shì)，隨機(jī)選擇了5個(gè)參考點(diǎn)，比較了改進(jìn)的加權(quán)k近鄰算法和基于歐氏距離的加權(quán)k近鄰算法的最近鄰參考點(diǎn)選擇以及定位誤差。表3根據(jù)參考點(diǎn)與測(cè)試點(diǎn)信號(hào)距離由小到大的順序，列舉了前4個(gè)最近鄰參考點(diǎn)以及相應(yīng)的歸一化物理距離?？梢钥闯?，對(duì)于基于歐氏距離的加權(quán)k近鄰算法所選擇的最近鄰參考點(diǎn)，其與測(cè)試點(diǎn)的物理距離排序與信號(hào)歐氏距離的排序并不一致。而對(duì)于改進(jìn)的加權(quán)k近鄰算法所選擇的最近鄰參考點(diǎn)，其與測(cè)試點(diǎn)的物理距離排序與信號(hào)加權(quán)歐氏距離的排序基本一致。話句話說(shuō)，信號(hào)加權(quán)距離越小代表物理距離也就越小。因此，使用加權(quán)歐氏距離可以提高指紋匹配的準(zhǔn)確度，賦予最近鄰參考點(diǎn)坐標(biāo)更合理的權(quán)重，可提高位置估計(jì)的精度。

表3 兩種加權(quán)k近鄰算法的最近鄰參考點(diǎn)選擇和定位誤差

為了驗(yàn)證所提出的算法能夠顯著提高定位精度，比較了3種基于不同距離度量的加權(quán)k近鄰算法的定位誤差：基于歐氏距離的加權(quán)k近鄰算法、基于曼哈頓距離的加權(quán)k近鄰算法和文中提出的基于加權(quán)歐氏距離的改進(jìn)的加權(quán)k近鄰算法。3種算法在選取不同數(shù)量的最近鄰參考點(diǎn)下的平均定位誤差如圖5所示，選取的最近鄰參考點(diǎn)個(gè)數(shù)等于4時(shí)的定位誤差累計(jì)概率分布如圖6所示?？梢钥闯?，所提出的改進(jìn)的加權(quán)k近鄰算法的定位誤差明顯小于其他兩種算法的。

圖5 不同最近鄰參考點(diǎn)個(gè)數(shù)下的平均定位誤差

圖6 最近鄰參考點(diǎn)個(gè)數(shù)為4時(shí)定位誤差累計(jì)概率分布

表4改進(jìn)的加權(quán)k近鄰算法和傳統(tǒng)的加權(quán)k近鄰算法的定位誤差統(tǒng)計(jì)m

方法50%定位誤差75%定位誤差平均定位誤差均方根定位誤差改進(jìn)的加權(quán)k近鄰算法1.352.481.821.51基于歐氏距離的加權(quán)k近鄰算法1.762.912.291.95基于曼哈頓距離的加權(quán)k近鄰算法1.813.692.612.14

從表4列出的定位誤差統(tǒng)計(jì)值中可以得出同樣的結(jié)論，即相比于傳統(tǒng)的基于歐氏距離和曼哈頓距離的加權(quán)k近鄰算法，所提出的改進(jìn)的加權(quán)k近鄰算法具有更小的定位誤差。相比于基于歐氏距離的算法，其平均定位誤差提升了20.5%，均方根誤差提升了22.6%。相比于基于曼哈頓距離的算法，其平均定位誤差提升了30.3%，均方根誤差提升了29.4%。

4 結(jié)束語(yǔ)

筆者通過(guò)分析室內(nèi)WiFi信號(hào)的波動(dòng)性,在信號(hào)距離計(jì)算中引入了接收信號(hào)強(qiáng)度方差，并根據(jù)WiFi信號(hào)的衰減特性給不同的接收信號(hào)強(qiáng)度差值分配權(quán)值，提出了一種改進(jìn)的加權(quán)k近鄰算法。實(shí)驗(yàn)結(jié)果表明，所提出的信號(hào)加權(quán)歐氏距離能夠更準(zhǔn)確地反映各位置點(diǎn)間的物理距離，提高了指紋匹配的準(zhǔn)確度和定位精度。改進(jìn)的加權(quán)k近鄰算法的平均定位誤差可達(dá)1.82 m，相比于傳統(tǒng)的基于歐氏距離和曼哈頓距離的加權(quán)k近鄰算法，其平均定位誤差分別約提升了20.5%和30.3%，能夠滿足用戶在室內(nèi)的高精度定位需求。