基于时空相关性的传感器网络数据压缩算法
2020-03-25王林景高志宇姚鹏帅
王林景, 高志宇, 姚鹏帅
(河南中医药大学 信息技术学院, 郑州 450046)
传感器具有一定的抗干扰性能及感知、 通信能力, 可以对目标的信息进行在线监测和采集, 通过计算机技术和通信技术, 可将多个传感器组合在一起形成一个传感器网络, 对一个区域中多个目标进行检测, 在许多领域应用广泛[1-3]. 在传感器网络的实际应用中, 存在较明显的缺陷, 如传感器节点的能量和宽带有限, 给传感器网络数据传输的距离带来巨大挑战. 为了减少传感器网络数据传输能耗, 提高传感器网络数据的传输质量, 在保证传感器网络数据质量的同时, 尽可能地减少传输数据量. 压缩算法是目前一种重要的减少传输数据量的技术, 其可适当去除数据之间的冗余, 降低传感器网络数据存储空间, 提高传感器网络数据传输速度和成功率, 因此设计一种效果良好的传感器网络数据压缩算法至关重要[4-6].
目前针对数据压缩原理不同, 传感器网络数据压缩算法可分为两类： 无损数据压缩算法和有损数据压缩算法. 其中无损数据压缩算法可对数据进行逆向恢复, 最早的无损数据压缩算法为Shannon编码的压缩算法, 根据数据冗余特性, 引入信息熵理论计算出信息编码的极限, 消除信息中的冗余, 但其压缩效果不理想. 基于Huffman编码的压缩算法属于无损数据压缩算法, 其编码效率高, 运算速度快, 但其需要相应的硬件配合, 因此传感器网络数据压缩的成本较高[7-9]. 为了解决基于Huffman编码压缩算法的缺陷, 出现了基于算术编码的压缩算法, 其重构后的数据与原始数据完全一致, 压缩效果上极大超过了Huffman编码算法, 同时具有Huffman编码算法的运算速度, 但由于其是一种无损数据压缩算法, 因此只针对文档数据进行压缩, 而随着信息技术、 多媒体技术的不断发展, 无损数据压缩算法无法获得理想的数据压缩效果[10]. 有损数据压缩算法主要针对视频、 图像、 声音等数据进行压缩, 虽然重建后的数据与原始数据不同, 但不影响原始数据的表达信息, 主要算法有： 静态图像联合专家小组的压缩算法(joint picture expert group, JPEG)、 动态图像联合专家小组的压缩算法(moving picture expert group, MPEG), 它们根据心理声学机制, 去除掉看不见、 难听见的数据, 从而达到对视频、 图像和声音进行压缩[11-12]. JPEG算法主要针对静止的图像, 其从整体上对图像进行处理, 压缩时间消耗较长； MPEG算法有多个版本, 其主要针对视频数据进行压缩, 具有压缩率高、 兼容性好等优点, 但其只是从空间上对数据进行压缩, 实际上数据在时间上也存在一定的冗余, 因此通用性较差, 对传感器网络数据压缩很难达到理想效果[13-15].
为了解决传感器网络数据压缩过程中存在的问题, 以改善传感器网络数据压缩效果为目标, 本文提出一种基于时空相关性的传感器网络数据压缩算法, 分别从时间和空间上对传感器网络数据进行压缩处理, 消除数据之间的冗余, 并采用具体仿真对比实验分析本文算法的可行性和优越性.
1 传感器网络数据压缩算法的设计
1.1 小波变换算法
传感器网络在采集数据时, 外界因素将一些无用信息包含其中, 这些无用信息可统称为噪声, 用n(t)描述, 则传感器网络的原始数据可描述为
f(t)=s(t)+n(t),
(1)
其中s(t)表示无噪的传感器网络数据[16-17].
小波变换算法是一种空间变换域的数据处理技术, 对原始传感器网络数据通过一定尺度分解, 可产生不同大小的小波系数w(m,n), 无噪传感器网络数据的小波系数与分解尺度m成正比, 而噪声与m成反比, 基于该特点可进行传感器网络数据消噪处理, 从空间上对传感器网络数据进行一定的压缩, 在减少传感器网络数据规模的同时, 提高传感器网络数据质量, 算法步骤如下：
1) 采用小波变换对原始传感器网络数据进行m尺度分解得到多个小波系数w(m,n), 其中n表示小波系数编号;
2) 计算w(m,n)和w(m+1,n)两个小波系数的关联度
R(m,n)=w(m,n)·w(m+1,n);
(2)
3) 设
采用
(3)
对关联度进行归一化操作, 缩小其取值范围;
4) 若满足条件|NR(m,n)|≥λ, 则表示w(m,n)对应的有用传感器网络数据, 其值保持不变; 否则其对应噪声, 小波系数设置为零,λ的计算公式为
(4)
其中σ(m)表示Pw(m)的均方差;
5) 采用小波逆变换对处理后的小波系数进行重构, 消除传感器网络数据中的噪声后, 减少了传感器网络数据存储空间.
1.2 压缩感知算法
1.2.1 压缩感知理论 去噪后的传感器网络数据可视为一个序列数据x, 其长度为N, 通常条件下, 该序列信号具有一定的非稀疏特性, 引入稀疏变换矩阵ψ∈N×N将其变换成稀疏数据f：
f=ψx.
(5)
基于压缩传感算法的工作原理, 根据稀疏信号与测量矩阵Φ∈M×N得到观测数据y, 其长度为M, 且满足条件：M≪N, 观测数据[18-20]为
y=Φf.
(6)
可以对观测数据y进行l0范数求解, 得到稀疏数据f的解：
将稀疏数据和测量矩阵进行合并可以产生：
(8)
根据式(5)可得x的精确解：
(9)
图1 压缩感知的工作原理
因此, 压缩感知理论的工作过程如图1所示.
1.2.2 数据重构算法 数据重构算法是压缩感知理论的核心内容, 主要目的是从观测数据中完整地恢复出原始数据, 本文选择正交匹配追踪算法作为传感器网络的数据重构算法, 其工作步骤如下：
1) 对正交匹配追踪算法的输入向量进行相应设置;
3) 搜索传感器网络数据的支撑索引, 计算公式为
(10)
4) 在搜索到传感器网络数据的支撑索引中加入数据支撑集, 即
Λl=Λl-1∪{λl};
(11)
5) 对残差按如下公式进行更新：
(12)
6) 输出重构后的传感器网络数据：
(13)
1.3 传感器网络数据压缩算法的工作原理
为提高传感器网络数据压缩效果, 本文提出一种基于时空相关性的传感器网络数据压缩算法, 其工作原理为： 首先采集传感器网络原始数据, 然后采用空间变换技术从空间上分析传感器网络数据之间的相关性, 进行去噪处理, 减少噪声所占的空间资源, 最后根据传感器网络数据时间上的相关性, 引入压缩感知算法对空间系数进行压缩处理, 减少传感器网络数据冗余, 其原理如图2所示.
图2 基于时空相关性的传感器网络数据压缩原理
2 传感器网络数据压缩算法性能仿真实验
为了分析基于时空相关性的传感器网络数据压缩的有效性, 本文采用MATLAB 2018作为仿真测试平台, 选择传感器网络数据压缩比、 传感器网络数据压缩前后数据的相似度及传感器网络数据压缩时间对实验结果进行评价. 为了体现时空相关性的传感器网络数据压缩算法的优越性, 选择MPEG的传感器网络数据压缩算法、 文献[15]的传感器网络数据压缩算法进行对比测试. 设传感器网络共有100个节点, 采集的数据为温度、 湿度、 图像、 声音、 视频, 传感器节点的通信距离为10 m.
2.1 传感器网络数据压缩比对比
图3 传感器网络数据压缩比对比
压缩比主要描述压缩后的数据量占原始数据量的比例, 时空相关性的传感器网络数据压缩算法、 MPEG算法和文献[15]算法的数据压缩比对比结果如图3所示. 由图3可见, MPEG算法和文献[15]算法的传感器网络数据压缩比较高, 对于温度、 湿度, 其压缩比较小, 但对于图像、 声音、 视频, 其压缩比始终高于50%, 无法充分描述传感器网络数据的时间和空间相关性, 而时空相关性的传感器网络数据压缩算法对所有类型的数据, 其压缩比均较小, 能充分挖掘传感器网络数据的时间和空间相关性, 最大程度地去除了冗余数据, 在相同条件下能获得较优异的传感器网络数据压缩结果.
2.2 传感器网络数据压缩前后数据的相似度对比
本文算法、 MPEG算法和文献[15]算法的传感器网络数据压缩前后的数据相似度(%)对比结果如图4所示. 由图4可见, 相对于MPEG算法和文献[15]算法, 本文算法提高了压缩前后的数据相似度, 即在保证压缩比的同时, 保证了传感器网络数据的有效性, 可重构得到更理想的原始传感器网络数据, 能描述更多的传感器网络原始数据.
2.3 传感器网络数据压缩时间对比
在传感器网络数据压缩过程中, 算法的执行速度十分重要, 本文采用传感器网络数据压缩时间对算法的执行速度进行评价. 本文算法、 MPEG算法和文献[15]算法的传感器网络数据的压缩时间(s)对比结果如图5所示. 由图5可见, 与基于MPEG算法和文献[15]算法的压缩时间相比, 本文算法的传感器网络数据压缩时间大幅度降低, 加快了传感器网络数据压缩速度, 在相同时间内, 可以处理更多的传感器网络数据, 提高了传感器网络数据压缩效率.
图4 传感器网络数据压缩前后的数据相似度对比
图5 传感器网络数据压缩效率对比
综上所述, 为了解决当前传感器网络数据压缩算法存在压缩比小、 信息丢失严重等缺陷, 本文提出了一种基于时空相关性的传感器网络数据压缩算法. 首先采用小波变换技术从空间上对传感器网络数据进行处理, 去除噪声所占的空间资源; 然后采用压缩感知算法从时间上对传感器网络数据进行去冗余操作; 最后与其他传感器网络数据压缩算法进行对比测试实验. 实验结果表明, 本文算法是一种速度快、 压缩比小的传感器网络数据压缩算法, 极大降低了传感器网络传输的数据量, 达到了传感器网络数据压缩的目的, 具有广阔的应用前景.
