一種基于CSI和RSSI的混合指紋定位方法*

黑毅力,黨小超,郝占軍*

(1.西北師范大學計算機科學與工程學院,蘭州 730070;2.天水第一中學,甘肅 天水 741000; 3.甘肅省物聯網工程研究中心,蘭州 730070)

近年來,隨著無線通信技術的不斷突破和移動互聯設備的推廣普及,人們對基于位置的服務LBS(Location Based Services)需求也越發強烈[1]。全球定位系統GPS(Global Positioning System)是目前世界上最常用的衛星定位系統。然而,由于復雜的室內環境中,GPS信號容易受到多徑效應的影響導致定位失效[2-3],所以迫使人們通過研究室內定位理論與技術來尋求高精度、低功耗的定位解決方案。其中,室內WiFi無線接入點AP(Access Point)的廣泛部署促使WiFi定位技術變得越來越流行,尤其是基于位置指紋的定位方法因其成本低廉、方法簡易的優勢逐漸成為室內定位的主流[4]。

傳統的指紋定位方法通常包含兩個階段:離線訓練階段(offline phase)和在線預測階段(online phase)[5]。在離線階段,通過大量采集定位區域中各個參考點RP(Reference Point)的無線信號特征作為該位置的指紋,構造位置-指紋數據庫。在線階段,通過將用戶所在位置的無線信號指紋特征與數據庫信息相匹配,得到匹配度最高的指紋所對應的位置作為用戶的最終位置。現有的指紋定位系統大多利用簡單且無需額外設備配置的WiFi接收信號強度RSSI(Received Signal Strength Indication)作為一種粗粒度的指紋信息,Fang等[6]提出一種利用WLAN主成分構建位置指紋的方法,它將RSSI測量值利用主成分分析的方法智能地轉換為指紋數據主成分,充分利用接入點的信息,提高了指紋定位方法的效率和魯棒性;Lei等[7]提出一種利用坐標差分修正的加權KNN室內WiFi定位方法(DC-WKNN),該方法首先構建RSSI指紋數據庫,然后利用加權KNN方法找到K個與查詢點最近的參考點,引入參考點的誤差向量,并利用誤差向量修正目標點的最終定位結果,較傳統的KNN和加權KNN方法提高了定位的精度。但是,室內非視距環境中多徑效應的存在會導致RSSI值的穩定性極度下降,從而無法滿足室內精確定位的要求[8]。基于物理層的信道狀態信息CSI(Channel State information)彌補了傳統RSSI中簡單子載波均值疊加幅度處理方式的不足,在一定程度上刻畫了多徑傳播,將單值RSSI幅度擴展至頻域,還附加了每個子載波的相位信息,為室內WiFi指紋定位技術提供了更為精細且穩定的信號特征信息[9-10]。Wu等[11]首次通過采集WiFi信號中的信道狀態信息作為特征進行定位,極大降低了定位的誤差。Wang等[12]也通過深度學習的方法訓練CSI數據產生權值特征作為指紋,提出一種高定位精度DeepFi定位算法,且在一定程度上減少了算法的復雜度。Chen等[13]提出了一種基于卷積神經網絡的室內定位方法,它將CSI組織成類似于圖像的時頻矩陣作為特征圖像,然后引入卷積神經網絡對指紋數據進行訓練,最后輸出加權質心結果作為目標最終位置。Zhou等[14]為了彌補利用CSI幅度信息定位引起的準確性和穩定性不足的問題,設計實現了一種基于CSI幅度和相位特征混合的指紋定位算法,在一定程度上提高了定位精度。然而,由于位置指紋定位方法在一定程度上為了保證預測精確度,本身就需要依賴于大量的訓練樣本,而將原始的CSI數據在未經處理的情況下直接作為指紋特征,數據維數較高,而且在某些情況下,原始CSI比RSSI值更容易受到動態環境的影響[15],導致參數估計難度較大,計算量也會增加。

通過研究分析傳統指紋定位方法和新興CSI信號特征,本文提出了一種混合WiFi位置指紋定位方法。該方法在離線階段通過移動終端在已知參考位置采集來自各個AP的RSSI信號和CSI信號共同建立更加魯棒的位置指紋數據庫,同時,為了降低指紋數據的復雜度和定位誤差,引入空間劃分聚類的方法對無線RSSI指紋地圖進行合理劃分,縮小搜索空間,實現目標位置的粗定位過程;在線階段,在保證高定位精度和可信度的前提下,為了進一步降低在匹配階段的計算量,在指紋地圖子區域中通過使用主特征提取方法得到對應位置的CSI指紋特征;最后,利用Kendall階次相關系數自主選擇K個近鄰參考點,利用加權估計的方法獲得最終結果作為目標的位置。

1 相關理論

1.1 信道狀態信息

在現有的通信系統中,正交頻分復用技術OFDM(Orthogonal Frequency Division Multiplexing)是應用最廣泛的一種多載波傳輸方案。它通過將信道分成若干正交子信道,然后再將數據調制到每個子信道上進行傳輸,最大限度地消除多徑干擾[16]。通過對現有的普通商用Wi-Fi設備添加兼容IEEE 802.11n的無線網卡,可以獲取無線信號發射端和接收端之間的CSI,它提供了多個子載波上的信號幅度和相位兩方面的信息。作為RSSI的升級版本,CSI能夠提供更為精細的多徑傳播信息[17]。在OFDM傳輸系統中,每個信道狀態的頻域模型可以表示為:

Y=H·X+N

(1)

式中:Y與X分別表示接收和發送信號向量,H表示信道信息矩陣,N表示加性高斯白噪聲。其中各個子載波的CSI可以表示為:

CSI=Y/X

(2)

假設在OFDM傳播過程中的子載波數為N,則CSI矩陣H可以表示為:

H=[H0,H1,…,Hi,…,HN-1]T,i∈[0,N-1]

(3)

定義第i個子載波的CSI為:

Hi=|Hi|ej(∠Hi)

(4)

其中Hi和∠Hi分別表示第i個子載波的振幅和相位。圖1表示使用2根接收天線和2根發送天線在兩個相距1 m距離的測試點1和測試點2采集到的CSI信號圖,從圖中可以得出CSI對于不同的傳播環境可以呈現不同的子載波幅度,這也驗證了將CSI信號當作某個特定位置上的信號特征指紋進行定位的可行性。

圖1 CSI采樣圖

1.2 主成分分析理論

主成分分析PCA(Principal Component Analysis)也稱主分量分析,是應用最廣泛的一種數學降維方法,其基本原理就是通過對數據的協方差矩陣進行特征值分解,特征值分解后的特征向量對應數據的主成分,特征值對應數據在各個主成分上的權重[18]。它將一個矩陣中樣本數據投影到一個新的空間中,用較少的新變量代替原來較多的舊變量,達到簡化數據集的目的,這樣不僅可以減少冗余數據,還可以去除噪聲干擾。

假定m個樣本在原始p維空間的數據矩陣為X=(x1,x2,…,xm)∈p×m,當p值較大時,在p維空間中考慮問題必定會增加計算的復雜度。為了解決這個問題,就需要進行降維處理,即用較少的綜合指標代替原來的指標,而且使這些綜合指標能盡量多地反映原來指標所表示的信息。為此,首先通過對所有樣本進行中心化,得到新矩陣p×m,其中然后計算樣本的協方差矩陣Y=X′X′T,對協方差矩陣Y進行特征值分解,將得到的特征值排序:λ1≥λd≥…≥λm,再取前m′個特征值對應的特征向量構成最終主成分分析的解

2 一種基于CSI和RSSI的混合定位方法

2.1 原始位置指紋空間聚類劃分

一般地,為了保證較高的定位的精度,指紋定位方法需要采集定位區域中大量的指紋數據建立數據庫,當定位或追蹤區域擴大時,指紋空間也會相應變大,如果不加處理在全局考慮問題,勢必會增加計算負擔。為了解決這個問題,本文將使用一種空間聚類劃分CLIQUE(Clustering In QUEst)的方法首先對定位區域中RSSI指紋信號進行子區域的劃分,在線定位階段只考慮子區域中的CSI信號指紋數據。CLIQUE是一種簡單的基于密度和網格的聚類方法,在處理混合型及高維數據空間數據方面具有很高的效率[19]。該方法是將數據空間Z分割成若干個矩形網格單元,將落到每一個網格單元中的點數作為這個單元的數據對象密度。設定一個閾值,當某個單元格的密度(點的個數)大于該數值時,就說這個網格單元是密集的。為了清楚闡述CLIQUE聚類劃分原理,給出以下定義1～4。

圖2 MixedFi定位方法流程圖

定義1設A={D1,D2,…,Dn}是n個有界的定義子空間,則Z=D1×D2×…×Dn就是一個n維的數據空間,將D1,D2,…,Dn看作Z的維(屬性或字段)。

定義2在n維數據空間中,一個聚類是由多個連通的密集單元格組成的最大單元集。

定義3一個單元格ui的選擇率selectivity(ui)定義為單元格中的點數與總的點數的比值。

定義4兩個n維中的單元格u1,u2,如果是連通的,當且僅當這兩個單元格有一個公共面或者u1,u2都跟另外一個單元格u3連通。

基于以上描述,RSSI指紋空間聚類劃分具體步驟如下:

輸入:原始指紋空間樣本點集V={v1,v2,…,vm},其中vi={rssii1,rssii2,…,rssiin},vi的第j個分量vij∈Dj。

過程:

1:選擇參數ξ,將空間Z分割為同樣的ξ個子區域,產生d個不相交的類矩形單元{u1,u2,…,ud},其中ui=[li,hi)

2:repeat

3: forj=1,2,…,mdo

4: 遍歷所有的數據對象V={v1,v2,…,vm};

5: if每一個ui都有li≤vi

6: 判斷對象vi是否落入一個單元格u={u1,u2,…,ud};

7: end if

8:end for

9:輸入密度閾值參數φ;

10: if selectivity(ui)>φ成立then

11: 判定數據單元ui是稠密的,找到所有n維子空間中的密集單元;

12: 通過n維子空間中的稠密單元集,找出n+1維子空間中的候選稠密單元集合;

13: else

14: 若n+1維子空間中的候選稠密單元集不為空,則跳轉到第3步;

15: end if

18: end if

19:untiln維數據空間搜索連通的密集單元格組成的最大單元集找到

2.2 在線位置指紋特征值提取

假設在定位子區域中將N個采樣位置采集到的n個有效接入點的CSI數據信息作為原始指紋,則構成一個n×N維的指紋空間A,A可以表示為

其中csipi表示在第p,p∈[1,N]個參考點測量得到的第i,i∈[1,n]個AP的采樣樣本數據。可以看到當參考點和AP數量增加時,其CSI指紋樣本維數也會激增,因此選擇主成分分析法對數據進行降維,減少數據量,節省時延和能耗。

2.3 自主近鄰選擇加權定位

K近鄰方法因其復雜度低的優勢在搜索匹配中得到了廣泛的使用,然而傳統的KNN方法只按照排序選定前K個近鄰樣本而忽略樣本屬性差別從而造成精度的嚴重下降,尤其當樣本密度分布極其不均勻時。為了解決這個問題,本文引入Kendall相關系數的思想自適應得到目標節點的K個近鄰點,同時給每一個對象對應的坐標利用加權的方式來計算未知點的最終位置坐標。

設目標點采集到來自AP的CSI信號構成在線指紋向量T={csi1,csi2,…,csip},對T進行PCA變換后,得到在線目標特征指紋向量T′,通過與特征指紋數據庫比對得到近鄰點,具體計算如下。

(5)

(6)

3 實驗與分析

為了驗證本文方法在實際室內環境中的性能,仿真實驗分別在12 m×9 m的實驗室和8 m×6 m的會議室環境中進行,布局分別如圖3(a)和圖3(b)所示。

圖3 實驗場景圖

本文采用安裝64位Ubuntu12.04LTS操作系統并配置Atheros9380網卡的4臺電腦分別作為信號發送機和接收機,網卡附帶三根2.4 G/5 GHz的雙頻外部天線,圖中三角形表示部分隨機測試點的位置,根據文獻[21]的結論,AP天線基本統一放置在距離地面1 m的試驗臺,因為在1 m高度RSSI信號精度是最高的。在采集RSSI信號數據時,測試者手持一臺操作系統是MIUI 9的MI5X手機作為可移動設備靜立在參考點進行數據采集,黑色圓點表示參考點,三角形表示待測點,測試點可以接收來自4個AP的信號,每個參考點采集RSSI數據30次,保存至PC端取平均值建立數據庫作為該點的RSSI特征向量。實驗環境以左下角為起點,設其坐標為(0,0),相鄰參考點之間的間隔為0.5 m,在實驗室環境中共收集90個位置的指紋信息,在會議室環境中收集75個點的指紋信息,同時在兩個實驗環境中的非參考點位置隨機選取50個點作為測試位置,通過比較測試點的估計位置與實際位置來評價定位算法的性能。部分實驗室原始位置指紋數據如表1所示,表2中的數據為經過PCA處理后提取5個主要特征得到的指紋數據。

表1 選取56維的原始位置指紋數據

表2 PCA提取5維的位置指紋數據

3.1 離線階段樣本點數對定位的影響

利用上述實測數據,在相同參數條件下,比較了室內采樣點數取不同值時,本文MixedFi方法和DeepFi、DC-WKNN方法定位誤差情況,同時,為了最大限度地消除實驗中隨機誤差的干擾,取每個測試點30次實驗位置的平均值作為最終結果。采用均一化定位誤差和誤差累計分布函數CDF(Cumulative Distribution Function)來評價性能,均一化定位誤差為:

(7)

圖4表示在實驗室中,參考點個數為20(圖4(a))和60(圖4(b))的情況下,各種方法定位結果誤差的累計分布函數。從圖中可以看出,當參考點個數為20時,MixedFi定位方法所對應的定位誤差在2 m內的累計概率超過了60%,而DeepFi和DC-WKNN方法在2 m的累計概率則分別是55%和40%。當參考點個數為60時,MixedFi定位方法所對應的定位誤差在1.8 m內的累計概率超過了80%,而DeepFi和DC-WKNN方法在1.8 m的累計概率則分別是75%和55%。所以隨著參考點個數的增加,幾種定位方法的準確率都在增加,并且MixedFi方法的定位精度始終高于DeepFi和DC-WKNN方法。

圖4 誤差累計分布圖

在空曠的會議室環境中,在參考點個數為20和60時,各定位方法定位誤差累計分布函數如圖5所示。其中,當參考點個數為20時,MixedFi方法定位誤差落在1.5 m范圍內的累計概率為85%左右,比DeepFi和DC-WKNN方法分別高出了15%和45%。且當參考點個數為60時,累計概率為60%時,MixedFi、DeepFi和DC-WKNN方法的定位誤差值分別為1.23 m,1.47 m,1.83 m,從統計學概率分布可以得出相比于其他兩種方法,本文所提出的方法定位精度最高。

圖5 誤差累計分布圖

通過上述實驗可以看出,相比于其他相似方法,本文提出的方法能夠在參考點選取多組不同的值時,隨著參考點個數的變化,MixedFi定位方法的誤差率均比DC-WKNN方法低,且誤差始終保持在3 m以內。這是因為MixedFi是對若干個可能的節點位置利用穩定性更高的CSI信號結合Kendall相關系數自適應確定鄰居節點進行加權修正計算,而DC-WKNN是通過粗粒度RSSI信號匹配鄰近節點確定節點坐標,相比之下,MixedFi方法的定位精度更高,誤差更小,穩定性也較好。表3列出了實驗室和會議室環境下各個定位方法的平均誤差、標準誤差以及平均定位精度,可以得出本文提出的方法相對于傳統的DeepFi和DC-WKNN方法,平均定位精度分別提高了約6.8%和38%,穩定性更高,可以很好地滿足室內定位的精度要求。

表3 方法整體定位性能比較

3.2 天線數量對定位的影響

在指紋定位方法中,信號發送機和接收機的天線數量也會對定位的性能產生一定的影響。發射天線TX(Transmitting antennas)和接收天線RX(Receiving antennas)的數目決定了通信鏈路的數量,也可以更加精細地刻畫選擇性信道。在本文中,隨機部署1TX-1RX,1TX-2RX,2TX-2RX,2TX-3RX和3TX-3RX進行實驗。

圖6是在兩種實驗場景下,當天線數量情況變化時定位平均誤差的變化情況,可以看出,在實驗室環境中,從1TX-1RX到2TX-2RX,幾種定位方法精度分別提高了15.4%,9.0%,13.0%;從2TX-2RX到3TX-3RX,分別提高了約48.3%,33.2%,17.1%,在3TX-3RX時,從圖6(b)中可以看到本文的定位精度可以達到1.02 m。在會議室環境中,由于多徑效應的影響比較小,天線數量的變化對定位精度的影響并不明顯,但是總體隨著天線的增加,幾種方法的定位精度也在增加,這是因為通信鏈路的質量決定了位置指紋信號的穩定性,且在不同的通信鏈路情況下,本文提出的方法均優于其他兩種方法。

圖6 平均定位誤差隨天線數量的變化情況

3.3 閾值θ對定位性能的影響

一般地,閾值θ是一個在[-1,1]范圍內的常數,當θ值等于1時,判定兩個隨機變量具有一致的等級相關性;當θ值等于-1時,判定兩個隨機變量具有完全相反的等級相關性;當θ值等于0時,則判定兩個隨機變量是相互獨立的。根據式(5)可以自適應得到K個近鄰點,這樣可以有效解決傳統K近鄰方法中K的取值問題。

為了得到閾值θ的最佳取值,實驗測試了在θ取不同值時,定位準確率的變化,結果如圖7所示。可以看到,在θ=0.1時,滿足條件的近鄰數為7,此時定位的準確率是45%;在0.2≤θ≤0.4時,隨著θ的增大,定位的準確率呈上升趨勢,在θ=0.4時,定位準確率達到最大;然而當θ超過0.4以后,隨著θ的增大,意味著兩個特征指紋向量的相關性也增大,此時滿足定位條件的近鄰數相應會減少,定位準確率整體呈下降趨勢。

圖7 定位準確率隨閾值θ值變化情況

3.4 定位時間比較

定位時間是衡量定位方法的一個重要指標,本實驗采用平均時間消耗來評價定位性能。實驗時在相同區域中將參考點數目設為80,閾值θ=0.4,設置天線數量為2TX-2RX,在MATLAB平臺上,定義平均定位耗時為網絡中所有待定位節點完成定位過程所消耗的時間總和與網絡中節點總數的比值。假設將節點i完成定位所消耗的時間記為ti,則S個目標點的平均定位耗時可定義為:

(8)

圖8 平均定位耗時比較

定位目標點對定位時間的影響如圖8所示,定位時間隨著待定位點的增加而增加。當目標定位點數量增多時,需要搜索和匹配最佳鄰節點的過程時間將增加,進而定位時間增加。本文提出的方法由于在定位計算之前對定位區域進行了合理的劃分,極大縮小了定位區域,同時在進行CSI指紋匹配時再次利用主成分分析對數據進行降維處理也減少了計算量,比傳統DC-WKNN方法在平均定位時間上快了2.6s,比DeepFi方法快1.1s,在實用效率方面得到了很大的提升。

3.5 算法復雜度比較

假設n為總參考點數,在離線訓練階段,DeepFi利用貪婪算法訓練數據集,算法計算權值用時O(n),排序用時為O(nlogn),最后選擇過程用時O(n),所以算法離線階段時間復雜度為O(nlogn)。而MixedFi在離線階段利用空間聚類的方法減少數據集,算法首先遍歷所有數據點用時為O(n),每個點查詢周圍的數據點用時O(logn),因此總時間復雜度為O(nlogn)。假設MixedFi和DeepFi方法在離線階段對數據集進行處理后,數據集在最壞情況下的最大近鄰數為m,且m?n。在線定位階段,由于DC-WKNN和MixedFi這兩種方法都是基于最近鄰居的選擇策略,但是DC-WKNN需要考慮幾乎所有的近鄰,因此DC-WKNN的算法復雜度為O(n),而MixedFi算法復雜度為O(m),可以看到DC-WKNN的速度是最慢的。DeepFi方法在現階段利用徑向基函數得到最終結果估計,而一般高斯核需將最初的m維特征映射到m2維后再進行計算,因此算法復雜度為O(m2)。綜上分析,MixedFi、DeepFi和DC-WKNN方法的時間復雜度分別為O(nlogn+m),O(nlogn+m2),O(n2)。一般地,定位系統只考慮在線定位階段的時延,因此MixedFi定位方法的執行效率仍然是最好的。

4 結束語

本文提出了一種基于CSI和RSSI的混合位置指紋定位方法(MixedFi)。該方法針對已有的基于RSSI指紋定位方法定位精度較低的問題,離線階段充分利用WiFi信號信息,將RSSI和CSI信號有效結合共同作為混合位置指紋信息,結合空間聚類方法對指紋數據有效劃分,精確縮小定位搜索范圍,然后利用主成分分析方法降低CSI指紋特征維度提高定位效率。最后,為了提高傳統KNN方法的定位精度,引入Kendall階次相關系數自適應篩選最優鄰居節點進行目標點加權位置計算。實驗表明,本文的方法能有效提高定位精度,同時相同條件下定位時間也得到了極大地改進,具有很強的實用性。下一步研究將集中在提高方法對實際三維室內外環境定位的普適性,同時進一步降低定位誤差和復雜度。