【基于非测距的物联网定位算法展开探究10000字（论文）】

--PAGE5-基于非测距的物联网定位算法展开研究目录TOC\o"1-2"\h\u30718第一章绪论 283061.1课题的研究背景及意义 228231.3物联网定位技术研究现状 3284581.4研究内容和章节安排 410258第二章物联网定位技术介绍 668052.1定位技术简介 6173532.2基于非测距的定位算法 6319082.3基于测距的定位算法 8206412.5本章小结 1217714第三章DV-Hop算法及其改进 1344383.1DV-Hop算法 13320203.3DV-Hop算法误差分析 1482703.2DV-Hop算法优化 15159833.2本章小结 1623306第四章仿真实验与分析 1724344第五章总结与展望 28第一章绪论1.1课题的研究背景及意义物联网IOT是指通过各种各样的信息传感器、射频识别技术、全球定位系统、红外感应器、激光扫描器等各种装置或技术，通过各类存在的网络进行接入，将各种各样传感器与网络结合起来而实现在任何时间、任何地点，人、机、物互联互通的网络统称。早在15世纪时，当人类开始将目光投向广阔的海洋并决定对其展开探索时，定位技术就已经给当时的人们带来了很大的帮助，但由于当时的定位技术尚处于刚开始发展的阶段，所以当时的定位方法也十分的粗糙，例如，出海的船只能依赖于航海线和引航灯航行、运用航海图和星象图来大致确认自己所处的位置这便是物联网定位的前身。在物联网的众多相关技术中，感知层的定位技术定位技术在该网络的众多技术中起决定性作用，同时也是物联网推广应用的前提条件，该技术主要是对一些目标进行监测、识别和跟踪。随着硬件设备行业的不断发展，带来了物联网领域的飞速发展，定位技术在技术手段、定位的精确度、定位范围及可用性等方面都有了质的飞跃。科技的进步，带来的是我们生活环境的巨大变化，当然，这种变化是朝向带给人们快捷和便利的方向的。举一个很简单的例子，现代社会的人们的日常生活几乎离不开手机的使用，而手机中的多数软件的使用都需要用到手机的位置信息，利用定位技术获取的定位信息在这些软件的相关功能中扮演者及其重要的角色。往更高的层面看，在国防领域，一些精准制导的导弹只有通过定位技术获取到目标的精确位置后才能将导弹发射到隔着十万八千里的目标位置并根据目标的位置变化调整导弹的飞行轨迹。由此可见定位技术的重要性。在目前成熟的定位技术中，全球定位系统GPS和北斗卫星等全球卫星定位系统是对目标进行定位的主要手段，但它们对硬件设备的成本、功耗和体积等方面都提出了很高的要求。此外，物联网定位技术还包括如近几年发展的蜂窝网络通过无线电和基站的定位技术，以及基于RFID标签的定位技术等。定位技术很多很多，通过对简单的定位技术进行分析比较，得到它们的优缺点，找到它们不同的适合应用场景，这是在定位技术研究领域的热门课题，也是设计出更加优秀的+定位算法的必要条件。1.3物联网定位技术研究现状节点定位技术牵涉到的相关技术指标比较多，包括节点定位的误差大小、通信网络是否可靠、路由算法、功率大小及硬件成本等，这些导致不同的定位算法在使用它们进行定位计算时，会出现不同的优缺点，这带来了它们有着各自不同的适用领域。对于这些定位算法，按照定位机制，一般可将其划分为基于测距（Range-Based）和非测距（Range-Free）的定位算法，这也是目前最广为人所采用的划分依据。基于测距的定位算法，指布置额外的硬件设备来得节点数据，再利用这些得到的已知节点的数据信息来估算未知节点的位置坐标信息。比较常见的基于测距的定位算法有基于最小二乘法的定位算法、基于接受信号强度RSSI测距的定位算法、基于到达时间TOA的定位算法，基于到达时间差TDOA的定位算法等。这些基于测距的定位算法因为需要部署额外的硬件设备，所以它们的节点布设硬件成本很高，通信开销也较大，但相对的，这些算法的覆盖率以及定位精确度都相对较高。基于非测距的定位算法，在于不用去像基于测距的算法那样部署节点得到节点数据，而是只需通过网络拓扑结构中的节点之间的关系和已经知道的信息，便可以通过相关数学公式大致计算出目标的位置信息。目前这一算法算是学者们最常研究的定位算法方向，因为它更加适用于在一些无需高精确度的场景中，而且无需顾虑过高硬件成本、环境影响等因素。这些算法包括质心定位算法、网格定位算法、DV-Hop算法等。现有的物联网定位算法在一定程度上能够满足大多数节点的定位问题，但是应用场景需要满足特定的限制条件。如果在不满足限制条件的情况下使用，往往会出现与预期差距过大的情况，即定位的精确度和稳定性会大幅度地下降，以至于无法得到正常的使用。分析已有算法的优缺点，在满足限制条件的情况下，提高定位算法的性能是当前研究的热门问题。算法是定位技术的核心。监测区域中的锚节点是定位算法的基石，考虑到硬件成本和运行维护能耗等问题，我们一般会将监测区域内的锚节点控制在一定范围之内，当降低监测区域内锚节点的部署密度时，定位算法的定位精度和定位覆盖率会出现较为明显的下降。文献[1]通过将粒子群算法与DV-Hop算法结合，利用适应度函数搜索到的群体最优值作为未知节点的位置坐标,以此来提高节点的定位精度。文献[2]将接收信号强度与Sigmoid函数结合起来作为权重以此来改进加权质心定位算法，通过优化后的算法来计算出未知节点的坐标，通过仿真实验表明，这种改进能够极大提升算法性能。由此来说，在更加接近真实环境的非理想验环境下，如何通过优化已有的算法来来提高算法的性能是物联网定位算法研究领域的研究热点。1.4研究内容和章节安排1.4.1主要工作和内容本文首先介绍了物联网定位算法的研究背景以及研究现状。接着介绍了几种基于测距的定位算法的实现原理，以及它们的优缺点，在第三章中着重介绍了基于非测距的三种基本算法，以及改进的加权质心定位算法，并通过仿真实验数据横向对比分析了质心定位算法与加权质心定位算法。1.4.2章节安排本文在大量学者的不断努力上，对经典算法的原理进行了相关介绍，结合其他相关研究成果，着重研究了DV-Hop及它的一个优化后的定位算法。结构安排如下：第一章：绪论章节主要介绍了物联网定位技术的当前研究背景和研究意义、研究现状以及介绍了部分学者对该领域的研究情况，最后对本论文的研究内容和组织结构进行了介绍。第二章：介绍了几种经典的定位算法，如基于非测距的质心定位、加权质心定位、网格定位。基于测距的最小二乘法定位，RSSI定位、TDA/TDOA定位算法等。第三章：着重介绍了基于非测距的DV-Hop及其优化算法，对他们的原理、误差进行了分析。第四章为实验仿真部分。本章节首先定义了仿真实验的误差。仿真实验验证了三种经典的非测距定位算法以及一种优化的DV-Hop算法，结果证明改进的算法对性质有了显著提升。第五章为文章的全文总结及未来展望部分，本章节总结了本论文完成的主要工作，以及在最后对下一步研究的方向进行了规划。

第二章物联网定位技术介绍2.1定位技术简介目标定位算法是获取目标位置的手段之一，利用观测到的数据信息，采用适当的定位算法、结合应用场景的特点进行目标定位能达到较好的效果。通过定位算法是无法得到与目标真实位置完全一致的位置信息的，但使用它能从最大程度上逼近真实位置，从而使定位误差降到合理的阈值以下。目标定位算法分为基于测距的定位算法和基于非测距的定位算法。2.2基于非测距的定位算法非测距定位Range-free，广泛的指不依赖于任何信息，无需测量目标与节点之间的距离、角度等数据信息，或者当被测目标与节点间的在距离和角度方面的误差非常大时，只能用这些信息作权值使用的算法。基于非测距的定位算法，只能依靠观测站的物理部署和简单的观测站是否探测到目标的“0”“1”二进制信息来对目标位置进行估计。非测距定位算法主要包有质心定位算法、加权质心定位算法和网格定位算法等，它们虽然能估计出具体位置，但是这个位值往往与目标真实位置的偏差比较大。2.2.1质心定位算法质心即质量中心，指物质系统上被认为该物体质量集中于此的一个假象点。三角形三条中线的交点、平行四边形的对角线、正六边形的对角线交点，这些点都可以看做是这些常见几何图形的质心，如下图所示图2.1几何图形的质心对于多质点系统来说，假定每个质点的重量为mi，位置为p(xi,yi,zi),那么该质点的质心计算方法可以用公式（2-1）来表示：（2-1）当考虑各质点的质量一样时，那么多质点系统质心的计算方法则可以简化为：（2-2）上述即为质心定理，通常用来计算一个图形或者物体的质心坐标，当将此定理的原理用在物联网定位领域上，它便变成了熟知的质心定位算法：假定在一个场地内，分布着若干个观测站，每一个观测站的位置设为p(xi,yi,zi)，将能够探测到的目标的所有观测站看成一个多质点系统，此时按照简化后的质心计算方法便可以计算得到一个位置，这个位置便是目标位置的估计值。2.2.2加权质心定位算法观测站在探测目标时，传感器可以根据探测到的目标信号的强度，如声音信号强度（dB）或无线接收信号强度（RSSI）粗略的判断目标的远近，并将这个强度作为一个权值，用在质心定位算法中，这便是加权质心定位算法了，它可以被表示为： （2-3）式（2-3）中，（xc,yc,zc）表示第i个基站的位置，w是权值。那么，在使用计算机进行仿真时，需要通过一定的数学关系来建模并表示这一权值w：一般地，权值与距离被认为会具有一定的比例关系，如RSSI与距离有近似反比的关系，建模时可粗略的认为： （2-4）式（2-4）中，r为目标与观测站的距离；n为噪声，表示观测站测得的RSSI和声音信号的强度是受到噪声干扰的。噪声的给定方法可以参考信噪比（SignalToNoiseRatio,SNR）参数，它的定义如下： （2-5）式（2-5）中，S表示信号值，在这里表示接收到的信号强度值（声音强度值）；N表示噪声的方差。假如信噪比是10dB,那么。2.2.3网格定位算法将观测站均匀的部署在检测场地，并将它们整齐地排列成队列网络的形式，以此来计算目标位置的算法称为网格定位算法。网格定位算法的特点是将监控区域网格划分，它在位置表示、坐标系建立、后台管理等方面具有优势在网格中，所有节点都位于监测区域内，当将此区域D进一步划分为n2或nm个单元时，通信半径一般为大于1个单元而小于2个单元区域，即边长为2个单元的正方形区域。由于观测站部署密集，为了简单有效，对于进入检测区域内的目标，可以选用探测到目标信号最强的几个观测站的位置信息来估计目标的位置。网格定位是一种避免网络大量通信的节能的定位算法。适合大量部署的检测环境，如无线传感器网络。它也是一种在硬件节点探测能力有限的或传感器信息准确度较低的场合中应用的一种有效的定位算法。2.3基于测距的定位算法基于非测距的定位算法误差通常来说是比较大的，要想提高精确度往往得提高观测站的部署密集度。但是对于很多功能强大的观测站，尤其是能实现精确测距和测角的观测站，实现精确定位就很容易。例如雷达、声呐等能非常准确地测量其与目标之间的距离。对于定位算法而言，它只能最大限度地降低误差，而不能完全地消除误差。下面介绍的是两种常见的基于测距的定位算法（Range-based）：最小二乘定位算法和基于RSSI测距的定位算法。2.3.1最小二乘定位算法设目标的坐标为M(x,y)，监测区域内有n个观测站，它们的的坐标分别为（x1,y1）,(x2,y2),…，（xn,yn）,目标到观测站的距离分别是d1,d2,…，dn,则： （2-6）在式（2-6）的基础上，从上至下依次与最后一式相减，就可以得到如下式 （2-7）由最小二乘原理原理可以得到目标位置的最小二乘估计值X： （2-8）式中，此式是基于观测距离的目标定位系统中最常用的定位算法。式中，当矩阵A大于等于2时，解有唯一一个。换句话说，只通过观测距离而要对二维平面目标定位需要至少3个并且是部署在不同位置的观测站，同样的道理，对三位空间目标定位时，需要至少4个并且是部署在不共面的空间位置中的的观测站。2.3.2基于RSSI测距的定位算法渐变模型（ShadowingModel）是在无线信号传输中被普遍采用的理论模型： （2-9）式中,d表示发射端与接收端的距离；p(d)表示RSSI值，即接收端与发射端之间的距离为d时接收到的信号强度；p(d0)表示接收端与发射端之间的距离为d0时接收到的信号功率；d0为参考距离；n是路径损耗PassLoss指数，通常由实际测量得到，障碍物越多，n值越大，从而接收到的平均能量下降的速度会随着距离的增加而变得越来越快：X是一个以dBm为单位、平均值为0的高斯随机变量，表示当距离一定时接收机接收到的能量值的变化情况。实际应用中一般采用简化的渐变模型： （2-10）为了便于表达和计算，通常取d0为1m。把p(d)改成RSSI，于是可得： （2-11）式中，A为无线收发节点之间相距1m时接收节点接收到的无线信号强度RSSI值。根据式（2-11）中给定的RSSI与d的函数模型，只需知道接收机接收到的RSSI值，接收机与发射机之间的距离d便可以通过此式计算得出。基于RSSI测距的定位算法流程如下：图2.2RSSI测距流程图2.3.3基于TOA的定位算法基于TOA的测距通过测量两个节点之间信号的传输速度和时间延迟来估算两点之间的距离精度的。如图2.3所示，信号在t1时刻从节点A发出,在t2时刻到达节点B，t3时刻时从节点B返回，最后在t4时刻节点A重新收到该信号，设信号传播速度为v，那么节点A、B之间的距离d为： （2-12）图2.3TOA测距示意图基于TOA测距的方法由于无线信号的传输速度快，时间测量即便有很小的误差都会导致结果距离出现很大的误差值，另外它对于传感器节点有很高的计算能力要求。2.3.4基于TDOA的定位算法两个节点发送无线电磁波、超声波信号两种不同的信号，接收节点通过信号的到达时间差，根据这两种信号的传播速度来计算收发节点间距离的方法，就是基于TDOA到达时间差的测距方法。如图2.4所示，节点A在t0时刻发送两种不同的信号给节点B，节点B分别在t1和t2时刻收到这两种信号，两种信号的传播速度分别设为v1、v2,那么节点A、B之间的距离d可用式来表示： （2-13）图2.4TDOA测距示意图由于超声波信号的传播速度比较低（约为331.4m/s）,因此基于超声波的TDOA定位机制可以在时间测量并不是特别精准的条件下进行精准定位。同时在使用TDOA方式进行定位时不需要全局时间同步，也不需要利用信号到达的绝对是件来确定节点的位置，降低了设备在时间方面的要求，因此易于实现且精度较高。但是。基于超声波的TDOA定位算法在距离的测量上还存在着一定的局限性。首先，由于超声波信号的传播具有方向性，当收发节点之间存在障碍物时，会带来较大的测距偏差；其次，此方法需要超声波信号收发节点在一定的角度范围内才能收集到数据，并且角度的不同也会带来测距精度的上下浮动；第三，因为超声波信号衰减较快，所以它的传播距离往往较短，通常在十几米的范围内；另外，超声波的传播特性会在一定程度上受到风向、温度等环境因素的影响。综上，超声波定位比较适合范围小、精度高的室内定位环境。2.5本章小结物联网定位技术可以分为基于非测距的定位技术和基于测距的定位技术两类：对于非测距的定位算法而言，它们的精确度一般都不高，并且精确度往往与检测场地部署的观测站密度有关。但是基于非测距的定位算法无需测量节点的距离、方位、到达时间等，而是利用网络连通度的信息以及信标节点与未知节点间的几何关系求出未知节点的坐标。这种类型的定位算法对传感器节点设备的要求较小。

DV-Hop算法及其改进3.1DV-Hop算法DV-Hop算法在APS算法系列中是最为研究者研究的定位算法，在DV-Hop的算法过程中，它不依赖于通过测距方法得到测量的物理量，而是利用多跳信标节点信息来进行信标定位。它所采用的算法机制与传统网络中的距离路由向量路由机制十分相似，在其中，未知的节点通过跳数和平均跳距计算出与信标节点之间的最小跳数，然后估算平均每跳距离，之后将最小跳数与平均每跳距离相乘得到估算出的未知节点和信标节点之间的距离，在最后通过这些计算得到的距离，使用三边测距法或者极大似然估计法即可求得未知节点的坐标。DV-Hop定位算法可分为以下三个步骤：计算未知节点与每一个锚节点的最小跳数在初始化网络时，网络中的已知节点就会不断地向周围节点广播自己的位置信息的分组，在初始阶段将跳数字段设置为0.网络中的接收节点会接受并记录具有到每一个锚节点的最小跳数。在将来自同一个信标节点的较大跳数的分组忽略后，将跳数值加1，之后将其转发给邻居节点，之后通过不断地接收-转发网络中的所有的节点都能够接收到相应的数据信息并将信息中的每一个节点的最小跳数记录下来。计算未知节点和锚节点的平均每一跳距离根据步骤（1）记录的其他锚节点的位置信息和相距跳数，每个锚节点利用下式估算平均每跳的实际距离： （3-1）其中，（xi,yi）为锚节点i的位置坐标；hj为锚节点i与j（j≠i）之间的跳段数。之后，锚节点将计算得到的每跳平均距离用特殊字段广播到网络中，未知节点只记录接收到的第一个每跳平均距离，并将其转发给周围节点。这种方式可以让网络中的大部分未知节点从最近的锚节点接收每跳平均距离。在未知节点全部记录下平均每跳距离后，根据记录的跳数，计算每个锚节点之间的距离未知节点计算自身位置利用步骤（2）中得到的到每个锚节点的跳段距离，未知节点利用三边测量法或极大似然估计法可以计算得出自身的位置坐标。图3.1是DV-Hop算法示意图：经过步骤（1）和步骤（2），可以计算出节点L1和L2、L3之间的距离和跳数。锚节点L2计算得到每跳平均距离为.假设未知节点A从L2获取每跳平均距离，则它与3个锚节点之间的距离分别为，最后使用三边测距法即可确认节点A的位置。图3.1DV-Hop算法测距示意图3DV-Hop算法误差分析在DV-Hop定位算法中，算法的步骤（1）中，由于传感器节点随机分布和广播分组过程中可能存在冲突等因素，节点得到的到锚节点的最小跳数存在有一定偏差，且跳数越多，偏差越大。在锚节点采用步骤（1）估算平均每跳距离时，所利用的是除了当前节点外所有其他的锚节点，所以得到的是全网络范围内的平均每跳距离，不足以反映锚节点一定范围内的网络密度分布情况，因此，采用该方法得出的平均每跳距离在密度均匀的各项同性网络中没有太大影响，但在密度不均匀的各项异性网络中，就会带来很大的计算误差。在DV-Hop算法的步骤（3）中，未知节点利用了到所有锚节点的距离数据信息，但是根据前面的分析，未知节点到锚节点的最小跳数可能有偏差，跳数越多，偏差越大，并且步骤（2）得出的平均每跳距离也只是对实际距离的一种估算，不可避免会存在着误差，这样锚节点距未知节点跳距越多，锚节点和未知节点的跳段距离误差就越大，利用较远锚节点的距离信息参与位置计算，反而可能降低了定位结果的精确度。3.2DV-Hop算法优化由3.1对经典的DV-Hop算法介绍可知，DV-Hop算法采用其中描述的三个步骤来对网络中的节点进行定位，该方法对硬件设备要求不高，实现也简单。其缺点是利用跳段距离来代替直线距离，存在一定的误差：在步骤（2）估算平均跳距时，由于估计过程中存在误差，在利用数学方法计算未知节点坐标时，将含误差的数据直接使用，因此定位准确度会得不到保证。根据上面的分析，本文对DV-Hop算法的一种优化算法做了研究，优化后的算法计算过程在大体上仍与原DV-Hop算法大致相同，下面只对改进之处进行说明。在DV-Hop算法的步骤（1）中，锚节点向周围节点广播自身信息的分组时，该分组加上生存期字段n，其他节点在转发该广播包时，首先检测包含生存期数据字段，如果n大于1，则将n=n-1，之后转发广播包,以保证该分组仅在n跳范围内广播。这样每个节点仅收到n跳范围内信标节点信息，降低了原DV-Hop算法高通信开销、高分组冲突概率等问题。图3.2优化算法步骤一在DV-Hop算法的步骤（2）中，利用步骤一中的式估算平均每跳实际距离时，锚节点j取自该节点n跳范围内跳数最少的的m个锚节点。这样处理保证估算的平均每跳实际距离更加符合该节点附近的节点分布情况，提高了距离估计精确度，并使该方法适用于各向异性网络。最后，在未知节点利用最小二乘法计算自身坐标时，由于锚节点距离该未知节点跳段越近，未知节点和锚节点间的距离估计就越精确（概率意义上），所以这里只选跳段距离最近的I个节点进行最大似然估计法运算。这样，既能提高算法的定位精确度，又可以降低节点的计算开销。参数m、n、I的取值要综合考虑锚节点比例、网络的连通度、传感器节点分布等因素。一般情况下，n要保证绝大多数未知节点一个节点能收到3个以上的锚节点分组，而m、I取4~6即可取得相对高的精确度。3.2本章小结本章先是介绍了经典的DV-Hop算法原理，接着研究了一种DV-Hop算法的优化算法，并介绍了优化算法的优化思路

第四章仿真实验与分析4.1仿真环境和参数为了比较几种基本算法的优缺点，以及为了验证改进后的DV-Hop算法的性能，在MatlabR2019b平台上进行了仿真实验4.2基于非测距的三种经典定位算法4.2.1质心定位算法观测站被随机分布在100m×100m的正方形区域内，假定它们的探测距离为50m,即在以观测站为中心的、半径为100m的范围内都能会被目标探测到，场地上部署N=6个观测站，一个目标随机出现在检测场地内，被其中的几个观测站探测到，并计算估计位置。当只有一个观测站探测到目标时：当三个观测站探测到目标时：当6个观测站全部能探测到目标时：当能观测到目标的观测站数量为1、3、6时，估计位置和实际位置的误差距离分别为41.5265m、31.83m、17.3004m,由此可见，使用质心定位算法时，随着能观测到目标的观测站数量的增加，对目标的定位精确度是逐步上升的。即质心定位算法的定位误差与观测站的位置及部署密度关系密切。4.2.2加权质心定位算法观测站被随机分布在100m×100m的正方形区域内，假定它们的探测距离为50m,即在以观测站为中心的、半径为100m的范围内都能会被目标探测到，并且观测站能够探测到目标距离观测站的声音信号强弱，观测站部署数量为6。一个目标随机出现在检测场地内，被其中的几个观测站探测到，并计算估计位置。当探测到目标的观测站数量为1时当探测到目标的观测站数量为3时当全部观测站都能探测到目标时当能探测到目标节点的的观测站数量分别为1、3、6时，定位误差分别为14.8732m，9.267m,5.3037m,即加权质心定位算法还是满足定位误差与观测站位置和部署密度关系密切的性质，但在相同的能探测到目标的观测站数目条件下，加权质心定位算法能大幅度降低定位误差。实现结果证明，权值的引入对于质心定位算法来说，能够有效地降低定位误差。4.2.3网格定位算法使用网格定位算法进行MATLAB算法仿真时，运行三次得到的结果分别为6.3349m、3.0264m、5.9012m,平均误差距离为5.0875m，从结果得出的定位精确度来看，网格定位精确度相比前两种算法得到的精确度更高，但网格定位算法需要部署大量的观测站节点，所以他比较适合大量部署的检测环境，如无线传感器网络。4.3DV-Hop算法在100m×100m的正方形区域的监测区域内，初始分布100个网络节点以及40个信标节点，节点的通信距离R定为40m.通过DV-Hop算法计算每个未知节点的误差。之后改变信标节点比例或者节点的通信半径，分别得出算法的平均定位误差和信标节点比例以及节点通信距离的关系。由以上仿真图可知，DV-Hop算法的定位误差在总体上会受到信标节点比例以及节点的通信半径的影响：信标节点比例和节点通信半径的提高均会在一定程度上提升算法的定位精确度。4.3优化后的DV-Hop算法不改变DV-Hop算法的运行条件，只改变信标节点比例或者节点通信距离，将DV-Hop算法及其改进算法进行比较分析，得出两者在相同条件下定位误差与信标节点比例以及节点通信半径的关系图。由以上仿真图可知，DV-Hop优化算法与原来算法相比，在同一运行条件下，能够明显的降低原来算法的定位误差。第五章总结与展望5.1工作总结本文围绕基于非测距的物联网