基于DV—Hop大型中心区域的改进定位算法

李博文+李盛欣

摘要：研究了一些目前在无线传感器网络中存在的定位技术，基于最小化洪泛法和能量消耗及便于信标节点的部署，提出了针对大型中心区域基于DV-Hop改进的定位算法，并借助OMNET++网络模拟器对两种算法进行性能测试，仿真结果表明改进的定位算法有明显的性能优势。

关键词：无线传感器网络；DV-Hop；洪泛法；能量消耗；OMNET++

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2015）22-0034-03

Abstract： In this study， a number of positioning technology in wireless sensor networks， based on the minimize flooding Law and the energy consumption and facilitate the deployment of the beacon nodes is proposed for a large central area of ??an improved localization algorithm based on DV-Hop， by OMNET + + network simulator two algorithms for performance testing， simulation results show improved positioning algorithm has a significant performance advantage.

Key words： wireless sensor networks； DV-Hop； the flooding method； energy consumption； OMNET ++

无线传感器网络的应用是当前最广泛的应用领域之一，例如环境监测和卫生保健系统[1]。而定位对于无线传感器网络应用是最大的难题[2]，例如追踪森林里动物、探测敌人和跟踪病人等，如没有找到发送数据信息的传感器位置，传送的数据信息就毫无作用。最初的方法是给传感器加装一个GPS接收器，然而这种方法不适合无线传感器网络，因为GPS接收器太昂贵，能量消耗太大，并且GPS接收器不能在稠密的植被和封闭的环境中工作。

辅助定位算法假设只有少部分传感器有确定位置通过手动配置或者使用GPS接收器，这些传感器叫做信标节点，可以用它们来估算其他传感器的位置。随着信标节点密度的增加，未知传感器的定位精确度也随之增加。研究表明除信标节点的密度外，恰当地部署信标节点也对定位精确度有影响[3]。

1 定位算法

无线传感器网络定位算法可以分为两类[4]：基于距离的算法Range-Based，如RSSI（Received Signal Strength Indicator）[5]、TOA（Time of Arrival）[6]、TDOA（Time Difference on Arrival）[7]、AOA（Angel of Arrival）[8]和距离无关的算法Range-Free，如DV-Hop（Distance Vector-Hop）算法[9]、凸规划算法[10]和MDS-MAP算法[11]等。前者需要测量相邻节点间的绝对距离或方位，并利用节点间的实际距离来计算未知节点的位置，并且对于传感器需要增加额外的硬件，这使得费用和能量消耗增加；后者无需测量节点间的绝对距离或方位，而是利用节点间的估计距离计算节点位置。

1.1 DV-Hop定位算法

DV-Hop算法的定位过程分为三个阶段[12]：

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

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

其中，（xi，yi）、（xj，yj）是信标节点i、j的坐标；hj是信标节点i与j（j≠i）之间的跳段数。然后，信标节点将计算的每跳平均距离用带有生存期字段的分组广播至网络中，未知节点仅记录接收到的第1个每跳平均距离，并转发给邻居节点。这个策（略确保了大多数节点从最近的信标节点接收到每跳平均距离值。未知节点接收到平均每跳距离后，乘以记录的跳数计算到每个信标节点的跳段距离。

1.2 DV-Hop定位算法的不足

（1）在大型的无线传感器网络中为了节约成本，使用有限处理和微控制的传感器。微控制和微处理不能运行计算复杂的算法，例如三边测量法中需要使用的非线性最小平方问题。因此在DV-Hop定位算法中估算传感器距离时把非线性最小平方问题线性化，再加上能量有限的传感器无法承受接收大量来自信标节点信息时的能量消耗。所有这些因素都阻碍了DV-Hop定位算法定位的精确度和改进。

（2）针对特定的环境例如在稠密的森林，对于这些环境很难在内部部署信标节点，最好的方法就是在这些环境的周界上部署信标节点。

1.3改进的DV-Hop定位算法

改进的DV-Hop定位算法的思想是针对中心区域部署信标节点，这些信标节点能够在监控下均匀部署在中心区域的周界上，最小化洪泛法传播，根据必要的有限信标节点精确定位从而减少能源消耗，三边测量法将用在基站，因为基站可以快速完成NLLS计算和充足的能量保留所有可能到信标节点的距离记录。例如要在茂密的森林里定位追踪某个动物比如熊猫，信标节点部署如图2所示。

改进的DV-Hop算法的定位过程如下：

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

（2）计算未知节点和信标节点的实际跳段距离。每个信标节点根据第（1）阶段中记录的其他信标节点的位置信息和相距跳数，利用式（1）估算平均每跳的实际距离。在这个阶段不同于DV-Hop定位算法，不再是信标节点根据式（1）估算平均每跳长度后开始第二次洪泛法传播给其他的传感器所估算的平均每跳长度，而是每个信标节点发送他们的估算平均每跳长度给基站，基站保留着一张每跳长度表，包括了每个信标节点的平均每跳长度。

（3）传感器报告监测数据信息给基站，在报告中传感器产生一个新包由两部分组成：报告信息和传感器的跳数表（到每个信标节点的跳数）。传感器先根据跳数表判断找到最近的信标节点，然后通过信标节点按编号位置以就近原则依次转播给基站。如图3所示。

（4）基站定位报告监测数据信息的传感器，用它保留的跳数长度表的记录和收到报告的跳数表的记录进行匹配，然后计算传感器到所有信标节点的距离，最后用三边测量法计算传感器的位置。

2 仿真实验及分析

借助OMNET++网络模拟器，对DV-Hop定位算法和改进的DV-Hop定位算法进行平均定位误差和平均能量消耗性能测试比较。在每个仿真实验中N个传感器随机部署在一个平面中心区域里，以圆形区域为例，M个信标节点均匀的放置在周界上，设定传感器无线通信半径为20 m，N为无线传感器网络面积除以π的平方根，M为N的0.1倍，分析不同参数对算法性能的影响，仿真次数为20次，用平均值来进行性能测试。

增大无线传感器网络面积，使无线传感器网络面积从0.1km2到20 km2逐渐增大，平均定位误差每2 km2增加，在图4中仿真实验结果表明增大无线传感器网络面积，对于平均定位误差增长率来说改进的DV-Hop定位算法比DV-Hop定位算法低。

增加传感器和信标节点的数量，设定无线传感器网络面积为600 km2，传感器的个数从600到2800增加，平均定位误差每200增加。在图5中仿真实验结果表明随着传感器个数的增加平均定位误差在DV-Hop定位算法中有明显的改变，而在改进的DV-Hop定位算法中没有明显的改变，这也说明改进的DV-Hop定位算法非常适合用在大型中心区域无线传感器网络中。在大型中心区域无线传感器网络中确保精确定位并且能够达到最小化无线传感器个数，这样可以减少部署开销。

增加无线传感器网络面积比较两种定位算法的能量消耗情况。在图6中仿真实验结果表明随着无线传感器网络面积的增加，能量消耗随之增加，但改进的DV-Hop定位算法能量消耗比DV-Hop定位算法低些，这又更进一步说明改进的DV-Hop定位算法能够适应大型中心区域无线传感器网络。

3 结论

对于改进的DV-Hop定位算法，目的在于最小化洪泛法，减少能量消耗，在确保必要定位精确度的情况下最小化信标节点的个数。改进的DV-Hop定位算法适合监测大型中心区域，因为信标节点可以部署在中心区域的周界上。通过仿真实验，增加无线传感器网络面积和传感器的数量，与DV-Hop定位算法进行比较，得到了更低的定位误差和能量消耗。

参考文献：

[1] 任丰原，黄海宁，林闯.无线传感器网络[J].软件学报，2003，l4（2）：1148-1157.

[2] 王福豹，史龙，任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报，2005，16（5）：857-868.

[3] 曹文明，王瑞.传感器网络覆盖定位模糊信息处理方法[M].北京：电子工业出版社，2013.

[4] 杨冕，秦前清.对传感器网络定位技术现状的研究[J].微机发展，2005，16（3）：26-28.

[5] Chen Xiaoyan，Pei Yanli.The Application of QGA in SensorOptimization Design[C]//Proc.of the 6th International Conferenceon Distributed Computing and Applications for Business，Engineering and Sciences.Wuhan，China：2012：14-17.

[6] Bachrach J，Taylor C，Girod L.Localization in Sensor Net-works[M].New York，USA：Wiley Press，2012：30-41.

[7] Girod L，Estrin D.Robust Rang Estimation Using Acoustic andMultimodal Sensing[C] //Proc. of IEEE/RSJ InternationalConference on Intelligent Robots and Systems.Maui，USA：IEEE Press，2011：1312-1320.

[8]Tang Zijian，Gannizzaro R C，Leus G，et al.Pilot-assisted Time-varying Channel Estimation for OFDM Systems[J].IEEE Trans.on Signal Processing，2012，55（5）：2226-2238.

[9] Niculescu D，Nath B.DV Based Positioning in Ad Hoc Net-works[J].Journal of Telecommunication Systems，2013，22（1/4）：267-280.

[10]Cerpa A，Estrin D.ASCENT：Adaptive Self-c0nfiguring SensorNetwork Topologies[C] //Proc.of the 1lth Joint Conference on IEEE Computer and Communications Societies，IEEE Press，2012：1655-1663.

[11]Shanc Y，Ruml W，Zhang Y，et al.Localization Form MereConnectivity[C] //Proc.of the 4th ACM Intemational Symposiumon Mobile Ad Hoc Networking，Computing.Annapolis，USA：ACM Press，2013：201-212.

[12] 林金朝，刘海波，李国军，等.无线传感器网络中DV-HOP节点定位改进算法研究[J].计算机应用研究，2011，26（4）：1272-1275.