基于字典学习和压缩感知的WSN数据压缩

杨欣宇，李爱萍，段利国，赵菊敏

(太原理工大学 信息与计算机学院，山西 晋中 030600)

0 引 言

作为物联网(internet of things，IoT)[1]的重要组成部分，无线传感网 (wireless sensor networks，WSN)[2]已被普遍应用于环境监测、军事防御、智慧农业等各个领域，应用普及产生的数据量与日俱增，由此造成的存储、传输、处理等需求也越来越大，WSN数据压缩的研究多年来一直是IoT应用推广最为关键的技术之一。

近年来，已有多种方法进行WSN数据的压缩[3]研究，但压缩效果仍有进一步提升的空间。LUO等[4]提出将压缩感知(compressed sensing，CS)[5]理论应用于大规模WSN数据收集，该方法能大幅、有效提高数据压缩比，但针对不同应用场景中监测数据的特征差异，采用固定的稀疏基运算时会出现稀疏表示结果不精确、数据重构精度低的问题。此外，感知节点处理能力有限，经典的基于CS的WSN数据压缩方法直接在感知节点上进行稀疏变换、矩阵测量等大量运算，不仅缩短网络寿命而且延缓了传输时间。

基于上述问题，提出一种基于字典学习和CS的WSN数据压缩模型。模型改进K-SVD初始字典，利用历史数据集训练适应数据特征的K-SVD稀疏基，从而保证在减少数据传输量的同时提高数据恢复精度；优化基于CS的WSN数据收集模型，把复杂的稀疏变换由感知节点转移到基站，延长网络寿命。在Berkeley实验室的温度数据集[6]上做对比实验，其结果表明，针对时空相关性较强的监测数据的压缩和恢复效果，本文方法比已有的OEGMP、基于DCT稀疏基的CS压缩等方法有明显提升。

1 相关工作

1.1 WSN组成及特点

WSN由部署在监测区域内的众多感知节点和功能强大的融合中心(基站或汇聚节点)构成，感知节点之间以多跳自组的方式，把监测数据传送到融合中心[2]。WSN感知节点的计算、存储能力、通讯带宽及电源能量都很有限，需要尽可能节省能耗。因此，有必要对WSN中感知层收集的大量数据在传输之前进行压缩，然后在应用层进行解压后再使用。

一般的WSN数据具有数据量大、实时性强、时空相关性等性质，且不同场景下的WSN，产生的监测数据特征也各不相同。

1.2 压缩感知理论

压缩感知理论于2006年由Donoho等[5]正式提出以来，已被广泛应用于无线通信、图像处理、数据采集等领域，其主要内容包括3部分：信号的稀疏变换、矩阵测量和信号重构，如图1所示。

图1 CS理论组成部分

设N×1维信号X是稀疏的，或者在某个变换域上可进行稀疏分解得到式(1)

X=Ψθ

(1)

θ是稀疏度为K(K≪N) 的N×1维列向量，即θ中只有K个非零项。然后将该稀疏系数投影到另一个与变换基Ψ不相关的、维数为M×N(M≪N) 的观测矩阵Φ上，得到M×1维观测集合y， 如式(2)所示，其中ACS称为传感矩阵

y=Φθ=ΦΨTX=ACSX

(2)

Candès、Tao等给出式(2)存在确定解的充分必要条件是：Φ与Ψ互不相关[7]，那么可以凭借这些观测值求解式(3)而得到信号X的精确恢复

(3)

信号的稀疏性或可压缩性，是CS应用的基础和前提，也是数据重构的关键，所以寻找一个能够把信号有效稀疏表示的稀疏基，成为研究CS的重要内容之一。

1.3 现有的WSN数据压缩方法

随着WSN应用规模不断扩大，数据量不断倍增，已有许多工作人员对提高数据压缩效率，减少数据传输量展开了深入研究[3,8]。

WSN监测数据大多在时间和空间上具有相关性。消除时间冗余较经典的算法，有预测编码类[9]、线性回归算法[10]等。通常通过路由结构来处理具有空间相关性的数据，LEACH(low energy adaptive clustering hierarchy)算法[11]在目前WSN数据压缩领域得到了良好的应用。乔建华等[8]全面阐述了基于CS的WSN压缩数据收集算法，表明CS理论在WSN中的适用性，总结出压缩比较小、稀疏基不适、数据恢复不精确等问题。Xie等[12]将差分矩阵用作稀疏基，结合改进的LEACH算法对WSN数据作压缩研究，实验结果表明该方法有效减少了数据传输量，但压缩步骤较复杂。因此，使用路由算法是提高数据压缩率的有效方法之一，同时，将稀疏变换转移到基站可有效降低压缩复杂度并减少节点能耗。

数据能否精确重构不仅取决于重构算法，还依赖于数据能否稀疏表示。K-SVD字典学习算法[13]与压缩感知理论的结合已在多个领域进行了大量研究，朱路等[14]将其用于图像降噪，弓震等[15]使用该技术对地震资料去噪。在压缩感知框架下，K-SVD字典对各类数据都展现出了较好的稀疏表示效果。综上，本文训练K-SVD字典对WSN数据进行稀疏表示，结合压缩感知进行WSN数据压缩研究。

2 K-SVD字典学习

信号的稀疏性是运用CS的前提，虽然在物理环境采集的大多信号并不稀疏，但在某个变换域上可进行稀疏分解的信号就是可压缩的。K-SVD学习算法能够适应数据本身特征，对数据稀疏表示。

K-SVD字典学习的主要思想[13]：根据原始样本数据Y训练完备字典矩阵D∈Rn×n，D包含n个原子di∈{d1,d2,…,dn}，S为样本Y在字典D上的稀疏表示，如式(4)所示

Y=DS

(4)

(5)

式中：包含两个自变量：字典D和稀疏系数S， 要求得使目标函数取最小值时自变量的值，一般是固定其中一个变量，求解另一个变量，如此迭代进行。字典D通过SVD分解或者最小二乘法逐列更新，可以利用已有的经典方法求解稀疏系数S， 如正交匹配追踪[16](orthogonal matching pursuit，OMP)、基追踪等算法。本文拟采用OMP算法求解S。

3 基于K-SVD字典和压缩感知的WSN数据压缩

本文提出一种基于K-SVD字典和压缩感知的WSN数据压缩模型，如图2所示，模型主要分为3个部分：①在基站，使用改进的K-SVD字典学习算法训练历史数据集，得到适合该数据类型的稀疏变换基Ψ；②在感知层，各个簇内的感知节点收集一段时间内的监测数据xi传输到簇头，簇头只需保存观测矩阵Φ进行CS压缩；③压缩数据yj经过多跳传输在基站完成重构。

图2 基于K-SVD字典和CS的WSN数据压缩模型

本文模型改进字典学习算法，将离散余弦变换[17](discrete cosine transform，DCT)设定为K-SVD字典学习算法的初始字典，能够消除数据相关性，加快算法收敛速度，训练效果更佳；利用LEACH算法[11]将感知节点分簇，对一段时间内采集的数据，传输到簇头进行CS压缩，可以同时消除数据间的时空冗余，提高压缩率；改变经典的压缩感知框架，假设WSN数据在某个变换基上是稀疏可压缩的，在各个簇头只进行压缩感知矩阵测量，将复杂的稀疏变换由感知层转移到基站。该模型符合WSN中，感知节点硬件资源和能耗有限、基站计算能力较强的特点，有效减轻感知节点负担，减少压缩步骤。

3.1 改进的K-SVD字典训练

由于WSN数据时空相关性较强，在某个变换基上可以稀疏表示，具有CS理论的可压缩性前提，所以需要对WSN数据进行稀疏变换。传统的稀疏基结构固定，如DCT、DWT等，不能对各种信号都进行准确的稀疏表示，影响数据重构效果，使用K-SVD字典学习算法可以有效解决这个问题。不需要事先固定稀疏基的形式，而是通过不断迭代和更新，根据已有信号的特征训练出合适的稀疏变换字典，提高数据重构精度。本文的K-SVD算法在基站利用历史数据训练稀疏基，不仅为感知节点减轻负担，而且为稀疏变换提供了更可靠和强大的计算能力。

传统的K-SVD字典学习算法，随机抽取样本的数据设置为初始字典进行字典训练，由于WSN监测数据通常具有较大的时空冗余，数值间的变化幅度较小，数值过于相似，初始字典中存在一定的线性相关性，因此会影响稀疏系数的求解效果，造成字典迭代更新时停滞不变的状况。离散余弦变换基[17]结构固定，拥有较强的“能量集中”性质，将时域转换为频域，信号的能量通常汇集在频域较低的部分，因此能够有效去除数据间的相关性。为解决字典训练效果不佳的问题，本文将DCT设置为初始字典，如式(6)

(6)

式中：u表示DCT矩阵维度，x(n) 是原始数据值。对于高度相关的WSN数据，DCT具有非常好的能量紧凑性，作为初始字典可以有效消除数据间的相关性，提高稀疏字典收敛速度和稀疏表示效果。

(7)

(8)

(9)

对E′k采用奇异值(SVD)分解，分解完成后的左矩阵的第一列赋值给dk， 将新的dk更新到字典D的第k列，即完成了字典的第k列原子的更新。上述过程与稀疏编码循环执行，直到字典中的各列原子全部更新完毕，本文的字典训练过程如算法1所示。学习字典训练时，因为在算法中嵌套两层循环以更新字典，其中第一层是更新稀疏编码，第二层在当前编码下更新字典，要更新字典的n列原子，那么在更新过程中，学习字典的更新需要进行n次，因此该算法时间复杂度为O(n2)， 空间复杂度为O(n)。

算法1：改进的K-SVD字典学习算法

Input：原始样本、初始字典、稀疏系数

Output：稀疏字典

Begin

(1)初始化：初始字典←DCT稀疏基，j=1；

(2)稀疏编码：根据上一步得到的字典，求解稀疏编码；

(3)字典更新：逐列更新字典

3)Ek只选择索引ωk对应的列得到E′k

5)j=j+1.

(4)判断样本稀疏表示后误差是否达到指定阈值， 若达到输出字典， 否则继续执行步骤(2)、 步骤(3)。

End

3.2 感知端数据压缩

通常，WSN感知节点部署密集，收集监测数据时间间隔较短，数据在时间和空间上存在较高的冗余度，为了处理数据的时空相关性，本文采用LEACH[11]路由算法将感知节点分簇。该算法是以循环的方式随机选择簇头节点，簇头向周边节点广播信息后自组分簇。每个簇内，感知节点将各自采集的一段时间内的数据传输到簇头，在簇头接收并整合原始数据后，使用CS理论实现WSN数据的压缩，压缩数据通过多跳的方式传送到基站。

鉴于WSN中感知节点计算能力和处理能力有限，本文模型对传统的CS数据压缩算法作出改进，假设WSN监测数据都具有可压缩性，采集到的数据集可以直接进行矩阵观测，不再需要在感知层完成稀疏变换，该方法可以有效缩短传输时延，降低数据压缩复杂度，减轻感知节点负担。WSN数据压缩分为4个步骤：①感知节点间根据自身所剩能量角逐簇头节点，划分簇群；②簇内节点传输一段时间内的监测数据到簇头节点；③在簇头节点完成CS矩阵测量，实现数据压缩；④压缩信息以多跳的方式传输到基站。

具体压缩过程如下：第i个节点在一段时间内采集的数据序列的表示如式(10)所示，则簇内n个节点在这段时间内采集的数据可表示成一个m×n维矩阵X， 如式(11)所示

xi=[xi1,xi2,…,xim]T

(10)

(11)

其中，矩阵的列向量代表簇内每个节点的时间序列数据，行向量代表各个节点在相同时间感知的数据，这样收集来的数据具备了较强的时空相关性，完成数据压缩可以同时消除时间和空间冗余，提高数据压缩率。为了方便CS矩阵测量，我们将矩阵X的元素按列的顺序展开表示，得到N×1(N=m*n) 维列向量，如式(12)所示

vec(X)=[x11,x12,…,x1m,x21,x22,…,xnm]T

(12)

如图2所示，在每个簇头节点，观测矩阵Φ与簇头数据vec(X) 相乘，即可完成WSN数据的压缩步骤，得到压缩数据y， 如式(13)所示

y=Φ·vec(X)

(13)

压缩数据经过多跳传输，到达基站。为了保证数据可以精确重构，本文使用与大部分正交基高度不相关的高斯矩阵[5]作为观测矩阵。此处观测矩阵设定为M×N(M≪N) 维，则压缩数据是M×1维，压缩后的数据传输量远远小于原始数据量。通过上述分析可得，WSN数据的压缩率取决于观测矩阵的维度，当数据总量N固定时，观测矩阵行数M越小，则数据压缩比越小，压缩效率越高。

3.3 基站数据重构

数据重构是在基站对压缩数据的解压缩过程。根据上述分析，基站已知观测矩阵Φ、适用于该环境数据的稀疏基Ψ(即字典D)和来自感知层的压缩数据y。由于原始数据X在稀疏基上是可稀疏变换的，可以表示成稀疏基Ψ和稀疏系数θ相乘的形式，如式(1)所示，结合式(13)，原始数据X的求解可以转换为式(14)

(14)

由于M≪N， 方程的个数远小于未知数的个数，没有确定性解，式(14)的l0范数问题属于NP难问题，难以求解。通常，学者们会把l0范数问题看作是l1范数问题或l2范数问题来解决。Candès给出式(14)存在确定解的充分必要条件[7]是：Φ与Ψ互不相关，即满足有限等距性质(restricted isometry property，RIP)，那么可以凭借这些压缩数据求解式(14)而得到信号X的精确恢复。本文选用经典的OMP[16]算法对压缩数据实现重构，加入阈值比较机制来控制算法进程，当数据恢复到理想效果，重构误差小于设定阈值时，不管迭代次数是否达到初始设定总次数，迭代都可以提前结束，不用再进行后续求解。具体的重构过程如算法2所示。

算法2：OMP重构算法

OMP重构算法

Input：r0，t，Λ0，U0，A，k，ε

Begin

(1)r0←y，t←1，Λ0←∅，U0←∅；

(2)A的每列aj与rt-1相乘， 找到乘积最大时对应元素的下标， 即λt=argmax||，j=1,2,…,λ,…,n；

(3)令索引Λt=Λt-1∪λt， 索引矩阵Ut=Ut-1∪aλ；

(6)t=t+1， 比较rt与ε，rt<ε则执行步骤(8)， 否则步骤(7)；

(7)t>k继续执行步骤(8)， 否则返回步骤(2)；

End

其中r0表示初始残差，t表示迭代次数，Λ0表示索引集合，U0表示按Λ0选出的矩阵，A=ΦΨ，k为算法需要迭代次数。ε代表重构误差阈值，和迭代次数k同时控制着重构算法的进度。稀疏基Ψ是经过对历史样本的字典学习训练而得，所求的稀疏系数θ更为精确。这里，θ是k稀疏的，即在该向量中只有k个项是非零的，且重构迭代次数为k。 数据解压缩过程中，重构迭代的次数越多，恢复的数据越精确，同时消耗的时间越多。但在实际应用中，需要根据场景的恢复精度需求选择合适的迭代次数，加入阈值机制可节省重构时间，数据恢复达到指定效果即可停止重构。重构算法中传感矩阵A的每列aj与rt-1相乘，A有n列，且需要找到乘积最大时对应元素的下标，因此OMP算法的时间复杂度为O(n2)。

4 实验及结果分析

4.1 数据集及实验环境

本文使用数据集[6]进行实验，该数据集包含在Intel Berkeley实验室中部署的传感器收集的温度、湿度、光强等数据信息。所涉及的算法通过Python编程语言实现，实验环境为Intel Core i7-8550U CPU@1.8 GHz，运行内存8 GB，64位Windows10操作系统，PyCharm开发平台。

4.2 性能评价指标

本文选择3个评价指标来检测本文模型的有效性。压缩率(compression ration，CR)是指簇头节点进行压缩过后传输给汇聚节点的数据量与压缩之前的原始数据量之比；均方根误差(root mean square error，RMSE)用来权衡重构值与实际值之间的偏差，RMSE越小，则偏差值越小，恢复数据越精确；相对重构误差(relative reconstruction error，RRE)反映数据恢复的可信程度。分别如式(15)～式(17)所示

(15)

(16)

(17)

4.3 实验结果分析

4.3.1 K-SVD字典训练

实验处理数据集，取8个相邻节点(编号14～21)，每个节点每隔一分钟产生的温度数据作为样本训练集，选取DCT作为初始字典，设定迭代次数和误差阈值，实验参数配置见表1。

表1 实验参数配置

样本训练集如下，可以看出，监测数据间的时空相关性较强，相邻数值相似，作为K-SVD字典学习算法的初始字典线性相关较高，影响字典训练效果，选取DCT作为初始字典可消除数据相关，提高字典的稀疏表示能力

利用算法2训练K-SVD字典，得出适应该数据集特征的稀疏变换字典。生成1024×1024维字典如下

4.3.2 簇的大小对数据重构效果的影响

为了确定使用本文模型对WSN数据压缩时最优簇的大小，需要分析不同簇的大小对数据重构结果的影响。簇内数据量分别取32、64、128、256、512和1024，比较在不同压缩率下的均方根误差值。当簇内数据量为32，压缩率为0.9时，均方根误差为0.74，恢复数据与真实数据偏差较大，实验结果表明，由于采集数据量较少，该模型不适用于簇内数据量小于32的情况。其它取值的实验结果如图3所示。

图3 不同簇的大小对数据重构结果的影响

分析图3结果，伴随数据量的增长，RMSE逐渐趋于平稳状态。当簇内数据量较大时，如簇的大小为512和1024，计算量也随之增长，影响数据的恢复精度。因此当簇内数据量为128和256时，使用该模型压缩效果更优。

4.3.3 重构迭代次数对数据重构效果的影响

由图3可知，当簇内原始数据量为512时，重构数据与原始数据之间的均方根误差约为0.14，此时本文模型的重构收敛速度如图4所示。选取不同压缩率，并在该压缩条件下设置重构算法的不同迭代次数，记录在不同压缩率下采取不同迭代次数时，重构数据的RMSE。图4固定重构数据的RMSE为0.14，代表数据已经有一个良好的恢复效果，统计在不同压缩率下，达到RMSE为0.14时，OMP算法所需进行的迭代次数。由于改进的K-SVD字典的自适应特性和良好的稀疏表示能力，当数据压缩率为0.2时，使用OMP算法重构数据所需的迭代次数仅为5次，重构数据的RMSE即可达到0.14，表明本文模型能较快收敛于最优解。

图4 重构迭代次数和数据压缩率的关系

4.3.4 对比其它WSN数据压缩算法

为了比较本文模型与其它WSN数据压缩算法的性能，将本文提出的压缩模型分别与OEGMP[9]算法、固定稀疏基DCT算法、随机选取K-SVD初始字典的CS数据压缩算法进行对比实验。实验模拟了簇内收集数据量为256时，不同压缩率下数据的恢复情况。如图5所示，其中加入均方根误差值(RMSE)为0.1的水平基线，OEGMP算法同样采用数学的方法只需传输少量信息到基站，使用预测类算法解压数据，但是只有在压缩率高于0.5时，OEGMP算法的数据恢复精度较高，压缩率低于0.5时，该算法的数据重构误差远大于本文算法；基于DCT稀疏基的CS压缩算法，由于DCT正交基结构固定，没有自适应能力，不适应本文实验的WSN数据特征，压缩重构效果较差；选取原始样本作初始字典，未做改进的K-SVD字典学习算法直接训练出的稀疏变换字典用于本实验，样本数据的相关性使得训练字典稀疏表示不够精确，重构效果不佳；本文模型改进K-SVD算法，初始字典选择DCT稀疏基，消除数据相关性，训练出的字典稀疏表示效果更优，可以看出在压缩率为0.2时，RMSE即低于0.1，重构效果优于K-SVD初始字典随机选取的算法，改进后的K-SVD字典对算法性能有一定的提升。

图5 本文压缩模型和其它压缩算法的对比

4.3.5 本文模型压缩数据恢复效果

取8个感知节点分一个簇，每个点向簇首传输32个数据，使用本文提出的基于字典学习和压缩感知的WSN数据压缩模型对簇首数据进行压缩并恢复。分别计算在不同压缩率下，重构数据与原始数据的相对误差，如表2(有效数字取小数点后三位)所示，随着压缩率的增大，数据相对重构误差越小。在压缩率为0.2，OMP算法重构迭代次数为5时，数据重构仅耗时0.0687 s，重构数据与原始数据对比效果如图6所示。

表2 恢复数据相对重构误差

图6 温度恢复数据与原始数据对比

由图6可知，本文模型在选取压缩率为0.2时，能够有效恢复原始数据，重构数据与原始数据的RMSE为0.098，可以满足大部分实际应用需求。

5 结束语

本文针对WSN监测环境的数据收集问题，提出一种基于改进K-SVD字典和CS的WSN数据压缩模型。该模型利用字典学习的自适应性，改进K-SVD字典学习算法，根据监测数据本身的特点训练出适合该类数据的稀疏基，同时为了减轻感知节点负担，将CS中的稀疏变换转移在基站进行，为基于CS的WSN数据压缩提供了一种新思路。

结合理论分析和实验验证，本文模型在WSN数据压缩收集中使用不仅提高了压缩效率、减少网络传输能耗，而且能以较高精度恢复原始数据。但文中使用的高斯观测矩阵所需存储空间较大、计算复杂度较高，在本阶段工作中没有考虑到，今后我们将研究更适合WSN使用的内存小、结构简单的观测矩阵。