改进的抵制虫洞攻击的DV-Hop算法

乐小意，何泾沙

（北京工业大学 北京 100024）

近年来，无线传感器网络引起学术界和工业界的广泛关注，在传感器节点的定位算法中，分为基于距离 （Rangebased）和距离无关（Range-free）的两种类型的定位算法，在距离无关的算法中，DV-Hop定位算法是一个基于跳数来实现定位的算法，由于其良好的精度，对硬件要求低等特点，使其成为一个优秀的算法，在现实生活中得到了广泛的应用。

文中主要是提出了一种WARSL定位机制，提高了传感器网络节点定位的准确性。

1 DV-Hop的基本原理

DV-Hop定位算法是Drago Niculescu等人根据距离矢量路由原理提出的一系列分布式定位算法APS（Ad Hoc position System）中的一种，采用加权方法、求精算法来提高DV-Hop算法的性能。

DV-Hop算法[1]的定位过程主要分为3个阶段。第一阶段，计算未知位置节点与信标节点的最小跳数。信标节点向邻近的节点广播自己的信息，节点接收到相邻节点广播的信息，将跳数值加1后转发；第二阶段，估算每跳的平均距离。信标节点在获得其他信标节点的信息之后，通过获得信息中的跳数，使用公式（1）计算出其平均每跳的距离。然后将其作为一个校正值广播至网络中。校正值公式为：

其中（xi-xj），（yi-yj）是信标节点 i，j的坐标，hj是信标节点i与j之间的最小跳数。当接收到校正值后，节点根据自身与信标节点之间的跳数值来计算信标节点之间的距离。第三阶段，未知节点根据自身与3个或多个信标节点的距离，使用三边测量或极大似然法来计算自己的位置。

虫洞攻击，一般需要两个节点才能完成，是一种主要针对网络中带防御性路由协议的严重攻击。它在两个串谋恶意节点间建立一条私有通道，攻击者在网络中的一个位置上记录数据包或位置信息，通过此私有通道将窃取的信息传递到网络的另外一个位置。

在DV-Hop定位算法中，虫洞攻击会对DV-Hop定位过程产生严重的影响。如图1所示，A1和A2节点相互协作在网络中发起虫洞攻击。当B1进行泛洪时，他的广播信号会通过虫洞链路A1转发到A2，并进一步转发给S7，最终到达B2。因此，B2获得与 B1之间的最小跳数为 3（B1－＞S6－＞S7－＞B2），而在真实的情况下，B2与 B1之间最小跳数为 6（B1－＞S1－＞S2－＞S3－＞S4－＞S5－＞B2）。 所以，当 B2在估算平均每跳距离的时，其得到的结果会比实际值偏大。另外，未知节点进行定位时，首先需要估算其与各个信标节点之间的跳数，然而，S6通过虫洞链路直接可以传递信息到S7，接着到达B2。S6与B2之间的最小跳数为 2（S6－＞S7－＞B2），而实际两者之间的最小跳数为 7（S6－＞B1－＞S1－＞S2－＞S3－＞S4－＞S5－＞B2）。 因此 S6估算的其与 B2之间的距离会偏小。

图1 虫洞攻击对于DV－Hop定位过程的影响Fig.1 Wormhole attack for DV－Hop positioning process

在无线传感器节点的定位中，随着对于无线传感器网络研究的不断深入，学术界也提出了各种各样的解决方法，主要还是从以下3个途径进行考虑：①通过增加硬件设备或完善算法本身等手段来加强定位方法的强壮性；②利用信息加密或者身份认证保证节点的信息传递的安全性和可靠性；③引入一些安全模型机制，检测和排除一些恶意的攻击节点。

2 WARSL定位机制

在安全的无线传感器网络中，只有信标节点和普通节点两种类型的节点，信标节点携带GPS（Global Position System）定位组件等手段获得自身的位置信息，发送包含位置参照信息的信标报文，供其他的节点使用；而普通节点自身没有GPS定位信息，只能通过信标节点的位置信息通过定位算法。

在无线传感器网络中，根据虫洞攻击所处的情况不同，虫洞攻击的分布主要有以下3种情况[2]：①信标节点与信标节点之间；②信标节点与普通节点之间；③普通节点与普通节点之间。通过分析，第二种情况和第三种情况可以采用相同的方式进行处理，因而在本文中，主要对于信标节点和信标节点，信标节点和普通节点的虫洞攻击进行讨论。

虫洞攻击在如下的环境中讨论，所有的信标节点和普通节点都是可信的，不会被恶意节点捕获。WARSL的定位机制是通过检测传感器节点的跳数值是否符合三角形法则或者最低跳数值法则来检测传感器网络中是否存在虫洞攻击，在有攻击的局部网络中，矫正不合理的跳数值。定位机制的运用在信标节点之间和信标节点与普通节点之间的原理不一样，下面将会对其做详细的解释。首先我将引入以下几个参数以便之后的说明。

d（A，B）:节点 A 和节点 B之间的距离；

r:传感器节点信息传播的半径；

Hopleast（A，B）:节点 A 和节点 B之间的最小跳数值

Hop（A，B）：节点 A和节点 B之间的跳数值

Hopopt（A，B）节点A和节点 B之间的最优值

如图2所示，在安全的传感器网络中，所有的传感器节点在一条直线节点之间的跳数值是最小。任何一对邻居节点的距离等于节点传播的半径[3]。两个节点间的最小跳数值按照公式（1）计算。

图2 节点间最小跳数值Fig.2 Minimum hop count between nodes

规则1虫洞攻击在信标节点与信标节点之间

如图3所示，A1和A2是两个恶意节点，A1和A2之间形成一条虫洞链路，B1和B2是两个信标节点。在正常情况下，B1和B2之间的跳数值为7，在有虫洞攻击的情况下，B1和B2之间的跳数值为3。由于信标节点可以计算出自己的位置，因而如果 Hop（B1，B2）＜Hopleast（B1，B2），则说明信标节点 B1和信标节点B2之间存在着虫洞攻击。则用最优值来替换阶段出来的值。 Hop（B1，B2）=Hopopt（A，B）。 在这种情况下，Hopopt（A，B）的值根据公式（2）来计算。 例如，假如 Hop（B1，B2）=3，Hopleast（B1，B2）=5，Hopopt（A，B）=6，由于 3＜5，则 Hop（B1，B2）=6。

规则2虫洞攻击在信标节点与普通节点之间

如图4所示，A1和A2是两个恶意节点，A1和A2之间形成一条虫洞链路，B1和B2是两个信标节点，S1是需要定位的普通节点。在正常情况下，S1在定位过程中，获取B1广播过来的位置信息，计算出其与B1之间的跳数值为5；在虫洞攻击的情况下，S1与B1之间的跳数值为3。在这种情况下，如果要检测出是否存在虫洞攻击，需要借助另外一个信标节点，如图中的信标节点B2，而且B2和S1之间没有虫洞攻击，d（B1，S1）和 d（S1，B2）和 d（B1，B2）之间构成一个三角形，要满足三角形三边的规则。即

如果不同时满足上面的关系式，则说明这条链路中存在着虫洞攻击。 在这种情况下，Hopopt（B1，S1）的值根据公式（3）来计算，Hop（B1，S1）=Hopopt（B1，S1）。 例如：Hop（B1，B2）=2，Hop（B2，S1）=5，Hop（B1，S1）=3。 则 Hop（B1，S1）=Hopopt（B1，S1）=10。

图4 虫洞攻击在信标节点和普通节点之间Fig.4 Wormhole attack between beacon node and common node

因而，如果将WARSL定位机制应用于DV-Hop定位算法中，其步骤如下[4]：

1）信标节点将自己的位置信息以分组的形式广播出去，信息的格式为 {idi，（xi，yi），Hopi}， 其中 idi表示信标节点的编号，（xi，yi）表示信标节点的坐标值， Hopi表示跳数值，初始值为0。

2）节点获得信标节点广播的信息，首先判断是否来自于一个信标节点，如果来自于同一个信标节点，则与已经保存的跳数值进行比较，保存最小的跳数值；如果不是来自与同一个信标节点，则保存跳数值。

3）如果该节点是信标节点，那么根据规则1，两个信标节点的之间的跳数值是否小于信标节点之间的最小值，如果信标节点之间的跳数值小于最小值，那么这两个信标之间存在着虫洞攻击，使用公式（2）替换测量信标节点的跳数值；反之，信标节点之间的跳数值是可信的。如果该节点是普通节点，那么根据规则2，判断节点间是否满足三角形法则，如果不满足的情况下，则说明信标节点与普通节点之间存在着虫洞攻击，使用公式（3）替换测量出来的跳数值。反之，信标节点与普通节点之间的跳数值是可信的。

4）节点保存可信的信标节点的跳数值，并将跳数值加1广播出去。

5）当泛洪过程结束后，每个信标节点根据公式（1）来计算自己的平均每跳距离。

6）每个信标将自己的平均每跳距离的消息广播到网络中，消息的格式{idi，Hopdi}，idi表示信标节点的编号，Hopdi表示信标节点的平均每跳距离。

7）未知节点接收到平均每跳距离后，根据自己数据表里记录的信标节点的跳数，找到一个离自身最近的信标节点，将该信标节点的平均每跳距离作为整个传感器网络的平均每跳距离。根据d=Hop×Hopd，计算未知节点与每个信标节点的距离。

8）当未知节点得到3个或者3个以上不同信标的距离后，可以使用三边测量法或极大似然估计法计算自己的位置。

为了更好的说明整个算法的流程，图5给出了算法的流程图。

图5 WARSL算法流程图Fig.5 Flowchart of algorithm WARSL

3 实验结果

对于定位算法而言，衡量其性能的指标主要包括定位误差、平均定位误差、定位精度、计算量、通信量等[5]，本实验的主要的目的是验证在虫洞攻击存在的情况WARSL定位算法能够提高定位的准确性，因而在本实验中采用平均定位误差来衡量WARSL定位算法的性能。平均定位误差的计算方法如下：

式中：（xi，yi）表示未知节点i的定位坐标；（x′i，y′i）表示未知节点i的真实坐标，N表示未知节点的个数。

实验环境假设[6]：100个节点随机的部署在300 m×400 m的方形区域中，节点的通信半径为30 m，虫洞链路数为10。平均定位误差随着网络中信标节点的比例关系如图6所示。

图6 平均定位误差随着信标节点的比例的变化Fig.6 Average position error with the change of the proportion of beacon nodes

从图6可以看出，当信标节点数量的在网络所占的比例较小时，在有虫洞攻击的环境下，WARSL定位算法能够较大的提高节点定位的准确度，当信标节点的数量比例达到20%之后，WARSL定位算法与DV-HOP定位算法的定位的准确度相差不大。但是整体而言，WARSL定位算法还是更加可靠。

4 结束语

文中针对DV-Hop定位算法，引入了一种新的检测机制，此机制通过一些检验规则能够很好的检测虫洞攻击，从而增强了定位结果的准确性。本方法不需要借助昂贵的硬件辅助，仅通过简单的计算来抵制虫洞攻击。

[1]周明伟，刘渊.WSNs中 DV-hop定位算法的安全增强研究[J].计算机工程与应用.

ZHOU Ming-wei，LIU Yuan.The security enhanced research of DV-hop localization algorithm in WSNs[J].Computer engineering and applications.

[2]Yanchao Niu，D.G.S.G.， A Robust Localization in Wireless Sensor Networks against Wormhole Attack [J].Journal of networks，2012（1）:187-194.

[3]Honglong Chen，W.L.A.Z.， Conflicting-Set-Based Wormhole Attack Resistant Localization inWireless Sensor Networks[J].Ubiquitous Intelligence and Computing-6th International Conference，2009：296-309.

[4]Khan Z A，M.H.I.， Wormhole Attack A new detection technique[C]//2012 International Conference on Emerging Technologies，2012：276-281.

[5]Nabila Labraoui，M.G.A.M.， Secure DV-Hop localization scheme against wormhole in wireless sensor networks[J].EuropeanTransactionsonTelecommunications，2011：303-316.

[6]刘彩霞，黄廷磊.WSN中抵御虫洞攻击的改进的DV-Hop算法研究[J].传感技术学报，2011（10）:1473-1478.

LIU Cai-xi，HUANG Ting-lei， A improvemented against wormhole attacks in WSNs[J].Journal of sensing technology，2011（10）:1473-1478.