无线传感器网络中基于压缩感知的分簇数据收集算法*

王　冲， 张　霞， 李　鸥

(信息工程大学 信息系统工程学院，河南 郑州 450001)



无线传感器网络中基于压缩感知的分簇数据收集算法*

王冲， 张霞， 李鸥

(信息工程大学 信息系统工程学院，河南 郑州 450001)

摘要:针对无线传感器网络(WSNs)能量有限、通信链路不可靠的特点，提出一种基于稀疏分块对角矩阵进行压缩感知的分簇(SBDMC)数据收集算法。该算法以稀疏分块对角矩阵作为观测矩阵以减少参与收集节点数目；采用分布式分簇路由实现数据的分布式收集；通过分析能耗模型得到最优簇头数目以减少网络能耗。在此基础上，给出一种有效的分簇路由数据收集算法。仿真分析表明:提出的算法较之已有算法可以减少通信能耗、延长网络寿命，同时均衡能耗负载。

关键词:无线传感器网络； 压缩感知； 数据收集

0引言

在无线传感器网络(WSNs)[1]数据收集中，由于节点能量受限、感知数据存在冗余，因此,需要对数据进行压缩处理以节省网络能耗。压缩感知(compressive sensing，CS)理论[2]应用于传感器网络数据收集可以有效地减少数据量，并实现很好的能耗均衡。

近年来，基于压缩感知的WSNs分簇数据收集已将有很多研究。文献[3]采用随机稀疏观测矩阵，减少了单次数据收集参与节点数目、优化了簇头数目以保证能耗最优。文献[4]则优化了采用Hybrid-CS下分簇数据收集的能耗，给出了集中式和分布式两种数据收集方案。文献[5]采用对角分块矩阵作为观测矩阵，分析网络能耗并给出了一种集中式分簇方案。本文采用稀疏分块对角矩阵(sparse block diagonal matrices，SBDM)[6]作为观测矩阵，以一轮数据收集的能耗为优化目标，采用分布式分簇机制，提出了一种基于SBDM的分簇(SBDM-based clustering，SBDMC)数据收集算法。

本文介绍了压缩感知中观测矩阵的设计，分析了通信能耗，给出网络总能耗；最后根据最优簇头数目，提出SBDMC算法，并进行性能的分析与对比。

1压缩感知数据收集

在压缩感知数据收集中，节点采集的数据x=[x1,x2,…,xn]T可以看作是一个n维的原始信号。如果在稀疏基Ψ下可以稀疏表示为稀疏度为k的稀疏信号θ，通过简单的线性变换可以变为M维(m≪n)的观测值y，从而减少通信量。在后端通过已有的正交匹配追踪(OMP),误差反向(BP)算法等成熟的重构算法，可以高精度重构原始数据。观测矩阵的设计是压缩感知数据收集的重要内容。

观测矩阵的设计需要尽可能减少参与数据收集的节点数目，同时需要结合传感器网络特点便于在节点处分布式实现。本文采用SBDM作为观测矩阵，矩阵中各元素以稀疏随机矩阵[7]的生成方式生成，每个元素以1/s的概率取非零值。参数s表征矩阵的稀疏程度，取N/s=lgN，矩阵中每一行平均有N/s=lgN个非零元素。矩阵以对角阵的形式组成观测矩阵，数据收集的具体实现如式(1)

(1)

其中，Φh为每个簇的对应对角阵中的一项在每次数据收集过程中各节点分布式生成观测矩阵的一列，在每次数据收集过程中对应项系数非零的节点将感知数据权值发送到簇头，簇头压缩后得到一个观测值。每个簇头平均收集M/h个观测值，簇头之间不再进一步压缩，Sink可以收集到M个观测值以重构原始数据。文献[8]以高斯随机矩阵为例证明在离散余弦变换(discretecosinetransform,DCT)基下BDM满足压缩感知的RIP条件。

2网络能耗与最优簇头数目

在分簇路由中，网络能耗主要分为两部分：簇内节点上传至簇头的能耗和簇头数据上传至Sink的能耗，即

(2)

(3)

E(d2)=∬r3f(r,θ)drdθ

(4)

由式(3)和式(4)可知，簇内平均通信能耗为

(5)

(6)

网络总的能耗为

(7)

(8)

根据卡尔丹公式可得最优簇头数目为

(9)

3分簇路由的数据收集算法

要想在实际网络中实现网络能耗最优，需要保证分簇的规模大小一致、簇头位于簇中心，这很难实现。结合压缩感知自身具备能耗均衡的特点，本文提出一种簇头数目固定的分布式分簇数据收集策略，主要包括三个部分：首轮分簇、簇头轮换机制以及数据收集策略。

首轮分簇：

1)Sink根据网络实际情况计算最优簇头数目hopt、观测次数M，将网络划分为规模大小尽量相等的hopt个簇，选择中心节点为簇头；

2)Sink发送簇头信息给每个簇头节点，簇头广播自身信息，普通节点选择距离最近的簇头节点作为自身簇头；

3)节点向簇头发送请求信息，簇头恢复确认消息完成首轮分簇。

簇头轮换机制：通过上文分析可知，簇头需要消耗更多的能量，而簇内节点距离簇头越近能耗越小。在余下轮的数据收集中采用基于节点剩余能量的簇头轮换机制，选择簇内剩余能量最大的节点作为簇头，距离簇内节点最近的节点成为下一轮簇头的概率最大。在一定程度上保证簇规模相等、且簇头节点位于簇中心。

分簇完成后开始数据收集，具体实现步骤如下：

1)簇头确定观测次数，并将数据收集划分为M/h个时段，每个时段完成一个观测值数据收集，进一步为个节点分配时隙；

2)节点在对应时隙内，如果对应感知数据权值非零，则将其发送至簇头，簇头将一个时段收集的数据权值求和得到一个观测值；3)簇头将压缩后的M/h个观测值经距离平方最短路径发送到Sink。

在数据收集过程中，簇与簇之间不再进一步压缩，每个簇只需要收集M/h个观测值即可在Sink重构原始数据，减少能耗的同时也降低了数据收集的时延。

4仿真分析

本节利用Matlab仿真工具进行仿真分析验证。设400个节点随机分布在200 m×200 m的正方形监测区域范围内。节点能量为1 J，数据包长度为1 024 bit，能耗参数按照文献[9]设置。本文将提出算法与已有的分簇数据收集算法相比较。对比的分簇数据收集算法包括：

1)LEACH-NC算法，为保证Sink可以重构原始数据以LEACH算法构建分簇的路由，但簇头不对收集到的数据进行压缩处理。

2)文献[5]提出的基于稀疏投影的能量有效数据收集策略(ECDC)。以单次数据收集能耗为优化目标，计算最优簇头数目，簇头之间构建最短生成树路由进一步压缩。

在LEACH-NC中，为获得最优的簇头数目，图 1给出了不同网络环境下网络寿命随簇头比例变化。以死亡10%节点死亡时的数据收集轮数作为网络寿命。在Sink远离网络、Sink在网络边界以及Sink在网络中心三种网络环境下最优的簇头比例分别为0.05,0.03,0.02。在能耗分析中，以最优簇头比例进行数据收集。

图1　LEACH-NC不同簇头概率下的网络寿命Fig 1　Network lifetime of LEACH-NC under different cluster head probabilities

根据上文的理论计算模型，取N/s=lgN≈2.6，可以得到最优簇头数目为8。在压缩比ρ=M/N=0.2的条件下，得到三种网络环境下死亡节点数目随数据收集轮数的变化，如图 2所示。可以得到：1)在网络能耗和生存寿命方面，本文提出的SBDMC算法性能要优于ECDC和LEACH-NC算法。2)采用压缩感知进行数据收集的ECDC和SBDMC算法中，节点在某几轮数据收集内击中死亡，具有很好的能耗均衡性。

5结束语

本文采用SBDM作为压缩感知观测矩阵，进一步减少了参与数据收集的节点数目。根据分析稀疏对角观测矩阵进行数据收集的特点建立网络能耗模型，通过分析该能耗模型，计算得到最优能耗簇头数目。联合节点剩余能量和最优簇头数目，给出一种簇头数目固定的基于节点剩余能量进行簇头轮换的分布式分簇策略，在减少网络能耗的同时实现了网络中各节点能耗均衡。仿真分析表明:与已有算法相比，本文提出算法减少网络能耗、延长了网络寿命。

图2　不同网络环境下死亡节点数目Fig 2　Number of dead nodes in different networks

参考文献:

[1]Akyildiz I F,Su W,Sankarasubramaniam Y,et al.Wireless sensor networks:A survey[J].Computer Networks,2002,38(4):393-422.

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

[3]Wu X,Xiong Y,Huang W,et al.An efficient compressive data gathering routing scheme for large-scale wireless sensor network-s[J].Computers & Electrical Engineering,2013,39(6):1935-1946.

[4]Xie R,Jia X.Transmission-efficient clustering method for wireless sensor networks using compressive sensing[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(3):806-815.

[5]Nguyen M T,Teague K A.Compressive sensing based data gathering in clustered wireless sensor networks[C]∥2014 IEEE International Conference on Distributed Computing in Sensor Systems (DCISS),IEEE,2014:187-192.

[6]Park J Y,Yap H L,Rozell C J,et al.Concentration of measure for block diagonal matrices with applications to compressive signal processing[J].IEEE Transactions on Signal Processing,2011,59(12):5859-5875.

[7]Wang W,Garofalakis M,Ramchandran K.Distributed sparse random projections for refinable approximation[C]∥Proceedings of the 6th Int’l Conf on Information Processing in Sensor Network,ACM,2007:331-339.

[8]Yap H L,Eftekhari A,Wakin M B,et al.The restricted isometry property for block diagonal matrices[C]∥2011 45th Annual Conference on Information Sciences and Systems (CISS),IEEE,2011:1-6.

王冲(1989-)，男，山东淄博人，硕士研究生，研究方向为无线传感网。

Clustering data gathering algorithm for wireless sensor networks based on compressive sensing*

WANG Chong, ZHANG Xia, LI Ou

(School of Information System Engineering,Information Engineering University,Zhengzhou 450001,China)

Abstract:Aiming at characteristics of energy limitation and unreliable communication link of wireless sensor networks(WSNs),a sparse block diagonal matrices clustering(SBDMC)routing data gathering algorithm for compressive sensing is presented.Sparse block diagonal matrix is used as measurement matrix to reduce number of gathering participated nodes;data is collected distributively by distributive cluster routing;and the optimal number of cluster head is obtained by analyzing energy consumption model.On the basis of the above research,an efficient clustering routing data gathering algorithm is proposed.The simulation results show that compared with the existing algorithms,the proposed algorithm can effectively reduce the energy consumption,prolong network lifetime and balance the energy consumption load.

Key words:wireless sensor networks(WSNs); compressive sensing(CS); data aquisition

作者简介:

中图分类号:TP 393

文献标识码:A

文章编号:1000—9787(2016)01—0142—04

*基金项目：国家科技重大专项资助课题(2014ZX03006003)

收稿日期：2015—04—30

DOI:10.13873/J.1000—9787(2016)01—0142—04