朱竹芳,焦 俊,李郑涛,孟珠李,张政云,杨莎莎
(安徽农业大学 信息与计算机学院,合肥 230036)
分簇算法与压缩感知下的农田信息处理
朱竹芳,焦 俊,李郑涛,孟珠李,张政云,杨莎莎
(安徽农业大学 信息与计算机学院,合肥 230036)
为了减小无线传感器传输数据的数据量,提出了一种相关性分簇算法与压缩感知相结合的方法。首先,将节点数据显著相关性的节点划分到一个簇中;其次,在每个簇中,根据节点间的平均相关度大小来确定参考节点与非参考节点,参考点的数据结合压缩感知进行无线网络传输,而非参考点的数据可以根据与参考节点的线性回归系数计算出来;最后,对实测的温度进行仿真实验。结果表明,簇中参考节点的数据重构误差在允许范围内,对非参考节点进行线性回归计算与原始数据相比基本吻合。
无线传感器;分簇;平均相关度;线性回归;压缩感知
无线传感器网络[1](wireless sensor network, 简称WSNs)由部署在监测区域内大量的廉价微型传感器节点组成,其特点就是部署灵活、规模大、集成化等,广泛应用于数据采集和监测。由于传感器节点上的能量有限,大量的数据传输,以及传统的无线通信采样传输,产生大量的冗余信息会缩短传感器节点的使用寿命,所以减少数据传输采样量是节约节点能耗、延长网络生命周期的有效方法[2]。
减小无线传感器网络节点能源消耗的方法有很多,比如太阳能光伏转换,[3]可以为WSN节点提供充足的能量而延长其寿命,以及延长节点采集的密度来减少无线模块发射的能耗[4]。而本文所说的结合分簇算法与压缩感知的方法,首先对节点数据进行相关性分析,将数据具有显著相关性的节点分在一个簇中,然后在每个簇中确定参考节点与非参考节点,[5]其次,只需将参考节点结合压缩感知,对信号进行稀疏化,选取合适的观测矩阵,然后将测量值进行无线网络传输,[6]最终在接收端对信号进行精确重构,而非参考节点数据只需根据线性回归关系来计算,该方法并不需要考虑外界环境和采集数据量等因素,从而有效减少了无线传感器网络传输数据的数据量,也降低了无线网络传输的能量消耗[7]。
在农业领域中,用传感器节点采集农田信息时,传感器之间所采集到的相同参数的数据往往存在着很强的相关性,[8]如果让所有节点的数据进行网络传输,会让协调器长时间工作,耗电量大而减短无线网络的使用寿命[9]。而簇内参考节点结合压缩感知进行无线传输,非参考节点利用线性回归进行计算,这样就减少网络传输量,进而延长了无线网络的生命周期。[10]整个数据采集过程如图1所示,其中协调器本身是汇聚节点,上电之后组建Zigbee网络,同时协调器也是监测节点,满足实验设计要求。
整个算法的具体设计步骤:
图1 信息处理框图
(1)获取无线传感器网络节点的参数数据(温度,湿度或者ph值),本实验只针对温度参数数据进行相关性分析,将节点分成多个簇,如图1中簇1、簇2、簇3所示。每个簇中根据平均相关度的大小将簇中的分点划分成参考节点与非参考节点,并且求出参考节点与非参考节点的回归系数。
(2)将选取的参考节点的数据,进行稀疏化,选取合适的观测矩阵,压缩之后经过协调器传输。
(3)参考节点在服务器接收端进行数据重构,而非参考节点根据参考节点的线性回归系数进行估算。
分簇算法的中心思想就是先根据相关系数的大小,找出两个最不相关的节点分别划分到两个簇中,再根据平均相关度的大小依次将其他节点放在这两个簇中。按照上述算法可以划分更多的簇,直到簇中节点间的数据都显著相关。
假设监控区内WSNs节点有M1个,每个节点以相同时间间隔采样了N个数据,那么将所有节点所接受的数据储存起来以N*M1的矩阵的形式表示:
(1)
其中,该矩阵每一列表示一个节点所采样到的信号向量,每一行表示所有节点同一时间所采样到的信号向量。
依次求任意列与列之间的相关系数:
(2)
可以将相关系数写成相关系数矩阵形式:
(3)
要判断节点x和节点y是否显著相关,可利用样本中的相关系数来给定一个检测统计量:
(4)
整个算法的流程如图2所示。其中,平均相关度的定义:
(5)
图2 分簇算法的整体流程图
式中k表示簇中节点的个数,rijm表示两节点间的相关系数。分簇结束后,在每个簇中,根据式(5)将节点的平均相关度最大的定义为参考节点,而其他的节点定义为非参考节点。
3.1 信号的稀疏表示
稀疏基ψ(N*N矩阵)是正交基矩阵,它其实就是某种正交变换的变换矩阵列向量组成的基。压缩感知的第一要素就是信号是稀疏的或者进行某种变换可以变成稀疏的,所以稀疏基的选取是压缩感知的关键。
采取的稀疏基是离散傅立叶变换基,式6表示的是离散傅立叶变换的正交变换公式
(6)
3.2 观测矩阵的设计
观测矩阵的目的就是将信号从高维投影到低维空间上,从而获得M个观测向量y,如式7所示,同时要确保从得到的观测矩阵能够重构出长度为N的原始信号。在压缩感知理论中,为了让观测值能够包含足够多的重构信号的信息,观测矩阵的设计要满足有限等距性质(RIP)如式8表示,
y=φx=φψθ
(7)
(8)
其中,δ为等距约束常数δ∈(0,1)。
采取的观测矩阵φ是随机高斯测量矩阵,构造一个M*N的观测矩阵,并且与稀疏基完全不相关,矩阵里每个元素独立,且服从均值为0,方差为1/M的高斯分布 。
3.3 重构算法
重构的算法具体来说就是利用感知矩阵Θ=φψ和测量向量值y得到稀疏表示,从而得到重构x。算法的关键是在少量样本点下,快速、精确地重构原信号,信号的重构是从长度为M的测量样本中,重构出长度为N的原信号的过程。该过程可归结为一个寻求约束条件下的最优解的问题,具体表述如式9所示:
(9)
s.t.φψ-1X=Y
采取的重构算法是正交匹配追踪,算法流程如图3所示。
3.4 节点采样的实现
图3 重构算法流程图
3.4.1 参考节点的压缩重构 在每个簇中首先选择根据节点间相关性强弱确定参考节点,其中步骤如下:
(1)选取簇1内节点数据,将数据用矩阵表示,并求出节点间的相关系数;
(2)求出相关系数的绝对值;
(3)将矩阵斜对角的数都变为0;
(4)求出矩阵每行的平均数即为平均相关度;
(5)找出平均数的最大值;
(7)找出所对应相关系数最小值的位置;
(8)将对应的一列赋值到X中,并且X为参考节点的一列数据;
(9)除掉了平均值相关度值最大一列的数据,剩余为非参考节点。
将选取好的参考节点进行压缩再重构,它的关键步骤如下:
(10)首先选取好合适的稀疏基和观测矩阵;
(11)传感矩阵各列与残差的内积;
(12)求出最大内积绝对值对应列的位置;
(13)最小二乘解;
(14)求出残差;
(15)得到原始数据的稀疏表示;
(16)得到重构数据。
3.4.2 非参考节点的计算 由于参考节点与非参考节点之间显著相关,所以就可以直接求出两者之间的线性回归系数,这样非参考节点并不需要进行传输,只需根据与参考节点的线性关系进行估算,其中涉及到的关键代码:
(1)选取一个非参考节点数据;
(2)求出参考节点与非参考节点的线性回归系数;
(3)线性回归求出非参考节点的数据;
(4)进行循环回到第一步,直到计算所有非参考节点数据;
(5)整个算法结束。
4.1 分簇仿真
本次实验选取了27个传感器节点中的温度数据,如图4所示,其中分别将网络节点随机分布在一个100 m* 100m的监测区域内。在该传感器网络中,每个传感器节点周期地探测温度、湿度、光照等信息,现以每个节点按1s间隔来采集128个数的数据,该实验是在Acer Aspire M3910电脑上通过 Matlab 平台进行实验。运用式(1)-(4)将节点1从节点27的数据分成三个簇,实验结果如图5、图6、图7所示,其中图5是节点1,2,4,5, 6,10,11,12,13,14,15,17,18,19,22的数据,图6是节点7,8,16,20,21,22,23,24,25,26,27的数据,图7是节点3,9的数据。
图4 总体数据图
图5 簇1
图6 簇2
图7 簇3
4.2 压缩感知实验仿真
本次实验数据采取上面分簇中的簇1里的数据,对簇1的数据进行选取参考节点与非参考节点,从表1可以看出选取节点11作为参考节点。参考节点压缩重构的数据结果如图8所示,非参考节点的估算的数据如图9所示。
对图4、图9进行比较可以看出非参考节点进行估算的精确度比较高,同时由图10可以看出非参考节点的原始数据与根据参考节点的线性关系进行估算的数据最大误差都保持在0.5~3℃左右,最小误差基本在0℃左右。从图11可以看出,随着采集数据长度的增加,两种数据收集方法的网络通信能耗都在增加,但由于压缩感知的数据收集方法网络能耗增加速度远远小于传统采样的网络能耗,并且随着采集信号长度的增加,能量节省效果越明显。
表1 簇内节点的平均相关度
图8 参考节点压缩前后对比
图9 非参考节点的估算图
图10 误差对比图
图11 能量消耗对比图
将分簇算法和压缩感知结合起来,首先保证了簇内节点间的数据的相关性,进而有利于将参考节点进行无线网络传输,而非参考节点只需根据与参考节点的线性回归系数进行估算,这样减轻了协调器的工作量。将压缩感知运用在无线传输中,采取压缩观测值进行传输大大减少了网络通信数据量,进而降低了无线传感器网络的能量消耗,延长了整个无线传感器网络的使用寿命。文中所给出的仿真实验的结果表明,分簇算法和压缩感知结合的方法具有较高的应用价值。
[1] 王泉,张纳温,张金成,等.压缩感知在无线传感器网络数据采集中的应用[J].传感技术学报,2014,(11):1562- 1567.DOI:10.3969/j.issn.1004- 1699.2014.11.022.
[2] 焦俊, 操俊, 潘中,等. 基于物联网的农田环境在线监测系统[J]. 农业工程, 2014(6):19- 22.
[3] 张波,刘郁林,常博文,等.线性回归的分布式压缩采样算法[J].重庆邮电大学学报(自然科学版),2014,26(2):207- 213.DOI:10.3979/j.issn.1673- 825X.2014.02.012.
[4] 张金成,吕方旭,王钰,等.WSNs中的分簇式压缩感知[J].仪器仪表学报,2014,35(1):169- 177.
[5] 吕方旭,张金成,石洪君,等.WSN中的分布式压缩感知[J].传感技术学报,2013,(10):1446- 1452.DOI:10.3969/j.issn.1004- 1699.2013.10.024.
[6] 王天荆,郑宝玉,杨震,等.基于滤波的压缩感知信号采集方案[J].仪器仪表学报,2013,34(3):573- 581.DOI:10.3969/j.issn.0254- 3087.2013.03.014.
[7] 宋欣,王翠荣.基于线性回归的无线传感器网络分布式数据采集优化策略[J].计算机学报,2012,35(3):568- 580.DOI:10.3724/SP.J.1016.2012.00568.
[8] 孟南南.压缩感知算法的FPGA实现研究[D].青岛大学,2013.
[9] 王强, 焦俊, 孔文等. 基于NS2的固定和移动节点的无线传感网络的仿真[J]. 合肥学院学报(自然科学版), 2015, 25(2):24- 28.
[10] Candes E. Compressive Sampling[M]//Proceedings of International Congress of Mathematicians. Zurich, Switzerlandi European Mathematical Society Publishing House, 2006:1433- 1452.
[责任编辑:张永军]
Farmland Information Processing Based on Clustering Algorithm and Compressed Sensing
ZHU Zhu- fang,JIAO Jun,LI Zheng- tao, MENG Zhu- li,ZHANG Zheng- yun,YANG Sha- sha
(School of Information and Computer,Anhui Agriculture University,Hefei 230036,China)
In order to reduce the amount of data of wireless sensor data,this paper propose a method combining with Correlation Clustering Algorithm and compressed sensing.First,the nodes which are significantly correlated with the node data are divided into a cluster.Then, the average correlation degree can determine the reference node and the non reference node in each cluster, and the data of the reference node can transfer for wireless network combining with compressed sensing, while the data of the non reference node can be calculated according to the linear regression coefficient of the reference node. For simulation experiment of the measured temperature, it is proved that the data reconstruction error of the reference node in the cluster is in the allowable range, and the linear regression calculation of the non reference node is basically consistent with the original data.
wireless sensor;clustering algorithm;average correlation degree;linear regression; compressed sensing
2016-11-29
2017-02-25
国家自然基金项目(31671589)资助。
朱竹芳(1992— ),女,安徽安庆人,安徽农业大学信息与计算机学院2015级硕士研究生。
TN915
A
2096-2371(2017)02-0041-06