WSN中基于压缩感知的分簇数据收集算法

张 蕾,崔娟娟,李晶晶

(扬州大学广陵学院机械电子工程系,江苏 扬州 225000)

0 引 言

随着信息技术的发展，无线传感器网络(Wireless Sensor Network, WSN)已经普遍应用于军事、农业、医疗卫生、家居服务、环境监测等诸多领域[1]。WSN是由若干成本较低、计算和通信能力以及自身能量有限的传感器节点根据特定的网络拓扑结构组成。网络中节点的能耗问题是设计无线传感器网络的关键问题[2]。

WSN分簇算法的提出有效地降低了网络的能量消耗,均衡了网络的能量负载。Heinzelman[3]于2000年提出了LEACH算法，LEACH算法是经典的分簇路由算法，它通过等概率地随机选举簇头节点，来均衡网络的能量负载。然而，LEACH算法中簇头节点的选择没有考虑节点能量和距离等因素[4]，簇结构和簇头节点的分布很不均匀，那些剩余能量少或者远离基站Sink的节点仍会被选为簇头节点，这将导致大量的节点在数据传输的过程中过早地死亡，从而缩短了网络的运行周期。

针对LEACH算法的缺陷，国内外专家对其进行了研究和改进。LEACH-C[3]、HEED[6]、DEEC[7]等经典的分簇路由算法相继被提出。这些算法考虑了节点的剩余能量和距离信息，解决了LEACH算法随机选举簇头节点的问题[8-9]。然而，这些算法分成的簇结构分布不均匀，网络中能量的消耗也不均匀。聚类算法能够根据数据之间的相似性对大量的数据进行分类，与WSN中的分簇算法思想类似。因此，国内外很多学者将聚类算法应用到WSN的分簇过程中[10]。其中，应用最广泛的聚类分析算法是K-means聚类算法。文献[11-14]均在网络分簇阶段采用了K-means聚类算法，基于节点的剩余能量和距离信息竞选簇头节点，既保证了簇结构和簇头节点分布的均匀性，又均衡了网络的能量消耗，延长了网络的运行周期。

为了降低WSN的数据传输量，很多学者将压缩感知算法(Compressed Sensing, CS)应用于WSN的数据收集[15-16]。对于稀疏信号或者在变换基空间上可压缩的信号，CS理论可以通过远低于奈奎斯特频率的方式对信号进行采样,并且能够精准地恢复出原始信号。CS技术在采集数据的同时实现了数据的压缩，降低了数据的冗余度，大大减少了数据通信量，延长了网络的生命周期[17]。

本文基于上述研究，综合考虑了网络中节点数据的时空相关性，提出一种将K-means均衡分簇与CS理论相结合的无线传感器网络数据收集算法。该算法首先采用K-means算法对WSN进行均衡分簇，根据簇内节点的剩余能量和位置信息选取簇头节点。各簇头节点使用CS理论对采样的数据进行数据融合，并通过多跳路由的方式传送给基站Sink节点。Sink节点使用OMP算法对收集的数据进行精准重构。经仿真实验表明，该算法有效地减少了网络的数据通信量，降低了压缩感知过程中所需要的观测量，均衡了WSN的能量消耗并延长了网络寿命。

1 基于K-means均衡分簇算法

本文提出的基于K-means均衡分簇算法是以轮循环方式进行的，只在第一轮采用K-means聚类算法划分网络成簇，此后的每一轮网络的簇结构都是固定的[11]。第一轮分为簇形成阶段、簇头竞选阶段和数据传输阶段，其他每一轮分为簇头竞选阶段和数据传输阶段[12]。簇头的选举需要综合考虑节点自身的能量、节点到簇内其他各节点的距离、节点与基站的距离。本文采用参量值r来衡量每个传感器节点，每一轮簇内r值最大的节点当选簇头节点。参量值r的计算公式如下：

(1)

其中，Ei为节点i的能量，dsi为节点i到基站Sink节点的距离，dki为节点i与簇内其他各节点的距离，cn为簇内节点数。α为网络系数，取值范围为(0,1)。α值根据经验选择，值越小则簇首更新频率越慢。

无线传感器网络分簇数的确定通常需要考虑网络的能量损耗模型。本文的能量损耗模型是基于文献[18]和文献[19]实现的。该能量损耗模型由发送电路的能耗、信号放大器的能耗和接收电路的能耗构成。设发送L比特数据，发送过程中消耗的能量如式(2)：

(2)

接收L比特数据的过程中消耗的能量如式(3)：

ERx=Eelec×L

(3)

其中，Eelec是发送或接收单位比特数据的能耗，Efs是自由空间衰落模型的能量系数，Emp是多路径衰落模型的能量系数，D为传输的距离。Dc是一个常量，表示距离的临界值。当传输距离D小于Dc时采用自由空间衰落模型，否则采用多路径衰落模型。

根据文献[12]和文献[20]可得到无线传感器网络分簇数k的最优值为：

(4)

其中，n表示网络节点数目，M表示正方形网络区域的边长，dmean表示节点到基站的平均距离。

2 WSN中压缩感知算法概述

2.1 压缩感知算法

压缩感知理论指出：如果信号是稀疏的或者在变换基空间上稀疏，压缩感知技术可以通过远低于奈奎斯特频率的方式对信号进行采样,并且能够精确地重构出原始信号[21]。假设原始信号为X=[x1,x2,…,xN]T∈RN，在N×N维变换基矩阵Ψ下是稀疏的，则原始信号X可以表示为：

X=Ψθ

(5)

其中，列向量θ只有少量的非零元素。稀疏矩阵Ψ一般为固定的正交基矩阵，比如傅里叶变换矩阵、离散余弦变换矩阵和离散小波变换矩阵等[22]。

Y=ΦX=ΦΨθ=Θθ

(6)

其中,Θ称为传感矩阵，Θ=ΦΨ。目前常用的测量矩阵Φ有随机高斯矩阵、伯努利随机测量矩阵、托普利兹矩阵、正交测量矩阵等。

由于信号X在变换基上是稀疏的，而且传感矩阵Θ满足RIP性质。基于以上2个原则，重构原始信号成为可能。信号重构算法主要分为凸优化算法和贪婪迭代算法2类[23]。

2.2 基于时空相关性的压缩感知算法

无线传感器网络在监测区域内部署了大量的传感器节点并连续采样。因此，同一传感器节点在相邻时刻所采集的数据存在时间冗余，同一节点与相邻节点在相同时刻所采集的数据之间存在空间冗余。由于无线传感器网络中节点的数据在时间和空间上存在一定的相关性，为了降低数据之间的冗余度，更好地压缩数据，本文对压缩感知算法中的稀疏基进行了改进[24-25]，具体如下:

假定无线传感器网络中某个簇内布置了N个传感器，在某段时间内每个节点采集K个数据。第i个节点采集到的数据可以表示为：

Di=[di1,di2,…,diK]T

(7)

那么，这段时间内簇首节点收集到的数据可以表示为：

本底资料为2013年国家下发的1∶250 000 DLG数据，更新资料为2017年更新完成的云南省1∶50 000 DLG数据库[1]。

(8)

在第j时刻，簇首节点收集到的数据可以表示为：

Xj=[d1j,d2j,…,dNj]

(9)

(10)

其中，D∈RK×N,C∈RN×N。

用特征值分解方法求矩阵C的特征向量P，将特征向量P作为稀疏基Ψ。这段时间内任意时刻簇头节点收集到的原始数据都采用同一稀疏基。由文献[25]和文献[26]可知，协方差矩阵可以衡量矩阵维度之间的关系。所以，矩阵C可以度量网络中不同节点数据之间的相关性。将协方差矩阵C对应的特征向量作为稀疏基，去除节点数据之间的相关性，降低数据的冗余度。

本文采用随机高斯矩阵作为测量矩阵Φ，观测向量Y=ΦX。压缩感知算法的压缩率定义为ρ=N/M，N为原始数据X的维数，M为观测向量Y的维数。

WSN中各个簇头节点采用基于时空相关性的压缩感知技术对收集到的数据进行压缩并传至基站Sink节点，由基站对收集到的数据进行精确重构[27]。本文选择OMP算法作为信号重构算法，详细描述如算法1所示。

算法1OMP算法

输入：传感矩阵Θ，观测向量Y，迭代次数K

输出：信号稀疏表示系数θ

Step1初始化设残差R0=Y，迭代次数t=1，索引集合Λ为空集。

Step2计算残差与传感矩阵Θ的列Θj的内积，找出最大内积值对应的索引λt，即：

Step3更新索引集Λ和原子集Θt，令Λt=Λt-1∪{λt}，将与残差内积最大的值所对应的传感矩阵Θ的列Θj并入原子集Θt，令Θt=[Θt,Θj]。

Step4计算Y=Θtθt的最小二乘解：

3 仿真实验和结果分析

本章对本文提出的算法进行仿真实验，并与其他几种算法进行比较。本文采用网络的数据通信量和信号重构时的效果作为评估标准。

3.1 网络通信量比较

3.1.1 仿真参数

本节通过仿真实验对不同数据收集算法进行比较，采用无线传感器网络的数据通信量作为评估算法的标准。在用于对比的数据收集算法中，LEACH with CS算法采用LEACH算法对网络分簇，在簇首节点采用本文提出的基于时空相关性的压缩感知算法融合数据；HEED with CS算法采用HEED算法对网络分簇，在簇首节点采用本文提出的基于时空相关性的压缩感知算法融合数据；Clustering without CS算法采用了与本文相同的分簇结构，但在簇首节点没有使用CS算法；LEACH without CS算法采用了LEACH算法对网络分簇，但没有使用CS算法。

假设传感器网络的分布区域为一个100×100的正方形区域。基站Sink节点的坐标为(0,0)。传感器节点个数从400～1600，以200为每步的增量。每个节点传输的数据包数为5。压缩率分别设置为5、10、15。为了保证实验的准确性，采用30次随机拓扑仿真结果的平均值作为实验结果[28]。

3.1.2 实验结果分析

在不同的压缩率下，随着传感器节点个数的增加，将本文算法与其他4种数据收集算法在网络通信量方面的变换进行了比较。图1(a)是压缩率为5时，各算法对应的网络通信量。图1(b)是压缩率为10时，各算法对应的网络通信量。图1(c)是压缩率为15时，各算法对应的网络通信量。

(a) 压缩率为5

(b) 压缩率为10

(c) 压缩率为15

由图1可知，随着无线传感器网络中节点数的增加，对应的网络通信量也在增加。由于LEACH without CS算法和Clustering without CS算法在簇头节点没有使用CS算法对数据进行融合,本文提出的算法对应的网络通信量是远远小于这2种算法对应的网络通信量的。根据前文对CS理论的分析可知，这样的结果是必然的。同时，由图1可知，本文提出的算法对应的网络通信量也是小于HEED with CS算法对应的网络通信量的。

由图1(a)可知，在压缩率为5的情况下，当网络中节点数小于1200时，LEACH with CS算法对应的网络通信量少于本文提出的算法对应的网络通信量。当网络中节点数大于等于1200时，本文提出的算法对应的网络通信量更少。由图1(b)可知，在压缩率为10的情况下，当网络中节点大于等于1000时，与LEACH with CS算法相比，本文提出的算法对应的网络通信量更少。同样，由图1(c)可知，在压缩率为15的情况下，在节点数为400～1600的范围内，相较于LEACH with CS算法，本文提出的算法对应的网络通信量更少，效果更好。根据图1可以总结出这样2条结论：1)本文提出的算法更加适合节点数较多、规模较大的无线传感器网络;2)压缩率越大，相较于LEACH with CS算法，本文提出的算法对应的网络通信量更少，效果更好。同时，本文提出的算法采用K-means聚类算法对网络分簇，簇头节点的选举考虑了节点的剩余能量和位置信息。相较于LEACH with CS算法和HEED with CS算法，本文提出的算法均衡了网络能耗，算法的扩展性更好，更加适合大型的无线传感器网络。

3.2 信号重构效果比较

本节基于MATLAB平台进行仿真实验，仿真对象为意大利某城市二氧化氮浓度的数据，数据集来源于UCI机器学习网站。实验比较了以随机高斯矩阵为测量矩阵、傅里叶变换矩阵为稀疏基、以OMP算法为信号重构算法的压缩感知算法(FFTCS)，以随机高斯矩阵为测量矩阵、离散余弦变换矩阵为稀疏基、以OMP算法为信号重构算法的压缩感知算法(DCTCS)和本文提出的基于时空相关性的压缩感知算法。主要比较的是这3种压缩感知算法重构所需要的测量值与重构误差之间的关系[29]。数据的重构误差可以定义为：

(11)

其中，X是原始数据，X′为重构后的数据。

实验结果如图2所示。随着观测值的增加，重构误差的值越来越小。以相对重构误差ε=O(10-15)为精确重构的标准，由仿真结果可知，当观测值为60时，本文提出的基于时空相关性的压缩感知算法已经达到精确重构的标准。然而，FFTCS算法和DCTCS算法，在观测值为300的情况下，仍然没有达到精确重构的标准。当观测值为300时，FFTCS算法的重构误差约为0.128，DCTCS算法的重构误差约为0.134。在相同重构误差的情况下，相较于FFTCS算法和DCTCS算法，本文提出的算法所需要的观测量更少。

图2 不同算法的重构效果

4 结束语

本文基于WSN中节点数据时空相关性的特点，提出了一种将K-means均衡分簇与CS理论相结合的无线传感器网络数据收集算法。该算法采用K-means均衡分簇算法对网络进行分簇并选择簇头节点，簇头节点采用CS理论采集数据，汇聚节点Sink采用OMP算法对收集到的数据进行重构。实验结果表明，相比于其他网络数据收集算法，本文提出的方法的网络通信量更低，扩展性更好，更加适合大型的无线传感器网络；与传统的压缩感知算法相比，本文提出的基于时空相关性的压缩感知算法降低了所需要的观测量，重构效果更好。