刘彩霞，黄廷磊

(1.桂林电子科技大学计算机科学与工程学院，广西桂林541004;2.桂林旅游高等专科学校现代教育技术中心，广西桂林541006)

位置信息对传感器网络的监测活动非常重要，没有位置的监测消息毫无意义，事件发生的位置和获取到信息的节点的位置是传感器节点监测消息中所包含的重要信息。如何确定无线传感器网络中节点的位置信息称为“节点定位”成为了必须解决的关键问题之一。所谓节点定位，就是根据少数已知位置的节点，按照某种定位机制确定自身的位置的过程。

根据定位机制，可将现有的无线传感器网络自身定位算法分为Range-based和Range-free两类。前者需要通过测量节点间点到点的距离或角度等信息;后者无须距离和角度信息，仅根据网络连通性等信息实现节点的定位。

DV-Hop算法是目前应用最广泛的非基于测距的定位算法之一，针对DV-Hop算法的改进算法已有很多，本文针对DV-Hop算法通信量大，且在恶劣环境下容易受到虫洞攻击影响，使定位精度大幅下降的情况，提出了一种改进的DV-Hop算法，通过合理地限制跳数，有效地减少了通信量;通过增加虫洞检测以及处理过程有效地减小了虫洞攻击的影响;通过虫洞链路位置确定以及受到攻击的节点对数量多少的检测，来选择性地对节点进行重定位过程，从而有效解决了大量虫洞攻击的影响。仿真验证表明，本文提出的定位方法，在同等条件下，明显减少了通信量，并在受到虫洞攻击时利用简单而有效的方法降低了定位误差，提高了定位精度。

1 DV-Hop及其已有改进算法

1.1 DV-Hop算法简介

DV-Hop算法是由美国的Niculescu等人提出的分布式定位系统中的一种算法。可分为如下步骤:

(1)锚节点先通过距离矢量路由广播自身信息，网络中所有节点记录下锚节点坐标及相应最小跳数，并和邻居节点交换信息。

(2)锚节点接收到来自其它所有锚节点的信息后，估算平均每跳距离。然后，每个锚节点广播自己的平均每跳距离，未知节点只接收离自己最近的锚节点的信息。

(3)当未知节点得到到3个及以上不同锚节点的距离后，运用三边测量法或极大似然估计法计算自己的位置。

1.2 已有改进算法

DV-Hop算法被提出后，对其改进算法已有很多［1-12］，其中，比较典型的文献［2］中，定位节点对接收到的多个信标节点的平均每跳距离进行算术平均处理;文献［3］根据定位节点记录的距离多个信标节点的跳数信息，对各信标节点的平均每跳距离值赋予了不同的权值;文献［4］也是采用加权平均思想，调整加权平均系数，修正全网平均每跳距离;文献［5］则是通过计算每个信标节点的平均每跳距离误差，从而计算出全网平均每跳距离误差，用来修正全网平均每跳距离。即已有成果大都是以增加节点的计算量或者通信量为代价来提高定位精度，文献［9］则是在减小通信量的基础上提高了定位精度。文献［9］对DV-Hop定位算法的改进是为了避免在网络拓扑结构不规则时，实际每跳距离的误差会随着跳数的增加而变大，估算的每跳距离也会与实际偏差越来越大。因此，文中算法限定了最大跳数 T，其中为正方形网络区域的边长，R为节点通信半径，P为锚节点的比例，A为每个未知节点定位需要的平均锚节点数，S为网络中节点总数，令未知节点接收跳数T范围内的包含校正值的锚节点信息，从而限制了未知节点的通信范围，减少了通信量。文献［9］中的算法与DV-验是否存在虫洞攻击，当时存在虫洞攻击，锚节点间用hop=1+来代替的跳数，其中R是Hop算法相比，减少了通信量，并提高了节点的定位精度，但是降低了网络的覆盖率。

上面文献中对DV-Hop算法的改进都是在安全环境下提出的，当网络环境不安全时，仅通过上面那些方法是无法保证定位性能的。由于DV-Hop算法依靠距离矢量交换估计距离，最容易受到虫洞攻击的影响，文献［10］中提出了一种抵抗虫洞攻击的方法，通过检测两个节点间的距离是否大于其最大通信半径来检节点的最大通信半径，(xi，yi)和(xj，yj)为两个锚节点的坐标;相似地，文献［12］中，作者提出了一种通过检测两个节点之间的跳数是否受到攻击的算法DWDV(Defend Wormhole Attack in DV-Hop)，具体方法是检测跳数是否小于最小跳数hopleast，如果跳数小于hopleast，则跳数是不合理的，则用最优化跳数hopopt替换受到攻击的跳数，hopopt是同网络区域相关的;文献［11］提出一种基于标签(Label-based DV-Hop)的DV-Hop安全定位算法，通过特定的策略将锚节点和未知节点加上不同的标签，从而将受到攻击的路由信息丢弃，但是寻找受到攻击的路由信息的过程比较复杂;Lazos等分别提出了 SeRLoc协议［13］、ROPE 协议［14］和 HiRLoc 协议［15］，虽然都一定程度上提高了定位精度，但是增加了大量的硬件成本、计算开销和通信开销，不适用于大规模的无线传感器网络应用。

2 虫洞攻击简介

虫洞攻击，是一种合谋攻击，攻击者可以建立一条不在彼此的通信范围内的链路，主要针对网络中带防御性的路由协议进行严重攻击。它在两个合谋恶意节点间建立一条延迟很小的隧道，即所谓的虫洞，攻击者在隧道一端把收到的包发送到隧道另一端，在隧道的另一端进行回放攻击。由于合谋的恶意节点通过一个私有的网络连接，而不是通过正常网络连接，所有又称这种攻击为隧道攻击。这种攻击能破坏路由竞争条件，使遭受攻击的节点收到一个错误的信息报，而丢弃了正确的包。另外，虫洞攻击还能导致路由拓扑混乱，通过虫洞转发包，可以使两个远距离的节点认为是相邻的。从而，使定位精度大为降低，给传感器节点的定位过程带来严重的影响。

3 本文改进算法

目前，对于DV-Hop算法在恶劣环境下的研究相对较少，而且已有的改进算法的性能还是不够理想，因此还需要进一步的研究。为了综合考虑算法性能，本文参考文献［9-10，12］提出一种新的基于DV-Hop的改进算法。

3.1 算法改进点

(1)为了减少通信量，对跳数T作了限制，此处参考文献［14］中的设置方法其中，假设网络区域为正方形，L是其边长，r为节点通信半径，P为锚节点的比例，S为网络中节点总数，A为每个未知节点定位需要的平均锚节点数。

(2)当检测到有虫洞攻击时，跳数信息必须进行处理，这样才可以避免虫洞攻击所造成的巨大影响，如果重新设置的跳数信息仍然不合理，也会造成定位误差的扩大，如何设置跳数信息是个具有挑战性的问题。

考虑到随着节点间跳数的增加，节点间实际距离与估计距离存在的误差越大，我们对跳数进行了特殊处理，当时，hop=，否则当＞3时，估计跳数不再是简单地对其进行取整，而是要加即 hop=，但 hop的最大值限制为T。

(3)对于存在虫洞攻击的情况下，为了确认虫洞链路的具体位置，我们又增加了一个信息广播过程，即在未知节点定位后将其位置信息广播向邻居节点，邻居节点接收到该信息之后，取出信息中包含的位置，通过判断是否大于r来检测两个节点之间是否存在虫洞链路，若存在，则标记该未知节点的id，并发反馈信息给该未知节点，同时发报警信号到网络控制器。

(4)在网络受到一定量的虫洞攻击时，我们选择性地增加了重定位过程，此时，系统控制器会根据接到的报警信号多少来决定是否需要重定位，若开始重定位，未知节点在执行定位过程时，不再需要进行安全检测，每个节点会查询首次定位时标记出的虫洞链路的位置，从而绕开它。

3.2 算法具体描述

该算法具体过程描述为:

(1)每个锚节点将其位置信息以数据分组的形式在网络中广播出去，分组的格式为{idi，xi，yi，hopi}，其中包含了该锚节点的id号、位置信息(xi，yi)以及跳数信息hopi，hopi初始值为0。

(2)接收到此分组的每个邻居节点将hopi改为hopi+1，如果此时 hopi＞T，则放弃该信息;否则执行(3)。

(4)当节点接收到一个idi号相同的数据分组时，便与自己数据表中相同idi号信息的hopi比较。若新的跳数小于数据表中已存在的跳数，则转向(3)，否则否则丢弃该数据分组，也不再进行转发。

(5)当泛洪过程结束后，每个锚节点计算自己的平均每跳距离。锚节点i可利用式(2)计算平均每跳距离:

(6)每个锚节点将自己计算的平均每跳距离以数据分组的形式广播至网络中，分组的格式为{idi，Ci，hopsi}，其中包含了该锚节点的idi号、平均每跳距离Ci以及被传播的次数hopsi。接收到此分组的邻居节点先判断hopsi是否大于或者等于T，如果是，则丢弃该分组;否则如果该节点是锚节点，则放弃该信息分组，如果不是则将hopsi加1并将该分组信息以{idi，Ci，hopsi}的形式存储到自己的数据表中，然后继续向新的邻居节点广播。当遇到idi号重复的数据分组时便丢弃。

(7)未知节点接收到平均每跳距离后，根据自己数据表中记录的跳数，按照Di=Ci*hopi来计算上一 个 矫 正 值 到每个锚节点的距离。

(8)未知节点得到3个或3个以上到不同锚节点的距离后，运用三边测量法或极大似然估计法计算自己的位置。

(9)首次定位结束后，计算出自己位置的未知节点，将自己的位置以数据分组的形式广播至网络中，分组的格式为{idi，xi，yi}。接收到此分组的邻居节点如果位置已知，则计算 L=是否大于 R，若是，则将 idi作一标记并单独保存下来，同时发出报警信号。

(10)未知节点广播完之后，网络总控制器根据接到报警信号的次数决定是否需要重新定位，若需要则启动重新定位程序。由于假定虫洞链路形成后不再改变位置，因而重定位过程中不需要再次进行安全检测，但是在信息分组泛洪过程中，接收信息的节点要检测信息是否来自首次定位时标记过的节点，若是，则直接放弃该消息，若不是，则将信息分组保存并在T跳范围内继续传播。

余下其他步骤与首次定位相同。为便于阅读，图1给出了算法流程图。

图1 算法流程图

3.3 算法分析

为了抵御虫洞攻击，本算法增加了虫洞检测过程，因而需要判断两个锚节点间距离是否合理，但由于锚节点的比例较小，因而这个过程计算量增加也较少;未知节点定位后广播自己的位置，周围节点需要通过计算来确定自己与该未知节点间是否存在虫洞链路，这也需要增加计算量，这个增加量与未知节点数量成线性关系;最后一部分是，当网络中受到虫洞攻击的节点对数量较多时，需要进行重新定位，从而导致计算量的增加。但在网络受到较少虫洞攻击或没有攻击时，该算法计算量的增加还是比较少的。

该算法在发现有虫洞攻击时，不是简单地通过取整来替代锚节点间的跳数而是通过一个公式，针对不同值进行不同的处理，可以较好地避免因网络拓扑不规则造成的距离误差;未知节点利用有限跳数范围内的锚节点作为参考节点，也有效缓解了网络拓扑结构不规则时累积跳距误差的影响，从而提高了定位精度。另外，该算法在抵御虫洞攻击时，仅仅通过简单的计算过程，没有增加任何的硬件成本，且在受到较多虫洞攻击时，可以通过重定位过程实现更准确的定位。

该算法增加了虫洞链路位置确认过程，在消息传播时可以绕开虫洞链路，从而为准确定位提供了保证，同时，在自定位结束后，节点传送所获得的信息时，也可以绕开虫洞链路，因此，该方法不仅能实现安全定位，而且在定位结束后的应用中也可以抵御虫洞攻击，起到了双重保护作用。

总之，在受到虫洞攻击时，该算法与文献［12］比，在网络拓扑结构不规则的情况下，也可以有效地提高定位精度，实现在虫洞攻击下的安全定位。

4 仿真验证

对于定位算法而言，衡量其性能的指标也不外乎定位误差、平均定位误差、定位精度、计算量、通信量等，本实验仿真的主要目的是验证在虫洞攻击存在时，提出算法对定位误差的控制效果，并验证算法通信量的大小，因而仿真环境仍然选择MATLAB R2007a，实验时，随机产生规定数目的点作为传感器节点的位置，锚节点则从产生的点中按规定比例取前面的点，然后通过判断节点间的距离是否大于节点的通信半径来确定节点间是否可以通信;虫洞链路仍然通过随机选择两个规定好距离的点来模拟，虫洞攻击则通过判断传感器节点与攻击者之间的距离是否小于攻击者的通信半径来确定，若小于，则表示传感器节点受到虫洞攻击。

4.1 验证1

本算法中设置了非线性的跳数替换公式，为了验证该公式的设置对定位误差的改进效果，我们用文献［12］中算法与本算法进行比较，每种算法仿真随机运行100次取平均值。

为了使算法适合大型网络使用，我们设仿真环境的主要参数为:500个节点随机部署在300 m×300 m的方形区域中，锚节点比例从5%到50%，节点通信半径R分别取20 m和40 m，虫洞链路的长度分别设为50 m，虫洞链路数从5到50递增。

在虫洞链路数为10，通信半径为R=20时，平均定位误差都随着锚节点比例的变化曲线分别如图2所示。

图2 平均定位误差随锚节点比例的变化曲线

分析上图，我们可以得出结论:平均定位误差随着锚节点比例升高而不断下降，当锚节点的比例超过30%时，定位误差的下降速度越来越缓慢，渐渐趋于平稳，但本算法表现出来的性能更好。

在通信半径为R=20 m，锚节点比例为20%，其中假设在虫洞链路数为20时，系统需要进行重定位，平均定位误差都随着虫洞链路数的变化曲线如下图3所示。

图3 平均定位误差随着虫洞链路数的变化情况

从图3我们可以看出，在通信半径和锚节点比例不变的情况下，文献［12］中算法的平均定位误差会随着虫洞链路数量增加不断升高，当虫洞链路数是50时，其平均定位误差接近节点通信半径的2倍，而使用本算法，平均定位误差则不会猛增，因此本算法可以更好地抵御虫洞攻击。

4.2 验证2

在仿真实验中，若我们假设在虫洞链路数超过20时，系统就需要重定位，则会造成通信量的增加，下面将本算法与DV-Hop算法进行比较，每种算法仿真随机运行100次取平均值。

我们设仿真环境的主要参数为:500个节点随机部署在300 m×300 m的方形区域中，锚节点比例为20%，节点通信半径R取20 m，虫洞链路的长度设为50 m，虫洞链路数从5到50递增;算法中设置的最大跳数限制T，由其公式计算出T＞1.465 8，实验中我们取T=3。仿真结果如图4所示。

图4 通信量随虫洞链路数的变化情况

我们按节点广播信息来计通信量，节点每广播一次，通信量就增加1，从图4可以看出，在锚节点比例和节点通信半径一定的情况下，随着虫洞链路数量的增加，DV-Hop算法需要的通信量不断减少;本算法的通信量则在重定位前后分别处于平稳状态，但在重定位后通信量会增加约1倍，却仍然比DV-Hop算法小很多;当锚节点比例或节点通信半径增大时，T会相应地减小，从而本算法的通信量也会随之略有减少。

5 总结

本文对DV-Hop算法进行了多方面改进，理论分析及仿真实验表明，本章算法不需要借助昂贵的硬件辅助，仅通过简单的计算来抵御虫洞攻击，不仅实现容易，而且算法性能较好，因而适合用于大规模的网络应用中。下一步我们将研究该算法在三维环境下无线传感器网络的定位应用。

［1］马祖长，孙怡宁.无线传感器网络节点的定位算法［J］.计算机工程，2004，30(7):13-14，48.

［2］彭刚，曹大元，孙利民.无线传感器网络节点定位机制的研究［J］.计算机工程与应用，2004.34:27-29.

［3］戴莹，王建平，张崇巍.无线传感器网络节点定位算法的研究与改进［J］.传感技术学报，2010，23(4):567-570.

［4］林金朝，陈晓冰，刘海波.基于平均跳距修正的无线传感器网络节点迭代定位算法［J］.通信学报，2009，30(10):107-113.

［5］林金朝，刘海波，李国军，等.无线传感器网络中DV-Hop节点定位改进算法研究［J］.计算机应用研究，2009，26(4):1272-1276.

［6］廖先林，耿娜，石凯，等.无线传感器网络节点自身定位算法［J］.东北大学学报:自然科学版，2007，28(6):801-804.

［7］赵清华，刘少飞，张朝霞，等.一种无需测距节点定位算法的分析和改进［J］.传感技术学报，2010，23(1):122-127.

［8］张佳，吴延海，石峰，等.基于DV-HOP的无线传感器网络定位算法［J］.计算机应用，2010，30(2):323-326.

［9］侯阿临，桃敏，沈杨，等.基于DV-Hop的免测距WSN定位算法研究［J］.长春工业大学学报(自然科学版)，2009，30(6):674-678.

［10］周启明，何勇.DV-Hop中虫洞攻击的仿真及其抵抗方法［J］.计算机工程与应用，2010，46(14):88-90.

［11］Wu Junfeng，Chen Honglong，Lou Wei，et al.Label-Based DV-Hop Localization Against Wormhole Attacks in Wireless Sensor Networks［C］//2010 Fifth International Conference on Networking，Architecture，and Storage，2010，7.

［12］Zhu Bin，Liao Junguo，Zhang Huifu.Defending Wormhole Attack in APS DV-Jop［C］//2008 Third International Conference on Communications and Networking in China，(Chinaeom2008，Aeeessionurnber:090111839491).

［13］Lazos L，Poovendran R，Capkun S.ROPE:Robust Position Estimation in Wireless Sensor Networks［C］//Proc.of IEEE IPSN，2005.

［14］Lazos L，Poovendran R.SeRLoc:Robust Localization for Wireless Sensor Networks［J］.ACM Transactions on Sensor Networks，2005，1(1):73-100.

［15］Lazos L，Poovendran R.HiRLoc:High-Resolution Robust Localization for Wireless Sensor Networks［J］.IEEE Journal on Selected Areas in Communications，2006，24(2):233-246.

［16］Hu Y C，Perrig A，Johnson D B.Wormhole Attacks in Wireless Networks［J］.IEEE Journal on Selected Areas in Communications，2006，24(2):370-380.