WSNs中DV-hop定位算法的安全增强研究

周明伟，刘渊

江南大学数字媒体学院，江苏无锡214122

1 引言

传感器的感知功能以及节点间的通讯能力，为无线传感器网络提供了广阔的应用前景。作为一种无处不在的感知技术，无线传感器网络广泛应用于军事、环境监测和预报、智能家居、健康护理、建筑物状态监控、复杂机械监控、城市交通、空间探索以及机场、大型工业园区的安全监测等领域。随着无线传感器网络的深入研究和广泛应用，无线传感器网络将逐渐深入到人类生活的各个领域。无线传感器网络采集的数据往往需要与其位置信息相结合才有意义，因此，确定事件发生的位置或获取信息的节点位置是无线传感器网络最基本的功能之一，对无线传感器网络应用的有效性是至关重要的，当一个传感器节点检测到一个紧急事件时，它的位置信息应该快速并准确地被识别，不知道传感器位置的遥感数据是没有意义的[1]。一个直接的解决办法是为每一个传感器节点配置一个GPS接收器。这样就可以准确提供它们的位置信息，然而为每个节点都配备GPS定位组件将消耗大量的成本，不符合最小化成本的目的。因此只能为一小部分节点配备GPS组件，这些配备GPS的节点称为信标节点或锚节点，未知位置的节点称为未知节点或待定位节点，待定位节点可以利用附近的多个锚节点的位置信息来估计自身的位置。

WSNs中节点定位技术越来越受到研究者的关注，并且提出了许多基于测距和基于非测距的方案。基于测距的技术需要测量相邻节点间的绝对距离或方位来计算未知节点的位置，包括信号强度测距法（Received Signal Strength Indicator，RSSI）[2]，到达时间差（Time Difference On A rrival，TDOA）测距法[3]，到达时间（Time Of A rrival，TOA）定位法[4]和到达角（Angle Of A rrival，AOA）[5]定位算法等。基于非测距的定位技术利用节点间的估计距离计算节点位置，包括质心（centroid algorithm）定位算法，凸规划（convex optim ization）定位算法，以三角形内的点近似定位（APIT）算法[6]，基于距离矢量计算跳数（DV-Hop）定位算法[7]等。但提出的这些定位算法仅能够在环境较稳定，未受到攻击者破坏的理想环境中进行，但由于位置信息是无线传感器网络服务的重要部分，设计一个具有抵御攻击的安全定位方案尤为重要。然而，任何一种安全措施都需要消耗一定的资源包括节点自身的计算和能源开销以及网络通信开销等，因此，对于一个具体的定位系统，还要考虑系统的应用背景、攻击模型、安全需求和资源条件等多种因素进行折中，以确定其防御策略[8]。

考虑到传感器节点自身条件的限制，本文在非测距的DV-Hop定位算法的基础上，增加了一些安全机制。DV-Hop定位算法是一种典型的利用跳数来定位未知节点的非测距方法，对节点的硬件要求低，实现简单。同时，本文选取虫洞攻击作为抵御目标，因为虫洞攻击不需要损坏任何节点也不需要破译密钥便可以实施攻击，因此，仅通过密钥管理技术来抵御虫洞攻击是不够的。

本文研究的安全方案是在对节点进行定位前，利用简单的三角不等式规则对信标节点的合法性进行检测，然后在DV-Hop定位算法的第一步进行改进，利用邻节点间的RTT属性值增加检测虫洞攻击的模块，若检测出虫洞攻击，则通过调整通信节点间的跳数来抵御虫洞攻击。最后，仿真实验证明了该方案对恶意信标节点、虫洞攻击的检测以及抵御的有效性。

2 DV-hop定位方案

2.1 DV-hop定位算法

距离向量算法（DV-hop）使用平均每跳距离计算实际距离，对节点的硬件要求较低，实现简单，它的定位过程如下：

（1）计算未知节点与每个信标节点的最小跳数

信标节点向邻居节点广播自身位置信息的分组，其中包含跳数字段，初始化为0，接收节点记录到每个信标节点的最小跳数，忽略来自同一个信标节点的较大跳数的分组，然后将跳数值加1，并转发给邻节点，通过这个方法，网络中的所有节点能够记录到每个信标节点的最小跳数。

（2）计算未知节点与信标节点的实际跳段距离

每个信标节点根据第一阶段中记录的其他信标节点位置信息和相距跳数，利用公式（1）估算平均每跳的实际距离：

其中(xi，yi)，(xj，yj)是信标节点i，j的坐标，hj是信标节点i与j之间的跳段数。

然后信标节点将计算的每跳平均距离用带有生存期字段的分组广播到网络中，未知节点仅记录接收到的第一个平均每跳距离，并转发给邻居节点，这个策略确保了绝大多数节点从最近的信标节点接收每跳平均距离值。未知节点接收到平均距离后，根据记录的跳数，计算到每个信标节点的距离。

（3）利用三边测量法或者极大似然估计法计算自身位置

未知节点利用第二阶段中记录的到各个信标节点的跳段距离，用三边测量法或极大似然估计法计算自身坐标。极大似然估计法在无线传感器网络定位计算中被广泛使用。假设与未知节点D(x，y)能够直接通信的信标节点有N个且坐标分别为(x1，y1)，(x2，y2)，…，(xn，yn)，并且假设通过测距技术已知它们到节点D的距离分别为d1，d2，…，dn，则存在如下关系：

由第一个方程开始逐一减去最后一个方程，则得到：

将式（3）表示为：

最后，使用标准的最小均方差估计法即可以估算得到未知节点D的坐标：

2.2 DV-hop定位算法的虫洞脆弱性分析

虫洞攻击是通过两个串谋恶意节点n1、n2建立起一条高质量高带宽的私有通道，攻击者在网络中的节点n1位置上记录数据分组或位置信息，通过此私有通道将窃取的信息传递到网络的另一个位置节点n2处。由于虫洞攻击采用高质量高带宽的私有通道，所以通过私有通道传递的数据分组比通过正常多跳路径传递的数据分组要早到目标节点。在这种情况下，即使网络通讯间存在信任和身份认证，攻击者无密钥仍能够进行攻击。虫洞攻击对DV-hop定位算法的影响主要表现在两方面：

（1）引起定位误差

虫洞攻击可以极大恶化DV-hop的定位过程，在DV-hop定位算法的第一阶段，虫洞攻击使得信标节点间的跳数异常，这直接影响了算法第二部计算平均跳段的过程，最终导致整个定位系统失效。如图1所示，在恶意节点A1和A2之间存在一条虫洞链，A1接收来自于节点B1的信息，然后将信息通过隧道转发给A2，A2将信息重放给B2，正常情况下，信标节点B1和B2之间有5跳，但在存在虫洞链的情况下，跳数变为2跳，导致B2对平均每跳的距离作出错误的估算。同样，位于B2附近的节点也将会得到一个较小的距离B1的跳数，这样使用三边测量法或者最大似然估计法计算坐标的时候将会得到一个具有较大误差的位置估计结果。

图1 虫洞攻击对系统的影响

（2）能量消耗

在存在虫洞攻击的情况下，节点不得不传送更多的重传信息，这样消耗了更多的能量，这对于一个资源有限的网络来说是致命的。

总之，虫洞攻击因其实现简单，对基于非测距的定位系统破坏性极大，因此，本文以虫洞攻击作为研究对象。

3 系统模型

本文提出的安全定位方案，主要由三部分构成，如图2所示。系统首先检测并移除非法或恶意的信标节点，待确定了信标节点的合法性之后，检测网络中是否存在虫洞攻击，然后根据得到的信息采取不同的定位方案。

图2 安全定位系统模型

3.1 检测并移除非法信标节点

由于无线传感器网络中未知节点是根据信标节点发送的位置信息来完成自身的定位过程，故信标节点的有效性直接关系到定位结果的有效性。若信标节点被恶意节点破坏或者是由恶意节点伪造的节点，那么所有的基于信标节点的定位系统都将失效。因此，本文研究的安全方案在定位之前添加了检测并移除非法信标节点的模块。考虑到传感器节点的自身资源的有限性，该模块使用了一个简单的规则——三角不等式规则来检测信标节点的合法性。

设N为待检测节点，B1和B2是一对待检测的信标节点，这三个节点构成了一个三角形ΔNB1B2，根据三角不等式规则，第三边必小于另两边之和并且大于另两边之差。即在ΔNB1B2中有：为B1与B2之间的距离，d1、d2为检测节点N分别到B1、B2节点的距离，利用接收到的信标信号，通过物理方法可以得到。若检测节点N发现d12不满足其中的任一条件则将认为B1、B2为恶意节点。然后检测节点N将检测结果发送给基站，基站将建立一个表格用于保存每个信标节点的ID以及被标记为恶意节点的次数统计。当某个节点被标记的次数超过阈值t时，则确认该节点为恶意节点将其从网络中移除。

在该方案中采用了一个简单的投票机制，假设网络中共有n个信标节点，每两个节点组成一个待检测对。当检测节点检测到信标节点为恶意节点时则投一票，最后将每个信标节点的票数累加。可知，一个信标节点获得最多票数为n-1，最少为0，即n-1代表着最不可信节点，而0代表着最可信节点。阈值t取为最大值与最小值的平均值，即

3.2 抵御虫洞攻击模型

在确定了信标节点的合法性后，接下来对网络中存在的非法节点进行检测。本文以虫洞攻击为研究目标，因其容易实现并且对定位方案具有很大影响，对定位系统是一个很大的挑战。同样考虑到传感器节点自身的有限资源，本文提出的安全方案是在DV-hop定位方案的第一阶段进行改进，利用节点间完成一次通信的时间RTT（Round Trip Time）[9]来检测网络中存在的虫洞链，若发现异常，则通过修改节点间跳数来降低虫洞攻击对定位系统的影响。抵御虫洞攻击算法流程图如图3所示。

3.2.1 RTT分析

图3 算法流程图

RTT是指数据包从一个节点，经过无线网络传递到另一节点的往返时间，RTT可由接收消息时间Rrec减去消息发送时间Rsend求得，即RTT=Rrec-Rsend。假设节点s1与邻居节点s2进行通信，在正常情况下，节点s1与节点s2的RTT值为2p。如果s1与s2之间建立的直接连接是由虫洞攻击形成的，那么往返时间RTTwormhole=2(p+w+p)=2(2p+w)。其中w为数据包在虫洞链形成的隧道中传递时消耗的时间，因此，可以认为存在虫洞链时，节点间的RTT至少是正常链接情况下的2倍，虽然RTT值不仅受到恶意节点存在的影响，还和网络的可用带宽、瓶颈带宽、是否拥塞等有关，但是理论上在同等状况下的网络环境中以上关系是不会发生改变的，即在w远小于p的情况下仍然成立。

3.2.2 抵御虫洞攻击算法的具体描述

（1）信标节点Sn发送包含自身位置信息的分组，其中包含跳数字段，初始化为0，同时记录发送时间Rsend。

（2）接收到信息的邻居节点发送应答消息给节点Sn，Sn接收应答消息并记录接收时间Rrec。计算Sn与每个邻节点的RTT=Rrec-Rsend，并对所有RTT求和得RTTtotal。

（3）计算节点Sn与所有邻节点Si完成一次通信的平均时间avgRTT=RTTtotal/i。

（4）比较每个RTT(sn，si)是否大于k×avgRTT，其中，n是节点具有的邻节点总数，m为存在的虫洞链的最多数量。若大于，则认为Sn与Si之间的链路为虫洞链路，则执行步骤（5）；若不大于，执行步骤（6）。

（5）修改Sn与Si之间的跳数统计，具体方法将在下文中介绍。

（6）判断网络泛洪是否结束，如果结束则进行DV-hop算法的其他阶段，否则返回步骤（1）继续寻找下一跳的邻节点。

本方案可以很大程度地降低虫洞链对定位系统的影响，这将在后文实验部分给予证明。

3.2.3 修改受虫洞链影响的跳数

当检测到有虫洞攻击时，跳数信息必须进行处理，这样才可以避免虫洞攻击所造成的巨大影响，如果重新设置的跳数信息仍然不合理，会造成定位误差的扩大。如何设置跳数信息是个具有挑战性的问题。本文利用文献[10]的方法，只不过在取整过程中，本文采用向上取整的方法，由于能够相互通信的节点必定在通信半径的范围之内，不能够相互通信的节点只能够通过第三方进行中转。对两信标节点之间的距离与通信半径的商采用向上取整的方式来确定两点之间的最小跳数更加合理，即当≤3时，跳数hop为：

3.3 算法分析

为了能够抵御虫洞攻击实现安全定位，本方案使用了两个简单的算法，首先检测并移除非法的信标节点，因为未知节点的定位与信标节点发送的位置信息紧密相关。检测非法信标节点时，使用一个特定的检测节点N，利用三角不等式规则对信标节点的合法性进行判断，这个待检测节点N要确保其合法性，实际环境中可以采用一个特制的节点，由于三角不等式规则不需要复杂计算并且此过程并未增加过多的硬件要求，只需要一个性能良好的节点来完成。因此，该方案不会增加传感器网络的负担。

待确定了信标节点的合法性后，在信标节点向网络中发送包含自身位置信息的过程中，通过计算与邻节点之间的RTT值来判断通信节点间是否存在虫洞链，对RTT值的计算不需要很大的存储空间，因此该过程不会消耗过多的资源。在检测到虫洞链时，通过修改节点之间的跳数来最小化虫洞攻击对定位系统的影响，该过程只有在检测到虫洞链存在时才会执行，否则按原始算法进行处理。因此，该方法充分考虑到节点资源的有限性，并且没有增加任何的硬件成本。

4 仿真结果分析

4.1 恶意信标节点的检测

本节验证基于三角不等式规则检测恶意信标节点的有效性。设无线传感器网络布局在500m×500m的区域内，如图4所示，网络中设置一个检测节点N，节点间通讯半径为r，以检测节点N为圆心(x0=y0=0)，半径为l的圆内设置n个信标节点，保证节点之间都可以相互通信。假设恶意信标节点谎报的位置与真实位置偏移距离为a，为了保证实验效果，实验中假设偏移方向为水平方向，即Δx=a，Δy=0。实验中设置n=11，c分别取值2、5、8，阈值t=5，a∈(0.1r，2r)，r=50m，用C程序来进行实验，所有信标节点到检测节点N的真实距离通过公式计算得到。实验结果如图5所示。

图4 网络中节点布局

图5 偏移量a与系统识别恶意节点的关系

（1）由图5可知，当恶意节点的偏移距离a较小时，该方案不能够准确地将所有恶意信标节点识别出来，当偏移距离a≥r时该方案才能发挥理想作用，将大部分恶意节点准确识别出，这说明恶意节点偏移量的大小对该方案的有效性有直接的影响。但在接下来的实验将证明若偏移量a较小时，其对定位系统的定位精度影响是很微弱的，即攻击者若想对定位系统造成较大的影响必须将偏移量a设置得足够大。但在a值较大的情况下，本方案可以将大部分恶意节点识别出。因为实际环境中，存在即使信标节点偏离实际位置很远，也可能满足三角不等式规则的情况，这会对识别结果造成一定的影响，如何避免此影响的研究将是今后的工作。

（2）该网络环境中设置了11个信标节点，当恶意节点的数目较少时，即小于n/2时，系统不会发生误报的现象，但恶意节点的数量超过节点总数的一半后，如c=8时，系统会将良性信标节点误报为恶意节点，即该方案对恶意节点的数量有一定的要求，若系统中存在过多的恶意节点，则会使系统失效，引起误报的情况。

4.2 偏移量大小对定位效果的影响

网络布局如图6所示，在200m×200m的区域中，布置10个节点，通讯半径为50m，其中B1、B2、B3为信标节点，且B3为恶意信标节点，选定节点N为待定位节点，已知B1到B3之间的距离为B1B3=125，B1B2=111.8，B2B3=125，B1与B3通信需要的最小跳数是3，B1与B2的为4，B3与B2的为4。因为待定位节点通信只需要1跳，根据DV-hop算法可知，节点N接收从B3获得的矫正值，而丢弃从B1、B2获得的。矫正值为(125+125)/(3+4)=35.71，因此它与3个信标节点之间的距离分别为NB1=3×35.71，NB2=3×35.71，NB3=1×35.71，使用三边测量法可以得到未知节点的位置信息，恶意节点会对矫正值产生影响，导致整个定位过程出现误差。本实验使用C程序来实现，实验结果如表1所示，其中定位误差为误差与通信半径之比。

图6 无线传感器网络布局

由表1可以看出，当偏移量a值较小时，其引起的定位误差在可以接受的范围内，仅为通信半径的0～30%之间。而当a值较大时，如1r附近，其引起的误差较大，对定位精度有着较大的影响。因此，得出结论，攻击者若企图破坏定位系统，a值必须足够大。

4.3 抵御虫洞攻击的有效性

本部分实验在Linux环境下，使用NS2模拟网络环境，然后对生成的trace文件进行分析，验证该方案检测以及抵御虫洞攻击的有效性。虫洞攻击由两个具有远大于正常节点的通信半径的特殊节点来模拟，并在两个恶意节点间用一条有线链路表示虫洞链。无线传感器网络布置在一个500m×500m的区域中，均匀分布100个传感器节点，其中包括信标节点和普通节点，节点的通信半径设置为50m。

表1 偏移量对定位精度的影响

在不存在虫洞攻击的情况下，随着信标节点的增长，定位精度的变化如图7所示。随着信标节点的增加，定位误差逐渐下降，当信标节点达到一定数量后，定位精度趋于平缓。

根据图7，选取15个信标节点来实验随着虫洞链的增加，DV-hop基本算法与使用本文提出的安全定位方案的定位误差之间的对比。假设每个虫洞链都可以成功截获数据包，并通过隧道传递给虫洞链另一端的恶意节点。实验过程中选定一个待定位节点作为实验对象，并人工设定虫洞链的位置，以便对定位结果造成直接影响，实验结果如图8所示。

图8 定位误差随着虫洞链数变化的情况

从图8可以看出，随着虫洞链数量的增长，由常规定位算法计算出未知节点的定位误差增长很快，在虫洞链数量为2时，定位误差超过了通信半径的一半以上，定位结果已经接近无效。由此可见，虫洞攻击对系统的定位效果有极大的影响，但本文提出的方案可以有效地减弱虫洞攻击对定位系统的影响。随虫洞链数量的增长，本文提出的安全定位方案的定位误差并未呈现急剧增长的局面，而是很好地控制了误差的增长，使得定位误差仍然在可以接受的范围内。

文献[11]中提出了一种通过检测两个节点之间的跳数是否受到了攻击的算法DWDV（Defined Wormhole attack in DV-hop），具体的方法是首先检测节点间跳数是否小于最小跳数hopleast，如果小于，则表明该跳数是不合理的，那么就用最优化跳数hopopt替换受到攻击的跳数，hopopt是同网络区域相关的。将本文提出的算法与该算法进行对比，结果如图9所示。

图9 与文献[11]中算法效果对比图

从图9中可以看出，在虫洞链数量较少的时候，文献[11]中的算法同样发挥出较好的效果，但随着虫洞链比重的增加到4个以上的时候，定位误差会急剧上升，而本文提出的算法仍然能够保持较好的定位效果。

5 总结

本文分析了常用于无线传感器网络节点定位的算法，其中大部分算法在理想的环境中不存在恶意攻击的情况下发挥了良好的定位性能，但随着技术不断更新，社会复杂化的加剧，显然已有的算法不能发挥其应有的价值，尤其是在对安全性要求较高的环境如战场中，在敌人采用恶意节点攻击的情况下，如何能够及时识别恶意节点并采取相应措施，显得尤为重要。因此，研究了一种安全的定位方案，由于虫洞攻击的特殊性，本文用其作为抵御对象，同时考虑到节点自身资源的限制，本文在实现简单，对硬件要求低的基于非测距的定位算法DV-hop的基础上增加了安全模块，并在运行定位模块之前增加检测并移除恶意信标节点的过程。理论分析及仿真实验证明，提出的安全定位方案不需要借助昂贵的硬件辅助，实现简单，在检测恶意信标节点以及抵御虫洞攻击上具有良好的效果。本文研究对象限制在静态传感器节点上，下一步的重点是研究能够适用于大规模随机性布置节点的动态网络节点定位的安全方案。

[1]Rabaey J M，Ammer M J，da Silva J L，et al.PicoRadio supports ad hoc ultra-low power w ireless networking[J].Computer，2002，33（7）：42-48.

[2]Girod L，Bychovskiy V，Elson J，et al.Locating tiny sensors in time and space：a case study[C]//Proceedings of the 2002 IEEE International Conference on Computer Design：VLSI in Computers and Processors，Freiburg，2002：214-219.

[3]Girod L，Estrin D.Robust range estimation using acoustic and multi modal sensing[C]//Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems，Maui，2001：1312-1320.

[4]Harter A，Hopper A，Steggles P，et al.The anatom y of a context-aware application[C]//Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking，Seattle.[S.l.]：ACM Press，1999：59-68.

[5]Nicolescu D，Nath B.Ad-hoc positioning system using AoA[C]//Proceedings of IEEE International Conference on Computer Communications，San Francisco，2003.

[6]He T，Huang C，Blum B M，et al.Range free location schemes for large scale sensor networks[C]//Proceedings of ACM International Symposium on Mobile Ad-hoc Networking&Computing，Maryland，2003.

[7]Niculescu D，Nath B.DV based positioning in Ad hoc networks[J].Journal of Telecommunication Systems，2003，22（1/4）：267-280.

[8]Labraoui N，Gueroui M，A liouat M，et al.Data aggregation security challenge in Wireless Sensor Networks：a survey[C]//Proceedings of the 5th IEEE International Symposium on Wireless Pervasive Computing（ISWPC），2010：325-330.

[9]Labraoui N，Gueroui M.Secure range-free localization scheme in Wireless Sensor Networks[C]//Proceedings of the 10th International Symposium on Programming and Systems（ISPS），2011：1-8.

[10]Liu Caixia，Huang Yanlei.Research on improved DV-hop algorithm against wormhole attacks in WSN[J].Chinese Journal of Sensors and Actuators，2011，24（10）.

[11]Zhu Bin，Liao Junguo，Zhang Huifu.Defending wormhole attack in ASP DV-Hop[C]//Proceedings of the 3rd International Conference on Communications and Networking，2008.