无线传感器网络节点定位技术.docx

无线传感器网络节点定位技术定位即确定方位、确定某一事物在一定环境中的位置。在无线传感器网络中的定位具有两层意义：其一是确定自己在系统中的位置；其二是系统确定其目标在系统中的位置。在传感器网络的实际应用中，传感器节点的位置信息已经成为整个网络中必不可少的信息之一，很多应用场合一旦失去了节点的位置信息，整个网络就会变得毫无用处，因此传感器网络节点定位技术已经成了众多科学家研究的重要课题。2.1 基本概念描述在传感器网络中，为了实现定位的需要，随机播撒的节点主要有两种：信标节点（Beacon Node）和未知节点（Unknown Node）。通常将已知自身位置的节点称为信标节点，信标节点可以通过携带GPS定位设备（或北斗卫星导航系统BeiDou（COMPASS）Navigation Satellite System、或预置其位置）等手段获得自身的精确位置，而其它节点称之为未知节点，在无线传感器网络中信标节点只占很少的比例。未知节点以信标节点作为参考点，通过信标节点的位置信息来确定自身位置。传感器网路的节点构成如图2-1所示。图2-1 无线传感器网络中信标节点和未知节点Figure 2-1 Beacon nodes and unknown nodes of wireless sensor network在图2-1中，整个传感器网络由4个信标节点和数量众多的未知节点组成。信标节点用B来表示，它在整个网络中占较少的比例。未知节点用U来表示，未知节点通过周围的信标节点或已实现自身定位的未知节点通过一定的算法来实现自身定位。下面是无线传感器网络中一些常用术语：(1) 邻居节点（Neighbor Nodes）：无需经过其它节点能够直接与之进行通信的节点；(2) 跳数（Hop Count）：两个要实现通信的节点之间信息转发所需要的最小跳段总数；(3) 连通度（Connectivity）：一个节点拥有的邻居节点数目；(4) 跳段距离（Hop Distance）：两个节点间隔之间最小跳段距离的总和；(5) 接收信号传播时间差(Time Difference of Arrival，TDOA)：信号传输过程中，同时发出的两种不同频率的信号到达同一目的地时由于不同的传输速度所造成的时间差；(6) 接收信号传播时间（Time of Arrival，TOA）：信号在两个不同节点之间传播所需要的时间；(7) 信号返回时间（Round-trip Time of Flight，RTOF）：信号从一个节点传到另一个节点后又返回来的时间；(8) 到达角度(Angle of Arrival，AOA)：节点自身轴线相对于其接收到的信号之间的角度；(9) 接收信号强度指示(Received Signa1 Strength Indicator，RSSI)：无线信号到达传感器节点后的强弱值。2.2 节点定位技术性能评价标准在无线传感器网络定位技术中，不同的定位算法对定位结果有不同的影响，通常情况下有以下几个指标来衡量：（1） 定位精度（Positional Accuracy）：定位精度是指空间实体位置信息（通常为坐标）与其真实位置之间的接近程度，它是衡量传感器网络定位的首要指标，只有达到一定定位精度的定位算法才是真实有效的。定位精度分为绝对精度和相对精度，绝对精度是指误差的绝对值，以长度为单位表示；相对精度是指误差值与节点之间距离的百分比。（2） 有效定位范围（Effective Rang of Orientation）：定位系统所能定位的有效范围。在WSN中要满足大多数节点能够被定位，只有覆盖大范围的节点定位才有意义。（3） 节点密度（Node Density）：节点密度就是指的播撒的传感器网络节点的疏密程度。在传感器网络中节点密度对定位的性能影响很大，一般情况下节点密度越高定位的精度也会越高，反之则会降低节点的定位精度。在WSN中针对不同的定位算法所需要节点密度也不相同，另外传感器节点的性能和价格也决定了播撒的节点的密度。（4） 信标节点密度 (Density of Beacon Node)：信标节点密度是指信标节点在整个WSN 中所占的比例。信标节点具有自身定位功能，价格较贵，不可能大面积播撒，它节点的密度决定了定位的精度的高低。（5） 容错性和自适应性（Fault Tolerance and Adaptivity）：所谓容错性是指在故障存在的情况下系统不会失效，仍然能够正常工作的特性。容错即是 Fault Tolerance，确切地说是容故障（Fault），而并非容错误（Error）。自适应性可以看作是一个能根据环境变化能够智能调节自身特性的反馈控制系统，以使系统能按照一些设定的标准工作在最优状态。（6） 安全性（Security）：Security指的是指系统对合法用户的响应及对非法请求的抗拒，以保护自己不受外部影响和攻击的能力。WSN通常工作在物理环境较为复杂的区域，定位系统易受到环境或人为的破坏和攻击，从而无法达到在理想的无线通信环境所能达到的定位效果，因此定位系统和算法必须具有很强的安全性。 （7） 功耗（Power Dissipation）：功耗是指功率的损耗，在WSN设计过程中功耗始终是困扰其应用的一个主要方面。由于传感器节点的能量受限并且不容易得到补充，因此需要整个WSN能够以较小的能耗和高效的能量利用率来实现安全定位是当前研究的所面临首要的问题23。（8） 代价与成本（Cost and Consideration）：定位算法的代价一般包括时间代价、资金代价和空间代价。在保证定位精度的前提下，应使定位系统的代价最小，如定位所需的计算量、通信量、存储空间等。各个评价标准之间相互关联、相互影响的。某一个标准的好坏可能是由另外的一个或几个决定的，一个指标变坏的同时一个指标也会跟着变坏，因此在传感器网络的设计过程中要结合实际情况综合考虑。2.3 传感器网络节点定位算法在定位的实现过程中有许多算法，根据不同的标准有不同的分类方法。最常见的分类是：基于测距的 (Range-Based) 定位算法和距离无关的 (Range-Free) 定位算法。假若定位算法需要知道未知节点到参考节点或信标节点之间的绝对距离时，然后才能计算出未知节点坐标信息，这样的定位方法就可以称为Range-Based的定位算法。反之，其它的算法无需测量节点之间的距离值就称之为Range-Free的定位算法。Range-Based定位算法精度上优于Range-Free的定位算法，但需要测量距离，计算量比较大，需要消耗大量能量，并不适用于低功耗、低成本等应用领域。Range-Free的定位算法实现起来比较简单，计算量也较小，但并不能实现高精度的定位，是一种粗精度的算法。2.3.1 基于测距的定位算法基于测距的定位算法实现起来比较复杂，首先需要通过TOA、TDOA、AOA、RSSI等常用的测距技术来测量各个未知节点到信标节点的绝对距离值，这个阶段也称为测距阶段；测距结束后就要进行定位（计算坐标）阶段，即利用测距阶段所得的节点间的距离或方位等参数来计算出未知节点的位置，在此期间常用的算法有：三边测量定位法（Trilateration）、多边定位法（Multilateration）、三角测量法（Triangulation）、极大似然估计法（Maximum Likelihood Method）和角度定位法（Goniometry）等。下面分别针对这两个阶段进行分析： （一）测距阶段算法分析： TOA是根据信号的传播时间计算被测节点之间的距离。TOA算法虽然定位精度较高，但是该算法要求节点之间精确同步，使用复杂，对硬件要求太高，因此不太适合于无线传感器网络定位的应用。TDOA是在TOA的基础上所形成的算法。在该算法中，发射节点采用两种不同频率的无线信号同时发送一组信息到指定的相同区域，由于这两种信号的传输速度不同，因此到达目的地的时间也会有所差别。接收节点根据这个时间差以及两种信号的传输速度就可以计算出接收节点和发射节点之间的距离值。AOA是通过Triangulation来进行定位运算。在AOA算法中，未知节点首先要计算出相对于参考节点的方位角，这就使得该算法在复杂电磁环境中的定位性能很差，不能够满足现实生活中较多电磁干扰的环境中使用。RSSI是利用信道衰减模型，根据所接收到的信号的强弱来实现节点的定位功能。在实践应用中，信号在传输过程中必然会遇到干扰、反射、吸收等的影响，这就极大的降低了定位精度24-25。PDOA是通过测量接收信号相位差，求出信号传播的往返时间，然后计算信号往返的距离。NFER是通过近场电场和磁场的相位差来测量距离的。表2-1对以上六种基于测距定位算法进行了比较。表2-1基于测距定位算法比较Table 2-1 Comparison of distance-based location algorithmNameExtra hardwareEffective distanceInterference rejectionDistance-measuring errorTOAYshortweakersmallerTDOAYshortestweaksmallestAOAYshortestweaksmallestRSSINlongstrongbigPDOAYlongstrongbigNFERNshortweaksmall（二）定位阶段算法分析：Trilateration26是通过三个已知坐标的信标节点以及这三个信标节点到未知节点的距离信息，根据二维空间距离公式建立方程组，采用线性化方法来求解出未知节点的位置信息。假设已知三个信标节点A、B、C的坐标分别为、它们到未知节点D的距离分别为：、，未知节点D的坐标设为。可以得到下列方程： （2-1）根据上式可得未知节点D的坐标方程为： （2-2）Multilateration是已知三个以上信标节点的坐标信息以及信标节点到这个未知节点的距离信息，利用两点间的距离公式可计算出未知节点到信标节点之间的距离，最后利用最小二乘法（LS，Least Square）、极大似然估计（MLE，Maximum Likelihood Estimation）或最小均方误差（MMSE，Minimum Mean Square Error）等求出未知节点的坐标信息。Triangulation是通过未知节点的接收器天线阵列来测量出周边信标节点所发出信号的入射角信息，利用所得到的角度信息和信标节点的坐标信息，根据Trilateration算出未知节点的坐标。Maximum Likelihood Method27原理如图2-2所示。图2-2 最大似然估计法Figure 2-2 Maximum Likelihood Method在该算法中已知1，2，3，n等n个信标节点的坐标为：、，。它们到未知节点D的距离分别为：、，假设未知节点D的坐标为。那么存在如下公式： （2-3）从第一个方程开始分别减去最后一个方程可得： （2-4） 式（2-4）可表示为：，其中：、如下面（2-5）到（2-7）所示： （2-5） （2-6） （2-7）利用最大似然估计法或最小二乘法可得D的坐标为： （2-8）2.3.2 基于无需测距的定位算法基于测距的定位算法虽然能够实现精确定位，但往往也对硬件要求较高，导致硬件成本增加，不利于大面积、多领域、广角度的使用。无需测距的定位算法使用起来比较简单，只需要利用未知节点到参考节点之间的估计距离值或其它位置信息，然后用三边测量法或极大似然估计法来计算出未知节点的坐标信息。无需测距定位算法由于不需要精确测量节点间的距离信息，极大地降低了对节点硬件的要求，另外它是利用节点间的距离估计值来进行计算，因此受环境的影响较小，在许多对节点定位精度要求不高的应用场合能够大量使用。现有的基于无需测距的定位算法主要有：DV-HOP算法、质心算法、Amorphous算法、APIT算法、凸规划算法和MDS-MAP算法等。下面分别介绍这几种方法： （1） 质心定位算法（Centroid）质量中心简称质心（Centroid），指物质系统上被认为质量集中于此的一个假想点。在传感器网络中，质心是指多边形的几何中心28，多边形各个顶点坐标的几何平均值即为质心坐标。质心定位算法是University of Southern California的Nirupama Bulusu等提出的，该算法适用于室外节点密度较高情况下的定位，它是基于网络的连通性（Connectedness）实现对节点的定位。其基本思想是：未知节点根据自身设定的门限值来接收周围信标节点所发出的包含节点位置和ID的信息来确定其所在的区域，根据其接收到的信标节点的ID及位置信息计算所在区域的质心，并把这个区域的质心作为自身的定位结果。该算法简单易行，对硬件要求较低，不需要额外任何硬件设备，但在定位过程中需要较多的信标节点，另外该算法在定位过程中都假设节点拥有理想的无线信号传输模型，这与实际的情况还有很大的差别，因此影响了Centroid的定位精度。质心定位算法的基本原理如图2-3所示。图2-3质心算法示意图Figure 2-3 Diagram of Centroid Principle该算法中，多边形区域、的六个顶点坐标分别为：、，则区域的质心为： （2-9）（2） 不定型定位算法（Amorphous）Amorphous29是基于连通性的定位算法，它需要预先知道网络的连通度。算法实现过程中，首先未知节点计算与每个信标节点之间的最小跳数；然后计算未知节点到每个信标节点的跳段距离，其中假设网络中节点的通信半径相同；最后再利用Trilateration或MLE等算法来进行定位计算。Amorphous实现起来比较简单，但定位精度不是很高，另外还有两个显著的缺点：一是需要预先知道网络的连通度；二是定位过程中需要较高的节点密度。（3） 近似三角形内点测试法（APIT） APIT（Approximate Point-in-Triangulation Test）算法能够以较高的定位精度适应于复杂的地理环境。APIT定位算法在实现过程中未知节点首先通过收集邻居节点的节点标识符、位置信息、发射信号功率的大小等信息来确定该节点是否位于不同的信标节点所组成的三角形内，然后统计包含未知节点的三角形区域，并把这些三角形区域的交集构成一个多边形，这个多边形基本上确定了未知节点所在的区域并缩小了未知节点所在的范围，最后计算这个多边形区域的质心，并将质心作为未知节点的位置，这样就实现了未知节点的定位。APIT定位算法基本原理如图2-4所示。图2-4 APIT算法示意图Figure 2-4 Diagram of APIT Principle在图2-4中未知节点从它所能接收到信号的信标节点、中随机选择三个，并测试自身是否在这三个信标节点所组成的三角形中，测试完成后再随机选取另外三个信标节点继续测试，直到测试完所有的组合为止。在图2-4中，未知节点分别选取、并测试自身是否位于这三个信标节点所组成的三角形中，判断完成后也就确定了这些三角形的交叉区域（如图中的阴影部分）所组成的多边形，然后计算这个多边形的质心S，并把质心S的坐标作为该未知节点的坐标。APIT定位算法利用电磁波衰落模型，相对于别的定位算法有着更高的定位精度，对节点密度要求也低，在节点密度较高的情况下定位更为准确，另外APIT定位算法的通信量小且适用于电磁波不规则的模型，能够在大多数场合应用。（4） 凸规划定位算法凸规划定位算法(Convex Optimization)是一种集中式的定位算法，所谓的集中式的定位算法是相对于分布式定位算法而言的，集中式定位算法采用集中的思想，收集到所有的传感器节点的有效信息后统一进行定位计算，集中式定位算法的可扩展性不好，信号传输和处理比较麻烦，不能够灵活使用。凸规划定位算法的基本原理如图2-5所示：未知节点首先根据其通信半径和与之能进行通信的信标节点建立其可能存在的位置区域，当穷举完这些区域之后按照一定的标准对这些区域进行筛选和位置划分，最后确定一个矩形区域（如图中阴影区域外的矩形区域），计算出该矩形区域的质心并把它作为未知节点的坐标，以此来实现节点定位。图2-5凸规划算法示意图Figure 2-5 Diagram of Convex Optimization Principle（5） MDS-MAP定位算法MDS-MAP定位算法是University of Missouri-Columbia的Yi Shang等提出来的。该算法属于集中式定位算法，它是利用节点间的连通信息通过Dijkstra或Floyd算法生成节点间距矩阵，然后利用多维尺度分析技术来获得节点间的位置信息。MDS-MAP定位算法的实现主要分为以下三个步骤：（1）首先从全局角度出发生根据给出的节点间的连通信息，如具备测距能力的邻居节点间的测量距离和不具备测量能力的节点间所赋予的距离值，生成网络拓扑连通图，然后通过最短路径法（Shortest Path Algorithm）粗略地估计每对节点间的距离，生成节点间距矩阵。（2）将经典多维尺度分析技术应用于节点间距矩阵，从而计算出整个网络的2维或3维相对坐标系统，该坐标为相对坐标。（3）根据信标节点的位置及信标节点的密度对（2）中所得的节点相对坐标进行转换，使之成为绝对坐标系统。MDS-MAP定位算法基于多维尺度分析技术来进行节点定位，该算法对网络节点密度要求严格，在节点分布均匀的情况下，较少的信标节点就可以获得很好的定位结果。MDS-MAP算法中假设每一对节点之间都是连通的，当节点密度较小时，不仅节点的定位误差会非常大，两外还会导致许多节点无法进行定位。只有网络的连通度达到一定的程度时，所有的未知节点才