基于概率稀疏随机矩阵的压缩数据收集方法

张 波刘郁林 王 开 王 娇

(重庆通信学院DSP研究室 重庆 400035)

1 引言

无线传感器网络(Wireless Sensor Networks,WSNs)[1]凭借其部署灵活、抗毁性强、高容错等独特优势，在环境监测、城市管理、抢险救灾等众多领域均具有非常广阔的应用前景。传感器节点通常采用微型嵌入式设备，携带的电池能量非常有限。因此，在节点能量受限条件下，实现对网络数据的有效收集，成为亟待解决的关键问题。

为节约数据收集的通信能耗，可采用数据压缩技术对网络数据进行压缩，从而减少数据的传输量，达到节约节点能量目的[2]。然而传统的数据压缩方法一般先将数据压缩后再传输，这种方法需要预先知道整个网络(或者网络的一部分)节点间的相关性，会带来很高的额外通信开销[3](交换数据来感知节点间相关性带来的额外通信开销)。近年来，国内外研究学者将压缩感知(Compressed Sensing, CS)[4,5]理论应用到网络数据收集中，提出了一种压缩数据收集(Compressive Data Gathering, CDG)[6]方法，该方法将CS的测量过程和WSNs的多跳路由相结合，在传输的过程中即可实现数据压缩，为WSNs高能效数据收集提供了一种理想的解决思路。

然而，文献[7]研究发现，采用传统的稠密测量矩阵作为网络数据收集的测量矩阵会带来密集观测问题，由于每个测量值均由密集观测得到，因此测量值的获取需要极大的通信开销，且进行数据重建时计算量巨大。为避免密集观测问题，文献[8]提出用稀疏随机矩阵作为测量矩阵对网络数据进行测量，该方法计算测量值只需部分节点参与，显著减少了获取测量值的通信开销。文献[9]设计了一种稀疏Toeplitz测量矩阵，该矩阵硬件实现容易，存储成本低，在分布式应用中，可节约获取测量值的通信开销，有效延长网络生命周期。

文献[8]和文献[9]均是从减少参与测量值计算节点个数的角度出发，设计适用于压缩数据收集的稀疏测量矩阵。一般地，参与测量值计算的有效投影节点个数越少且分布越集中，那么获取测量值的通信开销越小。基于这种思想，文献[10]将测量过程和分簇路由相结合，提出了一种可实现网络数据局部化测量的块对角矩阵，但该测量矩阵需要较多的测量次数才能确保原始数据精确重构，抵消了单次测量能耗较低的优势。

针对上述文献的不足，本文将节点间距离作为参数来控制节点当选有效投影节点的概率，设计了一种可以让有效投影节点分布集中化的概率稀疏随机矩阵。概率稀疏随机矩阵既减少了参与测量值计算的有效投影节点个数，又实现了有效投影节点的分布集中化，从而进一步节约了数据收集的通信能耗。在此基础上，为提高网络数据重构精度，本文还提出了一种适用于概率稀疏随机矩阵优化的测量矩阵优化算法。

2 问题描述

在WSNs数据采集应用中，需要将监控区域节点的采集数据传输至sink节点。设监控区域有N个节点，每个节点均采集得到一个数据值，那么整个网络感知得到的数据可用表示。设x可在的稀疏字典D下进行稀疏表示，即为变换系数构成的向量，若，则称θ的稀疏度为K,表示信号的零范数，即信号值不为零的个数。

若整个网络共有M条路由，那么sink节点可获得M个测量值，写成矩阵形式有为测量值向量，为测量矩阵。

图1 压缩数据收集示意图

由上述模型可知，若采用稠密测量矩阵作为网络数据收集的测量矩阵会带来密集观测问题。为避免密集观测问题，文献[8]提出采用稀疏随机矩阵作为测量矩阵对网络数据进行测量，然而随机选择的有效投影节点分布非常分散，获取投影值仍需要很大的通信开销。

一般地，适用于压缩数据收集的测量矩阵应满足以下两个条件：(1)测量矩阵具有良好的稀疏性；(2)测量矩阵可以让同一测量值对应的有效投影节点分布尽可能集中。在下节中将同时考虑以上两个条件，设计一种适用于压缩数据收集的测量矩阵。

3 概率稀疏随机矩阵设计

其中S为测量矩阵的稀疏率，即矩阵非零元素个数占总元素个数的比例。

概率稀疏随机矩阵的设计思想是：在距离矩阵R已知条件下，分别以各节点作为路径开启节点，以节点间距离作为参数来控制节点当选为有效投影节点的概率，设计一个既具有稀疏性又能让有效投影节点分布集中化的测量矩阵。该矩阵构建算法描述如下：

(1)分别以各节点作为路径开启节点，计算其它节点当选为有效投影节点的概率。当节点i为路径开启节点时，节点j当选为有效投影节点的概率为

其中iσ为常数。

依次以各节点作为路径开启节点，计算其它节点当选有效投影节点的概率。将节点当选有效投影节点的概率写成矩阵形式：

那么矩阵Φ称为概率稀疏随机矩阵。

(3)上述得到的概率稀疏随机矩阵Φ有N行，为实现欠采样，可从Φ中等间隔或随机抽取M行构成测量矩阵'Φ。为进一步提升该矩阵的性能，可利用测量矩阵优化理论[1113]-对该矩阵进行优化，第4节将给出一种适用于概率稀疏随机矩阵优化的测量矩阵优化算法。

4 概率稀疏随机矩阵优化

概率稀疏随机矩阵Φ是NN×维的，为实现信号的欠采样，可从中最优抽取M行构成测量矩阵。设为矩阵Φ的行索引集合是矩阵Φ行索引集合的子集，JΦ为Φ中保留集合J对应行构成的测量矩阵，则CS的测量过程可表示如下：为测量值向量y的等效字典。设 ()J=G表示对矩阵列单位化后的矩阵，则称为Gram矩阵。

在测量矩阵优化理论中，一般采用整体互相干系数来衡量测量矩阵和稀疏字典的不相干性。整体互相干系数定义为 Gram 矩阵非对角元素的平方和[12]，即：是 Gram矩阵的元素。整体互相干系数度量了测量矩阵和稀疏字典的相干性，整体互相干系数越小，稀疏近似算法的平均恢复性能越好。为减少整体互相干系数，可求解式(8)的优化问题：表示集合的势，即集合中元素的个数。

上述优化问题是在稀疏字典D和矩阵Φ已知的条件下，求解让平方和最小的行索引子集合J。可根据矩阵各行与稀疏字典的相干性，采用迭代方式，每次迭代删除与稀疏字典相干性最强的行，经过NM-次迭代后得到优化后的测量矩阵optΦ，算法具体步骤如下：

(2)寻找删除该测量向量可最小化整体互相干系数的索引tλ；

(3)删除让测量矩阵整体互相干系数最小化的测量向量，更新测量矩阵；

5 节点分布集中程度分析

证明 采用所有有效投影节点到路径开启节点的距离之和来度量有效投影节点分布的集中程度。要证明概率稀疏随机矩阵的有效投影节点的分布更集中，只需证明任意一条路径，概率随机方式选择的有效投影节点分布平均集中程度均高于随机方式。设节点为路径开启节点，计算其它有效投影节点到节点i距离和的期望。

采用随机方式时，该距离和的期望值为

采用概率随机方式时，该距离和的期望值为

由式(4)可知以节点i作为路径开启节点构建的路由有效投影节点的平均个数为，并结合式(3)可知

将式(11)代入式(10)可得

将式(9)与式(12)相除可得

式(13)当且仅当 1S= 时等式成立，即测量矩阵为稠密矩阵时，两种测量矩阵有效投影节点的分布集中程度一致。当时，概率稀疏随机矩阵的有效投影节点分布集中程度高于稀疏随机矩阵。

证毕

6 实验仿真

使用和文献[14]相同的能量模型，发送数据和接收数据的无线通信模型分别为

图2 有效投影节点的位置分布图

图4和图5分别比较了不同稀疏矩阵完成一次压缩数据收集的全局能耗和重建误差。固定监控区域节点个数为，稀疏系数向量长度为L=，稀疏度为，测量次数为，测量矩阵的稀疏率S由 0.05逐渐增加到 1，步长为0.05。对每个稀疏率S取值，重复实验1000次，计算不同稀疏矩阵完成一次压缩数据收集的平均全局能耗和平均重建误差。由图4可以看出，与稀疏随机矩阵和稀疏Toeplitz测量矩阵相比，当测量矩阵稀疏率小于0.55时，采用概率稀疏随机矩阵作为压缩数据收集的测量矩阵可降低约 15%~30%的通信能耗。这是因为与其它两种矩阵相比，概率稀疏随机矩阵的有效投影节点的分布最集中，因此数据传输所消耗的能量最少。由图5可以看出，在测量矩阵稀疏率一定的情况下，概率稀疏随机矩阵的重建误差与稀疏随机矩阵和稀疏 Toeplitz测量矩阵相仿，但是概率稀疏随机矩阵经过优化后，重建误差小于稀疏随机矩阵和稀疏Toeplitz测量矩阵。

7 结束语

采用稀疏矩阵作为测量矩阵可显著减少获取测量值的通信开销。因此，研究性能优异的稀疏测量矩阵对推动CS理论在WSNs中的应用具有重要意义。结合WSNs的分布式特点，本文设计了一种适用于WSNs压缩数据收集的概率稀疏随机矩阵，该矩阵既减少了计算投影值的有效投影节点个数，又能让有效投影节点分布集中化，显著减少了获取投影的通信代价，有效延长了网络的生命周期。

图3 重建成功率比较

图4 能耗随测量矩阵稀疏率的变化情况

图5 重建误差随测量矩阵稀疏率的变化情况

[1] Akyidiz L F, Su W, Sankarasubramaniam Y, et al.. A survey on sensor networks[J]. IEEE Communications Magazine,2002, 40(8): 102-114.

[2] 宋欣, 王翠荣. 基于线性回归的无线传感器网络分布式数据采集优化策略[J]. 计算机学报, 2012, 35(3): 568-580.Song Xin and Wang Cui-rong. Linear regerssion based distributed data gathering optimization strategy for wireless sensor networks[J]. Chinese Journal of Computers, 2012,35(3): 568-580.

[3] Quer G, Masiero R, and Munaretto D. On the interplay between routing and signal representation for compressive sensing in wireless sensor networks[C]. Proceedings of Information Theory and Applications Workshop, San Diego,2009: 206-215.

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

[5] 许志强. 压缩感知[J]. 中国科学: 数学, 2012, 42(9): 865-877.Xu Zhi-qiang. Compressed sensing: a survey[J]. Scientia Sinica Mathematica, 2012, 42(9): 865-877.

[6] Luo C, Wu F, Sun J, et al.. Compressive data gathering for large-scale wireless sensor networks[C]. Proceedings of the 15th Annual International Conference on Mobile Computing and Networking, Beijing, 2009: 145-156.

[7] Luo J, Xiang L, and Rosenberg C. Does compressed sensing improve the throughput of wireless sensor networks?[C].Proceedings of IEEE International Conference on Communications, Cape Town, 2010: 1-6.

[8] Wang W, Garofalakis M, and Ramchandran K. Distributed sparse random projections for refinable approximation[C].Proceedings of the 6th International Symposium on Information Processing in Sensor Networks, Cambridge, 2007:331-339.

[9] 张成, 杨海蓉, 韦穗. 基于随机间距稀疏Toeplitz测量矩阵的压缩传感[J]. 自动化学报, 2012, 38(8): 1362-1369.Zhang Cheny, Yang Hai-rong, and Wei Hui. Compressive sensing based on deterministic sparse Toeplitz measurement matrices with random pitch[J]. Acta Automatica Sinica, 2012,38(8): 1362-1369.

[10] Lee S, Pattem S, Sathiamoorthy M, et al.. Spatially-localized compressed sensing and routing in multi-hop sensor networks[C]. Proceedings of the Third International Conference on Geosensor Networks, Oxford, 2009: 11-20.

[11] Elad M. Optimized projections for compressed sensing[J].IEEE Transactions on Signal Processing, 2007, 55(12):5695-5702.

[12] Duarte-Carvajalino J M and Sapiro G. Learning to sense sparse signals: simultaneous sensing matrix and sparsifying dictionary optimization[J]. IEEE Transactions on Image Processing, 2009, 18(7): 1395-1408.

[13] Abolghasemi V, Ferdowsi S, and SaeidSanei. A gradientbased alternating minimization approach for optimization of the measurement matrix in compressive sensing[J]. IET Transactions Signal Processing, 2012, 92(4): 999-1009.

[14] Heinzelman W, Chandrakasan A P, and Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communcations, 2002, 1(4): 660-670.