无线传感器网络非测距定位算法比较

安徽理工大学 戴海祥 洪 炎 杨东东 黄国维 丁冰倩

无线传感器网络非测距定位算法比较

安徽理工大学 戴海祥 洪 炎 杨东东 黄国维 丁冰倩

基于非测距技术的定位方法没必要知道节点间距离，因此对硬件的要求较低，在无线传感网络中被广泛的应用。通过对各种非测距定位算法的原理分析，从节点的分布密度、测量误差、硬件消耗、分布形式、扩展性等方面对无线传感器网络非测距定位算法进行比较，分析出各算法的优缺点及可应用的范围，对无线传感网络定位算法的研究和选择有重要意义。

无线传感网络；非测距定位算法

0 引言

基于非测距技术的定位方法顾名思义就是不需要知道两个节点之间的距离为多少，因此在硬件方面这类算法的要求相比于其他算法较低，在无线传感网络中被广泛的应用。目前该定位算法主要有两类，一种是对节点间距离进行估计，再用三边定位算法进行定位；另一种是通过节点间信息的交互逐渐缩小未知节点所在的区域，反复多次后将区域的质心作为未知节点的位置。

1 质心定位算法

该算法的原理是，信标节点不断发送自己的位置、ID等信息，在通信范围内的待测节点接受这些信息，当待测节点接受到信息的信标节点的个数超过三个时，就可以将信标节点组成的几何图形的质心作为待测节点的最终位置。公式如(1)所示：

其中，（xi，yi）为待测节点通信范围内能够进行信息交互的信标节点坐标，（x，y）为待测节点坐标。

2 APIT定位算法

APIT定位算法简单来说就是从与待测节点能够进行信息交互的邻居节点中任意取出3个组成三角形，然后用PIT判定法来判断待测节点和三角形的位置关系，按照以上的方法核对所有的三角形组合，最终得出待测节点在这些三角形重叠的区域中。如图1所示。

图1 APIT定位算法基本原理图

如图1所示，阴影部分表示所有包含待测节点的锚节点三角形最终重叠的部分，将该部分的几何中心近似为待测节点的定位坐标。

3 DV-HOP定位算法

DV-Hop算法的最主要的思想是：利用估计的两节点间的距离作为实际的距离，然后利用三边测量法得到所求节点的位置，具体步骤如下：

（1）最小跳数值的记录

锚节点不停地向外发送自己的信息，如果待测节点在其通信半径内，就会接受这些信息，其中包括锚节点的ID，跳数值，具体的位置等，接收点将最小跳数值记录，如果接收到同一锚节点的信息，则将较大的那个跳数值删除，同时将跳数值加1，重复以上过程直到接受点记录到了定位区域内所有锚节点的最小跳数值。

（2）平均跳距的计算

定位区域内锚节点的个数为n，假设任意选取其中的两个i,j的坐标为（xi，yi），（xj，yj），在得知跳数、ID、位置等信息后，由公式(2)计算出平均跳距。

其中，hj表示两节点间的跳数，求得平均跳距后，与最小跳数相乘，将该值近似为实际距离。

（3）三边测量法定最终位置

根据所求节点间的实际距离，利用三边测量法得到所求节点的位置。

4 基于非测距的定位算法的比较

定位算法性能的比较大致从节点分布的类型、定位的误差、所需硬件的成本、可扩展性等方面进行比较的，下面对这几项参数进行简单的介绍。

(1)节点分布类型

在定位区域内，参考节点部署的密度越大，定位的精确度也就会越高，但也会对硬件设备造成更大的损耗。

(2)定位误差

待测节点的定位误差可以体现最终的定位效果。

(3)硬件成本

无线传感网络需要考虑的因素有很多，其中比较重要的因素就是硬件成本和整个网络的能耗问题，一方面是所用传感器节点的数量、大小、种类、能耗等，另一方面是节点之间进行数据和信息传输时网络的损耗和算法对数据进行处理的消耗。

(4)可扩展性

传统的定位算法往往只有在特定的环境和条件下才能到达预想的定位效果，随着科技的发展，硬件设备的升级，传统的定位算法能够有所改进，适用性更强。

5 算法比较与分析

由表1可知，虽然质心定位算法方法原理简单，但定位精度太低，适合运用于一些对定位精度要求不太高的情况。DV-HOP算法相比较而言虽然误差较小且有着不错可扩展性，但是功耗较大，如果能在这方面有所改进，这两种算法的应用前景将会很广泛。相比较而言，APIT 定位算法定位精度不错且可扩展性较强，硬件消耗也较低，但是该算法的定位效果对节点部署的密度依赖性太强，如果在这方面有所改进，APIT算法的应用前景将会有很大的提升。

表1 基于非测距的定位算法的各项参数比较

[1]李建中,高宏．无线传感器网络的研究进展[J]．计算机研究与发展,2016,45(01)：1-15．

[2]石为人,袁久银,雷璐宁．无线传感器网络覆盖控制算法研究[J]．自动化学报,2009,35(5)：540-545．

[3]张涛,余翔宇,蓝俊健,等．改进的无线传感器网络节点虚拟力部署方法[J]．计算机应用研究,2015,32(11)：3356-3358．

[4]孙利民,李建中,陈渝,等．无线传感器网络[M]．北京：清华大学出版社,2005．

戴海祥（1994—），男，江苏人，研究生，主要研究方向：无线传感网络定位。