基于奇异值分解的压缩感知定位算法

李一兵，黄辉，叶方，孙志国

(哈尔滨工程大学 信息与通信工程学院，黑龙江 哈尔滨，150001)

根据定位机制的不同，当前的定位算法[1-2]可分为基于测距(range-based)[3]的定位算法和基于非测距(range-free)的定位算法。两者相比，基于测距的定位算法通过接收信号强度(RSSI)、信号的到达时间差(TDOA)、到达角度(AOA)或到达时间(TOA)等不同来测量节点之间的距离，并据此对节点进行定位，能够获得更高的定位精度。现阶段，将压缩感知(compressive sensing，CS)[4-7]应用于目标定位领域已成为学术研究的热点之一。在基于压缩感知的目标定位算法中，普通节点首先只需采样少量的感知数据，同时完成数据压缩。压缩感知技术降低了算法对普通节点的要求，使其简单化、廉价化。然后，由数据融合中心完成对感知数据的重构，最终实现对目标的定位。基于此，近年来很多学者进行了大量的研究工作：文献[8]把目标定位问题有效地变换为了压缩感知问题，但该算法要求每个普通节点都有一个定位字典，对节点要求较高。文献[9]提出了基于贝叶斯压缩感知的目标定位算法，该算法可有效地保证普通节点消耗较少的能量，但容易产生虚假目标。文献[10-12]提出基于Orth 的稀疏目标定位算法，将多目标定位问题转换为多个N 维向量重构问题。为了使观测字典满足约束等距性条件(restricted isometry property，RIP)[6]，该算法对观测字典进行了Orth 预处理，然而，该变换过程影响了原信号的稀疏性，最终降低了算法的定位性能。本文作者将压缩感知理论应用于目标定位中，并针对观测字典无法满足RIP 性质的问题，提出一种新的基于SVD 的压缩感知定位算法。该算法通过对观测字典A 进行奇异值分解，得到新的观测字典。在有效地满足RIP 性质的同时，不改变原稀疏信号的稀疏度，从而保证了信号的重构性能和目标的定位精度。

1 系统模型

在无线传感器网络中，传感器节点首先需周期性的对感知区域内的每个目标的进行感知，然后分别将各自接收到的各个目标的信号强度发送给数据融合中心，最后融合中心利用目标定位算法进行目标定位，确定目标在网格中的具体位置。

假设在1 个方形的感知区域内，随机地分布着M个位置已知的传感器和K 个位置未知的目标(目标之间相互独立)，网格化这一方形区域，将其均匀地划分成N 个网格(标号为1, 2, …, N)。这样，就将目标的定位问题转化为了基于网格的目标定位问题，模型如图1 所示。

假设第k(1≤k≤K)个目标所在的网格序号为n(1≤n≤N)，则这K 个目标在网格中的位置可通过矩阵表示如下：

图1 压缩感知目标定位模型Fig.1 Target localization model via compressed sensing

式中：μk表示第k 个目标的位置，是一个第n 个元素为1，其他元素均为0 的N×1 维的向量。

依据压缩感知理论，基于网格的K 个目标定位问题可以通过下式表示：

式中：YM×K为M 个传感器对K 个目标节点的观测值；ΦM×N为观测矩阵，其第i 行元素表示第i 个感知器的位置所在，假设第i(1≤i≤M)个感知器所在的网格序号为l(1≤l≤N)，则表示 ΦM×N的第i 行的第l 个元素为1，该行其余元素为0；ΨN×N为稀疏变换基，可通过信号传输衰减模型得Ψi,j=RSSi,j，表示第i 个网格到第j 个网格的信号接收强度； Α =ΦΨ 为观测字典；ε 为高斯白噪声。

依据IEEE802.15.4 标准的信号衰落模型[13]，传感器节点接收到的信号强度为

式中：RSSi,j为第i 个网格到第j 个网格的接收信号强度(1≤i≤N，1≤j≤N)；P0为目标节点的发射信号强度； di,j为目标节点所在网格与传感器节点所在网格的欧式距离，可表示为：

式中：(xi, yi)和(xj, yj)分别为第i 个和第j 个网格中心的坐标。

2 基于Orth 的稀疏目标定位算法

从上述的基于压缩感知的目标定位模型中可以看出：观测字典A 元素之间相关，因此，观测字典A 无法满足RIP 性质。基于此，Feng 等[10-12]提出基于Orth的稀疏目标定位算法。该算法通过对信号进行Orth 预处理，使得到的新的观测字典有效满足RIP 性质。然后再进行信号重建与目标定位。

基于Orth 的稀疏目标定位算法的信号预处理过程如下：

式中： T =QA*表示一个线性变换算子；( )*表示矩阵逆变换运算；Q=orth(ΑH)H；orth(⋅)表示对矩阵进行列正交变换运算；(⋅)H表示矩阵的转置。

化简信号观测值 Y ′得

依据压缩感知理论，上式中矩阵Q 即为新的观测字典，由于Q=Orth(ΑH)H，是一个正交变换矩阵，此时，新的观测字典能较好的满足RIP 性质。

然而，由于原观测字典A 是一个M × N的矩阵而非方阵，因此， A*是伪逆矩阵。这样， A*A 不是一个标准的对角阵，即其非对角线上的元素不全为0。由此得到的 μ′ =A*Aμ 与μ 稀疏度不同，即原目标节点的位置信号μ 经过信号预处理之后，稀疏性被改变。因此，该算法的Orth 预处理会最终影响信号的重构性能和目标的定位性能。基于此，本文提出了一种新的基于SVD 的压缩感知定位算法。

3 基于SVD 的压缩感知定位算法

基于SVD 的压缩感知定位算法的框图如图2 所示，它主要分为以下3 个步骤：

(1) 对信号进行SVD 预处理，得新的观测字典G和观测值 Y ′；

(2) 利用压缩感知算法，重构稀疏信号μ ；

(3) 利用加权质心算法[14-15]估计目标位置。

图2 基于SVD 的压缩感知定位算法的框图Fig.2 Target localization chat via compressed sensing based on SVD

3.1 信号预处理

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

依据SVD 定理和式(7)，原观测字典A 可分解为

其中：Δ=diag(δ1,δ2, ⋅⋅⋅,δr)，且 δ1≥ δ2≥ ⋅⋅⋅≥ δr＞0，为观测字典A 的正奇异值。

令 Δ*=diag(1/δ1,1/δ2, ⋅⋅⋅,1/δr)，对观测值Y 进行下面的变换可得到新的观测值 Y ′：

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

列单位化矩阵Z，得新的矩阵G 为

由式(10)和(13)，观测值 Y ′即为

3.2 稀疏信号的CS 重构

通过式(14)可以看出 μ ′能被表示为

由于μ 是稀疏的，且 μ ′是通过μ 左乘1 个对角矩阵得到，因此， μ ′也是稀疏的，且 μ ′与μ 的稀疏度相同，又G 完全满足RIP 性质，因此，依据压缩感知理论， μ ′能被准确的重构。由 μ ′可得μ 为

3.3 目标位置估计

在基于网格的目标定位模型中，由于目标常常不是在网格的中心位置，因此，μk是一个近似的稀疏信号。为了减小定位误差，本文将对重建出来的信号的列向量 μk进行归一化，作为每个网格对第k 个目标估计位置的权值 ωk( n)：

式中： μk( n)为 μk的第n(1≤n≤N)个元素； ωk( n)为第n 个网格对估计第k 个目标坐标的影响因子。

利用加权质心算法求解出第k 个目标的位置：

其中：(xk, yk)表示第k 个目标的估计位置，(xn, yn)表示第n 个网格的中心位置。

4 性能仿真和分析

假设在1 个100 m×100 m 的方形感知区域内，随机地分布着一定数量的感知器节点，这些节点需合作定位出感知区域内的目标节点所在的位置。将该感知区域划分为25×25 的网格，并在Matlab 仿真环境下，对本文提出的基于SVD 的压缩感知定位算法和基于Orth 的稀疏目标定位算法进行实验对比(采用BP 算法作为压缩感知的重构算法)。

4.1 多目标的定位性能

如图3 所示为在信噪比SNR 为20 dB，传感器数M=8 时，基于SVD 的压缩感知定位算法和基于Orth的稀疏目标定位算法对K=5个目标进行定位的定位示意图。从图3 可以看出：对于全部的5 个目标节点，基于Orth 的稀疏目标定位算法估计出的目标中只有2个目标与实际所在网格相同，而基于SVD 的压缩感知定位算法定位的所有5 个目标的位置和目标的实际位置均在同一个网格。也就是说，相比于基于Orth 的稀疏目标定位算法，本文算法对目标的定位更准确，亦即定位性能更为优胜。

在其他参数不变的条件下，把目标数K 增加到25个，得到目标定位示意图如图4 所示。从图4 可以看出：在对多目标定位进行定位时，本文算法对大部分目标的估计位置与目标的实际位置相差很小。也就是说，与对比算法相比，本文算法对大部分目标的重构误差更小。因此，本文算法的定位性能要远优于对比算法，且对于目标个数的适应性更强。

4.2 传感器个数对定位性能的影响

图3 K=5 时2 种算法的目标定位对比示意图Fig.3 Target localization comparison of two algorithms when K=5

图4 K=20 时2 种算法的目标定位对比示意图Fig.4 Target localization comparison of two algorithms when K=20

在信噪比为20 dB，目标数K=5 时，仿真分析传感器数M 对算法定位性能的影响。图5 所示为目标的平均定位误差随传感器数M 变化的曲线。从图5 可看出：2 种算法的定位误差均随着传感器数M 的增加而减少；在相同的测量次数下，本文算法的平均定位误差要远低于基于Orth 的稀疏目标定位算法；本文算法在传感器数M≥6 时，目标定位误差都接近于0.5 m，即估计出的目标位置与实际位置非常接近。而基于Orth 的稀疏目标定位算法在传感器数M≥12 时，才可能使得目标估计位置接近于实际位置，而此时的定位误差仍大于1 m。即在同样的定位性能要求下，相比于基于Orth 的稀疏目标定位算法，本文算法需要的传感器数更少，也就是说，算法在定位过程中需传输的信息总量更少，计算量也更少，能量消耗也更小。

图5 定位性能与传感器数的关系Fig.5 Relationship between localization performance and M

4.3 噪声对定位性能的影响

如图6 所示为在传感器数M=8，目标数K=5 时，目标的平均定位误差随信噪比变化的曲线。从图6 可以看出：2 种算法的平均定位误差均随着信噪比的增加而减少；在相同的信噪比环境下，本文算法的平均定位误差远低于基于Orth 的稀疏目标定位算法；即使在信噪比为0 dB 这样恶劣的环境中，本文算法的平均定位误差也只有2.3 m 左右，而基于Orth 的稀疏目标定位算法在信噪比大于20 dB 时，平均定位误差仍然大于3 m。因此，在较为恶劣的感知环境中，本文算法仍然能保持较好的定位性能，亦即具有更强的抗噪性、鲁棒性。

图6 定位性能与信噪比关系Fig.6 Relationship between localization performance and SNR

4.4 算法复杂性分析

依据算法实现原理，在对信号的预处理过程中，基于SVD 的压缩感知定位算法的计算量主要体现在对观测字典 AM×N的奇异值分解中，而基于Orth 的稀疏目标定位算法的计算量主要包括矩阵 AM×N的正交化和伪逆运算中。由于奇异值分解的运算量比矩阵的伪逆运算的运算量小。因此，较基于Orth 的稀疏目标定位算法，本文算法的计算量更小，复杂度低。

5 结论

(1) 提出一种新的基于奇异值分解的压缩感知定位算法。算法通过SVD 和一系列信号预处理，得到的新的观测字典完全地满足了RIP 性质。而且不同于基于Orth 的稀疏目标定位算法，本文算法的信号预处理过程不影响原信号的稀疏性，从而确保了压缩感知重建算法的性能，提高了多目标定位精度。实验结果表明：基于SVD 的压缩感知定位算法的定位精度远优于基于Orth 预处理的稀疏目标定位算法，且本文算法具有更强的抗噪性、适应性。

(2) 在进一步研究工作中，可采用不同的信号预处理方法，在保证观测字典在满足RIP 性质的同时，不改变原信号的稀疏性，使目标定位的计算量更小，定位性能更优。

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

[2] 刘志坤, 刘忠, 唐小明. 基于改进型粒子群优化的节点自定位算法[J]. 中南大学学报(自然科学版), 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 的室内人员定位系统的设计与实现[J]. 应用科技, 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] 金坚, 谷源涛, 梅顺良. 压缩采样技术及其应用[J]. 电子与信息学报, 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] 赵春晖, 许云龙. 能量约束贝叶斯压缩感知检测算法[J]. 通信学报, 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].西安交通大学学报, 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] 卜长江, 罗跃生. 矩阵论[M]. 哈尔滨: 哈尔滨工程大学出版社, 2008: 91-94.BU Changjiang, LUO Yuesheng. Matrix theory[M]. Harbin:Harbin Engineering University Press, 2008: 91-94.