基于遗传压缩感知的无线传感器网络数据压缩方法

张 娜

基于遗传压缩感知的无线传感器网络数据压缩方法

张 娜

(河南城建学院计算机科学与工程学院 河南 平顶山 467036)

考虑到无线传感器网络WSNs能量、通信带宽、计算能力及成本有限，不适合大规模数据传输，同时存在数据冗余，需要进行数据压缩处理，提出一种新的基于遗传算法的压缩感知CS(Compressive Sensing)重构方法，应用于无线传感器网络数据压缩中。详细阐述分布式WSNs数据压缩特点，压缩感知基本理论，基于遗传算法的CS重构新方法以及在WSNs数据压缩中的应用。通过实验仿真证明，从压缩比、节点平均能耗、网络生存时间和网络时延四个方面，与DCCM算法及CCS算法的WSNs数据压缩算法进行比较，提出的算法具有较高的压缩比，提高了采集数据的重构精度，降低了数据冗余度和网络通信量，提高了网络效率。

无线传感器网络 压缩感知 遗传算法 压缩比 生命周期

0 引 言

随着WSNs不断的发展，信号采集需要的带宽和数据量现已成几何方式增长。因此必须建立新型采样机制以减少成本、通信量、延时、能源消耗和信息数据量[1]。WSNs的能量消耗常常直接决定了整个系统的稳定性与可靠性，而数据压缩对提升无线传感器网络的通信吞吐量非常显著[2]。传感器网络的能量消耗最主要集中于三个部分，分别为信号采样、信号处理与信号传输，其中能量消耗绝大部分在信号传输环节[3]。压缩传输信号可以有效地减少能量消耗，在对WSNs的数据压缩进行设计时应该考虑到两点：(1) 节点处理能力低；(2) 受限的内存资源。因此所设计的压缩算法的能量消耗必须尽可能少[4]。数据压缩的关键在于压缩算法消耗的能量应小于数据传输的能量。

虽然压缩感知CS是近几年才兴起的领域，但是它已经表现出了很强大的生命力与发展潜力。很多学者都在这个领域进行尝试，希望能有所贡献和突破。压缩感知把稀疏信号压缩和采样两个步骤合并进行，为了满足一个特性：在监控区域内传感器节点能耗与计算能力都十分有限的情况下，而远端汇聚终端却拥有持续能量供给与强大的计算能力。王英杰等[5]提出无线传感器网络中分布式数据压缩方法，应用到无线传感器网络数据压缩算法中，取得不错的效果；任学军等[6]提出了一种适合无线传感器网络的混合编码数据压缩算法；王玲等[7]提出基于时间相关性的无线传感器网络数据压缩与优化算法；张建明等[8]提出传感网络中误差有界的分段逼近数据压缩算法，取得不错效果。传统数据压缩方法虽然编码复杂但是解码简单。这意味着用有限资源的传感器节点进行复杂的编码算法，而在资源相对丰富的簇头节点进行简单的解码算法。基于以上分析，本文提出一种新的基于遗传算法的压缩感知重构方法，应用于无线传感器网络数据压缩中。不仅能使压缩编码部分变得更简单，使传输的数据更少，还能使解码算法相对更简易，提高压缩比和采集数据的重构精度，降低了数据冗余度和网络通信量，提高了网络效率。

1 分布式WSNs数据压缩

在监测区域内的成千上百个微型传感器节点组成了无线传感器网络，能够协作地对网络覆盖区域内对象的信息进行感知、采集和处理，最后经处理的信息发送给基站终端。通常情况下，WSNs是全分布式网络，而就其中的每个传感节点而言，一方面它们对信息具有独立的感知、处理和通信能力，但是另一方面它们的通信范围、能量、甚至计算能力等都是有限的。因此无法解决规模较大的复杂性问题。为了将传感节点的处理能力充分地利用起来，节点之间就必须相互合作，突破单个节点的限制，共同完成任务，解决实际问题，从而提高网络性能。

2 压缩感知(CS)理论介绍

传统的数据采样方法：“采样—压缩—传输—解压缩”有可能会失效。然而压缩感知采样由于具有简单采样、复杂解码的特性，因此能有效地解决这一问题。压缩感知与先信号采样再消除信号冗余部分的传统方法不同，它直接将压缩后的信号进行采样，并且同时进行压缩和采样，省去了大量没用的信号采样部分[9]。

压缩感知包括三个方面：信号的稀疏表示、编码测量与重构方法。信号能够进行压缩感知的先决条件是信号可以进行稀疏表示或者可压缩，即在某个变换基下，信号可以使用一种较为简洁的方式进行表达。它的非零系数个数必须远远小于自然信号中非零值的个数[10]。

对于有限长的一维信号x∈Rn(n∈N)， 假设其在某正交基Ψ={ψi}上是P稀疏的(1≤P

(1)

式中，θi为稀疏矩阵投影系数，式(1)可简写为：

x=Ψθ

(2)

式中，θ为n×1维的稀疏矩阵列向量，Ψ称作稀疏变换矩阵。

由压缩感知理论可知，当信号x稀疏或者经过稀疏变换Ψ后稀疏时， 可以用一个不相关的m×n维观测矩阵Ψ(m≤ n，m∈N)对x进行线性变换， 得到观测值y， 即：

ym×1=Φm×nxn×1=Φm×nΨn×nθn×1

(3)

可以看出观测值y的元素个数比x的元素个数要少，这样便实现了对感知信号的压缩采样。另外通过求解l1范数下的最优化问题完成将观测集合y进行重构得到信号x，即：

θ=argmin‖θ‖1s.t. y=ΦΨθ

(4)

3 基于遗传算法CS新重构方法

由压缩感知理论可知，基于遗传算法的CS新型重构方法与基于匹配的传统重构算法相异，区别比较大。它主要从目标函数的优化出发，把稀疏重构结果等同于生物中的染色体。假设在一定规模的种群中，经过复制、选择、交叉互换及变异等遗传过程之后，经迭代无限逼近最优最接近感知节点采样值的重构结果，之后从稀疏重构结果中获得各非零元素的位置信息；再通过最小二乘法得到各非零元素的幅度信息，最终完成重构处理，完成感知数据压缩信息传输过程。因此，本文基于遗传算法的压缩感知新型重构方法能够在稀疏度未知的情况下重构出最终的稀疏结果。

3.1 稀疏重构结果中各非零元素位置信息

1) 种群与编码方案

2) 复制

在父代染色体产生子代的过程中，要求给定遗传代沟GGAP具体数值，GGAP∈(0，1)。假设每代种群中的个体数B乘以1-GGAP个最优个体直接被复制到下一代。而其他子代个体，由选择运算产生。

3) 选择

选择目标函数值定义为：

(5)

最终的迭代优化目标是使目标函数取得最小值，即求得min{f}。

本文采用线性排序估算适应度Ji，首先对目标函数值进行降序排列。将最小适应度染色体个体放置在排序的目标函数值列表的首个位置，最适应个体放置在位置Bi上，Bi为种群个体数量。每个染色体个体根据其在排序种群中的位置W0通过计算可推出适应度值Ji， 即：

(6)

4) 交叉

遗传算法的交叉选用单点交叉，在个体编码串中用交叉概率随机选取一个新的交叉点，对两个配对个体进行部分染色体互换。

5) 变异

遗传算法的变异使用基本位变异，将个体编码串中按遗传过程中变异概率随机选定的某一基因座上的数值进行基本位变异运算，执行过程如下：

(1) 按变异概率在每一个个体上指定某一基因座为变异点；

(2) 对每一个染色变异点的基因值进行取反运算，从而得到新一代的遗传染色个体。

经过一系列的操作过程，再通过MAXGEN迭代(MAXGEN为最大遗传代数)就可以收敛得到最优染色体，即为最优解。一般最优染色体主要由“0”或“1”编码组成，其中“1”为稀疏结果中的非零元素，另外稀疏结果中非零元素的位置信息与它的位置信息相对应。

3.2 稀疏结果中各非零元素幅度信息的确定

知道稀疏结果中各非零元素位置信息后，再在各个位置上利用最小二乘法做投影来确定其幅度信息。假设稀疏结果中有一个非零元素在第j位置上，那么该非零元素的幅度为：

(7)

其中,Tj表示T的第j列，而：

T=ΦΨ

(8)

其中，T称为恢复矩阵。通过非零元素的幅度计算， 就可得到稀疏结果中各非零元素幅度信息。

综合上述内容，基于遗传算法的CS新型重构方法算法流程如图1所示。

图1 基于遗传算法的CS新型重构方法流程

4 CS新型重构方法在WSNs数据压缩中的应用

遗传压缩感知新型重构算法在无线传感器网络数据压缩中的应用如图2所示。

图2 遗传压缩算法在数据压缩中应用

遗传压缩感知算法与WSNs数据传输的具体应用相结合，能够对数据进行压缩后传输，具体过程归纳如下：首先，采集的数据通过传输到达簇头节点，簇头节点对数据进行压缩存储并处理，如图2所示。然后，簇头节点对各个传感器节点获得的数据进行分析，接着把压缩数据结果传送到汇聚终端，最终各个节点的信号在终端联合恢复重构出来。基于遗传算法进行CS的步骤如下：

(1) 远端汇聚终端发布命令。由汇聚终端发布的监测命令通过多跳路由传送到簇头节点，簇头节点以广播的方式将命令转发给每个簇内的传感器节点。

(2) 簇头节点汇聚监测数据。各个传感器节点根据任务命令采集感知的信息，然后将采集得到的数据传输到簇头节点，簇头节点存储信息数据，经过规定时间后开始处理。

5 实验仿真与分析

本文采用Matlab仿真平台对本文提出的遗传压缩感知数据压缩算法进行验证，其中电脑配置为处理器Pentium 2 GHz，内存为2 GB的PC环境下运行。在无线传感器网络数据压缩算法中，用到比较多的有简单的差分编码压缩算法DCCM(differential code compression method)和协作压缩感知CCS(Cooperative Compressed Sensing)算法[11]等。本文将与DCCM算法及CCS算法[12]进行比较分析。遗传算法参数设置：遗传算法种群大小为40，最大遗传代数MAXGEN=300，遗传代沟GGAP=0.95，交叉概率px=0.7，变异概率pm=0.03。实验中无线传感器网络所用的参数如表1所示。

表1 仿真实验参数

无线传感器网络数据压缩算法性能评价指标本文主要从传感器数据序列简单压缩有效性及与其他算法的压缩比、节点平均能耗、生存时间和网络时延等方面进行对比。

5.1 传感器数据序列压缩感知的有效性

为了对本文提出的改进压缩感知算法有效性有一个相对直观的理解，将传感器采集到的一组数据进行实验。其中数据长度N=100，原始数据、压缩感知重构后的数据和本文提出的算法重构后的数据对比图如图3所示。 从图3中可以看出，CCS算法重构率在83.7%，本文算法的重构率94.8%，均方根误差较小。本文提出的算法完成精确的重建，且重构信号质量稳定，保证高精度的还原性。

图3 传感器数据序列压缩重构效果图

5.2 压缩比

压缩比CR(compression ratio)的计算公式为：

CR=SCP/SOR

(9)

其中，SOR为初始数据量，SCP为压缩之后的数据量。另外CR数值越小，那么压缩之后的数据量占原始数据量比重越小，说明压缩性能越优。三种算法压缩比对比如图4所示。

图4 三种算法压缩比对比

从图4可以看出，随着节点数据采集量的增加，三种算法的压缩比都在逐渐下降，下降的幅度不是很大。相比较而言，CCS算法的压缩比低于DCCM算法的压缩比，压缩性能较优，而本文提出的GA-CS压缩算法的压缩比比CCS算法的压缩比还低，压缩性能最好。因为该算法很好地挖掘了无线传感器网络以数据为中心、数据之间的相关性的特点。编码过程中最大程度的去除了节点之间的冗余信息，得到了不错的压缩效果，并且随着节点采集数据量的增加，它的压缩比越来越小，逐步趋于平稳。另外给出遗传算法的收敛性和收敛时间如图5所示。遗传迭代算法在180代左右数据平缓，达到收敛，同时仿真时间消耗4.83 s。

图5 遗传算法迭代收敛曲线

5.3 节点平均能耗

节点能耗是衡量无线传感器网络性能参数的一个重要参数，同样适合数据压缩算法性能评价。数据传输过程中会增加数据压缩时的计算能耗，但在感知节点整个通信过程中的能量消耗而言，数据压缩计算能耗可以忽略不计。仿真中只考虑感知节点的无线通信能耗，设定仿真节点的初始能量、收发功率、数据包发送速率，同时根据数据分组长度计算每次发送数据后节点剩余的能量。计算网络发送与接收时的剩余能量差值就可知道网络运行中的能耗。三种算法的平均能耗如图6所示。

图6 三种算法平均能耗对比

从图6可以看出，节点数据采集量相同时，CCS算法的平均能量消耗比DCCM算法要低，而本文提出的算法比DCCM算法的平均能耗还低。随着感知节点发送数据包数量的增加，三种算法的平均能耗都随之增加，但本文提出的算法能耗增加幅度最小。这主要因为本文提出遗传压缩感知数据压缩算法能更好的挖掘感知节点之间的数据相关性，最大化的降低了冗余节点信息，提高了算法的压缩精度。

5.4 网络生存时间

同样地网络生存时间是无线传感器网络重要的性能指标，直接反应网络寿命的长短。本文分别对这三种算法的网络生存时间进行了仿真，仿真结果如表2所示。

表2 节点死亡时间轮数对比

从整体来看，本文提出的GA-CS算法节点死亡时间轮数都比DCCM算法和CCS算法要长，当网络感知节点10%能量耗尽时，GA-CS算法节点死亡速度为DCCM算法的77%和CCS算法的88%；在网络感知节点50%能量耗尽时，GA-CS算法节点死亡速度为DCCM算法的88.3%和CCS算法的93.7%；在网络感知节点75%能量耗尽时，GA-CS算法节点死亡速度为DCCM算法的77.9%和CCS算法的84.4%；在100%的节点能耗耗尽时，GA-CS算法节点的网络轮询时间分别多出3004和1478轮。可以看出，本文提出基于GA-CS算法无线传感器网络中的网络寿命明显比另两种算法的寿命要长。这主要是因为在数据压缩之后，减小了网络内部的数据冗余，减少了数据传输过程中的能耗，延长了网络寿命。因此，本文提出的算法适用于能量有限、计算有限及成本有限的无线传感器网络。

5.5 网络时延

网络时延TY包括两部分时间组成，从感知节点发送数据到接收节点收到数据包的传输延时TS和接收到数据包的节点进行数据压缩算法产生的计算耗时TC，计算公式为：

TY=TS+TC

(10)

三种算法的网络时延如图7所示。

图7 三种算法网络时延对比

从图7可以看出，三种算法的网络时延都随着节点数据采集的增加而延长。当节点的采集量较小时，DCCM算法的网络时延比CCS算法要短，短0.05 s，而比GA-CS算法的网络时延短了0.1 s，这主要是由于对数据进行压缩而消耗的计算延时。但随着节点数据采集量的增加，发送的数据包较大时，DCCM算法的网络时延明显比CCS算法要长，比GA-CS算法的网络时延更长。这里主要的时间消耗不是数据压缩计算延时，主要是数据采集量增大后的时间传输时间延时。可以看出本文提出的基于GA-CS算法的数据压缩算法，有效地降低了网络中所需要传输的数据量，从而达到减少网络延时的目的。

6 结 语

无线传感器网络由于能量、通信带宽、计算能力及成本有限，不适合大规模数据传输，同时存在数据冗余，需要进行数据压缩处理。本文提出一种新的基于遗传算法的压缩感知重构方法，应用于无线传感器网络数据压缩过程中。对GA-CS算法进行的性能分析， 从压缩比、节点平均能耗、网络生存时间和网络时延四个方面，与DCCM算法及CCS算法的WSNs数据压缩算法进行比较。实验验证表明，本文提出的算法具有较高的压缩比，提高了采集数据的重构精度，降低了数据冗余度和网络通信量，提高了网络效率。

[1] Erratt N,Liang Y.Compressed data-stream protocol:an energy-efficient compressed data-stream protocol for wireless sensor networks[J].Let Communications,2011,5(18):2673-2683.

[2] Liu Xiang,Jun Luo,Rosenberg C.Compressed Data Aggregation:Energy-Efficient and High-Fidelity Data Collection[J].Networking,IEEE/ACM Transactions on,2013,21(6):1722-1735.

[3] Shancang Li,Li Da Xu,Xinheng Wang.Compressed Sensing Signal and Data Acquisition in Wireless Sensor Networks and Internet of Things[J].Industrial Informatics,IEEE Transactions on,2013,9(4):2177-2186.

[4] 曾凡文,王永利,刘冬梅.可调重构误差的传感数据时间相关压缩算法[J].计算机应用与软件,2011,28(11):279-282.

[5] 王英杰,鞠时光,阴晓加.无线传感器网络中分布式数据压缩方法[J].计算机工程,2010,36(18):88-90.

[6] 任学军,房鼎益.一种适合无线传感器网络的混合编码数据压缩算法[J].小型微型计算机系统,2011,32(6):1055-1058.

[7] 王玲,石为人,石欣.基于时间相关性的无线传感器网络数据压缩与优化算法[J].计算机应用,2013,33(12):3453-3456.

[8] 张建明,林亚平,傅明.传感网络中误差有界的分段逼近数据压缩算法[J].软件学报,2011,22(9):2149-2165.

[9] 尹亚光,丁贵广.无线传感器网络中的数据压缩技术研究[J].计算机应用与软件,2010,27(7):1-4.

[10] 范祥辉,李士宁,杜鹏雷.WSN中一种自适应无损数据压缩机制[J].计算机测量与控制,2010,18(2):463-465.

[11] 蒋鹏,吴建峰,吴斌.基于自适应最优消零的无线传感器网络数据压缩算法研究[J].通信学报,2013,34(2):1-7.

[12] 吴大鹏,孙青文,唐季超.能量有效的无线传感器网络协作压缩感知机制[J].电子与信息学报,2012,34(11):2687-2693.

WIRELESS SENSOR NETWORK DATA COMPRESSION METHOD BASED ON GENETIC COMPRESSED SENSING

Zhang Na

(InstituteofComputerScienceandEngineering,HenanUniversityandUrbanConstruction,Pingdingshan467036,Henan,China)

In view of that the wireless sensor networks (WSNs) are limited in energy, communication bandwidth, computing capability and cost, they are not suitable for large-scale data transmission, and that there is the presence of data redundancy meanwhile and has the need of data compression, we put forward a new genetic algorithm-based compressed sensing (CS) reconstruction method, and applied it to wireless sensor network data compression. In this paper we expatiate on the features of distributed WSNs data compression, the basic theory of compressed sensing, as well as the genetic algorithm-based new CS reconstruction method and its application in WSNs data compression. It was proved through experimental simulation that compared with WSNs data compression algorithms using DCCM algorithm and CCS algorithm in four aspects of compression ratio, average nodes energy consumption, network lifecycle and network delay, the proposed algorithm had higher compression ratio, improved the reconstruction accuracy of the collected data, reduced the data redundancy and network traffic, and improved the network efficiency.

Wireless sensor networks Compressive sensing Genetic algorithm Compression ratio Lifecycle

2014-10-08。国家自然科学基金项目(61202248)；河南省科技发展计划科技攻关重点项目(122102210412)。张娜，博士，主研领域：模式识别与智能系统。

TP393

A

10.3969/j.issn.1000-386x.2016.04.031