随着通信技术、嵌入式计算技术和传感器技术的飞速发展和日益成熟，具有感知、计算和通信能力的微型传感器开始出现。由大量成本低廉的这类传感器节点通过无线方式组成了传感器网络。它具有远程监控、实时监测、能在恶劣或特殊环境工作的许多优点，已被列为对人类未来生活产生深远影响的十大新兴技术之首。
无线传感器网络的工作区域很广，适用于人们无法接近的恶劣或特殊环境，传感器节点主要通过飞行器撒播、人工埋置和火箭弹射等方式任意散落在被监测区域内。节点的位置信息都是随机的，节点所采集到的数据，若没有位置信息几乎是没有应用价值的。所以，在无线传感器网络的应用中，节点的定位也就成为了关键的问题。
获得节点位置信息的直接想法是使用全球定位系统（global positioning system，GPS）实现，但是，由于传感器节点的数量非常巨大，达到数千甚至数万，成本太高。另外，传感器节点是采用电池供电，其能量不仅十分有限，而且，无法补充，因此，不适宜在每个节点都装备高能耗的GPS设备。目前，主要解决方法是利用少量已知节点（采用GPS定位或者预先放置的节点），通过节点定位算法，来获得节点的位置信息。
一、节点定位算法的基本原理
在三维空间中，知道了1个点到4个已知参考点的距离，就可以确定该点的坐标。在传感器网络中，坐标系是二维空间，因此，只要知道了1个节点到3个参考节点的距离就可以确定节点的位置。假设3个参考点的坐标分别为（x1，y1），（x2，y2），（x3，y3），待确定位置节点的坐标是（xi，yi），该节点到3个参考节点的距离分别是λ1，λ2，λ3，根据二维空间距离计算公式，可以获得一个非线性方程组，采用线性化方法来求解，可以得到待定位置节点的坐标（xi，yi）。在节点定位算法中，按照上述方程求解，就可以得到待定位置节点的坐标，从而达到定位的目的。
二、节点定位算法
根据定算法的基本原理，目前，已经提出了一些适用有效的传感器网络的节点定位算法，主要有DV2hop算法、DV2distance算法、位置分发算法、Euclidean算法等。
1．DV2hop算法
DV2hop算法是Niculescu等人为了避免对节点间距离的直接测量而提出的。该算法基本思想是将待定位节点到参考节点之间的距离用网络中节点的平均每跳距离和节点之间的跳数乘积来表示，使用三角定位来获得节点的位置信息。虽然待定位节点通信范围内的参考节点数量不多，但是，采用上述方法可以获得到通信范围外多个参考节点的估计距离，利用大量的信息获得该节点的位置。在网络平均连接度为8，参考节点比例为5%情况下时，算法的定位误差大约是节点射频通信距离的1/3左右。
在定位算法开始之前，网络中除参考节点外，其他的节点都没有位置信息。网络内的节点需要获得它们到每个参考节点的跳数，将跳数与平均每跳距离相乘，就可以获得该节点到每个参考节点的估计距离。将计算所得距离与参考节点的位置信息一起，按照节点定位算法的基本原理，进行三角计算，就可以获得该节点的位置信息。
在算法开始的时候，每个参考节点都发出一个包括自己位置信息、地址和跳数值为0的位置信息包，它们周围所有跳数为1的邻居节点都收到这样的信息，将参考节点位置信息和跳数记录下来，并将收到信息包的跳数+1，再向自己的邻居节点广播。由于广播是全向的，一个参考节点发出的广播信息可能会多次到达一个节点，这导致了节点可能会收到很多多余的广播信息。为了防止广播信息的无限循环，只有最新收到的信息才被重新广播。信息是不是最新，指该节点已经收到某个参考节点的广播，而且，最近收到的信息包中的跳数大于或等于存储器中存储的到该参考节点的跳数。如果收到的信息是最新的信息，就会引起一个新的广播，而旧的信息则被丢弃，而不会进行广播。
一个参考节点从其他参考位置节点收到跳数信息，它就可以估计平均每跳距离，并向整个网络广播该信息。参考节点i的平均每跳距离可以按如下步骤的计算，首先，求出参考节点i到每个单位节点的距离，然后，在求出参考节点i到每个单位节点的跳数，两者相除，就得到了参考节点i的平均每跳距离。在实验中发现，当总跳数大于一定的值之后，每个节点所计算的平均跳数基本一样。这个值与网络的平均连接度成近似反比关系，也就是说，节点分布越密集的网络的平均每跳距离也越小。
DV2hop算法的优点在于它比较简单，并且，不需要进行节点之间的距离测量，可以避免测量时带来的误差，节点不需要任何附加硬件支持，是无线传感器网络节点定位的一个理想方案。但是，通过研究发现，这种算法有一些值得改进的地方:在获得平均每跳的计算过程中，节点之间通信量过大；没有考虑不良节点（本质上无法定位的节点）的影响，导致平均定位误差较大。
2．DV2distance算法
为了降低节点的性能要求，BadriNath等人提出了DV2distance算法。DV2distance算法与DV2hop类似，所不同的是相邻节点使用RSSI测量节点间点到点距离，然后，利用类似于距离矢量路由的方法传播与参考节点的累计距离。当未知节点获得与3个或更多参考节点的距离后使用三角测量定位。DV2distance算法也仅适用于各向同性的密集网络。实验显示，该算法的定位精度为20%（网络平均连通度为9，参考节点比例为10%，测距误差小于10%）；但随着测距误差的增大，定位误差也急剧增大。
该算法与DV2hop算法相比较，优点在于它对节点的要求比较低，节点不用储存网络中各个节点的位置信息，减少了节点间的通信量，从而节省了节点的工作能量。不足之处在于，因为它直接测量节点间的距离，这样，对距离的敏感性要求较高，误差较大。
3．位置分发算法
为了使网络中的节点充分利用，JoeAlbowicz提出了位置分发算法。一个节点，当给它很高的位置信息时，它就可以作为它的邻居节点的参考节点，并且，可以扩大网络系统的覆盖面积。本文分四部分讨论这个算法。
（1）参考选择
在选择参考节点的阶段，一个节点从它临近的参考节点那里获得参考信息，当它获得一系列参考节点信息后，它就要用一种方法将这些参考节点归类排序。参考节点显示出它们的剩余价值，节点选择出最低的剩余价值的参考节点在算法下一个阶段应用。对于一个坐标是X，Y，Z的节点的剩余价值是这样定义的。它的剩余价值等于该点到每个参考节点的距离和该参考节点的标准覆盖范围的差的平方。换句话来说，剩余价值是参考节点到被计算距离的节点和参考节点的范围半径的不同面积的总和。从最初参考节点来考虑，剩余价值的值应该接近0。
（2）距离测量
当节点选择一系列参考节点后，它就要收集到每个参考节点的距离。对于一些测量技术来说，当节点收到从参考节点发来的消息时，它所需要的一些位置信息应该包括在参考节点的信息里。对于少数的精确的测量技术，节点可以收集一系列的信息样本，直到这些样本信息的变化趋近于0。节点这时候就可以使用这些信息样本，即节点与参考节点之间的距离。节点也可以拒绝应用一些参考节点，这些参考节点提供的信息样本是不稳定的。
（3）位置估计
当一个节点估计出它到参考节点的距离时，它自己的位置也可以估计出来了。在这种方法中，运用了线性方程和泰勒级数。这种方法通过泰勒展开公式，将非线性方程近似成线性方程。通过线性迭代得到需要的参数。但不幸的是，在某些事例中，这种方法会产生很大的误差，结果振动幅度很大。很多种技术被应用，用来减少这种情况的发生。很小心地选择最开始的系统参数。使用可以接受的参数，这样，才可以使系统达到一种静态的平衡。
（4）循环阶段
如果一个节点获得一个合理的位置预算，它就可以在协议中作为一个新的参考节点，现在节点最需要的就是通过参考节点的限制标准。因此，很大一部分节点都对位置得到很好的预算，只有更多地精确地节点的位置预算，这样，才可以扩大网络的覆盖范围，并且，可以避免大误差的产生。新的参考节点既增加了已知确切位置的节点个数，同时，提高了位置预算的精确度。可以通过上述方法，不断精确地预算出一些节点的位置，这些已经知道精确位置的节点又可以在网络中作为参考节点应用。这样，通过不断的循环，可以得到网络中大部分节点的精确位置，在无线传感器网络的应用中可以起很重要的作用。
4．Euclidean算法
为了降低对参考节点的依赖性，Niculescu等人提出了Euclidean算法。这种方法直接将几何距离传送给节点，这也是最和GPS相近的一种方法。任意一个节点A必须要有2个邻居节点B和C，并且，这2个邻居节点都要被参考节点L所固定，例如:四边形ABCL。精确的测量距离AB，AC，BC。所以，就形成了这样一个条件:任意的B和C，除了要是A的邻居节点外，它们2个也要是邻居节点，或者A知道BC的距离，在当地的无线传感器网络中，要知道所有A的邻居节点位置。
在任何情况，对于四边形ABCL来说，每条边都知道，并且，对角线BC也知道，这样，就使得A可以计算另外的对角线AL，也就是节点A到参考节点L的几何距离。现在有2种可能的情况:一种是A在节点BCL的外侧，一种就是A在BCL的中间，就是图中A的位置。这2种情况下，A到参考节点L的距离是不同的，如何区分，主要用以下方法辨别:当节点A有一系列直接邻居节点时，并且，这些直接邻居节点都是参考节点L所确定的，或者通过节点B和C有其他普通邻节点。通过这些节点可以大概估算出节点A的位置，如果不能很好地选择出A的位置，那么，距离AL是不可用的，直到通过更多的邻居节点或者2跳节点确定A的位置为止。当节点A的正确位置确定后，那么，根据图的实际关系，就可以得到三角形ACB。BCL和ACL。这样，通过计算，就可以得到对角线AL了。然后，经过运算，就可以得到节点A的位置信息。
5．算法比较
无线传感器网络节点定位算法的主要思想，就是在已知一些参考节点的情况下，以这些参考节点为定位坐标，通过三角计算方法来确定其他节点的位置，上述的4种节点定位算法的主要算法思想也是如此。它们的区别之处在于计算待测节点和参考节点之间距离的不同，是通过节点间跳数与节点每跳距离来计算，而DV2distance算法和Euclid2ean算法和位置分发算法主要是通过射频通信来直接计算距离。另一方面，从节点性能要求比较，DV2hop算法对节点性能要求较高，而其他3种算法则较低。对参考节点依赖性比较，位置分发算法，Euclidean算法比DV2hop算法和DV2distance算法要低；在网络通信量的比较上，DV2distance算法则比其他3种算法的通信量要少；而在定位误差方面，位置分发算法的误差要小于其他算法。经过一系列对比，位置分发算法无疑是最好的，它降低了对参考节点的依赖性，并提高了平均定位精度。
三、结束语
本文主要分析了无线传感器网络节点定位算法的基本原理，通过概述现有的几种典型节点定位算法，并对算法性能进行分析比较，位置分发算法能极大地降低了网络通信量，并提高了平均定位精度。无线传感器网络的节点定位算法中，参考节点的确定是关键问题。因此，如何准确地确定参考节点将是以后的研究关键；为提高节点位置计算精度，距离计算方式也是节点定位算法研究的一个重点。
[
本帖最后由 liujq 于 2008-1-28 11:51 编辑 ]
