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

何風行 余志軍 劉海濤

①(中國科學院上海微系統與信息技術研究所 上海 200050)

②(無錫物聯網產業研究院 無錫 214135)

1 引言

壓縮感知理論自2006年正式提出以來[1,2]，在信號處理、通信、WSN等領域中的應用迅速成為學術熱點。WSN主要特點是傳感器節點的能量、計算能力、通信能力受限，而融合中心有相對強大的計算能力，能量不受限。基于壓縮感知的系統特點是：傳感器節點直接采樣少量數據，同時完成采樣和壓縮，不需要基于香農-乃奎斯特定理進行大量、高速采樣再額外運行復雜的壓縮算法。這使得傳感器節點變得簡單、廉價，付出的代價是信號恢復時的重構算法運算量較大，而信號重構是在融合中心進行，融合中心沒有能量、計算能力的苛刻限制。壓縮感知的這種“天然特點”是為WSN“量身定制”的。

定位是WSN的支撐技術，WSN采集的信息中包含位置信息才能和物理世界對應，具有實際意義[3]。基于接收信號強度(RSS)的定位技術相比基于到達時間差(TDOA)，到達時間(TOA)，到達角度(AOA)等定位技術，具有成本低廉、無需多余硬件、容易獲取等特點，取得廣泛應用。近年來將稀疏變換、壓縮感知應用于 WSN定位問題研究成為學術熱點。文獻[4]用稀疏變換研究定位問題，不足之處是算法的復雜度太高。文獻[5]用壓縮感知研究WSN的定位問題，它把 WSN目標定位問題轉變為壓縮感知問題，這種方法的不足之處在于每個傳感節點都需要有一個定位字典(localization dictionary)，并且對目標在網格中的位置做了限定。文獻[6]用壓縮感知的方法研究了WSN目標定位問題，把WSN多目標定位問題轉換為K個稀疏度為1的N維向量重構問題。不足之處在于 WSN需要傳輸的數據沒有能進一步“壓縮”，對于M個傳感節點，K個目標的情況，需要傳送M×K個傳感數據。對于目標不在網格中心，該文采用的方法是把目標位置估計為候選定位結果集的中心，這是一種粗略的估計方法，會帶來估計誤差。

本文將WSN的基于RSS的定位問題轉換為壓縮感知問題，給出了明確的系統模型和工作方式，該方法大大降低了系統的通信開銷，與文獻[6]中的方法相比，通信開銷從M×K減少到M。對于目標不在網格中心的情況提出了采用迭代回溯的壓縮感知算法，顯著提高了定位精度。仿真結果顯示本文提出的方法具有較好的定位效果。

2 系統模型

系統模型如圖1所示。設需要定位的區域為一方形區域，將此方形區域劃分為N個網格。此區域中隨機布設M個傳感器，每個傳感器的位置為已知。在整個區域中有K個目標(不要求K為已知量)。這是一個基于網格的目標定位問題，通過傳感器接收到的信號強度確定目標處于N個網格中的哪些位置。

系統的工作方式如下：每個目標周期性發射信號，發送周期為T，目標之間相互獨立，不要求同步。傳感器周期性地收集信號，收集周期也為T，將該周期內收到的信號強度值做累加，周期時間片結束后，每個傳感器將累加結果發送給融合中心。融合中心運行壓縮感知定位算法，計算出目標處于N個網格中的哪些位置。

第m個傳感器(1 ≤m≤M)和第n個網格(1≤n≤N)中的目標的歐式距離為

式(1)中，xm和ym為第m個傳感器的坐標，xn和yn為第n個網格中目標的坐標。

無線信號強度的衰落受障礙物遮擋、多徑傳播等環境因素影響較大。大量實驗統計結果表明，平均接收信號強度與信號傳輸距離之間的函數關系為[3]

圖1 采用壓縮感知的WSN多目標定位系統模型

設第n個網格中的目標發出的信號到第m個傳感器處衰減后，變為

對噪聲的處理方法是對傳感器的測量結果疊加高斯白噪聲。

3 壓縮感知算法

壓縮感知算法的一般過程為：已知測量矩陣Φ∈RM×N(M＜ ＜N)和某未知信號X∈RN在采用該測量矩陣時的線性測量值Y∈RM：

Y也可以看作信號X在測量矩陣Φ下的線性投影。壓縮感知主要解決的問題就是由測量結果Y重構信號X。顯然，由于X的維數遠遠大于Y的維數，這是一個欠定線性方程組求解問題，有無窮多解。然而壓縮感知理論證明，如果信號X是K稀疏的，并且Y與Φ滿足一定條件，信號X可以由測量值Y通過求解l1范數最小的最優化問題精確重構[1,2]：

下面討論壓縮感知算法如何應用于 WSN的多目標定位。先分析目標位于網格中心的特殊情況，然后分析目標位于任意位置的一般情形。

(1)目標位于網格中心 將目標在網格中的位置限定為網格中心，位于第n個網格中目標的坐標為(xn,yn)。

測量矩陣Φ∈RM×N(M＜ ＜N)中的元素φm,n為第m個傳感器接收到的位于第n個網格中目標的信號強度：

系統的壓縮采樣過程可用式(7)描述。

式(7)中xn=0 或1(1 ≤n≤N)，當第n個網格中有目標時xn=1 ，否則xn=0 。目標的總個數為K個，顯然，N維向量X的稀疏度為K。傳感器的測量結果Y為測量矩陣與稀疏向量X的乘積，其物理意義就是ym(1 ≤m≤M)為每個周期T內第m個傳感器收到的多個目標信號強度之和。

式(7)簡記為

這樣，WSN的基于接收信號強度(RSS)的多目標定位問題轉換為根據M個測量結果，重構N維稀疏向量的壓縮感知問題。可以運用l1范數最小的最優化算法求出問題的解。

測量矩陣Φ的生成有兩種辦法：一種方法是根據采用的信號衰減模型生成測量矩陣，另一種方法是根據實際測試結果得到測量矩陣。本文采用的是前一種方法。信號的重構結果和測量矩陣有很大關系，當測量矩陣滿足約束等距性條件(RIP)時信號可以得到精確重構，RIP條件是信號能夠精確重構的充分條件而非必要條件[7,8]。文獻[7]指出，X是稀疏度為K的N維向量，對X進行M次隨機測量，如果滿足式(9)，則可以通過求解l1范數最小的凸優化問題，由式(5)以壓倒性的概率精確重構X。

式(9)中，C為正的常數，μ(Φ,I)為矩陣Φ和單位矩陣I的互相關系數(mutual coherence)。矩陣的互相關系數μ(Φ,Ψ)表征了兩個N×N單位正交矩陣Φ和Ψ的相關性：

式(10)中，和ψj分別為Φ和Ψ的第k行和第j列，可得

對于本例，由于信號X本身就是稀疏信號，所以Ψ=I，有

將矩陣Φ和Ψ限定為正交矩陣對壓縮感知不是必須的，只是簡化分析過程。由以上分析可得，需要的測量次數即傳感器數量M，和目標個數K、測量矩陣和單位矩陣的互相關系數、網格劃分數量N有關。 m axφm,n取決于傳感器和劃分的網格中心之間的最短距離。因此，布設的傳感器最好和網格中心保持較大的距離，這樣測量矩陣中的值就比較平均，每個測量結果的權重大致相同，可以取得較好的定位結果。如果測量矩陣中的個別值極大，對應個別傳感器的權重很大，削弱其他傳感器的測量結果的作用，將使得定位結果變差。

(2)目標位置任意 將目標的位置限定在網格中心是很有局限性的，實際上目標可以在網格中的任何位置。

壓縮感知主要包括兩個階段[1,2]：壓縮測量階段和重構階段。壓縮測量階段中得到壓縮采樣結果Y。重構階段為根據測量矩陣Φ和測量結果Y重構X的過程。壓縮感知要求重構矩陣等于測量矩陣，一般可以通過兩種方式實現[4,6]：(a)將測量矩陣傳輸到重構端；(b)測量矩陣采用某隨機種子產生的偽隨機矩陣，重構端已知該隨機種子，從而得知測量矩陣。而在本系統中，測量矩陣是對目標信號強度進行測量的實際過程中形成的，因此融合中心得不到測量矩陣。如果把目標的位置估計為網格中心，可以根據式(6)構造出測量矩陣，但若采用該測量矩陣進行定位，除不能定位目標在網格中的具體位置，還產生虛假目標。

我們采用多分辨率分析(MRA)方法解決這個問題，采用迭代回溯法[9,10]使重構矩陣逐步趨近于實際的測量矩陣。算法的核心思想是：若某網格中可能存在目標，則對目標在該網格中的位置不斷迭代，選擇使重構誤差最小時的目標位置。迭代回溯算法的示意圖如圖2所示，若某網格中可能有目標，初始估計目標的位置為網格的中心位置O，重構信號，計算重構誤差，第1次迭代時，將目標的位置嘗試調整為A,B,C,D(分別是 4個小正方形的中心)，分別重構信號，計算重構誤差，選擇A,B,C，D,O5個點中重構誤差最小的點作為目標位置的估計。這樣就把目標在該網格中的位置區域由以O為中心的大正方形區域縮小為以A,B,C,D,O其中之一點為中心的小正方形區域。然后可以繼續進行迭代過程，進一步縮小目標所在區域范圍。

設第n個網格中的目標位置 (X(n,1),Y(n,1))初值為網格中心(XGn,YGn)，網格寬度為G。

圖2 迭代回溯算法示意圖

第i次迭代時(i=1,2,3…)，目標的位置調整為

通過把目標的位置嘗試調整為A,B,C,D，分別得出重構矩陣、重構信號，計算重構誤差，目標位置取為A,B,C,D,O的重構誤差最小的相應點位置。

由于N維向量X的元素的取值只有0和1(假設一個網格中不會有多個目標)，所以最理想的重構結果只有 0和 1。計算重構誤差的目標函數選擇為實際重構結果和理想重構結果的偏En為重構結果中的元素xn和理想結果的偏差：

重構的信號中絕大部分接近于 0，該值的大小也近似表示了該網格中存在目標的概率。因此可以只對大于某閾值的信號進行迭代回溯算法，降低算法的復雜度：

迭代回溯算法描述如下：

步驟2 生成重構矩陣Φ，運行重構算法得到重構結果X，計算重構誤差。

步驟4 嘗試調整目標位置至A,B,C,D，分別得到重構矩陣、重構信號、計算重構誤差。取重構誤差最小值所對應的點(A,B,C,D,O中之一)，接受為此次目標位置調整的結果。

本算法的步長調整類似于二分查找，每次迭代將把目標所在區域縮小為當前區域面積的1/4。理論上可以遍歷該網格的任何位置，且不會超出該網格的范圍。執行i次迭代后，目標可能在的位置縮小為網格面積的1/4i。

本迭代回溯算法的優點是定位精度不再受制于網格寬度G，在不增加網格數量N即問題維數的情況下，可以在網格中進一步精確定位，需要付出的代價是算法迭代次數的增加。在噪聲情況下，定位結果差于Cramer-Rao界。關于本問題Cramer-Rao界可以參考文獻[3,11]簡單地推導出來，限于篇幅本文不再列出。

迭代算法的計算復雜度分析如下，設執行一次壓縮感知重構算法的計算復雜度為O(1),X的所有元素中大于TH的元素有c×K個，則需要執行4c×K次壓縮感知重構算法，計算復雜度為O(4c×K)。最好情況為O(4K)，最差為O(4N)。c的大小和TH的大小有密切的關系，仿真結果表明TH取為0.3左右有較好的效果，此時c約為1～2，執行i輪迭代回溯算法的計算復雜度為O(4c×K×i)。

實際情況中，重構偏差可能會趨于固定值，而不能任意小。造成該問題的原因有兩個：TH的設定值和噪聲情況。如果TH設定的值比較大，可能會使迭代回溯算法操作的點太少，無法調整目標在網格中的位置，致使該偏差只能趨于固定值。如果噪聲比較大將影響重構信號的稀疏性，使得定位效果變差。

4 仿真結果

對本文所提出的基于壓縮感知的定位算法在Matlab中進行了仿真驗證，所采用的壓縮感知重構算法為l1范數最小重構算法(BP)。定位區域設為50 m×50 m的方形區域。傳感器布設在和網格中心1.5 m以外的區域。仿真參數的選取如表1所示。一般要求M＞2K，最好達到4K～6K，原信號可以得到較好的重構。仿真參數TH取為經驗值0.3，如前文所述。采用的信號模型為：p0=-4 0 dBm,n0=2,d0=1。

表1 主要仿真數據參數

下面針對目標位于網格中心和位置任意的情況分別給出仿真結果。

(1)目標位于網格中心 圖3為目標位于網格中心時，采用壓縮感知算法的定位結果，共有9個目標。由圖可以看出，在無噪聲情況下得到了理想的定位效果。在SNR=20 dB和SNR=15 dB時的定位效果隨噪聲增大逐漸變差。

圖4為通過200次蒙特卡羅實驗結果，假設目標個數K為已知。目標正確關聯的標準是：對目標的定位結果為目標實際所在的或相鄰的網格。由圖4(a)可以看出，隨目標個數的增多即信號的稀疏度逐漸變差，平均定位誤差逐漸變大。隨著噪聲的增大定位誤差也會變大。由圖4(b)可以看出，目標關聯正確率隨目標個數的增多、噪聲的增大逐漸下降。圖4表明在目標數量較少時壓縮感知算法可以得到較高的定位精度，隨著目標數量增加節省通信量的優勢得以體現，但是定位精度逐漸下降。當K＞M/ 2時重構不出原信號，算法失效。

圖3 目標位于網格中心時的壓縮感知定位結果

(2)目標位置任意 圖5為目標位置任意時的定位結果，共有7個目標。由圖可以看出，在無噪聲時，不采用迭代回溯算法會產生虛假目標，定位精度約為2 m。采用迭代回溯算法可以很大程度上抵消重構矩陣和測量矩陣的不同帶來的影響，無虛假目標，定位精度小于 1 m，提高了 50%以上。在SNR=25 dB時產生虛假目標，定位精度變差。

和傳統定位方法相比，壓縮感知算法特點是降低了通信開銷。傳統工作方式中對K個目標進行定位需要傳輸數據量為M×K，壓縮感知算法需要傳輸數據量為M，當K=20時只需上傳原來5%數據量，適用于通信環境惡劣的 WSN網絡。融合中心壓縮感知重構 BP算法的復雜度為O(N3)。非壓縮感知算法，比如LS (Least Squares)算法的復雜度為O(M3)。

5 結束語

本文提出了一種將壓縮感知應用于 WSN多目標定位的方法，將 WSN的定位問題轉換為壓縮感知問題。本文提出的迭代回溯定位算法大大降低了系統的通信開銷。仿真結果顯示本方法具有較好的多目標定位效果。算法的不足是在噪聲情況下性能較差，未來將開展對壓縮感知定位算法優化的研究，提高系統在高噪聲情況下的定位性能。

圖4 目標位于網格中心時定位效果的評價指標

圖5 目標位置任意時的壓縮感知定位結果

[1]Donoho D.Compressed sensing[J].IEEE Transactions onInformation Theroy,2006,52(4)：1289-1306.

[2]Candès E,Romberg J,and Tao T.Robust uncertainty principles：exact signal reconstruction from highly incomplete frequency information[J].IEEE Transactions on Information Theory,2006,52(2)：489-509.

[3]Patwari N,Ash J N,Kyperountas S,et al..Locating the nodes：cooperative localization in wireless sensor networks[J].IEEE Signal Processing Magazine,2005,22(4)：54-69.

[4]Malioutov D,Cetin M,and Willsky A S.A sparse signal reconstruction perspective for source localization with sensor arrays[J].IEEE Transactions on Signal Processing,2005,53(8)：3010-3022.

[5]Cevher V,Duarte M F,and Baraniuk R G.Distributed target localization via spatial sparsity[C].Proceedings of the European Signal Processing Conference,Lausanne,Switzerland,Aug.25-29,2008：25-29.

[6]Feng Chen,Valaee S,and Tan Zhen-hui.Multiple target localization using compressive sensing[C].IEEE Global Communications Conference,Honolulu,HI,USA,Nov.30-Dec.4,2009：1-6.

[7]Candès E and Romberg J.Sparsity and incoherence in compressive sampling[J].Inverse Problems,2007,23(3)：969-985.

[8]Candès E and Plan Y.A probabilistic and RIPless theory of compressed sensing[J].IEEE Transactions on Information Theory,2011,57(11)：7235-7254.

[9]Blumensath T and Davies M E.Iterative hard thresholding for compressed sensing[J].Applied and Computational Harmonic Analysis,2009,27(3)：265-274.

[10]Dai Wei and Milenkovic O.Subspace pursuit for compressive sensing signal reconstruction[J].IEEE Transactions on Information Theory,2009,55(5)：2230-2249.

[11]Hossain A K M M and Soh W S.Cramer-Rao bound analysis of localization using signal strength difference as location fingerprint[C].IEEE Conference on Computer Communications,San Diego,CA,USA,Mar.15-19,2010：1-9.