李麗娜馬?、邶堒S徐攀峰

?

基于LANDMARC與壓縮感知的雙段式室內(nèi)定位算法

李麗娜①馬 ?、佗邶?躍*①徐攀峰①

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

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

室內(nèi)定位；壓縮感知；模擬退火；正則化正交匹配追蹤；相關(guān)向量機

1 引言

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

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

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

圖1 LANDMARC-SROMP CS雙段式室內(nèi)定位算法流程圖

3 LANDMARC-SROMP CS雙段式定位算法原理及實現(xiàn)

3.1 基于LANDMARC的區(qū)域定位

3.2 測量矩陣構(gòu)建

為實現(xiàn)待定位目標(biāo)的位置估計，需先進行測量矩陣的構(gòu)建。采用虛擬標(biāo)簽的RSSI值填充測量矩陣。虛擬標(biāo)簽RSSI值的填充要滿足無線信號傳播損耗模型(又稱經(jīng)驗?zāi)Ｐ?[6]：

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

高斯核函數(shù)學(xué)習(xí)能力較強，泛化性能較弱；而樣條核函數(shù)恰好相反。該組合核函數(shù)在最大限度地保留學(xué)習(xí)能力的同時提高其泛化性能。并且，用拉普拉斯核函數(shù)代替?zhèn)鹘y(tǒng)組合核函數(shù)中的調(diào)節(jié)因子，進一步提高了核函數(shù)的學(xué)習(xí)能力。經(jīng)驗證，該組合核函數(shù)滿足組合核函數(shù)構(gòu)建的異構(gòu)條件[8]。RVM算法的核函數(shù)不需要滿足Mercer準(zhǔn)則[9]，降低了核函數(shù)選擇的復(fù)雜程度。訓(xùn)練時，設(shè)T互相獨立，且來自模型：

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

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

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

3.4 SROMP壓縮感知重構(gòu)算法

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

步驟 4 執(zhí)行一次退火產(chǎn)生新的稀疏因子。

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

4 仿真與實驗

4.1 傳播損耗模型訓(xùn)練實驗

圖2 SVM模型訓(xùn)練效果圖

圖3 高斯核RVM損耗模型訓(xùn)練效果圖

圖4 組合核RVM模型訓(xùn)練效果圖

表1 模型訓(xùn)練結(jié)果與樣本偏差統(tǒng)計表(dB)

4.2 定位算法仿真

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

圖5 定位仿真布局圖

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

圖7 目標(biāo)定位仿真效果圖

4.3 定位實驗評估

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

圖8 單目標(biāo)定位實驗結(jié)果

圖9 平均定位誤差曲線圖

表2 定位誤差及平均計算時間分析統(tǒng)計表

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

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

圖10 多目標(biāo)定位實驗場景圖

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

圖11 多目標(biāo)定位實驗結(jié)果

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

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

5 結(jié)束語

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

[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] 何風(fēng)行, 余志軍, 劉海濤. 基于壓縮感知的無線傳感器網(wǎng)絡(luò)多目標(biāo)定位算法[J]. 電子與信息學(xué)報, 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] 趙春暉, 張燚, 王玉磊. 基于小波核主成分分析的相關(guān)向量機高光譜圖像分類[J]. 電子與信息學(xué)報, 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的相關(guān)向量機入侵檢測模型[J]. 計算機應(yīng)用, 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 算法的圖像精確重構(gòu)[J]. 計算機應(yīng)用, 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；網(wǎng)絡(luò)出版：2016-04-07

龍躍 longyue85@sina.com

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

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

李麗娜： 女，1973年生，副教授，博士，研究方向為物聯(lián)網(wǎng)感知層相關(guān)技術(shù)及應(yīng)用.

馬 ?。?女，1988年生，碩士生，研究方向為RFID室內(nèi)定位技術(shù).

龍 躍： 女，1983年生，講師，博士，研究方向為網(wǎng)絡(luò)傳輸控制及故障診斷技術(shù).

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