11.1无线传感器网络节点定位和跟踪技术

无线传感器网络节点定位华北电力大学电气与电子工程学院通信技术研究所唐良瑞教授通信新技术专题讲座1无线传感器网络（WirelessSensorNetwork，WSN）就是由部署在监测区域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳自组织网络。无线传感器网络2无线传感器网络主要用来检测网络部署区域中各种环境特性，比如温度、湿度、光照、声音、磁场强度等等，但对这些传感数据在不知道响应的位置信息的情况下，往往是没有意义的。传感器节点通常是用飞机等工具随机地部署到监测区域中的，因此无法预先确定节点部署后的位置，只能在部署完成后采用一定的方法进行定位。目前使用最广泛的全球定位系统（GlobalPositioningSystem,GPS），由于其在价格、功耗、适用范围以及体积等各方面的制约，使其很难完全应用于大规模无线传感器网络。无线传感器网络节点定位由此，如何确定无线传感器网络中节点的位置信息称之为“节点定位”成为了必须解决的关键问题之一。3所谓节点定位（nodelocalization）,即通过一定的技术、方法和手段获得无线传感器网络中节点的绝对（相对于地理经纬度）或相对位置信息的过程。由于节点硬件配置低，能量、计算、存储和通信能力有限，因此对节点定位提出了较大的挑战。无线传感器网络的特点使得定位算法一般从以下几个方面评估：无线传感器网络节点定位4无线传感器网络自身定位系统和算法的性能评价(1)定位精度定位技术首要的评价指标就是定位精度，一般用误差值与节点无线射程的比例表示。例如：定位精度为20%表示定位误差相当于节点无线射程的20%。也有部分定位系统将二维网络部署区域划分为网格，其定位结果的精度也就是网格的大小，如微软的RADAR。(2)锚节点密度锚节点定位通常依赖人工部署或GPS实现。人工部署锚节点的方式不仅受网络部署环境的限制，还严重制约了网络和应用的可扩展性。而使用GPS定位,锚节点的费用会比普通节点高两个数量级，这意味着即使仅有10%的节点是锚节点，整个网络的价格也将增加10倍。因此，锚节点密度也是评价定位系统和算法性能的重要指标之一。5(3)节点密度在WSN中，节点密度增大不仅意味着网络部署费用的增加，而且会因为节点间的通信冲突问题带来有限带宽的阻塞。节点密度通常以网络的平均连通度来表示。许多定位算法的精度受节点密度的影响，如DV-Hop算法仅可在节点密集部署的情况下合理地估算节点位置。(4)功耗功耗是对WSN的设计和实现影响最大的因素之一。由于传感器节点电池能量有限，因此在保证定位精度的前提下，与功耗密切相关的定位所需的计算量、通信开销、存储开销、时间复杂性是一组关键性指标.无线传感器网络自身定位系统和算法的性能评价6(5)代价定位系统或算法的代价可从几个不同方面来评价。时间代价包括一个系统的安装时间、配置时间、定位所需时间。空间代价包括一个定位系统或算法所需的基础设施和网络节点的数量、硬件尺寸等。资金代价则包括实现一种定位系统或算法的基础设施、节点设备的总费用。(6)容错性和自适应性定位系统和算法的软、硬件必须具有很强的容错性和自适应性，能够通过自动调整或重构纠正错误、适应环境、减小各种误差的影响，以提高定位精度。无线传感器网络自身定位系统和算法的性能评价7物理定位与符号定位(physicalpositionandsymboliclocation)绝对定位与相对定位(absoluteversusrelative)紧密耦合与松散耦合(tightlycoupledversuslooselycoupled)集中式计算与分布式计算(centralizedcomputationversusdistributedcomputation)基于测距的定位和非基于测距的定位算法(range-basedversusrange-free)粗粒度与细粒度(fine-grainedlocalizationversuscoarse-grainedlocalization)无线传感器网络自身定位系统和算法的分类8根据定位算法是否需要通过物理测量来获得节点之间的距离（角度）信息：基于测距的定位算法是利用测量得到的距离或角度信息来进行位置计算。非基于测距的定位算法一般利用节点的连通性和多跳路由信息交换等方法来估计节点间的距离或角度，并完成位置估计。基于测距的定位和非基于测距的定位算法9基于测距的定位技术是通过测量相邻节点间的实际距离或方位进行定位，通常分为三个步骤:（1）测距未知节点首先测量到邻近节点的距离或角度，然后计算到邻近信标节点的距离或方位；（2）定位未知节点在计算出到达三个或者三个以上信标节点的距离或角度后，利用三边测量(trilateration)法，三角测量(triangulation)法或者极大似然估计(multilateration)法等计算节点的坐标;在使用测距信息进行定位时，同时可采用多次测量和循环定位求精等算法来减小测距误差对定位的影响；（3）修正对求得的节点坐标进行修正，以减少误差。基于测距的定位技术10常见测距/向方法到达时间(TimeofArrival,TOA)到达时间差(TimeDifferenceofArrival,DOA)到达角(AngleofArrival,AOA)接收信号强度指示(ReceivedSignalStrengthIndication,RSSI)几种常见测距/向方法11常见测距/向方法T0T1发射机接收机已知信号的传播速度，根据信号的传播时间来计算节点间的距离。基于TOA的定位精度较高，但要求节点间保持精确的时间同步，因此对传感器节点的硬件和功耗提出了较高的要求。VTTd*)(01到达时间(TimeofArrival，TOA)TOA12常见测距/向方法发送者同时发送两种不同的信号，一般采用射频信号和超声波信号，根据接收到这两种信号的时间差和它们的速度把时间差转化为距离。TDOA的测量精度一般要优于TOA，在无线传感器网络的定位研究中使用比较多；只是它要求节点具备感知至少两种不同信号的能力，而且超声波信号的传播距离非常有限。到达时间差(TimeDifferenceofArrival,TDOA)T0T3发射机接收机T2T1TDOAUSRFUSRFVVVVTTTTd**)]()[(021313AOA测距技术需要天线阵列或是多个超声波接收器结合来实现，这样就需要额外的硬件来满足要求；而且AOA技术容易受到外界环境影响，如噪声、NLOS问题等都会对测量结果产生不同的影响。常见测距/向方法到达角(AngleofArrival,AOA)14已知发射功率，在接收节点测量接收功率，计算传播损耗，使用理论或经验的信号传播模型将传播损耗转化为距离。该技术主要使用RF信号。节点间的RSSI值使用经验的无线信号传播模型进行模拟:常见测距/向方法接收信号强度指示(ReceivedSignalStrengthIndication,RSSI)15（1）三边测量法三边测量法是根据3个已知坐标的节点到未知节点的距离来确定节点坐标。已知A、B、C三个节点的坐标分别为、和，它们到未知节点D(x,y)的距离分别为，如图所示，则通过计算可以得到以下三个式子：节点位置估计方法222222222xyxyxyaaabbbcccddd（-x）（-y）（-x）（-y）（-x）（-y）,aaxy,bbxy,ccxyabcddd、、16(2）三角测量法三角测量法的原理如图所示。主要是在测量信号到达角的情况下使用该方法，节点的位置可以通过三角形中的正弦和余弦法则求得。正弦定理：余弦定理：节点位置估计方法aCbcAB/sin/sin/sinAaBbCc2222222222cos2cos2cosABCBCaBACACbCABABc17（3）最大似然估计最大似然估计的原理类似于三边测量法，不同的是有三个以上的点的坐标和对应的距离是已知的，如图所示，假设n个点的坐标为相应的距离为，，，U的坐标（x,y）未知，节点位置估计方法112233(,),(,),(,),,(,),nnxyxyxyxy1d2d3ndd222()()iiixxyyd18非基于测距的定位算法19质心算法质心算法完全利用未知节点与导标节点是否连通进行定位，实现简单易行。也不需要节点之间进行协调，意味着具有良好的可扩展性。虽然质心算法的定位精度并不高，属于粗粒度定位算法，但可以满足那些对位置精度要求不太苛刻的应用。202、APIT算法APIT（ApproximatePoint-In-TriangulationTest）算法的思想是三角形覆盖逼近，未知节点处于多个三角形覆盖区域的重叠部分中。如图所示，未知节点从所有邻居导标节点集合中选择3个节点，测试是否位于这3个节点组成的三角形内部，重复这一过程直到穷举所有的三元组合或者达到期望的精度，然后计算所有覆盖未知节点的三角形的重叠部分的重心作为其位置估计。非基于测距的定位算法21在介绍了APIT算法的理论基础之后，下面介绍其具体实现过程。APIT算法可以分为三个阶段：1）导标节点信息接收和交换。未知节点接收导标节点的位置信息、节点ID和信号强度等信息，以及未知节点之间相互交换各自接收到的导标节点信息。2）APIT测试，即上面所述的判断是否位于导标节点三元组合形成的三角形内部。APIT算法223）计算三角形覆盖区域的重叠部分重心，将其作为待定位节点的估计位置仿真证明，APIT算法在导标节点比例较大时，能够获得较高的定位精度。3、DV-Hop算法DV-Hop（DistanceVector-Hop）算法是Niculescu等人根据距离矢量路由（distancevectorrouting）原理提出的一系列分布式定位算法（合称为“APS”算法）之一。除DV-Hop算法外，APS算法还包括DV-distance、Euclidean和DV-coordinate。DV-Hop算法的核心思想是未知节点通过路由方法“测量”与导标节点之间的最少跳数（hopcount）,并计算每跳的平均距离，以最少跳数和平均跳距的乘积作为未知节点和导标节点之间的距离估计。非基于测距的定位算法231）“测量”与导标节点之间的最少跳数采用典型的距离矢量路由交换协议，导标节点向邻居节点广播导标节点信息，包括位置信息和跳数（初始值为0）。收到这些信息的节点记录位置信息和跳数（把数值加1），然后转发给它的邻居节点，这样网络中的所有节点能够记录每个导标节点的位置和相应最少跳数。2）计算与导标节点的估计距离导标节点根据在第1）阶段中记录的其他导标节点的位置信息和相应的最少跳数，按照下式估计每跳的平均距离：DV-Hop算法22(()())/iijijjjijicxxyyh24DV-Hop算法DV-Hop算法的不足是只能在各向同性的网络中表现良好性能，因为只有在各向同性的网络中平均跳距才能比较合理地估计节点之间的实际距离。不过DV-Hop算法实现简单，也不存在测距误差的影响。254）Euclidean定位算法Euclidean定位算法给出了计算与锚节点相隔两跳的未知节点位置的方法。假设节点拥有RSSI测距能力。如图所示，已知未知节点B、C在锚节点L的无线射程内，BC距离已知或通过RSSI测量获得；节点A与B、C相邻。对于四边形ABCL，所有边长和一条对角线BC已知，根据三角形的性质可以计算出AL的长度(节点A与L的距离)。从几何学可以得知结果有A和A'两种可能,但是由于未知节点和L不相邻，所以只有A这一种情况。使用这种方法，当未知节点获得与3个或更多锚节点之间的距离后定位自身。非基于测距的定位算法222cos()/2ABACBCACBC222cos()/2BLBCCLCLBC2222cos()ALACCLACCL26Euclidean定位算法，可以精确的计算出与锚节点相隔一跳的未知节点与锚节点的距离，较DV-Hop等需要估