劉　凱, 方小俊, 黃青華

(上海大學通信與信息工程學院特種光纖與光接入網重點實驗室, 上海 200072)

?

基于RTI雙重構的免攜帶設備目標無線定位

劉凱, 方小俊, 黃青華

(上海大學通信與信息工程學院特種光纖與光接入網重點實驗室, 上海 200072)

摘要：免攜帶設備定位是利用目標對無線通信鏈路產生的陰影衰落來估計目標的位置。針對現有算法定位精度有限、計算復雜度高等問題,在無線層析成像(radio tomographic imaging, RTI)的基礎上提出了基于雙重構的定位算法。該算法利用正則化快速重構的特點,首先對目標進行初步的定位;其次將粗定位區(qū)域進行像素精確劃分,同時利用鏈路選擇法減少鏈路個數,降低算法復雜度;最后提出補空間稀疏度自適應匹配重構算法,將目標位置轉化為稀疏信號重構問題，完成定位。實驗仿真結果表明,與基于RTI的單重構定位算法相比,所提雙重構算法能達到較好的定位精度,且實時性更高。

關鍵詞：免攜帶設備定位; 正則化; 壓縮感知; 雙重構

0引言

現有的定位技術都要求目標攜帶特定設備輔助定位,對于入侵檢測、火災救援等特定場合,目標無法滿足攜帶設備的要求。免攜帶設備定位(device-free localization, DFL)[1]是在目標不攜帶任何設備的情況下獲取目標的位置信息,因而在多種場合下具有廣泛的應用前景。

文獻[2-3]提出DFL。文獻[4-5]將DFL問題建模為指紋識別問題,提出了指紋法,文獻[6]建立了由單目標到雙目標的射頻地圖,降低了多目標指紋離線訓練量。文獻[7]提出鏈路法,利用鏈路交叉、多信道通信和支持向量回歸模型定位目標位置。

指紋法需要離線訓練,而鏈路法定位精度受限于鏈路的個數。文獻[8]借助工業(yè)CT的原理,提出了無線層析成像(radio tomographic imaging, RTI)方法。文獻[9]進一步利用接收信號強度(received signal strength, RSS)方差定位實現了動態(tài)目標的定位。文獻[10]基于差分RSS進行定位,提高了對設備和環(huán)境的魯棒性。文獻[11-12]利用壓縮感知理論,解決了RTI重構時的病態(tài)問題。

RTI重構方法主要有兩種:正則化(Regularization)方法重構速度快,但定位精度較低[13];壓縮感知算法精度高，但計算量大[14]。本文結合兩種重構算法的優(yōu)點,先利用正則化縮小定位范圍,同時采用鏈路選擇法減少參與定位的鏈路個數,最后基于補空間稀疏度自適應匹配的壓縮感知算法實現了精確定位,提出了兼顧精度和計算復雜度的雙重構方法。

1雙重構的粗定位

1.1問題描述

DFL是指當目標人物進入到布有無線傳感網節(jié)點的環(huán)境中時,利用目標對無線鏈路的陰影衰落效應,根據目標位置和鏈路RSS的規(guī)律進行定位,定位示意圖如圖1所示。

圖1　DFL定位示意圖

若在定位區(qū)域內有J個無線節(jié)點進行相互通信,則理論上最多存在L=J(J-1)/2條無線鏈路,根據RTI思想將這個定位區(qū)域劃分為N個小方格,每個方格都當作圖像的一個像素點,當目標在t時刻出現時,基于陰影傳播模型[15],第i條鏈路的信號強度變化量Δyi表示為

(1)

式中,Δyi主要是由兩個時刻的遮蔽衰減量Si(t)決定。假設在定位區(qū)域內共有M條無線鏈路參與定位,那么RSS變化量轉換為矩陣形式為

y=Wx+n

(2)

式中,y表示M×1維的鏈路測量向量;x表示N×1維的目標位置信息向量;n表示M×1維的噪聲向量;W表示M×N維權重矩陣，其值由橢圓模型可求出,定義為

(3)

式中,dij1和dij2為第j個像素中心到第i條鏈路兩端節(jié)點的距離;di為兩端節(jié)點間的通信距離;λ為可調節(jié)的橢圓寬度參數。

1.2基于正則化的重構

根據式(2)的RTI線性模型方程,可以由已知向量y和權重矩陣W重構出目標位置信息x。然而這是病態(tài)求逆的不適定問題,解決此問題通常采用正則化方法[16]。

解方程y=Wx+n可以歸結為求Tikhonov[17]泛函公式極小值的問題。公式為

(4)

式中,α為正則化參數;Φ為正則化矩陣。將式(4)兩邊求導,結果等于0,可得出目標向量

(5)

對xTik取最大值得到的像素中心點坐標作為目標xo的位置,從而實現目標初步定位,表示為

(6)

1.3雙重構理論

正則化方法雖能快速重構出目標信息xTik,但在實際的定位環(huán)境中,直接用正則化定位精度較差。為了彌補單重構算法在定位性能上的不足,本文在正則化單重構的基礎上,再次進行稀疏重構,利用雙重構的算法來提高定位精度。首先將正則化重構出的結果進行處理

(7)

式(7)表示對xTik進行從大到小排序,同時選擇v個較大的像素值所對應的方格作為目標的粗定位區(qū)域向量A,經過粗定位后縮小了目標定位區(qū)域的范圍,如圖2(a)所示。根據圖2(a)粗定位出紅框內的區(qū)域,然后將其A中每個像素方格再次進行像素點的精確劃分,其中每個像素方格再劃分為F個小像素點,形成含有S個像素點的位置區(qū)域A,如圖2(b)所示。

(8)

圖2　雙重構定位原理圖

細重構算法中計算量的大小通常和鏈路個數有關。根據文獻[7]中提出的鏈路中心概率覆蓋模型,目標在位于以當前鏈路為直線中心軸的橢圓范圍內時,目標對通信鏈路的影響最大。為了提高重構速度,采用鏈路選擇方法減少鏈路冗余。

考慮到目標位于定位區(qū)域中時,定義向量U=[l1,l2,…,lM]表示為無線通信鏈路集合,將U分為受目標影響的鏈路集合U1和基本不受影響的鏈路集合U0,同時選擇有變化的鏈路集合U1參與定位,表示為

(9)

式中,μ為RSS變化量的閾值。

2基于壓縮感知的細重構

2.1稀疏分析

在位置區(qū)域A內,目標在某一個時刻其位置信息是唯一的,即在A上是稀疏的。定義S×1維向量θ表示區(qū)域A中位置信息的索引,記為θ=[0,…,1,…,0]T。假設目標位于區(qū)域A中某一位置上,則目標所在該像素位置的索引值為1,其他為0。

將實時測量的y中鏈路RSS變化量進行排列,再從集合U1中選擇L′(L′

(10)

式中,φl中的每個元素表示鏈路索引,被選擇的鏈路索引置1,未被選擇的鏈路索引置0。式(2)可化為

(11)

2.2重構算法

為了從觀測信號yL′中重構出稀疏向量θ的值,通?？梢酝ㄟ^l1范數的最優(yōu)化求解出目標的位置信息,表示為

(12)

但是在實際的定位環(huán)境中,不能直接采用該方法進行重構,這是因為測量值yL′和矩陣WL′S之間需要滿足弱相關性或不相關性[18],為了解決這一問題,需要對測量向量yL′進行正交化預處理,表示為

(13)

(14)

2.3CMPs-SAMP定位算法

目前已有多種壓縮感知算法應用在定位過程中,包括匹配追蹤(matching pursuit, MP),正交匹配追蹤(orthogonal matching pursuit, OMP)[19]等算法。本文所提重構算法是結合正交匹配(complementary matching pursuit, CMP)[18]算法和稀疏度自適應匹配追蹤(sparsity adaptive matching pursuit, SAMP)[20]算法的一種新的重構算法。使其具有較好的原子選擇和重建方式,得到較好的定位性能。

其中采用CMP算法選擇原子,用OMP方式重建的壓縮感知算法(CMP selection OMP update, CMPs-OMPu)[18],相比OMP算法在感知矩陣中選擇一個最匹配原子的方式,其采用剔除S-1個不匹配的原子,保留剩下一個最匹配的原子方式。假設要求的稀疏解可以表示為

(15)

(16)

CMPs-OMPu算法通過求解θc的值來解θ*,具有較好的原子選擇方式,重構結果更加稀疏。

在實際定位過程中,重建方式也是壓縮感知定位過程中一個非常重要的環(huán)節(jié),CMPs-OMPu算法雖有較好的原子選擇方式,但其重建速度較慢,在復雜室內定位環(huán)境下其重建效果不佳。

SAMP沿用OMP算法的原子選擇原則,但其通過設置一個可變步長,逐步對信號進行估計,同時具有回退篩選思想,具有較好的重建效果,速度也快于OMP等算法。

因此CMPs-SAMP算法克服了CMPs-OMPu算法的局限性。其重建過程設置一個可變步長,將重建過程分為多個階段,在每個階段所需的支撐集Λ大小不變,通過選取觀測矩陣Q和殘差r之間相關性較大的一些值形成候選集Γ,再從候選集Γ中通過計算再次得到支撐集。當滿足式‖rt-rt-1‖2≤δ時,停止迭代,否則以步長z增大支撐集的大小,這種回溯思想使得它精度較好于同類算法。

總之,CMPs-SAMP算法是一種結合了CMPs-OMPu算法和SAMP算法的新的重建算法,保證了定位精度的同時還提高了雙重構算法的實時性，算法的具體步驟如下。

輸入測量信號y′,觀測矩陣Q,初始步長z。

輸出稀疏信號向量索引值θ,殘差r。

初始化迭代余量r0=y′,稀疏向量θ0=0,迭代計數器t=0,候選集Γ0=?,支撐集Λ=?,階段stage=1。

步驟 2計算相關性gt=ΔQT(QQT)-1rt-1;

步驟 3找出gt中z個最大值對應的索引值存入集合Z,得到候選集Γt=Γt-1∪{Z};

步驟 4計算組合QΓt=QΓt-1,采用步驟2和步驟3計算QΓt和y′,選z個最大值對應索引值存入支撐集Λ;

步驟 6判斷迭代終止條件‖rt-rt-1‖2≤δ,滿足則停止,且θ=θt,r=rt,輸出θ和r,否則轉到步驟7;

步驟 7進入到下一階段,支撐集的大小增大為z=z*stage,stage=stage+1,轉步驟1。

在實際的定位環(huán)境中,重構出的θ可能同時存在多個非零值,在這種情況下,通常是設一個閾值ε,對θ中大于閾值的索引值所對應的位置進行加權平均來估計目標的位置,表示為

(17)

綜上所述,本文算法流程如圖3所示。

圖3　雙重構目標定位算法流程圖

3實驗結果與分析

3.1實驗設置

為了驗證本文提出算法的性能,本文在上海大學行健樓內布置ZigBee傳感器節(jié)點的定位區(qū)域里進行真實數據的采集,同時也采用猶他大學SPAN實驗室的數據加以驗證。本文實測環(huán)境如圖4所示,采集數據用的節(jié)點是TI CC2530無線節(jié)點,IEEE 802.15.4協議和2.4 GHz頻率。此實驗定位區(qū)域為4.4 m×5.5 m,在5.5 m的兩條長邊各布置6個傳感器節(jié)點,相間隔1.1 m。

圖4　實測定位區(qū)域圖

3.2實驗結果分析

圖5和圖6表示目標定位的單重構和雙重構算法結果。單重構進行了兩次實驗,分別將定位區(qū)域劃分為20個和180個像素方格。雙重構定位時,先將該定位區(qū)域初步劃分為20個像素方格,進行正則化重構,定位出v=2個像素點,然后將每個像素點細分成9個小像素點,最后對這18個像素點進行壓縮感知重構。

圖5　目標單重構誤差累積概率分布

圖6　目標雙重構誤差累積概率分布

誤差累積概率定義為當所有誤差c小于等于某個特定的誤差值err時,其出現概率的和。其數學表達式為

F(err)=P(c≤err)

(18)

圖5(a)和圖5(b)表示將定位區(qū)域僅劃分為20個和180個像素點時不同算法單重構的誤差累積概率圖,從圖中可以看出，本文提出的重構算法CMPs-SAMP相比其他算法定位精度要好,且像素點的個數越多,其定位精度越高,圖5(b)中本文重構算法CMPs-SAMP在1 m內的定位精度要比圖5(a)中的定位精度高約30%以上。圖6表示本文雙重構算法的定位誤差圖,顯示本文CMPs-SAMP算法相比圖5(b)而言在1 m以內的定位精度高5%左右。

圖7給出了目標位于定位區(qū)域內某一位置上對通信鏈路影響的分析情況。從圖中可以看出,大部分鏈路其信號強度是基本不受影響的。從而可將鏈路分為受影響的集合和不受影響的集合,同時選取穩(wěn)定性較強的鏈路參與定位,可減小算法的計算量。

表1是對不同算法的時間復雜度進行比較的結果,其中第2列、第3列分別是對定位區(qū)域僅劃分為20個和180個像素點時單重構算法復雜度,第4列是基于本文雙重構思想的復雜度。本次實驗選取稀疏度K=3,M=66。雙重構減少了鏈路個數,使得本文雙重構算法相比單重構算法的復雜度較低。

表2列出在HP CQ40筆記本(2.1GHz的Intel Pentium處理器,2GB內存)上進行20次實驗不同算法的平均運行時間,實驗結果表明本文的雙重構RTI算法有更高的實時性。

圖7　單目標引起的鏈路信號強度變化情況

重構算法20個像素單重構 (N=20)180個像素單重構 (N=180)本文雙重構算法 (N=20,L'=20,S=18)OMPO(KMN)O(KMN)O(MN+KL'S)CMPs-OMPuO(KM2N+KMN2)O(KM2N+KMN2)O(MN+KL'2S+KL'S2)SAMPO(MNKln(z)/z)O(MNKln(z)/z)O(MN+KL'Sln(z)/z)CMPs-SAMPO((M2N+MN2)Kln(z)/z)O((M2N+MN2)Kln(z)/z)O(MN+(L'2S+L'S2)Kln(z)/z)RegularizationO(MN)O(MN)—

表2　不同重構算法的運行時間　s

圖8給出了鏈路的時變特性對定位精度的影響,采用猶他大學SPAN實驗室的數據,在不同鏈路采樣樣本數情況下,對平均定位誤差進行比較。本文所提算法在少量采樣樣本數時就能達到較好的定位精度。在提高定位精度的同時能減少實時定位的鏈路計算工作量,有利于系統(tǒng)的擴展應用。

圖8　目標定位誤差隨采樣樣本數變化情況

圖9表示在本文算法中橢圓寬度對定位精度的影響。文獻[7]提出中心覆蓋模型,表明選擇不同的橢圓寬度其目標對鏈路的影響范圍是不同的,選擇合適的橢圓寬度對實現精確定位也是必要的。本次實驗中選擇的橢圓寬度為λ=0.11時其定位效果較好。

圖9　橢圓寬度對定位誤差的影響

4結論

本文所提雙重構算法相比單重構算法而言減少了算法的運行時間,提高了目標定位的精度和實時性。由于本次實驗是通過采集真實環(huán)境下RSS值進行定位分析,沒有考慮人的走動以及多徑效應對定位性能的影響,而且目前還沒有比較完整的算法能精確地分離并實現相鄰多目標之間的定位,這些問題將是以后研究的重點。

參考文獻：

[1] Zhang D, Liu Y, Guo X, et al. RASS: a real-time accurate and scalable system for tracking transceiver-free objects[J].IEEETrans.onParallelandDistributedSystems,2013,24(5):996-1008.

[2] Youssef M, Mah M, Agrawala A. Challenges: device-free passive localization for wireless environments[C]∥Proc.ofthe13thAnnualInternationalConferenceonMobileComputingandNetworking,2007：222-229.

[3] Zhang D, Jian M, Quanbin C, et al. An RF based system for tracking transceiver-free objects[C]∥Proc.oftheIEEEInternationalConferenceonPervasiveComputingandCommunications,2007: 135-144.

[4] Kosba A E, Abdelkader A, Youssef M. Analysis of a device free passive tracking system in typical wireless environments[C]∥Proc.ofthe3rdInternationalConferenceonNewTechnologies,MobilityandSecurity,2009: 1-5.

[5] Seifeldin M, Saeed A, Kosba A, et al. Nuzzer: a large-scale device-free passive localization system for wireless environments[J].IEEETrans.onMobileComputing,2013,12(7):1321-1334.

[6] Liu K, Yu J J, Huang Q H. Bi-object device-free localization based on compressive sensing[J].JournalofElectronics&InformationTechnology,2014, 36(4)：862-867. (劉凱, 余君君, 黃青華. 基于壓縮感知的免攜帶設備雙目標定位算法[J]. 電子與信息學報,2014,36(4):862-867.)

[7] Zhang D, Liu Y, Ni L M. Link-centric probabilistic coverage model for transceiver-free object detection in wireless networks[C]∥Proc.oftheIEEE30thInternationalConferenceonDistributedComputingSystems,2010: 116-125.

[8] Wilson J, Patwari N. Radio tomographic imaging with wireless networks[J].IEEETrans.onMobileComputing,2010, 9(5): 621-632.

[9] Wilson J, Patwari N. A fade-level skew-laplace signal strength model for device-free localization with wireless networks[J].IEEETrans.onMobileComputing,2012, 11(6): 947-958.

[10] Wang J, Gao Q, Yu Y, et al. Robust device-free wireless localization based on differential RSS measurements[J].IEEETrans.onIndustrialElectronics,2012, 60(12): 5943-5952.

[11] Kanso M A, Rabbat M G. Compressed RF tomography for wireless sensor networks: centralized and decentralized approaches[C]∥Proc.oftheIEEE5thInternationalConferenceonDistributedComputinginSensorSystems,2009: 173-186.

[12] Wang J, Zhang X, Gao Q, et al. Device free localisation with wireless networks based on compressive sensing[J].Communications,2012, 6(15): 2395-2403.

[13] Yang Z, Huang K, Guo X, et al. A real-time device-free localization system using correlated RSS measurements[J].EURASIPJournalonWirelessCommunicationsandNetworking,2013(186): 1-12.

[14] Zhang L, Tan Z. Study on compressive sensing in the application of wireless localization[J].JournalofInternetTechnology,2010,11(1): 129-134.

[15] Wang J. Wireless localization and tracking based on Bayesian estimation[D]. Dalian: Dalian University of Technology,2011.(王潔. 基于貝葉斯估計方法的無線定位跟蹤技術研究[D].大連:大連理工大學,2011.)

[16] Li J. Regularied methods for ill-posed problems[D]. Changsha: Central South University,2009.(李景. 不適定問題的正則化方法[D]. 長沙:中南大學,2009.)

[17] Zhu H P. The regularization theory for ill-posed problems and application[D]. Wuhan： Wuhan University of Technology,2007.(朱華平. 不適定問題的正則化理論及其應用[D]. 武漢理工大學,2007.)

[18] Zhou C M. Research on signal reconstruction algorithm based on compressive sensing[D]. Beijing: Beijing Jiaotong University,2010. (周燦梅. 基于壓縮感知的信號重建算法研究[D]. 北京:北京交通大學,2010.)

[19] Feng C. Research and implementation of a compressive sensing-based indoor positioning system using RSS[D]. Beijing: Beijing Jiaotong University,2011.(馮辰. 基于壓縮感知的RSS室內定位系統(tǒng)的研究與實現[D]. 北京:北京交通大學,2011.)

[20] Liu Y X, Zhao R Z, Hu S H, et al. Regularized adaptive matching pursuit algorithm for signal reconstruction based on compressive sensing[J].JournalofElectronics&InformationTechnology,2010, 32(11): 2713-2717.(劉亞新, 趙瑞珍, 胡紹海, 等. 用于壓縮感知信號重建的正則化自適應匹配追蹤算法[J]. 電子與信息學報,2010, 32(11): 2713-2717.)

劉凱(1981-),男,副教授,博士,主要研究方向為盲信號處理、通信信號處理、室內無線定位、雷達信號處理、雷達信號分選。

E-mail: liukai@shu.edu.cn

方小俊(1990-),男,碩士研究生,主要研究方向為無線定位、信號處理。

E-mail: fangxiaojune@126.com

黃青華(1978-),女,副研究員,博士,主要研究方向為陣列信號處理、盲信號處理和3D音頻。

E-mail: qinghua@shu.edu.cn

網絡優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20150604.1438.001.html

Device-free localization based on RTI bi-reconstruction

algorithm with wireless sensor networks

LIU Kai, FANG Xiao-jun, HUANG Qing-hua

(KeyLaboratoryofSpecialtyFiberOpticsandOpticalAccessNetworks,SchoolofCommunicationand

InformationEngineering,ShanghaiUniversity,Shanghai200072,China)

Abstract:Device-free localization (DFL) is the estimation of target without carrying any electronic device by the shadow-fading of wireless communication links. However, current algorithms have some disadvantages of low positioning accuracy and large computation during positioning. A novel algorithm based on radio tomographic imaging(RTI), combining regularization and compressive sensing theory, called bi-reconstruction algorithm, is proposed to locate the target. The algorithm uses the characteristics of the fast reconstruction of regularization and first of all, it divides the location area into a plurality of grids to complete the initial positioning of the target. In order to achieve precise positioning, the possible location areas are divided into multiple small grids again, simultaneously the link selection method is used to decrease the number of links and reduce the algorithm complexity. Then, complementary sparsity adaptive matching pursuit (CMPs-SAMP) is adopted to locate the target and transform the localization problem to a sparse signal reconstruction problem. The simulation results show that the proposed bi-reconstruction algorithm outperforms other single reconstruction algorithms.

Keywords:device-free localization (DFL); regularization; compressive sensing; bi-reconstruction

作者簡介：

中圖分類號：TN 911.7

文獻標志碼：A

DOI:10.3969/j.issn.1001-506X.2016.01.06

基金項目：國家自然科學基金(61501288,61571279);上海市自然科學基金(15ZR1415500)資助課題

收稿日期：2014-10-21；修回日期：2015-04-19；網絡優(yōu)先出版日期：2015-06-04。