第8章无线传感器网络节点定位技术.ppt

,第八章 无线传感器网络节点定位技术,节点定位技术概述,节点定位技术研究现状与发展,节点定位技术关键问题,基于测距的定位技术,无需测距的定位技术,协作定位技术,第八章 无线传感器网络节点定位技术,无线传感器网络节点定位,：依靠网络中少量的位置已知的节点，通过邻居节点间有限的通信和某种定位机制确定网络中所有未知节点的位置。,节点定位,在实际应用中包含两种含义：,自定位,确定节点自身在系统中的位置,目标定位,确定目标节点在系统中的位置,第八章 无线传感器网络节点定位技术,节点定位技术概述,信标节点,：已知自身位置信息的节点，可通过,GPS,定位设备或手工配置、确定部署等方式预先获取位置信息，为其他节点提供参考坐标。,未知节点,：信标节点以外的节点统称为未知节点，也有文献称为盲节点。,邻居节点,：一个节点通信距离范围内的所有节点的集合。,跳数,：两个节点之间跳段的总数。,跳距,：两个节点之间各跳段的距离之和。,节点连接度,：节点可以探测发现到的邻居节点个数。,网络连接度,：所有节点的邻居个数取平均值，可反映传感器配置的密集程度,第八章 无线传感器网络节点定位技术,节点定位技术概述,一些概念,传感器网络的定位算法通常需要具备以下特点,：,自组织性,：传感器网络的节点随机部署，不依赖于全局基础设施协助定位；,健壮性,：传感器节点的硬件配置低，能量有限，可靠性较差，定位算法必须能够容忍节点失效和测距误差；,节能性,：尽可能地减少算法中计算的算法复杂度，减少节点间的通信开销，以尽量延长网络的生存周期；,分布式,：无线传感器网络通常是大规模部署网络，节点数目多，定位任务将不会是单个节点所能承担的，这就需要定位算法具有一定的分布式，把任务分派到各个节点；,可扩展性,：无线传感器网络中的节点数目可能是成千上万甚至更多，为了满足对不同规模的网络的适用性，定位算法必须具有较强的可扩展性。,第八章 无线传感器网络节点定位技术,节点定位技术概述,要求,作为一种全新的技术，无线传感器网络具有许多挑战性的研究课题，而定位就是其中之一，定位也是大多数应用的基础和前提,传感器节点的微型化和有限的电池供电能力使其在节点硬件的选择上受到很大的限制，低功耗是其最主要的设计目标。必须针对密集性，节点的计算、存储和通信等能力都有限的特定场合设计有效的,低功耗,定位算法,近十年来，无线传感器网络自身定位问题研究有了许多新颖的解决方案和思想，但是每种系统和算法都是用来解决不同的问题或支持不同的应用的，它们用于定位的物理现象、传感器设备的组成、能量需求、基础设施和时空的复杂性等许多方面,有所不同,。,对现有的,WSN,定位研究成果研究比较发现，没有一种定位方案能在有效减少通信开销、降低功耗、节省网络带宽的同时获得较高的定位精度。,而且大部分停留在仿真和实验阶段。,因此，该领域还有待更多的人提出更好的方法，以求更好地解决定位问题，使得无线传感器网络能够真正在实际生活中得到广泛的应用。,第八章 无线传感器网络节点定位技术,节点定位技术的研究现状和发展,目前，在节点定位应用中，由于受传感器节点能量有限、可靠性差、网络规模大且节点随机布放、无线模块的通信距离有限等影响，对定位算法和定位技术提出了很高的要求。一般来说我们从定位区域与精确度、实时性和能耗三个方面来衡量节点定位技术的好坏。,1,定位区域与精确度,定位区域与精确度是传统定位方法和无线传感器网络定位都具有的衡量指标，而且定位区域和精度一般都是互补存在的，定位区域越大，意味着精度越小。,2,实时性,实时性是定位技术的另外一个关键指标，实时性与位置信息的更新频率密切相关，位置信息更新频率越高，实时性越强,3,能耗,能耗是无线传感器网络独有的一个衡量指标。在无线传感器网络中，节点的电能靠电池来供应，电池是不可替换的，因此节省能量就成了无线传感器网络中一个重要的问题,。,另外，还有一些小的方面来衡量无线传感器网络定位技术的好坏，如定位技术的扩展性、鲁棒性和节点带宽的占用等,。,第八章 无线传感器网络节点定位技术,节点定位技术的研究现状和发展,利用信标节点的位置，通过测量和估计信标节点与目标节点的距离，我们就能够利用它们之间的关系很容易地算出目标节点的位置。,基于测距的定位技术涉及几何中的图形问题，已知节点的位置，求另外几个节点的位置，比较常用的方法有,：,三边定位,法,角度定位,法,角度定位需要另外测量接收信号夹角，测量出夹角后使用数学几何条件，确定节点的位置。,因为测量的信号夹角不可能很精确，所以,AOA,的精度不理想。,第八章 无线传感器网络节点定位技术,节点定位技术,基于测距的定位,1,基本思想,三边,定位,法如图所示，已知,A,、,B,、,C,三个节点的坐标分别为（,x,1,，,y,1,）、（,x,2,，,y,2,）、（,x,3,，,y,3,）。测得它们到未知节点,D,的距离分别为,d,1,、,d,2,、,d,3,。假设节点,D,的坐标为（,x,，,y,）。以,A,、,B,、,C,三点为圆心，,d,1,、,d,2,、,d,3,为半径做圆，三圆的焦点即为节点,D,的坐标。,第八章 无线传感器网络节点定位技术,基于测距的定位技术,三边定位法,那么，我们可以列出以下公式,：,将第一个方程和第二个方程同时减去第三个方程，得到结果,将其写成线性方程的形式，,AX,=,B,，其中,基于测距的定位技术,三边定位法,第八章 无线传感器网络节点定位技术,由此可以得出节点,D,的坐标为,基于测距的定位技术,三边定位法,第八章 无线传感器网络节点定位技术,三边定位技术的计算方法比较简单，在已知两点之间距离的情况下，采用单纯的数学公式就可以计算出来，节点之间距离的测量才是三边定位技术的最难点，一般来说，有三种算法可以测量两个节点之间的距离：,根据接收信号的强度来计算距离；,根据信号传播时间或者时间差来计算距离；,根据,接收信号相位差定位。,2,主要技术,1,）根据接收信号强度定位,，,信号衰减模型,如下,式,：,式中，,P,(,d,),、,P,(,d,0,),分别表示在距离基站,d,、,d,0,处的信号强度，,P,(,d,),是接收节点实际测得的信号强度,RSSI,，,P,(,d,0,),一般可以距天线,d,0,米处的路径衰减来代替,。,基于测距的定位技术,三边定位法,第八章 无线传感器网络节点定位技术,2,）根据信号传播时间测距（,TOA,）,该技术是采用信号到达时间来测量距离的，是一种基于电波传输时间的定位技术。己知信号传播速度，通过测量信号从发射机传播到多个接收机所消耗的传播时间来确定移动用户的位置,TOA,测距的基本思想是测量移动台发射信号的到达时间，并且在发射信号中要包含发射时间标记以便接收基站确定发射信号所传播的距离，该方法要求移动台和基站的时间精确同步,为了测量移动台的发射信号的到达时间，需要在每个基站处设置一个位置测量单元，为了避免定位点的模糊性，该方法至少需要三个位置测量单元或基站参与测量,基于测距的定位技术,三边定位法,第八章 无线传感器网络节点定位技术,如图所示，有,A,、,B,、,C,三个基站，因为节点间的距离测量都是一样的，这里我们就假定先测量基站,A,到目的节点的距离。假设基站,A,到目的节点,D,的距离为,d,，声波传播速度为,v,，在,T,1,时刻基站,A,发射机发射一个声波信号给目的节点,D,，,D,节点在,T,2,时刻接收到该声波信号，经过短暂的处理之后，在,T,3,时刻目的节点,D,回送一个声波测距信号给,A,节点，在,T,4,时刻,A,节点接收到该信号。由此可以得出声波信号在介质中传播的时间为,：,基于测距的定位技术,三边定位法,第八章 无线传感器网络节点定位技术,在这段时间内，声波传播的距离为,2,d,，我们就可以得到,值得注意的是，这里的,T,1,和,T,4,时刻是由节点,A,测得的，,T,2,和,T,3,时刻是由目的节点,D,测得的，由于时钟漂移、定位误差等的存在，两者的时间会有一定的时间差，但是由于无线采用双向通信的方式，两者的时间差相互抵消，对结果没有,太大,影响,基于测距的定位技术,三边定位法,第八章 无线传感器网络节点定位技术,3,）根据到达时间差测距（,Time Difference Of Arrival,，,TDOA,）,在基于到达时间差,TDOA,的定位机制中，发射节点同时发射两种不同传播速度的无线信号，接收节点根据两种信号到达的时间差以及已知这两种信号的传播速度，计算两个节点之闻的距离，再通过已有基本的定位算法计算出节点的位置。,基于测距的定位技术,三边定位法,第八章 无线传感器网络节点定位技术,如图所示，发射节点在时刻,T,0,同时发射无线射频信号和超声波信号，接收节点记录两种信号到达的时间,T,1,和,T,2,，己知无线射频信号和超声波的传播速度分别为,c,1,和,c,2,，那么我们可以知道射频信号和超声波信号传播的时间为,：,TDOA,有一些固有的缺陷需要考虑。首先利用,TDOA,进行定位要求传感节点上必须附加特殊的硬件（声波或者超声波的收发器等），这会增加传感节点的成本；其次，声波或者超声波在空气中的传输特性和一般的无线电波并不一样，空气的温度、湿度或者风速都会对声波的传输速度产生很大的影响，这就使得距离的估计可能出现较大偏差；最后，,TDOA,测速的一个很大的假设是发送节点和接收节点之间是没有障碍物阻隔的，在有障碍物的情况下会出现声波的反射、折射和衍射，此时得到的实际传输时间将变大，在这种传输时间下估算出来的距离也将出现较大的误差。,基于测距的定位技术,三边定位法,第八章 无线传感器网络节点定位技术,可以得出,即：,接收信号相位（,PDOA,）,通过测相位差，求出信号往返的传播时间，计算出往返距离,其中,，,fc,是信号频率，,是信号的波长，,是发送信号和,反射信号,的相位差。由上式可知,d,的范围是,0,。不同的距离如果相差,倍，则测量获得的相位相同。,基于测距的定位技术,三边定位法,第八章 无线传感器网络节点定位技术,常用的角度定位方法有：已知两个顶点和夹角的射线确定一点，以及已知三点和三个夹角确定一点。,1,已知两个顶点和夹角的射线确定一点,如图所示，测得参考点,A,(,x,1,y,2),和,B,(,x,2,y,2),收到的信号夹角分别是,和,，根据,可以计算出待测节点,N,的位置坐标,(,x,y,),。这是一种参考节点,A,和,B,自身在坐标系已经矫正的情形，如果参考点,A,和,B,方向没有校正，需要在计算时补偿方向偏差。,基于测距的定位技术,三角定位法,第八章 无线传感器网络节点定位技术,如图所示，在测量出角,、角,和角,后，可以使用三角定位的方法计算出,N,点的位置,(,x,y,),。,对于参考点,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,，,再根据,如下,方程组,，,就可以确定点,D(xD,yD),的坐标。,基于测距的定位技术,三角定位法,第八章 无线传感器网络节点定位技术,在无线传感器网络中，基于测距的定位技术往往具有很大的优势，算法比较简单，实现容易，研究人员一般从几个方面来评判这些定位技术的优略。,（,1,）定位精度，即测距误差，,为,测得的距离与实际距离的差值，一般来说采用超声波的,TDOA,协议最小，而采用功率衰减来判别距离的,RSSI,测距误差最大。,（,2,）覆盖范围。,GPS,是全球定位系统，一次覆盖范围最好，其次是,采用功率衰减的,RSSI,。,而,TOA,和,TDOA,定位技术采用超声波短波，传播距离最短，因此覆盖范围最小。,（,3,）抗干扰能力。当有干扰如电磁干扰，多径干扰等存在时，节点是否能够正常稳定工作成为测距定位技术性能的一个重要指标。,（,4,）实现成本。,测距定位技术比较,第八章 无线传感器网络节点定位技术,1,基于连通性的定位,连通性（,Connectivity,）是指两个节点是否连通,。,基于连通性的定位,可以根据一个节点能否成功解调其他节点传来的数据包作为依据。,如果节点,i,和节点,j,连通，则表示节点,i,能够通过感知、通信等途径，确定节点,j,在自己周围的一定范围内，但不知道具体的距离和方向。确切地说，节点,i,和节点,j,之间的连通性测量,Q,ij,，可以依据接收信号强度表示成,0,或,1,的二元变量模型，即,：,式中，,P,ij,是节点,i,收到的从节点,j,发出的信号的强度，单位是,dBm,；,P,i,是数据包刚好能被解调所需的最小接收信号阈值强度。,无需测距的定位技术,基于连通性,第八章 无线传感器网络节点定位技术,2,基于跳数的定位,在无线传感器网络中，节点间最基本的通信方式是洪泛，所以很多节点定位机制都是采用两个节点之间的跳数（,Hop,）来估计节点之间的距离的。,跳数原理就是对信标节点信息洪泛的过程进行跳数统计，通过统计未知节点与信标节点之间的跳数，然后根据信标节点之间的距离和跳数估算出全网每一跳的平均距离，二者相乘，即可得到两个节点之间的距离。,无需测距的定位技术,基于跳数,第八章 无线传感器网络节点定位技术,质心定位算法,的核心思想是：全网约定一段时间,t,为定位时间。时间,t,为,式中，,T,为发信号的时间间隔；,S,为,t,时间内要发送的消息个数；为小于,1,、大于,0,的常数。,在这段时间,t,内，信标节点每隔时间,T,向邻居节点广播一个信标信号，信号中包含自身的位置信息。未知节点记录从每个发来信号的信标节点接收到的信标信号数量。,i,时间结束后，未知节点计算与各个信标节点之间的通信成功率指标,CM,i,，即,：,无需测距的定位技术,质心定位算法,第八章 无线传感器网络节点定位技术,假设这些坐标分别为（,x,1,，,y,1,）、（,x,2,，,y,2,）、（,x,k,，,y,k,），则未知节点的坐标（,x,est,，,y,est,）,可用质心公式计算,为,：,无需测距的定位技术,质心定位算法,第八章 无线传感器网络节点定位技术,APIT,定位算法的理论基础是最佳三角形内点测试法,PIT,。,PIT,理论为判断某一点,M,是否在三角形,ABC,内，假如存在一个方向，沿着这个方向,M,点会同时远离或接近三角形,ABC,的三个顶点,A,、,B,、,C,，那么点,M,位于三角形,ABC,外；否则，点,M,位于三角形,ABC,内,。,无需测距的定位技术,APTI,定位算法,第八章 无线传感器网络节点定位技术,在图（,a,）中,位置未知节点,M,通过与邻居节点,1,交换信息，得知自身如果运动至节点,1,，将远离信标节点,B,和,C,，但会接近信标节点,4,，与邻居节点,2,、,3,、,4,的通信和判断过程类似，最终确定自身位于三角形,ABC,中；,而在图（,b,）中，当节点,4,可知自身运动至邻居节点,2,处，将同时远离信标节点,A,、,B,、,C,，故判断自身不在,ABC,中。,无需测距的定位技术,APTI,定位算法,第八章 无线传感器网络节点定位技术,APIT,定位的具体步骤如下,：,（,1,）收集信息：未知节点收集邻近信标节点的信息，如位置、标识号、接收到的信号强度等，邻居节点之间交换各自接收到的信标节点的信息。,（,2,）,APIT,测试：测试未知节点是否在不同的信标节点组合的三角形内部。,（,3,）计算重叠区域：统计包含未知节点的三角形，计算所有三角形的重叠区域。,（,4,）计算未知节点位置：计算重叠区域的质心位置，作为未知节点的位置。,无需测距的定位技术,APTI,定位算法,第八章 无线传感器网络节点定位技术,DV-Hop,算法,的基本思想是将未知节点到信标节点之间的距离用网络中节点的平均每跳距离和两节点之间跳数的乘积来表示，然后再使用三边测量法或极大似然估计法来获得未知节点的位置信息。,DV-Hop,算法的定位过程分为以下三个阶段,：,1,）计算未知节点与每个信标节点的最小跳数,首先使用典型的距离矢量交换协议，使网络中所有节点获得与信标节点之间的跳数。在算法开始的时候，每个信标节点都发出一个包括自己位置信息、地址和跳数值为,0,的位置信息包，它们周围所有跳数为,1,的邻居都收到这样的信息，将信标节点的位置信息和跳数记录下来，并将收到信息包的跳数值加,1,，再向自己的邻居节点广播。这个过程一直持续下去，直到网络中每个节点都获得每个信标节点的位置信息和相应的跳数值为止。,无需测距的定位技术,DV-Hop,定位算法,第八章 无线传感器网络节点定位技术,2,）计算未知节点与信标节点的平均每跳距离,在第二阶段，每个信标节点根据第一阶段获得的其他信标节点位置和相隔跳数之后，根据,下,式计算网络平均每跳距离,HopSize,。,式中，（,x,i,，,x,j,）、（,y,i,，,y,j,）是信标节点,i,和,j,的坐标，,h,ji,是信标节点,i,和,j,（,ij,）之间的跳段数。在实验中，我们发现，当总跳数大于一定的值之后，每个节点所计算的平均每跳距离基本一样。,无需测距的定位技术,DV-Hop,定位算法,第八章 无线传感器网络节点定位技术,3,）利用三边测量法计算自身位置,在未知节点获得与,3,个或,3,个以上信标节点的距离后，执行三边测量定位。,该算法只需要较少的信标节点，计算和通信开销适中，不需要节点具备测距能力，是一个可扩展的算法，但是该算法对信标节点的密度要求较高，对于各向同性的密集网络，才可以得到合理的平均每跳距离，从而能够达到适当的定位精度。,无需测距的定位技术,DV-Hop,定位算法,第八章 无线传感器网络节点定位技术,将节点间点到点的通信连接视为节点位置的几何约束，把整个网络模型化为一个凸集，从而将节点定位问题转化为凸约束优化问题，然后使用线性矩阵不等式、半判定规划或线性规划方法得到一个全局优化的解决方案，确定节点位置。同时也给出了一种计算未知节点有可能存在的矩形空间的方法。,无需测距的定位技术,凸优化方法,第八章 无线传感器网络节点定位技术,无线传感器网络自身定位算法的性能对其可用性有直接的影响，如何评价定位算法是一个需要研究的问题,。可,从是否需要信标节点、信标节点布置方式、计算模式、定位原理和节点外加设备等角度对上述无须测距节点定位技术进行了分析和比较，如,下,表所示。,无需测距的定位技术,分析比较,第八章 无线传感器网络节点定位技术,刚性体理论概述,刚性，即在不考虑物质特性的理想条件下任何两个连接点之间的欧氏距离不随其运动状态改变的特性。普通刚性理论是一种定义在光滑轨道上的运动特性。当图沿着光滑轨道,运动时，任意两个节点,q,i,(,t,),和,q,j,(,t,),间的欧氏距离不随时间函数变化，则,q,i,(,t,),和,q,j,(,t,),具有普通刚性特性。用数学描述，即当几何图沿着轨道,q,(0,),做刚性运动时，则任意时刻的节点集,q,i,(,t,),和,q,j,(,t,),是全等的。可用数学公式表示为,式中，,R,(,q,),是一个,m,n,型的矩阵，称为刚体矩阵。,协作定位技术,第八章 无线传感器网络节点定位技术,定理,1,：在二维的平面空间中，图形,G,=(,v,L,),拥有,n,个顶点，如果,L,（,L,为图形的边集）存在一个有,2,n,3,条边的子集,E,，且对任意一个非空边集,E,中有,n,个顶点且,E,中元素数量不超过,2,n,3,，那么图形,G,=(,V,L,),在二维平面空间中具有普通刚性。,第八章 无线传感器网络节点定位技术,定理,2,：在一个二维平面空间中图,G,内包含,n,4,个定点，如果图,G,中某个点具有,3-,连接（,3-Connected,）结构且该图形是冗余刚性的，那么图,G,就是全局刚性结构。,协作定位技术,协作体的定义,将刚性理论引入网络结构拓扑中是无线传感器网络中基于协作模式节点定位的第一步，用图形结构的方式描述网络拓扑结构。,定义,1,：在网络图形,G,N,=(,V,E,N,),中，存在节点,u,和,v,G,(,V,),，,R,(,u,v,),或,R,(,v,u,),表示节点,u,和,v,之间的几何距离，设,r,是网络中节点的最大无限传输距离，当,R,(,u,v,),r,时，,u,和,v,之间可以无线连通，则称,u,和,v,为直接相邻节点或邻居节点。,定理,3,22,：在二维空间的无线传感器网络,N,中的节点以随机的形式分布，当网络中存在,m,3,个非共线导标节点，且网络,N,所对应的结构,G,N,=(,V,E,N,),是全局刚性，则网络,N,中的节点可以被定位。,协作定位技术,第八章 无线传感器网络节点定位技术,定义,2,：无线传感器网络中的一组连通的节点,C,组成的局部网络拓扑,N,，若,N,中所对应节点之间的连接特性及导标节点的物理位置的约束可以唯一确定,N,中位置节点的位置信息，那么，称局部网络拓扑,N,为定位协作体,定义,3,：（单元定位协作体）对某一定为协作体,，若不存在定位协作体,满足,，则称定位协作体,L,u,为单元定位协作体。包含,n,（,n,=1,2,3,）个两两相连的未知节点及,m,（,m,=3,）个导标节点，且不含任何冗余边的,LCS,成为最简单的定位协作体或最简定位协作体，如图,8.12,所示。,协作定位技术,第八章 无线传感器网络节点定位技术,定理,4,：,设,L,1,和,L,2,为两个定位协作体，它们所对应的节点集分别为,V,1,和,V,2,，且,两个集合没有共同元素,，若存在一个导标节点,v,1b,L,1,及,v,2b,L,3,且,v,1b,与,L,2,中未知节点的连接度为,1,，去掉导标节点,v,1b,和,v,2b,，并合并,v,1b,和,v,2b,与未知节点的连接形成新的连接,l,b,，使,L,1,和,L,2,合并构建成新网络拓扑结构,L,，则,L,为定位协作体，如图所示。,定理,5,：设一个定位协作体,L,，将,L,中的所有节点看做导标节点，若,m,个不属于,L,的位置节点组成的集合,S,u,与,L,中的部分或全部节点元素构成的网络拓扑可以形成新的定位协作体，则位置节点集,S,u,L,所形成的拓扑结构为定位协作体。,协作定位技术,第八章 无线传感器网络节点定位技术,将无线传感器网络中节点构建定位协作体其过程描述如下,：,（,1,）初始化阶段，无线传感器网络中一共有节总数为,n,，其中有,m,个导标节点，导标节点的坐标集,g,=(,x,i,y,i,),，,i,=1,2,m,，导标节点比例为,m,/,n,，有,n,m,个位置节点。初始化位置节点的邻居导标节点集为空集。,（,2,）导标节点向四周广播发送自己的位置信息，位置节点与其邻居导标连通，采集与该位置节点无线链接的导标节点个数为,n,ib,，这些导标节点集的坐标为,D,i,(,u,v,),，即该未知节点与,n,ib,个导标节点单跳连通。,（,3,）未知节点采集与之邻近位置节点的导标连通信息，这些邻近位置节点的导标连通个数为,n,jb,，坐标集为,D,u,(,u,v,),，即该位置节点与,n,jb,个导标两跳连通。但未知节点与周围导标节点的连通情况可用连通公式表示为,协作定位技术,第八章 无线传感器网络节点定位技术,当,，该位置节点与周围邻居导标的连通数目小于,3,，根据定理,3,可知，该节点不具备构建全局刚性图的连通条件，即该节点不能与网络导标节点构建定位协作体，因此不能定位。,当,时，该位置节点可与周围导标节点通过两跳连通构建定位协作体，即该未知节点与网络节点可构成最简定位协作体，该位置节点可能被定位。,协作定位技术,第八章 无线传感器网络节点定位技术,