一种改进的无线传感器网络定位算法

张欣慧，熊肖肖，赵学健，孙知信

(1.南京邮电大学 物联网学院，江苏 南京 210003；2.南京邮电大学 现代邮政学院，江苏 南京 210003)

0 引 言

无线传感器网络具有低功耗、低成本、分布式和自组织的特征，可以广泛构造信息访问的平台以实现一些新的功能，例如对各种检测对象的信息收集，检测与跟踪指定范围内的复杂目标，等等。为了在无线传感器网络中监测传感器网络的活动情况以实现一些具体的网络操作和网络应用，节点的位置信息非常重要[1]。事件发生的位置以及节点的信息都建立在监测信息的基础上，毋庸置疑，没有定位信息的监测消息往往是毫无意义的[2]。因此，位置信息在无线传感器网络应用中起到了关键作用。

在现阶段，常见的测距方法包括：到达时间(ToA)、到达时间差(TDoA)、到达角度(AoA)和接收信号强度指示器(RSSI)等等。这种类型的算法虽然精度较高，但同时也带来了硬件要求极高和通信消费严重等问题。因此，这些方法并不适用于低能耗或低成本的应用程序。具体的定位算法可以根据节点处理信息的方式划分为集中式定位和分布式定位，或根据是否需要测量距离或角度信息划分为基于测距的定位和无需测距的定位。无需测距的定位算法不需要测量绝对距离或方向，依靠网络连通性的信息或其他方法即可完成定位。常见的此类算法有凸定位算法、质心定位算法、DV-hop定位算法、不定型定位算法、APIT算法等。

文中首先介绍了APIT算法的演变史并总结了每种算法的优缺点，指出了未来的研究方向。在此基础上，详细分析了费马点模型及基于中垂线分割的PB-APIT算法的思想，提出了一种基于三角形中线垂面分割的APIT-3D的改进算法(vertical plane of triangle midline-approximate point-in-triangulation test-3D，VTM-APIT-3D)，并通过仿真来验证和评估算法的性能。

1 相关技术研究

APIT算法于2003年提出[3]，存在的一些问题包括：(1)锚节点稀疏时对网络覆盖率影响较大，网络边缘处的未知节点定位难，可扩展性较弱；(2)需要判断测试三角形内的静止未知节点是否出现假阳性；(3)重叠区域中节点的定位精确度需要改进。对于APIT算法存在的问题，提出了一些改进算法：文献[4]提出了一种基于三角形重心扫描的改进APIT算法，显著地提高了节点的平均精度。文献[5]提出了近似三角形内点APIT定位算法和DV-HOP定位算法相结合的混合定位算法，并证明了其有效性。文献[6]将未知节点升级为锚节点，提出了一种基于中垂线分割的算法，命名为PB-APIT。三角形被每一边的垂直平分线划分为4或6个子区域，通过检测的信号强度来确认未知节点位于某一个子区域，该方案使定位精度大约提高18%，解决了问题1；文献[7]降低了“In-To-Out Error”和“Out-To-In Error”误判的可能性，以增加判断的正确性；文献[8]提出将重叠区域划分为多个子区域以减小三角形区域的大小，解决了问题3。然而，由于无线传感器网络的节点是随机分布的，网络拓扑结构的建立相当困难，上面讨论的改进算法只能分析一些特殊情况，随机性问题仍然是一个难点。

此外，现实中的无线传感器网络往往被布局在复杂的三维地形中，为了实现三维环境下更为精确的节点定位，一些文献对二维的APIT算法进行了改进，将其扩展到三维定位上来。文献[9]在APIT-3D算法中使用了正中面的概念。如果传感器网络部署在近似立方体空间中，即可借助正中面和通信半径去除无节点包含的立方体，以缩小节点的定位范围。文献[10]在APIT中使用蒙特卡洛方法和RSSI滤波器采样方法，仿真结果表明MC-APIT的最低位置误差高达10%。文献[11]提出一种融合了APIT，RSSI和PSO且无需测距的定位算法。该算法在信标节点交换信息的过程中对信标节点的相邻节点的RSSI测量结果进行加权，基于强度来测量距离。通过PSO和成本函数对相邻节点的位置和速度矢量连续迭代，最终使用APIT通过PSO计算的信标节点和相邻节点的距离来计算未知节点的坐标。文献[12]认为APIT算法的网络覆盖率过低，因此提出了结合DV-hop的APIT算法，改进后的算法解决了未知节点周围的邻居信标节点少于三个就无法定位的问题。实验结果表明，该算法的定位精度提高了7.4%，网络覆盖率提高了31.3%。通过对这些研究的深入分析，文献[13]提出了基于费马点分离的FM-APIT-3D算法，利用费马点将大三棱锥划分为四块小三棱锥。当无线通信半径为30时，该算法的定位精度提高至多约17.2%，网络覆盖率始终是100%。

上述文献均为了解决无线传感器网络中更为精确的节点定位问题，但是以上大部分定位算法仅适用于二维平面中，部分可用于三维环境中的定位算法也存在定位精度与网络覆盖率较低的问题。故文中利用数学模型对现有的三维定位算法进行改进，以提高定位精度与网络覆盖率。

2 基础模型分析

2.1 费马点模型

费马点是三维空间内的特殊点，类似于质心和内部中心。如果存在一个点，它到某有限点集的所有顶点的距离和最小，这一点便被称为费尔马点。在任意三棱锥中，费马点必然唯一存在且可以将三棱锥划分为四个子三棱锥。建立三维坐标系后，三棱锥的四个顶点为A(x1,y1,z1)、B(x2,y2,z2)、C(x3,y3,z3)、D(x4,y4,z4)，可以通过式1计算费马点F(xF,yF,zF)：

(1)

文献[14]提出的FM-APIT-3D算法和文献[12]提出的DFPLE算法均使用费马点模型定位未知节点。除此之外，费马点模型还可被用于其他算法中。文献[15]提出了一种允许计算是从云跨越到网络的无线传感器网络分布式平台，它减少了传感器网络中的传输、中间网络以及云基础设施。该平台是完全分布式的，允许均匀网络中的每一个节点接受来自用户的连续查询，找到所有满足用户查询的节点，再找到一个最佳节点(费马点)对网络进行查询，并为用户提供结果。文献[16]提出了一种基于三角剖分的bmO(nlogn)最短路径算法，结合改进的Dijkstra算法和费马点构建一个低能见度图，可以在较短的时间内计算出近似最短路径。文献[17]提出利用费马点进行3D注视定位，该方法使用基于3D重建场景的激光雷达对一个自由漫游的眼动仪进行定位，提供了在复杂的静态环境(例如犯罪现场)中进行搜索任务的策略。

以上算法均通过使用费马点划分空间来达到优化定位模型的目的，但仍存在一些问题：

(1)费马点模型借助费马点来估计节点的位置，但因分割前后均使用APIT-3D算法来判断未知节点的有效范围，算法过程重复且单一。

(2)费马点模型多次把未知节点估计在一个形为三棱锥的有效范围内，再通过计算这些三棱锥重叠范围的质心来估计未知节点的坐标。由于同为三棱锥的估计范围容易造成累积误差，导致定位精度较低。

(3)未知节点通信范围内的邻居锚节点有很大的概率会少于四个，这会严重影响定位精度或导致网络覆盖率降低。锚节点的密度是影响定位精度的关键因素，锚节点越多，定位精度越高，但单纯地添加锚节点又会增加能耗和成本。

(4)APIT算法选择周围邻居节点密度相对较高的未知节点来模拟运动。当未知节点周围的邻居节点密度较低时，势必会影响到算法的实施过程。

因此，文中提出一种新的使用费马点模型的三维定位算法，其定位精度和网络覆盖率与FM-APIT-3D算法和DFPLE算法相比均有所提高。

2.2 PB-APIT算法

PB-APIT算法针对二维的APIT算法进行改进，是一种仅适用于二维平面的二维定位算法。该算法的执行步骤如下：

(1)第一步与APIT算法相似，未知节点与周围的邻居节点交换各自从测试三角形的三个锚节点接收到的信息，比较二者接收到的信号强弱，也顺便比较未知节点自身从测试三角形的三个锚节点接收到的信号强弱。

(2)利用PIT算法判断未知节点位于测试三角形的内部或外部。若未知节点周围存在一个邻居节点，它接收到的来自测试三角形的三个锚节点的信号强度都大于或小于未知节点所接收到的，则该未知节点位于测试三角形内；反之，则位于测试三角形外。

(3)如果未知节点位于某测试三角形的内部，则利用测试三角形三边的中垂线对测试三角形进行分割。对于直角三角形和钝角三角形，可被分割为四个小区域；对于锐角三角形，可被分割为六个。

(4)由于已经比较过未知节点从测试三角形的三个锚节点接收到信号的强弱，故可以直接判断出未知节点位于哪个小区域内。

PB-APIT算法与APIT算法的不同之处在于，有效区域不再是三角形而是分割后的小区域，求出所有小区域的重叠区域，其质心即为未知节点的坐标。有效区域从三角形到多边形小区域的改变，减少了累积误差的产生，提高了定位精度，有着较好的使用前景。但由于现实中的无线传感器网络往往被布局在复杂的三维地形中，二维的PB-APIT算法在现实场景中使用受限，故文中将适用于三维环境的费马点模型与PB-APIT算法中的分割思想结合，提出一种基于三角形中线垂面分割的APIT-3D的改进算法(简称VTM-APIT-3D)。

3 VTM-APIT-3D算法

3.1 算法流程

(1)通过执行APIT-3D算法找到所有包含有未知节点的三棱锥。

(2)在某一三棱锥中找到一个名为费马点的特殊点，将该点链接到其他四个顶点，把三棱锥分割成四个部分，然后通过APIT-3D算法判断哪个子三棱锥中包含有未知节点。

(3)在该子三棱锥内，找到顶点不含费马点的三角形，取其任意一边作该边的中线，再过这条中线作三角形面的中线垂面，把该三棱锥划分为两部分。

(4)之前执行步骤2中的APIT-3D算法时已经得出未知节点从该三角形的三个锚节点接收到信号的强弱，根据信号强弱判断未知节点位于中线垂面两侧的哪一侧。若存在两个锚节点接收到的信号强度一样大的情况，则可认为未知节点位于中线垂面两侧的任意小区域中。

(5)再通过同样的方法找到其他包含未知节点的分割小区域，通过求这些不规则小区域重叠范围的质心来估计未知节点的坐标。

3.2 三角形中线垂面的定义

VTM-APIT-3D算法中所提到的三角形中线垂面是指在某三角形的任一边作它的中线，然后过这条线作一个与该三角形所在平面垂直的面，这个面便被称为三角形中线垂面。如图1所示，三角形的三个顶点坐标分别为A(x1,y1,z1)，B(x2,y2,z2)，C(x3,y3,z3)，M为BC的中点。

直线AM的方程可简写为：

(2)

平面ABC的法向量可简写为：

(3)

三角形中线垂面AMPQ的方程为：

(4)

如图1所示，三角形ABC的中线为直线AM，其中线垂面为面AMPQ。通过APIT-3D算法已得知未知节点N位于三棱锥F-ABCN内，且已比较过未知节点N从三角形ABC的三个锚节点接收到信号的强弱。若锚节点B接收到的来自未知节点N的信号强度比锚节点C接收到的信号强度都大，则N位于中线垂面偏B的一侧；反之，N位于中线垂面偏C的一侧。

图1 三角形中线垂面分割模型

4 实验仿真和结果分析

本节对VTM-APIT-3D算法、DFPLE算法和FM-APIT-3D算法的性能进行详细的对比和分析。仿真模拟实验在Intel双核2.3 GHz CPU，4 GB内存，Matlab2014a的平台上进行。所采用的网络布局为随机分布在100 m×100 m×100 m大小的立方体网络中的200个节点，并选中其中N个节点作为锚节点，其余为未知节点。

4.1 性能评估

算法改进的目的之一就是提高定位精度，定位精度由定位误差判断，定位误差越小，定位精度越高。未知节点i的定位误差计算公式如下：

(5)

其中，(xi-act,yi-act)为节点i的实际位置；(xi-est,yi-est)为节点i的估计位置；R为节点i的通信半径。

假设该网络中一共有M个节点，其中N个为锚节点(i=1至i=N为锚节点，i=N+1至i=M为未知节点)，则所有未知节点的平均定位误差如下：

(6)

下文从定位精度与网络覆盖率的角度，比较VTM-APIT-3D算法、DFPLE算法和FM-APIT-3D算法的性能。

4.2 VTM-APIT-3D算法仿真结果

取随机分布在100 m×100 m×100 m大小的立方体网络中的200个节点进行仿真实验，其中20个节点为锚节点，其余为未知节点。定位结果如表1所示。

表1 定位结果分析(R=15)

从表1可以看出，VTM-APIT-3D算法定位精度较高，所有的未知节点都能被定位且定位误差较小，因此该算法在优化定位方面效果较为理想。

4.3 不同锚节点数量下的定位精度

如图2所示，当节点通信半径R=16，且锚节点的数目N从1逐渐增加到50时，三种算法的定位精度均有所提高。由于参考节点数量和测试三棱锥数量的增加，未知节点定位的估计范围被缩小，定位精度自然就提高了。此外，锚节点对节点定位的可能性有直接影响。当锚节点数量较少时，VTM-APIT-3D算法的定位精度明显优于DFPLE算法和FM-APIT-3D算法。VTM-APIT-3D算法改进了定位模块的划分，缩小了定位的估计范围，加快了定位速度。定位的估计范围可减少至其他算法的二分之一。更重要的是，VTM-APIT-3D算法可以解决无法定位的情况，所以定位精度有较大提高。

图2 不同锚节点数量下的平均定位误差

4.4 不同通信半径下的定位精度

如图3所示，当锚节点数量N=18，且节点通信半径R从1逐渐增加到30时，三种算法的平均定位误差都快速降低。这是因为R的增大使未知节点可以与更多的锚节点进行通信，所以测试三棱锥的数量不断增长，节点的估计范围逐渐减小。由于节点通信半径的大小对定位精度的影响尤为明显，可以得出结论：VTM-APIT-3D算法的定位精度明显优于DFPLE算法和FM-APIT-3D算法。随着R的增加，一跳通信范围内的锚节点数目也会更多，VTM-APIT-3D算法获得的测试三棱锥数量也更多。当R=30时，VTM-APIT-3D算法的定位精度提高了约17.2%。

图3 不同通信半径下的平均定位误差

5 结束语

文中提出利用中线垂面切割三维区域的思想，减少了使用费马点模型的算法中多次把未知节点估计在三棱锥形状的有效范围内造成的累积误差。仿真结果表明，与其他使用费马点模型的DFPLE算法和FM-APIT-3D算法相比，利用VTM-APIT-3D算法在三维环境中对未知节点进行定位，定位精度和网络覆盖率均有明显提高。当无线通信半径为30时，其定位精度提高至多约17.2%，网络覆盖率始终是100%。当然，该算法相对于DFPLE算法和FM-APIT-3D算法而言时间复杂度较高，网络能耗也有所增加，今后的研究方向应在提高定位精度和网络覆盖率的同时注重减少定位所需的能量消耗。