无线传感器网络节点自身定位算法研究

　　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 个锚节点能与其通信，则计算这些锚节点所组成的正方形重叠区域，以该重叠区域的中心作为未知节点的位置。