适用于无线传感器网络的层次化分布式压缩感知

2017-10-14程银波司菁菁候肖兰

电子与信息学报 2017年3期

程银波司菁菁候肖兰

程银波司菁菁*候肖兰

(燕山大学信息科学与工程学院秦皇岛 066004)

分布式压缩感知(Distributed Compressed Sensing, DCS)是在无线传感器网络(Wireless Sensor Network, WSN)中减少数据传输量、降低能量消耗的有效手段。该文面向分簇WSN，提出层次化分布式压缩感知(Hierarchical Distributed Compressed Sensing, HDCS)。在利用簇内DCS消除簇内时间、空间冗余的基础上，利用簇间DCS消除簇间空间冗余，减少簇头的数据发送量。针对分簇WSN采集信号的结构化稀疏特性，建立块稀疏簇内联合稀疏模型与块稀疏簇间联合稀疏模型，提出HDCS观测方案与层次化联合重构算法。仿真结果表明，与普通DCS相比，HDCS在保证重建信号质量的同时，能够有效减轻簇头的通信负担，并显著降低Sink上的信号重构时间。

无线传感器网络；分布式压缩感知；层次化分布式压缩感知；分簇

1 引言

有效的分簇结构能够提高无线传感器网络(Wireless Sensor Network, WSN)[1,2]的资源利用率、降低路由复杂度、增强网络稳定性[3,4]。研究表明，在分簇WSN中应用压缩感知(Compressed Sensing, CS)[5]或分布式压缩感知(Distributed Compressed Sensing, DCS)[6]技术能够有效降低网络中的数据传输能耗、延长网络的工作寿命。然而，现有的研究成果主要基于CS/DCS实现分簇WSN中簇内成员采集数据的压缩以及簇头生成(或接收到)的CS/ DCS压缩数据向Sink的多跳汇聚。例如，文献[7]研究CS与分簇算法的融合，在分簇算法的基础上应用CS技术压缩簇内成员采集的数据，减少网络中的数据传输量。文献[8]在混合CS模型下研究簇的大小与传输数据量的关系。文献[9-11]研究簇头CS数据的簇间多跳、多分辨率、层次化路由策略。实际上，在同一监测区域内，不但簇内成员采集的数据间具有时间、空间相关性，相邻簇间也具有很强的空间相关性。如果能够在利用DCS去除簇内成员采集数据的时间、空间冗余的基础上，对各簇簇头采集到的数据继续进行压缩，去除簇间冗余，则有望进一步降低簇头的通信负担，延长网络的工作寿命。

针对这一问题，本文面向分簇WSN，提出层次化分布式压缩感知(Hierarchical Distributed Compressed Sensing, HDCS)。首先，研究层次化联合稀疏模型的构建，利用簇内联合稀疏模型描述簇内成员采集数据的时间相关性与空间相关性，利用簇间联合稀疏模型描述同一监测区域内各簇采集数据的空间相关性。进而，研究HDCS的层次化观测方案，并基于WSN采集信号的结构化稀疏特性，提出HDCS的层次化联合重构方案。在保证信号重建质量的同时，尽可能减少簇头转发的数据量。最后，利用合成信号和实际WSN测得的温度信号分析HDCS的性能，并与普通DCS进行比较。

2 问题模型

3 层次化分布式压缩感知

联合稀疏模型(Joint Sparsity Model, JSM)的建立是DCS的一个关键问题。本文基于分簇WSN中传感器采集数据的结构化稀疏特性，构建簇内JSM与簇间JSM，并在此基础上研究簇内DCS与簇间DCS。

3.1 簇内DCS

3.2 簇间DCS

表1 joint BOMP算法的伪代码

3.2.2 簇间JSM 实验中发现，簇头重建的簇内公共成分系数向量与成员特有成分系数向量仍然具有分块稀疏特性。据此，本文在混合支撑集模型[13]的基础上构建块稀疏簇间JSM，描述同一监测区域内个簇簇内公共成分系数向量的相关性。将建模成簇间公共成分与簇特有成分之和的形式，即

(6)

3.3 HDCS的层次化联合重构

进一步，本文针对块稀疏簇间JSM，设计了joint BPMMPIP算法(伪代码如表2所示)，用于实现的联合重构。根据式(5)所示的观测过程，若以传感矩阵、列块集合、索引集、观测向量、簇间公共块稀疏度、各簇特有块稀疏度、扩张路径数、剪枝操作开始的层数和剪枝比例作为输入，则可基于joint BPMMPIP算法输出的重构出。

4 传输能耗与重建复杂度分析

(1)数据传输量分析：设同一监测区域内的个簇中各包含个成员节点，每个成员单位时间段内采集信号的长度为、生成的观测值数量为。在HDCS中，每个簇内的个成员需要向簇头传输的总观测值数量为，与普通DCS相同。若设每个簇头在进行簇间DCS观测时生成个簇间公共成分观测值和个成员特有成分观测值，则个簇头需要向Sink传输的总观测值数量为，而在普通DCS方案中，个簇头需要向Sink汇聚的总观测值数量为。将与之比表示为

(2)传输能耗分析：HDCS与普通DCS的簇内数据传输能耗相同，因此本文主要比较两方案的簇头数据传输能耗。结合文献[9,11,15,16]中的能耗分析模型，HDCS方案中个簇头上的数据传输总能耗与普通DCS方案中个簇头上的数据传输总能耗可分别表示为

(9)

表2 joint BPMMPIP算法的伪代码

5 仿真结果与分析

编写Matlab仿真程序，分别利用随机合成信号和Intel Berkeley Research Lab真实WSN测得的温度信号(来自http://db.csail.mit.edu/labdata/ labdata.html)测试本文提出的HDCS的性能，并与普通DCS进行比较。实验中HDCS采用3种不同的实现方案。方案1利用joint BOMP实现簇内、簇间重构；方案2利用joint BOMP实现簇内重构、利用joint BPMMPIP实现簇间重构；方案3利用joint BPMMPIP实现簇内、簇间重构。在普通DCS方案中，簇内成员的观测与Sink的重构采用与HDCS方案1中的簇内观测与簇内重构相同的方法。本文在采样率相同、传输数据量之比的情况下，比较HDCS与普通DCS的重建效果；在采样率相同、重建效果相同的情况下，通过计算值比较HDCS与普通DCS需要在网络中传输的数据量。仿真计算机的硬件配置为CPU AMD athlon(tm)255，主频3.11 GHz，内存1.75 GB。软件环境为32位Windows7操作系统下的Matlab R2010a。实验在每个指定采样率下重复进行100次。以归一化均方误差(Normalized Mean Squared Error, NMSE)作为衡量算法重建效果的指标。

由图1可见，随着采样率的增加，4种方案的NMSE值均逐渐降低。在相同采样率下，HDCS方案的NMSE值要低于普通DCS，且HDCS方案1，方案2，方案3的NMSE值依次降低。这说明，当簇头传输数据量相同时，HDCS具有优于普通DCS的重建性能，而且HDCS方案3的重建性能优于方案2，方案2的性能优于方案1。由图2可见，在达到相同NMSE值时，HDCS需要在网络中传输的数据量明显低于普通DCS。而且，随着采样率的增加，HDCS与普通DCS需传输的数据量之比逐渐降低。例如，当采样率为0.3时，HDCS方案1，方案2，方案3需要在网络中传输的数据量仅为普通DCS的73.5%, 60.2%和57.6%。

接下来，采用Intel Berkeley Research Lab真实WSN测得的温度值进行实验。选取小空间范围内的传感器1~30，将传感器1~5, 6~10, 11~15, 16~20, 21~25, 26~30组成6个簇。将日期2004.03.01-2004.03.07测得的温度值每隔3.5 min采样一个点，得到长度为2048的信号。选取sym8小波基作为,和，将,,构造成元素符合高斯分布且每一行经过归一化处理的随机矩阵。图3显示了当时，3种HDCS方案和普通DCS在相同采样率下获得的NMSE值的对比情况。图4显示了达到相同的NMSE值()时，3种HDCS方案需要在网络中传输的数据量分别相对于普通DCS的归一化值，即值。

由图3可见，当簇头传输数据量相同时，HDCS的NMSE值低于普通DCS，即HDCS具有优于普通DCS的重建性能。由图4可见，当获得相同的NMSE值时，HDCS需要在网络中传输的数据量要显著低于普通DCS，而且随着采样率的增加，相对值越来越小。例如，当采样率为0.3时，HDCS方案1，方案2，方案3需要在网络中传输的数据量仅为普通DCS的77.1%, 53.5%和42.2%。

图1 合成数据实验中数据量相同时4种方案的NMSE值比较

图2 合成数据实验中当时3种HDCS方案的值比较

图3 实际数据实验中数据量相同时4种方案的NMSE值比较

图4 实际数据实验中当时3种HDCS方案的值比较

最后，比较HDCS与普通DCS在Sink上的重构时间。表3、表4分别展示了在采用合成数据与实际数据进行的实验中，当时，在部分采样率下，HDCS方案1，方案2在Sink的重构时间与普通DCS重构时间的比值。HDCS方案3采用的簇间重构算法与方案2相同，因此其在Sink的重构时间与方案2相同。由表3、表4可见，HDCS的重构时间显著低于普通DCS。此外，表3、表4还表明HDCS方案1的重构时间低于方案2，即joint BOMP算法的运行时间低于joint BPMMPIP算法。

表3 合成数据实验中HDCS与普通DCS重构时间之比

采样率0.140.180.220.260.30 HDCS方案10.03300.03540.03670.03740.0412 HDCS方案20.27070.29600.31830.34000.3750

表4 实际数据实验中HDCS与普通DCS重构时间之比

采样率0.140.180.220.260.30 HDCS方案10.00850.00970.01100.01220.0131 HDCS方案20.28200.29300.31200.34500.3730

综合上述仿真实验结果可见，与普通DCS相比，本文提出的HDCS在保证重建信号质量的同时，能够明显降低分簇WSN中簇头的数据传输量，并显著降低Sink上的信号重构时间。比较本文提出的joint BOMP算法与joint BPMMPIP算法可见，joint BOMP算法的运算时间较低，而joint BPMMPIP算法的联合重建性能较高。比较3种HDCS实现方案可见，方案1的重构时间最低，方案3的联合重构性能最高，而方案2能够在簇头运算时间与Sink节点重构性能方面获得较好的折中。

6 结束语

本文基于分簇WSN的空间结构特性以及传感器采集数据的结构化稀疏特性研究HDCS。在利用簇内DCS联合去除簇内成员采集数据的时间冗余与空间冗余的同时，利用簇间DCS去除同一监测区域内多个簇采集数据的空间冗余。构造了块稀疏簇内JSM，并提出了簇内DCS重构算法joint BOMP；构造了块稀疏簇间JSM，并提出了簇间DCS重构算法joint BPMMPIP。利用合成信号与WSN实测温度信号进行的仿真实验表明，与普通DCS相比，当网络传输数据量相同时，HDCS能够获得更高的重建效果；当重建效果相同时，HDCS能够明显降低簇头的数据发送量。此外，与普通DCS相比，HDCS显著降低了Sink上的信号重建时间。

由于实验条件的限制，本文主要利用计算机仿真实验对HDCS方案进行了验证与性能分析，HDCS在实际WSN上的实现与性能分析有待进一步研究。另一方面，本文设计的HDCS方案需要簇头进行簇内重构与簇间观测，因此簇头的计算任务要高于普通DCS。接下来将研究簇头对簇内采集数据的二次观测，以减轻簇头的计算负担。此外，如何在块稀疏度未知的情况下实现HDCS重构也是一个需要继续研究的问题。

[1] CHEN H, SHI Q, TAN R,. Mobile element assisted cooperative localization for wireless sensor networks with obstacles[J]., 2010, 9(3): 956-963. doi: 10.1109/TWC. 2010.03.090706.

[2] CHEN H, GAO F, MARTINS M,. Accurate and efficient node localization for mobile sensor networks[J]., 2013, (18): 141-147. doi: 10.1007/s11036-012-0361-7.

[3] PRASATH K and SHANKAR T. RMCHS: ridge method based cluster head selection for energy efficient clustering hierarchy protocol in WSN[C]. Proceedings of International Conference on Smart Technologies and Management for Computing, Communication, Controls, Energy and Materials, Chennai, India, 2015: 64-70.

[4] 唐宏, 王惠珠. 基于无线信号不规则性的无线传感网层次型拓扑控制算法[J]. 电子与信息学报, 2015, 37(9): 2246-2253. doi: 10.11999/JEIT141626.

TANG Hong and WANG Huizhu. Wireless signal irregularity based hierarchical topology control algorithm for wireless sensor networks[J].&, 2015, 37(9): 2246-2253. doi: 10.11999/ JEIT141626.

[5] DONOHO D. Compressed sensing[J]., 2006, 52(4): 1289-1306. doi: 10.1109/ TIT.2006.871582.

[6] BARON D, DUARTE M, SARVOTHAM S,. An information-theoretic approach to distributed compressed sensing[C]. Proceedings of the 43rd Allerton Conference on Communication, Control, and Computing, Monticello, USA, 2005: 814-825.

[7] NGUYEN M and RAHNAVARD N. Cluster-based energy- efficient data collection in wireless sensor networks utilizing compressive sensing[C]. Proceedings of IEEE Military Communication Conference, San Diego, USA, 2013: 1708-1713.

[8] XIE R and JIA X. Transmission-efficient clustering method for wireless sensor networks using compressive sensing[J]., 2014, 25(3): 806-815. doi: 10.1109/TPDS.2013.90.

[9] NGUYEN M, TEAGUE K, and RAHNAVARD N. Inter- cluster multi-hop routing in wireless sensor networks employing compressive sensing[C]. Proceedings of IEEE Military Communication Conference, Baltimore, USA, 2014: 1133-1138.

[10] XU X, ANSARI R, KHOKHAR A,. Hierarchical data aggregation using compressive sensing(HDACS) in WSNs[J]., 2015, 11(3): 1-25. doi: 10.1145/2700264.

[11] LIU D, ZHOU Q, ZHANG Z,. Cluster-based energy- efficient transmission using a new hybrid compressed sensing in WSN[C]. Proceedings of IEEE Conference on Computer Communications Workshops, San Francisco, USA, 2016: 372-376.

[12] ELDAR Y, KUPPINGER P, and BOLCSKEI H. Block- sparse signals: Uncertainty relations and efficient recovery[J]., 2010, 58(6): 3042-3054. doi: 10.1109/TSP.2010.2044837.

[13] SUNDMAN D, CHATTERJEE S, and SKOGLUND M. Distributed greedy pursuit algorithms[J]., 2014, 105(12): 298-315. doi: 10.1016/j.sigpro.2014.05.027.

[14] 司菁菁, 候肖兰, 程银波. 基于块剪枝多路径匹配追踪的多信号联合重构[J]. 系统工程与电子技术, 2016, 38(9): 1993-1999. doi: 10.3969/j.issn.1001-506X.2016.09.05.

SI Jingjing, HOU Xiaolan, and CHENG Yinbo. Joint multi-signal reconstruction based on block pruning multipath matching pursuit[J]., 2016, 38(9): 1993-1999. doi: 10.3969/j.issn.1001-506X.2016. 09.05.

[15] CHEN H, LIU B, HUANG P,. Mobility-assisted node localization based on TOA measurements without time synchronization in wireless sensor networks[J]., 2012, 17(1): 90-99. doi: 10.1007/s11036-010-0281-3.

[16] CHEN H, WANG G, WANG Z,. Non-line-of-sight node localization based on semi-definite programming in wireless sensor networks[J]., 2012, 11(1): 108-116. doi: 10.1109/TWC. 2011.110811.101739.

Hierarchical Distributed Compressed Sensing for Wireless Sensor Network

CHENG Yinbo SI Jingjing HOU Xiaolan

(,,066004,)

Distributed Compressed Sensing (DCS) is an effective means to reduce the amount of data transmission and energy consumption in Wireless Sensor Network (WSN). Hierarchical Distributed Compressed Sensing (HDCS) is proposed for clustering WSN. It eliminates the temporal-spatial redundancies among data collected by the cluster members with the intra-cluster DCS, and eliminates the spatial redundancies among clusters with the inter-cluster DCS. According to the signal’s structured sparsity, a block-sparse intra-cluster joint sparsity model and a block-sparse inter-cluster joint sparsity model are constructed. Then, a hierarchical measurement scheme and a hierarchical joint reconstruction scheme are proposed for HDCS. Experimental results show that compared to general DCS, HDCS can relieve the transmission burden in the network effectively, without lowering the quality of the reconstructed signal. Moreover, it can reduce the signal reconstruction time at the Sink observably.

Wireless Sensor Network (WSN); Distributed Compressed Sensing (DCS); Hierarchical Distributed Compressed Sensing (HDCS); Cluster

TP393

1009-5896(2017)03-0539-07

10.11999/JEIT160439

2016-05-03；改回日期：2016-11-23；

2017-01-11

司菁菁 sjj@ysu.edu.cn

国家自然科学基金(61471313, 61303128)，河北省自然科学基金(F2014203183)，燕山大学青年教师自主研究计划课题(13LGB015)，秦皇岛市科学技术研究与发展计划(201602A031)

The National Natural Science Foundation of China (61471313, 61303128), The Natural Science Foundation of Hebei Province (F2014203183), The Youth Foundation of Yanshan University (13LGB015), The Science and Technology Plan of Qinhuangdao (201602A031)

程银波：男，1978年生，讲师，研究方向为分布式计算.

司菁菁：女，1980年生，副教授，研究方向为多媒体通信与信号处理.

候肖兰：女，1988年生，硕士生，研究方向为分布式压缩感知.