无线传感器组网-定位技术

第八章、定位技术内容提要WSN定位概述基本术语定位的分类基于测距的定位技术无需测距的定位技术测距方式对精度的影响典型定位系统一、概述1、定位的含义在传感器网络的很多应用问题中，没有节点位置信息的监测数据往往是没有意义的。无线传感器网络定位问题的含义是指自组织的网络通过特定方法提供节点的位置信息。这种自组织网络定位分为节点自身定位和目标定位。节点自身定位是确定网络节点的坐标位置的过程。目标定位是确定网络覆盖区域内一个事件或者一个目标的坐标位置。节点自身定位是网络自身属性的确定过程，可以通过人工标定或者各种节点自定位算法完成。目标定位是以位置已知的网络节点作为参考，确定事件或者目标在网络覆盖范围内所在的位置。在无线传感器网络中，传感器节点自身位置信息的获取是大多数应用的基础。首先，传感器节点必须明确自身位置才能详细说明“在什么位置发生了什么事件”，从而实现对外部目标的定位和跟踪；其次，了解传感器节点的位置分布状况可以对提高网络的路由效率，从而实现网络的负载均衡以及网络拓扑的自动配置，改善整个网络的覆盖质量。2.定位的意义位置信息有多种分类方法。位置信息有物理位置和符号位置两大类。

物理位置指目标在特定坐标系下的位置数值，表示目标的相对或者绝对位置。

符号位置指在目标与一个基站或者多个基站接近程度的信息，表示目标与基站之间的连通关系，提供目标大致的所在范围。3.位置信息的分类二、基本术语(1)锚点：指通过其它方式预先获得位置坐标的节点，有时也称作信标节点。网络中相应的其余节点称为非锚点。(2)测距：指两个相互通信的节点通过测量方式来估计出彼此之间的距离或角度。(3)连接度：包括节点连接度和网络连接度两种含义。节点连接度是指节点可探测发现的邻居节点个数。网络连接度是所有节点的邻居数目的平均值，它反映了传感器配置的密集程度。(4)邻居节点：传感器节点通信半径范围以内的所有其它节点，称为该节点的邻居节点。(5)跳数：两个节点之间间隔的跳段总数，称为这两个节点间的跳数。(6)基础设施：协助传感器节点定位的已知自身位置的固定设备，如卫星、基站等。(7)到达时间：信号从一个节点传播到另一个节点所需要的时间，称为信号的到达时间。(8)到达时间差(TDoA)：两种不同传播速度的信号从一个节点传播到另一个节点所需要的时间之差，称为信号的到达时间差。(9)接收信号强度指示(RSSI)：节点接收到无线信号的强度大小，称为接收信号的强度指示。(10)到达角度(AngleofArrival,AoA)：节点接收到的信号相对于自身轴线的角度，称为信号相对接收节点的到达角度。(11)视线关系(LineofSight,LoS)：如果传感器网络的两个节点之间没有障碍物，能够实现直接通信，则这两个节点间存在视线关系。(12)非视线关系：传感器网络的两个节点之间存在障碍物，影响了它们直接的无线通信。三、定位的分类根据定位结果坐标类型的不同网络中存在已知位置的锚节点，所有节点根据锚节点确定自己的位置，使用同一个坐标系。网络中不存在已知位置的参考节点，所有节点确定到其它节点的相对位置。绝对定位相对定位根据在定位过程中是否把信息传送到某个后台中心或服务器进行节点坐标的计算把所需信息传送到某个中心节点(如某台服务器)，并进行节点定位计算的方式。指依赖节点间的信息交换和协调，由节点自行计算的定位方式。集中式定位分布式定位根据各节点定位的先后次序从信标节点开始，首先从邻居节点开始定位，然后逐渐向外围延伸，各节点依次实现定位。

定位一旦开始，所有的节点同时进行位置坐标的计算，即定位。不存在先后次序。递增式的定位算法并发式的定位算法根据定位过程中实际测量节点间的距离和角度与否通过测量节点间点到点的距离或角度等信息进行位置估计。无须距离和角度信息，仅根据网络连通性等信息即可实现定位。无须测距技术的定位基于测距的定位(5)根据部署的场合不同，分为室内定位和室外定位；(6)根据信息收集的方式，网络收集传感器数据称为被动定位，节点主动发出信息，用于定位称为主动定位。利用信标节点的位置，通过测量和估计信标节点与目标节点的距离，我们就能够利用它们之间的关系很容易地算出目标节点的位置。基于测距的定位技术涉及几何中的图形问题，已知节点的位置，求另外几个节点的位置，比较常用的方法有：三边定位法角度定位法角度定位需要另外测量接收信号夹角，测量出夹角后使用数学几何条件，确定节点的位置。因为测量的信号夹角不可能很精确，所以AOA的精度不理想。四、基于测距的定位技术1．基本思想三边定位法如图所示，已知A、B、C三个节点的坐标分别为（x1，y1）、（x2，y2）、（x3，y3）。测得它们到未知节点D的距离分别为d1、d2、d3。假设节点D的坐标为（x，y）。以A、B、C三点为圆心，d1、d2、d3为半径做圆，三圆的焦点即为节点D的坐标。基于测距的定位技术——三边定位法那么，我们可以列出以下公式：将第一个方程和第二个方程同时减去第三个方程，得到结果将其写成线性方程的形式，AX=B，其中基于测距的定位技术——三边定位法由此可以得出节点D的坐标为三边定位和多边定位多边定位Multilateration多次测量方程的个数大于变量的个数估计方法：最小二乘（LS，LeastSquare）极大似然（MLE,MaximumLikelihoodEstimation）最小均方差（MMSE,MinimumMeanSquareError）三边定位法三边定位技术的计算方法比较简单，在已知两点之间距离的情况下，采用单纯的数学公式就可以计算出来，节点之间距离的测量才是三边定位技术的最难点，一般来说，有以下多种算法可以测量两个节点之间的距离：根据接收信号的强度进行测距；根据信号传播时间进行测距；根据信号传播时间差进行测距；根据接收信号相位差进行测距。2．主要技术1）根据接收信号强度测距（RSSI）

信号衰减模型如下式：式中，P(d)、P(d0)分别表示在距离基站d、d0处的信号强度，P(d)是接收节点实际测得的信号强度RSSI，P(d0)一般可以距天线d0米处的路径衰减来代替。基于测距的定位技术——三边定位法2）根据信号传播时间测距（TOA）该技术是采用信号到达时间来测量距离的，是一种基于传输时间的定位技术。己知信号传播速度，通过测量信号从发射机传播到多个接收机所消耗的传播时间来确定移动用户的位置TOA测距的基本思想是测量基站节点发射信号的到达时间，并且在发射信号中要包含发射时间标记以便接收基站确定发射信号所传播的距离，该方法要求接收节点和基站节点的时间精确同步基于测距的定位技术——三边定位法如图所示，有A、B、C三个基站节点，因为节点间的距离测量都是一样的，这里我们就假定先测量基站A到目的节点的距离。假设基站A到目的节点D的距离为d，声波传播速度为v，在T1时刻基站A发射机发射一个声波信号给目的节点D，D节点在T2时刻接收到该声波信号，经过短暂的处理之后，在T3时刻目的节点D回送一个声波测距信号给A节点，在T4时刻A节点接收到该信号。由此可以得出声波信号在介质中传播的时间为：基于测距的定位技术——三边定位法2）根据信号传播时间测距原理在这段时间内，声波传播的距离为2d，我们就可以得到值得注意的是，这里的T1和T4时刻是由节点A测得的，T2和T3时刻是由目的节点D测得的，由于时钟漂移、定位误差等的存在，两者的时间会有一定的时间差，但是由于采用双向无线通信的方式，两者的时间差相互抵消，对结果没有太大影响基于测距的定位技术——三边定位法在基于到达时间差TDOA的定位机制中，发射节点同时发射两种不同传播速度的无线信号，接收节点根据两种信号到达的时间差以及已知这两种信号的传播速度，计算两个节点之闻的距离，再通过已有基本的定位算法计算出节点的位置。基于测距的定位技术——三边定位法3）根据到达时间差测距（TimeDifferenceOfArrival，TDOA）如图所示，发射节点在时刻T0同时发射无线射频信号和超声波信号，接收节点记录两种信号到达的时间T1和T2，己知无线射频信号和超声波的传播速度分别为c1和c2，那么我们可以知道射频信号和超声波信号传播的时间为：由

可以得出：3）到达时间差测距原理TDOA有一些固有的缺陷需要考虑。（1）利用TDOA进行定位要求传感节点上必须附加特殊的硬件（声波或者超声波的收发器等），这会增加传感节点的成本；（2）声波或者超声波在空气中的传输特性和一般的无线电波并不一样，空气的温度、湿度或者风速都会对声波的传输速度产生很大的影响，这就使得距离的估计可能出现较大偏差；（3）TDOA测速的一个很大的假设是发送节点和接收节点之间是没有障碍物阻隔的，在有障碍物的情况下会出现声波的反射、折射和衍射，此时得到的实际传输时间将变大，在这种传输时间下估算出来的距离也将出现较大的误差。3）到达时间差测距的缺点通过测相位差，求出信号往返的传播时间，计算出往返距离其中，fc是信号频率，λ是信号的波长，φ是发送信号和反射信号的相位差。由上式可知d的范围是[0,λ]。不同的距离如果相差λ倍，则测量获得的相位相同。4）接收信号相位差测距（PDOA）常用的角度定位方法有：已知两个顶点和夹角的射线确定一点，以及已知三点和三个夹角确定一点。1．已知两个顶点和夹角的射线确定一点如图所示，测得参考点A(x1,y2)和B(x2,y2)收到的信号夹角分别是α和β，根据可以计算出待测节点N的位置坐标(x,y)。这是一种参考节点A和B自身在坐标系已经矫正的情形，如果参考点A和B方向没有校正，需要在计算时补偿方向偏差。基于测距的定位技术——三角定位法如图所示，已知ABC三点，在测量出角α、角β和角γ后，可以使用三角定位的方法计算出N点的位置N(XN,YN)。对于参考点A(x1,y1)、B(x2,y2)和夹角α，根据圆的内接四边形对角互补和弦所对的圆周角等于它所对的圆心角的性质，得到弦AB所对应的圆心角θ=2π－2α。可以由A、B和N确定一个内接圆O的圆心C1（xc1,yc1）和半径rc1，同理由A、C和N三点就可以确定O2(xc2,yc2,rc2)，由B、C和N三点就可以确定O3(xc3,yc3,rc3)。根据圆O1、O2、O3，再根据如下方程组，就可以确定点N(XN,YN)的坐标。基于测距的定位技术——三角定位法在无线传感器网络中，基于测距的定位技术往往具有很大的优势，算法比较简单，实现容易，研究人员一般从几个方面来评判这些定位技术的优劣。（1）定位精度，即测距误差，为测得的距离与实际距离的差值，一般来说采用超声波的TDOA协议最小，而采用功率衰减来判别距离的RSSI测距误差最大。（2）覆盖范围。GPS是全球定位系统，一次覆盖范围最好，其次是采用功率衰减的RSSI。而TOA和TDOA定位技术采用超声波短波，传播距离最短，因此覆盖范围最小。（3）抗干扰能力。当有干扰如电磁干扰，多径干扰等存在时，节点是否能够正常稳定工作成为测距定位技术性能的一个重要指标。（4）实现成本。测距定位技术比较五、无需测距的定位技术基于非测距的定位算法不需要知道未知节点与参考节点间的距离或角度信息，而通过网络的连通性和跳数来进行定位，相对基于测距的定位算法来说，非测距定位算法需要较高密度的参考节点，因而在参考节点数量不多的情况下定位的精度并不是很高。常见的非测距定位算法有质心算法、APIT算法、DV-Hop算法等1．基于连通性的定位连通性（Connectivity）是指两个节点是否连通。基于连通性的定位可以根据一个节点能否成功解调其他节点传来的数据包作为依据。如果节点i和节点j连通，则表示节点i能够通过感知、通信等途径，确定节点j在自己周围的一定范围内，但不知道具体的距离和方向。确切地说，节点i和节点j之间的连通性测量Qij，可以依据接收信号强度表示成0或1的二元变量模型，即：式中，Pij是节点i收到的从节点j发出的信号的强度；Pi是数据包刚好能被解调所需的最小接收信号阈值强度。无需测距的定位技术分类2．基于跳数的定位在无线传感器网络中，节点间最基本的通信方式是洪泛，所以很多节点定位机制都是采用两个节点之间的跳数（Hop）来估计节点之间的距离的。跳数原理就是对信标节点信息洪泛的过程进行跳数统计，通过统计未知节点与信标节点之间的跳数，然后根据信标节点之间的距离和跳数估算出全网每一跳的平均距离，二者相乘，即可得到两个节点之间的距离。无需测距的定位技术分类质心定位是一种粗定位算法，该算法利用网络连通度实现定位。质心定位算法的定位过程是：全网约定一段时间t为定位时间。在这段时间t内，信标节点每隔时间T向邻居节点广播一个信标信号，信号中包含自身的位置信息。未知节点记录从每个发来信号的信标节点接收到的信标信号数量。（1）质心定位算法假设这些坐标分别为（x1，y1）、（x2，y2）、…、（xk，yk），则未知节点的坐标（xest，yest）可用质心公式计算为：（1）质心定位算法APIT定位算法的理论基础是最佳三角形内点测试法PIT。PIT理论为判断某一点M是否在三角形ABC内，假如存在一个方向，沿着这个方向M点会同时远离或接近三角形ABC的三个顶点A、B、C，那么点M位于三角形ABC外；否则，点M位于三角形ABC内。（2）

APIT定位算法在图（a）中,未知节点M通过与邻居节点1交换信息，得知自身如果运动至节点1，将远离信标节点B和C，但会接近信标节点A，与邻居节点2、3、4的通信和判断过程类似，最终确定自身位于三角形ABC中；而在图（b）中，当节点4可知自身运动至邻居节点2处，将同时远离信标节点A、B、C，故判断自身不在ABC中。（2）

APIT定位算法（1）收集信息：未知节点收集邻近信标节点的信息，如位置、标识号、接收到的信号强度等，邻居节点之间交换各自接收到的信标节点的信息。（2）APIT测试：测试未知节点是否在不同的信标节点组合的三角形内部。（3）计算重叠区域：统计包含未知节点的三角形，计算所有三角形的重叠区域。（4）计算未知节点位置：计算重叠区域的质心位置，作为未知节点的位置。（2）

APIT定位算法计算步骤DV-Hop算法的基本思想是将未知节点到信标节点之间的距离用网络中节点的平均每跳距离和两节点之间跳数的乘积来表示，然后再使用三边测量法或极大似然估计法来获得未知节点的位置信息。DV-Hop算法的定位过程分为以下三个阶段：1）计算未知节点与每个信标节点的最小跳数首先使用典型的距离矢量交换协议，使网络中所有节点获得与信标节点之间的跳数。在算法开始的时候，每个信标节点都发出一个包括自己位置信息、地址和跳数值为0的位置信息包，它们周围所有跳数为1的邻居都收到这样的信息，将信标节点的位置信息和跳数记录下来，并将收到信息包的跳数值加1，再向自己的邻居节点广播。这个过程一直持续下去，直到网络中每个节点都获得每个信标节点的位置信息和相应的跳数值为止。（3）

DV-Hop定位算法2）计算未知节点与信标节点的平均每跳距离在第二阶段，每个信标节点根据第一阶段获得的其他信标节点位置和相隔跳数之后，根据下式计算网络平均每跳距离HopSize。式中，（xi，yi）、（xj，yj）是信标节点i和j的坐标，hji是信标节点i和j（i≠j）之间的跳段数。在实验中，我们发现，当总跳数大于一定的值之后，每个节点所计算的平均每跳距离基本一样。（3）

DV-Hop定位算法3）利用三边测量法计算自身位置在未知节点获得与3个或3个以上信标节点的距离后，执行三边测量定位。（辅助方法，以提高精度）该算法只需要较少的信标节点，计算和通信开销适中，不需要节点具备测距能力，是一个可扩展的算法，但是该算法对信标节点的密度要求较高，对于各向同性的密集网络，才可以得到合理的平均每跳距离，从而能够达到适当的定位精度。（3）

DV-Hop定位算法如图所示，参考节点A、B间的距离为25m，跳数为2，参考节点B、C间的距离为35m，跳数为5，则B可以计算出与A和C间的平均每跳距离为(25+35)／(2+5)=8．6m。假如参考节点B距离未知节点O的距离最近，则O将从B获得平均每跳距离，又已知O与A、B、C间的跳数分别为3、2、3，则其与A、B、C间的距离分别为：8．5×3=25．8m，8．6×2=17．2m，8．6×3=25．8m，通过这三个距离，未知节点便可以通过三边定位计算自身的坐标。DV-Hop定位算法举例无线传感器网络自身定位算法的性能对其可用性有直接的影响，如何评价定位算法是一个需要研究的问题。可从是否需要信标节点、信标节点布置方式、计算模式、定位原理和节点外加设备等角度对上述无须测距节点定位技术进行了分析和比较，如下表所示。无需测距的定位技术——分析比较六、测距方式对精度的影响Radio（VHF、UWB、CDMA、光、红外光）

一米的壁垒：更高的精度非常困难声音（声波、超声波）超声波的传播速度约300m/s，设TDOA达到的时钟精度为1ms，则测距精度30cm。1ms的时钟精度是很低的，经过优化的时间同步方案可以提供几十微秒的精度。那么使用超声波测距的方法可以达到1cm的精度。超声波的传播速度受到环境的影响，同时传播距离在几米到几十米的范围。由于声波接收的方向性，需要小心的部署。七、

典型定位系统全球和区域导航系统全球导航系统地区导航系统无线传感器网络定位系统使用TOA/TDOA方式定位的系统使用RSS方式定位的系统2013年左右世界四大全球卫星定位系统1、美国全球定位系统（GPS）。二十世纪70年代由美国陆海空三军联合研制的新一代空间卫星导航定位系统。军民两用，目前正在试验第二代卫星系统。GPS使用24颗人造卫星在离地面约2万公里的高空上，以12小时的周期环绕地球运行。在地面上的任意一点都可以同时观测到4颗以上的卫星。由于卫星的位置精确可知，通过4颗卫星发出的信号，我们可得到卫星到接收机的距离。精度达到5-10m，专用车载GPS导航仪已经广泛使用于车辆导航等应用领域。2、欧洲“伽利略”（GALILEO）系统。该系统将由30颗中高度圆轨道卫星和2个地面控制中心组成，其中27颗卫星为工作卫星，3颗为候补。卫星高度为24126公里，位于3个倾角为56度的轨道平面内。伽利略系统可以分发实时的米级定位精度信息，这是现有的卫星导航系统所没有的。3、俄罗斯“格洛纳斯”（GLONASS）系统。由24颗卫星组成，精度在10米左右，军民两用，设计2009年底服务范围拓展到全球。4、中国“北斗”系统。由5颗静止轨道卫星和30颗非静止轨道卫星组成。定位精度10米。2012年12月27日，北斗系统空间信号接口控制文件正式版正式公布，北斗导航业务正式对亚太地区提供无源定位、导航、授时服务。地区导航系统：区域范围LORAN系统

LORAN（LOngRAngeNavigation）是一种地区导航系统。基站以一定的时间间隔发送低频无线信号，船只、飞机等接收到多个信号基站的信号后，可以计算出自身所处的位置。LORAN系统发展经历LORAN-A、LORAN-C、LORAN-D和LORAN-F，最为重要的是LORAN-C系统。LORAN-C是测量脉冲和测量相位相结合的双曲线导航系统，工作频段90~110kHz，1957年开始建设，直到现在已经建成大量电台链，覆盖了北半球大部分地区。北斗

中国北斗卫星导航系统（BeiDouNavigationSatelliteSystem-"BDS"）是我国自行研制的全球卫星定位与通信系统。是继美国全球卫星定位系统（GlobalPositioningSystem-"GPS"）和俄罗斯全球卫星导航系统（Глоба́льнаянавигацио́ннаяспу́тниковаясисте́ма-"GLONASS"）之后第三个成熟的卫星导航系统。系统由空间端、地面端和用户端组成，可在全球范围内全天候、全天时为各类用户提供高精度、高可靠定位、导航、授时服务，并具短报文通信能力，已经初步具备区域导航、定位和授时能力，定位精度优于20m，授时精度优于100ns2007年4月14日4时11分，我国在西昌卫星发射中心用“长征三号甲”运载火箭，成功将第1颗北斗导航卫星送入太空。2009年4月15日零时16分，中国在西昌卫星发射中心用“长征三号丙”运载火箭，成功将第2颗北斗导航卫星送入预定轨道。2010年1月17日0时12分，我国在西昌卫星发射中心用“长征三号丙”运载火箭，成功将第3颗北斗导航卫星送入预定轨道，这标志着北斗卫星导航系统工程建设又迈出重要一步，卫星组网正按计划稳步推进。2010年6月2日晚23时53分，我国在西昌卫星发射中心用“长征三号丙”运载火箭，将第4颗北斗导航卫星成功送入太空预定轨道。2010年8月1日5时30分，我国在西昌卫星发射中心用“长征三号甲”运载火箭，成功发射第5颗北斗导航卫星。2010年11月1日0时26分，我国在西昌卫星发射中心用长征三号丙运载火箭成功将第6颗北斗导航卫星送入太空。2010年12月18日4时20分，我国在西昌卫星发射中心使用“长征三号甲”运载火箭，成功将第7颗北斗导航卫星送入太空预定转移轨道。2011年4月10日4时47分，我国在西昌卫星发射中心用“长征三号甲”运载火箭，成功将第8颗北斗导航卫星送入太空预定转移轨道。2011年