基于生成树的WSN溯源数据压缩方法.docxVIP

基于生成树的WSN溯源数据压缩方法 　　摘 要：在无线传感器网络中溯源数据记录了一个数据从产生至被传输到基站途经的所有节点以及在这些节点上对数据的操作。提出一种基于生成树的溯源数据压缩方法，其基本思想是在字典中存放WSN拓扑图的生成树并对其建立索引，在数据包传输过程中传输的是生成树的索引而不是完整的生成树。仿真实验结果表明，在大规模稀疏WSN中采用该方法，溯源数据在文件大小和传输能耗等方面都优于已知的其它溯源数据编码技术，而且该方法对线性溯源数据和聚合溯源数据采用完全相同的处理方式，算法实现简单、一致性好。　　关键词：生成树；溯源数据；数据压缩　　DOIDOI：/　　中图分类号：TP301　　文献标识码：A 文章编号：1672--0014-04　　0 引言　　WSN由具有一定通信能力与数据处理能力的传感器节点组成，是一种能够根据环境自主完成指定任务的智能自治网络系统[1，2]。一般地，WSN节点的能量主要消耗在数据传输过程中，因此为了减少远距离传输造成的能量消耗和信号衰减，WSN通常采用多跳的方式与BS通信[3]，即通过相邻节点的转发将数据传输至BS。传感器节点的多样性也导致对采集数据的可信性评估极为困难[4]。在一些关键应用中，如工业控制等领域，因为采用可信度低的数据决策而造成重大损失的已有先例[5]。一般地，在WSN中使用溯源数据[6]记录数据从源节点至BS途经的所有节点以及在这些节点上对数据的操作。溯源数据是在WSN中实施数据可信性评估的重要依据之一。　　最简单的溯源数据模型是在数据包中逐次记录数据传输途经节点的ID，但这种溯源数据会随着数据传输路径的延长迅速膨胀，并最终导致数据量过载问题。因此相继提出了一些轻量级的溯源数据方法[7，8]。因为受信息熵极限的制约，轻量级的方法并未从根本上解决溯源数据随数据传输路径增长而快速膨胀的问题。　　鉴于此，本文提出一种基于生成树编码的溯源数据压缩方法，TPE的应用对象是大规模稀疏WSN。TPE的基本思想是在基于字典压缩方法的基础上，将编码对象由字符串转变为WSN拓扑图的生成树并建立生成树的字典，在溯源数据传输过程中传输的是生成树在字典中的索引而不是完整的生成树。基于TinyOS的仿真实验表明，在大规模稀疏WSN中，相较于其它已知的溯源数据编码技术，相同条件下采用本文TPE获得的溯源数据编码平均长度最短，因此在WSN中对能量和传输带宽的节约效果显著。本文主要贡献在于：　　针对大规模稀疏WSN，提出了一种基于其拓扑图生成树的溯源数据无损压缩方法TPE，在已知的同类方法中，具有最高的平均压缩比。　　TPE对线性溯源数据和聚合溯源数据，采用相同的编码方法，算法的通用性、一致性好。　　通过基于TinyOS的仿真实验，实证了TPE的各项主要性能指标。　　1 溯源数据模型　　在WSN中，节点按照功能可划分为源节点、转发节点和汇聚节点。其中：源节点采集数据并将其封装在数据包中；转发节点沿着趋向于BS的方向将来自源节点的数据包转发至相邻节点；汇聚节点将来自不同路径上的多个数据包整合成一个较大的数据包并发往BS。传输由若干个较小数据包整合而成的较大数据包比独立传输这些较小的数据包更节省能量，因此WSN的传输协议大多支持汇聚操作。　　溯源数据有两种基本类型：①线性溯源数据，如图1所示，其中数据源节点n4产生数据包并通过转发节点传送至BS，可用表示；②聚合溯源数据，如图1所示，其中汇聚节点n3将从n4和n5接收的数据整合成一个较大的数据包后通过转发节点传送至BS，可表示为：。其中，递归式表示树，a表示根节点；b表示其左孩子节点；c表示除左孩子外的其他孩子节点，c可以为空，也可以是1个或多个节点。　　因为从树的叶子节点到其根节点的路径是唯一的，所以给定一棵生成树以及其上的某个叶子节点，即可确定一个从该叶子节点到BS的线性溯源数据；而给定一棵树以及其上的多个叶子节点，即可确定一个从这些叶子节点到BS的聚合溯源数据。例如在图1的生成树中，若数据源为n7，则线性溯源数据为；若数据源为n7与n8，则聚合溯源数据为：。　　2 溯源数据编码与解码算法　　因为WSN中每个节点都存有完整的生成树字典，所以溯源数据只需记录：①某棵生成树的索引；②数据传输所在当前节点的ID ；③一个或多个数据源节点的ID 。TPE方法中溯源数据的表示形式为：　　因为TPE的解码只涉及对树的查找操作，而编码在每个数据包途经的每个节点上均需要先解码、再编码，所以先讨论TPE的解码算法。　　 解码　　当BS收到某数据源节点传来的数据包时，先根据其携带的treeID在字典中查找对应的生成树，然后在找到的生成树上根据sourcetID的位置即可求出数据传输的路径，即从sourcetID所在的叶子节点至树的根?点