基于多粒度拓扑图的无线传感器网络逐级精化溯源方法

康照玲，徐芹宝，王昌达

(江苏大学 计算机科学与通信工程学院，江苏 镇江212013)(*通信作者电子邮箱changda@ujs.edu.cn)

0 引言

无线传感器网络(Wireless Sensor Network， WSN)使用范围非常广泛，如环境监测、智能电网等[1]。在WSN中，节点间相互协作，实时监测、感知、采集物理世界的信息，并将这些信息处理为计算机所能识别的数据，通过一跳或多跳的方式传输到基站(Base Station， BS)[2]。由于传感器节点容易受外界环境的影响，数据在传输的过程中可能被损坏，这就需要对数据进行可信性分析。溯源(Provenance)是评估数据可信性的重要依据，因为它记录了传输途径的节点以及对数据的加工处理过程[3-4]。在大规模传感器网络中，因为数据的平均传输链路较长，所以导致Provenance逐渐增大，进而导致数据包的过载问题，因此，研究人员提出了分段传输Provenance的方法。概率溯源流(Probabilistic Provenance Flow， PPF)[5]是将较大的Provenance分割为一定数量的片段，每次以给定的概率传输溯源分段；伪随机噪声(Pseudo Noise， PN)码方法[6]则是通过伪噪声码将大的Provenance编码为一系列较小的二进制码块，通过数据包延迟信道传送。以上两种方法在全部Provenance分段到达BS之前无法解码，所以传输的鲁棒性弱、溯源数据的利用率低。

针对传统分段传输方法中数据利用率低、耗能较高的问题，本文提出一种基于多粒度拓扑图的WSN逐级精化溯源(Multi-granularity Topology-based Stepwise Refinement Provenance， MTSRP)方法。多粒度拓扑图是指在WSN初始拓扑图的基础上，按一定的规则将节点进行合并，将同类节点用一个抽象节点表示，从而产生一个由抽象节点所组成的粒度较粗的拓扑图；在此基础上对抽象节点继续合并，可以得到更粗粒度的拓扑图。逐级精化传输则是指按粒度从粗到细逐级传输Provenance。在BS端，可首先在较粗粒度上获取Provenance信息，然后根据后续到达的较细粒度数据逐级解码，直至获得准确的Provenance。因为可以根据粗粒度的信息Provenance初步断定其可信性，所以BS可以由此判断是否对接收的Provenance继续精化解码，从而提高了数据可信度评估的效率。基于TinyOS- 2.1.2软件仿真以及ZigBee硬件节点的实验均表明，本文所提出的方法与PPF[5]、PN[6]方法相比平均压缩比更高、节能效果和鲁棒性也更好。

1 相关工作

由于WSN是一个能量受限的网络，所以为了解决问题时减少路由开销，研究人员提出了大量的Provenance压缩算法。文献[7]提出了轻量级压缩Provenance算法，解决了Provenance随数据包传输路径的增长而迅速膨胀的问题。Hussain等[1]提出了采用算数编码压缩Provenance(Arithmetic Coding based Provenance compression， ACP)的方法，解决了Provenance的大小随路径的变化而变化的问题。但是在大规模WSN中，数据传输的链路长，采用轻量级或压缩的方法还是会出现严重的过载问题，分段传输Provenance的方法随之而出。此方法的主要思想是将Provenance分割成若干小块，每个小块携带一部分Provenance数据，由此解决了数据过载问题。

Alam等[5]提出的概率溯源流(PPF)法，将一个大的Provenance分割成若干小段，通过一定的概率计算决定当前应当传输的分段。Sultana等[6]提出了一种伪随机噪声(PN)码算法，即通过伪噪声码将较大的溯源编码为一系列较小的二进制码块，通过数据包间延迟信道传输。这些方法解决了由于传输链路的增加而导致数据过载的问题，但是在全部分段准确到达之前无法解码。

Wang等[8]提出的基于动态贝叶斯网络的传感器网络溯源压缩方法，即一种使用动态贝叶斯网络对WSN进行建模的方案，节点或BS能周期性地更新网络的拓扑结构，然后通过修改的算术编码压缩方法对Provenance进行编码。此方法解决了WSN拓扑会动态变化的问题。

文献[9]提出的商空间法，即根据一定的等价关系，将论域进行商空间划分获得新的元素，而这些新元素会构成一个新的空间，即一个较粗粒度的世界。

Wang等[10]提出的使用路径字典的方法传输Provenance，即在传输过程中，首先根据传输的Provenance路径信息建立字典，在后续传输过程中只需传输路径的索引即可，此方法解决了路径熵值的限制，具有很高的压缩比。所以本文利用了此方法，在每一层拓扑图上均建立相应的字典，因此传输效率很高。

本文所提出的基于多粒度拓扑图的WSN逐级精化溯源方法，以信息熵为等价条件，通过计算节点间的互信息(Mutual Information, MI)，将较大的WSN拓扑图划分为由少量抽象节点组成的较粗粒度的拓扑图，由此可将Provenance按层次分段传输，且无需全部分段完全到达，评估者依然能大致了解到该Provenance传输中的衍生过程，而且在传输过程中，在每一层拓扑图上均建立相应的路径字典信息，提高传输效率。

2 系统模型及相关工作

本章主要介绍基于非均匀粒度拓扑图的WSN逐级精化溯源方法所涉及的系统模型。

2.1 WSN拓扑图多粒度模型

多粒度模型主要是利用商空间划分理论[9]通过计算节点之间的互信息实现的，即在训练阶段收集每个节点在Provenance中出现的频率以及节点之间的拓扑关系，然后计算节点间的互信息并利用抽象节点内部的信息熵作为临界条件逐级将WSN的拓扑图进行划分成不同的粒度，且在每个粒度下的抽象节点内部的信息熵是相同的。如图1所示，在传输时，Provenance首先记录一级粒度下的节点信息n13、n23、n33，然后再记录二级粒度下的节点信息n12、n22，依此类推。在BS端则根据粒度从粗到细逐级精化解码。

图1 WSN拓扑图多粒度分层图

2.2 数据模型

根据传感器节点在WSN中扮演不同角色，可以把传感器节点分为三类：1)数据源节点。感知、采集客观世界信息。2)转发节点。将数据沿BS方向转发到下一节点。3)汇聚节点。将来自不同节点的数据汇聚为一个较大的数据包并传往BS。

每个数据包均具有数据值和Provenance数据。Provenance数据包括数据源节点id、当前节点id、路径序列号、汇聚集合等。其中，路径序列号的设置是为了使BS能够识别出隶属于不同粒度上的相同路径的Provenance分段。

2.3 Provenance模型

在WSN中，Provenance分为两种结构模型：1)简单Provenance模型，如图2(a)，叶子节点n1产生数据包，经过中间节点的转发直至BS，这种Provenance可以用〈n1,n2,n3,n4,n5,BS〉表示；2)汇聚Provenance模型，如图2(b)，n1,n2,n3,n4是数据源节点，n5是汇聚节点，n5汇聚从n1,n2,n3,n4接收的数据，然后再传至BS。这种汇聚Provenance可以用〈{n1,n2,n3,n4},n5,n6,n7,BS〉表示。

图2 两种Provenance模型

3 基于非均匀粒度Provenance编码与解码

本章主要从WSN粒度图的划分、在多级粒度图上压缩与解压缩Provenance三个方面进行讨论。

3.1 非均匀粒度拓扑图的划分

3.1.1 节点出现概率和节点间联合概率的计算

为了获取网络中传感器节点参与数据包转发、聚合等操作的概率，需要一个训练阶段。在训练阶段发生前，BS端处没有节点的出现概率和节点间联合概率等信息，所以假定一开始所有节点的出现概率和节点间联合概率均采用平均分布；然后，在训练过程中BS周期性地更新节点以及节点间概率数据。下面简要阐述在训练过程中概率的计算公式：

BS计算节点ni在数据包历史传输路径中出现的次数，记为ofi。根据ofi的值，BS可以计算出传输过程中节点总的发生频率of，那么对于节点ni来说，它的出现概率为opi，其计算方式[1,11]如下：

(1)

opi=ofi/of

(2)

在训练阶段结束前后，BS能检测出数据包路径中节点出现的先后次序，并计算出节点ni出现在节点nj后的总数，记为ofij，那么nj到ni的联合概率[1,11]为:

opij=ofij/ofj

(3)

3.1.2 互信息和信息熵计算

在BS端计算各个节点之间的互信息(MI)，互信息越大的两个节点关联度越大，互信息的计算方式为：

(4)

通过计算节点内部信息熵[12]来确定粒度的划分条件，查找出互信息最大的两个点之后，计算出其内部的信息熵，计算公式如下：

(5)

其中ki表示第i个聚类。

3.1.3 多粒度拓扑图划分算法

本方法采用树的双亲节点存储法[13]存储划分好的粒度拓扑图，存储的节点主要包含节点id、节点所在层次flag、节点合并的抽象节点所在位置parent以及节点的概率p。多粒度拓扑图划分过程为：1)计算出各节点之间的互信息MI；2)从MI中找出互信息最大的两个点ni、nj判断它们隶属哪层粒度，若ni.flag==nj.flagnj.flag，则将nj.parent置为ni所在位置。

算法1 WSN非均匀粒度拓扑图的划分算法。

输入：层次标记flag，当前粒度阈值value,节点间互信息MI；

输出：多粒度拓扑图ptree={id,flag,parent,p}。

1)

for eachk

2)

ifMI[k].infois max then

3)

ni=MI[k].id1

4)

nj=MI[k].id2

5)

end if

6)

ifni.flag==nj.flagandni.flag

7)

compute theHofniandnj

8)

ifH

9)

add a new id number into theptree

10)

elsek++

11)

end if

12)

end if

13)

ifni.flag==nj.flagandni.flag==flagthen

14)

compute theHofniandnj

15)

ifH

16)

change value of the child ofnjintoni

17)

deletenjfromptree

18)

elsek++

19)

end if

20)

end if

21)

ifni.flag>nj.flagthen

22)

compute theHofniandnj

23)

ifH

24)

nj.parent=ni

25)

elsek++

26)

end if

27)

end if

28)

ifni.flag

29)

compute theHofniandnj

30)

ifH

31)

ni.parent=nj

32)

elsek++

33)

end if

34)

end if

35)

end for

算法1各符号含义为：1)flag是当前要划分的拓扑图的层级数；2)value为当前粒度的阈值；3)MI表示节点间的互信息，存储形式为{节点ni，节点nj，两者互信息}；4)ptree存储划分完成的多粒度拓扑图；5)ni，nj表示互信息最大的两个节点；6)num_node表示节点数；7)H表示节点ni，nj内部的信息熵值，当H大于当前粒度所设置的最大值时，停止合并ni，nj。图3为多粒度拓扑图划分流程。

图3 多粒度拓扑图划分流程

多粒度拓扑图划分完成后，BS将划分完成的拓扑图广播到各个节点，各个节点随即知道它自己的抽象节点编号。

3.2 Provenance的非均匀多粒度编码

Provenance的非均匀多粒度编码是在基于非均匀多粒度划分的拓扑图上采用字典编码[10]的方法，即在节点处保存有当前层次的数据路径及其字典(Packet Path Dictionary， PPD)。传输过程中需要传输的信息包括数据源节点、当前数据节点、当前传输层次、汇聚节点集合、字典索引，记为prIndex={seq,sourceid,nodeid,flag,agr,dicindex}设置每个节点内部保存的字典为序列号、传输路径、汇聚集合、字典索引，记为PPD={seq,path,agr,dicindex}。已知当前传输层次为flag，编码过程如下：

图4 Provenance编码

算法2 多粒度拓扑图上编码Provenance。

输入：接收节点编号ni，序列号seqi，层次,flag。

输出：传输数据路径及节点信息prIndex=(vi,dicindex)。

1)

ifniis a data source node then

2)

3)

4)

seqi=hash(ni)

5)

agr=∅

6)

prIndex.v=vi

7)

8)

end if

9)

ifniis a forwarder node then

10)

11)

12)

seqi=hash(seqj+ni)

13)

agr=∅

14)

prIndex.v=vi

15)

16)

end if

17)

ifniis an aggregator node then

18)

19)

20)

seqi=hash(seq1+seq2+…+ni)

21)

agr={seq1,seq2,…}

22)

prIndex.v=vi

23)

24)

end if

为了便于理解此算法，下面给出一个应用实例。图4(a)为一个简易WSN拓扑图，图中圆圈内部表示节点的id值，因为拓扑图分为3层，所以节点(n1,n2,n3,n4)在第2层和第3层所属抽象节点id分别为(6，6，7，8)和(9，9，9，9)。如图4(a)，在数据源节点n1,n4采集到数据后，由n2转发到n3，在n3处汇聚由n2、n4转发而来的数据，再传输至BS。Provenance传输方式如下：

1)在第3层上传输Provenance时，n1,n4在第3层的抽象节点编号为9，更新数据包信息如图4(b)中的①、图4(b)中的③；n2在第三层所属抽象节点为9，更新数据包信息如图4(b)中的②；n3在第三层所属抽象节点为9，更新数据包信息如图4(b)中的④。

2)在第2层上传输时，n1,n4在第2层的抽象节点编号分别为6、8，更新数据包信息如图4(c)中的①、图4(c)中的③；n2在第二层所属抽象节点为6，更新数据包信息如图3(c)中的②；n3在第二层所属抽象节点为7，更新数据包信息如图4(c)中的④。

3)在第1层上传输时，数据包更新方式与第2层类似，数据包更新结果如图4(d)所示。

3.3 Provenance的非均匀多粒度解码

当BS接收到数据包p时将解码出的数据包中节点的拓扑图以T〈Vp,Ep〉形式保存，而BS会根据其对应的PPD中dicindex信息构建溯源拓扑信息。

算法3 在第flag层上解码Provenance。

输入：传输层次flag,数据路径及信息(vi,dicindex)。

输出：拓扑图Tflag(Vflag,Eflag)。

1)

if the AM-FM verification fails then

2)

3)

ifv.flag==flagthen

4)

ifv.arg==∅ then

5)

Tflag(Vflag,Eflag)=search path in PPD

6)

else

7)

pathset=number of ′;′ indicindex

8)

fori=1 topathsetdo

9)

pathi=searchbranchiofdicindexin PPD

10)

end for

11)

Tflag(Vflag,Eflag)=path1;…;pathpathset

12)

end if

13)

end if

14)

end if

15)

ifTflag(Vflag,Eflag) is not useful then

16)

drop the nextpacketviwhenvi.seq=v.seq

17)

end if

算法3中各符号含义：1)flag表示当前要解码的层次；2)vi表示存储有{seq，ni，flag}的集合；3)dicindex表示接收数据包中溯源索引；4)Tflag(Vflag,Eflag)表示接收到的数据包中第flag层的拓扑图。

为了便于理解此算法，以图4(a)为例简要描述此算法。

1)BS首先接收到数据包{hash,1,3,3,∅,〈9,∅〉}，解码出flag=3，则传输层次为最高层，且数据源节点为n1，当前节点为n3，没有汇聚节点，则解码出第3层上的Provenance为图5(a)。

2)接收数据包{hash,1,3,2,{6,8},〈6,7;8,7〉}，解码出此传输层次为第2层，且数据源节点为n1，当前节点为n3，汇聚节点为n7，汇聚从n6、n8节点接收到的数据包，解码出第二层上的溯源为图5(b)。

3)接收数据包{hash,1,3,1,{2,4},〈1,3;4,3〉}，与上述两层解码方式相同，解码结果如图5(c)。

图5 Provenance解码

4 性能分析与仿真

4.1 性能分析

本节主要对本文提出的MTSRP算法进行时间复杂度和空间复杂度分析，算法1中：1)s表示每个层次所需抽象的节点个数，2)k表示存储互信息值的个数，3)flag表示需要抽象的层次数，那么算法1的时间复杂度为O(s·flag)，空间复杂度为O(3·k)。算法2中：p表示PPD中所需保存的字典序列个数，算法2只需更新节点内部的PPD以及Provenance中的dicindex、seq、agr部分，所以算法2的时间复杂度为O(1)，空间复杂度为O(4·p)。算法3中：n表示PPD中记录数，利用建立好的字典进行解码，只需查询PPD中的记录，时间复杂度为O(n)，空间复杂度为O(n)。

4.2 仿真与实验

本文实验在TinyOS- 2.1.2操作系统下进行仿真，采用nesC编程语言编写应用程序，并通过PowerTOSSIMz能量仿真插件进行能量评估。

为了验证本文算法的有效性，将MTSRP方法与基于多级分簇概率溯源流(Hierarchical Clustering Probabilistic Provenance Flow， HCPPF)[14]方法、文献[8]提出的基于动态贝叶斯网络的Provenance(Dynamic Bayesian Network based Provenance， DBNP)方法进行对比。

4.2.1 性能指标

1)Average Provenance size：代表数据包的平均比特数。

2)Total Energy Consumption(TEC)：代表节点总能耗。当网络中有n1,n2,…,nm个节点，那么总的能量消耗为：

(6)

其中：ECni表示节点ni的能量消耗；m表示网络中节点的总数。

4.2.2 仿真结果

在仿真实验中，采用编号1～50的节点，其中节点50为BS节点，网络中跳数最大为12跳。在仿真过程中，分析线性Provenance和汇聚Provenance两种情况，讨论两者传输跳数与Provenance包含的平均比特数之间以及总能耗的关系。

图6给出了HCPPF、DBNP、MTSRP三种方法中Provenance平均比特数与传输跳数的关系。从图中可以明显看出在线性Provenance中，MTSRP方法采用路径字典压缩方法传输Provenance，所以随着传输跳数的增加，Provenance平均比特数一直处于较低的状态，压缩比相比其他方法而言优势较为明显。

图6 仿真实验中线性Provenance中Provenance平均比特数与传输跳数的关系

图7是HCPPF、DBNP、MTSRP三种方法传输跳数与总的能量消耗之间的关系。从图7中可以看出，在传输跳数逐渐增加时，MTSRP相比其他两种方法耗能最少。

图8所显示的是在TinyOS- 2.1.2中仿真时选取10个源节点和5个汇聚节点，并使用DBNP、HCPPF、MTSRP方法得到的Provenance平均比特数与数据包传输数目的关系。图8中曲线关系表示，MTSRP方法在数据包传输数目增加时，Provenance会根据建立好的路径字典中选取对应路径的索引来代替完整路径，所以汇聚效果更好并趋向于一个更低值。

4.2.3 硬件组网实验

采用50个ZigBee节点进行硬件实验，分别给这50个节点分配地址编号为0x0001～0x0050，其中编号0x0050为BS节点。将在仿真中已编译成功的二进制文件下载到节点的芯片上，并将节点部署在一个15 m×15 m的空地上。

图7 线性Provenance传输跳数与总能耗的关系

图8 仿真实验中汇聚Provenance中Provenance平均比特数与传输跳数的关系

图9显示的是在硬件组网实验中，在线性传输Provenance条件下，采用HCPPF、MTSRP、DBNP三种方法时，数据包传输跳数与Provenance平均比特数的关系。图中的数据曲线与图6的数据曲线相比相差不大，基本吻合。

图9 硬件实验中线性Provenance中Provenance平均比特数与传输跳数的关系

图10显示的是在汇聚Provenance条件下分别采用HCPPF、MTSRP、DBNP方法时，数据包传输跳数与Provenance平均比特数的关系。图中的数据曲线与图8的数据曲线相比数据变化趋势基本相同。由此证明了本文MTSRP方法的实用性和有效性。

5 结语

针对传统分段传输数据利用率低、耗能较高的问题，本文提出一种基于多粒度拓扑图的溯源传输方法，即将大的WSN拓扑图按一定的规则抽象成粗粒度的拓扑图，在传输过程中由粗到细传输Provenance。一方面解决了传统分段方法中全部分段到达之前无法解码的问题；另一方面评估者可以根据先到达的粗粒度数据衍生过程来判断当前数据是否可靠，是否需要采用更细粒度的数据进行评估；与此同时，本文方法在Provenance传输过程中节约了大量的能量。仿真实验以及硬件组网实验验证了本文方法的实用性和有效性。在下一步的工作中，将针对本文使用的路径字典的传输方法进行进一步的改进，解决网络拓扑动态变化时字典传输不稳定的问题。

图10 硬件实验中汇聚Provenance中Provenance平均比特数与传输跳数的关系

References)

[1] HUSSAIN S R, WANG C, SULTANA S, et al. Secure data provenance compression using arithmetic coding in wireless sensor networks [C]// Proceeding of the 2015 Performance Computing and Communications Conference. Piscataway, NJ: IEEE, 2015: 1-10.

[2] 李建中,高宏.无线传感器网络的研究进展[J].计算机研究与发展,2008,45(1):1-15.(LI J Z, GAO H. Survey on sensor network research [J]. Journal of Computer Research and Development, 2008, 45(1): 1-15.

[3] DOGAN G. A survey of provenance in wireless sensor networks [J]. Ad Hoc & Sensor Wireless Networks, 2016, 30(1/2): 21.

[4] BISDIKIAN C, KAPLAN L M, SRIVASTAVA M B. On the quality and value of information in sensor networks [J]. ACM Transactions on Sensor Networks, 2013, 9(4): 48.

[5] ALAM S M I, FAHMY S.A practical approach for provenance transmission in wireless sensor networks [J]. Ad Hoc Networks, 2014, 16(4): 28-45.

[6] SULTANA S, SHEHAB M, BERTINO E. Secure provenance transmission for streaming data [J]. IEEE Transactions on Knowledge & Data Engineering, 2013, 25(8): 1890-1903.

[7] SHEBARO B, SALMIN S, BERTINO E, et al. Demonstrating a lightweight data provenance for sensor networks [C]// Proceeding of the 2012 ACM Conference on Computer and Communications Security. New York: ACM, 2012: 1022-1024.

[8] WANG C, BERTINO E. Sensor network provenance compression using dynamic Bayesian networks [J]. ACM Transactions on Sensor Networks, 2017, 13(1): Article No. 5.

[9] 张燕平,张铃,吴涛.不同粒度世界的描述法——商空间法[J].计算机学报,2004,27(3):328-333.(ZHANG Y P, ZHANG L, WU T. The representation of different granular worlds: a quotient space [J]. Chinese Journal of Computers, 2004, 27(3): 328-333.)

[10] WANG C, HUSSAIN S R, BERTINO E. Dictionary based secure provenance compression for wireless sensor networks [J]. IEEE Transactions on Parallel & Distributed Systems, 2016, 27(2): 405-418.

[11] 袁裕琳.WSN中基于多级算术编码的溯源数据压缩方法[D].镇江：江苏大学,2016.(YUAN Y L. Data provenance compression using cluster based arithmetic coding in wireless sensor networks [D]. Zhenjiang: Jiangsu University, 2016.)

[12] YUAN L, KEVIN C, DESOUZA, et.al. Measuring agility of networked organizational structures via network entropy and mutual information [J]. Applied Mathematics and Computation, 2010, 216(10): 2824-2836.

[13] 严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,2007:135.(YAN W M, WU W M. Date Structure [M]. Beijing: Tsinghua University Press, 2007: 135.)

[14] 宋泽.基于分层视图的WSN溯源压缩算法的研究[D].镇江：江苏大学,2017.(SONG Z. Research on provenance compression algorithm based on hierarchical view in WSN [D]. Zhenjiang: Jiangsu University, 2017.)

This work is partially supported by the National Natural Science Foundation of China (61672269), the Transformation Project of Science & Technology Achievements of Jiangsu Province (BA2015161), the Top-Notch Talent Planning Project of Jiangsu University (1213000013).

KANGZhaoling, born in 1993, M. S. candidate. Her research interests include information security, wireless sensor network.

XUQinbao, born in 1987, M. S. candidate. His research interests include information security, wireless sensor network.

WANGChangda, born in 1971, Ph. D., professor. His research interests include information security, network communication, Internet of things.