5G超密集網絡下的室內壓縮重構指紋定位算法

賈鵬飛，張月霞,b,c

(北京信息科技大學 a.信息與通信工程學院；b.現代測控技術教育部重點實驗室；c.高動態導航北京市實驗室，北京 100101)

0 引 言

隨著位置服務的興起和廣泛應用，用戶對室內定位的精度提出了更高的要求。而隨著第五代移動通信技術的發展,5G將實現超密集網絡部署[1]，大幅提高基站密度，使用戶可以同時與多個基站進行通信，有利于多基站協作定位，從而使定位精度提高至亞米級，更好地滿足人們對于室內高精度定位的需求。

傳統的室內定位算法[2-5]都是基于測距的定位方法，在5G超密集網絡下其定位精度會受到影響，不能達到較高定位精度要求。而指紋匹配定位算法是預先構建定位所需的指紋庫，再將待定位點的數據通過指紋匹配算法與指紋庫中的數據進行匹對，從而估計待定位點的位置坐標，其定位精度較高。許多學者對指紋匹配定位算法做了大量研究。Horsmanheimo等人[6]設計并實現了一個基于5G的室內定位平臺，采用了精細定時測量技術，可通過多邊計算來計算位置估算值，實現了基于圖像的定位和基于RSSI的指紋識別。文獻[7]提出了一種基于K-means和支持向量機(Support Vector Machines，SVM)的藍牙室內定位算法，利用卡爾曼濾波和K-means算法對收集到的數據進行處理，最后通過SVM模型完成待測數據的分類，算法的定位精度穩定在1.5 m以內。這些指紋匹配算法雖有不錯的定位精度，但其指紋庫數據相對較少，不容易構建。在5G超密集網絡中，參與定位的基站多，所需測量的數據量龐大，因此如何降低指紋庫數據構建的復雜度并提高定位精度成為了當前亟待解決的問題。

本文提出一種5G超密集網絡下的壓縮重構指紋定位算法。該算法首先測量部分指紋庫數據，通過非精確增廣拉格朗日算法(Inexact Augmented Lagrangian Multiplier，IALM)進行矩陣填充，將該指紋庫矩陣重構為完整，然后利用加權K近鄰(Weighted K-Nearest Neighbor，WKNN)算法實現待定位點的在線匹配。

1 超密集網絡室內定位模型

假設5G超密集網絡室內定位模型如圖1所示，基站分布在模型頂部，總個數為N,u為待定位點，分布在空間中任意位置。

圖1 5G超密集網絡室內定位模型

為了給用戶提供更好的服務，提高定位精度，需對基站部署進行劃分。設基站分布滿足齊次泊松點過程[8]，那么基站服務范圍則可以用泰森多邊形(Voronoi diagram)來表征。

設每個基站的通信半徑為r，則基站的密度為

(1)

式中：S為模型頂部面積。根據文獻[9]，基站密度λ>>1 000 cell/km2。

根據齊次泊松點過程，基站的概率分布為

(2)

圖1中頂部基站服務區域分布如圖2所示，橫縱坐標表示平面區域內長和寬，其中每一小格代表10 m，即平面范圍為100 m×100 m，綠點代表基站位置且服從泊松分布，綠色區域表示泰森多邊形覆蓋范圍。

圖2 基站服務區域表征圖

2 指紋匹配算法

2.1 離線建庫階段

2.1.1 指紋庫組成

在室內空間中任意一點其對應的數據為指紋數據庫中的數據點，即指紋。設指紋點共n個，由于n趨于無窮大，在實際采集中獲取所有的指紋數據幾乎不可能，因此，設定指紋點在空間中均勻分布,且每個指紋間存在較小的間距d，這樣就可以將n限定為一個有限的值n′，那么指紋點的集合可以用L={l1,l2,l3,…,ln′}表示。以la點為例，該點坐標為(xa,ya,za)，其指紋表示為

S=[RSSI1a,RSSI2a,RSSI3a,…,RSSINa]T。

(3)

那么離線建立的指紋庫可以表示為一個N×n′的矩陣M：

(4)

2.1.2 矩陣填充算法

設Ω是指紋庫矩陣M的一個子集，Ω中只含有m個元素Mij，Mij為M中觀測到的元素，其中Mij∈M,m<

定義：PΩ為Ω上的投影算子，則有

(5)

PΩ(M)在Ω集合上等于Mij，在Ω的補集上等于0，則矩陣M中的已知元素可以用投影PΩ(M)來表示。在一定約束條件下，矩陣填充問題可以用如下秩函數最小化模型來表示:

min rank(X) s.t.PΩ(X)=PΩ(M)。

(6)

式中：rank(X)表示X的秩，X為填充矩陣。

但式(6)為非凸函數，因此該問題是一個NP-hard問題，求解極為困難。為此Recht等人在文獻[10]中提出用矩陣核范數最小化問題代替式(6)。核范數定義為

(7)

式中：‖X‖*表示X的核范數,σk(X)表示X的第k大奇異值。由于核范數是一個凸函數，因此矩陣填充問題可以轉化為如下最小化問題來求解：

min ‖X‖*s.t.PΩ(X)=PΩ(M) 。

(8)

本文采用ALM[11]算法對該問題進行求解。

將式(8)進行變形為

min ‖X‖*s.t.X+E=M,PΩ(E)=0 。

(9)

式中：E為矩陣X與原始矩陣M間的差,增加約束條件即PΩ(E)=0時，等式PΩ(X)=PΩ(M)成立。該算法的增廣拉格朗日函數為

(10)

式中：μ為增廣拉格朗日函數的懲罰因子，Y為矩陣變量。

ALM算法交替更新X、E、Y、μ,迭代公式如下：

(11)

由于IALM[11]不需要精確求解,只需一次迭代就可以達到較高精確度，故本文采用了IALM算法進行矩陣填充應用，其算法偽代碼如下：

1 給定觀測矩陣之PΩ(M),Y=0,E=0,k=0

2 while不收斂

4Xk+1=USμk-1[S]VT

6Yk+1=Yk+μk(M-Xk+1-Ek+1)

7μk+1=ρμk+1

8k=k+1

9 end

輸出：Xx+2

2.2 在線匹配階段

本文采用卡方距離計算待定位點與參考指紋點的相似度，并對其進行加權處理，采用加權K近鄰(Weighted K-nearest Neighbor,WKNN)算法[12]對待定位點進行指紋匹配。

Step1 計算待定位點與指紋庫中參考點間的卡方距離dj:

(12)

式中：RSSIij是第j個參考指紋點的第i個RSSI值，RSSIj是待定位點的第j個RSSI值。

Step3 對集合D中的K個距離進行加權處理，得到相應的加權系數ωi：

(13)

式中：δ是一個較小的正數，是為了避免分母為0。

(14)

式中：(xi,yi,zi)是對應參考點的指紋位置坐標。

3 仿真分析

RSSI=P+gain-loss-noise。

(15)

式中：P表示基站信號發送功率，gain表示信道增益，loss表示路徑損耗，noise表示高斯白噪聲。

3.1 指紋庫矩陣填充誤差分析

在指紋庫的構建中，先通過常規方法得到原始指紋庫M,然后對M進行隨機采樣60%的數據用以恢復剩余40%的數據以得到重構后的指紋庫X。

由于指紋庫數據過大，僅提供指紋點的1～7號指紋數據進行數據對比。原矩陣中的指紋數據如表1所示，重構指紋庫數據如表2所示，重構矩陣與原矩陣中數據的絕對誤差如表3所示。

表1 原指紋矩陣數據表

表2 重構指紋矩陣數據表

表3 誤差矩陣數據表

由表3可知，重構矩陣與原始矩陣間存在一定誤差，根據全部矩陣數據間的對比計算可得其平均誤差為1.13%，說明IALM算法可以很好地恢復原始矩陣。

3.2 定位誤差分析

設信噪比為10 dB,使用WKNN算法進行指紋匹配定位，得到如圖3所示定位結果。由圖可看出，本文算法定位結果與真實位置高度重合，具有較高的精確度。

圖3 三維定位結果圖

本文定位算法與傳統KNN算法平均誤差對比如圖4所示，可以看出，本文指紋定位匹配算法隨信噪比的增加，平均誤差呈遞減趨勢，整體定位誤差要小于傳統指紋匹配算法，且在信噪比為10 dB時達到誤差最小(0.200 8 m)，證明該算法具有良好的定位精確度。

圖4 平均誤差對比分析圖

4 結 論

本文提出的5G超密集網絡室內壓縮重構定位算法，首先構建部分指紋庫數據，然后通過矩陣填充IALM算法重構出完整指紋數據庫，在誤差為1.13%的情況下節約了40%的工作量。仿真實驗表明，本文提出的指紋定位算法相較于傳統指紋KNN匹配算法減少了指紋庫構建采集的工作量，且定位結果更好，在10 dB信噪比時誤差達到最小，為0.200 8 m。