基于壓縮感知的無線傳感器網(wǎng)絡(luò)多目標(biāo)定位算法

何風(fēng)行 余志軍 劉海濤

①(中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所 上海 200050)

②(無錫物聯(lián)網(wǎng)產(chǎn)業(yè)研究院 無錫 214135)

1 引言

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

定位是WSN的支撐技術(shù)，WSN采集的信息中包含位置信息才能和物理世界對應(yīng)，具有實際意義[3]?；诮邮招盘枏姸?RSS)的定位技術(shù)相比基于到達(dá)時間差(TDOA)，到達(dá)時間(TOA)，到達(dá)角度(AOA)等定位技術(shù)，具有成本低廉、無需多余硬件、容易獲取等特點，取得廣泛應(yīng)用。近年來將稀疏變換、壓縮感知應(yīng)用于 WSN定位問題研究成為學(xué)術(shù)熱點。文獻(xiàn)[4]用稀疏變換研究定位問題，不足之處是算法的復(fù)雜度太高。文獻(xiàn)[5]用壓縮感知研究WSN的定位問題，它把 WSN目標(biāo)定位問題轉(zhuǎn)變?yōu)閴嚎s感知問題，這種方法的不足之處在于每個傳感節(jié)點都需要有一個定位字典(localization dictionary)，并且對目標(biāo)在網(wǎng)格中的位置做了限定。文獻(xiàn)[6]用壓縮感知的方法研究了WSN目標(biāo)定位問題，把WSN多目標(biāo)定位問題轉(zhuǎn)換為K個稀疏度為1的N維向量重構(gòu)問題。不足之處在于 WSN需要傳輸?shù)臄?shù)據(jù)沒有能進(jìn)一步“壓縮”，對于M個傳感節(jié)點，K個目標(biāo)的情況，需要傳送M×K個傳感數(shù)據(jù)。對于目標(biāo)不在網(wǎng)格中心，該文采用的方法是把目標(biāo)位置估計為候選定位結(jié)果集的中心，這是一種粗略的估計方法，會帶來估計誤差。

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

2 系統(tǒng)模型

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

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

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

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

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

圖1 采用壓縮感知的WSN多目標(biāo)定位系統(tǒng)模型

設(shè)第n個網(wǎng)格中的目標(biāo)發(fā)出的信號到第m個傳感器處衰減后，變?yōu)?/p>

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

3 壓縮感知算法

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

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

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

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

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

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

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

式(7)簡記為

這樣，WSN的基于接收信號強度(RSS)的多目標(biāo)定位問題轉(zhuǎn)換為根據(jù)M個測量結(jié)果，重構(gòu)N維稀疏向量的壓縮感知問題?？梢赃\用l1范數(shù)最小的最優(yōu)化算法求出問題的解。

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

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

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

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

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

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

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

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

設(shè)第n個網(wǎng)格中的目標(biāo)位置 (X(n,1),Y(n,1))初值為網(wǎng)格中心(XGn,YGn)，網(wǎng)格寬度為G。

圖2 迭代回溯算法示意圖

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

通過把目標(biāo)的位置嘗試調(diào)整為A,B,C,D，分別得出重構(gòu)矩陣、重構(gòu)信號，計算重構(gòu)誤差，目標(biāo)位置取為A,B,C,D,O的重構(gòu)誤差最小的相應(yīng)點位置。

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

重構(gòu)的信號中絕大部分接近于 0，該值的大小也近似表示了該網(wǎng)格中存在目標(biāo)的概率。因此可以只對大于某閾值的信號進(jìn)行迭代回溯算法，降低算法的復(fù)雜度：

迭代回溯算法描述如下：

步驟2 生成重構(gòu)矩陣Φ，運行重構(gòu)算法得到重構(gòu)結(jié)果X，計算重構(gòu)誤差。

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

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

本迭代回溯算法的優(yōu)點是定位精度不再受制于網(wǎng)格寬度G，在不增加網(wǎng)格數(shù)量N即問題維數(shù)的情況下，可以在網(wǎng)格中進(jìn)一步精確定位，需要付出的代價是算法迭代次數(shù)的增加。在噪聲情況下，定位結(jié)果差于Cramer-Rao界。關(guān)于本問題Cramer-Rao界可以參考文獻(xiàn)[3,11]簡單地推導(dǎo)出來，限于篇幅本文不再列出。

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

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

4 仿真結(jié)果

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

表1 主要仿真數(shù)據(jù)參數(shù)

下面針對目標(biāo)位于網(wǎng)格中心和位置任意的情況分別給出仿真結(jié)果。

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

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

圖3 目標(biāo)位于網(wǎng)格中心時的壓縮感知定位結(jié)果

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

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

5 結(jié)束語

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

圖4 目標(biāo)位于網(wǎng)格中心時定位效果的評價指標(biāo)

圖5 目標(biāo)位置任意時的壓縮感知定位結(jié)果

[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.