基于RTI雙重構(gòu)的免攜帶設(shè)備目標無線定位

劉　凱, 方小俊, 黃青華

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

?

基于RTI雙重構(gòu)的免攜帶設(shè)備目標無線定位

劉凱, 方小俊, 黃青華

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

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

關(guān)鍵詞：免攜帶設(shè)備定位; 正則化; 壓縮感知; 雙重構(gòu)

0引言

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

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

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

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

1雙重構(gòu)的粗定位

1.1問題描述

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

圖1　DFL定位示意圖

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

(1)

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

y=Wx+n

(2)

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

(3)

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

1.2基于正則化的重構(gòu)

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

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

(4)

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

(5)

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

(6)

1.3雙重構(gòu)理論

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

(7)

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

(8)

圖2　雙重構(gòu)定位原理圖

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

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

(9)

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

2基于壓縮感知的細重構(gòu)

2.1稀疏分析

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

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

(10)

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

(11)

2.2重構(gòu)算法

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

(12)

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

(13)

(14)

2.3CMPs-SAMP定位算法

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

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

(15)

(16)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(17)

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

圖3　雙重構(gòu)目標定位算法流程圖

3實驗結(jié)果與分析

3.1實驗設(shè)置

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

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

3.2實驗結(jié)果分析

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

圖5　目標單重構(gòu)誤差累積概率分布

圖6　目標雙重構(gòu)誤差累積概率分布

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

F(err)=P(c≤err)

(18)

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

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

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

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

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

重構(gòu)算法20個像素單重構(gòu) (N=20)180個像素單重構(gòu) (N=180)本文雙重構(gòu)算法 (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　不同重構(gòu)算法的運行時間　s

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

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

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

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

4結(jié)論

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

參考文獻：

[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. (劉凱, 余君君, 黃青華. 基于壓縮感知的免攜帶設(shè)備雙目標定位算法[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.(王潔. 基于貝葉斯估計方法的無線定位跟蹤技術(shù)研究[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.(朱華平. 不適定問題的正則化理論及其應(yīng)用[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室內(nèi)定位系統(tǒng)的研究與實現(xiàn)[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.(劉亞新, 趙瑞珍, 胡紹海, 等. 用于壓縮感知信號重建的正則化自適應(yīng)匹配追蹤算法[J]. 電子與信息學報,2010, 32(11): 2713-2717.)

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

E-mail: liukai@shu.edu.cn

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

E-mail: fangxiaojune@126.com

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

E-mail: qinghua@shu.edu.cn

網(wǎng)絡(luò)優(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；網(wǎng)絡(luò)優(yōu)先出版日期：2015-06-04。