CN102595496A - 用于无线传感节点感知数据的上下文自适应商余编码方法 - Google Patents

Abstract

本发明公开了一种用于无线传感节点感知数据的上下文自适应商余编码方法，具体按以下步骤进行：对需要编码的N个传感数据依次进行求差，得到原始差值数据；将原始差值数据分别进行变换得到差值数据；初始化数据位数D为1，i＝1；将当前差值数据作为被除数，将2^D作为除数，得到当前差值数据的商Q和余数R；对余数进行定长编码，对商进行变长编码；令数据位数D等于当前差值数据的位数；判断是否还有下一个未编码的差值数据，如果有，i＝i+1，跳转步骤3，否则编码完成，得到差值数据的商余编码。本发明对针对慢变数据和非慢变数据均压缩率高，可以平滑地运行于传感节点之中，并实现无损数据压缩，且本发明运算复杂度低，存储空间占用小。

Description

用于无线传感节点感知数据的上下文自适应商余编码方法

技术领域

本发明属于数据压缩技术领域，具体涉及一种用于无线传感节点感知数据的上下文自适应商余编码方法。

背景技术

无线传感器网络(WSN)的应用越来越广泛，然而，无线传感器节点的能耗问题却是制约其应用的瓶颈之一。研究表明，传感节点的能量主要消耗在无线数据传输的过程中，因此各种数据压缩算法的研究迅速成为无线传感器网络中的新热点。

目前，传感器网络中的有损数据压缩研究已经有很多，基于传感节点的无损数据压缩算法却只有有限的几个。2006年Sadler C.M.和Martonosi M.提出一种基于字典的无损数据压缩算法，称为S-LZW算法，它是基于著名的LZW算法的一个针对无线传感器网络的改进版本，也是无线传感器网络中的第一个无损压缩算法。2008年，Marcelloni F.提出一种专用于传感节点数据压缩的简单Huffman(S-Huffman)编码算法，其编码方法是：首先对采集到的传感数据求差，然后对差值进行熵编码，越小的数据，编码越短，越大的数据，编码越长。该算法对温湿度数据可以达到60％以上的压缩率，相比S-LZW(27.25％)算法，具有明显的优势。由于该算法实现简单，运算速度快，压缩率高，很快成为传感器节点中的经典无损压缩算法。2009年和2010年，Tharini C.和范祥辉等分别提出了对S-Huffman算法的改进，通过构造二叉树来实现一种自适应Huffman编码。自适应Huffman编码对出现次数多的数据编以较短的编码，对出现次数少的数据编以较长的编码。对于中相关度的数据，自适应Huffman编码可以达到比S-Huffman有更好的压缩率。

但是，上述这些算法均存在以下一些明显的问题：

S-LZW算法是对PC机中的LZW算法的裁减，LZW算法是一种基于字典的无损压缩算法，它更适合于文本压缩，而不是数字压缩。因此，S-LZW算法对传感数据的压缩率并不高。同时，LZW算法需要一个很大的字典表来存储已有的串，S-LZW算法虽然对表空间进行了裁减，但相对于传感节点的存储容量来说，它所需要的存储空间依然太大。正是因为S-LZW算法需要占用较大的存储空间，算法实现也比较复杂而压缩率又不够高，因此，后续继续对该算法的研究很少。

S-Huffman算法只需一个占用15个字节的前缀表，同时压缩率也比较高，因此很快成为传感节点中的经典无损压缩算法。但由于S-Huffman是对前后数据的差值直接进行编码，因此，它只对变化比较缓慢的数据有比较好的压缩效果，当数据变换剧烈时，其压缩效果会急剧下降甚至还会出现负压缩(即压缩后的数据比压缩前的数据还要长)。同时，由于S-Huffman算法使用了Log₂ ^M这样的传感节点CPU并不支持的函数，其实现后的算法比较复杂，要根据输入数据的大小来具体实现。根据Marcelloni F.自己的描述，这一操作平均需要355个指令周期才能完成，相对于传感节点有限的处理能力才说，这一操作还是显得过于复杂。

而针对S-Huffman算法的两个改进算法，虽然对中相关度数据有较高的压缩率，但对于高相关度的数据，其压缩率的提升并不明显(由于自适应机制需要一定的适应时间，有时压缩率反而不如S-Huffman算法)。由于两个改进算法同样是对差值直接编码，因此，同样不适合于低相关度的数据(急剧变换的数据往往是低相关数据)的压缩。同时这两个算法需要更大的运算量和存储空间来完成自适应树的更新和维护，这些开销与压缩率的提升相比，显得并不相称。

从以上分析可看出，目前传感节点中的无损压缩算法研究，还停留在比较原始的阶段。主要表现是尚没有专用的算法出现，还停留在对PC机上经典算法进行改造并使之可以运行于节点之中的阶段。目前传感节点中的无损压缩算法均是对传统PC机无损压缩算法的裁剪，其性能尚不能满足应用的需求。

从实际应用角度，研究基于传感节点的无损压缩算法往往更有现实意义，原因如下：

(1)无损数据传输是很多高级应用的必然要求

有损压缩技术虽然能够显著地提高压缩率，但往往是以丢弃大量原始数据并/或损失原始数据的精度为代价的。无线传感器网络的主要应用是监测各种环境参数，而很多参数需要保持其原始精度，有损压缩算法无法达到这一要求。例如：在无线传感器网络的很多军事应用中，需要监测被测区域可能发生的未知变化。由于事前不能确定被测区域会发生哪些变化，传感节点就应该尽可能地保持采集数据的原始精度，并将其传回控制中心进行深入分析。再比如：在很多遥感和医学应用中，需要保持图像传感器采集到的高光谱图像的原始精度。在这些应用中，无损数据传输显然是非常必要的。

(2)来自传感节点的无损数据传输是数据融合的前提

很多应用采用数据融合算法来减少网络上传输的数据，但数据融合算法通常运行于汇聚节点中。为确保数据融合的准确性，要求融合前的数据必须保持原始精度。采用基于传感节点的无损压缩算法可以减少从传感节点往汇聚节点的数据传输，从而进一步提高节点的生存期。

(3)基于传感节点的无损压缩是多数有损压缩和分布式压缩算法的基础

多数无损压缩算法经过简单的裁减可以转换为有损压缩算法，且这种裁减通常可以在提高压缩率的同时减少运算量。例如：前文提到S-Huffman算法，如果在得到传感数据的差值后，设置一个阈值，将小于阈值的数据简化为0，而只编码大于阈值的数据，该算法就可以变化为有损算法，它可以在大大提高压缩率的同时，减少运算量。其它无损压缩算法大多数可以通过类似的方法转化有损压缩算法。同样，很多基于本地节点的压缩算法经过简单的变化可以转化分布式算法。例如：在基于广播的密集传感器网络中(这一假设条件与SERVETTOS.D.所提出的分布式小波变换算法相同)，节点间可以运行S-Huffman算法以减少相邻节点数据的空间相关性，从而实现一种分布式无损压缩效果。因此，基于传感节点的无损压缩是很多有损压缩和分布式压缩算法的基础。

发明内容

针对上述现有技术中存在的缺陷或不足，本发明的目的在于，提供一种用于传感器节点感知数据的上下文自适应商余编码方法(Context-based Adaptive Quotient Remainder encodingalgorithm，简称CAQR算法)。本发明对针对慢变数据和非慢变数据均压缩率高，可以平滑地运行于传感节点之中，并实现无损数据压缩，且本发明运算复杂度低，存储空间占用小。

为了达到上述目的，本发明采用如下的技术解决方案：

一种用于无线传感节点感知数据的上下文自适应商余编码方法，具体按以下步骤进行：

步骤0：对需要编码的N个传感数据Gandata[1]，Gandata[2]，Gandata[3]，……，Gandata[N]按照d[i]＝Gandata[i+1]-Gandata[i]依次进行求差，得到N-1个原始差值数据d[1]，d[2]，d[3]……d[i]……d[N-1]，其中，N为自然数，i＝1，2，3……N-1；

步骤1：将步骤0得到的N-1个原始差值数据d[i]分别按照下式进行变换，得到N-1个差值数据Data[i]，变换公式为 $\left\{\begin{array}{c}\mathrm{Data}\left[i\right]=2*d\left[i\right],d\left[i\right]\&GreaterEqual;0\\ \mathrm{Data}\left[i\right]=-2*d\left[i\right]-1,d\left[i\right]<0\end{array}\right.,$ 其中，N为自然数，i＝1，2，3……N-1；

步骤2：初始化数据位数D为1，令i＝1；

步骤3：将当前差值数据Data[i]作为被除数，将2^D作为除数，得到当前差值数据Data[i]的商Q和余数R；

步骤4：对余数R进行定长编码，对商Q进行变长编码，得到当前差值数据Data[i]的商余编码；

步骤5：令数据位数D等于当前差值数据Data[i]的位数，即用当前差值数据Data[i]的位数作为下一个差值数据Data[i+1]的位数；

步骤6：判断是否还有下一个未编码的差值数据，如果有，则令i＝i+1，跳转步骤3继续编码，否则，编码完成，得到N-1个差值数据的商余编码。

进一步的，所述步骤4中对商Q进行变长编码采用Huffman编码方法。

附图说明

图1是无线传感数据的差值概率分布，其中，横坐标表示无线传感数据的差值，纵坐标表示相应差值的数据个数。

图2是本发明的工作流程图。

图3是验证实验中的三组测试数据的分布规律。

图4是本发明与其他两种编码算法对不同类型的传感数据的压缩率比较结果，其中，横坐标表示三种算法分别针对3组数据的压缩结果，纵坐标表示压缩率。

具体实施方法

本发明将无线传感节点感知数据分为慢变数据和非慢变数据两类。其中，慢变数据是指传感节点感知数据的差值序列的标准差小于等于3的数据，慢变数据的波动程度较小；慢变数据之外的其他传感节点感知数据均为非慢变数据，非慢变数据的波动程度很大。

传感节点感知数据的概率分布特点分析如下：

传感节点要采集的数据是一个随时间而变化的函数。针对每个具体的时刻，由于各种干扰及节点采集精度等因素的影响，实际采集到的数据与真实值之间有微小的误差。显然，传感器采集到的数据d_i与真正的被采集量m_i有d_i＝m_i+ε_i，ε_i～N(0，σ_i ²)的关系，其中ε_i为误差，σ_i ²为方差。

对于某个具体的时刻，节点采集的数据是一个随机变量X，它服从均值为m_i，方差为σ²的正态分布，即X～N(m_i，σ²)，其中m_i就是t_i时刻的被采集量。

对于不同的时刻来说，所采集的数据均服从正态分布。显而易见，影响采集数据精度的各种干扰因素的概率分布是相互独立的。

设t₁和t₂是两个连续的时刻，则对于某个具体的传感节点来说，传感节点采集到的两个数据X_t1和X_t2均服从正态分布。即：X_t1～N(m_t1，σ_t1 ²)，X_t2～N(m_t2，σ_t2 ²)。

由于干扰因素的概率分布是相互独立的，根据正态分布的性质，可知：X_t2-X_t1～N(m_t2-m_t1，σ_t2 ²-σ_t1 ²)，设m_t2＝m_t1+Δt，σ_tt ²＝σ_t2 ²-σ_t1 ²，则求差变换后的数据X_t2-X_t1～N(Δt，σ_tt ²)。

显然，求差变换后的数据将依然服从正态分布。尤其是，当传感数据符合慢变数据的定义时，Δt≈0，则X_t2-X_t1～N(0，σ_tt ²)。即慢变数据中前后两个数据的差值服从以0为中心的正态分布。

为验证以上结论，发明人以Intel Berkeley实验室(http://www.intel-research.net/berkeley)于2004年2月28日至4月5日间采集的传感器网络实验结果数据(下载地址：http://db.csail.mit.edu/labdata/data.txt.gz)进行验证。本发明选择了1号节点从2004年3月1日19时至3月2日7时的温度数据，对其前后数据依次求差后进行了概率分析，结果显示如图1所示，显然，这段温度数据之间的差值比较完美地服从了以0为中心的正态分布，验证了申请人的分析。

综上，本发明的理论依据如下：

根据契比雪夫不等式P(/X-μ/＜3σ)＝99.7％，其中μ指均值，σ指标准差。可知，传感器采集到的数据绝大多数分布在均值附近。因此X_t2-X_t1的值将绝大部分分布在±3σ_tt之内。由于σ_tt只与节点采集精度相关，是一个比较小的量，这为采用差值编码实现数据压缩提供了便利。

由图1可知，只要根据正态分布的性质，对越靠近0值的数据编以越短的编码，对越偏离0值的数据编以越长的编码，就可以很好的实现无损压缩，这也就是S-Huffman编码算法针对慢变数据能够取得较好压缩率的原因。而当原始数据不再符合慢变数据的假设时，求差变换的结果将不再符合以0为中心的正态分布，S-Huffman算法的压缩效果将迅速下降。但当输入数据仍然有一定的相关度时，求差变换的结果将仍然基本符合以差值为中心的正态分布，这时采用自适应Huffman变换将取得较好的压缩效果。

发明人对用于传感节点感知数据的编码方法进行研究的基本思路如下：

首先，本发明中将编码有效位定义为：设有一N位定长编码，将其高K位(K＜N)去掉后，剩下的N-K位定长编码表示的数字不变，则称该编码的高K位为无效位，并称将所有无效位去掉后剩下的L(L＝N-K)位为N位定长编码的有效位。

通过分析二进制数据的特点发现，假如只计算有效位的话，定长编码比变长编码更紧凑。因为不管哪种变长编码方法，都是在确保一些编码变短(一般为出现概率较高的数据)的同时，一定是以另一些编码变长(一般为出现概率较低的数据)为代价的。

例如：二进制数0、1、2、3，假如用定长编码，需要用两位二进制数00、01、10、11表示。但是，对于数据0和1来说，用1位二进制数就可以表示其值，数据0和1的编码为00和01，它们的有效位只有末位1位。显然，如果只写出定长编码的有效位，则以上4个数字可以表示为0、1、10、11。而如果用变长编码，为保证其为唯一可译码，如使用Huffman编码就需要编为类似0，10，110，111这样的形式。显然，如果只考虑有效位，定长编码比变长编码更紧凑。

然而，上述只考虑有效位的定长编码在不事先给出编码长度的情况下，是无法正确解码的，因为它不是唯一可译码。反过来说，假如事先知道编码长度，则可以正确解码。由于求差变换的结果均服从正态分布，根据契比雪夫不等式(P(/X-μ/＜3σ)＝99.7％)，绝大多数数据将分布在均值附近。因此，在一组数据中的前后数据的位数偏差，绝大多数在3σ之内，那么，我们就可以用前一个数据的位数推断当前数据的位数，并根据推断的位数对当前数据进行定长编码。

例如：假设一段待编码的数据由2，1，0，1四个数据构成，根据第一个数据2，我们知道其二进制数据的有效位为2位，则推断下一个数据的有效位也为2位，那么我们就可采用二进制数“01”来编码数据1；然后根据1的有效位为1位，则推断下一个数据的有效位也为1位，就可以采用二进制数“0”编码第三个数据0；同理，根据0的有效位为1位推断下一个数据的有效位也为1位，可采用二进制数“1”来编码数据1；就可以得到这四个数字的编码为“100101”。显然，这样编码后的结果，要比采用基于唯一可译码的Huffman编码“11010010”要简短。

然而，对于上述的根据推断位数进行定长编码的方法，当后面数据的有效位大于前面数据的有效位时，当前数据的推断位数将小于其有效位的位数，这时编码就会存在问题。

例如：如果上一例的数据第四位是7而不是1，由于7的有效位至少为3位，而根据前一个数据0得到的推断位数仅1位，显然不可能只用1位二进制数表示7，上述的编码方法就不适用了。针对这种情况，我们提出了商-余表示法来解决这一问题。

本发明所述的商-余表示法，是指将原数据当成被除数，用除数、商和余数来表示原数据的方法。

有了商-余表示法，我们可以将上述的根据推断位数进行定长编码的方法做一些改进来解决上述问题。在需要压缩的一组数据中，将当前数据作为被除数，用前一个数据的位数作为该数据的推断位数D，以2^D作为除数，计算商Q和余数R。由于除数是根据当前数据的前一个数的位数计算得到的，因此不需要传输，仅用商和余数就可以表示该数。由于余数不可能大于除数，因此其位数也不可能大于除数的位数，因此可以用与除数位数相同的定长编码来表示余数。而商有可能大于除数，因此其位数不定，就只能用变长编码来表示。采用商-余表示法和基于上下文的除数推断法后，其编码后的长度将比直接对原数据编码的长度更短，并且成为唯一可译码，这就是基于上下文自适应商余编码的原理。

例如：数据7用其前一个数据0的位数作为其推断位数D＝1位，以2^D＝2作为除数，则数据7可以表示为(2，1，3)，其中2为除数，余数为1，商为3。由于除数(即2^D)是根据当前数据的前一个数的位数D计算得到的，因此除数(即2^D＝2)不需要传输，仅用商和余数就可以表示该数，数据7采用商-余表示法为(1，3)。余数1用一位二进制定长编码表示为“1”，将商3采用Huffman编码(变长编码方法)表示为“111”，则合在一起为“1111”，共4位。而原数据7直接用Huffman编码后的结果为“111001”，共6位，采用S-Huffman编码也有类似的结果。显然，采用商-余表示法结合基于上下文的除数推断后，编码位数变得更短了。

参照图2，本发明的用于无线传感节点感知数据的上下文自适应商余编码方法，具体包括以下步骤：

步骤0：对需要编码的N个传感数据Gandata[1]，Gandata[2]，Gandata[3]，……，Gandata[N]按照d[i]＝Gandata[i+1]-Gandata[i]依次进行求差，得到N-1个原始差值数据d[1]，d[2]，d[3]……d[i]……d[N-1]，其中，N为自然数，i＝1，2，3……N-1；

步骤1：将步骤0得到的N-1个原始差值数据d[i]分别按照下式进行变换，得到N-1个差值数据Data[i]，变换公式为 $\left\{\begin{array}{c}\mathrm{Data}\left[i\right]=2*d\left[i\right],d\left[i\right]\&GreaterEqual;0\\ \mathrm{Data}\left[i\right]=-2*d\left[i\right]-1,d\left[i\right]<0\end{array}\right.,$ 其中，N为自然数，i＝1，2，3……N-1；

步骤2：初始化数据位数D为1，令i＝1；

步骤3：将当前差值数据Data[i]作为被除数，将2^D作为除数，得到当前差值数据Data[i]的商Q和余数R；

步骤4：对余数R进行定长编码，对商Q进行变长编码，得到当前差值数据Data[i]的商余编码；

步骤5：令数据位数D等于当前差值数据Data[i]的位数，即用当前差值数据Data[i]的位数作为下一个差值数据Data[i+1]的位数；

步骤6：判断是否还有下一个未编码的差值数据，如果有，则令i＝i+1，跳转步骤3继续编码，否则，编码完成，得到N-1个差值数据的商余编码。

以下结合附表对本发明的相关内容做进一步详细分析。

算法的类C伪码描述如表1所示。

表1：上下文自适应商余编码(CAQR)的伪码描述

对于本发明的步骤1，将原始差值数据d[i]变换为差值数据Data[i]，是为了避免求商和余数过程中负数造成的编码错误，变换公式为 $\left\{\begin{array}{c}\mathrm{Data}\left[i\right]=2*d\left[i\right],d\left[i\right]\&GreaterEqual;0\\ \mathrm{Data}\left[i\right]=-2*d\left[i\right]-1,d\left[i\right]<0\end{array}\right.,$ 变换后负数变为奇数，正数变为偶数，解码时就可以根据奇偶可解出原来的正负数。

对于步骤3，当前差值数据Data[i]通过移位操作计算商Q和余数R。表1中，＞＞D表示右移D位，相当于除以2^D后只保留整数部分；＜＜D表示左移D位，相当于乘以2^D。由于左移和右移操作均为基本操作，可确保计算商和余数的运算能够在传感节点中平滑运行，因此实现该方法所需指令数很少。

对于步骤4，计算出商和余数之后，就进入编码过程。对余数R采用定长编码；对商Q采用变长编码，可选择Huffman编码方法对商Q进行编码。

如表2所示，发明人应用本发明对Intel Berkeley实验室的一组传感数据进行编码，得到该组传感数据的商余编码结果：

表2 Intel Berkeley实验室的一组传感数据编码结果

	传感数据	差值数据	商余编码输出
				1	2187	2187	1111111110111111111111
2	2179	-8	1011111
				3	2184	5	100111
4	2189	5	100111
				5	2197	8	1011111
6	2203	6	100111
				7	2218	15	1011111
8	2221	3	01111
				9	2225	4	100111
10	2225	0	00
				11	2227	2	01111
12	2235	8	1011111
				13	2241	6	100111
14	2247	6	100111
				15	2257	10	1011111
16	2260	3	01111

为验证本发明的编码方法的有效性，以下采用三组实际数据对本发明的编码方法进行实验验证，并结合此实施例对本发明的性能进行具体分析说明，需要说明的是本发明不限此实施例。

为验证本发明的有效性，我们采用实际数据对本发明以及其他两种传统方法进行了对比测试。测试数据1和测试数据2来自Intel Berkeley Research lab在2004年2月28日至4月5日间的传感器网络实验结果，测试数据3来自NWU-NISL lab在含光门土遗址保护项目中的振动数据，图3为该三组测试数据的分布规律，该三组测试数据的差值的标准差分别为：σ1＝1.61；σ2＝11.06；σ3＝247.53。可以看出，测试用的三组数据中，测试数据1符合慢变数据的定义；测试数据2基本符合慢变数据的定义，而测试数据3则完全不符合慢变数据的定义。

参加对比测试的算法包括本发明的CAQR算法、S-Huffman算法及ND-Encoding算法。为确保对比测试的准确性，该实验在编码前只对传感节点感知数据进行了求差变换，与S-Huffman和ND-Encoding算法所做一样，压缩率的计算公式也与S-Huffman算法的一样，如下式所示：

$\mathrm{comp}\_\mathrm{ratio}=100\&CenterDot;(1-\frac{\mathrm{comp}\_\mathrm{size}}{\mathrm{orig}\_\mathrm{size}})$

其中，comp_ratio表示压缩率，comp_size表示压缩编码后的数据总长度，orig_size表示原始数据的总长度。

测试结果如图4所示，横坐标表示三种算法针对3组数据的压缩结果，纵坐标表示压缩率。从图4可以得出以下结论：

(1)随着输入数据波动加大，三种编码方法的压缩率均在下降；

(2)当输入数据为慢变数据时，三种编码方法的压缩效果相差不大，其中ND-Encoding算法有最好的压缩效果，本发明的CAQR算法较ND-Encoding算法稍差一点。

(3)当输入数据不再符合慢变规律时，ND-Encoding算法的压缩效果急剧下降，但本发明的CAQR算法却仍有较好的表现，有最好的压缩效果。

本发明的CAQR算法在各种情况下均有不错的压缩效果。以下结合此实施例对本发明的性能进行具体分析说明：

(1)算法的压缩率分析

由于本发明的编码是上下文自适应的方法，因此每个数据的最终编码会受到输入数据概率分布的影响。假如输入数据均按最佳状况排列的话，即完美地服从以0为中心的对称的正态分布，本发明的方法能够得到最优编码，本发明的CAQR算法与S-Huffman、ND-Encoding算法的最佳编码长度对比如表3所示。

表3三种编码算法的最佳编码长度对比

数据	CAQR	ND-Encoding	S-Huffman
				0	2	2	2
-1	2	3	4
				1	3	3	4
-2	3	4	5
				2	4	4	5
-3	4	4	5
				3	4	4	5
-4	4	5	6
				4	5	5	6
...	...	...	...
				127	8	16	12
...	...	...	...
				16383	15	30	26

从表3可以看出，如果仅仅比较最佳编码，本发明的CAQR算法几乎在各种数据下都比另外两种算法更优，尤其是当输入数据的数据比较大时，CAQR算法的优势非常明显。因此，本发明才可能在上述的实际测试中取得很好的效果。

但是，由于实际数据的排列不可能确保编码算法总能取得最优编码，因此对于实际数据的编码压缩效果很可能会有所下降。但从图4的测试结果来看，这种下降也是比较轻微的，针对各种数据，它依然可以保持较好的压缩效果。

(2)算法的运算复杂度分析

从表1可以看出，CAQR算法的主程序对每个输入数据需要1个判断、2个移位、1个加法、2个赋值、1条插入语句及1个按位取反或移位操作，共需约11条语句。

对下一个数据的推断位数D所需的更新语句同样是由一系列判断语句构成，最多为12个判断语句加一个赋值语句，共需约13条语句。

以上语句中，除了插入语句比较复杂，需要2到4条基本指令才能实现，其余语句均为基本语句，可在一个指令周期内完成。

因此，完成本发明的编码方法所需的基本语句数约为：11+26+13＝50。由于这些语句均是传感器节点CPU所支持的基本语句，所以本发明的编码方法完全可以平滑地运行于传感节点之中，所需指令数很少。

(3)算法的空间占用分析

从表1可以看出，本发明只需个别临时变量用于存储中间数据，不需要耗费很大的存储空间，因此，符合无线传感节点的空间占用要求。

Claims (2)

1.一种用于无线传感节点感知数据的上下文自适应商余编码方法，其特征在于，具体按以下步骤进行：

步骤0：对需要编码的N个传感数据Gandata[1]，Gandata[2]，Gandata[3]，……，Gandata[N]按照d[i]＝Gandata[i+1]-Gandata[i]依次进行求差，得到N-1个原始差值数据d[1]，d[2]，d[3]……d[i]……d[N-1]，其中，N为自然数，i＝1，2，3……N-1；

步骤1：将步骤0得到的N-1个原始差值数据d[i]分别按照下式进行变换，得到N-1个差值数据Data[i]，变换公式为 $\left\{\begin{array}{c}\mathrm{Data}\left[i\right]=2*d\left[i\right],d\left[i\right]\&GreaterEqual;0\\ \mathrm{Data}\left[i\right]=-2*d\left[i\right]-1,d\left[i\right]<0\end{array}\right.,$ 其中，N为自然数，i＝1，2，3……N-1；

步骤2：初始化数据位数D为1，令i＝1；

步骤3：将当前差值数据Data[i]作为被除数，将2^D作为除数，得到当前差值数据Data[i]的商Q和余数R；

步骤4：对余数R进行定长编码，对商Q进行变长编码，得到当前差值数据Data[i]的商余编码；

步骤5：令数据位数D等于当前差值数据Data[i]的位数，即用当前差值数据Data[i]的位数作为下一个差值数据Data[i+1]的位数；

步骤6：判断是否还有下一个未编码的差值数据，如果有，则令i＝i+1，跳转步骤3继续编码，否则，编码完成，得到N-1个差值数据的商余编码。

2.如权利要求1所述的方法，其特征在于，所述步骤4中对商Q进行变长编码采用Huffman编码方法。

Images