基于奇异值分解的压缩感知定位算法
李一兵，黄辉，叶方，孙志国
(哈尔滨工程大学 信息与通信工程学院，黑龙江 哈尔滨，150001)
摘要：为了使观测字典满足约束等距性条件，保证算法的定位精度，提出一种基于奇异值分解的压缩感知定位算法。新算法首先将感知区域网格化，把定位问题转化为压缩感知问题，然后利用奇异值分解原理对观测字典进行分解，得到的新的观测字典有效地满足了约束等距性条件，且对观测值的预处理过程不影响原信号的稀疏性，从而有效地保证算法的重建性能，提升定位精度。仿真实验结果表明：相比于基于Orth的稀疏目标定位算法，基于SVD的压缩感知定位算法的定位性能更优，抗噪性、适应性更强，且算法复杂度低。
关键词：目标定位；压缩感知；约束等距性条件；稀疏性；奇异值分解
中图分类号：TP393 文献标志码：A 文章编号：1672-7207(2014)05-1516-06
Target localization via compressed sensing based on SVD
LI Yibing, HUANG Hui, YE Fang, SUN Zhiguo
(College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China)
Abstract: To ensure localization accuracy, a novel target localization algorithm via compressed sensing based on singular value decomposition (SVD) was proposed to make the measurement matrix satisfy the isometry property. By using gridding method for sensing area, the new algorithm converts target localization to compressive sensing issue, the measurement matrix obtained can effectively satisfy the restricted isometry property, and the preprocessing does not change the sparsity of the original signal, which effectively ensures the reconstruction performance and improves the localization accuracy. The experimental results show that compared with the localization algorithm of sparse targets based on Orth, the new target localization algorithm via compressed sensing based on SVD which is insensitive to noise has a much better performance and lower computation complexity.
Key words: target localization; compressed sensing; restricted isometry property; sparsity; singular value decomposition
根据定位机制的不同，当前的定位算法[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)
式中：
表示第k个目标的位置，是一个第n个元素为1，其他元素均为0的N×1维的向量。
图1 压缩感知目标定位模型
Fig. 1 Target localization model via compressed sensing
依据压缩感知理论，基于网格的K个目标定位问题可以通过下式表示：
(2)
式中：
为M个传感器对K个目标节点的观测值；
为观测矩阵，其第i行元素表示第i个感知器的位置所在，假设第i(1≤i≤M)个感知器所在的网格序号为l(1≤l≤N)，则表示的第i行的第l个元素为1，该行其余元素为0；
为稀疏变换基，可通过信号传输衰减模型得
，表示第i个网格到第j个网格的信号接收强度；
为观测字典；
为高斯白噪声。
依据IEEE802.15.4标准的信号衰落模型[13]，传感器节点接收到的信号强度为
(3)
式中：
为第i个网格到第j个网格的接收信号强度(1≤i≤N，1≤j≤N)；P0为目标节点的发射信号强度；
为目标节点所在网格与传感器节点所在网格的欧式距离，可表示为：
(4)
式中：(xi, yi)和(xj, yj)分别为第i个和第j个网格中心的坐标。
2 基于Orth的稀疏目标定位算法
从上述的基于压缩感知的目标定位模型中可以看出：观测字典A元素之间相关，因此，观测字典A无法满足RIP性质。基于此，Feng等[10-12]提出基于Orth的稀疏目标定位算法。该算法通过对信号进行Orth预处理，使得到的新的观测字典有效满足RIP性质。然后再进行信号重建与目标定位。
基于Orth的稀疏目标定位算法的信号预处理过程如下：
(5)
式中：
表示一个线性变换算子；( )*表示矩阵逆变换运算；
；
表示对矩阵进行列正交变换运算；
表示矩阵的转置。
化简信号观测值
得
(6)
依据压缩感知理论，上式中矩阵Q即为新的观测字典，由于
，是一个正交变换矩阵，此时，新的观测字典能较好的满足RIP性质。
然而，由于原观测字典A是一个
的矩阵而非方阵，因此，
是伪逆矩阵。这样，
不是一个标准的对角阵，即其非对角线上的元素不全为0。由此得到的
与
稀疏度不同，即原目标节点的位置信号经过信号预处理之后，稀疏性被改变。因此，该算法的Orth预处理会最终影响信号的重构性能和目标的定位性能。基于此，本文提出了一种新的基于SVD的压缩感知定位算法。
3 基于SVD的压缩感知定位算法
基于SVD的压缩感知定位算法的框图如图2所示，它主要分为以下3个步骤：
(1) 对信号进行SVD预处理，得新的观测字典G和观测值
；
(2) 利用压缩感知算法，重构稀疏信号；
(3) 利用加权质心算法[14-15]估计目标位置。
图2 基于SVD的压缩感知定位算法的框图
Fig. 2 Target localization chat via compressed sensing based on SVD
3.1 信号预处理
定理(SVD)：设矩阵
(r为B的秩)，则必然存在酉矩阵
和
，使得
(7)
其中：
，
＞0为B的正奇异值[16]。
依据SVD定理和式(7)，原观测字典A可分解为
(8)
其中：
，且
＞0，为观测字典A的正奇异值。
令
，对观测值Y进行下面的变换可得到新的观测值：
(9)
令
，则有：
(10)
因为为酉矩阵，所以，
。将式(8)代入Z中，并对Z化简得
(11)
列单位化矩阵Z，得新的矩阵G为
(12)
式中：
为矩阵Z的列向量；
表示求矩阵的模值。将Z由G表示如下：
(13)
由式(10)和(13)，观测值即为
(14)
依据压缩感知理论，矩阵G即为新的观测字典。由式(11)可知：Z即为矩阵
的前r行，又
为酉矩阵，所以矩阵Z的行向量之间相互正交。而新的观测字典G是通过单位化Z的列向量得到。所以，新的观测字典G是一个部分正交矩阵，即为压缩感知中常用的观测字典之一。因此，此时的G完全满足RIP性质。
3.2 稀疏信号的CS重构
通过式(14)可以看出
能被表示为
(15)
由于是稀疏的，且是通过左乘1个对角矩阵得到，因此，也是稀疏的，且与的稀疏度相同，又G完全满足RIP性质，因此，依据压缩感知理论，能被准确的重构。由可得为
(16)
3.3 目标位置估计
在基于网格的目标定位模型中，由于目标常常不是在网格的中心位置，因此，是一个近似的稀疏信号。为了减小定位误差，本文将对重建出来的信号的列向量进行归一化，作为每个网格对第k个目标估计位置的权值
：
(17)
式中：
为的第n(1≤n≤N)个元素；为第n个网格对估计第k个目标坐标的影响因子。
利用加权质心算法求解出第k个目标的位置：
(18)
其中：(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 传感器个数对定位性能的影响
在信噪比为20 dB，目标数K=5时，仿真分析传感器数M对算法定位性能的影响。图5所示为目标的平均定位误差随传感器数M变化的曲线。从图5可看出：2种算法的定位误差均随着传感器数M的增加而减少；在相同的测量次数下，本文算法的平均定位误差要远低于基于Orth的稀疏目标定位算法；本文算法在传感器数M≥6时，目标定位误差都接近于0.5 m，即估计出的目标位置与实际位置非常接近。而基于Orth的稀疏目标定位算法在传感器数M≥12时，才可能使得目标估计位置接近于实际位置，而此时的定位误差仍大于1 m。即在同样的定位性能要求下，相比于基于Orth的稀疏目标定位算法，本文算法需要的传感器数更少，也就是说，算法在定位过程中需传输的信息总量更少，计算量也更少，能量消耗也更小。
图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
图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。因此，在较为恶劣的感知环境中，本文算法仍然能保持较好的定位性能，亦即具有更强的抗噪性、鲁棒性。
1—基于奇异值分解的稀疏目标定位算法；
2—基于Orth的稀疏目标定位算法
图6 定位性能与信噪比关系
Fig. 6 Relationship between localization performance and SNR
4.4 算法复杂性分析
依据算法实现原理，在对信号的预处理过程中，基于SVD的压缩感知定位算法的计算量主要体现在对观测字典
的奇异值分解中，而基于Orth的稀疏目标定位算法的计算量主要包括矩阵的正交化和伪逆运算中。由于奇异值分解的运算量比矩阵的伪逆运算的运算量小。因此，较基于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 self- localization 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.
[11] Chen F, Au W S A, Valaee S, et al. Received signal strength based indoor positioning using compressive sensing[J]. IEEE Transactions on Mobile Computing, 2012, 11(12): 1983-1993.
[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.
(编辑 赵俊)
收稿日期：2013-06-06；修回日期：2013-09-20
基金项目：国家自然科学基金资助项目(61101141)；黑龙江省青年科学基金资助项目(QC2012C070)
通信作者：叶方(1980-)，女，浙江建德人，博士，副教授，从事超宽带无线通信、认知无线电研究；电话：13159800815；E-mail: yefang0815@sina.cn
