基于DV-hop定位的误差加权改进算法

(太原理工大学信息工程学院,山西 太原 030024)

0 引言

无线传感器网络(wireless sensor network，WSN)是部署大量低廉的智能传感器节点，并以自组织、多跳方式构成的无线网络系统。在传感器监测区域内,传感器将采集的数据进行传输和处理，实现对该目标区域的监测。无线传感器网络(WSN)具有无线自组织、高容错性、动态性强的特点，被广泛应用于军事、环境监测、农业生产、医疗卫生等领域[1-2]。节点定位是网络重构、检测和定位必不可少的研究基础。

按照是否要测量传感器节点之间的距离，现有的传感器定位算法可分为基于测距算法(range-based)和距离无关定位算法(range-free)两类[3]。距离相关的定位是指网络锚节点具有测量自身到邻居节点的距离、信号的角度和强度的能力，然后通过三边测量法、极大似然估计法等算法得出未知节点的坐标。传感器距离定位包括到达时间法(time of arrival, TOA)、到达角度法(angle-of-arrival,AOA)、到达时间差法(time difference of arrival,TDOA)和接收信号强度指示法(received signal strength indication,RSSI)等方法。这些方法定位精度较高，但对硬件的要求高。距离无关的定位是通过节点间相互网络连通度和通信半径等，利用三边测量法、极大似然估计法等算法得出未知节点的坐标。定位方法包括质心算法、APIT算法、DV-hop算法[4]等。距离无关定位算法不需要测量距离或角度的硬件，能耗较低，应用前景广泛。

1 DV-hop算法

1.1 DV-hop算法流程

DV-hop算法是由Niculescu等学者提出的免于测距的算法，它的算法定位过程分为以下3个阶段。

① 计算未知节点与每个锚节点的最小跳数

锚节点通过向传感器网络的邻居节点发送自身的信息分组，每个节点维护1个数据表{i,(xi,yi),hi}。其中，(xi,yi)为结点i的二维坐标，hi为起始节点到节点i的跳数，初始化时设置为0。邻居节点收到锚节点i的数据包后，将跳数hi加1，然后向邻居节点广播该数据包。接收节点保存每个锚节点的最小跳数，对于同一锚节点的较大的跳数则释放。

② 校正值的计算和广播

锚节点i记录的信息包括其他锚节点j的坐标信息和跳数信息。所有锚节点的平均每跳距离Ci的计算式为：

(1)

式中：(xi,yi)、(xj,yj)分别为锚节点i和锚节点j的二维坐标；hij为两锚节点之间的跳数距离。

将锚节点的平均每跳距离广播至传感器网络中，未知节点仅接收第一个锚节点的每跳距离，并将其作为自身传播的每跳距离，则可得出节点k与锚节点i的距离为Cik=Cihik。

③ 未知节点位置的计算

假设未知节点的二维坐标为(x,y)，锚节点i的坐标为(xi,yi)，而未知节点与网络锚节点i的估算距离为di,则可得出以下公式：

(2)

设:

(3)

(4)

(5)

由最小二乘法,可得p=(ATA)-1ATB。

DV-hop算法在实际应用中存在以下不足。

① 算法中的每个节点要接收和转发所有锚节点的数据包结构，这些节点处于活动状态，需要较长时间等待数据包，网络中的通信开销和能量消耗随之增加。

② 锚节点所占的比例不同，平均跳段距离也就不同。比例越高，平均跳段距离就越精确。当比例增加到一定程度时，距离保持稳定，但费用随之增加。

根据试验发现，未知节点与锚节点的估算距离影响了节点的定位精度。当未知节点与锚节点间距为一跳段时，测得的距离约为准确距离的1.2倍。随着节点之间间距的增大，估算误差也随之增加。因此，使用全部锚节点反而降低了节点的定位精度。

1.2 粒子群算法在DV-hop中的应用

粒子群算法是对DV-hop算法中三边测量法或最大似然估计法的未知节点坐标的误差进行修正和优化，是非线性方程求解的有效解决方案。每个可行解相当于粒子群中的一个粒子，粒子通过个体最优解P和全局最优解G，利用式(6)更新下一个节点的个体最优解的位置和速度信息数据；然后在这个空间中改变位置和速度，向最优解靠拢。

(6)

式中：i为第i个粒子；t为粒子群的迭代次数；c1、c2为学习因子，以平衡局部搜索和全局搜索能力；xi为粒子i的位置信息。

粒子群初始化时要设置粒子位置信息的上下限xmax和xmin、粒子速度信息的上下限vmax和vmin、最大迭代次数[5-7]。

1.3 典型DV-hop改进算法

2 改进的DV-hop算法

本文对传统的DV-hop算法进行了适当的改进。改进算法主要体现在以下3个方面：第一阶段采用限定数据包的广播范围；第二阶段采用了基于误差修正加权和跳距估计算法；第三阶段采用了基于粒子群的定位算法。粒子群算法通过不断舍弃最远节点而降低算法的复杂度。

DV-hop算法属于无需测距的定位算法，硬件要求简单，但网络中锚节点与未知节点的排列方式并非成直线排列，所以节点之间跳数越多，估算平均每跳距离的误差越大。改进的算法采用在锚节点向网络中广播的数据包结构中增加一个生存周期数据data，所以改进算法中的锚节点数据包中包括4个字段，分别为锚节点的标志i、锚节点的二维位置坐标(xi,yi)、跳数hi和data数据段。data数据表示锚节点能够传输的最大传播跳数，用于限定锚节点数据包传输的最大范围。定位算法根据锚节点在无线传感器网络中的比例和网络的规模来设置不同的data值。

若网络中总的锚节点数有M个，则锚节点i的平均每跳距离误差值εi为：

(7)

某一锚节点i的距离误差值越小，越能准确地估计出锚节点i的平均每跳距离。因此，误差值越小，权值应该越大。

假设网络中未知节点收到n个锚节点的数据报信息，锚节点i的平均每跳距离对应的加权值为：

(8)

图1 改进的粒子群优化算法流程图

3 算法仿真及试验分析

为了验证本文所提改进算法在应用中的有效性和可行性，采用Matlab对本文提出的算法和DV-hop算法进行仿真和分析。试验中将仿真节点随机分布在二维平面上，在区域100 m×100 m 的范围内随机布置100个节点，仿真次数为200次。改进算法中的生存周期Hmax设置为6，学习因子c1=c2=2，粒子群的最大迭代次数为20。

平均定位误差定义为：

(9)

归一化的节点定位误差定义为：

(10)

式中：xi,yi为节点i的估算距离；x,y为节点i的实际距离；R为节点通信半径；m为网络中的节点数，锚节点的个数按5、10、15、20、25、30、35、40依次增加。

3.1 锚节点对定位误差的影响

仿真通过设置网络中不同的锚节点数量，采用平均定位误差对DV-hop算法和本文的算法进行比较。本文取网络节点的数量为100，网络节点通信半径为20 m。在无线传感器网络中，锚节点的数量对节点的定位精度有一定的影响。当节点间通信半径R=20 m时，不同的锚节点数量对DV-hop算法和本文算法的定位精度的比较如图2所示。从图2可以看出，随着锚节点数的增加，两种算法中节点能够获取的信息越多，节点获得的定位距离信息越精确，定位精度呈现上升的趋势。

图2 平均定位误差曲线

当锚节点数增加到20时，本文提出的定位误差有了明显的改善；当锚节点数增加到30时，本文提出的算法相比于DV-hop算法,定位精度达到了3.4。从总体上来看，本文提出的算法比传统的定位算法在定位精度上有了明显的改善。

3.2 不同通信半径对本文算法的影响

当锚节点按比例增加时，在节点间通信半径为15 m、20 m、25 m、30 m这4种不同情况下，本文提出的改进算法的归一化定位误差的比较情况如图3所示。从图3可以看出，在4种不同通信半径下，网络的定位精度都随着网络中锚节点数的增加而更加精确。当锚节点达到一定比例时，定位精度趋于平稳。

图3 归一化平均定位误差曲线

4 结束语

本文分析了DV-hop算法[10-14]的3个阶段，阐述了两种典型的改进算法，提出了基于DV-hop定位的误差加权改进算法。

通过设定最大传输距离，减小了节点之间的传播跳数，提高了未知节点的定位精度，降低了网络的能耗开销。同时对接收到的k个锚节点的平均每跳距离误差加权和处理，使未知节点算出的平均每跳距离相比DV-hop更为准确，改善了无线传感器网络中的定位精度。改进的粒子群算法通过适应度函数减小了迭代的粒子数，缩短了不必要的迭代过程，从而有效改善了定位精度，减少了无线传感器网络定位的计算复杂度和计算时间，降低了定位误差。仿真试验验证了本文提出的DV-hop定位改进算法的可行性。

[1] He T,Huang C D,Blum B M,et al.Range-free localization schemes in large scale sensor networks[C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Networking.New York:ACM Press,2003:70-95.

[2] Cenedese A,Ortolan G,Bertinato M.Low-density wireless sensor networks for localization and tracking in critical environments[J].IEEE Transactions on Vehicular Technology,2010,59(6):2951-2962.

[3] 于弘毅，李鸥，张效义.无线传感器网络理论、技术与实现[M].北京：国防工业出版社,2008:143.

[4] Liu W Y,Wang E S,Chen Z J,et al.An improved DV-Hop localization algorithm based on selection of beacon nodes[J].Journal of Convergence Information Technology,2010,5(9):157-164.

[5] Kulkarni R V,Venayagamoorthy G k.Particle swarm optimization in wireless sensor networks:a brief survey[J].IEEE Transaction on Systems Man and Cybernetics,2011,41(2):262-267.

[6] Low K S,Nguyen H A,Guo H.A particle swarm optimization approach for the localization of a wireless sensor networks[C]//Proceedings of IEEE International Symposium on Industrial Electronic,2008:1820-1825.

[7] 黄艳，臧传治，于海斌.基于改进粒子群优化的无线传感器网络定位算法[J].控制与决策，2012,27(1)：156-160.

[8] 朱红松，孙利民.无线传感器网络技术发展现状[J].中兴通讯技术，2009,15(8):35-38.

[9] 肖美华，周之平.无线传感器节点加权平均跳距定位算法[J].计算机工程与设计，2010,31(1)：78-81.

[10]刘凯，余君君，谭力雄.跳数加权DV-Hop定位算法[J].传感技术学报，2012,25(11):1539-1542.

[11]赵林铠,洪志全.基于无线传感器网络的DV-Hop定位算法的改进[J].计算机应用，2011,31(5):1189-1192.

[12]张爱平,赖欣.在JSP中调用JavaBean实现Web数据库访问[J].计算机时代,2007(1):15-18.

[13]仲伟和.基于JSP网页自动生成工具的设计与实现[J].科技信息,2007(15):21-23.

[14]Lin C R, Gerla M.Adaptive clustering for mobile wireless networks[J].IEEE Journal on Selected Areas Communications, 1997,15 (7) :1265-1275.