眾包室內定位系統中基于多維尺度變換的接收信號強度平滑理論

張立曄，王 壯，房 超，孟曉亮，田愛奎

(山東理工大學計算機科學與技術學院，淄博 255000)

定位與導航服務在人們的日常生活中發揮著舉足輕重的作用。近年來，隨著移動終端和無線局域網(wireless local area network，WLAN)的普及，在移動終端實現基于位置的服務(location based service，LBS)已經逐漸改變了人們的生活和工作方式。越來越多的應用程序開始利用位置信息為用戶提供服務，其中既有如E911的傳統救援服務，也包含以智慧城市和物聯網為代表的全新應用領域[1-3]。為了獲取用戶的位置信息，眾多定位系統已經完成部署。在戶外，以中國北斗定位系統和美國全球定位系統(global positioning system,GPS)為代表的衛星定位系統已經可以為用戶提供精確的位置信息。然而，由于樓體的遮擋，衛星信號接收設備不能在室內和衛星被高樓阻擋的地區使用。因此，人們提出了多種室內定位解決方案用于替代衛星定位系統。

基于Wi-Fi的WLAN技術經過多年的研究，已廣泛部署在校園、機場、商場等公共場所，WLAN技術的普及為使用WiFi信號進行位置估計創造了機會。由于在公共區域中的所有可見接入點(access points,APs)都可以利用移動終端查看，并且移動終端還可以測量每個AP的接收信號強度(received signal strength,RSS)，因此利用Wi-Fi的RSS進行用戶位置估計成為常用的方法之一[4]。

基于RSS的位置指紋定位方法分為兩個階段：離線訓練階段和在線定位階段[5]。在離線訓練階段，在室內空間中設置大量參考點(reference point,RP)，并在參考點上采集來自所有AP的RSS數據，將RSS值與對應RP的位置空間坐標組成位置指紋數據庫radio map，radio map是位置指紋技術的基礎，其保存了信號空間到位置空間的映射。在在線階段，用戶利用移動終端采集所有AP的RSS值，并將用戶接收到的RSS值與radio map中的RSS信號空間進行匹配，進而得出用戶的當前位置[6-7]。

近年來，眾包技術以其出色的表現引起了室內定位領域的關注[7-8]。在眾包技術中，radio map不再由專業人員建立，而是將復雜煩瑣的工作化整為零，由眾多志愿者分別采集數據匯總而成。眾包技術大大減少了技術人員在訓練階段收集的RSS值的數量。當志愿者在進行日常活動時，移動終端采集各種傳感器數據用于建立radio map，例如，加速度計數據可用于計算兩次RSS采樣之間的相對位移；磁力計或陀螺儀用于測量方位變化等。最后，這些眾包數據經過處理之后組合在一起，構成無radio map。

為了更加規范地進行數據采集，技術人員在室內的設置起點和終點，手持移動終端從起點移動到終點，在移動過程中采集RSS數據和傳感器數據。利用加速度計和陀螺儀等傳感器計算兩個連續RSS樣本之間的相對位移，每一個采集RSS數據的位置即為參考點(reference point,RP)。通過同時收集RSS值和傳感器數據，可以快速構建無線電地圖。

在上述數據采集方法中，在每個RP上只能采集一個RSS數據，考慮到RSS值會受到噪聲和信道衰落的影響，單個RSS數據很難準確反映該位置的實際的RSS分布。為了消除噪聲對radio map的影響，中外專家學者提出了多種噪聲抑制算法。文獻[9]提出了相關時間窗濾波(sliding correlation time window,SCTW)算法對radio map進行平滑，在采集數據時，利用一段時間內采集的RSS數據對實時采集的RSS數據進行濾波，從而消除RSS數據的波動。文獻[10]提出了一種基于Hankel矩陣的radio map噪聲消除算法，該算法從radio map中提取不同AP對應的信號向量來構造Hankel矩陣，對Hankel矩陣進行求解從而實現信號和噪聲的分離。文獻[11]提出利用輕量級深度學習算法在基于信道狀態信息的室內定位系統中實現噪聲消除和降維，本算法對批量數據點多項式回歸，從而濾除噪聲。文獻[12]提出在同一RP上采集不同AP的RSS值，并計算不同AP的RSS值的差值，并將該差值與原始RSS數據融合作為指紋特征生成radio map，最后利用神經網絡算法進行用戶位置的解算。文獻[13]提出了WiDeep系統，該系統結合了堆疊式去噪自編碼器深度學習模型和概率框架來處理接收到的WiFi信號中的噪聲，同時得到RSS數據與相應RP位置之間的關系。文獻[14]提出了一種基于稀疏表示和低秩矩陣恢復的無線電地圖更新方法，該算法將RSS矩陣的低秩特性和稀疏先驗結合起來，處理指紋缺失和稀疏噪聲。從以上算法可以看出，現階段研究主要利用radio map中的部分數據之間的相關性實現對噪聲的抑制，而其他數據的信息被忽略了，因此無法實現最優的噪聲抑制效果。

受到這些算法的啟發，現研究一種多維尺度變換(multidimensional scaling,MDS)算法，對離線階段利用眾包技術采集的RSS值進行平滑處理。MDS算法是在一組數據對象上分析其相似性或非相似性的一種技術。在MDS算法中，由于APs和RPs的位置固定，在不同RPs處采集的RSS值具有內在關系，用相似矩陣表示[15-17]。基于信號傳播模型，考慮APs和RPs位置，可以計算得到在兩個RPs上采集的RSS數據的相似性距離。在離線訓練階段，利用MDS算法和相似度矩陣能夠降低噪聲和測量誤差對RSS數據的影響，從而實現對radio map的平滑處理，最終提高定位精度。

1 問題分析

考慮典型的Wi-Fi室內定位場景，其中用戶攜帶一個裝有Wi-Fi適配器的移動設備，在室內環境中從Wi-Fi AP采集RSS數據。在離線訓練階段，實驗人員在n個參考點上采集來自m個AP的RSS值，所有RSS數據與其對應的坐標信息構建成一個radio map。第i指紋(ri,ci)是由一個m×1維的RSS向量ri和相對應的坐標ci組成，其中ri為在第i個RP采集的來自m個AP的RSS值，第i個RP的坐標ci=(xi,yi)T。在傳統的Wi-Fi定位方法中，通常會在每一個RP采集數百個RSS數據，并計算這些RSS數據的平均值，利用該平均值最終得到無線電地圖。無線電地圖可以用矩陣形式表示為

(1)

式(1)中：rij為在第i個RP上采集的來自第j個AP的RSS平均值。在在線定位階段，用戶利用移動設備在某未知位置Sj處采集來自AP的RSS值rj，然后通過比較rj與radio map中的RSS數據來估計用戶所處的位置。在基本的定位理論中，如果所采集的rj與radio map中的ri相似，則認為用戶的位置Sj必定靠近Si。

眾包定位系統存在的一個問題是在離線訓練階段和在線定位階段會有大量不同品牌不同型號的移動終端在定位系統中運行。由于不同移動終端設備中配置的Wi-Fi信號接收器不同，而對于同一個AP，不同Wi-Fi信號接收器接收到的RSS強度有較大差別，從而得到不同的數據分布。大量研究表明，由于硬件的差異，不同設備采集的RSS差異甚至超過25 dBm[18-19]。因此，由于不同設備采集的RSS數據波動較大，造成定位系統的定位精度大大降低。針對上述問題，在文獻[20]中提出了基于線性回歸(linear regression，LR)算法的設備多樣性消除算法，該算法解決了設備多樣性問題，在離線訓練階段和在線定位階段都得到了具有一致性的RSS數據。

室內定位的另一個問題是移動設備在室內環境中采集的RSS值波動較大。首先，RSS數據會受到多種噪聲源的影響，例如路徑損耗、多徑和陰影；第二，AP的發射功率會隨著時間的不同而不同；第三，對于所有可用的AP，移動設備可能無法掃描整個頻譜采集RSS數據。因此，用來建立radio map的RSS數據必然包含大量環境噪聲和測量誤差。為了說明這一點，從多倫多大學Bahen大樓的某個位置采集了100個RSS值，并在圖1中繪制了直方圖。如圖1所示，雖然利用同一設備在同一位置采集來自同一個AP的這些RSS數據，但是所采集的RSS數據的功率分布在-70～-50 dBm的較大區間內。

圖2所示為Bahen大樓4樓走廊的RSS數據分布(不包括異常值-110 dBm)。在圖2中，每一個色塊代表在該RP上采集的來自某一AP的RSS值，為了便于顯示該值，對所有RSS值加110，使所有RSS值都大于0 dBm，取值范圍變為(0～110 dBm)，而顏色越偏紅色代表RSS值越大，顏色越偏藍色代表RSS值越小，后續radio map分布都遵從該范圍。因此圖中顯示的RSS值范圍從圖2中可以看出，雖然在整個走廊中，RSS數據的信號分布在一定程度上符合信號傳播模型，但是RSS數據在某些位置卻有較大的差異。利用這種包含大量波動的RSS數據進行定位會導致較大的位置估計誤差。

圖2 多倫多大學Bahen樓4樓走廊某AP的信號分布Fig.2 Signal distribution in corridor of 4th floor of Bahen building at University of Toronto

如上所述，可以得到室內定位系統中一個關鍵的挑戰：如何處理眾包定位系統采集的RSS數據，使其更接近理論值？采用MDS算法來抑制RSS值的波動，從而得到更加平滑的radio map。

定義D為AP與RP之間距離的矩陣，表達式為

D=[d(Si,APk)]n×m

(2)

式(2)中：d(Si,APk)為參考點Si與接入點APk之間的歐氏距離，即

d(Si,APk)=‖ci-cAPk‖2

(3)

式(3)中：cAPk為第k個AP的坐標。

定義R=[r(Si,Sj)]n×n為在參考點Si和Sj上采集的RSS數據的相似性矩陣，值得注意的是，RPs與參考點Si和Sj之間的相對RSS值與歐氏距離有關，公式為

r(Si,Sj)≈F[d(Si,APk)]

(4)

式(4)中：F為室內環境中的電磁波傳播模型。

2 基于MDS算法的RSS平滑理論

如前文所述，利用眾包技術獲得的RSS數據是在室內環境中正常行走時測量得到的，因此建立的radio map中RSS數據包含大量噪聲。利用MDS算法，根據采集點之間的相對距離、已知AP位置和信號傳播模型實現對radio map數據的平滑。

2.1 經典MDS算法

在離線訓練階段構建radio map時，數據空間中所有數據點之間的相似性距離的平方r2(Si,Sj),其中，i,j=1,2,…,n，由式(5)計算得到，即

(5)

然后得到數據空間中的平方相似矩陣為

(6)

在MDS算法中，相對點RSS′由R計算，計算過程如下。

首先，對相似性矩陣進行雙定心處理，表達式為

(7)

給出J的定義為

(8)

用奇異值分解(singular value decomposition,SVD)對B進行分解，即

B=UΛUT

(9)

式(9)中：Λ=diag(λ1,λ2,…,λm)為B的特征值的對角矩陣，λ1≥λ2≥…≥λn≥0；U=[u1,u2,…,un]，為一個正交矩陣，其中每一列是特征值對應的特征向量。

假設需要得到m維的解，用矩陣Λm表示前m個最大特征值，Um表示矩陣U的前m列，則經典尺度變換的坐標矩陣為

(10)

2.2 估計r2(Si,Sj)

為了平滑radio map中的RSS值，需要精確的相似距離矩陣。當在RPSi上采集的RSS值包含噪聲時，使用信號傳播模型來計算相似性距離r(Si,Sj)。如圖3所示，考慮在室內區域中安裝的第k(k=1,2,…,m)個AP。利用文獻[21]中的CS方法可以精確地估計AP的位置cAP，因此將其位置視為已知。利用文獻[22]中的室內信號傳播模型來模擬無線信號在環境中的傳播。

圖3 一個AP的典型Wi-Fi網絡Fig.3 A typical Wi-Fi network with one AP

那么從在位置Si處接收到的來自第k(k=1,2,…,m)個AP的RSS值，可以表示為

(11)

式(11)中：dik為第k個AP與測量位置之間的距離；P為AP的傳輸功率；αi為環境中的傳播損耗指數；hjk為包含路徑損耗、衰落和陰影的衰減。

使用式(11)的模型和文獻[15]的方法，可以得到

(12)

定義r(Si,Sj)為在位置Si和Sj上采集的來自所有AP的RSS值的差值矩陣。r(Si,Sj)的第k個元素為在位置Si和Sj上采集的來自第k個AP的RSS值的差值，可以表示為

rk(Si,Sj)=rik-rjk

(13)

r(Si,Sj)的歐氏距離范數可以寫為

(14)

r(Si,Sj)的歐氏距離范數可以寫為

(15)

2.3 MDS算法的應用

在室內區域的n個RP上采集來自m個AP的RSS值，得到一個n×m階的radio map。由于在RSS矩陣RSS中，含有噪聲的RSS值是未知的，因此假設在RPSi上采集的RSS值ri是含有噪聲的，利用MDS算法，基于坐標矩陣C和RSS矩陣中除ri之外的RSS值可以實現對ri平滑。利用該方法，其余RP上的RSS值可以一一實現平滑處理。radio map可以通過以下步驟進行平滑。

步驟1利用式(14)計算RPSi與其他RPs在數據空間中的相似距離。其余的相似距離由RSS值計算，最終，MDS算法所需的相似性距離矩陣由這兩部分相似距離組成。

步驟2對距離矩陣應用MDS，保留前m個最大的特征值和特征向量，構建m維相對RSS矩陣。

步驟3利用線性變換(可能包括縮放、旋轉和反射)，基于除ri外的矩陣RSS將相對RSS矩陣轉換為絕對RSS矩陣。

3 實驗結果與分析

利用仿真和實驗對基于MDS算法的RSS平滑進行了驗證。離線訓練階段，利用移動終端在多倫多大學Bahen中心4樓采集RSS數據和傳感器數據，然后利用傳感器數據和計步算法自動計算RPs的坐標。在實驗過程中，由于在每個RP只采集5個RSS值，結合計算得到的與RSS值對應的坐標，在30 min內構建了一個radio map。在線定位階段，實驗人員手持移動終端從房間4000(圖4的頂部)移動到房間4148(圖4的底部)，在該路徑上共收集到35個測試點的序列。

圖4 測試點實際位置Fig.4 Actual locations of Test Points

由于室內環境的復雜性，在不同區域的衰減是不同的。因此，在室內環境的不同位置采用不同的傳播損耗指數α值，以獲得更好的定位結果。當AP在RP的視線范圍內時，設α=3.5。當RP位于角落附近時，設置α=1.5來模擬由墻壁反射造成的信號衰減的減小。當從AP到RP中間有遮擋，即不在視線范圍時，設α=5，同時，如果信號傳播路徑中有更多障礙物時，該值會繼續增大。

如圖5(a)所示，盡管AP在室內環境中RSS的信號分布值與信號傳播模型基本一致，但是大量的噪聲和測量誤差使得radio map中某些RP上的RSS值出現劇烈波動。利用原始的radio map，得到如圖6所示的定位結果。可以看到，與圖4中的實際位置相比，定位結果存在明顯的誤差。此外，某些不同的測試點被錯誤地定位到相同的位置。

為了提高定位精度，在離線訓練階段，采用提出的MDS算法平滑接收到的RSS值。圖5(b)為平滑后的radio map信號分布，可以看到，經過MDS算法平滑之后，原始radio map中的RSS數據去除了很多噪聲和測量誤差，得到的radio map更符合室內信號模型。圖6為利用原始radio map進行定位測試得到的定位結果，可以看出，很多不同位置的測試點被錯誤地定位在同一位置。而圖7為利用平滑后的radio map進行定位得到的定位結果，從圖7可以看出，利用平滑之后的radio map進行定位得到的定位精度明顯提高，在圖6中堆積在一起的定位結果被定位在不同位置，并且更接近它們的實際位置。因此，提出的MDS算法能夠提供更高質量的位置服務。

圖5 radio map信號分布比較Fig.5 Comparison of signal distribution of radio map

圖6 利用原始radio map的定位結果Fig.6 Positioning results using original radio map

圖7 利用MDS算法后的定位結果Fig.7 Positioning results using the MDS algorithm

MDS算法定位誤差的累計分布曲線如圖8所示。作為對比，還利用文獻[8]中提出的光滑CHKS函數孿生(smooth twin CHKS support，SCTW)算法對radio map進行平滑，并利用該radio map和原始數據進行了定位測試。由于SCTW方法只使用了少量的無線電地圖RSS值，大部分radio map信息都被舍棄了，因此無法獲得更優的radio map。由于所提出的MDS算法得到了更加精確的radio map，因此與其他方法相比，利用MDS算法進行radio map平滑處理可以得到更高的定位精度，從測試結果可以看出，利用MDS算法對radio map進行平滑使得最大定位誤差由10 m減小到4 m，平均誤差由2.89 m減小到2.11 m。

圖8 定位誤差累計分布函數Fig.8 Cumulative distribution function of Positioning error

4 結論

提出了一種基于MDS算法的RSS平滑方法，在基于指紋的眾包室內定位系統中，由于RPs的固定位置，不同RPs之間的RSS值有內在的關系，利用MDS算法，可以挖掘不同RP上采集的RSS之間的內在關系，從而有效校正有噪聲的RSS值，得到更平滑的radio map。在多倫多大學Bahen中心測試了該方法，實驗結果表明該方法能顯著提高定位精度。