张水锋1， 程 庆 2 ，陈帅1 1.淮南师范学院电子工程学院 2.淮南师范学院计算机学院

非测距无线传感器网络定位算法研究

张水锋1， 程 庆 2 ，陈帅1 1.淮南师范学院电子工程学院 2.淮南师范学院计算机学院

本文介绍了无线传感器网络定位的原理及分类，阐述了非测距WSN算法中的质心算法的原理、DV-HOP算法的原理、APIT算法原理以及Amorphous 算法原理。同时对质心算法和DV-HOP算法进行了matlab仿真，并分析了非测距算法定位的误差。

无线传感器网络定位 非测距 质心算法 DV-HOP算法

由分布在监测区域里的无线传感器节点构成无线传感器网络(Wireless Sensor Network, WSN)。它是目前科技的前沿研究领域，具有高度集成和高度交叉的特点，主要应用于军事领域、农业生产、生态监测与灾害预警、基础设施状态监测、工业领域、智能交通、医疗系统以及信息家电设备等领域。

1 无线传感器网络定位原理及分类

无线传感器网络的一个基本功能是节点的定位，它对于无线传感器网络的定位起着至关重要的主要。无线传感器网络定位根据是否需要测量距离，可以分为测距定位算法和非测距定位算法。测距定位算法是要测量节点间的距离或者角度信息，然后使用三边测量、三角测量或者最大似然估计定位算法实现节点间定位。而非测距定位算法，不需要测量节点间的距离，通过一些其他信息实现定位。测距定位算法主要包括RSSI、TOA、TDOA和AOAO等算法，非测距定位算法主要包括质心算法、DV-HOP算法、Amorphous 算法和 APIT 算法等。

2 非测距WSN定位算法原理

非测距的定位算法由于对硬件的要求比较低，得到了广泛的使用。非测距的算法主要有四种，算法原理如下。

质心算法是利用节点之间的简单几何关系估算未知节点的坐标位置。DV-Hop(Distance Vector-Hop)定位算法的执行过程为：信标节点向邻居节点广播一个信息，该信息包含信标节点的节点编号、坐标和跳数计数数据，跳数的初始值设为 0，节点会根据收到的数据报更新计数表，保证每次计算到每个信标节点的最小跳数。当它收到来自同一个节点的信息时，比较其中的跳数计数，当大于对应的最小计数时，简单的丢弃该信息。否则，更新相应的最小跳数，并把信息的跳数计数加一，然后以广播的形式转发到整个网络，供其他节点参考修改。APIT 算法的基本思想是：遍历未知节点的所有邻居信标节点，每次都拿出三个节点组成一个三角形，判断未知节点是否处于该三角形区域内，确定完所有的三角形区域后会形成一个交集区域，未知节点的坐标即为该交集区域的质心。Amorphous的无线传感器网络定位算法，在算法初始阶段，信标节点发送位置信息并在全网内传播，未知节点以自己的通信半径乘以最小跳数计算到信标节点的距离，然后采用极大似然法计算坐标。

3 质心算法和DV-HOP算法的matlab仿真

对于前面提到的四种非测距的定位算法，本文主要对质心算法和DV-HOP算法进行了仿真，结果如下。

质心算法信标节点与未知节点仿真图

质心算法误差仿真图

DV-Hop算法信标节点与未知节点仿真图

DV-Hop算法误差仿真图

4 小结

从上面的仿真结果可知质心算法的误差较大，定位精度也不如DV-Hop 算法。质心算法由于只是简单的取邻居信标节点所组成的不规则多边形，因此其定位精度不是很高。DV-Hop 算法需要每个信标节点计算自己的平均每跳距离，该算法计算未知节点到信标节点的距离时的累积误差要小很多，所以DV-Hop 算法的定位精度较高。

[1]孙利民，李建中，陈渝，等. 无线传感器网络[M]. 北京:清华大学出版社，2006.

[2]崔莉，鞠海玲，苗勇，李天璞，刘巍，赵泽. 无线传感器网络研究进展[J]. 计算机研究与发展，2005，42(l): 163-174.

[3]杜新恒，程良伦. 无线传感器网络中距离无关定位算法的研究[J].计算机工程与应用2008，44(33): 119-121.

TN962

A

淮南师范学院科学研究基金项目(2016xj46)；2 01 3 高校省级自然科学研究项目( K j 2 01 3 z 2 9 7 )。