资源描述
单击此处编辑母版标题样式,第,4,章 定位技术,第,4,章 定位技术,4.1,定位技术简介,4.2,基于距离的定位,4.3,与距离无关的定位算法,4.1,定位技术简介,4.1.1,定位技术的概念、常见算法和分类,1.,无线传感器网络定位技术概念,在传感器网络节点定位技术中，根据节点是否已知自身的位置，把传感器节点分为信标节点,(beacon node),和未知节点,(unknown node),。信标节点在网络节点中所占的比例很小，可以通过携带,GPS,定位设备等手段获得自身的精确位置。信标节点是未知节点定位的参考点。除了信标节点以外，其他传感器节点就是未知节点，它们通过信标节点的位置信息,来确定自身位置。在如图,4-1,所示的传感网络中，,M,代表信标节点，,S,代表未知节点。,S,节点通过与邻近,M,节点或已经得到位置信息的,S,节点之间的通信，根据一定的定位算法计算出自身的位置。,图,4-1,传感器网络中信标节点和未知节点,2,节点位置计算的常见方法,传感器节点定位过程中，未知节点在获得对于邻近信标节点的距离，或者获得邻近的信标节点与未知节点之间的相对角度后，通常使用下列方法计算自己的位置。,1),三边测量定位法,(,trilateration,),三边测量定位法是一种常见的目标定位方法，其理论依据是在二维空间中，当一个节点获得三个或者三个以上参考节点的距离时，就可以确定该节点的坐标。三边测量技术建立在几何学的基础上，它用多个点与目标之间的距离来计算目标的坐标位置。如图,4-2,所示，在二维空间中，最少需要得到三个参考点的距离才能唯一地确定一点的坐标。假设目标节点的坐标为,(,x,，,y,),，三个信标节点,A,、,B,、,C,的坐标分别为,(,x,1,，,y,1,),、,(,x,2,，,y,2,),、,(,x,3,，,y,3,),，以及它们到未知目标节点的距离分别为,1,、,2,、,3,，则根据二维空间距离计算公式，可以建立如下方程组：,图,4-2,三边测量定位法,由公式,(4-1),即可解出节点,D,的坐标,(,x,，,y,),：,(4-1),2),三角测量法,(triangulation),三角测量法的原理如图,4-3,所示，已知,A,、,B,、,C,三个节点的坐标分别为,(,x,1,，,y,1,),、,(,x,2,，,y,2,),、,(,x,3,，,y,3,),，节点,D,到,A,、,B,、,C,的角度分别为,ADB,、,ADC,、,BDC,、假设节点,D,的坐标为,(,x,，,y,),。对于节点,A,、,C,和,ADC,，确定圆心为,O,1,(,x,O,1,，,y,O,1,),、半径为,r,1,的圆，则,(4-2),图,4-3,三角测量法原理图,由公式,(4-2),能够确定圆心,O,1,的坐标和半径,r,1,。同理对,A,、,B,、,ADB,和,B,、,C,、,BDC,，也能够确定相应的圆心,O,2,(,x,O,2,，,y,O,2,),、,O,3,(,x,O,3,，,y,O,3,),，半径,r,2,、,r,3,。最后利用三边测量法，由,O,1,、,O,2,、,O,3,确定,D,节点的坐标,(,x,，,y,),。,3),极大似然估计法,(maximum likelihood estimation),如图,4-4,所示，已知获得信标节点,1,、,2,、,3,n,的坐标分别为,(,x,1,，,y,1,),、,(,x,2,，,y,2,),、,(,x,3,，,y,3,)(,x,n,，,y,n,),，它们到待定位节点,D,的距离分别为,1,，,2,，,3,n,，假设,D,的坐标为,(,x,，,y,),，则存在公式：,(4-3),图,4-4,极大似然估计法,公式,(4-3),可表示为线性方程式,AX,=,b,，其中,使用标准的最小均方差估计方法可以得到节点,D,的坐标为,4.1.2,定位算法分类,在传感器网络中，根据定位过程中是否测量实际节点间的距离，把定位算法分为基于距离的,(range-based),定位算法和与距离无关的,(range-free),定位算法，前者需要测量相邻节点间的绝对距离或方位，并利用节点间的实际距离来计算未知节点的位置；后者无需测量节点间的绝对距离或方位，而是利用节点间估计的距离计算节点位置。,4.2,基于距离的定位,基于距离的定位机制,(range-based),是通过测量相邻节点间的实际距离或方位进行定位的。具体过程通常分为三个阶段：第一个阶段是测距阶段，首先测量未知节点到邻居节点的距离或角度，然后进一步计算到邻近信标节点的距离或方位，在计算到邻近信标节点的距离时，可以计算未知节点到信标节点的直线距离，也可以用二者之间的跳断距离作为直线距离的近似；第二个阶段是定位阶段，计算出未知节点到达三个或三个以上信标节点的距离或角度后，利用三边测量法、三角测量法或极大似然估计法计算未知节点的坐标；第三个阶段是修正阶段，对求得的节点的坐标进行求精，提高定位精度，减少误差。,基于距离的定位算法通过获取电波信号的参数，如接收信号强度,(RSSI),、信号传输时间,(TOA),、信号到达时间差,(TDOA),、信号到达角度,(AOA),等，再通过合适的定位算法来计算节点或目标的位置。,4.2.1,基于,TOA,的定位,在,TOA,方法中，主要利用信号传输所消耗的时间预测节点和参考点之间的距离。系统通常使用慢速信号,(,如超声波,),测量信号到达的时间，原理如图,4-5,所示。超声信号从发送节点传递到接收节点，而后接收节点再发送另一个信号给发送节点作为响应。通过双方的“握手”，发送节点即能从节点的周期延迟中推断出距离为,式中，,V,代表超声波信号的传递速度。这种测量方法的误差主要来自信号的处理时间,(,如计算延迟以及在接收端的位置延迟,T,2,-,T,1,),。基于,TOA,的定位精度高，但要求节点间保持精确的时间同步，因此对传感器的硬件和功能提出了较高的要求。,图,4-5 TOA,测量原理图,4.2.2,基于,TDOA,的定位,TDOA,测距技术被广泛应用在,WSN,定位方案中。一般是在节点上安装超声波收发器和,RF,收发器。测距时，在发射端两种收发器同时发射信号，利用声波与电磁波在空气中传播速度的巨大差异，在接收端通过记录两种不同信号到达时间的差异，基于已知信号传播速度，则可以直接把时间转化为距离。该技术的测距精度较,RSSI,高，可达到厘米级，但受限于超声波传播距离有限和非视距,(NLOS),问题对超声波信号的传播影响。,如图,4-6,所示，发射节点同时发射无线射频信号和超声波信号，接收节点记录两种信号分别到达的时间为,T,1,和,T,2,，已知无线射频信号和超声波的传播速度分别为,c,1,和,c,2,，那么两点之间的距离为,(,T,2,-,T,1,),S,，其中,S,=,c,1,c,2,/(,c,1,-,c,2,),。在实际应用中，,TDOA,的测距方法可以达到较高的精度。,图,4-6 TDOA,定位原理图,4.2.3,基于,AOA,的定位,另外一种方法是利用角度估算代替距离估计。估算邻居节点发送信号方向的技术，可通过天线阵列或多个接收器结合来实现。信标节点发出较窄的旋转波束，波束的旋转度数是常数，并且对所有节点都是已知的。于是节点可以测量每个波束的到达时间，并计算两个依次到达信号的时间差。如图,4-7,所示，接收节点通过麦克风列阵，通知发射节点信号的到达方向。下面以每个节点配有两个接收机为例，简单阐述,AOA,测定方位角和定位的实现过程。,图,4-7 AOA,定位图,1.,相邻节点之间方位角的测定,如图,4-8,所示，节点,A,的两个接收机,R,1,、,R,2,间的距离是,L,，接收机连线中点的位置代表节点,A,的位置。将两个接收机连线的中垂线作为节点,A,的轴线，该轴线作为确定邻居节点方位角度的基准线。在图,4-9,中，节点,A,、,B,、,C,互为邻居节点，节点,A,的轴线方向为节点,A,处箭头所示方向，节点,B,相对于节点,A,的方位角是，节点,C,相对于节点,A,的方位角是。在图,4-9,中，节点,A,的两个接收机收到节点,B,的信号后，利用,TOA,技术测量出,R,1,、,R,2,到节点,B,的距离,x,1,，,x,2,，再根据几何关系，计算节点,B,到节点,A,的方位角，它对应图,4-8,中的方位角，实际中利用天线阵列可获得精确的角度信息。同样再获得方位角，最后得到。,图,4-8,节点结构图,图,4-9,方位角图,2.,相对信标节点的方位角测量,在图,4-10,中，,L,节点是信标节点，,A,、,B,、,C,节点互为邻居。计算出,A,、,B,、,C,三点之间的相对方位信息。假定已经测得信标节点,L,、节点,B,和节点,C,之间的方位信息，只需要确定信标节点,L,相对于节点,A,的方位即可。,图,4-10,方位角测量,3.,利用方位信息计算节点的位置,如图,4-11,所示，节点,D,是未知节点，在节点,D,计算出,n,(,n,3),个信标节点相对于自己的方位角度后，从个信标节点中任选三个信标节点,A,、,B,、,C,。的值是信标节点,A,和,B,相对于节点,D,的方位角度之差，同理可计算出和的角度值，这样就确定了信标节点,A,、,B,、,C,和节点,D,之间的角度。,当信标节点数目,n,为,3,时，利用三角测量算法直接计算节点,D,坐标。当信标节点数目大于,3,时，将三角测量算法转化为极大似然算法来提高定位精度，如图,4-12,所示，对于节点,A,、,B,、,D,，能够确定以点,O,为圆心，以,OB,或,OA,为半径的圆，圆上的所有点都满足的关系，将点,O,作为新的信标节点，,OD,长度就是圆的半径。因此，从,n,个信标节点中任选两个节点，可以将问题转化为有个信标节点的极大似然估计算法，从而确定,D,点坐标。,AOA,定位不仅能够确定节点的坐标，还能提供节点的方位信息。但,AOA,测距技术易受外界环境影响，且,AOA,需要额外硬件，在硬件尺寸和功耗上不适用于大规模的传感器网络。,图,4-11,三角测量法图示,图,4-12,三角测量法转化为三边测量法,4.2.4,基于,RSSI,的定位,RSSI,随着通信距离的变化而变化，通常是节点间距离越远，,RSSI,值相对越低。一般来说，利用,RSSI,来估计节点之间的距离需要使用的方法是：已知发射节点的发射功率，在接收节点处测量接收功率；计算无线电波的传播损耗，再使用理论或经验的无线电波传播模型将传播损耗转化为距离。常用的无线信号传播模型为其中，,P,r,dB,(,d,),是以,d,0,为参考点的信号的接收功率；,是路径衰减常数；,X, dB,是以,2,为方差的正态分布，为了说明障碍物的影响。,(4-4),公式,(4-4),是无线信号较常使用的传播损耗模型，如果参考点的距离,d,0,和接收功率已知，就可以通过该公式计算出距离,d,。理论上，如果环境条件已知，路径衰减常数为常量，接收信号强度就可以应用于距离估计。然而，不一致的衰减关系影响了距离估计的质量，这就是,RSSI-RF,信号测距技术的误差经常为米级的原因。在某些特定的环境条件下，基于,RSSI,的测距技术可以达到较好的精度，可以适当地补偿,RSSI,造成的误差。虽然在实验环境中,RSSI,表现出良好的特性，但是在现实环境中，温度、障碍物、传播模式等条件往往都是变化的，这使得该技术在实际应用中仍然存在困难。,4.3,与距离无关的定位算法,尽管基于距离的定位能够实现精确定位，但是对无线传感器节点的硬件要求很高，因而使得硬件的成本增加，能耗增高。基于这些原因，人们提出了距离无关的定位技术。距离无关的定位技术无需测量节点间的绝对距离或方位，降低了对节点硬件的要求，但定位的误差也相应有所增加。,目前提出了两类主要的与距离无关的定位方法：一类方法是先对未知节点和信标节点之间的距离进行估计，然后利用三边测量法或极大似然估计法进行定位；另一类方法是通过邻居节点和信标节点确定包含未知节点的区域，然后把这个区域的质心作为未知节点的坐标。与距离无关的定位方法精度低，但能满足大多数应用的要求。与距离无关的定位算法主要有质心定位算法、,DV-Hop,算法、,APIT,算法、凸规划定位算法等，下面分别介绍这几种算法。,4.3.1,质心定位算法,质心定位算法是南加州大学的,Nirupama,Bulusu,等学者提出的一种仅基于网络连通性的室外定位算法。如图,4-13,所示，该算法的核心思想是：传感器节点以所有在其通信范围内的信标节点的几何质心作为自己的估计位置。具体的算法过程为：信标节点每隔一段时间向邻居节点广播一个信标信号，该信号中包含节点自身的,ID,和位置信息；当传感器节点在一段侦听时间内接收到来自信标节点的信标信号数量超过某一个预设门限后，该节点认为与此信标节点连通，并将自身位置确定为所有与之连通的信标节点所组成的多边形的质心；当传感器节点接收到所有与之连通的信标节点的,图,4-13,质心定位法示意图,位置信息后，就可以根据由这些信标节点所组成的多边形的顶点坐标来估算自己的位置了。假设这些坐标分别为,(,x,1,，,y,1,),、,(,x,2,，,y,2,),、,、,(,x,k,，,y,k,),，则可根据下式计算出传感器节点的坐标：另外，该算法仅能实现粗粒度定位，需要较高的信标节点密度。但它实现简单，完全基于网络的连通性，无需信标节点和传感器节点间的协调，可以满足那些对位置精度要求不太苛刻的应用。,4.3.2 DV-Hop,算法,DV-Hop,算法的定位过程可以分为以下三个阶段：,(1),计算未知节点与每个信标节点的最小跳数。首先使用典型的距离矢量交换协议，使网络中的所有节点获得距离信标节点的跳数,(distance in hops),。信标节点向邻居节点广播自身位置的信息分组，其中包括跳段数和初始化,0,。接收节点记录具有到每个信标节点的最小跳数，忽略来自同一个信标节点的较大跳段数，然后将跳段数加,1,，并转发给邻居节点，通过这个方法，可以使网络中的每个节点获得每个信标节点的最小跳数。,(2),计算未知节点与信标节点的实际跳段距离。,每个信标节点根据第一个阶段中记录的其他信标节点的位置信息和相距跳段数，利用公式,(4-6),估算平均每跳的实际距离其中，,(,x,i,，,y,i,),，,(,x,j,，,y,j,),是信标节点,i,、,j,的坐标，,h,j,是信标节点,i,与,j,(,j,i,),之间的跳段数。,(4-6),然后，信标节点将计算的每跳平均距离用带有生存期字段的分组广播到网络中，未知节点只记录接收到的第一个每跳平均距离，并转发给邻居节点。这个策略保证了绝大多数节点仅从最近的信标节点接收平均每跳距离值。未知节点接收到每跳平均距离后，根据记录的跳段数,(hops),来估算它到信标节点的距离,D,i,=,hops,Hopsize,ave,(3),利用三边测量法或者极大似然估计法计算自身的位置。估算出未知节点到信标节点的距离后，就可以用三边测量法或者极大似然估计法计算出未知节点的自身坐标。举例说明：如图,4-14,所示，已知锚节点,L,1,与,L,2,、,L,3,之间的距离和跳数。由,L,2,计算得到平均每跳距离,(40+75)/(2+5)=16.42,。假设,A,从,L,2,获取平均每跳距离，则它与三个节点之间的距离分别为,L,1,：,316.42,，,L,2,：,216.42,，,L,3,：,316.42,，然后使用三边测量法确定节点,A,的位置。,图,4-14,计算平均每跳距离,DV-Hop,算法在网络平均连通度为,10,，信标节点比例为,10%,的各向同性网络中平均定位精度大约为,33%,。其缺点是仅在各向同性的密集网络中，校正值才能合理地估算平均每跳距离。从上面的描述中可以看出，此方法利用平均每跳距离计算实际距离，对节点的硬件要求低，实现简单，然而存在一定的误差。练习：如图,4-15,所示，在,100 m100 m,的矩形区域中，随机布置,100,个传感器节点，通信半径为,15 m,，利用,DV-Hop,定位算法进行未知节点定位。,图,4-15 DV-Hop,定位仿真图,4.3.3 APIT,算法,T.He,等人提出的,APIT(Approximate,Point-In-triangulation Test),算法的基本思想是三角形覆盖逼近，传感器节点处于多个三角形覆盖区域的重叠部分中。传感器节点从所有邻居信标节点集合中选择三个节点，测试它是否位于由这三个节点组成的三角形的内部，重复这一过程直到穷举所有的三元组合或者达到期望的精度，然后以所有覆盖传感器节点的三角形的重叠部分的质心作为其位置并计算该位置。如图,4-16,所示，阴影部分区域是包含传感器节点的所有三角形的重叠区域，黑色圆点表示的质心位置作为传感器节点的位置。,图,4-16 APIT,算法示意图,算法的理论基础是最佳三角形内点测试法,(Perfect point-In-triangulation Test,，,PIT),，为了在静态网络中执行,PIT,测试，,APIT(Approximate,PIT Test),测试应运而生：假如节点,M,的邻居节点没有同时远离或靠近三个信标节点,A,、,B,、,C,，那么节点,M,就在节点,ABC,内；否则，节点,M,在,ABC,外。,APIT,算法利用无线传感器网络较高的节点密度来模拟节点移动，利用无线信号的传播特性来判断节点是否远离或靠近信标节点，通过邻居节点间的信息交换，仿效,PTT,测试的节点移动。,如图,4-17(a),所示，节点,M,通过与邻居节点,1,交换信息，得知自身如果运动至节点,1,，将远离信标节点,B,和,C,，但会接近信标节点,A,，与邻居节点,2,、,3,、,4,的通信和判断过程类似，最终确定自身位于,ABC,中；而在图,4-17(b),中，节点,M,可知假如自身运动至邻居节点,3,处，将同时远离信标节点,A,、,B,、,C,，故判断自身不在,ABC,中。在,APIT,算法中，一个目标节点任选三个相邻信标节点，测试自己是否位于它们所组成的三角形中，使用不同信标节点组合重复测试，直到穷尽所有组合或达到所需定位精度。,图,4-17 APIT,测试示意图,APIT,测试结束后，,APIT,用,grid SCAN,算法进行重叠区域的计算，如图,4-18,所示。在此算法中，网格阵列代表节点可能存在的最大区域。每个网格的初值都为,0,。如果判断出节点在三角形内，相应的三角形所在的网格区域的值加,1,；同样，如果判断出节点在三角形外，相应的三角形所在的网格区域的值减,1,。计算出所有的三角形区域的值后，找出具有最大值的重叠区域,(,图,4-18,中值为,2,的区域,),，最后计算出这个重叠区域的质心即为该节点的位置。,图,4-18 grid SCAN,示意图,在无线信号传播模式不规则和传感器节点随机部署的情况下，,APIT,算法的定位精度高、性能稳定，测试错误概率相对较小,(,最坏情况下为,14%),，平均定位误差小于节点无线射程的,40%,。但因细分定位区域和传感器节点必须与信标节点相邻的需求，该算法要求较高的信标节点密度。,APIT,定位具体步骤如下：,(1),收集信息。未知节点收集邻近信标节点的信息，如未知、标志号、接收到的信号强度等，邻居节点之间交换各自收到的信标节点的信息。,(2) APIT,测试。测试未知节点是否在不同的信标节点组合成的三角形内部。,(3),计算重叠区域。统计包含未知节点的三角形，计算所有三角形的重叠区域。,(4),计算未知节点位置。计算重叠区域的质心位置，作为未知节点的位置。在无线信号传播模式不规则和传感器节点随机部署的情况下，,APIT,算法的定位精度高，性能稳定，但,APIT,测试对网络的连通性提出了较高的要求。相对于计算简单的质心定位算法，,APIT,算法精度高，对信标节点的分布要求低。,练习：在,100 m100 m,的矩形区域中，随机布置,100,个传感器节点，通信半径为,15 m,。考虑当网络中锚节点数分别为,30,、,40,、,50,、,60,、,70,、,80,个时，定位的误差率和覆盖率的变化情况。图,4-19,为定位覆盖率随锚节点数变化的情况，这里采用蒙特卡洛法求定位覆盖率。在锚节点为,30,个时，,APIT,算法的定位覆盖率只达到了,10%,左右，说明此时只有很少一部分节点可以得到自己的位置信息，算法的有效性非常低，这是由,APIT,算法对网络密集性和锚节点分布均匀性的要求导致的。,APIT,算法只有在网络布置密集，且锚节点分布均匀的情况下，算法才能有效执行。而改进算法能够以虚拟锚节点的方式不断升级锚节点的数量，因此即使在锚节点数量很少的情况下，依然能够保持,50%,以上的定位覆盖率。,图,4-19,定位覆盖率,定位算法的有效性不能仅通过定位覆盖率来体现，另外一个重要指标是定位的误差率。定位误差率利用公式,(4-7),求得。其中，,(,x,，,y,),为节点的真实位置，,(,x,est,，,y,est,),为节点的估计位置，为未知节点个数，,R,为节点通信半径。定位误差率随锚节点变化曲线仿真图如图,4-20,所示。由定位误差率曲线可以看出来，在锚节点数较少的情况下，改进的算法误差率明显较小。,(4-7),图,4-20,定位误差率,4.3.4,凸规划定位算法,加州大学伯克利分校的,Doherty,等人将节点间点到点的通信连接视为节点位置的几何约束，把整个网络模型化为一个凸集，从而将节点定位问题转化为凸约束优化问题，然后使用半定规划和线性规划方法得到一个全局优化的解决方案，确定节点位置，同时也给出了一种计算传感器节点有可能存在的矩形空间的方法。如图,4-21,所示，根据传感器节点与信标节点之间的通信连接和节点无线通信射程，可以估算出节点可能存在的区域,(,图中阴影部分,),，并得到相应矩形区域，然后以矩形的质心作为传感器节点的位置。,图,4-21,凸规划定位算法示意图,凸规划是一种集中式定位算法，定位误差约等于节点的无线射程,(,信标节点比例为,10%),。为了高效工作，信标节点需要被部署在网络的边缘，否则外围节点的位置估算会向网络中心偏移。,
展开阅读全文