1引言

      无线传感器网络(WSNs)是由许多传感器节点通过自组织的形式组成的一种特殊的Ad-hoc网络，每一个传感器节点由数据采集模块、数据处理和控制模块、通信模块和供电模块等组成，此外还可能包括与应用相关的其他部分，比如定位系统、动力系统等。借助于内置多样的传感器，可以测量温度、湿度、气压、化学等我们感兴趣的物理现象。由于无线传感器网络在军事、医学、环境保护等领域有着非常广阔的应用前景，受到众多国家科研机构的重视。

      传感器节点的自身定位是传感器网络应用的基础。例如目标监测与跟踪、基于位置信息的路由、智能交通、物流管理等许多应用都要求网络节点预先知道自身的位置，并在通信和协作过程中利用位置信息完成应用要求。若没有位置信息，传感器节点所采集的数据几乎是没有应用价值的。所以，在无线传感器网络的应用中，节点的定位成为关键的问题。采用GPS(全球定位系统)是获得位置信息的一种方法，应用是非常广泛的。但他不适用于传感器网络，首先，无线传感器网络中节点数目比较多，因此单个节点的成本不能太高，为每一个节点配备GPS的方案太昂贵了；其次，由于传感器网络的布设特点，能源不易更换，要求网络有较长的生命周期，而GPS定位系统对能源的消耗过大，同时还会增加传感器节点的体积，也不适宜；最后，GPS不适于在屋内、水下和严重信号阻碍等环境下的应用。因为传感器网络的定位技术要适应传感器微型化、低成本和低能耗的要求，尽量延长传感器网络的生命期，只有通过网络内部节点之间的相互测距和信息交换，形成一套全网节点的坐标，才是经济可行的定位方案。

      2现有定位算法研究

      最早期的基于无线网络的室内定位系统，都采用了额外的硬件和设备，如AT&TCambridge的ActiveBat系统，采用了超声波测距技术，定位的物体携带由控制逻辑、无线收发器和超声波换能器组成的称为Bat的设备，发出的信号由安装在房间天花板上的超声波接收器接收，所有接收器通过有线网络连接；在微软的RADAR系统中，定位目标要携带具有测量RF信号强度的传感器，还要有基站定期发送RF信号，在事先实现的RF信号的数据库中查询实现定位；MIT开发了最早的松散耦合定位系统Cricket，锚节点(预先部署位置的节点)随机地同时发射RF和超声波信号，RF信号中包括该锚节点的位置，未知节点接收这些信号，然后使用TDOA技术测量与锚节点的距离来实现定位。

      以上系统都需要事先的网络部署或数据生成工作，无法适用于Ad-hoc网络。现阶段研究较多的是不基于测距(Range-free)的定位算法，这样就无需增加额外的硬件，还可以减小传感器节点的体积。除此之外，较好的算法还要具备以下几点特性：

      (1)较小的能耗

      传感器节点所携带能源有限和不易更换的特点要求定位算法应该是低能耗的。

      (2)较高的定位精度

      这是衡量定位算法的一个重要指标，一般以误差与无线射程的比值来计算，20％表示定位误差相当于节点无线射程的20％。

      (3)计算方式是分布式的

      分布式的定位算法，即计算节点位置的工作在节点本地完成，分布式算法可以应用于大规模的传感器网络。

      (4)较低的锚节点密度

      锚节点定位通常依赖人工部署或GPS实现。大量的人工部署不适合Ad-hoc网络，而且锚节点的成本比普通节点要高两个数量级。

      (5)较短的覆盖时间。

      2.1算法分析

      近些年提出很多典型的算法，但都有各自比较明显的优点和缺点。早期提出的质心算法和APIT算法要求有较高的锚节点密度，凸规划算法和MDS-MAP算法需要集中式的计算；Euclidean算法基于围绕在锚节点周围的节点的局部几何拓扑，但距离的测量较为复杂。在所有算法中Savarese等提出的Robustpositioning算法和Sav-vides等提出的N-hopmultilateration算法是典型的求精算法，与其他算法相比，是较为优秀的算法。

      2.1.1Robustpositioning算法

      Robustpositioning算法分为测距、定位和求精三阶段，在测距阶段，算法采用了DV-hop算法的思想，首先使用典型的距离矢量交换协议，使网络中所有节点获得距锚节点的跳数(distanceinhops)。第二阶段，在获得其他锚节点位置和相隔跳距后，锚节点计算网络平均每跳距离，然后将其作为一个校正值(correction)广播至网络中。当接收到校正值后，节点根据跳数计算与锚节点距离。如图1所示，锚节点L2计算出他的网络平均每跳距离为(40+75)／(2+5)=16.4m。

      在定位阶段，采用了最小二乘法(Lateration)进行计算，当未知节点获得与3个或3个以上锚节点(xi，yi)的距离di时，根据以下式子，可推出计算公式：

      由式(1)可推出：

      令：

      利用公式(2)，(3)可求得：

      最后利用公式：

      来判断所求的结果是否有效，当residue超过无线射程时，结果是无效的。

      在求精阶段，节点测量得到所有一跳邻居的距离并依次更新自己的位置。该算法的所有位置计算都使用最小二乘法。算法引入了置信度来提高求精阶段的性能，置信度被用来在三边定位中加权。当未知节点更新其位置估计时同样也更新其置信度。这样，网络的平均置信度将随迭代而增加，提高了覆盖度和精度。

      该算法的定位精度比较高，在网络连通度较高的情况下能较好地容忍距离误差。但由于对网络拓扑的依赖，需要较长的覆盖时间。

      2.1.2N-hopmultilateration算法

      在N-hopmultilateration算法中，测距使用的是超声波测距技术，该算法也分为3个阶段，第一阶段是生成协作子树，根据判定条件，在网络中生成多个由未知节点和锚节点组成的限制条件完整或超限制条件的构形，称为协作子树。每个构形包括n个未知变量(未知节点的坐标)和至少n个非线性方程式，并确保每个未知变量拥有惟一解。未被协作子树包含的节点在整个算法的后处理阶段进行定位。

      第二阶段是对未知节点位置的粗略估计，他通过粗略未知节点和锚节点问的距离来估算未知节点的位置。如图2所示，未知节点C在锚节点A，B所形成的Boundingbox里面，可推算出节点所在位置的x坐标的取值范围是(|xA-a|，|xB+(b+c)|)。

      第三阶段采用了循环求精，根据预设的定位精度，使用卡尔曼滤波技术在每个协作子树范围内(每个节点位置有惟一解)对第二阶段的结果进行循环求精。

      该算法要求锚节点要求锚节点要部署在网络的边缘才能达到较好的效果，而且循环求精的次数无法预知。

      2.1.3算法分析

      对于传感器网络节点定位算法，定位精度是个主要的评估标准，上述两种算法都采用了求精的步骤，仿真结果显示定位精度有了比较大的提高，但各自又有不足之处，在测距阶段，Robustpositioning算法采用了DV-hop的算法，DV-hop算法是基于距离矢量交换协议的，在大型网络中需要较长的覆盖时间，而N-hopmultilateration算法却采用了硬件测距的方法，提高了网络的成本。

      N-hopmuItilateration算法可以根据配置采用集中式和分布式两种计算方式，通信开销基本相当，他在定位阶段，采用了Boundingbox的方法，计算量要比最小二乘法小很多，是非常值得借鉴的思想。而对N-hopmulti-lateration算法，锚节点的密度和分布对算法的定位精度有较大的影响，而Robustpositioning算法在这方面的影响较小。总体上讲，Robustpositioning算法要比N-hopmultilateration算法具有更大的优势，今后主要的工作是如何提高该算法的覆盖速度，来适应大规模网络的需要。

      3结语

      近些年来，国内外提出了很多关于传感器网络节点的定位算法，每一种算法都有各自的特点。对于精度比较高的算法，通信开销和收敛速度等方面的性能可能就会有所下降，采用硬件测距可以提高定位精度，但同时会增加传感器节点的成本。根据具体业务的需要，定位的条件和要求会有所不同，因此，要针对具体的应用设计和采用适合的定位算法。传感器网络定位技术还有比较大的研究空间，主要集中在传感器节点测距硬件技术的研究、传感器网络定位算法仿真平台的研究与开发和基于复杂地理条件下的定位算法研究等方面。