無線傳感器網絡中基于壓縮感知的動態目標定位算法

孫保明　郭　艷李　寧　錢　鵬

（解放軍理工大學通信工程學院南京210007）

?

無線傳感器網絡中基于壓縮感知的動態目標定位算法

孫保明郭艷*李寧錢鵬

（解放軍理工大學通信工程學院南京210007）

傳統的動態目標定位算法需要采集、存儲和處理大量數據，并不適用于能量受限的無線傳感器網絡。針對該缺陷，該文提出一種基于壓縮感知的動態目標定位算法。該算法利用目標的運動規律設計稀疏表示基，從而將動態目標定位問題轉化為稀疏信號恢復問題。針對傳統觀測矩陣難以實現的缺陷，該算法設計可實現且與稀疏表示基相關性低的稀疏觀測矩陣，從而保證了算法的重構性能。該算法的特點是可利用較少的數據采集實現動態目標定位，從而大大延長無線傳感器網絡的壽命。仿真結果表明，該文所提出的基于壓縮感知的動態目標定位算法具有較好的定位性能。

無線傳感器網絡；動態目標定位；壓縮感知；稀疏表示基；觀測矩陣

1　引言

無線傳感器網絡是由大量廉價的具有感知、通信和計算能力的微型傳感器形成的多跳自組織網絡。其目的是感知、采集和處理網絡覆蓋區域中各種感知對象的信息，例如溫度、壓力、濕度、噪聲、光強度等物理信號。與傳統的信息獲取方式相比，無線傳感器網絡具有自組織、廉價、可擴展性強以及能在惡劣環境下正常工作等優點，在國防軍事、城市管理、生物醫療、環境監測和反恐救災等眾多領域具有極為廣闊的應用前景［1］。

在無線傳感器網絡的各種應用中，隱藏著一個共同的必備信息位置信息。位置信息至關重要，傳感器感知的數據只有在獲得位置信息后才具有更高的使用價值［2］。在實際生活中，人們不僅關心某一監測事件的發生，而且關心該事件發生的位置，只有知道位置信息后才能采取相應的應對措施。例如森林火災報警必須獲取火災的具體位置，入侵者監測必須實時掌握入侵者的運動軌跡，毒氣泄漏時必須知道有害氣體的漫延范圍等。復雜多變的應用環境導致傳感器網絡拓撲具有高度的動態性，若要實現動態目標實時定位，必須頻繁地感知和處理大量信息，這對信號采樣速率和數據處理速度提出了較高要求，使得傳統的信號采樣和數據處理方法“力不從心”。

壓縮感知（Com pressive Sensing，CS）技術［3，4］的出現為解決上述問題提供了新思路。作為信號處理領域的新興技術，壓縮感知基于信號的稀疏性，它通過低維空間的非相關觀測實現對高維信號的感知。壓縮感知理論表明，只要信號在某個變換基下是稀疏的，就可以用一個與變換基不相關的觀測矩陣對信號進行少量采樣，而這些少量的采樣值卻包含了重構該信號的足夠信息，通過求解一個優化問題就可以從這些采樣值中以高概率重構原信號。在壓縮感知理論中，信號的采樣與壓縮同時以低速率進行，對能量和計算能力的要求較低；而信號恢復是一個優化計算的過程，對能量和計算能力的要求較高。無獨有偶，在無線傳感器網絡動態目標定位中，負責信息采集的傳感器由于靠電池供電，能量及計算能力均受限，而負責信息處理的融合中心則沒有能量及計算能力的限制。因此，壓縮感知理論的這種天然特點仿佛是為無線傳感器網絡中動態目標定位問題“量身定制”的。

文獻［5］將目標所在的區域離散化為一個網格，通過探討目標位置與接收信號強度（Received Signal Strength，RSS）向量之間的關系，將定位問題轉化為RSS向量在某字典下的稀疏逼近問題，奠定了壓縮感知定位技術的基礎。但是該方法需要為每個傳感器構建一個稀疏字典，定位開銷較大。文獻［6］通過離散物理空間將每個目標的位置轉化為稀疏度為1的向量，從而將多目標定位問題轉化為多稀疏向量恢復問題，并利用壓縮感知技術進行定位。但該方法數據壓縮不充分，且需要事先知道目標的個數。文獻［7］研究了在目標數目未知情況下的多目標定位問題，將多個目標的位置轉化為一個稀疏向量，并設計了基于貪婪匹配追蹤的恢復算法。文獻［8］采用殘差最優匹配和多分辨率分析的方法對壓縮感知重構算法進行了改進，提高了定位精度，但是增加了恢復算法的計算復雜度。文獻［9，10］對感知矩陣分別進行LU分解和奇異值分解，得到的新感知矩陣有效地滿足了約束等距性條件，且該預處理方法不影響原信號的稀疏性，保證了算法的定位性能，但增加了算法復雜度和定位開銷。文獻［11］提出一種基于字典學習的壓縮感知室內定位方法。該方法首先利用K-SVD將無線電地圖（Radio Map，RM）分解為一個稀疏字典和一個稀疏表示矩陣的乘積，該稀疏表示矩陣的每一列對應著一個參考點。在線階段測得的RSS向量在稀疏字典中的表示系數與稀疏表示矩陣的某一列向量的相關性最小，該列對應的參考節點的位置即為目標的位置。文獻［12］提出一種壓縮感知與多邊測量技術相結合的無線傳感器網絡定位算法。該方法克服了目標只能在網格中心的局限性，但是增加了計算復雜度。文獻［13］設計一種基于梯度投影的兩步字典學習算法，利用該算法學習真實稀疏字典，從而消除環境變化造成的定位誤差。文獻［14，15］提出了一種非基于測距的壓縮感知定位方法。該方法通過測量傳感器感知范圍內目標的數量來實現定位，算法實現簡單，但定位精度很難得到保證。

以上的定位方法只考慮了靜態目標，而忽略了動態目標。基于此，本文提出了一種基于壓縮感知的動態目標定位算法。該算法通過時間離散化建立壓縮感知模型，利用目標的運動規律設計稀疏表示基，將動態目標定位問題轉化為稀疏信號恢復問題，利用較少信號采集實現動態目標精確定位，從而大大延長無線傳感器網絡壽命。

2　壓縮感知

圖1　壓縮感知模型

從y中恢復x是一個解線性方程組的問題，需要求解如式（1）所示的優化問題：

顯然，這是一個NP難問題。然而，當矩陣Φψ滿足有限等距性質（Restricted Isometry Property，RIP）［16］時，上述問題可以松弛為1e范數最小優化問題：

因此，對于給定的信號x，應該選擇合適的稀疏表示基ψ和觀測矩陣Φ；在保證信號x在ψ中的表示向量稀疏的同時，使ψ和Φ之間的相關性足夠小。

3　系統模型

為簡單起見，我們只考慮1維空間中的一個動態目標，相同的方法可以應用到多維空間中的多個目標。動態目標的位置在時域中是隨機且連續的，為了將其離散化，將時間劃分為T個時刻。一個動態目標在T個時刻的位置可表示為其中xi表示目標在第i個時刻的位置。傳統的動態定位方法假設目標在每個時刻內是靜止的，然后在每個時刻內用靜態方法實現定位。這種方法的精度取決于時間分辨率的大小，若要實現精確定位，需要頻繁地執行靜態定位算法，定位開銷較大。

實際上，目標的運動往往呈現某種規律，即目標的運動軌跡與運動速度在時域中均具有平滑性。這些規律為利用壓縮感知技術進行動態目標定位提供了契機。壓縮感知的兩大要素就是稀疏表示基和觀測矩陣。若存在一個稀疏表示基ψ，使得位置向量x稀疏，那么可以通過一個測量矩陣Φ對x進行欠采樣，并通過少量的采樣值恢復出位置向量x。值得說明的是，這里的采樣是指在抽樣時刻對目標進行靜態定位，采樣值為目標在若干個抽樣時刻的位置。因此，本文的目標就是設計合理的稀疏表示基和觀測矩陣，建立壓縮感知模型，利用少量時刻內的目標位置恢復所有時刻內的目標位置，如圖2所示。

圖2　動態目標定位模型

4　矩陣設計

4.1稀疏表示基設計

實際中，我們注意到目標的運動軌跡在時域內具有平滑性，即目標位置只有在少數時刻發生較大改變。因此，我們考慮如式（4）所示矩陣：

位置向量x在矩陣TM下的投影向量為

另外，我們還發現動態目標的速度在整個時域內也具有平滑性，即目標的速度只有在少量時刻發生顯著變化。因此，我們考慮如式（6）所示矩陣：

位置向量x在矩陣SM下的投影向量為

rS中的元素（xi-xi-1）-（xi+1-xi）近似為目標在兩個相鄰時刻的速度之差。因此，rS中只有少量元素較大，其他大部分元素可以忽略。位置向量x可稀疏表示為

4.2觀測矩陣設計

目前，壓縮感知理論大多采用隨機矩陣（例如高斯隨機矩陣）作為觀測矩陣。這類矩陣能夠保證以較大概率與稀疏表示基不相關，然而這類矩陣是非稀疏矩陣，不能應用于本文的定位場景。在本文的動態目標定位中，一次觀測相當于在某個抽樣時刻執行一次靜態定位算法，利用目標在若干時刻的位置恢復所有時刻的位置。顯然，一次觀測只能在一個時刻內進行；另外假設觀測值是精確的，每個抽樣時刻只需觀測一次［17］。因此，觀測矩陣是稀疏矩陣，即它的每行只有一個“1”，每列至多有一個“1”，其它元素全部為“0”。若它的元素，表明在第n個時刻進行第m次觀測。基于此，我們考慮如下兩種觀測矩陣：

（1）隨機稀疏觀測矩陣：隨機選擇若干個時刻進行觀測，記做RΦ。

（2）均勻稀疏觀測矩陣：均勻選擇若干個時刻進行觀測，記做UΦ。

5　性能分析

在壓縮感知中，實現信號重構需要滿足以下兩個條件：（1）信號在稀疏表示基下的表示向量足夠稀疏；（2）稀疏表示基與觀測矩陣不相關。本節將從這兩個角度分析所設計的稀疏表示基和觀測矩陣的性能。

5.1稀疏表示基的稀疏信號能力

實際中，信號x在稀疏表示基ψ下的表示系數r并非完全稀疏的，而是可壓縮的，即它的大部分元素接近于零。本文設計一種指標來衡量稀疏表示基的稀疏信號能力，即，其中ri表示向量r中的第i大元素表示向量s中的K個最大元素的能量；表示向量s的總能量。對于給定的參數K，該指標越大，稀疏表示基的稀疏信號能力越強。

本文分別采用模擬數據和實測數據來衡量稀疏表示基的稀疏信號能力，其中模擬數據通過隨機游走模型（Random W aypoint Model，RWM）獲得，實測數據［18］通過對不同地區若干志愿者的運動軌跡采集獲得，如表1所示。測試結果表明稀疏表示基Sψ的稀疏信號能力強于稀疏表示基Tψ，如圖3所示。當采用稀疏表示基Sψ時，最大的20個元素占據了所有信號中62.5%～91.4%的能量，這些信號的能量都集中在少量的大系數中。由此可見，稀疏表示基具有較強的稀疏信號能力。

表1　本文所采用的實測數據

5.2相關性

式（3）只能用來計算兩個正交基之間的相關性，而不能直接用來計算本文所設計的稀疏表示基和觀測矩陣之間的相關性。因此，這里采用非相關性［17］來間接反映稀疏表示基和觀測矩陣相關性的大小。對于給定的一組稀疏表示基和觀測矩陣它們之間的非相關性（），IψΦ定義為

其中iθ表示觀測矩陣Φ的第i個行向量在由稀疏表示基ψ各列張成的空間中的投影向量，即

表2分別顯示了不同稀疏表示基和觀測矩陣組合之間的非相關性。由表可知，本文所設計的稀疏表示基和觀測矩陣的非相關性較大，即相關性較小。當觀測矩陣Φ固定時，Sψ與Φ之間的非相關性大于Tψ與Φ之間的非相關性。當稀疏表示基ψ固定時，UΦ和ψ之間的非相關性幾乎等于RΦ與ψ之間的非相關性。然而，相對于RΦ，UΦ的觀測點更加均勻，能夠攜帶更多信息。而相對于UΦ，RΦ中的觀測點可以隨機選取，實際中不需要人為控制抽樣時刻，操作更加簡單。

表2　稀疏表示基與觀測矩陣的非相關性

6　仿真結果與分析

6.1仿真場景

我們采用前文所述的模擬數據和實測數據來驗證本文所提定位算法的性能。模擬數據由在100 m×100 m的區域中的20個目標隨機游走產生，時間間隔為1 s，最大速度為10 m/s，最小速度為2 m/s，暫停時間為10 s。為了方便與模擬數據進行比較，我們對實測數據中目標的運動范圍進行相應比例的縮放，使它的大小也為100m×100m。本文采用的性能指標為所有目標在所有時刻內的平均誤差，即

6.2恢復算法的影響

本節首先研究不同的恢復算法對定位性能的影響。本文考慮的恢復算法包括基追蹤（Basis Pursuit，BP），正交匹配追蹤（OrthogonalMatching Pursuit，OMP）和迭代加權最小二乘（Iterative Re-W eighted Least Squares，IRW LS）。在該實驗中，稀疏表示基采用，觀測矩陣采取，觀測次數M= 200，仿真結果如圖4所示。由圖可見，BP恢復算法優于OMP和IRW LS算法。這是因為BP運用線性規劃求解一個優化問題，而OMP和IRW LS都是通過貪婪迭代的方法獲得最優解，3種算法的計算復雜度將于6.5節進行討論。另外，在所有的實測數據中，New York軌跡的定位誤差最小；這是因為New York軌跡的稀疏性最好，如圖3所示。

6.3矩陣選擇的影響

圖5給出了不同的矩陣（稀疏表示基和觀測矩陣）選擇對定位性能的影響。從圖中可以看出，首先當觀測矩陣固定時，稀疏表示基優于稀疏表示基，這是因為的稀疏信號能力強于，如圖3所示。其次當稀疏表示基ψ固定時，均勻稀疏觀測矩陣優于隨機稀疏觀測矩陣，該現象與表2中的結論并不相符。這是因為恢復性能不僅與有關，還與觀測點的分布有關。觀測點分布越均勻，恢復性能越好，反之越差。在中，觀測點均勻選取，觀測值能夠涵蓋信號在較多時間段的信息；而在中，觀測點隨機選取，觀測值只能涵蓋信號在較少時間段的信息。

6.4測量噪聲的影響

圖3　稀疏表示基的稀疏信號能力

圖4　恢復算法對定位結果的影響

圖5　矩陣選擇對定位結果的影響

在實際測量中，傳感器不可避免地會受到周圍噪聲的影響。為了檢驗定位算法的魯棒性，我們在每個測量值中添加一個均值為0，方差為σ的高斯白噪聲N），定義信噪比為在該實驗中，稀疏表示基ψ采用，觀測矩陣采取。圖6顯示了在無噪聲，SNR=30 dB和SNR=20 dB情況下兩種數據的定位結果。

由圖6可見，對于所有的參數設置，定位誤差隨著測量次數的增加而降低，這是因為測量次數越大，信號恢復就越精確。另外，定位誤差隨著信噪比的降低而增大，這是因為噪聲越大，測量值就越不準確，信號恢復誤差就越大。在New York軌跡中，當信噪比SNR=20 dB，測量次數M=100時，定位誤差小于0.4m。由此可見本文提出的定位算法具有較強的魯棒性。

6.5與插值方法比較

為了檢驗本文所提定位算法的性能，我們仿真比較了該算法與傳統的基于樣條插值（Sp line Interpolation，SI）算法的定位效果，結果如圖7所示。由圖7可見，基于CS和SI的定位算法的誤差都隨著測量次數的增加而減少，這是因為觀測次數越多，獲得的原信號的信息也就越多。另外，基于CS的定位算法明顯優于基于SI的算法，這是因為基于SI的算法只是對信號進行簡單的插值，而基于CS的算法充分利用了信號的稀疏特性。

為了進一步檢驗本文所提定位算法的性能，我們仿真比較了，在某個定位精度指標約束下，基于CS和SI的定位算法所需要的最小測量次數。這里考慮0.1 m和0.2 m兩種精度指標，仿真結果如圖8所示。

由圖8可以看出，對于所有數據和方法，0.2 m約束下的最小測量次數都要小于0.1 m約束下的測量次數。另外，當約束和數據固定時，基于CS的定位算法所需的最小測量次數明顯小于基于SI的定位算法。因此，本文算法能夠利用較少的數據采集實現動態目標定位，從而大大延長無線傳感器網絡的壽命。

為了分析不同算法的計算復雜度，我們重復執行100次定位過程，計算其平均運行時間。這里考慮的算法包括基于CS的算法（BP，OM P和IRW LS）以及非基于CS的算法（SI），結果如表3所示。Technology，2010，25（2）:274-297.

圖6　測量噪聲對定位結果的影響

圖7　基于CS和SI算法的定位效果對比

圖8　不同精度指標約束下定位算法所需要的最小測量次數

［3］DONOHO D L.Comp ressed sensing［J］.IEEE Transactions on Information Theory，2006，52（4）:1289-1306.

［4］CANDèE J.Com pressive sam pling［C］.International Congress of Mathematicians，Mad rid，Spain，2006: 1433-1452.

［5］CEVHER V，DUARTE M，and BARANIUK R G. Distribu ted target localization via spatial sparsity［C］. Proceedings of the European Signal Processing Conference（EUSIPCO），Lausanne，Sw itzerland，2008:25-29.

［6］CHEN F，VALAEE S，and TAN Z.Multiple target localization using com pressive sensing［C］.IEEE Global Telecomm unications Conference（GLOBECOM），Honolulu，HI，USA，2009:1-6.

［7］ZHANG B，CHEN X，ZHANG N，etal.Sparse target counting and localization in sensor networks based on com pressive sensing［C］.IEEE International Conference on Com puter Communications（INFOCOM），Shanghai，China，2011: 2255-2263.

［8］何風行，余志軍，劉海濤.基于壓縮感知的無線傳感器網絡多目標定位算法［J］.電子與信息學報，2012，34（3）:716-721.doi: 10.3724/SP.J.1146.2011.00405.

HE Fenghang，YU Zhijun，and LIU Haitao.Multiple target localization via com pressed sensing in w ireless sensor networks［J］.Journal of Electron ics&Information Tevhnology，2012，34（3）:716-721.doi:10.3724/SP.J.1146. 2011.00405.

［9］趙春暉，許云龍，黃輝.基于LU分解的稀疏目標定位算法［J］.電子與信息學報，2013，35（9）:2234-2239.doi:10.3724/ SP.J.1146.2012.01527.

ZHAO Chunhui，XU Yunlong，and HUANG Hui. Localization algorithm of sparse targets based on LU-decom position［J］.Journal of Electronics&Information Tevhnology，2013，35（9）:2234-2239.doi:10.3724/SP.J.1146.

表3　不同定位方法計算復雜度分析

如表3所示，在基于CS的算法中，BP算法雖然定位誤差最小（見圖4），但計算復雜度也最高。另外，相比于基于CS的算法，SI算法的計算復雜度明顯較低。因此在實時性要求高的應用場景，SI算法較為適用；相反，在定位精度要求高的應用場景，本文算法更為適用。

7　結束語

本文提出一種基于壓縮感知的動態目標定位算法。該算法充分利用動態目標的運動規律設計合適的稀疏表示基，并設計與該稀疏表示基低相關的易實現的稀疏觀測矩陣，建立壓縮感知模型，從而用較少的信息采集實現動態目標精確定位，從而大大減少了定位開銷。仿真結果表明，本文所提出的定位算法具有較好的性能。

［1］AKYILDIZ IF，SUW，SANKARASUBRAMANIAM Y，etal. W ireless sensor networks:a survey［J］.Computer Networks，2002，38（4）:393-422.

［2］LIU Y，YANG Z，WANG X，et al.Location，localization，and localizability［J］.Journal of Computer Science and2012.01527.

［10］李一兵，黃輝，葉方，等.基于奇異值分解的壓縮感知定位算法［J］.中南大學學報（自然科學版），2014，45（5）:1516-1521.

LIYibing，HUANG Hu i，YE Fang，et al.Target localization via com pressed sensing based on SVD［J］.Journal ofCentral South University（Natural Science），2014，45（5）:1516-1521.

［11］GUYEN G K，VAN NGUYEN T，and SHIN H.Learning dictionary and com p ressive sensing forW LAN localization［C］. IEEE W ireless Comm unications and Networking Conference（WCNC），Istanbul，Turkey，2014:2910-2915.

［12］陳偉，顏俊，朱衛平.利用壓縮感知與多邊測量技術的無線傳感器網絡定位算法［J］.信號處理，2014，30（6）:728-735.

CHEN W ei，YAN Jun，and ZHU W eiping.W ireless sensor network location algorithm using com pressive sensing and m ultilateral m easurem ents［J］.Journal of Signal Processing，2014，30（6）:728-735.

［13］王婷婷，柯煒，孫超.自適應環境變化的RSS室內定位方法［J］.通信學報，2014，35（10）:210-217.

WANG Tingting，KE W ei，and SUN Chao.Environmentaladap tive RSS-based indoor localization［J］.Journal on Commun ications，2014，35（10）:210-217.

［14］LIU L，CU I T，and LüW.A range-free m ultip le target localization algorithm using com pressive sensing theory in w ireless sensor networks［C］.IEEE 11th International Conference on Mobile Ad Hoc and Sensor System s（MASS），Philadelphia，PA，USA，2014:690-695.

［15］呂偉杰，崔婷婷，劉超，等.一種新的基于壓縮感知的WSN多目標定位方法［J］.系統仿真技術，2015，11（1）:6-13.

LüW eijie，CU I T ingting，LIU Chao，et al.A new m ultip le target localization based on com p ressed sensing theory in WSN［J］.System Simulation Technology，2015，11（1）:6-13.

［16］SONG C and XIA S.Sparse signal recovery by m inim ization under restricted isometry property［J］.IEEE Signal Processing Letters，2014，21（9）:1154-1158.

［17］WU X and LIU M.In-situ soilm oisture sensing:M easurem ent scheduling and estimation using com pressive sensing［C］. Proceedings of the 11th ACM International Conference on Information Processing in Sensor Networks，Beijing，China，2012:1-12.

［18］RHEE I，SHIN M，HONG S，et al.M obility traces［OL］. http://craw dad.org/ncsu/m obilitym odels/，2009.

孫保明：男，1989年生，博士生，研究方向為壓縮感知、無線傳感器網絡定位.

郭艷：女，1971年生，教授，研究方向為信號處理、壓縮感知，波束形成.

李寧：男，1967年生，副教授，研究方向為信號處理、認知無線電.

錢鵬：男，1991年生，碩士生，研究方向為壓縮感知、無源目標定位.

Mobile Target Localization A lgorithm Using Com pressive Sensing in W ireless Sensor Networks

SUN Baom ing GUO Yan LINing QIAN Peng
（Institute ofCommunications Engineering，PLA University ofScience and Technology，Nanjing 210007，China）

Traditionalmobile target localization algorithm s are not suitable for w ireless sensor networks as they need to collect，store，and p rocessamass of data.To add ress this issue，amobile target localization algorithm based on comp ressive sensing is p roposed.Two sparse rep resentation bases are designed by exploiting themovement characteristics of m obile targets，therefore the mobile target localization issue is transferred into a sparse signal recovery issue.To avoid the unp ractical lim itation of traditionalmeasurementmatrices，two sparsemeasurement matrices are p roposed that are practical and low ly coherent w ith the designed representation bases.The characteristic of this algorithm is thatmobile target localization can be achieved by collecting a little data，thus prolonging the lifetime of wireless sensor networks.Simulation resu lts indicate that the proposed localization algorithm based on com pressive sensing is high ly efficient.

W ireless sensor networks；M obile target localization；Com pressive sensing；Sparse representation basis；Measurementmatrix

s:The National Natural Science Foundation of China（61571463，61371124，61272487，61472445，61201217）

TP393；TN 911.7

A

1009-5896（2016）08-1858-07

10.11999/JEIT 151203

2015-10-29；改回日期：2016-03-29；網絡出版：2016-05-09

郭艷guoyan_2000@sina.com

國家自然科學基金（61571463，61371124，61272487，61472445，61201217）