WSN是由大量的微型传感器节点构成、用于采集物理世界中感知对象信息的无线网络^[1-2]。传感器节点一般分布在无人值守的监控区域，其主要目的是采集网络监控区域中的相关信息。因为部署WSN的环境较为复杂，并且网络中涉及到的传感器种类较多，所以用于关键决策的数据须经过基站(BS)的可信性评估。由于使用可信度低的数据进行决策而造成重大损失的情况，在工业控制等应用领域较为常见^[3]。除数据源本身外，数据传输过程也对其可信度有重要影响^[4-5]。在WSN中，Provenance记录一个数据从其产生到传输至BS所涉及的全部节点，以及在这些节点上对该数据实施的操作^[6-7]。因此随着一个数据传输路径长度的增长，其对应的Provenance的大小也会快速增长。由于WSN是一种资源受限网络，网络传输带宽以及数据包容量等资源受到限制，当数据传输路径较长时，一般无法传输完整的Provenance。为此，多种分段Provenance传输方法相继被提出，其中代表性有PPM(probabilistic packet marking)方法^[8]和PPF(probabilistic provenance flow)方法^[9]等。PPM方法由于是根据在当前节点上的抽签概率来决定是否将其ID写入Provenance，因此不具有压缩功能；而PPF方法运用整数的素因子分解具有唯一性这一性质，并基于PPM方法，依靠传输不大于当前节点ID的最大素数乘积及其偏移量来实现Provenance的压缩。PPM和PPF方法的主要不足在于Provenance的平均值较大、能耗较高。因此，上述方法难以适用于大规模的WSN中。

在当前较为常见的WSN分簇算法中，LEACH(low energy adaptive clustering hierarchy)^[15]具有自适应以及低功耗等特性。LEACH能够将网络的能耗平均分摊到各个节点，从而使得网络生命周期延长。另一种较为常见的能量高效的分簇算法是EEHC(energy efficient hierarchical clustering)^[11]。它是一种分布式多级分簇算法，并能通过均衡能量消耗类延长网络生命周期。

由于节点能耗、无线传输带宽和数据包大小的限制，一般传统的Provenance压缩传输算法不能直接应用在WSN中^[16]。但研究人员通过对这些方法进行简化，先后提出了一些轻量级的方法^[17-19]，以适应在WSN中资源受限的环境。但这些轻量级的算法为减少数据传输量，首先舍弃了Provenance节点之间的拓扑形态，所以在本质上这些轻量级方法都属于有损压缩算法。

鉴于此，多种无损压缩Provenance方法相继被提出。Wang等^[20]提出一种基于字典的无损Provenance压缩方法。在此方法中，首先将每个节点ID看作一个符号，将每条数据包传输路径看作由这些符号构成的字符串，然后对已经使用过的数据传输路径建立带有索引的字典。由此在Provenance的传输过程中，可以只传输数据路径在字典中的索引，而无须传输路径本身。在WSN拓扑结构相对稳定时，此方法可以获得极高的Provenance平均压缩比。但是，在WSN拓扑结构不稳定的情况下，路径字典可重用性较差，效率较低。

Hussain等^[3]设计了一种通过算术编码进行Provenance压缩的方法。该方法使用WSN中节点参与数据包传输的相关概率，通过算术编码来压缩Provenance。其优点是对WSN的拓扑结构不敏感；缺点是受数据路径熵值的限制，可以实现的Provenance平均压缩比不高。

在文献[3, 20]中，单个的数据包中记录的是完整的Provenance，当WSN规模较大时，这些方法难以适用。为了克服数据包过载问题，通常将Provenance进行分段传输。基于IP追踪技术^[21-22]，Savage等^[13]设计了一种通过概率抽签进行数据包标记的Provenance传输方法PPM。当数据包途经某个节点时，该方法利用概率抽签的方式决定是否将该节点的ID写入途经的数据包中。在BS端，需要积累一定数量来自相同路径的数据包才能够解码Provenance，这个数量与概率抽签的阈值相关，阈值越小所需数据包的数量越多。又因为PPM没有采用任何数据压缩的方法，所以能耗相对较高。

在PPM的基础上，Fahmy等^[14]提出了一种通过概率抽签对传输路径片段标记的Provenance传输方法PPF。此方法在使用概率抽签对传输路径片段进行标记的同时，运用整数素因子分解特性，利用传输不大于节点ID的最大素数之积以及偏移量之和的方式来达到压缩传输Provenance的效果。

PPM和PPF方法都较为有效地克服了大规模WSN中Provenance的数据量过载问题。PPF方法以较大的传输路径片断而非单一节点为编码对象，并且使用一定的压缩策略，因此与PPM方法相比，能耗更低。但这两种方法在全部Provenance片段到达之前，不能进行Provenance解码，因此部分数据包丢失后，会导致解码失败。而本文中的HCPPF则具有依靠数据片段的Provenance分级重建功能，因此鲁棒性好。

鉴于当前的Provenance分段传输方法须全部分段数据正确到达BS后才能实施解码等问题，本文提出一种基于逐级重建的Provenance增量压缩方法(hierarchical clustering probabilistic provenance flow，HCPPF)，按层次由高到低以增量形式传输Provenance，并以逐级重建的形式在BS解码Provenance。此方法从根本上解决现有分段方法的不足。

1 相关模型介绍 1.1 WSN多级分簇模型

实现Provenance逐级增量压缩传输的基础是使用多级分簇模型(hierarchical clustering network model, HCNM)管理的WSN。如图 1中拓扑结构所示，本文中的多级分簇管理是指按照某种规则在WSN中选取一些节点。这些节点既是其上一级节点的簇内节点，又是其下一级节点的簇头节点。簇头节点负责管理对应簇内节点间的通信，并对簇内节点采集到的数据通过单跳或多跳的方式传输至BS；其下各级节点所传输的数据包只包含对应Provenance的增量信息。BS按粒度从粗到细，并根据陆续接收的增量数据对Provenance进行逐级重建。

1.2 数据模型

在WSN中，可以按照节点所起作用的不同，将节点分为3种类型：数据源节点，即感知并采集数据的节点；转发节点，即将接收到的数据包转发至下一节点的节点；聚合节点，即将来两个或多个节点的数据包聚合成一个新的数据包并将此新数据包传输至下一节点的节点。

数据源节点收集的数据通过一个MAC(message authentication code)^[10]与其对应的Provenance进行绑定，且每个Provenance还有一个通过Hash链生成的ID。BS可以根据不同的ID值对接收到的隶属于不同数据的Provenance片段进行分类和解码。

1.3 Provenance模型

如图 2所示，在WSN中，存在2种不同类型的Provenance：1)线性Provenance，如图 2(a)所示，n₁是数据源节点，数据包经转发后到达BS，表示为＜n₁, n₂, n₃, BS＞；2)聚合Provenance，如图 2(b)所示，n₁、n₂、n₃和n₈是数据源节点，n₄、n₅、n₆是聚合节点，在递归表达式＜((a)(b)), c＞中，(a)表示左子树，(b)表示右子树，c是根节点，所以可用＜…………n₁)(n₂)), n₄), (((n₃)(n₈)), n₅), n₆), n₇, BS)＞表示图 2(b)中的聚合Provenance。

2 基于增量的Provenance压缩传输

基于增量Provenance压缩传输的思想是：在对WSN进行分级管理的基础上，首次传输只传输最粗粒度的Provenance，之后的每一次传输只传输各粒度之间的增量信息。BS按粒度从粗到细逐级进行解码，最终得到完整的Provenance。此过程可以类比为导航地图的缩放，粗粒度的地图上只显示各个城市之间的位置关系，而细粒度的地图上则显示城市之间的道路分布和连通细节。

2.1 WSN多级分簇的建立

为了对WSN实施多级分簇管理，使用了能量高效多层分簇EEHC(energy efficient hierarchical clustering)方法^[11]。该方法主要包含2个阶段：1)初始化阶段：随机选择若干节点作为簇头节点，并以概率p通告其邻居节点自己为簇头，收到该通告的非簇头节点可成为该簇的成员节点(对于收到多个簇头节点通告的节点，随机选择其中之一加入)，各个簇中只有一个簇头节点；2)扩展阶段：迭代执行1)，各簇可进一步划分为多个子簇，直至满足预设的层级条件。

2.2 基于增量的线性Provenance编码

为实现增量传输，线性Provenance的编码过程是：1)如果当前节点获取的随机抽签概率小于预设阈值p₁且此节点为非簇头节点，那么把此节点ID的增量写入数据包中，同时，修改Provenance的ID和当前节点ID；2)若当前节点获取的随机抽签概率小于预设阈值p₂且此节点是簇头节点，那么先清除原有的Provenance，再将此节点ID的增量、Provenance的ID以及当前节点的ID写入数据包中；3)如果当前节点获取的随机抽签概率不小于p₂且此节点是簇头节点，那么就修改Provenance中的ID，详细过程见算法1。

    算法1：线性Provenance编码

INPUT: (x, c, n_i, w_i, falg_cluster, flag_num)

    OUTPUT: provenance_buffer

    FOR each packet w_i

      IF x＜p₁ andfalg_cluster==0 and flag_num==1

    THEN

    plus_value=ABS(c, n_i)

     c=n_i

    hash_value=hash(hash_value+n_i)

  write plus_value into provenance_buffer

  write hash_value into provenance_buffer

END IF

  IF x＜p₂ and falg_cluster==1 THEN

    flag_num=1

    provenance_buffer=0

    plus_value=ABS(c, n_i)

    c=n_i

    hash_value=hash(hash_value+n_i)

    write plus_value into provenance_buffer

  write hash_value into provenance_buffer

  END IF

  IF x > =p₂ andfalg_cluster==1 andflag_num==0

  THEN

    flag_num=1

    plus_value=ABS(c, n_i)

    c=n_i

    hash_value=hash(hash_value+n_i)

  write n_i into provenance_buffer

  write hash_value into provenance_buffer

  END IF

END FOR

在算法1中：N表示节点标识集合；flag_cluster为簇头旗标；flag_num为同一粒度层上的节点ID是否已完全写入Provenance的旗标；p₁表示簇内节点随机抽签概率阈值；p₂表示簇头节点随机抽签概率阈值；provenance_buffer表示Provenance的缓存；w_i代表数据源节点发送给BS的数据包；c表示当前节点ID；函数ABS用于计算节点ID的增量，其解析式如下：

$ {\rm{ABS}}\left( {{n_1}, {n_2}} \right) = \left| {{n_2}-{n_1}} \right|\left( {{n_1}, {n_2} \in N} \right) $

(1)

图 3是算法1的一个运行实例，圆圈中的数字是节点ID。图 3中，n₁₅、n₁₉和n₂₇分别是数据源节点、转发节点和BS。n₁₅采集的数据经n₁₉转发至n₂₇。执行算法1，在数据包途经的各个节点上只将节点ID的增量添加到Provenance，并修改其当前节点的ID，然后利用Hash链生成新的Provenance指纹。图中的数字4是n₁₉对n₁₅的增量，而8是n₂₇对n₁₉的增量。通过仅添加节点ID增量的方式，使得Provenance的数据量有效减少。

2.3 基于增量的线性Provenance解码

基于增量的线性Provenance解码过程为：1)通过Provenance的指纹，把属于同一Provenance的分段放到同一集合；2)通过后续收到的Provenance增量逐级获得Provenance中节点的ID信息；3)通过获得的节点ID信息重建完整的Provenance，具体过程见算法2。

    算法2：线性Provenance解码

INPUT: (w_i, n_i, provenance_buffer)

OUTPUT: provenance(n_i)

FOR each packet w_i

  IFhash_value from provenance_buffer is the same

THEN

  FOR each plus_value from provenance_buffer

    previous_node=n_i-plus_value

    write previous_node into plus_provenance(n_j)

    n_i=previous_node

    END FOR

      write provenance(n_j) into provenance(n_i)

    END IF

END FOR

在算法2中，provenance(n_i)是指由数据源节点n_i到BS在途节点构成的列表。除provenance(n_i)外，其余符号与算法1中符号含义相同。

图 4是算法2的一个执行实例，n₁₅、n₁₉和n₂₇为对应WSN多级簇结构的最高层节点，n₂₇为n₁₅、n₁₉所属簇的簇头节点，数字4为n₁₉对n₁₅的ID增量，数字8为n₂₇对n₁₉的ID增量；n₉、n₆和n₁₅为下一层节点，n₆为数据源节点，n₁₅不仅是最高层的簇内节点，而且是n₉、n₆所属簇的簇头节点，数字3为n₉对n₆的ID增量，数字6为n₁₅对n₉的ID增量。当BS获取到一个Provenance，如图 4(a)所示，将通过n₂₇的ID与增量信息8、4可以依次获得节点n₁₉、n₁₅的ID，从而解码出最高层级(最粗粒度)Provenance，如图 4(b)所示；根据下一个Provenance分段数据可解码得到次一层级的Provenance，如图 4(d)所示；图 4(e)为最终重建完成的Provenance。

2.4 基于增量传输的聚合Provenance编码

通过数据聚合(data aggregation)，即将两个或多个数据包汇聚为一个新数据包并进行传输，可以节省能量。通过以下方法对在聚合节点处的Provenance信息进行编码：1)通过prime函数获得不大于节点ID增量的最大素数，并且把素数之积放到provenance_buffer的左半部；2)通过offset函数获得该增量和素数间的偏移量，并且把偏移量的和放到provenance_buffer的右半部；3)选取包含较少节点ID的Provenance片段，并将其放到新Provenance数据区的左侧，后续不再对这部分信息进行处理；把包含较多节点ID的Provenance放到右侧，该区域将保存下一个节点处的节点ID增量。算法3是聚合Provenance的编码算法。

    算法3：聚合Provenance编码

INPUT: (w_i, n_i, buffer_y)

OUTPUT: provenance_buffer

FOR each packet w_i

  IF n_i is not an aggregated node THEN

    buffer_x=encoding n_i using algorithm 1

  END IF

    IF n_i is an aggregated node THEN

    buffer_x=encoding n_i using algorithm 1

  FOR each plus_value from buffer_x

    prime_buffer=prime_buffer×prime(plus_value)

    prime_offset=prime_offset+offset(plus_value)

  END FOR

    write prime_buffer into buffer_x

    write prime_offset into buffer_x

    write buffer_x into provenance_buffer

    write buffer_y into provenance_buffer

  END IF

END FOR

在算法3中：V为节点增量集合；prime函数值积存储在prime_buffer中；offset函数值之和存储prime_offset中；函数prime(n)=p_n，其中p_n是满足p_n≤n，n∈V的最大素数，V={n∈ABS|2≤n&&0≤n-p_n≤7}；函数offset(n)=n-p_n。

图 5是算法3的一个执行实例，其中的聚合节点共计收到2个数据源节点产生的Provenance。该算法先获得其素数的乘积和偏移量之和，再更新每个数据包中的Provenance，最终把聚合后的Provenance存放到新数据包中。

2.5 基于增量的聚合Provenance解码

BS通过指纹对接收到的聚合数据包中的Provenance片段进行分类，并在各分类中执行以下操作：1)解码BS至聚合节点的Provenance；2)迭代执行1)，解码聚合节点之间的Provenance。

当执行第一步操作时，BS先把prime_buffer中的整数拆分成由质数x_i组成的集合；再通过文献[12]中的算法把prime_offset拆分成由元素个数和因子数相等的y_i组成的集合，并且满足：

y_i∈M，y_i∈M={0, 1, 2, 3, 4, 5, 6, 7}，

最后通过公式：

$ \delta = \sum\limits_{i = 1}^n {{{\left( {{y_i}-\left( {{\rm{plus\_valu}}{{\rm{e}}_i}-{x_i}} \right)} \right)}^2}} $

(2)

在plus_value_i中搜索满足δ=0的所有节点ID增量序列，具体过程见算法4。

    算法4：聚合Provenance解码

INPUT: (w_i, buffer_x, buffer_y, plus_buffer)

OUTPUT: provenance(n_i)

FOR each packet w_i

  provenance(n_x)=decoding plus_buffer using algorithm 2

  write provenance(n_x) into provenance(n_i)

END FOR

FOR each packet w_i

  provenance(n_y)=decoding plus_buffer using algorithm 2

  write provenance(n_y) into provenance(n_i)

END FOR

在算法4中：从聚合节点至BS的Provenance存储到buffer_x中，数据源节点至聚合节点的Provenance存储到buffer_y中，节点ID的增量存储到plus_buffer中，provenance(n_i)表示从数据源节点n_i到BS途经的节点序列。

图 6是算法4的一个执行实例，n₂₇、n₁₉、n₂₅和n₁₁是对应WSN多级簇结构中的最高层节点，n₂₇是n₁₉、n₂₅和n₁₁所属簇的簇头节点，数字2、7、13是n₂₇ ID相对于n₂₅、n₁₉和n₁₁ ID增量的最大素数。

在图 6(a)中，数字0、1、3为最大素数与对应的ID增量之间的偏移量。n₁₉、n₁₅、n₉、n₄为下一级节点，n₉、n₄为数据源节点，n₁₅为聚合节点。n₁₉不仅是最高层的簇内节点，而且是n₁₅、n₉、n₄所属簇的簇头节点。数字5为n₁₅相对于n₉ ID增量的最大素数。由于n₁₉对n₁₅ID增量的最大素数是3，n₁₅对n₄ ID增量的最大素数是11，所以33为这两个素数的乘积。图 6(b)中的2个1为最大素数与对应的节点ID增量的偏移量之和。当接收到聚合Provenance的时候，通过n₂₇的ID、素数乘积以及偏移量之和，BS可以计算得出n₁₉、n₂₅和n₁₁的ID，并且解码出最高层(最粗粒度层)Provenance，如图 6(c)所示；当后续的Provenance分段收到后，可以解码得到次一层的Provenance，如图 6(d)所示；最终，解码得到完整的Provenance，如图 6(e)所示。

2.6 性能分析

在时间复杂度方面，因为算法1与WSN中的节点总数m正相关，所以它的时间复杂度为O(m)；

与此算法类似，算法2的时间复杂度也是O(m)。

因为算法3进行编码是一个含有n个数据源节点的Provenance，所以时间复杂度是O(mn)，即其时间复杂度取决于数据源节点的个数和WSN中的节点总数两个方面；算法4用到的是整数素因子分解算法，而此分解算法的时间复杂度为

$ O\left( {\exp \left( {{{\left( {\frac{{64b}}{9}} \right)}^{\frac{1}{3}}}{{\left( {\log b} \right)}^{\frac{2}{3}}}} \right)} \right) $

式中b表示整数中素因子的数目。所以，算法4的时间复杂度为

$ O\left( {n \cdot \exp \left( {{{\left( {\frac{{64m}}{9}} \right)}^{\frac{1}{3}}}{{\left( {\log m} \right)}^{\frac{2}{3}}}} \right)} \right) $

就空间复杂度而言，由于算法1、算法3在编码时仅使用一个定长的provenance_buffer来存放Provenance，因此它们的空间复杂度都为O(1)；而对于算法2，由于需存储WSN中的所有m个节点ID进行解码并重建Provenance，因此空间复杂度是O(m)；由于算法4需要解码总共含有n个数据源节点的Provenance，因此空间复杂度为O(mn)。

3 仿真与实验

针对提出的HCPPF方法，进行了基于TinyOS的软件仿真以及基于ZigBee节点的硬件组网实验。并在同样的配置下，将该方法与当前主要的Provenance分段传输方法PPM^[13]、PPF^[14]进行对比。性能对比过程中使用的指标如下：

1) Average Provenance Length (APL)：一定时间内，BS收到的全部Provenance的平均值，用字节数表示，APL的计算方式为

$ {\rm{APL = }}\frac{{\sum\limits_{i = 1}^m {P{S_i}} }}{m} $

(3)

式中：m为BS收到总数据包量，PS_i为第i个数据包的Provenance大小。

2) Total Energy Consumption (TEC)：一定时间内，传输Provenance消耗的能量总数，用毫焦数表示，TEC的计算方式为

$ {\rm{TEC = }}\sum\limits_{i = 1}^m {{\rm{E}}{{\rm{C}}_i}, } $

(4)

式中：EC_i为节点n_i传输Provenance所耗能量，m为WSN中节点总数。

3.1 基于TingOS的仿真

在Linux环境下，使用TinyOS-2.1.2的TOSSIM进行软件仿真，并通过POWERTOSSIMz插件对能耗进行测量。

仿真过程中，节点总数为121，BS是0号节点，网络最大跳数为12。图 7(a)为运行PPM、PPF以及HCPPF方法时，数据包传输跳数与线性Provenance的APL的关系曲线。如图 7(a)所示，在3种不同的Provenance方法中，线性Provenance的APL都随着数据包传输跳数单调增加，但HCPPF的APL增长幅度最慢，其次为PPF的APL曲线，而PPM的APL的曲线增长最快。由此可见，在相同环境中，与PPM和PPF方法相比，HCPPF方法可获得更高的线性Provenance平均压缩比。PPF与PPM相比，PPF性能更优。

图 7(b)为在线性Provenance中，运行PPM、PPF和HCPPF方法时，数据包传输跳数与传输能耗TEC的关系曲线。图 7(b)与图 7(a)中的曲线走势具有极高的吻合度，原因是如果Provenance的APL越小，那么能耗TEC也将越低。所以，在相同情况下，就能耗而言，HCPPF方法优于其他两种方法，而PPF方法又优于PPM方法。

图 7(c)为在随机选取10个节点为数据源节点和5个节点为聚合节点的情况下，运行HCPPF、PPM以及PPF方法，数据包传输数目与聚合Provenance的APL的关系曲线。如图 7(c)所示，在3种不同的Provenance方法中，聚合Provenance的APL都会随着数据包传输数目的增加单调递减且趋于某个稳定值，原因是当WSN中数据包数量较少时，聚合发生的可能性也会变小。

通过观察图 7(c)可知，HCPPF的APL曲线下降速度最快，最为陡峭；PPF的APL曲线次之；PPM的APL最为平缓。所以，在相同情况下，HCPPF方法较另外两种方法，对聚合Provenance具有更高的平均压缩比。同时，PPF方法又优于PPM方法。

3.2 硬件组网实验

在基于ZigBee节点的硬件组网实验中，共使用0x2501~0x2548的48个地址编号的48个ZigBee节点，并将0x2548地址编号节点用作BS。首先依照ZigBee节点的具体特性修改仿真中使用的代码的I/O接口函数，再通过下载器将其烧写到节点上。如图 8所示，在面积约为15×15 m²的区域内部署48个ZigBee节点，BS放置在中间位置并与一台笔记本电脑通过USB接口相连。

图 9为在实验中，当运行HCPPF、PPF以及PPM方法时，数据包传输跳数与线性Provenance的APL的关系曲线。通过观察图 9中的实验结果，可知实验结果与仿真结果(见图 7(a))的曲线走势基本吻合，实证了HCPPF方法的有效性。

图 10为在相同的情况下，运行HCPPF、PPF以及PPM方法时，数据包传输数量与聚合Provenance的APL的关系。通过观察图 10中的数据，实验结果与仿真结果(见图 7(c))基本吻合，也实证了HCPPF方法的有效性。

4 结论

本文提出的基于逐级重建的Provenance增量传输方法HCPPF能够以增量的形式传输Provenance，并且可以在BS端按粒度由粗到细进行解码并重建Provenance。HCPPF方法能从根本上克服现有Provenance分段传输方法须全部Provenance分段完全到达后才能解码等问题，且有效提高了数据可信性评估效率及评估鲁棒性。仿真与硬件组网实验结果均证实该方法的可行性与有效性。结合当前的研究现状，下一步主要针对HCPPF方法中上层节点能耗以及最佳层次结构等问题作进一步研究，进一步提高HCPPF方法的效率和性能。