無線傳感器網絡下基于壓縮感知的多目標分層貪婪匹配定位

游康勇 楊立山 郭文彬

隨著無線通信技術的進步以及無線傳感器網絡(Wireless sensor network,WSN)和物聯網等的高速發展,如何精確定位監控區域內的多個目標已經成為信號處理領域中極具挑戰和實際意義的問題.多目標定位可以應用于諸多場景,例如,WSN中傳感器節點定位[1]、室內定位[2]、污染源定位[3]、無線電監控等.

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

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

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

鑒于此,本文針對多目標定位問題,給出了明確的系統模型,證明預處理方法削弱模型信噪比,提出一種新穎的基于壓縮感知的層級貪婪匹配追蹤定位算法(Hierarchical greedy matching pursuit,HGMP).所提算法具有線性計算復雜度,提供了一種利用多目標定位場景中的結構信息實現快速貪婪定位的層級架構,提高了多目標定位系統的定位精度和抗噪聲性能.

1 系統模型

本節首先闡述基于德勞內三角剖分的空間網格化方法,介紹基于壓縮感知的多目標定位模型及各參數的意義.其次,從壓縮感知理論出發,討論定位問題中目標數、傳感器數目、網格數目三者的相互制約關系.接著,證明文獻中廣泛采用的基于正交的預處理操作本質上降低信噪比.最后,在討論部分闡述本文的主要動機.

1.1 空間德勞內三角網格劃分

不失一般性,設已知存在K個目標的二維感知區域被離散成N個網格點(目標服從感知區域內的連續均勻分布),其中隨機均勻散布M個傳感器(位置已知),每個傳感器測量該點處的接收信號強度(Received signal strength,RSS).在空間網格點數目足夠大的前提下,可以用網格點近似估計目標的位置來確定K個目標發射源的位置.

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

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

圖1 基于DTSG的三角網格劃分Fig.1 Triangulation grid using DTSG

1.2 基于壓縮感知的多目標定位模型

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

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

x=(x1,x2,···,xN)T為K稀疏矢量,編碼了目標在網格點中的近似位置.如果目標被近似到第i個網格點上時,xi為與目標功率有關的正數C,否則為0.

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

Ψ=[ψ1,ψ2,···,ψN]的每一列ψj代表所有網格點對網格點j處目標的RSS測量.在不考慮信號增益的條件下,網格點j處目標在網格點i上的接收信號強度滿足空間傳播的衰落模型[10]

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

3)測量矩陣Φ∈RM×N

測量矩陣表示網格點中的傳感器部署方案.多目標定位問題中,稀疏基矩陣Φ的前M列為傳

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

1.3 模型參數的約束關系

在多目標定位問題中,研究者感興趣的問題是需要多少個接收傳感器才能成功定位給定數目的目標發射源?網格劃分越密集,是否定位精度會越高?借由壓縮感知理論,可以獲得關于這些問題的初步結論.

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

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

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

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

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

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

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

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

1.4 基于正交的預處理方法及其不足

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

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

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

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

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

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

si為A的奇異值.

所以

由Cauchy-Schwarz不等式,有

綜上所述

等號成立的條件為:A的所有奇異值都為1.□

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

1.5 討論

由上述分析可知,密集劃分網格會造成A各列間的強相關性,進而影響重建性能.而文獻中為降低列間相關性而采取的正交預處理操作又被證明是放大噪聲影響,降低模型信噪比.然而,對于定位場景,只有目標附近的字典原子才會對真實的信號構成具有明顯貢獻,遠離目標的位置的原子劃分并不會給定位帶來益處.所以,對于給定的網格化空間和相應的過完備字典A,可以將觀測子空間視為信號子空間和噪聲子空間的疊加.

所以,本文的主要動機為以貪婪重建的方式,利用多目標定位場景中隱含的結構信息,從觀測子空間中分離出信號子空間,降低測量噪聲和網格密集劃分所帶來的強相關性的影響,提升貪婪恢復的定位準確性.更具體地,原始模型(1)中隱藏著豐富的結構信息,預處理模型(7)適合于貪婪求解,利用原始模型(1)和預處理模型(7)進行聯合迭代貪婪定位,將獲得更優異的定位表現.

2 層級貪婪匹配追蹤定位算法

本節首先分析多目標定位場景中隱含的結構信息.其次,利用這些結構信息提出一種分層貪婪匹配追蹤的多目標定位方法(HGMP).最后,對所提算法的收斂性和計算復雜度做出分析.

2.1 多目標定位場景中的結構信息

1)團塊模式

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

2)冗余信息

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

2.2 算法步驟

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

輸入.測量結果矢量y,原始感知矩陣A,目標數K;

圖2 多目標定位中的團塊模式Fig.2 Cluster pattern in multi-target localization

輸出.目標位置恢復點集P,x的K稀疏逼近;

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

預處理.計算預處理感知矩陣Q,計算z←Ty;

全局估計層.迭代量i←1,循環執行步驟1～5.

步驟1.尋找對當前殘差貢獻最大的原子團;

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

步驟3.對θ及其支撐集Π正則化,結果為;

步驟4.迭代更新.;

步驟5.如果i≤K,進入下一次迭代,返回步驟1;否則,進入稀疏恢復層,執行步驟6;

稀疏恢復層.

步驟6.擴大候選集

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

動態門限能夠自適應地提取對當前殘差貢獻最大的原子團,噪聲水平高時,殘差投影系數的方差較大,動態門限自適應地降低門限值來對抗噪聲的干擾,保證空域上與當前殘差相關的目標附近格點能夠被選入殘差相關集Λ.反之,當噪聲水平低時,動態門限會提高門限值,減少選入殘差相關集Λ中弱相關格點的數目.

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

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

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

2.3 討論和分析

1)收斂性和抗噪聲性能

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

2)計算復雜度

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

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

步驟3中正則化操作實質上是大小為C1的數集上的排序和二重循環遍歷過程,復雜度為.

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

步驟6擴大候選集,包含C2個遍歷格點集合的操作,復雜度為O(C2N).

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

綜上所述,當N較小時,HGMP算法計算復雜度不高于O(KMN2).當N很大時,HGMP算法的漸進復雜度為O(KMN).

3 算法仿真

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

3.1 評價度量

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

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

平均運行時間(Mean run time,MRT)指每次蒙特卡洛仿真中算法運行時間的平均值,以此來評價算法的時間復雜度.

3.2 仿真參數選擇

感知區域設為10m×10m的方形區域,網格點N=21×21,目標數K=4.目標有效全向輻射功率Pt=10dBm.稀疏基字典Ψ采用IEEE802.15.4標準中的室內傳播損耗模型[14].

測量噪聲為高斯白噪聲,為了有效驗證算法的定位性能,消除隨機因素的影響,取3000次仿真的均值作為實驗結果(每一次仿真均重新撒布目標和傳感器,重新構造空間網格).

3.3 仿真結果和分析

下文中均勻矩形網格劃分簡稱為矩形網格,DTSG網格劃分簡稱為三角網格.

1)抗噪聲性能和計算復雜度

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

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

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

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

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

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

圖5 不同噪聲水平下的平均運行時間Fig.5 MRT under different noise level

圖5給出上述實驗過程中各算法的平均運行時間.HGMP算法的計算復雜度顯著低于BP算法.隨著信噪比的提高,HGMP的平均運行時間降低.這是因為噪聲水平越低,殘差投影的團塊結構越明顯,投影方差越小,每次選入殘差相關集Λ中的格點數目也越少,從而運行時間也越少.同樣的噪聲水平下,HGMP算法在三角網格劃分上的運行時間要高于矩形網格劃分的,近似是矩形網格劃分的常數倍.這是因為計算殘差相關集采取的動態門限函數和殘差投影標準差相關,由于三角網格劃分的非均勻性和非規則性,其投影方差大于均勻矩形網格劃分的,導致三角網格中的殘差相關集包含更多的格點,使得三角網格上的運行時間高于矩形網格上的.相對BP算法和HGMP算法,OMP只包含投影、最小二乘、更新殘差三個步驟,所以其計算最為簡單,但從圖3和圖4可以看出,OMP低計算復雜度的代價是對噪聲敏感,當SNR較低時,定位性能低于HGMP和BP.

2)傳感器個數的影響

圖6 傳感器個數對平均定位正確率的影響Fig.6 The in fluences of sensor numbers on MLAR

圖7 傳感器個數對平均定位誤差距離的影響Fig.7 The in fluences of sensor numbers on MLED

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

4 結論

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