基于LANDMARC與壓縮感知的雙段式室內定位算法

李麗娜馬俊②龍躍徐攀峰

?

基于LANDMARC與壓縮感知的雙段式室內定位算法

李麗娜①馬 俊①②龍 躍*①徐攀峰①

①(遼寧大學物理學院 沈陽 110036),②(國網山東省電力公司電力科學研究院 濟南 250002)

鑒于已有室內定位算法定位精度與運算效率之間的矛盾，該文提出一種將LANDMARC區域定位與基于模擬退火優化正則化正交匹配追蹤(SROMP)的壓縮感知位置估計相結合的雙段式定位算法(LANDMARC- SROMP CS)。首先，利用LANDMARC定位算法快速鎖定目標所在區域范圍；在鎖定的區域內，再引入壓縮感知理論實現目標位置估計。此部分，首先根據鎖定區域范圍建立虛擬參考標簽；然后由新型組合核函數相關向量機算法訓練得到室內傳播損耗模型，計算獲得虛擬標簽處接收信號強度值，構建測量矩陣；最后利用SROMP壓縮感知重構算法求解出目標的位置索引矩陣，對索引矩陣中的位置相關點加權平均得到目標的位置信息。實驗結果表明，所提定位算法平均定位誤差為0.6445 m，算法運算效率相對較高，可以較好地滿足室內定位的要求。

室內定位；壓縮感知；模擬退火；正則化正交匹配追蹤；相關向量機

1 引言

隨著物聯網技術的發展及普及，對室內基于位置感知服務的需求越來越大，室內定位技術成為近年來的研究熱點。其中，基于接收信號強度指示(Received Signal Strength Indication, RSSI)的無線測距定位技術因其檢測機制簡單、硬件成本低、實現容易等，已經成為了室內定位技術中的主流方法[1]。但在已有的基于RSSI的室內定位算法中普遍存在定位精度及計算效率之間的矛盾，有待進一步研究。如應用極為廣泛的LANDMARC算法計算量小[2]，但定位精度有限，位置指紋法定位精度高，但離線位置指紋數據采集工作量較大，算法實現效率低。近年來，有學者嘗試將壓縮感知(Compressive Sensing, CS)應用于室內定位領域[3]，如文獻[4]利用壓縮感知思想，將定位表達為一個稀疏信號的重構問題，獲得了較高的定位精度。但現有測量矩陣多采用實體標簽的RSSI值進行構建，定位區域較大時，測量矩陣構建效率較低；另一方面，最常用的正交匹配追蹤(Orthogonal Matching Pursuit, OMP)重構算法計算量較小，但抗噪性較差，在復雜室內環境中定位精度不夠理想。鑒于以上，將LANDMARC算法與基于模擬退火優化正則化正交匹配追蹤(Regularized Orthogonal Matching Pursuit optimized by Simulated annealing, SROMP)的壓縮感知位置估計算法相結合，設計一種雙段式室內定位算法(文中以LANDMARC-SROMP CS表示)。并結合仿真及實驗研究對算法的可行性進行了驗證。

2 LANDMARC-SROMP CS雙段式定位算法流程

基于LANDMARC與壓縮感知的雙段式定位算法主要包括區域定位和位置估計兩個階段。區域定位階段，采用LANDMARC快速鎖定待定位標簽可能出現的區域地址，得到索引集。位置估計階段，在鎖定區域內，利用傳播損耗模型構造測量矩陣，再利用改進的SROMP壓縮感知重構算法求解目標位置。其中傳播損耗模型采用改進相關向量機(Relevance Vector Machine, RVM)算法在離線階段訓練得到。算法流程如圖1。

圖1 LANDMARC-SROMP CS雙段式室內定位算法流程圖

3 LANDMARC-SROMP CS雙段式定位算法原理及實現

3.1 基于LANDMARC的區域定位

3.2 測量矩陣構建

為實現待定位目標的位置估計，需先進行測量矩陣的構建。采用虛擬標簽的RSSI值填充測量矩陣。虛擬標簽RSSI值的填充要滿足無線信號傳播損耗模型(又稱經驗模型)[6]：

式中，為射頻標簽與閱讀器的實際物理距離，為預設參考距離，為預設距離處的RSSI值，為路徑損耗因子，為環境因子，為距離處的RSSI值。由于室內多徑效應、硬件穩定性等因素影響，導致經驗模型環境適應性較差，為此，本文提出一種新型的組合核函數相關向量機(Relevance Vector Machine, RVM)模型訓練算法用于室內傳播損耗模型的訓練。設定位區域內隨機布置的標簽與閱讀器的距離為,為其對應的RSSI值，則RVM模型訓練算法可描述為[7]

高斯核函數學習能力較強，泛化性能較弱；而樣條核函數恰好相反。該組合核函數在最大限度地保留學習能力的同時提高其泛化性能。并且，用拉普拉斯核函數代替傳統組合核函數中的調節因子，進一步提高了核函數的學習能力。經驗證，該組合核函數滿足組合核函數構建的異構條件[8]。RVM算法的核函數不需要滿足Mercer準則[9]，降低了核函數選擇的復雜程度。訓練時，設T互相獨立，且來自模型：

3.3 基于壓縮感知的位置估計原理

壓縮感知重構算法進行位置估計是通過構造和求解式(16)所示的欠定方程[12]：

式中，為閱讀器的個數，為參考標簽的個數，且>>，即式(16)為欠定的，無法直接求解，需通過壓縮感知重構算法解決此問題，并利用最小二乘法的矩陣思想計算的估計[13]：

3.4 SROMP壓縮感知重構算法

為進一步提高定位精度，本文提出一種基于模擬退火算法改進ROMP的SROMP壓縮感知重構算法。文獻[14]指出，多數情況下在迭代參數為原信號稀疏度的情況下重構結果最好，但對于定位問題，若指定位置稀疏度為1，易造成位置誤判。模擬退火算法復雜度低，且考慮到其在全局優化中的特殊優勢，采用模擬退火對迭代參數進行優化。將ROMP每一次迭代的重構誤差作為模擬退火搜索區間內的函數，根據測量矩陣的規模設置搜索區間上限，下限為1，將區間的最大值作為模擬退火的初始溫度，設定退火因子為整數變量，其值越小退火過程越平緩，根據Metropolis準則[15]，判定新解是否滿足轉移概率。SROMP算法的流程如下：

步驟 4 執行一次退火產生新的稀疏因子。

步驟 5 重復步驟1~步驟4至滿足終止條件，即殘差足夠小。

4 仿真與實驗

4.1 傳播損耗模型訓練實驗

圖2 SVM模型訓練效果圖

圖3 高斯核RVM損耗模型訓練效果圖

圖4 組合核RVM模型訓練效果圖

表1 模型訓練結果與樣本偏差統計表(dB)

4.2 定位算法仿真

定位實驗前，為驗證本文算法在室內定位中的可行性，在主頻分別為3.40 GHz和3.39 GHz的Intel i3 雙核CPU及1.86 GB內存的PC機上利用Matlab軟件進行定位仿真實驗。仿真布局如圖5所示，采用4個閱讀器與9個參考標簽布置為33的參考標簽陣列。

圖5 定位仿真布局圖

采用式(4)的經驗對數傳播損耗模型，令0=2,(0)=-15,=2，模擬實驗室環境建立傳播損耗模型，以坐標為(2.3, 2.3), (5,4)的點A, B為待定位目標，區域鎖定因子設為3。算法初始化，設定模擬退火的初始溫度0=48，退火因子=1，初始稀疏因子0=1。用本文LANDMARC-SROMP CS雙段式定位算法進行仿真定位。LANDMARC區域定位結果如圖6。

圖7 目標定位仿真效果圖

4.3 定位實驗評估

在與仿真實驗相同配置的PC機上，利用LabVIEW調用Matlab軟件進行定位實驗。取6 m6 m區域搭建定位系統，布局與圖5仿真實驗相同。令LANDMARC算法的最近鄰居值=3，并分別對傳統壓縮感知算法與本文雙段式定位算法進行初始化。設置初始殘差為4臺閱讀器檢測到的待定位目標的RSSI值；索引集置為空集。為本文算法設置初始溫度0=48，退火因子=1，初始稀疏因子=1。首先，針對11個目標點分別采用以上算法進行50次單目標定位實驗，隨機選取的定位結果及分析如圖8、圖9及表2。

圖8 單目標定位實驗結果

圖9 平均定位誤差曲線圖

表2 定位誤差及平均計算時間分析統計表

圖8表明，本文算法在各點的定位效果具有明顯優勢。由圖9分析可知，本文算法具有更高的定位精度和更好的穩定性，且不存在“過學習”的現象。基于傳統OMP的壓縮感知定位算法(以OMP CS表示)整體的定位精度優于LANDMARC算法，但兩者的誤差曲線均具有較大的波動，穩定性較差。由表2可知，本文提出的LANDMARC-SROMP CS雙段式定位算法的平均計算時間僅比LANDMARC算法略長，但卻明顯少于傳統OMP CS定位算法，即時間復雜度有明顯下降；并且其在定位精度方面具有明顯的優勢，很好地平衡了定位精度和定位效率之間的矛盾。

為了進一步驗證本文算法的可行性，其他條件不變，將本文算法用于多目標定位實驗。實驗時待定位目標手持有源RFID電子標簽并保持與實驗臺上放置的參考標簽處于同一水平面，隨機選取4個目標點A, B, C, D進行多目標定位實驗，4臺閱讀器檢測到的待定位目標及參考標簽的RSSI值等相關信息由同一無線路由器發送至上位機進行定位，定位場景如圖10所示。

圖10 多目標定位實驗場景圖

對A, B, C, D 4個待定位目標進行30次多目標定位實驗，隨機選取10次定位結果如圖11所示。可見，各目標的定位結果較集中分布在目標區域范圍內，但由于硬件靈敏度受到限制，且標簽間存在一定程度的干擾，故多目標定位的定位精度較單目標定位整體稍有下降，每次定位的結果稍有差別。

圖11 多目標定位實驗結果

表3 多目標定位誤差分析表(m)

由表3可以看出，本文算法用于多目標定位，最大誤差基本控制在2 m以內，其平均定位誤差可達1 m左右，滿足室內定位的精度要求；各目標位置處定位誤差接近，說明本文算法在定位區域的不同位置定位效果基本相同，具有較強的抗干擾性能。經測定，本文算法4個目標單次定位的平均運算時間為0.8931 s，可以滿足一般情況下對實時性要求不是特別嚴苛的多目標室內定位需求。

5 結束語

本文在分析了已有的基于場景分析的RSSI定位方法不足的基礎上，提出了一種基于LANDMARC區域定位與SROMP壓縮感知位置估計相結合的雙段式定位算法(LANDMARC- SROMP CS)，仿真及實驗結果顯示，本文定位算法較好地兼顧了定位精度及定位效率的兩方面的優勢，并獲得了較好的定位穩定性；同時，本文采用壓縮感知及虛擬標簽的思想，大大節省了硬件成本。但在對多目標進行定位時，基于SROMP壓縮感知的位置估計階段需要對多目標逐個求解，運算時間較長，有待進一步突破。另外，因射頻信號的時變特性使得本文算法定位結果的穩定性方面尚待進一步研究。

[1] YANG Ting and ZHU Liping. A review of modern indoor localization systems[C]. Proceedings of the 2nd National Conference on Information Technology and Computer Science, Shanghai, 2015: 10-11.

[2] WU Ling, and HUANG Liya. Improvement of location methods based on RFID[J]., 2013, 20(6): 36-41.

[3] LI Chengtie, WANG Jinkuan, and HAN Yinghua. An efficient compressed sensing-based cross-layer congestion control scheme for wireless sensor networks[C]. Proceedings of IEEE 26th Chinese Control and Decision conference, Shanghai, 2014: 5-6.

[4] 何風行, 余志軍, 劉海濤. 基于壓縮感知的無線傳感器網絡多目標定位算法[J]. 電子與信息學報, 2012, 34(3): 716-721. doi: 10.3724/SP.J.1146.2011.00405.

HE Fenghang, YU Zhijun, and LIU Haitao. Multiple target localization via compressed sensing in wireless sensor networks[J].&, 2012, 34(3): 716-721. doi: 10.3724/SP.J.1146.2011.00405.

[5] MIR Y U, KOPPARAPU V R, and YAND Dongkai. An enhanced K-nearest neighbor algorithm for indoor positioning systems in a WLAN[C]. Proceedings of 2014 IEEE Computers, Communications and IT Applications Conference (ComComAp), Beijing, 2014: 5-8.

[6] ZHANG Rongbiao, GUO Jianguang, CHU Fuhuan,. Environmental-adaptive indoor radio path loss model for wireless sensor networks localization[J]., 2011, 65(12): 1023-1031.

[7] MIHALIS A N, HATICE G, and MAJA P. Output- associative RVM regression for dimensional and continuous emotion prediction[J]., 2012, 30(3): 186-196.

[8] 趙春暉, 張燚, 王玉磊. 基于小波核主成分分析的相關向量機高光譜圖像分類[J]. 電子與信息學報, 2012, 34(8): 29-32. doi: 10.3724/SP.J.1146.2011.01282.

ZHAO Chunhui , ZHANG Yi, and WANG Yulei. Relevant vector machine classification of hyperspectral image based on wavelet kernel principal component analysis[J].&, 2012, 34(8): 29-32. doi: 10.3724/SP.J.1146.2011.01282.

[9] NURCIHAN C. Application of support vector machines and relevance vector machines in predicting uniaxial compressive strength of volcanic rocks[J]., 2014, 100(11): 634-644.

[10] CLéMENT D and FRéDéRIC E M. Stationary max-stable processes with the Markov property[J]., 2014, 124(6): 2266-2279.

[11] 唐朝偉, 李超群, 燕凱, 等. 基于LISOMAP的相關向量機入侵檢測模型[J]. 計算機應用, 2012, 32(9): 2606-2608.

TANG Chaowei, LI Chaoqun, YAN Kai,. Intrusion detection model based on LISOMAP relevant vector machine[J]., 2012, 32(9): 2606-2608.

[12] WANG Li, HU Jianfeng, and LIU Yongwei. Proceedings of an adaptive line search scheme for compressed sensing based on nemirovski's algorithm[C]. Proceedings of the 2nd National Conference on Information Technology and Computer Science, Shanghai, 2015: 7-8.

[13] GHAEDI M, GHAEDI A M, HOSSAINPOUR M,. Least square-support vector (LS-SVM) method for modeling of methylene blue dye adsorption using copper oxide loaded on activated carbon: Kinetic and isotherm study[J]., 2014, 25(4): 1641-1649.

[14] 李蘊華. 壓縮感知框架下基于ROMP 算法的圖像精確重構[J]. 計算機應用, 2011, 31(10): 2714-2716.

LI Yunhua. Precise image reconstruction based on ROMP algorithm in compressive sensing[J]., 2011, 31(10): 2714-2716.

[15] LIN C K Y, Haley K B, and SPARKS C. A comparative study of both standard and adaptive versions of threshold accepting and simulated annealing algorithms in three scheduling problems[J]., 1995, 83(2): 330-346.

[16] OLG A S P, EFSTATHIOS Z, FADY R M,. Sensory and microbiological quality assessment of beef fillets using a portable electronic nose in tandem with support vector machine analysis[J]., 2013, 50(1): 241-249.

Double Stage Indoor Localization Algorithm Based on LANDMARC and Compressive Sensing

LI Lina①MA Jun①②LONG Yue①XU Panfeng①

①(,,110036,),②(,,250002,)

In consideration of the contradiction between the positioning accuracy and computational efficiency of the previous indoor positioning algorithm, a double stage positioning algorithm (LANDMARC- SROMP CS) using LANDMARC combined with Compressive Sensing based on the Regularized Orthogonal Matching Pursuit optimized by the Simulated annealing algorithm (SROMP) is put forward. First of all, LANDMARC location algorithm is used to lock the target area quickly; then in the locked area, Compressive Sensing (CS) theory is introduced to realize the target position estimation. In this part, firstly, the virtual reference tags are constructed according to the scale of the locked area; then, the measurement matrix is constructed by the received signal strength data of the virtual reference tags, and the signal strength data are calculated by the indoor propagation loss model which is trained by a new relevance vector machine algorithm based on mixed kernel functions. At last, the SROMP compressive sensing reconstruction algorithm is used to get the position index matrix, and the position information of the target also can be obtained through a simple weighted average calculation. The experimental results show that the average positioning error of the proposed algorithm is only 0.6445 m, and the computation efficiency of the proposed algorithm is relatively high, which can meet the indoor positioning requirements well.

Indoor localization; Compressive Sensing (SC); Simulated annealing; Regularized Orthogonal Matching Pursuit (ROMP); Relevance Vector Machine (RVM)

TP391.44

A

1009-5896(2016)07-1631-07

10.11999/JEIT151050

2015-09-17；改回日期：2016-03-07；網絡出版：2016-04-07

龍躍 longyue85@sina.com

國家自然科學基金(61403176)，遼寧省教育廳科學技術研究項目(L2013003)

The National Natural Science Foundation of China (61403176), Science and Technology Research Project of Educational Commission of Liaoning Province of China (L2013003)

李麗娜： 女，1973年生，副教授，博士，研究方向為物聯網感知層相關技術及應用.

馬 俊： 女，1988年生，碩士生，研究方向為RFID室內定位技術.

龍 躍： 女，1983年生，講師，博士，研究方向為網絡傳輸控制及故障診斷技術.

徐攀峰： 女，1978年生，實驗師，研究方向為無線單片機技術及應用.