无线传感器网络中AOA节点定位改进算法研究

王梓有，周宪英

（1.海军航空工程学院 山东 烟台 264001；2.92941部队 辽宁 葫芦岛 125001）

近年来，随着无线通信、集成电路、传感器以及微电系统等技术的飞速发展和日益成熟，被誉为全球未来三大高科技产业之一的无线传感器网络（WSN，Wireless Sensor Network）引起了全世界范围的广泛关注[1]。随着物联网概念的提出，作为其关键技术的传感器技术成为人们研究核心，随着无线传感器网络的应用逐渐深入到人们生活的方方面面，其核心支撑的节点定位技术也得到不断的改进、推广。

在WSN中，传感器节点随机分布在监测区域内，其中部分节点能够通过携带自身定位设备或人工部署的方式获得自身的精确位置，此类节点被称为锚节点（anchor node）；其他未知节点（unknown node）只能根据锚节点位置按照某种定位机制估算出自身位置[2]。锚节点所占的比例直接影响到传感器网络的造价。根据是否需要测距，节点定位算法分为两类：基于测距（range-based）的定位算法和无需测距（range-free）的定位算法[3]。Range-free算法仅仅依靠网络连通性等信息就能够实现定位，其主要代表算法[4]有质心算法（Centroid）、DVHop （Distance Vector-Hop）、 凸 规 划 （Convex） 和 APIT（Approximate Perfect Point In Tri-angulation Test）等，无需测距的定位算法对硬件的要求不高，但通常定位精度不高[5]；基于测距的定位算法在定位过程中需要对节点间的角度信息或者距离等进行测量，其典型算法有接收信号强度法（RSSI，Received Signal Strength Indicator）、 信号传输时间法（TOA，Time of Arrival）、信号到达角法（AOA，Arrival of Angle）等，通过测量未知节点与锚节点之间的距离或角度信息，再运用三边测量法、三角测量法或最大似然估计法计算未知节点的位置信息[6]。Range-based算法定位精度较高，但对无线传感器网络节点的硬件、成本有一定的要求[7]，未来研究趋势是低成本、高能效的角度或距离测量技术及相关的定位算法。

基于信号到达角度的定位算法是一种典型的基于测距的定位算法，通过某些硬件设备感知发射节点信号的到达方向，计算接收节点和锚节点之间的相对方位或角度，然后再利用三角测量法或其他方式计算出未知节点的位置。本文首先介绍了典型的基于信号到达角度的节点定位算法，在此基础上，提出了一种改进的算法，即在对定位结果进行求精校正的阶段，通过选择过滤误差较大的估计位置，提高系统的定位精度，使最后的定位结果更加有效。

1 理论分析

1.1 基于信号到达角度的定位算法

算法第一步为测量阶段，即未知节点通过特殊设备测量得到在通信范围内的锚节点的信号到达角度信息。

第二步利用夹角射线原则解方程，计算未知节点的估计位置，假设未知节点 P（x，y），测量 A（x1，y1）、B（x2，y2）两个锚节点的信号到达角度信息为α、β，解方程：

可得未知节点P的坐标

第3部进行求精校正。当未知节点通信半径内有多个锚节点时，将两个锚节点作为一组分成不同排列组合，其结果会有多个估计位置，将多个估计位置组成的几何图形的质心作为未知节点的最终估计位置。

算法的一般流程图如图1所示。

图1 算法流程图Fig.1 Flow chart of algorithm

1.2 估计位置过滤

当未知节点的通信半径内有多个锚节点时，对于任意不共线的两个锚节点都能确定一个估计位置，由于锚节点的选择问题，估计位置可能存在某些误差较大的点，将这些估计位置排除，会提高系统的定位精度。

过滤误差较大的估计位置的方法：假设有A（xa，ya），B（xb，yb），C（xc，yc），D（xd，yd），E（xe，ye）5 个估计位置，首先计算任意两个估计位置间的距离为 Sij（如表1所示），Sij=

表1 估计位置之间的距离Tab.1 Distance of the estimated location

设定一个距离阈值d，且节点与自身的距离取为∞，当表中存在某一行的距离值均大于d时，认为该点为不可靠位置，不参与计算。若A、B、C、D为可靠位置，则将4个位置构点的最终估计位置。

基于上述思想，对原有算法最后一步进行了求精，即求多个估计位置的平均值时，排除了误差较大的位置，对算法进行了改进，为了陈述上的统一，对于改进后的算法称为基于信号到达角度的改进定位算法（Improved AOA Localization Algorithm for Wireless Sensor Network，IAOA）。

算法的适用条件：

1）无线传感器网络节点部署在二维平面内，传感器节点都搭载有特殊硬件，可测得在通信半径内的邻居锚节点的信号到达的角度值。

2）只有当估计位置个数大于等于3个时，才进行估计位置的过滤。对于只有两个估计位置的，直接取两个点的中点作为节点的最后估计位置。当只有一个估计位置时，该位置则为节点的最终估计位置。

2 仿真分析

为检验改进算法的性能，用MATLAB仿真工具对基于信号到达角度的定位算法（AOA）和本文提出的算法（IAOA）进行仿真实验。

2.1 仿真环境设置

在100 m×100 m的监测区域内，随机部署传感器节点。传感器节点数目为N，锚节点数目为n，传感器节点的通信半径r，角度测量偏差Δ。

定位误差：节点实际位置和估计位置之间的距离。

定位覆盖率：能够进行定位的未知节点数与总的未知节点个数之比。

为了保证实验的准确性，针对不同情况，本文分别进行了多次仿真，观察、统计仿真结果，对多次结果求平均作为最后的评价结果。

取 N=50，n=10，r=50，Δ=3°（基于射频的到达信号的角度测量标准偏差值在 3°左右[8]），d=0.08r，未知节点的定位误差如图2所示。

可见，IAOA的平均定位误差较小，算法的定位精度有了一定的提升。

2.2 节点通信半径对定位结果的影响

节点通信半径是直接影响算法定位效果的重要因素，节点的通信半径越大，覆盖的监测区域越大，未知节点的邻居锚节点数目就越多，定位的覆盖率和定位精度可能就越高，图3分别给出了节点通信半径在10～50时，两种算法的定位精度与定位覆盖率的情况。

图2 未知节点的定位误差图Fig.2 Localization error of unknown nodes

图3 通信半径对定位结果的影响Fig.3 Communication radius influences on positioning accuracy

从图3（a）可以看出，随着节点通信半径的增大，两种算法的定位误差都在逐渐下降，当r=30时，改进算法的定位精度明显高于原有算法。继续增大节点的通信半径，定位精度提升的效果不是很明显。图3（b）表明，改进算法的定位覆盖率与原算法基本一致，没有多少改进，由于必须有多个估计位置时，算法才对结果进行排除求精，所以算法仅仅是对定位精度进行了提升，并没有解决不能定位的盲区问题。因此，下文中将只针对定位精度对两种算法进行比较。

2.3 锚节点个数对定位精度的影响

一般来说，锚节点个数越多，未知节点监测到的锚节点数越多，定位覆盖率就越高，定位误差相对较小，定位性能就越好。但是，锚节点数量增多势必会增加网络的成本，两者之间的矛盾是不可避免的，实际情况下，在能够满足定位需求的前提下，锚节点数目应尽可能的少。下面将观察锚节点数量对算法定位精度的影响。

由图4可见，随着锚节点个数的增加，算法的定位精度都有所提升，但是改进算法下降较快，定位精度较高；当锚节点个数达到20时，改进算法其定位精度趋于平缓。

2.4 节点密度对定位精度的影响

单位面积上部署的节点数量，称为节点密度。对于一定的监测区域，当节点密度高时，在通信半径相同的情况下，未知节点更容易被更多的锚节点监测到，定位精度相对较高。

图4 锚节点数目对定位精度的影响Fig.4 Anchor node number influences on positioning accuracy

实验中，节点的通信半径r固定不变，锚节点密度（锚节点与所有节点的比例）为10%，改变节点数量，观察实验结果。

图5表明，当网络监测区域不变时，随着网络中节点数目的增多，节点密度增大时，算法的定位精度都在提高，且改进算法依旧能有较好的定位精度，但是节点数目的增加势必会增大节点间的通信量，能耗也随之增加，因此，节点数目的选择应综合考虑，达到所需要的定位精度即可。

图5 节点数目对定位精度的影响Fig.5 Node number influences on positioning accuracy

3 结 论

文中提出的算法对基于信号到达角度的定位算法进行了改进，对最后的估计位置进行了选择滤除，仿真实验表明，本算法在定位精度方面与改进前方法有较大的提高，应用范围也更加广泛。但是改进算法对锚节点的密度有局限性，即网络内未知节点的邻居锚节点平均数目大于3时，算法才能体现出其优越性，所以改进算法不能有效解决网络中锚节点密度较低时，定位覆盖率低的问题，网络中不能定位的盲区问题还有待进一步研究。

[1]王殊，阎毓杰，胡富平，等.无线传感器网络的理论及应用[M].北京：北京航空航天大学出版社，2007.

[2]YIXiao，LIUYu.Anovel environmentself-adaptivelocalization algorithm based on RSSI for wireless sensor network[C]//The 2010 IEEE International Conference on Wireless Communications， Networking and Information Security （IEEE WCNIS 2010）.Beijing.China:IEEEComputer Society，2010:360-363.

[3]宋文，王兵.无线传感器网络技术与应用[M].北京：电子工业出版社，2007.

[4]HE Tian，HUANG Cheng-du， Brain M Blum， et al.Rangefree Localization Schemesfor Large Scale Sensor Networks[C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Networking （MobiCom）， San Diego，California， September， USA:ACM Press，2003:81-95.

[5]衣晓，刘瑜.无线传感器网络Range-free自身定位算法仿真分析[J].海军航空工程学院学报，2009，24（4）:369-375.YI Xiao，LIU Yu.Wireless sensor network range-free localization algorithm simulation analysis[J].Journal of Naval Aeronautical and Astronautical University，2009，24 （4）:369-375.

[6]孙利民，李建中.无线传感器网络[M].北京：清华大学出版社，2005.

[7]Langendoen K，Reijers N.Distributed localization in wireless sensor networks:Aquantitativecomparison The Int’l[J].Journal of Computer and Telecommunications Networking，2003，43（4）:499-518.

[8]Collier S L，Wilson D K.Performance bounds for passive sensor arrays operating in a turbulent medium：plane-wave analysis[J].Acoust Soc America，2003，113（5）:2704-2718.