| 标题 | 基于生成树的WSN溯源数据压缩方法 |
| 范文 | 毛健+王昌达 摘 要：在无线传感器网络（WSN）中溯源数据（Provenance）记录了一个数据从产生至被传输到基站（BS）途经的所有节点以及在这些节点上对数据的操作。提出一种基于生成树的溯源数据压缩方法，其基本思想是在字典中存放WSN拓扑图的生成树并对其建立索引，在数据包传输过程中传输的是生成树的索引而不是完整的生成树。仿真实验结果表明，在大规模稀疏WSN中采用该方法，溯源数据在文件大小和传输能耗等方面都优于已知的其它溯源数据编码技术，而且该方法对线性溯源数据和聚合溯源数据采用完全相同的处理方式，算法实现简单、一致性好。 关键词：生成树；溯源数据；数据压缩 DOIDOI：10.11907/rjdk.171217 中图分类号：TP301 文献标识码：A 文章编号：1672-7800（2017）007-0014-04 0 引言 WSN由具有一定通信能力与数据处理能力的传感器节点组成，是一种能够根据环境自主完成指定任务的智能自治网络系统[1，2]。一般地，WSN节点的能量主要消耗在数据传输过程中，因此为了减少远距离传输造成的能量消耗和信号衰减，WSN通常采用多跳的方式与BS通信[3]，即通过相邻节点的转发将数据传输至BS。传感器节点的多样性也导致对采集数据的可信性评估极为困难[4]。在一些关键应用中，如工业控制等领域，因为采用可信度低的数据决策而造成重大损失的已有先例[5]。一般地，在WSN中使用溯源数据[6]记录数据从源节点至BS途经的所有节点以及在这些节点上对数据的操作。溯源数据是在WSN中实施数据可信性评估的重要依据之一。 最简单的溯源数据模型是在数据包中逐次记录数据传输途经节点的ID，但这种溯源数据会随着数据传输路径的延长迅速膨胀，并最终导致数据量过载问题。因此相继提出了一些轻量级的溯源数据方法[7，8]。因为受信息熵极限的制约，轻量级的方法并未从根本上解决溯源数据随数据传输路径增长而快速膨胀的问题。 鉴于此，本文提出一种基于生成树编码的溯源数据压缩方法（Tree Based Provenance Encoding Scheme，TPE），TPE的应用对象是大规模稀疏WSN。TPE的基本思想是在基于字典压缩方法的基础上，将编码对象由字符串转变为WSN拓扑图的生成树并建立生成树的字典，在溯源数据传输过程中传输的是生成树在字典中的索引而不是完整的生成树。基于TinyOS的仿真实验表明，在大规模稀疏WSN中，相较于其它已知的溯源数据编码技术，相同条件下采用本文TPE获得的溯源数据编码平均长度最短，因此在WSN中对能量和传输带宽的节约效果显著。本文主要贡献在于： （1）针对大规模稀疏WSN，提出了一种基于其拓扑图生成树的溯源数据无损压缩方法TPE，在已知的同类方法中，具有最高的平均压缩比。 （2）TPE对线性溯源数据和聚合溯源数据，采用相同的编码方法，算法的通用性、一致性好。 （3）通过基于TinyOS的仿真实验，实证了TPE的各项主要性能指标。 1 溯源数据模型 在WSN中，节点按照功能可划分为源节点、转发节点和汇聚节点。其中：源节点采集数据并将其封装在数据包中；转发节点沿着趋向于BS的方向将来自源节点的数据包转发至相邻节点；汇聚节点将来自不同路径上的多个数据包整合成一个较大的数据包并发往BS。传输由若干个较小数据包整合而成的较大数据包比独立传输这些较小的数据包更节省能量，因此WSN的传输协议大多支持汇聚操作。 溯源数据有两种基本类型：①线性溯源数据，如图1（a）所示，其中数据源节点n4产生数据包并通过转发节点传送至BS（节点n1），可用 因为从树的叶子节点到其根节点的路径是唯一的，所以给定一棵生成树以及其上的某个叶子节点，即可确定一个从该叶子节点到BS的线性溯源数据；而给定一棵树以及其上的多个叶子节点，即可确定一个从这些叶子节点到BS的聚合溯源数据。例如在图1（b）的生成树中，若数据源为n7，则线性溯源数据为 2 溯源数据编码与解码算法 因为WSN中每个节点都存有完整的生成树字典，所以溯源数据只需记录：①某棵生成树的索引（treeID）；②数据传输所在当前节点的ID （currentID）；③一个或多个数据源节点的ID （sourcetID）。TPE方法中溯源数据的表示形式为： 因为TPE的解码只涉及对树的查找操作，而编码在每个数据包途经的每个节点上均需要先解码、再编码，所以先讨论TPE的解码算法。 2.1 解码 当BS收到某数据源节点传来的数据包时，先根据其携带的treeID在字典中查找对应的生成树，然后在找到的生成树上根据sourcetID的位置即可求出数据传输的路径，即从sourcetID所在的叶子节点至树的根節点（BS）所确定的唯一路径。 若溯源数据中只含有一个sourcetID，则解码的结果是一个线性溯源数据；若溯源数据中含有多个sourcetID，则解码的结果是一个聚合溯源数据。溯源数据的解码算法如下： Algorithm 1. Provenance Decoding Input：pk Output：A（P） A（P）=0 I=pk .treeID FOR t=0；t≤m-1；t++ IF in A（TI），a[pk .currentID，t] ！= 0 pk .currentID.nextID（ ）=a[pk .currentID，t] END IF END FOR WHILE current node is not source node and receives a packet pk THEN IF pk .currentID.nextID（ ）=current node id THEN FOR all pk .sourceID traverse A（TI） front= pi .sourceID next= pi .sourceID.nextID（ ） WHILE pi .currentID ！= next in A（P），a[front，next]=1 front=next，next=front.nextID（ ） END WHILE return A（P 1），A（P 2），…，A（P n） END FOR END IF A（P）=A（P 1）|| A（P 2）||…|| A（P n） END WHILE 2.2 编码 （1）源节点处的编码方法。当源节点ni产生一个新的数据包时，其溯源数据的生成树索引treeID为， sourceID和currentID的值都是ni。 （2）转发节点处的编码方法。当ni为转发节点时，在转发时溯源数据的sourceID不变，currentID更新为ni，然后根据以下方法更新treeID：设转发节点ni收到其上一跳节点传递的溯源数据Pj={treeID，nk，nj}，根据Algorithm 2，首先计算出Pj从数据源nj到ni的当前路径，并通过字典找出所有包含当前路径的生成树，具体方法是将表示当前数据路径的邻接矩阵和字典中所有生成树的矩阵A（T0），A（T1），…，A（Tk-1）依次作异或XOR运算，对于当前路径邻接矩阵内的非零元素位置，若XOR后得到的新矩阵A（TI）（0≤I≤k-1）中的对应位置的元素都等于0，那么I即为满足条件的生成树索引，即转发后的线性溯源数据为：pj'={I，ni，nj}。 （3）汇聚节点处的编码方法。当汇聚节点nr先后接收到来自源节点ns和nt的溯源数据ps和pt后，首先通过汇聚得到新的数据包及其上的溯源数据pr'；然后在nr上执行Algorithm 1分别求出从ns和nt至当前节点nr的路径，并通过生成树字典找出同时包含以上2条路径的生成树的索引，记为treeID'；最后将currentID更新为nr，将ns和nt作为新的sourceID。即经过汇聚节点的溯源数据为：pr'={treeID'，nr，ns，nt}。 Algorithm 2. Provenance Encoding Input：pi，pj Output：pk′ IF current node is source node THEN FOR any Provenance sourceID=source node id=currentID treeID = END FOR END IF ELSE IF a simple node nk receives pi THEN Pi′ .currentID= current node id Pi′ .treeID is tree′s index which includes current path current path is decoded using Algorithm 2 END IF IF an aggregated node nk receives pi and pj THEN package′s path is decoded using Algorithm 2 pi′s path=A（P 1）， pj′s path=A（P 2） pk′s path=A（P 1）|| A（P 2） pk′ .treeID is tree′s index which includes pk′s path pk′ .currentID=k pk′.sourceID=i，j END IF 3 仿真实验 仿真在Linux环境下使用TinyOS 2.1.2进行，共采用编号0～99的100个节点，WSN的跳数在2～10之间，其中编号为0的节点是BS，其它节点被随机地选为数据源节点或转发节点。数据采集的周期为2秒。 将TPE的主要性能与以下3种常见的溯源数据编码方法作对比。 （1）Bloom filter based provenance scheme （BFP） [7] ：在該方法中，溯源数据表示形式为pd=vd，v1，v2，v3，其中v1、v2和v3分别表示源节点vd发出的数据在传输过程中所经过的节点。溯源数据的存储采用布隆过滤器格式随数据包一同传输。若节点vd的ID用vidi表示，则其计算公式如下： 其中，seq表示数据包序列号，E是基于AES的分块加密函数。 （2）Generic secure provenance scheme （SPS） [9] ：在该方法中，溯源数据表示形式为pi=ni，hash（Di），Ci，其中hash（Di）表示数据Di的哈希值，Ci包含了由计算公式Sign（hash（ni，hash（Di）|| Ci-1））求得的一个带有签名的完整性校验和。 （3）MAC based provenance scheme （MP） [10] ：该方法溯源数据中记录的是数据包途经节点的ID以及为了确保数据完整性而根据节点ID计算出的消息验证码CBC-MAC。 3.1 性能指标 本文使用如下性能指标分析TPE压缩方法： 溯源数据的平均大小（Average Provenance Size，APS）：当BS接收到一个来自源节点ni的数据包时，通过其携带的treeID和sourceID可计算出数据的完整溯源路径。若treeID与sourceID的大小分别用streeID和ssourceID表示，则溯源数据的大小为： 可通过如下公式计算平均溯源数据的长度： 其中，PSi表示节点ni上产生的单个溯源数据的长度sprovenance，m表示数据包传输途经的节点数量。 3.2 仿真结果 图2分别显示了在SPS、MP、BFP和TPE等不同方法下，溯源数据的平均大小与数据包传输跳数的关系。在SPS与MP的方法中，数据包途经的各节点都是向溯源数据中添加自身的ID，因此溯源数据的平均大小与传输跳数的增加均呈线性增长，且SPS方法的增速明显更快。虽然BFP的平均溯源数据大小整体上也呈上升趋势，但是相比前两者明显平缓，尤其在数据包传输跳数增加较大的情况下增速较为平缓，因此在大规模WSN中BFP具有良好的适用性。而在TPE方法中，在聚合溯源数据中源节点个数有限的前提下，无论数据包传输的跳数如何增加，平均的溯源数据大小几乎保持不变，约占3 Byte。又因为WSN主要的能耗用于无线信号的发送与接收，所以与SPS、MP和BFP相比，TPE方法在能量節约方面表现出较好的性能。 本文采用PowerTOSSIMz进行能量仿真。若WSN中有n个节点n1，n2，n3，….，nn，则总能量消耗（Total energy consumption，TEC）计算公式如下： 其中，ECi表示节点ni消耗的能量，n表示WSN中节点的数量。 图3给出了WSN中在所有数据源节点都产生100个数据包的前提下，MP、BFP、TPE这3种不同方法的能量消耗，即数据包经过不同传输跳数时节点所消耗的总能量（TEC）。在相同环境下，MP与BFP的能耗明显大于TPE，而且随着网络规模的扩大、节点数量的增加，TPE在节约能耗方面的优势更加明显。 4 结语 本文针对大规模稀疏WSN，提出了一种基于生成树的溯源数据无损压缩方法TPE。TPE对线性溯源数据和聚合溯源数据都可采用相同的编码方法，且能确保溯源数据在途经节点数量增加的情况下变化较小。软件仿真和硬件实验均表明，与其它已知的同类溯源数据压缩方法相比，TPE在节约能量和降低无线带宽占用率等方面都具有显著优势。 参考文献： [1]LIU VINCENT，ZHAO Y.Wireless sensor networks for internet of things：a systematic review and classification[J].Information Technology Journal，2013，12（16）：3581-3585. [2]CHEN X Q，MAKKI K，YEN K.Sensor network security：a survey[J].IEEE Communications Surveys and Tutorials，2009，11（2）：52-73. [3]SUTAR U S，BODHE S K.Energy efficient topology control algorithm for multi-hop ad-hoc wireless sensor network[C].IEEE International Conference on Computer Science & Information Technology，2010：418-421. [4]FENG H L，LI G H，LU W W.Trust based secure in-network data processing schema in wireless sensor networks[J].Journal of Networks，2011，6（2）：295-302. [5]CHRISTIN D，MOGRE P S，HOLLICK M.Survey on wireless sensor network technologies for industrial automation：the security and quality of service perspectives[J].Future Internet，2010，2（2）：96-125. [6]BUNEMAN P，KHANNA S，TAN W C.Why and where：a characterization of data provenance[C].International Conference on Database Theory，2001：316-330. [7]SULTANA S，GHINITA G，BERTINO E.A lightweight secure scheme for detecting provenance forgery and packet dropattacks in wireless sensor networks[J].IEEE Transactions on Dependable & Secure Computing，2015，12（3）：256-269. [8]ALAM S M I，FAHMY S.Energy-efficient provenance transmission in large-scale wireless sensor networks[C].IEEE International Symposium on a World of Wireless，Lucca ，2011，1：1-6. [9]HASAN R，SION R，WINSLETT M.The case of the fake picasso：preventing history forgery with secure provenance[C].Usenix Conference on File and Storage Technologies，2009：1-14. [10]SULTANA S，GHINITA G，BERTINO E.A lightweight secure provenance scheme for wireless sensor networks[C].International Conference on Parallel and Distributed Systems，2012：101-108. |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。