乔 欣，史良马，杨汉生，丁恩杰，王正创

(1.巢湖学院 机械与电子工程学院，安徽 巢湖 238000；2.中国矿业大学 物联网(感知矿山)研究中心，江苏 徐州 221008)

基于跳距修正L-M优化的WSN定位算法

乔 欣1，史良马1，杨汉生1，丁恩杰2，王正创1

(1.巢湖学院 机械与电子工程学院，安徽 巢湖 238000；2.中国矿业大学 物联网(感知矿山)研究中心，江苏 徐州 221008)

针对DV-Hop定位算法在节点随机分布的网络拓扑环境下存在误差较大的问题，文中通过分析平均跳距估计、未知节点坐标估计区域求解对定位精度的影响，提出了一种基于跳距修正L-M优化的WSN定位算法CLDV-Hop(Correct L-M DV-Hop)；仿真结果表明，在不增加额外开销且仿真环境相同的条件下，CLDV-Hop算法比现有改进的算法具有更高的定位精度，与DV-Hop算法相比精度提高了约33%～41%。

WSN；跳距修正；L-M优化

0 引言

无线传感器网络(wireless sensor network，WSN)是由布撒在区域内能够感知、处理、传输环境信息的大量传感器节点组成，通常被用于环境监测、医疗服务、军事侦查、工业诊断、智能空间等领域[1]。不管是何领域，缺少目标或传感器节点位置信息的研究都是无意义的。因此，节点定位技术成为WSN中的重要研究课题。

目前，较为成熟的GPS定位系统可以实现WSN的节点定位，但考虑到价格、体积、能耗及环境等因素，故不可能大规模地布置[2]。许多研究者针对无需GPS模块提出了各种定位算法，根据定位机制可划分为基于测距的定位算法(Range-Based)和与距离无关的定位算法(Range-Free)[3]。前者需要测量相邻节点间的绝对距离或者角度信息，常用的测距技术有RSSI、TOA、TDOA、AOA。后者仅根据网络的连通性等信息即可实现定位[4]。如质心算法、凸规划算法、APIT算法及DV-Hop算法等[5]。Range-Based对硬件要求较高，并且需要多次测量来获得合理的定位精度，所以计算量和通信开销很大。Range-Free定位机制凭借其在成本、功耗、复杂度等方面的优势，被广泛应用在大WSN。

DV-Hop是一种典型的无需测距定位算法，实现简单、定位精度较高[5]。但是，在节点随机分布的WSN中，该算法的定位精度仍然不足[6]，故针对该算法精度、稳定性、效率等存在的问题，很多学者提出了相应的改进方案。文献[7]提出利用三角不等式对未知节点到多跳锚节点的距离进行约束，同时采用加权双曲线进行定位；文献[8]提出用全新的方法计算锚节点到未知节点的距离、利用加权最小二乘法进行定位计算。本文提出了CLDV-Hop算法，并且与文献[7]、文献[8]中所述算法进行仿真分析，结果表明，在节点随机分布的网络拓扑结构中，CLDV-Hop算法具有更高的定位精度与稳定性。

1 算法描述与误差分析

1.1 DV-Hop算法

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

Step1 锚节点广播自身信息并计算平均跳距[9]。锚节点将自身信息以数据包的格式广播至网络的所有节点。由图1网络结构拓扑可知，锚节点i,j之间的跳数为hij=3，未知节点p与锚节点i的跳数为hip=3。

已知锚节点的坐标(x,y)与锚节点间的跳数h，那么可以根据公式(1)计算出每个锚节点的平均跳距HS。

(1)

Step3 定位阶段。如果网络中未知节点能够收到三个或者三个以上锚节点的信息，则可以执行三边定位法或最大似然估计法求解未知节点的坐标。

假设待求未知节点p坐标为(x,y)，第i个锚节点的坐标记为(xi,yi)，节点p到锚节点i的距离记为di。若WSN中有m个锚节点能够与未知节点p通信，则未知节点p的坐标可以根据式(2)方程组估计得出。

(2)

上述方程组可以转化为AX=b的形式。

方程AX=b利用最小二乘法解未知节点的估计坐标为：

X=(ATA)-1ATb

(3)

图1 网络拓扑结构

2 CLDV-Hop算法

本节中，在不增加网络通信量、硬件开销，不改变DV-Hop算法过程的条件下，本文对平均跳距和定位估计两个方面进行了改进。

2.1 平均跳距修正

DV-Hop算法中获得较为合理的平均跳距是保证定位精度的关键，本节，从两个方面对平均跳距进行修正，具体步骤如下：

1)节点在定位过程中，网络节点随机分布，当通信半径r一定时，在节点分布的局部区域可能会形成“空洞”，使得距离一定的锚节点之间的跳数值可能变大，这就导致求解平均跳距误差变大[10]。本文首先设定锚节点的跳数阈值δ，当hij>δ时，令hij=0，dij=0。

2)在估计未知节点的坐标时，未知节点将最先接收到锚节点平均跳距的信息作为其平均跳距。就整个节点非均匀分布的网络而言，不足以表示整个网络的平均跳距，可能会引起局部的定位精度偏差很大，使得整个网络的定位精度不稳定。因此，综合考虑多个锚节点的平均跳距，能够提高整个网络的定位精度。

假设有m个锚节点，结合公式(1)，锚节点j平均跳距的修正因子ϖj可表示为：

(4)

2.2 基于L-M法优化的定位估计

在DV-Hop算法中，如果能够确定3个或者3个以上锚节点到未知节点的距离，则可以通过三边或者多边定位法对未知节点的坐标进行估计[11]。事实上，尽管通过平均跳距的修正，未知节点到锚节点的跳段距离的估计也总是存在误差，因为多边定位法对测距误差敏感，当测距误差较大时，通过多边定位法计算出的估计坐标与真实坐标之间存在更大的偏差，另外，在仿真过程中发现，当ATA为病态矩阵时，通过多边定位法所估计出的未知节点坐标不仅误差很大，而且定位精度的稳定性较差，有时甚至得出错误的结果[9]。

本文采用多边定位法和L-M算法相结合的算法求解未知节点的估计坐标，即首先通过多边定位法获得未知节点的估计坐标，然后把估计值作为L-M算法的初值，进一步对未知节点坐标迭代求精。图2画出了锚节点为10时，其中一个未知节点的估计区域。

图2 未知节点估计区域

从式(2)中可以看出，该方程组为超定方程组。因此，将式(2)转换成：

(5)

式中，X为未知节点坐标(x,y)，r(X)为残差函数。

由此可将求解未知节点的估计坐标转化为求式(5)的无约束极小平方和问题，即minF(X)。L-M法在处理非线性最小二乘优化问题上具有明显的优势，本文中选用L-M法进行优化。

L-M算法的迭代公式可以表示为：

(6)

其中：X(0)为通过式(4)求得未知节点的最小二乘解求的坐标初值(x,y)，k为迭代变量，μ为阻尼参数，μ>0。r(X(k))为：

r(X(k))=(r1(X(k)),(r2(X(k)),…,(rm(X(k)))

J(X(k))为残差函数r(X)在X(k)处一阶导数组成的雅克比矩阵：

(7)

2.3CLDV-Hop定位算法的过程

CLDV-Hop算法步骤如下：

Step1:网络初始化。同时给出文中仿真相关变量，如下表所示。

表1 仿真变量及参数设置

Step2:锚节点通过洪泛广播的方式发送信息，包括自身ID、坐标、跳数。

Step3:最短路径算法计算节点间跳数、根据式(1)计算每个锚节点的平均跳距Dhop(AnchorAmount,1)并广播至网络、未知节点从最近的3个锚节点获得加权平均跳距UNWDhop(UNAmount,1)，通过跳数与平均跳距的乘积估算出未知节点到锚节点的距离DAll(AnchorAmount,UNAmount)。

Step6:通过平均定位误差、归一化平均定位误差、均方根误差对CLDV-Hop算法进行评价。

3 仿真与实验

为了验证改进后算法的性能，本文利用MATLAB 2010b平台对文中提出的CLDV-Hop定位算法进行仿真分析，并同有关方法进行了比较。仿真环境区域大小为100 m×100 m，并在该区域内随机放置100个节点，图3为网络节点随机分布图。其他仿真参数参考表1。

图3 网络节点随机分布图

图4仿真了锚节点数20、通信半径30时， DV-Hop和CLDV-Hop对未知节点定位的偏差。从图中可以看出，改进后算法的定位精度明显比DV-Hop算法精度高的多。

图4 未知节点定位偏差图

图5、6中分别对比了文献[7]通过加权双曲线定位算法(记为WDV-Hop)、文献[8]采用新的方式计算未知节点与锚节点距离的算法(记为NDV-Hop)及传统DV-Hop算法，仿真了几种算法归一化平均定位误差与网络节点总数的关系。图5中设置通信半径为20，锚节点为15个，从图中可以看出，随着网络节点总数的增加，文中提出的CLDV-Hop算法归一化平均定位误差更低。图6中设置通信半径为30，锚节点数为15个，从图中可以看出，节点总数为150个时，DV-Hop算法归一化误差为0.321 4，NDV-Hop算法约为0.240 8，WDV-Hop算法约为0.231 7，而文中提出的CLDV-Hop算法仅为0.198 7。从图5、6对比可以看出，通信半径取值不同对定位精度影响较大，每个无线传感网络中都存在一个最优通信半径的问题，实际应用中要多次测试选择最优的通信半径。

图5 通信半径为20时，网络节点总数对定位误差的影响

图6 通信半径为30时，网络节点总数对定位误差的影响

4 结论

本文提出了一种基于跳距修正L-M优化的WSN定位算法，能够应用在节点随机分布的大型无线传感器网络定位监测，如地质灾害监测、水质污染监测、森林火灾监测等。文中通过对平均跳距、定位计算两个方面分别进行改正，通过仿真

实验可以得出本文算法定位精度更高，是一种简单高效的WSN非测距定位算法。

[1]贾 琦，周新志.基于无线传感器网络DV-HOP定位算法的改进和研究[J].计算机测量与控制,2013,21(11)：3043-3046.

[2] Capkun S, Hamdi M, Hubaux J P. GPS-free positioning in mobile Ad-Hoc networks[A]. Proc. Hawaii Int. Conf. on System Sciences[C]. Maui, HW, USA, 2001：3481-3490.

[3] 石为人,贾传江,梁焕焕.一种改进的无线传感器网络DV-Hop定位算法[J].传感技术学报,2011,24(1):83-87.

[4] Girod L, Bychkovskiy V, Elson J. Locating tiny sensors in time and space: A case study[A]. Proceedings of the 2002 IEEE International Conference on Computer Design[C]. Freiburg (Germany) , 2002: 214-219.

[5] Niculescu D,Nath B. DV Based Positioning in Ad Hoc Networks[J].Journal of Telecommunication Systems, 2003, 22(1-4):267-280.

[6] He T, Huang C D, Blum B M, et al. Range-Free Localization Schemes for Large Scale Sensor Networks[A]. Proceedings of the Ninth Annual International Conference on Mobile Computing and Networking[C]. San Diego, United states，2003:81-95.

[7] 周 玲,康志伟,何怡刚.基于三角不等式的加权双曲线定位DV-HOP算法[J].电子测量与仪器学报,2013,27(5)：389-395.

[8] 朱 敏，刘昊霖，张志宏,等.一种基于DV-HOP改进的无线传感器网络定位算法[J].四川大学学报(工程科学版)，2012，44(1)：93-98.

[9] 乔 欣，常 飞，丁恩杰,等.基于跳距修正的WSN拟牛顿迭代定位算法[J].传感技术学报，2014,27(6)：797-801.

[10]Ding E J, Qiao X, Chang F. Iterative algorithm for Quasi-Newton in WSN based on modifying average hopping distances[J]. WIT Transactions on Engineering Sciences, 2014(87):589-596.

[11] Ding E J, Qiao X, Chang F. Improved weighted Centroid localization algorithm based on RSSI differential correction[J]. International Journal on Smart Sensing and Intelligent Systems, 2014,7(3):1156-1173.

Iterative Algorithm for L-M in WSN Based on Modifying Average Hopping Distances

Qiao Xin1, Shi Liangma1, Yang Hansheng1, Ding Enjie2，Wang Zhengchuang1

(1.School of Mechanical and Electrical Engineering, Chaohu University, Chaohu 238000, China；2.CUMT-IoT Perception Mine Research Center，Xuzhou 221008，China)

Aiming at the existing large errors of the DV—Hop localization algorithm in network topology nodes distributed randomly, the passage try to solve the position accuracy by analyzing the estimate of the average hop and the unknown node coordinates region, proposed a CLDV-Hop algorithm in WSN based on modifying average hopping distances. The simulation results show that, without increasing the overhead and the same conditions as the simulation environment, CLDV-Hop algorithm has higher positioning accuracy than existing improved algorithms, and compared with DV-Hop algorithm accuracy is improved by about 33%～41%.

WSN; average hop distance correction; L-M optimization

2016-07-15；

2016-09-22。

安徽省高校省级科学研究重点项目(KJ2012A203);巢湖学院校级项目(XLY-201603)。

乔 欣(1988-)，女，安徽宿州人，硕士，助教，主要从事无线传感器网络定位技术，ZigBee技术等方向的研究。

1671-4598(2017)02-0116-04

10.16526/j.cnki.11-4762/tp.2017.02.032

TP393

A