项目与诛囊 Ｓｃ科ｉｅｎｃｅ＆Ｔｅ技ｃｈ视ｎｏｌｏｇｙＰｒ Ｖｉｓｉｏｎ － 科技·探索·争鸣 无线传感器网络基于测距的节点定位算法综述 Ｏｖｅｒｖｉｅｗ ｏｆ ｔｈｅ Ｎｏｄｅ Ｌｏｃａｌｉｚａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｒａｎｇｉｎｇ ｏｆ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ 罗兰花梁海英任子亭 （贺州学院，广西贺州５４２８９９） 【摘要】基于测距的定位方法对测量的距离信．Ｅ－运用几何知识求解未知节点的位置，常用在定位精度较高的领域，可在误差、能耗、受环 境因素影响等方面进行优化。本文对基于测距的无线传感器网络节点定位算法进行详细地分析和比较。 【关键词】无线传感器网络；节点定位；三边测量法；最大似然估计法 【Ａｂｓｔｒａｃｔ］Ｔｈｅ ｎｏｄｅ ｌｏｃａｌｉｚａｔｉｏｎ ｂａｓｅｄ ｏｎ ｄｉｓｔａｎｃｅ ａｌｗａｙｓ ｕｓｉｎｇ ｇｅｏｍｅｔｒｉｃ ｋｎｏｗｌｅｄｇｅ ｔｏ ｓｏｌｖｅ ｔｈｅ ｕｎｋｎｏｗｎ ｎｏｄｅ’Ｓ ｐｏｓｉｔｉｏｎ．Ｉｔ’ｓ ｕｓｅｄ ｉｎ ｔｈｅ ｉｆｅｌｄ ｏｆ ｈｉｇｈ ｐｏｓｉｔｉｏｎｉｎｇ ａｃｃｕｒａｃｙ，ａｎｄ ｉｔ ｃａｎ ｂｒｉｎｇ ｏｐｔｉｍｉｚａｔｉｏｎ ｉｎ ｅｌＴｏｒ，ｅｎｅｒｇｙ ｃｏｎｓｕｍｐｔｉｏｎ，ａｎｄ ｉｎｆｌｕｅｎｃｅｄ ｂｙ ｅｎｖｉｒｏｎｍｅｎｔａｌ ｆａｃｔｏｒｓ．Ｔｈｅ ｐａｐｅｒ ｄｅｔａｉｌｅｄ ａｎａｌｙｓｉｓ ａｎｄ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｈｅ ｎｏｄｅ ｌｏｃａｌｉｚａＩｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｒａｎｇｉｎｇ ｏｆ ｗｉｒｅｌｅｓｓ ｓｃｎｓｏＦ ｎｅｔｗｏｒｋｓ． 【Ｋｅｙ ｗｏｒｄｓ］Ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ；Ｎｏｄｅ ｌｏｃａｌｉｚａｔｉｏｎ；Ｔｈｒｅｅ ｓｉｄｅｄ ｍｅａｓｕｒｅｍｅｎｔ；Ｍａｘｉｍｕｍ ｌｉｋｅｌｉｈｏｏｄ ｅｓｔｉｍａｔｅ ０引言 可用几何图形表示为以已知节点为圆心，节点距离为半径三个圆的交 近十年来，无线传感器网络得到了前所未有的发展，在众多领域 点，如下图１所示。 中得到了广泛的实际应用，被认为是影响人类发展的十大技术之一。 尽管节点定位在定位精度、定位时间、能量开销等方面有了很大改进， 但仍然是制约和影响无线传感器网络应用的关键技术之一。 １ 常见定位方法分类 无线传感器网络中节点定位方法根据不同手段和角度有不同的 分类方法，典型的分类有以下几种。 １．１绝对定位和相对定位 绝对定位为网络命名空间提供一个唯一的地址，定位结果为坐标 位置，如经纬度等。此类定位方法对网络变动时适应性较好；相对定位 则以网络中某些节点作为参考节点，为其他节点建立坐标，相对定位 图１三边测量法示意图 不提供唯一的地址，无需信标节点，网络变动时适应性差。 １．２粗粒度与细粒度 假设Ｄ点坐标为（ｘ，Ｙ），则可得以下表达式： 根据信号强度、角度或时间等信息计算未知节点的位置称为细粒 Ｉ Ｎ／—（ｘ－ｘ．）２＋—（ｙ－ｙ，，）２：ｄｌ 度定位，如Ｒａｄｉｏ Ｃａｍｅｒａ定位系统中的信号模式匹配技术（ｓｉｇｎａｌ ｐａｔｔｅｍ ｛Ｎ／—（Ｘ－Ｘｔ，）２＋—（ｙ＿ｙｂ）２＝ｄ２ ｍａｔｅｈｉｎｇ）…；根据逐渐接近信标节点的信息来度量未知节点的方法称 Ｊ ｋ／—（ｘ－ｘｆｌ２＋—（ｙ－ｙｃ）２：ｄ 为粗粒度定位，如质心、衰减模型、凸规划、Ａｃｔｉｖｅ Ｂａｄｇｅ和ＰａｒｃＴＡＢ 通过解方程可得到Ｄ点坐标为： 均属于粗粒度定位。 ｒｘ１一ｆ２（ ％）２（ｙ ）１一，『 ， 凼２＿ｄ ］ １－３集中式定位和分布式定位 【Ｙ Ｊ—ｌ２（ 一 。）２（ — ）ｊ【 — ＋ 一 ｄ 一ｄ２２ ｊ 集中式定位先将所需的信息传递到中心节点然后进行计算，该方 三边测量法的缺点是节点距离误差较大时，可能出现三个圆无法 法侧重于对定位信息的集中处理，可以获得相对精确的定位，缺点ｌ 】是 交于一点，方程无解即定位失败。 中心节点能耗大，容易造成个别节点过快耗尽能量，从而影响其他节 ２．２三角测量法 点定位。 三角测量法根据三个信标节点与未知节点的角度和三个节点的 分布式定位则依赖于节点间的信息交换和协调，获得足够信息后 坐标信息计算节点间的距离，然后计算出未知节点坐标。该方法也是 节点自行定位计算。分布式定位通过节点问合作减少了整体定位时 一种基于几何运算的定位方法。 间，且能耗比较均衡，但会放大和累积定位过程的误差，从而影响定位 精度。 １．４基于测距定位和无需测距定位 基于测距定位方法测量节点间的距离、角度、信号强度和传输时 间等信息，然后借助三边测量、三角测量、最小二乘法或最大似然估计 法计算未知节点的位置；无需测距定位方法则通过网络连通度、节点 间相对距离计算未知节点位置。 基于测距定位方法能实现较精确的定位，但对节点硬件要求高、 Ｂ 功耗大和易受环境因素的影响，常用于精度要求较高的专业领域，如 图２三角测量法示意图 国防军事、等。无需测距的定位方法具有硬件要求低、成本 低、能耗小等优点，但存在误差较大、定位精度较低等问题，常用在精 三边测量法和三角测量法属于形式化数学方法，并不能很好地直 度要求相对较低的领域，如环境监测等。 接应用在无线传感器网络中。因此，国内外研究人员对这两种方法进 ２节点位置计算方法及其分析 行了优化和适应性修改，以适用无线传感器网络。 ２．３最大似然估计法 ２．１三边测量法 最大似然估计（ｍａｘｉｍｕｍ ｌｉｋｅｌｉｈｏｏｄ ｅｓｔｉｍａｔｉ０ｎ，ＭＬＥ）是通用的数 ｊ边测量法利用三个已知信标节点的坐标和未知节点的距离推 学估计方法，当测试数据量大时具有逼近特性，是三边测量法的扩展 导出未知节点的坐标。假设已知Ａ、Ｂ、Ｃ三个节点，坐标分别为（ Ｙ ）， 方法。 ｘｌ１＇Ｙ ），（ Ｙ），Ａ、Ｂ，Ｃ到未知节点Ｄ的距离为别为ｄ，、ｄ２，ｄ，，未知节点 已知Ｎ个已知节点Ｐ ｘ ，Ｙ ）， （ｘ ，Ｙ ），……Ｐ¨（ｘｎ＇Ｙ ）和未知节点 ※基金项目：广西高校科学技术研究重点项目（ＺＤ２０１４１２９）；贺州学院校级科研项目（２０１４ＺＣ２４ ｏ 作者简介：罗兰花（１９８２一），女，江西宜春人，贺州学院，讲师，主要研究方向为无线传感器网络、云计算。 ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎ。ｌ。ｇｙ Ｖｉｓｉ。ｎ科技视界Ｉ ２７ 科技·据索·争Ｉ毫 Ｓｃ科ｉｅｎｃｅ＆Ｔｅ技ｃｈ视ｎｏｌｏｇｙ界 Ｖｉｓｉｏｎ 项目与深曩 Ｐ的距离分别为ｄ１，ｄ２，……ｄｎ，如下图３所示。 于Ｔｉｋｈｏｎｏｖ正则化方法的多边定位算法，通过分析和大量实验最终 确定最优信道衰减指数ｎ为４，最优参考点数为５，通过实验发现基于 ●Ｐ． Ｔｉｋｈｏｎｏｖ正则化方法比最大似然估计法减少了定位误差，部分实验结 果如表１所示。 该算法未增加硬件开销，但降低了距离误差和定位误差，算法性 ０－ ． ● 能优于传统的基于ＲＳＳＩ的最大似然估计法节点定位。 ３．２ Ｈｏｐ—ｔｅｒｒａｉｎ迭代算法 Ｈｏｐ－ｔｅｒｒａｉｎ迭代算法是基于测距和无需测距相结合的定位方法。 Ｐｌ 、 ～ 该算法分两步进行，第一步先用距离无关定位方法估算各节点的初始 ～、 位置，然后用基于测距的定位方法对节点位置迭代计算以减小定位误 差。实验表明，Ｈｏｐ－ｔｅｒｒａｉｎ算法能较好地改善稀疏信标节点问题和测 Ｐｌ 量误差对节点定位的影响 ，当网络连通度较低时，收敛性变差。 图３最大似然估计法示意图 张松涛 提出的一个改进的基于距离约束迭代定位算法ＤＣＲ 则可得到以下方程组 （Ｄｉｓｔａｎｃｅ Ｃｏｎｔｒｏｌ Ｒｅｆｉｎｅｍｅｎｔ），主要针对Ｈｏｐ—ｔｅｒｒａｉｎ算法在网络连通 度比较低时，迭代过程收敛性下降，成功定位节点比例很低等问题。 （ － ） （），－－ｙ）２＝ｄ ＤＣＲ算法定位过程中刷选上次迭代结果作为最新迭代结果。该算法 （ ）２＋（ ） ＝ 也分为两步，第一步是节点坐标估算；第二步刷选节点位置进行迭代 更新。仿真结果表明在连通度低的网络中，ＤＣＲ算法节点定位成功率 ｌ（ — ） ＋（ —ｙ） ＝ｄ 比Ｈｏｐ－ｔｅｒｒａｉｎ算法提高了２０—３０％，精度较高节点比例比Ｈｏｐ－ｔｅｒｒａｉｎ 然后将每个方程分别减去最后一个方程，消去二次项得到线性方 算法平均提高了６．５％ｆ５１。 程形如目： ３＿３基于信号传输距离（ＴＯＡ）定位算法 ＴＯＡ（Ｔｉｍｅ ｏｆ Ａｒｒｉｖａ１）定位算法根据信号传播时间和速率计算信 其中： 标节点到未知节点的距离。该算法分为三步。第一步测距。测量未知 ｆ ‰ ｙｌ— １ ｆ Ｘ１２￣Ｘ － －ｙｏ％ｄ］－ｄｌ １ 节点到信标节点的距离或方位，至少包含三个以上信标节点的距离信 Ａ＝２ ｌ ｉ ！ ｌ；Ｂ＝ｌ ｉ ｌ 息；第二步定位。通过极大似然估计等方法计算；第三步修正。进一步 【 ｌ １— Ｊ 【 ｌＬ ｌＬ ＋ 一 １。Ｊ 矫正节点坐标，以保证精度。ＴＯＡ算法测量精度较高，但要求节点之 ｘ＝ｆ ｌ 间严格的时间同步，因此对硬件需求高，成本和能耗高，应用在对精度 通过最小均方差估计方法得到节点坐标为： 要求高的专业领域。 刘鹏１６１提出的改进的ＴＯＡ定位算法，信标节点同时发送两种不同 ＝（Ａ ｒＡ）— ｒＢ 速率的无线信号，未知节点根据接收的信号时间差计算出节点问的距 最大似然估计的缺点是需要进行大量的矩阵运算，计算开销大。 离。该方法解决了时间严格同步和硬件延迟问题，仿真实验表明改进 ２．４最小二乘法 的ＴＯＡ算法能获得更好的定位精度。 最大似然估计求解时利用方程相减的方法消去二次项，这会损失 综合上述几类算法，从算法实现的难易程度、硬件需求、能耗、误 已知坐标信息。如上述实数方程组（１）不存在任何一组值（ ，ｙ）使其满足 差和需已知节点比例等方面进行比较，结果如表２所示。 方程组，那么可以通过找到一组值（ ，ｙ ）使得方程组两边的值最接近， 表２ ＲＳＳＩ、Ｈｏｐ—ｔｅｒｒａｉｎ、ＴＯＡ算法比较 即求近似解。另外考虑到误差，误差的平方称为二乘方，误差最小就是最 小二乘法。实际使用中常将最小二乘法常和最大似然法结合起来求解。 上述方法是节点计算的基本方法，随着研究不断深入和应用领域 的不断扩展，涌现了很多改进方法，同时三维节点位和智能定位等新 的定位技术的出现，使得节点计算方法得到了很大的优化。 ３基于测距的节点定位算法分析及比较 除了上述基于距离的节点定位算法外，还有基于信号传输时间差 ３．１ ＲＳＳＩ定位算法 （ＴＤＯＡ）的基本定位方法及其改进算法、基于信号到达角度（ＡＯＡ）的 ＲＳＳＩ定位算法基本思想通过接收到的射频信号（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ， 基本定位方法及其改进算法等。总的来说，基于ＲＳＳＩ的定位算法具有 ＲＦ）强弱，根据传播衰减模型计算已知节点到未知节点的距离。ＲＳＳＩ 实现简单、低成本等特点，众多研究人员对算法进行改进使其误差不 算法优点是实现简单、硬件要求低和能耗低；缺点是易受实际环境的 断降低而更受欢迎。 影响，导致平均定位误差较大。目前很多研究人员对该算法进行了改 进并获得了较好的仿真和实际使用效果。 ４总结 丁恩杰等口提出的基于ＲＳＳＩ和加权质心结合定位算法，该算法先 通过ＲＳＳＩ测距得到４个信标节点到未知节点的距离，再任选其中３ 基于测距的定位方法是目前无线传感器网络使用最广泛的定位 个距离为半径，以信标节点为圆心画圆得到３个圆的交叠区域，构成 技术，它能获得较高定位精度而备受关注。本文首先对定位方法分类 进行了综述，然后分析了经典的节点位置计算方法的特点，最后对无 一个三角形，求出这个三角形的质心。按照该方法求出４个质心坐标， 利用加权质心定位算法求出未知节点的坐标。仿真结果表明定位精度 线传感器网络中几种具有代表性的基于测距的节点定位算法进行了 有很大的提高。 详细分析和比较。ｅ 表１ Ｔｉｋｈｏｎｏｖ正则化方法五点定位结果与最大似然法比较［４１ 【参考文献】 ［１］汪炀．无线传感器网络定位技术研究【Ｄ１冲国科学技术大学，２００７．４：１９—２１． Ｉ定位结果 Ｔｉｋｈｏｎｏｖ （１８．０３．１０．２５） （１９．１８，９．３８） （１７．８３ ８５） （１９．４１，８．４３） （１９．２６，６．６３） ［２］于宁．无线传感器网络定位优化方法［Ｄ１．北京邮电大学，２００８．４：１５． ［３］丁恩杰，乔欣，常飞，乔莉．基于ＲＳＳＩ的ＷＳＮｓ加权质心定位算法的改进『Ｊ１． 定位误差 １．８３ ０．４７ １．８７ １ ００ ２．８０ 传感器与微系统，２０１３ ７：５３—５６． 最大似然法 （１８［４］秦念庆．基于ＲＳＳＩ的无线传感器网络多边定位算法研究ｆＤ１．山东大学论文， 定位结果 ．８￣１２５８） （１９．９０，１１３４） （１８．４２，１１．４３） （１￣１＆Ｉ２．３４） （１９．６５，１３，８７） ２００９．４：３５—３６ ［５］张松涛．无线传感器网络定位问题研究ｆＤ１．华中科技大学 ２０１０．５． 定位误差 ３．２８、ｒ １．９５ ２＿３７ ２．９７ ４．４７ ［６］刘鹏，宋迪，牛斗．ＷＳＮ中一种改进的丁０Ａ空间定位算法研究ｌ Ｊ１ｌ微计算机信 注：误差及定位结果单位为ｍ． 息，２００９（２５）：２８３—２８４． 秦念庆Ⅲ针对传统的基于ＲＳＳ１定位算法存在不适宅问题，提出基 ［责任编辑：王楠］ ２８ Ｊ科技视界ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎ。 。ｇｙ Ｖｉｓｉ。ｎ
