,

(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)

无线传感器网络常应用于环境监测领域，它利用其自组织网络、自主采集和发送数据等特性帮助科研人员收集宝贵的数据资料.目前传感器节点一直采用电池供电，由于其部署在人为不可达的地方，当节点能量耗尽时使用常规方式更换电池是行不通的[1-3].因此，如何有效的延长节点工作寿命是无线传感器网络研究中必须面对的一个难题.无线传感器节点大约80%的能量消耗在数据发送、接收和空闲三个状态[4]，因而有效减少节点在这三个状态的能量消耗成为传感器网络研究的重点之一.

针对空闲状态耗能问题，常用的方法是在MAC层协议中采用睡眠/唤醒机制.针对感知数据(如温度数据、湿度数据)冗余性较高的特点，主要采用数据压缩等技术减少传输数据量.无线传感器网络中的数据压缩算法分无损压缩算法和有损压缩算法.无损压缩算法即保存了数据的完整性也达到了减少传输量的目的，不足之处是其存在压缩上界.区别于无损压缩，有损压缩算法允许数据存在一定的误差，但可以达到极高的压缩率.注意到感知数据是每隔单位时间间隔采集，那么每个感知数据都和一个唯一的时间相对应.主要贡献在于：考虑感知数据的时间相关性，依据分段表示法的思想，提出一种最长直线近似表示的有损压缩算法(The longest straight line approximation, LSLA)，并结合经典Huffman编码算法，从而最大限度地减少感知数据冗余度.

1 相关研究

传感器节点受能量有限和内存较小的限制，基于无线传感器网络的压缩算法必须尽可能的简单，且压缩性能要好.目前，无线传感器网络中的有损压缩算法和无损压缩算法均不是很多.其中，有代表性的有损压缩算法是分段表示法，无损压缩算法则是Huffman编码.

分段表示法是用多条直线段近似表示数据的一种方法，其算法简单、计算速度快和压缩率高.按照分段的方式不同，分段表示法可以分为分段近似拟合(Piecewise aggregate approximation, PAA)[5]、分段线性表示(Piecewise linear representation, PLR)[6]和分段常量表示(Piecewise constant approximation, PCA)[7].其中PLR是目前应用在无线传感器网络中比较多的算法，其思想是用多条相邻的直线段拟合原数据序列.Line算法[8]是运用在无线传感器网络中的一种PLR算法，该算法主要用于压缩变化较慢的感知数据.ISDT(Improved swing door trending)算法[9]是对原SDT算法的一种改进，其思想是门限值依据实际数据自适应变化，从而得到更高的压缩率.FFP(Farthest feasible point)算法[10]是针对SDT算法的另一种改进方式，该算法是寻找最远点使线性分段最大化，从而提高压缩率.

Huffman编码是1952年被提出的一种基于统计的编码，它的主要思想是根据字符出现的概率来构造最优Huffman树.S-Huffman编码是由Francsco Marcelloni等提出的一种专用于无线传感器节点的数据压缩算法.其算法思想：依次计算前后相邻的感知数据之间的差值，然后再根据S-Huffman编码表对差值数据进行编码[11-12].Tharini等在文献[13]提出一种基于二叉树改进的自适应Huffman编码，其对不同的数据具有较好的压缩性能.

2 改进压缩算法描述

2.1 模型建立

传感器节点采集数据是每隔单位时间进行采集的，那么可知每个感知数据按照采集时间依次排列.因此，我们可以假设给采集到的感知数据依次编号为0,1,2,…,n.并定义一组带有编号的数据为时间序列.

定义1(时间序列) 设时间序列L=<(0,P0),(1,P1),…,(n,Pn)>，其中Pn表示编号n所对应的感知数据值.

这样我们可以将时间序列L表示在一个二维坐标系中，其中x轴表示编号，y轴表示感知数据值.如图1所示，图1是以编号为0的数据点作为原点.

图1 感知数据二维模型图

2.2 LSLA算法描述

首先需定义变量：Pt表示原始数据值；E表示压缩允许的误差值；Pt_up表示数据值Pt的误差上界；Pt_down表示数据值Pt的误差下界；Pt′表示数据值Pt的近似值，Pt′∈[Pt_down，Pt_up]；Ps表示每一轮压缩开始的起点值.

LSLA算法的基本思想：每轮压缩都寻求最长的直线段趋势，并只保留直线段的端点，剔除端点间的其它数据点.其中，在寻求最长直线段的过程中，直线必须依次经过数据点Pt的取值区间.从而可知：直线与取值区间相交的值就是在解码时得到的原始数据值Pt的近似值Pt′.在图1中每个数据点对应的垂线段就是该数据点的近似取值区间[Pt-E,Pt+E](或[Pt_down,Pt_up]).另外，图1中依次经过P0,P1,P2,P3,P4的取值区间的直线就是在第一轮压缩中所能得到的最长直线段趋势.

LSLA算法获得最长直线趋势的算法流程，如图2所示.

在图2中，Sent_ID用于保存压缩后剩余数据编号的集合，初始时Sent_ID={0}.Sent_Data用于保存压缩后剩余数据值，初始时Sent_Data={P0}.初始时起始点Ps=P0，s=0.

图2 LSLA算法流程图

图2中出现的Kt_up，Kt_down表示加入新数据后需要计算的新数据和起始点间的斜率，如图3中所示.Kup_min表示在每轮压缩过程中寻求最长直线时所有Kt_up的最小值.Kdown_max表示在每轮压缩过程中寻求最长直线时所有Kt_down的最大值.

图3 加入新数据Pt斜率示意图

基于分段表示的无线传感器网络数据压缩算法的特点是在压缩过程中不仅要保存感知数据值，同时还需保存该数据值所对应的编号值，编号值的存贮方式与感知数据值相同，即占用相同的字节数.但实际上编号值存储时所需的内存空间一般小于一个字节，如果采用和感知数据值同样的字节数表示，那么不仅浪费了节点宝贵的内存空间，同时在发送这些冗余数据时也会消耗节点的能量.从尽可能减少数据冗余度考虑，在下文中对集合Sent_ID和Sent_Data中的数据再进行一种基于S-Huffman改进的无损压缩算法.

2.3 基于S-Huffman改进的无损压缩算法

原始的S-Huffman编码表共有15个编码项，考虑传感器节点存储整个编码表需要占用较大的内存空间，并且在S-Huffman编码表中当后缀位数超过8位时，实际上是起不到压缩作用.因此，需对S-Huffman编码表作适当的改进，如表1所示.

表1 改进后S-Huffman编码表

改进后的S-Huffman编码表只有10个项，与原表相比大大减少了内存占用空间.改进后的编码表中没有表示差值为0的项，这是因为相邻数据间差值为0的概率几乎为0，因此将最短的前缀00用来表示定长编码，即其后缀为16位的数据原值.

改进型S-Huffman算法编码过程描述如下：首先，将Sent_ID和Sent_Data中的第一个数据直接保存，然后依次计算后续数据与前一个数据的差值，如果差值在表1的“取值范围”中，则按相应的前缀和后缀进行编码；如果计算得到的差值不在表1的“取值范围”中，则用前缀“00”加数据原值来表示.

3 实验分析

为分析所提出算法的压缩性能，预先通过TelosB传感器节点每隔单位时间采集了若干温度数据，从中选取了100个连续的数据作为实验输入对象(注：实验温度数据值为传感器节点采集的原始数据值，实际温度值还需通过相应的公式转换).如图4所示，纵坐标是十进制表示的温度数据值，横坐标表示单位时间.

图4 实验温度数据

实验过程是在同一台计算机上用C++语言模拟LSLA算法和文献[7]中的FFP算法，以及LSLA+S-Huffman算法和FFP+S-Huffman算法，并分别用图4中的温度数据作为输入值得出的结论.两组算法的性能主要通过压缩率来比较，这里定义：

压缩率=(1-剩余比特数/原始比特数)×100%

(1)

表2给出了各组算法在不同压缩误差E值下的压缩率，从实验结果可看出：

1) 在压缩误差E取值较小时，FFP算法和LSLA算法可能出现压缩率为负数.这是因为分段表示法在压缩过程中需同时存储数据的编号值，因此当压缩率较低时，就可能产生负压缩的效果.但从表2可看出采用组合算法后，即FFP+S-Huffman算法和LSLA+S-Huffman算法，有效的避免了这个问题，并且压缩率均在50%以上.

2) 随着误差E值的逐渐增加，LSLA算法比FFP算法在压缩率上具有明显优势，且压缩率增长的更快.

3) 分别对比单个算法LSLA和LSLA结合改进的S-Huffman算法，改进后算法压缩率比单个算法压缩率更高，能更有效地减少了数据冗余度.

表2 算法压缩率对比表

4 结 论

实验分析，LSLA算法结合改进的S-Huffman算法能够最大化的提高数据的压缩率，从而更有效的减少数据冗余，减少了网络中的通信量最终达到节省能量的目的.另外，LSLA算法和S-Huffman算法的时空复杂度均为O(n)，算法实现简单，满足无线传感器网络低时空复杂度的要求.模拟实验结果充分显示了笔者提出的改进算法的有效性.在同一片区域中，多个节点采集的数据值可能非常相近，因此在将来研究中，可以考虑采用分簇的方式，并对簇头节点收集的数据进行压缩.

参考文献：

[1] 俞立,王铭,董奇芬,等.基于无线传感网的目标跟踪算法及实验系统设计[J].浙江工业大学学报，2012，40(6):649-652.

[2] 蒋融融,张美玉.TinyILKH：一种改进的WSN逻辑层次组密钥管理方案[J].浙江工业大学学报,2012,40(3):331-335.

[3] 陈迪,孟利民.无线Ad Hoc网络中的多目标规划路由算法研究[J].浙江工业大学学报,2009,37(4):441-444.

[4] KIMURA N, LATIFI S. A survey on data compression in wireless sensor networks[C]//Inf-ormation Technology: Coding and Computing. Las Vegas: IEEE,2005:8-13.

[5] The 5thIndustrial Conference on Data Mining ICDM. Advances in data mining[C]. Leipzing:Elsevier,2005.

[6] KEOGH E, CHU S, HART D, et al. An online alg-orithm for segmenting time series[C]//Industrial Conference on Data Mining 2001.Leipzing:IEEE,2001:289-296.

[7] OLSTON C, JIAN J, WIDOM J. Adaptive filters for continuous queries over distributed data streams[C]//Proceedings of the 2003 ACM SIGMOD International Conference on Managem-ent of Data. California: ACM,2003:563-574.

[8] LI Y, LOKE S W, RAMAKRISHNA M V. Energy-saving data approximation for data and queries in sensor networks[C]//ITS Telecommunications Proceedings. Chengdu:IEEE,2006:782-785.

[9] 王举，房鼎益，陈晓江,等.文物监测中无线传感器网络数据压缩算法[J].西安电子科技大学报:自然科学版，2012,39(1):157-162.

[10] CHEN Gang, LI Li. An optimized algorithm for lossy compression of real-time data[C]//Intellig-ent Computing and Intelligent Systems (ICIS). Xiamen:IEEE,2010:187-191.

[11] 任学军，房鼎益.一种适合无线传感器网络的混合编码数据压缩算法[J].小型微型计算机系统，2011，32(6):1055-1058.

[12] MARCELLONI F, VECCHIO M, A simple algorithm for data compression in wireless sensor networks[J]. IEEE Communications Letters,2008,12(6):411-413.

[13] THARINI C, VANAJARANJAN P. Design of modified adaptive huffman data compression algorithm for wireless sensor network[J]. Journal of Computer Science,2009,5(6):466-470.