基于层次混合的高效概率包标记WSNs节点定位算法

周先存 黎明曦 陈振伟 徐英来 熊 焰 李瑞霞

①(皖西学院信息工程学院 六安 237012)

②(中国科学技术大学计算机科学与技术学院 合肥 230026)

③(解放军陆军军官学院六系 合肥 230031)

1 引言

无线传感器网络(Wireless Sensor Networks,WSN)是由集感知、计算、通信能力于一身的传感器节点组成，具有快速部署、实时监测、自组织等特点，能在多种场合满足环境、商业、军事等信息获取的实时性、准确性和全面性的需求[1,2]。由于WSN缺乏明显的边界和防火墙之类的安全设施，所有节点均直接暴露在攻击者面前，很容易遭到敌方入侵和渗透，攻击者一旦俘获节点，从内部对网络发动攻击，典型的如拒绝服务攻击等会极大地消耗网络的能量与带宽，造成极为严重的后果[3]。因此，设计一种在节点能量、计算、存储等资源有限的条件约束下，迅速溯源定位出恶意节点的算法，从而防止恶意节点对网络造成更大伤害是非常必要的，对推动WSN的发展应用也具有十分重要的意义。

传统IP网络中主要有3种著名的基础性溯源追踪技术[4]：日志记录技术(Logging or Hashbased)[5-8]，基于因特网控制报文协议的技术(ICMP-based)[9]和概率包标记技术(Probabilistic Packet Marking, PPM)[10-17]。日志记录技术需要路由器有较强的计算和存储能力，以记录所转发数据包的摘要信息，通过查询记录信息重构出转发路径[18]。这在由普通节点行使路由功能的 WSN中是无法应用的。基于因特网控制报文协议的技术是基于TCP/IP协议栈的，同样不适用于WSN[4]。概率包标记技术(Probabilistic Packet Marking)是指路由器以一定的概率将身份信息写入数据包后再对其转发，接收终端通过收集和分析这些标记，复原出包传输路径。概率包标记技术又分为确定性包标记(DPM)与确定性流标记(DFM)，即使攻击者从NAT或代理服务器后面的网络发起攻击， DFM方法也能追踪到攻击者的源IP地址，并且处理与内存开销小[16]。文献[17]提出了一种自适应概率包标记方案，其主要思想是：当分组进入首跳路由器时，其TTL值被设置为一个统一的值，当分组在网络中转发时，每经过一个中间路由器就将分组TTL值减1，因此，每个中间路由器可以推断出分组所经过的路由器级的跳数，然后相应地用与路由器级跳数成反比的概率标记分组。该标记方法能快速重构攻击路径。文献[19]将日志记录技术与概率包标记技术结合起来进行恶意节点定位。总体来看，概率包标记技术由于占用网络资源少，不影响正常的网络通信，无需人工参与，对不同协议的通用性强。由于传感器节点的计算性能和存储性都十分有限，不满足传统网络安全机制的计算复杂度需求，所以对恶意节点的溯源追踪多采用概率包标记方法。

文献[20]提出无线传感网恶意节点溯源定位的基本概率包标记(BPPM)算法，其基本思想是：节点收到数据包后，按照全网统一概率p决定是否对数据包进行标记。每个被标记过的数据包都保存有部分路径信息，当汇聚节点收集到足够数量的包时，就可以追踪到源节点。该方法标记过程简单，不会对节点造成过多额外的计算、通讯开销，但算法收敛性差。假设数据包从节点v到汇聚节点S需要经过d跳，那么汇聚节点收到节点v的标记的概率为A=p( 1 -p)d-1,d值越大，A值越小，因此距离S越远的节点，其标记被收集到的概率就越低，算法的收敛性越差。文献[20]中针对此种情况又提出了等概率包标记法(EPPM)，令pj表示到达S需要j跳的节点标记数据包的概率，对于每一个j,pj互不相同，但每个节点标记被汇聚节点收集到的概率都基本相等。该方法对所有节点更加平等，当恶意节点较远时，也可以更加迅速地将其定位。但该算法要求每个节点存储并不断更新自己的路由表，计算各自的标记概率，极大地加重了节点的计算、存储负担，对资源严格受限的WSN是不适应的。

2 层次式混合概率包标记算法

2.1 算法的基本思想

当传感器网络部署后，首先按照一定的算法对网络进行分簇，通过设定簇的规模，将一定数量的节点划归为一个簇，将每个簇看成一个大的“簇节点”，即整个网络由一些大的“簇节点”构成，每个“簇节点”内部又包含一定数量的传感器节点，在“簇节点”之间采用等概率包标记法，在“簇节点”内部采用基本概率包标记法，因此称该方法为层次式混合概率包标记算法(Layered Mixed Probabilistic Packet Marking, LMPPM)，既吸取两种算法的优点，又相对弥补两种算法的不足，整个网络被看成由一些大的簇节点 (V1,V2,…) 构成，每个簇节点内部又包含若干个节点 {V1(v1,v2…),V2(v5,v6… ) ,… } ，数据在节点间转发时，以簇为单位计算标记概率，簇内节点对其所转发数据包的标记概率满足

在 WSN中，分簇结构与平面结构相比，能够简化网络拓扑，优化节点的路由选择，减少节点间的干扰冲突，既能提高整个网络的通信效率，又能减少网络能量的消耗，从而延长整个网络的生存时间。由于“簇节点”的相对稳定性，又可以保持标记概率的相对稳定性，既减少了节点存储维护路由表和计算标记概率所产生的能量消耗，又较好的提高了溯源定位算法的性能。

2.2 算法描述

步骤 1 网络初始化。传感器节点布撒后自组织成网，根据预设的分簇算法，对节点进行分簇，选举簇头。汇聚节点定期向网络中广播hello消息，各簇头根据收到的 hello消息确定自身距汇聚节点的跳数；

步骤 2 确定标记概率。各簇头节点Vi按PVi= 1 /(c-Di)确定标记概率，其中c是常数，Di表示簇头节点Vi到汇聚节点的跳数。则汇聚节点收到簇头节点标记的概率为

即各簇头节点标记被汇聚节点收到的概率是相等的。簇头计算出标记概率后在簇内发布，簇内节点立即存储并使用该标记概率；

步骤3 标记方法。为防止恶意节点相互协作，在数据传输过程中修改数据，干扰追踪结果，引入散列消息验证码HMAC，即每个节点占用两个标记域，一个标记域用来存储加密后的节点标识，另一个用来存储相应的HMAC。节点以相应概率决定标记数据包，当标记域至少有两个为0时，则将自身标识添加到相应位置，当标记域均为非0时，则将标记域全部清空，并依次添加自身标识。

3 算法性能分析

基于文献[20]中对BPPM算法和EPPM算法的实验设置，本文着眼于具有大量节点的传感器网络实际应用系统(例如宁波citysee系统具有2000个以上的实际部署节点)进行分析。相对于小规模传感器网络，当传感器网络中包含大量节点时，其对于算法的功耗控制和收敛性有更高的要求，网络节点数与通信平均传输次数之间的关系如图1所示。

由于无线传感器网络在实际应用中多为大规模系统，为更好地对算法性能进行定量分析，文中假设恶意节点到汇聚节点需经过 32次数据转发(网络节点规模约为322=1024个)，网络初始化完成后，这32个中间节点被平均分布在8个簇内。考虑到无线传感器网络通常包含数量众多的节点，该假设作为符合算法模型的一个典型代表，其分析结果并不失一般性。下面从收敛时间、路由器负担、存储空间等方面，对BPPM算法，EPPM算法和本文提出的LMPPM算法进行分析比较。

假设iA表示数据包在节点vi处被标记且不被后续的节点所覆盖并最终到达汇聚节点的概率。在算法BPPM中，根据文献[20]中给出的概率计算公式np= 2 ，其中n为节点数，可得全网统一概率P=0.0625，则有

在算法 EPPM 中，按公式Pvi= 1 /(c-di),c＞di计算节点标记概率，此处c值取34，则有

根据2.2节中的描述，在LMPPM算法中，显然有AL32=PV8，

根据2.2节中步骤2,c等于34时，计算出各节点标记概率如表1所示。

表1 节点标记概率表

分别计算LMPPM, BPPM和EPPM 3个算法中ALi,ABi和AEi的值，结果如图2所示。

节点的标记到达汇聚节点的概率越大，说明汇聚节点重构出到达该节点的路径所需的数据包越少。从图2中可以看出，在13号节点之前，LMPPM算法明显好于BPPM算法，并逐渐趋近于EPPM。以下将进行具体分析：

(1)收敛性 在BPPM中，根据票券收集问题，受害者重构攻击路径所需的数据包数量的期望为E(N) ＜ ( lnd+O(1 ))/(p( 1 -p)d-1)，忽略常数项O(1)，分别将3个算法中的各节点标记概率代入上式，计算结果如图3所示。

从图3中可以明显看出，距离汇聚节点越远，LMPPM 算法的收敛性比 BPPM 算法提升得越明显，但对距离较近的节点，其期望值略大于BPPM算法，而EPPM算法收敛性则最好。

(2)最弱链问题 获得最弱链标记所需接收数据包数量的数学期望计算公式是E(N)PPM=，根据上述分析，3种算法为获得最弱链标记所需接收数据包数量的数学期望分别是

图1 不同规模无线传感器网络的运行特征

图2 节点标记到达汇聚节点概率图

图3 重构攻击路径所需数据包数量期望图

(3)计算与存储负担 BPPM 算法中节点只需储存一个固定概率值，无需更新维护路由以计算自身标记概率，故其计算与存储负担最小，EPPM算法需要节点储存自身路由信息并据此计算各自不同的标记概率，计算与存储负担最大。LMPPM 算法则介于两者之间，相对于BPPM增加了网络初始化阶段的分簇过程，但相对于分簇结构对 WSN整体性能的作用而言，该过程所带来的能量消耗是完全值得的。网络初始化完成后，仅需簇头节点计算标记概率，簇内其它节点只需存储簇头发布的标记概率，节点整体的计算负担相较 EPPM 有明显的降低，就本文所举例子来看，降幅约在3/4左右。而且簇结构的相对稳定性，也避免了因节点休眠引起的频繁更新路由信息所带来的计算与存储负担。

4 簇规模对算法的影响

为进一步研究算法的适用范围，从节点标记到达汇聚节点的概率、收敛性，最弱链3个方面对不同簇规模下算法的性能进行分析。m代表分簇数目，m= 1时相当于整个网络为一个簇，等同于 BPPM算法，m=32时相当于每个节点即为一个簇，等同于EPPM算法，刚才讨论了m=8时LMPPM算法的性能，下面进一步对m值分别等于2,4,16时的LMPPM算法性能进行分析。

4.1 到达汇聚节点的标记概率比较

节点的标记概率以及节点标记到达汇聚节点的概率计算方法与第3节相同，在不同簇规模下分别计算LMPPM, BPPM和EPPM 3个算法中ALi,ABi和AEi的值，得到如图4所示的计算结果。

分别对应于上一节分析的 BPPM,EPPM,LMPPM算法，可以明显看出：(1)不论簇规模大小，使用该算法都提高远距离节点的标记到达汇聚节点的概率；(2)随着分簇的细化，算法逐步逼近EPPM；(3)分簇规模对算法的影响并不显著，从 16个节点为一簇到2个节点为一簇，首个转发节点标记的到达概率并没得到显著提高。

4.2 收敛性比较

重构攻击路径所需的数据包数量按式(5)计算

将不同分簇情况下的标记概率代入式(5)，忽略常数项O(1)，计算结果如图5所示。

分析图5可以看出，即使网络只被分为两个簇，LMPPM算法在远距离节点上的收敛性都明显好于BPPM，随着分簇的细化，算法收敛性随之提升，但不同分簇规模下，算法的收敛性差距并不明显。

4.3 最弱链

图4 不同簇规模下节点标记到达汇聚节点概率图

图5 不同粗规模下重构攻击路径所需数据包数量期望图

即不论簇规模大小，LMPPM算法较之BPPM算法在最弱链问题上都有较大的改进，随着分簇细化，性能稳步提升，但升幅跃升不明显，比之EPPM算法还有较大差距。

综合上述分析可知，本文提出的LMPPM算法对分簇规模并没有特定要求。在不同簇规模下，算法性能均比 BPPM 算法有大幅度提升，比 EPPM算法更贴合网络实际，进一步提高了算法的适用范围。

5 结束语

本文提出的层次式混合概率包标记算法LMPPM结合了BPPM算法和EPPM算法的优点，与BPPM相比，在算法收敛性方面有了很大改善，与EPPM相比，较好地解决了节点计算与存储负担较重的问题。而这两种算法本质上是LMPPM的两个极端情况：当簇的规模设为最大值时，将整个网络看做一个簇，簇内节点都取同一标记概率，即等同于BPPM算法；当簇的规模设为最小值1时，将每个节点都是看做一个簇，簇间选择不同标记概率，即相当于EPPM算法。故本文所提出LMPPM算法体现的是在 WSN特征条件约束下，寻求整体最优的思想。通过对不同簇规模下算法性能的分析，验证了该算法的通用性，说明该算法具有更广泛的适用范围。

[1] Chen X Q, Makki K, Yen K,et al.. Sensor network security: a survey[J].IEEE Communications Surveys&Tutorials, 2009,11(2): 52-73.

[2] 刘萍, 李鹏飞, 谌屹, 等. 复杂电磁环境下的无线传感器网络战场电磁侦察与干扰应用研究[C]. 第 3届全国电磁环境效应与防护技术学术研讨会, 武汉, 2012: 28-31.Liu Ping, Li Peng-fei, Zhen Yi,et al.. Applied research on wireless sensor network battlefield reconnaissance and electromagnetic interference in complex electromagnetic environment[C]. The 3rd National Conference on Electromagnetic Environment Effects and Protection, Wuhan,2012: 28-31.

[3] Xu J, Zhou X H, and Yang F. Traceback in wireless sensor networks with packet marking and logging[J].Frontiers of Computer Science in China, 2011, 5(3): 308-315.

[4] 杨坤, 杨庚. 关于无线传感器网络中溯源方法的分析[J]. 计算机技术与发展, 2011, 21(7): 58-62.Yang Kun and Yang Geng. An analysis on traceback methods in wireless sensor networks[J].Computer Technology and Development, 2011, 21(7): 58-62.

[5] Snoeren A C, Partridge C, Sanchez L A,et al.. Hash-based IP traceback[C]. ACM SIGCOMM, New York, 2001: 3-14.

[6] Snoeren A C, Partridge C, Sanchez L A,et al.. Singlepacket IP traceback[J].IEEE/ACM Transactions on Networking, 2002, 10(6): 721-734.

[7] Sung M, Xu J, Li J,et al.. Large-scale IP traceback in highspeed Internet: practical techniques and theoretical foundation[J].IEEE/ACM Transactions on Networking, 2008,16(6): 1253-1266.

[8] Matsuda S, Baba T, Hayakawa A,et al.. Design and implementation of unauthorized access tracing system[C].SAINT,02 Proceedings of the 2002 Symposium on Applications and the Internet, Washington, 2002: 74-81.

[9] Bellovin S M. ICMP Traceback Messages[EB/OL]. http://tools.ietf.org/html/draft-ietf-itrace-04, 2000.

[10] Tseng Y, Chen H, and Hsieh W. Probabilistic packet marking with non-preemptive compensation[J].IEEE Communications Letters, 2004, 8(6): 359-361.

[11] Peng S H, Chang K D, Chen J L,et al.. A probabilistic packet marking scheme with LT code for IP traceback[J].InternationalJournalofFutureComputerand Communication, 2012, 1(1): 51-56.

[12] Belenky A and Ansari N. IP traceback with deterministic packet marking[J].IEEE Communications Letters, 2003, 7(4):162-164.

[13] Belenky A and Ansari N. On deterministic packet marking[J].Computer Networks:The International Journal of Computer and Telecommunications Networking, 2007, 51(10): 2677-2700.

[14] Foroushani V A and Heywood A N Z. Deterministic and authenticated flow marking for IP traceback[C]. The 27th IEEE International Conference on Advanced Information Networking and Applications (AINA2013), Barcelona, 2013:397-404.

[15] Tian H C and Bi J. An incrementally deployable flow-based scheme for IP traceback[J].IEEE Communications Letters,2012, 16(7): 1140-1143.

[16] Foroushani V A and Heywood A N Z. On evaluating IP traceback schemes: a practical perspective[C]. IEEE Security and Privacy Workshops, San Francisco, 2013: 127-134.

[17] Tian H C, Bi J, and Jiang X K. An adaptive probabilistic marking scheme for fast and secure traceback[J].Networking Science, 2013, 2(1/2): 42-51.

[18] Belenky A, Ansari N, and Jersey N. On IP traceback[J].IEEE Communications Magazine, 2003, 41(7): 142-153.

[19] Yang M H and Yang M C. RIHT: a novel hybrid IP traceback scheme[J].IEEE Transactions on Information Forensics andSecurity, 2012, 7(2): 789-797.

[20] 杨峰, 周学海, 张起元, 等. 无线传感器网络恶意节点溯源追踪方法研究[J]. 电子学报, 2009, 37(1): 202-206.Yang Feng, Zhou Xue-hai, Zhang Qi-yuan,et al.. A practical traceback mechanism in wireless sensor networks[J].Acta Electronica Sinica, 2009, 37(1): 202-206.