無線傳感器網(wǎng)絡(luò)下基于壓縮感知的多目標(biāo)分層貪婪匹配定位

游康勇 楊立山 郭文彬

隨著無線通信技術(shù)的進(jìn)步以及無線傳感器網(wǎng)絡(luò)(Wireless sensor network,WSN)和物聯(lián)網(wǎng)等的高速發(fā)展,如何精確定位監(jiān)控區(qū)域內(nèi)的多個(gè)目標(biāo)已經(jīng)成為信號(hào)處理領(lǐng)域中極具挑戰(zhàn)和實(shí)際意義的問題.多目標(biāo)定位可以應(yīng)用于諸多場(chǎng)景,例如,WSN中傳感器節(jié)點(diǎn)定位[1]、室內(nèi)定位[2]、污染源定位[3]、無線電監(jiān)控等.

傳統(tǒng)的定位算法主要分為兩類.一類是基于測(cè)距的定位算法,典型算法有利用到達(dá)時(shí)間測(cè)距(Time of arrival,ToA)、利用到達(dá)時(shí)間差測(cè)距(Time difference of arrival,TDoA)、利用到達(dá)角度測(cè)距(Angle of arrival,AoA)和利用接收信號(hào)強(qiáng)度進(jìn)行三邊測(cè)距(Received signal strength indicator,RSSI)[4];一類是非測(cè)距的定位算法,典型算法有DVhop定位[5]、基于信道感知定位[6]和RSSI指紋定位[7?8]等.然而這些方法都顯示出一定的局限性.

近年來,壓縮感知(Compressive sensing,CS)理論的興起[9]為我們提供了一種全新的視角去看待多目標(biāo)定位問題.通過對(duì)感知區(qū)域的網(wǎng)格化,目標(biāo)位置在空間域上的稀疏性為壓縮感知理論體系的應(yīng)用提供了可能.研究表明[10?11],基于壓縮感知的多目標(biāo)定位方法能夠?qū)崿F(xiàn)比傳統(tǒng)的定位方法更好的定位性能.Cevher等[12?13]提出了WSN 中多目標(biāo)定位的估計(jì)框架,提出只需少量的測(cè)量,便可以將目標(biāo)位置的稀疏向量通過傳感矩陣進(jìn)行恢復(fù).在此之后,Feng等[10]開始將多目標(biāo)定位問題建立在壓縮感知欠定方程上,并采取了基追蹤(Basis pursuit,BP)和基追蹤降噪(Basis pursuit denoising,BPDN)等恢復(fù)算法進(jìn)行仿真測(cè)試及性能比較.Zhang等[11]使用貪婪匹配追蹤(Greedy matching pursuit,GMP)算法替代傳統(tǒng)的壓縮感知恢復(fù)算法,提高了恢復(fù)的準(zhǔn)確性,同時(shí)對(duì)傳感矩陣是否滿足有限等距特性(Restricted isometry property,RIP)[9]進(jìn)行了證明.Lin等[14]通過融合兩種網(wǎng)格下的恢復(fù)結(jié)果獲得了分集增益,提高了定位精度.

然而,之前基于壓縮感知定位的研究有諸多不足.1)求解基于壓縮感知的多目標(biāo)定位問題時(shí),基于優(yōu)化逼近的方法定位精度高但計(jì)算復(fù)雜,基于貪婪恢復(fù)的方法計(jì)算簡(jiǎn)單卻定位精度低;2)簡(jiǎn)單使用一般的壓縮感知恢復(fù)算法來實(shí)現(xiàn)定位,忽略了多目標(biāo)定位問題中豐富的結(jié)構(gòu)信息,無法有效提升定位性能;3)為降低密集網(wǎng)格劃分帶來的強(qiáng)相關(guān)性,文獻(xiàn)中廣泛采用的正交預(yù)處理方法[10]削弱了原始定位模型中的信噪比,使得定位算法的抗噪性能大幅降低.

鑒于此,本文針對(duì)多目標(biāo)定位問題,給出了明確的系統(tǒng)模型,證明預(yù)處理方法削弱模型信噪比,提出一種新穎的基于壓縮感知的層級(jí)貪婪匹配追蹤定位算法(Hierarchical greedy matching pursuit,HGMP).所提算法具有線性計(jì)算復(fù)雜度,提供了一種利用多目標(biāo)定位場(chǎng)景中的結(jié)構(gòu)信息實(shí)現(xiàn)快速貪婪定位的層級(jí)架構(gòu),提高了多目標(biāo)定位系統(tǒng)的定位精度和抗噪聲性能.

1 系統(tǒng)模型

本節(jié)首先闡述基于德勞內(nèi)三角剖分的空間網(wǎng)格化方法,介紹基于壓縮感知的多目標(biāo)定位模型及各參數(shù)的意義.其次,從壓縮感知理論出發(fā),討論定位問題中目標(biāo)數(shù)、傳感器數(shù)目、網(wǎng)格數(shù)目三者的相互制約關(guān)系.接著,證明文獻(xiàn)中廣泛采用的基于正交的預(yù)處理操作本質(zhì)上降低信噪比.最后,在討論部分闡述本文的主要?jiǎng)訖C(jī).

1.1 空間德勞內(nèi)三角網(wǎng)格劃分

不失一般性,設(shè)已知存在K個(gè)目標(biāo)的二維感知區(qū)域被離散成N個(gè)網(wǎng)格點(diǎn)(目標(biāo)服從感知區(qū)域內(nèi)的連續(xù)均勻分布),其中隨機(jī)均勻散布M個(gè)傳感器(位置已知),每個(gè)傳感器測(cè)量該點(diǎn)處的接收信號(hào)強(qiáng)度(Received signal strength,RSS).在空間網(wǎng)格點(diǎn)數(shù)目足夠大的前提下,可以用網(wǎng)格點(diǎn)近似估計(jì)目標(biāo)的位置來確定K個(gè)目標(biāo)發(fā)射源的位置.

空間網(wǎng)格化是構(gòu)建定位模型的第一步,文獻(xiàn)中廣泛采用均勻矩形網(wǎng)格劃分.理論上,三角形和四面體是二維和三維空間的單純形,可以剖分任意復(fù)雜的幾何形狀.因三角剖分具有良好的靈活性和穩(wěn)定性,20世紀(jì)80年代后,對(duì)三角剖分的研究飛速發(fā)展,除了在有限元分析,流體力學(xué)等傳統(tǒng)領(lǐng)域大放光彩外,在模式識(shí)別,虛擬現(xiàn)實(shí),計(jì)算機(jī)視覺等領(lǐng)域也得到廣泛的應(yīng)用.

本文采用新提出的基于德勞內(nèi)三角剖分的空間網(wǎng)格化方法(Delaunay triangulation spatial gridding,DTSG)[14].DTSG方法利用傳感器節(jié)點(diǎn)和四個(gè)邊界點(diǎn)作為原始網(wǎng)格點(diǎn),對(duì)感知區(qū)域進(jìn)行初步的德勞內(nèi)三角剖分,然后依次添加各個(gè)德勞內(nèi)三角形的重心作為新的網(wǎng)格節(jié)點(diǎn),重新對(duì)感知區(qū)域進(jìn)行德勞內(nèi)三角剖分,如此迭代分裂,直至網(wǎng)格點(diǎn)個(gè)數(shù)滿足預(yù)設(shè)大小.相比均勻矩形網(wǎng)格,其具有靈活、網(wǎng)格多分辨率、網(wǎng)格密度自適應(yīng)的特點(diǎn).Lin等[14]的研究顯示,統(tǒng)計(jì)平均意義下,DTSG網(wǎng)格劃分方法的定位性能優(yōu)于傳統(tǒng)的均勻矩形網(wǎng)格劃分方法.而實(shí)際中,傳感器的布置符合一定的先驗(yàn)知識(shí),如在無線電監(jiān)控中,固定監(jiān)測(cè)站點(diǎn)和移動(dòng)監(jiān)測(cè)平臺(tái)往往布置在非法電臺(tái)出現(xiàn)機(jī)率大的區(qū)域.所以,這種由傳感器節(jié)點(diǎn)位置生成網(wǎng)格的空間劃分方法更切合實(shí)際應(yīng)用.圖1給出了M=50,N=441設(shè)定下DTSG網(wǎng)格劃分結(jié)果.其中黑色圓點(diǎn)為隨機(jī)布置的傳感器節(jié)點(diǎn),灰色圓點(diǎn)為依據(jù)DTSG算法生成的網(wǎng)格節(jié)點(diǎn),五角星為目標(biāo)發(fā)射源.圖1中的目標(biāo)發(fā)射源節(jié)點(diǎn)用于示意定位模型,由DTSG方法可知網(wǎng)格劃分與目標(biāo)無關(guān).

圖1 基于DTSG的三角網(wǎng)格劃分Fig.1 Triangulation grid using DTSG

1.2 基于壓縮感知的多目標(biāo)定位模型

由于K?N,所以目標(biāo)的估計(jì)位置在空域上具有稀疏性.根據(jù)壓縮感知理論,多目標(biāo)問題可以抽象為通過M維接收信號(hào)強(qiáng)度的有噪測(cè)量(噪聲為測(cè)量噪聲n,近似為高斯噪聲),重建出N維空間中的K稀疏位置矢量的稀疏近似問題.模型為

其中,A=ΦΨ稱為傳感矩陣,是一個(gè)過完備字典.在模型(1)中,我們用網(wǎng)格點(diǎn)來近似真實(shí)的目標(biāo)位置.各參數(shù)的意義如下:

x=(x1,x2,···,xN)T為K稀疏矢量,編碼了目標(biāo)在網(wǎng)格點(diǎn)中的近似位置.如果目標(biāo)被近似到第i個(gè)網(wǎng)格點(diǎn)上時(shí),xi為與目標(biāo)功率有關(guān)的正數(shù)C,否則為0.

2)基于RSS的稀疏基矩陣Ψ∈RN×N

Ψ=[ψ1,ψ2,···,ψN]的每一列ψj代表所有網(wǎng)格點(diǎn)對(duì)網(wǎng)格點(diǎn)j處目標(biāo)的RSS測(cè)量.在不考慮信號(hào)增益的條件下,網(wǎng)格點(diǎn)j處目標(biāo)在網(wǎng)格點(diǎn)i上的接收信號(hào)強(qiáng)度滿足空間傳播的衰落模型[10]

其中,P0為信號(hào)發(fā)射功率,Ke為環(huán)境衰減因子,di,j為網(wǎng)格點(diǎn)j到網(wǎng)格點(diǎn)i的物理距離,d0為近場(chǎng)參考距離.α為快衰落的影響因子,β為陰影衰落的影響因子.顯而易見,Ψi,j=RSS(di,j).不同于壓縮感知原理中的稀疏基矩陣,例如離散余弦變換基、快速傅里葉變換基、離散小波變換基等,在多目標(biāo)定位模型(1)中的稀疏基矩陣Ψ很可能不是N維空間的一個(gè)基矩陣,即.

3)測(cè)量矩陣Φ∈RM×N

測(cè)量矩陣表示網(wǎng)格點(diǎn)中的傳感器部署方案.多目標(biāo)定位問題中,稀疏基矩陣Φ的前M列為傳

測(cè)量結(jié)果矢量y為M個(gè)傳感器的實(shí)際RSS測(cè)量結(jié)果.y=(y1,y2,···,yM)T中的任一元素yi代表第i個(gè)傳感器感知到的所有目標(biāo)的功率疊加結(jié)果.

1.3 模型參數(shù)的約束關(guān)系

在多目標(biāo)定位問題中,研究者感興趣的問題是需要多少個(gè)接收傳感器才能成功定位給定數(shù)目的目標(biāo)發(fā)射源?網(wǎng)格劃分越密集,是否定位精度會(huì)越高?借由壓縮感知理論,可以獲得關(guān)于這些問題的初步結(jié)論.

對(duì)于無噪聲壓縮感知方程y=A x,文獻(xiàn)[11]證明,若M≥O(Klg(N/K))且A滿足(2K,σ)的RIP條件,則范數(shù)最小化問題

的解為,若x是嚴(yán)格K稀疏信號(hào),則;若x是非嚴(yán)格K稀疏信號(hào),則能重建出x最主要的K個(gè)系數(shù).當(dāng)y受到噪聲污染時(shí),壓縮感知方程(1)的范數(shù)最小化解的重建誤差為,其中c0,c1為很小的正常數(shù),為y的重建允許誤差范圍,為無噪聲時(shí)的重建誤差.

Zhang等[11]證明了多目標(biāo)定位模型(1)的傳感矩陣A以大概率滿足RIP條件.所以從壓縮感知的重構(gòu)的角度來看,給定網(wǎng)格劃分結(jié)果確定了A的構(gòu)成,而A滿足的RIP條件階數(shù)又進(jìn)一步確定了在當(dāng)前傳感矩陣下能夠重構(gòu)出的最大目標(biāo)數(shù)K.同時(shí),為了重構(gòu)出稀疏位置矢量x,傳感器個(gè)數(shù)需滿足M≥O(Klg(N/K)).

在多目標(biāo)定位問題中,目標(biāo)位置的參數(shù)空間是連續(xù)的.基于壓縮感知的定位方法通過把參數(shù)空間網(wǎng)格離散化獲得對(duì)目標(biāo)位置的網(wǎng)格點(diǎn)近似估計(jì),然后由這些網(wǎng)格點(diǎn)構(gòu)成有限離散的過完備字典(即傳感矩陣A).網(wǎng)格劃分越精細(xì),網(wǎng)格點(diǎn)和真實(shí)目標(biāo)之間的誤差就越小,但過密的網(wǎng)格會(huì)造成稀疏基字典中原子間的相關(guān)性越強(qiáng),進(jìn)而使得壓縮感知的重構(gòu)性能下降[15],有如下定理[12].

定理1[12].令A(yù)∈RM×N為一個(gè)過完備字典,為其第j列,定義相干性(Coherence)μ(A)為

令K≤1+1/16u,當(dāng)M≥O(Klg(N/K))時(shí),任何K稀疏向量x可以從測(cè)量 y=Ax中通過求解式(4)以大概率恢復(fù).

Cevher等[12]的研究表明,在基于壓縮感知的多目標(biāo)定位場(chǎng)景中,μ(A)依賴于?/2D.其中?為網(wǎng)格精度,D為網(wǎng)格點(diǎn)和傳感器之間的最大距離(由傳感器部署和網(wǎng)格劃分共同決定).從而,?決定能夠成功定位的目標(biāo)數(shù)的下界,而D決定其上界.

另一方面,為了緩解密集網(wǎng)格劃分造成的傳感矩陣各列之間的強(qiáng)相關(guān)性對(duì)壓縮感知重建性能的影響,Feng等[10]提出一種基于正交的預(yù)處理方法降低了原始傳感矩陣各列之間的相關(guān)性.此后,這種預(yù)處理方法被研究者廣泛使用[10,14,16],下面對(duì)基于正交的預(yù)處理方法做出了詳細(xì)介紹,并證明在有噪情況下,其本質(zhì)上放大了噪聲的影響,降低了信噪比.

1.4 基于正交的預(yù)處理方法及其不足

定義1(預(yù)處理算子T).給定模型,定義線性預(yù)處理算子為T=QA?.其中,A?表示A的偽逆,Q=orth(AT)T表示對(duì)矩陣A的規(guī)范正交化操作.

其中,V(:,1:r)為正交矩陣V的前r列構(gòu)成的子矩陣.可以證明,正交矩陣的隨機(jī)子矩陣滿足RIP條件[17].下文中,稱模型(1)為原始模型,模型(7)為預(yù)處理模型,相應(yīng)地,A稱為原始傳感矩陣,Q稱為預(yù)處理傳感矩陣.

可見,相對(duì)原始傳感矩陣A,預(yù)處理傳感矩陣Q的列間相關(guān)性已被大大降低.但預(yù)處理算子T并不是一個(gè)無損操作.從原始模型(1)到預(yù)處理模型(7),相對(duì)信號(hào)功率,預(yù)處理算子T放大了噪聲水平,即預(yù)處理算子T削弱了信噪比(Signal to noise ratio,SNR),有如下定理.

定義2(信噪比SNR).給定模型 y=A x + n,x為隨機(jī)向量.其中信號(hào)為A x,噪聲n～ N(0,σ2I).模型信噪比定義為

定理 2.給定模型,其中A∈為隨機(jī)向量且各分量xi滿足i.i.d.條件.模型信噪比為SNR1.對(duì)應(yīng)預(yù)處理模型為,模型信噪比為SNR2. 如果存在,則SNR2≤SNR1.

證明.A=UΣ1VT.其中,

si為A的奇異值.

所以

由Cauchy-Schwarz不等式,有

綜上所述

等號(hào)成立的條件為:A的所有奇異值都為1.□

在多目標(biāo)定位模型(1)中,按照空間傳播損耗模型構(gòu)建的原始傳感矩陣A,其奇異值一般遠(yuǎn)小于1,根據(jù)定理2,經(jīng)過預(yù)處理算子T處理后,預(yù)處理模型(7)的信噪比將遠(yuǎn)小于原始模型(1)的信噪比.

1.5 討論

由上述分析可知,密集劃分網(wǎng)格會(huì)造成A各列間的強(qiáng)相關(guān)性,進(jìn)而影響重建性能.而文獻(xiàn)中為降低列間相關(guān)性而采取的正交預(yù)處理操作又被證明是放大噪聲影響,降低模型信噪比.然而,對(duì)于定位場(chǎng)景,只有目標(biāo)附近的字典原子才會(huì)對(duì)真實(shí)的信號(hào)構(gòu)成具有明顯貢獻(xiàn),遠(yuǎn)離目標(biāo)的位置的原子劃分并不會(huì)給定位帶來益處.所以,對(duì)于給定的網(wǎng)格化空間和相應(yīng)的過完備字典A,可以將觀測(cè)子空間視為信號(hào)子空間和噪聲子空間的疊加.

所以,本文的主要?jiǎng)訖C(jī)為以貪婪重建的方式,利用多目標(biāo)定位場(chǎng)景中隱含的結(jié)構(gòu)信息,從觀測(cè)子空間中分離出信號(hào)子空間,降低測(cè)量噪聲和網(wǎng)格密集劃分所帶來的強(qiáng)相關(guān)性的影響,提升貪婪恢復(fù)的定位準(zhǔn)確性.更具體地,原始模型(1)中隱藏著豐富的結(jié)構(gòu)信息,預(yù)處理模型(7)適合于貪婪求解,利用原始模型(1)和預(yù)處理模型(7)進(jìn)行聯(lián)合迭代貪婪定位,將獲得更優(yōu)異的定位表現(xiàn).

2 層級(jí)貪婪匹配追蹤定位算法

本節(jié)首先分析多目標(biāo)定位場(chǎng)景中隱含的結(jié)構(gòu)信息.其次,利用這些結(jié)構(gòu)信息提出一種分層貪婪匹配追蹤的多目標(biāo)定位方法(HGMP).最后,對(duì)所提算法的收斂性和計(jì)算復(fù)雜度做出分析.

2.1 多目標(biāo)定位場(chǎng)景中的結(jié)構(gòu)信息

1)團(tuán)塊模式

原始模型(1)是對(duì)多目標(biāo)定位問題的網(wǎng)格點(diǎn)近似,真實(shí)的目標(biāo)位置可能分布在感知區(qū)域的任何位置,不一定精確地在網(wǎng)格點(diǎn)上.所以,接收信號(hào)投影到網(wǎng)格空間上的能量將分散在真實(shí)目標(biāo)附近的原子團(tuán)上.迭代過程中,殘差投影到網(wǎng)格空間上的能量將分散在對(duì)當(dāng)前殘差貢獻(xiàn)最大目標(biāo)附近的原子團(tuán)上.具體地,在真實(shí)目標(biāo)位置附近的網(wǎng)格點(diǎn)上,壓縮感知恢復(fù)系數(shù)或殘差在網(wǎng)格空間上的投影具有相近的取值,且幅度明顯高于遠(yuǎn)離目標(biāo)位置的網(wǎng)格點(diǎn)上的,稱這種模式為團(tuán)塊模式.圖2(a)和2(b)分別展示的是恢復(fù)系數(shù)在網(wǎng)格點(diǎn)索引集上和網(wǎng)格空間上的團(tuán)塊模式.Yang等[16]注意到了恢復(fù)系數(shù)的團(tuán)塊模式,其在BP算法的定位結(jié)果上利用KNN聚類對(duì)恢復(fù)位置進(jìn)行加權(quán)平均,鑒于BP算法O(N3)的計(jì)算復(fù)雜度,其很難被應(yīng)用到實(shí)際中;圖2(c)展示的是在原始傳感矩陣A上在OMP算法迭代過程中殘差的團(tuán)塊模式,可以清晰看到,左邊的目標(biāo)對(duì)當(dāng)前殘差貢獻(xiàn)最大,其附近的原子團(tuán)呈現(xiàn)出明顯的團(tuán)塊模式;圖2(d)展示的是預(yù)處理傳感矩陣Q上OMP算法迭代過程中殘差在網(wǎng)格空間上的投影,由于基于正交的預(yù)處理操作打亂了原始傳感矩陣A中的相關(guān)性,所以不再具有明顯的團(tuán)塊模式.本文研究OMP算法迭代過程中殘差在原始傳感矩陣A的團(tuán)塊模式.

2)冗余信息

如前所述,為了在多目標(biāo)定位問題中應(yīng)用貪婪類壓縮感知恢復(fù)算法,文獻(xiàn)中常采用預(yù)處理算子T.數(shù)學(xué)上,T是一個(gè)不可逆算子,它把M維非稀疏矢量y映射成r維(r≤M)矢量 z ,再通過z重建N維K稀疏矢量x.前文的分析顯示,T放大噪聲的影響,降低模型信噪比.此外,預(yù)處理傳感矩陣Q是一個(gè)正交矩陣的子矩陣,相對(duì)原始傳感矩陣而言,其列之間的相關(guān)性已被大大降低.所以相對(duì)原始模型(1),預(yù)處理模型損失了冗余的信息.對(duì)于一個(gè)系統(tǒng)來說,冗余雖然帶來有效性的降低,但是另一方面,卻是系統(tǒng)可靠性的重要保障.在多目標(biāo)定位問題中,這種冗余信息的損失可以從A和Q的列相關(guān)性中得到解釋.A中的每一列aj代表所有傳感器對(duì)網(wǎng)格點(diǎn)j處目標(biāo)的RSS測(cè)量,空域中網(wǎng)格點(diǎn)i和網(wǎng)格點(diǎn)j距離越近,就越相關(guān).所以A的列之間的相關(guān)性具有清晰的物理意義.作為這種相關(guān)性在殘差投影上的反映,投影結(jié)果也會(huì)在空域上呈現(xiàn)出清晰的相關(guān)性,如圖2(c)所示,殘差在原始傳感矩陣A上的投影呈現(xiàn)出清晰的團(tuán)塊模式.與此相反,預(yù)處理傳感矩陣Q是正交矩陣V的子矩陣,Q的列相關(guān)性已經(jīng)無法直接體現(xiàn)空域上網(wǎng)格點(diǎn)間的相關(guān)性.如圖2(d)所示,殘差在傳感矩陣Q上的投影無清晰的團(tuán)塊模式.

2.2 算法步驟

提出的HGMP算法是一種層級(jí)的貪婪算法,利用多目標(biāo)定位場(chǎng)景中的結(jié)構(gòu)信息,具有線性計(jì)算復(fù)雜度和很好的可解釋性.HGMP算法的思想是以貪婪的方式,逐步發(fā)掘多目標(biāo)定位問題中的殘差在原始傳感矩陣中投影的團(tuán)塊模式,進(jìn)而利用預(yù)處理模型獲得貪婪恢復(fù).算法特征為:全局估計(jì)層獲得目標(biāo)可能位置的全局估計(jì),稀疏恢復(fù)層利用全局估計(jì)信息進(jìn)行目標(biāo)稀疏位置矢量壓縮感知貪婪重建.有以下核心算法步驟.

輸入.測(cè)量結(jié)果矢量y,原始感知矩陣A,目標(biāo)數(shù)K;

圖2 多目標(biāo)定位中的團(tuán)塊模式Fig.2 Cluster pattern in multi-target localization

輸出.目標(biāo)位置恢復(fù)點(diǎn)集P,x的K稀疏逼近;

初始化.候選集?←φ,殘差相關(guān)集Λ←φ,刪除集?←φ,殘差v←y,格點(diǎn)索引集N←{1,2,···,N};

預(yù)處理.計(jì)算預(yù)處理感知矩陣Q,計(jì)算z←Ty;

全局估計(jì)層.迭代量i←1,循環(huán)執(zhí)行步驟1～5.

步驟1.尋找對(duì)當(dāng)前殘差貢獻(xiàn)最大的原子團(tuán);

步驟2.利用z和Q,在Λ中進(jìn)行局部正交匹配追蹤,得到Λ上的的恢復(fù)系數(shù)θ及其支撐集Π;

步驟3.對(duì)θ及其支撐集Π正則化,結(jié)果為;

步驟4.迭代更新.;

步驟5.如果i≤K,進(jìn)入下一次迭代,返回步驟1;否則,進(jìn)入稀疏恢復(fù)層,執(zhí)行步驟6;

稀疏恢復(fù)層.

步驟6.擴(kuò)大候選集

步驟7.利用z和Q,在候選集?中進(jìn)行正交匹配追蹤,得到x的K稀疏逼近及其支撐集P;其中,A?表示A的索引集為?的列構(gòu)成的子矩陣.步驟1中,Th(v,A)是自適應(yīng)動(dòng)態(tài)門限,定義為

動(dòng)態(tài)門限能夠自適應(yīng)地提取對(duì)當(dāng)前殘差貢獻(xiàn)最大的原子團(tuán),噪聲水平高時(shí),殘差投影系數(shù)的方差較大,動(dòng)態(tài)門限自適應(yīng)地降低門限值來對(duì)抗噪聲的干擾,保證空域上與當(dāng)前殘差相關(guān)的目標(biāo)附近格點(diǎn)能夠被選入殘差相關(guān)集Λ.反之,當(dāng)噪聲水平低時(shí),動(dòng)態(tài)門限會(huì)提高門限值,減少選入殘差相關(guān)集Λ中弱相關(guān)格點(diǎn)的數(shù)目.

步驟3中,正則化[18]處理旨在從恢復(fù)系數(shù)中找出幅度相近且具有最大能量的子集.給定恢復(fù)系數(shù)θ及其下標(biāo)集合Π,在集合Π中尋找子集Π0,滿足

正則化操作選擇所有滿足要求的子集Π0中具有最大能量的Π0作為輸出.

步驟6中,Neighbor(j,D)指在空域上與格點(diǎn)j的歐氏距離小于門限值D的格點(diǎn)集合.

2.3 討論和分析

1)收斂性和抗噪聲性能

不同于一般的基于壓縮感知的定位方法,HGMP通過全局估計(jì)層獲得目標(biāo)可能位置的候選原子集合,然后稀疏重建層在候選原子集合上獲得最終的稀疏貪婪重建結(jié)果.這等效于從觀測(cè)空間中分離出信號(hào)子空間,然后在信號(hào)子空間上進(jìn)行貪婪正交匹配追蹤.在進(jìn)行全局估計(jì)時(shí),利用原始傳感矩陣A上殘差投影的團(tuán)塊模式,篩選出對(duì)當(dāng)前殘差貢獻(xiàn)最大的原子團(tuán),然后利用預(yù)處理傳感矩陣Q易于貪婪恢復(fù)的優(yōu)勢(shì)獲得局部正交匹配追蹤恢復(fù)結(jié)果,最后通過正則化處理從局部恢復(fù)結(jié)果中挑選出能量最大且貢獻(xiàn)類似的原子團(tuán).由正則化操作的分析[18]可知,最終全局估計(jì)層的輸出原子團(tuán)中一定包含OMP最終估計(jì)的K個(gè)原子,而稀疏重建層算法是子空間上的OMP算法.所以,在高信噪比條件下,HGMP將和OMP算法保持一致的收斂性.當(dāng)信噪比較低時(shí),OMP算法易受噪聲干擾,陷入局部最優(yōu)解中,而HGMP挑選原子的方法比OMP更為謹(jǐn)慎,每次挑選出原子團(tuán)而非單個(gè)最相關(guān)原子的模式也使得算法對(duì)噪聲的魯棒性更強(qiáng).全局估計(jì)層把可能位置從N縮小到候選集?,已經(jīng)極大地去除了噪聲造成的虛假目標(biāo)位置候選點(diǎn).所以,在此基礎(chǔ)上進(jìn)行貪婪恢復(fù)定位具有明顯的抗噪聲優(yōu)勢(shì).

2)計(jì)算復(fù)雜度

步驟1中投影操作實(shí)質(zhì)是矩陣向量乘法,門限比對(duì)操作實(shí)質(zhì)是一個(gè)遍歷過程,所以步驟1的復(fù)雜度為O(MN).

步驟2把殘差的能量正交投影到殘差相關(guān)集Λ上,實(shí)質(zhì)上是一個(gè)OMP子問題,復(fù)雜度為,其中C1=card(Λ)且C1?N.

步驟3中正則化操作實(shí)質(zhì)上是大小為C1的數(shù)集上的排序和二重循環(huán)遍歷過程,復(fù)雜度為.

步驟4在候選集?中更新殘差涉及一個(gè)最小二乘問題,復(fù)雜度為O(M2C2),其中C2=card(?),且滿足C2?N.

步驟6擴(kuò)大候選集,包含C2個(gè)遍歷格點(diǎn)集合的操作,復(fù)雜度為O(C2N).

稀疏恢復(fù)層是候選集上的稀疏度為K的OMP操作,其復(fù)雜度為O(KMC2).

綜上所述,當(dāng)N較小時(shí),HGMP算法計(jì)算復(fù)雜度不高于O(KMN2).當(dāng)N很大時(shí),HGMP算法的漸進(jìn)復(fù)雜度為O(KMN).

3 算法仿真

為驗(yàn)證所提算法在抗噪性能和計(jì)算復(fù)雜度方面的提升,采用經(jīng)典的OMP算法和BP算法作為對(duì)比.此外,為了對(duì)比算法在DTSG網(wǎng)格劃分和均勻矩形網(wǎng)格劃分上的性能,對(duì)于同樣的仿真參數(shù)設(shè)置,每一次蒙特卡洛仿真中在兩種網(wǎng)格上分別進(jìn)行定位.仿真的硬件環(huán)境為Intel Core i7-6700處理器,主頻3.4GHz,8GB內(nèi)存;軟件環(huán)境為Windows 10+MATLAB R2016a.

3.1 評(píng)價(jià)度量

平均定位正確率(Mean localization accuracy rate,MLAR).如果在距離真實(shí)目標(biāo)Ti小于1m的范圍內(nèi)能夠找到恢復(fù)點(diǎn),認(rèn)為目標(biāo)Ti被成功定位,恢復(fù)點(diǎn)被稱為目標(biāo)Ti的匹配恢復(fù)點(diǎn).把被成功定位的目標(biāo)個(gè)數(shù)#SuccessfulLocalizedTargets與總目標(biāo)個(gè)數(shù)#Targets的比值記為恢復(fù)的正確率.

平均定位誤差距離(Mean localization error distance,MLED)定義為目標(biāo)Ti的真實(shí)位置(xi,yi)和最近的匹配恢復(fù)點(diǎn)位置之間的平均歐氏距離,公式為

平均運(yùn)行時(shí)間(Mean run time,MRT)指每次蒙特卡洛仿真中算法運(yùn)行時(shí)間的平均值,以此來評(píng)價(jià)算法的時(shí)間復(fù)雜度.

3.2 仿真參數(shù)選擇

感知區(qū)域設(shè)為10m×10m的方形區(qū)域,網(wǎng)格點(diǎn)N=21×21,目標(biāo)數(shù)K=4.目標(biāo)有效全向輻射功率Pt=10dBm.稀疏基字典Ψ采用IEEE802.15.4標(biāo)準(zhǔn)中的室內(nèi)傳播損耗模型[14].

測(cè)量噪聲為高斯白噪聲,為了有效驗(yàn)證算法的定位性能,消除隨機(jī)因素的影響,取3000次仿真的均值作為實(shí)驗(yàn)結(jié)果(每一次仿真均重新撒布目標(biāo)和傳感器,重新構(gòu)造空間網(wǎng)格).

3.3 仿真結(jié)果和分析

下文中均勻矩形網(wǎng)格劃分簡(jiǎn)稱為矩形網(wǎng)格,DTSG網(wǎng)格劃分簡(jiǎn)稱為三角網(wǎng)格.

1)抗噪聲性能和計(jì)算復(fù)雜度

圖3和圖4分別給出了M=50時(shí),在均勻矩形網(wǎng)格劃分和DTSG網(wǎng)格劃分下各算法的平均定位正確率和平均定位誤差距離受信噪比的影響.可以看出:

圖3 噪聲對(duì)平均定位正確率的影響Fig.3 The in fluences of the noise level on MLAR

圖4 噪聲對(duì)平均定位誤差距離的影響Fig.4 The in fluences of the noise level on MLED

a)隨著信噪比的增加,各算法的平均定位正確率不斷上升,平均定位誤差距離不斷下降.當(dāng)SNR>25dB時(shí),BP和OMP的定位性能趨于收斂,當(dāng)SNR>22dB時(shí),HGMP的定位性能趨于收斂.由于基于壓縮感知的多目標(biāo)定位模型是對(duì)真實(shí)目標(biāo)位置的一個(gè)逼近模型,當(dāng)信噪比大于一定程度時(shí),多目標(biāo)定位問題中的測(cè)量噪聲不再是主要矛盾.對(duì)于圖3,限制MLAR繼續(xù)增加的主要因素為定義成功定位的精度(仿真中為1m)和網(wǎng)格精度(網(wǎng)格劃分帶來的模型逼近誤差,仿真中平均網(wǎng)格間距為0.5m);對(duì)于圖4,限制MLED繼續(xù)降低的主要因素為網(wǎng)格精度.

b)在統(tǒng)計(jì)平均意義上,對(duì)于BP算法和HGMP算法,DTSG三角網(wǎng)格劃分和傳統(tǒng)的均勻矩形網(wǎng)格劃分的定位性能保持一致;對(duì)于OMP,在同樣的噪聲水平下,三角網(wǎng)格劃分能實(shí)現(xiàn)比均勻矩形劃分更高的定位正確率和更低的定位誤差距離.

c)在噪聲占主要影響因素的前提下(SNR<25dB),通過在迭代過程中利用殘差的團(tuán)塊模式,限制在信號(hào)子空間上進(jìn)行貪婪重建,HGMP的定位正確率和定位誤差距離優(yōu)于BP的,遠(yuǎn)遠(yuǎn)優(yōu)于OMP的,顯示出良好的抗噪能力.

圖5 不同噪聲水平下的平均運(yùn)行時(shí)間Fig.5 MRT under different noise level

圖5給出上述實(shí)驗(yàn)過程中各算法的平均運(yùn)行時(shí)間.HGMP算法的計(jì)算復(fù)雜度顯著低于BP算法.隨著信噪比的提高,HGMP的平均運(yùn)行時(shí)間降低.這是因?yàn)樵肼曀皆降?殘差投影的團(tuán)塊結(jié)構(gòu)越明顯,投影方差越小,每次選入殘差相關(guān)集Λ中的格點(diǎn)數(shù)目也越少,從而運(yùn)行時(shí)間也越少.同樣的噪聲水平下,HGMP算法在三角網(wǎng)格劃分上的運(yùn)行時(shí)間要高于矩形網(wǎng)格劃分的,近似是矩形網(wǎng)格劃分的常數(shù)倍.這是因?yàn)橛?jì)算殘差相關(guān)集采取的動(dòng)態(tài)門限函數(shù)和殘差投影標(biāo)準(zhǔn)差相關(guān),由于三角網(wǎng)格劃分的非均勻性和非規(guī)則性,其投影方差大于均勻矩形網(wǎng)格劃分的,導(dǎo)致三角網(wǎng)格中的殘差相關(guān)集包含更多的格點(diǎn),使得三角網(wǎng)格上的運(yùn)行時(shí)間高于矩形網(wǎng)格上的.相對(duì)BP算法和HGMP算法,OMP只包含投影、最小二乘、更新殘差三個(gè)步驟,所以其計(jì)算最為簡(jiǎn)單,但從圖3和圖4可以看出,OMP低計(jì)算復(fù)雜度的代價(jià)是對(duì)噪聲敏感,當(dāng)SNR較低時(shí),定位性能低于HGMP和BP.

2)傳感器個(gè)數(shù)的影響

圖6 傳感器個(gè)數(shù)對(duì)平均定位正確率的影響Fig.6 The in fluences of sensor numbers on MLAR

圖7 傳感器個(gè)數(shù)對(duì)平均定位誤差距離的影響Fig.7 The in fluences of sensor numbers on MLED

圖6和圖7分別給出了SNR=25dB條件下,傳感器數(shù)目為6,8,10,15,30,40,50時(shí),均勻矩形網(wǎng)格劃分和DTSG網(wǎng)格劃分下各算法的平均定位正確率和平均定位誤差距離.可以清晰看出,隨著傳感器的個(gè)數(shù)不斷增加,各算法的平均定位正確率不斷上升,平均定位誤差距離不斷下降,但變化趨于平緩.對(duì)于K=4,M=441,理論上需要傳感器的下界為Klg(N/K)≈19.從圖6和圖7可以看出,當(dāng)傳感器個(gè)數(shù)小于20時(shí),所有算法的平均定位誤差距離都大于1m,平均定位正確率小于70%.當(dāng)傳感器個(gè)數(shù)大于30時(shí),除了在矩形網(wǎng)格劃分上的OMP算法外,其他算法的平均定位誤差距離都小于1m,相應(yīng)的平均定位正確率大于82%.統(tǒng)計(jì)意義上,對(duì)于1m范圍的成功定位精度,經(jīng)驗(yàn)值和理論值之間的差距為11個(gè)傳感器.其次,對(duì)于同一傳感器數(shù)目,HGMP在DTSG三角網(wǎng)格劃分和均勻矩形網(wǎng)格劃分下都顯示出優(yōu)于其他算法的定位性能,且在DTSG三角網(wǎng)格劃分下的HGMP定位性能最優(yōu).

4 結(jié)論

本文給出了一種新穎的基于壓縮感知的多目標(biāo)分層貪婪匹配定位方法(HGMP),并證明了文獻(xiàn)中廣泛采用的正交預(yù)處理操作降低定位信噪比.所提算法從觀測(cè)子空間中分離出信號(hào)子空間,利用原始傳感矩陣和預(yù)處理傳感矩陣進(jìn)行聯(lián)合迭代貪婪定位,提供一種利用多目標(biāo)定位問題中豐富的結(jié)構(gòu)信息實(shí)現(xiàn)魯棒性貪婪定位的層級(jí)架構(gòu).理論分析和計(jì)算仿真表明,HGMP定位算法具有漸進(jìn)線性復(fù)雜度O(KMN).相同信噪比下,HGMP在不同網(wǎng)格劃分上均展示出更好的定位性能.