无线传感器网络区域混合感知的APIT定位算法

杨雪，王辉

（南京工业大学 电子与信息工程学院，江苏 南京211816）

无线传感器网络区域混合感知的APIT定位算法

杨雪，王辉

（南京工业大学 电子与信息工程学院，江苏 南京211816）

针对无线传感器网络的特点,在深入分析现有近似三角形内点测试(APIT)定位算法的基础上，提出一种改进机制，即区域混合感知的近似三角形内点测试(RMA_APIT)定位算法。该算法根据网络的部署情况，自动调整未知节点的定位区域并引入辅助节点对未知节点进行定位，从而提高定位精度。仿真结果表明，采用RMA_APIT定位算法，节点的定位精度和有效定位比都有较大提高。

无线传感器网络；定位；近似三角形内点测试；混合感知；辅助节点

无线传感器网络(WSNs)的大量应用都需要网络中节点的地理位置信息。另外，了解传感器节点位置信息还可以提高路由效率，为网络提供命名空间，向部署者报告网络的覆盖质量，实现网络的负载均衡及网络拓扑的自配置[1]。无线传感器网络的定位问题主要分为两类：(1)无线传感器网络对自身传感器节点的定位；(2)利用传感器节点对外部目标的跟踪定位，而节点自身的定位是实现外部目标跟踪定位的基础[2]。参考文献[1]对目前存在的部分定位算法的原理及特点做了详尽的分析和描述，并给出了定位系统和定位算法的性能评价参数。到目前为止，现有的无线传感器网络节点定位算法都有各自的特点和应用范围，根据定位的需求，各算法在性能评价参数上各有取舍,没有哪一种算法是绝对优秀的。综合考虑算法的各个性能评价参数，使节点的定位精度最优是定位算法的主要目标。定位算法的分类有很多种,根据定位过程中是否测量实际节点间的距离，可以把现有的定位算法主要分为两类:基于距离(Range-based)的定位算法和与距离无关(Range-free)的定位算法[3]。基于距离的定位算法利用 RSSI、TDOA、TOA和 AOA等技术测量节点之间的距离,然后用数学方法计算节点的坐标,该定位算法能够实现节点的精确定位，但对节点的硬件要求比较高。由于硬件成本、能耗等原因，人们提出了与距离无关的定位技术。与距离无关的定位算法对硬件要求比较低，定位精度随之降低，但是能够满足大多数应用的要求，典型的与距离无关定位算法主要有MDS算法、DV-HOP算法、Amorphous算法、Centroid算法等。

本文首先深入分析现有近似三角形内点测试(APIT)[4]定位算法的原理和性能，针对目前该算法仍然存在的问题，并充分考虑无线传感器网络的特点，提出一种区域混合感知的近似三角形内点测试(RMA_APIT)定位算法。其核心思想是节点根据网络的连接情况应用不同的方法感知节点定位区域，目的是为了自动调整节点的定位区域，从而提高定位精度。通过一系列的仿真实验证明，RMA_APIT算法能够很好地适应WSNs的特点,相比于APIT算法,RMA_APIT算法能够提供更加精确的定位服务。

1 RMA_APIT理论模型和算法描述

1.1 APIT算法

APIT 定位算法是一种基于区域的定位算法[5]，其核心思想是把邻居锚节点组成的多个三角形的交叠区域的质心作为节点的估计位置。APIT算法假设网络中的节点具有获取邻居节点信息的能力，未知节点在通信传播过程中获取所有邻居锚节点的信息以及所有邻居节点的信息，信息包括邻居锚节点的位置信息、未知节点及邻居节点到达锚节点的能量信息。假设未知节点i共有n个邻居锚节点,则n个邻居锚节点可以组成Cn3个三角形,对所有包含该未知节点i的三角形求交叠区域,交叠区域的质心即为未知节点i的估计位置。

APIT算法具有定位精度高、通信开销小等优点[6]，它能够很好地适应WSNs中的节点定位，但深入研究APIT算法原理及其流程后，可以发现APIT算法也有不足之处：

(1)未知节点的邻居锚节点数小于3时，未知节点就成为不可定位节点；

(2)未知节点具有3个或者3个以上邻居锚节点，但节点在任何3个邻居锚节点组成的三角形外部时，未知节点就成为不可定位节点；

(3)未知节点的邻居锚节点数较少，如只有3个邻居锚节点时，邻居锚节点能组成的三角形数较少，InToOut错误或OutToIn错误对节点的定位有较大影响；

(4)未知节点在部署区域的边缘时，未知节点的某一侧不会出现邻居锚节点，这样会使得未知节点不在邻居锚节点组成的三角形内部，导致未知节点成为不可定位节点。

针对APIT存在的诸多弊端，本文提出一种改进算法，即区域混合感知的APIT定位算法(RMA_APIT)。该算法根据网络连接情况，对节点的定位区域进行了调整，以减少不可定位节点数目及提高节点定位精度。

1.2 网络模型及假设

为方便对RMA_APIT算法进行理论阐述,假设网络中的所有节点部署在边长为R的正方形区域内。网络中普通节点的通信半径γ，锚节点的通信半径是普通节点的α(α＞1)倍，节点的邻居锚节点数阈值为 K。网络中的所有节点都可以获得邻居节点的信息。另外，根据无线传感器网络在应用中的特点，模型假设节点的通信区域不一定为理想的圆形区域。

1.3 RMA_APIT算法

仔细分析APIT算法存在的问题可以发现，应用APIT算法不能进行定位的节点可以分为两类：第一类，邻居锚节点数大于等于3而不能进行定位的未知节点；第二类,邻居锚节点数小于3而不能进行定位的未知节点。

为有效减少第一类不可定位节点的数目，不是直接判断未知节点i是否在锚节点组成的三角形MNP内部，而是在节点进行定位前判断未知节点的邻居锚节点数是否大于阈值K，若大于则用APIT进行定位；若节点的邻居锚节点数小于等于阈值K，如图1所示，图中设K=3，则采用下述区域混合感知技术进行定位。

首先，如图1所示，图中三角形实心点表示锚节点，圆形实心点表示普通节点，锚节点的通信区域是以锚节点为圆心、锚节点通信半径αγ为半径的圆形区域，且未知节点一定在其邻居锚节点的通信区域内，所以未知节点i一定在其邻居锚节点 M、N、P通信区域的交叠区域内，即图中A区域。

然后判断未知节点是否在锚节点M、N、P组成的三角形内部。若未知节点i不在三角形MNP内部或In-ToOut错误时，则A区域即为未知节点i的定位区域，即A区域的质心位置为未知节点i的估计位置，如图1(a)所示。若未知节点i在三角形MNP的内部，则用三角形MNP与A区域的交叠区域作为未知节点i的定位区域，即图1(b)中的B区域，B区域的质心即为未知节点i的估计位置。通过区域混合感知技术可对邻居锚节点数小于阈值K的未知节点进行更加精确的定位。

针对第二类不能定位节点，本文引入辅助节点进行定位。首先对整个网络中的节点进行第一轮定位，记录下不能定位的节点j；然后判断未知节点j的邻居锚节点数与已经被定位的邻居节点数之和是否大于等于3个，如果未知节点j的邻居锚节点数与已经被定位的邻居节点数之和大于等于3个,则把已经定位的邻居节点当做辅助锚节点,应用RMA_APIT算法对未知节点j进行第二轮定位，否则未知节点视为不可定位节点，如图2所示，图中三角形空心点表示辅助锚节点。

基于以上描述，给出RMA_APIT定位算法的执行流程图，如图3所示。

2 仿真结果及分析

为了有效评估RMA_APIT算法的性能，本文通过仿真实验的方法将其与APIT算法进行比较分析。

2.1 仿真实验设计

影响节点定位精度的因素很多，本实验主要选择节点数目、锚节点比重和节点无线传输模式的不规则度作为仿真参数，观察这些参数变化对节点定位精度和节点有效定位比的影响。参数定义如下：节点数目定义为部署区域内的节点总数，包括普通节点和锚节点，用N表示；锚节点比重为锚节点数与节点数目的比例，用Ar表示；节点有效定位比定义为能够被定位的节点数(Nl)占节点数目的比例，如式(1)所示，用ELR表示。

实验中具体的参数取值见表1。

表1 实验参数

2.2 仿真结果分析

图4和图5分别给出了节点数目对节点定位精度及ELR的影响。从图4中可以看出，随着节点数目的增加，两种算法的定位精度都在提高，但在相同节点数目的情况下，RMA_APIT算法的定位精度比APIT算法的定位精度高。图5仿真结果显示节点有效定位比随着节点数目增加而增加；在节点数目很低或很高时，两种算法的节点有效定位比很接近，节点数目在100～350之间时，RMA_APIT算法的节点有效定位比明显高于APIT算法的节点有效定位比，这是因为在节点数目很低时，未知节点的邻居节点数目都很少，RMA_APIT算法的区域混合感知技术受到限制，能够引入辅助节点进行定位的节点数少，故节点有效定位比不会有明显提高；在节点数目很高时，两种定位算法的节点有效定位比都接近1，因此也比较接近；当节点数目在 100～350之间时，RMA_APIT算法能够很好地调整未知节点的定位区域，并引入辅助节点进行定位，可以很好地减少不能定位的节点数，故RMA_APIT算法的节点有效定位比要明显高于APIT算法的节点有效定位比。

图6和图7显示了锚节点比重对节点定位精度和ELR的影响。仿真的节点数目为200时，锚节点比重从0.05逐渐增加到0.4。从仿真结果可以看出，随着锚节点比重的增加，RMA_APIT算法和APIT算法的定位精度与节点有效定位比ELR都在增加。在锚节点比重相同的情况下，RMA_APIT算法的节点有效定位比全部大于APIT算法的节点有效定位比，RMA_APIT算法的定位精度也普遍比APIT算法的定位精度高，只有在锚节点比重很小(Ar=0.05)时，RMA_APIT算法的定位精度比 APIT算法的定位精度稍低，这是因为锚节点数太少会导致节点定位误差较大，若再引入辅助节点进行定位，会使误差累积太大，从而影响RMA_APIT算法在低锚节点比重场景下的整体性能。

3 结论与展望

节点定位技术是WSNs中关键的支撑技术之一。本文对APIT定位算法进行改进，提出了区域混合感知的近似三角形内点测试(RMA_APIT)定位算法。RMA_APIT算法根据网络连接情况，对未知节点的定位区域进行调整并引入辅助节点对未知节点定位。仿真实验结果证明，RMA_APIT算法能够适应无线传感器网络的特点，相比于APIT算法，在节点数目相同、锚节点比重相同的情况下，RMA_APIT算法能够提供更加优质的定位服务，在获得相同定位精度的要求下，RMA_APIT算法更能节省网络部署的成本。下一步的工作是研究网络模型及网络部署情况对算法的影响，使算法能够在更加真实的网络环境中取得理想的定位效果。

[1]王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(5):857-868

[2]周四清,陈锐标.无线传感器网络APIT定位算法及其改进[J].计算机工程,2009,35(7):87-89.

[3]冯秀芳,崔秀锋,祈会波.无线传感器网络中基于移动锚节点的APIT的改进定位算法[J].传感技术学报,2011,24(2):269-274.

[4]HE T,HUANG C,BLUM B M,et al.Range-free localization schemes for large scale sensor networks[C].Proceedings of ACM MobiCom,San Diego,California,USA,2003:81-95.

[5]MA D,Meng J E,Wang Bang,et al.Range-free wireless sensor networks localization based on hop-count quantization[J].Springer,2010,DOI:10.1007/s11235-010-9395-y.

[6]周勇,夏士雄,丁士飞,等.基于三角形重心扫描的改进APIT无线传感器网络自定位算法[J].计算机研究与发展,2009,46(4):566-574.

A region mixed-aware APIT algorithm for WSNs

Yang Xue,Wang Hui
(College of Electronics and Information Engineering,Nanjing University of Technology,Nanjing 211816,China)

This work begins with a thorough investigation of APIT localization algorithm.On this basis,a region mixed-aware algorithm(RMA_APIT)is proposed.Based on the deployment of the network,RAM_APIT adjusts the positioning area of the unknown node automatically and introduces assistant nodes that used to position the unknown node,thereby improving positioning accuracy.Simulation results show that RAM_APIT algorithm improves positioning accuracy of a node and the ratio of effective localization nodes significantly.

WSNs;localization;APIT;mixed-aware;assistant node

TP393

A

0258-7998(2012)03-0113-04

2011-09-24)

杨雪，女，1986年生，硕士研究生，主要研究方向：无线传感器网络节点定位技术。

王辉，女，1962年生，博士，教授，硕士生导师，主要研究方向：光传输理论与系统、信号处理与控制技术。