基于熵降变换的无线传感网感知数据无损压缩算法研究

【作者】 任学军；

【导师】 房鼎益；

【作者基本信息】 西北大学 ， 计算机软件与理论， 2011， 博士

【摘要】 无线传感器网络(WSN)的应用越来越广泛,然而无线传感器节点的能耗问题却是制约其应用的瓶颈之一。研究表明,传感节点的能量主要消耗在无线数据传输的过程中,因此各种数据压缩算法的研究迅速成为无线传感器网络中的新热点。传感器网络中的有损数据压缩研究已经有很多,基于传感节点的无损数据压缩算法却只有有限的几个。目前传感节点中的无损压缩算法均是对传统无损压缩算法的裁剪,其性能尚不能满足应用的需求。从实际应用角度,研究基于传感节点的无损压缩算法往往更有现实意义。原因在于：无损数据传输是很多高级应用的必然要求；基于传感节点的无损数据传输是数据融合的前提；基于传感节点的无损压缩是很多有损压缩和分布式压缩算法的基础。因此,本文展开了针对传感节点的无损数据压缩算法研究。本文分析了一元线性拟合及DCT(离散余弦变换)和DWT(离散小波变换)对传感数据概率分布的影响,提出熵降变换+熵编码是进一步提高传感节点无损压缩效率的有效途径,并依此提出了多个熵降变换算法及一个熵编码算法,为WSN中的无损数据压缩研究提供了新的设计思路和实现途径。论文的主要研究工作和创新点概括如下：1.提出了基于熵降变换的无损压缩模型基于信源编码的无损数据压缩已无太大的潜力可挖,而通过可逆变换改变数据的概率分布则可以减小信源的实际熵并进一步提高其无损压缩率,因此本文提出了熵降变换+熵编码的无损压缩模型。通过深入分析后认为,熵降变换是进一步提高无损压缩效率的有效途径；可实现无损数据压缩的可逆熵降变换有很多个,只有最符合传感数据概率分布规律的变换才是最有效的。2.提出了多个基于拟合残差变换的熵降变换算法基于拟合残差变换的熵降算法研究从基于一元线性回归模型的传感数据拟合算法开始,通过对拟合残差进行熵编码实现了无损压缩(FR算法)。接着,分析了拟合残差编码算法的缺陷,提出了一种基于差值拟合残差编码的无损压缩新算法(DFR算法),达到了较好的压缩效果。针对差值拟合残差编码算法只能逆序解码,不适合实时应用的缺点,又提出两种基于差值拟合预测残差编码的算法,在保持了较高的压缩率的情况下,减小了编码延迟。3.提出了多个基于可逆域变换的熵降变换算法基于可逆域变换的算法研究从H.264中的DCT算法开始。首先对H.264中的DCT变换进行了分析,抛弃了原算法中复杂的量化、反量化模块及熵编码模块,引入了组合量化和S-Huffman熵编码,实现了一个可运行于传感节点之中的无损压缩算法(H264-DCT算法)。由于H264-DCT算法依然存在组合量化模块,使其只能实现准可逆变换。因此,又基于提升结构提出了一种完全可逆的整数DCT变换算法(S-DCT算法)。S-DCT算法在压缩率和运算速度上均有不错的提升。然后,研究了小波变换在传感节点中的应用,提出了基于提升结构5/3小波的改进算法(DWT53算法),其压缩效果比S-DCT更好。之后,通过分析S-DCT变换和DWT53变换的机理及二点提升结构对数据概率分布的影响,提出了一种新的变换算法——差值-中值-差值变换(简称差中差变换,DMD变换)。DMD变换可以对非单调数据进行有效压缩并在对实际数据的测试中取得了良好的效果。4.提出了一种针对熵降变换的熵编码算法根据两类熵降变换算法的特点,研究了基于正态分布的熵编码算法(ND-Encoding),通过对该算法的不断改进提出了一种自适应正态分布熵编码算法(CAND)。该算法针对慢变和非慢变数据均有良好的压缩性能。CAND算法的提出,使得变换与编码紧密结合为一个完整的无损压缩系统。代码分析和综合测试结果表明,本文所提出的多个基于熵降变换的无损压缩算法均能够以较小的运算量和存储空间开销获得比较突出的无损压缩率,充分证明了本文的观点：通过可逆熵降变换改变原始数据的概率分布是提高无损压缩性能的有效途径；可完成无损数据压缩的可逆熵降变换不只有DCT变换和DWT变换两种,而可以有很多种；任何一种可逆变换只要可以改变原始数据的概率分布,并可以利用该分布实现有效编码,就可以实现高效的无损数据压缩!更多还原

【Abstract】 Efficient utilization of energy has become a bottleneck to restrict the application of wireless sensor networks. It shows that most of the energy is consumed by the wireless communication module in sensor node for data transmission. The research of compression algorithms has become a new research focus, as the compression methods can reduce the number of bits to be transmitted by communication module to significantly reduce the energy requirement and increase the lifetime of the sensor node.They are a lot of lossy compression algorithms have been proposed for wireless sensor networks in recent year. But only a few papers have discussed the lossless compression algorithms in sensor nodes. Since most of the sensor nodes lossless algorithms are tailored from classic algorithms designed for personal computers, the compression performance of these algorithms cannot meet the requirement of practical application in WSN.This paper argues that the research of lossless compression algorithm is more significant in practical. The reasons can be list as follow. The lossless data is a necessary requirement for many advanced applications. The lossless transmission from sensor nodes is a prerequisite for many data fusion algorithms in cluster nodes. Most of lossy and/or distributed compression algorithms can be tailored from lossless algorithms to achieve higher compression ratio and better performance. Therefore, the research of lossless compression algorithm is carried out by this paper.Through analyzing the influence of sensor data’s probability distribution after discrete cosine transform (DCT) and/or discrete wavelet transform (DWT) and/or linear fitting, this paper considered that to encode result data after an entropy-decrease-transform is the only way to further improve the performance of lossless compression ratio. Then, several new entropy-decrease-transform algorithms and an entropy-encoding algorithm are proposed to prove this point. Hence, this paper provided a new method for design and realization of lossless compression in sensor nodes. The research works and innovations can be described as follow. Firstly, a new lossless compression model named Entropy-Decrease-Transform Compression Model is proposed in this paper. Since the research of source coding algorithms is close to perfect, to encode data after entropy-decrease-transform, which can reduce the entropy of sensor data through a reversible transform, has become the only way to further improve the performance of lossless compression ratio. The Entropy-Decrease-Transform Compression Model states that the forms of entropy-decrease-transform are unlimited and the best lossless compression ratio can be achieved only when the corresponding entropy-decrease-transform follows the sensor data’s probability distribution.Secondly, several new algorithms based on fitting-residuals-transform, which is a kind of entropy-decrease-transform, are proposed to achieve lossless compression. The research of fitting-residuals-transform started from a lossless algorithm based on one-dimensional linear regression model (i.e. FR algorithm). The algorithm calculates the fitting-residuals between sensor data and the fitting data based on the linear regression model. Then the fitting-residuals are input to an entropy encoder to achieve compression. By analyzing the shortcomings of FR algorithm, a new algorithm based on difference fitting residuals (DFR algorithm) is proposed to achieve a better compression results. As the inverse transform of DFR must be reversed, which is not suitable for real-time application, this paper proposed two algorithms (P-DFR and P-DFR2 algorithm) based on the difference fitting prediction residuals. Both algorithms can reduce the coding delay while maintaining high compression ratios.Thirdly, several new algorithms based on reversible-domain-transform, which is a kind of entropy-decrease-transform too, are proposed to achieve lossless compression. The research of the reversible-domain-transform started from the DCT transform in H.264. This paper proposed a simple DCT transform from H.264 (H264-DCT algorithm) by replace the complex quantitative, quantization and entropy encoder module with a combination quantization module and a simple Huffman encoder. As the H264-DCT algorithm remains the combination quantization module, it can only achieve quasi-reversible transform. Therefore, this paper proposed a reversible integer DCT-algorithm (S-DCT algorithm) based on the lifting scheme. S-DCT compression algorithm has achieved higher performance on compression ratio and computational complexity. Then, by analyzing the applications of discrete wavelet transform in WSN, this paper proposed an improved algorithm of lifting scheme 5/3 wavelet (DWT53 algorithm) to achieve lossless compression in sensor node. The compression ratio of DWT53 is better than S-DCT’s. After that, this paper has analyzed the compression mechanism of S-DCT and DWT53 and found that the core of reversible transform is the lifting scheme. Then, this paper has analyzed the characteristics of 2-point lifting scheme and its influence for sensor data’s probability distribution. Finally, a new entropy-decrease-transform named difference-median-difference transform (DMD transform) is proposed in this paper. The DMD can get better compression ratio for non-monotonic data than others.Finally, an entropy encoding algorithms is proposed to achieve better compression ratio. After proposed several entropy-decrease-transform algorithms, the paper found that the third-party entropy encoder used by these algorithms is difficult to play down the advantages of transforms. By analyzing the result data’s probability distribution of entropy-decrease-transforms, this paper proposed a new entropy encoder based on normal distribution (ND-Encoding algorithm). And then, after continuous improvement of the algorithm, a context adaptive normal distribution entropy encoding algorithm (CAND algorithm) is proposed in this paper. The algorithm can achieve better compression ratio for both slowly-varying data and non-slowly-varying data.Through the code analyzing and comprehensive testing, this paper has shown that all proposed algorithms can smoothly run in sensor node to achieve good compression ratio, despite a less computational effort. Hence, some conclusions can be made as follows. Through reversible entropy- decrease-transform to change the probability distribution of sensor data is the only way to improve the performance of lossless compression. The form of entropy-decrease-transform is not restricted to DCT and DWT. There are many reversible entropy-decrease-transforms can be used to achieve lossless compression, while most of them ware not be found by us yet. If any reversible algorithm can change the probability distribution of sensor data and the change can be gain to achieve effective entropy encoding, it would achieve efficient lossless data compression!更多还原