无线传感网容错数据融合方案设计

谢冬青，邢萧飞

（广州大学计算机科学与教育软件学院，广东 广州 510006）

无线传感网容错数据融合方案设计

谢冬青，邢萧飞

（广州大学计算机科学与教育软件学院，广东 广州 510006）

数据融合是无线传感器网络中一个重要研究问题，现有基于压缩感知（compressed sensing，CS）的数据融合方案主要是以集中的方式由基站节点完成数据融合任务，容易造成负载不均衡和“覆盖空洞”等问题.文章提出了一个基于压缩感知的容错数据融合（compressed sensing-based erasure-correcting data aggregation，CSEDA）方案，并使用正交匹配追踪（orthogonal matching pursuit，OMP）算法来准确地重构压缩后的数据，在保证所获得数据质量的条件下减少网络通信开销.另外，文章使用节点分簇机制来优化和均衡网络负载.实验结果表明，和其它的数据融合方案相比较，文章所提出的方案在数据重构的容错性和网络能量效率等方面上取得较好性能.

无线传感器网络；数据融合；压缩感知；能量均衡

无线传感器网络（Wireless sensor networks）的产生解决人类对物理信息的采集，将客观的物理世界与人类的逻辑社会联结在一起，因而被广泛应用在工农业、军事、医学护理、环境监测等领域［1］.由于传感器节点在尺寸和成本方面的约束，使其在通信、计算和能量供应等方面受到了极大的限制.因此，在满足网络服务质量条件下如何实现对数据的有效压缩是十分必要的.它可以去除感知信息中的冗余数据，在得到有效数据的前提下，减少节点之间数据通信量，也减少数据通信过程中的碰撞，减轻网络数据拥塞，节省节点能量，从而达到延长网络生存时间的目的.

最近几年在信号处理领域出现的压缩感知（compressed sensing）理论［2-3］提供了一种新的解决思路.它的核心思想是，只要采集的信号在时空域上具有稀疏性的特征，那么它就可以通过使用少量随机线性观测值来重新构造出原始信号.它凭借优异的压缩性能、非自适应编码及编码解码相互独立的特征在信息处理和通信领域受到广泛的关注，成为数据压缩领域最新突出的理论之一.

与传统数据融合技术不同，压缩感知适用于无线传感器网络的数据融合处理的主要原因：①它具有优异的数据压缩性能，实现数据采集和压缩同步完成，大大减少了需要传输的数据量；②编码的低计算复杂度，信号只需要在随机观测矩阵上进行线性投影，便可计算出压缩后的观测向量；③编码和解码的相互独立，对于相同的编码方法，可以使用不同的解码技术，解码节点通过收到的信息数据的观测向量，使用解码算法独立重构数据.同时，在一定概率的原始数据丢失的情况下并不影响对原始数据的重构质量，这保证了数据融合与重构的容错性能.

文献［4］提出了一个基础的压缩感知（compressed sensing，CS）算法，它主要是对城市交通数据进行压缩与重构，有效减少了网络的通信量.文献［5］提出了一个多信道单频谱方案（multi-channel singular spectrum analysis，MSSA），该方案是一个基于滞后协方差矩阵的非参数数据构造，用于部分数据已丢失的地理数据信息的重构.文献［6］提出了能量高效信息收集方案（energy efficient information collection，EEIC），它考虑了节点的能量消耗和感应数据的信息量2方面的因素，从节点收集数据并对其进行压缩处理.文献［7］提出了一个基于有效存储的渐进小波数据压缩算法，该算法依据小波函数的支撑长度和簇头的可用存储容量来确定渐进传送的数据单元，依据空间相关性来选择渐进传送数据的传感器节点，从而在存储有效的同时又节省网络传输耗能.文献［8］提出了一个压缩的稀疏函数方法（compressive sensing functions），它是在一个合适的函数基下通过使用一个改进的压缩感知技术来提高网络中采集数据的压缩质量.也有一些文献从其它角度提出了解决方案，如文献［9］提出了一个基于分簇的数据预测传送方案，根据应用期望的无缝覆盖率与所需簇头数量之间的数学关系来限制节点竞选簇头的初始概率，同时利用簇头节点簇内数据进行聚合，然后传送给基站，但这个方案没有解决丢失数据的重构问题.文献［10］基于改进的层次路由算法LEACH［11］而提出了一个基于分簇的数据融合算法，簇头节点通过非冲突的CSMA方法来压缩收集的数据，并将它传送给基站节点.上述方案存在的问题集中2个方面：①大部分数据压缩与处理以集中的方式由基站节点完成，导致了网络负载的不均衡和“覆盖空洞”等问题的产生；②基于压缩感知技术的数据收集与融合方案仅考虑了以服务为中心的无线传感器网络的某一方面特征，如数据结构特征、数据的相关性和数据重构成功概率等，缺少对网络这些特征的整体解决措施.本文依据网络节点之间数据传输的特征，提出一种基于压缩感知理论的容错数据融合（Compressed Sensing-based Erasure-Correcting Data Aggregation，CS-EDA）方案.同时，针对传感器网络在应用中因节点负载的不同，造成局部“覆盖空洞”情况的发生，设计了一个低开销的网络分簇方法，使所提出的方案在数据通信、能量效率、负载均衡和数据容错等方面具有比较好的性能，从而在保障网络服务质量的条件下，延长网络的生存时间.

1 网络模型与问题定义

1.1 网络模型

本文假设网络具有如下特征：

（1）节点是同构的，节点具有相同大小的感知半径和通信半径，节点采用有向的感知模型［12］；

（2）节点通信半径是其感知半径的2倍，一个完全覆盖的网络确保了节点之间的连通性；

（3）节点以随机均匀形式部署在监测区域，节点保持时钟同步.

1.2 问题定义

在给出正式问题定义之前，首先给出相关的定义.

定义1（节点有向感应模型）：节点有向感应模型定义为一个四元组＜O，Rs，V，α＞，见图1，其中，O＝（x，y）表示有向传感器节点的位置坐标，Rs表示节点的感知半径，单位向量V＝（Vx，Vy）为扇形感应区域中轴线，即节点的感应方向；Vx和Vy分别是单位向量V在X轴和Y轴方向上的投影分量；α表示覆盖边界与感应向量V的感应夹角.

图1 节点有向感应模型Fig.1 Diretional sensing model

定义2（感应矩阵）：它用于描述传感器网络监测的动态环境信息，其数学形式如下：

这里的n和t分别表示节点数量和节点在不同时间采集数据数量.

定义3（重构矩阵）：它是通过数据重构算法得到的近似于感应矩阵的重构矩阵，其数学表述形式如下：

问题定义：给定一个感应矩阵X，如何对其数据进行压缩，使得重构后的重构矩阵X′尽可能地接近X，即X′与X之间的误差最小化的问题.其数学表达如下：

2 基于压缩感知的容错数据融合方案

本节提出基于压缩感知的容错数据融合方案（Compressed Sensing-based Erasure-correcting Data Aggregation，CS-EDA），其基本思想是以分簇网络为基础，采用时间轮方式来选择簇头节点，簇头节点负责收集和融合数据，并将处理后的数据发送给基站节点，基站节点完成原始数据的重构任务.

2.1 分轮机制

本文采用时间分轮的方法，将整个网络运行时间划分成若干大小相等的时间段，每个时间段称为一个“轮”.每个时间轮由初始阶段和工作阶段组成，其中，工作阶段的时间长远大于初始阶段.在初始阶段完成包括节点覆盖面积计算和簇头选举等在内的网络分簇任务，在工作阶段实现对目标数据的采集和融合工作.算法在整个网络上以时间轮的方式运行，直至节点能量耗尽为止.同时，由于不需要事先掌握整个网络的拓扑结构，减少了系统的计算量和通信量.时间轮的划分见图2.

图2 网络时间轮划分Fig.2 Timeline of network

2.2 网络分簇

首先依据节点的覆盖面积来划分网络分簇的大小，然后在每个簇内选择出簇头节点（Cluster head）.

（1）目标覆盖判断

在时间轮的初始阶段，根据节点的感知和通信半径大小和用户对网络覆盖质量的要求，将整个监测区域划分成一些大小相等的虚拟网格（C1，C2，…，Cm）.任意一个节点的通信范围能够覆盖其相邻节点的位置，这样2个相邻的节点能够相互直接通信.各个节点计算其在所在虚拟网络内的覆盖面积（见图3），并根据其覆盖面积所在网格内的大小决定其属于哪一个网格.从属于相同网格的节点组成了一个网络分簇，为了提高网络的性能，在分簇实现过程中需要注意以下2方面的因素：

· 监测目标：保证每一个待监测的目标至少要被一个网络分簇覆盖.

· 节点分布：部署的节点密度要满足网络覆盖和连通性的要求.由于分簇大小与节点有效的覆盖面积成反比，当节点的有效覆盖面积较大，需要缩小虚拟网格的大小.同时需要保证相邻簇头之间能够进行通信.

图3 节点覆盖面积的计算Fig.3 The calculation of node′s coverage area

对目标的覆盖判断，本文采用了以下方法：假定监测目标位于P点位置，节点Si位于O点，2点之间只需要满足下面2个公式，则可以判定目标被有向传感器节点覆盖.

这里β为0P与V之间的夹角.

（2）簇头选举

相比较普通成员节点，簇头节点承担了更多的任务，因此，簇头节点的选择首先依据剩余能量大小，其次是节点位置；靠近网格中心的节点具有优先权.在首次网络分簇形成之后，随机选择一个位置靠近中心的节点作为簇头节点；在其后的时间轮内，由成员节点向原簇头节点发送一个“vote”竞选消息，该消息包括节点ID、剩余能量、位置等信息.节点Si成为簇头的概率采用公式（6）计算［6］.

原簇头节点在收集到成员发送的“vote”消息后，计算并比较的大小，选择其中最大的一个节点作为簇头.新的簇头节点向各成员节点发送一个“invitation”邀请消息，成员节点收到消息后确认，完成本轮簇头选举工作.在簇内，成员节点直接将数据发送给簇头节点；在簇间，簇节点将簇内数据与其它簇头节点传送来的数据采用下文所提出的融合算法压缩后发向基站节点.

2.3 空间相关性数据的收集与压缩

对于簇内成员节点采集的数据，这些数据通常具有时域和空域上的相关性［13］，而要使这些数据具有稀疏的特性，需要对其进行处理.首先除去公共部分，只保留私有部分，然后对私有部分做压缩处理，重构之后再加上公共部分，这样就能减少重构误差，提高节点对数据处理的速度，同时降低通信开销.

利用离散余弦变换（DCT）对数据进行稀疏变换.利用DCT的原因是它能够将大多数的信号的关键信息都集中在信号变换后的低频部分，DCT变换函数如下：

簇头节点将DCT函数变换得到需要的观测向量发送给基站节点.为了快速重构出原始数据，需要控制向量的规模不超过1 000.由于本文采用了网络分簇机制，每个簇内节点规模数控制在20以内，使得观测向量规模较小，因此，基站节点较为容易地重构得到原始数据.

2.4 数据重构算法设计与分析

对数据的重构采用的是正交匹配追踪算法来解决.数据重构算法实现步骤如下：

输入：n×t维测量矩阵Φ，n维观测向量y，理想数据矩阵的稀疏度k.

输出：重建的t维恢复数据X′，从｛1，…，t｝中选取的含有k个元素的指标集Γk，对y的n维近似向量ak，n维残差向量rm＝y-ak.

第1步：初始化剩余量，指标集Γk＝Φ，迭代计数器i＝0；

第2步：找到满足下面最优化问题的指标λi

第4步：求解最小二乘问题

第5步：计算新的数据估计和残差：yi＝Φixi，ri＝y-yi；

第6步：i＝i+1，假如i＜k，返回到第2步；

第7步：重构X′的非零值指标为Γk中的元素，X′的第λJ个元素的值等于xi的第J个元素.

算法的基本思想是在每次数据迭代中将从完备库中选出的原子使用Gram-Schmidt正交化方法进行正交化处理，再将所得到的采样数据在这些正交原子形成的空间上进行投影，得到数据在这些正交原子上的分量和余量，然后利用相同的方法进行余量分解，这些余量随分解过程的进行而迅速减小.通过递归对已选择原子集合进行正交化，这保证了迭代的最优性，减少了迭代次数.对一个k度稀疏n×t维测量矩阵，算法以极大概率重构原始数据矩阵值，其复杂度仅为O（knt）.

3 实验评价及分析

为了评价本文所提出的CS-EDA方案的性能，本节使用Matlab仿真工具和Intel Berkeley实验室对室内温度、湿度和光照强度等监测的真实数据集［14］来评价所提出方案的性能，这个数据包含了室内温度、湿度和光线强度等信息.并将所提出的CS-EDA方案与压缩感知（Compressed Sensing，CS）方案［4］、多信道单频谱方案（Multi-channel singular Spectrum Analysis，MSSA）［5］和能量高效信息收集方案（Energy Efficient Information Collection，EEIC）［6］做了不同评价标准下的性能对比.

3.1 实验环境和评价标准

为了评价网络的生存时间，本文通过MATLAB平台进行实验，传感器节点被随机部署在一个200 m*200 m的目标区域，整个监测区域被划分成16个虚拟网格.部署的节点数量分别是100、150和200，各代表节点分布的稀疏、中等、稠密环境，节点能耗采用文献［11］所提出的能耗模型，计算节点发送与接收数据所消耗的能量如公式（8）和公式（9）所示，其参数值分别设置为ET-elec＝50nJ/bit，ER-elec＝100nJ/bit，εfs＝10pJ/bit/m2.

其它实验环境参数的设置见表1.

表1 实验环境参数Table 1 Simulation parameters

实验首先分别进行不同数据丢失率条件下各个方案重构数据的出错率对比，数据重构的出错率η定义如公式（10）所示.其次从不同网络节点分布密度和分簇来评价网络的能量效率.

3.2 实验结果分析

图4（a）～（c）是针对节点采集的室内温度、湿度和光照强度数据在不同数据丢失率条件下4个方案在数据重构出错率的对比.通过对比这3个实验数据结果，本文所提的CS-EDA方案在4个方案中性能最好.从图4可见，数据丢失率从10%增加90%时，CS-EDA方案的数据重构的出错率保持在10%到20%的范围内，而其它3个方案的数据重构出错率较高，MSSA方案最高数据出错率接近于60%.同时，相比较图4（a）和（b）的室内温度和湿度实验数据重构结果，4个方案在图4（c）室内光照的数据重构出错率变化较小，这主要是因为光线强度的数据的相关度要比前两者高.

图4 测试室内不同条件下不同数据丢失率下数据重构的出错率对比Fig.4 Comparison of the 4 algorithms under different data loss probability

图5 不同节点分布密度条件下网络生存时间对比Fig.5 Comparison of the 3 algorithms terms of network lifetime

图5（a）～（c）是3种不同节点分布密度条件下网络生存时间的对比，这3种不同节点分布分别表示稀疏（N＝100）、中等（N＝150）和稠密（N＝200）的节点分布环境.从图5中可见网络生存时间越久，死亡的节点数越多.同时，通过计算这3种实验结果，CS-EDA方案比MSSA和EEIC方案在网络生存时间上分别平均提高了13.9%和39.7%，相比稀疏的节点部署环境，实验数据说明了CS-EDA方案在稠密节点部署环境下能够明显地提高网络生存时间.同时，本文也对比网络节点的剩余能量的大小，在稀疏的网络实验环境下，当死亡节点数为10时，本文随机选取了5个工作节点对比它们的剩余能量，其结果见图6.通过计算，CS-EDA方案比MSSA和EEIC方案在节点剩余能量上分别平均提高了16.1%和35.1%.

图6 节点剩余能量对比Fig.6 Comparison on the residual enery of nodes（N＝100）

图7为不同网络分簇条件下网络生存时间对比.网络被划分3种不同的分簇数，不同分簇对应的分簇大小见表2.从图7可见，当k＝16时，网络能够得到最大的生存时间.这表明将每个分簇网格大小与节点覆盖面积大小接近时，节点的能量效率最高，其原因是此时节点之间能够维护较好的覆盖和通连性，簇头节点与成员节点及其它簇头节点之间的通信效率最高.

图7 不同网络分簇下网络生存时间对比Fig.7 Comparison of network lifetime under different cluster size（N＝100）

表2 3种网络分簇Table 2 Three types of cluster size

4 结 论

由于无线传感网在能量、计算和存储等方面的限制，本文提出了一个基于压缩感知理论的容错数据融合方案，利用数据在时空域上的稀疏性特征，通过对原始数据进行有效处理来减少网络节点之间数据通信量，在数据丢失率较高条件下，方案能够重构出绝大部分的原始数据信息，提高了网络数据融合的容错性能.同时方案采用了网络分簇技术，通过将网络划分成若干大小合适的簇集合，优化和均衡了各节点之间的负载，提高了整个网络在通信和能量上的效率，从而在保证有效传输数据条件下，有效地延长了网络生存时间.

［1］ WANG F，LIU J.Networked wireless sensor data collection：Issues，challenges and approaches［J］.IEEE Commun Surv Tutor，2011，13（4）：673-687.

［2］ KULKAMNI R V，FORSTER A，VENAYAGAMOORTHY G K.Computational intelligence in wireless sensor networks：A survey［J］.IEEE Commun Surv Tutor，2011，13（1）：68-96.

［3］ 焦李成，杨淑媛，刘芳，等.压缩感知回顾与展望［J］.电子学报，2011，39（7）：1651-1662.JIAO L C，YANG S Y，LIU F，et al.Development and prospect of compressive sensing［J］.Acta Electr Sin，2011，39（7）：1651-1662.

［4］ LI Z，ZHU Y M，ZHU H Z，et al.Compressive sensing approach to urban traffic sensing［C］∥Proceed IEEE Icdcs，2011：889-898.

［5］ ZHU H，ZHU Y，LI M，et al.SEER：Metropolitan-scale traffic perception based on lossy Sensory data［C］∥ProceedIEEE Infocom，2009：217-225.

［6］ CHOU C，RANA R H U.Energy efficient information collection in wireless sensor networks using adaptive compressive sensing［C］∥Proceed IEEE LCN，2009：443-450.

［7］ 周四望，林亚平，叶松涛，等.传感器网络中一种存储有效的小波渐进数据压缩算法［J］.计算机研究与发展，2009，46（12）：2085-2092.ZHOU S W，LIN Y P，YE S T，et al.A wavelet data compression algorithm with memory-efficiency for wireless sensor network［J］.J Comput Res Devel，2009，46（12）：2085-2092.

［8］ XU L，QI X，WANG Y，et al.Efficient data gathering using compressed sparse functions［C］∥Proceed IEEE Infocom，2013：310-314.

［9］ 杨军，张德运，张云翼，等.基于分簇的无线传感器网络数据汇聚传送协议［J］.软件学报，2010，21（5）：1127-1137.YANG J，ZHANG D Y，ZHANG Y Y，et al.Cluster-based data aggregation and transmission protocol for wireless sensor networks［J］.Chin J Softw，2010，21（5）：1127-1137.

［10］LIU Y，ZHU L，TANG W.The data aggregation of wireless sensor networks based on compressed sensing and cluster［J］.J Comput Inform Sys，2013，9（9）：3399-3406.

［11］HEINZELMAN W，CHANDRAKASAN A，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Trans Wirel Commun，2002，1（4）：660-670.

［12］TAO D，TANG S，ZHANG H，et al.Strong barrier coverage in directional sensor networks［J］.Comput Commun，2012，35（8）：895-905.

［13］WANG P，AKYILDIZ I F.Spatial correlation and mobility-aware traffic modeling for wireless sensor networks［J］.IEEE/ ACM Trans Net（TON），2011，19（6）：1860-1873.

［14］Intel Indoor Test Data［EB/OL］.http：//www.select.cs.cmu.edu/data/labapp3/index.htm l.

Design of an erasure-correcting data aggregation approach for w ireless sensor networks

XIE Dong-qing，XING Xiao-fei
（School of Computer Science and Educational Software，Guangzhou University，Guangzhou 510006，China）

Data aggregation is a key issue in wireless sensor networks（WSNs）.Existing compressed sensing（CS）-based data aggregation work utilizes the centralized method to process the data by a sink node，which causes the load imbalance and“coverage hole”problems.This paper presents a CS-based erasure-correcting data aggregation（CS-EDA）approach and designs a data reconstruction algorithm to perform data recovery tasks by utilizing the orthogonal matching pursuit theory，which reduces communication cost under guaranteeing the quality of obtained data.Moreover，the energy consumption of network is optimized and balanced by using clustering mechanism.Simulation results demonstrate that the proposed CS-based erasure-correcting data aggregation approach obtains a better performance on the metrics of accurate data reconstruction and energy efficiency significantly compared to existing methods.

wireless sensor network（WSN）；data aggregation；compressed sensing；energy balance

TP 393

A

1671-4229（2016）01-0001-07

【责任编辑：陈 钢】

2015-12-20；

2016-01-06

国家自然科学基金委-广东联合基金资助项目（U1135002）；中国博士后科学基金资助项目（2014M562153）；广州市教育局市属高校科研基金资助项目（1201430560）；广东省教育厅青年创新人才资助项目（2015KQNCX109）

谢冬青（1965-），男，教授，博士.Email：dongqing_xie＠hotmail.com