基于模拟退火的加权DV-Hop的WSN定位算法

张治华，张玲华

(1.南京邮电大学 通信与信息工程学院，江苏 南京 210003；2.江苏省通信与网络技术工程研究中心，江苏 南京 210003)

0 引 言

无线传感器网络[1]是目前一个比较新兴的研究领域，研究其最基本的需求就是获取采集数据的节点位置信息。一般对于无准确位置信息的监测信息是没有任何利用价值的。在无线传感器网络中，需要获取无线传感网中传感器节点的位置信息，只有获取节点的具体位置，才能通过节点信息分析采取何种决策方式。所以说获取传感器节点的位置信息具有重要意义。综上所述，传感器网络节点定位技术是当今国内外研究的热点和重点[2]。

无线传感网络中的定位算法主要分为两种，一种是基于测距的定位算法(range-base),另一种是距离无关的(range-free)的定位算法[3]。前者主要是通过测量节点之间点到点的距离以及角度信息来计算节点位置，主要包括基于接受信号强度算法(RSSI)[4]、基于到达时间定位算法(TOA)[5]、基于到达时间差定位算法(TDOA)和基于到达角度算法(AOA)等[6]。这类算法虽然精度较高，但是对于硬件要求也高，而且受限于测距技术。后者是利用节点间的估计距离计算未知节点的位置，所以无需通过额外的硬件测量节点间的距离等信息。常用的与距离无关的定位技术有DV-Hop、质心算法[7]、Amorphous、APIT[8]等，这类算法成本和功耗都较低，应用也更加广泛。

DV-Hop算法[9]是目前无线传感网中应用最广泛的定位算法之一，针对原有算法的不足，提出了一种基于加权的平均每跳跳距的DV-Hop算法，通过未知节点对每个信标节点估计的平均每跳跳距进行归一化加权处理，对于距离未知节点较近的信标节点赋予大的权值。虽然改进后的加权DV-Hop定位算法相比传统定位算法的定位精度有所提高，但不是特别明显。为了进一步提高DV-Hop算法的定位精度，文中提出了模拟退火的加权DV-Hop算法。

1 经典DV-Hop算法描述

经典DV-Hop定位算法是基于距离矢量计算跳数的算法，具体步骤如下所述。

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

首先信标节点会向整个网络广播自身位置信息。信标节点的邻居节点会记录下广播的信息，其中包括跳数信息，初始化为0。邻节点会筛选同一信标节点的最小跳数信息并记录，然后将其加1传播到网络中。保证网络中所有节点记录下到信标节点的最小跳数。

1.2 计算未知节点与每个信标节点的估计距离

经过上一步节点信息的路由洪泛，由式1计算平均每跳距离。

(1)

其中，(xi,yi),(xj,yj)为信标节点i,j的坐标；hi为信标节点i与j之间的跳数：HopSize为平均跳距。

1.3 计算未知节点的自身位置

通过式2计算未知节点u到信标节点的估计距离du,i：

du,i=HopSize·hu,i

(2)

其中，hu,i为最小跳数。

当未知节点得到3个或者更多节点之间的距离后，再通过三边测量法[9]或者极大似然法等数学方法计算未知节点的坐标。

1.4 算法的误差分析

在DV-Hop定位算法中，用未知节点到信标节点的最小跳数乘以平均跳距来计算未知节点到信标节点的距离。

如图1所示，设A1、A2和A3为信标节点，U1、U2、U3、U4、U5和U为未知节点。其中A1到A2的实际距离为40 m，A2到A3的距离为25 m，U到A1、A2、A3的实际距离分别为50 m、20 m、50 m。针对未知节点U，信标节点A2与U的最小跳数为2，属于局部最小跳数，因此U从A2获取平均跳距。根据式1可得：Hopsize=(40+25)/(2+4)=10.8,那么U到A1、A2和A3的估计距离分别是10.8×3=32.4、10.8×2=21.6、10.8×3=32.4。由此可以看出，用A2估算平均跳距求U到其他信标节点估计距离的误差非常大，导致最终未知节点定位的误差也很大。

图1 误差分析

2 WDV-Hop算法

由上文误差分析可知，由于A2和A3实际距离很近，只是略大于通信半径，然而A2和A3跳距不止两跳而是达到四跳，导致用A2估计平均跳距产生的误差很大。针对误差分析可以引入加权系数[10]。在该算法中，用Wi表示不同信标节点加权系数，通过式3确定：

(3)

其中，ni表示未知节点到信标节点i的跳数。然后根据式4计算未知节点的加权平均跳距[11]：

(4)

将加权平均跳距代入式2，求出未知节点到信标节点的估计距离，最后通过三边测量法或者极大似然估计法求出未知节点的坐标。

WDV-Hop算法主要是对传统DV-Hop算法的第二步进行改进，通过修正平均每跳跳距来提高定位精度，对第三步计算未知节点位置并未涉及。虽然对平均每跳跳距进行加权修正，但是平均每跳跳距误差还是依然存在。由于最小二乘法对测距敏感，WDV-Hop算法的平均每跳跳距误差对节点的定位精度产生较大的影响。

3 模拟退火加权DV-Hop算法

在传统的DV-Hop和加权DV-Hop算法中，通常采用最小二乘法对未知节点的坐标进行估计，但基于最小二乘法对测距误差比较敏感，导致由于测距误差偏大而使得定位过程中的定位准确度降低。故应用模拟退火算法加强局部搜索最优解，提高定位算法精度。

模拟退火算法[12-14](simulated annealing，SA)是目前应用比较广泛，基于蒙特卡洛迭代的随机寻优方法。

模拟退火加权DV-Hop算法的核心思想如下：

(1)通过加权DV-Hop算法由式4求出HopSizeavg，然后将其带入式2求出未知节点U到信标节点的距离。

(2)选取合适的目标函数。该定位算法中建立合适的目标函数是非常关键的。

图2 节点定位示意图

如图2所示，设A1，A2，…，An为信标节点，节点坐标分别为(x1,y1),(x2,y2),…,(xn,yn)。U为未知节点，坐标为(x,y)，未知节点到信标节点的估计距离分别是d1,d2,…,dn。根据两点间的距离公式可得：

(5)

令：

(6)

则目标函数为：

(7)

(4)设置初试温度T0。

(5)设置循环计算器的初始值K=0。

(6)通过对当前解的最优点做一个随机变动来产生一个新的最优点，计算其目标函数S2。然后令目标函数的增量Δ=S2-S1。

(7)根据Metropolis准则：

(8)

如果Δ<0，则接受新产生的解作为当前的最优解；如果Δ≥0，以概率e-Δ/T接受新产生的解作为当前的最优解。

(8)如果k小于终止迭代步数，k=k+1，然后转向步骤6，否则转向步骤9。

(9)如果温度T未到达冷却状态，令T=T×α，α为降温系数，取值范围为0到1，并转向步骤5；如果温度达到冷却状态，输出当前的解即为最优解，结束算法。

4 仿真与分析

为评价提出的模拟退火加权DV-Hop算法性能，基于Matlab仿真平台对其进行仿真。实验设置如下：100个节点随机散布在100 m×100 m区域内，为使在不同条件下的分析直观化，将平均定位误差定义为[15]：

(9)

4.1 基于信标节点个数的分析

图3为信标节点个数与算法定位误差[16]的关系图，其中dv为传统的DV-Hop算法，wdv为加权DV-Hop算法，wdvth为模拟退火加权DV-Hop算法。由图可知，固定其他条件，当增加网络中信标节点的数量，三种算法的定位误差都呈现逐渐下降的趋势。主要因为当信标节点的数目增加，用于节点定位的信息也增加，平均误差也随之减小。在相同条件下，模拟退火加权DV-Hop算法的平均误差下降趋势比其他两

图3 信标节点个数-平均定位误差

种算法要明显很多。所以在低密度信标节点网络中，文中提出的算法优于传统DV-Hop和加权DV-Hop。

4.2 通信半径对平均定位误差的影响

图4为通信半径与平均定位误差的关系图，固定信标节点的个数为10，其他条件不变。通过改变节点的通信半径R来比较算法的性能。当R增大时，三种算法的平均定位误差都会减小。这主要是因为增加通信半径使得网络的连通度[17]提高。连通度表明在一个网络中，能够与一个节点直接进行通信的节点的平均个数。由图可知，在相同条件下，文中改进的算法相比其他两种算法下降趋势更加明显。在图4中，在横轴上随机取一点，即传输半径不变，wdvth算法的定位误差在三种算法中最小，所以该算法能够有效地节约节点的能量消耗。

图4 通信半径-平均定位误差

4.3 基于总节点数量的分析

图5是通过改变节点的总数来考察对算法对平均定位误差的影响。在仿真过程中，信标节点、通信半径等条件固定不变，将节点的总数从100开始逐渐增加。由图可知，节点总数的变化对算法的平均定位误差也是有影响的，三种算法的节点平均定位误差会随着节点总数的增加而下降。增加节点总数，同时不改变整个网络的区域大小，相当于提高了网络中的节点密度，使得网络的连通度得到提升。虽然三种算法的平均定位误差都下降，但是相比其他两种算法模拟退火加权DV-Hop算法的定位精度明显高于其他两种算法。

图5 总节点个数-平均定位误差

5 结束语

文中首先对传统定位算法的平均跳距进行了加权修正，更加准确地对平均每跳进行估计，减少误差对后续节点定位的影响。然后针对最大似然估计定位抗干扰性较弱，引入模拟退火算法对未知节点的坐标进行最优搜索。该算法在提高定位精度上具有明显的优势，能够有效降低由测距误差造成的对定位精度的影响。在信标节点密度较低时，该算法也能有较高的定位精度，同时能够有效地利用网络中的通信量，减少节点的能量消耗，具有较高的实用价值。

参考文献：

[1] YICK J,MUKHERJEE B,GHOSAL D.Wireless sensor network survey[J].Computer Networks,2008,52(12):2292-2330.

[2] MAO Guoqiang,FIDAN B,ANDERSON B D O.Wireless sensor network localization techniques[J].Computer Networks,2007,51(10):2529-2553.

[3] HE Tian,HUANG Chengdu,BLUM B M,et al.Range-free localization schemes for large scale sensor networks[C]//Proceedings of the 9th annual international conference on mobile computing and networking.San Diego:ACM,2003:81-95.

[4] 李再煜.RSSI定位原理的研究与实现[J].无线电工程,2013,43(7):8-10.

[5] 姜志鹏,陈正宇,刘 影,等.TOA定位算法非线性优化问题研究[J].传感技术学报,2015,28(11):1716-1719.

[6] 邹艳玲,程爱华.超宽带室内环境下的TDOA/AOA定位系统[J].微计算机信息,2008,24(33):164-166.

[7] ZHANG Bingjiao,JI Minning,SHAN Lianhai.A weighted centroid localization algorithm based on DV-Hop for wireless sensor network[C]//2012 8th international conference on wireless communications,networking and mobile computing.Shanghai,China:IEEE,2012:1-5.

[8] 熊志广,石为人,许 磊,等.基于加权处理的三边测量定位算法[J].计算机工程与应用,2010,46(22):99-102.

[9] NICULESCU D,NATH B.DV based positioning in Ad Hoc networks[J].Telecommunication Systems,2003,22(1-4):267-280．

[10] 周杭霞,崔 晨,叶佳骏.一种基于加权处理和误差修的DV-Hop定位算法研究[J].传感技术学报,2014,27(12):1699-1703.

[11] 李 琳,赵 可,林志贵,等.基于加权的三维DV-Hop定位算法[J].控制工程,2015,22(4):761-764.

[12] 李玉增,张雪凡,施惠昌,等.模拟退火算法在无线传感器网络定位中的应用[J].通信技术,2009,42(1):211-213.

[13] 傅文渊,凌朝东.布朗运动模拟退火算法[J].计算机学报,2014,37(6):1301-1308.

[14] 蒋惠波,刘 彬,袁卫华.基于Metropolis准则的自适应随机搜索算法研究[J].中国西部科技,2015,14(3):17-19.

[15] 张新荣,熊伟丽,徐保国.采用RSSI模型的无线传感器网络协作定位算法[J]. 电子测量与仪器学报,2016,30(7):1008-1015.

[16] WANG Yun,WANG Xiaodong,WANG Demin,et al.Range-free localization using expected hop progress in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2009,20(10):1540-1552.

[17] 孙小军,刘三阳,王志强.求解网络连通度问题的新算法[J].计算机工程与应用,2009,45(34):82-84.