2022年无线传感器网络节点定位技术.docx

《2022年无线传感器网络节点定位技术.docx》由会员分享，可在线阅读，更多相关《2022年无线传感器网络节点定位技术.docx（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用无线传感器网络节点定位技术定位即确定方位、确定某一事物在肯定环境中的位置；在无线传感器网络 中的定位具有两层意义：其一是确定自己在系统中的位置；其二是系统确定其 目标在系统中的位置；在传感器网络的实际应用中,传感器节点的位置信息已 经成为整个网络中必不行少的信息之一,很多应用场合一旦失去了节点的位置 信息,整个网络就会变得毫无用处,因此传感器网络节点定位技术已经成了众 多科学家讨论的重要课题；2.1 基本概念描述在传感器网络中,为了实现定位的需要,随机播撒的节点主要有两种：信 标节点 Beacon Node）和未知节点

2、 Unknown Node）；通常将已知自身位置的节点称为信标节点,信标节点可以通过携带GPS 定位设备 或北斗卫星导航系统 BeiDouCOMPASS）Navigation Satellite System 、或预置其位置）等手段 获得自身的精确位置,而其它节点称之为未知节点,在无线传感器网络中信标 节点只占很少的比例；未知节点以信标节点作为参考点,通过信标节点的位置信息来确定自身位置；传感器网路的节点构成如图2-1 所示；b5E2RGbCAP UUUUBUUUUUBUUUUUUBUUUBUUU图 2-1 无线传感器网络中信标节点和未知节点Figure 2-1Beaconnodes and

3、unknown nodes of wireless sensor networkp1EanqFDPw 在图 2-1 中,整个传感器网络由4 个信标节点和数量众多的未知节点组成；信标节点用 B 来表示,它在整个网络中占较少的比例；未知节点用 U 来表示,1 / 13 名师归纳总结 - - - - - - -第 1 页,共 13 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用未知节点通过四周的信标节点或已实现自身定位的未知节点通过肯定的算法来 实现自身定位；DXDiTa9E3d 下面是无线传感器网络中一些常用术语：1邻居节点 Neighbor Nodes）：无需经过

4、其它节点能够直接与之进 行通信的节点；2跳数Hop Count）：两个要实现通信的节点之间信息转发所需要的最小跳段总数；3连通度Connectivity）：一个节点拥有的邻居节点数目；4跳段距离 ：信号传 输过程中,同时发出的两种不同频率的信号到达同一目的地时由于不同 的传输速度所造成的时间差；RTCrpUDGiT 6接收信号传播时间 Time of Arrival , TOA）：信号在两个不同节 点之间传播所需要的时间；7 信号返回时间 ：节点自身轴线相对于其接收 到的信号之间的角度；9 接收信号强度指示 Received Signa1 Strength Indicator,RSSI：无 线

5、信号到达传感器节点后的强弱值；jLBHrnAILg 2.2 节点定位技术性能评判标准在无线传感器网络定位技术中,不同的定位算法对定位结果有不同的影响,通常情形下有以下几个指标来衡量：（1）定位精度 Positional Accuracy）：定位精度是指空间实体 位置信息 通常为坐标）与其真实位置之间的接近程度,它是衡量传 感器网络定位的首要指标,只有达到肯定定位精度的定位算法才是真实有效的；定位精度分为肯定精度和相对精度,肯定精度是指误2 / 13 名师归纳总结 - - - - - - -第 2 页,共 13 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用差的肯

6、定值,以长度为单位表示；相对精度是指误差值与节点之间距离的百分比； xHAQX74J0X （2）有效定位范畴 Effective Rang of Orientation ）：定位系统所能定位的有效范畴；在WSN中要满意大多数节点能够被定位,只有掩盖大范畴的节点定位才有意义；LDAYtRyKfE （3）节点密度 ：信标节点密度是指信标节点在整个 WSN 中所占的比例；信标节点具有自身定位功能,价格较贵,不行能大面积播撒,它节点的密度打算了定位的精度的 高低；dvzfvkwMI1 （5）容错性和自适应性 Fault Tolerance and Adaptivity ）：所谓 容错性是指在故障存在的

7、情形下系统不会失效,仍旧能够正常工作的特性；容错即是Fault Tolerance,准确地说是容故障Fault）,而并非容错误 Error）；自适应性可以看作是一个能依据环境变化能够 智能调剂自身特性的反馈掌握系统,以使系统能依据一些设定的标 准工作在最优状态；rqyn14ZNXI （6）安全性 Security）： Security指的是指系统对合法用 户的响应及对非法恳求的抗拒,以爱护自己不受外部影响和攻击的才能；WSN通常工作在物理环境较为复杂的区域,定位系统易受到环境或人为的破坏和攻击,从而无法达到在理 想的无线通信环境所能达到的定位成效,因此定位系统和算法必需具有很强的 安全性；Em

8、xvxOtOco （7）功耗Power Dissipation）：功耗是指功率的损耗,在WSN设计过程中功耗始终是困扰其应用的一个主要方面；由于传感器节3 / 13 名师归纳总结 - - - - - - -第 3 页,共 13 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用点的能量受限并且不简洁得到补充,因此需要整个 WSN能够以较小 的能耗和高效的能量利用率来实现安全定位是当前讨论的所面临首 要的问题 23； SixE2yXPq5 （8）代价与成本 定位算法和距离无关的Range-Free定位算法；假如定位算法需要知道未知节点到参考节点或信标节点之间的肯定 距

9、离时,然后才能运算出未知节点坐标信息,这样的定位方法就可以称为 Range-Based的定位算法；反之,其它的算法无需测量节点之间的距离值就称之 为 Range-Free的定位算法； Range-Based定位算法精度上优于 Range-Free的定 位算法,但需要测量距离,运算量比较大,需要消耗大量能量,并不适用于低功耗、低成本等应用领域；Range-Free的定位算法实现起来比较简洁,运算量也较小,但并不能实现高精度的定位,是一种粗精度的算法；y6v3ALoS89 2.3.1 基于测距的定位算法基于测距的定位算法实现起来比较复杂,第一需要通过 TOA 、 TDOA 、AOA 、RSSI 等

10、常用的测距技术来测量各个未知节点到信标节点的肯定距离值,这个阶段也称为测距阶段；测距终止后就要进行定位运算坐标）阶段,即利用测距阶段所得的节点间的距离或方位等参数来运算出未知节点的位置,在此期 间 常 用 的 算 法 有 ： 三 边 测 量 定 位 法 Trilateration ） 、 多 边 定 位 法Multilateration ）、三角测量法Triangulation ）、极大似然估量法Maximum Likelihood Method）和角度定位法 Goniometry）等；下面分别针对这两个阶段4 / 13 名师归纳总结 - - - - - - -第 4 页,共 13 页精选学习

11、资料 - - - - - - - - - 个人资料整理 仅限学习使用进行分析：M2ub6vSTnP 一）测距阶段算法分析：TOA 是依据信号的传播时间运算被测节点之间的距离；TOA 算法虽然定位精度较高,但是该算法要求节点之间精确同步,使用复杂,对硬件要求太高,因此不太适合于无线传感器网络定位的应用；TDOA 是在 TOA 的基础上所形成的算法；在该算法中,发射节点采纳两种不同频率的无线信号同时发送一组信 息到指定的相同区域,由于这两种信号的传输速度不同,因此到达目的地的时 间也会有所差别；接收节点依据这个时间差以及两种信号的传输速度就可以计 算出接收节点和发射节点之间的距离值；0YujCfm

12、UCw AOA 是通过 Triangulation 来进行定位运算；在AOA 算法中,未知节点首先要运算出相对于参考节点的方位角,这就使得该算法在复杂电磁环境中的定 位性能很差,不能够满意现实生活中较多电磁干扰的环境中使用；eUts8ZQVRd RSSI 是利用信道衰减模型,依据所接收到的信号的强弱来实现节点的定位 功能；在实践应用中,信号在传输过程中必定会遇到干扰、反射、吸取等的影 响,这就极大的降低了定位精度 24-25； sQsAEJkW5T PDOA 是通过测量接收信号相位差,求出信号传播的来回时间,然后运算 信号来回的距离；NFER 是通过近场电场和磁场的相位差来测量距离的；表 2-

13、1 对以上六种基于测距定位算法进行了比较；表 2-1 基于测距定位算法比较Name TOA TDOA AOA RSSI Table 2-1 Comparison of distance-based location algorithmGMsIasNXkA Extrahardware Effective Interference Distance- distance rejection measuring error Y short weaker smaller Y shortest weak smallest Y shortest weak smallest N long strong big

14、 5 / 13 名师归纳总结 - - - - - - -第 5 页,共 13 页精选学习资料 - - - - - - - - - PDOA Y long 个人资料整理仅限学习使用strong big NFER N short weak small 二）定位阶段算法分析：Trilateration 26 是通过三个已知坐标的信标节点以及这三个信标节点到未知节点的距离信息,依据二维空间距离公式建立方程组,采纳线性化方法来求解出未知节点的位置信息；假设已知三个信标节点A、B、C 的坐标分别为x 1,y 1、x 2,y 2、x 3,y 3它们到未知节点D 的距离分别为：1d、d 、d ,未知节点D的坐

15、标设为 , x y ；可以得到以下方程：TIrRGchYzg d12xx12yy12d22xx22yy22d32xx32yy322-1）依据上式可得未知节点D 的坐标方程为：x2x 1x 32y 1y312 x 12 x 32 y 12 y 3d2d231y2x2x 32y2y 32 x 12 x 32 y 12 y 3d22 d 12-2）3Multilateration 是已知三个以上信标节点的坐标信息以及信标节点到这个未 知节点的距离信息,利用两点间的距离公式可运算出未知节点到信标节点之间的距离,最终利用最小二乘法LS,Least Square）、极大似然估量MLE ,Maximum L

16、ikelihood Estimation ）或最小均方误差 MMSE , Minimum Mean Square Error）等求出未知节点的坐标信息；7EqZcWLZNX Triangulation 是通过未知节点的接收器天线阵列来测量出周边信标节点所发出信号的入射角信息,利用所得到的角度信息和信标节点的坐标信息,依据Trilateration 算出未知节点的坐标；lzq7IGf02E Maximum Likelihood Method27原理如图 2-2 所示；6 / 13 名师归纳总结 - - - - - - -第 6 页,共 13 页精选学习资料 - - - - - - - - - 1

17、个人资料整理仅限学习使用2n D34图 2-2 最大似然估量法Figure 2-2 Maximum Likelihood Method 在该算法中已知1,2,3, n 等 n 个信标节点的坐 标为：x y 1、x 2,y 2、x 3,y 3,x n,y n；它们到未知节点D 的距离分别为：d 、d 、d d ,假设未知节点 D 的坐标为x,y；那么存在如下公式：zvpgeqJ1hk x 1x2y 1y 2d 1x nx 2y ny2d 2-3）从第一个方程开头分别减去最终一个方程可得：x 1 22x2n22x 1nxnxy 12yy2 n2y 12y nyyd12d2 n2dn22-4 ） 式

18、nxnx2x1x nx2y2 nyn1nydn1n112-4）可表示为：AXb ,其中： A 、 X 、 b 如下面 2-5）到 2-7）所示：2x 1x n2y 1y nAx 1 2x n 22x n1x n2y n1y n2-5）y 12y n 2d n 2d 12bx n12x n2y n 21y n 2d2d n22-6）n17 / 13 名师归纳总结 - - - - - - -第 7 页,共 13 页精选学习资料 - - - - - - - - - 个人资料整理X仅限学习使用xy2-7）利用最大似然估量法或最小二乘法可得D 的坐标为： XT A A 1T A b 2-8）2.3.2

19、基于无需测距的定位算法 基于测距的定位算法虽然能够实现精确定位,但往往也对硬件要求较高,导致硬件成本增加,不利于大面积、多领域、广角度的使用；无需测距的定位 算法使用起来比较简洁,只需要利用未知节点到参考节点之间的估量距离值或 其它位置信息,然后用三边测量法或极大似然估量法来运算出未知节点的坐标 信息；无需测距定位算法由于不需要精确测量节点间的距离信息,极大地降低 了对节点硬件的要求,另外它是利用节点间的距离估量值来进行运算,因此受 环境的影响较小,在很多对节点定位精度要求不高的应用场合能够大量使用；现 有 的 基 于 无 需 测 距 的 定 位 算 法 主 要 有 ：DV-HOP算 法 、

20、质 心 算 法 、Amorphous 算法、 APIT 算法、凸规划算法和 这几种方法：NrpoJac3v1 MDS-MAP 算法等；下面分别介绍（1）质心定位算法 Centroid）质量中心简称质心 假想点；Centroid）,指物质系统上被认为质量集中于此的一个在传感器网络中,质心是指多边形的几何中心 28,多边形各个顶点坐标的几何平均值即为质心坐标；质心定位算法是University of Southern California 的NirupamaBulusu 等提出的,该算法适用于室外节点密度较高情形下的定位,它 是基于网络的连通性Connectedness）实现对节点的定位；其基本思

21、想是：未知节点依据自身设定的门限值来接收四周信标节点所发出的包含节点位置和 ID 的信息来确定其所在的区域,依据其接收到的信标节点的ID 及位置信息运算所在区域的质心,并把这个区域的质心作为自身的定位结果；该算法简洁易行,对 硬件要求较低,不需要额外任何硬件设备,但在定位过程中需要较多的信标节 点,另外该算法在定位过程中都假设节点拥有抱负的无线信号传输模型,这与实际的情形仍有很大的差别,因此影响了Centroid 的定位精度；1nowfTG4KI 8 / 13 名师归纳总结 - - - - - - -第 8 页,共 13 页精选学习资料 - - - - - - - - - 质心定位算法的基本原

22、理如图2-3 所示；个人资料整理仅限学习使用A 1A 6A 2x,y A 3 A 5 A 4图 2-3 质心算法示意图 Figure 2-3 Diagram of Centroid Principle x 2,该算法中,多边形区域A 、A 、A A 的六个顶点坐标分别为：x 1,y 1、y 2、x 3,y 3、x 4,y 4、x 5,y 5、x 6,y 6,就区域的质心为：y 62-9） , x 1x 2x 36x 4x 5x 6,y 1y 2y 36y 4y 5（2）不定型定位算法 Amorphous）Amorphous 29是基于连通性的定位算法,它需要预先知道网络的连通度；算 法实现过程

23、中,第一未知节点运算与每个信标节点之间的最小跳数；然后运算 未知节点到每个信标节点的跳段距离,其中假设网络中节点的通信半径相同；最终再利用 Trilateration 或 MLE 等算法来进行定位运算；Amorphous 实现起来比较简洁,但定位精度不是很高,另外仍有两个显著的缺点：一是需要预先知 道网络的连通度；二是定位过程中需要较高的节点密度；fjnFLDa5Zo （3）近似三角形内点测试法 APIT ）APITApproximate Point-in-Triangulation Test）算法能够以较高的定位精度适应于复杂的地理环境；APIT 定位算法在实现过程中未知节点第一通过收集邻居

24、节点的节点标识符、位置信息、发射信号功率的大小等信息来确定该节 点是否位于不同的信标节点所组成的三角形内,然后统计包含未知节点的三角 形区域,并把这些三角形区域的交集构成一个多边形,这个多边形基本上确定 了未知节点所在的区域并缩小了未知节点所在的范畴,最终运算这个多边形区域的质心,并将质心作为未知节点的位置,这样就实现了未知节点的定位；tfnNhnE6e5 9 / 13 名师归纳总结 - - - - - - -第 9 页,共 13 页精选学习资料 - - - - - - - - - APIT 定位算法基本原理如图2-4 所示；个人资料整理仅限学习使用A 2A 3SA 4A 5A 1A nA 6

25、图 2-4 APIT 算法示意图 Figure 2-4 Diagram of APITPrinciple在图 2-4 中未知节点从它所能接收到信号的信标节点1A、A 、A A 中随机挑选三个,并测试自身是否在这三个信标节点所组成的三角形中,测试完 成后再随机选取另外三个信标节点连续测试,直到测试完全部的组合为止；在图 2-4 中,未知节点分别选取A A A 、A A A 、A A A A A A 并测试自身是否位于这三个信标节点所组成的三角形中,判定完成后也就确定了这些 三角形的交叉区域 是一种集中式的定位算法,所谓的集中式的定位算法是相对于分布式定位算法而言的,集中式定位算法采纳集中的思想,

26、收集到全部的传感器节点的有效信息后统一进行定位运算,集中式定位算法的可扩展性不好,信号传输和处理比较麻烦,不能够敏捷使用；凸规划定位算法的基本原理如图2-5 所示：未知节点第一依据其通信半径和与之能进行通信的信标节点建立其可能存在的位置区域,当穷举完这些区域之后依据肯定 的标准对这些区域进行挑选和位置划分,最终确定一个矩形区域 如图中阴影区10 / 13 名师归纳总结 - - - - - - -第 10 页,共 13 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用域外的矩形区域）,运算出该矩形区域的质心并把它作为未知节点的坐标,以 此来实现节点定位；V7l4jR

27、B8Hs 图 2-5 凸规划算法示意图Figure 2-5 Diagram of Convex Optimization Principle 83lcPA59W9 （5）MDS-MAP 定位算法 MDS-MAP 定位算法是 University of Missouri-Columbia 的 Yi Shang等提出 来的；该算法属于集中式定位算法,它是利用节点间的连通信息通过 Dijkstra 或 Floyd 算法生成节点间距矩阵,然后利用多维尺度分析技术来获得节点间的 位置信息；mZkklkzaaP MDS-MAP 定位算法的实现主要分为以下三个步骤：1）第一从全局角度动身生依据给出的节点间的

28、连通信息,如具备测距能 力的邻居节点间的测量距离和不具备测量才能的节点间所给予的距离值,生成网络拓扑连通图,然后通过最短路径法Shortest Path Algorithm ）粗略地估量每对节点间的距离,生成节点间距矩阵；AVktR43bpw 2）将经典多维尺度分析技术应用于节点间距矩阵,从而运算出整个网络的 2 维或 3 维相对坐标系统,该坐标为相对坐标；ORjBnOwcEd 3）依据信标节点的位置及信标节点的密度对 进行转换,使之成为肯定坐标系统；2）中所得的节点相对坐标MDS-MAP 定位算法基于多维尺度分析技术来进行节点定位,该算法对网 络节点密度要求严格,在节点分布匀称的情形下,较少

29、的信标节点就可以获得很好的定位结果；2MiJTy0dTT MDS-MAP 算法中假设每一对节点之间都是连通的,当节点密度较小时,不仅节点的定位误差会特别大,两外仍会导致很多节点无法进行定位；只有网络的连通度达到肯定的程度时,全部的未知节点才能够实现定位；采纳该算法获得11 / 13 名师归纳总结 - - - - - - -第 11 页,共 13 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用的节点坐标一般为相对位置坐标,将其转化为肯定坐标需要进行矩阵运算,在二维空间中将未知节点的相对坐标转换为肯定坐标一般至少需要 3 个信标节点进行帮助运算,在三维空间中至少需要

30、 耗一般都比较大；gIiSpiue7A 4 个信标节点,因此该算法运算量和能表 2-2 对以上六种无需测距定位算法进行了比较；表 2-2 无需测距定位算法比较 Table2-2 Comparison of range-free algorithm 名称类别网络信标节是 否 需信 标 节定位DV-HOP 分布式节 点 密点密度要 额 外点 定 位精度影 响 较影响较大否好良好Centroid 分布式大影响较大否好一般影 响 较分布式大影响较大是一般一般Amorphous 影 响 较分布式小影响较小否好一般APIT 影 响 最集中式大影响较小否好较好凸规划影 响 较小MDS-MAP 集中式影 响

31、较影响较大是一般良好大2.4 本章小结本章第一介绍了无线传感器网络的基本概念、定位的基本概念、无线传感 器网络中一些常用术语、节点定位技术的性能评判标准、定位算法分类及节点 定位运算方法；接着重点分析了基于测距的定位算法和无需测距的定位算法,具体介绍了各种算法的定位过程、并介绍了各种算法的性能及适用范畴,然后 通过表格等形式分别对基于测距的定位算法和无需测距的定位算法的网络节点 和信标节点密度、定位误差和定位精度等参数进行了比较说明,分析了各个算 法的优劣,并指出了针对不同定位算法所存在的问题；uEh0U1Yfmh 各种定位算法都有各自不同的应用领域,针对不同的情形有不同的定位算法可 供挑选,

32、没有那一种算法拥有肯定的优势,在某一种场合比较适用,但应用环 境一旦转变,可能这种算法的性能就会发生变化；在具体的应用环境中要综合12 / 13 名师归纳总结 - - - - - - -第 12 页,共 13 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用考虑算法的特点和实际情形,对于安全和定位的各种参数要有所取舍；另外,在不同的应用中仍应考虑把几种算法综合起来使用,针对同一种环境进行区域 划分,不同的区域适用不同的定位算法,然后再把这些算法结合起来,这也是 今后讨论的一个重点；IAg9qLsgBX 13 / 13 名师归纳总结 - - - - - - -第 13 页,共 13 页