基于奇異值分解的壓縮感知定位算法

李一兵，黃輝，葉方，孫志國(guó)

(哈爾濱工程大學(xué) 信息與通信工程學(xué)院，黑龍江 哈爾濱，150001)

根據(jù)定位機(jī)制的不同，當(dāng)前的定位算法[1-2]可分為基于測(cè)距(range-based)[3]的定位算法和基于非測(cè)距(range-free)的定位算法。兩者相比，基于測(cè)距的定位算法通過(guò)接收信號(hào)強(qiáng)度(RSSI)、信號(hào)的到達(dá)時(shí)間差(TDOA)、到達(dá)角度(AOA)或到達(dá)時(shí)間(TOA)等不同來(lái)測(cè)量節(jié)點(diǎn)之間的距離，并據(jù)此對(duì)節(jié)點(diǎn)進(jìn)行定位，能夠獲得更高的定位精度。現(xiàn)階段，將壓縮感知(compressive sensing，CS)[4-7]應(yīng)用于目標(biāo)定位領(lǐng)域已成為學(xué)術(shù)研究的熱點(diǎn)之一。在基于壓縮感知的目標(biāo)定位算法中，普通節(jié)點(diǎn)首先只需采樣少量的感知數(shù)據(jù)，同時(shí)完成數(shù)據(jù)壓縮。壓縮感知技術(shù)降低了算法對(duì)普通節(jié)點(diǎn)的要求，使其簡(jiǎn)單化、廉價(jià)化。然后，由數(shù)據(jù)融合中心完成對(duì)感知數(shù)據(jù)的重構(gòu)，最終實(shí)現(xiàn)對(duì)目標(biāo)的定位。基于此，近年來(lái)很多學(xué)者進(jìn)行了大量的研究工作：文獻(xiàn)[8]把目標(biāo)定位問(wèn)題有效地變換為了壓縮感知問(wèn)題，但該算法要求每個(gè)普通節(jié)點(diǎn)都有一個(gè)定位字典，對(duì)節(jié)點(diǎn)要求較高。文獻(xiàn)[9]提出了基于貝葉斯壓縮感知的目標(biāo)定位算法，該算法可有效地保證普通節(jié)點(diǎn)消耗較少的能量，但容易產(chǎn)生虛假目標(biāo)。文獻(xiàn)[10-12]提出基于Orth 的稀疏目標(biāo)定位算法，將多目標(biāo)定位問(wèn)題轉(zhuǎn)換為多個(gè)N 維向量重構(gòu)問(wèn)題。為了使觀測(cè)字典滿足約束等距性條件(restricted isometry property，RIP)[6]，該算法對(duì)觀測(cè)字典進(jìn)行了Orth 預(yù)處理，然而，該變換過(guò)程影響了原信號(hào)的稀疏性，最終降低了算法的定位性能。本文作者將壓縮感知理論應(yīng)用于目標(biāo)定位中，并針對(duì)觀測(cè)字典無(wú)法滿足RIP 性質(zhì)的問(wèn)題，提出一種新的基于SVD 的壓縮感知定位算法。該算法通過(guò)對(duì)觀測(cè)字典A 進(jìn)行奇異值分解，得到新的觀測(cè)字典。在有效地滿足RIP 性質(zhì)的同時(shí)，不改變?cè)∈栊盘?hào)的稀疏度，從而保證了信號(hào)的重構(gòu)性能和目標(biāo)的定位精度。

1 系統(tǒng)模型

在無(wú)線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)首先需周期性的對(duì)感知區(qū)域內(nèi)的每個(gè)目標(biāo)的進(jìn)行感知，然后分別將各自接收到的各個(gè)目標(biāo)的信號(hào)強(qiáng)度發(fā)送給數(shù)據(jù)融合中心，最后融合中心利用目標(biāo)定位算法進(jìn)行目標(biāo)定位，確定目標(biāo)在網(wǎng)格中的具體位置。

假設(shè)在1 個(gè)方形的感知區(qū)域內(nèi)，隨機(jī)地分布著M個(gè)位置已知的傳感器和K 個(gè)位置未知的目標(biāo)(目標(biāo)之間相互獨(dú)立)，網(wǎng)格化這一方形區(qū)域，將其均勻地劃分成N 個(gè)網(wǎng)格(標(biāo)號(hào)為1, 2, …, N)。這樣，就將目標(biāo)的定位問(wèn)題轉(zhuǎn)化為了基于網(wǎng)格的目標(biāo)定位問(wèn)題，模型如圖1 所示。

假設(shè)第k(1≤k≤K)個(gè)目標(biāo)所在的網(wǎng)格序號(hào)為n(1≤n≤N)，則這K 個(gè)目標(biāo)在網(wǎng)格中的位置可通過(guò)矩陣表示如下：

圖1 壓縮感知目標(biāo)定位模型Fig.1 Target localization model via compressed sensing

式中：μk表示第k 個(gè)目標(biāo)的位置，是一個(gè)第n 個(gè)元素為1，其他元素均為0 的N×1 維的向量。

依據(jù)壓縮感知理論，基于網(wǎng)格的K 個(gè)目標(biāo)定位問(wèn)題可以通過(guò)下式表示：

式中：YM×K為M 個(gè)傳感器對(duì)K 個(gè)目標(biāo)節(jié)點(diǎn)的觀測(cè)值；ΦM×N為觀測(cè)矩陣，其第i 行元素表示第i 個(gè)感知器的位置所在，假設(shè)第i(1≤i≤M)個(gè)感知器所在的網(wǎng)格序號(hào)為l(1≤l≤N)，則表示 ΦM×N的第i 行的第l 個(gè)元素為1，該行其余元素為0；ΨN×N為稀疏變換基，可通過(guò)信號(hào)傳輸衰減模型得Ψi,j=RSSi,j，表示第i 個(gè)網(wǎng)格到第j 個(gè)網(wǎng)格的信號(hào)接收強(qiáng)度； Α =ΦΨ 為觀測(cè)字典；ε 為高斯白噪聲。

依據(jù)IEEE802.15.4 標(biāo)準(zhǔn)的信號(hào)衰落模型[13]，傳感器節(jié)點(diǎn)接收到的信號(hào)強(qiáng)度為

式中：RSSi,j為第i 個(gè)網(wǎng)格到第j 個(gè)網(wǎng)格的接收信號(hào)強(qiáng)度(1≤i≤N，1≤j≤N)；P0為目標(biāo)節(jié)點(diǎn)的發(fā)射信號(hào)強(qiáng)度； di,j為目標(biāo)節(jié)點(diǎn)所在網(wǎng)格與傳感器節(jié)點(diǎn)所在網(wǎng)格的歐式距離，可表示為：

式中：(xi, yi)和(xj, yj)分別為第i 個(gè)和第j 個(gè)網(wǎng)格中心的坐標(biāo)。

2 基于Orth 的稀疏目標(biāo)定位算法

從上述的基于壓縮感知的目標(biāo)定位模型中可以看出：觀測(cè)字典A 元素之間相關(guān)，因此，觀測(cè)字典A 無(wú)法滿足RIP 性質(zhì)。基于此，F(xiàn)eng 等[10-12]提出基于Orth的稀疏目標(biāo)定位算法。該算法通過(guò)對(duì)信號(hào)進(jìn)行Orth 預(yù)處理，使得到的新的觀測(cè)字典有效滿足RIP 性質(zhì)。然后再進(jìn)行信號(hào)重建與目標(biāo)定位。

基于Orth 的稀疏目標(biāo)定位算法的信號(hào)預(yù)處理過(guò)程如下：

式中： T =QA*表示一個(gè)線性變換算子；( )*表示矩陣逆變換運(yùn)算；Q=orth(ΑH)H；orth(?)表示對(duì)矩陣進(jìn)行列正交變換運(yùn)算；(?)H表示矩陣的轉(zhuǎn)置。

化簡(jiǎn)信號(hào)觀測(cè)值 Y ′得

依據(jù)壓縮感知理論，上式中矩陣Q 即為新的觀測(cè)字典，由于Q=Orth(ΑH)H，是一個(gè)正交變換矩陣，此時(shí)，新的觀測(cè)字典能較好的滿足RIP 性質(zhì)。

然而，由于原觀測(cè)字典A 是一個(gè)M × N的矩陣而非方陣，因此， A*是偽逆矩陣。這樣， A*A 不是一個(gè)標(biāo)準(zhǔn)的對(duì)角陣，即其非對(duì)角線上的元素不全為0。由此得到的 μ′ =A*Aμ 與μ 稀疏度不同，即原目標(biāo)節(jié)點(diǎn)的位置信號(hào)μ 經(jīng)過(guò)信號(hào)預(yù)處理之后，稀疏性被改變。因此，該算法的Orth 預(yù)處理會(huì)最終影響信號(hào)的重構(gòu)性能和目標(biāo)的定位性能。基于此，本文提出了一種新的基于SVD 的壓縮感知定位算法。

3 基于SVD 的壓縮感知定位算法

基于SVD 的壓縮感知定位算法的框圖如圖2 所示，它主要分為以下3 個(gè)步驟：

(1) 對(duì)信號(hào)進(jìn)行SVD 預(yù)處理，得新的觀測(cè)字典G和觀測(cè)值 Y ′；

(2) 利用壓縮感知算法，重構(gòu)稀疏信號(hào)μ ；

(3) 利用加權(quán)質(zhì)心算法[14-15]估計(jì)目標(biāo)位置。

圖2 基于SVD 的壓縮感知定位算法的框圖Fig.2 Target localization chat via compressed sensing based on SVD

3.1 信號(hào)預(yù)處理

其中：Σr=diag(σ1,σ2, ???,σr)，σ1≥ σ2≥ ???≥ σr＞0為B 的正奇異值[16]。

依據(jù)SVD 定理和式(7)，原觀測(cè)字典A 可分解為

其中：Δ=diag(δ1,δ2, ???,δr)，且 δ1≥ δ2≥ ???≥ δr＞0，為觀測(cè)字典A 的正奇異值。

令 Δ*=diag(1/δ1,1/δ2, ???,1/δr)，對(duì)觀測(cè)值Y 進(jìn)行下面的變換可得到新的觀測(cè)值 Y ′：

令Z=［Δ*0]UHA，則有：

列單位化矩陣Z，得新的矩陣G 為

由式(10)和(13)，觀測(cè)值 Y ′即為

3.2 稀疏信號(hào)的CS 重構(gòu)

通過(guò)式(14)可以看出 μ ′能被表示為

由于μ 是稀疏的，且 μ ′是通過(guò)μ 左乘1 個(gè)對(duì)角矩陣得到，因此， μ ′也是稀疏的，且 μ ′與μ 的稀疏度相同，又G 完全滿足RIP 性質(zhì)，因此，依據(jù)壓縮感知理論， μ ′能被準(zhǔn)確的重構(gòu)。由 μ ′可得μ 為

3.3 目標(biāo)位置估計(jì)

在基于網(wǎng)格的目標(biāo)定位模型中，由于目標(biāo)常常不是在網(wǎng)格的中心位置，因此，μk是一個(gè)近似的稀疏信號(hào)。為了減小定位誤差，本文將對(duì)重建出來(lái)的信號(hào)的列向量 μk進(jìn)行歸一化，作為每個(gè)網(wǎng)格對(duì)第k 個(gè)目標(biāo)估計(jì)位置的權(quán)值 ωk( n)：

式中： μk( n)為 μk的第n(1≤n≤N)個(gè)元素； ωk( n)為第n 個(gè)網(wǎng)格對(duì)估計(jì)第k 個(gè)目標(biāo)坐標(biāo)的影響因子。

利用加權(quán)質(zhì)心算法求解出第k 個(gè)目標(biāo)的位置：

其中：(xk, yk)表示第k 個(gè)目標(biāo)的估計(jì)位置，(xn, yn)表示第n 個(gè)網(wǎng)格的中心位置。

4 性能仿真和分析

假設(shè)在1 個(gè)100 m×100 m 的方形感知區(qū)域內(nèi)，隨機(jī)地分布著一定數(shù)量的感知器節(jié)點(diǎn)，這些節(jié)點(diǎn)需合作定位出感知區(qū)域內(nèi)的目標(biāo)節(jié)點(diǎn)所在的位置。將該感知區(qū)域劃分為25×25 的網(wǎng)格，并在Matlab 仿真環(huán)境下，對(duì)本文提出的基于SVD 的壓縮感知定位算法和基于Orth 的稀疏目標(biāo)定位算法進(jìn)行實(shí)驗(yàn)對(duì)比(采用BP 算法作為壓縮感知的重構(gòu)算法)。

4.1 多目標(biāo)的定位性能

如圖3 所示為在信噪比SNR 為20 dB，傳感器數(shù)M=8 時(shí)，基于SVD 的壓縮感知定位算法和基于Orth的稀疏目標(biāo)定位算法對(duì)K=5個(gè)目標(biāo)進(jìn)行定位的定位示意圖。從圖3 可以看出：對(duì)于全部的5 個(gè)目標(biāo)節(jié)點(diǎn)，基于Orth 的稀疏目標(biāo)定位算法估計(jì)出的目標(biāo)中只有2個(gè)目標(biāo)與實(shí)際所在網(wǎng)格相同，而基于SVD 的壓縮感知定位算法定位的所有5 個(gè)目標(biāo)的位置和目標(biāo)的實(shí)際位置均在同一個(gè)網(wǎng)格。也就是說(shuō)，相比于基于Orth 的稀疏目標(biāo)定位算法，本文算法對(duì)目標(biāo)的定位更準(zhǔn)確，亦即定位性能更為優(yōu)勝。

在其他參數(shù)不變的條件下，把目標(biāo)數(shù)K 增加到25個(gè)，得到目標(biāo)定位示意圖如圖4 所示。從圖4 可以看出：在對(duì)多目標(biāo)定位進(jìn)行定位時(shí)，本文算法對(duì)大部分目標(biāo)的估計(jì)位置與目標(biāo)的實(shí)際位置相差很小。也就是說(shuō)，與對(duì)比算法相比，本文算法對(duì)大部分目標(biāo)的重構(gòu)誤差更小。因此，本文算法的定位性能要遠(yuǎn)優(yōu)于對(duì)比算法，且對(duì)于目標(biāo)個(gè)數(shù)的適應(yīng)性更強(qiáng)。

4.2 傳感器個(gè)數(shù)對(duì)定位性能的影響

圖3 K=5 時(shí)2 種算法的目標(biāo)定位對(duì)比示意圖Fig.3 Target localization comparison of two algorithms when K=5

圖4 K=20 時(shí)2 種算法的目標(biāo)定位對(duì)比示意圖Fig.4 Target localization comparison of two algorithms when K=20

在信噪比為20 dB，目標(biāo)數(shù)K=5 時(shí)，仿真分析傳感器數(shù)M 對(duì)算法定位性能的影響。圖5 所示為目標(biāo)的平均定位誤差隨傳感器數(shù)M 變化的曲線。從圖5 可看出：2 種算法的定位誤差均隨著傳感器數(shù)M 的增加而減少；在相同的測(cè)量次數(shù)下，本文算法的平均定位誤差要遠(yuǎn)低于基于Orth 的稀疏目標(biāo)定位算法；本文算法在傳感器數(shù)M≥6 時(shí)，目標(biāo)定位誤差都接近于0.5 m，即估計(jì)出的目標(biāo)位置與實(shí)際位置非常接近。而基于Orth 的稀疏目標(biāo)定位算法在傳感器數(shù)M≥12 時(shí)，才可能使得目標(biāo)估計(jì)位置接近于實(shí)際位置，而此時(shí)的定位誤差仍大于1 m。即在同樣的定位性能要求下，相比于基于Orth 的稀疏目標(biāo)定位算法，本文算法需要的傳感器數(shù)更少，也就是說(shuō)，算法在定位過(guò)程中需傳輸?shù)男畔⒖偭扛伲?jì)算量也更少，能量消耗也更小。

圖5 定位性能與傳感器數(shù)的關(guān)系Fig.5 Relationship between localization performance and M

4.3 噪聲對(duì)定位性能的影響

如圖6 所示為在傳感器數(shù)M=8，目標(biāo)數(shù)K=5 時(shí)，目標(biāo)的平均定位誤差隨信噪比變化的曲線。從圖6 可以看出：2 種算法的平均定位誤差均隨著信噪比的增加而減少；在相同的信噪比環(huán)境下，本文算法的平均定位誤差遠(yuǎn)低于基于Orth 的稀疏目標(biāo)定位算法；即使在信噪比為0 dB 這樣惡劣的環(huán)境中，本文算法的平均定位誤差也只有2.3 m 左右，而基于Orth 的稀疏目標(biāo)定位算法在信噪比大于20 dB 時(shí)，平均定位誤差仍然大于3 m。因此，在較為惡劣的感知環(huán)境中，本文算法仍然能保持較好的定位性能，亦即具有更強(qiáng)的抗噪性、魯棒性。

圖6 定位性能與信噪比關(guān)系Fig.6 Relationship between localization performance and SNR

4.4 算法復(fù)雜性分析

依據(jù)算法實(shí)現(xiàn)原理，在對(duì)信號(hào)的預(yù)處理過(guò)程中，基于SVD 的壓縮感知定位算法的計(jì)算量主要體現(xiàn)在對(duì)觀測(cè)字典 AM×N的奇異值分解中，而基于Orth 的稀疏目標(biāo)定位算法的計(jì)算量主要包括矩陣 AM×N的正交化和偽逆運(yùn)算中。由于奇異值分解的運(yùn)算量比矩陣的偽逆運(yùn)算的運(yùn)算量小。因此，較基于Orth 的稀疏目標(biāo)定位算法，本文算法的計(jì)算量更小，復(fù)雜度低。

5 結(jié)論

(1) 提出一種新的基于奇異值分解的壓縮感知定位算法。算法通過(guò)SVD 和一系列信號(hào)預(yù)處理，得到的新的觀測(cè)字典完全地滿足了RIP 性質(zhì)。而且不同于基于Orth 的稀疏目標(biāo)定位算法，本文算法的信號(hào)預(yù)處理過(guò)程不影響原信號(hào)的稀疏性，從而確保了壓縮感知重建算法的性能，提高了多目標(biāo)定位精度。實(shí)驗(yàn)結(jié)果表明：基于SVD 的壓縮感知定位算法的定位精度遠(yuǎn)優(yōu)于基于Orth 預(yù)處理的稀疏目標(biāo)定位算法，且本文算法具有更強(qiáng)的抗噪性、適應(yīng)性。

(2) 在進(jìn)一步研究工作中，可采用不同的信號(hào)預(yù)處理方法，在保證觀測(cè)字典在滿足RIP 性質(zhì)的同時(shí)，不改變?cè)盘?hào)的稀疏性，使目標(biāo)定位的計(jì)算量更小，定位性能更優(yōu)。

[1] Stojmenovic I. Handbook of sensor networks: Algorithms and architectures[M]. New York: Wiley, 2005.

[2] 劉志坤, 劉忠, 唐小明. 基于改進(jìn)型粒子群優(yōu)化的節(jié)點(diǎn)自定位算法[J]. 中南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2012, 43(4):1371-1376.LIU Zhi-kun, LIU Zhong, TANG Xiaoming. Node selflocalization algorithm based on modified particle swarm optimization[J]. Journal of Central South University (Science and Technology), 2012, 43(4): 1371-1376.

[3] 閆保中, 張帥, 張宇. 基于RFID 的室內(nèi)人員定位系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]. 應(yīng)用科技, 2011, 38(11): 39-42.YAN Baozhong, ZHANG Shuai, ZHANG Yu. Design and implementation of the indoor personnel positioning system based on RFID[J]. Applied Science and Technology, 2011, 38(11):39-42.

[4] Candes E. Compressive sampling[J]. International Congress of Mathematicians, 2006(3): 1433-1452.

[5] Donoho D. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

[6] Candes E, Plan Y. A probabilistic and RIP less theory of compressed sensing[J]. IEEE Transactions on Information Theory, 2011, 57(11): 7235-7254.

[7] 金堅(jiān), 谷源濤, 梅順良. 壓縮采樣技術(shù)及其應(yīng)用[J]. 電子與信息學(xué)報(bào), 2010, 32(2): 470-475.JIN Jian, GU Yuantao, MEI Shunliang. An introduction to compressive sampling and its applications[J]. Journal of Electronics & Information Technology, 2010, 32(2): 470-475.

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

[9] 趙春暉, 許云龍. 能量約束貝葉斯壓縮感知檢測(cè)算法[J]. 通信學(xué)報(bào), 2012, 33(10): 1-6.ZHAO Chunhui, XU Yunlong. Energy constraint Bayesian compressive sensing detection algorithm[J]. Journal on Communications, 2012, 33(10): 1-6.

[10] Feng Chen, Valaee S, Tan Zhenhui. Multiple target localization using compressive sensing[C]// IEEE Global Communications Conference. Honolulu, HI, USA, 2009: 1-6.

[12] Au W S A, Chen F, Valaee S, et al. Indoor tracking and navigation using received signal strength and compressive sensing on a mobile device[J]. IEEE Transactions on Mobile Computing, 2013, 12(10): 2050-2062.

[13] IEEE standard online resource provided by IEEE 802.15 WPAN[EB/OL]. [2009-02-20]. http://www.ieee802.org/15/pub/TG4.html.

[14] WANG Jun, Urriza P, HAN Yuxing, et al. Weighted Centroid localization algorithm: Theoretical analysis and distributed implementation[J]. IEEE Transactions on Wireless Communications, 2011, 10(10): 3403-3413.

[15] 楊新宇, 孔慶茹, 戴湘軍. 一種改進(jìn)的加權(quán)質(zhì)心定位算法[J].西安交通大學(xué)學(xué)報(bào), 2010, 44(8): 1-4.YANG Xinyu, KONG Qingru, DAI Xiangjun. An improved weighted Centroid location algorithm[J]. Journal of Xi’an Jiaotong University, 2010, 44(8): 1-4.

[16] 卜長(zhǎng)江, 羅躍生. 矩陣論[M]. 哈爾濱: 哈爾濱工程大學(xué)出版社, 2008: 91-94.BU Changjiang, LUO Yuesheng. Matrix theory[M]. Harbin:Harbin Engineering University Press, 2008: 91-94.