传感网络中误差有界的分段逼近数据压缩算法

摘要

Wireless sensor networks usually have limited energy and transmission capacity. A critical and practical demand is to online compress sensor data streams continuously. This paper makes the following contributions. First, using the built-in buffer of sensor node, a piecewise constant approximation based data compression algorithm with infinite norm error bound is presented, which is named PCADC-sensor and is a near online algorithm. Second, with infinite norm and square norm error bound respectively, this study proposes two online piecewise linear approximation based data compression algorithms in sensor node, named PL ADC-sensor. A necessary and sufficient condition of PLA uniform approximation is given. Third, a piecewise linear representations based data compression algorithm in cluster head or sink, named PLRDC-cluster is presented. It does not need raw sensory data and can be applied to calculate aggregate functions. Last, the experiments on real-world sensor dataset show that the proposed algorithms match the sensor data stream model and can achieve significant data reduction.%无线传感器网络通常能量、带宽有限.一个关键而实用的需求是,在保证数据质量的情况下,对持续到达的采样数据进行在线式压缩.主要贡献:①利用传感器节点内置的缓冲区,提出了单传感器节点上基于分段常量逼近的准在线式数据压缩算法(PCADC-sensor),并给出了在无穷范数误差度量下的实现；②提出了单传感器节点上基于分段线性逼近的在线式数据压缩算法(PLADC-sensor).分别在无穷范数和2范数误差度量的情况下给出了计算PLA的两种简单快速算法,推导了分段线性一致逼近的充要条件;③簇头或基站无需接收原始采样数据,提出了基于原始数据的分段线性表示的压缩算法(PLRDC-cluster),推导了同一节点不同时段、不同节点相同时段两种情况下的计算公式.实验结果表明,这些算法较好地匹配了传感器数据流模型,显著减少了冗余数据传输.