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

改进的无线传感器网络TDOA定位算法 改进的无线传感器网络定位算法TDOA 张 健，李 鸥 ，ZHANG JianLI Ou 解放军信息工程大学 信息工程学院，郑州 450002 ，，，College of Information Engineeringthe PLA Information Engineering UniversZhengzhou ity 450200China :E-mailzj_cling@126.com ， ZHANG JianLI Ou.Improved TDOA positioningalgorithm for wireless sensor networks .Computer Engineering and ，，():Applications20104616117-120. postiioning ， : algorithmthis paper presents an improve d algorithm.With the AbstractAiming at the drawbacks of current TDOA ， ，time difference measuredthe at same sensotimer synchronizationof nodes is not necessary.By the rolling average metho dthe ， influence of multipath propagation and random noise is reduced.The improve d algorithm does not need additional hardwarewith ，small computational amount and hi gh position accuracand ypossesses better pract icability. :();;;Key wordsTime Differenceof Arriva TDOAanchor nodetargetsnode sposioninglti 摘要:针对 定位算法存在的不足，提出了一种改进算法。采用在同一节点上测量时差的方法消除了 定位算法中对 TDOA TDOA 节点时间同步的要求，利用滚动平均法削弱了多径传播和随机噪声的影。响改进算法无需额外的硬件支持，计算量小，定位精度高，具有较好的实用性。 关键词:到达时间差;参考节点;目标节点;定位 : 文章编号:() 文献标识码:中图分类号: DOI10.3778/j.issn.1020-8331.2010.16.4031002,8331201016-0117-04ATP393 引言 时差定位()的基本原理 1 2 TDOA 在传感器网络中，确定传感器节点自身位置和确定事件发 定义 将参与定位的已知位置信息的节点称为参考节点，生的位置是传感器网络基本的功能之一。事件发生的位置或获 将需要定位的未知位置节点称为目标节点。 中，目标节点向 个或 个以上的参考节点发送信 取事件节点的位置是监测消息中最重要的内容。如森林火灾发 TDOA 3 3 号，从第一个接收到信号的参考节点处开始计时，分别记录下 生的位置、战场上敌方车辆运动的区域、天然气管道泄漏的具 信号到达其余各个参考节点的时刻，这些时刻便是第一个接收 体地点等。而确定节点自身位置是确定事件发生位置的前提， 到信号的参考节点与其余参考节点信号到达的时间差，根据这 只有在传感器节点自身正确定位之后，才能确定事件发生的具 体位置。定位信息除用来 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 事件发生的地点外，还具有目标 些时间差可以列出双曲线方程组，计算出目标节点位置，因此，跟踪、协助路由、网络管理等用途。 这种定位算法也被称为双曲线定位，如图 。1无线信道环境的复杂性和传感器节点自身的特点，给传感 器网络定位算法的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 带来了挑战一种好的无线传感器网络 。 定位算法要具备以下几个条件:首先，算法必须具有较好的鲁 tR 1 1tR 3 3 棒性，能有效地进行定位;其次，由于传感器节点上的资源有 tT 0 限，算法的开销必须尽量小;再次，算法不应该增加节点的成本 和复杂度;最后，算法要是分布式的，在不同规模的传感器网络 Rt 2 2中能有效定位。 [1-2]针对 定位算法存在的缺点，提出了一种改进的无 TDOA 到达时间差定位图 1 线传感器网络 定位算法首先介绍时差定位的基本原理。TDOA 定位测距误差小，具有较高的定位精度，但参考节 TDOA 并指出其缺点;其次提出改进算法，分析定位过程中产生误差点之间需要时间同步，这对硬件和功耗提出了要求，双曲线方 的原因;再次仿真对比了算法的性能，并分析了参考节点布放 程组求解不方便，而且时差定位机制易受多径传播和噪声的干 位置对定位误差的影响;最后 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf ，改进算法要明显优于现 扰。针对上述问题，下面提出一种改进的 定位算法。有算法 TDOA 。 基金项目:国家发改委 项目()。 CNGI No.CNGI04-101D-- 作者简介:张健()，男，硕士生，主要研究方向:无线传感器网络定位算法;李鸥()，教授，博士生导师，主要研究方向:计算机网络与通信。1982-1961- 收稿日期: 修回日期: 2008-11-212009-02-09 [4]采用滚动平均的方法，每个周期不断地更新 ()和 ()的估 kiki改进的 定位算法 3 TDOA 1 2 计值: 网络模型3.1 [3]网络模型如图 軈，目标节点随机布放在一个二维的监控 2()() ?m+km+1mk 11 軈 ()k() m+1= 71 区域内，每个节点上都具有全向天线，所有的节点都是静止的 。m+1 个参考节点 、、的坐标分别为(，)、(，)、(，)，它3 ABC xy x y x y a b b c c a 軈()() ?m+km+1mk 22 軈 ()k() m+1= 8们不在同一条直线上，目标节点的坐标为(，)。监控区域被参 xy2 m+1 考节点 、、组成的三角形覆盖，如果监控区域很大，可以布 ABC ，，，… m=123放更多的参考节点将监控区域分割成多个小的监控区域。 在 M(M2)个周期后? A 軈()()() ?M-1kM-1+kM 1 1 軈 (k) () k=M=9 1 1M 监控区域 軈()?()() M1kM1+kM-- 2 2 目标节点軈() k =kM=() 102 2 M 参考节点 即得: () d=k+d 11C sb 1 saB ()12 d=k+d 定位场景图 2sc 2 sa 得到下面方程组: 节点都在彼此的通信范围内，所有节点之间不需要时间同2 2 2 步，目标节点周期性地发起定位过程。 ) () () (+y-y =d13x-x a sa a 2 2 2 ()定位过程14 3.2 () () ()xx +yy =d +k --b b sa 1 如图 所示，节点 、、为参考节点，节点 为目标节 3 ABC S 2 2 2()15 () () ()x-x +y-y =d +k c c sa 2 点。为主参考节点，、为辅参考节点，当 收到来自 的定 A BC A S 下面讨论式()、()、()组成的方程组的解，为了讨论 131415位信息后，将给 回复时间信息，而 、则不发送回复信息。 S BC 方便假设参考节点 、、的坐标分别为(，)、(，)、(，)，ABC 00x0xy 2 1 2 发射信号的传播速度已知为 ，和 分别代表 与 、、vdddS A sa sb sc 其中，，上面方程组转化为: 。x >0y >0之间的距离、。BC 1 2 2 2 2A () x +y =d16 sa2 2 2 ()17 () () x-x+y =d +k sa 1 12 2 2 ()18 () () () xx+yy =d +k -- 2 sa 2 2S 方程组的解为: 2 2C B -2k d -k +x 1 sa 1 1 图 定位过程 3 x= () 192x 1 22 2 2 2 目标节点 周期性地发送信号，假定周期为 ，每个周期 S T()()2k x -2k x d k x -k x +x x +y x -x x 1 2 2 1 sa 1 2 2 1 2 1 2 1 1 2 i i i() y= + 20开始时，发送信号。第 个周期，、、分别在时刻 、、收S i ABC ttt2xy2xy a b c 1 21 2iT iT i 将方程()()带入方程()，得到: 、192016到信号，时刻 ()主参考节点 向 发送回复，同时传递 tt >t A S a a a 2i iT i i i i () ad+bd+c=021 sa sa 信息:?t=t-t，回复信号分别在t 、t、t到达 B、C、S;根据三 a a a 1 2 3 其中，i i i i 角不等式，三角形的两边之和大于第三边得:，。假设: t >t t >t 2 2 2 2 2 1 b 2 c () () a=4[ky+kxkxx y ]22-- 1 2 1 2 1 2 2 1i i i i i i i ?t=t-t，?t=t-t，?t为 A 发出的回复信号与 S 发出的信号 2 2 2 1 1 b 2 2 c 1 )? ( )(b=4kkxy+4kxkx-- 1 1 1 2 1 2 2 1i 到达 B 的时间差，?t为 A 发出的回复信号与 S 发出的信号到22 2 2 2 2 ()() k x k x +x x +y x x x --231 2 2 1 2 1 2 1 1 2 达 C 的时间差由上述过程可以得到:。2 2 2 2 2 2 2 2 2 ()24 i i ()() c=k-xy +k x -k x +x x +y x -x x 2 1 2 2 1 2 1 2 1 1 2 1 1??() d+v?t+dd=v?t1- sa a ab sb 1方程()有正根的条件为: 21i i ()2 ??d+v?t+d-d=v?t sa a ac sc 2 c ()、且 ，有正根 ;1a=0b<0 c>0d=- sa 方程转化为:b 2 i i b b )() d=d+d+v(?t?t3-? sb sa ab a 1()且 ，有正根 ; 、2a>0b<0 c= d =- sa 4a 2a i i ()4 )d=d+d+v(?t?t-? sc sa ac a 22 -b- b -4ac 姨 假设:;()，有正根 3ac<0d= sa 2a i i () ()i=d +v(?t -?t )?k5 2 2 1ab a 1 -b- b -4acb 姨 i i ()且 ，有正根 、、、4a>0b<0c>0 c> d= ()sa 6 k()i=d +v(?t ?t )-? 4a 2a 2ac a 2 2 2.5 b -4ac -b+ TDOA 姨 ，这时产生模糊解。d = sa M=4 2a 2.0 M=8 M=16 当上述 3 个条件(1)、(2)、(3)其中有一个满足时，方程有M=32 1.5 M=64 唯一正根，将得到的 的值带入式()、()便得到节点 的d1920S sa 坐标，当得到模糊解时，可以分别得到节点坐标，由于待定位节 1.0 定位误差点位于监控区域内，剔除定位结果在监控区域外的结果 。 0.5 误差原因分析 3.3 从上面的定位过程可以看出，在第 i 个周期，改进算法需 0 0.1 0.2 0.3 0.4 0.5 i i i 要测量的值有 ?t?t和 ?t对它们的测量存在着误差，误差、。 方差a 1 2 图 性能比较4的产生主要有以下 个原因:节点接收系统时延无线多径衰 、3 落信道、非视距传播。 2 越大;对于改进算法，相同的方差 ，值越大测量误差越小 。σ M 节点接收系统时延指的是从信号到达节点接收天线到信 分析:改进算法的测量时间差值是同一参考节点上信号到 号被接收系统精确解调所用的时间，这个时间通常是定值或者 达的时间差，是相对同一参考节点测量得到的，因此节点之间 在一个很小的范围内变化。系统时延可以预先确定并用来校正不需要时间同步;采用滚动平均的方法降低了随机噪声的影 测量值。因此，主参考节点 在向目标节点 发送回复并传递A S 2 i 响，因此性能要优于 定位算法当 越大，相应得到的 。TDOA σ ?t之前可以通过校正来消除系统时延的对它的影响同样可。 a 目标节点的坐标 、的误差也越大，导致测量误差越大;对于 xy i i 以通过校正来消除接收系统时延对测量值 ?t和 ?t的影响。 1 2 改进算法，当 值越大时，测量误差对定位的影响越小，定位 M 无线多径衰落信道在很大程度上影响定位的准确性。多径 结果越准确，从而测量误差越小。在实际应用中，值的选择与M 信号有两个重要特点:第一，由于两点之间直线最短，沿着非直 系统要求的定位精度和随机噪声有关。接路径传播的信号比沿着直接路径传播的信号要晚到达节点 定位误差分布4.2 接收天线。第二，在视距传播模型中，通常传播的路径越长信号 图 是定位误差的分布图。参考节点 、、的坐标为5 ABC 的衰减越大，沿着非直接路径传播的信号比沿着直接路径传播 (，)(，)(，)，目标节点取坐标为(，)，，、、，，…， 00300030ijij =12的信号强度要弱。 上的点。对每个目标节点进行 次的定位实验，每次实 29 5 000 非视距传播是另外一个导致无线信道环境下定位误差的 验目标节点发起定位的周期数 ，测量误差服从高斯分布M=16因素。为了减轻非视距传播的影响，可以将节点架高以实现节 (，)。N00.5点之间的视距通信。 从上面的分析中可以得到，节点接收系统时延引起的测量 1.5 误差可以通过校正来消除，因此，导致测量误差的主要原因是 多径衰落信道和非视距传播，此外还有各种环境因素的影响， 1.0 将这些都称为随机噪声。 Z/m 0.5 仿真4 0 30 从定位过程可以看出，目标节点 的坐标(，)的计算需xyS 30 20 要 和 ，而 和 的值由定位过程中目标节点 发送的总 k k k k S 20 1 2 1 2 Y/m 10 10 X/m i i0 0 周期数 M 以及每个周期中测量得到的时间值决定，即 t? 、?t a 1 误差分布图图 5i i i 和 ?t。因此，目标节点 S 的定位误差来源于时间值 ?t、?t和 2 a 1 从仿真结果可以看出，当目标节点与 个参考节点之间的 3 i ?t的测量误差从上面的误差分析得到节点接收系统的时延。 2 距离都变大时，定位误差变大。当目标节点与 个参考节点中 3 对测量误差的影响可以通过校正来消除，因此，在下面的仿真的任何一个距离过近时，定位误差也将变大。因此，定位误差的 i i 大小和参考节点的布放位置有关。中，仅考虑 ?t和 ?t的测量误差测量误差的分布服从均值为。 1 2 2 参考节点分布对定位性能的影响4.3 [5]，方差为 的正态分布。 0σ 上面的仿真说明，定位误差和参考节点的布放位置有关 性能比较4.1 系。下面讨论参考节点位置对定位误差的影响，分别取主参 考将改进后算法和 定位算法进行性能对比，假定 TDOA 节点为顶点的三角形两条边的夹角为: 、、、、定位算法中参考节点之间是时间同步的，算法的测量误 30? 60? 90? 120? TDOA 差都服从正态分布，比较算法的定位性能。为了不失一般性，在 ，主参考节点与辅参考节点之间的距离为 米，监控区域 150?30 监控区域内，随机选择 个目标节点，将定位结果的误差5 000 内节点的误差分布情况如图 图 。从图中可以看出:6~10 ()测量误差的分布大概是以参考节点组成的三角形内的 12 进行平均。方差 的取值范围为 ，对于改进算法 分别 σ 0~0.5M 某一点为圆心的同心圆，离该点越近，测量误差越小，该点应该 取 、、、、，如图 。481632644是三角形角的平分线的交点，即三角形的内心。文献中也有 [6] 从图 4 中可以看出，在不考虑同步的情况下，改进算法的相似的结果; 2 性能要明显优于现有的时差定位算法;方差 越大测量误差 σ (2)当两边夹角为 60?，即参考节点组成等边三角形时，定 30 30 25 25 0.206 0.222 0.23820 20 25 0.254 0.201 20 15 15 0.235 0.250.213 0.22 15 0.225 10 10 0.205 0.236 10 5 5 5 0 0 0-8 -6 -4 -24 6 8 0 2 15 10 5 0 25 20 15 10 5 --------5 10 15 0 5 10 15 20 25 X/m X/m X/m 图 夹角 图 夹角 图 夹角 630?760?890?16 14 8 0.2760.2330.274 0.31 0.35 0.254 12 0.235 6 10 0.213 8 Y/m Y/m 4 6 4 2 2 0 0-20 10 20 30 -30 -20 -10 10 20 30 30 10 0 0 -- X/m X/m 图 图 9 夹角 120?夹角 150?10 (): 位误差的分布情况最佳文献中给出了证明，说明当参考 451-56.。[7-8]彭刚，曹元大，孙利明无线传感器网络节点定位机制的研究计 [2] .[J].节点组成等边三角形时，定位误差最小，并给出了参考节点布 算机工程与应用，，():2004403527-29. 放的方法，因此，当网络规模较大时，可以根据文献中给定[7-8] ，，，[3] Chen Hong-yangDeng Pin gXu Yong-junet al.A robust location 的布放参考节点的方法，对网络进行分割。algorithm with biased extended Kalman filterin g of TDOA data for Y/m wireless sensor networks[C]//InternationaIEEE l Conference onWire , ，，结论5 less CommunicationNetworking sand Mobile ComputingWCNM ，，，，:提出了一种改进的 定位算法。该算法有以下特点:2005WuhanChinaSeptember 23 -262005883-886. TDOA 王永才，赵千川，郑大钟传感器网络自身定位方法的设计与实现[4] .[J].()无需时间同步:定位过程中相对同一参考节点测量时 1计算机工程与应用，，():200541134-6. 间差消除了节点间时间同步的要求。 ，[5] Li Cong Zhuang Wei hua . Non line of sight error mitigation in ----()定位算法准确:目标节点周期性地发起定位过程，采用 2TDOA mobile location[C]//IEEE Global Telecommunications Confe, r滚动平均的方法，利用历史信息消除随机误差的影响。 ，，，:enceSan Antonio TX USANov 200 11680-684. ()无需额外的硬件设备，有效地满足了传感器节点成本 3Y/m [6] Nasipuri A，Li Kai.A directionality based location discovery scheme和体积的要求。 for wireless sensor networks[C]//Proceedings of the 1st ACM Inter, 仿真对比了算法性能，改进算法要明显优于 定位算 TDOA 法;分析了参考节点布放位置对定位误差的影响，当 个参考3 Y/m ， national Workshop on Wireless Sensor Networks and Application s 节点组成等边三角形时，定位效果最好。改进算法计算简单，具，，，，: AtlantaGeorgiaUSASeptembe2002r105-111.有较好的实用性。 关沫，赵海，韩光洁，等普适计算中定位服务的参考点选择及误差 [7] . 分析电子学报，，():[J].20053381425-1431. 孙佩刚，赵海，韩光洁，等混沌三角形定位参考点选择算法计算 参考文献:[8] .[J]. 周正无线传感器网络的节点自定位技术中兴通讯技术，，[1] .[J].200511 机研究与发展，，():200744121987-1995. ， rithms[C]//IEEE WCN C2004.(上接 页) 113 ，[6] McNair JFang Zhu.Vertica l handoffs in fourth -generation multi - ，，[2] Choi Hyun-HoSong OsokCho Don-gHo.A seamless handoff scheme ，，network environments[J] .IEEE Wireless Communications 200411 Communications Society for UMTS - WLAN interworking [ J ] . IEEE (): 38-15.，:Globecom20041559-1564. ， [7] Zhu FangMcNair J.Multiservice vertical handoff decision algo,， FangMcNair J.Cross layer design for mobile IP handoff [C]//[3] Zhu rithms[J].EURASIP Journa l on Wireless Communications and Net , ，，:IEEE Vehicular TechnologyConferenc e200542255-2259. ，working2006.，，[4] WangH JKatz R HGiese J.Policy-enabled handoffs across heter, o，，[8] Stevens -Navarro E Wong V W SLin Yu -xia.A vertical handoff geneous wireless network s [C]//Second IEEE Workshop on Mobile decision algorithm for heterogeneous wireless networks.Department ，:Computing Systemsand Applications199951-60. ，of Electrical and Computer EngineerinThe gUniversity of British ，[5] Zhu FMcNair J.Optimizations for vertical handover decision ,algo，，ColumbiaVancouveCanada.r