0 引言

作为信息采集和数据处理的关键组成部分，无线传感器网络（ wireless sensor networks,WSNs） 也得到了快速发展。WSNs 是集无线通信技术、传感器技术、嵌入式计算技术、信息处理技术、组网技术等现代网络技术于一体的网络，突出优点是能在恶劣环境下实现无线的信息采集和处理，具有非常广的应用前景。节点的位置信息是WSNs实现应用的重要一环，目前，针对节点定位的研究中有很多很成熟的算法，依据是不是需要测距，主要分为基于测距算法（ range-based） ,典型的有cooperative ranging 算法、NHopmultilateration primitive 算法、Euclidean等，无需测距算法，典型的有DV-Hop 算法、Amorphous 算法、APIT算法、Bounding Box 算法、Centroid 算法等。

由于WSNs 的节点非常多，虽然测距算法有很好的精度保证，但节点必须携带额外的测距设备，这样会很大程度上增加定位成本，而无需测距尽管不如测距那样准确，但在很多应用场合能达到需要的精度，而且在功耗等方面有较大的优势。本文选取无需测距算法中典型的4 个算法，包括Amorphous 算法、APIT 算法、Bounding Box 算法、Centroid算法，分别给出在不同参数条件下的仿真定位效果，以便于技术人员在不同条件下选取最优的算法。

1 无需测距算法原理

1. 1 Amorphous 算法

Amorphous 算法是由麻省理工大学的Nagpal R 等人提出的，其主要思想就是把锚节点和未知节点的跳数以及平均每跳距离的乘积作为两者之间的距离，共分三步： 1） 根据距离矢量交换协议，使网络中的每个节点都获得到锚节点的最小跳数； 2） 平均每跳距离用节点的通信半径表示，未知节点计算到每个锚节点的距离； 3） 利用最大似然估计或者三角测量法估计未知节点的位置。

1. 2 APIT 算法

APIT 算法基本思路是，未知节点首先收集邻近锚节点的信息。假设其周围有n 个锚节点能与未知节点通信，然后未知节点任意选取其中的3 个锚节点，这样就确定C3n个三角形。之后利用PIT 测试法逐一判断未知节点是否在这些三角形中，最后计算包含未知节点的那些三角形重叠区域，把该重叠区域的质心作为未知节点的位置。

1. 3 Bounding Box 算法

Bounding Box 算法是由美国加州大学伯克利分校Semic S N 等人提出的，该算法与APIT 的算法有相似之处，也是计算包含未知节点的重叠区域。只不过该算法定义一种离散的通信模型，这里假定节点的通信范围是以2 倍的通信半径为变长，以自身为中心的正方形。如果未知节点周围有m 个锚节点能与其通信，则计算这些锚节点所组成的正方形重叠区域，以该重叠区域的中心作为未知节点的位置。

1. 4 Centroid 算法

Centroid 算法基本思想是，网络约定一个定位时间，在该时间段内，锚节点向未知节点发送包含自身未知信息的数据包。未知节点记录下从每个锚节点的发来的数据包数目，等到定位时间结束后，未知节点计算与锚节点的通信成功率。根据预先设定的阀值，选出那些通信成功的锚节点，最后把这些锚节点的质心作为未知节点的坐标。

2 算法仿真比较

本文给出了以上述4 种无需测距定位算法在不同参数下的仿真结果比较，通过分析这些结果，结合实际情况可以选择最优的定位算法。

本文分别从定位误差和定位精度2 个方面考虑，模拟200 m × 200 m 的区域，节点的部署都采用随机撒播的方式。

本文平均定位误差定义为估计位置到真实位置的欧式距离与通信半径的比值。定位比例定义为除锚节点之外成功定位的节点数和未知节点的总数的比值。使用Matlab 仿真软件。

1） 假定区域有150 个节点，包括锚节点和未知节点，采用散乱撒播的方式。无线传感器的节点的能量有限，通信半径一般在几十米左右、不失一般性，这里假定通信半径为30 m,把锚节点的比例作为变量，给出比较仿真结果如图1、图2 所示。

图1 散乱布置条件下平均定位误差随锚节点比例变化趋势图

图2 散乱布置条件下定位比例随锚节点比例变化趋势图

2） 和第一部分参数设置相同，但这里固定锚节点比例为10 %,考察定位误差和定位比例随通信距离变化情况，仿真结果如图3、图4 所示。

图3 散乱布置条件下平均定位误差随通信半径变化趋势图

图4 散乱布置条件下定位比例随通信半径变化趋势图

3） 采用规则部署的方式，即把这部分区域采用网格法划分成一个个规则的小正方形区域，每个节点部署随机部署在小正方形边上。为了和第一，二部分相似，这里设置小正方形边长为17 m,那么，总节点数大约为144 个，锚节点和未知节点的部署仍采用随机撒播方式。这里假定通信半径为30 m,考察定位误差和定位比例随锚节点比例变化情况，仿真结果如图5、图6 所示。

图5 规则部署条件下平均定位误差随锚节点比例变化趋势图

图6 规则部署条件下定位比例随锚节点比例变化趋势图

4） 参数和第三部分相同，只是这里固定锚节点比例为15 %,因为在这一部分锚节点比例为10 % 时仿真显示有些算法的定位效果不太明显，不易对比。考察定位误差和定位比例随随通信半径变化趋势，仿真结果如图7、图8 所示。

图7 规则部署条件下平均定位误差随通信半径变化趋势图

图8 规则部署条件下定位比例随通信半径变化趋势图

通过这些仿真图，可以很方便地查找适合需要的定位算法。

例如： 对某一区域进行定位，属于随机散乱部署情况，要求定位精度不是很高但要稳定，但是定位比例要求要大，最重要成本要求很小，只是简单的测试，而且要求能长时间工作。在这种要求情况下，考察图1 ~ 图4.注意到随机散乱部署的情况下，Amorphous 算法虽然定位比例几乎为100 %,但误差大，且有很大跳跃性，排除。APIT 算法虽然定位精度最高，但定位的比例随锚节点变化非常明显，这显然会需要很多锚节点，这样会很大程度上增加成本，排除。

WSNs 节点的通信半径会随着发射功率减少而减少，为了能长时间工作，要求网络能在通信距离较小时也能准确定位。

Bounding Box 算法和Centroid 算法2 种算法，定位效果随通信半径变化的趋势（ 图3、图4） 基本吻合，而且2 种算法的定位误差在通信半径相同时，变化趋势（ 图1） 基本相同，但注意到图2,在锚节点比例相同情况，而且在锚节点比例较小区域（ 20%以下） ,Bounding Box 算法比Centroid 算法有更高的定位比例，所以，最终选择Bounding Box 算法。然后根据实际具体的参数部署节点，在定位算法上选择BoundingBox 算法即可。

使用Matlab 软件给出一个具体的函数，例如： 对图6 中Bounding Box 算法的变化趋势图，利用Matlab 曲线拟合函数，测试结果如图9 所示。

图9 数据拟合曲线图

可以发现N = 2 阶的拟合曲线和原曲线比较接近，故采用N = 2 阶曲线拟合函数，根据Matlab 的计算结果，有：

确定这样一个函数后就可以根据实际具体的需要值代入就可以计算出定位的效果。其他的算法在不同参数条件下利用这种方法确定一个函数，进而计算出定位效果。

这里分别考虑散乱部署和规则部署2 种情况，对于每一种情况，f（ x） ,g（ x） 表示拟合定位误差函数和拟合定位比例函数，x i（ i = 1,2,3,4） 分别表示APIT 算法，Amorphous算法，Bounding Box 算法，Centroid 算法锚节点比例，y i = 1,2,3,4分别表示以上4 种算法的通信半径，wi,w2分别表示考虑定位误差和定位比例的权重，定义定位效果Ci,这样有：

根据实际给出的成本参数转换为锚节点的比例，再根据实际要求的工作时间长短换算成一定通信半径，代入上式就可以求出定位效果，最后有：

根据式（ 3） 求出定位效果中取得最大值的算法，这样就确定哪种算法最优了。

3 结束语

本文给出了无需测距算法中典型的4 种定位算法，给出了它们分别在不同参数下的仿真定位效果，对工程人员选择适合的算法提供了很好借鉴，在此基础上，本文提出了一种基于数据拟合方法的定位效果逼近函数，并根据这些函数给出了具体的计算公式，这样就能根据实际要求，转换为某范围或某具体值代入计算公式就可以确定哪种算法最优了。