基于機器學習的室內定位技術研究

郭正碩，徐舒敏，吳錦州，華 勝

（1.南京郵電大學 物聯網學院，江蘇 南京 210000；2.南京郵電大學 計算機軟件學院，江蘇 南京 210000；3.南京郵電大學 通信與信息工程學院，江蘇 南京 210000）

當前，室內定位的實現方案很多，基于無線局域網（Wireless Local Area Networks，WLAN）的定位方法主要有三角形算法和位置指紋識別。三角形算法利用最少3個已知無線接入點（Access Point，AP）之間的距離信息估計目的坐標，其中，距離是通過測量來自AP的接收信號強度（Received Signal Strength，RSS）進行估計，而基于三角形算法的WLAN定位在不同環境下的傳輸損耗大不同，所以也很難建離精準、合適的損耗模型[1-2]。因此，基于三角形算法的定位方法在實施過程中困難重重。

WLAN具有高精度、低成本、可移動的優點，本項目基于機器學習算法，使用Matlab軟件，應用Hankel矩陣和自適應卡爾曼濾波技術，將噪聲信號在指紋數據庫中進行過濾，實現離線和在線的室內定位。離線階段和在線階段共同處理，既能在指紋數據庫上更好地降噪，又能提高算法的定位精度。實現方案經過實驗數據檢驗，具有精度上的可靠性。

離線階段的主要任務是構建一個指紋識別數據庫，本文構建指紋數據庫的Hankel矩陣，利用信號空間和噪聲空間奇異值不同的特點，可以有效去除部分噪聲，重構成較為精確的指紋數據庫，以供在線階段比對。

與傳統矩陣恢復算法相比，本文所提出的基于Hankel矩陣的方法在計算復雜度和降噪性能方面具有優勢。Hankel矩陣在從左到右的每個上升斜交對角線中具有相等的元素，可以通過適當的奇異值閾值，僅通過一個奇異值分解，就將信號空間與噪聲空間分開。基于奇異值的分解降噪是一種分析非線性、非平穩信號的有效方法，由于Hankel矩陣結構具有特殊性，可以有效地將噪聲與需要的信號分離、提高信噪比，并且能保留與噪聲信號的頻譜相混疊的系統信號。

在線階段，用戶終端測量來自所有AP的RSS，并將其與指紋數據庫中信號強度空間的RSS進行比對，用合適的指紋匹配算法計算用戶的位置。廣泛使用的指紋匹配算法是WKNN算法，但傳統的WKNN算法存在一定的局限性，會影響定位精度，需要進行改進。

Luo等[3]指出RSSI概率分布呈現一定的高斯分布特性，朱雪梅等[4]在其基礎上提出了一種基于RSSI分布重疊相似度的WKNN室內定位方法，即利用RSSI高斯概率分布重疊相似度與距離之間的關系，設定相似度閾值選取k個近鄰指紋點作為取樣點，以此獲取定位結果，解決傳統最大相似度法可能帶來的較大誤差和定位時間較長等問題。但實際上，參考點上信號強度分布并不是一個標準的高斯分布，還受到各種干擾的影響，因此，需要考慮各AP信號強度之間的關系。陳淼[5]認為，AP信號強度大小主要受到AP信號發射穩定性帶來的影響。在此基礎上，本文基于方差進行改進算法，降低AP信號發射穩定性帶來的干擾，進一步提高定位的精度。

本文在指紋數據庫構建階段，基于Hankel矩陣的特性、真實信號空間和噪聲空間奇異值不同，通過特征均值法設置閾值，對離線階段的指紋數據庫進行降噪處理，提高了離線階段指紋數據庫的精確度。同時，提出了一種提高定位精度的方法，主要分為兩步：第一步，利用自適應濾波方法，降低定位系統外部環境變化帶來的干擾。第二步，對自適應濾波過濾后的指紋數據庫使用基于方差改進的WKNN算法，降低定位系統內部AP發射功率穩定性帶來的影響。利用各取樣點在不同的AP下測得的方差設置權值，為不同的RP坐標分配權重，有效地降低了AP波動帶來的干擾，提高了現有WKNN算法的定位精度。

1 離線階段指紋數據庫的構建

1.1 Hankel矩陣奇異值分解原理

假設存在矩陣M為m×n階，其中的元素均屬于R或者C。則存在一個分解使：

其中，U是m×m階幺正矩陣，∑是半正定m×n階對角矩陣；而V*是V的共軛轉置矩陣，是n×n階酉矩陣。此分解法稱為矩陣的奇異值分解。對Hankel矩陣H進行奇異值分解得到：

式中，Um×m和Vn×n為正交矩陣，∑m×n為非對角矩陣，為矩陣H的奇異值。保留前K個奇異值而剩余則置零，再利用奇異值分解的逆過程得到重構矩陣H_s，將H_s依據空間重構的方法得到降噪后的信號。

本文假設信號與噪聲空間互不相干、奇異值不相同、信號空間較為集中，而噪聲空間相對而言較為分散，根據這些特點設置合適的閾值，將信號與噪聲分離。

1.2 離線階段指紋數據庫處理

1.2.1 含噪指紋數據庫到Hankel矩陣處理原理

假定含噪指紋數據庫包含位置空間和信號強度空間的映射關系，其中，位置空間由所有參考點（RP）的位置構成，信號強度空間由RP從AP測得的一系列接收信號強度（RSS）值構成，每個RP的位置對應一組來自所有AP的RSS值。

將所有參考點來自同一AP的RSS向量構成Hankel矩陣H。為了實現信號和噪聲的充分分離，構造的Hankel矩陣行數m和列數n的乘積應盡可能地最大。滿足行數m和列數n的最大乘積主要取決于信號個數的奇偶性，所以，根據N的奇偶性和不等式原理來確定矩陣行數m。劉佳音等[6]研究發現，當N為奇數時，m＝（N＋1）/2；當N為偶數時，m＝N/2，式中，N為信號個數，n由等式n＝N＋1－m來確定。

從含噪聲指紋庫中提取第i（1≤i≤N）個RP對應的來自各個AP的RSS值組成的信號矢量Xi，將Xi構造成Hankel矩陣Hi。

一個Hankel矩陣H可以表示為由一個信號空間Hs和一個噪聲空間Hn構成：

1.2.2 Hankel矩陣降噪原理

基于奇異值分解的信號降噪方法基本思路：根據真實信號和噪聲的不同特征，將含噪的測量信號構成的Hankel矩陣分解成真實信號空間與噪聲空間，利用不同的奇異值選擇方法對兩個空間的奇異值矩陣處理后重構信號，即可有效抑制測量信號中的噪聲。

對Hankel矩陣H進行奇異值分解，得到對應關系為：

式中，U和V為正交矩陣，而∑為非對角矩陣[6]。此方法的關鍵是恰當地選擇矩陣H的奇異值，將信空間Hs和噪聲空間Hn分開。設Hs的秩為rs，Hn的秩為rn。

假設理想信號s（k）和噪聲n（k）不相關，并且信號空間Hs的最小非零奇異值σsrs大于噪聲空間Hn的最大奇異值σn1，則可以得到以下結果：

其中，H=Hs+Hn。以外積的形式重公式（6）：

可以得到：r＝rs＋rn。

比較式（6）和式（7）可以看出，從∑中選擇恰當的奇異值，便可以將噪聲從信號空間中分離。假設選擇前l（=rs）個奇異值作為估計的理想信號空間，那么H可以被分成估計的理想信號空間，和估計的噪聲空間，形式如下：

確定奇異值選擇方法，進而選擇奇異值個數，然后對奇異值矩陣∑進行處理，∑'為處理后的矩陣；利用U，V和∑'構造新的矩陣

奇異值閾值的選擇在降噪過程中起到了決定性的作用，本文選用特征均值方法，在含噪的Hankel矩陣奇異值分解后，設得到的奇異值為σi，是方陣AAT的特征值λi的平方根，即：

將小于全體特征值均值的特征值置零，可以實現奇異值個數的準確判斷；然后重構矩陣，實現信號的降噪。

1.2.3 Hankel矩陣恢復原理

根據Hankel矩陣的特性，降噪得到的理想信號空間同樣是Hankel矩陣，因此，可以很方便地將對應AP的指紋數據庫恢復[8]。

抽取中每一條副對角線的平均值s來重建所需要的信號序列s（k），s（k）可以表示如下，n為矩陣的列數：

對所有AP的信號向量，可以得到所估計的信號向量（i=1，2，...，M，M為矩陣行數），最后，將所有的按照順序排列，即可得到降噪后的指紋數據庫：

通過對每個Hankel矩陣中副對角線上的元素取平均值來減小誤差，完成了利用Hankel矩陣奇異值分解來對指紋數據庫進行的降噪處理。

2 Sage-husa AKF的應用

2.1 自適應濾波技術

在本項目中，室內是一個動態變化的系統。為了將新指紋數據庫與在線RSS進行比對，在收集信號時對于RSS信號的噪聲過濾尤為重要。

由于在大多數實際系統中，系統過程噪聲方差矩陣Q和量測誤差方差陣R無法預知，量測矩陣H和狀態轉移矩陣也難以確立。如果建立的模型與實際模型有出入，則會引起濾波發散。自適應濾波方法可以有效解決濾波發散，使用量測值對預測值進行修正，也對不確定系統模型中的參數和噪聲統計參數進行估計修正。在線算法中AKF的使用如圖1所示。

圖1 在線算法中AKF的使用

自適應濾波是一種最佳濾波算法，在維納濾波、普通卡爾曼濾波的基礎上發展出了更強的適應性和更好的濾波效果，在實際應用中，尤其是在信息處理方面，得到了較好的發展[9]。

2.2 自適應卡爾曼濾波

關于自適應卡爾曼濾波，目前，使用較多的一種方法是Sage-Husa自適應濾波算法。該濾波方法在使用量測數據進行遞推時，通過時變噪聲估計估值器，實時估計和修正系統噪聲和量測噪聲的統計特性，從而修正系統模型誤差，并且在一定程度上抑制濾波發散現象。現假設線性離散系統數學模型為：

其中，Xk為系統狀態向量，Φk|k－1為系統狀態轉移矩陣，Γ為系統噪聲矩陣，Wk為系統噪聲向量，Zk為系統觀測向量，Vk為量測噪聲向量。

基于數學模型設計的sage-husa自適應濾波算法如下：

其中，式（13—14）對應預測部分，對狀態量X和伴隨協方差P進行預測，得到X'和P'。

式（15）為自適應卡爾曼濾波引入的一個超參數，調節更新參量dk，b被稱為遺忘因子，取值在0.95～0.99之間。式（16—19）對應更新部分的增益系數K求導部分，主要區別在于觀測誤差R基于dk幀數k變化，Rk→Rk－1，即觀測誤差R趨向穩定。

式（20—21）對應更新部分的狀態量更新部分需要注意的是，如果系統狀態變量的維數比較高，而Sage-Husa AKF中又增加了對系統噪聲統計特性的計算，計算量將大大增加，實時性也將難以得到保證。對于階次較高的系Sage-Husa自適應濾波算法中Rk和Qk的在線估計，有時會由于計算發散失去半正定性和正定性而出現濾波發散現象，此時，Sage-Husa自適應濾波算法的穩定性和收斂性不能完全保證。

3 基于方差改進的WKNN算法

3.1 基于歐式距離的WKNN算法的局限

在使用歐氏距離進行相似性計算時，RSS信號的強度反映了物理距離的遠近，理想情況下為物理位置越接近的點，RSS之間的差值就越小。由于室內是一個動態變化的系統，采樣點上采集到的RSS會有一定程度的波動，而對發射信號功率穩定性差的AP，波動尤為明顯。在實際情況中，信號強度的差值不一定完全由物理位置的遠近造成，也可能由AP自身的波動造成，使得歐氏距離為近鄰算法的權重時并不能真實反映實際的物理距離。因而需要對在基于歐式距離的近鄰算法進行改進[10]。

3.2 改進WKNN算法

與傳統的WKNN算法相比，改進的WKNN算法在離線階段對多次測得的信號強度取方差，方差反映樣體數據分布的離散程度，方差大的采樣點，RSS的波動越大，樣本集中的樣本點與均值差異較大的可能性也越高；方差小的采樣點，RSS的分布越集中，任意時刻的信號強度都不會脫離均值太遠。將方差的倒數作為系數加人到距離的計算中，降低方差大AP的接收信號強度在距離計算時所占的權重，使用加權歐氏距離進行相似性計算時，能在一定程度上消除部分RSS波動帶來的影響，提高最終的定位精度。

3.2.1 方差特征的提取

在離線階段建立指紋庫時，為了使指紋庫中每個采樣點的特征更為真實地反映對應物理位置的RSS特征，會在每個采樣點上進行多次的樣本采集。每個采樣點接收到每個AP的信號強度都是一個樣本集，包含在該點多次采集的信號強度。如采樣點j接收到第t個AP的信號強度信息集為：

其中，Z為每個采樣點的樣體量。指紋庫中任意采樣點j的RSS向量為：

其中，N為AP的個數。由此，得到接收信號強度rssj和接收信號方差σ j的向量：

3.2.2 加權距離的計算

加權歐氏距離是針對簡單歐氏距離缺點的一種改進方案，相當于為n維向量的不同維度賦予了不同權重，權重與該采樣點RSS的方差相關，使用加權距離計算待定位點i與采樣點j的距離dij：

4 仿真結果

本團隊模擬了一間30×30 m的房間，在房間的4個頂角模擬4個AP，并選取957個RP，相鄰RP之間的距離為1 m。使用的室內信道傳播模型和RP測得的RSS值分別表示如下：

其中，lossij表示第i個AP到第j個RP的功率損耗，disij表示第i個AP與第j個RP之間的距離，i=1,…,4，j=1,…,957。PL(d0)是在參考點d0處的功率損耗，本文中d0為2 m。Gr和Gr分別是發送天線增益和接收天線增益，Gt＝Gr＝1。是自由空間，c是光速，f是載波頻率，f＝2.4×109Hz。n是信道衰減因子，其范圍在2～5之間，n＝2。rssij表示在第j個RP測得的第i個AP的RSS值，PAP表示AP發射功率，如無特別說明，PAP＝30 dBm，noise是均值為0、方差為0.1的高斯白噪聲。

在離線階段，基于式（28—29）在所有RP處多次模擬接收來自所有AP的RSS值，對模擬結果取平均值，構建指紋數據庫，供在線階段使用。在在線階段，測試點測得的RSS值由同樣的模型模擬產生。

本團隊使用兩種方法來評估定位精度：

（1）使用測試點的位置估計與其實際位置之間距離的均方根誤差（RMSE，單位：m）來評估：

（2）使用定位誤差的概率分布來評估。

在仿真的離線階段，根據模擬的初始指紋數據庫構建Hankel矩陣，通過僅一個奇異值分解，就可以設置適當的奇異值閾值，將信號空間與噪聲空間區分開，以此過濾掉部分噪聲。利用不同的奇異值選擇方法對兩個空間的奇異值矩陣處理后，重構信號組成指紋數據庫。

降噪后，將降噪前后的RSS值進行對比。通過離線階段的信號空間分解，可以為在線階段信號位置的比對提供更加精準的信號定位點，受噪聲的干擾較小，相比較只在在線階段進行過濾降噪的方法有了更進一步的突破。

標準KF算法、Sage-Husa AKF算法的降噪效果對比如圖2所示，其中，橫坐標為算法的迭代次數，縱坐標是每一次迭代運算之后獲得的降噪后的RSS數值。

可以看出，標準KF算法的迭代過程不收斂，偏差原RSS測量值較大。本文Sage-Husa AKF算法相較于標準KF算法更加接近RSS測量值，但在某些時刻的迭代過程中，RSS波動較大，會偏離RSS測量值，也驗證了其缺點所在。標準KF算法過于簡單，在降噪的過程中無法適應信號和噪聲的統計特性，Sage-Husa AKF算法在標準KF算法的基礎上加入遺忘因子b以及噪聲協方差估計，利用前一時刻的降噪輸出結果，調節現時刻濾波參數，相較于標準KF算法能更好地適應信號與噪聲的統計特性。不降噪時與Sage-Husa AKF算法降噪定位性能RMSE的對比結果如表1所示。

表1 降噪方法使用效果

圖2 標準KF算法與Sage-Husa AKF算法

為了驗證改進WKNN算法對定位效果的提高作用，對所有測試點的定位誤差進行統計，定位誤差累積分布函數如圖3所示。累積分布函數能描述變量的概率分布情況，表示變量小于或等于某個數指的概率，定位誤差累積分布曲線上的點表示定位誤差小于x的概率。

圖3 一般WKNN與改進WKNN定位效果對比

可以看出，基于加權距離的改進WKNN算法的定位效果優于一般的WKNN算法。

仿真時采樣點單次測量的信號強度標準差設置為在一個略大范圍內隨機提取，由此模擬AP信號不穩定的情況。從仿真結果的分布上看，改進的WKNN算法的誤差集中在1～2.5 m的區間，幾乎沒有3 m以上的誤差，相較于對同一仿真數據所使用的一般WKNN算法，本論文提出的改進WKNN算法有較為明顯的提升。由此可以得出，當使用的AP信號較不穩定時，基于加權距離的改進WKNN算法的定位效果優于一般的WKNN算法。

5 結語

由于在室內環境中受到的環境影響因素較復雜，在建立指紋書庫過程中難以避免地會引入許多噪聲信號。本文在研究室內定位技術的過程中，提出了基于Hankel矩陣的降噪方法，關鍵部分是分為離線階段和在線階段，通過兩部分不同的功能來進行去噪。在離線階段，主要任務是利用Hankel矩陣構建一個指紋識別數據庫，是指紋識別方法的基礎，因為保留了信號空間和位置空間之間的映射。在在線階段，用戶終端感測RSS，并進一步將其與指紋數據庫的信號空間匹配，以估計用戶位置。在線階段使用sage-husa AKF進行濾波后，使用改進WKNN算法提高定位精度。