邮局订阅号：82-946120元/年技术创新软件时空《PLC 技术应用200例》您的论文得到两院院士关注一种基于TDOA 与三角形加权质心定位的混合算法A Hybrid Algorithm Based On TDOA And Triangle Weighted Centroid Localization(1.兰州大学;2.总参谋部通信训练基地)傅涛1,2杨凌1李晓燕1闫胜武1FU Tao YANG Ling LI Xiao-yan YAN Sheng-wu摘要:提出一种基于TDOA 与三角形加权质心定位的混合算法,该算法仅采用三个信标节点,充分利用节点的数据处理单元和通信单元,通过三角形加权质心定位算法得到一个定位信息,同时待定节点充分利用接收信号进行相关运算,求时差得到另一个定位信息。
对两组定位信息比较、取均值,得到相对稳定的定位信息,实验证明该算法不仅减小了定位误差,提高了定位精度,而且解决了TDOA 的模糊定位问题。
关键词:TDOA;信标节点;三角形加权质心定位;混合定位中图分类号:TP393文献标识码:A Abstract:A hybrid algorithm based on TDOA and triangle weighted centroid localization was proposed.This algorithm only usedthree beacon nodes,make full use of the data processing unit and node communication unit,We can get a location information through the triangle weighted centroid localization algorithm,and at the same time,an Unknown node make full use of accept signal related calculation,for time to get another location information.For both groups positioning information comparison,Calculate average and get a relatively stable location information,the experiment shows that this algorithm not only improve location accuracy,reducing the positioning error,and solve the problem of the fuzzy TDOA localization.Key words:TDOA;Beacon nodes;Triangle weighted centroid localization;Hybrid localization文章编号:1008-0570(2012)10-0395-021引言在无线传感器网络(WSN)中,没有位置信息的监测消息是毫无意义的,因而节点定位技术成为无线传感器网络中的一项关键支撑技术。
依据定位过程中是否需要测量实际节点间的距离,可将WSN 定位算法分为基于测距定位算法(Range-Based)和基于非测距定位算法(Range-Free)。
前者包括:到达时间法(TOA)、到达时间差法(TDOA)、到达角度法(AOA)、信号强度法(RSSI)等。
后者包括:质心算法、DV-HOP 算法、Amorphous 算法和APIT 算法等。
事实上,每种定位算法都有其适用范围和局限性,因而本文提出一种基于TDOA 与三角形加权质心定位的混合算法。
2TDOA 双曲线定位算法WSN 中传统的TDOA 测距技术是利用两种不同信号(一般是射频信号和超声波)到达同一节点所产生的时间差来确定节点间的距离,不仅增加了硬件成本和体积,而且应用规模受限,不符合本文要求,而移动通信系统中的TDOA 作为一种双曲线定位技术,可以很好的移植到WSN 当中,在不增加节点硬件成本的情况下完成节点定位功能。
2.1TDOA 定位算法原理如图1所示,假设A(x A ,y A )、B(x B ,y B )、C(x C ,y C )是三个信标节点,O(x,y)点是待定节点,T ij 表示信号从i 点到待定节点所用时间与信号从j 点到待定节点所用时间差,v 表示信号传播速度,d ij 表示待定节点到信标节点i 和j 点的距离差,解以下双曲线方程组即可得出未知节点的坐标,但此种方法存在模糊定位问题,可能存在双解两交点的情况,需要优化。
2.2TDOA 互相关方法数学模型TDOA 算法关键在于得到两个信标节点到待定节点的时间差T 。
直接计算TOA 需要节点达到严格同步,会大幅度增加节点的成本和能量消耗,实现起来困难,所以本文采用互相关技术求解时间差T,从而达到不增加节点硬件成本的效果。
如图1所示,当待定节点发起请求定位信号时,信标节点A 和B 发射的连续波信号为s(t),经传输后受到噪声干扰,待定节点O 接收到信号分别为x 1(t)、x 2(t):由(2)式化简可得(3)式:式中:T 是传输时延,T=d 1-d 2;A 为幅度比,A=A 1/A 2,则待定节点接收到信号的互相关函数为:根据自相关函数的性质,,可以用互相关函数达到极大值来估计时延差T 。
当取极大值时,τ就是我们需要测算的到达时间差T 的值,将T 代入公式,得解。
3基于RSSI 的定位算法3.1基于RSSI 的三角形质心定位算法傅涛:讲师硕士研究生395--技术创新在WSN中,只要知道了一个待定节点到三个信标节点的距离,就可以确定待定节点的二维空间位置。
依据无线电传播路径损耗模型,待定节点和信标节点间的距离分别为dA、dB、dC,三角形质心定位算法的基本原理就是计算三圆公共交叠区域的三个交点的坐标,以这三个交点作为三角形的顶点,该三角形的质心即为待定节点。
如图2所示,三角形顶点为D(xD,y D)、E(x E,y E)、F(x F,y F),D点坐标的计算方法如下所示,同理可得顶点E,F的坐标,利用传统的质心算法求得质心即为待定节点O的坐标:3.2基于RSSI的三角形加权质心定位算法分析无线电传播路径损耗模型可知,待定节点离信标节点越近,由RSSI的偏差产生的绝对距离误差越小,相反则越大。
三角形加权质心定位算法将RSSI信息纳入考虑范围,为每一个顶点坐标增加了权值,以体现不同顶点的贡献。
每个顶点由两个距离确定,如图2所示,顶点D(xD,y D)由以节点B、C为圆心,d B、d C为半径的两圆相交形成,故权值选择为,同理顶点E、F权值选择为、,对三角形质心定位算法进行修正,待定节点O的坐标为:4一种基于TDOA与三角形加权质心定位的混合算法4.1混合定位算法的提出新的混合定位算法充分利用节点的数据处理单元和通信单元,待定节点选取RSSI较大的三个值,确定三个信标节点。
利用三角形加权质心定位算法得到一个定位信息;同时待定节点充分利用接受信号进行相关运算,求时差得到另一个定位信息。
对两组定位信息取均值,得到相对稳定的定位信息,当TDOA出现模糊定位即双解两交点时,借助三角形加权质心算法结果,比较两个坐标间距,间距最小的即为TDOA的有效值,再求均值得到稳定定位信息。
4.2混合定位算法的实现待定节点比较RSSI值,选取RSSI值大的前三个作为信标节点A、B、C。
(1)依据无线电传播路径损耗模型换算出距离参数d A、d B、dC;依据公式(5)(6),通过三角形加权质心算法,待定节点坐标为O(x1,y1);(2)假设待定节点接收到三个信标节点信号分别为x1(t)、x2(t)、x3(t);依据公式(4)可得时差参数T12、T13;依据公式(1),通过TDOA双曲线定位算法,待定节点坐标为:单解一个交点,O(x2,y2);双解两个交点,O(x2,y2),O(x3,y3);(3)对两种结果比较,求均值,可得最终待定节点坐标O(x,y);单解:双解:4.3混合定位算法的仿真利用Matlab工具对混合定位算法进行仿真。
假设在一个80m×80m的二维平面区域内,随机分布30个待测节点,信标节点的坐标已知。
仿真结果如下所示:测距误差:,、分别表示待测节点与参考节点A的实际距离、估算距离。
如图3所示,三角形加权质心算法的测距误差相对较大而且不稳定,混合定位算法曲线相对平滑,测距误差较小,提高了定位信息的稳定性。
定位误差:,设节点通信距离为100m,(x,y)为节点测量坐标,(x i,y i)为节点原始坐标,如图4所示,混合定位算法定位误差较小。
5结论经过试验仿真,该算法在不增加节点的硬件成本,仅采用三个信标节点情况下,有效提高了定位相对稳定性,解决了TDOA的模糊定位问题,较三角形加权质心定位算法减小了定位误差,提高了定位精度。
下一步将继续对混合算法进行优化并希望应用于ZigBee模块当中。
本文无抄袭,作者全权负责版权事宜。
参考文献[1]Akyildiz W,Su Y,Sankarasubramaniam EC,A survey on sensornetworks.IEEE Communication Magazine,2002,40:102~106[2]李文锋.无线传感器网络与移动机器人控制[M].科学出版社,2009.1:54-73[3]Nicelescu D,Nath B.Ad hoc positioning(APS)using AOA.Proceedings of Joint Conference of IEEE Computer and Communi－cation Societies,New York,2003:1734-1743[4]He T,Huang C,Blum B M,et al.Range-free localization schemesin large scale sensor networks.Proceedings of the9th Annual In－ternational Conference on Mobile Computing and Networking,NewYork,2003:81-195[5]QinBin He,FangYue Chen,ShuiMing Cai,JunJun Hao,ZengRongLiu.An efficient range-free localization algorithm for wireless sen－sor networks.SCIENCE CHINA Technological Sciences??2011:?54(5):1053-1060?[6]Girod L,Estrin D.Robust range estimation using acoustic andmultimodal sensing.In:Proc of the IEEE/RSJ Int'1Conf.on Intel－ligent Robots and System(IROS01).Vol.3,Maui:IEEE Robotics andAutomation Society,2001.1312-1320[7]Pereira Pires,Rafael;Gracioli,Giovani;Wanner,Lucas;AugustoMedeiros Frohlich,Antonio.?Evaluation of an RSSI-based LocationAlgorithm for Wireless Sensor Networks.?Latin America Transac－tions,IEEE(Revista IEEE America Latina).2011:9(1):830-835(下转第480页)技术创新(c)中值滤波(d)均值滤波图2中值滤波及均值滤波对高斯噪声的滤波效果6结论本文结合传统的中值滤波和均值滤波算法,经过MATLAB语言设计程序,对嵌入了椒盐和高斯噪声的图像进行滤波处理。