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

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

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

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

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

(1)

(2)

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

2 改進的WiFi指紋定位算法

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

(3)

(4)

(5)

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

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

(6)

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

圖1 接收信號強度與物理距離的關(guān)系示意圖

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

(7)

(8)

(9)

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

(10)

(11)

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

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

(1)計算測試點與N個參考點的信號強度平均值以及來自不同無線接入點的信號強度差值的加權(quán)系數(shù)，時間復(fù)雜度為O(N+NM)，即O(NM)。

(2)計算測試點與N個參考點的加權(quán)歐氏距離，時間復(fù)雜度為O(N)。

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

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

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

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

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

3 實驗結(jié)果及評估

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

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

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

3.2 實驗結(jié)果分析

為了驗證WiFi信號的衰減特性，筆者采集了所有無線接入點在不同距離處的信號強度值，每個距離處采集時間為60 s，平均后的信號強度值如圖3所示。

圖3 無線接入點1～3在不同距離處的信號強度值

圖4 無線接入點4～7在不同距離處的信號強度值

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

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

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

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

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

圖6 最近鄰參考點個數(shù)為4時定位誤差累計概率分布

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

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

4 結(jié)束語

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